K S Sesh Kumar

Alvaro Barbero
email: alvaro.barbero@uam.es

Stefanie Jegelka

Suvrit Sra
email: suvrit@mit.edu

Francis Bach
email: francis.bach@inria.fr

K S Sesh Kumar
email: sesh-kumar.karri@inria.fr

Álvaro Barbero

Convex Optimization for Parallel Energy Minimization

published or not. The documents may come

Introduction

Energy minimization has become a key element in many low-to mid-level tasks in computer vision, such as segmentation or stereo correspondence (see [START_REF] Blake | Markov Random Fields for Vision and Image Processing[END_REF] for a survey). For many, frequently occurring such minimization problems, graph cut techniques have emerged as generic, very efficient tools that provide global optima for submodular quadratic penalties, and extend to several higher-order and non-submodular potentials too. However, when applying widely used graph-cut code (e.g., [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]) to huge problems in 3D or video, running time and memory usage become problematic. Ideally, we would wish to have algorithmic flexibility to decompose the problem into (almost) arbitrary subproblems that can be solved in parallel, and that adapt to new architectures such as GPU clusters. These latter needs can be met through convex optimization.

In this paper, we explore methods that allow combining convex and combinatorial optimization, and thereby offer a way to parallelize recent successful combinatorial methods [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF][START_REF] Chandran | A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem[END_REF][START_REF] Goldberg | Maximum flows by incremental breadth-first search[END_REF]. Our algorithms can run on large datasets while using only limited memory, and are flexible enough to be ported to different hardware architectures.

We begin by rewriting the energy minimization problem as a convex optimization problem. More precisely, we consider the equivalent reformulation of the min-cut problem as the minimization of a unary term w x plus the total variation f (x) associated to a graph, over the vertices of the hypercube x ∈ {0, 1} n . The straightforward convex relaxation replaces the set of vertices {0, 1} n of the hypercube with the full hypercube [0, 1] n . This relaxation is tight, a fact that has been exploited widely. Moreover, typical graph structures that occur in low-level vision problems naturally decompose as a superposition of chains, suggesting the use of iterative convex optimization methods [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF][START_REF] Savchynskyy | A study of Nesterov's scheme for Lagrangian decomposition and MAP labeling[END_REF]. However, the lack of smoothness (in the primal and dual problems) poses some difficulties in solving the problem efficiently.

Hence, we instead consider a reformulation through total variation denoising outlined by [START_REF] Hochbaum | An efficient algorithm for image segmentation, markov random fields and related problems[END_REF][START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF] for general submodular functions, which we use for cuts in this paper. The gist of this approach is to replace the nonsmooth relaxation by the total variation (TV) denoising problem min x∈R n 1 2 xw 2 + f (x), from which one may obtain an optimal solution of the energy minimization problem by thresholding. The benefit of this formulation is its smooth dual problem, which has a natural geometric interpretation: it reduces to computing the distance between two convex sets. Moreover, via the equivalence between energy minimization and projections we obtain fast projection subroutines, which in turn enable the use of classical, popular projection methods [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF].

While we focus on cuts in this paper, our framework extends to all higher-order submodular potentials, nonsubmodular quadratic potentials, and to multi-label problems (see Section 4.4 for more details). We make the following contributions:

-We study algorithms that allow to easily combine convex and combinatorial optimization (e.g., graph cut, total variation, algorithms for higher order submodular potentials), and to parallelize existing fast energy minimization methods for submodular potentials. In fact, this approach applies to arbitrary sums of submodular functions, each defined on all or a subset of the variables.

-As a case study, we specialize the optimization framework of [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF] to the submodular energy functions most commonly used in computer vision, such as quadratic functions with a 2D or 3D grid structure with various connectivities (Section 3.1). The resulting min-cut algorithm (and code) is conceptually very simple and may thus be easily used and modified.

-We perform an extensive empirical evaluation of serial and parallel, combinatorial and convex min-cut codes on benchmarks [START_REF] Verma | MaxFlow revisited: An empirical comparison of maxflow algorithms for dense vision problems[END_REF][START_REF] Kappes | A comparative study of modern inference techniques for discrete energy minimization problems[END_REF]. We observe that iterative techniques based on convex optimization match combinatorial max-flow algorithms on small problems, and on larger problems they offer complementary flexibility: (a) they have a reduced memory footprint and can tackle many problems where traditional methods run out of memory, (b) they parallelize easily on multi-core platforms, (c) they can be efficiently warm-started, (d) they quickly reach approximately good solutions, thereby enabling faster "inexact" solutions. These observations suggest to marry convex and combinatorial methods to attain "the best of both worlds".

Convex optimization for graph cuts

In this paper, we focus on energy minimization problems with pairwise potentials,

E(x) = - n i=1 w i x i + n i,j=1 ψ ij (x i , x j ), (1)
where the variables x i take values in a set of discrete labels. For simplicity, we here focus on binary labels, x i ∈ {0, 1}. The algorithms we discuss may be generalized to multiple labels via move-making strategies [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Moreover, we assume the pairwise potentials to be submodular, i.e., ψ ij (0, 1) [START_REF]Maxflow dataset online[END_REF][START_REF]Maxflow dataset online[END_REF]. (One may extend to non-submodular potentials via roof duality [START_REF] Rother | Optimizing binary MRFs via extended roof duality[END_REF]). It is well known that all such submodular energy functions may be written as graph cut functions with nonnegative "edge weights" a ij , up to a constant [START_REF] Picard | Minimum cuts and related problems[END_REF]:

+ ψ ij (1, 0) ≥ ψ ij (0, 0) + ψ ij
E(x) = - n i=1 w i x i + n i,j=1 a ij |x i -x j | + const. (2)
This function consists of two parts: (1) a sum of unary potentials -n i=1 w i x i = -w x; and (2) the sum of pairwise potentials, which is equivalent to a weighted graph cut between the set of indices i in {1, . . . , n} for which x i = 1, and its complement. For x ∈ R n , this sum is the total variation function f (x) = n i,j=1 a ij |x i -x j |. Note that this is a case of anisotropic weighted total variation. Since the weights a ij are non-negative, the function f is convex. We refer to the graph cut problem as the discrete problem:

min x∈{0,1} n f (x) -w x.
(D)

Convex reformulation

We obtain a relaxation to the combinatorial problem in Eq. (D) by replacing {0, 1} n by its convex hull [0, 1] n :

min x∈[0,1] n f (x) -w x. (C)
We refer to Eq. (C) as the continuous problem. This relaxation is exact: since the continuous convex problem in (C) is a minimization problem over a larger set than the discrete problem, its minimal value has to be lower than (D). However, as a consequence of properties of the total variation and its relation to submodular graph cut functions (see, e.g., [START_REF] Bach | Learning with Submodular Functions: A Convex Optimization Perspective, volume 6 of Foundations and Trends in Machine Learning[END_REF]Sec. 3.3] or [START_REF] Hochbaum | An efficient algorithm for image segmentation, markov random fields and related problems[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF] for a proof dedicated to cut functions), the two optimal values are equal and a solution to (D) may be obtained from a solution x ∈ [0, 1] n of (C) by looking at all "level sets" of x, that is by rounding the values of x to zero or one by thresholding at a given level in [0, 1] (there are at most n possible thresholds, which can be obtained by first sorting the components of x).

Convex duality

The total variation f is convex and absolutely homogeneous, that is, for any x ∈ R n and λ ∈ R, f (λx) = |λ|f (x). For all such functions, there exists a centrally symmetric convex body K ⊂ R n such that for all x ∈ R n [37, §13], f (x) = max y∈K y x.

Note that when f (x) happens to be equal to zero only for x = 0, then f is a norm and the set K is simply the unit ball of the dual norm.

Since f is piecewise affine, the set K is a polytope (i.e., the convex hull of finitely many points). The set K may be described precisely for general submodular functions and is usually referred to as the base polytope of the submodular function [START_REF] Fujishige | Submodular Functions and Optimization[END_REF][START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF][START_REF] Bach | Learning with Submodular Functions: A Convex Optimization Perspective, volume 6 of Foundations and Trends in Machine Learning[END_REF].

Using Fenchel duality, we arrive at the following dual problem to (C) [START_REF] Fujishige | Submodular Functions and Optimization[END_REF][START_REF] Bach | Learning with Submodular Functions: A Convex Optimization Perspective, volume 6 of Foundations and Trends in Machine Learning[END_REF]:

min x∈[0,1] n f (x) -w x = min x∈[0,1] n max y∈K y x -w x = max y∈K min x∈[0,1] n x (y -w) = max y∈K n i=1 min{y i -w i , 0}. (3)
This dual problem allows us to obtain certificates of optimality: given a pair (x, y) ∈ [0, 1] n × K, the quantity

gap(x, y) := f (x) -w x - n i=1 min{y i -w i , 0}
is always non-negative, and equal to zero if and only if x is optimal for (C) and y is optimal for the dual problem Eq. ( 3). This duality relation is essential to certify that a given solution is optimal (and corresponds to the traditional min-cut/max-flow duality).

While the cut problem is now reformulated as a convex optimization problem, it is still hard to minimize because neither the primal nor the dual are smooth, and thus iterative methods are typically slow (see detailed comparisons in [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF]). We now reformulate the problem so that the dual problem becomes smooth and potentially easier to optimize.

Equivalence to total-variation denoising

Following [START_REF] Fujishige | Submodular Functions and Optimization[END_REF][START_REF] Bach | Learning with Submodular Functions: A Convex Optimization Perspective, volume 6 of Foundations and Trends in Machine Learning[END_REF][START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF][START_REF] Nagano | Size-constrained submodular optimization through minimum norm base[END_REF], we consider the total variation denoising problem:

min x∈R n f (x) + 1 2 x -w 2 . (TV)
By expanding 1 2 xw 2 into 1 2 x 2 -w x + 1 2 w 2 , we see that going from the continuous problem (C) to (TV) means replacing the constraint x ∈ [0, 1] n by the penalty

1 2 x 2 = 1 2 n i=1 x 2 i .
This has a number of important consequences: (1) It makes the optimization problem strongly convex and thus the dual problem will be smooth; see Eq. ( 4). ( 2) A solution to (D) and hence (C) may be obtained by thresholding the unique solution x of (TV) at zero, that is, by defining xi = 1 if x i > 0 and xi = 0 otherwise. This is usually not true for arbitrary convex functions f (even absolutely homogeneous) and is a direct consequence of submodularity. Importantly, we need not solve the TV problem (TV) exactly to obtain a solution to (C), we only need to know which of the components are positive (resp. negative).

Analogously to Eq. ( 3), we may derive the dual to (TV): The primal and dual solutions x and y have a simple correspondence x = wy, as can be seen from the dual derivation. We have now obtained a dual problem which may be simply interpreted as the orthogonal projection of the vector w onto the polytope K. Importantly, a slight additional argumentation shows that the discrete energy minimization problem (D), the total variation relaxation (TV), and the projection onto K are equivalent. That means, a fast subroutine for one of the problems implies a fast subroutine for the other two.

min x∈R n f (x) + 1 2 w -x 2 = min x∈R n max y∈K y x + 1 2 w -x 2 = max y∈K min x∈R n y x + 1 2 w -x 2 = max y∈K 1 2 w 2 - 1 2 y -w 2 . (4)
While the reformulation is intuitive, orthogonal projections onto the polytope K are not fast to compute in general. Many special cases, however, are fast, including graphs that have fast cut subroutines (which may be combinatorial).

Decomposition of graphs

We assume that the total variation f (and equivalently the energy function) may be decomposed into a sum r j=1 f j (x) of r total variation functions f j . Each function f j can be defined on 2D grids, trees or chains. The only criterion for the decomposition is to efficiently perform orthogonal projections onto the polytope K j corresponding to f j . In fact, f j does not need to have full support.

