支持向量机（support vector machine，SVM）是一种出色的分类技术，也可以用于回归分析（SVR）。这种技术可以很好的应用于高维数据，避免维度灾难等问题。
SVM有一个特点就是使用训练集中的一个子集来表示决策边界，该子集称作支持向量。
最大边缘超平面
SVM的核心目标是找到分类中的最大边缘超平面，让其作为决策边界，那么什么是最大边缘超平面呢？
摘自周志华机器学习
可以看到，中间的这些直线把“+”和“-”分隔开来，形成了两类，这些直线就叫做超平面，它使得所有的“+”号在超平面的一侧，所有的“-”号在另外一侧，由于这些超平面都能完美的分隔+和-号的类别，所以误差是0.
但是可以发现，这种超平面有无数多个（图中就能看到有好多个），如果有一些未知的点需要预测分类，那么他们可能未必会被这些超平面完美的分隔：
未知点
以最下侧的超平面为例，如果我们有未知的点按照蓝色排布，那么可以看到，最下侧的这个超平面完全不能分类所有蓝色点的“-”号，那么如果它作为决策边界，泛化能力就不是很好。
我们肯定要从这些超平面中选一个最合理的作为决策边界，使得未知的点尽量的能被正确预测分类，那么肯定是上图中间的这个超平面最好了，我们目测就可以得到结果，因为它离两边这些点的距离围成的面积应该是最大的，而且两边的面积基本是差不多的。（个人理解）所以应该能装得下更多的未知点，也就能得到最好的泛化效果。
为了不用肉眼观测，能量化的得到这个结果，我们可以定义最大边缘超平面。
下图中有两个决策边界，和
，其中每个决策边界都对应着两个超平面(记作
)。其中
是由
进行两侧平移，直到接触到最近的一个训练集的点停止，生成的，同理
也是。
我们把两个超平面（同一个决策边界生成的）之间的距离叫做分类器的边缘，那么下图中，显然生成的两个超平面距离应该是最大的，
就叫做最大边缘超平面（
虽然是决策边界，但是决策边界都是超平面）。
通常来说，较大边缘的超平面具有更好的泛化误差，如果边缘比较小，那么决策边界的轻微扰动都可能对分类产生显著影响。
SVM算法的核心就是设计最大化决策边界边缘的分类器，以保证最坏情况下泛化误差最小。
线性支持向量机
公式
假设有一个包含个训练样本的二元分类问题，每个样本表示为一个二元组
, 其中
，对应于第i个样本的属性集（一个样本有多个属性/特征）,设y有-1和1两个类别，则一个线性分类器的决策边界可以写成如下形式：
其中的为参数，
是法向量（垂直于决策边界）的向量，代表着超平面的方向，而
代表超平面与原点之间的距离（可以用一次函数的公式来理解）。
为什么一定会垂直于决策边界呢？我们设有两个点
是决策边界上的两点，那么有：
二者相减有：
因为肯定是平行于决策边界的，那么为了保证内积为0，
肯定要垂直于决策边界。
注意图中的w
根据以上的决策边界，则肯定有：
在决策边界上方的点肯定存在
使得
（上图中的方块点）
在决策边界下方的点肯定存在使得
如果上方的点是1类，下方是-1类，则有：
如果我们能得到，那么就可以用这个公式对未知点进行预测分类。代入公式，如果
就是1类，反之则为-1类。
接下来我们的任务就是如何求这两个参数，首先，既然是求最大边缘超平面，我们要把决策边界的边缘算出来。
决策边界的边缘
根据上图，考虑那些离决策边界最近的方形和圆形，我们可以得到两个平行的超平面表示如下：
决策边界的边缘就是这两个超平面的距离。
参考上图的，不难得出边缘
为：
其中是w的2范数。
很显然，我们想要让这个最大，那么就要让
最小。
于是，接下来我们的求参数目标就明确了。
参数的确定
由于肯定是非负的，我们可以改写一下
这个式子，让它变成求
的最小值。
既然要求最小值，就需要有另外一个约束条件，否则是没办法求的，我们来看之前总结的线性SVM分类器的公式：
由于和
是决策边界的两个超平面，我们从上图中可以看出，所有的点（除了这两个超平面经过的点以外，经过的点是离决策边界最近的点），都肯定有
和
。
我们把y引入进来，那么这两个式子就能合到一起写为：
注意不要和之前总结的公式中的弄混，那个条件是最终预测分类的公式，也就是表明只要在决策边界的上方就可以进行分类，而现在的>=1是在已知训练集的情况下求模型的参数。
综合以上的式子，我们可以得到求参数的基本式：
目标函数是二次的，而约束在参数和
上是线性的，因此这是一个凸优化问题，不存在局部优化的问题。
求这一套公式的最小值，需要用到拉格朗日乘数法，这个我也不是很明白，就按照百度百科的定义往里套：
设给定二元函数z=ƒ(x,y)和附加条件φ(x,y)=0，为寻找z=ƒ(x,y)在附加条件下的极值点，先做拉格朗日函数
，其中λ为参数。
令F(x,y,λ)对x和y和λ的一阶偏导数等于零，即
F'x=ƒ'x(x,y)+λφ'x(x,y)=0 [1]
F'y=ƒ'y(x,y)+λφ'y(x,y)=0
F'λ=φ(x,y)=0
由上述方程组解出x,y及λ，如此求得的(x,y)，就是函数z=ƒ(x,y)在附加条件φ(x,y)=0下的可能极值点。
虽然我们这里的附加条件是大于等于1的，不过不妨改写一下试试，则有：
其中的就是拉格朗日乘子，理论上来说，拉格朗日乘子可以为任何值。
如果约束条件是=0的话，我们就可以直接对和
求偏导数，让他们等于0，就能求得参数。
但是目前条件并不是等于0的，而是大于等于0的。
处理不等式约束一种方法就是变换成一组等式约束，根据KKT条件，可以限制拉格朗日乘子飞赴，把之前的约束变换为：
该约束表明，除非训练样本满足方程，否则拉格朗日乘子必须为0。
结合上面展示决策边界和超平面的图，我们可以想到，满足这个方程的样本，肯定都在决策边界生成的两个超平面上。这些样本处的拉格朗日乘子肯定够大于0，而其他样本的拉格朗日乘子，肯定等于0，因此问题得到简化。因为参数的确定仅依赖于这些在超平面上的样本。
这些在超平面上的样本，被称作支持向量，这也就是支持向量机的命名缘由。
有了以上的修改后的约束，我们可以在 对
和
求偏导，并让他们等于0.
我们已知，这个时候的和
是有满足条件的最优解的，把这两个式子代入原公式，就能得到
的最小值（当然此时因为不知道拉格朗日乘子，我们是求不出来的），代入公式可得：
该函数叫做对偶拉格朗日函数。
用这个函数，就是把之前求w和b的公式变换成了求拉格朗日乘子的公式，同时需要注意，这个式子中是求拉格朗日对偶函数的最大化问题。
我们可以用二次规划法或者SMO方法来求拉格朗日乘子。
二次规划算法比较通用，但是计算量比较大，SMO算法的核心就是把复杂的式子变换成比较简易的之后，用二次规划来计算。
SMO的基本思路是：先固定之外的所有参数，然后求
上的极值，由于存在约束
，如果固定了
之外的其他变量，则能求出
。
那么对偶函数里有两个λ，我们就可以固定这两个λ之外的参数，之后求解。
其中有一个λ不满足KKT条件，则目标函数就会在迭代后减小，违背程度越大，变量更新后导致的目标函数值就越大。所以SMO先选取违背KKT条件最大的变量，第二个变量选择使目标函数值见效最快的变量，使选取的两个变量对应样本之间的间隔最大。
然后可以变换为简单的二次规划问题：
找到一组λ后，就可以用原公式求得的解，决策边界可以表示为：
之后b可以通过求解。
因为λ通过数值计算得到，因此可能存在误差，则b可能不唯一。通常我们可以用b的平均值作为决策边界的参数。
例子
例子
如图所示，这组数据集有两个特征和一个
标签，我们要对其进行建模分类，可以得到有两个拉格朗日乘子（支持向量上的），其他的均为0.
我们可以得到有：
第一个是针对
的参数，以此类推。
有了，可以求得
有：
可以根据两个b求平均值，得到b=7.93，因此就能得到分类的模型。
如果需要做预测，把对应点的x向量代入到模型中，求得结果为1的话，就是方形类，其他为圆形类。
非线性支持向量机
上面讨论的模型最终都会生成一条直线，也就是线性的模型，那么往往需要判断非线性的如何处理呢，这里需要引入核函数的技术。
核函数
要把SVM应用到非线性决策边界的数据集上，就要把数据集从原来的坐标空间x变换到新的坐标空间中。
我们假定存在一个合适的函数来变化给定的数据集，那么变换之后，我们就可以根据
来构建线性决策边界（类似于换元法，回忆一下）。变换之后，线性决策边界具有以下的形式：
根据线性SVM的参数计算公式，我们把公式里面的换成
，即可求解。
不过这种方式往往会涉及到向量对的点积，计算比较麻烦，当特征数较多时，可能会造成维度灾难的问题，因此我们要引入核函数。
核函数是一种使用原属性集计算变换后的空间中的相似度的方法，简而言之就是，我们如果按照上一段说的算法，则我们需要先计算，然后再计算参数，而我们运用核函数，可以直接计算\boldsymbol{x}就可以达到变换属性集的目的。
我们令，这样就可以把映射的函数变成了原属性集的计算。
就是核函数。
但是这个一般我们是不知道的，因此我们要找寻几种通用的函数，让他们可以实现
的功能，以便模拟非线性的决策边界。
这里我们引入一个Mercer定理，所有的核函数都必须满足Mercer定理。
Merver定理
任何半正定的函数都可以作为核函数。所谓半正定的函数f(xi,xj)，是指拥有训练数据集合（x1,x2,...xn)，我们定义一个矩阵的元素aij = f(xi,xj)，这个矩阵式n*n的，如果这个矩阵是半正定的，那么f(xi,xj)就称为半正定的函数。这个mercer定理是核函数必要条件.
通常有如下几种核函数：
摘自周志华机器学习
应用的时候，我们直接把核函数作为就可以了，也就是用代替。
另外需要注意，类似于高斯核函数这种带参数的函数，需要调整参数来满足不同的决策边界形状。
我们也可以通过核函数的组合来形成新的核函数：
- 如果
为核函数，那么对于任意正数 *
，有线性组合
也是核函数。
- 如果
- 如果
为核函数，则有任意函数
)
也为核函数。
软边缘
我们直到一般算法都要防止过拟合，防止噪声带来的模型泛化能力下降，那么SVM的防止过拟合方法就是软边缘。
image.png
如图，可以看到，图中有一些+类跑到了决策边界的下方，而有一些-类跑到了决策边界的上方，很明显这些类是不满足之前我们确定的约束的，在软边缘中，我们允许这种情况发生。同时引入一个松弛变量来表明软边缘的幅度，则有：
其中就是松弛变量。
很显然，这个变量的意义就是把下侧的超平面向上移动，上侧的向下移动，也就是说代入了误差估计。
当然，不可能无限制的增加，那样的话可能会包括太多错误样本，我们可以把最开始的目标函数改写，不求的最小值，而是改写成如下的式子：，其中C和k是指定的参数，表示对误分训练实例的惩罚，一般来说，k=1。
当C为无穷大时，公式迫使所有样本满足约束，而当C取有限值时，则允许部分样本不满足约束。
根据该公式，则我们可以改写拉格朗日函数为：
其中，前面两项是需要最小化的目标函数，第三项表示与松弛变量相关的不等式约束，最后一项是要求的值非负的结果。
其中均大于等于0，是拉格朗日乘子。
此外，根据KKT条件，可以变换约束如下：
注意，上述三个式子中的是非零的，当且仅当训练样本位于直线
上或者
。另外对于误分类的训练样本，
都为0.
我们按照正常优化的算法，对,
,
求偏导数，可以得到参数：
代入原公式，可以得到只包括拉格朗日乘子的对偶拉格朗日函数。
这个式子看上去跟不加软边缘的对偶函数是一样的，但是约束是不同的。
软边缘的对偶函数约束为
之后就可以用二次规划或者SOM求参数值了，从而得到模型。
这就是带软边缘的SVM。
多分类
以上提到的都是二元分类的办法，那么多分类可以参考常用的多分类处理，用一对一方法，如果有多分类问题，我们可以分解为K（K-1）/2个二类分类器，每一个分类器用来区分一对类。（注意这里的y都是单独的类，不是一堆类别的集合）
当为构建分类器时，其他不属于这两类的点都被忽略掉。
之后针对需要预测分类的样本，我们用不同的分类器进行分类，最后进行投票，得到结果。
以上就是SVM（用于分类的支持向量机）的内容，最后看看该算法的特点：
特征
- SVM是凸优化问题，不存在局部最优，所以性能比较好。
- SVM算法中，需要制定核函数类型，防止过拟合的话我们还需要一个C作为代价函数。
- 如果数据中存在分类的属性值（离散化），可以考虑引入哑变量，将每个属性值二元化。
网友评论