Knowledge Representation & Reasoning

Key ideas

Knowledge is not information. In the DIKW pyramid, data are raw symbols, information is interpreted data, knowledge is information actively integrated into our model of the world, and wisdom is knowing when to use it¹. Top-down (symbolic) AI rests on representing knowledge and reasoning with it.

Representations form a spectrum¹. At the simple end is algorithmic knowledge (a program: directly usable by a computer, but inflexible); at the other end natural language (most expressive, unusable for automatic reasoning). In between: network representations (semantic nets, stored as object–attribute–value triples), hierarchical ones (frames with slots, default values and inheritance; a scenario is a frame for a situation that unfolds in time), procedural ones (production rules) and logic (predicate logic, Horn clauses in Prolog, description logics).

Propositional semantics (truth tables)^2,7:

Key equivalences: $P_1,\dots,P_n \models C$ iff $(P_1\land\dots\land P_n)\to C$ is a tautology iff $\{P_1,\dots,P_n,\lnot C\}$ is unsatisfiable; unsatisfiable premises entail everything². Also $A\to B \equiv \lnot A\lor B \equiv \lnot B\to\lnot A$ (contrapositive), but $A\to B$ is not equivalent to $B\to A$.

Normal forms and completeness. Every sentence has an equivalent CNF (a conjunction of clauses); the truth-table method writes one clause per false row⁷. $\{\lnot,\land,\lor\}$, $\{\lnot,\to\}$ and NAND alone are functionally complete; $\{\land,\lor,\to\}$ is not, because every sentence built from them is true when all letters are true, so it cannot express $\lnot A$⁷. Formulas without $\lnot$ express exactly the monotone conditions — making one more letter true can never make them false⁸. So "at least $k$ of $n$ true" is expressible, while "exactly $k$" and parity are not.

Resolution works on CNF clauses: from $(A\lor X)$ and $(\lnot A\lor Y)$ infer $(X\lor Y)$. To prove $KB\models\alpha$, add $\lnot\alpha$ and derive the empty clause. It is sound and refutation-complete; in first-order logic it needs unification (a substitution making two literals identical, ideally the most general one)³.

First-order logic. Truth is relative to an interpretation (domain + meanings). There is no truth-table test for FOL validity: a sentence has infinitely many interpretations, though one counter-interpretation refutes it⁷. Quantifier order matters⁷. Useful facts: $\exists y\,\forall x\,L(x,y)\models\forall x\,\exists y\,L(x,y)$ but not conversely; $\lnot\forall x\,F(x)\equiv\exists x\,\lnot F(x)$⁷; if $x$ is not free in $G$, $\forall x\,(F(x)\to G)\equiv\exists x\,F(x)\to G$ and $\exists x\,(F(x)\to G)\equiv\forall x\,F(x)\to G$. $N(a)\land N(b)\land N(c)$ does not entail $\forall x\,N(x)$, since the domain may contain unnamed objects⁷.

Rule-based (expert) systems have a working memory of facts, a knowledge base of IF–THEN rules and an inference engine¹. Forward chaining is data-driven: fire rules whose conditions hold until nothing new (or the goal) is added. Backward chaining is goal-driven: pick rules that conclude the goal and recursively prove their conditions — natural for diagnosis ¹. The engine loops match → resolve conflicts → act; matching is the expensive phase, and the Rete algorithm keeps partial matches between cycles and only processes changes to working memory⁴. Conflict resolution picks one instantiation from the conflict set: rule order, salience, recency (newest fact), specificity (most conditions); refraction stops the same instantiation firing twice⁴.

Near-miss (arch) learning (Winston) updates a model from one example at a time⁵:

Example: the model allows only red; a yellow positive example → extend-set to {red, yellow}. Positive examples with incandescent and with fluorescent bulbs → climb-tree to "light source". A near miss that differs only by an orange colour → forbid-link orange⁵.

Knowledge-graph embeddings score triples $(s, r, o)$⁶: TransE wants $\mathbf{e}_s+\mathbf{e}_r\approx\mathbf{e}_o$ (small distance = plausible fact); DistMult uses a diagonal bilinear score, which is symmetric in $s$ and $o$; ComplEx uses complex vectors and the conjugate of the object, so it can model antisymmetric relations; RotatE rotates $\mathbf{e}_s$ element-wise by unit-modulus $r_k=e^{i\theta_k}$.

Formulas

RotatE: $\mathbf{e}_o\approx\mathbf{e}_s\circ\mathbf{r}$; a symmetric relation needs $\mathbf{r}\circ\mathbf{r}=\mathbf{1}$, i.e. every $\theta_k\in\{0,\pi\}$. ComplEx with a purely real $\mathbf{r}$ is symmetric again.

Worked example

$KB=\{P\lor Q,\ \lnot P\lor R,\ \lnot Q\lor S,\ \lnot R\}$. Does $KB\models S$? Add $\lnot S$ and resolve: $(\lnot P\lor R)+\lnot R\Rightarrow\lnot P$; $(P\lor Q)+\lnot P\Rightarrow Q$; $(\lnot Q\lor S)+Q\Rightarrow S$; $S+\lnot S\Rightarrow$ empty clause. So $KB\models S$. Check by truth table: only 1 of the 16 valuations satisfies $KB$ ($P,R$ false; $Q,S$ true), and $S$ is true on it.

Common pitfalls

• Knowledge ≠ information: knowledge is information integrated into a world model¹.
• Entailment vs implication: $P\models Q$ is a claim about sentences; it holds iff $P\to Q$ is a tautology². And $P\not\models Q$ does not give $P\models\lnot Q$.
• Contradictory premises make any argument valid — validity is not truth².
• Quantifier order matters: "someone is loved by everyone" entails "everyone loves someone", not the reverse⁷.
• Forward = data-driven, backward = goal-driven, not the other way round¹.
• Drop-link generalises. It removes a requirement because positive examples showed it does not matter; only near misses specialise (require/forbid)⁵.
• A near miss differs from the model in exactly one way; an example differing in two ways teaches nothing⁵.
• DistMult cannot model antisymmetric relations: swapping $s$ and $o$ leaves its score unchanged⁶.