Knowledge & Reasoning — Reading Notes

1.Knowledge-Based Agents

In Topics 01–04, agents navigated explicit search spaces or solved constraint satisfaction graphs where states were atomic or factored variables. A Knowledge-Based Agent maintains an explicit, declarative representation of the world as a set of logical sentences, incorporates new percepts, and derives new truths through deductive inference.

1.1Knowledge Base (Facts & Rules)

The core principle of knowledge engineering is decoupling Domain Knowledge from the Inference Engine. The Knowledge Base (KB) is a set of sentences in a formal knowledge representation language.

An agent's decision loop follows a declarative cycle: it senses a percept, constructs a logical sentence asserting the observation (TELL), queries the KB for the next best action (ASK), and records its chosen action in the KB before acting in the environment.

1.2Propositional Logic

Propositional logic is the foundational formal language for declarative knowledge representation. Its syntax consists of proposition symbols (e.g., P, Q, B1,1) and five standard logical connectives:

• Negation (¬): ¬P is True iff P is False.
• Conjunction (∧): P ∧ Q is True iff both P and Q are True.
• Disjunction (∨): P ∨ Q is True iff at least one of P or Q is True.
• Implication (⇒): P ⇒ Q is False only when P is True and Q is False (vacuously True when P is False). Note that P ⇒ Q ≡ ¬P ∨ Q.
• Biconditional (⇔): P ⇔ Q is True iff P and Q have identical truth values.

1.3Models & Logical Entailment (KB ⊨ α)

A model m is a formal assignment of truth values (True/False) to all proposition symbols. If a vocabulary contains n symbols, there are exactly 2n possible models (possible worlds). A sentence α is true in model m if m satisfies α (written m ⊧ α). We denote the set of all satisfying models by M(α).

Entailment means that whenever the Knowledge Base is true, the conclusion α is mathematically guaranteed to be true. No counterexample world exists where KB holds and α fails.

1.4Logical Inference: Forward Chaining

While general propositional inference can be exponential, restricting the Knowledge Base to Horn Clauses enables high-speed, linear-time inference.

• A Definite Clause is a disjunction of literals with exactly one positive literal: (P1 ∧ … ∧ Pk) ⇒ Q ≡ ¬P1 ∨ … ∨ ¬Pk ∨ Q.
• A Horn Clause has at most one positive literal.

The Forward Chaining Algorithm (PL-FC-Entails) operates in a data-driven, eager manner:

1. Initialize an agenda with all known atomic base facts.
2. Maintain a count[c] table recording how many unsatisfied premises remain for each rule c.
3. While the agenda is non-empty, pop a fact p. For each rule containing p in its premise, decrement its count.
4. When count[c] == 0, all premises are satisfied: the rule fires and its conclusion is pushed onto the agenda.
5. If the target query q is generated, return True; if the agenda empties without reaching q, return False.

2.Probabilistic Reasoning

In the real world, strict logic often fails due to three fundamental challenges: laziness (too many exhaustive rules required), theoretical ignorance (lack of complete causal knowledge), and practical ignorance (noisy sensors and partial observability). Probabilistic reasoning quantifies continuous degrees of belief under uncertainty.

2.1Uncertainty & Degrees of Belief

Probabilities express an agent's numerical degree of belief given available evidence. A proposition A has a prior probability P(A) ∈ [0, 1]. The Full Joint Probability Distribution assigns a probability to every possible assignment across all random variables X1, …, Xn such that:

Any query probability is computed by marginalization (summing out all unobserved hidden variables Z):

2.2Conditional Probability & Bayes' Rule

Conditional probability defines belief in event A given that evidence B has definitely occurred:

Equating the two expressions for P(A ∧ B) yields Bayes' Rule:

where α = 1 / P(Effect) is the normalization factor ensuring that P(Cause | Effect) + P(¬Cause | Effect) = 1.0.

2.3Bayesian Networks & Compact Joint Factorization

A full joint distribution over n boolean variables requires 2n - 1 parameters, which is computationally intractable. A Bayesian Network is a Directed Acyclic Graph (DAG) that exploits conditional independence to represent joint distributions compactly.

• Nodes: Random variables (discrete or continuous).
• Directed Edges: Direct causal or probabilistic influence.
• Conditional Probability Tables (CPTs): Each node Xi has a conditional distribution P(Xi | Parents(Xi)).

If each node has at most k parents, a Bayesian network requires only O(n · 2k) parameters instead of O(2n).

2.4Conditional Independence & Markov Blanket

Two variables X and Y are conditionally independent given Z (denoted (X ⊥⊥ Y | Z)) if P(X | Y, Z) = P(X | Z). A variable X in a Bayesian network is conditionally independent of all other nodes in the entire network given its Markov Blanket:

2.5Probabilistic Inference (Exact & Sampling)

