Generalizing Term Subsumption Languages to Fuzzy Logic

1 Introduction

During the past decade, knowledge representation works in AI have generated a class of languages called term subsumption languages (TSL), which is a knowl­ edge representation formalism with a well-defined logic­ based semantics. Using a TSL, a knowledge en­ gineer can explicitly describe defining characteristics of concepts (unary terms) and roles (binary terms) [Patel-Schneider et a/. 1990Jl . The major strength of term subsumption systems is their reasoning capabil­ ities offered by a classifier. The classifier is a spe­ cial purpose reasoner that automatically infers and maintains a consistent and accurate taxonomic lat­ tice of logical subsumption relations between terms [Schmolze and Lipkis 1983]. These formalisms gener­ ally descend from the ideas presented in KL-ONE [Brachman and Schmolze 1985] . Term subsumption lan­ guages are a generalization of both semantic networks and frames because the languages have well-defined se­ mantics, which is often missing from frames and seman­ tic networks [Woods 1975, Brachman 1983] .

*This research was supported by Engineering Excellence Fund at Texas A&M University.

1 A role in a TSL corresponds to a slot in other frame­ based systems.

Term subsumption languages are limited to express­ ing crisp concept definitions. However, many useful con­ cepts that are needed by an intelligent system do not have well-defined boundaries, i.e., they are vague con­ cepts. For instance, we may say that a baseball player is a good hitter if the person's hitting ratio is fairly high. In an intelligent monitoring and control system, we may wish to define a critical valve as a valve that has a low tolerance of pressure. In all these examples, a concept is defined by referring to other vague terms such as "fairly high hitting ratio" and "low pressure tolerance". It is the difficulty to express these vague concepts in term subsumption languages that motivates us to generalize the languages.

Fuzzy logic, which is a generalization of conventional logic, directly deals with the notion of vagueness and im­ precision using fuzzy predicates, fuzzy quantifiers, lin­ guistic variables, and other constructs. Thus, it offers an appealing foundation for generalizing TSL to capture imprecise and vague linguistic terms. In particular, the test score semantics in fuzzy logic allows us to easily gen­ eralize the term forming expression in TSL into elastic constraints, which can be satisfied to a degree.

In the following sections, we first introduce the ba­ sics of term subsumption languages and test score se­ mantics as a background. Section 3 generalizes the se­ mantics of term subsumption languages and describes a complete and sound subsumption test algorithm for a simple fuzzy term subsumption language. A discussion of related works then follows. Finally, we summarize the potential benefits of our approach.

2 Background

2.1 Term Subsumption Languages

A term subsumption languages (TSL) distinguishes two kinds of concepts: primitive concepts and defined con­ cepts. A primitive concept is a concept whose definition can not be stated in the language; a defined concept is a concept whose definition is described using other con­ cepts and a set of concept forming expressions provided by the language. Value restriction and number restric­ tion are two concept forming constructs that are offered by almost all TSL's. A value restriction restricts the type of a role value (i .e., slot value), while a number re­ striction constrains the cardinality of a role value. In this paper , a value restriction will be expressed in the form of (:all R C) which means that all values of the role R are of type C. A number restriction can be either in the form of (:at-least n R) , which means that the role R has at least n values, or in the form of ( :at-most n R), which states that the role R has at most n values.

To describe the formal semantics of these concept forming constructs in TSL's, we need to introduce the following terminology. A terminological knowledge base, denoted by T, consists of concepts and roles (which are also called relations in some TSL's) defined using a term subsumption language. An interpretation IT ofT is a pair (V, £) where V is a set of individuals described by terms in T and E is an extension function that maps concepts in T to subsets of V , and roles in T to subsets of the Cartesian product, V x V. Based on these nota­ tions, we describe the semantics of some term forming expressions in TSL's below [Nebel 1988]:

2.2 Test Score Semantics

In 1981, while the first KL-ONE workshop was be­ ing held, Lotti A. Zadeh was advocating a meaning­ representation language called PRUF based on possibil­ ity theory in fuzzy logic [Zadeh 1978b] . The semantics underlying PRUF is what Zadeh referred to as test score semantics, which interprets the meaning of a predicate as having an elastic constraint on objects in the database [Zadeh 1981, Zadeh 1982]. In PRUF, a query is pro­ cessed by first applying a sequence of tests to database objects, yielding a collection of test scores. By aggregat­ ing these test scores, the system obtains an overall test score that measures the compatibility between the query and the database.

