Artificial intelligence

Why AI starts with a graph

Almost every decision an artificial intelligence (AI) system makes can be written as a search: which route, which move, which sequence of actions reaches the goal. Before a program can search, it needs a model of the problem, and the model used here is a graph. A graph is an abstract data type made of nodes (also called vertices) and edges (also called arcs), so it stores objects and the relationships between them and nothing else.

To use a graph for AI, the nodes are the states the problem can be in and the edges are the moves from one state to another. In a route planner the nodes are towns and the edges are the roads. In a sliding-tile puzzle each node is one arrangement of the tiles and each edge is one legal move. In a board game each node is a position and each edge is a legal move to the next position. The complete set of states and moves is called the state space, and once the problem is expressed this way, solving it means finding a path from the start node to a goal node.

The point of using a graph is scale. A map of a country, a chess position or a delivery round has far too many possibilities for a person to check, but a graph lets a program store them compactly and hand them to an algorithm that explores them in a sensible order. That is why the graph is the first half of AI and the search algorithm is the second half: the graph says what the possibilities are, and the algorithm decides which ones to look at.

• Node (vertex): the object or state being represented - a town, a board position, a web page, one arrangement of a puzzle.
• Edge (arc): a link between two nodes showing a relationship or a legal move - a road, a move, a hyperlink.
• Undirected edge: the link works both ways, like a two-way road. Directed edge: it works one way only, like a one-way street, and a graph made of directed edges is a directed graph or digraph.
• Weight: a number on an edge giving its cost - distance, time, fuel or money. In an unweighted graph every edge counts as equal.
• Path: a sequence of edges from one node to another. Its cost is the sum of the weights along it, and the shortest path is the one with the lowest total cost, not necessarily the fewest edges.
• Adjacency matrix: an n by n two-dimensional array in which the cell at row i, column j holds the weight of the edge from node i to node j, or 0 if there is no edge.
• Adjacency list: for each node, a list of the nodes it is joined to together with the weights, so only the edges that actually exist are stored.

Dijkstra's algorithm: shortest path from one node

Dijkstra's algorithm finds the path of lowest total weight from a chosen start node to a destination. It keeps a tentative distance for every node, set to 0 for the start, infinity for all the others, together with a record of the node each one was reached from.

At each step it selects the unfinalised node with the smallest tentative distance and marks it finalised, meaning its distance is now known to be the true shortest distance. It then relaxes each neighbour: it compares the distance the neighbour already has with the distance to the current node plus the weight of the edge between them, and keeps the smaller value, updating the previous-node record whenever it improves.

The algorithm repeats until the destination is finalised, or until every reachable node has been finalised. Reading the previous-node records backwards from the destination gives the shortest path itself. A simple implementation scans all the nodes to find the smallest each time and is O(n squared); a priority queue reduces this to O((n + e) log n), where e is the number of edges. The table below traces it on a graph with edges A-B 4, A-C 2, C-B 1, C-D 8, B-D 5, B-E 12 and D-E 2, taking A as the start and E as the destination.

• Every edge weight must be zero or positive; negative weights break the algorithm.
• It works on directed and undirected graphs, and it finds the shortest distance to every node, not only to one destination.
• Its result is always the true shortest path, with no estimate involved.
• On a very large graph it behaves like a ripple spreading out equally in all directions, so it spends time exploring routes that lead away from the destination.

A*: searching towards the goal

The A algorithm is a shortest-path search that uses a heuristic, which is an estimate of the remaining cost from a node to the goal. For each node it calculates f = g + h, where g is the cost of the best route found so far from the start, h is the estimate from that node to the destination, and f is therefore the estimated total cost of a route through that node. At every step A expands the unfinalised node with the smallest f.

The heuristic has to be admissible: it must never overestimate the true remaining cost. The straight-line distance between two points on a map is admissible for road travel, because no road can be shorter than the straight line between its ends, and the number of tiles out of place is admissible for a sliding-tile puzzle, because each tile needs at least one move. With an admissible heuristic A* is guaranteed to return a shortest path, and it usually expands far fewer nodes than Dijkstra's algorithm because the h term pulls the search towards the goal.

The worked example uses the same graph as before, with heuristic values A 9, B 6, C 7, D 2 and E 0, which you can read as an estimate of the distance still to travel to E. A* expands A, then C with f = 9, then B with f = 9, then D with f = 10, then E and stops: the route found is A -> C -> B -> D -> E with cost 10, the same answer Dijkstra gave, and every node that was expanded lay on or near the best route. On a graph this small both algorithms expand the same five nodes; the saving from the heuristic appears on a large graph, where nodes that lead away from the destination are given a high f and are never expanded at all.

Dijkstra or A*: choosing the right search

