Artificial Intelligence (AI)

🕸️ 22.02 How graphs can be used in AI Figure 22.01

A graph is a collection of nodes (or vertices) which may be joined by edges. Each node has a name. An edge can carry a label, which is a numerical value.

A common use: the nodes are places and the edge labels are the distances between them. An edge is only drawn when you can travel directly between that pair of places. A graph like this can be used to find the shortest route between two nodes that are not next to each other.

We could find the shortest route from A to D ourselves by listing every possible route and adding up each one:

Fine for six nodes — but for a graph with 100 nodes this would take far too long. Luckily, AI algorithms have been developed to solve this kind of problem.

Book slip fixed: the book says "Using Figure 20.01" here; it means Figure 22.01.

🛣️ Dijkstra's algorithm

Dijkstra's algorithm finds the shortest path from one starting node to every other node. Here is the book's Structured English design for a simplified version:

Identify the source node (S) where the path starts.
Create an empty set called the ShortestPath set.
Create another set called RemainingNodes and put all of the nodes
  into this, including the source node (S).
Create a record that stores:
    node names
    calculated values for the distance to the node from the source node
    the sequence of nodes in the route to the node.
Set the distance value for the source node S to be 0.
Set the distance value for all other nodes to be INFINITY
  (a large value greater than any value that will be calculated).
While the ShortestPath set does not include all of the nodes:
    Pick the node (N) from the RemainingNodes set that has the
      lowest distance value.
    Move this node into the ShortestPath set.
    For each node in the RemainingNodes set that is adjacent to N:
        Calculate a new distance value by adding the label of the
          edge connecting the two nodes to the stored distance for N.
        If this value is less than the value currently stored,
          replace the stored value by the new one.
        If a new value has been stored, enter the sequence of
          nodes used to obtain this value.

Table 22.01 shows the algorithm working on Figure 22.01. Node names are red while still in the RemainingNodes set. The node N picked at each stage is in black. Data turns grey when it can no longer change, because the node has moved into the ShortestPath set.

Notice that some data never changes once it is set (nodes C and E), but other data has to be updated later (nodes D and F).

⭐ The A* algorithm

Dijkstra finds the best route from one node to all the others. Often you only want the best route to one target. You could stop Dijkstra once the target's route is fixed, but it would still do far more work than needed — at the start it may be busy exploring routes heading in completely the wrong direction.

A* ("A star") is a modification of Dijkstra designed to fix this. One step changes. In Dijkstra the step is:

Calculate a new distance value by adding the label of the edge connecting the two nodes to the already stored distance for N.

In A* it is expanded to:

Calculate a new distance value by adding the label of the edge connecting the two nodes to the already stored distance for N.
Calculate an estimated value for the distance of N from the destination node and add this to the new distance value.

The estimate of the distance still to go needs a heuristic function. Whatever function is chosen, it must guarantee that the estimate is lower than the actual value (it must never over-estimate).

🗺️ A worked example: seven towns Figure 22.02 · Table 22.02 · Figure 22.03

The task: find the shortest route between two towns using the existing roads. Figure 22.02 is a basic map of seven towns, A–G.

The map matters because it was drawn from an x–y coordinate for each town, and those coordinates are the basis of the heuristic. Pythagoras's theorem gives the straight-line ("as the crow flies") distance:

Direct distance = √( (difference in x)² + (difference in y)² )

This straight-line distance should always be less than any distance actually travelled along roads.

Table 22.02 The x–y coordinates for the towns A–G

The roads are shown as a graph in Figure 22.03. An edge means a road links the two towns directly, and its label is the distance along that road.

There are many versions of A*. The book points out that the version it demonstrates does not exactly match any one version in the literature.

📜 The book's Structured English for A*

Create three lists: the initial list, the open list and the closed list.
Insert an empty record for each node in the graph into the initial list.
Store the x and y coordinates of the node in each record of the initial list.
Initialise the value for distance travelled to zero in each record.
Create a look-up table with an entry for each pair of nodes that have
  a direct connecting road.
Store the distance of travel along that road for each pair of nodes.
Identify the target node for the travel.
Identify the starting node and copy its record into the open list.
Delete the record for the starting node from the initial list.

Now recursively apply the following until all possibilities have been examined:

For the parent node in the open list identify all adjacent nodes in the initial list.
Copy the record for each of the adjacent nodes into the open list.
Delete the records for the adjacent nodes from the initial list.
Check if the target node is now in the open list.

