SVM背景介绍,什么是线性分类和非线性分类,松弛变量,多元分类,具体应用和相关的工具包。

注脚

1.SVM 原理与应用 HITSCIR-TM Group zkli - 李泽魁

2.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 2

3.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 3

4.SVM 背景 支持向量 机 support vector machine SVM 4

5.为什么要用 SVM( 个人观点 ) 分类效果好 上手快 N 种语言的 N 个 Toolkit 理论基础完备 妇孺皆知的好模型 找工作需要它 ( 利益相关 :面试狗一只 ) 应用与原理 5

6.SVM 发展历史 重要理论 基础 1 60 年代, Vapnik 和 Chervonenkis 提出 VC 维理论 重要理论基础 2 1982 年, Vapnik 提出 结构风险最小化 理论 支持 向量机 (Support Vector Machine) 是 Cortes 和 Vapnik 于 1995 年首先提出 的 它在解决 小样本 、 非线性 及 高维模式识别 中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题 中 6

7.作者之一简介 Vapnik 《Statistical Learning Theory 》 作者 书中详细的论证了 统计机器学习 之所以区别于传统机器学习的本质,就在于统计机器学习能够精确的给出学习效果,能够解答需要的样本数等等一系列问题。 7

8.SVM 理论 基础 1 (比较八股) 统计 学习理论 的 VC 维 理论 (Statistical Learning Theory 或 SLT ) 是 研究有限样本情况下机器学习规律的 理论 ( Vapnik-Chervonenkis Dimension) 反映 了函数集的学习能力, VC 维 越大则学习机器越 复杂 8

9.SVM 理论 基础 2 (比较八股) 结构风险最小化 机器学习本质 上就是 一种对问题真实模型的 逼近。这个与问题真实解之间的误差,就叫做 风险 。 结构化风险 = 经验风险 + 置信风险 经验风险 =  分类器在给定样本上的误差 置信风险 = 分类器在未知文本上分类的结果的 误差,代表 了我们在多大程度上可以信任分类器在未知文本上分类的结果。(无法准确估值,给出估计的区间) 9

10.SVM 理论 基础 2 (比较八股) 结构化风险 = 经验风险 + 置信风险 置信风险因素: 样本数量,给定的样本数量越大,学习结果越有可能正确,此时置信风险越小; 分类函数的 VC 维,显然 VC 维越大,推广能力越差,置信风险会变大。 泛化误差界的 公式* R(w)≤ R emp (w)+ Ф( n/h) 公式中 R(w) 就是真实风险, Remp (w) 就是经验风险, Ф(n/h) 就是置信风险 。 统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险最小。 10

11.SVM 理论 基础(小结) 统计学习理论的 VC 维 理论 SVM 关注的是 VC 维 结构风险最小化 R(w )≤ R emp (w)+ Ф( n/h) 11

12.SVM 特性 小 样本 与问题的复杂度比起来, SVM 算法要求的样本数是相对比较少的 非线性 SVM 擅长应付样本数据线性不可分的情况,主要通过 松弛变量和 核函数技术来实现 高维 模式识别 例如文本的向量 表示,几万维,反例 : KNN 12

13.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 13

14.线性分类器 问题的引入 X 和 O 是两类样本 中间的直线就是一个分类函数,它可以将两类样本完全分开。 14

15.线性 函数? 在一维空间里就是一个 点 在二维空间里就是一条 直线 在 三维空间 里就是一个 平面 …… 如果不关注空间的维数,这种线性函数还有一个统一的名称 —— 超平面 (Hyper Plane) 15

16.线性 函数  分类问题 例如我们有一个线性 函数 g(x)= wx+b 我们可以取阈值为 0 ,这样当有一个样本 x i 需要判别的时候,我们就看 g(x i ) 的值 。 若 g(x i )>0 ,就判别为 类别 O 若 g(x i )<0 ,则判别为 类别 X Tips w 、 x 、 b 均可以是向量 中间那条直线的表达式是 g(x)=0 ,即 wx+b =0 ,我们也把这个函数叫做分类 面 16