Both algorithms find a shortest path, so the choice is about what information you have and what answer you need. Dijkstra's algorithm needs nothing but the weighted graph, and it gives the shortest distance to every node, which is what a network router wants when it has to fill in a routing table for every destination.

A needs a heuristic that can be calculated for any node, and it is worth the effort when there is a single destination and a good estimate is available, as in a satellite navigation system, a game character finding its way across a map, or a robot planning a route through a room. The better the heuristic, the fewer nodes are expanded, so A can be dramatically faster on a large graph.

The risk with A* is a heuristic that overestimates. The answer can then be a route that is not the cheapest, and a very poor heuristic can make the search wander further than Dijkstra would have. Dijkstra also has a weakness of its own: it cannot cope with negative edge weights, and it can waste time expanding large parts of the graph that lie in the wrong direction.

Machine learning, deep learning and reinforcement learning

Machine learning is the approach in which a program is not given the rules for a task. Instead it is given examples, and it builds a model from them that can be used to make predictions or decisions about new, unseen data. A programmer who writes a spam filter by hand lists the words and rules that mark a message as spam; a machine learning system is given thousands of messages already marked spam or not spam and works out the pattern for itself.

There are several reasons for choosing this approach. For some tasks nobody can write the rules down - describing exactly how to recognise a face, a spoken word or a handwritten letter in code is effectively impossible. For others the rules exist but there are far too many of them to write and maintain. Data also changes: fraud patterns, prices and language shift over time, and a model retrained on new examples keeps up in a way that a fixed set of rules cannot. Machine learning also finds patterns in very large data sets that a person would never notice, and its accuracy tends to improve as more training data is supplied.

Deep learning is machine learning that uses an artificial neural network with many hidden layers. Its advantage is that it learns the features it needs directly from raw data - the edges and shapes that make up a face, the sounds that make up a word - instead of relying on a person to decide in advance which measurements matter. That is why deep learning transformed image, speech and language tasks, and why it needs large amounts of data and considerable computing power.

Reinforcement learning is different again. There is no set of labelled examples and no correct answer supplied. An agent takes actions in an environment, receives a reward or penalty for what happens, and learns a policy - which action to take in each state - by trial and error, with the aim of maximising the total reward over time. It suits problems that are a sequence of decisions rather than a single judgement: playing a game, controlling a robot, or balancing the cooling in a data centre, where a good move now may only pay off many moves later.

• Machine learning: a model is learned from data, then used to predict or decide on new data, instead of rules being written by hand.
• Deep learning: machine learning with a many-layered neural network, which learns its own features from raw data such as pixels or sound.
• Reinforcement learning: an agent learns by acting, receiving rewards and adjusting its behaviour, with no labelled examples at all.
• Reasons for machine learning: the rules are unknown or too complex, there are too many rules, the data keeps changing, or the patterns are too subtle or too large for a person to find.
• Reasons for deep learning: the input is raw and high-dimensional, feature selection is itself difficult, and accuracy improves with more data and processing power.
• Reasons for reinforcement learning: the task is a sequence of decisions with delayed rewards, and the best action is not known in advance.

Supervised, unsupervised and reinforcement learning

Machine learning is divided into categories according to the kind of data and feedback available. In supervised learning every training example carries a label, which is the correct answer. The model learns the mapping from input to output and is then judged on how well it predicts the label for data it has not seen. If the label is a category, such as spam or not spam, the task is classification; if the label is a number, such as a price, the task is regression. The cost of supervised learning is the labelling: somebody has to mark up thousands of examples, and errors in the labels teach the model the wrong thing.

In unsupervised learning there are no labels. The model is given the inputs alone and looks for structure: grouping similar records into clusters, or finding items that occur together. A retailer can feed a year of transactions into a clustering algorithm and discover groups of customers who buy in similar ways, without anyone having decided in advance what those groups are. Because there is no correct answer to compare against, the output has to be interpreted by a person, and there is no straightforward way to score how right it is.

Reinforcement learning is a third category, and it is neither of these. The data is not a fixed data set at all: the agent generates its own experience by acting, and the feedback is a reward signal rather than a label. Learning is slow because the agent must try many actions, and the design of the reward matters enormously, because the agent will optimise whatever is rewarded, including a badly chosen reward that encourages the wrong behaviour.

Supervised learning is the category to reach for when you have historical examples with known outcomes; unsupervised learning when you want to explore data and find groups or associations you did not know were there; reinforcement learning when the problem is a series of decisions in an environment that responds to what the agent does.

Artificial neural networks

An artificial neural network (ANN) is a model built from layers of simple processing units. The input layer has one unit for each feature of the data, such as the brightness of each pixel in an image. One or more hidden layers sit between the input and the output, and the output layer produces the result - a class, a probability or a number.

