A Unifying Framework for Probabilistic Belief Revision

1 Introduction

Since an agent acquires new information all the time, a key question is how such new information affects the agent's beliefs. This is the main subject of study in the area of belief change [G¨ardenfors, 1988; Peppas, 2008]. The dominant approach in belief change is the AGM framework [Alchourr ´on et al., 1985; G¨ardenfors, 1988], which represents the agent's beliefs and input information as formulas of some background logic that subsumes classical logic.

In daily life, we most often deal with uncertain information, and quite often degrees of uncertainty are involved and play an essential role. For instance, we may decide to stay at home if the weather forecast says "the chance of a thunder storm is 90%" but we may seriously consider outdoor activities if the chance is 10%. More importantly, upon acquiring new information, the degree of uncertainty of our beliefs may change. For instance, the chance of an average American developing Type 1 diabetes by age 70 is 1%; however upon learning that the person has an immediate relative who

Abhaya Nayak Macquarie University abhaya.nayak@mq.edu.au Abdul Sattar Griffith University a.sattar@griffith.edu.au

has Type 1 diabetes, the chance rises to 10%-20%. Since the AGM framework does not take into account explicit measures of uncertainty, this kind of change is beyond its scope. 1 In this paper, we aim to develop a belief revision framework that deals with changes to degrees of uncertainty, among others.

To reach this aim, a crucial first step is to represent degrees of uncertainty properly. The most common representation of uncertainty in artificial intelligence is via probabilities, or more precisely probability functions which assign probabilities to propositional formulas. Also there are some established methods for incorporating new information into a probability function. The standard method is Bayesian conditionalisation or conditionalisation for short, which handles new information of the form "the probability of φ is 1," where φ represents some event. The best known generalisation of conditionalisation is Jeffrey conditionalisation [Jeffrey, 1965], which also handles new information with a degree of uncertainty such as "the probability of φ is 0.3." Neither conditionalisation nor Jeffrey conditionalisation is defined for the case where the probability of φ is initially zero. Lewis [1976] introduced a method called imaging that can handle such a "zero-probability" case. But imaging without further generalisation cannot handle new information with an associated degree of uncertainty.

We can identify at least two issues with the above methods. First, they assume that an agent's beliefs are represented by a single probability function, which means the agent has to know the exact probability for every event before any of the methods can be applied. In many cases, this is impossible, as very often we only have an estimation of the probability for a limited number of events. Second, each of these methods is limited in one way or another: either it handles only new information that is certain (i.e. imaging, conditionalisation) or only new information with non-zero initial probability (i.e. conditionalisation, Jeffrey conditionalisation).

We address both issues in our approach. The key is to deal with uncertainty through a probabilistic logic, which we call p-logic. Instead of probability functions, it is more natural and intuitive to work with individual probability statements such as "the probability of φ is 40%"; "the probability of φ is twice as likely as that of ψ"; or "the probability of φ is 20% more likely than that of ψ". P-logic, which originates from [Fagin et al., 1990], is capable of representing and reasoning with such probability statements. As opposed to probability functions, p-logic can deal with incomplete information.

1 Arguably, the entrenchment based approach in the AGM framework [G¨ardenfors and Makinson, 1988] captures some forms of uncertainty, but it neither represents explicit degrees of uncertainty nor changes to such degrees.

In our approach, we represent an agent's beliefs by a logically closed set of p-logic formulas called a p-belief set, which captures exactly the probabilistic information known to the agent. Then we define a variant of partial meet revision functions [Alchourr´on et al., 1985], called p-revision, for incorporating p-logic formulas into a p-belief set. P-revision is an "all purpose" revision method in that it can handle all forms of new information expressible by p-logic. P-revision is also well-behaved: we provide a representation theorem which shows that the class of p-revision functions can be characterised by the p-logic analogues of the basic AGM revision postulates.

An interesting outcomes of our approach is that we can show that each of the three methods, conditionalisation, Jeffrey conditionalisation, and imaging, is equivalent to some suitably-restricted class of p-revision functions. So, although these methods are devised in different contexts and were proposed long before the AGM framework, they all obey the basic principles of revision in the AGM framework. Moreover, our approach helps explicate the counterpart of AGM expansion in the probabilistic setting.

2 P-Logic

