(12) Anytime Hypothetical Reasoning

[Contents]

1. Background of the research
2. Purpose of the research
3. Contents of the research
4. Project Organization/Research Method
5. Resulting Software

[Background of the research]

Hypothetical reasoning [16][15] and the closely related class of default reasoning approaches play a fundamental role in a variety of knowledge processing applications. Hypothetical reasoning, and more generally, default inference, is inherently computationally hard [13] and practical applications, especially time-bounded ones, may require that some notion of approximate inference be used. Any approximation algorithm must provide useful partial results and the trade-offs involved must be clearly identified.

Approximate default inference has received scant attention in the literature. Notable exceptions include the work of Cadoli and Schaerf [1] in which they improve on the complexity of reasoning with Reiter's default logic by using consequence relations that are sound and incomplete in one case and complete but unsound in the other), the recent results of Etherington and Crawford [3] involving using limited contexts and fast incomplete consistency checks as well as the earlier work of Perlis [14]. Motivated by such deficiencies in the state-of-the-art, this project seeks to develop a system for approximate hypothetical reasoning by means of anytime algorithms.

[Purpose of the research]

Real-time algorithms are usually designed to satisfy a variety of application-specific requirements: some are required to provide partial, but useful results whenever they are stopped while others have the additional requirement that their partial results improve with time. Anytime algorithms are a useful conceptualization of processes that may be prematurely terminated whenever necessary to return useful partial answers, with the quality of the answers improving in a well-defined manner with time. Dean and Boddy [2] define an anytime algorithm to be one which:

• Lends itself to preemptive scheduling techniques.
• Can be terminated at any time and will give some meaningful answer.
• Returns answers that improve in some well-behaved manner as a function of time.

In the THEORIST system for hypothetical reasoning [16][15], a knowledge base is a triple (F, H, C) where F is a set of closed formulae representing the facts, H is a set of (not necessarily closed) formulae representing the hypotheses and C is another set of closed formulae representing the constraints. A scenario is a set F ∪ h where h is a set of ground instances of H such that F ∪ h ∪ C is consistent. We shall define an extension to be the deductive closure of a maximal (w.r.t. set inclusion) scenario.

This project seeks to implement a hypothetical reasoning system which supports anytime query processing. The proposed system will support the following classes of queries:

• Explanation: Given an observation g, find a minimal scenario which explains g (i.e. a minimal, w.r.t. set inclusion, F ∪ h such that F ∪ h g).
• Coherence: Compute an extension of a given knowledge base (F, H, C).
• Set-membership: Determine if a given formula φ is an element of any extension of (F, H, C).
• Set-entailment: Determine if a given formula φ is an element of all extensions of (F, H, C).

It will be possible to arbitrarily interrupt the system during the processing of each of these queries to obtain partial solutions. The quality of the solutions, obtained by applying solution quality metrics defined for each class of queries, would improve in a well-defined manner with the time available to compute the partial solutions.

[Contents of the research]

In [8] and [4], we have defined a repertoire of strategies for anytime default inference which can be broadly classified as follows:

• Restriction strategies: The general class of restriction strategies use different notions of restriction functions to obtain restricted versions of the original knowledge base which are simpler and smaller and for which exact solutions can be computed in the available time. In abstract terms, the anytime progression (i.e., the process through which an anytime algorithm progressively computes solutions of measurably improving quality) involves progressively less restricted theories being considered, following some priority ordering. In other words, we begin with a highly restricted knowledge base containing only information at the highest priority level which is used for answering queries. If additional time is available, we identify a less restricted knowledge base containing, in addition to the original version, information from the next lower level of priority for the purpose of query answering. The process iterates in a similar fashion if still more time is available. The restriction function takes two arguments: a THEORIST knowledge base and a parameter (to be explained below) which indicates how the knowledge base is to be restricted. This second parameter changes with progressively larger time steps. The class of restriction strategies can be further sub-divided as follows:

  -Language restriction strategies: With such strategies, the knowledge base is restricted to some subset of the language, with the anytime progression considering progressively larger subsets. We shall consider two ways in which such strategies may be implemented:

  *Predicate restriction: We shall assume the existence of a priority ordering on the predicate symbols (or propositional letters in the simpler case of propositional theories) of the language. It is relatively easy to identify such orderings in realistic situations; in a reactor control system, the reactor temperature predicate takes priority over the predicate concerning the pH value of the water in the cooling system, for instance. The anytime progression involves considering knowledge bases restricted with respect to progressively larger subsets of the set of predicate symbols.
  

  *Formula restriction:These strategies are similar to the predicate restriction strategies, except that the knowledge base is restricted with respect to arbitrary sets of formulae instead of predicate symbols.

  -Theory restriction: This constitutes the simplest class of restriction strategies. We exploit a priority ordering defined on the set of hypotheses H to consider knowledge bases consisting of the higher priority hypotheses first and adding lower priority ones when additional time is available.