While other decompositions are possible [START_REF] Kolmogorov | Convergent tree-reweighted message passing for energy minimization[END_REF][START_REF] Sontag | Tree block coordinate descent for MAP in graphical models[END_REF], in this paper, we focus on chains to illustrate our ideas; we note that 1D-TV (on chains) can be solved very efficiently-see Section 3.2. Note that the same idea works for decompositions into trees, stars, small "cubes" and 2D sheets.

2D and 3D grids

The most frequenly used 2D and 3D topologies in computer vision decompose straightforwardly in several ways [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF][START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF][START_REF] Kolmogorov | Minimizing a sum of submodular functions[END_REF][START_REF] Savchynskyy | A study of Nesterov's scheme for Lagrangian decomposition and MAP labeling[END_REF]. In our experiments, we split the 2D 4-connected grid into vertical and horizontal lines (Figure 1 left), and the 2D 8-connected grid additionally into zig-zagged paths (Figure 1 middle) . Diagonal lines are also possible but less efficient with respect to memory access.

Even though the set of 1D lines of equal color in the figures may be considered one f j , the lines are independent and may be addressed in parallel. Further parallelization (across colors) results from our splitting formulation. Finally, any fast algorithm for solving a 2D or 3D TV (or graph cut) problem may be used as a subroutine when setting f j to be an entire 2D grid sheet or 3D tensor.

Efficient 1D TV

As chains are the building blocks of our decomposition, performance of the overall method is heavily influenced by the speed at which 1D-TV can be solved. Being a classic regularizer for image denoising, literature on solvers for different variations of 1D and 2D TV abounds, though only recently fast direct methods for chains have been proposed. A notable example is the dynamic programming method of Johnson [START_REF] Johnson | A dynamic programming algorithm for the fused Lasso and l 0 -segmentation[END_REF], which guarantees linear complexity. Another outstanding method is that of Condat [START_REF] Condat | A direct algorithm for 1d total variation denoising[END_REF]; it is based on a thorough analysis of the KKT conditions and manages to achieve faster running times in practice, despite a pathological quadratic cost worst-case. These TV solvers, however, only apply to chains with constant weights.

To permit varying weights we use a recent method of [START_REF] Barbero | Modular proximal optimization for multidimensional total-variation regularization[END_REF] that obtains Condat's method through a taut-string viewpoint [START_REF] Grasmair | The equivalence of the taut string algorithm and BV-regularization[END_REF], in a way that allows weights along the chain. Experiments [START_REF] Barbero | Modular proximal optimization for multidimensional total-variation regularization[END_REF] indicate that this method shares the same performance as the original procedure, therefore rapidly solving TV chains in linear time in practice.

We also point out that the choice of the 1D-TV solver is independent of the overlying topologies and optimizers. This allows us to localize complexity to highly tuned TV chain solvers for the architecture under use (multicore, GPUs, etc.), thus providing overall modularity and adaption to the underlying hardware. In this paper, we use a general implementation for CPUs.

Message passing. Alternatively to the method that we have used, we may also use message passing techniques, which could be more efficient on certain architectures. These are directly adapted to solve the min-cut problem on a chain or a tree, not the total variation problem. However, it is known that by a sequence of at most n min-cut problems, one may obtain the exact TV solution [START_REF] Hochbaum | About strongly polynomial time algorithms for quadratic optimization over submodular constraints[END_REF].

Decomposed dual problems

By their form (total variation or Lovász extensions of submodular functions), the f i may be represented as a maximum of linear functions, that is, f j (x) = max yj ∈Kj y j x, for K j a certain polytope, j ∈ {1, . . . , r}. This form as well as the decomposability of the total variation may be used to obtain a decomposed dual problem for the continuous Problem (C). The dual splits in the same way as the primal, and admits parallel optimization algorithms [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF][START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF][START_REF] Kolmogorov | Minimizing a sum of submodular functions[END_REF][START_REF] Savchynskyy | A study of Nesterov's scheme for Lagrangian decomposition and MAP labeling[END_REF]. It however has a non-smooth objective function that makes optimization harder.

We hence next describe two dual problems for the (TV) problem [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF].

First dual problem. We use a standard reformulation for dual decomposition: we introduce a variable

x = (x 1 , . . . , x r ) ∈ R n × • • • × R n composed of
r copies of the input variable x, with the constraint that x i = x for each i ∈ {1, . . . , r} (see, e.g., [START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF]). We then add Lagrange multipliers λ i ∈ R n for each of these constraints. Writing f j as a maximum of linear functions introduces a dual variable vector y j ∈ K j . We collect those variables in a vector y = (y 1 , . . . , y r )

∈ K = K 1 × • • • × K r .
Overall, we obtain the following:

min x∈R n r j=1 f j (x) + 1 2 w -x 2 = max λ∈R n×r , y∈K min x∈R n , x∈R n×r r j=1 x j y j + 1 2 w 2 -w x + 1 2r r j=1 x j 2 + r j=1 λ j (x -x j ) = max λ∈L, y∈K 1 2 w 2 2 - r 2 r j=1 y j -λ j 2 6
AP, iter 1 AP, sequence AAR, iter 1 AAR, sequence

y 1 1 = ⇧ L (y 1 ) K L z 0 ... y 1 y 2 y 3 K L z 0 R K (z 0 ) R L (R K (z 0 )) K L z 1 z 0 K L y 1 y 2 y 3 z 1 z 2 z 3 z 0
Figure 2: Illustration of alternating projections (AP) and averaged alternating reflections (AAR) for Problem ( 5), the problem of finding the closest points between a polytope K and a subspace L. The iterations start at the black point z 0 . AP alternatingly projects onto K and then L. AAR reflects at K and then at L; the next iterate z t+1 (magenta) is the midpoint between z t and R L R K (z t ). For AAR, the sequence z t diverges, but the projected shadow sequence of y t = Π K (z t ) converges (red). Here, AAR takes larger steps than AP and hence converges more quickly.

= max

λ∈L, y∈K

1 2 w 2 2 - r 2 y -λ 2 , (5)
where L denotes the set of λ ∈ R n×r such that r j=1 λ j = w. We are thus faced with the problem of finding the closest point between two convex sets, which we explore in Sections 4.2 and 4.3.

Note that if the function f j only depends on a subset of variables of x, then we may restrict the corresponding variable λ j to be zero on the complement of that subset in order to have faster convergence for the iterative methods presented below.

Second dual problem. Given y ∈ K in (5), the optimal λ ∈ L may be obtained in closed form:

λ j = w r + y j - 1 r r k=1 y k . (6)
This leads to another dual problem, where the variables λ ∈ L are maximized out:

max y∈K 1 2 w 2 2 - 1 2 r j=1 y j -w 2 . (7)
The problem above has separable constraints y i ∈ K j , j ∈ {1, . . . , r} and a smooth objective function. We will discuss optimization procedures in Section 4.1.

Special case r = 2. When the function f is split into two functions, then the problem in Eq. ( 7) is equivalent to finding the distance between the convex set K 1 and the set {w -y 2 | y 2 ∈ K 2 }, for which methods presented in Sections 4.2 and 4.3 may be used.

Optimization for decomposable problems

Next, we describe optimization procedures that exploit the decomposable structure of the dual problems ( 5) and [START_REF] Bertsekas | Nonlinear programming[END_REF], where in particular the Cartesian decomposition K = K 1 × • • • × K r of the constraint sets plays an important role. In particular, we exploit that the projection onto K consists of r independent projections onto the sets K i . By the above derivations, each of those projections can be done quickly via a TV subroutine for each f i .

while averaging them to ensure firm nonexpansivity, a property that greatly simplifies convergence analysis [START_REF] Bauschke | Finding best approximation pairs relative to two closed convex sets in Hilbert spaces[END_REF]. To apply the AAR method, one first introduces the auxiliary vector z, which represents yλ. Then, AAR takes the form

z k+1 = 1 2 (R L R K + I)z k . (9)
However since usually K ∩ L = ∅, the sequence (z k ) generated by ( 9) diverges to infinity! The remarkable fact is that from this diverging sequence, we can extract a solution by maintaining a "shadow sequence" y k ≡ Π K (z k ). See Figure 2 for an illustration, and Theorem 3.13 in [START_REF] Bauschke | Finding best approximation pairs relative to two closed convex sets in Hilbert spaces[END_REF] for a proof of convergence.

Extensions

Above, we outlined flexible, parallelizable convex optimization algorithms for energy minimization with pairwise submodular potentials. These algorithms straightforwardly generalize from binary labels to the multi-label case, to submodular higher-order potentials, and to related problems. The reasons are two-fold:

(1) the above algorithms solve a minimum cut problem, and any methodological machinary that builds on graph cuts as a subroutine will work with the above algorithms too; (2) the decomposition theory and tightness of the relaxations hold generically for submodular functions, not only graph cuts.

For multi-label energy minimization, one may use move-making algorithms [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] that reduce the multi-label problem to a series of binary submodular energy minimization problems. The methods above solve those binary problems. For combinatorial algorithms, it has proved useful to reuse existing solutions and data structures [START_REF] Kohli | Efficiently solving dynamic markov random fields using graph cuts[END_REF]. "Warm-starting" is possible for the convex case too: we simply use the y i vectors of the previous problem to initialize the new problem. If the geometry of the polytopes K has not changed too much, this can save many iterations (see Figure 3(b)).

Second, the convex approach directly generalizes to submodular potentials that involve more than two nodes at a time (following [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF]); such potentials include [START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF][START_REF] Stobbe | Efficient minimization of decomposable submodular functions[END_REF][START_REF] Kohli | P3 & beyond: Move making algorithms for solving higher order functions[END_REF][START_REF] Kohli | Robust higher order potentials for enforcing label consistency[END_REF][START_REF] Hein | The total variation on hypergraphs -learning on hypergraphs revisited[END_REF]. Many of those potentials correspond to sufficiently simple submodular functions, often with small support, such that the relaxation (the equivalent to total variation for graph cuts) can be solved fast. Moreover, the same methods may even generalize to be used with roof duality [START_REF] Rother | Optimizing binary MRFs via extended roof duality[END_REF].

Finally, since the above methods also solve the parametric version of the discrete problem (by thresholding the solution of Eq. (TV) at different levels) as a byproduct, they are also applicable to the numerous applications of parametric graph cuts [START_REF] Kolmogorov | Applications of parametric maxflow in computer vision[END_REF][START_REF] Hochbaum | A polynomial time algorithm for rayleigh ratio on discrete variables: Replacing spectral techniques for expander ratio, normalized cut, and cheeger constant[END_REF].

Implementation details

The algorithms are inherently parallel by design as each projection/reflection onto a chain graph is independent of the other. Our implementation assumes decomposed functions and the decomposition depends on the problem at hand. In Section 3.1, we described some possible decompositions of grid-like graph structures on 2D and 3D graphs. However, this extends to many other decompositions. Empirically and theoretically [START_REF] Nishihara | On the linear convergence rate of decomposable submodular function minimization[END_REF], longer connected structures lead to faster convergence than decomposition e.g. into single edges.

Parallelization

We use the efficient 1D-TV implementation of [START_REF] Barbero | Modular proximal optimization for multidimensional total-variation regularization[END_REF] to solve the projection/reflection on chains in parallel.

Our implementation is in C++ and uses OpenMP; it ensures that the memory access pattern across threads is streamlined, since bad memory access patterns can lead to considerable slowdowns. While the 1D-TV solver is not optimized for GPUs, as explained in Section 3.2, it can be replaced by message passing based subroutines, which are inherently parallel and also friendly to GPU architectures.

