S 马氏距离、度量矩阵与度量学习

• 对高维数据降维的目的是找到合适的低维空间，而实质上是在寻找一个合适的距离度量。

• 如果找到合适的距离度量：

  • 如果知道每两个点间的距离，就可以通过 MDS 方法降维后，再通过回归方法拟合出降维映射。
  • 如果距离度量是一个线性的映射，也许就可以立即求解降维映射。

• 比如「马氏距离 (Mahalanobis distance)」引入度量矩阵 $\boldsymbol M$（应是一个半正定对称矩阵）描述距离度量：

  $$ {\rm dist}_{\rm mah} (\boldsymbol x, \boldsymbol y) = \sqrt{ (\boldsymbol x - \boldsymbol y) ^{\rm T} \boldsymbol M (\boldsymbol x - \boldsymbol y)} $$

  1. 当 $\boldsymbol M =\boldsymbol I$ 时，距离就是普通向量内积 $d = \| \boldsymbol x - \boldsymbol y \|_2$。
  2. 当 $\boldsymbol M$ 为对角矩阵（$\boldsymbol M =\boldsymbol \Lambda$）时，可得 $d = \| \boldsymbol \Lambda^{\frac 12} (\boldsymbol x - \boldsymbol y) \|_2$，相当于为各个维度在算距离时加权，各维度上权为 $\sqrt{\lambda_i}$。
  3. 再引入非主对角线元素的话，这时可以正交分解 $\boldsymbol M = \boldsymbol P \boldsymbol \Lambda \boldsymbol P^{\rm T} = (\boldsymbol \Lambda^{\frac 12} \boldsymbol P^{\rm T})^{\rm T}(\boldsymbol \Lambda^{\frac 12} \boldsymbol P^{\rm T})$，其中 $\boldsymbol P$ 是正交矩阵。也就相当于 $d = \| \boldsymbol \Lambda^{\frac 12} \boldsymbol P^{\rm T} (\boldsymbol x - \boldsymbol y) \|_2$，对于距离差 $\boldsymbol x- \boldsymbol y$，先作一正交变换，再在各维度上加权。
  • 也记作 $\| \boldsymbol v \|_{\boldsymbol M} = \sqrt{ \boldsymbol v^{\rm T} \boldsymbol M \boldsymbol v }$。

• 度量学习就是在求解合适的度量矩阵 $\boldsymbol M$。

• 度量矩阵可以用于降维。如果求出一个能够有效解决问题的度量矩阵 $\boldsymbol M = \boldsymbol P \boldsymbol \Lambda \boldsymbol P^{\rm T}$，然后发现其有一些小特征值，那么也就说明经过正交变换后的空间 $\boldsymbol y = \boldsymbol P^{\rm T} \boldsymbol x$ 中部分维度上的距离并不重要（权重很小），兴许可以将这些维度去除。

A 近邻成分分析 (Neighbourhood Component Analysis, NCA)

A1 临近成分分析的预测方法

• 临近成分分析将度量矩阵嵌入到 近邻分类器的评价指标中，目标是通过学习 $\boldsymbol M$ 以提高近邻分类器的性能（无论是 k-近邻还是 ε-近邻）。

• 将近邻分类器的简单投票法转换为基于马氏距离的概率投票法。对于任意样本输入 $\boldsymbol x$ 及其邻域样本下标序列 $r_1^{(\boldsymbol x)}, r_2^{(\boldsymbol x)}, \cdots, r_{|R^{(\boldsymbol x)}|}^{(\boldsymbol x)}$，预测其为邻域中各样本 $\boldsymbol x^{(i)} , \ i \in R^{(\boldsymbol x)}$ 的概率为：

  $$ p_X(\boldsymbol x^{(i)}; \boldsymbol x) = \frac {\exp (-\| \boldsymbol x - \boldsymbol x^{(i)} \|{\boldsymbol M}^2)}{\sum{j \in R^{(\boldsymbol x)}}\exp (-\| \boldsymbol x - \boldsymbol x^{(j)} \|_{\boldsymbol M}^2)} $$

  • 对于每一个标签 $y \in {\mathcal Y}$，其预测概率为邻域中具有此标签的各样本的累积概率：

    $$ p_Y(y; \boldsymbol x) = \sum_{i \in R^{(\boldsymbol x)}} {\mathbb I} (f(\boldsymbol x^{(i)}) = y) \cdot p_X(\boldsymbol x^{(i)}; \boldsymbol x) $$

    • 其中 $f(\boldsymbol x)$ 为 $\boldsymbol x$ 对应的实际标签。

  • 最终选择累积概率最高的对应类别作为预测结果。

