A Syntax-based Framework for Merging Imprecise Probabilistic Logic Programs

1 Introduction

The need for dealing with imprecise probabilistic beliefs is present in many real world applications. When multiple sources of probabilistic beliefs are available, one classic objective in statistics is to form consensus beliefs from the sources (e.g., [Nau, 1999; Pate-Cornell, 2002; Kern-Isberner and R¨odder, 2004; Chen et al., 2005; Osherson and Vardi, 2006; Bronevich, 2007] among others).

In the literature, many methods have been proposed to aggregate probability distributions where probabilistic beliefs are modeled as multiple probability distributions [Nau, 1999; Bronevich, 2007]. These methods are syntax-irrelevant in the sense that the underlying set of samples is unique and static.

In this paper, we consider situations where probabilistic beliefs are represented as probabilistic formulas in the form of (ψ|φ)[l, u], that is, conditional events are attached with probability bounds. Multiple belief sets may contain overlapped but not entirely the same set of probabilistic conditional events. Probabilistic conditional events explicitly given in an PLP suggest the focus and interests of that PLP in relation to an application. Let us consider a scenario where there are two sources providing relevant information. Source A is more concerned with the relationship between events φ and ψ and models its beliefs by estimating a probability bound for (ψ|φ). Source B is not aware of the relationship between

φ and ψ and hence does not have this relationship explicitly modeled in its beliefs. Let PLP PA and PB be elicited from sources A and B respectively. A rational way to merge PA and PB is to generate a PLP in which the bound for (ψ|φ) is closer to the bound of (ψ|φ) stated in PA than that implicitly inferred from PB. This observation suggests that first a rational merging procedure could be syntax-based in order to preserve any explicitly stated probabilistic beliefs, and second appropriate weights might be attached to sources (or even conditional events) to emphasize their relative importance.

Some syntax-based merging methods were proposed in [Kern-Isberner and R¨odder, 2004; Batsell et al., 2002; Osherson and Vardi, 2006] to extract a probability distribution from multiple probabilistic beliefs. However, our main objective of merging multiple PLPs is to obtain a new PLP which has a set of probability distributions as its probabilistic models, so that the impreciseness of the original PLPs can be preserved. Therefore, these methods do not satisfy our requirements.

When beliefs from different sources contradict with each other, each source should give up some of its beliefs in order to get consensus beliefs. Intuitively, we expect that each source gives up its beliefs as little as possible, and this is known as the minimal change principle. Another essential requirement is the mean-value principle, which states that the resultant probability bound for any conditional event shall not fall beyond the bounds given by the original sources. Constrained by these principles, in this paper we propose a framework to merge imprecise probabilistic beliefs syntactically. Within the framework, we define quantitatively how to measure the amount of beliefs that a source has given up (with respect to a merged result) and what constitute a minimal change (with respect to a set of sources). By instantiating the definitions for measuring the amount that a source shall give up on its beliefs, and for measuring the minimal change, we derive several concrete merging operators that possess different interesting characteristics. To formally regulate the behavior of merging PLPs, we propose a number of postulates in the framework, some of these extend the postulates for merging classical beliefs [Konieczny et al., 2004] whilst others are peculiar to the merging of probabilistic beliefs. It is proved that our instantiated operators satisfy most of these postulates.

The rest of this paper is organized as follows. After a brief review of PLPs in Section 2, we introduce our syntax-based merging framework in Section 3. Then, we provide postulates for merging PLPs in Section 4. Some instantiated operators are defined in Section 5. After comparing our work with related work, we conclude this paper in Section 6.

2 Probabilistic Logic Programs

