[7D]多次元

10:25 〜 10:50

[7D-02] 高次元内積空間における近似逆 k-Ranks クエリ

*青山 和禎¹、天方 大地¹、藤田 澄男²、原 隆浩¹ (1. 大阪大学大学院情報科学研究科、2. LINEヤフー株式会社)

発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：なし

キーワード：

内積探索、逆 k-Ranks

機械学習技術の進展により，ユーザやアイテムといったオブジェクトを高次元ベクトル空間にマッピングし，評価予測値の高い上位k個のアイテムを検索するk-MIPS問題が一般的に用いられる．また，特定のアイテムに興味を持つk人のユーザを検索する逆k-Ranks問題も注目されており，これは商品のプロモーション，ターゲッティング広告，および市場分析に活用できる重要な問題である．高次元空間において逆k-Ranksを高速かつ厳密に解くことは難しいため，本論文では，近似逆k-Ranks問題に焦点を当てる．この問題は，クエリアイテムベクトルq，アイテム集合P，ユーザ集合U，出力サイズk，および近似比c>1を入力とし，R(u,q,P)の小さいk人のユーザuを解とした時に，これに対してc倍の誤差を許容する．ここで，R(u,q,P)は，ユーザuがクエリアイテムqをどれだけ好むかを他のアイテムと比較した順位である．本稿では，この問題を高速に解くためのアルゴリズムを提案する．実世界のデータを用いた実験により，提案アルゴリズムが既存のアルゴリズムと比較して優れた性能であることを示す．