Clustering and Constructing User Coresets to Accelerate Large-scale Top-K Recommender Systems

[hakubishin3]

The WEB Conference 2020 Research Track https://dl.acm.org/doi/10.1145/3366423.3380283

[hakubishin3]

Motivation

この論文では, latent factor modelを使った推薦を前提に置いている.

ユーザとアイテムそれぞれのlatent vectorsを得た後, 各ユーザに対してアイテム推薦を行うために, ユーザとアイテムのペアの内積を計算する. この時, ナイーブに全てのユーザ・アイテムのペアに対して内積を計算すると時間がかかり過ぎてしまうので, 探索を高速化するためにLSHやTree系などの近似最近傍探索を使う場合が多い.

ただ既存の探索アルゴリズムには2つ問題があると述べている.

• Preparation timeが伸びることを許容してinference timeを短くすることに焦点を当てているが, 推薦システムでは適宜再学習する必要があるため, Preparation timeとinference timeを合わせた全体の実行時間を短くする必要がある.
• 最近傍探索は任意のクエリベクトルが与えられた時に近いベクトルを探す問題だが, 推薦システムではクエリは任意のベクトルではなくユーザを表すlatent vectorであり, それらは強いクラスタリング構造を持つ. 既存のアルゴリズムはクエリごとに独立で計算するためこの構造を無視している.

そのため, 提案手法ではユーザ間の関係性を活用して, latent factor modelを用いたアイテム推薦のPrediction process (Preparation + inference) を高速化する.

[hakubishin3]

Framework Overview

• Preparation Stage
  • ユーザのlatent vectorsをサブサンプリングしてr個のグループにクラスタリング
  • グループ内のユーザ集合をカバーできるようなrepresentative vectors (coreset) をグループごとに求める
  • アイテムのlatent vectorsからアイテムの階層的なグラフ構造を構築しておき, 各ユーザグループのcoresetを用いたgreedyなグラフ探索により, 候補アイテム集合をユーザグループ毎に取得する.
• Prediction Stage
  • 予測対象ユーザの所属するグループを探し, そのグループに対応する候補アイテム集合とユーザの内積を取ることで, ランク付けを行う

[hakubishin3]

Preliminary

グループとは, 似たような興味を持っているユーザの集合である.

またグループの候補アイテム集合とは, グループ内のユーザが満足するアイテムの集合であり, その要素数はアイテム総数よりもはるかに小さい.

同じグループ内のユーザの関心は, グループのcoresetのrepresentative vectorsによってカバーすることができる.

[hakubishin3]

Affinity Group Modeling by User Clustering

高速化のためにユーザ間の関係性を利用する.

(1)はユーザの所属するグループを示すindicator変数zを説明している. p_iがユーザiのベクトルで, v_r はグループrの重心ベクトル. (2)が重心ベクトルの計算方法.

(1)と(2)のiterationにより重心ベクトルが求められる.

ただ上記のiterationをそのまま行うと計算コストが高いので, ユーザベクトルの一部をサブサンプリングして重心ベクトルを計算するようにする.

ユーザの度数分布は下記のような感じになるので, この度数の対数に比例した確率でサンプリングを実施する.

[hakubishin3]

Coreset Construction as Finding a Set Cover

上記のままだと候補アイテム集合を求めるための計算量はO(|Pt|nd)と大きい (nはアイテム総数, dは次元, |Pt|はグループt内のユーザ数)

そのためグループをカバーできるベクトルを集めたcoresetを用意する.

サブサンプルされた部分集合のε-coverは, 真の分布との内積値の差が漸近的に保証される. よってサブサンプルされたユーザベクトルを使ってcoresetを構築することができる.

存在するユーザグループ毎にcoresetを構築する必要がある. 計算コストが高いので以下のようなアルゴリズムで効率的に求められるようにする (条件を満たさない場合は逐次代表ベクトルを追加していくようなロジック)

coresetを構築することで, 候補アイテムを求める時の計算量はO(|Pt|nd)からO(|st|nd)に減らすことができる (|st|はcoresetの代表ベクトルの数)

[hakubishin3]

Proximity Graph Navigation for Preferred Item Set Construction

候補アイテム集合を作る際, 全探索するとO(nd)の計算量になるため, 計算高速化のためにグラフ探索を採用する.

実データにおけるアイテムの度数分布はユーザと同様の傾向を持っており, スモールワールド性を持っている. これを探索するのは時間がかかるので, より効率的な探索のために階層的にグラフを作って探索を行うことにする.

グラフ探索: http://yusukematsui.me/project/survey_pq/doc/ann_billion_2018.pdf

[hakubishin3]

EXPERIMENTS

modelはNMF

SUはO(nm)のナイーブなアプローチからの速度改善率 (nはuserの数, mはitemの数) PTはPreparation time, ITはInference timeのこと