Knowledge Representation and Reasoning
Knowledge representation and reasoning is the branch of artificial intelligence concerned with encoding facts about the world in a form a computer can use, and with deriving new conclusions from that encoded knowledge.
Definition
Knowledge representation and reasoning is the study of how to express what an agent knows in a formal language and how to compute the logical consequences of that knowledge, so the agent can answer questions and decide how to act.
Scope
This area covers the formalisms used to represent knowledge symbolically and the inference procedures that operate on them: propositional and first-order logic with theorem proving and resolution, semantic networks, frames and ontologies, description logics, and nonmonotonic and default reasoning. It treats how a representation's expressiveness trades off against the tractability of reasoning, and how knowledge bases are queried and maintained. Statistical and learned representations of knowledge belong to the machine-learning subfield, and reasoning specifically about probability is treated under reasoning under uncertainty.
Sub-topics
Core questions
- How can facts, rules, and relationships about a domain be expressed in a formal, machine-usable language?
- What inference procedures derive new facts that follow from a knowledge base, and are they sound and complete?
- How does the expressiveness of a representation trade off against the computational cost of reasoning with it?
- How should reasoning handle incomplete information and default assumptions that may later be retracted?
Key concepts
- propositional and first-order logic
- entailment and inference
- resolution and theorem proving
- semantic networks and frames
- ontologies
- description logics
- nonmonotonic and default reasoning
- the frame problem
- expressiveness vs. tractability trade-off
Key theories
- Logic as a representation language
- Propositional and first-order logic provide a formal syntax and a model-theoretic semantics in which entailment captures correct inference, giving knowledge representation a rigorous notion of what conclusions are warranted by a knowledge base.
- Resolution and automated deduction
- Robinson's resolution principle reduces logical inference to a single, mechanizable rule on clauses, making refutation-complete theorem proving for first-order logic possible and underpinning logic programming and automated reasoning systems.
- The frame problem and commonsense reasoning
- McCarthy and Hayes identified the difficulty of representing what does and does not change when actions occur (the frame problem), exposing deep challenges in formalizing commonsense knowledge that motivated much later work in nonmonotonic logic.
Clinical relevance
Knowledge representation underlies expert systems, the Semantic Web and linked data, ontology-driven applications in biomedicine and engineering, query answering over structured knowledge bases, and the formal verification of systems; ontologies built on description logics are central to large-scale knowledge graphs.
History
Logic-based knowledge representation began with McCarthy's 1959 proposal for an 'advice taker' and was deepened by the McCarthy-Hayes frame-problem analysis (1969) and Robinson's resolution principle (1965). Parallel structured approaches gave rise to semantic networks and Minsky's frames in the 1970s, later formalized as description logics that underpin modern ontologies.
Debates
- Logicist vs. procedural and structured representations
- A long-running debate contrasts representing knowledge declaratively in logic, with general-purpose inference, against structured or procedural representations (frames, semantic networks, scripts) argued to better capture commonsense organization; description logics partly reconciled the two by giving structured representations a logical semantics.
Key figures
- John McCarthy
- Patrick J. Hayes
- John Alan Robinson
- Ronald J. Brachman
- Hector J. Levesque
- Marvin Minsky
Related topics
Seminal works
- mccarthy1969
- robinson1965
- brachman2004
Frequently asked questions
- What is the difference between knowledge representation and a database?
- A database stores explicit facts and answers queries about them, whereas a knowledge representation system also encodes general rules and relationships and uses inference to derive facts that were never stored explicitly. The emphasis in knowledge representation is on reasoning, not just retrieval.
- Why is there a trade-off between expressiveness and tractability?
- More expressive languages can state more subtle facts but generally make inference computationally harder, sometimes undecidable. Knowledge representation research seeks languages, such as certain description logics, that are expressive enough to be useful while keeping reasoning decidable and efficient.