Memory footprint

In our implementation every decomposable function must maintain states of dual variables for each node in the graph. Thus, the memory requirement of our methods increases bilinearly in the number of decomposed functions and the number of nodes. Our experiments suggest that the projection-based algorithms require less memory than standard combinatorial algorithms-see Table

Running time

With the TV subroutine we use, each projection/reflection step scales in the worst case quadratically in the length of the chain (the chain length is typically equal to √ n or 3 √ n, where n is the total number of nodes in the 2D or 3D graphs), but is in practice usually linear [START_REF] Barbero | Modular proximal optimization for multidimensional total-variation regularization[END_REF]. In fact, it did not scale quadratically for any of our data. Hence, empirically, the cost of each iteration grows bilinearly with the number f of functions f i , and with the number of nodes in the graph.

Experiments

Our experiments study the performance of the projection algorithms on 2D and 3D-maxflow datasets [START_REF]Maxflow dataset online[END_REF], exploiting in particular the parallel nature of the algorithms. We compare the algorithms to standard, popular maxflow implementations such as BK [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF], IBFS [START_REF] Goldberg | Maximum flows by incremental breadth-first search[END_REF], and HPF [START_REF] Chandran | A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem[END_REF]. For other algorithms [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF][START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF], we have not been able to find implementations that were easily portable to 3D datasets.

Table 2 shows running time and the number of iterations for the projection algorithms and others on a multicore machine 1 . The timings are recorded using the gettimeofday command. All the timings are for the optimization phase only and exclude data I/O (which is common to all methods).

2D problems

