Abstracts of the ISI AI Seminar Series 98

Abstracts of the ISI AI Seminar Series in 1999

Manuela Veloso - January 25, 1999

Richard Benjamins - February 10, 1999

Victor Lesser - March 3, 1999

Nick Jennings - March 26, 1999

Mike Pazzani - April 2, 1999

Neal Leash - April 9, 1999

Peter Stone - April 30, 1999

Yan Jin - May 21, 1999

Patrick Hanks - May 26, 1999

Michael Young - June 3, 1999

Susan Craw - July 2, 1999

Kevin Knight and Yaser Al-Onaizan - September 9, 1999

Usama Fayad - October 22, 1999

Milind Tambe - November 5, 1999

Dennis Kibler - November 19, 1999

Adnan Darwiche - December 3, 1999

Ellen Rilloff - December 10, 1999

Monday, January 25, 1999

Bounding the Suboptimality of Reusing Subproblems

Manuela Veloso
(joint work with Michael Bowling)

CMU

I have always been interested in the problem of reusing solution plans to simpler problems to solve more complex ones. It is a well recognized difficult and open question to understand the trade-offs in solution quality of this reuse process. We have been studying this problem within the context of action selection in a non-deterministic environment. Markov decision processes (MDPs) provide a framework for representing this action selection problem, and there are a number of algorithms that learn optimal policies within this formulation. This framework has also been used to study state space abstraction, problem decomposition, and policy reuse. These techniques sacrifice optimality of their solution for improved learning speed. In this talk, we examine the suboptimality of reusing policies that are solutions to subproblems. This is done within a restricted class of MDPs, namely those where non-zero reward is received only upon reaching a goal state. We introduce the definition of a subproblem within this class and provide motivation for how reuse of subproblem solutions can speed up learning. The contribution of this work is the derivation of a tight bound on the loss in optimality from this reuse. We examine a bound that is based on Bellman error, which applies to all MDPs, but does not provide us with a tight bound. We contribute our own theoretical result that gives an empirically tight bound on this suboptimality.

Wednesday, February 10, 1999

Putting Intelligence on and in the Web

Richard Benjamins
University of Amsterdam

Many researchers in the knowledge-system area are relating their work to the Web. Two often seen examples of this are (1) to use the Web as a test domain to try out knowledge technology, and (2) to use the Web to make knowledge technology more widely available.

In this talk, examples will be given of both approaches. The (KA)2 initiative is concerned with "intelligent" retrieval from the Web, while the IBROW project aims at using the Web to enable global reuse of knowledge-intensive components.

(KA)2

The Knowledge Annotation Initiative of the Knowledge Acquisition Community, (KA)2 is an initiative to develop an ontology that models the knowledge acquisition community (its researchers, topics, products, etc.). This ontology will form the basis to annotate WWW documents of the KA community in order to enable intelligent access to these documents. (KA)2 is an open joint-initiative where the participants are actively involved in (i) a distributive ontological engineering process to model the knowledge acquisition community (a domain ontology), and (ii) annotating web pages relevant for the KA community (the instances of the domain ontology). (KA)2 aims at intelligent knowledge retrieval from the Web and automatic derivation of ``new'' knowledge. In other words, it aims at knowledge-based reasoning on the Web, as opposed to information retrieval. Another objective of the initiative is to get better insight in distributive ontological engineering processes.

IBROW

The World-Wide Web is changing the nature of software development to a distributive plug&play process. This requires a new way of managing software by so-called intelligent software brokers. The aim of the European IBROW project is to develop an intelligent brokering service that enables third party knowledge-component reuse through the World-Wide Web. Suppliers provide libraries of knowledge components adhering to some standard, and customers can consult these libraries --through intelligent brokers-- to configure a knowledge system suited to their needs by selection and adaptation. IBROW integrates research on heterogeneous databases, interoperability and web technology with knowledge-system technology and ontologies. The aim is to develop a broker that can handle web requests for classes of knowledge system (e.g. diagnostic systems) by accessing libraries of reusable problem-solving methods on the Web, and selecting, adapting and configuring these methods in accordance with the domain at hand.

Wednesday, March 3, 1999

Evolution of Generic Partial Global Planning (GPGP)

