第5卷第6期 智能系统学报 Vol.5 No.6 2010年12月 CAAI Transactions on Intelligent Systems Dec.2010 doi:10.3969/j.issn.1673-4785.2010.06.002 流形学习与基于线性耦合映射的流形对齐 姜峰，李博，姚鸿勋，刘绍辉 (哈尔滨工业大学计算机学院，黑龙江哈尔滨150001) 摘要：从一些具有代表性的经典流形学习方法的回顾来看，传统的流形学习主要处理来自单一流形的数据的降维 问题.随着流形学习研究的不断深入，以多流形作为研究对象的流形学习问题逐步引起了研究者的注意.提出了一 种基于线性耦合映射的流形对齐算法.算法克服非线性流形对齐算法不能够直接处理Out-of-sample数据的问题.同 时，与已有的线性流形对齐算法相比，该算法不需要假设流形间满足仿射变换关系，因而能够更加灵活地处理一些 比较实际的流形对齐问题。 关键词：流行学习；流行对齐；线性耦合 中图分类号：TP18文献标志码：A文章编号：16734785(2010)06047606 Manifold learning and manifold alignment based on coupled linear projections JIANG Feng,LI Bo,YAO Hong-xun,LIU Shao-hui School of Computer Science,Harbin Institute of Technology,Harbin 150001,China) Abstract:Traditional manifold learning mainly deals with data dimensionality reduction problems from a single manifold.Through further development,manifold learning focusing on the multi-manifold has drawn the attention of many scholars.An algorithm of manifold alignment based on coupled projections was proposed.The proposed meth- od using the coupled linear projections dealt with an out-of-sample data set without re-training.Compared to other linear methods,it handled some real problems of manifold alignment with flexibility since the proposed method did not need any assumptions about the relationship of affine transformation between the manifolds. Keywords:manifold learning;manifold alignment;coupled projection 近年来随着有关流形学习算法的研究不断深 究刚刚起步，所以无论是流形对齐理论研究还是流 入，相关算法在高维数据降维和数据可视化等方面 形对齐算法在实际的模式识别、计算机视觉问题上 取得了巨大成功14].流形学习算法在机器学习、模 的应用研究都还有很长的路要走，为了克服非线性 式识别、计算机视觉等领域得到了广泛推广，成为上 流形对齐算法在处理Out-of-sample数据的先天不 述领域的研究热点.然而，从一些具有代表性的经典 足6]，本文提出了一种基于线性耦合映射的流形对 流形学习方法的回顾来看5，传统的流形学习主要 齐算法.与一些已有的线性流形对齐算法不同，本文 处理来自单一流形的数据的降维问题.随着流形学 提出线性耦合映射并不需要对流形间的关系进行很 习研究的不断深入，以多流形作为研究对象的流形 强的模型假设，因此也能更加灵活地处理一些较为 学习问题逐步引起了研究者的注意.“流形对齐”就 实际的流形对齐问题 是多流形学习中的一个代表性问题，具有重要的理 1流形对齐的研究进展 论价值和广泛的应用前景.近年来，流形对齐算法的 研究已经取得了一定进展，涌现出了一些非线性和 1.1问题描述 线性的流形对齐算法.然而，因为有关流形对齐的研 流形对齐的研究对象是来自不同流形上的多个 采样（数据）集合.为了便于理解，以2个流形的流 收稿日期：2009-1205. 基金项目：黑龙江省自然科学基金资助项目(200812) 形对齐问题为例进行阐述，在高维空间的存在2个 通信作者：姜峰.E-mail:iang@hit.edu.cn. 流形MCR:和M,CR”,在其上分别采样得到2
第6期 姜峰，等：流形学习与基于线性耦合映射的流形对齐 ·477 个采样集合，记为 式中：h=[g]T,e=[11…1]T是大小为 X={x,x,…,xw}CR (N+N,)×1的全1的列向量.这样最小化问题最终 Y={y1,2,…,y,}CR. 可以通过特征值分解的来解析求解作者在不同物体 在流形对齐问题中，一般情况下会认为不同的 的姿态数据库上检验了非线性流形对齐算法的性能. 流形MCR和M,CR”背后存在着一个彼此共享 文献[1]给出的是非线性流形对齐算法中的代 的、本质的公共流形McCR”.例如，不同分辨率的 表算法.其他一些流形对齐的相关工作还有文献[8- 人脸图像组成的流形实际上是共享着一个人脸公共 9]等.其中，文献[8]主要完成将一个流形对齐到另 流形.这些来自不同流形上的采样点在公共流形上 一个目标流形上去的任务，而文献[9]主要是利用 有一个对应的像点.对于X={x,2,…,xw,}CM 具有有序关系的信息来进行半监督流形对齐的.此 和M,CR”来讲，在M。上有一个集合X={x, 外，一些相关的技术（如高斯过程等10）对从其他 2,…,xN,}CM。与之对应.同样，Y={y,2,…, 方面理解流形对齐也会有所帮助， 1.3线性流形对齐 yw{CM。对应于采样点集合Y={1,2,…,xN,}C 非线性流形对齐算法在处理Out-of-sample数 M,如果x:和y:在公共流形M。上有相同的像点， 据点时[6]，需要重新进行训练.这是由于非线性算 则称x:和y:对应.而流形对齐的任务恰恰就是要找 法不能得到显式的映射，即从高维空间数据点到相 到来自不同流形的采样点之间的对应关系。 应的低维嵌入的映射函数.为此，文献[11]中给出 1.2非线性流形对齐 了一种可能的解决方案.这种方法可以简要地总结 在文献[7]中，作者从半监督学习的角度阐述 如下： 和形式化了流形对齐问题及其若干应用，并给出了 1)通过线性流形学习的方法对数据集合X和Y 相应的解法.对于给定2个高维空间的数据集合 进行降维，找到各自的低维嵌入？和Y,即x= X={1,2,…,x}CR0,和Y={1y…,%,}C g.(x),gR0:→R,xeR”,xeR;y=g,(y）,g, R“.如前所述，这些来自于嵌入在高维空间的低维 RP,→R,yeR,y∈R; 流形上的采样点集合，可以通过基于图模型的流形 2)通过基于Procructes分析的回归算法对2个 学习方法来找到其对应的低维嵌入.用G=(v,,w) 低维嵌人集合X和Y进行对齐，即 来表示由顶点集合)和边集合专构成的图.以拉普 拉斯特征映射(Laplacian eigenmap）为例，通过最小 inL(Q,)=∑I年-x-s(y-)Q2. 化下面的目标： 式中：x=mean(X),y=mean(Y).如作者在文献 ff=∑(f-f)S [11]中所述，如果在1)中选择具有显式的映射函数 的线性流形降维方法，然后配合2)基于线性回归的 来学习得到一个实值方程∫：)→R这里S表示相似 流形对齐方法，那么算法就能直接处理Out-of-sam 度矩阵，L表示广义图拉普拉斯矩阵。 ple的问题.然而，这种将降维和对齐割裂成2个步 这样对于2个数据集合X和Y,分别定义实值 骤的方式显然很难达到最优解，而且其中包含太多 方程∫和g,以及对应的广义拉普拉斯矩阵L和 的参数选择.例如1)中降维的维数选择就会影响到 L.在半监督对应学习的框架下，最终流形对齐的目 最后的流形对齐效果.此外基于Procructes分析的 标被形式化为 回归算法，具有较强的前提假设，即假设2个流形之 L(f,g)=u∑If-g:‖2+fLf+gLg 间只存在尺度、平移和旋转这样的仿射变换.显然这 式中：C是一个对应标注集合.如果i∈C,则表示已 种前提条件在实际问题中很难得到满足 知集合X中第i个数据点x:和集合Y中第i个数据 在前文中回顾了一些现有的具有代表性的流形 点y:为对应点.对于这样一个病态优化目标，文献 对齐算法，对于非线性流形对齐算法来讲，处理Out- [7]将最小化目标转化为一个最小化广义瑞利商的 of-sample数据的先天不足，限制了该类方法的适用 问题，即 范围.而对于文献[11]中提出的线性流形对齐算 L(f,8) 法，过强的前提假设导致算法只能够处理特定的流 min L(h) ff+8g ,.t.hTe=0. 形对齐问题.从上述两方面来讲已有的流形对齐算
478 智能系统学报 第5卷 法存在着不同的缺憾.为此，本文提出了一种结合2 类算法的优点的流形对齐算法，从而能够在不引入 器10=k及.)-o 过强的假设的前提下，兼顾处理Out-of-sample数据 这样，优化目标从直接寻找最优的满足对应关 问题， 系保持目标的低维嵌入和Y,转化为寻找最优的 满足对应关系保持目标的显式映射方程x=f(x)和 2基于线性耦合映射的流形对齐 y=∫，(y).这样的数学描述使得本文的方法具有了 为克服流形对齐算法处理Out-of-sample数据 直接处理Out-of-sample的数据能力，即通过显式的 时需要重新训练的问题，提出一种基于线性耦合映 映射函数能直接将新的数据投影到公共流形上去而 射的流形对齐方法.本文方法通过引入显式的映射 不需要重新进行训练优化. 函数为直接处理训练集之外的新数据提供了可能. 2.2流形结构保持正则化 下面首先给出本文方法的问题描述 从流形对齐的角度出发，低维空间的低维嵌入 如前所述，流形对齐的基本任务就是找到不同 仅仅保持已知的对应关系（对应关系保持目标）并 数据集合所对应的公共低维嵌入.对于数据集合X 不够.因为，原始高维空间的数据点之间的流形结构 和Y,通过显式的映射函数f:R→R和f: 对于寻找公共低维流形同样非常重要；所以，公共低 RP,→R找到原始数据点在公共流形上的低维嵌 维流形M。低维嵌入需要保持原始高维空间点之间 入.同时，这些嵌入要满足已知的通过人工标注得到 的局部结构，称之为流形结构保持约束.对于流形结 的对应关系.如文献[4]中提到的，流形对齐需要满 构保持约束来讲，可以采用大部分流形学习降维算 足一个目标和一个约束： 法中的流形结构保持的优化目标形式.但是，对于具 1)需要满足已知的来自不同流形上的数据点 体的问题需要选择适当的流形结构保持约束.为了 之间的对应关系，称之为“对应关系保持目标” 论述方便起见，采用了基于图模型的流形结构保持 2)同时，公共流形需要保持原始高维数据点各自 约束的数学形式，即 的流形结构，本文中称之为“流形结构保持约束” 五=器1-， 下面将详细地介绍对应关系保持目标和流形结 构保持约束的具体数学形式化，以及最终的基于线 4=成名-% 性耦合映射的流形对齐算法。 式中：边权矩阵S和S分别用来描述数据集合X 2.1对应关系保持目标 和Y上的局部近邻关系.将显式的映射函数引入到 所谓对应关系保持目标是指在公共流形M。上 流形结构保持约束中，从而得到关于映射函数的流 的来自不同高维空间的数据点的低维嵌人和Y, 形约束正则化形式： 应该满足已知的X和Y之间的对应关系.为了描述 更一般的情况，这里使用了一个二元组集合来代表 J)=元器1(）-f)1 这种对应关系.对应关系集合C中包含了所有的已 知的对应点对，其中(i,)∈C表示了数据集合X中 ）=名6w）-1% 的第i个数据点x:和数据集合Y中的第j个数据点 至此，基于显式映射函数的流形结构保持约束 Y,之间存在对应关系. 的数学形式化完成。 如何在低维嵌入空间的公共流形上中保持这种 2.3流形对齐的优化目标 已标注的对应关系呢？显然，对应关系就意味着对 在2.1和2.2中，分别给出了对应关系保持目 应高维数据点对的低维表示在公共流形上是无限接 标和流形结构保持约束的具体数学表达，现在需要 近的.这一直观的目标可以通过最小化下面的目标 将这2个目标统一到一个目标函数下，通过简单的 函数来实现.对应关系保持目标函数如下： 加权和的形式给出最终的流形对齐的目标函数： 粤》=长A。医*另 )=Jc()+a)+a,J(f). ，(1) 式中：和α，是加权系数，为了平衡流形结构保持 式中：K=|C1,本文中引入了2个显式的映射方程 约束之间以及对应关系保持目标和流形结构保持约 x=f(x)和y=f,(y)后，式(1)有了如下新的形式： 束之间的比重.这个加权系数对于不同的问题有不
第6期 姜峰，等：流形学习与基于线性耦合映射的流形对齐 ·479… 同的具体选择，通常情况下采用a=1和&，=1的 minTr(PZOZ'P),s.t.PZZP =I and pTZe =0. 设置.对于显式的映射函数，这里采用线性变换的形 对于这种形式的目标优化，P可以通过求解广义特 式，如∫(x)=Px(y)=Py.P和P,是2个变换 征值分解问题EP=EP来得到，式中：E=Z2Z, 矩阵，其大小分别为D×d和D.×d F=ZZ". 显然如何优化这样一个联合目标函数成为解决 流形对齐的关键.首先来看一种最简单的情形，即数 3实验 据集合X和数据集合Y中具有相同数目的采样点 为了验证提出的基于线性耦合映射的流形对齐 且具有一一对应的关系.也就是说N=N。,另外当 算法的性能，实验部分分别测试了本文方法在处理 且仅当i=j时，(i,)∈C.下面通过线性代数的知识 姿态流形对齐和光照流形对齐任务时的有效性.实 将目标函数变换到矩阵形式.首先，来看流形对齐目 验分别在人脸姿态数据集Face-10、物体姿态数据集 标函数的第1项，对应关系保持目标J(ff).通过 COL-20I2以及人脸光照数据集Extended Yale Face 等价推导能得到 Database B13]上进行.在姿态实验中，流形对齐的任 (PP)=为1P-PI2=卡 务是找到来自不同人的头部姿态序列图像之间的对 应关系，甚至是找到不同物体的姿态序列图像之间 Tr(P:XX'P:+P'Y'P,-PIXYP,PTYX P). 的对应关系 式中：T()是一个矩阵求迹的函数X和Y分别为 3.1数据库 数据集合的矩阵表示形式，每个列向量代表了数据 集合中的一个高维数据点，矩阵X的大小为D.× N,矩阵Y的大小为D,×N.其次，对流形对齐目标 函数中关于流形结构保持约束项进行相类似的推 导.由Jx(f)可以得到 J(P)=N.IP-Ps (a)物休姿态数据集 hC01L-20中物体“uck” C01上.20的20种物体 的一些姿态图像示例 是(Pxp. 式中：矩阵S、D、L分别表示了定义在以集合X 中的数据点为顶点的图模型的边权矩阵、度矩阵、以 及广义拉普拉斯矩阵.类似，能够得到如下推导： (C)人脸姿态数据集Fe10巾的不同人的头部 P)=(Prr. 姿态序列图像示例 图1姿态数据集图像示例 依据上面的等价变换，流形对齐目标函数有了 Fig.1 Example images of pose dataset 新的形式，分别令 在人脸姿态数据集FACE-10中，共包含了来自 10个不同人的头部姿态序列图像.这些姿态在 P= -90°~90°连续变化，具体姿态定义可以参见图2 (b)中的姿态的坐标设置.图1(c)中给出了2个不 *N. 同人的头部姿态序列图像示例.不同人的头部姿态 1 I 序列图像的姿态采集间隔并不一致，所以不同序列 N 的采样数目也不固定.图示中给出的2个序列中分 这样得到了一个简约的流形对齐能量目标函数 别包含了138和134幅图像.实验中，姿态序列 的矩阵形式化表达：J(P)=Tr(PZ2ZP). Face-10中的采用了32×32大小的图像.在物体姿 为了保证上式优化目标函数的具有惟一且稳定 态数据集C0L-20中，共包含了20种不同物体（如 的解，需要引入尺度不变约束PZZP=I和平移不 图1(a)所示)的姿态序列图像.这些图像是按照图 变约束PZe=0.于是，流形对齐的优化目标最终被 2(a)中的物体姿态的坐标设置进行采集而来.因为 形式化为一个条件极值问题，即 物体姿态序列图像中相邻姿态的采集间隔为5°，所
·480 智能系统学报 第5卷 以每个姿态序列中包含了72幅图像.图1(b)中给 不需要重新进行训练和优化.与已有的线性方法不 出了“duck”序列的一些示例图像.实验中，姿态序 同，本算法采用一步优化的方式避免了简单地将线 列C0L-20采用了16×16大小的图像 性降维和低维对齐串联而导致难以达到最优结果的 问题.而且，也避免了已有线性算法中对不同流形之 间的关系进行假设而导致算法很难适用一般实际情 13 35 -90 -90 90° 况的问题.此外，数学形式上的统一和继承使得本算 9亦 45 法很容易从2个流形对齐推广到多流形对齐.另外， 09 本文提出优化目标最终能够通过解析方法求解，这 (a)物休姿态数据C0L-20 b)人脸姿态数据集FACE-10 也使得本算法具有实现简单、易于推广的特点， 的姿态设橙坐标 的姿态坐标设置 参考文献： 图2姿态数据集坐标设置示意图 Fig.2 The coordinate settings of pose dataset [1]TENENBAUM J,SILVA V,LANGFORD J.A global geo- 3.2实验结果及分析 metric framework for nonlinear dimensionality reduction[J]. 首先来看不同流形对齐算法在数据集C0L-20 Science,2000,5500(290):2319-2323. 上的表现.图3分别对比了3种流形对齐算法，包括： [2]ROWEIS S,SAUL L.Nonlinear dimensionality reduction by 1)文献[7]中非线性流形对齐算法；2)文献[11]中基 locally linear embedding[J].Science,2000,5500(290): 2323-2326. 于Procructes分析的线性流形对齐算法；3)本文的基 [3]SAUL L,ROWEIS S.Think globally,fit locally:unsuper- 于线性耦合映射的流形对齐算法.从图43中可以看 vised learning of low dimensional manifolds[J].The Journal 到，1)和本文方法给出了令人满意的流形对齐结果 of Machine Learning Research,2003,4:119-155. 而2)似乎不太适合来完成当前的这2个数据集合的 [4]BELKIN M,NIYOGI P.Laplacian eigenmaps for dimen- 流形对齐任务.参照2)的分析，以及图3(a)和(b)中 sionality reduction and data representation J].Neural 给出的2个数据集合各自的独立低维嵌入，不难发现 Computation,2003,15(6):1373-1396. 2)中关于2个流形关系的近似仿射变换的模型假设 [5]YAN S,XU D,ZHANG B,ZHANG H,YANG Q.Graph 并不适用于图3(a)和(b)中的情形 embedding and extensions:a general framework for dimen- sionality reduction[J].IEEE Transactions on Pattern Anal- ysis and Machine Intelligence,2007,29(1):40-51. [6]BENGIO Y,PAIEMENT J,VINCENT P,et al.Out-of- sample extensions for LIE,Isomap,MDS,eigenmaps,and (a)duck'数据的低维嵌人)hlock'数据的低维嵌入 spectral clustering[C]//Advances in Neural Information Processing Systems.Cambrige:MIT Press,2004:177-184 [7]HAM J,LEE D,SAUL L.Semisupervised alignment of manifolds[C]//Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence.Edinburgh,UK, (©)文献7中非线性（山文献11中的基于（伦）本文方法结果 方法的对齐结果 procructes分r的 2005:120-127. 对齐结果 [8 ]CONG Haifeng,PAN Chunhong,YANG Qing.A semi-su- 图3姿态流形对齐效果 pervised framework for mapping data to the intrinsic mani- Fig.3 Pose manifold alignment fold[C]//Tenth IEEE International Conference on Comput- er Vision2005.[S.1.],2005:98-105. 4结束语 [9]XIONG Liang,WANG Fei,ZHANG Changshui.Semi-defi- nite manifold alignment[J].Lecture Notes in Computer Sci- 描述了一种新的基于线性耦合映射的流形对齐 ence,2007,4701:773. 算法.本算法通过流形对齐目标的优化得到了从每 [10]RASMUSSEN C,WILLIAMS C.Gaussian processes for 一个流形到公共流形的显式的映射函数.与非线性 machine learning[M].Cambrige:The MIT Press,2006: 的隐式的映射函数不同，本算法能够直接地解决 101-107. Out-of-sample问题，能够直接处理新的测试数据而 [11]WANG C,MAHADEVAN S.Manifold alignment using
第6期 姜峰，等：流形学习与基于线性耦合映射的流形对齐 481 procrustes analysis[C]//Proceedings of the 25th Interna- 李博，男，1980年生，博士研究 tional Conference on Machine Learning.Helsinki,Fin- 生，主要研究方向为模式识别、机器学 1and,2008:1120-1127. 习、图像处理等。 [12]NENE S,NAYAR S,MURASE H.Columbia object image library coil-20)[R].CUCS-006-96,Department of Computer Science,Columbia University. [13]GEORGHIADES A,BELHUMEUR P,KRIEGMAN D. From few to many:illumination cone models for face rec- 姚鸿勋，女，1965年生，教授，博士 ognition under variable lighting and pose[J].IEEE 生导师，主要研究方向为多媒体数据分 Transactions on Patter Analysis and Machine Intelli- 析与理解、信息检索、视频监控、模式识 gence,2001,23(6):643-660. 别.完成国家自然科学基金重点项目1 作者简介： 项（评优），国家自然科学基金1项（评 姜峰，男，1978年生，硕士生导 优)，国家“863”计划重点项目子项目1 师.主要研究方向为模式识别、机器学 项，“863”计划项目3项，“863”青年基金1项，信息产业部2 习、图像处理等. 项，国际合作4项.获省部级科技成果奖4项，其中一等奖2 项，二等奖1项，三等奖1项，另获省级教学成果奖2项.已 获国家发明专利4项，审理中5项.出版教材5部.已发表国 内外学术论文160余篇，被SCI检索32篇，EI检索91篇， ISTP检录61篇. 《仿生智能计算》一书在科学出版社出版 由北京航空航天大学博土生导师段海滨撰写的《仿生智能计算》(SBN:978-7030295583)一书已在科学出 版社出版.中国工程院院士、北京大学信息科学技术学院首任院长、《智能系统学报》编委会主任、人工智能和计算 机软件著名学者何新贵教授认真审阅了书稿，并为该书欣然作序。 本书系统、深入地介绍了仿生智能计算的起源、原理、模型、理论及其应用，力图概括国内外在这一学术领域 的最新研究进展.全书共分12章，主要包括仿生智能计算的思想起源、研究现状及机制原理；仿生智能计算的数 学基础；蚁群算法、微粒群算法、人工蜂群算法、微分进化算法、Memetic算法、文化算法、人工免疫算法、DNA计算 的原理、模型、理论和典型应用，以及仿生硬件、仿生智能计算领域研究前沿与展望：附录部分给出了本书各章算 法实例的程序源代码，分类整理并给出了相关网站， 何新贵院士在序言中对段海滨近年来在仿生智能计算领域的工作给予了高度评价，并对该书作了如下评价： “1)学术上：全书突出基础，强调背景，并着眼学术前沿与发展；2)内容上：取材新颖，覆盖面广，深人浅出，系统 性强，注重理论联系实际；3)撰写上：结构严谨，条理清晰，选例恰当，撰写内容符合认知规律，富有启发性.《仿生 智能计算》是一本能够帮助读者较快掌握和应用仿生智能计算方法的好书，不仅具有较高的学术价值，而且对工 程应用也具有较大的参考价值和指导意义.我确信该书的出版必将对我国智能科学与技术学科的发展和应用、培 育创新性科技人才起到重要的推动作用.” 历生得能年 图书邮购信息： 地址：北京市东黄城根北街16号科学出版社工程技术分社 邮编：100717 联系人：孙芳 电话：01064006909 传真：010-64030248