Katana VentraIP

Knowledge representation and reasoning

Knowledge representation and reasoning (KRR, KR&R, KR²) is the 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 dialog in a natural language. Knowledge representation incorporates findings from psychology[1] about how humans solve problems and represent knowledge, in order to design formalisms that will make complex systems easier to design and build. Knowledge representation and reasoning also incorporates findings from logic to automate various kinds of reasoning.

Examples of knowledge representation formalisms include semantic nets, frames, rules, logic programs and ontologies. Examples of automated reasoning engines include inference engines, theorem provers, model generators and classifiers.

"A knowledge representation (KR) is most fundamentally a surrogate, a substitute for the thing itself, used to enable an entity to determine consequences by thinking rather than acting," i.e., "by reasoning about the world rather than taking action in it."[21]

[21]

"It is a set of ontological commitments", i.e., "an answer to the question: In what terms should I think about the world?" [21]

[21]

"It is a fragmentary theory of intelligent reasoning, expressed in terms of three components: (i) the representation's fundamental conception of intelligent reasoning; (ii) the set of inferences the representation sanctions; and (iii) the set of inferences it recommends."

[21]

"It is a medium for pragmatically efficient computation", i.e., "the computational environment in which thinking is accomplished. One contribution to this pragmatic efficiency is supplied by the guidance a representation provides for organizing information" [21] so as "to facilitate making the recommended inferences."[21]

[21]

"It is a medium of human expression", i.e., "a language in which we say things about the world."[21]

[21]

Knowledge-representation is a field of artificial intelligence that focuses on designing computer representations that capture information about the world that can be used for solving complex problems.


The justification for knowledge representation is that conventional procedural code is not the best formalism to use to solve complex problems. Knowledge representation makes complex software easier to define and maintain than procedural code and can be used in expert systems.


For example, talking to experts in terms of business rules rather than code lessens the semantic gap between users and developers and makes development of complex systems more practical.


Knowledge representation goes hand in hand with automated reasoning because one of the main purposes of explicitly representing knowledge is to be able to reason about that knowledge, to make inferences, assert new knowledge, etc. Virtually all knowledge representation languages have a reasoning or inference engine as part of the system.[17]


A key trade-off in the design of knowledge representation formalisms is that between expressivity and tractability.[18] First Order Logic (FOL), with its high expressive power and ability to formalise much of mathematics, is a standard for comparing the expressibility of knowledge representation languages.


Arguably, FOL has two drawbacks as a knowledge representation formalism in its own right, namely ease of use and efficiency of implementation. Firstly, because of its high expressive power, FOL allows many ways of expressing the same information, and this can make it hard for users to formalise or even to understand knowledge expressed in complex, mathematically-oriented ways. Secondly, because of its complex proof procedures, it can be difficult for users to understand complex proofs and explanations, and it can be hard for implementations to be efficient. As a consequence, unrestricted FOL can be intimidating for many software developers.


One of the key discoveries of AI research in the 1970s was that languages that do not have the full expressive power of FOL can still provide close to the same expressive power of FOL, but can be easier for both the average developer and for the computer to understand. Many of the early AI knowledge representation formalisms, from databases to semantic nets to production systems, can be viewed as making various design decisions about how to balance expressive power with naturalness of expression and efficiency.[19] In particular, this balancing act was a driving motivation for the development of IF-THEN rules in rule-based expert systems.


A similar balancing act was also a motivation for the development of logic programming (LP) and the logic programming language Prolog. Logic programs have a rule-based syntax, which is easily confused with the IF-THEN syntax of production rules. But logic programs have a well-defined logical semantics, whereas production systems do not.


The earliest form of logic programming was based on the Horn clause subset of FOL. But later extensions of LP included the negation as failure inference rule, which turns LP into a non-monotonic logic for default reasoning. The resulting extended semantics of LP is a variation of the standard semantics of Horn clauses and FOL, and is a form of database semantics, [20] which includes the unique name assumption and a form of closed world assumption. These assumptions are much harder to state and reason with explicitly using the standard semantics of FOL.


In a key 1993 paper on the topic, Randall Davis of MIT outlined five distinct roles to analyze a knowledge representation framework:[21]


Knowledge representation and reasoning are a key enabling technology for the Semantic Web. Languages based on the Frame model with automatic classification provide a layer of semantics on top of the existing Internet. Rather than searching via text strings as is typical today, it will be possible to define logical queries and find pages that map to those queries.[15] The automated reasoning component in these systems is an engine known as the classifier. Classifiers focus on the subsumption relations in a knowledge base rather than rules. A classifier can infer new classes and dynamically change the ontology as new information becomes available. This capability is ideal for the ever-changing and evolving information space of the Internet.[22]


The Semantic Web integrates concepts from knowledge representation and reasoning with markup languages based on XML. The Resource Description Framework (RDF) provides the basic capabilities to define knowledge-based objects on the Internet with basic features such as Is-A relations and object properties. The Web Ontology Language (OWL) adds additional semantics and integrates with automatic classification reasoners.[23]

Primitives. What is the underlying framework used to represent knowledge? were one of the first knowledge representation primitives. Also, data structures and algorithms for general fast search. In this area, there is a strong overlap with research in data structures and algorithms in computer science. In early systems, the Lisp programming language, which was modeled after the lambda calculus, was often used as a form of functional knowledge representation. Frames and Rules were the next kind of primitive. Frame languages had various mechanisms for expressing and enforcing constraints on frame data. All data in frames are stored in slots. Slots are analogous to relations in entity-relation modeling and to object properties in object-oriented modeling. Another technique for primitives is to define languages that are modeled after First Order Logic (FOL). The most well known example is Prolog, but there are also many special-purpose theorem-proving environments. These environments can validate logical models and can deduce new theories from existing models. Essentially they automate the process a logician would go through in analyzing a model. Theorem-proving technology had some specific practical applications in the areas of software engineering. For example, it is possible to prove that a software program rigidly adheres to a formal logical specification.

