Cited by 3,279Machine Learning and AlgorithmsComputability, Logic, AI Algorithmssemigroups and automata theory

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

A theory of the learnable

Open access

Valiant, L. G.·1984·Communications of the ACM

DOI 10.1145/1968.1972

Open this paper in CoChat — free account Open PDF

Abstract

Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense.In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming.We give a precise methodology for studying this phenomenon from a computational viewpoint.It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learned using it in a reasonable (polynomial) number of steps.Although inherent algorithmic complexity appears to set serious limits to the range of concepts that can be learned, we show that there are some important nontrivial classes of propositional concepts that can be learned in a realistic sense.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

Integrity signals

Registry

Crossref · 10.1145/1968.1972

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Inductive Inference: Theory and Methods
Angluin, D., & Smith, C. H. (1983) · ACM Computing Surveys · doi:10.1145/356914.356918 · Cited by 872
A complexity theory based on Boolean algebra
Skyum, S., & Valiant, L. G. (1981) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1981.3 · Cited by 42
Self-citation

Flagged first, then by citations

Show all 3 references

Research works printed but not linked: 6

Barr A., 1982, Calif.
Duda R.O. and Hart P.F. Pattern Classification and Scene Analysis. Wiley New York. 1973. Duda R.O. and Hart P.F. Pattern Classification and Scene Analysis. Wiley New York. 1973.
ErdSs P., 1974, Academic Press
Goldreich O., 1984, Proceedings of 25th IEEE Symposium on Foundations of Computer Science (Singer Island, Fla., Oct. 24-26)
Michalski R.S., 1983, Calif.
Valiant L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published. Valiant L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published.

