A Non-Iterative Maximum Entropy Algorithm
Sally Goldman, Ronald Rivest
We present a new algorithm for computing the maximum entropy probability distribution satisfying a set of constraints. Unlike preview approaches, our method is integrated with the planning of data collection and tabulation. We show how adding constraints and performing the associated additional tabulations can substantially speed up computation by replacing the usual iterative techniques with a non-iterative computation. We note, however, that the constraints added may contain significantly more variables than any of the original constraints so there may not be enough data to collect meaningful statistics. These extra constraints are shown to correspond to the intermediate tables in Cheeseman's method. Furthermore we prove that acyclic hypergraphs and decomposable models are equivalent, and discuss the similarities and differences between our algorithm and Spiegelhalter's algorithm. Finally, we compare our work to Kim and Pearl's work on singly-connected networks.
Keywords: Maximum Entropy, Iterative Techniques
PDF Link: /papers/86/p133-goldman.pdf
AUTHOR = "Sally Goldman
and Ronald Rivest",
TITLE = "A Non-Iterative Maximum Entropy Algorithm",
BOOKTITLE = "Uncertainty in Artificial Intelligence 2 Annual Conference on Uncertainty in Artificial Intelligence (UAI-86)",
PUBLISHER = "Elsevier Science",
ADDRESS = "Amsterdam, NL",
YEAR = "1986",
PAGES = "133--148"