Deductive classifier

Last updated

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. [1]

Contents

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. 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 first-order logic, the more likely it is to result in expressions that require infinite or unacceptably large resources to compute. [2]

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 first-order logic 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. [3]

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++. [4]

Implementations

Protege Ontology Editor Protege 3.4.3.png
Protege Ontology Editor

The earliest versions of classifiers were logic theorem provers. The first classifier to work with a frame language was the KL-ONE classifier. [5] [6] 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. [7] In the Semantic Web the Protege tool from Stanford provides classifiers (also known as reasoners) as part of the default environment. [8]

Related Research Articles

Knowledge representation and reasoning is a field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks, such as diagnosing a medical condition or having a natural-language dialog. Knowledge representation incorporates findings from psychology about how humans solve problems and represent knowledge, in order to design formalisms that make complex systems easier to design and build. Knowledge representation and reasoning also incorporates findings from logic to automate various kinds of reasoning.

KL-ONE is a knowledge representation system in the tradition of semantic networks and frames; that is, it is a frame language. The system is an attempt to overcome semantic indistinctness in semantic network representations and to explicitly represent conceptual information as a structured inheritance network.

Description logics (DL) are a family of formal knowledge representation languages. Many DLs are more expressive than propositional logic but less expressive than first-order logic. In contrast to the latter, the core reasoning problems for DLs are (usually) decidable, and efficient decision procedures have been designed and implemented for these problems. There are general, spatial, temporal, spatiotemporal, and fuzzy description logics, and each description logic features a different balance between expressive power and reasoning complexity by supporting different sets of mathematical constructors.

The Web Ontology Language (OWL) is a family of knowledge representation languages for authoring ontologies. Ontologies are a formal way to describe taxonomies and classification networks, essentially defining the structure of knowledge for various domains: the nouns representing classes of objects and the verbs representing relations between the objects.

In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. Symbolic AI used tools such as logic programming, production rules, semantic nets and frames, and it developed applications such as knowledge-based systems, symbolic mathematics, automated theorem provers, ontologies, the semantic web, and automated planning and scheduling systems. The Symbolic AI paradigm led to seminal ideas in search, symbolic programming languages, agents, multi-agent systems, the semantic web, and the strengths and limitations of formal knowledge and reasoning systems.

GNOWSYS is a specification for a generic distributed network based memory/knowledge management. It is developed as an application for developing and maintaining semantic web content. It is written in Python. It is implemented as a Django app. The GNOWSYS project was launched by Nagarjuna G. in 2001, while he was working at Homi Bhabha Centre for Science Education (HBCSE).

Ronald Jay "Ron" Brachman is the director of the Jacobs Technion-Cornell Institute at Cornell Tech. Previously, he was the Chief Scientist of Yahoo! and head of Yahoo! Labs. Prior to that, he was the Associate Head of Yahoo! Labs and Head of Worldwide Labs and Research Operations.

<span class="mw-page-title-main">Logic in computer science</span> Academic discipline

Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas:

A knowledge-based system (KBS) is a computer program that reasons and uses a knowledge base to solve complex problems. Knowledge-based systems were the focus of early artificial intelligence researchers in the 1980s. The term can refer to a broad range of systems. However, all knowledge-based systems have two defining components: an attempt to represent knowledge explicitly, called a knowledge base, and a reasoning system that allows them to derive new knowledge, known as an inference engine.

Loom is a knowledge representation language developed by researchers in the artificial intelligence research group at the University of Southern California's Information Sciences Institute. The leader of the Loom project and primary architect for Loom was Robert MacGregor. The research was primarily sponsored by the Defense Advanced Research Projects Agency (DARPA).

Knowledge-based engineering (KBE) is the application of knowledge-based systems technology to the domain of manufacturing design and production. The design process is inherently a knowledge-intensive activity, so a great deal of the emphasis for KBE is on the use of knowledge-based technology to support computer-aided design (CAD) however knowledge-based techniques can be applied to the entire product lifecycle.

In computer science and artificial intelligence, ontology languages are formal languages used to construct ontologies. They allow the encoding of knowledge about specific domains and often include reasoning rules that support the processing of that knowledge. Ontology languages are usually declarative languages, are almost always generalizations of frame languages, and are commonly based on either first-order logic or on description logic.