17.分类面的决定 分离超平面不是 唯一 上面 的 N 直线 都可以对点正确 分类 分离超平面存在一个最好 的 17

18.分类 面的“好坏”量化 一个很直观的感受是, 让“离直线最近的点,距离直线尽可能地远” 就是 分割的间隙越大越好,把两个类别的点分得 越开越好 18

19.“分类间隔”的引入 文本分类分类时样本格式 label ( 标示出这个样本属于哪个类别 ) feature (文本 特征所组成的向量 ) 假设 label=±1 ,我们就可以 定义 一个样本点到某个超平面的 间隔为 ( 这是定义 ) δ i = y i ( wx i +b ) 19 ^

20.分类间隔 δ i = y i ( wx i +b ) y i ( wx i +b ) 总大于 0 的,而且它的 值等于 | wx i +b | 如果某个样本属于该类别 的话, wx i +b >0 , 而 y i 也大于 0 反之, wx i +b <0 ,而 y i 也小于 0 现在把 w 和 b 进行一下归一化,即用 w/||w|| 和 b/||w|| 分别代替原来的 w 和 b ,那么间隔就可以写 成 20 ^

21.分类 间隔  几何间隔 解析几何中点 x i 到直线 g(x)=0 的距离 公式 推广一下,是到超平面 g(x)=0 的距离, g(x)=0 就是上节中提到的分类 超平面 ||w|| 是什么符号? ||w|| 叫做向量 w 的 范数, 向量 长度 其实指的是它的 2- 范数 用归一化的 w 和 b 代替原值之后的间隔有一个专门的名称,叫做 几何间隔 21

22.量化问题之“支持向量” 被红色和蓝色的线圈出来的点就是所谓的支持向量 (support vector ) 22

23.量化问题之“最大化间隔” Maximum Marginal 原则 Classifier Boundary 就是 f(x) ,红色和蓝色的线( plus plane 与 minus plane )就是 support vector 所在的面,红色、蓝色线之间 的 间隔 就是 我们要最大化的分类间 的间隔。 23

24.量化问题之“最大化间隔” Maximum Margin 原则 几何间隔 24

25.几何间隔的现实含义 H 是分类面,而 H 1 和 H 2 是平行于 H ,且过离 H 最近的两类样本的直线, H 1 与 H , H 2 与 H 之间的距离就是几何 间隔 25

26.几何间隔 的存在意义 几何间隔与样本的误分次数间存在 关系 其中的 δ 是样本集合到分类面的间隔, R=max ||xi||  i =1,...,n ,即 R 是所有样本 中向量 长度最长的值(也就是说代表样本的分布有多么广 ) 误分 次数一定程度上代表分类器的误差 。(证明略) 误 分次数的上界由几何间隔 决定(样本 已知的时候) 26

27.Maximum Margin 为了使分类面更合适 为了减少误分次数 最大化几何间隔 27

28.minimize ||w|| 是否让 W=0 ,目标函数就最小了呢? = 。 = 式子有还有一些限制条件,完整的写下来,应该是这样 的 求最小值的问题就是一个优化 问题,一 个带约束的二次规划 (quadratic programming, QP) 问题,是一个凸 问题 凸二次规划区别于一般意义上的规划问题, 它有 解而且是 全局最优的解 ,而且 可以找到 28

29.如何解二次规划问题 等式约束,是求极值、拉格朗日转化等方法转化为无约束问题 不等式约束 的 问题怎么办? 方法 一 :用 现成的 QP (Quadratic Programming) 优化包进行 求解 ( 效率低 ) 方法 二:求解与原问题等价的对偶 问题 (dual problem) 得到 原始问题的 最优解 ( 更易求解、可以推广到核函数 ) 拉格朗日乘子法 拉格朗日对偶性 KKT 理论支撑 29