We consider conditional probabilistic logic programming in this paper [Lukasiewicz, 1998; 2001; 2007]. Let Φ be a finite set of predicate symbols and constant symbols, and V be a set of variables. An event or formula can be defined from Φ ∪ V and connectives ¬, ∧, ∨ as usual. We use Greek letters φ, ψ, ϕ for events. An assignment σ maps each variable to a constant from Φ. The Herbrand semantics can also be canonically defined. We use I to stand for a possible world. Notation I |=σ φ means I is a model of φ under σ, and we denote I |= φ if I |=σ φ for any assignment σ. A conditional event is of the form ψ|φ with events ψ and φ. A probabilistic formula is of the form (ψ|φ)[l, u] which means that the lower and upper probability bounds for conditional event ψ|φ are l and u, where l, u ∈ [0, 1]. In this paper, for simplicity we say [l, u] the probability bound for (ψ|φ). A conditional probabilistic logic program (PLP) P is a set of probabilistic formulas.

A probabilistic interpretation Pr is a probability distribution on IΦ, where IΦ is the set of all possible worlds. The probability of an event φ in Pr under σ is defined as Prσ(φ) = ∑I∈IΦ,I|=σφ Pr(I). If Prσ(φ) > 0, we define Prσ(ψ|φ) = Prσ(ψ ∧ φ)/Prσ(φ). We define Pr |=σ (ψ|φ)[l, u], iff Prσ(φ) = 0 or Prσ(ψ|φ) ∈ [l, u]. Pr is a probabilistic model of (ψ|φ)[l, u], denoted by Pr |= (ψ|φ)[l, u] iff Pr |=σ (ψ|φ)[l, u] for all σ. Pr is a probabilistic model of a PLP P, denoted by Pr |= P, iff Pr is a probabilistic model of all μ ∈ P. A PLP P is satisfiable or consistent iff a model of P exists. We define P |= (ψ|φ)[l, u], iff all probabilistic models of P are also probabilistic models of (ψ|φ)[l, u]. We define P |=tight (ψ|φ)[l, u], iff P |= (ψ|φ)[l, u], P ̸|= (ψ|φ)[l, u′ ], P ̸|= (ψ|φ)[l′ , u] for all l′ > l and u′ < u. Note that, if P |= (φ|⊤)[0, 0], then it is canonically defined as P |=tight (ψ|φ)[1, 0], where [1, 0] stands for an empty set. We define P ≡ P ′ iff Pr |= P ⇔ Pr |= P ′ .

3 AMerging Framework for PLPs

3.1 Problem description

A probabilistic profile, denoted as E, is a multi-set of PLPs, i.e. E = {P1, . . . , Pn}, where P1, . . . , Pn are PLPs. For simplicity, we require that each Pi is satisfiable and we define Γ(Pi) = {(ψ|φ) | ∃l, u, (ψ|φ)[l, u] ∈ Pi}. Γ(Pi) is the set containing all the conditional events (ψ|φ) that are of interests to the source providing Pi. For a probabilistic profile E, we have Γ(E) = ⋃ni=1 Γ(Pi). We call E1 and E2 are equivalent, denoted by E1 ≡ E2, iff there exists a bijection between E1 and E2 such that each PLP is equivalent to its image. In this paper, we use ⊔ to denote the multi-set union.

In theory, it is possible for a single conditional event to have two probabilistic bounds. For example, let P = {(q(X)|p(X))[0, 0.1], (q(X)|p(X))[0.9, 1]}, then P is satisfiable and P |=tight (p(X)|⊤)[0, 0]. If we have P ′ = {(p(X)|⊤)[0, 0]}, then P ≡ P ′ . However, in practice, a single knowledge base rarely contains two different probability bounds for the same conditional event. This condition is formally defined as follows.

Definition 1 A PLP P is called canonical iff for any conditional event (ψ|φ) in Γ(P),

• (ψ|φ)[l, u] ∈ P ⇒ l ≤ u;
• (ψ|φ)[l1, u1] ∈ P, (ψ|φ)[l2, u2] ∈ P ⇒ l1 = l2, u1 = u2.

In our merging framework defined here, we require that each original PLP Pi is canonical without losing generality since every PLP Pi has a canonical PLP equivalent to it.