If the target node is NOT in the open list:
    For each adjacent node now added, use the look-up table to find the
      distance of travel from the parent node.
    If options exist, calculate a value for each route and choose the smallest.
    For each adjacent node update the distance travelled and the path sequence.
    For each adjacent node use the heuristic function to calculate an
      estimated distance to travel.
    For each adjacent node calculate an estimated total distance from start
      node to target node (distance travelled + estimated distance to travel).
    Identify the adjacent node with the lowest estimated total. Leave its
      record in the open list as a parent node. Copy the records for the
      remaining nodes into the closed list and delete them from the open list.
    Continue with the next iteration of the recursion.

If the target node IS in the open list, for this node only:
    Use the look-up table to find the actual distance from the parent node.
    Calculate the total distance travelled.
    If the target's record has zero distance travelled, enter the value now
      calculated and the path sequence.
    If it already has a value, compare; if the new route is shorter, update
      the distance travelled and the path sequence.
    Copy the record for the target node into the initial list and delete it
      from the open list.
    If there is another adjacent node in the open list, continue with the
      actions above for when the target is not in the open list.
    If the open list is now empty, rewind to check nodes in the closed list
      that have not been included in previous path sequences. For each,
      calculate an estimated total distance from start node to target node.
      If this estimate is greater than the stored distance travelled for the
      target, continue to rewind. If it is less, copy the node's record into
      the open list as a parent node and continue with the actions above for
      when the target is not in the open list.

🚶 The book's walk-through: from A to D

1. With A as the parent, B, C and F are the adjacent nodes brought into the open list:

   Node	Distance travelled g	Estimated further distance h	Total f
   B	13	100	113
   C	45	50.2 (the book rounds to 51)	95.2 (book: 96)
   F	20	88.6 (book: 89)	108.6 (book: 109)

   There are two possible calculations for C and for F, but in each case the direct road is shorter.
2. C has the lowest total, so B and F move to the closed list and C becomes the new parent. The only adjacent node still in the initial list is G, which comes into the open list.
3. G becomes the parent for its adjacent nodes D and E. D is the target. The actual distance A → C → G → D is 45 + 25 + 40 = 110. This is stored in D's record, and D's record moves back to the initial list.
4. E is the only node left in the open list, so it becomes the parent. Its only adjacent node in the initial list is D, which comes back into the open list. The actual distance A → C → G → E → D is 45 + 25 + 10 + 15 = 95. That is lower than 110, so D's record is updated and moved back to the initial list.
5. The rewind now checks B and F. Their estimated totals (113 via B, about 109 via F) are both greater than 95, so they can be ignored. The shortest route is A–C–G–E–D, total distance 95.

📈 22.03 Machine learning

The requirements for machine learning can be summarised as:

• a computer-based system has a defined task or tasks to perform
• knowledge is acquired through the experience of performing the tasks
• as a result of this experience and knowledge, the performance of future tasks is improved.

Learning from experience is a sign of intelligence, so machine learning is one of the many approaches under the umbrella of AI. Learning can happen in several ways; three are considered here.

🧩 Unsupervised learning

In unsupervised learning the system has to draw its own conclusions from its experience of the results of the tasks it has performed. Algorithms are needed that can organise or categorise the knowledge it gains. One example identifies "conceptual clusters" using a hierarchy: all the knowledge starts in the root of a tree, then groups are moved into branches depending on their attributes.

Unsupervised learning is now a dominant activity. Powerful computers with access to huge data banks make decisions based on recorded past actions. Our activity on the web is recorded and stored, then used to decide which products or services to recommend to us next. There is no theoretical framework for this — it is rather as though the intelligence is built into the data.

👩‍🏫 Supervised learning

In supervised learning the system is fed knowledge with an associated classification. For example, an AI program might be developed to mark exam questions. During training it is given answers to exam questions together with a grade or categorised comments for each one.

A special case: expert systems

An expert system always focuses on a narrowly defined domain of knowledge. Human experts are given samples of data to analyse and provide the conclusions to be drawn. The data and conclusions go into the knowledge base. The system is tested by an expert supplying sample data and checking the system's conclusions; if performance is poor, more data and conclusions are added.

🏆 Reinforcement learning

Reinforcement learning has some features of unsupervised learning and some of supervised learning. It has its own vocabulary:

