Magazine article AI Magazine

Empirical Methods in AI

Magazine article AI Magazine

Empirical Methods in AI

Article excerpt

* In the last few years, we have witnessed a major growth in the use of empirical methods in Al. In part, this growth has arisen from the availability of fast networked computers that allow certain problems of a practical size to be tackled for the first time. There is also a growing realization that results obtained empirically are no less valuable than theoretical results. Experiments can, for example, offer solutions to problems that have defeated a theoretical attack and provide insights that are not possible from a purely theoretical analysis. I identify some of the emerging trends in this area by describing a recent workshop that brought together researchers using empirical methods as far apart as robotics and knowledge-based systems.

Twenty-five researchers gathered together during the Fifteenth International joint Conference on Artificial Intelligence (IJCAI-97) in Nagoya, Japan, for the Second Workshop on Empirical Artificial Intelligence. The workshop continued the work of a similar workshop held alongside ECAI-96 in Budapest, Hungary, the previous year. The workshop began with an invited talk by Henry Kautz (AT&T Labs). The rest of the workshop was arranged around two panels and two invited papers, designed to illustrate good empirical methods. Each panel had three panelists who kicked off a lively discussion by making some provocative remarks. The main goal of the workshop organizers was to limit the number of formal presentations and encourage discussion. The workshop format was highly successful at achieving this aim. I would recommend a similar format to other workshop organizers.

The debate during the workshop can broadly be divided into three categories: (1) past successes of empirical methods, (2) the design of computational experiments, and (3) the widespread use of random problems. The following summary necessarily offers just a partial description of the topics discussed during the workshop.(1)

Success Stories

Empirical methods have been successful in recent years. Indeed, as Henry Kautz reminded the workshop participants, in the last year alone, the New York Times has reported two major empirical successes: (1) DEEP BLUE'S defeat of Kasparov and (2) the computer-generated proof of an open problem in Robbins algebra. Pandurang Nayak (NASA Ames) described another highly publicized success, the diagnosis system for the Deep Space One spacecraft, which is based on a highly optimized satisfiability procedure. Although deciding satisfiability is intractable in general, this system generates plans in practice in essentially constant time for each step. It comes as quite a surprise to hear about real-time satisfiability testing.

Henry Kautz listed several reasons for the success of empirical methods. First, empirical studies are often an integral part of Al because systems can be too complex or messy for theory. Second, theory is often too crude to provide useful insight. For example, a problem might be exponential in the worst case but tractable in practice. Third, some questions are purely empirical. As Pedro Meseguer (IIIA, CSIC, Spain) pointed out during one of the panels, two search algorithms might not be comparable theoretically because the nodes searched by one algorithm are not subsumed by the other, but empirical evidence might strongly suggest we prefer one over the other. Kautz identified several other reasons to use empirical methods. Experimental results might, for example, identify new computational phenomena. Much of the recent research in threshold phenomena (so-called phase transitions) has been empirical. The theoretical analysis of such behavior is currently far behind. Experiments can also suggest new theory and algorithms. For example, the large body of research into stochastic algorithms such as GSAT has been stimulated by empirical success. Theory is still a long way from explaining the success of local search on large satisfiability problems. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed


An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.