？？拉格朗日乘子法
？？Soft Margin的优化

SVM基本思想

SVM用来解决线性不可分问题。
基本思想是，把原始空间映射到高维空间，转化为线性可分问题。

overview

SVM解决线性可分问题

SVM本质上是一个线性分类器，形成一个超平面。

1. 在哪？如图3所示，是和超平面垂直的一个向量。证明过程如图3所示。
   线性分类器

2. 空间中的一个点，到超平面的距离如何计算？原点到超平面的距离？

   
   到超平面的距离
   

   如何挑选模型？A和B的训练误差都为0。但是B更好，分割得平均，无偏，有更强的泛化能力。

   
   image.png
   如何量化B比A好呢？引入margin。如图7所示，B的margin更大。“Support Vectors”就是，恰好在margin上的样本。
   margin

目标函数

定义两个margin超平面分别为：和。

image.png
共有两个目标：一是，把样本分对；二是，最大化margin。
然后得到目标函数，一个带约束的二次优化问题。
image.png

如何优化？

？？用“拉格朗日乘子法”

拉格朗日乘子法
image.png
image.png

Soft Margin

实际中可能不存在一个解，能把所有训练样本都分对。所以就想出了Soft Margin来解决这个问题。
Soft Margin的基本思想是，允许支持向量机在一些样本上出错。如图15所示，通过修改约束条件，在左侧加一个，这样即使有些样本出错，因为加了一个数，使得仍能满足约束条件，可以得到解。

image.png
image.png

SVM解决线性不可分问题

一个例子：如图18所示，在一维空间线性不可分问题，映射到二维空间后，就线性可分了。

一个例子

原始问题很复杂，做一个映射后，就变得很简单。

image.png

映射函数怎么选？

其实我们根本不需要知道映射函数是什么，只需要知道kernel函数就行了。怎么做到的，看下面：
如下图所示，我们假设了一个映射函数，它把m维映射到维。

image.png
支持向量机的优化过程中，时间复杂度最高的地方是输入向量间做内积。我们增加输入维度后，时间复杂度由 image.png
image.png
这个方法叫做Kernel Trick，是支持向量机最巧妙的地方。图24是Kernel Trick的总结。
image.png
常用的kernel函数：
Kernels

如何优化？

求解w和b过程中，发现根本不需要知道映射函数是什么，就能求出w和b。

image.png

支持向量机的发展路径

image.png