所谓维度，指的是一个系统中自由变量的个数。高维（high-dimensional）问题是指系统中变量个数很多，以至于传统方法无法直接求解的问题。高维问题是现代应用数学、统计学、机器学习等领域中的核心挑战。可以说，目前前沿的学术报告中，十个有八九个和高维问题相关。

高维问题在不同的领域中可以有不同的表述方式。使用逼近论的语言可以表述如下。

假设我们需要逼近一个定义在\(d\)维欧式空间的有界子集上的函数，假设该函数有\(k\)阶光滑性，可以理解为该函数存在可积的\(k\)阶偏导数。假设采样点数量为\(n\)，则此时最优的逼近速度为\(O(n^{-k/d})\)。这里最优的意义是对于任意的逼近方法，都存在一个满足上述条件的函数，使得逼近误差的阶不低于\(O(n^{-k/d})\)。

这个结果说明，当函数的光滑性固定的时候，如果维数增加，收敛速度会呈指数速度变慢。用一个不太确切的比方，对于\(d\)维的问题，如果要达到和1维问题相当的精度，需要的采样点个数为\(n^d\)。在实际中，这是令人难以接受的。我们称这个问题为维度灾难（curse of dimensionality）。

在当今世界中，随着传感、计算、储存等技术的发展，高维度问题比比皆是。在工程上，传统制造过程能够控制或测量的变量很少，但是在现代生产过程中，装有成百上千个传感器（sensor）的生产线比比皆是；在生物学上，随着基因检测技术的发展，我们已经能够在较低成本下实现全基因组的检测，由此观测到数以十万记的变量；在互联网上，大量不同来源的信息组成了一张巨大的社交网络，甚至可以将全世界所有的人联系在一起。

总的来说，高维度带来了前所未有的复杂性，其主要的挑战包括：如果有效的建模、如何有效的采样和分析、如何设计高效的算法。

下面简单介绍一下目前处理高维度问题的主要方法。

1）增加光滑性

从上面逼近的例子可以看出，最终的收敛速度取决于光滑性和维度的比值。所以，如果假设函数的光滑性可以随着维度的增长而增长，我们仍然可以期待一个不太差的收敛速度。换句话说，如果问题的维度非常高，我们必须假定目标函数非常光滑。在机器学习中，支持向量机（support vector machine）和神经网络（neural network）是利用光滑函数的典型例子；相反决策树（decision tree）则是不那么光滑的分类器。在应用数学中稀疏网格（sparse grids）是增加光滑性的典型方法，它考虑具有各向异性（anisotropic）光滑性的函数构成的空间。

2）特征提取

特征提取的主要思想是利用奇异值分解（SVD）。如果一个大矩阵主要的变异性（variation）可以被其少数几个较大的奇异值解释，我们就可以将一个高维问题化为一个维度不那么高的问题。当然，大矩阵的奇异值分解本身也是极为困难的事，实际中可能采用诸如贪婪法等近似方法。在应用数学中一个常见的方法为缩减基法（reduced basis method）。在统计中主成分分析（PCA）和因子分析（factor analysis）等方法是传统的，也是现在仍然广泛使用的方法。例如，深度学习（deep learning）中的限制的玻尔兹曼机（restricted Boltzmann machine）的构造就使用了主成分分析的原理。

3）稀疏性

稀疏性是指一种内生性（endogenous）的结构，在这个结构中绝大部分变量的取值都为0。一个简单的比方是：尽管世界上有70亿人，但是绝大多数人对我造成的直接影响等于0。压缩感知（compressive sensing）是应用数学中非常有名的方法。在统计学中相应的问题称为变量选择（variable selection），历史很长方法也很多。除了探讨自变量对因变量有无影响这一种稀疏模式以外，另一种常见的稀疏模式是考虑图上的稀疏性。另外在非线性问题中也可以类似的定义稀疏结构，神经网络和深度学习是利用非线性稀疏结构的典型例子。

高维问题从正式提出到现在已有近三十年的历史。总的来说，该领域已经取得了非常大的发展。然而由于实际问题越来越复杂，同时新的计算技术也在不断的涌现，所以需要研究的问题依然很多。另外，如果讲我上面提到的所有方法的理论与实践都掌握得比较好，在工业界应该可以找到一份高薪的工作（滑稽）

本帖转自超理论坛，原作者是小当。XXXXXXXXXXXXXXXXXub/XXXXXXXXp/2803