DATA 森 亮太 デザイン科学クラスタ 60040116 2003.11.15.

Presentation on theme: "DATA 森 亮太 デザイン科学クラスタ 60040116 2003.11.15."— Presentation transcript:

1 DATA 森 亮太 デザイン科学クラスタ

2 Contents Abstract(要約) Data Compression (データ圧縮) Coordinate Systems(座標系)
Eigenvalues and Eigenvectors(固有値と固有ベクトル) Eigenvalues of Positive Matrices(正則行列の固有値) Random Vectors(ランダムベクトル) Normal Distribution(正規分布) Eigenvalues and Eigenvectors of the Covariance Matrix(共分散行列の固有値と固有ベクトル) High-Dimensional Spaces(高次元空間) Clustering(クラスタリング)

3 Abstract(要約) この章は、連続した状態空間を表すためにベクトルの使用を紹介する
そのような状態空間のサイズを減少させるのは自然な計算にとって主要である ベクトル状態空間のサイズを減少させる1つの方法は空間の次元数を変えることである もう１つの方法はプロトタイプポイントに換算してデータをまとめることである

4 Data Compression(データ圧縮)(1)
学習の大半はまさしく人類における固有の組織から引き起こされなければならない そのような組織は我々のセンサーの出力に反映される この出力は幾何学的かつ代数的な性質をもつ一組の離散的な測定値としてごく一般的に記述されることができる。 そのような性質の最も簡単な収集は線形空間を定義する 本章の焦点はそのような測定値の状態空間での構造を検出するために最も基本的な手法を述べることである その主眼は線形空間の基本的な性質を開発することと、データポイントの収集をコード化するのにどうそれらが使われることができるかを示すことである

5 Data Compression(2) 問題 解 小さい集合の次元を選択というアプローチのため非常に簡単で的確なテクニック
網膜の出力端での視覚の状態空間を考慮するけれども、それは約100万の独立した測定値がある これらは100万次元の空間に記録されることができる →データが膨大、そこで・・・ 解 非常に小さい次元空間で表現 小さい集合の次元を選択というアプローチのため非常に簡単で的確なテクニック 固有ベクトルを利用する手法(主成分分析) クラスタリングの手法

6 主成分分析とクラスタ化概要(1) 2つの主な分類、固有ベクトル(主成分分析)とクラスタリング
(a)固有ベクトル方向はデータのほとんどの変分方向に沿って指す。例ではこのテクニックはポイントpをただ１つの座標と小さい残差として符号化されるように許容する (b)クラスタリングは近いポイントグループをコード化するのにプロトタイプポイントを使用。例では、プロトタイプの座標はポイントpに関してより小さい残差とともに送られる。節約されたものは、ポイントのグループに同じプロトタイプを使用することができるので当然の結果として生ずる この章の焦点はこれらのテクニックを記述することである

7 主成分分析とクラスタリング概要(2) 図4.1 数量的データを圧縮するための技術における2つの主な分類
(a)固有ベクトル直線をそのデータ上の最大変化の直線にそって指し示す。たとえば、この技術はたった１つの座標と小さい残差として符号化されるようにそのポイントpを許容する (b)クラスタ化は近くのポイントのグループを符号化するためにプロトタイプポイントを使う。例えば、そのプロトタイプの座標はポイントpに対するより小さい残差を伴いながらあたえれる。その同じプロトタイプがポイントのグループのために使われているため、取り込むことが結果として生ずる。

8 Data Compression(3) 主成分分析 固有空間はより高次元空間から低次元空間までの変化が線形であると仮定
それらの技術はデータにおける最大変化を保つ変換を指定するということである 変化の方向は固有ベクトル方向 その方向に沿った変化量は固有値 固有ベクトル方向は一般的な座標系を莫大な有用性を持つ状態空間を構成する

