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

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

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

 

CE_PAUL   2018-06-11 23:39



   1个回答 
5

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,数据影响力更集中在训练数据周围,对于局部数据集中区域,“维数灾难”更不容易发生。



Zealing   2018-07-10 01:53

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


  相关主题

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

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

LS-SVM的核函数选取问题   1回答

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

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

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

在线性回归模型中存在epoch的说法吗?   2回答

与基于一般形式的支持向量回归相比,最小二乘支持向量回归更准确?   2回答

怎么处理真值大部分为0的回归问题   3回答

线性回归需要满足哪些基本前提假设   1回答

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

最小二乘线性回归的推导   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!