For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work, we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary topologies. We also give a novel formalization of stochastic local search, with focus on initialization and restart, using probability theory and mixture models. Experimentally, we apply our methods to the problem of MPE computation, using a stochastic local search algorithm known as Stochastic Greedy Search. By carefully optimizing both initialization and restart, we reduce the MPE search time for application BNs by several orders of magnitude compared to using uniform at random initialization without restart. On several BNs from applications, the performance of Stochastic Greedy Search is competitive with clique tree clustering, a state-of-the-art exact algorithm used for MPE computation in BNs.

This paper describes the use of machine learning to improve the performance of natural language question answering systems. We present a model for improving story comprehension through inductive generalization and reinforcement learning, based on classified examples. In the process, the model selects the most relevant and useful pieces of lexical information to be used by the inference procedure. We compare our approach to three prior non-learning systems, and evaluate the conditions under which learning is effective. We demonstrate that a learning-based approach can improve upon "matching and extraction"-only techniques.

Describes a model-based design method to develop CoRaven, a decision support tool that is intended to assist military intelligence analysts in managing and interpreting large quantities of battlefield information. In this method, we use observations of practitioners solving specific tasks in order to understand and model how they use information. We use this model of the task to help identify user needs that the tool must support, and, during initial prototyping, to guide usability analyses. We have found task models to be an important consideration in the decision support tool design process that can help to constrain the design space and reduce the time required to develop an effective decision support tool prototype.

Intelligence analysis is one of the major functions performed by an Army staff in battlefield management. In particular, intelligence analysts develop intelligence requirements based on the commander's information requirements, develop a collection plan, and then monitor messages from the battlefield with respect to the commander's information requirements. The goal of the CoRAVEN project is to develop an intelligent collaborative multimedia system to support intelligence analysts. Key ingredients of our design approach include: (1) significant knowledge engineering activities with domain experts, (2) representation of an explicit model of reasoning and activity to drive design, (3) the use of Bayesian belief networks as a way to structure inferences that relate observable data to the commander's information requirements, (4) collaborative graphical user interfaces to provide flexible support for the multiple tasks in which analysts are engaged, (5) sonification of data streams and alarms to support enhanced situation awareness, (6) detailed psychological studies of reasoning and judgment under uncertainty, and (7) iterative prototyping of candidate designs with domain experts for both formative and summative evaluation. The paper discusses our current progress on all these fronts.

Abstract An explicit representation of the problem solving method of an expert system shell as abstract control knowledge provides a powerful foundation for learning. This paper describes the abstract control knowledge of the HERACLES expert system shell for heuristic classification problems, and describes how the ODYSSEUS apprenticeship learning program uses this representation to semi-automate “endgame” knowledge acquisition. The problem solving method of HERACLES is represented explicitly as domain-independent tasks and metarules. Metarules locate and apply domain knowledge to achieve problem solving subgoals, such as testing, refining, or differentiating between hypothesis; and asking general or clarifying questions. We show how monitoring abstract control knowledge for metarule premise failures provides a means of detecting gaps in the knowledge base. A knowledge base gap will almost always cause a metarule premise failure. We also show how abstract control knowledge plays a crucial role in using underlying domain theories for learning, especially weak domain theories. The construction of abstract control knowledge requires that the different types of knowledge that enter into problem solving be represented in different knowledge relations. This provides a foundation for the integration of underlying domain theories into a learning system, because justification of different types of new knowledge usually requires different ways of using an underlying domain theory. We advocate the construction of a definitional constraint for each knowledge relation that specifies how the relation is defined and justified in terms of underlying domain theories.