Metric learning is a key problem for many data mining and machine learning
applications, and has long been dominated by Mahalanobis methods. Recent
advances in nonlinear metric learning have demonstrated the potential power of
non-Mahalanobis distance functions, particularly tree-based functions. We
propose a novel nonlinear metric learning method that uses an iterative,
hierarchical variant of semi-supervised max-margin clustering to construct a
forest of cluster hierarchies, where each individual hierarchy can be
interpreted as a weak metric over the data. By introducing randomness during
hierarchy training and combining the output of many of the resulting
semi-random weak hierarchy metrics, we can obtain a powerful and robust
nonlinear metric model. This method has two primary contributions: first, it is
semi-supervised, incorporating information from both constrained and
unconstrained points. Second, we take a relaxed approach to constraint
satisfaction, allowing the method to satisfy different subsets of the
constraints at different levels of the hierarchy rather than attempting to
simultaneously satisfy all of them. This leads to a more robust learning
algorithm. We compare our method to a number of state-of-the-art benchmarks on
$k$-nearest neighbor classification, large-scale image retrieval and
semi-supervised clustering problems, and find that our algorithm yields results
comparable or superior to the state-of-the-art, and is significantly more
robust to noise.

提出了一种新的非线性度量学习方法，其使用基于迭代、分层的半监督最大间隔聚类的树型算法来构建聚类层级森林，并将众多半随机弱度量层级的输出结合起来，以获得强大而稳健的非线性度量模型。与一些最先进的基准测试结果相比，这种方法的结果相当或优于现有最先进算法，并且对噪声更具稳健性。同时，这种方法具有两个主要贡献：第一，它是半监督的，同时融合了约束点和非约束点的信息；第二，它采用了一种松散的约束满足方法，在不同层次的层级中满足不同子集的约束，从而得到更加稳健的学习算法。

通过最大间隔集群层级树实现半监督非线性距离度量学习

Semi-Supervised Nonlinear Distance Metric Learning via Forests of  Max-Margin Cluster Hierarchies

The need for appropriate ways to measure the distance or similarity between
data is ubiquitous in machine learning, pattern recognition and data mining,
but handcrafting such good metrics for specific problems is generally
difficult. This has led to the emergence of metric learning, which aims at
automatically learning a metric from data and has attracted a lot of interest
in machine learning and related fields for the past ten years. This survey
paper proposes a systematic review of the metric learning literature,
highlighting the pros and cons of each approach. We pay particular attention to
Mahalanobis distance metric learning, a well-studied and successful framework,
but additionally present a wide range of methods that have recently emerged as
powerful alternatives, including nonlinear metric learning, similarity learning
and local metric learning. Recent trends and extensions, such as
semi-supervised metric learning, metric learning for histogram data and the
derivation of generalization guarantees, are also covered. Finally, this survey
addresses metric learning for structured data, in particular edit distance
learning, and attempts to give an overview of the remaining challenges in
metric learning for the years to come.

本文系统地综述了度量学习的前沿研究进展，着重分析了 Mahalanobis 距离度量学习、非线性度量学习、局部度量学习等新近涌现的强大替代方法，讨论了对于结构化数据的度量学习中仍存在的挑战，旨在给出度量学习近年来的发展方向。