高纬度的局部方法

高维的数据相比于低纬度的来说，多了很多麻烦。s首先，高维取样中，同样比例的邻域往往需要边长较长的取样。为了方便分析，我们假设是在p维单位超立方体中取样。如图，取一个占整个单位体积比例为 $r$ 的样本，那么取样边长就是

e_{p} (r) = r^{\frac{1}{p}}

那么如果样本空间维度是10，取样大小占总样本的1%，那么每一条边的平均取样边长度就是 $e_{10} (0.01) \approx 0.63$ ，如果取样10%，平均取样边长就是 $e_{10} (0.1) \approx 0.8$ ，也就是说我们取样10%就需要覆盖每个维度的80%
其次，均匀分布的样本点一般都更加靠近边缘处。例如，从原点到最近数据点的一个中值距离是

d (p, N) = (1 - {\frac{1}{2}}^{\frac{1}{N}})^{\frac{1}{p}}

证明Ex2.3
还有一点就是取样样本密度与

N^{\frac{1}{p}}

成正比，也就是说单输入问题

N_{1} = 100

稠密度的样本，对于10输入问题来说，就需要

N_{10} = 100^{10}

的样本容量。构造一个均匀分布的例子，在

[- 1, 1]^{p}

中取1000个点，

Y

与

X

的真正关系是：

Y = f (X) = e^{- 8 ‖ X ‖}

检验

x_{0} = 0

使用1-最近邻规则预测

y_{0}

，对1000个样本取均值，考虑

f (0)

均方误差：

\begin{aligned} M S E (x_{0}) & = E [f (x_{0}) - {\hat{y}}_{0}]^{2} \\ = E [{\hat{y}}_{0} - E ({\hat{y}}_{0})]^{2} + [E ({\hat{y}}_{0}) - f (x_{0})]^{2} \\ = V a r ({\hat{y}}_{0}) + B i a s^{2} ({\hat{y}}_{0}) \end{aligned}

备注：由于

x_{0}

是确定的，所以

f (x_{0})

可以看作是常值，上式直接拆开计算比较一下就可以了。上式成为方差偏倚分解。
对于

p = 1

的情况，

x_{0}

的最近点非常接近0，但是随着维度的增加，最近点逐渐远离。1-NN,MSE,方差，平方偏倚与维度的关系如图。
机器学习理论笔记（4）

高维函数的复杂性往往也是这样指数增长，要达到低维函数相同的精度，训练的数据大小也是呈指数增长的。
如果我们知道 $Y$ 与 $X$ 之间是接近线性的:

Y = X^{T} β + ε

其中

ε \sim N (0, σ^{2})

我们可以写成这样

{\hat{y}}_{0} = x_{0}^{T} β + \sum_{i = 1}^{N} l_{i} (x_{0}) ε_{i}

这里

l_{i} (x_{0})

表示

X (X^{T} X)^{- 1} x_{0}

的第

i

个元素，因为这种情况下，最小二乘估计是无偏差的。

\begin{aligned} E P E (x_{0}) & = E_{y_{0} | x_{0}} E (y_{0} - {\hat{y}}_{0})^{2} \\ = V a r (y_{0} | x_{0}) + E [{\hat{y}}_{0} - E {\hat{y}}_{0}]^{2} + [E {\hat{y}}_{0} - x_{0}^{T} - x_{0}^{T} β] \\ = V a r (y_{0} | x_{0}) + V a r ({\hat{y}}_{0}) + B i a s^{2} ({\hat{y}}_{0}) \\ = σ^{2} + E x_{0}^{T} (X^{T} X)^{- 1} x_{0} σ^{2} + 0^{2} \end{aligned}

机器学习理论笔记（4）

高纬度的局部方法

相关推荐