20.7.3 Defining similarity between two vectors

From the previous sections we can now compute a co-occurrence vector for a target word, with each co-occurrence feature weighted by an association measure, giving us

a distributional definition of the meaning of a target word.

To define similarity between two target words $ \nu $ and w, we need a measure for taking two such vectors and giving a measure of vector similarity. Perhaps the simplest two measures of vector distance are the Manhattan and Euclidean distance. Fig. 20.12 shows a graphical intuition for Euclidean and Manhattan distance between two two-dimensional vectors $ \vec{a} $ and $ \vec{b} $. The Manhattan distance, also known as Levenshtein distance or L1 norm, is

$$ \mathrm{distance}_{\mathrm{manhattan}}(\overrightarrow{x},\overrightarrow{y})=\sum_{i=1}^{N}|x_{i}-y_{i}| $$

The Euclidean distance, also called the L2 norm, was introduced in Ch. 9:

$$ \mathrm{distance}_{\mathrm{euclidean}}(\vec{x},\vec{y})=\sqrt{\sum_{i=1}^{N}(x_{i}-y_{i})^{2}} $$

Although the Euclidean and Manhattan distance metrics provide a nice geometric intuition for vector similarity and distance, these measures are rarely used for word similarity. This is because both measures turn out to be very sensitive to extreme values. Instead of these simple distance metrics, word similarity is based on closely related metrics from information retrieval and from information theory. The information retrieval methods seem to work better for word similarity, so we'll define a number of these in this section.

Let's begin with the intuition for a similarity metric in Fig. 20.9, in which the similarity between two binary vectors was just the number of features the two words had in common. If we assume a feature vector is a binary vector, we can define such a similarity metric as follows, using the dot product or inner product operator from linear algebra:

$$ sim_{dot-product}(\vec{v},\vec{w})=\vec{v}\cdot\vec{w}=\sum_{i=1}^{N}v_{i}\times w_{i} $$

In most cases, though, as we saw in the previous section, the values of our vector are not binary. Let's assume for the rest of this section that the entries in the co-occurrence vector are the \textit{association} values between the target words and each of the features. In other words, let's define the vector for a target word $ \vec{w} $ with $ N $ features $ f_1..f_N $ as:

$$ \vec{w}=(\operatorname{a s s o c}(w,f_{1}),\operatorname{a s s o c}(w,f_{2}),\operatorname{a s s o c}(w,f_{3}),\ldots,\operatorname{a s s o c}(w,f_{N})) $$

Now we can apply $\mathrm{sim}_{\mathrm{dot}-}\mathrm{product}$ to vectors with values defined as associations, to get the dot-product similarity between weighted values. This raw dot-product, however, has a problem as a similarity metric: it favors long vectors. The vector length is defined as:

$$ |\overrightarrow{v}|=\sqrt{\sum_{i=1}^{N}v_{i}^{2}} $$

A vector can be longer because it has more non-zero values, or because each dimension has a higher value. Both of these facts will increase the dot product. It turns out that both of these can occur as a by-product of word frequency. A vector from a very frequent word will have more non-zero co-occurrence association values, and will probably have higher values in each (even using association weights that control somewhat for frequency). The raw dot product thus favors frequent words.

We need to modify the dot product to normalize for the vector length. The simplest way is just to divide the dot product by the lengths of each of the two vectors. This normalized dot product turns out to be the same as the cosine of the angle between the two vectors. The cosine or normalized dot product similarity metric is thus:

$$ sim_{cosine}(\vec{v},\vec{w})=\frac{\vec{v}\cdot\vec{w}}{|\vec{v}||\vec{w}|}=\frac{\sum_{i=1}^{N}v_{i}\times w_{i}}{\sqrt{\sum_{i=1}^{N}v_{i}^{2}}\sqrt{\sum_{i=1}^{N}w_{i}^{2}}} $$

Because we have transformed the vectors to unit length, the cosine metric, unlike Euclidean or Manhattan distance, is no longer sensitive to long vectors from high-frequency words. The cosine value ranges from 1 for vectors pointing in the same direction, through 0 for vectors which are orthogonal (share no common terms), to -1 for vectors pointing in opposite directions, although in practice values tend to be positive.

Let's discuss two more similarity measures derived from information retrieval. The Jaccard (Jaccard, 1908, 1912) (also called Tanimoto or min/max (Dagan, 2000)) measure was originally designed for binary vectors. It was extended by Grefenstette (1994) to vectors of weighted associations as follows:

$$ sim_{Jaccard}(\vec{\nu},\vec{w})=\frac{\sum_{i=1}^{N}min(v_{i},w_{i})}{\sum_{i=1}^{N}max(v_{i},w_{i})} $$

The numerator of the Grefenstette/Jaccard function uses the min function, essentially computing the (weighted) number of overlapping features (since if either vector has a zero association value for an attribute, the result will be zero). The denominator can be viewed as a normalizing factor.

A very similar measure, the Dice measure, was similarly extended from binary

vectors to vectors of weighted associations; one extension from Curran (2003) uses the Jaccard numerator, but uses as the denominator normalization factor the total weighted value of non-zero entries in the two vectors.

$$ sim_{Dice}(\vec{v},\vec{w})=\frac{2\times\sum_{i=1}^{N}min(v_{i},w_{i})}{\sum_{i=1}^{N}(v_{i}+w_{i})} $$

