机器学习算法之支持向量机

整体思路
参考文献

整体思路

支持向量机最基本的思路是按照二分类来理解的，目的是为了找到一个超平面可以将所有的样本以最大间隔分割开来，假设选定的超平面为：

$W^TX + b = 0$

当 $W^TX+b>0$ 时，样本被归为正类，$W^TX+b<0$ 时，样本被归为负类；

样本与超平面的距离可以表示为：

$\frac{|W^TX+b|}{||W||}$

在特征空间当中，能够决定超平面位置的只有”支持向量”,而正反两类支持向量与超平面的距离应当是相同的，该距离经过特征的缩放可修正为1,也就是说可以将其大小缩放为当 $W^TX+b \ge 1$ 时，样本被归为正类，$W^TX+b \le -1$ 时，样本被归为负类；此时上式中的支持向量与超平面的距离可以修正为：

$\frac{1}{||W||}$

正反两类支持向量与超平面的间隔是相同的，间隔可以表示为：

$\frac{2}{||W||}$

此时，可以表示出SVM的基本模型就是在分类正确的基础上令间隔最大化：

$argmax \frac{2}{||W||}$ $s.t. y_i (WX_i^T+b) \ge 1$

为求解方便，上式等价于:

$argmin \frac{1}{2} ||W||^2$ $s.t. y_i (WX_i^T+b) \ge 1$

为了求解上述模型，采用拉格朗日乘子法(lagrange multiplier¹)将约束条件与目标函数通过一个非负的$\lambda$结合在一起可以得到拉格朗日函数,其中，i代表的是不同的样本点：

$L(W, b, \lambda) = \frac{1}{2} ||W||^2 + \sum_{i=1}^{n} \lambda_i (1 - y_i(W^TX_i+b))$

上式对W和b分别求偏导数可以得到：

$\frac{\partial{f}}{\partial{W}} = W - \sum_{i=1}^{n} \lambda_i y_i X_i = 0 \leftrightarrow W = \sum_{i=1}^{n} \lambda_i y_i X_i$ $\frac{\partial{f}}{\partial{b}} = - \sum_{i=1}^{n} \lambda_i y_i = 0 \longleftrightarrow \sum_{i=1}^{n} \lambda_i y_i = 0$

我们要求解的目标是上述目标函数的最小值，对W和b求偏导，将解带回原式就得到了原始问题的对偶问题

参考文献

李航. “统计学习方法.” 清华大学出版社, 北京 (2012). ↩

生若直木，不语斧凿.

目录

整体思路

参考文献