What is learning? Induction, generalization, and inductive bias

Learning = improving from experience

A workable definition (after Herbert Simon): learning is any change in a system that lets it perform *better the second time* on the same task, or on another task drawn from the same population. The phrase “same population” is the whole game — the learner sees only a fraction of all possible examples and must generalize correctly to instances it has never seen.

Deduction vs induction

The single most exam-relevant distinction in this module:

- Deductive reasoning runs from a general rule to a specific conclusion that the rule *guarantees*. It is truth-preserving: if the premises are true, the conclusion *must* be true. *All men are mortal; Socrates is a man; therefore Socrates is mortal.* - Inductive reasoning runs the other way — from specific observed examples to a general rule. It is not truth-preserving: the conclusion is a plausible *generalization*, not a logical certainty. From “every swan I have seen is white” you may induce “all swans are white” — and a single black swan refutes it.

Machine learning is fundamentally inductive: the program is handed examples and must infer the general concept. That is exactly why it can be wrong on new data — induction *creates* knowledge that goes beyond the evidence, which deduction never does.

The generalization lattice

Concept learning is search through a space of candidate descriptions ordered by generality. Two dual operations move you through that space:

- Generalization makes a description cover *more* instances — drop a condition, or replace a constant with a variable (color(red) → color(X)). - Specialization makes a description cover *fewer* — add a condition, or pin a variable to a constant.

The “more-general-than” relation forms a lattice over descriptions: every region of the space sits between a most-specific and a most-general bound. This lattice is what makes the candidate-elimination search of the next lesson tractable.

Inductive bias — why learning is even possible

Here is the catch (it is Hume’s problem of induction): any finite set of examples is consistent with *infinitely many* different general rules. Pure data cannot choose among them. So every learner must bring a prior preference — an inductive bias — that constrains the concept space or ranks the candidates.

Worked example — the bias is doing the work. Given the points $(1,1), (2,2), (3,3)$, you “obviously” induce $y = x$. But $y = x$, or a degree-5 polynomial through those three points, or “$y=x$ except on Tuesdays” are *all* consistent with the data. You picked $y=x$ because you carry a bias toward simple hypotheses — Occam’s Razor: prefer the simplest description consistent with the examples. ID3 (L8.3) builds this same razor into its tree-size preference. Bias is not a bug; without it, generalization is impossible.