第1期 陈晓华，等：可拓支持向量分类机 ·149· 值函数g(x),得到决策函数： 得到解a=[a5,…,aT。 f(x)=sgn(g(x)) (7) 3)计算最优超平面参数： 以便推断任意x对应的输出y,并判断其是否可以 变换为相反的输出-y。 w=∑ayx 可拓样本若样本点x可以通过改变某个或某 b=y-(wx),je0≤a≤C 些可拓变量的值而改变类别标号，则称x为可拓 4)构造分划超平面(w·x)+b=0,从而求出决策函 样本。 数fx)=sgn(w·)+b)。 下面给出可拓分类问题示意性的例子。图1中 5)对输入x,首先用决策函数f(x)得到其对应 给出了两类点，分别用▲和■表示，分量[x2为可拓 的预测类别%，然后用其可拓变量对应的可拓区间 变量。图1(a)所示的是所有点的可拓变量区间均 a和b分别代替[xJ,这样对E个可拓变量，会得到 满足[x2∈[a,b]的情况，即所有点被上下两条直线 2个不同的组合值，相应的，我们基于x,得到了 [x2=a和[x2=b所控制；图1(b)所示的是每个点的 2个新的输入，分别用决策函数来判断，若有一个 可拓变量区间不同的情况，即满足[x,∈[d,b,在图 被判断为%，则认为该输入是可变换的。 中就是每个点分别被双箭头线段所控制。 对图1(a)所示的例子，可以用算法2得到图 2(a)所示的分划线，因该问题的可拓变量区间为定 [x 值，所以可以直接得到两条垂直的线，在这两条垂 直线中间的点都是可拓样本（用圆圈标注），并用箭 头表示该样本在可拓变量的变化方向。对图1(a) 所示的例子，用算法2得到图2(b)所示的分划线， 可以看出没有可拓样本点，即没有点可以通过可拓 0 [x) 变量的区间变化来达到类别标号的改变。 (a)可拓变量区间固定 ]2 [2 0 (a)可拓区间固定的分划线 0 [x]2 b)可拓变量区间变化 图1可拓分类问题 Fig.1 Extension classification problem 注意，与标准的两类分类问题不同，这里除了 0 给出标准的训练集外，还给出了每个点的可拓变量 b)可拓区间变化的分划线 区间。据此可以构建算法2：可拓SVM1。 图2可拓分类SVM 算法2可拓SVM1 Fig.2 Extention classification SVM 输入输入训练集（见式(1）)： 进一步，考虑稍微复杂的情况，若对上述的可 输出决策函数。 拓分类问题，增加了先验知识。该先验知识为：在 1)输入训练集（见式(1）)，并选择合适的惩罚参 给定的训练集S中，训练点x,的可拓变量 数C>0。 [x],i=1,2,,l,jeE在可拓区间内变化时，其y,没 2)构造并求解凸二次规划问题： 有变化，如何寻找决策函数来推断任意x对应的输 四gwy宫a 出y,并判断其是否可以变换为相反的输出-y。 =1 可以看出，这时候训练点的输入就不再是一个 s.t.】 y=0 点，而是一个集合。如果限定该集合是一个凸集， 0≤a≤C,i=1,2,…,l 比如为一个球体，则训练集变为值函数 g(x) ，得到决策函数： f(x) = sgn(g(x)) (7) 以便推断任意 x 对应的输出 y，并判断其是否可以 变换为相反的输出–y。 可拓样本 若样本点 x 可以通过改变某个或某 些可拓变量的值而改变类别标号，则称 x 为可拓 样本。 [x]2 [x]2 ∈ [a, b] [x]2 = a [x]2 = b [xi]j ∈[a i j , b i j ] 下面给出可拓分类问题示意性的例子。图 1 中 给出了两类点，分别用▲和■表示，分量 为可拓 变量。图 1(a) 所示的是所有点的可拓变量区间均 满足 的情况，即所有点被上下两条直线 和 所控制；图 1(b) 所示的是每个点的 可拓变量区间不同的情况，即满足 ，在图 中就是每个点分别被双箭头线段所控制。 注意，与标准的两类分类问题不同，这里除了 给出标准的训练集外，还给出了每个点的可拓变量 区间。据此可以构建算法 2：可拓 SVM1。 算法 2 可拓 SVM1 输入 输入训练集 (见式 (1))； 输出 决策函数。 1) 输入训练集 (见式 (1))，并选择合适的惩罚参 数 C >0。 2) 构造并求解凸二次规划问题： min w,b,ξ 1 2 ∑l i=1 ∑l j=1 yiyj(xi · xj)αiαj− ∑l j=1 αi s.t. ∑l j=1 yiαi = 0 0 ⩽ αi ⩽ C, i = 1,2, ···, l α ∗ = [α ∗ 1 x ∗ 2 ,··· ,α∗ l ] 得到解 T。 3) 计算最优超平面参数: w ∗ = ∑l i=1 α ∗ i yixi b ∗ = yj−(w ∗ · xj), j ∈ {j   0 ⩽ α ∗ i ⩽ C} (w ∗ · x)+b = 0 f(x) = sgn((w ∗ · x)+b) 4) 构造分划超平面 , 从而求出决策函 数 。 xk f(xk) a k j b k j [xk]j |E| 2 |E| 2 |E| 5) 对输入 , 首先用决策函数 得到其对应 的预测类别 yk，然后用其可拓变量对应的可拓区间 和 分别代替 ，这样对 个可拓变量，会得到 个不同的组合值，相应的，我们基于 xk 得到了 个新的输入，分别用决策函数来判断，若有一个 被判断为-yk，则认为该输入是可变换的。 对图 1(a) 所示的例子，可以用算法 2 得到图 2(a) 所示的分划线，因该问题的可拓变量区间为定 值，所以可以直接得到两条垂直的线，在这两条垂 直线中间的点都是可拓样本 (用圆圈标注)，并用箭 头表示该样本在可拓变量的变化方向。对图 1(a) 所示的例子，用算法 2 得到图 2(b) 所示的分划线， 可以看出没有可拓样本点，即没有点可以通过可拓 变量的区间变化来达到类别标号的改变。 [xi]j ,i = 1,2, ···, l, j ∈ E 进一步，考虑稍微复杂的情况，若对上述的可 拓分类问题，增加了先验知识。该先验知识为：在 给定的训练 集 S 中，训练 点 x i 的可拓变量 在可拓区间内变化时，其 yi 没 有变化，如何寻找决策函数来推断任意 x 对应的输 出 y，并判断其是否可以变换为相反的输出–y。 可以看出，这时候训练点的输入就不再是一个 点，而是一个集合。如果限定该集合是一个凸集， 比如为一个球体，则训练集变为 (a) ਟᤃਈ䟿४䰤പᇊ (b) ਟᤃਈ䟿४䰤ਈॆ [x]2 O [x]1 [x]2 O [x]1 图 1 可拓分类问题 Fig. 1 Extension classification problem (a) ਟᤃ४䰤പᇊⲴࡂ࠶㓯 (b) ਟᤃ४䰤ਈॆⲴࡂ࠶㓯 [x]2 O [x]1 [x]2 O [x]1 图 2 可拓分类 SVM Fig. 2 Extention classification SVM 第 1 期 陈晓华，等：可拓支持向量分类机 ·149·