DEIM Forum 2023 2b-3-1

公平性を考慮した高速な内積探索青山和禎†

天方 大地†

藤田 澄男††

原隆浩†† 大阪大学 〒 565–0871 大阪府吹田市山田丘 1-5†† ヤフー株式会社
E-mail: †{aoyama.kazuyoshi,amagata.daichi,hara}@ist.osaka-u.ac.jp, ††sufujita@yahoo-corp.jp
あらまし近年，推薦システムは多くの実世界アプリケーションに応用されている．既存の推薦システムでは，ユー

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

1 はじめに近年，推薦システムは Amazon や Netﬂix など多くの実世界
アプリケーションに応用されている．実世界においてユーザがアイテムの購入を検討する際，アイテム数は膨大であるため，ユーザが一つ一つ興味のあるアイテムを調べるのは手間である．
そのため，ユーザが興味を持ちそうなアイテムだけを推薦する
推薦システムを用いることでユーザがアイテムを探す負担を軽減することができる [4]．
推薦システムにおける最も有名な手法の一つは MF（Matrix

Factorization）であり，ユーザの未評価アイテムに対して評価
予測値を得る手法である [9]．MF に基づく推薦システムでは，
クエリとしてユーザベクトル q が与えられたとき，q との内積が最大となる上位 k 個のアイテムベクトルを探索する k-MIPS
問題を解くことが一般的である．この k 個のアイテムというのは，推薦リストとして実際に推薦されるアイテムである．
しかし，推薦結果に対するユーザ満足度の観点において，k-MIPS 問題を解くことが最も適しているとは限らない．まず，
k-MIPS 問題では，推薦リストに含まれるアイテムには似たものが多くなり，ユーザの満足度が下がってしまう問題がある [7]．
例えば，映画における推薦システムにおいて，『アベンジャー
ズ』に対して高い評価をつけたユーザに対して，『アベンジャー
ズ/エンドゲーム』など『アベンジャーズ』シリーズばかり推薦することは，ユーザにとって自明な推薦であり，新鮮さのない「飽き」を生じさせる推薦である．これは，ユーザの嗜好とユーザ満足度の観点からみると，良い推薦であるとは言い難い．
次に，k-MIPS 問題では，推薦結果が毎回同一の結果になってしまうという問題もある．推薦結果が毎回同一であるとユーザが新しい興味を得られる機会が少なくなってしまいユーザ満足度が低くなってしまう．実世界には，多種多様なアイテムが存在しており，推薦の幅が狭くなってしまうことはユーザにとって大きな機会損失である．
この問題を解決するために，我々は公平性を考慮した内積探索問題を考える．我々は 2 つの公平性を考慮することでユーザ満足度の高い推薦が行えると考える．1 つ目に，カテゴリの公平性を考える．k-MIPS 問題では，内積値の大きさに基づく推薦を行っており，特定のカテゴリのアイテムが多く推薦される可能性がある [7]．この問題を解決するため，推薦される k 個のアイテムの各カテゴリは推薦時に毎回均等な確率で決定されるという条件を設定する．この設定によって，推薦リスト内のカテゴリは多種多様なものとなり，推薦結果の多様性を高めることができる．2 つ目に，カテゴリ別のアイテム集合内の公平性である．k-MIPS 問題では，内積値の大きい順に k 個のアイテムを推薦しているが，それでは，推薦されうるアイテムの範囲が狭く，ユーザが推薦結果に新規性や多様性を感じない．そのため，我々はユーザとの内積がある閾値以上となる全てのア
イテムについて，一様ランダムに推薦され，推薦結果は以前の推薦結果に依存しないという設定をする．つまり，ユーザがある程度興味のあるアイテムからランダムに推薦され，推薦結果
は毎回ランダムなものとする．この設定により，推薦リストのアイテムはユーザの嗜好を反映したものでありながら，ユーザにとって新規性や多様性の高いものにすることができる．
この問題を解く素朴なアルゴリズムとしては，クエリが与えられたとき，カテゴリをランダムに決定し，そのカテゴリのア
図 1: 素朴なアルゴリズム概要

イテム集合について，内積がある閾値以上となるアイテムを全て探索し，その探索したアイテム集合の中からランダムにアイテムを選択する．しかし，このアルゴリズムでは，k 個のアイ

