<span style="font-variant:small-caps;">Google Distance Between Words</span> 

Rudi Cilibrasi and Paul Vitnyi have demonstrated that it is possible to extract the meaning of words from the world-wide web. To achieve this, they rely on the number of webpages that are found through a Google search containing a given word and they associate the page count to the probability that the word appears on a webpage. Thus, conditional probabilities allow them to correlate one word with another word's meaning. Furthermore, they have developed a similarity <span>distance function</span> that gauges how closely related a pair of words is. We present a specific counterexample to the triangle inequality for this similarity distance function.

Introduction
============

When the Google search engine is used to search for word *x*, Google displays the number of hits that word *x* has. The ratio of this number of hits to the total number of webpages indexed by Google represents the probability that word *x* appears on a webpage. Cilibrasi and Vitányi @CV use this probability to extract the meaning of words from the world-wide-web. If word *y* has a higher conditional probability to appear on a webpage, given that word *x* also appears on the webpage, than it does by itself, then it can be concluded that words *x* and *y* are related. Moreover, higher conditional probabilities imply a closer relationship between the two words. Thus, word *x* provides some meaning to word *y* and vice versa.\
Cilibrasi and Vitányi's *normalized Google distance* (**NGD**) function measures how close word *x* is to word *y* on a zero to infinity scale. A distance of zero indicates that the two words are practically the same. Two independent words have a distance of one. A distance of infinity occurs for two words that never appear together.\
Although Cilibrasi and Vitányi's **NGD** function was sensibly derived from its basic axioms (which allow it to theoretically yield the values mentioned above), it does not account for the presence of multi-thematic webpages. In other words, the **NGD** function does not account for webpages, such as dictionary sites and other long pages, which encompass many unrelated subjects. For this reason, it is necessary to renormalize the **NGD** formula to achieve the desired values.

**NGD**'S EXPECTATION VALUE
===========================

On the average, two random words should be independent of one another. Hence, two random words should have an **NGD** of one. To test this assumption, we randomly selected two sets of five words from the dictionary. In addition, we randomly chose one set of ten words from two different news articles (five words were taken from each article). We then proceeded to evaluate the **NGD** among the different word pairs in each set using Cilibrasi and Vitányi's formula $${\mathbf{NGD}}(x,y)  = \frac{\max \left\{\log f(x),\log f(y)\right\} - \log f(x,y)}
{{\log M - \min \left\{\log f(x),\log f(y)\right\}}},$$where $f(x)$ and $f(y)$ are the number of hits of words $x$ and $y$, respectively, and $M$ is the total number of webpages that Google indexes.\
Our first set, which consisted of the words *micrometeorite*, *transient*, *denature*, *pentameter*, and *reside*, yielded an expectation value of 0.64 for the **NGD** with a standard deviation of 0.14. Our second set, which consisted of the words *detrition*, *unity*, *interstice*, *abrupt*, and *reside*, had an expectation value of 0.75 for the **NGD** with a standard deviation of 0.12. Our last set, which consisted of the words *agency*, *diabetic*, *enforcement*, *federal*, *hormone*, *illegal*, *intelligence*, *measure*, *spread*, and *war*, yielded an expectation value of 0.77 with a standard deviation of 0.15. Averaging the above values (weighing them correctly according to the number of words in each set), we obtain an expected value of 0.7325 for the **NGD**. A similar evaluation provides us with a standard deviation of 0.14.\
A different type of analysis brought us to a similar expectation value. We call this evaluation the *triangle difference*, (**TD**). The reason for this name is that we evaluated the following difference: $${\mathbf{TD}} \equiv {\mathbf{NGD}}(x,y) + {\mathbf{NGD}}(y,z) - {\mathbf{NGD}}(x,z).$$The reason to evaluate such difference stemmed from the possibility that the sum of two distances, between words x and y, and y and z, might be smaller than the distance between x and z. If such were the case, then it would be sensible to redefine the distance between two words such that it minimizes all possible **NGD** sums: $${\mathbf{NGD}}^{*}(x,z) \equiv$$ $$\min \left\{ {\mathbf{NGD}}(x,y) + {\mathbf{NGD}}(y,z),{\mathbf{NGD}}(x,z)\right\},$$for all words $y$. The triangle difference, however, is only violated by extremely rare exceptions, so it is not necessary to perform such minimization. Nevertheless, we proceeded to evaluate the expected triangle difference for each of our sets. They were 0.69, 0.79, and 0.60, for the first, second, and third sets, respectively. Combining them, they yield an expected triangle difference of 0.67. This, of course, is close to the expected value of **NGD**, as the triangle difference for random words is $$E\left[{\mathbf{TD}}\right] \equiv E\left[{\mathbf{NGD}}(x,y)\right] + E\left[{\mathbf{NGD}}(y,z)\right]$$ $$- E\left[{\mathbf{NGD}}(x,z)\right]$$ $$E\left[{\mathbf{TD}}\right] = 2E\left[{\mathbf{NGD}}\right] - E\left[{\mathbf{NGD}}\right] = E\left[{\mathbf{NGD}}\right].$$Therefore, the expectation value of the triangle difference should be equal to the expectation value of the **NGD**. A rough average of our expectation values obtained through each method is 0.7.

