Concept - Cosine Similarity

Cosine Similarity

Definition (s.121): a similarity measure between two texts determined by the angle between their word-count vectors (lines from the origin (0,0) to the points), and not by the lengths of the lines. Similarity $=\cos (\text{angle})$.

Intuition (s.121-134)

• Build a table of word counts per phrase (columns = words, e.g. Hello, World), plot each phrase as a point (x = count of “Hello”, y = count of “World”), and draw lines from the origin.
• Identical phrases -> same point -> angle $0^{\circ }$ -> $\cos (0^{\circ })=1$ (s.122-127, s.133).
• No words in common (Hello vs World) -> points on different axes -> angle $90^{\circ }$ -> $\cos (90^{\circ })=0$ (s.128-132).
• Some overlap (“Hello, World!” vs “Hello!”) -> angle $45^{\circ }$ -> $\cos (45^{\circ })=0.71$, between 0 and 1 (s.134).
• Length independence (s.121): “Hello, World!” (1,1) vs “Hello Hello Hello!” (3,0) also gives $45^{\circ }$ and $\cos =0.71$; the different line lengths do not matter.

Situation	Angle	Cosine similarity	Slide
Phrases exactly the same	$0^{\circ }$	1	s.127, s.133
Some overlap	$45^{\circ }$ (example)	0.71	s.134
Nothing in common	$90^{\circ }$	0	s.131-132

Manual 4-step procedure (s.136-139)

1. Make a table of the word counts.
2. Plot the points.
3. Figure out the angle.
4. Calculate the cosine of the angle. Slide 140: doing this is “pretty tedious”; slide 141: a relatively simple formula computes it quickly on a computer directly from the table of word counts.

Formula (s.142-150)

$\text{CosSim}(A,B)=\frac{{\sum }_{i=1}^n{A}_i{B}_i}{\sqrt{{\sum }_{i=1}^n{A}_i^2}\sqrt{{\sum }_{i=1}^n{B}_i^2}}$

• $\Sigma$ = shorthand for adding up a bunch of stuff (s.143); $i$ = index, keeps track of the word being worked on (s.144), starts at 1 = first word in the table, Hello (s.145); $n$ = number of different words in the phrases, here $n=2$ (Hello, World) (s.146); $A$ and $B$ = the two phrases (s.147): $A$ = “Hello, World!” (s.148), $B$ = “Hello!” (s.149).
• Plugging in $i=1$ (Hello): $(1\times 1)+\dots$ over $\sqrt{1^2+\dots }\sqrt{1^2+\dots }$ (s.150). The $i=2$ (World) terms continue in the next chunk.

Related

Concept - Bag of Words (the count vectors it is computed on) | Concept - TF-IDF | Concept - Word Embeddings

Appears in

• 02 Pre-processing - Chunk 05 (s.121-150)

LSA example (s.182, s.188) - from 02 Pre-processing - Chunk 07 (s.181-193)

In the doc-term example, cosine(doc4, doc5) on the full 5-topic dense vectors is $-6.1\times 10^{-16}$ (~0, s.182); after Concept - Truncated SVD to 2 dimensions it is 0.75020516 (s.188).

Introduction & first worked example (s.91-120) - from 02 Pre-processing - Chunk 04 (s.91-120)

• Motivation (s.91-96): Troll 2 tweets - “I love Troll 2!”, “I like Troll 2.”, “I love Troll 2! I love it!!!” are similar (positive), “Troll 2 is bad.” differs (s.91). Easy by eye for few sentences (s.92), but for a month of Twitter traffic a computer must do it (s.93-94). Cosine Similarity “comes in handy” (s.95): a relatively easy to calculate metric telling how similar or different things are (s.96).
• Count table (s.97-103): “Hello, World!” -> Hello 1, World 1; “Hello!” -> Hello 1, World 0.
• Plot (s.104-110): x-axis = count of Hello, y-axis = count of World; “Hello, World!” at (1,1) (center of graph, s.107), “Hello!” at (1,0) on the x-axis (s.108); lines from origin (0,0) (s.109) have a $45^{\circ }$ angle (s.110).
• Result (s.111-112): $\cos (45^{\circ })=0.71$ = Cosine Similarity of the two phrases.
• Repetition (s.113-120): “Hello Hello Hello!” = (3,0): point further out on x-axis (s.117) but angle still $45^{\circ }$ (s.118) -> same 0.71 (s.119): “determined entirely by the angle between the lines” (s.120).

Added context

Algebraic check: $A=(1,1),B=(1,0)$: $1/(\sqrt{2}\cdot 1)=0.71$; $A=(1,1),B=(3,0)$: $3/(\sqrt{2}\cdot 3)=0.71$.

From 01 Intro, s.37-39 (01 Intro - Chunk 02 (s.31-48))

• Popular similarity for weighted document vectors (TF or TF-IDF): $\cos (d_1,d_2)=\frac{d_1\bullet d_2}{\Vert d_1\Vert \Vert d_2\Vert }$, $\Vert a\Vert =\sqrt{\sum a_i^2}$ (s.37).
• Example: $d_1=(3,2,0,5,0,0,0,2,0,0)$, $d_2=(1,0,0,0,0,0,0,1,0,2)$: dot = 5, $\Vert d_1\Vert =\sqrt{42}=6.481$, $\Vert d_2\Vert =\sqrt{6}$ (slide prints 2.245; true value 2.449), cos = 0.3150 (s.37).
• “Commonly used combination for text clustering” with TF-IDF (s.38): Saturn/Jupiter example gives cos(d1,d2)=0.13, cos(d1,d3)=0.05, cos(d2,d3)=0.00, because is/the have idf = log(3/3) = 0 (s.39).
• Contrast with Concept - Jaccard Coefficient (binary vectors; 0.44/0.27/0.18 on the same documents) and use in Concept - Document Clustering.

From chunk 06 (s.151-172)

• i = 2 plug-in (s.151): $\frac{(1\times 1)+(1\times 0)}{\sqrt{1^2+1^2}\sqrt{1^2+0^2}}=0.71$ (s.152), equal to $\cos 45^{\circ }$ on the Hello/World plot (s.153). Plotting only works for 2 distinct words (s.154-158).
• 5-word example (s.159-169): A = “I love Troll 2!” = (1,1,1,1,0), B = “I love Gymkata!” = (1,1,0,0,1) over columns I, Love, Troll, 2, Gymkata. Needs a 5-D plot, which cannot be drawn, so just use the formula: $\frac{2}{\sqrt{4}\sqrt{3}}=0.58$ (s.165-168). Summary: easy-to-compute metric of how similar or different things are (s.169).
• Limitation (s.172): on a bag-of-words Concept - Document-Term Matrix, “gas” (doc 4) and “oil” (doc 5) have cosine similarity 0 - counting captures no semantics.
• Written $\cos \theta =\frac{\mathbf{A}\cdot \mathbf{B}}{\Vert \mathbf{A}\Vert \Vert \mathbf{B}\Vert }$ on s.172.

Source: 02 Pre-processing - Chunk 06 (s.151-180)

Introduced at 02 Pre-processing s.89-90

The section “Document-term Matrix & Cosine Similarity” opens at s.89; s.90 shows four sentences about the movie Troll 2 (“I love Troll 2!”, “I like Troll 2.”, “I love Troll 2! I love it!!!”, “Troll 2 is bad.”) as the motivating example. See 02 Pre-processing - Chunk 03 (s.61-90).