Artificial Intelligence

A graph is a data structure made up of:

• Nodes (also called vertices) — points that represent a state or object (e.g. a town, a junction, a position in a game).
• Edges — connections that join two nodes (e.g. a road between two towns).

A weighted graph adds a number (a weight) to each edge, representing a cost such as distance, travel time or price.

Term	Meaning
Node / vertex	a point (a state or object)
Edge	a connection between two nodes
Weight	a numeric cost on an edge

Why graphs help AI. Many AI problems are really about finding the best path through a set of possibilities — the shortest route on a map, the cheapest sequence of moves, the quickest way from one state to a goal state. A graph captures which states are connected and how costly each connection is, so a search algorithm can explore it efficiently and return the lowest-cost path.

Here is a small weighted graph (the one used in the worked example). Each circle is a node; each line is an edge labelled with its weight:

Dijkstra's algorithm finds the shortest path from a start node to every other node in a weighted graph. The idea:

1. Give the start node a distance of 0 and every other node a tentative distance of infinity. Mark all nodes unvisited.
2. Pick the unvisited node with the smallest known distance.
3. Relax each of its neighbours: if (current distance + edge weight) is smaller than the neighbour's recorded distance, update it.
4. Mark the current node visited (its shortest distance is now final).
5. Repeat from step 2 until every node is visited.

Tracing the graph above from A (edges: A–B 4, A–C 1, C–B 2, C–D 5, B–D 1, D–E 3):

Visit	Node	Distances updated
1	A (0)	B = 4, C = 1
2	C (1)	B = 3 (improved from 4), D = 6
3	B (3)	D = 4 (improved from 6)
4	D (4)	E = 7
5	E (7)	— done

Result: A = 0, C = 1, B = 3, D = 4, E = 7. Notice B's distance improved from 4 to 3 once C had been processed — that overwrite is exactly what "relaxing" means.

Key point: Dijkstra uses only the actual cost so far (often called g). It has no idea where the goal is, so it effectively spreads outward in all directions until it reaches everything.

A* does the same job as Dijkstra — find a shortest path — but it is goal-directed (informed). It adds a heuristic:

A heuristic (h) is an estimate of the remaining cost from a node to the goal (for a map, this could be the straight-line distance).

A* chooses which node to expand next using:

$f(n) = g(n) + h(n)$

where:

• g(n) = the actual cost from the start to node n (the same value Dijkstra uses), and
• h(n) = the estimated cost from n to the goal.

Because h points toward the goal, A* prefers nodes that look closer to the destination, so it expands fewer nodes that lead away from the goal and usually reaches the goal faster than Dijkstra.

	Dijkstra	A*
Information used	cost so far (g)	g + heuristic h
Search direction	all directions	toward the goal
Best for	shortest paths to all nodes / no good heuristic	shortest path to one goal with a good heuristic
Typical speed (single goal)	slower	usually faster

In short: A* is Dijkstra plus a heuristic. If you set h = 0 everywhere (no estimate), A* behaves exactly like Dijkstra.

An artificial neural network (ANN) is loosely modelled on the brain. It is built from layers of interconnected nodes ('neurons'):

• Input layer — receives the raw data (e.g. the pixels of an image).
• Hidden layer(s) — do the processing; there can be one or many.
• Output layer — produces the result (e.g. 'cat' or 'dog').

Every connection between nodes has a weight (a number). A node combines its weighted inputs to produce an output that is passed on to the next layer. Learning happens by adjusting the weights.

How ANNs helped machine learning. Before ANNs, programmers had to hand-code the rules for a task. ANNs instead learn the patterns directly from data, including very complex, non-linear ones. This made huge progress possible in tasks that were too hard to write rules for — image recognition, speech recognition, handwriting recognition, language translation and more.

Machine learning (ML) is a branch of AI in which a system improves at a task by learning from data, rather than being explicitly programmed with the rules. There are three main categories:

Supervised learning — learns from labelled data. Each training example has an input and its correct output (a label). The model learns the mapping input → known output, then predicts outputs for new inputs.

• Classification — predict a category (e.g. spam / not spam).
• Regression — predict a continuous number (see §6).
• Use it when you have labelled examples of the right answers.

Unsupervised learning — finds patterns in unlabelled data. There are no labels/correct outputs; the model discovers structure by itself, most commonly by clustering similar items together.

• Use it when you have lots of data but no labels — e.g. grouping customers into segments, or spotting unusual transactions.

Reinforcement learning — learns by reward and penalty. An agent takes actions in an environment and receives a reward for good outcomes or a penalty for bad ones. Through trial and error over many attempts it learns the actions that maximise its total reward.

• Use it when the correct action isn't known in advance but outcomes can be scored — e.g. game playing, robotics, self-driving control.

Category	Training data	Goal	Example
Supervised	labelled	predict known output	spam filter, price prediction
Unsupervised	unlabelled	find patterns/clusters	customer segmentation
Reinforcement	rewards/penalties	maximise reward	game-playing agent

Deep learning is ML that uses neural networks with many hidden layers. The extra layers let the network learn increasingly abstract features, giving very high accuracy on hard problems — it is how much of modern supervised/unsupervised/reinforcement learning is implemented.

Back propagation of errors is the main way a neural network is trained:

1. Forward pass — feed an input through the network to get an output.
2. Measure the error — compare the network's output with the target (correct) output.
3. Propagate the error backwards — pass this error back through the layers, from the output layer toward the input layer.
4. Adjust the weights — change each connection weight by a small amount in the direction that reduces the error.
5. Repeat over many training examples until the outputs are accurate enough.

So back propagation is, in one line: the error is propagated backwards and the weights are adjusted to reduce it. This is what lets a network gradually 'learn'.

Regression methods. Regression is a supervised technique that predicts a continuous numeric value from input features — for example predicting a house price from its size and location, or a temperature from weather readings.

• It is supervised because it learns from examples whose correct numeric values are known.
• It differs from classification: classification outputs a discrete category/label, whereas regression outputs a number on a continuous scale.
• A simple form, linear regression, fits a straight line through the data and uses it to predict new values; the model is improved by reducing the difference (error) between its predictions and the actual values — the same 'reduce the error' idea seen in back propagation.