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

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