机器算法验证 - 无免费午餐定理和 K-NN 一致性 - 吾爱随笔录

无免费午餐定理和 K-NN 一致性

机器算法验证 k-最近邻一致性

2022-03-07 01:03:59

在计算学习中，NFL 定理指出不存在通用学习器。对于每个学习算法，都有一个分布导致学习器输出一个具有大误差的假设，概率很高（尽管有一个低错误假设）。结论是，为了学习，必须限制假设类或分布。在他们的“模式识别的概率理论”一书中，Devroye 等人为 K 近邻学习器证明了以下定理：其中

Assume μ has a density. if k \to \infty and k / n \to 0 then for every ϵ > 0, there's N, s.t. for all n > N : P (R_{n} - R^{*} > ϵ) < 2 e x p (- C_{d} n ϵ^{2})

$\text{Assume } \mu \text{ has a density. if } k\to \infty \text{ and } k/n\to0 \\ \text{ then for every } \epsilon>0, \text{ there's } N, \text{ s.t.} \text{ for all } n>N : \\ P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2})$

R^{*}

$R^*$ 是贝叶斯最优规则的误差，是 K-NN 输出的真实误差（概率在大小为的训练集上），是实例空间上的概率度量和是一些常数，仅取决于欧几里得维数。因此，我们可以尽可能地接近最好的假设（不是某些受限类别中的最佳假设），而无需对分布做出任何假设。所以我想了解这个结果如何与 NFL 定理不矛盾？谢谢！

R_{n}

$R_n$

n

$n$

μ

$\mu$

R^{d}

$\mathbb{R}^d$

C_{d}

$C_d$

2个回答

我理解 NFL 定理的方式是，在每项任务中没有比其他学习算法更好的学习算法。然而，这不是一个明确的数学意义上的定理，它有一个证明，而是一个经验观察。

与您对 kNN 所说的类似，还有神经网络的通用逼近定理，它指出给定一个 2 层神经网络，我们可以用任意误差逼近任何函数。

现在，这怎么不打破NFL？它基本上表明您可以使用简单的 2 层 NN解决任何可以想象的问题。原因是，虽然理论上 NN 可以逼近任何东西，但实际上很难教它们逼近任何东西。这就是为什么对于某些任务，其他算法更可取。

一种更实用的 NFL 解释方法如下：

没有办法先验地确定哪种算法最适合给定任务。

这个问题的答案已经在问题的文本中：“假设有一个密度”，这意味着该陈述仅在分布绝对连续时才有效。因此 NFL 不适用于此处。 $\mu$ $\mu(X,Y)$

为了扩展这一点，NFL 定理说（参见 Devroye 书中的示例 7.2）：“给定任何分类规则，存在一个过度风险很大的分布。 ”直观地说，NFL 暗示归纳偏差是不可避免的，并且任何关于分类器性能的一致性结果必须伴随着对数据分布的某些假设。这些假设需要排除那些导致大量超额风险的“不良”分布。

局部平均方法（直方图、k-NN、内核）的所有一致性结果都需要分布的绝对连续性。有时这个假设是根据后验概率函数的连续性来表述的。这种限制是非常必要的，因为局部平均方法依赖于特征空间内“平滑”变化的标签。换句话说，关于某个距离度量接近的两个数据点应该具有也很有可能接近的标签。 $(X,Y)$ $\eta(x) = \mathbb{Pr}(Y=1\mid X)$

局部平均方法，例如最近邻法，利用测试点的邻域来决定其标签。因此，k-NN 的不良分布是条件分布函数非常粗糙并且邻居的标签不再有用的分布。NFL 定理是关于此类不良分布的存在，而一致性结果专门用于避免此类不良分布。 $\eta(X)$

其它你可能感兴趣的问题

上一篇计算复杂季节性的季节性指数下一篇高斯 VAE 的优化是否合适？