Sets are indicator vectors

Domain $\mathcal{D} = \{\text{Tom}, \text{Ann}, \text{Joe}, \text{Sue}, \text{Sam}\}$

Quantifiers are tests on two counts

Here $A = \text{runner} = \{\text{Tom}, \text{Ann}, \text{Sue}\}$, $B = \text{tall} = \{\text{Ann}, \text{Joe}, \text{Sue}\}$ and $A \cap B = \{\text{Ann}, \text{Sue}\}$, so $|A| = 3$ and $|A \cap B| = 2$.

Practice 1. Quantifiers

Domain $\mathcal{D} = \{\text{Tom}, \text{Ann}, \text{Joe}, \text{Sue}, \text{Sam}\}$

$$A = \text{singer} = (1,0,1,1,1), \qquad B = \text{dancer} = (0,0,1,1,1)$$

(a) Compute $A \odot B$ and $A \cdot B$. Say what each denotes.

(b) Evaluate Every singer is a dancer, Some singer is a dancer and No singer is a dancer, naming the test.

(c) Evaluate Every dancer is a singer. Compare with part (b).

(d) What single change to the model makes Every singer is a dancer true?

Practice 1. Answers

• (a) $(0,0,1,1,1)$, the set $A \cap B = \{\text{Joe}, \text{Sue}, \text{Sam}\}$ of singers who are dancers, and $3$, the size of that set
• (b) $|A| = 4$ and $|A \cap B| = 3$. Every needs $3 = 4$, false, Tom is the witness. Some needs $3 > 0$, true. No needs $3 = 0$, false
• (c) Now the restrictor is dancer, $|B| = 3 = |A \cap B|$, so true. Swapping the arguments changes the answer, because the first noun is the restrictor
• (d) Make Tom a dancer, so that $|A \cap B| = |A| = 4$

A relation is a matrix

Domain $\mathcal{D} = \{\text{Tom}, \text{Ann}, \text{Joe}, \text{Sue}\}$. $F_{ij} = 1$ when $i$ follows $j$, rows are the follower.

Columns, rows and sentences

• $F\mathbf{e}_{\text{Joe}} = (1,1,0,1)$, the people who follow Joe, $\{\text{Tom}, \text{Ann}, \text{Sue}\}$
• $F^\top\mathbf{e}_{\text{Joe}} = (1,0,0,0)$, the people Joe follows, $\{\text{Tom}\}$
• The two indices of $F$ are different argument positions, so the two sets differ
• “Ann follows Joe” is the bilinear form $\mathbf{e}_{\text{Ann}}^\top F\,\mathbf{e}_{\text{Joe}} = F_{23} = 1$, true

Types and tensor orders

Practice 2. Relations

Domain $\mathcal{D} = \{\text{Tom}, \text{Ann}, \text{Joe}, \text{Sue}\}$. $T_{ij} = 1$ when $i$ teaches $j$.

(a) Compute $T\mathbf{e}_{\text{Sue}}$ and $T^\top\mathbf{e}_{\text{Sue}}$. Name each set in English.

(b) Write “Ann teaches Tom” as a bilinear form and evaluate it.

(c) Is $T$ symmetric? Name a pair that settles it.

(d) Give the type of teaches, and the order and type of $T\mathbf{e}_{\text{Sue}}$.

Practice 2. Answers

• (a) $T\mathbf{e}_{\text{Sue}} = (1,1,0,0)$, the people who teach Sue, $\{\text{Tom}, \text{Ann}\}$. $T^\top\mathbf{e}_{\text{Sue}} = (1,0,0,0)$, the people Sue teaches, $\{\text{Tom}\}$
• (b) $\mathbf{e}_{\text{Ann}}^\top T\,\mathbf{e}_{\text{Tom}} = T_{21} = 0$, false
• (c) Not symmetric. $T_{12} = 1$ but $T_{21} = 0$. Any such pair works
• (d) $\langle e,\langle e,t\rangle\rangle$. $T\mathbf{e}_{\text{Sue}}$ has order 1 and type $\langle e,t\rangle$, a predicate

The pipeline

$$\text{counts} \to \text{ratio} \to \text{PMI} = \log_2(\text{ratio})$$

$$\text{PMI} \to \text{PPMI} = \max(0, \text{PMI}) \to \cos$$

• With counts, the ratio is $\dfrac{N \cdot n(w,c)}{n(w)\,n(c)}$
• Ratio above $1$. They co-occur more than chance predicts, PMI is positive
• Ratio $1$. Independent, PMI is $0$
• Ratio below $1$. They co-occur less than chance, PMI is negative

A worked table

Row totals $(50, 30, 20)$, column totals $(40, 40, 20)$.

Reading the table