As a 2D example, we use the tsukuba data [START_REF]Maxflow dataset online[END_REF], a multi-label task on 2D images corresponding to 4-neighborhood grids. To cope with multiple labels, we use alpha expansion [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Notably, the decomposition for 2D 4connected grids uses only two functions (vertical and horizontal), and therefore corresponds to the special dual for r = 2 in Section 3.3. For this formulation, AAR converges remarkably faster than other iterative algorithms, and even outperforms the combinatorial methods. The time comparisons at the bottom of Table 2 show that in general, the running times of our methods are comparable to standard combinatorial algorithms on images of 384 × 288 size.

Warm starts. Figure 3(b) shows the number of iterations required for the algorithm to converge on each frame of size 480 × 360 of the VideoSegA [START_REF]Maxflow dataset online[END_REF] dataset. These are the consecutive frames of a video, which are 2D images with 8-neighborhood grids (see Figure 1). We use the dual variables at the convergence of the previous frame to warm-start the projection/reflection process. This makes the method converge to the optimal solution substantially quicker than with other initializations.

3D problems

On the 3D data, the running times of the algorithms differs more widely. In particular, the number of iterations for the algorithms to converge appears to depend on two important characteristics: (i) number of nodes in the graph (dimensionality) (ii) the edge weights in the graph (weights of the TV term). The latter affects the size of the polytopes K, i.e., the diameter of the domain of the dual problem, a parameter that commonly influences the convergence of convex optimization methods (see also [START_REF] Nishihara | On the linear convergence rate of decomposable submodular function minimization[END_REF]).

Effect of edge weights. Table 2 shows results for larger edge weights, as well as weights scaled by a factor of 0.1. The iterative methods become faster with smaller weights, while the combinatorial methods robustly perform well with large weights too. On many instances, AAR converges faster than the cyclic BCD, while on others BCD is faster.

Approximate solutions. Since we can obtain a feasible solution (discrete cut) from any iterate of the projection methods by thresholding the continuous vector, Table 2 [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF], IBFS [START_REF] Goldberg | Maximum flows by incremental breadth-first search[END_REF], and HPF [START_REF] Goldberg | Maximum flows by incremental breadth-first search[END_REF] on 3D datasets with 6 connectivity. AAR(< p%) denotes the time taken for the algorithm to find a cut whose difference to the optimal cut is p% of the difference between the cut in the first iteration and the optimal cut. AAR-JD(< p) denotes time taken by the algorithm to reduce Jaccard Distance to p. AAR(0.1x) is the number of iterations taken by AAR after scaling the pairwise weights by 0.1.

Memory.

Apart from running time, we also investigate the memory footprint of the algorithms. Table 1 shows the memory footprint of all algorithms on the Abdomen data [START_REF]Maxflow dataset online[END_REF], which is 512 × 512 × 551. AAR uses considerably less memory than the standard algorithms.

Conclusion and Future work

We have proposed parallel iterative algorithms for binary energy minimization problems. The algorithms rely on a fast projection subroutine. For binary submodular potentials (graph cuts), this subroutine is simply a total variation problem, which can be efficiently solved on sub-graphs with special structure. In other examples, these subroutines could be fast algorithms for solving cuts on arbitrary subgraphs, or for simpler submodular energies. Hence, while the experiments here concentrate on cuts and decompositions into line graphs, the same methods apply to decompositions into 2D sheets, 3D cubes or any other subgraphs, and to sums of simple higher-order potentials.

We observed that the iterative methods perform similarly to combinatorial methods on 2D grid graphs, and require less memory than other, popular implementations of maximum flow algorithms. The tradeoffs betweem convex and combinatorial methods illustrated here have some interesting implications, and suggest a wider study of integrating combinatorial and convex methods via different decompositions. For example, instead of TV oracles for line graphs, one may use oracles for larger specialized subgraphs. These oracles could use algorithms such as BK, HPF or IBFS, since the projection and TV oracle can be solved by parametric graph cuts. A 3D tensor is easily decomposed into two components: grids and lines. Those more complex subroutines can still be invoked in parallel using AAR. Thus, one can combine convex and combinatorial methods to greatly benefit from the strengths of both.

The convex algorithms admit stochastic variants too [START_REF] Ene | Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions[END_REF]. However, the decompositions used in the experiments here (Figure 1) only use a decomposition into 2-4 functions. Finally, given the remarkably improved behavior of iterative methods for smaller weights, it is of great empirical interest to study algorithms that can use homotopies or continuation techniques to start by solving with lower weights and use the ensuing solutions to speed up the medium and high weight regimes.

Figure 1 :

 1 Figure 1: Grid graph structures and decompositions, indicated by different colors. Left: 2D, 4-connected, middle: 2D, 8-connected, right: 3D tensor, 6-connected.

Figure 3 :

 3 Figure 3: Speedup of the AAR algorithm with parallelization and warm starts. (a) Normalized scale of performance with increasing number of cores on Bunny datasets [1] of different resolutions. (b) Number of iterations taken by each from of a video with "normal" initialization and "warm start" from the dual variables of the previous frame.

Table 1 :

 1 1. Unlike the 32 bit integers used in many other implementations, we use (64 bit) double precision numbers. Reducing those to 32 bit would reduce the memory requirements of the projection methods even further. Memory footprint for Abdomen dataset (512 × 512 × 551)

	Algorithm	AAR BK [10] IBFS [17] HPF [13]
	Memory(GB) 26.82	42.83	44.16	55.46

Table 2 :

 2 also shows the time taken to obtain an approximate solution with limited error (10% and 2%, measured by Jaccard distance). The results suggest that, while a complete dual certificate of convergence for the discrete problem takes a bit longer, a reasonable approximate solution can be obtained fairly quickly. Medium (202 × 199 × 157), and Small (102 × 100 × 79). It is evident that more cores can improve the performance of the algorithm considerably. When using GPUs, it is important to consider their limited video memory, and hence the algorithms need to have a low memory footprint to perform well. Performance comparison of AAR with BK

	Parallel speedup. Figure 3-(a) shows the speedup of AAR achievable with an increasing number of cores.
	This figure reports the running time on the Bunny dataset (3D) with different resolutions: Large (401 × 396 ×
	312),

20 core, Intel(R) Xeon(R) CPU E5-2670 v2 @

2.50GHz with 100Gigabytes of memory. We only use up to 16 cores of the machine to ensure accurate timings.

Cyclic projections

The first method we consider for problem [START_REF] Bertsekas | Nonlinear programming[END_REF] is block coordinate descent (BCD), a classic method [START_REF] Bertsekas | Nonlinear programming[END_REF] that has recently witnessed a huge resurgence of interest in large-scale optimization [START_REF] Richtárik | Parallel coordinate descent methods for big data optimization[END_REF][START_REF] Beck | On the convergence of block coordinate descent type methods[END_REF]. Since the cost function is a separable quadratic, BCD assumes a form that is more commonly known as cyclic projections (more precisely, this is so if we go through the constraint blocks in a cyclic order). Specifically, we update coordinate blocks i = 1, . . . , r as follows:

where Π Ki denotes orthogonal projection onto set K i . This projection is solved by solving a (fast) TV problem with f i . Notice that the variable y i is overwritten after the update, so that when updating y i+1 , the latest values y 1 , . . . , y i are used in the projection.

In addition to cyclic projections, one could solve the smooth dual (7) using a gradient-based method like FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. Such a method is also easy to implement because the Lipschitz constant of the gradient is easily seen to be r and the required projections decompose due to the structure of K.

Alternating projections in product space

The method of cyclic projections offers a practical choice. However, it is inherently serial. To solve the problem in parallel, the first dual formulation (5) turns out to be more suited (note that this provides a second source of parallelization, beyond the fact that each polytope K j is itself a product of polytopes corresponding to individual lines).

The key idea is to exploit the "product space" K 1 × • • • × K r . Since w is constant, as previously mentioned, ( 5) is nothing but the problem of finding the closest point between two convex sets [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF]. Applying BCD, except this time with just two coordinate blocks, we obtain the classic alternating projections (AP) (cast in a product space setting), which performs for k = 0, 1, . . . , the iteration:

The key point here is that the projection Π K decomposes

so that each of the coordinate blocks may be computed in parallel (our implementation exploits this fact), while the projection Π L is merely an averaging step detailed in (6).

Alternating reflections in product space

The recent work [START_REF] Jegelka | Reflection methods for user-friendly submodular optimization[END_REF] provided strong experimental evidence that for projection problems of the form (5), AP is often outperformed by a more refined method of [START_REF] Bauschke | Finding best approximation pairs relative to two closed convex sets in Hilbert spaces[END_REF], namely, averaged alternating reflections (AAR). Here, instead of alternating between the projection operations Π K and Π L , one uses reflection operators


Asma Belhadi

Didier Dubois

Faiza Khellaf-Haned

Henri Prade
email: henri.prade@irit.fr

Multiple agent possibilistic logic

Keywords: possibilistic logic, possibility theory, uncertainty, multiple agent inconsistency

The paper presents a 'multiple agent' logic where formulas are pairs of the form (a, A), made of a proposition a and a subset of agents A. The formula (a, A) is intended to mean '(at least) all agents in A believe that a is true'. The formal similarity of such formulas with those of possibilistic logic, where propositions are associated with certainty levels, is emphasised. However, the subsets of agents are organised in a Boolean lattice, while certainty levels belong to a totally ordered scale. The semantics of a set of 'multiple agent' logic formulas is expressed by a mapping which associates a subset of agents with each interpretation (intuitively, the maximal subset of agents for whom this interpretation is possibly true). Soundness and completeness results are established. Then a joint extension of the multiple agent logic and possibilistic logic is outlined. In this extended logic, propositions are then associated with both sets of agents and certainty levels. A formula then expresses that 'all agents in set A believe that a is true at least at some level'. The semantics is then given in terms of fuzzy sets of agents that find an interpretation more or less possible. A specific feature of possibilistic logic is that the inconsistency of a knowledge base is a matter of degree. The proposed setting enables us to distinguish between the global consistency of a set of agents and their individual consistency (where both can be a matter of degree). In particular, given a set of multiple agent possibilistic formulas, one can compute the subset of agents that are individually consistent to some degree.

Introduction

Possibilistic logic [START_REF] Dubois | Possibilistic logic[END_REF][START_REF] Dubois | Possibilistic logic: A retrospective and prospective view[END_REF] was originally motivated by the need to manipulate statements of the form N (a) ≥ α in a logical way [START_REF] Dubois | Necessity measures and the resolution principle[END_REF], where N is a necessity measure (see, for example, [START_REF] Dubois | Possibility theory: Qualitative and quantitative aspects[END_REF] valued in a totally ordered scale and a is a proposition in classical logic. This statement means that the proposition is an accepted belief with a minimal strength, and is syntactically encoded under the form of a pair (a, α). Such certainty-qualified statements have a clear modal flavour. Possibilistic logic can also be viewed as a special case of a labelled deductive system [START_REF] Gabbay | Labelled deductive systems[END_REF]. Inference in possibilistic logic propagates certainty in a qualitative manner, using the law of the weakest link, and is inconsistencytolerant, as it enables non-trivial reasoning to be performed from the largest consistent subset of most certain formulas. A characteristic feature of this uncertainty theory is that a set of propositions {a ∈ L : N (a) ≥ α} in a propositional language L, the propositions of which are believed at least to a certain extent, is deductively closed (thanks to the mindecomposability of necessity measures with respect to conjunction). As a consequence, possibilistic logic remains very close to classical logic.

One may think of associating other 'labels' with classical logical formulas. It may be lower bounds of other measures in possibility theory, such as weak or strong possibility measures (see, for example, [START_REF] Dubois | Possibilistic logic: A retrospective and prospective view[END_REF]. It may also be a set of logical arguments in favour of a [START_REF] Lafage | A logic of supporters[END_REF], a set of distinct sources supporting the truth of the associated formula [START_REF] Dubois | Dealing with multi-source information in possibilistic logic[END_REF], or a set of time instants where the formula holds true for sure [START_REF] Dubois | Timed possibilistic logic[END_REF]. In this paper, we investigate in detail a 'multiple agent' logic where formulas are of the form (a, A), and A is a subset of agents that are known to believe that a is true. The idea was outlined in [START_REF] Dubois | Extensions multi-agents de la logique possibiliste [Multi-agent extensions of possibilistic logic[END_REF][START_REF] Dubois | Toward multiple-agent extensions of possibilistic logic[END_REF], and previously in [START_REF] Dubois | Dealing with multi-source information in possibilistic logic[END_REF] in an information fusion perspective, but the underlying semantics was never studied. In contrast, with timed possibilistic logic where it is important to make sure that the knowledge base remains consistent over time, what matters in multiple agent logic is the collective consistency of subsets of agents. The formula (a, A) will be understood at the semantic level as a constraint of the form N(a) ⊇ A, where N is a set-valued mapping that returns the set of agents for whom it is certain that a is true. Thus stating (a, A) amounts to saying that at least all the agents in A believe a.

The problem of processing information coming from various sources has a rather long tradition in logic, which at least dates back to [START_REF] Belnap | A useful four-valued logic[END_REF], whose approach was extended by [START_REF] Carnielli | Society semantics for multiple-valued logics[END_REF]. However, these authors only consider the situations where sources provide information about atomic formulas. A solution to this limitation has been proposed in [START_REF] Avron | Processing information from a set of sources[END_REF] using a new tool called non-deterministic logical matrices. The approach that we present in this paper handles information pertaining to any kind of propositional formulas, but we restrict ourselves to the case of propositions a jointly supplied by all agents in a set A, and the conjunction of formulas of the form (a, A). In other words, the language does not allow formulas like ¬(a, A) ('it is false that all the agents in A believe a') or disjunctions (a, A) ∨ (b, B). In particular, and in contrast with [START_REF] Belnap | A useful four-valued logic[END_REF], we do not represent pieces of information of the form 'there is at least one agent in A who believes a', which amounts to a disjunctive statement. Handling such formulas could be achieved by getting inspiration from the so-called generalised possibilistic logic [START_REF] Dubois | Stable models in generalized possibilistic logic[END_REF], as briefly mentioned at the end of this paper. Indeed, basic possibilistic logic, from which our multiple agent logic derives, suffers from the same limitations of handling only conjunctions of formulas of the form (a, α). Besides, the multiple agent logic can be nicely extended into a multiple agent possibilistic logic which handles formulas expressing that 'at least all agents in A believe that a is true at least at level α'. Then N becomes a fuzzy set-valued mapping that returns a weighted set of agents.

The paper is organised in the following way. The next section provides a brief refresher on possibilistic logic, where its main features are emphasised. Section 3 presents the multiple agent logic and its semantics, along with soundness and completeness results. Section 4 outlines the extension of multiple agent logic with certainty levels. These three sections are illustrated by a running example which shows how (in)consistency is handled in terms of subsets of agents and in terms of certainty levels. The concluding section briefly discusses prospective extensions of the proposed framework.

A refresher on possibilistic logic

We first describe the syntax of possibilistic logic, provide a short background on possibility theory that underlies its semantics, and then present its semantics in terms of possibility distributions and necessity measures, before ending the section with an illustrative example.

Syntax

Let L denote a propositional logical language. Well-formed formulas of L, denoted a, b, c, . . . , a i , . . . , are built from atoms, denoted p, q, r, . . . and the usual connectives ¬, ∧, ∨ (where a∨b = de f ¬(¬a∧¬b)) with parentheses ( and ), using the usual rules. ⊤ and ⊥ denote the tautology and the contradiction respectively. We take the axioms of propositional logic (PL) for granted, and the modus ponens as inference rule (a, ¬a ∨ b ⊢ b). We can equivalently use the resolution or cut rule (¬a ∨ b, a ∨ c ⊢ b ∨ c) and refutation (proving Ŵ ⊢ a amounts to proving Ŵ, ¬a ⊢ ⊥, where Ŵ stands for a collection of propositional formulas a 1 , . . . , a m and ⊥ is the contradiction).

Language

A (basic) possibilistic logic formula is a pair (a, α), with a ∈ L and α ∈ S, where S is a bounded totally ordered scale, equipped with an ordering relation denoted by ≤. Then α is called the certainty level (or weight) of the propositional formula a. More precisely, (a, α) means that it is certain at least at level α that a is true. In the following we take S = [0, 1]. But any bounded totally ordered set, finite or not, can be used as well. Then the complementation to 1 operation, namely 1-(•), used in the following should be understood as an order-reversing map. A possibilistic logic base Ŵ is a set of such pairs, namely Ŵ = {(a i , α i ) | i = 1, . . . , m}, understood as the conjunction of pairs (a i , α i ), with ∀i, α i > 0.

Axioms and inference rules

The axioms of possibilistic logic (Dubois et al., 1994), L for short, are those of PL, where each axiom schema is now supposed to hold with the maximal certainty, i.e., is associated with level 1. It has two inference rules:

• if β ≤ α then (a, α) ⊢ (a, β) (level weakening); • (¬a ∨ b, α), (a, α) ⊢ (b, α), ∀α ∈ (0, 1] (level modus ponens).
We may equivalently use the level weakening rule with the L counterpart of the resolution rule:

(¬a ∨ b, α), (a ∨ c, α) ⊢ (b ∨ c, α), ∀α ∈ (0, 1] (level resolution).
Using level weakening, it is then easy to see that the following inference rule is valid:

(¬a ∨ b, α), (a ∨ c, β) ⊢ (b ∨ c, min(α, β)) (α-β-resolution).
The idea that in a reasoning chain, the certainty level of the conclusion is the smallest of the certainty levels of the formulas involved in the premises is at the basis of the syntactic approach proposed by [START_REF] Rescher | Plausible reasoning[END_REF] for plausible reasoning, and would date back to Theophrastus, a follower of Aristotle.

The following inference rule, which we call formula weakening, also holds as a consequence of α-β-resolution:

if a ⊢ b then (a, α) ⊢ (b, α), ∀α ∈ (0, 1] (formula weakening).
Indeed, a ⊢ b expresses that ¬a ∨ b is valid in PL and thus (¬a ∨ b, 1) holds, which by applying the α-β-resolution rule with (a, α) yields the result.

It turns out that any valid deduction in propositional logic is valid as well in possibilistic logic where the corresponding propositions are associated with any level α ∈ (0, 1]. Thus since a, b ⊢ a ∧ b, we have (a, α), (b, α) ⊢ (a ∧ b, α). Note that we also have (a ∧ b, α) ⊢ (a, α) and (a ∧ b, α) ⊢ (b, α) by the formula weakening rule. Thus, stating (a ∧ b, α) is equivalent to stating (a, α) and (b, α). Thanks to this property, it is always possible to rewrite a L base under the form of a collection of weighted clauses.

Note also that if we assume that for any propositional tautology t, i.e., such that t ≡ ⊤, (t, α) holds with any certainty level, which amounts to saying that each axiom schema holds with any certainty level, then the α-β-resolution rule entails the level weakening rule, since (¬a ∨ a, β) together with (a ∨ c, α) entails (a ∨ c, β) when β ≤ α.

Inference and consistency

Inference in L is quite similar to the one in PL. We may either use the L axioms and the level weakening and level modus ponens rules, or equivalently proceed by refutation (proving Ŵ ⊢ (a, α) amounts to proving Ŵ, (¬a, 1) ⊢ (⊥, α) by repeated application of the α-β-resolution rule, where Ŵ stands for a collection of L formulas (a 1 , α 1 ), . . . , (a m , α m )). Moreover, note that Ŵ ⊢ (a, α) if and only if Ŵ α ⊢ (a, α) if and only if (Ŵ α ) * ⊢ a where Ŵ α = {(a i , α i ) ∈ Ŵ, α i ≥ α} and Ŵ * = {a i | (a i , α i ) ∈ Ŵ}. Thus, the certainty levels stratify the knowledge base Ŵ into nested level cuts Ŵ α , i.e., Ŵ α ⊆ Ŵ β if β ≤ α. A consequence (a, α) from Ŵ can only be obtained from formulas having a certainty level at least equal to α, so from formulas in Ŵ α ; then a is a classical consequence from the PL knowledge base (Ŵ α ) * , and α = max{β|Ŵ β ⊢ (a, α)}.

The inconsistency level of Ŵ is defined by

inc-l(Ŵ) = max{α | Ŵ ⊢ (⊥, α)}.
The possibilistic formulas in Ŵ whose level is strictly above inc-l(Ŵ) are safe from inconsistency, namely inc-l({(a i , α

i ) | (a i , α i ) ∈ Ŵ and α i > inc-l(Ŵ)}) = 0. Indeed, if α > inc-l(K ), (Ŵ α ) * is consistent.
In particular, we have the remarkable property that the classical consistency of Ŵ * is equivalent to saying that Ŵ has a level of inconsistency equal to 0. Namely, inc-l(Ŵ) = 0 if and only if Ŵ * is consistent.

The semantics of L is expressed in terms of possibility distributions, (weak) possibility measures and (strong) necessity measures. Let us first recall these notions.

Background on possibility theory

Let be the set of interpretations of the propositional logic language L. A possibility distribution [START_REF] Zadeh | Fuzzy sets a basis for a theory of possibility[END_REF] on is a function π from to [0,1]. It is supposed to reflect the available knowledge: π(ω) estimates to what extent it is possible that the interpretation ω corresponds to the real state of the world. The possibility distribution π is normalised if ∃ω ∈ such that π(ω) = 1. Normalisation expresses that at least one interpretation in is fully possible.

Based on a possibility distribution π , a function, from L to [0,1], called possibility measure, denoted by , is defined by [START_REF] Zadeh | Fuzzy sets a basis for a theory of possibility[END_REF] 1 as

(a) = max{π(ω) |ω |= a}.
The possibility measure estimates the extent to which a is compatible with the available knowledge represented by π . Informally, (a) = 0 means that a is impossible, while (a) = 1 means that a is fully possible and expresses full consistency with the current knowledge. Particularly, (a) = 0 when a is a contradiction. (a) = (¬a) = 1 expresses that both a and ¬a are fully possible, which corresponds to a case of total ignorance (about a).

Possibility measures are such that (⊤) = 1 and (⊥) = 0, and satisfy the characteristic axiom (a ∨ b) = max( (a), (b)).

A necessity measure N [START_REF] Dubois | Fuzzy sets and systems: Theory and applications[END_REF], defined from L to [0,1], is associated by duality with , namely

N (a) = 1 -(¬a),
expressing that a is all the more necessarily true, or certain, as ¬a is more impossible, and conversely the absence of certainty in favour of a (N (a) small) makes ¬a possible ( (¬a) high). Thus N is defined from π by

N (a) = min{1 -π(ω)|ω |= ¬a}.
Informally, N (a) estimates to what extent a is entailed by the available knowledge. N (a) = 1 means that a is sure, for instance N (a) = 1 when a is a tautology. The case of total ignorance in terms of necessity measure is represented by N (a) = N (¬a) = 0 indeed; from the available knowledge nothing enables us to say if a is rather true or rather false.

Necessity measures are such that N (⊤) = 1 and N (⊥) = 0, and satisfy the characteristic axiom

N (a ∧ b) = min(N (a), N (b)).
As a consequence, min(N (a), N (¬a)) = 0 should hold. Dually, max( (a), (¬a)) = 1. It can be checked that these two conditions hold for any a if and only if π is normalised. Thus having for some a, min(N (a), N (¬a)) > 0 (or equivalently max( (a), (¬a)) < 1) amounts to having π unnormalised, which intuitively expresses a situation of inconsistency, since one cannot be somewhat certain of both a and ¬a, or find both a and ¬a somewhat impossible.

Semantics

We have now recalled the notions needed for presenting the semantics of L [START_REF] Dubois | Possibilistic logic[END_REF]. Let us first consider a L formula (a, α) that encodes the statement N (a) ≥ α. Its semantics is given by the following possibility distribution π (a,α) , defined by

π (a,α) (ω) = 1 if ω a and π (a,α) (ω) = 1 -α if ω ¬a.
Intuitively, the underlying idea is that any model of a should be fully possible, and that any interpretation that is a counter-model of a is all the less possible as a is more certain, i.e., as α is higher. It can easily be checked that the associated necessity measure is such that N (a,α) (a) = α, and π (a,α) is the least informative possibility distribution (i.e., maximising possibility degrees) such that this constraint holds. In fact, any possibility distribution π such that ∀ω, π(ω) ≤ π (a,α) (ω) is such that its associated necessity measure N satisfies N (a) ≥ N (a,α) (a) = α (hence is more committed).

Let us now consider a L knowledge base Ŵ = {(a i , α i ), i = 1, . . . , m}, thus corresponding to the conjunction of L formulas (a i , α i ), each representing a constraint N (a i ) ≥ α i . The base Ŵ is semantically associated with the possibility distribution

π Ŵ (ω) = min i=1,...,m π (a i ,α i ) (ω) = min i=1,...,m max([a i ](ω), 1 -α i ),
where [a i ] is the characteristic function of the models of a i , namely [a i ](ω) = 1 if ω a i and [a i ](ω) = 0 otherwise. Thus, the least informative induced possibility distribution π Ŵ is obtained as the min-based conjunction of the fuzzy sets of interpretations (with membership functions π (a i ,α i ) ), representing each formula. It can be checked that

N Ŵ (a i ) ≥ α i for i = 1, . . ., m,
where N Ŵ is the necessity measure defined from π Ŵ . Note that we may only have an inequality here since Ŵ may, for instance, include two formulas associated with equivalent propositions, but with distinct certainty levels.

So a L knowledge base is understood as a set of constraints N (a i ) ≥ α i for i = 1, . . . , m, and the set of possibility distributions π associated with N that are compatible with this set of constraints has a largest element which is nothing but π Ŵ , i.e., we have ∀ω, π(ω) ≤ min i=1,...,m π (a i ,α i ) = π Ŵ (ω). Thus, the possibility distribution π Ŵ semantically representing a L base Ŵ is the one which assigns the largest possibility degree to each interpretation, in agreement with the semantic constraints N (a i ) ≥ α i for i = 1, . . . , m that are associated with the formulas (a i , α i ) in Ŵ. Thus, any possibility distribution π ≤ π Ŵ semantically agrees with Ŵ, which can be written π Ŵ.

The semantic entailment is defined by

Ŵ (a, α) if and only if ∀ω, π Ŵ (ω) ≤ π {(a,α)} (ω).
It can be shown [START_REF] Dubois | Possibilistic logic[END_REF]) that possibilistic logic is sound and complete w.r.t. this semantics, namely Ŵ ⊢ (a, α) if and only if Ŵ (a, α).

Moreover, we have

inc-l(Ŵ) = 1 -max ω∈ π Ŵ (ω),
which acknowledges the fact that the normalisation of π Ŵ is equivalent to the classical consistency of Ŵ * . Thus, an important feature of possibilistic logic is its ability to deal with inconsistency. The consistency of Ŵ is estimated by the extent to which there is at least one interpretation completely possible for Ŵ, i.e., by the quantity cons-l

(Ŵ) = 1 -inc-l(Ŵ) = max ω∈ π Ŵ (ω) = max π|=Ŵ max ω∈ π(ω).
Table 1. Detailed computation of the possibility distribution in the example.

ω π {(¬ p∨q,.8)} π {(¬ p∨r,.9)} π {(¬ p∨¬r,.1)} π {(¬q∨r,.6)} π {( p,.3)} π {(q,.7)} π {(¬q,.2)} π {(r,.8)} π Ŵ pqr 1 1 0.9 1 1 1 0.8 1 0.8 pq¬r 1 0.1 1 0.4 1 1 0.8 0.2 0.1 p¬qr 0.2 1 0.9 1 1 0.3 1 1 0.2 p¬q¬r 0.2 0.1 1 1 1 0.3 1 0.2 0.1 ¬ pqr 1 1 1 1 0.7 1 0.8 1 0.7 ¬ pq¬r 1 1 1 0.4 0.7 1 0.8 0.2 0.2 ¬ p¬qr 1 1 1 1 0.7 0.3 1 1 0.3 ¬ p¬q¬r 1 1 1 1 0.7 0.3 1 0.2 0.2

An example in possibilistic logic

Let us illustrate the previously introduced notions on the following L base Ŵ, which is in clausal form ( p, q, r are atoms): {(¬ p ∨ q, 0.8), (¬ p ∨ r, 0.9), (¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (¬q, 0.2), (r, 0.8)}.

First, it can be checked that inc-l(Ŵ) = 0.2. Thus, the sub-base Ŵ 0.3 = {(¬ p ∨ q, 0.8),(¬ p ∨ r, 0.9),(¬q ∨ r, 0.6),( p, 0.3),(q, 0.7), (r, 0.8)} is safe from inconsistency, and its deductive closure is consistent, i.e., ∄a, ∄α > 0, ∄β > 0 such that Ŵ 0.3 ⊢ (a, α) and Ŵ 0.3 ⊢ (¬a, β). By contrast, Ŵ 0.1 ⊢ (¬r, 0.1) and Ŵ 0.1 ⊢ (r, 0.8). Note also that while (¬ p ∨ r, 0.9), ( p, 0.3) ⊢ (r, 0.3), we clearly have Ŵ ⊢ (r, 0.8) as well. This illustrates the fact that in possibilistic logic we are interested in practice in the proofs leading to the highest certainty levels. Besides, in case Ŵ contains (r, 0.2) rather than (r, 0.8), then (r, 0.2) would be of no use, since subsumed by (r, 0.3). Indeed, it can be checked that Ŵ \ {(r, 0.8)} and (Ŵ \ {(r, 0.8)}) ∪ {(r, 0.2)} are associated with the same possibility distribution.

The possibility distribution associated with Ŵ, whose computation is detailed in Table 1, is given by π Ŵ ( pqr

) = 0.8; π Ŵ (¬ pqr ) = 0.7; π Ŵ (¬ p¬qr ) = 0.3; π Ŵ ( p¬qr ) = π Ŵ (¬ pq¬r ) = π Ŵ (¬ p¬q¬r ) = 0.2; π Ŵ ( pq¬r ) = π Ŵ ( p¬q¬r ) = 0.1.
As can be seen cons-l(Ŵ) = max ω∈ π Ŵ (ω) = 0.8 and inc-l(Ŵ) = 1 -0.8 = 0.2. Similarly, inc-l(Ŵ \ {(¬q, 0.2)}) = 0.1 and inc-l(Ŵ \ {(¬q, 0.2), (¬ p ∨ ¬r, 0.1)}) = 0.

Multiple agent logic

We now introduce a multiple agent logic (ma-L) which parallels possibilistic logic in many respects, starting with the syntactic aspects, then introducing a set-valued counterpart of the notions of possibility distribution, possibility measure, and necessity measure, before presenting the semantics that relies on these notions, and ending with an illustrative example.

Syntax

Language L still denotes a propositional logic language. Let All denote the finite set of all agents considered. A subset of agents is denoted by capital letters A, B, or by indexed letters A i for i = 1, . . . , m. Clearly, the set of subsets of agents equipped with the usual set operations, i.e., (2 AL L , ∩, ∪, , ⊆), is a Boolean algebra, thus only partially ordered, which contrasts with the scale S used in possibilistic logic.

A multiple agent propositional formula (ma-formula) is a pair (a, A), where a is a classical propositional formula of L and A is a non-empty subset of All, i.e., A ⊆ All. The intuitive meaning of formula (a, A) is that at least all the agents in A believe that a is true. In spite of the obvious parallel with possibilistic logic (where propositions are associated with levels expressing the strength with which the propositions are believed to be true), (a, A) should not be just understood as another way of expressing the strength of the support in favour of a (the larger A, the stronger the support), but rather as a piece of information linking a proposition with a group of agents. A multiple agent knowledge base (ma-base) is simply a finite set Ŵ = {(a i , A i ), i = 1, . . . , m}, viewed as the conjunction of ma-formulas. Ŵ • denotes the set of classical formulas obtained from Ŵ by ignoring the sets of agents:

Ŵ • = {a i | (a i , A i ) ∈ Ŵ, i = 1, . . . , m}.

Inference rules and axioms

Ma-L has two inference rules:

• if B ⊆ A then (a, A) ⊢ (a, B) (subset weakening); • (¬a ∨ b, A), (a, A) ⊢ (b, A), ∀A ∈ 2 AL L \ ∅ (subset modus ponens).
The axioms of ma-L are those of PL where each axiom schema is now supposed to hold for the maximal set of agents, i.e., is associated with subset All. We may equivalently use the subset weakening rule with the ma-L counterpart of the resolution rule:

(¬a ∨ b, A), (a ∨ c, A) ⊢ (b ∨ c, A), ∀A ∈ 2 AL L \ ∅ (subset resolution).
Using subset weakening (since A ∩ B ⊆ A and A ∩ B ⊆ B), it is then easy to see that the following inference rule is valid:

if A ∩ B = ∅, then (¬a ∨ b, A), (a ∨ c, B) ⊢ (b ∨ c, A ∩ B) (A-B-resolution).
Clearly, if A ∩ B = ∅, the information resulting from applying the rule does not belong to the language, and would make little sense: it is of no use to put vacuous formulas of the form (a, ∅) in a ma-base as it corresponds to information possessed by (at least) no agent. As a consequence, we also have a formula weakening rule:

if a ⊢ b then (a, A) ⊢ (b, A), ∀A ∈ 2 AL L \ ∅ (ma-formula weakening).
As for L, any valid deduction in propositional logic is valid as well in ma-L where the corresponding propositions are associated with a subset A ∈ 2 AL L \ ∅. Thus, similarly to L, stating (a ∧ b, A) is equivalent to stating (a, A) and (b, A). Thanks to this property, it is always possible to rewrite a ma-base under the form of a collection of clauses labelled by subsets of agents.

Inference and consistency

Inference in ma-L is similar to that of PL. We may either use the ma-L axioms and the subset weakening and subset modus ponens rules, or equivalently proceed by refutation (proving Ŵ ⊢ (a, A) amounts to proving Ŵ, (¬a, All) ⊢ (⊥, A) by repeated application of the A-B-resolution rule, where Ŵ stands for a collection of ma-formulas (a 1 , A 1 ), . . . , (a m , A m )).

Since 2 AL L is not totally ordered like S is, we cannot 'slice' Ŵ into layers. Still, one can define the restriction of Ŵ to a subset A ⊆ All as

Ŵ A = {(a i , A i ∩ A) | A i ∩ A = ∅ and (a i , A i ) ∈ Ŵ}.
Moreover, an inconsistency subset of agents for Ŵ can be defined as

inc-s(Ŵ) = {A ⊆ All | Ŵ ⊢ (⊥, A)} and inc-s(Ŵ) = ∅ if ∄A s.t. Ŵ ⊢ (⊥, A).
Note that in this definition, A = ∅ is not forbidden. For instance, let Ŵ = {( p, A), (q, B),

(¬ p ∨ q, C), (¬q, D)}, then inc-s(Ŵ) = (A ∩ C ∩ D) ∪ (B ∩ D), and obviously inc-s(Ŵ A∩B∩C∩D ) = ∅.
Clearly, it is not the case that the consistency of Ŵ (inc-s(Ŵ) = ∅) implies that Ŵ • is consistent. This feature contrasts with possibilistic logic. Just consider the example Ŵ = {(a, A), (¬a, A)}, then inc-s(Ŵ) = A∩ A = ∅ while Ŵ • is inconsistent. This is because there is nothing anomalous with agents that contradict each other. Yet the consistency of Ŵ • does entail inc-s(Ŵ) = ∅.

The semantics of ma-L is expressed in terms of set-valued possibility distributions, setvalued possibility measures and set-valued necessity measures, which are now introduced.

A set-valued possibility theory

A multiple agent possibility distribution (ma-distribution) is a function π from a set of interpretations to 2 All , the set of subsets of agents. Then π (ω) represents the subset of agents in All who find ω possible. If π (ω) = ∅, it means that all agents agree that ω is impossible. A ma-distribution is ma-normalised if ∃ω ∈ , π (ω) = All. This expresses a collective (or social) consistency since there exists at least one interpretation that all agents find possible.

Associated with π , we can define a function from L to 2 All that will be called a multiple agent possibility measure (ma-possibility measure) by analogy, for obvious reasons, in the following way:

(a) = ω|=a π (ω).

It is the set of agents for whom a is possibly true. Note that there is an equivalent definition of (a). Namely, instead of focusing on the sets π (ω) of agents that consider each interpretation possible, one can represent the same information by focusing on the set of interpretations E k considered possible by each agent k ∈ All, obviously defined as

E k = {ω, k ∈ π (ω)}. Dually we have that π(ω) = {k ∈ All, ω ∈ E k }. Then it is easy to see that (a) = ω|=a π (ω) = {k, E k ∩ [a] = ∅}.
By convention, (⊥) = ∅. Moreover, if π is ma-normalised, then (⊤) = All. However, (⊤) = All does not entail that π is ma-normalised. Just consider the example where = { p, ¬ p}, π ( p) = A, π (¬ p) = A. Then (⊤) = A ∪ A = All, while π is not ma-normalised. This situation departs from usual valued possibility theory in finite settings, where (⊤) = 1 is equivalent to ∃ω, π(ω) = 1.

Besides, the condition (⊤) = All is equivalent to ω∈ π(ω) = All. This condition means that the set of agents who find at least one interpretation possible is precisely the whole set of agents All. This means that each agent is individually consistent, even if altogether the agents are not necessarily mutually so. For this reason, the condition

(⊤) = ω∈ π (ω) = All
is called the i-normalisation of π . Clearly, (⊤) ⊂ All if and only if ∃k ∈ All : E k = ∅, and the set of individually inconsistent agents is I = All\ (⊤). Clearly (a)∪ (¬a) = (⊤) (the set of self-consistent agents), while (a) ∩ (¬a) is the set of agents that ignore everything about a.

We define a multiple agent necessity measure (ma-necessity measure) as usual by duality, N : L → 2 All , namely N(⊤) = All (tautologies are certain for any agent), and

N(a) = (¬a) = ω|=¬a π (ω).
Note that if (⊤) = All, we may fail to have the inclusion ∀a ∈ L, N(a) ⊆ (a). Indeed, while (a) ⊆ (⊤), N(a) includes the set I of inconsistent agents. So, N(a) ⊆ (a) for all a if and only if I = ∅. However we always have that N(a)∩ (¬a) = ∅.

In contrast, and as suggested by [START_REF] Smets | Belief functions[END_REF] for belief functions, we can define the set of agents that believe a as

Bel(a) = {k : ∅ = E k ⊆ [a]},
which gathers the subset of self-consistent agents who are sure that a is true. We obviously have the desirable inclusion ∀a ∈ L, Bel(a) ⊆ (a), namely the consistent agents who are sure that a is true are among the ones who think that a is possibly true. It is easy to see that Thus, the set of agents who think that a ∧ b is certainly true is the intersection of the set of agents who think that a is certainly true, and of the set of agents who think that b is certainly true. Moreover, we have N(a ∨ b) ⊇ N(a) ∪ N(b) (and likewise for Bel): the set of agents who are certain about a ∨ b is larger (in the broad sense) than the union of the agents who are certain about a and of the agents who are certain about b.

Bel(a) = (⊤) \ (¬a) = (⊤) ∩ N(
If (⊤) = All (i-normalisation), then Bel(a) = (¬a) = N(a). Hence, under inormalisation, Bel(a) ∪ (¬a) = All, i.e., any agent finds either a certainly true or ¬a possibly true, but not both (since in any case, N(a) ∩ (¬a) = ∅). Otherwise there would exist one agent who is inconsistent. But it does not hold that N(a) = ∅ implies that (a) = All, in contrast with the usual possibility theory.

As a summary, Figure 1 pictures the relations between the set (a) of agents who think that a is possible, the set (¬a) of agents who think that ¬a is possible, the set I of agents who are individually inconsistent, the set Bel(a) of consistent agents who are certain of a, and the set Bel(¬a) of consistent agents who are certain of ¬a.

Possibilistic semantics of the multiple agent logic

We have now introduced the notions needed for presenting the semantics of ma-L. Let us first consider a ma-L formula (a, A), which represents the piece of information 'at least all agents in A believe a'. In other words, the agents in A find any interpretation of ¬a impossible. This means that the maximal set of agents who think that ¬a is possible is A (these agents, like those in A, also find the interpretations of a possible, according to this knowledge). Thus, the fact that all agents in A believe a does not prevent all agents from finding the models of a possible. This leads to the following semantic representation of formula (a, A) by the ma-distribution π {(a,A)} :

∀ω ∈ , π {(a,A)} (ω) = All if ω |= a A if ω |= ¬a,
where is the set of interpretations associated with L. It can be checked that the associated ma-necessity measure is such that N {(a,A)} (a) = A. In fact, any possibility distribution π

such that π ⊆ π {(a,A)} , i.e., ∀ω ∈ , π (ω) ⊆ π {(a,A)} (ω), has its associated ma-necessity measure N satisfying N(a) ⊇ N {(a,A)} (a) = A.
More generally, the ma-distribution π Ŵ semantically associated with a set of maformulas Ŵ = {(a i , A i ), i = 1, . . . , m} is given by

π Ŵ (ω) = All if ∀(a i , A i ) ∈ Ŵ, ω |= a i {A i : (a i , A i ) ∈ Ŵ, ω |= ¬a i } otherwise.
Thus, the value π Ŵ (ω) of the ma-distribution for ω is obtained as the intersection of the different subsets A i of agents that still find ω possible according to the different formulas (a i , A i ) violated by this interpretation: the larger the set of agents who find the interpretation impossible, the smaller the maximal set of those that may find it possible. It can be checked that

N Ŵ (a i ) ⊇ A i for i = 1, . . . , m,
where N Ŵ is the ma-necessity measure defined from π Ŵ . Note that we may only have an inequality here since Ŵ may, for instance, include two formulas associated with equivalent propositions, but with distinct subsets of agents. Thus, π Ŵ is the largest ma-distribution satisfying the set of formulas Ŵ in the sense that it allocates to each interpretation the maximal subset of agents that may find it possible according to the constraints expressed by the formulas (a i , A i ), namely the constraints N Ŵ (a i ) ⊇ A i . Any ma-distribution π such that π ⊆ π Ŵ (i.e., ∀ω ∈ , π (ω) ⊆ π Ŵ (ω)) semantically agrees with Ŵ, which can be written π Ŵ. The semantic entailment is defined by

Ŵ (a, A) if and only if ∀ω, π Ŵ (ω) ⊆ π {(a,A)} (ω).
Thus, if π Ŵ then π {(a, A)}. For proving the soundness of the rule we have to check that, if

A 1 ∩ A 2 = ∅, ∀ω, π(ω) {(c 1 ,A 1 ),(c 2 ,A 2 )} ⊆ π(ω) {(c 3 ,A 1 ∩A 2 )}
where (c 1 , A 1 ) and (c 2 , A 2 ) are ma-L clauses, and c 3 is any classical resolvent of c 1 and c 2 , then (c 3 ,

A 1 ∩ A 2 ) is a resolvent of (c 1 , A 1 ) and (c 2 , A 2 ) by the A-B-resolution rule (c 1 , A 1 ), (c 2 , A 2 ) ⊢ (c 3 , A 1 ∩ A 2 ). We have π {(c 1 ,A 1 ),(c 2 ,A 2 )} (ω) = All i f ω |= c 1 ∧ c 2 A 1 ∩ A 2 i f ω |= ¬(c 1 ∧ c 2 ) and π {(c 3 ,A 1 ∩A 2 )} (ω) = All i f ω |= c 3 A 1 ∩ A 2 i f ω |= ¬c 3 . It holds since the situations π {(c 1 ,A 1 ),(c 2 ,A 2 )} (ω) = All and π {(c 3 ,A 1 ∩A 2 )} (ω) = A 1 ∪ A 2 cannot occur, as by hypothesis ω |= c 1 ∧ c 2 ⇒ ω |= c 3 .
It is easy to see that in the other situations the inclusion holds. So the A-B-resolution rule is sound.

For completeness, suppose Ŵ ⊢ (a, A). Then ∄ ⊆ Ŵ, ⊢ (a, A) using A-B refutation, with all formulas in . Hence for all such ⊆ Ŵ, either

• ⊢ a, or • ⊢ a but A ⊆ ∩ (a i ,A i )∈ A i .
In the first case • |= a (completeness of PL), hence |= (a, A) as well.

In the second case

∃(i, k) : k ∈ A, k ∈ A i . Let • {k} = {a j : k ∈ A j , (a j , A j ) ∈ }, clearly •
{k} ⊢ a since it does not contain a i and a i is needed to derive a. Hence • {k} |= a (completeness of PL). But then {k} |= (a, {k}) either, and |= (a, A). Since this is the case for all subsets of Ŵ, Ŵ |= (a, A).

Remark. Another proof could proceed by equivalences:

Ŵ ⊢ (a, A) ⇐⇒ Ŵ ⊢ (a, {k}), ∀k ∈ A ⇐⇒ Ŵ {k} ⊢ (a, {k}), ∀k ∈ A ⇐⇒ Ŵ • {k} ⊢ a, ∀k ∈ A ⇐⇒ Ŵ • {k} |= a, ∀k ∈ A (completeness of PL). The latter stands for E k = [Ŵ • {k} ] ⊆ [a]. Then again Ŵ • {k} |= a ⇐⇒ Ŵ {k} |= (a, {k}) (this is {(ω, k) : ω ∈ E k } ⊆ {(ω, k) : ω ∈ [a]}); then Ŵ {k} |= (a, {k}) ⇐⇒ Ŵ |= (a, {k}) (adding irrelevant agents to Ŵ {k} ).
And since all of these derivations hold for all k ∈ A, this is equivalent to Ŵ |= (a, A).

As defined in the previous subsection, there exist two forms of normalisation for a ma-distribution π , the ma-normalisation and the i-normalisation, the first one entailing the second one:

• ∃ω ∈ such that π (ω) = All (ma-normalisation); • {π(ω), ω ∈ } = All (i-normalisation). Proposition 2. Given a ma-base Ŵ = {(a i , A i ), i = 1, . . . , m}, the ma-normalisation of π Ŵ is equivalent to the consistency of Ŵ • . Proof. π Ŵ is ma-normalised if and only if ∃ω ∈ such that π Ŵ (ω) = All, if and only if ω |= a i , ∀i = 1, . . . , m, that is, Ŵ • is consistent. Proposition 3. Given a ma-base Ŵ = {(a i , A i ), i = 1, . . . , m}, the i-normalisation of π Ŵ is equivalent to the consistency of (Ŵ k ) • = {a i |(a i , A i ) ∈ Ŵ, k ∈ A i }, for all agents k ∈ i=1,...,m A i .
Proof. Indeed, assume ∃k such that (Ŵ k ) • is inconsistent; then this agent k has an inconsistent set of beliefs, which contradicts i-normalisation.

More generally, cons-s(Ŵ) = ω∈ π Ŵ (ω) = Ŵ (⊤) is the subset of agents who are individually consistent in Ŵ, while its complement inc-s(Ŵ) = ω∈ π Ŵ (ω) = I is the subset of agents who are individually inconsistent. Lastly, inc-s(Ŵ) as just defined is precisely equal to {A ⊆ All | Ŵ ⊢ (⊥, A)}, since they respectively correspond to the semantic and syntactic ways of computing the subset of individually inconsistent agents.

A multiple agent logic example

Let us consider the following ma-base: Ŵ = {(¬ p∨q,A), (¬ p∨q,C), (¬ p∨r,A), (¬ p∨¬r,B), (¬q∨r,All), ( p,All), (q,A), (¬q,D), (r,C)}.

Note that the classical PL base Ŵ • coincides with Ŵ * in the example in Section 2.4. The ma-distribution associated with Ŵ is given by π

Ŵ ( pqr ) = B ∩ D; π Ŵ ( pq¬r ) = π Ŵ (¬ pqr ) = π Ŵ (¬ pq¬r ) = π Ŵ (¬ p¬qr ) = π Ŵ (¬ p¬q¬r ) = ∅; π Ŵ ( p¬qr ) = A ∩ B ∩ C; π Ŵ ( p¬q¬r ) = A ∩ C.
Its detailed computation can be found in Table 2. The set of agents who are individually consistent is given by

cons-s(Ŵ) = Ŵ (⊤) = (A ∩ C) ∪ (A ∩ B ∩ C) ∪ (B ∩ D) = (A ∩ C) ∪ (B ∩ D)
and then the set of agents who are individually inconsistent is

I = inc-s(Ŵ) = (A ∪ C) ∩ (B ∪ D).
If we now ask who believes r , it can easily be seen that the answer is

N(r ) = A ∪ C ∪ D, since Ŵ ⊢ (r, A), Ŵ ⊢ (r, C), Ŵ ⊢ (r, D), and thus Ŵ ⊢ (r, A ∪ C ∪ D).
If we want to know who believes r and is consistent, then we have to compute Bel(r ) in the form

(A∪C ∪ D)\inc-s(Ŵ) = (A∪C ∪ D)\((A∪C)∩(B ∪ D)) = (B ∩C ∩ D)∪(A∩ B ∩C ∩ D).
Besides, note that in Ŵ, we have four distinct symbols pertaining to subsets of agents, namely A, B, C, D. This induces a partition of the set of agents into 2 4 = 16 subsets of indistinguishable agents sharing the same opinion (which correspond to the interpretations of the language induced by these symbols). For each subset S in this partition, one can compute the propositional part (Ŵ S ) • of the restriction Ŵ S of Ŵ to S. The result is given below. Then, the propositional bases that are consistent are marked with * . The facts that Ŵ ⊢ (r, A ∪C ∪ D) and inc-s(Ŵ) = (A ∪C)∩(B ∪ D) can be checked using these PL bases.

Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q, ¬ p ∨ ¬r, r, ¬q} Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q, ¬ p ∨ ¬r, r } Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q, ¬ p ∨ ¬r, ¬q} Ŵ • A∩B∩C∩D = {¬ p q, p r, ¬q ∨ r, p, q, ¬ p ∨ ¬r } Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q, r, ¬q} Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q, r } * Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q, ¬q} Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬ p ∨ r, ¬q ∨ r, p, q} * Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬q ∨ r, p, ¬ p ∨ ¬r, r, ¬q} Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬q ∨ r, p, ¬ p ∨ ¬r, r } Ŵ • A∩B∩C∩D = {¬q ∨ r, p, ¬ p ∨ ¬r, ¬q} * Ŵ • A∩B∩C∩D = {¬q ∨ r, p, ¬ p ∨ ¬r } * Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬q ∨ r, p, r, ¬q} Ŵ • A∩B∩C∩D = {¬ p ∨ q, ¬q ∨ r, p, r } * Ŵ • A∩B∩C∩D = {¬q ∨ r, p, ¬q} * Ŵ • A∩B∩C∩D = {¬q ∨ r, p} *
Lastly, using here the obvious identity Ŵ • S∪T = Ŵ • S ∩ Ŵ • T , we could compute the sets of beliefs of any given subset of agents. However, this would be an extremely costly process. This points out that beyond the proof that Ŵ ⊢ (a, A) by establishing that Ŵ ∪ {(¬a, All)} ⊢ (⊥, A) using the A-B-resolution rule, we need a dual inference mechanism where A is 'fixed', rather than a, taking advantage of the 'symmetrical' roles played by a and A.

