【svm学习笔记】svm_基础理论1

【写在前面】

这两天因为工程需要，用到svm，好奇之下，也自学一下，顺便记些笔记。

理论部分，主要参考的是网友Jasper的网文《svm入门》系列，原帖子见http://www.blogjava.net/zhenandaci/MyPosts.html。

既然人家都写了，为啥我还要写？不是写给别人看得，是写给自己的。主要是理清自己的思路，毕竟svm的理论这么深厚，稍不留神，就不知道“走”到哪儿了，就不知道为什么“到这儿了”，我主要是记录自己思路的足迹；另外，也就是备忘，《svm入门》毕竟是按人家的思路写的，有些我知道的，看起来觉得啰嗦，而我不太了解的，似乎又写得比较少。总之，开动了，至于能走到哪儿，我就不知道了。

【svm基础理论学习思路】

主要是理清主体思路。

问题：分类问题，即基于一些特征把某些样本分到若干个类别之中。这是模式识别、机器学习的经典问题。

分类问题可以分为两类：1. 线性可分问题；2. 线性不可分问题。

1. 线性可分问题

线性可分问题 --> 结构风险最小化 --> 最小误分次数 --> 最大几何间隔分类面 --> 最小化平面法向量|w| --> 带条件约束的凸二次规划 --> 加入拉格朗日乘子转成对偶问题 --> 解析解 or 数值解

2. 线性不可分问题

线性不可分问题 --> 线性可分问题

（1）向高维空间映射，使得大部分样本线性可分，核函数

（2）松弛变量，对于某些少数不可分的样本点，一定程度上忽略（程度大小，取决于惩罚因子C）

以上1和2是svm的核心理论部分。当然，还有一些外围部分的知识，主要是面临一些实际问题，如：1. 如何处理多类问题；2. 时空复杂度等。

【结构风险】

说结构风险之前，必须要说经验风险。

经验风险，是用样本定义的风险；对于分类问题，就是错误率；对于回归问题，就是平方训练误差；对于概率密度估计，经验风险等同于极大似然估计。

期望风险，是指真实风险，是我们能够永远逼近，但是无法达到的度量，代表模型的真实性能。

结构风险，是在经验风险的基础上，考虑到模型复杂度因素，对期望风险的一个逼近，逼近公式如下：

R(f) <= Remp(f) + Theta (h/n)

这里面不方便输入公式，我就用文字代替了。上面公式中的字母，R表示Risk，风险；Remp表示经验风险，Risk-empirical；Theta就是那个希腊字母；n表示训练样本数目；h表示模型复杂度，有个特定的名称，叫做“VC维”。可以看到，后面的那一项，与训练样本数目成反比（样本数目越多，模型越精确，风险越小），与模型的复杂度成正比（模型越复杂，泛化能力越小，对未知样本的风险就越大）。

“VC维”的物理意义：

如果有h个训练样本，这些样本被分为两类，这两类的划分方法有2^h种（很简单，对于每个样本，都可以有两种选择，到第一类或者到第二类，那h个样本，就是那么多选择）。如果对于任意一种分法，训练出的模型都能够正确的将h个训练样本分类，则就说这个模型能将h个训练样本“打散”，“VC维”就是模型能够打散的样本的最大个数。

以上只是直观的介绍“VC维”的物理意义。平时，只要记住他表示的是模型的复杂度就行了。