A distance-based approach for merging probabilistic knowledge bases

Abstract

In the stages of development of probabilistic expert systems, knowledge merging is a major concern. To deal with knowledge merging problems, several approaches have been put forward. However, in the proposed models, each original probabilistic knowledge base (PKB) is represented by a set of probabilistic functions fulfilling such knowledge base. The drawbacks of the solutions are that the output of model is also a set of probabilistic functions satisfying the resulting PKB and there is no algorithm for implementing the merging process of PKBs in which each of them consists of probabilistic constraints. In this paper, distance-based approach is utilized to propose a new method of merging PKBs to ensure that both the input and output of methods are represented by sets of probabilistic constraints. To this aim, the relationship between the probability rules and the probabilistic constraints, and the several transformation methods for the representation of the original PKB are presented, a set of merging operators (MOs) is proposed, and several desirable logical properties are investigated and discussed. Several algorithms for merging PKBs are presented and the computational complexities of these algorithms are also analyzed and evaluated.

Keywords

Probabilistic knowledge base knowledge merging merging operator algorithm

1 Introduction

Improving appropriate methods to build and maintain the action of knowledge-based systems is very necessary. In security systems, advanced methods of symbolic knowledge representation are used to integrate different, distributed source of information and in this way to make a system be flexible and more effective [1]. It is necessary to transform information stored in knowledge bases when two computer systems need to be integrated or when they exchange content of their knowledge bases [2]. In order to ensure that systems could interact with each other, the knowledge bases originating from these systems have to be consistent. Knowledge merging could be understood as a process of creating a consistent knowledge from a set of knowledge bases deriving from different systems [3]. Knowledge merging is an important problem and its applications are many and diverse. The process of merging could require that knowledge bases should change to ensure the consistency of the merged knowledge base. Therefore, it is a difficult problem and considering these changes is very essential. Knowledge merging could be observed in two respects: Merging knowledge bases which are not similar and merging a set of different representations for same knowledge base but different in representing degree [3]. Therefore, the first task in the knowledge merging process is to solve the inconsistency in knowledge bases. A data filling approach for incomplete set in which missing data is filled in terms of the probability of objects appearing in the mapping sets of parameters could find in [4]. A class of basic inconsistency measures for probabilistic framework has been introduced in [5, 6]. In a probabilistic environment, some strategies have been developed to deal with the inconsistency of a knowledge base. The method of modification of probabilities is one of the most common approaches. This method has been applied in [7 –10].

A general model of knowledge merging problem referring to its inconsistency in distribution aspect was introduced in [3]. In this work, the author worked out and discussed the knowledge merging problem, postulates for knowledge merging and algorithms for this process. In a logic environment, some approaches were proposed to merge propositional knowledge [11 –13]. The main idea of those strategies is often to build a family of MOs: Model-based operators and Formula-based MOs [11], DA² MOs [12], MOs (Quota, Gmin) [13]. MOs in [11, 12] are built in the propositional logic framework and they require all the knowledge bases have the same importance, priority, or feasibility. Moreover, model-based operators cannot take into account inconsistent knowledge bases, but in some cases the information from these bases can be useful while the drawback of formula-based MOs is that the sources of information could be lost in the merging process.

It can be necessary to merge knowledge bases with more structure than the one of propositional logic. In this case weighted approaches are the best way. This is usually represented using possibilistic logic. For possibilistic knowledge merging issue, there are many different methods [14 –16] proposed to solve. Merging process of these methods includes two stages: the separation and the combination. In the first step, each knowledge base is divided into two sub-bases and then the combination step employs different operators to combine different classes of sub-bases. However, there is no possibilistic merging operator satisfying all the postulates for merging possibilistic knowledge bases [16]. Another method proposed in [17] state that keeping weighted information after merging is not always necessary. The models of this work are models of the formula representing the integrity constraints that are maximal with respect to the lexicographic ordering. However, the drawback of the solutions is that the work does not present a representation theorem for the generalized postulates. Moreover, the merging results are usually consistent when using the propositional MOs, while the merging results may be inconsistent if using the possibilistic MOs.

Within the probabilistic framework, knowledge merging is understood as a process of building a joint probability distribution from an input set of low-dimensional distributions [18 –20]. The main purpose of this work is to create a unifying framework for operations with probability distributions that would be used for description of iterative procedures for proposing solving methods. However, the convergence of those algorithms in [18 –20] have not been carefully considered. Another approach is to build MOs based on convex Bregman divergences. A family of probabilistic MOs was first introduced in [21] and they were further studied in [22, 23]. These operators were discussed, evaluated, and compared to each other in detail in [23]. However, the main limitation of approaches proposed in [21 –23] is that it only works with PKBs represented by probability functions.

In the previous work [24], the representation of PKB by probability functions and divergence distance functions is taken into account. A deeply survey is first made on how to compute a set of probability functions satisfying PKB, then the way these functions could be employed to merge probabilistic knowledge bases by proposing two MOs based on divergence distance functions has also been shown. Satisfied probabilistic functions correspond to convex optimization problems or linear programs while all these operators correspond to convex optimization problems. However, the propositions and examples are given but there is no proofs nor algorithms to implement the merging process. Moreover, the output of the proposed model is only the probabilistic functions representing newly merged knowledge base being not represented in the same form as the original knowledge bases.

This paper is extended from our conference paper [24]. It introduces in more details how to calculate a set of probability functions satisfying a PKB, probability merging vector as well as the new probability of constraints in merged PKB. Comparing with the conference paper our contributions are based on the fact that propositions for calculating such values are proved by pointing that there always exists optimal solutions [25] and the output of merged PKB is similar to original PKBs in representation. Besides, main algorithms using to merge PKBs have been put forward by obeying probability rules and condition property of MOs. In addition to pointing out that proposed operators fulfill several desirable properties, two new operators is investigated more and unproven remaining statements have also been made. Finally, a simple but explanatory example to illustrate, analyze and evaluate computational complexity of proposed algorithms is presented.

The rest of this paper is organized as follows. The second section presents the related work on approaches for merging PKBs. Some basic notions about probability function, probabilistic constraint, probability rules, the representation of knowledge bases in a probabilistic framework, and a PKB profile for such bases are presented in the third section. The subsequent section gives distance-based probabilistic MOs. The way to determine probabilistic merging vector as well as the desirable logical properties for MOs are also drawn and discussed in this section. Algorithms for merging PKBs as well as the analysis and evaluation of these algorithms are presented in the next sections. The final section will conclude the main results that have been investigated and give some future works.

2 Related work

The problem of merging PKBs has been studied for a long time and gets a lot of attention in recent years. The idea of probabilistic merging has been introduced and discussed in detail by Vomlel [18]. This work proposed a design and characterization of methods applicable to the merging process of knowledge bases represented by a set of probability distributions. Vomlel used the means of the Iterative Proportional Fitting Procedure (IPFP) to build a joint probability distribution from an input set of low-dimensional distributions. In the case of inconsistent input set, five iterative methods were proposed, namely: CC LCC, AA, GA, and GEM. In the case of consistent input set, iterative proportional fitting procedure have the best convergence rate of five iterative methods for inconsistent input set. However, several properties of methods were not proven and not achieved in this general case due to problems with probability distributions containing zeroes. Vomlel continued proposing another method that extends IPFP to deal with inconsistent constraints, named GEMA [19]. It generalizes the concept of expectation maximization. The time performance of GEMA was extremely sensitive to both the initial knowledge bases and the constraints. As full joint distributions were directly manipulated by GEMA, the advantages of other probabilistic models such as the Bayesian networks (BNs) could be taken. In order to overcome these limitations, Zhang et al. [20] proposed another algorithm called Smooth which addressed both consistent and inconsistent constraints. However, the convergence of Smooth was only proven empirically through experiments. Therefore, the key drawback of the approaches [18 –20] is that PKBs must be represented by probability distributions.

Adamcik [23] associated the geometrical notion of projections by means of a Bregman divergence with the framework of pooling operators to solving the problem of probabilistic knowledge merging. A class of MOs based on minimization of a sum of convex Bregman divergences was introduced and proposed. The most common model of merging operator was defined by $Δ (K_{1}, \dots, K_{n}) = {arg \min_{v \in D^{L}} H (w^{(i)} | | v) : w^{(i)} \in V_{K_{i}}^{L}}$ where L is a finite propositional language, D^L is the set of all probability functions over, H is a Bregman divergence function and each PKB K_i for 1 ≤ i ≤ n over L is a set of constraints on probability functions over L such that the set of all probability functions satisfying the constraints in K_i forms a nonempty closed convex subset $V_{K_{i}}^{L}$ of D^L. The ${\hat{Δ}}^{D}$ -merging operator was defined by using Squared Euclidean Distance and extending the LinOp-pooling operator, in the sense that it coincides with LinOp in the special case when each knowledge base admits only a single probability function. The linear Entropy Operator was defined by using Kullback-Leibler Divergence while the Linear Renyi Operator was employed Renyi Divergence. The linear Entropy Operator was similar to the Linear Euclidean Operator built by Osherson and Vardi in [26] and contained reversed parameter compared to Social Entropy Operator proposed by Wilmers in [21]. Adamcik also showed that MOs satisfied the natural principle of consistency. However, original PKBs and resulting knowledge base in this work were only represented by probabilistic functions and placed in the context of the propositional language. Moreover, more general applications as well as the rate of convergence of the algorithm need to be carefully investigated.

