9.1　Maximal Margin Classifier

9.1.1　What is a Hyperplane?

9.1.2 　Classification Using a Separating Hyperplane

　magnitude of $f(x^{*})$ :　 $f(x^{*})$ が超平面から離れてるほど予測の確信度が高い．逆に，あまり離れてなければ疑わしい．

9.1.3　The Maximal Margin Classifier

　分離平面と，それに最も近い観測との距離をマージンという．このマージンを最大化するように学習して良い分類を期待するのは自然な発想．でもマージン最大化は $p$ が大きいと過学習してしまう．

　マージンから最小の距離にあるサンプルをサポートベクターという．超平面の上下で最低2つは存在する．

9.1.4　Construction of the Maximal Margin Classifier

　マージン $M$ の最大化は最適化問題として以下のように書ける． $\displaystyle \begin{align} \max_{\beta_0,\ \beta_1,\ldots,\ \beta_p} M,\ \mbox{subject to }\sum_{j=1}^{p}\beta_j^{2}=1,\ y_i(\beta_0+\sum_{j=1}^{p}\beta_jx_{ij}) \geq M\ \ \forall i=1,\ldots,n \end{align}$ 制約の後者は全てのサンプルがマージンを境界として正しく分類されていることを意味している．前者は，パラメタを大きくしてしまえば後者の制約の右辺 $M$ よりも左辺を大きくすることが可能になってしまうので，総和が1という制約を設けている．

9.1.5　The Non-separable Case

　マージン最大化は，そもそも分離可能な超平面が存在する時はうまくいくが，存在しない場合の方が圧倒的に多い．というわけで，いくつか誤分類してても良いですよ，というようにマージンを拡張したソフトマージンを考える．このキレイに分離できない場合に対してマージン最大化分類器を一般化したものがSupport Vector Classifier．

9.2　Support Vector Classifiers

9.2.1　Overview of the Support Vector Classifier

　Support Vector Classifierは個別の観測に対してロバストで，かつ，多くの訓練用の観測に対してうまく分類できるsoft margin classifierの一種．

9.2.2　Details of the Support Vector Classifier

　Support Vector Classifierは最適化問題として以下の形で書ける． $\displaystyle \begin{align} \max_{\beta_0,\ \beta_1,\ldots,\ \beta_p} M \end{align}$ $\displaystyle \begin{align} \mbox{subject to }\sum_{j=1}^{p}\beta_j^{2}=1,\ y_i(\beta_0+\sum_{j=1}^{p}\beta_jx_{ij}) \geq M(1-\epsilon_i)\ \ \forall i=1,\ldots,n, \end{align}$ $\displaystyle \begin{align} \epsilon_i \geq 0,\ \sum_{i=1}^{n}\epsilon_i \leq C \label{slack} \end{align}$ $C$ は非負のパラメタ． $\epsilon_1,\ldots,\epsilon_n$ はどれくらい誤分類を許すかを表すスラック変数． $\epsilon_i=0$ の時はマージンの外側にある． $\epsilon_i>0$ ならば，マージンを超えて超平面に近づいた状態． $\epsilon_i=1$ なら超平面の向こう側，つまり，完全な誤分類になる． $C$ はクロス・バリデーションとかで決める．こいつがバイアス・バリアンスのトレードオフを決める．式 $\eqref{slack}$ を見て分かる通り， $C$ が小さければ誤分類を認めない狭いマージンになり， $C$ が大きければ大きなマージンになる．

　面白いのは，Support Vector Classifierのは全ての観測ではなく，サポートベクターとマージン内の観測のみで決まる点．

9.3　Support Vector Machines

9.3.1　Classification with Non-linear Decision Boundaries

