技術要約：有界ランク1射影を用いたグラスマン多様体カーネル近似のためのランダム特徴量

問題定義

多くの教師あり学習および教師なし学習のタスクにおいて、データクラスやクラスターは、個々のユークリッド点ではなく、高次元空間における低次元部分空間として自然に表現される。これには、グラスマン多様体 $\mathcal{G}(k, n)$（$\mathbb{R}^n$ におけるすべての $k$ 次元部分空間の集合）上での操作が必要となる。カーネルマシン（SVMなど）は、正定値カーネル（射影カーネルやビネ・コーシー・カーネルなど）を用いてこのようなデータ上で効果的に学習できるが、スケーラビリティの問題に直面する。標準的なカーネル法は、$N \times N$ のグラム行列を構築・保持する必要があり、$O(N^2)$ のメモリと計算コストを要するため、大規模なデータセットに対しては実行不可能である。

グラスマン多様体カーネルをランダム特徴量によって近似しようとする既存の試みには、主に2つの制限がある：

1. 高密度なランダム射影： 部分空間を、密なガウス行列への直交射影によって埋め込む手法は、特徴量あたりのストレージと計算に $O(n^2)$ を必要とし、高次元では実用的ではない。
2. 非有界なランク1射影 (ROP)： ROPは、二次形式の測定値 $a^\top P b$ を用いることで計算コストを低減できるが（特徴量あたり $O(kn)$）、重い裾を持つ分布（sub-Weibull分布）を示す。これにより収束率が低下し、グラスマン多様体全体に対して、特徴量数が固有次元に対して線形にスケールするような一様近似の保証を得ることが困難になる。

手法

著者らは、スケーラブルで一様なカーネル近似を実現するために、ランク1射影 (ROP) と 有界な非線形変換 を組み合わせた一連のランダム特徴量マップを提案している。

1. ランク1射影 (ROP)

直交基底 $U$（ここで $P = UU^\top$）によって表される部分空間 $P \in \mathcal{G}(k, n)$ に対して、本手法は $m$ 個の独立したランク1二次形式測定を用いて部分空間をプローブする：
$$\psi_{\text{rop}}(U) = \left( a_i^\top P b_i \right)_{i=1}^m$$
ここで $a_i, b_i \sim \text{i.i.d. } \mathcal{N}(0, I_n)$ である。これにより、特徴量あたりの計算コストは $O(kn)$に削減され、ストレージも$U^\top a_i$および$U^\top b_i$を因子分解することで$O(kn)$ に抑えられる。

2. 有界な非線形変換

重い裾を持つ分布を持つ非有界なROPを制御し、一様収束を確保するために、著者らは $\psi_{\text{rop}}$ を有界な関数 $g(\cdot)$ で合成する：
$$\psi_g(U) = g(\psi_{\text{rop}}(U))$$
分析対象となる2つの具体的な変換は以下の通りである：

• バイナリ特徴量： 正負関数（sign function）を用いる。$g(\lambda) = \text{sign}(\lambda)$。これはバイナリランダム特徴量 $\psi_\pm \in \{\pm 1\}^m$ を生成し、コンパクトな1ビットストレージと高速なビット演算を可能にする。
• 周期的な特徴量： 複素指数関数を用いる。$g(\lambda) = \exp(i\omega \lambda)$。これはランダムフーリエ特徴量に類似した周期的なランダム特徴量 $\psi_\circ$ を生成する。

3. 構造化射影

計算複雑性をさらに削減するために、著者らは密なガウス・プローブ・ベクトルを、高速ウォルシュ・アダマール変換とランダムな対角符号行列の合成に基づく構造化ランダム行列（Choromanskiら, 2016に触発されたもの）に置き換える。これにより、統計的性質を維持したまま、計算複雑性を $O(kmn)$から$O(km \log n)$ へと低減させる。

主な貢献

理論的保証

本論文は、これらの有界なランダム特徴量の経験的内積が、特定の明確に定義された回転不変なグラスマンカーネルの不偏推定量であることを確立している。極めて重要な点として、著者らは、固定された次元 $k$ のすべての部分空間に対して、一様近似境界を証明している。

