Mail


Shortcuts For Experts

Intro
RDBMS/XML
FOL
Frames
Description Logics
A.I.
RDF
UMLS
Google
Conclusion


Description Logics- The Marriage of Logic and Objects

Whereas frame systems are a pragmatic tool for representing knowledge as object, description logics have a more ambitious objective: Not only to represent knowledge as objects, but to justify the process with strict logical reasoning. Unfortunately, Using strict logic to structure knowledge, as we have discussed with first order logic, can make our knowledge database slow and can lead to unavoidable infinite loops in our knowledge storage and retrieval useful information. However, we can avoid some of this intractability in our software by restricting the power of our language to be less than that of first order logic. Earlier, we had done this by restricting ourselves only to and or and not. In this we're going to do this by laying out our logic data so that we only use logic commands that are useful for discussing worlds that are organized into objects. Although this ends up limiting the descriptive power of our knowledge structures, we hope that it does so in a way that is easier for a software program to handle. Also, we hope that much real-world information tends to be easily described with objects, so that our language remain expressive in all the ways that are important.



Superficially, description logics look somewhat similar to their distant cousins, the frame systems: A description logic database consists of a series of symbols followed by information about what they mean. For instance, to describe our salad bar items from earlier, we could say, using a description logic notation:


(lettuce salad_bar_station_food)

(tomato salad_bar_station_food)

(onion salad_bar_station_food)

(carrot salad_bar_station_food)

(cheese (and salad_bar_station_food
             (fills food_group "dairy") 
             (fills fattening "yes")))
However, describing it in this way would be problematic: In a description logic system, the descriptions of each object are meant as tools that the computer can use to categorize each thing (they sufficient for categorizing the item) and exceptions are not permissible. In fact, description logics allow us to describe items in such detail that we can let the computer build them into an unambiguous hierarchy of categories based on their descriptions. Such unambiguous hierarchies are called true ontologies. The basic frame system we described earlier did not have sufficient expressive power to make such ontologies possible, but a basic description logic does have this power.

Not surprisingly, this power requires us to be more careful about the types of statements we make in several different ways:

First of all, description logics (in their basic sense) do not permit us to override properties, so we wouldn't be able to have salad_bar_station_food be non-fattening and then describe cheese as being a fatting exception to this rule.

Second of all, stating that an onion is always a salad_bar_station_food is clearly false in a general sense and if, later on, we state more assertions about onions not from salad bars, the computer may encounter contradictions, something we didn't have to worry about with frame systems. So, instead, we need to get more fancy about how we describe our vegetables- One way to do this would be to break each vegetable on our saladbar into two different concepts: The vegetable itself and a version of the vegetable that may appear on a salad bar. Let re-do our previous descriptions with a more appropriate version:


(vegetable (and (fills food_group "vegetable")
                (fills fattening "no")))

(salad_bar_station_food (and buffet_food
			     (fills temperature "cold")))

(lettuce vegetable)

(tomato vegetable)

(onion vegetable)

(carrot vegetable)

(cheese dairy_product
        (fills food_group "dairy")
	(fills fattening "yes"))

(salad_bar_lettuce (and lettuce
                        salad_bar_station_food))

(salad_bar_tomato (and tomato
                        salad_bar_station_food))

(salad_bar_onion (and onion
                        salad_bar_station_food))

(salad_bar_carrot (and carrot
                        salad_bar_station_food))

(salad_bar_cheese (and cheese
                       salad_bar_station_food))
One fact is immediately evident in this reformulation of our salad bar items: Our descriptions have become quite complex. This is true not only because we had to create extra items to help out the computer's categorizer, but also because we have multiple inheritance. This multiple inheritance (which we can see, for instance, in the description of the salad_bar_lettuce as both being a lettuce and a salad_bar_food) allows us to avoid contradictions in properties, since our cheese can separately inherit properties from dairy_product and or veggies from vegetable while both of them inherit properties from salad_bar_food.

Unfortunately, humans have a hard time thinking about things that inherit from multiple sources- This may possibly be a reason for why description logics are not used as heavily today among computer scientist as one might expect, given their expressive power. However, the reliance on multiple inheritance that is common with description logics can also be a blessing in disguise: As our knowledge databases grow, our human minds may start buckling under the complexity of multiple inherited properties, but the computer can often handle these far more gracefully- In such situations, the person entering the knowledge can often leverage the computer powers to "fill in" the multiple-inheritance relationships based on an incomplete description of the data by the human. Having the computer "fill in" missing relationships is a key ability of description logic systems and is called determining subsumption- A topic we will address in detail in the next section.

