关键词 　 支持向量机； 线性支持向量机； 核方法； 近似高斯核； 再生核希尔伯特空间

    支持向量机（ ｓ ｕ ｐ ｐ ｏ ｒ ｔ 　ｖ ｅ ｃ ｔ ｏ ｒ 　ｍ ａ ｃ ｈ ｉ ｎ ｅ ， Ｓ ＶＭ ）［ １ － ３ ］是重要的机器学习方法． 该方法利用核诱导的特征映射将输入空间中的数据映射到特征空间， 继而在特征空间中训练线性学习器 ［２ ］ ．

    近年来， 大规模线性 Ｓ ＶＭ 的高效求解方法得到长足发展 ． Ｚ ｈ ａ ｎ ｇ［ ４ ］ 提出应用随机梯度下降算法来求解线性Ｓ ＶＭ ； Ｓ ｈ ａ ｌ ｅ ｖ － Ｓ ｈ ｗ ａ ｒ ｔ ｚ等人［ ５ ］ 进一步应用次梯度（ｓ ｕ ｂ － ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ） 下降算法给出更有效的求解算法；Ｊ ｏ ａ ｃ ｈ ｉ ｍ ｓ［ ６ ］ 基于截平面方法（ｃ ｕ ｔ ｔ ｉ ｎ ｇ 　ｐ ｌ ａ ｎ ｅ ）提出Ｓ ＶＭ －Ｐ ｅ ｒ ｆ算法； Ｓ ｍ ｏ ｌ ａ等人 ［７ ］ 进一步提出丛方法 （ ｂ ｕ ｎ ｄ ｌ ｅ 　ｍ ｅ ｔ ｈ ｏ ｄ ） ；Ｌ ｉ ｎ 等 人 ［８ ］ 应 用 置 信 域（ｔ ｒ ｕ ｓ ｔ 　ｒ ｅ ｇ ｉ ｏ ｎ ） 来求解大规模逻辑斯蒂回归（ ｌ ｏ ｇ ｉ ｓ ｔ ｉ ｃｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ） ； Ｃ ｈ ａ ｎ ｇ 等人［ ９ ］ 采用坐标下降（ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅｄ ｅ ｓ ｃ ｅ ｎ ｔ ） 法来求解Ｌ ２ － Ｓ ＶＭ ； Ｈ ｓ ｉ ｅ ｈ等人［ １ ０ ］ 应用对偶坐标梯度算法（ｄ ｕ ａ ｌ 　ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ） 求解线性Ｓ ＶＭ ； Ｙ ｕ等人 ［１ １ ］ 将上述方法推广到逻辑斯蒂回归上．虽然已有线性 Ｓ ＶＭ 高效求解算法， 但缺少处理非 线性 Ｓ ＶＭ 的高效 算 法 ［１ ２ － １ ４ ］ ． 

    如 何 应 用 线 性Ｓ ＶＭ 求解算法来设计非线性 Ｓ ＶＭ 求解算法得到关注 ［１ ２ ， １ ５ － １ ７ ］ ．将特征映射显式地作为线性 Ｓ ＶＭ 的输入， 能将非线性 Ｓ ＶＭ 转化为特征空间中的线性Ｓ ＶＭ ， 从而可应用高效线性 Ｓ ＶＭ 算法求解非线性Ｓ ＶＭ． Ｖ ｅ ｄ ａ ｌ ｄ ｉ 和 Ｚ ｉ ｓ ｓ ｅ ｒ ｍ ａ ｎ［ １ ７ ］ 研究可加核（ａ ｄ ｄ ｉ ｔ ｉ ｖ ｅｋ ｅ ｒ ｎ ｅ ｌ 　ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ） 特 征 映 射 的 近 似 构 造； Ｃ ｈ ａ ｎ ｇ 等人 ［１ ２ ］ 给出多项式核特征映射的显式构造；Ｒ ａ ｈ ｉ ｍ ｉ和 Ｒ ｅ ｃ ｈ ｔ［ １ ５ － １ ６ ］ 基于随机特征（ｒ ａ ｎ ｄ ｏ ｍ 　ｆ ｅ ａ ｔ ｕ ｒ ｅ ｓ ） 来构造平移不变核的特征映射； Ｙ ａ ｎ ｇ 等人 ［１ ８ ］ 应用低阶泰勒展开来近似高斯核， 并加速共轭梯度优化算法；Ｃ ａ ｏ等人 ［１ ９ ］ 同样应用低阶泰勒展开来近似高斯核，加速Ｓ ＶＭ 预测． 这些工作没有给出该近似核特征映射的显示构造， 从而无法直接应用线性 Ｓ ＶＭ 算法来求解非线性 Ｓ ＶＭ．

本文提出一种基于近似高斯核显示描述的大规模 Ｓ ＶＭ 求解方法 ． 首先， 给出近似高斯核的定义，推导近似高斯核与高斯核偏差的上界． 然后显式描述近似高斯核再生核希尔伯特空间的结构， 精确描述Ｓ ＶＭ 解的空间． 最后， 显式构造近似高斯核的特征映 射， 并 将 特 征 数 据 （ ｍ ａ ｐ ｐ ｅ ｄ 　ｄ ａ ｔ ａ ） 作 为 线 性Ｓ ＶＭ 的输入， 应用线性Ｓ ＶＭ 高效求解算法来求解非线性Ｓ ＶＭ．

    １　 预备知识

    本节 介 绍 再 生 核 希 尔 伯 特 空 间 （ｒ ｅ ｐ ｒ ｏ ｄ ｕ ｃ ｉ ｎ ｇｋ ｅ ｒ ｎ ｅ ｌ 　Ｈ ｉ ｌ ｂ ｅ ｒ ｔ 　ｓ ｐ ａ ｃ ｅ ， Ｒ ＫＨ Ｓ ） 与再生核（ ｒ ｅ ｐ ｒ ｏ ｄ ｕ ｃ ｉ ｎ ｇｋ ｅ ｒ ｎ ｅ ｌ ） 的基本概念．记 Ｒ ＋ ＝ ｛ ｘ ： ｘ ∈ Ｒ ， ｘ ＞０ ｝ ， Ｎ ＋ ＝ ｛ ｘ ： ｘ ∈ Ｎ ， ｘ ＞０ ｝ ． 对于 α ＝ （ α １ ， …， α ｎ ）Ｔ∈ （ Ｎ ＋ ∪ ｛ ０ ｝ ）ｎ和 ｘ=（ｘ １ ， …， ｘ ｎ ） ， 记 ｜ α ｜＝∑ｎｉ ＝１ αｉ ， ｘα ＝∏ｎｉ ＝１ｘα ｉｉ及 Ｃｋα ＝ｋ ！∏ｎｉ ＝１ αｉ ！ ．设 Ｘ  Ｒｎ 为非空集合， 若存在一个希尔伯特空间 Ｈ 及映射 Φ ： Ｘ → Ｈ 使得对  ｘ ， ｘ ′ ∈ Ｘ ， 都有 Ｋ（ｘ ， ｘ ′ ） ＝ 〈 Φ （ ｘ ′ ） ， Φ （ ｘ ） 〉 ， 则称 Ｋ 为 Ｘ 上的核函数，Φ （ • ） 为其特征映射．定义１．设 Ｘ 为非空集合， Ｈ ＝ ｛ｆ ： Ｘ → Ｒ ｝ 为函数 ｆ 构成的希尔伯特空间．１ ）若对所有 ｘ ∈ Ｘ ， Ｄ ｉ ｒ ａ ｃ泛函 δ ｘ ： Ｈ → Ｒ ，δ ｘ （ ｆ ） ： ＝ ｆ （ ｘ ）连续， 则称空间 Ｈ 为 Ｒ ＫＨ Ｓ．２ ）若  ｘ ∈ Ｘ ， 有 Ｋ （ •， ｘ ） ∈ Ｈ ， 且  ｆ ∈ Ｈ ，  ｘ∈ Ｘ 均满足再生性：ｆ （ ｘ ） ＝ 〈 ｆ ， Ｋ （ •， ｘ ） 〉 ，则称 Ｋ 为 Ｈ 的再生核．具有再生核的希尔伯特空间一定为 Ｒ ＫＨ Ｓ． 反之亦然 ．

    ２　 近似高斯核

