Due:
at the beginning of class, Tuesday Sept. 16, 2003
For
questions on this assignment, you may contact me (james@cs)
or Myrosia Dzikovska (myros@cs).
Part
A: Written Questions
1. For each answer, explicitly identify the random variables you use, their sample spaces, and summarize the information specified in the question in terms of probabilities.
a. What's the probability that your friend will be late for a movie when it's raining, if the probability of rain is 30%, the probability of your friend being late for a movie is 50%, and the probability of rain given that your friend is late, is 20%?
b. If whether Harry wins a race is independent of how I got to the racetrack, what is the probability that he wins when I drive, if the probability of him winning is .3 and the probability of me driving is .5.
c. An urn contains b blue balls and c cyan balls. A ball is drawn at random, its color recorded and the ball is returned to the urn, and then a ball is drawn again. What is the probability that (i) the first ball drawn is cyan, (ii) the second ball drawn is cyan, (iii) the first two balls drawn are cyan, (iv) that the first ball drawn is cyan given that the second ball drawn is cyan.
2. Answer the same questions as in part (1c), except that whenever a ball is drawn from the urn, when it is replaced, we also add d additional balls of the same color.
3. For two probability distributions P1 and P2, both modeling a random variable X with two values a and b, show that the function defined by
l1 * P1(X) + l2 * P2(X)
is guaranteed to be a probability distribution if both l1 and l2 and greater or equal to 0 and less than or equal to 1, and l1 + l2= 1. If you canąt produce a formal proof, you can get partial credit for laying out how you would prove it, and proving the parts you can.
Part B: Programming
For this assignment, you will be given two corpora: part of the Brown Corpus, which is a corpus of written English including news and fiction texts, and part of the Switchboard corpus, which is a corpus of transcribed informal conversations. Please answer the questions posed for each of these.
1.
Clean up the Copora
The
corpus data in Brown corpus are tagged with parts of speech, in the format
"word/tag", for example, "company/N". Write a Perl program that strips away the tags, leaving only the words
in the corpus. Count the number of words in the corpus.
The
data in Switchboard corpus have annotations about non-verbal noises in square
brackets, such as [laughter] etc. Write a program that removes them from the
corpus. Count the number of words in the corpus, and the number of annotations
you removed.
2.
Collect Data from Corpora:
Given
an untagged corpus, write a Perl program that reads in a corpus and calculates
the frequencies of all words. Answer the following questions
-
What are the 10 most frequent words in the corpus?
- How
many words occurred just once? 2 times? 3 times?
3.
Given the word frequency counts in the corpus, verify how well Zipf's law holds
for this corpus. Zipf's law states that "In the English language, the
probability of encountering the rąth most common word is given roughly by K/r
for r up to 1000, for some constant K". It has been suggested previously
that K=0.1. Answer the following questions:
·
identify the constant K that
best "fits" the data you collect from the two corpora, using some
measure of "fit" of your own design. Justify in the documentation why
your measure of fit is reasonable.
·
For the 50 most frequent
terms in the corpus and your constant K, for how many the frequency is
predicted correctly by Zipf's law within a 5% error margin? Within a 10% error
margin?
·
Is Zipf's law still correct for low frequency terms in the
corpus? Specifically, if a term occurred once, two or three times in the
corpus, is it's frequency correctly predicted within a 5 or 10% error margin
with your constant K?
Please
submit the following for this assignment
·
Your source code files in
Perl. The code should be easy to read and commented appropriately. Please make
sure that the code can be run on the CS network (i.e. it does not use any Perl
modules not globally installed there).
·
The README file that explains
how to run your code, and what to expect in the output. It should include
o
The names of all program
files you submitted, and their command line arguments
o
Examples which show how to
run them
o
The printouts from your test
run
o
The list of known bugs, if
there are and
·
A writeup that answers more
general questions asked in this assignment (you can include it as part of the
README file). As part of the general writeup, describe any problems you
encountered with the data, and how you solved them.
Your grade on the programming part will be based on the following: 50% for a written analysis of your approach, discussion of what testing and evaluation you did to verify the use of your approach, and documentation on how to use your program, 25% for well-written code, and 25% for the results of running on the test corpora.