雑記： SVMのラグランジュ乗数法と双対問題（途中）

何か問題点がありましたらご指摘いただけますと幸いです。

f:id:cookie-box:20180305231302p:plain:w60

前々回の PRML 読み（パターン認識と機械学習下（第7章：その1） - クッキーの日記）でプロデューサーがハードマージンSVMの最適化問題を解いてたと思うんだけど、よくみるとなんかおかしいんだよな…。

f:id:cookie-box:20180305232608p:plain:w60

何がですか？

元々のラグランジュ関数ってこれだろ？本の (7.7) 式かな。

$\displaystyle L(w, b, a) = \frac{1}{2} ||w||^2 - \sum_{n=1}^{N} a_n \{ t_n (w^{\top} \phi(x_n) + b) - 1 \}$ 俺たちはこれを「最大化」するのと「最小化」するのとどちらをしたいのかといったら「最小化」したいんだよな？いま訓練データと分類境界の最短距離が $1 / ||w||$ で、これを最大化したいんだから、 $\displaystyle \frac{1}{2}||w||^2$ を最小化しないとだし。第2項についてはどうしたいのかはよくわかんないけど、これがあるから最小化から最大化に逆転するってこともないだろ？まあそれで、上の式を解くのに、普通に $w$ と $b$ を求めてもいいと思うんだけど、カーネル関数の話にしたいから $w$ と $b$ を消去して (7.10) 式にしたわけじゃん。 $\displaystyle \tilde{L}(a) = \sum_{n=1}^{N} a_n - \frac{1}{2}\sum_{n=1}^{N} \sum_{m=1}^{N} a_n a_m t_n t_m k(x_n, x_m)$ だから、これを最小化すればいいんだなって思ったら「 $a$ について最大化すればよい」ってかいてあるじゃん！なんで？いつの間に最大化問題になってたの？おかしくない？？

…まず、いますべての $n$ で $a_n \geqq 0$ なので、 $\tilde{L}(a)$ を最小化しようとしたら常に解は $a_n = 0 \; (n=1, \cdots, N)$ になりますね。つまり、ハードマージンSVMの解は常に $w=0$ であるというおかしな話になってしまいます。しかし、だから最大化するというのも説明になりません。それではハヤトの疑問の答えになっていませんね。話を整理しましょう。僕たちはある制約下で $\displaystyle \frac{1}{2}||w||^2$ を最小化したい、というのは間違いないです。そこまではいいです。それで、制約付き最小化問題の解を求めるために、ラグランジュ関数の助けを借りることにしました。それもいいです。しかし、「ラグランジュ関数を最小化したい」のかというと、そういうことではありません。それはラグランジュ関数の役割に誤解があります。ラグランジュ関数の役割は、「あなたの求める答えはラグランジュ関数の停留点（ $\nabla_{w, b}L(w, b, a) = 0$ となる $(w, b)$ ）に絞れます」です。以下の本により詳しい話があるのでみてみましょう。

サポートベクターマシン入門

作者: ネロクリスティアニーニ,ジョンショー‐テイラー,Nello Cristianini,John Shawe‐Taylor,大北剛
出版社/メーカー: 共立出版
発売日: 2005/03/01
メディア: 単行本
購入: 8人クリック: 135回
この商品を含むブログ (42件) を見る

この本の5章が「最適化の理論」です。この本の5章では以下の形に表せる最適化問題の性質を議論します。ただし、 $f(w)$ は凸な2次関数で、不等式制約 $g_i(w)$ 及び等式制約 $h_i(w)$ は線形関数とします。 $\displaystyle \begin{split} & {\rm minimise} & \quad f(w), & \qquad w \in \Omega, \\ & {\rm subject \; to} & \quad g_i(w) \geqq 0, & \qquad i = 1, \cdots, k, \\ & & \quad h_i(w) = 0 ,& \qquad i = 1, \cdots, m\end{split}$

明らかにハードマージンSVMもソフトマージンSVMもこの形にあてはまっています。PRML では変数が $w, \, b$ （ソフトマージンSVMなら $w, \, b, \, \xi$ ）でしたが、それらの変数を全て連結したのがこちらの本の $w$ と考えていいでしょう。PRML における $\displaystyle \frac{1}{2}||w||^2 + C \sum_{n=1}^{N} \xi_n$ は、 $\displaystyle\left(\begin{array}{c} w \\ b \\ \xi \end{array}\right)$ の2次の項までを含む関数ですよね。なおかつ凸（ヘッセ行列が半正定値）です。ただ $b$ や $\xi$ については0次とか1次なので、狭義凸にはなっていませんが。そして、制約 $t_n ( w^{\top} \phi(x) + b) \geqq 1 - \xi_n$ や $\xi_n \geqq 0$ は $\displaystyle\left(\begin{array}{c} w \\ b \\ \xi \end{array}\right)$ の線形関数です。