P-logic can be seen as a syntactically restricted version of the logic given in [Fagin et al., 1990] for reasoning about probabilities. 2 Roughly speaking, a p-logic formula, called a p-formula, represents a constraint on the probabilities of some events.

Events are represented using formulas of classical propositional logic. Let A be a finite set of propositional atoms. The propositional language L is defined using the standard set of Boolean connectives, based on the atoms in A and the constants ⊤ and ⊥. We write propositional atoms as lower case Roman letters (a, b, c, . . .) and propositional formulas as lower case Greek letters (φ, ψ, . . .). Let Cn be the classical consequence operator. We denote a propositional interpretation or possible world as ω or µ possibly with a subscript, and sometimes as a bit vector such as 011 . . . which indicates that a is assigned false, b is assigned true, c is assigned true, and so on. For a set of propositional formulas S, we denote its set of models as |S|. For a propositional formula φ, |{φ}| is abbreviated to |φ|. The set of all possible worlds is denoted Ω. If ω ∈ |φ|, we say φ is true in ω and ω is a φ-world.

With events represented by propositional formulas, we represent constraints on their probabilities with atomic pformulas which take one of the following three forms:

1. p(φ) ▷◁ t
2. p(φ) ▷◁ c · p(ψ)
3. p(φ) ▷◁ p(ψ) + t

2 wherein all events are measurable.

where φ, ψ ∈ L, ▷◁∈ {⩽,⩾,=} and t, c are rational numbers such that 0 ⩽ t ⩽ 1 and 0 < c. A p-formula is a conjunction of atomic p-formulas (e.g., (p(φ) ⩾ 0.4) ∧ (p(φ) = p(ψ) + 0.2)). We write p-formulas as upper case Greek letters (Φ, Ψ, . . .) and denote the set of all p-formulas as LP. The three forms of atomic p-formulas are also referred as Category 1, 2, and 3 p-formulas and constrain, respectively, the probability of a single event, the ratio between probabilities of two events, and the difference between probabilities of two events. 3 Our intention is that each category captures a specific type of commonly encountered constraints on probabilities of events.

Not all constraints are, however, covered here. For instance p-logic does not support inequalities involving more than two events (e.g., p(φ) + 3 · p(ψ) ⩾ 2 · p(δ)) or arbitrary Boolean combinations of inequalities (e.g., (p(φ) = 0.3) ∨ (p(φ) = 0.4)). While restricted, p-formulas is in our opinion sufficient to capture most "commonsense" probability constraints. Also it will be clear that p-logic is more than enough for representing the revision process behind conditionalisation, Jeffrey conditionalisation, and imaging. Hence, the restricted syntax of p-logic demonstrates that not much formal machinery is needed from the probability standpoint to capture the three methods in a revision setting.

The basic semantic element for p-logic is a probability function. A probability function P : L ↦→ [0, 1] is a function that satisfies the Kolmogorov axioms:

• 0 ⩽ P(φ) ⩽ 1 for all φ ∈ L,
• P(⊤) = 1, and
• P (φ ∨ ψ) = P (φ) + P (ψ) whenever ¬ψ ∈ Cn(φ).

We denote the set of all probability functions as P. The letter P is reserved to denote a probability function throughout the paper. P satisfies an atomic p-formula

1. p(φ) ▷◁ t iff P(φ) ▷◁ t;
2. p(φ) ▷◁ c · p(ψ) iff P(φ) ▷◁ c · P(ψ); and

P satisfies a p-formula Φ∧Ψ iff it satisfies Φ and Ψ. P satisfies a set of p-formulas iff it satisfies all p-formulas in that set. Let X be a set of p-formulas and Φ a p-formula. If P satisfies X, then it is called a p-model of X. The set of p-models of X is denoted as ||X||. We abbreviate ||{Φ}|| by ||Φ||. We say X (respectively Φ) is consistent iff ||X|| ̸= ∅ (respectively ||Φ|| ̸= ∅); and X entails Φ under p-logic, denoted X |=P Φ, iff ||X|| ⊆ ||Φ||. The logical closure of X, denoted cl(X), is such that

A p-belief set B is a logically closed set of p-formulas, that is B=cl(B). The letter B is reserved to denote a p-belief set throughout the paper.

In many cases, it is more convenient to work with probabilities of possible worlds instead of propositional formulas. So we write P(ω1, . . . , ωn) or P(|φ|) as a "shorthand" for