30.求解步骤 转化为对偶问题 对偶转化 & KKT 条件 求解 wb 极小化 拉格朗日乘子极值 求解 α 极 大化 用 SMO 算法求解 α 乘子 30

31.1 、对偶问题的转化 给每一个约束条件加上一个拉格朗日乘子( Lagrange multiplier ),定义 拉格朗日函数 根据对偶算法与 KKT 条件约束,这个问题可以从 转化为 其中 p *和 d *等价条件就是 KKT 条件 * 31

32.2 、 wb 的极小化 那么问题转化为 先固定 α ,求 wb 的最小值 将以上结果代入之前的 L , 得到只含 α 的优化结果 32

33.3 、 α 的 极 大化 优化问题接上一步处理结果 如果求出了 α *,那么 w 和 b 就可以随之求解 最终得出分离超平面和分类 决策函数。 那么有什么好方法求 α 呢? 33

34.3 、利用 SMO 算法求解对偶问题中的 拉格朗日乘子 α 优化问题接上一步处理结果 上述式子要解决的是在 参数 α i 上 求最大 值的 问题, 至于 xy 都是已知数 SMO 算法 ( 略 ) 34

35. 表达式的感性分析 ( 番外篇 ) 线性函数 表达式为 g(x )=< w,x >+b 样本 确定了 w ,用数学的语言描述,就是 w 可以表示为样本的某种 组合 w=α1x1+α2x2+…+ α nxn 同时 w 不仅跟样本点的位置有关,还跟 样 本的 类别有关(也就是和样本的“标签”有关)。因此用 下 面 这个式子表示才算完整 : w= α 1 y 1 x 1 + α 2 y 2 x 2 +…+ α n y n x n   35

36.分类函数的预测 将w的表达式带入分类函数后 对于新点 x的预测,只需要计算它与训练数据点的内积即可(表示向量内积) 所有非Supporting Vector 所对应的系数 都 α i 是 等于零的,因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。 36

37.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 37

38.非线性分类——问题的引入 我们把横轴上端点a和b之间红色部分里的所有点定为正类,两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么?不能,因为二维空间里的线性函数就是指直线,显然找不到符合条件的直线。 38

39.非线性分类——问题的引入 显然通过点在这条曲线的上方还是下方就可以判断点所属的类别 39

40.非线性分类——问题的引入 这条曲线就是我们熟知的二次曲线,它的函数表达式可以写为: 它不是一个线性函数,但是,我们可以新建一个向量y和a: 这样g(x)就可以转化为f(y)=<a,y> 40

41.非线性分类——问题的引入 原先问题是: 转化后的问题: 在 任意维度的空间中,这种形式的函数都是一个线性函数 原来在二维空间中一个线性不可分的问题,映射到四维空间后,变成了线性可分的。 解决 线性不可分问题的基本思路——向高维空间 转化 ( 这种特征变换称作特征映射 (feature mapping)) ,使 其变得线性可分。 41

42.核函数——例子引入 我们文本分类问题的原始空间是1000维 的 , 在 这个维度上问题是线性不可分的。现在我们有一个2000维空间里的线性 函数 式中的 w ’ 和x ’ 都是 2000维的向量,只不过 w ’ 是 定值,而 x ’ 是变量 现在我们的输入,是一个1000维的向量x,分类的过程是先把x变换为2000维的向量 x ’ , 然后求这个变换后的向量 x ’ 与 向量 w ’ 的 内积,再把这个内积的值和b相加,就得到了结果,看结果大于阈值还是小于阈值就得到了分类结果。 42

43.核函数——例子引入 我们 其实只关心那个高维空间里内积的值,那个值算出来了,分类结果就算出来了。 是否能有这样一种函数K(w,x),他接受低维空间的输入值,却能算出高维空间的内积 值 < w ’ ,x ’ > ? 如果有这样的函数,那么当给了一个低维空间的输入x以后: 这两个函数的计算结果就完全一样,我们也就用不着费力找那个映射关系,直接拿低维的输入往g(x)里面代就可以了 43

