Large-Margin Metric Learning for Partitioning Problems

Abstract

In this paper, we consider unsupervised partitioning problems, such as clustering, image segmentation, video segmentation and other change-point detection problems. We focus on partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, which include mean-based change-point detection, K-means, spectral clustering and normalized cuts. Our main goal is to learn a Mahalanobis metric for these unsupervised problems, leading to feature weighting and/or selection. This is done in a supervised way by assuming the availability of several potentially partially labelled datasets that share the same metric. We cast the metric learning problem as a large-margin structured prediction problem, with proper definition of regularizers and losses, leading to a convex optimization problem which can be solved efficiently with iterative techniques. We provide experiments where we show how learning the metric may significantly improve the partitioning performance in synthetic examples, bioinformatics, video segmentation and image segmentation problems.

References in corpus (3)

• Natural Scales in Geographical Patterns
• Optimal detection of changepoints with a linear computational cost
• Revisiting k-means: New Algorithms via Bayesian Nonparametrics

Cited by in corpus (9)

• Selective review of offline change point detection methods
• A Survey on Metric Learning for Feature Vectors and Structured Data
• A Kernel Multiple Change-point Algorithm via Model Selection
• Semantic Autoencoder for Zero-Shot Learning
• Metric Learning for Temporal Sequence Alignment
• ruptures: change point detection in Python
• New efficient algorithms for multiple change-point detection with kernels
• Differentiable Segmentation of Sequences
• Maximal Margin Distribution Support Vector Regression with coupled Constraints-based Convex Optimization