2018-11-15 神奇的SVM

作者: 金夜SHOW | 来源:发表于2018-11-15 15:20 被阅读0次

1、神奇的SVM从点到直线距离开始：

$r=\frac{\vert w^Tx+b\vert }{\vert \vert w\vert \vert }$

一个二位坐标系，怎么才能把两类分开，我翻墙找到个MIT机器学习的视频，贼棒！把软件隔、核函数解释的清清楚楚。有个油管是视频，贴不过来，只能给路径了！简单清晰佩服佩服！吐槽下国内的讲述听不下去，上来就推公式，真的受不鸟。

https://www.youtube.com/watch?v=6nDqY8MPLDM

2、如何选这条“线”——优化问题

1、解决目标：最大化间隔 $r$ ，也就是最小化间隔 $\vert\vert w \vert\vert$

$\begin{array} \\min_{w,b} \quad\frac{1}{2} \vert \vert w \vert \vert ^2\\ \text{s.t} \quad \quad y_i(w^Tx_i+b)\geq 1 , \quad i=1,2,...,m \end{array}$

2、对偶问题转换：原优化问题是凸二次规划问题，不等式太多，需要求解的空间太大，所以求其对偶问的解。

对偶理论有许多重要应用：在原始的和对偶的两个线性规划中求解任何一个规划时，会自动地给出另一个规划的最优解；当对偶问题比原始问题有较少约束时，求解对偶规划比求解原始规划要方便得多。

（1）拉格朗日乘子法和KKT条件

https://www.zhihu.com/question/58584814/answer/159863739

重点：

1、KKT条件是凸优化问题有解的必要条件，主要是对不等式限制，把超多不等式转化为等式，只留下松弛变量一个不等式约束，这样就是减少了解空间，提升效率。

2、拉格朗日约束就是进一步求导的方式，缩减不等式数量。

思想：将不等式约束条件变成等式约束条件

通过拉格朗日乘子我们将原问题化为先求 $\alpha$ 为何值时，拉格朗日方程有最大值，然后求出 $\alpha$ 后求解 $w=\sum_{i=1}^m {\alpha} _i y_i x_i$ （拉格朗日方程对 $w$ 和 $b$ 求偏导为0）和 $b$ 的问题。

故所求的对偶问题是：

$\begin{array} \\\max_{\alpha} \quad \sum_{i=1}^m {\alpha} _i-\frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m{\alpha} _i{\alpha} _jy_iy_j \textbf{x}_i^T \textbf{x}_j \\ s.t \qquad \sum_{i=1}^m{\alpha} _iy_i=0;\\ \quad \quad\quad \alpha _i\geq 0,i=1,2... ,m \end{array}$

KKT条件（注意是必要条件）

$\begin{cases} \alpha _i\geq0; \\ y_if(x_i)-1 \geq 0;\\ \alpha _i( y_if(x_i)-1 ) = 0 \end{cases}$

可见，通过对偶问题后，本问题就转换为求解 $\alpha$ 获取最大值的问题。通过KKT条件 $\alpha _i( y_if(x_i)-1 ) = 0$ ，我们进一步确认两种情况的出现，一种是： $\alpha _i= 0$ ，另一种情况是 $y_if(x_i)=1$

于是上面这个二次规划问题（ $\textbf{x}_i^T \textbf{x}_j$ ）进一步用SMO方法解。
3、序列最小优化算SMO:

https://zhuanlan.zhihu.com/p/29212107

为什么用这个算法呢？百度发现怎么解二次规划问题，很多人会说常用方法是：椭球法、内点法、增广拉格朗日法、梯度投影法等。

其实问题再回归以下，什么是支持向量？？支持向量就是那些在不同样本中离我们的“线”最近的样本点。

SVM其实训练只需要支持向量参与就行，其他都是忽略项。那么上述这些算法其实对于大量样本来讲，大部分的样本都是无用的，也就是无法引起我们对目标函数更大的变化，所以专门设计了SOM算法，用启发式算法，每次选择取违背KKT条件程度最大的变量，这个怎么找？SOM用启发式算法，当确定了第一个变量后，选择使两个变量对应样本之间最大的变量作为第二个变量。直观来说，更新两个差别很大的变量，比起相似的变量，会带给目标函数更大的变化。思路通了以后再看以上公式推导和编程。

3、如何选这条“线”——不是“直”线？？

核函数：

类似学习线性变换的方法，我们一般讲低纬度不可分的话我们会给这些数据进行映射，将其映射到高纬平面中，使其线性可分。但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的(如上文中19维乃至无穷维的例子)。那咋办呢？此时，核函数就隆重登场了，核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。

4、如何选这条“线”——隔板不是“1”？？

最大化隔板、不满足条件的样本尽量少？？？

怎么办？继续对第一个拉格朗日方法优化问题加约束啊！方法和1一样，只是在出力样本时候加个损失函数，其中有hinge损失、指数损失和对数损失。这样我们就完成了整个问题的主要思路的梳理。

5、个人提炼

其实，SVM可以说是3条直线走天下，简单易懂，最后目标极其清晰！这里的支持向量、对偶问题、核函数、软隔板，其实也就是研究人员分析问题时的几个步骤：1、找关键点，2、复杂问题反面思考，3、高纬解决问题，4、没有一次能全部解决的问题，凡事留个裕度。

2018-11-15 神奇的SVM

1、神奇的SVM从点到直线距离开始：

$r=\frac{\vert w^Tx+b\vert }{\vert \vert w\vert \vert }$

2、如何选这条“线”——优化问题

3、如何选这条“线”——不是“直”线？？

4、如何选这条“线”——隔板不是“1”？？

5、个人提炼

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读