Niyogi: Informational Complexity of Learning

This is the first in a series of posts highlighting the contents of Partha Niyogi's 1998 monograph The Informational Complexity of Learning, and using this as a jumping-off point for some discussion of my own.

I'll begin with some brief notions from Chapter 2. In this chapter, Niyogi emphasizes some very important points of learning theory, while developing a new analysis of learnability by neural nets. In a fairly standard mathematical model of learning championed by Vapnik and others, we view a learner as attempting to formulate the best hypothesis possible within its hypothesis class, which approximates the target concept within the concept class.

Let me just stop right there, in order to discuss the ramifications of this for language learning. Though this framework does not originate with Niyogi, in my view he is one of a few linguists who understood it. I believe that this setup alone may be used to all but prove the necessity of some kind of "Universal Grammar" which is commonly advocated. Universal Grammar should be seen as the limitations on "possible human languages" that in effect makes the hypothesis class of languages used by the human learner sufficiently small. Numerous negative results have shown time and again that overly large classes of languages are not strictly learnable, essentially because they are too big. To me, this speaks loudly against any language learning model which invokes a "general cognitive learning" idea, as if humans could leverage their general abilities to successfully learn whatever kind of language is thrown at them. We already know from experience that humans can only learn human languages. Creolization from simpler fabricated lingua francas and pidgins is easily understood in this way. In that scenario, the target concept is outside the hypothesis class, and the learners settle on the best hypothesis in the hypothesis class, which is in fact a human language.

I presume that Universal Grammar is an innate set of things delineating the required properties of a human language, and which thereby also delineates the hypothesis class which is used by human learners. Beyond that, I do not know what it is exactly. I will continue to use Partha's book to further this discussion in later posts.

Partha Niyogi: a reminiscence

Our small field was dealt a body blow by the death of Partha Niyogi last month. An official obituary can be found at the University of Chicago news site. In this post I will not repeat this information, but will just offer a personal perspective on Partha from my interactions with him while we were colleagues.

I worked as a Visiting Assistant Professor in the Linguistics and Computer Science departments at the University of Chicago for four academic years, spanning from 2000-2004. During the first part of this period, Partha was an Assistant Professor, but he was awarded tenure sometime before I departed. Partha's research breadth was something I always admired about him, especially since I aspired to contribute research in more or less similar areas encompassing mathematical linguistics, learning theory, and speech processing. We had a number of conversations over the years mostly about my research rather than his. He was always interested to talk with other people about their work. I also interacted with Partha frequently in the ways that colleagues do, and I got to learn how he dealt with research through his reactions to various talks given by the many visitors who passed through.

One thing that always struck me about Partha was his incredible mathematical knowledge. I was still really a beginner compared to him, and even now I can only say that I am a little more advanced at math than I was then. His skills and knowledge in math are still a model which I will always aspire to, and probably never achieve. In spite of the obvious difference between our skill levels, he was never condescending when discussing mathematical subjects with me. He just spoke at his level and kind of assumed that I would do my homework if I didn't understand right away.

The work of Partha's with which I am the most familiar is his first book The Informational Complexity of Learning, from which I learned and am still learning many things about Kolmogorov complexity, neural nets, and other topics. It is still a timely piece in my view, and in the future I hope to offer some posts highlighting many parts of this book. I remember when I told him I had bought his book, he was kind of like "what did you do that for? It's quite expensive." He was never proud or arrogant.

I've seen a number of posts and reminiscences around since his death which paint a picture of Partha as a kind of renegade, always willing to go for the brass ring in his research, to go beyond what most people thought was doable or even sane. I would venture to offer some counterweight to this view, however. In my experience, Partha was, while very skilled at making real progress beyond the incremental advance, nevertheless quite conservative scientifically. He regarded much of my best work in speech processing as kind of "crackpot," in fact. He openly despised my work on the reassigned spectrogram, which I was just starting to promote as the next great thing for acoustic phonetics and speech science. I once asked him if he would consider trying reassigned spectrograms for his speech recognition research, and he told me flat out that he didn't believe the representation was meaningful, and that he "wouldn't touch it with a ten-foot pole," an expression that kind of surprised me from a non-native English speaker. I guess every time I do some more research on reassigned spectrograms, I'm still trying to prove myself to Partha. It's sad now that he won't be around to "eat his words," because I'm convinced the project finally worked out to something that would have satisfied him. I know that, confronted with a better understanding and some solid conclusions, he would have happily dined on his former naysaying. I'm very sad to have lost an old adversary and sparring partner.