Approximation of Indistinct Concepts

ABSTRACT

This theory on seai-equivalence relations is an iaportant and useful tool for investigating classification, pattern recognition, polling and inference etc. Based on it, this paper presents a new fraaeworlc, in which an indistinct concept, that is one with incoaptete or undeterained inforaation about the objects, can be represented approxiaately. Such an approxiaate representation will reflect deep structures of concepts which are aeaningful for the systea. Clearly, the work we present here is to a great extent inspired by general discussions of knowLedge engineering research. The theory developed here seeas to be of interest in knowledge representation and natural language processing. Froa the iapleaentation point of view, this theory can be realized by various AI techniques.

0. INTRODUCTION

Two aajor issues of knowledge engineering are representation and utilization of knowledge . Following Ortowslca and Pawlak [I] , anything that can be spoken about in the subject position of a natural language sentence is an object, properties of which are fundaaental eteaents of the knowledge of a given doaain; then concepts are aore coaplex eleaents of knowledge. This gives the possibilities of representing the concepts related to a given doaain. To represent indistinct concepts--the inforaation about a set of the objects represented by such a concept is undeterained or incoaplete in a sense, --Pawlak [ 2] introduced the rough sets

APPROXIMATION OF INDISTINCT CONCEPTS Zhang Ningyi Institute of Applied Matheaatics Guizhou Acadeay of Sciences 40 East Yanan Road , Guiyang, China <Coapleted March, 1987.)

concepts defined by union of soae equivalent classes of an equivalence relation. Unfortunately, in aany real situations it is not sufficient to consider equivalence relation only. In fact. a tot of relations deterained by the attributes of objects do not satisfy transitivity. This Lisits the expressive power of rough sets.

The Preceding fact forced us to extend Pawlak' s works. Seai-equivalence nilation theory [3] just offers one of the possible research directions in this field. The original idea of the theory was suggested by Poincare'. Wu Xueaou and his colleagues have established and developed the theory [3], [4). In its fraaework, we give interior and exterior approxiaations of indistinct concepts respectively . Its gradual approxiaations defined in teras of a faaily of seai-equivatence relations are at so given in it. Such approxiaate representations witt reflect deep structures of concepts and iaprove the expressive power of Pawlak's knowledge representation systea. The work we present in this paper provides a powerful toot for incoaptete knowledge representation and utilization, and deve tops soae new researches in AI, e. g. pat tern recognition, au touted deduction, search aethods, etc. --these will be discussed in other papers.

I. PRELININARIES

In this paper, we will use ataost the saae terainology and notations as in [4] . First, we will give a brief account of relations. seai-equivalence

Definition I. I [3] A <binary) relation 6 on a noneapty set 6 is catted a seai-equivalence relation if the following condi lions hold for any a , b and c in G,

1. a o a ( reftexivi ty)

2. a o b = ) b o a ( s yaae try).

If it further satisfies

3 . a o b and b 6 c = ) a o c ( t ran s i t i vi t y) then we call 6 an equivalence relation.

Let Es [G] = { o, o is a seai-equivatence relation on G)

E [ G ] = { E, E is an equivalence relation on G) Obviously, E [�]~Es [G]

Theorea 1. I [4] <Es[G], U, n> is a coaplete lattice, where G' (coaplete relation) is the greatest eteaent and I (equality relation) is the least eleaent.

Lena 1.1 [4] <E [G] , n > is a coaplete tower seai-tattice. E [G] does not close under U, but ( E [ G] · < ) i s a c oap l e t e l at t i c e.

Defini lion I. 2 For any o E Es [G] and any given aE G, we call the set (b,a o b, bE G) a relative class of a to 6. in syabot [a] 1 = { b , a 6 b, bEG . The faaily of sets {[a] 11 a E G ) is catted a relative quotient set of G and is denoted as G 1 ·

Defini lion I. 3 [ 3] For o E Es [G] , a set Qli: G with Q'so.aaxiaal with respect to inctusio~ Q=aax(As;:G, A' € o)

is a seai - equivalence class of G relative to o ; a faai ly of sets {Q,Q is a seai-equivalence class of G relative to o) is the seai-equivatence quotient set of G relative to o and is denoted as G,-6.

