**PAC Learning**

The paper that proposed the PAC learning framework: L. Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):1134–1142, 1984. Communications of the ACM Volume 27 , Issue 11 (November 1984) Pages: 1134 – 1142 Year of Publication: 1984 Author: L. G. Valiant

## Links

## Bibliography

- AIZENSTEIN, H. and L. PITT, 1992. Exact learning of read-k disjoint DNF and not-so-disjoint DNF.
*Proceedings of the fifth annual workshop on Computational ….*[Cited by 22] (1.56/year) - ALMUALLIM, H. and T.G. DIETTERICH, 1991. Learning with many irrelevant features.
*Proceedings of the Ninth National Conference on Artificial ….*[Cited by 221] (14.65/year) - ALMUALLIM, H. and T.G. DIETTERICH, 1994. Learning Boolean Concepts in the Presence of Many Irrelevant Features.
*Artificial Intelligence.*[Cited by 114] (9.43/year) - ANGLUIN, D., 1987. Learning regular sets from queries and counterexamples.
*Information and Computation.*[Cited by 401] (21.01/year) - ANGLUIN, D., 1992. Computational learning theory: survey and selected bibliography.
*Proceedings of the twenty-fourth annual ACM symposium on ….*[Cited by 86] (6.10/year) - ANGLUIN, D., M. FRAZIER and L. PITT, 1992. Learning conjunctions of Horn clauses.
*Machine Learning.*[Cited by 113] (8.02/year) - ANTHONY, M. and N. BIGGS, 1998. PAC learning and neural networks.
*The handbook of brain theory and neural networks table of ….*[Cited by 6] (0.74/year) - ANTHONY, M., 1997. Probabilistic analysis of learning in artificial neural networks: The PAC model and its variants.
*Neural Computing Surveys.*[Cited by 37] (4.07/year) - ANTHONY, M.H.G. and N. BIGGS, 1997. Computational Learning Theory. books.google.com. [Cited by 293] (32.23/year)
- APOLLONI, B. and S. CHIARAVALLI, 1997. PAC learning of concept classes through the boundaries of their items.
*Theoretical Computer Science.*[Cited by 10] (1.10/year) - ASLAM, J.A. and S.E. DECATUR, 1993. General bounds on statistical query learning and PAC learning with noise via hypothesis boosting.
*Foundations of Computer Science, 1993. Proceedings., 34th ….*[Cited by 33] (2.52/year) - AUER, P. and P.M. LONG, 1994. Simulating access to hidden information while learning.
*Proceedings of the twenty-sixth annual ACM symposium on ….*[Cited by 14] (1.16/year) - AUER, P., R.C. HOLTE and W. MAASS, 1995. Theory and applications of agnostic PAC-learning with small decision trees.
*Proceedings of the Twelfth International Conference on ….*[Cited by 74] (6.67/year) - AUER, P., target. On Learning from Multi-Instance Examples: Empirical Evaluation of a Theoretical Approach. [Cited by 51] (?/year)
- BARRERA, J.,
*et al.*, 1995. Automatic programming of binary morphological machines by PAC learning.*Proceedings of SPIE.*[Cited by 4] (0.36/year) - BARRERA, J.,
*et al.*, 2000. Automatic programming of morphological machines by PAC learning.*Fundamenta Informaticae.*[Cited by 14] (2.30/year) - BARTLETT, P.L. and R.C. WILLIAMSON, 1991. Investigating the distribution assumptions in the Pac learning model.
*Proceedings of the fourth annual workshop on Computational ….*[Cited by 10] (0.66/year) - BAUM, E.B. and D. HAUSSLER, 1990. What size net gives valid generalization?.
*Neural Computation.*[Cited by 656] (40.77/year) - BAUM, E.B., 1990. The perceptron algorithm is fast for nonmalicious distributions.
*Neural Computation.*[Cited by 30] (1.86/year) - BENEDEK, G.M. and A. ITAI, 1988. Learnability by fixed distributions.
*Proceedings of the first annual workshop on Computational ….*[Cited by 66] (3.65/year) - BLUM, A. and A. KALAI, 1998. A Note on Learning from Multiple-Instance Examples.
*Machine Learning.*[Cited by 38] (4.70/year) - BLUM, A. and P. LANGLEY, 1997. Selection of Relevant Features and Examples in Machine Learning.
*Artificial Intelligence.*[Cited by 436] (47.96/year) - BOARD, R. and L. PITT, 1990. On the necessity of Occam algorithms – ?num=100&hl=en&lr=&ie=UTF-8&cluster=4854787145544822889″>group of 5 ». ACM Press New York, NY, USA. [Cited by 43] (2.67/year)
- BSHOUTY, N.H., 1993. Exact learning via the Monotone theory.
*Foundations of Computer Science, 1993. Proceedings., 34th ….*[Cited by 119] (9.09/year) - BSHOUTY, N.H., 1996. Simple learning algorithms using divide and conquer.
*Computational Complexity.*[Cited by 25] (2.48/year) - BSHOUTY, N.H., J.C. JACKSON and C. TAMON, 1999. More efficient PAC-learning of DNF with membership queries under the uniform distribution.
*Proceedings of the twelfth annual conference on ….*[Cited by 30] (4.23/year) - BSHOUTY, N.H., N. EIRON and E. KUSHILEVITZ, 2002. PAC learning with nasty noise.
*Theoretical Computer Science.*[Cited by 7] (1.71/year) - BSHOUTY, N.H., Z. CHEN and S. HOMER, 1994. On learning discretized geometric concepts.
*Foundations of Computer Science, 1994 Proceedings., 35th ….*[Cited by 15] (1.24/year) - CASTRO, J. and D. GUIJARRO, 1998. Query, PACS and simple-PAC Learning. [Cited by 6] (0.74/year)
- CASTRO, J. and D. GUIJARRO, 2000. PACS, simple-PAC and query learning.
*Information Processing Letters.*[Cited by 4] (0.66/year) - CASTRO, J. and J.L. BALCAZAR, ALT. Simple PAC learning of simple decision lists.
*Sixth Internatinal Worksho.*[Cited by 12] (?/year) - CHRISMAN, L., 1989. Evaluating bias during pac-learning.
*Proceedings of the sixth international workshop on Machine ….*[Cited by 5] (0.29/year) - COHEN, W.W., 1993. Pac-learning a restricted class of recursive logic programs.
*Proceedings of the Eleventh National Conference on ….*[Cited by 26] (1.99/year) - COHEN, W.W., 1994. Pac-learning nondeterminate clauses.
*Proceedings of the twelfth national conference on Artificial ….*[Cited by 19] (1.57/year) - COHEN, W.W., 1995. Pac-Learning Recursive Logic Programs: Efficient Algorithms.
*Arxiv preprint cs.AI/9505104.*[Cited by 40] (3.61/year) - COHEN, W.W., 1995. Pac-learning Recursive Logic Programs: Negative Results.
*Arxiv preprint cs.AI/9505105.*[Cited by 38] (3.43/year) - COHEN, W.W., 1995. Pac-learning non-recursive Prolog clauses.
*Artificial Intelligence.*[Cited by 24] (2.16/year) - CSISZAR, I. and J.G. KORNER, 1982. Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, Inc. Orlando, FL, USA. [Cited by 640] (26.57/year)
- DE, L. and S. DZEROSKI, 1994. First-order jk-clausal theories are PAC-learnable.
*Artificial Intelligence.*[Cited by 103] (8.52/year) - DE, L., 1997. Logical settings for concept-learning.
*Artificial Intelligence.*[Cited by 83] (9.13/year) - DECATUR, S.E. and R. GENNARO, 1995. On learning from noisy and incomplete examples.
*Proceedings of the eighth annual conference on Computational ….*[Cited by 15] (1.35/year) - DECATUR, S.E., 1993. Statistical queries and faulty PAC oracles.
*Proceedings of the sixth annual conference on Computational ….*[Cited by 29] (2.22/year) - DECATUR, S.E., 1997. PAC learning with constantpartition classification noise and applications to decision tree induction.
*Proceedings of the Fourteenth International Conference on ….*[Cited by 10] (1.10/year) - DENIS, F. and R. GILLERON, 2001. PAC Learning under Helpful Distributions.
*Theoretical Informatics and Applications.*[Cited by 16] (3.14/year) - DENIS, F., 1998. PAC learning from positive statistical queries.
*Proc. 9th International Conference on Algorithmic Learning ….*[Cited by 24] (2.97/year) - DENIS, F., C.D.&.#.3.9.;.H.A.L.L.U.I.N. and R. GILLERON, 1996. PAC Learning with Simple Examples.
*Proceedings of the 13th Annual Symposium on Theoretical ….*[Cited by 16] (1.59/year) - DHAGAT, A. and L. HELLERSTEIN, 1994. PAC learning with irrelevant attributes.
*Foundations of Computer Science, 1994 Proceedings., 35th ….*[Cited by 25] (2.07/year) - DRUCKER, H., R. SCHAPIRE and P. SIMARD, 1993. Boosting performance in neural networks.
*International journal of pattern recognition and artificial ….*[Cited by 81] (6.19/year) - DZEROSKI, S., S. MUGGLETON and S. RUSSELL, 1992. PAC-learnability of determinate logic programs.
*Proceedings of the Conference on Computational Learning ….*[Cited by 80] (5.68/year) - EISENBERG, B. and R.L. RIVEST, 1990. On the sample complexity of pac-learning using random and chosen examples. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. [Cited by 18] (1.12/year)
- FREUND, Y. and R.E. SCHAPIRE, 1997. A decision-theoretic generalization of on-line learning and an application to boosting.
*Journal of Computer and System Sciences.*[Cited by 1505] (165.56/year) - FREUND, Y., 1992. An improved boosting algorithm and its implications on learning complexity.
*Proceedings of the fifth annual workshop on Computational ….*[Cited by 43] (3.05/year) - GAMARNIK, D., 2003. Extension of the PAC framework to finite and countable Markov chains.
*Information Theory, IEEE Transactions on.*[Cited by 14] (4.53/year) - GOLDBERG, P.W., 1993. PAC-learning geometrical figures. [Cited by 8] (0.61/year)
- GOLDBERG, P.W., S.A. GOLDMAN and S.D. SCOTT, 1996. PAC learning of one-dimensional patterns.
*Machine Learning.*[Cited by 6] (0.59/year) - GOLDMAN, S.A. and R.H. SLOAN, 1995. Can PAC learning algorithms tolerate random attribute noise?.
*Algorithmica.*[Cited by 21] (1.89/year) - HAUSSLER, D., 1988. Quantifying inductive bias: AI learning algorithms and Valiant’s learning framework.
*Artificial Intelligence.*[Cited by 236] (13.05/year) - HAUSSLER, D., 1990. DECISION THEORETIC GENERALIZATIONS OF THE PAC MODEL FORNEURAL NET AND OTHER LEARNING APPLICATIONS. [Cited by 10] (0.62/year)
- HAUSSLER, D., 1990. Decision Theoretic Generalizations of the PAC Learning Model. University of California, Santa Cruz, Computer Research …. [Cited by 6] (0.37/year)
- HAUSSLER, D., 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications.
*Information and Computation.*[Cited by 360] (25.55/year) - HOLDEN, S.B. and P.J.W. RAYNER, 1995. Generalization and PAC learning: some new results for the class ofgeneralized single-layer networks.
*Neural Networks, IEEE Transactions on.*[Cited by 30] (2.71/year) - HORVATH, T. and G. TURAN, 2001. Learning logic programs with structured background knowledge.
*Artificial Intelligence.*[Cited by 14] (2.75/year) - JACKSON, J.C. and M.W. CRAVEN, 1996. Learning sparse perceptrons.
*Advances in Neural Information Processing Systems.*[Cited by 17] (1.68/year) - KEARNS, M.J. and U.V. VAZIRANI, 1994. An introduction to computational learning theory – ?num=100&hl=en&lr=&ie=UTF-8&cluster=2116392035656427316″>group of 4 ». MIT Press Cambridge, MA, USA. [Cited by 490] (40.53/year)
- KEARNS, M.J., R.E. SCHAPIRE and L.M. SELLIE, 1994. Toward efficient agnostic learning.
*Machine Learning.*[Cited by 148] (12.24/year) - KLIVANS, A.R. and R.O.&.#.3.9.;.D.O.N.N.E.L.L. , 2002. Learning intersections and thresholds of halfspaces.
*Foundations of Computer Science, 2002. Proceedings. The 43rd ….*[Cited by 19] (4.65/year) - KULKARNI, S.R.,
*et al.*, 1993. PAC learning with generalized samples and an applicaiton to stochastic geometry.*Pattern Analysis and Machine Intelligence, IEEE Transactions ….*[Cited by 5] (0.38/year) - KWEK, S., 1998. PAC Learning Intersections of Halfspaces with Membership Queries.
*Algorithmica.*[Cited by 9] (1.11/year) - LING, X.C., Proc. of IJCAI. Inductive learning from good examples. [Cited by 16] (?/year)
- LINIAL, N.,
*et al.*, 1988. Results on learnability and the Vapnik-Chervonenkis dimension.*Foundations of Computer Science, 1988., 29th Annual ….*[Cited by 36] (1.99/year) - LITTLESTONE, N., 1989. From on-line to batch learning.
*Proceedings of the second annual workshop on Computational ….*[Cited by 50] (2.93/year) - LITTLESTONE, N., 1990. Mistake bounds and logarithmic linear-threshold learning algorithms. [Cited by 106] (6.59/year)
- LITTLESTONE, N., 1991. Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow.
*Proceedings of the fourth annual workshop on Computational ….*[Cited by 89] (5.90/year) - LJUNG, L., 1996. PAC-learning and asymptotic system identification theory.
*Decision and Control, 1996., Proceedings of the 35th IEEE.*[Cited by 5] (0.50/year) - LONG, P.M. and L. TAN, 1998. PAC Learning Axis-aligned Rectangles with Respect to Product Distributions from Multiple-Instance ….
*Machine Learning.*[Cited by 37] (4.57/year) - LONG, P.M., 1995. On the sample complexity of PAC learning half-spaces against the uniform distribution.
*Neural Networks, IEEE Transactions on.*[Cited by 6] (0.54/year) - LONG, P.M., log. An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform …. [Cited by 4] (?/year)
- LUGER, G.F., 1997. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA. [Cited by 335] (36.85/year)
- MAASS, W. and G. TUR?N, 1994. How fast can a threshold gate learn?. MIT Press Cambridge, MA, USA. [Cited by 33] (2.73/year)
- MAASS, W., 1993. Agnostic PAC-learning of Functions on Analog Neural Nets. neurocolt.com. [Cited by 15] (1.15/year)
- MAASS, W., 1994. Efficient agnostic PAC-learning with simple hypothesis.
*Proceedings of the seventh annual conference on ….*[Cited by 43] (3.56/year) - MAASS, W., 1995. Vapnik-Chervonenkis dimension of neural nets.
*The Handbook of Brain Theory and Neural Networks.*[Cited by 27] (2.43/year) - MAASS, W., 1995. Agnostic PAC-learning of functions on analog neural networks.
*Neural Computation.*[Cited by 6] (0.54/year) - MAHADEVAN, S. and P. TADEPALLI, 1994. Quantifying prior determination knowledge using the PAC learning model.
*Machine Learning.*[Cited by 5] (0.41/year) - MCALLESTER, D.A., 1999. Some PAC-Bayesian Theorems.
*Machine Learning.*[Cited by 58] (8.18/year) - NAJARIAN, K. and G. DUMONT, 2001. PAC learning in non-linear FIR models.
*International Journal of Adaptive Control and Signal ….*[Cited by 9] (1.77/year) - NARASIMHAN, M. and J. BILMES, 2004. PAC-learning bounded tree-width graphical models.
*Proceedings of the 20th conference on Uncertainty in ….*[Cited by 5] (2.39/year) - OSHERSON, D.N., M. STOB and S. WEINSTEIN, 1986. Systems that learn: an introduction to learning theory for cognitive and computer scientists. MIT Press Cambridge, MA, USA. [Cited by 102] (5.08/year)
- RAO, N.S.V. and V.A. PROTOPOPESCU, 1996. On PAC learning of functions with smoothness properties using feedforward sigmoidal networks.
*Proceedings of the IEEE.*[Cited by 9] (0.89/year) - RON, D., 2001. Property testing.
*Handbook of Randomized Computing.*[Cited by 49] (9.63/year) - SATOH, K. and S. OKAMOTO, 1994. Toward PAC-learning of weights from qualitative distance information.
*Case-Based Reasoning: Papers from the 1994 Workshop.*[Cited by 10] (0.83/year) - SCHAPIRE, R.E., 1992. The design and analysis of efficient learning algorithms. MIT Press Cambridge, MA, USA. [Cited by 55] (3.90/year)
- SCHUURMANS, D. and R. GREINER, 1995. Sequential PAC learning.
*Proceedings of the eighth annual conference on Computational ….*[Cited by 12] (1.08/year) - SCHUURMANS, D. and R. GREINER, 1995. Practical PAC Learning.
*Proceedings of the Fourteenth International Joint Conference ….*[Cited by 6] (0.54/year) - SERVEDIO, R., 2002. Perceptron, winnow, and PAC learning.
*SIAM Journal on Computing.*[Cited by 6] (1.47/year) - SERVEDIO, R.A., 1999. On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm.
*Proceedings of the twelfth annual conference on ….*[Cited by 15] (2.12/year) - SHAMIR, E. and C. SHWARTZMAN, 1995. Learning by extended statistical queries and its relation to PAC learning.
*Proceedings of the Second European Conference on ….*[Cited by 5] (0.45/year) - SLOAN, R.H., 1995. Four types of noise in data for PAC learning.
*Information Processing Letters.*[Cited by 11] (0.99/year) - VAN, J.H., 1998. Introduction to Coding Theory. Springer-Verlag New York, Inc. Secaucus, NJ, USA. [Cited by 447] (55.25/year)
- WARMUTH, M.K., 1989. Towards Representation Independence in PAC Learning. cse.ucsc.edu. [Cited by 16] (0.94/year)