Yahoo!のニュースコメント欄からスパムを排除するには
論文紹介のコーナー．*1
今回紹介するのは，KDD'2011のUnbiased Online Active Learning in Data Streams (Wei Chu, Martin Zinkevich, Lihong Li, Achint Thomas, and Belle Tseng)．
Yahoo! Labsのグループによる研究です．(その後，第一著者はMicrosoftへ移動しています)
本論文は，ユーザーがコンテンツを生成できるウェブサービスから効率的にスパムやアダルトコンテンツを排除する手法について提案されています．
このようなサービス形態はUser-Generated Content(UGC)と呼ばれ，ニュースサイトのコメント欄や掲示板・SNS・ソーシャルゲーム・ユーザー投稿型動画サイトが主な例として挙げられます．
3行概要
研究目的
- Yahoo!等のサイトでは，毎日100万規模のコンテンツが生成されており，スパムやアダルトコンテンツの排除に多大なコストがかかっている．
- ルールベースや人手のチェックによるスクリーニングは不可能．機械的な手法で排除したい．
- しかし，機械学習によってスパムやアダルトコンテンツを排除するにしても，教師データが大量に必要．
- さらには，スパマーはこちらのスパム判定器の性質に合わせて新たなスパムを生成してくるため，それらに順応するための教師データは絶えず必要となる．
- つまり，not i.i.d.
- 本研究では，最近のスパムデータに最速で順応するための，学習に有用な少量のデータを抽出する方法について議論する．
能動学習
- 能動学習は，データにラベルを付与し学習するのに有用なデータを抽出するための手法．
- データにラベルを付与するコストが高い場合に，特に効果的な手法．
- ラベルの付与に専門家の知識が要求される．
- ラベルの付与に年単位の時間がかかる．
- 一刻も早い精度の向上が求められる．
- 能動学習には大きく分けて２種類ある．
- Pool-based Scenario : ラベル無しデータを大量に集め，その中から学習に有用そうなデータを選び出す方法.
- Stream-based Scenario : データがやってくるたびに，そのデータにラベルを付与するかどうかを選択する方法．（ラベル付与の有無にかかわらず，データはすぐに捨てる）
- 本研究では，大規模なデータをストリーム的に扱いたいため，Stream-based Scenarioを選択する．
重点サンプリング
- 本手法では，能動学習を用いる際に重点サンプリングを用いる．(2式)
- 能動学習を用いる場合，真のデータ分布と能動学習によって得られたデータの分布が大きく異なることがある．（サンプリングバイアス）
- この場合，能動学習によって得られたデータに関して最適化を行なっても，真のデータ分布に関する最適化問題を解いたことにはならない．
- サンプリングバイアスを解決するため，重点サンプリングを導入．
- 重点サンプリングは，能動学習によって得られたデータ点の出現確率を，真の分布との比によって重み付けをすることで不偏性を保証する．
学習手法
サンプリング手法
その他拡張
- 以下のモデル拡張を掲示
- Weighted Likelihood(3.1節)
- Decay Model(3.2節)
- not i.i.d.の時にオンライン学習・能動学習・データのシャッフルが有効となる例(4章)
実験
- 30日分のニュースサイトのコメント欄を用意し，スパム判定を行う．
- データ数は26万
- 特徴次元数は27万
- １データ当たりの平均非零要素数は90
- スパム率は1〜5%程度
- 始めの１日分は全て学習に用いる．
- その後の29日分のデータを能動学習によって学習し，精度を比較する．
- 実験結果は全て正確な数値が載っていないので，どの程度改善されたかは分からない．
- １日目のデータのみを用いて学習した場合と比べ，どの程度精度が向上したか，しか載っていない．
エントロピー基準・関数値基準・ランダムの３種類のサンプリング手法の比較
重点サンプリングの有効性
- 不変推定量となるようにパラメータを設定する場合，精度が明らかに向上することが示された．
その他
- オンライン学習の有効性を主張．
- １日目のデータのみから学習するよりも，その後のデータも用いて学習し続けるほうが明らかに精度が良くなる．（Figure 3)
- コンセプトドリフトに対応するには，ある程度過去の学習を忘却させたほうが良い事を主張．
- Decay Modelにより精度が向上することを確認．(Table 1)