本节首先定义近似高斯核， 推导近似高斯核与高斯 核 偏 差 上 界； 然 后 显 式 描 述 近 似 高 斯 核 的Ｒ ＫＨ Ｓ 、 显示构造近似高斯核的特征映射 ．

    ２． １　 近似高斯核定义定义 ２． 近似高斯核 ． 设 Ｘ  Ｒｎ 为非空集， 近似高斯核 Ｋ ： Ｘ × Ｘ →ＲＲ定义如下：Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０∑ｍｋ ＝０１ｋ ！ρｋ ∑｜ α ｜＝ ｋＣｋα ｘαｙα ，（１ ）其中，α ＝ （ α １ ， …， α ｎ ）Ｔ ∈ （Ｎ∪ ｛ ０ ｝ ）ｎ ，ｍ ∈ Ｎ ， σ ０ ，ρｋ ∈Ｒ ＋ ．下面定理说明： 近似高斯核收敛于高斯核， 近似高斯核是高斯核的近似 ．定理１．若 ｍ ＝∞ 且 ρｋ ＝ σｋ０ ， ｋ ＝０ ， １ ， …， 则近似高斯核为Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０∑∞ｋ ＝０１ｋ ！ σｋ０ ∑｜ α ｜＝ ｋＣｋα ｘαｙα为高斯核， 即 Ｋ （ ｘ ，ｙ ） ＝ｅ－ｘ － ｙ２２ σ ０．证明 ． 令 δ∑∞ｋ ＝０１ｋ ！ σｋ０ ∑｜ α ｜＝ ｋＣｋα ｘαｙα ， 则近似高斯核可表示为ｅ ｘ ｐ －ｘ ２ ＋ｙ ２２ σ（ ）０δ ． 由泰勒展开可得：ｅ ｘ ｐ〈ｘ ， ｙ 〉σ（ ）０＝１＋ 〈ｘ ， ｙ 〉σ ０＋ … ＋〈ｘ ， ｙ 〉ｍｍ ！ σｍ０＋ … ＝∑∞ｋ ＝０〈ｘ ， ｙ 〉ｋｋ ！ σｋ０．由于 〈ｘ ， ｙ 〉ｋ ＝ （ｘ １ ｙ １ ＋ ｘ ２ ｙ ２ ＋ … ＋ ｘ ｎ ｙ ｎ ）ｋ＝∑｜ α ｜＝ ｋＣｋα ｘαｙα ， 易得：ｅ ｘ ｐ〈ｘ ， ｙ 〉σ（ ）０＝ ∑∞ｋ ＝０１ｋ ！ σｋ０ ∑｜ α ｜＝ ｋＣｋα ｘαｙα＝ δ ． （ ２ ）　　 由式（ ２ ） 可得：Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ（ ）０ ｅ〈 ｘ ， ｙ 〉σ（ ）０ ＝ｅ－ｘ － ｙ２２ σ（ ）０ ．证毕 ．下面给出偏差 ｜ Ｋ （ ｘ ，ｙ ） － Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） ｜ 的上界，其中， Ｋ （ｘ ， ｙ ） 为近似高斯核， Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） 为高斯核．定理２．若令 ρｋ ＝ σｋ０ ， ｋ ＝０ ， １ ， …， ｍ ， 则存在 ξ ∈［０ ， 〈 ｘ ， ｙ 〉 ? σ２０ ］ ， 使得：｜ Ｋ （ ｘ ， ｙ ） － Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） ｜≤１（ ｍ ＋１ ） ！〈ｘ ， ｙ 〉σ ０ｍ ＋１ｅξ ．证明．由于：Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） － Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０ｅ〈 ｘ ， ｙ 〉σ ０－ ∑ｍｋ ＝０１ｋ ！〈ｘ ， ｙ 〉σ（ ）０（ ）ｋ．　　 由泰勒展开余项定理可知， 存在 ξ ∈ ［ ０ ， 〈 ｘ ， ｙ 〉 ?σ２０ ］ ， 使得：ｅ ｘ ｐ〈ｘ ， ｙ 〉σ（ ）０＝ ∑ｍｋ ＝０１ｋ ！〈ｘ ， ｙ 〉σ（ ）０ｋ＋ Ｒ ｍ〈ｘ ， ｙ 〉σ（ ）０，（３ ）其中， Ｒ ｍ （ 〈ｘ ， ｙ 〉 ? σ ０ ） ＝ （ 〈 ｘ ， ｙ 〉 ? σ ０ ）（ ｍ ＋１ ）ｅξ? （ ｍ ＋１ ） ！ ．因此， Ｋ ｇ ａ ｕ ｓ ｓ （ｘ ， ｙ ） － Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０×Ｒ ｍ〈ｘ ， ｙ 〉σ（ ）０．由于 －ｘ ２ ＋ｙ ２２ σ ０≤０， 有 ｅ－ｘ２ ＋ｙ２２ σ ０≤１ ，可得：｜ Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） － Ｋ （ ｘ ， ｙ ） ｜≤ Ｒ ｍ〈ｘ ， ｙ 〉σ（ ）０≤１（ ｍ ＋１ ） ！〈ｘ ， ｙ 〉σ ０ｍ ＋１ｅξ ．证毕．注１ ．若 Ｘ 有界， 即  Ｃ ≥ ０ ，  ｘ ∈ Ｘ ， ｘ ≤ Ｃ， 则｜ Ｋ （ ｘ ， ｙ ） － Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） ｜ ≤１（ ｍ ＋１ ） ！ｘ • ｙσ（ ）０ｍ ＋１ｅξ ≤１（ ｍ ＋１ ） ！Ｃ２σ（ ）０ｍ ＋１ｅξ ．因此， 当阶数 ｍ →∞ ，｜ Ｋ （ ｘ ， ｙ ） － Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ， ｙ ） ｜→０． 这表明近似高斯核的构造是一致的 ．

    ２． ２　 近似高斯核的 Ｒ ＫＨ Ｓ下面显示描述近似高斯核的 Ｒ ＫＨ Ｓ．定理３．设 Ｘ  Ｒｎ ， 空间Ｈ Ｋ 为Ｈ Ｋ ＝ ｆ （ ｘ ） ＝ｅ－ｘ２２ σ ０∑ｍｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｆ α ｘα ，ｘ ∈｛ ｝Ｘ ，（４ ）Ｈ Ｋ 上的内积〈 ， 〉 Ｋ 定义为〈ｆ ， ｇ 〉 Ｋ ＝ ∑ｍｋ ＝０ρｋｋ ！ ∑｜ α ｜＝ ｋｆ α ｇ αＣｋα， （５ ）其中，ｆ ， ｇ ∈ Ｈ Ｋ ， 有：ｆ ＝ｅ－ｘ２２ σ ０∑ｍｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｆ α ｘα ，ｇ ＝ｅ－ｘ２２ σ ０∑ｍｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｇ α ｘα ，ｆ α 和 ｇ α 为刻画 ｆ 和 ｇ 的系数 ． 则近似高斯核：Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０∑ｍｋ ＝０１ｋ ！ρｋ ∑｜ α ｜＝ ｋＣｋα ｘαｙα为 Ｈ Ｋ 的再生核 ．证明 ．１ ） Ｋ （ ｘ ， • ） ∈ Ｈ Ｋ ；２ ）再生性， 即对所有 ｆ ∈ Ｈ Ｋ 和 ｘ ∈ Ｘ ， 〈 ｆ ， Ｋ（ •，ｘ ） 〉 ＝ ｆ （ ｘ ） ．给定 ｘ ， Ｋ （ ｘ ，ｙ ） 为 ｙ 的函数， Ｋ （ ｘ ， ｙ ） 可以表示为Ｋ （ ｘ ， • ） （ ｙ ） ＝ｅ－ｙ２２ σ ０∑ｍｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｅ－ｘ２２ σ ０Ｃｋα ｘαρ ｋｙα ．　　 令 ｆ α ＝ｅ－ｘ２２ σ ０Ｃｋα ｘα?ρｋ ， 因此可知 Ｋ （ ｘ ， •） ∈Ｈ Ｋ ． 对于  ｆ ∈ Ｈ Ｋ， 由Ｈ Ｋ 中的内积定义可得：〈 Ｋ （ｘ ， • ） ， ｆ 〉 Ｋ ＝∑ｍｋ ＝０ρｋｋ ！ ∑｜ α ｜＝ ｋ（ｅ－ ｘ２? ２σ ０ Ｃ ｋα ｘα?ρｋ ） ｆ αＣｋα＝ｅ－ｘ２２ σ ０∑ｍｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｆ α ｘα＝ ｆ （ ｘ ） ．证毕．　　 注２．上述定理给出近似高斯 Ｒ ＫＨ Ｓ的显示描述， 精确刻画假设空间（ ｈ ｙ ｐ ｏ ｔ ｈ ｅ ｓ ｉ ｓ 　ｓ ｐ ａ ｃ ｅ ） 形式， 增强核方法的可解释性， 奠定近似高斯核的理论基础 ．下面考虑阶数 ｍ ＝∞ 的情况．推论１．设 Ｘ  Ｒｎ ， 空间Ｈ Ｋ 为Ｈ Ｋ｛＝ ｆ （ ｘ ） ＝ ｅ－ｘ２２ σ ０∑∞ｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｆ α ｘα ：ｆ ２Ｋ ＝ ∑ｍｋ ＝０ρｋｋ ！ ∑｜ α ｜＝ ｋｆ２αＣｋα＜ ∞ ， ｘ ∈｝Ｘ，Ｈ Ｋ 上的内积〈 ， 〉 Ｋ 定义为〈ｆ ， ｈ 〉 Ｋ ＝ ∑∞ｋ ＝０ρｋｋ ！ ∑｜ α ｜＝ ｋｆ α ｇ αＣｋα，其中，ｆ ， ｇ ∈ Ｈ Ｋ ， 有：ｆ ＝ｅ－ｘ２２ σ ０∑∞ｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｆ α ｘα ，ｇ ＝ｅ－ｘ２２ σ ０∑∞ｋ ＝０１ｋ ！ ∑｜ α ｜＝ ｋｇ α ｘα ，ｆ α 和 ｇ α 为刻画 ｆ 和 ｇ 的系数． 那么：Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０∑∞ｋ ＝０１ｋ ！ρｋ ∑｜ α ｜＝ ｋＣｋα ｘαｙα为 Ｈ Ｋ 的再生核．证明．令 ｍ ＝∞ ， 基于定理３可证明该结论．注３．文献［２ ０ ］ 已经给出高斯核 Ｒ ＫＨ Ｓ的显式描述 ． 由定理 １ 可知， 当 ｍ ＝∞ ，ρｋ ＝ σｋ０ 时， 近似高斯核为高斯核 ． 因此本文扩展文献［ ２ ０ ］ 相关结论， 而且采用 Ｗ ｅ ｙ ｌ 内积使证明更为简洁 ．

    ２． ３　 近似高斯核显式特征映射下面显式构造近似高斯核的特征映射．定理 ４． 设 Ｘ  Ｒｎ ， 近似高斯核Ｋ （ ｘ ， ｙ ） 的特征映射：Φ Ｋ （ ｘ ） ＝ ［ Φ ０ （ ｘ ） ， Φ １ （ ｘ ） ， …， Φ ｍ （ ｘ ） ］ ，（６ ）即 Ｋ （ ｘ ，ｙ ） ＝ 〈 Φ Ｋ （ ｘ ） ， Φ Ｋ （ ｙ ） 〉 ， 其中，Φ ｉ （ ｘ ） ＝ ｅ－ｘ２２ σ ０Ｃｉα ? （ ｉ ！ρｉ 槡） ｘα｜ α ｜＝［ ］ｉ（７ ）为向量，ｉ ＝０ ， １ ， …， ｍ ．证明 ． 由式（ ７ ） 容易验证：ｅ－ｘ２ ＋ｙ２２ σ（ ）０１ｋ ！ρｋ ∑｜ α ｜＝ ｋＣｋα ｘαｙα＝ 〈 Φ ｋ （ ｘ ） ， Φ ｋ （ ｙ ） 〉 ．　　 因 而 有 Ｋ （ ｘ ， ｙ ） ＝ ∑ｍｋ ＝０〈Φ ｋ （ ｘ ） ， Φ ｋ （ ｙ ） 〉 ＝〈Φ Ｋ （ ｘ ） ， Φ Ｋ （ ｙ ） 〉 ．证毕 ．现举例说明上述近似高斯核的显式特征映射 ．设输入空间维数 ｎ ＝２ ， 则２阶近似高斯核（ ｍ ＝２） 为Ｋ （ ｘ ， ｙ ） ＝ｅ－ｘ２ ＋ｙ２２ σ ０∑２ｋ ＝０１ｋ ！ρｋ ∑｜ α ｜＝ ｋＣｋα ｘαｙα＝ｅ－ｘ２ ＋ｙ２２ σ（０１ρ０＋１ρ１ ｘ１ ｙ １ ＋１ρ１ ｘ２ ｙ ２ ＋１ρ２ ｘ２１ ｙ２１ ＋２ρ２ ｘ１ ｘ ２ ｙ １ ｙ ２ ＋１ρ２ ｘ２２ ｙ２ ）２，其中，ｘ ＝ ［ ｘ １ ， ｘ ２ ］ ， ｙ ＝ ［ ｙ １ ， ｙ ２ ］ ∈ Ｒ２． 由式（６ ） （ ７ ）可知：Φ Ｋ （ ｘ ） ＝ｅ－ｘ２２ σ［０１ρ 槡０，１ρ 槡１ ｘ１ ，１ρ 槡１ ｘ２ ，１ρ 槡２ ｘ２１ ，２ρ 槡２ ｘ１ ｘ ２ ，１ρ 槡２ ｘ２ ］２ ．　　 容易验证 Ｋ （ ｘ ， ｙ ） ＝ 〈 Φ Ｋ （ ｘ ） ， Φ Ｋ （ ｙ ） 〉 ．注４．设训练数据 Ｓ ＝ ｛ ｘｉ ， ｙ ｉ ｝ｉ ＝１ ， 通过近似高斯核的显式特征映射， 将｛Φ Ｋ （ ｘ ｉ ） ， ｙ ｉ ｝ｉ ＝１ 作为线性Ｓ ＶＭ 的输入， 从而可应用线性Ｓ ＶＭ 来求解非线性分类问题．

    ３　 基于近似高斯核的高效非线性 Ｓ ＶＭ

