Fabio Cuzzolin
email: cuzzolin@cs.ucla.edu

Algebraic structure of the families of compatible frames of discernment

Keywords: Family of compatible frames, minimal refinement, Birkhoff lattices, linear independence, conflict problem

One of the major contributions of Shafer's mathematical theory of evidence is the introduction of uncertainty descriptions on different representation domains of phenomena, called families of compatible frames of discernment. Here we analyze these families of frames from an algebraic point of view, by studying the properties of minimal refinements of collections of domains and introducing the internal operation of maximal coarsening to establish the structure of semimodular lattice. Motivated by the search for a solution of the conflict problem that arises in sensor fusion applications, we will show the connection between classical independence of frames as Boolean subalgebras and independence of frames as elements of a locally finite Birkhoff lattice. This will eventually suggest a potential algebraic solution of the conflict problem.

Introduction

The theory of evidence [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] was introduced in the late Seventies by Glenn Shafer as a way of representing epistemic knowledge, starting from a sequence of seminal works ( [START_REF] Dempster | Upper and lower probability inferences based on a sample from a finite univariate population[END_REF], [START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF]), [START_REF] Dempster | Upper and lower probabilities inferences for families of hypothesis with monotone density ratios[END_REF]) of Arthur Dempster. In this formalism the best representation of one's subjective belief is a belief function (b.f.) rather than a Bayesian mass distribution. Belief functions assign probability values to sets of possibilities rather than single events, naturally encoding evidence in favor of propositions. The theory provides a simple method for combining the evidence carried by a number of different sources (Dempster's rule) with no need of any a-priori distributions.

