流形学习

流形学习(manifold learning)是机器学习、模式识别中的一种方法,在维数约简方面具有广泛的应用。它的主要思想是将高维的数据映射到低维,使该低维的数据能够反映原高维数据的某些本质结构特征。流形学习的前提是有一种假设,即某些高维数据,实际是一种低维的流形结构嵌入在高维空间中。流形学习的目的是将其映射回低维空间中,揭示其本质。

简介

流形学习是一类借鉴了拓扑流形概念的降维方法。“流形”是指的是连在一起的区域,数学上,它指的是一组点,且每个点都有其邻域。给定任意一个点,其流形局部看起来像是欧几里得空间。换言之,它在局部空间有欧式空间的性质,能用欧式空间来进行距离计算。因此,很容易地在局部建立降维映射关系,然后再设法将局部关系推广到全局,进而进行可视化展示。[描述来源:周志华. (2016). 机器学习. Qing hua da xue chu ban she.;Goodfellow, I., Bengio, Y., Courville, A., & Bengio, Y. (2016). Deep learning (Vol. 1). Cambridge: MIT press.]

示意图如下所示:

Image.jpg

[图片来源:Tenenbaum, J. B., De Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. science, 290(5500), 2319-2323.]

流形学习的数学定义如下所示:已知数据集$X={x_1,x_2,...,x_n}$,假定$X$中的样本是由低维空间中的数据集$Y={y_1,y_2,...,y_n}ˆd$通过某个未知的非线性映射ƒ所生成的,即:

Image.jpg

其中$/eplison_i$表示噪声,d《D。[描述来源:Silva, V. D., & Tenenbaum, J. B. (2003). Global versus local methods in nonlinear dimensionality reduction. In Advances in neural information processing systems (pp. 721-728).]

2. 发展历史

描述

流形算法作为一个降维算法,有许多改进的算法被提出,并应用于不同的领域,如信息检索、模式分类与识别任务等。下图对比了现阶段常见流形算法的特征:

image.png

[图片来源: 姚雪曼. 基于流形学习的降维技术的研究与实现[D]. 中国科学技术大学]

主要事件

//必填,数量≥1

年份事件相关论文/Reference
1995Bregler 和Omohundro首次提出流形学习的概念Bregler, C., & Omohundro, S. M. (1995, June). Nonlinear manifold learning for visual speech recognition. In Computer Vision, 1995. Proceedings., Fifth International Conference on(pp. 494-499). IEEE.
2003de Silva 和Tenenbaum 给出了流形学习的准确数学描述de Silva, V., & Tenenbaum, J. B. (2003). Unsupervised learning of curved manifolds. In Nonlinear estimation and classification (pp. 453-465). Springer, New York, NY.
2000等距特征映射算法(Isomap)和局部线性嵌入算法(LLE)被提出Tenenbaum, J. B., De Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. science, 290(5500), 2319-2323.
2002-2003Laplacian Eigenmaps(LE) 和 Hessian Eigenmaps被提出(1)Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6), 1373-1396.(2)Donoho, D. L., & Grimes, C. (2003). Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Sciences, 100(10), 5591-5596.
2004-2006LTSA (Local tangent space alignment)和最大差异展开算法被提出(1)Zhang, Z., & Zha, H. (2004). Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. SIAM journal on scientific computing, 26(1), 313-338.(2)Weinberger, K. Q., & Saul, L. K. (2006, July). An introduction to nonlinear dimensionality reduction by maximum variance unfolding. In AAAI (Vol. 6, pp. 1683-1686).
2007黎曼流形学习算法被提出Lin, T., Zha, H., & Lee, S. U. (2006, May). Riemannian manifold learning for nonlinear dimensionality reduction. In European Conference on Computer Vision (pp. 44-55). Springer, Berlin, Heidelberg.
2008t-分布随机邻居嵌入算法被提出Maaten, L. V. D., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of machine learning research, 9(Nov), 2579-2605.
2004-2010面对模式分类与识别任务的流形学习算法被提出,并广泛应用于掌纹识别和人脸识别任务上(1)He, X., Cai, D., Liu, H., & Ma, W. Y. (2004, July). Locality preserving indexing for document representation. In Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 96-103). ACM.(2) He, X., Yan, S., Hu, Y., Niyogi, P., & Zhang, H. J. (2005). Face recognition using laplacianfaces. IEEE transactions on pattern analysis and machine intelligence, 27(3), 328-340.(3) Gui, J., Jia, W., Zhu, L., Wang, S. L., & Huang, D. S. (2010). Locality preserving discriminant projections for face and palmprint recognition. Neurocomputing, 73(13-15), 2696-2707.
2004-2010广泛应用于图像去噪,图像压缩,三维动画处理,运动图像检测领域(1)Gong, D., Sha, F., & Medioni, G. (2010, March). Locally linear denoising on image manifolds. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (pp. 265-272).(2) Ye, J., Janardan, R., & Li, Q. (2004, August). GPCA: an efficient dimension reduction scheme for image compression and retrieval. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 354-363). ACM.(3)Chang, H., & Yeung, D. Y. (2006). Robust locally linear embedding. Pattern recognition, 39(6), 1053-1065.
2010k-近邻分类与流形学习算法相结合,用于图像分类Ma, L., Crawford, M. M., & Tian, J. (2010). Local manifold learning-based $ k $-nearest-neighbor for hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing, 48(11), 4099-4109.
2014基于流形学习的特征提取被提出Lunga, D., Prasad, S., Crawford, M. M., & Ersoy, O. (2014). Manifold-learning-based feature extraction for classification of hyperspectral data: A review of advances in manifold learning. IEEE Signal Processing Magazine, 31(1), 55-66.