• Abstraction strategies: These strategies exploit results from our work on default abstractions [6]. In the context of hypothetical reasoning, the notion of hypotheses abstraction is as follows. Informally, a set of hypotheses represents the abstraction of another set of hypotheses if each maximal scenario of a THEORIST knowledge base in which the latter is replaced by the former set of hypotheses (other components remaining the same) is included in some maximal scenario of the original knowledge base. In this case the anytime progression involves abstracting away classes of irrelevant, or lower priority hypotheses, for initial query answering and progressively refining the knowledge base (where, informally, the refinement relation is the inverse of the abstraction relation) if more time becomes available.

We shall consider two classes of metrics for measuring solution quality:

• Proximity-to-exact-solution metrics: These metrics use the distance of the partial solution from the exact solution to evaluate solution quality. The notion of distance can be interpreted in different ways. A simple interpretation treats a scenario x' to be closer to the exact solution x than a scenario x'' if and only if x'' ⊂ x' ⊆ x. This class of metrics applies only to explanation and coherence queries; it does not make sense to consider the distance of one boolean-valued solution from another (as in set-membership and set-entailment queries) using the metric described above.
• Proximity-to-exact-theory metrics: These metrics are based on the intuition that a partial solution to a query may be viewed as an exact solution to the same query with respect to a restricted version of the original knowledge base. Given this, one partial solution is deemed to be better than another if the former is an exact solution with respect to a restricted knowledge base which is closer to the original knowledge base than the restricted knowledge base for which the latter is an exact solution. Once again, we have to account for a notion of distance, but in this case, between knowledge bases. The restriction functions, together with the priority orderings provide a simple method of comparing distances. Given a language with a set of predicate symbols p, a knowledge base restricted to some subset p' of these symbols is deemed to be closer to the exact knowledge base than another knowledge base restricted to the subset p'' of predicate symbols if and only if p'' ⊂ p' ⊆ p. This is the only class of metrics that can be applied to queries with boolean-valued solutions, such as set-membership or set-entailment. However, they can also be applied to the explanation and coherence queries.

  This project seeks to implement a hypothetical reasoning system which supports anytime query processing for the following classes of queries: explanation, coherence, set-membership and set-entailment. For each class of query, the proposed system shall support the following repertoire of four anytime strategies: predicate restriction, formula restriction, theory restriction and abstraction-based strategies. After the completion of the implementation phase, we propose to carry out experiments with randomly generated propositional THEORIST knowledge bases, along lines similar to those in [3]. In addition, we propose to implement a small prototype real-world application involving the use of a THEORIST knowledge base to encode user preferences in a news/web content filtering system. The system shall support arbitrary termination of execution by means of clicking on a ``stop" button similar to those supplied with web browsers.

  The implications and applicability of an implemented anytime hypothetical reasoning system extend far beyond the simple application described above. Our earlier work [7][12][17] has demonstrated a close connection between hypothetical reasoning and constraint satisfaction problems, specifically partial constraint satisfaction problems. Our proposed system can thus serve as a template for anytime systems for partial constraint satisfaction. Our earlier work has also demonstrated the crucial role played by hypothetical reasoning in incremental inductive logic programming [5], the management of requirements evolution in the context of requirements engineering [18], software maintenance [9] and belief revision [11][10]. The proposed system can thus provide the basis for anytime knowledge processing in each of these domains.

[Project Organization/Research Method]