Detecting Campaign Promoters on Twitter using Markov Random Fields (ICDM'14) を読んだ
ICDM14からもう一本。一度も参加したこと無いけど来年は参加してみたいな。
概要
TwitterからCampaign Promotersを検出する。Campaign Promotersってのは企業によるマーケティングやら政府による何らかのキャンペーンとかをやってるTwitterアカウントのこと。ちょっと前に流行ってたけどキャンペーンとかマーケティングをステルスでやるアカウントが多いからそういうの見つけたいよねっていうモチベーション。
貢献
- 複数タイプのノード、エッジを扱えるようにMRFを拡張してT-MRF (Typed MRF) を提案
- Campaign Promotersを検出できるようにMRFのノードポテンシャルとエッジポテンシャルを設計
手法
一言で言えばタスク特化にした特殊なグラフを作って、MRFを使ってTwitterユーザがPromotersかNon-promotersかを推定するだけ。簡単。
少し詳細
まずUser-URL-Burst Networkっていうこんな感じのグラフを構築する（論文中 Fig.2）。
UserノードはTwitterアカウント、URLノードはTwitterに投稿されたことのあるURL、Burstノードは普段より明らかに多くのツイートが投稿された日にそれぞれ対応する。User-URL間のエッジはあるユーザがそのURLを含んだツイートをポストしたことがあれば張る。User-Burst間のエッジはユーザのツイートがそのBurstに含まれていれば張る。図にはなぜかないんだけどUser-Userエッジってのもあって、それはツイート内容の類似度やフォローしてるユーザの類似度が大きいユーザ間に張る（ただのフォローエッジではない）。
このグラフを作る理由は、PromotersはツイートにPromoteしたい対象のURLを含む事が多いし、短期間にまとめてPromote対象のツイートをする事が多いかららしい。PromotersがポストしたURLはPromoted URLである確率が高いし、Promoted URLをツイートするユーザはPromotersである確率が高い的な考え方。
これにMRFを適用するだけ。
- ノードが持つ確率変数はPromoters、Non-promotersかどうかを表す。これを推定したい。
- 異なるタイプのノードは異なるタイプの確率変数を持つから複数種類のノードを含むグラフにも適用できるようにMRFを拡張してT-MRFというのを提案、それを使う。ただ異なる確率変数を持つと言いながらこの論文ではどのタイプのノードもPromotersかNon-promotersかという確率変数しか持たない。
- 異なるタイプのノードに対しては異なるノードポテンシャルを設計する。例えばUserノードのノードポテンシャルはそのユーザのツイートの内容から決める。
- 異なるタイプのエッジに対しては異なるエッジポテンシャルを設計する。
ノードポテンシャルとエッジポテンシャルの設計についてはなんの検証もされていないのが残念。論文中には「予備実験で決定した」としか書いてない。むしろその辺が重要な気がするんだけど。うーん。
Markov Random Field (MRF)
ここらへん。
Markov random field - Wikipedia, the free encyclopedia
この論文では隣接ノード間の依存関係のみを考慮するpairwise MRFを使ってる。
実験
色々な手法（以下）と比較、提案手法が勝った！
- ロジスティック回帰：素性に何を使ったかは書いてないけど多分ノードポテンシャルに使ったものと同じものを使ってる。
- ICA (Iterative Classification Algorithm)：これについても詳細は書いてないけど、ロジスティック回帰でラベルなしユーザがPromotersかNon-promotersかを推定してその結果を次のイテレーションの学習に使うってのを繰り返す。
- T-MRF (ノードポテンシャルなし）
- T-MRF (Burstノードなし）
- T-MRF (User-Userエッジなし）
- T-MRF （全部入り）
感想
ヒューリスティクスもりもりだけどそれらの検証については書いてない。アルゴリズムの提案は重要だけどどの特徴が効いていい結果が出たのかもそれと同じくらい重要だと思うんだけどなあ。単なるロジスティック回帰とかICAに勝てるのはある意味当たり前なんだから提案手法のバリエーションともっと詳細に比較して欲しい。
