I was reading a textbook (equation 4.3) on n-gram models and came across this form of the chain rule of probability: \begin{align*} P(X_1 = x_1, \ldots, X_n = x_n) &= P(X_1=x_1) \cdot P(X_2=x_2 \mid X_1=x_1) \cdot \\ &\quad \cdot P(X_3=x_3 \mid X_1^2=x_1^2) \cdots P(X_n=x_n \mid X_1^{n-1}=x_1^{n-1}) \end{align*}

Here the random variable $X$ is the $i$-th word in some sentence. This is for n-gram models. So $P(X_1=x_1,\ldots, X_n-x_n)$ is the probability of a certain sentence $(x_1,\ldots, x_n)$ with $n$ words.

Does anyone know why you can condition on $X_1$ to the power of $1$, $2$, or etc? How is it the same as this form: \begin{align*} P(X_1=x_1, \ldots, X_n=x_n) &= P(X_1=x_1) \cdot P(X_2=x_2 \mid X_1=x_1) \cdot \\ &\quad \cdot P(X_3=x_3 \mid X_2=x_2, X_1=x_1) \cdot \\ &\quad \cdots P(X_n \mid X_{n-1}=x_{n-1},\ldots, X_1=x_1) \end{align*}

I tried googling and I seem to only find the latter form.


I am fairly certain that the source you linked to is using $X_1^k$ as shorthand for $X_1,\dots,X_k$ (sort of like $(X_i)_{i=1}^k$). This seems reasonable because they later go on to say they'll approximate $P(w_n \mid w_1^{n-1})$ by $P(w_n \mid w_{n-1})$. They then define the $N$-gram model, which looks $N-1$ words in the past, by the approximation $P(w_n \mid w_1^{n-1} ) \approx P(w_n \mid w_{n-N+1}^{n-1})$. If this is intended to condition on the previous $N-1$ words, then $w_{n-N+1}^{n-1}$ should indeed be shorthand for $w_{n-N+1},\dots,w_{n-1}$.

  • $\begingroup$ Yes, that's exactly it: $x_1^n$ stands for $(x_1, ..., x_n)$. $\endgroup$ – Marcelo Ventura Jun 10 '16 at 5:15
  • $\begingroup$ Also, "approximate $P(w_n \mid w_1^{n-1})$ by $P(w_n \mid w_{n-1})$" means they assume that Markovian loss of memory applies as a good approximation. $\endgroup$ – Marcelo Ventura Jun 10 '16 at 5:17

It appears to be an annoying shortened notation -- one which should never be used without a clearly highlighted explanation because it can easily be confusing.   I hate those.

The relevant introduction is buried in paragraph 3, on page 3.

For this reason, we’ll need to introduce cleverer ways of estimating the probability of a word $w$ given a history $h$, or the probability of an entire word sequence $W$.   Let’s start with a little formalizing of notation. To represent the probability of a particular random variable $X_i$ taking on the value “the”, or $P(X_i = $“the”$)$, we will use the simplification $P($the$)$.   We’ll represent a sequence of $N$ words either as $w_1 \ldots w_n$ or $w^n_1$.   For the joint probability of each word in a sequence having a particular value $P(X = w_1,Y = w_2,Z = w_3, \ldots, W = w_n)$ we’ll use $P(w_1,w_ 2, \ldots ,w_n)$.



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.