机器学习第七周笔记 支持向量机

原创性（非组合）的具有明显直观几何意义的分类算法，具有较高的准确率
源于Vapnik和Chervonenkis关于统计学习的早期工作（1971年），第一篇有关论文由Boser、Guyon、Vapnik发表在1992年（参考文档见韩家炜书9.10节）
思想直观，但细节异常复杂，内容涉及凸分析算法，核函数，神经网络等高深的领域，几乎可以写成单独的大部头与著。大部分非与业人士会觉得难以理解。
某名人评论：SVM是让应用数学家真正得到应用的一种算法

思路

---

简单情况，线性可分，把问题转化为一个凸优化问题，可以用拉格朗日乘子法简化，然后用既有的算法解决
复杂情况，线性不可分，用映射函数将样本投射到高维空间，使其变成线性可分的情形。利用核函数来减少高维度计算量

• 1. 最大边缘超平面（MMH）

Paste_Image.png

• 2. 转化为凸优化问题

Paste_Image.png

• 3. 拉格朗日乘子法

Paste_Image.png

背景：拉格朗日乘子法的几何解释

Paste_Image.png

• 3. Karush-Kuhn-Tucker 最优化条件(KKT 条件)

Paste_Image.png

• 参考文章

关于支持向量机：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

• 4. 进一步简化为对偶问题
     前一步得出的KKT条件中的变量太多
     为后续引入核函数作模型准备
     将前一步的梯度计算结果重新代入到拉格朗日函数

Paste_Image.png

• 5. 对偶问题：简化后的凸优化问题
     比之前的凸优化问题简洁
     可以用各种凸优化算法加以解决
     只有支持向量参不计算，所以计算觃模进低于我们的想象

Paste_Image.png

• 对偶问题
  对偶公式中的未知数仅涉及拉格朗日乘子，而原问题中未知数还包含决策边界几何特征参数，未知数太多
  待定乘子中实质有徆多为0，仅在“支持向量”处丌为0，所以最后的出的函数表达式进比想象中简单（但问题是预先无法知道哪些样本点是“支持向量”）

线性不可分的情形

---

大部分情况都丌是线性可分的
线性丌可分时无法使用前述数学技巧
也可以使用加惩罚函数的斱法解决：http://www.cnblogs.com/LeftNotEasy/archive/2011/05/18/2034566.html

• 1. 松弛变量不惩罚函数

公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分，当xi在正确一边的时候，ε=0，R为全部的点的数目，C是一个由用户去指定的系数，表示对分错的点加入多少的惩罚，当C徆大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会徆多，不过可能由此得到的模型也会丌太正确，所以如何选择C是有很多学问的，不过在大部分情况下就是通过经验尝试得到的。

Paste_Image.png

• 2. 线性不可分情形下的对偶问题

Paste_Image.png

• 3. 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

算法基本思路

Paste_Image.png

• 4. 映射至高维空间
• 5. 维度灾难
     公式中红字的地斱要使用映射后的样本向量代替做内积
     最初的特征是n维的，我们将其映射到n^2 维，然后再计算，这样需要的时间从原先的O（n）变成O（n^2）

Paste_Image.png

• 6. 引入核函数
     参考：http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html
     假设n=3，见下算例
     这时发现我们可以只计算原始样本x和z内积的平斱（时间复杂度是O(n)），就等价于计算映射后高维样本的内积。

Paste_Image.png

• 另一种核函数

Paste_Image.png

• 几种常用核函数

Paste_Image.png

• 核函数的有效性

Paste_Image.png

• 核函数矩阵

Paste_Image.png

• 7. Mercer定理

Paste_Image.png

• 8. 在拉格朗日函数中使用核函数简化

Paste_Image.png

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])