Unit V: NLP, Learning & Expert Systems — Artificial Intelligence

Section 01

Natural Language Processing — Introduction & Syntactic Processing

Every time you type a query into a search engine, ask a voice assistant a question, or receive an auto-translated email, you are using Natural Language Processing (NLP). NLP is the sub-field of AI that enables computers to understand, interpret, and generate human language — the most natural and complex form of human communication.

Human language is extraordinarily difficult to process automatically. The sentence "I saw the man with the telescope" is genuinely ambiguous — did I use the telescope, or did the man have it? Resolving such ambiguities requires not just grammar but world knowledge, context, and pragmatic reasoning. NLP tackles this challenge through a pipeline of processing stages, each building on the last.

The NLP Processing Pipeline

NLP systems process language through a layered pipeline of analysis. Each layer handles a different aspect of meaning:

Figure 1.1 — The NLP processing pipeline. Each layer adds a deeper level of analysis, from word forms up to the speaker's communicative intent. Each stage's output feeds the next.

Morphological and Lexical Analysis

Morphological analysis decomposes words into their component morphemes (stems, prefixes, suffixes). The word "unpredictably" → un + predict + able + ly. This helps map surface word forms to their base meanings. Lexical analysis (tokenisation + part-of-speech tagging) assigns each token a grammatical category.

Word	Morphological Analysis	POS Tag	Lemma
The	definite article (no morphemes)	DT (determiner)	the
doctor	doctor (root)	NN (noun, singular)	doctor
treated	treat + ed (past tense)	VBD (verb, past)	treat
patients	patient + s (plural)	NNS (noun, plural)	patient
carefully	care + ful + ly	RB (adverb)	carefully

Syntactic Processing — Parsing

Syntactic processing (parsing) determines the grammatical structure of a sentence — how words group into phrases and how phrases relate to each other. The result is a parse tree (or phrase structure tree) that makes the hierarchical structure explicit.

Context-Free Grammar (CFG)

A CFG defines the syntax of a language through production rules of the form X → Y₁ Y₂ … Yₙ, where X is a non-terminal symbol and Y₁…Yₙ are terminals or non-terminals. Standard sentence-level rules:

-- Phrase structure rules --
S   → NP VP                   -- Sentence = Noun Phrase + Verb Phrase
NP  → Det N | Det N PP      -- NP = Det + Noun (optional PP)
VP  → V NP | V NP PP       -- VP = Verb + NP (optional PP)
PP  → P NP                   -- PP = Preposition + NP
Det → the | a | an
N   → doctor | patient | hospital
V   → saw | treated | found
P   → with | in | on

Worked Example Parse Tree for "The doctor treated the patient"

Figure 1.2 — Parse tree for "The doctor treated the patient carefully." S splits into NP (subject) and VP (predicate). The VP further divides into V, object NP, and AdvP. This hierarchical structure makes grammatical relationships explicit.

Structural Ambiguity — "I saw the man with the telescope"

Parse	Structure	Meaning
Parse 1	VP = [V [NP the man [PP with the telescope]]]	The man had the telescope (PP modifies NP)
Parse 2	VP = [V [NP the man] [PP with the telescope]]	I used the telescope to see him (PP modifies VP)

Both parses are grammatically valid — a parser returns both. Choosing the correct one requires semantic and world knowledge. This is a core challenge in NLP.

Key Insight — Parsing Algorithms

Two main parsing strategies: Top-Down (Recursive Descent) — start from S, expand rules until terminals match the input. Fast but may explore many dead ends. Bottom-Up (Shift-Reduce / CYK) — start from terminals, combine into larger phrases. The CYK algorithm runs in O(n³|G|) and handles all CFGs. Modern NLP uses neural parsers (transformers) that run in linear time with much higher accuracy than grammar-based parsers.

🎯 Quick Check: The sentence "Flying planes can be dangerous" has two interpretations. Which syntactic property explains this ambiguity?

✅ Correct! "Flying planes can be dangerous" has two parse trees: (1) [NP Flying planes] [VP can be dangerous] — planes that are flying are dangerous; (2) [NP-gerund Flying planes] [VP can be dangerous] — the activity of flying planes is dangerous. "Flying" is a present participle that can function as both an adjective (modifying "planes") and a gerund (head of an NP). This is structural (syntactic) ambiguity — the same word sequence has two valid phrase structure trees.

Section 02

Semantic Analysis, Discourse & Pragmatic Processing

A parse tree tells us structure — but not meaning. "Colourless green ideas sleep furiously" is perfectly grammatical but semantically nonsensical. Semantic analysis maps parsed structures onto representations of meaning, resolving word-sense ambiguity and establishing relationships between entities. Discourse processing then links sentences together, while pragmatics addresses the speaker's intent beyond literal meaning.

Semantic Analysis

Compositional Semantics

Compositional semantics (the Principle of Compositionality, Frege) holds that the meaning of a complex expression is determined by the meanings of its parts and the rules combining them. Semantic analysis maps syntactic parse trees to logical forms using this principle.