• $\text{PMI}(\text{coffee}, \text{hot}) = \log_2 \dfrac{100 \cdot 40}{50 \cdot 40} = \log_2 2 = 1$
• $\text{PMI}(\text{coffee}, \text{cup}) = \log_2 \dfrac{100 \cdot 10}{50 \cdot 40} = \log_2 \dfrac{1}{2} = -1$
• A zero count gives ratio $0$ and $\text{PMI} = -\infty$
• PPMI clips every negative value to $0$, so $-1$ and $-\infty$ both become $0$

Cosine on PPMI rows

$$\cos(\mathbf{u},\mathbf{v}) = \frac{\mathbf{u}\cdot\mathbf{v}}{\|\mathbf{u}\|\,\|\mathbf{v}\|}$$

• Two PPMI rows are orthogonal when they share no context with a positive value
• A word whose PPMI row is all zeros is the zero vector, with $\|\mathbf{0}\| = 0$
• Then the cosine is $\dfrac{0}{0}$, which is undefined. That is a modeling problem, not a rounding one

Context smoothing

Raise context counts to a power $\alpha < 1$ before normalizing.

$$p_\alpha(c) = \frac{\text{count}(c)^\alpha}{\sum_{c'} \text{count}(c')^\alpha}$$

What smoothing does

• It flattens the context distribution, so the rare context $c_3$ gains mass, from $0.050$ to $0.089$
• The probability sits in the denominator of PMI, so a larger $p_\alpha(c_3)$ pushes its PMI down
• That corrects PMI’s bias toward rare contexts, which look strongly associated by accident

Practice 3a. A table to work through

Row totals $(50, 30, 20)$, column totals $(50, 30, 20)$. Leave answers as $\log_2$ of a fraction.

(a) Compute $\text{PMI}(x_1, c_1)$ and $\text{PMI}(x_1, c_2)$.

(b) Compute the whole PMI row of $x_3$. What does it say about $x_3$?

(c) Write the PPMI matrix. What distinction was lost?

Practice 3a. More parts

Use the same table.

(d) Compute $\cos(x_1, x_2)$ on the PPMI rows. Then try $\cos(x_1, x_3)$ and say precisely what goes wrong.

(e) On the raw count rows, $\cos(x_1, x_2) \approx 0.87$. Explain why this disagrees with part (d).

Practice 3a. Answers

• (a) Ratio $\frac{100 \cdot 30}{50 \cdot 50} = \frac{6}{5}$, so $\text{PMI}(x_1,c_1) = \log_2\frac65$. Ratio $\frac{100 \cdot 12}{50 \cdot 30} = \frac45$, so $\text{PMI}(x_1,c_2) = \log_2\frac45$, which is negative
• (b) Every ratio is $1$, so the row is $(0,0,0)$. The distribution of $x_3$ over contexts equals the context totals, so $x_3$ is independent of every context, uninformative rather than rare
• (c) $\text{PPMI} = \begin{pmatrix} \log_2\frac65 & 0 & 0 \\ 0 & \log_2\frac43 & \log_2\frac43 \\ 0 & 0 & 0 \end{pmatrix}$. Negative association and independence both became $0$

Practice 3a. Answers continued

• (d) $x_1$ has support only on $c_1$ and $x_2$ only on $c_2, c_3$, so the dot product is $0$ and $\cos = 0$. For $x_3$ the PPMI row is the zero vector, so the formula gives $\frac{0}{0}$, undefined
• (e) The raw rows $(30,12,8)$ and $(10,12,8)$ overlap on every context, mostly because both words are frequent. PPMI removes the frequency baseline, and after clipping they share no positive context

Practice 3b. Smoothing

Context counts $(60, 30, 10)$ and $\alpha = 0.5$.

(a) Compute $p(c)$ and $p_\alpha(c)$ for the three contexts.

(b) Which context gains probability, and which loses?

(c) What happens to the PMI of the rarest context, and why is that the point of smoothing?

Practice 3b. Answers

• (a) $p = (0.60, 0.30, 0.10)$ and the square roots are $(7.75, 5.48, 3.16)$ with sum $16.39$, so $p_{0.5} \approx (0.47, 0.33, 0.19)$
• (b) The rare context $c_3$ gains, from $0.10$ to $0.19$. The common context $c_1$ loses
• (c) A larger denominator lowers the PMI of $c_3$. Rare contexts were being over-rewarded, and smoothing corrects that

The bilinear form

$$\mathbf{u}^\top G\,\mathbf{v} = \sum_{i,j} u_i\,G_{ij}\,v_j$$

Take $\mathbf{u} = (2,3)$, $\mathbf{v} = (5,1)$ and $G = \begin{pmatrix} 1 & 2 \\ 0 & 3 \end{pmatrix}$.

