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

Takhanov R.
August 2023 Springer

Theory of Computing Systems
2023 #67 Issue 4 760 - 784 pp.

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| ²· | Γ^∩¯ | ²) 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_ϱ_∈_Γ‖ ϱ‖ ²) where ‖ ϱ‖ is the arity of ϱ∈ Γ . For a general language Γ and non-positive weights, the minimization task can be carried out in O(| V| · | Γ^∩¯ | ²) 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_ϱ_∈_Γ‖ ϱ‖ .

Conditional random fields , Maximum a posteriori (MAP) , Pattern-based potential , Valued constraint satisfaction

Text of the article Перейти на текст статьи

Mathematics Department, School of Sciences and Humanities, Nazarbayev University, 53 Kabanbay Batyr Ave, Astana, 000010, Kazakhstan

Mathematics Department

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026