ACオートマトンとベイズ法に基づくスパム識別

背景

オープンな知識ソーシャルプラットフォームとして、Zhihu は「友好的」、「合理的」、「専門的」な議論の雰囲気を提供し、多数のユーザーの参加を促し、多くの高品質なコンテンツを生み出しています。しかし同時に、一部のスパマーも引きつけ、Zhihuに「違法」、「広告」、「わいせつ・ポルノ」、「個人攻撃」などの大量のジャンクコンテンツを生み出し、Zhihuユーザーの正常な議論や交流に深刻な影響を与え、ユーザーエクスペリエンスに大きな影響を与え、コミュニティ管理にも大きな妨害をもたらしました。

まずは、実際のゴミの一部を見てみましょう。

違法コンテンツ

「脳死状態」「IQが低い」など、侮辱的で誇張した方法で他人を嘲笑する。この種のコンテンツは、他者への敬意を欠き、悪意のある言葉を使って他者を挑発するため、議論を正常かつ効果的に進めることが不可能になります。

WeChatビジネスなどのジャンク広告もいくつかあります。

これらのスパムコンテンツは、Zhihu ユーザー間の正常なコミュニケーションに深刻な影響を及ぼします。これまで、当社のエンジニアは、それらを識別して処理するためのいくつかの方法を試してきました。たとえば、テキスト分類モデルの精度は 96% で、毎日 300 件以上の情報を識別し、DFA を使用してキーワードに基づいて多数の項目を呼び出します。これらの試みは一定の成果を上げていますが、リコールが不十分であったり、スパムではないコンテンツがリコールされすぎたり、偶発的な被害が多かったりします。このため、手動レビューを導入しましたが、迅速に処理できず、コンテンツが蓄積されやすく、管理者にとっても大きな負担となり、平均して週に 1 人の人員を消費していました。

初期の試みの結果は理想的ではなかったものの、多くのデータが蓄積されました。これらのデータを分析した結果、これらのスパムコンテンツにはパターンがあることがわかりました。これを基に、Aho-Corasick オートマトンを使用してマルチモード マッチングを実現し、その上にフィルタリング メカニズムを追加して、スパム コンテンツ分析システムの最初のバージョンを実装し、良好な結果を達成しました。

アホ・コラシック・オートマトン

AC オートマトン アルゴリズムは 1975 年にベル研究所で作成されました。このアルゴリズムは、複数のパターンの文字列を決定論的な有限状態マシン (DFA) に巧みに構築し、一致させる文字列を DFA の入力として受け取り、状態マシンに状態遷移を実行させます。特定の状態に到達すると、パターン マッチングが完了します。

​​

文字列「ushers」が入力されると、オートマトンは状態 0 から状態遷移を開始します。完全な状態遷移パスを図 2 に示します。

​​

AC で赤いノードに遭遇した場合、パターン マッチが発生し、一致したパターンは「he」、「she」、「hers」であることを意味します。

具体的には、Double Array Trie を使用して AC オートマトンを実装することができ、効率的なマルチモード マッチングを維持しながらスペースをさらに節約できます。

ベイズ法

AC オートマトンでは文字列から辞書内のキーワードを素早く見つけることができますが、要求のごく一部しか満たすことができません。つまり、正確性に関係なく大量のリコールが発生すると、明らかに偶発的な傷害が発生し、これも Zhiyou にとって非常に不親切です。間違いなく、この問題を解決するには「ベイジアン」方式を使用すればよいのではないだろうか、と尋ねる Zhihu ユーザーがいるでしょう。ほら、人々はスパム フィルタリングをかなりうまくやっているのに、なぜまだ AC が必要なのでしょうか。はい、はい、はい、その通りです。しかし、実験により、直接フィルタリングに「ベイズ」法を単純に使用した場合、精度と再現率はあまり理想的ではないことが判明しました。その理由は、1) Zhihu ユーザーは幅広い知識と多様な思考を持っていること、2) ロングテールで、多くの単語が比較的頻繁に出現しないことです。

AC + ベイジアン > 最大 { AC, ベイジアン }

