Connecting the Dots Between News Articles(KDD 2010) 読んだメモ

Connecting the dots between news articles
KDD2010のBest Research Paper: innovative contribution。タイトルはきっとjobsのスピーチが元ネタ。

概要

ニュースを2つ(s、t)与えるとその2つのニュースの間にあり、かつ、論理的に一貫したニュース記事群"chain"を提示する。
具体的には、Dispatches From a Day of Terror and Shock - The New York Times(9.11の記事)とThe Tragic Story of Daniel Pearl - The New York Times(誘拐されたジャーナリストの記事)という二つの記事を与えるとこのシステムは次のような一連の記事を提示する。
(start)

Dispatches From a Day of Terror and Shockz
Two Networks Get No Reply To Questions For bin Laden (Coverage of September 11th)
Opponents of the War Are Scarce on Television (Coverage of the war in Iraq and Afghanistan)
‘Afghan Arabs’ Said to Lead Taliban’s Fight
Pakistan Ended Aid to Taliban Only Hesitantly
Pakistan Officials Arrest a Key Suspect in Pearl Kidnapping (Pearl abducted in Paksitan while investigating links to terror)
The Tragic Story of Daniel Pearl

(end)

特徴

良いストーリーの特徴、及び一貫性"coherence"を定式化
リンク構造を使わずに"influence"を定式化(完全に使ってないとは言えないと思うが)
chain coherenceを最大化しつつ(理論的な保証もしつつ)、2つの固定した点(すなわちクエリとしてのニュース)を繋ぐ効果的な方法を提示
ユーザーのフィードバックをモデルに組み込む事が可能(web系のこういう論文だと必ずモデルのpersonalizingに触れている印象がある)
実データでユーザに試してもらって有用性を確認

論文の方針

線形計画問題の形で解く事により、大域的な最適解を目指す。
そんな面倒なことをせず、記事をノードとするグラフを構築し、sからtまでの最短経路を計算すればいいじゃないかと思われるが、これでは良いchainにならない(Figure 1 left)。何故ならば、この方法で得られたchainは隣り合う2つの記事は確かに類似しているが、全体的な話題の一貫性が得られない。まるで連想ゲームのように一部が類似するものを並べてるようなものになってしまう。
なので局所最適解に陥らないようにしていく。

story coherence

まずはchain $(d_1,\cdots,d_n)$ が与えられたものとして、そのstory coherence(以降coherence)を測る方法を考える。
単純に考えると次のようなもの（隣接する記事において共起している単語数）が浮かぶ。
$Coherence(d_1, \cdots, d_n) = \sum_{i=1}^{n-1}\sum_{w} 1(w\in d_i \cap d_{i+1})$
しかしこれだと一部のリンクが強くなりすぎてしまい、coherenceが高いとは考えられなくなってしまう。
次に遷移における関連性が一番小さいものをCoherenceにしてみる。
$Coherence(d_1, \cdots, d_n) = \min_{i=1,\cdots,n-1} \sum_{w} 1(w\in d_i \cap d_{i+1})$
これでもいくつか問題がある。

Missing words : 記事に現れていないが現れるべき重要な単語を考慮できない
Importance : 単語の重要性が考慮されていない

これら2つの問題点からcoherenceを次のように定式化してみる。Influenceはあとで定義する。
$Coherence(d_1, \cdots, d_n) = \min_{i=1,\cdots,n-1} \sum_{w} Influence(d_i, d_i+1|w)$
しかしまだ問題点がある。

Jitteriness : ↑のCoherenceではtopicが現れたり消えたりする。これでは話題がいったりきたりして一貫性に欠ける

ので目的関数を次の形にする。activeも後で定義する。
$Coherence(d_1, \cdots, d_n) = \max_{activations}\min_{i=1,\cdots,n-1} \sum_{w} Influence(d_i, d_i+1|w)1(w\,active\,in\,d_i,d_{i+1})$
で、influenceはnon-negativeなので(これは後半に定義される)全部activeの状態だと目的関数がmaxになってしまう。しかしこれじゃ何の意味もないので全active wordと1遷移におけるactive wordの数に制約を置く。
であとはこれらを線形計画問題の形にする(2.2.1)。式は大体書いてある通りだが正直 $\forall w \sum_{i} word-init_{w, i} \leq 1$ の意味が分からなかった。word-initはword-activeの変化分であるという理解だが何故これが"initialized at most once"の制約に繋がるのか。word-activeがi=1..4で0.1ずつ増加したら"initialized"がここまで書いてわかった。word-initはinitializeの度合いだから総和で1を超えなければ問題無いのか。initializeの回数だと勘違いしていた。

