924 工程科学学报，第42卷，第7期 理，下面对方法中需要用到的一些数学基础知识 以获得最优解 进行简单地说明 基于决策函数(5)，重写文献[13]中的线性列 1.2.1混合核 生成增强算法，使用2范数正则化构建如下凸二 核方法被证明了是解决许多应用中推理问题 次规划问题： 的有效方法.通过引入正半定核，可以使用线性 1 学习算法创建非线性模型.给定观测样本(x1, mina.2 y1),(x2,2),…,(x,y》∈X×Y.其中输入空间XeR, d (6) 输出空间Y∈R(回归问题)，通过非线性映射： S.t. y〉Kij+≥1,5i≥0，i=1,…,l Φ：X→F x→(x) (1) a≥0，j=1,…,d 把输入数据映射到一个新的特征空间F={(xx∈X, 求得其对偶问题为： d 其中F∈R”,原问题转化为： maxuming 1 i2 {(x1)y),(p(x2)y2),…,(x,ym}eF×Y（2) (7) 在满足Mercer条件情况下，一定存在一个特征空 s.t. uiyiKii≤aj,j=1,…,d, 间F和一个映射Φ：X→F,使得 i=I k(x,z）=x)Xz) 0≤h≤C,i=1,…,1 (3) 求解式(6)和(7)的最优解为(@，，)，根据文 k(x,z)即为核函数. 献[13引，验证如下问题： 核函数有两种主要的类型：全局核函数和局 部核函数，局部性核函数学习能力强、泛化性能较 T=max∑y,K (8) 弱，而全局性核函数泛化性能强、学习能力较弱， j 式中，遍历核矩阵中的所有列.列生成算法将 因此考虑把这两类核函数混合起来构成混合核函 列系数α分为两部分，使用启发式算法选出的一部 数.对文献[10]中混合核函数的形式进行扩展得 ，. 分W用于训练模型，未选中的部分N作为备选，假 到多核混合核函数的形式为k(x,)= 设未选中的部分αW=0,通过求解式(6)和(7)得当 其中k(x,z)为单核函数，p是对应的核函数编号， 前最优解得a",则d=(a",=0).经文献[14证 4p为组合系数.由SVM决策函数可知，混合核函 明，（位，，）是原始-对偶问题的当前最优解，如果 数的决策函数为： 对于所有的jEN∑K≤0，则位，店即为满足 =1 (4) KKT条件的全局最优解.对于线性列生成增强模 式中，α是模型参数，x是第个输入向量.本文中， 型，每次选择N中使∑K,最大的列K加入到约 i=l 不单独计算每个核矩阵（核对样本的Gram矩阵）， 束问题中 而是采用混合模型，其决策函数为： 将列生成增强算法推广到解决具有不敏感参 f=∑∑k,x》 数s的损失函数maxy-fx川-s,0的回归问题， (5) j=1p= 模型的下限约束α>0为非必需条件，所以在原模 1.22列生成 型中去除下限约束.为了构建回归模型，本文将偏 离真实值至少ε的点作为误差点.使用2范数正则 列生成算法是用于求解大型线性规划问题的 一种重要方法.在原始问题中，列生成算法并不是 化，对应的凸二次规划问题为： d 一次性求解出所有参数心，而是选取混合核矩阵 mina2Z a+C(⑤+m) K(构造方法在第4章介绍)的列子集并求解对应 的α的最优解四.根据拉格朗日对偶性，通过求 S.t. Kjj+≥7-e,i=1,…,l 解对偶问题可得到原始问题的最优解.原始问题 (9) 的每一列对应于对偶问题的一个约束，当约束问 K+i≥-%-e,i=1,…, 题的解违反对偶问题中不存在的约束时，则需将 台 该约束（原始问题中的一列）添加到约束问题中， 5≥0，≥0，i=1,…,1.理，下面对方法中需要用到的一些数学基础知识 进行简单地说明. 1.2.1    混合核 K {(x1, y1),(x2, y2),··· ,(xl , yl)} ∈ X×Y X ∈ R n Y ∈ R 核方法被证明了是解决许多应用中推理问题 的有效方法. 通过引入正半定核 ，可以使用线性 学习算法创建非线性模型. 给定观测样本 . 其中输入空间 ， 输出空间 （回归问题），通过非线性映射： Φ : X → F x 7→ Φ(x) （1） F = {Φ(x)|x ∈ X} F ∈ R n 把输入数据映射到一个新的特征空间 ， 其中 ，原问题转化为： {(Φ(x1), y1),(Φ(x2), y2),··· ,(Φ(xl), yl)} ∈ F×Y （2） F Φ : X → F 在满足 Mercer 条件情况下，一定存在一个特征空 间 和一个映射 ，使得 k(x,z) = Φ(x)×Φ(z) （3） k(x,z) 即为核函数. k(x,z) = ∑ P p=1 µpkp(x,z) kp (x,z) p µp 核函数有两种主要的类型：全局核函数和局 部核函数，局部性核函数学习能力强、泛化性能较 弱，而全局性核函数泛化性能强、学习能力较弱， 因此考虑把这两类核函数混合起来构成混合核函 数. 对文献 [10] 中混合核函数的形式进行扩展得 到多核混合核函数的形式为 ， 其中 为单核函数， 是对应的核函数编号， 为组合系数. 由 SVM 决策函数可知，混合核函 数的决策函数为： f(x) = ∑ l j=1 αj (∑ p µpkp(x, xj) ) （4） α xj 式中， 是模型参数， 是第 j 个输入向量. 本文中， 不单独计算每个核矩阵（核对样本的 Gram 矩阵）， 而是采用混合模型，其决策函数为： f(x) = ∑ l j=1 ∑ P p=1 α p j kp(x, xj) （5） 1.2.2    列生成 α K α 列生成算法是用于求解大型线性规划问题的 一种重要方法. 在原始问题中，列生成算法并不是 一次性求解出所有参数 ，而是选取混合核矩阵 （构造方法在第 4 章介绍）的列子集并求解对应 的 的最优解[11] . 根据拉格朗日对偶性[12] ，通过求 解对偶问题可得到原始问题的最优解. 原始问题 的每一列对应于对偶问题的一个约束，当约束问 题的解违反对偶问题中不存在的约束时，则需将 该约束（原始问题中的一列）添加到约束问题中， 以获得最优解. 基于决策函数（5），重写文献 [13] 中的线性列 生成增强算法，使用 2 范数正则化构建如下凸二 次规划问题： minα,ξ 1 2 ∑ d j=1 α 2 j +C ∑ l i=1 ξi s.t. yi ∑ d j=1 Ki jαj +ξi ⩾ 1, ξi ⩾ 0,i = 1,··· ,l, αi ⩾ 0, j = 1,··· ,d （6） 求得其对偶问题为： maxuminα ∑ l i=1 ui − 1 2 ∑ d j=1 α 2 j s.t. ∑ l i=1 uiyiKi j ⩽ αj , j = 1,··· ,d, 0 ⩽ ui ⩽ C,i = 1,··· ,l （7） (αˆ,ξˆ 求解式（6）和（7）的最优解为 ,uˆ) ，根据文 献 [13]，验证如下问题： τ = max j ∑ l i=1 uˆiyiKi j （8） j K α W N α N = 0 α W αˆ= (α W ,α N= 0) (αˆ,ξˆ,uˆ) j ∈ N, ∑ l i=1 uiyiKi j ⩽ 0 (αˆ,ξˆ,uˆ) N ∑ l i=1 uiyiKi j K· j 式中， 遍历核矩阵 中的所有列. 列生成算法将 列系数 分为两部分，使用启发式算法选出的一部 分 用于训练模型，未选中的部分 作为备选，假 设未选中的部分 ，通过求解式（6）和（7）得当 前最优解得 ，则 . 经文献 [14] 证 明， 是原始–对偶问题的当前最优解，如果 对于所有的 ，则 即为满足 KKT 条件的全局最优解. 对于线性列生成增强模 型，每次选择 中使 最大的列 加入到约 束问题中. ε max{|y− f(x)|−ε,0} α > 0 ε 将列生成增强算法推广到解决具有不敏感参 数 的损失函数 的回归问题[15] ， 模型的下限约束 为非必需条件，所以在原模 型中去除下限约束. 为了构建回归模型，本文将偏 离真实值至少 的点作为误差点. 使用 2 范数正则 化，对应的凸二次规划问题为： minα,ξ,η 1 2 ∑ d j=1 α 2 j +C ∑ l i=1 (ξi +ηi) s.t. ∑ l i=1 Ki jαj +ξi ⩾ yi −ε,i = 1,··· ,l, − ∑ l i=1 Ki jαj +ηi ⩾ −yi −ε,i = 1,··· ,l, ξi ⩾ 0,ηi ⩾ 0,i = 1,··· ,l. （9） · 924 · 工程科学学报，第 42 卷，第 7 期