こんにちは。レトリバのリサーチャーの木村@big_wingです。

今回はNeurIPS2022で発表されたSignRFF: Sign Random Fourier Featuresを紹介します。

論文の概要
Sign Random Fourier Features
- Random Fourier Features
- 近似近傍探索とSign Random Fourier Features
Ranking Efficiency: 異なるLocality Sensitive Hashingの比較のための指標
実験
- 様々なパラメータ設定でのRanking Efficiency
- 実データにおける実験
まとめ

論文の概要

紹介する論文は私が以前のブログで紹介したRandom Fourier Featuresに関連する論文です。本論文では近似最近傍探索（Approximate Nearest Neighbor search; ANN search）への応用を見据え、Random Fourier Featuresを用いたバイナリコード生成手法を提案しています。

本論文の貢献は以下の通りです。

Random Fourier Featuresに基づくバイナリコード生成手法であるSign Random Fourier Features (SignRFF)を提案し、この手法がlocality-sensitiveの性質を持つことを示した。
異なる Locality Sensitive Hashing (LSH)手法の性能を比較するための指標としてRanking Efficiencyを新たに提案した。

これらについて順に紹介していきたいと思います。また本ブログ中の図は紹介論文から引用しています。

Sign Random Fourier Features

Random Fourier Features

最初にRandom Fourier Features (RFF)について簡単に振り返ります。RFFはもともとShift-invariantなクラスのカーネル関数を近似するための手法として提案されました¹。この論文では特にガウスカーネルを対象としています。今、各データ点は $\mathbb{R}^{d}$ 上の点とし、このうちの2点を $\boldsymbol{x, y}$ とします。以下簡単のため各データ点は $| \boldsymbol{x} | = | \boldsymbol{y} | = 1$ と正規化されているものとします。この時コサイン類似度は $\rho = \rm{cos}(\boldsymbol{x},\boldsymbol{y})= \Sigma\it_{i=1}^{d} x_i y_i$ となり、 $\gamma$ をパラメータとするガウスカーネルはコサイン類似度 $\rho$ を用いて

$\begin{align} k(\boldsymbol{x},\boldsymbol{y})=k(\rho)=e^{-\gamma^2 (1-\rho)} \end{align}$

と表現することができます。このガウスカーネルに対してRFFは、

$\begin{align} F(\boldsymbol{x})=\rm{cos}(\boldsymbol{w}^\top \boldsymbol{x} + \tau) \tag{1} \end{align}$

と定義されます。ここで $\boldsymbol{w} \sim \mathcal{N}(\boldsymbol{0},\gamma ^2 \boldsymbol{I}_d)$ 、 $\tau \sim Unif(0,2\pi)$ であり、 $d$ 次元正規分布と一様分布にそれぞれ従います。このように定義したRFFに対し、 $\mathbb{E} \lbrack F(\boldsymbol{x})F(\boldsymbol{y}) \rbrack =k(\boldsymbol{x},\boldsymbol{y})/2$ が成り立ちます。

そのため、ガウスカーネルを $b$ 次元で近似したい場合には $\boldsymbol{w_1}, \ldots , \boldsymbol{w_b} \overset{i.i.d.}{\sim} \mathcal{N}(\boldsymbol{0},\gamma ^2 \boldsymbol{I}_d)$ 、 $\tau_1, \ldots, \tau_b \overset{i.i.d.}\sim Unif(0,2\pi)$ といったように $b$ 個のパラメータをそれぞれサンプリングし、

$\begin{align} F_{b}(\boldsymbol{x}) = \lbrack \rm{cos}(\boldsymbol{w}_{1}^\top \boldsymbol{x} + \tau_{1}), \ldots, \rm{cos}(\boldsymbol{w}_{b}^\top \boldsymbol{x} + \tau_{b}) \rbrack \end{align}$

と各点における特徴量を作成することで近似が実現できます。

近似近傍探索とSign Random Fourier Features

先程説明したRFFで、各点においてガウスカーネルを近似するような特徴量を得ることができました。このままでも十分有用なのですが、近似最近傍探索 (ANN search)を行いたい場合、さらに各点がバイナリコードとして表現されているとより便利です。バイナリコードとして表現することでデータをより省メモリで保持することができ、より高速な検索が可能となります。