なお、目的関数が2次関数で、不等式制約と等式制約が線形関数な最適化問題を2次計画問題（quadratic programming）というそうです。また、目的関数とすべての制約が凸関数で、最適解を探索する領域 $\Omega$ も凸（※）である最適化問題を凸最適化問題（convex optimisation problem）とよぶと。目的関数が凸だと、 $w^{\ast}$ が局所最小解ならば必ず大域最小解になるのでこれはありがたいです。まとめると上記の問題は、2次計画問題かつ凸最適化問題である、凸2次計画問題といわれるクラスの最適化問題になります。

※	領域 $\Omega \subseteq \mathbb{R}^n$ が凸であるとは、 $\Omega$ 内の任意の2点の任意の内分点が $\Omega$ 内にあることです。例えば3次元空間内の球は凸ですが、ドーナツは凸ではないです。SVM の状況では $w,\,b, \, \xi$ の成分は（不等式制約を入れる前は）どの実数をとってもいいので $\Omega = \mathbb{R}^{M + 1 + N}$ であり、 $\Omega$ は凸です。

2次計画問題の「計画」って何なんだ…英語が planning ってわけでもないし謎だな…まあいいや。その凸2次計画問題を解く方法を早く知りたい！

ええ、最適化理論では「最適点はどのような性質を満たすのか」「では具体的にどのような手続きでその最適点にたどり着けばいいのか」を議論しますが、この本の5章のスコープは前者であるようですね。では「凸2次計画問題の最小点はどのような性質を満たすのか」をみていきましょう…といいたいところですが、いきなり凸2次計画問題にとびつくのではなく、順を追っていきましょう。まずそもそも、等式制約も不等式制約もない場合、最小点はどのような点になるでしょうか。どうなりますか、ハヤト？

え、何も制約がない場合？ただ単に $f(w)$ を最小化したいってことだよな。だったら、 $\displaystyle \frac{\partial f(w)}{\partial w}=0$ を満たす $w$ がどこか求めるって感じじゃないの？ …あれ、間違ってる？

いえ、正しいですよ。まず、 $f(w)$ の最小点 $w^{\ast}$ では $\displaystyle \frac{\partial f(w)}{\partial w}=0$ です。 $0$ でないならば、その点に置いたビー玉は $f(w)$ がもっと小さいところに転がりますからね。傾きがあるので。最小点はビー玉がその点から転がらない、停留点でなければなりません。また、いま $f(w)$ は凸な2次関数としているので、 $\displaystyle \frac{\partial f(w)}{\partial w}=0$ ならば（停留点ならば）その点で $f(w)$ は最小である、と逆向きもいえるわけです。もし2次関数でも凸でなかったら停留点は最小点ではなく最大点かもしれませんし、2次関数でもなかったら停留点は局所最小点にすぎなかったり鞍点だったりするかもしれませんので、一般的にはこの逆向きの方はいえません。この「最小点ならば停留点である」＝「停留点さえ調べればその中に最小点がある」という定理（定理5.5）を、フェルマーの定理といいます…が、フェルマーの定理と日本語で検索しても中々この定理は出ませんね…フェルマーの定理といって、フェルマーの小定理や大定理（最終定理）という異なる定理を指している場合もあるようです。「フェルマーの定理停留点」と検索しても今度は光学のフェルマーの原理とか引っかかってきますし…。

じゃあ人と話すとき、「最小点は停留点である」の意味で「フェルマーの定理」っていってもすれ違っちゃうかもだから気を付けた方がいいな…。でも、フェルマーってそんなにたくさんの定理を証明したんだな！

最終定理は証明してくれなかったんですけどね…本題に戻りましょう。次は等式制約を加えてみましょう。

$\displaystyle \begin{split} & {\rm minimise} & \quad f(w), & \qquad w \in \Omega, \\ & {\rm subject \; to} & \quad h_i(w) = 0 ,& \qquad i = 1, \cdots, m\end{split}$ この最小点はどこにあるでしょうか？

