論文紹介 “Data Spectroscopy: Learning mixture models using eigenspaces of convolution operators” (ICML 2008) ─ by Tao Shi, Mikhail Belkin, and Bin Yu IBM東京基礎研究所.

Presentation on theme: "論文紹介 “Data Spectroscopy: Learning mixture models using eigenspaces of convolution operators” (ICML 2008) ─ by Tao Shi, Mikhail Belkin, and Bin Yu IBM東京基礎研究所."— Presentation transcript:

1 論文紹介 “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勉強会

2 論文の概要 解きたい問題: 多峰性のある分布の密度推定 どうやってそれをやるか “Spectroscpy （分光学）” ときた
具体的には、混合正規分布のパラメター推定 混合数、各クラスタの平均ベクトルと共分散行列 どうやってそれをやるか ガウシアン・カーネルの行列の固有値分解を行う 固有値、固有ベクトルを、上記のパラメターと結びつけることができる “Spectroscpy （分光学）” ときた | 2008/09/12 | T-PRIMAL勉強会

3 何が面白い（と思った）か ガウシアンカーネルの難しげな解析解が世の中に役に立つ現場を目撃できる
カーネル行列の固有ベクトルについての新たな理解が得られる EM推定の初期値を決める際の一手法として役に立つかもしれない 1次元、N=1000、ふたつの山に不釣合いあり k-means (k=2) よりはずっと推定精度がよい 混合重み、平均、分散の見積もり | 2008/09/12 | T-PRIMAL勉強会

4 目次 まずは分布が1次元の単一正規分布の時 次に分布がd次元の単一正規分布の時 一般の混合分布の時 実験的評価
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 | 2008/09/12 | T-PRIMAL勉強会

5 目次 まずは分布が1次元の単一正規分布の時 次に分布がd次元の単一正規分布の時 一般の混合分布の時 実験的評価
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 | 2008/09/12 | T-PRIMAL勉強会

6 1次元ガウシアン・カーネルと、その固有関数の定義
Kの固有関数の定義 測度 p(x)dx の下での固有方程式 | 2008/09/12 | T-PRIMAL勉強会

7 1次元ガウシアン・カーネルの固有値と固有関数は解析的に知られている
固有関数の解析的な形 もし測度 p が 単一の正規分布 N(x | μ, σ2) ならば、i = 0, 1, 2, … に対し 定数a, b, c も、σとωの関数として解析的に与えられる（本文参照） 固有値の解析的な形 に対して エルミート多項式 正規分布 σ: 正規分布の幅 ω: カーネルの幅 | 2008/09/12 | T-PRIMAL勉強会

8 何らかの方法で固有値がわかれば、σは逆算可能
固有値の表式（再掲） カーネルの幅ωが与えられた時、σを推定することができる ただし、固有値がわかっているという前提。 λ0とλ1を使えば、 ではどうやって固有値を求めるのか σ: 正規分布の幅 ω: カーネルの幅 ただし | 2008/09/12 | T-PRIMAL勉強会

9 経験分布を使えば、関数の固有方程式は行列の固有方程式になる
関数についての固有方程式の定義 経験分布を入れる 固有方程式をデータ点 y = x(m) で評価することで、結局、行列の固有方程式になる ただし | 2008/09/12 | T-PRIMAL勉強会

10 固有ベクトルがわかれば、μも計算可能 最上位の固有関数は、正規分布 p(x) を若干修正したものと一致する
0次のエルミート多項式は H0 = 1 であるため したがって、最上位の固有ベクトルにおいて、山を探せばμがわかる μ ≒ x(s) ただし s: 最大値を与えるインデックス なお、Kは正値行列なので、固有ベクトルの成分はすべて正 Perron-Frobeniusの定理 | 2008/09/12 | T-PRIMAL勉強会

11 ここまでのまとめ pとして経験分布を使いさえすれば、データから固有値と固有関数を計算することが可能
これはデータがどういう分布に従っていようとも可能 特に、もし、データが1次元の単一正規分布に従っていると信じられる理由があるなら、 最上位の2つの1固有値の比から分散σを計算できる 最上位の固有ベクトルの成分をスキャンすることで、平均μを計算できる | 2008/09/12 | T-PRIMAL勉強会

