文献情報
タイトル: Neural Nearest Neighbors Networks
著者: Tobias Plötz Stefan Roth
概要
NeurIPS2018の論文．特徴抽出→$k$-NNを求める部分を微分可能にする方法についての研究．1つだけを選ぶcross-entropyを拡張してk個を選ぶようにしたい．従来も確率的な$k$近傍計算方法は存在したが，$k$個のサンプルは1番近いものから順にサイコロを振って1個選ぶ，という操作を繰り返していた．しかし，このような方法では結局一つだけ選ぶために誤差の伝搬が進みにくい．提案手法では学習の過程では$j$番目の要素を1つだけ選ぶ代わりに，各サンプルの期待値を重みとした重み付き和$\sum \bar{w}_i^jx_i$により近傍点を合成して学習する．理論的な裏付けとしては，cross-entropyの温度パラメタ$t$が0に近づくような「極限分布」においては，これも結局1つ選ぶのと同じになるため，$k$-NNを学習できる．
なぜこの論文のメモを残した？
数式の定義が一部曖昧で読みにくかったためメモを残す．基本的に論文の解説というよりは論文の補完程度のメモ．なお，ここに他の方の論文紹介などもある．
論文を読むときに理解しにくいポイント
数式(5)においては，$w_i^j$は$i$番目のサンプルが$j$番目の近傍点であったかどうかを表している．ただ，この$w_i^j$は論文中で明確に定義されていないため，数式が厳密に理解できない．おそらく，これは$\rm{Cat}(w^j|\alpha^j,t)$という分布（$w^j$は各サンプルが$j$番目の近傍点である期待値）に従ってサイコロを振ってランダムに一つだけ選んで得られたone-hot-vectorのことだと思う（違うと思う人はコメントをくれると泣いて喜びます）．
おそらく，提案手法に相当する式(8)-式(10)が従来の確率的$k$近傍計算の純粋な連続値緩和になっていることを示すため，式(5)-式(6)をこのような書き方にしているのだと思う．素直な気持ちで式(8)-式(10)を読むと混乱しなくてすむ．ポイントは，1個のサンプルを選びながら学習するのではなく，$k$個のサンプルの重み付き和を近傍点と思って学習する部分にある．この点で，本質的にGumbel softmaxなどで離散化しながら探索をするのとは異なるアプローチになっている．
なお，図1も正直自分にはかなりわかりにくいが，おそらく，ここの(1,0,0)とか(0,1,0)とかは$j$番目の近傍点となる尤度のようなものを表していて，(b)は決定論的．(c)はサイコロで決めるものの，サイコロふった後は特定のサンプルが$j$近傍と信じてやる，(d)は重み付きなので一個を決定しない，といったことを言いたいのだと思う（ここも図を正しい解釈できる人からのコメントがあると嬉しい）．