论文部分内容阅读
在当前的信息时代中，大量的高维数，复杂结构数据不断涌现，而且对机器自动分析和处理数据的要求越来越高。人们希望机器可以处理各种复杂的任务。而传统机器学习中，以二分类为主的预测范式，已经越来越难以满足各种复杂多样的需求。探询新的机器学习范式，是目前机器学习研究中的一项重要任务。而基于相似度/不相似度的匹配范式有认知心理学的基础，符合人类认知的特点，并且有广泛的适用范围。因此，对匹配范式的研究，已经越来越受到人们的重视。
从机器学习的观点来看，匹配范式中相似度/不相似度的学习是机器学习需要研究的任务。而在各种不相似度函数中，度量是具有很好数学性质的一类。本文对如何学习一类可以等距嵌入欧氏空间的度量进行了较为系统的研究。我们称这类度量为欧氏度量，但它不同于输入空间的欧氏度量。我们指出，学习欧氏度量等价于学习对称半正定核。通过本文证明的表示定理，说明了欧氏度量等价于对输入空间进行一定的非线性变换后得到的度量。并由此提出了完整的欧氏度量学习框架。此框架区分了度量学习的两个部分，即先验度量和训练约束。文中讨论了这两个部分的表示方式。并通过表示定理，提供统一的方式将训练集上学得的度量推广到全空间。以往的一大类监督，非监督，半监督的非线性维数约简算法均可以纳入框架。依此观点，对前人在非线性维数约简及度量学习方面的工作进行了综述。
根据欧氏度量学习框架，提出了三个欧氏度量学习算法。第一个算法由于使用一个特殊的损失函数，而可利用谱方法求解。即，可将其描述为某个矩阵的特征值问题，而矩阵的某些特征向量即为其解。在使用图Laplacian诱导的度量做为先验度量时，此特征值问题可以变为稀疏特征值问题。因此利用Krylov子空间方法求解此问题，可使方法能够处理大规模的数据集。当标签样本较少时，简单的损失函数可以导致学得的度量出现异常的扭曲。由此，本文提出了一种平滑化技术，对损失函数进行平滑化，解决了这一问题。
之后，通过引入Bregman divergence作为正则化项，将任意凸二阶可微损失函数意义下的欧氏度量学习和核学习问题表示为一个无约束的优化问题，其中，整个核矩阵为优化变量。由于优化变量的个数是样本数的平方级，通常的牛顿法和拟牛顿法难以应用。本文提出了两种方法求解这一问题。第一种方法称为再开始的半牛顿法，它利用Hessian算子中的部分信息，计算一种特殊的半牛顿步进行迭代。第二种方法是信赖域截断牛顿法。它通过对Hessian算子方程进行提前终止的共轭梯度法寻找牛顿步的近似，并利用此近似进行信赖域迭代。这两种方法可在样本数立方级的时间内解决度量学习问题。信赖域截断牛顿法的收敛速度很快，然而每步的开销大于半牛顿法。因此，对于简单的优化问题，半牛顿法更为适用。而对于复杂的优化问题，信赖域法较为优胜。这两种算法有一共同特性，即其均可以在一次计算中算出优化问题对应于不同正则化参数的多个解，而计算代价与计算一个解相比，没有显著的增加。这一特性简化了最优正则化参数的寻找过程，并且提示了正则化方法解路径与半定规划中内点法中心路径之间的联系。
文中对提出的算法在模拟数据以及若干UCI数据集上进行了实验。对于第一个算法，还在70000个样本的MNIST数据集上进行了实验。