Outline of a multiple agent possibilistic logic

We now introduce a multiple agent possibilistic logic (ma--L) which extends both possibilistic logic and the multiple agent of the previous section.

One may think of two different ways for building a joint generalisation of the two settings. A first idea would be to embed -L inside ma-L. This would mean having in the syntax formulas of the form ((a, α), A), understood as (at least) all the agents in A have the uncertain piece of belief (a, α). Ma-L would then correspond to formulas of the form ((a, 1), A). The other way to have a graded generalisation of ma-L, outlined in this section, is to consider that the language is now made of formulas of the form (a, F) where F is a fuzzy set of agents. The degree of membership µ F (k) is the minimal degree of certainty of a for this agent. Note that in general, F is not normalised, i.e., max k µ F (k) = 1. Clearly, All is partitioned by F into subgroups of agents F i having the same certainty level α i associated with proposition a (including the subgroup of agents having zero certainty); then, F can be viewed as a weighted union i α i /F i , where all the α i are distinct and strictly positive, and the F i s are classical, mutually disjoint subsets.

We start with the syntactic aspects of ma--L, then introduce a fuzzy set-valued counterpart of the notions of possibility distribution, possibility measure, and necessity measure, before presenting the semantics that rely on these notions, and ending with an illustrative example.

Syntax

