目次まずは分布が1次元の単一正規分布の時

Tokyo Research Laboratory
論文紹介 “Data Spectroscopy: Learning mixture models
using eigenspaces of convolution operators” (ICML 2008)
─ by Tao Shi, Mikhail Belkin, and Bin Yu
IBM東京基礎研究所
井手剛
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
論文の概要
 解きたい問題: 多峰性のある分布の密度推定

具体的には、混合正規分布のパラメター推定
• 混合数、各クラスタの平均ベクトルと共分散行列
 どうやってそれをやるか


ガウシアン・カーネルの行列の固有値分解を行う
固有値、固有ベクトルを、上記のパラメターと結びつけることができる
 “Spectroscpy （分光学）” ときた
Page 2
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
何が面白い（と思った）か
 ガウシアンカーネルの難しげな解析解が世の中に役に立つ現場を目撃できる
 カーネル行列の固有ベクトルについての新たな理解が得られる
 EM推定の初期値を決める際の一手法として役に立つかもしれない


Page 3
1次元、N=1000、ふたつの山に不釣合いあり
k-means (k=2) よりはずっと推定精度がよい
• 混合重み、平均、分散の見積もり
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
目次
 まずは分布が1次元の単一正規分布の時

Sec. 2. single component in R
 次に分布がd次元の単一正規分布の時

Sec. 3. single component in Rd
 一般の混合分布の時

Sec. 4. Spectroscopic estimation for mixtures of Gaussians
 実験的評価

Page 4
Sec.5. Simulations and experiments
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
目次
 まずは分布が1次元の単一正規分布の時

Sec. 2. single component in R
 次に分布がd次元の単一正規分布の時

Sec. 3. single component in Rd
 一般の混合分布の時

Sec. 4. Spectroscopic estimation for mixtures of Gaussians
 実験的評価

Page 5
Sec.5. Simulations and experiments
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
1次元ガウシアン・カーネルと、その固有関数の定義
 ガウシアン・カーネル

 Kの固有関数の定義

• 測度 p(x)dx の下での固有方程式
Page 6
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
1次元ガウシアン・カーネルの固有値と固有関数は解析的に知られている
 固有関数の解析的な形

もし測度 p が単一の正規分布 N(x | μ, σ2) ならば、i = 0, 1, 2, … に対し
エルミート多項式

定数a, b, c も、σとωの関数として解析的に与えられる（本文参照）
 固有値の解析的な形

Page 7
正規分布
に対して
| 2008/09/12 | T-PRIMAL勉強会
σ: 正規分布の幅
ω: カーネルの幅
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
何らかの方法で固有値がわかれば、σは逆算可能
 固有値の表式（再掲）
σ: 正規分布の幅
ω: カーネルの幅
 カーネルの幅ωが与えられた時、σを推定することができる


ただし、固有値がわかっているという前提。
λ0とλ1を使えば、
ただし
 ではどうやって固有値を求めるのか
Page 8
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
経験分布を使えば、関数の固有方程式は行列の固有方程式になる
 関数についての固有方程式の定義


経験分布を入れる
 固有方程式をデータ点 y = x(m) で評価することで、結局、行列の固有方程式になる
ただし
Page 9
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
固有ベクトルがわかれば、μも計算可能
 最上位の固有関数は、正規分布 p(x) を若干修正したものと一致する

0次のエルミート多項式は H0 = 1 であるため
 したがって、最上位の固有ベクトルにおいて、山を探せばμがわかる


μ ≒ x(s)
• ただし s: 最大値を与えるインデックス
なお、Kは正値行列なので、固有ベクトルの成分はすべて正
• Perron-Frobeniusの定理
Page 10
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
ここまでのまとめ
 pとして経験分布を使いさえすれば、データから固有値と固有関数を計算することが可能

これはデータがどういう分布に従っていようとも可能
 特に、もし、データが1次元の単一正規分布に従っていると信じられる理由があるなら、


最上位の2つの1固有値の比から分散σを計算できる
最上位の固有ベクトルの成分をスキャンすることで、平均μを計算できる
Page 11
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
目次
 まずは分布が1次元の単一正規分布の時

