Reasoning in the real world must often deal with imperfect information, and default assumptions must be made. Thirteen cases in which this is true are discussed. A practical reasoning system must perform parametric, symbolic and higher order reasoning; these are described. Requirements for default reasoning: default conclusions, nonmonotonicity, truth maintenance, ordering of extensions, and practicability are given. Characteristic features of default reasoning models: allocation of belief to propositions, representations of extensions, and modularity vs cohesiveness are discussed. Finally tables are given comparing selected reasoning systems/models on Domains, Satisfaction of Requirements, and Characteristic Features.

Most real world reasoning is formed in the context of *information*
imperfections. Extended logics incorporate heuristic assumptions and defaults
in the reasoning process. This allows a human or system to make inferences and
reach conclusions based on imperfect information.

In *truth maintenance systems*, the system will check its assumptions
in order to identify one or more assumptions or hypotheses that will be
rejected when a deduction is made that is inconsistent with previous
deductions. In *assumption based truth maintenance systems*, the system
will identify the assumption sets that are in conflict when conflicting
deductions are identified and designate each deduction with the alternative
assumption sets under which that deduction would be consistent, which can be
used to identify the setting under which each new deduction follows.

Probabilists view the qualification problem in terms of symbolic logic. Defaults will often be used to deal with it, but this is usually an inefficient way to express improbability. Researchers in logic-based reasoning suggest a probabilistic viewpoint is useless because it does not support reasoning about qualifiers. Reiter suggests nomonotonic reasoning results in a formal approach to reasoning conventions; and with respect to such conventions, statistical reasoning has no role whatsoever.

However, a goal of monotonic reasoning is to generate conclusions that are usually correct, so some form of probabilistic or statistic reasoning should play a role in reasoning based on conventions. We suggest an approach to inferences based on imperfect information that coherently combines nonmonotonic reasoning and measure based or probabilistic reasoning. Logic is descriptively universal. Classic logic can be made to handle real-world domains effectively, but not efficiently, so default reasoning is necessary.

**II. A Taxonomy of Imperfect Information Cases**

The cases:

**The Qualification Problem**

It is impractical and implausible to include all preconditions for the successful performance of an action. Default rules are required to reason about actions or formulate plans without having to anticipate and check every condition that could fail -- the default rule would include ony the preconditions that are typically relevant.

functional need |
To reason about plans and actions |

available incomplete information |
The list and status of conditions that could interfere with the actions |

reasons available information is incomplete |
The list of possible qualifications is intractably large. |

uncertain information |
Whether unusual or unanticipated conditions will arise |

assumptions useful for handling the problem
that could be made through default reasoning |
Unusual or unanticipated circumstances do not pertain. |

**The Frame Problem**

The frame problem deals with change over time; ideal reasoning would require rules to specify the exact effect of each action on all other time-dependent knowledge, even if there is no direct connection. We need to avoid the effort of reinferring, even on a default basis, the persistence of every piece of time dependent knowledge for every instant of time.

When there is insufficient time to consider every possibility, default rules may be useful for quick rough answers. Ideally, the rules could be layered such that the system could select the level of detail based on the time available and costs. Time constraints can force the use of defaults regardless of other factors.

functional need |
To reason within time constraints. |

available incomplete information |
Whatever information and conclusions are missed in the rush |

reasons available information is incomplete |
Insufficient time is available to fully collect and consider information before the decision is required |

uncertain information |
Whether enough information has been considered in enough depth |

assumptions useful for handling the problem
that could be made through default reasoning |
Any reasonable assumptions that save perception and deduction time as appropriate to the available time. |

Reasoning consumes time and mental effort, which much be weighed against the expected gain of the resulting decisions and the opportunity cost of using these resources differently.

**Inaccessible or Unavailable Information**

Unavailable information calls for assumptions to be made concerning what is missing. In more general cases it is infeasible to anticipate the possible combinations of missing inputs, so some form of partial matching or hypothesize-and-test must be used.

functional need |
To reason when some relevant information is inaccessible |

available incomplete information |
The inaccessible information |

reasons available information is incomplete |
There is no way to access the information |

uncertain information |
Whether having the missing information would significantly change the interpretation |

assumptions useful for handling the problem
that could be made through default reasoning |
Assumptions about what is missing |

Sometimes one can identify possible outcomes, but lacks control or information to assume a specific outcome -- probability or relative frequency of occurrence may be used.

functional need |
To reason about situations involving random chance |

available incomplete information |
Precise probabilities may not be known for all cases |

reasons available information is incomplete |
A great many point estimates may be required and there may be insufficient experience with similar cases. |