A ma--L formula is a pair (a, F) where a is a proposition in L and F is a fuzzy subset of All. Namely, F belongs to the complete distributive lattice L = [0, 1] All , where L is equipped with the fuzzy set max-based union ∪, min-based intersection ∩, and inclusion F ⊆ G ⇐⇒ µ F µ G . The following equivalence is expected:

(a, F), (a, F ′ ) ⊢⊣ (a, F ∪ F ′ ).
This generalises the syntactic equivalence of ma-L (a, A), (a, B) ⊢⊣ (a, A ∪ B). We also expect the resolution rule, if F and G do not have disjoint supports,

(¬ p ∨ q, F); ( p ∨ r, G) ⊢ (q ∨ r, F ∩ G),
and the weakening rule, if F ⊆ G then (a, F) ⊢ (a, G).

In the following we use particular fuzzy sets

F = (α/A) such that (α/A)(k) = α if k ∈ A, and (α/A)(k) = 0 if k ∈ A.
Thus, we restrict ourselves to formulas of the form (a, α/A) that encode the piece of information 'at least all agents in A believe a at least at level α', and formulas with more complex weights (a, i α i /F i ).

In the syntactic equivalence between The result is equivalent to the set of elementary formulas {(a, α/A ∩ B), (a, max(α, β)/A ∩ B), (a, β/A ∩ B)}, with the proviso that we omit formulas weighted by empty sets.