さて式(1)のRFFからバイナリコードを得るにはどうすればよいでしょうか？最も素朴なアイディアは、

$\begin{align} h_{sign}(x) = sign(F(\boldsymbol{x}))=sign(\rm{cos}(\boldsymbol{w}^\top \boldsymbol{x} + \tau)) \tag{2} \end{align}$

とRFFの符号によってバイナリ化することです。ここで $sign(x)$ は引数 $x$ が負であれば0、そうでなければ1となる関数です。実際に式(2)が本論文で提案されたSign Random Fourier Features (Sign RFF)です。著者らはこの一見簡単なSign RFFが提案されていなかった理由としてSign RFFの性質の理論的な解析の困難さがあると指摘しています。詳細は割愛しますが、論文中で著者らはSign RFFのlocality-sensitiveな性質を理論解析しています。locality-sensitiveな性質を簡単に述べると、より似ているデータ点のペアはより高い確率で同じバイナリコードとなり、似ていないデータ点のペアは同じバイナリコードとなる確率が低いということです。

Ranking Efficiency: 異なるLocality Sensitive Hashingの比較のための指標

Sign RFFがlocality-sensitiveな性質を持つことは前章で簡単に触れましたが、locality-sensitiveな性質をもつバイナリコードへのHashing手法は他にも多くあります²,³。さて、実際に各LSH手法をデータに適用することなく、各LSHの性能を比較するためにはどうすればよいでしょうか？著者らはこの問いに対してRanking Efficiency (RE)という指標を新たに提案しました。以下REの導出について簡単に紹介します。

今、 $\boldsymbol{x, y}$ をデータ集合上の2点とし、 $\boldsymbol{q}$ をクエリの点とし、 $\boldsymbol{x}$ のほうが $\boldsymbol{y}$ よりクエリ $\boldsymbol{q}$ に真に近いとします。するとlocality-sensitiveな性質からLSHによって生成されるバイナリコードが一致する確率において $p_x > p_y$ が成り立ちます。これらの確率の推定量を、

$\begin{align} \hat{p}_{x} = \frac{1}{b} \Sigma_{i=1}^{b} \mathbb{1} \lbrace h_{i}(\boldsymbol{x})= h_{i}(\boldsymbol{q}) \rbrace, \hat{p}_{y} = \frac{1}{b} \Sigma_{i=1}^{b} \mathbb{1} \lbrace h_{i}(\boldsymbol{y})= h_{i}(\boldsymbol{q}) \rbrace \end{align}$

とします。これら推定量についても同様の $\hat{p_{x}} \gt \hat{p_y}$ の大小関係が成り立っていることが望ましいです。

ここで、

$\begin{align} E_x = \mathbb{E} \lbrack \mathbb{1} \lbrace h(\boldsymbol{x})= h(\boldsymbol{q}) \rbrace \rbrack \\ E_y = \mathbb{E} \lbrack \mathbb{1} \lbrace h(\boldsymbol{y})= h(\boldsymbol{q}) \rbrace \rbrack \\ Cov(\mathbb{1} \lbrace h(\boldsymbol{x})= h(\boldsymbol{q}) \rbrace, \mathbb{1} \lbrace h(\boldsymbol{y})= h(\boldsymbol{q}) \rbrace) = \Sigma = \begin{pmatrix} V_x & V_{xy} \\ V_{xy} & V_y \end{pmatrix} \end{align}$

と平均と分散共分散行列を表すと、 $b \to \infty$ で、中心極限定理から

$\begin{align} \begin{pmatrix} \hat{p}_{x} \\ \hat{p}_{y} \end{pmatrix} \sim \mathcal{N}(\begin{pmatrix} E_{x} \\ E_{y} \end{pmatrix},\Sigma/b) \end{align}$

が得られます。実際は $b= 30$ 程度で十分良い近似となっています。この結果から $b$ がある程度大きい領域における推定量の大小関係の確率について、

$\begin{align} P(\hat{p}_{x} > \hat{p}_{y}) = \Phi \left( \frac{\sqrt{b}(E_{x}-E_{y})}{\sqrt{V_{x}+V_{y}-2V_{xy}}} \right) \end{align}$

