Knowledge Representation and Reasoning

Knowledge representation and reasoning is a field of artificial intelligence concerned with expressing information about the world in computationally usable forms and developing methods for drawing conclusions from it. Representation determines what a system can describe and what its descriptions mean; reasoning determines how those descriptions support answers, explanations, and decisions. The field encompasses logical, structured, probabilistic, and hybrid approaches, rather than a single language or reasoning technique. Its central problem is to connect meaningful descriptions of a domain with effective computation. (cs.ubc.ca)

Foundations

A representation is not simply a collection of stored facts. It provides conventions for describing entities, properties, relationships, events, and other features of a domain, together with an account of how those descriptions can be interpreted and manipulated. A knowledge base contains particular statements expressed using such conventions; a representation formalism supplies the language and its associated reasoning framework. (cs.ubc.ca)

In an influential 1993 analysis, Randall Davis, Howard Shrobe, and Peter Szolovits identified five roles of a knowledge representation:

• A surrogate for the world: it enables reasoning about situations without directly acting in them.
• A set of ontological commitments: it determines which kinds of things and distinctions the system recognizes.
• A partial theory of intelligent reasoning: it specifies which inferences are permitted or encouraged.
• A medium for efficient computation: its organization affects which conclusions can be reached economically.
• A medium of human expression: it enables people to communicate knowledge to a computational system.

These roles can conflict. A representation convenient for human explanation may not be the most computationally efficient, while a highly restricted language may make useful domain distinctions difficult to express. (groups.csail.mit.edu)

Syntax, semantics, and inference

Formal representation systems distinguish three components:

1. Syntax defines permissible symbols and expressions.
2. Semantics specifies what those expressions mean and when they are satisfied.
3. Inference procedures manipulate expressions to answer questions or obtain conclusions.

For example, a language might permit the expression LocatedIn(parcel, warehouse). Its syntax determines whether this is a well-formed expression; its semantics determines how the named objects and relationship are interpreted. An inference procedure might combine it with other statements to determine where the parcel can be collected. Precise semantics makes it possible to assess reasoning independently of a particular implementation. (people.cs.pitt.edu)

Logical representation and deduction

Logic supplies languages in which statements and their relationships can be defined precisely. Propositional logic treats propositions as units that may be true or false. First-order logic additionally describes individuals, predicates, variables, and quantification, allowing general statements about objects and their relationships. (artint.info)

Consider an illustrative knowledge base:

It follows that:

The general rule and the particular fact jointly support a conclusion that need not have been stored explicitly. This is an instance of deductive reasoning. The conclusion follows from the premises; the derivation does not independently establish that the premises accurately describe the real world. (cs.unca.edu)

A fundamental distinction separates logical consequence from derivability:

means that the statement $\varphi$ is true in every interpretation satisfying the knowledge base $K$, whereas

means that an inference system can derive $\varphi$ from $K$. Soundness requires that derived conclusions be logical consequences. Completeness, relative to a specified language and semantics, requires that all logical consequences be derivable. These are properties of a reasoning system, not guarantees that its domain assumptions are correct. (cl.cam.ac.uk)

Major representation approaches

Rules and logic programs

Rule-based representations express relationships between conditions and conclusions. A rule can state, for example, that an item is eligible for dispatch if it is packed and has an assigned destination. Reasoners can apply such rules to facts and intermediate conclusions. (artint.info)

Two common strategies are forward chaining, which starts from available facts and derives consequences, and backward chaining, which starts from a query and searches for supporting rules and premises. Their usefulness depends on the structure of the knowledge base and the questions being asked. Rule systems also differ in their treatment of negation, missing information, and assumptions; similar-looking rule notation does not by itself establish equivalent meanings. (cs.ubc.ca)

Frames and semantic networks

A frame organizes knowledge around a structured description of an object or stereotypical situation. Its slots can describe participants, attributes, expected values, or associated procedures. Marvin Minsky’s 1974 proposal emphasized larger, interconnected structures combining factual and procedural knowledge, rather than representing everything as isolated statements. (mit.edu)