Sorted by citations

Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907
Approximation by superpositions of a sigmoidal function
Cybenko, G. (1989) · Mathematics of Control, Signals, and Systems · doi:10.1007/bf02551274 · Cited by 13,883
Machine learning: Trends, perspectives, and prospects
Jordan, M. I., & Mitchell, T. M. (2015) · Science · doi:10.1126/science.aaa8415 · Cited by 9,955
The capacity of wireless networks
Gupta, P., & Kumar, P. R. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825799 · Cited by 8,192
Stacked generalization
Wolpert, D. H. (1992) · Neural Networks · doi:10.1016/s0893-6080(05)80023-1 · Cited by 7,951
Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors)
Friedman, J., Hastie, T., & Tibshirani, R. (2000) · The Annals of Statistics · doi:10.1214/aos/1016218223 · Cited by 6,884
Instance-Based Learning Algorithms
Aha, D. W., Kibler, D. F., & Albert, M. K. (1991) · Machine Learning · doi:10.1023/a:1022689900470 · Cited by 5,290
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · ACM SIGMOD Record · doi:10.1145/170036.170072 · Cited by 4,551
An introduction to kernel-based learning algorithms
Müller, K. R., Mika, S., Rätsch, G., Tsuda, K., & Schölkopf, B. (2001) · IEEE Transactions on Neural Networks · doi:10.1109/72.914517 · Cited by 3,521
The ethics of algorithms: Mapping the debate
Mittelstadt, B. D., Allo, P., Taddeo, M., Wachter, S., & Floridi, L. (2016) · Big Data & Society · doi:10.1177/2053951716679679 · Cited by 4,567
Human-level concept learning through probabilistic program induction
Lake, B. M., Salakhutdinov, R., & Tenenbaum, J. B. (2015) · Science · doi:10.1126/science.aab3050 · Cited by 2,817
Machine learning and the physical sciences
Carleo, G., Cirac, J. I., Cranmer, K. S., Daudet, L., Schuld, M., Tishby, N., Vogt-Maranto, L., & Zdeborová, L. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.045002 · Cited by 2,640
The Strength of Weak Learnability
Schapire, R. E. (1990) · Machine Learning · doi:10.1007/bf00116037 · Cited by 4,600
Learning regular sets from queries and counterexamples
Angluin, D. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90052-6 · Cited by 2,099
The Boosting Approach to Machine Learning: An Overview
Schapire, R. E. (2003) · Lecture notes in statistics · doi:10.1007/978-0-387-21579-2_9 · Cited by 2,101
Queries and Concept Learning
Angluin, D. (1988) · Machine Learning · doi:10.1023/a:1022821128753 · Cited by 1,918
Learning in the Presence of Concept Drift and Hidden Contexts
Widmer, G., & Kubat, M. (1996) · Machine Learning · doi:10.1023/a:1018046501280 · Cited by 1,857
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
Pruning algorithms-a survey
Reed, R. (1993) · IEEE Transactions on Neural Networks · doi:10.1109/72.248452 · Cited by 1,710
Improving Generalization with Active Learning
Cohn, D. A., Atlas, L., & Ladner, R. E. (1994) · Machine Learning · doi:10.1023/a:1022673506211 · Cited by 1,597
Inductive Logic Programming: Theory and methods
Muggleton, S., & de Raedt, L. (1994) · The Journal of Logic Programming · doi:10.1016/0743-1066(94)90035-3 · Cited by 1,537
On the mathematical foundations of learning
Felipe Cucker, B., & Smale, S. (2001) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-01-00923-5 · Cited by 1,559
Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1023/a:1022869011914 · Cited by 1,514
Connectionist learning procedures
Hinton, G. E. (1989) · Artificial Intelligence · doi:10.1016/0004-3702(89)90049-0 · Cited by 1,505
Machine learning methods for landslide susceptibility studies: A comparative overview of algorithm performance
Merghadi, A., Yunus, A. P., Dou, J., Whiteley, J., Pham, B. T., Bui, D. T., Avtar, R., & Boumezbeur, A. (2020) · Earth-Science Reviews · doi:10.1016/j.earscirev.2020.103225 · Cited by 1,329
Software unit test coverage and adequacy
Zhu, H. P., Hall, P. A. V., & May, J. H. R. (1997) · ACM Computing Surveys · doi:10.1145/267580.267590 · Cited by 1,252
Principles and methods of testing finite state machines-a survey
Lee, D., & Yannakakis, M. (1996) · Proceedings of the IEEE · doi:10.1109/5.533956 · Cited by 1,230
Human-in-the-loop machine learning: a state of the art
Mosqueira-Rey, E., Hernández-Pereira, E., Alonso-Ríos, D., Bobes-Bascarán, J., & Fernández-Leal, Á. (2022) · Artificial Intelligence Review · doi:10.1007/s10462-022-10246-w · Cited by 1,251
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,241
A perspective view and survey of meta-learning
Vilalta, R., & Drissi, Y. (2002) · Artificial Intelligence Review · doi:10.1023/a:1019956318069 · Cited by 1,108
Arcing classifier (with discussion and a rejoinder by the author)
Breiman, L. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691079 · Cited by 1,124
Selective Sampling Using the Query by Committee Algorithm
Freund, Y., Seung, H. S., Shamir, E., & Tishby, N. (1997) · Machine Learning · doi:10.1023/a:1007330508534 · Cited by 1,098
Domain adaptation for medical image analysis: A survey
Guan, H., & Liu, M. (2022) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2021.3117407 · Cited by 1,057
Occam's Razor
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90114-1 · Cited by 1,054
Introduction to Semi-Supervised Learning
Zhu, X., & Goldberg, A. B. (2009) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00196ed1v01y200906aim006 · Cited by 1,025
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,019
Classifier systems and genetic algorithms
Booker, L. B., Goldberg, D. E., & Holland, J. H. (1989) · Artificial Intelligence · doi:10.1016/0004-3702(89)90050-7 · Cited by 962
Learning Information Extraction Rules for Semi-Structured and Free Text
Soderland, S. G. (1999) · Machine Learning · doi:10.1023/a:1007562322031 · Cited by 928
Interactive machine learning for health informatics: when do we need the human-in-the-loop?
Holzinger, A. (2016) · Brain Informatics · doi:10.1007/s40708-016-0042-6 · Cited by 906
What can we learn privately?
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
Learning Decision Lists
Rivest, R. L. (1987) · Machine Learning · doi:10.1023/a:1022607331053 · Cited by 894
Sparse multinomial logistic regression: fast algorithms and generalization bounds
Krishnapuram, B., Carin, L., Figueiredo, M. A. T., & Hartemink, A. J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.127 · Cited by 883
Discovering models of software processes from event-based data
Cook, J., & Wolf, A. L. (1998) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/287000.287001 · Cited by 887
Can machine learning be secure?
Barreno, M., Nelson, B. A., Sears, R., Joseph, A. D., & Tygar, J. D. (2006) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/1128817.1128824 · Cited by 852
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Haussler, D. H. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90010-d · Cited by 845
Learning From Noisy Examples
Angluin, D., & Laird, P. D. (1988) · Machine Learning · doi:10.1023/a:1022873112823 · Cited by 839
The security of machine learning
Barreno, M., Nelson, B. A., Joseph, A. D., & Tygar, J. D. (2010) · Machine Learning · doi:10.1007/s10994-010-5188-5 · Cited by 839
Statistical strategies for avoiding false discoveries in metabolomics and related experiments
Broadhurst, D., & Kell, D. B. (2006) · Metabolomics · doi:10.1007/s11306-006-0037-z · Cited by 857
Classification with Noisy Labels by Importance Reweighting
Liu, T., & Tao, D. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2456899 · Cited by 796
Adversarial learning
Lowd, D., & Meek, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081950 · Cited by 755
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 744
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
Kearns, M. J., & Valiant, L. G. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 739
Self-citation
Discriminative Reranking for Natural Language Parsing
Collins, M., & Koo, T. (2005) · Computational Linguistics · doi:10.1162/0891201053630273 · Cited by 711
Thousands of samples are needed to generate a robust gene list for predicting outcome in cancer
Ein‐Dor, L., Zuk, O., & Domany, E. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601231103 · Cited by 699
Safe Reinforcement Learning via Shielding
Alshiekh, M., Bloem, R., Ehlers, R., Könighofer, B., Niekum, S., & Topcu, U. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11797 · Cited by 37
Cost-sensitive learning by cost-proportionate example weighting
Zadrozny, B., Langford, J., & Abe, N. (2004) · Third IEEE International Conference on Data Mining · doi:10.1109/icdm.2003.1250950 · Cited by 680
Efficient noise-tolerant learning from statistical queries
Kearns, M. J. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 679
LERS-A System for Learning from Examples Based on Rough Sets
Grzymala‐Busse, J. W. (1992) · Springer eBooks · doi:10.1007/978-94-015-7975-9_1 · Cited by 657
Advance and Prospects of AdaBoost Algorithm
Cao, Y., Miao, Q., Liu, J., & Gao, L. (2013) · Acta Automatica Sinica · doi:10.1016/s1874-1029(13)60052-x · Cited by 655
From Boolean to probabilistic Boolean networks as models of genetic regulatory networks
Shmulevich, I., Dougherty, E. R., & Zhang, W. (2002) · Proceedings of the IEEE · doi:10.1109/jproc.2002.804686 · Cited by 631
On the hardness of approximate reasoning
Roth, D. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(94)00092-1 · Cited by 642
How to use expert advice
Cesa‐Bianchi, N., Freund, Y., Haussler, D. H., Helmbold, D. P., Schapire, R. E., & Warmuth, M. K. (1997) · Journal of the ACM · doi:10.1145/258128.258179 · Cited by 617
One-class classification: taxonomy of study and review of techniques
Khan, S. S., & Madden, M. G. (2014) · The Knowledge Engineering Review · doi:10.1017/s026988891300043x · Cited by 629
Active learning
Settles, B. (2012) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00429ed1v01y201207aim018 · Cited by 605
Universal Grammar, statistics or both?
Yang, C. D. (2004) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2004.08.006 · Cited by 584
Constant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1993) · Journal of the ACM · doi:10.1145/174130.174138 · Cited by 567
Wrapper induction: Efficiency and expressiveness
Kushmerick, N. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00100-9 · Cited by 550
FloatBoost learning and statistical face detection
Li, S. Z., & Zhang, Z. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.68 · Cited by 525
Unsupervised Domain Adaptation in Brain Lesion Segmentation with Adversarial Networks
Kamnitsas, K., Baumgartner, C. F., Ledig, C., Newcombe, V., Simpson, J., Kane, A. D., Menon, D. K., Nori, A., Criminisi, A., Rueckert, D., et al. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59050-9_47 · Cited by 525
Finding the homology of submanifolds with high confidence from random samples
Niyogi, P., Smale, S., & Weinberger, S. (2008) · Discrete & Computational Geometry · doi:10.1007/s00454-008-9053-2 · Cited by 523
CONNECTIONIST LEARNING PROCEDURES11This chapter appeared in Volume 40 of Artificial Intelligence in 1989, reprinted with permission of North-Holland Publishing. It is a revised version of Technical Report CMU-CS-87-115, which has the same title and was prepared in June 1987 while the author was at Carnegie Mellon University. The research was supported by contract N00014-86-K-00167 from the Office of Naval Research and by grant IST-8520359 from the National Science Foundation.
Hinton, G. E. (1990) · Elsevier eBooks · doi:10.1016/b978-0-08-051055-2.50029-8 · Cited by 524
Towards a theory of natural language interfaces to databases
Popescu, A.-M., Etzioni, O., & Kautz, H. (2003) · ACM International Conference on Intelligent User Interfaces (IUI) · doi:10.1145/604045.604070 · Cited by 522
Learning to Learn: Introduction and Overview
Thrun, S., & Pratt, L. (1998) · Learning to Learn · doi:10.1007/978-1-4615-5529-2_1 · Cited by 521
Quantum advantage in learning from experiments
Huang, H.-Y., Broughton, M., Cotler, J., Chen, S., Li, J., Mohseni, M., Neven, H., Babbush, R., Kueng, R., Preskill, J., et al. (2022) · Science · doi:10.1126/science.abn7293 · Cited by 519
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Statistical mechanics of learning from examples
Seung, H. S., Sompolinsky, H., & Tishby, N. (1992) · Physical Review A · doi:10.1103/physreva.45.6056 · Cited by 532
Computational limitations on learning from examples
Pitt, L., & Valiant, L. G. (1988) · Journal of the ACM · doi:10.1145/48014.63140 · Cited by 503
Self-citation
Constructive algorithms for structure learning in feedforward neural networks for regression problems
Kwok, T.-Y., & Yeung, D. (1997) · IEEE Transactions on Neural Networks · doi:10.1109/72.572102 · Cited by 490
Deep learning-based feature engineering for stock price movement prediction
Long, W., Lu, Z., & Cui, L.-X. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.10.034 · Cited by 500
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, C. R., & Crutchfield, J. P. (2001) · Journal of Statistical Physics · doi:10.1023/a:1010388907793 · Cited by 471
Supervised Learning
Cunningham, P., Cord, M., & Delany, S. J. (2008) · Springer eBooks · doi:10.1007/978-3-540-75171-7_2 · Cited by 538
Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
Haussler, D. H. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90002-1 · Cited by 468
An Introduction to Boosting and Leveraging
Meir, R., & Rätsch, G. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36434-x_4 · Cited by 460
Evolution of Universal Grammar
Nowak, M. A., Komarova, N. L., & Niyogi, P. (2001) · Science · doi:10.1126/science.291.5501.114 · Cited by 449
The Impact of Diversity on Online Ensemble Learning in the Presence of Concept Drift
Minku, L. L., White, A. P., & Yao, X. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2009.156 · Cited by 448
Computational and evolutionary aspects of language
Nowak, M. A., Komarova, N. L., & Niyogi, P. (2002) · Nature · doi:10.1038/nature00771 · Cited by 437
The truth will come to light: directions and challenges in extracting the knowledge embedded within trained artificial neural networks
Tickle, A. B., Andrews, R., Golea, M., & Diederich, J. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/72.728352 · Cited by 437
An analysis of model-based Interval Estimation for Markov Decision Processes
Strehl, A. L., & Littman, M. L. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.08.009 · Cited by 428
Boolean Feature Discovery in Empirical Learning
Pagallo, G., & Haussler, D. H. (1990) · Machine Learning · doi:10.1023/a:1022611825350 · Cited by 424
A general lower bound on the number of examples needed for learning
Ehrenfeucht, A., Haussler, D. H., Kearns, M. J., & Valiant, L. G. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90002-3 · Cited by 403
Self-citation
Tolerating noisy, irrelevant and novel attributes in instance-based learning algorithms
Aha, D. W. (1992) · International Journal of Man-Machine Studies · doi:10.1016/0020-7373(92)90018-g · Cited by 401
Partition testing does not inspire confidence (program testing)
Hamlet, D., & Taylor, R. (1990) · IEEE Transactions on Software Engineering · doi:10.1109/32.62448 · Cited by 394
Machine Learning for User Modeling
Webb, G. I., Pazzani, M. J., & Billsus, D. (2001) · User Modeling and User-Adapted Interaction · doi:10.1023/a:1011117102175 · Cited by 391
Probabilistic Inductive Logic Programming
Raedt, L. D., & Kersting, K. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78652-8_1 · Cited by 394
A Nearest Hyperrectangle Learning Method
Salzberg, S. L. (1991) · Machine Learning · doi:10.1023/a:1022661727670 · Cited by 386
Arithmetic Circuits: A Survey of Recent Results and Open Questions
Shpilka, A., & Yehudayoff, A. (2009) · now publishers, Inc. eBooks · doi:10.1561/0400000039 · Cited by 438
The ethics of algorithms: key problems and solutions
Tsamados, A., Aggarwal, N., Cowls, J., Morley, J., Roberts, H., Taddeo, M., & Floridi, L. (2022) · AI & SOCIETY · doi:10.1007/s00146-021-01154-8 · Cited by 384
Distributed learning in wireless sensor networks
Predd, J. B., Kulkarni, S. R., & Poor, H. V. (2006) · IEEE Signal Processing Magazine · doi:10.1109/msp.2006.1657817 · Cited by 383
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80062-5 · Cited by 371
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2004) · Journal of the ACM · doi:10.1145/972639.972643 · Cited by 370

