4.11 Approaches to knowledge representation

What this is and why it exists

A representation exists to make inference cheap, not to store facts. That one sentence explains most of the design choices in this area, and it is the thing people miss when they treat knowledge representation as a database question. This topic gives you four properties to judge any scheme against and four families of scheme to judge — and the useful discovery is that each family fails a different one of the four, so there is no general winner and the choice is always about your problem.

The vocabulary

• Knowledge base — the stored knowledge a system reasons over.
• Inference — deriving something not explicitly stored.
• Representational adequacy — can the scheme express what you need?
• Inferential adequacy — can it derive what you need?
• Inferential efficiency — can it derive it fast enough to be useful?
• Acquisitional efficiency — can the knowledge be got in at all?
• Declarative — knowledge stated as facts, separate from how it is used.
• Procedural — knowledge embedded in the steps of a procedure.

The mental model

Start from the purpose, because it decides everything else. If storage were the point, a table of facts would be sufficient and this topic would not exist. The point is inference: the system must answer questions nobody stored the answer to. Which means a representation is good when the inferences you care about are cheap in it, and the same knowledge stored differently can make the same question trivial or intractable. Ask what you will need to conclude before deciding how to store anything — the same habit the search unit applied when it insisted on goal formulation first.

The four properties are the questions to ask of any scheme.

Representational adequacy: can it express what you need to say? A scheme that cannot state "some but not all", or "this is true unless", or "probably", cannot hold knowledge of that kind at all, however convenient it is otherwise.

Inferential adequacy: can it derive the conclusions you need? Expressing something and being able to reason with it are different. A scheme can hold a fact perfectly and provide no mechanism for combining it with another.

Inferential efficiency: can it derive them fast enough? This is where expressive schemes fail. There is a persistent trade between how much a representation can say and how quickly it can reason — the more expressive the language, the harder the inference, and the most expressive logics have inference problems that are undecidable in general. A system that would eventually deduce the answer is the search unit's completeness point again.

Acquisitional efficiency: can the knowledge be got in at all? This is the property that defeats more systems than the other three combined, and it is the least discussed. Someone must supply the knowledge. If that requires a scarce expert, working with an engineer, for months, then the representation may be excellent and the system will still fail — which is precisely what happened to the expert systems whose collapse the history topic describes. When judging a scheme, ask who will write the knowledge down and how long it will take them.

The four families, and what each is good at.

Relational knowledge is facts in tables: rows of attributes and values, or simple relations between things. Its representational range is narrow — it holds facts and not rules, exceptions or generalities. It has essentially no inference of its own beyond lookup and combination. What it has is unmatched efficiency and, crucially, acquisitional efficiency: everybody can fill in a table, tooling exists everywhere, and the knowledge can be collected by people who understand the domain and nothing else. It is the right answer far more often than its low status suggests, and a great many systems that reach for something elaborate would have been better served by it.

Logical knowledge states facts and rules in a formal language with defined rules of inference. It is strong on representational and inferential adequacy: it can express general statements, conditions and negation, and it derives conclusions soundly with a proof you can inspect. Its weaknesses are the other two properties. Inference becomes expensive as the knowledge base grows, and the more expressive the logic the worse this gets. And it handles uncertainty and exceptions badly — classical logic has no comfortable way to say "birds fly, except the ones that do not", so exceptions must be encoded explicitly and the knowledge base grows brittle as they accumulate.

Procedural knowledge embeds the knowledge in code: how to do something, expressed as the steps for doing it. It is very efficient, it captures skill that nobody can state declaratively, and it handles special cases naturally because a procedure can test for them directly. Its cost is that the knowledge is no longer inspectable or reusable — you cannot ask a procedure what it knows, you cannot use its knowledge to answer a different question, and you cannot check it for consistency. The declarative-versus-procedural choice is a trade of flexibility against efficiency, and it recurs throughout computing.

Inheritance-based knowledge organises concepts into a hierarchy where properties are stated once at a general level and apply to everything below. It is compact — enormously so, since one statement covers thousands of cases — and the inference is cheap, being a walk up the hierarchy. It suits domains that genuinely are hierarchical, which is many of them. Its failure is exceptions: the moment a subordinate concept contradicts something inherited from above, the mechanism must be patched, and the patches interact. That difficulty is the subject of the next topic.

So the honest comparison, which is what an examination question is asking for. Relational fails inferential adequacy. Logical fails inferential efficiency and struggles with exceptions and uncertainty. Procedural fails representational adequacy in the sense that matters — the knowledge cannot be inspected or reused. Inheritance fails on exceptions. Every representation buys some inferences cheaply and makes others impossible, and naming both sides is what an honest comparison requires. There is no general winner, and a scheme presented as having no weaknesses has had one left out.

Which is why real systems combine them, and that is worth saying plainly rather than treating the four as exclusive choices. A production system commonly holds bulk facts relationally, a hierarchy of types for compactness, rules in a logical form for the reasoning that must be explicable, and procedures for the parts that are skill rather than fact. Choosing per kind of knowledge, rather than adopting one scheme for everything, is what an experienced designer does — and the four properties are how you argue for each choice.

What you should now be able to explain or do

State what a representation is for and why that decides the design choices. Apply the four adequacy properties to any scheme. Explain the trade between expressiveness and inference cost. Say why acquisitional efficiency defeats more systems than the others and what question it reduces to. Describe the four families and what each buys. Name which property each family fails. Argue that there is no general winner and recognise a comparison with a weakness left out. Design a system that uses several schemes for different kinds of knowledge.

Check yourself