度量学习
机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。度量学习（metric learning）的基本动机就是直接尝试“学习”出一个合适的距离度量。
如果要对距离度量进行学习，必须有一个便于学习的距离度量的表达式，对两个\(d\)维样本\(\pmb{x}_i\)和\(\pmb{x}_j\)，它们之间的平方欧氏距离为 \[dist_{ed}^2(\pmb{x}_i, \pmb{x}_j) = ||\pmb{x}_i - \pmb{x}_j||_2^2 = dist_{ij,1}^2 + dist_{ij,2}^2 + \cdots + dist_{ij,d}^2\] 其中\(dist_{ij,k}\)表示\(\pmb{x}_i\)和\(\pmb{x}_j\)在第\(k\)维上的距离，若假定不同属性的重要性不同，则可引入属性权重\(\pmb{w}\)，得到 \[\begin{align}
dist_{wed}^2(\pmb{x}_i, \pmb{x}_j) &= ||\pmb{x}_i - \pmb{x}_j||^2 = w_1·dist_{ij,1}^2 + w_2·dist_{ij,2}^2 + \cdots + w_d·dist_{ij,d}^2 \nonumber \\
&= (\pmb{x}_i - \pmb{x}_j)^T \mathbf{W} (\pmb{x}_i - \pmb{x}_j) \nonumber
\end{align}\] 其中\(w_i \geq 0\)，\(\mathbf{W} = diag(\pmb{w})\)是一个对角矩阵，\((\mathbf{W}_{ii}) = w_i\)。
上式中的\(\mathbf{W}\)可通过学习确定，但是还可以更进一步：\(\mathbf{W}\)的非对角元素均为0，这意味着坐标轴是正交的，即属性之间无关；但是现实问题中往往不是这样，如人的身高和体重，它们显然正相关，其对应的坐标轴不再正交。为此，可将上式中的\(\mathbf{W}\)替换为一个普通的半正定对称矩阵\(\mathbf{M}\)，于是就得到了马氏距离（Mahalanobis distance）： \[dist_{mah}^2 (\pmb{x}_i, \pmb{x}_j) = (\pmb{x}_i - \pmb{x}_j)^T \mathbf{M} (\pmb{x}_i - \pmb{x}_j) = ||\pmb{x}_i - \pmb{x}_j||_{\mathbf{M}}^2\] 其中\(\mathbf{M}\)也称为"度量矩阵"，而度量学习则是对\(\mathbf{M}\)进行学习。注意到为了保持距离非负且对称，\(\mathbf{M}\)必须是（半）正定对称矩阵，即必有正交基\(\mathbf{P}\)使得\(\mathbf{M}\)可写成\(\mathbf{M} = \mathbf{P} \mathbf{P}^T\)。
标准马氏距离中\(\mathbf{M}\)是协方差矩阵的逆，即\(\mathbf{M} = \pmb{\Sigma}^{-1}\)，在度量学习中\(\mathbf{M}\)被赋予了更大的灵活性。
对\(\mathbf{M}\)的学习需要设置一个目标，假定我们希望提高近邻分类器的性能，则可将\(\mathbf{M}\)直接嵌入到近邻分类器的评价指标中去，通过优化该性能指标相应地求得\(\mathbf{M}\)。
下面以近邻成分分析（Neighbourhood Component Analysis，NCA）为例：
近邻分类器在进行判别时通常使用多数投票法，邻域中的每个样本投1票，邻域外的样本投0票。这里将其替换为概率投票法，对于任意样本\(\pmb{x}_j\)，它对\(\pmb{x}_i\)分类结果影响的概率为 \[p_{ij} = \frac{exp(- ||\pmb{x}_i - \pmb{x}_j||_{\mathbf{M}}^2)}{\sum_l exp(- ||\pmb{x}_i - \pmb{x}_j||_{\mathbf{M}}^2)}\] 当\(i=j\)时，\(p_{ij}\)最大。显然，\(\pmb{x}_j\)对\(\pmb{x}_i\)的影响随着它们之间距离的增大而减小。若以留一法正确率的最大化为目标，则可计算\(\pmb{x}_i\)的留一法正确率，即它被自身之外的所有样本正确分类的概率为 \[p_i = \sum_{j \in \Omega_i} p_{ij}\] 其中\(\Omega_i\)表示与\(\pmb{x}_i\)属于相同类别的样本的下标集合。于是，整个样本集上的留一法正确率为 \[\sum_{i=1}^m p_i = \sum_{i=1}^m \sum_{j \in \Omega_i} p_{ij}\] 带入概率计算公式，同时考虑\(\mathbf{M} = \mathbf{P} \mathbf{P}^T\)，则NCA的优化目标为 \[\min_{\mathbf{P}} \quad 1-\sum_{i=1}^m \sum_{j \in \Omega_i} \frac{exp(-||\mathbf{P}^T \pmb{x}_i - \mathbf{P}^T \pmb{x}_j||_2^2)}{\sum_l exp(-||\mathbf{P}^T \pmb{x}_i - \mathbf{P}^T \pmb{x}_l||_2^2}\] 求解上式即可得到最大化近邻分类器正确率的距离度量矩阵\(\mathbf{M}\)。
实际上，我们不仅能把错误率这样的监督学习目标作为度量学习的优化目标，还能在度量学习中引入领域知识。例如，若已知某些样本相似、某些样本不相似，则可定义“必连”约束集合\(\mathscr{M}\)与“勿连”约束集合\(\mathscr{C}\)，\((\pmb{x}_i, \pmb{x}_j) \in \mathscr{M}\)表示\(\pmb{x}_i\)与\(\pmb{x}_j\)相似，\((\pmb{x}_i, \pmb{x}_k) \in \mathscr{C}\)表示\(\pmb{x}_i\)和\(\pmb{x}_k\)不相似。显然，我们希望相似的样本之间距离较小，不相似的样本之间距离较大，于是可通过求解下面这个凸优化问题获得适当的度量矩阵\(\mathbf{M}\)： \[\begin{align} & \min_{\mathbf{M}} \quad \sum_{(\pmb{x}_i, \pmb{x}_j) \in \mathscr{M}} ||\pmb{x}_i - \pmb{x}_j||_{\mathbf{M}}^2 \nonumber \\ & s.t. \qquad \sum_{(\pmb{x}_i, \pmb{x}_j) \in \mathscr{C}} ||\pmb{x}_i - \pmb{x}_k||_{\mathbf{M}} \geq 1 \nonumber \\ & \qquad \qquad \mathbf{M} \succeq 0 \nonumber \end{align}\] 其中约束\(\mathbf{M} \succeq 0\)表明\(\mathbf{M}\)必须是半正定的。上式要求在不相似样本间的距离不小于1的前提下，使相似样本间的距离尽可能小。
不同的度量学习方法针对不同目标获得“好”的半正定对称距离度量矩阵\(\mathbf{M}\)，若\(\mathbf{M}\)是一个低秩矩阵，则通过对\(\mathbf{M}\)进行特征值分解，总能找到一组正交基，其正交基数目为矩阵\(\mathbf{M}\)的秩\(rank(\mathbf{M})\)，小于原属性数\(d\)。于是，度量学习学得的结果可衍生出一个降维矩阵\(\mathbf{P} \in \mathbf{R}^{d \times rank(\mathbf{M})}\)，可用于降维。