An information-theoretic framework for optimization with application to supervised learning

The article develops a unified approach for hard optimization problems involving data association, i.e. the assignment of elements viewed as “data” {x_i}, to one of a set of classes, (C_j), so as to minimize the resulting cost. The diverse problems which fit this description include data clustering, statistical classifier design to minimize probability of error, piecewise regression, structured vector quantization, as well as optimization problems in graph theory, e.g. graph partitioning. Whereas standard descent-based methods are susceptible to finding poor local optima of the cost, the suggested approach provides some potential for avoiding local optima, yet without the computational complexity of stochastic annealing. The approach we develop is based on ideas from information theory and statistical physics, and builds on the work of Rose, Gurewitz, and Fox (see IEEE Trans. on Inform. Theory, vol.38, p.1249-58, 1992) for clustering and related problems