Each connection between a unit in one layer and a unit in the next carries a weight, which is a number saying how strongly that input affects that unit. A unit calculates the sum of every input multiplied by its weight, adds a bias that shifts the total, and passes the result through an activation function that decides what the unit passes on. The activation function is what allows the network to represent a curved, non-linear relationship rather than only a straight-line one, which is why a network can separate classes that no straight line could separate.

Running data forward through the network from input to output is called a forward pass, and it is how a trained network makes a prediction. The weights are what the network has learned: they start as small random numbers, and training is the process of adjusting them until the outputs match the training data. Because each hidden unit combines many inputs, the hidden layers can build up intermediate features - an early layer responding to edges, a later layer to combinations of edges that form a shape - which is what makes a network able to work from raw data.

ANNs helped machine learning because they removed two of its main limits. A person no longer has to decide which features of the data to measure, since the network learns useful combinations of the raw inputs for itself. And a network with enough units can approximate very complex relationships, so it copes with noisy, high-dimensional data such as images, audio and text, where classical statistical methods struggled.

• Input layer: one unit per feature; it passes the data into the network unchanged.
• Hidden layer(s): units that combine the inputs, applying weights, a bias and an activation function; more layers allow more abstract features.
• Output layer: produces the prediction - one unit for a yes or no decision, one per class for a classification, or one for a numeric value.
• Weight: the strength of a connection, adjusted during training; the set of all weights is what the network has learned.
• Bias: a constant added inside each unit, which shifts the activation so that the unit can fire even when all its inputs are zero.
• Activation function: the non-linear step that decides the output of a unit, so the network can model curves rather than only straight lines.
• Forward pass: data flowing from the input layer to the output layer to produce a prediction from the current weights.

Back propagation of errors

A new network has random weights, so its first predictions are poor. Back propagation of errors is the training method that fixes them. The training data goes through a forward pass and produces an output, which is compared with the correct, known output. The difference between them is the error, measured by a loss function such as the sum of the squared differences.

That error exists only at the output layer, but the weights that caused it are spread through every layer, and the hidden units have no target values of their own. Back propagation solves this by working backwards: the error at the output is used to calculate how much each weight in the last layer contributed to it, that share is passed back to the previous layer, and the process continues layer by layer to the input. The calculation uses the derivative of the activation function, which is why the activation function must be differentiable.

Each weight is then adjusted in the direction that reduces the error, by an amount controlled by the learning rate - a large rate learns quickly but can overshoot, a small rate is stable but slow. This adjustment is gradient descent. One pass through the whole training set is an epoch, and training repeats for many epochs until the error stops falling. If training continues too long the network can memorise the training examples, including their noise, and then perform badly on new data.

Back propagation is what made multi-layer networks practical. Before it, there was no way to set the weights of the hidden layers, because no one knows what a hidden unit ought to output; after it, a network with many hidden layers could be trained from examples, which is the basis of deep learning.

• Forward pass: present one training example and calculate the network's output.
• Calculate the error: compare that output with the known correct output using a loss function.
• Backward pass: propagate the error back through the layers, working out each weight's share of the blame using the derivatives of the activation functions.
• Update the weights: change each weight slightly in the direction that reduces the error (gradient descent), scaled by the learning rate.
• Repeat: do this for every example, for many epochs, until the error is acceptably small or stops improving.

Regression methods

Regression is a supervised learning method that predicts a continuous numeric value rather than a category. The simplest form, linear regression, fits a straight line to the training data: y = mx + c, where x is the input, y is the predicted value, m is the gradient and c is the intercept. Training chooses m and c so that the line is as close as possible to the data points, normally by least squares, which minimises the sum of the squared vertical distances between each point and the line.

With more than one input the method becomes multiple regression, which fits an equation with one coefficient per input - for example predicting a house price from its floor area, number of rooms, age and distance from the centre. Each coefficient says how much the predicted value changes when that input rises by one unit while the others stay the same, so the model can be inspected as well as used.

Regression is not restricted to straight lines: the inputs can be transformed, or a curve fitted, to capture a relationship that bends. A related method, logistic regression, produces a probability between 0 and 1 and is therefore used for classification even though its name contains the word regression - the output is a probability that an item belongs to a class, which is then turned into a decision by a threshold.

In machine learning terms, regression is the supervised task you choose when the answer is a number: a price, a temperature, a demand, a lifespan. It is a good first method because it is fast, needs comparatively little data, and its coefficients can be explained to a person, but it assumes the relationship has the shape you have chosen, so it underfits a problem whose pattern is genuinely complex - which is one of the reasons deep networks are used instead.

• Simple linear regression: one input, a straight line, y = mx + c.
• Multiple regression: several inputs, one coefficient each, so the effect of each can be separated.
• Least squares: the fitting method that minimises the total squared distance between the data points and the line.
• Logistic regression: predicts a probability and is used for classification, not for a continuous value.
• Use it when: the output is numeric, the relationship is fairly smooth, and you need a model that can be explained.