模式识别

Size: px

Start display at page:

Download "模式识别"

魁寿
5 years ago
Views:

1 模式识别支撑向量机 SVM 吴建鑫南京大学计算机系,2018 1

2 统计学习方法的粗略分类 Statistical learning methods p(y = i), p y = i x, p(x y = i), p(x) 还记得其含义吗? Generative (probabilistic) models: 估计 p x y = i 和 p(y) 然后用贝叶斯定理求 p y = i x 生成模型 ( 下一章 ) Discriminative (probabilistic) models: 直接估计 p y = i x 判别模型 ( 下一章 ) Discriminant function: 直接求一个把各类分开的边界不假设概率模型, 如 FLD( 上一章 ),SVM( 本章 ) 更多阅读 PRML

3 目标理解并掌握 SVM 中主要思想的含义描述数学表述如何将一个好的 idea 形式化能实际应用 SVM 提高目标理解相关推导, 能在有文献帮助下自主完成推导进一步能通过独立阅读了解统计学习 3

4 SVM Support vector machine 支撑向量机注意 SVM 的形式化过程, 和简化的思路 4

large margin( 最大边际?) http://zh.wikipedia.org/wiki/file:classifier.

5 large margin( 最大边际?) 用线性边界分开 2 类正类 positive class, y i = 1 负类 negative class, y i = 1 可以有很多边界 L1,L2, L3,, 在训练集上都 100% 正确 ( 假设能完全分开 ) 哪个最好? 5

6 margin 图片来自 PRML 第 7 章一个点 ( 样例 ) 的边际 margin 是其到分界超平面 separating hyperplane 的垂直距离 SVM 最大化 ( 所有训练样本的 ) 最小边际有最小边际的点称为支撑向量 (support vectors) 所以叫支撑向量机 support vector machine 6

7 几何 geometry 示意图分类超平面 f x = w T x + b = 0 红色绿色为其法向量 normal vector x 为任一点 / 样例其到超平面的距离为? 图片来自 PRML 第 4 章 7

8 计算 margin 投影点为 x, x x 为距离向量其方向与 w 相同, 为 w/ w 其大小 r 可为 0, 或正, 或负 ; margin 为其大小的绝对值 x = x + r w w, 两边同乘以 w T, 然后加上 b w T x + b = w T x + b + r wt w w f x = f x + r w 为什么? r = f(x) w x 的 margin 是为什么? f(x) w = wt x+b w 8

9 分类评价怎么样分类? f x > 0 分为正类,f x < 0 分为负类那么 f x = 0 怎么办? 对于任何一个样例, 怎么知道预测的对错? y i f x i >0 正确 y i f x i < 0 错误即, 因为我们假设能完全分开, 所以 y i f x i = f x i 9

10 SVM 的形式化描述那么,SVM 问题是什么? argmax w,b argmax w,b argmax w,b min i min i 1 w min i 非常难以优化, 怎么办? 继续简化 w T x i + b w y i w T x i + b w y i w T x i + b 10

11 换个角度看问题到目前为止对 w 没有限制, 要求最大化最小的边际, 难优化判断对错 : 如果 yf x >0 即正确即 y(w T x + b)>0, 只需要方向, 完全不需要大小! 如果 (w, b) 变为 λw, λb, 预测和边际会变吗? 那么我们可以限定 min i y i w T x i + b 为 1 问题变为 : 在限制 min y i w T x i + b 为 1 时, 最大化 i 1 argmin w,b 2 wt w s. t. y i w T x i + b 1, i 1 w 11

12 拉格朗日乘子法,again L w, b, a = 1 2 wt w σ n i=1 a i y i (w T x i + b) 1 Subject to a i 0 作业 : 证明最优化的必要条件 L = 0 w = σ n w i=1 a i y i x i L = 0 0 = σ n b i=1 a i y i 在此两条件下, 将两个等式代入回 L n n L(a) = a i 1 2 a i a j y i y j x T i x j i=1 i=1 j=1 n 12

13 SVM 的对偶形式在原来的空间 ( 输入空间,input space) 中变量是 x i, 称为 SVM 的 primal form 现在的问题里面变量是 a i, 即拉格朗日乘子, 称为对偶空间 dual space 对偶空间完成优化后, 得到最优的 a, 可以得到原始空间中的最优解 w SVM 的对偶形式 dual form argmax a n n n a i 1 2 a i a j y i y j x T i x j i=1 i=1 j=1 s. t. a i 0 n a i y i = 0 i=1 13