• With $G = I$ the form is the dot product, $2 \cdot 5 + 3 \cdot 1 = 13$
• With $G$, write out all four terms

Ranking with a metric

A query $\mathbf{q}$ is compared with several candidates $\mathbf{x}$. Each candidate gets a score, and the ranking sorts the candidates by score.

$$\text{score}_G(\mathbf{x}) = \mathbf{q}^\top G\,\mathbf{x}$$

• The metric $G$ decides how much each coordinate counts
• $G = I$ is the ordinary dot product, so every coordinate counts equally
• $G = \text{diag}(g_1, g_2)$ gives $g_1 q_1 x_1 + g_2 q_2 x_2$, so $g_i$ is the weight of coordinate $i$
• A non-diagonal $G$ also mixes coordinates, through the cross terms $q_i G_{ij} x_j$

The scores

Query $\mathbf{q} = (1,2)$, candidates $\mathbf{a} = (4,1)$ and $\mathbf{b} = (1,3)$, and metric $G = \text{diag}(g, 1)$.

• Dot product. $\mathbf{q}\cdot\mathbf{a} = 6$ and $\mathbf{q}\cdot\mathbf{b} = 7$, so $\mathbf{b}$ is returned
• With this $G$, $\mathbf{q}^\top G \mathbf{a} = 4g + 2$ and $\mathbf{q}^\top G \mathbf{b} = g + 6$
• $\mathbf{a}$ wins when $4g + 2 > g + 6$, that is $g > \frac{4}{3}$
• With $g = 3$ the scores are $14$ and $9$, so the ranking is reversed

A metric can reverse a ranking

Each label gives the score of that point. Dashed lines join points with the same score. The grey arrow points toward higher scores, so the point on the higher line wins.

Practice 4. Bilinear forms and metrics

(a) Let $\mathbf{u} = (1,4)$, $\mathbf{v} = (3,2)$ and $G = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$. Compute $\mathbf{u}^\top\mathbf{v}$ and $\mathbf{u}^\top G\mathbf{v}$, writing out all four terms for the second.

(b) A query $\mathbf{q} = (3,1)$ is compared with $\mathbf{a} = (2,2)$ and $\mathbf{b} = (5,0)$. Which is returned under the dot product?

(c) Find a diagonal $G = \text{diag}(1,g)$ under which the other candidate wins. Verify by computing both scores.

Practice 4. Answers

• (a) $\mathbf{u}^\top\mathbf{v} = 3 + 8 = 11$. And $1\cdot2\cdot3 + 1\cdot1\cdot2 + 4\cdot0\cdot3 + 4\cdot1\cdot2 = 6 + 2 + 0 + 8 = 16$
• (b) $\mathbf{q}\cdot\mathbf{a} = 8$ and $\mathbf{q}\cdot\mathbf{b} = 15$, so $\mathbf{b}$ is returned
• (c) $\mathbf{q}^\top G\mathbf{a} = 6 + 2g$ and $\mathbf{q}^\top G\mathbf{b} = 15$, so $\mathbf{a}$ wins when $g > 4.5$. Take $g = 5$, giving $16$ against $15$

The outer product

$$(\mathbf{u}\mathbf{v}^\top)_{ij} = u_i\,v_j$$

Take $\mathbf{u} = (2,1,0)$ and $\mathbf{v} = (1,0,3)$.

$$\mathbf{u}\mathbf{v}^\top = \begin{pmatrix} 2 & 0 & 6 \\ 1 & 0 & 3 \\ 0 & 0 & 0 \end{pmatrix}$$

• Every row is a multiple of $\mathbf{v}^\top$, by $2$, $1$ and $0$
• Every column is a multiple of $\mathbf{u}$
• So the rank is $1$. This is forced by how an outer product is built

Practice 5. Outer products

(a) For $\mathbf{u} = (3,0,1)$ and $\mathbf{v} = (1,2,1)$ write out $\mathbf{u}\mathbf{v}^\top$ and state its rank.

(b) Is $\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ an outer product of two vectors? If so, which?

(c) Is the $2\times2$ identity an outer product of two vectors? Explain using rank.

Practice 5. Answers

• (a) $\begin{pmatrix} 3 & 6 & 3 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{pmatrix}$, rank $1$, since every row is a multiple of $\mathbf{v}^\top$
• (b) Yes. It equals $\mathbf{w}\mathbf{w}^\top$ with $\mathbf{w} = (1,2)$, and its second row is twice the first
• (c) No. The identity has rank $2$, but an outer product of nonzero vectors has rank $1$. The identity is a sum of two outer products, $\mathbf{e}_1\mathbf{e}_1^\top + \mathbf{e}_2\mathbf{e}_2^\top$

One operation, three readings