Knowledge representation and reasoning in AI, explained

Knowledge representation and reasoning in AI is the field that asks how to write down what a system knows about the world in a form a computer can use, and how to let it work out new things from that. A medical diagnosis and a natural-language dialog are the two examples the field itself uses.

If you like thinking about how machines hold ideas about a messy world, Contain ASI is a browser story strategy game for 1 to 4 players in which you try to keep four fictional AI labs from crossing into recursive self-improvement before 2027. It is fiction, and it gives these questions a setting.

What knowledge representation and reasoning in AI means

Wikipedia's article separates two ideas. Knowledge representation (KR) models information in a structured way so it can be treated as knowledge in a knowledge-based system. Knowledge representation and reasoning (KRR) also aims to understand, reason about and interpret that knowledge.

The field draws on two sources. It takes findings from psychology about how people solve problems and represent knowledge, so the formalisms make complex systems easier to design and build. It takes findings from logic, so various kinds of reasoning can be automated.

The traditional focus is on declarative representation, meaning facts and rules that say what is true. Related formalisms include vocabularies, thesauri, semantic networks, axiom systems, frames, rules, logic programs and ontologies. The engines that reason over them include inference engines, theorem provers, model generators and classifiers.

Why not just write code?

The article's answer is that conventional procedural code is not the best formalism for complex problems. Representing knowledge explicitly makes complex software easier to define and maintain. If you talk to experts in terms of business rules rather than code, you shrink the gap between users and developers.

There is a trade-off at the center of the field: expressivity against tractability. First-order logic (FOL) is very expressive and is the standard for comparing languages, but it has two drawbacks. It allows many ways of saying the same thing, which makes it hard to use, and its proof procedures are complex, so implementations are hard to make efficient. A key discovery of 1970s AI research was that languages with less than the full power of FOL can come close to its expressive power and be easier for both people and computers. IF-THEN rules in rule-based expert systems and the logic programming language Prolog came out of that balancing act.

A short history of how systems held knowledge

General problem solvers

The earliest work focused on general problem solvers: the General Problem Solver of Allen Newell and Herbert A. Simon, and the Advice Taker that John McCarthy proposed, both in 1959. The first began with a goal, split it into sub-goals and built strategies for each. The second proposed using the predicate calculus to do common sense reasoning. Many early systems used graphs and semantic networks, so problem solving became a matter of path-finding.

Expert systems

The field then shifted. Rather than general problem solvers, AI turned to expert systems that could match human competence on one task, such as medical diagnosis. They gave us terms still used today: a knowledge base of facts and rules about a domain, and an inference engine that applies the knowledge to answer questions. Read more in our post on expert systems and symbolic AI.

Frames, rules and classifiers

In the mid-1970s Marvin Minsky developed the frame: an abstract description of a category, like an object class, with slots for data values. Frames were good for representing the real world as classes and subclasses, and rules were good for complex logic such as a diagnosis, so systems combined both. Another line of work, driven by mathematical logic, produced KL-ONE, a frame language with rigorous semantics. Its reasoner, called the classifier, could analyze declarations, infer new assertions and check a knowledge base for consistency. See also Marvin Minsky.

Common sense

People lean on a huge base of everyday knowledge about physics, causality and intentions that is not obvious to a machine. The frame problem is an example: in an event-driven logic you need axioms saying things stay where they are unless something moves them. One of the most ambitious attempts was Doug Lenat's Cyc project, where analysts wrote common-sense models of time, causality, physics and intentions into its own language.

Five roles of a representation

In a 1993 paper, Randall Davis of MIT described five roles for a knowledge representation. It is a surrogate, a substitute for the thing itself that lets a system work out consequences by thinking instead of acting. It is a set of ontological commitments, an answer to "in what terms should I think about the world?". It is a fragmentary theory of intelligent reasoning. It is a medium for efficient computation. And it is a medium of human expression, a language in which we say things about the world.

The Wikipedia article also gives Ron Brachman's 1985 list of core issues, including incompleteness (dealing with confidence), non-monotonic reasoning (updating dependent conclusions when facts change) and the pull between expressive adequacy and reasoning efficiency. In general, the more powerful a representation, the less efficient its reasoning engine.

A worked example: a tiny knowledge base

You can feel the ideas with a pen. Try this in five steps:

1. Write a universal, a general statement about the world: "All humans are mortal."
2. Write a fact, a specific case: "Socrates is human."
3. Ask a question: "Is Socrates mortal?" An inference engine joins the fact to the universal and answers yes. Nobody wrote that answer down.
4. Add confidence. The article notes that expert systems attached certainty factors, so a statement can read "Socrates is human with confidence 50%". Now your answer carries a confidence too.
5. Add a default for a frame. A "restaurant" frame can carry default expectations such as ordering food, which narrows the search space and helps a system pick a response.

Notice the cost at every step. You had to choose terms, which is Davis's second role. More detail makes reasoning slower, which is the trade-off from earlier.

Where this meets AI risk

The article adds that, in a broader sense, parameterized models in machine learning, including neural network architectures such as convolutional neural networks and transformers, can also be seen as a family of knowledge representation formalisms. Which formalism suits knowledge-based systems best has long been debated: Frank van Harmelen and colleagues reviewed the case for and against logic, and Paul Smolensky explored combining symbolic and connectionist approaches.

For safety readers this raises a plain question: can you read what a system knows? An explicit rule is easy to inspect. A learned model is harder; see explainable AI. In Contain ASI, which says its labs, people and events are fictional, that tension is the kind of thing a story can play with, but the game is not a source for how real systems work.

Frequently asked questions

What is knowledge representation in AI?

It is modeling information in a structured way so a computer system can use it as knowledge. With reasoning added, it also lets the system draw conclusions.

What is an inference engine?

It is the part of a knowledge-based system that applies the knowledge base to answer questions and solve problems in the domain.

What is a frame in AI?

A frame is an abstract description of a category, similar to an object class, with slots for data values. Marvin Minsky developed the idea in the mid-1970s.

Is Contain ASI a prediction about AI?

No. The page says all its labs, people and events are fictional. It is a story strategy game inspired by the AI 2027 scenario.

Get started with Contain ASI

Reading about knowledge is one thing; deciding with partial knowledge is another. Contain ASI runs in your browser and needs WebGL 2, so use a recent Chrome, Edge, Firefox or Safari. From the home page you can start a New campaign or open How to play.

Play Contain ASI: a story strategy game for 1 to 4 players that runs in your browser. Its labs, people and events are all fictional.