Prml7

written

疎な解を持つカーネルマシーン

カーネル法では、データ集合のサイズの2乗分の計算をしなければならなかったので、もっと疎な解を使ってカーネル関数を扱うことを考える。ここでは、SVMとRVMついてみる。

SVM

SVMでは、決定超平面と教師データとの最小の距離を持つベクトルをサポートベクターとしてサポートベクターとの距離マージンを最大するような決定超平面を決める。

クラス分類

線形モデルを用いて、２クラス問題を解くことを考える。線形モデルは、 \[y(x)=w^{\mathrm{T}}\phi(x)+b\] となる。教師データは、\(t\in\{-1.1\}\)となるデータを使い、符号により分類するとする。決定面との距離は、 \[\frac{t_{n}y(x_{n})}{||w||}=\frac{t_{n}(w^{\mathrm{T}}\phi(x_{n})+b)}{||w||}\] となる。ここで求めたいのは、マージンを最大する\(w\)と\(b\)なので、 \[\mathrm{argmax}_{w,b}\{\frac{1}{||w||}\min_{n}[t_{n}(w^{\mathrm{T}}\phi(x_{n})+b)]\}\] を解ければよい。ここで、パラメータを定数倍しても解は変わらないので、適切に定数倍すると、サポートベクターについて、 \[t_{n}(w^{\mathrm{T}}\phi(x_{n})+b)=1\] で表せる。これにより、成約式 \[t_{n}(w^{\mathrm{T}}\phi(x_{n})+b)\leq1\] が成り立ち、求めるべきは、 \[\mathrm{argmin}_{w,b}\frac{1}{2}||w||^{2}\] を制約式のもとでとくことになる。ここで、訓練集合にもノイズが含まれていることを考える。正しく分類された場合は0、誤って分類された場合は、\(|t_{n}-y(x_{n})|\)を表すスラック変数\(\xi\)を導入する。スラック変数が、1以下の時には、正しく分類されていると考えることで、多少の誤差も許容する用になる。これにより \[C\sum_{n=1}^{N}\xi_{n}+\frac{1}{2}||w||^{2}\] を最小にするパラメータを決める問題になる。また制約式は、 \[t_{n}y(x_{n})\leq1-\xi_{n}\] となる。Cは正則化係数と似たような働きをする。この最小化問題を解くためにラグランジェ未定乗数をもいてラグランジェ関数を定義すると、 \[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}\)と\(\mu_{n}\)はラグランジェ乗数である。対応するKKT条件は、 \[a_{n}\leq0\] \[t_{n}y(x_{n})-1+\xi_{n}\leq0\] \[a_{n}(t_{n}y(x_{n})-1+\xi_{n})\] \[\mu_{n}\leq0\] \[\xi_{n}\leq0\] \[\mu_{n}\xi_{n}\leq0\] となる。ここで、各パラメータにおける極値をもとめると、 \[\frac{\partial L}{\partial w}=0\Rightarrow w=\sum_{n=1}^{N}a_{n}t_{n}\phi_(x_{n})\] \[\frac{\partial L}{\partial b}=0\Rightarrow \sum_{n=1}^{N}a_{n}t_{n}=0\] \[\frac{\partial L}{\partial \xi_{n}}=0\Rightarrow a_{n}=C-\mu_{n}\] となる。これをラグランジェ関数に代入すると、 \[\hat{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})\] の双対表現で表わせる。ここでの制約式は、 \[0\leq a_{n}\leq C\] \[\sum_{n=1}^{N}a_{n}t_{n}=0\] で表され、この制約式のもと最小化するaを求めればよい。この時求められるaは、サポートベクター以外は、\(a_{n}=0\)となるため、疎な解になる。また、aはwの双対表現なので、bはについて考えると、bは、 \[t_{n}(\sum_{m\in S})a_{m}t_{m}k(x_{n},x_{m}+b)=1\] で求められる。Sはサポートベクターの集合を表す。新しい入力に対する予測は、 \[y(x)=\sum_{n\in S}a_{n}t_{n}k(x,x_{n})+b\] で表される。y ここでは、計算機上の誤差を少なくするために、サポートベクターの平均をとり、 \[b=\frac{1}{N_{M}}\sum_{n\in M}(t_{n}-\sum_{m\in S}a_{m}t_{m}k(x_{n},x_{m}))\] で求める。ここで、ラグランジェ双対表現されたラグランジェ関数の解き方について考える。この時、関数は2次式で凸関数なので、極値は最大値になる。最もよく使われるのは、保護共役勾配法または、SMOと呼ばれるものである SMOでは、二つのラグランジェ乗数を含む部分問題を逐次解いていき解を求める。多クラスへの拡張を考える。多クラスでのSVMの適用はまだ解決していない。提案されているものとして、あるクラスに分類されるとき、対応したSVMの教師には1を、他のSVMには、\(-\frac{1}{(K-1)}\)を用いる方法などがある。

回帰

SVMで回帰することを考える。ここでは、決定超平面が回帰関数になる。疎な解を求めるために、\(\epsilon\)許容誤差関数を用いて、誤差関数を定義すると、 \[C\sum_{n=1}^{N}E_{\epsilon}(y(x_{n})-t_{n})+\frac{1}{2}||w||^{2}\] \[E_{\epsilon}(y(x)-t)=|y(x)-t|-\epsilon(|y(x)-t|-\epsilon\leq0) or 0\] となる。この最適化問題をsvmでとく。 svmでは、超平面の外側であればどれだけ離れてもいてよかったが、回帰では、超平面に常に地下なければならないので、二つのスラック変数使う。許容誤差で表される領域においては、両方0となる。許容誤差の範囲を出た時に上辺、下辺に対応したスラック変数の値が変化する。これによりsvmの誤差関数は、 \[C\sum_{n=1}^{N}(\xi_{n}+\hat{\xi_{n}})+\frac{1}{2}||w||^{2}\] となる。制約条件は、 \[t_{n}\leq y(x_{n})+\epsilon+\xi_{n}\] \[t_{n}\geq y(x_{n})-\epsilon-\xi_{n}\] となる。スラック変数は、非ゼロである。これをラグランジェ未定乗数で解く。ラグランジェ関数は、 \[L=C\sum_{n=1}^{N}(\xi_{n}+\hat{\xi_{n}})-\sum_{n=1}^{N}(\mu_{n}\xi_{n}+\hat{\mu_{n}}\hat{\xi_{n}})-\sum_{n=1}^{N}a_{n}(\epsilon+\xi_{n}+y_{n}-t_{n})-\sum_{n=\hat{1}^{N}a_{n}}(\epsilon+\hat{\xi_{n}}-y_{n}+t_{n})] となる。各パラメータにおいて極値を計算し、式変形すると、 \[\hat{L(a,\hat{a})}=-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}(a_{n}-\hat{a_{n}})(a_{m}-\hat{a_{m}})k(x_{n},x_{m})-\epsilon\sum_{n=1}^{N}(a_{n}-\hat{a_{n}})+\sum_{n=1}^{N}(a_{n}-\hat{a_{n}})t_{n}\] で表わせ、\(a_{n}\)、\(\hat{a_{n}}\)について最大化する問題になる。KKT条件は、 \[a_{n(\epsilon+\xi_{n}+y_{n}-t_{n})=0}\] \[a_{n(\epsilon+\hat{\xi_{n}}-y_{n}+t_{n})=0}\] \[(C-a_{n})\xi_{n}=0\] \[(C-\hat{a_{n}})\hat{\xi_{n}}=0\] となる。bについては、 \[b=t_{n}-\epsilon-\sum_{n=1}^{N}(a_{n}-\hat{a_{n}})k(x_{n},x_{m})\] となる。新しい予測は、 \[y(x)=\sum_{n\in S}^{N}(a_{n}-\hat{a_{n}})k(x,x_{n})+b\] で表される。

RVM

svmのような識別関数でなく、確率が出てくる識別器。svmのベイズ版みたいな感じ。

回帰

基本的には、線形回帰と同じで、目的変数tの条件付き確率は、 \[p(t|x,w,\beta)=N(t|y(X),\beta^{-1})\] \[y(x)=w^{\mathrm{T}}\phi(x)\] である。データ集合が与えられた時の尤度関数は、 \[p(\mathbf{t}|X,w,\beta)=\prod_{n=1}^{N}p(t_{n}|x_{n},w,\beta)\] となる。rvmでは、事前分布にパラメータごとに異なったハイパーパラメータを使うことで疎な解を得る。事前分布は、 \[p(w|\alpha)=\prod_{i=1}^{M}N(w_{i}|0,\alpha_{i}^{-1})\] となる。ベイズより、パラメータの事後分布は、 \[p(w|\mathbf{t},X,\alpha,\beta)=N(w,m,\Sigma)\] \[m=\beta\Sigma\Phi^{\mathrm{T}}\mathbf{t}\] \[\Sigma=(A+\beta\Phi^{\mathrm{T}}\Phi)^{-1}\] となる。Aは、\(\alpha\)を対角成分に持つ対角行列、特徴空間を使わずカーネルを使う場合は、計画行列ではなくグラム行列になる。最適化アルゴリズムをもちいてハイパーパラメータを最適化すると、予測分布は、 \[p(t|x,X,\alpha^{*},\beta^{*})=\int p(t|x,w,\beta^{*})p(w|X,\mathbf{t},\alpha^{*},\beta^{*})=N(t,m^{\mathrm{T}}\phi(x),\sigma^{2}(x))\] \[m=\beta^{*}\Sigma\Phi^{\mathrm{T}}\mathbf{t}\] \[\Sigma=(A^{*}+\beta^{*}\Phi^{\mathrm{T}}\Phi)^{-1}\] \[\sigma^{2}(x)=(\beta)^{-1}-\phi(x)^{\mathrm{T}}\Sigma\phi(x)\] となる。この時、多くの\(\alpha\)は、無限大になり、平均0に尖った形になるため基底関数を無効にする。残った基底関数に対応する入力を、関連ベクトルという。これは、サポートベクターに相当する。ハイパーパラメータを最適化する方法を考える。一つは、エビデンス近似で、尤度関数\(p(\mathrm{t}|\alpha,\beta)\)を最大にする方法で、これは、導関数を0とおくか、EMアルゴリズムで求められる。もっと高速に求められるものとして、逐次的疎ベイジアン学習アルゴリズムがある。まずはじめに、適当に\(beta\)を初期化する。次に、基底関数を一つ選び、\(\alpha\)を決める。 \(\alpha\)は \[a_{i}=\frac{s_{i}^{2}}{q_{i}^{2}-s_{i}}\] \[s_{i}=\phi_{i}^{\mathrm{T}}C_{-i}^{-1}\phi_{i}\] \[q_{i}=\phi_{i}^{\mathrm{T}}C_{-i}^{-1}\mathrm{t}\] \[C=\beta^{-1}I+\Phi A^{-1}\Phi^{\mathrm{T}}\] により決まる。\(C_{^i}\)は、Cから\(\alpha_{i}\)に関する項以外を除いたもの。対応するハイパーパラメータ以外の初期値は無限とする。これにより今のモデルは、選ばれた一つの基底関数のみで初期化されている。これを元に、\(\Sigma\)とｍを決める。次に有効な基底関数を決める。 \(q_{i}^{2}>s_{i}\)ならば有効な基底関数として、\(\alpha_{i}\)を更新する。 \(q_{i}^{2}\geq s_{i}\)ならば無効な基底関数として、\(\alpha_{i}\)を無限にする。再び\(beta、\Sigma、m\)を更新し、収束するまで繰り返す。

分類

RVMでも出力に関してシグモイド関数を通すことで、\(t\in\{0,1\}\)を出力するようにする。ここでは、解析的に積分ができないので、ラプラス近似を用いて計算する。また、ラベルに間違いはないと仮定しているので、\(\beta\)は存在しない。まず、\(\alpha\)を初期化する。次に、今の\(\alpha\)に関して、ラプラス近似を行い、近似した分布で周辺尤度を計算する。最後に、尤度関数を最大にするように\(\alpha\)を更新する。これらを収束するまで繰り返す。\(\alpha\)の最適化は回帰の時と同じものが使える。