不同的矩阵$\mathbf{M}$会得到不同的马氏距离，这就有一个寻找最优$\mathbf{M}$的问题。
可以使用近邻成分分析学习$\mathbf{M}$。

度量学习

在有趣的距离与范数中，我们讨论了距离，这里我们进一步地将欧氏距离推广成马氏距离，并讨论对其学习。

欧氏距离
$$\begin{array}{rl}{\mathrm{dist}}^2({\mathbf{x}}_i,{\mathbf{x}}_j)& =||{\mathbf{x}}_i,{\mathbf{x}}_j|{|}_2^2\\ & =({\mathbf{x}}_i,{\mathbf{x}}_j{)}^{\mathrm{T}}({\mathbf{x}}_i,{\mathbf{x}}_j)\\ & =({\mathbf{x}}_i,{\mathbf{x}}_j{)}^{\mathrm{T}}\mathbf{I}({\mathbf{x}}_i,{\mathbf{x}}_j)\end{array}\text{\hspace{1em}(10.116)}$$
其中，$\mathbf{I}$为单位矩阵，即对角线为1的对角矩阵。

由此想到将改单位矩阵为一般的对角矩阵又如何？这就是将欧氏距离推广成含参数$\mathbf{W}$的距离
$$\begin{array}{rl}{\mathrm{dist}}^2({\mathbf{x}}_i,{\mathbf{x}}_j)& =({\mathbf{x}}_i,{\mathbf{x}}_j{)}^{\mathrm{T}}\mathbf{W}({\mathbf{x}}_i,{\mathbf{x}}_j)\end{array}\text{\hspace{1em}(10.117)}$$
其中，$\mathbf{W}=\mathrm{diag}(w_1,w_2,\cdots ,w_d)=\mathrm{diag}(\mathbf{w})$，视向量$\mathbf{w}$为权重向量。 对角矩阵说明$d$维分量间是正交的，也即属性间无关。

若取消属性间无关的限制，可将对角矩阵$\mathbf{W}$替换成半正定对称矩阵$\mathbf{M}$，由矩阵理论，有正交基阵$\mathbf{P}$使得$\mathbf{M}=\mathbf{P}{\mathbf{P}}^{\mathrm{T}}$，则可定义新距离：
$$\begin{array}{rl}{d}_m^2({\mathbf{x}}_i,{\mathbf{x}}_j)& =({\mathbf{x}}_i,{\mathbf{x}}_j{)}^{\mathrm{T}}\mathbf{M}({\mathbf{x}}_i,{\mathbf{x}}_j)\\ & \stackrel{\mathrm{def}}{=}||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}_{\mathbf{M}}^2\end{array}\text{\hspace{1em}(10.118)}$$
称为马氏距离。 非负性、同一性、对称性显然，直递性证明如下：

因$\mathbf{M}$为半正定对称，故有分解：$\mathbf{M}=\mathbf{P}{\mathbf{P}}^{\mathrm{T}}$，其中，$\mathbf{P}$为正交基。 则
$$\begin{array}{rl}{\mathrm{dist}}_{\mathbf{M}}^2({\mathbf{x}}_i,{\mathbf{x}}_j)& =({\mathbf{x}}_i-{\mathbf{x}}_j)\mathbf{P}{\mathbf{P}}^{\mathrm{T}}({\mathbf{x}}_i-{\mathbf{x}}_j{)}^{\mathrm{T}}\\ & =\mathrm{tr}(({\mathbf{x}}_i-{\mathbf{x}}_j)\mathbf{P}{\mathbf{P}}^{\mathrm{T}}({\mathbf{x}}_i-{\mathbf{x}}_j{)}^{\mathrm{T}})\\ & =\mathrm{tr}({\mathbf{P}}^{\mathrm{T}}({\mathbf{x}}_i-{\mathbf{x}}_j{)}^{\mathrm{T}}({\mathbf{x}}_i-{\mathbf{x}}_j)\mathbf{P})\\ & =\mathrm{tr}({\mathbf{P}}^{\mathrm{T}}||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2\mathbf{P})\\ & =||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2\mathrm{tr}({\mathbf{P}}^{\mathrm{T}}\mathbf{P})\\ & ={\alpha }^2||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2\end{array}\text{\hspace{1em}(10.119)}$$
其中，由于$\mathbf{P}$为正交基，故可设$\mathrm{tr}({\mathbf{P}}^{\mathrm{T}}\mathbf{P})={\alpha }^2$。
在式(10.119)中，由欧氏距离$||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2$的直递性即可得到${\mathrm{dist}}_{\mathbf{M}}$的直递性。

显然，不同的矩阵$\mathbf{M}$会得到不同的马氏距离，这就有一个寻找最优$\mathbf{M}$的问题。

可以使用近邻成分分析学习$\mathbf{M}$。

（1）点${\mathbf{x}}_i$的近邻点${\mathbf{x}}_j$到它的距离用马氏距离，按“近墨者黑”的原则，距离越近影响越大。

易知“影响度”$p$与“距离”$d$是一个反比例关系，如图10.2所示。

显然，从图10.2知，当$d$越来越小时，$p$变得非常大，这也是我们不希望看到的，所以，希望有一个 “上界”。 将图10.2中的图像向左平移，则得到有界，如图10.3。

如图10.3所示，不管距离多近，影响度不超过1，然而图10.3中函数的数学性质不太好，找一个图像与它相像，但数学性质好的函数代替，即有图10.4。

比较图10.3与图10.4，将二者放到一起得到图10.5。

由图10.5知，二者趋势一致且在距离$d$足够小时二者非常接近，故这种替代是合理的。

（2）找到函数后，进一步优化

• 为避免开方，通常用距离的平方取代距离。
• 将影响度“概率化”（使其和为1），即$\sum (\cdot )=1$。

故${\mathbf{x}}_j$对${\mathbf{x}}_i$的影响度为
$$\begin{array}{r}\frac{{\mathrm{e}}^{-d_j^2}}{{\sum }_j{\mathrm{e}}^{-d_j^2}}\end{array}\text{\hspace{1em}(10.120)}$$
整理即得【西瓜书式(10.35)】的定义。

（3）投票。$k$近邻本来是考虑近邻的点才投票，但若采用式(10.120)【西瓜书式(10.35)】的概率投票，远距离的点影响甚微，故不 妨把投票权放宽到整个样本集，这样就省了是否是近邻的判断。

样本集$D$中，对一个具体的样本${\mathbf{x}}_i$而言，每个类别的样本子集对其都有一个总影响，设与${\mathbf{x}}_i$类别相同的样本${\mathbf{x}}_j$组成集合，设其下标集为${\Omega }_i$，且${\Omega }_i$中不含$i$（留一法），则预测${\mathbf{x}}_i$类别的正确率为
$$\begin{array}{r}{p}_i=\sum _{j\in {\Omega }_i}\text{（xj按式(10.120)投票）}\end{array}\text{\hspace{1em}(10.121)}$$
在整个样本集中，对每个样本都使用上述留一法得到其预测的正确率，让正确率之和${\sum }_{i=1}^m{p}_i$最大化，则得到NCA的优化目标【西瓜书式(10.38)】，可用随机梯度法求解。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：10.9 局部线性嵌入公式推导（更正书中的公式）
下一篇：11.1 子集搜索与评价（流水贪心，贪心法的优缺点）