SVM模型
简介
支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。
SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。
相关概念
线性可分：二维空间上，两类点被一条直线完全分开叫做线性可分。
和 
是 n 维欧氏空间中的两个点集。如果存在 n 维向量 w 和实数 b，使得所有属于 的点 
都有 
，而对于所有属于 的点 
则有 
，则我们称 和 线性可分。
最大间隔平面：从二维扩展到多维空间中时，将 和 完全正确地划分开的 
就成了一个超平面。
为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。
支持向量：样本中距离超平面最近的一些点，这些点叫做支持向量。
SVM最优化问题
超平面表示方法
\[w^{T} x+b=0
\]
扩展到 \(n\) 维空间后，点 \(x=\left(x_{1}, x_{2} \ldots x_{n}\right)\) 到直线 \(w^{T} x+b=0\) 的距离为:
\[\frac{\left|w^{T} x+b\right|}{\|w\|}
\]
其中 \(\|w\|=\sqrt{w_{1}^{2}+\ldots w_{n}^{2}}\)
支持向量到超平面的距离为 d，其他点到超平面的距离大于 d。
于是有下列公式：
\[\begin{cases}\frac{w^{T} x+b}{\| w|| d} \geq 1 \quad y & =1 \\ \frac{w^{T} x+b}{\|w\| d} \leq-1 & y=-1\end{cases}
\]
\(\|w\| d\) 是正数, 我们暂且令它为 1 （之所以令它等于 1, 是为了方便推导和优化，且这样做对目 标函数的优化没有影响），故:
注：个人觉得是因为这个超平面对于一定的数据集是确定的，w是常数，d也是常熟，只是未知而已，但是是确定的，就像高中导数经常用的x0，去掉对优化无影响。
\[\left\{\begin{array}{l}
w^{T} x+b \geq 1 \quad y=1 \w^{T} x+b \leq-1 \quad y=-1
\end{array}\right.
\]
将两个方程合并，我们可以简写为:
注：还要加上y=1或-1的条件才行，参考中的这个有点问题
\[y\left(w^{T} x+b\right) \geq 1
\]
至此我们就可以得到最大间隔超平面的上下两个超平面：
每个支持向量到超平面的距离可以写为:
\[d=\frac{\left|w^{T} x+b\right|}{\|w\|}
\]
由上述 \(y\left(w^{T} x+b\right)>1>0\) 可以得到 \(y\left(w^{T} x+b\right)=\left|w^{T} x+b\right|\), 所以我们得到:
\[d=\frac{y\left(w^{T} x+b\right)}{\|w\|}
\]
这里乘上 2 倍也是为了后面推导，对目标函数没有影响。刚刚我们得到支持向量 \(y\left(w^{T} x+b\right)=1\), 所以我们得到:
\[\max \frac{2}{\|w\|}
\]
再做一个转换:
\[\min \frac{1}{2}\|w\|
\]
为了方便计算（去除 \(\|w\|\) 的根号），我们有:
\[\min \frac{1}{2}\|w\|^{2}
\]
所以得到的最优化问题是：s.t.是subject to 局限于,加上y=+1或-1
\[\min \frac{1}{2}\|w\|^{2}
s . t . \quad y_{i}\left(w^{T} x_{i}+b\right) \geq 1
\]
这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。
对偶问题
拉格朗日乘数法
就是微积分多元函数求极值那个
等式约束优化问题
\[\min f\left(x_{1}, x_{2}, \ldots, x_{n}\right)
\]
s.t. \(\quad h_{k}\left(x_{1}, x_{2}, \ldots, x_{n}\right)=0 \quad k=1,2, \ldots, l\)
我们令 \(L(x, \lambda)=f(x)+\sum_{k=1}^{l} \lambda_{k} h_{k}(x)\), 函数 \(L(x, y)\) 称为 Lagrange 函数，参数 \(\lambda\) 称 为 Lagrange 乘子没有非负要求。
利用必要条件找到可能的极值点:
\[\begin{cases}\frac{\partial L}{\partial x_{i}}=0 & i=1,2, \ldots, n \\ \frac{\partial L}{\partial \lambda_{k}}=0 & k=1,2, \ldots, l\end{cases}
\]
等式约束下的 Lagrange 乘数法引入了 
个 Lagrange 乘子，我们将 
与 
一视同仁，把 
也看作优化变量，共有 
个优化变量。
不等式约束优化问题
主要思想是将不等式约束条件转变为等式约束条件，引入松弛变量，将松弛变量也是为优化变量。
可以写为:
\[\begin{array}{ll}
\underset{x}{\operatorname{minimize}} & f(\boldsymbol{x}) \\text { subject to } & g_{i}(\boldsymbol{x}) \leq 0, i=1,2, \cdots, m
\end{array}
\]
引入拉格朗日乘子 \(\left(\mu_{i} \geq 0\right)\), 定义上述问题的拉格朗日量 (Lagrangian) 如下
\[L(x, \mu)=\left[f(x)+\sum_{i=1}^{m} \mu_{i} g_{i}(x)\right]
\]
同时定义拉格朗日对偶函数 (Lagrange dual function) 如下:
\[F(\mu)=i n f_{x} L(x, \mu)=i n f_{x}\left[f(x)+\sum_{i=1}^{m} \mu_{i} g_{i}(x)\right]
\]
一般情况下, \(L(x, \mu)\) 是能取到最小值的, 所以 \(F(\mu)=\inf _{x} L(x, \mu)=\min _{x} L(x, \mu)\) 求解。当强对偶性成立时, 通过KKT条件求解极值点, 然后从极值点挑出最值点。
求解。当强对偶性成立时，通过KKT条件求解极值点，然后从极值点挑出最值点。
\[\left\{\begin{array}{l}
\nabla f(x)+\sum_{i=1}^{m} \mu_{i} \nabla g_{i}(x)=0 \g_{i}(x) \leq 0, \forall i=1, \cdots, m \\mu_{i} \geq 0, \forall i=1, \cdots, m \\mu_{i} g_{i}(x)=0, \forall j=1, \cdots, m
\end{array}\right.
\]
第一个条件使得目标函数和约束函数的法向量共线（梯度共线）。
最后一个条件称为互补松弛条件(Complementary Slackness Condition)。通过引入这个条件, 增加了m个等式约束，使得等式的数量跟变量一样。
强对偶性
对偶问题其实就是将:
\[\begin{gathered}
\min _{w} \max _{\lambda} L(w, \lambda) \s . t . \quad \lambda_{i} \geq 0
\end{gathered}
\]
变成了：
\[\begin{gathered}
\max _{\lambda} \min _{w} L(w, \lambda) \s . t . \quad \lambda_{i} \geq 0
\end{gathered}
\]
类似于上面的倒数得到SVM最优化问题的表达式。
假设有个函数 \(f\) 我们有:
\[\min \max f \geq \max \min f
\]
也就是说，最大的里面挑出来的最小的也要比最小的里面挑出来的最大的要大。这关系实际上就是 弱对偶关系，而强对偶关系是当等号成立时，即:
\[\min \max f=\max \min f
\]
如果 \(f\) 是凸优化问题，强对偶性成立。
SVM优化过程
SVM优化公式：
\[\begin{aligned}
&\quad \min _{w} \frac{1}{2}\|w\|^{2} \ &\text { s.t. } \quad g_{i}(w, b)=1-y_{i} \quad\left(w^{T} x_{i}+b\right) \leq 0, \quad i=1,2, \ldots, n
\end{aligned}
\]
构造拉格朗日函数
微积分多元函数学的，忘得差不多了。。，就是用来求最大最小值的
\[\begin{aligned}
\min _{w, b} \max _{\lambda} L(w, b, \lambda)=& \frac{1}{2}\|w\|^{2}+\sum_{i=1}^{n} \lambda_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right] \& s . t . \quad \lambda_{i} \geq 0
\end{aligned}
\]
利用强对偶性转化：
利用强对偶性转化:
\[\max _{\lambda} \min _{w, b} L(w, b, \lambda)
\]
现对参数 \(\mathrm{w}\) 和 \(\mathrm{b}\) 求偏导数:
\[\begin{aligned}
&\frac{\partial L}{\partial w}=w-\sum_{i=1}^{n} \lambda_{i} x_{i} y_{i}=0 \&\frac{\partial L}{\partial b}=\sum_{i=1}^{n} \lambda_{i} y_{i}=0
\end{aligned}\begin{aligned}
&\frac{\partial L}{\partial w}=w-\sum_{i=1}^{n} \lambda_{i} x_{i} y_{i}=0 \&\frac{\partial L}{\partial b}=\sum_{i=1}^{n} \lambda_{i} y_{i}=0
\end{aligned}
\]
得到:
\[\begin{aligned}
\sum_{i=1}^{n} \lambda_{i} x_{i} y_{i} &=w \\sum_{i=1}^{n} \lambda_{i} y_{i} &=0
\end{aligned}
\]
我们将这个结果带回到函数中可得:
\[\begin{aligned}
L(w, b, \lambda) &=\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{n} \lambda_{i}-\sum_{i=1}^{n} \lambda_{i} y_{i}\left(\sum_{j=1}^{n} \lambda_{j} y_{j}\left(x_{i} \cdot x_{j}\right)+b\right) \&=\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{n} \lambda_{i}-\sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{n} \lambda_{i} y_{i} b \&=\sum_{j=1}^{n} \lambda_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)
\end{aligned}\begin{aligned}
L(w, b, \lambda) &=\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{n} \lambda_{i}-\sum_{i=1}^{n} \lambda_{i} y_{i}\left(\sum_{j=1}^{n} \lambda_{j} y_{j}\left(x_{i} \cdot x_{j}\right)+b\right) \&=\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{n} \lambda_{i}-\sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{n} \lambda_{i} y_{i} b \&=\sum_{j=1}^{n} \lambda_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)
\end{aligned}
\]
也就是说:
\[\min _{w, b} L(w, b, \lambda)=\sum_{i=1}^{n} \lambda_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)\min _{w, b} L(w, b, \lambda)=\sum_{i=1}^{n} \lambda_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)
\]
去掉了w和b变量，得到只含有一个变量的式子，如下：
\[\begin{gathered}
\max _{\lambda}\left[\sum_{i=1}^{n} \lambda_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda_{i} \lambda_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)\right] \\text { s.t. } \sum_{i=1}^{n} \lambda_{i} y_{i}=0 \quad \lambda_{i} \geq 0
\end{gathered}
\]
我们可以看出来这是一个二次规划问题，问题规模正比于训练样本数，我们常用 SMO(Sequential Minimal Optimization) 算法求解。
SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优 化一个参数, 其他参数先固定住, 仅求当前这个优化参数的极值。我们来看一下 SMO 算法在 SVM 中的应用。
我们刚说了 SMO 算法每次只优化一个参数，但我们的优化目标有约束条件: \(\sum_{i=1}^{n} \lambda_{i} y_{i}=0\),
- 选择两个需要更新的参数 \(\lambda_{i}\) 和 \(\lambda_{j}\), 固定其他参数。于是我们有以下约束:
这样约束就变成了：
\[\lambda_{i} y_{i}+\lambda_{j} y_{j}=c \quad \lambda_{i} \geq 0, \lambda_{j} \geq 0
\]
其中 \(c=-\sum_{k \neq i, j} \lambda_{k} y_{k}\), 由此可以得出 \(\lambda_{j}=\frac{c-\lambda_{i} y_{i}}{y_{j}}\), 也就是说我们可以用 \(\lambda_{i}\) 的表达 式代替 \(\lambda_{j}\) 。这样就相当于把目标问题转化成了仅有一个约束条件的最优化问题, 仅有的约束是 \(\lambda_{i} \geq 0\)
- 对于仅有一个约束条件的最优化问题，我们完全可以在 \(\lambda_{i}\) 上对优化目标求偏导, 令导数为 零, 从而求出变量值 \(\lambda_{i_{\text {new }}}\), 然后根据 \(\lambda_{i_{\text {new }}}\) 求出 \(\lambda_{j_{\text {new }}}\) 。
- 多次迭代直至收敛。
通过 \(\mathrm{SMO}\) 求得最优解 \(\lambda^{*}\) 。
求偏导数时得到：
\[w=\sum_{i=1}^{m} \lambda_{i} y_{i} x_{i}
\]
由上式可求得 \(\mathrm{w}\) 。
我们知道所有 \(\lambda_{i}>0\) 对应的点都是支持向量, 我们可以随便找个支持向量, 然后带入： \(y_{s}\left(w x_{s}+b\right)=1\), 求出 \(b\) 即可,
两边同乘 \(y_{s}\), 得 \(y_{s}^{2}\left(w x_{s}+b\right)=y_{s}\)
因为 \(y_{s}^{2}=1\), 所以: \(b=y_{s}-w x_{s}\)
为了更具鲁棒性，我们可以求得支持向量的均值:
\[b=\frac{1}{|S|} \sum_{s \in S}\left(y_{s}-w x_{s}\right)
\]
步骤 \(5: \mathrm{w}\) 和 \(\mathrm{b}\) 都求出来了，我们就能构造出最大分割超平面： \(\boldsymbol{w}^{T} x+b=0\)
分类决策函数： \(f(x)=\operatorname{sign}\left(w^{T} x+b\right)\)
其中 \(\operatorname{sign}(\cdot)\) 为阶跃函数：
\[\operatorname{sign}(x)=\left\{\begin{array}{rl}
-1 & x<0 \0 & x=0 \1 & x>0
\end{array}\right.
\]
将新样本点导入到决策函数中既可得到样本的分类。
核函数
问题
线性不可分问题：将二维线性不可分样本映射到高维空间中，让样本点在高维空间线性可分
核函数意义
这是因为低维空间映射到高维空间后维度可能会很大，如果将全部样本的点乘全部计算好，这样的 计算量太大了。
但如果我们有这样的一核函数 \(k(x, y)=(\phi(x), \phi(y)), \quad x_{i}\) 与 \(x_{j}\) 在特征空间的内积等于 它们在原始样本空间中通过函数 \(k(x, y)\) 计算的结果，我们就不需要计算高维甚至无穷维空间的 内积了。
举个例子：假设我们有一个多项式核函数:
\[k(x, y)=(x \cdot y+1)^{2}
\]
带进样本点的后：
\[k(x, y)=\left(\sum_{i=1}^{n}\left(x_{i} \cdot y_{i}\right)+1\right)^{2}
\]
而它的展开项是：
\[\sum_{i=1}^{n} x_{i}^{2} y_{i}^{2}+\sum_{i=2}^{n} \sum_{j=1}^{i-1}\left(\sqrt{2} x_{i} x_{j}\right)\left(\sqrt{2} y_{i} y_{j}\right)+\sum_{i=1} n\left(\sqrt{2} x_{i}\right)\left(\sqrt{2} y_{i}\right)+1
\]
如果没有核函数，我们则需要把向量映射成:
\[x^{\prime}=\left(x_{1}^{2}, \ldots, x_{n}^{2}, \ldots \sqrt{2} x_{1}, \ldots, \sqrt{2} x_{n}, 1\right)
\]
然后在进行内积计算, 才能与多项式核函数达到相同的效果。
常见核函数
线性核函数
\[k\left(x_{i}, x_{j}\right)=x_{i}^{T} x_{j}
\]
多项式核函数
\[k\left(x_{i}, x_{j}\right)=\left(x_{i}^{T} x_{j}\right)^{d}
\]
高斯核函数
\[k\left(x_{i}, x_{j}\right)=\exp \left(-\frac{\left\|x_{i}-x_{j}\right\|}{2 \delta^{2}}\right)
\]
总结
优点
- 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
- 能找出对任务至关重要的关键样本（即：支持向量）；
- 采用核技巧之后，可以处理非线性分类/回归任务；
- 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
缺点
- 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为
，其中 N 为训练样本的数量；
- 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 ；
- 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。
因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。
参考
[1] 【机器学习】支持向量机 SVM（非常详细） - 知乎 (zhihu.com)
[2] 支持向量机（SVM）——原理篇 - 知乎 (zhihu.com)
SVM模型
原文：https://www.cnblogs.com/dddddblog/p/svm_model.html
