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

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 $Γ$ 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, $ \overline{Γ^{\cap}}\supseteq Γ$, and give examples of constraint languages for which $|\overline{Γ^{\cap}}|$ 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 ${\mathcal O}(|V|\cdot |D|^2 \cdot |\overline{Γ^{\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 ${\mathcal O}(|V|\cdot |\overline{Γ^{\cap}}| \cdot |D| \cdot \max_{ρ\in Γ}\|ρ\|^2 )$ where $\|ρ\|$ is the arity of $ρ\in Γ$. For a general language $Γ$ and non-positive weights, the minimization task can be carried out in ${\mathcal O}(|V|\cdot |\overline{Γ^{\cap}}|^2)$ time. We argue that in many natural cases $\overline{Γ^{\cap}}$ is of moderate size, though in the worst case $|\overline{Γ^{\cap}}|$ can blow up and depend exponentially on $\max_{ρ\in Γ}\|ρ\|$.