Froa the above definition, it is easy to verify the following facts .

Corollary !.!If 6 E E[G] and a E Q E G/ o,then [a] 1 = Q, for each a E G.

Corollary I. 2 For any Q E G,- 6, if a E Q, then Q S [a].. Therefore, (G/ 6j<jG61< jGj.

<Here [A I denotes the cardinal of A, for any set A ). Theorea I. 2 For any a E G, there is b E G such that a E [b] there also is Q E G/ 6 such that a E Q.

Theorea I . 3 For any 6 E Es [G] · a, b, c E G, I. b E [a], iff a 6 b

2. b E Q E G-' 6 iff 'V c E Q => b o c

3. 'q Q E G/ o, the restriction o I Q of o to Q is an equivalence relation on Q.

The proofs of theorea 1. 2 and 1.3 are trival .

Theorea I. 4 [3] [4] U,,. [a],- G, U G/ o = G.

Theorea I. 5 For any o E Es [G] ,

U,..,l Q' = U,., [a]',

Proof. Iaaediate.

Definition 1. 3 Let I be an index set . Suppose for any i E I, o i E Es [Gi] . Define o = II 6 i S II Gi X II Gi as follows,

-+ ~ .... < a,b > E o iff< ai, bi > E oi for any1,b E II Gi and each i E I, where a;_, bi is ~ -+ i - th coaponent of a and b respectively.

Theorea 1.6 [3] For o = II o i E Es [II Gi], we have

Reaark. If o i E E [ G i] , then the still hold and are transforaed above facts into ones corresponding to the theory on the equivalence relations. Further discussions on these works are given in [3] · [ 4]

2. APPROXIMATE DEFINABILITY

In general, we are not able to distinguish all the objects by aeans of properties of these objects, · inforaations about which are incoaplete or undeterained . To deal with such cases we introduce notions of approxiaate definabilities of sets. Defini lions and inferences, introduced in this and the next sections, are applied to that case in which G =U{Qi,QiEG/ o, i E I).

Defini lion 2. I For any given o E Es [G] , a set ASG is o - definable, if there is Io ~I such that A =UIQi,i E I 0 1, where G=U(Qi,QiEG/ o,iEII. Denote Def [G] =(A, A ~ G and A is 6 -definable ).

Clearly, both the eapt y set and the universal set G are o -definable. By the defini lion we easily obtain,

Theorem 2. I <Def [G] , U) is a coaplete upper seai-lattice . In general, Def [G] is not closed under n or c, where u, n, c are union, intersection and coapteaent respectively .

Defini lion 2. 2 A set G is o -selective iff any Q E G,- o is a set containing a single eleaent.

Corollary 2.1 A set G is o -selective iff any AS.G is o -definable.

Proof. => 1 Since any set Q E G/ 6 contains only

• Q single ele·ent, so 6 is an equati ty relation on G. It !·plies Def [G] = {A,A=G}. Therefore, any AS:. G is 6 -definable .

¢: 1 By hypothesis {a} E Def [G] holds for any a E G. I t i ·P lies G/ 6 = { (a}, a E G}.

Defini tion2. 3 For any 6 E Es [G] , A~�, we say that ...

1. the set A= n {B,A~B , BE Def [G] } is an exterior approxi·ation of set A, and the set != U {B,B5A, BE Def [G] } is an interior one;
2. a set A is approxiutety6 -definable if A::;t:G and !::;t:¢ 1

3. a set A is internally 6 -nondefinable if,!=¢, and A is externally 6 -nondefinable if A= G. A is totally 6- nondefinable if A=~ and A= G.

Roughly speaking, 6 -definabi ti ty gives us a possibility to answer such ·e·bership question as x 1E A precisely. Approxiute definabi li ty enables us to decide that an ete·ent x ·ore definitely belongs to A or not to A; or is in the borderline case, which depends on the infor·ation provided by the objects.

Theore· 2. 2 For 6 E Es [G] , ASG, we have,

I. A is 6 -definable iff A =A= A

1. A~B=) ASB, !~~,
2. !. = < A > = ~ A = A Si.J...l
3. A U B = A U B, ~ = .!._ U !:_

