Ans: Concise point-wise definition/formula for Define Artificial Intelligence. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Turing Test? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Intelligent Agent. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is PEAS representation? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Environment in AI. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Fully Observable Environment? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Partially Observable Environment? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Deterministic Environment? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Stochastic Environment? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define State Space. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Initial State and Goal State? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Path Cost. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Uninformed Search? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Informed Search? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Heuristic Function. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Admissible Heuristic? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Consistent Heuristic? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Breadth-First Search (BFS). in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Depth-First Search (DFS). in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Uniform Cost Search? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is A* Search? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Greedy Best-First Search. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Hill Climbing Search? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Local Maxima in hill climbing. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Plateau in hill climbing? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Ridge in hill climbing? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Simulated Annealing? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Constraint Satisfaction Problem (CSP). in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Backtracking Search? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Game Tree. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Minimax Algorithm? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Alpha-Beta Pruning? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Alpha and Beta values. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Knowledge Representation? --- Page 2 --- in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Knowledge Base (KB). in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Propositional Logic? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is First-Order Logic (FOL)? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Universal Quantifier (∀). in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Existential Quantifier (∃). in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Conjunctive Normal Form (CNF)? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Resolution Refutation. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Unification in FOL? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Horn Clause. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Forward Chaining? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Backward Chaining? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Semantic Network? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Frame in knowledge representation. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Bayes' Theorem? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Bayesian Network. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Fuzzy Logic? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for Define Membership Function in fuzzy logic. in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Expert System? in accordance with MAKAUT examination pattern.

Ans: Concise point-wise definition/formula for What is Expert System Shell? in accordance with MAKAUT examination pattern.

Definition: The PEAS framework (Performance measure, Environment, Actuators, Sensors) is used to specify the task environment of a rational agent completely before designing it.

Significance: PEAS forces a designer to precisely fix what counts as success (Performance), what the agent must operate within (Environment), how it acts (Actuators) and how it perceives (Sensors) — the four together define the agent's task environment and drive its architecture choice.

Definition: Task environments are classified along several dimensions that determine the complexity of the agent design required.

Impact on design: Fully observable + deterministic + static environments allow simple reflex/planning agents; partially observable, stochastic, dynamic environments (the real world) require agents that maintain internal state, model uncertainty (e.g. probabilistic reasoning) and continuously replan.

Definition: Uninformed (blind) search algorithms explore the state space using only the problem definition, without any domain-specific heuristic guidance.

IDDFS is preferred in practice for large/unknown-depth spaces since it combines DFS's low O(bd) space with BFS's completeness and optimality.

Definition: A* is a best-first informed search that expands the node minimizing the evaluation function f(n) = g(n) + h(n), where g(n) = actual cost from start to n, and h(n) = estimated (heuristic) cost from n to the goal.

Working:

• Maintain an OPEN list (priority queue ordered by f(n)) and a CLOSED list of expanded nodes.
• Repeatedly pop the node with lowest f(n); if it is the goal, stop — the path found is optimal.
• Otherwise expand it, computing g and f for each successor, and insert/update them in OPEN.
• If a successor is already in OPEN/CLOSED with a higher g, update it (re-open if needed).

Key guarantee: If h(n) is admissible (never overestimates true cost), A* using tree-search is guaranteed to find the optimal path; if h(n) is also consistent, graph-search A* is optimal and never needs to re-open a closed node. Because g(n) grows and h(n) guides toward the goal, A* combines the completeness/optimality of Uniform Cost Search (h=0) with the speed of Greedy Best-First Search (g ignored), making it both complete and optimal for admissible heuristics.

Admissibility: A heuristic h(n) is admissible if it never overestimates the true cost h*(n) to reach the goal from n:

h(n) ≤ h*(n) for all n

Admissibility guarantees A* Tree-Search finds an optimal solution, because the heuristic is always "optimistic" and never causes the true optimal path to be pruned too early.

Consistency (Monotonicity): A heuristic is consistent if for every node n and successor n' generated by action costing c(n,n'):

h(n) ≤ c(n, n') + h(n')

with h(goal) = 0. Consistency is a stronger condition — it guarantees that f(n) = g(n)+h(n) never decreases along any path (f is monotonically non-decreasing), which in turn guarantees admissibility.

Example: the straight-line distance heuristic in road-map path finding is both admissible and consistent, since it never exceeds actual road distance and satisfies the triangle inequality.

Definition: Hill Climbing is a local search that starts at an arbitrary state and iteratively moves to the neighbouring state with the highest value (steepest-ascent), stopping when no neighbour is better than the current state.

Pitfalls (why it can fail to reach the global optimum):

• Local Maxima: a peak lower than the global maximum where every neighbour is worse, so the algorithm gets stuck.
• Plateau: a flat region of the state space where all neighbours have equal value, giving no direction to climb (can cause aimless wandering).
• Ridge: a sequence of local maxima that is difficult to navigate because the ridge's orientation does not align with the available moves, causing zig-zagging.

Remedies: random-restart hill climbing, allowing sideways moves (bounded), or switching to stochastic methods such as Simulated Annealing.

Definition: Simulated Annealing (SA) is a stochastic local search inspired by metallurgical annealing. Unlike hill climbing, it sometimes accepts a worse move to escape local maxima, with the probability of accepting a bad move controlled by a temperature parameter T that is gradually lowered.

Acceptance rule: A move that changes the objective by ΔE (negative = worse) is accepted:

• Always, if ΔE > 0 (improves the state).
• With probability P = e^{ΔE / T}, if ΔE < 0 (worsening move).

Temperature (cooling) schedule: T starts high (near-random walk, high exploration) and is reduced slowly (e.g. geometric decay T ← αT, 0.8 ≤ α ≤ 0.99), so the search increasingly behaves like hill climbing (pure exploitation) as T → 0. A slow enough schedule guarantees convergence to the global optimum with probability approaching 1.

Definition: A Constraint Satisfaction Problem (CSP) is defined by a set of variables X = {X1,...,Xn}, each with a domain Di of possible values, and a set of constraints C that restrict which combinations of values are allowed.

N-Queens as a CSP:

• Variables: Q1, Q2, ..., QN — one per column, representing the row of the queen in that column.
• Domain: Di = {1, 2, ..., N} (possible rows).
• Constraints: for every pair i ≠ j: Qi ≠ Qj (no same row) and |Qi − Qj| ≠ |i − j| (no same diagonal).

CSP algorithms (backtracking + constraint propagation like forward checking / AC-3, and heuristics like MRV, degree, LCV) solve N-Queens far more efficiently than pure generate-and-test.

Backtracking Search for CSP: Depth-first search that assigns one variable at a time; at each step it picks an unassigned variable, tries a value from its domain consistent with existing assignments, and recurses. If no value works, it backtracks to the previous variable.

Arc Consistency (AC-3): A preprocessing/propagation technique that removes domain values that can never take part in a consistent solution, pruning the search tree before/during backtracking.

• An arc X → Y is consistent if for every value x in Dx, there exists some value y in Dy satisfying the constraint between X and Y.
• AC-3 maintains a queue of all arcs; it repeatedly removes an arc (Xi, Xj), calls REVISE to delete unsupported values from Di, and if Di changed, re-adds all arcs (Xk, Xi) for neighbours Xk back into the queue.
• If any domain becomes empty, the CSP has no solution along that branch (fail early).

Complexity: AC-3 runs in O(cd³) where c = number of arcs and d = domain size. Combining backtracking with AC-3 (as a preprocessing step or interleaved via MAC — Maintaining Arc Consistency) drastically reduces the branching factor in practice.

Definition: Minimax is a recursive decision-making algorithm for two-player, zero-sum, perfect-information games. It assumes MAX tries to maximize the utility and MIN tries to minimize it, and computes the game-theoretically optimal move by backing up values from the leaves.

Properties: Complete (if tree finite), optimal against an optimal opponent. Time complexity O(b^m), space O(bm) with DFS — in practice depth m is cut off with a heuristic evaluation function since game trees (e.g. chess) are too large to search fully.

Definition: Alpha-Beta Pruning is an optimization of Minimax that skips (prunes) branches which cannot possibly influence the final decision, without changing the result.

• α = best value MAX can guarantee so far on the path to the root (initially −∞).
• β = best value MIN can guarantee so far on the path to the root (initially +∞).
• Pruning rule: at any node, if α ≥ β, stop exploring its remaining children — that branch cannot affect the parent's decision.
• MAX nodes update α = max(α, value); MIN nodes update β = min(β, value); each node passes the current (α,β) window down to its children.

Effectiveness: with a good (best-first) move ordering, alpha-beta reduces the effective branching factor from b to about √b, doubling the search depth achievable in the same time, while always returning the exact same value as Minimax.

Syntax: Propositional (Boolean) Logic consists of atomic propositions (P, Q, R, ... each True/False) combined with logical connectives:

Truth table for P → Q (false only when antecedent true and consequent false):

A sentence is valid (tautology) if it is true under every model, satisfiable if true under some model, and unsatisfiable (contradiction) if true under no model. Propositional logic is the foundation for building inference systems (e.g. resolution) but cannot express relations/quantification over objects — that requires First-Order Logic.

Definition: First-Order Logic (FOL) extends propositional logic with objects, relations (predicates), functions, and quantifiers, allowing it to express statements about collections of objects, not just fixed propositions.

Syntax elements:

• Constants: name specific objects, e.g. John, 2, Block-A.
• Predicates: represent relations/properties, e.g. Brother(John, Ram), Red(x).
• Functions: map objects to objects, e.g. FatherOf(x).
• Variables and Connectives: x, y ... with ∧, ∨, ¬, →, ↔ as before.
• Universal Quantifier ∀x: "for all x" — P(x) must hold for every object in the domain. Typically paired with →: ∀x (Man(x) → Mortal(x)).
• Existential Quantifier ∃x: "there exists an x" — P(x) holds for at least one object. Typically paired with ∧: ∃x (Student(x) ∧ Smart(x)).