えー…今度は $\displaystyle \frac{\partial f(w)}{\partial w}=0$ じゃダメだよな…これで求まった点が都合よく $h_i(w) = 0 \; (1, \cdots, m)$ を満たしてくれるわけないだろうし…。…あれ、でも $h_1(w) = 0$ をつかえば $w$ の成分を1つ消去できるよな。 $h_m(w) = 0$ までつかえば $m$ 個消去できるはずだ。そうやって消せるだけ消した上で残りの未知変数に対して $f(w)$ を偏微分すれば制約を守って $f(w)$ を最小化できる！

…まあそれで解けるんですよね。 $h_i(w)$ が線形なら未知変数を消去することはできるはずですし。ただ今回は諸事情によりそのような解き方をしません。そう解いてしまうと上手く双対問題にできないですし、そもそも $h_i(w) = 0$ を解くのも面倒です。なので、今回は $h_i(w) = 0$ が $w_{1:m}$ について陽に解けない場合でも適用できる方法を紹介します。

俺が考えた意味！

しばらく等式制約が線形という条件がなくても成り立つ話をします。まず等式制約が1本のみの場合を考えます。 $h_1(w) = 0$ という等式制約は、 $\mathbb{R}^n$ 内を自由に動き回るはずだった $w$ を $n-1$ 次元に閉じ込めます（※）。この $n-1$ 次元曲面（※）上で、ベクトル $\nabla h_1(w)$ は曲面に垂直です。もし垂直でなかったら、この曲面上に置いたポテンシャル $h_1(w)$ を受けるビー玉は曲面上をいずこかに転がってしまいますが、この曲面上ではどこも $h_1(w)=0$ なので、ビー玉はどちらにも転がってはいけませんので。そして、この曲面上であって $f(w)$ が最小になる点を探したいわけですが、その点ではベクトル $\nabla f(w)$ もまた曲面に垂直です。もし垂直でなかったら、ポテンシャル $f(w)$ を受けるビー玉は曲面上を転がってしまい、転がった先では $f(w)$ がより小さいはずなので。つまり、求める最小点では $\nabla f(w) \parallel \nabla h_1(w)$ なんです。まとめると、いま考えている等式制約付き最小化問題の最小点は「曲面 $h_1(w)=0$ 上にあって、 $\nabla f(w) + \beta_1 \nabla h_1(w) = 0$ が成り立つ点」でなければなりません。 $\beta_1$ はゼロでない定数です。

ビー玉置きすぎだろ！

次に等式制約がもう1本、 $h_2(w)=0$ もある場合を考えます。いま $w$ が動き回れるのは曲面 $h_1(w)=0$ と曲面 $h_2(w)=0$ の交わりの曲面です（※）。この曲面上を移動するには、 $\nabla h_1(w)$ にも $\nabla h_2(w)$ にも垂直に進まなければなりません。そして、最小点では「『 $\nabla h_1(w)$ にも $\nabla h_2(w)$ にも垂直』という方向にしか進めないのではこれ以上 $f(w)$ を減らすことができない」となっているはずです。つまり、 $\nabla f(w)$ が $\nabla h_1(w)$ と $\nabla h_2(w)$ が張る面内にあるんです。よって、最小点は「曲面 $h_1(w)=0 \; \land h_2(w)=0$ 上にあって、 $\nabla f(w) + \beta_1 \nabla h_1(w)+ \beta_2 \nabla h_2(w) = 0$ が成り立つ点」です。等式制約が $m$ 本ある場合も同様に、最小点は、全ての等式制約を満たす曲面上であって、以下が成り立つ点です。

$\displaystyle \nabla f(w) + \sum_{i=1}^{m} \beta_i \nabla h_i(w) = 0$ 最小点がこの性質を満たすことをラグランジュの定理といいます。

…ジュンあのさ、さっきから「等式制約を満たすある点が最小点だったら、その点に置いたポテンシャル $f(w)$ を受けるビー玉は、等式制約を満たす面に閉じ込められているならば、そこから転がっていかない」みたいな感じで話進んでる気がするんだけど、確かに最小点だったら $f(w)$ がもっと減る方向に動けたらいけないけど、逆にそういう動けない点だったら最小点なの？

違いますよ？僕がいっているのは最小点である必要条件であって、十分条件ではありません。

え？じゃあ十分条件も求めなきゃ…。

ラグランジュの定理はこれでじゅうぶん便利なんですよ。最小点が空間内のどこにあるのか全くわからなかったのが、上の性質を満たす点に絞れただけでもうれしいでしょう？ラグランジュの定理の式を解いて求まった点が極小点であるか極大点であるかそのどちらでもないのかはその点におけるヘッセ行列の固有値を確かめるべきです。もっとも、SVMの最適化問題では $f(w)$ が凸で2次なのでこの場合は必ず極小点というか最小点になります。

つづきは後で