3 Note that the p-formula p(φ) ▷◁ p(ψ) is both a Category 2 and a Category 3 p-formula.

The following example helps to illustrate the specifics of p-logic.

Example 1. Let A = {a, b}. Then Ω = {11, 00, 10, 01}. Consider the Category 1 p-formula p(11) ⩾ 0.5 (shorthand for: p(a ∧ b) ⩾ 0.5). Suppose the probability function P is such that P (11) = 0.7, and P (10) = P (01) = P (00) = 0.1. Then P satisfies p(11) ⩾ 0.5 since P(11) ⩾ 0.5. Note that p(11) ⩾ 0.5 |=P p(11) ⩾ c for any c < 0.5, since any P that satisfies p(11) ⩾ 0.5 has P (11) ⩾ 0.5 which means, by basic inequality, P(11) ⩾ c for any c < 0.5.

Working with logics like p-logic offers several advantages over probability functions. While a probability function is a complex structure that encapsulates the probabilistic information for all events, with p-logic we have the flexibility to deal with each piece of information separately. Also with p-logic, one can deal with incomplete information. Hence the probability of some events can be given without specifying the probability of all events. As well a constraint can be placed on an event (such as the fact that its probability is less than 0.4) without giving the exact probability. At the same time, one can clearly specify a complete probability function using only atomic p-formulas of any category.

3 P-Revision Functions

In this section, we consider how to revise a p-belief set by a p-formula. To begin, we define probabilistic expansion in the same way as AGM expansion. The probabilistic expansion of B by Φ, denoted B + Φ, is such that

Probabilistic expansion gives trivial results when Φ is inconsistent with B. To devise a non-trivial method, we follow the construction of partial meet revision in the AGM framework. 4 In revising B by Φ, we first determine the maximal subsets of B that are consistent with Φ; we call these subsets the remainder sets of B with respect to Φ.

Definition 1. The set of remainder sets of B with respect to Φ, denoted B ↓ Φ, is such that X ∈ B ↓ Φ iff

1. X ⊆ B,
2. X ∪ {Φ} is consistent, and
3. If X ⊂X′ ⊆ B, then X′ ∪ {Φ} is inconsistent.

We then select some of the "best" remainder sets. The intersection of these "best" remainder sets is expanded by Φ to form the revision outcome. The decision on which remainder sets to select is modelled by a selection function. A function γ is a selection function for B iff γ(B ↓ Φ) is a nonempty subset of B ↓ Φ, unless B ↓ Φ is empty, in which case γ(B ↓ Φ) = ∅. Then p-revision functions are defined as follows.

4 Strictly speaking, in the AGM framework, partial meet revision is constructed indirectly from a (partial meet) contraction via the Levi identity. Here we employ an equivalent, direct, construction of partial meet revision.

Definition 2. A function ∗ : 2LP ×LP ↦→ 2LP is a p-revision function iff

where γ is a selection function for B.

For properties of p-revision function, consider the following postulates:

(P ∗ 1) B ∗ Φ is a p-belief set.

(P ∗ 4) If B +Φ is consistent, then B +Φ ⊆ B ∗ Φ.

(P ∗ 5) B ∗ Φ is inconsistent iff Φ is inconsistent.

(P ∗ 1) - (P ∗ 6) are the p-logic versions of the six basic AGM revision postulates. We show that (P ∗ 1) - (P ∗ 6) fully characterise the class of p-revision functions.

Theorem 1. A function ∗ : 2LP ×LP ↦→ 2LP is a p-revision function iff it satisfies (P ∗ 1) - (P ∗ 6).

For revising probabilistic information, p-revision has at least three advantages over the previously mentioned classical methods such as conditionalisation. First, an agent's beliefs are modelled as a p-belief set, which does not have to contain the probabilistic information for all events; therefore, p-revision does not require the agent to be "probabilistically omniscient" to start with. Second, new information is modelled as a p-formula; therefore, p-revision can accommodate more forms of new information than the classical methods. Thirdly, p-revision can handle the "zero-probability" cases that are undefined for conditionalisation and Jeffrey conditionalisation.

4 Equivalence with Conditionalisation, Jeffrey Conditionalisation, and Imaging

Due to the richness of p-logic, the problems behind many approaches to revising probabilistic information can be represented as sub-problems of those behind p-revision. In this section, we demonstrate that conditionalisation, Jeffrey conditionalisation, and imaging are each equivalent to specific p-revision functions.