Victor Lesser
University of Massachusetts, Amherst

The GPGP/TAEMS domain-independent coordination architecture for small agent groups was first detailed in an ICMAS95 paper. In this talk, we discuss the evolution of this framework over the last four years motivated by its use in a number of applications, including: information gathering and management, coordination of concurrent engineering activities, distributed situation assessment, and hospital scheduling. First, we review the basic architecture of GPGP and then present extensions to the TAEMS domain-independent representation of agent activities. We next describe new coordination mechanisms for use in resource sharing and contracting and the need for more complex coordination mechanisms. Finally, extensions to GPGP that permit the description and learning of situation-specific coordination strategies are detailed along with techniques for using GPGP in large agent organizations.

Friday, March 26, 1999

Agent-Based Computing: Promise and Perils

Nicholas Jennings
Dept. Electronic Engineering, Queen Mary & Westfield College,
University of London, London E1 4NS, UK.
n.r.jennings@qmw.ac.uk

Agent-based computing represents an exciting new synthesis both for Artificial Intelligence and, more generally, Computer Science. It has the potential to significantly improve the theory and the practice of modelling, designing, and implementing complex systems. Yet, to date, there has been little systematic analysis of what makes agents such an appealing and powerful conceptual model. Moreover, even less effort has been devoted to exploring the inherent disadvantages that stem from adopting an agent-oriented view. Here both sets of issues will be explored. The standpoint of this analysis will be the role of agent-based software in solving complex, real-world problems. In particular, it will be argued that the development of robust and scaleable software systems requires autonomous agents that can complete their objectives while situated in a dynamic and uncertain environment, that can engage in rich, high-level social interactions, and that can operate with flexible organisational structures.

Friday, April 2, 1999

Learning Comprehensible Predictive Models from Data

Mike Pazzani
UCI

Knowledge discovery in databases is a field whose goal is to turn data into knowledge. For example, by analyzing a database of credit card customers we can determine what types of customers are most likely to be profitable for the company. By "mining" databases of medical records, new cost-effective procedures for screening for diseases may be uncovered. Several decades of research in statistics, neural networks and artificial intelligence have identified a variety of approaches that produce accurate descriptive or predictive models. However, experts are unwilling to accept the results of these techniques when they don't make sense, are difficult to understand, or violate prior understanding. Here, we discuss factors that make learned knowledge acceptable to experts and discuss modifications to rule learning, linear regression and text classification algorithms that make the learned models more comprehensible.

Friday, April 8, 1999

Improving Big Plans

Neal Lesh

I'll describe joint work with Nat Martin and James Allen on improving large plans. I'll present the Improve algorithm which modifies a given plan so that it has a higher probability of achieving its goal. Improve simulates a plan repeatedly and then performs data mining on the simulation traces to pinpoint defects in the plan that most often lead to plan failure. Improve then applies qualitative reasoning and plan adaptation algorithms to modify the plan to correct these defects. We have tested Improve on plans containing over 250 steps in a island- evacuation domain. The original plans were produced by a domain-specific scheduling routine. In our experiments, the modified plans had, on average, a 15% higher probability of achieving their goals than the original plans.

Friday, April 30, 1999

TBD

Peter Stone
CMU

Friday, May 21, 1999

KICAD: A Knowledge Infrastructure for Collaborative and Agent-based Design

Yan Jin
The IMPACT Laboratory
Department of Aerospace and Mechanical Engineering, USC

Engineering design problems are inherently complex and involve many highly coupled sub-tasks that require multiple designers to work together collaboratively. Because of the limitation of current knowledge and technologies, collaborative design in practice is still highly experience-based. Our on-going research "building knowledge infrastructure for collaborative design" attempts to develop a theoretical framework to model collaborative design and an agent-based technology, called KICAD, to support design and collaboration. In KICAD, each designer has an intelligent agent associated. The agents actively work with their designers to enrich their "knowledge" about the tasks, and provide intelligent and timely support to their designers when needed. This talk will provide an overview of the KICAD research program and describes the current research achievements.

