Artificial Intelligence, taught from nothing to full marks.

Your paper is 4 hours for 10 questions of 10 marks. That is 24 minutes per question, so budget 18 minutes writing and keep 60 minutes spare for the two numericals that will eat time (crypt-arithmetic and A*). Never leave a question blank: an examiner cannot give marks to a blank page, but a definition plus a diagram on a half-remembered topic reliably fetches 4.

The five-part skeleton

Every theory question in this paper fits this skeleton. Use it mechanically.

Question-order strategy in the hall

1. 0-5 min: read the whole paper, tick the four questions you can answer cold.
2. 5-90 min: those four theory questions, fast, with diagrams.
3. 90-150 min: the standard numericals: Bayes, A*, resolution, ID3. These are formulaic; you will have practised them.
4. 150-210 min: crypt-arithmetic and anything requiring construction (Bayesian network, decision tree).
5. 210-240 min: the weakest question, plus going back to add diagrams and headings to earlier answers.

What Artificial Intelligence actually means

Forget the movies. In this syllabus AI has a narrow, examinable meaning: the study and construction of agents that receive percepts from an environment and perform actions that are rational, that is, actions expected to maximise some performance measure. That one sentence is the definition to write in any "What is AI?" question.

Russell and Norvig, the prescribed book, organise every definition of AI ever proposed into four boxes along two axes: thinking versus acting, and human-like versus rational. Draw this table for a guaranteed 2 marks in any introductory question.

Foundations of AI: the disciplines it borrowed from

A "foundations of AI" question wants six to eight lines. One line each:

History of AI: the milestones worth naming

• 1943 McCulloch & Pitts propose the first artificial neuron model.
• 1950 Turing publishes Computing Machinery and Intelligence, proposing the Turing test.
• 1956 Dartmouth Conference: John McCarthy coins the term "artificial intelligence". Birth year of the field.
• 1956-1969 Early enthusiasm: Logic Theorist, General Problem Solver (GPS), LISP (McCarthy, 1958), perceptron (Rosenblatt, 1958).
• 1969 Minsky & Papert show a single perceptron cannot learn XOR → funding collapses.
• 1974-1980 First "AI winter": the reality of intractability and the knowledge bottleneck.
• 1980s Expert systems become industry (DENDRAL, MYCIN, XCON); Japan's Fifth Generation project; then a second winter.
• 1986 Backpropagation popularised: neural networks revive.
• 1997 IBM's Deep Blue defeats world chess champion Garry Kasparov.
• 1995 onwards The field turns to probability and statistics: Bayesian networks, HMMs, machine learning on data.
• 2011 onwards IBM Watson wins Jeopardy!; deep learning wins ImageNet (2012); AlphaGo beats Lee Sedol (2016); large language models (2020s).

The Turing test

Definition: Proposed by Alan Turing in 1950 as an operational definition of intelligence. A human interrogator, in a separate room, converses through a text-only channel with a human and a machine. If the interrogator cannot reliably tell which is which, the machine is said to have passed the test and is deemed intelligent. Turing called it the "imitation game".

Capabilities a machine needs to pass it

1. Natural language processing: to communicate in English.
2. Knowledge representation: to store what it knows and hears.
3. Automated reasoning: to answer questions and draw new conclusions.
4. Machine learning: to adapt to new circumstances and detect patterns.

Total Turing test

The standard test avoids physical interaction. The total Turing test includes a video signal and a hatch through which objects are passed, so the machine must also have:

5. Computer vision: to perceive objects.
6. Robotics: to manipulate objects and move about.

These six capabilities together are essentially the whole of AI, which is why Turing's test still structures the field.

Reverse Turing test and CAPTCHA

In a reverse Turing test the roles are inverted: a machine is the interrogator and must decide whether the entity it is talking to is a human or another machine. CAPTCHA: Completely Automated Public Turing test to tell Computers and Humans Apart, is exactly this: a server poses a distorted-text or image-selection challenge that humans solve easily and programs solve poorly.

Limitations and criticisms of the Turing test

• It tests imitation of humans, not intelligence. An aeroplane is not tested by whether it fools a birdwatcher.
• It rewards deception: a machine must pretend to be bad at arithmetic to pass.
• It is not reproducible or mathematically analysable; results depend on the interrogator's skill.
• Trivial programs can fool naive judges (ELIZA, 1966), so passing is not sufficient.
• Searle's Chinese Room argument: manipulating symbols correctly does not entail understanding.
• It is anthropocentric: it cannot recognise a non-human form of intelligence.

Asked "If the Turing test is passed, does this show computers exhibit intelligence?": answer: it shows behavioural equivalence in conversation, which is evidence of intelligence under a behaviourist definition, but it is neither necessary (a superintelligent system might fail by being too fast and accurate) nor sufficient (ELIZA-style trickery). Conclude that AI moved on to the rational-agent definition for exactly this reason.

Agents, rationality and PEAS

An agent is anything that perceives its environment through sensors and acts upon that environment through actuators. The percept sequence is the complete history of everything the agent has perceived. An agent function maps every percept sequence to an action; the agent program is its concrete implementation running on the architecture.

Rational agent

Definition: For each possible percept sequence, a rational agent selects the action that is expected to maximise its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

Rational is not the same as omniscient (rationality maximises expected not actual performance), not the same as perfect, and not the same as clairvoyant. A rational agent must also explore, learn, and be autonomous: relying on its own percepts rather than only on the designer's prior knowledge.

PEAS: how to specify a task environment

Before designing an agent you specify Performance measure, Environment, Actuators, Sensors. Always answer PEAS questions as a table.

Types of intelligent agents

Five types, in increasing order of capability. Every one of them has appeared in a paper. Learn the one-line definition, the diagram, and a named example for each.

1. Simple reflex agent

Selects an action using only the current percept, ignoring the percept history, through condition-action rules of the form if condition then action. Works only if the environment is fully observable; otherwise it gets stuck in infinite loops. Example: a thermostat; a vacuum agent whose rule is "if dirty then suck else move".

2. Model-based reflex agent

Maintains internal state: a model of the world, so it can handle a partially observable environment. The model answers two questions: how the world evolves independently of the agent, and how the agent's own actions affect the world. Example: a robot vacuum that remembers which rooms it has already cleaned; a car that remembers a vehicle it saw a moment ago and is now in its blind spot.