4.1 Conditionalisation & Jeffrey Conditionalisation

Conditionalisation is one of the most common methods for revising probability functions. The conditionalisation of P on φ, denoted P + φ , is defined as

The input φ is understood as "the probability of φ is 1." Jeffrey conditionalisation is the best known generalisation of conditionalisation. It deals with changes to a probability function induced by an input of the form "the probability of φ is c"

where 0 ⩽ c ⩽ 1. For simplicity we write the input as φ = c. The Jeffrey conditionalisation of a probability function P on φ = c, denoted P J φ=c , is defined as

in the general case, with special conditions attached to avoid division by zero. 5 It is easy to see that when c = 1 this reduces to conditionalisation.

Since we can represent a probability function P by a pbelief set B that has P as the only p-model, and the expression "the probability of φ is c" as the p-formula p(φ) = c, the Jeffrey conditionalisation of P on φ = c corresponds to the problem of revising B by p(φ)=c where ||B|| = {P }, which is a sub-problem for p-revision functions. We show that there are p-revision functions that yield an equivalent outcome to Jeffrey conditionalisation on this problem.

As its distinguishing feature, Jeffrey conditionalisation does not affect the probability ratios among formulas that imply φ and among those that imply ¬φ.

Lemma 1. If P(α) > 0, P(β) > 0 and either both α |= φ and β |= φ or both α |= ¬φ and β |= ¬φ, then

The key here is to formulate this ratio-preserving feature as a restriction to the selection functions for p-revision. To this end, we introduce the notion of ratio-formulas.

Definition 3. A p-formula of Category 2, p(α) = c · p(β), is a ratio-formula for φ iff 0 < c and either both α |= φ and β |= φ or both α |= ¬φ and β |= ¬φ.

A ratio-formula for φ is a Category 2 p-formula that describes the ratios between probabilities of propositional formulas that imply φ or those that imply ¬φ. So if α |= φ but β ̸|= φ, then p(α) = c · p(β) is not a ratio-formula for φ. In revising B by p(φ) = c where ||B|| = {P}, in order to keep the profile of probability ratios for φ and ¬φ untouched, we have to preserve all ratio-formulas for φ in B, which we denote as Rφ(B). We can show that Rφ(B) together with the new information p(φ) = c, give us the Jeffrey conditionalisation of P on φ = c.

In relation to p-revision, there is a remainder set of B with respect to p(φ) = c that contains Rφ(B).

Lemma 3. Let ||B|| = {P}. Then there exists some element X in B ↓ (p(φ) = c) such that Rφ(B) ⊆ X.

Thus, according to Lemma 2, if the selection function for B picks a single remainder set that contains Rφ(B), then the p-revision function yields an equivalent outcome to Jeffrey conditionalisation.

5 Here we follow [Halpern, 2005] and require that if c > 0, then P (φ)>0 and similarly if 1-c >0, then P (¬φ) > 0. Also c·P + φ (ψ) is taken to be 0 if c = 0, even if P (φ) = 0. Similarly (1-c)·P + ¬φ (ψ) is taken to be 0 if 1-c = 0, even if P(¬φ) = 0.

Theorem 2. Let ||B|| = {P}. Then there is a p-revision func-

Since Jeffrey conditionalisation generalises conditionalisation, the equivalence result also applies to conditionalisation. The following example illustrates the equivalence between a p-revision function and Jeffrey conditionalisation.

Example 2. Let Ω = {11, 00, 10, 01}, |φ| = {11, 00}, and P be a probability function such that P(11) = P(10) = P(01) = 0.2 and P(00) = 0.4. Then the Jeffrey conditionalisation of P on the input that "the probability of φ is 0.3," denoted P J φ=0.3 , is such that P J φ=0.3 (10) = 0.35, P J φ=0.3 (01) = 0.35, P J φ=0.3 (11) = 0.1, and P J φ=0.3 (00) = 0.2.

The Jeffrey conditionalisation corresponds to the revision of the p-belief set B by the p-formula p(φ) = 0.3 where ||B|| = {P}. The set of ratio-formulas for φ in B, denoted RB(φ), is such that RB(φ) = {p(10) = p(01), p(10, 01) = 2·p(01), p(10, 01) = 2·p(10), p(11) = 2·p(00), p(11, 00) = 3·p(11), p(11, 00) = 1.5·p(00)}. Note that |¬φ| = {10, 01}. Since RB(φ) is consistent with p(φ) = 0.3, there is a remainder set of B with respect to p(φ) = 0.3 that contains RB(φ).

