MITAP (MITRE text and audio processing) is a prototype system available for monitoring infectious disease outbreaks and other global events. MITAP focuses on providing timely, multilingual, global information access to medical experts and individuals involved in humanitarian assistance and relief work. Multiple information sources in multiple languages are automatically captured, filtered, translated, summarized, and categorized by disease, region, information source, person, and organization. Critical information is automatically extracted and tagged to facilitate browsing, searching, and sorting. The system supports shared situational awareness through collaboration, allowing users to submit other articles for processing, annotate existing documents, post directly to the system, and flag messages for others to see. MITAP currently stores over 1 million articles and processes an additional 2,000 to 10,000 daily, delivering up-to-date information to dozens of regular users.

Much work in AI deals with the selection of proper actions in a given (known or unknown) environment. However, the way to select a proper action when facing other agents is quite unclear. Most work in AI adopts classical game-theoretic equilibrium analysis to predict agent behavior in such settings. This approach however does not provide us with any guarantee for the agent. In this paper we introduce competitive safety analysis. This approach bridges the gap between the desired normative AI approach, where a strategy should be selected in order to guarantee a desired payoff, and equilibrium analysis. We show that a safety level strategy is able to guarantee the value obtained in a Nash equilibrium, in several classical computer science settings. Then, we discuss the concept of competitive safety strategies, and illustrate its use in a decentralized load balancing setting, typical to network problems. In particular, we show that when we have many agents, it is possible to guarantee an expected payoff which is a factor of 8/9 of the payoff obtained in a Nash equilibrium. Our discussion of competitive safety analysis for decentralized load balancing is further developed to deal with many communication links and arbitrary speeds. Finally, we discuss the extension of the above concepts to Bayesian games, and illustrate their use in a basic auctions setup.

We develop, analyze, and evaluate a novel, supervised, specific-to-general learner for a simple temporal logic and use the resulting algorithm to learn visual event definitions from video sequences. First, we introduce a simple, propositional, temporal, event-description language called AMA that is sufficiently expressive to represent many events yet sufficiently restrictive to support learning. We then give algorithms, along with lower and upper complexity bounds, for the subsumption and generalization problems for AMA formulas. We present a positive-examples--only specific-to-general learning method based on these algorithms. We also present a polynomial-time--computable ``syntactic'' subsumption test that implies semantic subsumption without being equivalent to it. A generalization algorithm based on syntactic subsumption can be used in place of semantic generalization to improve the asymptotic complexity of the resulting learning algorithm. Finally, we apply this algorithm to the task of learning relational event definitions from video and show that it yields definitions that are competitive with hand-coded ones.

This paper presents a new classifier combination technique based on the Dempster-Shafer theory of evidence. The Dempster-Shafer theory of evidence is a powerful method for combining measures of evidence from different classifiers. However, since each of the available methods that estimates the evidence of classifiers has its own limitations, we propose here a new implementation which adapts to training data so that the overall mean square error is minimized. The proposed technique is shown to outperform most available classifier combination methods when tested on three different classification problems.

Deduction, induction, and abduction [Pei55] are the three basic reasoning mechanisms. Deduction allows drawing conclusions from known facts using some piece of knowledge, so that "battery is down" allows concluding "car will notstart"thanks totheknowledge oftherule"if thebatteryisdown, the car will not start". Induction derives rules from the facts: from the fact that the battery is down and that the car is not starting up, we may conclude the rule relating these two facts. Abduction is the inverse of deduction (to some extent [MF96]): from the fact that the car is not starting up, we conclude that the battery is down. Clearly, this is not the only possible explanation 2 of a car not starting up.

In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.

Is there a general model that can predict the perceived phrase structure in language and music? While it is usually assumed that humans have separate faculties for language and music, this work focuses on the commonalities rather than on the differences between these modalities, aiming at finding a deeper 'faculty'. Our key idea is that the perceptual system strives for the simplest structure (the 'simplicity principle'), but in doing so it is biased by the likelihood of previous structures (the 'likelihood principle'). We present a series of data-oriented parsing (DOP) models that combine these two principles and that are tested on the Penn Treebank and the Essen Folksong Collection. Our experiments show that (1) a combination of the two principles outperforms the use of either of them, and (2) exactly the same model with the same parameter setting achieves maximum accuracy for both language and music. We argue that our results suggest an interesting parallel between linguistic and musical structuring.

For many individuals and organizations think example, software programs can be used to about and perform their work. Electronic commerce--the obtain cheaper prices for utilities such as basic conduct of business activities electronically telephone services. A simple program can be by digital media--is now part of installed to monitor and direct long distance everyday business. The user dials the country code, and as sharp falls in the share prices of many "dotcoms" he/she continues to dial the telephone number, since early 2000, electronic commerce is the program contacts various long distance still likely to have a major and lasting effect on providers and negotiates the best deal for its most forms of economic activities. The program can be set up to inform the Advances in web-based technologies further user about the price before the call is connected; support the growth of electronic commerce. In for example, the best rate for this call is nine particular, automation and delegation technologies--known cents a minute with no minimum charge.

We examine the design space of auction mechanisms and identify three core activities that structure this space. Formal parameters qualifying the performance of core activities enable precise specification of auction rules. This specification constitutes an auction description language that can be used in the implementation of configurable marketplaces. The specification also provides a framework for organizing previous work and identifying new possibilities in auction design.

After outstanding service as Book Review Editor, B. Chandrasekaran has completed his term. His energetic guidance of the book reviews section brought the magazine a rich set of reviews that were always eagerly anticipated, and I would like to thank him for his important contributions. I am delighted to announce that Michael Wellman, of the University of Michigan, has agreed to join the magazine as the new Book Review Editor. I know that the book reviews feature will flourish under his stewardship, and I enthusiastically welcome him to the magazine. I would also like to draw readers' attention to a related addition to the AI Magazine web site (www.aimagazine.org).