A k-近邻学习、降维与嵌入

A1 k-近邻学习 (K-Nearest Neighbor, kNN)

• 要求解测试样本时，在训练集中找到 k 个最近样本，然后用「投票法」/「平均法」等结合这些训练样本进行预测（可以基于距离远近进行加权投票或加权平均）。
• 是一种懒惰学习 (lazy learning)：训练阶段对训练样本不进行任何处理，训练时间开销为零；只对测试样本进行处理。
  • 反之，会在训练阶段对样本进行处理的方法被称为急切学习 (eager learning)。
• 事实上，如果样本独立同分布、对任意 $\boldsymbol x \in {\mathcal X}$ 和任意小正数 $\delta \in \R$，在 $\boldsymbol x$ 附近 $\delta$ 距离范围内总能找到一个训练样本（即训练样本的采样密度足够大），那么其泛化错误率不超过贝叶斯最优分类器错误率的两倍（证略）。
  • 然而，在现实任务中采样密度足够大的要求通常很难满足。
  • 尤其当数据越高维，数据样本越容易稀疏、同时计算距离的开销更大，这被称为「维数灾难 (curse of dimensionality)」。

A2 降维与嵌入 (embedding)

• 降维 (dimension reduction)：通过某种变换将原始高维空间转变为一个低维空间。
• 嵌入 (embedding)：高维数据中与学习任务密切相关的也许仅仅是某个低维分布，这个分布被称为高维空间的一个「嵌入」。
• 降维后低维空间的维数一般是事先指定的，当然也可以在不同的低维空间中用 k-近邻分类器（或其他开销较小的学习器）进行交叉验证，选取较好的维度数。

B Multiple Dimensional Scaling (MDS) 方法

• 「多维缩放」Multiple Dimensional Scaling (MDS) 方法 [Cox and Cox, 2001] 能够在低维空间中保持原始空间中样本间的距离。
• 令原始 $D$ 维空间中 $|X|$（$|X| < D$）个样本间的距离矩阵为 $\boldsymbol D \in \R^{|X|\times |X|}$，其中元素 $d_{ij} = \| \boldsymbol x_i - \boldsymbol x_j \|$ 。目标是获得原始样本矩阵 $\boldsymbol X \in \R^{D \times |X|}$ 在 $S \ (S \le D)$ 维空间的一个表示 $\boldsymbol Y \in \R^{S \times |X|}$，并且 $\| \boldsymbol y_i - \boldsymbol y_j \| = d_{ij}$。
• 其实此方法也能同样处理 $D > |X|$ 的情况。

B1 求解降维后样本的内积矩阵

• 先作降维后样本的内积矩阵 $\boldsymbol B = \boldsymbol Y^{\rm T} \boldsymbol Y \in \R^{|X| \times |X|}$，$b_{ij} = \boldsymbol y_i^{\rm T} \boldsymbol y_j$。
  • 求得 $\boldsymbol B$ 之后就可以还原得到 $\boldsymbol Y$（下一部分的事情）。这里先求从距离矩阵 $\boldsymbol D$ 求得 $\boldsymbol B$ 的方法。$\boldsymbol B$ 显然是一个对称矩阵。
  • 结论是，作：
    • $d_{i\cdot}^2 = \frac 1 {|X|} \sum_{j=1}^{|X|} d_{ij}^2$。
    • $d_{\cdot j}^2 = \frac 1 {|X|} \sum_{i=1}^{|X|} d_{ij}^2$。
    • $d_{\cdot \cdot}^2 = \frac 1 {|X|^2} \sum_{i=1}^{|X|} \sum_{j=1}^{|X|} d_{ij}^2$。
  • 可以得到 $b_{ij} = -\frac 12 (d_{ij}^2 - d_{i \cdot}^2 - d_{\cdot j}^2 + d_{\cdot \cdot}^2)$。

证明：

