Aspects of the Binary CMAC: Unimodularity and Probabilistic Reconstruction

摘要

The CMAC is a neural net for computing real-valued functions. Conceptually, the CMAC maps a point in the function’s domain to a set of locations in an associative memory. Each location “contains” a weight, and the sum of the weights is taken to be the function’s value at that point. The overall process may be modeled as the multiplication of an input vector by an “association matrix.” This paper highlights some aspects of the CMAC’s mapping and function computation procedures. Regarding the mapping procedure, it is shown that the associative matrix of a univariate CMAC has the consecutive-ones property; this implies that the matrix is totally-unimodular, a property of great importance in integer optimization. For a multivariate CMAC, the association matrix can be partitioned into sub-matrices, each with the consecutive-ones property. Regarding the function computation procedure, it is shown that a univariate CMAC can compute a function exactly iff a certain distribution is reconstructible from its one dimensional marginals. A CMAC extension, free of this limitation and derived from the theory of balanced matrices, is briefly discussed. These results are generalizable to multivariate CMACs in a relatively straightforward manner.