(a regular column in
intelligence magazine)Syed S. Ali
University of Wisconsin - Milwaukee
Intelligence requires knowledge. Knowledge is used to determine behavior and to derive new knowledge from old. In software systems, we can code knowledge implicitly or explicitly. Implicit coding (called procedural knowledge) is knowledge about how to do things. Implicit encodings are typically coded as a set of instructions for performing a task (aka a software program). Explicit codings (called declarative knowledge) use (usually task-specific) computerized knowledge with a single program (called a knowledge representation system) that manipulates knowledge to perform services such as deriving new knowledge (called reasoning), planning, and acting.
Programmers have been writing code that, quite successfully, automates a wide range of tasks. So, why should software developers consider using declarative knowledge representation in their intelligent software? One important answer lies in the high cost of updating software. When you need to change the behavior of your software, you must change its code. The Y2K problem is a clear example of this. By contrast, for software that makes use of a knowledge representation system, changing behavior can be as easy as changing the knowledge (in the case of the Y2K problem, the meaning of the date concept) in the knowledge representation system. Software that uses procedural knowledge is often brittle, that is, it will break if any of the assumptions made when coding the software change. (In the case of Y2K, the assumption was that the software would have long since been replaced by Y2K!)
Another advantage of knowledge representation is in knowledge discovery, the discovery of new information from old. For example, you may have a large quantity of data (say a corpus or transaction log) and want to find useful correlations (a simple example of this is Amazon.com's incitement to spend more money by pointing out that people that bought a book also bought other books.) Writing special-purpose software for each type of discovery problem is inefficient and can be avoided by the use of knowledge representation software.
Not all tasks require a full knowledge representation system; for those that do, the advantages are great. Problems where the task knowledge of the domain does not change (or changes little) are more efficiently solved with procedural encoding (for example, a payroll system). Problems where the task knowledge changes (or is unknown) are candidates for the use of knowledge representation systems. For lots of examples of such problems (and knowledge representation systems) see Peter Clark's list of knowledge-based projects and groups at http://www.cs.utexas.edu/users/mfkb/related.html.
There are two broad categories of knowledge representation system software: symbolic and sub-symbolic. I characterize a knowledge representation as symbolic if it is possible to assign understandable meaning to any portion of the data structures (the representation) used to represent knowledge. Sub-symbolic knowledge representation encodes knowledge in patterns of data structures or use probabilistic information. Sub-symbolic knowledge representation is typically used in uncertain information tasks where meaning is uncertain or probabilistic.
Below is a list of some of the important types of knowledge representation systems. I also indicate a problem class that these types of systems are typically used for, a useful URL to find out more, and one or more specific systems:
These categories are not disjoint. Rule-based expert systems can make use of probabilistic information to assign probabilities when combining evidence in rule use. Description logic systems include some of the capabilities of semantic networks.
Knowledge engineering requires great deal of expertise, both in the task domain as well as the knowledge representation system language. More useful knowledge representation tends to be more expressive requiring more expertise to craft the knowledge. To effectively use many sub-symbolic knowledge representation systems, a good grasp of basic mathematics and probability theory is essential. Much symbolic knowledge representation software is based on (typically first-order) logic or its extensions. This is because logic provides a well-defined computational process for deriving new knowledge from old correctly (reasoning). Stu Shapiro has an excellent introduction to logic (as well as a simple reasoner) available at http://www.cse.buffalo.edu/~shapiro/Reasoning/.
Before selecting a knowledge representation system, insure that it is appropriate to your task and the data associated with the task. This can be nontrivial, as several kinds of systems may be appropriate. For example, both Bayesian networks and rule-based expert system may be appropriate for diagnosis; other characteristics of the problem will determine the best fit. The usability of the knowledge representation system for your problem is important. Usability considerations include: documentation (including tutorials), availability and platforms (license, UNIX/Lisp or Windows), interface (is it easy to use), user community or support (someone to answer your questions), speed, and scalability (will it handle your task now and in the future). Deborah McGuinness and Peter Patel-Schneider overview some of these issues (with a focus on CLASSIC) at http://www.research.att.com/~dlm/papers/use-final-abstract.html.
Other than some of the specific resources I've mentioned, some useful meta-resources are:
The next issue of Links will survey authoring tools. Specifically: what are they; why might be need them; and whats out there. Feel free to send me your personal recommendations.
If you have any comments on this column (or suggestions for topics for future ones) or interesting resources, please email me at: syali@usa.net. This article (and updates to it) is available online at http://tigger.cs.uwm.edu/~syali/links.html/ with links to all the resources mentioned.