COS 435, Spring 2008 - Problem Set 1

Collaboration Policy

You may discuss the general methods of solving the problems with other students in the class. However, each student must work out the details and write up his or her own solution to each problem independently. 

Lateness Policy

• Penalized 10% of the earned score if submitted by 5:00 pm Thursday (2/21/08).
• Penalized 25% of the earned score if submitted by 1:30 pm  Monday(2/25/08).
• Penalized 50% if submitted later than 1:30 pm  Monday (2/25/08).

Problems

Problem 1 
Consider combining the vector model with the "set of terms" model for documents and queries.  In this case,  for a dictionary of t index terms, each document is a t-dimensional vector whose j^th component is a 1 if the document contains one or more instance of the j^th term and is a 0 otherwise.  Query vectors are defined analogously.  

• Part a:  Consider the distance dissimilarity metric and dot product similarity metric without normalization by the length of the vectors:  Dist(d, q)  = √(Σ_i (d_i – q_i)² ) and d•q  = Σ_i (d_i * q_i).   Express each metric as a function of the number of distinct terms ("1"s) in document d, the number of distinct terms in query q, and the number of terms shared by d and q.
  

• Part b: Under this 0/1 vector model, do the dot product metric and the distance metric produce the same ordering of documents by similarity to a query? (Increasing order of distance from query and decreasing order of dot product with query. ) If yes, why. If not,  give an example and describe the difference between the similarity rankings.

Problem 2

• Part a:  An Introduction to Information Retreival Exercise 6.18, pg 131:  (Paraphrasing) Consider a query q and documents d₁, d₂,..., in the (general) vector model.  Show that if q and the d_i are all normalized to unit vectors, then the rank order produce by ranking the documents d_i in order of increasing Euclidean distance from q is identical to the rank order produced by ranking the documents d_i in order of decreasing dot product with q.  (Note that the cosine similarity measure is normalized by definition: (d•q) / (|d|*|q|) .) 
  

• Part b:  What changes in Problem 1, part b when vectors are normalized to unit vectors?  Why?

Problem 3
In class we discussed ways one might add ranking to the Boolean model of queries.  In this problem, consider more specifically combining Boolean queries with the vector model for ranking.  In the combined model, a document will still only satisfy a query if it evaluates to "true".   How might you rank the documents that satisfy the query using a vector scoring technique?  What  query vector would you use for scoring, and what metric would you use?  Do a small example of your choosing to illustrate your technique.

Problem 4
What is the computational cost (running-time) of doing a comparison of a query to all documents after latent semantic indexing has been used to express the term-document matrix C in terms of matricies U'_k, Σ'_k, and V'_k for the rank-k approximation (using our class notation)? Do not include the preprocessing cost to find matrices U'_k, Σ'_k, and V'_k.   Unit-cost computations are scalar addition, multiplication, comparison and other basic program steps, not vector operations.  You should list each step of the computation to compare a query expressed as a vector of weights for t index terms to all N documents. Your analysis should be in terms of t, N, and the reduced rank k after latent semantic indexing as been applied.