（应用数学专业论文）有监督的流形学习及其在人体行为识别中的应用.pdf

有监督的流形学习及其在人体行为识别中的应用 专业：应用数学 姓名：马锦华 指导老师；阮邦志教授赖剑煌教授 摘要 人体行为识别是计算机视觉与模式识别中的研究热点之一。它在智能视频监 控、感知接口和虚拟现实等领域中均有着广泛的应用前景。在入体行为识别中， 一般用一段视频或者一系列图像来记录人体行为，故待处理的数据往往具有较高 的维数。然而，高维数据不但难以被人们直观理解，而且在识别阶段会导致过高 的计算复杂度。所以，研究人体行为数据的低维表达，是一项必要且紧追的工作。 经典的线性降维方法，譬如p c a 等，能够有效地对数据进季亍压缩，然藤人体 行为数据具有高度的非线性特征，所以经典的线性降维方法不适用于对人体行为 数据进行降维。为此，我们需要寻求有效的非线性降维方法来处理人体行为数据。 经过研究发现，非线性的流形学习技术能很好地保持数据的非线性性质。然丽， 经典的非线性流形学习算法也不能直接应用于人体行为识别中，其原因有三个方 面：第一，在高维空间中，代表不同动作的两个流形可能相交，所以入体行为数 据的整体，并不满足光滑流形的性质；第二，经典算法没有利用类别信息；第三， 经典算法不能有效地处理样本集外的数据。 基于以上分析，本文针对行为数据的特点，利用数据的类别信息，提出了三 秸有监督的流形学习方法：兰) 从局部保持映射的框架出发，提出了优化的有监 督局部保持映射算法；2 ) 受多维标度分析的启发，从流形的整体性质出发，重 构流形平移后的距离结构，提出了有监督等距投影算法；3 ) 针对流形之间的度 量方法，利用线性判别分析( l d a ) 的思想，提邂了基予流形的判别分析。 实验结果表明，本文提如的算法应用予在人体行为识别中，优子经典的流形 学习算法；而在本文提出的算法中，综合变现最好的算法是优化的有监督局部保 持映射。 关键词：流形学习，人体行为识别，有监督学习，降维算法 s u p e r v i s e dm a n i f o l dl e a r n i n ga n di t sa p p l i c a t i o ni n h u m a na c t i o nr e c o g n i t i o n m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：j i n h u am a s u p e r v i s o r ：p o n g c h iy u e n ，j i a n h u a n gl a i a b s t r a c t h u m a na c t i o nr e c o g n i t i o ni sa na c t i v er e s e a r c ht o p i ci nc o m p u t e rv i s i o na n d p a t t e r nr e c o g n i t i o n i th a saw i d er a n g eo fp o t e n t i a la p p l i c a t i o n s ，s u c ha si n t e l l i g e n t v i s u a l s u r v e i l l a n c e ，p e r c e p t u a li n t e r f a c e ，v i r t u a lr e a l i t y , e t c i nh u m a na c t i o n r e c o g n i t i o n ，s i n c ea c t i o nd a t ai ss t o r e da ss e q u e n c e so fi m a g e si nc o m p u t e r , t h e d i m e n s i o n a l i t yo ft h ei m a g ed a t ai sv e r yh i 曲h i g hd i m e n s i o n a ld a t ai sh a r dt o u n d e r s t a n df o rh u m a nb e i n g m o r e o v e ru s i n g h i g hd i m e n s i o n a ld a t ai nt h e c l a s s i f i c a t i o ns t a g ew o u l dm a k et h ec o m p u t a t i o n a lc o m p l e x i t yi n c r e a s e s ol e a r n i n g t h el o wd i m e n s i o n a lr e p r e s e n t a t i o n sf o rh u m a na c t i o n si sn e c e s s a r y l i n e a rd i m e n s i o n a l i t yr e d u c t i o n ，f o re x a m p l ep c a ，i sa ne f f e c t i v et e c h n i q u ef o r d a t ac o m p r e s s i o n h o w e v e r , d u et ot h en o n l i n e a rv a r i a t i o ni nh u m a na c t i o n s ， t r a d i t i o n a ll i n e a r d i m e n s i o n a l i t y r e d u c t i o nm e t h o d s a r en o t a p p l i c a b l e t o d i m e n s i o n a l i t yr e d u c t i o nf o rh u m a na c t i o nr e c o g n i t i o n s ow en e e dt of i n ds o m e n o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u e st oe x t r a c tf e a t u r e sf r o mt h ea c t i o nd a t a m a n i f o l dl e a m i n gi san o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u ed e v e l o p e d r e c e n t l y i tc a nw e l lp r e s e r v et h en o n l i n e a r i t i e so ft h em a n i f o l d s oi nt h i sp a p e r , w e u s em a n i f o l dl e a r n i n gf o rh u m a na c t i o n r e c o g n i t i o n h o w e v e r , t h et r a d i t i o n a l m a n i f o l dl e a r n i n ga l g o r i t h m ss u c ha si s o m a p ，l l e ，l e ，e t c a r ei n a p p l i c a b l ei nh u m a n a c t i o nr e c o g n i t i o n t h e r ea r et h r e er e a s o n sw h yw em a k et h i sc o n c l u s i o n f i r s t ，t w o m a n i f o l d sr e p r e s e n t i n gd i f f e r e n ta c t i o n sm a yi n t e r s e c ti nt h eh i g hd i m e n s i o n a l e u c l i d e a ns p a c es ot h a tt h ed a t as e ti n c l u d i n ga l la c t i o n sd o e sn o ts a t i s f yt h em a n i f o l d 1 1 1 p r o p e r t i e s s e c o n d ，t h e s ea l g o r i t h m sa r eu n s u p e r v i s e d ，w h i c hm e a n st h a tt h e yh a v e n o tt a k e nf u l la d v a n t a g eo ft h ec l a s si n f o r m a t i o ni na c t i o nr e c o g n i t i o n i na d d i t i o n ， t h e s ea l g o r i t h m sc a n n o tb ee x t e n d e dt ot h eo u t - o f - s a m p l e sd a t ae f f e c t i v e l yi nt h e r e c o g n i t i o ns t a g e b a s e do nt h e s ec o n s i d e r a t i o n s ，i nt h i sp a p e r , w ep r o p o s e dt h r e es u p e r v i s e d m a n i f o l dl e a r n i n ga l g o r i t h m sf o rh u m a na c t i o nr e c o g n i t i o n ：( 1 ) b a s e do nt h e f r a m e w o r ko fl p p , t a k i n ga d v a n t a g eo ft h ec l a s si n f o r m a t i o n ，w ep r o p o s e da n i m p r o v e dv e r s i o no fs u p e r v i s e dl p p ；( 2 ) c o n s i d e r i n gh o w t or e c o n s t r u c tt h ed i s t a n c e c o n f i g u r a t i o no ft h em a n i f o l d sa f t e rt r a n s l a t i o n s ，i n s p i r e db ym d s ，w ep r o p o s e d s u p e r v i s e di s o m e t r i cp r o j e c t i o n ；( 3 ) c o n c e r n i n gt h em e t r i cb e t w e e nm a n i f o l d s ，u s i n g t h ei d e a si nl d a ，w e p r o p o s e dad i s c r i m i n a n ta n a l y s i sa l g o r i t h mb a s e do nm a n i f o l d s i no u re x p e r i m e n t ，w eu s e dt h e s ea l g o r i t h m sp r o p o s e di nt h i sp a p e rt oe x t r a c tf e a t u r e s f r o mt h ea c t i o nd a t a ，t h e nu s i n gt h e mf o ra c t i o nr e c o g n i t i o n e x p e r i m e n t a lr e s u l t si n d i c a t e dt h a to u rp r o p o s e dm e t h o d so u t p e r f o r mo t h e r t r a d i t i o n a la l g o r i t h m sf o rh u m a na c t i o nr e c o g n i t i o n i ng e n e r a lt h eb e s ta l g o r i t h mf o r h u m a na c t i o nr e c o g n i t i o ni ss u p e r v i s e dl p p k e y w o r d s ：m a n i f o l dl e a r n i n g ，h u m a na c t i o nr e c o g n i t i o n ，s u p e r v i s e dl e a r n i n g ， d i m e n s i o n a l i t yr e d u c t i o n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均邑在文中以明确方式标明。本人完全意识到本声骧的法律结果由本人承担。 学位敝储签名群 2 酗7 年6 月f e t 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利弱的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：写锝午 导师签名； 蚓宅乏j 髑期i 钟年6 , e lf e t日期：知，锋参月3 - e t 第1 章引言 1 1 研究背景和意义 第1 章引言 人体行为识别是计算机视觉与模式识别中的研究热点之一。它在智能视频监 控、感知接口和虚拟现实等领域中均有着广泛的应用前景 1 2 。 在自动化的人体行为识别系统中，一个动作一般用一段视频或者一系列图像 来记录。而我们通常把一幅图像看成是高维欧氏空间中的一个向量，例如，一幅 l o o x1 0 0 的图像是1 0 0 0 0 维的欧氏空间中的向量。这样，导致了人体行为数据具 有较高的维数。然而，高维数据不但包含一些与运动无关的信息；而且，高维数 据难以被人们直观理解和利用。所以，对人体行为数据进行降维，从中提取出描 述运动的特征信息很有必要性。 一些经典的线性降维方法，例如主成份分析( p c a ) ，线性判别分析( l d a ) 和独立成分分析( i c a ) 等1 3 ，都是从高维数据中提取特征的有效方法。然而， 人体的运动是人体的非线性形变过程，所以人体行为数据具有高度的非线性性， 经典的线性降维方法并不适用。 流形学习是近年来兴起的一种非线性降维技术。它在降维的过程中能有效地 保持流形的非线性性质。而人体的动作序列可以看成是高维欧氏空间中某个连续 流形的离散化。所以，在降维过程中，要保持人体运动的非线性变化特征，就是 要保持流形的非线性性质。因此，本文将从流形的角度出发，研究人体行为数据 的低维流形，从而在原始人体行为数据中提取出本质的运动特征，实现对数据的 降维。 研究人体动作序列的低维表达，有以下几个方面的好处： 1 ) 综合利用运动信息 人体行为的运动信息主要由两个方面组成：空间信息和时间信息。空问信息 指的是人体行为中每个姿势的形状信息；时间信息指的是一个动作中相继两个姿 势的变化特点。而研究人体行为的动态流形，一方面能提取出最有用的空间形状 信息，另外一方面能使时间信息完全保留。这样，无论是人体的全局或局部的运 动信息都得到了有效的利用。 中山大学硕士学位论文：有监督的流形学习及其在人体行为识别中的应用 2 ) 降低行为数据库的存储空间 人体的动作是多种多样的。而一个动作在计算机上的存储方式是一段视频， 视频中包含若干帧图像( 姿势) 。这样，如果要建立一个完备的人体行为数据库， 则需要十分庞大的存储空间。而研究人体动作序列的低维流形可以大大减少人体 行为数据库的存储空间。 3 ) 提取人体动作的特征 在原始人体行为数据中经常包含一些没用的信息，或噪声。所以，直接利用 原始数据进行识别有可能会使识别率降低。而研究人体动作的低维流形，从原始 的人体动作序列中提取出最有用的运动信息，可以使识别率得到提高。 4 ) 人体动作序列的可视化 人类直观上可以认知的最高维数是3 维。然而，原始的人体行为数据的维数 远大于3 维，所以，我们并能从直观上直接观察出人体动作序列在高维空问中的 分布特点。当知道了人体动作的低维表达( 2 维或3 维) 时，我们可以从直观上认 知人体运动的特点，从而有利于我们进一步探索和理解人体运动的本质特征。 1 2 研究现状 1 2 1 流形学习 流形学习是2 0 0 0 年由t e n e n b a u m 等人s d r o w e i s 等人在s c i e n c e 杂志上相继 发表的两篇论文 4 5 中提出来的。从2 0 0 0 年以后，流形学习理论得到了迅速的 发展。到目前为止，关于这方面的研究有很多 4 - 1 3 ，其中较有代表性的工作 是等距映射( i s o m e t r i cm a p p i n g ，简称i s o m a p ) 4 ，局部线性嵌入( l o c a l l y l i n e a re m b e d d i n g ，简称l l e ) 5 ，拉普拉斯特征映射( l a p l a c i a ne i g e n m a p s ， 简称l e ) 6 和局部切空间排列( l o c a lt a n g e n ts p a c ea 1 i g n m e n t ，简称l t s a ) 7 。这四种方法分别是基于流形的不同性质而提出来的。其中，i s o m a p 是多维 标度分析 1 4 的扩展，它的思想是保持流形中两点间的测地距离。而l l e 和l e 考 虑的都是流形中的领域性质。不同的是l l e 保持的是领域中的线性重构权值；l e 则基于紧致黎曼流形上的l a p l a c e - b e l t r a m i 算子，保持流形中数据点之间的领域 关系。至于l t s a ，它着眼于考虑流形间的切空间。在l t s a 中，我们先构造数据点 的切空间，然后对切空间进行对准，最小化全局重构误差。 2 第1 章引言 以上介绍了一些经典的非线性流形学习算法。然而，对于高维空间中的某些 流形，如果它们的内蕴结构并没有弯曲的度量，则它们可以线性地嵌入到平面或 超平面中。所以，一些线性的降维方法可以归于流形学习的范畴，例如主成份分 析( p r i n c i p l ec o m p o n e n ta n a l y s i s ，简称p c a ) 3 和多维标度分析 ( m u l t i - d i m e n s i o n a ls c a l i n g ，简称m d s ) 1 4 。 从广义上讲，流形学习可以定义为：保持高维流形中某些本质几何性质( 即 不依赖于坐标系选取的性质) 的降维方法。 1 2 1 基于流形学习的人体行为识别 目前，虽然关于流形学习的研究工作有很多 4 卜 1 3 ，但是将这些流形学习 方法应用于人体行为识别中的工作却很少。 关于这方面的研究，最早的是2 0 0 7 年，w a n g 等人在论文 1 5 中提出了利用 局部保持映射( l o c a l i t yp r e s e r v i n gp r o j e c t i o n ，简称l p p ) 1 3 对人体行 为数据进行降维。l p p 是l e 的线性化方法。在论文 1 5 中，作者先用l p p 从人 体行为数据提取特征，得到了动作序列的一个低维表达，然后基于这个低维表达 用均值h a u s d o r f f 距离度量两个序列之问的相似性，并用最近邻分类器进行识 别，得到了很好的识别效果。 随后，在2 0 0 8 年，j i a 等人在论文 1 6 中提出了利用局部时空判别嵌入 ( l o c a ls p a t i o t e m p o r a ld i s c r i m i n a n te m b e d d i n g ，简称l s t d e ) 进行人体行 为识别。l s t d e 也利用了l p p 的思想，将高维空间中相近的同类数据点映射到低 维空间中相近的点，将相近的异类数据点映射到低维空间中远离的点。而且， l s t d e 不仅考虑了动作序列在高维空间中的空间分布性质，而且还考虑了动作序 列的时间分布性质，即把高维空间中相近的异类动作序列的片段，映射到低维空 间中相对远离的片段，而两个小片段之间的距离用流形到流形的距离( m a n i f o l d t om a n i f o l dd i s t a n c e ，简称m m d ) 1 7 度量。然而，在文献 1 6 中报告的实验 结果却比 1 5 中的差。 1 3 本文的主要工作 本文针对人体行为数据的特点，利用数据的类别信息，分别从三个不同的角 度，提出了三种有监督的流形学习方法：1 ) 从局部保持映射的框架出发，提出 3 中山大学硕士学位论文：有监督的流形学习及其在人体行为识别中的应用 了优化的有监督局部保持映射算法；2 ) 受多维标度分析的启发，从流形的整体 性质出发，重构流形平移后的距离结构，提出了有监督的等距投影算法；3 ) 针 对流形之间的度量方法，利用线性判别分析( l d a ) 的思想，提出了基于流形的 判别分析。 实验结果表明，本文提出的有监督的流形学习算法优于经典的流形学习算 法；而在本文提出的算法中，综合变现最好的算法是优化的有监督局部保持映射。 本文共分五章，具体的章节安排如下：第一章是引言，主要介绍了本文的研 究背景与要研究的问题的研究现状；第二章详细地介绍了流形学习中较有代表性 的几种算法p c a 、m d s 、i s o m a p 、l l e 和l e ，并将它们统- - n 相同的框架中； 第三章提出了三种有监督的流形学习方法优化的s - l p p 、有监督的等距投影 和基于流形的判别分析；第四章为实验部分；最后一章是总结与展望。 4 第2 章流形学习的基本理论 第2 章流形学习的基本理论 本章首先给出了流形学习的数学描述，然后介绍了几种较为经典的流形学习 算法一p c a 、m d s 、i s o m a p 、l l e 、l e 、n p e 和l p p 。其中，n p e 和l p p 是l l e 和 l e 的线性化。 2 1 流形学习的数学描述 在介绍各种流形学习算法之前，我们首先给出流形学习的数学定义：假设d 维欧氏空间r d 中有刀个样本而，屯，矗，这刀个样本在r d 中的某个连续流形上， 将该流形记为x = ( _ ，x 2 ，) ：又假设存在尼维欧氏空间瞅( 后 刀。 所以，我们一般不直接求解特征值问题( 2 4 ) ，转而求解特征值问题叉7 瓢= j f z ， 并且令8 ：；x u ，这样就得到了( 2 - 4 ) 的解。 p 归纳一下，p c a 算法由以下几个步骤组成： 1 ) 构造中心化的数据矩阵叉 叉叱喝护嬲) ，m = 去喜而 2 ) 计算散度矩阵s 并求解特征值问题。 a 、若d ，7 ，则令s ：叉戈7 ，然后求解特征值问题( 2 3 ) ，得到单位化特 征向量色。 b 、若d 阿，则令s ：叉7 牙，然后求解特征值问题戈7 蔬：元z f ，令 岛2 去魏， 3 ) 得到投影矩阵尸和低维嵌入l ，：将特征向量按特征值大小的逆序排列， 即五乃磊，令p = ( q ，乞，) ，y = p 7x 。 _ 4 ) 得到样本集外的数据x 的低维嵌入y ：y = p r 一班) 。 2 2 2 多维标度分析( m d s ) 多维标度分析( m u l t i - d i m e n s i o n a ls c a l i n g ，简称m d s ) 1 4 是多元统计 分析中另外一种经典的降维方法。在m d s 中，假设给出以个数据点之间的不相似 度矩阵为d ，我们要在低维空间中找出一组点，使这组数据点之间的距离结构， 7 中山大学硕士学位论文：有监督的流形学习及其在人体行为识别中的应用 最佳地拟合给定的不相似度矩阵d 。下面，我们着重讨论经典的m d s 。 在经典m d s 中，两个点之间的不相似度用这两点之间的欧氏距离来度量。这 样，经典m d s 可以看作是最好地保持高维流形中数据点之间的欧氏距离的流形学 习方法。我们知道，在经典m d s 中，d ：f ，= 恃一一1 1 2 = 妒薯一2 _ r x , + x j r _ 。令 伊= ( 五7 ，吒r 矗) r ，i = ( 1 ，1 ) r ， 则d 可以写成这样的形式， d ：矿一2 x r 彳+ 动r 。又令何：i 一_ r n ，则 一h d h l 2 = x 1x(2-5) 若令b = 一h d h l 2 ，则b 是半正定实对称矩阵。所以，b 可以分解成这样的形式， b = u a u7 ，其中u r u = i ，人是对角矩阵，且人的对角元素对应着b 的非0 特 征值且这些特征值由大到小排序。假设z = 人眦u7 ，则叉7 孑= z 7 z ，且 怯一乃2 = 岛。若取z 的前后列组成的矩阵中的第f 行作为一在酞中的逼近，即 令乃= ( z ，l ，乙) ，这样就得到了经典m d s 的解】，。而这个解在保持距离的意义 下是最优的，详细的证明可以参考文献 1 4 第1 4 章的定理1 4 4 1 。 另外，对于一般的不相似度矩阵d ，m d s 的求解过程与经典m d s 的求解过程 是一样的，其最优性证明可以参考文献 1 4 中的定理1 4 4 2 。 总结起来，m d s 由以下几个步骤构成： 1 ) 计算中心化内积矩阵b b = 一h d h | 2 其中，h ：= ，一j f i 7 n ) d 为不相似度矩阵 2 ) 求解特征值问题 b e = 2 e 3 ) 得到低维嵌入】，：将2 ) 中求得到特征向量按特征值大小的逆序排列， 即五枷乃，令】，= ( 厮，忍，风) r 。 2 2 3p c a 与经典m d s 之间的对偶关系 从2 2 1 和2 2 2 中，我们看到：p c a 与m d s 是互为对偶问题，即它们分别 8 第2 章流形学习的基本理论 对应矩阵趸又7 和叉7 趸的特征向量，且p c a 的投影矩阵p 与m d s 的低维嵌入】，有 这样的关系，y = p r x ，即x i 中心化后的样本数据矩阵x 在p c a 的投影矩阵p 上 的投影正好是m d s 的解】，。所以，如果我们只是想得到样本数据的低维嵌入，那 么p c a 与经典m d s 是一样的，这两种方法都可以使用；而如果我们还要对样本集 外的数据进行降维，则我们只能使用p c a ：然而，当数据点之间的不相似度不是 用数据点之间的欧氏距离度量时，则p c a 无法使用，只能使用m d s 。 2 3 非线性流形学习 在上一节中我们介绍了两种经典的线性流形学习算法。然而，当数据分布在 高度弯曲的流形上时，经典的线性降维方法并不能得到高维数据的一个很合理的 低维嵌入。这样，引起了人们对非线性流形学习的研究。本节将介绍其中的几个 较有代表性的非线性流形学习算法i s o m a p 、l l e 和l e ，和l l e 和l e 的线性 化n p e 和l p p 。 2 3 1 等距映射( is o m a p ) 等距映射( i s o m e t r i cf e a t u r em a p p i n g ，简称i s o m a p ) 4 是2 0 0 0 年由 t e n e n b a u m 等人提出来的。它是m d s 的泛化，是非线性流形学习中具有突破性发展 意义的算法之一。目前，i s o m a p 已成功地应用于生物医学数据的可视化和头部姿 势的估计。 在经典m d s 中，两个数据点之间的相似性用两个数据点之间的欧氏距离表示。 然而，对于弯曲的流形，欧氏距离不足以刻画流形中任意两点问的位置关系。例 如，从图2 一l ( a ) 中，我们可以看出，流形中欧氏距离相对较近的两点在流形上 的测地距离却比较远。 基于这样的考虑，t e n e n b a u m 等人在m d s 的框架中，革命性地引入了流形中两 点闻的测地距离( 即不考虑外蕴空间，只考虑流形本身的连接流形上两点问的最 短路径) 代替欧式距离作为度量两个数据点之间的相似性。这就是所谓的i s o m a p 。 而构造测地距离的算法分两步： 1 ) 建立流形的领域关系图g ：首先，对任意的x i 找出它的领域。一般有两 种方法： 9 中山大学硕士学位论文：有监督的流形学习及其在人体行为识别中的应用 占领域法：如果忙一一i 占，则认为_ 属于薯的领域( 薯) 。 k 近邻法：找出与誓距离最小的前k 个点作为x j 的领域( _ ) 。 在s 领域法中，一般较难取得一个合适的s ，所以本文将用誓的k 近邻法作 为而的领域( 一) 。在确定了领域之后，若薯n ( x j ) ，或0 ( 一) ，则薯和在 g 中连上一条权值为忙一t0 的边。 2 ) 在图g 中用d i j k s t r a 算法求出任意两点间的最短路径( 测地距离) 。 这样，我们就得到了任意两点间的近似测地距离吒。然后在m d s 的框架中， 令岛= 乃2 ，就得到了i s o m a p 的低维嵌入。例如，用i s o m a p 对图2 - 1 ( a ) 中的 “瑞士卷 流形进行降维，得到它的2 维嵌入，如图2 - 1 ( b ) 。从图2 - 1 ( b ) 中 可以看出，i s o m a p 相当于把高维空间中卷曲的流形在低维空间中展开。 ( a ) “瑞士卷( b ) “瑞士卷 的二维嵌入 图2 1 “瑞士卷”及其2 维嵌入【4 】 2 3 2 局部线性嵌入( l l e ) 局部线性嵌入( l o c a l l yl i n e a re m b e d d i n g ，简称l l e ) 5 1 1 是另一个 具有突破性意义的非线性流形学习方法。在l l e 中，假设流形具有局部线性结构， 即对于流形中任意一点t ，都可以用它的领域中的点线性表出。用数学的语言描 述，就是对任意一点毛，都存在权值坞，使薯_ ，且鸭。l ， l m l = 0 ，如果0 仨( 再) ，如图2 - 2 所示。 l o 第2 章流形学习的基本理论 图2 - 2 流形的局部线性【1 1 】 l l e 的目的是保持流形的局部线性结构，即令降维后的数据保留原始流形中的局 部线性重构权值m u 尽可能不变。具体地说，l l e 由三步构成： 1 ) 建立领域关系图g ：若再( t ) 或0 e n ( x j ) ，则和_ 在g 中连上一 条边。 2 ) 计算重构权值坞：求解以下的最优化问题： 叫卜藐，叫1 26 ， 其中，坞满足坞= l ，且觏与之间没有边，鸭= o 3 ) 寻找最佳的构造点只：求解以下问题： 噘碎一手埘 7 ， 在步骤2 中，因为对不同的天歹，蛾和呜是相互独立的。所以，我们只 要对每一个而求解最优化问题( 2 - 8 ) 。 m m i n i x , - 刊1 2 “= l ， ( 2 8 ) m 口= o ，苇x jtn q 、 若记t 的领域集矩阵为置= ( ，气) ，m = ( 心，m ，坂) ，则问题( 2 8 ) 可以转化为： m 肘i ，nm , 7 ( r 一五) 7 ( x f 一置) m ，s j m r t = l 中山大学硕士学位论文：有监督的流形学习及其在人体行为识别中的应用 此问题可以用拉格朗日乘数法求解。用口表示拉格朗日乘子，则m 与口应满足 2 ( x ，l r z ) 7 ( 薯i t x i ) m , + o 1 ：0 ，m , i ：1 所以，；gg ：( r z ) 7 ( x f 一置) 可逆时， 弘篙，硎可以用鼢二乘 法求解m 。 在得到局部线性结构矩阵 坞) 后，把问题( 2 7 ) 写成矩阵的形式，我们可 以得到( 2 - 7 ) 的等价形式： 而因为 m i n ”y m r l l 2 ly - y m r i l 2 = t r ( ( y y m ，) ( 】，7 一m y 7 ” = t r ( y ( i m7 ) ( ，一m ) y 7 ) 所以，( 2 - 9 ) 等价于 m i n t r ( y ( i m ) 7 ( ，一m ) y r ) s j y ，= ， 而问题( 2 1 0 ) 相当求解特征问题 ( i m ) 7 ( ，一m ) e = 2 e ( 2 - 9 ) ( 2 - 1 0 ) ( 2 - 1 1 ) 因为m ，= 1 ，所以 l - ( m 扩+ 一m 雎m 眵) = 1 - 1 + 咏一帆 ( 2 一1 2 ) j k j = 0 所以( ，一m )