上記の問題を考慮して、設定されたカテゴリキーワードに応じてACオートマトンを使用して該当カテゴリのコンテンツを識別し、「ベイズ」法の考え方を使用して各カテゴリのスパムコンテンツを正確にフィルタリングすることを提案しました。問題を解決するためのアイデアが得られたので (アイデアは非常に重要です)、AC とベイジアンを使用してスパム フィルタリングを作成する方法を見てみましょう。ここに写真が直接あります。一枚の写真は千の言葉に値します。

​​

図3の「メインキーワード」は、AC自動機を使用してキーワードで囲まれた該当カテゴリの内容です。描写後、「オプション」で設定された戦略を使用して、各カテゴリのスパム コンテンツをフィルタリングします。戦略は、「ベイジアン」の考え方を使用して要約されます。

以下では、コメントデータを例に、ベイズ法を使って戦略をまとめる方法を紹介します。

まず、サンプルデータを分析し、各単語を抽出し、通常のコメントとスパムコメントにおける各単語の頻度を計算します。たとえば、「sb」という単語が 1,000 件のスパムコメントのうち 500 件に出現し、その頻度は 0.5 であるとします。また、1,000 件の通常のコメントでは、その単語が含まれるのは 2 件だけなので、その頻度は 0.002 となります。新しいコメントに「sb」という単語が含まれている場合、それがスパムコメントである確率は式 1 を使用して計算できます。 (ここで、S と H はそれぞれスパムコメントと通常のコメントを表し、W は単語「sb」を表し、P(S) はスパムコメントの確率を表し、P(W/S) はスパムコメントにおける W の頻度を表します)

​​

（フォーミュラ1）

事前の知識がない場合は、通常、P(S)=P(H=0.5)と仮定します。前の例では、P(S/W)=0.996 と簡単に計算できます。これは、「sb」という単語でスパムコメントを簡単に区別できることを意味します。このように単語をマイニングすることで、もちろん肯定的な観点からも検討することができます。たとえば、「I」という単語は、データ内でスパムコメントではないとより適切に区別できます。さらに、複数の単語の共起や単語間の空間的な構造関係も考慮することができます。これらはすべて現在のロジックによってサポートされています。

具体的な実装では、図 4 に示すように、実際の効果を見てみましょう。 （議論に資さない内容も扱います）

オンライン効果は図5に示されています。

このロジックはアルゴリズムロボット「Wall-E」の頭脳に統合されており、コメント、プライベートメッセージ、回答、質問など、Zhihuの多くのシナリオで毎日生成されるスパムコンテンツを99％の精度で処理します。毎日3,000件以上のスパムコメントを処理しています。オンラインになってからは、封建主義や迷信的な質問が数万件、個人的なタスクを代行して完了することに関する質問が数千件、医療アドバイスを求める質問が数千件、その他の違法な質問が数千件処理され、Zhihuユーザーが「友好的な」ディスカッション環境を維持するのに役立っています。

さらに、このシステムにより、オペレーターはワンストップのセルフサービス戦略管理を実装するのにも非常に便利になります。まず、サンプルを通じて戦略を策定し、次にオフライン バージョンを通じて戦略を検証し、その精度と再現率を評価し、最後に自分で戦略をオンラインで起動します。プロセス全体でエンジニアの介入が不要になり、運用効率が大幅に向上します。

要約と展望

友好的な議論や交流を促進するために、私たちは多くのスパムを積極的に特定し、対処するという小さな一歩を踏み出しました。しかし、まだ道のりは長い。今後、私たちはロボット「ウォーリー」のために、自動誘導戦略やディープラーニングの導入など、より完全でインテリジェントな頭脳を構築し、より科学的で効率的な認識能力を確立し、全自動であらゆるコンテンツを正確に識別します。

AC オートマトンと「ベイジアン」思考に基づくコンテンツ認識システムは、スパム コンテンツの識別を出発点として構築されましたが、このシステムは世論、その他のコンテンツ分類などの他のシナリオにも適用できますが、ここでは詳しく説明しません。