支持向量机

支持向量机(svm)是一种用于分类的算法，它的思想是找出一条平面最大间隔的将数据集分开。它可以分为硬间隔分类和软间隔分类。

1.硬间隔分类器
给定数据集 $\{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\}$ ,要找出一条平面 $y=w^Tx+b$ 最大间隔的分割数据集的优化函数可以表示为
$\max \min dist(w^T,b)$
$s.t \quad y_i(w^Tx_i+b)>0; i=1,2,...n$
$dist(w^T,b)$ 表示数据上的数据到平面的距离,意思表示为从n个样本点中找到，离平面最近的那个点的距离，使这个距离最大化，同时使样本点分类正确。根据点到平面的距离公式， $dist(w^T,b)$ 可以表示为
$dist(w^T,b)=\frac{|w^Tx+b|}{||w||}$
优化函数可以替换为：
$\max \limits_{w,b} \min \limits_{x_i,i=1,2,3...} \frac{|w^Tx_i+b|}{||w||}$
可以优化为：
$\max \limits_{w,b} \frac{1}{||w||} \min \limits_{x_i,i=1,2,3...}y_i(w^Tx_i+b)$
假设 $\min \limits_{x_i,i=1,2,3...}y_i(w^Tx_i+b)$ 存在最小值 $\gamma$ ,由于w,b作为超平面的系数，可以缩放，有无数个，可以直接令 $\gamma$ =1，是不会影响分类效果，方便优化计算，最终的优化函数化简为：
$\min \limits_{w,b} \frac{1}{2}||w||$
$s.t \quad y_i(w^Tx_i+b)>=1; i=1,2,...n$