The new approach proposed in this paper is compared with existing ones given in the literature. Like the merging methods given in [18 , 26], this new approach also employs distance functions to find a set of probability functions representing common PKB. However, the first difference is that some propositions introduced in [9, 10] are applied to find probabilistic functions satisfying original PKB that is represented by probabilistic constraints. The second difference is that probability rules proposed [27] are employed to find new value of probabilistic constraints in common PKB.

3 Basic notions

A sample space, denoted by $S$ , is a set which includes all possible outcomes of a statistical experiment. A finite set of possible outcomes forms an event. A set of events denoted by $\hat{ɛ}$ , $\hat{ɛ} = {E_{1}, \dots, E_{n}}$ . Given $F, G \in \hat{ɛ}$ , the intersection F and G, denoted by F ∩ G, is an event which contains all elements that are common to Fand G; the negation of event F, denoted by ¬F, is abbreviated by $\bar{F}$ . A complete conjunction of $\hat{ɛ}$ , denoted by Θ, $Θ = {\tilde{E}}_{1} \cap {\tilde{E}}_{2} \cap \dots \cap {\tilde{E}}_{n}$ where ${\tilde{E}}_{i} = {E_{i}, {\bar{E}}_{i}}$ . A set of all complete conjunctions of $\hat{ɛ}$ , denoted by $\land (\hat{ɛ}), \land (\hat{ɛ}), = {Θ_{1}, \dots, Θ_{2^{n}}}$ . A complete conjunction $Θ \in \land (\hat{ɛ})$ satisfies an event F, denoted by Θ ⊨ F, iff F appears in Θ. Also, it said that Θ ⊨ {E₁, …, E_n} if Θ ⊨ E_i, ∀ 1 ≤ i ≤ n. Let $℧ (X) = {Θ \in △ (\hat{ɛ}) | Θ ⊨ X}$ , where X is an event or a set of events. Let $m = | Λ (\hat{ɛ}) | = 2^{n}$ be the numbers of complete conjunctions of $\hat{ɛ}$ . Let $ℝ_{\geq 0}$ be the set of non-negative real values including +∞. Let $ℝ_{[0, 1]}$ be the set of all real values from 0 to 1.

Definition 1. Let $P : Λ (\hat{ɛ}) \to ℝ_{[0, 1]}$ such as, $\sum_{i = 1}^{m} P (Θ_{i}) = 1, P$ is called a probability function.

Let $\hat{P} (\hat{ɛ})$ be a set of all probability functions $P$ over set of events $\hat{ɛ}$ , defined by $\hat{P} (\hat{ɛ}) = {P (Θ_{1}), \dots, P (Θ_{2^{n}})}$ . Let $\vec{ϑ} = (ϑ_{1}, \dots, ϑ_{m})^{T}$ be a column vector, where an auxiliary variable ϑ_i corresponding to a probability $P (Θ_{i})$ .

Proposition 1. Let $F, G \in \hat{ɛ}$ Probability function $P$ satisfies the following probability axioms:

( P0 ) $P (F) = \sum_{Θ \in Λ (\hat{ɛ}) : Θ ⊨ F} P (Θ)$

( P1 ) $P (FG) = P (F) P (G / F) = P (G) P (F / G)$ provided $P (G) > 0, P (F) > 0$

( P2 ) $P (G_{k} | F) = \frac{P (G_{k}) P (F | G_{k})}{\sum_{i = 1}^{n} P (G_{i}) P (F | G_{i})} \forall k = 1, . . ., n$

( P3 ) $P (F) = \sum_{i = 1}^{n} P (G_{i}) P (F | G_{i})$

( P4 ) $P (F) = 1 - P (\bar{F})$

Any countable sequence of disjoint sets (synonymous with mutually exclusive events) F₁, F₂, … F_n satisfies

( P5 ) $P (\cup_{i = 1}^{\infty} F_{i}) = \sum_{i = 1}^{\infty} P (F_{i})$

Proof. Axiom P0 may be inferred easily from the Definition 1. Axiom P1 is the result of Definition 2.10, axiom P2 is the result of Theorem 2.14, axiom P3 is the result of Theorem 2.13, axiom P4 is the result of Theorem 2.9, axiom P5 is the result of Corollary 2.2, which were proposed and proved in [27].□

Definition 2. Let $F, G \in \hat{ɛ}$ and $ρ \in ℝ_{[0, 1]}$ . A probabilistic constraint is an expression of the form c [ρ],where c = (F|G).

Intuitively, a constraint (F|G) [ρ] means that our knowledge in F given that G hold has probability value ρ. If F does not depend on G,G ≡ ⊤ , (F| ⊤) [ρ], is abbreviated by (F) [ρ].

Definition 3. A PKB, denoted by $K = 〈 κ_{1}, \dots κ_{h} 〉$ , is a finite set of probabilistic constraints, where κ_i = c_i [ρ_i] for all i = 1, … h.

Let $h = | K |$ be the total number of constraints in $K$ . A probability function $P \in \hat{P} (\hat{ɛ})$ satisfies a probabilistic constraint c [ρ], denoted by $P ⊨ c [ρ]$ iff $P (FG) = ρ P (G)$ . A probability function $P$ satisfies $K$ denoted by $P ⊨ K$ iff $P ⊨ k \forall k \in K$ . Let $℧ (K) = {P \in \overset{⌢}{P} (\hat{ɛ}) | P ⊨ K}$ be the set of all probability function values satisfying $K$ . The set of constraints of $K_{1} \cup K_{2}$ corresponds to $℧ (K_{1} \cup K_{2}) = ℧ (K_{1}) \cap ℧ (K_{2})$ .

Definition 4. Let $K$ be a set of PKBs. Inconsistency measure $J M$ is a function $J M : K \to ℝ_{\geq 0}$ such that $J M (K) = 0$ if and only if $℧ (K) \neq \emptyset, K \in K$ .

Definition 5. A PKB $K$ is consistent, denoted by 𝒦 ⊯ ⊥, iff $℧ (K) \neq \emptyset$ . Otherwise, $K$ is inconsistent, denoted by $K ⊨ ⊥$ .

Definition 6. A PKB profile, denoted by $B = {K_{1}, \dots K_{n}}$ is a finite set of PKBs satisfying the following conditions:

$\forall K_{i} \in B : K_{i} ⊭ ⊥$

$\forall K_{i}, K_{j} (i \neq j)$ :

$+ | K_{i} | = | K_{j} |$

