[分类] 感知机和支持向量机 (perceptron &

作者: 数据麻瓜 | 来源:发表于2018-12-21 02:17 被阅读220次

感知机是一个线性分类器，是向量机的基础。

为了方便叙述，仅考虑2维问题。如果数据是线性可分的话，那么一定存在一些线 $f(x)=\beta_0+\beta x$ ，使得线的两侧是两个不同的类。

1. 感知机模型：
Y={1,-1},如果 $\beta_0+\beta x>0$ ，则预测 $\hat{y}_i=1$ ;如果 $\beta_0+\beta x<0$ ，则预测 $\hat{y}_i=-1$ 。所以，如果出现误分类的话， $y_i(\beta_0+\beta x_i)<0$ 。
在这个模型中，我们的目标是将误分类点的个数->0,所以其实是在最小化一下这个loss function：
min $D(\beta_0,\beta)= min -\sum_{i \in M} y_i(\beta_0+\beta x_i)$ ,其中M是误分类点的index，用一些最优化方法可以解得：
$\frac{\partial D (\beta_0,\beta)}{\partial \beta_0}=-\sum_{i \in M} y_i x_i$ ; $\frac{\partial D (\beta_0,\beta)}{\partial \beta}=-\sum_{i \in M} y_i$

但感知机模型有一些问题：

如果一个平面线性可分的话，那一定存在不止一条的线可以划分这个平面，但我们显然是想要找到一条最好的
如果这些点线性不可分，那这个算法可能不会收敛

为了解决问题1，我们想在模型1的基础上加一些条件限制，于是有了hard-margin SVM:

2.Hard-Margin SVM
hard-margin SVM是在寻找一条线性分割线的同时，找到一个可以最大间隔超平面的线。
令 $\gamma_i = y_i(\frac{\beta_0}{||\beta||}+\frac{\beta x_i}{||\beta||})$ ,如果点 $x_i$ 是分类正确的话，那么 $\gamma_i$ 是点到超平面的距离。如果是误分类点的话，那么 $\gamma_i<0$ ,所以我们希望

$max_{\beta,\beta_0,||beta||=1} \gamma$
$s.t. y_i(\beta_0+\beta x_i) \ge \gamma$

这就保证了所有点到超平面的距离都大于 $\gamma$ ,最大化 $\gamma$ 使得我们能得到一个最大间隔超平面。

因为 $||\beta||=1$ ,所以 $\frac{1}{||\beta||}y_i(\beta_0+\beta x_i) \ge \gamma$ -> $y_i(\beta_0+\beta x_i) \ge ||\beta|| \gamma$ ，令 $||\beta|| =\frac{1}{\gamma}$ ,则这个模型的优化问题等价于：

$min_{\beta,\beta_0} \frac{1}{2}||\beta||^2$
$s.t. y_i(\beta_0+\beta x_i) \ge 1$

要求解这个问题，我们可以把这个优化问题写成最小化以下的拉格朗日方程： $L_p=\frac{1}{2}||\beta||^2-\sum_{i=1}^N\alpha_i [y_i(\beta_0+\beta x_i) -1]$ ，令一阶导为0求极值
$\frac{\partial L_p}{\partial \beta}=\beta-\sum_{i=1}^N\alpha_i y_i x_i=0$ ; $\frac{\partial L_p}{\partial \beta_0}=\sum_{i=1}^N\alpha_i y_i=0$
将这些值代入 $L_p=\frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j x_i x_j y_i y_j-\sum_i \alpha_i y_i[(\sum_{j=1}^N\alpha_j y_j x_j)x_i]+\sum_i\alpha_i=\alpha_i - \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i x_j$
考虑 $L_P$ 的对偶问题 $L_D=max_\alpha [\alpha_i - \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i x_j]$
$s.t. \alpha_i \ge 0,\sum_{i=1}^N\alpha_i y_i=0$

至于为什么这个方法要叫做Support Vector Machine,是因为我们会发现只有在两条边界线上的点对应的 $\alpha_i$ 会大于0，所以其实问题的解仅仅只和训练集中的一部分点有关，那这些点就被称为support vector。

求解对偶问题与求解原问题等价，那为什么要引入对偶问题呢？一个是因为对偶问题的求解一般会比较简单，而且对偶问题改变了算法复杂度。
对于原问题，算法复杂度与feature数有关，而对于对偶问题，算法复杂度与样本数有关。因为在SVM中有时会运用核函数进行升维，并且升维后的样本维度可能会大于样本数，所以对偶问题会更容易求解。
而且对偶问题的形式更容易引入核函数的概念

为了解决问题2，又可以再hard-margin模型的基础上加一些容忍度，使得模型可以容忍误分类点的存在。

3.Soft-Margin SVM
$min_{\beta,\beta_0} \frac{1}{2}||\beta||^2+C\sum_{i=1}^n \epsilon_i$
$s.t. y_i(\beta_0+\beta x_i) \ge 1-\epsilon_i; \epsilon_i \ge 0$