English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Estimating Maximally Probable Constrained Relations by Mathematical Programming

MPS-Authors
/persons/resource/persons45231

Qu,  Lizhen
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons98382

Andres,  Bjoern
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

1408.0838.pdf
(Preprint), 522KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Qu, L., & Andres, B. (2014). Estimating Maximally Probable Constrained Relations by Mathematical Programming. Retrieved from http://arxiv.org/abs/1408.0838.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-D324-6
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.