一、硬间隔SVM

支撑向量机也是一种硬分类模型，在之前的感知机模型中，我们在线性模型的基础上叠加了符号函数，在几何直观上，可以看到，如果两类分的很开的话，那么其实会存在无穷多条线可以将两类分开。在 SVM 中，我们引入最大化间隔这个概念，间隔指的是数据和直线的距离的最小值，因此最大化这个值反映了我们的模型倾向。

1. 模型定义

假设有以下数据：

SVM的主要思想是在特征空间中寻找一个最大间隔的超平面实现数据的二分类，SVM属于判别模型。这里的间隔指的是样本点到分离超平面的距离的最小值，用函数来表达。下图中在和线上的样本点就叫支持向量：

支持向量机
超平面实现将数据的正例和负例分隔开，因此有（约束为分类任务的要求）：

另外最大间隔通过以下方式来表达：

然后求解支持向量机就可以转化为以下带约束的优化问题：

上述优化问题还可以进一步转化：

【对于这个约束 %3E0#card=math&code=y_i%28w%5ETx_i%2Bb%29%3E0&height=20&width=109)，不妨固定 %3D1%3E0#card=math&code=%5Cmin%20y_i%28w%5ETx_i%2Bb%29%3D1%3E0&height=20&width=164)，这是由于分开两类的超平面的系数经过比例放缩不会改变这个平面，这也相当于给超平面的系数作出了约束。】

由此上述优化问题转化为：
%3D1%5C%5C%0A%5CRightarrow%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%5C%20s.t.%5C%20y_i(w%5ETx_i%2Bb)%5Cge1%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A#card=math&code=%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%5C%20s.t.%5C%20%5Cminiy_i%28w%5ETx_i%2Bb%29%3D1%5C%5C%0A%5CRightarrow%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%5Cge1%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A&height=82&width=643)

这是一个带N个约束的凸优化问题，有很多求解这种问题的软件。

1. 优化问题的转化

但是，如果样本数量或维度非常高，直接求解困难甚至不可解，于是需要对这个问题进一步处理。上述优化问题可以使用拉格朗日乘子法来求解，构建拉格朗日函数：

然后上述优化问题就可以转换为以下优化问题：

我们可以简单地看一下为什么可以这么转化：

然后使用以下结论继续对该优化问题进行转化：

因此该优化问题可以继续转化：

总结一下，该优化问题经历了以下转化过程：

1. 模型求解

• 对求导

  

• 求解

  

这里我们可以看出是数据的线性组合。

• 得出

  

因此该优化问题就相当于：

也就相当于：

• KKT条件

首先定义该优化问题的KKT条件：

)%3D0(slackness%5C%20complementary)%5C%5C%0A%26%5Clambda_i%5Cge0%5C%5C%0A%261-y_i(w%5ETx_i%2Bb)%5Cle0%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0A%26%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w%7D%3D0%2C%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20b%7D%3D0%0A%5C%5C%26%5Clambda_k%281-y_k%28w%5ETx_k%2Bb%29%29%3D0%28slackness%5C%20complementary%29%5C%5C%0A%26%5Clambda_i%5Cge0%5C%5C%0A%261-y_i%28w%5ETx_i%2Bb%29%5Cle0%0A%5Cend%7Balign%7D%0A&height=97&width=352)

该优化问题满足上述KKT条件，这是由于以下定理：

KKT条件中也叫松弛互补条件，即和总有一个为0。也就是说只有支持向量对应的才可能有值（），而其他不在和上的样本点对应的一定为，该性质可以用来求出。
我们已经根据求出了，接下来要求出，我们可以通过求解来得出各个，而这个过程也是支持向量机算法计算量最大的地方，这里我们就不展示过程了。
找出求解得到的不等于的，也就是支持向量对应的，假设其中一个支持向量为，则有，最终可以解得：

二、软间隔SVM

我们的训练数据通常不是理想的线性可分，有时甚至是线性不可分的数据。对于存在噪声的一些数据，我们应该允许一点分类错误，因此我们需要对目标函数进行一些调整：

1. 使用误分类点的个数作为loss

   

显然使用的指示函数是不连续的，不利于求解，所以不使用这种loss函数。

1. 使用距离作为loss

   

该函数为合页损失函数（Hinge Function），令，则对的图像如下：

合页损失函数

1. 软间隔SVM的优化问题

   

引入，则该优化问题转化为：

上面的式子中，常数可以看作允许的错误⽔平，同时上式为了进⼀步消除符号，对数据集中的每⼀个观测，我们可以认为其⼤部分满⾜约束，但是其中部分违反约束，因此这部分约束变成。
软间隔SVM也是使用拉格朗日乘子法进行求解。