中国科学技术大学：《信息检索与数据挖掘》课程教学资源（课件讲稿）第10章 文本分类（支持向量机及机器学习方法）

信息检索与数据挖掘 2019/4/22 1 信息检索与数据挖掘 第10章文本分类 part1:文本分类及朴素贝叶斯方法 part2:基于向量空间的文本分类 part3:支持向量机及机器学习方法

信息检索与数据挖掘 2019/4/22 1 信息检索与数据挖掘 第10章 文本分类 part1: 文本分类及朴素贝叶斯方法 part2: 基于向量空间的文本分类 part3: 支持向量机及机器学习方法

信息检索与数据挖掘 2019/4/223 本讲内容：支持向量机及机器学习方法 。支持向量机 近20年机器学习的研究产生了一 ·二元线性SVM 系列的高效分类器，如支持向量 机、提升式(boosted)决策树 、 ·SVM用于非线性分类 正则化logistic回归、神经网络和 ·机器学习方法 随机森林(random forest)等。 ·人工神经网络(Artificial Neural Network,ANN〉 ·深度学习(Deep Learning)现状 ·经典的深度学习模型/算法 ·卷积神经网络Convolutional Neural Networks(CNN ·多层反馈网络Recurrent neural Network(RNN) ·自动编码器AutoEncoder ·受限玻尔兹曼机Restricted Boltzmann Machine,RBM ·深度置信网络(Deep Belief Nets.,DBN)

信息检索与数据挖掘 2019/4/22 3 本讲内容：支持向量机及机器学习方法 • 支持向量机 • 二元线性SVM • SVM用于非线性分类 • 机器学习方法 • 人工神经网络（Artificial Neural Network, ANN） • 深度学习（Deep Learning）现状 • 经典的深度学习模型/算法 • 卷积神经网络 Convolutional Neural Networks (CNN) • 多层反馈网络 Recurrent neural Network(RNN) • 自动编码器 AutoEncoder • 受限玻尔兹曼机 Restricted Boltzmann Machine, RBM • 深度置信网络 (Deep Belief Nets，DBN） 近20 年机器学习的研究产生了一 系列的高效分类器，如支持向量 机、提升式（boosted）决策树、 正则化logistic回归、神经网络和 随机森林（random forest）等

信息检索与数据挖掘 2019/4/224 本讲内容：支持向量机及机器学习方法 。支持向量机 ·二元线性SVM ·SVM用于非线性分类 ·机器学习方法 ·人工神经网络(Artificial Neural Network,ANN) ·深度学习(Deep Learning)现状 ·经典的深度学习模型/算法 ·卷积神经网络Convolutional Neural Networks(CNN) ·多层反馈网络Recurrent neural Network(RNN) ·自动编码器AutoEncoder ·受限玻尔兹曼机Restricted Boltzmann Machine,RBM ·深度置信网络(Deep Belief Nets,DBN)

信息检索与数据挖掘 2019/4/22 4 本讲内容：支持向量机及机器学习方法 • 支持向量机 • 二元线性SVM • SVM用于非线性分类 • 机器学习方法 • 人工神经网络（Artificial Neural Network, ANN） • 深度学习（Deep Learning）现状 • 经典的深度学习模型/算法 • 卷积神经网络 Convolutional Neural Networks (CNN) • 多层反馈网络 Recurrent neural Network(RNN) • 自动编码器 AutoEncoder • 受限玻尔兹曼机 Restricted Boltzmann Machine, RBM • 深度置信网络 (Deep Belief Nets，DBN）

信息检索与数据挖掘 2019/4/225 用超平面来分割多维空间 A hyperplane is a set of the form {x alx=b),where a∈Rn,a≠0，andb∈R. A hyperplane divides Rn into two halfspaces.A (closed)halfspace is a set of the form {x aTx<b}, aTx≥b To aTx≤b aTx=b

信息检索与数据挖掘 2019/4/22 5 用超平面来分割多维空间 • A hyperplane is a set of the form {x | aTx = b}, where a ∈ Rn , a ≠ 0, and b ∈ R. • A hyperplane divides Rn into two halfspaces. A (closed) halfspace is a set of the form {x | aTx ≤ b}

信息检索与数据挖掘 2019/4/226 separating hyperplane theorem separating hyperplane theorem:Suppose C and D are two convex sets that do not intersect,i.e.,CD=0. Then there exist a0 and b such that ax b for all x ∈C and ax≥b for all x∈D. dist(C,D)=inf{lu-vll2|u∈C,v∈D} aTx≥b aTx≤b f(x)=aTx-b=(d-c)T(x-(1/2)(d+c) Source:Convex Optimization),Stephen Boyd Chapter 2 Convex sets

信息检索与数据挖掘 2019/4/22 6 separating hyperplane theorem • separating hyperplane theorem: Suppose C and D are two convex sets that do not intersect, i.e., C ∩ D = ∅. Then there exist a≠0 and b such that aTx ≤ b for all x ∈ C and aTx ≥ b for all x ∈ D. Source: 《Convex Optimization》,Stephen Boyd Chapter 2 Convex sets

信息检索与数据挖掘 2019/4/22 7 应该选哪个超平面？ ·对于线性可分的训练集而言，肯定存在无穷多个分类面可 以将两类完全正确地分开，但是不同的分类面在测试集的 表现完全迥异 ·对于新数据，有些分类器的错误率很高，有一些却很低。 如感知机：通常很差；朴素贝叶斯、Rocchio:一般；线性 SVM:好 对于二类线性可分问题存在无 穷多个能区分两类的超平面 直观的感觉是绿色的更好

信息检索与数据挖掘 2019/4/22 7 应该选哪个超平面？ • 对于线性可分的训练集而言，肯定存在无穷多个分类面可 以将两类完全正确地分开，但是不同的分类面在测试集的 表现完全迥异. . . • 对于新数据，有些分类器的错误率很高，有一些却很低。 如感知机：通常很差；朴素贝叶斯、Rocchio：一般；线性 SVM：好 对于二类线性可分问题存在无 穷多个能区分两类的超平面 直观的感觉是绿色的更好

信息检索与数据挖掘 2019/4/22 8 Distance between polyhedra The (Euclidean)distance between the polyhedra Pi ={x Aix 61}and P2 x A2x b2}in R"is defined as dist(P1,P2)=inf{lx1-x2ll2|x1∈P1,x2∈P2}. If the polyhedra intersect,the distance is zero. To find the distance between Pi and P2,we can solve the QP minimize x1-23 subject to A1x1≤b1,A2x2≤b2, with variables 1,2 ER".This problem is infeasible if and only if one of the polyhedra is empty.The optimal value is zero if and only if the polyhedra intersect, in which case the optimal xI and z2 are equal (and is a point in the intersection PiP2).Otherwise the optimal z1 and z2 are the points in Pi and P2,respectively, that are closest to each other.(We will study geometric problems involving distance in more detail in chapter 8.) Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems

信息检索与数据挖掘 2019/4/22 8 Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems

信息检索与数据挖掘 2019/4/229 分类器的间隔 •有些学习方法（如感知机）只需找到任一线性分界 面即可，而另一些方法（如NB)则需按照某个准 则找到最优的线性分界面。 ·SVM是最大间隔分类器的一种，它是基于向量空 间的机器学习方法，其目标是找到两个类别之间的 一个决策边界，使之尽量远离训练集上的任意一点 (当然一些离群点和噪音点可能不包括在内)。 ·对于SVM而言，它定义的准则是寻找一个离数据 点最远的决策面。从决策面到最近数据点的距离决 定了分类器的间隔(margin)

信息检索与数据挖掘 2019/4/22 9 分类器的间隔 • 有些学习方法（如感知机）只需找到任一线性分界 面即可，而另一些方法（如NB）则需按照某个准 则找到最优的线性分界面。 • SVM是最大间隔分类器的一种，它是基于向量空 间的机器学习方法，其目标是找到两个类别之间的 一个决策边界，使之尽量远离训练集上的任意一点 （当然一些离群点和噪音点可能不包括在内）。 • 对于SVM 而言，它定义的准则是寻找一个离数据 点最远的决策面。从决策面到最近数据点的距离决 定了分类器的间隔（margin）

信息检索与数据挖掘 2019/4/22 10 支持向量机(SVM,Support Vector Machines) 支持向量 最大间隔 SVM的目标是最大化决 决笛超平而 策超平面处的分类器间 隔(maximize the margin) SVM的决策函数通过训 练集中的支持向量 (support vectors)获 取 间隔最大化 图15-1分类器间隔两端的5个点是支持向量 Margin:分类器的间隔

信息检索与数据挖掘 2019/4/22 10 支持向量机（SVM，Support Vector Machines） •SVM的目标是最大化决 策超平面处的分类器间 隔（ maximize the margin） •SVM的决策函数通过训 练集中的支持向量 （ support vectors ）获 取 Margin: 分类器的间隔

信息检索与数据挖掘 2019/4/2211 一个SVM的例子：几何求解 ·最大间隔权重向量将和两类中距离最短的那条线段（直线）平 行，即与连接点(1,1)和(2,3)的直线平行，这可以得到权重 向量(1,2)。最优的分类直线与上述线段垂直并相交与其中 点（中垂线），因此它经过点(1.5,2)。 X2=-0.5x1+2.75 于是，SVM的决策方程为： y=x1+2x2-5.5 y>0属于一类 y<0属于另一类

信息检索与数据挖掘 2019/4/22 11 一个SVM的例子：几何求解 • 最大间隔权重向量将和两类中距离最短的那条线段(直线)平 行，即与连接点(1, 1)和(2, 3)的直线平行，这可以得到权重 向量 (1,2)。最优的分类直线与上述线段垂直并相交与其中 点(中垂线)，因此它经过点 (1.5, 2)。 x2 = - 0.5x1 + 2.75 于是，SVM的决策方程为： y = x1 + 2x2 − 5.5 y > 0 属于一类 y < 0 属于另一类