Probabilistic inference computes the posterior distribution P(Query | Evidence):

• Exact Inference by Enumeration: Sums terms from the factored joint distribution over all hidden unobserved variables: P(X | e) = α ∑y P(X, e, y).
• Approximate Likelihood Weighting: A Monte Carlo sampling algorithm that clamps evidence variables to their observed values and weights each generated sample by the probability of the evidence given parents: w = ∏ P(ej | parents(Ej)). Never rejects samples!

3.Temporal Reasoning & Hidden Markov Models

Standard Bayesian networks model static worlds. In dynamic domains (robot navigation, patient monitoring, financial tracking, speech recognition), the environment state evolves across discrete time slices t = 0, 1, 2, ….

3.1States Over Time & The Markov Property

Let Xt denote the set of unobservable (hidden) state variables at time t, and Et denote the observable sensor evidence variables at time t. The First-Order Markov Property states that the current state depends only on the immediately preceding state:

A temporal process is stationary if transition probabilities P(Xt | Xt-1) and sensor probabilities P(Et | Xt) do not change over time.

3.2Hidden Markov Model (HMM) Formulation

A Hidden Markov Model is a temporal probabilistic model with a single discrete hidden state variable Xt ∈ S and evidence variable Et ∈ O. An HMM is completely specified by the 5-tuple ⟨S, O, T, M, f0⟩:

• State Space (S): Set of discrete states {s1, …, sK}.
• Observation Space (O): Set of discrete observations {o1, …, oM}.
• Transition Matrix (T): Ti,j = P(Xt=sj | Xt-1=si).
• Emission Matrix (M): Mj,k = P(Et=ok | Xt=sj).
• Initial Prior Distribution (f0): f0(si) = P(X0=si).

3.3Filtering & The Forward Algorithm

Filtering (State Estimation) is the task of computing the belief state over current state Xt given all observations up to time t: f1:t = P(Xt | e1:t). The Forward Algorithm computes this recursively in a two-step Predict-Update cycle:

In matrix notation, let f1:t be the belief column vector and Ot be the diagonal emission matrix where (Ot)j,j = P(et | Xt=sj). The forward update is:

3.4Prediction, Smoothing, and Viterbi Decoding

An HMM supports four fundamental temporal inference queries:

• 1. Filtering (P(Xt | e1:t)): Tracks current state online as new data arrives. Time per step: O(|S|2).
• 2. Prediction (P(Xt+k | e1:t)): Projects belief k steps into the future using f1:t+k = (TT)k f1:t. The belief distribution eventually converges to the stationary distribution of T.
• 3. Smoothing (P(Xk | e1:t) for k < t): Computes historical state estimates in hindsight by combining forward messages from the past with backward messages from the future (Forward-Backward algorithm).
• 4. Most Likely Sequence (Viterbi Algorithm): Finds the single sequence of hidden states x1:t* that maximizes the posterior probability P(x1:t | e1:t) (equivalently, the joint P(x1:t, e1:t)) using dynamic programming across the trellis:
  m_t[j] = max_i (m_t-1[i] · T_i,j) · P(e_t | s_j)

4.Paradigm Comparison

4.1Logic vs. Bayesian Networks vs. Hidden Markov Models

Comparing the three core reasoning paradigms across representation, uncertainty handling, temporal dynamics, and computational complexity:

5.Practice Exercises & Worked Solutions

Initial Setup:
  Agenda = [SymptomA, SymptomB]
  Inferred = {SymptomA: True, SymptomB: True}
  count table: R1 = 2, R2 = 2, R3 = 1, R4 = 1

Step 1: Pop SymptomA
  - Decrement R1 count: count[R1] = 1 (remains un-fired).

Step 2: Pop SymptomB
  - Decrement R1 count: count[R1] = 0 → FIRES R1! Add ConditionC to Agenda.
  - Decrement R3 count: count[R3] = 0 → FIRES R3! Add SymptomD to Agenda.
  - Agenda = [ConditionC, SymptomD].

Step 3: Pop ConditionC
  - Decrement R2 count: count[R2] = 1.

Step 4: Pop SymptomD
  - Decrement R2 count: count[R2] = 0 → FIRES R2! Add DiseaseE to Agenda.
  - Agenda = [DiseaseE].

Step 5: Pop DiseaseE
  - Decrement R4 count: count[R4] = 0 → FIRES R4! Add PrescribeMedicationF to Agenda.
  - Agenda = [PrescribeMedicationF].

Step 6: Pop PrescribeMedicationF
  - Query goal reached! Return True.

1. Compute joint probability for Disease = True:
   P(+ ∧ Disease) = P(+ | Disease) · P(Disease)
                     = 0.99 × 0.001 = 0.000990