サイズ k ，アイテム集合 P および閾値 τ が与えられた時に，テムを探索する場合，カテゴリ内の全てのアイテムについて，

p·q >= τ となるアイテムの中から，次の条件で出力サイズ k 個

内積を計算する必要があり，カテゴリ内のアイテム数を n，ベのアイテムを探索する．

クトルの次元数を d とすると O(nd) の時間計算量が必要である．実世界のデータセットにおいて，アイテム数は膨大になりうるため，この素朴なアルゴリズムは大規模なシステムにはス
ケールしない．

•k 個の各アイテムについて，あるカテゴリ i が探索される確率は均等である．

•

集合 Pi ′ において，集合内の各アイテムが探索される確率は均等である．

以上から素朴なアルゴリズムでは，高速に計算することは難•クエリ結果は過去のクエリ結果とは独立である．

しい．そこで我々は，問題解決のための新しいアルゴリズムを提案する．我々のアイデアは，コーシーシュワルツの不等式とこの問題を解く素朴なアルゴリズムとしては，次のようなもの

二分探索を用いて，条件を満たすアイテムの範囲を高速に求め，が考えられる．図 1 は素朴なアルゴリズムの概要を示している．

その中からランダムに探索していくというものである．我々の以下の処理を k 個のアイテムが得られるまで繰り返す:

主な貢献は以下である．

(1) カテゴリをランダム一様に決定する．(決定されたカテゴ•

内積空間における公平性を考慮した探索を行うための新リを i とする．)

しいアルゴリズムを提案する．
提案アルゴリズムの性能を理論的に分析する．具体的に(2) Pi ′ が未計算であれば，カテゴリ i のアイテム集合 Pi のは，素朴なアルゴリズムでは時間計算量 O(nd) だが，提案アル

全アイテムベクトルについて内積を計算し，閾値 τ 以上か•

ゴリズムでは O(kd log n) に削減できることを示す．

•

実世界のデータセットを用いて大規模な実験を行う．比較手法よりも高速であることを示す．

どうかを調べ，Pi ′ を構築する．

(3) Pi ′ =| ∅ のとき，Pi ′ からランダムにアイテムベクトルを返し，そのアイテムベクトルを取り除く．
この素朴なアルゴリズムでは，全てのアイテムについて内積を2 予備知識

計算する必要があるため，時間計算量 O(nd) となってしまう．
本章では，表記の説明と問題定義を行い，素朴なアルゴリズ
ムでは高速に解くことが難しいことを説明する．

そのため，我々は時間計算量を削減し，O(kd log n) で解けるよ
うなアルゴリズムを提案する．

P は n 個のアイテムベクトル p(1) , ..., p(n) からなるアイテ
ム集合とする．Q は m 個のユーザベクトル q(1) , ..., q(m) からなるユーザ集合とする．各データベクトル p ∈ P，q ∈ Q は d

3 提案アルゴリズム

次元であり，p = (p1 , ..., pd )，q = (q1 , ..., qd ) である．カテゴ

この章では，公平性を考慮した内積探索問題を O(kd log n)

リ数を C とする．各アイテムベクトルはカテゴリを 1 つ持ち，時間で解くことのできる我々の提案アルゴリズムについて説明

カテゴリ i のアイテムベクトル集合を Pi ∈ P とする．

する．まず，提案アルゴリズムの方針について説明し，次に，アルゴリズムをオフラインフェーズとオンラインフェーズに分

定義 1( 内積 ) 2 つのベクトル p = (p1 , ..., pd ) ∈ R と
dq = (q1 , ..., qd ) ∈ Rd が与えられた時，内積 p · q は以下で求まる．

けて具体的に説明する．最後に，アルゴリズムの分析として，
空間計算量と，時間計算量および公平性について説明する．

3. 1 方p·q=d∑p s · qss=1

針まず，素朴なアルゴリズムの時間計算量が O(n) となってしまう原因は，カテゴリが決定された後，決定されたカテゴリのアイテム集合内の全てのアイテムベクトルについて，内積を計．
閾値 τ が与えられたとき，内積 p · q >= τ となるカテゴリ iのアイテム集合を Pi ′ とする．
ここで，我々の解決する問題を次のように定義する．

