Kikker の学習の仕組みと Rocchio アルゴリズム

先日のソーシャルブックマーク研究会では id:kanbayashi さんによる発表がありました。id:kanbayashi さんは Kikker や はてブまわりのひと などの開発をされている方です。最近情報検索理論に入門した自分にとっては、非常に面白い発表でした。

発表の中で Kikker の学習の仕組みについての解説もありました。Kikker は Cosine similarity で推薦するドキュメントを検索しているそうですが、ユーザーのクリックデータを使って、ユーザーごとに推薦対象を最適化するようにしているそうです。この学習は、ユーザーが見たページのベクトルを、そのユーザーの趣向ベクトルに足し込むことで実現している、とのことでした。

発表ではベクトルを加算することについて「たぶんこれでうまくいく」とのことでしたが、先日 IIR の9章の復習をしていて、これは Rocchio アルゴリズムそのものなのだな、ということに気づきました。

Rocchio アルゴリズムは、検索結果の適合度を改善するための適合性フィードバック (Relevance feedback) を実現する古典的なアルゴリズムです。ユーザーからポジティブもしくはネガティブなフィードバックを受け取って、そのフィードバックから検索クエリを改善します。

例えばユーザーが、ある検索クエリ q に対する検索結果ドキュメント群のうちドキュメント d1 とドキュメント d3 は relevant であると判断したら、それをシステムに入力させます。d1, d3 は、relevant なドキュメントの集合全体 Cr から見ると、部分集合になっています。これを Dr とします。ベクトル空間上では位置ベクトルで Dr の重心ベクトルが求められます。検索クエリのベクトル q を Dr の重心に近づけると、(Dr の周辺は relevant なドキュメントが固まっているという前提が成立するなら) より relevant な集合に類似したベクトルへと最適化されます。

\Large\vec{q_{m}} \quad = \quad {\alpha}\vec{q_{0}} \qquad + \qquad {\beta}\quad\frac{1}{|D_{r}|} \sum_{\vec{d_{j}}\in D_{r}}\vec{d_{j}} \qquad - \qquad {\gamma}\quad\frac{1}{|D_{nr}|}\sum_{\vec{d_{j}}\in D_{nr}}\vec{d_{j}}

上記が Rocchio アルゴリズムの式です。qm が最適化されたベクトル、q0 が最初のクエリ、右辺の二項目が relevant なドキュメント部分集合 Dr の重心ベクトル、三項目が non-relevant な集合 Dnr の重心ベクトルです。重心ベクトルを加算することでクエリの位置ベクトルは relevant なクラスタへ近づき、除算減算することで non-relevant なクラスタから遠ざかります。

α、β、γ は重み付けの係数です。フィードバックとして返却されるドキュメントが多いならβ、γの値を大きくするとより強くフィードバックがかかります。

Kikker ではクリックがあったドキュメントを relevant だと学習するようです。これはポジティブフィードバックのみで、ネガティブフィードバックがないことを意味します。従ってこの場合 γ = 0 の場合に等しく、Dnr の重心ベクトルは利用していないことになります。IIR#9 ではポジティブフィードバックはネガティブフィードバックより役に立つので重みを強く付けるよう推薦されていますし、ネガティブフィードバックを必要としないシステムは γ = 0 であると解説があります。

クリックがあったドキュメントのベクトルを趣向ベクトル (クエリベクトル) に足し込んでるとのことなので、これは Rocchio アルゴリズムでクエリベクトルを重心に近づけていることにほぼ等しいのだと思いました。(足し込んだベクトル数で正規化すると、より精度が上がる、ということになるでしょうか。) ベクトルの加算で学習がうまくいっているのにはこのような裏付けがあると言えそうです。