TY - JOUR

T1 - Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring

AU - Takhanov, Rustem

N1 - Funding Information:
This research has been funded by Nazarbayev University under Faculty-development competitive research grants program for 2023-2025 Grant #20122022FD4131, PI Zh. Assylbekov. We would like to thank Anuar Sharafudinov for his help with writing a Java code that computes the closure of a simple language.
Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023

Y1 - 2023

N2 - 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 Γ 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 Γ we introduce a closure operator, Γ∩¯ ⊇ Γ , and give examples of constraint languages for which | Γ∩¯ | is small. If all predicates in Γ 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 O(| V| · | D| 2· | Γ∩¯ | 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 O(| V| · | Γ∩¯ | · | D| · maxϱ∈Γ‖ ϱ‖ 2) where ‖ ϱ‖ is the arity of ϱ∈ Γ . For a general language Γ and non-positive weights, the minimization task can be carried out in O(| V| · | Γ∩¯ | 2) time. We argue that in many natural cases Γ∩¯ is of moderate size, though in the worst case | Γ∩¯ | can blow up and depend exponentially on maxϱ∈Γ‖ ϱ‖ .

AB - 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 Γ 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 Γ we introduce a closure operator, Γ∩¯ ⊇ Γ , and give examples of constraint languages for which | Γ∩¯ | is small. If all predicates in Γ 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 O(| V| · | D| 2· | Γ∩¯ | 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 O(| V| · | Γ∩¯ | · | D| · maxϱ∈Γ‖ ϱ‖ 2) where ‖ ϱ‖ is the arity of ϱ∈ Γ . For a general language Γ and non-positive weights, the minimization task can be carried out in O(| V| · | Γ∩¯ | 2) time. We argue that in many natural cases Γ∩¯ is of moderate size, though in the worst case | Γ∩¯ | can blow up and depend exponentially on maxϱ∈Γ‖ ϱ‖ .

KW - Conditional random fields

KW - Maximum a posteriori (MAP)

KW - Pattern-based potential

KW - Valued constraint satisfaction

UR - http://www.scopus.com/inward/record.url?scp=85164318393&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85164318393&partnerID=8YFLogxK

U2 - 10.1007/s00224-023-10128-w

DO - 10.1007/s00224-023-10128-w

M3 - Article

AN - SCOPUS:85164318393

SN - 1432-4350

JO - Theory of Computing Systems

JF - Theory of Computing Systems

ER -