3. Goal-based agent

Keeps internal state and explicit goal information describing desirable situations. It asks "what will happen if I do action A, and does that bring me closer to the goal?": this requires search and planning (all of Unit 2). Slower and less efficient than a reflex agent, but far more flexible: change the goal and the behaviour changes without rewriting rules. Example: a route-finding car agent told to reach Pokhara; a chess program aiming at checkmate.

4. Utility-based agent

Goals give only a binary distinction, happy or unhappy. A utility function maps a state (or a sequence) to a real number measuring degree of happiness, so the agent can choose between conflicting goals (speed versus safety) and weigh uncertain outcomes by expected utility. Example: a taxi choosing between a fast risky route and a slow safe one; an airline pricing engine.

5. Learning agent

Any of the above can be turned into a learning agent. Four components: this list is the answer to "explain learning agents":

1. Performance element: selects external actions; this is the whole agent we described so far.
2. Critic: observes the environment through a fixed performance standard and tells the learning element how well the agent is doing.
3. Learning element: makes improvements to the performance element using the critic's feedback.
4. Problem generator: suggests exploratory actions that are suboptimal now but lead to informative experiences (this is how the agent avoids getting stuck in a local habit).

Properties of task environments

Asked as "discuss rational agent with its various task environment". Give all seven pairs, each with a one-line definition and an example, then classify one environment (chess, taxi driving) against all seven as a closing table.

Human intelligence vs machine intelligence

Applications of AI to list in that same question: healthcare diagnosis and imaging, autonomous vehicles, natural language assistants and machine translation, fraud detection and credit scoring, recommendation systems, robotics and manufacturing, agriculture (crop and pest detection), weather and disaster prediction, expert systems, computer vision and biometrics, game playing.

Problem solving as search

A goal-based agent solves a problem by deciding on a goal, formulating the problem, searching for a sequence of actions that reaches the goal, and then executing it. Formulating the problem means writing down five things, memorise this list, it is the standard opener for the whole unit:

1. Initial state: where the agent starts. In(Kathmandu).
2. Actions: ACTIONS(s) returns the set of actions applicable in state s.
3. Transition model: RESULT(s, a) returns the state reached. Together, the initial state, actions and transition model define the state space, drawn as a graph whose nodes are states and edges are actions.
4. Goal test: decides whether a state is a goal state.
5. Path cost: a numeric cost for each path; step cost c(s, a, s′) is the cost of one action. The solution is a path from initial to goal; the optimal solution is the one with the lowest path cost.

How every search algorithm is judged

Uninformed (blind) search

No information beyond the problem definition, the algorithm cannot tell a promising state from a hopeless one. It only knows whether a state is a goal.

Breadth-first search (BFS)

Expands the shallowest unexpanded node first. Implemented with a FIFO queue. Complete; optimal only when every step cost is equal; time and space O(b^d). Its fatal flaw is memory: it keeps every node of the frontier.

Uniform cost search (UCS)

Expands the node with the lowest path cost g(n), using a priority queue. It is BFS generalised to unequal step costs. Complete and optimal for any non-negative step costs. Complexity O(b^{1+⌊C*/ε⌋}) where C* is the optimal cost and ε the smallest step cost. UCS = A* with h(n) = 0: say this and you get the comparison mark free.

Depth-first search (DFS)

Expands the deepest node first, using a LIFO stack (or recursion). Space is only O(bm), which is its one great virtue. Not complete (infinite loops on cycles or infinite depth) and not optimal. Time O(b^m) which can be far worse than BFS when m ≫ d.

Depth-limited search (DLS)

DFS with a cut-off depth ℓ. Fixes the infinite-path problem but becomes incomplete if ℓ < d, and is non-optimal. Time O(b^ℓ), space O(bℓ).

Iterative deepening search (IDS)

Runs DLS with ℓ = 0, 1, 2, … until a goal is found. The best uninformed method: it combines DFS's O(bd) memory with BFS's completeness and optimality (for unit costs). Repeating the shallow levels costs little because the bottom level dominates the node count, for b = 10, d = 5, IDS generates about 123,456 nodes against BFS's 111,111, an overhead of only ~11%.

Bidirectional search

Runs two simultaneous searches, forward from the initial state and backward from the goal, stopping when the frontiers meet. Time and space fall from O(b^d) to O(b^d/2), an enormous saving. Requires the goal state to be explicitly known and the actions to be reversible, and the meeting check itself costs memory.

Informed (heuristic) search

Heuristic function h(n) = the estimated cost of the cheapest path from node n to a goal state, with h(goal) = 0. It injects problem-specific knowledge so the search can prefer promising branches. A heuristic is:

• Admissible if it never overestimates: h(n) ≤ h*(n), the true remaining cost. Admissibility is what makes A* optimal in tree search.
• Consistent (monotonic) if for every node n and successor n′, h(n) ≤ c(n, a, n′) + h(n′), the triangle inequality. Consistency implies admissibility and makes A* optimal for graph search.

Where heuristics come from: relax the problem. In the 8-puzzle, if a tile could move anywhere you get h₁ = number of misplaced tiles; if it could move to any adjacent square you get h₂ = total Manhattan distance. Both are admissible, and h₂ dominates h₁ (h₂ ≥ h₁ everywhere), so h₂ expands fewer nodes. Other sources: pattern databases, subproblem costs, and learning from experience.

Greedy best-first search

Evaluation function f(n) = h(n). Expands the node that looks closest to the goal. Fast and memory-light in practice, but incomplete (can loop) and not optimal, the classic failure is Arad→Sibiu→Fagaras→Bucharest, which greedy finds but which is 32 km longer than the route through Rimnicu Vilcea and Pitesti.

A* search: the most examined algorithm in this syllabus

Algorithm: write these steps, then trace the table:

