Anytime Belief Revision
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 74-80.
© 1997 International Joint Conferences on Artificial Intelligence
Abstract
Belief Revision is a ubiquitous process underlying many forms of intelligent behaviour. The AGM paradigm is a powerful framework for modeling and implementing belief revision systems based on the principle of Minimal Change; it provides a rich and rigorous foundation for computer-based belief revision architectures. Maxi-adjustment is a belief revision strategy for theory bases that can be implemented using a standard theorem prover, and one that has been used successfully for several applications. In this paper we provide an anyt i me decision procedure for maxi-adjustments, and study its complexity. FUrthermore, we outline a set of guidelines that serve as a protomethodology for building belief revision systems employing a maxi-adjustment . The algorithm is under development in the belief revision module of the CIN Project .
- Alchourr6n, C., Gardenfors, P., and Makinson, D. [1985], On the logic of th eory change: Partial m ee t func- tions for contraction and revision, Journal of Sym- bolic Logic 50: 510 -530.
- Antoniou, G. and Williams, M.A. [1996], R easoning with Incomplete and Changing Information, in N. Terashima and E. Altman (eds) , Advanced Informa- tion Technology Tools, Chapman and Hill, 395 -401.
- Dubois, D., Lang, J., and Prade, H. [1994], Possibilis- tic Logic, Handbook of Logic in Artificial Intelligence and Logic Programming, Gabbay, D., Hogger, C, and Robinson, J. (eds), Claredon Press, Oxford.
- Eiter, T and Gottlob, G. [1992], Th e Complexity of Propositional Knowledg e Base R evision, Artificial In- telligence 57: 227 -270.
- Gardenfors, P. [1988], Knowledg e in Flux, A Bradford Book, The MIT Press.
- Gardenfors, P., and Makinson, D. [1988], Revisions of Knowledg e Systems using Epistemic Entre nchm e n~ Proceedings of TARK, 83 -96.
- Gardenfors, P. and Makinson, D. [1994], Nonmono- tonic Inference Based on Expectations, Artificial In- telligence 65: 197 -245.
- Lang, J. [1997], Possibilistic Logic: Algorithms and Complexity in J. Kohlas and S. Moral (eds), Handbook of Algorithms for Uncertainty and D efeasibl e Reason- ing, Kluwer Academic Publishers.
- Lehmann, D. [1992], What should a Knowl edge Bas e En- tail, in Principles of Knowledge Representation and Reasoning, Morgan Kaufmann, 1992.
- MacNish, C.K. and Williams M.A. [1996], From B e- lief Revision to Design Revision: Applying The- ory Change to Changing Requirem ents, in Reasoning about Incomplete and Changing Information, Lecture Note Series, Springer Verlag, 1997.
- Makinson, D. [1987], On the Status of th e Postulate of Recovery in the Logic of Th eory Chang e, Journal of Philosophical Logic, 16: 383 -394.
- Nebel, B., [1991]
- B elief Revision and D efault R easoning, in Principles of Knowledge Representation and Rea- soning, Morgan Kaufmann, 417 -428.
- Rott, H. [1992] Preferential B eli ef Change using Gen- eralised Epistemic Entrenchment, Journal of Logic, Language and Information, 1: 45 -78.
- Spohn, W ., [1983] Deterministic and Probabilistic Rea- sons, Erkenntis 19: 371 -396.
- Williams M.A. [1992], Two functions for theory bas e change, in the Proceedings of the Australian Joint Conference on Artificial Intelligence, p259 -265.
- Williams, M.A. [1995] Iterated Th eory Bas e Chang e: A Computational Model, IJCAI-95, Morgan Kaufmann, 1541 -1550.
- M.A. Williams, [1996] A Practical Appraoch to Belief Revision: Reason-Based Change, in L. Aiello, and S. Shapiro (eds), Principles of Knowledge Representa- tion and Reasoning: Proceedings of the Fifth Inter- national Conference, Morgan Kaufmann, San Mateo, CA, 412 -421, 1996.
- Williams, M.A., and Williams, D.M., A Belief Re- vision System for the World Wid e Web, IJCAI Workshop on Artificial Intelligence and the Internet, 1997. http:/ /u2 .newcastle.edu.aujwebworld/papers/ai- internet. html Link
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.
1 Introduction
Belief Revision underlies many forms of intelligent be haviour. An intelligent agent must be adept at revis ing its beliefs in a rational way. The AGM paradigm, so named after its founders Alchourron, Gardenfors and Makinson [1985], is a powerful theoretical framework for modeling and implementing belief revision systems; it provides a rich and rigorous foundation for principled computer-based architectures that endow agents with the ability to change their beliefs in a coherent and ra tional fashion.
Gardenfors and Makinson [1988] provided a construc tive means for defining revision functions based on an epistemic entrenchment ordering of a reasoning agent 's beliefs. FUrthermore, they showed that there is a one to-one relationship between revision functions and epis temic entrenchment orderings.
Iterated revision can be achieved by transmuting epis temic entrenchment orderings where the emphasis is not exclusively on acceptance and removal of beliefs from a theory, but also on raising and lowering of the degree of acceptance of beliefs. Raising the degree of acceptance of a belief corresponds to a revision, whilst lowering it corresponds to a contraction.
Maxi-adjustment is a specific strategy for implement ing belief revision systems. It strives for maximal inertia of information under change, and was devised by Williams [1996] . It has been shown to be successful in applications where the systems designer or knowledge engineer is able to specify dependencies among beliefs [MacNish and Williams, 1996]. In essence, when incom ing information is inconsistent with the agent's knowl edge, a maxi-adjustment retracts only those minimally entrenched beliefs that are inconsistent with the new in formation.
In this paper we provide an anytime decision proce dure for maxi-adjustments. FUrthermore, we outline a set of guidelines that serve as a protomethodology for building belief revision systems. The algorithm is under development in the belief revision module of the CIN Project; a project that is seeking to develop an intel ligent information management toolkit [Antoniou and Williams, 1996] .
Section 2 outlines belief revision in the AGM paradigm. Section 3 discusses several important mod eling problems that arise when AGM change func tions are used in practice, it thence outlines how maxi-adjustments overcome them. Section 4 describes subsumption removal; an optional feature of maxi adjustment that can be used to enhance its performance. In section 5 we give an anytime algorithm for maxi adjustments, and in section 6 we discuss its complex ity. In section 7 we make several methodological remarks concerning the design and development of belief revisions systems that employ the maxi-adjustment strategy.
2 Belief Revision
An intelligent information system must possess the abil ity to revise its knowledge base when it receives new information. The AGM paradigm has become one of the standard frameworks for modeling change.
Let us begin with some technical preliminaries: L will denote a (possibly first-order) language which contains a complete set of Boolean connectives. We will denote sen tences in L by lower case Greek letters. We assume L is governed by a logic that is identified with its consequence relation 1- which is assumed to satisfy the following con ditions [Gardenfors, 1988]: (a) if a is a truth-functional tautology, then 1- a, (b) if 1- (a -+ /3) and 1- a, then 1- /3 (modus ponens) , (c) 1- is consistent, i.e. lf..l, where ..l denotes the inconsistent theory, (d) 1- satisfies the de duction theorem, and (e) 1- is compact.
The set of all logical consequences of a set T ~ L , i.e. {a : T 1- a}, is denoted by Cn(T) . A theory of L is any subset of £ closed under Cn. We let £r>4, pronounced 'elbow', denote the set of contingent sentences.
Within the AGM paradigm a body of information is represented as a theory, and informational changes are regarded as transformations on theories. The princi pal AGM functions are contraction and revision. They can be described using the well known AGM rationality postulates, and individual contraction and revision func tions can be uniquely determined by any of the several standard constructions, e.g. the epistemic entrenchment ordering construction. Both the postulates and the con structions attempt to encapsulate the principle of Mini mal Change. The magnitude of change may not be based on set inclusion measures; sometimes the most rational response to avoiding inconsistency is to forfeit more than the minimal number of beliefs, e.g. it may be better to retract several weakly held beliefs than to surrender a single strongly held belief.
A revision, T~, attempts to change a theory T to incor porate a so that the resultant theory is consistent pro vided a itself is consistent. A contraction, T;;, involves the removal of a set of sentences from T so that a nontau tological sentence a is no longer implied. A withdrawal function [Makinson, 1987] is a generalised contraction function in that it satisfies all but the most notorious postulate for contraction, namely recovery; the property T = Cn(T- U a). It has been argued in the literature that recov:ry is not always appropriate for a limited rea soner, however it is one of the most important postulates for capturing the notion of minimal change when infor mation is given up.
3 Implementing Belief Revision
For the purpose of developing an implementation of AGM change functions, Gardenfors and Makinson's [1988] work was a significant breakthrough. They showed that an epistemic entrenchment ordering ( cer tain total preorder on the sentences in the language) can uniquely determine how the system will react to the pres sures of impinging information. In order to develop com putational models based on the entrenchment construc tion two obvious problems must be overcome: first an epistemic entrenchment ordering has to be propagated by the change function, and second a finite representa tion for epistemic entrenchment orderings is needed.
We use partial entrenchment rankings 1 as our repre sentation of well-ranked epistemic entrenchment order ings, and we model iterated beliefrevision by propagat ing these rankings using a maxi-adjustment; a procedure described in Williams [1996] .
3.1 Partial Entrenchment Rankings
Finite partial entrenchment rankings will be sufficient for present purposes. They represent finite epistemic en trenchment orderings of£ where the elements of a finite (a not necessarily closed) set of sentences are mapped to the natural numbers.
Definition: A finite partial entrenchment ranking is a function B from a finite subset of sentences in £ into the natural numbers N such that the following conditions are satisfied for all a E dom(B):
1 Partial entrenchments were defined in (Williams 1995], and essentially identical representations can be found in (Du bios et al 1994, Rott 1992, Williams 1992], and elsewhere.
(PERl) 1/'r/ a then {,6 E dom(B): B(a) < B(,B)} 'r/ a . (PER2) I/1- -,a then B(a) = 0 .
(PER3) 1- a if and only if B(a) = max(B(dom(B))). The higher the integer assigned to a sentence by a par tial entrenchment ranking the more firmly it is held. (PER2) says that inconsistent information is assigned zero, and (PER3) says that the tautologies alone are assigned the highest rank. The most piquant property of a ranking, is given in (PER2), namely a nontautolog ical sentence a cannot be entailed by sentences ranked strictly higher than a itself.
We refer to B(a) as the degree of acceptance of a. The intended interpretation of a partial entrenchment ranking is that sentences assigned a degree of acceptance greater than zero form the agent's explicit beliefs of the system, and their logical closure form his implicit beliefs. Definition: Define the explicit information content of a ranking B to be {a E dom(B) : B(a) > 0}, and denote it by exp(B). Define the implicit information content of B to be Cn(exp(B)) , and denote it by content(B) .
Typically, we are not only interested in the degree of acceptance of explicit information, but also in the de gree of acceptance of sentences they entail. A partial entrenchment ranking represents a system's incomplete preferences from which a complete entrenchment rank ing can be generated. There could, well, be an infinite number of entrenchment rankings which are compatible with a given partial specification. The following function 'degree' derives the minimum possible degree of accep tance for implicit information as specified by a partial entrenchment ranking.
Definition: Let a E £t>4. If B is a finite partial en trenchment ranking, then define degree(B, a) to be
{ largest j such that {,6 E exp(B) : B(,B) 2: j} 1- a if a E content(B) 0 otherwise
Example: If B(a --> ,6) = 3, B(a) = 2, B('y) = 1, then we can compute degree(B, ,6) = 2, degree(B, a 1\ ,6) = 2, degree(B, a V 1) = 2, degree(B, a 1\ 1) = 1, degree(B, 8) = 0, degree(B, -,8) = 0.
3.2 Maxi-Adjustments
The (a, i)-maxi-adjustment of the partial entrenchment ranking B, is denoted B*(a, i), it modifies B by assign ing a the new ranking i whilst maintaining the properties of a partial entrenchment ranking. It is formally defined in [Williams, 1996] .
The input i can be specified as an integer, as a number in a specified range, e.g. [0, 1], as B(,B) for some ,6 which would mean give the new information a the same rank as ,6, or in linguistic terms depending on the application at hand.
Maxi-adjustments are motivated by Spohn's notion of a reason. According to Spohn [1983] ,6 is a reason for a if and only if raising the epistemic rank of ,6 would raise the epistemic rank of a.
Maxi-adjustment is based on the idea that if you be lieve a reason your coffee cup is leaking is that it has a hole, then whereupon closer inspection you discover its not leaking at all, it would seem a rational response to retract your cup has a leak and your cup has a hole. Contrariwise, if you are unaware that holes are reasons for leaks, then you could quite happily continue to be lieve your cup has a hole even when you discover that it is no~ leakin~. In other words, common sense suggests that mformatwn should be retracted only if there is good reason to do so.
To evaluate reasons, it seems eminently sensible to require that raising the rank of a should disturb the agent's background ranking as little as possible. It is easy. to show that whenever a and (3 are in exp(B), if we simply enforce the properties of a partial entrench ment ranking then (3 is a reason for a if and only if degree(B, (3 -+ a) > B(a). Maxi-adjustments aim to use a closed world assumption with respect to reasons: if it cannot be derived that (3 is a reason for a, then it is as sumed that (3 is not a reason for a. The system designer sp~ifies reasons by ensuring that degree(B, (3 -+ a) is stnctly larger than degree(B, a). All nontautological reasons are defeasible, and there may be reasons for rea sons.
Like most revision procedures on theory bases maxi ad~ustm~nts are syntactically dependent on exp(B). De sp!te t~us. syntax d_ependence it can be shown that (i) B (a, z) IS a partial entrenchment ranking in which a is assigned the degree of acceptance i, (ii) if i is gre~t.er than zero then content(B*(a, i)) is an AGM revision (content(B))~, (iii) content(B*(a, 0)) is an AGM withdrawal function, and (iv) Cn(B*(a, O)u-.a) n content(B) is an AGM contraction (content(B))~.
The change functions defined above by maxi adjustment may not be the same as those obtained via Gar?enfors and Makinson's construction using the epis temic entrenchment ordering derived in the obvious way from the relative ordering given by B using the func tion degree. Ordinary adjustment [Williams 1995] is a procedure that complies exactly with the standard en trenchment construction. There exist several variants of maxi-adjustment, all are minor variations of the main algorithm described in the next section. Our implemen t~tion [Williams and Williams, 1997] offers anytime algo nthms for all of the variants. By performing a so-called hybrid-adjustment (an adjustment followed by a maxi adjustment) we can guarantee that at least as much in formation is retained as would be using the standard en trenchment procedure. In practice hybrid-adjustments and maxi-adjustments retain a great deal more informa tion than the standard recipe.
O~her _properties o_f maxi-.adjustment include: (i) every rankmg IS reachable m a fimte language via a finite num ber of maxi-adjustments, (ii) maxi-adjustments only use the relative ranking of sentences, (iii) maxi-adjustments p_reserve _fini!eness; Jexp(B*(a, i))l :5 Jexp(B)I + 1, (Iv) _maxi-adJustment does not reassign explicit beliefs ~wldmg ran~s greate: than max( { i, B(a), B(-.a)} ), i.e. It preserves mformatwn that is more inportant than the incoming information, (v) moving a sentence up j ranks in one step results in the same ranking as 'jacking it up' J ranks one rank at a time, and (vi) similarly, moving a sentence down j ranks in one step results in the same ranking as moving it down j ranks one rank at a time.
Finally, based on the well known connections between belief revision, possibilistic reasoning and nonmonotonic r~asoning, maxi-adjustments can be applied to possibilis ttc knowledge bases [Dubois et a~ 1994], and nonmono tonic knowledge bases [Gardenfors and Makinson 1994 ~m~1W~. '
4 Subsumption Removal
The idea of using reasons to determine what informa tion to retract during the. contraction of a sentence a works well for all beliefs except for some ranked at degree(B, a). For example, if (3 -+ a, (3 and a are equally ranked, then neither (3 -+ a nor (3 is a Spohnian reason for a, yet belief in both cannot be maintained if a is to be contracted. In this case the Gardenfors and Makinson construction would remove both (3 -+ a and (3. A standard maxi-adjustment is designed to do the same however it also provides an optional procedure that use~ subsumption removal which if selected removes all the beliefs subsumed by the information to be contracted. For the case in question above, this would result in the retraction of (3 -+ a in preference to (3 because (3 -+ a is subsumed by a.
Subsump~ion removal is not always appropriate, has a computatiOnal cost, and should be used with caution. W?en contracting (or lowering) a belief a using a maxi adJustment we justify removing beliefs subsumed by a on the following grounds:
- (i) If B is interpreted to be a partial specification of an agent's epistemic entrenchment, then it will, in general, be compatible with several epistemic en trenchments (which could, in principle be gener ated using a different mechanism for degree). If B((J -+ a) = degree(B, a) then there may exist a compatible epistemic entrenchment ordering that would retain (3 using the standard Gardenfors and Makinson construction, but no such compatible or dering could exist that would retain (3 -+ a2. If a v (3 is explicit and B(a V (3) = degree(B, a) then we may prefer not to use subsumption removal because it could be interpreted to mean that the user defi nitely wants (3 removed when a is- this situation can be trivially detected, and built into the algorithm.
- (ii) Since a 1- (!3 -+ a) the sentence (3 -+ a does not add any epistemic power to the ranking if a itself is an explicit belief. In other words, the same epistemic entrenchment ordering would be generated using the function degree irregardless of whether (3 -+ a. is ex plicit. If subsumption removal is applied then when ever a is an implicit but not explicit belief the maxi adjustment algorithm makes it explicit. In other words, reducing the ranking of a will not remove a even if it wasn't previously explicit, except of course when the new rank is zero.
5 Anytime Maxi-Adjustments
An anytime algorithm is one that if interrupted has con structed a partial solution that approximates the actual solu~ion, and the longer it runs the better the approxi matwn. The proposed algorithm for maxi-adjustment is anytime because it constructs the desired resultant par tial entrenchment ranking in a top down iterative fashion refining the partly constructed ranking until it converges on the actual ranking. FUrthermore, it captures impor tant beliefs before less important beliefs, by rebuilding the ranking from the highest rank to the lowest.
. 2 In other words, if o = (3 --+ o, then o V (3 > o is pos sible, but o V ((3 --+ o) > o would violate the postulates of entrenchment.
Put simply, the algorithm consists of two main phases: First find the largest cut of the ranking that is consis tent with the sentence to be moved, and second salvage as much of the remainder of the ranking by giving pref erence to higher ranked beliefs.
An important and endearing feature of the algorithm is that after completing its first phase the content of the ranking constructed so far is guaranteed to satisfy the AGM postulates for withdrawal and revision. Further more, there is enough information to construct a con traction function as well.
The second phase refines the ranking, in the sense that it recaptures as many beliefs as possible by removing only the minimal subsets at each rank that together with the higher ranked beliefs to be kept entail the informa tion to be contracted.
For simplicity of exposition, and without loss of gen erality, nonbeliefs and tautologies are not explicit in our rankings, in addition we focus on the principle case of movement of contingent beliefs within the ranking.
The algorithm requires the services of a standard the orem prover to implement references to entailment in the function degree, and in the generation of minimal sub sets that entail sentences to be moved down the ranking via the movedown procedure. Before the procedure can decide whether to raise or to lower the degree of accep tance of the sentence o: it computes its current degree of acceptance. If its degree is to decrease, then moved own is performed. If its degree is to increase then ...,o: is de creased first (if necessary) using moved own, and then a is moved up the ranking using moveup. The pro cedure maxi-adjustment( a:, i, B,newB) is the (a, i) maxi-adjustment of B resulting in the formation of the new ranking newB. The highest integer given to any sentence in the domain of B is assigned to the global variable max_degree. ·
If the maxi-adjustment procedure is interrupted then newB constructed so far is returned and if i > 0 then we check that o: has been added to rank i, if not we do so.
PROCEDURE: maxi-adjustment(a, i, B, newB)
Input: A partial entrenchment ranking B, a sentence a, and an integer i which represents the new desired
rank of o:.
if a E dom(B) then degree__o: := B(a)
else degree_o: := degree(B, o:) end if max_degree = max(B(dom(B))) case of degree__o:: greater than i: movedown(o:, degree__o:, i, B, newB). lower than i: if degree_o: = 0 then degree ..noLa := degree(B, -,a:) else degree..not__o: = 0 end if if degree..not__o: > 0 then
movedown(o:, degree..not_o:, 0, B, newB) end if B := newB moveup(o:, i, B, newB) otherwise: newB := B end case Output: The new partial entrenchment ranking newB. FUNCTION: degree(B, o:) Input: A partial entrenchment ranking B, and a sen tence o:. degree := max_degree+ 1 do degree := degree -1 until {fJ : degree ~ B({J)} f- o: or degree = 0 assign degree( a:, B) := degree
Output: The degree of o: in the ranking B.
- PROCEDURE: movedown(o:, j, i, B, newB) Input: A partial entrenchment ranking B, a sentence o:, an integer j representing the current degree of o: in B, and an integer i representing the desired new degree of o:. for k = max_degree down to j + 1 do newB(fJ) := k for all sentences {J such that B({J) = k. for k = j down to i do - generate minimal subsets of sentences at rank k that together with dom(newB) entail o: - newB(fJ) := k for all {J not in any such minimal
subset. Output: The new partial entrenchment ranking new B. PROCEDURE: moveup(o:, i, B, newB) a integer i representing the desired new degree of
Input: A partial entrenchment ranking B, a sentence a, 0:.
for k = max_degree down to i + 1 do newB(fJ) := k for all sentences {J such that B({J) = k. newB(o:) := i for k = i - 1 down to 1 do newB(fJ) := degree(newB, o: -+ {J).
Output: The new partial entrenchment ranking new B.
Subsumption removal is an optional feature of the maxi adjustment procedure. There are several ways to use it: (i) eliminate subsumed beliefs before the minimal subsets are generated, or (ii) eliminate subsumed beliefs from the minimal subsets after they have been found. The first approach will, in general, result in more beliefs being re moved than the second, and will also reduce the number of minimal subset that must be generated. To incorpo rate the first approach (the second is equally obvious) we insert the following instruction between the first and sec ond for loop constructs in the movedown procedure, so that subsumed sentences are removed before the minimal subsets are generated: remove sentences in dom(B) if B(fJ) = degree( a:, B) and o: f- {J. Then after the second for construct we add: if i > 0 then newB(o:) := i
6 Complexity
The procedure maxi-adjustment(B, o, i, newB) re turns a revised ranking newB for any allocation of com putational time. The longer the algorithm runs the closer the ranking newB approximates B*(o, i).
First-order logics satisfy the conditions required of the underlying logic given in section 2, hence the AGM framework and the proposed algorithm supports changes to rich knowledge bases, in principle. However, it is well known that satisfiability in first-order languages is un decidable, consequently nontrivial belief revision algo rithms that are guaranteed to terminate cannot be con structed. The maxi-adjustment decision procedure de scribed herein is an anytime algorithm, so it can be used to generate an infinite sequence of better and better ap proximations to revision and contraction functions.
As noted in the previous section the maxi-adjustment procedure essentially consists of two main phases.
The first phase is computationally easier than the sec ond and if it is completed then we are guaranteed to satisfy the AGM postulates for revision and withdrawal, and notably we have enough information to construct a contraction function, if desired. It is interesting to note that for query evaluations, such as is f3 E B*(o, i), only the first phase need be carried out.
The function degree is the workhorse of the first phase. Computing degree(B, o) is NP-hard. If a poly nomial fragment of propositional logic is used, then com puting degree is polynomial. Our anytime algorithm uses a top-down strategy that, if interrupted will always err on the side of overestimating the degree of sentences which in turn will never lead to inconsistency. A purely bottom up procedure would not exhibit this behaviour. However a hybrid strategy that combined a top-down and a bottom-up binary search would be more efficient on average, than a purely top-down linear search for the degree of o, and if B has n natural partitions then it requires [log2 n] satisfiability checks [Lang, 1997]. An interpolation strategy that used information about rank ing's history, or information available from the appli cation at hand would also improve the performance of the function degree. Hybrid and informed techniques have been investigated in Lang [1997]. If we adopt a hybrid algorithm for degree in our anytime algorithm then should the program be interrupted we simply use the most recent upper bound to calculate the resultant ranking.
The first phase determines the most important core of the ranking to survive the change, the second phase refines it by maintaining as many other beliefs as pos sible based on the original ranking. The second stage of the maxi-adjustment is in t:..f, and hence solvable with a polynomial number of calls to an NP oracle (c.f. [Nebel 1991, Eiter and Gottlob 1992]). The worse case arises when all explicit beliefs are equally ranked. The computational cost decreases as the number of ranks in crease. So the more discerning the agent the easier it is for him to modify his beliefs using a maxi-adjustment. This property concords with our intuition, i.e. it seems psychologically plausible, but not all revision strategies exhibit it. For example, ordinary adjustment which is based on the standard entrenchment construction does not.
7 Methodological Remarks
7.1 Contraposition
The use of maxi-adjustment presupposes that the knowl edge engineer is able to identify reasons. The inability to identify reasons simply means that more information than is perhaps intended is retained in practice. If f3 is a reason for o then f3 -+ o should be placed higher in the ranking than o. Using material implication in this way has an important ramification, namely contraposition of reasons, i.e. whenever o is a (whole) reason for /3, then ·!3 is a (whole) reason for ·o. For example, if one of the reasons my hang-guilder is ascending is that the up-lift is sufficient to overcome the effects of gravity, then one of the reasons it is not ascending is that the up-lift is insuf ficient. Consequently, reasons do not capture causality in a broader context.
Another effect of contraposition is that if f3 is a rea son for o, then when an agent revises by adding ·o he will, if only implicitly, accept ·/3. Maxi-adjustment can also be used to model applications in which contraposi tion of reasons is not an appropriate assumption. This is achieved by breaking down the changes to the ranking into more primitive operations, and composing a trans action on the ranking!
7.2 Some Guidelines
Knowledge Engineers and System Designers are accus tomed to the syntax sensitivity present in prevalent in formation modelling methods, such as (restricted) log ical languages, entity-relationship models, conceptual graphs, etc. Methodologies have been developed for these traditional techniques: they guide the development process to a faithful, hopefully optimal, representation of the application at hand.
Maxi-adjustment is also syntax dependent, and whilst a methodology for using maxi-adjustments is not yet available the following application independent guide lines have helped in the development of several belief revision applications.
(1) Important information should be explicit.
- Information should be in its simplest logical form.
- The number of ranks should be maximised if incoming information is expected to be inconsistent with highly entrenched information.
- Conjunction can be used to bind information items together, e.g. if the application calls for o to be re moved whenever f3 is and vice versa, then o A f3 can be used. If the conjuncts themselves are not explicit, or not derivable from other explicit beliefs then they will stand and fall together.
- Represent sentences that do not need to be bound as independent sentences, e.g. if o and f3 are not related then using o and f3 is preferable to the compound sentence o A f3.
- Irredundant rankings are preferable.
- If the set {/3t, fJ2, ... , f3n} constitutes a reason for o (i.e. their simultaneous satisfaction would mean that o must hold), then the sentence /31 A/32A ... A/3n -+ o is placed higher in the ranking than o.
- Subsumption at the same rank should be avoided, and should only be used to satisfy guideline (1).
Guidelines 4, 5, and 6 are related to data normalisa tion in database design; a process used to transform a database into a representation that minimises update anomalies. As is commonly the case with sets of guide lines, there are exceptions and some guidelines may be in conflict with one another for a particular application. For example, following ( 1) may lead to a redundant rank ing which clearly offends (6).
Methodologies will have to be developed to support the effective use of belief revision in real-world appli cations. Their development will be facilitated through experience with implemented prototype systems out in the field. Our aim is, not only, to develop a robust be lief revision system but also to assist the user in making design choices. This is partially achieved in our system [Williams and Williams, 1997] by making as many of the consequences of a users ranking representation visible. For example beliefs are highlighted before being moved, changes can be stepped through, reasons can be queried for in advance (since they are determined by the current ranking), and rankings can be unwound and saved using commit and rollback mechanisms. Rankings can also be modified hypothetically during development and testing.
The anytime algorithm for maxi-adjustment is under development in the CIN Project: a project that is seek ing to develop an Intelligent Information Management Toolkit. It offers a suite of sophisticated methods for default reasoning and belief revision. The system is cur rently founded on an objected-oriented design. The core of the belief revision system is implemented in c ++ us ing a state-of-the-art tableau theorem prover, and a Java based Graphical User Interface that provides facilities for dropping and dragging sentences up and down a ranking. Several rankings can be manipulated simultaneously.
8 Discussion
Iterated belief revision can be achieved by transmuting a partial entrenchment ranking. In this paper we de scribed an anytime decision procedure for iterated belief revision.
We discussed the complexity of our anytime algorithm. In essence, it possesses two main phases: (i) determine the degree of acceptance for the information to be moved down the ranking, and (ii) remove minimal sets of sen tences at each rank that entail the information to be moved down the ranking. The first phase is computa tionally simpler than the second, and if the first phase is completed before the algorithm is interrupted then we are guaranteed to be able to identify a theory base whose closure satisfies the AGM postulates for revision and withdrawal. Furthermore, the ranking so far con tains enough information to construct a theory satisfying the postulates for contraction.
The prop.osed anytime algorithm has been used for several applications, and as a result of the experienced gained in using our system we were able to provide a do main independent protomethodology for developing be lief revision applications based on maxi-adjustment.
@inproceedings{ijcai1997p12,
title = {Anytime Belief Revision},
author = {Williams, Mary-Anne},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {74--80},
year = {1997},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1997/12},
}
TY - CPAPER TI - Anytime Belief Revision AU - Williams, Mary-Anne T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 74 EP - 80 UR - https://ijcai.org/proceedings/1997/12 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: