Publications

カンファレンス (国内) 公平性を考慮した高速な内積探索

青山 和禎 (阪大), 天方 大地 (阪大), 藤田 澄男, 原 隆浩 (阪大)

第15回データ工学と情報マネジメントに関するフォーラム (第21回日本データベース学会年次大会) (DEIM2023)

2023.4.25

近年,推薦システムは多くの実世界アプリケーションに応用されている.既存の推薦システムでは,ユー ザがアイテムに対して行う評価を予測し,評価予測値の高い上位k 個のアイテムを探索するk-MIPS 問題を解くこと が一般的である.しかし,k-MIPS 問題では公平性を考慮しておらず,推薦リストに含まれるアイテムに偏りがあり, 推薦リスト中のアイテムの多様性が低く,新たな気付きを与えづらい.そのため,本論文では,公平性を考慮した内 積探索問題を扱う.この問題は,カテゴリをもつアイテムベクトルの集合,クエリ,閾値および出力サイズk が与え られたときに,k 個の各アイテムについて,カテゴリはランダムに決定され,決定されたカテゴリのアイテム集合か らクエリとの内積が閾値以上となる全てのアイテムについて結果として出力される確率が均等になるように探索する というものである.素朴なアルゴリズムでは高速に解くことは難しいため,我々は,この問題を高速に解くためのア ルゴリズムを提案する.我々のアルゴリズムは,コーシーシュワルツの不等式を用いたアイテムの探索範囲決めを二 分探索を用いて高速に行い,決定した範囲内のアイテムからランダムに条件を満たすアイテムを探索する.我々のア ルゴリズムは,理論的および実践的に高速である.実世界のデータを用いた実験により,提案アルゴリズムが既存の 技術と比較して優れた性能であることを示した.

Paper : 公平性を考慮した高速な内積探索新しいタブまたはウィンドウで開く (外部サイト)