Let E = {P1, . . . , Pn} be a probabilistic profile, and P ∈ Δ(E) be a PLP in the result of merging the PLPs in E where Δ is a merging operator. We require that P satisfies the following constraints.

• P is canonical.
• For any Pi ∈ E and any (ψ|φ) ∈ Γ(E), suppose that Pi |= (ψ|φ)[li, ui], then P |= (ψ|φ)[l, u], s.t., mini li ≤ l ≤ u ≤ maxi ui. This requirement is also known as the mean-value property which guarantees a probabilistic Pareto principle from Social Choice Theory [Sen, 1986] as discussed in [Kern-Isberner and R¨odder, 2004].
• Since Γ(P) = Γ(E), the only difference between Pi and P is the probabilistic bounds for the conditional events in Γ(Pi). Therefore, we can measure the differences of these probability bounds. Δ(E) should contain those PLPs such that each of them is closest to all the PLPs in E (w.r.t. the probability bounds). This requirement is also known as the minimal change principle.
• We can further require that the conditional events in the original PLPs have as similar effects as possible in the merging to get more preferred merging results.

3.2 Strong consistency between PLPs

When two knowledge bases infer contradicting conclusions, we consider them inconsistent. That is true in classical logic, since for two propositional (or first order) knowledge bases K1 and K2, K1 ∪K2 is unsatisfiable iff there exists a φ such that K1 |= φ and K2 |= ¬φ. However, two PLPs infer contradicting conclusions (e.g. infer two disjoint bounds for the same conditional event) does not suggest that these two PLPs are inconsistent. Let us demonstrate this with the following example.

Example 1 Let P1 = {(q(t)|p(t))[0.4, 0.5]} and P2 = {(q(t)|p(t))[0.51, 0.6]} be two PLPs. Informally, P1 states that "q(t) looks unlikely to be true when p(t) is true" whilst P2 says that "q(t) looks likely to be true when p(t) is true". Intuitively, P1 and P2 contradict each other. However, P1∪P2 is satisfiable, and P1 ∪ P2 |=tight (p(t)|⊤)[0, 0], which says that p(t) cannot be true.

Obviously, P1 ∪P2 is not a reasonable candidate for merging P1 and P2, since by merging, we want to extract appropriate bounds for the conditional event (q(t)|p(t)) rather than simply state that the antecedent p(t) can not be true. In our framework, for any P, if P ≡ P1 ∪ P2 and Γ(P) = Γ(P1 ∪ P2), then P is not canonical. Therefore, P1 ∪ P2 does not satisfy the first constraint we outlined above, and thus can not be a candidate of merging result. It is worth noting that the union of PLPs may or may not be canonical.

Definition 2 Let P1, . . . , Pn be PLPs. We define the compact union of P1, . . . , Pn, denoted as ⊎ni=1 Pi, as follows

In the compact union, only one bound is assigned to a conditional event. The compact union of a set of PLPs is semantically equivalent to the union of these PLPs.

Proposition 1 Let P1, . . . , Pn be PLPs. Then ⊎ni=1 Pi ≡ ⋃ni=1 Pi.

Now, we can construct a canonical PLP P ′ from any PLP P by replacing each (ψ|φ)[l, u] with l > u in (P ⊎ P) by (φ|⊤)[0, 0]. Obviously, P ′ ≡ P. Two PLPs that infer contradicting conclusions should be considered inconsistent. To achieve this, we have the following definition.

Definition 3 PLPs P1, . . . , Pn are strongly consistent iff ⊎ni=1 Pi is canonical and satisfiable (consistent).

In Example 1, P1 ⊎P2 = {(q(t)|p(t))[0.51, 0.5]}, which is not canonical, therefore P1 and P2 are not strongly consistent.

3.3 Minimal Change

