Assumptions of n-gram models

I found myself wondering to what extent this week's class was about particular models (eg. n-gram models and variations) and to what extent it was about techniques for determining parameters of these models (eg. maximum likelihood estimates, expectation maximisation). Of course it doesn't need to be "all about one and none about the other", but I think it's worth keeping in mind that these two things are in principle separable. You might not like n-gram models but the technique of expectation maximisation can be applied to whatever model you prefer, and likewise you might not like expectation maximisation but there are other ways to build n-gram models.

Either way I think we should be clear on the assumptions going into an n-gram model ... if n-gram models are "just an example to show how EM works", then it's worth keeping in mind that the following assumptions were "dispensable" or "inessential" properties of the discussion on Monday, and if on the other hand n-gram models are a substantive proposal for some particular application, then we would obviously like to understand why the following are assumed.

If we have random variables X1, X2, X3, X4, which can take on values like w1, w2, w3, ..., then the following is just a fact:

(1) P(X1=w1,X2=w2,X3=w3,X4=w4) = P(X1=w1) P(X2=w2|X1=w1) P(X3=w3|X1=w1,X2=w2) P(X4=w4|X1=w1,X2=w2,X3=w3)

We played around with the following approximation to this probability:

(2) P(X1=w1) P(X2=w2|X1=w1) P(X3=w3|X2=w2) P(X4=w4|X3=w3)

Already this makes two assumptions:

(3a) Each random variable is conditioned on exactly one other (except for X1)
(3b) There is no random variable on which two other distinct random variables are dependent

Just to make those clear (and make it clear that they're independent of each other), (3a) would not be true in this case ...

(4) P(X1=w1) P(X2=w2|X1=w1) P(X3=w3) P(X4=w4|X3=w3,X2=w2)

although (3b) is certainly still true here.

(3b) would not be true, however, if we used an approximation like this:

(5) P(X1=w1) P(X2=w2|X1=w1) P(X3=w3|X1=w1) P(X4=w4|X1=w1)

although (3a) is certainly true here. In general, these other approximations in (4) and (5) are just as "sensible" as (2) is. Which one makes more sense will just depend on what the variables actually mean. If X1, X2, X3 and X4 represent the weather on four consecutive days (in that order), then we could probably do a lot worse than the "beads on a string" approximation (2). On the other hand, if X1 represents the weather today in a particular place and X2, X3 and X4 represent the weather today in three other nearby places, then the "spokes on a wheel" approximation (5) probably makes more sense.

Also, we said that the approximation in (2) has W^2 parameters, where W is the number of possible values for variables like w1, w2, etc. (Plus another W parameters for X1 but let's ignore that.) There's one more assumption going into this, which is easily missed in the abbreviated P(w2|w1) notation:

(3c) The relationship between X1 and X2 is the same as the relationship between X2 and X3, and the same as the relationship between X3 and X4. ie.
P(X2=w|X1=w') = P(X3=w|X2=w') = P(X4=w|X3=w')

This assumption is necessary for there only to be one "table of parameters", as Philip put it, with W columns and W rows. Without this assumption, we would need three such tables: one for the relationship between X1 and X2, another for the relationship between X2 and X3, and another for the relationship between X3 and X4.