Measuring influence without links

$influence(d_i, d_j|w)$ を計算する。"depite the fact that this notion is based on ramdom walks, it requires no edges."と書いてある理由がよくわからない。
ドキュメントと単語で有向2部グラフEを作る。エッジの重みはTF-IDFを用いる。その後それぞれのノードから遷移確率になるように、ドキュメント側で正規化したのちに単語側で正規化する(ここで重みが非対称になる)。その後
$\prod^{i}(v)=\epsilon(v=d_i) + (1-\epsilon)\sum_{(u,v)\in E}\prod^{i}(u)P(u|v)$
の式に従い2部グラフ上のランダムウォークを繰り返して定常確率を求める。
しかし求めたいのは $influence(d_i, d_j|w)$ である。なので今度はwから出て行くエッジを除いたグラフ $E_{\notin w}$ を作ってそこでランダムウォークをする。もしこの時wが強い影響力を持っているなら、その時の定常確率 $\prod_{w}^{i}(v)$ は元の定常確率 $\prod^{i}(v)$ から著しく低下する筈である。
よって $influence(d_i,d_j|w) = \prod^{i}(d_j) - \prod_{w}^{i}(d_j)$ をinfluenceとする。

Finding a good chain

ここまではchainが得られたものとして、それの評価関数を考えていた。次はchainそのものをどのようにして得るかという話になる。
これも局所最適解を避けるために線形計画問題として解く。具体的には2.2.1の線形計画問題にノードの遷移と時間制約を表す式を追加する。この流れが自然で良かった。

Rounding、Scaling up

Roundingはなんか証明が入ってる。正直何言ってるか分からなかった。
Scaling upは計算量削減のために行った工夫。そもそもLP解くにはO(|D|^2 W)必要らしい（理由知らない）、がこんなの実システムでは運用できない。

Selecting an initial set of documents : chainの候補にする記事、及び用いる単語を全てではなくsubsetを取る。選び方は2部グラフのランダムウォーク。これで微妙だったらsubsetを増やす。
Speeding up influence calculation : influenceを求めるランダムウォークは繰り返し数を定数cとしてもO(c|D||W|)=O(|D||W|)かかる。これは全記事に対する計算を全単語を一つずつ取り除きながらやるのでこの値になる。これを削減する。やり方はまず単語を取り除かないランダムウォークを行う。その時、どの単語からどの記事に何度遷移したかを数え上げておく。そしてinfluence(d_i, d_j|w)を計算するときの\prod_{w}^{i}(d_j)をランダムウォークを使わず、「wを経由せずにd_jに到達した回数」とする。当然これでは真の値ではないが、どうせ期待値が欲しかったのでこれでも構わないらしい。

evaluation

実験。データは1995年から2003年にかけてのニューヨーク・タイムズとロイター。比較対象はconnecting dots、shortest-path(コサイン類似度で記事間にエッジ貼って最短経路)、google news timeline、Event threading。二重盲検で提示しつつ被験者に色々アンケート取る。

interaction model

ユーザのフィードバックを取り入れる。

incorporate user interests : ユーザがchainの途中で記事における別のトピックに興味を持ったら、別の記事を提示する。目的関数を次の形に変化させる。

$\sum_{w} \pi_{w} Influence(d_i, d_i+1|w)1(w\,active\,in\,d_i,d_{i+1})$
$\pi$ は1に初期化しておき、ユーザが単語wに興味を持ったら重みを増やし、興味を持たなかったら重みを減らす。例えば推薦した記事の単語クリックなんかでフィードバックできると嬉しい。その時は似たような単語をクリックしまくらせるのは面倒なので共起などを使って適当に似た単語の重みも増やすようにする。

感想

面倒になって局所最適解で収めようとするのを大域的最適解に持っていくというのが面白いと思う。動いてるところが見たい。
著者らも言っているように「点と点を繋ぐ」というのは情報の整理だけではなく、そこから新たな発見を生み出す可能性のある行為であると思う。この研究の続きが読みたい。

糞糞糞ネット弁慶

読んだ論文についてメモを書きます．趣味の話は http://repose.hatenablog.com