概述
- 优点：泛化错误率低，计算开销不大，结果易解释。
- 缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二分类问题。
- 适用数据类型：数值型和标称型
概念解释
线性可分：见图1，可以在图中画出一条直线将两组数据点分开。可以说，这组数据线性可分
分隔超平面：图1中将数据集分隔开的直线称为分隔超平面。此时在二维平面上是一条直线，如果是三维数据集，则会是一个平面。更高维度的，则会是一个超平面
图1
间隔与支持向量
给定训练集
基于训练集D在样本空间找到一个分隔超平面，将不同类别的样本分开，但这样的超平面有很多，如图1所示。
直观上看，两类数据正中间的超平面比较好（图1中标粗的直线），这个超平面离两类数据的间隔最大，对训练样本局部扰动的“容忍”性最好。由于训练集的局限性或噪声的因素，训练集外的样本可能更接近分隔界，这将使许多分隔超平面出现错误，而离两类数据间隔最大的超平面受影响最小。简言之，这个分隔超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。
分隔超平面可用如下式子来描述：
样本空间中任意点x到超平面的距离r为：
输入数据给分类器会输出一个分类标签。这相当于一个类似于Sigmoid函数在作用。下面用类似于单位阶跃函数的函数对作用得到
，其中当u < 0时f(u)输出-1，反之则输出+1。不妨令：
如图2所示，距离超平面最近的几个数据点使式的等号成立，它们被称为支持向量（support vector），两个异类支持向量到超平面的距离之和为：
被称为间隔
图2
显然，我们需要找到具有最大间隔的分隔超平面，也就是要找到满足式中约束的参数w和b，使得
最大，即：
上述公式可重写为：
由此，我们就得到SVM(Support Vector Machine)的基本型。
拉格朗日乘子法和KKT条件
拉格朗日乘子法
拉格朗日乘子法多用于组合优化问题。例如下面这个带约束的优化问题：
这是一个带等式约束的优化问题，有目标值，有约束条件。假设没有约束条件,那么这个问题该怎么求解？
直接f对各个x求导等于0，解x就可以了，可以看到没有约束的话，求导为0，那么各个x均为0吧，这样f=0了，最小。但是x都为0不满足约束条件，那么问题就来了。
额外说一点，为什么上面说求导为0就可以呢？理论上多数问题是可以的，但是有的问题不可以。如果求导为0一定可以的话，那么f一定是个凸优化问题，什么是凸的呢？像下面这个左图：
凸的就是开口朝一个方向（向上或向下）。更准确的数学关系就是：
需要注意的是这个条件是对函数的任意x取值。如果满足第一个条件就是开口向上的凸，第二个是开口向下的凸。
对于凸问题，你去求导的话，只有一个极点，这就是最优点。而像上图右边的图，你去对它求导的话，会得到多个极点，我们可以直接从图看到，只有其中一个极点是最优解，其他的是局部最优解。如果这是真实问题，要选择哪个呢？说到这里，我们要明白拉格朗日法是一定适合于凸问题的，但不一定适合于其他问题。
回到有约束的问题上，既然有了约束不能直接求导，那么我们可以把这个约束乘一个系数加到目标函数中去，这样就相当于既考虑了原目标函数，也考虑了约束条件，例如上面的函数，将约束条件加进去就变为：
分别对x求导等于0，如下：
把它再代到约束条件中去，可以看到2个变量两个等式，可以求解，将得到的解再代回去求x就可以了。那么一个带等式约束的优化问题就通过拉格朗日乘子法完美解决了。还有一种带有不等式的约束问题怎么办？那么就需要用更一般化的拉格朗日乘子法，即KKT条件，来解决这种问题了。
KKT条件
KKT条件指在满足某些规则条件下, 非线性规划问题能有最优解的充要条件, 是广义拉格朗日乘数的重要成果
一般优化问题(含等式和不等式约束约束):
引入Lagrange算子,
:
可将
和
分别看做两个约束
和
的限制条件
KKT条件指上述问题的最优点必须满足:
- 约束条件满足:
-
即,
最优点处,
必须是
和
的线性组合
引入拉格朗日算子可以求出极值的原因:
由于f(t)的dt变化方向受其他不等式的约束, 且在极值
与
,
之间存在线性关系, 故引入拉格朗日算子可以求出极值
-
且
不等式
的限制条件有方向性, 故
, 等式
的限制条件无方向性, 故
无符号限制
参考
学习SVM，这篇文章就够了！（附详细代码）
支持向量机（SVM）从入门到放弃再到掌握
一文理解拉格朗日对偶和KKT条件
浅谈最优化问题的KKT条件
直观理解KKT条件
网友评论