東京大学工学部 4年生 夏学期 [03-501130]

応用音響学
第4回 (5/ 1)

亀岡弘和
東京大学大学院情報理工学系研究科
システム情報学専攻
kameoka@hil.t.u-tokyo.ac.jp

講義スケジュール
前半（亀岡担当）
 4/08: 第1回
 4/15: 第2回
 4/22: 第3回
 4/29: 休日
 5/01(木): 第4回
 5/06: 休日
 5/13: 第5回
 5/20: 第6回
 5/27: 第7回後半（牧野担当）
 6/03: 第8回
 6/10: 第9回
 6/17: 第10回
 6/24: 第11回
 7/01: 第12回
 7/08: 第13回
 7/15: 第14回

 7/22: 学期末試験

講義資料と成績評価
講義資料
http://hil.t.u-tokyo.ac.jp/~kameoka/aa/
成績評価
 出席点 学期末試験
本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリングのおさらい k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

k-meansクラスタリング
データの教師なしクラスタリングの一手法

k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定

k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定(Step 2)
クラスタ代表値を決定

k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定(Step 2)
クラスタ代表値を決定

k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定(Step 2)
クラスタ代表値を決定

k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定(Step 2)
クラスタ代表値を決定

k-meansクラスタリング
データの教師なしクラスタリングの一手法(Step 0)
クラスタ代表値を初期設定(Step 1)
クラスタ境界を決定(Step 2)
クラスタ代表値を決定

k-meansクラスタリング
アルゴリズムの収束性


クラスタリングの目的関数
散らばり：クラスタ代表値：各データの帰属クラスタ

反復アルゴリズム(Step 1)

⇒明らかに(Step 2)⇒目的関数は当然単調減少する→収束性が保証されるを解くとクラスタ重心本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

k-meansクラスタリングの生成モデルとしての解釈
K個のクラスタ（塊）からなるデータの生成プロセスを確率モデルで表現できないか？
 クラスタリング問題はその逆プロセス

k-meansクラスタリングの生成モデルとしての解釈
K個のクラスタ（塊）からなるデータの生成プロセスを確率モデルで表現できないか？
 クラスタリング問題はその逆プロセス
生成プロセスの例
 K個の正規分布をランダムに生成
 サンプルごとに正規分布のクラス番号をランダムに選択
 選択されたクラス番号の正規分布に従ってサンプル値を生成

生成された全サンプルが観測データ！

k-meansクラスタリングの生成モデルとしての解釈
K個のクラスタ（塊）からなるデータの生成プロセスを確率モデルで表現できないか？
 クラスタリング問題はその逆プロセス
生成プロセスの例
 K個の正規分布をランダムに生成
 サンプルごとに正規分布のクラス番号をランダムに選択
 選択されたクラス番号の正規分布に従ってサンプル値を生成


生成された全サンプルが観測データ！
データの確率的な生成プロセスの仮定⇔データの確率モデル化
本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

最尤推定
データから、尤度関数が最大となる確率モデルのパラメータを推定するための一般的な枠組 尤度関数とは？
データを ，パラメータを とすると，尤度関数はのこと
 「データの生成源として，パラメータ の確率モデルがどの程度尤もらしいか」を意味した規準




最尤推定




最も尤もらしい、データの生成源を推定すること

クラスタリング問題の例では・・・
観測データ

確率モデル

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

混合正規分布モデル (Gaussian Mixture Model; GMM)
混合正規分布モデルによるデータの生成プロセス
K個の正規分布をランダムに生成
 サンプルごとに

正規分布のクラス番号をランダムに選択
 選択されたクラス番号の正規分布に従ってサンプル値を生成


生成された全サンプルが観測データ
生成モデルfor：k番目の正規分布が選ばれる確率
確率

for

1 234

K

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

EMアルゴリズム
GMMパラメータの最尤推定
GMMのパラメータ：
 求めたいのは尤度関数の導出
生成モデル

対数をとっても最大化の目標は変わらない

EMアルゴリズム
を最大化する




を求めたい

しかし解析的には求められない！
ちなみに， が既知であれば（各データにクラスラベルが付与されていれば），各正規分布パラメータの最尤推定は解析的に求められる⇒平均，分散，データの各クラスへの帰属率を求めるだけ解析的な求解を困難にしているのはにおけるlogの中のsummationのように尤度関数に姿を現さない変数のことを「潜在変数」または「隠れ変数」という

補助関数法補助関数法を局所最小化するためのテクニック
を満たすを補助関数と定義
 反復アルゴリズム
目的関数

[1]
[2]


収束性

補助関数

目的関数

[1]
[2]

Jensenの不等式
Jensenの不等式


：凸関数



例えば，の場合：右辺左辺

EMアルゴリズム
対数尤度の下限関数対数関数が凹関数であることに注意してJensenの不等式を適用は補助関数！の

EMアルゴリズム
対数尤度と補助関数の関係：
反復アルゴリズムによる局所最大化
対数尤度

補助関数

[2] Θの更新[1] λの更新

EMアルゴリズム
対数尤度と補助関数の関係：
反復アルゴリズムによる局所最大化
対数尤度

補助関数

[2] Θの更新[1] λの更新

なぜEMアルゴリズムと呼ばれるか
λの更新式

データ がクラス の正規分布から生成された（事後）確率補助関数
観測データと潜在変数のペア⇒「完全データ」と呼ぶ

よって、は「完全データに対する対数尤度」の期待値に相当本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

本日の話題確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係

k-meansクラスタリングとの関係
k-meansアルゴリズム
(Step 1)

(Step 2)

EMアルゴリズムによる
GMMパラメータの最尤推定
(E-Step)

(M-step)後者が前者と等価となる条件：
Eステップにおけるデータのクラス分けが排他的になる

本日の講義のまとめ
確率モデル（生成モデル）によるパターン認識（クラスタリング）問題の定式化
 k-meansクラスタリング
 k-meansクラスタリングの生成モデルとしての解釈 最尤推定 混合正規分布モデル (Gaussian Mixture Model; GMM)
 EMアルゴリズム


補助関数とJensen不等式

EMアルゴリズムによるGMMパラメータの最尤推定とk-meansアルゴリズムの関係