Implementation of and Experiments with a Variable Precision Logic Inference System, P Haddawy

Tags: certainty, system, Shafer, inference rules, numerical parameters, censor, current system, Uncertain inference, rule base, inference engine, backward chaining, Dempster-Shafer theory, system searches, inference system
Content: From: AAAI-86 Proceedings. Copyright ©1986, AAAI (www.aaai.org). All rights reserved.
IMPLEMENTATION
OF AND EXPERIMENTS WITH
A VARIABLE PRECISION LOGIC INFERENCE SYSTEM*
Peter Haddawy Intelligent Systems Group Department of Computer Science University of Illinois Urbana, Illinois 61801
ABSTRACT
A system capable of performing
approximate inferences under time constraints is
presented. Censored production rules are used
to represent both domain and control informa-
tion. These are given a probabilistic semantics
and reasoning is performed using a scheme
based on Dempster-Shafer
theory. Examples
show the naturalness of the representation
and
the flexibility of the system. Suggestions for
further research are offered.
I INTRODUCTION
It is a Sunday afternoon and your fully autonomous car is taking you for a drive. Suddenly a truck pulls out into the road ahead of you. Your car has 5 seconds to decide what to do. If your car were powered by current reasoning technology, chances are it would never reach a decision because while trying to determine the best course of action it would hit the truck, destroying both itself and you. In this situation any decision, even a rough guess, is better than indecision. What is needed is a system capable of producing the best decision possible within a given time limit.
Certainty refers to the degree of belief in a
statement, while specificity refers to the degree
of detail of a description. The idea of a logic in
which the certainty of an inference could be
varied to conform to cost constraints
was
presented by Michalski and Winston [1985].
This Variable Precision Logic (VPL) used cen-
sored production rules to encode both domain
and control information.
The rules take the
form
P->D[C read If P then D unless C.
The unless part of the rule is called the censor.
Censors represent exception conditions and as
such are considered to be false most of the time.
Therefore, the determination
of their truth
values is given a lower priority than that of rule
antecedents.
Whereas unlimited resources are
devoted to checking the antecedents, only a lim-
ited amount of resources is devoted to checking
the censors in time critical situations.
The
unless symbol is logically interpreted as an
exclusive-or operator between the censor and
the consequent. Thus, given the rule
Sunday -> Go to the park 1 Weather is bad,
In any practical reasoning process
there are extra-logical
cost constraints such as
time and resource limitations which must be
taken into account. The tradeoff between the
cost, certainty, and specificity of inferences can
be used to flexibly adjust to these constraints.
* Th'IS work was supported in part by the Defense Advanced
research project Agency under grant N00014-K-85-0878,
in part
by the National Science Foundation under grant NSF DCR 84-
06801, and in part by the Office of Naval Research under grant
N00014-82-K-0186.
we can conclude that if it is Sunday and the weather is good, I will go to the park; and if it is Sunday and the weather is bad, I will not go to the park. Formally, P,AP,A * - * +D [C,vC,v - - . is logically interpreted as P,AP,A - - - A-( C,vC,v...)--+D and P,AP,A ''- A(C,VC,V...)--D
238 / SCIENCE
In order to make the exceptions quantitative, numerical parameters are associated with each rule, representing the strength of inference when the truth value of the censor is known and when the value is unknown. These values allow the precision of inferences to be varied.
This paper presents a formalization
of the notion of uncertainty in censored produc-
tion rules and an implementation
of an inference
system capable of varying the certainty of infer-
ences to conform to given time limits.
These values are constrained restrictions:
by the following
When the value of the censor Shafer interval for the conclusion according to
is known, the D is computed
s(D) = @`)[l - p(C)Io p(D) = 1 - s(P)s(C)@
II FORMALISM AND THEORY
Uncertain inference in the VPL sys-
tem is performed using a scheme based on
Dempster-Shafer
theory [Shafer 19761. Domain
information is represented in the form of rules
and facts. A fact is assigned a certainty
represented by a Shafer interval, [s p]. The s
value indicates the support for a proposition,
while the p value indicates its plausibility. The
intervals for A & 1A are related by p(A) = 1 -
$(-IA). The s and p values can also be thought of
as the minimum and maximum probabilities of
the proposition. The amount of uncertainty in a
proposition is defined as the difference of the
values. A value of `unknown' is represented as
the interval [0 l]. Th e value of a conjunction or
disjunction of facts is calculated by applying the
formulas for probabilistic
product or sum
respectively
to the support and plausibility
values separately.
Rules are interpreted as expressing
conditional probabilities.
Beliefs are propogated
across the rules using an approach similar to that employed by Ginsberg [1984] and derived
by Dubois & Prade [1985]. Suppose we have the rule A -> B, where prob(l3~A)~[S,P,] and
prob(A)EISAPA]. Th en it can be shown that
prob(B) E [S,S,, I--s,+S,P,].
Now
if
prob(d3 / A)E[S,P,] th en P, = l-S, from which
it follows that prob(B)EISAS,, l-S,,%]. To use
this scheme, the certainty
of a rule is
represented by four values: Q p 7 S, where
a=S,forPAlC->D
p=S;forPAC->lD
7= S, for P -> D
s=S;forP->
YD
When the censor value is unknown, the formulas are s(D) = s(P)a p(D) = 1 - s(P)/3.
Evidence for multiply argued conclusions is combined using Dempster's orthogonal sum rule. This requires the assumption that the evidence events are conditionally independent. The formula used to combine two Shafer intervals is similar to that in [Ginsberg 19841:
[u b]@[c d] =
--
l-
"_"
I-(ad+bc)
bd l-(ad+bc)
1
The above discussion has presented
an approximate inference scheme for proposi-
tional logic, but the VPL system uses a typed
predicate logic representation.
The type infor-
mation enumerates the elements of a finite
domain for each predicate argument. In this
representation,
terms containing only
instances are equivalent to propositional
and thus present no additional problems.
ground logic How-
ever, a semantics for expressions with free vari-
ables is needed. Rules of the form A(x,y) ->
B(x), with an associated certainty [s p] are inter-
preted as Vx,y p(B(x)lA(x,y)) = [s p]. This is
essentially a short-hand for listing rules over the entire domain of x and y. Similarly, a fact A(x)
with certainty [s p] is interpreted as Vx p(A(x))
= Is PI.
Uncertainty and expert systems: automated reasoning / 239
III SYSTEM OVERVIEW
The VPL system consists of six main components: the user interface, the parser, the knowledge base, the unifier, the inference engine, and the rule-base analyzer. The system is implemented in Common Lisp and runs on a Symbolics 3640.
The system is designed to be fully interactive for incremental rule base development. The user may assert or retract rules and facts, define new types and predicates, and make queries. Once a rule base is complete, the user may perform an analysis of inference times. The rule-base analyzer determines for each possible query the inference time required for all uniform depths of censor chaining. A censor chain is a rule chain in the search tree leading from a censor. A list of times with associated depths for each query is stored in the time data base.
A user query may have an optional
time limit associated with it, in which case the
system searches the time data base to determine
the maximum censor chaining depth which will
guarantee a response in the requried time. If no
time limit is specified, chaining depth is unlim-
ited. The system performs backward chaining
inference, with possibly limited search depth on
censors. Inference is performed in two stages:
search and calculation.
The search strategy is
breadth first and exhaustive.
The exhaustive
search is achieved by generating all consistent
ground instances of any free variables after
unification.
To satisfy a goal, the system
searches for a fact which unifies with the goal.
If none is found, it tries to find rules which unify
with the goal. If both of these attempts fail, the
query is given a value of [0 11. During the
search process, instructions for performing the
certainty calculations are put on a calculation
stack. When the search terminates, the entries
on the calculation stack are evaluated and put
on a value list. The computation on the bottom
of the stack corresponds to the user query.
I-V EXAMPLES
approximate
inference methods. The idea is
that a bird can fly unless it is a special kind of
bird such as a penguin or is in an unusual condi-
tion such as dead. The input file shows domain
type declarations, followed by predicate declara-
tions, followed by rules.
Following the input file is a log of some example runs. After the rules are loaded, the system is told that tweety is a dead bird, from which it concludes that tweety cannot fly. Next, changing our certainty in tweety's death changes the certainty in his ability to fly proportionately. When the system is told that tweety may be a kiwi, this information combines with the possibility of his death to further decrease our belief in his ability to fly. Finally, if tweety is neither in an unusual condition nor a special bird, he is able to fly.
type (animal (spot rover jane tweety (bird (tweety road-runner))
road-runner))
pred
(is-bird (animal))
(flies (animal))
(is-special-bird
(bird))
(is-in-unusual-condition
(animal))
(is-penguin (bird))
(is-ostrich (bird))
(is-emu (bird))
(is-kiwi (bird))
(is-domestic-turkey
(bird))
(is-dead (animal))
(is-sick (animal))
(has-broken-wing
(bird))
assert
((is-bird 8x) => (flies 8x)
1 (is-special-bird
8x)
(is-in-unusual-condition
8x) 1.0 1.0 .9 .05)
((is-dead $x) = > (is-in-unusual-condition
$x) 1.0 0.0)
((is-sick $x) = > (is-in-unusual-condition
8x) 0.9 0.06)
This section presents two simple examples to demonstrate the system's capabilities. The first is intended to highlight the
((has-broken-wing
$x) = >
(is-in-unusual-condition
8x) 1.0 0.0)
240 / SCIENCE
((is-penguin 8x) => (is-special-bird
8x) 1.0 0)
((is-ostrich $x) => (is-special-bird
$x) 1.0 0)
((is-emu $x) = > (is-special-bird
8x) 1.0 0)
((is-kiwi $x) => (is-special-bird
tf;x) 1.0 0)
((is-domestic-turkey
$x) = >
(is-special-bird
$x) 1.0 0)
Example Runs
-- Tweety is a dead bird --- ENTER Command > assert ENTER Command or assertion > ((is-bird tweety) 1 1) ENTER Command or assertion > ((is-dead tweety) 1 1) ENTER Command or assertion
0.027635619 seconds elapsed time

[l.OO 1.001
The next example is the one
described in the introduction. It shows the abil-
ity of the system to vary the depth of censor
chaining in response to time limits. The input
file shows rules for determining if a car can stop
in time to avoid an obstacle based on the condi-
tion of its brakes and the road. A log of the
sample run shows the effect of varying the time limit. With a censor chaining depth of 1 or less
the system cannot determine the truth values of
the road-condition
censor and thus uses the
more approximate version of the rule.
ENTER Command or make query of system > (flies tweety) using censor chaining depth of UNLIMITED 0.103377685 seconds elapsed time

[O.OO 0.001
-- reduce certainty in Tweety's death - ENTER Command or make query of system > (assert ((is-dead tweety) .7 .8)) ENTER Command or assertion > (? (flies tweety)) using censor chaining depth of UNLIMITED 0.1013306 seconds elapsed time

[O.OO 0.3Oj
--- suspect that Tweety is a kiwi --- ENTER Command or make query of system > (assert ((is-kiwi tweety) .3 .5)) ENTER Command or assertion > (? (flies tweety)) using censor chaining depth of UNLIMITED 0.10849539 seconds elapsed time

[O.OO 0.211
--- Tweety is healthy and normal --
ENTER Command or make query of system
> (assert (( is - in - unusual-condition
tweety) 0 0))
ENTER Command or assertion
> ((I is-special-bird
tweety) 1 1)
ENTER Command or assertion
> (? (flies tweety))
using censor chaining depth of UNLIMITED
We (level (low medium high)) (rating (good fair poor)) (substance (gravel ice)) (place (road ground)) (temp-type (below-freezing (looks (shiny rough))
moderate hot))
pred
(speed-distance-ratio
(level))
(can-stop-in-time())
(road-condition
(rating))
(brake-condition
(rating))
(on (substance place))
(temperature (temp-type))
(road-appearance
(looks))
(construction-site
0)
(sound-of-pebbles-hitting-underside-of-car
0)
assert
; rules
( (- speed-distance-ratio
high) =>
(can-stop-in-time)
1 (road-condition
poor)
(brake-condition
poor) 1.0 1.0 .85 .l)
( (on ice road) = > (road-condition
poor) 1.0 0)
( (on gravel road) => (road-condition
poor) .9 .l)
( (temperature below-freezing)
(road-appearance
shiny) = > (on ice road) .9 .I)
( (construction-site) (sound-of-nebbles-hitting-underside-of-car1
Uncertainty and Expert Systems: AUTOMATED REASONING / 24 1
=> (on gravel road) .9 .l)
systems for operating rooms to domestic robots.
; facts
((speed-distance-ratio
high) .05 .15)
((temperature below-freezing) .2 .3)
((road-appearance
shiny) 0 0)
((construction-site)
1.0 1.0)
((sound-of-pebbles-hitting-underside-of-car)
.8 .85)
Example Runs
--- time limit of 1 second --
ENTER Command or input file
> (? ((can-stop-in-time)
1))
using censor chaining depth of 2
0.08085977 seconds elapsed time
In the current system, if the value of a rule's censor is known, the a! and /3 certainty values are used. If the value is unknown, the 7 and 6 values are used. A better approach would be to look at the degree to which the censor value is known and use this to interpolate between the o & p and 7 & S rule certainty values.
Much world knowledge
is best
expressed in the form of taxonomies. Taxo-
nomies carry more information than simple col-
lections of rules. To make the system more
effective, I am working on incorporating special-
ized inference rules for reasoning in taxonomies.
[O.OO 0.451
--- time = .05 second ---
ENTER Command or make query
> (? ((can-stop-in-time)
.05))
using censor chaining depth of 1
0.031729784 seconds elapsed time
of system
[0.72 0.921
- time = .03 second ---
ENTER Command or make query
> (? ((can-stop-in-time)
.03))
using censor chaining depth of 0
0.017470836 seconds elapsed time
of system
This paper has only investigated the trade-off between inference time and certainty. The trade-offs between cost and specificity and certainty and specificity need yet to be explored. This is a direction in which the results of machine learning research hold much promise. ACKNOWLEDGEMENTS I would like to thank Prof. Michalski for his guidance, Lisa Wolf for comments on a draft of this paper, and John Wiegand and Jim Kelly for help on an earlier implementation. REFERENCES

[0.72 0.921
--- time limit too low ---
ENTER Command or make query of system
> (? ((can-stop-in-time)
.Ol))
Cannot perform inference in requested time.
Minimum guaranteed time is 0.018423745 set
Dubois, D., Prade, H. "Combination and Propogation of Uncertainty with Belief Fuctions" In Proc. IJCAI-85. LOS ANGELES, California, August, 1985, pp. 111-113.
Ginsberg, M.L. "Non-monotonic
Reasoning
Using Dempster's Rule" In Proc. AAAI-84.
Austin, Texas, August, 1984, pp. 126-129.
V CONCLUSIONS It has been shown that the formalism of censored production rules when given a probabilistic semantics allows a system to adjust the certainty of inferences to conform to time constraints. Such a system has numerous applications in situations where decisions must be made in real time and with uncertain information. Examples range from medical expert
Michalski, R.S., Winston,P.H., "Variable Precision Logic" MIT AI Memo 857, Artificial Intelligence Laboratory, MIT, August, 1985 (accepted for AI Journal, 1986). Shafer, G. A mathematical theory of Evidence. Princeton University Press, Princeton, New Jersey, 1976.
242 / SCIENCE

P Haddawy

File: implementation-of-and-experiments-with-a-variable-precision-logic.pdf
Title: 1986 - Implementation of and Experiments with a Variable Precision Logic Inference System
Author: P Haddawy
Author: Haddawy, Peter
Subject: Science;Uncertainty and Expert Systems;1986 AAAI Proceedings
Published: Sun Aug 1 13:47:09 1999
Pages: 5
File size: 0.51 Mb


Midnight Clear, 13 pages, 0.45 Mb

, pages, 0 Mb

The Ancient Jewish Wedding, 22 pages, 0.41 Mb

, pages, 0 Mb
Copyright © 2018 doc.uments.com