欧氏度量学习
文献类型：学位论文
| 作者 | 李伏欣 |
| 学位类别 | 工学博士 |
| 答辩日期 | 2008-08-28 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 中国科学院自动化研究所 |
| 导师 | 王珏 |
| 关键词 | 度量学习 核学习 谱方法 再生核希尔伯特空间理论 表示定理 半牛顿法 信赖域法 信赖域截断牛顿法 正则化解路径 非线性半定规划 metric learning kernel learning spectral methods RKHS methods half-Newton method conjugate gradient methods trust-region methods truncated Newton methods regularization path nonlinear SDP |
| 其他题名 | Euclidean Metric Learning |
| 学位专业 | 模式识别与智能系统 |
| 中文摘要 | 在当前的信息时代中，大量的高维数，复杂结构数据不断涌现，而且 对机器自动分析和处理数据的要求越来越高。人们希望机器可以处理各种 复杂的任务。而传统机器学习中，以二分类为主的预测范式，已经越来越难以 满足各种复杂多样的需求。探询新的机器学习范式，是目前机器学习 研究中的一项重要任务。而基于相似度/不相似度的匹配范式有认知心理学 的基础，符合人类认知的特点，并且有广泛的适用范围。因此，对匹配范式的 研究，已经越来越受到人们的重视。 从机器学习的观点来看，匹配范式中相似度/不相似度的学习是机器学习需要 研究的任务。而在各种不相似度函数中，度量是具有很好数学性质的一类。本文对 如何学习一类可以等距嵌入欧氏空间的度量进行了较为系统的研究。我们称这类度量 为欧氏度量，但它不同于输入空间的欧氏度量。我们指出，学习欧氏度量 等价于学习对称半正定核。通过本文证明的表示定理，说明了欧氏度量 等价于对输入空间进行一定的非线性变换后得到的度量。并由此提出了完整 的欧氏度量学习框架。此框架区分了度量学习的两个部分，即先验度量和训练 约束。文中讨论了这两个部分的表示方式。并通过表示定理，提供统一的方式 将训练集上学得的度量推广到全空间。以往的一大类监督，非监督，半监督的非线性 维数约简算法均可以纳入框架。依此观点，对前人在非线性 维数约简及度量学习方面的工作进行了综述。 根据欧氏度量学习框架，提出了三个欧氏度量学习算法。第一个算法 由于使用一个特殊的损失函数，而可利用谱方法求解。即，可将其描述为某个矩阵的 特征值问题，而矩阵的某些特征向量即为其解。在使用图Laplacian诱导的度量做为 先验度量时，此特征值问题可以变为稀疏特征值问题。因此利用Krylov子空间方法 求解此问题，可使方法能够处理大规模的数据集。当标签样本较少时，简单 的损失函数可以导致学得的度量出现异常的扭曲。由此，本文提出了一种平滑化技术， 对损失函数进行平滑化，解决了这一问题。 之后，通过引入Bregman divergence作为正则化项，将任意凸二阶可微损失函数意义下 的欧氏度量学习和核学习问题表示为一个无约束的优化问题，其中，整个核 矩阵为优化变量。由于优化变量的个数是样本数的平方级，通常的 牛顿法和拟牛顿法难以应用。本文提出了两种方法求解这一问题。 第一种方法称为再开始的半牛顿法，它利用Hessian算子中的部分 信息，计算一种特殊的半牛顿步进行迭代。第二种方法是信赖域截断牛顿 法。它通过对Hessian算子方程 进行提前终止的共轭梯度法寻找牛顿步的近似，并利用此近似进行信赖域 迭代。这两种方法可在样本数立方级的时间内解决 度量学习问题。信赖域截断牛顿法的收敛速度很快，然而每步的开销大于半牛顿法。 因此，对于简单的优化问题，半牛顿法更为适用。而对于复杂的优化问题， 信赖域法较为优胜。这两种算法有一共同特性，即其均可以在一次计算中 算出优化问题对应于不同正则化参数的多个解，而计算代价与计算一个解 相比，没有显著的增加。这一特性简化了最优正则化参数的寻找过程，并且 提示了正则化方法解路径与半定规划中内点法中心路径之间的联系。 文中对提出的算法在模拟数据以及若干UCI数据集上进行了实验。 对于第一个算法，还在70000个样本的MNIST数据集上进行了实验。 |
| 英文摘要 | In this paper, the problem of Euclidean metric learning is studied. Euclidean metrics are defined as metrics that can be embedded in an Euclidean space. The paper explained the equivalence of learning a Euclidean metric and learning a kernel, and proved representer theorems for learning Euclidean metrics, thus pointing out that learning a Euclidean metric is learning a nonlinear transformation of the input space. Based on these discoveries, a framework for Euclidean metric learning is proposed. The framework clarifies the two information sources in Euclidean metric learning: the prior metric and the training constraints. And through the representer theorem, a unified approach to generalize the learned metric to the entire space is proposed. A lot of spectral nonlinear dimensionality reduction methods and metric learning methods are summarized under this framework. We went on to design algorithms in this framework. The first algorithm uses a special loss function, thus it is formulated as an eigenvalue problem and the solution is the eigenvectors. The eigenvalue problem can be made sparse so it is able to handle large datasets using Krylov space algorithms. When the labeled data are sparse, simple loss functions may cause abnormal skews in the learned metric, the paper proposed a smoothing method which solved this problem. The latter algorithms are able to handle arbitrary convex second-order differentiable loss functions. With a Bregman divergence as the regularizer, it is formulated into an unconstrained optimization problem with the entire n * n kernel matrix as optimization variables. Since the number of variables is of order O(n2<上标!>), the computational cost of usual Newton methods and quasi-Newton methods would be prohibitive. We proposed two approaches to deal with this problem in O(n3<上标!>)$: the first approach is a restarted half-Newton method, which utilizes a part of the information from the Hessian to make the computation tractable. It is a simple algorithm good for easy problems. The second approach is a trust-region truncated Newton method. It performs conjugate gradient on the Hessian operation equation to compute an approximation of the Newton step. It has a very fast convergence rate, however the overhead is more than the half-Newton method. Therefore, it is better for harder problems. Meanwhile, the proposed algorithms are able to compute many points on the regularization path of the problem in a single run, with the needed time not significantly larger than computing a single solution. This regularization path property makes it easier to search for the best regularization parameter, and hints possible connections between the regularization path and the central path in semidefinite programming. Experiments on synthetic, UCI and MNIST datasets (where applicable) are given for the algorithms. |
| 语种 | 中文 |
| 其他标识符 | 200518014628082 |
| 源URL | [http://ir.ia.ac.cn/handle/173211/6125]  |
| 专题 | 毕业生_博士学位论文 |
| 推荐引用方式 GB/T 7714 | 李伏欣. 欧氏度量学习[D]. 中国科学院自动化研究所. 中国科学院研究生院. 2008. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。