Artificial Intelligence exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Artificial Intelligence
- Practise search traces by hand: on one small graph, write the BFS, DFS and A* expansion orders with the frontier after every step, and check that each f = g + h value adds up.
- Draw game trees on paper and back up the minimax values level by level, then redo the same tree with alpha-beta pruning, marking each pruned branch and the bound that cut it off.
- For logic, translate English sentences into first-order logic, convert them to clause form, and work one full resolution proof and one unification with the substitution written out.
- Learn each figure, such as the agent structures, a semantic net, a frame hierarchy and the expert system architecture, by drawing it from memory and labelling every box and arrow.
Introduction and Intelligent Agents
Syllabus: AI problems; Foundations of AI; History of AI; Intelligent agents: agents and environments; The concept of rationality; The nature of environments; The structure of agents; Problem-solving agents and problem formulation
One-page revision summary
- AI builds agents that perceive their environment and act to achieve the best expected outcome.
- The four approaches to AI are thinking humanly, acting humanly, thinking rationally and acting rationally; modern AI mainly follows the rational agent approach.
- AI task domains are mundane tasks (perception, language, commonsense, robot control), formal tasks (games, mathematics) and expert tasks (diagnosis, design, fault finding).
- The physical symbol system hypothesis of Newell and Simon states that a physical symbol system has the necessary and sufficient means for general intelligent action.
- Philosophy, mathematics, economics, neuroscience, psychology, computer engineering, control theory and linguistics form the foundations of AI.
- Milestones of AI history include the artificial neuron model (1943), the Turing test (1950), the Dartmouth workshop (1956), expert systems, Deep Blue (1997) and deep learning.
- An agent perceives through sensors and acts through actuators; the agent function maps percept sequences to actions.
- Rationality depends on the performance measure, prior knowledge, available actions and the percept sequence, and it maximises expected rather than actual performance.
- A rational agent should gather information, learn from its percepts and become autonomous.
- A task environment is specified by PEAS: performance measure, environment, actuators and sensors.
- Environments are fully or partially observable, single or multi-agent, deterministic or stochastic, episodic or sequential, static or dynamic, discrete or continuous, and known or unknown.
- Agent types in increasing capability are simple reflex, model-based reflex, goal-based and utility-based agents, and any of them can become a learning agent.
- A learning agent has a performance element, a critic, a learning element and a problem generator.
- A problem-solving agent formulates a goal, formulates the problem, searches for a solution and then executes it.
- The two-square vacuum world has 2 × 2² = 8 states; with n squares it has n × 2ⁿ states.
Learn these by heart
- Agent = architecture + program.
- Rational agent: for each percept sequence, choose the action expected to maximise the performance measure, given the percepts and built-in knowledge.
- PEAS = Performance measure, Environment, Actuators, Sensors.
- Well-defined problem = initial state + actions + transition model RESULT(s, a) + goal test + path cost.
- Environment dimensions: observable, agents, deterministic, episodic, static, discrete, known.
- Learning agent = performance element + critic + learning element + problem generator.
- 8-puzzle: 9! = 362,880 arrangements, of which 9!/2 = 181,440 are reachable from any start state.
2-mark questions
1 What is the Turing test? 2 marks
The Turing test, proposed by Alan Turing in 1950, is a behavioural test of machine intelligence. A human interrogator types questions to a hidden person and a hidden computer. If the interrogator cannot reliably tell which replies come from the computer, the computer passes. The total Turing test also checks vision and the handling of objects.
2 Name any four disciplines that form the foundations of AI, with one contribution of each. 2 marks
- Philosophy: logic, methods of reasoning and the relation between mind and brain.
- Mathematics: formal logic, algorithms, computability and probability.
- Economics: decision theory and utility for making rational choices.
- Neuroscience: how networks of neurons in the brain process information.
Psychology, computer engineering, control theory and linguistics also contributed.
3 Distinguish between an agent function and an agent program. 2 marks
The agent function is an abstract mathematical mapping from every possible percept sequence to an action; it describes what the agent does. The agent program is the concrete code that implements this function on a physical architecture, taking the current percept as input. Hence agent = architecture + program.
4 What is a rational agent? How is rationality different from omniscience? 2 marks
A rational agent selects, for each percept sequence, the action expected to maximise its performance measure, given the evidence of its percepts and its built-in knowledge. Rationality maximises expected performance, whereas omniscience means knowing the actual outcome of every action in advance, which is impossible. A rational agent can still be unlucky.
5 What is a PEAS description? Give the PEAS description of a robot vacuum cleaner. 2 marks
PEAS lists the Performance measure, Environment, Actuators and Sensors that specify a task environment. For a robot vacuum cleaner:
- Performance: floor area cleaned, time taken, battery used.
- Environment: rooms, floor, dirt, furniture, people.
- Actuators: wheels, brushes, suction motor.
- Sensors: camera, bump sensor, dirt sensor, cliff sensor.
6 What are the components of a well-defined problem? 2 marks
- Initial state: where the agent starts.
- Actions: the actions applicable in each state.
- Transition model: the state that results from each action.
- Goal test: decides whether a state is a goal.
- Path cost: a numeric cost for each path.
A solution is an action sequence from the initial state to a goal state.
10-mark questions
1 What is artificial intelligence? Explain the four approaches to defining AI, and classify the problems that AI deals with into task domains with examples. 10 marks
Artificial intelligence (AI) is the branch of computer science that builds programs and machines able to do tasks that need intelligence when people do them, such as understanding language, reasoning, learning and planning. Definitions of AI differ in two ways: some deal with thought and others with behaviour, and some measure success against human performance while others measure it against an ideal standard called rationality. This gives four approaches.
1. Thinking humanly (cognitive modelling): the program should think the way people think. We first find out how the human mind works, through introspection, psychological experiments and brain imaging, and then build programs whose steps match human steps. This is the approach of cognitive science.
2. Acting humanly (the Turing test approach): a machine is intelligent if its behaviour cannot be told apart from a person's. To pass the Turing test a computer needs natural language processing, knowledge representation, automated reasoning and machine learning; the total Turing test adds computer vision and robotics.
3. Thinking rationally (laws of thought): the program reasons correctly with formal logic, deriving true conclusions from true premises. The difficulties are that informal and uncertain knowledge is hard to state in logic, and that reasoning which works in principle can be far too slow in practice.
4. Acting rationally (rational agent approach): the program is an agent that acts to achieve the best outcome or, under uncertainty, the best expected outcome. It is the most general approach, because correct inference is only one way of acting rationally, and modern AI follows it.
AI problems (task domains). The problems AI deals with fall into three groups:
- Mundane tasks: perception (vision and speech), natural language understanding, commonsense reasoning and robot control. People do these easily, yet they are hard for machines.
- Formal tasks: games such as chess and checkers, and mathematics such as logic, geometry, calculus and proving properties of programs.
- Expert tasks: engineering design, fault finding, manufacturing planning, scientific analysis, medical diagnosis and financial analysis, which need specialised knowledge.
Most AI problems share two features: the number of possibilities to search is huge, so brute force is not practical, and they need a lot of knowledge. A good AI technique therefore represents knowledge so that it captures generalisations, is easy to modify and narrows the possibilities that must be searched.
In conclusion, AI can be defined through four approaches, of which acting rationally is the most widely used, and its problems range from mundane tasks to formal and expert tasks.
2 Explain the foundations of AI and give a brief account of the history of AI. 10 marks
AI draws on ideas from several older disciplines, and its history shows waves of optimism, setbacks and steady progress.
Foundations of AI:
1. Philosophy: how the mind arises from the brain, where knowledge comes from and how reasoning leads to action; it gave the idea of formal rules of reasoning. 2. Mathematics: formal logic, algorithms, computability and its limits (undecidable and intractable problems), and probability for reasoning under uncertainty. 3. Economics: decision theory and utility, which tell an agent how to choose actions with the best expected payoff, and game theory for several agents. 4. Neuroscience: how neurons in the brain process information, which inspired artificial neural networks. 5. Psychology: cognitive psychology treats the brain as an information-processing device, which led to cognitive science. 6. Computer engineering: fast programmable computers on which AI programs run. 7. Control theory and cybernetics: machines that use feedback to reach a goal by reducing an error. 8. Linguistics: how language relates to thought, which led to natural language processing.
History of AI:
1. Early work (1943–1955): McCulloch and Pitts proposed an artificial neuron model in 1943, and in 1950 Alan Turing described the Turing test and the idea of machine learning. 2. Birth of AI (1956): John McCarthy, with Minsky, Shannon and Rochester, organised the Dartmouth workshop, where the name artificial intelligence was adopted; Newell and Simon showed the Logic Theorist, a theorem-proving program. 3. Early successes (1956 to the late 1960s): the General Problem Solver, Samuel's checkers program that learned to play well, and McCarthy's Lisp language (1958). 4. Setbacks (late 1960s and 1970s): programs failed on larger problems because of combinatorial explosion, machine translation disappointed and funding was cut, a period later called the first AI winter. 5. Expert systems (late 1960s to 1980s): DENDRAL inferred molecular structures and MYCIN diagnosed blood infections using domain knowledge; in the 1980s expert systems became a commercial boom. 6. Return of neural networks (mid-1980s): the back-propagation algorithm became widely known in 1986 and made multi-layer networks trainable. 7. Probability and machine learning (late 1980s and 1990s): Bayesian networks and hidden Markov models became standard, and in 1997 IBM's Deep Blue defeated world chess champion Garry Kasparov. 8. Big data and deep learning (2010s onwards): deep neural networks trained on huge data sets transformed vision, speech and language; AlphaGo defeated Lee Sedol at Go in 2016, and large language models followed.
In conclusion, AI grew out of philosophy, mathematics and related fields into an engineering discipline whose progress has come in waves.
3 Define agent, percept sequence, agent function and agent program. Explain the concept of rationality with an example, and distinguish rationality from omniscience. 10 marks
An agent is anything that perceives its environment through sensors and acts upon that environment through actuators. A person senses with eyes and ears and acts with hands and legs; a robot uses cameras and motors; a software agent receives keystrokes and files and acts by displaying output.
1. Percept: what the agent's sensors receive at a given instant. 2. Percept sequence: the complete history of everything the agent has perceived so far; its choice of action can depend on this history and on its built-in knowledge, but not on anything it has not perceived. 3. Agent function: a mathematical mapping from every percept sequence to an action; an abstract description of behaviour, like a huge table. 4. Agent program: the concrete implementation of the agent function, running on the agent's architecture (agent = architecture + program).
Rationality. A rational agent does the right thing, judged by a performance measure that scores the sequence of environment states its actions produce. What is rational at any time depends on four things: the performance measure, the agent's prior knowledge of the environment, the actions it can perform, and its percept sequence to date. Definition: for each possible percept sequence, a rational agent selects the action expected to maximise its performance measure, given the evidence of the percept sequence and its built-in knowledge.
Example. A vacuum agent works in two squares, A and B, both dirty at the start, with the agent in A.
1. Measure M1 gives one point for each clean square after each action, over six actions. 2. A reflex agent (suck if the square is dirty, otherwise move to the other square) does Suck, Right, Suck, Left, Right, Left. The clean counts are 1, 1, 2, 2, 2, 2, so M1 = 10. 3. A second agent remembers that both squares are clean and then does NoOp: Suck, Right, Suck, NoOp, NoOp, NoOp. Its clean counts are the same, so M1 = 10. 4. Measure M2 also subtracts one point per move. The reflex agent makes four moves: M2 = 10 − 4 = 6. The second agent makes one move: M2 = 10 − 1 = 9, the best possible score.
Both agents are rational under M1, but only the second is rational under M2: rationality depends on the performance measure.
Rationality versus omniscience. An omniscient agent knows the actual outcome of its actions, which is impossible. Rationality maximises expected performance, not actual performance. A rational agent should also gather information (looking before crossing a road), learn from what it perceives, and become autonomous instead of relying only on its designer's knowledge.
In conclusion, rationality means maximising the expected value of a clearly defined performance measure.
4 What is a task environment? Write the PEAS description of an automated taxi, and explain the properties of task environments with examples. 10 marks
A task environment is the setting in which an agent must act, together with what counts as success; it defines the problem the agent has to solve. It is specified by a PEAS description (Performance measure, Environment, Actuators and Sensors), which is the first step in designing any agent.
PEAS description of an automated taxi:
- Performance measure: safety, reaching the correct destination, short trip time, low fuel use, legality (obeying traffic rules), passenger comfort and profit.
- Environment: roads, other traffic, pedestrians, customers and weather.
- Actuators: steering, accelerator, brake, indicator signals, horn and a display for passengers.
- Sensors: cameras, GPS, speedometer, odometer, engine sensors and a touch screen for customers.
Properties of task environments:
1. Fully observable or partially observable: fully observable if the sensors give the complete relevant state at each moment, as in Sudoku. A taxi cannot see what other drivers intend, so its environment is partially observable. 2. Single agent or multi-agent: solving Sudoku is single agent; chess is competitive multi-agent; taxi driving is partly cooperative (avoiding collisions) and partly competitive (parking spaces). 3. Deterministic or stochastic: deterministic if the next state is completely fixed by the current state and the action. Taxi driving is stochastic because traffic and tyre bursts cannot be predicted exactly. 4. Episodic or sequential: in an episodic environment each decision is independent, as in labelling each photo separately; in a sequential one a decision affects later decisions, as in chess and driving. 5. Static or dynamic: dynamic if the world changes while the agent is deciding, as in taxi driving; semidynamic if only the score changes with time, as in chess with a clock; static as in Sudoku. 6. Discrete or continuous: chess has a finite number of states and moves, while a taxi's speed and position vary continuously. 7. Known or unknown: in a known environment the outcomes (or outcome probabilities) of all actions are given; otherwise the agent must learn how the environment works.
Classification of examples:
- Sudoku: fully observable, single agent, deterministic, sequential, static, discrete.
- Chess with a clock: fully observable, multi-agent, deterministic, sequential, semidynamic, discrete.
- Taxi driving: partially observable, multi-agent, stochastic, sequential, dynamic, continuous.
In conclusion, the hardest environments are partially observable, multi-agent, stochastic, sequential, dynamic, continuous and unknown; taxi driving has all these properties except that its environment is mostly known.
5 Explain the structure of agents. Describe simple reflex, model-based reflex, goal-based, utility-based and learning agents, and draw the structure of a model-based reflex agent. 10 marks
Building an agent means writing an agent program that carries out its agent function. The program runs on a computing device with physical sensors and actuators, called the architecture, so agent = architecture + program. The program takes the current percept as input and returns an action. A table-driven agent that looks up the whole percept sequence in a table is impossible in practice, because the table would be astronomically large, so practical agents use the following designs.
1. Simple reflex agents choose an action from the current percept only, ignoring the percept history, using condition–action rules such as "if the traffic light is red, then stop". They are simple and fast but work correctly only when the environment is fully observable; in a partially observable environment they can get stuck in infinite loops, which choosing actions at random can sometimes break.
2. Model-based reflex agents handle partial observability by keeping an internal state that records the parts of the world they cannot see now. The previous state is updated with each new percept using a model of the world: knowledge of how the world changes on its own and how the agent's own actions affect it. A condition–action rule is then matched against the updated state to select the action.
3. Goal-based agents also keep goal information that describes desirable situations, and choose actions that, according to the model, lead towards a goal; search and planning find the action sequences. They are more flexible than reflex agents, because changing the goal changes the behaviour without rewriting rules.
4. Utility-based agents use a utility function that maps a state to a real number measuring how desirable it is. When goals conflict (speed against safety) or outcomes are uncertain, they choose the action that maximises expected utility.
5. Learning agents can improve any of these designs. They have four parts: the performance element, which selects actions; the critic, which tells how well the agent is doing against a fixed performance standard; the learning element, which makes improvements; and the problem generator, which suggests exploratory actions that give new experience.
In conclusion, agent programs range from simple reflex rules to utility-maximising, learning designs, and each step adds knowledge and flexibility at the cost of more computation.
6 What is a problem-solving agent? Explain the steps it follows and the components of a well-defined problem, and formulate the 8-puzzle as a problem. 10 marks
A problem-solving agent is a goal-based agent that treats each world state as a whole, without internal structure. It finds a sequence of actions leading from its current state to a goal state and then carries it out.
Steps followed by a problem-solving agent:
1. Goal formulation: from the current situation and its performance measure, the agent adopts a goal, a set of world states it wants to reach. 2. Problem formulation: it decides which states and actions to consider, at a suitable level of abstraction that removes unneeded detail. 3. Search: it simulates action sequences in its model until it finds one that reaches the goal; this sequence is the solution. 4. Execution: it carries out the solution one action at a time. In a fully observable, deterministic and known environment it can ignore its percepts while doing so (open-loop execution).
Components of a well-defined problem:
- Initial state: the state the agent starts in.
- Actions: ACTIONS(s), the actions applicable in state s.
- Transition model: RESULT(s, a), the state reached by doing action a in state s. The initial state, actions and transition model define the state space, a graph whose nodes are states and whose links are actions.
- Goal test: decides whether a given state is a goal state.
- Path cost: gives a numeric cost to each path, usually the sum of the step costs.
A solution is an action sequence from the initial state to a goal state; an optimal solution has the lowest path cost.
Formulating the 8-puzzle. A 3 × 3 board holds tiles 1 to 8 and a blank (_), written row by row.
- States: the positions of the eight tiles and the blank. There are 9! = 362,880 arrangements, but only half of them, 181,440, can be reached from any given start state.
- Initial state: 123 / 4_6 / 758.
- Actions: move the blank Left, Right, Up or Down, if it stays on the board.
- Transition model: the blank swaps places with the neighbouring tile.
- Goal test: is the state 123 / 456 / 78_?
- Path cost: 1 per move.
With the blank in the centre, all four moves apply: Up gives 1_3 / 426 / 758, Down gives 123 / 456 / 7_8, Left gives 123 / _46 / 758 and Right gives 123 / 46_ / 758. None of these is the goal, and Right from 123 / 456 / 7_8 gives 123 / 456 / 78_. So Down, Right is an optimal solution with path cost 2.
In conclusion, a good formulation turns a task into a state space in which search can find an optimal solution.
Search and Game Playing
Syllabus: Searching for solutions; Uninformed search strategies: breadth-first search and depth-first search; Search with partial information (heuristic search); Hill climbing; A* and AO* algorithms; Problem reduction; Game playing: adversarial search and games; The minimax algorithm; Optimal decisions in multiplayer games; Problems in game playing; Alpha-beta pruning; Evaluation functions
One-page revision summary
- Searching for solutions builds a search tree whose root is the initial state; each node records its state, parent, action and path cost g(n).
- The frontier (open list) holds generated but unexpanded nodes, and the explored set (closed list) stops repeated states from being expanded again.
- Breadth-first search expands the shallowest node first with a FIFO queue; depth-first search expands the deepest node first with a LIFO stack.
- Iterative deepening search repeats depth-limited DFS with limits 0, 1, 2 and so on, combining the low memory of DFS with the completeness of BFS.
- Heuristic (informed) search uses an estimate h(n) of the cheapest cost from n to a goal; greedy best-first search expands the node with the lowest h(n) but is not optimal.
- Search with partial information arises when the agent cannot fully observe its state or know its actions' results: sensorless problems are searched over belief states, contingency problems need plans that branch on percepts, and exploration problems must discover states and actions by acting.
- Hill climbing keeps only the current state and moves to a better neighbour; it can stop at a local maximum, a plateau or a ridge.
- Backtracking, random restarts, sideways moves, stochastic hill climbing and simulated annealing help hill climbing escape local optima.
- A* expands the node with the smallest f(n) = g(n) + h(n) and is optimal when h is admissible (and consistent, for graph search without reopening); with h(n) = 0 it becomes uniform-cost search.
- Problem reduction splits a problem into subproblems; in an AND-OR graph an OR branch is one alternative and an AND arc joins subproblems that must all be solved.
- AO* expands a node on the current best partial solution graph, revises costs back to the root, and labels a node SOLVED when every child under its marked arc is solved.
- Adversarial search handles games in which agents have conflicting goals; chess and tic-tac-toe are deterministic two-player zero-sum games of perfect information.
- Minimax backs up utilities from the leaves, with MIN nodes taking the minimum and MAX nodes the maximum; it takes O(b^m) time and O(bm) space.
- In multiplayer games each node holds a vector of utilities, the player to move maximises its own component, and alliances may form and break.
- Problems in game playing: the game tree is huge (chess has a branching factor of about 35, so a game of 100 plies gives about 35^100, roughly 10^154 nodes), moves must be made within a time limit, and depth cut-offs cause the horizon effect.
- Games of chance such as backgammon add chance nodes to the game tree and back up expected values (expectiminimax).
- Alpha-beta pruning gives the same result as minimax; it prunes at a MAX node when the value reaches β and at a MIN node when the value falls to α.
- With perfect move ordering alpha-beta examines about O(b^(m/2)) nodes, roughly doubling the depth that can be searched in the same time.
- An evaluation function estimates the utility of a non-terminal position; it should order terminal states as the true utility does, be quick to compute and reflect the chance of winning.
Learn these by heart
- A*: f(n) = g(n) + h(n); h is admissible if h(n) ≤ h*(n) and consistent if h(n) ≤ c(n, n') + h(n').
- BFS: time and space O(b^d). DFS: time O(b^m), space O(bm).
- MINIMAX(s) = UTILITY(s) at a terminal state, the maximum over the children at a MAX node and the minimum over the children at a MIN node.
- Alpha-beta: prune at a MIN node when its value ≤ α and at a MAX node when its value ≥ β; best ordering gives O(b^(m/2)).
- AO*: cost of an arc = sum over its children of (arc cost + h(child)); h(node) = cost of its cheapest arc.
- EVAL(s) = w1 f1(s) + w2 f2(s) + ... + wn fn(s); chess material: pawn 1, knight 3, bishop 3, rook 5, queen 9.
- Hill climbing gets stuck at local maxima, plateaus and ridges.
2-mark questions
1 What are the four criteria used to evaluate a search strategy? 2 marks
A search strategy is judged by:
- Completeness: does it always find a solution when one exists?
- Optimality: does it find the lowest-cost solution?
- Time complexity: how many nodes does it generate?
- Space complexity: how many nodes must it store?
Complexity is stated using the branching factor b, the goal depth d and the maximum depth m.
2 Compare breadth-first search and depth-first search. 2 marks
- Frontier: BFS uses a FIFO queue; DFS uses a LIFO stack.
- Completeness: BFS is complete when b is finite; DFS can fail in infinite or looping spaces.
- Optimality: BFS is optimal when all step costs are equal; DFS is not optimal.
- Time: BFS O(b^d); DFS O(b^m).
- Space: BFS O(b^d); DFS only O(bm).
3 What is a heuristic function? When is a heuristic admissible? 2 marks
A heuristic function h(n) estimates the cost of the cheapest path from node n to a goal, using problem knowledge; h(goal) = 0. It is admissible if it never overestimates: h(n) ≤ h*(n) for every n, where h*(n) is the true cheapest cost. Examples: straight-line distance in route finding and misplaced tiles in the 8-puzzle.
4 What is problem reduction? What is an AND-OR graph? 2 marks
Problem reduction solves a hard problem by splitting it into smaller subproblems that are solved separately and combined. An AND-OR graph shows this: OR branches are alternative ways to solve a node, any one being enough, while an AND arc joins subproblems that must all be solved. A solution is a subgraph from the root to solved nodes.
5 Define a game as a search problem. 2 marks
A game is defined by S0, the initial state; PLAYER(s), the player to move; ACTIONS(s), the legal moves; RESULT(s, a), the state a move leads to; TERMINAL-TEST(s), true when the game is over; and UTILITY(s, p), the payoff of terminal state s for player p. In a zero-sum game such as chess, one player's gain is the other's loss.
6 What is the horizon effect? How does quiescence search reduce it? 2 marks
When search stops at a fixed depth, the program cannot see a serious loss just beyond it, so it may make delaying moves that only push the unavoidable loss past its horizon. Quiescence search reduces this by searching further from unstable positions, such as those with pending captures, so the evaluation function is applied only to quiet positions.
10-mark questions
1 Explain how a problem is solved by searching a search tree. Describe breadth-first search and depth-first search with an example, and compare them. 10 marks
Searching for solutions means exploring the state space of a well-defined problem until a goal state is found. The search builds a search tree: the root holds the initial state, and expanding a node applies every legal action to generate its children. Each node stores its state, its parent, the action that produced it and the path cost g(n).
The general search procedure is:
1. Put the node for the initial state in the frontier (open list). 2. If the frontier is empty, report failure. 3. Remove a node from the frontier according to the strategy. 4. If it holds a goal state, return the path to it. 5. Otherwise add it to the explored set (closed list), expand it, add children not seen before to the frontier, and go to step 2.
The strategy, the order in which nodes leave the frontier, is what separates one method from another. Uninformed (blind) strategies use only the problem definition. Breadth-first search (BFS) expands the shallowest node first using a FIFO queue; depth-first search (DFS) expands the deepest node first using a LIFO stack.
Example. S is the start and G the goal; children are taken left to right, and the goal test is applied when a node is removed from the frontier.
BFS trace (front of queue first):
- Remove S: frontier A, B
- Remove A: frontier B, C, D
- Remove B: frontier C, D, G
- Remove C: frontier D, G, E, F
- Remove D: frontier G, E, F
- Remove G: goal reached.
BFS order: S, A, B, C, D, G. Path S → B → G, 2 steps.
DFS trace (top of stack first):
- Remove S: stack A, B
- Remove A: stack C, D, B
- Remove C: stack E, F, D, B
- Remove E: stack F, D, B
- Remove F: stack G, D, B
- Remove G: goal reached.
DFS order: S, A, C, E, F, G. Path S → A → C → F → G, 4 steps.
Comparison:
- Completeness: BFS is complete when b is finite; DFS is complete only in finite spaces when repeated states are checked.
- Optimality: BFS finds the shallowest goal, which is optimal when all steps cost the same; DFS is not optimal, as the example shows.
- Time: BFS O(b^d); DFS O(b^m). If, as in the example, the goal test is applied on removal, BFS time and space become O(b^(d+1)), because the children of the depth-d nodes are also generated.
- Space: BFS O(b^d), as it stores a whole level; DFS O(bm), as it keeps only the current path and the unexpanded siblings.
In conclusion, BFS suits shallow goals when memory is available, while DFS suits deep spaces with little memory.
2 What is heuristic search? Explain the hill climbing algorithm with an example, and discuss its problems and their remedies. 10 marks
Uninformed search knows only the problem definition, so it expands nodes blindly. Heuristic (informed) search uses partial information about the problem, a heuristic function h(n) that estimates the cheapest cost from node n to a goal, to decide which node to expand next. In route finding h(n) can be the straight-line distance to the destination; in the 8-puzzle it can be the number of misplaced tiles. A good heuristic greatly reduces the number of nodes examined.
Hill climbing is a local heuristic search. It keeps only the current state and repeatedly moves to a better neighbouring state, like a climber who always takes an uphill step. When a lower h is better, "upwards" means towards smaller h.
Steepest-ascent hill climbing:
1. Set current = initial state. 2. Generate all successors of current and pick the best one, next. 3. If next is not better than current, stop and return current. 4. Otherwise set current = next and go to step 2.
Simple hill climbing moves to the first better successor instead of the best one.
Example. Each node shows its h value, and G (h = 0) is the goal.
- At S (h = 10) the successors are A (6) and B (8); A is best, so move to A.
- At A (6) the successors are C (5) and D (7); move to C.
- At C (5) the successors are E (6) and F (9); neither is better, so the search stops at C.
C is not the goal. Hill climbing is stuck at a local minimum of h, although the goal is only two steps from S along S → B → G; it never returned to B because B looked worse than A.
Problems of hill climbing:
- Local maximum (here a local minimum of h): a state better than all its neighbours but not the best overall, like C.
- Plateau: a flat region where all neighbours have the same value, so there is no direction to move.
- Ridge: a high region that slopes upwards, but the available moves do not run along it, so every single move goes downhill.
Remedies:
- Backtrack to an earlier state and try another direction.
- Random-restart hill climbing: start again from other states and keep the best result; restarting at B reaches G in one move.
- Allow a limited number of sideways moves, or make a big jump, to leave a plateau.
- Stochastic hill climbing and simulated annealing sometimes accept worse moves to escape local optima.
In conclusion, hill climbing is fast and needs very little memory, but it is neither complete nor optimal.
3 Explain the A* search algorithm. Trace it on a weighted graph with heuristic values, and state when A* is optimal. 10 marks
A* is a best-first search that ranks each node n by
f(n) = g(n) + h(n)
where g(n) is the cost of the path from the start to n and h(n) is the heuristic estimate of the cheapest cost from n to the goal, so f(n) estimates the cheapest solution cost through n.
Algorithm:
1. Put the start node in OPEN with g = 0; CLOSED is empty. 2. If OPEN is empty, fail. Otherwise move the node n with the smallest f from OPEN to CLOSED. 3. If n is the goal, return the path found by following parent links. 4. For each successor m, let g(m) = g(n) + cost(n, m). If m is new or this g is lower than its recorded g, record g, f and parent n, and put m in OPEN. Go to step 2.
Example. Find a path from S to G; edge labels are step costs and each node shows its h value.
The heuristic is admissible: the true costs to G are S 9, A 8, B 6, C 4 and D 2, and no h exceeds them.
Trace:
- Expand S (f = 7): A gets g = 1, f = 1 + 6 = 7; B gets g = 4, f = 4 + 4 = 8.
- Expand A (f = 7): B through A has g = 3 < 4, so B is updated to f = 3 + 4 = 7, parent A; C gets g = 6, f = 6 + 3 = 9.
- Expand B (f = 7): C through B has g = 5 < 6, so C is updated to f = 5 + 3 = 8, parent B; D gets g = 8, f = 8 + 2 = 10.
- Expand C (f = 8): G gets g = 9, f = 9 + 0 = 9.
- OPEN holds G (9) and D (10). Expand G (f = 9): goal reached.
Expansion order: S, A, B, C, G. Path S → A → B → C → G with cost 1 + 2 + 2 + 4 = 9, the cheapest path.
Properties:
- Complete when b is finite and every step cost exceeds some small positive constant.
- Optimal when h is admissible, h(n) ≤ h*(n). A graph search that never reopens CLOSED nodes also needs h to be consistent, h(n) ≤ cost(n, m) + h(m) for every edge, as the h here is.
- Main drawback: it keeps every generated node in memory.
In conclusion, A* with an admissible heuristic finds the cheapest path while expanding far fewer nodes than blind search.
4 What is problem reduction? Explain AND-OR graphs and the AO* algorithm with an example. 10 marks
Problem reduction decomposes a problem into subproblems, solves each one and combines their solutions. Such a decomposition is drawn as an AND-OR graph:
- OR branches are alternatives; solving any one of them solves the node.
- An AND arc joins branches that must all be solved; it is drawn as an arc across them.
- A solution is a subgraph from the root to terminal (directly solvable) nodes, not a path.
A* cannot handle AND arcs, whose cost depends on all their children, so AO* is used.
AO* algorithm (every arc costs 1 here):
1. Start with the root and estimate its h. 2. Follow the marked arcs from the root and pick an unexpanded node of this best partial solution. 3. Expand it, estimating h for each new successor; terminal successors are SOLVED with h = 0, and a non-terminal node with no successors is unsolvable (FUTILITY). 4. Revise costs back to the root: an arc costs the sum over its children of (1 + h(child)); a node's h is its cheapest arc cost, and that arc is marked; a node is SOLVED when all children under its marked arc are SOLVED. 5. Stop when the root is SOLVED or its cost exceeds FUTILITY; otherwise go to step 2.
Example. C and D are joined by an AND arc, as are G and H; G, H and I are terminal. The estimates are h(B) = 2, h(C) = 1, h(D) = 1, h(E) = 4, h(F) = 5 and h(J) = 1.
- Expand A: via B, 1 + 2 = 3; via the AND arc (C, D), (1 + 1) + (1 + 1) = 4. Mark B; h(A) = 3.
- Expand B: E gives 1 + 4 = 5 and F gives 1 + 5 = 6, so h(B) = 5. Revise A: via B = 6, via C and D = 4, so the mark switches to C and D.
- Expand C (taken before D): its AND arc to G and H costs 1 + 1 = 2, so h(C) = 2 and C is SOLVED. Revise A: (1 + 2) + (1 + 1) = 5, still below 6.
- Expand D: I costs 1 and J costs 1 + 1 = 2, so h(D) = 1 through I, and D is SOLVED. Revise A: still 5, and with C and D both SOLVED, A is SOLVED.
The solution graph is A → (C and D), C → (G and H), D → I, with cost 5.
In conclusion, AO* expands only the best partial solution, revises costs backwards after each expansion, and switches arcs when an estimate rises, as A did.
5 Explain adversarial search and the minimax algorithm with an example game tree. How are optimal decisions made in multiplayer games? 10 marks
Games are adversarial search problems: agents with conflicting goals act in the same environment, so each must plan for the opponent's replies. In a two-player zero-sum game of perfect information, such as chess or tic-tac-toe, the players are MAX, who moves first, and MIN. The initial state, PLAYER(s), ACTIONS(s), RESULT(s, a), TERMINAL-TEST(s) and UTILITY(s, p) define a game tree whose levels alternate between MAX and MIN.
Minimax algorithm. The minimax value of a node is the utility, for MAX, of the terminal state reached when both players play optimally:
MINIMAX(s) = UTILITY(s) if s is terminal MINIMAX(s) = max over actions a of MINIMAX(RESULT(s, a)) if MAX is to move MINIMAX(s) = min over actions a of MINIMAX(RESULT(s, a)) if MIN is to move
Steps:
1. Generate the game tree down to the terminal states and apply the utility function to each. 2. Back up values level by level: a MIN node takes the minimum of its children, a MAX node the maximum. 3. At the root, MAX chooses the move to the child with the highest value.
Example. MAX at root R can move to the MIN nodes B, C and D, whose terminal children carry the utilities shown.
- B = min(3, 8) = 3
- C = min(9, 1) = 1
- D = min(6, 5) = 5
- R = max(3, 1, 5) = 5
So MAX's best move is to D, which guarantees at least 5. The largest leaf, 9, lies under C, but MAX cannot reach it, because MIN would answer with 1.
Properties: minimax is a depth-first search; it is complete if the tree is finite and optimal against an optimal opponent. It takes O(b^m) time and O(bm) space, so it cannot search a full game such as chess.
Optimal decisions in multiplayer games. With three or more players each node holds a vector of utilities, one per player, and the player to move picks the child whose vector is best in its own component. For players P1, P2 and P3, with vectors written (P1, P2, P3):
- At node n, P3 chooses between (3, 5, 2) and (6, 1, 4) and picks (6, 1, 4), since 4 > 2.
- At node m, P3 chooses between (2, 7, 5) and (4, 3, 1) and picks (2, 7, 5), since 5 > 1.
- At their parent, P2 chooses between (6, 1, 4) and (2, 7, 5) and picks (2, 7, 5), since 7 > 1.
Multiplayer games can also lead to alliances, which players form and break as their interests change.
In conclusion, minimax gives the optimal move under perfect play, and backing up utility vectors extends it to multiplayer games.
6 Explain alpha-beta pruning with an example. What is an evaluation function, and how is it used when the search must be cut off? 10 marks
Minimax examines every node, which is impossible for real games. Alpha-beta pruning returns the same move but skips branches that cannot affect the decision, using two bounds passed down the tree:
- α (alpha): the best value found so far for MAX on the path; it starts at −∞.
- β (beta): the lowest value found so far for MIN on the path; it starts at +∞.
1. At a MAX node, set α = max(α, child value). If the node's value reaches β or more, prune its remaining children (beta cut-off), since MIN above will avoid this node. 2. At a MIN node, set β = min(β, child value). If the node's value falls to α or less, prune its remaining children (alpha cut-off), as MAX above has a better choice.
Example. R is MAX, A and B are MIN, and C, D and E are MAX, with leaves C: 3, 5; D: 6, 9; E: 1, 2; B's second child is a terminal leaf 7. Search goes depth-first, left to right.
- C (α = −∞, β = +∞) sees 3 and 5, so C = 5, and A sets β = 5.
- D (α = −∞, β = 5) sees 6; since 6 ≥ β, leaf 9 is pruned and D ≥ 6. A = min(5, 6) = 5.
- R sets α = 5. E (α = 5, β = +∞) sees 1 and 2, so E = 2.
- At B, 2 ≤ α = 5, so leaf 7 is pruned and B ≤ 2.
- R = max(5, 2) = 5; the best move is to A.
Only 5 of the 7 leaves were examined, yet the root gets its minimax value. With perfect move ordering, alpha-beta examines about O(b^(m/2)) nodes instead of O(b^m), so it can search about twice as deep.
Evaluation functions. Real games are too deep to search fully, so search stops at a depth limit and each position there gets an estimate EVAL(s) instead of its true utility, often a weighted linear function:
EVAL(s) = w1 f1(s) + w2 f2(s) + ... + wn fn(s)
where each fi is a feature and wi its weight. In chess, f1 can be material balance, with pawn = 1, knight = bishop = 3, rook = 5 and queen = 9; other features measure king safety or pawn structure. A good evaluation function orders terminal states as the true utility does, is quick to compute and reflects the chance of winning. A fixed depth limit can cause the horizon effect, which quiescence search reduces.
In conclusion, alpha-beta pruning and a good evaluation function let a program search deeper within its time limit.
Knowledge Representation and Uncertainty
Syllabus: Knowledge representation issues; Predicate logic and logic programming; Semantic nets; Frames and inheritance; Constraint propagation; Representing knowledge using rules; Rule-based deduction systems; Reasoning under uncertainty and a review of probability; Bayesian probabilistic inference; Dempster-Shafer theory
One-page revision summary
- A knowledge representation maps facts about the world into symbols, and a program reasons on those symbols, so the choice of representation decides what can be inferred and how fast.
- Issues in knowledge representation include which attributes, such as isa and instance, are basic, how attributes relate (inverses, single-valued attributes, inheritance), what granularity to use, how to represent sets of objects, and how to choose the right structure.
- The frame problem is the difficulty of stating efficiently which facts stay unchanged when an action changes the world.
- Predicate logic uses predicates, variables and the quantifiers ∀ and ∃; resolution proves a goal by adding its negation to the clauses and deriving the empty clause.
- Unification finds a substitution that makes two literals identical, for example {x/ravi} for passes(x, ai) and passes(ravi, ai).
- Prolog answers a query by depth-first, left-to-right backward chaining over Horn clauses and treats a goal it cannot prove as false (the closed world assumption, which its negation as failure relies on).
- A semantic net stores knowledge as nodes joined by labelled arcs; isa and instance arcs give property inheritance, and partitioned nets show the scope of quantifiers.
- A frame groups slots and fillers for one object; facets such as default, if-needed and if-added add default values and attached procedures, inherited down isa links.
- Constraint propagation removes values that break a constraint; when it stalls, a value is guessed, propagated, and withdrawn by backtracking if a contradiction appears.
- A rule can be read declaratively, as a statement of what is true, or procedurally, where control knowledge such as rule order decides how it is applied.
- A rule-based deduction (production) system has a rule base, a working memory of facts and an inference engine that repeats a match, conflict resolution and act cycle.
- Conflict resolution chooses one rule when several match, for example by rule order, by specificity (more conditions) or by the recency of the matched facts.
- Forward chaining is data-driven and derives every consequence of the facts; backward chaining is goal-driven and uses only the rules relevant to the question.
- Uncertainty comes from incomplete knowledge, noisy sensors, rules with exceptions and the cost of listing every condition, so systems need degrees of belief instead of only true or false.
- Non-monotonic reasoning draws default conclusions and withdraws them when new facts contradict them, unlike classical logic, where adding facts never removes a conclusion.
- Bayes' theorem turns the causal probability P(evidence | cause) into the diagnostic probability P(cause | evidence), and the posterior from one piece of evidence becomes the prior for the next.
- A Bayesian network is a directed acyclic graph whose nodes store P(node | parents), so the joint distribution needs far fewer numbers than a full table.
- In Dempster–Shafer theory, mass on Θ stands for ignorance, and dividing by 1 − K removes the mass that fell on empty intersections; K near 1 signals strongly conflicting evidence.
Learn these by heart
- Good representation: representational adequacy, inferential adequacy, inferential efficiency, acquisitional efficiency.
- Horn clause: a disjunction of literals with at most one positive literal; p ∧ q → r is written r :- p, q in Prolog.
- Arc X → Y is consistent when every value of X has some value of Y that satisfies the constraint.
- Bayes' theorem: P(H | E) = P(E | H) · P(H) / P(E), with P(E) = P(E | H) · P(H) + P(E | ¬H) · P(¬H).
- Bayesian network: P(X1, ..., Xn) = product of P(Xi | Parents(Xi)) over all nodes.
- Bel(A) = Σ m(X) for X ⊆ A; Pl(A) = Σ m(X) for X ∩ A ≠ ∅ = 1 − Bel(¬A); Bel(A) ≤ Pl(A).
- Dempster's rule: m12(A) = Σ m1(X) · m2(Y) over X ∩ Y = A, divided by 1 − K, where K = Σ m1(X) · m2(Y) over X ∩ Y = ∅.
2-mark questions
1 What four properties should a good knowledge representation system have? 2 marks
A good knowledge representation system should have:
- Representational adequacy: it can represent all the knowledge the domain needs.
- Inferential adequacy: its structures can be manipulated to derive new knowledge from old.
- Inferential efficiency: it can store extra guidance that steers inference towards the most promising paths.
- Acquisitional efficiency: new knowledge can be added easily, ideally automatically.
2 What is a Horn clause? Why does Prolog use Horn clauses? 2 marks
A Horn clause is a disjunction of literals with at most one positive literal, such as ¬p ∨ ¬q ∨ r, which means p ∧ q → r and is written in Prolog as r :- p, q. Prolog uses Horn clauses because resolution can work backwards from the goal, one subgoal at a time, which is simple and efficient.
3 Distinguish between declarative and procedural representation of knowledge. 2 marks
A declarative representation states knowledge as facts and rules that say what is true, and a separate, general inference procedure decides how to use them. A procedural representation embeds knowledge in procedures that say how to use it, so control information, such as the order in which goals and rules are tried, is part of the knowledge itself.
4 What is arc consistency? Make the constraint X < Y arc consistent when X and Y both have the domain {1, 2, 3}. 2 marks
An arc X → Y is consistent if every value in the domain of X has at least one value in the domain of Y that satisfies the constraint. For X < Y, X = 3 has no larger Y, so it is removed: D(X) = {1, 2}. Checking Y → X removes Y = 1: D(Y) = {2, 3}.
5 Define prior and posterior probability. How does Bayes' rule connect them? 2 marks
The prior probability P(H) is the degree of belief in a hypothesis H before any evidence is seen. The posterior probability P(H | E) is the belief after evidence E has been observed. Bayes' rule turns one into the other: P(H | E) = P(E | H) · P(H) / P(E), where P(E | H) is the likelihood.
6 Define belief and plausibility in Dempster–Shafer theory. On Θ = {a, b, c} with m({a}) = 0.5, m({a, b}) = 0.3 and m(Θ) = 0.2, find Bel({b}) and Pl({b}). 2 marks
Belief Bel(A) is the total mass of all subsets of A; plausibility Pl(A) is the total mass of all sets that intersect A, so Pl(A) = 1 − Bel(¬A). No focal element lies inside {b}, so Bel({b}) = 0, and Pl({b}) = m({a, b}) + m(Θ) = 0.3 + 0.2 = 0.5. The belief interval of {b} is [0, 0.5].
10-mark questions
1 What is a semantic network? Explain with an example how a semantic net represents knowledge, how inheritance is used to answer questions, and how a relation with more than two arguments is represented. 10 marks
A semantic network (semantic net) represents knowledge as a labelled directed graph. Nodes stand for objects, classes or values, and each labelled arc stands for a relation between two nodes. A program answers questions by following arcs from node to node.
1. Nodes and arcs: every arc is a binary predicate. In the example net, the arc colour from Parrot to Green means colour(Parrot, Green), and the arc owner from Mithu to Ravi means owner(Mithu, Ravi).
2. Two special links: isa joins a class to a more general class, as in isa(Bird, Animal), isa(Parrot, Bird) and isa(Penguin, Bird). instance joins an individual to its class, as in instance(Mithu, Parrot). Other arcs carry properties: Animal breathes Air, Bird has Feathers, Bird moves by Flying, and Penguin moves by Swimming.
3. Property inheritance: a question is answered by searching the graph. To answer "Does Mithu have feathers?", start at Mithu, find no has arc there, follow instance to Parrot and isa to Bird, and find has Feathers, so the answer is yes. In the same way Mithu breathes Air (from Animal) and moves by Flying (from Bird).
4. Exceptions: a value stored at a lower node overrides the inherited default. Penguin has its own moves by arc to Swimming, so the search for how a penguin moves stops at Penguin and never reaches Flying at Bird. The rule is to search upward from the most specific node and use the first value found.
5. Relations with more than two arguments: arcs are binary, so a predicate such as gave(Ravi, Sita, Book) becomes a node G1 for the event itself, with arcs instance(G1, Giving), agent(G1, Ravi), recipient(G1, Sita) and object(G1, Book). Any number of arguments can be attached this way.
6. Quantifiers: a statement such as "every student reads some book" cannot be shown by plain arcs. Partitioned semantic nets group arcs into spaces to show the scope of each quantifier.
Advantages: the net is easy to read, related facts sit next to each other, and inheritance saves storage because a property is stored once, at the most general class it applies to. Limitations: link names have no fixed meaning, so programs may read them differently, and negation, disjunction and quantifiers are hard to express.
In conclusion, a semantic net is a graph of objects and relations whose isa and instance links let a program infer properties by inheritance, with exceptions handled by the most specific value.
2 What is a frame? Explain slots, fillers, default values and procedural attachments, and describe how inheritance works in a frame hierarchy, including the problem of multiple inheritance. 10 marks
A frame is a structured record that collects what is known about one stereotyped object, class or situation. The idea was proposed by Marvin Minsky. A frame has a name and a set of slots (attributes), and each slot holds a filler (value). Frames are linked into a hierarchy by isa and instance slots, much like classes and objects in object-oriented programming.
1. Slots and fillers: a filler can be a number, a symbol or another frame, so frames point to one another.
2. Facets of a slot: a slot can carry more than a value.
- value: the actual filler;
- default: the value assumed when nothing better is known;
- type or range: the kind of value allowed, for example age must be a number;
- if-needed: a procedure run to compute the value when it is asked for;
- if-added: a procedure run when a value is stored, for example to update related frames.
The last two are procedural attachments, which add procedural knowledge to a declarative structure.
3. Example hierarchy:
Frame: Person
legs: default 2
can-vote: if-needed (yes when age >= 18)
Frame: Student
isa: Person
age: default 20
income: default none
Frame: Employee
isa: Person
income: default salary
Frame: Ravi
instance: Student, Employee
age: 234. Inheritance: to find a slot value for Ravi, look in Ravi's own frame first; if the slot is missing, follow the instance and isa links upward and use the first value found.
- legs(Ravi) = 2, inherited from Person through either parent.
- age(Ravi) = 23: Ravi's own value overrides the default 20 from Student. A default holds only until a more specific value is known.
- can-vote(Ravi): the if-needed procedure inherited from Person runs with age 23 and returns yes.
5. Multiple inheritance: Ravi is both a Student and an Employee, so the search for income finds none through Student and salary through Employee. The usual rule, prefer the value from the class that lies below the other, cannot decide, because neither class lies below the other. The system must then use a stated priority order of parents, ask the user, or report the conflict, instead of picking a value at random.
Advantages: all facts about an object are kept together, defaults allow reasoning with incomplete information, and inheritance saves storage. Limitations: defaults can be wrong for exceptional cases, and multiple inheritance needs extra rules for conflicts.
In conclusion, a frame is a node with internal structure: slots, facets and attached procedures, with inheritance down the isa hierarchy supplying default values.
3 What is constraint propagation? Solve the cryptarithmetic problem SEND + MORE = MONEY by constraint propagation, showing how the value of each letter is deduced. 10 marks
Constraint propagation solves a constraint satisfaction problem (variables, domains and constraints) by using the constraints to remove impossible values and derive new constraints before any guess; each deduction can trigger others. If it stalls, a value is guessed and propagated, and the search backtracks on a contradiction.
Problem: each letter is a different digit, S and M are not 0, and
S E N D
+ M O R E
---------
M O N E YLet c1, c2, c3 and c4 be the carries out of the units, tens, hundreds and thousands columns; the column constraints are:
- units: D + E = Y + 10·c1
- tens: N + R + c1 = E + 10·c2
- hundreds: E + O + c2 = N + 10·c3
- thousands: S + M + c3 = O + 10·c4, and M = c4
Propagation steps:
1. Two four-digit numbers add up to at most 19998, so c4 ≤ 1; as M = c4 and M is not 0, M = 1.
2. Thousands column: S + 1 + c3 = O + 10, so S = 9, or S = 8 with c3 = 1, and O is 0 or 1. M = 1 already, so O = 0.
3. Hundreds column: E + c2 = N + 10·c3. If c3 = 1, N could only be 0, which O uses; so c3 = 0 and E + c2 = N. Since E ≠ N, c2 = 1 and N = E + 1. The thousands column with c3 = 0 now gives S = 9.
4. Tens column: N + R + c1 = E + 10 with N = E + 1 gives R = 9 − c1. S uses 9, so c1 = 1 and R = 8.
5. Units column: D + E = Y + 10. The free digits are 2 to 7, so Y ≥ 2 and D + E ≥ 12. As D ≤ 7, E ≥ 5, and N = E + 1 must also be free. E = 7 makes N = 8, used by R; E = 6 makes N = 7 and leaves no D; so E = 5, N = 6, D = 7 and Y = 2.
Result: S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2, that is 9567 + 1085 = 10652.
Here propagation alone fixes every letter with no guessing. In harder problems it narrows the domains so that a few guesses with backtracking finish the job.
4 How is knowledge represented as rules in logic programming? Write a small Prolog program, show how a query is answered by backward chaining, and compare backward chaining with forward chaining. 10 marks
In logic programming, knowledge is written as facts and rules in a restricted form of predicate logic, and the program is run by asking it questions. Prolog is the best-known logic programming language.
1. From predicate logic to rules. Sita and Ravi study AI, Ravi is hardworking and Rao teaches AI. Two rules:
- ∀s ∀c (studies(s, c) ∧ hardworking(s) → passes(s, c))
- ∀t ∀s ∀c (teaches(t, c) ∧ passes(s, c) → proud(t, s))
In clause form the first rule is ¬studies(s, c) ∨ ¬hardworking(s) ∨ passes(s, c). It has exactly one positive literal, so it is a Horn clause, and Prolog writes it with the conclusion (head) on the left.
2. The Prolog program:
studies(sita, ai).
studies(ravi, ai).
hardworking(ravi).
teaches(rao, ai).
passes(S, C) :- studies(S, C), hardworking(S).
proud(T, S) :- teaches(T, C), passes(S, C).Here :- is read "if", the comma is read "and", and variables begin with a capital letter.
3. Backward chaining on the query ?- proud(rao, Who).
- proud(rao, Who) matches the head of the proud rule with T = rao and S = Who, giving the subgoals teaches(rao, C) and passes(Who, C).
- teaches(rao, C) matches a fact, so C = ai.
- passes(Who, ai) matches the passes rule, giving studies(Who, ai) and hardworking(Who).
- studies(Who, ai) first matches studies(sita, ai), so Who = sita; hardworking(sita) cannot be proved, so this branch fails and Prolog backtracks.
- The next fact gives Who = ravi, and hardworking(ravi) is a fact, so every subgoal succeeds.
Answer: Who = ravi. Prolog searches depth first, tries subgoals left to right and clauses top to bottom, and treats a goal it cannot prove as false (the closed world assumption).
4. Forward chaining on the same rules starts from the facts. Cycle 1: studies(ravi, ai) and hardworking(ravi) fire the passes rule, adding passes(ravi, ai). Cycle 2: teaches(rao, ai) and passes(ravi, ai) fire the proud rule, adding proud(rao, ravi). No rule adds anything new, so it stops.
5. Comparison in rule-based deduction systems:
- Backward chaining is goal-driven: it starts from the question and uses only relevant rules. It suits diagnosis and question answering, as in Prolog and the MYCIN expert system.
- Forward chaining is data-driven: it starts from the facts and derives every consequence. It suits monitoring and configuration, where new data keeps arriving.
- Reason forward when there are few facts and many possible goals, and backward when one specific goal is asked.
In conclusion, rules written as Horn clauses are both declarative, stating what is true, and procedural, because Prolog's fixed search order decides how they are used.
5 State Bayes' theorem and explain its use in probabilistic inference. A computer has a virus with probability 0.1. With a virus it runs slow with probability 0.8 and shows pop-ups with probability 0.6; without one these are 0.2 and 0.05. Taking the two symptoms as independent given the virus state, find the probability of a virus when the computer is slow, and when it is slow and shows pop-ups. 10 marks
Reasoning under uncertainty is needed because knowledge is incomplete, sensors are noisy and rules have exceptions; probability measures belief by a number from 0 to 1.
1. Review of probability:
- Axioms: 0 ≤ P(A) ≤ 1, P(true) = 1, and P(A ∨ B) = P(A) + P(B) − P(A ∧ B).
- Conditional probability: P(A | B) = P(A ∧ B) / P(B), when P(B) > 0.
- Product rule: P(A ∧ B) = P(A | B) · P(B) = P(B | A) · P(A).
- Total probability: P(E) = P(E | H) · P(H) + P(E | ¬H) · P(¬H).
2. Bayes' theorem follows from the two forms of the product rule:
P(H | E) = P(E | H) · P(H) / P(E)
P(H) is the prior, P(E | H) the likelihood and P(H | E) the posterior. In AI it is used for diagnosis: the causal probability P(symptom | fault) is easy to estimate, and Bayes' theorem turns it into the diagnostic probability P(fault | symptom).
3. Worked example. Let V = virus, S = slow and P = pop-ups.
P(V) = 0.1, P(¬V) = 0.9 P(S | V) = 0.8, P(S | ¬V) = 0.2 P(P | V) = 0.6, P(P | ¬V) = 0.05
(a) Computer is slow:
P(S) = 0.8 × 0.1 + 0.2 × 0.9 = 0.08 + 0.18 = 0.26 P(V | S) = 0.08 / 0.26 = 0.3077
(b) Slow and pop-ups. Since S and P are independent given V:
P(S ∧ P | V) · P(V) = 0.8 × 0.6 × 0.1 = 0.048 P(S ∧ P | ¬V) · P(¬V) = 0.2 × 0.05 × 0.9 = 0.009 P(V | S ∧ P) = 0.048 / (0.048 + 0.009) = 0.048 / 0.057 = 0.8421
Updating one symptom at a time agrees: the posterior P(V | S) = 4/13 becomes the new prior, and (4/13 × 0.6) / (4/13 × 0.6 + 9/13 × 0.05) = 2.4 / 2.85 = 0.8421.
4. Bayesian networks: a full joint distribution over n Boolean variables needs 2^n − 1 numbers. A Bayesian network is a directed acyclic graph in which each node stores P(node | parents), and the joint probability is the product of these terms. For this example, P(V, S, P) = P(V) · P(S | V) · P(P | V), which needs 1 + 2 + 2 = 5 numbers instead of 7.
In conclusion, Bayes' theorem turns causal knowledge into diagnostic conclusions: here one symptom raises the virus probability from 0.1 to about 0.31 and both raise it to about 0.84. The answers are only as sound as the priors and the independence assumption.
6 Explain the Dempster–Shafer theory of evidence: frame of discernment, basic probability assignment, belief, plausibility and Dempster's rule of combination. Illustrate by combining three pieces of evidence about why a car will not start. 10 marks
Bayesian probability must give every hypothesis a probability, and belief not given to H goes to ¬H. Dempster–Shafer (D-S) theory gives belief to sets of hypotheses, so ignorance is shown openly.
1. Frame of discernment Θ: the set of mutually exclusive, exhaustive hypotheses. Here Θ = {B, F, S}: flat battery, empty fuel tank, faulty starter motor.
2. Basic probability assignment (mass function) m: gives each subset A of Θ a mass m(A) from 0 to 1, with m(∅) = 0 and all masses adding to 1. Sets with m(A) > 0 are focal elements; mass on Θ means "don't know".
3. Belief and plausibility:
- Bel(A) = Σ m(X) over all X ⊆ A: evidence that fully supports A.
- Pl(A) = Σ m(X) over all X with X ∩ A ≠ ∅ = 1 − Bel(¬A).
- Bel(A) ≤ Pl(A), and the width of the belief interval [Bel(A), Pl(A)] shows ignorance.
4. Dempster's rule for two independent sources: m12(A) = Σ m1(X) · m2(Y) over X ∩ Y = A, divided by 1 − K, where the conflict K = Σ m1(X) · m2(Y) over X ∩ Y = ∅.
5. Example:
- Clicking sound: m1({B, S}) = 0.7, m1(Θ) = 0.3.
- Dim headlights: m2({B}) = 0.6, m2(Θ) = 0.4.
- Fuel gauge near empty: m3({F}) = 0.5, m3(Θ) = 0.5.
Combining m1 and m2: no intersection is empty, so K = 0, and m12({B}) = 0.7 × 0.6 + 0.3 × 0.6 = 0.60, m12({B, S}) = 0.7 × 0.4 = 0.28, m12(Θ) = 0.3 × 0.4 = 0.12.
Combining m12 with m3:
- {B} ∩ {F} and {B, S} ∩ {F} are empty, so K = 0.60 × 0.5 + 0.28 × 0.5 = 0.30 + 0.14 = 0.44.
- The other products are {B}: 0.30, {B, S}: 0.14, {F}: 0.12 × 0.5 = 0.06 and Θ: 0.06.
- Dividing by 1 − K = 0.56: m({B}) = 0.536, m({B, S}) = 0.25, m({F}) = 0.107, m(Θ) = 0.107.
- Bel({B}) = 0.536, Pl({B}) = 0.536 + 0.25 + 0.107 = 0.893
- Bel({F}) = 0.107, Pl({F}) = 0.107 + 0.107 = 0.214
- Bel({S}) = 0, Pl({S}) = 0.25 + 0.107 = 0.357
In the figure, Bel of a set adds the masses at that set and at every set reached from it by following the lines downwards, that is, at its subsets. So the flat battery is best supported, with belief interval [0.536, 0.893].
Limitation: when K is near 1 the sources strongly disagree and the normalised result can mislead.
In conclusion, D-S theory puts mass on sets, keeps ignorance on Θ and combines evidence by Dempster's rule; if every focal element is a single hypothesis, Bel = Pl and it becomes ordinary probability.
First-Order Logic and Learning
Syllabus: First-order logic; Inference in first-order logic; Propositional versus first-order inference; Unification and lifting; Forward chaining; Backward chaining; Resolution; Learning from observation and inductive learning; Decision trees; Explanation-based learning; Statistical learning methods; Reinforcement learning
One-page revision summary
- First-order logic describes a world of objects, relations and functions using constants, variables, predicates, function symbols, connectives and the quantifiers ∀ and ∃.
- A model of first-order logic has a domain of objects and an interpretation that maps constants to objects, predicates to relations and function symbols to functions.
- Universal instantiation may replace a universally quantified variable by any ground term many times, while existential instantiation replaces an existentially quantified variable once by a new Skolem constant.
- Propositionalization turns a first-order KB into a propositional one, and by Herbrand's theorem every entailed sentence has a proof from a finite part of it.
- Entailment in first-order logic is semi-decidable: a procedure can confirm every entailed sentence, but none can always show that a sentence is not entailed.
- Unification finds the most general unifier θ with SUBST(θ, p) = SUBST(θ, q), and the occurs check stops a variable from unifying with a term that contains it.
- Generalized Modus Ponens lifts Modus Ponens to first-order logic, so inference works with variables instead of every ground instance.
- Forward chaining is data-driven: it fires every rule whose premises are known facts until the query is derived or no new fact appears.
- Forward chaining is complete for first-order definite clauses and always terminates for Datalog, which has no function symbols.
- Backward chaining is a goal-driven, depth-first search of an AND–OR proof tree, as in Prolog, and it is incomplete because it can loop forever.
- Resolution proves KB ⊨ α by refutation: add ¬α in clause form and derive the empty clause.
- Conversion to clause form eliminates implications, moves negation inwards, standardizes variables apart, Skolemizes, drops ∀ and distributes ∨ over ∧.
- Learning is supervised, unsupervised or reinforcement learning, depending on whether the feedback is the correct answer, nothing or a reward.
- Inductive learning looks for a hypothesis that agrees with the training examples and predicts new ones well, preferring the simplest such hypothesis.
- Decision-tree learning splits on the attribute with the highest information gain and prunes branches that only fit noise, to avoid overfitting.
- In explanation-based learning the proof of one example is generalized into a rule, so Background ⊨ Hypothesis and no new facts are learned.
- Bayesian learning weights every hypothesis by its posterior P(h | d) ∝ P(d | h) P(h); MAP learning uses only the most probable hypothesis, and maximum-likelihood learning assumes a uniform prior.
- A naive Bayes classifier assumes the attributes are conditionally independent given the class, and the EM algorithm learns parameters when some variables are hidden.
- Passive reinforcement learning evaluates a fixed policy, while active reinforcement learning must also choose actions and balance exploration with exploitation.
- Q-learning is model-free: it learns Q(s, a) directly from observed transitions and acts by choosing the action with the highest Q value.
Learn these by heart
- GMP: from p1′, …, pn′ and p1 ∧ … ∧ pn → q, where SUBST(θ, pi′) = SUBST(θ, pi) for every i, infer SUBST(θ, q).
- Resolution: from two clauses with literals li and ¬mj where UNIFY(li, mj) = θ, infer all the other literals of both clauses with θ applied.
- ¬∀x P ≡ ∃x ¬P and ¬∃x P ≡ ∀x ¬P; ∀ goes with →, and ∃ goes with ∧.
- Entropy: H(S) = −Σ pi log2 pi; two equal classes give H = 1 bit.
- Information gain: Gain(A) = H(S) − Σ (|Sv| / |S|) H(Sv), over the values v of A.
- EBL: Hypothesis ∧ Descriptions ⊨ Classifications and Background ⊨ Hypothesis.
- TD learning: U(s) ← U(s) + α (r + γ U(s′) − U(s)).
- Q-learning: Q(s, a) ← Q(s, a) + α [r + γ maxa′ Q(s′, a′) − Q(s, a)].
2-mark questions
1 State the rules of universal instantiation and existential instantiation, with an example of each. 2 marks
Universal instantiation (UI): from ∀v α infer SUBST({v/g}, α) for any ground term g; it can be applied many times. Example: from ∀x Student(x) → Learns(x) infer Student(Ravi) → Learns(Ravi).
Existential instantiation (EI): from ∃v α infer SUBST({v/k}, α), where k is a new constant (a Skolem constant); it is applied once. Example: ∃x Topper(x) gives Topper(K1).
2 What is unification? Find the most general unifier of Likes(x, Mother(x)) and Likes(Ravi, y). 2 marks
Unification finds a substitution θ that makes two atomic sentences identical: UNIFY(p, q) = θ, where SUBST(θ, p) = SUBST(θ, q).
Matching the first arguments gives x/Ravi. The second arguments then are Mother(Ravi) and y, giving y/Mother(Ravi). The most general unifier is θ = {x/Ravi, y/Mother(Ravi)}, and both sentences become Likes(Ravi, Mother(Ravi)).
3 What is Skolemization? Give an example of a Skolem constant and of a Skolem function. 2 marks
Skolemization removes existential quantifiers when sentences are converted to clause form. An existential variable outside every ∀ becomes a new constant: ∃x Topper(x) becomes Topper(T). One inside ∀x becomes a new function of x: ∀x Student(x) → ∃y Mentor(y, x) becomes ¬Student(x) ∨ Mentor(M(x), x). The result is satisfiable exactly when the original is.
4 What is inductive learning? State Ockham's razor. 2 marks
In inductive learning the agent is given examples (x, f(x)) of an unknown function f and must find a hypothesis h, from a hypothesis space H, that approximates f and also predicts new examples correctly. A hypothesis that agrees with all the examples is consistent.
Ockham's razor: prefer the simplest hypothesis that is consistent with the data.
5 What is explanation-based learning? Give a small example. 2 marks
Explanation-based learning (EBL) uses background knowledge to prove why one example belongs to a concept, then generalizes the proof into a rule. For example, a proof of Eligible(Ravi) through Student(x) ∧ Topper(x) → Eligible(x) and HighMarks(x, s) ∧ Core(s) → Topper(x) yields Student(x) ∧ HighMarks(x, s) ∧ Core(s) → Eligible(x). EBL speeds up reasoning but learns no new facts.
6 Out of 20 emails, 6 are spam. Using maximum-likelihood learning, estimate θ = P(spam). 2 marks
Treating the emails as independent, the likelihood is L(θ) = θ⁶(1 − θ)¹⁴, so the log-likelihood is 6 log θ + 14 log(1 − θ).
Setting its derivative to zero: 6/θ − 14/(1 − θ) = 0, so 6(1 − θ) = 14θ and θ = 6/20 = 0.3. The maximum-likelihood estimate is the observed fraction of spam.
10-mark questions
1 Explain the syntax and semantics of first-order logic. How do the quantifiers work? Translate some English sentences into first-order logic. 10 marks
First-order logic (FOL), or predicate logic, is more expressive than propositional logic. Propositional logic assumes that the world contains only facts, each true or false, whereas FOL assumes that it contains objects, relations among them and functions on them, so one sentence can speak about all objects or some objects.
Syntax
1. Constant symbols name objects: Ravi, Sita, AI.
2. Variables such as x and y stand for objects that are not named.
3. Predicate symbols name properties and relations: Student(x), Likes(x, y).
4. Function symbols map objects to an object: Father(Ravi) is Ravi's father.
5. A term is a constant, a variable or a function applied to terms; every term refers to an object.
6. An atomic sentence is a predicate applied to terms, such as Likes(Ravi, AI), or an equality t1 = t2 between terms.
7. A complex sentence joins sentences with the connectives ¬, ∧, ∨, → and ↔.
8. A quantified sentence uses ∀ (for all) or ∃ (there exists) with a variable.
Semantics
A model has a domain, a non-empty set of objects, and an interpretation that maps each constant to an object, each predicate to a relation and each function symbol to a function on the domain. An atomic sentence is true when the objects named by its terms are in the relation named by its predicate, and t1 = t2 is true when both terms refer to the same object. The connectives keep their propositional meaning.
Quantifiers
- ∀x P is true when P is true for every object in the domain. Its natural partner is →: ∀x Student(x) → Studies(x) speaks only of students, while ∀x Student(x) ∧ Studies(x) wrongly says that everything is a student.
- ∃x P is true when P is true for at least one object. Its natural partner is ∧: ∃x Student(x) ∧ Topper(x).
- Negation links the two: ¬∀x P ≡ ∃x ¬P and ¬∃x P ≡ ∀x ¬P.
- The order of different quantifiers matters: ∀x ∃y Mentor(y, x) says everyone has some mentor, while ∃y ∀x Mentor(y, x) says one person mentors everyone.
Translations
- Every CSE student likes programming: ∀x CSE(x) → Likes(x, Programming).
- Some student failed in Maths: ∃x Student(x) ∧ Failed(x, Maths).
- Nobody likes exams: ¬∃x Likes(x, Exams), which is the same as ∀x ¬Likes(x, Exams).
- Every student has a mentor: ∀x Student(x) → ∃y Mentor(y, x).
- Ravi's father is a teacher: Teacher(Father(Ravi)).
In conclusion, FOL builds sentences from terms, predicates, connectives and quantifiers, and its semantics fixes their truth in a model through a domain and an interpretation. This is the language used by the inference methods of this unit.
2 Explain inference in first-order logic: universal and existential instantiation, propositionalization, the comparison of propositional and first-order inference, and how unification and lifting give generalized Modus Ponens. 10 marks
Inference in first-order logic derives new sentences from a knowledge base (KB). There are two routes: reduce the KB to propositional logic and use propositional inference, or reason directly with variables through unification, which is called lifted inference.
1. Universal instantiation (UI). From ∀v α we may infer SUBST({v/g}, α) for any ground term g, as many times as needed. From ∀x Doctor(x) ∧ Licensed(x) → Prescribes(x) we get Doctor(Meena) ∧ Licensed(Meena) → Prescribes(Meena).
2. Existential instantiation (EI). From ∃v α we infer SUBST({v/k}, α), where k is a new constant called a Skolem constant: ∃x Surgeon(x) becomes Surgeon(S1). EI is applied once and the existential sentence is then discarded. The new KB is not logically equivalent to the old one, but it is satisfiable exactly when the old one is.
3. Propositionalization. Applying EI to each existential sentence and UI with every ground term turns the KB into a propositional KB, in which ground atoms such as Doctor(Meena) act as proposition symbols. Suppose the KB holds the rule above and the facts Doctor(Meena), Licensed(Meena) and Doctor(Kiran). The rule gives two instances, for Meena and Kiran, and propositional inference derives Prescribes(Meena).
4. Propositional versus first-order inference.
- Propositionalization is complete: by Herbrand's theorem, if a sentence is entailed by the first-order KB, it has a proof from a finite subset of the propositional KB.
- With function symbols there are infinitely many ground terms, such as Father(Ravi) and Father(Father(Ravi)), so instances are generated to depth 1, then 2, and so on. This finds a proof of every entailed sentence but may run forever on one that is not entailed: entailment in FOL is semi-decidable.
- It is wasteful: it builds every instance, even irrelevant ones such as the Kiran rule, and a rule with k variables and n constants has n^k instances.
- First-order inference instantiates only what a proof needs.
5. Unification and lifting. UNIFY(p, q) returns the most general unifier θ with SUBST(θ, p) = SUBST(θ, q); the occurs check makes x fail to unify with Father(x). Generalized Modus Ponens (GMP) is the lifted form of Modus Ponens: from atomic sentences p1′, …, pn′ and a rule p1 ∧ … ∧ pn → q, if SUBST(θ, pi′) = SUBST(θ, pi) for every i, infer SUBST(θ, q). Unifying Doctor(x) ∧ Licensed(x) with Doctor(Meena) and Licensed(Meena) gives θ = {x/Meena}, so Prescribes(Meena) follows in one step, and the Kiran instance is never built.
In conclusion, propositionalization shows that first-order inference can be reduced to propositional inference, while unification and GMP lift the inference rules to work directly with variables. Lifted inference is the basis of forward chaining, backward chaining and resolution.
3 Explain forward chaining and backward chaining for first-order definite clauses. Use both to prove Gets(Ravi, Scholarship) from R1: HighMarks(x, s) ∧ Core(s) → Topper(x); R2: Student(x) ∧ Topper(x) → Eligible(x); R3: Eligible(x) ∧ Applied(x) → Gets(x, Scholarship); R4: Topper(x) → Honoured(x); and the facts Student(Ravi), HighMarks(Ravi, DBMS), Core(DBMS), Applied(Ravi). Compare the two methods. 10 marks
A definite clause has exactly one positive literal: it is either a fact or a rule p1 ∧ … ∧ pn → q. Over such clauses, inference can run from the facts towards the goal (forward chaining) or from the goal back to the facts (backward chaining). Both use unification and Generalized Modus Ponens.
Forward chaining
1. Start with the known facts.
2. In each iteration, find every rule whose premises unify with known facts, and add its conclusion SUBST(θ, q) if it is new.
3. Stop when a new fact matches the query, or when no new fact can be added (a fixed point).
Trace:
- Iteration 1: R1 with θ = {x/Ravi, s/DBMS} adds Topper(Ravi).
- Iteration 2: R2 with {x/Ravi} adds Eligible(Ravi), and R4 adds Honoured(Ravi).
- Iteration 3: R3 with {x/Ravi} adds Gets(Ravi, Scholarship), which matches the query, so it is proved.
Honoured(Ravi) was not needed: forward chaining also derives facts that have nothing to do with the goal.
Backward chaining
1. Take the goal and find a fact that unifies with it, or a rule whose conclusion unifies with it.
2. For a rule, its premises with θ applied become subgoals, and all of them must be proved (an AND node); choosing among rules is an OR choice.
3. Prove the subgoals depth-first, left to right, carrying the substitution along, until every subgoal ends in a fact.
Trace:
- Gets(Ravi, Scholarship) unifies with the conclusion of R3, θ = {x/Ravi}: subgoals Eligible(Ravi) and Applied(Ravi).
- Eligible(Ravi) by R2: subgoals Student(Ravi), a fact, and Topper(Ravi).
- Topper(Ravi) by R1: HighMarks(Ravi, s) unifies with a fact, giving s/DBMS, and Core(DBMS) is a fact.
- Applied(Ravi) is a fact, so the goal is proved. R4 is never used.
Comparison
- Forward chaining is data-driven; backward chaining is goal-driven.
- Forward chaining may derive many irrelevant facts; backward chaining looks only at rules relevant to the goal.
- Forward chaining is complete for definite clauses and always terminates when there are no function symbols (Datalog). Depth-first backward chaining can loop forever, so it is incomplete, but it needs space only linear in the proof size.
- Backward chaining is the basis of Prolog; forward chaining suits production systems and deductive databases.
In conclusion, both methods reach the same answer here, but backward chaining did less work because the query was known in advance.
4 Explain resolution in first-order logic, including conversion to clause form. Use resolution to prove that Asha is happy, given: every CSE student who attends classes studies AI; everyone who studies AI knows logic; everyone who knows logic solves some puzzle; anyone who solves a puzzle is happy; Asha is a CSE student; Asha attends classes. 10 marks
Resolution, together with factoring (merging two literals of a clause that unify into one), is refutation-complete for first-order logic. To prove KB ⊨ α, we add ¬α to the KB, convert everything to clause form and derive the empty clause, a contradiction. The rule: from two clauses containing literals li and ¬mj with UNIFY(li, mj) = θ, infer the clause made of all the other literals of both, with θ applied.
Conversion to clause form (CNF)
1. Eliminate implications: α → β becomes ¬α ∨ β.
2. Move ¬ inwards: ¬(α ∧ β) ≡ ¬α ∨ ¬β, ¬∃x P ≡ ∀x ¬P, ¬∀x P ≡ ∃x ¬P.
3. Standardize variables apart, so each quantifier has its own variable.
4. Skolemize: replace each existential variable by a Skolem constant, or by a Skolem function of the universal variables around it.
5. Drop the universal quantifiers.
6. Distribute ∨ over ∧ and split conjunctions into separate clauses.
Worked example. In FOL: (1) ∀x CSE(x) ∧ Attends(x) → Studies(x, AI); (2) ∀x Studies(x, AI) → Knows(x, Logic); (3) ∀x Knows(x, Logic) → ∃y Solves(x, y); (4) ∀x (∃y Solves(x, y)) → Happy(x); (5) CSE(Asha); (6) Attends(Asha). Here Solves(x, y) means x solves puzzle y. Goal: Happy(Asha).
Sentence 3 becomes ∀x ¬Knows(x, Logic) ∨ ∃y Solves(x, y); y lies inside ∀x, so it is replaced by the Skolem function F(x). Sentence 4 becomes ∀x ¬(∃y Solves(x, y)) ∨ Happy(x), then ∀x ∀y ¬Solves(x, y) ∨ Happy(x). After standardizing apart:
- C1: ¬CSE(x1) ∨ ¬Attends(x1) ∨ Studies(x1, AI)
- C2: ¬Studies(x2, AI) ∨ Knows(x2, Logic)
- C3: ¬Knows(x3, Logic) ∨ Solves(x3, F(x3))
- C4: ¬Solves(x4, y4) ∨ Happy(x4)
- C5: CSE(Asha)
- C6: Attends(Asha)
- C7: ¬Happy(Asha), the negated goal
Resolution steps:
- R1 = C7 + C4, θ = {x4/Asha}: ¬Solves(Asha, y4)
- R2 = R1 + C3, θ = {x3/Asha, y4/F(Asha)}: ¬Knows(Asha, Logic)
- R3 = R2 + C2, θ = {x2/Asha}: ¬Studies(Asha, AI)
- R4 = R3 + C1, θ = {x1/Asha}: ¬CSE(Asha) ∨ ¬Attends(Asha)
- R5 = R4 + C5: ¬Attends(Asha)
- R6 = R5 + C6: the empty clause □
The empty clause shows that KB ∧ ¬Happy(Asha) is unsatisfiable, so KB ⊨ Happy(Asha): Asha is happy. Every step used the negated goal or a clause derived from it, which is the set-of-support strategy; it keeps the search focused on the goal.
In conclusion, resolution with unification gives a sound and refutation-complete proof method for first-order logic once the sentences are in clause form.
5 Explain learning from observations, inductive learning and the decision-tree learning algorithm with entropy and information gain. Build a decision tree for Placed from these examples (CGPA, Internship, Communication → Placed): 1 High, Yes, Good → Yes; 2 High, No, Average → Yes; 3 High, Yes, Average → Yes; 4 Medium, Yes, Good → Yes; 5 Medium, No, Good → No; 6 Medium, Yes, Average → Yes; 7 Medium, No, Average → No; 8 Low, Yes, Good → No; 9 Low, No, Average → No; 10 Low, No, Good → No. 10 marks
Learning from observations means that an agent improves its behaviour from its percepts and experience instead of being programmed for every case. With labelled examples it is supervised learning, without labels it is unsupervised learning, and with rewards it is reinforcement learning. Inductive learning is supervised: from examples (x, f(x)) the agent finds a hypothesis h that approximates f and predicts new cases, preferring the simplest consistent hypothesis (Ockham's razor).
A decision tree maps attribute values to a decision: each internal node tests an attribute, each branch is one value, and each leaf gives the class.
Decision-tree learning (ID3)
1. If all examples have the same class, return a leaf with that class.
2. If no attributes are left, return the majority class; if no examples are left, return the majority class of the parent.
3. Otherwise choose the attribute with the highest information gain, make it the node, and repeat for each value with the matching examples.
Entropy: H(S) = −p log2 p − q log2 q, where p and q are the fractions of Yes and No.
Gain(A) = H(S) − Σ (|Sv| / |S|) H(Sv), summed over the values v of A.
Worked example. There are 5 Yes and 5 No, so H(S) = 1.
- CGPA: High (3 Yes, 0 No) H = 0; Medium (2 Yes, 2 No) H = 1; Low (0 Yes, 3 No) H = 0. Remainder = (4/10)(1) = 0.4, so Gain = 0.6.
- Internship: Yes (4 Yes, 1 No) and No (1 Yes, 4 No), each H = −0.8 log2 0.8 − 0.2 log2 0.2 = 0.722. Gain = 1 − 0.722 = 0.278.
- Communication: Good (2 Yes, 3 No) and Average (3 Yes, 2 No), each H = 0.971. Gain = 1 − 0.971 = 0.029.
CGPA has the highest gain, so it is the root. High and Low are pure, so they become leaves. For Medium (examples 4 to 7, H = 1), Internship gives Yes (2 Yes) and No (2 No), so its gain is 1, while Communication gives one Yes and one No on each branch, so its gain is 0. Internship is therefore tested under Medium.
The tree reads: if CGPA is High, Placed = Yes; if Low, Placed = No; if Medium, Placed = Yes exactly when the student has an internship. Communication is never tested because it carries almost no information about the class.
In conclusion, ID3 grows the tree greedily by information gain and gives a small tree consistent with the data. Real data has noise, so trees are pruned to avoid overfitting.
6 What is reinforcement learning? Explain passive and active reinforcement learning, temporal-difference learning and Q-learning, and work out one Q-learning update. 10 marks
In reinforcement learning (RL) an agent learns how to act from rewards and punishments that it receives while acting, without being told the correct action in each state. The environment is usually a Markov decision process with states, actions, a transition model and rewards, and the agent looks for a policy π, a mapping from states to actions, that maximizes the expected sum of discounted rewards.
1. Elements: agent, environment, state s, action a, reward r, policy π, the utility U(s) (expected discounted reward from s) and the discount factor γ, with 0 ≤ γ ≤ 1.
2. Passive reinforcement learning. The policy π is fixed and the agent learns only how good it is, that is, the utilities Uπ(s).
- Direct utility estimation averages the reward-to-go observed from each state over many trials.
- Adaptive dynamic programming (ADP) learns the transition model and rewards, then solves the Bellman equations for the fixed policy.
- Temporal-difference (TD) learning updates after each observed transition from s to s′ with reward r: U(s) ← U(s) + α (r + γ U(s′) − U(s)), where α is the learning rate. It needs no transition model.
3. Active reinforcement learning. The agent must also decide what to do, so it faces the exploration and exploitation trade-off: exploiting the best-known action earns reward now, while exploring may find better actions. A simple rule is ε-greedy: take a random action with probability ε, and the best-known action otherwise.
4. Q-learning is an active, model-free TD method that learns a value Q(s, a) for each state and action:
Q(s, a) ← Q(s, a) + α [r + γ maxa′ Q(s′, a′) − Q(s, a)]
The agent then chooses, in each state, the action with the highest Q value, and U(s) = maxa Q(s, a).
Worked update. Let α = 0.5 and γ = 0.9. In state A the agent takes Right, with Q(A, Right) = 2, receives r = 1 and reaches state B, where Q(B, Left) = 4 and Q(B, Right) = 6.
- Target = r + γ maxa′ Q(B, a′) = 1 + 0.9 × 6 = 6.4
- TD error = 6.4 − 2 = 4.4
- New Q(A, Right) = 2 + 0.5 × 4.4 = 4.2
In conclusion, passive RL evaluates a given policy, active RL also improves it, and Q-learning does this without a model of the environment; RL is used in game playing and robot control.
Expert Systems
Syllabus: Architecture of expert systems; Roles of expert systems; Knowledge acquisition; Meta-knowledge; Heuristics; Typical expert systems: MYCIN, DART and XCON; Expert system shells
One-page revision summary
- An expert system solves problems in a narrow domain at the level of a human expert by reasoning with knowledge obtained from experts.
- Its components are the knowledge base, working memory, inference engine, explanation facility, knowledge acquisition facility and user interface.
- Keeping the knowledge base separate from the inference engine lets knowledge change without reprogramming and makes shells possible.
- The inference engine repeats a match-select-fire cycle, using conflict resolution to pick one rule, and reasons by forward or backward chaining.
- The explanation facility answers WHY a question is asked and HOW a conclusion was reached.
- Expert systems play roles such as interpretation, prediction, diagnosis, design, planning, monitoring, debugging, repair, instruction and control.
- The domain expert supplies the knowledge, the knowledge engineer draws it out and encodes it, and the end user consults the system.
- Knowledge acquisition transfers expertise from experts and other sources into the knowledge base and is the bottleneck of expert system development.
- The stages of knowledge acquisition are identification, conceptualization, formalization, implementation and testing, with testing feeding back to earlier stages.
- Knowledge acquisition techniques include interviews, protocol analysis, observation, case analysis, repertory grids and machine learning from examples.
- Meta-knowledge is knowledge about knowledge, such as meta-rules that decide which rules to try first and rule models that check new rules.
- Heuristics are experience-based rules of thumb that usually give good answers quickly but carry no guarantee of being correct or optimal.
- Heuristic (shallow) knowledge links symptoms directly to likely causes, while deep knowledge models the underlying principles.
- MYCIN, built at Stanford in the 1970s, diagnosed bacterial blood infections and meningitis and recommended antibiotics, using backward chaining over rules with certainty factors.
- XCON (R1), built at Carnegie Mellon for DEC, configured VAX computer orders by forward chaining and was one of the first commercially successful expert systems.
- DART, a Stanford and IBM project, diagnosed faults in computer installations for IBM field engineers, first with EMYCIN rules and later from a design description (model) of the device.
- An expert system shell is an expert system with an empty knowledge base, supplying the inference engine, rule language, editor, explanation facility and interface.
- Examples of shells are EMYCIN (MYCIN without its medical knowledge), CLIPS from NASA and Jess for Java.
Learn these by heart
- Expert system = knowledge base + inference engine, with working memory, explanation facility, knowledge acquisition facility and user interface.
- Forward chaining goes from facts to conclusions (data-driven, as in XCON); backward chaining goes from a goal to supporting facts (goal-driven, as in MYCIN).
- Rule CF: CF(conclusion) = CF(rule) × CF(premise), with CF(A AND B) = min(CF(A), CF(B)) and CF(A OR B) = max(CF(A), CF(B)).
- Two positive CFs for the same conclusion combine as CF = CF1 + CF2 × (1 − CF1); CFs range from −1 to +1.
- Knowledge acquisition stages: identification → conceptualization → formalization → implementation → testing.
- Meta-knowledge is knowledge about knowledge; a heuristic is a rule of thumb with no guarantee.
- Expert system shell = expert system minus its domain knowledge.
2-mark questions
1 What is an expert system? Name its main components. 2 marks
An expert system is a computer program that solves problems in a narrow, specialised domain at the level of a human expert, by reasoning with knowledge obtained from experts. Its main components are the knowledge base, working memory, inference engine, explanation facility, knowledge acquisition facility and user interface.
2 Name the people involved in building and using an expert system, and state the role of each. 2 marks
- Domain expert: has the specialised knowledge and experience that the system must capture.
- Knowledge engineer: draws the knowledge out of the expert, structures it and encodes it in the knowledge base.
- End user: consults the system for advice or decisions.
A tool builder may also supply the shell or programming tools used to build the system.
3 What is the knowledge acquisition bottleneck? 2 marks
Knowledge acquisition, the transfer of expertise from experts and other sources into the knowledge base, is the slowest and costliest step in building an expert system. Experts find their experience-based knowledge hard to put into words, their time is scarce, and the rules need repeated checking. This limiting step is called the knowledge acquisition bottleneck.
4 What is meta-knowledge? Give an example. 2 marks
Meta-knowledge is knowledge about knowledge: what the system knows, how reliable that knowledge is, and when and how to use it. For example, the meta-rule "IF the infection was acquired in hospital THEN try the rules about hospital-acquired organisms first" diagnoses nothing itself; it only controls the order in which the diagnostic rules are tried.
5 What is a heuristic? Give an example of heuristic knowledge in an expert system. 2 marks
A heuristic is a rule of thumb, learnt from experience, that usually finds a good solution quickly but is not guaranteed to be correct or optimal. For example, a car-fault expert system may use: IF the engine does not crank AND the headlights are dim THEN suspect the battery first. Such rules make the system try likely causes first.
6 Two rules in a MYCIN-style system support the same conclusion with certainty factors 0.6 and 0.5. Find the combined certainty factor. 2 marks
Two positive certainty factors for the same conclusion combine as CF = CF1 + CF2 × (1 − CF1).
CF = 0.6 + 0.5 × (1 − 0.6) = 0.6 + 0.5 × 0.4 = 0.6 + 0.2 = 0.8
The combined certainty factor is 0.8. The second rule raises the belief, but the result can never exceed 1.
10-mark questions
1 With a neat diagram, explain the architecture of an expert system and the function of each of its components. 10 marks
An expert system is a program that gives expert-level advice in a narrow domain such as medical diagnosis or computer configuration. Its architecture keeps the domain knowledge (the knowledge base) separate from the general reasoning procedure (the inference engine), so knowledge can be added or changed without rewriting the program.
1. Knowledge base: stores the long-term domain knowledge, mostly as IF-THEN production rules, together with facts and sometimes frames or semantic nets. Much of it is heuristic knowledge, the rules of thumb of the expert. Example: IF the engine does not crank AND the headlights are dim THEN the battery is probably weak.
2. Working memory: holds the facts of the current case, such as the user's answers and the intermediate conclusions. The inference engine reads and updates it; it starts empty for each consultation and grows as rules fire.
3. Inference engine: the reasoning part. It repeats a match-select-fire cycle: find the rules whose conditions match working memory, choose one by a conflict-resolution strategy (rule priority, the most specific rule or the most recent facts), and fire it to add its conclusion. It reasons by forward chaining, from known facts to conclusions (data-driven), or by backward chaining, from a goal to the facts that would prove it (goal-driven), and may combine uncertain evidence with certainty factors.
4. Explanation facility: answers the user's WHY question (why is this question asked?) by showing the rule being tried, and the HOW question (how was this conclusion reached?) by tracing the rules fired. This builds trust and helps developers find wrong rules.
5. Knowledge acquisition facility: an editor through which the knowledge engineer, working with the domain expert, can add and change rules and check them for conflicts or gaps.
6. User interface: carries the dialogue with the user through questions, menus or forms, and presents the advice in an understandable form.
The people around the system are the domain expert, who supplies the expertise, the knowledge engineer, who draws it out and encodes it, and the end user, who consults the system.
In conclusion, the knowledge base and working memory hold what the system knows, the inference engine reasons with it, and the other components make the system usable, trustworthy and easy to maintain. Removing the knowledge base leaves an expert system shell that can be reused in a new domain.
2 What is an expert system shell? Explain its components and the steps in building an expert system with a shell, and give examples with the advantages and limitations of shells. 10 marks
An expert system shell is a ready-made software tool that contains every part of an expert system except the domain knowledge: it is an expert system with an empty knowledge base. A developer builds a new expert system by filling the shell with the rules and facts of one domain, instead of programming the reasoning from scratch. This works because expert systems keep the knowledge base separate from the inference engine.
Components of a shell:
1. Inference engine: a built-in reasoning method (forward chaining, backward chaining or both) with a conflict-resolution strategy, often with certainty factors for uncertainty. 2. Knowledge representation language: a fixed syntax for writing rules and facts, and in some shells frames or objects. 3. Knowledge-base editor: lets the knowledge engineer enter, test and debug rules, and checks them for errors and conflicts. 4. Explanation facility: answers WHY and HOW questions from the trace of the rules tried. 5. User interface and working memory: run the dialogue with the end user, asking questions and giving advice, and hold the facts of each case.
Steps in building an expert system with a shell:
1. Identify a suitable problem: a narrow domain, an available domain expert and knowledge that can be written as rules. 2. Choose a shell whose representation and reasoning fit the problem, for example backward chaining for diagnosis and forward chaining for configuration. 3. Acquire the knowledge from the domain expert and write it as rules in the shell's language. 4. Test the system on real cases with the expert and refine the rules. 5. Deploy and maintain it, updating the knowledge base as the domain changes.
Examples:
- EMYCIN (Essential MYCIN): MYCIN with its medical knowledge removed, used to build PUFF, which interprets lung function tests, and SACON, which advises engineers on structural analysis.
- CLIPS: a forward-chaining rule-based tool developed at NASA.
- Jess: a rule engine for Java, modelled on CLIPS.
Advantages:
- Much shorter development time and lower cost, because the reasoning, explanation and interface parts already exist and are tested.
- Developers concentrate on the knowledge, and domain experts can build small systems themselves.
- Maintenance is easier because the knowledge is kept separate.
Limitations:
- The fixed representation and reasoning method may not suit every problem; a shell designed for diagnosis may handle design poorly.
- A general shell may run more slowly than a program written for one task.
- A shell does not remove the knowledge acquisition bottleneck.
In conclusion, a shell supplies the reasoning and the knowledge base supplies the expertise, so building an expert system becomes mainly a knowledge engineering task.
3 What is knowledge acquisition? Explain its stages and the techniques used to acquire knowledge from experts, and state why it is difficult. 10 marks
Knowledge acquisition is the process of extracting, structuring and organising knowledge from human experts and other sources, such as manuals, case records and databases, and transferring it into the knowledge base of an expert system. A knowledge engineer does it together with one or more domain experts.
Stages of knowledge acquisition:
1. Identification: define the problem, its scope, the people involved, the resources and the goals. 2. Conceptualization: find the key concepts, objects and relations of the domain, and how the expert uses them to reach decisions. 3. Formalization: choose a representation (rules, frames or semantic nets) and an inference method, and map the concepts onto them. 4. Implementation: write the knowledge as rules or frames in a shell or language, producing a working prototype. 5. Testing: run the prototype on test cases with the expert and compare its advice with the expert's.
Testing sends the work back to earlier stages: a wrong rule is fixed by refining the rules in implementation, a poor representation needs a redesign in formalization, and a misunderstood concept needs a reformulation in conceptualization. In short, the team must identify, conceptualize, formalize, implement and test, and repeat as needed.
Techniques:
- Interviews: unstructured interviews at the start to learn the domain, then structured interviews with prepared questions on specific points.
- Protocol analysis: the expert thinks aloud while solving a real problem, and the recorded protocol is analysed to extract rules.
- Observation: the knowledge engineer watches the expert at work.
- Case analysis: the expert explains how particular past cases were solved.
- Repertory grid: the expert rates domain objects against pairs of opposite attributes, which shows how the expert tells them apart.
- Machine learning: induction methods such as decision-tree learning build rules from solved examples.
- Automated tools: programs such as TEIRESIAS, built for MYCIN, help experts enter and debug rules themselves.
Why it is difficult:
- Much expert knowledge is tacit: experts apply it without being aware of it and cannot easily explain it.
- Experts are busy, and their time is costly.
- The expert and the knowledge engineer use different vocabularies.
- Knowledge may be incomplete or inconsistent, and experts may disagree.
For these reasons knowledge acquisition is called the bottleneck of expert system development. Careful acquisition, testing and refinement decide the quality of the final system.
4 Explain meta-knowledge and heuristics in expert systems with suitable examples. 10 marks
Besides plain facts, an expert system needs heuristics, which let it reason quickly the way a human expert does, and meta-knowledge, which lets it decide how to use its own knowledge.
Heuristics
A heuristic is a rule of thumb that an expert learns from experience. It usually leads to a good answer quickly, but it is not guaranteed to be correct or optimal. Much of an expert's skill is such heuristic, or shallow, knowledge, which links symptoms directly to likely causes; deep knowledge, by contrast, models the underlying principles, such as how a device works.
- Car fault finding: IF the engine does not crank AND the headlights are dim THEN suspect the battery first.
- Diagnosis in general: check the common causes of a symptom before the rare ones.
- Search: in route finding, the straight-line distance to the goal estimates the remaining cost; in the 8-puzzle, the number of misplaced tiles estimates the moves still needed.
Heuristics prune the search so that the most promising hypotheses are tried first, allow decisions when data are incomplete or uncertain (usually with a certainty factor attached), and capture the practical experience that makes an expert better than a textbook.
Meta-knowledge
Meta-knowledge is knowledge about knowledge: what the system knows, how reliable each piece is, and when and how to use it. It works at a meta-level above the object-level domain rules, and in rule-based systems it is often written as meta-rules, that is, rules about rules.
Example meta-rule: IF the infection was acquired in hospital THEN try the rules about hospital-acquired organisms first. It diagnoses nothing; it tells the inference engine which rule to try first when it applies the domain rules to the case facts to reach a conclusion.
Uses of meta-knowledge:
1. Control of reasoning: choosing which goals and rules to try first and which to skip, as in conflict resolution. 2. Knowledge acquisition: TEIRESIAS, a program that helped experts extend MYCIN's rules, used rule models, summaries of what typical rules about a conclusion contain, to warn the expert when a new rule seemed to lack an expected condition. 3. Explanation: the system can explain its strategy, not only the rules it fired. 4. Knowing its limits: recognising when a problem lies outside its competence instead of giving confident but wrong advice.
In short, heuristics make an expert system efficient, and meta-knowledge makes it flexible and aware of its own knowledge.
5 Describe the MYCIN expert system: its purpose, structure, knowledge representation, reasoning and explanation. Show with an example how its certainty factors are combined. 10 marks
MYCIN is one of the best-known early expert systems. It was developed at Stanford University in the 1970s, mainly by Edward Shortliffe, to help doctors diagnose bacterial infections of the blood, and later meningitis, and to choose antibiotic treatment.
1. Purpose: from the patient's history, symptoms and laboratory culture results, MYCIN identifies the organisms likely to be causing the infection and recommends antibiotics, with doses adjusted to the patient, for example to body weight.
2. Structure: a consultation program holds the dialogue with the doctor (the user), reads and updates the patient data and does the reasoning; an explanation program uses its reasoning trace to answer questions; and a knowledge acquisition program lets medical experts add and change rules. The rules form the static knowledge base, and the patient data a dynamic database for each case.
3. Knowledge representation: several hundred IF-THEN rules, each with a certainty factor (CF). A simplified rule in MYCIN's style: IF the organism is gram-positive AND its shape is coccus AND it grows in chains THEN there is suggestive evidence (CF 0.7) that the organism is streptococcus. Facts are object-attribute-value triples with their own CFs.
4. Reasoning: backward chaining (goal-driven). MYCIN starts from the goal of deciding which organisms need treatment, finds rules that conclude about it and treats their premises as subgoals, searching depth-first. MYCIN asks the doctor for facts that no rule can establish, such as laboratory results.
5. Certainty factors: a CF lies between −1 (definitely false) and +1 (definitely true), with 0 meaning no evidence. For a rule, CF(conclusion) = CF(rule) × CF(premise), where the CF of an AND of conditions is their minimum. Two positive CFs for the same conclusion combine as CF1 + CF2 × (1 − CF1).
Example: rule R1 (CF 0.7) has conditions known with CF 0.8 and 0.5, so it gives 0.7 × min(0.8, 0.5) = 0.7 × 0.5 = 0.35. Rule R2 (CF 0.6) has a certain condition (CF 1.0) and gives 0.6. Combined: 0.35 + 0.6 × (1 − 0.35) = 0.35 + 0.39 = 0.74. The other order, 0.6 + 0.35 × 0.4 = 0.74, gives the same result.
6. Explanation: the doctor can ask WHY a question is asked (MYCIN shows the rule it is trying) and HOW a conclusion was reached (it lists the rules that fired).
In evaluations its advice compared well with that of infectious-disease specialists, but it was never used routinely in hospitals, mainly because it stood alone and every case had to be typed in, which took a long time, and also because of ethical and legal concerns. Removing its medical knowledge produced the shell EMYCIN.
6 Explain the roles that expert systems play, and describe XCON and DART as typical expert systems. 10 marks
Expert systems are used wherever scarce expertise in a narrow field must be made available widely, quickly and consistently. Their roles can be described by the kind of task they perform.
- Interpretation: inferring a description of a situation from data, as DENDRAL inferred molecular structures from mass-spectrometer data.
- Prediction: forecasting likely consequences, such as weather or crop yields.
- Diagnosis: finding faults or diseases from symptoms, as in MYCIN for infections and DART for computer faults.
- Design and configuration: arranging components to meet constraints, as in XCON.
- Planning: choosing a sequence of actions to reach goals, such as the steps of a laboratory experiment.
- Monitoring and control: comparing observed with expected behaviour and acting on the difference.
- Debugging, repair and instruction: prescribing and carrying out remedies for faults, or tutoring a student by finding and correcting mistakes.
Towards its user, a system may act as an assistant doing routine analysis, a colleague whose advice is weighed, or an expert whose advice is normally accepted. For an organisation, it preserves the knowledge of retiring experts, gives consistent advice at any hour and helps train junior staff.
XCON (R1):
1. It was developed by John McDermott at Carnegie Mellon University for Digital Equipment Corporation (DEC), first under the name R1, and was in use at DEC from about 1980. 2. Task: configuring VAX computer systems from customer orders. It checked that each order was complete and consistent, added missing components, and decided how the components were placed in cabinets and connected by cables. 3. Method: a production system written in OPS, a rule language from Carnegie Mellon, using forward chaining. The facts of the order trigger rules that make one configuration decision after another, with almost no backtracking, because the rules hold enough knowledge to make each choice correctly. 4. Impact: it grew from several hundred rules to thousands and saved DEC an estimated tens of millions of dollars a year. It is often described as one of the first commercially successful expert systems.
DART:
1. It was a joint project of the Heuristic Programming Project at Stanford University and IBM in the early 1980s. (A later military logistics planner, the Dynamic Analysis and Replanning Tool, only shares the name.) 2. Task: diagnosing faults in computer installations. It advised IBM field service engineers by naming the hardware and software components most likely to cause an observed fault, with a brief explanation of the evidence. It began with the teleprocessing subsystems of IBM 370-class computers. 3. Method: the first version was built with the EMYCIN shell as production rules. Michael Genesereth then developed a version that reasoned from a design description of the device, a model of its parts, connections and expected behaviour, instead of from symptom-fault rules, so the same method can diagnose other devices. 4. Significance: it showed that diagnosis can use deep knowledge of how a device works, not only experience-based rules as in MYCIN.
Thus MYCIN and DART for diagnosis and XCON for configuration show the range of roles expert systems play.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
39 pages
- Rational agents (NUS CS3243 lecture slide)
- Properties of breadth-first search (NUS CS3243 lecture slide)
- Dempster–Shafer theory (Wikipedia)
- Resolution (logic) (Wikipedia)
- DART: An Expert System for Computer Fault Diagnosis (IJCAI 1981)
- Stanford HPP Report 81-20: diagnosis from design descriptions (AITopics)
- Genesereth, The use of design descriptions in automated diagnosis (AITopics)
- Mycin (Wikipedia)
- Dartmouth workshop (Wikipedia)
- Logic Theorist (Wikipedia)
- AI winter (Wikipedia)
- Learning representations by back-propagating errors (Nature 323, 1986)
- Physical symbol system (Wikipedia)
- Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA* (IJCAI 1993)
- Environment types (NUS CS3243 lecture slide)
- Alpha-beta pruning (Wikipedia)
- Properties of alpha-beta (NUS CS3243 lecture slide)
- A* search algorithm (Wikipedia)
- Branching factor (Wikipedia)
- Horizon effect (Wikipedia)
- Quiescence search (Wikipedia)
- Last-Branch and Speculative Pruning Algorithms for Max-n (IJCAI 2003)
- Hill climbing (Wikipedia)
- Chess piece relative value (Wikipedia)
- Inference engine (Wikipedia)
- Horn clause (Wikipedia)
- Local consistency (Wikipedia)
- Verbal arithmetic (Wikipedia)
- Expanding the Utility of Semantic Networks Through Partitioning (IJCAI 1975)
- Frame (artificial intelligence) (Wikipedia)
- Skolem normal form (Wikipedia)
- Davis–Putnam algorithm (Wikipedia)
- Q-learning (Wikipedia)
- ID3 algorithm (Wikipedia)
- Inference in Datalog (NYU AI course notes, E. Davis)
- Explanation-based learning (Wikipedia)
- Buchanan and Shortliffe, Rule-Based Expert Systems, Preface (1984)
- Xcon (Wikipedia)
- CLIPS (Wikipedia)
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Artificial Intelligence: A Modern Approach · Stuart Russell and Peter Norvig
- Artificial Intelligence · Elaine Rich, Kevin Knight and Shivashankar B. Nair
- Computational Intelligence: A Logical Approach · David Poole, Alan Mackworth and Randy Goebel
- Artificial Intelligence: Structures and Strategies for Complex Problem Solving · George F. Luger
- Artificial Intelligence: A New Synthesis · Nils J. Nilsson