Joint Inference of Multiple Label Types in Large Network (ICML'14) を読んだ

ICML14から。数式とか書くのはめんどくさいからアイデアを中心に書く。

概要

ネットワーク上の ノード分類 の話で、各ノードは 複数のラベルタイプを持っている という設定。例えば論文中で使われている例だと、Facebookユーザの出身地、現住所、高校、大学、雇い主の５つのラベルタイプを同時に推定する。

アイデア

提案手法は接続されているノードペアの 多くが出来るだけラベルを共有する ようにノードのラベルを決定する。このやり方がうまくいくことを説明するために既存手法（ラベル伝搬法）がうまくいかない例を挙げる。下の図（論文中Fig. 1）に対してラベル伝搬法を適用すると、u のhometownとcurrent cityはそれぞれ多数決により H と C' と推定される。でもこれだと右の方にいる赤いやつらと u がどのタイプのラベルも共有しないため、 なぜ友達なのかが説明されない という状況になる。普通に考えればある人とある人が友達になるにはなにか理由があるはず。つまり なにかしらのラベルを共有するはず。

ラベル伝搬法と違って提案手法は なぜノードが接続されているか を最大限説明しようとするため、u のcurrent cityの推定結果を C' ではなく C であるとする。こうすることによって、左側のノード達はhometownラベルを共有してるから u と友達で、右側のノード達はcurrent cityラベルを共有してるから u と友達だという説明ができる。著者らはこうすることによってノード分類の精度が上がると考え、実際に精度が上がった。

貢献

• ノード分類（ラベル推定）問題を、ノード間にエッジが張られている理由を説明する 問題に変換した。理由を説明するというのは、接続されているノードペアが共有しているラベルを見つけること。
• スケーラブル（分散可）、高精度のノード分類手法を提案。
• 10億ノードくらいのFacebookグラフを使った実験をし、ラベル伝搬法より精度が高いことを示した。

手法

（数式書くのはめんどくさいので概要だけ書いておく）

一言で言えば、ラベルを共有する接続されたノードペアの数を最大にするように、ノードのラベルを決める。

そういうノードペアの数が多いほど大きくなる目的関数を設計し、それを最大化する。目的関数は凸じゃないから最適化がめんどくさいんだけど、ノードごとに見てやると凸になってるので、ノードごとに目的関数を最大化し、その結果を使って別のノードについて最大化するってのをメッセージパッシング的に繰り返す。

実験

ラベル伝搬法と比較。Facebookのデータを使う（著者らはFacebookの人、ずるい！）。大体勝った（そんなに圧勝はしてない）。

感想

ICMLだけど数式こてこてしてないゆるふわな感じの論文だった。アイデアは面白いし手法もシンプルでよかったんだけど実験ではあんまり良い結果にはなってないように見えた。ICMLとかのガチ機械学習系の論文はあまり読むことはないんだけど、問題定義とかすごくシンプルにかかれてて良い。逆にデータマイニング系はまぁしょうがないとは思うんだけど背景から何からイントロでいろいろ説明しようとするからもうイントロ読むだけでお腹いっぱいになる。

Label propagationとLabel spreading

グラフベース半教師あり学習 (SSL) のLabel propagation (LP) とLabel spreading (LS) の違いを説明している文献があまりなかったのでそれについてちょっと書いてみる。SSL自体とかLP、LSについては以下の記事にまとめた文献がいい感じなのでそちらを参照。

半教師あり学習のモデル仮定 - でかいチーズをベーグルする

LPの元論文はこれ (PDF)

"Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions", ICML2003

LSの元論文はこれ (PDF)

"Learning with Local and Global Consistency", NIPS2003

まとめ

• LPとLSの超概要、ランダムウォークとしての解釈、最適化問題としての解釈を書いた
• 軽い実験をした
  • 基本的にLSの方がLPより高精度っぽい
  • ラベル密度が小さい時は精度の差が開くっぽい
  • ラベルにノイズが有る時は精度の差が開くっぽい

Label propagation

超概要

データをノード、データ間の類似度をエッジとしてグラフを構築し、そのグラフ上でラベル付きノードからラベル無しノードへラベルを「伝播」させる。近くにラベル１が多いノードはラベル１に、近くにラベル２が多いノードはラベル２に分類される感じ。解としてはラベルなしノードiのラベルがkである確率が全てのiとkについて得られる（つまり行列が得られる）。ちなみにパラメータはない*1。

ランダムウォークとしての解釈

データiのラベルを知りたいとき、グラフ上でデータiに対応するノードからランダムウォークをスタートする。このとき、ランダムウォークが初めにラベルがkであるラベル付きデータ（ノード）に到達する確率は、LPによって得られる解と等しい。

最適化問題としての解釈

1. ラベル付きデータのラベルは変化しないという制約のもと、
2. グラフ上で隣接しているノードは同じラベルを持ちやすい

というコスト関数を最小化するを求める。これがLPの解と等しい。

Label spreading

超概要

LPと同様にデータ間の類似度からグラフを構築し、ラベル付きノードからラベル無しノードへとラベルを伝播させる。LPとの違いはラベル付きノードのラベルも同時に再推定する点。つまり、LSはラベル付きデータ i のラベルが変化することを許す。例えば、ラベルが k であるラベル付きデータ i がたくさんのラベル k' データと類似していれば、i のラベルは k ではなく実は k' である確率が高いと出力する。これがLSのキモ。

パラメータはの一つで、どれだけ元のラベルを重視するかを表す。が大きいほどラベル付きデータのラベルは変わりやすくなる。パラメータのチューニングが必要という点ではLSの方が使いづらいのかな。ちなみに元論文ではと決め打ちされていた。

ランダムウォークとしての解釈

LPと同様に、データ i のラベルを知りたいとき、グラフ上でデータ i に対応するノードからランダムウォークをスタートする。ただし確率で隣接ノードのどれかに移動するが、確率でデータ i に対応するノードに戻る。これを無限ステップ繰り返した時、ウォークがラベル k のラベル付きノードにいる確率はLSの出力に等しい。

最適化問題としての解釈

1. ラベル付きデータは元々の自分のラベルからは変わりづらく、
2. グラフ上で隣接しているノードは同じラベルを持ちやすい

というコスト関数を最小化するを求める。これがLSの解と等しい。パラメータは(1)と(2)の重みとして働く。LPではラベル付きノードがもともとの自分のラベルから変わらないような 制約 を入れていたが、LSでは制約にはなっていない。

実験

LPとLSはどっちを使ったらいいんだ、どう使い分けたらいいんだ、さっぱり分からん！ということで軽く実験をしてみた。scikit-learnに入ってるLPとLSの実装とDigitsデータを使った。LPとLSの他にふつーのSVMも比較した。

実験設定

Digitsデータを分類した。入力は画像データそのもので、ラベルはその画像がどの数字か(0から9)。1000サンプルのうちからランダムで一定の割合のノードのラベルを隠して分類を30回繰り返した。LP、LS、SVMのカーネルはRBFカーネルを使った。パラメータ（バンド幅、SVMのC）はグリッドサーチで決定。LSのは元論文と同様に0.99に決め打ちした。

1. ラベル密度を変えた実験：全体のデータ数に対するラベル付きデータの割合を1%から50%まで変化させてどう精度が変わるかを見た。
2. ラベルにノイズを入れた実験：ラベル付きデータのラベルをランダムに変更してどう精度が変わるかを見た。ノイズを入れる割合は0%から50%、ラベル密度は5%にした。

コードはここに置いたので興味のある人だけどうぞ。

ラベル密度を変えた実験

結果

• 期待通りラベル密度を小さくしていくとLPとLS共にSVMに勝った。
• LPよりLSの方がちょっと精度が高い。
• ラベル密度を小さくしていくとLPとLSの精度の差が少しずつ開いていく。

横軸はラベル密度、縦軸は精度、エラーバーは標準偏差。

考察（注意：個人の感想です）

ラベル密度が小さい時にSVMに勝てるのはまぁ周知の事実。と言うかそれが半教師あり学習の強み。 面白いのはラベル密度を小さくしていくとLPとLSの精度の差が開いたところ。なんでか考えたんだけど、多分LSのランダムウォークとしての解釈のところでランダムウォークが確率で始点に戻るところが効いてるのかな。ラベル密度が小さいとランダムウォークがラベル付きノードに到達せずにどんどん始点から遠ざかってしまう事が多くなるけど、LSでは一定確率で始点に戻ることでそれがある程度防げるとか。

ラベルにノイズを入れた実験

結果

• ノイズを入れる割合を大きくしていくとLPとLSの差が顕著に開く。
• SVMは悲惨な結果だけどLPとLSは高い精度を維持。

横軸はノイズの割合、縦軸は精度、エラーバーは標準偏差。

考察（注意：個人の感想です）

予想通りの結果になった。LSはもともとラベルがついてるデータのラベルを変更することも許してるから、ノイズでラベルが変わってしまったノードのラベルも正しく修正出来たってことだと思う。一方でLPとSVMはノイズで変わってしまったラベルも"信じきって"学習した結果精度が落ちてしまったって感じかな？ちょっとわからなかったのが、LPの精度もそこまで下がらなかったところ。ラベル密度も小さいし(1000サンプル中50個しかない）、そのうちの半分のラベルがランダムに変更されているのにこれだけ精度高いとは。。。

おわりに

今回実験した限りだとLSを使っとけば問題ないという結果になった。まぁでも「どんな場合でもLSの方が優れている」なんてことは無いしLPを使ったほうがいい場面も多分あるんだろうな。分からんけど。ちなみに今回の実験の設定ではSVMが悲惨な結果でLPとLSが圧勝してたけど、これは今回はLPとLSのモデル仮定（類似してるデータは同じラベルを持つ）が正しかったからであって、どんな場合でも（ラベル密度が小さければ）半教師ありがSVMとかの教師あり学習に勝てるわけじゃない。

*1:類似度の計算にRBFカーネルを使う場合が多いので、その場合はバンド幅のパラメータが必要になる。

Semantic Stability in Social Tagging Streams (WWW'14) を読んだ

WWW14から。次のWWW15はイタリアフローレンス！参加したい！

概要

Social tagging systems（FlickrとかDeliciousとか）においてリソース（Flickrなら写真、DeliciousならWebページ）に付けられたタグがどのように "Stable" になっていくかを分析。

Social tagging systemsではいろんな人が何のルールもなしに好き勝手タグ付けをするので、結果として意味を成さないめちゃくちゃなタグ付けになってしまいそうだけど、（多くの人が経験上分かるように）そうはならない。時間を追ってどんどんタグ付けされていくわけだけど、一定時間経つとあるリソースに付けられたタグの "割合" は変化しなくなる。こういう状況を "Stable" であるという。

例えば、Deliciousでgoogle.comは多分"search engine"とかそういうタグを付けられてるんだけど、Stableな状態になるとその後みんながタグ付けを続けてもgoogle.comに付けられたタグの割合は変わらない。

この論文ではStableであるという状態を表す新しい指標を提案し、それを使って三つの異なるSocial tagging systemsの違いや、Stableになる原因について論じている。

貢献

1. Social tagging systemsがStableであるかどうかを示す指標を提案。既存の指標のいくつかの問題点を解決している。
2. 提案指標を使って三つのSocial tagging systems (Delicious, Librarything, Twitter lists) がStableであるかどうかを分析。
3. 三つのシステムの違いや、Social tagging systemsがStableになる原因について議論。

提案指標

直感的には、付けられたタグの割合が変化しなくなったリソースが多いほどそのSocial tagging systemはStableであると言える。

実際には提案指標では付けられたタグの割合じゃなくて、付けられたタグの順位（google.comに付けられたタグで一番多いのは"search engine"とかそういうランキング）が変化しなくなるかどうかを見る。

Rank Biased Overlap

これはこの論文の提案した指標じゃないけど、これを使ってる。

あるリソース1に付けられたタグの頻度によるランキングをとし、２つのランキングの類似度を以下で測る。

はランキングの1からd位までという意味。RBOは[0,1]の範囲の値を取り、0は２つのランキングが全く異なることを意味し、1は完全で同じであることを意味する。

はパラメータで、0にするとランキングの1位だけしか考慮されなくなり（互いの1位が同じならRBO=1、そうでないならRBO=0）、1に近づけるほど下位まで考慮することになる。

Rank-based Stability Method

同じリソースの時刻tでのランキングと時刻t+t'でのランキングについて上のRBOを計算する。で、その値が閾値kより大きいリソースの割合f(t,k)を計算する。それが大きいほどStableであると言える。これだけ。

この値はSocial tagging systemについて決まる値なので、それを各Social tagging systemについて計算して比較する。またランダムなタグ付けをシミュレートして、それについてもこの値を計算して比較する。

提案指標の特徴三つ

1. あるリソースに付けられたタグの割合そのもの（google.comに付けられた全てのタグの内"search engine"は割合0.7とか）を使うんじゃなくてランキングを使う。
2. いくつかの既存指標ではランダムなタグ付けもStableである事になってしまうが、この指標ではランダムなタグ付けはStableであると判定されない（後述）。
3. 既存指標はいままで出現したことのなかったタグを扱えなかったがこの指標は扱える。

結果

（論文中 Fig.7）

なんかすごい見づらい図なんだけど、縦軸がパラメータkで、横軸が時刻t。線の色が各Social tagging systemsに対応してて、各線はf(t,k)の値の等高線になってる。

まぁ図を読む必要も特に無いので結果だけまとめると、

• Social tagging systemsは三つともランダムなタグ付けよりもStableだった
• Twitterは他の２つのSocial tagging systemsよりfの値が小さかったんだけど、これはTwitterでリストを作る時に「このユーザにはこういうタグ（リスト名）をつけたほうがいいですよ」っていう推薦がないから（と思われる）
• この図から読み取れることではないけど、Stableになる原因としてはシステムからのタグの推薦と、ユーザ達が持ってるBackground knowledge（どういうタグを付けるべきか）が挙げられる。これはシミュレーションから得られた結果 (Fig. 8) で示している。

感想

サーベイが本気。論文中で何かを主張する時は大抵文献が参照されてるか実験結果があるかだった気がする。論文書く時はホントはそれくらいしないといけないね。すごい。結果はまぁ驚くもんでもなくて、直感に反しないんだけど。どこかで「当たり前の結果を出すことが大事」みたいなのを見たことがあるし最近そう思うので、この手の分析しました論文ではしっかりとした手順を踏んで直感的なことを "示す" ってのが重要なんだと思う。

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できる。超便利。