第２回IPABセミナー

2012年2月17日

確率的パターン認識とクラスタリングの新手法

東京工業大学 計算工学専攻
杉山 将概要2

本講演では，講演者のグループで最近開発した確率的パターン認識とクラスタリングの新手法を紹介する．
確率的パターン認識は，パターンxがクラスyに属する確率p(y|x)を推定し，この確率を最大するクラスyにパターンxを割り当てるパターン認識法である．確率的パターン認識の代表的な手法は（カーネル）ロジスティック回帰であるが，非線形最適化問題を準ニュートン法などで解く必要があるため，大規模なデータに適用するのが困難であった．そこで我々は，最適解が解析的に求められる手法「最小二乗確率的分類器(LSPC)」を提案した[1]．LSPCは，カーネルロジスティック回帰と同等の認識精度を維持しつつ，数百～千倍高速に学習できることを実験的に示す．
クラスタリングの目的は，似たパターンに同じクラスラベルを，似ていないパターンに異なるクラスラベルを割り当てることである．これまでに，様々なクラスタリング手法が提案されてきたが，アルゴリズムの適切な初期化が困難であったり，カーネル幅や近傍数などのパラメータの決定が困難であるという問題があった．そこで我々は，初期値に依存せず解析的に解を求められるクラスタリング法「二乗損失相互情報量クラスタリング(SMIC)」を提案する共に，カーネル幅や近傍数などのパラメータを客観的に決定するための規準「最小二乗相互情報量(LSMI)」を提案した[2]．提案手法の有効性を計算機実験により示す．
[1] Sugiyama, M.
Superfast-trainable multi-class probabilistic classifier by least-squares posterior fitting.
IEICE Transactions on Information and Systems, vol.E93-D, no.10, pp.2690-2701, 2010.
http://sugiyama-www.cs.titech.ac.jp/~sugi/2010/LSPC.pdf[2] Sugiyama, M., Yamada, M., Kimura, M., & Hachiya, H.
On information-maximization clustering: tuning parameter selection and analytic solution.
International Conference on Machine Learning (ICML2011), pp.65-72, 2011.
http://sugiyama-www.cs.titech.ac.jp/~sugi/2011/ICML2011a.pdf

本発表の構成
1. 確率的パターン認識
条件付き確率推定B) 提案手法
C) 高速化の理由
D) 実験A)

2. クラスタリング

3

決定的パターン認識の標準手法：
サポートベクトルマシン
訓練標本から，マージンを最大にする決定境界を求める
クラス１

クラス２

決定境界

テストパターン

テストパターンの属するクラスを予測

4

確率的パターン認識
応用場面によっては，予測したクラスの信頼度を知りたいことがあるテストパターン が属するクラス を予測するだけでなく，その確率も求める
確率が最大のクラスにテストパターンを分類

確率が低いときは「棄却」という選択肢を選ぶこともできる（応用上は重要！）

5

確率的パターン認識の標準手法：
カーネルロジスティック回帰（KLR）
多クラスカーネルロジスティックモデル：（罰則付き）最尤推定により学習：

6学習アルゴリズム

7サポートベクトルマシン（決定的分類）

ロジスティック回帰（確率的分類）

非線形高速

低速

線形で入力が疎

超高速

超高速

超高速に学習できる非線形確率的分類器を紹介する

本発表の構成
1. 確率的パターン認識
条件付き確率推定B) 提案手法
C) 高速化の理由
D) 実験A)

2. クラスタリング

8

定式化
パターン：
クラス：
訓練標本：パターンとクラスの組

方針：条件付き確率を密度比の形で推定する

Sugiyama, Suzuki & Kanamori,Density Ratio Estimationin Machine Learning,Cambridge University Press, 20129

条件付き確率のカーネル最小二乗推定
モデル：

クラス のパラメータの学習規準：

10二乗損失の分解

1項目：のに関する期待値
2項目：のに関する期待値
3項目：定数なので無視期待値は標本平均で近似できる
密度推定不要11

最小二乗確率的分類器(LSPC)

12

Sugiyama (IEICE-ED 2010)

期待値を標本平均で近似し， -正則化項を加える：

解は解析的に計算できる：
を出力とするカーネルリッジ学習と等価本発表の構成
1. 確率的パターン認識
条件付き確率推定B) 提案手法
C) 高速化の理由
D) 実験A)

2. クラスタリング

13

KLRの学習の困難さ
正規化定数の計算が煩雑:は全クラスのパラメータを含む：
 正規化なしでは尤度が無限大に発散：最適化を高速化するための良い「構造」がない

14

なぜLSPCは速いか？

15

LSPCは正規化定数を含まない：

 LSPCは正規化なしでも一致性を持つ（実用上は事後に正規化をしても良い） 各クラス別々に学習できる：

単純なカーネル最小二乗の定式化のおかげで，解が解析的に求められる！

LSPCのパラメータの非負性学習したパラメータがある．

16は負の値を取る可能性

 非負拘束を加えても良いが，解を解析的に求められなくなる（二次計画問題を数値的に解く必要がある）