1. Put the start node in OPEN with f = g + h; CLOSED is empty.
2. If OPEN is empty, stop and report failure.
3. Remove from OPEN the node n with the smallest f(n) and move it to CLOSED.
4. If n is the goal, stop; trace parent pointers back to give the solution path and cost.
5. Otherwise generate the successors of n. For each successor n′, compute g(n′) = g(n) + c(n, n′) and f(n′) = g(n′) + h(n′).
6. If n′ is new, add it to OPEN. If it is already in OPEN or CLOSED with a larger g, update its g and parent (re-open it if necessary); otherwise discard it.
7. Go to step 2.

Local search and optimisation

When the path to the goal is irrelevant and only the final state matters (8-queens, timetabling, VLSI layout), keep a single current state and move to a better neighbour. Memory is constant, and the state space may be infinite.

Hill climbing

A loop that continually moves in the direction of increasing value and terminates when no neighbour is higher. It is "greedy local search": it never looks beyond the immediate neighbours, keeps no search tree, and is sometimes described as trying to climb Everest in thick fog while suffering from amnesia.

Variants: Simple hill climbing (take the first better neighbour), steepest-ascent (evaluate all neighbours, take the best), stochastic (choose randomly among uphill moves), first-choice (generate successors randomly until a better one appears, good for many successors), random-restart (run hill climbing from random initial states until a goal is found; this one is complete with probability approaching 1).

Simulated annealing fixes all three by occasionally accepting a worse move with probability e^ΔE/T, where T (temperature) is lowered over time. At high T it explores almost randomly; as T → 0 it becomes ordinary hill climbing. If the schedule lowers T slowly enough it finds the global optimum with probability approaching 1. Local beam search keeps k states instead of one; genetic algorithms are beam search with sexual recombination.

Adversarial search: min-max and alpha-beta

In a two-player, zero-sum, perfect-information game (chess, tic-tac-toe), one player MAX tries to maximise the score and the opponent MIN tries to minimise it. The min-max algorithm computes the value of each node by a depth-first exploration to a terminal (or cut-off) depth, then backs values up: MAX nodes take the maximum of their children, MIN nodes the minimum. It assumes the opponent plays optimally, which is why it is suitable for chess: the resulting move is the best achievable against a perfect opponent. Complete and optimal on finite trees; time O(b^m), space O(bm).

Alpha-beta pruning keeps two bounds along the current path: α = the best (highest) value MAX can guarantee so far, β = the best (lowest) value MIN can guarantee. Prune a branch when α ≥ β, because that branch can never influence the final decision.

Constraint Satisfaction Problems (CSP)

Definition: A CSP is defined by three components:

1. X: a set of variables {X₁ … Xₙ}.
2. D: a set of domains {D₁ … Dₙ}, one per variable, listing its allowed values.
3. C: a set of constraints specifying allowed combinations of values.

A state is an assignment of values to some variables; it is consistent if it violates no constraint, complete if every variable is assigned, and a solution if it is both. The key idea is that the goal test is decomposed into constraints, so the solver can prune whole regions of the space at once instead of treating states as black boxes.

Types of constraints: unary (one variable: SA ≠ green), binary (two variables, SA ≠ WA), higher-order/global (Alldiff, the cryptarithmetic column sums), and preference/soft constraints (turned into an optimisation problem). Examples: map colouring, N-queens, Sudoku, timetable scheduling, job-shop scheduling, crypt-arithmetic.

