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 ${\vec {q}}$ and document vector ${\vec {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 {sim} \left({\vec {q}},{\vec {d}}\right)=\cos {\theta }={\frac {{\vec {q}}\cdot {\vec {d}}}{\left\|{\vec {q}}\right\|\,\left\|{\vec {d}}\right\|}}$

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

${\begin{aligned}{\hat {q}}&={\frac {\vec {q}}{\left\|{\vec {q}}\right\|}}&{\hat {d}}&={\frac {\vec {d}}{\left\|{\vec {d}}\right\|}}&\mathrm {sim} \left({\hat {q}},{\hat {d}}\right)=\cos {\theta }&={\hat {q}}\cdot {\hat {d}}\end{aligned}}$