050.371/671 - Formal Methods in Cognitive Science
Problem Set 5
Due May 3, 2000
Problem 1
Imagine that you land on a far away island on which there are three tribes
which speak three different languages. The language of the first tribe,
which we will call L1, consists of the single word ``Rock'',
the second one, L2, consists of the two words ``Rock'' and ``Scissors'',
and the third, L3, includes the three words ``Rock'', ``Scissors''
and ``Paper''. Since each of these groups is rather hostile to the others,
you are well advised to figure out as quickly as possible the language
of the group with which you are interacting. You remember that an anthropologist
friend of yours, who had once visited this very same island, told you that
all members of these tribes had the curious property that they could not
help naming any object with which they came into contact, so long as the
language they spoke had a word for the object. So, whenever a member of
the third tribe encounters a rock, a pair of scissors or a piece of paper,
he feels compelled to cry out ``Rock'', ``Scissors'' or ``Paper'', as appropriate.
In contrast, members of the second tribe would cry out ``Rock'' or ``Scissors''
whenever coming across a rock or a pair of scissors, but would remain silent
in the face of a piece of paper. Members of the first tribe remain silent
for all objects but rocks.
Part A: You come across a native and decide to follow him around
for a while in order to figure out the language that he speaks. Give a
learning algorithm L that will use
your observations, each one consisting of a pairing of an object (either
rock, scissors or paper) with a verbal response (either ``Rock'', ``Scissors'',
``Paper'' or silence) to figure out which language your companion speaks.
Part B: You suddenly remember that your anthropologist friend
had told you that on this island, there were twice as many rocks as there
were pairs of scissors, and three times as many pairs of scissors as pieces
of paper. Cleverly, you infer that the probability that your newfound native
friend will come across a rock in his travels is twice the probability
of coming across a pair of scissors, which in turn is three times the probability
of coming across a piece of paper. Doing some quick algebra, you conclude
that
m({rock}) = .6, m({scissors})
= .3,m({paper}) = .1. Suppose now that you are
faced with the following sequence of observations of your native friend:
| sees |
says |
| rock |
``Rock'' |
| paper |
- |
| rock |
``Rock'' |
You hastily conclude that your friend must speak L1. If it
turns out that your friend actually speaks L2, what is the error
set for your hypothesis? If you wanted to achieve 85% accuracy, would this
be good enough? That is, is erm(L1,L2)
< .85?
Part C: Continue to assume that your friend actually speaks L2.
Of all the possible sequences of observations of length 3, which ones would
incorrectly lead the learning algorithm L
you gave in part A to an incorrect conclusion? What is the probability
that a sequence of 3 observations will be one of these (i.e.,
m3{s
Î S(3,L2)|
L(s) = L2})? What is the
probability of such a misleading sequence in the case of an arbitrary number
n of observations? State how many observations you would need to reach
90% confidence that your hypothesis was correct by finding the least m
for which
| mm{s Î
S(m,L2)| L(s)
= L2} > .9 |
|
Suppose that you only require that your hypothesis be 85% accurate. Determine
the number of observations that would now be required to obtain 90% confidence
by finding the least m for which
| mm{s Î
S(m,L2)| erm(L(s),L2)
< .85} > .9 |
|
Part E: Suppose that your friend speaks L3. What is
the probability that a sequence of n observations will lead your learner
to an incorrect conclusion (i.e., m3{s
Î S(3,L3)|
L(s) = L3})? In this case,
how many observations would be required to reach 90% confidence that your
hypothesis is correct, i.e., what is the least m for which
| mm{s Î
S(m,L3)|L(s)
= L3} > .9 |
|
What happens in this case to the number of observations m required for
90% confidence if you were to only require 85% accuracy? That is, what
is the least m for which
| mm{s Î
S(m,L3)| erm(L(s),L3)
< .85} > .9 |
|
Problem 2
Chapter 3, Exercise 5 from Anthony and Biggs text.
File translated from TEX by TTH,
version 2.25.
On 26 Apr 2000, 01:07.