Another thing that can be observed in our salad bar example is that some of the properties still might lead to contradictions later on. Notice, for instance, that vegetables are described as non-fattening. Since "non-fattening" is a rather vague concept (especially given the current popularity of low-carb diets) we might still encounter contradictions later on if we try to merge different databases together that have differing opinions of what makes a low-fat food. We could avoid such a confusions by creating even more items (such a low_fat_vegetables) that essentially "factor out" any possible areas of confusions. If we continue along this path of creating ever more objects, we often reach a point where every object has only one or very few new properties that it contributes to its descendants and all our definitions have become tautologies (for instance, saying that vegetable belongs to the "vegetable" food group is essentially a tautology). Although knowledge databases of this type can be overly complex, they are also very general, to the point that even a botany and a buffet-management program could agree on the same vocabulary. Such generality is a holy grail in knowledge representation, and description logics are one possible way computer software might be able to achieve this difficult goal.

Determining Subsumption

Now that have looked at the basic concept of a description logic and have seen examples of some data in this format, lets look at an actual example of a nitty-gritty algorithm that can calculate subsumption on description logic items. Suppose we have the following in our database describing sandwiches:


(vegetarian_food (and (fills comes_from plants)
		      (fills fat_content low_fat)))

(red_pepper vegetarian_food))

(grilled_red_pepper (and red_pepper grilled_food))

(low_fat_ingredient (fills fat_content low_fat))

(unbuttered_panini (and bread_bun vegetarian_food grilled_food))

(healthy_entree (and entree (all ingredients low_fat_ingredient)))

(vegetarian_sandwich (and entree (all ingredients vegetarian) (fills ingredients bread_bun)))

