基于核的机器学习方法及其在多用户检测中的应用.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：0.92M 资料格式：pdf 举报版权申诉

qq_28339273-10534746-16359647967112996407.pdf-第1页.png

第1页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第2页.png

第2页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第3页.png

第3页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第4页.png

第4页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第5页.png

第5页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第6页.png

第6页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第7页.png

第7页 / 共13页

qq_28339273-10534746-16359647967112996407.pdf-第8页.png

第8页 / 共13页

文本预览

第 26 卷第 7 期 2005 年 7 月通信学报 Journal on Communications Vol.26 No.7 July 2005 基于核的机器学习方法及其在多用户检测中的应用周亚同，张太镒，刘海员（西安交通大学电子与信息工程学院，陕西西安 710049）摘要：阐述了核方法的基本原理与研究动机，分析了特征空间的性质，介绍了常见的核方法，给出了构建新核方法的步骤及需要注意的问题，指出了核方法值得关注的研究方向，展示了其在多用户检测中的应用情况，以其对核方法研究领域有较全面的把握。关键词：核方法；支持向量机；机器学习；再生核希尔伯特空间；多用户检测中图分类号：TP18 文献标识码：A 文章编号：1000-436X(2005)07-0096-13 Kernel-based machine learning method and the applications to multi-user detection: a survey ZHOU Ya-tong, ZHANG Tai-yi, LIU Hai-yuan (School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China) Abstract: The major characteristics of the feature space and present alternative methods and corresponding algorithms were analyzed. The steps to construct a novel kernel method and the future research issues were given. Finally the applications to multi-user detection using KM were explored. It is expected to understand KM comprehensively. Key words: kernel method; support vector machine; machines learning; reproducing kernel Hilbert space; multi-user detection 1 引言机器学习是人工智能技术中十分重要的一个方面，主要研究如何从观测数据出发得出目前尚不能通过原理分析得到的规律，利用这些规律去分析客观现象，对未来数据或无法观测的数据进行预测。简单地说就是用计算机来模拟人的学习能力，以达到自动获取知识的目的。有三类基本的机器学习问题[1]，它们分别是模式分类、函数回归与预测以及概率密度估计。近年来有一类被称为核方法(KM, kernel method) 的学习算法，在机器学习领域内掀起了阵阵波澜。核方法，或称核机器，是基于核的机器学习方法的简称。对一些只涉及样本间内积运算的机器学习方法，如果改变内积定义的方式，用事先定义的核函数取代内积，就可以得到与该学习方法对应的核方收稿日期：2004-11-25；修回日期：2005-04-28 基金项目：国家自然科学基金资助项目（40274019）法。用核函数取代内积的这种方式被称为“核技巧” (kernel trick)，通过应用核技巧由原学习方法得到相应核方法的过程被称为“核化”（kernelizing）。早在 1964 年，Aizerman 给出了势函数方法的收敛性证明[2]，拉开了核方法研究的序幕。1992 年Boser 与 Vapnik 等人借助核技巧构建支持向量机(SVM, support vector machine)[3]。1998 年 Schölkopf 等人对线性主成分分析(LPCA, linear principal component analysis)方法进行核化，得到了相应的核主成分分析（KPCA, kernel principal component analysis）方法[4]。从此许多学者基于Schölkopf 等人的思路将核技巧应用于各种包含内积运算的学习方法中，众多核方法源源不断地被构建出来。目前核方法已成为机器学习领域内的研究焦点之一，而作为最重要的核方法， SVM 更是焦点中的焦点。在机器学习领域内的学术杂志如《Machine Learning》、《Neural Computation》、