The other major pillar of the theory (strictly related to the nature of belief functions) is the notion of family of compatible frames, a structured collection of representations of the external world. As a matter of fact, as our knowledge is inherently imprecise it cannot be exhausted by any single-domain representation. This implies, for instance, that representing ignorance in a Bayesian setup is impossible, since any non-informative distribution is not invariant when passing from a domain to another one [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. On the other side, "acceptable" belief functions admit sister functions on any other frame of a family of compatible frames, defining this way the class of support functions.

In sensor fusion applications to engineering or computer vision (Cuzzolin and Frezza, 1999) we often face situations in which several belief functions defined on different frames of a family need to be combined to make decisions or update the knowledge state of a system. Unfortunately, their combination is not always possible: as we prove in this paper, this is true only when their domains are independent in a very precise way (Theorem 1). We refer to this question by using the term conflict problem. A possible naive solution consists then on building a conflict graph whose nodes are the belief functions to combine, and recursively detecting the most coherent set of functions (see Section 3.1). However, this a rather heuristic solution which suffers a high computational cost, and no clear criteria for choosing a collection of b.f. instead of another are provided.

In this paper we try an pose the conflict problem in a rigorous mathematical context, by studying the algebraic structure of the families of compatible frames as objects obeying a small number of axioms [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The intuition comes from a striking resemblance between the notion of independence of frames (see Definition 9)

ω 1 (A 1 ) ∩ • • • ∩ ω n (A n ) = ∅, ∀A i ⊂ Θ i
and the familiar linear independence relation for a collection of subspaces {V i } of a vector space

V v 1 + • • • + v n = 0, ∀v i ∈ V i .
We may wonder whether this is a simple analogy, or rather the symptom of a deeper similarity of these structures at the algebraic level. Given a collection of arbitrary elements of a vector space, a well known procedure called Gram-Schmidt algorithm is able to generate a new collection of independent vectors, spanning the same subspace. It would be highly desirable to design an analogous procedure which, given a set of belief functions defined on arbitrary elements of a family of frames, would yield another collection of (combinable) belief functions defined on independent frames, generating an equivalent (in some formal sense) Dempster's combination.

In this work we prepare the mathematical ground for this ambitious goal, by studying the monoidal and lattice structures of families of compatible frames of discernment. As a matter of fact, it turns out that both vector subspaces and families of frames share the structure of AMAIframe-published.tex;14/02/2006;19:27;p.2 Birkhoff lattice [START_REF] Stern | Semimodular lattices[END_REF]. Birkhoff lattices admit the introduction of a linear dependence relation on their atoms. We can then reasonably conjecture (as we will see in Section 7) the equivalence between the classical notion of independence of frames as Boolean subalgebras, and their independence as elements of a locally finite Birkhoff lattice. A formal proof of this equivalence would eventually prefigure a solution to the conflict problem based on a "pseudo Gram-Schmidt" algorithm, transforming belief functions on arbitrary frames into "equivalent" b.f. on independent frames.

Paper outline

After briefly recalling the basic notions of the theory of evidence (Section 2), we give a characterization of the relationship between the conflict problem and the notion of independence of frames (Section 3). As Dempster's combination is guaranteed if and only if the underlying frames are independent (Theorem 1), it is crucial to study independence in more detail to provide practical solutions to real-world applications (Section 3.1), in which different measurements are fused to make decisions or compute estimates.

This can be done in a rigorous fashion by posing the problem in an algebraic context (Section 4), after finding an alternative, constructive set of axioms for the families of compatible frames. If we assume we have a finite knowledge of the problem (a realistic assumption in practical applications) we can build the subfamily of frames of discernment generated by any given frame.

In Section 5 we first focus on these finite subfamilies of frames, showing that the natural operator of minimal refinement ⊗ induces on them a structure of commutative monoid with annihilator (Theorem 4). The collection of refinings of a finite subfamily of frames is also a monoid, as one can build an isomorphism between frames and refinings (Equation ( 8)). More important, both frames (F, ⊗) and refinings (R, ⊗) of a general family of compatible frames of discernment also possess the algebraic structure of a commutative monoid (Section 5.4), with finite subfamilies as submonoids. The situation is summarized by Equation ( 13).

As the internal operation of a monoid induces an order relation, we are tempted to think at the problem from a lattice-theoretic point of view. As a matter of fact, in Section 6 we prove that the collection of sets of a family of compatible frames is a Birkhoff lattice (with minimal refinement as least upper bound or sup, and the dual operation of maximal coarsening ⊕ as greatest lower bound or inf ) of locally finite length and with a smallest element. Formally, (F, ⊗, ⊕) is a Birkhoff lattice bounded below.

This is where the interplay between the conflict problem and the algebraic structure of the families of frames takes place, as Birkhoff lattices come with a notion of independence. It is then quite natural to conjecture (Section 7) that the independence of frames as Boolean subalgebras (Definition 9), originally incorporated into the theory of evidence, could possibly be equivalent to the independence of frames as elements of a Birkhoff lattice (Theorem 14). This would open the way to an algebraic solution of the conflict problem, where a pseudo Gram-Schmidt orthogonalization procedure would be used to transform any given collection of b.f. into a new, combinable set by projection onto independent frames.

Previous work

Not much work has been done on the properties of the families of compatible frames. In [START_REF] Shafer | Propagating belief functions in qualitative Markov trees[END_REF], though, an analysis of the collections of partitions of a given frame in the context of the hierarchical representation of belief can be found. A wider exposition of the algebraic properties of the families of frames is instead presented in [START_REF] Kohlas | A Mathematical Theory of Hints -An Approach to the Dempster-Shafer Theory of Evidence[END_REF], where Chapter 7 is devoted to their lattice-theoretical interpretation and the meaning of the concept of independence, while Chapter 8 develops the consequences of the application of constraints to the structure of the family of compatible frames and deepens the properties of Markov trees as a useful characterization.

Some work has been done on the conflict problem, too [START_REF] Deutsch-Mcleish | A study of probabilities and belief functions under conflicting evidence: comparisons and new method[END_REF]). Murphy [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF], on his side, studied a related problem (the failure to balance multiple evidence), illustrated the proposed solutions and described their limitations.

The theory of evidence

In the theory of evidence [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], subjective degrees of belief are mathematically represented as belief functions (b.f.), which generalize finite probability distributions in the finite case. Belief functions encoding different pieces of evidence can be combined by means of Dempster's rule [START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF]. The concept of family of compatible frames is introduced to formalize the intuitive idea of different levels of description of a same phenomenon.

Belief functions

Axiomatic definition

The reader will of course be familiar with the classical definition of probability measure, due to Kolmogorov.

Definition 1. A probability measure over a σ-field F ⊂ 2 Θ associated with a sample space Θ is a function p : F → [0, 1] such that 1. p(∅) = 0; 2. p(Θ) = 1; 3. if A ∩ B = ∅, A, B ∈ F then p(A ∪ B) = p(A) + p(B) (additivity).
Now, let us restrict ourselves to finite sets, and relax the third constraint allowing the function to have the value obtained by additivity as a lower bound. We then get a new mathematical object: a belief function.

Definition 2. Suppose Θ is a finite set, and let 2 Θ denote the set of all the subsets of Θ.

A belief function on Θ is a function s : 2 Θ → [0, 1] such that 1. s(∅) = 0; 2. s(Θ) = 1;

for every positive integer n and every collection

A 1 , ..., A n ∈ 2 Θ s(A 1 ∪...∪A n ) ≥ i s(A i )- i<j s(A i ∩A j )+...+(-1) n+1 s(A 1 ∩...∩A n ).
The third axiom is called superadditivity, and obviously reduces to standard additivity when we replace the inequality with an equality. Belief functions can then be seen as generalizations of familiar probability distributions on finite domains. Θ can be interpreted as the set of possible answers to a decision problem, exactly one of which is the correct one. For each subset (proposition) A ⊂ Θ the quantity s(A) measures the degree of belief that the true answer lies in A.

Basic probability assignment

Belief functions can be given an alternative but equivalent description in terms of total belief committed to a set of possibilities A. Let us call the finite set of possible outcomes for a decision problem frame1 of discernment.

Definition 3. A basic probability assignment (b.p.a.) over a frame Θ is a function m : 2 Θ → [0, 1] such that m(∅) = 0, A⊂Θ m(A) = 1, m(A) ≥ 0 ∀A ⊂ Θ.
Subsets of Θ associated with non-zero values of m are called focal elements and their union C core. Now suppose a b.p.a. is introduced on an arbitrary frame.

Definition 4. The belief function s associated with a basic probability assignment m is defined as (see figure 1-left)

s(A) = B⊂A m(B).
Conversely, a basic probability assignment m associated with a given belief function s can be uniquely recovered by means of the Moebius inversion formula2

m(A) = B⊂A (-1) |A-B| s(B)
(1) so that there is a 1-1 correspondence m ↔ s between these two set functions. It can be proved that Definition 4 and 2 are equivalent.

Dempster's rule of combination

Belief functions representing distinct bodies of evidence can be combined by means of the so called Dempster's rule of combination [START_REF] Dempster | Upper and lower probability inferences based on a sample from a finite univariate population[END_REF][START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF]

m(A) = i,j:A i ∩B j =A m 1 (A i ) • m 2 (B j ) 1 - i,j:A i ∩B j =∅ m 1 (A i ) • m 2 (B j ) , A = ∅. ( 2
)
The normalization constant in Equation (2) measures the weight of conflict Con(s 1 , s 2 ) between two belief functions, and represents the

A B B 1 2 Q ) ( ) ( 2 2 3 1 B m A m × 2 3 B A Ç 1 A 2 A 3 A 4 A 1 B 2 B 3 B Figure 1
. Left: Basic probability assignment and belief value. In the picture m(B) = 0, B ⊂ A only for B 1 and B 2 so that s(A) = m(B 1 ) + m(B 2 ). Right: Dempster's rule of combination: on the y,x axes are depicted the focal elements Ai and B j of s 1 , s 2 respectively. The width of columns and rows is proportional to the b.p.a. associated with each focal element (in a size 1 square). Each intersection is given the product of the corresponding masses (equal to the area of the related square). Contributions of coincident intersections are then summed. This value is finally normalized by taking into account all the empty intersections (denominator of Equation ( 2)).

amount of probability they attribute to contradictory (i.e. disjoint) subsets. If all the intersections between focal elements of s 1 and s 2 are empty (C 1 ∩ C 2 = ∅) the two belief functions are said non-combinable.

The above definition can be easily extended to the combination of an arbitrary number of belief functions.

Example

Consider as an example a gray-scale image, and imagine you need to measure the column index of the center of mass of the intensity function of the image. A naive quantization of the column range in, say, 5 intervals (Figure 2-left) yields a frame of discernment {c 1 , ..., c 5 } (Figure 2-middle). On this frame we can define a belief function s 1 with two focal elements A 1 = {c 2 } and A 2 = {c 2 , c 4 } through the basic probability assignment m 1 (A 1 ) = 0.7, m 1 (A 2 ) = 0.3. For instance, the belief values of the sets {c 4 }, {c 2 , c 5 }, {c 2 , c 3 , c 4 } are then s 2.3. Random sets and belief functions

1 ({c 4 }) = m 1 ({c 4 }) = 0, s 1 ({c 2 , c 5 }) = m 1 ({c 2 }) + m 1 ({c 5 }) + m 1 ({c 2 , c 5 }) = 0.7 + 0 + 0 = 0.7, s 1 ({c 2 , c 3 , c 4 }) = m 1 ({c 2 }) + m 1 ({c 2 , c 4 }) = 0.7 + 0.3 = 1 respectively. Now introduce another b.f. s 2 with b.p.a. m 2 (B 1 ) = m 2 ({c 2 , c 3 }) = 0.6 and m 2 (B 2 ) = m 2 ({c 4 , c 5 }) = 0.4. Their Dempster's combination yields a new b.f. with focal elements (Figure 2-right) X 1 = A 1 ∩ B 1 = A 2 ∩ B 1 = {c 2 } and X 2 = A 2 ∩ B 2 = {c 4 } and b.p.a. m(X 1 ) = 0.7•0.6+0.3•0.6 1-0.7•0.4 = 5/6, m(X 2 ) = 0.3•0.4 1-0.7•0.4 = 1/6. c 1 c 2 c 3 c 4 c 5 c 1 c 2 c 3 c 4 c 5 A 1 A 2 B 1 B 2 X 1 X 2 Figure 2.

Multi-valued mappings

In fact, in the original approach due to Dempster belief functions are inherently associated with multi-valued maps between frames. Let us suppose we have probabilities (coming from arbitrary sources, for instance subjective judgement or objective measurements) for a question Q 1 an we want to derive a degree of belief for a related question Q 2 . For example, Q 1 could be the judgement on the reliability of a witness, and Q 2 the decision about the truth of the reported fact. Let us call X and Θ the sets (frames) of possible answers of Q 1 and Q 2 respectively. Given a probability P (x) on X we wish to derive a degree of belief s(A) that A ⊂ Θ contains the correct answer to Q 2 . If we call Γ(x) the subset of responses to Q 2 compatible with x, each element x ∈ X tells us that the answer to Q 2 is somewhere in A, whenever Γ(x) ⊂ A. The degree of belief s(A) is then the total probability of all the answers x that satisfy the above condition, namely

s(A) = P {x|Γ(x) ⊂ A}.
The map Γ is called a multi-valued mapping from X to Θ. This mapping, together with the probability measure on X, induces a belief function on Θ: (P, Γ) → s.

Belief functions as random sets

Having a multi-valued mapping Γ, a straightforward step is to consider the probability P (x) attached to the subset Γ(x) ⊂ Θ: what we obtain is a random set in Θ, i.e. a probability measure on a collection of subsets (see [START_REF] Goutsias | Random sets: theory and applications[END_REF][START_REF] Matheron | Random Sets and Integral Geometry[END_REF] for the most complete introductions to the matter). The degree of belief s(A) then becomes the total probability that the random set is contained in A.

This approach has been emphasized in particular by [START_REF] Goodman | Uncertainty Models for Knowledge-based systems[END_REF], [START_REF] Nguyen | Belief functions and random sets'. In: Applications and Theory of Random Sets[END_REF][START_REF] Nguyen | On Random Sets and Belief Functions[END_REF]) and resumed in [START_REF] Shafer | Propagating belief functions in qualitative Markov trees[END_REF]. Consider a multi-valued mapping Γ : X → 2 Θ . We can define the lower inverse of Γ as

Γ * : 2 Θ → 2 X A → Γ * (A) . = {x ∈ X : Γ(x) ⊂ A, Γ(x) = ∅}.
(3) and in the dual way its upper inverse as

Γ * : 2 Θ → 2 X A → Γ * (A) . = {x ∈ X : Γ(x) ∩ A = ∅}. ( 4
)
Given two σ-fields A, B on X, Θ respectively, Γ is said strongly measurable iff ∀B ∈ B, Γ * (B) ∈ A. The lower probability measure on B is defined as P * (B) . = P (Γ * (B)) for all B ∈ B. Nguyen proved that, if Γ is strongly measurable, the probability distribution P of the random set [START_REF] Nguyen | On Random Sets and Belief Functions[END_REF] coincides with the lower probability measure

P [I(B)] = P * (B) ∀B ∈ B
and (in the finite case) the probability distribution of the random set Γ is precisely the basic probability assignment associated with the lower probability (belief function) P * .

An analysis of the relations between the transferable belief model and the theory of random sets can be found in [START_REF] Smets | The Transferable Belief Model and Random Sets[END_REF].

Refinings

As belief functions are inherently associated with maps between different (but related) domains, the theory of evidence quite naturally contemplates the impact of evidence on different finite descriptions of the same problem. In particular, a new amount of evidence can allow us to make decisions (by means of Dempster's rule) over more detailed domains. This argument is embodied into the notion of refining. Definition 6. Given two frames Θ and Ω, a map ω : 2 Θ → 2 Ω is a refining if it satisfies the following properties

1. ω({θ}) = ∅ ∀θ ∈ Θ, 2. ω({θ}) ∩ ω({θ }) = ∅ when θ = θ , 3. ∪ θ∈Θ ω({θ}) = Ω,
while its value for arbitrary subsets A of Θ is given by

ω(A) . = θ∈A ω({θ}).
Ω is called a refinement of Θ, while Θ is said a coarsening of Ω. Both frames represent sets of possible outcomes for the same decision problem, but the finer one is a more detailed description, obtained by splitting each possible answer θ ∈ Θ into a set ω({θ}).

Consider for example a partition

A 1 , ..., A n of Ω. If we define Θ = {A 1 , ..., A n } the map ω : 2 Ω → 2 Θ with ω(A i ) = A i is a refining.

Vacuous extension

Any belief function s defined on a frame Θ can be "projected" onto any refinement Ω of Θ by vacuous extension.

Definition 7. Suppose Ω is a refinement of Θ, with refining ω : 2 Θ → 2 Ω . The vacuous extension on Ω of a belief function s : 2 Θ → [0, 1] on Θ is the belief function s : 2 Ω → [0, 1] on Θ defined as s (A) = max B⊂Θ, ω(B)⊂A s(B) ∀A ⊂ Ω.
s is a belief function on the frame Ω [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], whose focal elements are exactly the images of the focal elements of s,

{B 1 , ..., B k } → {A 1 = ω(B 1 ), ..., A k = ω(B k )} with m s (A i ) = m s (B i ).
Recall the example of Section 2.

m s 2 (A 1 ) = 0.7, m s 2 (A 2 ) = 0.3.

Families of compatible frames

Now that the basis tools (refining maps between frames) have been introduced, the intuitive idea of different descriptions of a same phenomenon can be formally expressed by the concept of family of compatible frames (see [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], pages 121-125).

Definition 8. A non-empty collection of finite non-empty sets F is a family of compatible frames of discernment with refinings R, where R is a non-empty collection of refinings between couples of frames in F, if F and R meet the following requirements:

Axiom 1. composition of refinings: if ω 1 : 2 Θ 1 → 2 Θ 2 and ω 2 : 2 Θ 2 → 2 Θ 3 are in R, then ω 1 • ω 2 ∈ R. Axiom 2. identity of coarsenings: if ω 1 : 2 Θ 1 → 2 Ω and ω 2 : 2 Θ 2 → 2 Ω are in R and ∀ θ 1 ∈ Θ 1 ∃ θ 2 ∈ Θ 2 such that ω 1 ({θ 1 }) = ω 2 ({θ 2 }), then Θ 1 = Θ 2 and ω 1 = ω 2 . Axiom 3. identity of refinings: if ω 1 : 2 Θ → 2 Ω and ω 2 : 2 Θ → 2 Ω are in R, then ω 1 = ω 2 .
Axiom 4. existence of coarsenings: if Ω ∈ F and A 1 , ..., A n is a disjoint partition of Ω, then there is a coarsening Ω of Ω in F corresponding to this partition, i.e. ∀A i there exists an element of Ω whose image under the appropriate refining is A i .

Axiom 5. existence of refinings: if θ ∈ Θ ∈ F and n ∈ N then there exists a refining ω : 2 Θ → 2 Ω in R and Ω ∈ F such that ω({θ}) has n elements.

Axiom 6. existence of common refinements: every pair of elements in F has a common refinement in F.

By iterative application of Axiom 6 it follows that any finite collection of compatible frames has many common refinements. One of these is particularly simple.

Proposition 1. If Θ 1 , ..., Θ n are elements of a family of compatible frames F then there exists a unique element Θ ∈ F such that 1. ∀i ∃ ω i : 2 Θ i → 2 Θ refining; 2. ∀θ ∈ Θ ∃ θ i ∈ Θ i f or i = 1, ..., n such that {θ} = ω 1 ({θ 1 }) ∩ ... ∩ ω n ({θ n }).
(5)

This unique frame is called the minimal refinement Θ 1 ⊗ • • • ⊗ Θ n of the collection Θ 1 , ..., Θ n and is the simplest space in which you can compare propositions belonging to different compatible domains.

Example

In Section 2.2.1 we introduced a frame Θ 1 by partitioning the column range into 5 intervals. The set of columns can be partitioned also into 10 intervals, yielding a new frame Θ 2 (section 2.4.1). More, the row range can also be divided in, say, 6 intervals (Θ 3 ). All those frames are clearly related to the location of the center of mass: as Figure 3 suggests, they all belong to a family of compatible frames, with the

w 2 w 3 Q Q 1 Q 2 Q 3 Figure 3.

Independence and evidence conflict

Belief functions carrying distinct pieces of evidence over different frames of a family can be combined by using Dempster's rule. We just need to project each of them onto their common refinement by vacuous extension, and then combine them by means of Dempster's rule. The information brought by each belief function can then be used to evaluate propositions in this finer, common environment.

Motivations: sensor fusion

A natural application of these attractive features of the theory of evidence can be found in sensor fusion, where measurements coming from different sources have to be combined to make decisions, in order to increase the robustness of the process.

For instance, in some recent works [START_REF] Cuzzolin | An Evidential Reasoning Framework for Object Tracking[END_REF][START_REF] Cuzzolin | Integrating feature spaces for object tracking[END_REF] we proposed an evidential framework for the solution of the object tracking problem. In this context, given a sequence of images of a moving articulated object you want to reconstruct the position and configuration of the body at each time instant. We represented a number of different feature measurements extracted from the AMAIframe-published.tex; 14/02/2006; 19:27; p.12 images as belief functions and combined them to compute an estimate of the pose q(t) ∈ Q, where Q is a sufficiently "good" finite approximation of the parameter space Q of the object.

As an example, we can think of a human hand as an articulated object with 27 degrees of freedom (its position, orientation and the values of the angles between pairs of links of the fingers). As features we can choose indifferently the positions of the fingertips in the image plane, the center of mass of the image itself, etc. In [START_REF] Cuzzolin | An Evidential Reasoning Framework for Object Tracking[END_REF] we showed some experiments involving a simple planar robot (see Figure 4). These feature spaces Θ i and the approximate parameter space Q form a finite subset of a family of compatible frames of discernment, where Q is a common refinement of the collection of feature spaces (see Figure 5).

Independence and conflicting evidence

Unfortunately, the combination of pieces of evidence originally defined on different domains is guaranteed only for trivially interacting frames. Definition 9. Let Θ 1 , ..., Θ n be compatible frames, and ω i :

2 Θ i → 2 Θ 1 ⊗•••⊗Θ n
the corresponding refinings to their minimal refinement. They are said to be independent3 if

ω 1 (A 1 ) ∩ • • • ∩ ω n (A n ) = ∅ (6) whenever ∅ = A i ⊂ Θ i for i = 1, ..., n. Q Q Q Q Q 1 Q 2 n w w w 1 2 n Figure 5
. Families of feature spaces involved in the object tracking problem. The actual continuous parameter space Q of the articulated object is unknown, while its finite approximation Q is the common refinement where the evidence extracted from the image is combined.

Independence of frames and combinability of belief functions are as a matter of fact strictly connected.

Theorem 1. Let Θ 1 , ..., Θ n a set of compatible frames. The following conditions are equivalent:

1. all the possible collections of belief functions s 1 , ..., s n defined respectively over Θ 1 , ..., Θ n are combinable over their minimal refinement Θ 1 ⊗ ... ⊗ Θ n ;

2. Θ 1 , ..., Θ n are independent;

3. there is an isomorphism

Θ 1 ⊗ • • • ⊗ Θ n ↔ Θ 1 × • • • × Θ n ; 4. |Θ 1 ⊗ • • • ⊗ Θ n | = n i=1 |Θ i |.
Proof. 1 ⇒ 2. We know that if s 1 , ..., s n are combinable then s i , s j must be combinable ∀i, j = 1, ..., n. Hence ω i (C i ) ∩ ω j (C j ) = ∅ ∀i, j where C i is the core of s i , and

ω i : 2 Θ i → 2 Θ 1 ⊗•••⊗Θ n is the refining connecting Θ i with the common refinement Θ 1 ⊗ • • • ⊗ Θ n .
As s i , s j are arbitrary, their cores C i , C j can be any pair of subsets of Θ i , Θ j respectively, so that the condition can be rewritten as

ω i (A i ) ∩ ω j (A j ) = ∅ ∀A i ⊂ Θ i , A j ⊂ Θ j . 2 ⇒ 1. Since Θ 1 , ..., Θ n are independent, ω 1 (A 1 ) ∩ • • • ∩ ω n (A n ) = ∅ for all non-empty A i ⊂ Θ i , ∀i = 1, .., n. But then if we pick A i = C i (the core of s i ) ∀i = 1, ..., n we get ω 1 (C 1 ) ∩ • • • ∩ ω n (C n ) = ∅, i.e. the vacuous extensions of s 1 , ..., s n onto Θ 1 ⊗ • • • ⊗ Θ n are combinable (see Section 2.2). 2 ⇒ 3. We note that i ω i ({θ k i }) = i ω i ({θ l i }) ⇔ θ k i = θ l i ∀i = 1, ..., n.
In fact, if ∃j s.t.

θ k i = θ l i then ω i ({θ k i }) = ω i ({θ l i })
for the properties of refinings: since they are disjoint, it must be i ω i ({θ

k i }) = i ω i ({θ l i }). Hence their number coincides with the number |Θ 1 | × • • • × |Θ n | of the n-tuples of singletons of Θ 1 , ..., Θ n , and since Θ 1 ⊗• • •⊗Θ n is a minimal refinement each of these subsets must correspond to a singleton. 3 ⇒ 2. For Proposition 1, each θ ∈ Θ 1 ⊗• • •⊗Θ n corresponds to a subset of the form i ω i ({θ k i }). Since the singletons are |Θ 1 | × • • • × |Θ n |
the above subsets come in the same number, but then they all are nonempty, so that Θ 1 , ..., Θ n are independent.

3 ⇒ 4. Obvious. 4 ⇒ 3. Θ 1 ⊗ • • • ⊗ Θ n = { i ω i ({θ i }) : θ i ∈ Θ i }, so that if the intersec- tions' number is |Θ 1 | × • • • × |Θ n |
they all must be non-empty and each of them can be denoted by (θ 1 , ..., θ n ).

For any collection of non-independent frames there exists at least a collection of belief functions defined on them that are not combinable. Any given set of belief functions is then characterized by a weight of conflict Con. When Con = ∞ there is no way of combining all of them by means of Dempster's rule.

The conflict problem

Going back to our sensor fusion application, since the belief functions built from the extracted features are not always compatible, we need a method for detecting the subset we are going to apply the rule of combination to. A basic property of the conflict weight is

Con(s 1 , ..., s n+1 ) = Con(s 1 , ..., s n ) + Con(s 1 ⊕ ... ⊕ s n , s n+1 ),
so that if Con(s i , s j ) = +∞ then Con(s i , s j , s k ) = +∞ ∀s k . This suggests a bottom-up technique. First the level of conflict is computed for each pair of measurement functions (s i , s j ), i, j = 1, ..., n. Then a suitable threshold is chosen and a conflict graph is built, where every node represents a belief function while an edge indicates a conflict level below the threshold. Finally the subsets of combinable b.f. of size d + 1 are recursively computed from those of size d, eventually detecting the most coherent set of features.

This approach obviously suffers a high computational cost when large groups of functions turn out to be compatible. Also, there is no clear indication about how to select a particular set of combinable belief functions.

Theorem 1 instead establishes a direct connection between conflicting evidence and independence of frames. As we have discussed in the introduction, this strongly suggests that a satisfactory, formal solution could be found in an algebraic context. In this perspective, it is necessary to understand the nature of the analogy between independence of vector spaces and independence of frames. This in turns involves a study of the algebraic properties of the families of compatible frames.

Axiom analysis

Constructive approach

To understand the algebraic properties of families of frames we necessarily need to analyze the axioms of Definition 8. As we have seen in Section 3.1, in real-world applications our knowledge of a given problem is finite. We first then consider an arbitrary finite set S, and adopting a constructive approach we check the result of the application of the axioms of Definition 8.

Axiom A4 needs to be applied first, yielding the collection of all the possible partitions of S and the refinings between each of them and the basis set. By applying A4 again to the new sets all the refinings among them are achieved, while no other set is added to the collection. Axioms 2 and 3 guarantee the uniqueness of the obtained maps and sets. 4 It is clear even at a first glance that A6 claims an existing condition but is not constructive, i.e. it does not allow to generate new sets from a given initial collection. Let us then introduce a new axiom Axiom 7. Existence of the minimal refinement: for every pair of elements in F there exists their minimal refinement in F, i.e. a set satisfying the conditions of Proposition 1. and consider another set of axioms by replacing A6 with A7. Let us call A 1..6 and A 1..5,7 these two formulations.

Theorem 2. A 1..6 and A 1..5,7 are equivalent formulations of the notion of family of compatible frames.

Proof. It is necessary and sufficient to prove that (i) A7 can be obtained by using the set of axioms A1, ..., A6 and (ii) that A6 can be obtained from A1, ..., A5, A7. (i). See [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] or Proposition 1 . (ii). Each refinement of a given pair of sets Θ 1 , Θ 2 can be obtained by arbitrarily refining Θ 1 ⊗ Θ 2 by means of Axiom A5. Anyway, the minimal refinement is obviously a refinement so that A7 ⇒ A6.

From now on we will then replace axiom A6 with axiom A7.

Finite knowledge

Again, if we assume finite and static our knowledge of the problem, Axiom A5 cannot be used. According to the established notation let us call A 1..4,7 the set of axioms corresponding to the finite knowledge case.

Definition 10. The subfamily generated by a collection of sets Θ 1 , ..., Θ n by means of a set of axioms A is the smallest collection of frames Θ 1 , ..., Θ n A containing Θ 1 , ..., Θ n and closed under the application of the axioms in A.

Given their importance in concrete applications it is natural to focus first on the properties of finite sub-families of compatible frames. We will then extend the analysis to general abstract families to get a comprehensive picture of the matter.

Lemma 1. The minimal refinement of two coarsenings Θ 1 , Θ 2 of a frame S is still a coarsening of S.

Proof. From the hypothesis S is a common refinement of Θ 1 and Θ 2 , and since the minimal refinement is coarsening of every other refinement the thesis follows.

Immediately we conclude that Theorem 3. The subfamily of compatible frames generated by the application of the restricted set of rules A 1..4,7 to a basis set S is the collection of all the disjoint partitions of S along with the appropriate refinings.

Note that this is not necessarily true when using Axiom A6.

Monoidal structure

The "constructive" version of Definition 8 allows us to introduce in a family of compatible frames the internal operation

⊗ : F × • • • × F → F {Θ 1 , ..., Θ n } → ⊗ i Θ i (7)
associating each collection of frames with their minimal refinement. ( 7) is well defined, for Axiom A7 ensures the existence of ⊗ i Θ i .

Finite families as commutative monoids

Let us then consider a finite subfamily of compatible frames F . = S A 1..4,7 for some S ∈ F, and discuss the properties of the minimal refinement.

Theorem 4. The internal operation ⊗ of minimal refinement satisfies the following properties:

1. associativity: Θ 1 ⊗(Θ 2 ⊗Θ 3 ) = (Θ 1 ⊗Θ 2 )⊗Θ 3 , ∀ Θ 1 , Θ 2 , Θ 3 ∈ F ; 2. commutativity: Θ 1 ⊗ Θ 2 = Θ 2 ⊗ Θ 1 , ∀Θ 1 , Θ 2 ∈ F ; 3. existence of unit: ∃1 ∈ F s.t. Θ ⊗ 1 = Θ, ∀Θ ∈ F ; 4. annihilator: Θ ⊗ S = S, ∀Θ ∈ F
where 1 is the unique frame of F containing a single element.

Proof. Associativity and commutativity. If we look at Equation ( 5), associativity and commutativity follow from the analogous property of the set-theoretic intersection. Unit. Let us prove that there exists a unique frame 1 in F with cardinality 1. Given Θ ∈ F , due to Axiom A4 (existence of coarsenings) there exists a coarsening 1 Θ of Θ and a refining ω 1 Θ Θ : 2 1 Θ -→ 2 Θ . Then, by Axiom A1 there exists another refining 1 ω ∈ R such that

1 ω : 2 1 Θ -→ 2 S .
Now, if we consider a pair of elements of F , say Θ 1 , Θ 2 , the above procedure yields two pairs set-refining (1

Θ i , 1 ω i ) with 1 ω i : 2 1 Θ i → 2 S . But if we call 1 θ i the unique element of 1 Θ i 1 ω i ({1 θ i }) = S ∀i = 1, 2
so that for Axiom A2 (identity of coarsenings) uniqueness follows:

1 ω 1 = 1 ω 2 , 1 Θ 1 = 1 Θ 2 .
Annihilator. If Θ ∈ F then obviously Θ is a coarsening of S, therefore their minimal refinement coincides with S itself.

In other words, a finite family of frames of discernment (F , ⊗) is a finite commutative monoid with annihilator with respect to the internal operation of minimal refinement. However, a family of frames is not only a collection of sets, but also the collection of refinings between these sets. Does Theorem 4 have any consequence for these refinings?

Isomorphism frames-refinings

Actually, a family of frames can be dually viewed as a set of refining maps with attached their domains and codomains (perhaps the most synthetic approach as it accounts for sets automatically, allowing to reduce the number of axioms). In the finite case we can immediately establish the following correspondence

Θ ←→ ω Θ S : 2 Θ → 2 S (8)
between an element Θ of a finite subfamily of compatible frames and the unique refining from Θ to S (see Axiom A3).

Definition 11. Given ω 1 : 2 Θ 1 → 2 S and ω 2 : 2 Θ 2 → 2 S their composition induced by the operation of minimal refinement is the unique refining from Θ 1 ⊗ Θ 2 to S (as for Axiom A3 there is only one refining connecting two frames of the family) Proof. Associativity and commutativity come from the analogous property of the minimal refinement operator. The unit element is 1 ω : 2 1 S → 2 S , as

ω 1 ⊗ ω 2 : 2 Θ 1 ⊗Θ 2 → 2 S . ( 9
Dom(1 ω ⊗ ω) = 1 S ⊗ Dom(ω) = Dom(ω) ⇒ 1 ω ⊗ ω = ω
for Axiom A2. On the other side if we consider 0 ω : 2 S → 2 S the unique refining from S onto itself (which exists by Axiom A4 with n = 1) we have

Dom(0 ω ⊗ ω) = S ⊗ Dom(ω) = S so that 0 ω is

It easily follows that

Proposition 2. Given a finite family of compatible frames, the bijection ( 8) is an isomorphism between commutative monoids.

Some remarks

It may be interesting to note that the existence of both unit element and annihilator in a finite family of frames are consequences of the following proposition:

Proposition 3. (ω Θ S • ω Ω Θ ) ⊗ ω Θ S = ω Θ S ∀ Ω, Θ. Proof. Cod(ω Θ S • ω Ω Θ ) = S so the operation ⊗ can be applied. By noting that Dom(ω Θ S • ω Ω Θ ) = Ω is a coarsening of Dom(ω Θ S ) = Θ we get Dom((ω Θ S • ω Ω Θ ) ⊗ ω Θ S ) = Dom(ω Θ S • ω Ω Θ ) ⊗ Dom(ω Θ S ) = Dom(ω Θ S ) = Θ
and from Axiom A3 the thesis follows.

As a matter of fact, when

Ω = 1 S then ω Θ S •ω Ω Θ = ω Θ S •ω 1 S Θ = 1 ω and we get 1 ω ⊗ ω Θ S = ω Θ S .
On the other side, when Θ = S then ω Θ S = ω S S = 0 ω and we have the annihilation property ω Ω S ⊗ 0 ω = 0 ω .

Generators

Even if not strictly necessary in the context of the conflict problem, something more can be said about the dual finite monoids generated by ⊗ in terms of the notion of generator. Given a monoid M, the submonoid M generated by a subset M of M is defined as the intersection of all the submonoids of M containing M .

Definition 12. The set of generators of a monoid M is a finite collection M of elements of M such that M = M. Theorem 6. The set of generators of the finite family of compatible frames S A 1..4,7 seen as finite commutative monoid with respect to the internal operation ⊗ (minimal refinement) is the collections of all the binary frames.

The set of generators of the associated monoid of refinings S ω (.) S A 1..4,7 is the collection of refinings from all the binary partitions of S to S itself: AMAIframe-published.tex;14/02/2006;19:27;p.20 Proof. We need to prove that all the possible partitions of S can be obtained as minimal refinement of a number of binary partitions. Let us consider a generic partition Π = {S 1 , ..., S n } and define

S ω (.) S A 1..4,7 = {ω ij : 2 Θ ij → 2 S | |Θ ij | = 2, ω ij ∈ R} .
Π 1 = {S 1 , S 2 ∪ • • • ∪ S n } . = {A 1 , B 1 } Π 2 = {S 1 ∪ S 2 , S 3 ∪ • • • ∪ S n } . = {A 2 , B 2 } • • • Π n-1 = {S 1 ∪ • • • ∪ S n-1 , S n } . = {A n-1 , B n-1 }.
It is not difficult to see that every arbitrary intersection of elements of Π 1 , ..., Π n-1 is an element of the n-ary partition Π, in fact

A i ∩ B k = ∅, k ≥ i, A i ∩ A k = A i , k ≥ i, B i ∩ B k = B k , k ≥ i so that i A i = A 1 = S 1 , i B i = B n-1 = S n .
If both As and Bs are present the resulting intersection is ∅ whenever there exist a pair B l , A m with l ≥ m. Hence the only non-empty mixed intersections in the class {X 1 ∩ • • • ∩ X n } must necessarily be of the following kind

B 1 ∩ ... ∩ B k ∩ A k+1 ∩ ... ∩ A n-1
and we have

B 1 ∩ • • • ∩ B k ∩ A k+1 ∩ • • • ∩ A n-1 = = (S k+1 ∪ • • • ∪ S n ) ∩ (S 1 ∪ • • • ∪ S k+1 ) = S k+1
where k+1 goes from 2 to n-1. That satisfies the fundamental condition for Π to be the minimal refinement of Π 1 , ..., Π n-1 (note that the choice of the binary frames is not unique). The second part of the proof, concerning the refining maps, comes directly from the existence of the isomorphism (8).

The monoids associated with finite families are then really simple, their structure being completely determined by the binary frames and related refinings. This is not true for complete families of compatible frames. Even if the general case is not a copycat of the finite one, though, the analysis of finite subfamilies provides us with the necessary intuition to cope with the general case.

General families as commutative monoids

The algebraic structure of monoid is then a direct implication of the notion of minimal refinement. We may wonder whether a general family of compatible frames possess the same structure. The answer is positive.

Theorem 7. F is an infinite commutative monoid with no annihilators.

Proof. The proof of Theorem 4 still holds for the first two points. Existence of unit. Suppose there exist two frames 1 = {1} and 1 = {1 } with size 1. For Axiom A6 they have a common refinement Θ, with ω 1 : 2 1 → 2 Θ and ω 1 : 2 1 → 2 Θ refinings. But then ω 1 ({1}) = Θ = ω 1 ({1 }), and by Axiom A2 1 = 1 . Now, for every frame Ω ∈ F Axiom A4 ensures that there exists a partition of Ω with only one element, 1 Ω . For the above argument, 1 Ω = 1. In conclusion there is only one monic frame in F, and since it is a refinement of every other frame, it is the unit element with respect to ⊗. Annihilators. Suppose a frame 0 Θ exists such that 0 Θ ⊗ Θ = 0 Θ for each Θ. We then would have, given a refinement Ω of 0 Θ (built by means of Axiom A5), 0 Θ ⊗ Ω = Ω that is a contradiction.

The finite case also suggests the presence of a similar structure for the set of refinings R. However, in a complete family of frames whatever basis set S you choose there are refinings with codomain distinct from S, so that it is impossible to write down a simple correspondence between frames and maps as in Equation ( 8). Nevertheless, if we note that given two maps ω 1 and ω 2 their codomains Ω 1 , Ω 2 always have a common refinement Ω, we can write

ω 1 ⊗ ω 2 . = ω 1 ⊗ ω 2 (10)
where, after calling w 1 (w 2 ) the refining map between Ω 1 (Ω 2 ) and Ω,

ω 1 = w 1 • ω 1 , ω 2 = w 2 • ω 2
and ⊗ on the right side of Equation ( 10) stands for the composition of refinings in the finite family of compatible frames Ω A 1..4,7 generated by Ω. This way the operation ⊗ is again well-defined.

The composition of refinings can be rewritten in a more elegant way, proving its validity for general families too.

Definition 13. Given two maps ω 1 , ω 2 ∈ R, ω 1 : 2 Θ 1 → 2 Ω 1 and ω 2 : 2 Θ 2 → 2 Ω 2 we define ω 1 ⊗ ω 2 : 2 Θ 1 ⊗Θ 2 → 2 Ω 1 ⊗Ω 2 . ( 11
)
This operation is again well-defined, for the correspondence

(Dom(ω), Cod(ω)) ↔ ω ( 12
)
(guaranteed by Axiom A3) is a bijection. It obviously reduces to Definition 11 when applied to finite subfamilies.

Theorem 8. The set of refinings R of a complete generated family of compatible frames is a commutative monoid with respect to the internal operation (11).

Proof. Obviously ⊗ is commutative and associative for commutativity and associativity of the operation of minimal refinement of frames.

To find the unit element 1 ω it suffices to note that 1 ω is in correspondence through ( 12) with a pair of frames (Θ, Ω) such that

Θ ⊗ Θ 1 = Θ 1 ∀ Θ 1 ∈ F, Ω ⊗ Ω 1 = Ω 1 ∀ Ω 1 ∈ F
but that means Θ = Ω = 1, so that 1 ω : 2 1 → 2 1 and 1 ω turns out to be nothing but the identity map on 1.

Corollary 1. R is a submonoid of the product monoid (F, ⊗)×(F, ⊗) through the map (12).

Monoidal structure of families of compatible frames

In order to summarize what we have learned about the algebraic structures induced on families of compatible frames by the operation of minimal refinement, it is worth to specify the missing relations among them. Clearly, ( S ω A 1..4,7 , ⊗) (where S ω A 1..4,7 is the collection of all the refinings of a finite family of frames) is a monoid, too, and

Proposition 4. ( S ω (.) s A 1..4,7 , ⊗) is a submonoid of ( S ω A 1..4,7 , ⊗).
Proof. Obviously S ω (.) s A 1..4,7 ⊂ S ω A 1..4,7 in a set-theoretic sense. We only have to prove that the internal operation of the first set is inherited from the second one. If

ω 1 : 2 Θ 1 → 2 S and ω 2 : 2 Θ 2 → 2 S then S ⊗ S = S and ω 1 ⊗ S ω ω 2 : 2 Θ 1 ⊗Θ 2 → 2 S⊗S = 2 S ≡ ω 1 ⊗ S ω (.) s ω 2
In turn,

Proposition 5. ( S ω A 1..4,7 , ⊗) is a submonoid of (R, ⊗).
Proof. It suffices to prove that S ω A 1..4,7 is closed with respect to the composition operator (11). But then, given two maps ω 1 , ω 2 whose domains and codomains are both coarsening of S, Dom(ω

1 ⊗ ω 2 ) = Dom(ω 1 ) ⊗ Dom(ω 2 ) and Cod(ω 1 ⊗ ω 2 ) = Cod(ω 1 ) ⊗ Cod(ω 2 ) are still coarsenings of S.
while as far as frames are concerned, Proposition 6. ( S Θ A 1..4,7 , ⊗) is a submonoid of (F, ⊗).

Proof. Obvious, for the finite family of compatible frames S Θ A 1..4,7 is strictly included in the complete one F, and S Θ A 1..4,7 is closed with respect to ⊗, i.e. if Θ 1 and Θ 2 are coarsenings of S then their minimal refinement is still a coarsening of S.

A comprehensive picture of the relations between the monoidal structures associated with a family of compatible frames (F, R) can then be appreciated in the following diagram:

( S ω (.) s A 1..4,7 , ⊗) ⊂ ( S ω A 1..4,7 , ⊗) ⊂ (R, ⊗) ( S Θ A 1..4,7 , ⊗) ⊂ ( S Θ A 1..4,7 , ⊗) × ( S Θ A 1..4,7 , ⊗) ∩ = ( S Θ A 1..4,7 , ⊗) ⊂ (F , ⊗) ⊂ (F, ⊗) × (F, ⊗) (13)
where ∼ denotes an isomorphism, and ⊂ an inclusion between monoids.

Lattice structure

The notion of minimal refinement is the essence of the idea of families of compatible frames of discernment. This fact is reflected in the elegant scheme above, where a hidden matrioska of encapsulated monoids is depicted. It is still unclear, though, what is the deep root of the analogy between independence relations we discussed in the Introduction, with its potential role in the conflict problem.

Let us then take a step further.

Minimal refinement as least upper bound

It is well-known (see [START_REF] Jacobson | Basic Algebra I[END_REF], page 456) that the internal operation • of a monoid M induces an order relation among the elements of

M, namely b ≥ a ≡ ∃ c s.t. b = a • c, In our case this yields Θ 2 ≥ Θ 1 ≡ ∃ Θ 3 s.t. Θ 2 = Θ 1 ⊗ Θ 3 (14) ≡ Θ 1 ⊗ Θ 2 = Θ 2 , i.e. Θ
2 is a refinement of Θ 1 5 . Since both finite and general families of frames are monoids, AMAIframe-published.tex;14/02/2006;19:27;p.24 Proposition 7. S A 1..4,7 and F are partially ordered set (posets) with respect to the order relation (14).

In a poset the dual notions of least upper bound and greatest lower bound of a pair of elements can be introduced. Definition 14. Given two elements x, y ∈ X of a poset X their least upper bound sup X (x, y) is the smallest element of X that is bigger than both x and y, i.e. sup X (x, y) ≥ x, y and

if ∃z s.t. z ≤ sup X (x, y), z ≥ x, y then z = sup X (x, y).
Definition 15. Given two elements x, y ∈ X of a poset X their greatest lower bound inf X (x, y) is the biggest element of X that is smaller than both x and y, i.e. inf X (x, y) ≤ x, y and

if ∃z s.t. z ≥ inf X (x, y), z ≤ x, y then z = inf X (x, y).
The standard notation is inf(x, y) = x ∧ y and sup(x, y) = x ∨ y. By induction sup and inf can be defined for arbitrary finite collections too.

It must be pointed out that not any pair of elements of a poset, in general, admits inf and/or sup. Definition 16. A lattice is a poset in which each pair of elements admits both inf and sup.

Definition 17. An infinite lattice L is said complete if each arbitrary collection (even not finite) of points in L admits both sup and inf.

In this case there exist 0 ≡ ∧L, 1 ≡ ∨L called respectively initial and final element of L.

The notion of lattice provides us with an alternative interpretation of the minimal refinement operation.

Theorem 9. In a family of compatible frames F seen as a poset the sup of a finite collection of frames coincides with the minimal refinement,

sup F (Θ 1 , ..., Θ n ) = Θ 1 ⊗ • • • ⊗ Θ n .
5 It is interesting to note that Proposition (3) can be expressed in terms of the order relation

ω 2 ≥ ω 1 ⇒ ω 1 ⊗ ω 2 = ω 2 . Again, since ω 2 ≥ ω 1 ⇔ ω 2 = ω 1 ⊗ ω 3 for some ω 3 , it can rewritten as ω 1 ⊗ (ω 1 ⊗ ω 3 ) = (ω 1 ⊗ ω 1 ) ⊗ ω 3 = ω 1 ⊗ ω 3 . ( 15
)
This means that ω ⊗ ω = ω (idempotence) is a sufficient condition. -published.tex; 14/02/2006; 19:27; p.25 Proof. Of course Θ 1 ⊗• • •⊗Θ n ≥ Θ i ∀i = 1, ..., n for there exists a refining between each Θ i and their minimal refinement. Now, if there exists another frame Ω greater than each Θ i , then Ω is a common refinement for Θ 1 , ..., Θ n , hence it is a refinement of the minimal refinement, i.e. Ω ≥ Θ 1 ⊗ • • • ⊗ Θ n according to the order relation ( 14).

AMAIframe

At a first glance is not clear what inf{Θ 1 , ..., Θ n } should represent.

Maximal coarsening as greatest lower bound

Let us then introduce a new notion.

Definition 18. A common coarsening of two frames Θ 1 , Θ 2 is a set Ω ∈ F such that ∃ω 1 : 2 Ω → 2 Θ 1 and ω 2 : 2 Ω → 2 Θ 2 refinings, i.e.

is a coarsening of both frames.

This is well defined, as Theorem 10. If Θ 1 , Θ 2 ∈ F are elements of a family of compatible frames then they have a common coarsening.

Proof. From the proof of Theorem 7 they have at least 1 as common coarsening.

Theorem 10 is nothing but the dual of Axiom A6 (see Section 2.5). This opens the way to the introduction of a new operator acting on collections of compatible frames, the dual of the minimal refinement.

Theorem 11. Given a collection Θ 1 , ..., Θ n of elements of a family of compatible frames F there exists a unique element Ω ∈ F such that:

1. ∀i there exists a refining

ω i : 2 Ω → 2 Θ i ; 2. ∀θ ∈ Ω ∃ A 1 ⊆ ω 1 ({θ}), ..., A n ⊆ ω n ({θ}) s.t. η 1 (A 1 ) = ... = η n (A n )
where

η i : 2 Θ i → 2 Θ 1 ⊗•••⊗Θn .
We first need a simple intermediate result. Proof. Let us suppose there not exists such an element θ, but X i is covered by a subset X ⊂ Θ. If we consider one of these elements θ ∈ X we have

Lemma 2. Suppose Θ 1 ⊗• • •⊗Θ n is the minimal refinement of Θ 1 , ..., Θ n , with refinings η i : 2 Θ i → 2 Θ 1 ⊗•••⊗Θ n , and there exist X 1 ⊂ Θ 1 , ..., X n ⊂ Θ n with η 1 (X 1 ) = • • • = η n (X n ) such that ∃ A 1 ⊆ X 1 , ..., A n ⊆ X n s.t. η 1 (A 1 ) = ... = η n (A n ). Then for every common coarsening Θ of Θ 1 , ..., Θ n , with refinings ω i : 2 Θ → 2 Θ i , there exists θ ∈ Θ such that X i ⊂ ω i ({θ}) ∀i = 1, ...,
η i (ω i ( θ) ∩ X i ) = η i (ω i ( θ)) ∩ η i (X i )
but then η 1 (ω 1 ( θ)) = ... = η n (ω n ( θ)) by definition of common coarsening, and η 1 (X 1 ) = ... = η n (X n ) for hypothesis, so that

η 1 (ω 1 ( θ) ∩ X 1 ) = ... = η n (ω n ( θ) ∩ X n ) with A i . = ω i ( θ) ∩ X i ⊆ X i ∀i = 1, ...,
ω i ({l 1 }) = A i , ω i ({l 2 }) = B i ∀i = 1, ..., n
having defined B i = ω i ({l})\A i . This can always be done, for if ω i ({l})\ A i = ∅ for some i then it is not void ∀i. This procedure can be iterated until there are not subsets satisfying condition 2. It is also guaranteed to terminate, as the number of possible bijections of the images ω i ({l}) is finite. More precisely, the maximum number of steps is Uniqueness. Suppose Ω is another common coarsening satisfying condition 2, with refinings ω i : 2 Ω → 2 Θ i , distinct from Ω. If we define X i .

= ω i ({θ}), θ ∈ Ω, by lemma 2 there exists θ ∈ Ω such that ω i ({θ}) ⊂ ω i ({θ }). But then condition 2 implies ω i ({θ}) = ω i ({θ }) for every pair θ, θ so that Ω = Ω .

Definition 19. This unique frame is denoted by Θ 1 ⊕ ... ⊕ Θ n , and called maximal coarsening of Θ 1 , ..., Θ n .

Theorem 12. If Ω is a common coarsening of a finite set of compatible frames Θ 1 , ..., Θ n then Ω is a coarsening of their maximal coarsening too, i.e. there exists a refining ω : 2

Ω → 2 Θ 1 ⊕•••⊕Θn .
Proof. Let us consider another common coarsening Ω of Θ 1 , ..., Θ n , with α i : 2 Ω → 2 Θ i . If it satisfies condition 2 of Theorem 11 then for the uniqueness of Θ 1 ⊕ • • • ⊕ Θ n it coincides with the maximal coarsening. Otherwise the procedure of the above proof can be used to produce such a frame. Again, uniqueness guarantees that this is the maximal coarsening and by construction it is a refinement of Ω .

In other words, Corollary 2. The maximal coarsening Θ 1 ⊕ • • • ⊕ Θ n of a collection of frames Θ 1 , ..., Θ n coincides with the greatest lower bound (inf ) of the collection of frames as elements of the poset (F, ≥).

Birkhoff property

Proposition 1 and Theorems 9, 11 and 12 have a straightforward consequence on the algebraic structure of F.

Corollary 3. The collection of sets F of a family of compatible frames of discernment is a lattice, with respect to the internal operations of minimal refinement and maximal coarsening.

As we will see in this last part of the paper, the lattice-theoretic language turns out to be the right tool for discussing the algebraic nature of the conflict problem.

From a technical point of view, it must be pointed out that F lacks the attribute of completeness: the axioms do not guarantee the existence of a minimal refinement for an infinite (even countable) collection of sets. A more precise characterization of (F, ⊗, ⊕) can be given after introducing a few other lattice-theoretic notions (a reference can be found in [START_REF] Stern | Semimodular lattices[END_REF] and [START_REF] Szasz | Introduction to lattice theory[END_REF]). It can be proved that the Birkhoff property if weaker that modularity [START_REF] Stern | Semimodular lattices[END_REF]. Definition 22. A poset is said to have finite length if the length of its chains (collections of consecutive elements) is bounded. Now we have the tools to precise the nature of the lattices of compatible frames. Theorem 13. A finite family of compatible frames ( S A 1,..,4,7 , ≥) is a complete Birkhoff lattice of finite length6 .

Proof. ( S A 1,..,4,7 , ≥) is complete. Actually each finite lattice is complete for it does not contain any infinite collection of elements. ( S A 1,..,4,7 , ≥) is Birkhoff. Assume that Θ 1 and Θ 2 both cover their maximal coarsening. Necessarily Θ 1 ⊕ Θ 2 must have rank

|Θ 1 ⊕ Θ 2 | = |Θ 1 | -1 = |Θ 2 | -1, so that both refinings ω 1 : 2 Θ 1 ⊕Θ 2 → 2 Θ 1 and ω 2 : 2 Θ 1 ⊕Θ 2 → 2 Θ 2 leave unchanged each point of Θ 1 ⊕ Θ 2 but one, replaced by two new elements.
Now, on the other side Θ 1 and Θ 2 represent two different partitions Π 1 , Π 2 of their minimal refinement. By construction these partitions coincide but for the elements obtained by refining these two points, as shown in Figure 6. But then, their minimal refinement must be by definition the superposition of Π 1 , Π 2 : analytically Proof. It just remains to point out that, for Theorem 7, each arbitrary collection of frames in F admits a common coarsening 1, playing the role of initial element of the lattice.

Π 1 = {{p 1 , p 2 },
⊕ • • • ⊕ Θ n , Θ 1 ⊗ • • • ⊗ Θ n ].
We are hence finally able to discuss the difference between vector spaces and compatible frames in algebraic terms. As a matter of fact, it turns out that the collection of vector subspaces of a vector space forms a modular lattice [START_REF] Beutelspacher | Projective geometry[END_REF]. Lattices of compatible frames, instead, are not modular : Figure 7 shows a simple counterexample: Both the pairs formed by picking one of the left-most frames and the right-most one have the same minimal refinement and maximal coarsening (the unit frame). However, they are different even though linked by a refining, violating Definition 20.

Independence and pseudo Gram-Schmidt algorithm

Maybe it is time for a little summary. So far we have proved that the problem of conflicting belief functions, so important for sensor fusion applications, is inherently related to the notion of independence of frames. This in turn is strikingly similar to the notion of independence of vector subspaces. We have wondered whether this is more than a simple analogy or there is instead a deep connection, possibly providing us with a formally correct solution of the conflict problem.

We posed the question in an algebraic setup, and investigated the properties of the axioms defining a family of frames, in particular the notion of minimal refinement. We now know that both frames and refinings form monoids with respect to ⊗. This brought us to explore a possible description in terms of partially ordered sets. We learned how to define a dual operation in the families of compatible frames of discernment, called maximal coarsening ⊕. These families form in fact a lattice with respect to ⊕, ⊗.

The bottom line is that this particular class of lattices, called "Birkhoff", also includes lattices of the vector subspaces of a vector space. Those are in fact something more ("modular" lattices). As we are going to see, Birkhoff lattices are among the algebraic structures where the concept of independence can be introduced. In this last section we will discuss the possible outcomes of our algebraic analysis, and conjecture a possible formal solution of the conflict problem.

Linear independence and Birkhoff lattices

The following definition is due to Szasz [START_REF] Szasz | Introduction to lattice theory[END_REF].

Definition 23. Consider the collection P(M ) of all the finite subsets of a given set M and define in the product M ×P(M ) a relation Λ. Λ is said to be a linear dependence on the set M if it satisfies the following conditions:

1. p j Λ {p 1 , ..., p m }, j = 1, ..., n; 2. if p Λ {p 1 , ..., p m } and ∀j p j Λ {q 1 , ..., q n }, then p Λ {q 1 , ..., q n }; 3. if p Λ {p 1 , ..., p m , q} but p Λ {p 1 , ..., p m }, then q Λ {p 1 , ..., p m , p} where Λ means "is not in relation with".

A set provided with a linear (in)dependence relation is often called matroid [START_REF] Oxley | Matroid theory[END_REF]. Definition 23 is rather cryptic, so maybe it may be useful to give of it an alternative interpretation. More intuitively, a collection I of elements of a set M (matroid) is called the independent sets of M if it meets the independence augmentation axiom: if I 1 and I 2 are in I and |I 1 | < |I 2 | then there exists an element e of I 2 -I 1 such that I 1 ∪ e ∈ I. Try and think at the usual vector space case, and you will realize it does indeed satisfy this condition. Some elements of a Birkhoff lattice do admit a linear dependence relation. Let us call rank h(a) of an element a of a finite length semimodular lattice bounded below L, the length of the interval I[0, a] (i.e. the sublattice {x ∈ L : 0 ≤ x ≤ a}). In a lattice bounded below, the elements "covering" 0 (i.e. such that there are no other elements in the chains containing them) are called atoms. It can be proved that (see [START_REF] Cuzzolin | Visions of a generalized probability theory[END_REF], Chapter 6) Theorem 14. If L is a Birkhoff lattice bounded below, the equivalence relation LD ⊂ L × P(L) defined as

p LD {p 1 , ..., p n } ≡ h(p ∨ p 1 ∨ • • • ∨ p n ) < h(p 1 ∨ • • • ∨ p n ) + h(p)
(16) where p, p 1 , ..., p n ∈ A (the set of atoms) and h is the rank of the elements of the lattice is a linear dependence relation.

In other words, the atoms of a Birkhoff lattice form a matroid. Actually, the notion of linear independence of atoms of a semimodular lattice is due to G. Birkhoff and H. Whitney [START_REF] Whitney | On the abstract properties of linear dependence[END_REF], and is well known since the first half of the last century (consult his seminal work [START_REF] Birkhoff | Abstract linear dependence and lattices[END_REF], or [START_REF] Birkhoff | Lattice theory[END_REF]).

Equivalence of independence relations

As a family of compatible frames F is a Birkhoff lattice, it admits the lattice-theoretic dependence relation ( 16) on its atoms (the binary frames). On the other side, F is also endowed with the evidencetheoretic independence relation (6). Are they related?

A connection between these two different notions of independence becomes clear when we note that the linear independence relation associated with ( 16) is

p LI {p 1 , ..., p n } ≡ p LD {p 1 , ..., p n } ≡ h(p ∨ p 1 ∨ • • • ∨ p n ) = = h(p 1 ∨ • • • ∨ p n ) + h(p) = h(p 1 ) + ... + h(p n ) + h(p) (17)
where for a frame lattice Θ ∨ Ω = Θ ⊗ Ω. But now, condition 4 of Theorem 1 can be written as

f (Θ 1 ⊗ • • • ⊗ Θ n ) = f (Θ 1 ) + ... + f (Θ n )
where f = lg(|Θ|) = lg(r(Θ)) and r = |Θ| is the rank of a frame Θ as element of the lattice (F, ⊗, ⊕). We can then conjecture that Conjecture 1. The extension of the linear independence relation ( 17) to arbitrary elements of the frame lattice and the evidence-theoretic independence of frames ( 6) are equivalent.

The necessary steps to achieve an equivalence proof become obvious:

1. proving that Equation (17) defines a linear independence relation for arbitrary elements of a Birkhoff lattice, possibly enriched with additional properties;

2. showing that this can be also true for at least a suitable class of monotone functions of the rank (like logarithm).

To our knowledge no one has yet proposed to give a matroidal structure to whole Birkhoff lattices. Maybe a naive, straightforward implementation of ( 17) is not feasible: the problem is likely to deserve a paper of its own.

Towards an algebraic solution of the conflict problem

Anyway, the above discussion suggests a way to solve the conflict among measurement belief functions without resorting to the conflict graph mentioned in Section 3 [START_REF] Cuzzolin | An Evidential Reasoning Framework for Object Tracking[END_REF][START_REF] Cuzzolin | Integrating feature spaces for object tracking[END_REF].

We have pointed out in the Introduction the striking similarity between independence of frames and vectors. Their formal expressions in terms of vectors (top) and subsets (bottom), respectively, confirm this impression

i v i = 0 ⇐⇒ v 1 + ... + v n = 0, ∀v i ∈ V i i V i = 0 ⇐⇒ span{V 1 , ..., V n } = R d 1 × • • • × R d n i Θ i = 0 F ⇐⇒ Θ 1 ⊗ • • • ⊗ Θ n = Θ 1 × • • • × Θ n A t = ⇐⇒ ω 1 (A 1 ) ∩ • • • ∩ ω n (A n ) = ∅
where A t = (with the initial element of a Boolean algebra) is the independence condition for Boolean sub-algebras [START_REF] Sikorski | Boolean algebras[END_REF].

This analogy has a formal root in Corollary 4. L(V ) and F are both Birkhoff lattices, admitting the notion of independent elements. Moreover, the elements of these lattices (subspaces and frames) are commutative monoids. A vector space, indeed, is a group with respect to the operation "+" and a frame is a Boolean algebra, i.e. a complete distributive lattice, hence they are both commutative monoids ( [START_REF] Jacobson | Basic Algebra I[END_REF]). If Conjecture 1 is true, independence of frames and vector spaces may be nothing but different expressions of the matroidal structure of Birkhoff lattices.

We remember that, given a collection of arbitrary elements of a vector space, the well known Gram-Schmidt algorithm generates another collection of independent vectors, spanning the same subspace. Its basis elements are the independence condition and the projection of vectors onto other subspaces. Conjecture 1 suggests the concrete possibility of designing a "pseudo Gram-Schmidt" method resting on the shared algebraic structure of Birkhoff lattice of commutative monoids, and the associated independence relation. This algorithm, starting from a set of belief functions defined over a finite collection of discrete feature spaces, would build another collection of independent frames of the same family Θ 1 , ..., Θ n ∈ F -→ Θ 1 , ..., Θ m ∈ F s 1 , ..., s n → s 1 , ..., s m with m = n in general, and the same minimal refinement

Θ 1 ⊗ • • • ⊗ Θ n = Θ 1 ⊗ • • • ⊗ Θ m .
Once projected the n b.f. s 1 , ..., s n onto the new set of frames we would achieve a set of surely combinable belief functions s 1 , ..., s m , equivalent, in some sense, to the previous one. A formal definition of the equivalence of possibly non-combinable collections of belief functions needs of course to be introduced, even if it is reasonable to say it has to involve Dempster's combination.

Perspectives

In this work, in conclusion, we have shown how an algebraic description of the families of frames could open the way to a solution of the problem of conflicting evidence by means of algebraic tools. However, although we think the proposed method is the most elegant and rigorous approach to cope with groups of conflicting belief functions, the fundamental issues of Conjecture 1 and the pseudo Gram-Schmidt algorithm still need to be addressed prior to a practical application to information fusion problems (like the pose estimation task we discussed in Section 3). For instance, a precise definition of the projection operator in the context of Birkhoff lattices of commutative monoids has to be formulated. Furthermore, power sets are not groups, so we cannot simply subtract the projected elements like in the original G-S algorithm. Difficult questions concern the meaning of the obtained collection of independent frames (in the object tracking context, we could ask whether they represent actual features), or the order in which the input data is "orthogonalized". The prize of this challenging pursuit would be an elegant and definitive arrangement of the conflict problem, and by this means a rigorous approach to sensor fusion tasks.

Of course the present algebraic analysis's applications are far more extended, as many concepts of the theory of evidence are inherently connected to the structure of the underlying domains. For example, the notion of support function depends on the idea of refining and could quite likely be reformulated using the algebraic language. Its analysis in the light of the lattice structure of F can lead eventually to an alternative solution of the canonical decomposition problem. For a more technical point of view, other properties of the frame lattices still need to be investigated: the presence and nature of complements and semi-complements, intervals and the relations of filters and ideals with finite and general families of frames.

  2.1, and imagine to refine each column range c 1 , ..., c 5 into two subranges: ω(c 1 ) = {c 11 , c 12 }, ..., ω(c 5 ) = {c 51 , c 52 }. The new frame Ω . = {c 11 , c 12 , c 21 , c 22 , c 31 , c 32 , c 41 , c 42 , c 51 , c 52 } is a refinement of Θ . = {c 1 , ..., c 5 }. The vacuous extension of s 2 defined above is then the belief function s 2 on Ω with focal elements A 1 = {c 21 , c 22 } and A 2 = {c 21 , c 22 , c 41 , c 42 } and probability assignment

  Figure 3. An example of family of compatible frames of discernment. Different discrete quantizations of row and column ranges of an image have a common refinement, the set of cells shown on the left. The refinings between all those frames are shown on the right.

Figure 4 .

 4 Figure 4. The PantoMouse planar robot (left). Its pose is just the 2D position of its end-effector (right).

)

  Theorem 5. The subcollection of the refinings of a finite family of compatible frames S A 1..4,7 with codomain S S , Θ ∈ S A 1..4,7 } is a finite commutative monoid with annihilator with respect to (9).

Definition 20 .

 20 A lattice L is modular iff if a ≥ b, a ∧ c = b ∧ c, a ∨ c = b ∨ c then a = b. Definition 21. A lattice L is Birkhoff when a, b a ∧ b implies a ∨ b a, bfor all a, b ∈ L, where x y (x "covers" y) means that x > y and ∃z : x > z > y.

Figure 6 .

 6 Figure 6. Example of partitions like Π 1 (solid line) and Π 2 (dashed line) in Theorem 13.

Fabio Cuzzolin Figure 7 .

 Cuzzolin7 Figure 7. Non-modularity of finite families of frames: a counterexample.

  (figure 1-right).

	Definition 5. The orthogonal sum of two belief functions s 1 , s 2 is a
	new belief function s 1 ⊕ s 2 whose focal elements are all the possible
	non-empty intersections A i ∩ B j between focal elements A i , B j of s 1 , s 2
	respectively, and whose b.p.a. is given by

  The frame (middle) associated with a partition of the column range of an image (left). The b.f. s 1 with focal elements A 1 , A 2 and s 2 with f.e. B 1 , B 2 (middle) can be combined through Dempster's rule yielding a new belief function s1 ⊕ s2 (right) with f.e. X 1 and X 2 .

  an annihilator for S

	(.) S A 1..4,7 . ω

AMAIframe-published.tex; 14/02/2006; 19:27; p.19

  n, which is a contradiction. Now we can face the proof of Theorem 11.Proof. Existence. The proof is constructive. Let us take an arbitrary coarsening L of Θ 1 , ..., Θ n (which exists by Theorem 10) and check for every l ∈ L whether there exists a collection of subsets {A i ⊆ ω i ({l}), i = 1, ..., n} such that η 1 (A 1 ) = ... = η n (A n ). If the answer is negative we have the desired frame. Otherwise we can build a new common coarsening L of Θ 1 , ..., Θ n by simply splitting {l} into a pair {l 1 , l 2 } where

  p 3 , ..., p n }, Π 2 = {p 1 , ..., p n-2 , {p n-1 , p n }} having denoted their minimal refinement by {p 1 , p 2 , ..., p n-1 , p n }. Its rank is then equal to |Θ 1 ⊗Θ 2 | = |Θ 1 |+1 = |Θ 2 |+1. Hence it covers both frames, for there cannot exist any frame of intermediate size between Θ 1 or Θ 2 and Θ 1 ⊗ Θ 2 . By looking at the proof of Theorem 13 we can observe how it proves the Birkhoff property of general families of frames, too. As a matter of fact, being Birkhoff is a local property involving the sublattice [Θ 1

AMAIframe-published.tex; 14/02/2006; 19:27; p.4

For a note about the intuitionistic origin of this denomination see Rosenthal, Quantales and their applications[START_REF] Rosenthal | Quantales and their applications[END_REF].AMAIframe-published.tex; 14/02/2006; 19:27; p.5

See[START_REF] Stern | Semimodular lattices[END_REF] for an explanation in terms of the theory of monotone functions over partially ordered sets.

AMAIframe-published.tex; 14/02/2006; 19:27; p.7

AMAIframe-published.tex; 14/02/2006; 19:27; p.8

AMAIframe-published.tex; 14/02/2006; 19:27; p.9

AMAIframe-published.tex; 14/02/2006; 19:27; p.10

AMAIframe-published.tex; 14/02/2006; 19:27; p.11

This definition is nothing but a formulation in the evidential language of the concept of independence of Boolean subalgebras of a Boolean algebra[START_REF] Sikorski | Boolean algebras[END_REF].AMAIframe-published.tex; 14/02/2006; 19:27; p.13

Observe that axiom A1 in this situation is redundant, for it does not add any new refinings.

AMAIframe-published.tex; 14/02/2006; 19:27; p.17

AMAIframe-published.tex; 14/02/2006; 19:27; p.18

AMAIframe-published.tex; 14/02/2006; 19:27; p.21

AMAIframe-published.tex; 14/02/2006; 19:27; p.22

AMAIframe-published.tex; 14/02/2006; 19:27; p.23

AMAIframe-published.tex; 14/02/2006; 19:27; p.27

AMAIframe-published.tex; 14/02/2006; 19:27; p.28

For an alternative proof see[START_REF] Szasz | Introduction to lattice theory[END_REF].AMAIframe-published.tex; 14/02/2006; 19:27; p.29

AMAIframe-published.tex; 14/02/2006; 19:27; p.30

AMAIframe-published.tex; 14/02/2006; 19:27; p.31

AMAIframe-published.tex; 14/02/2006; 19:27; p.32

AMAIframe-published.tex; 14/02/2006; 19:27; p.33

Acknowledgements

This work has been partially supported by the Italian Space Agency (ASI) at the Autonomous Navigation and Computer Vision Laboratory of the University of Padova, Italy, led by Ruggero Frezza.