唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

論文感想: "Personalized PageRank vectors for tag recommendations: inside FolkRank" (RecSys 2011)

概要

ユーザーとアイテムとタグのデータが与えられた時に、ユーザーとアイテムに対するタグの推薦を行う方法としてFolkRankというアルゴリズムがよく使われている(らしい)。
このアルゴリズムを近似的に計算して、計算量を削減して高速に処理できるようにしている。

方法

PageRank

FolkRankは基本的に(Personalized) PageRankアルゴリズムを元にしている。
簡単に説明するとPageRankはグラフ構造上のどのノードが重要かということを推定してくれる

この論文ではグラフの形を変えるのと、preference vector (damping factor) というどのノードが重要かという事前知識を与えるベクトルを変えることによって、アルゴリズムを変更している

FolkRank

ユーザーとタグ、アイテムの三部グラフについてPageRankアルゴリズムを適用する。
ただしpreference vectorでは推薦対象のユーザーとアイテムのみ大きな重みを与える。

重み付けしたpreference vectorを用いて計算したPageRankから、均等な重みを与えたときのPageRank引き算したものがFolkRankとなる

FolkRank as Personalized PageRank Vectors

FolkRankのアルゴリズムを式変形すると、実は重み付けしたpreference vectorから、均等な重みを与えたpreference vectorを引いたものを新たなpreference vectorとしたときのPageRankの式と同じになることがわかる。
このことから、別々に計算した後に引かなくても一回の計算で済むようになる。

また線形性から、事前にユーザーやアイテムのどれか一つだけを0以外にして他を全部ゼロにしたpreference vectorでFolkRankを計算しておけば、それらの結果の線形結合としてユーザーとアイテムの組み合わせに対するFolkRankが得られる。

FolkRank of a Bipartite Graph

ユーザーを除いたタグとアイテムの二部グラフから計算することで高速化を行う。
グラフからユーザーを除いた代わりにユーザーとタグの関係の情報をpreference vectorに入れる

Tag-Centric FolkRank

タグのグラフだけを使って、ユーザーとアイテムとタグの関係の情報はpreference vectorに入れる

結果

近似によって結果はほとんど悪くならないどころか、場合によっては近似のほうが評価尺度が高くてびっくり(?)
実験では近似をすることで最大10倍ぐらい速くなっている

感想

三部グラフを使っていたのを二部グラフにしたりとか、こんなざっくりとした近似でうまくいくんですね

論文紹介で聞いて面白そうだなと思ったので記事にしました。
あまり読み込んではいないので、間違いなどがあったらすいません。