Based on the constraints on merging PLPs given above, we take merging PLPs in E as a process of constructing a canonical consistent PLP P s.t. Γ(P) = Γ(E). Then, in addition to the extra conditional events in P from other PLP Pj, the major difference between P and any Pi ∈ E is that the probabilistic bounds for the conditional events in Γ(Pi) could be different. A quantitative measure about the difference between these probabilistic bounds for conditional events in Γ(Pi) can be viewed as a measure about how much belief Pi has given up in order to reach an agreement with other PLPs in E. Ideally, each PLP wants to give up its beliefs as little as possible.

For any l and u, if 0 ≤ l ≤ u ≤ 1 then we call [l, u] a sub-interval of [0, 1].

Definition 4 Let [l, u], [l′ , u′ ] be two sub-intervals of [0, 1]. We define the change from interval [l, u] to interval [l′ , u′ ], denoted by Ch([l, u], [l′ , u′ ]), as

Definition 5 Let [l, u], [l′ , u′ ] be two sub-intervals of [0, 1]. We define the weak change from interval [l, u] to interval [l′ , u′ ], denoted by wCh([l, u], [l′ , u′ ]), as wCh([l, u], [l′ , u′ ]) = max(l - l′ , 0) + max(u′ - u, 0)

Obviously, Ch is symmetric while wCh is asymmetric.

Based on the change of bounds, we can define the change and weak change from one PLP to another.

Definition 6 Let P1 and P2 be two canonical PLPs s.t. Γ(P1) ⊆ Γ(P2). We define the change (resp. weak change) from P1 to P2, denoted as d(P1, P2), as

Ch(P1, P2) is greater than 0 iff some bounds are indeed changed, while wCh(P1, P2) is greater than 0 iff some bounds are loosened.

Example 2 Let us consider a situation about whether taking drug a will reduce the probability of a patient's (with a certain disease m) mortality. One Doctor thinks that a large proportion of the patient population with this disease will have a highly reduced probability of mortality, whilst another Doctor thinks a patient also with condition d is unlikely to be benefited from this drug. Obviously, patients having disease m and also with condition d form a subclass of patients with disease m.

Let rMor(X) denote "reducing mortality of X" and dis(X, d) denote "X having disease of d", and let

μ1 = (rMor(X)|drug(X, a) ∧ dis(X, m))

Then, the beliefs from the two doctors can be represented by the two PLPs below:

Let P and P ′ be two PLPs s.t.

We can calculate the (weak) changes from P1 and P2 to P and P ′ respectively, as shown in the following tables, e.g. Ch(P1, P) = 0.083 and wCh(P2, P ′ ) = 0.45.

Definition 7 An aggregation function Ag is a total function associating a nonnegative real number to every finite tuple of nonnegative real numbers that satisfies:

• x ≤ y ⇒ Ag(x1, ..., x, ..., xn) ≤ Ag(x1, ..., y, ..., xn).
• Ag(x1, ..., xn) = 0 if and only if x1 = · · · = xn = 0.
• For every nonnegative real number x, Ag(x) = x.

Functions Max, Sum, and weighted sum wSum are exemplar aggregation functions.

Definition 8 Let E be a probabilistic profile, and Ag be an aggregation function. Suppose that P is a canonical PLP s.t. Γ(P) = Γ(E). We define the (weak) change from E to P, denoted as d Ag (E, P), as d Ag (E, P) = Ag({d(Pi, P) | Pi ∈ E}), where d is wCh or Ch.

To preserve the minimal change principle, P ′ should not be chosen as the merge result.

Proposition 2 Let E be a probabilistic profile, then wCh(Pi, ⊎ E) = 0 for all Pi ∈ E.

Proposition 3 Let E be a probabilistic profile and P be a PLP. If wCh(Pi, P) = 0 for all Pi ∈ E, then P |= ⊎ E.

The above two propositions state that if we simply union multiple PLPs together, then we get tighter bounds, and thus the weak changes from all source PLPs to the result are 0.

Computing weights

To address the importance of a source for contributing to the calculation of the merged bound for a conditional event during merging, we investigate how weights shall be attached to sources (or even conditional events).