Sec. 2. single component in R
 次に分布がd次元の単一正規分布の時

Sec. 3. single component in Rd
 一般の混合分布の時

Sec. 4. Spectroscopic estimation for mixtures of Gaussians
 実験的評価

Sec.5. Simulations and experiments
Page 12
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
p(x)がd個の独立な分布の積になっていれば、d個の独立な問題を解けばいい
 この時は、固有関数もまた各部分の直積で表される
d 個の独立な1次元の固有値問題を解けばいい
Page 13
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
d次元のそれぞれが独立でなくても、平均ベクトルμの推定は容易
 多次元でも、empiricalバージョンの固有方程式は変わらない
ただし
 独立でなくても、「xがμの時に密度関数が最大値をとる」という事実は変わらない
 Kの最上位の固有ベクトルv0の「山」を探せば、その位置がμの推定値

μ≒ x(s)
• ただしsは、 v0 (x(s)) が最大になるようなインデックス
Page 14
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
Σの推定は、求められた d+1個の固有ベクトルから、線形回帰を介して行える
 共分散行列Σは未知だが、とりあえず次のスペクトル分解を仮定する

{ui}で張られる空間で考えると、固有関数はd個の独立な1次元問題の直積となる
 {ui}は未知であるが、この基底の下での固有ベクトル（≒固有関数）なら求められる


なぜなら、この空間で考えてもカーネル行列はもとと同じだから（∵ 回転不変性）
最上位の固有ベクトルv0と、その次のd個の固有ベクトルw1 , w2 , …, wdを求める
• 正確にはwjは、「その第n成分がx(n)にほぼ比例しているような固有ベクトル」
 1次のエルミート多項式H1(x)がxの線形関数であることを用いると、基底 {ui} を線形回帰
で求めることができる

Algorithm 2 参照
Page 15
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
目次
 まずは分布が1次元の単一正規分布の時

Sec. 2. single component in R
 次に分布がd次元の単一正規分布の時

Sec. 3. single component in Rd
 一般の混合分布の時

Sec. 4. Spectroscopic estimation for mixtures of Gaussians
 実験的評価

Sec.5. Simulations and experiments
Page 16
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
それぞれの山がある程度離れていれば、個々の山について問題を解けばよい
 固有ベクトルを求めると、勝手に分離してくれる
Page 17
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
ただし、「山の分離が十分」という仮定が必要
 山の分離が十分でない時は？ → どういう方法を使うにせよ、どうしようもない

“there does not exist a computationally feasible method for estimating parameters of a
mixture distribution in several dimensions without a separation assumption.”
Page 18
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
目次
 まずは分布が1次元の単一正規分布の時

Sec. 2. single component in R
 次に分布がd次元の単一正規分布の時

Sec. 3. single component in Rd
 一般の混合分布の時

Sec. 4. Spectroscopic estimation for mixtures of Gaussians
 実験的評価

Sec.5. Simulations and experiments
Page 19
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
実験1: 人工的に作った5次元、3混合正規分布
山の分離がこの程度でもパラメター推定は一応正確
 カーネルの幅ωは0.1と手で決める。
 N=3000、データ生成→推定を50回繰り返す
（残りの3つの次元はノイズ）
Page 20
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
実験2: USPS手書き数字のクラスタリングへの応用
それなりに正確にクラスタリングできている
 実験条件


v1
N=1866、d=256（16×16ピクセル）
• 「3」が658個、「4」が652、「5」が556
カーネルの幅ω=2
v16
v49
 実験方法


Kの固有ベクトルのうち、すべての要素が
同符号のものを上位から3つ選ぶ
各固有ベクトルはクラスターに対応している
はずなので、要素をスキャンして、最大の
要素を探し、それを山のラベルとする
 実験結果


第1、第16、第49番目の固有ベクトルが同
符号条件を満たす
クラスタリングは結構うまくいっている
• overall accuracy = 93%
• 他の手法との比較がないので何ともい
えないところもある
Page 21
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
おしまい。
Page 22
| 2008/09/12 | T-PRIMAL勉強会
© Copyright IBM Corporation 2007

Download Report