Computing a partition function of a generalized pattern-based energy over a semiring

DOI10.1007/S00224-023-10128-WMaRDI QIDQ6174653zbMATH OpenOpenAlexFDO

Authors Rustem Takhanov

Publication date 17 August 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.17526

zbMATH Keywords

conditional random fieldsvalued constraint satisfactionmaximum a posteriori (MAP)pattern-based potential

Mathematics Subject Classification ID

Theory of computing (68Qxx) Artificial intelligence (68Txx) Algebraic structures (08Axx)

Abstract: Valued constraint satisfaction problems with ordered variables (VCSPO) are a special case of Valued CSPs in which variables are totally ordered and soft constraints are imposed on tuples of variables that do not violate the order. We study a restriction of VCSPO, in which soft constraints are imposed on a segment of adjacent variables and a constraint language $Gamma$ consists of $0,1$-valued characteristic functions of predicates. This kind of potentials generalizes the so-called pattern-based potentials, which were applied in many tasks of structured prediction. For a constraint language $Gamma$ we introduce a closure operator, $overlineGamm{a}^{cap}supseteqGamma$, and give examples of constraint languages for which $|overlineGamm{a}^{cap}|$ is small. If all predicates in $Gamma$ are cartesian products, we show that the minimization of a generalized pattern-based potential (or, the computation of its partition function) can be made in $mathcalO(|V|cdot|D{|}^{2}cdot|overlineGamm{a}^{cap}{|}^2)$ time, where $V$ is a set of variables, $D$ is a domain set. If, additionally, only non-positive weights of constraints are allowed, the complexity of the minimization task drops to $mathcalO(|V|cdot|overlineGamm{a}^{cap}|cdot|D|cdotma{x}_{hoinGamma}|ho{|}^2)$ where $|ho|$ is the arity of $hoinGamma$. For a general language $Gamma$ and non-positive weights, the minimization task can be carried out in $mathcalO(|V|cdot|overlineGamm{a}^{cap}{|}^2)$ time. We argue that in many natural cases $overlineGamm{a}^{cap}$ is of moderate size, though in the worst case $|overlineGamm{a}^{cap}|$ can blow up and depend exponentially on $ma{x}_{hoinGamma}|ho|$.

Cites work

• scientific article; zbMATH DE number 6378100 (Why is no real title available?)
• A proof of the CSP dichotomy conjecture
• Bounded backtracking for the valued constraint satisfaction problems
• Classifying the Complexity of Constraints Using Finite Algebras
• Effectiveness of structural restrictions for hybrid CSPs
• Hybrid VCSPs with crisp and valued conservative templates
• Hypertree decompositions and tractable queries
• Inference algorithms for pattern-based CRFs on sequence data
• Monotone monadic SNP and constraint satisfaction
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the complexity of \(k\)-SAT
• Principles and practice of constraint programming -- CP 2010. 16th international conference, CP 2010, St. Andrews, Scotland, September 6--10, 2010. Proceedings
• Reduction operations in fuzzy or valued constraint satisfaction
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Soft arc consistency revisited
• Statistical mechanics, three-dimensionality and NP-completeness
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• Tree clustering for constraint networks

This page was built for publication: Computing a partition function of a generalized pattern-based energy over a semiring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174653)