（计算机应用技术专业论文）人体运动捕捉数据的检索.pdf

大连理工大学硕士学位论文 摘要 随着传感器技术的进步，人体运动捕捉技术日益成熟，并在动画制作、保健、医疗 诊断、运动分析、机器人控制、真实场景游戏，甚至家庭娱乐等领域中得到成功的应用。 经过三十几年的发展，逐步积累而成的运动捕捉数据库更是为运动捕捉技术的研究与重 用提供了良好的支持。然而，由于运动捕捉数据具有维度高数据量大的特点，因此如何 迅速且准确地从大型的人体运动捕捉数据库中检索出所需要的运动序列成为了人体运 动捕捉领域中亟待解决的问题之一。 对人体运动捕捉数据进行检索主要有两种形式：基于语义描述的检索和基于运动样 本的检索。基于语义描述的检索是指用户采用一段文字来描述需要的检索的运动，系统 根据文字描述从数据库中检索出与待检索运动在语义上最为相关的运动。基于运动样本 的检索是指用户可以采用一段运动捕捉片段来描述有待检索的运动。系统根据待检索的 运动片段本身所包含的数值信息，从数据库中检索出数值上最为相近的运动序列。 为了解决基于语义描述的检索问题，本文采用条件随机场方法，对运动捕捉序列进 行语义标注。条件随机场包括两个过程：训练过程和标记过程。在训练过程中，仅需做 出高层语义的标注，如“走”、“跑 、“跳等。训练时，用k 一均值方法从训练样本 中提取特征，并用提取出的特征构建c r f 中的特征函数。经过训练的条件随机场可用来 标注未知序列，从而得到该序列的高层语义特征，有利于进一步的索引建立。实验结果 表明，在选取了合适的训练集合及参数的情况下，本方法可以正确和全面地在未知长序 列中标记出训练集合中所含有的语义特征。 为了解决基于运动样本的检索问题，本文提出了一种通过维度熵的降序排列构造的 符号图模型。首先通过类似拉班舞谱的空间分割法将m 维时间序列数据转化为k 维的 符号序列。然后将维度按照信息熵进行降序排列并构建层次结构的符号状态转换图。则 检索问题转化为求符号图上一条路径所经过的各个节点所代表集合的交集。实验结果表 明符号图模型是一种有效的索引方法。 关键词：运动捕捉；检索；条件随机场；符号化 大连理工大学硕士学位论文 r e t r i e v a lo fh u m a nm o t i o nc a p t u r ed a t a a b s tr a c t t h et e c h n o l o g yo fh u m a nm o t i o nc a p t u r et a k e si t sa d v a n c e m e n t sa l o n gw i t ht h e d e v e l o p m e n to fm o d e ms e n s o r i th a sb e e na p p l i e di nt h ea r e a so fv i v i da n i m a t i o n , h e a l t hc a r e ， c l i n i cd i a g n o s i s ，m o t i o na n a l y s i s ，r o b o tc o n t r o l ，r e a l - s c e n eg a m e ，e v e nf a m i l ye n t e r t a i n m e n t a f t e rt h ed e v e l o p m e n tf o rm o r et h a nt h r e ed e c a d e s ，t h ea c c u m u l a t e dd a t a b a s eo fh u m a n m o t i o nc a p t u r ed a t ap r o v i d e sa d v a n c e ds u p p o r tf o rs t u d ya n dr e u s eo ft h eh u m a nm o t i o n c a p t u r ed a t a b t i tt h eh u m a nm o t i o nc a p t u r ec i a t ai sak i n do fh i 曲d i m e n s i o n a ld a t aa n d c o m p r i s e sl a r g ea m o u n to fi n f o r m a t i o n s oh o wt o r e t r i e v ed e s i r e dm o t i o ns e q u e n c e e f f i c i e n t l ya n dq u i c k l yo u to fal a r g eh u m a nm o t i o nc a p t u r ed a t a b a s er e m a i n sa nu n s o l v e d p r o b l e mi nt h ea r e ao fh u m a nm o t i o nc a p t u r e t h e r ea r et w ok i n d so fr e t r i e v a l ：s e m a n t i cb a s e dr e t r i e v a la n dm o t i o nb a s e dr e t r i e v a l s e m a n t i cb a s e dr e t r i e v a lm e a n st h a tt h er e t r i e v a ls y s t e mt a k e st h ew o r d ss p e c i f i e db yu s e r d e s c r i b i n gt h es e m a n t i cf e a t u r eo ft h em o t i o na si n p u t ，a n dr e t r i e v e st h em o s ts e m a n t i c l y r e l e v a n tm o t i o ns e q u e n c e s m o t i o nb a s e dr e t r i e v a lm e a n st h a tt h er e t r i e v a ls y s t e mt a k e sa m o t i o ns a m p l es p e c i f i e db yu s e ra si n p u ta n dr e t r i e v e st h em o s tn u m e r i cs i m i l a rm o t i o n s e q u e n c e 1 1 1 i sp a p e l s o l v e st h es e m a n t i cb a s e dr e t r i e v a lp r o b l e mb yc o n d i t i o n a lr a n d o mf i e l d ( c r f ) t h e r ea r et w op r o c e d u r e so ft h ec o n d i t i o n a lr a n d o mf i e l d ：t h et r a i n i n gp r o c e d u r ea n d t h ei n f e r e n c ep r o c e d u r e h i g hl e v e ls e m a n t i cf e a t u r e sa r en e e d e dt ob em a r k e do u tf o rt h e t r a i n i n gd a t a k - m e a n si s i n v o l v e di n t ot h et r m n i n gp r o c e d u r et og e n e r a t et h ef e a t u r e f u n c t i o n s t h et r a i n e dc r fm o d e lc o u l db eu s e dt ol a b e ln e wu n k n o w ns e q u e n c e sw i t l lh i 曲 l e v e ls e m a n t i cf e a t u r e sw h i c ha r ev e r yu s e f u lf o r t h ei n d e x i n gp r o c e d u r ea f t e r w a r d t h e e x p e r i m e n tr e s u l ts h o w st h a tt h i sm e t h o dc o u l dl a b e lt h es e m a n t i cf e a t u r e so u tc o r r e c t l ya n d c o m p r e h e n s i v e l yw h e np a r a m e t e r so ft h em o d e la r ec h o s e na p p r o p r i a t e l y t os o l v et h em o t i o nb a s e dr e t r i e v a lp r o b l e m ，t h i sp a p e rp r e s e n t sa ni n d e xs t r u c t u r ec a l l e d s y m b o lg r a p h f i r s t ，t h i sm e t h o dt r a n s f o r m st h eh u m a nm o t i o nc a p t u r ed a t ao fm d i m e n s i o n s i n t oakd i m e n s i o n a ls y m b o ls e q u e n c et h r o u g he q u a l l ys p a t i a ld i v i s i o n t h e nh i e r a r c h i c a l s y m b o lt r a n s f o r m a t i o ng r a p hi sc o n s t r u c t e db yt h ed e c e n to r d e ro fe n t r o p ya te a c hd i s t i n c t d i m e n s i o n s ot h er e t r i e v a lp r o b l e mt r a n s f o r m si n t o 也ei n t e r s e c t i o no fn o d e sa l o n gap a t hi n t h es y m b o lg r a p h e x p e r i m e n tr e s u l ts h o w st h a ts y m b o lg r a p hi sa ne f f i c i e n ti n d e xs t r u c t u r e k e yw o r d s ：m o t i o nc a p t u r e ；r e t r i e v a l ；c o n d i t i o n a lr a n d o mf i e l d ；s y m b o l i z a t i o n i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：兰2 篮亟边歪匿：迄越j 堡垒至拴盎2 作者签名：i 盔堡丕堕日期：趁监年j l 月_ 2 日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理工大学硕士学位论文 1 绪论 1 1 研究背景 二次世界大战后，在斯坦福大学神经生物力学实验室中，一种用予康复领域中，用 于对伤残、截肢、脑瘫、帕金森症患者运动及行为学分析研究及物理治疗的新技术诞生 了。这就是动作捕捉技术。从2 0 世纪7 0 年代开始，此项技术被逐渐应用于动画制作领 域，包括迪斯尼公司在内的许多动画制作公司，曾试图利用此项技术，通过捕捉演员的 动作以改进动画制作效果。他们通过纽约计算机图形技术实验室的r e b e c c aa l l e n 设计 的一种光学装置，将演员的表演姿势投射在计算机屏幕上，作为动画制作的参考。对此 项研究的正式展开是在2 0 世纪8 0 年代开始的，美国b i o m e c h a n i c s 实验室、s i m o nf r a s e r 大学、麻省理工学院等同时介入了计算机人体运动捕捉的研究。此时的研究始终滞留在 在试用性研究，而在8 0 年代末，越来越多的研究人员和开发商的目光逐步转向了实用 化。比如在1 9 8 8 年，可捕捉人头部运动和表情的系统由s g i 公司开发成功。现如今， 进入实用化时代的运动捕捉技术，随着计算机软硬件技术的飞速发展和动画制作品质需 求的提高，发展成为可由运动捕捉设备支持的商品，例如m o t i o n a t m l y s i s 、p o l h e m u s 、 s e g ai n t e r a c t i v e 、m a c 、x - i s t 、f i l m b o x 、v i c o n 等。 动作捕捉技术提供了在动画制作领域之外的新的人机交互手段。这种手段不仅可以 实现“三维鼠标 和“手势识别 ，还使操作者能以自然的动作和表情直接控制计算 机，并为最终实现可以理解人类表情、动作的计算机系统和机器人提供了技术基础。就 简便快捷而言，新的手段远远优于传统的键盘与鼠标操作。 体育训练方面，运用运动捕捉技术可以捕捉运动员的动作，进行量化分析，同时结 合人体生理学及物理学原理，研究改进的方法，使体育训练摆脱纯粹依靠经验的状态， 进入理论化、数字化时代。同时能够捕捉成绩较差的运动员的动作，并将其与优秀运动 员的动作进行对比分析，从而达到提高训练效果的目的。 在真实场景游戏中，由运动捕捉技术研发的新型游戏可以带给游戏者以一种全新的 参与感，加强游戏的真实感和互动性。参与者可利用运动捕捉技术捕捉游戏者的各种动 作，用以驱动游戏环境中角色的动作。 在机器人操纵方面，与传统的遥控方式相比，一种基于运动捕捉技术儿研发的系新 统可以实现更为直观、细致、复杂、灵活而快速的动作控制，大大提高机器人应付复杂 情况的能力。在机器人全自主控制尚未成熟的情况下，这一技术有着特别重要的意义。 人体运动捕捉数据的检索 这种系统是由机器人将危险环境的信息传送给控制者，控制者根据信息做出各种动作， 运动捕捉系统可以将动作捕捉下来，实时传送给机器人并控制其完成同样的动作。 如是则可看出，运动捕捉技术有着广阔的应用背景和激动人心的开发前景。但是， 以目前的技术水平来看，还存在着使用的仪器过于昂贵、过程过于复杂，整个运动捕捉 过程开销十分巨大等弊端，这就要求了对已有的运动捕捉数据必须进行最大程度的开发 和利用。于是重新利用现有的运动捕捉数据以适应新的需求，既对运动捕捉数据进行修 改、变换、拼接、融合等操作，已经成为运动捕捉技术领域中的新课题。 目前，运动捕捉技术经历了三十几年的发展，积累了大量的运动捕捉数据，例如 c m u g r a p h i c sl a b 发布的m o t i o nc a p t u r ed a t a b a s e 、e y e s ，j a p a n 提供的m o c a p d a t a 和 m o t e k 提供的m o t i o nc a p t u r ed a t as o l u t i o n s 等都是可以公开下载的数据捕捉库。这一切， 都为都为运动捕捉数据的重用提供了有力的支持。 在对运动捕捉数据进行必要的修改与合成以便适应当前需要之前，往往要先从已有 的动作库中快速、准确地检索出需要的动作序列。然而，人体运动捕捉序列一般具有较 高的维度，而且其中既蕴含有形的数值信息，又蕴含着无形的语义信息，信息量极大。 因此，如何利用计算机的辅助，自动从运动捕捉数据库中迅速、准确地检索出需要的运 动是一个亟待解决的问题。 1 2 国内外研究现状 1 2 1 数据的表示形式 对于运动捕捉数据检索系统，数据的表示形式对于检索系统有着至关重要的作用： 一方面，不同的数据表示形式从多个相异角度以不同的形式对运动捕捉数据中所蕴含的 信息进行加工、提取和运用，以适应不同检索工作的需求；另方面，不同的数据表示 形式往往对应着不同的空间维度，或者在时间维度上对序列进行不同程度的压缩，用更 少的数据表达更多的信息，从而提高检索系统的效率。 在已有的研究成果中，人体运动捕捉数据除了直接采用3 维坐标进行表示之外，还 可以采用关键帧、几何语义特征、场景描述语言、拉班舞谱等方法进行表示。 由于运动捕捉数据具有较高的采样频率，对其进行关键帧的提取可以从时间维度上 对原始序列进行有效的压缩。对此，浙江大学的杨涛等人提出基于分层曲线简化的捕捉 数据的关键帧提取l l 】【2 】。他们首先引入骨骼夹角作为运动特征，并以此确定候选关键帧； 然后采用分层曲线简化算法精选候选关键帧获得最终关键帧集合。最后通过对算法参数 自适应调节，以满足不同压缩率要求。 大连理工大学硕士学位论文 m e i n a r dm u l l e r 等人认为“逻辑上相似的运动未必在数值上相似 。于是他们在此 基础上引入了一系列定性的具有几何相关性的特征来描述人体运动捕捉数据。通过这种 从数值到逻辑的转换，既可以对运动捕捉数据进行自适应的分段，又可以方便地进行人 体局部运动姿态的检索，并采用灵活可变的索引方式对大型数据库建立索引【3 l 【4 】嘲。高 岩等人在此基础上提出场景描述语言【6 】川。他们使用三层结构：字、动作、场景来描述 运动场景。他们还特别指出通过采用场景描述语言，系统可以很有效地用场景描述语言 把用户输入的粗略的文本描述转化为精确的场景描述，这使得检索结果十分精确。另外， 场景描述语言还能够有效地实施多步骤的查询过程。 为了实现局部检索，z h a n gs h u n 等人提出采用拉班舞谱标记物体运动序列【8 】【鲥。首 先，给每一个运动捕捉数据库中的运动序列配有一个相对应的用拉班舞谱标记的序列。 然后，用有度量的相似性测量方法去测量拉班舞谱序列之间的相似性并且找出具有相似 的拉班舞谱的序列，最后通过动态规划把这些动作序列片段紧密接合起来得到用户最理 想的检索结果。为了对拉班舞谱进行度量，采用以下距离公式来计算两个拉班拍e 和b ， 之间的距离： 一 d ( e ，哆) = l i v , 。- z j 斯 ( 1 1 ) k = l 其中，k 。，只。是拉班拍置和b ，中的第k 个关节分别映射到子空间的3 维单位向量。 表示第k 个关节在拉班拍中的所占的权重。 1 2 2 索引结构 索引结构是现代信息检索中的重要课题，索引结构建立的目的是把运动捕捉数据库 中的数据映射到某种数据结构上，使得检索的复杂度低于d ( 刀) 。一个好的索引结构可以 大大加快系统的检索速度。 台湾清华大学的邱志义等人引入一种仿射不变的姿态特征，并在此基础上提出了基 于原始数据姿态分布的索引图结构【l o 】。他们引入一个对于骨骼间的转换，旋转，和骨骼 的缩放比例不变的特征用来忽略两个相似人体运动轨迹的绝对位置，方向，和骨骼的大 小，从而使得检索变得高效。他们对一段人体动作序列提取一个骨骼变换仿射不变的姿 态向量，用来表示在一个动作帧中的所有骨骼。然后将这个姿态分解成几个主要骨骼片 段对的应分割姿态。最后，对于每个骨骼片段都会有一个根据相应分割姿势的分布，通 过自组织网络聚类构成索引图。索引图的拓扑性质使得相似姿态的查找和检索效率得以 提高。 人体运动捕捉数据的榆索 浙江大学的向坚等人【】【1 2 】【1 3 】通过从物体运动中提取一种基于3 维空间变换特征规 律的空间变换特征和运动的一些关键的时间特性来得到人体运动的3 维时序特征。他们 基于原始数据中的4 8 维数据，定义了f f l ，h 等空间划分规则，得到了关节点之间的上 下左右的空间关系，即3 维空间变换特征。之后利用空间变换特征速度来提取空间速度 相似度，这是度量两个运动快慢的决定性因素，这也是最常用的时间特性。进行变换时， 首先通过时间特性和空间变换特征的结合来得到人体运动完整的3 维时序特征，然后分 别处理每一个关节点的局部时序特征，并利用决策树学习各关节点的相似程度来计算其 对整体相似的影响，这就在检索过程中避免了很大部分无意义的相似度计算，实现一 个高效的运动检索仿真系统。 1 3 本文主要内容与组织结构 从人机接口的角度来说，基于内容的运动检索系统可以提供以下两种方式对运动捕 捉数据库进行检索： ( 1 ) 基于语义描述的检索：用户采用一段文字来描述需要检索的运动，系统根据文 字描述从数据库中检索出与待检索运动在语义上最为相关的运动。 ( 2 ) 基于运动样本的检索：用户可以采用一段的运动捕捉片段来描述有待检索的运 动，也可以通过用户界面上设置的摆动小人模型调节出若干运动姿态作为关键帧，系统 可以对这些关键帧进行插值，或直接利用这些关键帧构成待检索的运动片段。系统根据 待检索的运动片段本身所包含的数值信息，从数据库中检索出数值上最为相近的运动序 列。 从检索系统设计的角度来说，逐个比较的方法可以保证数据库被完整遍历，因此得 到的结果准确。但是只适用于数据库容量相对小的检索，对于数据库容量大、时间要求 苛刻的检索并不适用。另种方法是事先对运动捕捉数据库建立一个索引，检索时直接 通过索引找到所需的运动，不必遍历整个数据库，从而大大地降低了时间的复杂度。 在基于语义描述的检索方面，为了能够支持局部匹配，并从较为高级的语义层面对 动作进行特征提取，本文采用一种有监督的标注方法条件随机场( c o n d i t i o n a l r a n d o mf i e l d s ，简称c r f ) ，对运动捕捉序列进行语义标注。条件随机场包括两个过程： 训练过程和标记过程。在训练过程中，仅需做出高层语义的标注，如“走”、“跑”、 “跳 等。训练时，用k 一均值方法从训练样本中提取特征，并用提取出的特征构建c r f 中的特征函数。经过训练的c r f 可用来标注未知序列，从而得到该序列的高层语义特征， 有利于进一步的索引建立。采用c m ug r a p h i c sl a b 发布的m o t i o nc a p t u r ed a t a b a s e 进行 大连理工大学硕士学位论文 实验，试验结果表明，在选取了合适的训练集合及参数的情况下，本方法可以正确和全 面地在未知长序列中标记出训练集合中所含有的语义特征。 基于运动样本的检索方面，本文提出了一种通过维度熵的降序排列构造的符号图模 型。首先通过类似拉班舞谱的空间分割法将m 维时间序列数据转化为k 维的符号序列。 然后将维度按照信息熵进行降序排列并构建层次结构的符号状态转换图。则检索问题转 化为求符号图上一条路径所经过的各个节点所代表集合的交集。最后，应用c m u g r a p h i c sl a b 发布的m o t i o nc a p t u r ed a t a b a s e 动作数据库进行实验，结果表明符号图模型 是一种有效的索引方法。 人体运动捕捉数据的检索 2 相关理论基础 2 1 序列标注模型 序列标注问题是指：给定某观察序列o = a 0 2 q 及一个表示观察序列的某种隐含 的特性的有限标记集合s = 墨 ，求出与q 对应的由s 构成的最佳标记序列s 。在计算 语言学与生物信息学等领域，序列标注都有重要的应用。例如，自然语言处理过程中的 词性标注、命名实体识别；在生物信息学领域有线性序列分析、模型分析、基因发现等 方面的应用。 解决序列标注问题的主要方法有隐马尔可夫模型、最大熵马尔可夫模型与条件随机 场模型。 2 1 1 隐马尔可夫模型 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，h m m ) 1 1 4 作为种统计分析模型，创立 于2 0 世纪7 0 年代。8 0 年代得到了传播和发展，成为信号处理的一个重要方向，现已成 功地应用于语音识别，行为识别，文字识别以及故障诊断等领域。 隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向 量序列，观察到每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测 向量是由一个具有相应概率密度分布的状态序列产生的。所以隐马尔可夫模型是个双 重随机过程具有一定状态数的隐马尔可夫链和显式随机函数集。 隐马尔可夫模型可以用五个元素来描述： 1 ，模型的隐含状态数目，即集合s 的规模。虽然这些状态是隐含的，但在许 多实际应用中，模型的状态通常有具体的物理意义。 2 m ，每个状态有可能对应的不相同的观测值的数目。 3 么，状态转移概率矩阵。描述了h m m 模型中各个状态之间的转移概率。其中 4 = 尸( q + l = s j lq t = 墨) ，1 f ，j n( 2 1 ) 式( 2 1 ) 表示在，时刻，状态为s 的条件下，在f + l 时刻状态是s ，的概率。对于所有 状态都在一步之内可达的情况下有a 。 0 ，在其余的情况下可以允许有一个或多个为 零。 4 刀，与隐含状态，对应的观测信号的概率矩阵。 召，( 后) = p 圪( ，) i 毋= s j 】l n ，l k m ( 2 2 ) 式( 2 2 ) 表示在，时刻、状态是s ，条件下，观察符号为圪( ，) 的概率。 大连理工大学硕士学位论文 5 刀，概率矩阵，表示状态的初始分布。 万= 刀， 刀f = p 级= s ，】ls n ( 2 3 ) 式( 2 3 ) 表示在初始时刻( ，= 1 ) ，状态为s ，的概率。 般的，可以用五= ( 彳，b ，7 r ) 来简洁地表示一个隐马尔可夫模型。给定了，膨， 彳，b ，7 后，隐马尔可夫模型可以产生一个观测序列o = q 0 2 0 ，其过程如下： 1 根据状态的初始分布石选择一个初始状态仍= 墨； 2 设置f = l ； 3 根据状态s 的概率分布情况，即匆( j i ) 选择观察信号q = 圪； 4 根据状态s 的状态转移分布矩阵彳，转换到一个新的状态g 川= s 5 设置t = ，+ l ，如果t t 则转步骤3 ，否则结束。 以上过程既适用于根据状态转移矩阵产生观察信号的过程，又适用于通过已知观察 信号推断其所对应的隐含状态的过程。由于h m m 的过程是从模型得到观察信号，因此 也被称为“产生式 模型。 在h m m 的应用领域中，有三个基本问题： 1 评估问题：给定观测序列0 = q d 2 p 和模型参数元= ( a ，b ，万) ，怎样有效计算 某一观测序列发生的概率。 从另外个焦度来考虑这个评估问题，它不仅仅可以在给定模型和观察信号的情况 下求出某个观察信号发生的概率，而且可以被用于评估所选择的模型与实际上观测到的 信号之间的符合程度，这也是用来评判模型选择的优劣的一种重要的标准。 2 推断问题：给定观测序列0 = q 0 2 0 ，和模型参数名= ( a ，b ，j r ) ，如何寻找到一 个状态序列g = 吼g ：鳃使其成为某种意义上最优的对于观测序列 0 = 0 1 0 2 d 在本质上的解释。 推断问题试图去发现模型的隐含部分，试图去寻找“正确的的状态序列。然而， 对于退化模型而言，不存在所谓“正确 的状态序列。因此对于实际应用而言，总是在 某种优化条件下去求解一个最优的值。从推断问题的定义可以看出，对推断问题的求解 即是对序列标注问题的最终目标。 3 学习问题：怎样调整模型参数彳= ( 么，b ，万) 使得p ( o 旯) 最大。 学习问题在给定个观察序列集合的情况下调整模型参数，使得e ( oi 旯) 最大。给 定的这个观察序列的集合称为“训练集合”。训练问题对于大多数的h m m 应用而言都 人体运动捕捉数据的榆索 是最关键的一部分。因为无论对于评估问题还是推断问题，都需要在某一给定模型的基 础上进行，对于大多数的实际应用而言，模型都是由“训练集合 得来的。 针对以上三个问题，人们分别提出了相应的算法。 对于评估问题，在给定模型参数名的情况下，希望求得某一观察信号0 = q 0 2 0 ， 发生的概率，也就是p ( oi 五) 。最直接的解决这个问题的方法是列举所有可能出现的长 度为丁的观察序列进行求解。考虑如下状态序列： q = q l q 2 q r ( 2 4 ) 其中纺表示初始状态，则式( 2 4 ) 中状态序列对应的观察信号d 的概率为： r p ( o i q ，五) = 1 - i p ( qlg r ，五) ( 2 5 ) t = l 基于观察信号的独立性假设，可以得n - p ( o iq ，力) = 气( q ) b q 2 ( q ) ( q ) ( 2 6 ) 此时状态序列q 的概率为： p ( qi 五) = ，口吼9 2 口级秭钉 ( 2 7 ) 则状态序列q 和观察信号d 同时发生的概率，也就是二者的联合概率为： p ( d ，q l 五) = p ( o l q ，五) 尸( q ，名) ( 2 8 ) 则观察序列( ) 的概率可以通过所有可能出现的状态序列所对应的概率之和求出。 p ( oi 五) = p ( oiq ，2 ) p ( q ，z ) ( 2 9 ) ( 2 1 0 ) 在初始时刻t = l 时，以死的概率出现状态吼并以6 ( d i ) 的概率产生观察信号q 。当 时钟从，= l 变为，= 2 时，状态9 。到q ：存在转移概率：勃并以6 ( q ) 的概率产生观察信号 0 2 。这种迭代过程一直持续到状态q r 一，与状态如之间以概家，一钉进行迁移并以6 ( q ) 的 概率产生观察信号q 。 从以上的计算过程中可以看出，计算p ( o | 五) 需要进彳子2 丁r 次运算。因为对于每 个t = 1 ，2 ，t ，都有个可能到达的状态，对于每个状态序列而言都需要2 丁次运算来 计算式( 2 1 0 ) 中的和。更精确地说，计算p ( oi 力) 需要( 2 t 一1 ) n r 次乘法和r 1 次加法。 显然，这种计算复杂度是不可行的，即使对于较小的和丁，例如n = 5 ，t = 1 0 0 的情 大连理工大学硕士学位论文 况，都将要产生2 1 0 0 5 瑚1 0 7 2 的运算量。因此，需要更加高效的方法来解决这个问题。 幸运的是，存在一种叫做“前向后向的方法，可以较为高效地解决评估问题。 首先考虑前向变量q ( j ) ，定义为： ( f ) = p ( q 0 2 d ，吼= si 力)( 2 1 1 ) 也就是在给定五的情况下，时刻t 的状态s 与部分观察序列q q 织之间的联合概 率，这个概率可以采用迭代的方法进行求解： ( 1 ) 初始化：呸( f ) = 乃勿( d 1 ) l f n 厂n ( 2 ) 迭代：q + ，( ) = i 哆( f ) 口 i 乞( 0 ，+ ，) ，l ， p ( ol 彳) 则模型旯的似然程度比模型五要高，即模型彳比模型五更 有可能是产生相应观察序列的模型。 根据以上的结论，可以采用五和彳不断进行互换的迭代，不断重复地进行重估的计 算，直到达到某种临界点为止。这样不断重新估计模型的过程叫做h m m 的极大似然估 计。需要指出的是，前向后向方法将导致局部最优的结果，且对于某些复杂的问题，将 产生多个局部最优值。 式( 2 2 5 ) 中的估计公式，可以通过对b a u m 的辅助方程的最大化过程求得： q ( 名，_ ) = p ( oq ，2 ) l o g p ( o ，qi 动】 ( 2 2 6 ) 口 b a u m 等人证明，对q ( 彳，名) 的最大化将导致似然程度的增加，即： m a x e q ( 2 ，名) 】= p ( oi 见) p ( ol 五) ( 2 2 7 ) 最终，似然方程收敛于某一临界点。 在估计过程中，需要注意的是，h m m 中的各个参数需要在任意一次迭代中满足统 计学的约束规律： n 万，：l a g = 1 ，1 f j = l b j ( k ) = l ，1 j n ( 2 2 8 ) ( 2 2 9 ) ( 2 3 0 ) 如果用图来描述h m m 模型中状态与状态、状态与观察信号之间的关系，h m m 模 型可以称之为一种“有向图 模型。设有向无环图g = ( v ，e ) ，使其顶点k 与某种随机 变量一一对应，其边毛则表示两个随机变量之间的条件依赖关系，如图2 3 所示。其中， s 表示第z 时刻的状态值，表示第i 时刻的观察信号值。特别地，状态在时刻j 的概率 仅依赖于i l 时刻的状态。类似地，时刻i 的观察信号仅依赖于时刻，的状态。 大连理工大学硕士学位论文 & 1 s ， h x lx 2kl 图2 3 隐马尔可夫模型的有向图表示 f i g 2 3d i r e c t e dg r a p hi l l u s t r a t i o no f h i d d e nm a r k o vm o d e l 虽然h m m 有着广泛的应用，但对于序列标注的问题，却并不是最好的解决方案。 、删在状态和观察信号之间定义了联合概率分布p ( x ，s ) ，这对于通过模型产生观察信 号的“产生式”过程适用，而序列标注问题所关注的概率分布是在给定观察信号时，观 察信号与状态之间的条件概率p ( six ) 。h m m 的这种计算观察信号与状态之间的联合概 率p ( x ，y ) 的方法需要枚举所有可能产生的观察信号来进行计算。当观察信号有长距离的 依赖关系时，此种计算非常困难。因此，产生式模型必须对观察信号做严格的独立性假 设。在h m m 中，时刻，的观察信号只能依赖时刻t 的状态，并保证序列中所有观察信号 是相互独立的。 然而现实中的信号并不能保证完全互相独立。幸运的是，条件模型为序列标注问题 提供了更好的解决方案，从而避免产生式模型中过强的独立性假设。条件模型真接计算 序列标注问题所关注的观察信号与状态之间的条件概率p ( s i x ) ，而不是通过式( 2 3 1 ) 来 列举所有观察信号本身的概率与状态和观察信号之的联合概率分布p ( x ，s ) 求得。 s a r gm a x 。p ( siz ) = 鹕m 晖丛掣( 2 3 1 ) p t x ) 2 1 2 最大熵马尔可夫模型 最大熵马尔可夫方法( m a x i m u me n t r o p ym a r k o vm o d e l ，m e m m ) i s 】不需要隐马 尔可夫模型中的强独立性假设，是一种适用于序列标注阀题的模型，已被成功地应用于 词性标注与文本分段问题。 s ls 2s 3 s 1 s ，f 寸h 舌舌占舌占 x l 趋x 3k lx ，t 图2 4 最大熵马尔可夫方法的有向图表示 f i g 2 3d i r e c t e dg r a p hi l l u s t r a t i o no fm a x i m u me n t r o p ym a r k o vm o d e l 人体运动捕捉数据的检索 虽然h m m ，m e m m 都是以概率自动机为基础的模型，但是与h m m 不同的是， m e m m 将观察信号看作是状态所依赖的条件，而不是由状态产生的结果。然而，在这 种模型中，m e m m 并不分别定义状态s 与j 之间的转移概率p ( s l j ) 和观察信号与状态 之间的条件概率p ( s i z ) 这两种不同的分布，而是在集合s 上定义一种统一的概率分布： 一l 砂= p ( s 。h x ) ( 2 3 2 ) 式( 2 3 2 ) 表示在给定观察信号z 的情况下，从状态s 转移到状态s 的概率。用有向图 来表示m e m m 中的条件依赖关系，如图2 4 所示。时刻f + 1 的状态仍然仅依赖于时刻， 的状态，不同的是观察信号z 成为了状态s 所依赖的条件，而不是产生的结果。因此， 则m e m m 的分布规律可以采用随机变量s 的联合分布来表达，将状态s 与某种特别的 标记y 相对应，得到： p ( y f 功= p ( 乃i 而il p ( 只1 只一。，薯) ) ( 2 3 3 ) 将观察信号处理为状态所依赖的条件意味着观察信号x 不必如h m m 中所要求的那 样遵循严格的独立性假设。m c c a l l u m 等人采用了最大熵框架进行求解【1 5 】，他们将每个 状态与观察信号之间的转移方程定义为一种对数线性模型： 聃i 功。赤e x p ( 莩姒o ”( 2 3 4 ) 其中z ( s ，功是归一化因子，五是待估计的参数，六表示特征方程。参数五可以采 用估计方法求解。特征方程以对观察信号采用二值化特征进行描述，例如： 撇，= 艺幺纛办一 亿3 5 ， 特征方程兀返回一个布尔值，表示特征b 是否在训练集合中出现。 k = 乜幺黧岁批删肛j 2 1 3 标记偏置问题 结合实际应用中的一个例予来阐明标记偏置( l a b e lb i a sp r o b l e m ) i h - 题【1 6 】，该例子基 于基于最大熵马尔科夫模型的组块。图2 5 是一个有用于识别两个经过分词后的语句中 组块的有限状态接收机： 今年下了三场雪。 今年一共有三场雪 大连理工大学硕士学位论文 分别用b e g i n 和e n d 表示起始状态和终止状态，用b 和i 表示组块边界标记，用 n p 、v p 和m p 代表类型标记。如图2 5 所示，语句和的正确标记结果分别是 状态序列0 一l 2 4 _ 6 _ - 7 和0 一l 3 5 十7 。但是，由于状态2 4 的转移和状态 3 5 的转移都是惟一的，而且最大熵马尔科夫模型要求对每一个状态进行归一化，导致 状态l 转移到状态2 和状态3 的概率值会全部被转移到状态4 和状态5 。在这些状态转 移的过程中，输出序列对于概率值的转移没有起到任何影响，即语句和都会被 标记成一种形式的组块序列结果。标记结果仅仅由状态2 和状态3 从状态l 获得的转移 概率决定，而与输出序列无关。因此，标记偏置问题严重地影响了最大熵马尔科夫模型 的序列标记准确度。 i m pb - v p 图2 5 标记偏置问题状态图 f i g 2 5t h e s t a t eg r a p ho fl a b e lb i a sp r o b l e m 2 1 4 条件随机场模型 条件随机场( c o n d i t i o n a lr a n d o mf i e l d s ，c r f ) 是一种新的解决序列标注问题的有 监督的统计学方法。c r f 采用无向图模型来表示随机变量之间的关系，且从全局角度给 出观察信号和状态之间的条件概率关系，和以往的隐马尔可夫方法和最大熵马尔w 夫方 法相比，c r f 既不需建立在随机变量严格独立的假设之上，又不会产生标注偏差问题， 是一种较好的解决序列标注问题的方法。 与m e m m 相同，c r f 也属于条件概率模型，但不同的是，c r f 并不采用有向图来 描述模型中随机变量的依赖关系，而是采用无向图来表达随机变量之间的联合概率分 布。这使得在给定观察信号的情况下，可以给出整个状态序列上的单一联合概率分布， 而不是在给定当前状态的情况下去定义下一个状态概率分布。由于具有这种基于整个状 态序列的条件分布的特性，c r f 可以针对现实应用中的各种具体问题建立非独立的、互 动的特征方程来描述不同领域的观察序列。 人体运动捕捉数据的检索 定义一个无向且无环的图g ：( 矿，互) ，来辅助说明c r f 。 设y = ( y ，) 1 ，v ，那么随机变量y 便可以用g 中的点，来索引。当y v 条件依赖于 x 时，如果随机变量y ，在图g 上满足m a r k o v 性，那么二维随机变量( x ，y ) 便称为一个 条件随机场，其中的m a r k o v 性是指： p ( yl x ，y 0 ，w v ) = p ( y ，i x ，y w ，w v ) ，其中w ，表示点w 和点v 相邻。也就是说 在给定x 的前提下，图g 中只有和1 ，相邻的点才能决定y ，的概率。 根据随机场的基本理论，可以得到： p ( yx ) 5 夏1 酉e x p ( 萎莩丸 ( c ，y f ，x ) ) ，c c ( 2 3 7 ) 其中，z ( x ) 为归一化因子，z ( x ) = e x p ( y ，丸五( c ，y ，x ) ) ，c c ，c 是g 中所 x yc e ck 有最大团( m a x i m u mc l i q u e ，极大完全子图) 的集合，五是定义在c 上的特征函数，则 ( 2 3 7 ) 中的参数元可由极大似然估计方法求得： 三( o ) = 芦( k , y ) 1 0 9 p ( yx ， ) ( 2 ，3 8 ) 其中声( x ，y ) 表示训练数据中p ( x ，y ) 的经验分布。确定了参数元的c r