扩展

度量学习的目的是在样本上学习距离度量函数. 距离度量函数必须服从4个公理非负性，对称性，次可加性及不可分与同一性.在实践中，度量学习算法一般忽略了不可分与同一性并学习伪度量.

首先，了解伪度量空间.伪度量空间是度量空间的推广，一个伪度量空间\((X,d)\)是有非负实值函数组成的集合\(X\)，若\(d:X \times X\mathbb{\rightarrow R \geq}0\)，对于\(\forall x,y,z \in X\)满足公式（1-9）中条件则可称为伪度量.

\[{d(x,x) = 0
}{d(x,y) = d(y,x)
}\]

与度量空间不同，伪度量空间中的点可能不满足不可分与同一性，也就是说如果\(d(x,y) = 0\)可能\(x \neq y\).

假设有集合\(\mathcal{S} = \left( x_{i}|x_{i} \subseteq \mathbb{R}^{n} \right)\)，给出了成对相似矩阵的定义，它是两两相似点的集合

\(S:\quad\left( x_{i},x_{j} \right) \in \mathcal{S}\quad\ (x_{i}\ 与\ x_{j}相似)\)

同理给出成对不相似矩阵\(D\)的定义，它是两两不相似点的集合

\(D:\left( x_{i},x_{j} \right) \in S\quad\ (x_{i}\ 与\ x_{j}不相似)\)

我们通过学习距离度量矩阵来解决相似点之间的距离度量\(d(x,y)\)

\(d(x,y) = d_{A}(x,y) = \| x – y\|_{A} = \sqrt{(x – y)^{T}A(x – y)}\)

为了确保公式满足度量距离函数的非负性和次可加性，我们要求\(A\)是正半正定的矩阵，即\(A \succcurlyeq 0\).如果\(A = I_{0}\)，那么就是采用欧氏距离度量.

提出优化问题

定义成对相似点\(\left( x_{i},x_{j} \right)\)之间的最小平方距离\(\ {\min{}_{A}}\sum_{\left( x_{i},x_{j} \right) \in \mathcal{S}}^{}\left\| x_{i} – x_{j} \right\|_{A}^{2}\).如果对\(A\)不加以限制，那么当\(A = 0\)时，虽然可以让相似点\(d_{A}(x_{i},x_{j}),(x_{i},x_{j} \in S)\)等于零，但是这样做不相似的成对点\(d_{A}(x_{i},x_{j}),(x_{i},x_{j} \in D)\)也将变为0，所以我们应该添加约束条件防止该问题发生.因此得出优化问题如下

\[\begin{array} { c l } { \min _ { A } } & { \sum _ { \left( x _ { i } , x _ { j } \right) \in \mathcal { S } } \left\| x _ { i } – x _ { j } \right\| _ { A } ^ { 2 } } \\ { \text { s.t. } } & { \sum _ { \left( x _ { i } , x _ { j } \right) \in \mathcal { D } } \left\| x _ { i } – x _ { j } \right\| _ { A } \geq 1} \\ { } & { A \succeq 0 } \end{array}\]

公式\(\sum_{\left( x_{i},x_{j} \right) \in \mathcal{D}}^{}\left\| x_{i} – x_{j} \right\|_{A} \geq 1\)中，右边的常数1的更改成任意常数\(c\)，若将1改为常数\(c\)只会让学习的度量矩阵从\(A\)线性变换到\(c^{2}A\).此外，该优化问题是求解半正定矩阵\(A\)，两个约束为凸约束.因此，对于此类凸优化问题，我们能够使用局部最小来求解它.

计算\(A\)的对角元素

我们可以使用Newton-Raphson（牛顿拉夫森）来推导学习半定阵\(A\)对角线的算法.定义

\(g(A) = g\left( A_{11},\ldots,A_{{nn}} \right) = \sum_{\left( x_{i},x_{j} \right) \in \mathcal{S}}^{}\left\| x_{i} – x_{j} \right\|_{A}^{2} – \log\left( \sum_{\left( x_{i},x_{j} \right) \in \mathcal{D}}^{}\left\| x_{i} – x_{j} \right\|_{A} \right)\)

易证\(\min g(A)\)与\(A \succcurlyeq 0\)目标优化等效，解为线性相关.因此可以使用\(Newton-Raphson\)能够有效地优化问题.

\(g(A) = g\left( A_{11},\ldots,A_{\text{nn}} \right) = \sum_{S}^{}\left\| x_{i} – x_{j} \right\|_{A}^{2} – \ln\left( \sum_{D}^{}\left\| x_{i} – x_{j} \right\|_{A} \right)\)

设

\(\begin{matrix} x_{\text{ij}} = \left. \ \left( x_{i1} – x_{j1} \right)^{2},\ldots,\left( x_{\text{id}} – x_{\text{jd}} \right)^{2} \right)\rbrack^{T} \\ A = \left\lbrack A_{11},\ldots,A_{\text{dd}} \right\rbrack \\ \end{matrix}\)

然后