Solving techniques to name: backtracking search (depth-first, one variable at a time); forward checking (delete inconsistent values from neighbours' domains immediately); constraint propagation / arc consistency (AC-3); and the ordering heuristics: MRV (minimum remaining values: pick the most constrained variable), degree heuristic (tie-break on the variable involved in most constraints), LCV (least constraining value: pick the value that rules out fewest choices for neighbours). Local search with the min-conflicts heuristic solves million-queens problems in seconds.

Crypt-arithmetic: the guaranteed 10 marks

Every paper since 2018 contains one. It is a CSP: variables are the letters, domains are {0…9}, constraints are all letters have different digits, no leading letter is zero, and one column-sum equation with carries per column.

The method, in the order you should write it

1. Write the sum in column form, label columns from the right as c₁, c₂, … and mark the carries.
2. Fix the forced digits first: the leading digit of a longer answer is 1; letters that repeat across columns give the strongest equations.
3. Write one algebraic equation per column, of the form (digit + digit + carry-in) = result digit + 10 × carry-out.
4. Substitute known values and reason about parity and ranges to narrow the domains, this is constraint propagation.
5. Only when the domains are small, try candidates (backtracking); reject any that repeat a digit.
6. Verify by full addition and state the mapping in a table.

All seven crypt-arithmetic problems set at PU, EAT+THAT, ODD+ODD, GO+TO, NINA+SING, LOGIC+LOGIC, WRONG+WRONG and BASE+BALL, are solved step by step in the solved questions section.

Genetic algorithms

Definition: A genetic algorithm is a randomised, population-based search and optimisation technique inspired by Darwinian natural selection, in which candidate solutions encoded as chromosomes are evaluated by a fitness function and evolved through selection, crossover and mutation over successive generations.

Steps of a genetic algorithm

1. Encoding / representation. Represent a candidate solution as a chromosome, usually a binary string, but permutations or real vectors are also used.
2. Initialise population. Generate N random chromosomes.
3. Fitness evaluation. Score each chromosome with a fitness function f(x) that measures how good that solution is.
4. Selection. Choose parents with probability related to fitness, roulette-wheel, tournament, rank or elitist selection.
5. Crossover (recombination). With probability p_c (typically 0.6-0.9) pick a crossover point and swap the tails of two parents to make two offspring. Variants: single-point, two-point, uniform.
6. Mutation. With a small probability p_m (typically 0.001-0.01) flip a bit, to maintain diversity and reintroduce lost alleles.
7. Replacement. Form the new generation, usually keeping the best individuals (elitism).
8. Termination. Stop when the fitness converges, an optimal solution is found, or a generation limit is reached. Return the fittest chromosome.

Swarm intelligence, ant colony and particle swarm optimisation

Swarm / collective intelligence is the emergence of global intelligent behaviour from the local interactions of many simple agents with no central control, ants, bees, bird flocks, fish schools. It is used when the search space is large, dynamic and distributed, and when robustness matters more than a guaranteed optimum: routing, scheduling, clustering, robot swarms, feature selection.

Ant Colony Optimisation (ACO)

Real ants deposit pheromone on their path; shorter paths are traversed more often per unit time, so they accumulate pheromone faster, so more ants follow them, a positive feedback loop that converges on the shortest route. Evaporation prevents premature convergence on a bad path.

Algorithm:

1. Initialise pheromone τ_ij on every edge to a small constant; place m ants on random nodes.
2. Each ant builds a complete tour, choosing the next node j from i with probability p_ij = [τ_ij]^α[η_ij]^β ⁄ Σ [τ_ik]^α[η_ik]^β, where η_ij = 1/d_ij is the visibility (heuristic desirability), α weights pheromone and β weights distance.
3. Evaporate: τ_ij ← (1 − ρ)·τ_ij, with evaporation rate ρ ∈ (0,1).
4. Deposit: each ant adds Δτ = Q / L_k to the edges of its tour, where L_k is its tour length: shorter tours deposit more.
5. Record the best tour; repeat from step 2 until the iteration limit or convergence.

Answer to "can search optimisation be performed with swarm intelligence?": yes: ACO solves TSP, vehicle routing, network routing and job scheduling; it is adaptive to changing graphs, inherently parallel and robust to failure of individual agents, at the cost of no optimality guarantee, several parameters to tune (α, β, ρ, Q, m) and slow theoretical convergence.

Particle Swarm Optimisation (PSO)

A population of particles flies through the search space; each remembers its own best position pbest and knows the swarm's best gbest. On each iteration:

Steps: initialise positions and velocities randomly → evaluate fitness → update pbest and gbest → update velocity and position by the equations above → repeat until convergence → return gbest. PSO is simpler than a GA (no crossover or mutation, few parameters) and works naturally on continuous problems such as neural network weight tuning.

Knowledge and its representation

Knowledge is information about the world in a form that an agent can use to decide what to do: facts, relationships, rules, procedures and heuristics. A knowledge-based agent keeps a knowledge base (a set of sentences in a formal language), TELLs it new percepts, and ASKs it what action to take; the answer follows by inference.

Types of knowledge

• Declarative: knowing that: facts and assertions. "Kathmandu is the capital of Nepal."
• Procedural: knowing how: rules, procedures, strategies. "To start the car, turn the key."
• Meta-knowledge: knowledge about knowledge: which rule to apply, how reliable a source is.
• Heuristic: rules of thumb from an expert's experience.
• Structural: knowledge of concepts, relationships and hierarchies between objects.

Knowledge representation schemes

Properties of a good representation: representational adequacy (can express everything needed), inferential adequacy (can derive new knowledge), inferential efficiency (can do so quickly, with guidance), acquisitional efficiency (new knowledge can be added easily).

Frames represent the same knowledge as a table of slots and values, which is easier to compute with:

Semantic nets and frames are used in reasoning under uncertainty by attaching certainty factors or probabilities to links and slots, and they underpin ontologies and the knowledge base of an expert system.

Propositional logic

A proposition is a declarative sentence that is either true or false. Symbols P, Q, R combine with connectives ¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (if and only if).

A sentence is valid (a tautology) if true in every model, satisfiable if true in some model, unsatisfiable if true in none. KB ⊨ α ("KB entails α") means α is true in every model in which KB is true; the whole of logical inference is machinery for deciding entailment. The key identity used by resolution is: KB ⊨ α if and only if (KB ∧ ¬α) is unsatisfiable: this is proof by refutation / contradiction.

Rules of inference: list these in any "rules for inference" question

Useful equivalences for rewriting: P → Q ≡ ¬P ∨ Q; P ↔ Q ≡ (P → Q) ∧ (Q → P); De Morgan ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q; contraposition P → Q ≡ ¬Q → ¬P; distributivity P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).

First-order predicate logic (FOPL)

FOPL adds objects, relations and quantifiers to propositional logic.

• Constants: Ram, Nepal, 3: specific objects.
• Variables: x, y, z.
• Predicates: likes(x, y), Student(x): relations returning true/false.
• Functions: father(x), plus(x, y): return objects, not truth values.
• Connectives: ¬ ∧ ∨ → ↔ as before.
• Quantifiers: ∀ (universal, "for all") and ∃ (existential, "there exists").

Advantages of FOPL: asked directly in 2018

• Expressive: represents objects, their properties, relations among them, and general rules over all objects, which propositional logic cannot.
• Concise: one quantified sentence replaces thousands of propositions, so the knowledge base is compact and maintainable.
• Well-defined syntax and semantics, so inference is sound and complete (resolution refutation).
• Declarative and modular: knowledge is separate from the inference engine, so new facts can be added without rewriting procedures.
• It is the basis of logic programming (Prolog) and of the rule bases of expert systems.
• Supports variables, functions and equality, allowing complex real-world statements.

Propositional vs predicate logic: the comparison table

Unification and substitution

Unification finds a substitution θ that makes two logical expressions identical: UNIFY(p, q) = θ where SUBST(θ, p) = SUBST(θ, q). Example: UNIFY(knows(Ram, x), knows(y, Sita)) gives θ = {y/Ram, x/Sita}. Rules: a variable may bind to any term; two different constants never unify; the occur check forbids binding x to a term containing x. Unification is what lets Generalised Modus Ponens and resolution work on quantified sentences.

Conjunctive Normal Form (CNF)

Definition: A sentence is in CNF when it is a conjunction of clauses, where each clause is a disjunction of literals: (A ∨ ¬B) ∧ (C ∨ D ∨ ¬E).

The eight steps of CNF conversion

1. Eliminate ↔: α ↔ β becomes (α → β) ∧ (β → α).
2. Eliminate →: α → β becomes ¬α ∨ β.
3. Move ¬ inwards (De Morgan): ¬(α ∧ β) → ¬α ∨ ¬β; ¬(α ∨ β) → ¬α ∧ ¬β; ¬¬α → α; ¬∀x P → ∃x ¬P; ¬∃x P → ∀x ¬P. The result is negation normal form.
4. Standardise variables apart: rename so that each quantifier uses a unique variable.
5. Skolemise: remove ∃. An ∃ not inside any ∀ becomes a new constant (a Skolem constant); an ∃ inside ∀x becomes a function of x (a Skolem function), e.g. ∀x ∃y loves(x, y) → ∀x loves(x, F(x)).
6. Drop universal quantifiers: all remaining variables are implicitly universally quantified.
7. Distribute ∨ over ∧: (α ∧ β) ∨ γ → (α ∨ γ) ∧ (β ∨ γ).
8. Flatten and separate clauses, writing each conjunct on its own line.

