--- id: FOUND-007 title: "Learning, Reasoning and Generalization" alternative_names: - "Induction, Deduction and Generalization" - "Learning Theory Foundations" category: "Foundations → Cognition and Learning" volume: I chapter: 2 entry_type: "Standard Article" level: 3 status: "Draft" last_reviewed: 2026-10-15 version: "0.1.0" prerequisites: - "FOUND-003" related_entries: - "FOUND-008" - "FOUND-011" - "TECH-ML-001" - "TECH-DL-001" - "TECH-REASON-001" - "CAP-REASON-001" --- # Learning, Reasoning and Generalization ## 1. Concise Definition **Learning** is the process by which a system improves its performance on a class of tasks from experience or data. **Reasoning** is the derivation of conclusions from premises or evidence by some inference procedure. **Generalization** is the ability to perform well on inputs not encountered during learning. In AI the three are distinct but interdependent: learning without generalization is memorization, and reasoning without learned or supplied knowledge has nothing to operate on. ## 2. Overview & Significance The central difficulty of machine learning is that a finite sample of examples is compatible with infinitely many rules. A learner therefore needs assumptions (an *inductive bias*) that favour some rules over others, and a theory of when those assumptions justify confidence in predictions. Reasoning, historically the focus of symbolic AI, addresses a different problem: given knowledge, what follows from it ([[FOUND-003] Knowledge Representation](FOUND-003_knowledge_representation.md); [[FOUND-011] Logic and Formal Systems](FOUND-011_logic_and_formal_systems.md))? The relationship between the two is a recurring question in AI. Statistical learners (see [[TECH-ML-001] Machine Learning](../vol03_technical/TECH-ML-001_machine_learning.md) and [[TECH-DL-001] Deep Learning](../vol03_technical/TECH-DL-001_deep_learning.md)) generalize well on many tasks without explicit rules, while logic-based systems reason exactly but depend on hand-supplied knowledge. Whether large language models reason, or reproduce patterns that resemble reasoning, is actively disputed (Section 8). Because a system's apparent competence can be a product of the training distribution, the distinction between learning a skill and generalizing beyond the data is central to evaluating claims about intelligence ([[CAP-BENCH-001] AI Evaluation](../vol04_capabilities/CAP-BENCH-001_ai_evaluation.md)). ## 3. Historical Development Formal learning theory begins with Valiant's (1984) "A theory of the learnable", which defined learnability in terms of efficient algorithms that, with high probability, output an approximately correct hypothesis (the *probably approximately correct*, PAC, framework). Vapnik and collaborators developed statistical learning theory, relating generalization to the capacity of a hypothesis class (the Vapnik-Chervonenkis dimension). Shalev-Shwartz and Ben-David (2014) give a modern textbook treatment of both. Wolpert (1996) showed that, averaged over all possible target functions, no learning algorithm outperforms any other (the "no free lunch" results), which makes explicit that generalization depends on assumptions about the problem rather than on the algorithm alone. The classical picture, in which models with more capacity than the data warrant overfit, was challenged by deep learning practice. Zhang et al. (2017) showed that standard deep networks can fit training sets with randomly assigned labels, and argued that traditional measures of model complexity therefore do not by themselves explain why such networks generalize on real data. Belkin et al. (2019) proposed a "double descent" risk curve to reconcile modern over-parameterized models with the classical bias-variance trade-off. On the reasoning side, deductive inference was mechanized in the 1950s and 1960s (Newell and Simon's Logic Theory Machine; resolution theorem proving), and is covered in [[FOUND-011] Logic and Formal Systems](FOUND-011_logic_and_formal_systems.md) and [[HIST-003] Symbolic AI and the Perceptron](../vol02_history/HIST-003_symbolic_ai_perceptron.md). More recently, Wei et al. (2022) reported that prompting large language models to produce intermediate reasoning steps ("chain of thought") improved performance on arithmetic, commonsense and symbolic reasoning benchmarks. Lake et al. (2017) argued that human-like learning relies on compositional, causal models and intuitive theories, and that current networks lack them. Chollet (2019) proposed that intelligence be measured as skill-acquisition efficiency over a scope of tasks, controlling for prior knowledge and experience, rather than as skill on fixed tasks. ## 4. Technical / Conceptual Explanation ### 4.1 The learning problem Let inputs $x \in \mathcal{X}$ and labels $y \in \mathcal{Y}$ be drawn from an unknown distribution $\mathcal{D}$. A learner receives a sample $S = \{(x_i, y_i)\}_{i=1}^{m}$ and selects a hypothesis $h$ from a class $\mathcal{H}$. The **true risk** of $h$ under a loss $\ell$ is $$R(h) = \mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(h(x), y)],$$ and the **empirical risk** is $$\hat{R}_S(h) = \frac{1}{m}\sum_{i=1}^{m} \ell(h(x_i), y_i).$$ The **generalization gap** is $R(h) - \hat{R}_S(h)$. Empirical risk minimization chooses $h$ to minimize $\hat{R}_S$, and learning theory asks when the gap is small. ### 4.2 Capacity-based guarantees For binary classification with a hypothesis class of VC dimension $d$, standard results (see Shalev-Shwartz & Ben-David, 2014) bound, with probability at least $1-\delta$ over samples, the gap uniformly over $\mathcal{H}$ by a quantity of order $$\sqrt{\frac{d\,\ln(m/d) + \ln(1/\delta)}{m}}.$$ The bound shrinks with more data and grows with class capacity. It is distribution-free, which makes it conservative; for large neural networks the bound is typically too loose to be informative, which is the observation behind Zhang et al. (2017). ### 4.3 No free lunch and inductive bias Wolpert (1996) shows that without assumptions linking training data to unseen cases, all algorithms have equal expected off-training-set performance when averaged uniformly over targets. Practical learners succeed because real problems are not uniformly distributed over targets: they are smooth, compositional, sparse or structured, and learner architectures encode matching biases (convolutions encode translation structure, for example). ### 4.4 Bias, variance and double descent For squared loss, expected error decomposes into bias squared, variance and irreducible noise. In the classical regime, increasing capacity lowers bias and raises variance, producing a U-shaped test-error curve. Belkin et al. (2019) report empirically that, for several model families, test error can decrease again once capacity passes the *interpolation threshold* at which the model fits the training data exactly, giving a "double descent" curve. They propose a mechanism for this pattern. The phenomenon is documented for specific models; its extent across modern deep-learning practice is still being studied. ### 4.5 Forms of reasoning - **Deduction**: conclusions follow necessarily from premises (truth-preserving). See [[FOUND-011] Logic and Formal Systems](FOUND-011_logic_and_formal_systems.md). - **Induction**: general rules are inferred from instances; conclusions are probable, not guaranteed. This is the mode of statistical learning. - **Abduction**: inference to the best explanation of observations. - **Probabilistic reasoning**: updating degrees of belief under uncertainty ([[FOUND-008] Probability, Statistics and Bayesian Inference](FOUND-008_probability_statistics_and_bayesian_inference.md)). ### 4.6 Distribution shift Guarantees such as those in 4.2 assume test data are drawn from the training distribution $\mathcal{D}$. When they are not (covariate shift, new task composition, new domains), performance can degrade in ways that in-distribution validation does not reveal. Chollet (2019) argues that measuring generalization requires tasks whose content the system cannot have encountered, which is the design aim of his proposed benchmark. ## 5. Types, Components & Classifications **Learning paradigms** (details in [[TECH-ML-001] Machine Learning](../vol03_technical/TECH-ML-001_machine_learning.md) and [[TECH-RL-001] Reinforcement Learning](../vol03_technical/TECH-RL-001_reinforcement_learning.md)): supervised, unsupervised and self-supervised, and reinforcement learning. **Kinds of generalization.** - *In-distribution*: new samples from the training distribution. - *Out-of-distribution*: shifted conditions or inputs. - *Compositional*: new combinations of known parts, a capability emphasised by Lake et al. (2017). - *Task or skill generalization*: acquiring new skills efficiently, the notion formalized by Chollet (2019). **Reasoning approaches in AI.** - *Symbolic*: theorem provers, rule engines and constraint solvers, which are sound by construction but depend on a supplied formal representation. - *Statistical/neural*: inference implicit in learned parameters. - *Prompted or trained step-wise reasoning* in language models, as in Wei et al. (2022). - *Hybrid (neurosymbolic)*: combining the two; see [[FOUND-011] Logic and Formal Systems](FOUND-011_logic_and_formal_systems.md). ## 6. Applications & Concrete Examples - **Image and speech classification, translation, recommendation** are deployed applications in which generalization from training data to new inputs is the core requirement; see [[TECH-DL-001] Deep Learning](../vol03_technical/TECH-DL-001_deep_learning.md). - **Benchmark evaluation.** Held-out test sets estimate in-distribution generalization. Contamination of training data by test items undermines such estimates ([[TECH-DATA-001] Training Data, Contamination and Provenance](../vol03_technical/TECH-DATA-001_training_data_contamination_and_provenance.md)). - **Chain-of-thought prompting.** Wei et al. (2022) report gains on arithmetic, commonsense and symbolic benchmarks for sufficiently large models; this is a laboratory result about benchmark accuracy, not proof of a particular internal mechanism. - **Random-label experiments.** Zhang et al. (2017) fit networks to randomly labelled data as a diagnostic showing that capacity alone does not guarantee generalization. ## 7. Advantages, Limitations & Unresolved Questions **Strengths.** Statistical learning scales to problems where explicit rules cannot be written; formal reasoning offers correctness guarantees relative to its premises. **Limitations.** - Classical capacity-based bounds are often uninformative for deep networks (Zhang et al., 2017). - Learners inherit the biases and gaps of their training data, and shifts in distribution can produce failures not predicted by held-out accuracy. - Prompted reasoning in language models can yield fluent but incorrect or unfaithful steps; the reported benchmark gains (Wei et al., 2022) do not settle whether the generated steps reflect the computation that produced the answer. [VERIFICATION NEEDED: cite a source on faithfulness of chain-of-thought explanations if this point is retained in later versions] - Symbolic reasoning is brittle when knowledge is incomplete or inconsistent. **Unresolved questions.** Why over-parameterized networks generalize as well as they do; how to define and measure generalization beyond the training distribution; whether reasoning in neural networks is a distinct capability or an extension of pattern learning; and how much prior structure a system needs to learn efficiently (the position argued by Lake et al., 2017). ## 8. Current State of Knowledge As of 2026-10-15: - The risk decomposition, PAC and VC frameworks and no-free-lunch results are established mathematics. - Double descent is a documented empirical pattern for several model classes (Belkin et al., 2019); a unified theory for deep networks remains incomplete. - Whether large language models "reason" is **Contested**. One position holds that step-wise generation and training on reasoning traces produces genuine multi-step inference; another holds that outputs reflect learned surface patterns that fail under distribution shift. This article does not resolve the dispute and points to [[TECH-REASON-001] Reasoning Models and Test-Time Compute](../vol03_technical/TECH-REASON-001_reasoning_models_and_test_time_compute.md) and [[CAP-REASON-001] Reasoning, Planning and Long-Horizon Capability](../vol04_capabilities/CAP-REASON-001_reasoning_planning_and_long_horizon_capability.md) for current evidence. Benchmark figures change quickly and are tracked in the Living Reference collection (`MODEL-001`). - The view that human-like generalization requires compositional and causal structure (Lake et al., 2017) is a research position, not a settled finding. ## 9. Future Trajectory & Strategic Outlook No registered forecast is made here. Observed directions: evaluation designs aimed at novel-task generalization (Chollet, 2019); theory for over-parameterized models following Belkin et al. (2019); and integration of learned and symbolic components. Near-term progress is likely to be incremental and measured on benchmarks whose validity is itself debated. Claims that any specific architecture will close the gap between pattern learning and flexible reasoning within a given period are speculative and are not asserted. ## 10. Related Entries & Knowledge Graph - **Foundational Concepts**: - [[FOUND-003] Knowledge Representation](FOUND-003_knowledge_representation.md): how knowledge to reason over is encoded. - [[FOUND-008] Probability, Statistics and Bayesian Inference](FOUND-008_probability_statistics_and_bayesian_inference.md): the mathematics of inductive inference. - [[FOUND-011] Logic and Formal Systems](FOUND-011_logic_and_formal_systems.md): the theory of deductive reasoning. - [[FOUND-010] Optimization and Gradient Descent](FOUND-010_optimization_and_gradient_descent.md): how learners find hypotheses in practice. - **Related Methods & Technologies**: - [[TECH-ML-001] Machine Learning](../vol03_technical/TECH-ML-001_machine_learning.md): the learning paradigms. - [[TECH-DL-001] Deep Learning](../vol03_technical/TECH-DL-001_deep_learning.md): over-parameterized learners. - [[TECH-LLM-001] Large Language Models](../vol03_technical/TECH-LLM-001_large_language_models.md): systems in which the reasoning debate is concentrated. - **Advanced Implications & Future Trajectories**: - [[TECH-REASON-001] Reasoning Models and Test-Time Compute](../vol03_technical/TECH-REASON-001_reasoning_models_and_test_time_compute.md): reasoning-oriented training and inference. - [[CAP-REASON-001] Reasoning, Planning and Long-Horizon Capability](../vol04_capabilities/CAP-REASON-001_reasoning_planning_and_long_horizon_capability.md): measured reasoning capability. - [[AGI-001] Artificial General Intelligence](../vol05_agi/AGI-001_artificial_general_intelligence.md): generality as a defining target. ## 11. References & Foundational Literature 1. Valiant, L. G. (1984). A theory of the learnable. *Communications of the ACM*, 27(11), 1134-1142. https://doi.org/10.1145/1968.1972. [Defines PAC learnability. Checked against Crossref.] 2. Shalev-Shwartz, S., & Ben-David, S. (2014). *Understanding Machine Learning: From Theory to Algorithms*. Cambridge University Press. ISBN 978-1107057135. [Textbook source for risk, VC-dimension and generalization bounds. ISBN and authors checked against Open Library; bound form from standard theory, not re-derived here.] 3. Wolpert, D. H. (1996). The lack of a priori distinctions between learning algorithms. *Neural Computation*, 8(7), 1341-1390. https://doi.org/10.1162/neco.1996.8.7.1341. [No-free-lunch results for learning. Checked against Crossref.] 4. Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. *International Conference on Learning Representations (ICLR 2017)*. arXiv:1611.03530. [Networks can fit random labels, so classical complexity measures do not by themselves explain generalization. Authors and title checked against arXiv page; venue from author knowledge.] 5. Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019). Reconciling modern machine-learning practice and the classical bias-variance trade-off. *Proceedings of the National Academy of Sciences*, 116(32), 15849-15854. https://doi.org/10.1073/pnas.1903070116. [Proposes the double-descent risk curve. Checked against Crossref abstract.] 6. Lake, B. M., Ullman, T. D., Tenenbaum, J. B., & Gershman, S. J. (2017). Building machines that learn and think like people. *Behavioral and Brain Sciences*, 40, e253. https://doi.org/10.1017/S0140525X16001837. [Argues for compositional and causal structure in human-like learning. Checked against Crossref; article number from author knowledge.] 7. Chollet, F. (2019). On the measure of intelligence. arXiv:1911.01547 (preprint). [Proposes intelligence as skill-acquisition efficiency and a benchmark intended to test it. Checked against arXiv page.] 8. Wei, J., et al. (2022). Chain-of-thought prompting elicits reasoning in large language models. *Advances in Neural Information Processing Systems (NeurIPS 2022)*. arXiv:2201.11903. [Reports benchmark gains from intermediate-step prompting. Nine authors confirmed on arXiv; venue from author knowledge.] ## 12. Evidential Classification Matrix | Section / Claim | Evidence Category | Supporting Source | Confidence / Status | | :--- | :--- | :--- | :--- | | Risk, empirical risk, generalization gap definitions | Established | Shalev-Shwartz & Ben-David (2014) | High | | PAC learnability framework | Established | Valiant (1984) | High | | No free lunch for learning algorithms | Established | Wolpert (1996) | High | | Deep nets fit random labels; classical complexity measures insufficient | Well Supported | Zhang et al. (2017) | Moderate to High | | Double descent in over-parameterized models | Well Supported | Belkin et al. (2019) | Moderate; extent across deep learning under study | | Chain-of-thought prompting improves benchmark accuracy | Preliminary to Well Supported | Wei et al. (2022) | Moderate; benchmark-specific | | LLMs "reason" in a robust, general sense | Contested | Wei et al. (2022); Lake et al. (2017) | Low; unresolved | | Intelligence as skill-acquisition efficiency | Contested (proposal) | Chollet (2019) | Moderate; one framework among several | ## 13. Revision History - **v0.1.0** (2026-10-15): Initial draft. Citations checked against arXiv/Crossref/publisher pages where marked; not independently fact-checked.