Proof. We should prove ~ = A_U _! as an exa·ple only. The others are trival.

By definition 2. 3, it is clear that

!'=A, !SB =>! U _!c;A U B=>!_ U!S'~.

On the other hand, we suppose A n B =¢without loss of generality, and let J be a subset of I such that ~ = U { Qj , Qj E G/ 6 , J E J ) Then AUB$AUB =)U{Qj,jEJ'lSA, U{ Qj,jEl"lSB, where J' U J'' = J .

Therefore, A U B = A U B ---

Exa·ple 2. 1. Let us consider a set G, which consists of six people . Let o be a re tat ion on G such that

oi, o ;}- ) E o i f f with each other, for any o;.and o.}are fuitiar i , j E { 1, 2, 3, 4, 5, 6 l.

The relation 6 is defined by the following table,

where if oi 6 oa- then write I on the crossed point of i-th line and j-th co tun, otherwise write 0. So, we get G/ 6 ={{ o,, o,}, {o, ,o, ,o,),(o, ,o,)) For A= ( o, , o , , o,), we have A = { o, , o, , o,}, !_= {o, , o,)

3. GRADUAL APPROXIMATIONS OF INDISTINCT CONCEPTS

By theore· 1.1 <Es [G] , U, n > is a co·ptete lattice. For the sake of convenience, let <1 , V, 1\) be such an algebra that the following conditions are held,

o i n o j = o k i u i v j = k,

for any i, j, k EJ,oi, oj, 6kE Es [G] . In particular, 6 0 is a co·ptete relation on G, o 1 is an equality relation on G where 0 and 1 are the least and the greatest ele·ents of J respectively.

We consider a fa·ily of relations { o k, kE K~J ) 5 Es [G] . Without toss of generality, we suppose that { 6 k, k E K } is a ·onotone decreasing sequence, by which gradual approxi·ations of the indistict concepts will be established.

Definition 3. I For any E K, a function fi, G'--4{ 0, I) C::J is defined by

for both a and b in G.

Definition 3. 2 A function f,�'~X is defined by f ( a, b) = V { < f f < a, b) 1\ i ) , i E K)

And let o c;.G' be a relation such that f ( a,b) ) 0, for any a,b in G . a o b iff

if < a, b > E o i

otherwise Leaaa 3. 1 For any i, j E K if i ( j then fi. < a, b > > f t< a, b >, "V a, b E G.

Proof. Iaaediate froa aonotony of ( 6 k,k E){> and - definition 3. 1

Theorea 3.1 6=U(6i,iE](} E Es [G]

Proof. For all a, b in G.

<a, b) E 6 ( = ) f< a, b) 0

• (=)~i.EK,f,. <a,b)/\i)O
• ( = ) 3 i, E K, f,. < a, b) = 1 and i ) 0
• ( = ) <a, b > E U ( 6 i, i E K}.

It is now evident that S E Es [G] .

Leaaa 3. 2 If 'A.,6 EEs [G), and A.<6, then for any Q E G/ 'A, there is P E G/ 6 such that QSP.

Proof. It is iaaediate froa setting

