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 Γdocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$varvec{Gamma }$$end{document} consists of {0,1}documentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${textbf {{0,1}}}$$end{document}-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 Γdocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$varvec{Gamma }$$end{document} we introduce a closure operator, Γ∩ˉ?Γdocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$ overline{varvec{Gamma }^{cap }}supseteq varvec{Gamma }$$end{document}, and give examples of constraint languages for which Γ∩ˉdocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$overline{varvec{Gamma }^{cap }}$$end{document} is small. If all predicates in Γdocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$varvec{Gamma }$$end{document} 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·D2·Γ∩ˉ2)documentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${varvec{mathcal O}}(varvec{V}cdot varvec{D}varvec{^2} cdot overline{varvec{Gamma }^{cap }}varvec{^2})$$end{document} time, where Vdocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$varvec{V}$$end{document} is a set of variables, Ddocumentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$varvec{D}$$end{document} 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)documentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${varvec{mathcal O}}(varvec{V}cdot overline{varvec{Gamma }^{cap }} cdot varvec{D} cdot varvec{max }_{varrho in varve