18th April 2002

75 minutes

I. Latent Semantic Analysis (LSA)

(7 marks)

Consider a vocabulary of four words: { and, language, processing, speech }. Let a phrase "speech and language processing" be under speech recognition process. Using Bellegarda's 'N-gram + LSA language modeling' method, calculate the bi-lsa probability:

P^bi-lsa( processing | speech, and, language )

This requires first to calculate LSA-based probability

P^lsa ( w_q = processing | H_q-1 = {speech, and, language} )

and then to integrate it with bi-gram probability. The LSA-based probability is given by

where,

The LSA space was constructed using 2 latent dimensions with corresponding singular values of 2 and 1 respectively. The following information is available:

II. K-means Clustering

(7 Marks)

1. Construct an example data set for which the K-means algorithm takes more than one iteration to converge.
2. A data set consists of 4 points arranged at the vertices of a square and the k-means clustering procedure is run for k=2 clusters.
   • How many stable cluster solutions are possible? Draw them and show.
   • Which of these clusterings are globally optimum and which are sub-optimal in the sense of Euclidean distances?

III. Tri-gram Tagging

(5 Marks)

1. Derive the tagging sequence arg max_t1,n P (t_1,n / w_1,n) under the assumptions:
   • words are independent of each other
   • a word's identity only depends on its tag
   • the current tag depends on the previous two tags
2. Draw an HMM for this tri-gram tagger.

IV. Similarity Measures

(5 Marks)

1. Consider the following sentences:

   An electron is round.

   A ball is spherical.

   In this case ball and electron are semantically similar in the context of shape.

   However in the following sentences:

   An electron is tiny.

   That ball is huge.

   ball and electron are semantically dissimilar in the context of size.

   • Find the vector space similarity in the two cases. Suggest ways to bring out the inherent knowledge contained in the sentences for correct classification of similarity.
   • How about if in the second set of sentences the second sentence were "That ball is small." What method will work on this?

2. The standard vector space model tries to return the document that most closely approximates the query, given that both query and document are vectors defined by their word occurrence. On the web, this strategy often returns very short documents that are the query plus a few words.
   • Explain why this is so.
   • Suggest ways of overcoming this.