44.假设 映射函数是 我们要将 映射为 那么定义核函数( Kernel ) 为 如果 要实现该节开头的效果,只需先 计算 , 然后 计算 即 可,然而这种计算方式是非常低效的 。 比如 最初的特征是 n 维的,我们将其映射 到 n^2 维 ,然后再计算,这样 需要 O(n^2) 的 时间。那么我们能不能想办法减少计算时间 呢 ? 核函数 —— 形式化定义 44

45.核函数 这样的K(w,x)确实存在。它被称作 核函数 ( kernel ) , 而且还不止一 个 事实上,只要是满足了Mercer 条件 * 的 函数,都可以作为核函数。 核函数的基本作用就是接受两个低维空间里的向量,能够计算出 经过某个变换 后在 高维空间里 的 向量内积值 。 45

46.核函数 —— 例子 1 假设 x 和 z 都是 n 维的 展开 后, 得 我们可以只计算原始特征 x 和 z 内积 的 平方 , 时间 复杂度是 O(n ) , 就等价与 计 算 映射后特征的内积。也就是说我们 不 需要 花 时间 O(n^2) 了 46

47.核函数 —— 例子 2 核函数 对应的映射函数( n=3 时) 是 47

48.核函数举例 1—— 高斯核 如果 x 和 z 很 相近 ( ) , 那么核函数值为 1 ,如果 x 和 z 相差 很大 ( ) , 那么核函数值约等于 0 。 由于 这个函数类似于高斯分布,因此称为高斯核函数,也叫做径向基函数 (Radial Basis Function 简称 RBF) 。 它 能够把原始特征映射到无穷维。 48

49.核函数举例 1—— 高斯核 49

50.核函数 举例 2——sigmoid 核 既然高斯核函数能够比较 x 和 z 的相似度,并映射到 0 到 1 ,回想 logistic 回归, sigmoid 函数 可以,因此 还有 sigmoid 核函数等等。 50

51.核函数举例 3—— 多项式核 刚才我们举的例子是这里多项式核的一个特例( R = 0 , d = 2 ) 。 虽然 比较麻烦,而且没有必要,不过这个核所对应的映射实际上是可以写出来 的 。 51

52.核函数 举例 4—— 线性核 这实际上就是原始空间中的内积 。 这个 核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一 起来 52

53.核函数小结 我们会经常遇到线性不可分的样例,此时,我们的常用做法是把样例特征映射到高维空间中 去 如果凡是遇到线性不可分的样例,一律映射到高维空间,那么这个维度大小是会高到可怕 的 核函数就隆重登场了,核函数的价值在于它虽然也是讲特征进行从低维到高维的转换,但核函数绝就绝在它事先在低维上进行计算,而将实质上的分类效果表现在了高维上,也就如上文所说的避免了直接在高维空间中的复杂计算 53

54.核函数分类效果图 篱笆部署问题 54

55.核函数还有什么值得我们注意的 既然有很多的核函数,针对具体问题该怎么选择 ? 对核函数的选择,现在还缺乏指导 原则 如果使用核函数向高维空间映射后,问题仍然是线性不可分的,那怎么办 ? 松弛变量 55

56.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 56

57.问题的引入 现在我们已经把一个本来线性不可分的文本分类问题,通过映射到高维空间而变成了线性可分 的 57

58.问题的引入 圆形和方形的点各有成千上万 个, 现在想象我们有 另一个样 本点,但是这个样本的位置是这样的: 58

59.近似线性可分问题 就是 图中 黄色那个点 , 它 是方形的,因而它是负类的一个样本,这单独的一个样本,使得原本线性可分的问题变成了线性不可分的。这样类似的问题(仅有少数点线性不可分)叫做“ 近似线性可分 ”的问题 。 59

