Lecture 13 · The inferences

Induction at scale.

Examples constrain; they rarely identify. The engine is search over discrete hypotheses — and the honest output is a version space, not a single truth.

9 sections 441 rules in the lab 1 version-space lab Self-paced
00 · Learning objectivesLecture 13 · Induction at scale

By the end of this lecture

Four things you can do.

01

Separate induction from fitting

Name the hypothesis space, the consistency test, and the discrete artifact a rule learner returns.

02

Read a version space

Find the S and G boundaries, and say which unlabelled cases the examples decide.

03

Explain the search

Describe DSL enumeration, and how DeepCoder, DreamCoder, and LLM proposers guide it.

04

State the limits

Say what consistency, synthesis, and PAC guarantees assume — and where induction fails.

S/V · Lecture 13
00 · The hookLecture 13 · Induction at scale

A conveyor belt, six labels

What is the rule?

ObjectColourShapeSizeMaterialLabel
c1redcubesmallmetal+
c2redcubelargerubber+
c3redcubelargemetal+
s1redspheresmallmetal−
b1bluecubelargemetal−
g2greencylindersmallmetal−
r1redcylindersmallrubber?
g1greencubelargerubber?

Three positives, three negatives, two unlabelled objects. A rule that fits the six labels is a hypothesis about the rest.

But the labels do not pick one rule. They eliminate some; they leave several alive.

The task is not “predict the next label.” It is “characterize the rules that fit.”

S/V · Lecture 13
00 · The hookLecture 13 · Induction at scale

The examples do not decide

Three rules, two disagreements.

Rule 1

red ∧ cube

Covers c1, c2, c3. Rejects r1 and g1. The safest rule.

Rule 2

red ∧ (cube ∨ cylinder)

Covers c1, c2, c3, r1. Accepts red cylinders.

Rule 3

(red ∨ green) ∧ cube

Covers c1, c2, c3, g1. Accepts green cubes.

ObjectLabelRule 1Rule 2Rule 3
c1, c2, c3 (red cubes)+acceptacceptaccept
b1 (blue sphere)−rejectrejectreject
r1 (red cylinder)unlabelledrejectacceptreject
g1 (green cube)unlabelledrejectrejectaccept

r1 and g1 are the ambiguity. Rule 1 rejects both; Rule 2 accepts r1; Rule 3 accepts g1. The data cannot choose.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale
01 / 08

From examples to a hypothesis space.

The examples filter. The language decides what can survive.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale

Induction is constrained search

Cover the positives. Exclude the negatives.

h* ∈ { h ∈ H : ∀p ∈ P, B ∧ h ⊨ p   and   ∀n ∈ N, B ∧ h ⊭ n }H is the hypothesis space, B the background knowledge, P the positives, N the negatives.

H

The rules or programs the learner may return. This is the bias.

B

What is already known: facts, types, a family tree, a DSL.

E

The labels. They eliminate hypotheses; they rarely identify one.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale

Two kinds of induction

A vector is not a rule.

AspectStatistical fittingRule / program induction
HypothesisParameter vector θDiscrete rule, clause, or program
FitMinimize empirical riskCover positives; exclude negatives
OutputWeights, scores, a boundaryAn artifact you can read and execute
GeneralizationSimilarity under the distributionEntailment or execution on new inputs
Typical failureShortcuts, shift, opacityWrong language, overgeneralization, search

A neural network is also a hypothesis space. The difference is what the learner returns, and what “fit” means.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale

Generality is a partial order

S is specific. G is general.

Version space. Every hypothesis in H that covers all positives and no negative.

S. The most specific consistent hypotheses — the least general generalization of the positives.

G. The most general consistent hypotheses — the rules that cannot be relaxed without covering a negative.

h1 ≥ h2 iff ext(h1) ⊇ ext(h2). The gap between S and G is the ambiguity.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale

The whole version space

Three rules. Two boundaries.

RuleBoundaryCoversDecides
colour = red ∧ shape = cubeSc1 c2 c3rejects r1 and g1
colour = red ∧ shape ∈ {cube, cylinder}G1c1 c2 c3 r1accepts r1
colour ∈ {red, green} ∧ shape = cubeG2c1 c2 c3 g1accepts g1

Identifiable means S = G: every consistent rule agrees on every object. Ambiguous means the gap is non-empty. The lab counts both.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale

Interactive · toggle a negative

Watch the space move.

Positives are fixed: c1, c2, c3. Toggle which negatives are in the dataset.

With all three, the space has two G rules. Remove g2 and the two branches merge into one maximal rule. Remove s1 and the shape constraint relaxes: spheres become allowed.

Consistent—
G rules—
Ambiguous—

S—

G—

Loading the 441-rule space.

S/V · Lecture 13
01 · Induction from examplesLecture 13 · Induction at scale

Relational induction

A variable is the new feature.

parent(ali, reza).   parent(reza, sara).
parent(sara, omid).   parent(ali, mina).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Relations

The concept is a pattern between objects, not an attribute of one.

