27.1 度量学习亦称 距离度量学习 (distance metric learning)在机器学习中对高维数据进行降维的主要目的是希望找到一个合适的低维空间在此空间中进行学习(数据的分布特征、内在规律)比在原始空间的性能更好。事实上每个空间对应在样本属性上定义的一个距离度量而寻找合适的低维空间实质上就是在寻找(学习出)一个合适的距离度量这就是度量学习(metric learning)的基本动机。27.1.1 马氏距离 - 度量矩阵M之前定义的多种距离度量计算式都是固定的​、没有可调节的参数不能通过对样本数据的学习加以改善。例如两个d维样本xi和xj之间平方欧氏距离可写为dist-ed^2(xi, xj) |xi1-xj1|^2 |xi2-xj2|^2 ... |xid-xjd|^2假定不同属性的重要性不同可引入属性权重widist-wed^2(xi, xj) w1·|xi1-xj1|^2 w2·|xi2-xj2|^2 ... wd·|xid-xjd|^2 (xi-xj)ᵀW(xi-xj)其中wi≥0令Wdiag(wi)是一个对角(线)矩阵即(W)iiwi可通过学习确定。再往前走一步W的非对角(线)元素均为零这意味着坐标轴是正交的即属性之间无关但在现实问题中往往不是这样例如西瓜数据集的密度和含糖量两个属性是正相关其对应的坐标轴不再正交。为此将W替换为一个普通的半正定对称矩阵M就得到马氏距离(Mahalanobis distance) :dist-mah^2(xi, xj) (xi-xj)ᵀM(xi-xj)其中M亦称度量矩阵​注意为了保持距离非负且对称M必须是(半)正定对称矩阵即必有正交基 P 使得M能分解为M PPᵀ度量学习是对M进行学习。27.1.2 近邻成分分析 (NCA) - 优化目标对M进行学习 (即为新空间寻找一个合适的距离度量M一般作为参数去优化) 需要一个目标(载体)通过算法与样本集可对其进行优化。假设目标(载体)是提高近邻分类器的性能则可将M(即马氏距离表达式)应用到近邻分类器的性能指标即目标函数M即此目标函数的参数。算法运行样本集提高近邻分类器的性能的过程即优化其目标函数的参数即相应地求解M。以近邻成分分析(Neighbourhood Component Analysis简称NCA)[Goldberger et al.,2005]为例进行讨论 :近邻分类器在进行判别时通常使用多数投票法将其替换为概率投票法 -- 对于任意样本xj它对xi分类结果产生影响的程度即概率为pij exp(-(xi-xj)ᵀM(xi-xj)) / Σ(k)exp(-(xi-xk)ᵀM(xi-xk))当ij时pij最大。显然xj对xi分类结果的影响随着它们之间距离的增大而减小。若以留一法(LOO)正确率的最大化为目标则计算xi的留一法正确率即它被自身之外的样本正确分类的总概率为pi Σ(j∈Ωi)pij其中Ωi表示与xi属于相同类别的样本。全部样本集的留一法正确率为 :Σ(i1,m)pi Σ(i1,m)Σ(j∈Ωi)pij将pij概率表达式代入且因为MPPᵀ则NCA的优化目标为通过线性变换 Pᵀxi 将原始样本xi映射到新空间使样本之间马氏距离等价于在新空间中的欧氏距离假设样本xi∈Rn (n维向量)马氏距离矩阵 M∈R(n×n) 为半正定对称矩阵。根据谱定理M可分解为MPPᵀP∈R(n×k)其中krank(M)≤n若M满秩则knPᵀxi ∈ Rn (保持空间维度)否则knPᵀxi ∈ Rk (降维)当k1时Pᵀxi为标量。所以Pᵀxi的维度取决于M的秩k。求解即可得到近邻分类器(概率投票法) LOO(留一法)正确率最大化 的距离度量矩阵M。可使用随机梯度下降法求解27.2 随机梯度下降法求解 NCA 优化目标以下是使用随机梯度下降法求解 NCA 的优化目标 -- 近邻分类器(概率投票法) LOO(留一法)正确率最大化 的距离度量矩阵M通过Python编程实现的代码仅供参考。import numpy as np m 100 # 假设样本数量 d 10 # 假设特征维度 P np.random.randn(d, d) # 初始化P矩阵 learning_rate 0.01 iterations 10 # 生成模拟数据: X为样本特征集y为标签集 np.random.seed(42) X np.random.randn(m, d) y np.random.randint(0, 2, sizem) # 2个类别 # 计算xi与每个样本之间距离的集合 {||Pᵀxi-Pᵀxj||**2} (使用广播机制高效计算) def compute_distances(P, xi): X_trans X P.T # print(X_trans.shape) # (m,d) xi_trans xi P.T # print(xi_trans.shape) # (d,) a np.sum(X_trans**2, axis1) # print(a) # (m,) b 2*(xi_trans X_trans.T) # print(b) # (m,) c np.sum(xi_trans**2) # print(c) # 标量 dists a - b c return dists # 计算NCA优化目标中每个样本的损失值与更新参数(P)的梯度 def nca_loss_and_grad(P, X, y, i): xi X[i] dists compute_distances(P, xi) # 计算 Σ(j∈Ωi)exp(-||Pᵀxi-Pᵀxj||**2) mask (y y[i]) (np.arange(len(y)) ! i) # Ωi表示与xi属于相同类别的样本 n_i np.sum(np.exp(-dists[mask])) # print(n_i) # 计算 Σ(k)exp(-||Pᵀxi-Pᵀxk||**2) ≈ 1 d_i np.sum(np.exp(-dists)) # print(d_i) # 计算NCA优化目标(损失值) loss 1 - (n_i / d_i) # 计算梯度 grad np.zeros_like(P) for j in np.where(mask)[0]: xj X[j] diff xi - xj grad np.outer(diff, diff) P * (np.exp(-dists[j]) / d_i) return loss, grad # 随机梯度下降法 for epoch in range(iterations): print(f- {epoch1}/{iterations} epochs -) for i in range(m): loss, grad nca_loss_and_grad(P, X, y, i) print(f{i1}/{m} loss {loss}) # 每个样本的损失值 P - learning_rate * grad # 根据梯度更新参数P M P P.T print(M)针对不同目标不同的度量学习方法获得好的 半正定对称距离度量矩阵M若M是一个非满秩矩阵可通过对M进行特征值分解总能找到一组正交基其正交基数目为矩阵M的秩rank(M)小于原属性数d。于是度量学习的学习结果衍生出一个降维矩阵P∈Rd×rank(M) 即这组正交基M PPᵀ能用于降维之目的 Pᵀxi。