Test-score semantics is more general than the seman­ tics of term subsumption languages, in which test scores are limited to true and fals. Unlike KL-ONE, however, PRUF was not concerned about developing efficient spe­ cial purpose reasoners. By combining works in these two areas, we can develop a knowledge representation system that takes advantage of both the generality of test score semantics and the efficient reasoning capabilities of term subsumption systems.

3 Generalizing the Semantics of Term Subsumption Languages

In this section, we generalize the semantics of term sub­ sumption language. First, we generalize the extension of a term and the subsumption relationship between terms. Then we describe how various concept forming expres­ sions can be generalized into elastic constraints using test score semantics in fuzzy logic.

3.1 Generalizing the Extension Function and the Subsumption Relationship

We first generalize the extension function E such that the extension of a concept is a fuzzy subset of V, and the extension of a role is a fuzzy subset of V x V. A fuzzy subset C of Vis characterized by a membership function Jl.c that maps elements of Vto the interval [0, 1]. The degree to which an element x of V belongs to a concept Cis denoted as J.l.c (x) . Similarly, the degree to which an ordered pair < x, y > belongs to a role R is denoted as J.l.R (x, y). Moreover, we can generalize the extension of a term forming expression to a fuzzy set and denote the degree to which an object x satisfies a term forming expression e by J.le(x).

A concept C1 subsumes a concept C2 if and only if the extension of the former is a fuzzy superset of the extension of the latter. More formally, we say that C1 subsumes c2 if and only if for any set 1) and any exten­ sion function E over V the following holds:

3.2 Soft Value Restriction

A value restriction in a terminological language con­ strains all the role values of an object to be in­ stances of a given class. For instance, a type of valve can be defined by restricting its pressure tolerance to an interval. We can generalize this kind of con­ straint to an "elastic constraint" or "soft constraint" (e.g., (:all Pressure-Tolerance Low-pressure)) in two ways. The logic implication in the original semantics

can be generalized to a fuzzy implication operator. Thus, the degree to which a value restriction is satisfied by an instance x is determined by the degree to which the implication is true for x. This can be formulated as follows :

where J.l.R(x,y) =>C(y) ( x, y;) can be defined using various fuzzy implication operators [Magrez and Smets 1989].

An alternative approach to generalizing the seman­ tics of a value restriction is to use the notion of con­ ditional necessity in possibility theory [Zadeh 1978a, Dubois and Prade 1988]:

In essence, this formula computes a measure that a Pressure-Tolerance of x is necessarily a college gradu­ ate. It is easy to verify that both generalizations of the value restriction above are consistent with the original semantics. For the rest of our discussion, we will be using Equation 6 as the generalized semantics of value restrictions.

3.3 Soft Number Restriction

The cardinality of a fuzzy set is defined using sigma­ counts in test-score semantics[Zadeh 1981]:

where A is a fuzzy set characterized by a membership function J.lA . We can thus generalize the number re­ striction in terminological languages to a "soft" number restriction using sigma-counts and fuzzy numbers:

where at-least-n and at-most-n are fuzzy subsets of real numbers characterized by the following membership functions:

where z is a real number.

3.4 Fuzzy Conjunction

Finally, the degree an instance satisfies a conjunction of sub-expressions can be computed using the "min" oper­ ator in fuzzy set theory. For instance, suppose Critical­ Valve is defined as a valve whose pressure tolerance is low. This can be expressed as

(defconcept Critical-Valve (:and Valve

(:all Pressure-Tolerance Low-pressure)))

The degree to which an instance is a Critical-Valve can thus be defined as follows:

where PT and L stand for "Pressure-Tolerance" and "Low-pressure" respectively.

It should be noted, however, that other Triangular Norms operators could be used to represent the conjunc­ tion of the sub-expressions. Moreover, by considering the bounds imposed by all Triangular Norms, we could rep­ resent the lower and upper bounds of such intersection as:

3.5 Defining Fuzzy Concepts Using Membership Functions

A fuzzy concept can also be defined by describing its membership function explicitly, or by modifying the membership function of an existing fuzzy concept. To do the former, we also need to specify the domain of the membership function, which is called the universe of dis­ course in fuzzy set theory. For instance, we may define the fuzzy concept Low-pressure by specifying its mem­ bership function and its un~verse of discourse as follows :

where low is a function that returns the membership degree for a given pressure. Once such a fuzzy set is completely specified, we can define many other fuzzy sets using modifiers (also called hedges in fuzzy logic) such as NOT, VERY, SLIGHTLY, etc. This can be expressed in a generalized term subsumption language as follows:

