Up
Previous
Next

Optimal mutual information quantization is NP-complete

Brendan Mumey and Tomas Gedeon

Montana State University

We consider the computational complexity of quantizing a joint (X,Y) probability distribution in order to maximize the mutual information of the quantization. We show that, in general, this problem is NP-complete via reductions from various forms of the PARTITION problem. In recent years, the problem of optimal quantization of the mutual information between two random variables has received increased attention. We note the application to discovery of neural coding scheme in early sensory system of the cricket as well as the central role of quantization of mutual information in the closely related "Information bottleneck" optimization scheme. The latter method has been applied to a variety of coding applications. In the application to neural coding, one models the input to the system as a random variable X and the output as a random variable Y. To simplify the situation, as well as to acknowledge inherent discreteness of collected data, X and Y are assumed to be discrete random variables. Mutual information is always nonnegative and tells us, roughly, how well we can predict X by observing Y, and vice versa. Since noise is omnipresent in neural processing, sensory systems must be robust. As such, they must represent similar stimuli in a similar way and then react to similar internal representations of the outside stimuli in a consistent way. This leads to a conclusion that individual input and output patterns are not important for understanding neural function, but rather classes of input stimuli and classes of output patterns and their correspondence is the key. Therefore we are led to a problem of optimal assignment of input and output patterns to classes, where the optimality is judged on how much original mutual information is still present between the collections of classes. More specifically, we will consider two different quantization methods one-sided quantization and two-sided (joint) quantization. In a one-sided quantization, we quantize (cluster) only one variable, let us say Y, to a space of finitely many abstract classes, Y_N, where N represents the number of classes. In two-side quantization, both variables are simultaneously quantized. In both cases, we have shown that finding the quantization that maximizes mutual information is NP-complete. While it has been speculated that theses two problems (and some associated quantization problems) were NP-complete, to the authors' knowledge our work is the first formal demonstration that this is so.