支持向量机

线性可分支持向量机
约定训练样本集\(D=\{(x_i,y_i)|i=1...N\}\), \(x\in\mathcal X=R^n, y_i\in\mathcal Y =\{\pm 1\}\).

如果存在特征空间\(\mathcal X\)中的超平面\(H:w\cdot x + b = 0\)满足：\[(w\cdot x_i + b ) \cdot y_i >0\]即所有样本能被H正确分类，称D是线性可分的。原点到H的距离为\(\frac{|b|}{\lVert w\rVert}\).
我们用\((w,b)\)表示H。

下面设D线性可分，讨论最优的分离超平面。
令 \(\hat \gamma = \min\limits _{i} y_i \cdot (w\cdot x_i + b)\). 可以对 \((w,b)\) 乘以同一常数，使得\(\hat\gamma=1\).

此时，取得等号成立的点\(y_i\cdot(w\cdot x_i + b)=1\)落在两个超平面之一中：\(w\cdot x_i + b = \pm 1\). 它们到原超平面H的距离恰好是\(\frac{1}{\lVert w\rVert}\). 两个超平面的距离\(\frac{2}{\lVert w\rVert}\)称为间隔。

样本点到超平面的距离表征此点分类预测的置信度，最小者为\(\frac{1}{\lVert w\rVert}\). 最优的分离超平面将优化如下问题：\[\max\limits_{w,b} \frac 1 {\lVert w\rVert}\]\[s.t.\quad y_i\cdot (w\cdot x_i + b)\ge 1\]等价的凸二次规划问题为\[\max\limits_{w,b} \frac 1 2 \lVert w \rVert^2.\]若D线性可分，则此凸二次规划问题的解存在且唯一。

对偶问题
采用拉格朗日乘子法来求此凸二次规划问题：令\[L(w,b,a) = \frac 1 2 \lVert w\rVert^2+\sum\limits _{i=1}^N a_i - \sum\limits_{i=1}^N a_iy_i(w\cdot x_i + b)\]
分别对w和b求偏导等于0可得\[w = \sum\limits_{i=1}^N a_iy_ix_i,\]\[\sum\limits_{i=1}^N a_iy_i=0.\]
代入L得对偶问题\[\max\limits_a \sum_i a_i -\frac 1 2 \sum_i\sum_j a_ia_jy_iy_j\ (x_i\cdot x_j)\] 其约束条件为\[\sum_i a_i y_i =0, a_i\ge 0\]
由KKT条件可得\[1-y_i(w\cdot x_i + b ) \le 0, \quad a_i\ge 0,\]\[a_i\cdot [1-y_i(w\cdot x_i + b)]=0.\]

SMO算法
SMO算法的基本思路是固定某\(a_i\)以外的全部参数，并优化\(a_i\)。但固定n-1个参数时最后一个参数可以直接解出。因此每次选取两个参数进行优化。进一步，SMO算法采取启发式选取，每次选择一个违背KKT条件最严重的变量和一个使目标函数增长最快的变量。
对原约束\(\sum a_iy_i=0\)乘以\(y_1\)得\(a_1+a_2y_1y_2 - \gamma=0\)，\(\gamma\)是暂时不考虑的常数，\(s=y_1y_2\). 得\(a_1+sa_2=\gamma\).
转化为优化问题：\[\max_{a_1,a_2} W(a_1,a_2)\]\[s.t.\quad 0\le a_1,a_2\le C, a_1+sa_2=\gamma.\]
线性支持向量机
考虑D不是线性可分的情况。策略：容忍一部分点违反约束\(y_i(w\cdot x_i + b)\ge 1\)，但尽可能少。
引入松弛变量\(\xi_i\)使得约束弱化为\(y_i(w\cdot x_i + b)+\xi_i\ge 1.\) 对于\(\xi\ne0\)的点称为特异点。优化问题为：\[\min_{w,b}\ \frac 1 2 \lVert w \rVert ^2 + C\sum_{i=1}^N \xi_i^p\quad (p\ge 1),\]\[s.t.\quad y_i(w\cdot x_i + b)\ge 1-\xi_i, \quad \xi_i\ge0.\]
对于特异点，不妨取\(\xi_i = 1-y_i(w\cdot x_i + b)\). 由此启发，引入合页损失函数\(h(z) =\max(0,\ 1-z)\). 则可以简写\[\xi_i = h(y_i(w\cdot x_i + b))\]得到等价的优化问题\[\min_{w,b} \sum_{i=1}^N h(y_i(w\cdot x_i + b)) + \frac 1 {2C} \lVert w \rVert ^2.\]
合页损失函数h也可以选取0-1损失函数，二次合页损失函数。以上优化问题也可用拉格朗日乘子法求解对偶问题。

核方法与非线性支持向量机
对于非线性边界的问题，可以将原始特征空间\(\mathcal X\)映射到高维特征空间\(\phi:\mathcal X\to \mathcal Z\)，使在这个空间内线性可分。超平面变为\(w\cdot\phi(x) + b =0\). 为了减轻计算高维内积的复杂度，引入核技巧：不直接定义\(\phi\)，而定义核函数\(K(x_i,x_j) = \phi(x_i)\cdot \phi(x_j).\)

正定对称核函数：\((K(x_i,x_j))_{m\times m}\)是对称半正定矩阵。

    所属分类：机器学习     发表于2022-05-10