Authors: Valiant, L. G.
Affiliations: Harvard University (US)
Corresponding author: Valiant, L. G.
Venue: Communications of the ACM
Publisher: Association for Computing Machinery (ACM)
Published: 1984-11-05
Volume: 27
Issue: 11
Pages: 1134-1142
ISSN: 0001-0782 (ISSN-L)
1557-7317
DOI: 10.1145/1968.1972
OpenAlex: W4238893454
Cited by: 3,279
References: 3
Citations by year: 2026: 58 · 2025: 93 · 2024: 117 · 2023: 106 · 2022: 123 · 2021: 116 · 2020: 96 · 2019: 91 · 2018: 89 · 2017: 94 · 2016: 89 · 2015: 84 · 2014: 62 · 2013: 91 · 2012: 71
FWCI: 10.16
Type: journal article
Language: en
Open access: bronze
doi.org
Licence: www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations: Communications of the ACM (publishedVersion)
Funders: National Science Foundation
Topics: Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
Keywords: learnability, concept learning, knowledge acquisition, learning protocols, information gathering, computational complexity, algorithmic complexity, computational learning theory

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

A theory of the learnable

Abstract

Overview

Integrity signals

Verification

Claims the paper makes

Claims other papers make about this one

Self-check

Citations

Cites

Cited by

Related

Metadata

Record

About these checks