6
$\begingroup$

I have a dataset consisting 5000 sentences. I need to calculate PMI between 3-gram and 5-grams in this dataset.

For example:

The 5-gram is: $x_1$$x_2$$x_3$$x_4$$x_5$

And the 3-gram is: $x_2$$x_3$$x_4$

How can I calculate PMI($x_2$$x_3$$x_4$, $x_1$$x_2$$x_3$$x_4$$x_5$) in this dataset? What is the exact formula?

As far as I know, in order to calculate PMI(y,z), it is needed to keep track of these counts in the dataset:

Count(y,z) --> The number of co-occurrences of y and z

Count(i,z) --> The number of occurrences of z

Count(y,i) --> The number of occurrences of y

N --> The sample size

The final formula is:

$PMI(y,z) = \frac{Count(y,z)N}{Count(i,z)Count(y,i)}$

In the context of my problem, these counts are listed as below:

$Count_1$($x_2$$x_3$$x_4$, $x_1$$x_2$$x_3$$x_4$$x_5$) : All occurrences of exact 5-gram " $x_1$$x_2$$x_3$$x_4$$x_5$ "

$Count_2$(i, $x_1$$x_2$$x_3$$x_4$$x_5$) : All occurrences of exact 5-gram "$x_1$$x_2$$x_3$$x_4$$x_5$ " !!!!!

$Count_3$($x_2$$x_3$$x_4$, i) : All occurences of 5-grams in the form of " _ $x_2$$x_3$$x_4$ _ ", that is the first and last words are subsituted with all the possible words in the dataset.

$N$ : All the 3-grams. !!!!!

My problem is with $Count_2$ and $N$. As you see, $Count_2$ is equal to $Count_1$. Is it sensible? And I'm not sure about the way I have counted $N$.

$\endgroup$
12
$\begingroup$

Let's start by taking a look at where your expression for PMI comes from. According to this article, for a pair of outcomes $x$ and $y$, $$PMI(x,y) = \log\left[\frac{p(x,y)}{p(x)p(y)}\right]$$ This says that, in order to calculate PMI properly, you need to somehow define a rule for associating the observation of your $n$-grams with a probability.

In the context of your particular data set, which can be cleanly divided into 5000 sentences, a very natural thing to define would be the probabilities for various $n$-grams to appear in a single sentence. To calculate the PMI, we can start by defining two different outcomes:

  • Outcome 1: the 3-gram $\vec{x} = (x_{1}, x_{2}, x_{3})$ appears in a given sentence
  • Outcome 2: the 5-gram $\vec{y} = (y_{1}, y_{2}, y_{3}, y_{4}, y_{5})$ appears in a given sentence

In general, the 3-gram and 5-gram need not contain any words in common in order to calculate a valid PMI, however if you wish to set $x_{1} = y_{2}$, $x_{2} = y_{3}$, etc., you may certainly do so and still calculate a mathematically well-defined result.

To obtain $p\left(\vec{x}, \vec{y}\right)$, the joint probability that both the 3-gram and the 5-gram appear simultaneously in the same sentence, we would simply count the number of sentences $n\left(\vec{x},\vec{y}\right)$ in your data set which contain both $\vec{x}$ and $\vec{y}$ together, and divide by the total number of sentences $N=5000$; i.e., $$p\left(\vec{x}, \vec{y}\right) = \frac{n\left(\vec{x},\vec{y}\right)}{N}$$ Similarly, $p\left(\vec{x}\right)$ and $p\left(\vec{y}\right)$ are defined by the number of times that $\vec{x}$ and $\vec{y}$ are observed individually in each of the 5 sentences. Thus, the PMI is defined by $$PMI\left(\vec{x},\vec{y}\right) = \log\left\{\frac{\left[\frac{n\left(\vec{x},\vec{y}\right)}{N}\right]}{\left[\frac{n\left(\vec{x}\right)}{N}\right]\left[\frac{n\left(\vec{y}\right)}{N}\right]}\right\} = \log\left[\frac{n\left(\vec{x},\vec{y}\right)N}{n\left(\vec{x}\right)n\left(\vec{y}\right)}\right]$$ which looks superficially similar to your result, with a few key differences (e.g., you forgot the include the $\log$ function, etc.). This formula is valid regardless of whether or not the 3-gram $\vec{x}$ and the 5-gram $\vec{y}$ have any words in common, and it is defined with the understanding that:

  • $N$ is the number of sentences in the data set (5000, in this case)
  • The values $n\left(\vec{x}, \vec{y}\right)$, $n\left(\vec{x}\right)$, and $n\left(\vec{y}\right)$ count the number of times that $\vec{x}$ and $\vec{y}$ appear with all words simultaneously together in the same sentence (i.e., if 2 of the words in a 5-gram appear in one sentence and 3 of the words appear in the next, it doesn't actually count as a valid 5-gram because the words aren't found all together within the same sentence)

In the question as you originally stated it, you considered a very special and unusual case: one where every word in the 3-gram was identical to a word in the 5-gram; i.e., $x_{1}=y_{2}$, $x_{2}=y_{3}$, $x_{3}=y_{4}$. In this unique circumstance, as you correctly observed, $n\left(\vec{x},\vec{y}\right) = n\left(\vec{y}\right)$, i.e., the number of sentences in which the 3-gram and 5-gram appear jointly is the same as the number of in which the 5-gram appears in total. Thus, in this special case, those two terms cancel, and we are left with $$PMI\left(\vec{x},\vec{y}\right) = \log\left[\frac{N}{n\left(\vec{x}\right)}\right]$$ This is a perfectly valid result, assuming that you are trying to calculate the PMI for this special case. However, it's not a very general result; usually, you'd be considering cases where the words of the 3-gram and 5-gram don't overlap, and thus those count values would not cancel.

$\endgroup$
  • $\begingroup$ Are you sure about N? In mahy case I've seen it is considered as the number of words (not senteces), in this case I wondered if it is the number of words or 3grams? $\endgroup$ – Moh Dec 28 '13 at 20:50
  • $\begingroup$ Would you please take a look at my other question? thanks. stackoverflow.com/questions/20813333/… $\endgroup$ – Moh Dec 28 '13 at 20:53
  • $\begingroup$ I'm not completely sure about $N$; I'm not an NLP expert, and PMI is actually a much larger more general concept that extends beyond NLP. I just tried to define it sensibly for your problem, that's all. If you want to define $N$ using number of words, then I think you might prefer to define it as total number of words divided by number of words in each $n$-gram. Consider a limiting case where your entire data set consists of the same $n$-gram repeated over and over. When you compute the probability associated with that $n$-gram as number of observations divided by $N$, it should come out to 1. $\endgroup$ – stachyra Dec 28 '13 at 21:54
  • 1
    $\begingroup$ @MOLi N indeed is the number of documents. p(x,y) is the probability of x and y occurring together. To convert the count to a probability, you will need to divide by the number of documents. If (x,y) occurs in each document then p(x,y) will be equal to 1, which makes sense. $\endgroup$ – Shirish Kumar May 28 '14 at 5:45
3
$\begingroup$

The problem you are coming across is due to the fact that your 3-grams are a deterministic function of your 5-grams (e.g. just a marginalization). In such cases $I[X:f(X)] = H[f(X)]$ and so your $I[x_2x_3x_4 : x_1x_2x_3x_4x_5] = H[x_2x_3x_4]$ and translating back to pointwise, $pmi(x_2x_3x_4 : x_1x_2x_3x_4x_5) = h(x_2x_3x_4) = -log(p(x_2x_3x_4))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.