本节首先简要介绍线性 Ｓ ＶＭ 高效求解算法．然后， 基于近似高斯核的显式特征映射， 应用线性Ｓ ＶＭ 高效算法来求解非线性 Ｓ ＶＭ．

    ３． １　 高效线性 Ｓ ＶＭ设训练数据为｛ （ｘ ｉ ， ｙ ｉ ） ｝ｉ ＝１ ， ｘ ｉ ∈ Ｒｎ ，ｙ ｉ ∈ ｛ －１ ，＋１ ｝ ， 线性 Ｓ ＶＭ 求解如下优化问题：ｍ ｉ ｎ １２ｗＴ ｗ ＋ Ｃ ∑ｉ ＝１ ｍ ａ ｘ（１－ ｙ ｉ （ ｗＴｘ ｉ ＋ ｂ ） ， ０ ） ．　　 不失一般性， 可通过在输入数据中增加一维使偏置项 ｂ 包含在 ｗ 中， 从而将 ｗＴｘ ｉ ＋ ｂ 替换成 ｗ Ｔ ｘ ｉ ，由此得式（８ ） 优化问题：ｍ ｉ ｎ １２ｗＴ ｗ ＋ Ｃ ∑ｉ ＝１ ｍ ａ ｘ（１－ ｙ ｉ ｗＴｘ ｉ ， ０ ） ．（８ ）　　 优化问题式（ ８ ） 称为 Ｓ ＶＭ 的原始形式， 其对偶形式为ｍ ｉ ｎα　 １２αＴ Ｑ α －ｅＴα ，ｓ ． ｔ ． 　０≤ α ｉ ≤ Ｃ ， ｉ ＝１ ， …，  ，（９ ）其中，Ｑｉ ｊ＝ ｘＴｉ ｘ ｊ ｙ ｉ ｙ ｊ ， ｅ ＝ ［ １ ， …， １ ］Ｔ ．文献［１ ０ ］ 给出高效的对偶坐标下降算法求解优化问题． 该算法每次只对一个坐标方向进行优化 ．若α 是当前迭代点， 则对它的第 ｉ 个坐标方向进行优化相当于求解如下单变量的优化问题：ｍ ｉ ｎ　 １２ Ｑｉ ｉ ｄ２ ＋ （Ｑ α － ｅ ） ｉ ｄ ＋ ｃ ｏ ｎ ｓ ｔ ａ ｎ ｔ ，ｓ ． ｔ ． 　０≤ α ｉ ＋ ｄ ≤ Ｃ ．（１ ０ ）其最优解为α ｉ ， ｎ ｅ ｗ ＝ｍ ｉ ｎ 　ｍ ａ ｘ α ｉ －ｙ ｉ ｗＴｘ ｉ －１Ｑ ｉ ｉ，（ ）０ ，（ ）Ｃ ． （ １ １ ）若 αｉ 为当前值， 而 α ｉ ， ｎ ｅ ｗ 是更新后的值， 则：ｗ ← ｗ ＋ （ α ｉ ， ｎ ｅ ｗ － α ｉ ） ｙ ｉ ｘ ｉ ．（１ ２ ）

    ３． ２　 基于显式特征映射的高效非线性Ｓ ＶＭ将｛Φ Ｋ （ ｘ ｉ ） ， ｙ ｉ ｝ｉ ＝１ 作为线性Ｓ ＶＭ 的输入， 从而可将线性Ｓ ＶＭ 的高效求解算法应用到非线性Ｓ ＶＭ上． 这种情况下， 决策函数 ｆ 为 ｆ （ ｘ ） ＝ ｗＴ ΦＫ （ ｘ ）． 相应的迭代为α ｉ ， ｎ ｅ ｗ ＝ｍ ｉ ｎ 　ｍ ａ ｘ α ｉ －ｙ ｉ ｗＴ ΦＫ （ ｘ ｉ ） －１Ｑ ｉ ｉ，（ ）０ ，（ ）Ｃ ，ｗ ← ｗ ＋ （ α ｉ ， ｎ ｅ ｗ － α ｉ ） ｙ ｉ Φ Ｋ （ ｘ ｉ ） ，其中，Ｑ ｉ ｉ ＝ 〈 Φ Ｋ （ ｘ ｉ ） ， Φ Ｋ （ ｘ ｉ ） 〉 ｙ ｉ ｙ ｉ ．注５．假设 Φ Ｋ （ ｘ ） 的维数为 ｐ ， 那么上述方法每次迭代需要 Ｏ （ｐ ） 次操作 ． 而标准的非线性 Ｓ ＶＭ 的复杂度为 Ｏ （３ ） ， 为样本的数目． 因此对于大规模分类问题， 当特征映射 Φ Ｋ （ ｘ ） 的维数适中时， 相比于标准非线性 Ｓ ＶＭ 算法， 本文所提出的算法求解效率将显著提高 ．

    ３． ３　 显式特征映射的稀疏保持性由 Φ Ｋ （ ｘ ） 的定义可知其维数为 Ｃｎ ＋ ｍｍ， 故当原始数据的维数 ｎ 很大或近似高斯核的阶数 ｍ 很大时，特征映射后的数据的维数较大 ． 如果原始数据本身具有一定的稀疏性， 那么映射后的数据仍会保持一定的稀疏性． 假定阶数 ｍ ＝２ ， 设维数为 ｎ 维的实例ｘ 中有 ｎ～维的属性值为０． 由式（７ ） 可知， Φ １ （ ｘ ） 中为０ 的特征的个数为 ｎ～ ．在 Φ ２ （ ｘ ） 中则有 ｎ ｎ～ － Ｃ ｎ～２ 为 ０．因此 Φ Ｋ （ ｘ ） 有 ｎ～ ＋ｎ ｎ～ － Ｃ ｎ～２ 维的值为 ０． 如假设 ｎ ＝２ ０ ， 当数据稠密时， 用２阶近似高斯核映射后维数为２ ３ １． 若该实例中有 ５ 个属性为 ０ ， 则映射后的特征向量中将有 ９ ５ 个值为 ０． 由此可见， 显式特征映射具有稀疏保持性 ． 可使特征映射的计算和 Ｓ ＶＭ 的求解简便有效．

    ３． ４　 预 　 测如果采用近似高斯核的显式特征映射， 其决策函数为 ｆ （ ｘ ） ＝ ｗＴ ΦＫ （ ｘ ） ． 对测试样本 ｘ 进行预测需要 Ｏ （ ｎ＾ ） 次操作，ｎ＾ 为 Φ Ｋ （ｘ ） 中非０特征的个数． 如果采用高斯， 决策函数为 ｆ （ ｘ ） ＝∑＃Ｓ Ｖｉ ＝１Ｋ ｇ ａ ｕ ｓ ｓ （ ｘ ｉ ， ｘ ）α ｉ ， 预测复杂度为 Ｏ （ ｎ ×＃Ｓ Ｖ ） ， ＃Ｓ Ｖ 表示支持向量的数目． 可见， 采用高斯核的非线性Ｓ ＶＭ 的预测复杂度随着支持向量的数目线性增长． 对于大规模训练数据， 支持向量的规模可能较大． 而通过选择适当的近似阶数 ｍ ， 基于近似高斯核显式映射的非线性Ｓ ＶＭ 的预测复杂度比普通高斯核的非线性Ｓ ＶＭ低很多 ．

    ４　 实验结果与分析