Worked Example From Parse Tree to Logical Form

Sentence: "The doctor treated every patient"

Phrase	Semantic Rule	Logical Form
"the doctor"	Definite NP → specific individual	`ιx Doctor(x)` (the unique doctor)
"every patient"	Universal NP → quantified variable	`∀y Patient(y)`
"treated"	Transitive verb → binary predicate	`Treated(subj, obj)`
Full sentence	S → compose all parts	`∀y Patient(y) → Treated(doctor₁, y)`

Word Sense Disambiguation

Many words have multiple senses. "bank" can mean a financial institution or a river bank. WSD assigns the correct sense based on context words:

Sentence	Ambiguous Word	Context Clues	Correct Sense
"The patient's condition improved"	patient (adj/noun)	Possessive 's + condition	Noun: sick person
"Be patient while waiting"	patient (adj/noun)	Imperative + "while waiting"	Adjective: tolerant
"He deposited money at the bank"	bank	deposited, money	Financial institution
"The fish swam near the bank"	bank	fish, swam	River bank

Discourse Processing

Real language is not isolated sentences — it is connected text. Discourse processing deals with how sentences in a text relate to each other to create coherent meaning.

Co-reference Resolution

pronoun → antecedent

"The doctor examined John. She found he had pneumonia." — "She" refers to the doctor, "he" refers to John. Must link pronouns and definite NPs to the entities they refer to.

Discourse Relations

causal, temporal, contrast

"The patient felt better. The fever had broken." — Second sentence is a causal explanation of the first. Discourse relations (RST theory) classify these: Cause, Elaboration, Contrast, Sequence.

Topic Segmentation

coherent topic chains

Long documents split into topic segments. A medical report has sections: Chief Complaint → History → Examination → Diagnosis → Treatment. Segmentation identifies these boundaries automatically.

Information Structure

given vs. new information

"The doctor arrived. She immediately examined the patient." — "The doctor" is given (introduced); "She immediately examined" is new information. Tracks what is in common ground vs. newly asserted.

Pragmatic Processing

Pragmatics — Language in Context

Pragmatics studies how context and social conventions influence the interpretation of utterances beyond their literal linguistic meaning. The same sentence can mean very different things in different situations.

Key concepts: Speech Acts (Austin, Searle) — utterances as actions (assertions, requests, promises, warnings). Implicature (Grice) — what is suggested but not literally said. Presupposition — background assumptions an utterance takes for granted.

Worked Example Pragmatic Interpretation — Beyond Literal Meaning

Utterance	Literal Meaning	Pragmatic (Intended) Meaning	Mechanism
"Can you pass the salt?"	Query about physical ability	Request: please pass the salt	Indirect Speech Act
"It's cold in here."	Statement about temperature	Request: please close the window	Implicature
"John stopped smoking."	Statement about behaviour change	Presupposes John used to smoke	Presupposition
"Some students passed."	At least one student passed	Implicature: NOT all students passed	Gricean Maxim of Quantity

Grice's Cooperative Principle — Four Maxims

Maxim	Principle	Violation Example
Quantity	Be as informative as required, not more or less	"Some patients have the disease" when all do — implies not all
Quality	Say only what you believe to be true	Sarcasm violates this deliberately
Relation	Be relevant to the conversation	Changing subject abruptly signals avoidance
Manner	Be clear, brief, and orderly	Deliberately obscure phrasing signals special meaning

🎯 Quick Check: In co-reference resolution, what challenge does the sentence "The trophy didn't fit in the suitcase because it was too big" present for NLP systems?

