ミニマックス確率マシンとその拡張について

ミニマックス確率マシンと
その拡張について
東京工業大学経営工学専攻
北原知就
水野眞治
中田和秀
第11回情報論的学習理論ワークショップ (IBIS 2008)
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
ミニマックス確率マシン
Lanckriet et al. (2002)
•
•
•
•
2クラス判別手法
線形関数で判別
各クラスの平均ベクトルと分散共分散が既知
判別の精度：実際の分布形に依存
最悪精度基準
各クラスについて可能なすべての分布形を考えた
ときの最悪の場合の誤判別率が最小になるように
線形判別関数を決定
最悪精度基準と最適化
• すべての分布形を考えたときの確率の上限値
を考えるような状況は、凸計画法によってうまく
扱える。
• ミニマックス確率マシンは、二次錐計画問題と
いう凸計画問題に帰着でき、効率的に解ける。
本発表の柱
1．ミニマックス確率マシンを詳説
2．最悪の場合の確率と最適化
→ 凸計画法によって扱える
3．2次、凸判別への拡張
→ 最適な判別関数の一つは線形
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
設定
aT x  b  0
aT x  b  0
赤：クラス1
(平均, 共分散)=
(1 , 1 )
青 :クラス2
(平均,共分散)=
線形判別関数
aT x  b  0
aT x  b  0  Class 1,
aT x  b  0  Class 2,
aT x  b  0  Class 1 or Class 2.
l ( z)  a z  b
T
( 2 ,  2 )
各クラスの最悪の誤判別率
aT x  b  0
aT x  b  0
クラス1のサンプル
x の誤判別率
Prxclass1{a x  b  0}
T
(1 , 1 ) だけでは決まらない。
aT x  b  0
可能な分布形すべてを考え
たときの最悪の値
12
a x  b  0  Class 1,
aT x  b  0  Class 2,
aT x  b  0  Class 1 or Class 2.
T
 sup x~( 1 ,1 ) Pr{a x  b  0},
T
判別関数の最悪の場合の誤判別率
クラス1の誤判別率の上限
12  sup x~(  , ) Pr{a x  b  0},
T
1
1
クラス2の誤判別率の上限
21  sup x~( 
2 , 2 )
Pr{a x  b  0},
T
l ( z)  a z  b の最悪の場合の誤判別率 l
l  max{12 , 21}
T
ミニマックス確率マシンの定式化
minl ( z )aT z b l
最悪の場合の誤判別率を最小化
 min 
s.t sup x ~ ( 1 ,1 ) Pr{a x  b  0}   ,
T
sup x ~ ( 2 , 2 ) Pr{aT x  b  0}  
変数：(a, b), 
データ：(i , i ) (i  1,2)
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
強力な結果
(Marshal and Olkin, 1960)
T   : convex
n
1
sup x ~ (  , ) P r{x  T } 
,
2
1 d
where d  infzT ||  1/ 2 ( z   ) ||
確率の上限値は
 から T へのある種の距離によって決まる。
数値例
1 5 3
2  (0,0), 2   
2 3 5
ｙ
4
3
2 から T
T
μ1
2
1.0
0.8
0.6
1
への距離
d
=1
0.4
0.2
μ2
-3
-2
-1
O
-1
-2
1
2
3
ｘ
確率変数が
の上限値
T
に入る確率
1
1


2
1 d
2
ミニマックス確率マシンとの関連
• 凸領域が半空間の場合、確率の上限値は陽
に書ける。
• このことにより、ミニマックス確率マシンは二
次錐計画問題に帰着される。
• 北原ら(2007)はミニマックス確率マシンが多
クラスに拡張でき、この場合も2次錐計画問
題に帰着できることを示した。
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
Motivations
2次不等式領域(凸とは限らない)についても、Marshal
and Olkinに対応する結果が知られている:
Vandenberghe et al. (2007)
Generalized Chebyshev bounds via semidefinite
programming.
この結果を利用し、ミニマックス確率マシンを2次判別に
拡張可能
計算実験の結果、最適解が常に線形に
ミニマックス判別問題を理論的に解析
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
2次ミニマックス判別
• 2次関数 q( z)  zT Az  2bT z  c
• 凸でなくても良い
xT Ax  2bT x  c  0  Class 1,
xT Ax  2bT x  c  0  Class 2,
xT Ax  2bT x  c  0  Class 1 or Class 2.
q(z ) の最悪の場合の誤判別率  q
 q  max{sup x ~ (  , ) Pr{x Ax  2b x  c  0},
T
1
T
1
sup x ~ ( 2 , 2 ) Pr{xT Ax  2bT x  c  0} }
2次ミニマックス判別の定式化
minq ( z ) zT Az 2bT z c  q
 min 
s.t sup x ~ ( 1 ,1 ) Pr{x Ax  2b x  c  0}   ,
T
T
sup x ~( 2 , 2 ) Pr{x Ax  2b x  c  0}  
T
Variable
( A, b, c), 
data
T
(i , i ) (i  1,2)
半正定値計画問題に帰着可
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
判別の集合による特徴づけ
• 線形、2次判別：ある集合とその外部、境界によって
判別
• 線形判別の場合
S  {z   n | a T z  b  0},
ext( S )  {z   n | a T z  b  0},
bd ( S )  {z   n | a T z  b  0}.
S
を凸集合で置き換える
凸ミニマックス判別
• 開凸集合 S
x  S  Class 1,
x  ext( S )  Class 2,
x  bd ( S )  Class 1 or Class 2.
S の最悪の場合の誤判別率  S
 S  max{sup x ~(  , ) Pr{x  ext( S )  bd ( S )},
1
1
sup x ~ ( 2 , 2 ) Pr{x  S  bd ( S )}
}
凸ミニマックス判別の定式化
minS:open convex  S
 min 