Semantic networks organize concepts or individuals as nodes connected by labeled relationships. Hierarchical links can support inheritance, but the consequences of a link depend on its defined meaning: a subclass relationship is not the same as membership, physical containment, or part–whole structure. A diagram becomes a formal reasoning representation only when the interpretation of its relationships is specified. (groups.csail.mit.edu)

Ontologies and description logics

An ontology specifies concepts and relationships used to describe a domain. It can provide a shared vocabulary and formal axioms that support interpretation across independently developed systems. Ontology engineering therefore involves decisions about meaning and domain structure, not merely assigning labels to data. (artint.info)

Description logics provide formal languages for describing classes, individuals, and relationships. Associated reasoning tasks include determining whether one class is a subclass of another, whether an individual belongs to a class, and whether a collection of axioms is consistent. The Web Ontology Language, particularly OWL 2 DL, provides standardized ontology modeling grounded in this tradition. (w3.org)

Knowledge graphs

A knowledge graph represents entities and relationships in graph form. It may contain instance-level facts, schema information, and links between sources. Its reasoning capabilities depend on the semantics and methods attached to it: graph connectivity alone does not determine which new statements follow. (artint.info)

A useful distinction separates logical inference, which derives consequences of specified axioms, from graph completion, which predicts potentially missing relationships using learned patterns. A predicted relationship may be plausible without being logically entailed. (arxiv.org)

Probabilistic representations

When information is uncertain, a system can represent degrees of belief rather than only categorical assertions. Probabilistic graphical models, including Bayesian networks, describe dependencies among variables and support inference about unobserved quantities from evidence. Such models distinguish uncertainty about a proposition from the logical structure of that proposition. (cl.cam.ac.uk)

Probabilistic and logical approaches can be combined. A system may use explicit relationships and rules to describe a domain while assigning uncertainty to observations, hypotheses, or relationships. Their integration requires a clear account of how the logical and probabilistic components interact. (arxiv.org)

Forms of reasoning

Reasoning in this field extends beyond deduction:

• Abduction identifies hypotheses that could explain observations in conjunction with background knowledge. An explanation is not automatically established as true.
• Induction develops generalizations from examples or observations.
• Probabilistic inference updates or computes beliefs given evidence.
• Constraint reasoning searches for assignments satisfying restrictions.
• Planning uses descriptions of states, actions, and goals to find suitable courses of action.

These activities answer different questions. Asking what necessarily follows from a model is different from asking what could explain an observation, what is probable, or which action sequence achieves a goal. (artint.info)

Monotonic and nonmonotonic reasoning

Classical logical consequence is monotonic: adding premises does not invalidate previously entailed conclusions. Everyday reasoning often depends on assumptions that may need revision. Nonmonotonic reasoning formalizes this defeasible character. For example, a system may assume that a scheduled delivery proceeds normally unless evidence of cancellation becomes available. (cs.ubc.ca)

Default rules must therefore be distinguished from universal implications. “Deliveries normally proceed as scheduled” allows exceptions; “every scheduled delivery proceeds” does not. Confusing the two changes the consequences of the representation. (arxiv.org)

Missing information, identity, and change

Open-world and closed-world assumptions

Under an open-world assumption, absence of a statement does not establish its falsity. OWL uses this approach: an ontology that does not state whether an individual has a particular relationship may simply be incomplete. Under a closed-world assumption, a system treats information not established within a designated scope as false. The appropriate choice depends on whether that scope is intended to contain complete information. (w3.org)

Identity is another separate modeling choice. OWL does not automatically assume that two different names denote different individuals. Distinctness must be established when it matters. Otherwise, information sources using different identifiers may still refer to the same entity. (w3.org)

Actions and the frame problem

