线性可分支持向量机（Linear Support Vector Machine）
线性可分和超平面
二分类问题
二分类问题就是：给定的各个样本数据分别属于两个类之一，而目标是确定新数据点将归属到哪个类中。
特征的向量空间模型
样本在被机器学习算法处理时，由其特征来表示。进行机器学习训练或预测时，样本需要转化为特征向量。
假设样本的特征向量为 n 维，这些样本的特征向量就处在 n 维的特征空间中。
线性可分
选取特征的目的：将一个事物的某些属性数字化，再映射为特征空间中的点，其目的当然是为了对其进行计算。
图中的红蓝两色点都是样本的特征向量，蓝色点对应的是正类，红色点对应的是负类：
这两类样本在其特征空间里线性可分。
线性可分严格的数学定义：
$D_0$ 和 $D_1$ 是 $n$ 维欧氏空间中的两个点集（点的集合）。
如果存在 $n$ 维向量 $w$ 和实数 $b$，使得所有属于 $D_0$ 的点 $x_i$ 都有 $wx_i + b > 0$，而对于所有属于 $D_1$ 的点 $x_j$ 则有 $wx_j + b < 0$。
则称 $D_0$ 和 $ D_1$ 线性可分。
超平面
将 $D_0$ 和 $D_1$ 完全正确地划分开的 $wx + b = 0 $ ，就是超平面（Hyperplane）。
超平面：n 维欧氏空间中维度等于 n-1 的线性子空间。
1维欧氏空间（直线）中的超平面为0维（点），
2维欧氏空间中的超平面为1维（直线）；
3维欧氏空间中的超平面为2维（平面）；
以此类推……
在数学意义上，将线性可分的样本用超平面分隔开的分类模型，叫做线性分类模型，或线性分类器。
最大间隔超平面:
- 两类样本分别分隔在该超平面的两侧；
- 两侧距离超平面最近的样本点到超平面的距离被最大化了。
找到最大间隔超平面
线性可分支持向量机就是：以找出线性可分的样本在特征空间中的最大间隔超平面为学习目的的分类模型。
二维坐标系里，两个辅助超平面（蓝、红两条直线）：
这两个超平面互相平行，它们范围内的区域称为间隔，最大间隔超平面位于这两个辅助超平面正中的位置与它们平行的超平面-图中绿线为最大间隔超平面。
用我们初中时就熟悉的表示方法来表示这两条直线，则：
蓝线：$x_2 = sx_1 + t_1 => sx_1 – x_2 + t_1 = 0$ (1)
红线：$x_2 = sx_1 + t_2 => sx_1 – x_2 + t_2 = 0$ (2)
设 $d = t_1 – t_2$，位于（1）和（2）正中的绿线（所求最大分割超平面）则表示为：
$ x_2 = sx_1 + t_1 – \frac{d}{2}=>sx_1 – x_2 + t_1 - \frac{d}{2} = 0 $ (3)
将 $ t_2 = t_1 -d$ 带入（2），然后将（1）两侧同时减去 $\frac{d}{2}$，
（2）两侧同时加上 $\frac{d}{2}$，则有:
$sx_1 – x_2 + (t_1 - \frac{d}{2}) = -\frac{d}{2}$ (1’)
$sx_1 – x_2 + (t_1 - \frac{d}{2}) = \frac{d}{2}$ (2’)
将（1'），（2'）和（3）两侧同时除以 $ -\frac{d}{2}$，则有：
$-\frac{2s}{d}x_1 + \frac{2}{d}x_2 + (1-\frac{2t_1}{d}) = 1$ (1’’)
$-\frac{2s}{d}x_1 + \frac{2}{d}x_2 + (1-\frac{2t_1}{d}) = -1$ (2’’)
$-\frac{2s}{d}x_1 + \frac{2}{d}x_2 + (1-\frac{2t_1}{d}) = 0$ (3’’)
设 $x = (x_1, x_2)，w = (\frac{-2s}{d}, \frac{2}{d})，b = 1-\frac{2t_1}{d}$，
则这三个超平面可以分别表示为：
蓝线： $wx + b = 1$
红线：$wx + b = -1$
绿线（最大分割超平面）：$wx + b = 0$
定义
用来训练线性可分支持向量机（Support Vector Machine，SVM）的样本记作：
$T = {(x_1, y_1), (x_2, y_2), … , (x_m, y_m) }$
其中，$x_i$ 为 $n$ 维实向量，而 $y_i$ 的取值要么是1，要么是-1，$i=1,2,…, m$，$y_i$ 为 $ x_i$ 的标签，当 $y_i = 1$ 时， $x_i $ 为正例；当 $y_i = -1$ 时， $x_i$ 为负例。
我们要找到将上面 $m$ 个样本完整正确地分隔为正负两类的最大间隔超平面 $w·x + b = 0$。
这个超平面由其法向量 $w$ 和截距 $b$ 确定，可用 $（w,b）$ 表示。
这 $m$ 个样本在特征空间是线性可分的，因此可以找到两个将正负两类样本分离到距离尽可能大的超平面，它们分别是：
$w·x + b = 1$ （超平面1）
和
$w·x + b = -1$ （超平面2）
通过几何不难得到这两个超平面之间的距离是 $\frac{2}{||w||}$，因此要使两平面间的距离最大，我们需要最小化 $||w||$。
详细分析一下
设 $w = (k, -1)，b_1 = b + 1，b_2 = b -1$，
则超平面1又可以表示为：$x_2 = kx_1 + b1$；
超平面2则为：$x_2 = kx_1 + b_2$。
设超平面1和超平面2之间的距离为 $l$， 见下图
因为有：$\frac{e}{l} = k$
则有：
$\frac{\sqrt{(d^2 – l^2)}}{l} = k$
$\frac{(d^2 – l^2)}{l^2} = k^2$
$\frac{(b_1-b_2)^2}{l^2} – 1 = k^2$
因为 $b_1 -b_2 = 2$，所以：
$\frac{4}{l^2} = k^2 + 1$
$l = \frac{2}{\sqrt{(k^2 + 1)}}$
又因为 $w = (k, -1) => ||w|| = \sqrt{( k^2 + (-1)^2)} = \sqrt{(k^2 + 1)}$
所以：
$l = \frac{2}{||w||}$
学习目标
依据定义，我们知道样本数据需满足下列两个条件之一：
若 $y_i = 1$，则 $wx_i + b \ge 1$
若 $y_i = -1$，则 $wx_i + b \le -1$
也就是说没有样本点处在超平面1和超平面2中间，且所有点都在正确的那一侧。
将上面两个式子合并一下就是 $y_i(wx_i + b) \ge 1$。
也就是说，我们要最小化 $||w||$ 是有约束条件的，条件就是：
$y_i(wx_i + b) \ge 1， i=1，2，…, m$
因此，求最大分割超平面问题其实是一个约束条件下的最优化问题，我们要的是：
$min(||w||)$
$s.t. \ \ y_i(wx_i + b) \ge 1，\ \ i=1，2，…, m$
为了后面好算，我们用 $\frac{(||w||^2)}{2}$ 来代替 $||w||$，并将约束条件变一下形式：
$min(\frac{||w||^2}{2})$
$s.t. \ \ 1- y_i(wx_i + b) \le 0， \ \ i=1，2，…, m$
这就是支持向量机的学习目标，其中 $min(\frac{||w||^2}{2})$ 是目标函数，我们要对它进行最优化。
对这样一个最优化问题，需要通过优化算法来求解。梯度下降是优化没有约束条件问题的算法。
此处我们遇到的，是一个有约束条件的最优化问题。
拉格朗日乘子法
拉格朗日乘子法，是一种多元函数在变量受到条件约束时，求极值的方法。
可视化函数及其约束条件
（被约束的）函数
先可视化一个二元函数 $f(x,y)$。
$z = f(x,y)$ 。涉及3个变量：$x$，$y$ 和 $z$。
在三维直角坐标系中将 $f(x,y)$ 画出来会是一个三维空间的曲面
这样一个函数实际上表达了 $x，y，z$ 三者之间的关系。
下面几幅图，分别对应不同的 $f(x,y)$：
（函数的）约束条件
函数 $f(x,y)$ 的约束条件为：$g(x,y) = 0$。
$g(x,y) = 0$ 又可以写成：$y = h(x)$ 的形式--它所表达的是 $x$ 与 $y$ 两者之间的相互关系
$y = h(x)$，如果在二维直角坐标中作图，形状应该是一条曲线。
注意：直线也属于广义的曲线；平面也属于曲面。我们说的曲线是包括直线的，曲面则包括平面。
约束条件对函数的约束
- 建立一个$xyz$三维直角坐标系。
- $f(x,y)$ 对应图形是三维坐标系里面的一个曲面。
- 在 $z = 0$ 的平面上，把 $y=h(x)$ 的图形（一条曲线）画出来。
- 将第 3 步做出的那条曲线沿着平行 z 轴的方向平移，它平移过的轨迹也形成了一个曲面，这个曲面和 $z = f(x,y)$ 形成的曲面会相交，交叠的部分是一条三维空间中的曲线。
- 第 4 步形成的曲线，其实就是 $g(x,y) = 0$ 在 $z=0$ 平面上形成的曲线，在 $z=f(x,y)$ 形成的曲面上的投影。
一个例子
可以看到 $f(x,y)$ 是存在极大值的，同时因为约束条件是 $g(x,y) = 0$，所以，如果我们要取如下目标的话：
$max f(x,y)$
$s.t. \ \ g(x,y) = 0$
对应点一定位于 $g(x,y) = 0$ 投影到 $f(x,y)$ 上之后形成的那条曲线上，比如上图中的点 B。
它不一定是 $z=f(x,y)$ 的极大值(A点)，但却是符合约束条件 $g(x,y) = 0$ 的极大值
目标函数
回到线性可分 SVM 的目标函数：
$min\frac{||w||^2}{2}$
$s.t.\ \ 1- y_i(w·x_i + b) \leqslant 0， i=1，2，…, m$
其中的自变量为 $w$ 和 $b$，也是一个二元函数（$x_i$ 和 $y_i$ 都是样本值，已知数值，$\frac{||w||^2}{2}$ 虽然只包含 $w$，但我们可以想象它也是一个二元函数，只不过变量 $b$ 的系数为0）。
所以，我们可以再抽象一步，将其概括为：
$min f(x,y)$
$s.t. g(x,y) \leqslant 0$
这个约束条件其实可以写作：
$ s.t.\ \ g(x,y) = 0 \ \ OR \ \ g(x,y) < 0$
因为不等式约束条件难度稍大，我们先从等式约束条件开始。
等式约束条件
假设，我们的目标函数是：
$min f(x,y)$
$s.t. g(x,y) = 0$
在图中作出 $f(x,y)$ 和 $g(x,y)$ 的等高线（三维图形投影到二维平面后的结果），形如下图：
绿线是 $g(x,y)$ 的等高线，因为约束条件是 $g(x,y) = 0$，因此，只有一条 $g(x,y)$ 的等高线--$g(x,y) = 0$ 对我们有意义，因此只画它即可。
蓝线是 $f(x,y)$ 的等高线。图中两条蓝线具体对应的函数分别是 $f(x,y) = d_1$ 和 $f(x,y) = d_2$。
$d_1$ 和 $d_2$ 是两个常数，对应上图中两个蓝圈对应的 $z$ 轴坐标。此处，$d_2 < d_1$。
图中绿线与蓝线相切点，映射到 $f(x,y)$ 上，就是取得 $f(x,y)$ 符合 $g(x,y) = 0$ 的约束的极小值的点。
设相切点的自变量值为 $(x^* , y^* )$。
函数的梯度：表示该函数在某点处的方向导数，方向导数是某个多维函数上的点沿每个维度分别求导后，再组合而成的向量。
记作：
$\nabla_ {x,y} f = (\frac{\partial{f}}{\partial{x}}, \frac{\partial{f}}{\partial{y}})$，
$ \nabla_ {x,y} g = (\frac{\partial{g}}{\partial{x}}, \frac{\partial{g}}{\partial{y}})$
一个函数的梯度与它的等高线垂直。
为什么梯度的方向与等高线切线方向垂直？
因此，在相切点处，$f(x^* ,y^* )$ 的梯度与 $f(x,y) = d_2$ 在 $(x^* ，y^* )$ 处的切线垂直，$g(x^* ,y^* )$ 的梯度与 $g(x,y) = 0$ 在 $(x^* ，y^* )$ 处的切线垂直。
又因为 $f(x,y) = d_2$ 对应的蓝线与 $g(x,y) = 0$ 对应的绿线在 $(x^* ， y^* ) $ 处是相切的。
注意：为什么相切？反过来想，如果它们不相切会怎样？
要么不相交，这样的话 $g(x,y)= 0$ 就没法约束 $f(x,y)$了；
要么有两个交点，如果这样，我们可以再做另一条 $f(x,y)$ 的等高线，让新等高线和 $g(x,y) =0$ 相切，再取那个切点为 $(x^* , y^* )$。如此一来，它们还是在 $(x^* , y^* ) $ 处相切。
在 $(x^* , y^* )$ 点处 $f(x,y)$ 与 $g(x,y)$ 的梯度，要么方向相同，要么方向相反。
所以，一定存在 $\lambda \ne 0$， 使得：
$\nabla_ {x,y}f(x^* ,y^* ) + \lambda \nabla_ {x,y}g(x^* ,y^* ) = 0$
这时我们将 $\lambda$ 称为拉格朗日乘子
拉格朗日乘子和拉格朗日函数
定义拉格朗日函数：$L(x,y,\lambda) = f(x,y) + \lambda g(x,y)$ -- 其中 $\lambda$ 是拉格朗日乘子。
拉格朗日函数把原本的目标函数和其限制条件整合成了一个函数。
拉格朗日函数对 $x，y$ 求偏导：
$L'_ {x,y}(x,y,\lambda) =f'_ {x,y}(x,y) + \lambda g'_ {x,y}(x,y)$
我们令拉格朗日函数对 $x，y$ 求偏导的结果为 $0$，则有：
$f'_ {x,y}(x,y) + \lambda g'_ {x,y}(x,y) = 0$
刚才已经知道了，$f(x,y)$ 符合 $g(x,y) = 0$ 约束的极小值的点 $(x^* ,y^* )$ 满足：$\nabla_ {x,y}f(x^* ,y^* ) + \lambda \nabla_ {x,y}g(x^* ,y^* ) = 0$，用导函数表示就是：$f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0$。
也就是说我们要求的极小值点正好满足拉格朗日函数对 $x、y$ 求导后，令其结果为 0 形成的导函数。
既然如此，我们当然也就是可以直接引入一个新的变量：$\lambda$ - 拉格朗日乘子，和目标函数、约束条件一起，先构造出拉格朗日函数 $L(x,y, \lambda)$。
然后再令 $L'_ {x,y}(x,y,\lambda) = 0$，之后通过最优化 $L'_ {x,y}(x,y,\lambda) = 0$，求取 $(x^* ,y^* )$ 的值。
另外，而令拉格朗日函数对 $\lambda$ 求偏导的结果为 $0$：$L'_ \lambda(x,y,\lambda) = 0$，就得到了约束条件：$g(x, y) = 0$。
拉格朗日函数也可以通过求导变化成约束条件本身。
于是，原本有约束的优化问题，就可以转化为对拉格朗日函数的无约束优化问题了。
不等式约束条件
了解了约束条件是等式的情况，我们再来看约束条件是不等式的情况。
当条件是：$g(x,y) \leqslant 0 $ 时, 我们可以它拆分成：$g(x,y) = 0 \ \ OR \ \ g(x,y) < 0$，两种情况来看。
这两种情况下可以先各取一个极小值，再比较一下，哪个更小就用哪个。
拆分后的严格不等式约束条件：$g(x,y) < 0 $
而对于 $g(x,y) < 0$ 情况，因为 $< 0$ 是一个区间，而不再是对应到三维坐标中的某个固定的曲面。
这种情况下，如果 $f(x,y)$ 的极小值就在这个区间里，然后直接对 $f(x,y)$ 求无约束的极小值就好了。
对应到拉格朗日函数就是：令 $\lambda = 0$，直接通过令 $f(x,y) $ 的梯度为 $0$ 求 $f(x,y)$ 的极小值。
求出极小值 $f(x^* ,y^* )$ 之后，再判断 $(x^* ,y^* )$ 是否符合约束条件。
拆分后的等式约束条件：$g(x,y) = 0$
$g(x,y) = 0$ 可以参照上一小节的做法。
有一点要注意，在仅有等式约束条件时，我们设 $f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0$，只要常数 $\lambda \ne 0$ 就可以了。
但是在以从 $g(x,y) \leqslant 0$ 中拆分出来的等式为约束条件时，我们要求：存在常数 $\lambda > 0$, 使得 $f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0$。
这是为什么呢？我们先来可视化地看看下面不等式约束的两种情况：
图中黑点表示最终满足约束条件的函数极小值。
如果是图左侧的状况，限制条件就又变成了 $g(x,y) <0$，且直接求 $f(x,y)$ 极小值就行。
只有是右侧情况时，不等式约束条件才又变成了等式。这种情况，才是我们在拆分了不等式条件后有意义的情况。
在这种情况下，最终找到的符合约束条件的极小值 $f(x^* ,y^* )$ 肯定不是 $f(x,y)$ 的极小值。
函数梯度的物理意义：实际上，一个函数在某一点的梯度方向（向量方向）指明了该函数的函数值相对于当前函数值增量的方向。
也就是说：我们在 $g(x^* ,y^* )$ 的梯度方向上前进一个长度：$\epsilon$（$\epsilon$ 很小很小），到达点 $(x^{** }, y^{** })$，则 $g(x^{** }，y^{** }) > g(x^* ,y^* )$。
注意：此处可以用 $z = x + y$ 和 $z = -x -y$ 来直观感受一下。二维平面（比如 $z = 0$ 平面）上的 $y=x$ 是这两个函数共同的等高线投影，不过 $z=x+y$ 的导数方向为 $(1,1)$，而 $z=-x-y$ 的导数方向为 $(-1,-1)$，两个导向量共线，但方向相反，正好分别指向各自上升的区域。
因为 $g(x^* ,y^* )= 0$，又根据梯度的物理意义，则 $(x^* ,y^* )$ 点处 $g(\cdot)$ 函数的梯度方向指向的是 $g(x, y) > 0$ 的区域。
偏偏我们的约束条件是 $g(x，y) <0$，那说明不等式约束条件所对应的区域与 $(x^* ,y^* )$ 点处 $g(\cdot)$ 函数的梯度方向是相反的。
我们现在考虑的是图4右侧的情况，此时 $f(\cdot)$ 函数带约束条件的极小值点 $(x^* , y^* )$ 就位于 $g(x, y) = 0$ 对应的曲线上。
而 $(x^* ,y^* )$ 点处 $f(\cdot)$ 函数的梯度方向正是 $f(\cdot)$ 函数本身的增量方向，因此在 $g(x,y) <0$ 所在的区域对应的应该是 $f(x, y)$ 的递增方向，如若不然，就应该是图左侧的情况了
只有当 $f(x,y)$ 梯度方向和 $g(x,y) <0$ 区域所在方向相同，也就是和 $(x^* ,y^* ) $ 点处 $g(\cdot)$ 函数梯度方向相反，那么 $f(x,y)$ 的约束条件极小值才会出现在 $g(x,y)=0$ 的曲线上。
所以，在这种情况下，存在常数 $\lambda > 0$，使得 $f'_ {x,y}(x^* ,y^* ) = - \lambda g'_ {x,y}(x^* ,y^* )$，进一步导出：
$f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0，\ \ \lambda > 0$
KKT 约束条件
我们将上面拆分开的严格不等式和等式两种情况再整合起来:
- 如果严格不等式成立时得到 $f(\cdot)$ 函数的极小值，则有 $\lambda=0$，这样才能将拉格朗日函数直接转换为原始函数。则有 $\lambda g(x,y) = 0$。
- 如果等式成立时得到 $f(\cdot)$ 函数的约束条件极小值，则必然存在 $\lambda > 0$，且同时 $g(x,y) = 0$, 因此也有 $\lambda g(x,y) = 0$。
于是，对于不等式约束条件 $g(x,y) \leqslant 0$，最终的约束条件变成了：
$g(x,y) \leqslant 0$;
$\lambda \geqslant 0$;
$\lambda g(x,y) = 0$
这样由1变3的约束条件，叫做 KKT 约束条件。
目标函数转化为拉格朗日函数
KKT 条件不是单独成立的，它是拉格朗日乘子法的一部分
当我们在约束条件下求解函数最优化问题，且约束条件为不等式时（问题描述如下）：
$Optimize\ \ f(x,y)$
$s.t. \ \ g(x,y) \leqslant 0$
我们针对目标函数生成拉格朗日函数为：
$L(x,y,\lambda) = f(x,y) + \lambda g(x,y)$
同时有 KKT 条件：
$g(x,y) \leqslant 0$
$\lambda \geqslant 0$
$\lambda g(x,y) = 0$
假设最优化结果对应点为 $(x^* , y^* )$，则当目标函数为：
$min f(x,y)$
$s.t. \ \ g(x,y) \leqslant 0$
时，若存在 $\lambda \ne 0 $，使得 $f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0$，则 $\lambda > 0$。
而当目标函数为：
$max f(x,y)$
$s.t. \ \ g(x,y) \leqslant 0$
时，若存在 $\lambda \ne 0 $，使得 $f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0$，则 $\lambda < 0$。
或者写作：此时，若存在 $\lambda \ne 0 $，使得 $f'_ {x,y}(x^* ,y^* ) - \lambda g'_ {x,y}(x^* ,y^* ) = 0$，则$\lambda > 0$。
注意：上面几个式子要注意：
- $L(x,y,\lambda) = f(x,y) + \lambda g(x,y)$ 是拉格朗日函数的定义；
- $\lambda \geqslant 0$ 是之前我们推导出来的 KKT 条件；
- 存在常数 $\lambda > 0$, 使得 $f'_ {x,y}(x^* ,y^* ) + \lambda g'_ {x,y}(x^* ,y^* ) = 0$ 或者 $f'_ {x,y}(x^* ,y^* ) - \lambda g'_ {x,y}(x^* ,y^* ) = 0$ 是推导 KKT 条件过程中经历的一个步骤 - 这个步骤中涉及到的是在 $(x^* ,y^* )$ 这个确定点处 $f$ 函数和 $g$ 函数的梯度。
