Ling 361, Intro to Computational Linguistics
fall 2002

Remember that you are encouraged to collaborate on homework problems, but each person should turn in a separate assignment.

If you wish, you may e-mail this assignment to me as an attachment in a textfile, Microsoft Word, or Rich Text Format (RTF).

1. Do exercise 8.1 from Jurafsky and Martin, on p. 319.

2. Do exercise 9.1 from Jurafsky and Martin, on p. 355. The grammar in fig. 9.3 on p. 330 should handle all but a couple of the phrases in this exercise. Which ones? What rule would you add to this grammar to handle them? (Notice that a common English part of speech isn't mentioned in this grammar.)

3. a. Explain the sources of ambiguity present in the following sentences:

1. We saw that gasoline can explode.
2. Where did you say she kissed him?
3. I forgot how good beer tastes.

b. Test the CMU Link Parser using these three sentences. Make sure that all three boxes (including "show all linkages") below the window in which you type the sentences are checked. The output will look somewhat different from the trees used in Jurafsky and Martin, since this is a "link" or "dependency" parser. Does the parser find structures for all the meanings you found? If you noted readings that its output doesn't indicate, why do you think it doesn't distinguish them?

4. Suppose you are considering buying a telescope and want to find out what the expression "limiting magnitude" means. So you go to your search engine and enter the terms telescope, limiting, and magnitude. Here are some relevant portions of possible responses you might get. The first three are the first sentences from the top three documents returned for this query by Google, while the last is a definition from an old astronomy book I happened to unearth recently:

1. "The parameters below all effect the limiting magnitude of the dimmest star that you can see through your telescope." (from http://www.go.ednet.ns.ca/~larry/astro/maglimit.html)
2. "In the course of either buying or using a telescope, it would be nice to know how much more powerful the telescope is than your eye in gathering light. You would also like to have an idea of what the faintest magnitude you can see would be." (from http://www.astrodigital.org/astronomy/seeing.html)
3. "Limiting magnitude calculations: Use this form to calculate the faintest star you can see for a given place, time and observer." (from http://www.astro.columbia.edu/~ben/star.html)
4. "The limiting magnitude of a telescope is the magnitude of the faintest stars that can be seen with that telescope under ideal conditions." (from Exploration of the Universe, by George O. Abell)

b. Suppose there are 24 documents in the entire collection, and that these four are the only ones that contain any of the query terms. Find the inverse document frequency for each of the three terms. Then recalculate the vector components for each document as the product of term frequency and idf (you can leave the query vector as it is). What is the dot product of the query vector with each of these vectors? What is the cosine of the angle between the query vector and each of these vectors? Did the ranking of document relevance by cosine change?

You can use the following (very rough) approximations for logarithms in your calculations:

x	1	2	3	4	5	6	7	8
log(x)	0	1	1.5	2	2.25	2.5	2.75	3

c. Now suppose that magnitude appears in 12 out of the 24 documents in the collection. Recalculate the components of each of the document vectors, their dot products with the query vector, and the cosine of the angle between the query vector and each of these vectors. How did the change in the idf of magnitude affect your results?

Back to the main syllabus page