Deductive classifier

A deductive classifier is a type of artificial intelligence inference engine. It takes as input a set of declarations in a frame language about a domain such as medical research or molecular biology. For example, the names of classes, sub-classes, properties, and restrictions on allowable values. The classifier determines if the various declarations are logically consistent and if not will highlight the specific inconsistent declarations and the inconsistencies among them. If the declarations are consistent the classifier can then assert additional information based on the input. For example, it can add information about existing classes, create additional classes, etc. This differs from traditional inference engines that trigger off of IF-THEN conditions in rules. Classifiers are also similar to theorem provers in that they take as input and produce output via First Order Logic. Classifiers originated with KL-ONE Frame languages. They are increasingly significant now that they form a part in the enabling technology of the Semantic Web. Modern classifiers leverage the Web Ontology Language. The models they analyze and generate are called ontologies.

History

A classic problem in knowledge representation for artificial intelligence is the trade off between the expressive power and the computational efficiency of the knowledge representation system. The most powerful form of knowledge representation is First Order Logic (FOL). However, it is not possible to implement knowledge representation that provides the complete expressive power of first order logic. Such a representation will include the capability to represent concepts such as the set of all integers which are impossible to iterate through. Implementing an assertion quantified for an infinite set by definition results in an undecidable non-terminating program. However, the problem is deeper than not being able to implement infinite sets. As Levesque demonstrated, the closer a knowledge representation mechanism comes to FOL, the more likely it is to result in expressions that require infinite or unacceptably large resources to compute.

As a result of this trade-off, a great deal of early work on knowledge representation for artificial intelligence involved experimenting with various compromises that provide a subset of FOL with acceptable computation speeds. One of the first and most successful compromises was to develop languages based predominately on modus ponens, i.e. IF-THEN rules. Rule-based systems were the predominant knowledge representation mechanism for virtually all early expert systems. Rule-based systems provided acceptable computational efficiency while still providing powerful knowledge representation. Also, rules were highly intuitive to knowledge workers. Indeed, one of the data points that encouraged researchers to develop rule-based knowledge representation was psychological research that humans often represented complex logic via rules.

However, after the early success of rule-based systems there arose more pervasive use of frame languages instead of or more often combined with rules. Frames provided a more natural way to represent certain types of concepts, especially concepts in subpart or subclass hierarchies. This led to development of a new kind of inference engine known as a classifier. A classifier could analyze a class hierarchy (also known as an ontology) and determine if it was valid. If the hierarchy was invalid the classifier would highlight the inconsistent declarations. For a language to utilize a classifier it required a formal foundation. The first language to successfully demonstrate a classifier was the KL-ONE family of languages. The LOOM language from ISI was heavily influenced by KL-ONE. LOOM also was influenced by the rising popularity of object-oriented tools and environments. Loom provided a true object-oriented capability (e.g. message passing) in addition to Frame language capabilities. Classifiers play a significant role in the vision for the next generation Internet known as the Semantic Web. The Web Ontology Language provides a formalism that can be validated and reasoned on via classifiers such as Hermit and Fact++.

Implementations

The earliest versions of classifiers were logic theorem provers. The first classifier to work with a Frame language was the KL-ONE classifier. A later system built on common lisp was LOOM from the Information Sciences Institute. LOOM provided true object-oriented capabilities leveraging the Common Lisp Object System, along with a frame language. In the Semantic Web the Protege tool from Stanford provides classifiers (also known as reasoners) as part of the default environment.

External links

Fact++ Reasoner

HermiT Reasoner

Protege Ontology Editor

References

{{Inference engines

Knowledge representation
Ontology languages
Classification algorithms