uncertain information |
Whether the probabilities are accurate. |

assumptions useful for handling the problem
that could be made through default reasoning |
Probability distributions are set by default to the degree that the precise probabilities are unknown. |

functional need |
To reason from data that supports multiple interpretations |

available incomplete information |
Additional context that would clarify interpretations |

reasons available information is incomplete |
The additional context is not available |

uncertain information |
Which interpretation applies |

assumptions useful for handling the problem
that could be made through default reasoning |
The interpretation that best fits the rest of the context |

**Conventions of Human Communication**

Defaults are central to efficient communication.

**The Closed World Assumption**

Default reasoning is called for when it is reasonable to assume that one has all relevant knowledge about a subject, that is, one assumes it must not be true or I would know about it.

functional need |
To derive conclusions based on the absence of information that would have been present if the opposite conclusion were true. |

available incomplete information |
That which would directly support the conclusion |

reasons available information is incomplete |
One can only possess a finite amount of information and the problem may not have come up for consideration before. |

uncertain information |
Whether one would indeed know if the opposite were true. |

assumptions useful for handling the problem
that could be made through default reasoning |
Given that one would know if the proposition were true, assume that if one does not know that it is true, then it is false. |

**Correlation of Objects**

Once an object is identified, one mentally correlates subsequent perceptions of a same object and matches patterns.

functional need |
To correlate different perceptions of the same object. |

available incomplete information |
The full set of object attributes for the two perceptions and the occurrence within the time interval between perceptions. |

reasons available information is incomplete |
An object cannot be perceived with complete precision nor kept under constant perception, and some of its attributes may change. |

uncertain information |
Whether the two perceptions are of the same object |

assumptions useful for handling the problem
that could be made through default reasoning |
Given that a new perception matches the expected perception of a known object, the new perception is of the known object. |

**Imprecise Information**

functional need |
To draw conclusions from imprecise information |

available incomplete information |
The lack of precision corresponds to lack of information |

reasons available information is incomplete |
Precise measurements are unavailable or unnecessary. |

uncertain information |
What is the precise information |

assumptions useful for handling the problem
that could be made through default reasoning |
The measure is precise as reported, or the worst-case error has occurred, depending on the situation. |

**Degree of Involvement**

functional need |
To make conclusions based on the degree of involvement. |

available incomplete information |
The precise degree of involvement and the precise relationships between different types of involvement. |

reasons available information is incomplete |
Precise measurements may be unavailable, ranges of involvement may be only roughly defined, and the correlation between different types of involvement may be low or based on imprecise data. |

uncertain information |
The actual degree of involvement and relationship between different types of involvement |

assumptions useful for handling the problem
that could be made through default reasoning |
Simple functions that represent degree of involvement and combination methods that draw meaningful conclusions. |

**Inconsistent Information**

functional need |
To resolve apparent inconsistencies that arise. |

available incomplete information |
The knowledge that some of what is thought to be true is actually false. |

reasons available information is incomplete |
Effort, assumption, or deception. |

uncertain information |
Which, if any, of the inconsistent alternatives is correct. |

assumptions useful for handling the problem
that could be made through default reasoning |
The information that appears to be inconsistent should be treated as an assumption. |

**III Parametric, Symbolic, and Higher-Order Reasoning**

A practical reasoning system must perform parametric, symbolic and higher order reasoning, and involves some form of variables and formulas.

In *parametric* models (propositional
logic, integer linear programming, fuzzy set theory, Bayesian probability,
Pearl's causal networks, statistical classifiers, neural networks, logic
circuits...), variables have domain numbers or truth values.

- parameters and formulas must be predefined because there is no mechanism
for defining new parameters or formulas
- meanings of parameters are inaccessible because they are merely tokens
related through formulas
- the parametric systems are nondeterministic-polynomial complete

*Symbolic* reasoning differs from parametric reasoning in that
it...