✅ Correct! This is the famous "Winograd Schema Challenge" — a co-reference problem requiring real-world knowledge. Grammatically, "it" could refer to either the trophy or the suitcase. To resolve it correctly (it = trophy), the system must know: if X can't fit into Y because it's too big → "it" is X (the thing that's too big for the container). This requires common-sense knowledge about containment and size relationships. Solving Winograd schemas is considered a key benchmark for NLU and has been used to test large language models.

Section 03

Forms of Learning & Inductive Learning

A system that can only do what it was explicitly programmed to do will always be limited by the programmer's knowledge. Machine learning breaks this barrier: systems that learn from experience improve their performance on tasks without being explicitly reprogrammed. This section surveys the major paradigms of learning and examines inductive learning — the process of generalising from specific examples to general rules.

Learning Agent (Mitchell, 1997)

A computer program is said to learn from experience E with respect to task T and performance measure P if its performance on T, as measured by P, improves with experience E.

Example: A spam filter (T = classify email) learns (E = labelled examples) and improves accuracy (P = % correct) over time.

Forms of Learning — A Taxonomy

Figure 3.1 — Taxonomy of machine learning paradigms. Supervised learning (most tested in exams) uses labelled examples. Unsupervised discovers hidden structure. Reinforcement learns from reward signals. Semi-supervised combines both.

Paradigm	Input	Feedback	Goal	Example Task
Supervised	Labelled (x, y) pairs	True labels given	Learn f: x → y	Spam detection, diagnosis
Unsupervised	Unlabelled x only	None	Find structure in x	Customer segmentation, topic modelling
Reinforcement	State observations	Reward / penalty	Maximise cumulative reward	Game playing, robot navigation
Semi-supervised	Few labelled + many unlabelled	Sparse labels	Propagate labels	Image classification with few labels
Self-supervised	Unlabelled x	Pseudo-labels from data	Learn rich representations	GPT, BERT pre-training

Inductive Learning

Inductive learning is the process of generalising from specific training examples to a general hypothesis (concept or rule) that correctly classifies unseen examples. It is the most fundamental form of supervised learning.

Given: a set of training examples (positive and negative instances of a concept).
Goal: find a hypothesis H consistent with all examples and general enough to classify new ones correctly.
Key challenge: inductive bias — with infinitely many consistent hypotheses, we need additional assumptions to prefer simpler or more general ones (Occam's Razor).

Inductive Learning Problem Given: Training set D = {(x₁,y₁), (x₂,y₂), \dots, (xₙ,yₙ)} where xᵢ = input features, yᵢ = target label Find: Hypothesis H such that H(xᵢ) \approx yᵢ for all training examples AND H generalises well to new unseen examples (low test error) Version space: Set of all hypotheses consistent with training data Occam's Razor: Prefer the simplest consistent hypothesis

Explanation-Based Learning (EBL)

Explanation-Based Learning

EBL (Mitchell et al., 1986) generalises from a single training example by constructing a logical explanation of why the example belongs to the target concept, then generalising that explanation. Unlike statistical inductive learning (which needs many examples), EBL uses existing domain knowledge to explain one example and extract a reusable rule.

ALGORITHM: Explanation-Based Learning (EBL)

Goal: Observe one example of a concept. e.g., "a cup is safe-to-drink-from."

Explain: Using background domain knowledge, construct a proof of why this example satisfies the concept. e.g., the cup is light, has a handle, is stable → therefore safe to drink from.

Generalise: Replace specific constants in the proof with variables. Extract the most general conditions that make the proof valid.

Output: A general rule: ∀x Light(x) ∧ HasHandle(x) ∧ Stable(x) → SafeToDrinkFrom(x).

Learning Using Relevance Information

Not all features are equally useful for learning. Relevance-based learning uses prior knowledge about which attributes are relevant to the target concept, focusing the learner and improving generalisation from fewer examples.

Feature Selection

max I(feature; label)

Select features with high mutual information with the target label. Removes irrelevant and redundant features. e.g., for spam detection: word frequency relevant; email font size irrelevant.

Relevance Feedback

User marks relevance

User labels retrieved documents as relevant/irrelevant; the learner adjusts its model. Rocchio algorithm for IR: move query toward relevant, away from irrelevant documents.

Prior Knowledge Injection

constrained hypothesis space

Tell the learner which attributes matter. EBL does this explicitly. Modern: attention mechanisms in transformers learn which input tokens are relevant for each output.

FOIL (Quinlan, 1990)

max FOIL-gain

First-Order Inductive Learner — learns Horn clause rules by adding literals that maximise FOIL-gain (a variant of information gain for relational data). Combines relevance with inductive rule learning.

🎯 Quick Check: Explanation-Based Learning (EBL) differs from standard inductive learning primarily because:

✅ Correct! EBL's key feature is that it can learn from a single example — something statistical inductive learning cannot do. It achieves this by leveraging rich domain knowledge to construct a logical explanation (proof) of why the example fits the concept. The explanation is then generalised by replacing constants with variables. This makes EBL powerful for domains with strong prior knowledge (like physics, chess) but weak for domains where we lack good domain theories. The trade-off: EBL is knowledge-intensive but data-efficient.

Section 04

Learning Decision Trees

Decision trees are one of the most interpretable and widely used machine learning algorithms. A decision tree classifies examples by asking a series of attribute-value questions, following branches based on answers until a leaf (classification) is reached. They are the basis of modern ensemble methods (Random Forests, Gradient Boosting) and are frequently featured in AI exams.

Decision Tree

A decision tree is a tree where each internal node tests an attribute, each branch corresponds to an attribute value, and each leaf node gives a classification. To classify a new example, start at the root, follow branches based on the example's attribute values, and return the label at the leaf reached.

Running Example Play Tennis Dataset (Mitchell, 1997)

Should we play tennis today? Four weather attributes and 14 training examples (9 positive, 5 negative). This exact dataset appears in almost every AI exam on decision trees — know it by heart.

Day	Outlook	Temperature	Humidity	Wind	Play?
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

The ID3 Algorithm — Information Gain

Information Gain and Entropy

ID3 (Quinlan, 1986) selects the attribute at each node that maximises Information Gain — the reduction in entropy (uncertainty) achieved by splitting on that attribute.

Entropy and Information Gain Entropy(S) = −Σ pᵢ log₂(pᵢ) where pᵢ = fraction of examples in class i = 0 if all same class (pure) = 1 if 50/50 split (maximum uncertainty) InfoGain(S, A) = Entropy(S) − Σ_{v∈values(A)} |Sᵥ|/|S| × Entropy(Sᵥ) = entropy BEFORE split − weighted entropy AFTER split For PlayTennis (9 Yes, 5 No): Entropy(S) = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = −0.643×(−0.637) − 0.357×(−1.485) = 0.410 + 0.530 = 0.940 bits

Worked Example ID3 — Computing Information Gain for All Attributes

Step 1 — Entropy of Outlook subsets

Outlook Value	Examples	Yes/No	Entropy
Sunny	D1,D2,D8,D9,D11	2 Yes, 3 No	−(2/5)log(2/5)−(3/5)log(3/5) = 0.971
Overcast	D3,D7,D12,D13	4 Yes, 0 No	−1·log(1)−0 = 0.0 (pure!)
Rain	D4,D5,D6,D10,D14	3 Yes, 2 No	−(3/5)log(3/5)−(2/5)log(2/5) = 0.971

Gain(S, Outlook) = 0.940 - (5/14)\times0.971 - (4/14)\times0.000 - (5/14)\times0.971 = 0.940 - 0.347 - 0.000 - 0.347 = 0.246 bits

Information Gain for All Attributes

Attribute	Information Gain	Selected?
Outlook	0.246 bits	✅ YES — highest gain → root node
Temperature	0.029 bits	❌ Low gain
Humidity	0.151 bits	❌ Second highest
Wind	0.048 bits	❌ Low gain

Outlook is chosen as the root (highest information gain = 0.246). The Overcast branch immediately gives a pure leaf (always Play=Yes). Recursion continues on Sunny and Rain branches with remaining examples.

Figure 4.1 — Learned decision tree for the Play Tennis dataset. Outlook is the root (highest gain=0.246). Overcast always gives Yes (pure leaf). Under Sunny, Humidity decides; under Rain, Wind decides. The tree correctly classifies all 14 training examples.

Overfitting and Pruning

Watch Out — Overfitting

Overfitting occurs when the tree grows too deep, fitting noise in the training data rather than the true pattern. An overfit tree has 100% training accuracy but poor generalisation. Prevention: Pre-pruning (stop growing when gain falls below a threshold) or Post-pruning (grow full tree, then prune branches that don't improve validation accuracy). Random Forests tackle overfitting by averaging many trees trained on random subsets.

🎯 Quick Check: The Outlook=Overcast branch in the Play Tennis decision tree has entropy 0.0. What does this mean, and why does ID3 create a leaf node here immediately?

✅ Correct! Entropy = −Σ pᵢ log₂(pᵢ). When all 4 Overcast examples are Yes (p_Yes=1, p_No=0): Entropy = −1·log₂(1) − 0·log₂(0) = 0. Zero entropy = zero uncertainty = perfect purity. ID3 immediately makes this a leaf node with label Yes because splitting further cannot reduce entropy below 0. Any split on an already-pure node would be pointless. This is a key insight: the goal of ID3 is to reach pure leaves (entropy=0), and when we already have one, we stop.

Section 05

Neural Network Learning & Genetic Algorithms

Decision trees work beautifully on tabular data with clear attribute splits — but they struggle with images, audio, and continuous-valued inputs. Neural networks learn hierarchical representations directly from raw data, making them the backbone of modern deep learning. Genetic algorithms borrow from biological evolution to search vast hypothesis spaces that gradient-based methods cannot navigate.

Neural Network Learning — The Perceptron

Artificial Neuron (Perceptron)

A perceptron computes a weighted sum of its inputs, adds a bias, and passes the result through an activation function. For input vector x, weights w, bias b, and activation σ:

Single Neuron Computation z = w₁x₁ + w₂x₂ + … + wₙxₙ + b = w·x + b (weighted sum) ŷ = σ(z) (activation) Common activations: Step: σ(z) = 1 if z≥0, else 0 (Perceptron — binary) Sigmoid: σ(z) = 1/(1+e^{−z}) (smooth, 0 to 1) ReLU: σ(z) = max(0, z) (deep learning standard) Tanh: σ(z) = (e^z−e^{−z})/(e^z+e^{−z}) (−1 to +1)

Figure 5.1 — Multi-layer neural network (MLP). Input layer feeds hidden layers (ReLU activation); output uses Softmax for classification. Backpropagation (red dashed) adjusts weights by propagating the gradient of the loss from output back to input.

Backpropagation — Learning the Weights

Backpropagation Algorithm

Backpropagation (Rumelhart, Hinton & Williams, 1986) computes the gradient of the loss function with respect to every weight in the network using the chain rule, then updates weights using gradient descent.

ALGORITHM: Backpropagation Training

Forward Pass: Compute network output ŷ = f(x; W) layer by layer. Store all intermediate activations.

Compute Loss: L = Loss(ŷ, y). For classification: Cross-entropy L = −Σ yᵢ log ŷᵢ. For regression: MSE L = (1/n)Σ(ŷ−y)².

Backward Pass: Compute δL/δW for every weight using chain rule from output to input: δL/δwᵢⱼ = δL/δaⱼ × δaⱼ/δzⱼ × δzⱼ/δwᵢⱼ.

Weight Update: wᵢⱼ ← wᵢⱼ − η × δL/δwᵢⱼ where η = learning rate (e.g. 0.001). Repeat for all weights.

Iterate: Repeat Steps 1–4 for all mini-batches over multiple epochs until convergence (loss stops decreasing).

Gradient Descent Weight Update Output layer delta: δₒ = (ŷ - y) \times σ'(zₒ) Hidden layer delta: δₕ = (Σ wₒₕ \times δₒ) \times σ'(zₕ) \leftarrow chain rule Weight update: Δwₕₒ = -η \times δₒ \times aₕ Δwᵢₕ = -η \times δₕ \times xᵢ Example: η=0.1, output=0.8, target=1.0, σ'(z)=0.16 (sigmoid at 0.8) δₒ = (0.8-1.0) \times 0.16 = -0.032 Δw = -0.1 \times (-0.032) \times aₕ = +0.0032 \times aₕ \leftarrow weight increases (toward target)

Genetic Learning (Genetic Algorithms)

Genetic Algorithm (GA)

A Genetic Algorithm (Holland, 1975) searches a hypothesis space by maintaining a population of candidate solutions (chromosomes) and evolving them through selection, crossover, and mutation — mimicking biological natural selection. GAs excel when the search space is large, non-differentiable, or has many local optima that trap gradient-based methods.

ALGORITHM: Genetic Algorithm for Learning

Initialise: Create a population of k random individuals (bit strings or rule sets). Each individual = one candidate hypothesis.

Evaluate Fitness: For each individual, compute f(individual) = measure of how well it solves the problem (accuracy, reward, etc.).

Selection: Select parents with probability proportional to fitness (roulette wheel). Better individuals reproduce more.

Crossover: With probability p_c, swap tail segments of two parents at a random crossover point to produce two offspring.

Mutation: With probability p_m (small, e.g. 0.01), flip each bit. Maintains genetic diversity; prevents premature convergence.

Replace: New population replaces old. Repeat from Step 2 until termination criterion (max generations or fitness threshold).

Worked Example GA for Decision Rule Learning — One Generation

Encode the Play Tennis attributes as a bit string: Outlook(2 bits) + Temperature(2 bits) + Humidity(1 bit) + Wind(1 bit) = 6-bit chromosome. 1=relevant/True, 0=irrelevant/False.

Individual	Chromosome	Rule Decoded	Fitness (accuracy)	Selection Prob.
A	`110011`	Sunny AND High-Humidity AND Strong-Wind → No	0.72	0.72/2.65 = 27%
B	`010100`	Overcast AND Low-Temp → Yes	0.65	0.65/2.65 = 25%
C	`100110`	Outlook AND Humidity AND Wind rule	0.71	0.71/2.65 = 27%
D	`111001`	Sunny AND Hot AND Normal	0.57	0.57/2.65 = 22%

Crossover Example (Parents A and C, crossover at position 3)

	Chromosome	Decoded Rule	Fitness
Parent A	`110\|011`	Sunny AND …	0.72
Parent C	`100\|110`	Outlook AND …	0.71
Child A'	`110\|110`	New rule combining best of both	0.78 ↑ Improved!
Child C'	`100\|011`	New variant	0.69

Child A' achieves higher fitness (0.78) than either parent by combining their best segments — this is the power of crossover.

Feature	Neural Networks	Decision Trees	Genetic Algorithms
Learning paradigm	Gradient-based optimisation	Greedy recursive splitting	Population-based evolution
Interpretability	❌ Black box	✅ Fully interpretable	❌ Hard to interpret
Data requirement	Large (thousands–millions)	Small–medium (hundreds)	Medium (evaluation-heavy)
Handles non-linearity	✅ Excellent	✅ Good (axis-aligned)	✅ Excellent
Escapes local optima	❌ SGD can get stuck	N/A (greedy)	✅ Via crossover + mutation
Best for	Images, text, audio, sequences	Tabular data, explainable AI	Combinatorial optimisation, rule evolution

🎯 Quick Check: In backpropagation, why must we store the intermediate activations from the forward pass before computing the backward pass?

✅ Correct! The gradient of the loss with respect to weight wᵢⱼ (connecting neuron i to j) is: δL/δwᵢⱼ = δL/δzⱼ × aᵢ, where aᵢ is the activation of neuron i from the forward pass. Without aᵢ, this gradient cannot be computed. This is why backpropagation requires a full forward pass first — to cache all intermediate activations — before the backward pass can calculate gradients. This memory cost (storing all activations) is why training large networks requires significant GPU memory.

Section 06

Expert Systems

In the 1970s and 80s, AI researchers asked a provocative question: could we capture the expertise of the world's best doctors, lawyers, and engineers in a computer program? The answer was expert systems — AI programs that emulate the decision-making ability of a human expert in a specific domain. Unlike general-purpose programs, expert systems encode deep, specialised knowledge and can explain their reasoning — a property that earned them widespread adoption in medicine, engineering, and finance.

The most famous early success was MYCIN (Stanford, 1976) — a system that diagnosed bacterial blood infections with accuracy matching senior physicians. This section covers the architecture, design, and knowledge acquisition process that make expert systems work.

Architecture of an Expert System

Figure 6.1 — Expert system architecture. A knowledge engineer (working with domain experts) populates the knowledge base with rules. The inference engine applies rules to working memory (patient facts) to derive conclusions. The explanation module traces the reasoning for the user.

Representing and Using Domain Knowledge

The power of an expert system comes entirely from the quality and completeness of its knowledge base. Domain knowledge is encoded in several forms, all of which we saw in Unit III and IV.

Classic Example MYCIN — Rules, Certainty Factors, and Explanation

MYCIN Knowledge Base (Sample Rules)

-- Rule 52: Identify organism as Pseudomonas --
IF   the gram-stain of the organism is gramneg
AND  the morphology is rod
AND  the aerobicity is aerobic
THEN there is suggestive evidence (CF=0.6) that
     the identity of the organism is Pseudomonas

-- Rule 073: Treat with Gentamicin for Pseudomonas --
IF   the identity of organism-1 is Pseudomonas
AND  the patient is not allergic to Gentamicin
THEN recommend Gentamicin  [CF=0.8]

-- Rule 119: Penicillin coverage for Streptococcus --
IF   the identity of organism-1 is Streptococcus
AND  the patient has received Penicillin in past 6 months
THEN consider Penicillin-resistant strain  [CF=0.4]

Backward Chaining Trace

Goal: What drug should be prescribed? → Triggers drug-recommendation rules → Triggers identity-of-organism rules → Triggers lab-result queries.

Step	Goal	Rule Applied	Sub-goal / Action
1	PRESCRIBE(drug, patient)	Drug rules	Need: IDENTITY(organism, ?)
2	IDENTITY(organism, Pseudomonas)	Rule 52	Need: GramStain=neg, Morphology=rod, Aerobic
3	GramStain=neg	Ask user	Q: "What is the gram stain of organism-1?"
4	Morphology=rod	Ask user	Q: "What is the morphology of organism-1?"
5	Identity ≈ Pseudomonas [CF=0.6]	Rule 073	RECOMMEND(Gentamicin) [CF=0.8×0.6=0.48]

Explanation Facility — WHY and HOW

-- User asks WHY is gram stain needed? --
SYSTEM: "I am trying to determine the identity of organism-1."
"Rule 52 states: IF gram-stain is gramneg AND morphology is rod"
"AND aerobic THEN identity is Pseudomonas [CF=0.6]."
"I need gram-stain to apply this rule."

-- User asks HOW did you conclude Pseudomonas? --
SYSTEM: "I concluded Pseudomonas [CF=0.6] because:"
"  1. Gram stain = gramneg  (you told me, CF=1.0)"
"  2. Morphology = rod      (you told me, CF=1.0)"
"  3. Aerobicity = aerobic  (lab result, CF=0.9)"
"  → Rule 52 applied with combined CF = 0.6×0.9 = 0.54"

Why Explanation Matters

MYCIN's explanation facility was arguably as important as its diagnostic accuracy. Physicians could ask WHY (what information is needed and why) and HOW (how a conclusion was reached). This transparency built trust and allowed doctors to catch errors — something a black-box neural network cannot provide.

Expert System Shells

Expert System Shell

An expert system shell is a reusable framework containing the inference engine, working memory management, explanation facility, and user interface — everything except the domain-specific knowledge base. A knowledge engineer can build a new expert system by simply populating the shell with domain rules, without implementing the reasoning engine from scratch.

EMYCIN (Empty MYCIN) was the first major shell, created by stripping MYCIN's medical knowledge and keeping the reasoning architecture. Subsequent shells became commercial products used across industries.

Shell / System	Year	Origin	Key Features	Applications
EMYCIN	1979	Stanford (from MYCIN)	Backward chaining, certainty factors	Medical diagnosis
OPS5	1977	Carnegie Mellon	Forward chaining, Rete algorithm	R1 (DEC VAX config)
CLIPS	1985	NASA	Forward chaining, C-based, free	Aerospace, manufacturing
JESS	1995	Sandia National Labs	Java-based CLIPS variant, JVM integration	Enterprise, web apps
Drools	2001	Red Hat / JBoss	Java, RETE algorithm, business rules	Finance, banking, insurance

Knowledge Acquisition

Knowledge Acquisition Bottleneck

Knowledge acquisition — the process of extracting expert knowledge and encoding it into the knowledge base — is the single hardest and most time-consuming step in building an expert system. Experts find it difficult to articulate the heuristics and intuitions they use, a phenomenon called tacit knowledge.

KNOWLEDGE ACQUISITION PROCESS — Stages

Identification: Define the problem domain, identify the expert(s), select the representation formalism. Determine scope — what questions must the system answer?

Conceptualisation: Identify key concepts, their relationships, and the reasoning strategies experts use. Techniques: structured interviews, think-aloud protocols, case analysis.

Formalisation: Translate conceptualised knowledge into formal rules, frames, or ontologies suitable for the chosen shell. This is where tacit knowledge is hardest to capture.

Implementation: Enter formal rules into the knowledge base. Test on sample cases. Identify missing rules and incorrect certainty factors.

Testing and Validation: Evaluate against known expert cases. Expert reviews the system's reasoning traces. Iterate: add rules, adjust CFs, refine conditions.

Maintenance: Update the KB as domain knowledge changes (new drugs, new diseases, changed protocols). Track rule interactions to avoid unintended consequences.

Forward Chaining

Data → Conclusions

Start with known facts in working memory. Fire all matching rules. Repeat until goal is derived or no more rules fire. "Data-driven." Best when: all data available upfront, multiple possible conclusions.

Backward Chaining

Goal → Sub-goals

Start with the goal. Find rules that can prove it. Recursively prove sub-goals. Ask user only for needed data. "Goal-driven." Best when: single hypothesis to verify, many possible data items (ask only what's needed).

Certainty Factors

CF ∈ [−1, +1]

MYCIN's uncertainty handling. CF = 0 = no evidence; CF = 1 = certain; CF = −1 = certainly false. Combined: CF(A∧B) = min(CF_A, CF_B). Simpler than Bayesian but less principled.

RETE Algorithm

Pattern network

Efficient rule matching: pre-compiles rules into a discrimination network. Avoids re-evaluating unchanged facts. Used in OPS5, CLIPS, Drools. Reduces rule matching from O(rules×facts) to near O(1) per fact change.

Key Insight — Why Expert Systems Succeeded and Then Declined

Success (1970s–80s): R1/XCON (DEC, 1980) configured VAX computers, saving $40M/year. MYCIN matched physicians in diagnosis. PROSPECTOR discovered a molybdenum deposit worth $100M.
Decline (late 80s–90s): Knowledge acquisition bottleneck — encoding new domains took years. Knowledge bases became unmaintainable. No learning — systems could not improve automatically. Could not handle exceptions gracefully.
Revival (2010s–present): Hybrid systems combine ML (for pattern recognition) with expert system shells (for transparent reasoning). Medical AI now combines neural networks with rule engines for explainability.

🎯 Quick Check: A doctor using MYCIN asks "WHY do you need to know the patient's gram stain result?" Which expert system component answers this question, and what does it use?

✅ Correct! The Explanation Facility handles WHY and HOW questions. WHY("gram stain"): traces the backward chaining stack — "I'm asking because Rule 52 needs gram-stain=gramneg to conclude Pseudomonas, and I'm trying to identify the organism in order to recommend a drug." It uses the goal stack maintained by the inference engine during backward chaining. HOW("Pseudomonas"): shows the chain of rules and facts that led to that conclusion. This transparency is what distinguishes expert systems from black-box ML — it is the explanation facility, not the inference engine or KB alone.

Section 07

Exam Preparation Summary

This section consolidates every definition, formula, algorithm, and comparison from Unit V into a single revision reference.

★ NLP Pipeline — All Levels

Level	Task	Input→Output	Key Technique	Example
Morphological	Decompose word forms	Words → morphemes	Finite-state transducers	treated → treat + ed
Lexical (POS)	Tag parts of speech	Tokens → POS tags	HMM, CRF, BERT	treated/VBD doctor/NN
Syntactic	Build parse tree	Tagged words → tree	CFG, CYK algorithm	S→NP VP, NP→Det N
Semantic	Compute meaning	Parse tree → logical form	Lambda calculus, WSD	Treated(doctor, patient)
Discourse	Link sentences	Sentences → coherent text	Co-reference, RST	"She" → doctor
Pragmatic	Identify speaker intent	Utterance → speech act	Grice's maxims, speech acts	"Can you pass salt?" = Request

★ Machine Learning — Forms and Algorithms

Algorithm	Type	Key Formula / Concept	Best For
Decision Tree (ID3)	Supervised	Gain(S,A) = H(S) − Σ\|Sᵥ\|/\|S\|·H(Sᵥ)	Tabular data; interpretable AI
Neural Network	Supervised	Backprop: δw = −η·∂L/∂w	Images, text, audio
Genetic Algorithm	Evolutionary	Selection + Crossover + Mutation	Combinatorial optimisation
Inductive Learning	Supervised	Generalise from (x,y) pairs	General classification / regression
EBL	Knowledge-intensive	Explain ONE example → generalise	Domains with strong prior knowledge
Reinforcement	Reward-based	max E[Σ γᵗ rₜ]	Games, robotics, control

★ Information Gain — Full Calculation Template

ID3 Entropy and Information Gain — Exam Template Step 1: H(S) = -(p₊)log₂(p₊) - (p₋)log₂(p₋) For 9 Yes, 5 No: H = -(9/14)log₂(9/14) - (5/14)log₂(5/14) = 0.940 Step 2: For each attribute A with values v₁, v₂, \dots: Gain(S,A) = H(S) - Σᵥ (|Sᵥ|/|S|) \times H(Sᵥ) Step 3: Choose attribute with HIGHEST gain as next split node. Step 4: Recurse on each branch. STOP when: • All examples in node have same label (entropy = 0) \to leaf • No attributes left \to majority vote leaf • No examples left \to parent majority vote

★ Expert System Components

Knowledge Base

Rules + Facts

IF-THEN rules with certainty factors. Domain-specific. Built by knowledge engineer from expert interviews.

Inference Engine

Forward / Backward

Forward: data→conclusions. Backward: goal→sub-goals. Conflict resolution selects which rule fires.

Working Memory

Current State

Holds known facts about current case. Rules match against working memory. Updated as inference proceeds.

Explanation Facility

WHY / HOW

WHY: traces goal chain. HOW: shows rule+facts chain for conclusion. Critical for user trust and verification.

KA Bottleneck

Tacit Knowledge

Experts cannot articulate all they know. Acquisition = interviews + think-aloud + case analysis + iteration.

Shell

KB-less Engine

Reusable inference engine (CLIPS, Drools, EMYCIN). Fill with domain rules to get a new expert system.

Common Exam Mistakes

Watch Out!

Mistake 1: Confusing structural ambiguity (two parse trees) with lexical ambiguity (one word, two meanings). "I saw the man with the telescope" is structural; "bank" is lexical.

Mistake 2: Forgetting that entropy = 0 means a PURE node (all same class) — this is the BEST outcome for a split, not the worst. ID3 aims for entropy 0.

Mistake 3: Mixing up forward chaining (data-driven, fires all matching rules) with backward chaining (goal-driven, asks only what's needed). Medical diagnosis typically uses backward chaining.

Mistake 4: In the GA crossover example, children inherit HEAD from one parent and TAIL from the other — not the reverse. Check which part of the string is being swapped.

Mistake 5: Saying neural networks are "complete" like logic-based systems. NNs are statistical learners — they generalise from data but can fail on out-of-distribution examples. Expert systems with rules are more predictable but cannot learn.

Mistake 6: In EBL, the generalisation step replaces constants with variables — not the other way round. The goal is to make the rule as general as possible while still being provably correct.

Typical Exam Question Types

Question Pattern	Required Approach	Key Terms
"Describe NLP processing levels"	List all 6 levels; give input/output/technique for each	Morphological, lexical, syntactic, semantic, discourse, pragmatic
"Draw parse tree for sentence X"	Apply CFG rules; use NP/VP/PP/Det/N/V notation	S→NP VP, NP→Det N, VP→V NP, PP→P NP
"Apply ID3 to dataset"	Compute entropy of S; compute gain for each attribute; pick highest; recurse	H(S) = −Σ pᵢ log₂ pᵢ; Gain = H(S) − weighted child entropy
"Explain backpropagation"	Forward pass → compute loss → backward pass (chain rule) → weight update	δL/δw, learning rate η, gradient descent
"How does a GA work?"	5 steps: Init → Evaluate → Select → Crossover → Mutate	Population, chromosome, fitness, roulette wheel, crossover point
"Architecture of an expert system"	Draw diagram with KB, inference engine, WM, explanation, UI	Forward/backward chaining, certainty factors, WHY/HOW

Challenge Quiz

🎯 Challenge: A hospital wants to build an AI system to diagnose rare cancers. The system must: (a) explain every diagnosis to oncologists, (b) learn from new patient cases as they arrive, and (c) handle ambiguous test results (probability < 1). Which combination of techniques best addresses ALL three requirements?

✅ Correct! No single technique satisfies all three requirements alone. (a) Explanation: Neural networks are black boxes — they cannot generate clinically useful "WHY" traces. Expert systems excel here. (b) Learning: Classic expert systems cannot learn from new cases — rules must be manually updated. Neural networks and Bayesian networks learn automatically. (c) Uncertainty: Both Bayesian networks and NNs handle probabilistic evidence; expert system certainty factors are a simpler approximation. The solution: a hybrid neuro-symbolic system — the neural/Bayesian component handles learning and uncertainty, while the expert system layer generates explanations from the model's decisions. This architecture is now the state of the art in clinical AI (e.g., IBM Watson for Oncology, clinical decision support systems).