ARO Workshop on Abductive Reasoning

                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Abstracts

1) Abductive Inferences, Perception and Multi-Source Information Fusion
John Josephson, Ohio State University

2) Statistical Relational Learning
Pedro Domingos, University of Washington

3) Probability vs Evidence
Glenn Shafer, Rutgers University

How can reasoning from fragmentary evidence make use of statistical theories that require more structured starting points? Recent work on defensive forecasting casts new light on this question. The conventional wisdom is that statistical methods require an objective probability model, supplemented by subjective assumptions when no such model has been validated. But the success of defensive forecasting shows that the crucial question is not whether there is a valid model but simply whether there is an agreed-on repetitive structure for the question to be answered and the data for answering it. If we agree to place the current example in a particular sequence of other examples, then defensive forecasting can produce valid probability forecasts—valid insofar as they resist all statistical tests—without any assumptions. But if no single sequence of previous examples imposes itself, then we must go outside the framework of probability theory to weigh evidence. Reasoning to the best explanation means reasoning to the best repetitive structure.

4) Learning Structure from Relational Observations: A Bayesian Approach
Tina Eliassi-Rad, Lawrence Livermore National Laboratory

In many real-world applications, observations appear in the form of links or connections between objects (e.g. communication networks, financial transaction networks, social networks, etc). Such networked data contain valuable information that can be exploited in order to discover groups, predict links, and generally speaking better understand the structure within the observations. A fundamental issue in all structure discovery problems is that the actual size of the structure is unknown a priori. In most cases, this is addressed by running the same model several times with a different cardinality each time and selecting the one that provides the best fit to the data (e.g., based on a Bayes factor criterion in the case of Bayesian techniques). Obviously, it would be preferable to develop techniques that are able to infer the size of the structure from the data and simultaneously examine hypotheses of different cardinalities. Nonparametric Bayesian latent variable models provide such a flexible modeling environment, where the size of the model (i.e., the number of groups) can adapt to the available data and readily accommodate outliers. Of particular interest are models that can represent an object’s mixed membership by quantifying the degrees of membership to various groups. In this talk, I will describe such a model, called the Infinite Mixed Membership Model (IMMM). Our IMMM model has a hierarchical nonparametric prior that is based on the Chinese Restaurant Franchise. Inference is readily performed using Gibbs sampling. I will also describe an extension to our model that generates hierarchical structures from the data. Based on empirical studies on synthetic and real data, our model performs very well (as measured by the area under the ROC) when missing links abound. Three areas of future work include: (1) efficient inference procedures for nonparametric Bayesian approaches, (2) structure discovery by combining Bayesian and graph-theoretic approaches, and (3) nonparametric Bayesian models for time-evolving networked data.

5) Statistical Relational Learning for Abductive Reasoning in Heterogeneous Environments
Lise Getoor, University of Maryland

New technology is making it possible to deploy large numbers of sensing devices with widely varying capabilities. Because of their large size and diverse properties, it will be extremely difficult to hand-code control strategies for these heterogeneous sensor networks. At the same time, effective strategies are extremely important to effectively integrate large amounts of data, to carefully allocate scarce resources such as power, and to detect anomalies that can occur due to malicious tampering.

Statistical Relational Learning (SRL) is an emerging research area that combines probabilistic (statistical) inference with logical (relational) inference. Its roots are in probabilistic graphical models, but it is distinguished by its use of logical representations and constraints to model and exploit domain structure and regularities. It is well-suited to domains in which there is a mix of low-level noisy observational data that needs to be combined together based on logical relationships such as proximity, field-of-view, and other contextual constraints.

7) Higher Order Learning
William Pottenger, Rutgers University

Modern data mining algorithms primarily leverage first-order relations, aiming to discover patterns such as association or classification rules only within records. The underlying assumption is that records are independent and identically distributed (Taskar et al., 2002). This assumption simplifies the underlying mathematics of statistical models, but in fact does not hold for many real world applications (Getoor & Diehl, 2005). Although useful models can be learned, in many cases more accurate models can be learned if higher-order associations are leveraged by the data mining algorithm – associations between records. Coupled with this is a growing need for data fusion due to increasing data fragmentation (Rahm & Bernstein, 2001). Consequently, there is a greater need to incorporate contextual information – i.e., higher-order associations that cross record boundaries.

Some limited higher-order information is already employed in a number of applications including market basket analysis, law enforcement, homeland defense, etc. For example, an important law enforcement application that employs 2nd-order associations is COPLINK(r) Detect (Hauck et al., 2002), which assists law enforcement personnel using textual entity extraction and link-generation to build a semantic network. Mooney et al. (2002) discuss a link discovery algorithm developed as part of the DARPA Evidence Extraction and Link Discovery program that uses Inductive Logic Programming to mine multi-relational data. Tan et al. (2000; 2002) intimate that the future of cross-selling in the e-Marketplace may be greatly impacted by the results of further study of higher-order associations. This is in keeping with our own results on real world e-Marketplace data, which indicate that the latent information contained in higher-order associations can be leveraged to build more effective association rule models. Yet other than our own, existing approaches at best incorporate only a fraction of the available higher-order latent information in that most are limited to 2nd-order associations.

8) Robust Reasoning and Learning about Goal-Directed Activities
Pat Langley, Arizona State University

