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

arXiv: https://arxiv.org/abs/2305.17526 · HTML: https://mlsanity.com/paper/2305.17526/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 44 references that are in the map.
- First posted on arXiv 27 May 2023.

## Builds on (most cited first, 4 of 4)

- [Constraint Solving via Fractional Edge Covers](https://mlsanity.com/paper/1711.04506/) (2017)
- [Combining pattern-based CRFs and weighted context-free grammars](https://mlsanity.com/paper/1404.5475/) (2014)
- [Multiscale Fields of Patterns](https://mlsanity.com/paper/1406.0924/) (2014)
- [Patterns versus Characters in Subword-aware Neural Language Modeling](https://mlsanity.com/paper/1709.00541/) (2017)

## Abstract (arXiv)

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,  overlineGammacapsupseteq Gamma, and give examples of constraint languages for which |overlineGammacap| 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 mathcal O(|V|· |D|2 · |overlineGammacap|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|· |overlineGammacap| · |D| · maxρ∈ Gamma|ρ|2 ) where |ρ| is the arity of ρ∈ Gamma. For a general language Gamma and non-positive weights, the minimization task can be carried out in mathcal O(|V|· |overlineGammacap|2) time. We argue that in many natural cases overlineGammacap is of moderate size, though in the worst case |overlineGammacap| can blow up and depend exponentially on maxρ∈ Gamma|ρ|.