[メモ] Prioritized DCIのアルゴリズム - にんひどりんはんのう

ICLR2017

上記論文で提案されている効率的なk-nn手法、Prioritized DCIについてのメモ。

同じ著者らが提案したDynamic Continuous Indexing(DCI)の改良手法になる。

あくまでアルゴリズムを理解したかっただけなので理論保証や証明等は省く。
また理解が間違っているかもしれないのであしからず。

データ構造の構築

データ構造は $mL$ 個のバイナリツリー $\{ T_{jl} \}_{j \in [m], l \in [L]}$ 。
$m$ と $L$ は適当なインデックス。速度や性能に影響する。
$n$ は学習データの数。
またランダム射影をするための単位ベクトル集合 $\{u_{jl}\}_{j \in [m], l \in [L]}$ も用意。

アルゴリズムは

事前に学習データを次元削減のため適当な方法(例えばNNとかで) $\mathbb R^d$ に射影しておく
各学習データポイントについて $u_{jl}$ で内積をとる
その値をkey、学習サンプルとしてのインデックスをvalueとして対応するバイナリツリー $T_{jl}$ に追加する

これにより $n$ 個のサンプルが追加されたバイナリツリーが $mL$ 個構築される。

クエリの検索

現在 $L$ 個のバイナリツリー集合が $m$ 個ある。
この $L$ 個のバイナリツリー集合からそれぞれ $k_0$ 個の候補点を抽出する。
結果的に(重複含む) $Lk_0$ 個の候補点が得られるのでここから近傍点を $k$ 個探索しそれを返す。

用意として $L \times n$ の2次元配列 $C$ 、 $L$ 個の優先度付きキュー $P_l$ をそれぞれ用意する。
またあらかじめクエリを $\mathbb R^d$ に射影しておく。

$l \in L$ 番目の優先度付きキュー $P_l$ は、対応する $T_l$ の $m$ 個のバイナリツリーそれぞれから1つずつ最も距離の近いサンプルを取り出し、クエリとの差分の絶対値のマイナスを優先度として追加し初期化する。
つまり各 $P_l$ には $m$ 個のデータが入っていて、距離の近い順に取り出せる状態になる。

ここから探索。
ある $l \in L$ について。
$l$ 番目の集合からの候補点が $k_0$ に満たない場合に

$P_l$ から候補点 $p$ を取り出し、対応する学習データのインデックス $h$ から $C_l$ の対応するインデックスのカウントを+1する(C[l][h] += 1のイメージ)。
もしカウントが $m$ になったなら(C[l][h] == m)それを $l$ 番目の集合の候補点として追加する。
今回のサンプルを選択したバイナリツリーから次に近い点を探索し、同じように $P_l$ に追加する

上記を $k_1$ 回繰り返す。

所感

結構計算が多いように感じるけど内積とってスカラ値にするからそんなにきつくはないのかな？
実際に大規模データで試したわけじゃないのでどれくらいの速度なのかちょっとわからない。
ランダム単位ベクトルが唯一の確率的な要素かな？
$k_1$ のサイズは少々気になる。 $k_1 \geq m$ の制約はありそう？