A multiple agent possibilistic logic base (ma--L base) is then defined as a finite set (i.e., conjunctions) of maformulas. Let Ŵ * • denote the set of classical formulas obtained from Ŵ by ignoring the fuzzy sets of agents: if Ŵ = {(a i , α i /A i ), i = 1, . . . , m} then Ŵ * • = {a i , i = 1, . . . , m}.

The resolution rule becomes in ma--L

(¬ p ∨ q, α/A); ( p ∨ r, β/B) ⊢ (q ∨ r, min(α, β)/(A ∩ B)).
When α = 1 = β, we retrieve the ma-L resolution rule, identifying (a, A) with (a, 1/A). When A = All = B, we retrieve the possibilistic resolution rule.

Inference in ma--L is very similar to the one in ma-L. We proceed by refutation, i.e., proving Ŵ ⊢ (a, F) amounts to proving Ŵ, (¬a, All) ⊢ (⊥, F) by repeated application of the above resolution rule, also using the equivalence (a, G), (a, G ′ ) ⊢⊣ (a, G ∪ G ′ ) where G and G ′ are fuzzy sets. Then the fuzzy inconsistency subset for Ŵ is now obtained as inc-sl(Ŵ) = {α/A | Ŵ ⊢ (⊥, α/A)}. It yields the fuzzy set of individually inconsistent agents.

Multiple agent possibility theory

A graded multiple agent possibility distribution (ma--distribution) is a function π from a set of interpretations to [0, 1] All , the set of fuzzy subsets of agents. Then π (ω) represents the fuzzy subset of agents in All who find ω possible to some extent. Associated with π , we can define a function from L to [0, 1] All , which will be called the graded multiple agent possibility measure -possibility measure) for obvious reasons, in the following way (now using the max-based fuzzy set union):

(a) = ω∈ {π(ω), ω |= a}.
(a) is the fuzzy set of agents who think that it is possible to some extent that a is true. By duality, N(a) = (¬a) = ω∈ {π (ω), ω |= ¬ p} where fuzzy set complementation is defined as usual by F(k) = 1-F(k), and we use the min-based fuzzy set intersection. N(a) is the fuzzy set of agents who are certain to some extent that a is true, or are inconsistent to some degree.

