情報知能学基礎演習豊田秀樹(2008)『データマイニング入門』 (東京図書)第８章情報知能学科白井英俊 1 復習：ベイジアンネットワーク • P.234よりベイジアンネットワークを利用すると、各ノード（確率変数）の因果的な構造（影響）関係を視覚的にモデル化し、さらにその各ノードの状態がどの程度の確率で起こりうるのかということ（不確実性の程度）を数値的な値として評価できるようになる。不確実な事象のモデル化がベイジアンネットワーク 2 前回の課題でもしもbanlistを使わなければ… Score: -603.9853 Relscore: 0.3749276 体重人種喫煙高血圧過敏 3 サポートベクターマシン • ニューラルネットワークネットワークへの入力ユニットを増やすと識別力の高いモデルを構成することが可能交差妥当性が乏しくなるという欠点がある • サポートベクターマシン(SVM, Support Vector Machine) 第3世代の学習マシン：本質的に3層の階層型Neural Net マージン最大化カーネルトリック 4 線形分離不可能性識別問題において線形分離可能性：線形関数で超平面（2次元の場合は直線）により対象の分類が可能である場合。そうでなければ線形分離不可能 XOR(排他論理和） (1,0), (0,1)の場合は1 (1,1), (0,0)の場合は0 線形分離可能線形分離不可能（識別のための直線が1本でない） 5 超平面について • n次元空間において、一次方程式 a1x1+a2x2+ … +anxn +b = 0 (n-1個の変数の値が決まれば、残りの1個の変数の値が決定される、という関係)は「超平面」を構成する • 例： n=2, つまり2次元の場合、 ax+by+c=0 は直線を表す(x の値を決めればyの値が決まる) n=3、つまり3次元の場合、ax+by+cz+d=0は平面を表す (xとyの値を決めればzの値が決まる) n >= 4 でも同様に考えられる 6 高次元空間への写像 • ある次元空間(次元数をnとする)では線形分離不可能であっても、n+1次元では線形分離可能にできる場合がある。 • 2次元におけるXORの例の場合 z 2 2  ( z1, z2 , z3 )'  ( x1 , x2 , 2 x1x2 )' • その結果が図8.3 カーネルトリックにより写像計算が簡単に！ 7 超平面の決定方法 • ニューラルネットでは、誤差逆伝播法 • SVMではマージン最大化超平面とデータとの距離が最大になるような超平面を選択する、ということ ⇒汎化性能が高いこの求め方は8.2.3で 8 線形閾値関数 • yi をオブザベーションi(i=1,2,…,I)の２値型の名義的反応(出力） • xiを、 yi を予測するために用いられるオブザベーションiに関するJ次元のベクトル(入力） xi = (xi1,xi2,…, xij…,xiJ)’ 線形閾値関数(yiについてクラス1には「１」、クラス２には「－１」を与えるとき） yi = 1, f(xi) ≧ 0 のとき－1, f(xi) < 0 のとき 9 識別超平面線形閾値関数におけるf(xi) f(xi)=ω’ xi+b ここでωはJ次元の重みベクトル識別超平面は f(x)= ω’ x+b =0 (8.2) あるデータ xiとこの超平面との距離は：  ω' xi  b   ω      10 マージン最大化データの集まりxiと超平面との最小距離に対し次の制約を課す： Min ω' xi  b   1 i 1, 2,...,I これにより下位の一意性を保証ゆえに、データの集まりxiと超平面との最小距離は、 1/ ω （実際は２グループあるので 2/ ω ）これを最大化することは、次を最小化することと同値 2 ω /2 11 マージン最大化（続き) • ラグランジュの未定乗数法を用いて… クラス１ならy ＝１, (ω’ x +b) ≧0 2 クラス2ならy =-1, (ω’ x +b) < 0 目的関数： ω / 2 不等式制約: yi (ω’I xi +b) ≧1 (8.7) i i L(ω,b,α）= ω 2 / 2    i [ yi {( ω' xi  b)  1}] i i (8.8) i 1 ここでαiはラグランジュの未定乗数、 αi ≧0 ラグランジュの未定乗数法: g(x,y)=0という条件の下でｚ = f(x,y) の最大値（最小値）を求める問題は、λという係数を用いて L=f(x,y) - λg(x,y) という関数の極値を求める問題とみなす 12 ラグランジュの未定乗数法を用いて (8.8)を最小化するωとbに対し、(8.9), (8.10)が成り立つ参考： y=x2+ax+cにおいて最小値はy’=0を与えるxで得られる。ここでxをベクトルωと考える… I I L(ω, b, α )  ω    i yi x i  0  ω    i yi x i ω i 1 i 1 I L(ω, b, α )    i yi  0 b i 1 (8.9) (8.10) 以上を(8.8)に代入して I 1 I I L(α)   i   i j yi y j xi 'x j 2 i 1 j 1 i 1 (8.11) が得られる。これを最大化することにより、目的関数の最適化を行う  i  0, I  i yi  0 i 1 13 L(ω, b, α)  ω 2 式の変形 / 2    [ y {( ω' x  b)  1}] I i 1 i i i (8.8) I I I 1 2  ω  ω'   i yi x i  b  i yi    i 2 i 1 i 1 i 1 I 1 2 2  ω  ω  b * 0  i 2 i 1 1 2 I  ω  i 2 i 1 符号を入れ替えた次のようなL(α)を作ると、今度は「最大化」問題となる I 1 I I L(α)   i   i j yi y j xti x j 2 i 1 j 1 i 1 (8.11) 14 カーネルとサポートベクター I 1 I I L(α)   i   i j yi y j xti x j 2 i 1 j 1 i 1 (8.11) ベクトルの内積の式になっている。高次元空間への写像Φを行うとすればここは、  ( xi ) t  ( xi ) と書ける。カーネル： Φ(xi)の内積をxiの内積の関数で表現したもの L(α)の最大化問題を解くと、ほとんどは、αi=0。０でないαiを(8.9)に代入してωを得る。b値は別のクラスに属するサポートベクターxsv1, xsv2により 1 b 2 ω' x SV 1  ω' x SV 2  (8.12) 15 カーネルトリックカーネルk(xitxi)に対して (8.2) 式は以下のようになる： SV f (x)    s ys (x ts x)  b 線形SVM: s 1 SV t f ( x )   y k ( x 非線形SVM:  s s s x)  b s 1 代表的なカーネル：線形カーネル k(xi’xj) = xi’ xj 多項式カーネル k(xi’xj) = (γ xi’ xj +δ)d ガウシアンカーネル k(xi’xj) = exp(-γ||xi -xj||2) シグモイドカーネル k(xi’xj) = tanh(γ(xi’xj)-δ) 16 ハードマージンとソフトマージン • ハードマージン：境界面f(x)=±1に挟まれる領域にオブザーベーションは存在せず、誤分類もないマージン • ソフトマージン：少数のオブザベーションの誤分類を許すマージン。以下の制約をもつ yi (ω' xi  b)  1  i , i  0 • 分析の経済性からソフトマージンが必要な場合もある 17 実習 • サポートベクターマシンの数学的な根拠の理解にはちょっと訓練が必要。。。 • データに対し、よりよい識別関数f(x)を求めるにも、訓練が必要。。。 • 参考： http://www.neurosci.aist.go.jp/~kurita/lecture/svm/svm.html http://arx.ee.utsunomiya-u.ac.jp/research/svm/index.html http://www.neuro.sfc.keio.ac.jp/~masato/study/SVM/index.htm http://www.bi.a.u-tokyo.ac.jp/~tak/svm.html 18