Both CNF problems that PU has ever set, P → ((Q ∧ ¬R) ↔ S) and "Everyone who loves all animals is loved by someone", are worked out line by line in the solved section.

Resolution and refutation

Resolution rule: from (A ∨ B) and (¬B ∨ C) infer (A ∨ C). The complementary literals B and ¬B cancel. In FOL the literals must first be made identical by unification, and the resulting substitution is applied to the resolvent.

Forward and backward chaining

Both work on Horn clauses (clauses with at most one positive literal, i.e. rules of the form P₁ ∧ P₂ ∧ … → Q), which is why they are efficient enough for real expert systems.

Forward chaining (data-driven) starts from the known facts, finds all rules whose premises are satisfied, adds their conclusions to working memory, and repeats until the goal appears or no new fact can be derived. Backward chaining (goal-driven) starts from the goal, finds rules that conclude it, and recursively tries to prove those rules' premises as sub-goals.

Why uncertainty exists, and why logic is not enough

A logical agent must believe a sentence, disbelieve it, or have no opinion. The real world does not cooperate. Consider the medical rule ∀p Toothache(p) → Cavity(p). It is wrong: toothache can be caused by gum disease, an abscess or many other things. Repairing it into Toothache(p) → Cavity(p) ∨ GumProblem(p) ∨ Abscess(p) ∨ … requires an almost unlimited list, which is the qualification problem.

Sources of uncertainty: partial observability (sensors see only part of the world), noisy or faulty sensors, non-deterministic action outcomes, incomplete or contradictory knowledge, theoretical ignorance (no complete theory of the domain exists), practical ignorance (the theory exists but the data is not available for this patient), and vague or imprecise linguistic terms ("tall", "hot").

Approaches to handling uncertainty: name all five

• Probability theory (Bayesian): degrees of belief in [0, 1], updated by Bayes' rule. The dominant approach; combined with utility it gives decision theory.
• Fuzzy logic: degrees of truth for vague predicates, not degrees of belief.
• Certainty factors: the ad-hoc [−1, 1] confidence scores used by MYCIN.
• Dempster-Shafer theory: belief functions over sets of hypotheses; distinguishes "unknown" from "equally likely".
• Non-monotonic / default reasoning: conclusions can be retracted when new facts arrive (birds fly, but Tweety the penguin does not).

Basic probability

Bayes' rule: derive it, then use it

Bayesian belief networks

Definition: A Bayesian (belief) network is a directed acyclic graph in which each node is a random variable, each directed edge X → Y means "X is a direct cause of / directly influences Y", and each node carries a conditional probability table (CPT) giving P(node | its parents). It is a compact representation of the full joint distribution.

Steps to construct a Bayesian network

1. Identify the relevant random variables and their domains.
2. Order the variables so that causes come before effects: a causal order gives the sparsest network.
3. For each variable in order, choose the minimal set of already-placed variables that directly influence it; draw arrows from those parents.
4. Write the CPT for each node, 2^k rows for k boolean parents. Root nodes get priors.
5. Check acyclicity, and check that the conditional independence assumptions the graph asserts are actually reasonable.

Inference in belief networks means computing P(query | evidence). Exact methods: inference by enumeration of the joint, and variable elimination (which reuses repeated sub-expressions). Because exact inference is NP-hard in general networks, approximate methods are used: direct sampling, rejection sampling, likelihood weighting and Markov chain Monte Carlo (Gibbs sampling).

Applications: medical diagnosis (Pathfinder), spam filtering, fault and network diagnosis, speech recognition, gene regulatory networks, risk analysis and insurance, image segmentation, troubleshooting wizards, information retrieval. Advantages: compact, encodes causal structure readably, handles missing data, combines expert knowledge with data, supports both diagnostic (effect → cause) and causal (cause → effect) reasoning. Limitations: exact inference is NP-hard; the network structure and CPTs are hard to elicit; it assumes a fixed, acyclic causal structure; poor at continuous variables without discretisation.

Knowledge engineering for uncertain reasoning

The process of building the probabilistic model: (1) decide what to talk about, (2) decide on the vocabulary of random variables, (3) encode general knowledge about dependences, the network topology, (4) encode a description of the specific problem instance as evidence, (5) pose queries and check the answers against expert intuition, (6) debug and refine the model. This mirrors ordinary knowledge engineering but with probabilities rather than hard rules.

Fuzzy logic

Definition: Fuzzy logic, introduced by Lotfi Zadeh in 1965, is a many-valued logic in which the truth value of a proposition is a real number in [0, 1] rather than just 0 or 1. It models vagueness: the fact that predicates like "tall", "hot" or "fast" have no sharp boundary, as opposed to probability, which models likelihood.

A fuzzy set A over a universe X is defined by a membership function μ_A(x) → [0, 1]. Operations: union μ_A∪B = max(μ_A, μ_B); intersection μ_A∩B = min(μ_A, μ_B); complement μ_¬A = 1 − μ_A. Common membership shapes: triangular, trapezoidal, Gaussian, sigmoid.

The fuzzy inference system: four blocks

1. Fuzzification. Convert crisp inputs into degrees of membership in the linguistic sets (22°C → Cold 0.5, Warm 0.32).
2. Knowledge base / rule base. IF-THEN rules written by an expert in linguistic terms: IF temperature is Hot AND humidity is High THEN fan speed is Fast.
3. Inference engine. Evaluate each rule: take the min (AND) or max (OR) of the antecedent memberships to get the firing strength, clip or scale the consequent set accordingly, then aggregate all rule outputs by max. (Mamdani method; Sugeno uses a functional consequent.)
4. Defuzzification. Convert the aggregated fuzzy output back to a crisp number. Methods: centroid / centre of gravity (most common), mean of maxima, weighted average, bisector.