3. 发展分析

瓶颈

主要问题可以总结为以下几部分:

  1. 流形学习方法的参数选择问题。流形学习构建低维的空间是否成功很大程度上取决于临近数的选择,而至今为止还没有理论指导。
  2. 算法的性能评估问题。需要知道低维空间对高维空间的描述能力,肉眼观察很难给出一个客观的评价。
  3. 现阶段的流形学习多假设高维数据在一个连通的流形空间,这不符合一些模型,如蛋白质的互作用数据等。
  4. 对于保持全局特性的算法可以保证原始空间点之间的位置关系,即可以保证原始空间的临近点在低维空间仍然物理空间比较近,但这个算法的计算复杂度较高,因为需要考虑全局范围内的关系。保持局部特性的方法虽然计算复杂度很低,但是原始空间的远距离点的物理位置会发生变化。
  5. 此外,如何构建合理的低维空间的邻域也是存在的问题之一。

未来发展方向

  1. 针对参数选择问题,现阶段存在特征映射法和集合学习法,
  2. 如何对不同的流形学习算法在同一个数据集上给出定性、定量的评估,
  3. 自适应的邻域选择算法可以被考虑解决邻域选择的困难性问题,
  4. 现阶段的流形学习多是有监督的,如何构建无监督的也是未来的发展方向之一。

Contributor: Yilin Pan

相关人物
约书亚·布雷特·特南鲍姆
约书亚·布雷特·特南鲍姆
Joshua Brett Tenenbaum(约书亚·布雷特·特南鲍姆)是麻省理工学院认知科学与计算教授。他以对数学心理学和贝叶斯认知科学的贡献而闻名。 Tenenbaum之前曾在斯坦福大学任教,他于2010年10月至2011年1月担任Wasow Visiting Fellow。 Tenenbaum于1993年获得耶鲁大学物理学学士学位,并获得博士学位。 1999年开始任职麻省理工学院。他的工作主要集中在分析概率推理作为人类认知的引擎和作为发展机器学习的手段。
颜水成
颜水成
颜水成,新加坡国立大学副教授、360集团副总裁、人工智能研究院院长、第十三批国家 "千人计划"专家。颜水成的主要研究领域包括计算机视觉、深度学习、信息检索应用与多媒体分析。他带领的团队曾提出的“Network in Network” ,对深度学习产生了很大的推动力,同时他的团队开发的”Purine”是全球第一个开源的支持多机多GPU的深度学习系统。
Hongyuan Zha
Hongyuan Zha
John Langford
John Langford
杰弗里·辛顿
杰弗里·辛顿
杰弗里·埃弗里斯特·辛顿 FRS(英语:Geoffrey Everest Hinton)(1947年12月6日-)是一位英国出生的加拿大计算机学家和心理学家,以其在类神经网络方面的贡献闻名。辛顿是反向传播算法和对比散度算法的发明人之一,也是深度学习的积极推动者。
Lawrence K. Saul
Lawrence K. Saul
Laurens van der Maaten
Laurens van der Maaten
Mikhail Belkin
Mikhail Belkin
简介
相关人物