SVM(1)——基本型推导
SVM的全称是 Support Vector Machine，中文译名为支持向量机，是一种用来解决分类问题的监督学习算法，
给定训练样本集，分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。但能将训练样本分开的划分超平面可能有很多。如下图：
显然，在所有的划分超平面中，红色的那个是最好的一个，因为该超平面离所有的样本都隔着较远的距离，也就是说对训练样本局部扰动的容忍性较高。支持向量机算法就是在寻找这样的一个超平面。那么怎么样对距离进行判断呢？我们引入了函数距离和几何距离。
假设函数定义
在引入函数距离和几何距离之前，我们要先定义好它的假设函数。我们的假设函数的形式如下：
\[g(z) = \begin{cases} 1 \quad z \ge 0\\ -1 \quad 其它 \end{cases}\\ h_{w,b}(x)=g(w^Tx+b)\]其中，我们又把 \(\ z=w^Tx+b=0 \\) 称为超平面（hyperplane），即决策边界。它要比所处空间低一个维度。
函数距离（functional margin）
函数距离是我们定义的一个用来表示分类的正确性以及确信度的性质。我们用 \(\ \hat{\gamma} \\) 来表示。给定一个样本 \(\ (x^{(i)}, y^{(i)})\\) ，它的函数距离为：
\[\hat{\gamma}^{(i)} = y^{(i)}(w^Tx^{(i)}+b)\]显然在分类问题中，我们希望点距离超平面越远越好，即 \(\ |w^Tx^{(i)}+b|\\) 的值越大越好，越大我们越确信它被分类正确。与此同时，我们设定超平面之上的全部为正例，其标签为1；超平面之下的全部为反例，其标签都为-1。由此我们可以得到：
\[\begin{cases} \hat{\gamma}^{(i)} \gt 0 \ \Rightarrow\ 分类正确\\ \hat{\gamma}^{(i)} \le 0 \ \Rightarrow\ 分类错误 \end{cases}\]至此，我们可以得到这样的函数距离：其绝对值大小代表着确信度，其符号代表着正确性。令整个数据集的函数里为所有单个样本中函数距离最小的一个：
\[\hat{\gamma} = \min_i \hat{\gamma}^{(i)}\]此外，我们还注意到函数距离的一个特殊的性质：当 w 和 b 成比例缩放时，超平面没有变化，但是函数距离却会跟着变化（svm中w和b同缩放对决策边界无影响）：
\[{w'}^=nw,\ b' = nb'\\ \hat{\gamma}'={w'}^Tx+b'=nw^Tx+nb=n\hat{\gamma}\]这说明函数距离只能表示是否分类正确，以及相对的确信度。它会给你一个数字但是取不会提供参考标准，你无法辨别点是否真的远离或接近超平面。直觉上来说我们可以给 w 加个约束条件比如：用 \(\ (\frac{w}{||w||_2}, \frac{b}{||w||_2})\\) 来替换 \(\ (w,b)\\) ，这样当(w,b)任意放大或缩小时，函数距离将不会产生任何变化。这会对我们比较不同迭代次数中样本的确信度产生帮助。
几何距离（geometric margin）
几何距离就是样本点到超平面的欧几里得距离，标记它为 \(\gamma\) (没有函数距离符号的“帽子”)。任意一点到超平面的距离为：
\[\gamma = \frac{|w^Tx+b|}{||w||_2}\]式子中分母的意思是取w的第二范数,即对向量在各个维度的元素的平方和开根，此处可以类比点到直线、点到平面的距离公式来来理解。在此问题中，我们可以通过y的值的来实现绝对值：
\[\gamma^{(i)} = y^{(i)} \cdot \frac{w^Tx+b}{||w||_2}=y^{(i)} \cdot [ \frac{w^T}{||w||_2}x^{(i)} + \frac{b}{||w||_2} ]\]令数据集的几何距离为所有样本到超平面的几何距离最小的一个：
\[\gamma = \min_i \gamma^{(i)}\]我们注意到， \(\gamma = \frac{\hat{\gamma}}{||w||_2}\) ，且当 \(\ ||w||_2 =1\\) 时， \(\ \hat{\gamma} = \gamma\) 。于是我们就把几何距离和函数距离联系到了一起。与函数距离不同，放缩(w,b)对几何距离不会产生影响。此式可以同时表达正确性和有参考标准的确信度。
最大距离分类器（max margin classifier）
回想我们的初衷，我们希望的是即使是距离超平面几何距离最近的一个样本，也有着比较大的距离，即最大化数据集的几何距离。我们得到了我们问题的第一个数学形式：
\[\max_{\gamma,w,b} \gamma \quad s.t. \begin{cases} y^{(i)} (w^Tx^{(i)}+b) \ge \gamma \quad i=1,...,m\\ ||w|| _2= 1 \end{cases}\]此处令 \(||w||_2=1\) 是为了保证函数间隔等于几何间隔。对于几何间隔我们可以任意缩放w和b而不会产生任何影响，我们很容易就可以缩放w和b到满足这个条件的地步。我们设置 \(|w_1|=1,w_1^2+|w_2|=1\) 等等任何条件或是不添加条件，都不会对问题（最大化几何距离）产生任何影响。
然而，对上述问题使用拉格朗日乘子法时，“||w||=1”的曲线是非凸的（non-convex），难以用软件来求解最优值。我们需要对它进行改进。考虑函数距离与几何距离的关系，我们找到了原问题的一个等价形式：
\[\max_{\hat{\gamma},w,b} \frac{\hat{\gamma}}{||w||_2} \quad s.t. \quad y^{(i)} (w^Tx^{(i)}+b) \ge \gamma \quad i=1,...,m\]这样我们就避免了我们不喜欢的“ \(||w||_2=1\) ”。然而，其中的“ \(\frac{\hat{\gamma}}{||w||_2}\) ”仍然是非凸的。我们还需要继续找问题的等价形式。
回顾在几何距离中，我们可以任意放大缩小w和b，而放大缩小w和b等同于放大缩小 \(\hat{\gamma}\) ,故我们可以对函数距离设置约束。令 “ \(\hat{\gamma} \equiv1\) ”，我们得到原问题的第三个等价形式：
\[\max_{\hat{\gamma},w,b} \frac{1}{||w||_2} \quad s.t. \quad y^{(i)} (w^Tx^{(i)}+b) \ge \gamma \quad i=1,...,m\]而最大化 \(\frac{1}{||w||_2}\) 又等同于最小化 \(\frac{1}{2} {||w||_2}^2\) (常系数是为了求导方便)，我们得到原问题的最终的等价形式：
\[\max_{\hat{\gamma},w,b} \frac{1}{2}{||w||_2}^2 \quad s.t. \quad y^{(i)} (w^Tx^{(i)}+b) \ge \gamma \quad i=1,...,m\]这就是SVM的基本型。
参考资料：
- cs229-Lecture6
- cs229-Lecture7
- cs229 notes3
- [1]周志华.机器学习[M].北京:清华大学出版社,2016：121-123.