グラム（カーネル）行列の固有値分解で対応する特徴ベクトルを得る

類似度を設計するのと，特徴ベクトルを設計するのはどちらが難しいだろうか？とりあえず今は類似度を設計する方が簡単だとしよう．そしてその類似度が正定値カーネルになるように設計し，$k$としよう：

- http://ibisforest.org/index.php?正定値カーネル

n個のデータ$\{x_i\}_{i=1}^n$を持っているとしよう．大事なのは$x$はなんでもいいってこと．文字列でも，木でも画像でも動画でも．ただ，類似度を設計すれば良い（この類似度を学ぶ枠組みもある）．データとカーネルから，グラム行列（カーネル行列とも言われる）$K, \ K_{ij}=k(x_i,x_j)$を構成しよう．この段階で使える機械学習アルゴリズムは多々ある．例えばSVM，ロジスティック回帰，その他諸々．しかし，$K \in \mathbb{R}^{n \times n}$であり，nが大きくなると，すなわちデータが膨大な量だとこのまま使うのは計算量的にもメモリ的にも厳しい．

そこで，$K$の固有値分解$K=USU^T$を考えよう．なお，これらは固有値の大きい順にソートされているとする．そして，$\Phi=US^{\frac{1}{2}}$としよう．そうすると，$K=\Phi\Phi^T$となり，なんとこれが最初に設計した類似度に対応する特徴ベクトル（を縦並べたもの）になっている．さらに，$K$はしばしばlow-rankであり，$S$の対角成分の多くは0である．そこで，$S$の固有値が0でないm個の成分だけ使おう．そうすると$\Phi \in \mathbb{R}^{n \times m}$となり低次元表現を得る．依然として$K=\Phi\Phi^T$である．

ここで$m$をコントロールすることで，$K$の近似表現を得ることができると気づく．これである程度の近似性能を保ちながら，次元を削減することができる．ゲットした特徴ベクトルは，クラスタリングに投げたりできる．

しかしながら，大きな大きな問題がある．それはサンプルに入ってない新しい点が来たときにどうするか？ということ．そう，このままでは分類や回帰に使えない．これを今後調べていく．何かやり方をご存知だったら教えてください．