CSCE 470 Lecture 6

« previous | Friday, September 6, 2013 | next »

Search Ranking

Two Key Questions

1. How to represent each query or document?
   • set of terms
   • bag of words → TF, log TF, TF IDF
2. How to measure similarity (or distance) between $q$ and $d$?
   • Jaccard
   • Manhattan Distance ($|u_1-v_1|+\dots +|u_n-v_n|$
   • Euclidean Distance ($\sqrt{(u_1-v_1{)}^2+\dots +(u_n-v_n{)}^2}$)
   • Cosine

Cosine Similarity

Measures angle between query vector $\overrightarrow{q}$ and document vector $\overrightarrow{d}$. Two vectors are similar if

• the angle between is smaller (i.e. $\theta \to 0$), and thus
• the cosine similarity is larger (i.e. $\cos \theta \to 1$)

From vector calculus, we can find the cosine between two vectors as follows:

$\mathrm{s}\mathrm{i}\mathrm{m}(\overrightarrow{q},\overrightarrow{d})=\cos \theta =\frac{\overrightarrow{q}\cdot \overrightarrow{d}}{\Vert \overrightarrow{q}\Vert \Vert \overrightarrow{d}\Vert }$

If the vectors are stored in a normalized format, the similarity formula becomes much easier:

$\begin{array}{rlrlrl}\hat{q}& =\frac{\overrightarrow{q}}{\Vert \overrightarrow{q}\Vert }& \hat{d}& =\frac{\overrightarrow{d}}{\Vert \overrightarrow{d}\Vert }& \mathrm{s}\mathrm{i}\mathrm{m}(\hat{q},\hat{d})=\cos \theta & =\hat{q}\cdot \hat{d}\end{array}$