（通信与信息系统专业论文）基于“词袋”模型的图像分类系统.pdf

基于“词袋”模型的图像分类系统中文摘要 基于“词袋模型的图像分类系统 中文摘要 作为图像检索、图像识别、图像过滤等方法的关键技术，基于内容的图像分类技 术已成为模式识别领域中的一个重要研究方向，它的日的是将图像数据按照自身的语 义特征进行分类，“词袋模型在基于内容的图像分类领域中取得了很大的成功，因 此越来越受到大家的重视。但是，在构建视觉词汇表的过程中，当前的很多方法只是 简单的将底层特征进行聚类，并没有考虑图像区域之间的空问关系，这导致了词汇表 不够准确和稳定。本论文引入和改进了几种能够结合空间信息的算法，用于构建视觉 词汇表。本文的主要贡献在以下几点： 首先，提出了一种演化s o m s d 算法对传统的s o m s d 的神经网络算法进行加 速并用来进行图像分类。传统的s o m s d 算法的最大优点是它能够有效处理结构数 据，区分相似度较高的对象。但是，由于引入了空问信息，s o m s d 计算量非常大， 影响了其在大规模图像库上的应用。在保留s o m s d 处理结构数据能力的前提下， 本文利用分层演化思想提高计算效率。实验证明：演化s o m s d 算法在图像分类性 能上比没有考虑结构信息的传统算法有了明显的提高，。其计算速度远远高于传统的 s o m s d 算法。 其次，提出了一种基于空间约束的分层模糊c 均值算法，该算法是基于f c m s ( 基于空间约束的模糊c 均值算法) 改进而来的。相比k 均值，其避免了噪声对视 觉词汇的影响，增加算法聚类的鲁棒性；相比f c m s ，其提高了算法的计算效率。 在相同环境下的实验证明，该算法在图像分类的鲁棒性和计算效率方面都有了明显的 提高。 关键词：图像分类，词袋模型，b a go f w o r d s ，b o w ，s o m - s d ，e v o l v i n gs o m s d ， f c m s ，f c m h s 作者：周鸽 指导老师：王加俊 a b s t r a c tb a g o f - v i s u a lw o r d sf o ri m a g ec a t e g o r i z a t i o n b a g - o f - v i s u a lw o r d s f o r i m a g ec a t e g o r i z a t i o n a b s t r a c t c o n t e n tb a s e di m a g ec a t e g o r i z a t i o n ，a sak e yt e c h n i q u eo fi m a g er e t r i e v a l ，i m a g e r e c o g n i t i o na n di m a g ef i l t e r i n g ，h a sb e c o m eo n eo f t h em o s ti m p o r t a n tr e s e a r c ha r e a si nt h e f i e l do ft h ep a t t e r nr e c o g n i t i o n i ta i m sa tc l a s s i f y i n gi m a g e si n t od i f f e r e n ts e m a n t i c c a t e g o r i e s t h eb a go fv i s u a lw o r d sm o d e lw h i c hh a sa c h i e v e dal o to fs u c c e s si ni m a g e c l a s s i f i c a t i o na t t r a c t sm o r ea n dm o r ea t t e n t i o n h o w e v e rm o s te x i s t i n ga p p r o a c h e s c o n s t r u c tav i s u a lv o c a b u l a r yb ys i m p l yc l u s t e r i n gi m a g er e g i o n sr e p r e s e n t e dw i t h l o w - l e v e lv i s u a lf e a t u r e s ，w h e r es p a t i a lc o n t e x to fi m a g er e g i o n sh a sn o tb e e nw e l lu t i l i z e d t h i st h e s i sa d o p t e da n di m p r o v e ds o m em e t h o d sw h i c hc a l lt a k et h es p a t i a lc o n t e x ti n t o c o n s i d e r a t i o n t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： f i r s t l y , an e wa l g o r i t h mc a l l e de v o l v i n gs o m s di sp r o p o s e df o rt h ea c c e l e r a t i o no f t h ec o n v e n t i o n a ls o m s df o ri m a g ec l a s s i f i c a t i o n t h em o s ti m p o r t a n ta d v a n t a g eo ft h e c o n v e n t i o n a ls o m - s di st h a ti tc a nd e a lw i t hs t r u c t u r a ld a t aa n dd i s t i n g u i s hs i m i l a r o b j e c t s h o w e v e r , i ti sn o ts u i t a b l ef o rl a r g ed a t a b a s eb e c a u s eo ft h ee x t r e m e l yi n t e n s i v e c o m p u t i n gt a s kr e s u l t e df r o mt h ec o n s i d e r a t i o no ft h es p a t i a li n f o r m a t i o n w er e s o l v e dt h e p r o b l e mw h i l ek e e p i n gt h ec a p a b i l i t y o fd e a l i n gw i t hs t r u c t u r a ld a t ab yu t i l i z i n ga h i e r a r c h i c a la n de v o l v i n gs t r a t e g y e x p e r i m e n t a lr e s u l t sd e m o n s t r a t e dt h a to u rp r o p o s e d m e t h o dp e r f o r m sb e t t e rt h a nt h o s ew i t h o u tc o n s i d e r i n gs p a t i a lc o n t e x ta n dc a ni m p l e m e n t m u c hf a s t e rt h a nt h ec o n v e n t i o n a ls o m s da l g o r i t h m s e c o n d l y , a na l g o r i t h mc a l l e df c m h si sp r o p o s e df o rt h ei m p r o v e m e n to ft h e f c m s ( f c mw i t hs p a t i a lc o n s t r a i n t s ) i t sm o r er o b u s tt ot h en o i s ec o m p a r e dw i t ht h e k - m e a n sa l g o r i t h m ，a n dm o r ee f f i c i e n tc o m p a r e dw i t ht h ef c m - sa l g o r i t h m e x p e r i m e n t a l i n t h es a m ee n v i r o n m e n ts h o w e das i g n i f i c a n ti m p r o v e m e n ti n t h er o b u s t n e s sa n d e f f i c i e n c yi ni m a g ec l a s s i f i c a t i o n i i b a g o f - v i s u a lw o r d sf o ri m a g ec a t e g o r i z a t i o n a b s t r a c t k e yw o r d s ：i m a g ec a t e g o r i z a t i o n ，b a go fw o r d s ，b o w , s o m s d ，e v o l v i n gs o m s d ， f c m s ，f c m h s i i i w r i t t e n b yg ez h o u s u p e r v i s e db yj i a j u nw a n g 基于“词袋”模型的图像分类系统第一章绪论 1 1 研究背景和意义 第一章绪论 在信息爆炸的二十一世纪，伴随着电子工业的突破以及数字化程度的不断加深， 随着计算机技术、数字图像处理技术和数据库技术的不断发展，当今的数字网络中每 天都会出现大量杂乱而未归类的数字资源。在这些资源中，数字图像作为其中最重要 的一种媒体存在形式所扮演的角色也不断被人们所认可和重视，这些图像资源在人们 的工作、学习、生活等各方面起到了重要的作用。与此同时，越来越多的传统资源被 不断转化成数字形式进行保存及传递，特别是图像资源，数字图像逐渐取代传统的胶 片图像，并且这种趋势还在不断加剧。在这些新老数字图像中，包含了千变万化的内 容，有人物图像、山水图像、车辆图像、建筑图像等等。为了方便对资源的管理，通 常我们需要把图像根据其表述的内容进行分类管理，即将特定的图像归到某一指定的 语义类别中。但是，面对如此海量的数字图像，人们发现，要对其进行分r - j 另j 类是一 件非常困难的事。 在使用传统的人工分类方法时，图片往往是依据人工对图片内容的标注进行分类 操作，其实质仍是在对文本信息的分类。这种方式已慢慢地被淘汰，主要原因有二： 一是对图像进行人工标注费时费力，尤其面对海量的图像库时，人工标注工作量巨大； 二是文本标注存在主观性和不确定性，直接影响到分类的准确性。 在二十世纪9 0 年代初，人们提出了基于内容的图像分类1 1 , 2 】的概念。基于内容的 图像分类不同于传统的基于文本的图像分类，它不需要过多的人工参与，而是利用图 像自身的特征来进行分类。 基于内容的图像分类具有广阔的应用前景，对图像检索、图像过滤、图像识别等 具有重要意义，主要包括： ( 1 ) 图像检索。二十一世纪，互联网中的图像资源以指数爆炸式速度不断增加。 面对庞大的图像资源，g o o g l e 、b a i d u 等互联网内容搜索提供商相继建立了自己的图 像搜索引擎，方便用户快速查找自己所需要的图像，但当前的图像检索系统大多基于 第一章绪论基于”词袋”模型的图像分类系统 图像的人工标识进行检索，很少是基于图像内容进行检索的，因而图像检索系统仍有 较大的发展空间。 ( 2 ) 卫星图像识别。卫星图像识别是指使用图像分类识别技术对卫星图像进行 分类识别。可以从中获得地形信息、温度信息、海洋信息等。卫星图像识别已成为图 像识别中应用最为广泛、最为成熟的技术之一。 ( 3 ) 医学图像分类。医院及医学研究机构每天会产生大量的医学图像，也需要 调阅大量的医学图像。采用有效的图像管理方法，根据不同的病理特征或者图像特征 进行分门别类，将大大提高医疗机构的工作效率，同时也会提高这些图像的医疗价值 和科研价值。 ( 4 ) 多媒体信息过滤。互联网及数字电视等数字网络的不断发展，为人们提供 了快速获取丰富资源的途径。根据国家的相关法律法规，相关发布商( 如电信、移动、 广电等单位) 需要过滤其中的部分内容，使用基于内容的图像分类技术便可以快速的 将需要屏蔽的内容从正常内容中分离出来。 1 2 图像分类的研究现状 在模式识别领域，现有的图像分类技术已经取得了不错的进展，但是它们通常还 存在着一些问题。一是，大部分图像分类模型都是基于图像的底层特征的，如直接根 据颜色、轮廓、纹理等底层信息进行分类，这种传统的分类模型算法无法解决图像分 类过程中的“语义鸿沟 问题1 3 。j ，因为计算机自动提取的图像视觉特征与人所理解 的图像内容存在巨大的差异。现有的所谓基于内容的图像分类其实都是基于底层的图 像特征，没有真正达到“语义级别。人类的智慧让我们对图像的语义能够轻而易举 地的获得和理解。通常人眼在判别图像的主题或者类别时，并非建立在图像底层视觉 特征的基础上，而是建立在对图像所描述的对象或事件的语义理解的基础上。这种理 解是日积月累得到的一种能力。怎样从图像的特征抽象出其内容或主题是跨越“语义 鸿沟”要亟待解决的问题，只有跨越此鸿沟，才能真f 地做到“基于内容 的图像分 类。二是，大多数图像分类算法总是忽视图像内容中目标与目标之间的空间关系【8 母l 。 这个缺陷已有研究人员指出，具体来说它们没有能够充分利用图像“暗示”给我们的 图像区域隐含的空间相关性。 2 基于“词袋”模型的图像分类系统第一章绪论 “词袋”模型( b a g o f - w o r d s ，b o w ) 0 0 - 1 2 是文本建模中最为成功的模型之一， 该模型已经被应用到现实的图像分类中，取得了非常不错的效果。早期的基于“词 袋”模型的图像分类算法可以实现高速的图像分类，但是它还是无法解决图像分类中 的“语义鸿沟问题及图像区域间空间关系被忽略的问题。 于是，有人使用文本语言建模( 1 a n g u a g em o d e l ，l m ) 1 3 - 1 5 1 筝j 概念考虑各个视觉 词汇之问的空间关系，并以此提出了一种称为b o w - l m 8 。9 1 的图像分类模型，它能够 较好地表达图像的高级语义信息，缓解甚至解决以上问题，达到较高的分类准确率。 1 3 本文主要工作 “词袋”模型是基于内容的图像分类系统中最为成功的模型之一，它是近些年图 像分类领域中的研究热点，但其技术还不够成熟，仍存在较大问题。其中一个问题在 于视觉词汇表构建过程中忽略了图像区域之间的相互关系，针对这个问题，本文引入 了s o m s d ( s e l f - o r g a n i z i n gm a pf o ra d a p t i v ep r o c e s s i n go fs t r u c t u r e dd a t a ) 算法和 f c m s ( f c mw i t hs p a t i a lc o n s t r a i n t s ) 算法进行聚类的基本思想。实验证明，s o m s d 达到了提高分类效果的目标，但其计算效率较低，而f c m s 算法则由于其计算效率 实在过低而无法实现。事实上，以上两种算法都存在计算效率下降的问题，主要原因 是这两种算法都引入了空间信息，导致了训练样本个数增多、目标函数复杂度增加。 鉴于此，本文提出了基于演化树的e v o l v i n gs o m s d 算法和基于分层结构的f c m h s 算法，这两种算法较好的解决了计算效率和计算性能之间的平衡。 1 4 论文组织结构 本文的内容组织如下： 第一章绪论：本章首先阐述了基于内容的图像分类技术的研究背景和意义，概 述了目前国内外图像分类算法的研究现状和研究方法，介绍了图像分类所面对的主要 技术瓶颈以及本文的主要创新点。 第二章基于“词袋 模型的图像分类系统简介：本章首先介绍了基于“词袋 模型( b a g o f - v i s u a lw o r d ) 的图像分类算法的基本概念、研究现状及基本流程，讨 论并分析了该模型的优缺点，提出了本文的算法改进思想。着重介绍了本文后续章节 第一章绪论基于“词袋”模型的图像分类系统 的研究对象基于“词袋”模型和语言建模的图像分类方案，概述了该方案的基本 实现步骤，最后列出了使用传统的b o w - l m 方法在相关数据库上的分类性能。 第三章基于自组织神经网络和演化自组织神经网络的视觉词汇表生成方法：本 章介绍了s o m s d 算法的基本概念、原理及其优缺点，并将其首次引入到视觉词汇 表的构建过程中来，在c o t e c h 图像库上的实验证明，通过整合训练集中各图像区域 间的结构关系提高了系统的分类性能，但由于加入的结构信息，导致训练速度降低。 鉴于此，我们提出了一种可以自适应分层演化的e v o l v i n gs o m s d 算法，实验证明， 本章的算法提高了图像分类的性能。 第四章基于f c m h s 的视觉词汇表构建方法：本章首先介绍了f c m s ( f c m w i t hs p a t i a lc o n s t r a i n t s ) 算法的基本概念、原理及其优缺点，由于其目标函数非常复 杂导致训练速度明显降低，使得它无法应用于本文的图像分类系统中。于是，本章提 出了一种快速的分层算法( f c m h s ) ，并在c o t e c h 数据库上进行了验证，证明了本 章的算法能够有效提高图像分类性能及计算效率。 第五章总结和展望：本章简单总结了本文所作的主要工作并展望了所改进算法 将来进一步提高和改进的方向。 4 摹十“词袋”模型的图像分类系统第一二章基于“词袋”模型的图像分类系统简介 第二章基于“词袋 模型的图像分类系统简介 2 1 “词袋 模型概述 “词袋”模型( b a go f w o r d s ，b o w ) 是一种用于文本的经典表述方法【1 6 17 1 ，最 早用于文本分类，文本检索等领域，由于其快速、高效性，在文本领域中取得了巨大 的成功。但早期的“词袋模型忽略了特征之间的空间位置关系，造成了一些信息的 损失。尽管如此，由于其能方便、快速的构造出设计模型，还是得到了广泛的应用。 在此基础上，对比图像和文本的差别，有人提出了“视觉词袋”模型( b a go f v i s u a lw o r d s ) 的概念i i ，将“词袋 模型从文本领域引入到基于内容的图像分类问 题中来。一般来说，一篇文档通常可以看作是由若干文本单词组成的，而一幅图像则 可以看作是由若干个视觉词汇( 图像区域) 构成的。因此，既然由一篇文本文档可以 得到词条一文档( t e r m d o c u m e n t ) 共生矩阵，那么从一幅图像中同样可以得到视觉词 汇一图像( v i s u a lt e r m i m a g e ) 共生矩阵。这里的视觉词汇指的是按照各种不同图像 分割算法得到的图像区域。因此，经过各种分类器后得到的主题也就成了视觉主题。 基于主题的图像分类方法就是要按照不同图像主题，即视觉主题进行分类，图2 1 清 楚地表达了文本分类与图像分类的对应关系。 以上的“词袋”模型，在解决图像分类问题时，通常首先需要对图像进行分割， 接着提取每个图像区域的特征( 如图像的颜色、纹理、轮廓等) ，然后将每一个特征 用与其最接近的一个视觉词汇来表示，完成图像的“词袋”描述。最后，使用不同的 分类器进行分类，主要包括以下几类：d a n c e 【1 2 l 等提出的采用朴素贝叶斯分类器( n a i v e b a y e sc l a s s i f i e r ，n b c ) 、支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 相结合的方法； s i v i c 等陋2 0 1 引入的基于概率潜在语义分析( p r o b a b i l i s t i el a t e n ts e m a n t i ca n a l y s i s ， p l s a ) 图像主题的分类算法；b l e i 等【1 9 , 3 2 - 3 3 1 使用的潜在狄利克雷分配模型( l a t e n t d i r i c h l e a l l o c a t i o n ，l d a ) 自然场景图像分类方法，其中，p i e r r et i r i l l y 等 9 】人在传统 “词袋 模型中使用( l a n g u a g em o d e l ，l m ) 作为分类器，基于“词袋 和语言模 型的图像分类系统( b o w - l m ) 不但保留了传统“词袋”模型的方便和快速性，同时 第一：孥培f “涮袋”模型的图像分类系统简介皋寸。测袋”模型的图像分类系统 融入了词汇之问的空间结构信息，这使得图像的最终分类性能得到了很大的提升。 文本词汇1 文本词汇2 i l 一 文本词汇n i 朗絮吲 视觉词汇1 视觉词汇2 i i 视觉词汇n 图2 1b o w 在文本分类与图像分类中的对应关系 2 2 “词袋 模型基本原理 “词袋”模型是文本的简化描述模型。在此模型中，文本被表达成无序f l , o - q t 词组 合，不去考虑语法与词序。“词袋”模型虽然简单，但是非常有效。在文本分类中， “词袋”模型常和s v m 分类器、n b c 分类器结合，获得了非常好的分类效果。 、矽 蓬妇熬淄 瓣灞懑嗍 矽 图2 2b o w 住蚓像分类系统中的表述原理 巷壁蠢 基于“词袋”模型的图像分类系统第二章基于“词袋”模型的图像分类系统简介 将“词袋”模型应用到图像分类领域中来，可以把“词袋”模型直观地理解为将 每一幅需要描述的图像转化为一袋子典型的无序的视觉词汇的组合，如图2 2 所示。 具体到本文所使用的b o w 表述模型，它的基本实现过程如下： 第一步，对图像采用均匀分割的方式生成图像区域，即采用n x n 的固定网格来 对图像进行均匀分割，这样每幅图像可以得到n x n 个图像区域： 第二步，利用尺度无关特征变换( s c a l ei n v a r i a n tf e a t u r et r a n s f o r m ，s i f t ) 1 2 5 1 提取图像区域的特征，每一个图像区域被描述成一个1 2 8 维的特征向量； 第三步，使用非监督聚类算法( 如k 均值) 对训练集上所有图像区域的s i f t 特 征进行聚类，每一个聚类中心即对应一个视觉词汇，从而生成一个由k 个视觉词汇 构成的视觉词汇表( 类比于文本的词汇表) ； 第四步，根据前面生成的视觉词汇表，将图像中每个图像区域的s i f t 特征对应 到视觉词汇表中的一个视觉词汇。具体来说，就是用图像区域的s i f t 特征与视觉词 汇表中的每个视觉词汇所对应s i f t 特征进行比较，从而找出最相近的视觉词汇来表 示图像区域。 2 3 视觉词汇表构建 从图2 2 中可知，在图像转化为b o w 描述的过程中，无论是训练集的图像还是 测试集的图像，都要以视觉词汇表为参照标准，将每一个图像区域对应到视觉词汇表 中的一个视觉词汇，所以，如何构建一个完整而准确的视觉词汇表显得举足轻重。但 是，当前的构建方法往往只是依靠一些简单的非监督算法来实现，得到的视觉词汇表 并不够准确和稳定，在本节接下来的内容中，详细分析了s o m 、k 均值等算法在视 觉词汇表构建过程中存在的缺陷，并提出了问题解决的思路。视觉词汇表的构建流程 如图2 3 所示： 园一圈 图2 3 基t - b o w 视觉词汇表生成流程 第二帝堆f “词袋”模型的图像分类系统简介 綦十“词袋”模型的图像分类系统 2 3 1 图像分割及s i f t 特征提取 划分图像中有意义的区域对于图像分类有着重要的作用，人们获得图像区域的方 式通常有很多种，如自动分割、均匀分割等2 1 , 2 2 1 。考虑到当前的图像自动分割技术仍 然无法达到令人满意的程度，并且本文的重点不在于考察图像的分割算法，因此本文 对图像采用均匀分割的方式来生成图像区域，如图2 - 4 所示。若以8 8 的固定网格来 对图像进行分割，则每幅图像可以得到8 8 = 6 4 个图像区域，这样就可以对每一个区 域寻找其对应的b o w 描述。 需要说明的是，为了与本文后续章节中的新算法进行有效的对比，在使用k 均值 和s o m 算法进行聚类的过程中，本文只选择了8 8 分割后图像中心的3 6 个区域，即实 线框中的区域进行聚类。 鐾一雾 图2 - 4 图像均匀分割示例 通过均匀分割获得图像区域之后，下一步需要对所有的图片进行特征提取，这是 图像分类中非常重要的一个步骤，因为在整个图像分类过程中，真正参与分类计算工 作的其实是每一个图像区域对应的特征向量，因此，分类首要任务就是提取稳定的特 征，并进行描述，描述子的选取就至关重要。根据文献【2 3 】中的测试，本文使用了尺 度不变特征描述子( s c a l ei n v a f i a n tf e a t u r et r a n s f o r m ，s i f t ) 2 4 1 ，对每一个图像区域 进行特征提取，s i f t 特征用该区域梯度方向直方图表示，是一个1 2 8 维向量。 口口口i 口 基于“词袋”模型的图像分类系统第二章基卜“词袋”模型的图像分类系统简介 s i f t 是d a v i dgl o w e l 2 4 1 在2 0 0 4 年的提出的，该图像特征提取算法成功地被运 用到图像拼接、图像分类等计算机视觉课题中。最大的特点在于它对图像的尺度缩放 保持稳定的不变量( s c a l ei n v a r i a n t ) ，这对于处理现实中的各类物体、人、车或者风 景图像能够保持足够的稳定性，具有以下五个显著的优剧： 1 、s i f t 特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性， 对视角变化、仿射变换、噪声也保持一定程度的稳定性。 2 、独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。 3 、多量性，即使少数的几个物体也可以产生大量s i f t 特征向量。 4 、高速性，经优化的s i f t 匹配算法甚至可以达到实时的要求。 5 、可扩展性，可以很方便地与其他形式的特征向量进行联合。 2 3 2 聚类生成视觉词汇表 攀| ；“；弩一匡一- zf | ：王叠- w 。 i 巨三刍彷二。i _ 9 第二二章恭- f “词袋”模型的图像分类系统简介雉十”词袋”模型的图像分类系统 邻域信息，如虚线框内所示，( a ) 图周围出现了云彩( b ) 图周围出现了沙滩和小岛， 那么根据这些信息，很容易判断哪个是天空，哪个是海面；2 、噪声会干扰图像的表 述。如图2 7 所示，图中( a ) 与( b ) 分别是蓝色的天空和带有白色噪声的海面，( a ) 图中根据云彩可以判定中心区域为天空，但是( b ) 图中海面上的白色噪声点可能会 被误认为是云彩，产生干扰，导致误判。所以，针对以上第一点，本文提出了使用 s o m s d 及其改进算法e v o l v i n gs o m s d 的解决方案，针对第二点，本文提出了使用 f c m s 及其改进算法f c m h s 的解决方案。 ( a ) 带有云彩的天空( b ) 带有小岛的海面 图2 6 利用空间邻域信息区分相似区域的示例 ( a ) 带有云彩的天空 2 4 语言模型 ( b ) 带有小岛的海面 图2 7 利用空间邻域信息防i = 噪声的干扰 语言模型( l a n g u a g em o d e l ，l m ) 8 - 9 , 1 3 - 1 5 1 以一种完全不同的方式对语言文字进 行建模，经常应用于自然语言分类、文本分类和文本检索等领域 2 6 , 2 7 1 。可以将它理解 l o 基于“词袋”模型的图像分类系统第二章基于“词袋”模型的图像分类系统简介 为是一种针对语言文本建立概率分布的统计模型，建模的对象可以是常见的自然语 言，比如中文、英文、日文等，也可以是像计算机程序设计语言这样的逻辑语言。 根据贝叶斯原则，语言模型将语言看作是一个随机序列，语言中的一个句子或一 个词组都是具有一定分布的随机变量，所以，语言模型的基本原理就是计算文本语言 中任意字符序列w l w 2 出现的概率p r l ( i 嵋，w 2 一，) 。简化后的n - g r a m 模型在 文字语言识别领域中，占据着绝对主流的地位，目前，该模型性能优于其它任何一种 统计语言模型。它的特点在于不仅仅可以统计生成单独文字的概率模型，而且可以统 计生成语言序列的概率模型。 2 4 1 语言建模基本原理 在语言模型中，假设d 代表一个由k 个词顺序排列组成的文本序列，即d 代表文 字序列w 1 w ：1 4 t 。，那么，语言模型认为文字出现的概率同它前面的k - 1 个词有关 系，且d 出现的概率耽( d ) 定义如下： p r l ( d ) = 兀k 耽“l ，w 2 w 一，) ( 2 1 ) ，= l 实际使用中，出于计算效率的考虑，基于词的n - g r a m 模型得到了广泛的应用。 在n - g r a m 模型中，指定词的出现不再与其前面全部上下文相关，近似认为w k 的出 现概率只同它前面的胛1 个词相关。则公式( 2 1 ) 简化为下式： k p r l ( d ) = 兀p r l ( w l 彬一川w 一。) n l ( 2 2 ) t = l 其中，n = 2 的二元模型( b i g r a m ) 和n = 3 的三元模型( t r i g r a m ) 是最常使用的两类 n - g r a m 模型。以三元模型为例，语言模型近似地认为任意词的出现概率只同它前 面的两个词有关，即： k p r l ( d ) = 兀p r l ( w lw f 一：w ，一。) ，= l ( 2 3 ) 从公式( 2 - 2 ) 和公式( 2 3 ) 可以发现，根据离散的m a r k o v 模型定义，n - g r a m 模型相当于一个刀1 阶的m a r k o v 链，因此，它有时也被称作基于m a r k o v 的统计语 言模型。 第二章摹于“词袋”模型的图像分类系统简介基于“词袋”模型的图像分类系统 根据最大似然值估计原则，通常使用统计方法利用公式( 2 - 4 ) 估计词的条件 概率p t ( f ，w 2 h 一。) ： 刚小一) = 荆 ( 2 - 4 ) 其中，c ( w ) 表示词汇w 2 心在整个训练库r 中出现的次数。 2 4 2 零概率问题以及解决办法 语言模型在使用过程中，需要利用训练集中的数据来估计词的上下文概率分布， 一般这个过程称为语言模型的参数训练。根据公式( 2 4 ) 即可以完成大部分训练过 程，但是，由于词序列出现的概率p r l ( 1w l ，w 2 一。) 与在整个训练集中的出 现次数有关。根据z i p f 定律：大量的低频词，无论训练集的规模如何扩大，其出现 频度依然很低或根本不出现。所以，当采用公式( 2 4 ) 来估计词汇的概率分布时， 将面临零概率问题( 也称作数据稀疏问题) ，即低频词的上下文条件概率为零。 在n - g r a m 模型中，虽然扩大训练集，可以在一定程序上缓解以上问题，但在真 实语言环境中，即使词表再大，也不可能包含测试集中的所有词汇，总会有许多j 下确 的句子或者词组在训练集中从未出现，按照n - g r a m 模型的计算方法，这些句子的 p e ( d ) 概率都将为o 。也就是说，任何一个句子只要包含了一个在训练集中从未出现 或者出现的次数很少的词序列，那么，在识别过程中，不管句子中其它词序的条件概 率为多少，p r t ( d ) 三0 。这种情况严重影n i l _ j n - g r a m 模型的语言描述能力，应该极力 避免。所以，语言模型一般需要采用数据平滑技术( d a t as m o o t h ) 来解决该问题。 当前，语言模型所使用的数据平滑过程就是对采用最大似然估计原则估计的概率分布 进行调整，保证模型中任何概率参数均不为零，同时，使模型中的概率分布更加均匀。 数据平滑技术实现的基本策略主要有两剧9 】： 一、打折策略。将公式( 2 - 4 ) 中的c 0 用c = q ，d ( d c 。 1 3 第一- - 4 章皋于“词袋”模型的图像分类系统简介 基于“词袋”模型的图像分类系统 这里，t 的定义为：在给定文本序列w 2 叱的情况下，除序列w 。w 2 外，所有 以w t w 2 w k l 开始的序列的个数。 4 、k a t z 平滑技术 k a t z 平滑技术同时利用了g o o d t u r i n g 估计与低阶语言模型信息。其打折系数定 义为下式： d = ( c 0 + 1 ) v ( c w + 1 ) ( k + 1 ) v ( 七+ 1 ) g v ( c f f ，)v ( 1 ) 一掣舻 v il l 这里，k 的典型值为：七= 7 。 矾 t ，结束，否则，重复步骤( 2 ) 。 图3 3 演示了具有三个节点的d a g 数据在一个二维s o m s d 网格上的映射过程 【3 l 】，图中所有数据及映射过程均为假设，并非真实计算，并且从图中可知m = 2 ，c = 2 ， q = 2 。首先，末顶点3 的特征值( 2 2 7 ，1 3 ) 使用上文提到的特殊坐标进行重构，本 文特殊坐标值定为( 1 ，1 ) ，故重构后的特征值为( 2 2 7 ，1 3 ，1 ，1 ，1 ，1 ) ，将 该坐标值根据坂础进行映射，得到赢单元的坐标值为( 2 ，2 ) ；接着，根据顶点3 的 映射结果，重构顶点2 的特征值( 3 1 4 ，0 2 7 ) 为( 3 1 4 ，0 2 7 ，2 ，2 ，1 ，1 ) ，同 样的，将重构后的特征值根据鸠础进行映射，得到赢单元的坐标值为( 0 ，1 ) ：最后， 根据顶点2 和顶点3 对应的赢单元的坐标值，对根顶点1 的特征值( 0 0 7 ，o 0 5 ) 进 行重构，得到( 0 0 7 ，0 0 5 ，0 ，1 ，2 ，2 ) ，再根据m 。胁进行映射，最终得到根顶点 1 对应赢单元的坐标值为( 1 ，o ) 。那么，该d a g 最终的映射结果为：m 4 ( d ) = ( 1 ，o ) 。 2 7 第三章基于臼组织神经网络和演化白组织神经网络的 见觉词汇表生成方法基：j ：“词袋”模型的图像分类系统 3 3 3 0l23 ol23 0l23 图3 - 3s o m - s d 映射过程示例 3 3e v o l v i n gs o m s d 算法 使用s o m s d 算法所构建的视觉词汇表，能较好解决相似图像区域区分不够准 确的问题，即通过引入上下左右四个相邻图像区域来辅助聚类，使视觉词汇表的构建 更准确有效。但是，s o m s d 与s o m 相比，由于引入了结构信息，计算量明显增加， 基于“词袋”模型的幽像分类系统第三章甚于自组织神经网络和演化白组织神经网络的视觉词汇表生成方法 原因有两点：l 、聚类的样本数增加。从单一根顶点变为到每一个根顶点带有多个末 顶点；2 、映射空间放大。从仅需区分根顶点变为区分所有的末顶点和带有不同末顶 点的根项点。所以，在本文的视觉词汇表聚类过程中，虽然s o m s d 可以完成聚类 任务，但计算效率是最大的问题所在。 针对以上问题，本文提出了一种e v o l v i n gs o m s d 算法( 基于演化的s o m s d ) 。 该算法沿用了s o m s d 的基本映射思想，结合了文献 3 5 1 提出的分层演化的树形映 射空间，该映射空问可以在训练的过程中根据样本集不断地演化扩展，这种策略在很 多场合都得到了成功的应用【2 9 。1 1 ，包括在对s o m 算法的改进过程中【3 5 1 。相比标准的 s o m s d 算法，通过引入这种演化技术，一、使得原本处于同一平面内的神经元按照 分层树形拓扑结构分布，加快搜索速度；二、各聚类簇根据指定阈值参数自行决定演 化与否，有效控制聚类簇之间的相似度。 图3 4 描述了一个- - b l 树( m 。= 2 ) e v o l v i n gs o m s d 的基本演化过程【3 5 】，它 以根神经元为起点，根据训练空间的样本初始化其权值，然后，根神经元会分裂产生 m 。个子神经元，并且根据根神经元的权值进行初始化( m 。为神经元分裂值决定每 一次分裂产生的子神经元个数，适当的m 。既可以提高计算效率，同时也可以提高聚 类的准确度) 。在接下来的演化过程中，当任何一个末端神经元被选为赢单元的次数 ( 赢单元击中数) 超过事先设定的闽值t ( 赢单元最大击中数) 时，该神经元将再一 次进行分裂并产生虬。个新神经元，新产生的神经元被标记为该神经元的子神经元， 同时，使用父神经元的权值对其进行初始化。该步骤被不断地重复迭代，直至树形映 射空间不再发生改变。 ( a ) 赢单元搜索策略 a ( b ) 合作更新过程 图3 4m 。= 2 的e v o l v i n gs o m - s d 算法的分层映射空间 2 9 第三帝基于臼组织神经| l 习络和演化白组织神经网络的视觉词汇表生成方法基于“词袋”模型的图像分类系统 e v o l v i n gs o m s d 的训练算法与s o m s d 相似，可以表示如下：m 4 ( d ) ：y 一a ， 其输入空间中既包含了每一个顶点的标签信息，又包含了结构信息，而输出空间则是 一个降维的映射空间中的索引号。整个映射过程可以用下面的迭代公式实现： 聃 巍删1 1 ) ，一州，) ) 2 笔p ( 3 8 ) 膨卜1 比( 弘，彬( ) ，蟛( d ) ) 。历洲妇 u 嗡 与s o m s d 不同的是，由于映射空间为分层树型结构，无法用原先的坐标系来 描述映射结果，所以，本文给每一个神经元都赋予一个索引号，并用索引号来描述映 射结果。输入顶点v 重构后的特征向量可用+ 。( 即q = 1 ) 表示，由于它由m + c 维数 据组成，定义如下： 。 + 。2 h ，m ，k ，k 一 ( 3 - 9 ) 这里，”，是d a g 顶点v 的标签向量，是顶点v 的第f 个子顶点对应赢单元索引 号，也就是说，+ 。由m 维标签向量( 即顶点本身的特征向量) 和c 维子顶点对应赢 单元的索引号构成。同样，对于所有末顶点，由于其不存在任何子顶点，需使用特殊 的坐标向量n i l 来定义其中的c 维数据，但n i l a 必须定义在输出空间以外。 另外，式中的磁础与s o m s d 中相同，需完成竞争与合作两个步骤： 假设计算赢单元时，每一个带有坐标向量c 。的神经元都对应着一个权值向量 w f 孵” 第一步，竞争：竞争的目的是查找赢单元，e v o l v i n gs o m s d 引入了类似于 t s s o m ( t r e e s t r u c t u r e ds o m ) 3 6 1 的搜索策略来提高效率。以图3 。4 为例，每一个 父节点拥有两个子节点，黑色节点表示末端节点，作为最终映射空间中的一个神经元； 白色节点为中间节点，是算法训练过程中的临时节点，并不被作为最终映射空间中的 神经元。赢单元搜索过程如图3 4 中( a ) 所示，从根节点丌始自上而下进行，当一 个父神经元被确定后，只有其对应的子神经元会被继续搜索，重复以上步骤，直至寻 找到对应的末神经元作为赢单元，以此达到减小搜索范围，提高计算效率的目的。 由于，e v o l v i n gs o m s d 的输入向量同样由标签特征和子节点坐标两部分构成， 在计算时，根据实际数据集按照公式( 3 5 ) 调整两者的权重。 第二步，合作：通过竞争过程选择到了赢单元嵋、，需要对赢单元嵋，及其相邻 神经元进行调整，使其与输入向量更加接近。合作过程与竞争过程相反，合作过程按 3 0 基于“词袋”模型的图像分类系统第三章基于白组织神经嘲络和演化自组织神经网络的视觉词；l 表生成方法 照由下至上的顺序对神经元进行更新，如图3 4 中( b ) 所示，其中的匹配距离仍按 公式( 3 6 ) 进行计算。 但是，在公式( 3 7 ) 中，选择相邻神经元的时候，由于神经元在不同的平面内， 无法按原先的规则计算，为此，引入如下的距离表示方法1 3 5 】： 在一个给定的树形空间中，两个神经元之间的距离定义为：两者之问的“最小跳 跃数”1 。以图3 4 为例，这罩的“最小跳跃数是指以黑色实线为路径，从一个节 点到另一个节点所需经过的实线的根数，图中可知，任一父节点与其子节点之间的距 离为0 ，同个父节点的两个子节点之间的距离为1 。 e v o l v i n gs o m s d 算法的实现步骤总结如下： 假设有限集d = 4 ，吐，以 是由门个d a g 样本组成的集合，( j = l ，2 ，3 ) 为 某一指定d a g 的中第，个顶点，k ( 扛1 ，2 ，3 ) 为映射空间中第f 个神经元的权值， 它的赢单元击中数为红。 ( 1 ) 设定e v o l v i n gs