P = aax (A, QsA and A'S6 }.

For any given set Ac;;.G, let A and A be exterior and interior approxiaati!_ns of A with 7espect to 6, respectively; and let Ai and Ai be exterior and interior approxiaations of any grade i E K of A, with respect to 6\, respectively. It seeas true that the sequences (~i:iEK} and ( A.i ,iEK} should satisfy aontonei ty. Unfortunately, the following exaaple shows that neither the sequence ( Ai, iEK} nor the sequence {Ai,iEK} satisfies ao~toneity -- aonotone increasing or decreasing. So, we will consider only the case of { 6 i, i E K }SE [G] .

Exaaple 3. 1 let G={a,b,c,d}, 6 ={a,b,c}' U{<b,d>, <d,b>,<d,d>l, A. ={ a, c}'U {b,d}'.

Obviously, A.<~ So we have,

{a, b l}l. = G ;?(a, b} 6 = {a, b, c}

{a, c },_ = { a, c } ~ {a, c } 6 = q,

but then we also ha;e,--

{a, cl~ = {a,c}~{a,b;cl = {a, c} 6

I a,b,cl,_ = {a,cl£(a. b.c } = ~ 6 .

Even so, it is quite a useful tool for gradual approxiaations of the indistinct concepts, specially when we try to siaplify our probleas. Generality speaking, a concept can be represented by listing the attributes of objects. The aore of the attributes we list, the better the approxiaations are. But this is usually to be done only in an extent. So, we can use U 0l,iEKI <n l Al, i EK I> as an approxiaation of .! <T> in aost cases . Here, we give a simple illustration of exploiting the theory .

Exaaple 3. 2 Let G be a set constituted by a given group of jltYJ'ons. Suppose R<o>, R<s> and R<t> are three relations on G. i.e. R<o> istllt'neithbDY relation, R(s) the saae schoolaate relation, and R< t) the townsaan relation. Given a set A~�, our task is to find out that in G who are closely related to one another aaong theaselves and who are closely related to a person in A.

To do so, we first get interior and exterior approxiaations ..!_(o) and Mo> of A with respect to R<o>. Siai larly, we have _Ms>, Ms>, Mt> and Tc t>. Secondly, let's set

..L= _Mo) u .!._(s), B= A (O) n T (S) ·

Then J!. and B are the approxiaations of interior and exterior approxiaations of A with respect to R (O) n R (S) respectively. In the saae way. we obtain ,

.L= !._<o> u A<t>, c =Teo> n A<t>

JL= !. < s > U _M t >, D = A < s > n A< t>

_L = A< o > U .!.< s > U A< t>

E = A <o> n Ms> n M:n.

Finally, we can choose a rational solution based on our understanding of the saying" Be closely related to a person in A". Such an idea seeas useful to aachine cognition, natural language understanding and autoaatic theorea proving, etc.

Of course, tiait ourselves relations E [ G] the situations becoae cleaer if we to the case of the set of equivalence . Now,JlabdBinexaaple 3. 2 are really interior and exterior approxiaations of A with respect to R<o> n R<s> respectively . The reason for this lies in the following theoreas .

Leaaa 3. 3 Suppose any 6, >'-. E E [ G] and let 6 ( 'A . For each Q E G/ A. there is ( Pj,jEJ}S:G/ 6 such that Q = U {Pj ,j E 1} .

Proof.Ctearly 6I ·Q E E [QJ . Let Q/ 6 =(Pj,j E J}. It is sufficient to prove that Pj E GA) for each j E 1. In fact, if it is not true, then we can suppose that there is soae Pj~�/ 6 . Thus there is always Pj · E G/ 6 such that Pj~· . So <P" j U <Q-Pj ))' E G/ ],, it is contradictory with aaxiaality of Q ( see de fin i t ion l. 3 ) .

Froa above leaaa it is easy to establish the following facts ,

Theorea 3. 2 Let ( 6 i, i E K}SE [G] be a aonotone dcreasing sequence, then the sequence (Ai, i E K } is aonotone decreasing and (_!i,iE K} is aonotone increasing. Moreover, _!i:-!_sAs:Ai for each i E K.

Corollary 3. 2 A= n (Ai,iEKI,l_=U( !ioiEKl. That is a E A iff for all i E K there is b E G such that <a, b) E 6 i, aE A iffthereisiEKsuchthatforallb E G and c a, b) E o i.

Reaark . If a relation 6 E E [G] is given , we choose a aonotone decreasing faaily of relations, { 6 i 1 i E K} S E [G] , according to the practical considerations, such that U { 6 i, i E K} e6 . Let o i" = 6 no i for i E K. Then by what is aentioned before we obtain exterior and interior approxiaations Ai and ~} of any grade i E K of A, with respect to 6 i". In fact, such an idea has been realized in a Coaputer Diagnosing Systea [5 ] . The Logical foraalisa that provides toots for the exaaination of expressive power of the sys tea in teras of approxiaate definabilit y is discussed further in other papers .