Statistical models of grammar induction, by which I mean models that estimate a probability distribution over both syntactic analyses and word strings after observing only word strings, are typically a type of model called a generative model. This notion of "generative" is actually pretty similar to the notion of "generative" in modern syntax: there is an inventory of re-usable substructures or pieces (like context free grammar rules, which are really just local subtrees), and structures and word strings are produced by selecting pieces from your inventory. The primary difference from standard syntax is that each choice is associated with a probability score.

Now, there's a little bit of a technical wrinkle here, and I was wondering if the other commenters here had any reactions. The thing that makes these models "generative" in the statistical sense is that each "probability score" is restricted to be a conditional probability of the right hand side, given the parent node. So if you fix the parent node, and add up the probability score of each possible right hand side of that parent node, the sum will be one. This constraint on the probability scores is computationally convenient, because it means we can guarantee that the probability of every tree sums to one, since the probability of every subtree sums to one in this recursive fashion, and we can get the probability of any particular structure by just multiplying the probability scores of the pieces that actually appear in that structure. However, this has the consequence that the model as a whole is parameterized in terms of observations given latent variables.

An alternative is to allow the "probability scores" to be any non-negative number, using what's called an undirected or energy model. There are two reasons that people don't do this in practice. First, if probability scores are any non-negative number, and there are unobserved variables (we only see words, not dependency arcs, for example), the computational complexity gets really bad. If we multiply the probability scores of each piece in a structure, the resulting number is only proportional to the probability of the structure (the constraint in generative models just guarantees that the proportionality constant is always 1). To actually get the probability of the structure, we have to add up the products of the probability scores of all the pieces that we could have used, including the strings that we could have seen but did not. Obviously, doing this kind of sum exactly is impossible (although random approximations are possible). Second, it turns out that undirected models do not have any more expressive power than directed models: it's been proven that given any set of weights from an undirected model, it is possible to find a set of conditional probabilities for the corresponding directed model that produces exactly the same probability distribution over structures.

So people pretty much never use undirected models for grammar induction: even though they are perfectly well-defined, they are a nightmare computationally, and don't buy you anything in principle. On the other hand, they have different biases, so we might end up learning a different distribution over structures in practice. Also, it leads to this weird situation where we are learning models that are parameterized in terms of the probability of the observations given the unobserved stuff:



even though we usually don't care about the probability of the stuff we saw: if you "run" the models in this direction to generate new "observed stuff" like word strings, you typically get garbage. What we usually care about is the probability of the unobserved stuff given the observed stuff. You can do this by using Baye's rule to "run the models in reverse:"



i.e., we see a sentence and we want to know how to parse it; we don't care what the probability of that sentence is.

On a more theoretical level, though, I wonder how important this issue is. I mentioned in another thread that a notion of grammaticality based on typical sets might be interesting, but the feasibility of such a model relies on getting good probabilities when running the models "forward." Another thing to consider is the potential for theoretical tidiness, with one generative model responsible for both production (running "forwards") and perception (running "in reverse"). On the other hand, maybe it just isn't possible to partial out specifically linguistic influences (subject-verb agreement) from general knowledge (movie-popcorn agreement) in string probabilities.

I don't necessarily have a specific question, but these are some things I've been thinking about lately and wondered if anybody had any reactions.