単純に負の出力を０に切り上げることにする：

LSPCの更なる高速化

17

カーネルを対象クラスの標本のみに配置する：
 対象クラスの標本がある場所は事後確率が大きい それ以外では事後確率はゼロに近い： クラスの標本数

本発表の構成
1. 確率的パターン認識
条件付き確率推定B) 提案手法
C) 高速化の理由
D) 実験A)

2. クラスタリング

18

実験結果

19

画像からの一般物体認識
Pascal VOC(AUC)

オーディオタグ付け
Freesound (AUC)

LSPCは速くて高精度！

確率的パターン認識のまとめ
KLR:対数線形モデルの最尤推定
 正規化項の計算が煩雑 最適化を高速化するための良い「構造」がない

LSPC:線形モデルの最小二乗推定
 正規化が不要⇒クラスごとに学習できる

 解が解析的に計算できる

http://sugiyama-www.cs.titech.ac.jp/~sugi/software/LSPC/

関連研究：
 マルチタスク，マルチラベル，転移学習への拡張
 条件付き確率密度推定

 顔画像からの年齢認証への応用

20本発表の構成
1. 確率的パターン認識
2. クラスタリング
従来法の紹介
提案法A)
B)
i.
ii.

C)

クラスタリング
チューニングパラメータの自動選択実験

21

クラスタリングラベルなし標本
クラスタラベル22にを付与する：

 似た標本は同じクラスタに割り当てる 似ていない標本は違うクラスタに割り当てる

本研究では，クラスタ数 は既知と仮定する

本発表の構成
1. 確率的パターン認識
2. クラスタリング
従来法の紹介
提案法

A)
B)
i.
ii.

C)

クラスタリング
チューニングパラメータの自動選択

実験

23

モデルに基づくクラスタリング24

 混合モデルを最尤推定やベイズ推定で学習

K平均法 (MacQueen, 1967) ディリクレ過程混合法 (Ferguson, 1973) 利点と欠点：
 チューニングパラメータがない クラスタの形状があらかじめ定めたモデル（≒ガウシアン）で決まってしまう アルゴリズムの初期化が困難

モデルなしクラスタリング

25

クラスタの形状に関して仮定を置かない：
スペクトルクラスタリング：非線形次元削減を行った
あとにK平均法を適用する(Shi & Malik, 2000; Ng et al., 2002)

識別的クラスタリング：識別器とクラスタラベルを同時に学習する(Xu et al., 2005; Bach & Harchaoui, 2008)



従属性最大化クラスタリング：標本との従属性が最大になるようにクラスタラベルを決定する(Song et al., 2007; Faivishevsky & Goldberger, 2010)

情報量最大化クラスタリング：情報量が最大になるように識別器を学習(Agakov & Barberu, 2006; Gomes et al., 2010)モデルなしクラスタリング
 利点と欠点：
 クラスタの形状が柔軟 カーネル・類似度のパラメータの決定が困難
 アルゴリズムの初期化が困難

26

本発表の構成
1. 確率的パターン認識
2. クラスタリング
従来法の紹介
提案法A)
B)
i.
ii.

C)

クラスタリングチューニングパラメータの自動選択実験

27

本研究の目的
新たな情報量最大化クラスタリング法を提案する：
 最適解が解析的に求められる チューニングパラメータを客観的に決定できる

提案法の流れ：
情報量を最大にするようにノンパラメトリック・カーネル分類器を学習する
 情報量を最大にするようにチューニングパラメータを決定する
28

二乗損失相互情報量（SMI）

29

情報量の尺度として，SMIを用いる：

 通常の相互情報量はカルバック・ライブラー（KL）

ダイバージェンス
 SMIはピアソン（PE）ダイバージェンス KLもPEも，f-ダイバージェンスというクラスに属する（即ち，似た性質を有する）
 実際，通常の相互情報量と同様に，SMIは

本発表の構成
1. 確率的パターン認識
2. クラスタリング
従来法の紹介
提案法A)
B)
i.
ii.

C)

クラスタリング
チューニングパラメータの自動選択実験

30

カーネル確率的分類器
カーネル確率的分類器：

SMIが最大になるように分類器を学習する：

ただし，ラベルなしデータ与えられない！

しか31

32

SMIの近似クラスタ事後確率をカーネルモデルで近似：
期待値を標本平均で近似：
クラスタ事前確率は一様と仮定：: クラスタ数

これらにより，次のSMIの推定量が得られる：

SMI推定量の最大化

が正規直交だという仮定のもと，大域的最適解はカーネル行列 の主成分によって与えられる
 Cf. Ding & He (ICML2004)

33

34

SMIに基づくクラスタリング（SMIC）
事後処理：
 主成分の符号を定める：：要素が全て１のベクトルに基づいて正規化
 負の出力をゼロに切り上げる 最終的な解（解析的に計算可能）：：ベクトルの第 要素：要素が全て０のベクトル本発表の構成
1. 確率的パターン認識
2. クラスタリング
従来法の紹介
提案法

A)
B)
i.
ii.

C)

