1、第七章 SVM支持向量机 SVM and Vapnik Vapnik 百度 http:/ 2hLcGtLXbsKo6XH4H2gDcavY4-cNKRYrHeP3r5YFEwhHKM66ncq Vapnik Wiki https:/en.wikipedia.org/wiki/Vladimir_Vapnik SVM 支持向量机(supportvectormachines. SVM) 二类分类模型.它的基本模型是定义在特征空间上的间隔最大的线 性分类器，间隔最大使它有别于感知机； 支持向量机还包括核技巧，这使它成为实质上的非线性分类器. 支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸 二
2、次规划(convex quadratic programming)的问题，也等价于正则化 的合页损失函数的最小化问题.支持向量机的学习算法是求解凸二 次规划的最优化算法. 支持向量机(supportvectormachines. SVM) 线性可分支持向量机(linear support vector machine in linearly separable case ). 硬间隔最大化(hard margin maximization)； 线性支持向量机(linear supportvector machine) 训练数据近似线性可分时，通过软间隔最大化(soft margin maxim
3、ization)； 非线性支持向量机(non-linear support vector machine) 当训练数据线性不可分时，通过使用核技巧(kernel trick)及软间隔最大化。 SVM分类 支持向量机(supportvectormachines. SVM) 当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时， 核函数(kernel function)表示将输入从输入空间映射到特征空间得 到的特征向量之间的内积； 通过使用核函数可以学习非线性支持向量机，等价于隐式地在高 维的特征空间中学习线性支持向量机，这样的方法称为核技巧； 核方法(kernel method)是比支持向量
4、机更为一般的机器学习方法. SVM分类 二分类问题： 输入空间：欧式空间或离散集合 特征空间：欧式空间或希尔伯特空间 线性可分支持向量机、线性支持向量机：假设这两个空间的元素 一一对应，并将输入空间中的输入映射为特征空间中的特征向量； 非线性支持向量机：利用一个从输入空间到特征空间的非线性映 射将输入映射为特征向量； 支持向量机的学习是在特征空间进行的. 线性可分支持向量机 假设特征空间上的训练数据集： 正例和负例 学习的目标：找到分类超平面， 线性可分支持向量机：给定线性可分训练数据集，通过间隔最大 化或等价地求解相应的凸二次规划问题学习得到的分离超平面为 决策函数： 线性可分支持向量机 w
5、x + b 0 wx + b 0 为惩罚参数 线性支持向量机与软间隔最大化 线性不可分的线性支持向量机的学习问题： 可证明w的解是唯一的，b不是， 设该问题的解是w*,b*,可得到分离超平面和决策函数 3 线性支持向量机与软间隔最大化 原始问题 的拉格朗日函数： 其中： 对偶问题是拉格朗日函数的极大极小问题 首先求 对w,b,的极小，由 得： 带入 3 线性支持向量机与软间隔最大化 得： 再对 求的极大，得到对偶问题： 线性支持向量机与软间隔最大化 原始问题 的对偶问题： 定理：设 是对偶问题 的一个解，若存在*的 一个分量 ，则原始问题的解w*,b* 3 4 4 线性支持向量机与软间隔最大化
6、 输入：线性不可分训练数据集 输出：分离超平面和分类决策函数 1、构造并求解约束最优化问题 求得最优解： 线性支持向量机学习算法 2、计算 并选择*，适合条件 ，计算 3、求得分离超平面 分类决策函数 线性支持向量机学习算法 支持向量 线性支持向量机学习还有另外一种解释，就是最小化以下目标函 数： 第一项： 称为合页损失函数 合页损失函数hinge loss function 线性支持向量机原始最优化问题: 等价于： 合页损失函数hinge loss function 合页损失函数hinge loss function 例子 非线性支持向量机与核函数 例子 例子 例子 度量空间 赋范空间 向量
7、空间 希尔伯特空间 内积空间 泛函基础 形成于20世纪30年代的数学分支； 从变分问题，积分方程和理论物理的研究中发展而来； 综合运用了函数论，几何学，代数学的观点； 可看成是无限维向量空间的解析几何及数学分析； 研究内容 无限维向量空间上的函数，算子和极限理论； 研究拓扑线性空间到拓扑线性空间之间，满足各种拓扑和代数条件 的映射； 泛函分析 函数概念被赋予了更为一般的意义 古典分析中的函数概念是指两个数集之间所建立的一种对应关系 现代数学的发展却是要求建立两个任意集合之间的某种对应关系 在数学上，把无限维空间到无限维空间的变换叫做算子 研究无限维线性空间上的泛函数和算子理论，就产生了一门新的
8、 分析数学，叫做泛函分析。 泛函分析 泛函分析自身 算子谱理论、巴拿赫代数、拓扑线性空间理论、广义函数论； 与其他数学学科的关联 微分方程、概率论、函数论、连续介质力学、计算数学、控制论、最优 化理论等学科中都有重要的应用，建立群上调和分析理论的基本工具； 与其他科学学科的关联 连续介质力学、量子物理学，是研究无限个自由度物理系统的重要而自 然的工具之一。 泛函分析的研究内容 距离空间 Banach空间（完备的赋范线性空间） Hilbert空间（完备的内积空间） 度量空间 设X是非空集合，对于X中的任意两元素x与y，按某一法则都对应 唯一的实数(x, y)，并满足以下三条公理（距离公理）： 1
9、.非负性：(x, y) 0，(x, y) =0当且仅当x=y； 2.对称性：(x, y) =(y, x)； 3.三角不等式: 对任意的x, y, z (x, y) (x, z) + (z, y) 则称(x, y)为x与y间的距离（或度量），并称X是以为距离的距离 空间（或度量空间），记成(X, )，或简记为X；X中的元素称为X 中的点。 度量(距离)空间 是泛函分析最基本的研究框架，在泛函分析中遇到的空间均 为度量空间； 度量空间的概念起源于经典分析，人们在研究线性常微分方 程、偏微分方程、变分法以及逼近论。 泛函分析中，经常将符合一定要求的元素放在一起所构成的 集合称之为一个“空间”，元素称
10、之为 “点”。 “点”：包含真正意义下的点、数列和函数。 泛函分析中，很少研究一个“点”的具体性质，而是研究一 个空间中点与点之间的关系，以及空间中符合一定条件的点 组成的该空间子集的一些性质。 度量(距离)空间 Lpa,b表示区间a,b绝对值的p次幂L可积函数的全体， 并把几乎处处相等的函数看成是同一个函数，对于x, yLpa,b，规定 则Lpa,b构成一个距离空间，称之为p次幂可积函数 空间 度量(距离)空间 完备性概念 完备性概念 线性空间（线性空间）： 空间中的任意两点可以做加法或与数相乘，运算的结果仍未该空间的点， 并且该空间中的每个点可以定义长度，这个长度称为该点的范数，范数 可以
11、视为欧式空间中向量长度概念的推广。 由于赋范空间既有代数结构，又有拓扑结果，因此其空间结构较 度量空间要丰富得多，其在实际中的应用也更加重要。 线性空间和赋范空间 设V是一个非空集合，K是实（或复）数域，并可在其上定义“加法”，“数乘”运 算，而且满足以下公理 加法交换律：x+y= y+x 加法结合律：(x+y)+z= x+(y+z) 存在零元：x+0=x 存在逆元：x+(-x)=0 数乘：1x=x a(bx)= (ab)x (a+b)x=ax+bx a(x+y)=ax+ay 则称V是数域K上的线性空间 线性空间 设X是实（或复）线性空间，如果对于X中每个元素x，按照一定的法 则对应于实数|x
12、|，且满足： |x|0，|x|=0当且仅当x等于零元（x=0） |ax|=|a|x|，a是实（或复）数 |x+y|x| + |y| 则称X是实（或复）赋范线性空间，|x|称为x的范数 赋范线性空间必然是距离空间： 定义(x, y)=|xy| 与度量空间不同： 平移不变性：d(x+a, y+a)=d(x, y), x,y,a 属于X 齐次性：d(ax, ay)=|a|d(x, y),x, y属于X，a属于K 赋范空间 如果赋范线性空间(X, |.|)是完备的，则称(X, |.|)是Banach空 间。 巴拿赫(Banach)(Banach)空间 如果赋范线性空间(X, |.|)是完备的，则称(X
13、, |.|)是Banach空 间。 巴拿赫(Banach)(Banach)空间 T是由赋范线性空间X中的某个子集D到赋范线性空间中的一个映 射，则称T 是算子，D是T 的定义域，记为D(T)，像集y | y=Tx, xD是T 的值域，记为T(D). 若T进一步满足 可加性：T(x+y)=Tx+Ty 齐次性：T(ax)=aT(x) 则T是线性算子 若存在正数M使得对于一切xD(T)，有|Tx| M|x|，则T是有 界算子 有界线性算子 T是由赋范线性空间X中的某个子集D到赋范线性空间中的一个映 射，则称T 是算子，D是T 的定义域，记为D(T)，像集y | y=Tx, xD是T 的值域，记为T(
14、D). 若T进一步满足 可加性：T(x+y)=Tx+Ty 齐次性：T(ax)=aT(x) 则T是线性算子 若存在正数M使得对于一切xD(T)，有|Tx| M|x|，则T是有 界算子 有界线性算子 定理：设X 和X1都是赋范线性空间，在B(X, X1)中定义加法和数乘 运算： (T1+T2)x=T1x+T2x(T1,T2 B(X, X1)，x X) (aT)x=a(Tx) (TB(X, X1)，a是数) 则B(X, X1)按照以上的线性运算是一个线性空间，并以前述算子范 数的定义构成赋范线性空间 若X1是Banach空间，则B(X, X1)也是Banach空间 有界线性算子 几何化：引入正交投影
15、的概念 定义：设X 是定义在实（或复）数域K上的线性空间，若对于X 任 意一对有序元素x,y, 恒对应数域K的值(x, y)，且满足 (ax, y) = a(x, y)； (x+y, z) = (x, z) + (x, z) (x, y)=(y, x) (x, x) 0，且(x, x)=0的充要条件是x=0 则称X为内积空间，(x, y)称为x, y的内积。 内积空间和Hilbert空间 可由内积导出范数 完备的内积空间称为希尔伯特(Hilbert)空间 Hilbert空间必为Banach空间 HilbertHilbert空间 HilbertHilbert空间 赋范线性空间X成为内积空间的充要
16、条件是它的范数满足中线公 式 而且内积可表示为 HilbertHilbert空间 HilbertHilbert空间 内积空间中的标准正交系 非线性分类问题： 非线性可分问题 如果能用Rn中的一个超曲面将正负例正确分开，则称这个问题为非线性 可分问题. 非线性支持向量机与核函数 非线性问题往往不好求解，所以希望能用解线性分类间题的方法 解决这个问题。 采取的方法是进行一个非线性变换，将非线性问题变换为线性问 题，通过解变换后的线性问题的方法求解原来的非线性问题。 原空间： 新空间： 非线性支持向量机与核函数 用线性分类方法求解非线性分类问题分为两步: 首先使用一个变换将原空间的数据映射到新空间;
17、 然后在新空间里用线性分类学习方法从训练数据中学习分类模型。 核技巧就属于这样的方法 核技巧应用到支持向量机，其基本想法： 通过一个非线性变换将输入空间(欧氏空间R”或离散集合)对应于一个特征 空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中 的超平面模型(支持向量机)。分类问题的学习任务通过在特征空间中求解 线性支持向量机就可以完成. 非线性支持向量机与核函数 核函数定义： 设X是输入空间(欧氏空间Rn的子集或离散集合)，又设H为特征空间(希 尔伯特空间)，如果存在一个从X到H的映射 使得对所有 函数K(x,z)满足条件 则称 为核函数， 为映射函数， 式中 为 和 的内积
18、 非线性支持向量机与核函数 核技巧的想法是： 在学习与预测中只定义核函数K(x,z)，而不显式地定义映射函数， 通常，直接计算K(x,z)比较容易，而通过 和 计算K(x, z)并 不容易。 注意：是 输入空间Rn到特征空间H的映射，特征空间H一般是高 维，映射可以不同。 非线性支持向量机与核函数 例： 假设输入空间是R2，核函数是 ,试找出其相关的特征空间 H和映射 解： 可以取： 容易验证： 非线性支持向量机与核函数 例： 假设输入空间是R2，核函数是 ,试找出其相关的特征 空间H和映射 解： 同样： 都满足条件。 非线性支持向量机与核函数 注意到： 线性支持向量机对偶问题中，无论是目标函
19、数还是决策函数都只 涉及输入实例和实例之间的内积。 目标函数中的内积 用核函数 代替，目标函数： 决策函数： 核函数在支持向量机的应用 问题： 己知映射函数，可以通过 和 的内积求得核函数K(x,z). 不用构造映射, 能否直接判断一个给定的函数K(x,z)是不是核函数? 或者说，函数K(x,z)满足什么条件才能成为核函数? 假设K(x,z)是定义在XxX上的对称函数，并且对任意的 K(x,z)关于 的Gram矩阵是半正定的，可以依据函数 K(x,z)，构成一个希尔伯特空间(Hilbert space)； 其步骤是首先定义映射 ，并构成向量空间S，然后在S上定义 内积构成内积空间; 最后将S完
20、备化构成希尔伯特空间. 正定核 1、定义映射，构成向量空间S 映射： 对任意 定义线性组合: 考虑由线性组合为元素的集合S, 由于集合S对加法和数乘运算是封 闭的，S构成一个向量空间。 正定核 2、在S上定义内积，构成内积空间 在S上定义一个运算“*”，对任意f，g属于S 定义运算*： 证明内积空间： 正定核 3、将内积空间S完备化为希尔伯特空间 由： 内积得到范数： 因此，S是一个赋范向量空间；根据泛函分析理论，对于不完备 的赋范向量空间S，一定可以使之完备化，得到完备的赋范向量 空间H；一个内积空间，当作为一个赋范向量空间是完备的时候， 就是希尔伯特空间，这样，就得到了希尔伯特空间H。 再
21、生性： 正定核 正定核的充要条件 设K： ，是对称函数，则K(x,z)为正定核函数的充 要条件是对任意 K(x,z)对应的Gram矩阵 是半正定的。 给定一个实矩阵 A，矩阵 ATA 是 A 的列向量的格拉姆矩阵， 而矩阵 AAT 是 A 的行向量的格拉姆矩阵。 格拉姆矩阵是半正定的，反之每个半正定矩阵是某些向量 的格拉姆矩阵。这组向量一般不是惟一的：任何正交基的 格拉姆矩阵是恒同矩阵。 正定核 正定核的等价定义 设 ，是K(x,z)是定义在 对称函数，如果对任意的 K(x,z)对应的Gram矩阵 半正定的，则称K(x,z)为正定核。 这一定义在构造核函数时很有用。但对于一个具体函数K(x,z
22、) 来 说，检验它是否为正定核函数并不容易，因为要求对任意有限输 入集 验证K对应的Gram矩阵是否为半正定的。 在实际问题中往往应用己有的核函数。 正定核 1、多项式核函数（Polynomial kernel function) 对应的支持向量机为P次多项式分类器，分类决策函数： 2、高斯核函数 （Gaussian Kernel Function) 决策函数： 常用核函数 3、字符串核函数： 考虑一个有限字符表，字符串s是从中取出的有限字符的序 列，包括空字符。s长度用|s|表示，元素记作 。 两串字符s和t的连接记作st。所有长度为n的字符串的集合记 作 ，所有字符串记作 考虑s的子串u，
23、给定一个指标序列 u定义为 ，长度记作 如果i是连续的，则 ， 否则 常用核函数 3、字符串核函数： 假设S是长度大于或等于n的字符串的集合，s是S的元素。现在建立字 符串集合S到特征空间 的映射 。 表示定义在 上的 实数空间，其每一维对应一个字符串 ，映射 将字符串s对应 于空间 的一个向量，其在u维上的取值为 常用核函数 3、字符串核函数： 两个字符串s和t上的字符串核函数是基于映射 的特征空间中 的内积 字符串核函数 给出了字符串s和t中长度等于n的所有子串组成 的特征向量的余弦相似度。 两串字符串相同的子串越多，就越相似，字符串核函数的值就越大。 常用核函数 输入：线性不可分训练数据
24、集 输出：分类决策函数 1、选取适当的核函数和参数C，构造最优化问题： 求得最优解： 5 非线性支持向量机学习算法 2、并选择*，适合条件 ，计算 3、构造决策函数 当K(x,z)是正定核函数时， 是凸二次规划问题， 解是存在的。 5 非线性支持向量机学习算法 序列最小最优化(sequential minimal optimization SMO)算法：1998 年由Platt提出。 动机： 支持向量机的学习问题可以形式化为求解凸二次规划问题.这样的 凸二次规划问题具有全局最优解，并且有许多最优化算法可以用 于这一问题的求解； 但是当训练样本容量很大时，这些算法往往变得非常低效，以致 无法使用
25、.所以，如何高效地实现支持向量机学习就成为一个重要 的问题。 序列最小最优化算法 SMO（Sequential minimal optimization ) 解如下凸二次规划的对偶问题 注意：变量是拉格朗日乘子i，一个对应一个样本 序列最小最优化算法 启发式算法，基本思路： 如果所有变量的解都满足此最优化问题的KKT条件，那么得到解； 否则，选择两个变量，固定其它变量，针对这两个变量构建一个二 次规划问题，称为子问题，可通过解析方法求解，提高了计算速度。 子问题的两个变量：一个是违反KKT条件最严重的那个，另一个由 约束条件自动确定。 SMO算法包括两个部分： 求解两个变量二次规划的解析方法
26、选择变量的启发式方法 SMO算法 选择两个变量，其它固定，SMO的 的子问题： 5 6 两个变量二次规划的求解过程 两个变量，约束条件用二维空间中的图形表示 假设问题 的初始可行解为 ，最优解 设2未经剪辑时的最优解为 6 两个变量二次规划的求解过程 根据不等式条件 的取值范围： 左图： 右图： 两个变量二次规划的求解过程 求解过程： 先求沿着约束方向未经剪辑时的 再求剪辑后的 记： 令： E 为输入x的预测值和真实输出y的差，i=1，2 两个变量二次规划的求解过程 定理： 最优化问题 沿约束方向未经剪辑的解： 剪辑后的解 得到1的解 6 两个变量二次规划的求解过程 证明： 引进记号 目标函数
27、写成： 由 及 两个变量二次规划的求解过程 得到只是2 的函数的目标函数 对2求导 令其为0： 两个变量二次规划的求解过程 将 代入： 将 代入： 两个变量二次规划的求解过程 得到定理： 最优化问题 沿约束方向未经剪辑的解： 剪辑后的解 得到1的解 6 两个变量二次规划的求解过程 SMO算法在每个子问题中选择两个变量优化，其中至少一个变量 是违反KKT条件的 1、第一个变量的选择：外循环 违反KKT最严重的样本点， 检验样本点是否满足KKT条件： 先检查 变量的选择方法 2、第二个变量的检查: 内循环， 选择的标准是希望能使目标函数有足够大的变化 即对应 最大 ，即E1，E2 的符号相反，差异
28、最大 如果内循环通过上述方法找到的点不能使目标函数有足够的下降 则：遍历间隔边界上的样本点，测试目标函数下降 如果下降不大，则遍历所有样本点 如果依然下降不大，则丢弃外循环点，重新选择 变量的选择方法 3、每次完成两个变量的优化后，重新计算b，Ei 由KKT条件： 计算阈值b和Ei 3、每次完成两个变量的优化后，重新计算b，Ei 由KKT条件： 计算阈值b和Ei 如果： 计算阈值b和Ei 输入：训练数据集 ，精度 输出：近似解 SMO算法 SVM light：Joachims http:/svmlight.joachims.org LIBSVM:http:/www.csie.ntu.edu.t
29、w/cjlin/libsvm SMO算法 SMO算法处理小规模数据集 SMO算法中的辅助函数 简化版SMO算法 利用完整Platt SMO算法加速优化 完整版Platt SMO的支持函数 完整版Platt SMO算法中的优化例程 完整版Platt SMO的外循环代码 在复杂数据上应用核函数 核转换函数 在测试中使用核函数 SMO算法编程实现 SMO算法中的辅助函数 SMO算法处理小规模数据集 SMO算法中的辅助函数 SMO算法处理小规模数据集 简化版SMO算法 SMO算法处理小规模数据集 简化版SMO算法 1 2 . 1 2 11 12 21 22 11 12 11 22 1111 + 121
30、2 2111 + 2212 11 1111 + 1212 + 22(2111 + 2212) SMO算法处理小规模数据集 SMO算法处理小规模数据集 SMO算法处理小规模数据集 SMO算法处理小规模数据集 SMO算法处理小规模数据集 。 。 SMO算法处理小规模数据集 SMO算法处理小规模数据集 完整版Platt SMO的支持函数 完整版Platt SMO的支持函数 完整版Platt SMO的支持函数 完整版Platt SMO的支持函数 完整版Platt SMO的内循环优化例程 完整版Platt SMO的内循环优化例程 完整版Platt SMO外循环 完整版Platt SMO外循环 完整版Platt SMO外循环 计算权值向量w 在复杂数据上应用核函数 核转换函数 核转换函数 核函数加入对原函数的修改 核函数进行样本测试 核函数进行样本测试 核函数进行样本测试 核函数进行样本测试 支持向量机手写识别 支持向量机手写识别 支持向量机手写识别 支持向量机手写识别 END
