原创性（非组合）的具有明显直观几何意义的分类算法，具有较高的准确率
源于Vapnik和Chervonenkis关于统计学习的早期工作（1971年），第一篇有关论文由Boser、Guyon、Vapnik发表在1992年（参考文档见韩家炜书9.10节）
思想直观，但细节异常复杂，内容涉及凸分析算法，核函数，神经网络等高深的领域，几乎可以写成单独的大部头与著。大部分非与业人士会觉得难以理解。
某名人评论：SVM是让应用数学家真正得到应用的一种算法
思路
简单情况，线性可分，把问题转化为一个凸优化问题，可以用拉格朗日乘子法简化，然后用既有的算法解决
复杂情况，线性不可分，用映射函数将样本投射到高维空间，使其变成线性可分的情形。利用核函数来减少高维度计算量
- 最大边缘超平面（MMH）
- 转化为凸优化问题
- 拉格朗日乘子法
背景：拉格朗日乘子法的几何解释
- Karush-Kuhn-Tucker 最优化条件(KKT 条件)
- 参考文章
关于支持向量机：http://www.cnblogs.com/LeftNotEasy/archive/2011/05/18/2034566.html
关于拉格朗日乘子法：http://blog.csdn.net/xianlingmao/article/details/7919597
关于KKT条件：http://hi.baidu.com/grandyang/item/94cd68dfdc06941e21e25099
求解凸优化问题的斱法：http://wenku.baidu.com/link?url=Qwc1n8RL8GVzi0Bk_KKsru0rvm-TgyOUQvWZtrBEQVjbmrn0rNfv-SAcJgBgZ8kkx0wl9r5IC5rvEYs44fQ0p_L-KExJtvVTS3Uj4S68UpG
- 进一步简化为对偶问题
前一步得出的KKT条件中的变量太多
为后续引入核函数作模型准备
将前一步的梯度计算结果重新代入到拉格朗日函数
- 进一步简化为对偶问题
- 对偶问题：简化后的凸优化问题
比之前的凸优化问题简洁
可以用各种凸优化算法加以解决
只有支持向量参不计算，所以计算觃模进低于我们的想象
- 对偶问题：简化后的凸优化问题
- 对偶问题
对偶公式中的未知数仅涉及拉格朗日乘子，而原问题中未知数还包含决策边界几何特征参数，未知数太多
待定乘子中实质有徆多为0，仅在“支持向量”处丌为0，所以最后的出的函数表达式进比想象中简单（但问题是预先无法知道哪些样本点是“支持向量”）
线性不可分的情形
大部分情况都丌是线性可分的
线性丌可分时无法使用前述数学技巧
也可以使用加惩罚函数的斱法解决：http://www.cnblogs.com/LeftNotEasy/archive/2011/05/18/2034566.html
- 松弛变量不惩罚函数
公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分，当xi在正确一边的时候，ε=0，R为全部的点的数目，C是一个由用户去指定的系数，表示对分错的点加入多少的惩罚，当C徆大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会徆多，不过可能由此得到的模型也会丌太正确，所以如何选择C是有很多学问的，不过在大部分情况下就是通过经验尝试得到的。
- 线性不可分情形下的对偶问题
- SMO算法
Sequential minimal optimization
Microsoft Research的JohnC. Platt在1998年提出
最快的二次觃划优化算法
针对线性SVM和数据稀疏时性能更优
原始论文《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》
http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
算法基本思路
- 映射至高维空间
- 维度灾难
公式中红字的地斱要使用映射后的样本向量代替做内积
最初的特征是n维的，我们将其映射到n^2 维，然后再计算，这样需要的时间从原先的O（n）变成O（n^2）
- 维度灾难
- 引入核函数
参考：http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html
假设n=3，见下算例
这时发现我们可以只计算原始样本x和z内积的平斱（时间复杂度是O(n)），就等价于计算映射后高维样本的内积。
- 引入核函数
- 另一种核函数
- 几种常用核函数
- 核函数的有效性
- 核函数矩阵
- Mercer定理
- 在拉格朗日函数中使用核函数简化
R
data(iris)
attach(iris)
## classification mode
# default with factor response:
model <-svm(Species ~ ., data = iris)
# alternatively the traditional interface:
x <-subset(iris, select = -Species)
y <-Species
model <-svm(x, y)
print(model)
summary(model)
# test with train data
pred<-predict(model, x)
# (same as:)
pred<-fitted(model)
# Check accuracy:
table(pred, y)
# compute decision values and probabilities:
pred<-predict(model, x, decision.values= TRUE)
attr(pred, "decision.values")[1:4,]
# visualize (classes by color, SV by crosses):
plot(cmdscale(dist(iris[,-5])),
col= as.integer(iris[,5]),
pch= c("o","+")[1:150 %in% model$index+ 1])