Abstract
We consider the problem of PAC learning probabilistic networks in the case where the structure of the net is specified beforehand. We allow the conditional probabilities to be represented in any manner (as tables or specialized functions) and obtain sample complexity bounds for learning nets with and without hidden nodes.
Article PDF
Similar content being viewed by others
References
Abe, N., Takeuchi, J., & Warmuth M.(1990). Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence. ACM Conference on Computational Learning Theory. San Mateo, CA: Morgan Kaufmann.
Cover, T. M., & Thomas, J. A. (1991).Elements of information theory. New York: John Wiley.
Dudley, R. M. (1978). Central limit theorems for empiricalmeasures. Annals of Probability, 6, 899–929.
Friedman, N., & Yakhini, Z. (1996). On the samplecomplexity of learning Bayesian networks. Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence. San Mateo, CA: Morgan Kaufmann.
Haussler, D. (1992).Decision-theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100, 78–150.
Pearl, J. (1988).Probabilistic reasoning in intelligent systems. San Mateo, CA: Morgan Kaufmann.
Pollard, D. (1984). Convergenceof stochastic processes. New York: Springer-Verlag.
Russell, S., Binder, J., Koller, D., & Kanazawa, K.(1995). Local learning in probabilistic networks with hidden variables. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Los Altos, CA: William Kaufmann.
Valiant, L. (1984). A theory of thelearnable. Communications of the ACM, 27, 1134–1142.
Vapnik, V. N. (1982). Estimation of dependenciesbased on empirical data. New York: Springer-Verlag.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dasgupta, S. The Sample Complexity of Learning Fixed-Structure Bayesian Networks. Machine Learning 29, 165–180 (1997). https://doi.org/10.1023/A:1007417612269
Issue Date:
DOI: https://doi.org/10.1023/A:1007417612269