Let ∗ be a p-revision function where the selection function γ for B is such that γ(B ↓ p(φ) = 0.3) = {X} and RB(φ) ⊆ X. Then we have B ∗ (p(φ) = 0.3) = cl(X ∪ {p(φ) = 0.3)}). Note that p(11) = 2 · p(00) together with p(φ) = 0.3 entail p(11) = 0.1 and p(00) = 0.2. Also p(φ) = 0.3 entails p(¬φ) = 0.7; and p(10) = p(01) together with p(¬φ) = 0.7 entail p(10) = 0.35 and p(01) = 0.35. So the only probability function that satisfies B ∗ (p(φ) = 0.3) is P J φ=0.3 .

4.2 Imaging

Imaging, introduced in [Lewis, 1976], is the starting point for many works on probabilistic belief revision [Ramachandran et al., 2010; Chhogyal et al., 2014; Rens et al., 2016]. In contrast to Jeffrey conditionalisation, imaging gives non-trivial results for the "zero-probability" case. Lewis makes the assumption that for each possible world ω and each consistent propositional formula φ, there is a φ-world, denoted ωφ, that is closest to ω among the φ-worlds. The image of a probability function P on φ is obtained by shifting the original probability of each world ω over to ωφ. As in conditionalisation, the input φ is understood as "the probability of φ is 1."

While there is only one way to do Jeffrey conditionalisation, there are many ways to do imaging; and each is determined by how, for each consistent φ ∈ L and each ω ∈ Ω, ω is assigned a closest φ-world. According to [Lewis, 1976], the only restriction for such an assignment is that if ω ∈ |φ|, then ωφ=ω, that is the closest φ-world to any φ-world is the φ-world itself. We model the assignment of closest world by a function I : Ω × L ↦→ Ω such that I(ω, φ) gives us the closest φ-world to ω and

1. I(ω, φ) ∈ |φ| and
2. I(ω, φ) = ω whenever ω ∈ |φ|.

We call such functions closest world functions.

Now the imaging process can be captured precisely by a image function defined as follows.

Definition 4. A function ◦ : P×L ↦→ P is an image function iff

where the probability function P ◦ φ is the outcome of ◦ on P and φ, and I is a closest world function. We say ◦ is determined by I.

From now on, we work with image functions rather than the general notion of imaging, as the former is precise on how the imaging is done.

Similar to the case of Jeffery conditionalisation, we can represent a probability function P by a p-belief set B that has P as the only p-model; and the expression "the probability of φ is 1" as the p-formula p(φ) = 1. So for an image function ◦, the problem behind P ◦ φ corresponds to the problem of revising B by p(φ) = 1 where ||B|| = {P}; this is again a sub-problem of p-revision functions. We next show the equivalence of some p-revision functions with the image function.

The imaging process can be characterised by a number of probability shifts, one shift for each world ω that "benefits" from the probability movement in the imaging process. We can picture such a shift for a beneficiary world ω as consisting of two steps: (a) identify all worlds, including ω, whose (relevantly) closest world is ω, and (2) shift their combined probability mass to ω. The key here is to formulate such probability shifts as restrictions on the selection functions underlying p-revision. To this end, we introduce the notion of a shift-formula.

Definition 5. A p-formula of Category 1, p(α) = c, is a shiftformula for φ iff |α| ∩ |φ| is a singleton.

The intention here is that, given the desired outcome P(φ) = 1, for each φ-world ω we identify a sentence α such that |α| contains exactly those worlds each of which has ω as its closest world among |φ|. It is easily noted that, in such a case, |α| ∩ |φ| = {ω} is a singleton. The resultant probability of ω (due to imaging) is the total probability it will receive from members of |α|, and c is intended to capture that total. Since we have a shift-formula p(α) = c for every φ-world ω, we can capture every shift of probability behind P ◦ φ. We accordingly define the shift-set for φ (with respect to P and I) as the set of such relevant shift-formulas:

Definition 6. The shift-set for φ with respect to P and I, denoted SIP (φ), is a set of shift formulas. A shift formula p(α) = c is in SIP (φ) iff there exists ω ∈ |φ| such that

