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

Metric learning is a key problem for many data mining and machine learning applications, and has long been domi-nated by Mahalanobis methods. Recent advances in nonlin-ear metric learning have demonstrated the potential power of non-Mahalanobis distance functions, particularly tree-based functions. We propose a novel nonlinear metric learn-ing method that uses an iterative, hierarchical variant of semi-supervised max-margin clustering to construct a for-est of cluster hierarchies, where each individual hierarchy can be interpreted as a weak metric over the data. By in-troducing randomness during hierarchy training and com-bining the output of many of the resulting semi-random weak hierarchy metrics, we can obtain a powerful and ro-bust nonlinear metric model. This method has two primary contributions: first, it is semi-supervised, incorporating in-formation from both constrained and unconstrained points. Second, we take a relaxed approach to constraint satisfac-tion, allowing the method to satisfy different subsets of the constraints at different levels of the hierarchy rather than at-tempting 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. Index terms — Metric learning, nonlinear, semi-supervised, max-margin clustering, hierarchical clustering