As mentioned in the first lecture, one of the assumptions underlying work in Artificial Intelligence is that intelligent behaviour can be achieved through the manipulation of symbol structures (representing bits of knowledge). These symbols can be represented on any medium - in principle, we could develop a (very slow) intelligent machine made out of empty beer cans (plus something to move the beer cans around). However, computers provide the representational and reasoning powers whereby we might realistically expect to make progress towards automating intelligent behaviour.
So, the main question now is how we can represent knowledge as symbol structures and use that knowledge to intelligently solve problems. The next few lectures will concentrate on how we represent knowledge, using particular knowledge representation languages. These are high level representation formalisms, and can in principle be implemented using a whole range of programming languages. The remaining lectures will concentrate more on how we solve problems, using general knowledge of problem solving and domain knowledge.
In AI, the crucial thing about knowledge representation languages is that they should support inference. We can't represent explicitly everything that the system might ever need to know - some things should be left implicit, to be deduced by the system as and when needed in problem solving. For example if we were representing facts about a particular CS3 Honours student (say Fred Bloggs) we don't want to have to explicitly record the fact that Fred's studying AI. All CS3 Honours students are, so we should be able to deduce it. Similarly, you probably wouldn't explicitly represent the fact that I'm not the president of the United States, or that I have an office in Lilybank Gardens. You can deduce these things from your general knowledge about the world.
Representing everything explicitly would be extremely wasteful of memory. For our CS3 example, we'd have 100 statements representing the fact that each student studies AI. Most of these facts would never be used. However, if we DO need to know if Fred Bloggs studies AI we want to be able to get at that information efficiently. We also would like to be able to make more complex inferences - maybe that Fred should be attending a lecture at 12am on Tuesday Feb 9th, so won't be able to have a supervision then. However, there is a tradeoff between inferential power (what we can infer) and inferential efficiency (how quickly we can infer it), so we may choose to have a language where simple inferences can be made quickly, though complex ones are not possible.
In general, a good knowledge representation language should have at least the following features:
Some of these features may be present in recent non-AI representation languages, such as deductive and object oriented databases. In fact, these systems have been influenced by early AI research on knowledge representation, and there is some promise of further cross-fertilisation of ideas, to allow robust, multi-user knowledge/data bases with well defined semantics and flexible representation and inference capabilities. However, at present the fields are still largely separate, and we will only be discussing basic AI approaches here.
Broadly speaking, there are three main approaches to knowledge representation in AI. The most important is arguably the use of logic. A logic, almost by definition, has a well defined syntax and semantics, and is concerned with truth preserving inference. However, using logic to represent things has problems. On the one hand, it may not be very efficient - if we just want a very restricted class of inferences, we may not want the full power of a logic-based theorem prover, for example. On the other hand, representing some common-sense things in a logic can be very hard. For example in first order predicate logic we can't conclude that something is true one minute, and then later decide that it isnt true after all. If we did this it would lead to a contradiction, from which we could prove anything at all! We could decide to use more complex logics which allow this kind of reasoning - there are all sorts of logics out there, such as default logics, temporal logics and modal logics. However, another approach is to abandon the constraints that the use of a logic imposes and use a less clean, but more flexible knowledge representation language.
Two such ``languages'' are structured objects
and production systems. The idea of structured
objects
is to represent knowledge as a collection of
objects and relations, the most important relations
being the subclass and instance relations.
The subclass relation (as you might expect)
says that one class is a subclass of
another, while the instance relation says that
some individual belongs to some class. We'll use them
so that ``X subclass Y'' means that X is a subclass of Y, not that
X has a subclass Y. (Some books/approaches
use the relation isa to refer to the subclass relation.
So Fred Bloggs is an instance of the class representing AI3 students,
while the class of AI3 students is a subclass of the class of
third year students.
We can then define property inheritance, so that,
by default, Fred inherits all the typical attributes of AI3 students,
and AI3 students inherit typical attributes of 3rd yr students.
We'll go into this in much more detail below.
Production systems consist of a set of if-then rules, and a working memory. The working memory represents the facts that are currently believed to hold, while the if-then rules typically state that if certain conditions hold (e.g, certain facts are in the working memory), then some action should be taken (e.g., other facts should be added or deleted). If the only action allowed is to add a fact to working memory then rules may be essentially logical implications, but generally greater flexibility is allowed. Production rules capture (relatively) procedural knowledge in a simple, modular manner.
The next 2-3 lectures will describe these different knowledge representation languages in more detail. We'll start with structured objects, as these are fairly easy to understand (and are the subject of the next exercise). Then we'll talk about logic, and then production rules. The discussion of production rules should lead naturally into our next major topic: problem solving using search.