Mathematics of Data Fusion

One of the long-time goals in both engineering and everyday life activities has been the efficient use and combination of all available and relevant information. Typically, such evidence involves various types of uncertainty which must be utilized in order to make good decisions. Technically speaking, the methodologies involved in accomplishing the above goal has been given a variety of names including: “data fusion”, “information fusion”, “combination of evidence”, and “synthesis of observations’ Data fusion or information fusion are names which have been primarily assigned to military-oriented problems. In military applications, typical data fusion problems are: multisensor, multitarget detection, object identification, tracking, threat assessment, mission assessment and mission planning, among many others. However, it is clear that the basic underlying concepts underlying such fusion procedures can often be used in nonmilitary applications as well. The purpose of this book is twofold: First, to point out present gaps in the way data fusion problems are conceptually treated. Second, to address this issue, by exhibiting mathematical tools which treat combination of evidence in the presence of uncertainty in a more systematic and comprehensive way. These techniques are based essentially on two novel ideas relating to probability theory: the newly developed fields of random set theory and conditional and relational event algebra.

Data fusion, or information fusion as it is also known, is the name which has been attached to a variety of interrelated problems arising primarily in military applications. Condensed into a single statement, data fusion might be defined thusly:

Locate and identify an unknown number of unknown objects of many different types on the basis of different kinds of evidence. This evidence is collected on an ongoing basis by many possibly re-allocatable sensors having varying capabilities. Analyze the results in such a way as to supply local and over-all assessments of the significance of a scenario and to determine proper responses based on those assessments.

This chapter is devoted to theoretical aspects of random sets. It is intended to provide information about set-valued random elements within probability theory. The writing of this chapter is tutorial in nature. Readers who are interested only in applications of random sets might skip this chapter without discontinuities. The applications of random set theory to data fusion problems will be treated in subsequent chapters of this Part II of the book, in which additional materials on theoretical issues of random sets will be incorporated at appropriate places. Also, to make the reading of applied issues easier, we choose to recall the basics of random set theory when necessary. Incorporating this freedom of choice has led to some redundancy, mostly in definitions, which may be beneficial.

In this and the four chapters which follow, we develop the random set approach to data fusion summarized in Section 2.5 of Chapter 2. This chapter sets the stage by developing the mathematical cornerstone of this approach: the concept of a finite random set. The necessary mathematical preliminaries—topological spaces of finite sets, hybrid discrete-continuous spaces and hybrid integrals, etc.—are set forth in Section 4.1. Section 4.2 introduces the set integral and the set derivative. The concepts of finite random subset, absolutely continuous finite random subset, and global density of an absolutely continuous finite random subset, are explored in Section 4.3.

The purpose of this chapter is to extend the basic elements of practical statistics to multisensor, multitarget data fusion. Specifically, in section 5.1 we show that the basic concepts of elementary statistics—expectations, covariances, prior and posterior densities, etc.—have direct analogs in the multisensor, multitarget realm. In section 5.2 we show how the basic elements of parametric estimation theory—maximum likelihood estimator (MLE), maximum a posteriori estimator (MAPE), Bayes estimators, etc.—lead to fully integrated Level 1 fusion algorithms. That is, they lead to algorithms in which the numbers, I.D.s, and kinematics of multiple targets are estimated simultaneously without any attempt to estimate optimal report-to-track assignments. In particular, we show that two such fully integrated algorithms (analogs of the MLE and MAPE) are statistically consistent. The chapter concludes with section 5.3, in which we prove a Cramér-Rao inequality for multisensor, multitarget problems. The significance of this inequality is that it sets best-possible-theoretical-performance bounds for certain kinds of data fusion algorithms.

In this chapter we describe the basic elements of a unified approach to data fusion, assuming that observations are unambiguous (the approach will be generalized to include ambiguous observations in the next chapter). Section 6.1 briefly describes the basic problem under consideration. Section 6.2 describes how random set techniques can be used to derive measurement models for entire sensor suites, and prior knowledge in data fusion is discussed in Section 6.3. Section 6.4 describes “global” motion models and “global” discrete-time recursive Bayesian nonlinear filtering, and how they can be used to fuse data generated by dynamic targets. The problem of determining global densities for the output of a data fusion algorithm is considered in Section 6.5, which specific application to multihypothesis-type algorithms. The chapter concludes with three detailed, simple examples in Section 6.6.

