Reactions to reactions so far

Many thanks to the folks who have posted to the blog! (Others: please follow suit!) There are two different but related threads here that are interesting. One stays closer to the "Colorless green ideas" dialogue; that's less about learning, per se, than about the role of probabilistic models in understanding questions linguists care about. There's lots of good discussion to be had there, but I'm not going to head that way right now; I'd just strongly endorse Tim's reminder that folks should read Abney's 1996 chapter, and I'd add Pereira's "...Together Again?" (which hopefully folks have read by now) and also Chris Manning's chapter in the Probabilistic Linguistics volume.

The second thread has more to do with what the course is about and how we can best make it valuable to people. I may have already solved this problem simply by letting other folks teach for a couple of weeks. :-) But let me take up the "hammers and nails" discussion. I do agree that an "If you build it, they will come" mentality may be a bit unrealistic for (linguistic) scientists, as opposed to engineers -- that was my philosophy in developing and deploying the Linguist's Search Engine, for example, but beyond an existence proof that it can be genuinely useful to honest-to-God linguists and psycholinguists (see my BLS paper from a few years back), my goal of helping linguistic theoreticians get more data-driven proved wildly optimistic. As has been pointed out in some of the reaction pieces here, but with slightly different phrasing, a community is more likely to adopt new techniques when they fit a "requirements pull" (what hammers might help with this damned nail?) than when they arise via a "technology push" (here's a cool new hammer, wonder what it's useful for?).

That said, here are two reasons we've been visiting the hardware store to browse the hammer section. The first is analogous to why (from my perspective) we did a seminar about computation and language last year. The idea of computation is central to what linguists (often say they) care about, and there's a whole discipline devoted to really, really understanding what computation is about, that linguists should be aware of, if by "computation" they really mean what they think they mean. Analogously, the entire program of Chomskian linguistics (I loved the idea of "UMDian" linguistics, by the way) is defined by the problem of learning, and there's a whole discipline devoted to really, really understanding the idea of learning in a formal, systematic way. It may be useful or at least entertaining to see the conceptual connections between the fields.

The second reason runs counter to the "nail first" philosophy. There are lots of good reasons to focus on the problems people want solved and find solutions to them; in business, for example, the "solution selling" approach is all about finding the customer's pain and giving them what they need to solve it. But there's a catch: often customers only think they know what they need. Sometimes introducing something new solves pain customers didn't even know they had; and sometimes the "something new" isn't even being used the way it was originally intended!

My favorite example: Was Google designed to compete with bookmarking in Web browsers? Heck, no. Browser developers were driven by the problem of users wanting to keep track of pages they'd visited, and "bookmarks" seemed like a good solution to the problem. But then search got good enough that the page you want often comes up on the first page of hits, especially for "known item" searches where you can generate a very effective query,. Today, lots of people (including me) use browser bookmarks very little, if at all. It's faster and easier just to type a query into Google.

Anyway, bottom line in an already too-long post: I agree that it would be good for the class to involve more discussion of the nails that linguists need hammered, related to learning, no question. I need people's help to address that issue and I'm open to suggestions. At the same time, I'm hoping that people will take the time not only to understand the ideas that are being presented, but also to actively brainstorm and discuss their relevance to issues you care about.

Yeah, what Asad said

I agree wholeheartedly with everything Asad said.

It's often mentioned that NLP turned away from "the old questions of symbolic representations" at the same time as there was relatively suddenly a huge increase in available electronic data (eg. the web) and in computing power to process it. But to be more precise, what we got a lot more of was electronic data about which words appear next to which other words, and linguists have long had a strong hunch that these aren't actually the data which most relevantly characterise a sentence.

It turned out that suddenly the results of the "old methods" (i.e. combining our best theory of which relationships really matter in a sentence, with the negligible data available about these relationships) were inferior to those of the "new methods" (i.e. combining a theory of which relationships really matter which was known to be not-quite-right, with the bucketloads of data available about those), and all the engineers flocked to these new methods, because they worked better. (Who would blame them?!) But I don't think this makes the theory that was known to be not-quite-right any better than we thought.

