Abstract
Prior knowledge, or bias, regarding a concept can reduce the number of examples needed to learn it. Probably Approximately Correct (PAC) learning is a mathematical model of concept learning that can be used to quantify the reduction in the number of examples due to different forms of bias. Thus far, PAC learning has mostly been used to analyzesyntactic bias, such as limiting concepts to conjunctions of boolean prepositions. This paper demonstrates that PAC learning can also be used to analyzesemantic bias, such as a domain theory about the concept being learned. The key idea is to view the hypothesis space in PAC learning as that consistent withall prior knowledge, syntactic and semantic. In particular, the paper presents an analysis ofdeterminations, a type of relevance knowledge. The results of the analysis reveal crisp distinctions and relations among different determinations, and illustrate the usefulness of an analysis based on the PAC learning model.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Angluin, D. (1988). “Queries and concept learning,”Machine Learning, 2.
Blumer, A., Ehrefeucht, A., Haussler, D., and Warmuth, M. (1989). “Learnability and the Vapnik-Chervonenkis Dimension”,Journal of the ACM, 36 (4):929–965.
Brooks, R. (1991). “Intelligence without reason,” inProceeding of the 12th IJCAI, Morgan Kaufmann.
Danyluk, A. (1989). “Finding new rules for incomplete theories: Explicit biases for induction with contextual information,” inProceeding of the Sixth International Machine Learning Workshop, Morgan-Kaufmann.
Davies, T., and Russell, S. (1987). “A logical approach reasoning by analogy,” inProceedings of The Tenth International Joint Conference on Artificial Intelligence, Morgan Kaufmann.
Davies, T. (1988). “Determination, uniformity, and relevance: Normative criteria for generalization and reasoning by analogy,” in D. H. Helman, editor,Analogical Reasoning, pages 227–250. Kluwer Academic Publishers.
Dejong, G., and Mooney, R. (1986). “Explanation-Based Learning: An alternative view,”Machine Learning, 1 (2).
desJardins, M. (1989). “Probabilistic evaluation of bias for learning systems,” inProceedings of the Sixth International Machine Learning Workshop, pages 495–499. Morgan-Kaufmann.
Dietterich, T. (1989). “Limitations on inductive learning,” inProceedings of the Sixth Machine Learning Workshop, pages 124–128. Morgan Kaufmann.
Hall, R. (1988). “Learning by failing to explain,”Machine Learning, 3. (1)
Haussler, D., Littlestone, N., and Warmuth, M. (1988). “Predicting 0,1 functions on randomly drawn points,” inProceedings of the 29th IEEE Symposium on Foundations of Computer Science, pages 100–109.
Haussler, D. (1988). “Quantifying inductive bias: “AI learning algorithms and Valiant's learning framework,”Artificial Intelligence, 36 (2).
Hirsh, H. (1989).Incremental Version-Space Merging: A General Framework for Concept Learning. PhD thesis, Standford University.
Kearns, M., and Valiant, L. (1989). “Cryptographic limitations on learning boolean formulae and finite automata,” inProceedings of the 21st Annual ACM Symposium on Theory of Computing.
Korf, R. (1985). “Macro-Operators: A Weak Method for Learning,”Artificial Intelligence, 26 (1): 35–77.
Mahadevan, S., and Tadepalli, P. (1988). “On the tractability of learning from incomplete theories,” inProceedings of the Fifth International Machine Learning Conference, pages 235–241. Morgan-Kaufmann.
Mahadevan, S. (1989). “Using determinations in EBL: A solution to the incomplete theory problem,” inProceedings of the 6th International Workshop on Machine Learning, pages 320–325. Morgan-Kaufmann.
Mitchell, T., Keller, R., and Kedar-Cabelli, S. (1986). “Explanation-based generalization: A unifying view,”Machine Learning, 1 (1).
Mitchell, T. (1980). “The need for biases in learning generalizations,” Technical Report CBM-TR-117, Rutgers University.
Natarajan, B., and Tadepalli, P. (1988). “Two new frameworks for learning,” inProceedings of the Fifth International Machine Learning Conference, Morgan-Kaufmann.
Natarajan, B. (1987). “On learning boolean functions,” inACM Symposium on Theory of Computing.
Natarajan, B. (1989). “On learning sets and functions,” Machine Learning, 4 (1).
Natarajan, B. (1991).Machine Learning: A Theoretical Approach, Morgan Kaufmann.
Pazzani, M. (1992). “The Utility of Knowledge in Inductive Learning,”Machine Learning, 9(1): 57–94.
Pearl, J. (1988).Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.
Pitt, L., and Valiant, L.G. (1988). “Computational limits of learning from examples.”Journal of the ACM, 35 (4): 965–984.
Pitt, L., and Warmuth, M. (1990). “Prediction preserving reducibility,”Journal of Computer and System Sciences, 41 (3).
Rich, E., and Knight, K. (1991).Artificial Intelligence. McGraw-Hill.
Rivest, R. (1987). “Learning decision lists,”Machine Learning, 2(3): 229–246.
Russell, S., and Grosof, B. (1989). “A sketch of autonomous learning using declarative bias,” in P. Brazdil and K. Konolige, editors,Machine Learning, Meta-Reasoning, and Logics, Kluwer Academic.
Russell, S. (1986).Analogical and Inductive Reasoning, PhD thesis, Stanford University.
Russell, S. (1987). “Analogy and single instance generalization,” inProceedings of the 4th International Conference on Machine Learning, pages 390–397. Morgan-Kaufmann.
Russell, S. (1988). “Tree-structured bias,” inProceedings of the Seventh National Conference on Artificial Intelligence (AAAI), pages 641–645. Morgan-Kaufmann.
Russell, S. (1989).The use of knowledge in analogy and induction. Morgan Kaufmann.
Tadepalli, P. (1991). “A formalization of explanation-based macro-operator learning,” inProceedings of the IJCAI, pages 616–622.
Tadepalli, P. (1993). “Learning from queries and examples with tree-structured bias,” inProceedings of the Tenth International Machine Learning Conference, Morgan-Kaufmann.
Valiant, L. (1984). “A theory of the learnable,”Communications of the ACM, 27 (11).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mahadevan, S., Tadepalli, P. Quantifying prior determination knowledge using the PAC learning model. Mach Learn 17, 69–105 (1994). https://doi.org/10.1007/BF00993865
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00993865