9 Data Compression(4) クラスタリング よりわずかな数のプロトタイプポイントに換算してデータポイントの分布をまとめる。
これらのプロトタイプを計算する系統立った方法はプロトタイプポイントの数を推測し、それらのそれぞれの確率分布の記述を調整するのにデータを使用すること 調整を実行する非常に一般的な方法は期待最大化と呼ばれる。

10 Coordinate Systems(座標系)(1)
ベクトルによって行列をかけ算することはy=Axとなる行列積の特別な場合 上式は としてかくことができる またA列の線形結合として変換すると

11 Coordinate Systems(2) ベクトルをつかう際、それらが直交座標系に関して説明されると暗黙的に仮定 →実際の同格のベクトルについて議論しない しかし、一般的な場合ではデータに関して右の座標系は直交していないかもしれない この点についてベクトルaiが座標系または多次元空間の基底として特別な解釈をもつということが大事 例えば、３次元上における基礎でa1,a2,a3はy=a1y1+a2y2+a3y3として関わるようにyを許容する

12 Coordinate Systems(3) 座標系の基本となる重要性質はそれらがお互いに比例して説明可能であるということ
例えば、yは基底ベクトルaiに換算して説明可能

13 しかし、右の行列は３つ目の成分を説明しない
Coordinate Systems(4) この基礎はi≠jのようなすべてのiとjにおいてaj･ai=0に対して直交している しかし、非直交基底もまた動作すると判明 例えば、(係数はもちろん異なっているだろうが)左の行列Aはまだ表現されるようにyを許容するだろう。 しかし、右の行列は３つ目の成分を説明しない すべてのiについてxi =0なら

14 Coordinate Systems(5) n次元行列の列が空間にかからないとき、何が起こるか?
行列の次元は線形独立ベクトルの数と等しい。(それは、行列の階数[ランク]として知られている)。階数rが次元N以下であるときに、ベクトルはr次元の副空間にかかる

15 Coordinate Systems(6) 行列には最大階数以下があるのが望ましい
例えば、方程式Ax=0には非自明な解(xが0以外の解を持つ)があるように、Aの列は線形従属でなければならない Ax=0は前の方程式の書き直されたバージョン 列が線形独立であるなら、方程式を満たすことができる唯一の方法はすべてのiについてxi=0を持つこと しかし、非自明な解のために、xiは0であるべきではない →列は線形従属でなければならない。 例えば、すべての面に3つのベクトルがあるとき、3次元上で線形従属

16 Coordinate Systems(7) 対照的に独自の解をもつ方程式Ax=cにおいてｘが唯一の解をもつためにはAは線形独立でなくてはならない 下図のベクトルcは列ajの線形結合に換算して表されなければならない。 一般に列はcの空間に含まれなければならない。 →ベクトルcと共にそれら(a1とa2)は線形従属である

17 図4.2 (a)：Aの列はもし3つ列ベクトルが同一平面上にないなら、3つの次元において線形独立である
(b)：Ax=cの場合、ベクトルcはAによって補われた空間になければならない。ゆえに2つの次元において、a1とa2とcとはすべて同一平面上になければならない(線形従属)

18 Coordinate Systems(8) ニューラル・ネットワーク上でy=Wx形式の座標変換を実行することができる
この手続きが行われる方法はまず線形神経回路要素を定義することである 基本的要素には、重みまたは非常に簡単な「シナプス」をもつ (代わりに行列のためのWの使用は、要素がシナプスのモデルであること) 各重みはそのそれぞれの入力値で増える ニューラル・ネットワーク上で別々のユニットは出力ベクトルの異なった成分を表している

19 図4.3 基本行列積は線形座標で使用 線形座標では変換を線形ニューラルネットワークで実行可能

20 Eigenvalues and Eigenvectors (固有値と固有ベクトル)(1)
ベクトルが行列によって掛けられるとき、結果のベクトルの大きさと方向が原型と異なる しかし、どのような行列にもベクトル方向があるので、行列積はベクトルの大きさだけを変える 特別な方向に関しては行列積はスカラー倍に減少する。 例

