いろいろ考えてみた

Isomapがうまく次元削減できることは結果から明らかなのだけれど、学部時代に
線形代数や最適化の授業をサボってきた僕にとっては「何故」うまくいくか理解
できなかったので、先生の助けなども借りながら考えてみた。

Isomap自体はこちらで見たらよく分かります。
http://d.hatena.ne.jp/audioswitch/20081004/1223138496

多次元尺度構成法

多次元尺度構成法(MDS: Multi Dimensional Scaling)
多次元尺度構成法 - WikipediaがIsomapの基本的なアイデアになっている。

要は、似たものは近く、似てないものは遠くに配置しようという考え方である。非類似度（似てない具合の尺度）を現在分かっている情報から抽出しようとする。

Centering Matrix

IsomapにはCentering Matrix なるものが出てくる。
解説はこちらに詳しく記載されている
Centering matrix - Wikipedia, the free encyclopedia
が、要はベクトル毎に平均を求め、それを各要素から減じた値を返すという役割を担う。これがCenteringの由来なんでしょうね。

今、Centering Matrixをで行列とし、任意の行列をとすると、は列毎のCenteringを行い、は行毎のCenteringを行う。

IsomapではCentering Matrixをとおき、近傍グラフにおける頂点同士の最適経路を要素に持つ行列の各要素を2乗したものをとおき、とする。
この操作の意味は、最適経路の行列を列毎、行毎にCenteringしたものを乗算することに相当。
今、は頂点同士の最適経路を要素に持つ行列のため、行方向、列方向のCentering結果は同じになる。
また、Centeringの意味を考えると「平均からの距離」になるので、Centeringされたベクトル同士を掛けると、分散・共分散行列（のようなもの）が結果として得られる。
これの固有値・固有ベクトルを求めることで、高次元空間上で分散の大きな軸から順に見つかっていく、みたいな感じでしょうかね。

ま、何か違う気がしなくもない感じですが、今のところはこんな感じだと思っております。