title: Relaxation labeling with learning automata.
abstract: Relaxation labeling processes are a class of mechanisms that solve the problem of assigning labels to objects in a manner that is consistent with respect to some domain-specific constraints. We reformulate this using the model of a team of learning automata interacting with an environment or a high-level critic that gives noisy responses as to the consistency of a tentative labeling selected by the automata. This results in an iterative linear algorithm that is itself probabilistic. Using an explicit definition of consistency we give a complete analysis of this probabilistic relaxation process using weak convergence results for stochastic algorithms. Our model can accommodate a range of uncertainties in the compatibility functions. We prove a local convergence result and show that the point of convergence depends both on the initial labeling and the constraints. The algorithm is implementable in a highly parallel fashion.
authors.affiliation: Department of Electrical Engineering, Indian Institute of Science, Bangalore 560012, India.
authors.forename: M A
authors.initials: MA
authors.lastname: Thathachar
authors.forename: P S
authors.initials: PS
authors.lastname: Sastry