什么是“维数灾难”,为什么说引入核函数就避免“维数灾难”

  统计/机器学习 回归分析 开放问题    浏览次数:8098        分享
0

在文献中看到说如果要构造一个显式的映射将样本空间中的点映射到高维特征空间中,有可能会面临“维数灾难”的危险,所以想请问一下,机器学习当中所谓的“维数灾难”指的具体是什么呢?怎么样去理解这个概念呢?为什么说SVM通过构造核函数而无需显式地知道这个映射关系就避开了“维数灾难”呢?

 

CE_PAUL   2018-06-11 23:39



   1个回答 
6

Soft margin SVM的dual problem是(参考wiki):

其中$y_i$是分类标签1/-1,$c_i$是数据$x_i$重要性,如果$x_i$在分割平面的边缘(margin)外,$c_i=0$,也就是此点离分割平面太远,不参与测试时的计算。

SVM要计算数据点之间的内积inner product matrix $\phi(X) \cdot \phi(X')$。内积表示两个点的相似性,参考cosin similarity。内积的计算量正比于数据维度。

假设$n$为数据点数,$p$为原始数据维度,$p_1$为人造的新数据维度。

有两种办法计算两个点$X,X'$在高维空间的内积:

第一种是 先把数据显性的升维,$p\rightarrow p_1$,再计算内积。$\phi(X) \cdot \phi(X')$,

$\phi(X)$是升维操作。比如X是2维数据$X=[x_1,x_2]$,$\phi(X)=[\sqrt{\lambda_1}x_1,\sqrt{\lambda_2}x_2,\sqrt{\lambda_3}x_1^2,\sqrt{\lambda_4}x_2^2,\sqrt{\lambda_5}x_1x_2,\sqrt{\lambda_6}x_1^3,...]$

数据显性升维后,每一维都有个权重需要学习。升维后SVM训练计算量$\mathcal{O}(n^2p_1)$,但我觉得还称不上“维数灾难”。一般“维数灾难”要计算量正比于维度平方$p_1^2$。比如线性回归中要计算covariance matrix,它元素个数是维度平方。这才是“维数灾难”。应该说SVM有“数据点灾难”,应为完整的kernel matrix 是$n\times n$,$n$为数据点个数。

第二种是直接用非线性kernel代替高维的点击$K(X,X')=\phi(X) \cdot \phi(X')$,直接计算了两点的高维相似性。计算量$\mathcal{O}(n^2p)$。

----------------------------------------------------------------------

我先前错误地把“维数灾难”理解为计算量的提升,你说的应该是curse of dimensionality,也就是增加数据维数,有限的数据在高维空间更稀疏,反而分类的准确性下降。

我觉得不能简单看数据密度,应该看数据影响力的密度。

线性kernel的内积$X\cdot X'=|X||X'|cos(\theta)$, RBF kernel $K(X,X')=exp(-\frac {|X-X'|^2} {2\gamma})$

可以看到在线性kernel中X'对X内积的等高线是一个过原点的斜面。而RBF kernel中离训练数据X'越近,X'的影响力越大,在原始的低维空间中成以数据点为中心高斯分布。

import matplotlib.pyplot as plt
import numpy as np
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
delta=1
x = y = np.arange(-30.0, 30.01, delta)
X, Y = np.meshgrid(x, y)
v1=np.array([10,10])
Z=X*v1[0]+Y*v1[1]
# Z=X*v1[0]*1+Y*v1[1]*100+np.power(X,2)*np.power(v1[0],2)*-1+np.power(Y,2)*np.power(v1[1],2)*-1+np.multiply(X,Y)*v1[0]*v1[1]*0
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot_surface(X, Y, Z, rstride=8, cstride=8, alpha=0.3)
cset = ax.contour(X, Y, Z,zdir='z', cmap=cm.coolwarm)
plt.axis('equal')
plt.title('dot product contour')
plt.show()


Z_RBF=np.exp(-(np.power(X-v1[0],2)+np.power(Y-v1[1],2))/200)
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot_surface(X, Y, Z_RBF, rstride=8, cstride=8, alpha=0.3)
cset = ax.contour(X, Y, Z_RBF,zdir='z', cmap=cm.coolwarm)
plt.axis('equal')
plt.title('RBF kernel contour')
plt.show()



kernel的维数越低,数据的影响力(inner product)越均匀,所有数据综合后的影响力密度越均匀。而RBF kernel可看做是无限维的kernel,数据影响力更集中在训练数据周围,对于局部数据集中区域,“维数灾难”更不容易发生。



SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2018-07-10 01:53

了解,多谢多谢! - CE_PAUL   2018-07-17 20:29


  相关讨论

y取值有上下界限的回归问题

如何对大型线性回归进行并行计算?

线性回归是机器学习算法吗?

Sigmoid核函数是不是对新输入的需要预测的点的测量误差不敏感?

有序的分类变量的预测是回归问题还是多分类问题?

泊松回归有哪些应用场景?

拟合数据的Z-score规范化怎么进行操作?

训练样本中每个维度是否独立对回归结果的影响

如果迫使一个线性回归模型的截距为0,会有什么坏处吗?

泊松回归的公式是什么?

  随便看看

支持向量机(SVM)里的支持向量是什么意思

除了PCA,还有什么降维的方法?

为什么自然常数e等于阶乘的倒数的和?

pandas.DataFrame的index重新排列(从0开始)

print里的"%.2f"是什么意思?