The theory of belief functions or “theory of evidence” allows the mathematical representation of uncertain pieces of evidence on which decisions can be based. Frequently, different pieces of evidence belong to distinct, albeit related, domains or “frames”: for instance, audio and video clues can be combined to infer the identity of a person from a video. Evidence encoded by different belief functions on separate frames can be merged on a common frame, a combination which is guaranteed to exist if and only if the frames are “independent” in the sense of Boolean algebras. In all other cases the evidence conflicts. Independence of frames and belief function combinability are then strictly related. In this chapter, the authors discuss the notion of independence of frames in the theory of evidence from an algebraic point of view, starting from an analogy with standard linear independence. The final goal is to search for a solution of the problem of conflicting belief function via a generalization of the classical Gram-Schmidt algorithm for vector orthogonalization. Families of frames can be given several algebraic interpretations in terms of semi-modular lattices, matroids, and geometric lattices. Each of those structures is endowed with a particular (extended) independence relation, which we prove to be distinct albeit related to independence of frames.
TopIntroduction
The theory of evidence was born as a contribution towards a mathematically rigorous description of subjective probability. In subjective probability, different observers (or “experts”) of the same phenomenon possess in general different notions of what the decision space is. Mathematically, this translates into admitting the existence of several distinct representations of this decision space at different levels of refinement. Evidence will in general be available on several of those domains or frames. In order for those experts to reach a consensus on the answer to the considered problem, it is necessary for such frames to be mathematically related to each other. This idea is embodied in the theory of evidence by the notion of family of frames. The evidence gathered on distinct elements of the family (corresponding to different experts or sensors) can be moved to a common frame in order to be merged.
In this context the notion of independence of frames IF (Shafer,1976) plays an important role. If different pieces of evidence are encoded as different belief functions on distinct frames, evidence fusion under Dempster's orthogonal sum (Dempster, 1967; Dempster, 1968; Dempster, 1969) is guaranteed to take place in all cases if and only if the involved frames are independent (Cuzzolin, 2005) in a very precise way, which comes from the theory of Boolean algebras. As Dempster's sum assumes the conditional independence of the underlying probabilities generating belief functions through multi-valued mappings, it is not surprising to realize that combinability (in Dempster's approach) and independence of frames (in Shafer's formulation of the theory of evidence) are strictly intertwined.
Here we build on the results obtained in (Cuzzolin, 2005) to complete the algebraic analysis of families of frames and conduct a comparative study of the notion of independence of frames, so central in the theory of evidence, in an algebraic setup. The work is articulated into two parts.
In the first half we prove that families of frames are endowed with three different algebraic structures, namely those of: 1. Boolean algebra, 2. upper semi-modular lattice, and 3. lower semi-modular lattice. In the second part we study relationships and differences between the different forms of independence that can be introduced on such structures, and understand whether IF can be reduced to one of them.
The contribution of this work is therefore twofold. On one side, we complete the rich algebraic description of families of compatible frames by relating them to semi-modular lattices and matroids, extending some recent preliminary results (Cuzzolin, 2005). On the other, we pose the notion of independence of frames in a wider context by highlighting its relation with classical independence in modern algebra. Even though IF turns out not to be a cryptomorphic form of matroidal independence, it possesses interesting relations with several extensions of matroidal independence to lattices, stressing the need for a more general, comprehensive definition of this widespread and important notion.
Eventually, this work may open the way to an algebraic solution of the conflict problem, where a pseudo Gram-Schmidt orthogonalization procedure is used to transform any given collection of belief functions into a new, combinable set by projection onto a new set of independent frames.
The outline of the Chapter is as follows. We start by recalling the notions of compatible frames and independence of frames as Boolean sub-algebras. We review a recent result linking frame independence and combinability with respect to Dempster's sum of belief functions: combinability can then be studied in an algebraic setup by analyzing the algebraic properties of independence of frames. Next, the example-based pose estimation problem is briefly described, as a typical application in which (possibly conflicting) belief functions living on different compatible frames need to be combined.
After that, the notion of independence on matroids is recalled. Even though families of frames endowed with IF do not form a matroid, matroids are strictly related to other algebraic structures, such as semi-modular lattices, which do describe collections of compatible frames.