Background knowledge

The parent facts are the prior. Change them and the hypothesis changes.

Language bias

Predicates, argument types, recursion. The space of all programs is too large.

FOIL grows clauses top-down; Progol works bottom-up; Metagol learns higher-order programs. Consistency checking is NP-hard.

S/V · Lecture 13
02 · Programs & DSLsLecture 13 · Induction at scale
02 / 08

The hypothesis is a program.

A grammar defines the space; a cost function chooses inside it.

S/V · Lecture 13
02 · Programs & DSLsLecture 13 · Induction at scale

The grammar is the bias

A program space you can name.

e ::= x | map(f, e) | filter(p, e) | reverse(e)
    | take(n, e) | drop(n, e) | sum(e)
f ::= inc | double | neg
p ::= even | positive

Primitives

What can appear in a program. Add fold and the space grows.

Types

sum is a number, so it cannot be an argument to map. Types prune.

Cost

AST size, or a learned prior. The cost breaks ties the data cannot.

Remove reverse and no amount of data produces a reversal program. The primitives are knowledge.

S/V · Lecture 13
02 · Programs & DSLsLecture 13 · Induction at scale

Search by size

The smallest program wins — by convention.

ProgramSizeFits [1,2,3]→[2,3,4]?Why not chosen
map(inc)1yeschosen: smallest
map(inc) ∘ reverse ∘ reverse3yesequal on every list; larger
map(λx. x+1 if x>0 else x)—yes, on positivesnot in the DSL; differs on negatives

The examples filter; the language and the cost choose. There is no unique “program that fits.”

S/V · Lecture 13
02 · Programs & DSLsLecture 13 · Induction at scale

Induction meets deduction

Propose, check, add a counterexample.

01 · propose

The synthesizer returns a program consistent with the current examples.

02 · verify

A checker tests it against the full specification, not just the sample.

03 · counterexample

A failure is added to the examples; the search resumes.

04 · accept

No counterexample: correct relative to the specification.

examples length([]) = 0 propose length verify fails on [1,2] — expected 2, got 2? no: length gives 2; pass next fails on [[1],[2,3]] — a counterexample is added repair a program that flattens before counting

The verifier is the guarantee. If the specification is only a finite sample, “verified” means “fits the sample.”

S/V · Lecture 13
03 · Neural guidanceLecture 13 · Induction at scale
03 / 08

Neural guidance.

Make the search smaller, not the answer certain.

S/V · Lecture 13
03 · Neural guidanceLecture 13 · Induction at scale

The bottleneck

Complete search is exponential.

Programs

The number of programs grows exponentially with AST size. Depth 12 quickly outgrows enumeration.

Examples

Examples prune; they do not shrink the grammar. A bigger sample helps, but the space is still there.

Guidance

A score orders candidates, or a policy proposes primitives. The search becomes heuristic.

LeverWhat it changesWhat it does not
Type/arity pruningRemoves ill-typed candidates; soundDoes not order the survivors
ExamplesFilters candidates after evaluationDoes not shrink the grammar
A learned scoreOrders candidates; may be wrongDoes not preserve completeness

“At scale” means guided and checked, not complete and guaranteed.

S/V · Lecture 13
03 · Neural guidanceLecture 13 · Induction at scale

DeepCoder · 2017

Predict the primitives, then search.

score(f | E) → keep top-k primitives → enumerate programs built from themThe network is trained on a corpus of generated programs and their input–output examples.

What it buys

The search space shrinks by orders of magnitude. The enumerator stays exact inside the restricted space.

What it costs

If the true primitive is not in the top-k, the program cannot be found. A wrong prior turns completeness into incompleteness.

S/V · Lecture 13
03 · Neural guidanceLecture 13 · Induction at scale

DreamCoder · 2021

Grow the language.

Wake

Symbolic search solves tasks and writes programs. The solutions are the data.

Sleep

A recognition model proposes abstractions; the library is refactored to compress the corpus.

New abstractions join the DSL, so later searches can use them. Library learning changes the hypothesis space, not just its order.

Cost: compute, a base DSL, and a corpus. The base DSL is still the ceiling; compression is a heuristic, not a proof.

S/V · Lecture 13
03 · Neural guidanceLecture 13 · Induction at scale

LLMs as proposers

Propose, execute, repair.

prompt → candidate program
executor → pass / fail on the examples
failure → counterexample → revised prompt

Codex

Functions from docstrings; unit tests are the check.

AlphaCode

Many candidates; sample tests filter them.

FunSearch

LLM proposes mutations; an evaluator selects.

The checker remains the guarantee. Visible tests are not hidden tests; an evaluator is not the intent.

S/V · Lecture 13
04 · Few-shot inductionLecture 13 · Induction at scale

In-context induction

Examples in the prompt, no weight update.

red cube → accept
red sphere → reject
blue cube → reject
green cube → ?

The model answers. Change the examples and the answer changes. Behaviourally, this is induction.

But no hypothesis is returned. The rule is implicit in the computation; you can probe it, not inspect it.