本节将通过实验验证所提出的方法的精确性与有效性． 实验均是在２ ． ２Ｇ Ｂ 　ＡＭＤ 　Ｏ ｐ ｔ ｅ ｒ ｏ ｎ 　Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｏ ｒ６ １ ７ ４Ｃ Ｐ Ｕ ， ３ ０Ｇ Ｂ 　Ｄ Ｄ Ｒ ３内存的机器上运行的．本文采用与文献［１ ２ ］ 相同的实验设定， 并应用相同的数据集． 数据集的描述如表１所示． 其中，ｎ是属性维数，ｎ－是非０属性数目的平均值．  是训练数据的数目． ｔ 为测试数据的数目． 本文实验考虑阶数 ｍ ＝２ 的情况， 则近似高斯核的形式为Ｋ Ｇ ａ ｕ ｓ ｓ － ２ （ ｘ ， ｙ ） ＝ｅ－ γ （ ｘ２ ＋ｙ２ ） ∑２ｋ ＝０２ｋγｋ? ｋ ！ ∑｜ α ｜＝ ｋＣｋα ｘαｙα ，（１ ３ ）其中，γ ＝１ ? （ ２ σ ） ． 以 下 实 验 将 对 比 Ｌ Ｉ Ｎ Ｅ ＡＲ［ ２ １ ］ ，Ｐ Ｏ Ｌ Ｙ － ２［ １ ２ ］ ，Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ［ ２ ２ ］ 和本文所提出 ＧＡＵ Ｓ Ｓ－ ２ ，详情如下：１ ） Ｌ Ｉ Ｎ Ｅ Ａ Ｒ 、 线性 Ｓ ＶＭ． 代码为 Ｌ Ｉ Ｂ Ｌ Ｉ Ｎ Ｅ Ａ Ｒ［ ２ １ ］ ．２ ） Ｐ Ｏ Ｌ Ｙ － ２ 、 构造２次多项式核 Ｋ Ｐ ｏ ｌ ｙ － ２ ＝ （γ ｘＴｙ ＋１ ）２的显式特征映射， 将数据映射到显式表示的特征 空 间， 再 采 用 高 效 线 性 Ｓ ＶＭ 求 解 算 法． 文献［１ ２ ］ 提供该方法的代码 ． 该代码是 Ｌ Ｉ Ｂ Ｌ Ｉ Ｎ Ｅ ＡＲ的扩展， 计算 Φ （ ｘ ） 是在训练时进行的．３ ） Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ 、 普通高斯核的非线性 Ｓ ＶＭ ， 即Ｋ Ｇ ａ ｕ ｓ ｓ ＝ｅ ｘ ｐ （ － γ ｘ － ｙ ２ ） ， 代码为 Ｌ Ｉ Ｂ Ｓ ＶＭ ［ ２ ２ ］ ．４ ） ＧＡＵ Ｓ Ｓ － ２ 、本 文 提 出 的 算 法 ． 调 用Ｌ Ｉ Ｂ Ｌ Ｉ Ｎ Ｅ ＡＲ． 但与 Ｐ Ｏ Ｌ Ｙ － ２ 不同的是， 训练前先计算所 有 Φ （ ｘ １ ） ， Φ （ ｘ ２ ） ，…， Φ （ ｘ ） ，不 需 要 对Ｌ Ｉ Ｂ Ｌ Ｉ Ｎ Ｅ ＡＲ 代码进行修改 ． 这样实现仅仅是为了简单， 尽管由于缓存 － 内存 － Ｃ Ｐ Ｕ 速度问题， 可能使效率受一定影响（ 参见文献［１ ２］ 中３． ４ 节的分析） ．４ 种算法中参数 Ｃ ∈ ｛ ２０ ， …，２１ ０ ｝ 和 γ ∈ ｛２－１ ０ ，…，２５ ｝ 都通过５折交叉验证进行选择（Ｌ Ｉ Ｎ Ｅ ＡＲ 没有参数 γ ） ．Ｔ ａ ｂ ｌ ｅ 　１　Ｂ ｅ ｎ ｃ ｈ ｍ ａ ｒ ｋ 　Ｄ ａ ｔ ａ ｓ ｅ ｔ ｓ表 １　 实验所用标准数据集Ｄ ａ ｔ ａ ｓ ｅ ｔ ｓ 　 ｎ ｎ－ ｔａ ９ ａ １ ２ ３ 　 １ ３． ９ 　 ３ ２ 　 ５ ６ １ 　 １ ６ 　 ２ ８ １ｉ ｊ ｃ ｎ ｎ ２ ２ １ ３． ０ 　 ４ ９ 　 ９ ９ ０ ９ １ 　 ７ ０ １ｃ ｏ ｖ ｔ ｙ ｐ ｅ 　 ５ ４ １ １． ９ 　 ４ ６ ４ 　 ８ １ ０ １ １ ６ 　 ２ ０ ２ｍ ｎ ｉ ｓ ｔ ３ ８ 　 ７ ５ ２ １ ６ ８． ２ 　 １ １ 　 ９ ８ ２ １ ９ ８ ４ｒ ｅ ａ ｌ － ｓ ｉ ｍ 　 ２ ０ 　 ９ ５ ８ 　 ５ １． ５ 　 ５ ７ 　 ８ ４ ８ 　 １ ４ 　 ４ ６ １ｗ ｅ ｂ ｓ ｐ ａ ｍ 　 ２ ５ ４ ８ ５． １ 　 ２ ８ ０ 　 ０ ０ ０ ７ ０ 　 ０ ０ ０４． １　 精度与效率４种方法的测试精度和训练时间分别如表２和表３所示． 首先考虑Ｌ Ｉ Ｎ Ｅ ＡＲ和 Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ的结果．从表 ２ 可知， 在所有 ６ 个数据集上， Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ 的精度都高于 Ｌ Ｉ Ｎ Ｅ ＡＲ ； 而从表 ３ 可知， Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ 的训练时间比Ｌ Ｉ Ｎ Ｅ ＡＲ长很多．然后再看 ＧＡＵ Ｓ Ｓ － ２的性能． 从表２可以看出，ＧＡＵ Ｓ Ｓ － ２ 与 Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ 的分类性能相近， 且从表 ３可看出， 相比于 Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ ， ＧＡＵ Ｓ Ｓ － ２ 的计算效率显著提高 ． 具体地， 在ａ ９ ａ ， ｉ ｊ ｃ ｎ ｎ ， ｍ ｎ ｉ ｓ ｔ ３ ８ ， ｒ ｅ ａ ｌ－ ｓ ｉ ｍ 和ｗ ｅ ｂ ｓ ｐ ａ ｍ 数据集上， 本文方法的精度与 Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ相差无几 ． 在 ｃ ｏ ｖ ｔ ｙ ｐ ｅ 数据集上， 精度不如 Ｋ Ｅ Ｒ Ｎ Ｅ Ｌ．原因是阶数 ｍ ＝２对这个数据集是不够的． 实际上，当考虑 ｍ ＝３时， 此时 ＧＡＵ Ｓ Ｓ － ２在该数据集上的精度为８ ２ ． ４ ８％ ， 提高２ ． ４％． 在个别数据集上精度不如普通高斯核 Ｓ ＶＭ ， 但训练时间上的优势是显著的， 因而本文所提出的方法提供了一个效率和精度之间的很好折中 ．最后比较算法 ＧＡＵ Ｓ Ｓ － ２ 和 Ｐ Ｏ Ｌ Ｙ － ２． 从表 ２ 可以看出， 在所有 ６ 个数据集上有 ４ 个 ＧＡＵ Ｓ Ｓ － ２ 在精度上比 Ｐ Ｏ Ｌ Ｙ － ２ 高 ． 尽管前面所述本文计算特征映射的实现方式不如 Ｐ Ｏ Ｌ Ｙ － ２ 高效， 但 ＧＡＵ Ｓ Ｓ － ２的训练时间在 ４ ? ６ 个数据集上比 Ｐ Ｏ Ｌ Ｙ － ２ 的短 ． 原因是 ＧＡＵ Ｓ Ｓ － ２的收敛速度往往 Ｐ Ｏ Ｌ Ｙ － ２快， 这可以从图１得到验证． 从图１可知 ＧＡＵ Ｓ Ｓ － ２的迭代次数在５ ? ６ 个数据集上比 Ｐ Ｏ Ｌ Ｙ － ２ 少 ．上述实验表明， 本文方法能提高非线性 Ｓ ＶＭ 的求解效率， 并保证算法的精确性 ．

    ５　 结 　　 语

    为了应用高效线性Ｓ ＶＭ 算法求解大规模非线性Ｓ ＶＭ 分类问题， 本文引入近似高斯核． 首先， 度量近似高斯核与高斯核的偏差上界， 从理论上说明近似高斯核的合理性． 然后， 对近似高斯核的再生核希尔伯特空间进行精确刻画， 由此能对 Ｓ ＶＭ 解的结构进行精确描述， 增强模型的可解释性， 为刻画Ｓ ＶＭ 的学习性能带来帮助． 最后， 显式构造近似高斯核的特征映射， 从而能应用线性Ｓ ＶＭ 高效算法来求解非线性Ｓ ＶＭ． 实验进一步验证所提出的方法合理性及高效性．进一步工作将研究近似高斯核在其他核方法中的应用及其泛化理论．

    参 考 文 献［ １ ］ Ｖ ａ ｐ ｎ ｉ ｋ 　Ｖ． Ｔ ｈ ｅ 　Ｎ ａ ｔ ｕ ｒ ｅ 　ｏ ｆ 　Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 Ｔ ｈ ｅ ｏ ｒ ｙ ［ Ｍ ］ ．Ｂ ｅ ｒ ｌ ｉ ｎ ： Ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ， ２ ０ ０ ０［ ２ ］ Ｃ ｒ ｉ ｓ ｔ ｉ ａ ｎ ｉ ｎ ｉ 　Ｎ ， Ｓ ｈ ａ ｗ ｅ － Ｔ ａ ｙ ｌ ｏ ｒ 　Ｊ ．Ａ ｎ 　Ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｔ ｉ ｏ ｎ 　ｔ ｏ 　Ｓ ｕ ｐ ｐ ｏ ｒ ｔＶ ｅ ｃ ｔ ｏ ｒ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ 　ａ ｎ ｄ 　Ｏ ｔ ｈ ｅ ｒ 　Ｋ ｅ ｒ ｎ ｅ ｌ － Ｂ ａ ｓ ｅ ｄ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 Ｍ ｅ ｔ ｈ ｏ ｄ ｓ［ Ｍ ］ ． Ｃ ａ ｍ ｂ ｒ ｉ ｄ ｇ ｅ ， ＵＫ ： Ｃ ａ ｍ ｂ ｒ ｉ ｄ ｇ ｅ 　Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ 　 Ｐ ｒ ｅ ｓ ｓ ， ２ ０ ０ ０［ ３ ］ Ｚ ｈ ａ ｎ ｇ 　 Ｘ ｕ ｅ ｇ ｏ ｎ ｇ ． Ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｔ ｉ ｏ ｎ 　ｔ ｏ 　ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ 　ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 ｔ ｈ ｅ ｏ ｒ ｙａ ｎ ｄ 　ｓ ｕ ｐ ｐ ｏ ｒ ｔ 　ｖ ｅ ｃ ｔ ｏ ｒ 　ｍ ａ ｃ ｈ ｉ ｎ ｅ ［ Ｊ ］ ．Ａ ｃ ｔ ａ 　Ａ ｕ ｔ ｏ ｍ ａ ｔ ｉ ｃ ａ 　Ｓ ｉ ｎ ｉ ｃ ａ ，２ ０ ０ ０ ， ２ ６ （ １ ） ： ３ ２ － ４ ２ （ ｉ ｎ 　Ｃ ｈ ｉ ｎ ｅ ｓ ｅ ）（ 张学工．关于统计学习理论与支持向量机［ Ｊ ］ ．自动化学报， ２ ０ ０ ０ ， ２ ６ （１ ） ： ３ ２ － ４ ２ ）［ ４ ］ Ｚ ｈ ａ ｎ ｇ 　 Ｔ ｏ ｎ ｇ ．Ｓ ｏ ｌ ｖ ｉ ｎ ｇ 　 ｌ ａ ｒ ｇ ｅ 　ｓ ｃ ａ ｌ ｅ 　ｌ ｉ ｎ ｅ ａ ｒ 　ｐ ｒ ｅ ｄ ｉ ｃ ｔ ｉ ｏ ｎ 　ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｓｕ ｓ ｉ ｎ ｇ 　 ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｓ ［Ｃ ］ ? ? Ｐ ｒ ｏ ｃ 　ｏ ｆ 　ｔ ｈ ｅ２ １ ｓ ｔ 　Ｉ ｎ ｔ 　Ｃ ｏ ｎ ｆ 　ｏ ｎ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ．Ｓ ａ ｎ 　Ｆ ｒ ａ ｎ ｃ ｉ ｓ ｃ ｏ ， Ｃ Ａ ：Ｍ ｏ ｒ ｇ ａ ｎ 　Ｋ ａ ｕ ｆ ｍ ａ ｎ ｎ ， ２ ０ ０ ４ ： １ ６ － １ ２ ３［ ５ ］ Ｓ ｈ ａ ｌ ｅ ｖ － Ｓ ｈ ｗ ａ ｒ ｔ ｚ 　Ｓ ， Ｓ ｉ ｎ ｇ ｅ 　Ｙ ， Ｓ ｒ ｅ ｂ ｒ ｏ 　Ｎ ， ｅ ｔ 　ａ ｌ ．Ｐ ｅ ｇ ａ ｓ ｏ ｓ ：ｐ ｒ ｉ ｍ ａ ｌ 　ｅ ｓ ｔ ｉ ｍ ａ ｔ ｅ ｄ 　ｓ ｕ ｂ － ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　ｓ ｏ ｌ ｖ ｅ ｒ 　ｆ ｏ ｒ 　Ｓ ＶＭ ［ Ｊ ］ ．Ｍ ａ ｔ ｈ ｅ ｍ ａ ｔ ｉ ｃ ａ ｌ 　Ｐ ｒ ｏ ｇ ｒ ａ ｍｍ ｉ ｎ ｇ ， ２ ０ １ １ ， １ ２ ７ （ １ ） ： ３ － ３ ０［ ６ ］ Ｊ ｏ ａ ｃ ｈ ｉ ｍ ｓ 　Ｔ． Ｔ ｒ ａ ｉ ｎ ｉ ｎ ｇ 　 ｌ ｉ ｎ ｅ ａ ｒ 　Ｓ ＶＭ ｓ 　ｉ ｎ 　ｌ ｉ ｎ ｅ ａ ｒ 　ｔ ｉ ｍ ｅ ［ Ｃ ］ ? ? Ｐ ｒ ｏ ｃｏ ｆ 　ｔ ｈ ｅ 　１ ２ ｔ ｈ 　Ａ ＣＭ　Ｃ ｏ ｎ ｆ 　ｏ ｎ 　Ｋ ｎ ｏ ｗ ｌ ｅ ｄ ｇ ｅ 　Ｄ ｉ ｓ ｃ ｏ ｖ ｅ ｒ ｙ 　 ａ ｎ ｄ 　Ｄ ａ ｔ ａＭ ｉ ｎ ｉ ｎ ｇ ．Ｎ ｅ ｗ　Ｙ ｏ ｒ ｋ ： Ａ ＣＭ ： ２ ０ ０ ６ ： ２ １ ７ － ２ ２ ６［ ７ ］ Ｓ ｍ ｏ ｌ ａ 　Ａ ， Ｖ ｉ ｓ ｈ ｗ ａ ｎ ａ ｔ ｈ ａ ｎ 　Ｓ ， Ｌ ｅ 　Ｑ．Ｂ ｕ ｎ ｄ ｌ ｅ 　ｍ ｅ ｔ ｈ ｏ ｄ ｓ 　ｆ ｏ ｒｍ ａ ｃ ｈ ｉ ｎ ｅ 　ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ［ Ｃ ］ ? ? Ａ ｄ ｖ ａ ｎ ｃ ｅ ｓ 　ｉ ｎ 　Ｎ ｅ ｕ ｒ ａ ｌ 　Ｉ ｎ ｆ ｏ ｒ ｍ ａ ｔ ｉ ｏ ｎＰ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｓ ｙ ｓ ｔ ｅ ｍ ｓ 　２ ０． Ｃ ａ ｍ ｂ ｒ ｉ ｄ ｇ ｅ ， ＭＡ ： Ｍ Ｉ Ｔ 　Ｐ ｒ ｅ ｓ ｓ， ２ ０ ０ ８ ：１ ３ ７ ７ － １ ３ ８ ４［ ８ ］ Ｌ ｉ ｎ 　Ｃ 　Ｊ ， Ｗ ｅ ｎ ｇ 　 Ｒ 　Ｃ ， Ｋ ｅ ｅ ｒ ｔ ｈ ｉ 　Ｓ． Ｔ ｒ ｕ ｓ ｔ 　ｒ ｅ ｇ ｉ ｏ ｎ 　ｎ ｅ ｗ ｔ ｏ ｎ 　ｍ ｅ ｔ ｈ ｏ ｄｆ ｏ ｒ 　ｌ ａ ｒ ｇ ｅ － ｓ ｃ ａ ｌ ｅ 　ｌ ｏ ｇ ｉ ｓ ｔ ｉ ｃ 　ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　ｏ ｆ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅＬ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 Ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ ， ２ ０ ０ ８ ， ９ ： ６ ２ ７ － ６ ５ ０［ ９ ］ Ｃ ｈ ａ ｎ ｇ 　 Ｋ　Ｗ ， Ｈ ｓ ｉ ｅ ｈ 　Ｃ 　Ｊ ， Ｌ ｉ ｎ 　Ｃ 　Ｊ ． Ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　ｍ ｅ ｔ ｈ ｏ ｄｆ ｏ ｒ 　ｌ ａ ｒ ｇ ｅ － ｓ ｃ ａ ｌ ｅ 　Ｌ ２ － ｌ ｏ ｓ ｓ 　ｌ ｉ ｎ ｅ ａ ｒ 　Ｓ ｕ ｐ ｐ ｏ ｒ ｔ 　Ｖ ｅ ｃ ｔ ｏ ｒ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　ｏ ｆ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 Ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ ， ２ ０ ０ ８ ， ９ ： １ ３ ６ ９ － １ ３ ９ ８［ １ ０ ］ Ｈ ｓ ｉ ｅ ｈ 　Ｃ 　Ｊ ， Ｃ ｈ ａ ｎ ｇ 　 Ｋ　Ｗ ， Ｌ ｉ ｎ 　Ｃ 　Ｊ ．Ａ 　ｄ ｕ ａ ｌ 　ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　ｄ ｅ ｓ ｃ ｅ ｎ ｔｍ ｅ ｔ ｈ ｏ ｄ 　ｆ ｏ ｒ 　Ｌ ａ ｒ ｇ ｅ － ｓ ｃ ａ ｌ ｅ 　ｌ ｉ ｎ ｅ ａ ｒ Ｓ ＶＭ ［ Ｃ ］ ? ? Ｐ ｒ ｏ ｃ 　ｏ ｆ 　ｔ ｈ ｅ 　２ ５ ｔ ｈ 　Ｉ ｎ ｔＣ ｏ ｎ ｆ 　ｏ ｎ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ．Ｓ ａ ｎ 　Ｆ ｒ ａ ｎ ｃ ｉ ｓ ｃ ｏ ， Ｃ Ａ ： Ｍ ｏ ｒ ｇ ａ ｎＫ ａ ｕ ｆ ｍ ａ ｎ ｎ ， ２ ０ ０ ８ ： ４ ０ ８ － ４ １ ５［ １ １ ］ Ｙ ｕ 　Ｈ　Ｆ ， Ｈ ｕ ａ ｎ ｇ 　 Ｆ 　Ｌ ， Ｌ ｉ ｎ 　Ｃ 　Ｊ ．Ｄ ｕ ａ ｌ 　ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　ｄ ｅ ｓ ｃ ｅ ｎ ｔｍ ｅ ｔ ｈ ｏ ｄ ｓ 　ｆ ｏ ｒ 　ｌ ｏ ｇ ｉ ｓ ｔ ｉ ｃ 　ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ 　ａ ｎ ｄ 　ｍ ａ ｘ ｉ ｍ ｕ ｍ 　ｅ ｎ ｔ ｒ ｏ ｐ ｙ 　 ｍ ｏ ｄ ｅ ｌ ｓ［ Ｊ ］ ．Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ， ２ ０ １ １ ， ８ ５ （ １ ? ２ ） ： ４ １ － ７ ５［ １ ２ ］ Ｃ ｈ ａ ｎ ｇ 　 Ｙ　Ｗ ， Ｈ ｓ ｉ ｅ ｈ 　Ｃ 　Ｊ ， Ｃ ｈ ａ ｎ ｇ 　 Ｋ　Ｗ ， ｅ ｔ 　ａ ｌ ．Ｔ ｒ ａ ｉ ｎ ｉ ｎ ｇ 　 ａ ｎ ｄｔ ｅ ｓ ｔ ｉ ｎ ｇ 　 ｌ ｏ ｗ － ｄ ｅ ｇ ｒ ｅ ｅ 　ｐ ｏ ｌ ｙ ｎ ｏ ｍ ｉ ａ ｌ 　ｄ ａ ｔ ａ 　ｍ ａ ｐ ｐ ｉ ｎ ｇ ｓ 　ｖ ｉ ａ 　ｌ ｉ ｎ ｅ ａ ｒ Ｓ ＶＭ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　ｏ ｆ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 Ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ ， ２ ０ １ ０ ， １ １ ：１ ４ ７ １ － １ ４ ９ ０［ １ ３ ］Ｄ ｉ ｎ ｇ 　 Ｌ ｉ ｚ ｈ ｏ ｎ ｇ， Ｌ ｉ ａ ｏ 　Ｓ ｈ ｉ ｚ ｈ ｏ ｎ ｇ ．Ａ ｐ ｐ ｒ ｏ ｘ ｉ ｍ ａ ｔ ｅ 　ｍ ｏ ｄ ｅ ｌ 　ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎｏ ｎ 　ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ 　ｐ ａ ｔ ｈ 　ｆ ｏ ｒ 　ｓ ｕ ｐ ｐ ｏ ｒ ｔ 　ｖ ｅ ｃ ｔ ｏ ｒ 　ｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　ｏ ｆ 　Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ 　Ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ 　ａ ｎ ｄ 　Ｄ ｅ ｖ ｅ ｌ ｏ ｐ ｍ ｅ ｎ ｔ ， ２ ０ １ ２ ， ４ ９（ ６ ） ： １ ２ ４ ８ － １ ２ ５ ５ （ ｉ ｎ 　Ｃ ｈ ｉ ｎ ｅ ｓ ｅ ）（ 丁立中，廖士中 ． 基于正则化路径的支持向量机近似模型选择［ Ｊ ］ ． 计算机研究与发展， ２ ０ １ ２ ，４ ９ （ ６ ） ： １ ２ ４ ８ － １ ２ ５ ５ ）［ １ ４ ］Ｄ ｉ ｎ ｇ 　 Ｌ ｉ ｚ ｈ ｏ ｎ ｇ， Ｌ ｉ ａ ｏ 　Ｓ ｈ ｉ ｚ ｈ ｏ ｎ ｇ ．ＫＭＡ － α ： Ａ 　ｋ ｅ ｒ ｎ ｅ ｌ 　ｍ ａ ｔ ｒ ｉ ｘａ ｐ ｐ ｒ ｏ ｘ ｉ ｍ ａ ｔ ｉ ｏ ｎ 　ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ 　ｆ ｏ ｒ 　ｓ ｕ ｐ ｐ ｏ ｒ ｔ 　ｖ ｅ ｃ ｔ ｏ ｒ 　ｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　ｏ ｆ 　Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ 　Ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ 　ａ ｎ ｄ 　Ｄ ｅ ｖ ｅ ｌ ｏ ｐ ｍ ｅ ｎ ｔ ， ２ ０ １ ２ ， ４ ９（ ４ ） ： ７ ４ ６ － ７ ５ ３ （ ｉ ｎ 　Ｃ ｈ ｉ ｎ ｅ ｓ ｅ（ 丁立中，廖士中 ．ＫＭＡ － α ：一个支持向量机核矩阵的近似计算算法［ Ｊ ］ ． 计算机研究与发展， ２ ０ １ ２ ， ４ ９ （４ ） ： ７ ４ ６ － ７ ５ ３ ）［ １ ５ ］ Ｒ ａ ｈ ｉ ｍ ｉ 　Ａ ， Ｒ ｅ ｃ ｈ ｔ 　Ｂ．Ｒ ａ ｎ ｄ ｏ ｍ 　ｆ ｅ ａ ｔ ｕ ｒ ｅ ｓ 　ｆ ｏ ｒ 　ｌ ａ ｒ ｇ ｅ － ｓ ｃ ａ ｌ ｅ 　ｋ ｅ ｒ ｎ ｅ ｌｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ ［ Ｃ ］ ? ? Ａ ｄ ｖ ａ ｎ ｃ ｅ ｓ 　ｉ ｎ 　Ｎ ｅ ｕ ｒ ａ ｌ 　Ｉ ｎ ｆ ｏ ｒ ｍ ａ ｔ ｉ ｏ ｎ 　Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇＳ ｙ ｓ ｔ ｅ ｍ ｓ 　１ ９． Ｃ ａ ｍ ｂ ｒ ｉ ｄ ｇ ｅ ， ＭＡ ： Ｍ Ｉ Ｔ 　Ｐ ｒ ｅ ｓ ｓ ， ２ ０ ０ ７ ： １ １ ７ ７ － １ １ ８ ４［ １ ６ ］ Ｒ ａ ｈ ｉ ｍ ｉ 　Ａ ， Ｒ ｅ ｃ ｈ ｔ 　Ｂ．Ｕ ｎ ｉ ｆ ｏ ｒ ｍ 　ａ ｐ ｐ ｒ ｏ ｘ ｉ ｍ ａ ｔ ｉ ｏ ｎ 　ｏ ｆ 　ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓｗ ｉ ｔ ｈ 　ｒ ａ ｎ ｄ ｏ ｍ 　ｂ ａ ｓ ｅ ｓ ［ Ｃ ］ ? ? Ｐ ｒ ｏ ｃ 　ｏ ｆ 　ｔ ｈ ｅ 　４ ６ ｔ ｈ 　Ａ ｎ ｎ ｕ ａ ｌ 　Ａ ｌ ｌ ｅ ｒ ｔ ｏ ｎＣ ｏ ｎ ｆ 　ｏ ｎ 　Ｃ ｏ ｍｍ ｕ ｎ ｉ ｃ ａ ｔ ｉ ｏ ｎ ， Ｃ ｏ ｎ ｔ ｒ ｏ ｌ ， ａ ｎ ｄ 　Ｃ ｏ ｍ ｐ ｕ ｔ ｉ ｎ ｇ ．Ｌ ｏ ｓＡ ｌ ａ ｍ ｉ ｔ ｏ ｓ ， Ｃ Ａ ： Ｉ Ｅ Ｅ Ｅ 　Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ 　Ｓ ｏ ｃ ｉ ｅ ｔ ｙ ， ２ ０ ０ ８ ： ５ ５ ５ － ５ ６ １［ １ ７ ］ Ｖ ｅ ｄ ａ ｌ ｄ ｉ 　Ａ ， Ｚ ｉ ｓ ｓ ｅ ｒ ｍ ａ ｎ 　Ａ．Ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｔ 　ａ ｄ ｄ ｉ ｔ ｉ ｖ ｅ 　ｋ ｅ ｒ ｎ ｅ ｌ ｓ 　ｖ ｉ ａｅ ｘ ｐ ｌ ｉ ｃ ｉ ｔ 　ｆ ｅ ａ ｔ ｕ ｒ ｅ 　ｍ ａ ｐ ｓ ［ Ｊ ］ ． Ｉ Ｅ Ｅ Ｅ 　Ｔ ｒ ａ ｎ ｓ 　ｏ ｎ 　Ｐ ａ ｔ ｔ ｅ ｒ ｎ 　Ａ ｎ ａ ｌ ｙ ｓ ｉ ｓａ ｎ ｄ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎ ｃ ｅ ， ２ ０ １ ２ ， ３ ４ （ ３ ） ： ４ ８ ０ － ４ ９ ２［ １ ８ ］ Ｙ ａ ｎ ｇ 　 Ｃ ｈ ａ ｎ ｇ ｊ ｉ ａ ｎ ｇ ， Ｄ ｕ ｒ ａ ｉ ｓ ｗ ａ ｍ ｉ 　Ｒ ， Ｄ ａ ｖ ｉ ｓ 　Ｌ．Ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｔ 　ｋ ｅ ｒ ｎ ｅ ｌｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ 　ｕ ｓ ｉ ｎ ｇ 　 ｔ ｈ ｅ 　ｉ ｍ ｐ ｒ ｏ ｖ ｅ ｄ 　ｆ ａ ｓ ｔ 　Ｇ ａ ｕ ｓ ｓ 　ｔ ｒ ａ ｎ ｓ ｆ ｏ ｒ ｍ［ Ｃ ］ ? ?Ａ ｄ ｖ ａ ｎ ｃ ｅ ｓ 　ｉ ｎ 　Ｎ ｅ ｕ ｒ ａ ｌ 　Ｉ ｎ ｆ ｏ ｒ ｍ ａ ｔ ｉ ｏ ｎ 　Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｓ ｙ ｓ ｔ ｅ ｍ ｓ 　１ ６．Ｃ ａ ｍ ｂ ｒ ｉ ｄ ｇ ｅ ， ＭＡ ： Ｍ Ｉ Ｔ 　Ｐ ｒ ｅ ｓ ｓ ， ２ ０ ０ ４ ： １ ５ ６ １ － １ ５ ６ ８［ １ ９ ］ Ｃ ａ ｏ 　Ｈ ｕ ｉ ， Ｎ ａ ｉ ｔ ｏ 　Ｔ ， Ｎ ｉ ｎ ｏ ｍ ｉ ｙ ａ 　Ｙ．Ａ ｐ ｐ ｒ ｏ ｘ ｉ ｍ ａ ｔ ｅ 　Ｒ Ｂ Ｆ 　ｋ ｅ ｒ ｎ ｅ ｌＳ ＶＭ 　ａ ｎ ｄ 　Ｉ ｔ ｓ 　ａ ｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ 　ｉ ｎ 　ｐ ｅ ｄ ｅ ｓ ｔ ｒ ｉ ａ ｎ 　ｃ ｌ ａ ｓ ｓ ｉ ｆ ｉ ｃ ａ ｔ ｉ ｏ ｎ ［ Ｃ ］ ? ?Ｐ ｒ ｏ ｃ 　ｏ ｆ 　ｔ ｈ ｅ 　１ ｓ ｔ 　Ｉ ｎ ｔ 　Ｗ ｏ ｒ ｋ ｓ ｈ ｏ ｐ 　 ｏ ｎ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 ｆ ｏ ｒＶ ｉ ｓ ｉ ｏ ｎ － ｂ ａ ｓ ｅ ｄ 　Ｍ ｏ ｔ ｉ ｏ ｎ 　Ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ． Ｂ ｅ ｒ ｌ ｉ ｎ ： Ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ， ２ ０ ０ ８ ： １ ２ ０ －１ ２ ９［ ２ ０ ］ Ｓ ｔ ｅ ｉ ｎ ｗ ａ ｒ ｔ 　Ｉ ， Ｈ ｕ ｓ ｈ 　Ｄ ， Ｓ ｃ ｏ ｖ ｅ ｌ 　Ｃ． Ａ ｎ 　ｅ ｘ ｐ ｌ ｉ ｃ ｉ ｔ 　ｄ ｅ ｓ ｃ ｒ ｉ ｐ ｔ ｉ ｏ ｎ 　ｏ ｆ 　ｔ ｈ ｅｒ ｅ ｐ ｒ ｏ ｄ ｕ ｃ ｉ ｎ ｇ 　 ｋ ｅ ｒ ｎ ｅ ｌ 　Ｈ ｉ ｌ ｂ ｅ ｒ ｔ 　ｓ ｐ ａ ｃ ｅ ｓ 　ｏ ｆ 　Ｇ ａ ｕ ｓ ｓ ｉ ａ ｎ 　Ｒ Ｂ Ｆ 　ｋ ｅ ｒ ｎ ｅ ｌ ｓ［ Ｊ ］ ． Ｉ Ｅ Ｅ Ｅ 　Ｔ ｒ ａ ｎ ｓ 　ｏ ｎ 　Ｉ ｎ ｆ ｏ ｒ ｍ ａ ｔ ｉ ｏ ｎ 　Ｔ ｈ ｅ ｏ ｒ ｙ ， ２ ０ ０ ６ ， ５ ２ （ １ ０ ） ：４ ６ ３ ５ － ４ ６ ４ ３［ ２ １ ］ Ｆ ａ ｎ 　Ｒ ， Ｃ ｈ ａ ｎ ｇ 　 Ｋ　Ｗ ， Ｈ ｓ ｉ ｅ ｈ 　Ｃ 　Ｊ ． Ｌ Ｉ Ｂ Ｌ Ｉ Ｎ Ｅ Ａ Ｒ ： Ａ 　ｌ ｉ ｂ ｒ ａ ｒ ｙ 　 ｆ ｏ ｒｌ ａ ｒ ｇ ｅ 　ｌ ｉ ｎ ｅ ａ ｒ 　ｃ ｌ ａ ｓ ｓ ｉ ｆ ｉ ｃ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ． Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　ｏ ｆ 　Ｍ ａ ｃ ｈ ｉ ｎ ｅ 　Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇＲ ｅ ｓ ｅ ａ ｒ ｃ ｈ ， ２ ０ ０ ８ ， ９ ： １ ８ ７ １ － １ ８ ７ ４［ ２ ２ ］ Ｃ ｈ ａ ｎ ｇ 　 Ｃ 　Ｃ ， Ｌ ｉ ｎ 　Ｃ 　Ｊ ． Ｌ Ｉ Ｂ Ｓ ＶＭ ： Ａ 　ｌ ｉ ｂ ｒ ａ ｒ ｙ 　 ｆ ｏ ｒ 　ｓ ｕ ｐ ｐ ｏ ｒ ｔ 　ｖ ｅ ｃ ｔ ｏ ｒｍ ａ ｃ ｈ ｉ ｎ ｅ ｓ ［ Ｅ Ｂ ? Ｏ Ｌ ］ ．２ ０ ０ １ ［ ２ ０ ０ ７ － ０ ８ － ０ ６ ］ ．ｈ ｔ ｔ ｐ ： ? ? ｗｗｗ． ｃ ｓ ｉ ｅ ．ｎ ｔ ｕ． ｅ ｄ ｕ． ｔ ｗ ? ～ｃ ｊ ｌ ｉ ｎ ? ｌ ｉ ｂ ｓ ｖ ｍ