読者です 読者をやめる 読者になる 読者になる

いろいろ考えてみた

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


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

多次元尺度構成法

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


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

Centering Matrix

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


今、Centering MatrixをCn \times n行列とし、任意のn \times n行列をXとすると、 C Xは列毎のCenteringを行い、 X Cは行毎のCenteringを行う。


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


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