In the previous chapter we showed how the theory of finite random sets can be used to reformulate multisensor, multitarget estimation problems as single-sensor, single-target problems. We then showed how this fact allowed us to directly generalize conventional and very well understood “Statistics 101” techniques to multisensor, multitarget estimation problems. It nevertheless could be argued that the random set formulation is just a fancy “bookkeeping” scheme which introduces complication while adding little value over, for example, more familiar vector-oriented approaches. In this chapter we turn to two problems which are difficult to attack using any approach other than random set theory:

The term performance evaluation in data fusion refers to problems of the following kind:

The issue considered here is concerned with the analysis and combination of certain multi-source information which has some degree of uncertainty attached to it. When the uncertainty corresponding to each source is provided via the probability of a single unconditional event, standard probability and statistics techniques are adequate for dealing with the problem. However, it often arises that uncertainty is not provided in such a format. This can happen, e.g., when information is supplied initially through natural language descriptions which are then converted to fuzzy logic. Another occurrence is when weighted combinations, or appropriate nonlinear functions, of probabilities of contributing simpler events represent the degree of uncertainty. In such cases it is not obvious initially how to represent (or even whether such a representation is possible for) the uncertainty as a probability evaluation of a legitimate event. Further details of the problem considered here are presented in the next section. Two excellent treatments on the general topic of data fusion which not only survey various statistical and probabilistic techniques, but also consider nonstandard approaches, including fuzzy logic and Dempster-Shafer theory, may be found in Hall [7] and Waltz and Llinas [14]. However, these texts, as well as the bulk of the current approaches to data fusion and combination of evidence problems, have not addressed the problems stated above. Because the tools used in dealing with these issues, conditional and relational event algebra, lie outside of the mainstream development of probability, as well as the current development of fuzzy logic and other areas, most readers of this text, even with a strong background in probability, will find the concepts introduced here, at first, quite unfamiliar. Consequently, the approach taken here is to subdivide the topic interest through the introduction of a number of motivating examples which also show how conditional and relational event algebra can be used to address them.

Because conditional event algebra is actually a special case of relational event algebra and is needed for the development of the latter, we present here an illustrative example of its use.

Conditional event algebra(s) can be roughly divided into two camps: boolean and non-boolean. (Again, see the above definitions.) It appears that of the many possible conditional event algebras possible — and proposed, so far — three stand out in their significance for possible applications. All three have a number of common desirable properties — and a fundamental link concerning deduction (elaborated upon in Section 13.1), but each also has certain desirable and negative properties, the others do not possess. Two of these are non-boolean, while the third is boolean.

For purposes of both self-containment and in order to show a new more improved approach to this product space algebra, we present a number of key results which also may be found in Goodman and Nguyen [1], [2], but with streamlined proofs here:

So far the only connections between PS, DGNW, and AC have been through those properties that are shared (or those properties they differ on). In Section 11.6, we mentioned that McGee, independently, in effect, obtained the PS logical operations without explicitly recognizing the form of the conditional events themselves. Extending McGee’s work, Goodman and Nguyen have also shown relations between DGNW and PS via “fixed point” evaluation of the third or indeterminate value for the three-valued (min,max) logic corresponding to DGNW. (See [3],Section 4.)

As we have stated previously, the standard development of probability theory and applications has been overwhelmingly numerically-oriented. Algebraic aspects, when involved, are still fundamentally directed toward numerical optimization criteria, such as the well-developed areas of transformation group-invariant estimation and hypotheses testing. In fact, the very foundations of modern information theory is almost entirely numerically-based as e.g. in [7]. This is not only borne out by any survey of the general literature, but also by considering any of the leading efforts devoted to combining or comparison of evidence, such as in [8] or the survey [2]. In this chapter we concentrate on determining a fundamentally more algebraically-oriented approach to the problem of testing hypotheses for the distinctness of events and related similarity issues — in the sense of “algebraic metrics” which replace, but are compatible with, all probability evaluations and numerical metrics (see Sections 14.6 and 14.7). This allows us to discover additional probability distance functions (d _P,3 and d _P,4), one of which (d _P,3) is apparently superior in a number of ways to the traditional one (d _P,2). (See Section 14.8.) PS cea is seen to play a major role in the above results. Preliminary aspects of this work can be found in [3].

In this case, two expert observers independently (or perhaps with some coordination or influence) provide their opinions concerning the same situation of interest: namely the description of an enemy ship relative to length and visible weaponry of a certain type. Suppose that Experts 1 and 2 have stated the following information which is obviously already intermingled with uncertainty: