PAC Learning Explained

PAC Learning (Probably Approximately Correct)

🔹 What is PAC Learning?

PAC stands for Probably Approximately Correct. It ensures that a learning algorithm produces a model that is approximately correct with high probability.

🔹 ε (Epsilon) – Error Tolerance

It represents the maximum acceptable error.

Example: ε = 0.05 means 5% error allowed (5 mistakes out of 100 emails).

🔹 δ (Delta) – Confidence

It represents how confident we are in the model.

Example: δ = 0.01 means 99% confidence that the error will be ≤ 5%.

🔹 Real-Life Example (Spam Detection)

Suppose you are building a spam classifier:

• ε = 0.05 → 5% error allowed
• δ = 0.01 → 99% confidence

This means your classifier has 99% confidence that the error is less than or equal to 5%.

🧠 Memory Trick

ε = error you allow
1-δ = confidence about error

🔹 Hypothesis Space (H)

Hypothesis space is the set of all possible models (rules) that a learning algorithm can choose from.

Example:

• If email contains "free" → Spam
• If email contains "offer" → Spam
• If email length > 100 → Spam
• Always Not Spam

All these possible rules together form the hypothesis space H.

Why Hypothesis Space Matters?

• Large hypothesis space → more choices → harder to learn
• Small hypothesis space → easier to select the best model
• More hypotheses require more training data

🔹 Sample Complexity Formula

m ≥ (1/ε) [ ln|H| + ln(1/δ) ]

Improved (Standard) Form:

m ≥ (1/2ε²) ln(2|H|/δ)

Where:
m = number of training samples
|H| = size of hypothesis space
ε = error tolerance
δ = confidence parameter

✅ Use Case 1: How Much Data is Needed?

Problem:

You want to train a classifier with the following requirements:

• ε = 0.05 (5% error allowed)
• δ = 0.01 (99% confidence)
• |H| = 1000 (number of possible hypotheses)

Formula Used:

m ≥ (1/ε) [ ln|H| + ln(1/δ) ]

Substitute Values:

m ≥ (1 / 0.05) [ ln(1000) + ln(1 / 0.01) ]

m ≥ 20 [ ln(1000) + ln(100) ]

ln(1000) ≈ 6.9,    ln(100) ≈ 4.6

m ≥ 20 × (6.9 + 4.6)

m ≥ 20 × 11.5 = 230

Final Answer:

You need at least 230 training samples (emails) to ensure the classifier achieves ≤ 5% error with 99% confidence.

🔹 VC Dimension (Model Capacity)

VC Dimension measures the capacity or complexity of a model — how well it can fit different patterns.

Simple Idea:

It is the maximum number of points that a model can perfectly classify in all possible ways.

Example:

• A line can classify 3 points in all ways → VC = 3
• But not 4 points → so VC = 3

Why Important?

• Higher VC → more complex model
• Needs more data
• Risk of overfitting

🔹 Inductive Bias

Inductive bias is the set of assumptions a learning algorithm makes to generalize beyond the training data.

Examples:

• Linear classifiers assume the decision boundary is a line.
• Decision trees assume data can be split hierarchically by features.
• k-NN assumes nearby points have similar labels.

Key Idea: Without inductive bias, learning is impossible — because infinitely many hypotheses could fit the training data.

🔗 Relation Between PAC Learning and Inductive Bias

• PAC requires inductive bias: To achieve PAC guarantees, the learner must restrict itself to a hypothesis space (H). This restriction is the inductive bias.
• Bias defines hypothesis space size: Stronger bias → smaller hypothesis space → less data needed.
  Weaker bias → larger hypothesis space → more data required.
• Bias vs Generalization: PAC learning explains when a given inductive bias leads to good generalization. Too weak bias → huge H → impractical data requirement.
  Too strong bias → may miss the true concept.
• VC Dimension Connection: Inductive bias determines the VC dimension of the hypothesis space. PAC learning uses VC dimension to estimate how much data is required for reliable learning.

🔹 Conclusion

Think of PAC learning as a contract:

If you give me enough data (based on ε, δ, |H|, or VC dimension),

Then I promise that, with high probability, my model will be approximately correct on unseen data.

✔ In simple terms:

More data → Better guarantee of accuracy and confidence.