Papadopoulos, A., Pachet, F., Roy, P. and Sakellariou, J. Exact Sampling for Regular and Markov Constraints with Belief Propagation. 21th Principles and Practice of Constraint Programming Conference (CP 2015), Cork (Ireland), 2015

Sony CSL authors: Fran├žois Pachet, Pierre Roy

Abstract

Sampling random sequences from a statistical model, subject to hard constraints, is generally a difficult task. In this paper, we show that for Markov models and a set of Regular global constraints and unary constraints, we can perform perfect sampling. This is achieved by defining a factor graph, composed of binary factors that combine a Markov chain and an automaton. We apply a simplified version of belief propagation to sample random sequences satisfying the global constraints, with their correct probability. Since the factor graph is linear, this procedure is efficient and exact. We illustrate this approach to the generation of sequences of text or music, imitating the style of a corpus, and verifying validity constraints, such as syntax or meter.

Keywords: markov constraints, belief propagation

Downloads

[PDF] Adobe Acrobat PDF file

BibTeX entry

@INPROCEEDINGS { papadopoulos:15b, ADDRESS="Cork (Ireland)", AUTHOR="Papadopoulos, A. and Pachet, F. and Roy, P. and Sakellariou, J.", BOOKTITLE="21th Principles and Practice of Constraint Programming Conference (CP 2015)", TITLE="Exact Sampling for Regular and Markov Constraints with Belief Propagation", YEAR="2015", }