Definition 9 Let E = {P1, . . . , Pn} be a probabilistic profile. Suppose that the set Γ(E) can be represented as {μ1, . . . , μm}. Let W = (W l ,W u ) be a pair of n × m matrices from R[0,1] , s.t. ∀k, ∑i W l [i][k] = ∑i W u [i][k] = 1. For any Pi ∈ E and μk ∈ Γ(E), suppose that Pi |=tight μk[lik, uik]. A weighted combination of P1, . . . , Pn w.r.t. W is a PLP, denoted as ⊗WPi∈E Pi, s.t. ⊗WPi∈E Pi = {μk[l, u] | μk ∈ Γ(E), and l = ∑μi∈Γ(Pi) W l [i][k] × lik, u = ∑i W u [i][k] × uik}.

For simplicity, we use ⊗W E to denote ⊗WPi∈E Pi. Weights W l [i][j] and W u [i][j] reflect the importance of the lower bound and upper bound for conditional event μj contributed by PLP Pi.

On the other hand, it is easy to prove that if a PLP P satisfies the mean-value property w.r.t. E then there must exist a W s.t. P = ⊗W E.

Example 3 (Cont. of Example 2) Assume that weights assigned to the three conditional events in P1 and P2 are

Then, the weighted combination of P1 and P2 produces P .

4 Postulates

In classical merging, some postulates are provided [Konieczny et al., 2004]. In this paper, we adapt the postulates from [Konieczny et al., 2004] for merging PLPs. The merging operator Δ maps a probabilistic profile to a set of PLPs. Suppose that P ∈ Δ(E), then ideally P should satisfy the following:

• IC1 P is satisfiable.
• IC2 If E is strongly consistent then P |= Pi for all Pi ∈ E.
• IC3 If E1 ≡ E2, then Δ(E1) ≡ Δ(E2).
• IC4 If E = {P1, P2}, then ∃P ′1 ∈ Δ({P1, P2}) P ′1 ⊎ P1 is satisfiable iff ∃P ′2 ∈ Δ({P1, P2}) P ′2 ⊎ P2 is satisfiable.
• IC5 If E = E1 ⊔ E2, P1 ∈ Δ(E1), and P2 ∈ Δ(E2), then P1 ⊎P2 |= P.
• IC6 Let E = E1 ⊔ E2, P1 ∈ Δ(E1), P2 ∈ Δ(E2). If P1 ⊎ P2 is satisfiable, then ∃P ′ ∈ Δ(E), P ′ |= P1 ⊎P2.
• IC7 Let P1 ∈ Δ(E ⊔ {Pi}) and P2 ∈ Δ(E ⊔ {P ′ i }), where P ′ i is obtained by replacing a probabilistic formula (ψi|ϕi)[li, ui] in Pi with (ψi|ϕi)[l′i , u′i ]. Then Ch(P1, P2) ≤ Ch(Pi, P ′ i ).
• IC8 If Pi |= (ψ|φ)[l, u] for all i, then P |= (ψ|φ)[l, u].
• Maj For any E and P ∈ E. Suppose that P1 = · · · = Pn = P and P ′ ∈ Δ(E ⊔ {P1, . . . , Pn}), then limn→∞ wCh(P, P ′ ) = 0.
• Arb For any E and P ∈ E. Suppose that P1 = · · · = Pn = P , then Δ(E) = Δ(E ⊔ {P1, . . . , Pn}).

In these postulates, IC1-IC6, and Maj are essentially equivalent to those provided in [Konieczny et al., 2004] with trivial integrity constraint ⊤ and Arb is to that provided in [Meyer, 2001]. IC7 says that a slightly change of the sources will not affect the result too much, and the change of the results will always be smaller than the change of the sources. IC8, also known as consensus postulate, means that the common beliefs of the original PLPs should be preserved after merging.

5 Merging Operators

5.1 Merging by dilation of the probability bounds

A straightforward method to merge multiple PLPs is to weaken all of them until they become strongly consistent and then generate their compact union to get a new PLP.

