FUZZY PARTITIONS II: BELIEF FUNCTIONS a Probabilistic View
Belief Functions
Fuzzy Partitions II: Belief Functions A Probabilistic View
T. Y. Lin
Department of Mathematics and Computer Science, San Jose State University,
San Jose, California 95192 , USA
1 Introduction
One of the very first counter intuitive parts of belief function is its definition, it takes a simple minded "direct" sum of the measures of focal elements. In this computation the measures of the intersections are ignored. As a consequence atomic intersections of focal elements (the intersection contains no other focal elements) have zero belief measure. One may wander: Is belief function a reasonable and mathematically sound measure? Our answer is yes. Belief functions can be viewed as a generalization of random variables, however, the generalization sounds too "naïve" in the first impression: In classical theory, the inner probability is the least upper bound of the “direct” sum of the probabilities of all masses. Belief functions adopt the same definition; it is, the least upper bound of the “direct” sum of the basic probabilities of all focal elements. Indeed, they are the same, however, in classical theory all masses are disjoints, while focal elements may not. The goal of this paper is to show that in spite of these, belief functions are sound measures.
Since [7], we have been searching for a "correct" view of belief functions. In that paper, we successfully express the belief functions in terms of probabilistic multi-valued random variables. In [6], we also examine the belief function from the point of view of information granulation. We show belief functions are granular in the sense that they are functions on the level of granules (focal elements); a belief function is a “pullback” of a classical probability on the ring of power set that consists of those names of focal elements. Implicitly however the theory does assume that the names of focal elements are semantically independent. In the present paper, we explicitly express such an assumption in terms of granular fuzzy sets [3], [4]. A granular fuzzy set has a crisp set representations. So the disjoint-ness becomes an unambiguous notion. In terms of such notion "semantic independent" can be expressed precisely and formally. In this paper, we view the basic probability assignments of focal elements as assignments to some fuzzy sets; focal elements are merely their supports. Furthermore these fuzzy sets are mutually disjoint, even though their supports may intersects. This new view, we believe, provides a well-defined theory of belief functions. If one treats membership functions and fuzzy sets as synonyms [11], then the belief function on fuzzy sets are distributions (generalized functions).
------This research is partially supported by Electric Power Research Institute, Palo Alto, California, San Jose State University, Amdhal Corporation, NASA Grant NCC2-275, ONR Grant N00014-96-1-0556, LLNL Grant 442427-26449, ARO Grant DAAH04-961-0341, and BISC Program of UC Berkeley
Belief Functions
2 Discrete Random Variables
Mathematically a random variable is a real valued function whose numerical values is determined by chance. In this section, we will examine the classical random variables from the point of view of belief functions. Let (C, , Pr) be a probability space, where C is the universe, is a -algebra, and Pr is a probability measure [2]; we will be interested in the case C is a finite set.
2.1. Suppose C is a finite set. A real-valued function X: C R, is a measurable function, if all its inverse images are measurable (this definition is equivalent to that of [2] only when C is finite). Let the set of distinct values be S = {a1, a2,…, an}. We will be interested in the inverse image X-1(ai) of ai under X; for convenience we will write
Xi = X-1(ai)={c | c C and X(c)= ai }
By abuse of notation, we also use X to denote the collection of inverse images
X = {Xi : i = 1, 2, …, n}
So X is a random variable as well as the collection of inverse images, which forms a partition on U. The collection X generates a -algebra (X) .
2.3. A new probability PX can thus be defined by setting PX(Xi) = Pr(Xi), and extending it to (X) additively, namely, for Y = jXj,
PX(Y) = j PX(Xj ), where j varies through a finite subset of {1, 2, .. , n}.
In particular, the total sum PX(C) = ni=1 PX(Xi) =1. So (C, (X), PX) is a new probability space.
2.4. The inner probability can be expressed by
PX*(A) = SUP{j PX(Yj ) | A Y= jYj and Yj X},
where SUP is the least upper bound.
2.5. So given a random variable, we have
(S1) a partition X on C, and
(S2) a numerical value, m(Xi )=PX(Xi ), i = 1, 2, …, n, such that
(S3)ni=1 m(Xi) =1.
and the inner X-probability is the belief function.
Bel(A) = PX*(A)= SUP{j m(Yj) | A Y= jYj and Yj X}
It is clear Shafer theory is a generalization of random variables, in which (S1) is weaken to a partial covering, yet the theory computes belief functions as if X is disjoint. This observation spells out the precise point of our motivation in re-interpreting Shafer theory. The main goal of this paper is to re-interpret the notion of focal elements: even though they appear to have non-empty intersections, their basic probability assignments are, in fact, "measures" of disjoint fuzzy sets. Focal elements are merely the support of these fuzzy sets.
2.6. Let A be any subset of C. The lower and upper approximation are defined by
L[A]= {Yj X: Yj A}; H[A] = {Yj X: Yj , Yj A 0}
It is clear that L[A] (X), and we have
Proposition BelX(A) = PX*(A) = PX(L[A])
Similar results, mainly on concrete counting measures, are obtained by many rough setters; e.g. see [9] for references and exposition. There are generalizations: In [10] and [11], we established the results for binary neighborhood systems (generalized rough sets for binary relations), in [6], we established further. The approximations, however, are not in the "usual sense," they are approximated in the level of concepts. We should point out that "direct" generalizations are invalid; see 3.5 in next section.
3 Belief Functions -- Shafer Theory
Let be a finite set and2 be its power set. A unit interval valued function
m : 2 [0, 1], is a basic probability assignment(bpa) if
m(0) = ( is empty set) and
nm(En) =1, where En varies through 2.
A set En is a focal element, if m(En) 0.
3.2. Belief function Bel can be defined by basic probabilities:
Bel (A) = {m(B), B A}, where the summation runs through all subset of A.
3.3. Let C = {1, 2, 3, 4, 5, 6, 7, 8}. Two focal elements and their bpa's are
X={1,2,3,4,5} and Y={2,3,4,5,6};
m(X)= 2/3, m(Y)= 1/3, and other bpa's are zero.
Then, by definition,
Bel(X) = 2/3, Bel(Y) =1/3, and Bel(X Y)=0.
The belief measure of atomic intersection is zero; an intersection is called atomic if it does not contains any focal element. Intuitively, it implies that the evidences of any two atomic events are always “independent;” atomic event is an event that has no sub-events with positive evidences.
3.5. Let C ={1, 2, 3, 4, 5} be the universe. Let B be a binary relation B C C, which is defined by
B1= { x | (x , 1) B} = {1, 2, 3}
B2= { x | (x , 2) B} = B3 = { x | (x , 3) B}={1, 2, 3, 4}
B4={ x | (x , 4) B} ={2, 3, 4}, B5= { x | (x , 5) B} =
Each Bi consists of those points that are B-related to the element i; they are referred to as elementary B-neighborhoods. We will show that "direct" generalizations are invalid: Let (B) be the -ring generated by {B1, B2, B3, B4, B5}. Suppose a measure is defined on (B) as follows:
PrB(B1) = PrB(B4) = 3/10, PrB(B2) = PrB(B3) = 2/5, PrB(B5)= 0.
Its inner measure is:
PrB*[{1, 2, 3, 4, 5}] = SUP{PrB(B1B4B5), PrB(B2B5), PrB(B3B5)
= SUP{PrB(B1B4), PrB(B2), PrB(B3)}=2/5, since B5= .
Next, we take the measure of Bi as bpa 's,
mB(Bi)= PrB(Bi), i=1, 2, 3, 4, and other bpa's are zero,
and we have
BelB({1, 2, 3, 4, 5}) = mB({1, 2, 3})+ mB({2, 3, 4}}+ mB({1, 2, 3, 4})
= PrB(B1)+ PrB(B4)+ PrB(B1{4}) = 1
The difference is resulted from that believe value sums up the multiple measures of the overlapping areas; B1 is measured twice in believe value, only once in the inner probability. The question then is: Is multiple count of common area essential to human belief? Our proposal is that bpa's should not be interpret as measurements of focal elements, they are measurements of fuzzy sets whose supports are focal elements. With such interpretations, belief functions are the inner probabilities of granular fuzzy sets; this is the subject of next section.
4 Belief Functions A New View
4.1. Suppose we are given a bpa, m : 2C [0, 1]. Let Yi : i = 1, 2, …, s be the focal elements. Let i be the characteristic function of Yi. Then we define our target membership functions (fuzzy sets and membership functions are synonyms) by
(1)TYi(c)= m(Yi)i(c), i = 1, 2, .., s.
We write n = s+1 and define:TYn(c) = 1 si=1 TYi(c) , or equivalently,
(2)ni=1 TYi(c) = 1.
It is clear that TYn(c) 0; it is a legitimate membership function. Next we set bpa of TYi, i= 1, 2, …, n:
(3) m(TYi) = m (Yi), i = 1, 2, .., s, and m(TYn) = 0.
(4) ni=1 m(TYi) = si=1 m(Yi)i(c) + m(TYn) =1
4.2. Let us recall the notion of fuzzy partitions introduced in [1].A family of fuzzy sets FXi, i = 1, 2, …, t is said to be a BH- partition, if ti=1 FXi,(c) =1
Proposition {TYi | i = 1, 2, .., n} is a BH-partition.
4.3. Based on the notion of contexts and granular fuzzy sets [3], [4], we introduced the notion partition for granular fuzzy sets. In [5], we show that under a nice context, a BH-partition can be realized by a crisp partition in the context. In this paper, we will construct a very specific crisp partition directly. Let U = C [0, 1] and be called the total space [5]. Consider the natural projection NP: U C. We will show that there is a crisp partition {Xi} on U such that
TYi(c) = ([c] Xi ) / ([c]) = ([c] Xi )
where [c]= c [0, 1], and (c S)=(S) is the Lesbegue measure of S [0,1]. Given a membership function TYi we will define Xi as follows: At each point c C, we set c0 = 0, cn =1. For i = 1, 2,.. , n, we define half-open intervals,
Ic = [ci, ci+1) such that TYi(c) = ci ci-1, and set
Xi = c { c [ci-1, ci) : c C}
Such an Xi is called a realization of TYi ; it is a crisp set representation of a fuzzy set TYi . The 6-tuple
(U, NP, C, , {TYi: i = 1, 2,.. , n}, {Xi:i = 1, 2,.. , n})
is called the context of {TYi:i = 1, 2,.. , n}. Since ni=1 TYi(c) = 1,
Ic = {[ci-1, ci) : i =1 , 2, …, n} is a crisp partition on [0, 1], and
X = {Xi : i = 1, 2, …, n} is a crisp partition on U= C [0, 1].
So,we have
(S1) a partition X = {Xi : i = 1, 2, …, n}on U, and
(S2) a numerical value, m(Xi ) m(TYi) =m(Yi), i = 1, 2, …, n, such that
(S3) ni=1 m(Xi) =1
These three conditions clearly say that X can be treated as a random variable on the total space U. Next, we will define a belief function on C by X.
BelX(A [0, 1]) = PX*(A [0, 1]) = SUP{j m(Xj) | A [0, 1] jXj }
Observe that A [0, 1] jXj if and only if A jYj , so, we have
PX*(A [0, 1]) = SUP{j m(Xj) | A [0, 1] jXj }
= SUP{j m(Yj) | A jYj }= BelY(A)
So we have define BelY(A) in terms of the probability PX of random variable X. Therefore BelY is a well-defined set function.
5 Conclusions
The definition of belief functions sounds like a "too naïve" generalization of the probability theory of random variables. In this paper, we show that we can view the bpa of focal elements as probabilities of fuzzy sets that have those focal element as their supports. Using the notion of granular fuzzy sets [3], [4], these fuzzy sets on base space C can be realized by crisp sets on the total space U. Thus we have the setting of classical random variables on the total space. We show that the belief functions of fuzzy sets on C are the inner probabilities of the random variables on U. So belief functions is a sound and well-defined set function. These findings also imply that we can introduce an additive fuzzy measure theory; this will be reported in near future.
References
1. Bezdek, J. and Harris, J. (1978) Fuzzy Partitions and Relations: An Axiomatic Basis for Clustering, Fuzzy Sets and Systems 1, 112-127, 1978
2. Halmos, P. (1950), Measure Theory, Van Nostrand, 1950.
3. Lin, T. Y. (1997), Rough Sets, Fuzzy Sets and Their Interactions. In: Proceedings of Fifth National Conferences on Fuzzy Theory and Applications (Fuzzy 97), Dec 19-20, Tainan, Taiwan, 1997
4. Lin, T. Y. (1998a), Sets with Partial Memberships. In: Proceedings of 1998 IEEE World Congress on Computational Intelligence, Anchorage, Alaska, May 4-9, 1998
5. Lin, T. Y. (1998b) Fuzzy Partitions I: Rough Sets, In : Proceedings of the Seventh Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, July 6 - 10, Paris, France, 1998
6. Lin, T. Y.(1998c) Granular Computing of Binary relations II: Rough Set Representation and Belief Functions. In: Rough Sets and Knowledge Discovery, Polkowski and Skowron (eds), Springer-Verlag, 1998 (to appear).
7. Lin, T. Y. and Liau, C. J. (1997) Belief Functions Based on Probabilistic Multivalued Random Variables. In: Proceedings of Joint Conference of Information Science, Research Triangle Park, North Carolina, March 1-5, 1997, 269-272.
8. Lin, T. Y. and Yao, Y. Y., Neighborhoods Systems and Belief Functions Proceedings of The Fourth Workshop on Rough Sets, Fuzzy Sets and Machine Discovery, Tokyo, Japan, November 8-10,1996, 202-207.
9. Skowron A., and Grzymala-Busse, J.W., (1994), From rough set theory to evidence theory. In: Advances in the Dempster Shafer Theory of Evidence, R.R Yaeger, M. Fedrizzi and J. Kacprzyk (eds.), John Wiley & Sons, Inc., New York, Chichester, Brisbane, Toronto, Singapore, 193--236.
10. Yao and Lingras (1998, Interpretations of belief functions in the theory of rough sets. Information Sciences, Vol. 104, No. 1-2, pp. 81-106, 1998)
11. .Zadeh, L. A.(1965), Fuzzy sets, Information and Control, 8, 338-353, 1965.
Tsau Young (T. Y.) Lin received his Ph.D from Yale University, and now is a Professor at San Jose State University, also a visiting scholar at BISC, University of California-Berkeley. He is the founding president of international rough set society. He has served as the chairs, co-chairs, and members of program committees in many conferences. He is an editor and a member of editorial board in several international journals. His interests include approximation theory (in database retrievals and reasoning), data mining, data security, data warehouse, fuzzy sets, intelligent control, non classical logic, Petri nets, and rough sets (alphabetical order).