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

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

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

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

前回：第6章その6 ／次回：まだ

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

第7章は「疎な解を持つカーネルマシン」ですね。

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

この章のタイトルだけ雰囲気違くない？なんかラノベのタイトルっぽくない？

そうなんですか？ラノベのタイトルって「俺の疎な解を持つカーネルマシンの学習が収束しないのはお前らが悪い」みたいなのじゃないんですか？

他人のせいにするなよ！

導入を読むと「疎な解」というのはおそらくこういうことなんですね。カーネル法は可算無限個の重みの最適化を有限個の重みの最適化に変換してくれる手法ですが、有限個といっても訓練データの個数なのでそれもそれで多く、学習にも予測にも計算コストがかかります。しかし、重みの解が疎な場合には計算コストを抑えることができる。本章ではそのような場合をピックアップするということだと思います。というか取り扱うモデルは次の2つですね。7.1 節が SVM（サポートベクトルマシン）と、7.2 節が RVM（関連ベクトルマシン）です。前者では出力の事後確率は得られませんが、後者では事後確率の推定ができるらしいです。

事後確率が得られないっていうと、スパムメールかどうかの分類はしてくれるけど、どれくらいの確率でスパムメールかまでは教えてくれないってことだよな。

7.1 節で最初に出てくる2値分類問題は第6章の最終回で参考にした「学習システムの理論と実現」の「第3章カーネルマシン」で出てくる話とむしろ同じですね。まずカーネル関数のことは忘れて素朴に考えます。いま、モデル $y(x) = w^{\top} \phi(x) + b$ を、訓練データ $\{ (x_n, t_n) \}_{1 \leqq n \leqq N}$ で学習したいです。ただし $t_n \in \{-1, \, 1\}$ です。なお、訓練データは特徴空間で線形分離可能とします。このとき一般には、特徴空間において $-1$ のサンプルたちと $1$ のサンプルたちを分離する超平面は無数に存在します。サンプルたちを分離する超平面が1つあったら、それをほんの少しずらしてもやはりサンプルたちを分離しているでしょうから。訓練データを分離するだけなら無数にある超平面のどれを選んでも違いはありませんが、未知のデータの識別への適用を考えると、あまりサンプルすれすれで分離するような超平面は選びたくないものです。なので、方針として、分離超平面の中でも分離超平面に最も近いサンプルまでの距離が最大であるものを求める解とします。このように学習することを「マージン最大化」といい、そうやって学習したモデルが SVM ですね。なぜマージン最大化するのかは改めて後の節で説明があるようですが、36～37ページの説明によると、クラスごとに Parzen 推定法（分散 $\sigma^2$ のガウスカーネル）で密度推定し、その密度をもとに誤分類率が最小となる超平面を求めると、 $\sigma \to 0$ の極限でマージン最大超平面と一致するそうです。なぜそうなるかは $\sigma$ を $0$ に近づけるにつれ分離超平面はサポートベクトル以外のデータ点からの影響を受けなくなるから…この後40ページで初めて出てくるサポートベクトルという単語を37ページで使ってきましたね…。

てかその説明いる？マージン最大な分離超平面の方がよさそうだからでよくない？

…僕たちは分類器を学習するとき、何も訓練データにおける損失関数を最小化したいわけではないはずです。未知の点を分類したいはずなんです。であれば、即座に訓練データを分離する超平面を探すのではなく、クラス毎の密度を推定するのが誠実な手順といえると思います。36～37ページの主張は、ある密度推定をしたもとでの誤分類率最小分離超平面の極限がマージン最大分離超平面に一致するというものですから、マージン最大化に正当な意味を与えているでしょう？なぜマージン最大化をしたのかと訊かれたとき、その方がよさそうだから、では回答として曖昧でしょう？

はい。

線形分離可能な仮定のもとでは、点 $x_n$ から分離超平面 $y(x)=w^{\top} \phi(x) + b=0$ までの距離は $\displaystyle \frac{t_n y(x_n)}{||w||} = \frac{t_n(w^{\top} \phi(x_n) + b)}{||w||}$ なので、解きたいマージン最大化問題は $\displaystyle \underset{w, \, b}{\rm arg \, max} \; \left\{ \frac{1}{||w||} \underset{n}{\rm min} \bigl( t_n(w^{\top} \phi(x_n) + b) \bigr) \right\}$ ですね。どう解きますか、ハヤト？

えっ？ 1番近いデータ点までの距離が最大になるように超平面のパラメータ $w, \, b$ を探すんだよな… $\underset{n}{\rm min}$ ってのが邪魔だよな。どれがマージン最大な分離超平面に一番近い点かって最初からわかんないし。そこがなければ普通に $w, \, b$ についての勾配が求まるんじゃない？

ええ、 $\underset{n}{\rm min}$ は邪魔ですね。そこで、 $w, \, b$ には定数倍の自由度があることを利用します。 $\displaystyle \underset{n}{\rm min} \bigl( t_n(w^{\top} \phi(x_n) + b) \bigr) = 1$ としてしまうんです。そういう $w, \, b$ を選ぶと決めるんです。そうすれば先の最大化問題は $\displaystyle \underset{w, \, b}{\rm arg \, max} \; \left\{ \frac{1}{||w||} \right\}$ となって、邪魔だった $\underset{n}{\rm min}$ が消えます。

まるっと消えた！？あれでも、その最大化問題って常に $w$ をゼロベクトルに近づけろ、みたいなことにならない？てか最大値発散しない？