Definition 10 Let P be a canonical PLP. A PLP P ′ is called a dilation of P iff P |= P ′ and Γ(P) = Γ(P ′ ).

A dilation of a PLP is obtained by loosing the probability bounds for some conditional events in the original PLP.

Definition 11 Let E be a probabilistic profile, we define dilation merging operators, denoted by Δ(wCh,Ag) (E) where Ag is an aggregation function, as P ∈ Δ(wCh,Ag) (E) iff P = argminP{wCh Ag (E, P) | P is satisfiable and P = ⊗W (E) for some pair of weight matrices W}.

Proposition 4 Let E = {P1, . . . , Pn} be a probabilistic profile, and P ∈ Δ(wCh,Max) (E). Then there exits E ′ = {P ′1 , . . . , P ′n }, s.t. P ′ i is a dilation of Pi, and P ≡ ⊎ E ′ .

The above proposition indicates that the merging result can also be obtained by first weakening the beliefs of every Pi such that these weakened PLPs are strongly consistent with others, and the merging result is the compact union of the weakened PLPs.

Example 4 Let P1 and P2 be two PLPs as given in Example 2. We have Δ(wCh,Max) as a singleton set. Suppose that Δ(wCh,Max) = {P ′′ }, then we have P ′′ = {μ1[0.916, 0.916], μ2[0.1, 1], μ3[0.164, 0.164]}.

Proposition 5 Let E = {P1, P2} be a probabilistic profile, and P ∈ Δ(wCh,Max) (E), then wCh(P1, P) = wCh(P2, P).

5.2 Merging by Keeping Impreciseness

Decreasing impreciseness VS. keeping impreciseness

Merging by dilation may drastically decrease the impreciseness of beliefs in that the bounds for some conditional events are much tighter than their bounds stated in the original PLPs. However, sometimes we still want the merging result be imprecise to maintain the reliability. For instance, let P1 and P2 be as given in Example 1. By dilation merging, we get Δ(wCh,Max) ({P1, P2}) = {P} where P = {(q(t)|p(t))[0.505, 0.505]}. Probability 0.505 is chosen because it is the only value that is closest to both of the upper bound for (q(t)|p(t)) given in P1 and the lower bound for (q(t)|p(t)) given in P2. However, when the imprecise bounds given in P1 and P2 suggest that both of them agree that imprecise probability bounds are more suitable for the conditional event due to lack of information, the bound [0.505, 0.505] is too tight as the merging result. This motivates us to propose the following operator to keep impreciseness.

The merging operator

In general, we do not require that W l = W u . In fact, in the dilation operator, the corresponding weights do not satisfy the above condition.

However, there are some intuition to require W l = W u if we regard the lower and the upper bound are equally important (or equally possible) for any conditional event in a PLP.

When requiring W l = W u , it is more nature to use Ch to measure the difference of a probabilistic profile to a PLP, since in Ch, the differences of the lower bounds and upper bounds are equally treated. Therefore, for the operators Δ(Ch,Ag) , we require that W l = W u :

Definition 12 Let E be a probabilistic profile, we define merging operators Δ(Ch,Ag) (E) as P ∈ Δ(Ch,Ag) (E) iff P = argminP{Ch Ag (E, P) | P is satisfiable and P = ⊗W E for some pair W = (W l ,W u ) and W l = W u }, where Ag is an aggregation function.

Example 5 Let P1 and P2 be as given in Example 1. By merging, we get that Δ(Ch,Max) ({P1, P2}) = {P } where P = {(ψ|φ)[0.451, 0.550]}.

Example 6 Let PLP P1 and P2 be as given in Example 2. Then Δ(Ch,Max) ({P1, P2}) is a singleton set, which contains the only one PLP P as given in Example 2.

Comparing to Example 4, in the above example, the belief about the probability of μ3 is imprecise. The upper bound 0.134 for μ3 is lower than 0.164 given in Example 4, this is because the lower bound 0 for μ3 in P2 has more effect in this operator.

