knowledge representation

Knowledge representation (KR) is a subfield of artificial intelligence (AI) concerned with designing formalisms to encode information about the world in a structured, machine-readable manner. Its primary goal is to enable computer systems to store, organize, and reason with knowledge, thereby supporting tasks such as inference, planning, natural language understanding, and decision-making. KR relies on symbolic structures—such as logical formulas, graphs, or frames—that capture objects, relations, categories, and rules, often drawing on insights from philosophy, linguistics, and cognitive science.

1.1 Philosophical origins

The roots of knowledge representation lie in ancient philosophy, particularly in debates about the nature of knowledge and its symbolic encoding. Plato’s theory of forms and Aristotle’s categories provided early frameworks for classifying entities and their properties. Later, the rationalist tradition (e.g., Leibniz’s characteristica universalis) and the empiricist emphasis on sensory experience influenced how AI researchers conceptualized representing facts and rules.

1.1.1 Symbolism vs. connectionism

A central philosophical divide in KR is between symbolism and connectionism. Symbolism holds that knowledge can be adequately captured through discrete, symbolic structures (e.g., logical formulas, rules). Connectionism, inspired by neural networks, contends that knowledge emerges from distributed patterns of activation across many simple processing units. While early AI favored symbolism, modern hybrid systems often combine both approaches.

1.2 Key properties

Knowledge representation formalisms are evaluated along several key properties that determine their suitability for a given task.

1.2.1 Expressive power

Expressive power refers to the range of concepts and relationships a formalism can capture. For example, first-order logic can represent objects, properties, and quantifiers, while propositional logic is limited to atomic facts. Higher expressiveness often comes at the cost of increased computational complexity.

1.2.2 Computational tractability

Tractability concerns the efficiency of reasoning with a representation. A formalism may be highly expressive but lead to undecidable or intractable inference problems. Balancing expressiveness and tractability is a core challenge in KR design.

1.3 Ontological commitments

Every KR scheme makes implicit assumptions about what exists in the domain—its ontological commitments. These decisions determine the categories (e.g., objects, events, properties) allowed in the representation. For instance, an ontology that treats “red” as a property differs from one that treats it as a value of a color attribute. Such commitments shape how knowledge is structured and reasoned about.

2.1 Logical representations

Logic-based approaches use formal languages with well-defined syntax and semantics to encode knowledge as sets of statements (axioms). They are foundational in KR due to their clarity and support for deductive reasoning.

2.1.1 Propositional logic

Propositional logic deals with atomic propositions (e.g., “It is raining”) and logical connectives (AND, OR, NOT, IMPLIES). While simple and tractable, it cannot represent objects or relations, limiting its expressive power.

2.1.2 First-order logic

First-order logic (FOL) extends propositional logic by adding predicates, functions, and quantifiers. It can represent objects, their properties, and relationships among them.

2.1.2.1 Quantifiers and variables

FOL uses universal (∀) and existential (∃) quantifiers. Variables allow statements like “All humans are mortal” (∀x human(x) → mortal(x)). This expressive capability makes FOL a widely used foundation for KR, though full FOL inference is only semi-decidable.

2.1.3 Non-classical logics

Non-classical logics modify or extend classical logic to handle specific phenomena. Modal logic adds operators for necessity and possibility; temporal logic handles time; default logic deals with exceptions. These logics address limitations of FOL in capturing context, change, or incomplete information.

2.2 Graph-based representations

Graph-based formalisms depict knowledge as networks of nodes and edges, where nodes represent concepts or entities and edges represent relations.

2.2.1 Semantic networks

Semantic networks are directed graphs where nodes denote objects or concepts and labeled arcs indicate relationships such as “is-a,” “has-part,” or “causes.” They were popular in early AI for natural language understanding but can suffer from ambiguity and lack of formal semantics.

2.2.2 Conceptual graphs

Conceptual graphs, based on Peirce’s existential graphs, provide a more formal graph notation. They use boxes for concepts and circles for relations, and can be translated into first-order logic. This formalism supports reasoning through graph operations such as join and projection.

2.3 Frame-based systems

Frame-based representations organize knowledge around structured objects called frames. Each frame represents a concept or individual and contains slots for attributes and relationships.

2.3.1 Slots and facets

A slot in a frame holds a value, which can be a number, a string, or a reference to another frame. Facets specify additional constraints or metadata, such as the allowed range of values, default values, or attached procedures (e.g., “if-needed” demons).

2.3.2 Inheritance hierarchies

Frames are typically arranged in a hierarchy where subclasses inherit slots and values from their parent classes. For example, a “Bird” frame might have a slot “canFly” with default value “true,” and a “Penguin” subclass can override it with “false.” Inheritance simplifies knowledge base maintenance but raises issues of multiple inheritance conflicts.

2.4 Rule-based systems

Rule-based representations encode knowledge as condition-action pairs (if-then rules). They are intuitive and widely used in expert systems.

2.4.1 Production rules

Production rules have the form “IF condition THEN action.” The condition typically matches patterns in working memory, and the action adds, removes, or modifies facts. They are used in forward and backward chaining reasoning.

2.4.2 Description logics

Description logics (DLs) are a family of formal languages for representing knowledge about concept hierarchies and roles. DLs provide decidable fragments of first-order logic and are the logical foundation of Web ontology languages like OWL. They support automatic classification and subsumption reasoning.

3.1 Deductive reasoning

Deductive reasoning infers new facts that logically follow from given premises. It guarantees truth preservation: if the premises are true, the conclusion must be true.

3.1.1 Forward chaining

