SVMについて雑にまとめる

はじパタのSVMの直感的理解に苦しんだので雑に整理しておく。

SVMの導出

  • SVMを使うと2クラスの線形識別できるよ
  • 基本2クラスだけど多クラスの場合は、判別したいクラスとその他のクラスの2クラス問題にして一対他SVMするよ
  • サポートベクトルとは、識別境界を決めるために使用する学習データのことだよ。つまり境界付近のデータだよ。
    • サポートベクトルをつかって学習機械をつくるからSVMだよ
  • SVMの導出にはラグランジュ未定定数法をつかうよ
    • ラグランジュ未定乗数法は、制約条件下で評価関数を最適化する手法だよ。ただし制約条件下は等式のみだよ。
    • 制約条件下が不等式の場合は、KKT条件が必要だよ
  • この最適化問題の主問題の解は、双対問題の解がわかれば求まるよ

線形分離できない時

  • 基本的にSVMは線形分離できるときだけ使える手法だよ
  • ただし、ある程度の誤識別を許容することで線形分離できない問題も解くことができるよ
  • どれくらい誤識別するかをスラック変数で表すよ。スラック変数の総和が大きいほどマージンを超えてくるよ。
  • スラック変数の総和にどれくらペナルティを与えるかが、パラメータCだよ
  • Cが大きいほどマージンを超えてくることに厳しくなるよ。でも過学習しやすくなるので汎化誤差が大きくなるよ。
  • これをC-SVMとかいうよ
  • ちなみにスラック変数は学習の時だけつかうよ

非線形特徴写像

  • 線形分離できないd次元のデータをM>>dなM次元に写像すると、データの間隔に隙間ができるので(疎になるで)超平面で線形分離できる可能性がでてくるよ
  • ただし内積計算に時間がかかるので内積カーネルを用いたほうがいいよ
  • 内積カーネルには多項式カーネルと動径基底関数カーネルがあるよ
  • このあたりはよくわからんかったので、あとでやりなおすぞ

ν(ニュー)-SVM

  • 学習機械(識別する仕組み)が達成できる誤り率と機械の複雑さには関連性があるよ
  • 「誤り率と機械の複雑さ」のトレードオフをνというパラメータをつかって調整するよ
  • C-SVMの時と似ていて、複雑にすると誤り率が減るけど汎化誤差がますよ(過学習)、ぎゃくに単純すぎると誤り率が高くなるよ
  • パラメータνは、-ρ倍することでトレードオフを調整するよ。-ρなのは、ρが大きくなれば評価関数が小さくなるので最適化にすすむからだよ。
  • νは、「サポートベクトルの割合(全データのうち、どれくらいがサポートベクトルになるか?)の下限」と、「上限サポートベクトルの割合の上限」を表すよ
    • 上限サポートベクトル(Bounded SV)とは、α_i = 1/N となるデータだよ。

1クラスサポートベクトル

  • 2クラス分類で話をすすめてきたけれど、1クラスだけで学習して使う方法もあるよ
  • ある1クラスに属すか?属さないか?を分類するよ
  • 新規性判別、例外検出、外れ値検出に利用するよ

サポートベクトルの理解 むずかしい。

Jupyter NotebookでPIL画像(QRコード)表示

すこし躓いたのでメモ。

qrcodeモジュールでQRコードを作成するとPIL画像になる。 Jupyter上でPIL画像を表示するには、matplotlibのimshowを使うようだ。 imshowは、numpy.array型を引数に取るのでPILを一度numpy.array型に変換するする。

という具合にnumpyまで登場して、わりと面倒だし煩雑。PIL対応して欲しい。

サポートベクターマシンとかラグランジュ未定乗数法とか

2日かけてはじパタ8章の冒頭を読んでなんとなーく理解してきた。

ラグランジュという言葉に怖気づきそうになったけれど、 要は2変数関数の微分Wikipediaの言葉をそのまま借りると「束縛条件のもとで最適化をおこなう解析学の手法」なんだね。

ラグランジュ未定乗数法では、等式制約しか扱えないが、KKT条件(カルーシュ・クーン・タッカー条件)を用いた手法(制約に条件をさらに加える)なら不等式制約も扱うことができる。

SVMの導出は不等式制約条件なのでKKT条件が必要。

2変数関数g(x,y)=0(等式制約)とかg(x,y)>=1(不等式制約)等々の条件下で、関数f(x,y)最大化or最小化するx,yを求めるときに使う手法。 これを主問題(primary problem)という。

そして主問題を式変換していくと、ラグランジュ未定乗数を変数にした関数の問題に置き換えられる。 これを双対問題という。 (双対ってなんだ?って思ったけど英語のduality problemのほうが直感的なきがする。)

  • 双対問題の最大値を求めると、主問題の最小値が求まるし
  • 双対問題の最小値を求めると、主問題の最大値が求まる。

つらつらと文字で書くと凄く難しく感じるけれど 「ある条件下で2変数関数の最適解を求める方法だよ」 「ある条件が不等式ならKKT条件も必要だよ」 「双対問題(duality problem)を解けば主問題(primary problem)も解けちゃう」 ということのようだ。

なるほどなぁー

さて概要はつかめたけど、式の直感的な解釈にまでは至っていないので、もうちょっと読み深めていこう。

はじパタ8章がむずかしい

突然だがはじめてのパターン認識を読んでいる。

はじめてのパターン認識

はじめてのパターン認識

 

6章辺りまでは親切な内容だったが7章あたりからエンジンがかかってきて8章から牙を向けてきた。8章はサポートベクターマシンの導出からはじまる。8.1.2のKKT条件でラグランジュ未定定数がでてきて戸惑っている。はて…ラグランジュどこかで聞いたことが… 物理だったかな?

聞きなれない単語と数式に困りっていたけおd、直感的な解釈はWikipediaがよかった。

ラグランジュの未定乗数法 - Wikipedia

丁寧な解説はこのあたりか

ラグランジュの未定乗数法と例題 | 高校数学の美しい物語

 

にしても今は数学の丁寧な解説書や解説ページが増えたのでいい時代になったなぁ。学生時代にほしかったよ。まぁでも、いま人生でいちばん数式を楽しめている感じがするのでジックリやっていこう。

 

あ。どうもはじめまして。