Dr. Yan Jin is Assistant Professor of Mechanical Engineering at University of Southern California and the Associate Director of the USC IMPACT Laboratory. He received his Ph.D. degree in Naval Engineering from the University of Tokyo in 1988. Since then, Dr. Jin has done research on agent-based systems, distributed problem solving, organization modeling, and collaborative engineering. Prior to joining USC faculty in the Fall of 1996, Dr. Jin worked as a senior research scientist at Stanford University for 5 years. His current research interests include design process modeling, agent-based collaborative engineering support, and computational organization modeling. Dr. Jin is a receipient of 1998 National Science Foundation CAREER Award.

Monday, May 26, 1999

Mapping Syntax onto Semantics: A Lexicographical Approach

Patrick Hanks
Oxford University Press

According to dictionaries, many words have more than one sense. But a human being reading or hearing a text is rarely troubled by any awareness of ambiguity, and insightful linguists from Fillmore onwards have been sceptical of "checklist theories of meaning".

In this talk I explore the notion that phraseology provides cues on which utterer and audience depend for activating meaning, without activating a checklist of word-by-word semantic choices. I assume that meanings are events rather than static abstract objects. Strictly speaking, therefore, what dictionaries show are meaning potentials not meanings. Dictionaries do a good job of identifying the meaning potentials of words, especially rare and unusual ones, but, with the exception of the Collins COBUILD project, they have made little attempt to show how meaning and use interact.

This may not matter for human users, but it can be a fatal flaw for computer applications. Typically, a computer does not know how to tell one sense of a word from another, and dictionaries do not provide this information. It is no comfort to tell the computer that, for a human being, the ambiguity does not arise in the first place.

I shall present a sample entry [for the lexical item SHAKE] from a robust phraseological dictionary designed to fill this gap. The aim is to provide a machine-tractable dictionary, based on painstaking corpus analysis, identifying all and only the normal, correct uses of each word in the language and showing how different components of a word's meaning potential are activated in different lexico-syntactic contexts.

The dictionary must account not only for literal uses but also for metaphors and other exploitations, insofar as these are comprehensible to human users of the language and can be distinguished from mistakes. For this reason, in addition to a syntactic description of each word's normal behaviour linked to a semantic interpretation, it is assumed that the dictionary will in due course contain a set of "exploitation rules", showing how metaphors and other exploitations are generated from norms.

The good news is that, even for a moderately complex verb such as SHAKE, all the normal uses are accounted for in a table of only three dozen phraseological patterns (five defaults and thirty variations).

The bad news is that the notion of a LEXICAL SET is central to the lexicosyntactic analysis, and there is no known shortcut to identifying membership of lexical sets. Intensional criteria are suspect, and machine-readable thesauruses wreak havoc. (Any good thesaurus will tell you that, like FINGER, FIST is semantically related to HAND, but of course "shaking one's fist" does not activate the same meaning of SHAKE as "shaking someone's hand".)

Turning to another entry, CLIMB, I shall show how different entailments are activated by the whole phraseological context, not by any one lexical item in it. "Climbing the steps" activates a slightly different set of implications from "climbing a mountain". Again, the norms can be schematized, and default semantic entailments attached.

Finally, if time allows, I shall give further illustrations of the distinction between norm and exploitation, and I shall claim that all questions and negatives are exploitations. ("Youthful enthusiasm", for example, is a type of enthusiasm, but "feigned enthusiasm" is not: it is a negative.)

BIO

Patrick Hanks is chief editor of Current English Dictionaries at Oxford University Press. His latest contribution to English lexicography is the New Oxford Dictionary of English, published in August 1998, edited with Judy Pearsall and a world-wide team of lexicographers.

Before joining OUP in 1990, he was chief editor of Collins English Dictionaries, having led the team that compiled the first edition of Collins English Dictionary (1979). From 1980 to 1983 he studied for a Ph.D. with Yorick Wilks at the University of Essex, having decided to put lexicography behind him.

From 1983 to 1990 he was managing editor and subsequently editorial director of the Cobuild project in computational lexical analysis, working with John Sinclair. From 1987 to 1990 he also worked on lexical analysis with Ken Church at AT&T Bell Labs. In 1991 he set up a collaboration ("the Hector Project") between Oxford University Press and Digital's Systems Research Center in Palo Alto CA, researching the relationship between word meaning and word use.