• An agent is learning how best to perform in an environment.
• The environment has many defined states.
• At each step the agent takes an action.
• The agent has a policy that guides its actions.
• The policy is influenced by the recorded history and by knowledge of the current state of the environment.
• An action changes the environment to a new state.
• After each action the agent receives a reward: a measure of how effective the action was towards the overall goal.
• The policy guides the agent in deciding whether the next action should exploit knowledge it already has or explore a new avenue.

In summary, the aim is to maximise the reward by improving the policy. It is a trial-and-error search for the best performance, needing many repeated attempts at the same problem.

Applications: playing logic games such as backgammon; robotics, where a robot learns to do a task well; navigating a maze — when the agent turns the way that eventually leads to the exit it gets a positive reward, and a wrong turn earns a negative one.

📉 Regression analysis methods Figure 22.04

Sometimes the aim of an AI system is to predict a numerical output from input values. To use regression analysis, the system is first given real values for both the inputs and the outputs. This data is used to look for a correlation. If a correlation exists that can be written as a mathematical formula, that formula can then predict outputs when new data is input.

The simplest case: one input quantity and a linear relationship. Example: an AI system predicting candidates' A Level Computer Science marks. We might expect them to correlate with the candidates' IGCSE Mathematics marks. Figure 22.04 shows what might be found from historic data.

There is good correlation. The straight line is the calculated best fit, and its formula could sensibly be used to predict future A Level Computer Science marks from IGCSE Mathematics marks.

Regression can be more complicated. A formula could be fitted using marks from three different exams as inputs. Or a non-linear relationship may be needed — for example, predicting the sales of a new product whose sales are expected to grow exponentially.

🧠 22.04 Artificial neural networks Figure 22.05

The neural networks in our brains give us our intelligence, so it seems obvious to use artificial neural networks as a foundation for AI systems. Figure 22.05 shows two nerve cells.

At one end of a nerve cell are many dendrites, which can receive signals. At the other end are many axon terminal buttons, which can transmit signals. The synapse is the region between an axon terminal button and a dendrite, and it contains neurotransmitters. When a cell receives input signals, the voltage in the axon rises. At some threshold voltage the neurotransmitters are activated and signals are sent to the dendrites of neighbouring cells.

🔺 Modelling it in a computer Figure 22.06

An artificial neural network can be built in software or hardware. In Figure 22.06 the triangles are the nodes, which represent artificial neurons (they are sometimes drawn as circles). A node can receive one or more inputs and send its output to one or more other nodes.

Modelling a node: a weighting factor is applied to each input; the weighted values are summed; then an activation function computes the node's output. Any input that is not a number must first be converted into one so the weighted values can be summed.

Figure 22.06 has three layers. The left column of three nodes receives the input; the right column gives the output. The two nodes in between form a hidden layer. Some networks have several hidden layers.

🔋 An example: battery cost-effectiveness

Imagine an AI system using a neural network to estimate the cost-effectiveness of batteries, based on the price paid and the lifetime of use.

• Each input represents one example battery — data that identifies the battery and its price.
• One hidden node might be concerned with the type of device the battery is used in; the other with the type of user of that device.
• The output nodes compute an estimated cost per unit of time for a specific battery.

Every node has adjustable factors: the weighting factors for each input and the activation function. During initial learning these must be tuned to make the predictions as accurate as possible. The method used is back propagation of errors:

1. Collect real battery-lifetime data from actual use.
2. Create the system with trial values for all the adjustable factors.
3. Run it with the input data that matches the real use. Each output node now has an error: the difference between its output and the real lifetime value.
4. Re-run with different weights and activation functions for the output-layer nodes, to see how the accuracy of the output depends on those factors.
5. Do the same for the nodes in the hidden layer, and finally for the input layer.
6. The system can now predict the cost-effectiveness of other batteries. As more real-use data becomes available, back propagation can be applied again to improve it further.

🏗️ Deep Learning

In the brain, neurons are thought to be arranged in layers: the lower layers have easily understood functions, while higher layers do more abstract processing. With today's computing power, artificial neural networks are being built with large numbers of hidden layers to try to do something similar. These are Deep Learning systems.

📌 Summary

• A graph can be constructed from nodes and edges, where the edges carry numerical value labels.
• Algorithms are available to find the shortest path between two nodes in a graph.
• Machine learning can be supervised or unsupervised.
• Regression analysis involves finding a mathematical equation which is a best fit to sample data.
• Artificial neural networks are modelled using nodes which receive input and provide output.
• Back propagation of errors can be used for machine learning using artificial neural networks.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.