SVM处理非线性可分 KKT 对偶问题核函数

上一篇文章讲到，如果数据是线性可分的，直接使用最大边距作为目标函数，但是如果数据是线性不可分的情况下，该目标函数是不可用的。那么如何处理线性不可分的情况呢？How to Classify Complex Data？

数据映射到高维

image.png

主要步骤为

把低维的数据映射到高维的空间里（数据量变的比原本的远远大得多）
高维空间里的数据经过非线性变换器处理
最后转换成线性分类器
由上面步骤可知，数据虽然进入了高维的转换，数据量是变的很多，但是时间复杂度是一样的，因为最后还是使用线性分类器进行的。

拉格朗日等号条件处理

先来看看拉格朗日乘数法的概念：
拉格朗日乘数法（以数学家约瑟夫·路易斯·拉格朗日命名）是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题，其变量不受任何约束。这种方法引入了一种新的标量未知数，即拉格朗日乘数
简单总结为：拉格朗日乘数法是一个求极值的方法，极值的函数是目标函数受多个条件限制的多元函数，这个方法可以将函数和限制条件的函数通过拉格朗日乘数组合成求目标函数和限制条件的最终函数的最优化问题。即f(x)+lamda(g(x))

等号条件处理：
min f(x)
s.t. g(x)=0

举个例子：
约束条件为：
$min x1^{2}+x2^{2}$
$s.t. x2-x1 = -1$
通过拉格朗日乘数法，可以得到
$min x1^{2}+x2^{2}+\lambda(x1^{2}-x2^{2}+1)$
最后求拉格朗日乘法得到的函数进去求极值，这里是最小值，那么就可以通过求导数为0，得到的极值的解。
$\binom{\frac{\partial L}{\partial X1}}{\frac{\partial L}{\partial X2}} = \binom{2x1-\lambda }{2x2-\lambda}=\binom{0}{0}$
$\left ( \frac{\partial L}{\partial \lambda } \right ) = \left ( 0 \right )$
求解得到
$x1=\frac{1}{2},x2=-\frac{1}{2},\lambda =1$
拉格朗日等式极值求解的推导过程：

image.png

如果是多项式等式约束的话，如下所示，求解导数的时候就lamda一个个去求解

image.png

拉格朗日不等号条件处理

顾名思义，不等号条件就是存在不等式的，等式拉格朗日的乘数法是处于等号条件下的，那么我们可以根据不等号条件变成等号条件的处理方式。那根据拉格朗日乘数法的优化函数如下所示，那么如何得到呢？
$min x1^{2}+x2^{2}+\lambda(h(x))$

image.png

由上图可知，要想得到两个函数的极值，就要使h(x)=0
下面我们看看两个定理：

1、没有限制条件的最优解正好满足限制条件h(x)<=0
=>∂=0 h(x)<=0
2、没有条件下的最优解不满足限制条件h(x)<=0
=>h(x)=0 ∂>0
所以由①②可得∂h(x)=0
(1)当 h(x)<0，最佳解位于K的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)，所以∂=0
(2)h(x)=0最佳解落在K的边界，称为边界解(boundary solution)，此时约束条件是有效的(active),所以∂>0。
这两种情况的最佳解具有不同的必要条件。

image.png

这些条件合称为Karush-Kuhn-Tucker (KKT)条件
KKT条件就是在不等式约束条件的前提下，求得极值的原始可行性、对偶可行性、互补送持续的条件下求得的，所以原始可行性、对偶可行性、互补送持续也叫做KKT条件，如果存在不等式的约束条件，都会有KKT条件的
上面结果可推广至多个约束等式与约束不等式的情况。考虑标准约束优化问题(或称非线性规划)：

image.png

定义Lagrangian 函数

image.png

image.png