Reasoning About Control: The Investigation of an Evidential Approach
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Expert Systems. Pages 203-205.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
The cor nplexit .y o f the domains in which expert systems are exfWctrd to op<>rate re quires that they be capable of "reasoning" about t IH"ir :l<·tions. It ha s been argued th:-.t expert systems must reason fr n nr •' ridrnr ia/ info rmation - i.e., uncertain, incomplete, and occasionallv inarcuratc inf o rmation !LOW82aJ. As a consequence , a model for re' " '' ning a bo ut co ntr o l mu st d eal with several problems - being able to o rgani ze "c ontrol-related " evidential information that is generically dis ti!lrt and ·fr o m dis parate so urces , to overcome minor errors in the rv id •· nti:1l inform at ion need ed to reach a deci sion , and to explain the ar t inn s taken by the system. These are a few of some formidable control i"' ue s and problems that remain largely un so lved JBAH82J . Thus , w<· re port 0 11 a n investigation into how t.hese iss ues and problems can be :1d dr e,;se cl when th e problem of reasoning about system control is vi<·w ed as an <·vid c ntial process.
- JU AH82 j Barnett, .J .A., "Some Issues of Control in Expert Sy stems," Proc . International Conference on Cybernetics and Society, October I 982, pp. 1-5.
- JDEMG7j Dempster , A. P ., "Upper and lower probabilities induced by a multivalucd mapping," Annals of Mathematical Statistics, 38, 1967, pp . 32[>-339.
- jD EI\1G8J Dempster , A.P. , "A generalization of Bayesian in- feren ce," Journal of th e Royal Statistical Society, Series B, 30, 1968, pp . 205-247.
- jLOW82aj Lowran ce, J.D. and T .D . Garvey , "Evidential Reaso ning : A Developing Concept," Proc . International Conference on Cybern etics and Society , October 1982, pp. 6-9.
- e A more complete discussion of an evidential-based approach to ad- dressing these and other problems can be found in IWES83J. JLO\VS:!bJ Lowr ance, J .D. , "Dependency-Graph Models of Evid enti a l Support ," Ph.D. dissertation , Department of Computer a nd Inform a tion Sc ience , University of Massachusetts, Amherst , MA, Se pt ember l 982.
- JSIIA7GJ Shafer , G. , A Mathematical Theory of Evidence, Prin ce ton University Press , Princeton, New Jersey , 1976.
- JWES83J Wes ley , L.P ., "Reasoning About Control: An Evidential Approach," SRI International technical report in preparation .
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
ABSTRACT
The cornplexit.y of the domains in which expert systems are ex fWctrd to op<>rate requires that they be capable of "reasoning" about t IH"ir :l<·tions. It has been argued th:-.t expert systems must reason frnnr ·'ridrnr ia/ information - i.e., uncertain, incomplete, and occasion allv inarcuratc information !LOW82aJ. As a consequence, a model for re'"''ning about control must deal with several problems - being able to organi ze "control-related" evidential information that is generically dis ti!lrt and ·from disparate sources , to overcome minor errors in the rv id··nti:1l informat ion needed to reach a decision , and to explain the ar t inns taken by the system. These are a few of some formidable con trol i"'ues and problems that remain largely unsolved JBAH82J . Thus, w<· report 011 an investigation into how t.hese issues and problems can be :1ddre,;secl when the problem of reasoning about system control is vi<·wed as an <·vidcntial process.
INTRODUCTION
Exp<"l sys tems t hat operate in complex domains are continually confronted with th<· problem of deciding what to do next . Furthermore , ouch systems nrust "re:1son" about their alternatives and choose an ac tion on the ln., is of uncertain, incomplete, and inaccurate information , r :1 ll<'d rvidcn ti:tl information !LOW82aJ. For instance, the decision to t:1ke" p:1rti r ular action can be influenced by the expected outcome of t:1 ki11g th:~t :1dinn. However. situations may arise in which uncertainty rxi,ls about the consr<Juences of taking any action , particularly when un rontroll:~ble nr unpredictable events may intervene. Resource limita tions, for ex:unple. might not permit gathering all relevant facts , thus forcing dcc i, ions to be made with incomplete information . Finally , it must be anticipated that the information supplied to the system may be inaccurat e because, among other reasons , the sources or the infor m:ltion are iri1perfec t . We , as well as the systems we build , must be capable of choosing an action on the basis of evidential information .
-----------· -----------
·Ttris research was supported , in part , by the Defense Advanced R<·se:u ch Projects Agency (DAHPA) under contract number N000148 1-C-0115 . The views and conclusions contained in this document are tho>e o f the aut.hor and should not be interpreted as representing the offi cial policies, either expressed or implied , of SRI International, D.\Rl'A, or the U.S. Government .
.. The :>uthor is currently enrolled in the department of Computer and Informa tion Sc i<·nce (COINS), University of Massachusetts, Amherst, M!\ 01003.
REASONING ABOUT CONTROL: THE INVESTIGATION OF AN EVIDENTIAL APPROACH ·
Leonard P. Wesley ··
Artificial Intelligence Center SRI International Menlo Park , CA 94025
Ther<'l'orc, the on-going research reported here is concerned with some probl<'ms that must be dealt with berore such capabilities can be real ized .
Some Control Problems
TypiCCtl!y the information needed to choose between alternatives is obt:l in i'<l from multiple sources and varies in both the type and the unit of me:.surrmcnt . For example, costs and goalsfsubgoals are two distinct t)' pes of information. One source might talk about costs in terrm of CPU cycles, and another distinct source might talk about costs in terms of the degradation of the system's ability to complete it;, task. A problem of interest is how can generically distinct types of information be combined to obtain a wnsensus of opinions, from disp:u:1tc sourees, about the appropriate action to take?
A "'ronrl problem is that the information that is required to choose l)('twc<·n :litrrnatives may contain minor errors. No system can always mc;:sure accurately the costs of taking an action or determine precisely tho go:tls/ subgo:t ls that should be satisfied. Yet we require that expert syst.enrs br robus t enough to make effective decisions despite sucb er rors. Wh:lt mech:tnisms can be employed to correct for minor errors?
It is impnrt01nt that expert systems be able to explain their actions. So mel inws deci, ions are based on information that tends to support th·>Sc JHopo,i· ion:; in favor of choosing a particular action , tends to rc fut~ t.hos<' propositions in competition with the action taken, or both (i .e., tonflict ing inform:ltion). At other times an action is taken because t. h<· oys t em i .~ partially ignorant about some aspect. of the information requir<·d t.o reach any decision. In short., to explain its decisions, a sys tem must hr able to distinguish among evidence that tends to support., tends to refute , and neither supports nor refutes the propositions of irrtNrst. What is an adequate representation of the total evidential infornr :l tion, as it bears on the propositions of interest, that will allow systems to provide rnore meaningful and accurate expbnations or their actions?
ACTIONS, CONTROL-FEATURE SPACES, AND A CONTROL ENVIRONI\IENT
We ron<idcr an action to be the invocation of a parameterized JHOC<·ss, such as a knowledge source (KS), where a KS is a procedure or senso r r hat. m:1kcs observations about the environment or the invocation of processes for obtaining additional information that is required to chon~e :-tn act ion .
Solcctirrg the appropriat.e action depends on the observation of fea tures in :tn environment . Just as spectral attributes can be considered features or object.s, so can goalsfsubgoals be features of actions. If ob jects can be partially discerned frorri information about what spectral feat ur<!S a re obse rved , then the appropriate actions can be partially disc:rrned from information about which goals/subgoals need to be satisfied.
Examples of control-feature spaces are goals/subgoals, costs as sociated with invoking various KSs, the reliability of KSs, and so on. A control-feature space, therefore, is any observable or quantifiable aspect of an ~nvironmcnt and system that can possibly help to discern the appropriate action. The set of all control-feature spaces of potential interest constitutes a "control environment". In general, a control en vironment includes any aspect of a system and its environment about which information may be obtained to assist in making a decision.
REASONING fROM EVIDENTIAL INFORMATION
Lowrance and Garvey have characterized uncertain, incomplete, and inaccurate information as evidential information that must be used by expert systems to reason about their environment [LOW82a]. 1 Just as the information needed to interpret our environment is evidential in nature, so is the information needed to decide what to do next. That is, information about such things as goals, consequences of ac tions, the power of KSs, and how much is known about the environ ment is not easily expressed in terms of Boolean logic or probabilities. Hather, such information is evidence that tends to confirm or refute hypotheses about wh:1t control feature values have been observed, and these hypotheses in turn directly or indirectly imply what actions should be taken.
For ou r :1pproach, the information required to reason about what to do next i.5 obtained through a set of control knowledge sources (CKSs). 2 Similar to I<Ss, CKSs provide partially processed, "control related ," evidential information that is based upon their observations of the control environment.
A Formal VIew
Let A, the set of mutually exclusive and exhaustive actions that a system can possibly take, be defined as
Let F, , F2 , , Fm constitute the control-feature spaces of inkr~st.a Associated with each F1, 1 ~ i ~ m, is a set 11 of possible fea ture values of F1, where
For each /i E h it is possible to identify a subset of actions for which ~ach action is possibly the best one to take when ft is observed. For instance, it an analysis of the situation indicates that the goal of getting from point A to point B as fast as possible should be satisfied, then flying or driving, as opposed to walking, is possibly the best action. Alternatively, if the goal of getting from point A to point B by relatively economical means should be satisfied, then walking is possibly the best ar:tion.
1 Lowrance's and Garvey's development of the concept of evidential reasoning is based, in part, on Shafer's [SHA76] extension of Dempster's [DEM67, DEM68] work on upper and lower probabilities.
2 A CKS differs from a KS only in the scope of the environment and types of features it is expected to perceive.
aBecause we are limited in our capacity to reason with large bodies of information, a premise of this research is that we deal with this dilemma by employing some methods tor producing a manageable set or alternative actions and control-related information. We suggest that methods analogous to this one must be employed in expert systems.
We can now construct a frame of action, e ·.
e.= {(aj,/,,/2 .. . , fm) I Gj is possibly the best action to take when
Each 11 induces an equivalence relation over e. that partitions e. into lTd equivalence classes. Each / 1 E h therefore, is effectively an equivalence cl:1ss whose members are those elements of e. that exhibit feature value /;. Therefore, /1 ~e., and as a consequence
In reality, :1 CKS cannot always convey its observations in terms of the individual fl's. A CKS must be capable of communicating in terms of disjunctions of possibilities (e.g., through the proposition /' 1 V !'{ where / 1 1 ./ 1 { E Ji). Similarly, at times a CKS might need to express total ignorance about some observation (e.g. , through a proposition corresponding to e.). Consequently, a model for reasoning must incorporate those propositions with which CKSs wish to express t.heir observations.
A sy~ t- em cannot always obtain the exact value for a subset of features, nor will it always know what subset of features is required to choose between alternative actions. At best, a system will only be able to induce and refine a partial ordering over a subset of alternatives to the extent. that it is capable of realizing what control-feature spaces are required to diseern the appropriate action and is able to reason from imperfect measurements of those features .
BODIES OF EVIDENCE
A CKS conveys its observations by providing a mass vector, which it derives from a body of evidence that tends to confirm or refute a su~ set of the propositions of interest. In an evidential approach, every CKS has a unit of "mass" that it may distribute, on the basis of its beliefs about what it h3S observed, among the various propositions. Given its observations, a CKS might believe that a subset of the propositions is partially or completely true. Such beliefs can be conveyed by attribut ing a proporti·onate amount of its unit mass directly to the truthfulness of those propositions. Conversely, ·a CKS can attribute a portion of its mass directly to the negation of a subset of propositions if it believes that they are partially or completely faiBe.
Bayesian distributions and maea vectors
A mass dist.ribution can be viewed as a generalized B:1yesian dis tribution of belief over a set or propositions. A Bayesian distribution assigns a unit of belief over a set of mutually exclusive and exhaustive propositions, as designated by the mapping m.
Th~ probability of any proposition , for instance B ~e. , is the sum of the belief attributed to propositions that imply B or one minus the 'urn of the belid attributed to propositions that imply not B (i.e., ·D).
It follows that
llowever, a mass distribution need not attribute belief to mutually ex clu, ivc and exhaustive propositions. That is, belief may be distributed a' clc-:: i!;nated by t.he mapping Jl.f.
The sum of t.he mass att rihuted to propositions that imply B plus t.be sum of the mass attributed to propositions that imply · B need not equal one, becaus<' some mass may have been assigned to propositions that imply neither (e .g., e.).
Each body of evidence, therefore, induces an interval , called an "<·vi<knt.ial interval .. , within which belief about a proposition must lie. An <·vid<·ntial int erval is a subinterval of the real interval IO,q . The luw~ r and upper bounds of the evidential interval will be called support (S'pt) and plausibility (Pi s), respectively. The Spt represents the total mass that tends to support a proposition:
The 1'1.· represents the degree to which the mass fails to refute the propMit inn.
The intrrprct.ations of some evidential intervals are summarized below:
Completely true II , II ;
Completely false 10, 0];
Completely Ignorant !O, I];
Tends to support !Spt , lj, 0 < Spt < I;
Tends to refute !O, Plsj, 0 < Pl~ < l ;
Tends to support and refute !Spt , Plsj, 0 < Spt S Pls < I.
AN EVIDENTIAL APPROACH
The application of our approach begins by invoking a subset of the available CKSs in order to make observations of the system's control environment . Each CKS conveys i~s observations by providing a body of e,·idence, in the form of a mass vector, that expresses its belief in propositions such as
- TT lE COST OP INVOKING KSl WILl, BE 100 CPU SECONDS,
- OUR GOAL SHOULD BE TO IDENTIFY OBJECTS CLOSEST TO US Fll?ST.
An integral part of our approach is the use of Dempster's rule to combine bodies of ev idence IDEM67 , DEM68]. Given two arbitrarily complex mass vectors , say M1 and M2 , Dempster's rule produces a third mass v~ctor , A/3 , that reflects a consensus of the opinions ex pressed in i\11 and A/2 . That is,
Shafer ISH A itlJ and Lowrance ILOW82bJ can be consulted to under stand how multiple bodies of evidence can be combined. Furthermore, Dempster's rule is both commutative and associative. Therefore, the order and grouping of combinations is immaterial. This allows results to be obtained with whatever degree or parallelism the host hardware can support.
Dempster 's rule accomplishes two functions . The first is to obtain a con,<:nsus about what actions each CKS believes is possibly the best to take. For insf.:tnce, one CKS might provide evidence that pertains to tlw costs associat('(l with invoking various KSs, whereas a second CKS rn:ty pr<Wide evicknce that pertains to the reliability or invoking various J..:Ss . Given t-h<: evidence they each provide, the task is to determine what adions both CI<Ss agree are the most appropriate to take.
Forallp,,pz , p~~e ·. M3(P3)=(I-Kt 1 L Mt(pt)Mz(p2), ~'' n112=P·
If both bodies of eviden<:e are completely consistent , then there is ~ t le:"t one action that they both agree is possibly the best to take, and it can be said they are expressing completely compatible opinions, 1\ = 0. Conversely , if the evidence they provide is not completely consistent, then their opinions are not completely compatible, 0 < 1\ S I . Dempster's rule simultaneously determines which actions, if any , both C:I..;Ss agree are appropriate and provides a measure, K, of the wmpat.ibility between t.he two bodies of evidence.
The second funct ion of Dempster's rule is to correct for minor errors that. may occur in bodies of evidence. The assumption here is that the likelihood of distinct CKSs introducing the same type of error in th<·ir bodies of evidence is negligible. Therefore, any such errors can he overwhelmed by a sufficient amount of redundant and generally correct ev idence . If a subset of CKSs makes gross errors, such bad information should be discarded if it is detected.
N~xt the result of applying Dempster's rule must be extrapolated from t hose proposit.inns on which it bears directly to the remainin& de pendent proposit-ions' This extrapolation process is performed by an inference enginc 6 that carries out its task by adjusting the bounds on the ~v id~nt. ial interval t.t.at is associated with every dependent proposi tion.
· Lowrance has developed a model, called dependency graphs, that arc a formal representation of logical dependencies between propositions ILOW82b].
6 T he inference engine used in this approach is similar to that described in Lowrance's thesis ILOW82b] .
Aft.<·r the extrapolation process terminates a partial ordering over ! '"' set of alt~rnative actions is r~ r. ~ct~d in the evidential intervals as soc iated with each a E 8 0 · Selecting the appropriate action involves evaluCLting t hese evidential intervCLls. Although a complete decision theory for pNforming such an evaluation is not yet available, it is pos sible to rhoos~ actions on the basis of several simple criterion. For ~xampl~. determining the best action is obvious for those propositions that corr~spond to alternatives that have evidential intervals that do not ov~rlap . For t.hose propositions with overlapping evidential inter v:d>, further evaluation is called for. There are many utility- vs. cost bCLsed theories that can be used to select an action on the basis of beliefs that arc constrained by an evidential interval. However , a simple scheme might be to usc the median of the evidential interval.
SUMMARY
This pap~r has described some important problems confronting expert systems that operate in complex domains - pooling generically distinct cvidcnt.i a. l informa.tion , correcting for minor errors in eviden tial information, and realizing an adequate representation of the total evidence t.hat t~nds to support , t.ends to refute , and neither supports nor r~fut~s the propositions of interest. We have also described how an cv id r nt.ial approach to reasoning about control can address some of the~e prohlems. 0 Dempster 's rule is a mechanism for obtaining a consensus about the appropriate actions to take and correcting minor errors; a system can bet.ter explain its actions because a confidence in terval ~ llnws it to distinguish between supporting, refuting, and neutral evid~ntial information .
ACKNOWLEDGMENTS
l would like to thank Drs. John D. Lowrance and Thomas D. Ga rvey for their untiring guidance and extremely helpful suggestions.
@inproceedings{ijcai1983p48,
title = {Reasoning About Control: The Investigation of an Evidential Approach},
author = {Wesley, Leonard P.},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {203--205},
year = {1983},
note = {Expert Systems},
url = {https://ijcai.org/proceedings/1983/48},
}
TY - CPAPER TI - Reasoning About Control: The Investigation of an Evidential Approach AU - Wesley, Leonard P. T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 203 EP - 205 UR - https://ijcai.org/proceedings/1983/48 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards