SVMとRVM
SVM
入力 $\boldsymbol{x}_n$ を $t_n = \pm 1$ に線形分類することを考える．シグモイドを使った分類とは異なり，今回は $y_n = \boldsymbol{w}^{\text{T}} \boldsymbol{\phi}(\boldsymbol{x}) + b$ に対して
$$\begin{align*} t_n y_n > 0 \end{align*}$$
を満たすように $\boldsymbol{w}, b$ を決めることとする(つまり分類方法としては $y_n$ の符号しか見ていない)．これだけだと一意に決定できないため，超平面 $y(\boldsymbol{x}) = 0$ とデータの距離に注目してみる．各々のデータとこの超平面の垂直距離は
$$\begin{align*} \frac{t_{n} y(\boldsymbol{x}_{n})}{|\boldsymbol{w}|}=\frac{t_{n}(\boldsymbol{w}^{T} \phi (\boldsymbol{x}_{n})+b)}{|\boldsymbol{w}|} \end{align*}$$
で与えられる．そこで「超平面に最も近いデータ点の距離を最大化する」パラメーターをこの問題の解とする．つまり以下の最適化問題を解く．
$$\begin{align*} \underset{\boldsymbol{w}, b}{\arg \max }\left\{\frac{1}{|\boldsymbol{w}|} \min_{n}[t_{n}(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\phi}(\boldsymbol{x}_{n})+b)]\right\} \end{align*}$$
ここで $(\boldsymbol{w}, b)$ を定数倍しても垂直距離は変わらないことに着目すると，超平面に最も近いデータ点について
$$\begin{align*} t_{n} (\boldsymbol{w}^{\text{T}} \boldsymbol{\phi} (\boldsymbol{x}_{n})+b)=1 \end{align*}$$
が成立するように定数倍できる．このとき $t_{n} (\boldsymbol{w}^{\text{T}} \boldsymbol{\phi} (\boldsymbol{x}_{n})+b)\geq 1$ が全てのデータ点において成立している．すると元の最適化問題は $| \boldsymbol{w} |$ を最小化する，すなわち
$$\begin{align*} \underset{w, b}{\arg \min} \ & \frac{1}{2}|\boldsymbol{w}|^2 \\ {\rm s.t.}\ \ & t_{n} (\boldsymbol{w}^{\text{T}} \boldsymbol{\phi} (\boldsymbol{x}_{n})+b)\geq 1 \end{align*}$$
に帰着される．未定乗数を $\boldsymbol{a} \in \mathbb{R}^N, a_i \geq 0$ としてラグランジアン $L(\boldsymbol{w}, b, \boldsymbol{a})$ は
$$\begin{align*} L(\boldsymbol{w}, b, \boldsymbol{a}) = \frac{1}{2} |\boldsymbol{w}|^{2} - \sum_{n=1}^{N} a_{n} \{t_{n} (\boldsymbol{w}^{\text{T}} \phi (\boldsymbol{x}_{n})+b)-1 \} \end{align*}$$
である．ここで制約の項を引き算にしているのは後々 $\boldsymbol{a}$ についてラグランジアンを最大化したいためである．未定乗数法により最適性の必要条件として
$$\begin{align*} \boldsymbol{w} &=\sum_{n=1}^{N} a_{n} t_{n} \phi\left(\boldsymbol{x}_{n}\right) \\ 0 &=\sum_{n=1}^{N} a_{n} t_{n} \end{align*}$$
が得られる．これを用いてラグランジアンから $(\boldsymbol{w}, b)$ を消去すると双対問題として
$$\begin{align*} \underset{a}{\arg \max} \tilde{L}(\boldsymbol{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 (\boldsymbol{x}_{n}, \boldsymbol{x}_{m}) \\ {\rm s.t.}\ \ & a_n \geq 0 \\ & \sum_{n=1}^{N} a_n t_n = 0 \end{align*}$$
が得られる．ここでカーネル関数は $k(\boldsymbol{x}_1, \boldsymbol{x}_2) = \boldsymbol{\phi(x)}_1^{\text{T}} \boldsymbol{\phi(x)}_2$ である．2次計画法によりこれを解いてパラメーター $(\boldsymbol{w}, b)$ を求め， $y(\boldsymbol{x})$ の符号を調べればテストデータを分類できる．あるいは
$$\begin{align*} y(\boldsymbol{x})=\sum_{n=1}^{N} a_{n} t_{n} k(\boldsymbol{x}, \boldsymbol{x}_{n})+b \end{align*}$$
計算する．しかしKKT条件により一部のデータを除いて $a_n = 0$ となるので，この $\Sigma$ のうち $a_n \neq 0$ となるものだけが有効である．このとき $\boldsymbol{x}_n$ はサポートベクトルと呼ばれ，最小化したマージンの上に存在する点である．訓練が終わった後はこのサポートベクトルだけ保持して上の $\Sigma$ を計算し，予測に用いればよい．
RVM
関連ベクトルマシンは回帰にも用いることができ，事後分布も計算できる．3章に出てきたエビデンス近似と導出は似ている．訓練データ $(\boldsymbol{x}_n, t_n), n = 1, \ldots , N$ を用いて以下のようにカーネル関数を用いて回帰モデルを立てる．
$$\begin{align*} y(\boldsymbol{x})=\sum_{n=1}^{N} w_{n} k (\boldsymbol{x}, \boldsymbol{x}_{n})+b \end{align*}$$
これに雑音 $\mathcal{N}(0, \beta^{-1})$ が加えられて観測値が得られるとする．なおここではカーネル関数は正定値である必要はない． $X$ を $\boldsymbol{x}_n^{\text{T}}$ を縦に並べたとすると尤度関数は
$$\begin{align*} p(\boldsymbol{t} \mid \boldsymbol{X}, \boldsymbol{w}, \beta)=\prod_{n=1}^{N} p (t_{n} \mid \boldsymbol{x}_{n}, \boldsymbol{w}, \beta ) \end{align*}$$
である．次にパラメータ $\boldsymbol{w}$ の事前分布として3章のエビデンス近似と同様に平均がゼロのガウス分布を用いるのだが，3章とは異なり各要素について異なる精度パラメーター $\alpha_i$ を用いて
$$\begin{align*} p(\boldsymbol{w} \mid \boldsymbol{\alpha})=\prod_{i=1}^{M} \mathcal{N} (w_{i} \mid 0, \alpha_{i}^{-1}) \end{align*}$$
とする．するとSVMと同様にほとんどの訓練データについては $\alpha_i$ が無限大に近づくため，事後分布がゼロ中心に集中することになるのである．ベイズの定理より事後分布は
$$\begin{align*} p(\boldsymbol{w} \mid \boldsymbol{t}, X, \alpha, \beta)& = \mathcal{N}(\boldsymbol{w} \mid \boldsymbol{m}, \boldsymbol{\Sigma}) \\ \boldsymbol{m} &= \beta \boldsymbol{\Sigma} \Phi^{\text{T}} \boldsymbol{t} \\ \boldsymbol{\Sigma} &= (\boldsymbol{A}+\beta \Phi^{\text{T}} \Phi)^{-1} \end{align*}$$
となる．ここで $\boldsymbol{A} = \mathrm{diag}(\alpha_i)$ である．エビデンス近似により $(\boldsymbol{\alpha}, \beta)$ を求めるため，以下の対数尤度を最大化することで第二種の最尤推定を行う．
$$\begin{align*} \ln p(\boldsymbol{t} \mid \boldsymbol{X}, \boldsymbol{\alpha}, \beta) &=\ln \mathcal{N}(\boldsymbol{t} \mid 0, C) \\ &=-\frac{1}{2} \{N \ln (2 \pi)+\ln |C|+\boldsymbol{t}^{\text{T}} C^{-1} \boldsymbol{t}\} \end{align*}$$
ここで $C=\beta^{-1} \mathbf{I}+\Phi \mathbf{A}^{-1} \Phi^{\text{T}}$ である．3章と同様に対数尤度の微分を用いて
$$\begin{align*} \alpha_{i}^{\text {new}} &= \frac{\gamma_{i}}{m_{i}^{2}} \\ (\beta^{\text {new}})^{-1} &= \frac{|\boldsymbol{t}-\Phi \boldsymbol{m}|^{2}}{N-\sum_{i} \gamma_{i}} \end{align*}$$
として更新を行えばよい．ここで $\gamma_i = 1 - \alpha_i \Sigma_{ii}$ である．最適値 $(\boldsymbol{\alpha}^{*}, \beta^{*})$ が求まったら事後分布は
$$\begin{align*} p(t \mid \boldsymbol{x}, X, \boldsymbol{t}, \boldsymbol{\alpha}^{\star}, \beta^{\star}) &= \mathcal{N}(t \mid \boldsymbol{m}^{\text{T}} \boldsymbol{\phi}(\boldsymbol{x}), \sigma^2(\boldsymbol{x})) \\ \sigma^{2}(\boldsymbol{x}) &= (\beta^{\star})^{-1}+\phi(\boldsymbol{x})^{\text{T}} \Sigma \phi(\boldsymbol{x}) \end{align*}$$
で与えられる．もちろん $\boldsymbol{m}, \Sigma$ の計算には $(\boldsymbol{\alpha}^{\star}, \beta^{\star})$ を用いる．
スパース性の解析
TODO