(defconcept Very-Low-pressure

(:VERY Low-pressure)).

4 Subsumption Test

The major component of a term subsumption sys­ tem's reasoner is a subsumption test, which determines whether a term description subsumes (i.e., is more gen­ eral than) another term description. In our generalized term subsumption systems, a term a subsumes another term b if and only if the extension of a is a fuzzy superset of the extension of b (i.e., 'Vx E 1) J.la(x) ~ J.lb(x)).

In a landmark paper that discussed the tradeoff be­ tween the expressiveness and the tractability of sub­ sumption test, Ronald J. Brachman and Hector J. Levesque described a simple term subsumption language :F c- that has a sound and complete algorithm for the subsumption test [Brachman and Levesque 1984]2. In this section, we show that a similar fuzzy term subsump­ tion language, called :FT sc-, also has a sound and com­ plete algorithm for the subsumption test. The grammar of a :FTS£- is shown below.

2 Even though Brachman and Levesque's algorithm fo~ computing the subsumption of concept descriptions in :F c­ has polynomial time complexity, Bernhard Nebel has recently shown that the problem of determining the subsumption of terms, in general, is intractable[Nebel 1989).

<term-definition> ::= <primitive-concept-definition> I <defined-concept-definition> I <primitive-role-definition> <primitive-concept-definition> ::= ( defconcept <c-name> (:and <c-name>* :primitive)) <defined-concept-definition> ::= ( defconcept <c-name> (:and <concept-forming-expr>+ )) I ( defconcept <c-name> :universe-of-discourse <c-name> :membership-fx <lambda expression> ) I ( defconcept <c-name> (<modifier> <c-name>) ) <modifier>::= :NOT I :VERY I :SLIGHTLY <concept-forming-expr> ::= <c-name> I (:all <r-name> <c-name>) I (:some <r-name'>) <primitive-role-definition> ::=

( defrole <r-name> :primitive )

The. subsumption algorithm for :FT s.c- ts a slightly modified version of that of :F .c- presented m [Brachman and Levesque 1984]:

Subsumption Algorithm for :FTs.c-: SUBS?[a,b]

1. If a and b are both defined by membership func­ tions, then return true if they have the same uni­ verse of discourse and their membership functions satisfy the condition 3 :

wher~ U is the universe of discourse of these con­ cepts. Otherwise, return false. .

• ' l · 2. If only one of the two concepts are defined usmg membership functions, return false.
• If both a and b are defined using concept forming expressions, normalize their descriptions by recur­ sively replacing all non-primitive concepts in the de­ scriptions by their definitions.
• Flatten the normalized concept description by re­ moving all nested :and operators.
• Collect all arguments to an :all for a given role.
• Assuming the description of a is now (:and a1 ... an) and the description of b is now (:and b1 ... bm), then return true iff for each ai
• (a) if ai is an atom (i.e., the name of a primitive concept) or a : some, then one of the bj is ai.
• (b) if ai is (:all: r ct), then one of the bj is (:all r c2) where SUBS?[c1,c2]·

By slightly modifying Brachman and Levesque's proof about the soundness and completeness of :F .c- 's sub­ sumption algorithm in [Brachman and Levesque 1984], we can show that the algorithm above is both complete and sound. To prove the soundness of the algorithm, we must show that if SUBS?[a,b] is true, then a indeed subsumes b. Suppose SUBS?[a,b] is true, a and b'must be in one of cases below:

3 We assume that before testing the subsumption of a con­ cept that is defined using modifiers, the system has computed its membership functien using the standard interpretation of those modifiers in fuzzy logic.

1. Both a and b have the same universe of discourse and their membership functions satisfy the test that a is a fuzzy superset of b. I
2. Both a and b are defined using concept forming ex­ pressions. For any conjunct in a, say ai, either ai is among the bj or it is of the form (:all r ct). In the latter case, there is an (:all r c2) among the bj where SUBS?[c1,c2] . To prove by induction, we need to show that if £[ct] 2 £h], theii

Using the generalized semantics for :all (i.e., Equa­ tion 6), we get

