Explaining the Success of Nearest Neighbor Methods in Prediction

解释预测中最近邻方法的成功

引言

最近邻 (Nearest Neighbor, NN) 方法是一种历史悠久且至今仍广受欢迎的预测技术，其核心思想是“相似的事物可能具有相似的属性”。本文旨在解释最近邻方法在理论和实践中取得成功的原因。

本文首先阐述了最近邻方法广受欢迎的四个关键原因：

  1. 定义相似性的灵活性：用户可以灵活选择特征空间和距离函数，使其能轻松适应特定应用场景，并与深度学习、集成学习等先进的表示学习和距离学习技术相结合。
  2. 计算效率：得益于多种高效的近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索算法，如局部敏感哈希 (Locality-Sensitive Hashing, LSH) 和随机树，NN方法能够扩展到现代应用中常见的大规模高维数据集。
  3. 非参数性：NN方法对数据的底层模型假设很少，不需预先设定复杂的数据结构，而是让数据本身直接驱动预测，这在探索结构未知的“大数据”时尤为重要。
  4. 可解释性：NN方法通过展示找到的“最近邻”来为其预测提供直观依据。这使得从业者可以诊断模型，理解预测结果，这在医疗等高风险领域至关重要。

在理论层面，本文侧重于非渐近 (nonasymptotic) 的统计保证，即在给定用户指定的误差容限下，需要多少训练数据和如何设置算法参数。传统的理论保证依赖于难以在实践中估计的量，如回归函数的平滑度或分类决策边界附近的概率密度。而近期研究则转向了更易于解释和验证的“聚类结构”，证明了在时间序列预测、协同过滤和图像分割等应用中，数据中的聚类结构是NN方法成功的关键。

本文的组织结构如下：

背景知识

本文首先定义了预测任务的基本框架。给定一个数据点，也称为特征向量 $X \in \mathcal{X}$（其中 $\mathcal{X}$ 是特征空间），目标是预测其标签 $Y \in \mathbb{R}$。假设我们有 $n$ 个独立同分布的训练数据对 $(X_1, Y_1), \dots, (X_n, Y_n)$。

回归

回归 (Regression) 任务的目标是估计条件期望函数 $\eta(x)$，也称为回归函数 (regression function)：

\[\eta(x) \triangleq \mathbb{E}[Y \mid X = x]\]

该函数给出了在给定特征 $X=x$ 时标签 $Y$ 的期望值。在最小化期望平方误差的意义上，$\eta(x)$ 是对 $Y$ 的最优预测。对于任何预测函数 $f(x)$，其期望平方误差满足：

\[\mathbb{E}[(Y - f(x))^2 \mid X = x] \ge \mathbb{E}[(Y - \eta(x))^2 \mid X = x]\]

右侧是无法消除的噪声方差，是任何预测器所能达到的误差下限。

由于真实的 $\eta(x)$ 未知，我们需要通过训练数据学习一个估计 $\hat{\eta}(x)$。评估 $\hat{\eta}(x)$ 的好坏通常使用偏差-方差分解 (Bias-Variance Decomposition)。对于一个测试点 $x$，估计器 $\hat{\eta}(x)$ 的期望平方预测误差可以分解为三部分：

  1. 噪声方差：数据本身固有的、不可避免的误差。
  2. 偏差的平方：$(\mathbb{E}_n[\hat{\eta}(x)] - \eta(x))^2$，度量了估计值的期望与真实值之间的差距。模型越简单，偏差通常越高。
  3. 方差：$\mathbb{E}_n [(\hat{\eta}(x) - \mathbb{E}_n[\hat{\eta}(x)])^2]$，度量了估计值在不同训练数据集下的波动性。模型越复杂，方差通常越高。 一个好的估计器需要在偏差和方差之间取得平衡，这即是著名的偏差-方差权衡 (bias-variance tradeoff)。

分类

在二元分类 (binary classification) 问题中，标签 $Y$ 只取两个值，如 ${0, 1}$。分类器的目标是学习一个函数 $\hat{Y}(x)$，将特征向量 $x$ 映射到其中一个类别。

在最小化错分率的意义下，最优的分类器是贝叶斯分类器 (Bayes classifier)：

\[\widehat{Y}_{\text{Bayes}}(x) = \underset{y \in \{0,1\}}{\operatorname{argmax}} \mathbb{P}(Y = y \mid X = x)\]

在二元设定下，回归函数 $\eta(x) = \mathbb{P}(Y=1 \mid X=x)$。因此，贝叶斯分类器可以表示为：

\[\widehat{Y}_{\text{Bayes}}(x) = \begin{cases} 1 & \text{if } \eta(x) \ge \frac{1}{2}, \\ 0 & \text{otherwise.} \end{cases}\]

这表明，最优分类器本质上是看回归函数 $\eta(x)$ 是否超过阈值 $1/2$。因此，一个自然的想法是先估计回归函数 $\hat{\eta}(x)$，然后将其“插入”上式来构造分类器，这种方法被称为插件分类器 (plug-in classifier)。本文讨论的最近邻分类器都属于此类。

