Grammatical Zombies

The talk on the street is that linguists should stuff their portfolios with probabilistic grammars as they have intrinsic advantages over the old, stogy under-performing non-probabilsitic grammars of yore.  Partisans assure us that going probabilistic makes the learning problem easier, reduces the need for rich innate structures, and even lowers cholestoral levels. Though I am genetically inclined to skepticism (especially about things that sound too good to be true), debunking these claims has always required talents above my pay grade.  Lucky for me I know people who understand these issues deeply and are able to translate their significance for the unwashed, i.e. me. This is all preamble for the following post by Bob Berwick, someone that I have been able to persuade to post on an occasional basis, (hopefully not too occasionally) especially on technical topics from computational linguistics. The bottom line is that ideas that are too good to be true aren't, though their intellectual half lives can be very very long, as Bob explains below. Btw, I stole the title for this post from Bob's apposite reference to John Quiggin, an Australian economist who has done yeoman's work debunking hard to kill bad ideas in macroeconomics.

                                                             Going off the Gold Standard

                                                                     Robert C. Berwick

You don't have to wander very far along the computational linguistics byways these days to stumble across what economist John Quiggin dubs “zombie ideas” - bad memes like “supply-side economics after the Clinton boom and the Bush bust – repeatedly refuted with evidence and analysis" yet somehow always rising from the dead.  Among these, two stand out, virtually articles of probabilistic faith: One, that Gold’s (1967) celebrated results about the non-learnability of most language families given positive-only evidence become moot, once one “goes probabilistic.”  And two, that “going probabilistic” can be cashed out simply by adding probabilities to context-free rules, rendering probabilistic context-free grammars easier to learn than their context-free counterparts.  Easy enough, in fact, to drive a stake through the heart of Demon Rationalism (aka, prior constraints on grammars).  But is any of this true?  Or is it instead, to quote the now-immortal words of Meygn Kelly on election night, just “math you do as a Republican to make yourself feel better”?

Well, Yes and No.  Yes, in that nearly every thoughtful scholar of language learnability, starting just a few years post Gold-rush, bound up in the foundational work of Jay Horning, Jerry Feldman, and Ken Wexler, in the late 1960s, and up to the present day, has stressed that the tough Gold standards for learning exact identification of languages on all possible positive texts – are cognitively implausible and overly restrictive, so should be relaxed in favor of what's called “probabilistic example presentation” and “probabilistic convergence.”  That was, and still is, the consensus view.  In other words, from the very beginning of serious research into language learnability for natural languages, the probabilistic view has stood front and center.  All agree we’re after a learning standard that ensures much more: feasibility. (Chomsky's words, 1965, pp. 53-54) or what Ken Wexler (1980) termed “easy learnability”, that is, “learnability from fairly restricted primary data, in a sufficiently quick time, with limited use of memory” (p. 18).[1] [2]

In probabilistic presentation, a learner gets sentences drawn from some underlying distribution, and only has to succeed on positive example sequence that it gets with sufficient probability, rather than on all positive example sequences, as with Gold.  And in fact, there’s a technical sense in which this move does the trick.  When learnability on all texts – the Gold standard – is relaxed in favor of what Ken Wexler was first to call “measure-1 learnability” at a Stanford workshop in September, 1970, then, unsurprisingly, moving the goalposts changes the game.  What perhaps is surprising is this change seemingly moves the goalposts almost to the line of scrimmage: now, instead of no interesting language classes being learnable, all interesting language classes are learnable (officially, all recursively enumerable language families).

Why?  Picture sentences being spit out one at a time by some underlying stochastic source (aka, the “I blame the parents” model), so every sentence occurs with some probability. (Assuming independent draws – what’s technically called “i.i.d” – draws from an independent and identically distributed stochastic source).  In that case, a learner cannot count on using some vanishingly rare example sentence as a red flag for their correct target language. So, we don’t want to insist, as Gold did, that the learner must succeed on all texts.  If figuring out that your language is English means having to wait for the one David Foster Wallace sentence that begins “Uninitiated adults who might...” and trundles to a close 90 words later with, “subdued, almost narcotized-looking,” then you know you’re goose is cooked.  However, if a learner knows that all longer and longer sentences always become less and less likely, then it can know with high confidence that e.g., the first 100 sentences are more than enough to sort out what particular target language your source has been pitching.

