View source for Knowledge representation and reasoning

{{Short description|Field of artificial intelligence}}
'''Knowledge representation''' ('''KR''') aims to model information in a structured manner to formally represent it as [[Knowledge|knowledge]] in knowledge-based systems whereas '''knowledge representation''' '''and reasoning''' ('''KRR''', '''KR&R''', or '''KR²''') also aims to understand, reason, and interpret knowledge. KRR is widely used in the field of [[artificial intelligence]] (AI) with the goal to represent [[information]] about the world in a form that a computer system can use to solve complex tasks, such as [[Computer-aided diagnosis|diagnosing a medical condition]] or [[natural language user interface|having a natural-language dialog]]. KR incorporates findings from psychology<ref>{{cite book |first1=Roger |last1=Schank |first2=Robert |last2=Abelson |title=Scripts, Plans, Goals, and Understanding: An Inquiry Into Human Knowledge Structures |date=1977 |publisher=Lawrence Erlbaum Associates, Inc.}}</ref> about how humans solve problems and represent knowledge, in order to design [[Formal system|formalisms]] that make complex systems easier to design and build. KRR also incorporates findings from [[logic]] to automate various kinds of ''reasoning''.

Traditional KRR focuses more on the declarative representation of knowledge. Related knowledge representation formalisms mainly include [[Vocabulary|vocabularies]], [[thesaurus]], [[semantic network]]s, [[Axiom system|axiom systems]], [[Frame (artificial intelligence)|frames]], [[Rule-based system|rules]], [[Logic programming|logic programs]], and [[Ontology (information science)|ontologies]]. Examples of [[automated reasoning]] engines include [[inference engine]]s, [[Automated theorem proving|theorem prover]]s, [[Boolean satisfiability problem|model generators]], and [[Statistical classification|classifiers]].

