在机器学习中，对高维数据进行降维的主要目的是但愿找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好．事实上，每一个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量．那么，为什么不直接尝试“ 学习” 出一个合适的距离度量呢？这就是度量学习(metric learning)的基本动机． 在数据分类或者聚类中咱们应该让类似数据的距离尽量地接近，不类似的距离尽量地疏远，这就是距离度量学习的目的.html
度量学习的目的是在样本上学习距离度量函数. 距离度量函数必须服从4个公理非负性，对称性，次可加性及不可分与同一性.在实践中，度量学习算法通常忽略了不可分与同一性并学习伪度量.python
首先，了解伪度量空间.伪度量空间是度量空间的推广，一个伪度量空间\((X,d)\)是有非负实值函数组成的集合\(X\)，若\(d:X \times X\mathbb{\rightarrow R \geq}0\)，对于\(\forall x,y,z \in X\)知足条件则可称为伪度量.git
\[{d(x,x) = 0 }\]
\[{d(x,y) = d(y,x) }\]github
与度量空间不一样，伪度量空间中的点可能不知足不可分与同一性，也就是说若是\(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}类似)\)curl
同理给出成对不类似矩阵\(D\)的定义，它是两两不类似点的集合机器学习
\(D:\left( x_{i},x_{j} \right) \in S\quad\ (x_{i}\ 与\ x_{j}不类似)\)ide
咱们经过学习距离度量矩阵来解决类似点之间的距离度量\(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\)，两个约束为凸约束.所以，对于此类凸优化问题，咱们可以使用局部最小来求解它.
咱们可使用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}\)
在计算\(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)
欢迎转载，请注明出处和做者。
做者：Arlen Lee
出处：http://www.noobyard.com/article/p-gpomdqzq-md.html