"Time", "Purchase" , "Cost"
"7:30", "Hamburger" , 3.49
"8:45", "Fries" , 1.49
"9:00", "Shake, chocolate", 1.29
|
You may recognize this format: This is called a comma-delimited text file. It's basically a table where each item in a row is separated by commas- In this example, the first row happens to be special because it lists the titles of the columns in the table. This type of file can be imported into most programs that work with tables, such as Excel. It is a popular way to store tables, because it is only a simple text file that programs can read and work with. Although many books that deal with knowledge like to use math notation, this tutorial is going to use only simple text notations like this for examples, since they are more natural for persons who are not used to reading math notation.
Ok, now the one thing that is interesting about this list of fast food purchases is that some of the items have quotes around them- This is because some of the items that are in the table are arbitrary text strings that may confuse the structure of the file- Notice, for instance how the last row for a shake is listed as "shake, chocolate" and without the quotes we would be unsure wether the comma in the name should be treated like the other commas in the file. Other items (such as the cost of the items that are just numbers) may not need these quotes. The parts of a text file that help define the structure of the file (such as the quotes and commas in this example) are called the syntax of the file. Syntax helps us to avoid confusing different parts of text with each other and helps define the role each piece of text plays in the structure of data (number, text string, etc.).
But for any piece of data we also want to know what each piece of data means. The parts of a file that determine the meaning of the data are called semantics.
Semantics are established by words (or other pieces of data) that usually do one of two things:
- Have special meaning to a program that reads the file
- Describe relationships between the parts of a file
In our fast food example, there really aren't a lot of semantics- Conceivably, a program might recognize that the words "Cost" or "Time" have special meaning, which might allow the program to do calculations based on time or cost. But, basically, a table in this type of format is just simple data without much semantics. If, however, we wanted to allow more sophisticated abilities in a table format, (such as allowing a user to add formulas to calculate the totals for all purchases) then we would need to indicate internal relationships and that would require the format to have more complex semantics.
In this primer, we're not too interested in syntax, since it is not especially important for encoding knowledge- We will be focusing on semantics instead. For this reason, we're going to write most of our examples using syntax expression notation. In this format, all data is stored as lists of things arranged with spaces between them, with the whole list delimited by parenthesis. Additionally, the first word in the list always has a special agreed-upon meaning. Also, lists can be nested.
As an example, we could express the previous data in syntax expression format as follows:
|
(table (titles "Time" "Purchase" "Cost")
(row "7:30" "Hamburger" 3.49 )
(row "8:45" "Fries" 1.49 )
(row "9:00" "Shake, chocolate" 1.29 ))
|
This syntax is very flexible for many different layouts of data and by using it uniformly we avoid focusing too much attention on the syntax used to present it, and can instead focus more attention on the actual knowledge it contains.
Adding Semantics to Data
Ok, so what we want to do is inject meaning into our data, and, as we have seen, the way to do this is to develop ways of structuring data what are rich in semantics. The most straightforward way of doing this is to create a data structure that has symbols in it that represent something. In the comma-delimited text file example the file was just filled with raw data, not true symbols: If the word "Hamburger" had been misspelled "Hambruger", any software reading the file would likely not have noticed the difference. What we are talking about now is creating words that have to be spelled correctly and used correctly because they have meaning and represent something that a person or computer program can understand.
So what sort of things could a symbol represent?
Well, basically a symbol could represent one of four things:
- Individual: A symbol could represent an agreed-upon specific object in the real world.
- Relationship: A symbol could indicate an agreed-upon relationship between other symbols.
- Set of things: A symbol could refer to a group of objects in the real world, using agreed-upon rules among the persons using the symbol.
- Higher concepts and other stuff: A symbol could refer to some sort of abstract idea that is only indirectly related to the real world. This includes, among other things, relationships between things that are more complex than just straight mappings between two other symbols. This also includes ideas that are "fuzzy" because we are unsure exactly what real world objects are in the group the symbol refers to.
We can ease the process of thinking about formal knowledge representation if we limit ourselves to only certain types of symbols- That's why the KR system we're going to study first is only going to basically deal with individuals and relationships for now. Also, this first system we will discuss will use some clever tricks to deal with the difficult word "agreed-upon" that makes it hard to talk about individuals and relationships in a concrete manner.
Representing Knowledge with Classical Logic
The first rigorous way of representing data that we will discuss is first-order logic (FOL), the logic you might have learned in high school- This is where we talk about things like "and", "or" and "implies". The reason this system of logic is called "first order" is because we don't use confusing higher order symbols. Instead, we just create a simple list of individuals in the real world, and give some of them names. Additionally, we will have things called predicates that let us indicate relationships between individuals. By using only individuals, predicates, and a few simple operators, we have a powerful way of representing lots of different types of knowledge in a relatively straightforward manner.
Even though first order logic is relatively straight-forward, it still has plenty of complexities. The two main complexities that we are going to look at soon in this primer are Interpretations and Tractability. But first, let's look at how we can write knowledge using FOL.
Writing Knowledge Using FOL
Basically, what we do is simply take predicates and individuals and write out any statements that evaluate to be true. For instance, suppose we want to say that it rained in New York on a particular day:
|
(rained new_york_city july_13th_2005)
|
Notice that we are again using syntax-expression notation. This means that the word right after the opening parenthesis has a special meaning- In this case, we're using it to hold the predicate. The other words between the parenthesis are the individuals the predicate operates on. Remember that a predicate, for a given set of individuals, always evaluates to either true or false. By writing out a specific predicate with individuals, like we have done above, we are asserting that for this set of individuals, the predicate evaluates to true.
Another important feature of predicates is that a given predicate always has the same number of individuals as arguments (in the example above that number is two arguments- new_york_city and july_13th_2005), but that any number of such arguments is allowed. For instance, The first triumvirate of the Roman Empire can be described, with three arguments, as follows:
|
(triumvirate julius_caesar pompeius_magnus marcus_licinius_crassus)
|
In this case, the predicate triumvirate is being used to indicate all known triumvirates. The phrase above indicates that the three individuals mentioned are considered one such triumvirate.
Note also that we can use predicates with only one argument, if we wish, as a simple grouping mechanism. For instance, we could use this trick to state the July 13th, 2005 was a Wednesday:
|
(wednesday july_13th_2005)
|
Along with predicates (which let us express true statements about individuals) FOL also uses connectives, which let us connect together such predicates into more complex statements. These connectives will probably already be pretty familiar to you:
- and : Lets us state that both predicates are true, such as (and (sings-songs barney-the-dinosaur) (is-purple barney-the-dinosaur))
- or : Lets us state that at least one of two predicates are true, such as (or (is-guy-in-suit barney-the-dinosaur) (is-dinosaur barney-the-dinosaur))
- not : Flips the statement between true and false, such as (not (eats-children barney-the-dinosaur))
There are a couple more connectives that require a little more explanation:
- all : The all command takes two items: The name of a variable and another expression that makes use of this variable. For instance, if everybody in a bar is wearing a hat, then we could say (all X (or (hat_wearer X) (not (person_in_bar X)))). This translates, more precisely, as "For all things X it is true either that X is wearing a hat or X is not a person in the bar". In this case, both hat_wearer and person_in_bar are predicates.
- exists: This command also takes two items that are a variable and an expression, but only requires a single instance of an object to exist that meets the given criteria. For instance, if we assume every church has a priest, then when could be fairly certain that: (exists X (and (priest X) (person_in_my_church X))) Which translates to "There exists a thing X where X is a priest and X is a person in my church"
Interpretations
One key convenience a logician has that most people do not is that a logician is working mostly within the world of logic, whereas somebody trying to represent knowledge with logic is usually dealing with tangible objects, such as trees, chairs, patients, etc. Because of this, we have to be very careful when translating real things into logical symbols- This can, surprisingly, be a difficult challenge.
First of all, even if we limit our statements to those that refer only to individuals we still have to figure out how the term agreed-upon fits into our knowledge system. If we understood the real world well enough, maybe we could get rid of the word agree-upon and simply come up with some system where anybody could immediately tell what symbol represents a thing in the real world, but alas, our current understanding of the world makes this impossible: First of all, there are an infinite number of different ways of naming things in the real world with symbols because the real world is just so huge (especially if you include symbols describing mathematics) Secondly, certain symbols could refer to parts of other symbols' objects, or overlap with them somehow, and force our symbols into all kinds of nasty relationships. The way scientists avoid this whole mess is to build a concept called an interpretation- When we use an interpretation, we basically say to ourselves:
| "The real world is too messy for us to name things directly. Instead, we'll just create an imaginary structure that maps things in the real world to symbols- But we just won't worry too much about what objects in the real world map to our symbols, because doing so is impossible to do perfectly anyway" |
If we use interpretations to do our reasoning, it becomes impossible to draw any real conclusions about the world, only conclusions about the interpretation. We will explore why this is so in the next section.
An Example Of Interpretations
In order to understand how formal interpretations help remove ambiguities from knowledge representation, let's look at two theoretical KR researchers and show how proper use interpretations allows them to communicate logically without ambiguity. Our two researchers are Dr. Smith and Life_unit_273:
Dr. Smith
Life_unit_273
Let's look at a small world that these researchers might like to encode as knowledge and see how the ideas of interpretations and first order logic allows them to do this effectively:
|
Lisa is the mother of Jim and Bob.
Jim can skateboard really well.
Bob likes to play his harmonica and his guitar.
His guitar is really loud.
|
Ok, now part of thinking of interpretations is that different people may have different interpretations... For instance, Dr. Smith sees that there are the following different individuals in this mini world:
|
 lisa jim bob bobs_harmonica bobs_guitar
