ロバスト推定教師なしクラスタリング正しいクラス分類に向けた課題

ロバスト推定
教師なしクラスタリング
モデルパラメータ推定
外れ値（アウトライア）除去
M‐estimator
Least Median Square
K‐means クラスタリング
1
正しいクラス分類に向けた課題
• 前処理
本講義のフォーカス
– ノイズ除去，正規化など
• 特徴量抽出
– ドメイン/タスク依存
• 撮影画像そのもの，エッジや色ヒストグラムなどの特徴量
• 識別空間
– 事例が記録/類似度評価される空間
• 識別器
– 線形/非線形識別
– 最近傍/K近傍識別
– など
2
モデルパラメータ推定
なぜロバスト統計が必要か？
3
直線あてはめの例
• x‐y平面における２点を通る直線の方程式
y
y = 0.5x + 1
(10,6)
(2,2)
x
4
直線あてはめの例
• x‐y平面における２点を通る直線の方程式
y = ax + b
y
y = 0.5x + 1
2 = 2a + b
6 = 10a + b
 2 1 a  2
10 1 b   6

   
(10,6)
(2,2)
x
13
直線あてはめの例
• x‐y平面における２点を通る直線の方程式
 2 1 a  2
10 1 b   6

   
x
A
b
y
y = 0.5x + 1
x  A-1b
 1
1 1
A  
8  10 2 
1
(10,6)
(2,2)
x
14
直線あてはめの例
• x‐y平面における２点を通る直線の方程式
 1 2
a 
1 1
b    8  10 2  6

 
 
0.5
 
1
y
y = 0.5x + 1
(10,6)
(2,2)
x
15
直線あてはめの例
• x‐y平面における3点以上を通る直線の方程式
y
y = 0.5x + 1
(10,6)
(6,4)
(2,2)
x
16
直線あてはめの例
• x‐y平面における3点以上を通る直線の方程式
 2 1
 2
10 1 a   6

 b   
 6 1   4
x
A
b
y
y = 0.5x + 1
(10,6)
(6,4)
(2,2)
x
17
直線あてはめの例
• x‐y平面における3点以上を通る直線の方程式
擬似逆行列
y
A  ( AT A) -1 AT
✝
y = 0.5x + 1
✝
xA b
(10,6)
(6,4)
(2,2)
x
18
直線あてはめの例
• x‐y平面における3点以上を通る直線の方程式
擬似逆行列
A  ( AT A) -1 AT
140 18
T
A A

18
3


1  3  18
T
-1
( A A) 
96  18 140 
0
1  -12 12
✝
A 
96 104  40 32
✝
19
直線あてはめの例
• x‐y平面における3点以上を通る直線の方程式
 2 1
0 
1 0
1  -12 12
✝

AA 
10 1  



0
1
96 104  40 32

 6 1 
20
直線あてはめの例
• x‐y平面における誤差を含む点群を通る直線の方程式
擬似逆行列
y
A  ( AT A) -1 AT
✝
✝
xA b
y = 0.5x + 1
２乗誤差を最小にする
 2
 2 1
10 1 a 6
    

 6 1 b  4
 


 


