2019-01-14

雑記： RNN の勾配が消失したり爆発したりする話のメモ

雑記

参考文献

ニューラルネットワークと深層学習（Web上の教材）
http://www.bioinf.jku.at/publications/older/2604.pdf（LSTM の原論文）

シチュエーション（まずL+1層パーセプトロンの場合）

$0$ 層目を入力層、 $L$ 層目を出力層として、 $0, 1, \cdots, L$ 層が連なっているとする。
$w_{jk}^l$ を、 $l-1$ 層目の $k$ 番目のニューロンから $l$ 層目の $j$ 番目のニューロンへの接続の重みとし、 $b_j^l$ を $l$ 層目の $j$ 番目のニューロンのバイアスとする（ $l =1, \cdots. L$ ）。
を番目の番目のニューロンの活性化前の値、を番目の番目のニューロンの活性化後の値とする。つまり、活性化関数をとすると、以下の関係が成り立つ。
$\displaystyle a_j^l = \sigma( z_j^l ) = \sigma \left( \sum_k w_{jk}^l a_k^{l-1} + b_j^l \right)$
- $z_{j}^l$ と $a_{j}^l$ はニューラルネットワークへの入力ベクトル $x$ に依存する $z_{j}^l(x)$ と $a_{j}^l(x)$ だが、いまはある入力ベクトルに固定されていると考えて $(x)$ を省略する。
- それぞれの文字の下の添え字を取ってベクトル（重みについては行列）とみなすと $a^l = \sigma( w^l a^{l-1} + b^l )$ ともかける。
コスト関数をとする（例えば正解とニューラルネットワークの出力の2乗誤差など）。
- 但し、 $C$ がニューラルネットワークの出力 $a_j^L$ の関数でかかれていることは仮定する。

やりたいこと

任意の $l, j, k$ について $\displaystyle \frac{\partial C}{\partial w_{jk}^l}$ 及び $\displaystyle \frac{\partial C}{\partial b_{j}^l}$ を求めたい（これらを求める1つの手続きを知りたい）。

やり方

まず、 $C$ の最終出力 $a_j^L$ に関する偏微分 $\displaystyle \frac{\partial C}{\partial a_j^L}$ はただちに求まる。
次に、 $C$ の最終出力の活性化前の値 $a_j^L$ に関する偏微分を考えると、上の $\displaystyle \frac{\partial C}{\partial a_j^L}$ を利用して以下のようになる。

$\displaystyle \frac{\partial C}{\partial z_j^L} = \frac{\partial C}{\partial a_j^L} \frac{\partial a_j^L}{\partial z_j^L} = \frac{\partial C}{\partial a_j^L} \sigma' (z_j^L)$

さらに、最終層の1つ手間の層の活性化前の値 $a_j^{L-1}$ に関する偏微分を考える。最終層の全ニューロンの活性化前の値に関する偏微分をつかって以下のようにかける。

$\displaystyle \frac{\partial C}{\partial z_j^{L-1}} = \sum_k \frac{\partial C}{\partial z_k^L} \frac{\partial z_k^L}{\partial z_j^{L-1}} = \sum_k \frac{\partial C}{\partial z_k^L} \frac{\partial \displaystyle \sum_m \Bigl( w_{km}^{L} \sigma(z_m^{L-1}) + b_k^{L} \Bigr) }{\partial z_j^{L-1}} = \sum_k \frac{\partial C}{\partial z_k^L} w_{kj}^{L} \sigma ' (z_j^{L-1})$

この要領で遡っていけば、1層目の $z_j^1$ に関する偏微分までかける。つまり、ネットワーク中の全てのニューロン $z_j^l$ に関する $C$ の偏微分が明示的に求まる。

