ロバスト推定 教師なしクラスタリング モデルパラメータ推定 外れ値（アウトライア）除去 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 ✝ xA 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 ✝ ✝ xA 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 ✝ ✝ xA 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 nF – 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
© Copyright 2025 ExpyDoc