14 剩下的问题如何最优化? 对偶空间中原始空间中如果能允许少数点 y i f x i < 1 如果允许一个点 y i f x i < 1, 但是大幅度增加 margin 呢? 如果不是线性可分的 linearly separable, 但是可以用非线性的边界分开 non-linearly separable? 如果不是两个类, 而是多个呢? 14

15 Soft margin 可以允许少数点 margin 比 1 小但是犯错误是有惩罚的, 否则? y i w T x i + b 1 y i w T x i + b 1 ξ i ξ i : 松弛变量 slack variable, 即允许犯的错误 ξ i 0 =0, (0 1), =1, >1 各自代表什么? 15 图片来自 PRML 第 7 章

16 如何惩罚? Primal space argmin w,b,ξ s. t. n 1 2 wt w + C i=1 ξ i y i w T x i + b 1 ξ i ξ i 0 C > 0: 正则化参数 regularization parameter ξ i 代价, 我们要最小化代价函数 ( 总代价 ) 1 2 wt w 正则项 regularization term, 对分类器进行限制, 使复杂度不至于太高 ( 另一个角度, 还是最大化边际 ) 那么, 怎么确定 C 的值? 16

17 Soft margin 的对偶形式自主阅读 PRML n argmax a i 1 a 2 a i a j y i y j x T i x j i=1 i=1 j=1 s. t. C a i 0 对偶形式仅依赖于内积! n n n a i y i = 0 i=1 17

18 内积 : 线性和非线性的联系线性和非线性有时候紧密联系在一起通过内积 x = x 1, x 2, z = z 1, z 2 K x, z = 1 + x T z 2 = 1 + x 1 z 1 + x 2 z 2 2 = 1 + 2x 1 z 1 + 2x 2 z 2 + x 2 1 z x 2 2 z x 1 z 1 x 2 z 2 1 2x 1 T 1 2z 1 = 2x 2 x 1 2 x 2 2 2x 1 x 2 2z 2 z 1 2 z 2 2 2z 1 z 2 18

19 Kernel trick 两个向量 x, y R d, 一个非线性函数 K x, y 对于满足某些条件的函数 K, 一定存在一个映射 (mapping) φ: R d Φ, 使得对任意的 x, y K x, y = φ x T φ y 非线性函数 K 表示两个向量的相似程度其等价于 Φ 里面的内积 Φ: 特征空间 feature space 可以是有限维的空间, 但也可以是无穷维的空间 infinite dimensional Hilbert space 19

20 什么样的限制条件? 必须存在特征映射 feature mapping, 才可以将非线性函数表示为特征空间中的内积 Mercer s condition(mercer 条件, 是充分必要的 ): 对任何满足 g 2 u du < 的非零函数, 对称函数 K 满足条件 : g u K(u, v)g(v)dudv 0 看上去眼熟? 另一种等价形式 : 对任何一个样本集合 x 1,, x n, x i R d, 如果矩阵 K = K ij i,j ( 矩阵的第 i 行第 j 列元素 K ij = K(x i, x j )) 总是半正定的, 那么函数 K 满足 Mercer 条件如何判定是否满足? 有几种方法? 20

21 核支撑向量机 Kernel SVM 核函数 kernel function: K 对偶形式 : argmax σ n i=1 a i 1 σ a 2 i=1 n n σ j=1 a i a j y i y j K(x i, x j ) 分类边界 : w = σ n i=1 a i y i φ(x i ) 怎样预测 :w T φ x = φ x T σ n i=1 a i y i φ x i = n a i y i K(x, x i ) σ i=1 线性 : w = σ n i=1 a i y i x i, w T x 计算量为 O(d) 非线性 ( 核 ) 方法测试所需时间为? 假设计算 K 的时间为 O(d), 是 O(nd) 吗? 21