2.拉格朗日函数
上面带约束的优化函数可以用拉格朗日乘子法构造拉格朗日函数(Lagrange function)再通过求解其对偶问题(dual problem)得到原始问题的最优解。拉格朗日函数为
$L(w,b,\alpha)=\frac{1}{2}||w|| + \sum_{i=1}^n\alpha_i(1-y_i(w^Tx_i+b)$
原问题可以表示为
$\begin{cases} \min \limits_{w,b} \max \limits_{\alpha} L(w,b,\alpha)\\ s.t \quad \alpha_i>=0 \end{cases}$
对偶问题可以表示为
$\begin{cases} \max \limits_{\alpha} \min \limits_{w,b} L(w,b,\alpha)\\ s.t \quad \alpha_i>=0 \end{cases}$
在svm 中原问题和对偶问题同解，所以可以直接通过求解对偶问题。
对w,b求偏导
$\begin{cases} \frac{\partial L}{\partial w}= w-\sum_{i=1}^n\alpha_iy_ix_i=0 \\ \frac{\partial L}{\partial b}=\sum_{i=1}^n\alpha_iy_i=0 \end{cases}$
得出
$w=\sum_{i=1}^n\alpha_iy_ix_i=0$
将其带入到L中得到关于 $\alpha$ 的优化函数
$L(\alpha)=\sum_{i=1}^n\alpha_i -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t \quad \alpha_i>=0 \quad \sum_{i=1}^n\alpha_iy_i=0$

关于b的求解可以通过kkt条件，
$\begin{cases} \alpha_i>=0 \\ \alpha_i(1-y_i(w^Tx_i+b))=0\\ 1-y_i(w^Tx_i+b)<=0 \end{cases}$
$\alpha>0$ 的点为支持向量找出这些点如 $(x_k,y_k)$ ，有kkt条件可以计算出:
$b=y_k-\sum_{i=1}^n\alpha_iy_ix_ix_k$

3.软间隔分类器
软间隔的svm 分类器的思想是允许分类有一些错误，在原来的优化函数上加一个惩罚项。在硬间隔分类器上是严格要求 $y_i(w^Tx_i+b)>=1$ ,现在允许少数点可以划分错误。表达式为
$\max(0,1-y_i(w^Tx_i+b))$
加入到原来的优化函数中
$\frac{1}{2}||w|| + C\sum_{i=1}^n\max(0,1-y_i(w^Tx_i+b))$
C>0为惩罚系数，可以将上式优化为
$\frac{1}{2}||w|| + C\sum_{i=1}^n\xi_i$
$s.t. \quad y_i(w^Tx_i+b)>=1-\xi_i \\ \xi_i>=0$
与硬间隔类似，我们可以通过拉格朗日乘子法将其转换为对偶问题进行求解
$L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||+C\sum_{i=1}^n\xi_i+\sum_{i=1}^n\alpha_i(1-\xi_i-y_i(w^Tx_i+b)-\sum_{i=1}^n\beta_i\xi_i$
先最小化 $\min \limits_{w,b,\xi}$ ,分别对w,b, $\xi$ 求导
$\begin{cases} \frac{\partial L}{\partial w}= w-\sum_{i=1}^n\alpha_iy_ix_i=0 \\ \frac{\partial L}{\partial b}=\sum_{i=1}^n\alpha_iy_i=0\\ \frac{\partial L}{\partial \xi}=C-\alpha_i-\beta_i=0 \end{cases}$
最后得到的优化函数和硬间分类器是一样的，只是 $\alpha$ 的限制不一样
$L(\alpha)=\sum_{i=1}^n\alpha_i -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t \quad 0<= \alpha_i<=C ,\quad \sum_{i=1}^n\alpha_iy_i=0$
软间隔分类的kkt条件
$\begin{cases} \alpha_i>=0，\beta_i>=0 \\ \alpha_i(1-y_i(w^Tx_i+b))=0\\ 1-y_i(w^Tx_i+b)<=0\\ \beta_i\xi_i=0 \end{cases}$
参数b也可以通过kkt条件求解

SMO算法
前面都是关于如何计算w,b，SMO（Sequential Minimal Optimization，序列最小优化)是用来求解 $\alpha$ ,它的基本思想是将原问题求解 (α1,α2,...,αN) 这 N 个参数的问题分解成多个子二次规划的问题分别求解，每个子问题只需要求解其中的 2 个参数，每次通过启发式选择两个变量进行优化，不断循环，直到达到函数的最优值。之前关于 $\alpha$ 的优化函数如下：
$L(\alpha)=\sum_{i=1}^n\alpha_i -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t \quad 0<= \alpha_i<=C ,\quad \sum_{i=1}^n\alpha_iy_i=0$
假设选择两个变量 $\alpha_1,\alpha_2$ ,其他变量 $\alpha_i(i=3,4....N)$ 是固定的，原来的式子可以化简为只包含 $\alpha1,\alpha2$ 的式子
$\min \limits_{\alpha_1,\alpha_2} w(\alpha_1,\alpha_2)=\frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22}\alpha_2^2+ \\ y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha1-\alpha2) +y_1\alpha_1\sum_{i=3}^ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^ny_i\alpha_iK_{i2}$
$s.t \quad \alpha_1y1+\alpha_2y2=-\sum_{i=1}^ny_i\alpha_i=\xi \\ 0 \leq \alpha_i \leq C$
通过求导得到关于 $\alpha$ 的最优解为：
$\begin{cases} \alpha_2^{new,unc}=\alpha_2^{old} + \frac{y_2(E_1-E_2)}{\eta}\\ \eta=K_{11}+K_{22}-2K{1,2}\\ \end{cases}$
由于 $\alpha_2$ 是受条件约束的，约束条件如下当y1不等于y2时
$\begin{cases} L\leq\alpha_2\leq H\\ L=\max(0,\alpha_2^{old}-\alpha_1^{old})\\ H = \min(C,C+\alpha_2^{old}-\alpha_1^{old}) \end{cases}$
当y1=y2时
$\begin{cases} L\leq\alpha_2\leq H\\ L=\max(0,\alpha_2^{old}+\alpha_1^{old})\\ H = \min(C,C+\alpha_2^{old}+\alpha_1^{old}) \end{cases}$
最后可得
$\alpha_2^{new}=\begin{cases} H ; \alpha_2>H\\ alpha_2^{new,unc} ; L \leq \alpha_2 \leq H\\ L; \alpha_2<L \end{cases}$
$\alpha_1^{new}=\alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})$
关于阈值b和插值E的更新
每次更新完 $\alpha_1,\alpha_2$ 以后， $b^{new}$ 的更新公式为
$b_1^{new}=-E_1-y1K_{11}(\alpha_1^{new}-\alpha_1^{old})-y2K_{21}(\alpha_2^{new}-\alpha_2^{old})+b_1^{old}$
$b_2^{new}=-E_2-y1K_{12}(\alpha_2^{new}-\alpha_2^{old})-y2K_{22}(\alpha_2^{new}-\alpha_2^{old})+b_2^{old}$
$E_i$ 的更新公式如下
$E_i^{new}=\sum_{j=1}^n\alpha_jy_jK_{ij}+b^{new}-y_i$