登录网易通行证
使用网易通行证(含网易邮箱)帐号登录
提交您的投诉或建议
视频画面花屏
视/音频不同步
播放不流畅
分享给朋友:
扫描分享给微信好友和朋友圈
扫一扫分享给微信好友和朋友圈
通过代码可以让这个视频在其它地方上播放！
复制FLASH代码
复制HTML代码
复制页面地址
使用公开课APP下载视频
扫描二维码 手机继续看
扫描二维码在手机上继续观看，
还可分享给您的好友。
没有公开课客户端？
登录后才能查看我的笔记
暂时没有笔记!
确定删除笔记？
即将播放下一集，请您保存当前的笔记哦！
对字幕纠错要登录哦！
内容不能少于3个字
这一讲首先介绍了人工智能的定义[0:00:00]。之后，教授讲解了生成测试法，并详细谈到了给事物命名的重要性：“给某种事物命名后，你就对它拥有了力量”[0:11:30]。再后，教授介绍了人工智能发展的简史，讲到了本课程中将会接触到的各种人工智能程序[0:20:28]。最后，教授展望了人工智能的未来并讲了一些课程事务信息[0:32:40]。
这一讲首先通过一个积分题引出了课程内容，讲解早期人工智能中求解符号积分的人工智能程序，该程序能够求解出MIT微积分期末考试中的几乎所有积分题目并打败大一学生[0:00:00]。之后，教授介绍了安全变换和启发式变换，并用它们求解了这个积分题[0:05:40]。详细介绍了程序求解积分题的方法之后，教授讲解了人工智能这方面中值得思考的问题[0:31:40]。
这一讲首先介绍了一个移动方块的人工智能程序，并以此详细讲解了目标树的概念，这一程序不仅能够能够实现目标，还能解释自己在过程中的一些行为[0:00:00]。第二部分，教授详细介绍了基于规则的专家系统，有一个医疗方面的专家系统比医生的诊断还要准确，教授讲解了它是如何做到的[0:18:20]。第三部分，教授通过杂货店装袋的例子，总结了知识工程中的三大原则[0:33:17]。
这一讲开始讨论各种搜索算法，首先是最基本的大英博物馆法，也就是找出一切可能的蛮力算法[0:00:00]。之后教授通过例子讲解了深度优先搜索算法和广度优先搜索算法[0:08:05]。之后，教授介绍了搜索中如何避免重复搜索，并用其分别优化深度优先和广度优先算法，得到爬山算法和束搜索算法[0:20:26]。最后，教授讲解了故事阅读中搜索的程序例子[0:41:15]。
这一讲主要讨论了最短路径问题。首先教授在黑板上演示了一个例子，介绍分支限界法[0:00:00]。之后，教授引入了扩展列表，避免重复扩展，以优化分支限界法[0:18:35]。再后，教授通过可容许启发式对算法进行了优化，避免寻找最短路径时往反方向进行的无谓搜索[0:25:15]。最后，教授将上述两种优化加到分支限界法上，得到A*算法，并讲解了A*算法中可能碰到的一些问题[0:36:00]。
这一讲讲解了人工智能如何进行博弈，包括下棋，深蓝曾经因为击败国际象棋世界冠军卡斯帕罗夫而轰动一时。这一讲首先介绍了进行博弈可以使用的各种方法[0:00:00]。之后开始讲解极小化极大算法[0:14:40]。再后，教授介绍了极小化极大算法的优化——α-β剪枝法，这样做能够有效提高算法效率[0:21:57]。最后，教授讲解了逐步深入和随时算法的概念，并介绍了深蓝的实际工作机制[0:34:10]。
这一讲主要讲解了如何让计算机智能识别物体的组成，也就是线条图解释，这是计算机视觉方面的基础。教授首先介绍了这方面研究的历史，详细介绍了不同时期，三位计算机科学家对这一问题的解决方法：首先讲解了Guzman的实验方法[0:00:00]，之后讲解了哈夫曼的理论方法[0:11:50]，最后讲到Waltz是如何将前人的方法总结得出优秀算法的[0:32:00]。
这一讲主要讲解地图着色问题和资源调度问题。首先，教授使用一般深度优先搜索为美国地图进行着色（四色问题），这是根本行不通的[0:00:00]。之后，教授在此基础上使用了域缩减算法，这让问题处理得到了很大改善[0:09:20]。再后，教授又加入了最多约束优先的优化，这种做法效果很大[0:29:00]。最后，教授将地图着色问题的解决方法应用到了资源调度问题，考虑如何调度飞机的情况[33:35]。
这一讲讨论了计算机视觉和对象识别，介绍了这方面技术的缓慢发展以及仍未完全解决的现状。这一讲首先介绍了大卫·马尔对计算机视觉的早期思想[0:00:00]。之后，教授介绍了Shimon Ullman的比对理论（alignment theories），并进行了模拟演示和相关证明[0:07:00]。最后一部分，教授介绍了人脸识别技术的现有方法和困境[0:30:45]。
这一讲开始讨论机器学习方面的内容，机器学习专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，不断改善自身的性能，是人工智能的核心[0:00:00]。教授首先举例讲解了机器人如何辨别流水线上不同的产品，以此介绍最近邻问题[0:08:45]。之后，教授讲解了机械臂如何在学习过程中实现特定的动作，例如打球和抽熄蜡烛[0:24:15]。最后，教授讲解了睡眠相关的研究[0:42:20]。
这一讲继续讲机器学习方面的内容。首先，教授介绍了识别树的概念，这是用一系列测试标准判别某个体属于哪一类的树[0:00:00]。之后，教授考虑了大数据的情况，这时就有必要引入无序度的概念，来衡量测试的质量，这部分借用了信息论方面的知识[0:21:43]。最后，教授在前面的基础上进行完善，考虑了数值数据如何处理，并同之前的最近邻算法进行了对比[0:40:30]。
这一讲继续讲机器学习方面的内容。首先，教授介绍了生物学上的神经网络，并将其推广到人工智能领域，对其进行建模[0:00:00]。之后，教授讲解了性能函数，并讲到如何对其进行优化，详细讲到了梯度上升法[0:10:40]。再后，教授详细进行了相关的偏导计算，并深入探究了反向传播算法[0:25:36]。最后，教授讲到了神经网络算法相关的一些问题，并给出了示例[0:40:45]。
这一讲继续讲机器学习方面的内容，主要内容是遗传算法，这是一种对生物和进化的模仿，教授首先介绍了相关的生物学知识[0:00:00]。第二部分，教授介绍了朴素的进化算法[0:07:20]。第三部分考虑了对算法的一些改进（包括模拟退火算法）[0:20:50]。最后，教授介绍了一些遗传算法的例子，包括用方块模拟的生物进化[0:35:10]。
这一讲继续讲机器学习方面的内容，首先介绍了音韵学方面的基础知识，讲到了音素、区别性特征等概念[0:00:00]。之后，教授引出了Yip-Sussman机器的概念，并通过一个课堂演示讲解了它在音韵学方面的用途[0:14:00]。最后，教授介绍了稀疏空间的概念，并总结出了好的AI算法应该满足哪些要素[0:37:15]。
这一讲继续讲机器学习方面的内容，首先介绍了一次性学习（one-shot learning）的概念，讲解如何通过相近差错（near miss）从每一对例子中学到确切的知识[0:00:00]。之后，教授将这方面人的学习同机器学习进行了详细对比[0:14:30]。最后，教授通过一次性学习的概念，总结出了一个好的概念应当满足哪些特性才更容易出名[0:37:30]。
[第16课]16 学习：支持向量机
这一讲继续讲机器学习方面的内容，焦点是支持向量机。教授首先介绍了如何通过一条最宽的&街道&将两类样本点分开[0:00:00]。之后，教授详细给出了支持向量机概念中涉及到的数学推导，并由此得到了一个非常妙的结论[0:15:10]。最后，教授演示了一个demo，并讲解了核函数的概念和应用[0:38:50]。
这一讲继续讲机器学习方面的内容，着重讲解boosting(提升)算法。这一讲首先总结了之前的各种学习算法，引入了分类器的概念，并讲解了如何从弱分类器得到强分类器[0:00:00]。之后，教授讲到了各种改进，来得到boosting算法[0:11:50]。最后，教授讲解了如何使用一些计算技巧，获得简单美妙的结果，告诉学生在考试中碰到相关问题应该怎么算[0:35:30]。
这一讲首先简介了人类的进化历程，强调象征性思维能力是让人类不同于其它生物的关键[0:00:00]。随后，教授介绍了内语言和语义网络的概念[0:09:00]。之后，教授详细介绍了内语言中非常重要的三大元素：分类、轨迹和过渡框架[0:14:30]。最后教授强调了故事讲解和理解的重要性，并告诉大家如何讲故事[0:39:25]。
这一讲介绍了人工智能方面的一些通用架构：第一部分讲解了通用问题求解器（GPS）[0:00:00]；第二部分讲解了SOAR架构（状态算子与结果架构）[0:09:24]；第三部分详细讲解了马文·闵斯基的情绪机器（emotion machine）[0:16:16]；第四部分向详细讲解了包容架构（subsumption architecture），这也是当今主流吸尘器机器人伦巴所使用的架构[0:22:26]；最后，教授讲解了自己现在正在开发的Genesis架构[0:34:00]。
这一讲主要是一些概率相关的必要知识，首先教授通过一个例子引出了考虑概率问题的重要性，引入了联合概率表的概念，并进行了相关演示[0:00:00]。第二部分，教授讲解了一些基本的概率公理和定义[0:18:30]。最后，教授引出了信念网络这一概念，并将之前所讲的概率知识用于这一重要领域[0:36:30]。
这一讲首先详细讲解了上一节已经提到过的贝叶斯概率方面的知识，考虑如何从一系列条件概率的乘积算出整张联合概率表[0:00:00]。然后，教授介绍了如何根据结果来反推哪类模型更有可能正确（例如有两个硬币，抛得正反的概率不同，如何通过实际抛掷试验，求更有可能是哪个硬币）[0:18:15]。最后，教授介绍了结构发现方面的内容[0:42:50]。
这一讲是MIT人工智能课程的最后一节课，教授首先继续上一讲讲完了主干内容，包括模型融合、跨通道偶合[0:00:00]。之后，教授对课程进行了一些回顾，并讲到了期末考的相关事项[0:12:30]。再后，教授展望了未来，告诉感兴趣的同学，后面还有哪些课程值得学习[0:20:30]。最后，教授演示了他的团队正在开发的Genesis系统，并在此基础上进行了总结[0:29:40]。
学校：麻省理工学院
讲师：美国
授课语言：英文
类型：国际名校公开课 科技
课程简介：本课程学习人工智能，以授课形式讲述什么人工智能，人工智能的重要性和其未来，包括如何进行博弈、图像识别、以及机器学习方面的内容
扫描左侧二维码下载客户端Python中支持向量机SVM的使用方法详解
转载 &更新时间：日 16:02:27 & 作者：陆瑶
这篇文章主要为大家详细介绍了Python中支持向量机SVM的使用方法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
除了在Matlab中使用PRTools工具箱中的svm算法，Python中一样可以使用支持向量机做分类。因为Python中的sklearn库也集成了SVM算法，本文的运行环境是Pycharm。
一、导入sklearn算法包
　　Scikit-Learn库已经实现了所有基本机器学习的算法，具体使用详见说明
　　skleran中集成了许多算法，其导入包的方式如下所示，
　　逻辑回归：from sklearn.linear_model import LogisticRegression
&&&&& &朴素贝叶斯：from sklearn.naive_bayes import GaussianNB
&　　K-近邻：from sklearn.neighbors import KNeighborsClassifier
&　　决策树：from sklearn.tree import DecisionTreeClassifier
&　　支持向量机：from sklearn import svm
&二、sklearn中svc的使用
（1）使用numpy中的loadtxt读入数据文件
　　loadtxt()的使用方法：
　　fname:文件路径。eg：C:/Dataset/iris.txt。
　　dtype：数据类型。eg：float、str等。
　　delimiter：分隔符。eg：‘，'。
　　converters：将数据列与转换函数进行映射的字典。eg：{1:fun}，含义是将第2列对应转换函数进行转换。
　　usecols：选取数据的列。
　　以Iris兰花数据集为例子：
　　由于从UCI数据库中下载的Iris原始数据集的样子是这样的，前四列为特征列，第五列为类别列，分别有三种类别Iris-setosa， Iris-versicolor， Iris-virginica。　　　
当使用numpy中的loadtxt函数导入该数据集时，假设数据类型dtype为浮点型，但是很明显第五列的数据类型并不是浮点型。
因此我们要额外做一个工作，即通过loadtxt()函数中的converters参数将第五列通过转换函数映射成浮点类型的数据。
首先，我们要写出一个转换函数：
def iris_type(s):
it = {'Iris-setosa': 0, 'Iris-versicolor': 1, 'Iris-virginica': 2}
return it[s]
接下来读入数据，converters={4: iris_type}中“4”指的是第5列：
path = u'D:/f盘/python/学习/iris.data' # 数据文件路径
data = np.loadtxt(path, dtype=float, delimiter=',', converters={4: iris_type})
读入结果：
（2）将Iris分为训练集与测试集
x, y = np.split(data, (4,), axis=1)
x = x[:, :2]
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=1, train_size=0.6)
　　1. split(数据，分割位置，轴=1（水平分割） or 0（垂直分割）)。
　　2. x = x[:, :2]是为方便后期画图更直观，故只取了前两列特征值向量训练。
　　3. sklearn.model_selection.train_test_split随机划分训练集与测试集。train_test_split(train_data,train_target,test_size=数字, random_state=0)
　　参数解释：
　　train_data：所要划分的样本特征集
　　train_target：所要划分的样本结果
　　test_size：样本占比，如果是整数的话就是样本的数量
　　random_state：是随机数的种子。
　　随机数种子：其实就是该组随机数的编号，在需要重复试验的时候，保证得到一组一样的随机数。比如你每次都填1，其他参数一样的情况下你得到的随机数组是一样的。但填0或不填，每次都会不一样。随机数的产生取决于种子，随机数和种子之间的关系遵从以下两个规则：种子不同，产生不同的随机数；种子相同，即使实例不同也产生相同的随机数。
（3）训练svm分类器
# clf = svm.SVC(C=0.1, kernel='linear', decision_function_shape='ovr')
clf = svm.SVC(C=0.8, kernel='rbf', gamma=20, decision_function_shape='ovr')
clf.fit(x_train, y_train.ravel())
&　　kernel='linear'时，为线性核，C越大分类效果越好，但有可能会过拟合（defaul C=1）。
　　 kernel='rbf'时（default），为高斯核，gamma值越小，分类界面越连续；gamma值越大，分类界面越“散”，分类效果越好，但有可能会过拟合。
　　decision_function_shape='ovr'时，为one v rest，即一个类别与其他类别进行划分，
　　decision_function_shape='ovo'时，为one v one，即将类别两两之间进行划分，用二分类的方法模拟多分类的结果。
（4）计算svc分类器的准确率
print clf.score(x_train, y_train) # 精度
y_hat = clf.predict(x_train)
show_accuracy(y_hat, y_train, '训练集')
print clf.score(x_test, y_test)
y_hat = clf.predict(x_test)
show_accuracy(y_hat, y_test, '测试集')
如果想查看决策函数，可以通过decision_function()实现
print 'decision_function:\n', clf.decision_function(x_train)
print '\npredict:\n', clf.predict(x_train)
　　decision_function中每一列的值代表距离各类别的距离。
（5）绘制图像
1.确定坐标轴范围，x，y轴分别表示两个特征
x1_min, x1_max = x[:, 0].min(), x[:, 0].max() # 第0列的范围
x2_min, x2_max = x[:, 1].min(), x[:, 1].max() # 第1列的范围
x1, x2 = np.mgrid[x1_min:x1_max:200j, x2_min:x2_max:200j] # 生成网格采样点
grid_test = np.stack((x1.flat, x2.flat), axis=1) # 测试点
# print 'grid_test = \n', grid_testgrid_hat = clf.predict(grid_test)
# 预测分类值grid_hat = grid_hat.reshape(x1.shape) # 使之与输入的形状相同
这里用到了mgrid()函数，该函数的作用这里简单介绍一下：
假设假设目标函数F（x，y）=x+y。x轴范围1~3，y轴范围4~6，当绘制图像时主要分四步进行：
　　【step1：x扩展】(朝右扩展)：
&&&&&&&& [1 1 1]
　　 [2 2 2]
　　 [3 3 3]
　　【step2：y扩展】(朝下扩展)：
　　 [4 5 6]
　　 [4 5 6]
　　 [4 5 6]
　　【step3：定位（xi，yi）】：
　　 [(1,4) (1,5) (1,6)]
　　 [(2,4) (2,5) (2,6)]
　　 [(3,4) (3,5) (3,6)]
　　【step4：将（xi，yi）代入F(x,y)=x+y】
　　因此这里x1, x2 = np.mgrid[x1_min:x1_max:200j, x2_min:x2_max:200j]后的结果为：
　　再通过stack()函数，axis=1，生成测试点
2.指定默认字体
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
cm_light = mpl.colors.ListedColormap(['#A0FFA0', '#FFA0A0', '#A0A0FF'])
cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])
plt.pcolormesh(x1, x2, grid_hat, cmap=cm_light)
plt.scatter(x[:, 0], x[:, 1], c=y, edgecolors='k', s=50, cmap=cm_dark) # 样本
plt.scatter(x_test[:, 0], x_test[:, 1], s=120, facecolors='none', zorder=10) # 圈中测试集样本
plt.xlabel(u'花萼长度', fontsize=13)
plt.ylabel(u'花萼宽度', fontsize=13)
plt.xlim(x1_min, x1_max)
plt.ylim(x2_min, x2_max)
plt.title(u'鸢尾花SVM二特征分类', fontsize=15)
# plt.grid()
plt.show()
pcolormesh(x,y,z,cmap)这里参数代入x1，x2，grid_hat，cmap=cm_light绘制的是背景。
scatter中edgecolors是指描绘点的边缘色彩，s指描绘点的大小，cmap指点的颜色。
xlim指图的边界。
最终结果为：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具机器学习实战 - 读书笔记(06) – SVM支持向量机
最近在看Peter Harrington写的“机器学习实战”，这是我的学习笔记，这次是第6章：SVM 支持向量机。
支持向量机不是很好被理解，主要是因为里面涉及到了许多数学知识，需要慢慢地理解。我也是通过看别人的博客理解SVM的。
推荐大家看看on2way的SVM系列：
SVM - Support Vector Machine。支持向量机，其含义是通过支持向量运算的分类器。其中“机”的意思是机器，可以理解为分类器。
什么是支持向量呢？在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。
见下图，在一个二维环境中，其中点R，S，G点和其它靠近中间黑线的点可以看作为支持向量，它们可以决定分类器，也就是黑线的具体参数。
分类器：就是分类函数。
线性分类：可以理解为在2维空间中，可以通过一条直线来分类。在p维空间中，可以通过一个p-1维的超平面来分类。
向量：有多个属性的变量。在多维空间中的一个点就是一个向量。比如 \(x = (x_1, x_2, ..., x_n)\)。下面的\(w\)也是向量。
约束条件(subject to) ： 在求一个函数的最优值时需要满足的约束条件。
向量相乘: \(xw^T = \textstyle \sum_{i=1}^n w_ix_i\)
内积: \(\langle x,y \rangle = \textstyle \sum_{i=1}^n x_iy_i\)
解决的问题：
在训练数据中，每个数据都有n个的属性和一个二类类别标志，我们可以认为这些数据在一个n维空间里。我们的目标是找到一个n-1维的超平面（hyperplane），这个超平面可以将数据分成两部分，每部分数据都属于同一个类别。
其实这样的超平面有很多，我们要找到一个最佳的。因此，增加一个约束条件：这个超平面到每边最近数据点的距离是最大的。也成为最大间隔超平面（maximum-margin hyperplane）。这个分类器也成为最大间隔分类器（maximum-margin classifier）。
支持向量机是一个二类分类器。
非线性分类
SVM的一个优势是支持非线性分类。它结合使用拉格朗日乘子法和KKT条件，以及核函数可以产生非线性分类器。
分类器1 - 线性分类器
是一个线性函数，可以用于线性分类。一个优势是不需要样本数据。
classifier 1:
f(x) = xw^T + b
\(w\) 和 \(b\) 是训练数据后产生的值。
分类器2 - 非线性分类器
支持线性分类和非线性分类。需要部分样本数据（支持向量），也就是\(\alpha_i \ne 0\)的数据。
\(\because\)
\(w = \textstyle \sum_{i=1}^n \alpha_iy_ix_i\)
\(\therefore\)
classifier 2:
f(x) = \textstyle \sum_{i=1}^n \alpha_iy_i K(x_i, x) + b \\
\text{here} \\
\qquad x_i \text{ : training data i} \\
\qquad y_i \text{ : label value of training data i} \\
\qquad \alpha_i \text{ : Lagrange multiplier of training data i} \\
\qquad K(x_1, x_2) = exp(-\frac{\lVert x_1 - x_2 \rVert ^2}{2\sigma^2}) \text{ : kernel function} \\
\(\alpha\), \(\sigma\) 和 \(b\) 是训练数据后产生的值。
可以通过调节\(\sigma\)来匹配维度的大小，\(\sigma\)越大，维度越低。
SVM的目的是要找到一个线性分类的最佳超平面 \(f(x) = xw^T + b = 0\)。求 \(w\) 和 \(b\)。
首先通过两个分类的最近点，找到\(f(x)\)的约束条件。
有了约束条件，就可以通过拉格朗日乘子法和KKT条件来求解，这时，问题变成了求拉格朗日乘子\(\alpha_i\) 和 \(b\)。
对于异常点的情况，加入松弛变量\(\xi\)来处理。
使用SMO来求拉格朗日乘子\(\alpha_i\)和\(b\)。这时，我们会发现有些\(\alpha_i = 0\)，这些点就可以不用在分类器中考虑了。
惊喜! 不用求\(w\)了，可以使用拉格朗日乘子\(\alpha_i\)和\(b\)作为分类器的参数。
非线性分类的问题：映射到高维度、使用核函数。
线性分类及其约束条件
SVM的解决问题的思路是找到离超平面的最近点，通过其约束条件求出最优解。
对于训练数据集T，其数据可以分为两类C1和C2。
对于函数：\(f(x) = xw^T + b\)
对于C1类的数据 \(xw^T + b \geqslant 1\)。其中至少有一个点\(x_i\)， \(f(x_i) = 1\)。这个点称之为最近点。
对于C2类的数据 \(xw^T + b \leqslant -1\)。其中至少有一个点\(x_i\)， \(f(x_i) = -1\)。这个点称也是最近点。
上面两个约束条件可以合并为：
\(y_if(x_i) = y_i(x_iw^T + b) \geqslant 1\)。
\(y_i\)是点\(x_i\)对应的分类值（-1或者1）。
求\(w\)和\(b\).
则超平面函数是\(xw^T + b = 0\)。
为了求最优的f(x)， 期望训练数据中的每个点到超平面的距离最大。
（解释1: 这里需要理解一个事情，根据上图，我们可以给每个点做一条平行于超平面的平行线（超平行面），因此，这个最大化相当于求最近点到超平面距离的最大化。）
总结，现在我们的公式是：
Formula 6.1
f(x) = xw^T + b \\
\text{subject to} \\
\qquad y_if(x_i) = y_i(x_iw^T + b) \geqslant 1, i = 1, ..., n
几个训练脑筋的小问题：
Q: y是否可以是其它非{-1， 1}的值?
A: 将y值定义为{-1， 1}是最简化的方案。你的分类可以是cat和dog，只要将cat对应到1, dog对应到-1就可以了。你也可以将y值定义为其它数比如: -2, 2或者2, 3之类的，但是这样就需要修改超平面函数和约束条件，增加了没必要的繁琐，实际上和y值定义为{-1， 1}是等价的。
Q: 如果两组数据里的太近或者太远，是不是可能就找不到\(xw^T + b = 1\) 和\(xw^T + b = -1\)的这两个点？
A: 不会。假设可以找到\(x_iw^T + b = c\) 和 \(x_jw^T + b = -c\). \(c & 0 and c && 1\)。其超平面函数为\(xw^T + b = 0\).
上面公式左右同时除以c, 则：
\(x_iw^T / c + b / c = 1\)
\(x_jw^T / c + b / c = -1\)
\(w' = w/c\)
\(b' = b/c\)
\(x_iw'^T + b' = 1\)
\(x_jw'^T + b' = -1\)
可以找到超平面函数:
\(xw^T + b' = 0\)
因此，总是可以找到y是{-1, 1}的超平面，如果有的话。
最大几何间隔（geometrical margin）
\(f(x)\)为函数间隔\(\gamma\)。
如果求\(\text{max } yf(x)\)，有个问题，就是w和b可以等比例增大，导致\(yf(x)\)的间隔可以无限大。因此需要变成求等价的最大几何间隔：
\bar{\gamma} = \frac{yf(x)}{\lVert w \rVert} \\
\text{subject to} \\
\qquad y_if(x_i) = y_i(x_iw^T + b) \geqslant 1, i = 1, ..., n
\(\lVert w \rVert\) : 二阶范数，也就是各项目平方和的平方根。 \(\sqrt {\textstyle \sum_{i=1}^n w_i^2}\)
根据上面的解释，这个问题可以转变为：
\text{max } \frac{1}{\lVert w \rVert} \\
\text{subject to} \\
\qquad y_i(x_iw^T + b) \geqslant 1, i = 1, ..., n
再做一次等价转换：
Formula 6.2
\text{min } \frac{1}{2} \lVert w \rVert ^ 2 \\
\text{subject to} \\
\qquad y_i(x_iw^T + b) \geqslant 1, i = 1, ..., n
求解问题\(w,b \Leftrightarrow \alpha_i, b\)
我们使用拉格朗日乘子法和KKT条件来求\(w\)和\(b\)，一个重要原因是使用拉格朗日乘子法后,还可以解决非线性划分问题。
拉格朗日乘子法和KKT条件可以解决下面这个问题：
求一个最优化问题 \(f(x)\)
刚好对应我们的问题：\(min \frac{1}{2} \lVert w \rVert ^ 2\)
如果存在不等式约束\(g_k(x) &= 0, k = 1, …, q\)。
对应 \(\text{subject to } \qquad 1 - y_i(x_iw^T + b) &= 0, i = 1, ..., n\)
F(x)必须是凸函数。这个也满足。
SVM的问题满足使用拉格朗日乘子法的条件。因此问题变成：
Formula 6.3
\underset{\alpha}{max} \text{ } W(\alpha) = \mathcal{L}(w,b,\alpha) = \frac{1}{2} \lVert w \rVert ^ 2 - \textstyle \sum_{i=1}^n \alpha_i(y_i(x_iw^T + b) - 1) \\
\text{subject to} \\
\qquad \alpha_i &= 0, i = 1, ..., n \\
\qquad \textstyle \sum_{i=1}^n \alpha_iy_i = 0 \\
\qquad 1 - y_i(x_iw^T + b) &= 0, i = 1, ..., n \\
\qquad w = \textstyle \sum_{i=1}^n \alpha_iy_ix_i \\
\text{here} \\
\qquad \alpha_i \text{ : Lagrange multiplier of training data i} \\
消除\(w\)之后变为：
Formula 6.4
\underset{\alpha}{max} \text{ } W(\alpha) = \mathcal{L}(w,b,\alpha) = \textstyle \sum_{i=1}^n \alpha_i - \frac{1}{2} \textstyle \sum_{i,j=1}^n \alpha_i\alpha_jy_iy_jx_i^Tx_j \\
\text{subject to} \\
\qquad \alpha_i &= 0, i = 1, ..., n \\
\qquad \textstyle \sum_{i=1}^n \alpha_iy_i = 0 \\
\qquad \alpha_i(1 - y_i(\textstyle \sum_{j=1}^n \alpha_jy_j \langle x_j,x_i \rangle + b)) = 0, i = 1, ..., n
\(\langle x_j,x_i \rangle\)是\(x_j\) 和 \(x_i\)的内积，相当于\(x_ix_j^T\)。
可见使用拉格朗日乘子法和KKT条件后，求\(w,b\)的问题变成了求拉格朗日乘子\(\alpha_i\)和\(b\)的问题。
到后面更有趣，变成了不求\(w\)了，因为\(\alpha_i\)可以直接使用到分类器中去，并且可以使用\(\alpha_i\)支持非线性的情况（\(xw^T + b\)是线性函数，支持不了非线性的情况哦）。
以上的具体证明请看：
关于拉格朗日乘子法和KKT条件，请看：
处理异常点（outliers）
如上图：点w是一个异常点，导致无法找到一个合适的超平面，为了解决这个问题，我们引入松弛变量(slack variable)\(\xi\)。
修改之间的约束条件为：\(x_iw^T + b &= 1 – \xi_i \qquad \text{for all i = 1, …, n}\)
则运用拉格朗日乘子法之后的公式变为：
Formula 6.5
\underset{\alpha}{max} \text{ } W(\alpha) = \mathcal{L}(w,b,\alpha) = \textstyle \sum_{i=1}^n \alpha_i - \frac{1}{2} \textstyle \sum_{i,j=1}^n \alpha_i\alpha_jy_iy_jx_jx_i^T \\
\text{subject to} \\
\qquad 0 \leqslant \alpha_i \leqslant C, i = 1, ..., n \\
\qquad \textstyle \sum_{i=1}^n \alpha_iy_i = 0 \\
\qquad \alpha_i(1 - y_i(\textstyle \sum_{j=1}^n \alpha_jy_j \langle x_j,x_i \rangle + b)) = 0, i = 1, ..., n
输入参数：
参数\(C\)，越大表明影响越严重。\(C\)应该一个大于0值。其实\(C\)也不能太小，太小了就约束\(\alpha_i\)了，比如200。
参数\(\xi\)，对所有样本数据起效的松弛变量，比如：0.0001。
具体证明请看：
求解\(\alpha\) - 使用SMO方法
1996年，John Platt发布了一个称为SMO的强大算法，用于训练SVM。SMO表示序列最小优化（Sequential Minimal Optimization）。
概要：SMO方法的中心思想是每次取一对\(\alpha_i\)和\(\alpha_j\)，调整这两个值。
参数: 训练数据/分类数据/\(C\)/\(\xi\)/最大迭代数
初始化\(\alpha\)为0；
在每次迭代中 （小于等于最大迭代数），
- 找到第一个不满足KKT条件的训练数据，对应的\(\alpha_i\)，
- 在其它不满足KKT条件的训练数据中，找到误差最大的x，对应的index的\(\alpha_j\)，
- \(\alpha_i\)和\(\alpha_j\)组成了一对，根据约束条件调整\(\alpha_i\), \(\alpha_j\)。
不满足KKT条件的公式：
Formula 6.6
\text{(1) } y_i(u_i - y_i) \leqslant \xi \text{ and } \alpha_i & C \\
\text{(2) } y_i(u_i - y_i) \geqslant \xi \text{ and } \alpha_i & 0 \\
\qquad u_i = \textstyle \sum_{j=1}^n \alpha_jy_j K(x_j, x_i) + b \\
\qquad K(x_1, x_2) = \langle x_1, x_2 \rangle \\
\qquad \xi \text{ : slack variable}
调整公式：
Formula 6.7
\alpha_2^{new} = \alpha_2^{old} - \frac{y_2(E_1 - E_2)}{\eta} \\
\alpha_1^{new} = \alpha_1^{old} + y_1y_2(\alpha_2^{old} - \alpha_2^{new}) \\
b_1 = b^{old} - E_1 -y_1(\alpha_1^{new} - \alpha_1^{old})K(x_1, x_1) - y_2(\alpha_2^{new} - \alpha_2^{old})K(x_1, x_2) \\
b_2 = b^{old} - E_2 -y_1(\alpha_1^{new} - \alpha_1^{old})K(x_1, x_2) - y_2(\alpha_2^{new} - \alpha_2^{old})K(x_2, x_2) \\
\begin{cases}
b_1 & \text{if } 0 \leqslant \alpha_1^{new} \leqslant C \\
b_2 & \text{if } 0 \leqslant \alpha_2^{new} \leqslant C \\
\frac{b_1 + b_2}{2} & \text{otherwise}
\end{cases} \\
\qquad E_i = u_i - y_i \\
\qquad \eta = 2K(x_1, x_2) - K(x_1, x_1) - K(x_2, x_2) \\
\qquad u_i = \textstyle \sum_{j=1}^n \alpha_jy_j K(x_j, x_i) + b \\
\qquad K(x_1, x_2) = \langle x_1, x_2 \rangle
具体证明请参照:
最后一步：解决非线性分类
根据机器学习的理论，非线性问题可以通过映射到高维度后，变成一个线性问题。
比如：二维下的一个点\(&x1, x2&\), 可以映射到一个5维空间，这个空间的5个维度分别是:\(x1, x2, x1x2, x1^2, x2^2\)。
映射到高维度，有两个问题：一个是如何映射？另外一个问题是计算变得更复杂了。
幸运的是我们可以使用核函数(Kernel function)来解决这个问题。
核函数(kernel function)也称为核技巧(kernel trick)。
核函数的思想是：
仔细观察Formula 6.6 和 Formula 6.7，就会发现关于向量\(x\)的计算，总是在计算两个向量的内积\(K(x_1, x_2) = \langle x_1, x_2 \rangle\)。
因此，在高维空间里，公式的变化只有计算低维空间下的内积\(\langle x_1, x_2 \rangle\)变成了计算高维空间下的内积\(\langle x'_1, x'_2 \rangle\)。
核函数提供了一个方法，通过原始空间的向量值计算高维空间的内积，而不用管映射的方式。
我们可以用核函数代替\(K(x_1, x_2)\)。
核函数有很多种, 一般可以使用高斯核（径向基函数（radial basis function））
Formula 6.8
K(x_1, x_2) = exp(-\frac{\lVert x_1 - x_2 \rVert ^2}{2\sigma^2})
可以通过调节\(\sigma\)来匹配维度的大小，\(\sigma\)越大，维度越低，比如10。
可以参照：
如何解决多类分类问题
支持向量机是一个二类分类器。基于SVM如何构建多类分类器，建议阅读C. W. Huset等人发表的一篇论文&A Comparison of Methods for Multiclass Support Vector Machines&。需要对代码做一些修改。
Machine Learning in Action by Peter Harrington
阅读(...) 评论()