60.Outlier 的处理分析 有一万个点都符合某种规律(因而线性可分),有一个点不符合,那这一个点是否就代表了分类规则中我们没有考虑到的方面 呢 更有可能的是,这个样本点压根就是错误,是噪声,是提供训练集的同学人工分类时一打瞌睡错放进去的。所以我们会简单的忽略这个样本点,仍然使用原来的分类器,其效果丝毫不受影响。 60

61.硬间隔分类问题 由于我们原本的优化问题的表达式中,确实要考虑所有的样本点(不能忽略某一个,因为程序它怎么知道该忽略哪一个呢?),在此基础上寻找正负类之间的最大几何间隔,而几何间隔本身代表的是距离,是非负的,像上面这种有噪声的情况会使得整个问题无解 。 这种 解法其实也叫做“ 硬间隔 ”分类法,因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。 61

62.如何评价硬间隔分类 硬间隔的分类法其结果容易受少数点的控制,这是很危险 的 解决 方法: 允许一些点到分类平面的距离不满足原先的 要求 62

63.松弛变量的引入 意思是说离分类面最近的样本点函数间隔也要比 1 大。如果要引入容错性,就给 1 这个 硬性的 阈值加一个松弛变量,即 允许 因为松弛变量是非负的,因此最终的结果是要求间隔可以比 1 小 63

64.松弛变量 值的确定 当某些点出现这种间隔比 1 小的情况时(这些点也叫离群点),意味着我们放弃了对这些点的精确分类,而这对我们的分类器来说是种 损失 但是放弃这些点也带来了好处,那就是使分类面不必向这些点的方向移动,因而可以得到更大的几何间隔(在低维空间看来,分类边界也更平滑) 64

65.松弛变量 vs 优化问题 我们原始的硬间隔分类对应的优化 问题 我们要把松弛变量加入到优化问题中,即将损失越小越好 65

66.软间隔分类器 如果是 ,则为 二阶软间隔 分类器 如果是 ,则为 一阶软间隔分类器 66

67.惩罚因子 C 惩罚 因子 C 把 损失加入到目标函数里的时候,就需要一个惩罚因子( cost , 也就是 N 中工具包中的参数 C ) 67

68.松弛变量 & 惩罚因子的几点说明 并非 所有的样本点都有一个松弛变量与其对应。实际上只有“离群点” 才有,没 离群的点松弛变量都等于 0 松弛变量的值实际上标示出了对应的点到底离群有多远,值越大,点就越 远 惩罚因子 C 决定了你有多重视离群点带来的损失,显然当所有离群点的松弛变量的和一定时,你定的 C 越大,对目标函数的损失也越 大 惩罚 因子 C 不是一个变量,整个优化问题在解的时候, C 是一 个事先 指定的值 68

69.核函数 vs 松弛变量 相同点: 都是解决线性不可分问题的 不同点: 在原始的低维空间中,样本相当的不可分,无论你怎么找分类平面,总会有大量的离群点,此时用核函数向高维空间映射一下,虽然结果仍然是不可分的,但比原始空间里的要更加接近线性可分的 状态 达到 了近似线性可分的 状态后, 此时再用松弛变量处理那些少数“冥顽不化”的离群 点 69

70.C 的运用:数据 集 偏斜 (unbalanced ) 它指的是参与分类的两个类别(也可以指多个类别)样本数量差异很大。比如说正类有 10000 个样本,而负类只给了 100 个 70

71.数据集偏斜 (unbalanced) 方形的点是负类。 H , H1 , H2 是根据给的样本算出来的分类 面 两 个灰色点 有提供的话,那算出来的分类面应该是 H’ , H2’ 和 H1 负类给的样本点越多 , 就 越容易出现在灰色 点 附近 的点,我们算出 的 结果 也就越接近于 真实 的 分类面。 71

72.unbalanced 问题的解决方法 (1) 惩罚 因子,那 就是给样本数量少的负类更大的惩罚因子,表示我们重视这部分 样本 72

