A Theory of the Learnable.

Valiant, L. G. (1984). A Theory of the Learnable. Communications of the ACM, 27(11), 1134-1142.

Type

Journal article

Intellectual base

Primary research

Year

1984

Volume

27

Issue

11

Pages

1134-1142

DOI

10.1145/1968.1972

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/1968.1972

Cited from

philosophy, systems_cybernetics

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Inductive Reasoning
  • Contemporary machine-learning theory, rooted in Valiant's PAC framework

    This sourceValiant theory of the learnable PAC framework computational learning.

• Intrinsic Ceiling vs Input
  • the sample-complexity and model-capacity framework from statistical learning (Bayes error, PAC bounds) was adopted in econometrics, psychological-measurement theory, and clinical-trial design;

    This sourceIntroduces the PAC-learning framework relating model capacity (achievable-error ceiling) to sample complexity (the input to approach it), adopted across statistics and related fields.

    Supported in partVerified against the work's full text

    Valiant supplies the PAC learning framework itself, but not its later adoption in econometrics, psychological measurement or clinical-trial design.

    “exploring the class of concepts that can be learned using it in a reasonable (polynomial) number of steps”

    Read by an automated reader; not a human review. How support was checked

Domain-specific

• Sample complexity
  • Valiant's PAC formulation made this relation explicit by treating learnability as the existence of an algorithm whose sample and computational requirements are polynomial in the relevant parameters.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 3 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:237444770c9f · see in the full table