机器学习笔记—

SVM(Support Vector Machine)。中文名为支持向量机。就像自己主动机一样。听起来异常神气。最初总是纠结于不是机器怎么能叫“机”,后来才知道事实上此处的“机”实际上是算法的意思。

支持向量机一般用于分类，基本上，在我的理解范围内。全部的机器学习问题都是分类问题。而据说，SVM是效果最好而成本最低的分类算法。

SVM是从线性可分的情况下最优分类面发展而来的，其基本思想能够用下图表示：

(最优分类面示意图)

图中空心点和实心点代表两类数据样本，H为分类线，H1、H2分别为过各类中离分类线近期的数据样本且平行与分类线的直线。他们之间的距离叫做分类间隔(margin)。

最优分类线，就是要求分类线不但能将两类正确的分开，使训练错误率为0。并且还要使分类间隔最大。

推广到高维空间，最优分类线就叫做最优分类面了。

设 $(x{i},y{i}),i=1,...,n,x{i}\in R^{d},y{i}\in \{+1,-1\}$ 为两类线性可分的样本集合。

相应的线性判别函数的一般形式为 $f(x)=\omega \cdot x+b$ ,相应的分类方程为

%5Comega%20%5Ccdot%20x+b%3D0" alt="" style="font-size:18px; margin:10px; text-align:center">。将判别函数进行归一化。使全部样本都满足 $|f(x)|\geqslant 1$ ,此时离分类面近期的样本

f%28x%29%3D%201" alt="" style="margin:10px; text-align:center">,要求分类面对全部样本都能正确分类，即满足 $y{i}[(\omega \cdot x{i})+b]-1\geqslant 0,i=1,\cdots ,n$ (记为A),

此时分类间隔等于 $2/\left | \left | \omega \right | \right |$ 。间隔最大等价于 $\left | \left | \omega \right | \right |^{2}$ 最小。

最优分类线H就是满足式A且使

%5Cfrac%7B1%7D%7B2%7D%5Cleft%20%7C%20%5Cleft%20%7C%20%5Comega%20%5Cright%20%7C%20%5Cright%20%7C%5E%7B2%7D" alt="" style="margin:10px; text-align:center">最小的分类面。

两类数据样本中立分类面近期的样本，且平行于分类面H的超平面 $H{1}$ 、 $H{2}$ 上的数据就是式A中使等号成立的那些数据样本。这些数据样本叫做支持向量(support
vector,SV)。

由上可知，最优分类面问题能够表示为约束优化问题。在式A的约束下，求例如以下函数的最小值

%5Cvarphi%20%28%5Comega%20%29%3D%5Cfrac%7B1%7D%7B2%7D%5Cleft%20%5C%7C%20%5Comega%20%5Cright%20%5C%7C%20%5E%7B2%7D" alt="" style="margin:10px; text-align:center">

为此。定义例如以下Lagrange函数

$L(\omega ,b,a)=\frac{1}{2}\left \| \omega \right \|^{2}-\sum_{i=1}^{n}\alpha _{i}[y_{i}(\omega \cdot x_{i}+b)-1]$ (记为式B)

式中， $\alpha_{i}$ 为拉格朗日函数的乘子（Lagrange
Multiplier) 。

%5Calpha_%7Bi%5Cgeqslant%20%7D0" alt="" style="margin:10px; text-align:center">。要求式B的最小值，对各个參数求偏导数。且偏导数为0。结果例如以下

$\left \{ \begin{gathered} \frac{\partial L}{\partial \omega }=0\Rightarrow \sum_{i=1}^{n}\alpha _iy_ix_i \hfill \\ \frac{\partial L}{\partial \omega }=0\Rightarrow \sum_{i=1}^{n}\alpha _iy_ix_i \hfill \\ \frac{\partial L}{\partial a_i }=0\Rightarrow a_i[y_i(\omega \cdot x_i+b)-1] \hfill \\ \right. \end{gathered}$

依据A式和B式的约束条件，能够将上述分类面的求解问题问题转化为例如以下凸优化的问题

$\left \{ \begin{gathered} max\sum_{i=1}^{n}\alpha _i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha _i\alpha_jy_iy_j(x_ix_j) \hfill \\ s.t.\alpha\geq 0,i=1,\cdots ,n \hfill \\ \sum_{i=1}^{n}\alpha _iy_i=0 \hfill \\ \right. \end{gathered}$