Estimating Maximally Probable Constrained Relations by Mathematical Programming
This work addresses a fundamental problem in machine learning for researchers and practitioners, offering a unified framework for multiple tasks, but it is incremental as it builds on existing mathematical programming approaches.
The paper tackles the problem of estimating constrained relations, such as classification, clustering, and ranking, by introducing a family of probability measures that unify these tasks. It results in convex optimization for learning measures, linear-time solutions for maps, and NP-hardness for equivalence relations and orders, with practical experiments on real data.
Estimating a constrained relation is a fundamental problem in machine learning. Special cases are classification (the problem of estimating a map from a set of to-be-classified elements to a set of labels), clustering (the problem of estimating an equivalence relation on a set) and ranking (the problem of estimating a linear order on a set). We contribute a family of probability measures on the set of all relations between two finite, non-empty sets, which offers a joint abstraction of multi-label classification, correlation clustering and ranking by linear ordering. Estimating (learning) a maximally probable measure, given (a training set of) related and unrelated pairs, is a convex optimization problem. Estimating (inferring) a maximally probable relation, given a measure, is a 01-linear program. It is solved in linear time for maps. It is NP-hard for equivalence relations and linear orders. Practical solutions for all three cases are shown in experiments with real data. Finally, estimating a maximally probable measure and relation jointly is posed as a mixed-integer nonlinear program. This formulation suggests a mathematical programming approach to semi-supervised learning.