Estimating Maximally Probable Constrained Relations by Mathematical Programming

Lizhen Qu, Bjoern AndresarXiv 2014 · OpenReview

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.

Graphical models for the Bernoulli (a) and Logistic (b) variants of the proposed framework.

The process is divided into two main stages:

  1. 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.
  2. 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.

Relative error on MNIST classification as a function of regularization ($\sigma^{-2}$) and polynomial lifting degree ($d$).

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

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.
BibTeX
@misc{qu2014estimating,
  author = {Lizhen Qu and Bjoern Andres},
  title = {{Estimating Maximally Probable Constrained Relations by Mathematical Programming}},
  year = {2014},
  eprint = {1408.0838},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1408.0838},
}
Figure