算するためである．我々の定義する公平性を考慮した内積探索問題では，p · q >= τ となる全てアイテムベクトル p を求める
必要はない．そのため，ランダムサンプリングを考える．具体的には，カテゴリをランダムに決定し（i とする），Pi からラ

定義 2( 公平性を考慮した内積探索問題 ) クエリ q，出力

ンダムサンプリングし，p · q >= τ を満たす場合はそのアイテム
ベクトル p を返す．この処理を k 個のアイテムが得られるまで繰り返す．ランダムサンプリングすることで，公平性の条件を満たしつつ，内積計算回数を減らすことができる．
しかし，Pi からランダムサンプリングした p が，p · q >=τ
となる確率は，|Pi ′ |/|Pi | であるため，|Pi ′ | が |Pi | と比べて小さいとき，アイテムが返されるために必要なサンプリング回数が増え計算時間が長くなる．
そのため，我々は，コーシーシュワルツの不等式 (p · q <=∥p∥∥q∥) を利用し，サンプリングした p が p · q >= τ を満たす
確率を高めることを考える．具体的には，コーシーシュワルツ
図 2: クエリフェーズ概要の不等式 (p · q <= ∥p∥∥q∥) から |p||q| < τ となる p を枝刈りする．条件を満たすことがないアイテムベクトルを枝刈りすることができるため，アイテムが返される確率が高まり，サンプ
リング回数を減らすことができるため，高速化できる．
次に，どのようにすれば高速に ∥p∥∥q∥ < τ となる p を枝刈りしサンプリング範囲を求めることができるのかということを考える．単純な方法として次のような手法が考えられる．

Algorithm 1 クエリフェーズ
Input: P1 ，. . . , PC ，q，τ ，and k
Output: Qk
1: compute ∥q∥
2: Qk ← ∅3: while |Qk | < k do

まず，前処理として，各カテゴリのアイテムベクトル集合に4:

おいて，アイテムベクトル p をノルム ∥p∥ の降順にソートし

5:i ← a randomly selected categoryindex ← arg min ∥pl ∥∥q∥ >=τておく．次に，クエリフェーズとして，クエリ q が与えられた

6:

for each j ∈ [1, O(log n)] dol,pl ∈Pi

とき，カテゴリをランダムに決定し (i とする)，Pi 内のアイテ

7:pα ← random sample f rom {p1 , · · · , pindex }if pα · q >= τ then

ムベクトル p について，順に ∥p∥∥q∥ と τ とを比較していく．

8:∥p∥∥q∥ < τ となるアイテムベクトルが見つかったとき，そのア

9:イテムベクトルと残りのアイテムベクトルは全て ∥p∥∥q∥ < τ

10:となるため枝刈りを行うことができる．しかし，この手法では，
最悪 Pi の全ての要素にアクセスする必要があり，サンプリン

Qk ← Qk ∪ {pα }breakend if

11:
12:

end for

13: end while

グ範囲を決定することに最悪 O(n) 時間要する．これでは，高速化のための手段として十分ではない．
コーシーシュワルツの不等式を適用しサンプリング範囲を求めるということは，∥p∥∥q∥ >= τ を満たすアイテムベクトル pの内，∥p∥ が最小のものを求めるということである．そのため，二分探索が適用でき，O(log n) 時間で求めることができる．
我々のアルゴリズムは，コーシーシュワルツの不等式と二分探索を用いて，条件を満たすアイテムの範囲を高速に求め，その中からランダムに探索していくことで，効率的に条件を満たすアイテムベクトルにアクセスする．

3. 2 オフラインアルゴリズム
最初に，提案アルゴリズムのデータ構造を構築するオフライ
ンアルゴリズムについて説明する．なお，このオフライン処理は一度しか行われず，構築されたデータ構造は任意の q および

τ に適用できる．

アルゴリズムについて説明する．図 2 はクエリフェーズの概要を示している.Algorithm 1 はクエリフェーズの擬似コードを示している．
クエリフェーズでは，以下の処理を k 個のアイテムが所得されるまで繰り返す．

(1) ランダムにカテゴリを決定する．(i とする．)(2) カテゴリ i のアイテムベクトル集合 Pi について，コーシー
シュワルツの不等式を適用し，二分探索で ∥p∥∥q∥ < τ となる p について枝刈りし，探索範囲を決定する．

