Self-annealing and self-annihilation: unifying deterministic annealing and relaxation labeling

Experimental results on synthetic matching and labeling problems clearly demonstrate the three-way relationship between deterministic annealing, relaxation labeling and self-annealing.

Abstract

Deterministic annealing and relaxation labeling algorithms for classification and matching are presented and discussed. A new approach – self annealing – is introduced to bring deterministic annealing and relaxation labeling into accord. Self-annealing results in an emergent linear schedule for winner-take-all and linear assignment problems. Self-annihilation, a generalization of self-annealing is capable of performing the useful function of symmetry breaking. The original relaxation labeling algorithm is then shown to arise from an approximation to either the self-annealing energy function or the corresponding dynamical system. With this relationship in place, self-annihilation can be introduced into the relaxation labeling framework. Experimental results on synthetic matching and labeling problems clearly demonstrate the three-way relationship between deterministic annealing, relaxation labeling and self-annealing.