5.3 Preferred Candidates

However, PLPs that satisfy Definition 12 are not unique in general, as shown by the following example.

Example 7 Let P1 = {(p|⊤)[1, 1], (q|⊤)[1, 1]} and P2 = {(p ∧ q|⊤)[0, 0]}. Then P1 and P2 are unsatisfiable. Let P and P ′ be given as

In this example, P is more reasonable than P ′ , since in P, p and q are symmetrically defined, just as that they are symmetrically defined in P1 and P2. In other words, the weights for (p|⊤) and (q|⊤) w.r.t. P1 and P2 are equivalent when obtaining P and inequivalent when obtaining P ′ . Intuitively, we should choose the PLPs from the merging results such that the weights for the conditional events in the original PLPs are as close as possible.

Let S = 〈s1, . . . , sn〉 be a finite sequence of real numbers in descending order. We define ⊴ as a lexicographic order among descending ordered sequences, i.e. S1 ⊴S2 iff

• |S1| ≤ |S2| and s1i = s2i for all i ≤ |S1|, or
• ∃i s.t. s1i < s2i and ∀j < i, s1j = s2j.

Let S be a finite multi-set of real numbers, we define sq(S) as a descending ordered sequence of the elements from S, then we can define a partial order ≼ as S1 ≼ S2 iff sq(S1) ⊴ sq(S2). For instance, if S1 = {0.8, 0.9, 0.8, 0.6} and S2 = {0.8, 0.9, 0.7, 0.7}, then S2 ≼ S1.

Let P and P ′ be PLPs s.t. Γ(P1) = Γ(P). We define C d (P ′ , P) as C d (P ′ , P) = {d([l′ , u′ ], [l, u]) | μ[l′ , u′ ] ∈ P ′ and μ[l, u] ∈ P}, where d is wCh or Ch.

Set C d (P ′ , P) contains the (weak) change values from the bounds given in an original PLP (P ′ ) to those given in a candidate (P) of merging result for the conditional events in P ′ .

Definition 13 Let E = {P1, . . . , Pn} be a probabilistic profile. Define Δ(d,Max) ≼ (E) as a set of PLPs s.t.

where d is wCh or Ch.

The above definition applies the min-max principle to require that the maximum (weak) change from the probabilistic formulas in the original PLPs be minimized.

Example 8 (Cont. of Example 7) Now, we have that Δ(Ch,Max) ≼ (E) = {P}. So, the less reasonable PLP P ′ is eliminated from the candidates of merging results.

Similarly, for operators Δ(d,Sum) , we can obtain Δ(d,Sum) ≼ by requiring the (weak) changes from the original PLPs to the merging result be as close as possible, but we omit the details due to space limitation.

5.4 Properties

Proposition 6 Let Ag be an aggregation function.

Δ(wCh,Ag) satisfies postulates IC1, IC2, and IC4-IC8;

Δ(Ch,Ag) satisfies postulates IC1, IC4, IC5, IC7, and IC8;

Δ(wCh,Ag) ≼ satisfies postulates IC1, IC2 and IC4-IC8;

Since postulate IC3 means that the merging operator is syntax-irrelevant and our framework is syntax-based, our operators can not satisfy IC3. We can extend our framework so that two semantically equivalent but syntactically different conditional events (denoted like (ψ1|φ1) ≡ (ψ2|φ2)) can be taken as the same conditional event. As a consequence, our merging framework is beyond syntax-based in which how conditional events are expressed is irrelevant.

Proposition 7 Our merging operators Δ(d,Sum) and

Δ(d,Sum) ≼ satisfy postulateMaj, while operators Δ(d,Max) and Δ(d,Max) ≼ satisfy postulate Arb, where d is wCh or Ch.

It is worth noting that in propositional logic, no merging operators can simultaneously satisfy IC2, IC4, IC6 and Arb.

6 RelatedWork and Conclusion

