【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.度量学习
在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。那么，为何不直接尝试“学习”出一个合适的距离度量呢？这就是度量学习（metric learning）的基本动机。
亦称“距离度量学习”（distance metric learning）。
欲对距离度量进行学习，必须有一个便于学习的距离度量表达形式。【机器学习基础】第三十四课：聚类之距离计算一文中给出了很多种距离度量的表达式，但它们都是“固定的”、没有可调节的参数，因此不能通过对数据样本的学习来加以改善。为此，我们先来做一个推广。
对两个$d$维样本$\mathbf{x}_i$和$\mathbf{x}_j$，它们之间的平方欧氏距离可写为：
\[\text{dist}_{\text{ed}}^2 (\mathbf{x}_i,\mathbf{x}_j)=\parallel \mathbf{x}_i - \mathbf{x}_j \parallel_2^2 = dist_{ij,1}^2+dist_{ij,2}^2+\cdots+dist_{ij,d}^2 \tag{1}\]其中$dist_{ij,k}$表示$\mathbf{x}_i$与$\mathbf{x}_j$在第$k$维上的距离。若假定不同属性的重要性不同，则可引入属性权重$\mathbf{w}$，得到：
\[\begin{align} \text{dist}_{\text{wed}}^2 (\mathbf{x}_i,\mathbf{x}_j) &=\parallel \mathbf{x}_i - \mathbf{x}_j \parallel_2^2 \\&=w_1 \cdot dist_{ij,1}^2+ w_2 \cdot dist_{ij,2}^2+\cdots+w_d \cdot dist_{ij,d}^2 \\&= \begin{bmatrix} dist_{ij,1} & dist_{ij,2} & \cdots & dist_{ij,d} \end{bmatrix} \begin{bmatrix} w_1 & 0 & \cdots & 0 \\ 0 & w_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & w_d \\ \end{bmatrix} \begin{bmatrix} dist_{ij,1} \\ dist_{ij,2} \\ \vdots \\ dist_{ij,d} \\ \end{bmatrix} \\&=(\mathbf{x}_i - \mathbf{x}_j)^T \mathbf{W} (\mathbf{x}_i - \mathbf{x}_j) \end{align} \tag{2}\]其中$w_i \geqslant 0$，$\mathbf{W} = \text{diag}(w)$是一个对角矩阵，$(\mathbf{W})_{ii}=w_{i}$。
式(2)中的$\mathbf{W}$可通过学习确定，但我们还能再往前走一步：$\mathbf{W}$的非对角元素均为零，这意味着坐标轴是正交的，即属性之间无关；但现实问题中往往不是这样，例如考虑西瓜的“重量”和“体积”这两个属性，它们显然是正相关的，其对应的坐标轴不再正交。为此，将式(2)中的$\mathbf{W}$替换为一个普通的半正定对称矩阵$\mathbf{M}$，于是就得到了马氏距离（Mahalanobis distance）：
\[\text{dist}_{\text{mah}}^2(\mathbf{x}_i,\mathbf{x}_j)=(\mathbf{x}_i - \mathbf{x}_j)^T \mathbf{M} (\mathbf{x}_i - \mathbf{x}_j) = \parallel \mathbf{x}_i - \mathbf{x}_j \parallel^2_{\mathbf{M}} \tag{3}\]标准马氏距离中$\mathbf{M}$是协方差矩阵的逆，即$\mathbf{M}=\Sigma^{-1}$；在度量学习中$\mathbf{M}$被赋予更大的灵活性。
其中$\mathbf{M}$亦称“度量矩阵”，而度量学习则是对$\mathbf{M}$进行学习。注意到为了保持距离非负且对称，$\mathbf{M}$必须是（半）正定对称矩阵，即必有正交基$\mathbf{P}$使得$\mathbf{M}$能写为$\mathbf{M}=\mathbf{PP}^T$。
对$\mathbf{M}$进行学习当然要设置一个目标。假定我们是希望提高近邻分类器的性能，则可将$\mathbf{M}$直接嵌入到近邻分类器的评价指标中去，通过优化该性能指标相应地求得$\mathbf{M}$。下面我们以近邻成分分析（Neighbourhood Component Analysis，简称NCA）为例进行讨论。
近邻分类器在进行判别时通常使用多数投票法，邻域中的每个样本投1票，邻域外的样本投0票。不妨将其替换为概率投票法。对于任意样本$\mathbf{x}_j$，它对$\mathbf{x}_i$分类结果影响的概率为：
\[p_{ij} = \frac{\text{exp}(-\parallel \mathbf{x}_i - \mathbf{x}_j \parallel^2_{\mathbf{M}})}{\sum_l \text{exp} (-\parallel \mathbf{x}_i - \mathbf{x}_l \parallel^2_{\mathbf{M}})} \tag{4}\]当$i=j$时，$p_{ij}$最大。显然，$\mathbf{x}_j$对$\mathbf{x}_i$的影响随着它们之间距离的增大而减小。若以留一法（LOO）正确率的最大化为目标，则可计算$\mathbf{x}_i$的留一法正确率，即它被自身之外的所有样本正确分类的概率为：
\[p_i=\sum_{j \in \Omega_i} p_{ij} \tag{5}\]其中$\Omega_i$表示与$\mathbf{x}_i$属于相同类别的样本的下标集合。于是，整个样本集上的留一法正确率为：
\[\sum_{i=1}^m p_i = \sum_{i=1}^m \sum_{j \in \Omega_i} p_{ij} \tag{6}\]将式(4)代入式(6)，再考虑到$\mathbf{M}=\mathbf{PP}^T$，则NCA的优化目标为：
\[\min \limits_{\mathbf{P}} 1-\sum_{i=1}^m \sum_{j \in \Omega_i} \frac{\text{exp} \left( -\parallel \mathbf{P}^T \mathbf{x}_i - \mathbf{P}^T \mathbf{x}_j \parallel_2^2 \right)}{\sum_l \text{exp} \left( -\parallel \mathbf{P}^T \mathbf{x}_i - \mathbf{P}^T \mathbf{x}_l \parallel_2^2 \right)} \tag{7}\]求解式(7)即可得到最大化近邻分类器LOO正确率的距离度量矩阵$\mathbf{M}$。
可用随机梯度下降法求解。
实际上，我们不仅能把错误率这样的监督学习目标作为度量学习的优化目标，还能在度量学习中引入领域知识。例如，若已知某些样本相似、某些样本不相似，则可定义“必连”（must-link）约束集合$\mathcal{M}$与“勿连”（cannot-link）约束集合$\mathcal{C}$，$(\mathbf{x}_i,\mathbf{x}_j) \in \mathcal{M}$表示$\mathbf{x}_i$与$\mathbf{x}_j$相似，$(\mathbf{x}_i,\mathbf{x}_k) \in \mathcal{C}$表示$\mathbf{x}_i$与$\mathbf{x}_k$不相似。显然，我们希望相似的样本之间距离较小，不相似的样本之间距离较大，于是可用过求解下面这个凸优化问题获得适当的度量矩阵$\mathbf{M}$：
\[\begin{align*} &\min \limits_{\mathbf{M}} \quad \sum_{(\mathbf{x}_i,\mathbf{x}_j) \in \mathcal{M}} \parallel \mathbf{x}_i - \mathbf{x}_j \parallel_{\mathbf{M}}^2 \\ & \begin{array} ss.t.& \sum_{(\mathbf{x}_i,\mathbf{x}_k) \in \mathcal{C}} \parallel \mathbf{x}_i - \mathbf{x}_k \parallel_{\mathbf{M}}^2 \geqslant 1, \\& \mathbf{M} \succeq 0, \\ \end{array} \end{align*} \tag{8}\]其中约束$\mathbf{M} \succeq 0$表明$\mathbf{M}$必须是半正定的。式(8)要求在不相似样本间的距离不小于1的前提下，使相似样本间的距离尽可能小。
不同的度量学习方法针对不同目标获得“好”的半正定对称距离度量矩阵$\mathbf{M}$，若$\mathbf{M}$是一个低秩矩阵，则通过对$\mathbf{M}$进行特征值分解，总能找到一组正交基，其正交基数目为矩阵$\mathbf{M}$的秩$\text{rank}(\mathbf{M})$，小于原属性数$d$。于是，度量学习学得的结果可衍生出一个降维矩阵$\mathbf{P} \in \mathbb{R}^{d \times \text{rank}(\mathbf{M})}$，能用于降维之目的。
度量学习自身通常并不要求学得的$\mathbf{M}$是低秩的。
低秩矩阵：如果$X$是一个$m$行$n$列的数值矩阵，$\text{rank}(X)$是$X$的秩，假如$\text{rank}(X)$远小于$m$和$n$，则我们称$X$是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。
