Ch 1 · 18 Artificial Intelligence (AI) · AS & A Level Computer Science 9618
Topic 1 of 1 in Artificial Intelligence — AS & A Level Computer Science 9618 — 79 lessons.
Introduction
Many AI systems work by searching for the best solution among many possibilities, or by learning patterns from data. This lesson covers graphs and two graph search algorithms (Dijkstra and A\*), then machine learning: neural networks, deep learning, the main learning categories, back propagation and regression. (Syllabus topic 18: section 18.1.) You will not be asked to write code for graph searches, but you must be able to carry them out by hand.
Key ideas — 18.1 (a) Graphs in AI
A graph is a set of nodes (vertices) connected by edges (arcs).
🧑🏫 Teacher's explanation
Imagine you are in a massive, sprawling shopping mall. Each store is a 'node' (a point where you can be), and the walkways connecting them are 'edges'. Some walkways are longer than others—you can think of this length as a 'weight'. If you want to get from the food court to the cinema as quickly as possible, you are performing a 'search' on this graph.
📖 Definitions
🔍 Worked example — Easy
Using the provided graph, find the shortest path from node A to node C using only direct edges or single intermediate nodes. Edges: A-B (4), A-C (2), A-G (3), B-C (1).
🔍 Worked example — Standard
Apply Dijkstra's algorithm logic to find the shortest distance from node A to node D in the following subgraph: A-B (4), A-C (2), B-D (5), C-D (8), C-B (1).
🔍 Worked example — Exam-style
In an A* search, the total cost f(n) is calculated as f(n) = g(n) + h(n), where g(n) is the actual cost from the start to node n, and h(n) is the heuristic estimate from n to the goal. Given: Start is A, Goal is D. Path A arrow C: g(C) = 2. Heuristic for C to D: h(C) = 5. Heuristic for B to D: h(B) = 2. Path A arrow B: g(B) = 4. Calculate f(C) and f(B) and determine which node the A* algorithm would expand next.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
For a node n, the function f(n) = g(n) + h(n) is used. g(n) is the cost from the start to node n. h(n) is the estimated cost from node n to the goal Z.
Key ideas — 18.1 (b) Dijkstra's algorithm
Dijkstra's algorithm finds the shortest path from a start node to every other node.
🧑🏫 Teacher's explanation
Imagine you are standing in a large shopping mall and want to find the quickest way from the entrance to a specific store. You don't know which corridors are the shortest, so you start exploring every path you see. However, you are smart: you always choose to walk down the path that currently looks the shortest from where you are standing. As you walk, you keep a notepad where you write down the shortest time it took to reach every shop you pass. If you find a shortcut to a shop you've already seen, you erase the old time and write down the new, shorter time.
📖 Definitions
🔍 Worked example — Easy
A graph has three nodes: A, B, and C. The edge weights are: A to B = 5, A to C = 10, B to C = 2. Find the shortest distance from A to C.
🔍 Worked example — Standard
Find the shortest path from node S to node T in a graph with edges: (S,A)=4, (S,B)=2, (A,T)=5, (B,A)=1, (B,T)=8.
🔍 Worked example — Exam-style
A graph has nodes {1, 2, 3, 4}. Edges: (1,2)=10, (1,3)=5, (2,4)=1, (3,2)=3, (3,4)=8. Find the shortest path from 1 to 4.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 18.1 (c) The A* algorithm
A\* finds the shortest path from a start node to a single goal, usually much faster than Dijkstra, by using a heuristic: an estimate of the remaining cost from each node to the goal (e.g. the straight-line distance).
🧑🏫 Teacher's explanation
Imagine you are in a massive, dark shopping mall trying to find a specific store. Dijkstra's algorithm is like walking in every possible direction, one meter at a time, exploring every hallway and corner equally until you accidentally bump into the store. It is thorough but very slow because it doesn't know where the store is located.
📖 Definitions
🔍 Worked example — Easy
A node X has a current path cost from the start of g = 15. The heuristic estimate from X to the goal is h = 7. Calculate the f value for node X.
🔍 Worked example — Standard
In a graph, node A is the start and F is the goal. The path A arrow B arrow F has actual costs: A arrow B = 5 and B arrow F = 8. The heuristic for node B is h(B) = 3. Calculate the f value for node B.
🔍 Worked example — Exam-style
A search algorithm is navigating a grid. The current node N has g = 12. The heuristic h for N is 5. Another node M has g = 10 and h = 4. Which node will the A* algorithm expand next, and what is its f value?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Calculate the f value for node P. [1] (b) State the purpose of the heuristic in the A* algorithm. [2] [3 marks]
Key ideas — 18.1 (d) Artificial neural networks
An artificial neural network (ANN) is modelled on the neurons of the brain. It has:
🧑🏫 Teacher's explanation
Imagine you are trying to teach a child to recognize a 'dog'. You don't give them a manual of mathematical rules like 'if ears > 5cm and snout is wet'. Instead, you show them 1,000 pictures of dogs. Every time they guess wrong, you nudge them slightly to adjust their mental criteria. This is exactly how an Artificial Neural Network (ANN) works.
📖 Definitions
🔍 Worked example — Easy
A single neuron receives two inputs, x_1 = 0.5 and x_2 = 0.8. The weights for these connections are w_1 = 0.4 and w_2 = -0.2. Calculate the weighted sum of the inputs before an activation function is applied.
🔍 Worked example — Standard
A neural network is performing supervised learning. The network predicts an output of 0.7 for an image of a cat, but the actual label (the correct answer) is 1.0. Calculate the error (difference) between the prediction and the target.
🔍 Worked example — Exam-style
In a deep learning model, an error is calculated at the output layer. The system uses back propagation to adjust weights. If the error is E, and the gradient of the error with respect to a weight w is partial E/partial w = 0.5, and the learning rate eta = 0.1, what is the new weight if the current weight is 0.5?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 18.1 (e) Machine learning, deep learning and reinforcement learning
🧑🏫 Teacher's explanation
Imagine you are teaching a child to identify animals. In supervised learning, you show them a picture and say, "This is a cat." They learn the pattern. In unsupervised learning, you give them a pile of animal toys and say, "Put things that look similar together." They might group them by color or shape without knowing what a 'cat' is.
📖 Definitions
🔍 Worked example — Easy
A supervised learning model is being trained to classify emails as 'Spam' or 'Not Spam'. The training set contains 800 'Spam' emails and 200 'Not Spam' emails. If the model predicts 'Spam' for every single email, what is its accuracy?
🔍 Worked example — Standard
In a reinforcement learning scenario, an agent receives a reward of +10 for reaching a goal and a penalty of -5 for hitting an obstacle. If the agent takes 5 actions that result in 2 goals and 3 obstacles, calculate the total reward.
🔍 Worked example — Exam-style
A deep learning neural network uses 3 hidden layers. The first layer detects edges, the second detects shapes, and the third detects complex features. If the input image is a 28 × 28 pixel grayscale image, how many total input pixels are being processed in the first layer?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify the type of machine learning being used. [1] (b) Explain why this type of learning is preferred for this application rather than supervised learning. [2] [3 marks]
Key ideas — 18.1 (f) Back propagation of errors
Back propagation is how a neural network is trained in supervised learning:
🧑🏫 Teacher's explanation
Imagine you are practicing archery. You fire an arrow (the forward pass), and it lands 10cm to the left of the bullseye (the error). To improve, you don't just shrug; you analyze how your stance, your grip, and your release contributed to that error. You adjust your grip slightly to the right to compensate. This adjustment is the 'back propagation'.
📖 Definitions
🔍 Worked example — Easy
A single neuron receives an input of x = 0.8. The weight of the connection is w = 0.5. The activation function is a simple identity function (output = x × w). If the target output is 0.5, calculate the error (Target - Actual).
🔍 Worked example — Standard
In a neural network, the error calculated at the output layer is E = 0.4. During back propagation, the gradient for a specific weight w is calculated to be 0.2. If the learning rate is eta = 0.1, calculate the new weight if the current weight is w_old = 0.5 and the update rule is w_new = w_old - (eta × gradient).
🔍 Worked example — Exam-style
A neural network is undergoing back propagation. The error at the output layer is 0.05. The weight adjustment required for the output layer is 0.02. The weight adjustment required for the hidden layer is 0.01. If the network performs 100 iterations of back propagation with these constant adjustments, what is the total cumulative adjustment applied to the hidden layer weight?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State the purpose of the back propagation process in this context. [2] (b) Describe the steps involved in the back propagation process. [3] [5 marks]
Key ideas — 18.1 (g) Regression
Regression is a supervised machine learning method that predicts a continuous numerical value from input data, by finding the relationship between variables. Linear regression fits the line of best fit, y = mx + c, through the training data, choosing m and c to minimise the error between the predicted and actual values. Example: predicting a house's price from its floor area, or a student's exam mark from hours of revision. (Classification, by contrast, predicts a category.)
🧑🏫 Teacher's explanation
Imagine you are trying to guess how much a person weighs based on their height. You notice that as height increases, weight generally increases too. If you plot these points on a graph, they won't form a perfect straight line, but they will follow a general upward trend. Regression is the mathematical process of drawing the 'best' possible straight line through those points so that if someone tells you their height, you can look at your line and make a very good guess of their weight.
📖 Definitions
🔍 Worked example — Easy
A simple linear regression model follows the equation y = 2x + 5. If the input value x is 10, what is the predicted value y?
🔍 Worked example — Standard
A machine learning model uses the line of best fit y = mx + c. Given m = 0.5 and c = 12, calculate the predicted value y when x = 40.
🔍 Worked example — Exam-style
In a regression task, the actual value for a data point is y_actual = 50. The model predicts y_pred = 42. Calculate the error (residual) for this specific point.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Worked example
Deep learning, trained on millions of labelled images, lets the car's cameras recognise pedestrians, road signs and other vehicles, because deep neural networks are good at finding features in images. Reinforcement learning helps it learn driving decisions (when to brake, change lanes, turn) by trial and error in simulations, receiving rewards for safe, smooth, efficient driving and penalties for collisions, because there is no single correct answer to label for every situation.
🔍 Worked example — Easy
A self-driving car uses Deep Learning to identify objects. If the network identifies a 'Stop Sign' with 95\% confidence and a 'Speed Limit Sign' with 40\% confidence, which object is the most likely intended classification?
🔍 Worked example — Standard
In a Reinforcement Learning scenario for a robot, the reward function R is defined as: R = 10 for reaching the goal, R = -5 for hitting an obstacle, and R = -1 for every second spent moving. If the robot reaches the goal in 5 seconds without hitting an obstacle, calculate the total reward.
🔍 Worked example — Exam-style
Explain the difference between Supervised Learning and Unsupervised Learning in the context of a self-driving car's sensor data.
⚠️ Common errors
Common mistakes
Practice
Answers: (1) To model states and the connections (with costs) between them, so the best path can be searched for; e.g. route finding in satellite navigation. (2) It estimates the remaining cost to the goal; adding it to the actual cost (f = g + h) directs the search towards the goal, so fewer nodes are expanded. (3) A → C (2) → B (3) → D (8): shortest distance 8. (4) Supervised uses labelled data to learn to predict outputs (e.g. spam detection); unsupervised uses unlabelled data to find groups or patterns (e.g. customer segmentation). (5) An agent takes actions in an environment and receives rewards or penalties, learning by trial and error which actions maximise its total reward. (6) An input is passed forward; the output is compared with the correct output to find the error; the error is passed backwards through the network and each weight is adjusted to reduce it; repeated over many examples. (7) A continuous numerical value, from the relationship between input variables (e.g. a line of best fit).