$$ \operatorname{assoc}_{\mathbf{prob}}(w,f)\;=\;P(f|w) $$

$$ \begin{array}{c} assoc_{PMI}(w,f)~=~\log_{2}\frac{P(w,f)}{P(w)P(f)}\end{array} $$

$$ \begin{array}{r l}{\mathrm{a s s o c}_{\mathrm{L i n}}(w,f)}&{{}=\log_{2}\frac{P(w,f)}{P(w)P(r|w)P(w^{\prime}|w)}}\end{array} $$

$$ \begin{array}{c} assoc_{t-test}(w,f)~=~\frac{P(w,f)-P(w)P(f)}{\sqrt{P(f)P(w)}}\end{array} $$

$$ \begin{array}{r l r}{\mathrm{s i m}_{\mathrm{c o s i n e}}(\vec{\nu},\vec{w})}&{{}=}&{\frac{\vec{\nu}\cdot\vec{w}}{|\vec{\nu}||\vec{w}|}=\frac{\sum_{i=1}^{N}\nu_{i}\times w_{i}}{\sqrt{\sum_{i=1}^{N}\nu_{i}^{2}}\sqrt{\sum_{i=1}^{N}w_{i}^{2}}}}\end{array} $$

$$ \begin{array}{c} sim_{Jaccard}(\vec{v},\vec{w})\;=\;\frac{\sum_{i=1}^{N}\min(\nu_{i},w_{i})}{\sum_{i=1}^{N}\max(\nu_{i},w_{i})}\end{array} $$

$$ \begin{array}{r l r}{\mathrm{s i m}_{D i c e}(\vec{v},\vec{w})}&{{}=}&{\frac{2\times\sum_{i=1}^{N}\operatorname*{m i n}(v_{i},w_{i})}{\sum_{i=1}^{N}(v_{i}+w_{i})}}\end{array} $$

$$ \begin{array}{r l r}{\operatorname{s i m}_{\mathrm{J S}}(\vec{v}||\vec{w})}&{{}}&{=~D(\vec{v}|\frac{\vec{v}+\vec{w}}{2})+D(\vec{w}|\frac{\vec{v}+\vec{w}}{2})}\end{array} $$

Figure 20.13 Defining word similarity: measures of association between a target word w and a feature $ f = (r, w') $ to another word $ w' $, and measures of vector similarity between word co-occurrence vectors $ \vec{v} $ and $ \vec{w} $.

Finally, there is a family of information-theoretic distributational similarity measures, (Pereira et al., 1993; Dagan et al., 1994, 1999; Lee, 1999), also based on the conditional probability association measure $ P(f|w) $. The intuition of these models is that two vectors $ \vec{v} $ and $ \vec{w} $ are similar to the extent that their probability distributions $ P(f|w) $ and $ P(f|v) $ are similar. The basis of comparing two probability distributions $ P $ and $ Q $ is the Kullback-Leibler divergence or KL divergence or relative entropy (Kullback and Leibler, 1951):

$$ \begin{array}{c} D(P||Q)~=~\sum_{x} P(x)\log\frac{P(x)}{Q(x)}\end{array} $$

Unfortunately, the KL-divergence is undefined when $ Q(x) = 0 $ and $ P(x) \neq 0 $, which is a problem since these word distribution vectors are generally quite sparse. One alternative (Lee, 1999) is to use the \textit{Jenson-Shannon divergence}, which represents the divergence of each distribution from the mean of the two, and doesn't have this problem with zeros:

$$ JS(P||Q)\;=\;D(P|\frac{P+Q}{2})+D(Q|\frac{P+Q}{2}) $$

Rephrased in terms of vectors $ \vec{v} $ and $ \vec{w} $,

$$ \begin{array}{c c l}{\operatorname{s i m}_{\mathbf{J S}}(\vec{v}||\vec{w})}&{=}&{D(\vec{v}|\displaystyle\frac{\vec{v}+\vec{w}}{2})+D(\vec{w}|\displaystyle\frac{\vec{v}+\vec{w}}{2})}\end{array} $$

Fig. 20.13 summarizes the measures of association and of vector similarity that we have designed. See the history section for a summary of other vector similarity measures.

Finally, let's look at some of the results of distributional word similarity. The following are the ten most similar words to the different parts of speech of hope and brief, derived using the online dependency-based similarity tool (Lin, 2007); this tool defines the co-occurrence vector using all minipar grammatical relations, uses the \textit{assocLin} measure of association, and a vector similarity metric from Lin (1998a).

• hope (N): optimism 0.141338, chance 0.136681, expectation 0.136559, prospect 0.125597, dream 0.119079, desire 0.117939, fear 0.116273, effort 0.111264, confidence 0.109136, promise 0.108269

• hope (V): would like 0.157988, wish 0.139532, plan 0.139349, say 0.136786, believe 0.135058, think 0.132673, agree 0.129985, wonder 0.129709, try 0.127047, decide 0.125387,

• brief (N): legal brief 0.139177, affidavit 0.103401, filing 0.0982636, petition 0.0864875, document 0.0835244, argument 0.0831851, letter 0.0785654, rebuttal 0.077766, memo 0.0768226, article 0.0758248

• brief (A): lengthy 0.256242, hour-long 0.191421, short 0.173561, extended 0.163085, frequent 0.162555, recent 0.15815, short-lived 0.154955, Prolonged 0.149289, week-long 0.149128, occasional 0.146385