Flexible, natural-language priors, no DSL. And no version space, no coverage set, no certificate.

No weights change. The hypothesis is not returned; only behavior you can probe.

The prompt is a specification you cannot read. It changes the answer without leaving an artifact you can inspect.
S/V · Lecture 13
04 · Few-shot inductionLecture 13 · Induction at scale

Mechanism, not magic

Several algorithms fit the behavior.

Retrieval

The prompt evokes a similar task from pretraining.

Gradient-like

Linear attention can implement steps of gradient descent or ridge regression.

Bayesian

In-context learning as inference over latent concepts.

Garg et al. (2022), Akyürek et al. (2022), von Oswald et al. (2022), Olsson et al. (2022), Xie et al. (2022): existence proofs on controlled tasks, not a theory of frontier models.

Same behavior, different algorithms. A mechanism claim needs an intervention, not a correlation.
S/V · Lecture 13
05 · What is learnedLecture 13 · Induction at scale

The artifact decides what you can check

A program, a rule, a representation.

Program

map(inc)

Executable, composable. Check on held-out inputs. Cost: a DSL.

Rule

grandparent(X,Z)

Entailable, explainable. Check coverage in B. Cost: a logic language.

Representation

a vector

Transferable. Probe it, test downstream. Cost: opacity; many rules fit.

Behaviour underdetermines the hypothesis. A probe that finds a feature does not prove the model uses it.

Ask what artifact the method returns before asking what it learned: a program, a rule, or a representation supports a different check.
S/V · Lecture 13
05 · What is learnedLecture 13 · Induction at scale

Choosing inside the space

Pick one, and say why.

h* = argminh ∈ H   L(h) + L(E | h)Minimum description length: the hypothesis plus the data given the hypothesis.

Both red ∧ cube and (red ∨ green) ∧ cube fit the labels. The shorter rule rejects the green cube g1; the longer one accepts it. If the intended rule is the longer one, the simplicity prior is wrong.

Kolmogorov complexity is uncomputable and language-dependent. In practice the DSL supplies the code; “shortest” means shortest in that DSL.

S/V · Lecture 13
06 · Guarantees & limitsLecture 13 · Induction at scale

What the induction buys

Every guarantee has an assumption.

ClaimGuaranteesAssumes
Version-space consistencyAll positives covered, no negative coveredH fixed; labels noise-free
Identifiability (S = G)All consistent rules agree on every objectThe boundaries coincide; H fixed
Synthesis correctnessThe program satisfies the specificationChecker sound; search complete
PAC boundTrue error ≤ ε with probability 1−δFinite H; i.i.d. data; target in H

None of these says the learned rule is true. They say it is correct relative to the language, the examples, and the checker.

S/V · Lecture 13
06 · Guarantees & limitsLecture 13 · Induction at scale

What goes wrong

Empty, overgeneral, or wrong language.

Empty space

No rule covers the positives and excludes the negatives. The language is too weak, the labels conflict, or the data are noisy.

Overgeneral

A rule near G ignores distinctions the sample never tested. A rule near S commits to noise.

Ambiguity

Finite examples leave many rules. “Grue” is the philosophical version: the data do not choose the predicate.

And the practical one: benchmarks leak. A model may have seen the test set; a DSL may be tuned to the task.

An empty version space is a diagnosis; ambiguity is the information content of the sample. Neither is a crash.
S/V · Lecture 13
07 · CasesLecture 13 · Induction at scale

Five systems, one anatomy

Same search, different bias.

SystemHypothesis spaceGuidanceCheck
FlashFillString DSLVersion-space search + rankingUser examples
DeepCoderList/arithmetic DSLNeural primitive predictionExamples
DreamCoderGrowing DSLRecognition model + compressionTask solutions
AlphaCodeGeneral programsLLM proposalsSample tests
FunSearchProgram populationLLM mutations + evaluatorEvaluator

The pattern repeats: a language, a proposer, a checker. The differences are in what the checker can see.

S/V · Lecture 13
08 · RecapLecture 13 · Induction at scale

Recap

What you can now do.

01 · Separate

Rule induction returns a discrete artifact judged by coverage; fitting returns weights judged by loss.

02 · Read

S and G bound the version space; unlabelled cases between them are ambiguous.

03 · Relate

ILP adds variables, relations, and background knowledge to the hypothesis language.

04 · Synthesize

A DSL is the hypothesis space; a cost function is the prior; CEGIS adds a checker.

05 · Guide

DeepCoder prunes, DreamCoder grows the language, LLMs propose and get checked.

06 · Limit

Consistency is not truth; a finite spec underdetermines the program; benchmarks leak.

S/V · Lecture 13
08 · RecapLecture 13 · Induction at scale

Next · hands-on

Break the version space.

Open the lab. Relabel one object at a time. Watch S and G move, and watch an unlabelled object become decided — or stay ambiguous.

Lab 13 · Rules from examples → open the lab

Bring one rule you believe, one example that could refute it, and the version space you can defend.

S/V · Lecture 13
Speaker notes