MACHINE LEARNING IS INDUCTIVE INFERENCE: reasoning from specific observations to a general rule. THE THREE MODES OF INFERENCE, for contrast: DEDUCTION from general to specific, and TRUTH-PRESERVING. All men are mortal; Socrates is a man; therefore Socrates is mortal. The conclusion cannot be false if the premises are true. INDUCTION from specific to general, and NOT truth-preserving. Every swan I have seen is white; therefore all swans are white. FALSE, as Australia demonstrated. ABDUCTION from an observation to the best explanation. The grass is wet; it probably rained. Also not truth-preserving — the sprinkler. MACHINE LEARNING IS INDUCTION, SO ITS CONCLUSIONS ARE NEVER GUARANTEED. That is not a defect to be engineered away; it is the logical nature of the enterprise. A learned model is a well-supported guess, and the entire discipline of evaluation exists because the guess cannot be proved. THE INDUCTIVE LEARNING HYPOTHESIS, which is the assumption that makes it work at all: "Any hypothesis found to approximate the target function well over a sufficiently large set of training examples will also approximate the target function well over other unobserved examples." THIS IS AN ASSUMPTION, NOT A THEOREM. It is the "future resembles the past" premise from the previous topic, stated in learning terms, and everything rests on it. CONCEPT LEARNING — the cleanest formal setting, and the one the syllabus expects: Given examples of a CONCEPT (a boolean-valued function over instances), infer a general definition of it. "Days suitable for playing tennis", "patients with the disease", "emails that are spam". THE FORMAL SETUP: the INSTANCE SPACE X — all possible instances the TARGET CONCEPT c : X → {0, 1} TRAINING EXAMPLES — pairs ⟨x, c(x)⟩, positive and negative the HYPOTHESIS SPACE H — the candidate definitions the learner may consider THE GOAL: find h in H such that h(x) = c(x) for all x in X — and the learner can only check the training examples. A WORKED HYPOTHESIS SPACE. Instances described by four attributes: Sky ∈ {Sunny, Cloudy, Rainy} Humidity ∈ {Normal, High} Wind ∈ {Strong, Weak} Water ∈ {Warm, Cool} So the instance space |X| = 3 × 2 × 2 × 2 = 24 distinct instances. A hypothesis is written as a CONJUNCTION OF CONSTRAINTS, one per attribute, each being a specific value, "?" for "any value", or "∅" for "no value accepted": ⟨Sunny, ?, Strong, ?⟩ means "sunny AND windy, whatever the humidity and water". COUNTING THE HYPOTHESIS SPACE: each attribute may take its own values plus "?" plus "∅": (3+2) × (2+2) × (2+2) × (2+2) = 5 × 4 × 4 × 4 = 320 syntactically distinct hypotheses. Excluding those containing "∅" (which all represent the empty concept and are semantically identical): 4 × 3 × 3 × 3 = 108 semantically distinct hypotheses, plus one empty concept. NOW COMPARE WITH THE SPACE OF ALL POSSIBLE CONCEPTS: any subset of the 24 instances is a concept, so there are 2^24 = 16,777,216 possible concepts. THE CONJUNCTIVE HYPOTHESIS SPACE CONTAINS 109 OF THEM. That is the INDUCTIVE BIAS made numerical — the learner has committed in advance to conjunctive concepts and cannot express "sunny or rainy", which is one of the 16.7 million it has excluded. IF THE TARGET CONCEPT IS DISJUNCTIVE, NO AMOUNT OF DATA WILL FIND IT.

