On the Origin of Languages

Re-reading the intriguing book by Merritt Ruhlen: On the Origin of Languages: Studies in Linguistic Taxonomy. The basic premise is that contrary to widespread belief, the tools of comparative linguistics can be applied beyond the Indo-European family to reconstruct the roots of a world proto-language. Though it sounds far-fetched at first, Ruhlen makes a compelling case for his methodolgy, and gives some world-etymologies that I can't resist from reproducing below. It gives me particular satisfaction to see these ancient roots manifest themselves in the languages I read, write and speak: Russian, English, Hebrew, Latin. The asterisk indicates an unattested form.

KAMA 'hold (in the hand)'. Ruhlen gives the Proto-Afro-Asiatic root *km, from which we get the Arabic kamasa 'seize, grasp'. Could the Hebrew חמש 'five' be related (as in, the five fingers of the hand)? The Indo-European cognate is *gemo, which appears in Russian as жму 'I press'.

My favorite: MANA 'to stay (in a place)'. Proto-Afro-Asiatic: *mn, which manifests in Hebrew as אמן. This root means 'true, enduring', and is borrowed by many Indo-European languages as amen. Of course, the I-E family has this root occurring natively as well -- as the Proto-IE *men. The Latin manere will be more familiar to English speakers as remain.

Another favorite: MENA 'to think (about)'. Hebrew: מנה 'to count'; English: mind, mental; Russian: мнить.

I'll close with the colorful PUTI 'vulva'. Hebrew speakers will immediately recognize this as פות, via the Proto-Afro-Asiatic *pwt 'hole, anus, vulva'. Speakers of Romance languages might be pleased to learn that when they curse a woman as puta(-na), they're invoking an ancient root, dating back tens of thousands of years!

A final note, and an appeal to my more professional linguist readers. Ruhlen writes: "the Indo-European family has been established beyond doubt," and this has been my belief ever since I began to amateurishly dabble in comparative linguistics. However, I recently had an argument with a computational linguist/computer scientist/mathematician who claims that the IE-family is "merely" a hypothesis, and a rather controversial one at that. Does anyone know of a reputable linguist who doubts the common origin of the so-called Indo-European languages, and questions the basic structure of reconstructed Proto-IE?

Update: More world etymologies are available online.

Update II: To be fair and balanced, I'm linking to a harsh critique of Ruhlen and his methods, with a hat tip to Cosma.

Shameless self-promotion

Some good news on the publications front. My paper with Kavita Ramanan has been accepted (with minor revisions) to the Annals of Probability. If you just want the main idea (actually, a much simpler proof of a more general form of the main result), this is the paper to read.

Another recent acceptance is my Universal Regular kernel extended abstract, to appear in MLG'07. It's a short 4-page writeup, and if you can resolve the issue of computing K_n, I guarantee you fame and fortune.

I'm hanging out at the FCRC conference (Mehryar is presenting our Rational Kernels paper with Corinna at COLT). So if you're around, find me and say hi, and most definitely come to Mehryar's talk on Thurs. at 2:40. I'll try and blog about the conference a bit later, but we always have Scott to count on.

Thesis online

After abusing our department coordinator's patience beyond all common decency, I've stopped making revisions on my thesis. I know, I know -- a week from now I'll casually glance at it and see something I'll want to change. But major OCD notwithstanding, enough is enough. I'm putting it online for public perusal; don't all rush in to download it all at once now. As always, questions and comments are more than welcome.

Idea for Sci-Fi story

How can you tell if the reality you experience is "real" or is just a giant computer simulation? Philosophers realized long ago that of course you cannot; Hofstadter and Deutsch make the a posteriori obvious point that the question itself is meaningless. Any physical process may be viewed as a computation and therefore a "simulation".

But what if we allow the possibility of simulator malfunctions? Address errors, memory leaks, unknown-error-must-shut-down type things. What would it feel like to be in a simulation that suddenly displayed such artifacts? Parts of your universe are working fine as before, but you might locally observe very strange discontinuities and irregularities.

There are sophisticated theories of spacetime defects that I lack the mathematical apparatus to understand (any quantum gravitists want to help out?). Might any of these defects be explicable as computer bugs in the universal simulator? Could one at least get a decent sci-fi story out of this? I'm sure this vein has been already explored -- can anyone point me to a good story? Anyone up the the task of writing one?

Misc. update + possible flamewar

