Min-max probability machine

Transcript

1. Min-max probability machine @ kingqwert
2. 下準備1(テキトウな) 1. 主問題と双対問題 1. 双対定理 1. 主問題と双対問題のいずれか一方が最適解を持つなら、もう一方も最適解を持ち、主問 題の最小値と双対問題の最大値は一致する。 2. 二次錐計画問題 1. ２次錐 2. Min w’x s.t. Ax=b, x in S
3. 下準備2(テキトウな) 1. マハラノビス距離 1. イメージは簡単：相関構造を加味した正規化した距離 2. 外れ値検出に便利：テコ比との関係（マハラ距離/N-1=テコ比） 1. つまり、まはらがデカイと外れ値である可能性大 2. グラム行列 1. Aをn次正方行列都市、その随伴行列A*とすると、A*A(当然半正値エルミート) 3. カーネルのイメージ 1. 高次元に写像したら一気に道がひらけたぜ！ 2. カーネルトリック使うと、別にφ(x)を定義不要！
4. テコ比 • y_kの係数がテコ比 o y_kが1単位変化するときに、第kサンプルの予測値がどれだけ影響されるか o これがデカければデカイほど、サンプルの変動は予測値に大きい影響与えちゃ う！→外れ値とかの予測へ
5. Min-max問題 • いま、2 つのクラスに属するそれぞれのデータが存在す るとき、そのデータから平均と共分散行列を推定するこ とは可能。 • しかし、そのデータの分布が分かっている状況はレア。 • 分布の分からないデータに対し、与えられた平均と共分 散行列をもつ全ての分布に関して、判別率が最悪となる 場合の分布における誤判別率が最小になるような線形判 別関数を求めることを目的とする問題を、Min-max 問 題と呼ぶ。
6. ミニマックス確率マシン Lanckriet et al. (2002) • 2クラス判別手法 • 線形関数で判別 • 各クラスの平均ベクトルと分散共分散が既知 • 判別の精度：実際の分布形に依存 最悪精度基準 各クラスについて可能なすべての分布形を考えたとき の最悪の場合の誤判別率が最小になるように線形判別 関数を決定
7. 最悪精度基準と最適化 • この問題の何がお得かって。。。。 • すべての分布形を考えたときの確率の上限値を考えるよう な状況は、凸計画法によってうまく扱える！ • つまり、、、、 • ミニマックス確率マシンは、二次錐計画問題という凸計画 問題に帰着でき、効率的に解ける！！！
8. そんなの解くの簡単だよ！ （いや、簡単かどうかは微妙だ が。。） はい、内点法 or simplex method ~
9. Minmaxの設定 ) ( b z a z l T + = 赤：クラス1 (平均, 共分散)= ) , ( 1 1 S µ 0 < +b x aT 0 > +b x aT , 1 Class 0 Þ < +b x aT , 2 Class 0 Þ > +b x aT . 2 Class or 1 Class 0 Þ = +b x aT 青 :クラス2 (平均,共分散)= ) , ( 2 2 S µ 線形判別関数
10. 最悪の誤判別率 0}, Pr{ sup ) , ( ~ 12 1 1 ³ + º S b x aT x µ a クラス1のサンプル の誤判別 率 } 0 { Pr 1 class ³ + Î b x aT x ) , ( 1 1 S µ x 0 < +b x aT 0 > +b x aT , 1 Class 0 Þ < +b x aT , 2 Class 0 Þ > +b x aT . 2 Class or 1 Class 0 Þ = +b x aT 可能な分布形すべてを考え たときの最悪の値 だけでは決まらない。
11. ミニマックス確率マシン • 問題設定 (誤判別確率を最小化したい) • これの推定は厳しくない？ o だって、確率分布わかってないもん • じゃあ、これだわ。これ解いたら終わり。 o sup p()は、期待値µ、分散Σの分布族の上界
12. Marshal and Olkin, 1960 T ⊂ ℜn : convex sup x~(µ,Σ) Pr{x ∈ T} = 1 1+ d2 , where d = inf x∈T ||Σ−1/2 (x − µ) || µ T 確率の上限値は から へのマハラノビス距離に等し い！
13. 幾何学的解釈
14. Lanckriet et al. (2002)の功績 • 距離ってこれで書き直せるんじゃね？ • 証明は、省略。 なる変数変換を施して、ラグランジアンでwを求めるだけ。 （なぜなら、 ）
15. ゴニョゴニョ式変形 • 証明欲しけりゃくれてやる！ • とにかく、これを解けばいいよ。By Marshal and Olkin • これ明らかに２次錐問題。なぜなら
16. ちなみに • 北原ら(2007)はミニマックス確率マシンが多クラスに拡 張でき、この場合も2次錐計画問題に帰着できることを 示した。
17. w導出アルゴリズム • ブロック座標降下法 o ちょっと数学的に難しいので、イメージだけ。 • 行列の要素を逐次的に最適化するアルゴリズム o ある最適化したい行列の(i,j)成分だけ最適化し、その他の部分は定数として扱う。
18. Rの関数とかないよ。 だって、w, b, γ(w)の計算式 出ちゃてるもん ただの最適化問題なので愚直に式変形していくだけ。 それが、mpm-linear.r (146P) あ、でもなんか、mpm-linear-ex.rによるとSVMと それほど変わらない精度を誇ってるっぽいね。
19. 内点法などで、、、 • 求めるべきパラメータは • 最初の2つは判別関数f(x)=w’x-bを求めるのに必要 • 最後のγは(13.5)より、最悪ケースでの誤り率を計算する のに必要
20. Fisher’s classifierとの関係 • 教科書54PよりFisherの超平面はこんな感じ • こっから求めるb1 (p(x|y)~N, y:ラベル,x:データ) • Min-max定理で考えたFisher的判別分析によるb2 (最も 不利な分布での判別関数) • ラベル数がアンバランスな場合 o |b1|≤|b2|ってなるよ！ o b2にはバイアスが入るよね！（だって、バランスな場合を想定＝一番最悪！）
21. Kernelをもちいて • 判別関数(classifier)を非線形へ写像 • カーネル関数をデータベクトルの内積として表現 • f(x)=w’φ(x)はカーネル関数の和で
22. カーネルって怪しくな いッスか？ • 高次元空間上での内積<φ(x),φ(y)>って割と計算無理 ゲー → んじゃ、ある関数ｋ(x,y)で内積がかけたら幸せだよね。 そんな定理有るよ！ • Mercerの定理 o u, v in X の関数 k が内積の形で書ける必要十分条件は • k が対称関数，つまり，k(u, v) = k(v, u) である． • Kが半正定値。つまり、任意の関数ｇに何して、