Representing actions requires describing both what changes and what remains unchanged. The frame problem concerns the efficient representation of persistence: moving an object may change its position without changing its color or ownership. A system needs a principled way to capture these non-effects without enumerating every unaffected property for every action. (cl.cam.ac.uk)

Related difficulties include the qualification problem, concerning potentially numerous conditions that prevent an action from having its expected effect, and the ramification problem, concerning indirect consequences. These problems show why action representation requires more than a list of immediate effects. (cl.cam.ac.uk)

Historical development

Logical representation was an early direction in symbolic artificial intelligence. In Programs with Common Sense, published in 1959, John McCarthy proposed an “Advice Taker” that would use formally expressed information to reason about what to do. This approach made explicit knowledge and inference central to intelligent behavior. (www-formal.stanford.edu)

During the 1970s, structured approaches investigated how knowledge could be organized around familiar objects and situations. Minsky’s A Framework for Representing Knowledge, issued as an MIT memorandum in June 1974 and reprinted in 1975, became an influential statement of the frame approach. (mit.edu)

Subsequent work developed formal ontology languages, reasoning under uncertainty, defeasible inference, and combinations of representation with learning. OWL illustrates the standardization of explicit ontology languages, while research connecting KRR with machine learning explores complementary uses of knowledge, data, and learned representations. (w3.org)

Applications and integration with learning

Knowledge-based systems use representation and reasoning for tasks such as explaining observations, answering questions, integrating information sources, checking domain constraints, and planning actions. Explicit representations can make assumptions and inference steps inspectable, particularly when explanations identify the facts and rules supporting a conclusion. (cs.ubc.ca)

Machine learning can acquire relationships or rules from examples, predict missing information, or guide search within a reasoner. Conversely, explicit knowledge can constrain learning and help explain its outputs. The division is therefore not simply between systems that “learn” and systems that “reason”; individual systems can do both. (arxiv.org)

Neuro-symbolic artificial intelligence studies combinations of neural and symbolic methods. Approaches include translating symbolic knowledge into neural representations and connecting learned components with explicit reasoning systems. An important technical issue is whether such translations preserve the intended semantics. A useful prediction or numerical approximation is not, without further conditions, equivalent to a sound logical inference. (doi.org)

Limitations and design trade-offs

Expressiveness and computational cost are closely connected. General first-order reasoning is only semidecidable: a suitable proof procedure can eventually find a proof when a consequence holds, but it need not terminate when no proof exists. Restricting a representation language can improve decidability or tractability, at the cost of limiting what can be expressed directly. (cl.cam.ac.uk)

Model construction and maintenance remain substantial difficulties. Knowledge from different sources may use incompatible terminology, entity boundaries, or assumptions. Systems also evolve, introducing distinctions that their original designers did not anticipate. Consistency within a formal model does not resolve disagreements about how the domain should be modeled. (artint.info)

Explanation and correctness must be distinguished. An inference trace can show how a conclusion follows from premises, but it cannot by itself establish that those premises are true, complete, or appropriate to the situation. Evaluation consequently concerns both the reasoning mechanism and the representation’s adequacy for its intended domain and tasks. (artint.info)

References

1. What is a Knowledge Representation?groups.csail.mit.edu
2. Artificial Intelligence — 1.4 Knowledge Representationcs.ubc.ca
3. Introduction to Knowledge Representation and State Space Searchpeople.cs.pitt.edu
4. Introduction to knowledge representation and reasoningcl.cam.ac.uk
5. Introduction to Knowledge Representationcs.unca.edu
6. Chapter 5 Propositions and Inferenceartint.info
7. Artificial Intelligence — 5 Propositions and Inferencecs.ubc.ca
8. Artificial Intelligence — 5.3 Knowledge Representation Issuesartint.info
9. Artificial Intelligence, Third Edition, Python Codeartint.info
10. Part II Reasoning and Planning with Certaintyartint.info
11. Artificial Intelligence — 13.3 Ontologies and Knowledge Sharingartint.info
12. OWL 2 Web Ontology Language Primer (Second Edition)w3.org