パターン認識特論

パターン認識特論
ADA Boosting
低精度の識別器を組み合わせて
高精度の識別器を作る
出力(識別結果)
識別器1
識別器2
入力(特徴ベクトル)
Boostingとは同じタ
イプの識別器を異
なる学習をさせて結
合する
識別器n
異なるタイプの識別
器を学習をさせて
結合する方法もあ
る
ADA Boostingの利点
• 単純な計算の反復で安定な識別器を作る
ことができる.
• 最適化の特別なアルゴリズムを必要とせ
ず,実装が容易.
• 人物顔検出などに用いることができ,特徴
の「選択」も行える.
歴史的背景
• 1988年 Keans, Valiant :
大量の学習データが与えられているとき、ランダ
ム選択よりも少しましな学習能力を有する識別
器があれば、それらを組み合わせることによって、
任意の高精度識別器が構成できる
• 1989年 Schapire 最初の Boosting アルゴリズム
• 1990年 Freund
改良型 Boosting
• 1995年 Freund and Schapire ADA Boosting
• 1998年 Friedman et al Real AdaBoost
Friedman et al LogitBoost
Friedman et al Gentle ADABoost
• 2000年 Freund BrownBoosting
識別器出力の統合
• 組み合わされた出力 F ( x) は、個々の識
別器の出力 ft ( x)
{-1, 1} の重み付き
和として表される。
T
F ( x)    t f t ( x)
t 1
出力(識別結果)
1 f1 ( x)
2 f 2 ( x)
T fT ( x)
Step1:初期化
以下のデータ分布が与えられているとする.
x1
x2
xn
各点は以下のクラス
ラベル:
yn= +1 ( )
-1 ( )
と重みを持つ:
Dn =1/N
Step1:初期化
• ( x1, y1 ),( x2 , y2 ),...,( xN , yN ) が与えられて
いるとする。但し、yi {1,1} である。
• Di1  1/ N (i  1 N )とする。
このとき、以下のStep2と3を、t=1~Tまで繰
り返す。
Step2:識別器tの学習
0 E  false
I (E)  
1 E  true
N
 t   D I ( yn  ft ( xn ))
n 1
弱識別器が直線の場合
t
n
識別誤差を最小化するように学習
Step3:重みの更新
重み付きエラー
0 E  false
I (E)  
1 E  true
識別器tの重み
データの重み
N
D
n 1
t
n
1
N
 t   D I ( yn  ft ( xn ))
n 1
t
n
1 1 t
 t  log
2  t
t 1
n
D



間違わないほど
 t  0.5 のとき
大きな値になる
0とする。
exp{ t yn ft ( xn )}
D
Zt
t
n
正規化項
間違うほど大
きな値になる
Step3:重みの更新(イメージ図)
誤識別を起こした
データの重みを増
す
学習終了後に得られる識別器
 T

H ( x)  sign  t ht ( x) 
 t 1

出力(識別結果)
f (x)
識別器1
識別器2
入力(特徴ベクトル)
識別器n
続き
続き
続き
最終結果
f1
f2
f4
f3
線形識別面4枚から非線形識別面を作ることができる
例
例
例
例
例
例
ADA Boosting の特性
T
1 N

 T
• 誤識別確率   exp  yi  t ht ( xi )    Zt
N i 1
t 1

 t 1
N
Z t   D exp  t yi ht ( xi ) 
i 1
t
i
学習すればするほど誤りは少なくなる。
T

2
Z t  exp  2  t 

t 1
 t 1 
T
 t  1/ 2   t
しかも、誤識別が減るのが早い。
未知入力に対するリスク
トレーニングサンプルに対する誤りの確率
Pr[H ( x)  y]
 Td 
未知入力に対する誤りのオーダ O

 N 
d: VC dimension


 Td 

P r[H ( x)  y ]  O

N


デモ
• http://www.cs.technion.ac.il/~rani/LocBoost/
Real ADABoost
• Step3の重み更新式が違う
Zt
1
t 
Zt
識別による検出
(クラスモデルとのマッチング)
Cascaded ADABoosting
• ADABoosting で作られた強識別器を多段に
接続する(速度と精度を両立させる工夫)
学習データ
カスケード型識別器
特徴
入力
1
特
徴
量 顔データ
検出に有効か調査顔
非顔
データ
特徴1
強学習
器
T 2 T
No Face
t
T
Face
内積計算の高速化
Integral Image(Viola&Jones)

Integral Imageとは矩形領域内の画素値の総和を画素
値とする画像
ii( x, y) 
(0, 0)
i( x, y)
x x , y y
ii ( x, y ) : integralimage
i ( x, y ) : 画素
(x, y)
s ( x, y ) : 縦の画素の総和
s ( x, y )  s ( x, y  1)  i ( x, y )
ii ( x, y )  ii ( x  1, y )  s ( x, y )
s ( x,1)  0, ii (1, y )  0
Integral Imageを用いた矩形内積分
iiRB-iiRT-iiLB +iiLT
Harr Like特徴
(0, 0)
iiLT
iiLB
iiRT
iiRB
わずか3回の加
減算で,任意の
矩形領域の積分
が行え,顔検出
で用いられる
Harr Like特徴も
高速に計算可能
検出時の位置・大きさ
の変化に対する対処法
• イメージピラミッドの走査