I have a text corpus, from which I have computed the unigram probabilities of every word.

Now, let $p_{i}$ & $p_{j}$ be the unigram probabilities of $i$ and $j$ respectively, what will be the probability with which a pair of words $i$ and $j$ will co-occur(within a maximum gap of 1 word) when independence between $i$ and $j$ is assumed?

EDIT: Here $p_{i}$ is the probability of any given word being $i$.

By co-occurrence probability, I mean the chance that word $i$ & $j$ co-occur in a random sequence of three words drawn from the corpus. By co-occurring I mean that $i$ and $j$ occurring anywhere in this 3 word random sequence within a maximum word distance of 1. (For example, $i$*$j$ and $ij$ are both valid co-occurrences of $i$ & $j$ but $i**j$ is not a valid co-occurrence since the distance between $i$ & $j$ is more than 1.)

And finally, $ijij$ counts as 3 co-occurrences.

  • $\begingroup$ I think we need a bit more information. What precisely is $p_i$: is it the probability of any given word being $i$, or the probability of $i$ occurring in a document? What do you mean by co-occurring: is it $i$ and $j$ occurring at a specific place, or $i$ and $j$ occurring anywhere in a document? Finally, would something like $ijij$ count as 1, 2 or 3 co-occurrences? $\endgroup$ – Simon Byrne Jul 20 '11 at 11:57

By the Principle of Inclusion-Exclusion, the probability of no co-occurrences of i and j in three words equals the probability that i fails to appear plus the probability that j fails to appear minus the probability that both i and j fail to appear. Subtracting this from 1 will yield the answer. The independence assumption lets us compute all three probabilities by multiplying the relevant "unigram" probabilities, whence the probability of a co-occurrence of i and j equals

$$1 - (1-p_i)^3 - (1-p_j)^3 + (1 - p_i - p_j)^3$$

$$= 3 p_i p_j (2 - p_i - p_j).$$

For example, when $p_i=p_j=1/3$, this formula gives $4/9$. The 12 possible patterns of co-occurrence can be symbolized as iij, iji, ijj, ij*, i*j, jii, jij, ji*, jji, j*i, *ij, *ji, each with equal probability of $(1/3)^3$. The chance therefore is $12/3^3=4/9$, agreeing with the formula.


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.