Notes Regarding **NGD**
=======================

In an arduous effort to find a set of words that would violate the triangle difference, we obtained a set that illustrates a few interesting properties of **NGD**. The set consists of the words *Rolling Stones*, *Beatles*, and *salmonflies* and it is, among the many word sets that we attempted, the only one that violates the triangle difference. Our first evaluation of the pertinent distances was the following:

            Word Pair            **NGD**
  ----------------------------- ---------
     Rolling Stones, Beatles      0.23
      Beatles, salmonflies        0.81
   Rolling Stones, salmonflies    1.06

\
Table 1. First evaluation of **NGD** values among the words *Rolling Stones*, *Beatles*, and *salmonflies*.

As can be observed, the **NGD** between *Rolling Stones* and *salmonflies* (1.06) is slightly higher than the addition of the Google distances between *Rolling Stones* and *Beatles*, and between *Beatles* and *salmonflies* (1.04). Therefore, our first observed property of **NGD** is that, even in the rare cases in which the triangle difference is violated, it is not by much. Furthermore, it is important to indicate that our example worked because of the high propensity that people have to misspell the word beetle as beatle, thus decreasing the distance between *Beatles* and *salmonflies*.\
The second property that we observed, which deserves much attention, is the **NGD** dependence on the Google server to which a user connects. A second evaluation of the distances in question yielded the following result:

            Word Pair            **NGD**
  ----------------------------- ---------
     Rolling Stones, Beatles      0.27
      Beatles, salmonflies        0.82
   Rolling Stones, salmonflies    1.14

\
Table 1. Second evaluation of **NGD** values among the words *Rolling Stones*, *Beatles*, and *salmonflies*.

This second set of distances was obtained by connecting to Google through a different internet service provider and it shows that Google distances are not stable values. In fact, from our example, they can vary by as much as 17% (for the *Rolling Stones-Beatles* word pair).\
The last property that this set of words depicts is the plausibility of Google distances that are higher than unity. With an **NGD** of 1.14, the word pair *Rolling Stones-salmonflies* has the highest distance that we have encountered. Indeed, Google distances greater than one are very rare, and before this example, the only one we had encountered was between the words *transient* and *pentameter* (1.02). Moreover, these cases are so rare that even Cilibrasi and Vitányi's conjecture about the words *by* and *with* having an **NGD** higher than one is false. The actual distance, per the Google server currently in use, is 0.19.

Conclusions
===========

Although Google can be used to extract the meaning of words, it is important to modify Equation 1 in order to obtain the desired distance values between words. The expectation value of **NGD**, which is the distance between two random and therefore independent words, is 0.7. To achieve the desired value of unity between independent words, it is only necessary to recalibrate the **NGD** formula by dividing by 0.7: $${\mathbf{NGD}}^{*}(x,y) =  \frac{{\mathbf{NGD}}(x,y)}{{0.7}}.$$\
It is also important to remember that **NGD** values are not exact. They depend on the number of hits that each word has, which makes them unstable. Factors such as the Google server to which one connects and the number of websites connected to the world-wide-web can cause discrepancies as high as 17%, which our *Rolling Stones-Beatles* example showed.

Acknowledgments
===============

We thank the Office of Undergraduate Research, University of Connecticut, for selecting our work for presentation @EK. The second author thanks the organizers M. Hutter, W. Merkle and P. Vitányi for the invitation to participate in the IBFI workshop *Kolmogorov Complexity and Its Applications*, Schloß  Dagstuhl, Germany, January-February 2006.

<span>99</span> R. L. Cilibrasi and P. M. Vitanyi, The Google similarity distance, *IEEE Transactions on Knowledge and Data Engineering* **19** (2007), no. 3, 370–383. arXiv:cs/0412098v3 \[cs.CL\]

A. Evangelista and B. Kjos-Hanssen, Google Distance Between Words. Poster, *Frontiers in Undergraduate Research*, University of Connecticut, 2006.

{'source': 'arXiv_out/0901'}