|
Notice how Dr. Smith did not encode jims_skateboard as an individual object: Presumably, Jim has a skateboard, but Dr. Smith isn't absolutely sure- After all, Jim may just ride other people's skateboards, or may he has never actually ridden a skateboard, but maybe it is just somehow known that he would be really great if he were ever to try it. Already, we can see how arbitrary our interpretation of the facts can be. But we already know that interpretations are arbitrary: The important point here is that Dr. Smith needs to create a one-to-one map of objects in the world and some symbols, like in the picture above- The details of the interpretation are not that important, only that it exists and that it leads to list of unique symbols that are mapped to.
The second step Dr. Smith needs to undertake is to define the predicates of this world. This is slightly more complex: Any individuals could be used as a parameter for the predicates and Dr. Smith needs to make sure that he knows the precise result that happens when each of these functions is applied to each possible combination of parameters. We can do this by creating a table of all possible combinations- This means the number of dimensions to our table will be equal to the number of parameters the predicate takes.
The first predicate Dr. Smith creates is called great_skateboarder. This predicate takes only one parameter and therefore only needs a one-dimensional table to describe what the function does:
great_skateboarder:
lisa False
jim True
bob False
bobs_harmonica False
bobs_guitar False
He does the same for loud:
loud:
lisa False
jim False
bob False
bobs_harmonica False
bobs_guitar True
Again, we can see there is room for interpretation here: After all, the example doesn't say explicitly that Bob doesn't skateboard- Also, we might consider Bob to be loud himself when he plays his guitar. The important thing is that Dr. Smith builds this table in one way or another, not the details of the interpretation he used to do it.
Next, he creates a predicate called parent- This time it takes two parameters and therefore requires a two-dimensional table:
|
parent:
lisa jim bob bobs_harmonica bobs_guitar
lisa False True True False False
jim False False False False False
bob False False False False False
bobs_harmonica False False False False False
bobs_guitar False False False False False
|
|
He does the same for plays
|
plays:
lisa jim bob bobs_harmonica bobs_guitar
lisa False False False False False
jim False False False False False
bob False False False True True
bobs_harmonica False False False False False
bobs_guitar False False False False False
|
Ok, now Dr. Smith has a complete interpretation about the world of Lisa, Bob, and Jim. Even though the interpretation had a lot of ambiguities, the final result is something that does not have any ambiguity, withing the realm of first order logic. For instance, Dr. Smith would agree that the following facts are true:
|
(parent lisa jim)
(parent lisa bob)
(great_skateboarder jim)
|
Based on these facts, it is clear that the following is also true:
|
(exists X (and (parent lisa X) (great_skateboarder X)))
|
In other words, from these facts it follows that lisa is the parent of at least one great skateboarder- We know this, because we can give an example: Jim.
Now here is a key point: No matter what Dr. Smith's interpretation was of the facts, if he agrees with the statements (parent lisa jim) (parent lisa bob) (great_skateboarder jim) he can know that the above statement is true with absolute certainty, even if, by chance, he interpreted the original facts wrong!
|
|
To illustrate this point, let's return to our space alien, life_unit_273, who is not very good at human languages and interprets the facts differently- Specifically, he thinks that when Dr. Smith is talking about Lisa, he actually meant Jim. When Dr. Smith is talking about parenting, he is actually talking about playing an instrument. When Dr. Smith talks about Jim and Bob, he is referring to the musical instruments. And finally, when Dr. Smith talks about skateboarding, he is talking about being loud.
Despite all these confusions, life_unit_273 will still be able to converse with Dr. Smith about the same situation and can do so in a logically correct fashion: In life_unit_273's interpretation, when he sees:
|
(parent lisa jim)
(parent lisa bob)
(great_skateboarder jim)
|
It basically means to him that "bob plays the harmonica and a loud guitar". He would also agree, based on this, that:
|
(exists X (and (parent lisa X) (great_skateboarder X)))
|
Except, in life_unit_273's world, this means that "Bob plays an instrument that is loud". A logician could take all of this a step further and prove that no matter what our interpretation is, the existence of the great skateboarder son follows from the three propositions, no matter what interpretation is used by the observer of the logical statements in question. In this manner, a person who wants to encode knowledge can decouple the ambiguities of interpretation from the mathematical certainty of first order logic. This means that, as long two persons are confident that their interpretation of the common vocabulary is the same, they can converse in the language of logic and be certain of the truth of conclusions that are drawn in the process. If, however, somebody, such as life_unit_273, doesn't have a correct interpretation of the definition of the individuals or the predicates, they may have perfectly sound logic skills but would not be guaranteed to agree with derived conclusions, since their interpretation may or may not agree with the propositions that the conclusions are based on.
The nature of interpretation is critical in formal knowledge representation and is carefully formalized by KR scientists in order to guarantee that no ambiguity exists in the logical structure of the represented knowledge. Now that we understand the basic syntax of FOL and have looked at the issue of interpretation, let's use FOL to see how we can process knowledge that has been represented...
Reasoning with FOL >>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
