Clustering and Constructing User Coresets to Accelerate Large-scale Top-𝐾 Recommender System
Author
Jyun-Yu Jiang, Patrick H. Chen, Cho-Jui Hsieh, Wei Wang
Department of Computer Science, University of California, Los Angeles, CA, USA
何故読んだか
Gunosyと類似した推薦手法を行っているようだったので、差分を知りたかったため
概要
Eコマース市場の推薦を前提とする
ユーザベクトルとアイテムベクトルの近傍検索には全てのユーザベクトルとアイテムベクトルの内積を求める必要があり、アイテム数が膨大になるほど更新的な推薦ができなくなるので、効率的な推薦が求められる
MIPS(the maximum inner product search)は内積計算の加速に有用な手段であり、準備と予測の2段階のプロセスを採用しているが、準備と予測を含めた総合的な時間は大きくなる傾向にある
上記の問題に対処したTop-K Recommender(CANTOR)の提案を行う
貢献
ユーザ情報を用いて推薦システムの予測プロセスを高速化
ユーザベクトルの分布に基づいてユーザをクラスタリングし、代表ベクトルを産出
公開されたデータセットでCANTORが推薦システムの向上に貢献したことを証明
提案手法(CANTOR)
変数/定数の定義
https://gyazo.com/df531d1c007033969be91ecb71204880
定義1: Affinity Group
コサイン類似度によりクラスタリングされたユーザのグループ
定義2: Preferred Item Set
Affinity Groupのユーザが好むアイテムセット
Affinity Groupの重心ユーザではなく、ある手法により代表的なユーザ(Coreset)を選出
定義3: User Coreset of an Affinity Group
下記を満たすユーザの集合(Preferred Item Setのアイテムとの内積が類似しているユーザ)
$ |p_i q^T - N_{st}(p_i)q^T| \leq\delta
フレームワーク
https://gyazo.com/e8797be81ebd7050f567a219b1d8c83f
※SU: Speed upの肝
Prepare Layer
1. Sub-sampled User Vectors:
Multinomial_Samplingを用いてユーザをサンプリングする <- SU
2. Affinitu Group Modeling -> Affinity Groups:
各々のAffinity Groupの重心を求める
3. Adaptive Representative Selection -> Representative Sets((各クラスタの代表ユーザベクトル集合)):
ユーザクラスタ毎にユーザベクトル間の類似度が閾値$ \epsilon以下のユーザベクトルを選出 <- SU
4. Preferred Item Set Construction for At -> Preferred Item set:
各クラスタのRepresentative Setsの近傍KのPreferred Itemを取得
Predict Layer
1. ユーザpiに最も類似しているクラスタの重心ベクトルvt選出
2. vtのPreferred Item setを取得
3. ユーザpiの近傍のPreferred Item set内のアイテム取得
4. アイテム推薦
実験
Dataset
https://gyazo.com/f1ea94894ef68e10c5bcf606dacbb230
BaseLine
$ \epsilon-approximate link prediction($ \epsilon-Approx)
Greedy-MIPS(GMIPS)
SVD-softmax(SVDS)
Fast Graph Decoder(FGD)
Learning to Screen(L2S)
結果
https://gyazo.com/659487a33fa170c14e1227913e4ad753
CANTORが安定した精度(Precision)、かつ、スピードで推薦することが可能
特にPT(準備プロセスにおけるスピード)が短縮されている
Adaptive Representative Selectionの有効性
https://gyazo.com/3bb6125ce70dd5be157bcfd75929d1bf
w/ : Adaptive Representative Selectionあり, w/o : Adaptive Representative Selectionなし
近傍アイテムを検索する際に、近傍元が少なくなっているので、それに応じて計算時間が短縮
所感
やっぱり、Gunosyのパソナロジックに大いに似ていたなという印象
Adaptive Representative Selectionに対するPrecisionの精度の向上度合いが含まれていなかったが、現在Gunosyでは重心を用いているけど、この重心に比べると精度が向上するのかな? <- コストと見合い
近傍探索に関しては特に改善点がなかったので、そこがネックな気がしている
大いに省略しているがHyperParameterに対してのTradeOffに関しての調査も行われているので、詳細を知りたい方は本論文を参照ください