73.unbalanced 问题的解决方法 (2) 不一定是样本少,还可能是分布不够广 “政治类” vs “体育类”文本分类,体育类集中在“篮球”领域 比如可以算算他们在空间中占据了多大的体积,例如给负类找一个 超球,它 可以包含所有负类的样本,再给正类找一个,比比两个球的半径,就可以大致确定分布的 情况 但是有些领域分布的确不够广,比如“高考作文” vs “ C 语言类” 73

74.unbalanced 问题的解决 方法 简单的就是美的 Libsvm 在 解决偏斜问题的 时候用的是方案一, 样本数量的 比 C 的初始值根据参数调优计算出来 咱们 先假定说 C + 是 5 这么大 , C - 就可以定为 500 这么大 ( 10000 : 100=100 : 1 ) 74

75.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 75

76.多元分类 SVM 是一种典型的两类分类器,即它只回答属于正类还是负类的 问题 而现实中要解决的问题,往往是多类的 问题 如何由两类分类器得到多类分类器,就是一个值得研究的问题 76

77.方案 一:一次求解 N 个分类面 一次性考虑所有样本,并求解一个多目标函数的优化问题,一次性得到多个分类 面 可惜这种算法还基本停留在纸面上,因为一次性求解的方法计算量实在太大,大到无法实用的地步 77

78.方案二:一类对其余 一类对余类法 (One versus rest , OVR ) 构造类别数 k 个的二元分类器 训练时第 i 个分类机取训练集中第 i 类为正类,其余类别点为负类 判别时,输入信号分别经过 k 个分类器输出 优点 每个优化问题的规模比较小,而且分类的时候速度很快 缺点 分类重叠 & 不可 分类 & 人为的数据偏斜 78

79.方案三:一对一 该方法在每两类问训练一个分类器,因此对于一个 k 类问题,将有 k(k-1) / 2 个 分类器 优点 避免了数据偏斜 训练阶段(也就是算出这些分类器的分类平面时)所用的总时间却比 “ OVR ” 方法少 很多 投票时也 会有分类重叠的现象,但不会有不可分类现象 缺点 类别 数为 5 的 时候,我们调用了 10 个分类器, 类别数如果是 1000 ,要调用的分类器数目会上升至约 500,000 个(但是时间上可能 OVO 还是比 OVR 少,因为考虑的样本数少) 79

80.方案四: DAG 方法 ( 有 向无环 图 ) DAG-SVMs 是针对 OVO 存在 误 分现象 提出 的 这种 方法 的 k(k-1) / 2 个分类器,构成 一个有向无环图。该有向无环图中含有 k(k-1)/2 个内部节点和 k 个叶结点,每个节点对应一个二类 分类器 80

81.方案四: DAG 方法 ( 有 向无环 图 ) 优点 简单易行,只需要使用 k-1 个决策函数即可得出结果,较“一对一 " 方法提高了测试速度,而且不存在误分、拒分区域 由于其特殊的结构, 故有一定的容错性,分 类精度较一般的二叉树 方法高 缺点 误差 积累 81

82.方案四: DAG 方法 ( 有 向无环 图 ) DAG 的错误累积 错误累积在一对其余和一对一方法中也都存在, DAG 方法好于它们的地方就在于,累积的上限,不管是大是小,总是有定论的,有理论 证明 而 一对其余和一对一方法中,尽管每一个两类分类器的泛化误差限是知道的,但是合起来做多类分类的时候,误差上界是多少 DAG 方法根节点的 选取 我们就总取在两类分类中正确率最高的那个分类器作根 节点 置信 度最大的路径 82

83.其他方案:决策树、 ECOC 决策树 方法 纠错输出编码 法 (ECOC) K * L 维编码矩阵 类别 判定用汉明距离 83

84.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 84

85.SVM 的应用 文本 分类 ( 下页详谈 ) 图像处理 图像 过滤、图片分类与检索 生物信息技术 蛋白质分类 语音识别 人脸 检测、指纹识别 手写字体 识别 网络 入侵检测、口令认证、网页分类 …… 85