The ma-normalisation continues to be defined as ∃ω ∈ , π (ω) = All (All is clearly the same as 1/All), and is still equivalent to the consistency of Ŵ * • . The i-normalisation is still defined by (⊤) = ω∈ π (ω) = All; it still means that all the agents are individually consistent. More generally, the degree of membership of an agent k to the fuzzy set (⊤) is nothing but the level to which the possibilistic logic base made of the uncertain pieces of belief held by the agent is consistent (in the -L sense).

Semantics

Let us consider a ma--L formula (a, α/A), which expresses that a is certain at least at level α for at least all agents in A. So the set of agents in A finds any interpretation of a completely possible. Furthermore, the other agents in A are free to find the interpretation of a completely possible. Then, the maximal set of agents who find any interpretation of a completely possible is A ∪ A = All. Besides, the maximal set of agents who find any interpretation of ¬a possible are the agents in A at least at level 1α, and the agents in A at least at level 1. This leads to the following semantic representation of (a, α/A):

π {(a,α/A)} (ω) = 1/All if ω |= a {(1 -α)/A ∪ 1/A} if ω |= ¬a.
In agreement with the syntactic equivalence (a, α/A), (a, β/B) ⊢⊣ (a, (α/A)∪

(β/B)), if ω |= ¬a, π {(a,α/A),(a,β/B)} (ω) = π {(a,α/A)} (ω) ∩ π {(a,β/B)} (ω) = ((1 -α)/A ∪ 1/A) ∩ ((1 -β)/B ∪ 1/B) = (1 -α)/(A ∩ B) ∪ (1 -max(α, β))/(A ∩ B) ∪ (1 -β)/(A ∩ B) ∪ 1/(A ∩ B), which defines π {(a,(α/A)∪(β/B))} (ω).
More generally, the ma--distribution associated with Ŵ = {(a i , α i /A i ), i = 1, . . . , m} is the mapping π from to L:

π Ŵ (ω) = 1/All if ∀(a i ,α i /A i ) ∈ Ŵ, ω |= a i {(1 -α i )/A i ∪ 1/A i | (a i , α i /A i ) ∈ Ŵ, ω |= ¬a i } otherwise.
Thus, the semantics of a base Ŵ = {(a i , α i /A i ) | i = 1, . . . , m} is now in terms of a fuzzy set-valued distribution, for which it can be checked that N(a i ) ⊇ α i /A i , where N(a) = (¬a) and (a) = ω: ω a π Ŵ (ω).

Soundness and completeness of ma--L can be conjectured on the basis of the soundness and completeness of -L and of ma-L, and is a matter left for further research.

A multiple agent possibilistic logic example

Let us consider the following ma--L base, which combines the certainty levels and the agent subsets of the two previous examples on the same propositional formulas: Ŵ = {(¬ p ∨ q, 0.6/A), (¬ p ∨ q, 0.8/C), (¬ p ∨ r, 0.9/A), (¬ p ∨ ¬r, 0.1/B), (¬q ∨ r, 0.6/All), ( p, 0.3/All), (q, 0.7/A), (r, 0.8/C), (¬q, 0.2/D)}.

The ma--distribution associated Ŵ is given by π

Ŵ ( pqr ) = (0.9/B ∪ 1/B) ∩ (0.8/D ∪ 1/D) π Ŵ ( pq¬r ) = (0.1/A ∪ 0.4/A) ∩ (0.2/C ∪ 0.4/C) ∩ (0.8/D ∪ 0.4/D) π Ŵ ( p¬qr ) = (0.3/A ∪ 1/A) ∩ (0.9/B ∪ 1/B) ∩ (0.2/C ∪ 1/C) π Ŵ ( p¬q¬r ) = (0.1/A ∪ 1/A) ∩ (0.2/C ∪ 1/C) π Ŵ (¬ pqr ) = (0.7/AL L) π Ŵ (¬ pq¬r ) = (0.2/C ∪ 0.4/C) ∩ (0.4/D ∪ 0.4/D) π Ŵ (¬ p¬qr ) = (0.3/A ∪ 0.7/A)
π Ŵ (¬ p¬q¬r ) = (0.3/A ∪ 0.7/A) ∩ (0.2/C ∪ 0.7/C) Its detailed computation can be found in Tables 3 and4. As in the previous example, one can compute the possibilistic logic part (Ŵ S ) • for each subset of the partition of the set of agents, and compute its inconsistency level, which is also indicated below. When this inconsistency level is equal to 0, it is marked with * , and we retrieve exactly the same seven cases as in the second example, as expected (since the example here coincides with the second example when we ignore the certainty levels). These inconsistency levels thus correspond to the levels of inconsistency of the different subgroups of agents.

The global inconsistency level of Ŵ when we ignore the subset of agents, i.e., inc-l((Ŵ) • ) is equal to 0.2 as in the first example. Thus, the 0.3-level cut of Ŵ, namely the set of maformulas {(a i , A i ) | (a i , α i /A i ) ∈ Ŵ and α i ≥ 0.3} is collectively consistent. Besides, keeping in mind that we have cons-s(Ŵ) = (A ∩ C) ∪ (B ∩ D) in the second example, it is clear that here, for instance, inc-l(Ŵ B∩D ) = 0, i.e., the agents in B ∩ D hold consistent possibilistic belief bases individually.

Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ q, 0.8), (¬ p ∨ r, 0.9), (¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (r, 0.8), (¬q, 0.2)} inc(Ŵ A∩B∩C∩D ) = 0.2 Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ q, 0.8), (¬ p ∨ r, 0.9), (¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (r, 0.8)} inc(Ŵ A∩B∩C∩D ) = 0.1 Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ r, 0.9), (¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (¬q, 0.2)} inc(Ŵ A∩B∩C∩D ) = 0.2 Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ r, 0.9), (¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7)} inc(Ŵ A∩B∩C∩D ) = 0.1 Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ q, 0.8), (¬ p ∨ r, 0.9), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (r, 0.8), (¬q, 0.2)} inc(Ŵ A∩B∩C∩D ) = 0.2 Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ q, 0.8), (¬ p ∨ r, 0.9), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (r, 0.8)} * Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ r, 0.9), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7), (¬q, 0.2)} inc(Ŵ A∩B∩C∩D ) = 0.2 (¬q, 0.2)} inc(Ŵ A∩B∩C∩D ) = 0.2 Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.8), (¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (r, 0.

Concluding remarks

The paper has presented a multiple agent logic and outlined its possibilistic extension that enables a rich handling of inconsistency both in terms of subsets of agents and in terms of levels of certainty. In particular, two formulas such as (¬a, A) and (a, B) are contradictory only if A ∩ B = ∅, i.e., if there exists an agent that believes both a and ¬a. There are many issues that have still to be studied. Beyond obvious computational issues, the kind of symmetrical roles played by a and A in (a, A) has to be investigated, in particular for jointly exploiting some possible pieces of knowledge about groups of agents such as A ⊆ B, or even A ∩ B = ∅.

One may think of several future lines of research. In particular, the multiple agent extension of the generalised possibilistic logic [START_REF] Dubois | Stable models in generalized possibilistic logic[END_REF] would allow us to consider the disjunction and the negation of formulas like (a, α/A), and then to syntactically encode statements like 'at most all agents in some subset believe a to at least degree α', or 'there exists at least one agent in subset A who believes a' to at least degree α.

Note

  a), and Bel(a) ∩ Bel(¬a) = ∅. Conversely, N(a) = Bel(a) ∪ I = {k : E k ⊆ [a]}. In other words, N(a) corresponds to the idea of logical implicability, and accounts for the fact that in classical logic everything follows from contradictions, while Bel(a) corresponds to a more intuitive idea of non-trivial belief. The following properties are easy to check: • If a |= b then (a) ⊆ (b), N(a) ⊆ N(b), and Bel(a) ⊆ Bel(b); • (a ∨ b) = (a) ∪ (b); • N(a ∧ b) = N(a) ∩ N(b); • Bel(a ∧ b) = Bel(a) ∩ Bel(b).

Figure 1 .

 1 Figure 1. The different sets of agents according to their attitude w.r.t. a.

  Proof. (sketch) Assume Ŵ is put under clausal form. This can be done without loss of information since the equivalence of {(a ∧ b, A)} with {(a, A), (b, A)} is semantically expressed by N(a ∧ b) = N(a) ∩ N(b) ⊇ A ⇔ N(a) ⊇ A and N(b) ⊇ A. Then the ma-L syntactic inference Ŵ ⊢ (a, A) amounts to a finite number of applications of the A-B-resolution rule to Ŵ ∪ {(¬a, All)}, put in clausal form, leading to (⊥, A).

  (a, α/A), (a, β/B) ⊢⊣ (a, (α/A) ∪ (β/B)), the weight (α/A) ∪ (β/B) is provably the same as α/(A ∩ B) ∪ max(α, β)/(A ∩ B) ∪ β/(A ∩ B).

  8)} inc(Ŵ A∩B∩C∩D ) = 0.1 Ŵ A∩B∩C∩D = {(¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3), (¬q, 0.2)} *Ŵ A∩B∩C∩D = {(¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), ( p, 0.3)} * Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.8), (¬q ∨ r, 0.6), ( p, 0.3), (r, 0.8), (¬q, 0.2)} inc(Ŵ A∩B∩C∩D ) = 0.2 Ŵ A∩B∩C∩D = {(¬ p ∨ ¬r, 0.1), (¬q ∨ r, 0.6), p, 0.3), (r, 0.8)} * Ŵ A∩B∩C∩D = {(¬q ∨ r, 0.6), ( p, 0.3), (¬q, 0.2)} * Ŵ A∩B∩C∩D = {(¬q ∨ r, 0.6), ( p, 0.3)} *Since this base without its certainty levels coincides with the ma-base of the second example, we keep the same inc-s(Ŵ) = (A ∪ C) ∩ (B ∪ D), but it is now partitioned into the subset of agents that are inconsistent at level 0.2, namely (A ∩ D) ∪ (A ∩ C ∩ D) and the subset of agents that are inconsistent at level 0.1 only, namely (A∩ B ∩ D)∪(A∩ B ∩C ∩ D).

  Proposition 1. ma-L is sound and complete w.r.t. this semantics, namely

Ŵ ⊢ (a, A) if and only if Ŵ (a, A).

In this paper, we do not differentiate between functions f from the language L to 2 All and functions 2 → 2 All , interpreting f (a) as f ([a]), that is, f (a) = f (b) whenever a and b are logically equivalent.

Ŵ A∩B∩C∩D = {(¬ p ∨ q, 0.6), (¬ p ∨ r, 0.9), (¬q ∨ r, 0.6), ( p, 0.3), (q, 0.7)} * Table 3. Detailed computation of the ma--distribution in the example, part 1.

Table 4. Detailed computation of the ma--distribution in the example, part 2.

pqr 0.7/All (0.8/D ∪ 1/D) 1/All (0.7/All) ∩ (0.8/D ∪ 1/D) ¬ pq¬r 0.7/All (0.8/D ∪ 1/D) (0.2/C ∪ 1/C) (0.4/All) ∩ (0.2/C ∪ 1/C) ∩ (0.8/D ∪ 1/D) ¬ p¬qr 0.7/All 1/All 1/All (0.7/All) ∩ (0.3/A ∪ 1/A) ¬ p¬q¬r 0.7/All 1/All (0.2/C ∪ 1/C) (0.7/All) ∩ (0.3/A ∪ 1/A) ∩ (0.2/C ∪ 1/C)

Table 2. Detailed computation of the ma-distribution in the example.