21 Eigenvalues and Eigenvectors(2)
ベクトルvがこれらの方向の１つを指し示すなら、λであるWv=kvがスカラーとなる vは固有ベクトル、λは固有値 任意のnでn×nマトリクスの固有値を見つけるのはニューメリカルレシピを参照 簡単な2次元の場合を例

22 方程式に解があるためには、行列の列が線形従属でなければならない
|W| = 0. ゆえに(3-λ)(2-λ)-2=0となり、λ1 = 4、λ2 = 1 λ1 = 4を方程式に代入すると ここで、v1=1,v2=1を代入する

23 Eigenvalues and Eigenvectors(3)
行列の唯一の非零要素が対角線上にある別の行列に行列変換すること さらに、これらの対角要素は固有値である 新しい基底でのスカラー倍へ古い基底における行列積を換算すること →ベクトルをもう1つの集合に表している基底ベクトルを変える 問題は局所基底が変えられるとき、変換に関して何が起こるのかということである

24 Eigenvalues and Eigenvectors(5)
座標変換はx*=Axとy*=Ayによって与えられるということを仮定 y=Wxと与えられたとすると W*に関してy*=W*x* WとW*の関係はx = A-1x*, y = Wx, y* = Ay 変形をまとめるとy*=AWA-1x* W*=AWA-1 このように関係づけられる行列を相似という

25 Eigenvalues and Eigenvectors(6)
固有ベクトルを基底としたと仮定 Wの固有ベクトルyiに関してWyi=λyi 固有ベクトルを横に並べた行列をΥとするとWY=YΛ Λは唯一の非零成分が対角要素λiの行列 両辺にY-1をかけるとY-1WY=Λ この方程式が意味することは 行列Wが与えられたとき、変換が唯一の非零要素を基底の固有ベクトルの座標に変形することによって対角線である行列のものに簡素化することが可能

26 Eigenvalues and Eigenvectors(7)
例 yが以下のy式に与えられるようにxとして特定のベクトルを選択 x* = Υ-1x, y* = Υ-1y これからそのy*=Λx*の値も算出できる

27 y*=Λx*の値

28 Eigenvalues and Eigenvectors(8)
固有値と固有ベクトルの多くの役立つ性質 1. 固有値行列Aはどんな直交変換のもとでも不変である。 2. そのすべての固有値が正であるなら、行列Aは正と定義する。 3. Aのトレースは、そのすべての固有値の合計であり、どんな直交変換のもとでも不変である。 4. Amのトレースは、そのすべての固有値の合計であり、どんな直交変換のもとでも不変である。 5. Aの行列式は、そのすべての固有値の積と等しく、どんな直交変換の下でも不変である。

29 Eigenvalues and Eigenvectors(9)
Eigenvalues of Positive Matrices(1) A>0であるときに、Frobenius-Perron定理

30 Eigenvalues and Eigen vectors(10)
Eigenvalues of Positive Matrices(2) Frobenius-Perron定理 A>0であるなら、λ0>0とx0>0となるような以下の1,2,3が存在する 1 2 他のAの固有値 3 は唯一のものである

31 Eigenvalues and Eigenvectors(11)
Eigenvalues of Positive Matrices(3) Frobenius-Perron定理 この定理もまたA≧0であるときの場合に拡張することができるが、An>0のようなnが存在する この場合すべての定理の結論はAに適用する

32 Eigenvalues and Eigenvectors(12)
Eigenvalues of Positive Matrices(4) Frobenius-Perron定理 固有ベクトルを以下の式のように正規化 Ax0=λ0x0なので

33 Frobenius-Perron定理 すべて足しあわせると ただし、 ゆえにλ0は以下の範囲で制限される

