导读
对于一个高维空间中的球体，将这个球的外壳去掉薄薄的一层，这个球的体积还剩原来的多少？本文以这个问题为引子，尝试探讨机器学习中的维度灾难，欢迎同行指正或拍砖。
由于编辑器不支持公式编辑，公式较多的地方，用截图代替。
高维空间中的球体
人类生活在三维空间，大脑的直觉也以三维空间为参考系建立，到了高维空间这种直觉就不再起作用，甚至在潜意识里形成误导。回到导读中的高维球体的问题，我们将其转化为如下形式。
从上述例子中可以得到如下推论：
     在高维空间中，假如样本在空间中是均匀分布的，那么绝大多数的样本都稀疏地分布在球的表面附近。
高维空间中的局部方法
假设在特征空间中，基于目标点局部的观测，可以很好地预测出目标点的特性，此类方法称为局部方法。典型的局部方法有近邻方法和核方法，这两种方法在高维空间中都会遇到问题。
近邻方法（kNN：knearest neighbors）
该方法的思想是：对样本空间中一个新的输入x（称为目标点）进行预测时，先找到空间中距x最近的k个已知样本（称为k个近邻），并用这k个样本对应的输出来产生预测结果。如果是分类问题，就进行多数投票；如果是回归问题，就对k个输出进行平均。
上述逻辑似乎无懈可击，因为即便是高维空间也总能找到离目标点最近的k个样本吧？但其实kNN有一个容易被忽略的隐含假设，即k个最近的样本离目标点都不能太远。在低维空间中，这是很容易满足的；但在高维空间却并非如此。结合上面高维空间中球体的例子，来考虑下面的问题。
核方法
与近邻方法相对应的，是核方法。核方法是在目标点周围先选择一个半径固定的邻域，邻域里有几个样本算几个样本，用来估计目标点的值。显然，核方法在高维空间中遇到的问题是，在目标点的邻域里可能根本找不到样本点，因此无法做出有效估计。
高维空间的划分
有一些机器学习算法，有赖于对空间的划分。其主要思想是先将整个输入空间划分为足够小的子空间，小到每个子空间里的模式都足够简单，这样就可以在局部进行简单建模。以决策树为例，它通过自上而下的二分过程，将整个输入空间（或特征空间）划分为一系列的小区间（树的叶子节点），然后在这些小区间上直接用常量建模。另外一个例子是非参数密度估计，下面以此为例进行详细介绍。
非参数密度估计
假设，我们要对下图中某一个位置的点进行分类预测，判断其颜色。
非参数密度估计的想法很简单，首先将整个区间划分为如图的16个小区间，在每个小区间中属于某种颜色的概率用频率来代替。那么对于图中画×的点，预测如下：
最后会预测为红色。
这种方法的问题在于，随着空间维度的增加，子区间的个数指数增加。必须确保子区间中有样本点才能进行预测，那么需要的样本点也会指数增加。用图示例如下：
基于空间划分的方法，本质上是把整体模式的复杂性转移到了空间划分的复杂性上。因为指数是爆炸增长的，所需样本点的个数也会成爆炸趋势，且不说实际根本没有足够多的样本，即便有了这些样本，样本的存储也是个问题。因此，这种在低维空间中很朴素很好用的方法，在高维空间中就形成了灾难。
高维空间中的基函数方法
还记得函数的taylor展开式吗？这说明只要函数在某一点的各阶导数存在，就可以在该点附近用一组多项式函数来近似表达原函数。这种情况下，多项式函数就形成了一组基函数。类似的，傅里叶级数则是用三角函数来作为基。
从函数拟合的角度来理解机器学习模型，自然就有了机器学习中的基函数方法。我们在此以多项式基函数为例，说明基函数方法在高维空间中应用的困难。
多项式基函数方法
总结
从上面的这些例子可以看出，我们在低维空间中建立的很多直觉，无法直接类推到高维空间。而在机器学习领域，高维特征是相当常见的。随着特征空间维度的增加，样本空间分布的稀疏程度、模型的复杂度和算法的计算量一般都会指数增长，这给机器学习领域的采样、计算和存储都带来了很大的困难，我们称之为“维度灾难”。
如何理解维度灾难的本质呢？假设平均每个特征维度的变量，平均可以取N种不同的值（对连续值的情况，对应该维度上空间的N个划分），那么D个维度变量组合的结果就是N的D次方。这个组合数是呈指数增长的，这种现象被称为“组合爆炸”。也就是说，在特征空间中每增加一个维度，都需要在先前的基础上成倍地增加尝试所有组合方式对结果的影响。组合爆炸之时，也就形成了灾难。
对于高维空间给机器学习带来的这些“灾难性”的后果，我们又该如何应对呢？一般可以考虑以下思路：
降维：如果不同维度之间存在线性相关的关系，或者数据集在某些维度上相对于另外的维度方差很小，可以用PCA或LDA等方法先进行降维，然后转化到低维空间再进行处理。
优化计算：虽然空间维度理论上带来计算量的指数增长，但通常可以利用模型的实际特性来优化计算。比如，变量的对称性（如FM：Factorization Machine），或空间距离的三角不等式（如kNN）等。
选择更适用于高维空间的方法：比如，同样是基函数方法，不同于多项式基函数的是，MARS（Multivariate Adaptive Regression Splines）使用分段线性的基函数，可以将基函数的数量降低到2N*D（N为样本数量，D为特征空间维度）。
参考文献
《The Elements of  Statistical Learning: Data Mining, Inference, and Prediction》，Second Edition，Jerome Friedman
《Pattern Recognition and Machine Learning》，Bishop
往期精彩回顾
【年会刚过，你中奖了吗？】在线抽奖活动中如何实现中奖概率的自适应调整
罗素的理发师和奥卡姆剃刀互联网从业人必须知道的「用户行为数据收集系统」
用户行为数据收集系统--(2)客户端SDK设计
用户行为数据收集系统--(3)数据接收端设计
更多精彩内容
长按扫码可关注

继续阅读
阅读原文