An Overview of Automated Reasoning

Stephen Post and Andrew P Sage

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.

I. Introduction

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.

functional need To project states over time frames

available incomplete information the states and events within the time frames.

reasons available information is incomplete
Only the present instant can be perceived, and that only partially. Also, one can remember the past nor predict the future in full and accurate detail

uncertain information Whether unusual or unanticipated conditions will arise

assumptions useful for handling the problem that could be made through default reasoning Conditions will hold over from a given time frame unless directly affected by some unknown event.

Time Constraints

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.

Diminishing Returns

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.

functional need
To balance the cost of reasoning against the return

available incomplete information The information and conclusions that were not pursued, and the actual versus expected costs and returns.

reasons available information is incomplete Additional data collection or reasoning was not deemed worth the effort

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 assumptions for which the expected cost of additional perception and deduction exceeds the expected return from doing so.

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

Random Choice

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.

Ambiguity and Equivocality

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.

functional need To communicate efficiently

available incomplete information That which was implicit

reasons available information is incomplete The communication was formulated according to conventions that support the transfer of information based on what was said and what was not said.

uncertain information
How closely the speaker is following the conventions and whether the communicants share the same assumptions.

assumptions useful for handling the problem that could be made through default reasoning The speaker is conveying true, relevant information that is in appropriate detail and should be able to be plainly understood.

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.

Parametric Reasoning

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

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

It is necessary for most real world reasoning.

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...

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

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.

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.

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...

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.

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.

Quick Notes

Automatic Reasoning

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.

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

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.

functional need	To project states over time frames
available incomplete information	the states and events within the time frames.
reasons available information is incomplete	Only the present instant can be perceived, and that only partially. Also, one can remember the past nor predict the future in full and accurate detail
uncertain information	Whether unusual or unanticipated conditions will arise
assumptions useful for handling the problem that could be made through default reasoning	Conditions will hold over from a given time frame unless directly affected by some unknown event.

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.

functional need	To balance the cost of reasoning against the return
available incomplete information	The information and conclusions that were not pursued, and the actual versus expected costs and returns.
reasons available information is incomplete	Additional data collection or reasoning was not deemed worth the effort
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 assumptions for which the expected cost of additional perception and deduction exceeds the expected return from doing so.

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

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

functional need	To communicate efficiently
available incomplete information	That which was implicit
reasons available information is incomplete	The communication was formulated according to conventions that support the transfer of information based on what was said and what was not said.
uncertain information	How closely the speaker is following the conventions and whether the communicants share the same assumptions.
assumptions useful for handling the problem that could be made through default reasoning	The speaker is conveying true, relevant information that is in appropriate detail and should be able to be plainly understood.

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.

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.

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.

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.

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.