tag:blogger.com,1999:blog-5275657281509261156.post251850714491600527..comments2024-03-28T04:04:55.806-07:00Comments on Faculty of Language: Alex Clark Had A Point: A Good OneNorberthttp://www.blogger.com/profile/15701059232144474269noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-5275657281509261156.post-79945608325001176882013-09-20T00:41:21.306-07:002013-09-20T00:41:21.306-07:00Just to play advocatus hornsteinum here, since Nor...Just to play advocatus hornsteinum here, since Norbert's bowed out of that role for this post, it seems like really the value of formalising is that you wind up correctly and thoroughly processing more and more subtle theoretical points. You could imagine doing this without "formalising" per se. If I were a syntactician I would have the option of spending all day thinking about theory internal details. The trick if I wanted to reap the benefits of formalism would merely be to think really hard, be honest about when I get stuck, and make some really careful notes. I would use formal deductive apparatus only when absolutely necessary - when I was certain that I could not come to correct conclusions without it. (In fact, that seems pretty close to the way most effective people start off work on anything.) The result needn't be a tome that lays out the pieces of a formalism well enough for anyone to build new things - just enough details for you to get the answers you wanted. There must be good examples of this.ewanhttps://www.blogger.com/profile/00161859381870853353noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-91768971852863926432013-09-18T10:15:04.786-07:002013-09-18T10:15:04.786-07:00Norbert alerted me to this excellent catch by Alex...Norbert alerted me to this excellent catch by Alex & Thomas: this is indeed *exactly* the place where a good formalization can shine, helping us to see what's amiss and *constructively fix* a linguistic theory. They are right: packing too much into features can blow up in your face, leading to a detectable jump in computational complexity. In particular (see Chs. 6-8 of Barton, Berwick, and Ristad, 1986), readers may recall that GPSG (&HPSG) also uses complex features to encode the derivational chains found in 'conventional' transformational (GB style) grammars (linguists: think Pesetsky-type 'containment paths' or Kayne's unambiguous paths). <br /><br />But this comes at far too high a price in complexity dollars. Gazdar, Pullum, Sag & Klein's 1985 version of GPSG admits more than 10^775 possible (binary-valued) features for even a single, fixed grammar like English. And it's far far worse than that – if we look at the space of possible GPSG grammars, just finding whether a given category satisfies a (finite) set of feature co-occurrence restrictions is intractable (PSPACE complete). And worse still, each of these separately complex components of GPSG *interact*, so that the system as a whole blows up even more -- taken together, Ristad shows that the entire system is exponential-polynomial time complete -- this is off-the-charts worse than 'mere' NP-hard problems since it includes all exponential time problems, including problems that are provably intractable. (This does not contradict the fact that the weak generative capacity of such GPSG grammars is only context-free so that the resulting languages are recognizable in cubic time. As Shieber 1983:137 observes, the problem is the grammar size: typical post-Gazdar GPSG systems "contain literally trillions" of rules.) <br /><br />In fact, as Eric shows, if we call m the size of the GPSG grammar, and n the input sentence length, then the time to recognize a sentence of length n wrt to the GPSG grammar G is doubly exponential in m, which is pretty frightening: it means that if a grammar with 2 symbols recognizes a sentence in 0.001 second, a grammar with 3 symbols would recognize the same sentence in 2.5 hours, and with 4 symbols, at least 10^63 *centuries.* Gulp. And this worst case really pops up, e.g., the GPSG grammar for English contains more than 10^33 admissible local trees. <br /><br />But the *real take-home message* is that Ristad uses this complexity result as a *diagnostic probe to fix GPSG theory*. The idea is to see how each part of GPSG theory is contributing to the bad result and what can be done to restrict the wayward component. For example, he shows that the feature restriction machinery can be chopped down so that it operates only locally. Ristad runs through 10 such problem areas. The end result is a more linguistically transparent and less complex grammatical system - revised GPSG - which falls into 'merely' the class NP. Now, you need not buy any of Eric's particulars, but this seems to me precisely the kind of juice we want to squeeze out of formalization.Robert Berwickhttps://www.blogger.com/profile/01114260546073129733noreply@blogger.com