THE GENERAL-TO-SPECIFIC ORDERING gives the hypothesis space structure. Hypothesis h₁ is MORE GENERAL THAN OR EQUAL TO h₂ if every instance h₂ accepts, h₁ also accepts. ⟨Sunny, ?, ?, ?⟩ is more general than ⟨Sunny, High, ?, ?⟩ The ordering is a PARTIAL order — some pairs are incomparable — and it is what makes efficient search possible. THE VERSION SPACE is the subset of H consistent with all the training examples seen so far. It is the set of hypotheses still in contention. IT CAN BE REPRESENTED COMPACTLY BY ITS BOUNDARIES: S — the SPECIFIC BOUNDARY: the most specific consistent hypotheses G — the GENERAL BOUNDARY: the most general consistent hypotheses Every hypothesis between them, in the general-to-specific ordering, is also consistent. STORING TWO BOUNDARY SETS REPRESENTS A POSSIBLY ENORMOUS VERSION SPACE, which is the algorithmic insight. THE CANDIDATE ELIMINATION ALGORITHM: initialise S to the most specific hypothesis ⟨∅, ∅, ∅, ∅⟩ initialise G to the most general ⟨?, ?, ?, ?⟩ for each training example d: if d is POSITIVE: remove from G any hypothesis inconsistent with d GENERALISE members of S minimally so they cover d if d is NEGATIVE: remove from S any hypothesis inconsistent with d SPECIALISE members of G minimally so they exclude d THE SYMMETRY IS THE ELEGANT PART: POSITIVE EXAMPLES PUSH S UPWARD (more general), NEGATIVE EXAMPLES PUSH G DOWNWARD (more specific), and the two boundaries converge. A WORKED TRACE, using the attributes above: initial: S = {⟨∅,∅,∅,∅⟩} G = {⟨?,?,?,?⟩} example 1: ⟨Sunny, Normal, Strong, Warm⟩ POSITIVE S must generalise to cover it: S = {⟨Sunny, Normal, Strong, Warm⟩} G is already consistent: G = {⟨?,?,?,?⟩} example 2: ⟨Sunny, High, Strong, Warm⟩ POSITIVE S must generalise where the values differ — Humidity: S = {⟨Sunny, ?, Strong, Warm⟩} G unchanged. example 3: ⟨Rainy, High, Strong, Warm⟩ NEGATIVE S is already consistent (it requires Sunny). G must specialise to exclude it, in every minimal way that keeps the positives: G = {⟨Sunny, ?, ?, ?⟩} (specialising on Humidity or Water would exclude a positive example, so only Sky survives) example 4: ⟨Sunny, High, Weak, Warm⟩ NEGATIVE G must specialise further: G = {⟨Sunny, ?, Strong, ?⟩} S unchanged. FINAL: S = {⟨Sunny, ?, Strong, Warm⟩} G = {⟨Sunny, ?, Strong, ?⟩} The version space is these two plus everything between — here, just one intermediate hypothesis ⟨Sunny, ?, Strong, ?⟩ down to ⟨Sunny, ?, Strong, Warm⟩. THE CONCEPT IS NOT YET UNIQUELY DETERMINED: more examples are needed to decide whether Water matters. WHAT THE VERSION SPACE TELLS YOU, and this is its practical value: · IF IT IS EMPTY, no hypothesis in H is consistent with the data — so either the data contains noise, or H is wrong (the target concept is outside the bias). · IF IT CONTAINS ONE HYPOTHESIS, the concept is determined. · IF IT CONTAINS SEVERAL, the learner does not yet know, and it can identify the MOST INFORMATIVE NEXT QUERY — an instance that half the version space classifies positive and half negative. That is ACTIVE LEARNING, and it is how a good diagnostician chooses the next test.

A LEARNER'S INDUCTIVE BIAS is the set of assumptions that, added to the training data, would logically entail its predictions. A BIAS-FREE LEARNER IS USELESS — the demonstration: Take H to be ALL possible concepts (all 2^24 subsets). The version space is then perfectly represented and never excludes anything unjustified. But consider a new instance x that was never in the training set: exactly HALF the surviving hypotheses classify x positive, and half negative. SO THE LEARNER CANNOT PREDICT ANYTHING about any unseen instance. It has learned only the training set, which it already had. A LEARNER THAT MAKES NO ASSUMPTIONS CAN MAKE NO PREDICTIONS. That is the precise, unavoidable version of the point. EXAMPLES OF INDUCTIVE BIAS IN COMMON ALGORITHMS: CANDIDATE ELIMINATION the target concept is in H (conjunctive) DECISION TREES (ID3) prefer SHORTER trees, and high-information-gain attributes near the root LINEAR MODELS the relationship is linear k-NEAREST NEIGHBOURS nearby instances have the same label NAIVE BAYES the features are conditionally independent given the class NEURAL NETWORKS smooth functions; and for convolutional networks, locality and translation equivariance — the priors identified in the machine vision topic EVERY ALGORITHM IS A BIAS. Choosing an algorithm IS choosing what you assume about the answer, which is why "which algorithm is best?" has no answer independent of the problem. OCCAM'S RAZOR as an inductive bias: prefer the simplest hypothesis consistent with the data. THE JUSTIFICATION, and it is a real argument rather than an aesthetic preference: there are FEWER simple hypotheses than complex ones, so a simple hypothesis fitting the data by coincidence is less likely. If only 10 hypotheses are simple and 10,000 are complex, a simple one that fits is stronger evidence than a complex one that fits. TWO MORE CONCEPTS THAT COMPLETE THE PICTURE: EAGER versus LAZY LEARNING EAGER learners build a model at training time and discard the data — decision trees, neural networks. Training is slow, prediction is fast. LAZY learners store the data and compute at prediction time — k-nearest neighbours. Training is instant, prediction is slow, and the hypothesis is effectively chosen per query, so it can be locally complex. PARAMETRIC versus NON-PARAMETRIC PARAMETRIC models have a fixed number of parameters regardless of data size — linear regression. NON-PARAMETRIC models grow with the data — k-NN, decision trees without depth limits. More flexible, and more prone to overfitting. THE CLOSING POINT FOR THIS TOPIC: LEARNING IS SEARCH THROUGH A HYPOTHESIS SPACE, GUIDED BY DATA AND CONSTRAINED BY BIAS. That framing connects it directly to ACtE0902 — the hypothesis space is a state space, the bias determines its size and shape, and the data provides the evaluation function. THE SAME EXPRESSIVENESS-VERSUS-TRACTABILITY TRADE-OFF APPLIES: a larger hypothesis space can express more and is harder to search reliably.