もちろん、 $w, \, b$ に入れた制約を無視してはいけません。いま $t_n(w^{\top} \phi(x_n) + b)$ という値はこれが最小となる $n$ で $1$ とすると決めたので、すべての $n$ で $t_n(w^{\top} \phi(x_n) + b) \geqq 1$ でなければなりません。この不等式制約の下で $\displaystyle \underset{w, \, b}{\rm arg \, max} \; \left\{ \frac{1}{||w||} \right\}$ を解きます（二次計画問題）。というか計算上の便利のために $\displaystyle \underset{w, \, b}{\rm arg \, min} \; \left\{ \frac{1}{2}||w||^2 \right\}$ に読み替えます。このような不等式制約下での最大／最小化問題はラグランジュ乗数法においてラグランジュ乗数に $\lambda \geqq 0$ という制約を入れると解くことができます。かなり見づらいですが2次元の特徴空間で適当な4つのデータ点で計算してみたのが以下のノートです。というか2枚目の1行目までは一般的な話です。1枚目の矢印の直前までは $w, \, b$ を最適化しようとしていたんですが、矢印の直後では $w, \, b$ を消してしまって $\{a_n\}$ の最適化問題に変換してしまっています。これがマージン最大化問題の双対表現です。

※ 矢印の根元の近くの $\sqrt{w_1^2 + w_2^2}$ は $(w_1^2 + w_2^2)$ の誤りです。

f:id:cookie-box:20190106210832p:plain:w620

f:id:cookie-box:20190106210902p:plain:w620

へー、不等式の制約があっても解けるんだ。…ってあれ？一番下のとこ、最終的にまた不等式の制約がある最大化問題になってない？プロデューサーはこっからどうやって解いたの？

はい、再び二次計画問題になるんです。この解き方は 7.1.1 節で議論するようです。なおプロデューサーさんは上の最大化を場合分けで解こうとしてよくわからなくなり R の optim 関数の力を借りました。

そっか…。

ちなみに、ノートの2枚目の1行目の式から、双対表現において特徴空間の点の座標は内積（カーネル関数）としてのみ現れるのがわかります。また、 $\displaystyle \frac{\partial L}{\partial w} = 0 \Leftrightarrow w = \sum_{n=1}^{N} a_n t_n \phi(x_n)$ より、最適解が $\displaystyle y(x) = \sum_{n=1}^{N} a_n t_n k(x, x_n) + b$ と例によって「サンプル点におけるカーネル関数の重み付き和」になっていることがわかります。つまり、この最適解は再生核ヒルベルト空間の元の中で最もよい解です。

…レプリゼンタ定理って不等式制約あってもいいの？

…すみません、よくわからなかったんです。ただ、マージン最大化問題は、不等式制約付き最大化問題の形の他に、40ページの (7.19) 式の最小化問題の形にもかけるということです。こちらであれば不等式制約がありません。ただ、この $E_{\infty}$ という関数は $\infty$ をとるということで、これは実数値関数とはいえません。レプリゼンタ定理では、ここは実数値関数でなければならないので…ただ、結果的には大丈夫なんだろうとは思います。39ページに戻ると、このマージン最大化問題におけるカーネル関数もまた正定値である必要があるという記述がありますね。正定値だと最大化すべきラグランジュ関数が上に有界になると。PRML においてカーネル関数は個別事例で出てくるので、毎度カーネル関数が満たすべき性質を確認しているのかもしれません。

40ページの、「すべてのデータ点について $a_n=0$ あるいは $t_n y(x_n) = 1$ が成り立つ」って？

上のノートだと、右上の白い点には $a_n=0$ が成り立ち他の3点には $t_n y(x_n) = 1$ が成り立ちます。 $t_n y(x_n) = 1$ が成り立つというのはすなわちその $n$ 番目の点が分離超平面に最も近いということです。最も近いなら $t_n y(x_n) = 1$ とすると決めたので。上のノートの例だと分離超平面に最も近い点が3点存在します。そしてこの3点の座標のみが分離超平面をどこに引くべきかに影響を及ぼします。右上の白い点は（結果的にですが）分離超平面に影響を及ぼしていません。未知の点に対する予測時に、未知の点とこの点とのカーネルは使わないんです。 $a_n=0$ というのはそういうことです。逆に予測に影響を及ぼす $a_n \neq 0$ である点をサポートベクトルといいます。上のノートの例だと右上の白い点を除いた3点がサポートベクトルです。この例だと全データ4点中3点がサポートベクトルなのでわかりづらいですが、現実の場面では普通全データ数が膨大で、サポートベクトルであるデータ数はそれに比べると僅かになります。これが SVM が「疎な解」たる所以で、予測の計算コスト上とてもうれしい性質です。

あー結果的に右上の白い点は存在しないのと同じなんだな。最初からはわかんないけど。40ページの続きにはバイアスパラメータ $b$ の求め方があるな。でも $b$ って双対表現に書き換えるために $w, \, b$ を消去したとき $\{a_n\}$ の式で表してたんじゃないの…って違うな。それは $w$ の方だけで $b$ は勝手に消えたのか。プロデューサーってどうやって $b$ 求めたの？

ええ、困ったのでサポートベクトルであるデータ点を1つ選んで $t_n(w^{\top} \phi(x_n) + b) = 1$ を $b$ について解きました。しかし、この解き方はカーネル法の文脈では不可ですね。 $\phi(x_n)$ を陽に扱ってはいけませんから。カーネル法における正しいバイアスパラメータ $b$ の求め方は、この式に $w = \sum_m a_m t_m \phi(x_m)$ を代入して $t_n(\sum_m a_m t_m k(x_n, x_m) + b) = 1$ を解くことです（式 7.17）。理論上はサポートベクトルのうち任意の1点を選べば $b$ は求まりますが、実用上は数値誤差抑制の観点から全てのサポートベクトルから $b$ を求めて平均するようですね。

（次回があれば）つづく