最近邻与核回归

本文介绍了三种基于最近邻思想的回归方法，它们都依赖于一个预先选定的距离函数 $\rho(\cdot, \cdot)$。

分类体系

这三种方法依据其选择“邻居”的方式进行划分：

k-最近邻回归

k-NN回归 (k-nearest neighbor regression) 对一个新点 $x$ 的预测，是其在训练集中 $k$ 个最近邻居的标签的平均值。其估计函数为：

\[\widehat{\eta}_{k\text{-NN}}(x) = \frac{1}{k} \sum_{i=1}^{k} Y_{(i)}(x)\]

其中 $Y_{(i)}(x)$ 是 $x$ 的第 $i$ 个最近邻的标签。参数 $k$ 的选择是一个典型的偏差-方差权衡：

固定半径近邻回归

固定半径近邻回归 (Fixed-radius near neighbor regression) 寻找距离 $x$ 不超过某个阈值 $h > 0$ 的所有训练样本，并对其标签进行平均。其估计函数为：

\[\widehat{\eta}_{\text{NN}(h)}(x) = \begin{cases} \frac{\sum_{i=1}^{n} \mathbb{1}\{\rho(x, X_i) \le h\} Y_i}{\sum_{i=1}^{n} \mathbb{1}\{\rho(x, X_i) \le h\}} & \text{if den. > 0}, \\ 0 & \text{otherwise} \end{cases}\]

其中 $\mathbb{1}{\cdot}$ 是指示函数。参数 $h$ 的选择同样存在偏差-方差权衡。一个潜在问题是，在数据稀疏的区域，可能在半径 $h$ 内找不到任何训练样本。

核回归

核回归 (Kernel regression)，特别是Nadaraya-Watson估计，是对所有训练样本标签的加权平均，权重由一个核函数 $K$ 和带宽参数 $h$ 决定。距离越远的样本权重越小。其估计函数为：

\[\widehat{\eta}_K(x;h) = \begin{cases} \frac{\sum_{i=1}^n K\left(\frac{\rho(x,X_i)}{h}\right)Y_i}{\sum_{i=1}^n K\left(\frac{\rho(x,X_i)}{h}\right)} & \text{if den. > 0}, \\ 0 & \text{otherwise.} \end{cases}\]

固定半径近邻回归可以看作是使用箱式核 (boxcar kernel) $K(s) = \mathbb{1}{s \le 1}$ 的特例。带宽 $h$ 的选择也体现了偏差-方差权衡。

回归理论

本章的目标是为在通用度量空间 (metric space) 中的k-NN、固定半径NN和核回归方法，提供非渐近的理论保证。这些保证明确了需要多少训练数据以及如何选择算法参数（如 $k$ 或 $h$），才能使预测误差低于用户指定的容限。理论分析主要借鉴了 Chaudhuri 和 Dasgupta (2014) 以及 Gadat 等人 (2016) 在分类问题上的研究思路，并将其推广到回归设置。

分类理论

本章展示了如何将上一章的回归理论保证直接转化为分类问题的保证。此外，本文指出，分类问题可以依赖于比回归问题更弱的假设条件来获得理论保证。具体来说，本文解释了 Chaudhuri 和 Dasgupta (2014) 如何在k-NN分类中利用这些较弱的条件，并说明其核心思想同样适用于固定半径NN和核分类方法。

三个当代应用中的预测保证

本章分析了最近邻方法在三个看似无关、但理论基础相似的现代应用中的成功：时间序列预测、在线协同过滤和基于图像块的图像分割。在所有这三个应用中，聚类结构 (clustering structure) 是实现成功预测的关键。理论保证将训练数据量、预测精度与聚类数量及噪声水平联系起来。核心思想是，只要簇间分离度足够大，使得噪声不太可能导致样本被归入错误的簇，那么对于一个测试点，其最近邻样本将主要来自同一个簇，从而实现准确预测。

计算

本章概述了在实践中用于实现高效最近邻搜索的数据结构，这是将NN方法扩展到大规模数据集的关键。

分类体系

本章将最近邻搜索算法分为两大类：

自适应最近邻与远邻

本章最后探讨了NN方法的两个前沿方向。

  1. 自适应最近邻方法 (Adaptive Nearest Neighbor Methods)： 一些常见的机器学习方法，如决策树及其集成方法（随机森林、AdaBoost等），可以被重新解释为一种自适应的加权最近邻方法。这些方法在学习过程中隐式地学习了一个距离度量，从而自适应地确定哪些邻居是“重要”的。

  2. 远邻 (Far Away Neighbors)： 传统NN方法只关注“近”的样本。本章介绍了一些新兴的算法思想，它们能够利用“远邻”的信息。例如，在协同过滤中，某些算法可以通过分析与用户品味相差甚远的其他用户来进行“盲回归”，这为NN方法开辟了新的研究思路。