34 Random Vectors(ランダムベクトル)(1)
行列がデータベクトルの集合上で変分によって定義される ベクトルは自然な変分を全体として得る何らかのランダム分布から得られる ランダムベクトルXは確率密度関数p(X)によって指定される。正式には以下の式となる ただし、

35 Random Vectors(2) ランダムベクトルは密度関数によって完全に特徴付けられるが、そのような機能は決定するのはしばしば難しいか、または使用するために数学的に複雑 より少ないパラメータで記述することができる関数で分布をモデリング 最も重要なパラメータは、平均ベクトルと共分散行列である

36 Random Vectors(3) 平均ベクトルと共分散行列が以下の式によって定義される

37 Random Vectors(4) とおくと、 平均ベクトルは、

38 共分散行列は、

39 Random Vectors(5) 特定のP(X)から抽出される任意の集合のランダムデータベクトルを考慮
集合の座標軸に関して、それらの軸に映し出されると、データはある変分を示す データが何らかの方法で凝集されたと仮定すると 意志決定で使用することができる自然類を定義するとき、そのようなかたまりはすべて重要である場合がある かたまりをもっともわかりやすくするために座標を選択 これらの座標方向が共分散行列の固有ベクトルである その上、最も重要な方向(最も多くの変分があるもの)は、大きい固有値を持っていることによって明らかにされる

40 図4.4 変化を最大にする座標選択は意思決定を簡素化することができる
上図は2つの自然類について明確に考察できるように2つのモードである固有値方向に沿った分布における固有ベクトル方向結果 下図は他の方向をおそらく上図のような構造を明らかにしそうであるが、わかりにくい

41 Random Vectors(6) Normal Distribution(正規分布)
第3章であったように、最も役に立つパラメトリック分布の1つは正規分布である 大部分の観測された確率変数がいくつかの確率成分の合計である傾向がある 確率成分の合計は通常分布される傾向がある 以下の式は正規分布のベクトルバージョンである

42 Random Vectors(7) Eigenvalues and Eigenvectors of the Covariance Matrix (1) 正規分布の記述する際、分布の記述を簡素化する座標の選択 特に、分布の変化を最大にする座標を選択→分布の分散が最大となるような基底ベクトル 最初に、以下の式のような新しいランダムベクトルZを選ぶことによって、Xを原点に変換 ゆえに２次式は となる

43 今ZTZとd2(Z,0,∑)が最大にされるようにZを見つける このための明確な条件は以下の式(4.1)である。
ゆえに２次式は となることから 言い換えれば、Zは固有値λがある共分散行列の固有ベクトルである。(次章を参照)

44 Random Vectors(4) Eigenvalues and Eigenvectors of the Covariance Matrix (2) 以下の通り主要な結果をまとめることができる ΦがΣの固有値nのn×n行列にする。すなわち、 そして、(4.1)より Λは固有値の対角行列 固有値の大きさがそれに対応する固有ベクトル方向の分散の大きさに対応する →固有値の大きな固有ベクトルをm(m<n)個とればよい近似となる

45 の証明

46 Random Vectors(4) Eigenvalues and Eigenvectors of the Covariance Matrix (3) Φはあらゆる正規直交変換である制約条件から始まることによって同様の結果に達することができると判明

47 Random Vectors(4) Eigenvalues and Eigenvectors of the Covariance Matrix (4) m<nであれば、誤差の最小量がある変化に近似するように、最大固有値mに関連する固有ベクトルを選択 平均2乗誤差は残っている固有値n-mの合計を示す

48 Random Vectors(4) Eigenvalues and Eigenvectors of the Covariance Matrix (4) Example: A Network That Encodes Data より早くどんな行列操作も線形ニューラルネットワークで実現される どのようなネットワークがデータを符号することができるのかを示す例(図4.5)

