Artificial Intelligence, Natural Language Understanding, and
Knowledge Representation and Reasoning
James Allen, George Ferguson, Daniel Gildea, Henry Kautz, Lenhart Schubert
Topics | Faculty
The AI/NL/KR group at Rochester is attempting to (a) understand
intelligent thought, planning, and communication, and (b) build
computer systems that think, behave, and communicate intelligently.
Our research along these lines spans the history of Artificial
Intelligence, from core issues in knowledge representation, planning,
and search, through natural language understanding and uncertain
inference, to cutting-edge research in areas such as speech
recognition, multi-modal interaction, data mining, machine learning,
and assistive technologies.
We are not really a single group with a unified purpose. Rather, we
are pursuing a wide variety of problems individually, as a group, with
other members of the Computer Science Department, and in
collaborations with other departments at Rochester and beyond. We have
strong connections to the
Brain and Cognitive Sciences
Departments, as well as an active role in the University's
Center for Language Sciences.
We see intelligence as
fundamentally multi-faceted, and therefore pursue connections to
related research as often as we can.
Some of the current research topics being pursued within the AL/NL/KR
- Intelligent Collaborative Agents: We are combining natural
language understanding and dialogue management with AI planning and
scheduling technology to create intelligent planning assistants. The
goal is to make the system's interaction with the user as intuitive as
possible by treating it as a dialogue between the participants, each
of whom bring different skills and objectives to the table. TRIPS, The
Rochester Interactive Planning System, is an end-to-end prototype of
such a system in a logistics domain.
- Spoken Language Systems: We are studying the use of speech
as a primary modality for human-computer interaction. One of the
foci of this work has been the need for robustness in the light of
phenomena such as speech recognition errors, casual speech, speech
repairs, interruptions, and so on, that do not occur in written
- Machine Translation: Current work focuses on adding syntactic
knowledge to statistical systems for translating text from one language
to another, modeling systematic differences in the grammar of the two languages.
- Language Modelling:
We are using probabilistic methods for modelling natural languages, in
particular to support automatic speech recognition and understanding.
We are working on models that attempt to exploit the deeper structure
of language rather than simply relying on n-gram models of context.
Also, we are interested in language model adaptation to new domains,
and optimizing the use of training data.
- Multi-modal Interaction: In addition to speech, we are
studying the use of multiple modalities to improve the effectiveness
of human-computer interaction. This work includes such things as
coordinated graphical and spoken display, use of multiple display
surfaces, gestural and visual input, and dynamic use of different
modalities as the user's environment changes (for example, if they
move around). We are also extending the discourse framework from
two-party to multi-party interactions.
- Expressive, Language-like Logics: We wish to capture the
content of ordinary language and commonsense reasoning as directly as
possible. The most recent such logic is called Episodic Logic, and is
implemented in the EPILOG system, which has been used to make complex
inferences about fairy tale fragments, aircraft maintenance reports,
and other domains.
- Natural Language Semantics: For events/situations,
tense/aspect, reference, affixes, mass terms, generic sentences,
belief, questions, vagueness, etc. Our recent and current work is
concerned not only with formal theories of these phenomena, but also
with ways of extracting semantic information automatically from
large text corpora.
- Computational Models of Belief: We are
developing a formal computational model of belief, one that meets
traditional philosophical requirements and can also serve in practical
reasoning about beliefs by ``simulative inference,'' i.e., inference about
another agent's beliefs by introspection about the conclusions one
would draw if one held the other agent's beliefs.
- Efficient, specialized inference techniques: For taxonomies,
part-structure, temporal relations, and other classes of relations
that pervade commonsense knowledge and are handled effortlessly
- Natural Language Parsing: The emphasis is on human-like,
error-tolerant strategies for parsing and disambiguation, and for
mapping syntactic structure to a representation of the underlying
meaning (allowing for context).
- Reasoning About Plans and Actions: This work supports both
language understanding (e.g., conversation planning and inferring the
goals and plans of story characters) and domain reasoning (e.g.,
formulating transportation plans in the TRAINS/TRIPS domains). We are
pursuing several approaches to this problem. First, we are developing
planning formalisms and algorithms based on Interval Temporal Logic to
represent and reason about complex plans in realistic domains. Second,
we are pursuing the use of ``Explanation Closure'' as an intuitive and
effective solution to the Frame Problem.
Finally, we are also developing ways of speeding up recent domain-independent
planning algorithms (based on regression, plan graphs, satisfiability
testing, etc.), for instance by better search control or by automatic
inference of state constraints that can be used to limit search.
- Task-Oriented Discourse:
An emphasis in this work is, first, the representation and use of the
context of the dialogue to solve problems in semantic interpretations
and, second, the recognition of the intentions underlying the
speakers' utterances. Work in this area has included the development
of the first computational model of speech acts, the development of a
multi-level plan-based analysis involving discourse-level plans as
well as domain-level plans, and the development of several different
discourse-plan recognition algorithms that can support complex
reasoning about plans and actions.
- Context Management for Dialogue Systems:
We are developing a model of discourse context management for use by
dialogue systems. A key issue here is keeping track of objects that
have been mentioned in the dialogue and what has been said about them.
We are investigating how to adapt existing knowledge-poor models, such
as centering, to dialogue, as well as developing our own
knowledge-rich model. This research is being used to make the TRIPS
system understand a wider range of referential expressions from the
user and to make its own utterances more natural and coherent.
- Pronominal Reference Corpus:
This is a data collection effort to develop a corpus of discourses in
which the antecedents of pronouns have been annotated. Despite the
crucial role of pronominalization in language, there is very little
such data within the scientific community. The data is being drawn
from task-oriented dialogues, radio news stories, and fictional
stories and annotated by members of the group. The results will be
used for evaluating pronoun resolution algorithms and as training data
for new statistical or learning-based algorithms.
- Philosophical Foundations of Uncertain Inference:
Many of the same questions (and
many of the same answers) are raised (and given) in philosophy and
artificial intelligence. To provide philosophically satisfying answers
is also to provide answers that are also practically useful, and that
can enlighten scientific disputes about evidential support. This
research has lately moved in two directions: toward the relation
between inductive or statistical or probabilistic support, and the
tentative support provided by nonmonotonic logics; and, since there is
tension between statistical support and deductive closure, toward the
paraconsistent logics that allow sensible inferences from
- Uncertain Inference Using Reference Classes:
This line of research aims
at extending evidential probability in a number of directions. In
cases where the selection principles are inadequate, we need to revise
the principles and/or provide new ones that are more suited to the
task of identifying the most appropriate reference class, thus
enabling us to establish a well founded theory of probability based on
statistical knowledge. We also seek to identify restricted parts of
the theory that admit tractable computation yet are expressive enough
for use in practical applications.
- Prototype Framework for Various Formalisms:
We are working on constructing a prototype framework in which we can
characterize both the generic uncertain reasoning process and a wide
spectrum of specific formalisms. This provides a common platform on
which we can translate the various pieces of information, originally
encoded using different formalisms, into a knowledge base with a
standard syntax and semantics. This step ensures that different
portions of the combined knowledge base are treated uniformly, and
that they are allowed to interact in a well understood manner. We are
then able to evaluate the behaviors and results of the combined system
against a clearly defined semantics.
- Intelligent Datamining:
A relatively recent area of research involves mining large datasets for
patterns of information and reasoning about the causes and effects of
the discovered patterns. For example, we are looking at using fast
simulators to provide large numbers of execution traces of a plan,
from which likely errors and their causes can be extracted and used to
improve the plan before it is executed. A central issue here is
dealing with the fact that large databases are practically always
inconsistent. Work on intelligent datamining is being undertaken by a
group involving Systems and Theory faculty as well as members of the
Current faculty associated with the AI/NL/KR group are:
- James Allen:
James' research interests span a range of issues covering natural
language understanding, discourse, knowledge representation,
common-sense reasoning, and planning. He has joint appointments in the
Brain and Cognitive Sciences and Linguistics departments, holds the
Dessauer Chair in Computer Science, and is a Fellow of the AAAI. He is
the author of the definitive graduate-level textbook Natural
Language Understanding, 2nd ed. (Benjamin Cummings, 1994).
- George Ferguson:
George is a Research Scientist in the department. His
interests are in the development and application of AI, NL, and KR
techniques in the construction of intelligent, collaborative computer
systems. This includes applying or extending existing theories, such
as for temporal reasoning or planning, to new problems, developing and
implementing new theories where traditional ones break down, and
creating frameworks in which such ``systems of systems'' can come
together to support intelligent behaviour. George is the principal
architect of TRIPS, The Rochester Interactive Planning System, and is
the founding chair of the Intelligent Systems Demonstrations Program
- Daniel Gildea:
Dan is interested in statistical approaches to natural language processing,
in particular language understanding and machine translation. He has
also worked on language and pronunciation modeling for speech recognition
and computational approaches to phonology.
- Henry Kautz:
Henry's research is concerned with fundamental questions of
efficiency and scalability of knowledge representation and reasoning
systems. Examples include using new randomized algorithms to solve
logical representations of planning problems, and using
machine learning techniques to optimize the performance of solvers
on distributions of problem instances. Other work includes
investigating the formal complexity of clause-learning system, and
exploring the connections between work in AI on logic and search and
work in verification. A major new initiative called Assisted
Cognition aims to create computer systems to help people suffering
from cognitive disorders, such as the effects of Alzheimer's disease.
This involves fundamental and applied research
ranging over topics such probabilistic reasoning, plan recognition,
ubiquitous computing, data fusion, user interfaces, and cognitive
- Lenhart Schubert:
Len's research interests center around language, knowledge
representation, inference and planning. These interests are tied
together by the general goal of developing agents with common sense
and the ability to converse and acquire knowledge through language.
Len is a Professor of Computer Science, a former member of the editorial
boards of the Journal of AI Research and Computational
Intelligence, past chair of several AI conferences, and a Fellow of
Recent Graduates of the AI/NL/KR Group
Recent graduates of the AI/NL/KR group are:
- Hao Zhang,
Handling Complexity of Synchronous Grammars, 2008.
- Ellen Campana,
Natural versus Standardized Approaches to Spoken System
Design: A Comparison Using the Dual-Task Paradigm, 2007.
- Proshanto Mukherji,
Discovering Laws as Anomalies in Logical Worlds, 2007.
- Nathan J. Blaylock,
Towards Tractable Agent-Based Dialogue, 2005.
- Joel R. Tetreault,
Empirical Evaluations of Pronoun Resolution, 2005.
- David D. Ahn,
The Role of Situations and Presuppositions in Restricting
Adverbial Quantification, 2004.
- Myroslava Dzikovska
A Practical Semantic Representation for Natural Language
- Lucian Galescu,
Hierarchical Statistical Language Models for Unlimited
- Teresa Zollo,
Detecting and Correcting Speech Recognition Errors during
Natural Language Understanding, 2003.
- Donna K. Byron,
Resolving Pronominal Reference to Abstract Entities, 2002.
- Gregory R. Wheeler (Joint Philosophy and CS),
Non-Monotonicity and Paraconsistency, 2002.
- Amanda J. Stent,
Dialogue Systems as Conversational Partners: Applying
Conversation Acts Theory to Natural Language Generation for
Task-Oriented Mixed-Initiative Spoken Dialogue, 2001.
- Mark G. Core,
Dialog Parsing: From Speech Repairs to Speech Acts, 2000.
- Aaron N. Kaplan,
A Computational Model of Belief, 2000.
- Eric K. Ringger,
Correcting Speech Recognition Errors, 2000.
- Amon B. Seagull,
Well-Foundedness and Reliability in Statistical Natural
Language Parsing, 2000.
- Choh Man Teng,
Non-Monotonic Inference: Characterization and Combination, 1998.
- Bulent Murtezaoglu,
Uncertain Inference and Learning with Reference Classes, 1998.
- Louis J. Hoebel,
A Practical Temporal Reasoning System, 1998, now at GE Research.
- Peter A. Heeman,
Speech Repairs, Intonational Boundaries and Discourse
Markers: Modeling Speakers' Utterances in Spoken Dialog,
1997, now at Oregon Graduate Institute.
- Marc N. Light,
Morphological Cues for Lexical Semantics, 1996, now at MITRE Corp.
- David R. Traum,
A Computational Theory of Grounding in Natural Language
Conversation, 1995, now at University of Maryland.
- George M. Ferguson,
Knowledge Representation and Reasoning for
Mixed-Initiative Planning, 1995, now at University of Rochester.
- Massimo Poesio,
Discourse Interpretation and the Scope of Operators,
1994, now at University of Edinburgh.