(3) (2) で求めた探索範囲の中から p をランダムにサンプリン
グする．

(4) (3) で取得した p が p · q >= τ となり，結果の集合に含ま

オフラインアルゴリズムとしては，アイテム集合 P を各カテ

れていなければ，結果の集合に p を追加する．そうでなけ

ゴリのアイテム集合 P1 · · · PC に分割する．各カテゴリのアイ

れば，(3) に戻る．サンプリングは最大 O(log n) 回行う．

テム集合 P1 · · · PC 内の全てのアイテムベクトル p について，
それぞれノルム ∥p∥ を計算する．各カテゴリのアイテムベクト

3. 4 分ル集合をノルム ∥p∥ でソートする．

空間計算量．我々のアルゴリズムにおいて，アイテムベクトル

3. 3 クエリフェーズ

集合 P 内の n 個のアイテムベクトルとノルムをデータ構造と次に，クエリとして q が与えられたとき，オフラインフェー
ズで構築したデータ構造を用いて，高速に内積探索するための析

して用いている．そのため，空間計算量は O(n) である．
時間計算量．j をクエリフェーズ (2) で二分探索によりサンプ
リング範囲を求めたときの ∥p∥ が最小のアイテムベクトルのイ

公平性．ま ず，カ テ ゴ リ の 公 平 性 に つ い て 考 え る ．カ テ ゴ

ンデックスとする．

リ の 変 数 を X と す る ．i と j を 任 意 の カ テ ゴ リ と す る と
定理 1

我々の 提 案 ア ル ゴ リ ズ ム の 時 間 計 算 量 の 期 待 値 はO(k(log n + d)) である．

Pr(X = i) = Pr(X = j) となり，カテゴリの公平性の条件を満たす．また，p と p′ を集合 Pi ′ 内の任意のアイテムベク
トルとする．このとき，アイテムベクトルの変数を Y とすると証明.

クエリフェーズの (2) の処理は二分探索を用いること

で O(log n) 時間で実行できる．次にクエリフェーズにおいて，p·q>= τ を満たす p が k 個返されるために必要なサンプリン
グ試行回数について考える．既に k ′ 個 p が取得されているときを考える．ここで Ak′ を p · q >= τ を満たす p が返されるた

Pr(Y = p) = Pr(Y = p′ ) となるため，カテゴリ別のアイテム
集合内の公平性の条件を満たす．

4 評価実験

めに必要な試行回数とする．Ak′ は変数である．ここで，|Q|

この章では，評価実験を行い，我々のアルゴリズムは公平を決定したカテゴリ内の p · q >= τ を満たす p の個数とする．

性を考慮した内積探索問題を解く他のアルゴリズムに比べて，高速であることを示す．全ての実験は，CPU に 3.0GHz のPr(Ak′ = m) = (Core i9-9980XE および 128GB の RAM を搭載した計算機上

j − |Q| + k′ m−1 |Q| − k′
)
×
j
j

で行った．

′

4. 1 設

ここで，z = 1 − |Q|−kとすると，j

E[Ak′ ] =∞∑定

データセット． 我々は以下の 4 つの実世界データセットを用い

mz

m−1

m=1

1
(1 − z) =1−z

た．各データセットのユーザ数，アイテム数，およびカテゴリ
内アイテム数を表 1 に示す．

j== O(1)|Q| − k′•Netﬂix 1 : Netﬂix Prize で用いられたレーティングのデー

タセット．

こ こ で ，j = O(n)，|Q| = O(n)，k ′ = O(k) で あ る ．よって，k 個のアイテムが返されるための試行回数の期待値∑′
は， k−1k′ =0 E[Ak ] = O(k)．よって，時間計算量の期待値は

2

O(k(log n + d)) となる．

•

Movielens 2 : Movielens 25M データセット．

•

AmazonKindle [6]: AmazonKindle の書籍のレーティン

グのデータセット．

•

AmazonMovie [6]: AmazonMovie の映画のレーティン

グのデータセット．
定理 2

少なくても定数確率で提案アルゴリズムの時間計算量

は O(k(log n + d)) となる．

Matrix Factorization を実行した．各データセットのデータベ

クエリフェーズの (3) の処理について考える．既に k ′証明.

