パターン認識と機械学習下（第7章：その2）

以下の本を読みます。上巻を読むこともあります。何か問題点がありましたらご指摘いただけますと幸いです。

作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
出版社/メーカー: 丸善出版
発売日: 2012/02/29
メディア: 単行本
購入: 6人クリック: 14回
この商品を含むブログを見る

前回：その1 ／次回：まだ

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

7.1.1 節「重なりのあるクラス分布」からです。前回までは「特徴空間で線形分離可能」という理想的な条件を課していました。前回定式化したマージン最大化問題はそもそもこの仮定がなければ成り立ちません。(7.5) 式の不等式制約は「分類境界に最も近い点と分類境界との距離をある正の値に固定し、その他の点は分類境界からもっと離れているとする」という意味ですし、不等式制約がない形にした (7.19) も、「意図しない側にはみ出た点があれば目的関数を無限大にする」という意味になっています。ので、線形分離不可能な場合は「不等式制約を満たす $w$ と $b$ が存在しない」とか「目的関数が常に無限大にしかならない」ということになってしまいますね。

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

そうなると $w$ と $b$ が求まんないな…。でも、特徴空間で全ての点をきれいに分離できない場合でも、ほとんどの点は分離できるってこともあるだろうし…10点以内ならはみ出てもいいってするとか？いやそれだと、本当ははみ出ないような分類境界があるのに別の分類境界が求まっちゃうかも…。だから、はみ出た点の個数に応じて減点した方がよさそう？ …だけど、「1点はみ出すだけで済むけどマージンがぎりぎりな分類境界」と「2点はみ出してしまうけどマージンが広く取れる分類境界」ってどっちがうれしいんだろう…？

その辺を「どのように減点するか」で調整するのでは？ここではまず、slack 関数というものを導入するそうです。

slack？って、プロデューサーがいつも「slack の使い方がよくわからない」って言ってるやつ？

それも slack ですが…slack というのは元々「たるんだ」「怠けた」という意味の英単語のようです…割とビジネスツールらしからぬネーミングだったんですね…あ、でもウィキペディアによるとソフトウェアの方の slack はそうではなく複数の単語の頭文字なんですね。それはさておき、こちらの slack 関数は各データ点に対して定義される以下のような関数です。

$\xi_n = \begin{cases} 0 & ({\rm for \, data \, points \, that \, are \, on \, or \, inside \, the \, correct \, margin \, boundary}) \\ |t_n - y(x_n)| & ({\rm otherwise}) \end{cases}$

margin boundary って何？

いまいちどこで言葉が定義されているのかわからないんですが、「マージン境界」とは、線形分離可能な場合だったら、求まった分類境界をどちらか側のサポートベクトルにくっつくまで平行にずらした超平面のことだと思います。つまり、分類境界を挟んで2枚のマージン境界があるはずです。分類境界をマージン境界すれすれまで平行にずらしても「2クラスを正しく分類する境界」にはなります。もちろん分類境界としてあまり望ましいものではないでしょうが。まあそれで、上の slack 関数は、その点がマージン境界上かマージン境界よりも内側（正しく分類される側）ならゼロをとり、そうでない点については、「正しい正解ラベルの値（-1 or 1）」と「 $y(x_n)$ 、つまりその点の分類境界からの距離の $||w||$ 倍の値」の差の絶対値をとるということです。なお、前回決め打ったように、サポートベクトルと分類境界の距離の $||w||$ 倍は 1 に固定されています。なので、 $\xi_n = |t_n - y(x_n)|$ はぴったりマージン境界上の点なら $\xi_n = 0$ 、マージン境界ははみ出てしまったが分類境界ははみ出ていないなら $0 < \xi_n < 1$ 、ぴったり分類境界上なら $\xi_n = 1$ 、分類境界もはみ出てしまっている（誤分類）なら $1 < \xi_n$ になります。つまり、slack 関数とは、マージン境界をはみ出せばはみ出すほど大きな値をとるペナルティになっています。これを利用して、分離境界からのはみ出しを許容したのがソフトマージンSVMです。対して、前回に扱った、はみ出しを許容しない SVM がハードマージンSVMですね。

あーこれが「どれだけ減点するか」になってるのか。slack 関数っていいつつ全然「ゆるく」ないじゃん！

「ゆるい」というのは線形分離できない場合でも SVM をつかえるようにしてあげますよ、という寛容さなのでは？はみ出した点に対して寛容でどうするんです。