He has done stints in Germany, Poland, and Sweden as a teacher of English as a foreign language -- experiences which led to co-authorship of a highly successful EFL textbook, Business Listening Tasks (Cambridge University Press, 1986).

He has long had an interest in personal names, and is co-author of Dictionary of Surnames (1988), Dictionary of First Names (1990), and Concise Dictionary of First Names (1992, 1997), all published by Oxford University Press. He is currently chief editor of The Dictionary of American Family Names (four volumes, forthcoming).

Tuesday, June 3, 1999

Using Grice's Maxim of Quantity to Select the Content of Plan Descriptions

Michael Young
North Carolina State University

Complex activities, by definition, contain a large amount of detail. When people describe these activities, they very naturally emphasize information they feel is important and leave out information they feel isn't essential. This is an example of obeying what the philosopher Grice calls the Conversational Maxim of Quantity: say no more and no less than what's needed in the given context. The plans produced by AI planning systems are typically quite complex, even for fairly straightforward activities. In order for natural interfaces for describing these types of plans to be designed, a principled way for determining what content to retain and what content to remove must be developed. In this talk, I'll describe the Cooperative Plan Identification (CPI) architecture, an architecture for producing textual descriptions of AI plans. The CPI architecture uses computational interpretations of Grice's Maxim of Quantity to search the space of plan descriptions, selecting descriptions that are at once concise and effective. I'll also describe an empirical evaluation of the CPI architecture in which human subjects carried out instructions produced by the algorithm in a text-based virtual world. The evaluation provides strong evidence that plan descriptions produced by the CPI architecture were more effective than those produced by several competing algorithms.

Michael Young is an assistant professor in the Department of Computer Science at North Carolina State University. His current work focuses on human and computer collaboration, particularly in virtual worlds. Michael's research deals with formal models of planning and plan recognition, natural language discourse generation, and the development and use of computational models of narrative to describe the structure of human and computer interaction. Before joining the Computer Science faculty at NC State, Michael was a post-doctoral fellow in the Robotics Institute at Carnegie Mellon University, where his research centered on the roles of intelligent systems in contexts where teams of humans and computers collaborate together.

Friday, July 2, 1999

A Refinement Toolkit to Debug and Maintain Knowledge Based Systems

Susan Craw

School of Computer and Mathematical Sciences
The Robert Gordon University
Aberdeen, Scotland
Currently on sabbatical at UC Irvine.

Knowledge refinement tools have focused largely on debugging knowledge based systems implemented using specific tools; e.g. Prolog, Clips or particular expert system shells. The KRUSTWorks project is exploiting our refinement experience with a variety of applications to create a refinement framework that defines a set of generic KBS concepts and refinement steps, and implements an extensible toolkit that provides refinement components to achieve these steps. Thus KRUSTWorks will allow a knowledge engineer to assemble a particular KRUSTtool with which to refine a specific KBS. This talk describes the knowledge demands of such an approach and how the core refinement algorithm reasons about this centralized knowledge to achieve refinements of the target system. The approach will be demonstrated on TFS, a tablet formulation application that is in routine use at Zeneca Pharmaceuticals. The KRUSTtool removed faults from an early buggy version of TFS so that the refined KBS matched the manually debugged TFS. More impressively, the KRUSTtool further refined this version of TFS to effect the maintenance that produced the current TFS; its creation was prompted by a change in Zeneca's formulation policy.

Thursday, September 9, 1999

Statistical Machine Translation

Kevin Knight and Yaser Al-Onaizanw

This talk will describe a six-week project that Kevin and Yaser were working on this summer.

Friday, October 22, 1999

Data Mining and The Database Backend

Usama Fayyad
(DMX) Group Microsoft Research

Data Mining is about finding interesting structure from databases, especially large data stores. Since manageability and convenience dictate that data will have to live in databases, we consider the problem of understanding how a database can accommodate data mining operations very important. I'll outline the research challenges and opportunities posed by the problem of extracting models from massive data sets. Operating under such scalability constraints poses interesting problems for how models can be built and what methods are practical. Following a brief overview of this rapidly growing area of research and applications, I'll focus on data mining methods for classification and clustering. The focus will be on how to scale some of these data access-intensive algorithms to large databases, and in particular how such methods could fit in with database systems. I will also cover applications of these techniques to solving difficult problems in traditional database system. These problems include effecient indexing of data for nearest-neighbor (find similar) queries in high dimensions and to database and datacube compression in OLAP.

