Learning Bayesian Nets that Perform Well
Russell Greiner, Adam Grove, Dale Schuurmans
A Bayesian net (BN) is more than a succinct way to encode a probabilistic distribution; it also corresponds to a function used to answer queries. A BN can therefore be evaluated by the accuracy of the answers it returns. Many algorithms for learning BNs, however, attempt to optimize another criterion (usually likelihood, possibly augmented with a regularizing term), which is independent of the distribution of queries that are posed. This paper takes the "performance criteria'' seriously, and considers the challenge of computing the BN whose performance -- read "accuracy over the distribution of queries'' -- is optimal. We show that many aspects of this learning task are more difficult than the corresponding subtasks in the standard model.
Keywords: Bayesian nets, (PAC-)Learning, sample/computational complexity,
PS Link: http://www.cs.toronto.edu/~greiner/PAPERS/ggs-bnpw-uai97.ps
PDF Link: /papers/97/p198-greiner.pdf
AUTHOR = "Russell Greiner
and Adam Grove and Dale Schuurmans",
TITLE = "Learning Bayesian Nets that Perform Well",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "198--207"