版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1454167
内容总结自花书《deep learning》Chapter5,由英文版翻译而来,英文版可以在其官网免费查阅。同时博主也发明中文翻译版的诸多错误和不细致的地方,建议阅读英文版。
近邻回归算法(nearest neighbor regression)模型简单地存储来自训练集的X\pmb{X}XXX和y\pmb{y}yyy,当被要求分类一个测试点时,模型查询训练集中与该点最近的项并且返回相关的目标(即label)。换句话说,y^=yi\hat{y}=y_iy^=yi当i=argmin∣∣Xi,:−x∣∣22i=argmin||\pmb{X_{i,:}-x}||_2^2i=argmin∣∣Xi,:−xXi,:−xXi,:−x∣∣22。算法也可以泛化到使用除L2L^2L2范数之外其他距离度量。如果该算法被允许通过平均Xi;:X_{i;:}Xi;: 中所有邻近的向量对应的yiy_iyi来打破必须是最近的关联,那么该算法会在任意回归数据集上达到最小的可能的训练误差(如果存在两个相同的输入对应不同的输出,训练误差有可能会大于0)。
更一般的,k-nearest neighbors是一类可以被应用于分类或者回归的技术。作为一个非参数学习算法,k-nearest neighbors不受限于固定数量的参数。我们通常认为k-nearest neighbors算法没有任何参数,而是实现了一个训练数据的简单函数。事实上,甚至不需要一个训练阶段或者学习过程。取而代之的是,在测试时,当我们需要为一个新的测试输入x\pmb{x}xxx产生一个输出yyy时,我们在训练集中找到k个与x\pmb{x}xxx最近的邻居,返回它们对应的kkk个yyy的平均值。这基本上对任何种类的能在yyy值上取平均的监督算法都有效。
作为一个非参数学习算法,k-nearest neighbors能够实现非常高的容量(capacity)。例如,我们有一个多分类任务,使用0-1损失函数来衡量性能。在这样的设定下,1-nearest neighbor在训练样本接近无穷大时收敛到2倍贝叶斯误差。多出来的贝叶斯误差来自随机在两个距离相同的邻居里选一个。当有无穷多训练数据时,所有测试点x\pmb{x}xxx都会有无穷多邻接距离为0。如果算法被允许在这些邻居上投票,而不是随机选择一个,则该过程会收敛到贝叶斯误差率。k-nearest neighbors的高容量使我们在给定一个大型训练集能够取得高准确度。它以高计算量实现这点,然而,给定一个小的有限的数据集,它会泛化得很差。
k-nearest neighbors的一个缺点是它不能学习到一个特征比另一个特征更有判别性。