12 目次 まずは分布が1次元の単一正規分布の時 次に分布がd次元の単一正規分布の時 一般の混合分布の時 実験的評価
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 | 2008/09/12 | T-PRIMAL勉強会

13 p(x)がd個の独立な分布の積になっていれば、d個の独立な問題を解けばいい
この時は、固有関数もまた各部分の直積で表される d 個の独立な1次元の固有値問題を解けばいい d 個の独立な1次元の固有値問題を解けばいい | 2008/09/12 | T-PRIMAL勉強会

14 d次元のそれぞれが独立でなくても、平均ベクトルμの推定は容易
多次元でも、empiricalバージョンの固有方程式は変わらない 独立でなくても、「xがμの時に密度関数が最大値をとる」という事実は変わらない Kの最上位の固有ベクトルv0の「山」を探せば、その位置がμの推定値 μ≒ x(s) ただしsは、 v0 (x(s)) が最大になるようなインデックス ただし | 2008/09/12 | T-PRIMAL勉強会

15 Σの推定は、求められた d+1個の固有ベクトルから、線形回帰を介して行える
共分散行列Σは未知だが、とりあえず次のスペクトル分解を仮定する {ui}で張られる空間で考えると、固有関数はd個の独立な1次元問題の直積となる {ui}は未知であるが、この基底の下での固有ベクトル（≒固有関数）なら求められる なぜなら、この空間で考えてもカーネル行列はもとと同じだから （∵ 回転不変性） 最上位の固有ベクトルv0と、その次のd個の固有ベクトルw1 , w2 , …, wdを求める 正確にはwjは、「その第n成分がx(n)にほぼ比例しているような固有ベクトル」 1次のエルミート多項式H1(x)がxの線形関数であることを用いると、基底 {ui} を線形回帰で求めることができる Algorithm 2 参照 | 2008/09/12 | T-PRIMAL勉強会

16 目次 まずは分布が1次元の単一正規分布の時 次に分布がd次元の単一正規分布の時 一般の混合分布の時 実験的評価
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 | 2008/09/12 | T-PRIMAL勉強会

17 それぞれの山がある程度離れていれば、個々の山について問題を解けばよい
固有ベクトルを求めると、勝手に分離してくれる | 2008/09/12 | T-PRIMAL勉強会

18 ただし、「山の分離が十分」という仮定が必要
山の分離が十分でない時は？ → どういう方法を使うにせよ、どうしようもない “there does not exist a computationally feasible method for estimating parameters of a mixture distribution in several dimensions without a separation assumption.” | 2008/09/12 | T-PRIMAL勉強会

19 目次 まずは分布が1次元の単一正規分布の時 次に分布がd次元の単一正規分布の時 一般の混合分布の時 実験的評価
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 | 2008/09/12 | T-PRIMAL勉強会

20 実験1: 人工的に作った5次元、3混合正規分布 山の分離がこの程度でもパラメター推定は一応正確
カーネルの幅ωは0.1と手で決める。 N=3000、データ生成→推定を50回繰り返す （残りの3つの次元はノイズ） | 2008/09/12 | T-PRIMAL勉強会

21 実験2: USPS手書き数字のクラスタリングへの応用 それなりに正確にクラスタリングできている
実験条件 N=1866、d=256（16×16ピクセル） 「3」が658個、「4」が652、「5」が556 カーネルの幅ω=2 実験方法 Kの固有ベクトルのうち、すべての要素が同符号のものを上位から3つ選ぶ 各固有ベクトルはクラスターに対応しているはずなので、要素をスキャンして、最大の要素を探し、それを山のラベルとする 実験結果 第1、第16、第49番目の固有ベクトルが同符号条件を満たす クラスタリングは結構うまくいっている overall accuracy = 93% 他の手法との比較がないので何ともいえないところもある v1 v16 v49 | 2008/09/12 | T-PRIMAL勉強会

22 おしまい。 | 2008/09/12 | T-PRIMAL勉強会