And this is exactly what Horning (1969) did.  He attached probabilities to context-free grammar rules, to get probabilistic context-free grammars (PCFGs).  So for instance, if there are 2 rules in a grammar expanding NPs, NP → Det N and NP → Pronoun, then we have a probability of 0.5 for each.  Since every rule in a PCFG is assumed to be statistically independent, the probability of any particular sentence is simply the product of the probabilities of the rules deriving it.  As sentences get longer and longer, their probabilities must shrink – they become exponentially less likely. If the learner knows this in advance, then it knows that very long sentences are so unlikely that they can be effectively eliminated, with the problem reduced to essentially that of learning to identify a family of finite languages. But we already knew that finite language families are learnable from positive-only examples.[3]

In fact, as Horning (1969, 80-81) suggests, one need not rely on any conventional probability distribution over context-free grammars and languages; one could substitute, for example, a measure that ascribes exponentially lower probabilities to larger grammars, and search for target grammars in order of increasing length, or even a probability measure that just assigns the value 2^–i to the grammar enumerated at step i, G_i (as discussed by Ken Wexler, 1980, fn. 22, 529-532; this is one way to develop the notion of an evaluation metric, something we’ll consider in later posts).  More generally, any so-called uniformly computable probability measure works (as proved in Dan Osherson, Michael Stob, and Scott Weinstein’s book, 1986, chapter 10 pp. 187-188, and by Angluin 1988).

So, are we done? Does adding probabilities to context-free rules really make them easier to learn?  No, there's a catch. TANSTAAFL (viz. There ain’t no such thing as a free lunch!). The measure-1 result holds scant cognitive interest (though it can be said to point the way to what constraints we really do need for human language learning models).  Why? The positive results for measure-1 learnability only work if the learner has extremely strong prior knowledge about the probability distribution that's feeding it sentences.  If you really want the learner’s tabula to be a little more rasa, then as the late Partha Niyogi put the matter, “when one considers statistical learning...all statistical estimation algorithms worth their salt are required to converge in a distribution-free sense” (Niyogi, 2005, p. 67).  So that’s to say, suppose the learner doesn’t have any pre-conceived (and accurate) notion of how the example sentences will be distributed. Problem is, Niyogi then shows, as per Angluin (1988), that distribution-free statistical learning collapses back to Gold learning: if a family of languages is measure-1 learnable in a distribution-free sense, then it is Gold learnable.  Measure-1 learnability doesn't enlarge the class of learnable languages one jot. Oops.

As if that weren’t enough, the assumptions blow away any remaining cognitive fidelity we thought we had won.  For one thing, the statistical independence of PCFG rules is precisely what has been explicitly and strongly rejected by the same folks who embrace Horning, in the recent flood of parsers statistically trained in a supervised way from pre-parsed corpus data.  Rather, such rules are plainly dependent: once you decide a sentence is NP VP, then it’s far more likely that the NP, being a subject, will be expanded as a pronoun, with the reverse true if the NP’s an object – which is just to say that PCFG rules aren’t really statistically independent.  The assumption that sentences are pitched to the learner in i.i.d fashion is plainly wrong.  Nobody believes parents speak this way.

Then too, Horning’s method for selecting grammars – explicit enumeration along with search using Bayes’ rule to hunt for the highest posterior probability grammar given the examples, sometimes collapsing phrase names together and sometimes splitting them apart – proved to be computationally intractable.  (It’s also not a wit different conceptually from what’s been advanced by contemporary Bayesian enthusiasts as far as anyone can tell.) Horning himself remarks on how slow his “550 line Lisp program,”  “EVALUATER”, ran, in part because “the enumerative problem is immense” (pp. 199-120). It could only (partly) find grammars with 2 or 3 nonterminals. To be sure, computation speed has increased by leaps and bounds over the past 35 years from Lisp/36 running on an IBM 360/67. And computer scientists have come up with faster methods to solve Bayesian problems, often approximate – ‘variational Bayes’ and the like.  Nevertheless, the immense space of possible PCFGs – larger than the space of CFGs – confounds search methods to this day.

