初步了解支持向量机(SVM)-1
从今天开始整理一些关于支持向量机-Support Vector Machine 的相关知识，大约发6-8篇的博客，敬请关注~欢迎推荐~
好了，由于这个东西本身就不好懂，要深入学习需要花费较多的时间和理。虽然现在网上有较多的参考文xian写的很不错，但是自己在学习的时候感觉所描述的数学公式还不够详尽，所以，借助于网上的一些资料和自己的理解，尝试整理一份比较适合初学者理解的资料。在这之前参考了较多的资料，有“支持向量机导论”，“统计学习方法”以及网上的一些博客，就不一一的详细列出了。
还是那句话，有任何问题，请随时不吝指正~
1 什么是支持向量机(SVM)
便于理解，从简单的分类说气，分类作为数据挖掘领域中一项非常重要的任务，它的目的是学会一个分类函数或分类模型（或者叫做分类器），该模型能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知类别。
所谓支持向量机，顾名思义，分为两个部分了解：一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点，下文将具体解释）；二，这里的“机（machine，机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如分类机（当然，也叫做分类器），而支持向量机本身便是一种监督式学习的方法（至于具体什么是监督学习与非监督学习，请参见此系列Machine Learning & Data Mining 第一篇），它广泛的应用于统计分类以及回归分析中。
而支持向量机是90 年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。
2 关于线性分类
在讲SVM 之前，必须先弄清楚一个概念：线性分类器（也可以叫做感知机）。
2-1 分类标准
未接简单起见，考虑的是一个两类的分类问题(多分类问题类似，只是延拓一下)，数据点用x 来表示，这是一个n 维向量，wT 上标中的“T”代表转置，而类别用y 来表示，可以取1 或者–1 ，分别代表两个不同的类。一个线性分类器就是要在n 维的数据空间中找到一个超平面，其方程可以表示为：
wTx + b = 0 (1.2.1)
上面给出了线性分类的定义描述，但或许读者没有想过：为何用y 取1 或者–1 来表示两个不同的类别呢？其实，这个1 或–1 的分类标准起源于Logistic 回归，为了完整和过渡的自然性，咱们就再来看看这个Logistic 回归。
2-2 1 或−1 分类标准的起源：Logistic 回归
使用的结果标签是y = −1，y = 1，替换在logistic 回归中使用的y = 0 和y = 1。同时将 替换成w 和b。以前的
Tx = θ0 + θ1x1 + θ2x2 + · · · + θnxn，
其中认为x0 = 1。现在我们替换θ0 为b，后面替换
θ1x1 + θ2x2 + · · · + θnxn
为w1x1 + w2x2 + · · · + wnxn（即wTx）。这样，我们让Tx = wTx + b，进一步
h(x) = g(Tx) = g(wTx + b)。
也就是说除了y 由y = 0 变为y = −1，只是标记不同外，与logistic 回归的形式化表示没区别。
再明确下假设函数
hw;b(x) = g(wTx + b)
上面提到过我们只需考虑Tx 的正负问题，而不用关心g(z)，因此我们这里将g(z) 做一个简化，将其简单映射到y = −1 和y = 1 上。映射关系如下：
g(z) = 1, z ≥ 0
−1, z < 0
于此，想必已经解释明白了为何线性分类的标准一般用1 或者–1 来表示。
2-3 线性分类的一个实例
下面举个简单的例子，一个二维平面（一个超平面，在二维空间中的例子就是一条直线），如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种则为蓝颜色的点，红颜色的线表示一个可行的超平面。
我们可以看出，这条红颜色的线把红颜色的点和蓝颜色的点分开来了。而这红颜色的线就是我们上面所说的超平面，也就是说，这个所谓的超平面的的确确便把这两种不同颜色的数据点分隔开来，在超平面一边的数据点所对应的y 全是–1，而在另一边全是1。接着，我们令分类函数
f(x) = wTx + b
显然，如果f(x) = 0，那么x 是位于超平面上的点。我们不妨要求对于所有满足f(x) < 0 的点，其对应的y 等于–1，而f(x) > 0 则对应y = 1 的数据点。
当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。更进一步，我们在进行分类的时候，将数据点x 代入f(x) 中，如果得到的结果小于0，则赋予其类别–1，如果大于0 则赋予类别1。如果f(x) = 0，则很难办了，分到哪一类都不是。
(1) 咱们就要确定上述分类函数f(x) = w · x+b（w · x 表示w 与x 的内积）中的两个参数w 和b，通俗理解的话w 是法向量，b 是截距（再次说明：定义特征到结果的输出函数u = ⃗w · ⃗x− b，与我们最开始定义的f(x) = wTx + b 实质是一样的）。
(2) 那如何确定w 和b 呢？答案是寻找两条边界端或极端划分直线中间的最大间隔（之所以要寻最大间隔是为了能更好的划分不同类的点，下文你将看到：为寻最大间隔，导出1/2∥w∥^2，继而引入拉格朗日函数和对偶变量，化为对单一因数对偶变量 的求解，当然，这是后话），从而确定最终的最大间隔分类超平面和分类函数；
(3) 进而把寻求分类函数f(x) = w · x + b 的问题转化为对w、b 的最优化问题，最终化为对偶因子的求解。
总结成一句话即是：从最大间隔出发（目的本就是为了确定法向量w），转化为求对变量w 和b 的凸二次规划问题。亦或如下所示。
3 函数间隔与几何间隔
一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面w · x + b 确定的情况下，|w · x + b| 能够相对的表示点x 到距离超平面的远近，而w · x + b 的符号与类标记y 的符号是否一致表示分类是否正确，所以，可以用量y · w · x + b 的正负性来判定或表示分类的正确性和确信度。
于此，我们便引出了定义样本到分类间隔距离的函数间隔的概念。
3-1 函数间隔
我们定义函数间隔为
^γ = y(wTx + b) = yf(x)
接着，我们定义超平面(w, b) 关于训练数据集T 的函数间隔为超平面(w, b) 关于T 中所有样本点(xi, yi) 的函数间隔最小值，其中x 是特征，y 是结果标签，i 表示第i 个样本，有
^γ = min ^γi, i = 1, 2, · · · , n
然与此同时，问题就出来了。上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w 和b，如将他们改变为2w 和2b，虽然此时超平面没有改变，但函数间隔的值yf(x) 却变成了原来的4 倍。其实，我们可以对法向量w 加些约束条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离——几何间隔的概念。
3-2 几个间隔
在给出几何间隔的定义之前，咱们首先来看下，如图1.4所示，对于一个点x，令其垂直投影到超平面上，对应的为x0，由于w 是垂直于超平面的一个向量，γ 为样本x 到分类间隔的距离，我们有
x = x0 + γ*w / ∥w∥
又由于x0 是超平面上的点，满足f(x0) = 0，代入超平面的方程即可算出
γ =(wTx + b)/∥w∥=f(x)/∥w∥
不过这里的γ 是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别y 即可，因此实际上我们定义几何间隔为
~γ = yγ =^γ/∥w∥
换而言之，函数间隔y(wTx + b) = yf(x) 实际上就是|f(x)|，只是人为定义的一个间隔度量；而几何间隔|f(x)|/∥w∥才是直观上的点到超平面距离。