• 综上就可以通过已知的 $\boldsymbol M$ 来进行概率投票。关于 $\boldsymbol M$ 如何求解有多种方法，比如下面的最大化 LOO 正确率。

A2 最大化 LOO 正确率的方法

• 将留一法 (Leave-One-Out) 的正确率作为最大化目标，也就是说做 $|X|$ 次数据集划分，每次刨除一个元素，并用其他的元素预测它，得到的总体预测准确率 $A$。

  • 换句话说，只要保证对于每个样本输入 $\boldsymbol x^{(m)}$ 而言的邻域样本集合 $R^{(\boldsymbol x^{(m)})}$ 除去了它自身（通俗地说就是「自己不能给自己投票」），就是留一法中的预测。

  • 根据上述要求，总体预测准确率 $A(\boldsymbol M)$ 为：

    $$ A(\boldsymbol M) = \frac 1 {|X|} \sum_{m=1}^{|X|} p_Y(f(\boldsymbol x^{(m)}); \boldsymbol x^{(m)}) $$

  • 若预先从各个样本 $\boldsymbol x^{(m)}$ 的邻域下标集合 $R^{(\boldsymbol x^{(m)})}$ 中筛出和样本标签 $h(\boldsymbol x^{(m)})$ 相同的样本下标，即作 $\Omega^{(\boldsymbol x^{(m)})} = \{ k \ | \ k \in R^{(\boldsymbol x^{(m)})}, \ h(\boldsymbol x^{(k)})= h(\boldsymbol x^{(m)}) \}$，那么 $A(\boldsymbol M)$ 可以写作：

    $$ A(\boldsymbol M) = \frac 1 {|X|} \sum_{m=1}^{|X|} \sum_{k \in \Omega^{(\boldsymbol x^{(m)})}} \frac {\exp (-\| \boldsymbol x^{(m)} - \boldsymbol x^{(k)} \|{\boldsymbol M}^2)}{\sum{j \in R^{(\boldsymbol x)}}\exp (-\| \boldsymbol x^{(m)} - \boldsymbol x^{(j)} \|_{\boldsymbol M}^2)} $$

• 根据 $\| \boldsymbol x - \boldsymbol u \|_{\boldsymbol M}^2 = (\boldsymbol x - \boldsymbol u)^{\rm T} \boldsymbol M (\boldsymbol x - \boldsymbol u)$，优化目标就可以显式写作：

  $$ A(\boldsymbol M) = \frac 1 {|X|} \sum_{m=1}^{|X|} \sum_{k \in \Omega^{(\boldsymbol x^{(m)})}} \frac {\exp (-(\boldsymbol x^{(m)} - \boldsymbol x^{(k)})^{\rm T} \boldsymbol M (\boldsymbol x^{(m)} - \boldsymbol x^{(k)}))}{\sum_{j \in R^{(\boldsymbol x)}}\exp (-(\boldsymbol x^{(m)} - \boldsymbol x^{(j)})^{\rm T} \boldsymbol M (\boldsymbol x^{(m)} - \boldsymbol x^{(j)}))} $$

• 求解上式中较优的 $\boldsymbol M^* = \argmax_{\boldsymbol M \succeq 0} A(\boldsymbol M)$（$\boldsymbol M \succeq 0$ 表示 $\boldsymbol M$ 是半正定对称矩阵）可以通过随机梯度下降法。

B 其它度量学习方法

• 全局距离度量学习方法：可以基于先验知识产生「必连关系」「勿连关系」的约束，这些约束因为对所有样本同时发生作用，被称为「全局距离度量学习方法」。

  • 比如定义**「必连」约束集合** ${\mathcal M}$ 和**「勿连」约束集合** ${\mathcal C}$，就可以求解下面这个凸优化问题，直接获得 $\boldsymbol M$：

    $$ \min_{\boldsymbol M \succeq 0} \sum_{(\boldsymbol u, \boldsymbol v) \in {\mathcal M}} (\boldsymbol u - \boldsymbol v)^{\rm T} \boldsymbol M (\boldsymbol u - \boldsymbol v) \ \ \ {\rm where} \ \sum_{(\boldsymbol u, \boldsymbol v) \in {\mathcal C}} (\boldsymbol u - \boldsymbol v)^{\rm T} \boldsymbol M (\boldsymbol u - \boldsymbol v) \ge 1 $$

• 如果使用局部约束，就叫做「局部距离度量学习方法」，甚至有一些研究试图为每个样本产生最合适的距离度量。