🧠 Knowledge representation and reasoning
Knowledge representation and reasoning is the area of artificial intelligence that studies how facts, concepts and rules about a domain can be encoded in a form a machine can store, and how new conclusions can be derived from that encoding by sound or plausible inference.
What it is
Knowledge representation and reasoning (KR&R) asks two linked questions. The first is what structure should hold what a system knows. The second is what operations should turn that structure into answers it was never told directly. A representation fixes a vocabulary of individuals, classes and relations. It also fixes a syntax for statements and a semantics that says when a statement is true. A reasoning procedure then works over that semantics. It may check consistency, answer queries, classify new items or propose explanations.
The main families of formalisms are these:
- First-order and propositional logic.
- Semantic networks and frames, which group attributes around concepts.
- Description logics, which underlie modern ontology languages.
- Production rules and logic programs.
- Probabilistic graphical and probabilistic-logic models.
- Large knowledge graphs of subject–relation–object triples.
- Learned vector embeddings of entities and relations.
They differ mainly in expressiveness, computational cost and robustness to noise, as the table below summarizes.
| Formalism | Typical inference | Strength | Weakness |
|---|---|---|---|
| Logic, description logics | Deduction, classification | Soundness, explicit semantics | Brittle, costly at scale |
| Semantic networks, frames | Inheritance along links | Intuitive, concept-centred | Loose semantics unless formalized |
| Rules, logic programs | Forward/backward chaining | Readable, editable | Hand-built, exceptions hard |
| Probabilistic graphical and logic models | Belief propagation, weighted model counting | Handles uncertainty | Inference can be expensive |
| Knowledge graphs + embeddings | Link prediction | Scales, tolerates gaps | No proof, opaque |
| Language models | Generation, cloze filling | Broad coverage, no schema | Unreliable, hard to update |
Several kinds of reasoning are distinguished:
- Deductive reasoning derives what must follow from the stored facts.
- Inductive reasoning generalizes rules from examples.
- Abductive reasoning proposes the best explanation for an observation.
- Default (nonmonotonic) reasoning draws conclusions that hold typically but can be withdrawn when exceptions appear. "Birds fly" is a standard example.
Commonsense knowledge, by contrast, names a kind of content rather than an inference pattern. It covers the everyday background facts that texts seldom state, such as that people mount horses and not swords (Mihaylov & Frank 2018).
An ontology is the shared, explicit schema of classes and relations that the facts in a knowledge base are stated against. DBpedia, for instance, maps Wikipedia infobox templates from many languages onto one ontology, which in 2012 had 320 classes and 1,650 properties (Mendes et al. 2012).
The key idea
The classic core is entailment. A knowledge base KB entails a statement φ when φ is true in every interpretation that makes KB true. A reasoner tries to decide or approximate this relation. Neural and statistical approaches change the representation from symbols to vectors, and they replace exact entailment with a learned plausibility score. An influential early score is the translation model, TransE (Bordes et al., 2013) (Lin et al. 2015; Nguyen et al. 2018). It states that a relation should move the head entity onto the tail entity in vector space:
f(h, r, t) = − ‖ h + r − t ‖
Here h and t are vectors for the head and tail entities, and r is a vector for the relation. ‖·‖ is a norm (L1 or L2), and f is higher for triples judged more likely true. Training pushes f up for observed triples and down for corrupted ones made by swapping an entity. Missing facts are then predicted by ranking candidate tails.
The scheme has been extended in several ways. Multi-step paths can be scored by composing relation vectors, so that "born in city → city in state → state in country" supports nationality (Lin et al. 2015). A convolutional network can be applied to the stacked h, r and t vectors. That model contains the translation score as an exact special case (Nguyen et al. 2018). Bilinear and tensor-based scoring functions are a parallel line of work (Yang et al. 2014; Socher et al. 2013).
What is gained is graceful handling of incompleteness and noise. What is lost is the guarantee that a conclusion follows logically from the premises.
History and founding papers
The field's roots lie in McCarthy's (1958) proposal to give programs common sense through logic. Quillian (1968) introduced semantic networks. Minsky introduced frames in a 1974 MIT memo, published in 1975. Reiter (1980) and McCarthy (1980) formalized default and nonmonotonic reasoning. Brachman and Levesque's work on the tractability–expressiveness trade-off in the 1980s led to description logics, systematized by Baader et al. (2003). Pearl (1988) made probabilistic networks a standard way to reason under uncertainty.
Lexical semantic networks became computational resources in their own right. WordNet treated as a graph of synsets supports graph-ranking inference. PageRank over sense candidates reached 47.27% accuracy on unsupervised all-words disambiguation, a 7.7% relative error reduction over the Lesk algorithm (Mihalcea et al. 2004). Multilingual semantic networks followed at much larger scale (Navigli & Ponzetto 2010).
Inductive logic programming showed that logical rules could be learned from data, for example to map questions to database queries (Zelle & Mooney 1996). Encyclopedic knowledge graphs extracted from Wikipedia had their first releases in the late 2000s, and they had become standard infrastructure by the 2010s. These include DBpedia (Lehmann et al. 2015; Mendes et al. 2012) and YAGO3. YAGO3 merged ten language editions under the WordNet taxonomy. On top of an English-based core of 3.4m entities and 17m facts, the non-English editions added roughly 1m entities and 7m facts (Mahdisoltani et al. 2015).
The incompleteness of these graphs motivated work on knowledge-base completion (Nguyen et al. 2018; Lin et al. 2015). Gaps also corrupt training data. In the Freebase data examined by Min et al. (2013), 93.8% of persons lacked a recorded place of birth. Many "negative" examples used in distant supervision are therefore unrecorded positives (Min et al. 2013). Completion models responded by learning from graph structure and text together. FB15k-237 is a Freebase benchmark built by removing near-duplicate relations (Toutanova & Chen 2015). On it, textual relation vectors built compositionally by a CNN raised MRR by 2.4 points compared with treating each textual pattern as an atomic relation (Toutanova et al. 2015).
On the reasoning side, neuro-symbolic systems kept explicit logic. DeepProbLog attaches neural networks to predicates of the probabilistic logic language ProbLog and trains both through query-level gradients (Manhaeve et al. 2018).
How it is used today
Knowledge graphs feed many downstream tasks. Entity linking maps mentions to entries, or to NIL when the entity is absent. One such system reached about 80% accuracy on TAC-KBP 2009 against a knowledge base of about 818,000 entries (Dredze et al. 2010). Question answering over knowledge bases often works through semantic parsing into query graphs (Yih et al. 2015; Yih et al. 2016), or by decomposing complex questions (Talmor & Berant 2018).
Embeddings help when the graph itself is sparse. In a MetaQA 1-hop setting with the answer-bearing triples deleted, EmbedKGQA reached a hits@1 of 29.9, against 20.1 for plain ComplEx tail prediction. Subgraph-search methods can in principle score zero here (Saxena et al. 2020). Dialogue systems also draw on stored knowledge. Mem2Seq reads knowledge-base tuples through multi-hop memory and copies their objects into replies (Madotto et al. 2018). ConceptFlow walks one- and two-hop ConceptNet neighbourhoods to let conversations shift topic (Zhang et al. 2020).
Commonsense knowledge is a major active area. Curated resources such as ConceptNet can be extended automatically. Novel tuples ranked by a simple bilinear model were rated about as good as medium-confidence ConceptNet entries: 3.20 against 3.14 on a 0–4 scale, for the top 100 of 3,000 sampled tuples (Li et al. 2016). Retrieved commonsense triples also improve cloze-style reading comprehension. On the hard common-noun subset, they cut relative error by about 9% compared with the same attention-sum reader without knowledge (Mihaylov & Frank 2018). Benchmarks such as CommonsenseQA target exactly this kind of background knowledge (Talmor et al. 2019).
Language models have changed the picture. Probing showed that BERT-large, without fine-tuning, recalls many relational facts. It reached 57.1% precision@10 on open-domain questions, against 63.5% for a supervised, task-specific system (Petroni et al. 2019). Commonsense triples can likewise be mined from pretrained models (Davison et al. 2019). Models can also be trained to track facts that change over time (Dhingra et al. 2022).
Hwang et al. (2020) argue for combining symbolic and neural knowledge rather than replacing one with the other. Their COMET(BART) model has 406M parameters and was trained on the curated ATOMIC 2020 graph of 1.33M tuples. It scored about 12 points above few-shot GPT-3 in human evaluation, although GPT-3 has 175B parameters, roughly 430 times more (Hwang et al. 2020). Sentence-level alignments between text and triples supply training and probing data for this kind of integration (Elsahar et al. 2018).
Open questions
Reliability of implicit knowledge is unresolved. Language models handle one-to-one facts far better than many-to-many relations (Petroni et al. 2019). Numerical commonsense is weak. Zero-shot RoBERTa-Large picked the right number word 45.85% of the time, while humans scored 89.7% closed-book. Adding an adjective lowered RoBERTa's score to 35.66% (Lin et al. 2020). It remains unclear how to tell when a model's output is a stored fact, a plausible default or a confabulation.
Other questions concern how embeddings and logic fit together. Embedding models complete graphs but do not justify their conclusions. Logic justifies its conclusions but cannot derive conclusions that the stored facts do not entail, and gaps in those facts are pervasive (Min et al. 2013). How to give learned systems explicit, checkable reasoning steps, as neuro-symbolic languages attempt (Manhaeve et al. 2018), is still open. So is how to express defaults with exceptions and abductive explanation inside neural models.
Finally, curation and scale pull against each other. Automatically extracted commonsense tuples of low precision transferred poorly to unseen entities, even when they were far more numerous (Hwang et al. 2020). This suggests that the quality of a representation, and the ontology behind it, still matters even when the reasoner itself is learned.
Key papers
Related concepts
- Ontology engineering — Ontology engineering is the discipline that studies how to design, build, evaluate, maintain and reuse ontologies. An ontology here is an…
- Semantic parsing — Semantic parsing is the task of mapping a natural-language utterance to a formal, machine-interpretable representation of its meaning, such…
- Lexical semantics — Lexical semantics is the study of word meaning. It asks what words and multiword expressions denote, how a word's senses are organized, how…
- Language model — A language model is a probability distribution over sequences of tokens (words, subwords or characters). It is usually factored into…
More papers
Topics: 🕸️ Knowledge graphs & ontologies · 🧮 Reasoning
Shelves: 🤖 AI & machine learning
This page in Markdown → https://md.research.elamur.ai/free/en/concepts/knowledge-representation/