Related work In the literature, many methods were proposed to merge or aggregate probability distributions [Clemen and Winkler, 1993; Jacobs, 1995; Pate-Cornell, 2002; Chen et al., 2005]. In these methods, each source represents its beliefs by a single probability distribution, and the merging result is also a probability distribution. Therefore, these methods can be classified as model-based. There are some methods [Nau, 1999; Bronevich, 2007] that can aggregate imprecise probabilities (the lower or upper bounds for a conditional event), but these methods are also syntaxirrelevant, in the sense that they require the original beliefs to be expressed on the same set of (conditional) events. In [Clemen and Winkler, 1993; Jacobs, 1995; Chen et al., 2005; Nau, 1999; Bronevich, 2007], aggregation functions are used to calculate the probabilities of the events, and the (weighted) sum function is a common choice. In contrast, our framework starts with a set of PLPs, and each PLP has a set of probability distributions associated with it. Second, our method is syntax-based; explicitly stated conditional events in the original PLPs are treated as of most relevant beliefs of the sources and our merging framework preserves these beliefs as much as possible. On the technical aspect, the probability bounds from the merged result are also the aggregation of the bounds from the original PLPs. Different from the methods mentioned in this paragraph, the weights for the conditional events reflect the relevant importance of conditional events to in the original PLPs.

In [Batsell et al., 2002; Osherson and Vardi, 2006], a syntax-based method was proposed for aggregating probabilistic beliefs, where each source gives a set of probabilistic formulas. In their method, all statements from the sources are put together (union) to form a (possibly inconsistent) set and the aggregation procedure is to find a probability distribution that is closest to all the statements in the set. Their method did not explicitly consider the change from a source to the merging result. On the contrary, our method uses the changes to guide the merging procedure.

In [Kern-Isberner and R¨odder, 2004], a method based on the maximum entropy principle is proposed. In their method, a single probability distribution is obtained as the merging result even when the sources are imprecise. On the contrary, in our framework, imprecise PLPs are returned as the result of merging.

In addition, we provided postulates for merging probabilistic beliefs and proved our instantiated operators satisfy most of them. Our postulates generalize the postulates for merging classical knowledge bases provided in [Konieczny et al., 2004], and satisfy properties that should be considered in the view of probability theory. For example, IC8 is the consequence of mean-value property.

On the other hand, IC8 can be reduced to propositional logic:

IC8' Let K1, . . . ,Kn be propositional knowledge bases, and Ki |= φ for all i ∈ [1, n], then the merging result Δ(K1, . . . ,Kn) |= φ.

However, not all propositional merging operators satisfy IC8'. For example. Let operators ΔdD,Sum,Sum IC and ΔdD,Sum,Max IC be as given in [Konieczny et al., 2004]. Let IC = ⊤, K1 = {p, p → q}, and K2 = {p, p → ¬q}, then ΔdD,Sum,Sum IC (K1,K2) |= p but ΔdD,Sum,Max IC (K1,K2) ̸|= p.

In [Kern-Isberner and R¨odder, 2004], a simple probabilistic Pareto principle was proposed stating that the merging result should assign probability value x to (B|A) for merging K1 = · · · = Kn = {(B|A)[x]}. Actually, it is essentially a special case of postulate IC2 when all original PLPs are the same, and all of our operators satisfy this probabilistic Pareto principle even for those which do not generally satisfy IC2. In addition, we do not require the original PLPs to contain only one probabilistic formula.

Conclusion In this paper, we proposed a syntax-based framework for merging PLPs. Explicit conditional events in original PLPs suggest in what aspect an original PLP is relevant to the scenario, and a merging procedure should respect this and therefore should be syntax-based. From our framework, concrete merging operators can be defined and they possess different interesting properties.

We also provided postulates for merging imprecise probabilistic beliefs, and our postulates extend the postulates for merging propositional knowledge bases.

Acknowledgments

We would like to thank Anthony Hunter and Jianbing Ma for their comments on an earlier version of this paper.