• サンプル複雑性： 特徴量数 $m = O(kn)$（対数因子を除く）があれば、全部分空間にわたって近似誤差を一様に制御できることを示している。これは、非有界なROPの要求事項である $O((kn)^2)$ に対し、周囲の次元 $n$ および部分空間の次元 $k$ に対して線形にスケールするという大幅な改善である。
• バイナリカーネル ($\kappa_\pm$)： バイナリ特徴量の期待カーネルは、正定値かつ回転不変であることが示されている。一般的な $k$ についての閉形式の表現は存在しないが、以下のように半明示的に特徴付けられる：
  $$\kappa_\pm(U, V) = 1 - \frac{2}{\pi} \mathbb{E}[\angle(P g, Q g)]$$
  ここで $g \sim \mathcal{N}(0, I_n)$ であり、$\angle(\cdot, \cdot)$ はベクトルのなす角である。$k=1$ の場合、閉形式 $(1 - 2\theta/\pi)^2$ が導出される。
• 周期カーネル ($\kappa_\circ$)： 周期的な特徴量の期待カーネルは、主角 $\{\theta_j\}_{j=1}^k$ に依存する閉形式の表現を持つ：
  $$\kappa_\circ(U, V) = \prod_{j=1}^k (1 + \omega^2 \sin^2 \theta_j)^{-1}$$
  著者らは、周波数パラメータ $\omega$ に関する $\kappa_\circ$ の挙動を分析している：
  • 大きな $\omega$： $\kappa_\circ$ は逆ビネ・コーシー・カーネルのように振る舞う（小さな主角に対して敏感である）。
  • 小さな $\omega$： $\kappa_\circ$ は射影Radial Basis Function (RBF) カーネル、$\exp(-\frac{1}{2}\omega^2 \|P-Q\|_F^2)$ を近似する。

計算複雑性

提案手法は大幅な効率向上をもたらす：

• メモリ： 非構造化有界ROPのストレージは、プローブベクトルのために $O(mn)$である。一様近似を保証するために$m = O(kn)$と代入すると、全体のメモリ複雑性は$O(kn^2)$となる（論文内では具体的に$O(\delta^{-2}(kn^2))$と導出されている）。これは、密な射影が$O(mn^2)$のストレージを必要とする（一様近似のために$O(k^3 n^3)$ にスケールする）こととは異なる。
• 計算： 非構造化有界ROPの計算複雑性は $O(kmn)$である。$m = O(kn)$の場合、これは$O(k^2 n^2)$にスケールする。これは、密な射影法に関連する$O(k^2 n^3)$ の複雑さよりも大幅に低い。
• ストレージ： バイナリ特徴量は、部分空間あたり $O(m)$ ビットのストレージしか必要としない。

実験結果

著者らは、合成実験および ETH-80データセット（異なる視点からの視覚的オブジェクト画像）を用いて提案手法を検証している。

1. カーネル近似： 実験により、有界ROPは、密な射影よりも大幅に低い計算コストとメモリコストで、ターゲットとなるカーネルに収束することが確認された。
2. 構造化埋め込み： 構造化されたアダマール・対角スケッチの経験的分析により、$S=3$ ブロックを使用することでガウス分布を近似するのに十分であることが示され、高速変換の使用が正当化された。
3. 分類性能：
   • スーパークラス分類（8クラス）およびオブジェクト分類（80クラス）のタスクにおいて、提案されたランダム特徴量（非構造化および構造化の両方）は、特定のタスクやカーネルに応じたトレードオフはあるものの、厳密なカーネル法と同等の分類精度を達成した。
   • 具体的には、構造化埋め込みにおいて、オーバーサンプリング比 $\rho = m/(nk)$ が 0.05（元の基底サイズのわずか5%）という低い値であっても、高い精度が得られ、厳密なカーネル評価と比較して計算時間を数桁削減できることが示された。例えば、80クラス分類タスクにおいて、構造化手法は総実行時間を厳密な射影カーネルの約52.9秒から約1.9秒へと短縮した。ただし、この高速化に伴い、この特定の条件下では精度が98.75%（厳密）から83.00%（構造化）へと低下するという顕著なトレードオフも観察された。

重要性と主張

本論文は、古典的なグラスマンカーネルに対する実用的かつスケーラブルな代替案を提供すると主張している。ランク1射影と有界な非線形性を組み合わせることで、以下のことが可能であることを示している：

1. グラスマン幾何学を高い精度で復元すること。
2. 固有次元に対して線形にスケールする特徴量数を用いて、多様体全体に対して一様な近似保証を得ること。
3. メモリと計算要件を劇的に削減し、大規模で高次元なアプリケーションにおけるカーネルベースの学習を可能にすること。

本研究は、理論的なカーネル手法と実用的なスケーラビリティの間の溝を埋めるものであり、近似誤差と計算コストのトレードオフを、ランダム特徴量の数と非線形変換の選択を通じて明示的に制御できるフレームワークを提供している。