x
21
直線あてはめの例
• x‐y平面における誤差を含む点群を通る直線の方程式
擬似逆行列
A  ( AT A) -1 AT
y
✝
✝
xA b
外れ値
y = 0.5x + 1
２乗誤差最小の基準で
推定される直線
x
22
クラス分類での例
• 各クラスのモデルパラメータ推定
– 各クラスの点群の分布をガウス分布で近似する
と．．．
外れ値
23
外れ値に頑健な
モデル推定・モデルパラメータ推定
24
ロバスト推定
• M‐estimator
– 外れ値の影響を低減
• Least Median Square 推定（LMedS推定）
– 外れ値を除去
25
M‐estimator
• 評価関数において，外れ値に対する重みを小さくする
• 最小二乗法における，誤差eに対する評価関数
– P0(e)=e2
• M‐estimator における評価関数
– P1(e)= e2
(|e|≦k)
2k|e| - k2 (|e| > k)
– P2(e)=e2 / (k + e2)
P0 (e)
P1 (e)
P2 (e)
e
26
M‐estimatorによるパラメータ推定
• 評価関数P(e)を最小化する最適化問題
• 関数によっては，必ずしも最適解に収束することは保
証できない
– よい初期値が必要になる
P0 (e)
P1 (e)
P2 (e)
e
27
LMedS推定
• 最小２乗（Least Mean Square: LMS）基準
– min  e
• M‐estimator基準
– min  P(e )
• 最小中央値２乗（Least Median Square: LMedS）
基準
2
i
i
i
i
– min medi ei
2
e2
e2
28
LMedS推定の頑健性
• Breakdown point を指標とした頑健性の評価
– Breakdown point では，全サンプルデータ中，外れ
値が何割を超えると，大きくパラメータ推定結果が変
化してしまうかを評価する
• 最小２乗における breakdown point = 0
• LMedS における breakdown point = 0.5
• なぜ最小２乗，LMedS それぞれにおける
breakdown point が 0, 0.5 になるか？
29
LMedSによる
パラメータ推定アルゴリズム
• 多次元データに適用可能なランダムサンプリ
ングによる探索ベースのアルゴリズム
1. 全データからF個のデータをランダムに選ぶ
•
•
このF個のデータ中に外れ値が含まれなければ良い
適切なFの決定法は？
2. F個のデータを用いてモデルのパラメータを推
定する
3. LMedS基準により，推定されたパラメータを評価
する
4. 1,2,3 をq回繰り返し，最良の（LMedSが最小にな
30
る）パラメータを選ぶ
直線あてはめの例
• x‐y平面における誤差を含む点群を通る直線の方程式
y
外れ値
y = 0.5x + 1
外れ値
２乗誤差最小の基準で
推定される直線
x
31
LMedSにおける
ランダムサンプリングの回数
• q回のランダムサンプリング中，少なくとも１回
のサンプル集合には外れ値が全く含まれな
い確率Pを考える
– 全データ中の外れ値の割合をε とする
– P = 1 – (1 – (1 – ε)F)q
– 例えば，ε=0.3, F=0.3 のとき，P=0.01 を保証する
ためには，サンプリング回数q=11となる
32
LMedSによる外れ値除去
• 前述のアルゴリズムによって，外れ値を除い
たパラメータ推定が可能
• しかし，パラメータ推定時に用いられるサンプ
ルデータ数Fは，全データ中の外れ値以外の
データ数よりも小さい可能性が高い
• 全データ中から全外れ値を除去して残るデー
タをすべて利用してパラメータ推定 → より
最小２乗的に優れたパラメータ推定
33
LMedSによる外れ値除去
• LMedSにより推定された誤差がeiのとき，誤差
の標準偏差は
5 

– ˆ
2
  C 1 
med ei
 nF 
– C=1.4826により，誤差を正規分布に一致させる
• たとえば，2.5ˆ よりも大きな誤差|ei|を持つサ
ンプルデータを外れ値として除去する
• 残った全サンプルーデータから最小２乗基準
でパラメータを推定する
34
ロバスト推定のまとめ
• モデルパラメータ推定時，外れ値の悪影響は
大きい
• ロバスト推定は，外れ値に対して頑健なパラ
メータ推定法
– M‐estimator
– LMedS推定
35
教師なしクラスタリング
K‐means クラスタリング
36
教師あり学習によるパターン認識
37
教師なし学習によるパターン認識
38
教師なし学習によるパターン認識
39
K‐means クラスタリング
• 教師なし（すなわち，学習サンプルのクラスが
未知）の状態で，全学習データをK個の塊（ク
ラスタ）に分割する
• 学習サンプルにクラスを与えることができな
い/難しい問題において有効
– Unsupervised learning
– Semi‐supervise learning
– Weakly‐supervised learning
40
K‐means クラスタリング
‐ アルゴリズム ‐
• Step 1
– 特徴空間中に，各クラスタを代表するk個のプロトタイプの初期値
p1,p2,…,pkを与える
• Step 2
– 各学習サンプルiに対して，プロトタイプp1,p2,…,pkとの距離を計算し，
距離最短のプロトタイプが属するクラスタにサンプルiを割り当てる
• Step 3
– 各クラスタにおいて，割り当てられたサンプルの平均を求め，その平
均を新しいプロトタイプとする
• Step 4
– Step 2 において所属クラスタが変化した学習サンプルがなければ，ク
ラスタリング終了する
41
K‐means の問題点と解決法
• k‐means クラスタリングの問題点
– クラスタ数kを事前に与える必要あり
• どうやってkを決定する？
• 赤池情報量基準（AIC）ですべてのkにおけるクラスタリ
ング結果を評価
– 初期値に依存する
• 複数の初期値集合を利用してk‐means クラスタリング
を実施し，もっとも誤差eの小さい結果を選択する
∈
ωiはクラスタiに属する学習サンプル集合
42
まとめ
• ロバスト統計
– 外れ値の悪影響を排除する
• 教師なしクラスタリング
– 学習サンプルのクラスが未知の際のアプローチ
43

Download Report