- makes the meaning of the propositions accessible
- supports an open-ended, inductive definition of a model because it allows
quantified variables for the terms in atomic formulas
- a mechanism to make default conclusions based on reasonable assumptions, given that the assumptions do not contradict other information
- The reasoning process must be nonmonotonic since the default conclusions are not strictly sound and may be found to be inconsistent with later information and be retracted
- when conclusions are withdrawn or changed it is necessary to maintain or readjust the truth of other related conclusions accordingly
- default reasoning can give multiple extensions or solutions when different combinations of feasible defaults exist, so it is necessary to order the extensions to identify the preferred solutions
- Logic based reasoning in ideal worlds is badly combinatorial and not decidable.
- Default reasoning for real world situations exacerbates the problem -- there is no algorithm guaranteed to stop and give a correct answer.
- Other logic based approaches become intractable through the explosive number of alternatives that can be encountered.
- Measure based approaches have limited practicality because of problems of statistical independence and are typically propositional.
- Practical reasoning systems must use higher-order variables, which is nonsemidecidable.
- serial -- maintain one current extension with true/false belief allocation and provision for backtracking. Similar to depth first search. Very efficient if can avoid backtracking.
- spatial -- spawn extensions as knowledge representations that coexist in memory, with true/false belief allocations. Supports breadth first or A* searches. Memory intensive and can duplicate conclusions in different extensions.
- conditional -- maintain one representation that concurrently represents all extensions by labeling each piece of knowledge with a set of enabling or disabling conditions, using true/false belief allocation. Effect is using one particular set of accepted assumptions as a filter for propositions. Used in Assumption-based Truth Maintenance Systems.
- overlay -- maintains one representations but distributes partial belief so that the representation is a weighted overlay of the different extensions. This avoids combinatorial multiplication of extensions, but muddles the extensions together into one.
- Most real world reasoning involves imperfect information, so defaults in the reasoning process are required to allow a human or system to make inferences and reach conclusions.
- Thirteen cases involving imperfect information are described
**The Qualification Problem**- It is unreasonable (and increasingly macabre) to provide all possible preconditions.
**The Frame Problem**- We should be able to assume conditions are consistent unless explicitly changed.
**Time Constraints**- Often choices need to be made before all relevant information can be processed.
**Diminishing Returns**- The time and effort expended on making a decision must be weighed against the advantage of making it.
**Unavailable or Inaccessible Information**- Sometimes information is just not available (occlusion)
**Random Choice**- Possible outcomes may be identified with no certainty of specific outcome, in which case we often consider probability or frequency
**Ambiguity and Equivocality**- Data may support several interpretations ('The astronomer looked at the star.')
**Conventions of Human Communication**- Human communication is full of implicit information, and the conventions for figuring out what is implicit must be known.
**Closed World Assumption**- We should be able to assume that we know all the relevant information, that a proposition is false unless we know it to be true.
**Correlation of Objects**- It is useful to assume that if we see an object that looks exactly like object A, and is in the same position as object A was when last we saw it, it is object A.
**Imprecise Information**- When information is imprecise, we will sometimes assume minimum and sometimes maximum error, depending on the situation
**Degree of Involvement**- We may need to make judgements about imprecise or ambiguous information based on degree of involvement ('There are many enemy troops.' is unclear until we know what the usual scale is).
**Inconsistent Information**- Several inconsistent alternatives may arise, and we must treat them as assumptions rather than facts.
- A practical reasoning system must perform
**parametric reasoning**- parameters and formulas must be predefined because there is no mechanism for defining new parameters or formulas
- meanings of parameters are inaccessible because they are merely tokens related through formulas
- NP complete
**symbolic reasoning**- makes the meaning of the propositions accessible
- supports an open-ended, inductive definition of a model because it allows quantified variables for the terms in atomic formulas
- necessary for most real world reasoning.
- includes parametric reasoning as a special case -- once ground atomic formulas are instantiated, an essentially parametric solution process must determine the truth values.
- Although reasoning with symbolic variables allows for a compact knowledge representation that can deal with new objects, it exacerbates the search problem.
**higher order reasoning**- First order symbolic reasoning can be extended so that predicate and function symbols are represented by quantified variables.
- Default reasoning requires
- A mechanism for making default conclusions based on reasonable assumptions, as long as the assumptions do not contradict other information.
- The reasoning process must be nonmonotonic since the default conclusions are not strictly sound and may be found to be inconsistent with later information and be retracted.
- When conclusions are withdrawn or changed, we need to be able to readjust the truth of other related conclusions accordingly
- Default reasoning can give multiple extensions or solutions when different combinations of feasible defaults exist, so it is necessary to order the extensions to identify the preferred solutions
- Characteristic features of default reasoning systems
- How they allocate belief across several alternative extensions.
- How they distinguish belief due to different extensions
- Representations of extensions:
- serial -- follow one extension at a time and backtrack (DepthFS). Efficient if you don't end up having to backtrack
- spatial -- have different extensions coexist (BreadthFS). Memory expensive.
- conditional -- use one particular set of accepted assumptions as a filter for propositions. Used in Assumption-based Truth Maintenance Systems.
- overlay -- maintain one representations with distributed partial belief so that it is a weighted overlay of the different extensions. Avoids combinatorial multiplication of extensions, but muddles the extensions together into one.
- How they balance the efficiency driven need for modular inference with the need for semantic cohesiveness. In modular inference, the antecedents of a production rule are true, the consequents can be asserted independently of the rest of the context. This leads to efficient reasoning, but is only valid when the rules are perfectly complete and accurate. Default rules require determining consistency, so default rules cannot be applied on a modular basis.