Semantic networks

Meta-representation. This is also known as the issue of in computer science. It refers to the capability of a formalism to have access to information about its own state. An example would be the meta-object protocol in Smalltalk and CLOS that gives developers run time access to the class objects and enables them to dynamically redefine the structure of the knowledge base even at run time. Meta-representation means the knowledge representation language is itself expressed in that language. For example, in most Frame based environments all frames would be instances of a frame class. That class object can be inspected at run time, so that the object can understand and even change its internal structure or the structure of other parts of the model. In rule-based environments, the rules were also usually instances of rule classes. Part of the meta protocol for rules were the meta rules that prioritized rule firing.

reflection

. Traditional logic requires additional axioms and constraints to deal with the real world as opposed to the world of mathematics. Also, it is often useful to associate degrees of confidence with a statement. I.e., not simply say "Socrates is Human" but rather "Socrates is Human with confidence 50%". This was one of the early innovations from expert systems research which migrated to some commercial tools, the ability to associate certainty factors with rules and conclusions. Later research in this area is known as fuzzy logic.[25]

Incompleteness

Definitions and vs. facts and defaults. Universals are general statements about the world such as "All humans are mortal". Facts are specific examples of universals such as "Socrates is a human and therefore mortal". In logical terms definitions and universals are about universal quantification while facts and defaults are about existential quantifications. All forms of knowledge representation must deal with this aspect and most do so with some variant of set theory, modeling universals as sets and subsets and definitions as elements in those sets.

universals

. Non-monotonic reasoning allows various kinds of hypothetical reasoning. The system associates facts asserted with the rules and facts used to justify them and as those facts change updates the dependent knowledge as well. In rule based systems this capability is known as a truth maintenance system.[26]

Non-monotonic reasoning

. The standard that Brachman and most AI researchers use to measure expressive adequacy is usually First Order Logic (FOL). Theoretical limitations mean that a full implementation of FOL is not practical. Researchers should be clear about how expressive (how much of full FOL expressive power) they intend their representation to be.[27]

Expressive adequacy

Reasoning efficiency. This refers to the run time efficiency of the system. The ability of the knowledge base to be updated and the reasoner to develop new inferences in a reasonable period of time. In some ways, this is the flip side of expressive adequacy. In general, the more powerful a representation, the more it has expressive adequacy, the less efficient its engine will be. Efficiency was often an issue, especially for early applications of knowledge representation technology. They were usually implemented in interpreted environments such as Lisp, which were slow compared to more traditional platforms of the time.

automated reasoning

In 1985, Ron Brachman categorized the core issues for knowledge representation as follows:[24]

Alphabet of human thought

Belief revision

Chunking (psychology)

Commonsense knowledge base

Conceptual graph

DIKW pyramid

a language for lexical knowledge representation

DATR

a KR language based on First-order logic

FO(.)

Logic programming

Logico-linguistic modeling

Knowledge graph

Knowledge management

Mind map

Semantic technology

Valuation-based system

; What IS-A is and isn't. An Analysis of Taxonomic Links in Semantic Networks; IEEE Computer, 16 (10); October 1983

Ronald J. Brachman

Hector J. Levesque Knowledge Representation and Reasoning, Morgan Kaufmann, 2004 ISBN 978-1-55860-932-7

Ronald J. Brachman

Hector J. Levesque (eds) Readings in Knowledge Representation, Morgan Kaufmann, 1985, ISBN 0-934613-01-X

Ronald J. Brachman

Chein, M., Mugnier, M.-L. (2009),, Springer, 2009,ISBN 978-1-84800-285-2.

Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs

Randall Davis, Howard Shrobe, and Peter Szolovits; AI Magazine, 14(1):17-33,1993

What Is a Knowledge Representation?

Joseph Y. Halpern, Yoram Moses, Moshe Y. Vardi Reasoning About Knowledge, MIT Press, 1995, ISBN 0-262-06162-7

Ronald Fagin

Jean-Luc Hainaut, Jean-Marc Hick, Vincent Englebert, Jean Henrard, Didier Roland: . ER 1996: 42-57

Understanding Implementations of IS-A Relations

Hermann Helbig: , Springer, Berlin, Heidelberg, New York 2006

Knowledge Representation and the Semantics of Natural Language

Frank van Harmelen, Vladimir Lifschitz and Bruce Porter: 2007.

Handbook of Knowledge Representation

Arthur B. Markman: Knowledge Representation Lawrence Erlbaum Associates, 1998

: Knowledge Representation: Logical, Philosophical, and Computational Foundations. Brooks/Cole: New York, 2000

John F. Sowa

Adrian Walker, Michael McCord, , and Walter G. Wilson: Knowledge Systems and Prolog, Second Edition, Addison-Wesley, 1990

John F. Sowa

Mary-Anne Williams and Hans Rott: "Frontiers in Belief Revision, Kluwer", 2001.

by Randall Davis and others

What is a Knowledge Representation?

by Pejman Makhfi

Introduction to Knowledge Modeling

by Enrico Franconi, Faculty of Computer Science, Free University of Bolzano, Italy

Introduction to Description Logics course

DATR Lexical knowledge representation language

Loom Project Home Page

Principles of Knowledge Representation and Reasoning Incorporated

Description Logic in Practice: A CLASSIC Application

The Rule Markup Initiative

- a non-free 3d knowledge representation system

Nelements KOS