Equation 12 thus follows. So no matter what ai is, the extension of b (which is the conjunction of all the bj's) must be a subset of ai. Since this is true for every ai, the extension of b must also be a subset of the. extension of a.

So, whenever SUBS?[a,b] is true, a subsumes b.

To prove the completeness of the algorithm, we need to show that anytime SUBS?[a,b] is false, there is an extension function £ such that £[a] ~ £[b]. There are five cases that may cause SUBS?[a,b] to return false.

1. Assume that a, b are both defined by membership functions, but they have different universe of dis­ course or there exists an Xi such that J.La(xi) < l'b(xi)· In either case, the extension of a is not a superset of the extension of b.
2. Assume t~at a is defined by concept expressio:ps, and b is defined by a membership function. Let * be an object not in b's. universe of discourse, we can construct an extension function £ that assigns * to all concepts defined by concept expressions, and as­ signs <*, *> to all roles. Hence, * is in the extension of a, but not that of b.
3. Assume that some atom ai does not appear among the bj. Let£ assign the ordered pairs <0,1>,<1,1> to every role and 0,1 to every primitive concept ex­ cept ai, to which it assigns 1. Hence, 0 is in ·the extension of b; but not that of a.
4. Assume that ai is (:some r), which does not appear among the bj. Let £ assign 0,1 to every primitive concepts and <0,1>,<1,1> to every role except r, to which it assigns only <1,1>. Hence, 0 is in the extension of b, but not that of a.
5. Assume that ai is (:all r ct),' where if (:all r c2) appears among the bi, then, by induction, c1 does not subsume c2 . Let £* be an extension func­ tion not using 0 or 1 but such that some object

* has a higher membership degree in c2 than in c1 (i.e., J.'e 1 (*) < J.'e 2 (*)). Then, let E contain c· and assign 0,1 to every primitive concepts and <0,1>,<1,1> to every role except r, to which it as­ signs <1,1>,<0,*>. Based on the generalized se­ mantics of :all construct, we have

It then follows that the membership degree of 0 in a is less than that in b.

In all cases, we have shown that &(a] is not a fuzzy super­ set of E(b]. So, a does not subsume b when SUBS?(a,b] is false. Therefore, we have proved that the subsumption algorithm is sound and complete.

5 Related Work

Most existing works in extending frame-based knowl­ edge representation languages for uncertainty manage­ ment lie in the category of probabilistic extensions. Lo­ kendra Shastri has developed a framework, based on the principle of maximum entropy, for dealing with uncer­ tainty in semantic networks (Shastri and Feldman 1985, Shastri 1989]. His approach is based on the assumption that the system has certain statistical data (e.g., the number of red apples, the number of sweet apples, ... ) . Based on these statistical data, Shastri's evidential the­ ory answers questions of the following kind: Given that an instance, r, is red and sweet, is r more likely to be an apple or a grape 'I The major shortcoming of Shastri's theory is the difficulty in obtaining marginal probability judgements that are required by his model.

Heinsohn and Owsnicki-Klewe recently proposed a model of probabilistic reasoning in hybrid term sub­ sumption systems(Heinsohn and Owsnicki-Klewe 1988] . Probabilistic knowledge is represented as probabilistic implications in the form of cl =>, c2 where s denotes the conditional probability P(C2(z)IC1(z)), C1 and C2 are concepts defined in the terminological knowledge base. The reasoning mechanism of their model is proba­ bilistic inheritance (i.e., the inheritance of probabilistic implications in concept taxonomy). The issue of non­ monotonicity of probabilistic inheritance has also been discussed in [Grosof 1986].

Even though these probabilistic extensions to frame­ based reasoning could potentially enlarge the applicabil­ ity of term subsumption systems, they do not directly address the issue of representing and reasoning about the subsumption relationships between vague concepts.

6 Summary

We have described an approach for generalizing term subsumption languages to fuzzy logic. Using test score semantics, we have generalized the concept forming con­ structs in term subsumption languages into elastic con­ straints. By slightly modifying previous works in term subsumption languages, we are able to show a complete and sound subsumption algorithm for a simple fuzzy term subsumption language. The generalized knowl­ edge representation framework not only alleviates the difficulty of conventional AI knowledge representation schemes in handling imprecise and vague information in an intelligent system, but also enables an intelligent sys­ tem to construct an abstraction hierarchy automatically based on the semantics of elastic concept descriptions, some of which may be vague and imprecise. Hence, our approach facilitates the development of complex intelli­ gent systems where the system's capability in perform­ ing high-level analysis using conceptual abstraction and analyzing vague and imprecise information are both es­ sential.

Acknowledgements

I am grateful to many discussions with Lotfi A. Zadeh, Robert MacGregor, Piero Bonissone, and Jonathan Lee. I would also like to thank the referees for their comments on an earlier draft of the paper.