![改めて問題を定式化
次の線形モデルで二値分類問題を解く
y(x) = wT φ(x) + b tn ∈ {?1, +1}
訓練データが線形分離可能と(ひとまず)する
よって、分類境界からデータ点までの距離は以下
の通り tn y(xn ) tn (wφ(xn ) + b))
=
||w|| ||w||
解は次の問題を解けば良い
1
argmaxw,b minn [tn (wT φ(x))]
||w||](https://image.slidesharecdn.com/prml07-130321005437-phpapp02/85/Prml07-8-320.jpg)
![スケーリングを行う
パラメータを定数倍しても、距離は変化し
ないので、適当なスケーリングにより、境
界に最も近い点について以下の式を成立さ
argmaxw,b
1
1
minn [tn (wT φ(x))]
||w||
minn [tn (wT φ(x))]
せる事が出来る。
argmaxw,b
||w||
tn (wT φ(xn ) + b) = 1
tn (wT φ(xn ) + b) = 1
すなわち、全点において
T
tn (w φ(xn ) + b) ≥ 1
tn (wT φ(xn ) + b) ≥ 1](https://image.slidesharecdn.com/prml07-130321005437-phpapp02/85/Prml07-9-320.jpg)
![すなわち、以下の二次最适化问题
tn (wT φ(xn ) + b) = 1
T を解けば良い
t (w φ(x ) + b) ≥ 1
n n
1
目的関数: minn [tn (wT φ(x))]
argmaxw,b
||w||
1
argminw,b ||w||2
2
T
tn (w φ(xn ) + b) = 1
制約条件:
argminf (x)
tn (wT φ(xn ) + b) ≥ 1
gi (x) > 0
この問題の解は、KKT条件を満たす。
m
f (x) + λi gi (x) = 0
i=1
λi ≤ 0](https://image.slidesharecdn.com/prml07-130321005437-phpapp02/85/Prml07-10-320.jpg)
More Related Content
What's hot (20)
Similar to Prml07 (20)
More from Tsukasa Fukunaga (9)
Prml07
- 1. PRML?第7章 疎な解を持つカーネルマシン 東京大学大学院?情報生命科学専攻? 修士二年?福永?津嵩
- 2. カーネル法のおさらい ?? 有効なカーネル関数を設計することで、特 徴空間への写像を明示的に構成する必要 がなくなる。(カーネルトリック) ?? ナイーブな適用では、訓練データの全てを 保持する必要があるため、メモリ量を多 く必要とする。また、学習には時間がか からないが予測に時間がかかる。
- 4. 7.1?最大マージン分类器 (SVM) ?
- 5. パーセプトロンの復習(4.1.7) 識別関数の１つ y(x) = f (wT φ(x)) f(x)はステップ関数 以下のパーセプトロン基準を最急降下アル ゴリズムで最小化する。(Mは誤分類された パターンの集合) Ep (w) = ? w T φ n tn n∈M
- 6. パーセプトロンの问题点と マックスマージン 全てのパターンを正しく分類している場合、 それらの識別関数の間に優劣はない(3つの 線は全てパーセプトロン基準が0となる) 直感的には まぁ真ん中が良いよね (マックスマージン)
- 8. 改めて問題を定式化 次の線形モデルで二値分類問題を解く y(x) = wT φ(x) + b tn ∈ {?1, +1} 訓練データが線形分離可能と(ひとまず)する よって、分類境界からデータ点までの距離は以下 の通り tn y(xn ) tn (wφ(xn ) + b)) = ||w|| ||w|| 解は次の問題を解けば良い 1 argmaxw,b minn [tn (wT φ(x))] ||w||
- 9. スケーリングを行う パラメータを定数倍しても、距離は変化し ないので、適当なスケーリングにより、境 界に最も近い点について以下の式を成立さ argmaxw,b 1 1 minn [tn (wT φ(x))] ||w|| minn [tn (wT φ(x))] せる事が出来る。 argmaxw,b ||w|| tn (wT φ(xn ) + b) = 1 tn (wT φ(xn ) + b) = 1 すなわち、全点において T tn (w φ(xn ) + b) ≥ 1 tn (wT φ(xn ) + b) ≥ 1
- 10. すなわち、以下の二次最适化问题 tn (wT φ(xn ) + b) = 1 T を解けば良い t (w φ(x ) + b) ≥ 1 n n 1 目的関数: minn [tn (wT φ(x))] argmaxw,b ||w|| 1 argminw,b ||w||2 2 T tn (w φ(xn ) + b) = 1 制約条件: argminf (x) tn (wT φ(xn ) + b) ≥ 1 gi (x) > 0 この問題の解は、KKT条件を満たす。 m f (x) + λi gi (x) = 0 i=1 λi ≤ 0
- 11. ||w|| (wTn tn n φ(x ) + b) ≥ 1 tn (wT φ(xn ) + b) ≥ n 1 1 argminw,b ||w|| 1b) = 1 2 KKT条件とは？ argmin ) + argminw,b 1 ||w|| T tn (w φ(xnw,b ||w|| 1 1 2 w,b ||w|| argmin 2 argminw,b ||w|| argminf (x)2 2 tn (wT φ(xn ) +(x)≥ 1 argminf b) argminf (x) 目的関数argminf (x) argminf (x) 制約条件1 gi (x) ≤ 0 argminw,b≤ ||w|| gi (x) = 0 gi (x) 0 とし、目的関数及び制約条件が全て凸関数であ 2 g (x) ≤ 0 gi (x) ≤ 0 i るならば、以下の条件を満たす事が必要充分で m m f (x) + λi gi (x) = 0 ある。 λif (x)(x)i=1 0λ g (x) = 0 argminf (x) f (x) + m gi + = i i m m (1) f λi +i (x) =ii=1≤(x) = 0 f (x) + (x) i=1 g λ gi 0 λi 0 i=1 (2) i=1(x) ≤ 0 gi λi ≤0 λi ≤ 0 ≤ (3) λi ≤ 0 λi λi g0i (x) = 0 m (4) f (x) +λi gi (x) =i0 λi gi0 = 0 λi g (x) = (x) i=1 λ g (x) = 0 λi gi (x) = 0i i λi ≤ 0
- 12. T n (w φ(xn ) + b) ≥ 1 1 KKT条件についての注意 argminw,b ||w|| 2 関数が凸関数でなかったときは、局所的最適解に おける必要条件だけを満たす argminf (x) ???を満たす制約を無効な制約、満たさない制 gi (x) > 0 約を有効な制約と呼ぶ m (x) + λi gi (x) = 0 証明や詳しい解説は『非線形最適化の基礎』(福島 i=1 雅夫 0著)など λi ≤ λi gi (x) = 0 大学の数学に慣れてない人は少し大変かも。。
- 13. i=1 λiλi (x) = = 0 g i gi (x) 0 m λi ≤ 0 f (x) ≤ 0 λi + λi gi (x) = 0 SVMにおけるKKT条件 i=1 N w= N a t φ(x ) w= n n tn φ(xn ) i gi (x) = 0 an n λ λi gi (x) = i0≤ 0 λ n=1n=1 SVMの目的関数及び制約条件は凸性を満た NN N すので、目的解はKKT条件を満たす N λi gi (x) nan0 = = w = a = ntn 0 0 t an tn φ(xn ) w= an tn φ(xn ) n=1 n=1 n=1 SVMのKKT条件は以下の通り n=1 N an ≥ 0 N an ≥ 0 (1)N w = = 0 n tn φ(xn ) an tn a an tn = 0 n=1 n=1 (2) tnt(wT φ(xn )n+ + b) ? ≥ ≥ 0 n=1 T n (w φ(x ) b) ? 1 1 0 N an ≥ 0 (3) an ≥ 0 an tn = 0 n=1 anann (wT φ(xn )n+ + b) ? 1) = 0 (4) (t (tn (wT φ(x ) b) ? 1) = 0 tn (wT φ(xn ) + b) ? 1 ≥ 0 tn (wT φ(xn ) + b)n? 10≥ 0 a ≥ an (tn (wT φ(xn ) + b) ? 1) = 0 T (wT an (tn (wtnφ(xn φ(xn ) ? 1) ? 1 ≥ 0 ) + b) + b) = 0
- 14. an ≥ 0 SVMの双対表現とKKT条件の解釈 T tn (wT φ(xn ) + b) tn (w 0 n ) + b) ? 1 ≥ 0 ? 1 ≥ φ(x an (tn (wT φ(xn ) + n (tn (wT φ(xn ) + b) ? 1) = 0 a b) ? 1) = 0 KKT条件(1)を線形モデルに代入すると、以 下の式が得られるN N y(x) = an tn k(x, xn ) + b n=1 y(x) = an tn k(x, xn ) + b n=1 この時、??となるデータベクトルのみ保 a =0 n an = 0 持しておけば良いことがわかる。これをサ ポートベクトルと呼ぶ。 1 1 bはKKT条件(2)から求める
- 15. 7.1.1?重なりのあるクラス分 布 ?
- 16. an ≥ 0 完全に分離する識別器の汎化性能 T n T t (w φ(x ) + b) ? 1 ≥ 0 n t (w φ(x ) + b) ? 1 ≥ 0 が高いとは限らない n n an (tn (wT φ(xn ) + b) ? 1) = 0 an (tn (wT φ(xn ) + b) ? 1) = 0 汎化性能を高めるために、訓練データの誤 分類を認める→スラック変数の導入 N y(x) = N an tn k(x, xn ) + b y(x) = an tn k(x, xnn=1 b )+ n=1 an = 0 スラック変数n = 0 a 1.データが正しく分類され、マージン境界ξn = 0 外に存在→ ξn = 0 2.そうではない→ ξ)| = |tn ? y(xn )| ξ = |t ? y(x n n n n 1 1
- 17. ξn = 0 制約条件の緩和 ξn = |tn ? y(xn )| ξn = 0 スラック変数を用いて制約条件をソフト 0 ≤ an ≤ C マージンに緩和する ξn = |tn ? y(xn )| tn y(xn ) ≥ 1 ? ξn 0 ≤ an ≤ C また、目的関数を以下のように定義する N 1 C ξn + ||w||2 (Cは正則化パラメーターでありCVで決定す tn y(xn ) ≥ 12? ξn n=1 る) N 1 C ξn + ||w||2 n=1 2
- 18. 二次凸计画问题になっているの で?? ハードマージンSVMと同様、 1.KKT条件を考察 2.線形モデルを双対化 3.bを求める ξ =0 n 違い ξn = |tn ? y(xn )| 1.制約条件が複数存在する 2.矩形制約が現れる( 0 ≤ an ≤ C )
- 19. n n n 0 ≤ an ≤ C ν-SVMは伊達じゃない！ N 1 2 ξ + ||w|| tn y(xn ) ≥ 1 ? ξn C n 2 n=1 制約条件C(C-SVM)の代わりに以下のように C N 1 ξn + ||w||2 0 ≤ an ≤ 1 N νを用いる n=1 2 N 1 0 ≤ an ≤ an ≥ ν N n=1 νはサポートベクトルの割合の下限と解釈 N an ≥ ν する事が出来る(数式的には、C-SVMと等 n=1 価)
- 22. 7.1.2 ロジスティック回帰との関 係 SVMの誤差関数(青)は、ロジスティック回帰(赤)と 似た形状。ただし、平坦な部分があるため疎性が 存在する。 真の誤差関数(黒)の連続関数による近似。この図か らわかる通り、SVMは外れ値に弱い。 二乗和誤差(緑)は正しい分類にも ペナルティを課す
- 24. 7.1.4?回帰のための厂痴惭 ?
- 25. C C + 2 ||w|| ||w||2 ξn ξn + N 2 1 n=1 a ≤ 1 n=1 0 ≤ an ≤ 誤差関数を以下のように書き換え 0≤ n 1 N N N 0 ≤ an ≤ a ≤ 1 a ≥ν る 0≤N N n N N n=1 n an ≥ ν an ≥ ν 二乗和誤差関数の代わりにε許容誤差関数 N n=1 N an ≥ ν ≥ ν C N n=1 1 E (y(xn ) ? tn ) + ||w||2 an を用いる Nn=1 n=1 1 N n=1 2 1 2 C 2 E (y(xn ) ? tn ) + ||w|| C E (y(xn ) ? tn ) + ||w|| N 2 n=1 2 n=1 N 1 1 E (y(x) ? t) = 0 C E (y(xn ) ? tn ) + t ||w||2 ||w||2 C E (y(xn ) ? 2n ) + n=1 n=1 E (y(x) ? t) = 0 2 (y(x) ? < E|y(x) ? t|t) = 0 E (y(x) ? t) ?? t) = 0 E|y(x) = t| < (y(x) 0 E (y(x)|y(x) = t| < ? t| ? ? t) ? |y(x) E |y(x) ? t| <? |y(x) ? t| ? E (y(x) ? t) = |y(x) ? t| ? ? t) (y(x) |y(x)= t| < otherwise E (y(x) ? t) =otherwise ?? t| ? otherwise E (y(x) ? t) = ? t| |y(x) |y(x) otherwise otherwise
- 26. n=1 2 N 1 C E (y(xn ) ? tn ) + ||w||2 スラック変数の導入 E (y(x) ? t) = 0 n=1 2 |y(x) ? t| < E (y(x) ? t) = 0 識別問題と同様に、スラック変数を導入し、 E (y(x) ? t) = |y(x) ? t| ? |y(x) ? t| < チューブの外側にデータ点が存在する事を otherwise E (y(x) ? t) = |y(x) ? t| ? 許す制約条件とする。 otherwise tn ≥ y(xn ) + + ξn tn ≤ y(xn ) ? ? ξn tn ≥ y(xn ) + + ξn この時、誤差関数は下のようになる。 tn ≤ y(xn ) ? ? ξn N C ?n ) + 1 ||w||2 (ξn + ξ n=1 2
- 30. バイオインフォマティクスとSVR 微生物ゲノムを扱う時に使われる事があるら しい？ 非線形性を導入すると線形回帰よりフィットしたとしても、 それに生物学的解釈を与えるのは難しい
- 31. 7.2?関连ベクトルマシン (RVM) ?
- 32. SVMとRVMの関係 モデルとしては、解が疎になる事を除き(多 分)関係はない SVM RVM 事後確率 計算出来ない 計算出来る 多クラス分類 拡張が難しい 拡張が簡単 交差検定 必要 不要(エビデンス近似) カーネル関数 正定値性が必要 正定値性は不要 汎化性能及び疎性 どちらも高い どちらもSVMより高い 学習速度 凸関数のため、高速 非凸関数のため、遅い
- 33. tn ≥ y(xn ) + + ξn ベイズ線形回帰の復習 tn ≤ y(xn ) ? ? ξn N ? 1 C (ξn + ξn ) + ||w||2 2 ?? パラメーターに事前分布を設定する n=1 p(w|α) = N (w|0, α?1 I) ?? 超パラメーターは、エビデンス近似を用い る事で、モデルエビデンスから自動的に決 定される ?? 推定した超パラメーターを用いてパラメー ターの事後分布や予測分布を評価する 2
- 34. tn ≥otherwise + ξn y(xn ) + tn RVM独自の部分 tn ≤ y(xn ) ? ? ξn ≥ y(x ) + + ξ n n N C ?n ) + 1 ||w||2 (ξn + ξ tn ≤ y(xn ) ? ? ξn 2 ?? RVM回帰はベイズ線形回帰とほぼ同じ n=1 N C ?n ) + 1α?1 I) ?? 事前分布を重みパラメーターそれぞれに採 p(w|α)n= N (w|0, ||w|| (ξ + ξ 2 2 用する n=1 p(w|α) = M (w|0, α?1 I) N ?1 p(w|α) = N (wi |0, αi ) i=1 M ?1 p(w|α) = N (wi |0, αi ) ?? 線形モデルをカーネル化する i=1 N y(x) = wn k(x, xn ) + b n=1 2
- 36. 7.2.2?疎性の解析 ?
- 37. i i i=1 M N なぜ疎になるのか？(直感的な説明) ?1 p(w|α) = = N (wi |0, αi y(x) w k(x, x ) + b ) n n i=1 n=1 N wn k(x, xn ) + b p(t|α, β) = N (t|0, C) 周辺確率の尤度は以下の通り y(x) = n=1 1 1 p(t|α, β) = N (t|0, C) C= I + ψψ T β α 1 1 ψが訓練データベクトルと関係ない方向を C = I + ψψ T β α 2 向いている場合、重みを0にする事が観測確 率が最大 2
- 38. p(t|α, β) = N (t|0, C) 1 1 C = I + p(t|α, β) = N (t|0, C) N (t|0, C)1 ψψ T p(t|α, β) = αi 1 β α C = I + ψψ T p(t|α, β) = N (t|0, C) 1 数理的な解析 C = I + ψψ β 1 T α 1 C = 1 I + 1 ψψ T T ?1 β α αi 1 lnN (t|0, C) = ?I + 1ln(2π) + ln|C| + t C t} C = 2 {N ψψ T 1 1 Tβ α β α αi p(t|α, β) = N+ ψψ C = I (t|0, C) 尤度関数を?で微分して停留点を求める 1 β α αi ?1 T C = C T + αiα |0, C) = ? {N ln(2π) + ln|C| +i t?iC?1 t} iψi ψi 1 α 対数尤度関数は lnN (t|0, C) = ? 2 {N ln(2π) + ln|C| + tT C?1 t} 2 1 C = I +1 1 αi ψψ T lnN (t|0, C) β ? α ln(2π) + ln|C| + tT C?1 t} = {N 1 2α?1 ψ 1L(α) = L(α?iln(2π) +Tln|C| + tT C?1 t} T = ? {N ) + λ(α ) ?1 C = (t|0, C) =(t|0,{N ln(2π) + ln|C| + t C t} lnN C?i + i ? i ψC) lnN i 2T ?1 i 1 2 ?1 C = C?i + αi ψi ψi T Cから?を陽に書き下すと (t|0, C) = ? {N i 2 αln(2π) + ln|C| + t C t} 2 1 ) L(α) = L(α?ii )+ = Ci?i + α ln(αi + si ) + qi λ(α )C λ(α lnαi ?i ψi ψi = ?1 T 1= ?1 2 α +s 0, C) = ? C {NC?i + αi ln|C|i + tT C?1 t} L(α) =i L(αi?i ) + λ(αi ) ln(2π) + ψi ψ T よって、対数尤度関数は 1 2 2 qi T ?1 αi ) = lnαi ? ln(αi + si ) + si = ψi C?i ψ1 i 2 qi 2 L(α) = L(α ) + λ(α αi + λ(α ) = si lnαi ? ln(αi + si ) + ?i i) i 2 αi + s i T ?1 T ?1 si = ψi C?i ψi qi = ψi C?i t 2 1 qi T ?1 si = ψi C?i ψi (αi ) = lnαi ? ln(αi + si ) + 2 αi + s i
- 39. lnN (t|0,2 = ? {N ln(2π) + ln|C| + t C t} ?1 C) dλ(α?1 t αi T 2 ? (qi ? si ) 2 T i) qi = ψi C?i si = ψ C ψi si ?1 = i ?i Tdα?1 q = ψ2(α?1 t si )2 i T i+ si = ψi C?i ψii 1 i C?i = α?1 i (αi ) 2 i s2 ? (qi ? inf ?1 + 微分する C) = ? {N ln(2π) 2 ln|C| + tT C?1C = C?i + αi ψi ψi si ) T qi = ψi C?i t t} ?1 T dλ(αi ) T + )2?1 i αi q = ψ2(α?1 t si αi s2 ? (qi ? si ) C?i = 2 i i dαi ?1 T C = C?i + αi ψi ψi i + si )2 L(α) = L(α?i ) + λ(αi ) ? dλ(αi ) qαi?1 ss2 ? (qi2 ? si ) 2 2(α inf = i < ii (αi ) ? αi sdαi (qi ? si2(αi + si )2 ?1 2 i ? 2 ) = inf 2 αi L(α) = L(αi + si )λ(αi ) 2(α?i ) + 2 1 qi λ(αi ) = lnαi ? ln(αi + si ) + よって、解は 2 qi < si 2 s2 i 2 αi + s i q2 ? si i <s 1 inf qi i q2 i T ?1 = lnαi ?2ln(αi + si ) + si = ψi C?i ψi 2 si α + si qi > si i 2 2 i ?s q2 < si qi s2 i i T ?1 q 2 ?を疎性パラメータ、を品質パラメータと呼 si = ψi C?i ψii ? si T ?1 qi = ψi C?i t 2 qi > si ぶ s2 i 2 T ?1 qi > si q2 ? s qii = ψi C?i t 2 qi > si
- 42. 3から7章のざっくりまとめ 3?4章:ベイズ線形回帰、ベイズ線形識別 回帰は積分が解析的に解けるが識別は解け ないため、ラプラス近似を用いる 5～7章:回帰?識別問題で非線形性を扱う 5章:基底関数そのものを学習させる(ニューラル ネットワーク) 6?7章:基底関数をデータ点から選択する(カー ネル法)