The DOI matches its Crossref record, with a small difference in title or year.
A Theory of the Learnable
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“Additionally, we show that by incorporating computational constraints, V-information can be reliably estimated from data even in high dimensions with PAC-style guarantees.”
From A Theory of Usable Information Under Computational Constraints (2020) · cites this paper as Valiant, 1984
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 9
- 10.1145/356914.356918 · DOI
- [2] Barr, A., and Feigenbaum, E.A. The Handbook of Artificial Intelligence. Vol. 2. William Kaufmann, Los Altos, Calif., 1982.
- 10.1145/800157.805047 · DOI · Paper page
- [4] Duda, R.O., and Hart, P.F. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
- [5] Erdös, P., and Spencer, J. Probabilistic Methods in Combinatorics. Academic Press, New York, 1974.
- 10.1109/SFCS.1984.715949 · DOI
- 10.1007/978-3-662-12405-5 · DOI
- 10.1109/SFCS.1981.3 · DOI
- [9] Valiant, L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published.
Cited by
Sorted by citations
Approximation by superpositions of a sigmoidal function
Cybenko, G. (1989) · Mathematics of Control, Signals, and Systems · doi:10.1007/bf02551274 · Cited by 13,883
Gaussian Processes for Machine Learning
Rasmussen, C. E., & Williams, C. K. I. (2005) · doi:10.7551/mitpress/3206.001.0001 · Cited by 11,705
Machine learning: Trends, perspectives, and prospects
Jordan, M. I., & Mitchell, T. M. (2015) · Science · doi:10.1126/science.aaa8415 · Cited by 9,955
Reinforcement Learning: A Survey
Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.301 · Cited by 8,972
Wolpert, D. H. (1992) · Neural Networks · doi:10.1016/s0893-6080(05)80023-1 · Cited by 7,951
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
The Strength of Weak Learnability
Schapire, R. E. (1990) · Machine Learning · doi:10.1007/bf00116037 · Cited by 4,600
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
Automatic subspace clustering of high dimensional data for data mining applications
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276314 · Cited by 2,412
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
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194
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
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
Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., & Papernot, N. (2021) · 2021 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40001.2021.00019 · Cited by 810
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
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
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
Domain Adaptation: Learning Bounds and Algorithms
Mansour, Y., Mohri, M., & Rostamizadeh, A. (2009) · arXiv · doi:10.48550/arxiv.0902.3430 · Cited by 504
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
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
Digital medicine and the curse of dimensionality
Berisha, V., Krantsevich, C., Hahn, P. R., Hahn, S., Dasarathy, G., Turaga, P., & Liss, J. (2021) · npj Digital Medicine · doi:10.1038/s41746-021-00521-5 · Cited by 344
THE EVOLVING CONTEXT OF THE FUNDAMENTAL DIFFERENCE HYPOTHESIS
Bley-Vroman, R. (2009) · Studies in Second Language Acquisition · doi:10.1017/s0272263109090275 · Cited by 335
Schaffer, C. (1993) · Machine Learning · doi:10.1023/a:1022653209073 · Cited by 310
Provably Bounded-Optimal Agents
Russell, S. J., & Subramanian, D. (1995) · Journal of Artificial Intelligence Research · doi:10.1613/jair.133 · Cited by 252
Human model evaluation in interactive supervised learning
Fiebrink, R., Cook, P. R., & Trueman, D. (2011) · Proceedings of the SIGCHI Conference on Human Factors in Computing Systems · doi:10.1145/1978942.1978965 · Cited by 207
On Issues of Instance Selection
Liu, H., & Motoda, H. (2002) · Data Mining and Knowledge Discovery · doi:10.1023/a:1014056429969 · Cited by 191
Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited
Muggleton, S. H., Lin, D., & Tamaddoni-Nezhad, A. (2015) · Machine Learning · doi:10.1007/s10994-014-5471-y · Cited by 184
Binary Ensemble Neural Network: More Bits per Network or More Networks per Bit?
Zhu, S., Dong, X., & Su, H. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00506 · Cited by 153
Guest Column: A Survey of Quantum Learning Theory
Arunachalam, S., & de Wolf, R. (2017) · ACM SIGACT News · doi:10.1145/3106700.3106710 · Cited by 152
A Theory of Usable Information Under Computational Constraints
Xu, Y., Zhao, S., Song, J., Stewart, R., & Ermon, S. (2020) · arXiv · doi:10.48550/arxiv.2002.10689 · Cited by 142
Qian, B., Su, J., Wen, Z., Jha, D. N., Li, Y., Guan, Y., Puthal, D., James, P., Yang, R., Zomaya, A. Y., et al. (2021) · ACM Computing Surveys · doi:10.1145/3398020 · Cited by 132
Inferring extended finite state machine models from software executions
Walkinshaw, N., Taylor, R., & Derrick, J. (2016) · Empirical Software Engineering · doi:10.1007/s10664-015-9367-7 · Cited by 127
Schultebraucks, K., Yadav, V., Shalev, A. Y., Bonanno, G. A., & Galatzer-Levy, I. R. (2022) · Psychological Medicine · doi:10.1017/s0033291720002718 · Cited by 108
Wireless Network Intelligence at the Edge
Park, J., Samarakoon, S., Bennis, M., & Debbah, M. (2019) · Proceedings of the IEEE · doi:10.1109/jproc.2019.2941458 · Cited by 92
Sim: a utility for detecting similarity in computer programs
Gitchell, D., & Tran, N. (1999) · ACM SIGCSE Bulletin · doi:10.1145/384266.299783 · Cited by 62
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
Forgetting to Learn Logic Programs
Cropper, A. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i04.5776
Metadata
- Authors
- Valiant, L. G.
- Venue
- Foundations of Computation and Machine Learning
- Publisher
- ACM
- Published
- 2026-08-11
- Pages
- 69-94
- Cited by
- 0
- References
- 0
- Language
- en
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