が成り立ちます。ここで $\Phi$ は標準正規分布の累積分布関数です。そのため $\Phi$ の内部の引数が大きい値をとるにつれて、この望ましい大小関係が成り立つ確率は大きくなります。著者らはこれに基づいてREを

$\begin{align} RE(\rho,c)= \frac{E-E_{c}}{\sqrt{V+V_{c}}} \end{align}$

と定義して提案しています。ここで $c$ は $0 \leq c \lt 1$ を満たす定数であり、 $E$ と $E_c$ はLSH手法において、それぞれコサイン類似度が $\rho$ と $c\rho$ の場合のハッシュの衝突確率です。また $V=E(1-E), V_c=E_c(1-E_c)$ です。この指標はハッシュ関数、 $\rho$ と $c$ を定めれば事前に計算することができます。

実験

様々なパラメータ設定でのRanking Efficiency

論文では前章で提案したREを様々なLSH手法、パラメータで実験をしています。図1にその結果を示します。SignRFFが提案手法で、KLSH、SQ-RFFが提案手法と同様に非線形なLSH手法となっており、SignRPが線形なLSH手法です。

まず、SignRPを除く非線形なLSH手法間で比較してみると、提案手法のSignRFFが他の非線形手法よりもREの値が大きくなっていることが確認できます。このことからSign RFFは既存の非線形なLSH手法よりも性能が良いことが期待されます。

次に線形なLSH手法であるSignRPとの提案法の比較です。上段の3つの図を見てみると、いずれのコサイン類似度 $\rho \le 0.7$ においても提案法よりSignRPのほうがREの値が大きくなっています。つまり $\rho$ の値が比較的小さい場合、つまりデータセット内の各データがあまり類似していないような状況においては線形のLSH手法であるSignRPのほうが非線形なLSH手法よりも有効であるということが示唆されます。一方で下段の3つの図を見てみるとコサイン類似度 $\rho$ の値が大きくなるにつれて、提案法のREの値が線形のLSH手法であるSignRPを上回る領域が増えています。このとこからデータセット内の各データが非常に類似しているような状況においては、非線形なLSH手法であるSignRFFが線形のSignRPよりも有効であるということが示唆されます。

著者らはこのようにデータセットの性質によって有効なLSH手法が異なり、REを計算するこで有効なLSH手法を事前に知ることができるのではないかということを主張しています。

実データにおける実験

最後に実データにおける実験結果を示します。図2は実験に用いた4つのデータセットにおいて、各データの近傍に含まれるデータとのコサイン類似度の平均を示したものです。図からCIFAR、SIFTはコサイン類似度の平均が大きく、MNISTとCIFAR-VGGはコサイン類似度の平均が小さいことがわかります。前節での実験結果から前者2つのデータセットにおいては非線形なLSH手法が有効で、後者2つにおいては線形なLSH手法が有効であることが期待されます。

実際に各LSH手法によってデータセットをバイナリコード化し、その上で近傍探索を行った結果を図3に示します。予想されたようにコサイン類似度の平均が大きかったCIFAR、SIFTでは非線形なLSH手法である提案手法の結果がよい一方で、コサイン類似度の平均が小さかったMNISTでは線形のLSH手法のほうが結果がよいことがわかります。この結果からLSH選択におけるREの有効性を主張しています。

まとめ

今回はRandom Fourier Featuresに基づいたバイナリコード生成手法であるSign Random Fourier Featuresと異なるLocality Sensitive Hashingの比較のための指標であるRanking Efficiencyを紹介しました。特に後者のRanking Efficiencyを用いることでデータセットごとに適切なLocality Sensitive Hashingを選択しようとする試みは興味深いと思いました。

Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NIPS), pages 1177–1184, Vancouver, Canada, 2007.↩
Maxim Raginsky and Svetlana Lazebnik. Locality-sensitive binary codes from shift-invariant kernels. In Advances in Neural Information Processing Systems (NIPS), pages 1509–1517, Vancouver, Canada, 2009.↩
Brian Kulis and Kristen Grauman. Kernelized locality-sensitive hashing for scalable image search. In proceedings of the IEEE 12th International Conference on Computer Vision (ICCV), pages 2130–2137, Kyoto, Japan, 2009.↩

Retrieva TECH BLOG

Sign Random Fourier Featuresの紹介