Artificial Intelligence

Artificial intelligence (AI) is the use of computer systems to do tasks that normally need human intelligence: recognising speech and images, making decisions, planning and learning. This chapter covers how graphs support AI, and the main kinds of machine learning. The ethical issues are in chapter 7.

18.1 Artificial intelligence (AI)

Graphs

A graph is a data structure made of nodes (vertices), which represent things (a place, a state of a game, a web page), and edges (arcs) that join the nodes. Edges may be directed (one way) and may be given a weight (a cost: distance, time, price). Graphs model networks: road maps, social networks, computer networks, and the possible moves in a puzzle or game.

A graph can be stored as an adjacency matrix (a 2D array where the entry at row i, column j is the weight of the edge from node i to node j, or 0 or ∞ if there is none), or an adjacency list (for each node, a list of the nodes it is joined to). The matrix is quick to check for a particular edge, but uses much memory for a graph with few edges; the list is more compact.

        A   B   C   D        Adjacency matrix of
   A    0   4   0   2        A-B (4), A-D (2),
   B    4   0   3   0        B-C (3), C-D (1)
   C    0   3   0   1
   D    2   0   1   0

How graphs help AI

An AI that has to find a solution can treat the problem as a graph: each possible state is a node and each action an edge, and the goal is to find a good path from the start to the goal. Examples: a satnav finding the quickest route, a game character moving round obstacles, a robot planning, and a recommendation system using links between users and products.

• Dijkstra's algorithm finds the shortest path from one node to all others in a weighted graph. It always expands the unvisited node with the lowest total cost so far, updating the costs of its neighbours, until the destination is reached. It always gives the best route but may check a lot of nodes that are in the wrong direction.
• A* (A star) algorithm is an improvement that uses a heuristic: an estimate of the remaining cost from a node to the goal (for example the straight-line distance). It chooses the node with the lowest f = g + h, where g is the known cost from the start and h is the estimated cost to the goal. It heads towards the goal, so it usually examines far fewer nodes and is faster, and finds the best route if the heuristic never overestimates.

Tap to enlarge

A weighted graph of six nodes A to F with the distances on the edges and the shortest path from A to F highlighted, A to C to B to D to E to F with a total of 13, and the final table of distances and previous nodes found by Dijkstra's algorithm

Close

To use Dijkstra on a small graph, keep a table with the shortest distance found so far for each node and the previous node; repeatedly take the unvisited node with the smallest distance, update its neighbours (if going through it is cheaper), and mark it visited. Read the route back through the "previous" column.

Machine learning

Machine learning (ML) is a branch of AI in which a system learns from data and improves its performance with experience, without being explicitly programmed with the rules. The program builds a model from training data and then uses it to make predictions or decisions on new data.

Main types:

• Supervised learning: trained on labelled data, where each example comes with the correct answer (an email marked as spam or not). The model learns to map inputs to outputs and is checked on data it has not seen. Used for classification and prediction.
• Unsupervised learning: finds patterns or groups in unlabelled data without being told the answers, for example grouping customers with similar buying habits (clustering).
• Reinforcement learning: a system (an agent) learns by trial and error in an environment. It takes actions and receives rewards for good results and penalties for bad ones, and it learns a strategy that maximises the total reward over time. Used for game-playing programs, robots learning to walk, and self-driving vehicles. No labelled data is needed, but it can take a very large number of attempts.

The reasons for using ML: it can handle tasks where the rules are too complicated to write by hand (recognising faces or speech); it can find patterns in huge amounts of data; it can adapt as new data arrives; and it can work faster and for longer than a person. The drawbacks: it needs large amounts of good data (biased data gives a biased system), it can be hard to explain the decisions, and it needs a lot of computing power.

Artificial neural networks (ANN)

An artificial neural network is a machine learning model inspired by the brain. It is made of connected nodes (artificial neurons) in layers:

• an input layer (one node for each input value),
• one or more hidden layers that do the processing, and
• an output layer that gives the result.

Each connection between nodes has a weight that says how strong it is. A node adds up its inputs, each multiplied by its weight, and passes the total through an activation function; if the result is large enough it "fires" and sends a signal to the next layer. Learning means adjusting the weights so that the output gets closer to the correct answer.

 Inputs        Hidden layer        Output
  x1 ---w---> (o) ---w---> 
  x2 ---w---> (o) ---w---> (o) ---> result
  x3 ---w---> (o) ---w---> 

Neural networks have helped machine learning by being able to learn complex, non-linear patterns directly from raw data, such as pixels or sound, and to improve with more data. They are used for image and speech recognition, translation and medical diagnosis.

Tap to enlarge

An artificial neural network with an input layer of three nodes, two hidden layers of four nodes and an output layer of two nodes, every node joined to every node in the next layer by a weighted connection

Close

Deep learning

Deep learning is machine learning that uses an artificial neural network with many hidden layers (a "deep" network). Each layer learns to recognise features at a higher level than the one before: in an image, the first layers may find edges, the next shapes, and the last whole objects such as a face. It can find the important features by itself from raw data, so people do not need to specify them, and it often gives the most accurate results on very complex problems. It needs huge amounts of data and a great deal of processing power (usually GPUs), takes a long time to train, and its decisions are hard to explain.

Back propagation of errors

Back propagation is the method used to train a neural network (supervised learning):

1. The training data is put through the network (forward pass) to get an output.
2. The output is compared with the correct answer to find the error.
3. The error is passed backwards through the network, from the output layer to the earlier layers, and the contribution of each weight to the error is worked out.
4. Each weight is adjusted a little to reduce the error.
5. The process is repeated many times with many examples, until the error is small enough.

Regression methods

Regression is used to predict a numerical value (such as a price or temperature) from other values, by finding the relationship between them in the training data. Linear regression fits a straight line ($y = mx + c$) that is as close as possible to the data points, by minimising the total error (for example the sum of squared distances between the points and the line). The line can then be used to predict $y$ for a new $x$. Logistic regression is used for classification, predicting the probability of an item belonging to one of two classes. In machine learning, the model is trained by choosing the values of its parameters (such as $m$ and $c$) that give the smallest error on the training data.