(grilled_sandwich (and entree (fills ingredients (and bread_bun grilled_food)))

(red_pepper_panini (and entree (fills ingredients unbuttered_panini) (fills ingredients grilled_red_pepper)))
If you remember from our previous chapter, description logics systems have the powerful ability to determine inheritance relationship among objects on its own by reasoning about other relationships among objects and the properties these objects possess. This allows us to have the computer do a lot of the "dirty work" for us when we build our knowledge database, especially when we're dealing with complicated situations involving multiple inheritance.

For example, suppose we wanted to know whether a vegetarian_sandwich is healthy_entree: It would make sense then that the computer should be able to determine that a vegetarian_entree is a healthy_entree, since we described it as an entree and stated that all its ingredients are vegetarian, which is described as a low-fat. The proper way to say this among knowledge scientists is to state that healthy_entree subsumes vegetarian_food: 

(subsumes healthy_entree vegetarian_sandwich)
If A subsumes B, it means that there a bunch of individuals in our world, some of which are in the set A, some of which are in the set B, and every single individual who is in set B is also in set A. Notice how the same kind of issues arise in this situation that we had with first order logic: Different people may have different interpretations about who the individuals are and what individuals belong to which sets- But, if we have enough facts in our database, the computer may be able to determine that A has to subsume B because opposing interpretations are guaranteed to lead to contradictions in all cases. A more formal (and this text is way, way informal) text on description logic will create similar descriptions of interpretation tables like we did with our life_unit_527 example, but do it with descriptions logics, which are really just convenient subsets of first order logics.

In our sandwich example, we have only two kinds of operators in our descriptions: and and fills. The and operator lets us list several other descriptions of sets and states that the object in question belongs to all the other sets. The fills operator says that the property in question must have a certain value. The properties of objects in description logics are referred to as "roles"- So, for example, the fat_content role of low_fat_ingredient is filled with "low_fat". Now let's look at the actual algorithm that us calculate that a vegetarian_sandwich is a healthy_entree...

The Algorithm


To do this, we run through the following steps:

1. Run through all the relevant statements in the database (or just the entire database) and take all objects that are inside of descriptions and replace them with their definitions whenever possible until no longer possible. For instance, we know that 
(red_pepper vegetarian_food)
, but we also know that 
(vegetarian_food (and (fills comes_from plants) (fills fat_content low_fat)))
so we can replace the symbol vegetarian_food in the definition of red_pepper to say 
(vegetarian_food (and (fills comes_from plants) (fills fat_conent low_fat)))
. This is called definition expansion.

Here is our little database after all statements have been expanded:


(vegetarian_food (and (fills comes_from plants)
		      (fills fat_content low_fat)))

(red_pepper (and (fills comes_from plants)
		      (fills fat_content low_fat)))

(grilled_red_pepper (and (and (fills comes_from plants)
		              (fills fat_content low_fat))
		         grilled_food))

(low_fat_ingredient (fills fat_content low_fat))

(unbuttered_panini (and bread_bun
                        (and (fills comes_from plants)
	    	             (fills fat_content low_fat))
			grilled_food))

(healthy_entree (and entree (all ingredients (fills fat_content low_fat))))

(vegetarian_sandwich (and entree 
                          (all ingredients (and (fills comes_from plants)
		                                (fills fat_content low_fat)))
		          (fills ingredients bread_bun)))

(grilled_sandwich (and entree (fills ingredients (and bread_bun grilled_food)))

(red_pepper_panini (and entree
                        (fills ingredients
                               (and bread_bun
                                    (and (fills comes_from plants)
	    	                         (fills fat_content low_fat))
			            grilled_food))
	                (fills ingredients (and (fills comes_from plants)
		                                (fills fat_content low_fat))
                                                grilled_food)))
2. Simplify any nested ands by removing the inner and:

(and (and ...) ...) --> (and ... ...)

This step is called normalization. (it becomes more complicated with more operators). After normalization, we will be left with descriptions that has an and on the outside (if any) and other stuff on the inside.


(vegetarian_food (and (fills comes_from plants)
		      (fills fat_content low_fat)))

(red_pepper (and (fills comes_from plants)
                 (fills fat_content low_fat)))

(grilled_red_pepper (and (fills comes_from plants)
		         (fills fat_content low_fat)
		         grilled_food))

(low_fat_ingredient (fills fat_content low_fat))

(unbuttered_panini (and bread_bun
                        (fills comes_from plants)
	    	        (fills fat_content low_fat)
			grilled_food))

(healthy_entree (and entree
                     (all ingredients (fills fat_content low_fat))))

(vegetarian_sandwich (and entree 
                          (all ingredients (and (fills comes_from plants)
		                                (fills fat_content low_fat)))
		          (fills ingredients bread_bun)))
			  
(grilled_sandwich (and entree (fills ingredients (and bread_bun grilled_food)))

(red_pepper_panini (and entree
                        (fills ingredients
                               (and bread_bun
                                    (fills comes_from plants)
	    	                    (fills fat_content low_fat)
			            grilled_food))))
3. Next, we'll want to look at the statement we want to prove and pick the appropriate definitions out of our database. Remember, out statement was:


(subsumes healthy_entree vegetarian_sandwich)
...and here are the definitions of these:

(healthy_entree (and entree
                     (all ingredients (fills fat_content low_fat))))

(vegetarian_sandwich (and entree 
                          (all ingredients (and (fills comes_from plants)
		                                (fills fat_content low_fat)))
		          (fills ingredients (and bread_bun
                                                  (fills comes_from plants)
	    	                                  (fills fat_content low_fat)
			                          grilled_food))))
4. Ok, now we need to take every clause in the "and" phrase of our subsumer (in this case, "healthy_entree") and make sure it follows the following rules:

  • If its an atom (like "entree" is), then there must be an identical clause in the subsumee "vegetarian_sandwich". And in the case of "entree", we have exactly the same "entree" in the subsumee.

  • If it is a "fills" phrase, then there must be an identical fill phrase in the vegetarian_sandwich (not applicable in this example)

  • If it is an "all" phrase (like the "(all ingredients ...)" part of "healthy_entree"), then there must be a similar "all" phrase (as there is) in the vegetarian_sandwich that is subsumed recursively. In the example, this would mean that the following has to be true (which can be determined using the same logic as we did for the whole):

	     (subsumes (fills fat_content low_fat) (and (fills comes_from plants) (fills fat_content low_fat)))
As we can see, the subsumer in this case consists entirely of a "fills" phrase- In this case, an identical "fills" phrase must be present in the subsumee. And indeed, the phrase (fills fat_content low_fat) appears in both descriptions!

If the above rules hold for all parts of the healthy_entree (which they do), then that means that the healthy_entree subsumes vegetarian_sandwich- In other words, a vegetarian_sandwich is a healthy entree. You now know how to determine subsumption!

What Has AI Taught us about Knowledge? >>