1、原理与应用大纲 背景 线性分类 非线性分类 松弛变量 多元分类 应用 工具包2大纲 背景背景 线性分类线性分类 非线性分类非线性分类 松弛变量松弛变量 多元分类多元分类 应用应用 工具包工具包3背景 支持向量机 4为什么要用(个人观点)分类效果好 上手快 种语言的个 理论基础完备 妇孺皆知的好模型 找工作需要它(利益相关：面试狗一只)应用与原理5发展历史 重要理论基础 年代，和提出维理论 重要理论基础 年，提出结构风险最小化理论 支持向量机()是和于年首先提出的 它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中6作者之一简介 作者 书中详
2、细的论证了统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。7理论基础（比较八股）统计学习理论的维理论(或)是研究有限样本情况下机器学习规律的理论()反映了函数集的学习能力，维越大则学习机器越复杂8理论基础（比较八股）结构风险最小化 机器学习本质上就是一种对问题真实模型的逼近。这个与问题真实解之间的误差，就叫做风险。结构化风险 经验风险 置信风险 经验风险 分类器在给定样本上的误差 置信风险 分类器在未知文本上分类的结果的误差，代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。（无法准确估值，给出估计的区间）9理
3、论基础（比较八股）结构化风险 经验风险 置信风险 置信风险因素：样本数量，给定的样本数量越大，学习结果越有可能正确，此时置信风险越小；分类函数的维，显然维越大，推广能力越差，置信风险会变大。泛化误差界的公式*()()()公式中()就是真实风险，()就是经验风险，()就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。10理论基础（小结）统计学习理论的维理论 关注的是维 结构风险最小化()()()11特性 小样本 与问题的复杂度比起来，算法要求的样本数是相对比较少的 非线性 擅长应付样本数据线性不可分的情况，主要通过松弛变量和核函数技术来实现 高维模
4、式识别 例如文本的向量表示，几万维，反例:12大纲 背景 线性分类 非线性分类 松弛变量 多元分类 应用 工具包13线性分类器 问题的引入 和是两类样本 中间的直线就是一个分类函数，它可以将两类样本完全分开。14线性函数？在一维空间里就是一个点 在二维空间里就是一条直线 在三维空间里就是一个平面 如果不关注空间的维数，这种线性函数还有一个统一的名称超平面()15线性函数分类问题 例如我们有一个线性函数()我们可以取阈值为，这样当有一个样本需要判别的时候，我们就看()的值。若()，就判别为类别 若()，而也大于 反之，而也小于 现在把和进行一下归一化，即用和分别代替原来的和，那么间隔就可以写成2
5、0分类间隔几何间隔 解析几何中点到直线()的距离公式 推广一下，是到超平面()的距离，()就是上节中提到的分类超平面 是什么符号？叫做向量的范数，向量长度其实指的是它的范数 用归一化的和代替原值之后的间隔有一个专门的名称，叫做几何间隔21量化问题之“支持向量”被红色和蓝色的线圈出来的点就是所谓的支持向量()22量化问题之“最大化间隔”原则 就是()，红色和蓝色的线（与）就是 所在的面，红色、蓝色线之间的间隔就是我们要最大化的分类间的间隔。23量化问题之“最大化间隔”原则 几何间隔24几何间隔的现实含义 是分类面，而和是平行于，且过离最近的两类样本的直线，与，与之间的距离就是几何间隔25几何间隔
6、的存在意义 几何间隔与样本的误分次数间存在关系 其中的是样本集合到分类面的间隔，即是所有样本中向量长度最长的值（也就是说代表样本的分布有多么广）误分次数一定程度上代表分类器的误差。（证明略）误分次数的上界由几何间隔决定（样本已知的时候）26 为了使分类面更合适 为了减少误分次数 最大化几何间隔27 是否让，目标函数就最小了呢？。式子有还有一些限制条件，完整的写下来，应该是这样的 求最小值的问题就是一个优化问题，一个带约束的二次规划(,)问题，是一个凸问题 凸二次规划区别于一般意义上的规划问题，它有解而且是全局最优的解，而且可以找到28如何解二次规划问题 等式约束，是求极值、拉格朗日转化等方法转
7、化为无约束问题 不等式约束的问题怎么办？方法一：用现成的()优化包进行求解(效率低)方法二：求解与原问题等价的对偶问题()得到原始问题的最优解(更易求解、可以推广到核函数)拉格朗日乘子法 拉格朗日对偶性 理论支撑29求解步骤 转化为对偶问题 对偶转化 条件 求解极小化 拉格朗日乘子极值 求解极大化 用算法求解乘子30、对偶问题的转化、对偶问题的转化给每一个约束条件加上一个拉格朗日乘子（给每一个约束条件加上一个拉格朗日乘子（），定义拉格朗），定义拉格朗日函数日函数根据对偶算法与条件约束，这个问题可以从根据对偶算法与条件约束，这个问题可以从转化为转化为其中其中*和和*等价条件就是条件等价条件就是条
8、件*31、的极小化、的极小化 那么问题转化为那么问题转化为 先固定先固定，求的最小值，求的最小值 将以上结果代入之前的，将以上结果代入之前的，得到只含得到只含的优化结果的优化结果32、的极大化的极大化 优化问题接上一步处理结果优化问题接上一步处理结果 如果求出了如果求出了*，那么和就可以随之求解，那么和就可以随之求解 最终得出分离超平面和分类决策函数。最终得出分离超平面和分类决策函数。那么有什么好方法求那么有什么好方法求呢？呢？33、利用算法求解对偶问题中的拉格朗日乘子、利用算法求解对偶问题中的拉格朗日乘子 优化问题接上一步处理结果优化问题接上一步处理结果 上述式子要解决的是在参数上述式子要解
9、决的是在参数上求最大值的问题，至于都上求最大值的问题，至于都是已知数是已知数 算法算法(略略)34 表达式的感性分析(番外篇)线性函数表达式为 ()样本确定了，用数学的语言描述，就是可以表示为样本的某种组合 同时不仅跟样本点的位置有关，还跟样 本的类别有关（也就是和样本的“标签”有关）。因此用下 面这个式子表示才算完整：35分类函数的预测 将的表达式带入分类函数后 对于新点 的预测，只需要计算它与训练数据点的内积即可（表示向量内积）所有非 所对应的系数都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。36大纲 背景 线性分类 非线性分类 松弛变量 多
10、元分类 应用 工具包37非线性分类问题的引入我们把横轴上端点和之间红色部分里的所有点定为正类，两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么？不能，因为二维空间里的线性函数就是指直线，显然找不到符合条件的直线。38非线性分类问题的引入 显然通过点在这条曲线的上方还是下方就可以判断点所属的类别39非线性分类问题的引入 这条曲线就是我们熟知的二次曲线，它的函数表达式可以写为：它不是一个线性函数，但是，我们可以新建一个向量和：这样()就可以转化为()40非线性分类问题的引入 原先问题是：转化后的问题：在任意维度的空间中，这种形式的函数都是一个线性函数 原来在二维空间中一个线性不
11、可分的问题，映射到四维空间后，变成了线性可分的。解决线性不可分问题的基本思路向高维空间转化(这种特征变换称作特征映射()，使其变得线性可分。41核函数例子引入 我们文本分类问题的原始空间是维的，在这个维度上问题是线性不可分的。现在我们有一个维空间里的线性函数 式中的 和 都是维的向量，只不过 是定值，而 是变量 现在我们的输入，是一个维的向量，分类的过程是先把变换为维的向量 ，然后求这个变换后的向量 与向量的内积，再把这个内积的值和相加，就得到了结果，看结果大于阈值还是小于阈值就得到了分类结果。42核函数例子引入我们其实只关心那个高维空间里内积的值，那个值算出来了，分类结果就算出来了。是否能有
12、这样一种函数(),他接受低维空间的输入值，却能算出高维空间的内积值？如果有这样的函数，那么当给了一个低维空间的输入以后：这两个函数的计算结果就完全一样，我们也就用不着费力找那个映射关系，直接拿低维的输入往()里面代就可以了43 假设映射函数是 我们要将 映射为 那么定义核函数（）为 如果要实现该节开头的效果，只需先计算 ，然后计算 即可，然而这种计算方式是非常低效的。比如最初的特征是维的，我们将其映射到维，然后再计算，这样需要()的时间。那么我们能不能想办法减少计算时间呢?核函数形式化定义44核函数 这样的()确实存在。它被称作核函数()，而且还不止一个 事实上，只要是满足了条件*的函数，都可
13、以作为核函数。核函数的基本作用就是接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。45核函数例子 假设和都是维的 展开后，得 我们可以只计算原始特征和内积的 平方，时间复杂度是()，就等价与计 算映射后特征的内积。也就是说我们不 需要花时间()了46核函数例子 核函数 对应的映射函数（时）是47核函数举例高斯核 如果和很相近()，那么核函数值为，如果和相差很大()，那么核函数值约等于。由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数(简称)。它能够把原始特征映射到无穷维。48核函数举例高斯核49核函数举例核既然高斯核函数能够比较和的相似度，并映射到到
14、，回想回归，函数可以，因此还有核函数等等。50核函数举例多项式核刚才我们举的例子是这里多项式核的一个特例（，）。虽然比较麻烦，而且没有必要，不过这个核所对应的映射实际上是可以写出来的。51核函数举例线性核 这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来52核函数小结 我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去 如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的 核函数就隆重登场了，核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝
15、在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算53核函数分类效果图 篱笆部署问题54核函数还有什么值得我们注意的 既然有很多的核函数，针对具体问题该怎么选择？对核函数的选择，现在还缺乏指导原则 如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么办？松弛变量55大纲 背景 线性分类 非线性分类 松弛变量 多元分类 应用 工具包56问题的引入 现在我们已经把一个本来线性不可分的文本分类问题，通过映射到高维空间而变成了线性可分的57问题的引入 圆形和方形的点各有成千上万个，现在想象我们有另一个样本点，但是这个样本的位置是这样
16、的：58近似线性可分问题 就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）叫做“近似线性可分”的问题。59的处理分析 有一万个点都符合某种规律（因而线性可分），有一个点不符合，那这一个点是否就代表了分类规则中我们没有考虑到的方面呢 更有可能的是，这个样本点压根就是错误，是噪声，是提供训练集的同学人工分类时一打瞌睡错放进去的。所以我们会简单的忽略这个样本点，仍然使用原来的分类器，其效果丝毫不受影响。60硬间隔分类问题 由于我们原本的优化问题的表达式中，确实要考虑所有的样本点（不能忽略某一个，
17、因为程序它怎么知道该忽略哪一个呢？），在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。61如何评价硬间隔分类 硬间隔的分类法其结果容易受少数点的控制，这是很危险的 解决方法：允许一些点到分类平面的距离不满足原先的要求62松弛变量的引入意思是说离分类面最近的样本点函数间隔也要比大。如果要引入容错性，就给这个硬性的阈值加一个松弛变量，即允许因为松弛变量是非负的，因此最终的结果是要求间隔可以比小63松弛变量 值的确定 当某些点出
18、现这种间隔比小的情况时（这些点也叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失 但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类边界也更平滑）64松弛变量 优化问题 我们原始的硬间隔分类对应的优化问题 我们要把松弛变量加入到优化问题中，即将损失越小越好65软间隔分类器 如果是 ，则为二阶软间隔分类器 如果是 ，则为一阶软间隔分类器66惩罚因子 惩罚因子 把损失加入到目标函数里的时候，就需要一个惩罚因子（，也就是中工具包中的参数）67松弛变量惩罚因子的几点说明 并非所有的样本点都有一个松弛变量与其对
19、应。实际上只有“离群点”才有，没离群的点松弛变量都等于 松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远 惩罚因子决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，你定的越大，对目标函数的损失也越大 惩罚因子不是一个变量，整个优化问题在解的时候，是一个事先指定的值68核函数 松弛变量 相同点：都是解决线性不可分问题的 不同点：在原始的低维空间中，样本相当的不可分，无论你怎么找分类平面，总会有大量的离群点，此时用核函数向高维空间映射一下，虽然结果仍然是不可分的，但比原始空间里的要更加接近线性可分的状态 达到了近似线性可分的状态后，此时再用松弛变量处理那些少
20、数“冥顽不化”的离群点69的运用：数据集偏斜()它指的是参与分类的两个类别（也可以指多个类别）样本数量差异很大。比如说正类有个样本，而负类只给了个70数据集偏斜()方形的点是负类。，是根据给的样本算出来的分类面 两个灰色点有提供的话，那算出来的分类面应该是，和 负类给的样本点越多，就越容易出现在灰色点 附近的点，我们算出的 结果也就越接近于真实 的分类面。71问题的解决方法()惩罚因子，那就是给样本数量少的负类更大的惩罚因子，表示我们重视这部分样本72问题的解决方法()不一定是样本少，还可能是分布不够广“政治类”“体育类”文本分类，体育类集中在“篮球”领域 比如可以算算他们在空间中占据了多大的
21、体积，例如给负类找一个超球，它可以包含所有负类的样本，再给正类找一个，比比两个球的半径，就可以大致确定分布的情况 但是有些领域分布的确不够广，比如“高考作文”“语言类”73问题的解决方法 简单的就是美的 在解决偏斜问题的时候用的是方案一，样本数量的比 的初始值根据参数调优计算出来 咱们先假定说是这么大，就可以定为这么大（：）74大纲 背景 线性分类 非线性分类 松弛变量 多元分类 应用 工具包75多元分类 是一种典型的两类分类器，即它只回答属于正类还是负类的问题 而现实中要解决的问题，往往是多类的问题 如何由两类分类器得到多类分类器，就是一个值得研究的问题76方案一：一次求解个分类面 一次性考
22、虑所有样本，并求解一个多目标函数的优化问题，一次性得到多个分类面 可惜这种算法还基本停留在纸面上，因为一次性求解的方法计算量实在太大，大到无法实用的地步77方案二：一类对其余 一类对余类法(，)构造类别数个的二元分类器 训练时第个分类机取训练集中第类为正类，其余类别点为负类 判别时，输入信号分别经过个分类器输出 优点 每个优化问题的规模比较小，而且分类的时候速度很快 缺点 分类重叠 不可分类 人为的数据偏斜78方案三：一对一 该方法在每两类问训练一个分类器，因此对于一个类问题，将有()个分类器 优点 避免了数据偏斜 训练阶段（也就是算出这些分类器的分类平面时）所用的总时间却比“”方法少很多 投
23、票时也会有分类重叠的现象，但不会有不可分类现象 缺点 类别数为的时候，我们调用了个分类器，类别数如果是，要调用的分类器数目会上升至约个（但是时间上可能还是比少，因为考虑的样本数少）79方案四：方法(有向无环图)是针对存在误分现象提出的 这种方法的()个分类器，构成一个有向无环图。该有向无环图中含有()个内部节点和个叶结点，每个节点对应一个二类分类器80方案四：方法(有向无环图)优点 简单易行，只需要使用个决策函数即可得出结果，较“一对一方法提高了测试速度，而且不存在误分、拒分区域 由于其特殊的结构，故有一定的容错性，分 类精度较一般的二叉树 方法高 缺点 误差积累81方案四：方法(有向无环图)
24、的错误累积 错误累积在一对其余和一对一方法中也都存在，方法好于它们的地方就在于，累积的上限，不管是大是小，总是有定论的，有理论证明 而一对其余和一对一方法中，尽管每一个两类分类器的泛化误差限是知道的，但是合起来做多类分类的时候，误差上界是多少 方法根节点的选取 我们就总取在两类分类中正确率最高的那个分类器作根节点 置信度最大的路径82其他方案：决策树、决策树方法 纠错输出编码法()*维编码矩阵 类别判定用汉明距离83大纲 背景 线性分类 非线性分类 松弛变量 多元分类 应用 工具包84的应用 文本分类(下页详谈)图像处理 图像过滤、图片分类与检索 生物信息技术 蛋白质分类 语音识别 人脸检测、
25、指纹识别 手写字体识别 网络入侵检测、口令认证、网页分类 85的文本分类应用 例:分类 万条微信数据，个类别。条测试数据，其余数据为训练数据。分类 句微博，个类别。句测试数据，其余数据训练。省略恢复“小明买了苹果，很甜。”86大纲 背景 线性分类 非线性分类 松弛变量 多元分类 应用 工具包87工具包 88简介 是林智仁()教授开发 可以很方便的对数据做分类或回归 程序小，运用灵活，输入参数少，并且是开源的，易于扩展，因此成为目前国内应用最多的的库 (,)89工具包 工具包组成(一个可视化的工具,用来展示训练数据和分类界面,里面是源码,其编译后的程序在文件夹下)(四个文件,用来数据集抽样(),
26、参数优选(),集成测试(),数据检查()(包含四个程序包)其他 源码90工具包常用命令 91模型文件92源码数据结构举例 93源码数据结构举例 调用的94 线性分类器 主要为大规模数据的线性模型设计 由于采用线性核,所以不需要计算,速度更快 缺点就是太吃内存了。的数据量需要接近的内存，数据量再大就没法做了 95什么时候用 当你面对海量的数据时，这里的海量通常是百万级别以上 海量数据分为两个层次：样本数量和特征的数量。使用线性和非线性映射训练模型得到相近的效果 对模型训练的时间效率要求较高96高效分类的理论基础 是个优化的框架，*它是先确定一个()，或者说先确定它的半径(因为球心就是)，然后在此
27、球内优化泰勒展式的局部模型(一般都是二阶)寻找方向，如果优化成功则球心转移，并扩大半径；如果不成功则球心不变，缩小半径。并如此反复。（区别于 先确定后优化）97高效分类的理论基础 是指牛顿法中计算*时采用数值迭代解决这个线性系统问题而不是直接高斯消元，其中和分别是目标函数的一阶导和二阶导。通常情况下，这里可以用共轭梯度的近似解来逼近。98 康奈尔大学 对计算机硬件的性能要求比要低 99 是一个开源的短文本(包括标题、短信、问题、句子等)分类工具包 它在的基础上针对短文本进一步优化，主要特性有：直接输入文本，无需做特征向量化的预处理 二元分词（），去停顿词，做词性过滤 基于线性核分类器 提供了完整的，用于特征分析和 检验100 格式 检验 特征分析101 缺点 不支持中文，需要替换分词器102总结背景历史、宏观的理论基础与优点线性分类分类面、间隔最大化、对偶问题求解参数非线性分类问题的提出、核函数定义、举例、对比松弛变量离群点、软间隔、松弛变量、惩罚因子、数据集偏斜问题多元分类多元分类的种方法应用在、图像、网络等方面的分类应用工具包、103参考 系列、资源推荐 林智仁机器学习讲义 讲义 刘家峰模式识别104谢谢105