\(\begin{matrix} \left\| x_{i} – x_{j} \right\|_{A}^{2} = \left( x_{i} – x_{j} \right)^{T}A\left( x_{i} – x_{j} \right) = x_{\text{ij}}^{T}A \\ g(A) = \sum_{S}^{}x_{\text{ij}}^{T}A – \ln\left( \sum_{D}^{}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}} \right) \\ \end{matrix}\)

得出

\(\begin{matrix} g^{‘}(A) = \left( \sum_{S}^{}x_{\text{ij}}^{T}A – \ln\left( \sum_{D}^{}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}} \right) \right)^{‘} \\ = \sum_{S}^{}x_{\text{ij}} – \frac{1}{\sum_{D}^{}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}}}\sum_{D}^{}\frac{1}{2}\left( x_{\text{ij}}^{T}A \right)^{- \frac{1}{2}}x_{\text{ij}} \\ \end{matrix}\)

\(g^{‘}(A)\)是一个与\(A\)大小相同的矩阵. 在这种情况下，我们想使用NewtonRaphson方法得到\(A\)，所以我们需要推导出更新中使用的Hessian矩阵\(g^{”}(A)\)规则.推导过程

\(\begin{matrix} g^{”}(A) = \partial g^{‘}(A)^{T}/\partial A \\ = \partial\left\lbrack – \left\lbrack \sum_{D}^{}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}} \right\rbrack^{- 1}\sum_{D}^{}\frac{1}{2}\left( x_{\text{ij}}^{T}A \right)^{- \frac{1}{2}}x_{\text{ij}}^{T} \right\rbrack/\partial A \\ = \left\lbrack \sum_{D}^{}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}} \right\rbrack\rbrack^{- 2}\sum_{D}^{}\frac{1}{2}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}}x_{\text{ij}}\sum_{D}^{}\frac{1}{2}\left( x_{\text{ij}}^{T}A \right)^{- \frac{1}{2}}x_{\text{ij}}^{T} – \\ \left\lbrack \sum_{D}^{}\left( x_{\text{ij}}^{T}A \right)^{\frac{1}{2}} \right\rbrack^{- 1}\sum_{D}^{} – \frac{1}{4}\left( x_{\text{ij}}^{T}A \right)^{- \frac{3}{2}}x_{\text{ij}}x_{\text{ij}}^{T} \\ \end{matrix}\) （1-23）

计算半正定阵\(A\)

在计算\(A\)的时候，约束\(A \succcurlyeq 0\)用牛顿拉弗森进行迭代反转Hessian时间复杂度过大.

所以提出对偶问题

\[\begin{array} { l l } { \max _ { A } } & { g ( A ) = \sum _ { \left( x , x _ { j } \right) \in \mathcal { D } } \left\| x _ { i } , x _ { j } \right\| _ { A } } \\ { \text { s.t. } } & { f ( A ) = \sum _ { \left( x _ { i } , x _ { j } \right) \in \mathcal { S } } \left\| x _ { i } , x _ { j } \right\| _ { A } ^ { 2 } \leq 1 } \\ { } & { A \succeq 0 } \end{array}\]

使用梯度上升和迭代投影来优化求解. 为了确保 \(A \succeq 0\)，如果对角元素 \(A_{ii}\) 是非负的，那么用 \(H ^ { – 1 } \nabla g\) 替换牛顿更新 \(\alpha H ^ { – 1 } \nabla g\)，其中 \(\alpha\) 是通过优化的步长参数。

求解\(A\)优化算法如下

Iterate
Iterate
\(\begin{array} { l } { A : = \arg \min _ { A ^ { \prime } } \left\{ \left\| A ^ { \prime } – A \right\| _ { F } : A ^ { \prime } \in C _ { 1 } \right\} } \\ { A : = \arg \min _ { A ^ { \prime } } \left\{ \left. \left| A ^ { \prime } – A \right| \right| _ { F } : A ^ { \prime } \in C _ { 2 } \right\} } \end{array}\)
until（条件：半定阵 \(A\) 收敛）
\(A : = A + \alpha \left( \nabla _ { A } g ( A ) \right) _ { \perp } \nabla _ { A } f\)
until （迭代收敛)

原文: Xing EP,Ng AY,Jordan MI, et al.Distance Metric Learning,with Application to Clustering with Side-information[C]//International Conference on Neural Information Processing Systems, 2002.
扩展阅读: https://metric-learn.github.io/metric-learn
GitHub : python版本 https://github.com/JasonYee/Distance-metric-learning
Matlab版本 https://github.com/arlenlee/Metric-Learning
补充：
Python版本简介见 https://github.com/JasonYee/Distance-metric-learning

matlab调用简介
X：数据
S：相似性约束（以成对相似性矩阵的形式）
D：相异性约束（以成对相异矩阵的形式）
A：初始距离度量矩阵
w：来自类似数据的权重向量（见论文）
t：约束C1的上限（成对距离的总和）
maxiter：最大迭代次数
iter_projection_new2(X, S, D, A, w, t, maxiter)