支持向量机问题

原理

1. 支持向量机使用的是什么类型的间隔？为什么？

   1. 使用几何间隔定义。
   2. 因为函数间隔只需要成比例的改变w和b，函数间隔就会发生变化，而实际分类超平面并未变化。
   3. 对超平面的w和b加上规范化约束，除以w的L2范数，可以使得间隔是确定的。
   4. 最后通过几何间隔和函数间隔之间的关系转化最优化问题。

2. 为什么需要间隔最大化？

   对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开，对未知新实例有很好的分类预测能力。

3. 简要描述一下支持向量机的原理

   1. 支持向量机学习的结果是在高维空间中划分出一条分类超平面（同时也是判别函数），得到一个约束最优化问题，求解以得到分类超平面的各个参数；
   2. 通过非线性变换将问题转化为线性问题，使用的是高斯核函数/径向基核函数；
   3. 求解参数使用序列最小优化算法；
   4. 其中，线性分类中y=wx+b，w是行向量，x是列向量，b是一个数；
   5. 支持向量机的损失函数是：合页损失函数；
   6. 支持向量机有三宝，间隔（几何间隔转为函数间隔），对偶（拉格朗日对偶），核技巧。

4. 简要描述一下核函数原理

   核函数应用在支持向量机需要由线性空间推广到非线性空间的场景。

   支持向量机通过非线性变换$φ(x)$，将输入空间映射到高维特征空间，由此将输入空间中的超曲面模型对应特征空间（希尔伯特空间）中的超平面模型，从而求解特征空间中的线性支持向量机完成输入空间分类问题的学习。

   如果支持向量机的求解只用到内积运算，而在低维输入空间又存在某个内积函数$K(x_1, x_2)$ ，它恰好等于在高维空间中这个内积，即$K(x_1,x_2)=φ(x_1)⋅φ(x_2)$。那么支持向量机就不用计算复杂的非线性变换，而由这个函数$K(x_1, x_2)$直接得到非线性变换的内积。

   该内积函数$K(x_1, x_2)$称为核函数，变换过程称为核技巧。

5. 简要描述一下序列最小优化算法：

   1. 序列最小优化算法是一种启发式算法。如果所有的变量都满足最优化问题的KKT条件，那么最优化问题的解就得到了。（KKT条件是最优化问题的充要条件）
   2. 先固定N-2个变量，迭代2个变量，重复直到收敛；外层选择违反KKT条件程度最大的点，内层循环使另一个变量产生足够大的差异（具体实现上是选择差值最大$|E_2-E_1|$的变量；选择边界变量；随机选择变量），最后更新阈值和差值。

6. 简要描述一下最小二乘法算法

   1. 最小二乘法将所有训练点视为支持向量，因为$\alpha_i=\gamma e_i \neq 0$；
   2. 利用等式约束代替不等式约束；
   3. 求解线性方程组代替求解非线性方程组，简化计算；
   4. 求解矩阵方程，得到变量的值；

7. 参数

   高斯径向基核函数公式为 $$ K(x_1,x_2)=exp{-\frac{\Vert x_1-x_2\Vert^2}{\sigma}} $$ 径向基核的参数$\sigma$，取值影响着分类超平面的复杂程度：

   参数越小，深远，过拟合；

   参数越大，浅近，欠拟合。

   惩罚因子C的取值综合了经验与结构风险：

   参数越大，扭曲，过拟合；

   参数越小，平滑，欠拟合。

实现思路

1. 计算核函数矩阵第i列的值

   输入：训练集train，核函数选项kernelOption（列表，包括核函数类型和参数）

   算法：

   1. $K(x_i,x_j)=exp{-\frac{\Vert x_i-x_j\Vert^2}{2\sigma^2}}$，其中$x_i,x_j$是样本；
   2. 根据训练集获得训练集的第i行内容，每行减去第i行逐个计算每个元素；

   输出：核函数矩阵；

   其中创建零矩阵的代码为numpy.mat(zeors(n,n))

2. SVM数据结构：

   1. 样本

   2. 样本分类标签

   3. 惩罚系数

   4. 迭代终止条件

   5. 拉格朗日因子 $num\times 1$ 的列向量

   6. 核函数矩阵 $num \times num$的矩阵

   7. 样本误差缓存 $num\times2$的矩阵

      需要缓存旧误差和新误差

3. 计算$\alpha_1$

4. 计算$\alpha$的误差$E_k$并更新误差缓存

   1. 公式如下： $$ E_k=\sum\limits_{i=1}^{N}\alpha_iy_iK_i1+b-y_k $$

   2. 向量对应元素相乘得到向量的代码为numpy.mutiply(matA,matB)

   3. 向量对应元素相乘再相加得到数的代码为matA * matB

   4. $\alpha$更新缓存为$[1,E_k]$