糞糞糞ネット弁慶

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

Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time (WebConf 2018) 読んだ

[1711.07601] Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time
Pinterest における推薦の論文.Jure Leskovec が last author に入っているのでとりあえず読む. WWW が WebConf に名前が変わったのが悲しい.

概要

超大規模なサービスである Pinterest においてリアルタイムな推薦を実現する Pixie について説明する.

手法

Pinterest ではユーザは Board の下にそれぞれの pin を保存する.実現したいのは直近のユーザの行動によって得られた pin と重みの集合であるクエリ Q に対して適した pin を推薦したい.
基本的な方針は pin と Board を二部グラフとみなしてそのグラフ上をランダムウォークする.

ランダムウォークの基礎

クエリ が 1 つだけで重みがない場合のランダムウォークについて考えてみると,二部グラフ上の かららスタートして 回二部グラフ上をランダムに渡り歩き,それぞれの pin を訪問回数 順に並び替えて返せばいい.
この手法を次に説明するように発展させていく.

ランダムウォークにバイアスをかける

まずはただランダムに遷移するのではなく,ユーザごとにバイアスをかけることを考える.隣接ノードを uniform に選ぶのではなく,ユーザごとの特徴量に従って遷移するノードを PersonalizedNeighbor(E, U) という関数で選ぶ.この関数についてはこれ以上の説明がないので詳細は不明.

複数のクエリと重みを扱う

クエリとして複数の pin とそれぞれの重みを扱う (重みはその pin に対してユーザがどういう行動をとったか,およびその行動が発生してからの経過時間にもとづいて決まるらしいが詳細な説明無し).
基本的には各クエリごとにランダムウォークを行い,クエリごとの pin の訪問回数 を保存する.
ここで重要なのは,各クエリにおいてランダムウォークの回数 を変えて とすることである.クエリの次数が大きければ大きいほどランダムウォークの回数は多くする.
と思ったらより効率的にするために early stopping を導入する.これは最低 個の pin に最低 回訪問したらランダムウォークを打ち切るというもの.これによって精度はそのままに計算時間が倍の速さになった.
(early stopping するなら重みの形はどうでもいいのだろう)

Multi-hit Booster

ただ足し合わせるのではなく, として複数のクエリから訪問されている pin を重く評価する.

グラフの枝刈り

グラフはそのままだと非常に大きいので枝刈りする.方針としては二つ.

雑多な Board を削除する

pin の説明文に対して LDA を適用して topic distribution を計算して topic vector とする.その後,それぞれの Board に直近で追加された複数の pin の topic vector の entropy を Board の entropy とし,これが大きい Board をグラフから削除する.

人気の pin を削除する

人気の pin を削除する.がただ削除するのではない.その pin の topic vector と Board の vector とのコサイン類似度を取って類似しているもののみ残す.

この枝刈りによってグラフの大きさを 1/6 にし,推薦の類似度を 58% 改善した.