概要

[[1610.09072]Orthogonal Random Features

• Gauss Kernelに対応するRandom Fourier Features (RFF)は、入力ベクトルにガウス分布からランダムサンプルされた重み行列をかけた後、cosを噛ませる物である。
• 本研究では、この重み行列をガウス分布ではなく、直交行列からサンプリングするOrthogonal Random Features (ORF)と、ORFの近似としてRandom Sign FlippingとWalsh-Hadamard matrixを組み合わせた重みを用いたStructured Orthogonal Random Features (SORF)と提案する。
• ORF, SORFに対して期待値と分散を理論的に評価する。期待値とカーネルの真の値の差はRFFと異なり0ではないが、元空間の次元dが大きくなると0に収束する（実験的にはd>32でok)。また分散はdが十分大きいとRFFよりも小さくなる。
• 実験的にも、ORFとSORFはRFFより近似性能が高く、さらにSORFはRFFより少ない計算量で計算できる。すなわち、SORFはRFFより速くて正確。

感想

• 理論、実験的に優位性が示されている良い論文だった。
• 直感的にも、直交行列を使うと入力の情報がより保たれそうなので、手法の納得感がある。
• 強いて難点を挙げるなら、近似性能は高いが実際に識別に用いた結果がRFFとどっこいどっこいなので、必ずしも近似性能の追求が正義なわけではないのかもしれない。