BIO OF USAMA FAYYAD:
Usama Fayyad is a Senior Researcher at Microsoft Research, where he heads the Data Mining & Exploration (DMX) Group. His research interests include scaling data mining algorithms to large databases, learning algorithms, and statistical pattern recognition, especially classification and clustering. At Microsoft he also works on shipping data mining capabilities in products such as Microsoft Commerce Server and Microsoft SQL Server. After receiving the Ph.D. degree from The University of Michigan, Ann Arbor in 1991, he joined the Jet Propulsion Laboratory (JPL), California Institute of Technology, where (until 1996) he headed the Machine Learning Systems Group and developed data mining systems for automated science data analysis. He received the 1994 NASA Exceptional Achievement Medal and the JPL 1993 Lew Allen Award for Excellence in Research for his work on developing data mining systems to solve challenging science analysis problems in astronomy and remote sensing. He remains affiliated with JPL as a Distinguished Visiting Scientist. He is a co-editor of Advances in Knowledge Discovery and Data Mining (MIT Press, 1996) and is an Editor-in-Chief of the journal: Data Mining and Knowledge Discovery. He was program co-chair of KDD-94 and KDD-95 (the First International Conference on Knowledge Discovery and Data Mining) and is general chair of KDD-96 and KDD-99. He is a director of the ACM SIGKDD and serves as Editor-in-Chief of its newsletter: SIGKDD Explorations.

Friday, November 19, 1999

Understanding (a little of) the Genome: What turns genes on

Dennis Kibler

The talk will begin with a short review of the necessary biological knowledge so that both the significance of locating binding sites and the constraints of biological fidelity are understood. Our approach towards finding binding sites relies on two major steps. First, we form families of co-regulated genes by clustering the gene expression data which we get from the Affymetrix gene chip machine. Next, using the family of co-regulated genes, we carry out a stochastic hill-climbing search over the upstream region of the genes for the binding sites. Through this procedure we have rediscovered known binding sites and suggested additional candidate binding sites.

Friday, December 3, 1999

Compiling Probabilistic and Logical Knowledge

Adnan Darwiche

Compiling knowledge has been emerging recently as a new direction of research for dealing with the computational intractability of reasoning. According to this approach, the reasoning process is split into two phases: an off-line compilation phase and an on-line query-answering phase. The main motivation behind knowledge compilation is to push as much of the computational overhead as possible into the off-line phase, in order to amortize that overhead over all on-line queries. Another motivation is to produce very simplistic on-line reasoning systems, which can be embedded cost effectively into primitive computational platforms. In this talk, I will discuss earlier work on compiling probabilistic knowledge in the form of Bayesian networks into parameterized arithmetic expressions. I will also discuss more recent work on compiling propositional theories into a new logical form, known as decomposable negation normal form (DNNF). I will go over applications of the compilation techniques to model-based diagnosis, and then touch upon recent work on its application to satisfiability-based planning.

Friday, December 10, 1999

Learning Dictionaries for Information Extraction by Multi-Level Bootstrapping

Ellen Rilloff

Information extraction systems usually require two dictionaries: a semantic lexicon and a dictionary of extraction patterns for the domain. We will present a multi-level bootstrapping algorithm that generates both the semantic lexicon and extraction patterns simultaneously. As input, our technique requires only unannotated training texts and a handful of seed words for a category. We use a "mutual bootstrapping" technique to alternately select the best extraction pattern for the category and bootstrap its extractions into the semantic lexicon, which then becomes the basis for selecting the next extraction pattern. To make this approach more robust, we add a second level of bootstrapping (meta-bootstrapping) that retains only the most reliable lexicon entries produced by mutual bootstrapping and restarts the process. We evaluated this multi-level bootstrapping technique on a collection of corporate web pages and a corpus of terrorism news articles. The algorithm produced high-quality dictionaries for several semantic categories.