The following lemma shows that our intuition on capturing the shift of probability through a shift-set is correct. That is, P ◦ φ , where the image function ◦ is determined by I, is the only p-model of SIP (φ) and p(φ) = 1.

Lemma 4. Let ◦ be an image function that is determined by I. Then

In relation to p-revision, we have that if B is a p-belief set that has P as the only p-model, then there is a remainder set of B with respect to p(φ) = 1 that contains SIP (φ).

Lemma 5. Let ||B|| = {P}. Then there exists element X in B ↓ (p(φ) = 1) such that SIP (φ) ⊆ X.

It follows then from Lemma 4 that if the selection function for B picks a single remainder set that contains SIP (φ), then the p-revision function yields an outcome equivalent to the imaging-function ◦.

Theorem 3. Let ◦ be an image function, and ||B|| = {P}. Then there is a p-revision function ∗ such that

The following example illustrates the equivalence between a p-revision function and an image function.

Example 3. Let Ω = {11, 00, 10, 01} and |φ|={11, 00}. Let P be a probability function such that P(11) = P(00) = 0, P(10) = 0.3, and P(01) = 0.7. Let ◦ be an image function where the associated closest world function I is such that I(10, φ) = 11 and I(01, φ) = 00. Then we have P ◦ φ (11) = 0.3 ,P ◦ φ (00) = 0.7, P ◦ φ (10) = 0, and P ◦ φ (01) = 0.

The problem behind P ◦φ corresponds to the the revision of the p-belief set B by the p-formula p(φ) = 1 where ||B|| = {P}. The shift-set for φ with respect to P and I, denoted SIP (φ), is such that SIP (φ) = {p(01, 00) = 0.7, p(10, 11) = 0.3}. Since SIP (φ) is consistent with p(φ) = 1, there is a remainder set of B with respect to p(φ) = 1 that contains SIP (φ).

Let ∗ be a p-revision function where the selection function γ for B is such that γ(B ↓ p(φ) = 1) = {X} and SIP (φ) ⊆ X. Then we have B∗(p(φ) = 1) = cl(X∪{p(φ) = 1}). Note that since |φ| = {00, 11}, we have p(01, 00) = 0.7 together with p(φ) = 1 entail p(00) = 0.7; p(10, 11) = 0.3 together with p(φ) = 1 entail p(11) = 0.3; and p(φ) = 1 entails p(10) = 0 and p(01) = 0. So the only probability function that satisfies B ∗ (p(φ) = 1) is P ◦ φ .

5 ANote on Probabilistic Expansion

It is generally accepted, starting with [G¨ardenfors, 1988], that the probabilistic analogue of AGM expansion is conditionalisation. In both the cases, exposure to evidence that does not contravene current knowledge leads to a new consistent belief state which incorporates both the old and the new knowledge; however, if the evidence "contradicts" old knowledge, the agent lands in the "epistemic hell". In the case of AGM expansion the epistemic hell is the inconsistent set Cn(⊥), and in case of conditionalisation it is an undefined belief state. Neither of these approaches employs any mechanism to resolve inconsistency. Note in particular that, in the probability setting, a piece of evidence with non-zero prior does not contravene current knowledge since there is at least one world with a non-zero probability mass that satisfies the evidence.

However, when a probabilistic belief state P is represented by a p-logic belief set B, the picture we get of conditionalisation alters drastically. Consider the conditionalisation of P by φ when P (φ) = 0.3. Here the conditionalisation outcome is properly defined, and hence would be considered a case of probabilistic expansion. In the context of p-logic, however, this conditionalisation would correspond to incorporation of the evidential sentence p(φ) = 1 into B where, presumably, B has p(φ)=0.3 as a member. Since no probability function can satisfy both p(φ)=0.3 and p(φ)=1, if we were to employ "expansion", we would expand to inconsistency. However conditionalisation demands otherwise, and what corresponds to conditionalisation in the context of p-logic is instead a proper p-revision function that involves resolving inconsistency. Hence we contend that it is our probabilistic expansion, namely a set union operation follow by logical closure, and not conditionalisation, that is the appropriate formulation of AGM expansion in a probabilistic setting.

We note that Voorbraak [1999] also claims that conditionalisation is different from AGM expansion, and his main argument is that AGM expansion aims to reduce ignorance whereas conditionalisation aims to reduce uncertainty.

6 RelatedWork