　Support Vector Classifierは線形分離可能な時に使う．非線形に分離したい時は二乗の項や相乗項を追加し，それに対応して制約も追加する．そうすると，追加された項を含めた時は線形に分離できるが，元の変数のみでは非線形な分離平面を得ることができる． $\displaystyle \begin{align} \max_{\beta_0,\ \beta_1,\ldots,\ \beta_p} M \label{margin} \end{align}$ $\displaystyle \begin{align} \mbox{subject to }\sum_{j=1}^{p}\beta_j^{2}=1,\ y_i(\beta_0+\sum_{j=1}^{p}\beta_{j1}x_{ij} + \sum_{j=1}^{p}\beta_{j2}x_{ij}^{2}) \geq M(1-\epsilon_i)\ \ \forall i=1,\ldots,n, \label{const1} \end{align}$ $\displaystyle \begin{align} \epsilon_i \geq 0,\ \sum_{i=1}^{n}\epsilon_i \leq C,\ \sum_{j=1}^{p}\sum_{k=1}^{2}\beta_{jk}^{2}=1 \label{const2} \end{align}$

9.3.2　The Support Vector Machine

　SVMはカーネルを使って高次元に写像された特徴空間を用いて得られるSupport Vector Classifierの拡張の一種らしい．

　Support Vector Classifierを，内積を使って書くと下式になる． $\displaystyle \begin{align} f(x)=\beta_0+\sum_{i=1}^{n}\alpha_i \langle x, x_i \rangle,\ \mbox{where } \langle x_i, x_{i'} \rangle = \sum_{j=1}^{p}x_{ij}x_{i'j} \end{align}$ $n$ 個のパラメタ $\alpha_i$ は観測の一つ一つに対応する．具体的には，その観測がサポートベクターなら非0，そうでないなら0．パラメタ $\alpha_1,\ldots,\alpha_n,\ \beta_0$ を求めるために ${}_nC_2$ 個の内積 $\langle x_i, x_{i'} \rangle$ を計算する必要がある．ただサポートベクターでない項は結果に効いてこないので，インデックス $S$ を使うと以下のように書き換えられる． $\displaystyle \begin{align} f(x)=\beta_0+\sum_{i \in S}\alpha_i \langle x, x_{i} \rangle \end{align}$ こうした方が計算軽いよね，という話．

　内積を一般化して，カーネル $K(x_i,x_{i'}$ を考える．カーネルが内積の場合，つまり， $\displaystyle \begin{align} K(x_i,x_{i'})=\sum_{j=1}^{p}x_{ij}x_{i'j} \end{align}$ の時は線形カーネルになる．これを使ったSVMは単なるSupport Vector Classifier．線形カーネルは観測のペアの類似度をピアソン相関係数を使って定量化していることになるらしい．

　また，多項式カーネルというのもある． $\displaystyle \begin{align} K(x_i,x_{i'})={(1+sum_{j=1}^{p}x_{ij}x_{i'j})}^{d} \end{align}$ $d>1$ なら線形カーネルよりも柔軟な決定境界が得られる．多項式カーネルは，本質的には，d次の項を含んだSupport Vector Classifierだと言える．

　SVMは以下の通り．ただ単にSVCの内積の項をカーネルで一般化しただけ． $\displaystyle \begin{align} f(x)=\beta_0+\sum_{i \in S}\alpha_i K(x,x_{i}) \end{align}$

　多項式カーネルと同様に，非線形な決定境界を与えるカーネルとしてradial kernelがある． $\displaystyle \begin{align} K(x_i,x_{i'})=\exp \bigl(-\gamma \sum_{j=1}^{p}{(x_{ij}-x_{i'j})}^{2} \bigr),\ \mbox{where }\gamma > 0 \end{align}$ こいつがどう動くのか？新たな観測 $x^{*}$ を予測したいとする． $x^{*}$ と訓練データ中のある観測 $x_i$ とのユークリッド距離はかなり離れているとする．そうすると， $\sum_{j=1}^{p}{(x_{ij}-x_{i'j})}^{2}$ は大きくなるのだが， $\exp$ を取ってるので，最終的な値は非常に小さくなる．要するに，観測から離れた訓練データは類似度を計算する上でほぼ機能せず，観測に近い位置にある訓練データのみを用いてラベルを予測している．

　カーネルの何が嬉しいかというと，高次元特徴空間を明示的に触る必要がない点が良い．つまり，手持ちの要素の ${}_nC_2$ 通りの組み合わせに対する $K(x_i,x_{i'}$ の演算だけで，高次元空間で操作した結果と同じ結果を得られるのが良い．

9.3.3　An Application to the Heart Disease Data

9.4 SVMs with More than Two Classes

9.4.1　One-Versus-One Classification

　多クラス分類する時はOne-Versus-Oneという手法がある．これは ${}_KC_2$ 個の分類器を造って，全ての分類機に対して入力を与え，最も多く予測されたクラスを結果として与える．

9.4.2　One-Versus-All Classification

　 $k$ 番目のクラスだったら+1，そうでないなら-1とする $K$ 個の分類器を作って，各分類機に入力を与え，分類機による結果が最も大きい分類機が属するクラスを，予測結果とする．

9.5　Relationship to Logistic Regression

　サポートベクター分類器 $\displaystyle f(X)=\beta_0+\sum_{j=1}^{p}\beta_jX_{j}$ に関する式 $\eqref{margin}-\eqref{const2}$ は以下のように書き換えられる． $\displaystyle \begin{align} \min_{\beta_0,\ \beta_1,\ldots,\beta_p} \biggl\{ \sum_{i=1}^{n}\max [0, 1-y_if(x_i)]+\lambda \sum_{j=1}^{p} \beta_j^{2} \biggr\},\ \mbox{where }\lambda > 0 \label{rewrite} \end{align}$ $\lambda$ が大きければ $\beta_1,\ldots,\beta_p$ は小さくなり，より多くの観測がマージン内に位置づけられる．結果としてlow-varianceでhigh-biasな分類器が出来上がる． $\lambda$ が小さければ，逆に，high-varianceでlow-biasな分類器が出来上がる．そういうわけで $\lambda$ は式 $\eqref{slack}$ の $C$ と同じ役割を果たしている．また，式 $\eqref{rewrite}$ にはRidge罰則項があるが，これがsupport vector classifierにおけるbias-varianceトレードオフをコントロールしている．式 $\eqref{rewrite}$ は損失関数と罰則項を使って以下のようにも書き換えられる． $\displaystyle \begin{align} \min_{\beta_0,\ \beta_1,\ldots,\beta_p} \{ L(\mathbf{X},{\bf y},\beta)+\lambda P(\beta) \},\ \mbox{where }\lambda > 0 \label{rewrite2} \end{align}$ $L$ はパラメタ $\beta$ の下でデータ $(\mathbf{X},\bf{y})$ にフィットさせた際の損失， $P(\beta)$ はパラメタ $\beta$ についての損失関数．RidgeやLassoなら損失は最小二乗法になるし，罰則項はL2ノルムの2乗もしくはL1ノルムになる．式 $\eqref{rewrite}$ の場合は $\displaystyle \begin{align} L(\mathbf{X},{\bf y},\beta)=\sum_{i=1}^{n}\max [0, 1-y_i(\beta_0+\beta_1x_{i1}+\ldots+\beta_px_{ip})] \end{align}$ になり，こいつはヒンジロスと呼ばれてるらしい．Fig 9.12を参照してほしいのだが，ヒンジロスは $y_i(\beta_0+\beta_1x_{i1}+\ldots+\beta_px_{ip})$ が1を超えた場合0になってる．これは結局マージンの正しい方，つまりサポートベクターではない例に反応しているので，そうしたデータはSVMがラベルを予測する上で使われないことに対応してる．一方ロジスティック回帰のロスは，ヒンジロスを滑らかにしたような結果になってる．そういうわけでSVMとロジスティック回帰はある意味似ており，かなり似た結果を返す．使い分けとしては，クラス間が明確に分離できるならSVM，そうでないならロジスティック回帰の方が精度が出るらしい．