How to Submit Proof Corrections Using Adobe Reader Using Adobe Reader is the easiest way to submit your proposed amendments for your IGI Global proof. If you don’t have Adobe Reader, you can download it for free at http://get.adobe.com/reader/. The comment functionality makes it simple for you, the contributor, to mark up the PDF. It also makes it simple for the IGI Global staff to understand exactly what you are requesting to ensure the most flawless end result possible. Please note, however, that at this point in the process the only things you should be checking for are: Spelling of Names and Affiliations, Accuracy of Chapter Titles and Subtitles, Figure/Table Accuracy, Minor Spelling Errors/Typos, Equation Display As chapters should have been professionally copy edited and submitted in their final form, please remember that no major changes to the text can be made at this stage. Here is a quick step-by-step guide on using the comment functionality in Adobe Reader to submit your changes. 1. Select the Comment bar at the top of page to View or Add Comments. This will open the Annotations toolbar. 2. To note text that needs to be altered, like a subtitle or your affiliation, you may use the Highlight Text tool. Once the text is highlighted, right-click on the highlighted text and add your comment. Please be specific, and include what the text currently says and what you would like it to be changed to. 3. If you would like text inserted, like a missing coma or punctuation mark, please use the Insert Text at Cursor tool. Please make sure to include exactly what you want inserted in the comment box. 4. If you would like text removed, such as an erroneous duplicate word or punctuation mark, please use the Add Note to Replace Text tool and state specifically what you would like removed. Mathematics of Uncertainty Modeling in the Analysis of Engineering and Science Problems S. Chakraverty National Institute of Technology - Rourkela, India A volume in the Advances in Computational Intelligence and Robotics (ACIR) Book Series Detailed Table of Contents Preface . ............................................................................................................................................... xiv Acknowledgment . ............................................................................................................................. xxii Chapter 1 Interval Mathematics as a Potential Weapon against Uncertainty .......................................................... 1 Hend Dawood, Cairo University, Egypt This chapter is devoted to introducing the theories of interval algebra to people who are interested in applying the interval methods to uncertainty analysis in science and engineering. In view of this purpose, we shall introduce the key concepts of the algebraic theories of intervals that form the foundations of the interval techniques as they are now practised, provide a historical and epistemological background of interval mathematics and uncertainty in science and technology, and finally describe some typical applications that clarify the need for interval computations to cope with uncertainty in a wide variety of scientific disciplines. Chapter 2 Uncertainty Modeling Using Expert’s Knowledge as Evidence .......................................................... 40 D. Datta, Bhabha Atomic Research, India In this paper we discuss the uncertainty modeling using evidence theory. In practice, very often availability of data is incomplete in the sense that sufficient amount of data which is required may not be possible to collect. Therefore, uncertainty modeling in that case with this incomplete data set is not possible to carry out using probability theory or Monte Carlo method. Fuzzy set theory or any other imprecision based theory is applicable in this case. With a view to this expert’s knowledge is represented as the input data set. Belief and plausibility are the two bounds (lower and upper) of the uncertainty of this imprecision based system. The fundamental definitions and the mathematical structures of the belief and plausibility fuzzy measures are discussed in this chapter. Uncertainty modeling using this technique is illustrated with a simple example of contaminant transport through groundwater. Chapter 3 Evidence-Based Uncertainty Modeling ................................................................................................ 55 Tazid Ali, Dibrugarh University, India Evidence is the essence of any decision making process. However in any situation the evidences that we come across are usually not complete. Absence of complete evidence results in uncertainty, and uncertainty leads to belief. The framework of Dempster-Shafer theory which is based on the notion of belief is overviewed in this chapter. Methods of combining different sources of evidences are surveyed. Relationship of probability theory and possibility theory to evidence theory is exhibited. Extension of the classical Dempster-Shafer Structure to fuzzy setting is discussed. Finally uncertainty measurement in the frame work of Dempster-Shafer structure is dealt with. Chapter 4 Hybrid Set Structures for Soft Computing ........................................................................................... 75 Sunil Jacob John, National Institute of Technology Calicut, India Babitha KV, National Institute of Technology Calicut, India A Major problem in achieving an effective computational systems is the presence of inherent uncertainty in the computational problem itself. Among various techniques proposed to address this, the technique of soft computing is of significant interest. Further, Generalized set structures like fuzzy sets, rough sets, multisets etc. have already proven their role in the context of soft computing. The computational techniques based on one of these structures alone will not always yield the best results but a fusion of two or more of them can often give better results. Such structures are regarded as hybrid set structures. This chapter surveys an analysis of various hybrid set structures which are quite useful tools for soft computing and shows how this hybridization can help in improving modeling real situations. Chapter 5 Source and M-Source Distances of Fuzzy Numbers and their Properties ............................................ 95 Majid Amirfakhrian, Islamic Azad University, Iran In many applications of fuzzy logic and fuzzy mathematics we need (or it is better) to work with the same fuzzy numbers. In this chapter we present source distance and source distance between two fuzzy numbers. Also some properties of parametric -degree polynomial approximation operator of fuzzy numbers. Numerical examples are solved related to the present analysis. Chapter 6 Construction of Normal Fuzzy Numbers using the Mathematics of Partial Presence . ...................... 109 Hemanta K. Baruah, Gauhati University, India Every normal law of fuzziness can be expressed in terms of two laws of randomness defined in the measure theoretic sense. Indeed, two probability measures are necessary and sufficient to define a normal law of fuzziness. Hence, the measure theoretic matters with reference to fuzziness have to be studied accordingly. In this chapter, we are going to discuss how to construct normal fuzzy numbers using this concept which is based on our mathematics of partial presence. Three case studies have been presented with reference to expressing stock prices in terms of fuzzy numbers. We have shown how exactly a normal fuzzy number appears. Chapter 7 Numerical Solution of Fuzzy Differential Equations and its Applications ........................................ 127 S. Chakraverty, National Institute of Technology Rourkela, India Smita Tapaswini, National Institute of Technology Rourkela, India Theory of fuzzy differential equations is the important new developments to model various science and engineering problems of uncertain nature because this theory represents a natural way to model dynamical systems under uncertainty. Since, it is too difficult to obtain the exact solution of fuzzy differential equations so one may need reliable and efficient numerical techniques for the solution of fuzzy differential equations. In this chapter we have presented various numerical techniques viz. Euler and improved Euler type methods and Homotopy Perturbation Method (HPM) to solve fuzzy differential equations. Also application problems such as fuzzy continuum reaction diffusion model to analyse the dynamical behaviour of the fire with fuzzy initial condition is investigated. To analyse the fire propagation, the complex fuzzy arithmetic and computation are used to solve hyperbolic reaction diffusion equation. This analysis finds the rate of burning number of trees in bounds where wave variable/ time are defined in terms of fuzzy. Obtained results are compared with the existing solution to show the efficiency of the applied methods. Chapter 8 Modeling with Stochastic Fuzzy Differential Equations .................................................................... 150 Marek T. Malinowski, University of Zielona Góra, Poland In the chapter, the authors consider an approach used in the studies of stochastic fuzzy differential equations. These equations are new mathematical tools for modeling uncertain dynamical systems. Some qualitative properties of their solutions such as existence and uniqueness are recalled, and stability properties are shown. Here, the solutions are continuous adapted fuzzy stochastic processes. The authors consider some examples of applications of stochastic fuzzy differential equations in modeling real-world phenomena. Chapter 9 Mathematics of Probabilistic Uncertainty Modeling . ........................................................................ 174 D. Datta, Bhabha Atomic Research, India This chapter presents the uncertainty modeling using probabilistic methods. Probabilistic method of uncertainty analysis is due to randomness of the parameters of a model. Randomness of parameters is characterized by specified probability distribution such as normal, log normal, exponential etc., and the corresponding samples are generated by various methods. Monte Carlo simulation is applied to explore the probabilistic uncertainty modeling. Monte Carlo simulation being a statistical process is based on the random number generation from the specified distribution of the uncertain random parameters. Sample size is generally very large in Monte Carlo simulation which is required to have small errors in the computation. Latin hypercube sampling and importance sampling are explored in brief. This chapter also presents Polynomial Chaos theory based probabilistic uncertainty modeling. Polynomial Chaos theory is an efficient Monte Carlo simulation in the sense that sample size here is very small and dictated by the number of the uncertain parameters and by choice of the order of the polynomial selected to represent the uncertain parameter. Chapter 10 Reaction-Diffusion Problems with Stochastic Parameters Using the Generalized Stochastic Finite Difference Method .............................................................................................................................. 206 Marcin Kamiński, Technical University of Łódź, Poland Rafał Leszek Ossowski, Technical University of Łódź, Poland The main aim of this work is to demonstrate the new stochastic discrete computational methodology consisting of the generalized stochastic perturbation technique and of the classical Finite Difference Method for the regular grids to model reaction-diffusion problems with random time series. The generalized stochastic perturbation approach is based on the given order Taylor expansion of all random variables. A numerical algorithm is implemented here using the Direct Differentiation Method of the reaction-diffusion equation with respect to the height of a channel in 1D problem; further symbolic determination of the probabilistic moments and characteristics is completed by the computer algebra system MAPLE, v. 14. Computational illustration attached proves that it is possible to determine using this approach up to the fourth order probabilistic moments and coefficients as well as to consider time series with random coefficients for any dispersion of the input variables. Stochastic fluctuations of the input uncertainty source are defined here as the power time series with Gaussian random coefficients having given first two moments. Chapter 11 MV-Partitions and MV-Powers . ......................................................................................................... 218 C. Drossos, University of Patras, Greece P. L. Theodoropoulos, Educational Counselor, Greece In this chapter, the authors generalize the Boolean partition to semisimple MV-algebras. MV-partitions together with a notion of refinement is tantamount a construction of an MV-power, analogous to Boolean power construction (Mansfield, 1971). Using this new notion we introduce the corresponding theory of MV-powers. Chapter 12 An Algebraic Study of the Notion of Independence of Frames . ........................................................ 240 Fabio Cuzzolin, Oxford Brookes University, UK 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. Chapter 13 Pricing and Lot-Sizing Decisions in Retail Industry: A Fuzzy Chance Constraint Approach............. 269 R. Ghasemy Yaghin, Amirkabir University of Technology, Iran S.M.T. Fatemi Ghomi, Amirkabir University of Technology, Iran S.A.Torabi, Amirkabir University of Technology, Iran Analysis of inventory systems involving market-oriented pricing decisions has recently become an interesting topic in the field of inventory control. Price and marketing expenditure are considered as important elements when selling goods and enhancing revenues by manufacturers. The importance of accounting for uncertainty in such environments spurs an interest to develop appropriate decision making tools to deal with uncertain and ill-defined parameters (such as costs and market function) in joint pricing and lot-sizing problems. In this research, a fuzzy chance constraint multi-objective programming model based on p-fractile approach is proposed to determine the optimal price, marketing expenditure and lot size. Considering pricing, marketing and lot-sizing decisions simultaneously, a possibilistic programming based on necessity measure is considered to handle imprecise data and constraints. Discount strategy as a fuzzy power function of order quantity is determined. After applying appropriate strategies to defuzzify the original possibilistic model, the equivalent multi-objective crisp model is then transformed by a single-objective programming model. A meta-heuristic algorithm is applied to solve the final crisp counterpart. Chapter 14 A New Approach for Suggesting Takeover Targets Based on Computational Intelligence and Information Retrieval Methods: A Case Study from the Indian Software Industry............................ 290 Satyakama Paul, University of Johannesburg, South Africa Andreas Janecek, University of Vienna, Austria Fernando Buarque de Lima Neto, University of Pernambuco, Brazil Tshilidzi Marwala, University of Johannesburg, South Africa In recent years researchers in financial management have shown considerable interest in predicting future takeover target companies in merger and acquisition (M&A) scenarios. However, most of these predictions are based upon multiple instances of previous takeovers. Now consider a company that is at the early stage of its acquisition spree and therefore has only limited data of possibly only a single previous takeover. Traditional studies on M&A, based upon statistical records of multiple previous takeovers, may not be suitable for suggesting future takeover targets for this company since the lack of history data strongly limits the applicability of statistical techniques. The challenge then is to extract as much knowledge as possible from the single/limited takeover history in order to guide this company during future takeover selections. Under such an extreme case, the authors present a new algorithmic approach for suggesting future takeover targets for acquiring companies based on solely one previous history of acquisition. The approach is based upon methods originating from information retrieval and computational intelligence. The proposal is exemplified upon a case study using real financial data of companies from the Indian software industry. Chapter 15 Fuzzy Finite Element Method in Diffusion Problems ........................................................................ 309 S. Chakraverty, National Institute of Technology, India S. Nayak, National Institute of Technology, India Diffusion is an important phenomenon in various fields of science and engineering. It may arise in a variety of problems viz. in heat transfer, fluid flow problem and atomic reactors etc. As such these diffusion equations are being solved throughout the globe by various methods. It has been seen from literature that researchers have investigated these problems when the material properties, geometry (domain) etc. are in crisp (exact) form which is easier to solve. But in real practice the parameters used in the modelled physical problems are not crisp because of the experimental error, mechanical defect, measurement error etc. In that case the problem has to be defined with uncertain parameters and this makes the problem complex. In this chapter related uncertain differential equation of various diffusion problems will be investigated using finite element method, which may be called fuzzy or interval finite element method. Chapter 16 Uncertainty Quantification of Aeroelastic Stability . .......................................................................... 329 Georgia Georgiou, University of Liverpool, UK Hamed Haddad Khodaparast, Swansea University, UK Jonathan E. Cooper, University of Bristol, UK The application of uncertainty analysis for the prediction of aeroelastic stability, using probabilistic and non-probabilistic methodologies, is considered in this chapter. Initially, a background to aeroelasticity and possible instabilities, in particular “flutter,” that can occur in aircraft is given along with the consideration of why Uncertainty Quantification (UQ) is becoming an important issue to the aerospace industry. The Polynomial Chaos Expansion method and the Fuzzy Analysis for UQ are then introduced and a range of different random and quasi-random sampling techniques as well as methods for surrogate modeling are discussed. The implementation of these methods is demonstrated for the prediction of the effects that variations in the structural mass, resembling variations in the fuel load, have on the aeroelastic behavior of the Semi-Span Super-Sonic Transport wind-tunnel model (S4T). A numerical model of the aircraft is investigated using an eigenvalue analysis and a series of linear flutter analyses for a range of subsonic and supersonic speeds. It is shown how the Probability Density Functions (PDF) of the resulting critical flutter speeds can be determined efficiently using both UQ approaches and how the membership functions of the aeroelastic system outputs can be obtained accurately using a Kriging predictor. Chapter 17 Uncertain Static and Dynamic Analysis of Imprecisely Defined Structural Systems ........................ 357 S. Chakraverty, National Institute of Technology Rourkela, India Diptiranjan Behera, National Institute of Technology Rourkela, India This chapter presents the static and dynamic analysis of structures with uncertain parameters using fuzzy finite element method. Uncertainties presents in the parameters are modelled through convex normalised fuzzy sets. Fuzzy finite element method converts the structures into fuzzy system of linear equations and fuzzy eigenvalue problem for static and dynamic problems respectively. As such method to solve fuzzy system of linear equations, fully fuzzy system of linear equations and fuzzy eigenvalue problems are presented. These methods are applied to various structural problems to find out the fuzzy static and dynamic responses of the structures. Also the chapter analyses the numerical solution of uncertain fractionally damped spring-mass system. Uncertainties considered in the initial condition of the system. Compilation of References ............................................................................................................... 383 About the Contributors .................................................................................................................... 412 Index.................................................................................................................................................... 417 240 Chapter 12 An Algebraic Study of the Notion of Independence of Frames Fabio Cuzzolin Oxford Brookes University, UK ABSTRACT 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. INTRODUCTION 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 DOI: 10.4018/978-1-4666-4991-0.ch012 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 no- Copyright © 2014, IGI Global. Copying or distributing in print or electronic forms without written permission of IGI Global is prohibited. An Algebraic Study of the Notion of Independence of Frames tion 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 semimodular 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 subalgebras. 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. Subsequently, we prove that families of frames are indeed both upper and lower semi-modular lattices, according to which order relation we pick. On such structures matroidal independence can be extended, yielding several different relations whose meaning we thoroughly discuss and whose links with IF we highlight in the final part of the Chapter. 241 An Algebraic Study of the Notion of Independence of Frames BACKGROUND Evidence combination has been widely studied (Yager, 1987; Zadeh, 1986) in different mathematical frameworks (Dubois & Prade, 1992; Smets, 1990): an exhaustive review would be impossible here. In particular, work has been done on the issue of merging conflicting evidence (DeutschMcLeish, 1990; Josang et al, 2003; Lefevre et al, 2002; Wierman, 2001), especially in critical situations in which the latter is derived from dependent sources (Cattaneo, 2003). Campos and de Souza (2005) have presented a method for fusing highly conflicting evidence which overcomes well known counterintuitive results. Liu (2006) has formally defined when exactly two basic belief assignments are in conflict by means of quantitative measures of both the mass of the combined belief assigned to the empty set before normalization, and the distance between betting commitments of beliefs. Murphy (2000), on her side, has studied a related problem: the failure to balance multiple sources of evidence. The notion of conflicting evidence is well known in the context of sensor fusion (Carlson & Murphy, 2005): the matter has been recently surveyed by Sentz and Ferson (2002). In opposition, though, not much work has been done on the properties of the families of compatible frames and their link with evidence combination. In (Shafer et al, 1987) an analysis of the collections of partitions of a given frame in the context of the hierarchical representation of belief can nevertheless be found, while in (Kohlas & Monney, 1995) both the lattice-theoretical interpretation of families of frames and the meaning of the concept of independence were discussed. In (Cuzzolin, 2005) these themes were reconsidered: the structure of Birkhoff lattice of a family of frames was proven, and the relation between Dempster’s combination and independence of frames highlighted. TOWARDS AN ALGEBRAIC APPROACH TO CONFLICT Independence of Frames and Dempster’s Combination In the theory of evidence (Dempster, 1967; Shafer, 1976), the mathematical representation of subjective probability is not a standard probability measure, but a belief function. Belief functions are defined by distributing non-zero masses to elements of the power set of the domain or frame (rather than elements of the domain itself), masses that need to normalize to 1. In this interpretation they can be considered as finite random sets (Nguyen, 1978). Obviously, they include probability measures in the special case in which masses are given only to singletons. They can also be interpreted as lower bounds to convex sets of probabilities (Cuzzolin, 2008). Different sources of evidence on the same problem can generate two or more distinct belief functions. These functions have then to be merged to take into account the full available evidence. Several different operators have been proposed. Historically the first such proposal is due to Dempster (1968, Section 2.1). In addition, such belief functions might not be defined on the same domain, but on different domains which all relate to the same decision or estimation problem. This idea is encoded by the notion of family of compatible frames. It turns out that belief functions defined on different compatible frames are guaranteed to be combinable if and only if such frames are independent is a way derived from Boolean algebras. Albeit not equivalent to independence of sources in the original formulation of Dempster’s combination, independence of frames is then strictly intertwined with combinability. A basic probability assignment (b.p.a.) over a finite set or frame (Shafer, 1976) Θ is a function m : 2˜ → [0, 1] on its power set 2˜ = {A ⊆ ˜ } such that m (∅) = 0 , ∑m (A) = 1 . A⊆˜ 242 An Algebraic Study of the Notion of Independence of Frames The belief function (b.f.) b : 2˜ → [0, 1] associated with a basic probability assignment m on Θ is defined as b (A) = ∑m(B ) . The focal B ⊆A elements of a belief function are the subsets A for which the b.p.a. is non-zero m(A) ≠ 0 . Different belief functions representing different pieces of evidence on the same decision space ˜ can be combined by Dempster’s orthogonal sum (Dempster, 1968). Definition 1: The orthogonal sum or Dempster’s sum of two belief functions b1, b2 : 2˜ → [0, 1] is a new belief function b1 ⊕ b2 : 2˜ → [0, 1] with b.p.a. mb ⊕b (A) = 1 2 ∑ ∑ ∩ mb (B ) mb (C ) B C =A ∩ 1 2 mb (B ) mb (C ) B C ≠∅ 1 , where ρ(A) Θ' is called a refinement of Θ , Θ a coarsening of ˜ ' . Shafer calls a structured collection F of frames a family of compatible frames of discernment ((Shafer, 1976), pages 121-125: see the Appendix for a formal definition). In such a family, in particular, every pair of frames has a common refinement, i.e., a frame which is a refinement of both. Each finite collection of compatible frames has many such 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 common refinement ˜ ∈ F of them such that for all i = 1, …, n such that (1) 2 {θ} = ρ ({θ }) ∩… ∩ρ ({θ }), 1 where mb denotes the b.p.a. of bi . i When the denominator of Equation (1) is zero the two functions are said to be non-combinable, and their orthogonal sum simply does not exist. What happens when the belief functions to combine are defined on different frames? If such frames are compatible, in a way that was given a mathematical characterization by Shafer (1976), then such a combination is still possible. Given two frames (finite sets) Θ and Θ' , a ' map ρ : 2Θ → 2Θ is a refining if it maps the elements of Θ to a disjoint partition of Θ' : ( ) ∩ρ ({θ }) = ∅ ∀θ, θ ρ {θ} ' ' ( ) ∈ Θ; ∪ρ {θ} = Θ' , θ∈Θ ∪ρ({θ}) for all A ⊆ Θ . The frame θ∈A 1 n n (2) where ρi denotes the refining between Θi and Θ . This unique frame is called the minimal refinement Θ1 ⊗ … ⊗ Θn of {Θ1, …, Θn } . In the example of Figure 1 we want to find out the position of a target point in an image. We can pose the problem on a frame Θ1 = {c1, …, c5 } obtained by partitioning the column range of the image into 5 intervals, or partition it into 10 intervals, yielding Θ2 = {c11, c12 , …, c51, c52 } . The row range can also be divided in, say, 6 intervals Θ3 = {r1, …, r6 } . All those frames belong to a family of compatible frames, with the collection of cells Θ = {e1, …, e60 } depicted in Figure 1-left as a common refinement, and refinings shown in Figure 1-right. It is easy to verify that Θ meets condition (2) for the frames Θ2 , Θ3 as, for example, 243 An Algebraic Study of the Notion of Independence of Frames Figure 1. An example of a family of compatible frames. Different discrete quantizations of row and column ranges of an image have as common refinement the set of cells on the left. The refinings ρ1, ρ2 , ρ3 between all those frames are shown on the right. {e } = ρ (c ) ∩ρ (r ) . Hence Θ is the minimal 41 2 11 3 4 refinement of Θ2 , Θ3 . The notion of compatible frames is crucial when facing real-world problems, as the available pieces of evidence are typically defined on different (albeit related) domains. For instance, in computer vision inference on the objects present in a scene is typically based upon a number of salient measurements or features extracted from the image(s). These features can be of various natures and belong to different spaces. Nevertheless, they all say something on, for example, the class of the object we are observing. Therefore, when representing evidence via belief functions, is important to be able to combine them even when they belong to different frames of a family. It has been proven that this is guaranteed to be possible (via Dempster’s rule) if and only if such frames are independent in the following way. Definition 2: Let {Θ1, …, Θn } be elements of a family of compatible frames, and the corresponding refinings to their minimal refinement. We say that {Θ1, …, Θn } are independent (Shafer, 1976) if 244 ( ) ∩…∩ρ ({A }) ≠ ∅ ρ1 {A1 } n n (3) whenever ∅ ≠ Ai ⊆ Θi for i = 1, …, n (see Figure 2). In particular, it is easy to see that if ∃j ∈ 1, …, n s.t. Θ j is a coarsening of some other frame Θi , Θi > 1, then {Θ1, …, Θn } are not independent. Mathematically, families of compatible frames are collections of Boolean sub-algebras of their common refinement ((Sikorski, 1964), see Appendix), as Equation (3) is nothing but the independence condition (23) for the associated sub-algebras. We denote in the following by IF the independence relation introduced in Definition 2. It can be proven that {Θ1, …, Θn } are IF iff (Cuzzolin, 2005) Θ1 ⊗ … ⊗ Θn = Θ1 ×…× Θn , (4) i.e., their minimal refinement is their Cartesian product. More importantly, belief functions defined on a number of frames {Θ1, …, Θn } are An Algebraic Study of the Notion of Independence of Frames Figure 2. Independence of frames surely combinable through Dempster’s rule iff {Θ1, …, Θn } are IF . Proposition 2 (Cuzzolin, 2005): Let {Θ1, …, Θn } be a set of compatible frames. Then they are independent iff all the possible collections of b.f.s b1, …, bn defined on Θ1, …, Θn , respectively, are combinable through Dempster’s sum (1) over their minimal refinement Θ1 ⊗ … ⊗ Θn . The notion of independence of frames is then intertwined with that of combinability. A Typical Application: ExampleBased Pose Estimation An example application in which the combinability of belief functions defined on different elements of a family of compatible frames is central is provided by the field of computer vision. Pose estimation (Agarwal & Triggs, 2006; Mori & Malik, 2006) is a well-studied problem there. Given an image sequence capturing the motion and evolution of an object of interest, the problem consists in estimating the position and orientation of the object at each time instant along the sequence, along with its internal configuration or pose. Such estimation is typically based on two pillars: salient measurements extracted from the images (features), and, when present, a model of the structure and kinematics of the moving body. Example based methods, on the other hand, explicitly store a set of training examples whose 3D poses are known, and estimate the object’s pose by searching for training image(s) similar to the given input image and interpolating the associated poses (Athitsos et al, 2004; Shakhnarovich et al, 2003). No prior structure of the pose space is incorporated in the estimation. Let us assume that: • The available evidence comes in the form of a training set of images containing sample poses of an unspecified object (see Figure 3(a)); The nature of the object is not necessarily known; we only know that its configuration can be described by a vector q∈ Q ⊂ RD in a pose space Q which is a subset of RD ; we assume, however, that an 245 An Algebraic Study of the Notion of Independence of Frames • “oracle” exists which provides for each training image I k the configuration qk of the object portrayed in the image; Also, we assume that the location of the object within each training image is roughly known, in the form of a bounding box containing the object of interest: features are then extracted only within the bounding box. During training, the object explores its range of possible configurations, and a set of poses is collected to form a finite approximation Q of the pose space: Q = {qk , k = 1, …,T } (5) At the same time a number N of distinct features are extracted from the available image(s): Y = {yi (k ), k = 1, …,T }, i = 1, …, N . (6) To acquire Q we need a source of “ground truth” (an “oracle”) to tell us what pose the object is in at each instant k of the training session. One option is to use a motion capture system as in (Cuzzolin and Gong, 2013; Rosales and Sclaroff, 2000) for the human body tracking problem (Figure 3(a)). In particular, if we apply a number of reflective markers in fixed positions of the body, the system is able to provide (through some triangulation algorithm) the 3D locations of the markers during the motion in the training stage. Since we do not know the parameter space of the Figure 3. (a) Top: training image of a person standing still and moving his right arm. Bottom: training image of the person walking inside a rectangle on the floor. Motion capture equipment is used to provide a ground truth pose vector qk for each training image I k . (b) Feature extraction: the object of interest is color segmented and the bounding box containing the foreground is detected to simulate localization annotation. The row and column indices of the vertices of this bounding box are collected in a feature vector y k = yi (k ) . (c) How a Mixture of Gaussian learned via EM clustering from the features col lected in the training stage defines an implicit partition on the set of training poses Q . The Gaussian densities Γ j , j = 1, …, n on the feature range Y define a partition of Y into regions Y j . Each region { } Y j is in correspondence with the set Q j of sample poses qk whose feature value y(qk ) falls inside Y j . 246 An Algebraic Study of the Notion of Independence of Frames object, it is then reasonable to adopt the markers’ locations as body configuration. The choice of the “sample” motions here is typically based on intuition, or gives a preference to “categorized” motions (like dancing or walking in human body tracking), perhaps as a legacy of the recognition problem. Based on this training evidence, in the testing stage: • A localization algorithm (trained in the training stage, e.g. (Felzenszwalb et al, 2010)) is employed to locate the object within the test image: features are only extracted (roughly) within the resulting bounding box; Such features are exploited to produce an • estimate q of its configuration, together with a measure of how reliable this estimate is. Learning Feature-To-Pose Maps Learning a model from a set of samples necessarily implies some sort of approximation of the involved feature spaces as well: this has non-trivial consequences on the performance of the resulting estimation. Given the training data (5), (6), EM clustering (McLachlan & Peel, 2000) provides a fast and reliable method to automatically build feature-pose maps that can eventually be used for examplebased pose estimation. Consider the N sequences of feature values {yi (k ), k = 1, …,T }, i = 1, …, N , acquired in the training session. EM clustering can be applied separately to each one of them, yielding a Mixture of Gaussian (MoG) approximation {Γ , j = 1, …, n } , Γ j i i j i ∼ N (µij , Σij ) (7) with ni components (Gaussian pdfs) of each d feature space (the range Yi ⊂ R i of the unknown feature function yi : I → Yi on the set of all images I ). The MoG (7) induces an implicit partition { Θi Yi 1, …, Yi ni } (8) o f t h e i - t h fe a t u r e r a n ge , w h e r e Yi j = {y ∈ Yi s.t. “ ij (y ) > “ li (y ) ∀l ≠ j } is the region of Yi in which the j-th Gaussian component dominates all the others (Figure 3(c)). The number n of clusters is a critical parameter of the EM algorithm, and is not known a priori (as, in fact, there might be no definite or unique answer). An estimate of n can be obtained from the data by cross-validation (Burman, 1989). As a result, the number of clusters ni will in general be different for each feature space. We call the finite partition ˜ i (8) of the range Yi of the i-th feature function the i-th approximate feature space. In virtue of the fact that features are computed in the training stage in synchronous with the true poses provided by the oracle, each element Yi j of the discrete feature space is associated with the set of training poses whose i-th feature value falls in Yi j (Figure 3(c) again): j ρi : Yi j Q i = qk ∈ Q : yi (k ) ∈ Yi j . (9) The feature-pose maps (9) are inherently multivalued, i.e., they map elements of an approximate feature space ˜ i to subsets of the collection of training poses Q . Given new feature evidence, we need to exploit the maps (9) to make inferences at the level of the pose. 247 An Algebraic Study of the Notion of Independence of Frames Evidential Modeling Summarizing, in the training stage the body moves freely in front of the camera(s), exploring its parameter space, while a sequence of training poses Q = {qk , k = 1, …,T } is provided by an oracle. The sample images are annotated by a bounding box indicating the location of the object within each image. At the same time: 1. For each time instant k, a number of features are computed from the region of interest of all the available images: Y = {yi (k ), k = 1, …,T }, i = 1, …, N ; 2. EM clustering is applied to each feature sequence {yi (k ), k = 1, …,T } (after choosing the appropriate number of clusters ni by cross validation), yielding: 3. N a p p r o x i m a t e f e a t u r e s p a c e s n Θi {Yi 1, …, Yi i } , i.e., the implicit partitions of the feature ranges Yi associated with the EM clusters; 4. N refinings (9) mapping clusters in the feature space to sets of sample training poses in the approximate pose space Q , So that the latter is a common refinement of the collection of approximate feature spaces {Θ1, …, Θn } . T h e c o l l e c t i o n o f FO D s Q, {Θ1, …, Θn } along with their refinings {ρ , …, ρ } is characteristic of both the object to 1 n track and the feature functions y1, …, yN designed and selected in the training stage: we call it the evidential model (Cuzzolin & Gong, in press) of the body (Figure 4). Figure 4. Evidential model architecture. EM clustering on each set of feature values collected in the n training stage yields an approximate feature space Θi {Yi 1, …, Yi i } . Refining maps ρi between each approximate feature space and the approximate parameter space Q = {qk , k = 1, …,T } are learned, allowing the fusion on Q of the evidence measured on {Θ1, …, Θn } . 248 An Algebraic Study of the Notion of Independence of Frames Tracking Algorithm 5. These “feature” belief functions are projected How can this structure be used to estimate the pose of the object, given new feature measurements? Assuming that each of those features yi gen- onto Q by vacuous extension; 6. Their Dempster’s combination is computed via (1); 7. The pignistic transform (Smets, 1990) is erates a belief function bi on the related feature space Θi , the feature pose maps (9) can be used to transfer the individual pieces of feature evidence onto the pose space and combine them there. If Ω is a refinement of Θ with refining ρ , any belief function defined on Θ can be “moved” to its refinement Ω by vacuous extension: a belief function b ' on Ω is called the vacuous extension of a b defined on Θ iff its focal elements are the images (via the refining ρ ) of focal elements of b. Since Q is a common refinement of all the feature spaces, the belief functions associated with new image measurements y1 (t ), …, yN (t ) can be projected on it and there combined via Dempster’s rule (1). Summarizing, given an evidential model of the moving body with N feature spaces, and given at time t one or more test images, possibly coming from different cameras: 1. The object detector learned in the training stage is applied to the test image(s), returning for each of them a bounding box roughly containing the object of interest; 2. The N feature values are extracted from the resulting bounding boxes, as in the training stage; 3. The likelihoods “ ij (yi (t )) of each feature value yi (t ) with respect to the appropriate learned Mixture of Gaussian distribution on Yi are computed, according to (7); 4. For each feature i = 1, …, N a belief function bi (t ) is built from these likelihood (cfr. Cuzzolin and Gong, in press); applied to the resulting belief function b(t ) , yielding a distribution on Q from which a pose estimate q(t ) can be computed (Cuzzolin and Gong, in press). Handling Conflict The mass assigned to the empty set by (1) represents the amount of evidence which is in contradiction, as it is assigned by the two belief functions to contradictory (disjoint) events. In our pose estimation scenario, conflict can arise in the test stage for basically two reasons: 1- the object is localized but in an imprecise way (due to limitations of the detector learned during training): as a consequence background features which conflict with foreground information are also extracted; 2- occlusions are present, causing conflict for similar reasons. By Proposition 2, belief functions coming from different image features are guaranteed to be combinable only in the ideal case in which all approximate feature spaces are IF independent (4). In all practical cases, the largest group of coherent, non-conflicting features need to be sought: under the assumption that most features will in any case come from the foreground, this will lead to the integration of foreground information only, bringing robustness to localization and occlusions. An analysis of the notion of conflict, and efficient algorithms for the detection of non-conflicting groups of belief functions are a crucial part of the framework (Cattaneo, 2011; Liu, 2006). 249 An Algebraic Study of the Notion of Independence of Frames An Algebraic Study of Independence of Frames In (Cuzzolin, 2005), starting from an analogy between independence of frames and linear independence, we conjectured a possible algebraic solution to the conflict problem, based on a mechanism similar to the classical Gram-Schmidt algorithm for the orthogonalization of vectors. Indeed, one can observe that the independence condition (3) resembles the condition under which a collection of vector spaces has maximal span (see also Equation (4)): v1 + … + vn ≠ ∅ ∀vi ∈ Vi ( ) ∩…∩ρ ({A }) ≠ ∅ ρ1 {A1 } ( n n ∀Ai ⊆ Θi span {V1, …,Vn } = V1 ×…×Vn Θ1 ⊗ … ⊗ Θn ≡ = Θ1 ×…× Θn . ≡ 10) Let us call a number of subspaces {V1, …,Vn } of a vector space V “independent” iff each collection of vectors {vi ∈ Vi , i = 1, …, n } is linearly independent. It follows that while a number of compatible frames {Θ1, …, Θn } are IF iff each ˜ selection of their representatives Ai ∈ 2 i has non-empty intersection, a collection of vectors subspaces {V1, …,Vn } is independent iff for each choice of vectors vi ∈ Vi their sum is non-zero. The collection of all the subspaces of a vector space or projective geometry forms a modular lattice. As we prove here, families of frames can be given the algebraic structure of semi-modular lattice, providing a partial explanation of this analogy. The goal of this Chapter is to go further and analyze the notion of independence of frames from an algebraic point of view, in order to understand whether it possesses any meaningful relations with other forms of independence. The purpose is two-fold: on one side, as independence of frames is formally independence of Boolean sub-algebras, this is a contribution 250 towards a better understanding of the notion in different fields of modern algebra. On the other hand, it provides the basis for an eventual algebraic proposal to the solution of the conflict problem in subjective probability. The paradigm of abstract independence in modern algebra is represented by the notion of matroid, introduced by Whitney (1935). Whitney, van der Waerden (1937), Mac Lane (1938) and Teichmuller (1936) all recognized that several apparently different notions of dependence (Beutelspacher & Rosenbaum, 1998; Harary & Tutte, 1969) in algebra (circuits in graphs, flats in affine geometries) have many properties in common with linear dependence of vectors. Definition 3: A matroid M = (E, I ) is a pair formed by a ground set E, and a collection of independent sets I ∈ 2E , such that: 1. ∅ ∈ I; 2. If I ∈ I and I' ⊆ I then I' ∈ I ; 3. If I1 and I2 are in I, and | I1| < | I2|, then there is an element e of I2 − I1 such that I 1 ∪e ∈ I . Condition (3) is called augmentation axiom, and is the foundation of the notion of matroidal independence. The name was coined by Whitney (1935) because of a fundamental class of matroids which arise from the collections of linearly independent (in the ordinary sense) sets of columns of a matrix, called “vector matroid”. Unfortunately, Theorem 1: A family of compatible frames F endowed with Shafer’s independence IF is not a matroid. Proof: In fact, IF does not meet the augmentation axiom (3) of Definition 3. Consider two independent frames I = {Θ1, Θ2 } . If we pick another arbitrary frame Θ3 of the fam- ily, the collection I ' = {Θ3 } is trivially IF. Suppose that Θ3 ≠ Θ1, Θ2 . Then, since An Algebraic Study of the Notion of Independence of Frames |I|>|I’|, by augmentation we can form a new pair of independent frames by adding any of Θ1, Θ2 to Θ3 . But it is easy to find a counterexample, for instance by picking as Θ3 the common coarsening of Θ1 and Θ2 (remember the remark after Definition 2). Matroidal independence, however, extends to similar relations in other algebraic structures, in particular semi-modular and geometric lattices (Stern, 1999). Even though families of frames are not matroids, they form semi-modular lattices: therefore, IF inherits interesting relations with a number of extensions of matroidal independence to semi-modular lattices (Birkhoff, 1935). Eventually, IF is in fact opposed to matroidal independence. The Lattice of Frames Collections of compatible frames (see Appendix) are collections of Boolean sub-algebras of (the power set of) their minimal refinement. In addition, as it has been proven in (Cuzzolin, 2005), they possess the structure of lattice. Two different order relations between frames can be defined. According to the chosen ordering, the resulting lattice will be either upper or lower semi-modular. This allows us to introduce a number of different extensions of matroidal independence to compatible frames, as we will see later on. A partially ordered set or poset is a set P endowed with a binary relation such that, for all x, y, z in P the following conditions hold: x ≤ x; if x ≤ y and y ≤ x then x = y; if x ≤ y and y ≤ z then x ≤ z. In a poset we say that x covers y (x y) if x ≥ y and there is no intermediate element in the chain (collection of consecutive elements) linking them. An example is the power set 2Θ of a set ˜ together with the inclusion relation ⊂ . A poset has finite length if the length of all its chains is bounded. Given two elements x,y ∈ P of a poset P their least upper bound supP (x,y) = x ∨ y is the smallest element of P that is bigger than both x and y. Their greatest lower bound infP (x,y) = x ∧ y is the biggest element of P that is smaller than both x and y. In the case of L = (2Θ , ⊆) “sup” is the usual set-theoretic union, A ∨ B = A ∪ B, while “inf” is the usual intersection A ∧ B = A ∩ B. By induction, sup and inf can be defined for arbitrary finite collections too. However, not any pair of elements of a poset, in general, is guaranteed to admit inf and/or sup. Definition 4: A lattice L is a poset in which each pair of elements admits both inf and sup. When each arbitrary (even not finite) collection of elements of L admits both inf and sup, L is said complete. In this case there exist 0 ≡ ∧ L, 1 ≡ ∨ L called respectively initial and final element of L. 2Θ is complete, with 0 = ∅ and 1 = {˜ } . The height h(x) of an element x in L is the length of the maximal chain from 0 to x. For the power set 2Θ , the height of a subset A ∈ 2Θ is simply its cardinality |A|. Families of Frames as Lattices In a family of compatible frames one can define two distinct order relations on pairs of frames, both associated with the notion of refining: Θ1 Θ1 ≤* Θ2 ⇔ ∃ρ : 2 Θ → 2 2 refining (11) ( Θ1 is a coarsening of Θ2 ), or Θ2 Θ1 ≤ Θ2 ⇔ ∃ρ : 2 Θ → 2 1 refining (12) i.e., Θ1 is a refinement of Θ2 . Relation (12) is clearly the inverse of (11). It makes sense to distinguish them explicitly as they generate two 251 An Algebraic Study of the Notion of Independence of Frames distinct algebraic structures, in turn associated with different extensions of the notion of matroidal independence. As it has been proven in (Cuzzolin, 2005), a family of frames F is a poset with respect to both (11) and (12). More precisely, after introducing the notion of maximal coarsening as the largest cardinality common coarsening Θ1 ⊕ …⊕Θn of x x ∧ y x ∨ y y ⇒ x ∨* y * x y * x ∧* y. (13) For lattices of finite length, upper and lower semi-modularity together imply modularity. In this sense semi-modularity is indeed “one half” of modularity. a given collection of frames, {Θ1 … Θn } , we can prove that: Upper and Lower SemiModular Lattices of Frames Proposition 3: Both (F , ≤) and (F , ≤* ) , where F is a family of compatible frames of discernment, are lattices, where Families of frames possess indeed the structure of semi-modular lattice. ∧i Θi = ⊗i Θi , ∨i Θi = ⊕i Θi , ∧i* Θi = ⊕i Θi , ∨i* Θi = ⊗i Θi . Upper and Lower Semi-Modularity A special class of lattices (modular lattices) arises from projective geometries, i.e. collections L(V) of all subspaces of a vector space V. Modular lattices, as many authors have shown, are also related to abstract independence. This quality is retained by a wider class of lattices called semimodular lattices. Definition 5: A lattice L is upper semi-modular if for each pair x, y of elements of L, x x ∧ y implies x ∨y y . A lattice L is lower semimodular if for each pair x, y of elements of L, x ∨ y y implies x x ∧ y . If L is upper semi-modular with respect to an order relation ≤ , than the corresponding dual lattice with order relation ≤* is lower semimodular, as 252 Theorem 2: (F , ≤) is an upper semi-modular lattice; (F , ≤* ) is a lower semi-modular lattice. Proof: We just need to prove the upper semimodularity with respect to ≤ . Consider two compatible frames Θ, Θ ' , and suppose that Θ covers their minimal refinement Θ ⊗ Θ ' , (their inf with respect to ≤ ). The proof articulates into steps depicted in Figure 5. • • As Θ covers Θ ⊗ Θ ' we have that | Θ |=| Θ ⊗ Θ ' | +1 ; This means that there exists a single element p ∈ Θ which is refined into a pair of elements {p1, p2 } of Θ ⊗ Θ ' , while all other elements of Θ are left unchanged: {p1, p2 } = ρ (p ); • • • This in turn implies that p1, p2 each belong to the image of a different element of Θ ' (otherwise Θ would itself be a refinement of Θ ' , and we would have Θ ⊗ Θ' = Θ ): p1 ∈ ρ ' (p '1 ) , p2 ∈ ρ ' (p '2 ) ; Now, if we merge p '1, p '2 we obviously have a coarsening Θ '' of Θ ' : {p '1, p '2 } = ρ '' (p '') An Algebraic Study of the Notion of Independence of Frames Figure 5. Proof of the upper semi-modularity of (F , ≤) • But Θ '' is a coarsening of Θ , too, as we can build the refining σ : Θ '' → 2Θ : σ (q ) = ρ ' ρ '' (q ) where ρ ' ρ '' (q ) is a ( ) ( ) subset of Θ for all q ∈ ˜ '' : ◦◦ If q = p '' , σ (q ) {p} ∪(ρ ' (p ' ) {p })∪(ρ ' (p ' ) {p }) ; If q ≠ p '' , ρ ' (ρ '' (q )) is also a set of 1 ◦◦ is 1 2 2 elements of Θ , as all elements of Θ but p are left unchanged by ρ . • • As Θ'' = Θ' − 1 we have that Θ'' is the maximal coarsening of Θ, Θ ' : '' Θ = Θ ⊕Θ ' ; Hence Θ ' covers Θ ⊕ Θ ’ , which is the sup of Θ, Θ ' in (F, ≤) . The lower semi-modularity with respect to ≤* comes then from (13). Theorem 2 strengthens the main result of (Cuzzolin, 2005), where we proved that finite families of frames are Birkhoff. A lattice is Birkhoff if x ∧ y ≺ x , y implies x , y ≺ x ∨ y . (Upper) semi-modularity implies the Birkhoff property, but not vice-versa. We will here focus on finite families of frames. Given a set of compatible frames {Θ1, …, Θn } we can consider the set P(Θ) of all the partitions of their minimal refinement Θ = Θ1 ⊗ … ⊗ Θn . As the independence condition (Definition 2) involves only partitions of Θ1 ⊗ … ⊗ Θn , we can conduct our analysis there. We denote by L (Θ) = (P (Θ), ≤) , L* (Θ) = (P (Θ), ≤* ) the two lattices associated with the set P(Θ) of partitions of Θ , with order relations (11), (12) respectively. Example: The partition lattice P4. Consider for example the partition lattice associated with a frame of size 4: Θ = {1, 2, 3, 4} , depicted in Figure 6, with order relation ≤* . Each edge indicates here that the bottom partition covers the top one. To understand how inf and sup work in the frame lattice, pick the partitions x = {1 / 2, 3, 4} , x ' = {1 / 2, 3 / 4} . 253 An Algebraic Study of the Notion of Independence of Frames According to the diagram the partition x ∨* x ' which refines both and has smallest size is Θ = {1 / 2 / 3 / 4} itself. Their inf x ∧* x ' is x , as x ' is a refinement of x . If we pick instead the pair of par titions y = {1, 2 / 3 / 4} and y ' = {1, 3 / 2 / 4} , we can notice that both y and y ' cover their inf y ∧* y ' = {1, 2, 3, 4} but in turn their sup y ∨* y ' = ˜ = {1 / 2 / 3 / 4} does not cover them. Therefore, (P (Θ), ≤* ) is not upper semi-modular but lower semi-modular. On the atoms of a lattice, i.e., the elements of the lattice covering 0 (think of one-dimensional subspaces of a vector space V) it is possible to define a matroidal independence relation. In particular, for each upper semimodular lattice L there exists a collection I of sets of atoms such that (A, I ) is a matroid. As families of frames form semi-modular lattices, we can explore the relations between IF and several extensions of matroidal independence to both L (Θ) and L* (Θ) . INDEPENDENCE ON LATTICES VS. INDEPENDENCE OF FRAMES Atom Matroid of a SemiModular Lattice are linearly independent iff ∑αi vi = 0 αi = 0 i for all i. This classical definition can be given several equivalent formulations: I2 : v j ≠ span(vi , i ≠ j ) ∀j = 1, …, n ; v j ∩span (v1, …, v j −1 ) = 0, ∀j = 2, …, n ; ( ) I3 : dim span (v1, …, vn ) = n. 254 Definition 6: The following relations on the elements of a semi-modular lattice with initial element 0 can be defined: {v1, …, vn } are I1 if (l (14) j ) ( ∨ li ≡ l j ∧ ∨ li ≠ l j i≠j i≠j ) ∀j = 1, …, n; {v1, …, vn } are I2 if l j ∧ ∨ li = 0 ∀j = 2, …, n; i<j {v1, …, vn } are I3 if h Consider again the classical example of linear independence of vectors. By definition {v1, …, vn } I1 : Remember that the one-dimensional subspaces of a vector space V are the atoms of the lattice L(V) all the linear subspaces of V, for which ∨= span, ∧ = ∩ , dim = h and 0 = 0. Following this intuition we can extend the relations (14) to collections of arbitrary (not necessarily atomic) non-zero elements of an arbitrary semi-modular lattice with initial element 0. ( l ) = ∑h (l ). i i i i These relations have been studied by several authors in the past: our purpose here is to understand their relation with independence of frames in the semimodular lattice of frames. For arbitrary elements of a lattice, I1, I2 and I3 are distinct, and none of them generates a matroid. However, when defined on the atoms of an upper semimodular lattice with initial element they do coincide, and form a matroid (Szasz, 1963). An Algebraic Study of the Notion of Independence of Frames Proposition 4: The restrictions of the above relations to the set of the atoms A of an upper semi-modular lattice L with initial element are equivalent, namely I1 = I2 = I3 = I on A, and (A, I ) is a matroid. As the partition lattice has both an upper L (Θ) and lower L* (Θ) semi-modular form, we can introduce two forms I1, I2 , I3 and I1* , I2* , I*3 of the above relations associated with L (Θ) and L* (Θ) , respectively. These constitute different valid extensions of matroidal independence to elements of semi-modular lattices. As families of compatible frames form semi-modular lattices in their own right, it is natural to wonder what their relationship is, if any, with Shafer’s independence of frames IF. Boolean and Lattice Independence in the Upper Semi-Modular Lattice L (Θ) Form of the relations. In L (Θ) the relations introduced in Definition 6 assume the forms: only if no frame Θ j is a refinement of the maximal coarsening of all the others. They are I2 if and only if, for all j = 2, …, n , Θ j does not have a non-trivial common refinement with the maximal coarsening of all its predecessors. The interpretation of I3 is perhaps more interesting. The latter is equivalent to say that the coarsening that generates ⊕ni =1 Θi can be broken up into n steps of the same length of the coarsenings that generate each of the frames Θi starting from Θ. . Namely: first Θ1 is obtained from Θ by merging Θ − | Θ1 | elements, then Θ − | Θ2 | elements of this new frame are merged, and so on until we get to a frame of cardinality ⊕ni =1 Θi . We will return on this when discussing the dual relation on the lower semi-modular lattice L* (Θ) . To study the logical implications between these lattice-theoretic relations and independence of frames, and between themselves, we first need a useful Lemma. Lemma 1: If {Θ1 … Θn } are IF, n > 1, then {v1, …, vn } ∈ I1 iff Θ j ⊗ ( ⊕i ≠ j Θi ) ≠ Θ j ∀j = 1, …, n, They read as follows: {Θ1 … Θn } are I1 if and (15) ⊕ni =1 Θi = 0F . Proof: We prove Lemma 1 by induction. For n = 2, let us suppose that {Θ1, Θ2 } are IF. Then ( Θ j ⊗ ( ⊕i < j Θi ) = Θ ∀j = 2, …, n, (16) 2 for all denotes as usual the refining from Θi to ( ) Θ − ⊕ni =1 Θi = ∑ Θ − | Θi | , i =1 2 ∅ ≠ A1 ⊆ Θ1, ∅ ≠ A2 ⊆ Θ2 (where ρi {v1, …, vn } ∈ I3 iff n ) ∩ρ ({A }) ≠ ∅ ρ1 {A1 } {v1, …, vn } ∈ I2 iff Θ1 ⊗ Θ2 ). Suppose by absurd that their common coarsening contains more than a single element, Θ1 ⊕ Θ2 = {a, b} . But then (17) forinthelattice L (Θ) wehave Θi ∧ Θ j = Θi ⊗ Θ j , Θi ∨ Θ j = Θi ⊕ Θ j , h (Θi ) = Θ − | Θi |, and ( ) ∩ρ (ρ (b )) = ∅ ρ1 ρ1 (a ) 2 2 0 = Θ. 255 An Algebraic Study of the Notion of Independence of Frames where ρi denotes the refining between Θ1 ⊕ Θ2 5. and Θi ), going against the hypothesis. {Θ , Θ } ∈ IF and {Θ , Θ } ∈ ℑ 1 2 1 2 3 iff Θi = 0F and Θ j = Θ. . Induction step: Suppose that the thesis is true for n − 1. We know that if {Θ1 … Θn } are Proof: 1. If {Θ1, Θ2 } are IF then Θ1 is not a refinement of Θ2 , and vice-versa, un- IF we have that any sub-collection {Θi , i ≠ j } is also IF. By inductive hypothesis, the latter implies: less one of them is 0F . But then they are I1 ( Θ1 ⊗ Θ2 ≠ Θ1, Θ2 ). 2. We can give a counterexample as in Figure 7 in which {Θ1, Θ2 } are I1 (as ⊕i ≠ j Θi = 0F ∀j = 1, …, n. none of them is refinement of the other one) but their minimal refinement Θ1 ⊗ Θ2 has cardinality Then, since 0F is a coarsening of Θ j for all 4 ≠| Θ1 | ⋅ | Θ2 |= 6 (hence they are not IF). 3. Trivial. 4. I3 I1 is equivalent to j, Θ j ⊕ (⊕i ≠ j Θi ) = Θ j ⊕ 0F = 0F . Pairs of frames: Let us consider first the special case of collections of just two frames. For n = 2 the three relations I1, I2 , I3 read respectively as not I1 not I3 . But {Θ1, Θ2 } not I1 reads as Θ1 ⊗ Θ2 = Θi , which is (18) in turn equivalent to Θ1 ⊕ Θ2 = Θ j . I.E., 5. As {Θ1, Θ2 } are IF, Θ1 ⊕ Θ2 = 1 so It is interesting to remark that if {Θ1, Θ2 } are lent to | Θ | + | 1 |=| Θ1 | + | Θ2 | . Now, by definition Θ1 ⊗ Θ2 ≠ Θ1, Θ2 , Θ1 ⊗ Θ2 = Θ, Θ + Θ1 ⊕ Θ2 =| Θ1 | + Θ2 . I1 then Θ1, Θ2 ≠ Θ. . We can prove the following logical implications. Theorem 3: 1. If {Θ1, Θ2 } are IF then {Θ1, Θ2 } are 2. 3. I1 if Θ1, Θ2 ≠ 0F . {Θ , Θ } ∈ ℑ d o e s n ot i m p ly {Θ , Θ } ∈ IF. {Θ , Θ } ∈ ℑ implies {Θ , Θ } ∈ ℑ 1 2 1 2 1 2 1 2 1 iff Θ1, Θ2 ≠ Θ . 4. {Θ , Θ } ∈ ℑ 1 2 3 1 implies {Θ1, Θ2 } ∈ ℑ1 iff Θ1, Θ2 ≠ Θ . 256 2 that {Θ1, Θ2 } ∈ ℑ3 , which is equiva- | Θ |≥| Θ1 ⊗ Θ2 |=| Θ1 || Θ2 | (the last passage holding as those frames are IF). {Θ , Θ } ∈ ℑ ≡ | Θ | + | Θ j |=| Θi | + | Θ j | ≡ | Θ |=| Θi | . 1 2 3 Butthen {Θ1, Θ2 } ∈ ℑ3 implies {Θ1, Θ2 } ∈ ℑ1 iff Θ1, Θ2 ≠ Θ. . An Algebraic Study of the Notion of Independence of Frames Figure 7. Counterexample for the conjecture “ I1 implies IF” of Theorem 3. stronger than the weakest form I1 . Some of those features are retained by the general case too. General Case n > 2 The situation is somehow different in the general case of a collection of n frames. IF and I1 , in particular, turn out to be incompatible. Theorem 4: If {Θ1 … Θn } are IF, n > 2 then {Θ1 … Θn } are not I1 . Therefore {Θ1, Θ2 } ∈ IF and {Θ1, Θ2 } ∈ ℑ3 together imply Θ1 + Θ2 ≥ Θ1 Θ2 + 1 ( ) ≡ Θ1 − 1 ≥ Θ1 Θ2 − Θ2 = Θ2 Θ1 − 1 ≡ Θ2 ≤ 1, which holds iff the equality holds, i.e., Θ2 = 0F . The latter implies Θ = Θ1 ⊗ Θ2 = Θ1 . In the singular case Θ1 = 0F , Θ2 = Θ by definition (18) the pair {0F , Θ} is both I2 and Proof: If {Θ1 … Θn } are IF then any collection formed by some of those frames is IF (otherwise we could find empty intersections in Θ1 ⊗ … ⊗ Θn ). But then, by Lemma 1, ⊕i ∈L⊂{1,…,n } Θi = 0F for all subsets L of {1, …, n } with at least 2 elements: |L| > 1. But then, as L = {i ≠ j, i ∈ {1, …, n }} has cardinality n − 1 > 1 (as n > 2 ) we have ⊕i ≠ j Θi = 0F for all j ∈ {1, …, n } . Therefore I3 , but not I1 . Besides, two frames can be both Θ j ⊗ (⊗i ≠ j Θi ) = Θ j ⊗ 0F = Θ j I2 and IF without being singular in the above sense. The pair of frames {y,y’} of Figure 6 provides such an example, as y ⊗ y ' = Θ ( I2 ) and they are IF. Finally, it well known that (Szasz, 1963) on an upper-semi-modular lattice (such as L (Θ) ): and {Θ1 … Θn } are not I1 . Proposition 5: I2 I3 . Proof: If {Θ1 … Θn } are IF then {Θ1 … Θk −1 } are IF for all k = 3,…,n. Independence of frames and the most demanding form I3 of extended matroidal independence relation to frames as elements of an upper semimodular lattice are mutual exclusive, and are both ∀j ∈ {1, …, n } Theorem 5: If {Θ1 … Θn } are IF, n > 2, then {Θ1 … Θn } are not I2 . But by Lemma 1 this implies ⊕i <k Θi = 0F , so that: Θk ⊗ ⊕i <k Θi ≠ Θk ∀k > 2. 257 An Algebraic Study of the Notion of Independence of Frames Now, {Θ1 … Θn } ∈ IF with n > 2 implies Θk ≠ Θ for all k. That holds because, as n > 2 , there is at least one frame Θi in the collection {Θ1 … Θn } which is distinct from 0F , and clearly {Θi , Θ} are not IF (as Θi is a non-trivial coarsening of Θ ). Hence Θk ⊗ ⊕i <k Θi ≠ Θ ∀k > 2, which is in fact a much stronger condition than ¬I2 . A special case is that in which one of the frames is Θ itself. By Definitions (15) and (16) of I1 and I2 , if there exists j such that Θ j = Θ then {Θ1 … Θn } ∈ ℑ2 implies {Θ1 … Θn } not I1 . By Proposition 5 it follows that Corollary 1: If {Θ1 … Θn } are IF, n > 2, then {Θ … Θ } are not 1 n I3 . Putting together the results of Theorems 3 and 5 and Corollary 1 we get that IF and I3 are incompatible in all significant cases. Corollary 2: If {Θ1 … Θn } are IF then they are not I3 , unless n = 2 , Θ1 = 0F and Θ2 = Θ . Boolean and Lattice Independence in the Lower Semi-Modular Lattice {v1, …, vn } ∈ I2* iff ( ) Θ j ⊕ ⊗ij=−11 Θi = 0F ∀j = 2, …, n, (20) n i =1 Θi ∧* Θ j = Θi ⊕ Θ j , , ˜ i ∨* ˜ h (˜ * i )= ˜ i {v1, …, vn } ∈ I iff Θ j ⊕ (⊗i ≠ j Θi )≠ Θ j ∀j = 1, …, n, (19) 258 (21) j = ˜ i ⊗ ˜ j, , − 1, , and 0 = 0F . . These relations also have quite interesting semantics. The frames {Θ1 … Θn } are I1* iff none of them is a coarsening of the minimal refinement of all the others. In other words, there is no proper subset of {Θ1 … Θn } which has still Θ1 ⊗ … ⊗ Θn as a common refinement. They are I2* iff for all j > 1 the frame Θ j does not have a non-trivial common coarsening with the minimal refinement of its predecessors. Finally, the third form I*3 of extended matroidal independence relation possesses a very interesting semantics in terms of probability spaces. As the dimension of the polytope of probability measures definable on a domain of size k is k − 1, , {Θ1 … Θn } are I*3 iff the dimension of the probability polytope associated with the minimal refinement is the sum of the dimensions of the polytopes associated with the individual frames: {Θ1 … Θn } ∈I*3 ≡ dim P˜ 1 ⊗…⊗˜ L (Θ) * 1 ) for in the lattice L (Θ) we have * Semantics of extended matroidal independence: Analogously, the extended matroidal independence relations associated with the lower semimodular lattice L* (Θ) read as ( {v1, …, vn } ∈ I*3 iff ⊗ni =1 Θi − 1 = ∑ Θi − 1 , n = ∑dim P˜ . i (22) It is interesting to point out the following analogy between independence of frames and I*3 . While condition (4) for IF Θ1 ⊗ … ⊗ Θn = Θ1 ×…× Θn An Algebraic Study of the Notion of Independence of Frames Figure 6. The partition (lower) semi-modular lattice L* (˜ ) for a frame ˜ of size 4. Partitions of ˜ are denoted by {A1 / … / Ak } . Partitions with the same number of elements are arranged on the same level. An edge between two nodes indicates that the bottom partition covers the top one. states that the minimal refinement is the Cartesian product of the individual frames, Equation (22) for I*3 states that the probability simplex of the minimal refinement is a Cartesian product of the individual ones. General Case {˜ i , i ≠ j} ∈ IF, for all θ ∈ ⊗i ≠ j Θi there exist θi ∈ Θi , i ≠ j s.t. {θ} = ∩ρ ' (θ ), i≠j i i where ρ 'i is the refining to ⊗i ≠ j Θi . Now, θ Theorem 6: If {Θ1 … Θn } ∈ IF and Θ j ≠ 0F for all j, then {Θ1 … Θn } ∈ ℑ1* . Proof: Let us suppose that {Θ1 … Θn } ∈ IF but not I1* , i.e., there exist j such that Θ j is a coarsening of ⊗i ≠ j Θi . We need to prove that ∃A1 ⊂ Θ1, …, An ⊂ Θn such that belongs to a certain element A of the partition Π j . By hypothesis ( Θ j ≠ 0F for all j) Π j contains at least two elements. But then we can choose θj = ρ−1 (B ) with B another element of Π j . In this case we obviously get ρj (θj ) ∩∩ρi (θi ) = ∅, i≠j ( ) ∩…∩ρ ({A }) = ∅, ρ1 {A1 } n n where ρi denotes the refining from Θi to Θ1 ⊗ … ⊗ Θn . Since Θ j is a coarsening of ⊗i ≠ j Θi , there exists a partition Π j of ⊗i ≠ j Θi associated with Θ j , and a refining ρ from Θ j to ⊗i ≠ j Θi . As which implies that {Θ1 … Θn } are not IF, against the hypothesis. Does IF imply I1* even when ∃˜ i = 0F ? The answer is negative. {Θ1 … Θn } ∈ ¬I1* means that there exists j s.t. Θ j is a coarsening of ⊗i ≠ j Θi . But if Θi = 0F then Θi is a coarsening of ⊗i ≠ j Θi . The reverse implication does not hold: IF and * I1 are distinct. 259 An Algebraic Study of the Notion of Independence of Frames Theorem 7: {Θ1 … Θn } ∈ I1* does not imply {Θ1 … Θn } ∈ IF. Proof: We need a simple counterexample. Consider two frames Θ1 and Θ2 in which Θ1 Θ j ⊗ ⊗i ≠ j Θi = Θ j × (×i ≠ j Θi ), Then Θ1, Θ2 ≠ Θ1 ⊗ Θ2 but it easy to find which is equivalent to {Θ j , ⊗i ≠ j Θi } ∈ IF. But then by Lemma 1 we get as desired. It follows from Theorems 6 and 9 that, unless some frame is unitary, an example (see Figure 8) in which Θ1, Θ2 are not IF. Corollary is not a coarsening of Θ2 ( Θ1, Θ2 are I1* ). Besides, like in the upper semi-modular case, I2* does not imply I1* . Theorem 8: {Θ1 … Θn } ∈ I2* does not imply {Θ1 … Θn } ∈ I1* . Proof: Figure 9 shows a counterexample to the conjecture I2* I1* . Given Θ1 ⊗ … ⊗ Θ j −1 and Θ j , one possible choice of Θ j +1 such that {Θ1 … Θ j +1 } are I2* but not I1* is shown. 3: {˜ 1 … ˜ n } ∈ IF {˜ 1 … ˜ n } ∈ I ∧ I (i.e., independence of frames is a more demanding requirement than both the first two forms of latticetheoretic independence) * 1 * 2 Note that the converse is false. Think of a pair of frames (n = 2), for which ( ) Θ1 ⊕ Θ2 ≠ Θ1, Θ2 Θ1, Θ2 ∈ ℑ1* , ( * 2 ) Θ1 ⊕ Θ2 = 0F Θ1, Θ2 ∈ ℑ . Independence of frames IF is a stronger condition than I2* as well. Such conditions are met for instance in Figure 8, where the two frames are not IF. Theorem 9: {Θ1 … Θn } ∈ IF {Θ1 … Θn } ∈ ℑ2* . Theorem 10: If a collection {Θ1 … Θn } of com- Proof: We first need to show that {Θ1 … Θn } are IF iff for all j = 1,…,n the pair {Θ j , ⊗i ≠ j Θi } is IF. As a matter of fact (4) can be written as patible frames is IF then it is not I*3 , unless n = 2 and one of the frames is the trivial partition. Proof: According to Equation (4), {Θ1 … Θn } are IF iff | ⊗Θi |= ∏ | Θi | , while accordi Figure 9. A counterexample to I2* I1* 260 An Algebraic Study of the Notion of Independence of Frames Figure 8. A counterexample in which I1* does not imply IF ing to (21) they are I*3 iff ⊗Θi − 1 = ∑( Θi − 1) . Those conditions i are both met iff ∑Θ i i − ∏ Θi = n − 1, i which happens only if n = 2 and either Θ1 = 0F or Θ2 = 0F . Instead of being algebraically related notions, independence of frames and matroidicity work against each other. As independence of frames derives from independence of Boolean subalgebras of a Boolean algebra (Sikorski, 1964), this is likely to have interesting wider implications on the relationship between independence in those two fields of mathematics. FUTURE RESEARCH DIRECTIONS On Independence Figure 10 illustrates what we have learned so far about the relations between independence of frames and the various extensions of matroidal independence to semi-modular lattices, in both the upper (left) and lower (right) semi-modular lattice of frames. Only the general case of a collection of more than two non-atomic frames is shown for sake of simplicity: special cases ( Θi = 0F for L* (Θ) , Θi = Θ for L (Θ) ) are also neglected. In the upper semi-modular case, minding the special case in which one of the frames is ˜ itself, independence of frames IF is mutually exclusive with all lattice-theoretic relations I1, I2 and I3 (Theorems 4, 5 and Corollary 1) unless we consider two non-atomic frames, for which IF implies I1 (Theorem 3). In fact they are the negation of each other in the case of atoms of L (Θ) (frames of size n − 1), when I = I1 = I2 = I3 is trivially true for all frames, while IF is never met. The exact relation between I1, I2 and I3 is not yet understood, but we know that the latter imply the former when dealing with pairs. In the lower semi-modular case IF is a stronger condition than both I1* and I2* (Theorems 6, 9). On the other side, notwithstanding the analogy coming from Equation (22), IF is mutually 261 An Algebraic Study of the Notion of Independence of Frames Figure 10. Left: relations between independence of frames IF and all the different extended forms of matroidal independence on the upper semi-modular lattice L (Θ) . Right: relations on the lower semimodular lattice L* (Θ) . exclusive with the third independence relation even in its lower semi-modular incarnation. Some common features emerge: the first two forms of lattice independence are always trivially met by atoms of the related lattice. More, independence of frames and the third form of lattice independence are mutually exclusive in either case. The lower semi-modular case is clearly the most interesting. Indeed, on L (Θ) independence of frames and lattice-theoretic independence are basically unrelated (see Figure 10-left). Their lower-semimodular counterparts, instead, although distinct from IF, have meaningful links with it (right). The knowledge of which collections of frames are I1* , I2* and I*3 tells us much about IF frames, as collections of Boolean independent frames are in ¯ I1* ∩ I2* ∩ I*3 . We know that IF is strictly included in I1* ∩ I , but the possibility that independence of frames * 2 may indeed coincide with I to be explored. * 1 262 ∩ * 2 I ¯ * 3 ∩I is still An Algebraic Solution to the Conflict Problem We can also exploit the analogy between vector spaces and families of compatible frames to conjecture an elegant algebraic solution to the conflict problem. Given a collection of arbitrary elements of a vector space, the well-known Gram-Schmidt algorithm generates a different collection of independent vectors, spanning the same subspace. The ingredients of the algorithm are: 1- the independence condition, and 2- the existence of a projection operator mapping vectors onto linear subspaces. The possibility exists of designing a “pseudo Gram-Schmidt” algorithm which, starting from a given set of belief functions defined over a finite collection of frames (e.g., the discrete feature spaces in the pose estimation problem, Figure 4) would generate a different collection of independent frames belonging to the same family of frames {Θ1, …, Θn } → {Θ'1 … Θ'm } An Algebraic Study of the Notion of Independence of Frames with, in general, m ≠ n , and the same minimal refinement Θ1 ⊗ … ⊗ Θn = Θ '1 ⊗ … ⊗ Θ'm . Once projected the n original b.f.s b1, …, bn onto the new set of frames we would achieve a set of surely combinable belief functions b '1, …, b 'm equivalent, in some sense, to the previous one. We would then be able to combine them on their common refinement: in the pose estimation problem this would allow us to extract an object pose estimate from a set of feature values without resorting to a conflict graph. A formal definition of this equivalence relation needs to be introduced, possibly involving their Dempster’s combination. CONCLUSION In this paper we gave a rather exhaustive description of families of compatible frames in terms of the algebraic structures they form: Boolean subalgebras, upper, and lower semi-modular lattices. Each of those comes with a characteristic form of independence. We compared them with Shafer’s notion of independence of frames, in a pursuit for an algebraic interpretation of independence in the theory of evidence. Even though IF cannot be explained in terms of classical matroidal independence, it possesses interesting relations with its extended forms on semimodular lattices. It turns out that independence of frames is actually opposed to matroidal independence, a rather surprising result. Even though this can be seen as a negative in the original perspective of finding an algebraic solution to the problem of merging conflicting belief functions on non-independent frames, we now understand much better where independence of frames stands from an algebraic point of view. New lines of research remain open, for instance in what concerns an explanation of independence of frames as independence of flats in a geometric lattice (Cuzzolin, 2008). We believe the prosecution of this study could in the future shed some more light on both the nature of independence of sources in the theory of subjective probability, and the relationship between matroidal and Boolean independence in discrete mathematics, pointing out the necessity of a more general, comprehensive definition of this very important notion. REFERENCES Agarwal, A., & Triggs, B. (2006). Recovering 3D human pose from monocular images. IEEE Transactions on PAMI, 28(1), 44–58. doi:10.1109/ TPAMI.2006.21 PMID:16402618 Athitsos, V., Alon, J., Sclaroff, S., & Kollios, G. (2004). Boostmap: A method for efficient approximate similarity rankings. [CVPR.]. Proceedings of CVPR, 04, 268–275. Beutelspacher, A., & Rosenbaum, U. (1998). Projective geometry. Cambridge, UK: Cambridge University Press. Birkhoff, G. (1935). Abstract linear dependence and lattices. American Journal of Mathematics, 57, 800–804. doi:10.2307/2371015 Burman, P. (1989). A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods. Biometrika, 76(3), 503–514. Campos, F., & de Souza, F. M. C. (2005). Extending Dempster-Shafer theory to overcome counter intuitive results. In Proceedings of IEEE NLP-KE (pp. 729-734). IEEE. 263 An Algebraic Study of the Notion of Independence of Frames Carlson, J., & Murphy, R. R. (2005). Use of Dempster-Shafer conflict metric to adapt sensor allocation to unknown environments (Technical report). University of South Florida. Deutsch-McLeish, M. (1990). A study of probabilities and belief functions under conflicting evidence: Comparisons and new method. [IPMU.]. Proceedings of IPMU, 90, 41–49. Cattaneo, M. E. G. V. (2003). Combining belief functions issued from dependent sources. [ISIPTA.]. Proceedings of ISIPTA, 03, 133–147. Dubois, D., & Prade, H. (1992). On the combination of evidence in various mathematical frameworks. In J. Flamm, & T. Luisi (Eds.), Reliability Data Collection and Analysis (pp. 213–241). Academic Press. doi:10.1007/978-94-011-2438-6_13 Cattaneo, M. E. G. V. (2011). Belief functions combination without the assumption of independence of the information sources. International Journal of Approximate Reasoning, 52, 299–315. doi:10.1016/j.ijar.2010.10.006 Cuzzolin, F. (2005). Algebraic structure of the families of compatible frames of discernment. Annals of Mathematics and Artificial Intelligence, 45(1-2), 241–274. doi:10.1007/s10472-0059010-1 Cuzzolin, F. (2008). On the credal structure of consistent probabilities. In Proceedings of JELIA’08. Dresden, Germany: JELIA. Cuzzolin, F. (2008). Boolean and matroidal independence in uncertainty theory. In Proceedings of ISAIM’08. Fort Lauderdale, FL: ISAIM. Cuzzolin, F., & Gong, W. (2013). A belief-theoretical approach to example-based pose estimation. IEEE Transactions on Fuzzy Systems. Dempster, A. P. (1967). Upper and lower probability inferences based on a sample from a finite univariate population. Biometrika, 54, 515–528. PMID:6064013 Dempster, A. P. (1968). Upper and lower probabilities generated by a random closed interval. Annals of Mathematical Statistics, 39, 957–966. doi:10.1214/aoms/1177698328 Dempster, A. P. (1969). Upper and lower probabilities inferences for families of hypothesis with monotone density ratios. Annals of Mathematical Statistics, 40, 953–969. doi:10.1214/ aoms/1177697600 264 Felzenszwalb, P., Girshick, R., McAllester, D., & Ramanan, D. (2010). Object detection with discriminatively trained part based models. IEEE Transactions on PAMI, 32(9), 1627–1645. doi:10.1109/TPAMI.2009.167 PMID:20634557 Harary, F., & Tutte, W. T. (1969). Matroids versus graphs. In The many facets of graph theory - Lecture Notes in Math (Vol. 110, pp. 155–170). Berlin: Springer-Verlag. doi:10.1007/BFb0060114 Josang, A., Daniel, M., & Vannoorenberghe, P. (2003). Strategies for combining conflicting dogmatic beliefs. In Proceedings of FUSION’03 (vol. 2, pp. 1133-1140). FUSION. Kohlas, J., & Monney, P.-A. (1995). A mathematical theory of hints - An approach to the Dempster-Shafer theory of evidence. In Lecture Notes in Economics and Mathematical Systems. Springer-Verlag. Lefevre, E., Colot, O., & Vannoorenberghe, P. (2002). Belief functions combination and conflict management. Information Fusion Journal, 3(2), 149–162. doi:10.1016/S1566-2535(02)00053-2 Liu, W. (2006). Analyzing the degree of conflict among belief functions. Artificial Intelligence, 170(11), 909–924. doi:10.1016/j.artint.2006.05.002 Mac Lane, S. (1938). A lattice formulation for transcendence degrees and p-bases. Duke Mathematical Journal, 4, 455–468. doi:10.1215/ S0012-7094-38-00438-7 An Algebraic Study of the Notion of Independence of Frames McLachlan, G., & Peel, D. (2000). Finite mixture models. Hoboken, NJ: Wiley-Interscience. doi:10.1002/0471721182 Stern, M. (1999). Semimodular lattices. Cambridge, UK: Cambridge University Press. doi:10.1017/CBO9780511665578 Mori, G., & Malik, J. (2006). Recovering 3D human body configurations using shape contexts. IEEE Transactions on PAMI, 28(7), 1052–1062. doi:10.1109/TPAMI.2006.149 PMID:16792095 Szasz, G. (1963). Introduction to lattice theory. New York: Academic Press. Murphy, C. K. (2000). Combining belief functions when evidence conflicts. Decision Support Systems, 29, 1–9. doi:10.1016/S01679236(99)00084-6 Nguyen, H. T. (1978). On random sets and belief functions. Journal of Mathematical Analysis and Applications, 65, 531–542. doi:10.1016/0022247X(78)90161-0 Rosales, R., & Sclaroff, S. (2000). Specialized mappings and the estimation of human body pose from a single image. In Workshop on Human Motion (pp. 19-24). Academic Press. Sentz, K., & Ferson, S. (2002). Combination of evidence in Dempster-Shafer theory. SANDIA Tech. Report, SAND2002-0835. Shafer, G. (1976). A mathematical theory of evidence. Princeton, NJ: Princeton University Press. Shafer, G., Shenoy, P. P., & Mellouli, K. (1987). Propagating belief functions in qualitative Markov trees. International Journal of Approximate Reasoning, 1(4), 349–400. doi:10.1016/0888613X(87)90024-7 Shakhnarovich, G., Viola, P., & Darrell, T. (2003). Fast pose estimation with parameter-sensitive hashing. In Proceedings of ICCV’03. ICCV. Sikorski, R. (1964). Boolean algebras. Berlin: Springer Verlag. Smets, P. (1990). The combination of evidence in the transferable belief models. IEEE Transactions on PAMI, 12, 447–458. doi:10.1109/34.55104 Teichmuller, O. (1936). p-algebren. Deutsche Math., 1, 362–388. van der Waerden, B. L. (1937). Moderne algebra (Vol. 1). Berlin: Springer-Verlag. Whitney, H. (1935). On the abstract properties of linear dependence. American Journal of Mathematics, 57, 509–533. doi:10.2307/2371182 Wierman, M. J. (2001). Measuring conflict in evidence theory. In Proceedings of the Joint 9th IFSA World Congress (vol. 3, pp. 1741-1745). Vancouver, Canada: IFSA. Yager, R. R. (1987). On the Dempster-Shafer framework and new combination rules. Information Sciences, 41, 93–138. doi:10.1016/00200255(87)90007-7 Zadeh, L. (1986). A simple view of the DempsterShafer theory of evidence and its implication for the rule of combination. AI Magazine, 7(2), 85–90. KEY TERMS AND DEFINITIONS Belief Function: A non-additive measure, it generalizes standard probability measures; mathematically is described by a random set. Conflict: Two belief functions are said to conflict when they do not admit Dempster’s combination. Dempster’s Rule: A generalization of Bayes’ rule, allows us to combine belief functions generated by independent sources of evidence. Frame: The finite domain of a belief function. Independent Frames: Collections of frames which are independent as Boolean sub-algebras of their common refinement. 265 An Algebraic Study of the Notion of Independence of Frames Lattice: A partially ordered element in which all elements admit both inf and sup. Matroid: A set endowed with a collection of independent subsets. Pose Estimation: The problem of inferring the configuration or “pose” of an articulated object from one or more images. Semi-Modular Lattice: A lattice in which if an element covers the inf, the sup covers the other element or vice-versa. Families of compatible frames are semi-modular lattices. 266 An Algebraic Study of the Notion of Independence of Frames APPENDIX Definition 7. A non-empty collection of finite non-empty sets F is a family of compatible frames of discernment (Shafer, 1976; pages 121-125) with refinings R , where R is a non-empty collection of refinings between pairs of frames in F , if F and R meet the following requirements: Θ Θ Θ Θ 1. Composition of Refinings: If ρ1 : 2 1 → 2 2 and ρ2 : 2 2 → 2 3 are in R , then ρ1 ρ2 ∈ R . ' ' Θ Θ 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 . ' ' 3. Identity of Refinings: If ρ1 : 2Θ → 2Θ and ρ2 : 2Θ → 2Θ are in R , then ρ1 = ρ2 . 4. Existence of Coarsenings: If Θ ∈ F and A1, …, An is a disjoint partition of Θ , then there is a coarsening ˜ ' of Θ in F which corresponds to this partition, i.e. ∀Ai there exists an element of Θ ' whose image under the appropriate refining is Ai . ' 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. 6. Existence of Common Refinements: every pair of elements in F has a common refinement in F . Definition 8: A Boolean algebra is a non-empty set B provided with three internal operations ∩ : ∪ : ¬ B×B → B A, B A∩B B×B → B A, B A∪B : B → B A ¬A called respectively meet, join and complement, characterized by the following properties: A∪B = B ∪A, A∩B = B ∩A; (A1) A∪ (B ∪C ) = (A∪B ) ∪C , A∩ (B ∩C ) = (A∩B ) ∩C ; (A2) 267 An Algebraic Study of the Notion of Independence of Frames (A∩B ) ∪B = B, (A∪B ) ∩B = B; (A3) A∩ (B ∪C ) = (A∩B ) ∪(A∩C ), A∪ (B ∩C ) = (A∪B ) ∩(A∪C ); (A4) (A∩¬A) ∪B = B, (A∪¬A) ∩B = B. (A5) ' For instance, the power set 2Θ of a set Θ is a Boolean algebra. X = 2Θ with Θ' a disjoint partition of Θ is then a Boolean sub-algebra (Sikorski, 1964) of 2Θ . A collection of compatible frames {Θ1, …, Θn } Θ Θ Θ1 ⊗…⊗Θn corresponds then to a collection of Boolean sub-algebras {2 1 , …, 2 n } of the power set 2 their minimal refinement Θ1 ⊗ … ⊗ Θn . Now, a collection of Boolean sub-algebras X1, …, X n is independent (IB) if ∩A i i ≠∧ ∀Ai ∈ X i , where ∧ ∩B is the initial element of the Boolean algebra B . For a collection of compatible frames (23) is expressed as (3). 268 of

© Copyright 2020