机器学习-笔记（四）- 原问题和对偶问题

从svm处理非线性数据集中知道了处理非线性数据集的方法是将低维映射到高维，并写出了优化问题，现在需要将这个优化问题写成对偶问题来求解

预备知识

原问题：又称原线性规划问题，是指每一个线性规划的原始问题，每个原问题均可以转化为与其对称的对偶问题。定义如下图

 对偶问题：对原问题另一个角度的解释。定义如下图

为什么要写成对偶问题？

1. 方便核函数的引入。（关于核函数后面的文章再介绍）
2. 原问题的求解复杂度与特征的维数相关，而转成对偶问题后只与问题的变量个数有关。由于SVM的变量个数为支持向量的个数，相较于特征位数较少，因此转对偶问题。

如何转成对偶问题？

svm线性不可分的优化问题如下图所示，待求$(w,b,\delta )$

1.先写出原问题

由于原问题的定义中，限制条件没有参数大于等于0，所以要将优化问题的参数$\delta$取反，写成以下形式：

最小化：$\frac{1}{2}||w||^2-C\sum_{i=1}^{N}{\delta_i}$

限制条件：$1+\delta_i-y_iw^T\varphi (x_i)-y_ib \leq 0$    ,    $\delta_i\leq 0$

2.将原问题转化成对偶问题

最大化：$\theta (\alpha,\beta)=inf(\frac{1}{2}||w||^2-C\sum_{i=1}^{N}{\delta_i}+\sum_{i=1}^{N}{\beta_i\delta_i}+\sum_{i=1}^{N}\alpha_i(1+\delta_i-y_iw^T\varphi (x_i)-y_ib))$

限制条件：$\delta_i\geq 0, \beta_i \geq 0$

求解对偶问题

首先明确我们需要求:（w,b,δ），求最值先求导（从上至下是式子1,2,3）

 将式子2和式子3带入，化简后得到一个与α，β有关的式子（即θ）$\theta (\alpha,\beta)=\frac{1}{2}||w||^2+\sum_{i=1}^{N}\alpha_i-\sum_{i=1}^{N}\alpha_iy_iw^T\varphi (x_i)$

将式子1带入，各项展开

 

得到最终的化简结果

$\theta (\alpha)=\sum_{i=1}^{N}\alpha_i+\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(X_i,X_j)$

限制条件$0\leq \alpha_i\leq C, \sum_{i=1}^{N}\alpha_iy_i=0$ 

到此位置，我们可以根据算法，算出α的值

为什么只需知道核函数就可求解

已知K核函数和y，α，但是注意了！我们初衷是要求w，b，δ，要想求解w，我们现在只知道式子1

$w=\sum_{i=1}^{N}\alpha _iy_i\varphi (x_i)$，如何从该式子中求得w呢？需要知道$\varphi$吗？

不需要

因为求w是想知道$w^T\varphi (x)+b$与0的关系，从而分开不同的类别，将求导的式子1带入可以化简得到一个与α（已知）和K（已知）有关的式子，也就是不用显式的求出w，也得到了最终的目的

 接下来我们需要知道如何求b

求b需要用到kkt条件

 如何求b

 因为已经求出了所有的α，因此可以针对每个α求出b，再求b的平均值

以上过程也说明，核函数的重要性。

常见的核函数

• 多项式核函数$K(X_1,X_2)=(X_1^\tau*X_2+1)^d$
• 线性核函数$K(X1,X2)=X_1^TX_2$
• 高斯核函数$K(X_1,X_2)=e^{\frac{-||X_1-X_2||^2}{2\sigma^2}}$

高斯核函数的应用场景和效果相对来说比较出色，因此主要介绍一下高斯核函数

高斯核函数$K(X_1,X_2)=e^{\frac{-||X_1-X_2||^2}{2\sigma^2 }}$

• $X_2$是核函数中心，$||X_1-X_2||^2$是两个向量之间的欧式距离，两个向量之间的距离越大，高斯核函数的值越小
• $\sigma$控制高斯核函数的作用范围，其值越大，高斯核函数的局部影响范围越大

高斯核函数与概率论中的高斯分布$g(x)=\frac{1}{\sigma\sqrt{2\pi }}e^{\frac{-1}{2}(\frac{x-\mu }{\sigma})^2}$一样，概率论中的高斯函数表达式有两个参数：

• μ为均值，它决定了整个高斯函数中心轴的位置；
• σ为标准差，它是用来描述样本数据分布的情况：
  • σ越大，整个高斯函数的分布曲线（钟型图案）就会越宽越分散，即分布曲线又矮又胖；
  • σ越小，整个高斯函数的分布曲线（钟型图案）就会越窄越集中，即分布曲线又高又瘦；

在使用高斯核函数的时候，我们需要确定c和gamma两个超参数的值，$gamma=\frac{-1}{2\sigma^2 }$，c是惩罚系数，将高斯核函数与高斯分布的图像联系起来，就可知：

• gamma与$\sigma$呈反比。gamma越大，曲线越高瘦/影响范围越小，gamma越小，曲线越矮胖/影响范围越大。gamma的范围是$2^{-15}\sim 2^{3}$
•  C是对样本分错的宽容度。C越高，说明越不能容忍出现分错,容易过拟合。C越小，容易欠拟合。C过大或过小，泛化能力变差。c的范围是$2^{-5}\sim 2^{15}$

超参数的选择可以查看求解兵王问题

以下是gamma=10，gamma=1，gamma=0.5的图