28 Using Fuzzy logic, Frames and Semantic Netfor knowledge representation
Bhushan Trivedi
Introduction
In this module we will see three more methods for knowledge representation, fuzzy logic, frames and semantic net. All of them extends the basic method of knowledge representation by providing solution to one or the other problem. Fuzzy logic help solve the problem of imprecision in data while frames represent the object and class representation and relationship, especially the inheritance issue. Semantic net describers and reasons with relations between various objects. Frames are used extensively while deploying AI based solutions using C++ and Java. Real world problem solutions requires to extends the singleton fame like structure to a frame system which is a collection of multiple frames connected to each other by some relation. The semantic net represents how each entity is connected with another and how one can reason by traveling over that link.
The need for Fuzzy logic
In 26th module we have seen the issues with representing knowledge in predicate logic. One of the issue is the idea of relative degree of membership. Young teacher and young politician are two phrases using same word “young” but very different range of age for being young. Whenever human expert provides way to solve problems, we get similar issues. For example if we ask a housewife the rules for instructing washing machine how to wash clothes we might receive following instructions.
“If cloths are dirty use more washing powder”
“If cloths are heavier, rinse more”
“If cloths are dirty, use hot water”
….
How can we model such statements in a computer program? Please understand the complexity. What do we mean by dirty? With 10 grams of dust, or 20 or what? Or heavy? 5 kilos? 7? 8? What? In fact these rules are quite general and should work for any values between any valid and acceptable numbers. For an example a 7 kg washing machine might accept any weight from 1 to 7. Dirtiness might be decided on a scale of 1 to 10. The washing powder might have four scales, half a spoon to two spoons and so on.
A logical answer to this problem is do somehow relate the weight value to some scale representing heaviness, dirtiness to a scale of 0 to 10 (or something similar) and so on and find out how these things are related and decide the amount of washing powder to be used or use rinsing cycles or choose program or use the temperature of the water to be used for washing.
We need to augment predicate logic or whatever method we are using for knowledge representation using fuzzy logic to enable this. Here is some information on fuzzy logic and fuzzy sets.
Fuzzy sets and fuzzy logic
The conventional sets are sometimes denoted as crisp sets as the boundary between a member and a non-member is well laid out. For example a class student or class teacher are crisp classes. If you are a member or you aren’t. Unlike that, the set like young student or fast car or heavy cloths aren’t that precise about membership. A student with age 10 is definitely young but what about 25? 35? In fact you can say that the association with class “young” is reducing as the student gets older. You do not have an age value where student suddenly ceased to be a member of class young. You can also see that while we are discussing politicians, the range changes, a politician with an age of 50 is considered “young” unlike a student.
Take the example of a fast car. A car with the speed of 150 kmph is definitely fast but what about 80kmph? Again, like young, while we are discussing car racing championship, 150 might not belong to a set of a fast car.
We routinely place objects into such classes where the meaning is well understood but the boundaries are not well defined. Rather the boundaries are fuzzy. Some objects are definitely members while some other objects are partial members. The membership criteria changes as per context given. There is a gradual change from a member to a non-member.
Such sets are known as fuzzy sets. If you look closely at the discussion that we had about washing machines, the sets like “dirty”, “heavy”, “rinse” are all fuzzy sets. Dealing with such sets requires different processing than conventional crisp sets. The fuzzy logic (or fuzzy reasoning) is a detailed mathematical model for representing fuzzy classes and related operations1.
The extent to which an object is a member of a class is denoted by a quantity called membership grades. A membership grade is a value between 0 and 1. An object with membership grade 1 is definitely a member of a class while an object with membership grade 0 is definitely not. Any other value indicates how far that object is a member of that class. For example membership grade for a student with age 10 is 1 while membership grade for a student with age 35 may be 0.4. This values, like certainty factors, is based on expert’s intuition and judgement. There is a difference though between a CF value and a membership grade. When we encounter two statements as follows. First, the rule has some uncertainty, the data is certain (if the patient has malaria, he has, if he does not have, he does not have it), we are uncertain about the rule being true. In the second case, the data is uncertain, the rule is perfectly certain, we are uncertain about degree to which our data matches the rule.
If the patient has fever, there is a suggestive evidence (0.7) that he has malaria If the cloths are dirty, rinse more.
Using multiple Fuzzy Sets to implement rule
What if the washing machine is running a typical wash program and encounters following rule
If the cloths are dirtier than normal, and also heavier than normal, pick up more washing powder and choose a longer rinse cycle.
While this rule was being deliberate upon, the value of dirtiness is determined as 7.6 (from a scale of 0 to 10) while value of heaviness is determined as 4.25 by washing machine sensors. We need to execute the rule. The rule looks like one written in predicate logic but with values that will determine the amount of washing powder and longevity of the rinse cycle requires more processing before the rule is applied.
- 1 The fuzzy logic is well designed mathematical model for dealing with fuzzy sets. The model itself is not fuzzy at it might seem from the name “Fuzzy logic”
The membership grade is mentioned as μ for both sets Dirty and Heavy in figure 28.1. The values 0.8 and 0.7 are membership grades determined by using a technique popularly known as interpolation. It is an easy job if the observed value is an index in the table. For example if we have 7, we can decide the dirtiness membership grade as 0.6 or if the value is 8 we decide the membership grade value is 0.9. It gets little more complex when the value is not an exact index value. The interpolation is a mathematical process to determine the value in such cases. It is basically an answer to a question if 7 is 0.6 and 8 is 0.9 than what is the value of 7.6?2 Thus we have obtained membership grade value for both dirtiness and heaviness of the cloths.
Now the program has to determine the amount of washing powder to be used with amount of rinse cycle. In fact this can be achieved by usi ng tables mentioned in figure 28.2.
Out of two values (0.8 for dirtiness, and 0.7 for heaviness), we will take higher value that is 0.83
2 Another way to look at this is by drawing a graph based on the values given in table and find out intersection on X axis for a given Y value. Interpolation is the same process which does not require graph drawing.
33 Why, because of that value is fuzzier than the other one. In other words, if the cloths are dirty and also heavy, and dirty demands 1.5 spoons of washing powder while heavy needs 2.0, obviously 2.0 table spoon is what preferred.
Now we pick up the value for both Washing Powder and Rinse Cycle, either directly picking up or using that membership grade. That gives us 1.5 spoon washing powder while 6 Rinse cycles.
The washing machine program executes accordingly.
There is a lot of other things to be said for fuzzy logic. One important branch of computer science is dealing with fuzzy neuro controllers. We will not discuss it further.
Frames
Frames are one of the oldest methods of knowledge representation using object oriented fashion. The discussion about frames is quite similar to any language supporting object oriented programming. A frame can represent a class as well as an object (but only one of them by one frame). A class does not have physical existence (it does not occupy memory) while an object has physical existence (it occupies memory). A frame (thus the class as well as objects) is represented as a collection of some attribute-value pairs. Attributes are both, data as well as methods. Here is an example of a frame representing a class and representing an object in figure 28.3. The frame IndianCricketer represents a class and Frame M S Dhoni represents an object of the class IndianCricketer. The attributes like Name, Age etc represents data members. CalcRank() is a method and thus Ranking is a function member. Interesting methods are if-needed and if-added which are available for most, if not all, attributes. The if- needed method is invoked if the value of that attribute is needed but not available while if-added is kind of a trigger. Whenever value of that attribute is available this trigger gets executed for further action. Whatever is to be done is represented by a function member. If needed is quite similar to a constructor function.
Those who have some understanding about object oriented programming can find the discussing quite similar to a discussion on how Java or C++ objects are defined and used. Frames are little loosely structured as both; the class as well as the object; uses the same structure. Also, unlike Java, frame do support and expect multiple inheritance. In our case, the class IndianCricketer is a multiply inherited class. It inherits both from a class called Cricketer as well as Indian. ISA is a well-known concept in frames indicating inheritance.
Though ISA sounds ironic, the idea is basically a subset relationship. When a Class1 has an ISA relationship with another class Class2, it is basically a subset of that class. We will find many such classes in surrounding. For example a Bike class and a Two-wheeler class, Indian class and Person class, Bowler class and a cricketer class. MCA-student class and a student class and so on. The word ISA or isa or is-a is derived from the fact that such relationship can be easily ascertained by testing if a statement involving both classes joined by “is a” is really a true statement.
A bike is a two wheeler.
An MCA student is a student.
An Indian is a person.
The ISA indicates subset of relationship while Instance of indicates membership relation. When the instance of relationship is provided, usually an object is identified as a member of the class. For example in above case, the frame M S Dhoni is connected with two classes, IndianCricketer and CSK using instance of relationship. Thus this frame is an instance of two classes at the same point of time.
Frame Systems
A singleton frame is of little use. A collection of frames, popularly known as a frame system is used for reasoning. Multiple frames are connected by many ways. Two of them are already discussed; viz. ISA and instance of. There are many other ways of doing so. The relations many a times generated based on requirement. For example if you want to find out surname of frame called Aradhya. There is a slot but the value is not provided. You will have to follow father-of link to find out surname attribute value available with father. If you find the father-of link connects to Abhishek and find out the surname is filled by value “Bachchan” you will get the value to be filled for this frame4. If such queries are expected, you must have father of link implemented by providing that attribute which points to that class or object.
| Frame: Indian Cricketer | Frame: M S Dhoni |
| ISA: Cricketer | Instance of : IndianCricker |
| ISA: Indian | Instance of : CSK |
| Name | MahendrasinghDhoni |
| Age | 36 |
| Bats | right |
| Balls | right |
| Balls played | 12000 |
| If needed : – GetBallsPlayed() | 11500 |
| If added: – CalclulateAverage() | 20 |
| Runs scored | 01 |
| Overs balled | 95 |
| Wickets taken | 105 |
| Strike rate | |
| Average | |
| If-Needed: CalculateAverage() | |
| Ranking: CalcRank() | |
| ……….. | |
| ….. |
Figure 28.3 A frame representing a class and a frame representing an object.
Similarly, if a query is asked, what is the value of colour of the jersey M S Dhoni wears? For which you will have to travel the instance of link (or sometimes it is denoted by team) link. Interestingly if you travel through one link representing India you will get value “Blue” but if you travel another link “CSK” you will get value “Yellow”. When you get two different answers while travelling through two different links it is a hard problem to solve unless we have clearer context. Such a problem occurs because of multiple inheritance issue and such a hierarchy is known as entangled hierarchy.
There are many ways Frames are implemented, even specific languages were designed and used. In most cases, general purpose languages like Java and C++ are preferred though for two reasons. First
4 For a serious representation, you may get the value of Married, Gender slots, for Gender value = Female and Married = true, the surname is derived from Husband link and parent it is easier for programmers to code and second, it is easier to integrate the solution with production like systems.
Semantic Networks
Semantic network or semantic net for short is a method of connecting objects in a semantic way. Computer science has many methods for connecting objects like ER diagram, DFD, Activity Diagram and so on. Semantic Net is quite general method which represents objects and connectors. Here is one example depicted in figure 28.4.
If you closely look at 28.4, you can understand that it describes objects and some relation between those objects. For example two objects, Mumbai and Sachin are connected with each other by a relation called Hometown; Sachin and Anjali are connected to each other using relation Wife5 and so on. Most relations are either isa or instance of though. You can see that this is an idea which complements frames. An individual object is defined and expressed using a frame, the inter-object connection is defined and expressed using semantic nets. In fact most systems are defined in both ways together.
If you compare predicate logic representation with semantic net, you can easily get the idea that relations are predicate names and the connecting objects are arguments. For example Wife (Sachin, Anjali) describes relation Wife with two arguments, i.e. names of husband and wife.
The importance of indicating objects
An interesting point comes to fore when a statement like “Sachin gave his bat to Sarfaraz” is to be modelled. Though it would look like to be represented as shown in figure 25.5 it is really not a very good idea.
What is wrong with this representation? There are two problems. First, the bat is not an object, it is a class. Sachin cannot give class bat to Sarfaraz, he can only give one of the objects of a given class. Second, we also have one more statement, Dravid gave his bat to Jay. The representation looks like figure 25.6. This representation is quite confusing. Who has given bat to whom? It is not at all clear.
Check how the problem is solved in 28.7 by providing individual object which are instances of a class bat.
The major use of semantic net is to get answers to queries related to relations between objects. For example if you ask, “Has Sachin anything to do with a Paediatrician?” The answer can be sought by travelling through two different links, form objet Sachin and from class Paediatrician (both represented as nodes in the diagram, thus we are finding if there is some path exists between these two nodes under consideration). The search find some intersecting point, in this case, Anjali and the system answer’s back that Sachin’s wife is a paediatrician. This search, quite logically so, is named intersection search. You can again compare this discussion with predicate logic and understand that the intersection search is nothing but the inference process that we had with predicate logic.
Representing quantification
Comparing with predicate logic, you might ask a question. How do we represent universal and existential quantification in semantic net? Let us take two statements we have introduced in module 24.
- All of the players are physically fit
- Some of the players are singers
For representing statement comprising of, one method to represent is called partitioned semantic net which is shown in the figure 28.8. The S is a generic idea which represents statements made about something. We assume that the statement that we made is one of that set. S, the statement that we made, has two links for any statement which is universally quantified. All variables which are universally quantified is partitioned inside another box which∀ is connected using a Form link. The variable which is universally quantified is connected using link. You can see that such box does not ∃exists, and neither of the links exist for the case depicted in 28.9. We have another link named instead.
What is the significance of fit being part of semantic net box and Physically Fit being out? We mention here that the players which are universally quantified by the variable P here, are physically fit, are part of the universal quantification and thus are determined by the variable P but, the overall class of physically fit is not quantified by this statement. Thus are shown as two different entities. Obviously the class fit is a subset of Physically Fit and thus shown connected by isa link.
We have chosen a typical method of representing quantification, it will not invalidate some other method to do so.
Summary
In this module we have seen three more methods of knowledge representation; i.e. using fuzzy logic, frames and semantic nets in brief. Fuzzy logic is a well-designed mathematical system for representing fuzzy sets and provide operations over them. Concepts like dirty cloths, young teacher etc. are represented using fuzzy logic. Multiple fuzzy sets are required to be consulted for executing rules written by experts dealing with fuzzy sets. A membership grade value determines the amount of membership of an element and thus the amount of reaction. Frames are object oriented way to represent knowledge preferred due to proliferation of object oriented knowledge representation by current general purpose languages. Frame systems are multiple frames connected to each other by various relations, most special ones are is-a and instance of. Semantic nets are ways of modelling such relations between objects and provide answers to queries using intersection search. The idea of a class and an object and the difference between them is very important for successfully implementing and reasoning using frames and semantic nets.
| you can view video on Using Fuzzy logic, Frames and Semantic Netfor knowledge representation | |