（计算机应用技术专业论文）基于语义标注的视频相关反馈检索系统.pdf

中文摘要自上个世纪九十年代以来，基于内容的视频检索便成为一个热门的研究课题。在信息爆炸的今天，如何使用计算机自动挖掘视频中的语义信息，并有效地利用高层特征进行视频检索，已经成为多媒体研究领域中一个亟待解决的问题。视频语义表示的优势在于与人的认知理解相符合，是一种解决低层特征与高层语义之间语义鸿沟问题的有效途径。本文提出一种基于视频语义的检索方法，该方法利用已经获得的视频语义标注信息，使用一种具有长期学习记忆性的相关反馈方法对视频语义进行查询。相关反馈是一种借助人机交互来提高检索精度的方法，本文讨论并实现了一种基于支持向量机的相关反馈方法：用户在一轮检索结果中选择符合查询目的的关键帧作为正例样本，系统根据正例样本数量以及检索的排序信息选择负例样本，这两类样本构成s v m 的训练集，学习得到s v m 模型后，使用该模型作为新一轮检索的分类器。由于用户反馈得到的调练集往往是一个小样本集，根据经验，利用小样本集训练得到的s v m 模型通常能够取得优秀的分类效果。另外，为提高s v m 的训练速度，本文在s v m 训练过程中采用了一种快速算法s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ，简称s m o 算法。相关反馈是提高检索准确度的有效手段，但一般的相关反馈系统的缺点是无法对用户的反馈信息进行长期保留，是一种短期记忆学习机制。而且基于视频低层特征的相关反馈检索仍然深受语义鸿沟的影响。为建立视频语义检索系统，并使其相关反馈操作具有长期学习记忆性，本文使用语义标注信息构造一个低维的视频语义特征，以此为基础建立一个关键帧与语义概念的关联网，通过用户的相关反馈操作对关联网进行具有长期记忆功能的更新，最终的查询结果即关联网中与查询概念相关程度较高的关键帧。本文提出的检索方法，具有长期记忆性，系统的检索精度能够通过知识积累不断得到提高；此外，由于检索是基于语义特征的，能更好地理解用户的查询意图，取得了较好的实验效果。关键词：视频检索；视频语义；相关反馈；s v m je塞窑道太堂亟堂僮监塞垣地咝a b s t r a c ts i n c et h e1 9 9 0 s ，c o n t e n t b a s ev i d e or e t r i e v a lh a sb e c o m eah o tr e s e a r c ht o p i c i nt h ee r ao fi n f o r m a t i o ne x p l o s i o n , i th a sb e c o m ea l lu r g e n tp r o b l e mi nt h er e s e a r c ho fm u l t i m e d i at h a th o wt om a k ec o m p u t e rt og e ts e m a n t i ci n f o r m a t i o nf r o mv i d e o sa u t o m a t i c a l l ya n du s i n gt h e mt or e t r i e v a lv i d e o se f f i c i e n t l y t h ea d v a n t a g eo fs e m a n t i cr e p r e s e n t a t i o no fv i d e oi st h a tt h er e c o g n i t i o nb a s e do ns e m a n t i ca c c o r d sw i t hh u m a n sc o g n i t i o nu n d e r s t a n d i n g u s i n gs e m a n t i cr e p r e s e n t a t i o ni sa ne f f e c t i v er e s o l u t i o no fs e m a n t i cg a pb e t w e e nl o w l e v e lv i s i o nf e a t u r e sa n dh i g h l e v e lc o n c e p tf e a t u r e s i nt h i sp a p e r , o u ro b j e c t i v ei st op r o p o s eav i d e or e t r i e v a lm e t h o db a s e do ns e m a n t i c i tr e l i e so nt h ea u t o m a t i ca n n o t a t i o ni n f o r m a t i f o rv i d e o s a n du s ear e l e v a n c ef e e d b a c km e t h o dw i t hl o n g - t e r mm e m o r yt or e t r i e v a lv i d e os e m a n t i c r e l e v a n c ef e e d b a c ki sa ne f f e c t i v em e t h o do fi m p r o v i n gt h er e t r i e v a la c c u r a c yu s i n gm a n m a c h i n ei n t e r a c t i o n am e t h o do fr e l e v a n c ef e e d b a c kb a s e do ns u p p o r tv e c t o rm a c h i n e ( s v m ) i sd i s c u s s e da n di m p l e m e n t e di nt h i sp a p e r a f t e rar e t r i e v a lp r o c e s s ，u s e rs u b m i tt h ec o r r e c tr e s u l t sa sp o s i t i v ee x a m p l e sa n dr e t r i e v a ls y s t e ms e l e c tt h en e g a t i v ee x a m p l e sa c c o r d i n gt oa m o u n to fp o s i t i v ee x a m p l e sa n dr a n ki n f o r m a t i o no fr e t r i e v a lr e s u l t s t h e s et w oc l a s se x a m p l e sc o - c o n s t r u c tat r a i n i n gd a t as e tf o rs v m a f t e ro b t a i n i n gas v mc l a s s i f i c a t i o nm o d e l ，t h er e t r i e v a ls y s t e mr u n snn e wc l a s s i f i c a t i o nr e t r i e v a lp r o c e s sw i t ht h i sm o d e l g e n e r a l l y , t h et r a i n i n gs e tf r o mu s e rf e e d b a c ki sas m a l ls a m p l es e t as v mc l a s s i f i e rt r a i n e df r o ms m a l ls a m p l es e th a se x c e l l e n c ep e r f o r m a n c eo nc l a s s i f i c a t i o na c c o r d i n gt ot h ep r e v i o u sw o r k i na d d i t i o n , af a s ta l g o r i t h m ，s e q u e n t i a lm i n i m a lo p t i m z a t i o n ( s m o ) ，i su s e dt os p e e du pt h et r a i n i n gp r o c e s so fs v m r e l e v a n c ef e e d b a c ki se f f e c t i v e l y , b u ti t 啪n o tr e m a i nt h ef e e d b a c ki n f o r m a t i o nf o rnl o n gt i m e ，h e n c ei t ss h o r t t e r mm e m o r yc a p a c i t y f u r t h e r m o r e ，s e m a n t i cg a pm u s th a v ea d v e r s ee f f e c to naf e e d b a c ks y s t e mb a s e do nl o w l e v e lv i s i o nf e a t u r e s n ep a p e rp r o p o s e sav i d e os e m a n t i cr e t r i e v a ls y s t e mw i t hl o n g - t e r mr e l e v a n c ef e e d b a c k f i r s t , al o w d i m e n s i o ns e m a n t i cf e a t u r ei sc o n s t r u c t e d a n dt h e na na s s o c i a t e dn c t w o r k b e t w e e nk e yf r a m e sa n ds e m a n t i cc o n c e p t si sc o n s t r u c t e d t h i sa s s o c i a t e dn e t w o r kc a r lb em o d i f i e dd u r i n gn s e r sf e e d b a c ko p e r a t i o n a n du s e r sf e e d b a c ki n f o r m a t i o nc a l lb er e m a i n e di nal o n gt e r m f i n a l l y , t h es y s t e mc a nm o d i f i e dt h ea s s o c i a t e dn e t w o r ka n dr c l n r nt h ek e yf l a m e sw h i c ha r ec l o s e l yr e l a t e dt ot h eq u e r y t h em o d e lo fv i d e or e t r i e v a lp r o p o s e di nt h ep a p e rc a nr e m a i nt h el o n g - t e r mi n f o r m a t i o ns p a n n i n gd i f f e r e n tq u e r i e s i tc a ni m p r o v et h ep e r f o r m a n c eo fr e t r i e v a lu s i n gt h ea c c u m u l a t e dk n o w l e d g e o u rr e t r i e v a ls y s t e mc a l lm a t c hu s e r s i n t e n tb e t t e rb e c a u s eo fu s i n gt h es e m a n t i cf e a t u r e k e y w o r d s ：v i d e or e t r i e v a l ；s e m a n t i c ；r e l e v a n c ef e e d b a c k ；s v m 学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：炙乍免导师签名：了阴幻签字日期：弦町年廖月砰日签字日期：扪年l 乙月涉日独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书丽使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：夏纬缸签字日期：刎年j2 ，月2 ，y 日致谢本论文的工作是在我的导师王方石副教授的悉心指导下完成的。在两年半的研究生学习中，王老师严谨的治学态度和科学的工作方法给了我极大的帮助和影响。无论在为人、为学上，王老师都给我予无微不至的关怀与指导，为我提供了许多难得的学习锻炼机会，使我在理论和实践上都得到了极大的提高。本论文从选题、撰写、字斟句酌的修改，到最后的定稿，都得到了王老师的悉心指导，王老师的严谨、精益求精的精神使我受益匪浅。感谢所有在研究生学习期问曾给我以支持、关心和帮助的各位老师、同学以及朋友，感谢他们对我的学习研究和论文工作所给予的无私帮助，感谢他们对我研究生生活的关怀与鼓励，在此期间我所取得的一点一滴的进步都离不开他们。另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。j e 哀銮通太堂亟堂僮论室缝盐1 1 研究背景1 绪论随着计算机硬件、数字化设备和多媒体、数据库、w e b 等技术的发展，各种各样的数字媒体涌入人类的日常生活。人们所面对的浩瀚的数据信息中，除了传统的字符信息以外，诸如声音、图像、视频等多媒体数据也已经广泛应用于互联网络、企业、甚至个人的信息系统中。显然，随着多媒体数据量的急剧增加，终端用户日益希望能够像对待文本数据一样，直观地对大量多媒体数据进行管理和详细的检索。因此，如何按照多媒体数据的特性去对多媒体信息进行检索，就成为当今多媒体技术研究的一个热点。在早期的多媒体检索技术研究中，人们使用传统的关系数据库系统来建立多媒体信息管理系统，这种方法需要采用专门的人工输入为多媒体数据建立一套较为完整的文本注释，用户检索时使用关键词在文本注释数据库上进行匹配。但随着多媒体技术的飞速发展，自2 0 世纪9 0 年代以来，多媒体数据产生爆炸式增长，在这样的情况下，这种人工注释的缺点也日益明显。首先，人工注释需要花费大量的人力，在海量的多媒体数据前尤为如此，而且在目前的技术环境下，每天都会产生大量的新数据，以人力的速度无法保证信息资源的更新、无法保证满足用户的需求。其次，人工注释难以解决蕴含在多媒体数据中的丰富内容以及对所感知内容描述的主观性。第三，对于实时播放的流媒体数据的处理是无法手工进行的，需要利用计算视的高速运算特性对其进行实时的内容分析。为解决上述问题，使用计算机对多媒体数据进行自动分析理解，进而给多媒体数据标注上较为完整客观的语义信息，成为一个比较理想的方案。为此，人们提出了基于内容的多媒体信息检索思想。基于内容的检索是指根据媒体和媒体对象的内容及上下文联系在大规模多媒体数据库中进行检索。其特点是；从媒体内容中提取信息线索；基于内容的检索是一种近似匹配；大型数据库( 集) 的快速检索。其目标是在无人为影响的条件下能自动理解或识别多媒体数据的重要特征。从2 0 世纪9 0 年代初，国际上就开始对基于内容的多媒体检索技术进行研究。基于内容的方法是从新的角度对多媒体信息进行管理，包括：视频媒体的结构化组织和浏览；图像、音频信号的分析处理，其目的不只是识别与理解，还用于更广泛的信息存取应用；考虑多种媒体及其之间的关系，加以综合利用；支持其他多媒体技术，如超媒体技术、虚拟现实技术、多媒体通信网络技术等。目前，基于内容的多媒体信息检索的主要工作集中在识别和描述图像的颜色、纹理、形状和空间关系上，对于视频数据，还有视频分割、关键帧提取、场景变换探测以及故事情节重构等问题。由此可见，这是一门涉及面很广的交叉学科，需要以图像处理、模式识别、计算机视觉、图像理解等领域的知识为基础，还需从认知科学、人工智能、数据库管理系统、入机交互、信息检索等领域引入新的媒体数据表示和数据模型，从而设计出可靠、有效的检索算法、系统结构以及友好的人机界面。1 1 。1 视频检索研究现状视频内容分析及检索技术作为一门新兴发展中的技术，广泛融合了诸多学科的知识与技术，通过对视觉、听觉以及文本等内容的分析。将非结构化的视频数据进行结构化处理。并使用有效的特征对结构化单元进行描述，以j 圪为基础构建视频检索系统，使用户能够方便地获取视频信息。这种新兴技术一旦发展起来，其应用前景将会非常广阔，如：视频数据库、视频监控、数字图书馆、网络多媒体搜索引擎、视频点播、遥感和地球资源管理、远程医疗、天气预报等等。因此，视频分析与检索成为研究领域的一个热门研究课题，国内外众多研究者从不同角度对这个问题展开研究。为了促进视频内容分析与检索技术研究的发展，美国国家标准技术研究院( 吣t ) 主办了国际视频内容分析与检索领域最具影响力的t r e c v i d ( t e x tr e t r i e v a lc o n f e r e n c eo nv l d e d ) 会议，于每年1 1 月份召开，是该领域中国际项尖级研究团体( 如c m u 、i b m 研究中心、清华大学、哥伦比亚大学等) 的一次盛大学术聚会。会议确定了四项研究任务：镜头边界检测、低层特征提取( 专指相机运动，即全局运动) 、高层特征提取( 即语义信息提取，包括对象、场景和事件检测) 以及视频检索。每年会后，各参与的研究单位都会发表多篇高水平的学术论文和详实的技术报告。目前，视频检索有四种常见的方式：浏览查询、样例查询、草图查询和关键词查询。浏览查询( b r o w s i n g ) 是一种最简单的查询方式，系统将所有视频关键帧排列显示，用户以浏览方式找到所需要的关键帧。样例查询( q u e r y b y e x a m p l e ，q b e ) 是基于内容视频检索中的常用方式，用户向检索系统提供与查询目标相关的若干关键帧样例，系统输出与样例相似的关键帧集合作为查询结果。草图查询( q u e r yb ys k e t c h ，q b s ) 是一种特殊的样例查询，用户可在系统提供的绘图界面上画出查询目标的草图，以此草图作为查询样例输入，系统输出与草图样例相似的关键帧集合作为查询结果。2关键词查询( q u e r yb yk e y w o r d ，q b e ) 即基于语义的查询，由用户输入若干能够描述查询目标的文本关键词，系统输出语义信息与关键词相符的关键帧集合作为查询结果。下面对国内外的视频检索技术研究进展进行简单介绍。1 1 2 国外视频检索研究进展目前，国外各研究单位已经实现了多个视频检索的原型系统，其中比较有代表性的有：( 1 ) o b i c ( q u e r yb yi m a g ec o n t e n t ) 系统弘1q b i c 是由m a l m a d e n 研究中心研究开发的基于内容检索系统的典型代表。这个系统支持样例及草图查询，同时支持图像、视频的检索。q b i c 中提供了四种视觉特征的检索功能，包括：颜色、颜色分布、纹理以及形状。其颜色特征的查询包含了颜色百分比查询及颜色分布查询，利用颜色百分比查询，用户可以获取具有相似颜色及比率的图像，在此基础上利用颜色分布查询，可以进一步获得平面空间上具有相似颜色分布的图像。q b i c 的纹理特征采用了改进的t a m u r a 纹理表示法，综合考虑了图像中线条的粗糙性、对比性和方向性。在形状特征上，包括形状区域、圆周率、离心率、主轴方向和一些代数不变矩，能针对目标的形状和轮廓进行匹配。在其新版本中，已经对基于文本关键字和基于图像内容的检索进行融合，并获得很好的效果。o b i c 被公认为基于内容检索系统的范例，其研究者在此基础上集成语音识别技术后又开发了c u e v i d e o 系统。( 2 )v i s u a l s e e k i i 和w 曲s e e k l 4 j这两个系统都是美国哥伦比亚大学的研究成果，其特点是对图像，视频中的视觉特征和文本信息做出有机结合，并且支持图像域的空间关系查询( s p a t i a lr e l a t i o n s h i pq u e r y ) 和压缩域的视觉特征提取，系统使用的视觉特征为颜色集( c o l o rs e t ) 和基于小波变换的纹理特征。其中v i s u a l s e e k 是一个视觉特征搜索引擎，而w 曲s e e k 是面向w w w 的文本、图像搜索引擎。( 3 ) v i d e o q l 5 】v d e o o 也是哥伦比亚大学研制的，它是一个全自动的、面向对象的、基于内容的视频检索系统。该系统除了样例、草图查询外，还支持基于关键词或主题浏览的检索方式，并提出了基于丰富视觉特征和时空关系的查询技术，用于帮助用户查询视频对象。( 4 ) v i r a g e l 6 lv t r a g e 是v i r a g e 公司研发的检索系统，该系统能够自动、实时地为视频建立结构化索引，与0 b i c 系统一样，v i r a g e 也提供了四种视觉特征的查询功能，但其查询方式可以在四种特征中进行任意组合。( 5 ) i n f o r m e d i a l 7 1i n f o r m e d i a 系统是c m u 研制的多媒体信息检索系统，其初衷是要建立一个数字化图书馆。该系统支持语音识别、图像理解、自然语言处理及智能视频检索，可自动提取视频摘要，支持基于语义的视频检索。( 6 ) m a r s i s m a r s 系统是u i u c 研制的多媒体分析和检索系统( m u l t i m e d i aa n a l y s i sa n dr e t r i e v a ls y s t e m ) ，同时支持图像、视频、音频等媒体信息的检索。该系统的研究范围涉及到计算机视觉、数据库管理系统和信息检索等多个领域。m a r s 不以寻找、研究最好的媒体信息描述特征为目标，而是着力于对各种不同视觉特征进行组织，使其能够自适应地支持各种不同的需求。系统支持样例查询方式，在目标模型的各个级别中均可灵活使用。另外，m a r s 首先在图像检索中提出了相关反馈的概念。1 1 3 国内视频检索研究进展在国内，清华大学、国防科技大学、复旦大学、浙江大学和上海交通大学等科研院所也在从事视频检索方面的研究工作，但目前国内在这一领域的研究还不成熟，从各类文献资料可以找到的相关项目和论文较少，下面列出国内几个较有代表性的项目和文献：( 1 ) 国防科技大学的多媒体数据库项目国防科技大学是国内较早开展多媒体数据库研究的单位之一，其多媒体系统( 9 】一书在多媒体研究领域影响较大。他们在语音识别研究的基础上对新闻视频建立索引。目前该项目已建立了一套多媒体数据库管理的原型系统。( 2 ) 语义联想支撑基于内容的视频检索【1 0 l这是浙江大学计算机系的研究成果，该系统从视频字幕提取文本信息，然后使用语义联想的方法来提高检索性能。其具体实现利用了两种已有的设备和软件：4s u n b e l t 公司的字幕捕捉卡t e x t g r a b b e r 和普林斯顿大学的g e o r g e m i i l e r 等人开发的电子词典系统w o r d n e t 。该项目建立了名为w e b m a r s 的视频信息检索系统。( 3 ) t v 一兀( t s i n g h u av i d e of i n d1 0 系统t v - f i 是清华大学研究开发的视频节目管理系统，其功能为：视频数据入库，基于内容的浏览、检索等。系统提供多种查询访问视频数据的模式，包括：样例查询、关键词查询、按视频结构浏览、按用户预定义类别浏览等。( 4 ) m i r e s l l l j中国科学院计算技术研究所和北京图书馆联合开发的m i r e s ( m u l t i m e d i ai n f o r m a t i o nr e t r i e v a ls y s t e m ) 是一项国家8 6 3 计划，该系统是一个基于i n t e r n e t 的多媒体信息检索系统，支持样例查询、关键词查询或两种查询的混合模式，可用于视频检索等相关领域。1 2 论文的主要研究工作本文主要研究一个基于相关反馈的视频语义检索原型系统，希望在视频语义的自动标注集上研究视频检索的方法，以期提高检索精度。在我们的研究中，视频语义始终处于一个基础而重要的地位频语义特征用于对视频关键帧进行描述，在本文中我们利用视频语义构造一种视而相关反馈则作为一种高效的辅助手段，共同组成研究工作中的主要部分。之所以引入视频语义特征，是由于在基于内容的视频检索与分析研究领域中，存在着一个众所周知的难以回避的问题“语义鸿沟( s e m a n t i cg a p ) 叫“，我们希望设计一种视频语义特征来对这个问题进行一定的弥补。在开始论文工作之前，我们已经使用一种自动的方法对视频语义进行标注，从而得到一个视频语义集合，本文的研究工作均基于这个语义标注集合。对于视频检索中的相关反馈技术，我们根据其小样本学习的特点，以支持向量机作为反馈中的分类器。鉴于支持向量机运算量较大，我们又选择并实现了一个快速的支持向量机学习方法一s m o 。在相关反馈检索中，用户先后两次执行同样的查询操作时，不得不重复相同的反馈操作，这是因为在通常的相关反馈系统中，用户反馈信息只存在于本次检索过程中，一旦检索结束，反馈信息也即刻被丢弃，这样的相关反馈是一种拥有短期记忆的学习机制，显然这会加重用户的负担。因此，我们从语义信息出发，构建一个语义标注与关键帧之间的关联网，然后以用户的反馈信息为依据，修改语义概念与关键帧之间的权值，对这个关联网络进行更新维护。在返回结果时，5将结果集中的关键帧按照语义匹配的程度进行排序。为了对检索性能做出较客观的评价，我们还提出了一种综合考虑准确率、查权率以及正确结果排位的综合指标。1 3 论文的组织结构本文各后续章节内容组织如下：第二章，介绍支持向量机的相关理论，以及一种训练支持向量机模型的快速方法一s m o 算法。第三章，介绍相关反馈技术及其优缺点，提出一个基于支持向量机的视频检索相关反馈模型。第四章，基于前两章的研究结果，构建一种低维的描述视频语义信息的语义特征，提出一个具有长期学习记忆机制的、基于相关反馈的视频语义检索原型系统。第五章，对论文的研究工作做出总结，对视频内容分析与检索领域的研究做出展望。62 支持向量机与传统的统计学相比，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s l t ) 是一种专门研究小样本情况下机器学习规律的理论。前苏联学者v n v a p n i k i j 等人从六、七十年代开始致力于这个方面的研究，到九十年代中期，随着该理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。统计学习理论是建立在一套较为坚实的理论基础之上，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ；同时，在这一理论的基础之上发展了一种新的通用学习方法支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 1 4 - 1 5 1 ，它已经初步表现出很多优于已有方法的性能，一些学者认为，s l t 和s v m 正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。支持向量机是一种学习机制，可用于模式识别和回归估计。支持向量机的概念是v a p n i k 等人在1 9 7 4 年提出的，但直到最近几年才受到重视，并开始成为人工智能界的一个研究热点。该项研究属于机器学习、模式识别和人工神经网络等多个学科，由于它与这些学科现有的理论和方法相比有明显的优越性，因此有重大的潜在应用价值。支持向量机的优越性表现在：( 1 ) 支持向量机是根据结构风险最小化原则，尽量提高学习机的泛化能力，即由有限的训练样本得到的小的误差能够保证对独立的测试集仍保持小的误差。( 2 ) 支持向量机算法是一个凸优化问题，因此局部最优解一定是全局最优解。支持向量机的这些特点正是其它学习算法，如人工神经网络学习算法等所不及的。支持向量机的理论基础是统计学习理论。传统的学习机器采用经验风险最小化准则，即使训练集的误差尽量小。缺点是在训练集有限时，不能保证小的期望风险，即训练集的误差小并不能保证在测试集上误差也小，这就是泛化能力问题。统计学习理论就是研究有限样本的学习问题，采用结构风险最小化准则，既考虑减, b i f l 练集的误差，也兼顾减小学习机的复杂性，称为v c 维，从而保证好的泛化能力。支持向量机分类器的基本原理是使用一个非线性变换将一个线性不可分的空间映射到一个高维的线性可分的空间，并建立一个具有极小v c 维数的分类器。该分类器仅由大量样本中的极少量支持向量确定，且具有最大的边界宽度。支持向量机算法的技巧在于不直接计算复杂的非线性变换，而是计算非线性变换的点积，即核函数，从而大大简化了计算。通过把核函数引入到一些学习算法，可以方便7地把线性算法转换为非线性算法，我们将其与支持向量机一起称为基于核函数的方法。支持向量机表现出来的优越分类能力，使其成为图像、视频内容分析与检索技术中一个受到重视的工具。目前，以有研究者利用支持向量机在人脸、动作、表情、视频字幕等对象的检测上，以及在手写文字、生物特征等识别问题上，均取得了较好的成绩。因此，我们希望在我们的检索方法中使用支持向量机，以提高检索性能。2 1 统计学习理论2 1 1 机器学习机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使其能够对未知输出做出尽可能准确的预测。一般表示为：变量与存在一定的未知依赖关系，即遵循某一未知的联合概率f ( x ，y ) ，机器学习问题就是根据玎个独立同分布观测样本：k ，_ ) ， b 2 ，y 2 ，k ，) ，。)但1 )在给定的一个函数集合 ，g ，a ) 中找到一个最优函数1 ( x ，口。) 对依赖关系进行估计，使得期待风险r ( a l 最小：r b ) - 弘( ) ，g ，a ) 归g ，y )( 2 2 )由于f ( x ，y ) 是一个未知的联合概率分布，无法经由上式求出r ( a ) ，因此在实际中使用经验风险代替：r 。仁) = z l ，k ，口1 ) ，t 】产( 2 3 )式( 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 ) 1 6 1 。经验风险是通过损失函数计算的，对于分类问题的损失函数来说，经验风险就是训练样本的错误率；对于回归问题来说，经验风险就是平方训练误差；而对于概率密度估计问题的损失函数来说，e r m 准则就等价于最大似然法。实际上，经验风险最小并不一定意味着期望风险最小，只有样本数趋向无穷大时，经验风险才有可能趋向期望风险，而很多问题中的样本数目是有限的，在这种情况下，训练样本的误差小无法保证在测试集上误差同样小。神经网络的过学习问题( 过学习问题指在一些情况下，训练误差过小反而导致了预测错误率的增加) 即是一个典型的例子。图2 - 1 是一个更为直观的例子，这是一个回归问题中出现的过学习现象，如图所示，在训练集上回归方程能够很好地逼近目标函数，然而在测试集上却出8现了较大的误差。丘o v e r f t u n gr lo 训练浆6 测试缎图2 - 1 过学习问题统计学习理论就是研究有限学习样本问题，其核心思想是学习机器要与有限的学习样本相适应，这里的主要问题是看学习机的复杂性。统计学习理论给出了期待风险r 仁) 与经验风险j t 。k ) 之间的关系：胄仁) s i ，仁) + 中( h )( 2 4 )中( 矗肛) 为信任项，h 表示学习机的复杂性，称为v c 维( 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 ) 。2 1 2v c 维v c 纠1 3 j 表示了无差错学习任何数据的能力，即学习机的能力。模式识别方法中对v c 维的直观定义是：对一个函数集，如果存在h 个样本能够被函数集里的函数按所有可能的2 “种形式分开，则称函数集能够把h 个样本分开，h 的最大值就是函数集的v c 维。在有限训练样本下，v c 维h 越高( 即学习机的复杂性越高) ，月k ) 与j 乙，仁)之间可能的差别越大，这就是为什么会出现过学习现象的原因。在机器学习过程中，不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。如图2 2 ，当h n ，o 3 7 时，信任项大于1 ，超出信任上界而失去意义。9躺f p聩2 1 3 结构风险最小化图2 - 2 信任项是单调函数对于给定数目的学习样本，如果学习机的v c 维过大，即学习机复杂，则信任项大，r 仁) 与月一a ) 相差较大，产生过学习现象；若v c 维过小，即学习机简单，则学习机难以很好地近似训练数据。统计学习理论提出的方法是：构造一个函数子集序列，使各子集按v c 维从小到大排列，对每个子集计算最小经验风险，在子集间选择经验风险和置信度之和最小的子集结构风险最小化( s t r u c t u r a lr i s km i n i m i z a t i o n ) 1 3 】。如图2 3 所示，在函数子集s ：上，信任项与见。( 口) 之和最小，符合结构风险最小化。如果使用s ，则其在训练集上的误差让人难以相信其性能；而岛，根据v c 维理论，使用该子集中的函数很大可能出现过学习现象。实现s r m 原则可以有两种思路：第一种是在每个函数子集中求最小经验风险，然后选择经验风险和置信度之和最小的子集，然而这种方法比较费时问，当子集数目很大甚至是无穷时并不可行；因此还有第二种思路，即设计函数集的某种结构使得每个子集都能取得最小的经验风险( 如使训练误差为o ) ，然后只需要选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思想的具体实现。、脱险垃界缸顾；l 州一、卜2 2 广义最优分类面函数r 缘： c 是匕毛v c 缔： h 2 也图2 - 3 风险边界和s r m 原则的图形说明( 风险边界是j z 仁) 与信任项之和)h支持向量机( s u p p o r tv e ：c t o rm a c h i n e ，s v m ) 是一种基于统计的学习方法，它是对s r m 的近似。概括地说，s v m 就是首先通过用内积函数定义的非线性变换将输入空间映射到一个高维空间，然后再在这个空间中求广义最优分类面的分类方法。s v m 是从线性可分情况下的最优分类面发展而来的，基本思想可以用图2 - 4的二维情况说明。在图中，实心点和空心点分别代表两类样本，h 为分类线，日，和日，分别为过各类中离分类线最近的样本并且平行于分类线的直线，它们之间的距离称作分类间隔( m a r g i n ) 。最优分类线就是要求分类线不但能将两类正确分开( 即训练错误率为0 ) ，而且同时使分类间隔最大。1 1图2 4 线性可分情况下的最优分类线上述分类线方程为：x 。w - b = 0 ，( 2 - 5 )通过对式( 2 5 ) 进行归一化，使得对线性可分样本集杠。，y 。 l x e r d , ) ， - u ，f - 1 ，n 葫足：y i w 。x 1 ) - b 1 - 1 t o o ，i - 卜，“( 2 - 6 )此时分类间隔脚a r g 加一2 l l w l i ，使分类间隔最大等价于使1 1 2 最小。满足式( 2 6 ) 且使得l 2 2 最小的分类线就称为最优分类线，h 。和h ：上的训练样本点就称作支持向量。易知，支持向量只是训练集样本中的- - , j , 部分，而对分类起作用的也只有这小部分的支持向量样本。使分类间隔最大实际上就是对推广能力的控制，这也是s v m 的核心思想之一。从直观上理解，分类间隔越大，则表明两类数据不易混淆，对于未知数据有更大的容错能力，若分类间隔小，则未知数据易落入另一类样本区域中。另外，统计学习理论指出，在维空间中，设样本分布在一个半径为r 的超球范围内，则满足条件i ( a 的正则超平面构成的指示函数集f ( x ，嵋6 ) = s 印( ( ，x ) - b )( 2 7 )的v c 维满足下式的界：hs l i n 忙2l ) + 1 ，( 2 8 )因此使0 叫1 2 最小就是使v c 维的上界最小，从而实现了s r m 准则中对函数复杂性的选择。利用拉格朗日优化方法可以把上述最优分类面问题转化为其对偶问题，即在约束条件y ；q o 和q2 0 t ( 其中f 1 ，厅) 对q 求解下列函数的最大值矽缸) - 善q 一言乏口口，咒y ，k 。工，) ，( 2 - 9 )其中q 为每个样本毛对应的拉格朗日乘子这是一个不等式约束下的二次函数求优问题，存在唯一解，解中将只有一部分( 通常是少部分) 口，不为0 ，其对应样本就是决定分类间隔的支持向量。求解上述问题后得到的最优分类函数如下：，b ) ms 印( ( w 工) 一6 ) - s g n l z 西y j “。j ) 一b i ，( 2 1 0 )、l 。1式( 2 1 0 ) 中的求和运算，实际上仅对支持向量口j 进行，b 是分类阙值，可以通过任何一个支持向量求得、或由两类中任意一对支持向量取中值求得。在线性不可分情况下，可以在式( 2 6 ) 中增加一个松弛因子喜= 0 ，则有：儿w ) - b 1 - 1 + 岛乏0 ，i 一1 ，厅( 2 1 1 )相应地将目标改为求吉l i 叫| 2 + c i 舅l 最小，其含义是折中考虑最少错分样本和最大分类间隔，由此得到广义最优分类面。其中惩罚因子c 是一个大于0 的常数，用于控制对错分样本的惩罚程度，该参数的调整将影响到分类时的推广能力。广义最优分类面的对偶问题与线性可分情况下几乎完全相同，只是口j 的约束变为0 s 口c 。2 3 支持向量机由上所述，我们知道学习问题为最小化目标函数r 宇) 。抑2 + c 【荟每) ，( 2 - 1 2 )其约束条件为罗y ，a 。= o 和0 5 qs c ( 其中i - 1 , ， ) 。由于引入了松弛项毒，在线性不可分的悟况下允许一定的错分。由式( 2 1 2 ) 可见，目标函数的第一项以减小v c 维为目的，第二项则用于减小经验风险，综合此二项以得到最小的期望风险。在线性可分的情况下，经验风险为0 ，v c 维得到最小化；在线性不可分的情况下，能够折中考虑经验风险和v c 维的最小化。为求解式( 2 1 2 ) 的最小化问题，引入拉格朗日系数：u w ，b ， ，廛，y ) - w 。w + c 善一善口f 【) ，r ( w x l + b ) - 1 + 最卜善y ，( 2 1 3 )其中a ，土0 ，n2 0 ，f - 1 ， 函数l 应该对口j 和n 最大化，且对w 、b 和最最小化。l 的极值满足下列条件：专l - o 盖l 。0 ，寿b 0 ( 2 - 1 4 )q 乃一oc q 一 - o , i 一1 ，玎( 2 1 5 )i * 1。1 3将式( 2 1 5 ) 带入式( 2 1 3 ) ，便可得该优化问题的对偶形式，即最大化函数缈b ) 。善 去磊a j a j y ，y j k x j ) ( 2 - 1 6 )相应的，分类判别函数变成m ) 。咿【。磊量q 咒( m ) - b 】仁1 7 )式( 2 - 1 7 ) 就是支持向量机的数学模型。按照优化理论中的k u h n - t u c k c r 定理，在鞍点，对偶变量与约束的乘积为0 ，如下式：口【) ，x i + 6 ) 一1 + 每】一0 ，i - 1 ，履( 2 1 8 ) 0 氧一0 ，i 一1 ，厅佗1 9 )由式( 2 1 8 ) 可见，非0 的a ；对应的样本仅由离超平面最近的样本组成，这些样本完全确定了超平面，这些样本即为支持向量。对于0 t c ，由式( 2 1 5 )可知0 ( nc c ，再由式( 2 - 1 9 ) 知皇。0 ，因此有：y j ( w x i b ) 一1 ，( 2 - 2 0 )根据此式可以由口；e ( o ，c ) 对应的样本计算出b 值。另外，支持向量机的求解过程实际上是一个二次规划问题( q u a d r a t i cp r o g r a m m i n g ，q p ) 的求解，根据优化理论的k u l m t u c k e r 定理，可得该q p 问题最优点的k k t 条件：fa i ；0 ，式( 3 一1 5 ) 一扎一c ，式( 3 1 9 ) 一岛- 0 , 式( 3 1 8 ) ；y , f ( x i ) 2 1 o c qco ，式( 3 1 5 ) 一n ，o ，式( 3 1 9 ) 一磊一o ，式( 3 1 8 ) 一y , f ( ) - 1( 2 2 1 )lq c ，式( 3 1 5 ) 4 n - 0 , 式( 3 1 9 ) j 毒苫o ，式( 3 1 8 ) 4y j ，( 毛) - 1在非线性分类问题中，首先使用一个非线性映射中把数据从原空间r 。映射到一个未知的高维特征空间q ，然后在q 中建立优化超平面。在实际问题中，特征空间q 的维数可能非常高，而支持向量机算法巧妙地解决了这个问题。观察算法可以发现在线性情况下只使用尺4 空间中的点积运算，因此，我们