(PS feel free to move this to the computational or out-of-the-box section... I wasn't sure whether to classify based on topic or methodology...)

Interesting post. I don't have too much of a direct response, but I have several related ideas. Sorry this might drag the discussion to a tangent...

1. Computational complexity
This is a huge issue in engineering (speech recognition, machine translation, etc.). But it apparently isn't much of an issue in cognition-- we do this quite easily. It's hard to know exactly what the complexity of the brain is compared to a computer, but whatever the correct algorithm is, we should be able to implement it in linear time for example.
If the best algorithm found is one that is computationally impractical, it is probably the wrong algorithm. That's an odd puzzle because the problem does really seem to be very complicated.

Yes, this is what I was trying to get at. Researchers have been avoiding undirected models because they are hard to engineer, but, since people probably use a resource-limited approximation algorithm anyway, this isn't really a justification for completely ignoring undirected models. There are still practical issues, however, in interpreting an implementation that relies on lots of approximations: is the behavior of our implementation due to the model, or to the kind of approximation our inference makes, or both?

2. What is the object of study?

For me, at this point, the object of study is the data available to children. What kinds of assumptions about the shape of linguistic structures turns that data into good evidence for structures? The algorithm the child uses is in principle separate from the assumptions about possible linguistic structures the algorithm makes; or, to put it another way, there are many different algorithms that rely on the same set of assumptions (or biases, or prior expectations) about what linguistic structures look like, and I'd like to tackle the issue of learning biases without having to get the details of the learning procedure right. The clearest way to do this is to use a really accurate inference procedure, so we can be confident that the conclusions about linguistic structure that our implementation reaches after seeing data are due to the model assumptions.

So what's left at the actual hierarchical structure?
Core relationships like modification and argument-selection. Maybe almost nothing else.

This sounds reasonable to me. In practice, the grammar induction systems that people have gotten to work have relied on dependency grammar or CCG representations that focus on modification and argument-selection. Grammar induction systems that model the details of linear order have not worked.

(There is a complication here in that obviously we need some kind of hierarchical structure to begin interpreting in the first place such as recognizing "try to" as a control structure rather than some other linear string. But I'll set that aside for now. It's probably some kind of boostrapping.)

In short: I think syntacticians are looking at the wrong thing.

So for your question, this suggests that building up a bunch of subtrees from surface form is the wrong approach and hence why it is computationally difficult and not especially reliable.

I'm a bit confused by this suggestion. Building up a bunch of subtrees from surface forms is not that hard and can be done relatively efficiently. What is hard is estimating probabilities for those subtrees if we don't constrain the probability score of each piece to be conditional probabilities. Or maybe I haven't understood your suggestion?

Quote

Yes, this is what I was trying to get at. Researchers have been avoiding undirected models because they are hard to engineer, but, since people probably use a resource-limited approximation algorithm anyway, this isn't really a justification for completely ignoring undirected models. There are still practical issues, however, in interpreting an implementation that relies on lots of approximations: is the behavior of our implementation due to the model, or to the kind of approximation our inference makes, or both?

The word "approximation" bothers me. Given the fact that children do learn language, they probably end up adapting it to the most efficient form for processing in some sense (broadly), so it probably isn't something that needs to be approximated-- it probably is relatively optimized, as a system.

Of course in terms of surface form, they are approximating something, such as distribution probabilities.

So I think we agree on this.

Quote

For me, at this point, the object of study is the data available to children. What kinds of assumptions about the shape of linguistic structures turns that data into good evidence for structures?

I agree, but the details are crucial: how is that input interpreted? What is it mapped onto?
I would tentatively say something like: they are identifying relationships in the sentences (dependencies) and mapping them probabilistically to forms.
I wouldn't say that they are analyzing surface forms directly.

Hmm, maybe my confusion has to do with the term "surface form" and "distribution probabilities" that are in "terms of surface form." What do you consider to surface form? Sometimes people use "surface form" to mean the string that is generated, and sometimes they use "surface form" to mean the whole structure after a series of operations, like transformations, have been applied. These models define probabilities over structures, they're not just relying on n-gram statistics from the string.

On the other hand, maybe it just isn't possible to partial out specifically linguistic influences (subject-verb agreement) from general knowledge (movie-popcorn agreement) in string probabilities.

I love it. I'm going to use that phrase next time I teach competency.

I've never been a syntactician, but certainly this is the direction that phonology has been moving for the last ten years or so. Optimality was an extremely ambitious formalism in its day, but it has more or less crumbled under its own weight. Most contemporary work attributes a great deal more importance to lateral forces: acoustic and articulatory mechanics, repetition, metalinguistic awareness, even "knowledge" located not in individuals but rather groups collectively. I'm biased here of course, and I'd love to see phonology reclaim it's seat as the heart of language theory, but if the field offers anything to linguistics generally its the notion that we really need to start considering a wider variety of *things* to constitute language.

I'm also struck by the (very non-scientific) experience of raising a couple of language-acquiring kids. Your average child is "fluent" in pragmatic function long, long before anything like compositional syntax shows up. That seems significant.

Many models take the input string and separate it into chunks then attempt to assign those chunks to a structure. I'm suggesting that those chunks will never match the correct structure because the structure operates at a different level. Of course it's related and so you'll get partial accuracy, but it won't ever be 100% working with only chunks of the input string.

Maybe you are talking about Steven Abney's 1991 "parsing by chunks" paper? Or Elias Ponvert's chunking-based parser? Or, if I may be so vain, my own paper on learning syntactic chunks using words and acoustic measures? Or was there another example you had in mind? (a serious question, since I can't think of any other chunk-based parsers with a cognitive spin).

Haha, what do you call an ambiguous typo? I thought "fro" was supposed to be for "from", and djr33 was asking how you got to talking about phonology when I started by talking about syntax (although in principle the same issue applies in computational modeling of phonology acquisition, there just hasn't been as much work on unsupervised, large scale speech recognition as there has been on unsupervised grammar induction).

Oh.

Quote

How'd you get there, fro this? (I'm genuinely curious.)

from

For or from, I'm not really following the question I'm afraid. He said "maybe it just isn't possible to partial out specifically linguistic influences", and I said (to paraphrase) "this is the rising opinion in phonology". That didn't seem like a particularly large jump to me when I wrote it.

I got that much
But--

Quote

I'd love to see phonology reclaim it's seat as the heart of language theory

Was that just a casual aside or did you mean that there was some implication it might happen?

If the past is any guide to the future, it will almost certainly happen. Linguistics has a very long history, and (like everything else) phonology has risen and fallen in prominence several times. In fact, before Chomsky, syntax wasn't really seen as requiring much explanation.

Though the generative turn shifted attention strongly away from phonology and morphology, generative models have actually been extremely productive in phonological research. But, they've never been quite sufficient. The lines have always been blurrier, and phonologists have generally needed to appeal to "something else" in addition to computational formalism in order to make the data work. Jkpate speculated here that syntax too might need a something else, and I'm curious (professionally and personally) to see if that ends up being true.