個 p が取得されているときを考える．ここで B をクエリフェー
ズ (3) においてランダムに p を決定したとき，p · q < τ であ′る事象とする．ここで Pr(B) = 1 − |Q|−kである．s 回連続で
j
失敗する確率は，ユニオンバウンドより，

Pr[B ∪ . . . ∪ B] <=ユーザベクトルとアイテムベクトルを生成するために，[3] の∑s

テゴリをメタ情報を基に割り当てている．その他の 3 つのデー
タセットは，データセット内の各アイテムにランダムにカテゴ
リを割り当てている．Movielens のカテゴリ数は 20 であり，その他の 3 つのデータセットのカテゴリ数は 25 である．
比較手法． 我々は以下の 3 つの比較手法を用いた．

|Q| − k′)Pr[B] = s(1 −j•

ここで，s(1 − |Q|−k) = c とする．c ∈ (0, 1] であり，c = O(1)jとする．このとき，s = O(1) を得る．そのため、時間計算量は

2

O(n)．
•

k
少なくても (1 − n1 ) の確率で提案アルゴリズムの時

r-NNS [2]: 公平性を考慮した範囲検索アルゴリズム．時間計算量の期待値は，o(kdn log n)．

•
定理 3

Cauchy-Schwarz: 提案アルゴリズムから二分探索とランダムサンプリングを取り除いたアルゴリズム．時間計算量は′O(k(log n + d)) となる．

クトルの次元数は 200 である．Movielens のデータセットはカr-NNIS [1]: クエリ独立性をもたせた公平性を考慮した

範囲検索アルゴリズム．時間計算量の期待値は，o(kdnlog5 n)．
すべてのアルゴリズムは C++で実装を行い，g++ 7.5.0 に最間計算量は O(kdlog n) となる．

適化オプション-O3 付加してコンパイルした．
証明.

クエリフェーズの (3) の処理について考える．既に k′

個 p が取得されているときを考える．ここで s 回試行したと′評価指標として，p · q >= τ となる p が 1 つ以上存在する全ユーザの平均実行時間 (msec) を用いた．

s) であき，少なくとも１回は成功する確率は，1 − (1 − |Q|−kjる．これが 1 − n1 と等しいとき，s =

log n
log

j
j−|Q|+k′= O(log n)kとなる．よって k 個のアイテムを取得するとき，(1 − n1 ) の確率で時間計算量 O(kdlog n) となる．

2

1：https://www.cs.uic.edu/liub/Netﬂix-KDD-Cup-2007.html
2：https://grouplens.org/datasets/movielens/る．ここでは，厳密解ベースの手法と近似解ベースの手法の二表 1: データセットの統計

つに分けて説明する．

ユーザ数

アイテム数

カテゴリ内アイテム数

Netﬂix480, 189

17, 770710 ∼ 711

Movielens162, 541

59, 047

51 ∼ 15191

ンによる手法の 2 つがある．空間分割を行う手法として，[12]AmazonKindle

1, 406, 890

430, 530

17221 ∼ 17222

では木データ構造に基づく分枝限定法を用いて不必要なデー

AmazonMovie

2, 088, 620

200, 941

8037 ∼ 8038

タベクトルを枝刈りする Dual-Tree および Dual-Tree の効率

厳密解ベースの手法には，空間分割を行う手法と，線形スキャを上げるための新しいデータ構造 Cone Tree が提案されている．しかし，空間分割に基づく手法は次元の呪いによって高4. 2 結果と分析
提案アルゴリズムと比較手法の比較．表 2 に τ = 4，k = 5 での平均実行時間の結果を示す．提案アルゴリズムの方が，最大（AmazonKindle の場合) 約 333 倍，最低（Netﬂix の場合) 約

18 倍高速であることが分かる．Cauchy-Schwarz と比較して提案アルゴリズムが高速である理由は，全てのアイテムベクトルを探索することなく，条件を満たすアイテムベクトルを効率的に探索できるためである．提案アルゴリズム，r-NNS，およびr-NNIS はサンプリングする手法であるが，r-NNS と r-NNIS
はサンプリングプールから条件を満たすアイテムベクトルが取得される確率が低く，多くのアイテムベクトルについて探索を行う必要があり，提案アルゴリズムと比較して低速となる．

