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.

Aggregate bigram model and EM

If anyone is interested in playing with the aggregate bigram model, I've got an implementation that you can download and build (provided you have a c++ compiler). Here's the source code. If you want a sample corpus to train on, here's the Brown corpus, and here's some test data. This isn't written to be useful except as a way to play with ABMs, which have kind of strange behavior that might be worth exploring.

To get things running, after downloading, you might try the following on a Unixy terminal (like one of the Linux machines in the lab) or in a Mac OS X terminal:

g++ -O3 -o abm abm.cc
./abm brown.txt chomsky.txt

This will compile the ABM trainer, build a model using the Brown corpus, and then evaluate the model on the contents of chomsky.txt. If you want to change aspects of the model or training (the number of classes, the initialization strategy, the number of iterations), you'll need to edit abm.cc and make changes to the relevant variables and recompile.

Training/test divergence in chess leads to "blunder of the century"

In class, I noted that catastrophic things can happen when the training data do not sufficiently represent situations that can occur in real life -- this is often referred to as the divergence between training data and test data. An interesting instance of this happening in the real world: a high stakes human-vs-machine chess match where the position on the board was simply outside the "repertoire" of the human grandmaster.

It turns out that this has been referred to as "the blunder of the century". In blog comments immediately afterwards, one person wrote, in all seriousness:

I have a bad feeling. No, I can't believe that Kramnik really just overlooked a mate in one. It is almost a must: he may have come down with some health problem, what was able to "disconnect" his thinking (like a mini-stroke or temporary cerebral ischemia or something along that line). At this point I am concerned about his health.I wouldn't be surprised if the next news would be that he is in a hospital.

Chess enthusiasts may be interested in this detailed analysis of what happened, including, as a mentioned, analysis looking at the grandmaster's visual attention as an indicator of what he was thinking at the time.

Monothetic Class

Thanks to Bill for pointing out the concept of monotheticity. (Did I just create a word?)

In a quick googling, most notions of this term seem to be fairly intuitive and easy to grasp:

monothetic

A Dictionary of Zoology | Date: 1999

monothetic In numerical classification schemes, the use of a single criterion or attribute as the basis for each subdivision of a sample population, as for example in association analysis. Compare POLYTHETIC.

(http://www.encyclopedia.com/doc/1O8-monothetic.html)

Monothetic / polythetic classification

A monothetic class is defined in terms of characteristics that are both necessary and sufficient in order to identify members of that class. This way of defining a class is also termed the Aristotelian definition of a class.

A polythetic class is defined in terms of a broad set of criteria that are neither necessary nor sufficient. Each member of the category must possess a certain minimal number of defining characteristics, but none of the features has to be found in each member of the category. This way of defining classes is associated with Wittgenstein's concept of "family resemblances." Monothetic type is a type in which all members are identical on all characteristics. Polythetic type is a type in which all members are similar, but not identical.
...

(http://www.db.dk/bh/lifeboat_ko/CONCEPTS/monothetic.htm)


But it can get worse... :

We call an algebraic group monothetic if it possesses a dense cyclic subgroup. For an arbitrary field k we describe the structure of all, not necessarily affine, monothetic k-groups G and determine in which cases G has a k-rational generator.
...

(http://www.austms.org.au/Publ/Jamsa/V82P3/r104.html)


Polytheticity (YAY! Another new word!) seems to me closely related with fuzzy sets and fuzzy membership, in that they both share the concept of prototypicality; however, in order to be, say, ".7 bird" you don't have to possess 70% of the bird properties (even if they could be monothetically listed ;-)). So these concepts are not the same.


If you want to read more about the relations of these concepts to other probably relevanty concepts to many of us, such as taxonomies, there's also this book:

Typologies and Taxonomies

By Kenneth D. Bailey

(http://books.google.com/books?id=1TaYulGjhLYC&pg=PA7&lpg=PA7&dq=monothetic+class&source=web&ots=LP0J1C8hgW&sig=Vn05C3UEjpxSc2Qksdb9KKrVU_Q&hl=en&sa=X&oi=book_result&resnum=10&ct=result)


-Yuval

Welcome!

This is the class blog for Linguistics 848, Seminar on Computational Learning (an advanced seminar in computational linguistics) at the University of Maryland, Fall 2008. See the course page for more information.