概要
ユーザーとアイテムとタグのデータが与えられた時に、ユーザーとアイテムに対するタグの推薦を行う方法として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倍ぐらい速くなっている
感想
三部グラフを使っていたのを二部グラフにしたりとか、こんなざっくりとした近似でうまくいくんですね
論文紹介で聞いて面白そうだなと思ったので記事にしました。
あまり読み込んではいないので、間違いなどがあったらすいません。