Approximate maximum entropy joint feature inference for discrete space classification

We propose a new method for learning discrete space statistical classifiers. We cast classification/inference within the more general framework of estimating the joint probability mass function (PMF) for the (feature vector, class label) pair. The proposal of Cheeseman (1983) to construct the maximum entropy (ME) joint PMF consistent with general lower order probability constraints has been severely limited by its huge learning complexity. Alternatives such as Bayesian networks require explicit specification of conditional independencies. Here we reconsider the ME problem, propose an approximate method which encodes arbitrary low order constraints, while retaining quite tractable learning. The new method approximates the joint feature PMF during learning on a sub-grid of the full feature space. Extensions to more general inference problems are indicated