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

条件付き確率場の推論と学習 - SlideShare

この論文では隣接ノード間の依存関係のみを考慮するpairwise MRFを使ってる。

実験

色々な手法（以下）と比較、提案手法が勝った！

• ロジスティック回帰：素性に何を使ったかは書いてないけど多分ノードポテンシャルに使ったものと同じものを使ってる。
• ICA (Iterative Classification Algorithm)：これについても詳細は書いてないけど、ロジスティック回帰でラベルなしユーザがPromotersかNon-promotersかを推定してその結果を次のイテレーションの学習に使うってのを繰り返す。
• T-MRF (ノードポテンシャルなし）
• T-MRF (Burstノードなし）
• T-MRF (User-Userエッジなし）
• T-MRF （全部入り）

感想

ヒューリスティクスもりもりだけどそれらの検証については書いてない。アルゴリズムの提案は重要だけどどの特徴が効いていい結果が出たのかもそれと同じくらい重要だと思うんだけどなあ。単なるロジスティック回帰とかICAに勝てるのはある意味当たり前なんだから提案手法のバリエーションともっと詳細に比較して欲しい。

scikit-learn準拠の学習器を作ってgrid searchとかcross validationする

Python Advent Calender 2014の19日目。

scikit-learnに準拠した学習器を自分で実装してscikit-learnに実装されているgrid searchとかcross validationを使えるようにするお話。Pythonの話というか完全にscikit-learnの話なんだけど、まあいいよね。

scikit-learnについてはこの辺がわかりやすいかな。

pythonの機械学習ライブラリscikit-learnの紹介

はじパタlt scikit-learnで始める機械学習

scikit-learn準拠にするには？

全部下のページに書いてある。

Contributing — scikit-learn 0.15.2 documentation

やること

1. sklearn.base.BaseEstimatorを継承する
2. 回帰ならRegressorMixinを（多重）継承する
3. 分類ならClassifierMixinを（多重）継承する
4. fitメソッドを実装する
   • 学習データとラベルを受け取って学習したパラメータをフィールドにセットする
   • initでパラメータをいじる操作を入れるとgrid searchが動かなくなる（後述）
5. predictメソッドを実装する
   • テストデータを受け取ってラベルのリストを返す

実装例（リッジ回帰）

scikit-learn-compatible Ridge Regression

Grid search

使用例

パラメータlambをうまく選んでやらないといけない。scikit準拠で実装したのでscikitに実装されてるgrid searchが使えて簡単にパラメータのバリデーションが出来る。

GridSearchCVに学習器RidgeRegression()とパラメータのリストparametersとデータを何分割するかcvを与える。それでfitしてbest_estimator_を取るだけでスコアが最も高かったパラメータを持った学習器が手に入る。Grid searchなんてめんどくさい作業がたった４行で出来るなんて！

Grid search for oreore regression

結果

青が学習したい関数、青い点がgrid searchに使ったデータ、緑が学習した曲線。うまくパラメータ（ラムダ）が選ばれて過学習してない。やったね！

Cross validation

使用例

5-fold cross validationをする。簡単のためラムダは0にした。

Cross validationもものすごく簡単で、学習器、データ、cv、スコアとして何を使うか（ここではMSE）を渡すだけ。結果としてcvの数だけ指定したスコアが返ってくる。たったの３行。

Cross validation for oreore regression

結果

$ python cross_validation.py
-0.0552436216908

なぜかMSEなのに負の結果が帰って来て困惑したけどこれは仕様らしくて、下のページで議論されてる。どうやらMSEが-1倍された値が返ってくるらしい。

MSE is negative when returned by cross_val_score #2439

initでパラメータをいじるとダメ

例えば上で実装したRidgeRegressionの6行目を下のように変えるとgrid searchがエラーを吐いて動かなくなる。

self.lamb = 2*lamb

initではパラメータの代入しかしちゃいけないっぽい。公式にもこう書いてある。

As grid_search.GridSearchCV uses set_params to apply parameter setting to estimators, it is essential that calling set_params has the same effect as setting parameters using the init method. The easiest and recommended way to accomplish this is to not do any parameter validation in __init__. All logic behind estimator parameters, like translating string arguments into functions, should be done in fit.

まとめ

scikit-learn準拠の学習器を作ってgrid searchやcross validationをした。簡単なルールに従うだけでscikit-learn準拠に出来る。もちろんscikit-learnに元々入ってる学習器に対してもgrid searchやcross validationできる。超便利。

Collective Prediction of Multiple Types of Links in Heterogeneous Information Networks (ICDM'14) を読んだ

ICDM14が始まったので興味ありそうな論文をいくつか読んでみようと思う。

概要

色んな種類のノード、エッジがあるネットワーク（Heterogeneous networks）においてリンク予測をする。

論文中で例に挙げられてたネットワークのスキーマ（論文中Fig.2を引用）はこんな感じで、遺伝子とか病気とかの関係が複雑に表されてる。 例えばこのネットワークにおいてGeneからDiseaseへのリンクを予測するとかいうタスク。

貢献

• Heterogeneous networkにおけるノード間の類似度（RM）を提案
• Co-trainingをベースとしたリンク予測手法（HCLP）を提案

手法

ノーテーションが複雑すぎて詳細を理解するのが相当面倒くさいんだけど、概念的にはすごく単純なので概念だけ説明する。

Metapath

あるノードタイプからあるノードタイプへのパスの種類。例えば上の図を使って説明すると "Gene -> Tissue -> Gene" というパスは、始点のGeneと終点のGeneが同じTissueを共有するという意味になる。また、 "Gene -> Disease -> Gene" というパスは始点のGeneと終点のGeneが同じ病気の原因となるという意味になる。これを使うと、同じTissueを共有している遺伝子同士は類似している可能性大だし、さらに同じ病気の原因にもなっている遺伝子同士はもっと類似しているよねということが言える。つまり何が言いたいかというと遺伝子同士（だけでなく同じタイプのノード）のいろんな種類の関係を使ってノード間の類似度を計算したいねということ。

Relatedness Measure (RM)

あるGene AとあるDesease B間のリンクを予測したいとする。この時、いろいろなMetapathを使ってAと類似するGeneの集合SAと、Bと類似するDeseaseの集合SBを見つける。そんでSAのノードからSBのノードへどれくらいの割合でリンクが張られているかを計算する。それがAとBの類似度となる。すごくシンプル。

論文中ではこういうふうに書いてある

PRINCIPLE 1. (Linkage Homophily Principle) Two nodes are more likely to be directly linked if most of their respective similar nodes are linked.

Iterative Framework

あとはもうほぼCo-Trainingやって終わり。簡単。

1. 全てのノードペアについて上記のRMを計算し、それを使ってリンク予測をするSVMを作る
2. 作ったSVMを使って、予測の対象とするノードペアの集合に対してそれぞれリンクがあるかどうか予測する
3. SVMによる出力値が閾値以上（つまり確信度の高い）のノードペアにはリンクが有ると見なして再度SVMを作る
4. 2-3を決められた回数だけ繰り返す
5. 最終的に出来たSVMによって予測の対象とするノードペアの集合に対してそれぞれリンクがあるかどうか予測、出力

手法のパラメータ多すぎ。

実験

• 上の図に示した遺伝子やら何やらのデータセット（SLAP*1）を使ったよ
• 提案した類似度（RM）と他の単純な類似度を比較したよ
• 提案したリンク予測手法を（HCLP）と、Co-trainingのようにIterationを回さない1-stepの手法を比較したよ
• もちろん提案手法が勝ったよ

感想

出たなMetapath！という感じしかしない。このグループの論文はMetapathを使ったいろんな手法を提案しまくってるけどどうもいいイメージがない。アイデアは面白いと思うけど、よく使われてるアルゴリズムとの比較はないし、ノーテーションが複雑すぎて理解するのが面倒くさい。で、何が新しかったんだろうとかんがえると結局Metapathを使ってるだけじゃんとなる（個人の感想です）。

パラメータ多すぎてどう使えばいいのかわからないし、いろんな要因が重なり合っててどこが効いていい結果が出てるのか分からない。最近良く思うことだけど、こういうアドホックな手法（ぱっと見新しくてすごそう）提案しっぱなしの論文は読者に何も知見を与えないと思う。もっとインクリメンタルでいいから一つ一つ検証していきましょうよ。

*1:B. Chen et al., Assesing drug target association using semantic linked data. PLOS Computational Biology, 8, 2012.

グラフのエッジリストから次数分布等をプロットするスクリプト書いた

グラフのデータを手に入れたらまずは次数分布をプロットするのが定石だけど、なぜか毎回毎回実装しなおしててアホだったから反省してちゃんと書いた。

次数分布とそのCDF、CCDFをプロットする。

要Numpy, Scipy, Matplotlib, Networkx。

使い方

言わずと知れたEnron email networkで試してみる。

まずデータをSNAPから取ってくる。

余談だけどSNAPにはいろんなネットワークデータがあって、これ眺めてるだけで楽しくなってくるね。

$ wget http://snap.stanford.edu/data/email-Enron.txt.gz
$ gunzip email-Enron.txt.gz

最初の4行は余計なものが入ってるので消す（tailで+5と指定すると5行目から最後までを出力してくれる便利機能があったなんて知らなかった）。

$ head -n4 email-Enron.txt
# Directed graph (each unordered pair of nodes is saved once): Email-Enron.txt
# Enron email network (edge indicated that email was exchanged, undirected edges)
# Nodes: 36692 Edges: 367662
# FromNodeId    ToNodeId
$ tail -n +5 email-Enron.txt > enron
$ head -n5 enron
0   1
1   0
1   2
1   3
1   4

各行にはエッジで繋がれてるノードのペアがタブ区切り（スペースでもOK）で記述されている必要がある。左がsource、右がdestination。

あとはedgelistのファイルを指定して実行するだけ。

$ python basic_plot.py enron

結果としてenron_{in|out}degree_{distribution|cdf|ccdf}.epsの6個のプロットが出力される。

ちなみにEnronのネットワークは無向グラフなのでindegreeもoutdegreeも同じになる。

enron_indegree_distribution.eps

enron_indegree_cdf.eps

enron_indegree_ccdf.eps

実装

Networkxでedgelistを読み込んでscipy.sparseに変換してから次数分布を計算してるけどこれが良いのか悪いのか分からない。多分悪い。

半教師あり学習のモデル仮定

Machine Learning Advent Calendar 2014の12日目。

最近半教師あり学習に興味があってちょっと勉強してみたのでそれについて書いてみる。自分が勉強した時に読んだ文献も下の方に書いたのでもし興味があれば。

半教師あり学習はラベル付きデータに加えてラベル無しデータも使って学習できるということですごく魅力的なんだけど、何も考えずに使うと教師あり学習より精度が落ちることがよくある。

ラベル無しデータはその名の通りどのクラスに属すかが分かっていないデータなので、何かしらの モデル に基いてそのデータがどのクラスに属するかを仮定してやらないといけない。つまりデータの分布（モデル）に仮定を置かないといけない。半教師あり学習をする上ではこれが 一番重要。

Introduction to Semi-Supervised Learningのp.15にもこう書いてある。

the model assumption plays an important role in semi-supervised learning.

というわけでここではいろいろな半教師あり学習手法についてその手法が仮定しているモデルについてまとめる。

Self-training

概要

ある分類器fを使ってラベル付きデータのみで学習し、ラベルなしデータの分類をする。その後分類したラベルなしデータのうち高い 確信度 で分類できたもののいくつかをラベルありデータとみなして再度学習する。これの繰り返し。Self-trainingはwrapper methodなのでどんな分類器でも使える。

Unsupervised word sense disambiguation rivaling supervised methods, ACL 1995

モデル仮定

自分が（高い確信度で）分類したデータの分類結果は正しいこと。これは異なるクラスに属すデータがwell-separatedであることを意味する。

Mixture Models (semi-supervised GMM)

概要

EMで推定する時のデータの寄与率（どのクラスに属すか）を、ラベル付きデータについてはそのデータが属すクラスでのみ値1を取るように固定し、ラベル無しデータについては通常のGMMの時と同様に計算する。GMMを例に出したけど混合多項分布を使ったテキスト分類の論文が有名っぽい。

Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning 2000

モデル仮定

トートロジーのように聞こえるかもしれないけど、 仮定したモデルが正しいこと。　例えば実際のデータは混合正規分布に従ってないのにsemi-supervised GMMで解こうとしてもうまくいかない。

Co-training

概要

データが二つの素性に分解できるとする（例えばwebページの分類をするときは画像と文章とか）。それぞれの素性について分類器を個別に用意し、ラベル付きデータのみでそれぞれ学習する。分類器１で高い確信度で分類できたラベルなしデータを分類器２での次回の学習に用い、逆に分類器２で高い確信度で分類できたラベルなしデータを分類器１での次回の学習に用いる。これを繰り返す。Self-trainingに似てるけど分類器を二つ使うところがポイント。これもWrapper method。

Combining labeled and unlabeled data with co-training, COLT 1998

モデル仮定

1. 個々の分類器だけでも 良い 分類が出来ること
2. 分解された二つの素性はラベルが与えられた上で 条件付き独立 であること

2が成り立たないと、どちらの分類器も同じような結果を出すから意味が無い。

Graph-based SSL (Label propagation)

概要

Label propagationはGraph-based SSLの一つ。ラベルありラベルなしに関係なく、データ間の類似度に基いてグラフを構築する。ノードはデータで（重み付き）エッジはデータ間の類似度。類似度の計算にはガウシアンカーネルを用いることが多い。構築したグラフ上でラベルありデータからラベルなしデータへ ラベルを伝搬 させ、ラベルなしデータのラベルを推定する。ラベルなしデータの近くにラベル１のラベルありデータが多く有れば、ラベル１に分類されるイメージ。ちなみにこれは元々グラフで表されるようなデータ（ソーシャルネットワークとか）に対してもよく用いられる。

Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions, ICML 2003

モデル仮定

（大きい重みで） 接続している２ノードは同じラベルを持つこと。 ラベルが違うデータでも類似度が大きくなることがよくあるような場合はうまくいかない。

S3VM

概要

Semi-supervised support vector machineのこと。通常のSVMはラベルありデータのみを見て決定境界を決めるが、S3VMではラベルなしデータも考慮して、出来るだけ決定境界がラベルなしデータの上を通らないようにする。実際に例を見てみるとわかりやすいかな。ちなみに通常のSVMと違ってコスト関数が凸にならないから扱いづらい。

Statistical Learning Theory (本)

モデル仮定

異なるクラスに属すデータがwell-separatedであること。言い換えると、特徴空間において決定境界付近には（ラベルなし）データが少ないこと。

良い文献

多分自分はこの順で読んだはず。もともとある程度半教師あり学習についての知識はあったけど。

半教師あり学習とは結局のところ何なのか? - Seeking for my unique color. 半教師あり学習 - SlideShare

半教師あり学習に関する簡単な俯瞰。良い。多分下の方に挙げる本を読めばこの記事に書いてあることは全て書いてあるんだけど、まずは日本語で俯瞰したい人におすすめ。

satomacoto: Pythonでラベル伝搬法を試してみる

Label spreadingっていうGraph-based SSLについての簡単な説明とその実装が書いてある。実装がすごい簡単でいいね。

グラフを用いたハーモニック関数による半教師あり学習

Label propagationについて詳細に説明してる記事。簡単な例を使って説明してるのでわかりやすい。最適化問題としての定式化とかについても書いてある。

ビッグデータ時代のサンタ狩り - ML Advent Calendar 2013 最終日

@sleepy_yoshiさんによる去年のML Advent Calendarのおおとり。Semi-supervised GMM（と近年問題になっているサンタ狩り）について書いてある。全てラベルなしの場合、全てラベルありの場合、どっちもある場合（半教師あり）について分けて比較してる。めちゃくちゃ詳細に説明してあるしすごくわかりやすい。超おすすめ。

Node Classification in Social Networks

グラフ上のノード分類という問題からいろいろなGraph-based SSLについて触れてる。それぞれの簡単な違いとかランダムウォークとしての解釈とか最適化問題としての解釈とか書かれてて良い。

Introduction to Semi-Supervised Learning (Synthesis Lectures on Artificial Intelligence and Machine Learning)

SSLの入門書。この記事にまとめたことは全てこの本に書いてある。Label propagationを提案した人が書いた本。参考文献リストとAppendixを除けば100ページもないし読みやすいのですぐ読める。全体を俯瞰したい人には超おすすめ。

Semi-Supervised Learning (Adaptive Computation and Machine Learning series)

厚い本だけどこれもSSLの入門書。Introduction to SSLよりもっと詳しく色々書いてある。いろんな文献から引用されてるからこっちのほうが定番なのかな。読んでる途中なので全体としておすすめできるかはわからない。