·200· 北京科技大学学报 2006年第2期 y:(wx）+b)-1≥0i=1,2,…n(1) 分类函数式(6)，都只涉及到训练样本间的内积运 此时分类间隔Margin等于2/‖w∥，使分类间隔 算，这样在高维空间只需要进行内积运算，而这种 最大等价于使‖w2∥w∥最小，满足条件式(1) 内积运算是可以用原空间的函数实现的，根据泛 且使2/！w‖最大的分类面就叫做最优分类超平 函有关理论，只要一种核函数满足Mercer条件， 面，如图1中的H,H1,H2上的训练样本点叫做 它就对应着某一变换空间的内积. 支持向量(SV).这样，寻找最优分类超平面的问 概括地说，支持向量机通过事先选择好的某 题就转化为求如下的一个二次规划问题： 一个非线性变换，将输入向量x映射到高维特征 min4(w)=lw‖2/2 (2) 空间Z,在这个特征空间中构造一个最优分类超 满足约束条件： 平面.支持向量机的示意图如图2所示，它由两 y(wx:+b)≥1，i=1,2,…,n (3) 层组成：第一层从由核定义的给定基的集合中选 利用Lagrange优化方法可以把上述最优分 择基K(x,x:),i=1,…,5;第二层在这一空间中 类超平面问题转化为其对偶问题1,5)，即在约束 构造一个线性函数，这完全等价于在对应的特征 条件 空间中构造一个最优分类超平面. 宫m=0 (4a) 和 a:≥0，i=1,2,…,n ay (4a) 下对a:求解下列函数的最大值 K(xx) K(,x) K(xx) Q(a)= 会-台2aoS a:为每一个样本对应的Lagrange乘子.这是一 +。。 个不等式约束下的二次函数寻优问题，存在惟一 解.容易证明，解中将只有一部分（通常只有一少 图2支特向量机的构成 部分)a:不为零，对应的样本就是支持向量，解上 Fig.2 Structure of SVM 述问题后得到的最优分类函数是 对于多类分类情况，可以利用如下方法来构 f(x)=sgn(w·x+b)= 造一个n类分类器1山： sgm∑aiy(xx)+b (6) (1)构造n个两类分类器，其中规则f(x), 式中，b“为分类阙值，i为支持向量.可以用任一 k=1,…,n,将第k类的训练样本与其他训练样 个支持向量（满足条件式(3）中的等号)求得 本分开.若向量x:属于第k类，则sigm(f(x:)= 在线性不可分的情况下，可以在条件式(3) 1,否则sign(f(x:)=-1. 中增加一个松弛项：≥0，则式(3)变为： (2)通过选取函数f(x),k=1,…,n中最大 y((wx:)+b)≥1-，i=1,2,…n(7) 值所对应的类别 m =arg maxifi (x;),,fn (x:), 将目标改为求(，5)=分P+c启最 即可构造出一个n类分类器. 小，即折中考虑最少错分样本和最大分类间隔，就 2SVM实现动态学习 得到广义最优分类超平面，其中，C>0是一个常 数，它控制对错分样本惩罚的程度.广义最优分 动态学习的过程是首先从标准的训练样本库 类超平面的对偶问题与线性可分情况下几乎完全 中选择适当的样本进行训练，设计分类器；然后根 相同，只是条件式(4b)变为： 据当前分类器在分类过程中的性能进行评价，判 C≥a≥0i=1,2,…,n (8) 断是否需要采集新的样本进行训练，若性能小于 对于非线性问题，可以通过非线性变换转化 某一给定值，则可以根据分类后的处理过程动态 为某个高维空间中的线性问题，在变换空间中求 采集新的训练样本，并重新进行训练，设计新的分 最优分类超平面.这种变换一般比较复杂，但从 类器.这个过程可以重复进行，从而使学习变成 上面的讨论可以看出，不论是寻优函数式(5)还是 动态过程，也可以说是自动学习，. 2 0 0 . 北 京 科 技 大 学 学 报 年 第 期 2 0 0 6 2 y ` ( ( w · ` x ) + b ) 一 1 ) 1 = 1 0 , 2 , … n ( 1 ) 此 时分类 间隔 M a gr in 等于 2/ }{ w {} , 使分类间隔 最大 等价于 使 !1 w 11 “ l w {l最小 , 满足条 件式 ( l ) 且使 2/ {! w {l 最大的分类面就 叫做最 优分类超平 面 , 如 图 1 中的 H , H , , H : 上 的训 练 样本点叫做 支持向量 ( S v ) . 这 样 , 寻 找最优 分类超 平面 的问 题就转化 为求如下的一个二次规 划 问题 : m i n 笋( w ) 二 11 w .1 “ / 2 ( 2 ) 满足约束条件 : 夕` ( w · x * + b ) ) 1 , i = 1 , 2 , … , n ( 3 ) 利 用 L ag ar n g e 优 化方法 可 以把上 述 最 优分 类超 平 面 问题转化 为其对 偶 问题〔’ · 5 ] , 即在约 束 条 件 分类函数 式 ( 6 ) , 都只涉及到训 练样本间的内积运 算 , 这样在 高维空 间只需要 进行内积运算 , 而这 种 内积运 算是可以用 原空 间的函数实现 的 . 根据泛 函有 关理 论 , 只要 一种核 函 数满足 M er ce r 条 件 , 它就对 应着某一变换 空 间的内积 . 概 括地说 , 支持 向量 机通 过 事先选择好 的某 一个 非线性变换 , 将输入 向量 x 映 射到 高维特征 空间 z , 在这个特征空 间中构造 一 个 最优分类超 平 面 . 支持 向量机 的示 意 图如 图 2 所示 , 它 由两 层组成 : 第一 层从 由核定义 的给定基 的集合 中选 择基 K ( x , x 、 ) , i = 1 , … , : ; 第二 层 在这 一空 间中 构造一 个线性 函 数 , 这 完全 等价于 在对 应 的特征 空间 中构造一个 最优分类超平面 . 习 y ia * = 0 和 a 、 ) 0 , i = 1 , 2 , … , n 下对 a * 求解下 列函数的最大值 ( 4 a ) ( 4 a ) ~ , 、 启 l 砚 火0 ) = 夕 J 比 了 一 下万 犷写 一 ` 名 a , 岁伪 ( x 、 · xj ) ( 5 ) “ 、 为 每一 个样 本对应 的 L ag ar n g e 乘子 . 这 是 一 个不等式约束下 的二 次函数寻 优 问题 , 存在惟 一 解 . 容易证明 , 解中将只有 一部 分 (通 常只有一 少 部分 ) a 、 不为零 , 对应 的样本 就是 支持向量 , 解上 述 问题后得 到的最优分类 函数是 f ( x ) = s g n ( w · x + b ) = s g n ( 习 。 : , 、 ( x ` · 二 ) + 。 · ) ( 6 ) 式中 , b ’ 为分类 闭值 , i 为 支持向量 . 可以 用 任一 个支持向量 (满足条件式 ( 3) 中的等号 )求得 . 在线性不 可分 的情况 下 , 可 以 在条 件式 ( 3) 中增 加一个 松弛项 宁* ) 0 , 则式( 3) 变为 : 夕 : ( ( w · x ` ) + b ) ) 1 一 务 , i 二 1 , 2 , … n ( 7 ) 将 目标改 为求 ( , , ; ) 一 令J} , 一} , 十 。 ! 交。 ) 最 ’ 一 ’ ` ’ ` 一 ’ “ 一 ` ” ” ’ 2 ” ” ” 一 、 自 、 , / ~ 小 , 即折 中考 虑最 少错分样本和 最大分类间 隔 , 就 得 到广义最优分类超平面 . 其中 , C > O 是一个 常 数 , 它控制对错分样本惩罚 的 程度 . 广义 最优分 类超平面 的对偶间题与线性 可分情况下几 乎完全 相 同 , 只是条件式 ( 4 b) 变为 : C ) a ` ) 0 1 = 1 , 2 , … , n ( 8 ) 对于 非线性 问题 , 可 以 通 过 非线性 变换转 化 为某个高维空 间中的 线性 问题 , 在变换 空 间 中求 最 优分类 超平 面 . 这 种变 换 一般 比较复杂 , 但 从 上 面的讨论 可以看出 , 不论是寻 优 函数式 ( 5) 还是 图 2 支持向 t 机的构成 n g . 2 tS cur tur e o f S V M 对于 多类分类情况 , 可以 利用如 下方法 来构 造 一个 。 类分类 器 1[] : ( 1) 构造 n 个两类 分 类器 , 其 中规 则 人 ( x ) , k = 1 , … , n , 将第 k 类 的训 练样本与其他 训 练样 本分开 . 若向量 x ` 属于 第 k 类 , 则 is gn ( 人 ( x ` ) ) 二 1 , 否则 s i g n ( fk ( x , ) ) = 一 1 . ( 2 )通 过选取 函 数 fk ( x ) , 走 = z , … , n 中最 大 值所对应 的类别 m = a r g m a x }f l ( x 、 ) , … , 几 ( x , ) } , 即可构 造出 一个 n 类分类器 . 2 S V M 实现动态学习 动 态学 习的过程是首先从标准 的训 练样本库 中选择适 当的样本进行训 练 , 设计分类器 ; 然 后根 据当前分类器 在分类过 程 中 的性能进行评 价 , 判 断是否需要采集新的样 本 进行训 练 , 若性能 小 于 某一给 定值 , 则 可 以根据分类后 的处 理 过 程动 态 采集新的训练样本 , 并重新进行训 练 , 设 计新的分 类器 . 这 个 过 程可 以重 复进行 , 从而 使学 习变成 动态过 程 , 也可以说是 自动学 习