そうなると任意の $l, j, k$ について $\displaystyle \frac{\partial C}{\partial w_{jk}^l}$ 及び $\displaystyle \frac{\partial C}{\partial b_{j}^l}$ を求めるのは容易で、つまり、以下のようにかける。
$\displaystyle \frac{\partial C}{\partial w_{jk}^l} = \frac{\partial C}{\partial z_j^l} \frac{\partial z_j^l}{\partial w_{jk}^l} = \frac{\partial C}{\partial z_j^l} \frac{\sum_k w_{jk}^l a_k^{l-1} + b_j^l}{\partial w_{jk}^l} = \frac{\partial C}{\partial z_j^l} a_k^{l-1}$
$\displaystyle \frac{\partial C}{\partial b_j^l} = \frac{\partial C}{\partial z_j^l} \frac{\partial z_j^l}{\partial b_j^l} = \frac{\partial C}{\partial z_j^l} \frac{\sum_k w_{jk}^l a_k^{l-1} + b_j^l}{\partial b_j^l} = \frac{\partial C}{\partial z_j^l}$

RNN の場合

入力層と出力層しかないニューラルネットワークを考える。出力層が1層しかないので $a_u$ や $z_u$ の右上の添え字を省く。この出力層をまた入力層につなげてループさせるとする。すると、何回ループしたときの出力なのかの区別が必要なので、 $a_u(t)$ や $z_u(t)$ とかく。 $\displaystyle \delta_u(t) \equiv \frac{\partial C}{\partial z_u(t)}$ とおく。
1ループ前への伝播は以下のようになる。

$\displaystyle \frac{\partial \delta_v(t-1)}{\partial \delta_u(t)} = f' \bigl( z_v(t-1) \bigr) w_{uv}$

$q$ ループ前への伝播は以下のようになる。

$\begin{eqnarray*}\frac{\partial \delta_v(t-q)}{\partial \delta_u(t)} &=& \sum_k \frac{\partial \delta_v(t-q)}{\partial \delta_k(t-q+1)} \frac{\partial \delta_k(t-q+1)}{\partial \delta_u(t)} \\ &=& \sum_k f' \bigl( z_v(t-q) \bigr) w_{kv} \frac{\partial \delta_k(t-q+1)}{\partial \delta_u(t)} \\ &=& f' \bigl( z_v(t-q) \bigr) \sum_k w_{kv} \frac{\partial \delta_k(t-q+1)}{\partial \delta_u(t)}\end{eqnarray*}$

途中経過がわかりやすいようにユニットの添え字を取り直す。時刻 $t$ のユニット $l_0$ から時刻 $t-q$ のユニット $l_q$ への伝播は以下のようになる。