One key facet of intelligence is the ability to interpret events in the environment, including abductive inference about the activities and motives of other agents. Despite their importance, there has been far less research on activity interpretation and plan understanding than there has been on plan execution and generation. Nevertheless, many ideas from the latter traditions are relevant to the former and can be adapted to address them.

In this talk, I review work on hierarchical task networks, a formalism that encodes ways to decompose tasks into subtasks and that has been used successfully for knowledge-based planning and execution. I focus on a special class of these structures - teleoreactive logic programs - that support both the explanation of observed behavior sequences and learning network structure from them.

Our initial efforts have focused on logical analysis of behavior traces, but we are developing an extended formalism - Markov task networks - that incorporates probabilistic information about task clauses and that supports plausible inference in the presence of incomplete and uncertain information. Unlike more general formalisms, Markov task networks are designed to support abductive inference about goal-directed behaviors as they are observed over time.

I will also describe our plans for learning within this framework.

Unlike most statistical relational methods, our approach uses knowledge-guided inference over individual traces to generate candidate relational structures. Statistical evidence is used to evaluate these hypotheses and to revise probabilities associated with each structure. We claim that such a knowledge-driven approach will learn from far fewer cases than ones which rely on statistical regularities to generate hypotheses.

9) Trailblazing, Complex Hypothesis Evaluation, Abductive Inference and Semantic Web – exploring possible synergy
Amit P. Sheth, Wright State University

Dr. Vannevar Bush outlined his vision for Memex in a 1945 Atlantic Monthly article [B45]. Describing how the human brain navigates an information space in what he called trailblazing, Dr. Bush said, “It operates by association. With one item in its grasp, it snaps instantly to the next that is suggested by the association of thoughts, in accordance with some intricate web of trails carried by the cells of the brain.” Now that we can label content with associated meaning (semantics), using the techniques of information extraction, we can develop an interactive, human-directed, semantic browsing environment in which analysts can explore heterogeneous content from disparate sources in a kind of stream-of-consciousness, identifying one item of interest and then following contextually relevant links to another [SR07]. See Figure 1.

Figure 1: Semantic Browser Interface showing neoplastic process "degree of" experimental model of disease	Figure 2: Complex Hypothesis linking Migrane and Magnesium that can be divided into sub-hypotheses and validated against a set of relevant documents

A second, complementary form of analysis that is now possible is to specify a complex hypothesis, break it down into different pieces, and look for evidence to match parts of the hypothesis (Figure 2).

In current Semantic Web research, longstanding work in IR, information extraction, NLP, statistical NLP, graph and query processing, among other techniques, is paired with knowledge representation and populated ontologies (schemas and associated fact/knowledge base) for the following activities that process all varieties of data: structured, semi-structured, and unstructured/text:

Extraction of entities [HSK02] and relationships [RSK06] (which form the semantic annotation or labeling of data—a key characteristic of Semantic Web) and their representation in RDF, which models named relationships (predicated in triples of the form <subject, predicate, object>

Subgraph extraction [RMPS05], path computations (semantic associations discovery) [AMS07], similarity, causality and other pattern discovery;

Support for higher-order activities including semantic search and querying [AMS05], semantic browsing, reasoning, analysis, hypothesis evaluation [STP03], discovery, explanation, question-answering and visualization

Some of the activities above involve processing in which complete certainty is not possible (e.g., entity and relationship extraction techniques applied to text). Some involve the need to process graphs with weights. Still others involve the need to model knowledge that cannot be modeled using the mainstream representation choice of description logics (such as OWL) and that requires fuzzy logic.. We used the terms “implicit semantics,” “formal semantics,” and “power semantics” to describe the range of requirements and choices [SRT05].

10) Known Unknowns - Probabilistic Inference and Large Knowledge Bases
Michael Witbrock, Cycorp, Inc., Austin, Texas

One aspect of Cyc is a very large, logic-based knowledge base that includes, inter-alia, large amounts of background knowledge about military and counter-terrorism matters, but it is more than that; the Cyc project is an attempt to move towards general artificial intelligence by supporting automated reasoning about a very wide variety of real-world concerns. To support that goal, Cyc also encompasses, obviously enough, and inference engine able to reason over a large, contextual, knowledge base, but it also includes components for interpreting and producing natural language, acquiring knowledge and responding to user queries, and for interfacing with other software.

Applying logic to representation of general knowledge, /at scale/, and using it in the production of intelligent behaviors has been difficult enough; unfortunately it is becoming clear that doing so using traditional logics is probably not sufficient, either for satisfying a long term goal of supporting general intelligence, or even for shorter term goals, like recognizing, interpreting, and elaborating descriptions of piracy events.

11) Statistical Learning and Probabilistic Abduction
Padhraic Smyth, University of California, Irvine

12) Searching for Interesting Plans as They Happen
Paul Cohen and Aram Galstyan, University of Southern California

13) Abductive Inference of Opponent Models
Dana Nau, University of Maryland

Opponent modeling -- i.e., building models of other agents' behavior -- is becoming increasingly important in military operations, economic modeling, cultural modeling, computer games, and other applications. The University of Maryland's Laboratory for Computational Cultural Dynamics (LCCD) has a major research effort on abductive techniques for inferring opponent models. I'll summarize our SOMA (Stochastic Opponent Modeling Agents) formalism. SOMA lets us express the probability that a given person or group will act in a certain way in a given situation, and we have techniques for abductively inferring SOMA rules from observed behavior.