2. Compute joint probability for Disease = False:
   P(+ ∧ ¬Disease) = P(+ | ¬Disease) · P(¬Disease)
                      = 0.02 × (1 - 0.001) = 0.02 × 0.999 = 0.019980

3. Compute total marginal evidence P(+):
   P(+) = P(+ ∧ Disease) + P(+ ∧ ¬Disease)
        = 0.000990 + 0.019980 = 0.020970

4. Compute posterior P(Disease | +):
   P(Disease | +) = P(+ ∧ Disease) / P(+)
                  = 0.000990 / 0.020970 ≈ 0.04721 (4.72%)

1. Compact Joint Factorization:
   P(B, E, A, J, M) = P(B) · P(E) · P(A | B, E) · P(J | A) · P(M | A)

2. Numerical Evaluation for (b, ¬e, a, j, ¬m):
   P(b)    = 0.001
   P(¬e)   = 1 - 0.002 = 0.998
   P(a | b, ¬e) = 0.94
   P(j | a)     = 0.90
   P(¬m | a)    = 1 - 0.70 = 0.30

   P(b, ¬e, a, j, ¬m) = 0.001 × 0.998 × 0.94 × 0.90 × 0.30
                       = 0.00093812 × 0.27
                       = 0.0002532924 (0.0253%)

--- DAY 1 (Observation U1 = true) ---
1. Predict: P(R1) = T^T · f0
   P(R1=True)  = 0.70 × 0.50 + 0.30 × 0.50 = 0.50
   P(R1=False) = 0.30 × 0.50 + 0.70 × 0.50 = 0.50

2. Update with U1 = true (P(u|R)=0.90, P(u|¬R)=0.20):
   Unnormalized R1=True:  0.90 × 0.50 = 0.450
   Unnormalized R1=False: 0.20 × 0.50 = 0.100
   Sum = 0.450 + 0.100 = 0.550 → α = 1 / 0.550

   f1 = ⟨ 0.450/0.550, 0.100/0.550 ⟩ = ⟨ 0.8182, 0.1818 ⟩
   P(Rain1 | u1) ≈ 81.82%

--- DAY 2 (Observation U2 = true) ---
1. Predict: P(R2 | u1) = T^T · f1
   P(R2=True)  = 0.70 × 0.8182 + 0.30 × 0.1818 = 0.5727 + 0.0545 = 0.6273
   P(R2=False) = 0.30 × 0.8182 + 0.70 × 0.1818 = 0.2455 + 0.1273 = 0.3727

2. Update with U2 = true:
   Unnormalized R2=True:  0.90 × 0.6273 = 0.5645
   Unnormalized R2=False: 0.20 × 0.3727 = 0.0745
   Sum = 0.5645 + 0.0745 = 0.6391 → α = 1 / 0.6391

   f2 = ⟨ 0.5645/0.6391, 0.0745/0.6391 ⟩ = ⟨ 0.8833, 0.1167 ⟩
   P(Rain2 | u1, u2) ≈ 88.33%

--- Time t = 1 (Observation U1 = true) ---
P(R1=Rain) = 0.70 × 0.50 + 0.30 × 0.50 = 0.50   (prior pushed one step through T)
m1[Rain]   = P(R1=Rain) · P(u|Rain)   = 0.50 × 0.90 = 0.450
m1[¬Rain]  = P(R1=¬Rain) · P(u|¬Rain) = 0.50 × 0.20 = 0.100

--- Time t = 2 (Observation U2 = false: P(¬u|Rain)=0.10, P(¬u|¬Rain)=0.80) ---
For State Rain at t=2:
  From Rain:   m1[Rain] × T[Rain→Rain]   = 0.450 × 0.70 = 0.3150
  From ¬Rain:  m1[¬Rain] × T[¬Rain→Rain] = 0.100 × 0.30 = 0.0300
  Max = 0.3150 (from Rain); Backpointer = Rain
  m2[Rain] = 0.3150 × P(¬u|Rain) = 0.3150 × 0.10 = 0.03150

For State ¬Rain at t=2:
  From Rain:   m1[Rain] × T[Rain→¬Rain]   = 0.450 × 0.30 = 0.1350
  From ¬Rain:  m1[¬Rain] × T[¬Rain→¬Rain] = 0.100 × 0.70 = 0.0700
  Max = 0.1350 (from Rain); Backpointer = Rain
  m2[¬Rain] = 0.1350 × P(¬u|¬Rain) = 0.1350 × 0.80 = 0.10800

--- Termination & Backtracking ---
At t=2, max(m2[Rain]=0.03150, m2[¬Rain]=0.10800) is m2[¬Rain] (0.10800).
- State at t=2: ¬Rain
- Backpointer from ¬Rain at t=2 points to: Rain at t=1.

Optimal Most Likely Sequence: [Rain, ¬Rain]