It might be argued that analysing the "which words are next to which other words" data as NLPers do is relevant for the language acquisition problem that linguists worry about, because this is the data that is available to human infants. I think this is a serious case of missing the point, however, because the infant comes equipped with "the right theory" (by definition) of which relationships really matter, so he/she is not in the same position as the engineers. (For subproblems at the phonological/morphological level, the situation might be more analogous, but I'm thinking more about sentence-level properties mainly.)

An interesting article on this topic, that Philip has mentioned a couple of times in class, is this one by Steven Abney:
http://www.ling.umd.edu/locker/ComputationalLearning/Abney95c.pdf
As may well be clear from the above, I happen to disagree with almost every interesting claim in there, but it does at least get you thinking. Some may remember rather lively discussions arising from this paper in last year's seminar.

What do you want?

Philip's last question in class ("Tell me what you want!" to paraphrase) has spurred this drive-by post. I think, to be completely blunt, while the goal of this course appears to reside in presenting NLP techniques to linguists, I'm not sure that this means of presenting it really serves that purpose. The field of linguistics doesn't seem to work that way: "present me with a set of hammers, and I will find nails." NLP applications have worked that way, because they are engineering. Linguistics, particularly of the sort practised at UMD, is not.

What linguists have done is that they've found the nails first, and if you are a critic, you'd say that they've tried to bang the nails in with their fists. (If you are not a general critic of UMDian linguistics, you'd say that nails analogy is bogus, and I might actually agree with you, but that's the subject of a different post and maybe a different course.) Be that as it may, to accomplish the goal of making this class relevant to linguists, it really has to be approached from the opposite direction of an NLP applications course.

That is to say, it has to be shown that these techniques are in fact the correct set of hammers, and that means starting from the nail. The linguist's accusation against attempts at importing NLP concepts has always been that the hammer is always too big or too little. To reiterate, you can't really say, "Well, I have these techniques, they use data!!! Surely you can find something." The linguist will wonder, as linguists often do, why s/he needs more than s/he already has, and whether LSA is just too big a hammer.

Let's take syntax. A question that seems to have been a biggie for the past little while here at UMD is the "Agree" issue: do we need a special syntactic operation like "Agree"? It's still not clear that NLP techniques serve to resolve these high-level questions (eg, what operations exist and are minimally necessary). And if they don't, then one has to find lower-level questions, perhaps the mechanics of the syntax-semantics interface. But that requires NLP techniques that can map strings to at least the First Order Predicate Calculus in order to do anything at the sophistication that semanticists use.

Since data driven techniques have either sacrificed this approach out of expediency or found them impossible to support, it's hard to make the case for the involvement of NLP in at least those two domains of linguistic investigation (syntax and semantics). I would suggest that the place for these techniques lies in what these techniques do best: finding ways to compare/score the competing predictions of theories. That's a limited role, but potentially an important one, since it is often possible to come up with contradictory interpretations of the data even over a single language when dealing with the ad hoc manual inference that linguists often use. But this limited role will be the case at least until CL/NLP returns to the old questions of symbolic representations that have largely fallen by the wayside in favor of scale. I can't say much about psycholinguistics though, but they generally already seem to use statistics.

Colorless green ideas

Here is Chomsky's footnote 4 from Syntactic Structures, two pages after his introduction of the famous Colorless green/Furiously sleep pair, which, he argues, shows that "in any statistical model for grammaticalness, these sentences will be ruled out on identical grounds as equally 'remote' from English."

One might seek to develop a more elaborate relation between statistical and syntactic structure than the simple order of approximation model we have rejected. I would certainly not care to argue that any such relation is unthinkable, but I know of no suggestion to this effect that does not have obvious flaws. Notice, in particular, that for any n, we can find a string whose first n words may occur as the beginning of a grammatical sentence S1 and whose last n words may occur as the ending of some grammatical sentence S2, but where S1 must be distinct from S2. For example, consider the sequences of the form "the man who ... are here," where ... may be a verb phrase of arbitrary length. Notice also that we can have new but perfectly grammatical sequences of word classes, e.g., a sequence of adjectives longer than any ever before produced in the context "I saw a -- house." Various attempts to explain the grammatical-ungrammatical distinction, as in the case of (1), (2), on the basis of frequency of sentence type, order of approximation of word class sequences, etc., will run afoul of numerous facts like these.

Even without rooting through LSLT, we see that Chomsky has immediately qualified his any statistical model, so I think any schism centring around the Colorless... argument is a result of miscommunication more than anything. This is just an argument that you can't get a blood out of a stone, and distributional information per se is to a theory of syntax a mere bloodless stone (contrary to what some people at the time apparently were proposing).

The details of his argument are not totally clear to me, but the argument about agreement seems to be an argument from nested dependencies, thus, against using a finite-state model; the argument from iterated modifiers seems to be an argument against a model in which we retrieve one of a finite set of strings of category labels, and replace each of the labels with a word. And if I've reconstructed that part of it correctly, the full argument perhaps was meant to be basically what Chris said today: if there's something fundamentally wrong with the model of language with respect to which we keep track of distributional information, then although you may get a reasonable approximation, ultimately, more data, whether you keep track of distributions or not, is not going to help. Having distributional information doesn't replace a theory of language; it presupposes one. Implicitly, one might imagine rounding the argument off by saying, Once we've come up with a proper theory of language, then maybe we can find a role for keeping track of distributions. Or maybe we won't need it.

So how does this relate to the contents of the course? Well, although it seems clear that EM is deeply important, and it's clear that finite state mappings of the kind we've been talking about are part of the language faculty, it's not clear to me that the interesting learning problem in, say, phonology, arises when we know the structure of the model and the only parameters are transition/emission probabilities; the problem is learning the structure of the machine. So these examples are admittedly a bit hard to sink my teeth into. Clustering and constructing features, however--the what's important here problems--we can easily cook up problems that look like that in any subfield of linguistics (for example, representations in both phonetics and phonology).

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.