Learning to Measure: Distance Metric Learning with Structured Sparsity

Abstract

Many important machine learning and data mining algorithms rely on a measure to provide a notion of distance or dissimilarity. Naive metrics such as the Euclidean distance are incapable of leveraging task-specific information, and consider all features as equal. A learned distance metric can become much more effective by honing in on structure specific to a task. Additionally, it is often extremely desirable for a metric to be sparse, as this vastly increases the ability to interpret or explain the measures produced by the distance metric. In this dissertation, we explore several current problems in distance metric learning and put forth solutions which make use of structured sparsity. The contributions of this dissertation may be broadly divided into two portions. In the first portion (chapter 2) we begin with a classic approach in distance metric learning and address a scenario where distance metric learning is typically inapplicable, i.e., the case of learning on heterogeneous data in a high-dimensional input space. We construct a projection-free distance metric learning algorithm which utilizes structured sparse updates and successfully demonstrate its application to learn a metric with over a billion parameters. The second portion (chapters 3 & 4) of this dissertation focuses on a new and intriguing regression-based approach to distance metric learning. Under this regression approach there are two sets of parameters to learn; those which parameterize the metric, and those defining the so-called ``virtual points''. We begin with an exploration of the metric parameterization and develop a structured sparse approach to robustify the metric to noisy, corrupted, or irrelevant data. We then focus on the virtual points and develop a new method for learning the metric and constraints together in a simultaneous manner. We demonstrate through empirical means that our approach results in a distance metric which is much more effective than the current state of-the-art. Machine learning algorithms have recently become ingrained in an incredibly diverse amount of technology. The primary focus of this dissertation is to develop more effective techniques to learn a distance metric. We believe that this work has the potential for rather broad-reaching impacts, as learning a more effective metric typically results in more accurate metric-based machine learning algorithms.