@InProceedings{GR86, author = { Sally A. Goldman and Ronald L. Rivest }, title = { A Non-iterative Maximum Entropy Algorithm }, pages = { 133--148 }, booktitle = { Proceedings of the Second Annual Conference on Uncertainty in Artificial Intelligence }, isbn = { 0-444-70396-9 }, editor = { John F. Lemmer and Laveen N. Kanal }, publisher = { Elsevier }, OPTyear = { 1986 }, OPTmonth = { August 8--10, }, date = { 1986 }, eventdate = { 1986-08-08/1986-08-10 }, eventtitle = { UAI '86 }, venue = { Philadelphia, Pennsylvania }, blocked = { pdf }, keywords = { maximum entropy, iterative techniques }, abstract = { 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. }, }