s.t sup x ~ ( 1 ,1 ) P r{x  ext(S )  bd( S )}   ,
sup x ~ (  2 , 2 ) P r{x  cl(S )}  
Variable
Data
S
: open convex set
(i , i ) (i  1,2)
How to solve this problem?
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
問題のまとめと主結果
問題 (最適値)
特徴付け
計算方法
難易度
LMC
1
線形関数
SOCP
易
QMC
2
2次関数
Parametric SDP
CMC
3
やや難?
定理2
開凸集合
?
難?
定理1
定理1, 2:LMCを解きさえすればよい。さらに、
1  2 , 1  3.
CMC はLMCと等価
Theorem 1
a z  b* : LMCの任意の最適解
T
*
H  {z   | a z  b*  0}
n
T
*
CMCの最適解
Also,
1  3.
強力な結果
(Marshal and Olkin, 1960)
T   : convex
n
1
sup x ~ (  , ) P r{x  T } 
,
2
1 d
where d  infzT ||  1/ 2 ( z   ) ||
確率の上限値は
 から T へのある種の距離によって決まる。
数値例
1 5 3
2  (0,0), 2   
2 3 5
ｙ
4
3
2 から T
T
μ1
2
1.0
0.8
0.6
1
への距離
d
=1
0.4
0.2
μ2
-3
-2
-1
O
-1
-2
1
2
3
ｘ
確率変数が
の上限値
T
に入る確率
1
1


2
1 d
2
証明の概略(1)
2
ｙ
2.0
1.5
1.0
0.5
-2.0
-1.5
-1.0
1
-0.5
O
-0.5
-1.0
-1.5
-2.0
S
0.5
S（円内）→クラス1
1.0
1.5
2.0
ｘ
円の外部→クラス2
境界はどちらでも可
証明の概略(2)
2
ｙ
ｙ
2 '
2.0
1.5
2.0
1.5
1.0
0.5
-2.0
-1.5
-1.0
-0.5
1.0
S
O
-0.5
-1.0
0.5
0.5
1.0
1.5
2.0
ｘ
-2.0
 2
-1.5
1/ 2
-1.0
-0.5
O
0.5
-0.5
-1.0
-1.5
-1.5
-2.0
-2.0
元の空間
U
変換後の空間
変換後の空間で射影問題を解けばよい。
1.0
1.5
2.0
ｘ
証明の概略 (3)
2
ｙ
ｙ
2 '
2.0
1.5
1.0
0.5
-2.0
-1.5
-1.0
-0.5
2.0
1.5
1.0
S
O
-0.5
-1.0
-1.5
-2.0
元の空間
0.5
1.0
1.5
2.0
ｘ
-2.0

1/ 2
2
-1.5
-1.0
-0.5
0.5
U
O
0.5
-0.5
-1.0
-1.5
-2.0
変換後の空間
1.0
1.5
2.0
ｘ
証明の概略 (4)
2
ｙ
SをHで置き換えても,  2
からの距離は不変。
2.0
1.5
1.0
0.5
-2.0
-1.5
-1.0
-0.5
H
S
O
-0.5
-1.0
0.5
1.0
1.5
2.0
ｘ
クラス2の最悪の場合の
誤判別率は不変
SはHに含まれる。
-1.5
-2.0
クラス1にとってよりよい判別領域
最悪精度の観点からは、半空間Hは Sよりも悪くない
QMCでは凸が最適
命題 2
q( z )  z T Az  2bT z  c : 任意の2次関数
  g ( z ) : 凸2次関数,
(WCM of g ( z ))  (WCM of q( z )).
図形的意味
0
1 0
1   , 1  

0
0
4
 


3
2 1 
2   , 1  

1
1
4
 


ｙ
ｙ
4
4
3
3
2
2
μ2
1
Class 1
Class 2
μ1
-3
-2
-1
O
1
2
3
ｘ

μ2
1
Class 1
Class 2
μ1
-3
-2
-1
O
-1
-1
-2
-2
1
2
3
ｘ
定理2 :最適な2次関数の一つが線形
任意の2次関数 z Az  2b z  c
T


 凸2次関数
線形関数（定理1）
T
目次
発表の概要
ミニマックス確率マシン
最悪の場合の確率と最適化
2つの拡張
(4-a)2次判別
(4-b)凸判別
5. 各判別法の関連
6. まとめ
1.
2.
3.
4.
まとめ
• ミニマックス確率マシン：2つのクラスの平均と
分散共分散行列が与えられているときに、各
クラスに対して可能なすべての分布形を考え
たときの最悪の場合の誤判別率を最小にす
る線形判別法
• 最悪の場合の確率：凸計画法と深い関連
• ミニマックス確率マシンの2つの拡張
2次判別、凸判別
• 拡張した問題の最適解の1つは線形

Download Report