情報学習理論渡辺澄夫東京工業大学教師あり学習の枠組み学習データ X1, X2, …, Xn Y1, Y2, …, Yn q(x,y) f(x,w) テストデータ情報源 X Y 学習モデル誤差と学習学習誤差 n E(w) = (1/n) Σ (Yi-f(Xi,w))2 i=1 ◎ 汎化誤差を小さくすること、すなわち予測を正確にすることが学習の目的である。 ○ 学習誤差が小さいことが汎化誤差が小さいことを意味するわけではない。 ○ 汎化誤差は予測してみなければわからない。汎化誤差を小さくする方法を求めて様々な工夫がなされてきた。サポートベクトルマシン(SVM) カテゴリ識別の問題 (xi,yi) i =1,2,…,n N xi ∈ R yi ＝ 1 or –1 カテゴリに対応 SVM2 1 φ N x∈R H φ(x)∈R sgn(t) = 1 (t≧0) -1 (ｔ<0) y = sgn(w・φ(x)+b) w, b, φ(x) をどのように決めるか？ -1 y SVM3 H R マージンを最大にする w b を選ぶことにする y=w・φ(x)+b (1) なぜマージンを最大化するのか (2) マージンを最大化するにはどうしたらよいか SVM4 H R 条件 yi (w・φ(xi)+b) >0 (i=1,2,..,n) のもとで | w・φ(xi)+b | Margin= Min i=1,2,…,n を最大にする ||w|| 点φ(xi)から平面 w・v+b=0 までの距離 SVM5 Marigin は w, b を定数倍しても変わらないので Min | w・φ(xi)+b | = 1 と仮定してよい条件 yi (w・φ(xi)+b) ≧1 (i=1,2,..,n) のもとで 1 Margin= ||w|| を最大にする ⇔ ||w||を最小にする SVM6 最適化問題Ａ条件 yi (w・φ(xi)+b) ≧1 (i=1,2,..,n) のもとで 2 ||w|| を最小にする複数の１次不等式で定義された凸集合の中で２次式を最小にする問題高次元空間上なので直接解くことは難しいが、効率的な近似最適化法が研究されている問1 2 R y 1 (a,1) 赤い点 (a,1) が a≧0 を動くとき、マージンを最大にする直線 px +qy =1 について p, q をa で表せ。 1 x O px + qy =1 SVM7 Kuhn-Tackerの定理から、双対問題と等価になる双対問題Ｂ変数 a1,a2,…,an に関する最大化問題条件 ai≧0 かつ Σ aiyi=0 のもとで E(a1,a2,…,an) = Σ ai – (1/2) Σ aiajyiyj(φ(xi)・φ(xj)) 双対問題Ｂが解けると、最適化問題Ａの解 (w,b) は w = Σaiyiφ(xi) b = yi - w・φ(xi) (ai>0となるiについて) SVM８サポートベクトル ai はサポートベクトル以外では０。 H R w = Σaiyiφ(xi) b = yi- w・φ(xi) (ai>0) (w,b)はサポートベクトルで定まっている。 SVM９マージン最大化の持つ意味真の分布は不明でありサンプルの出方についてもばらつきがあるが、ともかく、確率 (1-δ) 以上で未知データに対する誤り確率は Pr(err) ≦ (4/n) { Vc(1+log(2n/Vc))- (log δ)/4 } となる Vc≦ min { [D2/Margin2], H } +1 D = max||φ(xi)|| おおよそ「Margin：大⇔Pr(err)：小」マージン最大化は、予測精度を最良にするものではないが、実用上うまく行くことが多いので広く使われている。（注意）双対問題の解き方の例変数 a1,a2,…,an について条件 ai≧0 かつ Σ aiyi=0 のもとで下記を最大化 E(a1,a2,…,an) = Σ ai – (1/2) Σ aiajyiyj(φ(xi)・φ(xj)) 双対問題も変数の個数が多いと完全に解くことは難しい配布プログラムでは 0≦ai≦C で定数(L>0)を用いて H(a1,a2,…,an) = E(a1,a2,…,an) - L(Σaiyi)2 の最大化問題を最急上昇法で解いている． C の制限をつけることをソフトマージンという．問２雑音の大きさサポートベクトル数汎化誤差 0.0 0.1 0.2 0.3