MIT OCW, Machine Learning 02日目 SVM

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

The Support Vector Machine

大きなgeometric marginがあって線形分離できるという仮定のもとで,有限回の繰り返しでそのようなlinear classifierを与えられることを見た.Support Vector Machine(SVM)は繰り返しでなく直接そのようなlinear classifierを与える. まず,正しく線形分離を行うclassifierを見つけて(fig.1a),それからgeometric marginが最大になるように$\theta$を調節する(fig.1b).このような解は一意である.

figure 1

より形式的には,geometric marginを最大化する最適化問題となる. すなわち,$y_t\theta^T\mathbf{x}_t\geq \gamma$がすべてのtraining dataに成立するという制約条件のもとで,$\gamma_{geom}=\gamma/\|\theta\|$を最大化する. $\gamma_{geom}$を最大化する代わりに,逆数$\|\theta\|/\gamma$か$\frac{1}{2}(\|\theta\|/\gamma)^2$を最小化する問題とすることもできる.
$y_t\theta^T \mathbf{x}_t \geq \gamma$の両辺を$\gamma$で割って
$$\text{minimize } \frac{1}{2}\|\theta/\gamma\|^2 \text{ subject to }y_t(\theta/\gamma)^T \mathbf{x}_t \geq 1 \text{ for all } t= 1,...,n$$
となる.この問題の解は$\gamma$と$\theta$のそれぞれの値を与えず,$\theta$の定数倍によって得られるdecision boundaryは変わらないから,$\gamma=1$としてよい.以上から,結局
$$\text{minimize } \frac{1}{2}\|\theta|^2 \text{ subject to }y_t(\theta/)^T \mathbf{x}_t \geq 1 \text{ for all } t= 1,...,n$$
という最適化問題を解くことになる. この最適化問題はstandard SVM formであり,quadratic programming problem(目的関数が線形制約のもとのパラメータの二次関数)である. この解として得られるgeometric marginは$1/\|\hat{\theta}\|$である. decision boundaryとgeometric marginは$\gamma=1$という設定によって変化していない.

General Formulation, Offset Parameters

パラメータにoffset term $\theta_0$を加えることで,decision boundaryが必ずしも原点を通らなくとも良くなる. このときclassifierは
$$f(\mathbf{x}; \theta, \theta_0) = sign(\theta^T \mathbf{x}+\theta_0)$$
separating hyperplaneは$\theta^T\mathbf{x}+\theta_0=0$なる$\mathbf{x}$の集合である.$\theta_0$の導入によって,原点を通るlinear classifierよりも大きなmarginを取れるようになることが有る. $\theta_0$の導入によって最適化問題は
$$\text{minimize } \frac{1}{2}\|\theta|^2 \text{ subject to }y_t(\theta^T \mathbf{x}_t+\theta_0) \geq 1 \text{ for all } t= 1,...,n$$
となる.$\theta_0$は制約項においてだけ考慮する. $\theta_0$はまさしくgeometric marginを最大化するためにのみ導入されるのである.

Properties of the Maximum Margin Linear Classifier

Benefits

解はtraining dataが与えられるたびに一意に決まり,geometric marginが最大になるようにboundaryを引くから,データのノイズに対して頑強である. さらに,marginの上のexampleたち(support vectors)のみによってパラメータは決まる(これが利点であるか否かを言うには,classifierの良さをより形式的に測る方法を議論する.).

training examplesのみが与えられたときのclassifierの性能をはcross-validationによって計量される. これは単純に,training dataのある部分集合だけを使ってclassifierを訓練し,そのclassifierが選ばれなかったtraing examplesに対する成績を計測していくのである. leave-one-out cross-validationはそのような方法の一つで,traing dataから1つだけexampleを取り出して訓練を行い,取り出されたexampleを正しく判別できたか否かをたしかめ,これをtraing data全てに繰り返す. 右肩に$-i$を置くことで$i$番目のexampleを取り出して訓練したときのパラメーターを表すとすると,
$$\text{leave-one-out CV error } = \frac{1}{n} \sum_{i=1}^n \text{Loss} \left(y_i, f(\mathbf{x}_i; \theta^{-i}, \theta_0^{-i}) \right)$$
である.ただし$\text{Loss}(y, y') = \begin{cases} 1 \ \ (y\neq y') \\ 0 \ \ \text{otherwise} \end{cases}$ とする. leave-one-out CV errorが低いとよくgeneralizeできていると考えられるが,保証されているわけではない.
maximum margin linear classifierにおいて,あるexampleを除いて訓練を行ってそのexampleを判別し損ねるというのは,そのexampleがsupport vectorであるときであって,
$$\text{leave-one-out CV error} \leq \frac{number of support vectors}{n}$$
である. よって,support vectorが少ないほどよい.これを解のsparse(疎)性質という.

Problems

たった一つのexampleであっても,labelが間違っていると完全にmaximum margin classifierを変化させてしまう.

Allowing Misclassified Examples, Relaxation

labelを間違えることはよく有ることだから,これに弱いというのは致命的なので,mislabelに強くする工夫が必要である. うまく判別できないデータが与えられたとして,それがmislabelによるのか,あるいは線形分離不可能だからなのかを知ることは困難である. どちらにせよ, traing exampleに対する正確性と,未知のexampleに対する正確性にはトレードオフの関係が有ることを肝に銘じなければならない.
maximum margin classifierをmislabelに頑強にする最も単純な方法の一つにslack variableの導入が有る. それぞれのexampleに対して,どれほどmarginの内側に来てしまうかを計量し,それのtraing dataの和を小さくするようにobjective functionに付け加えるのである.形式的には
$$\text{minimize} \frac{1}{2}\|\theta\|^2 + C \sum_{t=1}^n \xi_t$$
$$\text{subject to } y_t(\theta^T \mathbf{x}_t+\theta_0) \geq 1-\xi_t \text{ and } \xi_t \geq 0 \text{ for all } t = 1, ... n$$

となる.$\xi_t$がslack variableである. example $\mathbf{x}_t$がmarginを内側にはみ出るとき$\xi_t > 0$となって,objective functionに$C\xi_t$を加え,$1/2\|\theta\|^2$の最少化を阻害し,未知のdataに対する頑強さを減じる. $C$を小さくするとよりmislabelに強いが未知のexampleに弱く,$C$を大きくするとmislabelに弱いが未知のexampleに強くなる.$C$が極端に大きくなると,slack variableを考えないのと同じことになる.