• 令降维后的 $\boldsymbol Y$ 被中心化，即 $\sum_{i=1}^{|X|} \boldsymbol y_i = \boldsymbol 0$。
  • 可以得知 $\sum_{i=1}^{|X|} b_{ij} = (\sum_{i=1}^{|X|} \boldsymbol y_i)^{\rm T} \boldsymbol y_j =0$，据对称性又有 $\sum_{j=1}^{|X|} b_{ij} = 0$。
• $\sum_{i=1}^{|X|} b_{ii} = {\rm tr} \ \boldsymbol B$，其本质是 ${\rm tr} \ \boldsymbol B = \sum_{i=1}^{|X|} \| \boldsymbol y_i \|^2$。
• 对距离作展开可得 $d_{ij}^2 = \|\boldsymbol y_i \|^2 + \| \boldsymbol y_j \|^2 -2 \boldsymbol y_i^{\rm T} \boldsymbol y_j = b_{ii} + b_{jj} - 2 b_{ij}$。可得如下公式：
  • $|X| d_{\cdot j}^2 = \sum_{i=1}^{|X|} d_{ij}^2 = \sum_{i=1}^{|X|} b_{ii} + \sum_{i=1}^{|X|} b_{jj}- 2 \sum_{i=1}^{|X|} b_{ij} = {\rm tr} \ \boldsymbol B + |X|b_{jj} - 0$。
  • $|X| d_{i\cdot}^2 = \sum_{j=1}^{|X|} d_{ij}^2 = \sum_{j=1}^{|X|} b_{ii} + \sum_{j=1}^{|X|} b_{jj}- 2 \sum_{j=1}^{|X|} b_{ij} = |X|b_{ii} + {\rm tr} \ \boldsymbol B - 0$。
  • $|X|^2 d_{\cdot \cdot}^2 = \sum_{i=1}^{|X|} \sum_{j=1}^{|X|} d_{ij}^2 = |X|\sum_{i=1}^{|X|} b_{ii} + \sum_{i=1}^{|X|} {\rm tr} \ \boldsymbol B = 2|X| {\rm tr} \ \boldsymbol B$。
• 观察距离展开式缺的就是一个 $b_{ii} + b_{jj}$，而上述公式可以构成 $b_{ii} + b_{jj} = d_{i \cdot}^2 + d_{\cdot j}^2 - d_{\cdot \cdot}^2$。
  • 代入距离展开式得 $d_{ij}^2 = d_{i \cdot}^2 + d_{\cdot j}^2 - d_{\cdot \cdot}^2 - 2b_{ij}$。原式得证。

B2 从内积矩阵还原降维后的样本矩阵

• 求得内积矩阵 $\boldsymbol B$ 之后，接下来就可以求 $\boldsymbol Y$。两者间的关系是 $\boldsymbol B = \boldsymbol Y^{\rm T} \boldsymbol Y$。

• 对对称矩阵 $\boldsymbol B$ 作正交分解 $\boldsymbol B = \boldsymbol V \boldsymbol \Lambda \boldsymbol V^{\rm T}$，其中 $\boldsymbol \Lambda$ 是各特征值构成的对角矩阵。于是：

  $$ \boldsymbol B = (\boldsymbol \Lambda^{\frac 12 } \boldsymbol V^{\rm T})^{\rm T} (\boldsymbol \Lambda^{\frac 12 } \boldsymbol V^{\rm T}), \ \ \ \ \ \boldsymbol Y = \boldsymbol \Lambda^{\frac 12 } \boldsymbol V^{\rm T} $$

  • 其中虽然 $\boldsymbol \Lambda \in \R ^{|X| \times |X|}$，但是 $\boldsymbol B$ 的非零特征值数目应不会超过 $D$ 个。

    因为 $\boldsymbol X \in \R^{D \times |X|}$，显然 ${\rm r} (\boldsymbol Y) \le {\rm r} (\boldsymbol X) \le D$，又 $\boldsymbol B = \boldsymbol Y^{\rm T} \boldsymbol Y$，故 ${\rm r}(\boldsymbol B) \le D$。