In contrast to p-revision, most approaches to probabilistic belief revision deal with changes to a single probability function induced by input of the form "the probability of φ is 1".

Apart from the classical methods mentioned previously, G¨ardenfors [1988] also provides a revision method for probability functions that adheres to the AGM framework. The main idea is that, in revising P by φ, first pick a probability function Q such that Q(φ) > 0 then take the conditionalisation of Q on φ (i.e., Q+φ ) as the revision outcome. In addition to revision, G¨ardenfors also discusses the corresponding operations of AGM contraction and expansion for probability functions. The approach by Chhogyal et al. [2014] is based on imaging. The authors propose various ways of assigning the closest worlds that are intuitively appealing, and evaluate their methods against some AGM-style revision postulates. Also based on the idea of imaging, the corresponding operation of AGM contraction is studied in [Ramachandran et al., 2010] for probability functions.

An approach that is closer to ours is by Rens et al. [2016] which works with a syntactically-restricted version of p-logic. To be precise, their language is restricted to a subset of Category 1 p-formulas. Since a set of such p-formulas may have more than one satisfying probability function, an agent's beliefs are modelled as a set of probability functions. They focus on a generalisation of imaging called general imaging [G¨ardenfors, 1988]. While imaging assumes that a possible world ω has a single most-similar φ-world (viz. ωφ), general imaging allows multiple most-similar worlds. In revising {P1, . . . , Pn} by φ, the approach of Rens et al. [2016] is to obtain the (general) image of Pi on φ for 1 ⩽ i ⩽ n, then take the set of imaging outcomes as the revision outcome. Frequently there is an infinite set of satisfying probability functions. Their main contribution is the identification of a finite set of boundary probability functions among the infinite set, such that revision of the finite set gives an identical outcome to revision of the infinite set. Note that although their logic allows one to express new information with a degree of uncertainty, their revision method, like imaging, handles only new information of the form "the probability of φ is

1". Also concerning changes to a set of probability functions, Grove and Halpern [1998] articulate some desirable properties and evaluate several revision methods over the properties. The methods they considered however can not handle the "zero-probability" case.

In [Boutilier, 1995] an agent's beliefs are captured by a Popper function [Popper, 2002] that takes the notion of conditional probability as the primitive. In this setting, Boutilier [1995] discusses issues of iterated belief revision. In [Delgrande, 2012], an agent's belief is modelled as a tuple that consists of a probability function and a confidence level c. Then methods for incorporating new and uncertain information with a confidence level exceeds c are introduced. Lindstr ¨om and Rabinowicz [1989] discussed ways of dealing with the non-uniqueness problem, that is a belief set can be associated with many different probability functions. Kern-Isberner [2001] brings conditionals and entropy measures into consideration for probabilistic belief revision. Bona et al. [2016] investigate ways of consolidating probabilistic information through belief base contraction [Hansson, 1999]. Noticeably, their approach is based on a syntactically-restricted version of p-logic (i.e., subset of Category 1 p-formulas). Chhogyal et al. [2015] give a concrete construction of G¨ardenfors' contraction method through argumentation.

7 Conclusion

In this paper, we have proposed p-logic, which is capable of representing and reasoning with some commonly encountered probability assertions. This allows us to deal with uncertainty in a more natural and familiar way. This also allows us to refer to each item of probabilistic information separately, which makes it easy to represent the change of information when our beliefs represented as p-formulas are revised.

With p-logic as the basis for dealing with uncertainty, we proposed p-revision, which is an "all purpose" revision method that complies with all the basic AGM revision postulates. We show that p-revision subsumes conditionalisation, Jeffrey conditionalisation, and imaging, which are the classical methods for revising probability functions. Significantly, the result implies that although these classical methods were introduced much earlier than the AGM framework, they all obey the basic principles of AGM revision.

We note that Category 3 p-formulas are redundant in establishing the correspondence of p-revision with the classical methods. Our results show that Category 2 p-formulas are sufficient to capture the revision process of Jeffrey conditionalisation and Category 1 p-formulas alone are sufficient for imaging. Whether there are meaningful revision methods whose representation requires Category 3 p-formulas is an interesting question that we will explore in our future work.

Acknowledgements

We thank Gavin Rens for useful comments on an earlier draft of this paper. This research has been supported by the Australian Research Council (ARC), Discovery Project: DP150104133, and the Natural Sciences and Engineering Research Council of Canada.