2015-01-27

AAAI2015一日目＆二日目

conference

f:id:yamaguchiyuto:20150127153004j:plain

AAAI2015に参加中（TASAは何なのか知らない）。１，２日目はワークショップとチュートリアルと招待講演があった。例のごとくワークショップはパスしていくつかチュートリアルと招待講演を聞いて回った。

いろいろ聞いた感じだと、AIコミュニティはホントにいろんな分野の融合になっていて、扱う範囲が広すぎると思った。自分は元々AIの人間ではないので、知らない単語とか分野がかなり合って、いろいろ知れただけでも参加してよかったと思った。レセプションで話した人たちもみんな結構バラバラの分野から来てて面白かった。

以下参加したチュートリアルと招待講演のメモ。

The Future of (Artificial) Intelligence - Stuart Russell

最近シンギュラリティやばいとかニュースで話題になったりしてるから、しょうがないそれに対して答えてやろうという招待講演。

色々例を挙げて話してたけど、メディア（？）への答えとしてはこれ。

response
- it'll never happen
- too late to stop
  - そんなことは起こらないと言いながらのこれ
- can't control research
  - このセリフはカッコ良かった

あと、「お前ら勘違いしてるぜ」と言ってた。

misconception
- machines have IQs
  - 尺度はたくさんあるしなんでIQ?
  - general intelligenceはまだまだ先
- It's right around the corner
  - いや、breakthroughはunpredictableだから。
- armies on robots
  - ないない。

良いAIを作る提案。

Proposal: provably "beneficial" AI

それにはこれが重要。

Value alignment
- learn reward functions by other agents
- 人へのrewardを学習するAI
- values differ across individuals and contries

その他言ってたこと。

AI = making computers do the right thing
progress is accelerating
Once performance crosses the usability threshold, small improvements are worth billions

Constraint-Based Temporal Reasoning

時間の表し方と、そこからの推論についてのチュートリアル。

時間の表し方には

qualitative
quantitative

の２つがある。例えば、

「朝食中に新聞を読んで、朝食の後にオフィスに歩いて向かった」

というのはqualitativeで、

「朝６時に起きて、その後朝食中に３０分間新聞をよんで、朝食後にオフィスに向かった。８時にオフィスに着いた」

というのがquantitative。要するに、時間の表現の中に数値が出てくるかどうかの違い。qualitativeだと各事象の「前後関係」しか表せない。こういう 時間制約 をうまく表現する方法を考える。んで何らかの方法で表現したら、与えられた情報から推論することで、例えば以下の様なクエリに答える。

「オフィスについた時に新聞を呼んでいたか？」「朝食を食べ始めた時刻のupper boundは？」

時間の表現方法についてはたくさん紹介してたんだけど、基礎的なところとしてはpoint algebraとinterval algebraっていうのが有名らしい。Interval algebraについては聞いたことあったかも。Point algebraは「朝食を食べ始めた時刻」見たいなTime pointの前後関係を代数的に表現する方法で、Interval algebraは「朝食を食べていた時間」の前後関係を代数的に表現する方法。これらはqualitativeな表現方法だけど、前後関係に数値を入れることでquantitativeに拡張していた。

その後はこういう時間関係にpreferenceを入れるとどうなるか見たいな話。例えば、

「火星探査機に火星の写真を取って分析してもらいたいからそのスケジューリングをする。もちろん分析するのは写真を取ったあとなんだけど、出来るだけ写真を取るタイミングは遅くしたい。どの時刻に写真を取って、どの時刻に分析を開始して、終了すればいいか。」

という問題を扱う。「写真を撮るタイミングを遅くしたい」みたいなのがpreference。事象の前後関係の制約を満たしたまま、preferenceを最大化（？）するにはどうしたらいいかっていう話だったんだけど細かいところはついていけなかった。

こんな分野全然知らなかったからすごく面白かった。たぶんAIコミュニティでもあんまりメジャーな分野じゃなかったみたいで、ものすごい基礎的な話から始まったのですごくわかりやすかった。

Voting Rules for AI

何かを決めるときの投票方法についてのチュートリアル。

３部構成だった。

１部：「選挙みたいに、いくつかの候補の中からひとつ選ぶときにどうしたら良いか」
２部：「レストランのコースメニューみたいに、いくつかの要素が絡み合ってる場合どう選んだらいいか」
３部：「マッチングの話」

１部

いくつかの候補の中からひとつ選ぶやりかたにも色々あるけど、それぞれ違う性質を持ってる。一般的に、voting ruleは以下の三つの性質を持っていることが望まれる。

anonymous: 全ての投票者は等しく扱われなくてはならない。つまり、ある二人の投票者の投票を入れ替えても、同じ結果になる。
neutral: 全ての候補は等しく扱われなくてはならない。つまり、候補Aに入った全ての票をBに変えて、候補Bに入った全ての票をAに変えると、AとBの結果が入れ替わる（Aが当選してたならBが当選するし、逆もまたしかり）。
monotone: 候補Aが当選していた時、Aの票を更に増やすことでAが落選してはいけない。また同様に、A以外の票を減らすことでAが落選してはいけない。

一番良く使われるのはもちろん「多数決」なんだけど、候補者が二人の時はMay's theoremによって多数決は上の三つの性質を持つことが示されている。