Advantages: handles vague, linguistic and imprecise knowledge; rules are readable by domain experts; robust to noisy or missing inputs; no exact mathematical model of the plant is needed; smooth, continuous control; simple and cheap to implement in hardware. Limitations: membership functions and rules are chosen by hand with no formal method; not based on probability so it cannot learn from data by itself; validation is difficult; performance degrades as the number of variables (and hence rules) grows.

What learning means for an agent

Definition (Mitchell): A computer program is said to learn from experience E with respect to a class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E. In agent terms: learning is any modification of the agent's components that improves its future performance, driven by feedback from the critic.

Three things determine the design of any learning element: which component is being improved, what prior knowledge the agent already has, and what feedback is available. The third determines the type of learning.

Supervised, unsupervised and reinforcement learning

This comparison has appeared in nine of the twelve papers. Learn the table, the three examples, and the diagram.

Classification vs regression vs clustering vs association

Classification vs clustering in one line: classification is supervised and assigns data to predefined classes learned from labelled examples; clustering is unsupervised and discovers the groups itself from similarity, with no labels and no predefined classes.

Inductive learning and learning from observations

Inductive learning is the task of finding a hypothesis h that approximates an unknown target function f, given a training set of examples (x, f(x)). It is induction: reasoning from specific examples to a general rule, so the conclusion is never guaranteed, only supported.

• Hypothesis space H: the set of functions the learner is allowed to consider. If the true f ∈ H the problem is realisable.
• Ockham's razor: prefer the simplest hypothesis consistent with the data.
• Overfitting: the model memorises noise in the training data; training error is tiny but test error is large. Cured by more data, pruning, regularisation, early stopping, dropout, simpler models.
• Underfitting: the model is too simple to capture the pattern; both errors are high. Cured by a richer model or better features.
• Validation: split into training / validation / test sets (typically 60/20/20), or use k-fold cross-validation: divide into k folds, train on k−1 and test on the remaining one, rotate, and average. Model selection uses the validation set; the test set is touched only once, at the end.

Decision trees

Definition: A decision tree is a supervised learning model shaped like a flowchart, in which each internal node tests one attribute, each branch is an outcome of that test, and each leaf gives a class label (classification tree) or a value (regression tree). Classification is done by walking from the root to a leaf following the tests, which is exactly how the tree performs inference.

ID3 and information gain: the formulas you must write

ID3 (Iterative Dichotomiser 3, Quinlan 1986) builds the tree top-down, greedily choosing at each node the attribute with the highest information gain, and recursing on each branch until the examples at a node are pure or no attributes remain.

Handy logs for the exam: log₂(1/2) = −1, log₂(1/3) = −1.585, log₂(2/3) = −0.585, log₂(1/4) = −2, log₂(3/4) = −0.415, log₂(1/5) = −2.322, log₂(2/5) = −1.322, log₂(3/5) = −0.737, log₂(3/8) = −1.415, log₂(5/8) = −0.678.

Types of decision tree: classification trees (discrete label) and regression trees (continuous value); by algorithm: ID3 (information gain, categorical only), C4.5 (gain ratio, handles continuous attributes and missing values, prunes), CART (Gini index, binary splits, does both classification and regression), CHAID (chi-square).

Significance: easy to understand and to explain to a non-expert (white-box model); needs little data preparation: no normalisation or scaling; handles both numeric and categorical data; fast at prediction time; performs implicit feature selection; converts directly into rules. Limitations: unstable: a small change in data can change the whole tree (high variance); greedy so it does not guarantee the globally optimal tree; strongly prone to overfitting without pruning; biased towards attributes with many values; poor at capturing smooth or linear relations; can be biased if classes are imbalanced.

Pruning combats overfitting: pre-pruning (stop early on a depth, minimum-samples or significance criterion) and post-pruning (grow the full tree, then remove subtrees that do not improve validation accuracy, reduced-error pruning, cost-complexity pruning).

Decision tree vs random forest

Example to close with: for credit approval a single tree gives the bank a reason it can quote to the customer; a random forest of 500 trees gives a few percent more accuracy but cannot be explained in a rejection letter.

Evaluating a classifier

Validation approaches: hold-out split, k-fold cross-validation, leave-one-out, stratified sampling (preserves class proportions), and bootstrap. The results go into a confusion matrix.

Neural networks

An artificial neural network is a computing system of simple interconnected processing units (neurons) modelled on the brain, in which knowledge is stored in the weights of the connections and learned by adjusting those weights from data.

The perceptron

Definition: A perceptron (Rosenblatt, 1958) is the simplest neural unit, a single neuron that computes a weighted sum of its inputs plus a bias and passes it through an activation function to produce an output.

Activation functions

Why a perceptron is a linear classifier, and why XOR breaks it

The perceptron fires when w₁x₁ + w₂x₂ + b ≥ 0. That equation defines a straight line (a hyperplane in higher dimensions) that divides the input space into two half-planes. So a perceptron can only represent linearly separable functions. AND, OR and NOT are linearly separable and one perceptron learns each of them. XOR is not: its true points (0,1) and (1,0) lie on one diagonal and its false points (0,0) and (1,1) on the other, so no single straight line separates them.

The fix: a multilayer perceptron. XOR = (x₁ OR x₂) AND NOT(x₁ AND x₂), so two hidden neurons, one computing OR, one computing NAND, feeding an AND output neuron solve it. One concrete set of weights: hidden h₁ = step(x₁ + x₂ − 0.5) (OR), h₂ = step(−x₁ − x₂ + 1.5) (NAND), output y = step(h₁ + h₂ − 1.5) (AND). The hidden layer transforms the input space into one in which the classes are linearly separable: that is the whole purpose of hidden layers.

Multilayer perceptron (MLP)

Definition: A feed-forward network with an input layer, one or more hidden layers of non-linear units, and an output layer, fully connected between adjacent layers, with information flowing in one direction and no cycles. With one sufficiently large hidden layer and a non-linear activation, an MLP is a universal approximator: it can approximate any continuous function to arbitrary accuracy.

Backpropagation

Definition: Backpropagation is the supervised learning algorithm for multilayer networks. It repeatedly (i) propagates an input forward to produce an output, (ii) computes the error against the target, and (iii) propagates that error backwards, using the chain rule of calculus to find the gradient of the error with respect to every weight, then updates each weight by gradient descent.

