Fast Item Ranking under Neural Network based Measures
読んだ理由
NNベースのユーザ-アイテム間のスコアによるランキングを高速に行えれば、リクエストベースの推薦精度向上やバッチによる推薦精度の向上に寄与できるかも
どんなもの?
ランキングを高速に行う
ランキングのパラダイムは大きく分けて2つ
representation learning
各アイテムについて単一のベクトル空間上の表現を学習し、それらを単純なマッチング関数(コサイン類似度、内積など)に入力してスコアを算出する
高速だが、アイテム同士の複雑な関係を考慮できず性能に限界がある
matching function learning
各アイテムのベクトル表現(異なる空間上でも良い)を受け取って、それらのマッチングスコアを返すマッチング関数を学習する
性能は良いが、すべてのアイテムとのマッチングスコアを計算するのにリソースを多く使い、遅い
先に小さな候補セットを抽出し、その中だけでマッチングスコアを計算する手法もあるが、必要なアイテムが候補セットに入らない可能性もあり、性能に限界がある
この研究ではmatching function learningによるランキングを高速化できる手法を提案する
アイテムが分布するベクトル空間を探索することで、全アイテムのスコアを計算せずに最適解に到達する
この手法はあらゆるランキング尺度に対応できる
例えば高速な探索としてのANNOYなどは、ランキング尺度に強い仮定を置いている
この手法はNNベースでのランキング尺度のような非凸なものにも対応できる
先行研究と比べてどこがすごい?
近似近傍探索では、ランキング尺度の仮定が強い
本研究はそのような強い仮定が必要ない
手法のキモはどこ?
HNSWをベースにした探索 SL2G を提案
正直詳しい理論は沼に嵌りそうなので具体的な実装のみ……
HNSWって?
近似近傍探索のアルゴリズム
まず、NSW
予めアイテムをノードとして、アイテム同士を繋いだグラフを作っておく
必ずしも近いアイテム同士が繋がれるわけではない、ところどころ遠いアイテム同士も繋がる(それが良いらしい)
探索時はランダムなアイテムを選択肢、そこから貪欲にエッジを辿ってクエリの近傍のエッジを探し出す
現在のアイテムに繋がっているそれぞれのアイテムと目標との距離を計算し、より近い方へアイテムを辿っていく
辿っていくアイテムと繋がっているアイテムに対してのみ距離を計算すればよいので、計算量を抑えられる
たまにある「長いエッジ」のおかげでショートカットしてさらに計算量を抑えられたりする
HNSWはNSWを階層的にしたもの
探索時、まずは粗いグラフからスタートして徐々に細かいグラフに移行していく
これのP23〜が非常にわかりやすかった
HNSWではL2尺度での探索を行ったが、それをNNベースの非凸なマッチング尺度に置き換えた
HNSWはL2尺度のような仮定の強い凸関数だけでなく、NNベースの非凸な関数にも適用できる……らしい
その場合でもちゃんと局所最適に陥らず、大域最適に落ち着く
これにも「長いエッジ」が良い役割を果たすらしい
グラフ作成時はあくまでL2ベース(それでも大丈夫だというのを証明してるっぽい)
ただし、データが十分に密でないとそれは成り立たない……らしい
まあわかる気もする
アルゴリズムは大きく2ステップに分かれる
L2尺度ベースのグラフ構築
構築したグラフ上での任意の尺度を用いた検索
L2尺度ベースのグラフ構築
https://gyazo.com/2dd05809f87561a73263efa3ec5969c3
HNSWをベースにしたグラフ構築
7~15のノード選択法はHNSWの手法
構築したグラフ上での任意の尺度を用いた検索
https://gyazo.com/2f11e0df84c7918570ff52514964b4ca
基本的にHNSWと同じっぽい
ただし $ fが任意の関数なのが異なる
どうやって有効だと検証した?
実験
データセット
Yelp
Amazon Movie
尺度関数
2通り用意
User VectorとItem Vectorを受け取る
これらは同じ空間上のベクトルでなくても良い
次元数とか違ってもOK
MLP-Concatは非対称なので、対称になるようにMLP-Em-Sumを用意した
User VectorとItem Vectorが同じ空間上に分布するようEmbedding Layerを噛ませる
https://gyazo.com/526e18894ebaac3cfed9df6b634905ff
ちなみに実際にはEm-Sumの入力は64次元、Concatは32次元
比較手法
同じタスクをやってる研究はない
クエリとアイテムのベクトル空間が違ったり、非凸な尺度関数での探索
とりあえずANNOYとHNSW
ANNOY
ANNOYで候補を絞り込んだあと、それに対してランキングする
HNSW
グラフの作成でもNNベースのマッチング関数を使う
ただし、改変後の精度保証はされない
検索ではほぼ提案手法と同じ?
ぶっちゃけかなり被ってるっぽい
実験設定
ground truthラベルを使った精度検証はしてないよ
(a) Recall vs. Time; (b) Recall vs. Computations.
top-10とtop-100で実験した
パラメータは各アルゴリズム毎に調整
All time-related experiments were performed on a 2X 3.00 GHz 8-core i7-5960X CPU server with 32GB memory.
実験結果
https://gyazo.com/6733eb3f5c092b50ea3889f523512668
https://gyazo.com/a2811be3e69796031a8f7eb77071d2f0
Recall vs Computationはtop-10のみ
ANNOYはやはり単純なmetric measure(L2 measureとか)に最適化されていて、性能はかなり悪い
HNSWはいくらかのRecallでは総当りより高速だが、それでもSL2Gよりはるかに悪い
非対称なMLP-Concateだとさらに性能差が顕著
SL2Gは局所解が複数存在するような空間でも適切に探索できる
スケーラビリティ
https://gyazo.com/ad79343e5a08b97e0fe3b684c8b6c110
スケーラビリティを調査するため、Yelpからデータをさらに生成
巨大なデータセット内でも、それなりのパフォーマンスで高速化を維持している
ベースラインは全然ダメ
グラフ構築速度
https://gyazo.com/7b765b15fbd4e4079d0292f8f00dafc2
複雑な尺度関数を使ったHNSWより、L2尺度を使ったSL2Gの方が遥かに早い
SONG実装
https://gyazo.com/6d44c2d42f5801aad70ed87c1e3f9105
SONGというGraph platform上でもHNSWとSL2Gを実装し、パフォーマンスを比較した
それでもやっぱりSL2Gの方が性能良い
所感
やってる事自体は先行研究を少し変えてみたって感じだけど、それが適用できる、ときちんと証明がついているのが良さげ
早そうだがそれはそれとしてメモリをだいぶ食いそう
やはり精度比較は欲しい
特にrepresentation learningとの比較がどうなるのか気になる