支持向量机SVM
1 线性分类
先假设线性可分的情形。这里我们考虑的是一个两类的分类问题。
- 数据点：$x_1,x_2,\ldots,x_n$ 共 $n$ 个点，每个点表示为m维向量 $x=(x^{(1)},x^{(2)},\ldots,x^{(m)})^T$ ，
- 线性分类器：在 $R^m$ 中找到一个超平面（hyperplane）将数据点分为两类
- 类别：表示为 $y$，取 +1 或者 -1
$R^m$ 的超平面表示为
$$
\begin{equation} \langle w,x \rangle +b=w^Tx+b=0\end{equation}
$$
其中向量 $w=(w^{(1)},w^{(2)},\ldots,w^{(m)})^T$，$\langlew,x\rangle$ 为向量内积，$w^Tx$ 则是从矩阵角度看，且有 $w^Tw=|w|^2$ 。
回忆起高中的数学知识，二维空间中这样的超平面就是任一直线，表示为$Ax+By+C=0$。因此 $m$ 维空间中的超平面为 $w^Tx+b=w^{(1)}x^{(1)}+w^{(2)}x^{(2)}+\ldots+w^{(m)}x^{(m)}+b=0$。
分类函数定义为
$$\begin{equation}f(x)=w^Tx+b\end{equation}$$
则在超平面上的 $x$ 有 $f(x)=0$，其余则 $f(x)>0$ 或 $f(x)<0$。
线性分类器对超平面的挑选标准是令数据点和超平面间的margin越大越好，这样confidence就越高。 确定超平面后，对一个数据点 $x$ 进行分类，实际上是通过把 $x$ 带入到分类函数 $f(x)=w^Tx+b$ 算出结果然后根据其正负号来进行类别划分的。
1.1 magrin
需要考虑两种 magrin。
functional margin
$$\begin{equation}\hat{\gamma}=yf(x)=y(w^Tx+b)\end{equation}$$
从刚才 $f(x)=0$，$f(x)>0$ 和 $f(x)<=0$ 的三种情况，容易想到 $f(x)$ 的值可以衡量 $x$ 到超平面的margin。并乘上对应的类别 $y$ 值（+1或-1）来消除正负号的影响，使得functional margin $\hat{\gamma}$ 恒为正。
但是，通过等比例地缩放 $w$ 和 $b$ 的值，可使得超平面 $w^Tx+b=0$ 不变，但 $f(x)=w^Tx+b$ 的值任意大，令实际距离不变的数据点和超平面间的 functional margin $\hat{\gamma}$ 也任意大，岂不是这样就最大化 functional margin了？因此以 functional margin 作为衡量标准并不合理。
geometrical margin
$$\begin{equation}\tilde{\gamma} = \frac{yf(x)}{|w|}= \frac{\hat{\gamma}}{|w|}\end{equation}$$
证明：
对于一个点 $x$ ，令其垂直投影到超平面上的对应的点为 $x_0$，$f(x_0)=0$，$w$ 是垂直于超平面的一个向量（因为设超平面上任意两点 $x_1$ 和 $x_2$，则 $w^Tx_1+b=0$，$w^Tx_2+b=0$，两式相减得 $w^T(x_1-x_2)=0$，即 $w$ 向量和超平面互相垂直），$\tilde{\gamma}$ 为 $x$ 到超平面的几何距离，依然用 $y$ 来保持非负性。因此有
$$\tilde{\gamma}\frac{w}{|w|}=y(x-x_0)$$
整理得 $x=x_0+\frac{\tilde{\gamma}}{y}\frac{w}{|w|}$，代入 $f(x)$ 得
$$f(x)=f(x_0+\frac{\tilde{\gamma}}{y}\frac{w}{|w|})=w^T(x_0+\frac{\tilde{\gamma}}{y}\frac{w}{|w|})+b=(w^Tx_0+b)+\frac{\tilde{\gamma}}{y}\frac{w^Tw}{|w|}=\frac{\tilde{\gamma}}{y}|w|$$
即$$\tilde{\gamma}=\frac{yf(x)}{|w|}$$
高中数学又立功了！二维空间中点 $P(x_0,y_0)$ 到直线 $Ax+By+C=0$ 的距离公式为 $d=\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}$。
显然，functional margin 和 geometrical margin 相差一个 $|w|$ 的缩放因子。由于 geometrical margin 多了 $|w|$ 这个分母，所以同比例缩放 $w$ 和 $b$ 的时候，超平面不会变， 数据点和超平面间的 geometrical margin $\tilde{\gamma}=\frac{y(w^Tx+b)}{|w|}$ 的值也不会变。因此，最大化 geometrical margin 才是我们真正想要的。
那废话这么多，为什么要介绍functional margin？因为它可以简化优化问题！
1.2 优化问题
实际上，在超平面（以下开始称为分割面）两边存在着gap，它的边界是另外两个平行的超平面，为了区别，我称它俩为支持面。两个支持面到分割面的距离相等，这个距离就是所能得到的最大的 geometrical margin $\tilde{\gamma}$ ，它是gap的一半。而必然有一些点“支持”这两个支持面（否则就可以进一步地扩充 gap ，这就不是最大的 margin 了），我称这些点为支持点。点可以表示为以原点为起始点的向量，因此也叫做 support vector。
最大间隔分类器（maximum margin classifier）的目标函数可以定义为：
$$
\max\tilde{\gamma}=\max\frac{\hat{\gamma}}{|w|} \
s.t.\hat{\gamma_i}\geq \hat{\gamma},\quad i=1,2,\ldots,n\
$$
其中不等式约束 $\hat{\gamma_i}\geq \hat{\gamma}$ 来自于 $\hat{\gamma}=\min \hat{\gamma}_i $，指的是 $n$ 个数据点到分割面的 functional margin 要大于支持面到分割面的 functional margin，因为显然所有点都在支持面“身后”。
这个优化问题还可以进一步简化。前面说过，可以通过等比例地缩放 $w$ 和 $b$ 的值，使得超平面不变，而 functional margin $\hat{\gamma}$ 任意变化。因此可以为所有的 $\hat{\gamma_i}$ 挑一个基准 $w$ 和 $b$ ，刚好令 $\hat{\gamma}=\min \hat{\gamma}_i=y(w^Tx+b)=1$，问题就简化为：
$$\begin{equation}\begin{array}{*{20}{l}}
&\max \frac{1}{|w|} \\
s.t. &y_i(w^Tx_i+b)\geq 1,\quad i=1,2,\ldots,n\\
\end{array}\end{equation}$$
而求 $\max \frac{1}{|w|}$ 也就是求 $\min |w|$。其实后面会有对 $w$ 的求导，且有 $w^Tw=|w|^2$， 因此等价求 $\min \frac{1}{2}|w|^2$ 实际上为 Lagrangian 对偶做好了铺垫。
最后优化问题就简化为：
$$\begin{equation}\begin{array}{*{20}{l}}
&\min \frac{1}{2}|w|^2 \\
s.t. &y_i(w^Tx_i+b)-1\geq 0 ,\quad i=1,2,\ldots,n\\
\end{array}\end{equation}$$
因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。解完该优化问题，就可以获得最优的 $w^∗$，$b^∗$，确定分类函数 $f(x)={w^∗}^Tx+b$。
凸规划：求凸函数在凸集上的极小点。
- 凸规划的局部极小点就是全局极小点，且极小点的集合是凸集。
- 如果凸规划的目标函数是严格凸函数，又存在极小点，那么它的极小点是唯一的。
二次规划：是非线性规划中一种特殊情况，目标函数是二次实函数，约束是线性的。提供了解决二次规划问题的包的包括Excel、Matlab、R、SAS等等。
2 Lagrangian对偶
注意到目标函数的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与 primal problem（原问题）等价的 dual problem （对偶问题）得到 primal problem 的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
Lagrangian如下：
$$\begin{equation}
\mathcal{L}(w,b,\alpha)=\frac{1}{2}|w|^2-\sum_{i=1}^n\alpha_i \left(y_i(w^Tx_i+b)-1\right)
\end{equation}$$
则
$$ \begin{equation}
\min_{w,b} \max_{\alpha_i\geq 0} \mathcal{L}(w,b,\alpha)\\ \text{等价于}\min_{y_i(w^Tx_i+b)-1\geq 0} \frac{1}{2}|w|^2
\end{equation}$$
它们被称为primal problem。
证明：
对内层的优化问题 $z(w)=$
\begin{array}{*{20}{l}}
&\max \mathcal{L}(w,b,\alpha) \\
s.t. &\alpha_i\geq 0 ,\quad i=1,2,\ldots,n\\
\end{array}
可分为两种情况讨论：
- 当所有数据点都满足 $y_i(w^Tx_i+b)-1\geq 0$ 的约束时，支持点始终取到 $0$，非支持点大于 $0$，而要达到 $\mathcal{L}(w,b,\alpha)$ 的最大值，则非支持点对应的 $\alpha_i=0$，从而达到最大值，即 $\frac{1}{2}|w|^2$。
- 当存在数据点 $y_i(w^Tx_i+b)-1\leq 0$ 时，$\mathcal{L}(w,b,\alpha)$ 的最大值可通过 $\alpha_i\rightarrow+\infty$ 趋近于无穷大。
因此求 $\min_{w,b}z(w)$ 时，满足约束的第一种情况就等价于求 $\min_{y_i(w^Tx_i+b)-1\geq 0} \frac{1}{2}|w|^2$，而不满足约束的第二种情况，对无穷大求最小值，自然不会是所要的。
与之对应的是daul problem：
$$\begin{equation}\max_{\alpha_i\geq 0} \min_{w,b} \mathcal{L}(w,b,\alpha)\end{equation}$$
记 primal problem 的最小值记为 $p^∗$ ，dual problem 的最大值为 $d^∗$，则对于所有的优化问题都有weak duality性质：
$$\begin{equation}d^∗\leq p^∗\end{equation}$$
而当某些特殊条件满足时，有strong duality性质：
$$\begin{equation}d^∗= p^∗\end{equation}$$
比如 凸规划+KKT条件 或 凸规划+Slater条件。
primal problem 满足，因此 strong duality 性质成立。优化问题由 primal problem 转换为求解 daul problem $\max_{\alpha_i\geq 0} \min_{w,b} \mathcal{L}(w,b,\alpha)$。
对内层 $\min_{w,b} \mathcal{L}(w,b,\alpha)$ 的求解可通过：
$$\begin{align}
\frac{\partial \mathcal{L}}{\partial w}=0 &\Rightarrow w=\sum_{i=1}^n \alpha_i y_i x_i \\
\frac{\partial \mathcal{L}}{\partial b} = 0 &\Rightarrow \sum_{i=1}^n \alpha_i y_i = 0
\end{align}$$
代回得
$$\begin{equation}
\min_{w,b} \mathcal{L}(w,b,\alpha)=\sum_{i=1}^n \alpha_i-\frac{1}{2}\sum_{i,j=1}^n \alpha_i\alpha_j y_iy_j x_i^Tx_j
\end{equation}$$
证明：
$$\begin{array}{*{20}{lr}}
\frac{1}{2}|w|^2-\sum_{i=1}^n\alpha_i \left(y_i(w^Tx_i+b)-1\right)&\\
=\frac{1}{2}w^Tw-\sum_{i=1}^n\alpha_i \left(y_i(w^Tx_i+b)-1\right)
&(w^Tw=|w|^2)\\
=\frac{1}{2}w^T\sum_{i=1}^n \alpha_i y_i x_i-w^T\sum_{i=1}^n \alpha_i y_i x_i-\sum_{i=1}^n \alpha_i y_ib+\sum_{i=1}^n \alpha_i
&(代入w)\\
=\sum_{i=1}^n \alpha_i-\frac{1}{2}w^T\sum_{i=1}^n \alpha_i y_i x_i
&(\sum_{i=1}^n \alpha_i y_i = 0 )\\
=\sum_{i=1}^n \alpha_i-\frac{1}{2}\left(\sum_{i=1}^n \alpha_i y_i x_i\right)^T\sum_{i=1}^n \alpha_i y_i x_i
&(代入w^T)\\
=\sum_{i=1}^n \alpha_i-\frac{1}{2}\sum_{i=1}^n \alpha_i y_i x_i^T\sum_{i=1}^n \alpha_i y_i x_i
&\\
=\sum_{i=1}^n \alpha_i-\frac{1}{2}\sum_{i,j=1}^n \alpha_i\alpha_j y_iy_j x_i^Tx_j
&(\sum_i a_i\sum_j b_j=\sum_{i,j} a_ib_j)
\end{array} $$
即 $\max_{\alpha_i\geq 0} \min_{w,b} \mathcal{L}(w,b,\alpha)$ 简化为：
$$\begin{equation}\begin{array}{*{20}{l}}
&\max \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \\
s.t., &\alpha_i\geq 0, i=1,\ldots,n \\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{array}\end{equation}$$
也将 $w=\sum_{i=1}^n \alpha_i y_i x_i$ 代入分类函数中
$$\begin{equation}
f(x)= w^Tx+b=\left(\sum_{i=1}^n\alpha_i y_i x_i\right)^Tx+b
= \sum_{i=1}^n\alpha_i y_i x_i^T x + b
\end{equation}$$
最后，用向量内积形式 $\langle x_i, x\rangle$ 替换 $x_i^Tx$。
优化问题：
$$\begin{equation}\begin{array}{*{20}{l}}
&\max \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j \langle x_i, x_j\rangle \\
s.t., &\alpha_i\geq 0, i=1,\ldots,n \\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{array}\end{equation}$$
分类函数：
$$\begin{equation}
f(x)=\sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b
\end{equation}$$
转换为内积带来以下好处：
- 对于新点 $x$ 的预测，只需要计算它与训练数据点的内积即可。
- 内积可以使用 Kernel 函数进行非线性推广。
- 非支持点对应的 $\alpha_i=0$ ，则新点的内积计算实际上只要针对少量的支持点，而不是所有的训练数据点。这就体现了 “Supporting Vector”。
通过解优化问题（如 SMO 算法），得到 $\alpha_i^∗$，代入得 $w^∗=\sum_{i=1}^n \alpha_i^∗ y_i x_i$，$b^∗=-\frac{\max_{y_i=-1}{w^∗}^Tx_i+\min_{y_i=1}{w^∗}^Tx_i}{2}$。
3 非线性扩展
3.1 映射
前面介绍了线性情况下的支持向量机，它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过，由于是线性方法，所以对非线性的数据就没有办法处理了。
通过映射 $\phi(\cdot)$ 将分类函数 $f(x)=\sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b $ 向高维空间映射，可使得其线性可分：
$$\begin{equation} f(x) = \sum_{i=1}^n\alpha_i y_i \color{red}{\langle \phi(x_i), \phi(x)\rangle} + b\end{equation}$$
其中的 $\alpha_i$通过求解 dual problem 而得：
$$\begin{equation}\begin{array}{*{20}{l}}
&\max_\alpha \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\color{red}{\langle \phi(x_i),\phi(x_j)\rangle} \\
s.t., &\alpha_i\geq 0, i=1,\ldots,n \\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{array}\end{equation}$$
例1：
$R^2$ 的点表示为 $x(\eta_1,\eta_2)^T$ ，则二次曲线可以写作：
$$a_1\eta_1 + a_2\eta_1^2 + a_3 \eta_2 + a_4\eta_2^2 + a_5\eta_1 \eta_2 + a_6 = 0$$
通过坐标映射 $\phi:(\eta_1,\eta_2)^T\rightarrow(z_1,z_2,z_3,z_4,z_5)^T$ 到 $R^5$ 中，对应点 $\phi(x)$ 的 $z_1=\eta_1$，$z_2=\eta_1^2$，$z_3=\eta_2$，$z_4=\eta_2^2$，$z_5=\eta_1 \eta_2$。那么显然，上面的方程在新的坐标系下可以写作：
$$\sum_{i=1}^5a_i z_i + a_6 = 0$$
从新的坐标 $z_i$ 角度看，这是一个超平面方程。因此， $R^2$ 中需要二次曲线分割（线性不可分）的数据点在 $R^5$ 中将可用超平面分割（线性可分）。高中数学示范， $P(x,y)$ 是圆 $x^2+(y-1)^2=4$ 上的任意一点，即满足 $x^2-2y+y^2-3=0$，通过将原来的$f(x,y)$的二次函数看作 $g(x^2,y,y^2)$ 的线性函数，就可以映射到三维空间中对应的点 $P(x^2,y,y^2)$。
直接向高维映射的方法看似成功，但是问题是：
- 映射维数爆炸：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间（验算一下？），这个数目是呈爆炸性增长的，这给 $\phi(\cdot)$ 的计算带来了非常大的困难。
- 无穷维情况：无从计算。
3.2 核函数
所以就需要 Kernel 出马了。核函数能简化映射空间中的内积运算，避开了直接在高维空间中进行计算，而结果却是等价的。
用 $\kappa(x_i,x)$ 的低维核函数代替 $\langle \phi(x_i), \phi(x)\rangle$ 的高维内积运算，使得分类函数为：
$$f(x)=\sum_{i=1}^n\alpha_i y_i \color{red}{\kappa(x_i,x)} + b$$
其中的 $\alpha_i$通过求解 dual problem 而得：
$$\begin{equation}\begin{array}{*{20}{l}}
&\max_\alpha\sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\color{red}{\kappa(x_i,x_j)} \\
s.t., &\alpha_i\geq 0, i=1,\ldots,n \\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{array}\end{equation}$$
例2：
设 $R^2$ 有两点 $x_1 = (\eta_1,\eta_2)^T$ 和 $x_2=(\xi_1,\xi_2)^T$，通过例1的映射 $\phi(\cdot)$ 得到 $R^5$ 中的对应点 $\phi(x_1)(\eta_1,\eta_1^2,\eta_2,\eta_2^2,\eta_1\eta_2)^T$，$\phi(x_2)(\xi_1,\xi_1^2,\xi_2,\xi_2^2,\xi_1\xi_2)^T$，映射内积为
$$\langle \phi(x_1),\phi(x_2)\rangle = \eta_1\xi_1 + \eta_1^2\xi_1^2 + \eta_2\xi_2 + \eta_2^2\xi_2^2+\eta_1\eta_2\xi_1\xi_2$$
令核函数 $\kappa(x_1,x_2)=\left(\langle x_1, x_2\rangle + 1\right)^2$， 则
$$\kappa(x_1,x_2)= 2\eta_1\xi_1 + \eta_1^2\xi_1^2 + 2\eta_2\xi_2 + \eta_2^2\xi_2^2 + 2\eta_1\eta_2\xi_1\xi_2 + 1$$
与 $\langle \phi’(x_1),\phi’(x_2)\rangle $ 结果相等，其中$\phi’(x_1)(\sqrt{2}\eta_1,\eta_1^2,\sqrt{2}\eta_2,\eta_2^2,\sqrt{2}\eta_1\eta_2,1)$，$\phi’(x_2)(\sqrt{2}\xi_1,\xi_1^2,\sqrt{2}\xi_2,\xi_2^2,\sqrt{2}\xi_1\xi_2,1)$。显然 $\phi’(\cdot)$也就是把 $\phi(\cdot)$ 某几个维度线性缩放一下，然后再加上一个常数维度。当然，因为我们这里的例子非常简单，所以我可以手工构造出 $\phi(\cdot)$ 对应的核函数出来，如果对于任意一个映射，想要构造出对应的核函数就很困难了。
原先需要映射到高维空间中，然后再根据内积的公式进行计算；现在可以直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。这样就可以解决映射维度爆炸的问题，甚至是无穷维度的情况也没有问题。
3.3 几个核函数
通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），例如：
- 多项式核 $\kappa(x_1,x_2) = \left(\langle x_1,x_2\rangle + R\right)^d$
- 高斯核 $\kappa(x_1,x_2) = \exp\left(-\frac{|x_1-x_2|^2}{2\sigma^2}\right)$
- 线性核 $\kappa(x_1,x_2) = \langle x_1,x_2\rangle$
除了 SVM 之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。
4 异常点
SVM 允许数据点在一定程度上偏离一下超平面。
修改原来的约束条件 $y_i(w^Tx_i+b)\geq 1$ 为：
$$y_i(w^Tx_i+b)\geq 1\color{red}{-\xi_i}, \quad i=1,\ldots,n$$
其中 $\xi_i\geq0$ 称为松弛变量 (slack variable) ，对应数据点 $x_i$ 允许偏离的 functional margin 的量。当然，如果我们运行 $\xi_i\geq0$ 任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些 $\xi_i\geq0$ 的总和也要最小，即
$$\min \frac{1}{2}|w|^2\color{red}{+C\sum_{i=1}^n \xi_i}$$
其中 $C$ 是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中 $\xi_i$ 是需要优化的变量（之一），而 $C$ 是一个事先确定好的常量。
优化问题：
$$\begin{equation}\begin{array}{*{20}{l}}
&\min\frac{1}{2}|w|^2 + C\sum_{i=1}^n\xi_i \\
s.t., & y_i(w^Tx_i+b)\geq 1-\xi_i, i=1,\ldots,n \\
& \xi_i \geq 0, i=1,\ldots,n
\end{array}\end{equation}$$
Lagrangian：
$$\mathcal{L}(w,b,\xi,\alpha,r)=\frac{1}{2}|w|^2 + C\sum_{i=1}^n\xi_i – \sum_{i=1}^n\alpha_i \left(y_i(w^Tx_i+b)-1+\xi_i\right) – \sum_{i=1}^n r_i\xi_i$$
解 $\min_{w,b,\xi}\mathcal{L}(w,b,\xi,\alpha,r)$：
$$\begin{align}
\frac{\partial \mathcal{L}}{\partial w}=0 &\Rightarrow w=\sum_{i=1}^n \alpha_i y_i x_i \\
\frac{\partial \mathcal{L}}{\partial b} = 0 &\Rightarrow \sum_{i=1}^n \alpha_i y_i = 0 \\
\frac{\partial \mathcal{L}}{\partial \xi_i} = 0 &\Rightarrow C-\alpha_i-r_i=0, \quad i=1,\ldots,n
\end{align}$$
注意到 $C−\alpha_i−r_i=0$ ，又有 $r_i\geq 0$ （作为 Lagrange multiplier 的条件），因此有 $\alpha_i\leq C$ 。
代回依然得
$$\begin{equation}
\min_{w,b,\xi}\mathcal{L}(w,b,\xi,\alpha,r)=\sum_{i=1}^n \alpha_i-\frac{1}{2}\sum_{i,j=1}^n \alpha_i\alpha_j y_iy_j \langle x_i,x_j\rangle
\end{equation}$$
即 $\max_{\alpha_i\geq 0,r_i\geq 0} \min_{w,b,\xi}\mathcal{L}(w,b,\xi,\alpha,r)$ 简化为：
$$\begin{equation}\begin{array}{*{20}{l}}
&\max \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle\\
s.t., & 0 \leq \alpha_i \color{red}{\leq C}, i=1,\ldots,n\\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{array}\end{equation}$$
可见，目标函数不变，只有 $\alpha_i$ 多了一个上限 $C$。而 Kernel 化的非线性形式也是一样的，只要把 $\langle x_i,x_j \rangle$ 换成 $\kappa(x_i,x_j)$ 即可。这样一来，一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。