F-logic is a knowledge representation and ontology language. It combines the advantages of conceptual modeling with object-oriented, frame-based languages, and offers a declarative, compact and simple syntax, and the well-defined semantics of a logic programming language.

The Semantic Web Rule Language (SWRL) is a proposed language for the Semantic Web that can be used to express rules as well as logic, combining OWL DL or OWL Lite with a subset of the Rule Markup Language.

Frames are an artificial intelligence data structure used to divide knowledge into substructures by representing "stereotyped situations".

Ontology learning is the automatic or semi-automatic creation of ontologies, including extracting the corresponding domain's terms and the relationships between the concepts that these terms represent from a corpus of natural language text, and encoding them with an ontology language for easy retrieval. As building ontologies manually is extremely labor-intensive and time-consuming, there is great motivation to automate the process.

A semantic reasoner, reasoning engine, rules engine, or simply a reasoner, is a piece of software able to infer logical consequences from a set of asserted facts or axioms. The notion of a semantic reasoner generalizes that of an inference engine, by providing a richer set of mechanisms to work with. The inference rules are commonly specified by means of an ontology language, and often a description logic language. Many reasoners use first-order predicate logic to perform reasoning; inference commonly proceeds by forward chaining and backward chaining. There are also examples of probabilistic reasoners, including non-axiomatic reasoning systems, and probabilistic logic networks.

In information technology a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction. Reasoning systems play an important role in the implementation of artificial intelligence and knowledge-based systems.

Flora-2 is an open source semantic rule-based system for knowledge representation and reasoning. The language of the system is derived from F-logic, HiLog, and Transaction logic. Being based on F-logic and HiLog implies that object-oriented syntax and higher-order representation are the major features of the system. Flora-2 also supports a form of defeasible reasoning called Logic Programming with Defaults and Argumentation Theories (LPDA). Applications include intelligent agents, Semantic Web, knowledge-bases networking, ontology management, integration of information, security policy analysis, automated database normalization, and more.

In knowledge representation, particularly in the Semantic Web, a metaclass is a class whose instances can themselves be classes. Similar to their role in programming languages, metaclasses in ontology languages can have properties otherwise applicable only to individuals, while retaining the same class's ability to be classified in a concept hierarchy. This enables knowledge about instances of those metaclasses to be inferred by semantic reasoners using statements made in the metaclass. Metaclasses thus enhance the expressivity of knowledge representations in a way that can be intuitive for users.

References

  1. ↑ Berners-Lee, Tim; Hendler, James; Lassila, Ora (May 17, 2001). "The Semantic Web A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities". Scientific American . 284 (5): 34–43. doi:10.1038/scientificamerican0501-34. Archived from the original on April 24, 2013.
  2. ↑ Levesque, Hector; Ronald Brachman (1985). "A Fundamental Tradeoff in Knowledge Representation and Reasoning". In Ronald Brachman and Hector J. Levesque (ed.). Reading in Knowledge Representation. Morgan Kaufmann. p.  49. ISBN   978-0-934613-01-9. The good news in reducing KR service to theorem proving is that we now have a very clear, very specific notion of what the KR system should do; the bad new is that it is also clear that the services can not be provided... deciding whether or not a sentence in FOL is a theorem... is unsolvable.
  3. ↑ Hayes-Roth, Frederick; Waterman, Donald; Lenat, Douglas (1983). Building Expert Systems. Addison-Wesley. pp.  6–7. ISBN   978-0-201-10686-2.
  4. ↑ MacGregor, Robert (1994). "A Descriptive Classifier for the Predicate Calculus" (PDF). AAAI - 94 Proceedings. Retrieved 17 July 2014.
  5. ↑ Woods, W. A.; Schmolze, J. G. (1992). "The KL-ONE family". Computers & Mathematics with Applications. 23 (2–5): 133–177. doi:10.1016/0898-1221(92)90139-9.
  6. ↑ Brachman, R. J.; Schmolze, J. G. (1985). "An Overview of the KL-ONE Knowledge Representation System". Cognitive Science. 9 (2): 171–216. doi: 10.1207/s15516709cog0902_1 .
  7. ↑ MacGregor, Robert (June 1991). "Using a description classifier to enhance knowledge representation". IEEE Expert. 6 (3): 41–46. doi:10.1109/64.87683. S2CID   29575443.
  8. ↑ "Protege Wiki: Reasoners that integrate with Protege". Stanford University. Retrieved 19 July 2014.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.