So in truth, Horning’s enumerative method doesn’t nearly go far enough. PCFGs don’t turn out to be any “easier to learn” than their non-probabilistic counterparts –  perhaps what’s meant here is that it’s  more straightforward to use known techniques to estimate PCFG probabilities.  However, that’s not the same thing as learning the underlying rules themselves.  In fact, estimating language distributions is harder in principle that estimating languages simpliciter, as Niyogi (2005, p.68) observes.  What’s needed, rather, is far, far, stronger medicine, something along the lines of Ken Wexler's “bounded degree of error” approach, in which the possible mistakes a learner can detect with respect to sentences of at most 2 embeddings spans the entire space of all possible errors across a complete family of transformational grammars.  Crucially, Ken’s approach is not enumerative.  Instead, it carries out a search in a tightly-bounded, finite space, with each learning step incrementally improving a single transformational component, rather than selecting and throwing away wholesale entire grammars. But to get this to work, Wexler found out that one must impose far stronger a priori constraints on the family of grammars or languages. 

In our internet era where it sometimes feels as though a veil of ignorance has been drawn across any work that was accomplished before 1990, it is well worth remembering that by that September 1970 workshop held at Stanford, Wexler and colleagues had already set up this model for learning transformational generative grammar where both presentation and convergence were probabilistic, in just the sense described by modern day probability enthusiasts – and found this was not nearly enough.  One had to include constraints on grammars, constraints that wound up to be empirically attested, like locality constraints on how far one could displace phrases.  That work, establishing a positive learnability result, still stands – though rarely cited by statistical enthusiasts despite its probabilistic underpinnings.  In fact, it’s apparently even been recently revived just this past year, in work by Mark Steedman and colleagues (2012), though without any apparent tip of the hat in Ken’s direction.  Mark uses combinatory categorial grammar instead of transformational grammar, but in many other ways follows Ken's model, with the learner using (meaning, surface string) pairs.  Plus ça change.

Next: Why Revolutionary new ideas do appear infrequently.

---

[1]A partial list of people embracing this view would include Jay Horning (1969); Henry Hamburger and Ken Wexler (1970, 1973, 1975); Bob Matthews (1979); Peter Culicover and Ken (1980); yours truly (1982/1985); Dana Angluin (1988); and Partha Niyogi (2005), among others. Here's Horning, 1969, 19, fn. 1, “In the sequel, when we prove identifiability in the limit with text presentation, it is with a different performance requirement, and a different condition on the presentation.”

[2]Here is the quote from Wexler's presentation at a September, 1970 workshop held at Stanford p.159 “A language class is identifiable in the limit with probability 1 with respect to a probabilistic presentation scheme if there exists a learning procedure such that for any member of the class there is a subset of measure 1, of the set of presentation sequences for which the procedure identifies in the limit the language."

[3]In fact, Horning, in what seems to have gone largely unnoticed by statistical enthusiasts stresses several times that his results hold only for the case of unambiguous context-free grammars: 1969: 32-33: “In the sequel we assume...that unambiguous grammars are desired, and will reject grammars which make any sample string ambiguous.”  Of course, on the assumption that natural languages are ambiguous, this immediately makes his results unacceptable from the standpoint of cognitive fidelity.  It’s hard to know just why this has been overlooked for 45 years.  Putting aside the possibility that the people citing Horning in fact haven't really read his thesis, luckily, this omission is of little importance, because Horning simply didn’t know how to place a properly-defined probability measure on the languages generated by ambiguous context-free grammars, a matter that has since been remedied by Osherson, Stob, and Weinstein (1986), who established a far more general result encompassing Horning’s, as noted below.