Learning and validation in backpropagation: the dataset is split into training and validation sets. Weights are updated only on the training set; after each epoch the error on the validation set is measured. Training error falls monotonically, but validation error falls and then starts to rise, that turning point is the onset of overfitting, and training is stopped there (early stopping). Cross-validation, regularisation, dropout and momentum are the other standard controls.

When do we need backpropagation? Whenever a network has hidden layers: the perceptron rule only works when the target output of a unit is known, and for hidden units it is not. Backpropagation supplies that missing error signal by the chain rule. Limitations: slow convergence, local minima, vanishing gradients in deep sigmoid networks, sensitivity to the learning rate and initial weights, and the need for large labelled datasets.

Hebbian learning

The oldest learning rule (Donald Hebb, 1949), often summarised as "neurons that fire together, wire together": if two connected neurons are active simultaneously, the strength of the connection between them increases. It is unsupervised: no target output is used.

Example. Train a Hebbian unit on the AND function in bipolar form (inputs and targets in {−1, +1}), starting from w₁ = w₂ = b = 0 with η = 1:

Hebbian learning explains associative memory and conditioning (the bell and the food in Pavlov's experiment) and underlies Hopfield networks, but unmodified it grows weights without bound, so practical versions normalise (Oja's rule).

Reinforcement learning in a little more depth

The agent occupies a state s, takes an action a, receives a scalar reward r and moves to s′. It learns a policy π that maximises expected discounted return. The central trade-off is exploration versus exploitation: trying new actions to gather information versus taking the best-known action now (handled by ε-greedy or softmax action selection).

Example: a robot in a grid gets +10 for reaching the goal, −10 for a pit and −1 per step; after many episodes the Q-table encodes the shortest safe route. Applications: game playing (AlphaGo, Atari), robot control, self-driving, dynamic pricing, recommendation, traffic-signal control.

Other learning methods worth two marks each

Knowledge in learning

Pure inductive learning starts from a blank slate; in practice an agent already knows a great deal, and prior knowledge makes learning far faster and from far fewer examples. Explanation-based learning (EBL) generalises from a single example by explaining why it worked using background knowledge. Relevance-based learning (RBL) uses knowledge about which attributes matter to cut the hypothesis space. Knowledge-based inductive learning (KBIL) and inductive logic programming (ILP) find hypotheses that, together with background knowledge, explain the observations, allowing the learner to invent new predicates.

Expert systems

Definition: An expert system is a computer program that uses a knowledge base of human expertise and an inference engine to solve problems within a narrow domain at a level comparable to a human expert, and can explain its reasoning.

Characteristics: high performance in a narrow domain; use of heuristic and judgemental knowledge; separation of knowledge from the inference mechanism; ability to explain why a question is asked and how a conclusion was reached; ability to reason under uncertainty; symbolic rather than numerical reasoning.

Components: explain each with one line and an example

1. Knowledge base. The domain knowledge: facts and heuristic IF-THEN production rules acquired from human experts. IF the patient has a fever AND a stiff neck THEN suspect meningitis (CF 0.7). This is what makes the system expert.
2. Inference engine. The reasoning mechanism that matches rules against the working memory, resolves conflicts when several rules fire (by priority, specificity or recency), and applies forward or backward chaining to reach a conclusion.
3. Working memory (database of facts). Holds the facts of the current case: this patient's symptoms and test results, and the intermediate conclusions derived so far.
4. User interface. Lets a non-expert consult the system in near-natural language, asking questions and displaying conclusions.
5. Explanation facility. Answers "why are you asking this?" and "how did you reach that diagnosis?" by replaying the chain of fired rules. This is essential for user trust and for medical or legal accountability.
6. Knowledge acquisition subsystem. The tools by which the knowledge engineer adds, edits and validates rules obtained from the domain expert, the main bottleneck in building the system.

People involved: the domain expert (supplies knowledge), the knowledge engineer (elicits and encodes it), the end user (consults the system), and the system builder / tool vendor. Classic systems to name: DENDRAL (chemical structures, the first), MYCIN (bacterial infections, certainty factors, Stanford), XCON/R1 (configuring DEC computers), PROSPECTOR (mineral exploration), CADUCEUS (internal medicine).

Stages in developing an expert system

1. Problem identification and feasibility. Is the domain narrow, is a human expert available, is the knowledge heuristic rather than algorithmic, is the payoff worth it?
2. Knowledge acquisition. Interview the expert, observe cases, study manuals; the hardest and slowest stage.
3. Knowledge representation. Choose rules, frames or logic and formalise the knowledge into that structure.
4. Design and tool selection. Select a shell (CLIPS, JESS, Prolog) or build from scratch; design the inference strategy and the user interface.
5. Prototype development. Build a small system covering a core subset of cases.
6. Testing, verification and validation. Run historical cases; compare conclusions against the expert's; measure accuracy, sensitivity and specificity.
7. Deployment and user training.
8. Maintenance and refinement. Update rules as domain knowledge changes; the knowledge base is never finished.

Advantages: preserves scarce expertise and makes it available anywhere, any time; consistent, unbiased and tireless; fast; useful for training juniors; explains its reasoning; can combine the knowledge of several experts. Disadvantages: no common sense or creativity; brittle at the edges of its domain, it fails badly rather than gracefully; expensive and slow to build because of the knowledge-acquisition bottleneck; cannot learn from experience by itself; needs constant maintenance; cannot handle novel situations its rules do not cover. Applications: medical diagnosis, geological prospecting, financial credit and fraud assessment, equipment fault diagnosis, process control, agricultural advice, legal reasoning, configuration and scheduling, helpdesks.

Natural Language Processing

Definition: NLP is the branch of AI concerned with enabling computers to read, understand, interpret and generate human language. It has two halves: natural language understanding (text or speech → meaning) and natural language generation (meaning → text or speech).

Why NLP is difficult: the problems of natural language understanding

