？？拉格朗日乘子法
？？Soft Margin的优化
SVM基本思想
SVM用来解决线性不可分问题。
基本思想是，把原始空间映射到高维空间，转化为线性可分问题。
overview
SVM解决线性可分问题
SVM本质上是一个线性分类器，形成一个超平面。
-
在哪？如图3所示，是和超平面垂直的一个向量。证明过程如图3所示。
线性分类器 -
空间中的一个点，到超平面的距离如何计算？原点到超平面的距离？
到超平面的距离
如何挑选模型？A和B的训练误差都为0。但是B更好，分割得平均，无偏，有更强的泛化能力。
image.png
如何量化B比A好呢？引入margin。如图7所示，B的margin更大。“Support Vectors”就是，恰好在margin上的样本。
margin
目标函数
定义两个margin超平面分别为：和。
共有两个目标：一是，把样本分对；二是，最大化margin。
然后得到目标函数，一个带约束的二次优化问题。
image.png
如何优化？
？？用“拉格朗日乘子法”
拉格朗日乘子法
image.png
image.png
Soft Margin
实际中可能不存在一个解，能把所有训练样本都分对。所以就想出了Soft Margin来解决这个问题。
Soft Margin的基本思想是，允许支持向量机在一些样本上出错。如图15所示，通过修改约束条件，在左侧加一个，这样即使有些样本出错，因为加了一个数，使得仍能满足约束条件，可以得到解。
image.png
SVM解决线性不可分问题
一个例子：如图18所示，在一维空间线性不可分问题，映射到二维空间后，就线性可分了。
一个例子
原始问题很复杂，做一个映射后，就变得很简单。
image.png
映射函数怎么选？
其实我们根本不需要知道映射函数是什么，只需要知道kernel函数就行了。怎么做到的，看下面：
如下图所示，我们假设了一个映射函数，它把m维映射到维。
支持向量机的优化过程中，时间复杂度最高的地方是输入向量间做内积。我们增加输入维度后，时间复杂度由 image.png
image.png
这个方法叫做Kernel Trick，是支持向量机最巧妙的地方。图24是Kernel Trick的总结。
image.png
常用的kernel函数：
Kernels
如何优化？
求解w和b过程中，发现根本不需要知道映射函数是什么，就能求出w和b。
image.png