86.SVM 的文本分类应用 例 : Topic 分类 14 万条微信数据, 33 个类别。 3000 条测试数据,其余数据为训练数据。 Emotion 分类 8000 句微博, 3 个类别。 2000 句测试数据,其余数据训练。 省略恢复 “小明买了苹果,很甜。” 86

87.大纲 背景 线性分类 非线性分类 松弛变量 多元 分类 应用 工具包 87

88.SVM 工具包 Libsvm Liblinear   Svm_perf LibShortText …… 88

89.Libsvm 简介 LibSVM 是林 智仁 ( Chih -Jen Lin ) 教授开发 可以很方便的对数据做分类或 回归 程序小,运用灵活,输入参数少,并且是开源的,易于扩展,因此成为目前国内应用最多的 SVM 的 库 The current release (Version 3.20, November 2014)  89

90.Libsvm 工具包 工具包组成 Java Matlab Python svm -toy( 一个可视化的工具 , 用来展示训练数据和分类界面 , 里面是源码 , 其编译后的程序在 windows 文件夹下 ) Tools( 四个 python 文件 , 用来数据集抽样 (subset), 参数 优选 (grid), 集成测试 (easy), 数据检查 ( checkdata )) Windows( 包含 libSVM 四个 exe 程序包 ) 其他 .c .h 源码 90

91.Libsvm 工具包常用命令 Svmtrain   svmtrain [options] training_set_file [ model_file ] Svmpredict svmpredict [options] test_file model_file output_file Svmscale svmscale [options] filename 91

92.Libsvm 模型文件 X.model 92

93.Libsvm 源码数据结构举例 SVM node SVM model 93

94.Libsvm 源码 数据结构 举例 SVM problem svm_train 调用的 svm_group_class 94

95.Liblinear Liblinear 线性分类器 主要为大规模数据的线性模型 设计 由于采用线性核 , 所以不需要计算 kernel value, 速度更 快 缺点 就是太吃内存了。 10G 的数据量需要接近 50G 的内存,数据量再大就没法做了  95

96.什么时候用 Liblinear 当你面对海量的数据时,这里的海量通常是百万级别 以上 海量 数据分为两个层次:样本数量和特征的数量。 使用线性和非线性映射训练模型得到相近的 效果 对模型训练的时间效率要求 较高 96

97.Liblinear 高效分类的理论基础 trust region method trust region method 是个优化的框架, a dual to line search x_k+1 = x_k + alpha * p_k 它 是先确定一个 region( hyperball ) ,或者说先确定它的半径 delta( 因为 球心就是 x_k ) , 然后在此球内优化泰勒展式的局部 模型 ( 一般 都是二 阶 ) 寻找 方向 p_k ,如果优化成功则球心转移,并扩大半径;如果不成功则球心不变,缩小半径。并如此 反复。(区别于 line search 先确定 p_k 后优化 alpha ) 97

98.Liblinear 高效分类的理论基础  truncated newton method truncated newton method 是指牛顿法中计算 H * p_k + g = 0 时采用数值迭代解决这个线性系统问题而不是直接高斯消元,其中 g 和 H 分别是目标函数的一阶导和二阶导 。 通常 情况下,这里可以用共轭梯度的近似解来逼近。 98

99.Svm_perf Made by 康 奈尔 大学 对计算机硬件的性能要求比 liblinear 要 低 See also Friendly to our 99

100.LibShortText LibShortText 是一个开源的 Python 短文 本 ( 包括 标题、短信、问题、句子 等 ) 分类工具包 它 在 LibLinear 的基础上针对短文本进一步优化,主要特性有 : 直接输入文本,无需做特征向量化的 预处理 二元分词( Bigram ),去 停顿词 ,做词 性过滤 基于线性核 SVM 分类器 提供了完整的 API ,用于特征分析和 Bad Case 检验 100