$+ \forall c_{k} [ρ k] \in K_{i}; c_{k^{'}}^{'} [ρ k^{'}] \in K_{j}; k = k^{'} : c_{k} = c_{k^{'}}^{'}$

$K_{i}$ is consistent to $K_{2}$ iff they satisfy condition 2, denoted by $K_{1} | | K_{2}$ . Otherwise, $K_{1} ∦ K_{2}$ .

4 Distance-based probabilistic MOs

4.1 Desirable properties

In the rest later, several properties of our family of probabilistic MOs used to characterize MOs will be put forward. Let Γ be a function $Γ : B \to ℧ (B)$ that maps a PKB profile onto a set of all probability function values satisfying $B$ . The following definition is similar to a set of logical properties which was stated in [3, 28].

Definition 7. Let $B = {K_{1}^{'}, \dots, K_{n}^{'}}$ and, $C = {K_{1}^{'},$ $\dots, K_{m}^{'}}$ be PKB profiles. Let $K$ be a consistent PKBs. Function $Γ : B \to υ (B)$ is called a probabilistic merging operator iff the following properties hold:

(CP1) Consistency Principle. If $\cap_{i = 1}^{n} ℧ (K_{i}) \neq \emptyset$ then $Γ (B) \subseteq \cap_{i = 1}^{n} ℧ (K_{i})$

The property CP1 assures that if the input PKB profile is consistent then the result of merging will be a subset of the intersection of the set of all probability function values satisfying $K_{i}$ .

(SCP) Strong Consistency Principle. If $\cap_{i = 1}^{n} ℧ (K_{i})$ ≠∅ then $Γ (B) = \cap_{i = 1}^{n} ℧ (K_{i})$

The property SCP assures that if the input PKB profile is consistent then the result of merging will be the intersection of the set of all probability function values satisfying $K_{i}$ .

(IP) Ignorance Principle. $\forall K = \emptyset : Γ (B \cup K) = Γ (B)$

The property IP state that the result of merging process should not be affected when an empty PKB is added.

(EP) Equivalence Principle. If there exists a permutation μ on {1, …, n} such that $℧ (K_{i}) = ℧ (K_{μ (i)}^{'})$ then $Γ (B) = Γ (C) .$

The property EP implies that result of merging process should not be contingent on the occurrence order of PKBs.

(CP2) Collegiality Principle. If $\cap_{i = 1}^{m} ℧ (K_{i}) \neq \emptyset$ and $Γ (B) \subseteq \cap_{i = 1}^{m} ℧ (K_{i}^{'})$ then $Γ (B \cup C) = Γ (B)$ .

The property CP2 implies that the result of merging process should not be affected when a PKB profile which the intersection of the set of all probability function values satisfying $K_{i}$ in it contains the merging result of other is added.

(AP) Agreement. If $Γ (B) \cap Γ (C) \neq \emptyset$ then $Γ (B) \cap Γ (C) = Γ (B \cup C)$ .

This property states that the intersection of the merging results of two distinct sets of knowledge bases is not empty, it should be similar to the merging of all PKBs in those two sets.

(DP) Disagreement Principle. If $\cap_{i = 1}^{m} ℧ (K_{i}^{'}) \neq \emptyset$ and $\exists K_{1} \in B$ , $K_{2} \in C$ : $K_{1} ∦ K_{2}$ then $Γ (B) \cap Γ (C) \neq \emptyset$ .

This property states that if the merged PKBs in $B$ is inconsistent with merged PKBs in $C$ of a distinct set of knowledge bases and PKBs in $C$ are collectively consistent, the merging results of PKBs in both $B$ and $C$ is also inconsistent with $B$ .

(SDP) Strong Disagreement Principle. $Γ (B) \cap Γ (C) = \emptyset$ .

This property states that the intersection of the merging results should be empty.

4.2 Satisfied probabilistic functions

Definition 8. Function φ (H, Θ) is called an indicator function whenever it is defined as follows: $φ : \hat{ɛ} \times Λ (\hat{ɛ}) \to ℝ_{[0, 1]},$ where $φ (H, Θ) = {\begin{matrix} 1 if Θ ⊨ H \\ 0 otherwise \end{matrix}$

Definition 9. (Characteristic Matrix). $A_{K}$ is called a characteristic matrix of $K$ whenever it is defined as follows: $A_{K} = (a_{ij}) \in ℝ^{h \times m}$ where $a_{ij} = φ (F_{i} \cap G_{i}, Θ_{j}) (1 - ρ_{i}) - φ ({\bar{F}}_{i} \cap G_{i}, Θ_{j}) ρ_{i} .$

Intuitively, a_ij is either 1-ρ, -ρ or 0 dependent on whether F_i ∩ G_i satisfies Θ_j, F_i ∩ G_i satisfies Θ_j, or not computable.

Proposition 2. p-norm satisfied probabilistic vector of $K$ , denoted by ${\vec{v}}_{K}^{p}$ , corresponding to ${\vec{ϑ}}^{*}$ of the optimal solution of the following optimization problem: $arg \min_{\vec{ϑ} \in ℝ^{m}} | | A_{K} \vec{ϑ} | |_{ρ}$ (1) $subject to : \sum_{i = 1}^{m} ϑ_{i} = 1; \vec{ϑ} \geq \vec{0}$ (2)

Proposition 2 is the result of Proposition 4 which was proposed and proved in [10].

Proposition 3. 1-norm satisfied probabilistic vector of $K$ , denoted by ${\vec{v}}_{K}^{1}$ , corresponding to ${\vec{ϑ}}^{*}$ of the optimal solution of the following linear programming problem: $arg \min_{(\vec{ϑ}, \vec{λ}) \in ℝ^{m + h}} \sum_{i = 1}^{h} λ_{i}$ (3) $subject to : A_{K} \vec{ϑ} - \vec{λ} \leq \vec{0}; A_{K} \vec{ϑ} + \vec{λ} \geq \vec{0}$ (4) $\sum_{i = 1}^{m} ϑ_{i} = 1; \vec{ϑ} \geq \vec{0}; \vec{λ} \geq \vec{0}$ (5)

Proposition 3 is the result of Proposition 5 which was proposed and proved in [10].

Proposition 4. ∞ -norm satisfied probabilistic vector of $K$ , denoted by ${\vec{ϑ}}_{K}^{\infty}$ , corresponding to ${\vec{ϑ}}^{*}$ of the optimal solution of the following linear programming problem: $arg \min_{(\vec{ϑ}, \vec{λ}) \in ℝ^{m + 1}} λ$ (6) $subject to : A_{K} \vec{ϑ} - \vec{1} λ \leq \vec{0}; A_{K} \vec{ϑ} + \vec{1} λ \geq \vec{0}$ (7) $\sum_{i = 1}^{m} ϑ_{i} = 1; \vec{ϑ} \geq \vec{0}; λ \geq 0$ (8)

Proposition 4 is the result of Proposition 6 which was proposed and proved in [10].

Definition 10. ${\bar{A}}_{K}$ is called a diagonal double matrix of $K$ whenever it is defined as follows: ${\bar{A}}_{K} = ({\vec{a}}_{ij}) \in ℝ^{h \times 2 h}$ where ${\vec{a}}_{ij} = {\begin{matrix} 1 & if i = j and i, j = 1, \dots, h \\ - 1 & if j - i = h and j = h + 1, \dots, 2 h \\ 0 & otherwise \end{matrix}$

Let $\vec{Δ} (\vec{ℓ}, \vec{ζ}) = (ℓ_{1}, . . ., ℓ_{h}, ζ_{1}, . . . ζ_{h})^{T}$ be a column vector.

Proposition 5. Unnormalized satisfied probability vector of $K$ , denoted by ${\vec{ϑ}}_{K}^{u}$ , corresponding to ${\vec{ϑ}}^{*}$ of the optimal solution of the following optimization problem: $arg \min_{(\vec{ϑ}, \vec{λ}) \in ℝ^{m \times 2 h}} \sum_{i = 1}^{h} (ℓ_{i} + ζ_{i})$ (9) $subject to : {\bar{A}}_{K} \vec{△} \leq \vec{1} - \vec{ρ}$ (10) ${\bar{A}}_{K} \vec{△} \geq - \vec{ρ}$ (11) $\sum_{i = 1}^{m} ϑ_{i} = 1; \vec{ϑ} \geq \vec{0}$ (12) $(ρ_{i} + ℓ_{i} - ζ_{i}) \sum_{Θ \in ℧ (F_{i} \cap G_{i})} ϑ_{i} - \sum_{Θ \in ℧ (G_{i})} ϑ_{i} = 0$ (13)

Proposition 5 is the result of Proposition 9 which was proposed and proved in [10].

Proposition 6. $℧ (K) = {\vec{ϑ}}_{K}^{1} = {\vec{ϑ}}_{K}^{p} = {\vec{ϑ}}_{K}^{\infty} = {\vec{ϑ}}_{K}^{u}$

Proposition 6 is the result of Proposition 5 which was proposed and proved in [24].

4.3 Probabilistic MOs

For any $x \in \hat{P} (\hat{ɛ})$ , $y \in \hat{P} (\hat{ɛ})$ , it is said that x dominates y, denoted by x ≫ y, if x_i = 0 implies y_i = 0 ∀1 ≤ i ≤ m. Let I (x) = {i : x_i ≠ 0}.

Definition 11. For a set of probability functions $\hat{P} (\hat{ɛ})$ , a divergence distance function, is a map $d : \hat{P} (\hat{ɛ}) \times \hat{P} (\hat{ɛ}) \to ℝ_{\geq 0}$ satisfiying the following conditions:

d (x, y) =0 iff x = y

d (x, y) ≥0

d (x, y) + d (y, z) ≥0, d (x, z) =0

where x, y, and z are probability functions.

Definition 12. Function d^SQ (x, y) is called a SQ divergence distance function whenever it is defined as follows: $d^{SQ} : \hat{P} (\hat{ɛ}) \times \hat{P} (\hat{ɛ}) \to ℝ_{\geq 0}$ , $d^{SQ} (x, y) = \sum_{i \in I (y)} (x_{i} - y_{i})^{2}$

Definition 13. Function d^RB (x, y) is called a Renyi-B divergence distance function whenever it is defined as follows: $d^{RB} : \hat{P} (\hat{ɛ}) \times \hat{P} (\hat{ɛ}) \to ℝ_{\geq 0}$ , $d^{RB} (x, y) = \sum_{i \in I (y)} [(x_{i})^{r} - (y_{i})^{r} - r (x_{i} - y_{i})^{r} (y_{i})^{r - 1}]$ for 1 < r ≤ 2

Definition 14. Function d^KL (x, y) is called a KL divergence distance function whenever it is defined as follows: $d^{KL} : \hat{P} (\hat{ɛ}) \times \hat{P} (\hat{ɛ}) \to ℝ_{\geq 0}$ , $\begin{matrix} d^{KL} (x, y) = {\begin{matrix} \sum_{i \in I (y)} x_{i} log \frac{x_{i}}{y_{i}} if y ≫ x \\ + \infty otherwise \end{matrix} \end{matrix}$

4.3.1 The probabilistic merging operator Γ^SQ

Proposition 7. Probability merging vector of $B$ , denoted ${\vec{y}}_{B}^{SQ}$ , is the optimal solution of the following optimization problem: $\begin{matrix} \arg \min_{{\vec{y}}_{B}^{SQ} \in ℝ^{n}} (\sum_{i = 1}^{n} d^{SQ} (x_{i}, y) : y \in \hat{P} (\hat{ɛ}); \\ x_{i} \in ℧ (K_{i}); K_{i} \in B) \end{matrix}$ (14) $subject to \sum_{i = 1}^{n} y_{i} = 1; {\vec{y}}_{B}^{SQ} \geq \vec{0}$ (15)

Proof. Let $C = {{\vec{y}}_{B}^{SQ} \in R^{n} | \sum_{i = 1}^{n} y_{i} = 1$ , ${\vec{y}}_{B}^{SQ} \geq \vec{0}}$ be a constraint set. Let $f ({\vec{y}}_{B}^{SQ}) = \sum_{i = 1}^{n} d^{SQ} (x_{i}, y)$ be an objective function, where $x_{i} \in ℧ (K_{i})$ . Suppose that $y$ is optimal for (14). Then there exists ${\vec{y}}_{B}^{SQ}$ such that $y = \sum_{i = 1}^{n} d^{SQ} (x_{i}, y)$ and $y \in {\vec{y}}_{B}^{SQ}$ , ${\vec{y}}_{B}^{SQ}$ is an optimal point. This leads to C is nonempty and thus ${\vec{y}}_{B}^{SQ}$ is feasible and attains the optimal value f^* Therefore vector ${\vec{y}}_{B}^{SQ}$ is the optimal solutions of (14) [25].□

Definition 15. (SQ Merging Operator). Function $Γ^{SQ} : B \to ℧ (B)$ is called SE Merging Operator whenever it is defined as follows: $Γ^{SQ} (B) = {\vec{y}}_{B}^{SQ}$ .

Proposition 8. Γ ^SQ fulfills all properties.

Proof. SCP. Suppose $\vec{y} \in Γ^{SQ} (B)$ . By Definition 15, $\vec{y}$ is the optimal value of problem (14) and then there exists $\vec{x} \in ℧ (K_{i})$ for i = 1, …, n. Since $\cap_{i = 1}^{m} ℧ (K_{i}) \neq \emptyset$ , $\vec{y} = \vec{x}$ . Therefore, $\vec{y} \in \cap_{i = 1}^{m} ℧ (K_{i})$ . Suppose $\vec{y} \in \cap_{i = 1}^{m} ℧ (K_{i})$ . There exists $\vec{y} \in ℧ (K_{i})$ for i = 1, …, n. By Proposition 7, $\vec{y} \in Γ^{SQ} (B)$ .□

CP1. This property is easily result from SCP.

IP and EP. Follows from Definition 15

AP. Firstly, $Γ^{SQ} (B) \cap Γ^{SQ} (C) \subseteq Γ^{SQ} (B \cup C)$ needs to be proven. Since $Γ^{SQ} (B) \cap Γ^{SQ} (C) \neq \emptyset$ , there is some $\vec{y} = Γ^{SQ} (B) \cap Γ^{SQ} (C)$ . For any such $\vec{y}$ there exist $\vec{α} = (α_{1}, \dots α_{n}) \in Γ^{SQ} (B)$ and $\vec{β} = (β_{1}, \dots, β_{m}) \in Γ^{SQ} (C)$ . By Proposition 7, $f^{*} ({\vec{y}}_{B}^{SQ})$ is the optimal value of problem (14), where $f ({\vec{y}}_{B}^{SQ}) = \sum_{i = 1}^{n} d^{SQ} (α_{i}, y)$ , $α_{i} \in ℧ (K_{i})$ . $f^{*} ({\vec{y}}_{C}^{SQ})$ is the optimal value of problem (14), where $f ({\vec{y}}_{C}^{SQ}) = \sum_{i = 1}^{m} d^{SQ} (β_{i}, y)$ , $β_{i} \in ℧ (K_{i}^{'})$ , $y \in \hat{P} (\hat{ɛ})$ . It follows that $f^{*} ({\vec{y}}_{B}^{SQ}) + f^{*} ({\vec{y}}_{C}^{SQ}) \leq f^{*} ({\vec{y}}_{B \cup C}^{SQ})$ and the same $\vec{y}, \vec{α}, \vec{β}$ globally minimize the sum $\sum_{i = 1}^{n} d^{SQ} (α_{i}, y) + \sum_{i = 1}^{m} d^{SQ} (β_{i}, y)$ subject to $α_{i} \in ℧ (K_{i})$ , 1 ≤ i ≤ n and $β_{i} \in ℧ (K_{i}^{'}), 1 \leq i \leq m$ . Thus $\vec{y} \in Γ^{SQ} (B \cup C)$ and $f^{*} {\vec{y}}_{B}^{SQ} + f^{*} {\vec{y}}_{C}^{SQ} = f^{*} ({\vec{y}}_{B \cup C}^{SQ})$ . Therefore, $Γ^{SQ} (B) \cap Γ^{SQ} (C) \subseteq Γ^{SQ} (B \cup C)$

Secondly, $Γ^{SQ} (B \cup C) \subseteq Γ^{SQ} (B) \cap Γ^{SQ} (C)$ needs to be proven. Suppose $\vec{y} = (α_{i}, . . ., α_{n}, β_{1}, . . ., β_{m}) \in Γ^{SQ} (B \cup C)$ .

Then $f^{*} ({\vec{y}}_{B \cup C}^{SQ}) = \sum_{i = 1}^{n} d^{SQ}$ $(α_{i}, y) + \sum_{i = 1}^{m} d^{SQ}$ (β_i, y) is the optimal value of optimization problem (14). Now assume that it does not exist $f^{*} ({\vec{y}}_{B}^{SQ}) = \sum_{i = 1}^{n} d^{SQ} (α_{i}, y)$ and $f^{*} ({\vec{y}}_{C}^{SQ}) = \sum_{i = 1}^{m} d^{SQ} (β_{i}, y)$ then this would contradict the minimality of either $f^{*} ({\vec{y}}_{B}^{SQ})$ or $f^{*} ({\vec{y}}_{C}^{SQ})$ . Thus $\vec{y} \in Γ^{SQ} (B) \cap Γ^{SQ} (C)$ .

Therefore, $Γ^{SQ} (B \cup C) \subseteq Γ^{SQ} (B) \cap Γ^{SQ} (C)$ .

SDP. The proof for this property is similar to the proof for 4.1.5 in [23].

DP. This property is easily result from SDP.

CP2. By property SCP, since $\cap_{i = 1}^{m} ℧ (K_{i}^{'}) \neq \emptyset$ , it follwows that $Γ^{SQ} (C) = \cap_{i = 1}^{m} ℧ (K_{i}^{'})$ . So then $Γ^{SQ} (B) \subseteq Γ^{SQ} (C)$ . Therefore, $Γ^{SQ} (B) \cap Γ^{SQ} (C) = Γ^{SQ} (B)$ . Using property AP, $Γ^{SQ} (B) \cap Γ^{SQ} (C) = Γ^{SQ} (B \cup C)$ showing that $Γ^{SQ} (B) = Γ^{SQ} (B \cup C)$ .

4.3.2 The probabilistic merging operator Γ^RB

Proposition 9. Probability merging vector of $B$ , denoted by ${\vec{y}}_{B}^{RB}$ , is the optimal solution of the following optimization problem:

$\begin{matrix} arg \min_{{\vec{y}}_{B}^{RB}} \in ℝ^{n} (\sum_{i = 1}^{n} d^{RB} (x_{i}, y) : \\ y \in \hat{P} (\hat{ɛ}); x_{i} \in ℧ (K_{i}); K_{i} \in B) \end{matrix}$ (16) $subject to \sum_{i = 1}^{n} y_{i} = 1; {\vec{y}}_{B}^{RB} \geq \vec{0}$ (17)

Proof. Let $f ({\vec{y}}_{B}^{RB}) = \sum_{i = 1}^{n} d^{RB} (x_{i}, y)$ be an objective function, where $x_{i} \in ℧ (K_{i})$ .□

Let $C = {{\vec{y}}_{B}^{RB} \in ℝ^{n} | \sum_{i = 1}^{n} y_{i} = 1, {\vec{y}}_{B}^{RB} \geq \vec{0}}$ be a constraint set. Suppose that $𝓎$ is optimal for (16). Then there exists ${\vec{y}}_{B}^{RB}$ such that $𝓎 = \sum_{i = 1}^{n} d^{RB} (x_{i}, y)$ and $y \in {\vec{y}}_{B}^{RB}$ , ${\vec{y}}_{B}^{RB}$ is an optimal point. This leads to $C$ is nonempty and thus ${\vec{y}}_{B}^{RB}$ is feasible and attains the optimal value f^* Therefore vector ${\vec{y}}_{B}^{RB}$ is the optimal solutions of (16) [25].

Definition 16. (RB Merging Operator). Function $Γ^{RB} : B \to ℧ (B)$ is called RB Merging Operator whenever it is defined as follows: $Γ^{RB} (B) = {\vec{y}}_{B}^{RB}$ .

Proposition 10. Γ ^RB fulfills all properties.

Proof. The proof for properties of Γ^RB is similar to that of Γ^SQ by using distance function d^RB (x, y) instead of d^SQ (x, y).□

4.3.3 The probabilistic merging operator Γ^LE

Proposition 11. Probability merging vector of $B$ , denoted by ${\vec{y}}_{B}^{LE}$ , is the optimal solution of the following optimization problem:

$\begin{matrix} arg \min_{{\vec{y}}_{B}^{LE} \in ℝ^{n}} (\sum_{i = 1}^{n} d^{KL} (x_{i}, y) : \\ y \in \hat{P} (\hat{ɛ}); x_{i} \in ℧ (K_{i}); K_{i} \in B) \end{matrix}$ (18) $subject to \sum_{i = 1}^{n} y_{i} = 1; {\vec{y}}_{B}^{LE} \geq \vec{0}$ (19)

Proof. Let $f ({\vec{y}}_{B}^{LE}) = \sum_{i = 1}^{n} d^{KL} (x_{i}, y)$ be an objective function, where $x_{i} \in ℧ (K_{i})$ .□

Let $C = {{\vec{y}}_{B}^{LE} \in ℝ^{n} | \sum_{i = 1}^{n} y_{i} = 1$ , ${\vec{y}}_{B}^{LE} \geq \vec{0}}$ be a constraint set. Suppose that y is optimal for (18). Then there exists ${\vec{y}}_{B}^{SE}$ such that $y = \sum_{i = 1}^{n} d^{KL} (x_{i}, y)$ and $y \in {\vec{y}}_{B}^{LE}$ , ${\vec{y}}_{B}^{LE}$ is an optimal point. This leads to C is nonempty and thus ${\vec{y}}_{B}^{LE}$ is feasible and attains the optimal value f^*. Therefore, vector ${\vec{y}}_{B}^{LE}$ is the optimal solutions of (18) [25].

Definition 17. (LE Merging Operator). Function $Γ^{LE} : B \to ℧ (B)$ is called LE Merging Operator whenever it is defined as follows: $Γ^{LE} (B) = {\vec{y}}_{B}^{LE}$

Proposition 12. Γ ^LE fulfills CP1, SCP, IP, EP, AP, CP2.

Proof. AP. Firstly, $Γ^{LE} (B) \cap Γ^{LE} (C) \subseteq Γ^{LE} (B \cup C)$ needs to be proven. Since $Γ^{LE} (B) \cap Γ^{LE} (C) \neq \emptyset$ , there is some $\vec{y} \in Γ^{LE} (B) \cap Γ^{LE} (C)$ . For any such $\vec{y}$ there exist $\vec{α} = (α_{i}, \dots, α_{n}) \in Γ^{LE} (B)$ and $\vec{β} = (β_{i}, \dots, β_{m}) \in Γ^{LE} (C)$ By Proposition 11 $f^{*} ({\vec{y}}_{B}^{LE})$ is the optimal value of problem (18) where $f ({\vec{y}}_{B}^{LE}) = \sum_{i = 1}^{n} d^{KL} (α_{i}, y), α_{i} \in ℧ (K_{i})$ ; $f^{*} ({\vec{y}}_{C}^{LE})$ is the optimal value of problem (18), where $f ({\vec{y}}_{C}^{LE}) = \sum_{i = 1}^{m} d^{KL} (β_{i}, y), β_{i} \in ℧ (K_{i}^{'}), y \in \overset{⌢}{P} (\hat{ɛ})$ . It follows that $f^{*} ({\vec{y}}_{B}^{LE}) + f^{*} ({\vec{y}}_{C}^{LE}) \leq f^{*} ({\vec{y}}_{B \cup C}^{LE})$ and the same $\vec{y}, \vec{α}, \vec{β}$ globally minimize the sum $\sum_{i = 1}^{n} d^{KL} (α_{i}, y) + \sum_{i = 1}^{m} d^{KL} (β_{i}, y)$ subject to $α_{i} \in ℧ (K_{i}), 1 \leq i \leq n$ and $\vec{β} \in ℧ (K_{i}), 1 \leq i \leq m$ . Thus $\vec{y} \in Γ^{LE} (B \cup C)$ and if $f^{*} ({\vec{y}}_{B}^{SE})$ and $f^{*} ({\vec{y}}_{C}^{SE})$ are not equal to +∞ then $f^{*} ({\vec{y}}_{B}^{LE}) + f^{*} ({\vec{y}}_{C}^{LE}) = f^{*} ({\vec{y}}_{B \cup C}^{LE})$

Therefore, $Γ^{LE} (B) \cap Γ^{LE} (C) \subseteq Γ^{LE} (B \cup C)$ . □

Secondly, $Γ^{LE} (B \cup C) \subseteq Γ^{LE} (B) \cap Γ^{LE} (C)$ needs to be proven. Suppose $\vec{y} = (α_{i}, \dots, α_{n}, β_{1}, \dots, β_{m})$ $\in Γ^{LE} (B \cup C)$ .

Then $f^{*} ({\vec{y}}_{B \cup C}^{LE}) = \sum_{i = 1}^{n} d^{KL} (α_{i}, y) + \sum_{i = 1}^{m}$ d^KL (β_i, y) is the optimal value of problem (18). Now assume that it does not exist $f^{*} ({\vec{y}}_{B}^{LE}) = \sum_{i = 1}^{n} d^{KL} (α_{i}, y) \neq + \infty$ and $f^{*} ({\vec{y}}_{C}^{LE}) = \sum_{i = 1}^{m}$ d^KL (β_i, y)≠ + ∞ then this would contradict the minimality of either $f^{*} ({\vec{y}}_{B}^{LE})$ or $f^{*} ({\vec{y}}_{C}^{LE})$ . Thus $\vec{y} \in Γ^{LE} (B) \cap Γ^{LE} (C)$ . Therefore, $Γ^{LE} (B \cup C) \subseteq Γ^{LE} (B) \cap Γ^{LE} (C)$ .

The proof for remaining properties of Γ^LE is similar to that of Γ^SQ by using distance function d^SQ (x, y) instead of d^KL (x, y).

4.3.4 The probabilistic merging operator Γ^SE

Proposition 13. Probability merging vector of $B$ , denoted by ${\vec{y}}_{B}^{SE}$ , is the optimal solution of the following optimization problem:

$\begin{matrix} arg \min_{{\vec{y}}_{B}^{SE} \in ℝ^{n}} (\sum_{i = 1}^{n} d^{KL} (x_{i}, y) : \\ y \in \hat{P} (\hat{ɛ}); x_{i} \in ℧ (K_{i}); K_{i} \in B) \end{matrix}$ (20) $subject to \sum_{i = 1}^{n} y_{i} = 1; {\vec{y}}_{B}^{SE} \geq \vec{0}$ (21)

Proof. Let $C = {{\vec{y}}_{B}^{SE} \in ℝ^{n} | \sum_{i = 1}^{n} y_{i} = 1, {\vec{y}}_{B}^{SE} \geq \vec{0}}$ be a constraint set. Suppose that $Y$ is optimal for (20). Let $f ({\vec{y}}_{B}^{SE}) = \sum_{i = 1}^{n} d^{KL} (y, x_{i})$ be an objective function, where $x_{i} \in ℧ (K_{i})$ . Then there exists ${\vec{y}}_{B}^{SE}$ such that $y = \sum_{i = 1}^{n} d^{KL} (y, x_{i})$ and $y \in {\vec{y}}_{B}^{SE}, {\vec{y}}_{B}^{SE}$ is an optimal point. This leads to C is nonempty and thus ${\vec{y}}_{B}^{SE}$ is feasible and attains the optimal value f^*. Therefore vector ${\vec{y}}_{B}^{SE}$ is the optimal solutions of (20) [25].□

Definition 18. (SE Merging Operator). Function $Γ^{SE} : B \to ℧ (B)$ is called SE Merging Operator whenever it is defined as follows: $Γ^{SE} (B) = {\vec{y}}_{B}^{SE}$ .

Proposition 14. Γ ^SE fulfills CP1, SCP, IP, EP, CP2.

Proof. CP2. Since $\cap_{i = 1}^{m} ℧ (K_{i}^{'}) \neq \emptyset$ it follows that $f^{*} ({\vec{y}}_{C}^{SE}) = \sum_{i = 1}^{m} d^{KL} (y, β_{i}) = 0 \neq + \infty$ . It is sufficient to consider the case when $\sum_{i = 1}^{m} d^{KL} (y, α_{j})$ is +∞. However, in this case both Γ^SE (B ∪ C) and Γ^SE (B) are equal to $\hat{P} (\hat{ɛ})$ . Therefore, Γ^SE (B ∪ C) = Γ^SE (B). The proof for remaining properties of Γ^SE is similar to that of Γ^LE by inverting two arguments in distance function d^KL (x, y).□

4.3.5 The probabilistic merging operator Γ^HU

Let $B = {K_{1}, . . ., K_{n}}$ . Let $I_{B} = {1, . . ., n}$

Let

$\begin{matrix} ℋ = {℧ : \exists I_{ℋ} \subseteq I_{ℬ} : ℧ = \underset{i \in I_{ℋ}}{\cap} ℧ (K_{i}) \neq \emptyset and \\ \forall j \in I_{ℬ} \ I_{ℋ} (\underset{i \in I_{ℋ}}{\cap} ℧ (K_{i})) \cap ℧ (K_{j}) \neq \emptyset} \end{matrix}$ (22)

Proposition 15. Let ${\hat{A}}_{B} = ({\vec{a}}_{1}^{T} . . . {\vec{a}}_{| H |}^{T})$ be profile matrix, where $\vec{α} = ℧_{i}$ with $℧_{i} \in H$ . There exist positive real numbers λ_i ∈ [0, 1] with $\sum_{i = 1}^{| H |} λ_{i} = 1$ such that, ${\vec{y}}_{B}^{HU} = {\hat{A}}_{B} \vec{λ}$ (23)where $\vec{λ} = (λ_{1}, . . ., λ_{| H |})^{T}$

Proof. Let $℧ (K_{1}) = 〈 ρ_{1}, . . ., ρ_{n} 〉; ℧ (K_{2}) = 〈 ζ_{1}, . . ., ζ_{n} 〉;$ $℧ (K_{3}) = 〈 ρ_{1}, . . ., ρ_{n} 〉$ □

From Definition 6, it follows that $B = {K_{1}$ , $K_{2}, K_{3}}$ . From (22), $H = {℧_{1}, ℧_{2}}$ , showing clearly that ${\vec{y}}_{B}^{HU} = (\begin{matrix} ρ_{1} & ζ_{1} \\ \dots & \dots \\ ρ_{n} & ζ_{n} \end{matrix}) (\begin{matrix} λ_{1} \\ λ_{2} \end{matrix}) = (\begin{matrix} ρ_{1} λ_{1} + & ζ_{1} λ_{2} \\ \dots \\ ρ_{n} λ_{1} + & ζ_{n} λ_{2} \end{matrix})$

Let $𝓎_{i} = ρ_{i} λ_{1} + ζ_{i} λ_{2}$ for i = 1, …, n. Since ${\vec{y}}_{B}^{HU}$ is the set of all probability function values satisfying merging PKB, it follows that $\sum_{i = 1}^{n} 𝓎_{i} = 1$ and $0 \leq 𝓎_{i} \leq 1$ . Therefore, λ₁ + λ₂ = 1 and 0 ≤ λ₁, λ₂ ≤ 1. This proves the proposition.

Definition 19. (HU Merging Operator). Function $Γ^{HU} : B \to ℧ (B)$ is called HU Merging Operator whenever it is defined as follows: $Γ^{HU} (B) = {\vec{y}}_{B}^{HU}$ .

Proposition 16. Γ ^HU fulfills CP1, SCP, IP, EP, and CP2.

Proof. SCP: Suppose $\vec{y} \in Γ^{HU} (B)$ . By Definition 19, $\vec{y} \in Â_{B} \vec{λ}$ since $\cap_{i = 1}^{m} ℧ (K_{i}) \neq \emptyset$ and thus $\vec{y} \in \cap_{i = 1}^{m} ℧ (K_{i})$ . Suppose $\vec{y} \in \cap_{i = 1}^{m} ℧ (K_{i})$ . There exists $\vec{y} \in ℧ (K_{i})$ for i = 1, …, n. By Proposition 15, $\vec{y} \in Γ^{HU} (B)$ . CP1: This property is an easy result from SCP.□

IP and EP. Follows from Definition 19. CP2: If $℧ \in H$ then $℧ \subseteq Γ^{HU} (B) \subseteq \cap_{i = 1}^{m} ℧ (K_{i}^{'})$ . So $Γ^{HU} (B \cup C)$ is also the convex hull of all the sets from $H$ . Therefore, $Γ^{HU} (B \cup C) = Γ^{HU} (B)$ .

5 Approach for merging PKBs

In this section, algorithms for merging PKBs are proposed.

5.1 Finding probability merging vector

5.1.1 Algorithms

The SM1 algorithm. It describes the process of searching a set of probability functions satisfying PKB $K$ with respect to the 1-norm. It consists of two stages, (i) find characteristic matrix (line from 1 to 5) by employing Definition 9, and followed by (ii) solving optimization problem (line 6). It originates from Proposition 2.

Algorithm 1. The SM1 algorithm
Input: $K$
Output: SM1( $K$ )
1: Fori = 1 to hdo
2: Forj = 1 tomdo
3: $a_{ij} = φ (F_{i} \cap G_{i}, Θ_{j}) (1 - ρ_{i}) - φ ({\bar{F}}_{i} \cap G_{i}, Θ_{j}) ρ_{i}$
4: End for
5: End for
6: Solving problem (3) with constraints (4)–(5)
7: $℧ (K) \leftarrow {\vec{ϑ}}_{K}^{1}$
8: Return $℧ (K)$

Algorithm 2. The SM4 algorithm
Input: $K$
Output: SM4( $K$ )
1: Fori = 1 to hdo
2: Forj = 1 to 2hdo
3: If (i = j) and (i < = h) and (j < = h) then ${\bar{a}}_{ij} = 1$
4: Else if (j - i = h) and (j < =2h) then ${\bar{a}}_{ij} = - 1$
5: Else ${\bar{a}}_{ij} = 0$
6: Solving problem (9) with constraints (11)–(13)
7: $℧ (K) \leftarrow {\vec{ϑ}}_{X}^{u}$
8: Return $℧ (K)$

The problem (3) with constraints (4)–(5) is implemented by using LPSolve (http://lpsolve.sourceforge.net) and ojAlgo (http://ojalgo.org/).

The SM2 algorithm. It is related to the ∞ -norm and implemented similar to the SM1. However, in the second stage, it solves optimization problem (6) with constraints (7)–(8). It originates from Proposition 4.

The SM3 algorithm. It is related to the p-norm and implemented similar to the SM1. However, in the second stage, it solves optimization problem (1) with constraints (2). The problem (1) with constraints (2) is implemented by using interior-point algorithm [29]. It originates from Proposition 3.

The SM4 algorithm. It also describes a process of searching a set of probability functions satisfying PKB $K$ but it does not base on norm. It also consists of two stages, (i) finding diagonal double matrix ${\bar{A}}_{K}$ , and followed by (ii) solving optimization problem. Lines from 1 to 5 present the first stage by employing Definition 10. The second stage is presented in line 6 by solving optimization problem (9) with constraints (11–13). It originates from Proposition 5.

The solution of the problem (9) is similar to the method of solving (1). By Proposition 6, algorithms lead to a same result.

5.1.2 The computational complexity

The interior-point methods [29] were employed to solve convex optimization problems: $min f_{0} (x)$ (24) subject to $f_{i} (x) \leq 0, i \leq 0, i = 1, . . ., m; Qx = b$ (25)

One of these methods is the barrier method. Now assume that the problem is solvable. Let m be the number inequality constraints, $μ = 1 + \frac{1}{\sqrt{m}}$ , ∈ be a guaranteed specified accuracy, $c = {log}_{2} ({log}_{2} \frac{1}{\in})$ .

Let function $Φ (x) = - \sum_{i = 1}^{m} log (- f_{i} (x))$ be the logarithmic barrier for (24). Therefore, the gradient of Φ (X) are given by $\nabla Φ (x) = \sum_{i = 1}^{m} \frac{1}{- f_{i} (x)} \nabla f_{i} (x)$ (26)t⁽⁰⁾ is the value that minimizes $inf_{g} {∥ t \nabla f_{0} (x^{(0)}) + \nabla Φ (x^{(0)}) + Q^{T} g ∥}_{2}$ (27)

The constant γ depends on the backtracking parameters α and β,and is given by $γ = \frac{α β (1 - 2 α)}{20 - 8 α}$

The computational complexity of algorithm is $N = \frac{log \frac{m}{t^{(0)} \in}}{log μ} (\frac{m (μ - 1 - log μ)}{γ} + c)$ (28)

The following propositions provide some assessments of the complexity of the algorithms.

Proposition 17. The computational complexity of the SM1 algorithm is $O ({| K |}^{3} + | K | | Λ (\hat{ɛ}) |)$ .

Proof. In the first stage, the cost can be done in $O (| Λ (\hat{ɛ}) | | K |)$ . In the second stage, by Propositions 2 as the objective and constraint functions of problems are linear, computing ${\vec{ϑ}}_{K}^{1}$ , based on the Simplex algorithm proposed in [25, 28] and thus the cost can be done in $O ({| K |}^{3} + | K | | Λ (\hat{ɛ}) |)$ . Therefore, the computational complexity of the SM1 is $O ({| K |}^{3} + | K | | Λ (\hat{ɛ}) |)$

Proposition 18. The computational complexity of the SM2 algorithm is $O ({| K |}^{3} + | K | | Λ (\hat{ɛ}) |)$ .

Proof. Proposition 17 and 18 are similar in proof.□

Proposition 19. The computational complexity of the SM3 algorithm is $O (max {| Λ (\hat{ɛ}) | | K |, N_{SM 3}})$ .

Proof. In the first stage, the cost can be done in $O (| Λ (\hat{ɛ}) | | K |)$ . In the second stage, by Proposition 1, as the objective functions of problems are not linear, computing ${\vec{ϑ}}_{K}^{p}$ based on the interior-point algorithm proposed in [29]. By (24)–(25) and (1), it follows that $f_{0} (\vec{ϑ}) = {∥ A_{K} \vec{ϑ} ∥}_{p}$ $f_{i} (\vec{ϑ}) = - ϑ_{i}$ for $i = 1, \dots, | Λ (\hat{ɛ}) |$ , $Q = \underset{| Λ (\hat{ɛ}) |}{\underset{︸}{(1, \dots, 1)}}$ . By (26) $\nabla Φ (\vec{ϑ}) = \sum_{i = 1}^{| Λ (\hat{ɛ}) |} \frac{1}{ϑ_{i}}$ and thus $t_{SM 3}^{(0)}$ is the value that minimizes $inf_{g} {∥ t \nabla f_{0} ({\vec{ϑ}}^{(0)}) + \nabla Φ ({\vec{ϑ}}^{(0)}) + Q^{T} g ∥}_{2}$ . By (28) and (1), $N_{SM 3} = \frac{{log}_{\in t_{SM 3}}^{\frac{| Λ (\hat{ɛ}) |}{(0)}}}{log μ} (\frac{| Λ (\hat{ɛ}) | (μ - 1 - log μ)}{γ} + c)$ and thus the cost for computing ${\vec{ϑ}}_{K}^{p}$ can be done in. $O (N_{SM 3}})$ Therefore, the cost of the SM3 is $O (max {| Λ (\hat{ɛ}) | | K |, N_{SM 3}}) .$ □

Proposition 20. The computational complexity of the SM4 algorithm is $O (max {2 | K |^{2}, N_{SM 4}})$

Proof. In the first stage, the cost can be done in $O (2 {| K |}^{2})$ . In the second stage, by Proposition 5, as the constraint functions of problems are not linear, computing ${\vec{ϑ}}_{K}^{u}$ based on the interior-point algorithm proposed in [29]. By (24)–(25) and (9), it follows that $f_{0} (\vec{ϑ}) = \sum_{i = 1}^{h} (ℓ_{i} + ζ_{i}), Q = (1, \dots, 1)$ .□

By (26), $\nabla Φ (\vec{ϑ}) = \sum_{i = 1}^{3 | K | + | Λ (\hat{ɛ}) |} \frac{1}{- f_{i} (\vec{ϑ})} \nabla f_{i} (\vec{ϑ})$

$t_{SM 4}^{(0)}$ is the value that minimizes $\inf_{g} {∥ t \nabla f_{0} ({\vec{ϑ}}^{(0)}) + \nabla Φ (\vec{ϑ}) + Q^{T} g ∥}_{2}$ $N_{SM 3} = \frac{{log}_{\in t_{SM 4}}^{\frac{| Λ (\hat{ɛ}) |}{(0)}}}{log μ} (\frac{| Λ (\hat{ɛ}) | (μ - 1 - log μ)}{γ} + c)$

Therefore, the cost is $O (max {2 {| K |}^{2}, N_{SM 4}})$

5.2 Distance-based merging algorithms

5.2.1 Algorithms

The SQMA algorithm. It describes the process of searching a set of probability function values representing newly merged knowledge base from a PKB profile $B$ by using SQ divergence distance function. The SQMA consists of two stages, (i) for each $K_{i}$ finding a set of probability function values satisfying $K_{i}$ (line 1) by using one of algorithms SM1, SM2, SM3, and SM4; (ii) building SQ divergence distance functions (from line 2 to 5), and solving optimization problem (14) (line 8) with objective function f (from line 6 to 7). It originates from Proposition 7.

The problem (14) with constraints (15) is also implemented by using interior-point algorithm [29].

The RBMA algorithm. This algorithm is implemented similar to the SQMA. Instead of using SQ divergence distance function in the second stage, Renyi-B divergence distance function according to Definition 13 is used $d_{i} \leftarrow d_{i} + [(x_{j})^{r} - (y_{j})^{r} - r (x_{j} - y_{j}) (y_{j})^{r - 1}]$ and solve optimization problem (16) with objective function f and constraints (17). The RBMA originates from Proposition 9.

Algorithm 3. The SQMA algorithm
Input: $B = {K_{1}, . . ., K_{n}}$
Output: SQMA( $B$ )
1: For each $K_{i} \in B$ do ℧ ( $K_{i}$ )
2: Fori = 1 tondo
3: d_i ← 0
4: For each $x_{j} \in ℧ (K_{i})$ dod_i ← d_i + (x_j - y_j) ²
5: End for
6: f ← 0
7: Fori = 1 tondof ← f + d_i
8: Solving problem (14), where f is objective function and
constraints (15)
9: $y \leftarrow {\vec{y}}_{B}^{SQ}$
10: Return y

The LEMA algorithm. It is implemented similar to the SQMA. Instead of using SQ divergence distance function in the second stage, a KL divergence distance function according to Definition 14 is used $d_{i} \leftarrow d_{i} + x_{j} log \frac{x_{j}}{y_{j}}$ and solve optimization problem (18) with objective function f and constraints (19). The LEMA originates from Proposition 11.

The SEMA algorithm. It is implemented similar to the LEMA but the parameters in the KL divergence function are swapped $d_{i} \leftarrow d_{i} + y_{j} log \frac{y_{j}}{x_{j}}$ and solve optimization problem (20) with objective function f and constraints (21). The SEMA originates from Proposition 13.

The HULL algorithm. It consists of three stages, (i) for each $K_{i}$ finding a set of probability function values satisfying $K_{i}$ and finding profile matrix, (ii) generating vector $\vec{λ}$ such as λ_i ∈ [0, 1] and $\sum_{i = 1}^{| H |} λ_{i} = 1$ , and followed by (iii) computing ${\hat{A}}_{B} \vec{λ}$ . The HULL originates from Proposition 15.

5.2.2 The computational complexity

Proposition 21. The computational complexity of the SQMA algorithm is $O (max {n \bar{N}, n | Λ (\hat{ɛ}) |, N_{SQMA}})$ .

Algorithm 4. The HULL algorithm
Input: $B = {K_{1}, . . ., K_{n}}$
Output: HULL( $B$ )
1: For each $K_{i} \in B$ do $℧ (K_{i})$
2: Finding profile matrix ${\hat{A}}_{B}$
3: Generating $\vec{λ}$ such as $\sum_{i = 1}^{\| H \|} λ_{i} = 1$ , λ_i ∈ [0, 1]
4: ${\vec{y}}_{B}^{HU} = {\hat{A}}_{B} \vec{λ}$
5: Return ${\vec{y}}_{B}^{HU}$

Proof. The cost of SQMA depends on two stages. In the first stage, the cost is $O (n \bar{N})$ ; where $\bar{N} \approx {\bar{N}}_{SM 1}$ , or $\bar{N} \approx {\bar{N}}_{SM 2}$ , or $\bar{N} \approx {\bar{N}}_{SM 3}$ , or $\bar{N} \approx {\bar{N}}_{SM 4}$ . In the second stage, the cost for building SQ divergence distance functions is $O (n | Λ (\hat{ɛ}) |);$ the cost for building the objective function is $O (n)$ ; computing ${\vec{y}}_{B}^{SQ}$ based on the interior-point algorithm proposed in [29] and by (28) and (14), the cost can be done in $O (N_{SQMA})$ and thus the total of cost for the second stage is $O (max {n | Λ (\hat{ɛ}) |, N_{SQMA}})$ . By (24)–(25) and (14), it follows that $f_{0} ({\vec{y}}_{B}^{SQ}) = \sum_{i = 1}^{n} d^{SQ} (x_{i}, y)$ , $Q = \underset{| Λ (\hat{ɛ}) |}{\underset{︸}{(1, \dots, 1)}}$ . By (26), $\nabla Φ ({\vec{y}}_{B}^{SQ}) = \sum_{i = 1}^{| Λ (\hat{ɛ}) |} \frac{1}{y_{i}}$ and thus $t_{SQMA}^{(0)}$ is the value that minimizes $inf_{g} {∥ t \nabla f_{0} ({\vec{y}}_{B}^{{SQ}^{(0)}}) + \nabla Φ ({\vec{y}}_{B}^{{SQ}^{(0)}}) + Q^{T} g ∥}_{2}$ □

By (28) and (14), $N_{SQMA} = \frac{{log}_{t_{{SQMA}^{\in}}}^{\frac{| Λ (\hat{ɛ}) |}{(0)}}}{log μ} (\frac{| Λ (\hat{ɛ}) | (μ - 1 - log μ)}{γ} + c)$

Therefore, the cost of the SQMA is $O (max {n \bar{N}, n | Λ (\hat{ɛ}) |, N_{SQMA}})$

Proposition 22. The computational complexity of the RBMA algorithm is $O (max {n \bar{N}, n | Λ (\hat{ɛ}) |, N_{RBMA}})$ .

Proof. Proposition 22 and 21 are similar in proof.□

Proposition 23. The computational complexity of the LEMA algorithm is $O (max {n \bar{N}, n | Λ (\hat{ɛ}) |, N_{LEMA}})$

Proof. Proposition 23 and 21 are similar in proof.□

Proposition 24. The computational complexity of the SEMA algorithm is $O (max {n \bar{N}, n | Λ (\hat{ɛ}) |, N_{SEMA}})$ .

Proof. Proposition 24 and 21 are similar in proof.□

Algorithm 5. The PCVA algorithm
Input: - Probability merging vector of $B, \vec{y}$
- Probabilistic constraints
Output: PCVA ( $\vec{λ}$ )
1: For each constraint (F)[ρ] doρ is computed by using
axioms P0, P3, P4 in Proposition 1
2: For each constraint (F\|G) [ρ] doρ is computed by using
axioms P1, P2 in Proposition 1
3: Return $\vec{y}$

Proposition 25. The computational complexity of the HULL algorithm is $O (max {\bar{N}, | H^{2} |})$ .

Proof. In the first stage, the cost depends on employing algorithm finding a set of probability function values satisfying $K_{1} \in B$ , denoted by $\bar{N}$ . In the second stage, the cost for generating vector $\vec{λ}$ is $O ({| H |}^{2})$ , the cost for computing ${\hat{A}}_{B} \vec{λ}$ is $O (| H |)$ . Therefore, the cost is $O (max {\bar{N}, | H^{2} |})$ .□

5.3 Algorithm for computing new probability value of constraints

The PVCA algorithm. It describes the process of computing new probability value of constraints in merged knowledge base. It consists of two stages, (i) computing new probability value of constraints having form (F)[ρ], and (ii) computing new probability value of constraints having form (F|G) [ρ]. It originates from Proposition 1.

Proposition 26. The computational complexity of PCVA algorithm is $O (| \vec{y} |)$ .

Proof. It is easy to prove.□

By using algorithm for finding probability merging vector, distance-based merging algorithms, and algorithm for computing new probability value of constraints, a common consistent PKB can be obtained from a PKB profile. The process of merging PKB is presented in Fig. 1.

Fig.1

The process of merging PKBs.

5.4 Example

To illustrate this merging process presented in Fig. 1, the following example will be considered:

A hospital makes a survey of depression disease. It assigns doctors who are neurologists to this survey.

These doctors provide the result in which the probability that people has depression disease (denoted by D) are, respectively, 0.7, 0.5, 0.5, 0.8, and 0.6; the probability that people always have sleep problems (denoted by S) are, respectively, 0.6, 0.5, 0.7, 0.7, and 0.8; the probability that people often feel life’s not worth living (denoted by L) are, respectively, 0.5, 0.5, 0.5, 0.6, and 0.6; the probability that a person has depression disease when that person who has always sleep problems are, respectively, 0.8, 1, 0.6, 0.75, and 0.7; and the probability that a person often feel life’s not worth living, given that he has depression disease are, respectively, 0.8, 1, 0.4, 0.75, and 0.5.

One of algorithms SM1, SM2, SM3, and SM4 is employed to find a set of probability function values satisfying $K_{i}, i = 1, . . ., 5$ . Then, one of algorithms SQMA, RBMA, LEMA, SEMA, HULL is employed to find a set of probability function values representing newly merged knowledge base. Finally, the PCVA is employed to compute new probability value of constraints in merged knowledge base.

Table 1 shows these values when the SQMA, LEMA, SEMA are employed while Table 2 shows these values when the RBMA with different values of r and the HULL with different values of $\vec{λ}$ are employed. The new PKB which are merged from $K_{1}, K_{2}, K_{3}, K_{4}$ is a consistent PKB represented by a probability function satisfying desirable properties. It is evident that the sum of the probability functions of the new PKB equals 1, that is, satisfies Definition 1 about the total of the probability of complete conjunctions over the set of events.

Table 1
Original PKBs and merged knowledge bases for algorithms SQMA, LEMA, and SEMA

κ $K_{1}$ $K_{2}$ $K_{3}$ $K_{4}$ $K_{5}$ SQMA LEMA SEMA

(D) 0.7 0.5 0.5 0.8 0.6 0.6403020 0.6500584 0.8726884

(S) 0.6 0.5 0.7 0.7 0.8 0.6579282 0.7000438 0.2585991

(L) 0.5 0.5 0.5 0.6 0.6 0.5020782 0.5500159 0.2085848

(S|D) 0.8 1 0.4 0.75 0.5 0.7890107 0.7231369 0.2041572

(D|L) 0.8 1 0.6 0.75 0.7 0.7423151 0.6137144 0.6233821

κ	$K_{1}$	$K_{2}$	$K_{3}$	$K_{4}$	$K_{5}$	SQMA	LEMA	SEMA
(D)	0.7	0.5	0.5	0.8	0.6	0.6403020	0.6500584	0.8726884
(S)	0.6	0.5	0.7	0.7	0.8	0.6579282	0.7000438	0.2585991
(L)	0.5	0.5	0.5	0.6	0.6	0.5020782	0.5500159	0.2085848
(S\|D)	0.8	1	0.4	0.75	0.5	0.7890107	0.7231369	0.2041572
(D\|L)	0.8	1	0.6	0.75	0.7	0.7423151	0.6137144	0.6233821

Table 2

Merged knowledge bases for algorithms RBMA and HULL

κ	RBMA			HULL
	r			$\vec{λ}$
	1.2	1.5	2	(0.2, 0.2, 0.2, 0.2, 0.2)	(0.1, 0.2, 0.3, 0.3, 0.1)	(0.5, 0, 0, 0, 0.5)
(D)	0.59246940	0.60675762	0.64030201	0.62000000	0.62000000	0.65000000
(S)	0.64011368	0.64590239	0.65792817	0.66000000	0.66000000	0.70000000
(L)	0.51766261	0.51297004	0.50207822	0.54000000	0.54000000	0.55000000
(S\|D)	0.77227016	0.77914565	0.78901069	0.76774194	0.75483871	0.75384615
(D\|L)	0.67921817	0.69614187	0.74231507	0.68518519	0.67592593	0.63636364

The detail for explaining the merging process and evaluating algorithms in this paper can be found in an online appendix^rmbox1\footnote [1]https://vtn82.blogspot.com/2019/04/jifs.html.

6 Conclusion

In this paper, a new distance-based approach to implement the process of merging PKBs was proposed. The probabilistic MOs based on divergence concepts have been taken under deep consideration and adapted to new probabilistic merging framework by building distance functions between probabilities of constraints. Propositions to calculate the satisfied probabilistic functions of original knowledge bases, probability merging vector, and new probability of constraints in merged PKB were also proposed and proven. Then, postulates about logical relationships between the family of MOs and desirable properties were given. Finally, computational propositions were employed to build merging algorithms. The key differences between the proposed method and existing ones are that input knowledge bases and the merged knowledge base are represented by probabilistic constraints, and our method is considered in a sample space context. However, the input of merging algorithms was PKBs required to be in the same form. Therefore, in the future, new methods will be going on investigating to allow the original knowledge bases to vary in form.

Footnotes

Acknowledgment

This work has been supported by Vietnam National University, Hanoi (VNU), under Project No. QG.19.23. The authors would like to thank Professor Quang Thuy Ha and Knowledge Technology and Data Science Lab, Faculty of Information Technology, VNU - University of Engineering and Technology for expertise support.

References

Kolaczek

, Kuchtiak-Pieczynska

, Juszczyszyn

, Grzech

, Katarzynak

and Nguyen

N.T.

, A Mobile Agent Approach to Intrusion Detection in Network Systems, In: Proceedings of KES (2005), 514–519.

Pietranik

and Nguyen

N.T.

, A Multi-attribute and Logic-Based Framework of Ontology Alignment, Zgrzywa A. (ed.), Multimedia and Internet Systems: Theory and Practice. Springer 2012 (2012), 99–108In.

Nguyen

N.T.

, Advanced Methods for Inconsistent Knowledge Management, Advanced Information and Knowledge Processing. 2008: Springer 1–351.

Qin H.W., Ma X.Q., (Ma, Xiuqin), T. Herawan and J.M. Zain, Data Filling Approach of Soft Sets under Incomplete Information, in Prof of ACIIDS 2011. 2011, Springer pp. 302–311.

Potyka

and Thimm

, Probabilistic Reasoning with Inconsistent Beliefs Using Inconsistency Measures, in International Joint Conference on Artificial Intelligence 2015 (IJCAI15). 2015, AAAI Press © (2015), pp. 3156–3163.

Nguyen

V.T.

and Tran

T.H.

, Inconsistency measures for probabilistic knowledge bases, in Proceedings KSE 2017. 2017, IEEE Xplore pp. 148–153.

Potyka

and Thimm

, Consolidation of Probabilistic Knowledge Bases by Inconsistency Minimization, in Proceedings ECAI 2014. 2014, IOS Press pp. 729–734.

Potyka

, Solving Reasoning Problems for Probabilistic Conditional Logics with Consistent and Inconsistent Information. FernUniversitat, Hagen, 2016.

Nguyen

V.T.

and Tran

T.H.

, Solving Inconsistencies in Probabilistic Knowledge Bases via Inconsistency Measures, in Prof of ACIIDS 2018. 2018, Springer pp. 3–14.

10.

Nguyen

V.T.

, Nguyen

N.T.

, Tran

T.H.

and Nguyen

D.K.L.

, Method for restoring consistency in probabilistic knowledge bases, in Journal of Cybernetics and Systems. 2018, Taylor & Francis pp. 1–22.

11.

Konieczny

and Pérez

R.P.

, Logic Based Merging, J Philosophical Logic 40(2) (2011), 239–270.

12.

Konieczny

, Lang

and Marquis

, DA2 merging opertors, Artificial Intelligence 157(1-2) (2004), 49–79.

13.

Everaere

, Konieczny

and Marquis

, Disjunctive merging: Quota and Gmin merging operators, Artif Intell 174(12–13) (2010), 824–849.

14.

, Liu

and Glass

D.H.

, A Split-Combination Method for Merging Inconsistent Possibilistic Knowledge Bases, in KR’04. 2004, AAAI Press pp. 348–356.

15.

, et al., A Revision-Based Approach to Resolving Conflicting Information, in UAI’05. 2005, AUAI Press pp. 477–484.

16.

, et al., A split-combination approach to merging knowledge bases in possibilistic logic, Ann Math Artif Intell 48(1-2) (2006), 45–84.

17.

, et al., Merging Knowledge Bases in Possibilistic Logic by Lexicographic Aggregation, CoRR (2012).

18.

Vomlel

, Methods of Probabilistic Knowledge Integration. 1999, [PhD thesis] Czech Technical University, Prague.

19.

Vomlel

, Integrating, Inconsistent Data in a Probabilistic Model, Journal of Applied Non-Classical Logics 14(3) (2004), 367–386.

20.

Zhang

, Peng

and Wang

, An Efficient Method for Probabilistic Knowledge Integration., (2008), pp. 179–182.

21.

Wilmers

, The Social Entropy Process: Axiomatising the Aggregation of Probabilistic Beliefs, In Probability, Uncerainty and Rationality 2010.

22.

Adamcik

and Wilmers

, The irrelevant information principle for collective probabilistic reasoning, Kybernetika 50(2) (2014), 175–188.

23.

Adamcik

, Collective Reasoning under Uncertainty and Inconsistency. 2014, [PhD thesis] University of Manchester, UK.

24.

Nguyen

V.T.

, Nguyen

N.T.

and Tran

T.H.

, Framework for Merging Probabilistic Knowledge Bases, in Prof of ICCCI 2018. Lecture Notes in Artificial Intelligence (2018), pp. 31–42.

25.

Bertsekas

, Dimitri

N.A.

and Ozdaglar

, Asuman, Convex Analysis and Optimization, 2003: Athena Scientific, Belmont, Massachusetts.

26.

Osherson

D.N.

and Vardi

M.Y.

, Aggregating disparate estimates of chance, Games and Economic Behavior 56(1) (2006), 148–173.

27.

Ronald

W.E.

, et al., Probability & Statistics for Engineers & Scientists, ed. 9. 2012: Prentice Hall.

28.

Matousek

and Gartner

Understanding and Using Linear Programming. 2007: In: Universitext. Sringer.

29.

Stephen

and Lieven

, Convex Optimization. 2004: Cambridge University Press.

A distance-based approach for merging probabilistic knowledge bases

Abstract

Keywords

1 Introduction

2 Related work

3 Basic notions

4 Distance-based probabilistic MOs

4.1 Desirable properties

4.2 Satisfied probabilistic functions

4.3.1 The probabilistic merging operator Γ SQ

5.1 Finding probability merging vector

5.1.1 Algorithms

5.1.2 The computational complexity

5.2.1 Algorithms

5.2.2 The computational complexity

5.3 Algorithm for computing new probability value of constraints

Footnotes

Acknowledgment

References

4.3.1 The probabilistic merging operator Γ^SQ