加すると，線形スキャンよりも性能が悪くなる．そのため，線形スキャンベースの手法が多数提案されている．線形スキャン
ベースの手法として，FEXIPRO [10] や LEMP [13, 14] がある．FREXIPRO は SVD 変換，正数変換，および整数近似によって厳密な内積上限を設定し，枝刈りの効果を高める手法である．LEMP は，アイテムベクトルの集合をバケットに似たよ
うなノルムのベクトルが含まれるようにバケットに分割し，バケット毎にノルムの大きさに応じた最適な手法を選択することで高速化している．
高次元ベクトル空間の場合，k-MIPS 問題を厳密に解くことは計算コストが高いため，近似解ベースの手法も多く研究されている．一般的な手法として，内積探索問題を最近傍探索

表 2: τ = 4，k = 5 での平均実行時間 (msec) の結果
Proposed

次元空間においてはうまく機能せず，数十次元まで次元が増Cauchy-Schwarz r-NNS r-NNIS

問題や最大コサイン類似度探索問題へと変換し，LSH を用いて高速に解く手法がある．Simple-LSH [11] は，アイテムとク

Netﬂix2.33 × 10−2

0.422

0.570

1.69

Movielens

3.51 × 10−2

1.76

2.66

11.6

エリそれぞれに対称変換を行い，MIPS 問題を MCS 問題 (最AmazonKindle

7.68 × 10−2

25.6

5.20

24.8

大コサイン類似度問題) に変換する．H2-ALSH [8] は，前処理

AmazonMovie

4.18 × 10−2

12.3

3.12

12.5

フェーズにおいて，ノルムの大きさに応じてデータベクトルの集合をいくつかの集合に分割しハッシュテーブルに格納する．

τ の影響．図 3 に τ を 3，3.5，4 および 4.5 に変化させたときの提案アルゴリズムと比較手法の平均実行時間の結果を示
す．どのデータセットにおいても，提案アルゴリズムが最も高速であるということが分かる．また，τ を大きくするほどCauchy-Schwarz は高速になっていることが分かる．これは，τ
が大きくなるほど，多くのアイテムベクトルが p · q < τ となるため，多くのアイテムベクトルを枝刈りでき，高速に計算できるためである．提案手法，r-NNS，および r-NNIS は．τ を大きくするほど，p · q >= τ となる p が少なくなるため低速となっている．また，同じアイテムをサンプリングすることも多くなるため，τ が大きくなるほど低速となる．

k の影響．図 4 に k を 5，10，15，20 に変化させたときの提案アルゴリズムと比較手法の平均実行時間の結果を示す．どの
データセットにおいても，提案アルゴリズムが最も高速であるということが分かる．どの手法においても，k を大きくするほど，多くのカテゴリのアイテム集合について探索を行うため，低速となる．

5 関連研究5. 1 k-MIPS
k-MIPS 問題を解くことは，多くのアプリケーションにとって重要であるので，高速に解くために多くの研究がなされていクエリフェーズにおいて分割したサブセットについて，ノルムの降順でサブセット内のデータベクトルの個数に応じて，線形スキャンと LSH を用いた近似最近傍探索の内適切な手法を用いている．また，k-MIPS 問題から近似最近傍探索問題へと変換するためのクエリとデータベクトルの変換に歪み誤差の少な
い QNF 変換を用いることでより厳密解に近づくようにしている．また，[5] ではベクトル量子化を用いた手法 ScaNN を提案している．ベクトル量子化は，データベクトル集合を有限個のセントロイドに置き換えることで，大量のデータを少ない代表
パターンに置き換え圧縮する手法である．ScaNN は，このベクトル量子化によって生じる損失を最小限にしつつ，ベクトルの量子化を行う．
しかし，これらの問題は k-MIPS 問題を解く手法であり，我々の定義する公平性を考慮した内積探索問題を解くことはできない．

5. 2 公 平 探 索
r-NNS [2] は，クエリ q とデータ集合 D が与えられたとき，
q との距離が r 以内の各データ点 p ∈ D について，一様な確率で返されるようなデータ構造を構築する問題に取り組んだ手法である．r-NNS のアイデアは，データ集合 D 内のデータ p について，ランダムなランク付けを行い，LSH を用いて高速化する手法である．時間計算量は，o(kn log n) となる．r-NNIS [1] は，

