（模式识别与智能系统专业论文）核方法信号处理在多用户检测中的应用.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 随着社会的发展，科学技术的进步，人们对无线通信技术的发展要求越来越高，移动 通信系统正朝着数字化、高速化和多媒体化方向发展，信号传输速率不断提高。因此，对 移动通信系统的设计提出了更高的要求，只有采用先进的多址接入方式以及现代数字信号 处理技术，才能实现高容量、高质量的移动通信。 现在普遍使用的多址接入方式有频分多址、时分多址以及码分多址，其中码分多址较 之频分多址、时分多址，具有更高的频谱利用率、系统容量以及其他优良特性。采用码分 多址技术，能满足现在以及将来一段时间内人们对移动通信的需要。但码分多址也有其不 足之处，码分多址存在多址干扰，多址干扰限制了系统的容量，同时也使远近效应的影响更 严重。为了消除或者抑制多址干扰，必须使用多用户检测技术。 目前，国内外学者在多用户检测技术领域做了大量的研究工作，概括为以下几类与空 时二维信号处理技术相结合、与多载波调制技术相结合、与智能天线技术相结合以及与智 馆邑算法相结合的多用户检测技术。本文研究了将核方法与多用户检测技术相结合，并通过 仿真实验验证了方法的有效性，得到了满意的结果。 本文的研究工作主要包括如下： 第一，在介绍c d m a 通信系统模型的基础上，分析了几种经典多用户检测器的性能， 并指出了每种检测器的优缺点。 第二，阐述了核方法的基本理论并分析支持向量机应用于c d m a 系统的可能性。 第三，研究了一种在线的支持向量机多用户检测方法( f o s v c ) 。该算法利用k k t 条 件判别实时增加的训练序列并构造当前训练样本集，从而能够有效地减少训练样本大小， 加快训练速度。仿真实验表明，该算法在不影响分类效果的情况下大大加快了训练速度， 且用于分类的支持向量较少，同时性能与传统支持向量机算法相当且明显优于m m s e ( r l s ) 多用户检测器。 关键词：码分多址多用户检测 核方法支持向量机 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fs o c i e t y , m o r ea n dm o r et h er e q u i r e m e n to fw i r e l e s s c o m m u n i c a t i o n ，i td r i v e st h em o b i l ec o m m u n i c a t i o nt e n d i n gt od i g i t a l 、f a s ta n dm u l t i m e d i a t h u s ， w er e q u i r em o r er i g o r o u sd e s i g nf o rm o b i l ec o m m u n i c a t i o n w eh a v et oa d o p tm o r ea d v a n c e m u l t i p l ea c c e s st e c h n i q u e sa n dd i g i t a ls i g n a lp r o c e s s i n gt e c h n i q u e st or e a l i z eh i g hq u a l i t ya n d c a p a c i t yc o m m u n i c a t i o n n o w , t h et d m a ，f d m aa n dc d m a a r ew i d e l yu s e di nt h ew o r d ，w h i l et h ec d m ah a v e h i g h e rs p e c t r u mu t i l i z a t i o nr a t e ，l a r g e rc a p a c i t ya n dm o r ee x c e l l e n tp r o p e r t yt h a nt d m aa n d f d m a ，s oc d m at e c h n i q u ec a ns a t i s f yp e o p l e sr e q u i r e m e n tf o rm o b i l ec o m m u n i c a t i o ni nt h e f u t u r e b u tt h em a i ( m u l t i p l ea c c e s si n t e r f e r e n c e ) w h i c ha c c o m p a n i e si nc d m as y s t e ml i m i t st h e c a p a c i t yo ft h ec o m m u n i c a t i o na n de n h a n c e st h en e a r - f a re f f e c t s ow em u s ta d o p tm u l t i u s e r d e t e c t i o nt or e s t r a i no re l i m i n a t et h em a i s of a r , r e s e a r c h e r so v e rt h ew o r l dh a v ed o n eal o to fr e s e a r c hw o r ka b o u tm u l t i u s e r d e t e c t i o n ( m u d ) ，i t c a nb e g r o u p e d i n t ot h e s ec l a s s e s ：c o m b i n a t i o no f s p a c e t i m e t w o d i m e n s i o n a l t e c h n o l o g y , c o m b i n a t i o n o fm u l t i c a r t i e rw a v em o d u l a t i o nt e c h n o l o g y , c o m b i n a t i o no fs m a r ta n t e n n at e c h n o l o g ya n dc o m b i n a t i o no fs m a r ta l g o r i t h m i nt h i st h e s i s ，t h e a p p l i c a t i o no ft h ek e r n e lm e t h o dt om u dp r o b l e mi so f f e r e d a f t e rt h a t ，t h es i m u l a t i o ns h o w e d t h ev a l i d i t yo ft h e s ea p p r o a c h e s t h i st h e s i sm a i n l yc o n t a i n st h ef o l l o w i n gs e c t i o n s ： f i r s t ，a f t e r a ni n t r o d u c t i o no ft h ec d m as y s t e mm o d e l ，t h ep e r f o r m a n c eo fs e v e r a l r e p r e s e n t a t i v em u l t i u s e rd e t e c t o r si sa n a l y z e d ，a n dt h ee x c e l l e n c ea n dt h ed i s a d v a n t a g eo ft h e s e d e t e c t o r sa r ed i s c u s s e d s e c o n d ，t h eb a s i ct h e o r yo ft h ek e r n e lm e t h o di se x p o u n d e da n dt h ep o s s i b i l i t yw i t hi ti n c d m a s y s t e mi sa n a l y z e d t h i r d ，af a s to n l i n es v ma l g o r i t h mf o rm u l t i - u s e rd e t e c t i o n ( f a s to n l i n es u p p o r tv e c t o r c l a s s i f i e r , f o s v c ) i sp r o p o s e di nt h i ss e c t i o n t h ea l g o r i t h md i s t i n g u i s h e sn e wa d d e ds a m p l e s a n dc o n s t r u c t st h ec u r r e n tt r a i n i n gd a t as e tu s i n gk k tc o n d i t i o ni no r d e rt or e d u c et h es i z eo f t r a i n i n gs a m p l e s a s ar e s u l t ，t h et r a i n i n gs p e e di se f f e c t i v e l yi n c r e a s e d s i m u l a t i o nr e s u l t s i l l u s t r a t et h a tt h ea l g o r i t h mh a saf a s t e rt r a i n i n gs p e e da n das m a l l e rn u m b e ro fs u p p o r tv e c t o r i l 南京邮电人学硕士研究生学位论文 a b s t r a c t p r e s e r v i n gt h es a m eq u a l i t yo fs e p a r a t i n gh y p e r - p l a n e t h ep e r f o r m a n c eo ft h ef o s v cd e t e c t i o n i sp r e t t ym u c ht h es a m et h i n ga st h a to fs v m d e t e c t i o n ，a n dm u c hb e t t e rt h a nt h a to fm m s e d e t e c t i o n k e yw o r d ：c d m a m u l t i u s e rd e t e c t i o nk e r n e lm e t h o d s u p p o r t v e c t o rm a c h i n e i i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生始巴日期! 兰 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：陋i 蓦 导师签名：研究生签名： 陋i 强 导师签名： 日期：盟 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 研究目的和意义 第一章绪论 目前第三代移动通信系统( 3 g ) 是能够满足国际电联提出的i m t 2 0 0 0 系统标准的新 代移动通信系统，要求具有很好的网络兼容性，能够实现全球范围内多个不同系统间的漫 游，不仅要为移动用户提供话音及低速率数据业务，而且要提供广泛的多媒体业务。根据 i t u 的标准，世界各大电信公司联盟均己提出了自己的第三代移动通信系统方案，其中较 有影响的空中接口建议如表1 1 。 表1 1 无线传输技术( 姗) 建议 建议描述提出组织 t d - s c d m a时分同步c d m a中国通信技术研究所( c a t t ) w c d m a 宽带c d m a日本无线工业和商业协会( a r i b ) u t r au m t s 陆地无线接欧洲电信标准委员会( e t s i ) 口 c d m a 2 0 0 0 宽带c d m a ( i s - 9 5 )美国通信工业协会( t i a ) t r 4 5 5 委员会 总体来说，虽然这些方案不甚相同，但是全世界在第三代移动通信系统中采用宽带码 分多址( w c d m a ) 技术已经达成共识。 c d m a 蜂窝系统与模拟蜂窝系统或t d m a 数字蜂窝系统相比，具有以下优势： ( 1 ) 容量大。 从原理上讲，无论何种多址方式所能提供的系统容量都是一样的。但是，结合具体的 应用条件和工作环境，能得到的通信容量有很大不同。c d m a 蜂窝系统能够提供更大的通 信容量。c d m a 存在“软容量 限制，增加码分多址系统的用户数目会以线性形式抬高噪 声门限。因此，码分多址中用户数目不存在任何绝对限制。不过，随着用户数的增加，所 有用户的系统性能都会逐渐降低。 ( 2 ) 抗干扰能力强。 在c d m a 中，信息码元被扩频码调制，展成了很宽的频谱，在接收端用匹配滤波器将 与本地解扩码一致的用户信息解调出来。而其它干扰，特别是单频或窄带干扰通过匹配滤 波器其频谱被扩散，从而将落入到信号通带内的干扰强度被大大地降低了。 ( 3 ) 抗衰落，抗多径干扰。 南京邮电人学硕士研究生学位论文第一章绪论 码分多址系统具有潜在的抗频率选择性衰落的能力。这是因为扩频通信系统所传送的 信号频谱己扩展很宽，频谱密度很低，如在传输中小部分频谱衰落时，不会使信号造成严 重的畸变。此外，如果扩频带宽比信道的相干带宽大，则c d m a 固有的频率分集将减轻多 径效应。 ( 4 ) 保密性好。 由于扩频信号在很宽的频带上被扩展了，单位频带内的功率很小，其信号的功率谱密 度很低。所以，应用扩频码序列扩展频的直接扩频系统，可在信道噪声和热噪声的背景下， 在很低的信号功率谱密度水平上进行通信，从而具有很低的被截获概率。 综上，由于c d m a 具有的种种优点和其所展现的诱人前景，使其在移动通信中得到了 广泛的应用，成为全世界接受的3 g 的空中接口方式。 c d m a 移动通信系统具有抗干扰、容量大、保密性好等优良性能，但由于扩频码的不 严格正交以及信道的异步时变特性，非零的互相关系数会引起不同用户之间的相互干扰， 称为多址干扰( m a i ，m u l t i p l ea c c e s si n t e r f e r e n c e ) 。m a i 的存在使c d m a 系统容量受到限 制，并且会带来“远近效应”，严重影响系统性能。相对于传统的匹配滤波器，多用户检测 ( m u d ，m u l t i u s e rd e t e c t i o n ) 1 1 , 2 技术能够充分利用m 舭中包含的用户互相关信息来估计、 降低或消除m a i 的影响，具有很好的抗远近效应的能力，这不仅能降低对功率控制的要求， 而且提高了系统的容量，因此m u d 已经成为第三代移动通信备选的关键技术之一。 1 9 8 6 年v e r d u 提出了高斯信道中的最佳多用户检测器( o m d ) ，分析了c d m a 系统改善 性能和提高容量的巨大潜力。然而由于最佳检测器的复杂度随系统中用户数成指数关系增 长【l 】，因此促使人们去寻找在性能上接近于最佳检测器、但实现复杂度却大大降低的次佳 多用户检测器。次佳检测器可分为线性和非线性两大类。前者主要包括解相关检测器和最 小均方误差( m m s e ) 检测器；后者包括连续干扰抵消检测器、并行干扰抵消检测器及迫 零判决反馈检测器等。c d m a 系统的目标用户的检测问题可以看成一个二元分类问题，显 然具有分类功能的机器学习算法都可以用于m u d 。采用核方法的多用户检测技术在样本逐 渐增大情况下具有良好的分类推广能力，因此从综合性能上考虑不失为一种有应用潜力的 检测方案。 1 2 多用户检测的研究和发展趋势 多用户的概念最早在1 9 7 9 年s c h n e i d e 提出3 1 。1 9 8 3 年k o h n o et a 1 发表了对多址接入干扰 接收器的研究1 9 8 6 年s v e r d u 做了开创性的研究，提出并分析了基于最大似然序列检测的最 2 南京邮电大学硕十研究生学位论文第一章绪论 优多用户检测，但其复杂度以用户数的指数函数增加，给实时的实现带来了困难。后来 s v e r d u 的研究激励了多个研究者寻找次最优的多用户检测器，以便用合理的可实现的复杂 度实现接近最优化的。i i , - 工t 4 - 白月匕k 。研究主要集中在寻找针对a w g n ( a d d i t i v ew h i t eg a u s s i a nn o i s e ) 信道的次最优检测。解相关检测、线l 生m m s e ( m i n i m u mm e a ns q u a r ee r r o r ) 检测、决策反 馈检测在随后的几年中纷纷被提了出来，并对它们在高斯白噪声信道中同步和异步结构中 的误码率和抗“远一近效应 等问题进行了深入而细致的研究。 研究衰落多径信道适用的检测器也是多用户检测的潮流之一。先是慢衰落信道，然后 是相对快衰落信道。平坦衰落和多径信道均有考虑。因为多用户检测器的参数如振幅、相 位和多用户间的互相关性经常改变，因此开始研究自适应多用户检测器，其检测器的参数 随所接收到的信号自动调整。目前自适应的多用户检测方法主要有：自适应m i n i m u mm e a n s q u a r e de r r o r ( m m s e ) 多用户检测器，自适应解相关多用户检测器，自适应最小输出能量 m i n i m u m o u t p u te n e r g y ( m o e ) 多用户检测器，自适应子空间多用户检测器等，此外还有具 体针对某一信道提出的自适应算法。这些算法要求已知的信息各有不同，性能也各有千 秋。实际上信号检测所需的参数从来不完美，因此又开始研究对相位、振幅和时延的不理 想估计的影响。 在1 9 9 5 年m i c h a e lh o n i g 年l l s e r g i ov e r d u 提出了盲多用户检测的概念。这种多用户检测器 仅需要知道和传统检测器相同的信息，就可以检测出所发送的信号，使得多用户检测技术 向实用化又前进了一步。自适应滤波的原理在其中得到了广泛的应用，l m s ，r l s ( 递归最 d - 乘) ，k a l m a n 等等各种算法纷纷被应用到多用户检测的系统中。 在1 9 9 8 年x i a o d o n gw a n g 和h v i n c e n tp o o r 提出t 子空间盲多用户检测技术，将盲自适 应信道估计、盲自适应阵列响应估计与盲多用户检测技术结合在一起，利用基于子空间的 高分辨方法对接收的信号进行多用户检测。在1 9 9 9 年他们又将多径c d m a 信道中接收天线 阵列技术与盲多用户检测技术相结合，提出了空时多用户检测技术。从而掀起了多用户检 测技术研究的新的浪潮。 同时多用户检测技术在其他方面的研究也迅速展开，研究者将其它技术和多用户检测 技术相结合进行系统分析，以达到更好的系统性能。如与信道编码技术相结合，研究t u r b o 码对系统性能的影响；如与r a k e 接收机结合，提高多用户检测技术在多径衰落下的性能。 目前在多用户检测方面的研究的主要朝着以下几个方面： 1 与空时二维信号处理技术相结合【4 , 5 , 6 】 空时处理技术是借助阵列处理技术，利用信号的空间特征来抑制干扰。把多用户检测 和空时处理两种技术结合起来，即空时多用户检测，不仅可以增加系统的容量，还可以提高 3 堕室型皇丕堂堡主堕塞圭堂垡堡塞塑= 雯笙堡 系统的可行性，降低系统的成本。n a g u i b 4 】于1 9 9 7 年研究了同步和异步情况下的最优空时多 用户检测，a r o r y a s w a r n i 5 】于1 9 9 7 年研究了多径条件下的最优空时多用户检测，提出了一种空 时白化接收机结构，由于这种接收机采用单用户的接收机前端，本质上仍是次优的。d u y i n g g a n g 在多径信道条件下，提出了参数化的最优空时多用户检测，并且描述性地给出了 空时多用户的v i t e r b i 算法。 2 与多载波调制技术相结合【_ 刀 d s c d m a 的容量主要受多址干扰( m a i ) 和多径效应的限制，采用多载波c d b l a ( m c - c d m a ) 后，能有效地抵抗多径效应的影响，但是多址干扰仍然是必须解决的问题。将多用户检测 技术应用于m c c d m a 中，能够充分发挥两者的长处，使多址干扰得到很好的克服，从而提 高系统的整体性能。t m i y a j i m a 于1 9 9 6 年利用h o p f i e l d 利j 经网络( h n n ) 对异步m c - c d m a 进 行多用户检测，并指出只要从信道状态信息中选择合适的h n n 参数，即可很好地解决多径 衰落和多址干扰问题。 3 与智能算法相结合 a 禁忌搜索( t a b us e a r c h ) 算法：是由g l o v e r 于1 9 8 6 提出的一种十分有效的启发式搜索算 法【8 , 9 1 ，它用一个禁忌表记录下已经达到过的局部最优点，在下一次搜索中就不用再搜索这 些点，从而跳出局部最优点，达到寻找全局最优点。唐普英、李志辉等2 0 0 4 于年研究了基 于禁忌搜索算法的多用户检测器，很好地解决了最优多用户检测的组合优化问题，获得良 好的检测性能【1 0 j 。 b 基于遗传算法的多用户检测【1 1 , 1 2 】：将传统检测器的输出作为一个初始染色体，初始 种群的所有个体都通过对此初始染色体基因的随机变异( 从+ 1 到一1 或相反) 来得到。 c 基于神经网络的多用户检测算法【1 3 】：神经网络信息的存储体现在神经元之间连接的 分布上，存储区和处理区合二为一。利用神经网络的高度并行运算能力，可以实时实现难 以用传统数字计算实现的最优信号处理算法。m r c h e n ”】等人于2 0 0 5 年发表的文章中，研 究了基于神经网络的多用户检测器，并取得了较好的实验结果。 d 基于支持向量机的多用户检测算法1 1 4 , 1 5 1 ：m r c h e n 1 4 1 于2 0 0 1 年将支持向量机技术应 用到多用户检测中来，并通过实验验证了利用支持向量机解决多用户检测问题的可行性和 有效性。该类算法将信号检测看作是一个二分类问题，将接收到的信号作为输入模式，通 过支持向量机训练信号分类器，最终将接收信号分为+ l 或者一1 类。 4 南京邮电大学硕士研究生学位论文第一章绪论 1 3 本文的主要工作 本文在系统地研究了c d m a 信道模型和主要的多用户检测算法性能与特点的基础上， 将目前信号处理领域内研究热点，核方法( k e r n e lm e t h o d ) 应用于多用户检测算法中。 本文的研究工作主要包括如下两个方面： 第一，在介绍c d m a 通信系统模型的基础上，分析了几种经典多用户检测器的性能， 并指出了每种检测器的优缺点。 第二，阐述了核方法的基本理论并分析支持向量机应用于c d m a 系统的可能性。 第三，提出了一种快速的在线支持向量分类( f o s v c ) 算法，它利用k k t 条件判别新增 加的训练序列，选择违反k k t 条件的样本构造当前训练样本集，从而有效地减少每次训练 样本的大小，提高训练速度并降低对计算内存的需求。仿真实验表明，该算法在不影响分 类效果的情况下大大加快了训练速度，且用于分类的支持向量较少，同时性能与传统支持 向量机算法相当且明显优于m m s e ( r l s ) 多用户检测器。 下面各章内容如下： 第一章为本文的绪论部分，本章首先阐明了本文所选课题的研究背景，指出所选课题 的研究意义，然后重点介绍多用户检测技术目前研究主要集中的几个方面以及研究现状， 最后总结了本文的主要研究工作和创新点。 第二章首先简要介绍了机器学习的基本方法，然后引出统计学习理论的基本思想，并 对统计学习理论的一些基本概念进行了介绍，最后详细介绍了支持向量机的有关分类的基 本理论知识，以此作为以后各章所研究的基础。 第三章阐述了c d m a 系统模型和多用户检测的研究概况，并分析比较了几种经典多用 户检测器的优缺点。 第四章介绍了在多径衰落信道下支持向量机的多用户检测算法，在此基础上提出了一 种快速在线多用户检测算法，并进行了仿真验证了其优越性。 第五章为总结，本章归纳了作者两年来在多用户检测研究方向上所做的工作，并对可 进一步展开研究的方向讲述个人看法。 南京邮电大学硕士研究生学位论文第二章核方法的举奉原理 2 1 统计学习理论 第二章核方法的基本原理 统计学习理论是一门研究基于数据的机器学习理论的科学，它的发展和成熟丰富了现 代数理统计学的内容【1 6 。8 1 。对于无穷大的样本，根据统计学中的大数定理就能给出：经验 误差的最小化可以确保测试误差的最小化。但对于有限样本，特别是小样本时，统计学习 理论的研究者认为最小化训练误差准则并不是自证的，而是需要证明的。他们认为对于有 限样本或许还存在另外的学习准则可以获得更好的推广能力。统计学习理论的研究者就是 要寻找更好的学习准则，并构造可实现的算法。1 9 6 8 年，v a p n i k 和c h e r v o n e n k i s t l 9 】对于 指示函数集提出v c 熵和v c 维数的概念，这两个概念是统计学习理论中的核心概念，正 是基于这两个概念他们发现了范函空间上的大数定理，得到了收敛速率的非渐近界。1 9 7 1 年 2 0 l ，他们发表了这些工作的完整证明。1 9 7 4 年【2 1 1 ，他们基于收敛速率的非渐近界，建立 了结构风险最小化准则，从而完成了模式识别的学习理论。从1 9 7 6 年到1 9 8 1 年间，v a p n i k 2 2 】 又将针对指示函数集得到的结论，如范函空间上大数定理，一致收敛速率的界和结构风险 最小化准则推广到实函数集。最后1 9 8 9 年；v a p n i k 和c h e r v o n e n k i s t 2 3 1 发现了经验风险最 小化准则和最大似然方法一致性的充要条件，完成了对经验风险最小化准则的分析。 统计学习理论被认为是针对小样本统计估计和预测学习的最佳理论，它从理论上系统 地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系以及如 何利用这些理论找到新的学习原则和方法等问题。其内容主要包括以下四个方面： ( 1 ) 经验风险最小化原则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理原则； ( 4 ) 实现这些新的原则的实际方法。 统计学习理论核心思想是：通过控制学习机器的容量实现对其推广能力的控制。基于 这一理论v a p n i k 等人于2 0 世纪9 0 年代发明了著名的支持向量机( s v m ) ，随后一些核学习 方法的研究者又在此基础上提出了一些其它的核学习方法。统计学习理论将机器学习问题 看作是利用有限数量的观察来寻找待求的依赖关系的问题。即：从给定的函数集中选择出 能够最好地逼近训练器响应的函数。机器学习的目的就是能根据给定的有限学习样本估计 出输入和输出之间的固有的依赖关系，使得训练好的学习机器能够准确地对未知样本进行 预测。 6 南京邮电大学硕士研究生学位论文第二章核方法的基本原理 2 1 1v c 维 统计学习理论中的一个重要的概念是v c 维【1 7 2 4 之7 1 ( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) ， 它是对函数集学习性能进行描述的一个重要指标。v c 维的定义：一个指示函数集的v c 维，是能够被集合中的函数以所有可能的2 种方式分成两类的向量的最大数目h ( 也就是 用这个函数集中的函数能够打散的最大样本集的样本数目) 函数集的v c 维用h 表示。 例! z 1 - 在r d 中( 一个d 维空间中) ，有向超平面函数集的v c 维是d + 1( 如：在二 维平面中，一个有向直线的函数集的v c 维是d + 1 = 3 ，它有2 3 = 8 种方式将3 个数据点打 散) ，如下图所示： 义 蟛 涞。卜 图2 1 在二维空间尺2 中三个样本点被有向直线打散( 8 种方式) 函数集越复杂，则此函数集的v c 维就越大。函数集具有有限的v c 维是学习过程一 致收敛的充要条件。 2 1 2 机器学习模型 机器学习问题表示为，已知变量y 与输入x 之间存在一定的未知依赖关系，即存在一 个未知的联合概率p ( x ，y ) ，典型的两类分类问题中，学习机器根据n 个独立同分布( 概率 分布未知) 训练样本对：( 而，乃) ，( ，此) x xy ，】，= ( 一1 ，+ 1 ) ，估计出一个函数 厂：x jy ，使得函数厂能正确地分类任一未知样本x 。函数f 可以通过最小化下面的期望 风险求得： 科门= p ( 厂( x ，w ) ，y ) d p ( x ，y ) ( 2 - 1 ) 其中，是损失函数，w 是函数的广义参数，p ( x ，j ，) 是概率分布。在模式识别中，0 1 损 7 南京邮电大学硕士研究生学位论文 ， 第二章核方法的基本原理 失函数的基本定义是： 输心 ，( ( x ，w ) ，y ) = o , y - - f ( x , w ) 图2 2 机器学习基本模型 一般来说，一个好的学习机器，对于相似的输入，总是可以获得相似的输出。 2 1 3 经验风险最小化原则 ( 2 - 2 ) 在( 2 - 1 ) 式中，因为概率分布p ( x ，y ) 未知，所以不能直接最小化期望风险，只能根据 训练样本和函数集的属性估计出一个最佳函数，最简单的方法就是通过最小化下面的经 验风险( e m p i r i c a lr i s k ) = i 善n ( ( 墨，w ) ，以) ( 2 - 3 ) 这种估计最佳函数用经验风险的最小值来代替期望风险的最小值就是所谓的经验风 险做最小化( e m p i r i c a lr i s km i n i m i z a t i o n 简称e r m ) 原则。概率论中的大数定理说明，在 一定条件下，当样本数趋于无穷多时，经验风险疋。在概率上趋近于期望风险r ，但并不 能保证当经验风险r e m p 最小时的与期望风险r 最小时的矿是同个值，更不能保证经 验风险尺( w ) 趋近于期望风险r ( ) 。在早期的神经网络研究中，一味地追求经验风险 最小，学习机器的推广能力并不好，甚至当经验风险r a p 越小，学习机器的推广能力 反而变差，这就是所谓的过学习现象。因此，对于有限样本情况，要想获得推广能力很好 的学习机器，不能只是简单地追求经验风险k 最小，必须寻求其他的优化准则。 8 南京邮电大学硕士研究生学位论文 第二章核方法的幕本原理 2 1 4 学习机器推广能力的界 统计学习理论提出，学习机器的实际风险( 期望风险) 是由两部分组成【1 7 , 2 7 】，假定h 是 某函数集的v c 维，疋即是经验风险，对所有的万 0 ，经验风险和实际风险至少以概率1 一万 满足下式： r + ( 2 4 ) 即学习机器的实际风险( 期望风险) 是由两部分组成： 跏) ( w ) + 伊( 鲁) ( 2 - 5 ) 其中，不等式右边的第一项是经验风险；第二项是置信范围( c o n f i d e n c ei n t e r v a l ) ，w 是 权向量，甩是样本数，h 是v c 维。 1 4 1 2 l 置 信o 8 范o 6 围 0 4 0 2 o 图2 3 置信范围是v c 维的单调增函数 当h n 较大时，置信范围较大，用经验风险最小化取得的最优解可能具有较差的推广 性；当样本数较多时，h n 较小，则置信范围就会很小，经验风险最小化的最优解就接近 于实际的最优解。如果，对于一个给定数目的训练数据，设计一个过于复杂的机器，即逼 近函数集复杂( v 维较高) ，则置信范围将会很大，这时即使可以将经验风险最小化为0 ， 在测试集上的错误率仍会很高，这种现象叫做过学习。为了避免过学习现象( 为了获得小 o 南京邮电大学硕士研究生学位论文 第二章核方法的基本原理 的置信范围) ，我们尽量构造v c 维小的学习机器，例如：线性函数的v c 维就较小。 2 1 5 结构风险最小化原则 由上面的分析知，要最小化期望( 实际) 风险，我们必须同时对上式右边中的两项进 行最小化，不等式右边的第一项经验风险取决于函数集中的一个特定的函数，第二项取决 于整个函数集的v c 维。在设计分类器时，我们不但要使经验风险最小化，还要使v c 维尽量 小，从而缩小置信范围，使得期望风险最小。结构风险最小化归纳原则【1 7 , 4 0 】( s t r u c t u r a l r i s km i n i m i z a t i o n 简称s r m ) 就是针对经验风险和置信范围这两项进行期望风险最小化的 归纳原则。即：s r m 是对给定数据逼近的精度和逼近函数的复杂性之间的一种折衷。 结构风险最小化原则：首先将函数集s = f ( x ，w ) ，weq ) 分解成子集序列，即： sc 是c c 瓯c c s ( 2 - 6 ) 使得各个子集按照置信范围的大小排列，也就是按照v c 的大小排列，即 岛缟s 魂， ( 2 7 ) 这样当选择经验风险与置信范围之和为最小的子集时，就可以达到期望风险最小，这 个子集中使经验风险最小的函数就是所求的最优函数。这就是结构风险最小化原则。 下图显示了期望风险和经验风险以及置信范围的关系曲线。要想获得期望风险的最小 化，我们必须兼顾经验风险和置信范围，在它们之间寻找一个最佳点。 风险 图2 4 期望风险与经验风险和v c 维的关系示意图 1 0 南京邮电大学硕士研究生学位论文第二章核方法的基本原理 2 1 6 学习机器的实现方法 由上面的分析可知，在针对实际问题时，若要最小化期望风险，我们必须首先找到学 习机器的适当结构，然后在这个机器中寻找使得在训练数据上错误最少的函数。我们有两 种方法可以完成对期望风险的最小化： ( 1 ) 保持置信范围固定( 通过选择一个适当构造的机器) ，然后最小化经验风险； ( 2 ) 保持经验风险值固定( 例如：对于线性可分情况，经验风险为零) ，然后最小 化置信范围。 传统的神经网络所采用的就是第( 1 ) 种方案，即首先确定网络的层和节点，也就是 固定了置信范围中，然后最小化经验风险，来达到最小化实际风险的目的。因为人们缺乏 对置信范围的了解，所以神经网络结构的选择往往凭经验，而且经常不能获得很好的效果。 而支持向量机所采用的是第( 2 ) 种方法，即在保证经验风险为一定值时( 如线性可 分时，经验风险等于0 ) ，通过最小化置信范围来最小化期望风险，即通过选择简单的线 性函数集使得置信范围较小，从而最小化实际风险1 7 ，2 4 删。 支持向量机就是基于结构风险最小化原则来实现期望风险最小化的机器学习算法，其 算法思想是：对于两类分类问题，当两类样本线性可分样本时，选择一个最优线性超平面 ( 因为超平面v c 维较小) 使得两类样本不仅线性可分，而且两类分开的间隔最大。当两类 样本线性不可分时，首先通过某种事先选择的非线性映射将原空间的数据映射到一个高维 特征空间( 可以是无穷维) 中，然后在这个高维的特征空间中构造最优的分类超平面( 因 为超平面v c 维较小) 。在1 9 9 2 年，v a p n i k 等人发现：为了能在这个高维的特征空间中构造 最优的分类超平面，并不需要以显式形式来考虑特征空间，只需要能够计算支持向量与高 维特征空间中向量的内积核函数。这一伟大发现奠定了核学习方法的理论基础，为核学习 方法的研究和发展提供了理论保障。 2 2 核方法的原理 核方法是基于核的机器学习方法的简称。核机器学习方法是基于统计学习理论和核技 术建立的，以支持向量机为其核心算法的一类统计机器学习方法【1 6 - 1 8 , 2 9 弓6 1 。可以说核机器 的产生是统计学习理论和核技术发展的产物。由于在核机器中采用了统计学习理论中的结 构风险准则，使得核机器不会陷入过拟合，具有良好的推广能力，又不必要求过多的i ) l l 练 样本，这在一定程度解决了神经网络中的“过拟合问题 和推广能力问题” 1 6 - 1 8 , 2 9 - 3 2 。 南京邮电大学硕士研究生学位论文第一二章核方法的基本原理 同时由于核技术的采用，实现了非线性的核机器，使核机器具有更大的假设空间，能解决 较为复杂的问题，而且不必付出庞大的计算代价，这也在一定程度上避免了神经网络中“维 数灾难问题”和b a y e s 网络中“网络规模爆炸问题”【即弼6 1 。 核的理论基础很早就有了，m e r c e r 定理【3 7 1 可追溯到1 9 0 9 年，再生核h i l b e r t 空间的研 究在1 9 世纪4 0 年代被a r o n a z 旬i n 3 s 】发展。核的理论也被用到近似估计和正则化理论中。 而运用m e r c e r 定理把核解释成一个h i l b e r r t 空问中的内积这一思想，则首先是1 9 6 4 年被 a i z e r m a n ，b e a v e r m a n 等人在机器学习领域中引进的【5 2 1 ，但直到v a p n i k ，b o s e r 和g u y o n 在 一篇支持向量机的文献【53 】中首先运用了这个思想，人们才开始充分理解它的含义。核技术 不仅在微分方程求解、微分几何、群论、调和分析等许多数学学科中有十分巧妙的应用， 近年来在机器学习、信号处理、混合g u a s s i a n 过程分析等许多领域受到了青睐。 核方法的基本思想【2 6 , 2 8 1 是：对于原空间中线性不可分的数据，首先经过一个非线性映 射妒：r f ，x 一够( z ) ，将原空间的数据映射到一个高维的特征空间f ( t g 称核空间，维数 可以无穷大) 中，只要选择满足m e r c e r 条件的核函数k ，就可以在这个特征空间中隐含地 进行运算，实现数据在高维空间中的线性分类( 或近似线性分类) ，这样就可以利用一些线 性算法来实现相对于原空间为非线性的算法，从而提高算法的性能。 利用核函数k 代替原空间中的内积，就对应于将数据通过一个映射，映射到某个高维 的特征空间中，高维特征空间是由核函数定义的。选定了一个核函数，也就对应地定义了 一个高维特征空间。特征空间中所有的运算都是通过原空间中的内积核函数来隐含实现。 即：任何( 线性) 只要用到标量内积的算法都可以通过一个核函数在高维特征空间中隐含 地进行运算。我们可以利用此思想，在特征空间中实现一般的线性算法，但却能实现相对 于原空间来说是非线性的算法。这将会大大地提高学习算法的效率，改进现有算法，提高 各类模式识别任务的识别率。 2 2 1 机器学习算法的具体核化过程 具体核化过程如f ： 以图2 1 中的模式分类问题为例简述机器学习算法的核化过程。图2 一l ( a ) 中分属于两类 n n 个独立样本( 五， ) ，( 而，乞) ，( h ，0 ) r xt 采样自( x ，f ) ，其中r 为原始输入空间， 丁= i - 1 ，1 l 代表类别标号集合。设变量x 与，之间存在一个未知的联合概率分布p ( x ，) ，其 中x 的维数为d 。记而，x 2 ，x u 的集合为z 。“= ( 五，x 2 ，h ) r ，t u = ( ，2 ，0 ) 7 ，样 1 南壅塑堕盔堂亟婴究生堂垡论塞第二章核方法的基本原理 本均值为历，自相关矩阵为s = x ；x n ，协方差矩阵为= s 一历历7 。 o 口 。 j 。 ；。 。x _ 。一一+ o ? ：。o ( a ) 输入空间中的n 个待分类样本( b ) 线性分类面函数( c ) 非线性面分类函数 图2 一l 核方法与s v m 基本原理 设某学习算法基于准则i 构造一个分类函数7 ：尺一t ，且在构造过程中只涉及样本间 的内积运算。如要得到该学习算法对应的核方法，首先通过某未知映射函数妒：r f 将 个样本映射到特征空间f 中，得到( p ( 葺) ，) ，( 缈( ) ，t 2 ) ，( 伊( h ) ，l ) f x t ，并记p ( _ ) ， 伊( 秘) ，伊( h ) 的集合为妒( z ) ，r 、f 、z 和妒( z ) 间的关系可参见图2 2 ； f ( a ) 输入空间( b ) 特征空间 图2 2 特征空间中点的原像示意图 然后在f 中仍基于准则r 构造新的分类函数f ：f t ，构造过程中凡涉及到形如 缈( 薯) 妒( 0 )