Probably Approximately Correct learning (PAC learning)
E345811
computational learning theory framework
learning theory model
theoretical framework in machine learning
Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.
All labels observed (9)
How this entity was disambiguated
This entity first appeared as the object of triple T3308894 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Probably Approximately Correct learning (PAC learning) Context triple: [Leslie Valiant, knownFor, Probably Approximately Correct learning (PAC learning)]
-
A.
P, NP, and NP-Completeness: The Basics of Complexity Theory
"P, NP, and NP-Completeness: The Basics of Complexity Theory" is a foundational textbook by Oded Goldreich that introduces the core concepts, problems, and techniques of computational complexity theory, with a focus on the classes P, NP, and NP-complete problems.
-
B.
Statistical Decision Functions
Statistical Decision Functions is a foundational work in decision theory and statistics that systematically develops the theory of optimal decision-making under uncertainty.
-
C.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
D.
Bayesian Occam factor
The Bayesian Occam factor is a term in Bayesian model comparison that automatically penalizes overly complex models by integrating over their larger parameter spaces, thereby implementing Occam’s razor in probabilistic inference.
-
E.
Interactive Proofs and the Hardness of Approximating Cliques
"Interactive Proofs and the Hardness of Approximating Cliques" is a seminal theoretical computer science paper that introduced powerful interactive proof techniques to show that finding near-maximum cliques in graphs is computationally intractable to approximate within strong bounds.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Probably Approximately Correct learning (PAC learning) Target entity description: Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.
-
A.
P, NP, and NP-Completeness: The Basics of Complexity Theory
"P, NP, and NP-Completeness: The Basics of Complexity Theory" is a foundational textbook by Oded Goldreich that introduces the core concepts, problems, and techniques of computational complexity theory, with a focus on the classes P, NP, and NP-complete problems.
-
B.
Statistical Decision Functions
Statistical Decision Functions is a foundational work in decision theory and statistics that systematically develops the theory of optimal decision-making under uncertainty.
-
C.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
D.
Bayesian Occam factor
The Bayesian Occam factor is a term in Bayesian model comparison that automatically penalizes overly complex models by integrating over their larger parameter spaces, thereby implementing Occam’s razor in probabilistic inference.
-
E.
Interactive Proofs and the Hardness of Approximating Cliques
"Interactive Proofs and the Hardness of Approximating Cliques" is a seminal theoretical computer science paper that introduced powerful interactive proof techniques to show that finding near-maximum cliques in graphs is computationally intractable to approximate within strong bounds.
- F. None of above. chosen
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
computational learning theory framework
ⓘ
learning theory model ⓘ theoretical framework in machine learning ⓘ |
| appliesTo |
binary classification
ⓘ
multiclass classification ⓘ some regression settings ⓘ |
| assumes |
access to labeled examples
ⓘ
i.i.d. examples from an unknown distribution ⓘ |
| confidenceParameterSymbol | delta ⓘ |
| contrastsWith |
exact learning models
ⓘ
heuristic, non-probabilistic learning notions ⓘ |
| coreConcept |
agnostic case
ⓘ
concept class ⓘ distribution over instances ⓘ generalization error ⓘ hypothesis class ⓘ learning algorithm ⓘ realizable case ⓘ sample complexity ⓘ target concept ⓘ |
| definesProperty |
PAC learnability
ⓘ
efficient learnability ⓘ |
| errorParameterSymbol | epsilon ⓘ |
| field |
Computational Learning Theory
ⓘ
surface form:
computational learning theory
|
| formalizes |
learning from examples
ⓘ
learning with high probability and small error ⓘ notion of efficient learnability ⓘ |
| goal |
achieve confidence at least 1 - delta
ⓘ
find hypothesis with error at most epsilon ⓘ |
| hasAbbreviation | PAC learning ⓘ |
| hasVariant |
Probably Approximately Correct learning (PAC learning)
self-linksurface differs
ⓘ
surface form:
PAC learning with noise
agnostic PAC learning ⓘ distribution-free PAC learning ⓘ distribution-specific PAC learning ⓘ |
| influenced |
VC dimension theory
ⓘ
active learning frameworks ⓘ boosting algorithms ⓘ statistical learning theory ⓘ |
| introducedBy | Leslie Valiant ⓘ |
| introducedIn |
Probably Approximately Correct learning (PAC learning)
self-linksurface differs
ⓘ
surface form:
"A Theory of the Learnable"
|
| publicationYear | 1984 ⓘ |
| publishedIn | Communications of the ACM ⓘ |
| relatedTo |
VC dimension
ⓘ
empirical risk minimization ⓘ uniform convergence ⓘ |
| requires |
polynomial sample complexity in 1/epsilon, 1/delta, and size parameters
ⓘ
polynomial-time learning algorithm for efficient PAC learning ⓘ |
| usedFor |
analyzing learnability of concept classes
ⓘ
characterizing when learning is computationally feasible ⓘ deriving bounds on sample complexity ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Probably Approximately Correct learning (PAC learning) Description of subject: Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.
Referenced by (10)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
“A Theory of the Learnable”
poverty of the stimulus argument
→
relatesTo
→
Probably Approximately Correct learning (PAC learning)
ⓘ
this entity surface form:
Gold’s theorem in language learnability
subject surface form:
Leslie Valiant
this entity surface form:
Probably Approximately Correct learning model
subject surface form:
Leslie Valiant
this entity surface form:
"A Theory of the Learnable"
Probably Approximately Correct learning (PAC learning)
→
introducedIn
→
Probably Approximately Correct learning (PAC learning)
self-linksurface differs
ⓘ
subject surface form:
Probably Approximately Correct learning
this entity surface form:
"A Theory of the Learnable"
Probably Approximately Correct learning (PAC learning)
→
hasVariant
→
Probably Approximately Correct learning (PAC learning)
self-linksurface differs
ⓘ
subject surface form:
Probably Approximately Correct learning
this entity surface form:
PAC learning with noise
“Probably Approximately Correct” (book)
→
mainSubject
→
Probably Approximately Correct learning (PAC learning)
ⓘ
subject surface form:
Probably Approximately Correct
this entity surface form:
PAC learning
“Probably Approximately Correct” (book)
→
title
→
Probably Approximately Correct learning (PAC learning)
ⓘ
subject surface form:
Probably Approximately Correct
this entity surface form:
Probably Approximately Correct
“Probably Approximately Correct” (book)
→
hasNotableConcept
→
Probably Approximately Correct learning (PAC learning)
ⓘ
subject surface form:
Probably Approximately Correct
this entity surface form:
PAC learning framework