49 図4.5 コード化のための固有ベクトル変換の使用 (a)ネットワークで共分散行列が実現されることができる。
(b)同様に、3つのネットワーク操作の継承として同じ変換を実現されることができる。 →固有値が小さい結合を消すことで少ない次元での近似が可能 もっとも小さい固有値に対応する含有成分をおとすことができるに従って,この定式化はデータがコード化されるのを(いくつかの誤差ともないながら)許容する。 図4.5Aに示されているように、共分散行列はネットワーク操作に換算して表現されることができる。 しかし∑による掛け算は　　　　　　よる掛け算と等しい、同等のネットワークは図4.5B示されるように図のような3つの操作をもつとういうことをつくられることができる

50 High-Dimensional Spaces(1)
非常に大きい空間を想定(たとえば、256×256) 共分散行列∑が非現実的に大きくなる→より小さいランクの行列で近似 n次元データベクトルXがM個存在 たいていの変分は次元が空間の次元よりもより少ない副空間にデータを投影することによってとらえることが可能

51 High-Dimensional Spaces(2)
もし、vがATAの固有ベクトルであるならそのときAvはΣの固有ベクトルである より小さいシステムは固有値がはるかに大きいシステムのものと同じ。また、この固有値は∑の固有値と等しく大きいほうからM個の固有値が得られる。だからｖを求めてAを左からかければ∑の固有ベクトルが得られる

52 High-Dimensional Spaces(3)
例：顔認識 複数のイメージに対するベクトルを主成分分析した場合、大きな固有値に対する固有ベクトル(固有顔)はあるパターンを示す 顔の画像はN×Nの明るさの配列のデータとして扱われる。M個の例を与える タスク：新しく与えられた顔画像がどの画像と一番近いかを出力すること

53 High-Dimensional Spaces(4)
顔画像の主成分得点を計算 訓練集合を とおいて 平均は 平均を引き算することで訓練集合を変換する Mの固有ベクトルukと固有値λk を求めていく

54 High-Dimensional Spaces(5)
より大きい固有ベクトルuk(固有顔)はvkを使うことによって、組み立て可能 (4.2)より7つの固有ベクトル

55 High-Dimensional Spaces(6)
固有ベクトル空間 固有ベクトル空間における新しいイメージの座標を計算[新しいデータに対して主成分得点を計算] ユークリッドノルムが最小となる顔画像を探す[下式が最小となる分類kを選択する]

56 Clustering(1) データ圧縮の2番目の手法
標本がプロトタイプベクトル空間に分布し、これらの幾つかの主要なパターン群に分割することをクラスタリングという 正規分布を当てはめるとすれば、 分散 平均

57 Clustering(2) 2つ以上の内部状態(k=1,2)を表すのは少し困難だが、第2章のとおりで似たようにすればよい

58 Clustering(3) ガウス分布で表現できると仮定すると

59 Clustering(4) ベイズの規則を使用しながら内部状態でデータ標本を見る確率を書くことができる
結果としてもしデータを与えられていてそれが特定の状態からきた確率(どちらの状態であるかの確率)を見積もりたいなら次式のベイズの規則を使用することができる この方程式は同様にあらかじめ特定の仮説がたてられている場合平均として許容する

60 Clustering(5) 現在、サンプルが独自に作りだされるならすべてのデータを見る確率は以下のようになる 最尤法

61 Clustering(6) それぞれの内部状態のためのパラメータを選ぶには、以下の式に与えられる対数尤度関数を最大にすることによって最尤推定を使用 これらの方程式はデータ点に換算したmkとσkの表現として解決することができる

62 Clustering(7) 推定を実行するための一般的な方法 期待最大で状態推定のアルゴリズム mkとσのために推定値でモデルを初期化する
モデルパラメータが一点に集まるまで以下を実行する: 1. 方程式(4.4)によると、確率的に内部状態を選ぶ。そして、順番に方程式(4.4)は方程式(4.3)を使用する。 2. 状態が見積もられるので方程式(4.5)を使用することによって、そのパラメータをアップデートする。