In a broader sense, parameterized models in [[machine learning]] — including [[Neural network (machine learning)|neural network]] architectures such as [[Convolutional neural network|convolutional neural networks]] and [[Transformer (deep learning architecture)|transformers]] — can also be regarded as a family of knowledge representation formalisms. The question of which formalism is most appropriate for knowledge-based systems has long been a subject of extensive debate. For instance, Frank van Harmelen et al. discussed the suitability of logic as a knowledge representation formalism and reviewed arguments presented by anti-logicists.<ref>{{Cite book |last1=Porter |first1=Bruce |title=Handbook of knowledge representation |last2=Lifschitz |first2=Vladimir |last3=Van Harmelen |first3=Frank |date=2008 |publisher=Elsevier |isbn=978-0-444-52211-5 |edition=1st |series=Foundations of artificial intelligence |location=Amsterdam Boston}}</ref> Paul Smolensky criticized the limitations of symbolic formalisms and explored the possibilities of integrating it with connectionist approaches.<ref>{{Cite journal |last=Smolensky |first=Paul |date=March 1988 |title=On the proper treatment of connectionism |url=https://www.cambridge.org/core/product/identifier/S0140525X00052432/type/journal_article |journal=Behavioral and Brain Sciences |language=en |volume=11 |issue=1 |pages=1–23 |doi=10.1017/S0140525X00052432 |issn=0140-525X|url-access=subscription }}</ref>

More recently, Heng Zhang et al. have demonstrated that all universal (or equally expressive and natural) knowledge representation formalisms are recursively isomorphic.<ref>{{Cite journal |last1=Zhang |first1=Heng |last2=Jiang |first2=Guifei |last3=Quan |first3=Donghui |date=2025-04-11 |title=A Theory of Formalisms for Representing Knowledge |url=https://ojs.aaai.org/index.php/AAAI/article/view/33674 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=39 |issue=14 |pages=15257–15264 |doi=10.1609/aaai.v39i14.33674 |issn=2374-3468|arxiv=2412.11855 }}</ref> This finding indicates a theoretical equivalence among mainstream knowledge representation formalisms with respect to their capacity for supporting [[artificial general intelligence]] (AGI). They further argue that while diverse technical approaches may draw insights from one another via recursive isomorphisms, the fundamental challenges remain inherently shared.

== History ==
{{Artificial intelligence|Major goals}}
The earliest work in computerized knowledge representation was focused on general problem-solvers such as the [[General Problem Solver]] (GPS) system developed by [[Allen Newell]] and [[Herbert A. Simon]] in 1959 and the [[Advice Taker]] proposed by [[John McCarthy (computer scientist)|John McCarthy]] also in 1959. GPS featured data structures for planning and decomposition. The system would begin with a goal. It would then decompose that goal into sub-goals and then set out to construct strategies that could accomplish each subgoal. The Advisor Taker, on the other hand, proposed the use of the [[predicate calculus]] to implement [[common sense reasoning]].

Many of the early approaches to knowledge representation in Artificial Intelligence (AI) used graph representations and [[semantic networks]], similar to [[knowledge graphs]] today. In such approaches, problem solving was a form of graph traversal<ref>{{Cite journal|last1=Doran|first1=J. E.|last2=Michie|first2=D.|date=1966-09-20|title=Experiments with the Graph Traverser program|journal=Proc. R. Soc. Lond. A |volume=294|issue=1437|pages=235–259|doi=10.1098/rspa.1966.0205 |bibcode=1966RSPSA.294..235D|s2cid=21698093}}</ref> or path-finding, as in the [[A* search algorithm]]. Typical applications included robot plan-formation and game-playing.

Other researchers focused on developing [[Automated theorem proving |automated theorem-provers]] for first-order logic, motivated by the use of [[mathematical logic]] to formalise mathematics and to automate the proof of mathematical theorems. A major step in this direction was the development of the [[resolution prover |resolution method]] by [[John Alan Robinson]].

In the meanwhile, John McCarthy and [[Pat Hayes]] developed the [[situation calculus]] as a logical representation of common sense knowledge about the laws of cause and effect. [[Cordell Green]], in turn, showed how to do robot plan-formation by applying resolution to the situation calculus. He also showed how to use resolution for [[Question answering|question-answering]] and [[automatic programming]].<ref>{{cite conference|first=Cordell|last=Green|url=https://www.ijcai.org/Proceedings/69/Papers/023.pdf|title=Application of Theorem Proving to Problem Solving|conference=IJCAI 1969}}</ref>

In contrast, researchers at Massachusetts Institute of Technology (MIT) rejected the resolution uniform proof procedure paradigm and advocated the procedural embedding of knowledge instead.<ref>Hewitt, C., 2009. Inconsistency robustness in logic programs. arXiv preprint arXiv:0904.3036.</ref> The resulting conflict between the use of logical representations and the use of procedural representations was resolved in the early 1970s with the development of [[logic programming]] and [[Prolog]], using [[SLD resolution]] to treat [[Horn clause]]s as goal-reduction procedures.

The early development of logic programming was largely a European phenomenon. In North America, AI researchers such as [[Ed Feigenbaum]] and [[Rick Hayes-Roth|Frederick Hayes-Roth]] advocated the representation of domain-specific knowledge rather than general-purpose reasoning.<ref>{{cite book | chapter-url=https://dl.acm.org/doi/pdf/10.1145/324634.325168 | doi=10.1145/324634.325168 | chapter=The limitation of logic | title=Proceedings of the 1986 ACM fourteenth annual conference on Computer science - CSC '86 | date=1986 | last1=Kowalski | first1=Robert | pages=7–13 | isbn=0-89791-177-6 | s2cid=17211581 }}</ref>

These efforts led to the [[cognitive revolution]] in psychology and to the phase of AI focused on knowledge representation that resulted in [[expert systems]] in the 1970s and 80s, [[Production system (computer science)|production systems]], [[frame language]]s, etc. Rather than general problem solvers, AI changed its focus to expert systems that could match human competence on a specific task, such as medical diagnosis.<ref>{{cite journal |last1=Nilsson |first1=Nils |title=Eye on the Prize |journal=[[AI Magazine]] |date=1995 |volume=16 |page=2}}</ref>

Expert systems gave us the terminology still in use today where AI systems are divided into a ''knowledge base'', which includes facts and rules about a problem domain, and an ''inference engine'', which applies the knowledge in the [[knowledge base]] to answer questions and solve problems in the domain. In these early systems the facts in the knowledge base tended to be a fairly flat structure, essentially assertions about the values of variables used by the rules.<ref>{{cite book|last1=Hayes-Roth|first1=Frederick|title=Building Expert Systems|year=1983|publisher=Addison-Wesley|isbn=978-0-201-10686-2|first2=Donald|last2=Waterman|first3=Douglas|last3=Lenat|url=https://archive.org/details/buildingexpertsy00temd}}</ref>

Meanwhile, [[Marvin Minsky]] developed the concept of [[Frame (artificial intelligence)|frame]] in the mid-1970s.<ref>Marvin Minsky, [http://web.media.mit.edu/~minsky/papers/Frames/frames.html A Framework for Representing Knowledge] {{Webarchive|url=https://web.archive.org/web/20210107162402/http://web.media.mit.edu/~minsky/papers/Frames/frames.html |date=2021-01-07 }}, MIT-AI Laboratory Memo 306, June, 1974</ref> A frame is similar to an object class: It is an abstract description of a category describing things in the world, problems, and potential solutions. Frames were originally used on systems geared toward human interaction, e.g. [[natural language understanding|understanding natural language]] and the social settings in which various default expectations such as ordering food in a restaurant narrow the search space and allow the system to choose appropriate responses to dynamic situations.

It was not long before the frame communities and the rule-based researchers realized that there was a synergy between their approaches. Frames were good for representing the real world, described as classes, subclasses, slots (data values) with various constraints on possible values. Rules were good for representing and utilizing complex logic such as the process to make a medical diagnosis. Integrated systems were developed that combined frames and rules. One of the most powerful and well known was the 1983 [[Knowledge Engineering Environment]] (KEE) from [[IntelliCorp (software)|Intellicorp]]. KEE had a complete rule engine with [[forward chaining|forward]] and [[backward chaining]]. It also had a complete frame-based knowledge base with triggers, slots (data values), inheritance, and message passing. Although message passing originated in the object-oriented community rather than AI it was quickly embraced by AI researchers as well in environments such as KEE and in the operating systems for Lisp machines from [[Symbolics]], [[Xerox]], and [[Texas Instruments]].<ref>{{cite journal|last=Mettrey|first=William|title=An Assessment of Tools for Building Large Knowledge-Based Systems|journal=AI Magazine|year=1987|volume=8|issue=4|url=http://www.aaai.org/ojs/index.php/aimagazine/article/viewArticle/625|access-date=2013-12-24|archive-url=https://web.archive.org/web/20131110022104/http://www.aaai.org/ojs/index.php/aimagazine/article/viewArticle/625|archive-date=2013-11-10|url-status=dead}}</ref>

The integration of frames, rules, and object-oriented programming was significantly driven by commercial ventures such as KEE and Symbolics spun off from various research projects. At the same time, there was another strain of research that was less commercially focused and was driven by mathematical logic and automated theorem proving.{{citation needed|date=February 2021}} One of the most influential languages in this research was the [[KL-ONE]] language of the mid-'80s. KL-ONE was a [[frame language]] that had a rigorous semantics, formal definitions for concepts such as an [[Is-a|Is-A relation]].<ref>{{cite journal|last=Brachman|first=Ron|title=A Structural Paradigm for Representing Knowledge|journal=Bolt, Beranek, and Neumann Technical Report|year=1978|issue=3605|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a056524.pdf|archive-url=https://web.archive.org/web/20200430153426/https://apps.dtic.mil/dtic/tr/fulltext/u2/a056524.pdf|url-status=live|archive-date=April 30, 2020}}</ref> KL-ONE and languages that were influenced by it such as [[LOOM (ontology)|Loom]] had an automated reasoning engine that was based on formal logic rather than on IF-THEN rules. This reasoner is called the classifier. A classifier can analyze a set of declarations and infer new assertions, for example, redefine a class to be a subclass or superclass of some other class that wasn't formally specified. In this way the classifier can function as an inference engine, deducing new facts from an existing knowledge base. The classifier can also provide consistency checking on a knowledge base (which in the case of KL-ONE languages is also referred to as an Ontology).<ref>{{cite journal|last=MacGregor|first=Robert|title=Using a description classifier to enhance knowledge representation|journal=IEEE Expert|date=June 1991|volume=6|issue=3|doi=10.1109/64.87683|pages=41–46|s2cid=29575443}}</ref>

Another area of knowledge representation research was the problem of [[commonsense reasoning|common-sense reasoning]]. One of the first realizations learned from trying to make software that can function with human natural language was that humans regularly draw on an extensive foundation of knowledge about the real world that we simply take for granted but that is not at all obvious to an artificial agent, such as basic principles of common-sense physics, causality, intentions, etc. An example is the [[frame problem]], that in an event driven logic there need to be axioms that state things maintain position from one moment to the next unless they are moved by some external force. In order to make a true artificial intelligence agent that can [[natural language user interface|converse with humans using natural language]] and can process basic statements and questions about the world, it is essential to represent this kind of knowledge.<ref>McCarthy, J., and Hayes, P. J. 1969. {{Cite web |url=http://www-formal.stanford.edu/jmc/mcchay69.pdf |title=Some philosophical problems from the standpoint of artificial intelligence |access-date=January 18, 2024 |archive-date=August 25, 2013 |archive-url=https://web.archive.org/web/20130825025836/http://www-formal.stanford.edu/jmc/mcchay69.pdf |url-status=bot: unknown }}. In Meltzer, B., and Michie, D., eds., ''Machine Intelligence'' 4. Edinburgh: Edinburgh University Press. 463–502.</ref> In addition to McCarthy and Hayes' situation calculus, one of the most ambitious programs to tackle this problem was Doug Lenat's [[Cyc]] project. Cyc established its own Frame language and had large numbers of analysts document various areas of common-sense reasoning in that language. The knowledge recorded in Cyc included common-sense models of time, causality, physics, intentions, and many others.<ref>{{cite book|last=Lenat|first=Doug|title=Building Large Knowledge-Based Systems: Representation and Inference in the Cyc Project|publisher=Addison-Wesley|isbn=978-0201517521|author2=R. V. Guha |date=January 1990}}</ref>

The starting point for knowledge representation is the ''knowledge representation hypothesis'' first formalized by [[Brian Cantwell Smith|Brian C. Smith]] in 1985:<ref>{{cite book|last=Smith|first=Brian C.|title=Readings in Knowledge Representation|year=1985|publisher=Morgan Kaufmann|isbn=978-0-934613-01-9|pages=[https://archive.org/details/readingsinknowle00brac/page/31 31–40]|editor=Ronald Brachman and Hector J. Levesque|chapter=Prologue to Reflections and Semantics in a Procedural Language|chapter-url=https://archive.org/details/readingsinknowle00brac/page/31}}</ref>

<blockquote>Any mechanically embodied intelligent process will be {{sic|comprised |hide=y|of}} structural ingredients that a) we as external observers naturally take to represent a propositional account of the knowledge that the overall process exhibits, and b) independent of such external semantic attribution, play a formal but causal and essential role in engendering the behavior that manifests that knowledge.</blockquote>

One of the most active areas of knowledge representation research is the [[Semantic Web]].{{citation needed|date=February 2021}} The Semantic Web seeks to add a layer of semantics (meaning) on top of the current Internet. Rather than indexing web sites and pages via keywords, the Semantic Web creates large [[ontology (information science)|ontologies]] of concepts. Searching for a concept will be more effective than traditional text only searches. Frame languages and automatic classification play a big part in the vision for the future Semantic Web. The automatic classification gives developers technology to provide order on a constantly evolving network of knowledge. Defining ontologies that are static and incapable of evolving on the fly would be very limiting for Internet-based systems. The classifier technology provides the ability to deal with the dynamic environment of the Internet.

Recent projects funded primarily by the [[Defense Advanced Research Projects Agency]] (DARPA) have integrated frame languages and classifiers with markup languages based on XML. The [[Resource Description Framework]] (RDF) provides the basic capability to define classes, subclasses, and properties of objects. The [[Web Ontology Language]] (OWL) provides additional levels of semantics and enables integration with classification engines.<ref name="Berners-Lee 34–43">{{cite journal|last1=Berners-Lee |first1=Tim |first2=James |last2=Hendler |first3=Ora |last3=Lassila |title=The Semantic Web – A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities |journal=[[Scientific American]] |date=May 17, 2001 |url=http://www.cs.umd.edu/~golbeck/LBSC690/SemanticWeb.html |doi=10.1038/scientificamerican0501-34 |volume=284 |issue=5 |pages=34–43 |url-status=dead |archive-url=https://web.archive.org/web/20130424071228/http://www.cs.umd.edu/~golbeck/LBSC690/SemanticWeb.html |archive-date=April 24, 2013 |url-access=subscription }}</ref><ref name="w3_org">{{cite web|url=http://www.w3.org/2001/sw/BestPractices/SE/ODSD/|title=A Semantic Web Primer for Object-Oriented Software Developers|last1=Knublauch|first1=Holger|last2=Oberle|first2=Daniel|last3=Tetlow|first3=Phil|last4=Wallace|first4=Evan|publisher=[[W3C]]|date=2006-03-09|access-date=2008-07-30|archive-date=2018-01-06|archive-url=https://web.archive.org/web/20180106172902/http://www.w3.org/2001/sw/BestPractices/SE/ODSD/|url-status=live}}</ref>

== Overview ==
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 language]]s have a reasoning or inference engine as part of the system.<ref>{{cite book|last1=Hayes-Roth|first1=Frederick|pages=[https://archive.org/details/buildingexpertsy00temd/page/6 6–7]|title=Building Expert Systems|year=1983|publisher=Addison-Wesley|isbn=978-0-201-10686-2|first2=Donald|last2=Waterman|first3=Douglas|last3=Lenat|url=https://archive.org/details/buildingexpertsy00temd/page/6}}</ref>

A key trade-off in the design of knowledge representation formalisms is that between expressivity and tractability.<ref>Levesque, H.J. and Brachman, R.J., 1987. Expressiveness and tractability in knowledge representation and reasoning 1. Computational intelligence, 3(1), pp.78-93.</ref> [[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.<ref>{{cite book|last1=Levesque|first1=Hector|title=Readings in Knowledge Representation|year=1985|publisher=Morgan Kaufmann|isbn=978-0-934613-01-9|page=[https://archive.org/details/readingsinknowle00brac/page/49 49]|first2=Ronald|last2=Brachman|editor=Ronald Brachman and Hector J. Levesque|chapter=A Fundamental Tradeoff in Knowledge Representation and Reasoning|quote=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.|chapter-url=https://archive.org/details/readingsinknowle00brac/page/49}}</ref> In particular, this balancing act was a driving motivation for the development of IF-THEN rules in [[rule-based system|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 system (computer science)|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,<ref>{{Cite book
| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell
| first2 = Peter.    | last2 = Norvig  | author2-link = Peter Norvig
| title=[[Artificial Intelligence: A Modern Approach]]
| year = 2021
| edition = 4th
| isbn = 978-0134610993
| lccn = 20190474
| publisher = Pearson | location = Hoboken | page=282
}}</ref> 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 [[Massachusetts Institute of Technology|MIT]] outlined five distinct roles to analyze a knowledge representation framework:<ref name=":0">{{cite journal|last1=Davis|first1=Randall|first2=Howard|last2=Shrobe|first3=Peter|last3=Szolovits|title=What Is a Knowledge Representation?|journal=AI Magazine|date=Spring 1993|volume=14|issue=1|pages=17–33|url=http://www.aaai.org/ojs/index.php/aimagazine/article/view/1029/947|access-date=2011-03-23|archive-date=2012-04-06|archive-url=https://web.archive.org/web/20120406094445/http://www.aaai.org/ojs/index.php/aimagazine/article/view/1029/947|url-status=live}}</ref>

* "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," <ref name=":0" /> i.e., "by reasoning about the world rather than taking action in it."<ref name=":0" />
* "It is a set of ontological commitments",<ref name=":0" /> i.e., "an answer to the question: In what terms should I think about the world?" <ref name=":0" />
* "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."<ref name=":0" />
* "It is a medium for pragmatically efficient computation",<ref name=":0" /> 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" <ref name=":0" /> so as "to facilitate making the recommended inferences."<ref name=":0" />
* "It is a medium of human expression",<ref name=":0" /> i.e., "a language in which we say things about the world."<ref name=":0" />

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.<ref name="Berners-Lee 34–43"/> The automated reasoning component in these systems is an engine known as the classifier. Classifiers focus on the [[Subsumption relation|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.<ref>{{cite web|last=Macgregor|first=Robert|title=Retrospective on Loom|url=http://www.isi.edu/isd/LOOM/papers/macgregor/Loom_Retrospective.html|work=isi.edu|publisher=Information Sciences Institute|access-date=10 December 2013|date=August 13, 1999|url-status=dead|archive-url=https://web.archive.org/web/20131025063241/http://www.isi.edu/isd/LOOM/papers/macgregor/Loom_Retrospective.html|archive-date=25 October 2013}}</ref>

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.<ref name="w3_org" />

== Characteristics ==
In 1985, [[Ronald J. Brachman|Ron Brachman]] categorized the core issues for knowledge representation as follows:<ref>{{cite book|last1=Brachman|first1=Ron|author1-link=Ronald J. Brachman|year=1985|title=Readings in Knowledge Representation|publisher=Morgan Kaufmann|isbn=978-0-934613-01-9|pages=XVI–XVII|editor1-last=Brachman|editor1-first=Ronald|editor2-last=Levesque|editor2-first=Hector J.|chapter=Introduction|url=https://archive.org/details/readingsinknowle00brac|url-access=registration}}</ref>

* Primitives. What is the underlying framework used to represent knowledge? [[Semantic network]]s 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.
* Meta-representation. This is also known as the issue of [[Reflective programming|reflection]] in computer science. It refers to the ability of a formalism to have access to information about its own state. An example is the meta-object protocol in [[Smalltalk]] and [[CLOS]] that gives developers [[Execution (computing)#runtime|runtime]] access to the class objects and enables them to dynamically redefine the structure of the knowledge base even at runtime. 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 runtime, 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.
* [[Completeness (logic)|Incompleteness]]. 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 system]]s 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]].<ref>{{cite journal|last=Bih|first=Joseph|title=Paradigm Shift: An Introduction to Fuzzy Logic|journal=IEEE Potentials|volume=25|pages=6–21|year=2006|issue=1 |url=http://www.cse.unr.edu/~bebis/CS365/Papers/FuzzyLogic.pdf|access-date=24 December 2013|doi=10.1109/MP.2006.1635021|bibcode=2006IPot...25a...6B |s2cid=15451765|archive-date=12 June 2014|archive-url=https://web.archive.org/web/20140612022317/http://www.cse.unr.edu/~bebis/CS365/Papers/FuzzyLogic.pdf|url-status=live}}</ref>
* Definitions and [[universals]] 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 quantification]]s. 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.
* [[Non-monotonic logic|Non-monotonic reasoning]]. 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]].<ref>{{cite journal|last=Zlatarva|first=Nellie|title=Truth Maintenance Systems and their Application for Verifying Expert System Knowledge Bases|journal=Artificial Intelligence Review|year=1992|volume=6|pages=67–110|doi=10.1007/bf00155580|s2cid=24696160}}</ref>
* [[Functional completeness|Expressive adequacy]]. 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.<ref>{{cite book|last1=Levesque|first1=Hector|title=Readings in Knowledge Representation|year=1985|publisher=Morgan Kaufmann|isbn=978-0-934613-01-9|pages=[https://archive.org/details/readingsinknowle00brac/page/41 41–70]|first2=Ronald|last2=Brachman|editor=Ronald Brachman and Hector J. Levesque|chapter=A Fundamental Tradeoff in Knowledge Representation and Reasoning|chapter-url=https://archive.org/details/readingsinknowle00brac/page/41}}</ref>
* Reasoning efficiency. This refers to the runtime efficiency of a system: The ability of the knowledge base to be updated and the reasoner to develop new inferences in a reasonable 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 [[automated reasoning]] 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.

== Ontology engineering ==
{{Main article|Ontology engineering|Ontology language}}

In the early years of [[knowledge-based systems]] the knowledge-bases were fairly small. The knowledge-bases that were meant to actually solve real problems rather than do proof of concept demonstrations needed to focus on well defined problems. So for example, not just medical diagnosis as a whole topic, but medical diagnosis of certain kinds of diseases.

As knowledge-based technology scaled up, the need for larger knowledge bases and for modular knowledge bases that could communicate and integrate with each other became apparent. This gave rise to the discipline of ontology engineering, designing and building large knowledge bases that could be used by multiple projects. One of the leading research projects in this area was the [[Cyc]] project. Cyc was an attempt to build a huge encyclopedic knowledge base that would contain not just expert knowledge but common-sense knowledge. In designing an artificial intelligence agent, it was soon realized that representing common-sense knowledge, knowledge that humans simply take for granted, was essential to make an AI that could interact with humans using natural language. Cyc was meant to address this problem. The language they defined was known as [[CycL]].

After CycL, a number of [[ontology language]]s have been developed. Most are [[declarative language]]s, and are either [[frame language]]s, or are based on [[first-order logic]]. Modularity—the ability to define boundaries around specific domains and problem spaces—is essential for these languages because as stated by [[Tom Gruber]], "Every ontology is a treaty–a social agreement among people with common motive in sharing." There are always many competing and differing views that make any general-purpose ontology impossible. A general-purpose ontology would have to be applicable in any domain and different areas of knowledge need to be unified.<ref>Russell, Stuart J.; Norvig, Peter (2010), [[Artificial Intelligence: A Modern Approach]] (3rd ed.), Upper Saddle River, New Jersey: Prentice Hall, {{ISBN|0-13-604259-7}}, p. 437-439</ref>

There is a long history of work attempting to build ontologies for a variety of task domains, e.g., an ontology for liquids,<ref>Hayes P, Naive physics I: Ontology for liquids. University of Essex report, 1978, Essex, UK.</ref> the [[lumped element model]] widely used in representing electronic circuits (e.g.<ref>Davis R, Shrobe H E, Representing Structure and Behavior of Digital Hardware, IEEE Computer, Special Issue on Knowledge Representation, 16(10):75-82.</ref>), as well as ontologies for time, belief, and even programming itself. Each of these offers a way to see some part of the world.

The lumped element model, for instance, suggests that we think of circuits in terms of components with connections between them, with signals flowing instantaneously along the connections. This is a useful view, but not the only possible one. A different ontology arises if we need to attend to the electrodynamics in the device: Here signals propagate at finite speed and an object (like a resistor) that was previously viewed as a single component with an I/O behavior may now have to be thought of as an extended medium through which an electromagnetic wave flows.

Ontologies can of course be written down in a wide variety of languages and notations (e.g., logic, LISP, etc.); the essential information is not the form of that language but the content, i.e., the set of concepts offered as a way of thinking about the world. Simply put, the important part is notions like connections and components, not the choice between writing them as predicates or LISP constructs.

The commitment made selecting one or another ontology can produce a sharply different view of the task at hand. Consider the difference that arises in selecting the lumped element view of a circuit rather than the electrodynamic view of the same device. As a second example, medical diagnosis viewed in terms of rules (e.g., [[MYCIN]]) looks substantially different from the same task viewed in terms of frames (e.g., INTERNIST). Where MYCIN sees the medical world as made up of empirical associations connecting symptom to disease, INTERNIST sees a set of prototypes, in particular prototypical diseases, to be matched against the case at hand.

== See also ==
* {{annotated link|Alphabet of human thought}}
* {{annotated link|Belief revision}}
* {{annotated link|Chunking (psychology)}}
* {{annotated link|Commonsense knowledge (artificial intelligence)|Commonsense knowledge base}}
* {{annotated link|Conceptual graph}}
* {{annotated link|DIKW pyramid}}
* [[DATR]], a language for lexical knowledge representation
* [[FO(.)]], a KR language based on [[first-order logic]]
* {{annotated link|Knowledge graph}}
* {{annotated link|Knowledge management}}
* {{annotated link|Logic programming}}
* {{annotated link|Logico-linguistic modeling}}
* {{annotated link|Mind map}}
* {{annotated link|Semantic technology}}
* {{annotated link|Valuation-based system}}

== References ==
{{Reflist}}

== Further reading ==
* [[Ronald J. Brachman]]; [https://web.archive.org/web/20040110031608/http://citeseer.nj.nec.com/context/177306/0 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}}
* Chein, M., Mugnier, M.-L. (2009),''[http://www.lirmm.fr/gbkrbook/ Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs]'', Springer, 2009,{{ISBN|978-1-84800-285-2}}.
* Randall Davis, Howard Shrobe, and Peter Szolovits; [https://ojs.aaai.org/aimagazine/index.php/aimagazine/article/view/1029 What Is a Knowledge Representation?] AI Magazine, 14(1):17-33,1993
* [[Ronald Fagin]], [[Joseph Y. Halpern]], [[Yoram Moses]], [[Moshe Y. Vardi]] ''Reasoning About Knowledge'', MIT Press, 1995, {{ISBN|0-262-06162-7}}
* Jean-Luc Hainaut, Jean-Marc Hick, Vincent Englebert, Jean Henrard, Didier Roland: [https://web.archive.org/web/20070211062250/http://www.informatik.uni-trier.de/~ley/db/conf/er/HainautHEHR96.html Understanding Implementations of IS-A Relations]. ER 1996: 42-57
* Hermann Helbig: ''[http://14.139.206.50:8080/jspui/bitstream/1/2412/1/Helbig,%20Hermann%20-%20Knowledge%20Representation%20and%20the%20Semantics%20of%20Natural%20Language.pdf Knowledge Representation and the Semantics of Natural Language]'', Springer, Berlin, Heidelberg, New York 2006
* Frank van Harmelen, Vladimir Lifschitz and Bruce Porter: [http://dai.fmph.uniba.sk/~sefranek/kri/handbook/handbook_of_kr.pdf Handbook of Knowledge Representation] 2007.
* Arthur B. Markman: ''Knowledge Representation''  Lawrence Erlbaum Associates, 1998
* [[John F. Sowa]]: ''Knowledge Representation'': Logical, Philosophical, and Computational Foundations. Brooks/Cole: New York, 2000
* Adrian Walker, Michael McCord, [[John F. Sowa]], and Walter G. Wilson: ''Knowledge Systems and Prolog'', Second Edition, Addison-Wesley, 1990
* Mary-Anne Williams and Hans Rott: "Frontiers in Belief Revision, Kluwer", 2001.

== External links ==
{{Commons category|Knowledge representation}}
* [http://medg.lcs.mit.edu/ftp/psz/k-rep.html What is a Knowledge Representation?] by Randall Davis and others
* [http://www.makhfi.com/KCM_intro.htm Introduction to Knowledge Modeling] by Pejman Makhfi
* [http://www.inf.unibz.it/~franconi/dl/course/ Introduction to Description Logics course] by Enrico Franconi, Faculty of Computer Science, Free University of Bolzano, Italy
* [http://www.ccl.kuleuven.ac.be/LKR/html/datr.html DATR Lexical knowledge representation language]
* [http://www.isi.edu/isd/LOOM/LOOM-HOME.html Loom Project Home Page]
* [http://kr.org Principles of Knowledge Representation and Reasoning Incorporated ]
* [http://www.research.att.com/sw/tools/classic/tm/ijcai-95-with-scenario.html Description Logic in Practice: A CLASSIC Application]
* [https://web.archive.org/web/20031202202839/http://www.dfki.uni-kl.de/ruleml/ The Rule Markup Initiative]
* {{usurped|1=[https://web.archive.org/web/20070212094025/http://nelements.org/ Nelements KOS]}} - a non-free 3d knowledge representation system

{{Clear}}
{{Knowledge representation and reasoning}}
{{computer science}}
{{Authority control}}

[[Category:Knowledge representation| ]]
[[Category:Intelligence assessment]]
[[Category:Scientific modelling]]
[[Category:Programming paradigms]]
[[Category:Automated reasoning]]