当たり前だろうが！と思うかもしれないけど、候補が３個以上ある時はそうも行かない。Arrow's theoremによって、候補が三つ以上ある（かついくつかの条件を満たす）時は、上記の三つの性質を全て満たすvoting ruleは存在しないことが示されている。

２部

こういう問題を考える。

「５人が夕食のメニューを考えている。メインはバジルペストパスタかトマトパスタのどちらか、ワインは白か赤かのどちらかから選びたい。それぞれの投票者はそれぞれ別の嗜好を持っている。どうやって決めたらいいか。」

ここで複雑なのは、単に「白か赤なら白がいいな」というものではなく、「基本的には白が好きだけど、トマトパスタなら赤がいいな。でもバジルペストパスタならやっぱり白がいいかな。」というように、それぞれの項目に依存関係がある。

こういうふうに、選ぶ対象が複数あって、かつそれぞれに依存関係がある時にどうやって選ぶかという問題。依存関係を全部考慮してたら組み合わせが爆発するので、いかに効率的に評価するかっていう話がされてた。

３部

Stable machingの話。

Gale-shapleyアルゴリズムでは、どちら側からプロポーズするかによってman optimalになるかwoman optimalになるかが変わる。man optimalってのは男性側の嗜好の観点からは最適なマッチング担ってるけど、女性側の嗜好の観点からはそうはなっていないということ。

面白いのが、man optimalの時（男性側からプロポーズする時）には、女性側が自分らの嗜好（どの男性が好みか）において嘘を着くことでより良いけっかを得られる。つまり、女性は正直に好みの男性を言わないほうが、好みの男性と結婚できる確率が高いということ。

大体wikipediaに載ってる話だったかな。

Natural Language Processing in Watson

IBMWATSONのチュートリアル。

WATSONの仕組みからどういう応用をやっているかまで話してた。いままで何度か聞いてたけどまた聞きに来てしまった。

導入部では、既存の研究論文とか他人のコード（他のプロジェクトに使われていた）とかを自分のプロジェクトに適用するのはとても難しいから、IBMがやってるようなグランドチャレンジが重要なんだよと言ってた。

WATSONの仕組みについてはもう散々話されてるから他のソース（例えばこことか）に頼るとして、面白かった点を幾つか。

質問の型が大事

jeopardy!ではこういう問題文が出される。

「米国が外交関係を持たない世界の4カ国のうち、この国は最も北にある」

つまり、疑問文になってない。そのため、そもそも何が聞かれてるのかを知る必要がある。そこで、質問の型が重要になってくる。この場合の型は「国」で、問題文に整合する国を答えなくてはならない。

質問の型を導入した時とそうでない時で、精度が10%も変わったんだとか。

実際のアプローチとしては、単に型で限定してから答えを見つけ出すのではなく、いろんな候補解を列挙してから、型に合う答えにより大きなスコアを割り当てるというようにしてるらしい。これを"generate-and-type" principleと呼んでた。

Spatial and temporal reasoning

問題文には場所とか年代に関する記述が多く存在するため、それを手がかりにする必要がある。単純に「1980年」っていう記述が出てきたらそれでキーワードマッチすれば良いじゃんと思うかもしれないけど、「1980年で400周年となる○○」みたいな問題文を出されてしまうと、単純なキーワードマッチだとうまくいかない。○○に関する情報には「1980年」というキーワードはまず出てこないため。

2014-12-31

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

paper machine learning

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

概要

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

アイデア

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

f:id:yamaguchiyuto:20141231092712p:plain

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

貢献

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

手法

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

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

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

実験

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

感想

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

2014-12-28

Label propagationとLabel spreading

machine learning

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

<a href="http://yamaguchiyuto.hatenablog.com/entry/machine-learning-advent-calendar-2014">半教師あり学習のモデル仮定 - でかいチーズをベーグルする</a>

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

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である確率 $F_{ik}$ が全てのiとkについて得られる（つまり行列 $F$ が得られる）。ちなみにパラメータはない*1。

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

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

最適化問題としての解釈

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

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

Label spreading

超概要

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

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

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

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

最適化問題としての解釈

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

というコスト関数を最小化する $F$ を求める。これがLSの解と等しい。パラメータ $\alpha$ は(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の $\alpha$ は元論文と同様に0.99に決め打ちした。

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

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

ラベル密度を変えた実験

結果

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

f:id:yamaguchiyuto:20141202235147p:plain

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

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

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

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

結果

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

f:id:yamaguchiyuto:20141202235150p:plain

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

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

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

おわりに

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

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

2014-12-24

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

paper

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になる原因について論じている。

貢献

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

提案指標

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

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

Rank Biased Overlap

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

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

${ RBO(\sigma 1, \sigma 2, p) = (1-p) \sum_{d=1}^{\infty} \frac{\sigma 1_{1:d} \cap \sigma 2_{1:d}}{d} p^{d-1} }$

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

${0 \leq p \lt 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について計算して比較する。またランダムなタグ付けをシミュレートして、それについてもこの値を計算して比較する。

提案指標の特徴三つ

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

結果

（論文中 Fig.7）

f:id:yamaguchiyuto:20141224073615p:plain

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

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

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

感想

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

2014-12-21

Detecting Campaign Promoters on Twitter using Markov Random Fields (ICDM'14) を読んだ

paper

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）。

f:id:yamaguchiyuto:20141219074016p:plain

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に勝てるのはある意味当たり前なんだから提案手法のバリエーションともっと詳細に比較して欲しい。