Formulation of Hypothesis
Concept learning is the task of inferring a boolean-valued function from a set of training examples labeled positive or negative. A hypothesis is a candidate rule for that function, expressed as a conjunction of constraints on the instance attributes. The problem is to search a hypothesis space for the hypothesis that best fits the observed training data — general enough to cover unseen positive instances, specific enough to exclude negative ones.
What a Hypothesis Looks Like
Each attribute in a hypothesis can take one of three forms:
- A specific value: the attribute must exactly match, e.g.
Sky = Sunny - A "don't care" symbol ($?$): any value for this attribute is acceptable
- A "no value" symbol ($\varnothing$): no value satisfies this — the hypothesis rejects every instance
A hypothesis such as $\langle \text{Sunny}, \text{Warm}, ?, \text{Strong}, ?, ? \rangle$ classifies an instance as positive whenever Sky is Sunny and Temperature is Warm, regardless of the remaining four attributes.
The Hypothesis Space
The hypothesis space ($H$) is the set of every hypothesis expressible under a given representation. Concept learning is a search problem over $H$, seeking the hypothesis consistent with all training examples.
[!NOTE]
The size of $H$ grows fast. With 6 attributes each taking 3 possible values, the syntactic hypothesis space has size $3^6$ — but many hypotheses are semantically identical once $\varnothing$ collapses everything to the empty set.
Ordering Hypotheses by Generality
Given two hypotheses, the general-to-specific ordering defines which one imposes fewer constraints.
More general than: $h_1$ is more general than or equal to $h_2$, written $h_1 \geq_g h_2$, if every instance satisfying $h_2$ also satisfies $h_1$.
More specific than: the inverse relationship — $h_2$ imposes tighter constraints than $h_1$.
| Feature | Most General Hypothesis | Most Specific Hypothesis |
|---|---|---|
| What it is | $\langle ?, ?, ?, ?, ?, ? \rangle$ | $\langle \varnothing, \varnothing, \varnothing, \varnothing, \varnothing, \varnothing \rangle$ |
| What it accepts | Every instance | No instance |
| Role in search | Upper bound of $H$ | Lower bound of $H$ |
This ordering is what makes the hypothesis space searchable without enumerating every hypothesis individually.
MCQ
Probabilistic Approximately Correct Learning
Probably Approximately Correct (PAC) learning is a formal framework that defines what it means for a concept class to be learnable: an algorithm should, with high probability, output a hypothesis with low error, using a number of training examples and an amount of computation that is polynomial rather than unbounded.
The Two Parameters
PAC learning formalizes learnability using two parameters:
- Error tolerance ($\varepsilon$): the maximum error allowed between the learned hypothesis and the true concept
- Confidence ($\delta$): the maximum probability the algorithm is allowed to fail to meet that error bound
A concept class $C$ is PAC-learnable by learner $L$ using hypothesis space $H$ if, for all concepts $c \in C$, all distributions $D$ over the instance space, and all $0 < \varepsilon < 1/2$, $0 < \delta < 1/2$, learner $L$ outputs a hypothesis $h \in H$ such that
$ P\big[\, \text{error}_D(h) \leq \varepsilon \,\big] \geq 1 - \delta $using a number of examples polynomial in $1/\varepsilon$, $1/\delta$, and the size of the hypothesis representation.
Why "Approximately" and Not "Exactly"
Zero-error learning: would require infinitely many training examples, which no finite dataset can provide
PAC learning: accepts a bounded error $\varepsilon$ and a bounded failure probability $\delta$, both achievable with a finite, polynomial-sized sample
Sample Complexity
The sample complexity of a learning problem is the number of training examples required to guarantee PAC-learnability. For a finite hypothesis space $H$, this is bounded by:
$ m \geq \frac{1}{\varepsilon}\left(\ln|H| + \ln\frac{1}{\delta}\right) $The term $\ln|H|$ grows only logarithmically with the size of the hypothesis space, which keeps the bound tractable even for large $H$.
[!TIP]
Decreasing $\varepsilon$ or $\delta$ tightens the guarantee, and the bound shows this directly increases the required sample size $m$.
MCQ
VC Dimension
Vapnik-Chervonenkis (VC) dimension measures the capacity of a hypothesis space independently of its cardinality, which matters when $H$ is infinite (as with linear separators or neural network decision boundaries) and $\ln|H|$ from the PAC sample-complexity bound is no longer defined.
Shattering
A hypothesis space $H$ shatters a set of instances $S$ if, for every possible dichotomy (labeling) of $S$ into positive and negative subsets, there exists some hypothesis in $H$ consistent with that labeling.
Consider the hypothesis class of linear classifiers in two dimensions:
- 2 points: all $2^2 = 4$ labelings are separable by some line — shattered
- 3 points (non-collinear): all $2^3 = 8$ labelings are separable by some line — shattered
- 4 points: at least one labeling (an XOR-style arrangement) is not separable by any single line — not shattered
Defining VC Dimension Formally
The VC dimension of $H$, written $VC(H)$, is the size of the largest finite set of instances that $H$ can shatter. If $H$ can shatter arbitrarily large sets, $VC(H)$ is infinite.
$ VC(\text{linear classifiers in 2D}) = 3 $ $ VC(\text{linear classifiers in } n \text{ dimensions}) = n + 1 $ $ VC(\text{axis-aligned rectangles in 2D}) = 4 $Each value marks the exact point at which the hypothesis class's expressive power is exhausted.
VC Dimension and Sample Complexity
For infinite hypothesis spaces, $VC(H)$ replaces $\ln|H|$ in the sample complexity bound:
$ m \geq \frac{1}{\varepsilon}\left(8 \cdot VC(H) \cdot \ln\frac{13}{\varepsilon} + 4 \ln\frac{2}{\delta}\right) $| Aspect | Low VC Dimension | High VC Dimension |
|---|---|---|
| Model flexibility | Limited, simpler boundaries | High, complex boundaries |
| Risk | Underfitting | Overfitting |
| Samples needed | Fewer | More |
[!IMPORTANT]
A hypothesis class with infinite VC dimension has no finite polynomial sample bound and is therefore not PAC-learnable.
MCQ
Hypothesis Elimination
Hypothesis elimination is a concept learning strategy that maintains the complete set of hypotheses in $H$ consistent with the training data seen so far, discarding any hypothesis that misclassifies a new example. Unlike constructing a single hypothesis incrementally, elimination narrows an entire candidate set down to whatever survives all the evidence.
Procedure
Step 1: Initialize with the Full Hypothesis Space
Every hypothesis in $H$ is treated as a candidate before any training example is processed.
Step 2: Test Each Hypothesis Against Each Example
For every labeled training instance, each remaining candidate hypothesis is checked for consistency.
for each hypothesis h in candidate_set:
if h(instance) != actual_label:
remove h from candidate_set
A hypothesis survives only if it correctly classifies every training example processed so far, positive and negative.
Step 3: Converge on the Version Space
After all examples are processed, the surviving candidates constitute the set of hypotheses consistent with the data.
[!WARNING]
Naive elimination checks every hypothesis in $H$ against every example, an $O(|H| \cdot m)$ operation. For large or infinite $H$ this is computationally infeasible — the limitation the Candidate Elimination algorithm addresses.
Limitation of Explicit Enumeration
Explicit listing: requires storing every surviving hypothesis individually, infeasible once $H$ is large since many hypotheses can survive early rounds
Boundary representation: only the most general and most specific surviving hypotheses need to be tracked, since every hypothesis between them is guaranteed consistent by the ordering relation
MCQ
Candidate Elimination Algorithm
The Candidate Elimination algorithm represents the set of hypotheses consistent with the training data compactly, using two boundary sets under the general-to-specific ordering, rather than enumerating the full version space. It combines the specific-to-general and general-to-specific search strategies into a single bidirectional algorithm.
The Two Boundaries
- General boundary ($G$): the set of maximally general hypotheses consistent with the training data
- Specific boundary ($S$): the set of maximally specific hypotheses consistent with the training data
The version space is defined as every hypothesis $h$ such that $h$ is more general than or equal to some member of $S$ and more specific than or equal to some member of $G$. Nothing between the two boundaries needs to be stored explicitly.
Initialization
$ S_0 = \{ \langle \varnothing, \varnothing, \varnothing, \varnothing, \varnothing, \varnothing \rangle \} \qquad G_0 = \{ \langle ?, ?, ?, ?, ?, ? \rangle \} $$S$ begins rejecting every instance and $G$ begins accepting every instance. Each training example moves the two boundaries toward each other.
Step 1: Process a Positive Example
if example is positive:
remove from G any hypothesis inconsistent with example
for each hypothesis s in S not consistent with example:
remove s from S
add all minimal generalizations of s that ARE consistent
remove from S any hypothesis more general than another in S
A positive example generalizes $S$ and never makes it more specific.
Step 2: Process a Negative Example
if example is negative:
remove from S any hypothesis consistent with example
for each hypothesis g in G that incorrectly covers example:
remove g from G
add all minimal specializations of g that ARE consistent
remove from G any hypothesis more specific than another in G
A negative example specializes $G$ and never makes it more general.
Worked Example
Using the standard weather dataset where the target concept is "days on which EnjoySport = Yes":
| Sky | AirTemp | Humidity | Wind | Water | Forecast | EnjoySport |
|---|---|---|---|---|---|---|
| Sunny | Warm | Normal | Strong | Warm | Same | Yes |
| Sunny | Warm | High | Strong | Warm | Same | Yes |
| Rainy | Cold | High | Strong | Warm | Change | No |
| Sunny | Warm | High | Strong | Cool | Change | Yes |
After processing all four examples, the boundaries converge to:
$ S = \{ \langle \text{Sunny}, \text{Warm}, ?, \text{Strong}, ?, ? \rangle \} $ $ G = \{ \langle \text{Sunny}, ?, ?, ?, ?, ? \rangle,\ \langle ?, \text{Warm}, ?, ?, ?, ? \rangle \} $Every hypothesis lying between $S$ and $G$ under the general-to-specific ordering is a valid member of the version space.
Comparing the Two Boundaries
| Feature | Specific Boundary ($S$) | General Boundary ($G$) |
|---|---|---|
| Initial value | Most restrictive hypothesis | Most permissive hypothesis |
| Updated by | Positive examples | Negative examples |
| Direction of change | Generalizes | Specializes |
| Represents | Tightest hypothesis fitting the data | Loosest hypothesis fitting the data |
[!NOTE]
If $S$ and $G$ converge to the same single hypothesis, the algorithm has identified the exact target concept, and no further training examples can narrow the version space further.