The hunt for new syntactic theories

It seems like syntacticians, of both mathematical and generative stripes, are constantly hunting for a new and improved syntactic theory. But I'm not really sure what we are supposed to be looking for. Surely now, it is established that any theory capable of generating languages of sufficient complexity is capable of "capturing the data" or describing it or whatever. Yet syntacticians still publish papers where they demonstrate that some new notion or theory is capable of deriving some fancy piece of data that somehow eludes the others. Is this really what they are doing? Because this seems like a moot argument.

It seems to me that, if there is to be any rationale for improving syntactic theory, it should be something like cognitive plausibility or computational effectiveness, or perhaps even theoretical elegance. I don't know what people are driving at, because the desiderata of a better syntactic theory are almost never discussed. Should we all know what we are seeking? Because I'm not so sure anymore, and thus I am not convinced we should continue to hunt around. For the moment I'm satisfied that type-logical grammar is capable of deriving everything that needs to be derived. Am I wrong?

Analog computation

This post is a quick precis of something that I hope works out a little longer. There has been, over the years, some amount of research on the complexity theory of analog computation (i.e., using analog devices with no quantization or digitization, which operate in continuous time over the real numbers). There is not, as yet, a good and complete theory of this, but some key recent papers that a person could start with are found in the book New Computational Paradigms (Springer 2008).

One question that continues to be debated is whether analog algorithms have the same constraints or lower bounds on complexity as digital algorithms computing the same results. In the most extreme view, it has been suggested that analog methods could be used to solve NP-hard problems quickly, perhaps in polynomial time. Some papers have analyzed this question, and the results so far appear to be negative. For example, a paper posted online by Warren Smith of NEC Corp. (1998) showed that in order for the above suggestion to hold of a particular kind of physical computer (a "plane mechanism"), some other implausible things would have to be the case as well.

OK, so maybe we cannot go all the way from NP-hard to P. But this doesn't in any sense prove that the lower complexity bounds are exactly equal. There are plenty of digital computations which, while not NP-hard, are still crappy in practice because they involve some large power of the input. What good is polynomial time when the algorithm's average case complexity is O(n^82) for instance?

Why is all this important? Well, cognitive science entertains a wide array of computational models, which are usually being proposed as "cognitively plausible" in some vague sense. So now there are debates about how tractable should a simulation need to be in order to seem cognitively plausible. But, all the simulations are digital. Meanwhile, the brain is not digital, it is some sort of analog system. I think that debaters need to take care over this mismatch, because there is no clear correspondence between the complexity of a digital computation and the complexity of an analog computation accomplishing the same task.

Neuroelectrodynamics

One of the million or so things that interest me is the question of how the brain actually accomplishes anything. This is relevant to linguistics because, well, that's sort of obvious. A prevalent model of neural computation tells us that the brain computes by passing information among various neurons, and that these neurons encode messages in sequences of action potential 'spikes' by a mechanism known as "spike timing."

A new book by Aur and Jog challenges this whole paradigm. It carries the strangely ungrammatical title Neuroelectrodynamics: Understanding the Brain Language and the grammar between the covers is no improvement, but it is very provocative and enticing to those of us who think that the current state of understanding in neuroscience is extremely poor.

The authors first demonstrate that neuron 'spikes' are not uniform or stereotypical, which itself goes against a main tenet of the spike timing model. They then outline a new scheme by which a new quantity of spike 'directivity' is encoded into the charges in movement during an action potential. Empirically, the details of dendritic arbors and axonal branches significantly modulate the extracellular action potential. Axons themselves cannot be approximated by linear cable models.

In the authors' charge movement model, different charges or groups under an electric field have distinct movements. To apply independent component analysis (ICA), the action potential is assumed to be the result of several independent sources, generated by charges that move. For recorded action potentials, blind source separation (a known signal processing technique) can be performed using ICA. The charge localization is obtained from triangulation and a point charge approximation. Singular value decomposition is performed for the matrix of charge coordinates. A 'spike directivity' can be described by a preferred direction of propagation of the electric signal during each action potential, and approximated with a vector. This is shown to be a much more effective means of encoding information and computation than spike timing. Details of the spike directivity are said to be published in other papers by the authors, which did appear in major neuroscience journals.

It is interesting to see how the current paradigm in neural computation could well be founded on nothing. The authors' ideas may not be proven, but they certainly have some interesting empirical findings which defy explanation otherwise, and it seems clear to me that the brain can't be doing all its work with spike timing.

Road to Reality

This summer I've been reading one of those few books that can change your life, The Road to Reality by Roger Penrose. This is basically all of modern theoretical physics, including the mathematical fundamentals starting from first principles. I have finally gotten through all the initial mathematical chapters, which include a quick rundown of Riemannian geometry and differential forms on manifolds. Why is it that mathematical physicists make the best math teachers? I also changed my life a few years back by reading Lectures on Mathematical Physics by Robert Geroch.

I suspect that this approach to geometry could be useful for a new approach to semantics and cognitive science (see previous post on the musings of Fenstad).
Geometry is so crucial to our understanding of reality (i.e. physics), it should not be surprising if it turns out to be crucial to our understanding of language and cognition as well.

Grammar, Geometry, and Brain

