Pattern generation using likelihood inference for cellular automata

摘要

Cellular automata are discrete dynamical systems which evolve on a discrete grid. Recent studies have shown that cellular automata with relatively simple rules can produce highly complex patterns. We develop likelihood-based methods for estimating rules of cellular automata aimed at the re-generation of observed regular patterns. Under noisy data, our approach is equivalent to estimating the local map of a stochastic cellular automaton. Direct computations of the maximum likelihood estimates are possible for regular binary patterns. The likelihood formulation of the problem is congenial with the use of the minimum description length principle as a model selection tool. We illustrate our method with a series of examples using binary images.