Upgrade to Pro — share decks privately, control downloads, hide ads and more …

カーネル法まとめ

Ringa_hyj
August 26, 2020

 カーネル法まとめ

まだ仮

Ringa_hyj

August 26, 2020
Tweet

More Decks by Ringa_hyj

Other Decks in Science

Transcript

  1. 古典的なパターン認識では、 逆行列や固有値などの線形代数的アプローチから線形回帰、最小二乗法、主成分分析を行った カーネル法では特徴量の次元を莫大に増やすので古典的なアプローチでは計算爆発が起こる (200次元を3次モーメントまで作るなら・・・) 3次モーメント = 特徴量のうち3つを選択して掛け合わせる 200C1 + 200C2

    + 200C3 = 1333500次元 しかし、カーネル法はデータ側を非線形変換することで線形モデルが使える強力な手法なので なんとかしてでも使いたい そこで計算爆発を抑えるカーネルトリックが考えられ、 カーネルトリックのための制約を持った変換関数が正定値カーネルである
  2. 線形K 1 ⅈ, = 1 , 1 … 1 ,

    … … , 1 … , 0 , = , = exp , = exp − − 2 22 , = exp − ෍ − , = + グラム行列 指数K ガウスRBFK ラプラスK 多項式K
  3. 関数推定 原点を通る線形モデル = = ෍ =1 Wの推定は関数と実測値のズレを損失関数として設定する , ; =

    − 2 = ෍ =1 , ; = − − R(W)は二次式であり、Wに対して微分して0になるときが最小 行列で表すなら ⅆ ⅆ = 2 − = 0 = −1 式を見るとわかるが行列計算で求めるなら逆行列がなければ計算できない
  4. カーネル関数に以下を選ぶとする , ′ = exp − − ′ 2 2

    = ෍ =1 2 このカーネルではx-x’=0のとき値が最大となる 直感的にはxに対してx’がどれだけ近い値の大きさを持っているかを表す βはハイパーパラメータ
  5. カーネルの中身は絶対値で符号が無くなっている 計算された行列Kを見てみると、対象行列になっていることから、転置したものも等しい ′, = , ′ = よって係数αの計算は = −1

    2 −1 = −1 = 単純な計算によって求められることが分かった この計算で求められるのは無限次元多項式に等しいような過学習した曲線である 外挿部分やデータ間の予測精度は悪い これは1変数をデータの行数だけの行列に増やすことによる次元の呪いである サンプル数と同じだけ自由度があるので過学習する 汎化性が欲しくなるよね
  6. リプレゼンター定理 ←複雑な正則化項を含む式を最小化するのではなく、特徴ベクトルの内積とその係数を もとめたらおなじことだよって意味?? 正則化がλ||w||^2であれば、最適解は右のように表せる この定理は、y=wΦ(x)の wをΦによる変換(特徴ベクトル)と係数αで表現できることを証明するものである 0 = ෍ =1

    係数をαとΦで表すことにする 上記のような特徴ベクトルの線形和についてΦに直交するような ξ成分を加えたWを考える ξはΦと直交するのでその積は0になり、前項のみが残る つまりξは影響しなくなるので、 wはw0の他の要素を含まない。 正則化項も ||w||^2 = ||w0||^2 + ||ξ||^2 として考えるとξ=0のとき最小値となる よって損失関数と正則項の加わった式の最小化を考えると、W=W0となる。 以上より、 Φ(xi)TΦ(x) = k(xi, x) と書き直せることより、 上式の最適解がもとまる = 0 + = = 0 + 0 + = ෍ = ෍ =1 ,
  7. 係数wと特徴ベクトルΦの内積をwΦ(x)とおいて y-wΦ(x) の最小二乗法 + 正則化項 という式をわざわざ計算しなくとも 特徴ベクトル同士Φと別の重みαで表現できるよ という定理 これが成り立つとカーネル法を使って表現できるのでカーネル法を学ぶ上で知っトク ξが直交する要素

    というのは、Φ(x)で張られる空間上に内 という待遇を考えてみることである ξに依存しないことが分かるので、最適解wはΦで張られる空間上に存在する。 wについての問題をαについて解くことで自然とwも決まるような問題に変形している このような問題を双対問題という というかwとか考えなくてもよくなる。もちろん問題を変換せず元の式でといてもいいが カーネル法を使うとカーネルトリックが聞いて計算が楽。
  8. カーネルトリックについてもうちょっと咀嚼 X=[x1,x2] X’=[x’1,x’2]とする カーネル法だと内積計算だったりするので、X=X’だったりするけど、見やすさのために分けてかく 手法1 6つの基底関数を考えて特徴ベクトルに写像してカーネル行列(グラム行列) を求めてから内積を計算する場合 回答 Φ(X) =

    (X1^2,x2^2,√2 *x1x2,√2x1, √2x2,1)という特徴抽出を考える XもX’もこの変換を使って6次元のデータを二つ作る これの内積計算を行う Φ(X)TΦ(X’) を得る 手法2 カーネル関数を使う 説明のためカーネル関数に帰着させる 上記のΦ(X)TΦ(X’)は(X1^2,x2^2,√2 *x1x2,√2x1, √2x2,1) ・ (X‘1^2,x’2^2,√2 *x’1x’2,√2x’1, √2x’2,1) を計算することであり、実際に展開してから平方完成を行うと (x1x’1 + x2x’2 + 1)^2 という式になる。 n*1 + n*1 回の掛け算だけで済む 行列で計算しなくても各要素をこれで計算したら直接求められる。 K(X, X’) =(XTX’ +1)^2 と定義したらいい。
  9. カーネル主成分分析 変数を特徴抽出によって作り出してから主成分分析をする 二次元の変数 X=[X1,X2] Φ(X) = {Φ1(X1), Φ2(X2),Φ3(X2)} Φ1=X1 Φ2=X2^2

    Φ3=X2 三次元に拡張して、主成分軸(平面)の方程式を考える a1Φ1 + a2Φ2 + a3Φ3 + a4 *1 =0 通常の主成分分析を使っても解ける これを カーネル主成分分析 と呼ぶ
  10. 纏めてラグランジュ方程式にすると = − 1 2 + − 1 ⅆ ⅆ

    = − 2 2 + 2 = 0 微分して0と置いて = 以上より、以下のようにグラム行列の固有値問題にできた カーネルPCAは元の特徴量について綺麗に写像できているかは不明 拡張した特徴ベクトルの世界での分散の最大化を目的にしている 主成分分析の主成分軸(面)は線形であるため、元のデータ空間の関係性が非線形の時には カーネルPCAが有用になる(スイスロール) ただし、どのカーネル関数を選ぶかによって有用にならない時もある
  11. 次元圧縮を特徴ベクトルの線形和として定義する = ばらつきの指標を 異なるクラス間分散 σ B 2 同じクラス内の分散 σ W

    2 とする。 うまい具合に分けるためには、 σ B 2 /σ W 2 が最大となるような関数fを考えてやればいい これを最大にする一つの解は分母を0にすることであるので、これは制約をかける リプレゼンターの定理から、上式f(x)をカーネル関数を含んだ式で表現できるので = ෍ =1 ,
  12. 各クラスの分散をσl2とすると、データのクラス内分散は以下のように表せる クラスはCクラスあるとする 2 = 1 ෍ =1 2 あるクラス限定の分散計算のために、例えばC=1の時のデータだけ取り出して平均を求めたい =

    1 ා =1 ෍ = , 以上より、クラス限定の分散は このクラスが限定された状態でのカーネル行列はK’とする 2 = 1 ා = ෍ =1 , − ′ 2 ここで、式を展開して、Slを使って表現すると
  13. 最小二乗法による損失関数 (ロジスティック回帰を参照) , = 1 2 − 2 = 1

    2 1 − 2 指示関数を使った場合 , = 1 2 − sgn[ ] 2 = 1 2 1 − [ ] 2 = 1 2 1 − [ ] 2 この場合、凸関数ではない そこで似たヒンジ損失関数を考える max 0,1 −
  14. スラック変数ξを使って制約を考える ξ>=0 ≥ 1 − ⅈ ⅈ = 1 −

    ⅈ ෍ 両方の制約を満たすうち、最小になるような識別関数のパラメータを求める min ෍ ℎ + min ෍ + 1 2 制約を考えて上記を書き直す これは凸二次計画問題となる
  15. 点と線の距離の公式の証明 ある直線式 ax + by + c= 0 と 点P(x1,y1)

    を考える 点と線の距離は、点から線に垂直に線を下した線分の距離とする 法線の交点をQ(x2,y2)とする ここで、この線分PQの傾きを考える 傾きとはxが1変化する時にyがどれだけ変化するかを表すものだった。 y2-y1 / x2-x1 直線の傾きはy=の形に変形して –a/b である 垂直な二直線の傾きの積は-1になる という法則から、上記の傾きを式変形する 以上から x2-x1=am y2-y1 = bmという式が出る − 2 − 1 2 − 1 = −1 2 − 1 = 2 − 1 =
  16. 直交する直線の傾きの積が-1の証明 三平方の定理 y=m’x+c (y-m’x-c) y=mx+c (y-mx-c) A(1,m) O(0,0) B(1,m’) H(1,0)

    ※切片c=0 三角形OAHは角Hで直角である。 (AO)2 = (AH)2 + (OH)2 = (m2+1) (BO)2 = (BH)2 + (OH)2 = (m’2+1) 求めたAO,BOを使ってABを求める (AB)2 = (BO)2 + (AO)2 = (m2+1) + (m’2+1) これは図形から以下のようになる = (m-m’)2 以上を変形して mm’=-1
  17. 点と線の距離の公式の証明 点と線の距離を、点から線に垂直に下した線分であるとする P(x 0 -x 0 , y 0 -y

    0 ) 線と点を平行移動して 点を原点にずらす x軸,y軸との交点をA,Bとする 0=ax+ by +c a(x+ x 0 )+ b(y+y 0 )+c = 0 P(x 0 ,y 0 ) A(,) B(,)
  18. 点と線の距離の公式の証明 P(x 0 -x 0 , y 0 -y 0

    ) a(x+ x 0 )+ b(y+y 0 )+c = 0 x=0の時 つまり点B a(0+ x 0 )+ b(y+y 0 )+c = 0 y=(-ax 0 -by 0 -c)/b y=0の時 つまり点A a(x+ x 0 )+ b(0+y 0 )+c = 0 x=(-ax 0 -by 0 -c)/a OA=|(ax 0 +by 0 +c)/a| OB=|(ax 0 +by 0 +c)/b| 三平方の定理より AB=sqrt( (OA)2+(OB)2 ) となる 三角形の面積は以下で成り立つはず ½(OA)(OB)=1/2(AB)*d A(,) B(,) 0 + 0 + 2 = 1 2 + 1 2 0 + 0 + = 0 + 0 + 2 + 2
  19. クラス分類を考える マージン最大化分類器 完全線形分離可能な場合 (データの関係が曲線でない、データの混ざりがない) x1 x2 f(x)=0 f(x)=-1 f(x)=1 =

    0 + 0 + 2 + 2 識別関数は互いのデータ点の中間である必要がある。 + ≥ 1 = 2 d d 識別関数は互いのデータ点の中間である必要がある。 両側d+dが最大になる場合が求めたい。 2dを最大にするには、上式の分母||w||2が小さくなる時である よって、最大化でなく、単に分母の最小化を考えてもいい。 分子は赤色までの距離のとき|-1|,黄色までの時|+1|となるので2 距離の計算に使われるベクトルを サポートベクトル 点と線の距離dをマージンと呼ぶ。 マージン最大化分類器は、 異クラスデータ間に最も幅の広い板を挿し込むもの
  20. 不等式制約を持つラグランジュ未定乗数法は カルーシュ・キューン・タッカー条件を満たす解から解が選ばれる , , = 1 2 − ෍ +

    − 1 = − ෍ = 0 特に一番最後の部分は相補性条件として知られる。 未定乗数αが0でないと成り立たない場合は括弧内が0より大きい場合であり、 αが解を持つ時とは制約式が計算して0になるような時である。 つまりサポートベクトルだけから計算する必要があることが分かる = ෍ = 0 + − 1 ≥ 0 ≥ 0 + − 1 = 0 KKT条件 ① ② ③ ④ ⑤
  21. wに関する偏微分式①を変形して = ෍ とする。この変形式と②を元の目的関数L()に代入すると = 1 2 − ෍ −

    ෍ + ෍ = ෍ − 1 2 = ෍ − 1 2 ා ෍ 上記のように、もとのパラメータwもbも存在しない、αを求めるだけの式に変形できた このように元の課題(主問題)を変形して、 別の問題(双対問題)の解を求めることで元の問題の解も求まる方法
  22. 双対表現を確認すると、 行数Nに対する内積XTXと、そのラベルデータtからなる行列がある これをHと置く = ෍ − 1 2 ා ෍

    = 1 − 1 2 この双対問題は、②よりαTt=0であったので、これを制約として、 ラグランジュ未定乗数 βを使うことで以下に直せる。 , = 1 − 1 2 − 上記でαを解き、αとt,xからwが求まる。 t(wx+b)-1=0を、サポートベクトルのt,x値を代入してbを求める
  23. 主問題を見ると、正則化項の付いた式のようになっている , , = 1 2 − ෍ + −

    1 wx+bを作るが、ノルムを大きくしすぎないように選ばれる
  24. + − 1 + ≥ 0 x1 ξ=0のとき マージンの上 0<ξ<=1のとき

    マージン内だが、最適識別超平面の正しく判別される側 ξ>1のとき 識別平面を超えて誤った側 スラックス変数ξを使って距離dを緩める マージン内や、誤分類を許す識別器を ソフトマージン識別器と呼ぶ
  25. ソフトマージン識別器の主問題 , = 1 2 2 + ෍ 制約 +

    − 1 + ≥ 0 ≥ 0 どれだけの誤りを許すのかをCによって制御することからC-svmとも呼ばれる ξとwの最小化を目指すように学習する Cは分類性能を交差検証によって確かめて決定する ラグランジュ未定乗数μをつかって = 1 2 2 + ෍ − ෍ − ෍ + − 1 +
  26. ソフトマージン識別器の主問題 , = 1 2 2 + / ෍ pは1か2が入る。1の時、L1

    SVM(標準、正規svmとも) 2のときL2 SVMと呼ばれる。
  27. 解はKKT条件を満たすものから選ばれる = 1 2 2 + ෍ − ෍ −

    ෍ + − 1 + = − − = 0 = − ෍ = 0 = ෍ = 0 + − 1 + ξ i ≥ 0 ≥ 0 ① ② ③ ④ ⑤ ξ ≥ 0 μ ≥ 0 α i ( + − 1 + ξ i ) ≥ 0 ⑥ ⑦ = 0 ⑥,⑦が相補性条件
  28. 元データXに対するこの変換した後のデータ行列を Φ(X)={Φ 1 (X),Φ 2 (X),…Φ M (X)} として表現する。次元はMになる。 Φ

    0 (X)=1 としてバイアス項を以降明記しないこととする 識別関数は を求めることであり、SVMの目的関数の偏微分から重みベクトルwは として求まるのだった。 もとの式に代入するとΦ(X)に関する計算が現れる。 これを一つの関数K(x,x)という形で表現する。このK()を核関数、カーネル関数、単にカーネル、と呼ぶ = ෍ = ෍ = ෍ ,
  29. カーネル関数はなぜうれしい? 1 X 1 2 √x 1 x 2 X

    2 2 √x 1 √x 2 六次元の内積計算でn*n行列を作るためにはn*n要素の計算が必要 しかし、ΦTΦによる計算を展開して 1+x 1 2x’ 1 2+2x 1 x 2 x’ 1 x’ 2 +x 2 2x’ 2 2+2x 1 x’ 1 +2x 2 x’ 2 これを平方完成すると (1+x 1 x’ 1 +x 2 x’ 2 )2 = (1 + XTX’)2 Φすると、元のn*d行列の内積からスカラを得て、1を足して、二乗したらいい。 このように計算が単純で済むし、 計算さえ決まれば何次元も特徴量を生成した行列をメモリ内に保持しなくて済む。 今回の例は二次の多項式カーネルを例にとった。
  30. 多項式カーネル , = + p次の特徴量を生成したことと同値にするカーネル関数 だいたい3~4次までのものしか見ない。 16*16の画像 256特徴量 をp=4での特徴量を考えた時、 そこから合成される次元は186043585次元までの抽出が考えられていることになる

    非常に高次元の非線形特徴空間への写像になるため、各データの距離は離れ、疎な空間となる このような学習法が背景にあるため、 疎なカーネルマシン と呼ばれる
  31. 動径基底関数カーネル (RBFカーネル) , = exp − 1 22 − 2

    σはカーネル関数の広がりを調節するパラメタ σが大きい時、入力データに対する広い範囲でのサポートベクトルが識別に関わる σが小さいとき入力データと近いデータのみがサポートベクトルとなる また、動径基底カーネルは無限次元の特徴量に展開することに等しい(証明pass)
  32. 1クラスSVMでの主問題 最小化 不等式制約 , = 1 2 − + 1

    ෍ − + ≥ 0 ≥ 0 この双対問題は = − 1 2 ා ෍ , 制約条件 0 ≤ ≤ 1 ෍ = 1
  33. ν-SVM 今まで t(wx+b) >= 1 という制約によって考えてきたが、この1さえも自動的に決めさせることを考える。(νトリック) t(wx+b) >= ρ その場合、最大化するマージンは

    2ρ/||w||2 ρが小さいとマージンも小さくなり汎化性は落ちる ρにたいしての調節を外部から加えられるようにνというハイパーパラメータを設ける w,ξの最小化を目指す。制約は νによって、マージンの大きさ、識別器の複雑さ、誤り率、を調節できる。 = 1 2 2 − + 1 ෍ + − + ≥ 0 ≥ 0
  34. SVMでの回帰 SVR 特徴量を合成(データ側を非線形変形)する考えによって線形回帰モデルを当てはめる z=y-f(x) の差分を最小にするように学習を進める。 二乗誤差による学習ではなく、区分線形関数γ()を使う γ(z) = { この区分線形関数を損失関数として考える

    真ん中の条件、ε以下の誤差は目をつぶる、ということから ε不感応関数 と呼ぶ 最小二乗法では二乗するために外れ値にロバストでないが、 この関数は緩やかな損失を与える z-ε (ε≦z) 0 (-ε≦z<ε) -z-ε (z<-ε)
  35. ξ i =γ(z)=γ(y i -f(x i )) ξ i ≧y

    i -f(x i )-ε ξ i ≧0 ξ i ≧-(y i -f(x i ))-ε 上記の制約の下で、二次の正則項を含めた以下を解くと回帰が求まる。 min ෍ +
  36. SVM回帰の双対表現 , , , , − = ෍ + 1

    2 − ෍ − ා + − + ෍ − ා − + + − ෍ 双対表現 これを最大化する。 制約は 0≦γ i + γ- i ≦1 , − = − 1 2 ෍ − − − − − ෍ − + − ෍ − +
  37. γ(z) = {2 2 ≤ − 2 2 ≥ 原点付近では二乗誤差、εを超えた範囲では線形誤差

    を採用して 外れ値に強いものにする。 フーバーの損失は、ε不感応関数のように原点付近のデータでも計算する必要がある。 (スパース性がない) フーバー型ロバスト推定 Huber損失関数 z=y-f(x)とする フーバー損失関数γ()は min 1 2 2 + −
  38. 残差を小さくするには |y-f(x)| < ε になるようなf(x)を学習する つまり、関数 f(x)±ε の範囲にyが入れば誤差は0と判定される この幅を εチューブ

    と呼ぶ このεを大きくしていけば誤差は小さくできるが、汎化のことも考えて、 データ点と関数f(x)(=最適超平面) のマージンを最大にする、という条件も付け加える必要がある +ε -ε
  39. 超平面 はD(x,y)=0 であるので、データ(x,y)までの距離は |D(x,y)| / ||w*|| ここでの ||w*|| は ||w*||=(1,

    -wT)T である データまでの最大距離をδとすると すべてのデータは |D(x,y)| <= δ||w*|| を満たす。 よって、最も超平面から遠くにあるデータが |D(x,y)| = ε である。 (SVCでは最も近いものとの距離を気にしていたが、チューブに全部いれるなら離れたデータとの距離を考える) y-f(x) は教師データと説明データの対 (x,y)から成り立つ損失関数Dとして考え、 D(x,y)と表現する
  40. |D(x,y)| = ε であるとは δ||w*|| = ε であるということになる。 マージンδを最大化するには||w*||を最小化する。 最小化するための凸二次計画のため二乗にすると、

    ||w*|| = (1, -wT)T だったので、 ||w*||2 = ||w||2 + 1 よって||w*||の最小化とは||w||の最小化として考えて問題ない min 1 2 2 − − ≤ + − ≤ 制約
  41. 制約 以上から求める式は min , 1 , ∗ = 1 2

    2 + ෍ + ∗ − − ≤ + + − ≤ + ∗ ≥ 0 ∗ ≥ 0 Cはマージンパラメータ pは1 or 2 p=1 のとき L1 SVR p=2 のとき L2 SVR と呼ぶ