それもそうか…って待てよ？あのさ、もし線形分離可能じゃなかったらそもそもマージン境界とか分類境界とかなくない？サポートベクトルもないし。

なので、僕のイメージでは、線形分離可能になるように邪魔な点を取り除いたうえでサポートベクトルと分類境界を決めて、その後邪魔な点を差し戻すということだと思います。学習の経過ではどの点を邪魔にするかどんどん変えてみて、目的関数を最適化していくといった感じなのでは？実際どのように最適化していくかはまだわかりませんが…とにかくみていきましょう。今回求めたい分類境界は以下です。

$\displaystyle \underset{w, \, b}{\rm arg \, min} \; \left\{ C \sum_{n=1}^N \xi_n + \frac{1}{2} ||w||^2 \right\}$
${\rm subject \, to} \; \quad \xi_n \geqq 0 , \; \; t_n y(x_n) = t_n ( w^{\top} \phi(x) + b) \geqq 1 - \xi_n \; \quad (n = 1, \cdots , N)$ ここで、 $C>0$ は slack 関数によるペナルティをどれだけ取り入れるかを調整するパラメータですね。

…なあジュン、42ページの下から6行目くらいにある「 $C$ は訓練エラーとモデルの複雑さとのトレードオフを制御する正則化係数（の逆数）と似た役割を果たしている」って何？あと $C \to \infty$ でハードマージンSVMと等しくなるっておかしくない？その $\underset{w, \, b}{\rm arg \, min}$ を前回と同じ $\displaystyle \underset{w, \, b}{\rm arg \, min} \; \left\{ \frac{1}{2}||w||^2 \right\}$ にするには $C=0$ にしなきゃだろ？

そのままの意味ですよ。例えば線形回帰モデルの正則化項 $\displaystyle \frac{\lambda}{2} ||w||^2$ は「本当は誤差を最小化すべきところを、それを犠牲にしても $w$ の2乗ノルムを抑えたい」といった感じで、 $\lambda$ を大きくするほど制約を強くすることになりますよね。 $\lambda=0$ とすれば正則化がない場合と同じです。対して $\displaystyle C \sum_{n=1}^N \xi_n$ は「本当は1点もはみ出してはいけないところを、それをねじまげても解を求めたい」ということで、似ているがちょっと違います。いま $\xi_n$ は「その点がマージン境界以内なら 0、そうでなければはみ出るほど徐々に大きくする」と定義されていますが、元はといえばマージン境界をはみ出すことなど許されなかったんです。「その点がマージン境界以内なら０、そうでなければ $\infty$ 」というのが $\xi_n$ の本来の姿だったんです。その本来の姿に戻すには $C \to \infty$ とすればよいことがわかるでしょう？また、その本来の姿で最適解を求めるにはすべての $n$ について $\xi_n = 0$ としなければならないので不等式制約も前回の (7.5) に一致します。むしろ単に $C=0$ としてしまうと上の問題の最適解は常に $w=0$ になりますよ？各 $\xi_n$ をなるべく小さくしようという作用が失われ、不等式制約が何の制約にもなりませんので。細部までの注意が足りませんよ、ハヤト？

叱られるほどでもなくない！？だって (7.21) 式をハードマージンにするには $C \to \infty$ ってぱっとわかんないよ？本にも「一瞬 $C=0$ っぽいけど」とか何もかいてくれてないし！

それで今回のラグランジュ関数は以下です。ラグランジュ乗数は前回も出てきた $\{a_n \geqq 0\}$ に加えて $\{\mu_n \geqq 0\}$ が新しく追加されました。

$\displaystyle L(w, b, \xi, a, \mu) = \frac{1}{2} ||w||^2 + C \sum_{n=1}^{N} \xi_n - \sum_{n=1}^{N} a_n \{ t_n y(x_n) - 1 + \xi_n \} - \sum_{n=1}^{N} \mu_n \xi_n$ それで前回のように $\{a_n \}$ の最適化問題に変形すると、面白いですね。最大化すべき $\{a_n \}$ の関数は前回と全く同じになるようです。しかし、制約が違います。前回の場合は $0 \leqq a_n, \; \; \displaystyle \sum_{n=1}^{N} a_n t_n = 0$ でしたが、今回は $0 \leqq a_n \leqq C, \; \; \displaystyle \sum_{n=1}^{N} a_n t_n = 0$ になるということです。 $a_n$ に上限がつくんですね。これをみても、ソフトマージンSVMは $C \to \infty$ としたときにハードマージンSVMになることがわかりますね。

（次回があれば）つづく