HW2, CS769

Nathanael Fillmore

Due Feb. 8, 2008

1 Text Processing

Question 1.

33345 tokens (cat stem|wc -w),

2245 types (cat stem|sed -e's/ $//g' -e's/\ /\n/g'|sort|uniq|wc -l)

Question 2.

$ cat stem|sed -e's/ $//g' -e's/\ /\n/g'|sort|uniq -c|less|sort -nr|head -n 10
2418 ,
1618 the
1106 '
 961 .
 810 and
 720 to
 620 a
 596 it
 545 she
 499 of

Question 3.

$ cat stem|sed -e's/ $//g' -e's/\ /\n/g'|sort|uniq -c|sort -nr|
  sed -e's/^*//' -e's/ .*$//'|grep -n '$'|sed -e's/:/ /'>q3data
matlab>>
load q3data;
plot(q3data(:,1), q3data(:,2), 'o');
xlabel('rank'); ylabel('count'); saveas(1, 'q3plot.eps');

loglog(q3data(:,1), q3data(:,2), 'o');
xlabel('rank'); ylabel('count'); saveas(1, 'q3loglog.eps');

The plots seem to fit Zipf’s law, with an inverse relation between rank and count and an almost straight line in the log-log plot.

Question 4.

A monkey hits A with probability p and white space with probability 1 − p. Derive the rank and frequency function relation on monkey words.

Pr(A) = p(1 − p) Pr(AA) = pp(1 − p) Pr(AAA) = ppp(1 − p) Pr(A n times) = p^{n}(1 − p)

2 Language Modeling

Question 5. 9723

$ cat tr.text |./text2wfreq |./wfreq2vocab -gt 4 > tr.vocab
text2wfreq : Reading text from standard input...
wfreq2vocab : Will generate a vocabulary containing all words which
              occurred more that 4 times. Reading wfreq stream from stdin...
              text2wfreq : Done.
              Size of vocabulary = 9723
              wfreq2vocab : Done.

Question 6. 633.84 perplexity on test corpus; 679.24 perplexity on training corpus.

$ cat tr.text | ./text2idngram -n 1 -vocab tr.vocab > tr.n1.idngram
[...]
$ cat > movie.ccs
<s>
$ idngram2lm -idngram tr.n1.idngram -vocab tr.vocab -context movie.ccs -n 1 -binary tr.n1.binlm
[...]
$ ./evallm -binary tr.n1.binlm
[...]
evallm : perplexity -text test.text
Computing perplexity of the language model with respect
   to the text test.text
   Perplexity = 633.84, Entropy = 9.31 bits
   Computation based on 713316 words.
   Number of 1-grams hit = 713316  (100.00%)
   56580 OOVs (7.35%) and 32957 context cues were removed from the calculation.
evallm : perplexity -text tr.text
Computing perplexity of the language model with respect
   to the text tr.text
   Perplexity = 679.24, Entropy = 9.41 bits
   Computation based on 680783 words.
   Number of 1-grams hit = 680783  (100.00%)
   42002 OOVs (5.81%) and 31763 context cues were removed from the calculation.

Question 7. 224.41 perplexity on test corpus; 105.07 perplexity on training corpus.

$ cat tr.text | ./text2idngram -n 2 -vocab tr.vocab > tr.n2.idngram
[...]
$ idngram2lm -idngram tr.n2.idngram -vocab tr.vocab -context movie.ccs -n 2 -binary tr.n2.binlm
[...]
$ evallm -binary ./tr.n2.binlm
[...]
evallm : perplexity -text test.text
Computing perplexity of the language model with respect
   to the text test.text
Perplexity = 224.41, Entropy = 7.81 bits
Computation based on 713316 words.
Number of 2-grams hit = 577029  (80.89%)
Number of 1-grams hit = 136287  (19.11%)
56580 OOVs (7.35%) and 32957 context cues were removed from the calculation.

evallm : perplexity -text tr.text
Computing perplexity of the language model with respect
   to the text tr.text
Perplexity = 105.07, Entropy = 6.72 bits
Computation based on 680783 words.
Number of 2-grams hit = 680783  (100.00%)
Number of 1-grams hit = 0  (0.00%)
42002 OOVs (5.81%) and 31763 context cues were removed from the calculation.

Question 8. 202.66 perplexity on test corpus; 28.87 perplexity on training corpus.

$ cat tr.text | ./text2idngram -n 3 -vocab tr.vocab > tr.n3.idngram
[...]
$ idngram2lm -idngram tr.n3.idngram -vocab tr.vocab -context movie.ccs -n 3 -binary tr.n3.binlm
[...]
$ evallm -binary ./tr.n3.binlm
Reading in language model from file ./tr.n3.binlm
Done.
evallm : perplexity -text test.text
Computing perplexity of the language model with respect
   to the text test.text
Perplexity = 202.66, Entropy = 7.66 bits
Computation based on 713316 words.
Number of 3-grams hit = 306876  (43.02%)
Number of 2-grams hit = 270153  (37.87%)
Number of 1-grams hit = 136287  (19.11%)
56580 OOVs (7.35%) and 32957 context cues were removed from the calculation.
evallm : perplexity -text tr.text
Computing perplexity of the language model with respect
   to the text tr.text
Perplexity = 28.87, Entropy = 4.85 bits
Computation based on 680783 words.
Number of 3-grams hit = 680782  (100.00%)
Number of 2-grams hit = 1  (0.00%)
Number of 1-grams hit = 0  (0.00%)
42002 OOVs (5.81%) and 31763 context cues were removed from the calculation.

Question 9. (XXX revise:) As the LMs become more complicated, i.e. as the n-grams become longer, the perplexity against the training data decreases significantly, while the perplexity against the test data decreases, but not as much. This makes sense, since in the case of trigrams, there are only a few choices for the third word of a trigram in the training corpus, while in the testing corpus, this is still true but in many cases the third word which appears won’t have appeared in that position in the training corpus. In the case of 2-grams this is less likely, and in the case of 1-grams it is not an issue at all—which is why we observe that the 1-gram perplexity against the training corpus is actually higher than against the testing corpus.

Question 10. P(the) = 0.0508201, P(movie) = 0.00350727, P(mulan) = 5.6725e-05, P(album) = 6.91769e-06.

$ evallm -binary ./tr.n1.binlm
[...]
evallm : perplexity -text tr.vocab.copy -probs vocab.probs
Computing perplexity of the language model with respect
   to the text tr.vocab.copy
Probability stream will be written to file vocab.probs
Perplexity = 46214.93, Entropy = 15.50 bits
Computation based on 9722 words.
Number of 1-grams hit = 9722  (100.00%)
0 OOVs (0.00%) and 0 context cues were removed from the calculation.