22 Complementary Slackness 对所有 i,kkt 条件包括 (C a i )ξ i = 0 情况 1:C > a i > 0,ξ i = 0, 在特征空间中边际为 1 的两个超平面上情况 2:a i = C, 对 ξ i 没有限制可以在超平面上介于两个超平面之间或以外 ( 即分类错误 ) 情况 3:a i = 0, 在预测时不需要计算这代表什么? 复杂度由 a i > 0 的个数, 而非样本的总数目来决定 a 是稀疏的在 soft margin SVM 中, 称 a i > 0 对应的 x i 为支撑向量 22

23 非线性核线性核 linear kernel, dot-product kernel: K x, y = x T y 非线性核 non-linear kernel RBF(radial basis function) 高斯 (Gaussian) 核 : K x, y = exp( γ x y 2 ) 多项式核 : K x, y = γx T y + c d 进一步阅读 : 更多核函数 23

24 非线性核的例子 (RBF) 24 图片来自 PRML 第 7 章

25 超参数如何决定 C γ 必须给定这些参数 parameter 的值, 才能进行 SVM 学习, SVM 本身不能学习这些参数! 称为超参数 hyper-parameter 对 SVM 的结果有极大的影响! 用交叉验证在训练集上来学习在训练集上得到不同参数的交叉验证准确率选择准确率最高的超参数的数值 25

26 多类 Multiclass(1) 思路 : 转化为 2 类问题 1-vs-1 (one versus one): C 个类 {1,2,, C} C 设计个分类器 : 用 i 和 j(i > j) 两类的训练数据学习 2 一共 C C 1 /2 个, 其中每个类出现 C 次对测试样本 x, 一共会得到 C(C 1)/2 个结果, 然后投票 vote 每个分类器 f i 采用其二值输出, 即 sign(f i (x))

27 多类 Multiclass(2) 1-vs.-all ( 或 1-vs.-rest) 设计 C 个分类器, 第 i 个分类器用类 i 做正类, 把其他所有 C 1 个类别的数据合并在一起做负类和交叉验证的步骤有些类似每个新的分类器 f i 采用其实数值输出, 即 f i (x) f i x 的实数输出可以看成是其信心 confidence 最终选择信心最高的那个类为输出 argmax i f i (x) 27

28 多类 Multiclass(3) 直接解决多类问题 ( 进一步阅读 ) Crammer-Singer 方法 DAGSVM( 进一步阅读 ) ECOC( 进一步阅读 ) 28

29 从 SVM 的介绍学到的思想? 1. 确定问题, 对问题有充分的认识 ( 实践理论 ) 2. 好的思路想法 idea( 如 margin) 从理论 ( 概率统计?) 中来或者实践 ( 已有线性分类器的缺点, 如感知机 perceptron) 3. 形式化用精确的数学形式表达出来如果不能精确描述, 或说明你的 idea 有问题简化, 开始时避免复杂模糊的想法 : 限制条件 ( 如, 线性可分 ), 从较小范围开始 ( 如,2 类 ) 4. 数学基础和研究用到的几何凸优化拉格朗日乘子法 Hilbert 空间经典的相关数学背景要熟悉 : 至少知道到哪里查 29

30 简化 : 一种可靠的思路问题 ( 特别是数学问题 ) 难以解决时, 尽量简化问题的表述, 如果难以形式化, 可以将问题简化简化后的问题可以去除很多复杂的考虑, 但是原问题的核心要保持如 SVM 从二类线性可分的情况开始有时可以通过换思路的方法等价简化如 SVM 限定 min i y i w T x i + b 为 1 也可以对原问题做不重要的修改以使简化成为可能如 ( 进一步阅读 )LIBLINEAR 假设不使用 b 30

31 进一步的阅读如果对本章的内容感兴趣, 可以参考如下文献凸函数拉格朗日乘子法 KKT 条件 : Convex Optimization 第一二五章 SVM 和统计学习最新会议论文集 :ICML NIPS AISTATS COLT SMO: on LIBSVM, SVMLight Pegasos: DCD/LIBLINEAR: 加性核 : 我的主页 publications 页面 [W5] 31

从零构建支持向量机(SVM)

从零构建支持向量机(SVM) (SVM) zhangh04@gail.co (SVM),,,,,,,,,,,,,,,,,,,,.,, {(x, y ), (x, y ),..., (x, y )}, x i R d, y {, }, h: R {, }, h(x i ) = y i, y i = ; h(x i ) = () y i =. i. y i h(x i ) =. (), x i, h(x i ) := sign(w