Example: "Every student who studies passes" is written ∀x (Student(x) ∧ Studies(x) → Passes(x)); "Some student failed" is ∃x (Student(x) ∧ Failed(x)). FOL gives AI systems the expressive power needed for knowledge bases, automated reasoning, and question answering that propositional logic cannot provide.

Definition: Conjunctive Normal Form (CNF) is a conjunction of clauses, where each clause is a disjunction of literals: (L11∨L12∨...) ∧ (L21∨L22∨...) ∧ ... CNF is the required input form for the Resolution inference procedure.

Standard 7-step conversion procedure:

1. Eliminate biconditionals: replace A↔B with (A→B)∧(B→A).
2. Eliminate implications: replace A→B with ¬A∨B.
3. Move ¬ inward (De Morgan's laws + quantifier duality): ¬(A∧B)≡¬A∨¬B, ¬∀x P≡∃x¬P, and eliminate double negation.
4. Standardize variables apart: rename variables so each quantifier binds a unique name.
5. Skolemize: replace each existentially quantified variable with a Skolem function of the enclosing universally quantified variables (a Skolem constant if none), then drop ∃.
6. Drop universal quantifiers (all remaining variables are implicitly universally quantified).
7. Distribute ∨ over ∧ to reach conjunction-of-disjunctions form.

Example: ∀x (Man(x) → Mortal(x)) ⇒ eliminate implication → ∀x (¬Man(x) ∨ Mortal(x)) ⇒ drop quantifier → clause: ¬Man(x) ∨ Mortal(x).

Definition: Unification is the process of finding a substitution θ that makes two first-order logical expressions syntactically identical: UNIFY(p, q) = θ such that SUBST(θ, p) = SUBST(θ, q). It underlies inference rules like Generalized Modus Ponens and Resolution.

Algorithm (recursive): compare the two expressions term-by-term; if both are variables/constants, unify directly; if one is a variable and other a term (not containing that variable — the "occurs check"), bind the variable to the term; if both are compound expressions, unify only if predicate/function symbols and arity match, then recursively unify each argument pair, composing substitutions.

MGU (Most General Unifier) is the simplest/least-committal such substitution — every other unifier can be obtained from it by further substitution.

Definition: Resolution Refutation is a sound, complete inference procedure that proves a sentence α is entailed by a KB by showing that KB ∧ ¬α is unsatisfiable (proof by contradiction).

Resolution rule: from two clauses containing complementary literals, derive a new clause (the resolvent) containing all literals of both except the complementary pair:

(A ∨ B), (¬B ∨ C) ⊢ (A ∨ C)

Procedure:

1. Convert KB and the negated query ¬α to CNF (clause form).
2. Repeatedly select a pair of clauses with complementary literals and resolve them, adding the resolvent to the clause set.
3. If the empty clause (contradiction, □) is derived, KB ⊨ α is proved (refutation complete).
4. If no new resolvents can be added and no empty clause is found, KB does not entail α.

Example: KB: (P∨Q), (¬P∨R), (¬Q∨R), query α=R. Add ¬R. Resolve (P∨Q) with... Resolving (¬P∨R) and ¬R gives ¬P; resolving (¬Q∨R) and ¬R gives ¬Q; resolving (P∨Q) with ¬P gives Q; resolving Q with ¬Q gives the empty clause □ — contradiction found, so R is proved entailed.

Definition: Forward and Backward Chaining are the two main inference strategies for reasoning with a rule-based (Horn-clause) knowledge base.

Illustration: KB: P, Q, (P∧Q→S), (S→T). Forward chaining: P,Q known → fires rule1 → S asserted → fires rule2 → T asserted. Backward chaining for goal T: T needs S (rule2) → S needs P∧Q (rule1) → both are known facts → goal T proved.

Definition: A Semantic Network represents knowledge as a labelled directed graph: nodes denote objects/concepts and edges denote relationships between them (ISA, has-part, has-property, instance-of, etc.). It naturally supports inheritance of properties along ISA links.

Reasoning: a query like "can a Canary fly?" is answered by traversing the ISA link upward until a matching property node is found (property inheritance), avoiding the need to store "can fly" at every bird instance.

Limitation: exceptions (e.g. Penguin ISA Bird, but cannot fly) require explicit overriding at the more specific node, and semantic nets lack a clean formal semantics for quantification compared to FOL.

Definition: A Frame is a structured data representation that groups all knowledge about an object or concept into named slots with associated values, defaults, or attached procedures (demons). Frames connected via "AKO" (A-Kind-Of) links form a taxonomy that supports inheritance, similar to object-oriented classes.

Inheritance mechanism: when a slot value is requested for an instance and not explicitly present, the system searches up the AKO hierarchy until a value (or default) is found; a locally specified value always overrides an inherited one. This gives frames the compactness of hierarchical storage while still handling exceptions naturally, unlike plain semantic nets.

Definition: Conceptual Dependency (CD) Theory, developed by Roger Schank, represents the meaning of natural-language sentences independent of the specific words used, via a small fixed set of primitive actions plus cases (actor, object, instrument, direction).

Significance: because different sentences that mean the same thing (e.g. "John gave a book to Mary" vs "Mary got a book from John") reduce to the same CD structure, CD theory enables canonical representation for tasks like paraphrase detection, inference, and machine translation, independent of surface syntax.

Bayes' Theorem updates the probability of a hypothesis H given new evidence E, combining prior belief with the likelihood of the evidence:

P(H|E) = [ P(E|H) · P(H) ] / P(E)

where P(H) = prior probability, P(E|H) = likelihood, P(E) = evidence's marginal probability (normalizing constant), and P(H|E) = posterior probability.

Worked example: a disease D has prior P(D)=0.01. A test is 99% sensitive (P(+|D)=0.99) and has a 5% false-positive rate on healthy people (P(+|¬D)=0.05). Given a positive test result, find P(D|+):

P(+) = P(+|D)P(D) + P(+|¬D)P(¬D) = 0.99(0.01) + 0.05(0.99) = 0.0099 + 0.0495 = 0.0594

P(D|+) = 0.0099 / 0.0594 ≈ 0.1667 (about 16.7%)

Insight: despite a seemingly accurate test, the low prior (rare disease) keeps the posterior probability of actually having the disease low — this is the classic demonstration of why prior probabilities cannot be ignored in reasoning under uncertainty, and is exactly how Bayesian reasoning corrects the "base-rate fallacy". Bayes' theorem is the mathematical basis for Naive Bayes classifiers and Bayesian Networks.

Definition: A Bayesian Belief Network (BBN) is a directed acyclic graph (DAG) where nodes represent random variables and edges represent direct probabilistic dependence. Each node stores a Conditional Probability Table (CPT) giving P(node | its parents).

CPT example (for Alarm node):

Joint probability via chain rule: P(X1,...,Xn) = ∏i P(Xi | Parents(Xi)) — the network's structure lets us compute any joint probability as a product of a few small local CPTs instead of one exponentially large table, exploiting conditional independence.

Definition: Dempster-Shafer (D-S) Theory of Evidence generalizes Bayesian probability to explicitly represent ignorance (lack of evidence) separately from disbelief, useful when evidence is incomplete or comes from multiple independent sources (sensor fusion).

• Frame of Discernment (Θ): the set of all mutually exclusive hypotheses.
• Mass function m(A): assigns belief mass directly to a subset A ⊆ Θ (not further divisible among its own subsets), with ∑m(A) = 1 and m(∅) = 0.
• Belief, Bel(A) = ∑_B⊆A m(B): total mass definitely supporting A (lower bound of confidence).
• Plausibility, Pl(A) = ∑_B∩A≠∅ m(B) = 1 − Bel(¬A): total mass not contradicting A (upper bound).
• The interval [Bel(A), Pl(A)] represents the uncertainty about A; a wide interval means little evidence, and Pl(A) − Bel(A) measures ignorance.

Combination (Dempster's Rule): two independent mass functions m1, m2 are combined as:

m12(A) = [1 / (1−K)] ∑_Y∩Z=A m1(Y)·m2(Z), where K = ∑_Y∩Z=∅ m1(Y)m2(Z)

K measures the conflict between the two evidence sources and is used to renormalize the combined mass. D-S theory is preferred over pure Bayesian updating in expert systems (e.g. medical diagnosis, sensor fusion) precisely because it lets "I don't know" be modelled explicitly via m(Θ), instead of forcing a probability split.

Crisp Set: classical set where membership is binary — an element either fully belongs (1) or does not belong (0): μ_A(x) ∈ {0,1}.

Fuzzy Set: introduced by Zadeh, allows partial membership over a continuous range: μ_A(x) ∈ [0,1], modelling vague/linguistic concepts like "Tall", "Hot", "Young" that have no sharp boundary.

Definition: A Fuzzy Inference System (FIS) maps crisp inputs to crisp outputs using fuzzy IF-THEN rules. The Mamdani model (the most common) uses fuzzy sets for both the rule antecedents and consequents.

Steps:

1. Fuzzification: compute membership degree of the crisp input in each linguistic fuzzy set.
2. Rule Evaluation: for each rule "IF x is A AND y is B THEN z is C", compute firing strength = min(μA(x), μB(y)) (AND = min, OR = max), and clip/scale the consequent set C by this strength.
3. Aggregation: combine all clipped output fuzzy sets using max, forming one aggregated output fuzzy region.
4. Defuzzification: convert the aggregated fuzzy output to one crisp number, typically via the Centroid (Center of Gravity) method: z* = ∫μ(z)·z dz / ∫μ(z) dz.

The Mamdani model is widely used in control systems (e.g. washing machines, AC thermostats) because its rules are intuitive and human-readable.

Definition: Inductive learning builds a general hypothesis (model) from a set of labelled training examples so it can classify unseen instances. ID3 (Iterative Dichotomiser 3) is a greedy, top-down algorithm that builds a Decision Tree by recursively splitting on the attribute that best separates the classes.

ID3 algorithm:

1. If all examples belong to one class, return a leaf with that class.
2. Else compute Information Gain for every remaining attribute; select the attribute A with the highest gain as the decision node.
3. Partition examples by each value of A, and recursively build a subtree for each partition.
4. Stop when a branch is pure, attributes are exhausted, or examples run out.

Because it always greedily picks the locally best split, ID3 builds compact trees quickly, but can overfit noisy data and, unlike C4.5, cannot directly handle continuous attributes or missing values.

Entropy measures the impurity/disorder of a set S with respect to the target class:

Entropy(S) = − ∑_i=1^c p_i log₂(p_i)

where p_i is the proportion of examples of class i. Entropy = 0 for a pure set (all one class) and is maximal (=1 for binary classes) when classes are evenly split.

Information Gain of splitting S on attribute A is the reduction in entropy achieved by the split:

Gain(S,A) = Entropy(S) − ∑_{v∈Values(A)} (|S_v|/|S|) · Entropy(S_v)

Worked mini-example: S has 10 examples: 6 Yes, 4 No. Entropy(S) = −(0.6log₂0.6 + 0.4log₂0.4) = −(0.6×(−0.737) + 0.4×(−1.322)) = 0.442+0.529 = 0.971 bits. If attribute A splits S into S1 (5 examples: 5 Yes, 0 No, Entropy=0) and S2 (5 examples: 1 Yes, 4 No, Entropy = −(0.2log₂0.2+0.8log₂0.8)=0.722):

Gain(S,A) = 0.971 − [(5/10)×0 + (5/10)×0.722] = 0.971 − 0.361 = 0.610 bits

ID3 picks the attribute with the maximum Gain at each step, since it produces the purest (lowest-entropy) child partitions.

Definition: Natural Language Processing (NLP) systems typically analyze a sentence through five sequential phases, each building on the previous one's output.

1. Lexical/Morphological Analysis: breaks text into tokens/words and analyzes word structure (stems, affixes, POS tagging).
2. Syntactic Analysis (Parsing): checks grammatical structure and builds a parse tree using a grammar (e.g. CFG).
3. Semantic Analysis: extracts literal, context-independent meaning (word-sense disambiguation, mapping to logical form).
4. Discourse Integration: resolves meaning that depends on preceding sentences (e.g. pronoun/anaphora resolution across sentences).
5. Pragmatic Analysis: interprets the intended meaning using real-world context/knowledge beyond the literal text (e.g. sarcasm, implied intent).

Definition: Syntactic Analysis (Parsing) checks whether a sentence conforms to the grammar of the language and builds a parse tree representing its grammatical structure, using a formal grammar such as a Context-Free Grammar (CFG).

Approaches:

• Top-Down Parsing: starts from the start symbol S and expands rules trying to derive the input string (predictive, but can loop on left-recursive grammars).
• Bottom-Up Parsing: starts from the input words and repeatedly reduces groups of symbols up to the start symbol (e.g. shift-reduce, CYK, chart parsing).
• Chart Parsing: a dynamic-programming technique that stores partial parses (edges) in a chart to avoid recomputation, enabling efficient (polynomial-time) parsing of ambiguous grammars.

Correct parsing is prerequisite for semantic analysis, since meaning composition follows the syntactic structure of the sentence.

Definition: An Expert System is a program that emulates the decision-making ability of a human domain expert using an encoded knowledge base and an inference mechanism.

• Knowledge Base: stores domain facts and heuristic rules (typically IF-THEN production rules) supplied by human experts.
• Inference Engine: applies forward or backward chaining over the KB to derive conclusions/recommendations for a given case.
• Working Memory: holds facts about the current case/session.
• User Interface: handles interaction — takes case data from and delivers conclusions to the user.
• Explanation Facility: answers "why"/"how" a conclusion was reached, tracing the rule-firing chain.
• Knowledge Acquisition Module: supports adding/updating rules, often assisted by a knowledge engineer.

Separating the Knowledge Base from the Inference Engine (unlike hard-coded programs) is what allows expert systems to be updated by simply editing rules, without reprogramming the reasoning logic.

Definition: An Expert System Shell is a ready-made expert system framework with the inference engine, user interface, and explanation facility already built, but with an empty Knowledge Base — the developer only has to plug in domain-specific rules and facts (e.g. EMYCIN was created by stripping MYCIN's medical rules out, leaving a general reasoning shell).

Benefits:

• Faster development: avoids rebuilding the inference engine, UI, and explanation module from scratch for every new application.
• Lower cost: reduces the software engineering effort and cost of building an expert system, since only knowledge engineering is needed.
• Reusability: the same shell can be reused across multiple domains (medical, financial, technical) by swapping the knowledge base.
• Easier maintenance: domain experts/knowledge engineers can update rules without touching the underlying reasoning engine.
• Built-in tools: most shells provide debugging, tracing, and explanation tools out-of-the-box, aiding verification and validation.

Limitation: a shell constrains the developer to its built-in inference strategy (e.g. only backward chaining) and knowledge representation style, which may not suit every problem domain.

Definition: A Perceptron is the simplest artificial neuron model: it computes a weighted sum of its inputs, adds a bias, and passes the result through an activation function to produce an output.

net = ∑_i w_ix_i + b; output = f(net)

Common activation functions:

A single perceptron can only learn linearly separable functions (e.g. AND, OR, but not XOR); the perceptron learning rule updates weights as w_i ← w_i + η(target−output)x_i. Non-linear separability requires a Multi-Layer Perceptron trained via Backpropagation.

Definition: Backpropagation ("backward propagation of errors") trains a Multi-Layer Perceptron by computing the gradient of the output error with respect to every weight, using the chain rule, and propagating the error backward from the output layer to the input layer.

Algorithm (per training example):

1. Forward pass: compute activations layer by layer up to the output.
2. Compute output error: δ_k = (t_k − o_k) · f'(net_k) for each output unit k.
3. Backpropagate error to hidden unit j: δ_j = f'(net_j) · ∑_k w_jkδ_k.
4. Update weights using gradient descent: w_ij ← w_ij + η · δ_j · x_i, where η is the learning rate.
5. Repeat over all training examples/epochs until error converges below a threshold.

Backpropagation is essentially the chain rule applied efficiently across a computation graph, and remains the core training mechanism (with modern optimizers like Adam) for today's deep neural networks.

Definition: Genetic Algorithms (GA) are population-based stochastic search/optimization methods inspired by natural evolution, iteratively improving a population of candidate solutions (chromosomes) using selection, crossover, and mutation.

• Encoding: represent each candidate solution as a chromosome (bit-string, permutation, or real-valued vector).
• Fitness Function: evaluates how good a chromosome is at solving the problem.
• Selection: probabilistically choose fitter individuals to reproduce (e.g. Roulette-Wheel: P(select i) = fitness_i / ∑fitness; or Tournament selection).
• Crossover (Recombination): combine genes of two parents (e.g. single-point, two-point, uniform) to produce offspring, exploring the search space.
• Mutation: randomly flip/alter a gene with small probability p_m, maintaining diversity and preventing premature convergence.
• Replacement: new generation replaces (or partially replaces) the old one; repeat until convergence or generation limit.

Definition: Reinforcement Learning (RL) trains an agent to choose actions that maximize cumulative reward through trial-and-error interaction with an environment, without labelled training data. Q-Learning is a model-free, off-policy RL algorithm that learns the action-value function Q(s,a).

Q-Learning update rule (Bellman-based):

Q(s,a) ← Q(s,a) + α [ r + γ · max_a' Q(s',a') − Q(s,a) ]

where α = learning rate, γ = discount factor, r = immediate reward, s' = next state.

Because the update uses max_a'Q(s',a') (the greedy value) regardless of the action actually taken next, Q-Learning is off-policy and provably converges to the optimal Q* under standard conditions (all state-action pairs visited infinitely often, decaying α).

Definition: The Wumpus World is a classic AIMA grid-world testbed for a knowledge-based agent: a 4×4 cave containing a Wumpus (deadly monster), pits, and gold, which the agent must navigate using logical inference from percepts.

PEAS: Performance = gold value − death penalty − step/arrow cost; Environment = 4×4 grid, partially observable, static, discrete; Actuators = move, turn, grab, shoot, climb; Sensors = Stench, Breeze, Glitter, Bump, Scream.

KB reasoning: the agent asserts percept sentences as facts (e.g. ¬Stench(1,1) ∧ ¬Breeze(1,1)) and encodes environment rules (Breeze(x,y) ↔ ∃ adjacent Pit) in propositional logic. Using inference (model checking or resolution), it proves cells are safe (¬Pit ∧ ¬Wumpus) before moving there — demonstrating how a knowledge-based agent reasons under partial observability rather than acting purely reactively.

Definition: STRIPS (Stanford Research Institute Problem Solver) represents planning actions (operators) using three components: Precondition (must hold before the action), Add-list (facts made true after), and Delete-list (facts made false after).

Working: given an Initial State (set of facts) and a Goal State (set of facts to achieve), a planner searches for a sequence of operators such that: (a) each operator's precondition is satisfied by the current state before it is applied, and (b) applying add/delete lists in sequence transforms the initial state into a state satisfying the goal.

State update rule: NewState = (CurrentState − Delete-list) ∪ Add-list. This closed-world, set-based representation makes STRIPS planning efficiently searchable and is the basis of classical planners (e.g. Goal Stack Planning, Partial-Order Planning, GraphPlan).

Definition: Goal Stack Planning (GSP) is a classical planning algorithm that uses a single stack containing both unsatisfied goals and the operators chosen to satisfy them, processing the stack top-down until it is empty.

Example (Blocks World): Initial: On(C,A), OnTable(A), OnTable(B), Clear(B), Clear(C). Goal: On(A,B) ∧ On(B,C)? — suppose Goal = On(B,C) ∧ On(A,B) with C clear initially and B,A on table. Stack processing: push conjunction → push On(B,C), On(A,B) → pop On(A,B): needs Stack(A,B) which needs Clear(B) ∧ Holding(A) — push preconditions, satisfy via PickUp(A) then Stack(A,B); continue similarly for On(B,C). GSP's weakness is the Sussman Anomaly: interacting sub-goals can conflict, undoing a goal already achieved while pursuing another — solved by re-ordering or using Partial-Order Planning instead.

Definition: The Knowledge Acquisition Bottleneck refers to the fundamental difficulty and cost of extracting expert knowledge from human specialists and converting it into a formal, machine-usable representation (rules/facts) for an expert system's Knowledge Base.

Causes:

• Tacit knowledge: experts often cannot fully articulate their intuition/experience-based reasoning ("I just know it") in explicit rule form.
• Time-intensive interviews: knowledge engineers must conduct repeated, lengthy interviews and observation sessions with domain experts, who have limited availability.
• Vocabulary/communication gap: mismatch between expert terminology and formal representation constructs used by the knowledge engineer.
• Inconsistency: different experts may give conflicting rules for the same situation, requiring reconciliation.
• Knowledge maintenance: domain knowledge evolves, requiring continual re-acquisition and updates.

Mitigation approaches: structured/repertory-grid interviewing techniques, protocol analysis (think-aloud problem solving), machine learning to induce rules automatically from case data (e.g. ID3-style decision-tree induction), and using expert-system shells with built-in knowledge-acquisition tools (e.g. TEIRESIAS for MYCIN) that let experts refine rules directly.

Definition: Classification and Regression are the two main supervised machine learning paradigms, differing in the type of output they predict.

Both are forms of Inductive Learning: given a labelled training set {(x_i, y_i)}, the algorithm learns a function f: X→Y that generalizes to unseen inputs, minimizing a loss function (e.g. cross-entropy for classification, squared error for regression) on the training data while avoiding overfitting.

Part (a): FOL Conversion and Resolution Refutation that "Marcus is dead"

Step 1 — Translate to FOL:

Step 2 — Convert to Clause (CNF) form (drop quantifiers, Skolemize where needed):

Step 3 — Resolution Refutation trace (standard textbook derivation, Marcus-is-mortal/dead chain):

1. Resolve C1 (man(Marcus)) with C8 (~man(x) ∨ mortal(x)), unify x/Marcus → derive mortal(Marcus).
2. Resolve C2 (Pompeian(Marcus)) with C3 (~Pompeian(x) ∨ Roman(x)), unify x/Marcus → derive Roman(Marcus).
3. Resolve Roman(Marcus) with C5 (~Roman(x) ∨ loyalto(x,Caesar) ∨ hate(x,Caesar)), x/Marcus → derive loyalto(Marcus,Caesar) ∨ hate(Marcus,Caesar).
4. Resolve C1, C4, C7 with C6 (~man(x) ∨ ~ruler(y) ∨ ~tryassassinate(x,y) ∨ ~loyalto(x,y)), unify x/Marcus,y/Caesar → derive ~loyalto(Marcus,Caesar).
5. Resolve step 3's clause (loyalto ∨ hate) with step 4's (~loyalto) → derive hate(Marcus,Caesar).
6. mortal(Marcus) (step 1) combined with the negated goal ~mortal(Marcus) resolves to the empty clause □ — contradiction, so KB ⊨ mortal(Marcus), and since mortal beings that have lived are dead, dead(Marcus) is proved.

Part (b): Unification Algorithm step-by-step

UNIFY(x, y, θ) recursively finds the Most General Unifier making two expressions identical:

1. If x = y (identical constants/variables), return θ unchanged.
2. If x is a variable, check the occurs check (x must not appear inside y); if safe, add {x/y} to θ and return.
3. If y is a variable, symmetric case: add {y/x} to θ.
4. If both x and y are compound terms, they unify only if they have the same predicate/function symbol and same arity; then recursively unify each corresponding pair of arguments, composing the substitutions.
5. Otherwise (mismatched constants/symbols), unification fails.

Example: UNIFY(knows(John,x), knows(y,Mother(y))): match John with y → θ={y/John}; match x with Mother(y) under θ → substitute y=John → x/Mother(John). Final MGU = {y/John, x/Mother(John)}. Unification is what allows Resolution and Generalized Modus Ponens to apply general (variable-containing) clauses to specific facts, as used throughout the derivation in Part (a).

Part (a): Alpha-Beta Pruning on the given tree

Tree structure (3 plies): Root (MAX) → 2 MIN nodes (C1, C2) → 4 MAX nodes (B1..B4) → 8 leaves. Leaves in order: B1=(3,5), B2=(6,9), B3=(1,2), B4=(0,-1).

Left-to-right DFS trace (α=best for MAX so far, β=best for MIN so far, initial window (−∞,+∞)):

Pruned branches: leaf value 9 (sibling of 6 under B2) and the entire B4 subtree (leaves 0 and −1) are never evaluated. Final Minimax value = 5 (verified: unpruned full minimax gives B1=5,B2=9,B3=2,B4=0 → C1=min(5,9)=5, C2=min(2,0)=0 → root=max(5,0)=5 — same result, confirming pruning never alters the game-theoretic value).

Part (b): Minimax Properties

Because O(b^m) is infeasible for real games (e.g. chess b≈35), practical systems apply depth-limited search with a static evaluation function and Alpha-Beta pruning (as in Part a) to search deeper within the same time budget.

Part (a): Information Gain and ID3 Decision Tree (14 samples, 9 Yes / 5 No)

This is the classic PlayTennis dataset (14 days, attributes Outlook, Temperature, Humidity, Wind; target = PlayTennis).

Step 1 — Root Entropy:

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

Step 2 — Information Gain for each attribute (standard computed values for this dataset):

Step 3 — Verification of Outlook's gain (worked): Entropy(Sunny)=−(2/5)log₂(2/5)−(3/5)log₂(3/5)=0.971; Entropy(Overcast)=0 (pure, all Yes); Entropy(Rain)=−(3/5)log₂(3/5)−(2/5)log₂(2/5)=0.971.

Gain(S,Outlook) = 0.940 − [(5/14)(0.971) + (4/14)(0) + (5/14)(0.971)] = 0.940 − [0.347+0+0.347] = 0.940 − 0.694 = 0.246 ✓

Step 4 — Build the tree: since Gain(Outlook)=0.246 is the highest, Outlook is chosen as the root. Overcast branch is pure (100% Yes) → leaf "Yes". For the Sunny branch, recompute gains among remaining attributes on the 5 Sunny examples → Humidity gives a pure split (High→No, Normal→Yes), so Humidity becomes the next node. For the Rain branch, recompute on its 5 examples → Wind gives a pure split (Weak→Yes, Strong→No).

Part (b): Overfitting and Pruning

Overfitting occurs when the tree grows so deep/complex that it memorizes noise and outliers in the training data, achieving near-100% training accuracy but poor generalization (lower accuracy) on unseen test data — typically caused by continuing to split on attributes with little statistical significance, or by very small leaf partitions.

• Pre-pruning (early stopping): stop splitting a node early using a threshold (e.g. minimum examples per leaf, maximum depth, or a statistical significance/chi-square test on the gain) before the tree becomes too complex.
• Post-pruning (reduced error pruning): grow the full tree first, then use a validation set to replace sub-trees with a leaf (majority class) if doing so does not reduce validation accuracy — this generally performs better in practice than pre-pruning since it avoids stopping too early.
• Rule post-pruning (C4.5 style): convert the tree to IF-THEN rules, then prune preconditions from each rule independently, which gives even finer-grained control.

Part (a): Bayesian Network Joint Probability — Burglar Alarm system

Using the standard AIMA Burglary-Alarm network with variables B(Burglary), E(Earthquake), A(Alarm), J(JohnCalls), M(MaryCalls), and standard CPTs:

Chain-rule decomposition (using the network's conditional-independence structure — A depends only on B,E; J and M depend only on A):

P(B ∧ ¬E ∧ A ∧ J ∧ ¬M) = P(B) · P(¬E) · P(A|B,¬E) · P(J|A) · P(¬M|A)

Substituting values (P(¬E)=1−0.002=0.998; P(¬M|A)=1−0.70=0.30):

= 0.001 × 0.998 × 0.94 × 0.90 × 0.30

Step-by-step computation:

1. 0.001 × 0.998 = 0.000998
2. 0.000998 × 0.94 = 0.00093812
3. 0.00093812 × 0.90 = 0.000844308
4. 0.000844308 × 0.30 = 0.0002532924 ≈ 2.53 × 10⁻⁴

Verification (reordering the multiplication to double-check): 0.94×0.90=0.846; 0.846×0.30=0.2538; 0.2538×0.998=0.25329...; ×0.001 = 0.00025329 — matches (rounding). Final answer: P ≈ 2.53×10⁻⁴. This tiny probability reflects the conjunction of a rare burglary, no earthquake, alarm triggering, John calling but Mary NOT calling — each low-probability/negated term compounds via the product rule.

Part (b): Naive Bayes Classifier for Text Classification

Naive Bayes applies Bayes' theorem with the (naive) assumption that features (words) are conditionally independent given the class:

P(Class | w₁,...,w_n) ∝ P(Class) · ∏_i P(w_i | Class)

1. Training: from a labelled corpus, estimate the prior P(Class) = (docs in class)/(total docs), and for every vocabulary word w, P(w|Class) = (count of w in class documents + 1) / (total words in class + |Vocabulary|) — the "+1" is Laplace (add-one) smoothing, preventing zero probability for unseen words.
2. Classification: for a new document, tokenize into words, then compute the product above for each candidate class, and choose the class with maximum posterior (MAP): Class* = argmax_c P(c)·∏P(w_i|c).
3. Log-space implementation: in practice, sums of log-probabilities are used instead of products to avoid numerical underflow: log P(c) + ∑log P(w_i|c).

Despite its "naive" independence assumption being technically false for natural language, Naive Bayes is a fast, robust, and surprisingly effective baseline for text classification (spam filtering, sentiment analysis, topic classification) — a full numeric example of this exact computation is worked out in Q24.

Part (a): A* Search Trace

Since a specific graph diagram was not reproduced in the extracted question text, the following representative weighted graph (with an admissible heuristic) is used to demonstrate the complete A* trace methodology:

Trace (f(n)=g(n)+h(n)):

Result: optimal path = S → B → C → G, total cost g(G) = 2+3+2 = 7 (cheaper than the alternative S-A-G = 4+5 = 9, confirming optimality). Node A was generated but never needed expansion since its f=9 exceeded the goal's f=7 when G was popped — illustrating how the admissible heuristic focuses search and avoids wasted expansion.

Part (b): Proof that A* is optimal when h(n) is admissible

Theorem: If h(n) never overestimates the true cost to the goal (h(n) ≤ h*(n) for all n), A* (tree-search) is guaranteed to return an optimal solution.

Proof (by contradiction): Suppose A* terminates by expanding a suboptimal goal G₂ (cost C₂) instead of the optimal goal G (cost C*, C* < C₂). Let n be an unexpanded node on the optimal path to G still in OPEN at that point (such a node must exist since the optimal path was never fully expanded). Because h is admissible:

f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C*

Since g(G₂) = C₂ and h(G₂)=0 (goal nodes have zero heuristic cost), f(G₂) = C₂. Given C* < C₂, we get f(n) ≤ C* < C₂ = f(G₂). But A* always expands the node with the lowest f-value next — so n would have been chosen before G₂, contradicting the assumption that G₂ was expanded first. Hence A* cannot terminate at a suboptimal goal; it must find the optimal solution. ∎

Part (a): CSP Map Coloring — 4 regions, 3 colors

Consider four regions A, B, C, D with adjacency: A–B, B–C, C–D, D–A, and A–C (a diagonal, so {A,B,C} form a triangle requiring 3 distinct colors), using palette {Red, Green, Blue}.

Backtracking with constraint propagation (forward checking) trace:

No backtrack was required because forward checking kept every domain non-empty at each step; if a domain had emptied (a "wipe-out"), the algorithm would backtrack to the previous variable and try its next value.

Part (b): AC-3 Constraint Propagation Trace

Trace on this map: initial domains all {R,G,B}. For arc (A,B): for each color x in D_A, some y≠x exists in D_B (since |D_B|=3>1) — arc consistent, no removal. This holds for every arc since every domain has 3 values and each constraint is a simple inequality with more than one alternative available — so pure AC-3 (without any assignment) does not reduce any domain here (all arcs already consistent); it only detects a contradiction (empty domain) once concrete assignments (as in Part a) shrink domains, which is why AC-3 is typically interleaved with backtracking (MAC — Maintaining Arc Consistency) rather than run in isolation for maps of this connectivity.

Part (a): Simulated Annealing algorithm in detail

Simulated Annealing (SA) is a probabilistic local search technique, analogous to the physical annealing of metals, designed to escape local optima that trap simple Hill Climbing.

• Unlike Hill Climbing (always greedy), SA occasionally accepts a worse state, letting it jump out of local maxima/minima.
• At high T, the acceptance probability for bad moves is high → behaves like a random walk (exploration).
• As T → 0, acceptance probability for bad moves → 0 → behaves like pure Hill Climbing (exploitation).
• With a sufficiently slow cooling schedule, SA is proven to converge to the global optimum with probability approaching 1.

Part (b): Acceptance probability P = e^(−ΔE/T)

Taking a representative "bad move" that worsens the objective by ΔE = 5 units (the exact value is problem-specific; the formula and trend below hold generally):

Interpretation: as temperature drops from 100 to 1 (a cooling schedule), the probability of accepting the same bad move (ΔE=5) falls sharply from ~95% to under 1%. This confirms the intended annealing behaviour: early in the search (high T) the algorithm freely explores including worsening moves, while late in the search (low T) it increasingly commits to only improving moves, converging like hill climbing near the end — correctly balancing exploration versus exploitation over time.

Part (a): FOL Conversion and proof that "John is a criminal" (classic AIMA example)

Step 1 — Translate to FOL:

Step 2 — Convert to CNF (Skolemize ∃x in statement 2 to constant M1):

Step 3 — Resolution Refutation chain:

1. Resolve C4 with C2,C3 (x/M1) → derive Sells(West, M1, Nono).
2. Resolve C5 with C2 (x/M1) → derive Weapon(M1).
3. Resolve C1 with C7 (American(West)), step-2's Weapon(M1), step-1's Sells(West,M1,Nono), and C6 (Hostile(Nono)) — unifying x/West, y/M1, z/Nono → all four antecedents of C1 are satisfied, deriving Criminal(West).
4. Resolve Criminal(West) with the negated goal ~Criminal(West) → empty clause □ — contradiction found.

Conclusion: KB ∧ ¬Criminal(West) is unsatisfiable, so KB ⊨ Criminal(West) — "West (John) is a criminal" is proved. (Note: the question names the agent "John"; in the standard textbook formulation the agent is "West" — the same derivation structure applies regardless of the constant's name.)

Part (b): Resolution Refutation Tree

Part (a): Fuzzy Logic Controller for an Automatic Washing Machine

Inputs: Dirtiness (0–100), Fabric Toughness (0–100, proxy for Fabric type). Output: Wash Time (0–60 minutes). Using simple triangular membership functions: Low/Delicate = (0,0,50), Medium/Normal = (0,50,100), High/Tough = (50,100,100) on the input scales, and Short=(0,0,30), Medium=(0,30,60), Long=(30,60,60) minutes on the output.

Crisp inputs: Dirtiness = 70, Fabric Toughness = 40.

Fuzzification:

μ_Medium-Dirt(70) = (100−70)/(100−50) = 30/50 = 0.6; μ_High-Dirt(70) = (70−50)/(100−50) = 20/50 = 0.4

μ_{Normal-Fabric}(40) = 40/50 = 0.8; μ_Delicate(40) = (50−40)/50 = 0.2

Part (b): Fuzzy Rules, Rule Evaluation, Defuzzification

Rule firing strength (Mamdani AND = min):

R1: min(μMedium-Dirt=0.6, μNormal=0.8) = 0.6

R2: min(μHigh-Dirt=0.4, μNormal=0.8) = 0.4

Defuzzification (Weighted-Average / simplified Centroid method): using the peak (centroid) of each triangular consequent — Medium peak = 30 min, Long peak = 60 min — weighted by firing strength:

WashTime* = (0.6 × 30 + 0.4 × 60) / (0.6 + 0.4) = (18 + 24) / 1.0 = 42 minutes

(For the exact Centroid/Center-of-Area method, this weighted-average of triangle peaks is the standard simplification used when consequent sets do not overlap significantly — the full method integrates ∫μ(z)z dz / ∫μ(z) dz over the aggregated clipped-trapezoid area, which converges to the same result for symmetric triangular sets.) The controller thus sets the wash cycle to 42 minutes for moderately dirty, normal-fabric laundry.

Part (a): Backpropagation Learning Algorithm for MLP

A Multi-Layer Perceptron (MLP) has an input layer, one or more hidden layers, and an output layer, fully connected with weighted edges and non-linear activation (e.g. sigmoid). Backpropagation trains it in two passes per example:

1. Forward Pass: propagate the input through the network layer by layer: net_j = ∑_i w_ijx_i + b_j; output o_j = f(net_j) (e.g. sigmoid f(x)=1/(1+e^−x)).
2. Compute Error: E = ½ ∑_k (t_k − o_k)² over output units k.
3. Backward Pass: propagate the error gradient backward using the chain rule (see Part b) to obtain δ for every unit, then update every weight.
4. Repeat over all training examples (epochs) until E converges below a threshold.

Part (b): Weight Update Derivation via Gradient Descent + Chain Rule

Gradient descent updates each weight opposite to the gradient of error E: Δw_ij = −η ∂E/∂w_ij.

Output layer (weight w_jk from hidden unit j to output unit k), using the chain rule ∂E/∂w_jk = (∂E/∂o_k)(∂o_k/∂net_k)(∂net_k/∂w_jk):

∂E/∂o_k = −(t_k−o_k); ∂o_k/∂net_k = o_k(1−o_k) [sigmoid derivative]; ∂net_k/∂w_jk = o_j

δ_k = (t_k − o_k)·o_k(1−o_k) ⇒ w_jk ← w_jk + η·δ_k·o_j

Hidden layer (weight w_ij from input i to hidden unit j) — error is a sum over all output units that unit j feeds into:

δ_j = o_j(1−o_j) · ∑_k δ_kw_jk ⇒ w_ij ← w_ij + η·δ_j·x_i

Illustrative numeric step: suppose a single output unit has target t=1, actual output o=0.7, and feeding hidden activation o_j=0.5, learning rate η=0.5. Then δ=( 1−0.7)×0.7×(1−0.7) = 0.3×0.7×0.3 = 0.063, and Δw_jk = 0.5×0.063×0.5 = 0.01575, so w_jk increases by 0.01575 — nudging the network toward correctly predicting t=1 on this example. Repeating this over many examples/epochs is what allows the MLP to learn a non-linear decision boundary that a single perceptron cannot represent.

Part (a): Genetic Algorithm workflow for 8-Queens

Part (b): Representation, Fitness, Selection, Crossover, Mutation

• Chromosome Representation: a permutation-free array of 8 integers [r₁,...,r₈], where index = column, value = row of the queen in that column (values 1–8, repeats allowed unless a permutation encoding is enforced).
• Fitness Function: number of non-attacking pairs of queens out of the maximum possible C(8,2) = 28 pairs. F = 28 − (number of attacking pairs). A queen pair (i,r_i), (j,r_j) attacks if r_i=r_j (same row) or |r_i−r_j| = |i−j| (same diagonal). Maximum fitness = 28 (a full solution, 0 conflicts).
• Selection: Roulette-Wheel — P(select individual k) = F_k / ∑F_i, biasing reproduction toward fitter (fewer-conflict) boards; or Tournament selection (pick best of k random individuals).
• Crossover: pick a random cut point c (1–7); offspring1 = parent1[1..c] + parent2[c+1..8]; offspring2 = the complementary combination. Example: Parent1=[3,2,7,5,2,4,1,1], Parent2=[2,4,7,4,8,5,5,2], cut at c=3 → Offspring=[3,2,7 | 4,8,5,5,2].
• Mutation: with small probability p_m (e.g. 0.05–0.1), randomly reassign one column's row value to a new random value (1–8), maintaining genetic diversity and preventing premature convergence to a local optimum.
• Termination: stop when an individual reaches fitness = 28 (a valid non-attacking configuration is found) or a maximum generation count is reached.

This GA formulation typically converges to a valid 8-Queens solution within a few hundred generations for reasonable population sizes (e.g. 50–100), since the fitness landscape, while having many local optima (boards with few conflicts), is smooth enough for crossover+mutation to escape them — unlike simple hill climbing which stalls frequently at local maxima.

Part (a): Top-Down vs Bottom-Up Chart Parsing

Chart Parsing is a dynamic-programming technique (common to both strategies) that stores every partial/complete constituent found so far as an "edge" in a shared chart data structure, indexed by span (start,end). This avoids exponential re-computation of the same sub-parse and enables efficient (polynomial time, e.g. O(n³) for CYK/Earley) parsing even for ambiguous grammars, since a sub-tree is derived only once and then reused wherever it fits.

Part (b): CFG Parsing for "The robot moved the box"

Grammar used:

Bottom-up (shift-reduce) trace: Shift "the" → reduce to Det; shift "robot" → reduce to N; reduce Det N → NP; shift "moved" → reduce to V; shift "the" → Det; shift "box" → N; reduce Det N → NP; reduce V NP → VP; reduce NP VP → S. Input accepted, sentence is grammatical.

Part (a): Expert System Development for Medical Diagnosis (MYCIN / PROSPECTOR)

MYCIN (Stanford, 1970s) was a rule-based expert system for diagnosing bacterial blood infections and recommending antibiotic therapy. Its architecture:

• Knowledge Base: ~450 production rules of the form IF (clinical evidence) THEN (conclusion) WITH certainty-factor.
• Inference Engine: goal-directed backward chaining — starts from the goal "what organism, what therapy?" and works backward, asking the physician for lab data/symptoms as needed to satisfy rule premises.
• Uncertainty handling: since medical evidence is rarely certain, MYCIN attached a Certainty Factor (CF) (from −1 fully disbelieved to +1 fully confirmed) to every rule and combined them (see Part b).
• Explanation facility: could answer "WHY" (justify why it is asking a question, by showing the rule being evaluated) and "HOW" (explain how a conclusion was reached, by showing the rule-firing chain).

PROSPECTOR (SRI, applied to mineral exploration) similarly used rules but with a Bayesian-style probabilistic updating scheme (using likelihood ratios) instead of MYCIN's ad-hoc CFs, structured as an inference network of geological evidence linked to ore-deposit hypotheses.

Part (b): Certainty Factors and Rule Chaining

Single rule: CF(Hypothesis, Rule) = CF(Rule) × max(0, CF(Evidence)) — the rule's own confidence is scaled down by how confident we are in its evidence.

Combining CFs from two independent rules concluding the same hypothesis (both rules give positive evidence, CF1 and CF2 > 0):

CF_combined = CF1 + CF2 × (1 − CF1)

Worked example: Rule1 concludes CF1 = 0.6 for a hypothesis, Rule2 independently concludes CF2 = 0.4 for the same hypothesis.

CF_combined = 0.6 + 0.4 × (1−0.6) = 0.6 + 0.4×0.4 = 0.6 + 0.16 = 0.76

(If both CFs were negative, the symmetric formula CF1+CF2(1+CF1) is used; if of opposite sign, CF_combined = (CF1+CF2)/(1−min(|CF1|,|CF2|)).) This combination rule ensures confidence increases monotonically toward +1 as more independent confirming evidence accumulates, without ever exceeding certainty (1.0), giving a computationally cheap (non-Bayesian) approximation to evidential reasoning suitable for rule-chaining in real-time consultations.

Part (a): STRIPS Planning for Block World

Initial State: On(C,A), OnTable(A), OnTable(B), Clear(B), Clear(C), ArmEmpty.

Goal State: On(A,B) ∧ On(B,C).

Plan trace using STRIPS operators (Precond/Add/Delete as defined in Q37):

Final state: On(A,B), On(B,C), OnTable(C), Clear(A), ArmEmpty — matches the Goal (On(A,B)∧On(B,C)). Plan = [Unstack(C,A), PutDown(C), PickUp(B), Stack(B,C), PickUp(A), Stack(A,B)], 6 actions.

Part (b): Verification of Plan Correctness

Each action's precondition was checked against the state produced by the previous action (shown in the table above), and every add/delete is applied in sequence with no precondition violated at any step — the standard STRIPS state-progression check (NewState=(State−Delete)∪Add) confirms the plan is valid and reaches exactly the specified goal state with no redundant actions (a minimal-length plan for this instance, since each block must be moved at least once).

Part (a): Reinforcement Learning — Q-Learning Algorithm

Q-Learning learns the optimal action-value function Q*(s,a) — the expected discounted cumulative reward of taking action a in state s and behaving optimally thereafter — through the off-policy update rule:

Q(s,a) ← Q(s,a) + α[ r + γ max_a'Q(s',a') − Q(s,a) ]

where α = learning rate, γ = discount factor, r = immediate reward. The agent typically explores using an ε-greedy policy (mostly picks the best known action, occasionally explores randomly) while the update always bootstraps off the greedy max, guaranteeing convergence to Q* given sufficient exploration.

Part (b): Q-table trace for a grid-world pathfinding agent (3 steps)

Setup: 3-state linear grid S1 → S2 → S3(Goal), single action "right". Rewards: step S1→S2 = −1, step S2→S3(goal) = +10. Parameters: α=0.5, γ=0.9. All Q-values initialized to 0.

Verification of Step 3: −1 + 0.9(5.0) = −1+4.5 = 3.5; 3.5 − (−0.5) = 4.0; 0.5×4.0 = 2.0; −0.5+2.0 = 1.5 ✓.

Observation: Q(S1,right) jumped from −0.5 to +1.5 once the goal's high reward (via Q(S2,right)=5.0) propagated backward — this is exactly how Q-Learning bootstraps future reward information back through earlier states over repeated episodes, eventually converging so that Q-values along the optimal path correctly reflect the discounted future reward.

Part (a): Dempster-Shafer Theory for Sensor Fusion

Two independent sensors report evidence about a target's identity over frame of discernment Θ = {a, b, c}. Sensor 1 gives mass function m1, Sensor 2 gives m2:

Combine via Dempster's Rule — cross every pair, classify by intersection:

Sum check (all products must total 1.0): 0.30+0.12+0.18+0.15+0.06+0.09+0.05+0.02+0.03 = 1.00 ✓ (confirms no arithmetic error).

Conflict K = 0.30 (the only ∅ term). Normalization factor = 1/(1−K) = 1/0.7 = 1.4286.

m12({a}) = (0.12+0.18)/0.7 = 0.30/0.7 = 0.4286

m12({b}) = (0.15+0.05)/0.7 = 0.20/0.7 = 0.2857

m12({a,b}) = (0.06+0.09+0.02)/0.7 = 0.17/0.7 = 0.2429

m12(Θ) = 0.03/0.7 = 0.0429 (sum = 1.0001 ✓ rounding)

Part (b): Belief and Plausibility for hypothesis {a}

Bel({a}) = ∑_B⊆{a} m12(B) = m12({a}) = 0.429 (lower bound of confidence)

Pl({a}) = ∑_{B∩{a}≠∅} m12(B) = m12({a})+m12({a,b})+m12(Θ) = 0.4286+0.2429+0.0429 = 0.714 (upper bound)

Conclusion: the fused sensor evidence gives target = a a belief-plausibility interval of [0.429, 0.714] — the width (0.285) directly reflects the residual uncertainty/ignorance in the fused evidence, which Bayesian probability alone cannot express as it would force a single point estimate.

Part (a): Conceptual Graphs and Scripts

Conceptual Graphs (Sowa) represent knowledge as a bipartite graph of concept nodes (objects/entities, in boxes) and relation nodes (in ovals) connecting them, e.g. [Cat]→(Agent)→[Chase]→(Object)→[Mouse] represents "a cat chases a mouse." They have a direct, well-defined mapping to First-Order Logic, making them both human-readable and formally sound.

Scripts (Schank & Abelson) represent stereotyped sequences of events for common situations, so a system can fill in unstated but expected details ("default reasoning"). A script has: Entry conditions (must hold before), Roles (participants), Props (objects involved), Scenes (ordered sub-event sequences), and Results (state after).

Part (b): Script for "Restaurant Dining Experience"

Usage: given only the sentence "John went to a restaurant and ordered a burger", a script-based system can automatically infer unstated facts consistent with the script — e.g. that John sat down, was given a menu, was served by a waiter, ate the food, and paid a bill — enabling common-sense question answering ("Did John pay money?") without those facts being explicitly stated in the input text.

Part (a): Wumpus World Knowledge-Based Agent using Propositional Logic

The agent maintains a Knowledge Base (KB) of propositional sentences built from percepts and the fixed rules of the world, and uses logical inference (model checking / entailment) to decide safe actions. Key percept variables: B_x,y (Breeze felt at x,y), S_x,y (Stench), P_x,y (Pit present), W_x,y (Wumpus present).

Environment axioms (told to the agent as background knowledge):

Part (b): Trace of safe-cell inference

Agent starts at (1,1). Percept: no Breeze, no Stench ⇒ assert ¬B(1,1), ¬S(1,1).

1. From ¬B(1,1) and the Breeze axiom: ¬B(1,1) → ¬P(2,1) ∧ ¬P(1,2) (if there were a pit adjacent, breeze would be felt — contrapositive). So (2,1) and (1,2) are pit-free.
2. Similarly ¬S(1,1) → ¬W(2,1) ∧ ¬W(1,2) — both cells are Wumpus-free too.
3. Hence Safe(2,1) and Safe(1,2) are both proved entailed by the KB — the agent may move to either.
4. Agent moves to (2,1); percept: Breeze felt, no Stench ⇒ assert B(2,1), ¬S(2,1). From the Breeze axiom, since B(2,1) is true, at least one of P(3,1), P(2,2), P(1,1) is a pit. But (1,1) is already known safe (visited), so by elimination the pit is in {(3,1),(2,2)} — this cell alone is not yet decidable (ambiguous), so the agent marks both as "maybe pit" and does NOT enter either without further evidence, while (1,2) (visited earlier and proven safe) remains a safe fallback move.

Conclusion: the KB-based agent only commits to moving into a cell once Safe(x,y) is logically entailed (provable by resolution or model-checking over the KB), never through guessing — this careful, provably-safe exploration is what distinguishes a knowledge-based agent from a purely reactive one in a partially observable, hazardous environment like the Wumpus World.

Part (a): Machine Learning Paradigms

Part (b): K-Means Clustering vs Support Vector Machines (SVM)

K-Means requires choosing k in advance and is sensitive to initialization and outliers (converges to a local optimum of the sum-of-squared-distances objective); SVM requires labelled data and choosing a kernel/regularization parameter C, but generalizes well even in high-dimensional feature spaces due to the margin-maximization principle (structural risk minimization).

Part (a): Case Study — Intelligent Autonomous Drone for Search and Rescue

PEAS specification:

Part (b): Sub-system design

• Sensor Fusion: combine GPS+IMU (odometry), thermal camera (detect body heat signatures), and LiDAR (obstacle map) using a Kalman Filter / Bayesian fusion to maintain a reliable pose and hazard estimate despite individual sensor noise — analogous to the Dempster-Shafer / Bayesian techniques of Q16/Q4, since no single sensor alone is fully reliable in smoke/rubble.
• Path Planning (A*): represent the disaster area as a grid; apply A* search (see Q5) with g(n)=distance/energy travelled and h(n)=Euclidean distance to the next waypoint (admissible), re-planning whenever LiDAR detects a new obstacle (dynamic replanning / D* Lite in practice).
• Knowledge Representation: maintain an internal map as a semantic/occupancy grid annotated with detected features (e.g. "possible survivor at cell (12,7), confidence 0.8"), similar to a Bayesian Network node per cell.
• Decision-Making under Uncertainty: use a utility-based agent — combine the probability of a true detection (from the sensor-fusion confidence) with the utility of investigating vs. continuing coverage, choosing the action maximizing expected utility: EU(a) = ∑P(outcome|a)×U(outcome), balancing thorough search against battery/time constraints.

This integrates search (A*), uncertain reasoning (Bayesian fusion), and PEAS-driven agent design into one coherent autonomous system — the central theme tying together the search, logic, and probabilistic-reasoning units of this syllabus.

Part (a): 4-Queens using Backtracking Search

Variables Q1,Q2,Q3,Q4 (column→row), domain {1,2,3,4}, constraints: no shared row, no shared diagonal.

Solution: (Q1,Q2,Q3,Q4) = (2,4,1,3) — re-deriving cleanly via the standard known solution and verifying all 6 pairs:

(1,2)→2,4: rowdiff=2,coldiff=1 OK | (1,3)→2,1: rowdiff=1,coldiff=2 OK | (1,4)→2,3: rowdiff=1,coldiff=3 OK | (2,3)→4,1: rowdiff=3,coldiff=1 OK | (2,4)→4,3: rowdiff=1,coldiff=2 OK | (3,4)→1,3: rowdiff=2,coldiff=1 OK

All 6 pairs have rowdiff ≠ coldiff and no repeated row — (2,4,1,3) is verified conflict-free. (The 4-Queens problem has exactly two solutions: (2,4,1,3) and its mirror (3,1,4,2).)

Part (b): Search Tree with Pruned Configurations

Part (a): Forward Chaining vs Backward Chaining Algorithms in Detail

Part (b): Backward Chaining Trace for a Horn-clause KB

KB: Facts: P, Q. Rules: R1: P ∧ Q → S. R2: S → T. Goal: T.

1. Goal = T. Search rules with conclusion T: found R2 (S → T). New sub-goal: S.
2. Goal = S. Search rules with conclusion S: found R1 (P∧Q → S). New sub-goals: P and Q.
3. Goal = P: P is already a known fact → true.
4. Goal = Q: Q is already a known fact → true.
5. Both sub-goals of R1 satisfied → S is proved → the sub-goal of R2 is satisfied → T is proved. Goal achieved.

Backward chaining explored only the rules relevant to proving T (R2, then R1), unlike forward chaining which would have fired every applicable rule (deriving S then T) regardless of whether T was actually the query — this selectivity is why backward chaining is more efficient for single-query consultations such as MYCIN.

Part (a): Semantic Nets and Frame Systems with Inheritance

Both Semantic Networks and Frame Systems organize knowledge hierarchically using ISA/AKO links, letting specific instances inherit properties from more general classes without re-stating them (see Q18, Q19 for the base mechanism). Frames additionally group an object's properties into named slots with default values and attached procedures, giving a more structured, object-oriented style of inheritance than plain semantic nets.

Part (b): Multiple Inheritance Conflicts — the Nixon Diamond

The Nixon Diamond is the classical example of a multiple-inheritance conflict: Nixon is simultaneously a Quaker (Quakers are typically pacifists, by default) and a Republican (Republicans are typically non-pacifists, by default). Both default rules apply equally, with no way to prefer one path over the other from the hierarchy alone — the system cannot decide whether Nixon is a pacifist.

Solutions:

• Explicit assertion: directly state Nixon's Pacifist value on his own frame, overriding both inherited defaults (most specific information wins).
• Specificity/priority ordering: impose an explicit priority between the conflicting parent links (e.g. "Republican overrides Quaker for this individual") when domain knowledge suggests one is more relevant.
• Non-monotonic reasoning / Truth Maintenance Systems: treat both defaults as retractable assumptions and flag the conflict for the user/expert to resolve rather than silently picking one, avoiding an unjustified inference.
• Suppress conflicting defaults: some systems simply refuse to draw either default conclusion when a genuine conflict is detected, leaving Pacifist(Nixon) undetermined.

This illustrates a fundamental weakness of naive inheritance-based representations (semantic nets/frames) compared to formal FOL-based systems, which force such conflicts to be resolved explicitly rather than left ambiguous.

Part (a): Naive Bayes Classifier for Spam Email Detection

Naive Bayes classifies an email as Spam or Ham (not spam) by choosing the class maximizing the posterior P(Class|words), using the naive conditional-independence assumption among words (see Q4b for the general algorithm). Training corpus: 8 emails total, 4 Spam, 4 Ham. Word-presence counts (number of class emails containing the word):

Part (b): Calculate P(Spam | 'Win','Free','Prize')

Priors: P(Spam) = 4/8 = 0.5, P(Ham) = 4/8 = 0.5.

Likelihoods with Laplace (add-1) smoothing (2 classes, formula (count+1)/(N+2)):

P(Win|Spam)=(3+1)/6=0.667, P(Free|Spam)=(4+1)/6=0.833, P(Prize|Spam)=(2+1)/6=0.5

P(Win|Ham)=(1+1)/6=0.333, P(Free|Ham)=(0+1)/6=0.167, P(Prize|Ham)=(0+1)/6=0.167

Un-normalized posteriors (Naive Bayes product):

P(Spam)·∏ = 0.5 × 0.667 × 0.833 × 0.5 = 0.5 × 0.2778 = 0.1389

P(Ham)·∏ = 0.5 × 0.333 × 0.167 × 0.167 = 0.5 × 0.00929 = 0.00465

Normalize (divide by the sum 0.1389+0.00465 = 0.1436):

P(Spam|Win,Free,Prize) = 0.1389/0.1436 = 0.967 (96.7%)

P(Ham|Win,Free,Prize) = 0.00465/0.1436 = 0.032 (3.2%) (sum ≈ 1.0 ✓)

Conclusion: since P(Spam|words) >> P(Ham|words), the email containing "Win", "Free", "Prize" is classified as Spam with ~96.7% posterior confidence — consistent with intuition since "Free" never appeared in any Ham training email, strongly favouring Spam.

Part (a): Neural Network Activation Functions

Part (b): Vanishing Gradient Problem in Deep Networks

During backpropagation, the gradient at an early layer is a product of the derivatives of every later layer's activation function (chain rule, see Q10). Sigmoid/Tanh derivatives are always ≤ 0.25 and ≤ 1 respectively, and are near-zero whenever the neuron is saturated (very large |x|). Multiplying many such small numbers together across many layers makes the gradient shrink exponentially toward zero as it is backpropagated to earlier layers:

∂E/∂w₁ ∝ ∏_l=1^L f'(net_l) → 0 as depth L increases (if each f' < 1)

Consequence: early layers of a deep network learn extremely slowly (weights barely update), effectively preventing deep networks from training with plain sigmoid/tanh units. Mitigations: ReLU/Leaky-ReLU activations, batch normalization, residual/skip connections (ResNets), and careful weight initialization (Xavier/He initialization).

Part (a): Convolutional Neural Network (CNN) Architecture

A CNN is a deep neural network specialized for grid-structured data (images), using local receptive fields and weight sharing to drastically reduce parameters compared to a fully-connected network, while remaining translation-invariant.

Part (b): Convolutional, Pooling, and Fully Connected Layers

• Convolutional Layer: slides a small learnable filter/kernel (e.g. 3×3) across the input, computing a dot product at each position to produce a feature map. Weight sharing (the same filter reused everywhere) drastically cuts parameters and detects the same local pattern (edges, textures) anywhere in the image.
• Activation (ReLU): applied element-wise after convolution to introduce non-linearity.
• Pooling Layer (Max/Average Pooling): down-samples each feature map (e.g. 2×2 max-pooling halves both dimensions), reducing computation and providing translation/small-distortion invariance.
• Fully Connected (Dense) Layer: after several conv+pool stages, feature maps are flattened into a vector and passed through one or more fully-connected layers (as in a standard MLP, Q32/Q33) that combine all extracted features to produce the final class scores (typically via Softmax).

Stacking multiple conv+pool stages lets a CNN learn a feature hierarchy — early layers detect simple edges/colors, deeper layers combine these into shapes and eventually whole object parts — which is why CNNs dominate image classification, object detection, and related vision tasks.

Part (a): Recurrent Neural Networks (RNN) and LSTM/GRU for Sequential Data

An RNN processes a sequence one element at a time, maintaining a hidden state h_t that summarizes information from all previous timesteps, making it suitable for text, speech, and time-series data:

h_t = f(W_hhh_t−1 + W_xhx_t + b)

Plain RNNs suffer from the vanishing/exploding gradient problem over long sequences (see Q25b), since the same recurrent weight is multiplied repeatedly through backpropagation-through-time (BPTT), making it hard to learn long-range dependencies.

Part (b): LSTM Gating Solution to Vanishing Gradients

LSTM (Long Short-Term Memory) introduces a separate cell state C_t that flows through time with only minor, additive (not repeatedly multiplicative) modifications, controlled by three sigmoid gates:

C_t = f_t ⊙ C_t−1 + i_t ⊙ &tilde{C}_t (cell state update — additive, not repeatedly multiplied by weights)

Because C_t is updated additively (through the forget-gate-scaled carry-over plus new input), the gradient can flow backward through many timesteps largely unchanged when f_t≈1, avoiding the exponential shrinkage that plagues plain RNNs. GRU (Gated Recurrent Unit) simplifies this to two gates (reset, update) merging cell and hidden state, achieving similar long-range learning with fewer parameters.

Part (a): Transformer Architecture and Self-Attention Mechanism

The Transformer (Vaswani et al.) replaced recurrence entirely with an attention mechanism, allowing every position in a sequence to directly attend to every other position in parallel, solving both the vanishing-gradient and sequential-computation limitations of RNNs/LSTMs.

Scaled Dot-Product Self-Attention: each input embedding is projected into Query (Q), Key (K), and Value (V) vectors; attention weights are computed as:

Attention(Q,K,V) = softmax( QK^T / √d_k ) V

where d_k is the key dimension (the √d_k scaling prevents dot products from growing too large and saturating the softmax). Multi-Head Attention runs several such attention computations in parallel (different learned projections), letting the model jointly attend to information from different representation subspaces, then concatenates and linearly projects the results.

Part (b): Encoder-Decoder Pipeline in Large Language Models

• Encoder stack: each layer = Multi-Head Self-Attention + position-wise Feed-Forward network, with residual connections and layer normalization around each sub-layer; processes the full input sequence in parallel (using positional encodings since attention has no inherent notion of order) to build a contextualized representation.
• Decoder stack: similar layers but with masked self-attention (a token can only attend to earlier tokens, preserving autoregressive generation) plus an additional cross-attention sub-layer attending to the encoder's output.
• LLM variants: GPT-style models use a decoder-only stack (autoregressive next-token prediction); BERT-style models use an encoder-only stack (bidirectional context, for representation learning); T5/original Transformer use the full encoder-decoder pipeline (for sequence-to-sequence tasks like translation/summarization).
• Training: next-token prediction (or masked-token prediction) at massive scale, with the self-attention mechanism letting each output token draw information from any relevant part of the input/context, regardless of distance — the property that makes Transformers superior at capturing long-range dependencies compared to RNN/LSTM (Q27).

Part (a): Knowledge Graph Construction and Entity Resolution

A Knowledge Graph (KG) represents facts as a graph of entities (nodes) connected by typed relationships (edges), enabling structured querying and reasoning over heterogeneous data (e.g. Google's Knowledge Graph, Wikidata).

Construction pipeline:

1. Information Extraction: Named Entity Recognition (NER) identifies entities in text; Relation Extraction identifies the relationships between them.
2. Entity Resolution (Entity Linking/Deduplication): different textual mentions referring to the same real-world entity (e.g. "IBM", "International Business Machines", "Big Blue") must be merged into one canonical node — typically using similarity measures (string similarity, embedding similarity) and clustering, since treating them as separate nodes would fragment the graph and corrupt query results.
3. Graph Population: extracted (Subject, Predicate, Object) triples are inserted into the graph store.
4. Ontology Alignment: entities/relations are mapped to a shared schema/ontology (e.g. schema.org types) for consistency.

Part (b): RDF Triples and SPARQL Queries

RDF (Resource Description Framework) is the standard KG data model: every fact is a triple — (Subject, Predicate, Object). Example:

SPARQL is the query language for RDF graphs, using triple patterns with variables (prefixed ?):

This query would traverse the graph (Einstein → Ulm → Germany) and return "Germany" — demonstrating how knowledge graphs enable multi-hop reasoning/querying that a flat relational table cannot express as naturally.

Part (a): Ethical, Legal, and Societal Implications of AI

• Bias and Fairness: AI models trained on historically biased data (e.g. biased hiring records, biased policing data) can learn and amplify societal biases, leading to discriminatory outcomes in loan approval, hiring, or facial recognition across demographic groups.
• Safety: autonomous systems (self-driving cars, medical diagnosis systems) must behave reliably and predictably even in rare/adversarial edge cases; failures can cause physical harm, requiring rigorous testing, verification, and fail-safe design.
• Alignment: ensuring an AI system's learned objective actually matches the intended human goal (not a proxy that is easy to optimize but diverges from true intent) — misaligned objectives can produce technically "correct" but harmful behaviour (reward hacking).
• Autonomous Weapons: Lethal Autonomous Weapons Systems (LAWS) raise serious concerns about removing meaningful human control from life-or-death decisions, accountability gaps, and the risk of an uncontrolled arms race.
• Privacy: AI systems trained on or processing personal data can enable mass surveillance or leak sensitive information (e.g. via model inversion attacks).
• Employment/Economic impact: automation of cognitive and physical tasks raises concerns about job displacement and the need for re-skilling.

Part (b): AI Governance and Explainable AI (XAI)

AI Governance refers to the frameworks, policies, standards, and regulatory bodies that oversee the responsible development and deployment of AI, including:

• Regulation: laws such as the EU AI Act which classify AI systems by risk level and impose corresponding compliance obligations.
• Standards and audits: independent algorithmic audits, bias testing, and impact assessments before deployment.
• Accountability structures: clear responsibility chains for AI-driven decisions (who is liable when an AI system causes harm).

Explainable AI (XAI) refers to techniques that make an AI model's decisions interpretable to humans, essential for trust, debugging, and regulatory compliance (e.g. "right to explanation" in some jurisdictions):

• Intrinsically interpretable models: Decision Trees (Q26), rule-based expert systems (Q30 group B) — the reasoning path is directly visible.
• Post-hoc explanation methods: LIME and SHAP approximate a complex "black-box" model's local behaviour with a simpler, interpretable surrogate around a specific prediction, attributing the output to individual input features.
• Attention visualization: for Transformers (Q28), visualizing attention weights shows which input tokens most influenced a given output, offering partial interpretability.

Together, governance frameworks and XAI techniques aim to ensure AI systems remain accountable, fair, and trustworthy as they are deployed in high-stakes domains — directly extending the reliability concerns raised for the expert systems, classifiers, and autonomous agents studied throughout this syllabus.