$\begin{eqnarray*} \frac{\partial \delta_{l_{q}}(t-q)}{\partial \delta_{l_0}(t)} &=& f' \bigl( z_{l_{q}}(t-q) \bigr) \sum_{l_{q-1}} w_{{l_{q-1}}{l_{q}}} \frac{\partial \delta_{l_{q-1}}(t-q+1)}{\partial \delta_{l_0}(t)} \\ &=& f' \bigl( z_{l_{q}}(t-q) \bigr) \sum_{l_{q-1}} w_{{l_{q-1}}{l_{q}}} \left[ f' \bigl( z_{l_{q-1}}(t-q+1) \bigr) \sum_{l_{q-2}} w_{{l_{q-2}}l_{q-1}} \frac{\partial \delta_{l_{q-2}}(t-q+2)}{\partial \delta_{l_0}(t)} \right] \\ &=& \sum_{l_{q-1}} \sum_{l_{q-2}} \left[ \prod_{m=q-1}^{q} \Bigl( f' \bigl( z_{l_{m}}(t-m) \bigr) w_{{l_{m-1}}{l_{m}}} \Bigr) \frac{\partial \delta_{l_{q-2}}(t-q+2)}{\partial \delta_{l_0}(t)} \right] \\ &=& \sum_{l_{q-1}} \cdots \sum_{l_{1}} \left[ \prod_{m=2}^{q} \Bigl( f' \bigl( z_{l_{m}}(t-m) \bigr) w_{{l_{m-1}}{l_{m}}} \Bigr) \frac{\partial \delta_{l_{1}}(t-1)}{\partial \delta_{l_0}(t)} \right] \\ &=& \sum_{l_{q-1}} \cdots \sum_{l_{1}} \prod_{m=1}^{q} \Bigl( f' \bigl( z_{l_{m}}(t-m) \bigr) w_{{l_{m-1}}{l_{m}}} \Bigr) \end{eqnarray*}$

よって、時刻 $t$ でのユニット $l_0$ の誤差を、時刻 $t-q$ のユニット $l_q$ の誤差まで伝播させるのに、 $m=1, 2, \cdots, q$ に対して $f' \bigl( z_{l_{m}}(t-m) \bigr) w_{{l_{m-1}}{l_{m}}}$ が掛け合わさっていく。そのため、さかのぼるステップ数 $q$ が大きいとき、絶対値の組み合わせによっては、勾配は発散するか、消滅する（これは RNN に限った話ではないが、通常の MLP では多層化のレベルはたかが知れているのに対して、RNN で長期の依存性を学習したい場合は特に問題になってくる；また、同じ重み $w_{uv}$ を何回も通る伝播パスが存在する）。

2019-01-13

Reinforcement Learning: An Introduction〔Second Edition〕（その4）（途中）

本読み強化学習

以下の本を読みます。何かお気付きの点がありましたらご指摘いただけますと幸いです。
Sutton & Barto Book: Reinforcement Learning: An Introduction

〈参考〉過去に強化学習についてかいたものへのリンク

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

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

1.1 節の3ページの1段落目までの内容はこうでした。

強化学習とは、未知の MDP の上で得られる報酬の和を最大化する方策を学ぶ枠組みである。
強化学習には、正解の行動の教師データはないので、自分で見つけ出すしかない（トライ＆エラー）。
強化学習では、目先に最大の報酬が得られる行動を選択すればよいということではない（遅延報酬）。
強化学習では、探索と知識利用の一方を選択するともう一方をあきらめざるをえないので（ジレンマ）、どのようにバランスをとるか英断する必要がある。

3ページ2段落目は…強化学習のまた別の特徴として、問題の全体を明示的に考慮する…？要領を得ません。

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

…例えば、教師あり学習は、「未知のメールがスパムかそうでないかを判定するために学習データから学習する方法」を教えてくれるよね。なら強化学習が教えてくれるのは、「スパム判定器の精度を向上させていくためにエージェントはどう行動べきか計画する」方法だ。強化学習が達成してくれることの方がより私たちの現実のゴールに近くて、強化学習以外の機械学習分野が扱うのは subproblem にすぎない。教師あり学習のノウハウをつかえば「スパム判定器」を用意できる。どれくらいよい判定器か訊かれたら「テストデータの判定精度99.9%」とか答えることもできるね。でもそれって判定器が実際どれくらい役に立つのかの答えになってない。判定器がどれくらい役に立つかって、これから実際に届くメールの生成モデルの上で計測すべきだからね。テストデータとは分布にずれがあるかもしれないし、実際のメールの生成モデルは時間変化していくかもしれない。実際スパムメールの特徴って年々変化していくかもしれないしね。それに、スパム判定器が優秀であまりにスパムメールをブロックしてしまうせいでスパムメールの手口が巧妙化していく、のように、スパム判定器とメール生成モデルは相互作用しうる。…まあ時間変化とか相互作用しないまでも、もしテストデータを生成したのと同じ生成モデルが期待されるとして、「判定精度99.9%」がどれくらい信頼できるスコアなのかわからないしね。テストデータがたまたま判定しやすいメールばかりに偏っていた可能性もある。だから強化学習のように生成モデル（環境）を用意してその上でどう意思決定していくかを計画した上で効果を計測するのが本来的、という話だと思う。

つづきは後で

2019-01-12

雑記： 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次なのでこの場合は必ず極小点というか最小点になります。

つづきは後で

2019-01-11

雑記：サポートベクターマシンの最適化問題まで

雑記

サポートベクターマシンって何がしたいのという話です（この最適化問題をカーネル関数の式に書き換えるまでやらないと片手落ちではあります）。
（暗いがより解像度が高い画像はこちら：https://pbs.twimg.com/media/DwoggizVYAAQ2j2.jpg:large）
f:id:cookie-box:20190112001238j:plain

2019-01-10

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

本読み機械学習

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

パターン認識と機械学習下 (ベイズ理論による統計的予測)

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

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

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

そうなると $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になることがわかりますね。

（次回があれば）つづく