A product rule relaxation method

Probabilistic relaxation estimates the probabilities of the potential labelings of the nodes of a multigraph. The constraints used are limited to those nodes which are connected by arcs in this multigraph. A multiplicative formula called the product rule is introduced for combining the estimates of several nodes. This formula is then shown to correspond to a discrete relaxation operator. Experiments were made using the product rule to break a substitution cipher and to disambiguate the semantic labeling of the pixels of a color image of a house. The experiments showed that in some applications, the product rule converges more rapidly to estimates that permit making reasonable decisions than did a previous formula using arithmetic averaging. The experiments also suggested ways to refine the relaxation formulas to produce more precise estimates.