流形学习中的增量谱嵌入方法
|
摘要
数据的维数约简是数学与计算机科学的新兴交叉研究方向.它所关注的问题是如何将高维数据表示在低维空间中,并由此发现其内在结构.特别地,流形学习方法在理解多维模式结构中取得了巨大成功.然而,大多数的流形学习算法以批处理的方式执行,进而无法高效地实现高维数据流的约简表示.为此,研究人员将目光投向了增量流形学习.
本文在增量学习的背景下,讨论了流形学习中谱嵌入算法的处理新样本数据的拓展.具体而言,本文的主要贡献可归纳为以下两个方面.
一方面,针对一类重要的流形学习方法——谱嵌入算法,本文给出了一个增量实现的一般框架.该框架不仅囊括了若干现有的增量算法,而且克服了现有算法每次只能处理一个样本的限制,提供了可以一次处理多个样本的新拓展.与此同时,我们给出了增量谱嵌入算法的收敛条件,分析了算法的收敛性.
另一方面,利用增量谱嵌入算法的一般框架,我们给出了两种新的增量算法——增量HLLE算法和增量LSE算法,同时分析了这两个增量算法的计算复杂性.通过与原算法计算复杂度的对比,本文从理论上证实了增量算法的高效性.另外,在合成数据集和图像数据集上的数值实验验证了提出的增量算法的准确度和时效性.这些数值实验包括两个方面,一是维数约简,二是在维数约简基础上进行的模式分类.
最后,我们对全文的工作进行了总结,并对将来的研究工作做了几点展望.
Dimensionality reduction is a novel research direction, which integrates the knowl-edge from mathematics and computer science. It mainly focuses on the problem of repre-senting the original high dimensional data in a low dimensional space and discovering theintrinsic structure. Especially, manifold learning methods make a great progress in un-derstanding the structure of multidimensional patterns. Most of these methods, however,operate in a batch mode and cannot be effectively applied when data samples are collectedsequentially. Therefore,incrementalmanifoldlearninghasappearedinresearchers'sights.
Under the background of incremental learning, this thesis has exclusively studiedout-of-sample extensions of spectral embedding algorithms in manifold learning. Moreconcretely, the main contributions of this thesis can be summarized into two aspects.
On the one hand, a general incremental framework is proposed for spectral embed-ding algorithms, a significant category of manifold learning methods. Not only does thisframework unify several contributions in incremental learning, but also it extends the ex-isting methods to be able to deal with the cases when two or more observations comesimultaneously, conquering the limitation of tackling only one sample per time. Mean-while,wepresenttheconvergentconditionsofincrementalspectralembeddingalgorithmsand analyze their convergence performance.
On the other hand, two novel incremental algorithms, consisting of the incrementalHLLE algorithm and the incremental LSE algorithm, are proposed by utilizing the generalframework as a tool. The complexity of computations of these two algorithms is theoret-ically analyzed. Compared with the batch methods, the two incremental methods show adesirable gift in terms of computational costs. Moreover, the efficiency and the accuracyof the proposed algorithms are evaluated on both synthetic and image dataset. All thenumerical simulations are designed from two views: one is dimensionality reduction andthe other is pattern classification based on reduced representation of original data.
Finally, we sum up the research results in this thesis and describe several directionsof further research in the fields.
本文在增量学习的背景下,讨论了流形学习中谱嵌入算法的处理新样本数据的拓展.具体而言,本文的主要贡献可归纳为以下两个方面.
一方面,针对一类重要的流形学习方法——谱嵌入算法,本文给出了一个增量实现的一般框架.该框架不仅囊括了若干现有的增量算法,而且克服了现有算法每次只能处理一个样本的限制,提供了可以一次处理多个样本的新拓展.与此同时,我们给出了增量谱嵌入算法的收敛条件,分析了算法的收敛性.
另一方面,利用增量谱嵌入算法的一般框架,我们给出了两种新的增量算法——增量HLLE算法和增量LSE算法,同时分析了这两个增量算法的计算复杂性.通过与原算法计算复杂度的对比,本文从理论上证实了增量算法的高效性.另外,在合成数据集和图像数据集上的数值实验验证了提出的增量算法的准确度和时效性.这些数值实验包括两个方面,一是维数约简,二是在维数约简基础上进行的模式分类.
最后,我们对全文的工作进行了总结,并对将来的研究工作做了几点展望.
Dimensionality reduction is a novel research direction, which integrates the knowl-edge from mathematics and computer science. It mainly focuses on the problem of repre-senting the original high dimensional data in a low dimensional space and discovering theintrinsic structure. Especially, manifold learning methods make a great progress in un-derstanding the structure of multidimensional patterns. Most of these methods, however,operate in a batch mode and cannot be effectively applied when data samples are collectedsequentially. Therefore,incrementalmanifoldlearninghasappearedinresearchers'sights.
Under the background of incremental learning, this thesis has exclusively studiedout-of-sample extensions of spectral embedding algorithms in manifold learning. Moreconcretely, the main contributions of this thesis can be summarized into two aspects.
On the one hand, a general incremental framework is proposed for spectral embed-ding algorithms, a significant category of manifold learning methods. Not only does thisframework unify several contributions in incremental learning, but also it extends the ex-isting methods to be able to deal with the cases when two or more observations comesimultaneously, conquering the limitation of tackling only one sample per time. Mean-while,wepresenttheconvergentconditionsofincrementalspectralembeddingalgorithmsand analyze their convergence performance.
On the other hand, two novel incremental algorithms, consisting of the incrementalHLLE algorithm and the incremental LSE algorithm, are proposed by utilizing the generalframework as a tool. The complexity of computations of these two algorithms is theoret-ically analyzed. Compared with the batch methods, the two incremental methods show adesirable gift in terms of computational costs. Moreover, the efficiency and the accuracyof the proposed algorithms are evaluated on both synthetic and image dataset. All thenumerical simulations are designed from two views: one is dimensionality reduction andthe other is pattern classification based on reduced representation of original data.
Finally, we sum up the research results in this thesis and describe several directionsof further research in the fields.
引文
[1] Bellman R E. Adaptive Control Processes - A Guided Tour[M]. New Jersy: Prince-ton University Press, 1961.
[2] Donoho D L. HIgh dimensional data analysis: the curse and blessings of dimen-sionality[C]. American Mathematics Society Conference: Conference:Math Chal-lenges of the 21st Century. 2000.
[3] Cunningham P. Dimension reduction[R]: University College Dublin, 2007.
[4] Pearson K. On lines and planes of closest fit to systems of points in space[J]. Philo-sophical Magazine, 1901, 2:559--572.
[5] Jolliffe I. Principal Component Analysis[M]. second ed. New York: Springer, 2002.
[6] Fisher R A. The use of multiple measurements in taxonomic problems[J]. AnnalsEugen., 1936, 7:179--188.
[7] Duda R O, Hart P E, Stork D. Pattern Classification[M]. second ed. Hoboken, NJ:Wiley-Interscience, 2000.
[8] Cox T F, Cox M A A. Multidimensional Scaling[M]. second ed. London: Chapmanand Hall, 2001.
[9] Lin T, Zha H B. Riemannian manifold learning[J]. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2008, 30(5):796--809.
[10]侯臣平.基于图优化框架的数据维数约简方法及应用研究[D].长沙:国防科学技术大学, 2009.
[11] van der Maaten L J P. Feature extraction from visual data[D]. Netherlands: TilburgUniversity, 2009.
[12] Tenenbaum J B, Silva V d, Langford J C. A global geometric framework for nonlin-ear dimensionality reduction[J]. Science, 2000, 290(5500):2319--2323.
[13] Silva V d, Tenenbaum J B. Global versus local approaches to nonlinear dimension-alityreduction[C].AdvancesinNeuralInformationProcessingSystems. Vancouver,BC, Canada: MIT Press, 2003,15:705--712.
[14] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embed-ding[J]. Science, 2000, 290(5500):2323--2326.
[15] Saul L K, Roweis S T. Think globally, fit locally: Unsupervised learning of lowdimensional manifolds[J]. Journal of Machine Learning Research, 2004, 4(2):119--155.
[16] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and datarepresentation[J]. Neural Computation, 2003, 15(6):1373--1396.
[17] Donoho D L, Grimes C. Hessian eigenmaps: Locally linear embedding techniquesfor high-dimensional data[J]. Proceedings of the National Academy of Sciences ofthe United States of America, 2003, 100(10):5591--5596.
[18] Weinberger K, Saul L K. Unsupervised learning of image manifolds by semidefiniteprogramming[C]. IEEE International Conference on Computer Vision and PatternRecognition. Washington, DC: IEEE, 2004,2:988--995.
[19] ZhangZY,ZhaHY. Principalmanifoldsandnonlineardimensionalityreductionviatangentspacealignment[J]. SiamJournalonScientificComputing, 2004, 26(1):313--338.
[20] Xiang S M, Nie F P, Zhang C S, et al. Nonlinear dimensionality reduction with localspline embedding[J]. IEEE Trans Knowl Data Eng, 2009, 21(9):1285--1298.
[21] Yin H J, Huang W L. Adaptive nonlinear manifolds and their applications to patternrecognition[J]. InformationSciences,2010,180(14):2649--2662. Yin,HujunHuang,Weilin.
[22] Mao J, Jain A K. Artificial neural networks for feature extraction and multivariatedata projection[J]. IEEE Trans Neural Networks, 1995, 6:296–317.
[23] Lowe D, Tipping M E. Feed-forward neural networks and topographic mappings forexploratory data analysis[J]. Neural Comput Appl, 1996, 4:83--95.
[24] Kohonen T. Self-organised formation of topologically correct feature map[J]. Biol.Cybernet., 1982, 43:56--69.
[25] Kohonen T. Self-Organized Maps[M]. third ed. New York: Springer, 2001.
[26] Bishop C M, Svensén M, Williams C K I. GTM: The generative topographic map-ping[J]. Neural Computation, 1998, 10:215--234.
[27] Yin H J. ViSOM– a novel method for multivariate data projection and structurevisualisation[J]. IEEE Transactions on Neural Networks, 2002, 13(1):237--243.
[28] YinHJ. Onmultidimensionalscalingandtheembeddingofself-organisingmaps[J].Neural Networks, 2008, 21(2-3):160--169.
[29] Law M H C, Jain A K. Incremental nonlinear dimensionality reduction by manifoldlearning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006,28(3):377--391.
[30] Bengio Y, Paiement J F O, Vincent P, et al. Out-of-sample extensions for LLE,Isomap, MDS, eigenmaps, and spectral clustering[C]. Thrun S, Saul K, ScholkopfB. Advances in Neural Information Processing Systems. 2004. Vancouver, BC,Canada: MIT Press, Advances in Neural Information Processing Systems, vol. 16.
[31] ChinTJ,SuterD. Out-of-sampleextrapolationoflearnedmanifolds[J]. IEEETrans-actions on Pattern Analysis and Machine Intelligence, 2008, 30(9):1547--1556.
[32] Xiang S M, Nie F P, Song Y Q, et al. Embedding new data points for manifoldlearning via coordinate propagation[J]. Knowledge and Information Systems, 2009,19(2):159--184.
[33] Kouropteva O, Okun O, Pietikainen M. Incremental locally linear embedding[J].Pattern Recognition, 2005, 38(10):1764--1767.
[34] Kumar S, Guivant J, Upcroft B, et al. Sequential nonlinear manifold learning[J].Intelligent Data Analysis, 2007, 11(2):203--222.
[35] Liu X M, Yin J W, Feng Z L, et al. Incremental manifold learning via tangent spacealignment[C]. SchwenkerF,MarinaiS. ArtificialNeuralNetworksinPatternRecog-nition. 2006. Ulm, Germany: Springer, Lecture Notes in Artificial Intelligence, vol.4087.
[36] Jia P, Yin J S, Huang X S, et al. Incremental Laplacian eigenmaps by preservingadjacent information between data points[J]. Pattern Recognition Letters, 2009,30(16):1457--1463.
[37] Yan S, Xu D, Zhang B, et al. Graph Embedding and Extensions: A General Frame-work for Dimensionality Reduction[J]. IEEE Transactions on Pattern Analysis andMachine Intelligence, 2007, 29(1):40 --51.
[38] Horn R A, Johnson C R. Matrix Analysis[M]. Cambridge: Cambridge UniversityPress, 1986.
[39] Golub G H, Van Loan C F. Matrix Computations[M]. third ed. Baltimore, MD: TheJohns Hopkins University Press, 1996.
[40] Stewart G. Accelerating the orthogonal iteration for the eigenvectors of a Hermitianmatrix[J]. Numerische Mathematik, 1969, 13(4):362--376.
[41] Friedman J, Hastie T, Tibshirani R. The Elements of Statistical Learning, Data Min-ing Inference and Prediction[M]. second ed. New York: Springer, 2008.
[42] SmithAK,HuoX. Perturbationanalysisofamanifoldlearningalgorithm--Hessianlocally linear embedding[R]: Georgia Institute of Technology, 2006.
[43] Patwari N, Hero A O. Manifold learning algorithms for localization in wirelesssensornetworks[C].IEEEInternationalConferenceonAcoustic, Speech, andSignalProcessing. Toulouse, France: IEEE, 2004,3:857--860.
[44] Rahimi A, Recht B, Darrell T. Learning appearance manifolds from video[C]. IEEEComputer Society Conference on Computer Vision and Pattern Recognition. SanDiego, CA, USA: IEEE Computer Society, 2005,1:868--875.
[45] Lim H, Camps O I, Sznaier M, et al. Dynamic appearance modeling for humantracking[C]. IEEE Computer Society Conference on Computer Vision and PatternRecognition. New York, NY, USA: IEEE Computer Society, 2006,1:751 -- 757.
[46] Elmer S P, Pande V S. Foldamer simulations: Novel computational methodsand applications to poly-phenylacetylene oligomers[J]. J. Chem. Phys., 2004,121(24):12760 -- 12771.
[47] Chen Y, Davis T A, Hager W W, et al. Algorithm 887: CHOLMOD, supernodalsparse Cholesky factorization and update/downdate[J]. ACM Trans. Math. Softw.,2008, 35(3):1--14.
[48] Abdel-Mannan O, Ben Hamza A, Youssef A. Incremental Hessian locally linearembedding algorithm[C]. 2007 9th International Symposium on Signal Processingand Its Applications. Sharjah, United Arab Emirates: IEEE, 2007,1-3:484--487.
[49] Yang Y, Nie F, Xiang S, et al. Local and global regressive mapping for manifoldlearningwithout-of-sampleextrapolation[C].Proceedingsofthe24thAAAIConfer-ence on Artificial Intelligence. Atlanta, Georgia, USA: AAAI Press, 2010:649--654.
[50] Bebe S, Nayar S, Murase H. Columbia object image library (Coil-20)[R], 1996.
[51] BeygelzimerA,KakadeS,LangfordJ. Covertreesfornearestneighbor[C].Proceed-ings of the 23rd international conference on Machine learning. Pittsburgh, Pennsyl-vania: ACM, 2006:97--104.
[2] Donoho D L. HIgh dimensional data analysis: the curse and blessings of dimen-sionality[C]. American Mathematics Society Conference: Conference:Math Chal-lenges of the 21st Century. 2000.
[3] Cunningham P. Dimension reduction[R]: University College Dublin, 2007.
[4] Pearson K. On lines and planes of closest fit to systems of points in space[J]. Philo-sophical Magazine, 1901, 2:559--572.
[5] Jolliffe I. Principal Component Analysis[M]. second ed. New York: Springer, 2002.
[6] Fisher R A. The use of multiple measurements in taxonomic problems[J]. AnnalsEugen., 1936, 7:179--188.
[7] Duda R O, Hart P E, Stork D. Pattern Classification[M]. second ed. Hoboken, NJ:Wiley-Interscience, 2000.
[8] Cox T F, Cox M A A. Multidimensional Scaling[M]. second ed. London: Chapmanand Hall, 2001.
[9] Lin T, Zha H B. Riemannian manifold learning[J]. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2008, 30(5):796--809.
[10]侯臣平.基于图优化框架的数据维数约简方法及应用研究[D].长沙:国防科学技术大学, 2009.
[11] van der Maaten L J P. Feature extraction from visual data[D]. Netherlands: TilburgUniversity, 2009.
[12] Tenenbaum J B, Silva V d, Langford J C. A global geometric framework for nonlin-ear dimensionality reduction[J]. Science, 2000, 290(5500):2319--2323.
[13] Silva V d, Tenenbaum J B. Global versus local approaches to nonlinear dimension-alityreduction[C].AdvancesinNeuralInformationProcessingSystems. Vancouver,BC, Canada: MIT Press, 2003,15:705--712.
[14] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embed-ding[J]. Science, 2000, 290(5500):2323--2326.
[15] Saul L K, Roweis S T. Think globally, fit locally: Unsupervised learning of lowdimensional manifolds[J]. Journal of Machine Learning Research, 2004, 4(2):119--155.
[16] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and datarepresentation[J]. Neural Computation, 2003, 15(6):1373--1396.
[17] Donoho D L, Grimes C. Hessian eigenmaps: Locally linear embedding techniquesfor high-dimensional data[J]. Proceedings of the National Academy of Sciences ofthe United States of America, 2003, 100(10):5591--5596.
[18] Weinberger K, Saul L K. Unsupervised learning of image manifolds by semidefiniteprogramming[C]. IEEE International Conference on Computer Vision and PatternRecognition. Washington, DC: IEEE, 2004,2:988--995.
[19] ZhangZY,ZhaHY. Principalmanifoldsandnonlineardimensionalityreductionviatangentspacealignment[J]. SiamJournalonScientificComputing, 2004, 26(1):313--338.
[20] Xiang S M, Nie F P, Zhang C S, et al. Nonlinear dimensionality reduction with localspline embedding[J]. IEEE Trans Knowl Data Eng, 2009, 21(9):1285--1298.
[21] Yin H J, Huang W L. Adaptive nonlinear manifolds and their applications to patternrecognition[J]. InformationSciences,2010,180(14):2649--2662. Yin,HujunHuang,Weilin.
[22] Mao J, Jain A K. Artificial neural networks for feature extraction and multivariatedata projection[J]. IEEE Trans Neural Networks, 1995, 6:296–317.
[23] Lowe D, Tipping M E. Feed-forward neural networks and topographic mappings forexploratory data analysis[J]. Neural Comput Appl, 1996, 4:83--95.
[24] Kohonen T. Self-organised formation of topologically correct feature map[J]. Biol.Cybernet., 1982, 43:56--69.
[25] Kohonen T. Self-Organized Maps[M]. third ed. New York: Springer, 2001.
[26] Bishop C M, Svensén M, Williams C K I. GTM: The generative topographic map-ping[J]. Neural Computation, 1998, 10:215--234.
[27] Yin H J. ViSOM– a novel method for multivariate data projection and structurevisualisation[J]. IEEE Transactions on Neural Networks, 2002, 13(1):237--243.
[28] YinHJ. Onmultidimensionalscalingandtheembeddingofself-organisingmaps[J].Neural Networks, 2008, 21(2-3):160--169.
[29] Law M H C, Jain A K. Incremental nonlinear dimensionality reduction by manifoldlearning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006,28(3):377--391.
[30] Bengio Y, Paiement J F O, Vincent P, et al. Out-of-sample extensions for LLE,Isomap, MDS, eigenmaps, and spectral clustering[C]. Thrun S, Saul K, ScholkopfB. Advances in Neural Information Processing Systems. 2004. Vancouver, BC,Canada: MIT Press, Advances in Neural Information Processing Systems, vol. 16.
[31] ChinTJ,SuterD. Out-of-sampleextrapolationoflearnedmanifolds[J]. IEEETrans-actions on Pattern Analysis and Machine Intelligence, 2008, 30(9):1547--1556.
[32] Xiang S M, Nie F P, Song Y Q, et al. Embedding new data points for manifoldlearning via coordinate propagation[J]. Knowledge and Information Systems, 2009,19(2):159--184.
[33] Kouropteva O, Okun O, Pietikainen M. Incremental locally linear embedding[J].Pattern Recognition, 2005, 38(10):1764--1767.
[34] Kumar S, Guivant J, Upcroft B, et al. Sequential nonlinear manifold learning[J].Intelligent Data Analysis, 2007, 11(2):203--222.
[35] Liu X M, Yin J W, Feng Z L, et al. Incremental manifold learning via tangent spacealignment[C]. SchwenkerF,MarinaiS. ArtificialNeuralNetworksinPatternRecog-nition. 2006. Ulm, Germany: Springer, Lecture Notes in Artificial Intelligence, vol.4087.
[36] Jia P, Yin J S, Huang X S, et al. Incremental Laplacian eigenmaps by preservingadjacent information between data points[J]. Pattern Recognition Letters, 2009,30(16):1457--1463.
[37] Yan S, Xu D, Zhang B, et al. Graph Embedding and Extensions: A General Frame-work for Dimensionality Reduction[J]. IEEE Transactions on Pattern Analysis andMachine Intelligence, 2007, 29(1):40 --51.
[38] Horn R A, Johnson C R. Matrix Analysis[M]. Cambridge: Cambridge UniversityPress, 1986.
[39] Golub G H, Van Loan C F. Matrix Computations[M]. third ed. Baltimore, MD: TheJohns Hopkins University Press, 1996.
[40] Stewart G. Accelerating the orthogonal iteration for the eigenvectors of a Hermitianmatrix[J]. Numerische Mathematik, 1969, 13(4):362--376.
[41] Friedman J, Hastie T, Tibshirani R. The Elements of Statistical Learning, Data Min-ing Inference and Prediction[M]. second ed. New York: Springer, 2008.
[42] SmithAK,HuoX. Perturbationanalysisofamanifoldlearningalgorithm--Hessianlocally linear embedding[R]: Georgia Institute of Technology, 2006.
[43] Patwari N, Hero A O. Manifold learning algorithms for localization in wirelesssensornetworks[C].IEEEInternationalConferenceonAcoustic, Speech, andSignalProcessing. Toulouse, France: IEEE, 2004,3:857--860.
[44] Rahimi A, Recht B, Darrell T. Learning appearance manifolds from video[C]. IEEEComputer Society Conference on Computer Vision and Pattern Recognition. SanDiego, CA, USA: IEEE Computer Society, 2005,1:868--875.
[45] Lim H, Camps O I, Sznaier M, et al. Dynamic appearance modeling for humantracking[C]. IEEE Computer Society Conference on Computer Vision and PatternRecognition. New York, NY, USA: IEEE Computer Society, 2006,1:751 -- 757.
[46] Elmer S P, Pande V S. Foldamer simulations: Novel computational methodsand applications to poly-phenylacetylene oligomers[J]. J. Chem. Phys., 2004,121(24):12760 -- 12771.
[47] Chen Y, Davis T A, Hager W W, et al. Algorithm 887: CHOLMOD, supernodalsparse Cholesky factorization and update/downdate[J]. ACM Trans. Math. Softw.,2008, 35(3):1--14.
[48] Abdel-Mannan O, Ben Hamza A, Youssef A. Incremental Hessian locally linearembedding algorithm[C]. 2007 9th International Symposium on Signal Processingand Its Applications. Sharjah, United Arab Emirates: IEEE, 2007,1-3:484--487.
[49] Yang Y, Nie F, Xiang S, et al. Local and global regressive mapping for manifoldlearningwithout-of-sampleextrapolation[C].Proceedingsofthe24thAAAIConfer-ence on Artificial Intelligence. Atlanta, Georgia, USA: AAAI Press, 2010:649--654.
[50] Bebe S, Nayar S, Murase H. Columbia object image library (Coil-20)[R], 1996.
[51] BeygelzimerA,KakadeS,LangfordJ. Covertreesfornearestneighbor[C].Proceed-ings of the 23rd international conference on Machine learning. Pittsburgh, Pennsyl-vania: ACM, 2006:97--104.