J. E. Fenstad has a provocative little book called Grammar, Geometry, and Brain (CSLI 2010). It is speculative and is sort of like an annotated bibliography, but as such it is very valuable as a discussion of work in cognitive science and brain modeling at the interface with linguistics. Fenstad is a mathematical logician and occasional linguist. The book is filled with his own preferences and experience, but it is very forward thinking, perhaps venturing into the crackpot, but that's OK with me. It is inspiring.

Fenstad states "you can never be more than the mathematics you know," something I heartily agree with. Like him I will continue to seek out new mathematics to apply in linguistics. I'm tired of formal language theory and logic, these tools cannot be everything for linguistic theory. Fenstad's suggestion is that Geometry can provide a direct link between linguistic theory and cognitive modeling. He points to the Conceptual Spaces framework of Gärdenfors (MIT Press 2000) for a geometrical theory of semantics which he suggests could be connected to syntax using attribute-value grammar. He also discusses several works in cognitive neuroscience, suggesting how geometry could play a role in a bridging model connecting neuronal assemblies to conceptual spaces. It's an interesting book that pointed me to a lot of other readings.

What makes languages learnable?

A recent paper by Ed Stabler (in Language Universals, Christiansen et al. eds. 2009) puts the focus on an important question that is rarely formulated in the literature. What are the structural properties of natural languages which guarantee learnability? We know from a variety of negative results going back to the famous Gold theorem that such properties have to go far beyond the defining principles of the Chomsky hierarchy, since none of the traditional language classes except the finite languages are strictly learnable, in the sense of identifiability in the limit. Because we presume to model natural languages as some sort of infinite languages, something else must be going on. There must be some restrictions on the possible forms of natural language that permit learnability in some sense. Stabler says that to address this question, we need a proposal about how human learners generalize from finite data. There is as yet no complete answer to this problem, and indeed very little research seems to be currently motivated by such questions.

While I do not generally use this forum to highlight my own published work, in this case I believe that my 2010 paper in the Journal of Logic, Language and Information (together with an erratum published this year) does address Stabler's question directly. The title of my paper is Grammar Induction by Unification of Type-Logical Lexicons, and therein the basic proposal is given. Human learners are proposed to generalize from finite data by unification of the sets of syntactic categories that are discovered by an initial semantic bootstrapping procedure. The bootstrapping procedure extracts basic category information from semantically annotated sentence structures (this is highly enriched data, to be sure, but I argue for the plausibility of that in general terms). The basic system of categories is then unified by a two-step process that takes into account the distribution of the words (usage patterns, expressed structurally), and is able to generalize to "recursively redundant extensions" of the learning data. This is then a specific proposal of the sort invited by Stabler. The resulting learnable class of languages is highly restricted, including only those that are in some sense closed under recursively redundant extensions. This is in accord with general thinking about human languages, in that it is normally the case that a recognized recursive procedure (such as the appending of prepositional phrases to expand noun phrases, in rough terms) can always be applied indefinitely to yield grammatical sentences of increasing length.

I hope in the future to highlight my findings in a more general journal like Cognitive Science. It is helpful that Stabler conveniently provided the leading question to my purported answer.

Bare Grammar

I was recently reminded (thanks to the comment from Emilio on my previous post) of some great work that was done by my former professors Ed Keenan and Ed Stabler, that I first learned about when I was a PhD student in the 1990s. The key publication for reference is their book Bare Grammar, published by CSLI in 2003. It is actually rather embarrassing that I had largely forgotten about this work while preoccupied with my own efforts in learning theory the past several years, since I should have used some of their ideas to further my own.

Bare Grammar is a largely atheoretical framework for describing syntactic structure. I won't present any details here while trying to highlight the major points. Keenan and Stabler begin by pointing out that human languages always have lexicons in which most elements are grouped into classes (like parts of speech) whose members are in some sense intersubstitutable in the "same" positions within the "same" structures. A simple example is afforded by the English sentences:

Trevor laughed.

Nigel cried.

It is observed that Trevor can substitute for Nigel (and vice versa) without "changing structure," yielding equally grammatical sentences. The same can be said of the verbs laughed and cried. This means that the two sentences "have the same structure," in that they are each obtainable from the other by a sequence of "structure-preserving transformations." Hmm, this is starting to remind me of my previous post where I ruminated about gauge theory, as was suggested by the comment there.

Being mathematical linguists, Keenan and Stabler formalize all this. A structure-preserving map is defined as an automorphism of the grammar. An automorphism h can have fixed points x, such that h(x) = x. The syntactic invariants of the grammar are fixed points of every automorphism. In the lexicon, these are identified with the function words---words that cannot be substituted without changing structure. By using some fancier mathematical operations (power lifting and product lifting), it is shown how certain properties of higher order can also be fixed points, which correspond to such things like invariant properties of expressions, and invariant relations and functions. Much of the book is engaged in evaluating potential invariants of these kinds.

A major point is that natural languages all have such invariants---an interesting fact, to be sure, which is not at all necessary from the basic considerations of formal language theory. It would be easy to devise a formal language that didn't have anything like a function word, yet natural languages all have such things.

I hope to spend some more quality time with this book in the near future, and may have some more posts about it. In the meantime, I recommend it to anyone interested in a novel theoretical approach to a range of interesting linguistic facts that are not seriously dealt with elsewhere.