Abstract
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.
Introduction
In many machine learning domains, output variables exhibit significant structural dependencies. For instance, clustering requires transitivity (if $A \sim B$ and $B \sim C$, then $A \sim C$), while ranking requires a linear order. Standard predictive models often treat these outputs as independent, failing to enforce global consistency. This paper proposes a unified mathematical framework that treats classification, clustering, and ranking as special cases of estimating a constrained binary relation. By abstracting these tasks into a single framework, the authors provide a principled approach to structured output prediction using mathematical programming.
Methodology
The core of the approach is a family of probability measures defined over the set of all possible relations between two finite sets. The authors introduce two primary variants: the Bernoulli Model for categorical class-based features and the Logistic Model for general feature vectors.
The process is divided into two main stages:
- Learning (Parameter Estimation): Given training data consisting of related and unrelated pairs, finding the maximally probable model parameters ($\theta$) is formulated as a convex optimization problem. This ensures that the learning phase is computationally efficient and globally optimal.
- Inference (Relation Estimation): Once parameters are learned, the task is to find the most probable relation that satisfies specific structural constraints (e.g., transitivity for clustering, totality and antisymmetry for ranking). This is framed as a 01-linear program. While inference for classification is solvable in linear time, it is NP-hard for clustering and ranking, necessitating the use of branch-and-cut algorithms or efficient heuristics like Kernighan-Lin.
To handle non-linear feature interactions within a linear programming framework, the authors employ randomized multilinear polynomial lifting. This technique maps features into a higher-dimensional space, allowing linear models to approximate complex decision boundaries.
Empirical Results
The framework was evaluated on the MNIST digit dataset and English Wikipedia sentences.
MNIST Classification and Clustering
On MNIST, the model achieved a 3.14% error rate using degree-2 polynomial lifting. While this does not surpass state-of-the-art deep learning models, it demonstrates the effectiveness of the lifting technique in a transparent, convex setting.
In the clustering task, enforcing equivalence relation constraints significantly improved performance. The fraction of misclassified pairs dropped from 15.0% (under independent classification) to 7.11% when global consistency was enforced.
Ranking in Wikipedia
The model was also applied to recover the linear order of words within sentences from English Wikipedia. The results indicated that the model is robust to the choice of the regularization parameter ($\sigma$) and can successfully reconstruct rankings from textual features.
Discussion and Future Work
The primary contribution of this work is the unified abstraction of diverse machine learning tasks into a single relational framework. By treating structural properties as hard constraints rather than soft penalties, the model ensures mathematically consistent outputs.
While the learning phase is efficient, the NP-hardness of inference for clustering and ranking remains a challenge for large-scale applications. Future research may focus on more advanced polynomial lifting techniques to close the performance gap with deep learning and exploring the proposed Mixed-Integer Nonlinear Program (MINLP) formulation for semi-supervised learning.
Summary updated