2003 Recipient: Aravind Joshi

2003 Recipient: Aravind Joshi

Joshi is the Henry K. Salvatore Professor of Computer and Cognitive Science at the University of Pennsylvania. He has previously received considerable recognition for his accomplishments. Three of his honors are particularly worthy of note. In 1997, he was the recipient of the highest honor in the field of artificial intelligence, the Research Excellence Award of the International Joint Conference of Artificial Intelligence (IJCAI), a distinction held by only eight other outstanding computer scientists. In 1999, he was appointed to the National Academy of Engineering, the only researcher in Natural Language Processing to have ever recieved this distinction. And just this year, Joshi was chosen to be the first recipient of the Lifetime Achievement Award given by the Association for Computational Linguistics.

Joshi has contributed a number of key ideas to the formal science of language. Perhaps the best known of these is Tree Adjoining Grammar. His work on TAG has played an important role in both natural language processing and in theoretical linguistics. In both disciplines, it stands as a monument to the value of principled mathematical thinking. Two key ideas underlying TAG are, first, that the statement of local syntactic and semantic dependencies can be factored apart from recursion and, second, that a modest increase in power beyond context-free grammar is sufficient to characterize natural language syntax. The TAG adjoining operation, as defined by Joshi, achieves both of these results in a strikingly elegant way, providing a powerful tool for linguistic description that at the same time yields grammars guaranteed to be computationally tractable. A large body of mathematics, computational, empirical linguistic, and psycholinguisitc work by Joshi and numerous others has been developing the consequences of Joshi’s original insight for more than a quarter of century.

Joshi’s work in mathematical linguistics over the years has had an extraordinary impact on linguistic theory, beyond the impact of TAGs themselves. To give just two examples here: (a) Joshi’s generalization of an earlier result of Stan Peters’ to show that arbitrary booleans of context sensitive filters on context free grammars still result in context free languages led directly to the development of Gerald Gazdar’s GPSG framework (actually first developed, we believe, while Gazdar was visiting Penn). (b) the generalization of TAGs to an entire class of languages (the so-called “Mildly Context Sensitive Languages”) provided a natural way to relate a number of superficially distinct linguistic theories from Combinatory Categorial Grammar to Head Grammar and HPSG to Government-Binding Theory and Minimalism.

Another key contribution of Joshi’s to the science of language (along with Weinstein and Grosz) is Centering Theory, a computationally tractable model of attention during discourse. Centering Theory has attracted a wide following among linguists and computer scientists working on formal models of discourse. Its leading idea is that referring expressions can be ranked on the basis of various structural properties and that these rankings can predict the likely coreferents of anaphoric expressions in discourse. These predictions can be used in the automatic processing of discourse but they also have a fine-grained structure, so that the theory can be used to show how different choices of coreference produce different pragmatic effects. The theory is attractive in part because it provides a framework for capturing not only the relationship of a current utterance to previous utterances but also with expectations regarding utterances yet to come. Perhaps most strikingly, it has yielded the first successful objective definition of the notion of “topic” or “theme”, a concept long thought important by linguists but notoriously difficult to nail down. Centering Theory has been found relevant for modeling a number of properties related to discourse coherence, including anaphora resolution, the distribution of various types of pronouns, the felicity condidtions of marked syntactic forms, and aspects of prosody.

Aside from his scientific work, Joshi has played a key organizational role in fostering the development of the new discipline of cognitive science. Over the past two decades and more, the University of Pennsylvania has developed a thriving program in cognitive science, largely due to the outstanding vision and tireless leadership that Joshi contributed to the effort. From his graduate student days onward, he was concerned with the interface between computation and cognition, working with early pioneers like Zellig Harris and Saul Gorn. By the late 1970’s Joshi had established an interdisciplinary faculty seminar that included psychologists and linguists, as well as computer scientists. This seminar was one of the early recipients of support from the Sloan Foundation’s cognitive science initiative. Later he led the effort at Penn to win an NSF Science and Technology Center for cognitive science and was founding co-director (with Lila Gleitman) of the Institute for Cognitive Science at Penn, a post which he held with great success until last year. His approach to these efforts was always to foster the broadest possible participation by researchers in different domains and with different orientations and always to emphasize the importance of educating young researchers and of supporting them morally and materially. IRCS is one of a small number of organizations at Penn that cross school lines and establishing it required great persistence and diplomatic skill. These were supplied by Joshi, whose commitment to a broad view of the field had convinced him that the effort was necessary.

Joshi’s writing has been both prolific and of exceptionally high quality. In the introduction of Gazdar et al.’s bibliography “Natural Language Processing in the 1980s,” they note that “The most prolific author represented, by quite a large margin, is Aravind Joshi.” Several of his most important works are listed below.

Joshi continues to be remarkably creative and prolific. Recently, Joshi has turned his attention to the application of ideas from mathematical linguistics to the analysis of DNA and the human genome. This follows an observation some years ago (by others) that while CFGs provide a formal basis for the mathematical analysis of the DNA that generates hairpin structures, the pseudo-knot structures of molecules like tRNA are generated by a non-context free DNA structure that can be nicely modelled by TAG.

Selected Bibliography

Joshi, A. K., Levy, L., and Takahashi, M. (1975). Tree Adjunct Grammars. Journal of Computer and System Sciences.

Joshi, A. K. (1985). How much context-sensitivity is necessary for assiging structural descriptions: Tree adjoining grammars. Natural Language Parsing, (ed. D. Dowty, L. Karttunen, and A. Zwicky), Cambridge University Press.

Joshi, A. K. (1990). Processing crossed and nested dependencies: an automaton perspective on the psycholinguistic results. Language and Cognitive Processses 5(1), 1-27.

Schabes, Y. and Joshi, A. (1991). Parsing with lexicalized tree adjoining grammar. In Tomita, Ed., Current Issues in Parsing Technologies. Kluwer, Boston.

Joshi, A. and Bangalore, S. (1994). Disambiguation of Super Parts of Speech (or Supertags): Almost Parsing. COLING 94.

Joshi, A., Becker, T., and Rambow, O. (1994). Complexity of Scrambling: a new twist to the competence/performance distinction. Tree-Adjoining Grammars: Formalisms, Linguisitc Analysis and Processing) (eds. A. Abeille and O. Rambow), CSLI Publications, Stanford University, pp. 167-182.

Grosz, B., Joshi, A. K., and S. Weinstein. (1995). Centering: A Frmework for modeling local coherence of discourse. Computational Linguistics.

Joshi, A. and Schabes, Y. (1996). Tree Adjoining Grammars. In G. Rosenberg and A. Salomaa, Eds., Handbook of Formal Languages.

Webber, B., Knott, A., Stone, M. and Joshi, A. (1999). Discourse relations: A structural and presuppositional account using lexicalised TAG. ACL 36.

Bangalore, S. and Joshi, A. (1999) Supertagging: an Approach to Almost Parsing. Computational Linguistics.