Symbolic reasoning includes parametric reasoning as a special case. Once ground atomic formulas are instantiated, an essentially parametric solution process must determine the truth values.

Although reasoning with symbolic variables allows for a compact knowledge representation that can deal with new objects, it exacerbates the search problem. Symbolic reasoning is essential for real-world applications because new objects are routinely encountered, and the relationships among them must be determined. Parametric systems have an implicit, limited ability to reason with symbolic variables one at a time. Symbolic reasoning deals with combinations of symbolic variables, and focuses on combinations of objects, providing an arbitrary degree of modularity. A parametric system can be augmented with feedback and nonmonotonicity to exhibit sequential reasoning like a Turing machine; but this voids the declarative nature of parametric models, negating the source of their power.

**Higher Order Reasoning**

First order symbolic reasoning can be extended so that predicate and function symbols are represented by quantified variables. Learning symbolic information, versus parameterization, calls for reasoning with higher order variables because it deals abstractly with new or unspecified rules or formulas and their constituents. Higher order reasoning requires both first-order symbolic reasoning and parametric reasoning.

**IV. Requirements for Default Reasoning**

Default reasoning requires...

**Default Conclusions**

It is important to be able to make conclusions based on reasonable assumptions and the absence of information to the contrary, even when these may not be strictly logically sound. The rule applies unless there is other information that contradicts the conclusion.

**Nonmonoticity**

The system must have the ability to retract or reverse a conclusion in light of further information. In a monotonic system, only two transitions are legal for the evidence and for the conclusions -- from unknown to true or unknown to false. In a nonmonotonic system, the systems knowledge of evidence is still limited to these two transitions, but the system's knowledge of conclusions is unconstrained.

Many measure-based approaches require a full set of input data in which only the values vary. The concept of further evidence can be best interpreted as later adjustments away from independent, a priori, values for the evidence. A measure-based system is nonmonotonic if it has a mechanism to adapt to, rather than start anew with, further evidence.

**Truth Maintenance**

When initial default conclusions are later defeated, it is necessary to readjust the rest of the context accordingly. This is usually implemented through dependency-directed backtracking, or labeling each proposition with truth value and conditions for and against it.

**Ordering of Extensions**

Practical performance in real-world situations relies on numerous assumptions,
and sometimes multiple conflicting combinations of assumptions can apply. In
general, the number of feasible extensions can be exponential in the number of
default conclusions, so we must have some method to prefer more likely or
better supported extensions. A default reasoning system generates an
*anomolous extension* if extra extensions are generated in the reasoning
process that run counter to normal or common sense expectations.

**Practicability**

A reasoning system for real world problems should be practicable.

**V. Characteristic Features of Default Reasoning Models**

One feature of the various models of default reasoning is the way they allocate belief, a second is how they distinguish belief due to different extensions, and a third is how they balance the efficiency driven need for modular inference with the need for semantic cohesiveness.

**Allocation of Belief to Propositions**

Logic based approaches typically work on true/false data and commit to conclusions being true or false. In measure based approaches, the inference mechanism portions belief over propositions.

**Representations of Extensions**

Nonmonotonic reasoning can lead to exploration of multiple extensions, which can be represented four ways...

Spatial and conditional approaches maintain multiple extension, so they are good for heuristic search and hypothesize-and-test reasoning. Serial, spatial and conditional separate extensions, which can lead to explosive search. Overlay approaches may be unable to identify the best choices in combination.

**Modularity Versus Cohesiveness**

In modular inference, the antecedents of a production rule are true, the consequents can be asserted independently of the rest of the context (extensional systems). This leads to efficient reasoning, but is only valid when the rules are perfectly complete and accurate. Default rules requires determining consistency, so default rules cannot be applied on a modular basis.

**VI Comparison of Default Reasoning Models**

Three tables are given comparing selected reasoning systems/models on Domains, Satisfaction of Requirements, and Characteristic Features.

Automatic Reasoning

*An Overview of Automated Reasoning*

Stephen Post and Andrew P. Sage

__IEEE Transactions on Systems, Man, and Cybernetics
__

__
__Vol 20 No 1, pp 202-224, Jan/Feb 1990

TK 6540 .I48 SMC SMC-20 Jan-Jun 1990