クラスタリング
チューニングパラメータの自動選択実験

35

チューニングパラメータの決定

36

SMICの解はカーネル関数に依存する
SMIを最大にするようにカーネルを決める
クラスタリングに用いたを使えば良い？

しかし，はSMIの教師なし推定量のため，精度が良くないチューニングパラメータの決定の段階ではクラスタラベルの推定値が得られているため，SMIの教師付き推定が可能！

SMIの教師付き推定37

最小二乗相互情報量（LSMI）：
 密度比を直接推定する

Suzuki & Sugiyama(AISTATS2010)※各確率密度は推定しない
 密度比推定は密度推定よりも優しい（Vapnikの原理）
各密度がわかる

密度比がわかる密度比の直接推定

38

カーネル密度比モデル：：カーネル関数（実験ではガウスカーネルを用いる）

最小二乗推定：密度比の直接推定
期待値を標本平均で近似し，正則化する：

大域的最適解が解析的に計算できる：

カーネル関数と正則化パラメータはクロスバリデーションで決定できる

39

最小二乗相互情報量（LSMI）

40

SMIの推定量が解析的に計算できる：

LSMIは優れた理論的収束特性を有する！
Suzuki & Sugiyama (AISTATS2010)

LSMIを最大にするように，SMICのカーネル関数を決定する

提案法のまとめ41

SMIクラスタリング＋LSMIによるモデル選択：

LSMI

 出力：

ラベルなし標本カーネルの候補
クラスタラベル

SMIC

 入力：

本発表の構成
1. 確率的パターン認識
2. クラスタリング
従来法の紹介
提案法A)
B)
i.
ii.

C)

クラスタリング
チューニングパラメータの自動選択

実験

42

実験設定

43

局所スケールカーネルのスパース版を用いる(Zelnik-Manor & Perona, NIPS2004): -th neighbor ofチューニングパラメータするように決定する

は，LSMIを最大に

SMICの実行例

44

提案法により自然なクラスタリング結果が得られた

性能比較

45

(MacQueen, 1967)
KM：K平均法
SC：自動調整スペクトルクラスタリング(Zelnik-Manor & Perona, NIPS2004)

MNN：平均最近傍近似に基づく従属性最大化
クラスタリング(Faivishevsky & Goldberger, ICML2010)

MIC：ロジスティックモデルを用いた情報量最大化クラスタリング＋最尤相互情報量に基づくモデル選択(Gomes, Krause & Perona, NIPS2010)(Suzuki, Sugiyama, Sese & Kanamori, FSDM2008)

the squared bracket, computation time for the entire procedure including modelselection is described.

実験結果

ARI
Time

Digit (d = 256; n = 5000; and c = 10)
KM
SC
MNN
MIC
0.42(0.01) 0.24(0.02)
0.44(0.03) 0.63(0.08)
835.9
973.3
318.5
84.4[3631.7]

SMIC
0.63(0.05)
14.4[359.5]

ARI
Time

Face (d = 4096; n = 100; and c = 10)
KM
SCMNN
MIC
0.60(0.11) 0.62(0.11) 0.47(0.10) 0.64(0.12)
93.3
2.1
1.0
1.4[30.8]

SMIC
0.65(0.11)
0.0[19.3]

Document (d = 50; n = 700; and c = 7)
KM
SCMNN
MIC
0.00(0.00) 0.09(0.02)
0.09(0.02)
0.01(0.02)
77.8
9.7
6.4
3.4[530.5]

SMIC
0.19(0.03)
0.3[115.3]

ARI
Time

Word (d = 50; n = 300; and c = 3)
KM
SCMNN
MIC
0.04(0.05) 0.02(0.01)
0.02(0.02)
0.04(0.04)
6.5
5.9
2.2
1.0[369.6]

SMIC
0.08(0.05)
0.2[203.9]

ARI
Time

Accelerometry (d = 5; n = 300; and c = 3)
KM
SCMNN
MIC
0.49(0.04) 0.58(0.14) 0.71(0.05) 0.57(0.23)
0.4
3.3
1.9
0.8[410.6]

SMIC
0.68(0.12)
0.2[92.6]

ARI
Time

Speech (d = 50; n = 400; and c = 2)
KM
SC
MNN
MIC
0.00(0.00) 0.00(0.00)
0.04(0.15) 0.18(0.16)
0.9
4.2
1.8
0.7[413.4]

SMIC
0.21(0.25)
0.3[179.7]

20News
Group

ARI
Time
Sens
eval2

46

Adjusted Rand
index (ARI)：
大きい方が良い赤：1%のt検定で最適か最適タイ
SMICは精度が良く，計算速度も速い！

クラスタリングのまとめ

47従来のクラスタリング法の欠点：
 アルゴリズムの初期化が困難 チューニングパラメータの初期化が困難

SMIC：二乗損失相互情報量（SMI）に基づく新たな情報量最大化クラスタリング法
 大域的最適解が解析的に求められる チューニングパラメータを客観的に決定できる

http://sugiyama-www.cs.titech.ac.jp/~sugi/software/SMIC/