• Ambiguity at every level (below): the central problem.
• Context dependence: the meaning of "it" or "there" depends on earlier sentences and on the physical situation.
• Need for world knowledge and common sense: "The trophy did not fit in the suitcase because it was too big", resolving "it" requires knowing about sizes and containers.
• Idioms, sarcasm, metaphor and humour that cannot be composed from word meanings.
• Ellipsis and anaphora: omitted words and pronoun references.
• Language variation: dialect, code-mixing (Nepali-English), spelling errors, new coinages, informal social-media text.
• Speech-specific problems: homophones, no clear word boundaries in continuous speech, accents, background noise.
• Resource scarcity for low-resource languages such as Nepali, few annotated corpora, no reliable parsers.

The stages of NLP

1. Lexical / morphological analysis. Break the text into tokens, identify word structure, roots, prefixes, suffixes, and assign parts of speech. "unhappiness" → un + happy + ness.
2. Syntactic analysis (parsing). Check the sentence against the grammar and build a parse tree showing how words group into phrases. "Colourless green ideas sleep furiously" is syntactically valid but semantically nonsense; "the boy the apple ate" is rejected here.
3. Semantic analysis. Attach meaning to the structure, checking that it is meaningful in the domain. "Hot ice-cream" is rejected at this stage.
4. Discourse integration. Interpret each sentence in the light of those around it, resolving pronouns and references. "Ram went home. He was tired."
5. Pragmatic analysis. Interpret intended meaning in the real-world context. "Can you pass the salt?" is a request, not a question about ability.

How a parse tree helps

A parse tree makes the grammatical structure of a sentence explicit, showing which words modify which. This lets the system (i) verify grammaticality, (ii) identify subject, verb and object for meaning extraction, (iii) resolve structural ambiguity by generating one tree per reading, and (iv) feed a systematic, compositional semantic interpretation.

Ambiguity in NLP: one example each, and do not mix them up

Applications of NLP: machine translation, chatbots and virtual assistants, sentiment analysis, spam filtering, speech recognition and synthesis, information retrieval and search, text summarisation, question answering, optical character recognition, grammar checking.

Certain Do these first: one of each will be on the paper

1. Solve a crypt-arithmetic problem stating all necessary conditions. Practise EAT+THAT and NINA+SING by hand until you can do either in 15 minutes. → solutions
2. Trace A* on a given graph and report the solution cost. With the OPEN/CLOSED table and an admissibility comment. → solutions
3. Represent a knowledge base in FOPL and prove a goal by resolution. → solutions
4. A Bayes' rule numerical with interpretation. → solutions
5. Components of an expert system + architecture diagram + development stages. → Unit 6
6. Supervised vs unsupervised vs reinforcement learning with examples. → Unit 5

Very likely Second priority

7. Explain backpropagation with an example; how learning and validation are done. → worked numerical
8. What is a perceptron? Can a single perceptron design an XOR gate? Justify. → Fig 5.3
9. Types of intelligent agent with diagrams and examples. → Unit 1
10. How can uncertainty be represented using fuzzy logic? Explain with an example. → Unit 4
11. Decision tree: types, significance, limitations; compare with random forest; ID3 with an example. → Unit 5, worked ID3
12. Genetic algorithm: steps with an example; use for optimisation. → Unit 2
13. Compare forward and backward chaining with examples. → Unit 3
14. Why is CNF required? Steps, then convert P → ((Q ∧ ¬R) ↔ S). → solutions
15. Compare BFS, DFS, UCS and A* with examples; informed vs uninformed search. → Unit 2 table
16. Turing test, total Turing test, reverse Turing test / CAPTCHA, with a justified stand. → Unit 1
17. Bayesian belief network: draw the burglar alarm network with CPTs; working principle; applications. → Fig 4.1
18. Steps of NLP; why NLP is difficult; types of ambiguity with examples. → Unit 6

Worth an hour each The rest of the surface area

19. Rational agent and the seven task-environment properties; PEAS for a part-picking robot and an automated car.
20. Heuristics: definition, significance, types and challenges in informed search.
21. Min-max search and the advantages of alpha-beta pruning.
22. Hill climbing: algorithm, its three problems and their solutions.
23. Semantic nets and frames with examples; propositional vs predicate logic.
24. Swarm intelligence: ant colony optimisation and particle swarm optimisation algorithms; short notes on SVM, deep learning, machine learning, reinforcement learning.

Formulas

Numbers to remember

• log₂: 1/2 = −1 · 1/3 = −1.585 · 2/3 = −0.585 · 1/4 = −2 · 3/4 = −0.415 · 3/8 = −1.415 · 5/8 = −0.678 · 1/5 = −2.322 · 2/5 = −1.322 · 3/5 = −0.737
• Burglary CPT: P(B) = 0.001, P(E) = 0.002, P(A|b,e) = 0.95 / 0.94 / 0.29 / 0.001, P(J|a) = 0.90 / 0.05, P(M|a) = 0.70 / 0.01
• Crypt answers: EAT+THAT = 819 + 9219 = 10038 · ODD+ODD = 655 + 655 = 1310 · GO+TO = 81 + 21 = 102 · NINA+SING = 5051 + 9054 = 14105 · LOGIC×2 = 90452 → 180904 · WRONG×2 = 12734 → 25468 · BASE+BALL = 7483 + 7455 = 14938 · SEND+MORE = 9567 + 1085 = 10652
• Mammogram answer 10.2% · rare disease 0.49% · spam 99.9% · blue cab 59.3%

Lists you will be asked to produce

Ten one-line answers that carry marks

1. Rationality maximises expected performance, not actual; it is not omniscience.
2. BFS is optimal only when all step costs are equal; UCS fixes that.
3. DFS is the only classical strategy with linear O(bm) memory.
4. A*'s drawback is memory, not time, it keeps every generated node.
5. ∀ pairs with →, ∃ pairs with ∧.
6. KB ⊨ α iff (KB ∧ ¬α) is unsatisfiable, the basis of refutation.
7. Fuzzy logic models degree of truth; probability models degree of belief.
8. Without a non-linear activation, any depth of network collapses to a single linear layer.
9. A single perceptron can only separate linearly separable classes, so XOR needs a hidden layer.
10. Accuracy is a misleading metric on imbalanced data; quote recall for screening problems.

Built from the COM 713.3 syllabus and fourteen past papers, 2018-2024. Where a scanned figure was unreadable, the method is given so you can apply it to your own printed copy. Good luck: the six certain topics are worth 60 marks, and you have time to own all of them.