Constraints First: A New MDD-based Model to Generate Sentences Under
  Constraints
Alexandre Bonlarron Aurélie Calabrèse Pierre Kornprobst Jean-Charles Régin
This paper introduces a new approach to generating strongly constrained
texts. We consider standardized sentence generation for the typical application
of vision screening. To solve this problem, we formalize it as a discrete
combinatorial optimization problem and utilize multivalued decision diagrams
(MDD), a well-known data structure to deal with constraints. In our context,
one key strength of MDD is to compute an exhaustive set of solutions without
performing any search. Once the sentences are obtained, we apply a language
model (GPT-2) to keep the best ones. We detail this for English and also for
French where the agreement and conjugation rules are known to be more complex.
Finally, with the help of GPT-2, we get hundreds of bona-fide candidate
sentences. When compared with the few dozen sentences usually available in the
well-known vision screening test (MNREAD), this brings a major breakthrough in
the field of standardized sentence generation. Also, as it can be easily
adapted for other languages, it has the potential to make the MNREAD test even
more valuable and usable. More generally, this paper highlights MDD as a
convincing alternative for constrained text generation, especially when the
constraints are hard to satisfy, but also for many other prospects.