図 3: τ の影響

図 4: k の影響

r-NNS の問題にクエリ結果が過去のクエリ結果とは独立である

セグメントを選び探索を行う．これを LSH を用いて高速化しという条件を追加した問題に取り組んだ手法である．r-NNISている．r-NNIS の時間計算量は，o(kdnlog5 n) となる．

のアイデアは，データ点をランダムシャッフルし，いくつかの

これらの手法は，LSH を用いた手法であるため，常に条件をセグメントに分割する．クエリが与えられたとき，ランダムに満たすデータ点 p は一様な確率でアクセスされることを保証していない．

6 結論

本論文では，公平性を考慮した内積探索問題を定義した．この問題では，カテゴリの公平性とカテゴリ内のアイテムの公平性を考慮することで，推薦リスト内のアイテムの多様性や新規性を高めることができる．素朴なアルゴリズムでは，O(n) 時間かかる．我々はコーシーシュワルツの不等式を用いたアイテ
ムの探索範囲決めを二分探索を用いて高速に行い，決定した範囲内のアイテムからランダムに条件を満たすアイテムを探索することで，O(kd log n) 時間で解くことができるアルゴリズムを提案した．また，実世界データセットを用いた実験を行い，我々のアルゴリズムが比較手法を大幅に上回る性能を持つことを確認した．

謝辞.

本研究の一部は，文部科学省科学研究費補助金・基 盤研究(A)(18H04095)，JST さきがけ (JPMJPR1931)，および JST
CREST(JPMJCR21F2) の支援を受けたものである.

文

献[1] M. Aumuller, S. Har-Peled, S. Mahabadi, R. Pagh, and
F. Silvestri, “Fair near neighbor search via sampling,” In
SIGMOD-Record, pp.42–49, 2021.
[2] M. Aumüller, R. Pagh, and F. Silvestri, “Fair near neighborsearch: Independent range sampling in high dimensions,” In
PODS, pp.191–204, 2020.
[3] W.S. Chin, B.W. Yuan, M.Y. Yang, Y. Zhuang, Y.C. Juan,and C.J. Lin, “Libmf: A library for parallel matrix factorization in shared-memory systems.,” Journal Machine Learning Research, vol.17, no.1, pp.2971–2975, 2016.
[4] P. Cremonesi, Y. Koren, and R. Turrin, “Performance ofrecommender algorithms on top-n recommendation tasks,”
In RecSys, pp.39–46, 2010.
[5] R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simcha, F. Chern,
and S. Kumar, “Accelerating large-scale inference withanisotropic vector quantization,” In ICML, pp.3887–3896,
2020.
[6] R. He and J. McAuley, “Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborativeﬁltering,” In World Wide Web, pp.507–517, 2016.
[7] K. Hirata, D. Amagata, S. Fujita, and T. Hara, “Solving
diversity-aware maximum inner product search eﬃciently
and eﬀectively,” In RecSys, pp.198–207, 2022.
[8] Q. Huang, G. Ma, J. Feng, Q. Fang, and A.K. Tung, “Accurate and fast asymmetric locality-sensitive hashing scheme
for maximum inner product search,” In SIGKDD, pp.1561–
1570, 2018.
[9] Y. Koren, R. Bell, and C. Volinsky, “Matrix factorization
techniques for recommender systems,” in IEEE Computer,
pp.30–37, 2009.
[10] H. Li, T.N. Chan, M.L. Yiu, and N. Mamoulis, “Fexipro:
fast and exact inner product retrieval in recommender systems,” In SIGMOD, pp.835–850, 2017.
[11] B. Neyshabur and N. Srebro, “On symmetric and asymmetric lshs for inner product search,” In ICML, pp.1926–1934,
2015.
[12] P. Ram and A.G. Gray, “Maximum inner-product searchusing cone trees,” In SIGKDD, pp.931–939, 2012.
[13] C. Teﬂioudi and R. Gemulla, “Exact and approximate maximum inner product search with lemp,” ACM Transactions
on Database Systems, vol.42, no.1, pp.1–49, 2017.
[14] C. Teﬂioudi, R. Gemulla, and O. Mykytiuk, “Lemp: Fast
retrieval of large entries in a matrix product,” In SIGMOD,
pp.107–122, 2015.