Forward chaining starts with known facts and repeatedly applies rules to derive new facts. It is driven by data and is used for tasks like monitoring and prediction. The process continues until no new facts are generated.

3.1.2 Backward chaining

Backward chaining begins with a goal (a fact to be proved) and works backward, applying rules to reduce the goal to subgoals. It is common in expert systems for diagnostic and question-answering tasks.

3.2 Inductive reasoning

Inductive reasoning derives general rules or patterns from specific observations. It is inherently uncertain, as conclusions may go beyond the data. Machine learning techniques such as decision tree induction and rule learning are computational forms of induction.

3.3 Abductive reasoning

Abduction infers the most plausible explanation for observed facts. Given a rule “If A then B” and observed B, abduction hypothesizes A. It is used in diagnostic reasoning, plan recognition, and story understanding. Abduction can generate multiple hypotheses, which require evaluation criteria.

3.4 Non-monotonic reasoning

Non-monotonic reasoning allows conclusions to be retracted when new information is added. Classical logic is monotonic: once a fact is derived, it remains true. Non-monotonic formalisms handle defaults and exceptions.

3.4.1 Default logic

Default logic introduces default rules of the form “In the absence of evidence to the contrary, infer X.” For example, “If something is a bird, infer it can fly, unless it is known to be flightless.” Default logic produces multiple extensions (sets of beliefs) and is used for commonsense reasoning.

4.1 Ontology development

Ontologies are formal, explicit specifications of a shared conceptualization. Developing an ontology involves defining classes, properties, relationships, and constraints for a domain.

4.1.1 Top-level vs. domain ontologies

Top-level (or upper) ontologies describe very general concepts such as time, space, and matter, intended to be reusable across domains. Domain ontologies cover specific areas (e.g., medicine, finance) and often import terms from top-level ontologies.

4.1.2 Ontology languages (OWL, RDF)

The Web Ontology Language (OWL) and Resource Description Framework (RDF) are W3C standards for representing ontologies on the Semantic Web. RDF provides a simple triple structure (subject–predicate–object), while OWL adds expressive constructs for class axioms and reasoning (based on description logics).

4.2 Knowledge acquisition

Knowledge acquisition is the process of capturing knowledge from human experts or data sources.

4.2.1 Manual elicitation

Manual methods involve interviewing domain experts, analyzing documents, and using knowledge engineering techniques (e.g., concept sorting, laddering). This approach is time-consuming but can yield high-quality, validated knowledge.

4.2.2 Automated extraction

Automated extraction uses natural language processing (NLP), machine learning, and data mining to extract knowledge from text, databases, or the Web. Techniques include relation extraction, named entity recognition, and ontology learning.

4.3 Knowledge base maintenance

A knowledge base (KB) requires ongoing maintenance to ensure consistency, completeness, and currency. Tasks include resolving conflicts, versioning, merging new knowledge, and removing obsolete facts. Tools for KB maintenance often include debugging environments and reasoners to detect contradictions.

5.1 Expert systems

Expert systems are AI programs that mimic the decision-making ability of a human expert. They use a knowledge base of rules and facts and an inference engine to solve problems in domains such as medical diagnosis (MYCIN), fault diagnosis, and configuration.

5.2 Natural language processing

KR supports natural language understanding by providing semantic representations of text. Frameworks such as Abstract Meaning Representations (AMR) and frame semantics encode the meaning of sentences in a structured form, enabling question answering, machine translation, and dialogue systems.

5.3 Semantic Web

The Semantic Web extends the World Wide Web with machine-readable metadata. KR languages like RDF and OWL enable data to be linked and queried across sources. Applications include data integration, intelligent search, and knowledge graphs (e.g., DBpedia, Google Knowledge Graph).

5.4 Robotics and planning

In robotics, KR is used to represent a robot’s environment, goals, and actions. Planning systems (e.g., STRIPS, PDDL) rely on formal representations of states, actions, and effects to generate sequences of actions that achieve objectives. Knowledge of object affordances and spatial relations is also essential.

6.1 Scalability

As knowledge bases grow to millions or billions of facts, reasoning and storage become computationally demanding. Techniques such as indexing, parallel reasoning, and approximate inference are being developed to improve scalability.

6.2 Uncertainty and vagueness

Real-world knowledge often involves uncertainty (e.g., “It might rain”) and vagueness (e.g., “tall”). Traditional crisp logic struggles with such phenomena.

6.2.1 Probabilistic KR

Probabilistic knowledge representation extends logic with probabilities, allowing statements like “P(rain | cloudy) = 0.8.” Formalisms include Bayesian networks, Markov logic networks, and probabilistic description logics.

6.2.2 Fuzzy logic

Fuzzy logic handles vagueness by allowing truth values between 0 and 1. For example, “tall” can be defined by a membership function. Fuzzy KR is used in control systems, but its semantics and reasoning can differ significantly from classical approaches.

6.3 Integration with machine learning

Modern AI increasingly combines symbolic KR with machine learning. This integration aims to leverage the generalization power of neural networks while retaining the interpretability and logical rigor of KR. Approaches include neural-symbolic systems, graph neural networks applied to knowledge graphs, and differentiable reasoning.

6.4 Commonsense knowledge

One of the longest-standing challenges in KR is capturing the vast body of commonsense knowledge that humans take for granted—such as the fact that objects fall when dropped, or that people have daily routines. Large-scale projects like Cyc and ConceptNet have attempted to encode commonsense, but coverage and formalization remain incomplete. Future work may leverage large language models and crowdsourcing to populate richer commonsense knowledge bases.