CogSci 131
The problem of induction
Tom Griffiths
string = computation;
disp(string);
thought
Minds and computers are both formal systems
Computational problems
Problems of deduction and search:
arithmetic, algebra, chess
We know what the underlying formal
system should be for these problems
we know how computers can solve these
problems (at least in principle)
in many cases, computers can solve these
problems better than people
Computational problems
Problems of deduction and search:
arithmetic, algebra, chess
But what about:
learning and using language
sophisticated senses: vision, hearing
similarity and categorization
inferring causal relationships
scientific investigation
Outline
Inductive problems
Break
The problem of induction
Inductive problems
Evaluating a set of hypotheses whose truth
is underdetermined by the available data
Examples:
learning and using language
sophisticated senses: vision, hearing
similarity and categorization
inferring causal relationships
scientific investigation
Learning language
Red: Target language
Blue: Current hypothesis
Multiple hypotheses can be consistent with the data
Learning language
Gavagai!
Hypotheses: (all consistent)
Rabbit
Dinner
Rabbit before t, dinner after
Undetached rabbit parts
Momentary rabbit-stage
Mass of rabbithood
Temporal cross-section of a
four-dimensional spacetime extension of a rabbit
Vision
Two consistent hypotheses:
a cube
a cunningly shaded 2D shape
Vision
Vision
Vision
Categorization
Categorization
cat small furry domestic carnivore
How do you find the appropriate rule?
Scientific discovery
Halley, 1752
75 years
76 years
Inductive problems
inductive problems
PQ
P
Q
PQ
PQ
PQ
PQ
PQ
Q
P
deduction
induction
abduction
Causal induction
PQ
PQ
PQ
PQ
PushSwitch Light
PushSwitch Light
PushSwitch Light
PushSwitch Light
Causal reasoning
PQ
Q
P
PushSwitch Light
Light
PushSwitch
Inductive problems
PQ
P
Q
PQ
PQ
PQ
PQ
deduction
induction
PQ
Q
P
abduction
Philosophers: a puzzle, a scandal, a myth
Break
Up next:
The problem of induction
Three problems
Platos problem
how do we know so much?
why are our inductions so successful?
Humes problem
induction can only be justified by induction
Goodmans new riddle
no simple syntactic rules for induction
Three problems
Platos problem
how do we know so much?
why are our inductions so successful?
Humes problem
induction can only be justified by induction
Goodmans new riddle
no simple syntactic rules for induction
Humes problem
Inductive inferences assume that the
future will be like the past
What is the basis for this assumption?
It is impossible that any arguments from experience
can prove this resemblance from past to future; since all
these arguments are founded on the supposition of that
resemblance.
Induction can only be justified by induction
The No Free Lunch Theorem
(Wolpert)
Averaged over all possible worlds, no learning
algorithm is better than any other
e.g.sequence prediction: given x1, x2, predict x3
000
001
010
Worlds: 011
100
101
110
111
00
00
01
Data: 01
10
10
11
11
0
1
0
Correct answer: 1
0
1
0
1
The No Free Lunch Theorem
(Wolpert)
In order for an algorithm to work better, the
distribution over worlds must be constrained
e.g.the future is like the past
000
001
010
Worlds: 011
100
101
110
111
00
00
01
Data: 01
10
10
11
11
0
1
0
Correct answer: 1
0
1
0
1
Anthropic argument
Goodmans response
Induction is no less justified than deduction
the formal system underlying deduction was
refined to confirm to our intuitions
the same process can yield rules for induction
Instead of searching for justification, we
should search for the rules of induction
what learning algorithm do people use?
Some inductions are better than others
Better and worse inductions
PushSwitch Light
PushSwitch Light
PushSwitch Light
PushSwitch Light
September17 Light
September17 Light
September17 Light
September17 Light
quality differs, despite the same syntax
suggests were missing some premises
The new riddle
Only a statement that is lawlike is capable of
receiving confirmation from an instance of it;
accidental statements are not. Plainly, then, we must
look for a way of distinguishing lawlike from
accidental statements.
What makes a statement lawlike (projectible)?
Grue
Grue = Green before t, blue after t
Observe three green emeralds before t
Both all emeralds are green and all
emeralds are grue are equally confirmed
So why is green lawlike, but not grue?
Syntactic complexity
Grue = Green before t, blue after t
This is a complicated property - perhaps
induction only works with simple properties?
Green = Grue before t, bleen after t
where bleen = Blue before t, green after t
Goodmans conclusion
lawlike or projectible hypotheses cannot be
distinguished on any merely syntactical grounds
There is some kind of extra knowledge (as to
what is projectible) that enters into our
inductive inferences
So there might be rules of induction, but
they need to take this knowledge into account
The challenge for formal systems
Our best example of a formal system is
deductive logic, but induction has its own rules
Its not clear that assumptions like simple
truth or falsehood apply
are you 100% sure this is the grammar?
are you 100% sure this is a cat?
are you 100% sure the comet will return?
The challenge for formal systems
Inductive problems:
learning and using language
sophisticated senses: vision, hearing
similarity and categorization
inferring causal relationships
scientific investigation
The situation differs from deductive problems:
what are the formal rules for induction?
how can computers solve these problems?
string = computation;
disp(string);
thought
Minds and computers are both formal systems
Making computational models
Goodman suggests that we identify formal
rules by iterative refinement
1. Develop models of inductive inferences
2. Test those models against human data
3. Modify models in light of data
The challenge of induction
Why is a single instance, in some cases,
sufficient for a complete induction, while in others
myriads of concurring instances, without a single
exception known or presumed, go such a very
little way towards establishing a general
proposition? Whoever can answer this question
knows more of the philosophy of logic than the
wisest of the ancients, and has solved the
problem of Induction.
John Stuart Mill (A System of Logic, 1843)
Next week
Typicality and categorization
fuzzy borders and uncertainty
Part II: Similarity, spaces, and features
