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

Items 801–900 of 1,004

Learning to see the wood for the trees: machine learning, decision trees, and the classification of isolated theropod teeth
Wills, S., Underwood, C. J., & Barrett, P. M. (2020) · Palaeontology · doi:10.1111/pala.12512 · Cited by 30
Approximate Testing of Visual Properties
Raskhodnikova, S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45198-3_31 · Cited by 30
Query learning of subsequential transducers
Vilar, J. M. (1996) · Lecture notes in computer science · doi:10.1007/bfb0033343 · Cited by 30
Ensembling Rule Based Classifiers for Detecting Network Intrusions
Panda, M., & Patra, M. R. (2009) · International Conference on Advances in Recent Technologies in Communication and Computing (ARTCom) · doi:10.1109/artcom.2009.121 · Cited by 30
Model-Based Reinforcement Learning in Factored-State MDPs
Strehl, A. L. (2007) · IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning · doi:10.1109/adprl.2007.368176 · Cited by 30
Learning-Based Testing the Sliding Window Behavior of TCP Implementations
Fiterău-Broştean, P., & Howar, F. M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-67113-0_12 · Cited by 30
Learning Regular Languages Using Non Deterministic Finite Automata
Denis, F., Lemay, A., & Terlutte, A. (2000) · Lecture notes in computer science · doi:10.1007/978-3-540-45257-7_4 · Cited by 30
Statistical Mechanics of Online Learning of Drifting Concepts: A Variational Approach
Vicente, R., Kinouchi, O., & Caticha, N. (1998) · Machine Learning · doi:10.1023/a:1007428731714 · Cited by 30
An incremental learning algorithm for constructing Boolean functions from positive and negative examples
Sánchez, S. N., Triantaphyllou, E., Chen, J., & Liao, T. W. (2002) · Computers & Operations Research · doi:10.1016/s0305-0548(01)00050-8 · Cited by 30
Recurrent networks for structured data – A unifying approach and its properties
Hammer, B. (2002) · Cognitive Systems Research · doi:10.1016/s1389-0417(01)00056-0 · Cited by 30
A General Framework for Learning Rules From Data
Apolloni, B., Esposito, A. A., Malchiodi, D., Orovas, C., Palmas, G., & Taylor, J. G. (2004) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.836249 · Cited by 30
Extending the Valiant Learning Model
Amsterdam, J. (1988) · Elsevier eBooks · doi:10.1016/b978-0-934613-64-4.50044-x · Cited by 30
Learning approximately regular languages with reversible languages
Kobayashi, S., & Yokomori, T. (1997) · Theoretical Computer Science · doi:10.1016/s0304-3975(96)00224-1 · Cited by 30
A neural-network model for learning domain rules based on its activation function characteristics
Fu, L. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/72.712152 · Cited by 30
Training sequences
Angluin, D., Gasarch, W. I., & Smith, C. H. (1989) · Theoretical Computer Science · doi:10.1016/0304-3975(89)90153-9 · Cited by 30
A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
Makino, K., & Ibaraki, T. (1998) · Journal of Algorithms · doi:10.1006/jagm.1997.0896 · Cited by 30
Grammatical Inference and Automatic Speech Recognition
Vidal, E., Casacuberta, F., & García, P. (1995) · Springer eBooks · doi:10.1007/978-3-642-57745-1_27 · Cited by 30
Vapnik-Chervonenkis bounds for generalization
Parrondo, J. M. R., & den Broeck, C. V. (1993) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/26/9/016 · Cited by 30
Trade-off among parameters affecting inductive inference
Freivalds, R., Smith, C. H., & Velauthapillai, M. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90005-9 · Cited by 30
Finite sample performance guarantees of fusers for function estimators
Rao, N. S. V. (2000) · Information Fusion · doi:10.1016/s1566-2535(00)00004-x · Cited by 30
A learning algorithm for elementary formal systems and its experiments on identification of transmembrane domains
Arikawa, S., Kuhara, S., Miyano, S., Shinohara, A., & Shinohara, T. (1992) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1992.183220 · Cited by 30
LEARNING READ-ONCE FORMULAS USING MEMBERSHIP QUERIES
Hellerstein, L., & Karpiński, M. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50013-1 · Cited by 30
A Critical Look at Experimental Evaluations of EBL
Segre, A. M., Elkan, C., & Russell, A. C. (1991) · Machine Learning · doi:10.1007/bf00114163 · Cited by 30
Inductive Inference with Bounded Number of Mind Changes
Velauthapillai, M. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50017-9 · Cited by 30
A theoretical framework for deep transfer learning
Galanti, T., Wolf, L., & Hazan, T. (2016) · Information and Inference · doi:10.1093/imaiai/iaw008 · Cited by 29
Prospectivity and Uncertainty Analysis of Tungsten Polymetallogenic Mineral Resources in the Nanling Metallogenic Belt, South China: A Comparative Study of AdaBoost, GBDT, and XgBoost Algorithms
Li, T., Xia, Q., Ouyang, Y., Zeng, R., Liu, Q., & Li, T. (2024) · Natural Resources Research · doi:10.1007/s11053-024-10321-9 · Cited by 32
A Generic Algorithm for Learning Symbolic Automata from Membership Queries
Maler, O., & Mens, I.-E. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63121-9_8 · Cited by 29
Watermarking Cryptographic Capabilities
Cohen, A., Holmgren, J., Nishimaki, R., Vaikuntanathan, V., & Wichs, D. (2018) · SIAM Journal on Computing · doi:10.1137/18m1164834 · Cited by 29
A New Look at an Old Problem: A Universal Learning Approach to Linear Regression
Bibas, K., Fogel, Y., & Feder, M. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849398 · Cited by 32
DomainATM: Domain adaptation toolbox for medical data analysis
Guan, H., & Liu, M. (2023) · NeuroImage · doi:10.1016/j.neuroimage.2023.119863 · Cited by 31
Learnability of Bipartite Ranking Functions
Agarwal, S., & Roth, D. (2005) · Lecture notes in computer science · doi:10.1007/11503415_2 · Cited by 29
Cross-validation for binary classification by real-valued functions
Anthony, M., & Holden, S. B. (1998) · Conference on Learning Theory · doi:10.1145/279943.279987 · Cited by 29
Machine Learning and the Police: Asking the Right Questions
Vestby, A., & Vestby, J. (2019) · Policing A Journal of Policy and Practice · doi:10.1093/police/paz035 · Cited by 35
On the complexity of some inductive logic programming problems
Gottlob, G., Leone, N., & Scarcello, F. (1999) · New Generation Computing · doi:10.1007/bf03037582 · Cited by 29
Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution
Blum, A. L., & Kannan, R. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1475 · Cited by 29
Min-max classifiers: Learnability, design and application
Yang, P.-F., & Maragos, P. A. (1995) · Pattern Recognition · doi:10.1016/0031-3203(94)00161-e · Cited by 29
On the sample complexity of PAC learning half-spaces against the uniform distribution
Long, P. M. (1995) · IEEE Transactions on Neural Networks · doi:10.1109/72.471352 · Cited by 29
A subexponential exact learning algorithm for DNF using equivalence queries
Bshouty, N. H. (1996) · Information Processing Letters · doi:10.1016/0020-0190(96)00077-4 · Cited by 29
When are k-nearest neighbor and back propagation accurate for feasible sized sets of examples?
Baum, E. B. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52255-7_24 · Cited by 29
Reverse-engineering of communication protocols
Lee, D., & Sabnani, K. K. (2002) · IEEE International Conference on Network Protocols (ICNP) · doi:10.1109/icnp.1993.340917 · Cited by 29
Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension
Haussler, D. H., Kearns, M. J., & Schapire, R. E. (1991) · Elsevier eBooks · doi:10.1016/b978-1-55860-213-7.50010-9 · Cited by 29
On-line learning of rectangles
Chen, Z., & Maass, W. (1992) · Conference on Learning Theory · doi:10.1145/130385.130387 · Cited by 29
Understanding Machine Learning Principles: Learning, Inference, Generalization, and Computational Learning Theory
Du, K.-L., Zhang, R., Jiang, B., Zeng, J., & Lu, J. (2025) · Mathematics · doi:10.3390/math13030451 · Cited by 35
$$L^*$$-Based Learning of Markov Decision Processes
Tappler, M., Aichernig, B. K., Bacci, G., Eichlseder, M., & Larsen, K. G. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-30942-8_38 · Cited by 28
Learning Description Logic Ontologies: Five Approaches. Where Do They Stand?
Ozaki, A. (2020) · Künstliche Intell. · doi:10.1007/s13218-020-00656-9 · Cited by 35
Grammatical Inference in Software Engineering: An Overview of the State of the Art
Stevenson, A., & Cordy, J. R. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36089-3_12 · Cited by 28
On the Learnability of Hidden Markov Models
Terwijn, S. A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45790-9_21 · Cited by 28
On PAC Learning Algorithms for Rich Boolean Function Classes
Servedio, R. A. (2006) · Lecture notes in computer science · doi:10.1007/11750321_42 · Cited by 28
Learning in the limit with lattice-structured hypothesis spaces
Heinz, J. N., Kasprzik, A., & Kötzing, T. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.07.017 · Cited by 28
Quantum versus classical learnability
Servedio, R. A., & Gortler, S. J. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2001.933881 · Cited by 38
A Complete Characterization of Statistical Query Learning with Applications to Evolvability
Feldman, V. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.35 · Cited by 28
Stochastic Finite Learning of the Pattern Languages
Rossmanith, P., & Zeugmann, T. (2001) · Machine Learning · doi:10.1023/a:1010875913047 · Cited by 28
Pac-learning non-recursive prolog clauses
Cohen, W. W. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(94)00034-4 · Cited by 28
On the power of incremental learning
Lange, S., & Grieser, G. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00404-2 · Cited by 28
Learning Random Monotone DNF
Jackson, J. C., Lee, H. K., Servedio, R. A., & Wan, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85363-3_38 · Cited by 28
Inferring Deterministic Linear Languages
de la Higuera, C., & Oncina, J. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45435-7_13 · Cited by 28
A Markovian extension of Valiant's learning model
Aldous, D., & Vazirani, U. V. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89558 · Cited by 28
On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm
Servedio, R. A. (1999) · Conference on Learning Theory · doi:10.1145/307400.307474 · Cited by 28
Criteria for Polynomial-Time (Conceptual) Clustering
Pitt, L., & Reinke, R. E. (1988) · Machine Learning · doi:10.1007/bf00116830 · Cited by 28
Mutually supervised learning in multiagent systems
Goldman, C. V., & Rosenschein, J. S. (1996) · Lecture notes in computer science · doi:10.1007/3-540-60923-7_20 · Cited by 28
On the necessity of Occam algorithms
Raymond Board, & Pitt, L. (1992) · Theoretical Computer Science · doi:10.1016/0304-3975(92)90367-o · Cited by 28
Polynomial-time learning of elementary formal systems
Miyano, S., Shinohara, A., & Shinohara, T. (2000) · New Generation Computing · doi:10.1007/bf03037530 · Cited by 28
Results on learnability and the Vapnik-Chervonenkis dimension
Linial, N., Mansour, Y., & Rivest, R. L. (1988) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21930 · Cited by 28
Equivalence Queries and Approximate Fingerprints
Angluin, D. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50012-x · Cited by 28
A connectionist learning algorithm with provable generalization and scaling bounds
Gallant, S. I. (1990) · Neural Networks · doi:10.1016/0893-6080(90)90089-4 · Cited by 28
Revolutionizing physics: a comprehensive survey of machine learning applications
Suresh, R., Bishnoi, H., Kuklin, A. V., Parikh, A., Моlokeev, М. S., Harinarayanan, R., Gharat, S., & Hiba, P. (2024) · Frontiers in Physics · doi:10.3389/fphy.2024.1322162 · Cited by 31
Learning schema mappings
ten Cate, B., Dalmau, V., & Kolaitis, P. G. (2012) · International Conference on Database Theory · doi:10.1145/2274576.2274596 · Cited by 27
Sensing and Probing Cardinalities for Active Cognitive Radios
Nguyen, T. V., Shin, H., Quek, T. Q. S., & Win, M. Z. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2178843 · Cited by 27
Model selection and error estimation without the agonizing pain
Oneto, L. (2018) · Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery · doi:10.1002/widm.1252 · Cited by 27
Symbolic Abstractions From Data: A PAC Learning Approach
Devonport, A., Saoud, A., & Arcak, M. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683316 · Cited by 27
Using Active Learning to Develop Machine Learning Models for Reaction Yield Prediction
Johansson, S., Svensson, H. G., Bjerrum, E. J., Schliep, A., Chehreghani, M. H., Tyrchan, C., & Engkvist, O. (2022) · Molecular Informatics · doi:10.1002/minf.202200043 · Cited by 30
MI-SegNet: Mutual Information-Based US Segmentation for Unseen Domain Generalization
Bi, Y., Jiang, Z., Clarenbach, R., Ghotbi, R., Karlas, A., & Navab, N. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-43901-8_13 · Cited by 30
Can Denoising Enhance Prediction Accuracy of Learning Models? A Case of Wavelet Decomposition Approach
Tamilselvi, C., Yeasin, M., Paul, R. K., & Paul, A. K. (2024) · Forecasting · doi:10.3390/forecast6010005 · Cited by 30
Learning Structured Concepts Using Genetic Algorithms
Giordana, A., & Sale, C. (1992) · Elsevier eBooks · doi:10.1016/b978-1-55860-247-2.50027-9 · Cited by 27
Response times seen as decompression times in Boolean concept use
Bradmetz, J., & Mathy, F. (2006) · Psychological Research · doi:10.1007/s00426-006-0098-7 · Cited by 31
Intelligent sampling for big data using bootstrap sampling and chebyshev inequality
Satyanarayana, A. (2014) · Conference proceedings - Canadian Conference on Electrical and Computer Engineering · doi:10.1109/ccece.2014.6901029 · Cited by 27
Complementary Attributes: A New Clue to Zero-Shot Learning
Xu, X., Tsang, I. W.-H., & Liu, C. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2930744 · Cited by 27
Searching for a solution to the automatic RBF network design problem
V.David Sánchez, A. (2002) · Neurocomputing · doi:10.1016/s0925-2312(01)00600-2 · Cited by 27
The Random Projection Method
Vempala, S. (2001) · Combinatorial optimization · doi:10.1007/978-1-4615-0013-1_16 · Cited by 27
On approximately identifying concept classes in the limit
Kobayashi, S., & Yokomori, T. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60454-5_47 · Cited by 27
A Polynomial Time Algorithm That Learns Two Hidden Unit Nets
Baum, E. B. (1990) · Neural Computation · doi:10.1162/neco.1990.2.4.510 · Cited by 27
Exact Learning of Discretized Geometric Concepts
Bshouty, N. H., Goldberg, P. W., Goldman, S. A., & Mathias, H. D. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539794274246 · Cited by 27
Effects of Kernel Function on Nu Support Vector Machines in Extreme Cases
Ikeda, K. (2006) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.860832 · Cited by 27
A Connectionist Computational Model for Epistemic and Temporal Reasoning
Garcez, A. D., & Lamb, L. C. (2006) · Neural Computation · doi:10.1162/neco.2006.18.7.1711 · Cited by 27
Learnability of description logics
Cohen, W. W., & Hirsh, H. (1992) · Conference on Learning Theory · doi:10.1145/130385.130398 · Cited by 27
General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Boosting
Aslam, J. A., & Decatur, S. E. (1998) · Information and Computation · doi:10.1006/inco.1998.2664 · Cited by 27
Learning String Patterns and Tree Patterns from Examples
Ko, K., Marron, A., & Tzeng, W.-G. (1990) · Elsevier eBooks · doi:10.1016/b978-1-55860-141-3.50049-3 · Cited by 27
Agnostic PAC Learning of Functions on Analog Neural Nets
Maass, W. (1995) · Neural Computation · doi:10.1162/neco.1995.7.5.1054 · Cited by 27
Inference of a minimum size boolean function from examples by using a new efficient branch-and-bound approach
Triantaphyllou, E. (1994) · Journal of Global Optimization · doi:10.1007/bf01097004 · Cited by 27
Optimizing similarity using multi-query relevance feedback
Bartell, B. T., Cottrell, G. W., & Belew, R. K. (1998) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199806)49:8 · Cited by 27
Nonuniform learnability
Benedek, G. M., & Itai, A. (1988) · Lecture notes in computer science · doi:10.1007/3-540-19488-6_108 · Cited by 27
An architecture for bounded rationality
Russell, S. (1991) · ACM SIGART Bulletin · doi:10.1145/122344.122374 · Cited by 26
SAT-based techniques for determining backbones for post-silicon fault localisation
Zhu, C. S., Weißenbacher, G., Sethi, D., & Malik, S. (2011) · Proceedings · doi:10.1109/hldvt.2011.6113981 · Cited by 26
Automating Abstract Interpretation
Reps, T., & Thakur, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-49122-5_1 · Cited by 26
Interactive Mapping Specification with Exemplar Tuples
Bonifati, A., Comignani, U., Coquery, E., & Thion, R. (2017) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3035918.3064028 · Cited by 26
L∗-based learning of Markov decision processes (extended version)
Tappler, M., Aichernig, B. K., Bacci, G., Eichlseder, M., & Larsen, K. G. (2021) · Formal Aspects of Computing · doi:10.1007/s00165-021-00536-5 · Cited by 26
On the computational complexity of ethics: moral tractability for minds and machines
Stenseke, J. (2024) · Artificial Intelligence Review · doi:10.1007/s10462-024-10732-3 · Cited by 34
Data Stream Mining Using Granularity-Based Approach
Gaber, M. M. (2009) · Studies in computational intelligence · doi:10.1007/978-3-642-01091-0_3 · Cited by 26
Assessing and generating test sets in terms of behavioural adequacy
Fraser, G., & Walkinshaw, N. (2015) · Software Testing Verification and Reliability · doi:10.1002/stvr.1575 · Cited by 26
Computational complexity analysis of multi-objective genetic programming
Neumann, F. (2012) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/2330163.2330274 · Cited by 26

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