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

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)も解けちゃう」 ということのようだ。

なるほどなぁー

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