2018-02-07
机器学习-SVMs

• 分类: ml • 标签: ml

这个算法的历史已经有五十出头，适应于各种其它问题比如回归、离群值分析和排序等

从感知机到SVM

感知机的解有无数个，而svm以最大间隔的概念定义了一个目标函数仅有一个最优解。

基础

SVM的核心是结构风险最小化。

SVM（支持向量机）是一个有监督的学习模型，通常用来进行模式识别、分类以及回归分析。是数学规划方法在分类上的一个典型应用。

SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。

主要体现在最优化问题的处理上，包括MaxEnt、SVM等算法都利用了对偶理论来解决最优化问题。

a) 可以解决样本有限情况下的机器学习问题，目标是得到现有情况下的最优解；b) 算法最后转化为二次型寻优问题，得到全局最优解，可以避免神经网络结构选择和局部极值问题；c) 算法将实际问题通过非线性变换到高维特征空间，在高维空间中构造线性判别函数解决非线性问题，可以提高泛化性能；d) 通过对二类问题的推广，可以解决多类分类问题。

拉格朗日对偶

拉格朗日对偶事实上把SVM从依赖d个维度转变到依赖N个数据点。考虑到在最后计算时只有支持向量SV才有意义，所以这个计算量事实上比N小得多。

线性可分SVM算法数学建模

一个最优化问题通常有两个最基本的因素：1）目标函数，也就是你希望什么东西的什么指标达到最好；2）优化对象，你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中，目标函数显然就是那个“分类间隔”，而优化对象则是决策面。最终可得到如下的最优化模型。
$$
\min_{w,b}\frac12\Vert w\Vert
$$

软间隔SVM

如果有一些点是异常点，那么怎么会把他理解成作为惩罚项，如果使用了核函数，此时是否会把他映射在高维情况下，从而线性可分了呢？

优点与缺点

优点：

支持向量机能对非线性决策边界建模，又有许多可选的核函数。
在面对过拟合时，支持向量机有着极强的稳健性，尤其是在高维空间中。
可以解决小样本情况下的机器学习问题
可以解决高维问题，即大型特征空间；
能够处理非线性特征的相互作用；
无需依赖整个数据；
可以提高泛化能力；

缺点：

支持向量机是内存密集型算法，当观测样本很多时，效率并不是很高，不太适用较大的数据集；
选择正确的核函数就需要相当的技巧，对非线性问题没有通用解决方案，有时候很难找到一个合适的核函数；
对缺失数据敏感；
在当前的业界应用中，随机森林的表现往往要优于支持向量机。

SMO

pass

SVR

SVR是支持向量回归(support vector regression)的英文缩写，是支持向量机(SVM)的重要的应用分支。

One class SVM

pass

SVM的应用

SVM在很多诸如文本分类，图像分类（手写字符识别），生物序列分析和生物数据挖掘等领域有很多的应用，而且SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。

然而工业界中特征的多样性导致很少去使用 svm ，其中一个重要原因，因为 svm 本质上是属于一个几何模型，这个模型需要去定义 instance 之间的 kernel 或者 similarity （对于linear svm 来说，这个similarity 就是内积）。这其实和我们在之前说过的问题是相似的，我们无法预先设定一个很好的similarity。这样的数学模型使得 svm 更适合去处理 “同性质”的特征，例如图像特征提取中的 lbp 。而从不同 channel 中来的 feature 则更适合 tree-based model, 这些模型对数据的 distributation 通常并不敏感。

参考

http://blog.csdn.net/v_july_v/article/details/7624837
https://www.zhihu.com/question/35602879
零基础学SVM—Support Vector Machine(一)
零基础学SVM-Support Vector Machine(二)
为什么支持向量机要用拉格朗日对偶算法来解最大化间隔问题？
机器学习技法–SVM的对偶问题
支持向量机SVM（二）
NTUML 18. 对偶支持向量机
https://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650731669&idx=1&sn=b31a361017e0c6b9ecb2270fe3c01cbf&chksm=871b30ebb06cb9fdd51d6ae57fa7e3375bcff98a649ecff8a1ba9f485ae8cd5f63876bb20cf6&mpshare=1&scene=23&srcid=1008EaBplXTYgkkch7WXBnDW#rd
https://juejin.im/post/5930cc4c2f301e006bd4b2a9
https://www.zhihu.com/question/21704547/answer/20293255
http://www.csuldw.com/2016/02/26/2016-02-26-choosing-a-machine-learning-classifier/

$$
\sum_i y_i \alpha_i = 0
$$

$$
(x_i,y_i), \quad x \in R^d, y \in {-1,1}.
$$

$$
g(x) = \text{sign}(\phi(w) \cdot \phi(x) + b)
$$

$$
\phi^*(w) = \arg \min_{\phi(w)} \frac{1}{2} \norm{\phi(w)}^2, \
\text{such that} \quad y_i (\phi(w) \cdot \phi(x_i) + b) \ge 1.
$$

$$
L(\phi(w),b,\alpha) = \frac{1}{2}||\phi(w)||^2 - \sum_i \alpha_i (y_i (\phi(w) \cdot \phi(x_i) + b) - 1).
$$

$$
\pd{L(\phi(w),b,\alpha)}{\phi(w)} = \phi(w) - \sum_i y_i \alpha_i \phi(x_i) = 0,\
\pd{L(\phi(w),b,\alpha)}{b} = \sum_i y_i \alpha_i = 0.
$$

dzzxjl

2018-02-07 机器学习-SVMs