[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 を重く評価する.