Posting has been and will be sparse over the next month or so as I transition to my new location (starting a postdoc at Weizmann).

What I'm working on: a tantalizing decoupling conjecture and a concentration bound for adaptive Markov processes (with Anthony Brockwell). Ask me about these.

Thoughts on leaving Pittsburgh: it's a shame I only met some of the people so late. Seems like in my last months at CMU I made a whole slew of new friends and colleagues -- anywhere from fellow mountain bikers (and I've got fresh scars to prove that) to fellow mathematicians, philosophers, and shmoozers. Where have you guys been for the past 5 years? A better question is where have I been: stuck in my office. I'm not sure there's necessarily a moral here (if I'd done more shmoozing and less work I'd probably still be stuck in that office) -- but it's always sad to see what one has been missing out on.

And now for the flamewar: Cosma and I were discussing The Bell Curve over a beer (or two... or three...). Now smearing Herrnstein and Murray's book as pseudo-scientific racist drivel is a favorite past-time of the Left (and not having read it isn't much of a deterrent). Cosma points out that conservatives can also pile on. In 2005, Murray wrote a lengthy and copiously documented rebuttal (well, more like a synopsis of the debate that their book had been generating for 11 years). Two must-read books for all equality-across-all-groups ideologues are Steven Pinker's The Blank Slate and Nicholas Wade's Before the Dawn.

There is no doubt that free scientific inquiry is severely curtailed on certain topics. Just try getting a grant to do climate research if you dare question anthropogenic global warming. The Larry Summers affair illustrates that even "mild, speculative, off-the-record remarks about innate differences between men and women" can get a university president fired. Yet differences between ethnic groups and the sexes do exist as a matter of verifiable empirical fact (please take the time to read Pinker and Wade before calling me names).

Once again, I'm only too glad that the "controversy" generated by math is of the easily dismissed crackpot type, not the type that costs one his career.

Serious attempts at P?=NP ?

Here's a question I'm hoping my readers will help out with. It seems that every week someone comes out with a "proof" that P=NP, and only slightly less frequently that P!=NP. Most of these are written by amateurs who don't even understand the problem.

Have there been any attemps by reputable mathematicians to resolve the issue? Lindenmann had produced several flawed proofs of Fermat's last theorem a century before Wiles got it right, and he was certainly no amateur. Does anyone know of any credible proof attempts, with subtle, nontrivial mistakes?

Student projects

The semester is over, the grades should be in by now, and most of my students from FLAC are graduating. One of the components of the course was a research project, during which the instructors mentor the students on an individual basis. This has been quite a rewarding experience, since I managed to get four of my students interested in some deep and fascinating problems in automata theory, with connections to my own work. I note that all the students I mentored did a fine job and a couple of them taught me new things. But in this post, I'd like to showcase the projects with the strongest connection to automata theory and machine learning.

Jeremiah Blocki is that brave soul who took on the notorious problem #3. First, here is that long-overdue writeup where I define the universal regular kernel. In his paper, Jeremiah gives closed-form expressions for K_n(x,y) for short x and y, as well as proving some simple lower bounds on the complexity of K_n.

Vinay Chaudhary became interested in my work with Corinna Cortes and Mehryar Mohri on learning piecewise testable languages with the subsequence kernel. Aside from understanding our somewhat involved word-algebraic proof of linear separability, Vinay had to learn a whole bunch of subtle machine-learning notions, essentially on his own. Having gained a command of margins, support vectors, embeddings and kernels, he embarked on an investigation of the empirical margin of piecewise testable languages. Vinay produced a excellent piece of research, with some tantalizing leads.

Matthew Danish considered a problem that I'd attempted many moons ago and put aside -- namely, one of characterizing the languages that one obtains by taking finite Boolean combinations of modular n-grams. (A modular n-gram is the set of all strings in which a given contiguous substring occurs k mod n times.) Matt also had to master abstruse concepts such as syntactic monoids and morphisms, and produced a solid paper.

Jonah Sherman decided to aim high and attempt the star-height problem. I remember how mesmerised I was by this problem when I first encountered it some four years ago. When Jonah had asked me about its importance, I replied that if we can't answer such natural questions about regular languages then we are in dire need of better tools! That was good enough for him, and he dove into some rather dense semigroup theory, even rediscovering the rather nontrivial result that all languages recognized by finite commutative monoids have star height of at most one. Impressive work done by a college junior, check it out!