Large-Margin Metric Learning for Constrained Partitioning Problems

We consider unsupervised partitioning problems based explicitly or implicitly on the minimiza-tion of Euclidean distortions, such as cluster-ing, image or video segmentation, and other change-point detection problems. We emphasize on cases with specific structure, which include many practical situations ranging from mean-based change-point detection to image segmenta-tion problems. We aim at learning a Mahalanobis metric for these unsupervised problems, leading to feature weighting and/or selection. This is done in a supervised way by assuming the avail-ability of several (partially) labeled datasets that share the same metric. We cast the metric learn-ing problem as a large-margin structured predic-tion problem, with proper definition of regulariz-ers and losses, leading to a convex optimization problem which can be solved efficiently. Our ex-periments show how learning the metric can sig-nificantly improve performance on bioinformat-ics, video or image segmentation problems. 1