支持向量机核心内容

支持向量机的学习路线：从回归问题到二分类问题，最大化间隔，max 1/||w||，min ||w||²/2，拉格朗日对偶问题，KKT条件，SMO算法。

1. 从线性回归到支持向量机

线性回归很简单：

给定一系列(x,y)，求线性函数f(x) = w*x + b，使得
min Σ(f(x) - y)^2

如果y不是连续值，而是离散的分类结果，该怎么处理？特别的，在二分类问题中该怎么处理？简单，将连续的y转化为离散的-1和1就行了。
转换方法有很多，比如最简单的：

g = -1 if y <0
g = 1 if y≥ 0

为了方便以后求导，这里用logistic函数进行转换，这里记作g(y)。logistic函数的形状可以参考https://blog.csdn.net/bitcarmanlee/article/details/51154481。模型变为：

给定一系列(x,y)，求线性函数f(x) = w*x + b，使得
min Σ(g(f(x)) - y)^2

但是……但是……Σ(g(f(x)) - y)^2 没有简单的方法去求解……所以我们换个方法，使用另外一个损失函数，将优化问题改为“最大化间隔”，详情可以参考https://blog.csdn.net/v_july_v/article/details/7624837
求解模型变为：

给定一系列(x,y)，求线性函数f(x) = w*x + b，使得
max d
s.t. d ≤ y*f(x)/||w||
y*f(x)称为函数间隔，y*f(x)/||w||称为几何间隔。

||w||是w的L2范数，也就是常说的欧式空间几何长度，可以参考https://blog.csdn.net/shijing_0214/article/details/51757564。修改后的模型称为支持向量机。

2. 模型转换

首先将问题中的中间变量d消除，令d = c/||w||，则问题变为

给定一系列(x,y)，求线性函数f(x) = w*x + b，使得
max c/||w||
s.t. y*f(x) ≥ c

f(x) = w*x+b与||w||可以进行等比例缩放，因此问题可以变为：

max 1/||w||
s.t. y*f(x) ≥ 1

将||w||的平方根消除，对目标函数做点小变换，问题转为：

min w^2/2
s.t. y*f(x) ≥ 1

这个时候已经可以用非线性规划的工具去求解了。

3. 拉格朗日对偶问题

接下来就是非常tricky的部分了。首先将问题转化为拉格朗日对偶问题，然后用SMO算法可以快速求解。为嘛转换为拉格朗日对偶问题？除了方便求解外，还有一个原因：有的时候我们没有办法用线性函数来进行分类（即f(x)是非线性函数），我们得使用核函数来进行处理，这种处理方法是基于拉格朗日对偶问题转换后的形式进行操作的。
首先，原问题的拉格朗日函数为L = w²/2 + Σλ*(1-y*f) ，通过KKT我们将问题转化为：

L' = 0
y*f ≥ 1
λ*(y*f - 1) = 0
λ ≥ 0

其中：

L'|w = 0 => w = Σλyx
L'|b = 0 => Σλy = 0

然后可以得到L = Σ_iλ_i - (Σ_i,jλ_iλ_jx_ix_j))/2，顺利把w和b都消除掉了~并且有

L'|λ = 0
λ ≥ 0

上面的条件可以转化为求解一个最大化优化问题：

max L(λ)
s.t. λ ≥ 0

至于为什么可以这么转化，具体可以参考：https://blog.csdn.net/blackyuanc/article/details/67640844

4. SMO：针对支持向量机的快速求解方法

1998年，Microsoft Research的John C. Platt在论文《Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines》中提出针对上述问题的解法：SMO算法，它很快便成为最快的二次规划优化算法，特别是在针对线性SVM和数据稀疏时性能更优。简单来说，步骤是：
循环执行下述步骤：
(1) 选取两个λ_i和λ_j
(2) 求解问题：
max L(λ_i, λ_j)
s.t. Σλy = 0
直到L无法再优化。具体的推导和步骤还可以参考https://www.cnblogs.com/xxrxxr/p/7538430.html。

5. 核函数

当遇到线性不可分的问题时，我们可以简单的用一个新的一次变量代替高次变量，这样相当于把低维的特征空间映射到高维空间。
比如说y = x+x²就可以用y = x₁+x₂代替，其中x₁ = x，x₂ = x²，特征空间由一维的[x]变为了二维的[x₁,x₂]。
定义一个非线性映射：φ(x)，比如说上面例子里面φ(x) = [x, x²]，我们可以对(φ(x),y)使用支持向量机。将决策规则中的f(t)从wφ(t) + b改为f(t) = wy<φ(x)φ(t)> + b (这里x，y都是已知的训练数据点，t是预测用的特征数据)，则拉格朗日对偶问题优化的L(λ) = Σ_iλ_i - (Σ_i,jλ_iλ_jy_iy_j<x_i,x_j>))/2。
为了避免爆炸性的计算引入核函数。定义核函数K(x,z) = <φ(x)φ(z)>为计算两个向量在隐式映射过后的空间中的内积的函数，可以得到L(λ) = Σ_iλ_i - (Σ_i,jλ_iλ_jy_iy_jK(x_i,x_j)))/2。我们其实并不需要内积展开的显式结构，只需要有不同x下的内积的值就行了，因此使用核函数的形式事先在低维上进行计算，而将实质上的分类效果表现在了高维上。