第 7 期周亚同等：基于核的机器学习方法及其在多用户检测中的应用 ·97· 《Journal of Machine Learning Research》和《IEEE Trans. on Neural Networks》等上有许多与核方法相关的文章，有的杂志还出版了专集。近年来与机器学习有关的著名国际会议如 ICML、NIPS、IJCNN 等都将核方法作为一个重要的讨论主题。很多研究机构建立了核方法的学术网站[5~7]，不少论文更是以其为研究对象[8~10]。目前国外已出版了一些关于核方法的专著[11,12],有的正准备出版[13]，还有的已经被译成中文[14]。是什么原因要研究核方法？目前核方法的发展状况如何？能否自己构建新的核方法？构建时要注意哪些问题？核方法有哪些值得关注的研究方向？面临哪些尚未解决的问题？它的应用前景如何？上面一系列问题的提出使得我们有必要对核方法作一个比较全面的评述，对上述问题的回答也就构成了本文的主体框架，因此本文结构安排如下：在第 2 节阐述核方法的基本原理后，第 3 节分析核方法的研究动机，第 4 节总结特征空间的性质，目的在于加深对核方法的理解。第 5 节先对常见的核方法进行归并，然后逐个进行介绍与比较，从而对核方法的研究进展有了清晰的印象，而且还可以举一反三，根据第 6 节提供的步骤和注意事项，自己动手构建新的核方法。第 7 节指出了核方法值得关注的研究方向，引领我们探索其未知领域。第 8 节展示核方法的应用情况，第 9 节总结全文。 2 核方法的基本原理 ) ) ,( 1,tx 1 ,…( 2,tx 2 R T }1,1 ∈ × 采样自( 以图 1 中的模式分类问题为例简述机器学习算法的核化过程。图 1(a)中分属于两类的 N 个独立样 ) ),tx ，本( Ntx ,N 其中 R 为原始输入空间， { T = − 代表类别标号集合。设变量 x 与t 之间存在一个未知的联合概率分布 xL 的集合 x x , , tx ，其中 x 的维数为d 。记 1 ), p 2 ( )T =t t t t , 2, 为χ。 L ，样， N N 1 =S X X N N 本均值为 m ，自相关矩阵为 / T ，协方 N 差矩阵为 Σ S mm 。 =X xL x x 1 )T − = ( ( N , , N N T 2 ) F T 设某学习算法基于准则 Γ 构造一个分类函数 :f R T→% ，且在构造过程中只涉及样本间的内积运算。如要得到该学习算法对应的核方法，首先通过某未知映射函数 : R F ϕ → 将 N 个样本映射 ) ( ) 到特征空间 F 中，得到 ( 1,tϕ x ,… 1 ( ) ( ) ( ∈ × ，并记 ( ) ϕ x x Nt ,N , ϕ ϕ 的 1 )ϕ χ ，R、F、χ和 ( 集合为 ( )ϕ χ 间的关系可参见第 4 节的图 2；然后在 F 中仍基于准则 Γ 构造新的分类 )iϕ ⋅x 函数 :f F )jϕ x 的运算就用事先定义的核函数 ( ( K x x 取 ,i 代之，经过上述步骤就得到了与原学习算法对应的核方法，且所得核方法中不含ϕ。 T→ ，构造过程中凡涉及到形如 ( ( ( ) 2,tϕ x 2 ( ) xL , ϕ , x ) ) N 2 j T ) x w , ，设其表达式为 ( f % 以 SVM 为例进一步细化上述原理性的叙述。 SVM 的思路最初来自在 R 中构造最优超平面 [1]。该最优超平面对应上文提 (optimal hyperplane)H2 到的分类函数 :f R T→% = b+w x ，w 为超平面的法向量。构造 2H 的准则 Γ 为：使过两类样本点中距 2H 最近的点且平行于 2H 的两个超平面 1H 与 3H 间的距离最大。现通过 ϕ → 将样本映射到 F 中，在 F 中仍基于准则 Γ 构造最优超平面 2H ， 1H 、 2H 与 3H 间的关系如图 1(b) 所示。此时 2H 与上文中的 :f F T→ 对应，相应的表达式变为 (1) ( ϕ= ) x w : R ( ( ϕ w F + x b ) ) f , T 上式中最优的 w 可以通过求解下面的约束优化问题得到 min { 1 2 2 w N + ∑ C ξ i } i 1 = ξ i i ) ⎡ ⎣ t i 1 − ≥ . .s t ( w x ϕ i b ⎤+ ⎦ = L N 1,2 (2) 上式中 iξ为松弛因子，正则化因子 C 控制着对错分样本的惩罚程度。将式(2)转化为相应的对偶规划[1]，拉格朗日因子 ( =α 由对偶规划求出，则 ( tα ϕ x ，将其代入式(1)有 i α α α N ) x α ( ( f ϕ 可得 = ∑w )T L = ) ) , , , N 1 2 i i i 1 = ，由于该式只涉及样本间的内 N i i 1 = ) ( ) t i x x i ( α ϕ ϕ ∑ b + 积运算，因此将 ( K 后该式的等号左边已与ϕ无关，因此变为 ( ϕ ϕx x x , i = ) ( ) )i x 代入，代入图 1 核方法与 SVM 基本原理图 f ( N ∑x ) = i 1 = t K α i i ( x x , i ) + b (3)

·98· 通信学报第 26 卷从 F 空间的角度看，式（3）是线性分类面函数（图 1（b）），因为在 F 中 ( K x x 被当作一个整体看待；但从 R 空间的角度看，式（3）是非线性分类面函数（图 1（c）），因为对 R 而言 K 是一个非线性函数。 ) , i 3 核方法的研究动机通过以上对核方法原理的分析，发现其研究动机至少可以从以下两个方面来理解。 ① 核方法在线性与非线性间架设起了一座桥梁。首先，核方法与通常的降维方法背道而驰，通过映射将 R 中的样本变换到 F 中，实现样本的升维；升维后的样本在 F 中变得非常稀疏，便于对其实施线性学习算法。例如对于模式分类而言，Cover 关于模式可分性的定理就指出[15]：一个复杂的模式分类问题被非线性投影到 F 中以后，该模式比在原始空间中更可能线性可分。因此核方法通过升维使问题得以简化。其次，从第 2 节可以看出，由于 F 与 R 间的映射是非线性的，因此在 F 中实施的线性算法从 R 空间的角度看是非线性的，这样核方法可以看作是相应线性算法的一个非线性版本，换句话说，核方法提供了学习算法非线性化的一条新途径。学习算法非线性化的另一条途径是：直接从待分析样本本身的分布出发，希望能找到很好描述其内在结构的非线性模型。例如对于 LPCA 方法，若按前述两种途径进行非线性化，可以分别得到 KPCA 方法和主曲线（PC, principal curves）[16]方法。两种非线性化途径各有优势：前者原理简单，计算复杂度相对较小；后者对样本的本质特征捕捉更准确。但两者目的都是为了能更准确地描述给定样本集的内在结构。 ) ( x x x , i ( ϕ= ② 在核方法中有等式代换 ( K ) ⋅ )iϕ x ，如果 F 的维数很高，上式等号右边的计算量会很大，甚至会陷入维数灾难而使得计算不可行；但通过上述代换， F 中的内积可基于 R 中的变量通过给定的核函数直接计算得到，即使 F 的维数非常高，核方法本身也并没有增加多少计算复杂度。特别是对某些映射函数而言， F 的维数是无限的，此时内积必须用积分来计算，这种代换的作用就更加明显。综上所述，核方法在线性与非线性间架设起一座桥梁，同时通过引入核函数回避了维数灾难，也没有增加计算复杂度，这正是它受到高度关注的原因。SVM 作为一种核方法，显然也具有上述的优势；但作为最重要的核方法，它的研究动机不仅仅于此。SVM 最重要的意义在于它撼动了传统机器学习方法一直作为自己根本出发点的诸多假定，使得我们去关注许多以往被视为理所当然的做法，从本质上推动了对学习过程的认识。 ) ( p ), 在图 1（b）中，根据 Bayes 决策理论，若知道 ( tϕ x ，就可以通过使期 ) =w ) x 最小化求得最优分类 ( F 中样本的联合分布望风险（为讨论方便假定 ϕ 已知） ( R ) ( ( ) ( ∫ p L t f d , ϕ ( ( ) ( ( ) f ϕ x w 为用 ( 面 ( L t f ϕ x w 对 f ϕ x w ， , ( ), t 进行预测而造成的损失。在实际中由于 ( ) tϕ x p ( )0 ( ) f ϕ x w 是不 , 未知，想直接通过 ) x w , )0 ( ( ϕ ) , ) w 求取 , ) ) ) ) ( t , , min R w i N , f 1 = ) ) w R emp ( ( ϕ ( L t i 然后通过 min R w 1 = ∑ N ) ( w 求出分类面可能的；根据概率论中的大数定理，很自然想到用 x w 代替 R(w)，经验风险 ( i ) , ( f ϕ x w ，这就是所谓的经验风险最小化（ERM, empirical risk minimization）原则。传统的机器学习方法如感知器（perceptron）[17]采用的感知准则实际上就是 ERM 原则。 ) ( emp emp ) ) , ( ) w 依概率收敛于 ( ) ERM 原则只是一种看似合理的做法，在大样本前提下是可行的，毕竟当样本数目趋于无穷时， R w 。但在小样本前提下 empR ERM 原则存在问题，因为并不能保证通过 ) w 获得的分类面是一样的。 min R w Vapnik 对上述问题进行了系统研究，并逐步形成了一个较完善的理论体系—统计学习理论(SLT, statistical learning theory)[1]。SLT 指出， ( R w ≤ R 以至少1 η− 的概率成立，上式中 emp ) h Nφ+w min R w ) w 和 emp ) ( ( ( ( ) = ( /h Nφ 范围，变量 h 被称为 VC 维，它是分类面复杂程度的度量，关于 VC 维更详细的解释见文献[1,14,17]。在小样本前提下可以令被称为置信 / ) ( ( ) ( = w R str + ( min R str w w ) ) w 代替 R emp min R w ( h Nφ ) w 求取分类面，这种然后用做法被命名为结构风险最小化（SRM， structure risk minimization）原则， ( strR w 被称为结构风险，它是期望风险的一个上界，因此 SRM 的实质是通过 (4) ) / ( ) ( h ln 2 / N h ln ( η / 4 ) ) ) 1 + − N

第 7 期周亚同等：基于核的机器学习方法及其在多用户检测中的应用 ·99· 使期望风险的上界最小来达到使期望风险本身最小的目的。 SVM 正是用 SRM 作为学习原则：将式（4） ∑ 项代表经与式（3）对比后发现，式（3）中的 ξ i N i 1 = 2 2 2 ) 1 1 2 /h Nφ 验风险，而 1 2 d∆⎡ r , ⎣ w ≤ 的前 w 项反映的则是置信范围 ( ∆ 2 的大小，因为 Vapnik 已证明[1]：在提下，由 SVM 生成的分类面的 VC 维满足 h ≤ ⎦ 其中 r 为包含 N 个样本的最小超球 min ⎤ + 的半径。由于结构风险不仅包含了经验风险，而且考虑了分类面的复杂程度；相应地，SRM 原则也不是一味强调使经验风险越小越好，而是在经验风险与分类面复杂程度间实现折衷，因此基于 SRM 原则的 SVM 比基于 ERM 原则的传统机器学习算法显得更为合理，也改变了被传统方法视为理所当然的做法。 4 特征空间的性质核方法是在特征空间 F 中实施的，F 的结构与度量等性质直接决定着核方法的性能。本节从以下 4 个方面总结其性质。 4.1 特征空间是一个再生核希尔伯特空间再生核希尔伯特空间（RKHS, reproducing kernel Hilbert space）是 Hilbert 空间上线性有界泛函的集合，一个 RKHS 有惟一的再生核与之对应。 RKHS 最突出的性质是其再生性：设 H 是一个 RKHS ， ( K x x 是其再生核，则 f H∀ ∈ ，有 ( f x x 成立，其中 H,⋅ ⋅ 表示 f , 定义在 H 上的内积。关于 RKHS 的更多性质可参见文献[18]。前述特征空间 F 也是一个 RKHS，事先定义的核函数就是其再生核。 4.2 映射函数与核函数的关系 ) ,i j ) Kx j )i =x ) H ( ( , i j j 如第 2 节所述，通过ϕ将 R 中的 N 个样本映射到 F 中，由于ϕ是未知的，这个映射实际上是由事 ) 先定义的核函数 ( K x x 完成的，因此有必要研究 ,i 二者间的关系。如果 ( K x x 比较特殊，由它可以 ,i 直接推知ϕ，比如已知 ( K =x 推知ϕ将 R 中的样本 i ( x 2 i 1 ( )2 x x ，可以 i )iϕ =x 映射成 ( x 。Mercer 定理[19]则指出了 ( ) K x x ,i ) j x x ,i j ( x , i 1 x x i i 1 = ) , 2 ) x i 2 i 2 ) , ⋅ 2 2 j j 与ϕ间的解析关系。 4.3 特征空间中点的原像问题 i i N 1 = ) − = 比如 ρ ψ ϕ ( cψ ϕ i 如图 2 所示， ( )ϕ χ 中的每个点均能在 χ中找到对应的原像，但并非 F 中的每个点ψ都存在原像。 = ∑ x 显然是 F 中的一个点，但它在 R 中不一定有原像。由于核方法中的一些变量如 SVM 的法向量 w 和 KPCA 提取的主方向都具有ψ的形式，因而非常有必要求出其原像。目前有两种求取原像的方法：第一种是在 R 中寻找ψ的一个近似原 ( ) 2 像 z，使得 z 尽可能的小；第二种是在 R 中寻找一个缩减集（reduced set）{ } 1 z ，且 cN i ′ = ∑ z ，当 1zN = 时第二种方法就退化为第一种方法。上述第一种方法还可以作如下推广：在 R 中同时寻找 M 个点 2 M { } 1 ( ) z kψ = 尽可能的小[20]。对于上述第一种方法，Burges 最早通过用梯度法搜寻ρ的极值而求得原像 z [21,22]，后来 Schölkopf 等人将之发展成原像算法（PA, pre-image algorithm），并对上述两种方法都适用[23]。PA 方法采用的是逐步逼近的思想，最终的原像以迭代方式给出。 2ψ ψ′− 尽可能的小，其中的共同近似原像z，使得ρ= ( ψ βϕ −∑ N<< ， ψ ϕ 使得 zN i= ) zN 1 = 1 = M k k k i i i 图 2 特征空间中点的原像示意图 4.4 特征空间中的度量 Amari 指出 ( )ϕ χ 是作为一个弯曲的黎曼子流型嵌入到 F 中的（见图 2）[24]。这种嵌入在χ中导入了黎曼度量，它能表征χ中的一个非常小的量 dx 被映射 )dϕ x ，到 F 中后的变化幅度。设 dx 在 F 中的像为 ( ，且 ( )dϕ 则 ( =x ϕ ∑ x ( i , 黎曼张量。另外χ中一个非常小的体积元 1 被称为黎曼距离，其中 ( ijg ) x 被称为 ∂ ∂∑ x i ) dx dx dx dx L ∇ϕ = ⋅ ( ϕ dx i g = x x x d d ) ) ij 2 i j j i

·100· 通信学报第 26 卷 ndx 在 F 中的映射为 det L ，其中 ) x 表示体积元经映射后的膨胀系数。在 F dx dx 2 dx n det ijg g x ( ij 1 ( ) 中除了可以定义黎曼距离和欧氏距离外，还可以定义其它度量，比如在文献[25]中定义了 F 中两点间的 Mahalanobis 距离，在文献[23]中定义了 F 空间的曲率，在文献[26]中定义了 F 空间中的中心距离等。上述度量的共同特点是与ϕ无关，因此基于这些度量可构建新的核方法。 5 常见的核方法常见的核方法可分为有监督型和无监督型。前者所处理的样本集的类别归属已事先标定，后者主要用来处理未被标定的样本集。本节并不准备对常见的核方法进行简单罗列，而是先对其加于整理和归并，然后将重点放在方法间的比较上。 5.1 有监督型核方法在常见的有监督型核方法中，SVM 是最典型的例子。除此之外，还有一批该类方法如核 Bayes 判别[27]、核 Fisher 判别（KFD, kernel Fisher discrimin- ant）[28]、核感知器（KP, kernel perceptron）[29]和核最小平方误差（KMSE, kernel minimum squares error）判别[25]等，它们分别由经典的线性判别方法如 Bayes 判别、Fisher 判别、感知器和 MSE 判别核化而来，因此我们将之归并为“基于核的判别方法”。这些方法与相应的线性判别方法相比，最显著的区别是能进行非线性判别。上述方法间的关系见图 3，图中横向双箭头代表有条件的等价关系，纵向单箭头代表核化方向。图 3 各种判别方法间的关系在已知样本的类先验概率密度和类条件概率密度的前提下，Bayes 判别根据样本的后验概率大小决定其类别归属，它的判别结果从理论上来说是最优的。但在许多实际问题中由于样本类条件概率密度很难确定，往往从样本集出发直接构造判别函数而得到相应的判别方法，比如 Fisher 判别、感知器和 MSE 判别等。其中 Fisher 判别通过使广义 Rayleigh 商 JF 极大化而求得判别函数的法向量 w。Rosenblatt 提出的感知器则是机器对学习过程进行数学研究的 N 2 2 T N N N− X w t 极小化而求得法向量真正开始，它通过使感知准则 Jp 极小化而求得判别函数的法向量。而 MSE 判别通过使平方误差准则 SJ = +=w S X t ，其中 +S 是样本自相关阵 S 的伪逆。上述判别方法间有紧密的联系，并且在某些条件下是等价的。比如若两类样本均服从高斯分布且二者的协方差矩阵相等时，Bayes 判别等价于 Fisher 判别[17]；当 Js 中的向量时，MSE 判 =t N 别等价于 Fisher 判别， 1N 和 2N 分别是两类样本的个 ( )T 1,1, 1 数；又比如当样本数 N → ∞ 时，若令 L ，则 MSE 判别以最小平方误差逼近 Bayes 判别。 N N N N N N 1 N N N =t )T L L ( / / , 1 , 2 / , / 2 ) ) ) )ϕ x 在 w 上的投影。另外 Mika 等人将 ( 基于核的判别方法就是上述线性判别方法核化后的结果。比如 Gestel 等人提出了核 Bayes 判别方法[27]，但该方法要求两类样本映射到特征空间 F 后仍然服从高斯分布且二者的协方差矩阵相等，显然该条件很难满足。在核 Fisher 判别中，由于广义 Rayleigh 商 JF 是ϕ的函数，因此必须将之变形为 J τ 且与ϕ无关，然后通过最大化 ( ( J τ 求出 τ 。尽管此时法向量 w 仍无法求出，但能求出 F 中的样本 ( J τ 极大化问题转化成使两类样本的平均边界（average margin）距离最大的优化问题[30]。Cooke 提出了 Fisher 判别的两种改进方法，并指出这两种改进方法都能被核化[31]。感知器只能对线性可分的两类样本进行判别，而 Xu 等人提出的核感知器[29]则可适用于非线性可分的情形。另外 Keller 和 Hunt 在感知器的基础上提出了模糊感知器（FP, fuzzy perceptron）[32]。Chen 等人将 FP 核化，构建了相应的模糊核感知器（FKP, fuzzy kernel perceptron）[33]，实验表明 FKP 的性能可与 SVM 相比。KMSE 判别是 MSE 判别对应的核方法，尽管在 F 中矩阵 S 因含有ϕ无法求出，但 Ruiz 等人给出了计算 +S 的方法[25]，因此最小平方误差准则在 F 中仍可实施，这意味着 KMSE 算法是可行的。值得指出的是，就像各种线性判别方法间存在紧密联系一样，上述由此导出的基于核的各种判别方法间也存在着紧密联系，而且容易推知它们中的一些方法在一定条件下是等价的，对这种等价性关系的深入探讨是核方法值得研究的方向之一。 5.2 无监督型核方法无监督型核方法最典型的例子当数 KPCA。另外还有一批该类方法，如核规范相关分析（KCCA, kernel canonical correlation analysis）[34]和核独立成分

第 7 期周亚同等：基于核的机器学习方法及其在多用户检测中的应用 ·101· 分析(KICA, kernel independent component analysis)[35] 等，它们与信号处理领域里的盲源分离（BSS, blind source separation）问题是紧密联系在一起的，因此我们将之归并为“基于核的盲源分离方法”。此外还有核聚类[36]、核投影寻踪（KPP, kernel projection pursuit）[37]等。 LPCA 是一种重要的无监督学习方法，它可以在信息损失最小的前提下对样本进行降维处理，实现高维数据的可视化，提高分析者的洞察能力和分 λ=Σv v 析效率。LPCA 通过协方差阵的特征值分解获得样本的第 h 个主成分 hy 及与之对应的第 h 个主方向 hv 。但在特征空间 F 中由于 Σ 是ϕ的函数，无法通过 Σ 的分解求得主方向 h ϕv 。因此 KPCA 方法用输出观测值 x=g(As)来提取信号源 s，有关 BSS 的综述可参见文献[39,40]。ICA 可能是 BSS 中用得最广泛的一种方法，但 ICA 是一种线性方法，若 g 是非线性函数，ICA 一般不能对 x 进行有效分离；而 KICA 等基于核的方法是相应线性方法的一个非线性版本，只要核函数设计合适，它可以对 x 进行有效分离，从这也可看出核方法的优势。最近 Dominique 等[41]和 Harmeling 等[42]还分别提出了一种新的基于核的盲源分离方法，前者是将 Stone 的算法[43]核化，后者是将 Ziehe 的 TDSEP（temporal de-correlation source separation）算法[44]核化。 N hj ) 令 ( = ∑v x ，转而通过核矩阵 NK 的特征值 ϕ αϕ j h j 1 = α 求取 α ，其中 ijα 是 α 第i 行第 j 列 K α Nλ= 分解 N )ϕ x 在 F 中的第 h 个主成分 hyϕ = 的元素。最终求出 ( ) K ，其中( ) ( x x 。 h N hj )ϕ x 值得注意的是：尽管 F 的维数很高，但在 F 中 ( 最多只有 N 个主成分。 ) x v ϕ ⋅ h hj K= ( ϕ N = ∑ j 1 = α hj K N ) ( , j LPCA 旨在寻找一个最佳的投影方向（第一主方向），它通过使样本投影的方差最大化来达到目的，最终转化成求解矩阵的特征向量问题；而规范相关分析(CCA, canonical correlation analysis)同时寻找多个最佳的投影方向，它通过使各样本投影间的相关性最大来达到目的，最终转化成求解矩阵的广义特征向量问题。与 LPCA 有对应的核方法 KPCA 一样，CCA 也有对应的核方法 KCCA[34]。另外我们知道，若两个变量不相关，它们不一定独立。 LPCA 只能保证抽取的各成分间互不相关，而 Jutten 等提出的独立成分分析（ICA, independent compon- ent analysis）方法[38]能保证抽取的成分间相互独立。 Bach 等人则构建了与 ICA 对应的核方法 KICA[35]。 KICA 方法有两种实现方式：一种是 KICA-KCCA，即用 KCCA 方法来计算 KICA 中的对照（contrast）函数；另一种是 KICA-KGV，即是用核广义方差（KGV, kernel generalized variance）方法计算对照函数。上述 6 种无监督学习方法间的关系见图 4，其中计算复杂度最大的方法是 KICA。所谓盲源分离（BSS）就是在信号源 s、传输信道 A 和混合函数 g 完全或部分未知的情况下，只利图 4 6 种无监督学习方法间的关系 6 构建新的核方法当掌握了核方法的基本原理、洞察了特征空间的性质后，可模仿已有的核方法，自己动手构建新的核方法。以下给出构建步骤：（1）选择合适的学习算法将其核化。所谓“合适”首先要求学习方法只能含有样本间的内积运算。其次要求学习方法的复杂度不能太高，因为内积运算通常是包含在矩阵运算里的，核化时用核函数取代内积的过程并不象 SVM 那样简单，这从第 5 节对各种核方法的介绍中也可看出；如果学习方法过于复杂，不仅核化过程异常烦琐，而且所得核方法因复杂度过高而失去意义。（2）根据核方法的处理对象设计合适的核函数。（3）模型选择。另外本节也指出了构建核方法时应注意的问题。 6.1 设计合适的核函数在第 4 节曾提到特征空间 F 的性质直接决定着核方法的性能，事实上 F 的性质又是由相应的核函数来决定的，由此可见设计合适的核函数的重要性。在实际应用中，往往根据新构建核方法要处理的对象类型设计新的核，有时候也基于核函数的性质将现有的核改换成新的核，比如核的嵌入（embedding）[45]和核的模糊化（blurring）等。在文献[13]中有更为详尽的阐述。当新构建核方法的处理对象是多媒体数据时，由于多媒体数据处理中会产生大量的低层次特征提

·102· 通信学报第 26 卷取子（extractor），经这些提取子生成的媒体元数据通常是符号化数据，若用通常的核函数进行处理，首先必须对这些符号化数据进行量化；为此可以借鉴 Aradhye 等人提出 M 元汉明（M-ary hamming）核和编辑距离(edit-distance)核[46]的做法，设计能直接处理符号化数据的核。特别地，若处理对象为语音，可直接利用 Jaakkola 等人设计的 Fisher 核[47]，因为 Fisher 核不仅可利用高斯混合模型产生的信息，而且不需要所有样本的维数是相同的。 , , j j x x d 1 κ= j j x jd ， 1, j x i 1, )T x id , j κ x i κ −x i x x i L L = ∏ L L ( K x xκ κ , i j ) ) ， ( =x j 当新构建核方法的处理对象是高维样本时，可根据 Vapnik 提供的方法[1]设计高维核：若一个 d 维空间可以分解成d 个一维空间的张量积，且定义在第 κ个一维空间上的核为 ( xκ κ ，则定义在d 维空 K x ,i 间上的多维核可表示为 ( K ) )T 其中 ( 。 =x i 当要求新构建的核方法具备良好的逼近能力时， = 可借鉴如下做法：高斯核的一般形式为 ( K ，它的距离度量 ( d exp ( j−x x 基于 2L 范数；Ribeiro 将之换成 Minkovsky i 范数[48]，逼近实验表明参数σ较大时，Ribeiro 的新核比高斯核的逼近误差小。低阶的多项式核和σ 大的高斯核推广能力好但逼近能力差，高阶的多项式核和σ小的高斯核与之相反，为此 Smits 等人用上述两种核的混合来保证核方法同时具有好的逼近和推广能力[49]。而邵等人采用的是分步逼近的方法[9]：先用一个小σ的高斯核逼近目标函数，得到一个逼近误差；再用另一个大σ的高斯核去逼近这个误差。 x x ,i x x ,i 2 2 j σ 2 / 2 ) ) = ) − x 2 当新构建核方法的处理对象有可以利用的先验知识时，可以在设计核时引入这些先验知识。比如在模式分类中就存在着一些先验知识：待分类图像经平移、旋转和加粗等变换后其类别保持不变；图像的每个像素只与其邻近像素存在相关性等。称前者为不变性先验，称后者为马尔科夫性先验。在设计这类核时下面的做法值得借鉴：Decoste 等人利用不变性先验知识设计抖动核（jittering kernel）[50]，他们将样本的平移、旋转等变换统称为样本的抖动，核 ( x x ， q 其中 qx 是 ix 经抖动后得到的众多像中与 jx 间的欧 K x x 对应的抖动核 ( K x x i K= ,i ) ( ) ) , , I j j j 氏距离最小的一个。Haasdonk 等人设计的切距（tangent distance）核也利用了不变性先验知识[51]，因为切距具有群变换下的不变性，将高斯核中的 2L 范数换成切距后就得到了切距核。Barzilay 等人基于图像的马尔科夫性先验提出邻域核的概念[52]。他们在核函数内只让相邻像素而不是所有像素参与内积运算。Schölkopf 同样基于图像的马尔科夫性先验提出了局部相关核[53],他们只让将图像 x 和 y 中两个子块内的像素参与内积运算。 6.2 模型选择对新构建的核方法而言，核函数的设计确实重要，但当核函数设计完毕、也即核函数的类型固定后，如何确定核函数中待定参数（简称核参数）的最优值同样重要，这就是所谓的模型选择问题。若新构建的核方法是用于样本分类，比较常用的模型选择方法是留一法（leave one out）[54]或交叉验证法（cross validation）。所谓留一法是从 N 个样本中取出一个后，用剩下的 1−N 个样本训练核方法，然后用取出的那个样本测试核方法；再把取出的样本放回，又取出另外一个样本，将这个过程重复 N 次并统计测试时被错分的样本总数 k ，最后用 Nk / 作为留一法对核方法分类错误率的估计。交叉验证法是留一法的推广，与留一法不同的是它每次取出多个样本而不是一个样本。用留一法或交叉验证法进行模型选择时，每给定一个核参数，都将其代入到核方法中，然后算出分类错误率的估计值 ˆε，使 ˆε 最小的核参数即为所求，上述做法的缺点是计算量大。 ˆ =ε 如果我们构建的是 SVM，还可以像 Kwok 那样将 SVM 置于显著度框架（evidence framework）中，用显著度框架的第二级推理实现正则化因子C 的选择，用第三级推理实现核参数的选择[55]。也可以像 Cristianini 等人那样通过最小化 SVM 分类错误率的上界来达到模型选择的目的，因为他们已经证明了分类错误率的上界是核参数的平滑函数[56]。 6.3 构建新的核方法时应注意的问题在构建新的核方法时一个特别容易忽视的问题：一些学习方法是有相应的假设前提的，当这些学习方法被核化而得到与之对应的核方法时，上述假设前提作为学习方法的一部分同样被核化，此时应首先检查核化后的假设前提在特征空间 F 中能否成立。比如 Bayes 判别的假设前提是 R 中两类样本

第 7 期周亚同等：基于核的机器学习方法及其在多用户检测中的应用 ·103· 均服从高斯分布且二者协方差相等，因此与之对应的核方法——核 Bayes 判别的假设前提是两类样本映射到 F 中以后仍服从高斯分布且二者的协方差矩阵相等。由于样本映射到 F 中后变得稀疏，再假设其服从高斯分布就比较勉强，因此在 5.1 节就已指出该假设前提很难满足。再比如 LPCA 通常是在样 0=m 的假设前提下得到特征值分解公式，本均值因此与之对应的核方法 KPCA 要求样本映射到 F 中以后其均值 ( ϕ 仍等于零，显然该 ( ϕ = ∑m ) x i N ) / N i 1 = 假设前提很难满足；为此 Schöl- kopf 通过对核函数进行归一化处理来规避上述假设[4]。 7 核方法值得关注的研究方向核方法目前的发展使得我们有必要认识其存在的问题与值得关注的研究方向。考虑到 SVM 的特殊地位，现从以下两个方面进行论述。 7.1 一般核方法值得关注的研究方向 j j ) ,i ,i 我们认为核方法目前有以下五个值得关注的研究方向。(1)从样本中学习核矩阵 NK 。在很多核方法 ) 中，最终参与运算的是 NK 而不是核函数 ( K x x 。如果能从样本提供的信息中通过学习的方式自动得到 NK ，比事先指定一个 ( K x x 进而得到 NK 要更合理些。目前已提出了多种核矩阵学习方法：比如 Lanckriet 的半正定规划（SDP, semi-definite programming）方法[57]，Bousquet 的基于梯度的方法[58]，Crammer 的基于提升算法的方法[59]，Tsuda 的基于 EM 算法的方法 [60] 和 Zhang 的基于 Tanner-Wong 算法的方法等[61]。由于核矩阵学习的计算量大，上述方法无不是在减少计算量方面各显其能。考虑到还没有哪一种方法能在减少计算量方面明显胜出，因此值得进一步去研究。 (2) 高斯过程（GP, Gaussian processes）模型[62]。高斯过程也称正态过程，是最重要的随机过程之一，当其用于解决机器学习问题时被称为 GP 模型。 GP 模型是一种重要的核方法，模型中的协方差函数实际上就是核函数。GP 模型与 SVM 有紧密的联系，Sollich 曾指出[63]：SVM 可以理解成显著度框架下某推断问题采用了 GP 模型的先验知识和合适的似然函数后得到的最大后验概率解。目前对 GP 模型的学习曲线（learning curve）及其上下界[64] 研究较多，也有学者研究 GP 模型与其他模型的结合[65]。 (3) 寻找已有核方法的快速算法，这是核方法用于实时处理的关键。比如 Smola 等[66]提出一种被称为稀疏核主成分分析(SKPCA, sparse kernel principle component analysis)的快速算法，提高了 KPCA 的计算速度。 (4) 核函数设计与模型选择。尽管在第 6.1 和 6.2 节中已用较大篇幅对此加于论述，但由于该问题对核方法的重要性，因此还需进一步研究。 (5) 拓展核方法的应用领域，比如探索其在多用户检测和智能多媒体等领域中。因为理论和应用往往相辅相成，核方法良好的应用效果会反过来推动理论不断向前发展。 7.2 SVM 值得关注的研究方向我们认为 SVM 有以下 8 个值得关注的研究方向。(1)SVM 的算法改进。自 SVM 提出后，出现了大量改进算法，它们大致可以归并为三类：第一类是引入新参量或者新约束条件，比如 Lin 提出的 FSVM（fuzzy SVM）[67]事先给每个样本指定一个隶属度因子，用于度量样本在参与构建分类面时的贡献。第二类是精简训练样本集，比如 Yang 等[68] 首先找出样本集中的卫向量（guard vector）,然后在卫向量的基础上构建 SVM。第三类是与现有的机器学习方法相结合，比如卢等[69]将 SVM 与主动学习方法结合，提出了交互式 SVM 算法。根据上述 3 种思路，我们完全可以提出自己的改进算法。 (2) SVM 的快速算法。目前 SVM 快速算法可分为两类，第一类是基于分解迭代的思想，即将原始的二次规划问题分解成若干规模较小的子问题求解；第二类是基于转换的思想，将 SVM 转换成另一类容易求解的问题。前者如 Platt 的序贯最小优化(SMO, sequential minimal optimization)算法[70]等，后者如 Keerthi 等人提出的最近点迭代算法(NPA, nearest point algorithm)[71]等。两类算法离对样本进行实时处理均还有差距，因此寻找更优的快速算法对 SVM 而言有决定性意义。 (3) 多元分类 SVM。经典的 SVM 方法只能用于两类样本的分类，而多元分类 SVM（multi-class SVM，MSVM）具有对多类别样本分类的能力。目前 MSVM 算法大致可分为组合型和整体型两类，前者如 Sebald 等人构造的 M-ary SVM[72]，后者如 Weston 等人提出的方法[73]。Hsu 等[74]对二者进行详细比较后指出，若综合考虑分类准确率、算法复杂度等指标，没有一类方法占有绝对优势；而且当样

分享到：

赞收藏

资料库

基于核的机器学习方法及其在多用户检测中的应用.pdf

相关推荐

人工智能

热门标签

最新资料