A maximum entropy method for expert system construction (monte carlo, recognition, partition function)
Alan Lippman · 1986
We consider a maximum entropy method of expert system construction. Simply stated, in cases where more than one distribution satisfies the constraints (knowledge) supplied to the system, we pick the one with maximum entropy. Viewing entropy as a measure of information, we pick the distribution that makes the fewest additional assumptions. Theoretically we show that this distribution is (typically) unique, and that its explicit identification amounts to solving a dual problem of minimizing a convex function which lies in as many dimensions as we have constraints. Unfortunately, in most interesting applications, the exact calculation of the gradients of this function proves computationally intractable. We construct and analyse a Monte Carlo method to overcome this difficulty. We test the method for an artificial system with known distribution. We calculate the system's statistics, use them as constraints, and then find the maximum entropy distribution. The Monte Carlo method proves successful. As our main example we consider the problem of character recognition. Sample letters are presented and features extracted. Sample statistics concerning these features provide the constraints for our system. The maximum entropy distribution lies on the space of features and labels, where the latter identifies the letter. Under this distribution we can find the most likely label corresponding to a set of features. The results prove encouraging for a range of typed letters.