101.LibShortText 格式 Bad case 检验 & 特征 分析 101

102.LibShortText 缺点 不 支持中文,需要替换分词器 102

103.总结 背景 SVM 历史、宏观的理论基础与优点 线性分类 分类 面、间隔最大化、对偶问题求解 参数 非线性分类 问题的提出、核函数定义、举例、对比 松弛变量 离群点、软间隔、松弛变量、惩罚因子、数据集偏斜问题 多元 分类 多元分类的 N 种方法 应用 在 NLP 、图像、 网络等 方面的分类应用 工具包 libsvm 、 liblinear 、 svm_perf 、 libshortText 103

104.参考 SVM 系列 Jasper 、 JerryLead 、 v_JULY_v 、 Free Mind Superbear 、 Zouxy09 、 Guoze 、 zhoubl668 SVM 资源推荐 林智仁 - 机器学习 讲义 SVM CMU- SVM Slides MIT-SVM 讲义 刘家 峰 - 模式识别 SVM 104 / 104

105.谢谢 ~ 105

user picture
  • 献良
  • 非著名互联网公司工程师

相关Slides

  • 论文提出了一种新的深度神经网络模型家族,并没有规定一个离散的隐藏层序列,而是使用神经网络将隐藏状态的导数参数化。然后使用黑箱微分方程求解器计算该网络的输出。这些连续深度模型的内存成本是固定的,它们根据输入调整评估策略,并显式地用数值精度来换取运算速度。论文展示了连续深度残差网络和连续时间隐变量模型的特性。此外,还构建了连续的归一化流,一个可以使用最大似然方法训练的生成模型,无需对数据维度进行分割或排序。至于训练,论文展示了如何基于任意 ODE 求解器进行可扩展的反向传播,无需访问 ODE 求解器的内部操作。这使得在较大模型内也可以实现 ODE 的端到端训练。

  • 自然语言处理的总体介绍及其主要的任务,传统机器学习方法和深度学习方法分析,以及涉及到的NLP前沿研究进展。

  • 1. 中国人工智能产业发展迅速,但整体实力仍落后于美国 2. 中国企业价值链布局侧重技术层和应用层,对需要长周期的基础层关注 度较小 3. 科技巨头生态链博弈正在展开,创业企业则积极发力垂直行业解决方案, 深耕巨头的数据洼地,打造护城河 4. 政府端是目前人工智能切入智慧政务和公共安全应用场景的主要渠道, 早期进入的企业逐步建立行业壁垒,未来需要解决数据割裂问题以获得长 足发展 5. 人工智能在金融领域的应用最为深入,应用场景逐步由以交易安全为主 向变革金融经营全过程扩展 6. 医疗行业人工智能应用发展快速,但急需建立标准化的人工智能产品市 场准入机制并加强医疗数据库的建设 7. 以无人驾驶技术为主导的汽车行业将迎来产业链的革新 8. 人工智能在制造业领域的应用潜力被低估,优质数据资源未被充分利 用 9. 人工智能加速新零售全渠道的融合,传统零售企业与创业企业结成伙 伴关系,围绕人、货、场、链搭建应用场景 10. 政策与资本双重驱动推动人工智能产业区域间竞赛,京沪深领跑全 国,杭州发展逐步加速 11. 各地政府以建设产业园的方式发挥人工智能产业在推动新旧动能转换 中的作用 2. 杭州未来科技城抓住人工智能产业快速发展的机会并取得显著成绩, 未来可以从人才、技术、创新三要素入手进一步打造产业竞争力

  • 张首晟教授讲述了量子的世界,人工智能未来的发展以及区块链技术的展望与发展趋势。张提出区块链与人工智能共生的见解,人工智能需要数据,但是数据往往被中心化平台垄断,因而阻碍创新。从这种意义上人工智能有所欠缺。 加密经济学创造了一个对于数据提供者有正确激励机制的数据市场。人工智能能够依赖这个数据市场起飞。