QADAM

Prologue

A robot with no ideas yet

This book follows that journey. Every chapter matches one week of the AI Fundamentals course, and every skill Qadam learns is a real AI technique. The three characters play fixed roles: Qadam is the agent that has to act, Aru is the engineer who asks the questions a beginner would ask, and Bürkit explains the theory.

You do not need any background to read it. Technical terms are highlighted like this the first time they appear and are collected again in the glossary at the end.

What is artificial intelligence?

Artificial intelligence (AI) is the study and design of systems that perceive their surroundings, reason about them and choose actions that achieve goals. Textbooks describe four historical views: systems that think like humans, act like humans (the Turing test, 1950), think rationally (logic), and act rationally. This course, like the standard textbook by Russell and Norvig, uses the last one: AI is about building rational agents.

The agent–environment loop

An agent is anything that observes its environment through sensors and acts on it through actuators. A single observation is a percept; everything the agent has observed so far is its percept sequence. The mapping from percept sequences to actions is the agent function; the code that implements it on a real machine is the agent program.

Rationality: doing the right thing with what you know

A rational agent chooses, for every percept sequence, the action that is expected to maximize its performance measure, given its evidence and built-in knowledge. Three consequences follow:

• Rational is not omniscient. If a bridge collapses while Qadam drives over it, the choice to cross could still have been rational given what Qadam knew.
• Rational depends on the performance measure. “Arrive fast” and “arrive safely” lead to different best actions.
• Rational agents gather information and learn. Looking before crossing is part of acting well.

PEAS: describe the job before the algorithm

Before choosing any algorithm, engineers write down the task as PEAS: Performance measure, Environment, Actuators, Sensors. Here is Qadam’s:

What kind of world is it?

The right design depends on the environment. Six questions classify any task:

Five agent architectures

From simplest to richest:

1. Simple reflex agent: if-then rules on the current percept only (“obstacle closer than 40 cm → stop”). Fast and transparent, but blind to anything it cannot see right now.
2. Model-based reflex agent: keeps an internal state, a memory of the parts of the world it cannot currently see (“there was a hole behind that bush”).
3. Goal-based agent: imagines future action sequences and picks one that reaches a goal. This needs search and planning (Chapters 2–4).
4. Utility-based agent: goals are not enough when trade-offs exist (fast vs safe). A utility function scores outcomes, and the agent maximizes expected utility (Chapter 5).
5. Learning agent: any of the above plus a learning element that improves its behaviour from feedback (Chapters 8–9).

A search problem has five parts

1. Initial state: where the agent starts (S, the workshop).
2. Actions: what it can do in each state (drive along a road).
3. Transition model: which state an action leads to.
4. Goal test: is this state a goal? (G, the clinic.)
5. Path cost: the sum of step costs (minutes of driving).

All states and actions together form the state-space graph. A search algorithm explores it by building a search tree of partial plans. The plans waiting to be explored form the frontier (also called the fringe). Taking a plan from the frontier and adding its successors is called expanding a node. Every search algorithm in this chapter is the same loop; they differ only in which frontier node they expand next.

Uninformed search: no hints

Breadth-first search (BFS) expands the shallowest node first, using a first-in-first-out queue. It finds the route with the fewest roads, which is the cheapest route only when every road costs the same.

Depth-first search (DFS) expands the deepest node first, using a last-in-first-out stack. It needs very little memory, but it can wander far down a bad branch and is not optimal.

Uniform-cost search (UCS) expands the node with the smallest path cost so far, written g(n), using a priority queue. With positive step costs it always returns the cheapest route. It is the search version of Dijkstra’s algorithm.

Informed search: using Bürkit’s hint

A heuristic h(n) estimates the cost from n to the goal. Greedy best-first search trusts only h(n): fast, but easily fooled. A* search combines both:

f(n) = g(n) + h(n)  =  cost so far + estimated cost still to go

A heuristic is admissible if it never overestimates the true remaining cost, and consistent if for every road n → n′ with cost c, h(n) ≤ c + h(n′). With an admissible heuristic A* tree search is optimal; with a consistent heuristic A* graph search is optimal and never needs to reopen a node. Straight-line distance is the classic admissible heuristic: no road is shorter than a straight line.

Worked example: four algorithms, one map

I ran all four algorithms on Figure 2.1 in Python (neighbours in alphabetical order; a node counts as expanded when it is taken from the frontier, the goal included). Bürkit’s heuristic was checked against the true remaining costs (S 7, A 6, B 4, D 3, C 1, E 8): it is both admissible and consistent.

UCS and A* both find the optimal 7-minute route, but A* never expands the Elevator: f(E) = 2 + 7 = 9 is larger than the cost of the route it already has. That saved expansion is exactly what a good heuristic buys. On large maps the saving is thousands of nodes.

When the path is not the answer

In Chapter 2 the answer was a route. In many problems only the final configuration matters: where to put a mast, how to place eight queens on a chessboard, which order to visit cities in (the travelling salesperson problem), how to set the weights of a neural network. Local search keeps just one (or a few) complete candidate solutions and improves them step by step. It uses almost no memory and works in huge or continuous spaces.

Three ingredients: a state (one complete candidate), a set of neighbours (small changes to it), and an objective function that scores it (to maximize, like height; or to minimize, like cost or error).

Take a delivery robot in Astana. The state is the order of its stops (the QAIRU campus, Bayterek, EXPO, Khan Shatyr, the railway station and so on), the objective is the total length of the tour, and a neighbour is made by 2-opt: remove two roads from the tour and reconnect the two pieces the other way round, which reverses the segment between them. If the new tour is shorter, keep it. In the lecture’s example a single such move shortens the route from 76 km to 68 km, and the robot simply repeats this until no move helps.

Hill climbing

Hill climbing moves to the best neighbour as long as it is better than the current state, and stops when no neighbour is better. Here is a trace on Qadam’s altimeter readings along one valley, starting at position 0:

Three ways to get stuck

• Local maximum: a peak higher than its neighbours but lower than the best peak (Figure 3.1).
• Plateau: a flat area where all neighbours have the same value, so there is no direction to follow.
• Ridge: a narrow rising crest where every single small step goes downhill, even though the ridge itself rises.

Escaping

Random-restart hill climbing runs hill climbing many times from random starts and keeps the best result. Sideways moves allow a limited number of steps across plateaus.

Simulated annealing borrows an idea from metalwork: hot metal moves freely, then settles as it cools. It picks a random neighbour; a better one is always accepted, and a worse one is accepted with probability

P(accept) = e^{Δ / T}   (Δ < 0 is how much worse, T is the “temperature”)

At high temperature bad moves are often accepted (exploration); as T falls they become rare (exploitation). For a move that is 2 units worse: at T = 10, e−0.2 ≈ 0.819; at T = 1, e−2 ≈ 0.135. If the temperature is lowered slowly enough, the probability of finding the global optimum approaches 1.

Local beam search keeps k states at once and keeps the best k of all their neighbours, so good regions attract more searchers. Genetic algorithms keep a population, select parents by fitness, combine them by crossover and add random mutation. In continuous spaces we follow the slope directly: gradient descent updates θ ← θ − α ∇f(θ), the same rule that trains neural networks in Chapter 9.

Constraint satisfaction: when rules define the answer

A constraint satisfaction problem (CSP) has three parts: a set of variables, a domain of allowed values for each variable, and constraints that say which combinations of values are allowed. A solution is a complete and consistent assignment: every variable has a value and no constraint is violated.

• Variables: KZ, KG, UZ, TJ, TM (Kazakhstan, Kyrgyzstan, Uzbekistan, Tajikistan, Turkmenistan).
• Domains: {red, green, blue} for every country.
• Constraints: countries that share a border get different colours. There are seven such borders: KZ–KG, KZ–UZ, KZ–TM, KG–UZ, KG–TJ, UZ–TJ, UZ–TM.

A CSP is usually drawn as a constraint graph: one node per variable and one edge per constraint.

Backtracking search, with good habits

Backtracking search is depth-first search for CSPs: it assigns one variable at a time and goes back (backtracks) as soon as a constraint is violated. Three habits make it much faster than blind trial and error:

• Minimum remaining values (MRV): choose next the variable with the fewest legal values left (“fail first”). Ties are broken by the degree heuristic: pick the variable involved in the most constraints with unassigned variables.
• Least constraining value (LCV): for the chosen variable, try first the value that removes the fewest options from its neighbours.
• Forward checking: after every assignment, delete the values that just became illegal from the neighbours’ domains. If some domain becomes empty, backtrack immediately instead of discovering the dead end later.

Here is the full run on Aru’s map (values tried in the order red, green, blue; remaining ties broken alphabetically):

Arc consistency is a stronger form of constraint propagation. An arc X → Y is consistent if for every value of X there is some allowed value of Y. The AC-3 algorithm keeps a queue of arcs, removes values that have no support, and re-checks the neighbours of every changed variable. It can prove that a problem has no solution before any search starts.

Local search works for CSPs as well. The min-conflicts heuristic starts from a complete assignment that may break some rules, picks a variable that is in conflict and gives it the value that breaks the fewest constraints. On the n-queens puzzle it is astonishingly effective: even with a million queens it needs only about 50 steps on average after the initial assignment.

Hard rules and soft wishes: the QAIRU timetable

Real timetables mix two kinds of constraints. Hard constraints must never be broken: a teacher cannot teach two classes at once, a room cannot host two classes at once, and a student group cannot be in two places. Soft constraints are wishes, such as “no long idle gaps between classes”. The lecture treats the university timetable (6 subjects, 4 teachers, 3 rooms, 5 time slots) as local search over complete weekly timetables. A neighbour swaps the time or the room of two classes, and the cost to minimize is

Cost = 100·T + 100·R + 20·S + 5·W

Here T, R and S count teacher, room and student-group clashes, and W counts idle gaps. The large weights make a single hard clash more expensive than many gaps, so the search removes clashes first. With our own example numbers: a draft with one teacher clash, two group clashes and three gaps costs 100 + 40 + 15 = 155. After one good swap it has no teacher clash, one group clash and two gaps, so the cost drops to 20 + 10 = 30. Once T = R = S = 0 the timetable is a valid CSP solution, and the remaining cost only measures how comfortable it is. Industrial solvers such as Google OR-Tools handle the same kind of problem at full university scale.

Games as search

Togyz kumalak (“nine pebbles”) is a traditional Kazakh board game: two players, nine holes each, 162 stones. Like chess it is deterministic, fully observable, turn-taking and zero-sum: one player’s gain is exactly the other’s loss. A game is defined by an initial state, whose turn it is, the legal actions, a transition model, a terminal test and a utility for each final position (+1 win, 0 draw, −1 loss). All possible plays form the game tree.

Minimax

Call our player MAX and the rival MIN. The minimax value of a position is the utility MAX can guarantee if both sides play perfectly:

MINIMAX(s) = UTILITY(s) if terminal · max over actions if MAX moves · min over actions if MIN moves

The minimax algorithm computes this by depth-first recursion, backing values up from the leaves. It is complete for finite trees and optimal against an optimal opponent, but it visits the whole tree: O(bm) time. For chess, with about 35 moves per position and games of about 80 plies, that is hopeless.

Alpha–beta pruning

Alpha–beta pruning returns the same decision as minimax while skipping branches that cannot change it. It carries two numbers down the tree: α, the best value MAX can already guarantee, and β, the best value MIN can already guarantee. As soon as a MIN node’s value drops to α or below, MAX will never let play reach it, so its remaining children are pruned. With perfect move ordering alpha–beta needs only about O(bm/2) nodes, so it can search roughly twice as deep in the same time.

Worked example

MAX chooses one of three moves; MIN then replies. Leaf values are scores for MAX. The MIN values are min(5, 9, 7) = 5, min(4, 8, 10) = 4 and min(6, 2, 11) = 2, so MAX picks the left move with value 5. Alpha–beta reaches the same answer but skips three leaves: after seeing 4 in the middle branch it knows that branch is worth at most 4 < 5, and after seeing 2 in the right branch it knows that branch is worth at most 2. Step through it below.

Real games need shortcuts

Real game trees are far too deep, so programs stop at a fixed depth and score positions with an evaluation function (for example material count in chess, or stones in your kazans in togyz kumalak). Stopping too early can cause the horizon effect: a disaster just beyond the search depth stays invisible. Games with dice add chance nodes, and expectimax replaces min with a probability-weighted average. Very large games such as Go use Monte Carlo tree search, which estimates a move’s value by playing many quick random or learned games from it.

Markov decision processes

A Markov decision process (MDP) describes sequential decisions when actions have random outcomes. It has:

• a set of states S and actions A;
• a transition model T(s, a, s′) = P(s′ | s, a);
• a reward function R(s, a, s′) (here a small living reward for every step and +1 / −1 at the exits);
• a discount factor γ between 0 and 1: a reward one step later is worth γ times as much.

“Markov” means the future depends only on the current state, not on how you got there. A solution is a policy π(s), an action for every state. The optimal policy π* maximizes the expected sum of discounted rewards.

Rewards, returns and the discount

A reward is what the agent gets for one step. The return is the discounted sum of all rewards from now on, G = r₁ + γ·r₂ + γ²·r₃ + …. For rewards 5, 10 and 20 with γ = 0.9 the return is 5 + 9 + 16.2 = 30.2. The discount decides how far ahead the agent “sees”: a reward of 100 that arrives 10 steps later is worth only 0.10 today with γ = 0.5, 34.87 with γ = 0.9 and 90.44 with γ = 0.99.

Because outcomes are random, the agent compares expected values. An action that gives +10 with probability 0.9 and −50 with probability 0.1 is worth 0.9·10 + 0.1·(−50) = 4 on average. Two kinds of value are used. V(s) says how good it is to be in state s; Q(s, a) says how good it is to take action a in s and act well afterwards. They are linked by V*(s) = maxa Q*(s, a): if Q(A, left) = 2, Q(A, right) = 8, Q(A, up) = 4 and Q(A, down) = −5, then V*(A) = 8 and the best action is “right”.

The Bellman equation

The value of a state is the best expected one-step reward plus the discounted value of where you land:

V*(s) = max_a Σ_s′ T(s, a, s′) · [ R(s, a, s′) + γ · V*(s′) ]

Value iteration starts with V₀ = 0 and applies this equation to every state again and again; the values converge to V*. The policy is then read off by choosing the action with the best expected value in each state. Policy iteration alternates two steps instead: evaluate the current policy, then improve it greedily; it often converges in fewer rounds.

Worked example: the frozen yard

Qadam’s yard is a 4×3 grid with one rock. The top-right cell is the clinic gate (+1), the cell below it is a hole in the ice (−1). Each move goes the intended way with probability 0.8 and slips to each side with probability 0.1; hitting a wall or the rock means staying put. Every step costs 0.04. With γ = 1, value iteration converges to the values below (they match the classic textbook result), and the arrows show the optimal policy.

The first iterations show how information spreads backwards from the reward. For the cell left of the gate: V₁ = −0.04; V₂ = 0.8·(−0.04 + 1) + 0.1·(−0.04 − 0.04) + 0.1·(−0.04 − 0.04) = 0.752 (the two slips bump into the wall or slide down, landing on cells whose V₁ is −0.04); V₃ = 0.827. One cell further left becomes positive only at iteration 3 (0.546). Value moves one step per iteration.

From planning to learning: reinforcement learning

Value iteration and policy iteration are planning: they need to know T and R. A real robot usually does not; it must learn by trying. This is reinforcement learning (RL). Unlike supervised learning, nobody shows the right answer. The agent only receives rewards, often late, and must work out which earlier actions earned them.

Monte Carlo methods wait until an episode ends and move V(s) toward the return that actually happened. Temporal-difference (TD) learning does not wait: after a single step it compares what it expected with what it has just seen.

δ = r + γ · V(s′) − V(s)     V(s) ← V(s) + α · δ

Example: V(A) = 5; the robot moves to B and gets r = 2; V(B) = 8, γ = 0.9. The target is 2 + 0.9·8 = 9.2, so the TD error is δ = 4.2. The step went better than expected and V(A) rises; with α = 0.5 it becomes 7.1.

Q-learning applies the same idea to Q-values, so the agent can choose actions without any model. After each experience (s, a, r, s′) it updates

Q(s, a) ← Q(s, a) + α · [ r + γ · max_a′ Q(s′, a′) − Q(s, a) ]

Example: Q(A, right) = 4, r = 2, the best Q-value at B is 8, γ = 0.9, α = 0.5. The target is again 9.2, the error is 5.2 and the new value is 4 + 0.5·5.2 = 6.6. Repeated over many episodes the Q-table settles, and the policy is read off as π(s) = argmaxa Q(s, a). In the lecture’s five-cell corridor the early episodes wander back and forth, and the later ones walk straight to the goal.

The agent has to balance exploration (trying actions to learn more) and exploitation (using what it already knows). The three knobs above are independent: α is about the size of a correction, γ about the horizon, ε about curiosity.

On-policy, off-policy, with or without a model

SARSA is Q-learning’s cautious twin. Its name lists what it uses, (s, a, r, s′, a′): the target is r + γ·Q(s′, a′) with the action a′ the agent will really take next, exploratory moves included. That makes it on-policy. Q-learning is off-policy: it learns about the greedy policy (the max) while it behaves ε-greedily. Next to a cliff, SARSA learns a safer path a little away from the edge, while Q-learning learns the shortest path right along it and falls more often while exploring.

Model-based RL first learns T and R from experience and then plans with them. Model-free RL (Monte Carlo, TD, Q-learning, SARSA) learns values or a policy directly. Model-based methods need fewer real trials; model-free methods are simpler and are not misled by a wrong model.

When the table is too big: deep RL

A Q-table needs one number for every state–action pair. The lecture’s home-battery manager sees charge level, electricity price, demand, solar output and hour: 10 × 20 × 20 × 20 × 24 = 1,920,000 states, and with three actions (charge, hold, discharge) 5,760,000 Q-values. Most of them would never be visited. Function approximation replaces the table with a model that generalizes between similar states, usually a neural network (Chapter 9). A deep Q-network (DQN) learns Q(s, a; θ) and is kept stable by an experience replay buffer (training on shuffled past experiences) and a separate target network; in 2015 one DQN design learned to play 49 Atari games using only the screen pixels and the score. Policy-gradient methods learn the policy πθ(a | s) directly, and actor–critic methods combine an actor (the policy) with a critic (a value estimate that judges it).

Reward design and safety

An RL agent optimizes exactly what is rewarded, not what we meant. This is reward misspecification, and its result is reward hacking: in a well-known 2016 experiment a boat-racing agent found that circling forever to hit the same bonus targets scored more points than finishing the race. For physical machines the lecture’s advice is to keep hard safety limits outside the reward (a maximum speed or a forbidden zone is enforced by a separate controller, not traded against points), to train first in a simulator or on logged data, to watch for sensor faults and for situations unlike the training data, and to keep a human override.

The language of uncertainty

A random variable is a quantity whose value is uncertain, such as Hazard ∈ {yes, no}. A joint distribution gives the probability of every combination of values; summing out variables gives a marginal probability. The conditional probability of a given evidence b is

P(a | b) = P(a, b) / P(b)   ⇔   P(a, b) = P(a | b) · P(b)  (product rule)

Two variables are independent if P(a | b) = P(a): learning one tells you nothing about the other. They are conditionally independent given c if, once you know c, learning b adds nothing about a.

Bayes’ rule: turning evidence around

The sensor’s manual tells us P(ALARM | hazard). We want the opposite, P(hazard | ALARM). Bayes’ rule converts one into the other:

P(H | E) = P(E | H) · P(H) / P(E)    posterior = likelihood × prior / evidence

Here the prior P(H) is what we believed before the beep, the likelihood P(E | H) is how well the hypothesis explains the evidence, and the posterior P(H | E) is the updated belief.

Worked example

Hazards occur on 20% of trips: P(H) = 0.20. The sensor raises ALARM in 90% of hazards, P(A | H) = 0.90, and also in 10% of safe trips, P(A | ¬H) = 0.10.

P(A) = 0.90·0.20 + 0.10·0.80 = 0.18 + 0.08 = 0.26

P(H | A) = 0.18 / 0.26 = 9/13 ≈ 0.692  ·  P(H | NORMAL) = 0.02 / 0.74 = 1/37 ≈ 0.027

So the alarm raises the risk from 20% to about 69%, not to 90%. Think of 100 trips: 20 have a hazard and 18 of them beep; 80 are safe and 8 of them beep anyway. Of the 26 beeps, 18 are real. Ignoring the prior is called the base-rate fallacy; it is one of the most common reasoning mistakes, made even by doctors reading medical tests.

Bayesian networks

With many variables the full joint table explodes: n yes/no variables need 2ⁿ − 1 numbers. A Bayesian network is a directed acyclic graph in which each node is a variable and each arrow means “directly influences”. Each node stores a conditional probability table (CPT) given its parents, and the joint distribution factorizes:

P(x₁, …, xₙ) = Π_i P(xᵢ | parents(Xᵢ))

Inference by enumeration. To answer a query we sum the factorized joint over the unknown variables. Probability of an alarm:

P(Icy) = 0.3·0.7 + 0.7·0.1 = 0.28  ·  P(Alarm) = 0.28·0.9 + 0.72·0.05 = 0.288

Did it snow, given an alarm? P(Snow, Alarm) = 0.3 · (0.7·0.9 + 0.3·0.05) = 0.1935, so P(Snow | Alarm) = 0.1935 / 0.288 ≈ 0.672, up from the prior 0.30. The network also shows conditional independence: once Qadam knows the road is icy, the alarm says nothing more about the weather. Indeed P(Snow | Icy) = 0.21 / 0.28 = 0.75 whether or not the alarm rang.

Three building blocks. Every Bayesian network is built from three small patterns. In a chain A → B → C (like Figure 6.1) and in a fork A ← B → C (one cause with two effects), knowing B blocks the flow of information between A and C. A collider A → B ← C works the other way round: A and C are independent until B is observed. Suppose the slip alarm can be set off by ice or by a loose wheel. Hearing the alarm raises the probability of both causes; if the camera then shows ice, the probability of a loose wheel goes back down, because the ice already explains the alarm. This is called explaining away.

When enumeration is too slow. Enumeration repeats the same sums many times. Variable elimination computes each partial sum once and reuses it. For large networks even that can be too slow, so we sample. Prior sampling generates many random worlds from the CPTs and counts them; rejection sampling throws away the worlds that contradict the evidence; likelihood weighting fixes the evidence and weights each world by how likely that evidence is; Gibbs sampling repeatedly redraws one variable at a time given all the others. The more samples, the closer the estimate gets to the exact answer.

A famous special case is the naive Bayes classifier, which assumes all features are independent given the class. Despite that “naive” assumption it works well for spam filtering and text classification.

A model of time

A hidden Markov model (HMM) describes a system whose true hidden state Xₜ changes over time and is seen only through noisy observations (evidence) Eₜ. It rests on two assumptions:

• Markov assumption: the next state depends only on the current state, described by a transition model P(Xₜ | Xₜ₋₁).
• Sensor Markov assumption: each observation depends only on the current state, described by an emission (sensor) model P(Eₜ | Xₜ).

Four questions an HMM can answer

• Filtering: what is the state now? P(Xₜ | e₁:ₜ)
• Prediction: what will the state be later? P(Xₜ₊ₖ | e₁:ₜ)
• Smoothing: what was the state at an earlier time, using later evidence too?
• Most likely explanation: which whole sequence of states best explains the observations? Solved by the Viterbi algorithm.

The forward algorithm: predict, then update

Filtering is done recursively, one day at a time:

predict: P(Xₜ | e₁:ₜ₋₁) = Σ_xₜ₋₁ P(Xₜ | xₜ₋₁) · P(xₜ₋₁ | e₁:ₜ₋₁)

update: P(Xₜ | e₁:ₜ) = α · P(eₜ | Xₜ) · P(Xₜ | e₁:ₜ₋₁)   (α normalizes to 1)

Worked example: four days of storm

Same sensor as Chapter 6: P(ALARM | HAZARD) = 0.9, P(ALARM | SAFE) = 0.1. Hazards persist: P(HAZARD → HAZARD) = 0.8, P(SAFE → SAFE) = 0.9. Before day 1 the belief is the prior P(HAZARD) = 0.2. Day 1 in detail: predict 0.2·0.8 + 0.8·0.1 = 0.24; update 0.24·0.9 = 0.216 and 0.76·0.1 = 0.076; normalize 0.216 / 0.292 ≈ 0.740.

Notice day 4: a second alarm in a row pushes the belief to 93%, higher than any single alarm could (69% in Chapter 6), because the model knows hazards tend to persist. The Viterbi algorithm finds that the most likely full sequence is HAZARD, HAZARD, HAZARD, HAZARD: one silent day is more likely to be a sensor miss than a hazard that disappeared and came back. I confirmed this by checking all 16 possible sequences.

Rational decisions: maximum expected utility

A decision-making agent turns data into a prediction, the prediction into a value for each action, and the best value into an action. A utility U(o) is a number that says how much the agent values an outcome o. The expected utility of an action averages over its possible outcomes, given the evidence e:

EU(a | e) = Σ_o P(o | a, e) · U(o)     a* = argmax_a EU(a | e)

The principle of maximum expected utility (MEU) says that a rational agent chooses the action with the highest expected utility. Rationality is judged by the information available before acting. A good decision can still end badly through bad luck, and that does not make it irrational; rational does not mean all-knowing.

Worked example. Qadam’s sensors say the ice holds with probability 0.9. A fast, safe crossing is worth U = 100; breaking through is worth −500 (a lost robot and no medicine); the bridge is certain and worth 60.

EU(ice) = 0.9·100 + 0.1·(−500) = 40     EU(bridge) = 60

So Qadam takes the bridge, although the ice is “90% safe”. When failure is catastrophic, 90% is not enough. How sure would it need to be? The ice wins only if p·100 + (1 − p)·(−500) > 60, that is p > 560/600 ≈ 0.933.

Is it worth checking first? Suppose a thermal scan could tell Qadam for certain whether the ice will hold. Then it would cross when the ice holds (90% of the time, utility 100) and take the bridge otherwise (utility 60): 0.9·100 + 0.1·60 = 96. Without the scan the best it can do is 60. The difference, 96 − 60 = 36, is the value of perfect information: the scan is worth doing if it costs less than 36 utility points. Information has value only when it can change the decision.

Risk attitudes. MEU can prefer the riskier option. Project A pays 100 with probability 0.9 and −20 otherwise (EU = 88); project B pays 200 with probability 0.6 and −50 otherwise (EU = 100). A risk-neutral agent, whose utility is linear in money, picks B. A risk-averse agent has a concave utility, where each extra tenge matters a little less than the one before, and may prefer A. The attitude to risk lives in the utility function, not in the probabilities.

Thresholds come from costs. A factory machine will fail this week with probability p. Maintenance costs 2,000; a failure costs 10,000. Carrying on has an expected cost of p · 10,000, so maintenance is rational when p > 2,000 / 10,000 = 0.20. If the failure cost were 20,000 and p = 0.15, carrying on would cost 3,000 on average, more than the 2,000 for maintenance, so maintaining saves 1,000. The threshold is 0.20, not 0.5: it comes from the costs of the possible mistakes, not from accuracy. The same idea will set the alarm threshold of a classifier later in this chapter.

From writing rules to learning them

Decisions need probabilities, and probabilities need data. In classical programming a person writes the rules and the computer applies them. In machine learning (ML) we give the computer data together with the outcomes, and it produces the rule: a model ŷ = fθ(x) whose parameters θ are learned from examples.

What does “learning” mean?

Tom Mitchell’s classic definition: a program learns from experience E with respect to a task T and performance measure P if its performance at T, measured by P, improves with E. Three main kinds:

• Supervised learning: examples come with correct answers (labels). Predicting a category is classification; predicting a number is regression.
• Unsupervised learning: no labels; find structure, for example clustering similar trips together.
• Reinforcement learning: learn from rewards by acting (Chapter 5).

Each example is described by features (inputs such as weather or bridge type). We train on a training set and measure on a separate test set the model has never seen, because what matters is generalization to new cases, not memorizing old ones.

Most projects follow the same workflow: collect data, split it, fit a model on the training part, evaluate it on data it has never seen, and only then deploy it and keep monitoring it. The split must happen before anything is learned from the data. Data leakage is when information from the test set, or from the future, slips into training. A classic example is a “repair date” column that is filled in only after a machine has failed: the model learns to read it, looks brilliant in the lab and is useless in the factory.

Decision trees

A decision tree asks one question per node and gives an answer at each leaf. It is built top-down by choosing, at each node, the feature that best separates the classes. “Best” is measured with entropy, the uncertainty of a set of labels, and information gain, the drop in entropy after a split:

H(S) = − Σ pᵢ · log₂ pᵢ   ·   Gain(S, F) = H(S) − Σ_v (|Sᵥ| / |S|) · H(Sᵥ)

Worked example. Qadam’s notebook has 8 crossings: 5 “cross”, 3 “wait”, so H = 0.954 bits. Splitting on Weather gives Sunny (4 cross, 0 wait, H = 0) and Rainy (1 cross, 3 wait, H = 0.811): gain 0.954 − ½·0 − ½·0.811 = 0.549. Splitting on Bridge gives only 0.049. So the root asks about the weather.

Trees are easy to read, handle non-linear patterns and need little data preparation. A single tree is unstable, though: change a few examples and it may grow quite differently (high variance), and a deep tree overfits easily. A random forest trains many trees, each on a bootstrap sample of the rows (drawn with replacement) and with a random subset of the features at each split, and lets them vote (or averages them for regression). The forest is more accurate and much more stable than one tree, at the price of being harder to explain.

Other classic models

k-nearest neighbours (k-NN) stores all examples and labels a new case by majority vote of the k most similar ones. Linear regression fits a line ŷ = w·x + b by minimizing the mean squared error (MSE); if a campus building uses 5·temperature + 100 kWh, it predicts 250 kWh on a 30 °C day. Regression is judged with MAE, RMSE or R². Logistic regression passes the same weighted sum through the sigmoid function σ(z) = 1 / (1 + e−z) to output a probability between 0 and 1, and classifies with a threshold (often 0.5, but see below). For example σ(2) ≈ 0.881, σ(0) = 0.5 and σ(−2) ≈ 0.119. Its decision boundary is a straight line, which matters in Chapter 9.

Naive Bayes applies Bayes’ rule from Chapter 6 with a bold shortcut: it assumes the features are independent of each other once the class is known, and simply multiplies P(feature | class) terms. It is fast and works surprisingly well for text, for example spam filtering.

K-Means is unsupervised clustering. Choose K and place K centres; assign every point to its nearest centre; move each centre to the mean of its points; repeat until nothing changes. This reduces the within-cluster spread J = Σk Σx ∈ Ck ‖x − μk‖². Features must be on similar scales first, and a human still has to interpret what each cluster means.

Overfitting and underfitting

A model that is too simple misses real patterns (underfitting, high bias). A model that is too flexible memorizes noise in the training data and fails on new data (overfitting, high variance). Signs of overfitting: training accuracy near 100%, test accuracy much lower. Remedies: more data, simpler models, pruning trees, regularization, and cross-validation (rotating which part of the data is held out).

Good practice keeps three separate sets: a training set to fit the parameters, a validation set to choose the model and its threshold, and a test set used only once, at the very end. A model is calibrated if its probabilities mean what they say: of all the cases it scores 0.7, about 70% should really be positive. Calibration matters whenever probabilities feed an expected-utility decision. In the field two more risks appear: distribution shift (new data no longer looks like the training data, for example a new machine or a new season) and the leakage described above.

Measuring a classifier

Say the positive class is UNSTABLE ground, the dangerous case. A confusion matrix counts true positives (TP), false positives (FP), false negatives (FN) and true negatives (TN). From it:

accuracy = (TP+TN)/all · precision = TP/(TP+FP) · recall = TP/(TP+FN) · F1 = 2PR/(P+R)

Example on 100 surfaces: TP 18, FN 2, FP 6, TN 74 gives accuracy 0.92, precision 0.75, recall 0.90, F1 ≈ 0.818. For a robot the worst error is calling unstable ground stable (a false negative), so recall on the UNSTABLE class deserves the most attention, even at the cost of some false alarms. Accuracy alone can mislead when classes are imbalanced: a model that always says “stable” would be 80% accurate here and completely useless.

The same trap at factory scale: if only 2% of machines fail, a model that always answers “normal” is 98% accurate and catches no failure at all (recall 0). Between model A (accuracy 95%, recall 60%) and model B (accuracy 92%, recall 90%), B is the better choice for safety despite its lower accuracy. The threshold, too, is a decision rather than a property of the model. Combining this chapter’s two halves, flag a case as positive when P(positive) > CFP / (CFP + CFN), where CFP is the cost of a false alarm and CFN the cost of a miss. If a missed failure costs 9 times as much as a false alarm, the threshold is 1/10 = 0.1, far below 0.5.

The artificial neuron

An artificial neuron multiplies each input xᵢ by a weight wᵢ, adds a bias b, and passes the sum through an activation function:

z = w₁x₁ + w₂x₂ + … + wₙxₙ + b   ·   output = g(z)

Common activations: the step function (0 or 1), the sigmoid 1/(1+e−z) (between 0 and 1), tanh (between −1 and 1) and ReLU max(0, z), the default in modern deep networks. Example: inputs (0.8, 0.2), weights (1.5, −2.0), bias 0.1 give z = 1.2 − 0.4 + 0.1 = 0.9; sigmoid(0.9) ≈ 0.711, ReLU(0.9) = 0.9.

The perceptron, and the problem it could not solve

Frank Rosenblatt’s perceptron (1958) is one neuron with a step activation. It learns with a simple rule: after each example, nudge the weights toward the right answer,

wᵢ ← wᵢ + η · (y − ŷ) · xᵢ   ·   b ← b + η · (y − ŷ)

where η is the learning rate. Starting from zero weights with η = 1, a perceptron learns logical AND in 6 passes through the data (epochs), ending with w = (2, 1), b = −2. But a single perceptron draws one straight line, so it can only learn linearly separable patterns. XOR (“exactly one input is 1”) cannot be split by any single line. Minsky and Papert’s 1969 book made this limitation famous and slowed neural-network research for years.

Multilayer networks

The fix is to stack neurons in layers: an input layer, one or more hidden layers, and an output layer. This is a multilayer perceptron (MLP). Each hidden neuron draws its own line; the next layer combines them into curved, multi-part boundaries. With enough hidden units, a network with one hidden layer can approximate any continuous function on a bounded region (the universal approximation theorem), although finding the right weights is another matter.

How a network learns

1. Forward pass: compute outputs layer by layer.
2. Loss: measure the error with a loss function, for example mean squared error or cross-entropy for classification.
3. Backpropagation: use the chain rule of calculus to compute how much each weight contributed to the error (the gradient), from the output layer back to the input.
4. Gradient descent: move every weight a small step downhill, w ← w − η · ∂Loss/∂w (the same idea as Chapter 3, now in thousands of dimensions).

Settings chosen by the engineer rather than learned, such as the number of hidden units, the learning rate and the number of epochs, are hyperparameters. Too high a learning rate makes training jump around; too low makes it crawl. Large networks can overfit, so we use regularization: early stopping, weight penalties, or dropout (randomly switching off neurons during training).

Learning, memorizing or understanding? A student who memorizes the 18 answers of a practice test scores 18/18 on it and 2/6 on new questions. Networks can do the same. Model A reaches 98% on its training data but 65% on the test set: it memorized. Model B reaches 91% and 89%: it generalized, and it is the one to deploy. That is why we keep a validation set (to tune hyperparameters and decide when to stop) and a test set (for the final, honest score), and watch the loss curves: when validation loss starts rising while training loss keeps falling, the network has begun to memorize. Even a high test score shows only that the model found useful patterns, not that it understands the world.

Network or tree? In the lecture’s robot example a decision tree reaches 82% accuracy (F1 0.79) and trains in about a second, while a small neural network reaches 88% (F1 0.86) but trains for about 12 seconds and is much harder to explain. The choice depends on the cost of each error (calling an unstable surface stable is dangerous, the reverse is only a false alarm), on the need for explanations and on the data available. For images, convolutional neural networks (Chapter 10) learn their own feature maps and beat hand-made features.

Deep learning

Deep learning means neural networks with many layers trained on large datasets. Each layer learns a more abstract representation: for a photo, early layers detect edges, middle layers shapes, late layers whole objects. Nobody hand-designs these features; they are learned. The breakthrough moment was 2012, when the AlexNet network, trained on GPUs, won the ImageNet image-recognition challenge by a wide margin.

• Convolutional neural networks (CNNs) slide small learned filters across an image, reusing the same weights everywhere. They power image recognition, medical imaging and the camera systems of self-driving cars.
• Transformers (2017) process sequences with attention: every word looks at every other word and decides how much each one matters for its meaning. They replaced older recurrent networks for language.

How a large language model works

A large language model (LLM) is a transformer with billions of weights, trained to do one simple-sounding job: predict the next token. Four ideas explain most of what it does.

• Tokens and embeddings. Text is cut into tokens, whole words or pieces of words. Each token becomes a long vector of numbers, its embedding, and words with similar meanings end up with nearby vectors.
• Attention. In “Qadam gave Aru the map because she asked for it”, the model must link “she” to Aru and “it” to the map. Self-attention lets every token weigh every earlier token and mix in information from the ones that matter. Many attention layers stacked together build up meaning.
• Pretraining, then fine-tuning. In pretraining the model reads a huge amount of text and learns P(next token | all previous tokens); grammar, facts and styles are side effects of getting that prediction right. A pretrained model only continues text. Fine-tuning on example dialogues and reinforcement learning from human feedback (RLHF) turn it into an assistant: people rank several answers, a reward model learns their preferences, and RL (Chapter 5) pushes the LLM toward the preferred answers.
• Sampling, temperature and context. The model outputs a probability for every possible next token, picks one, appends it and repeats. The temperature works like the one in simulated annealing (Chapter 3): low temperature almost always picks the most likely token, high temperature gives more varied and more surprising text. The model can only use what fits in its context window, the prompt plus the conversation so far, besides what it absorbed in training.

Generative AI beyond text

Generative AI means models that create new content (text, images, audio, video, code) instead of only labelling it. LLMs generate text token by token. Most image generators are diffusion models: during training they learn to remove a little noise from a noisy picture; to create an image they start from pure random noise and remove it step by step, guided by the text prompt, until a picture appears that matches the description. The same results can help a designer, or produce a convincing deepfake of a real person. This is why synthetic content should be labelled.

Hallucination, and how to keep a model honest

An LLM produces the most plausible continuation, not a checked fact, so it can state false things fluently, including invented quotes and references. This is called hallucination. It can be reduced but not switched off: grounding the model in real documents placed into its context (retrieval-augmented generation, RAG), asking for sources and actually opening them, using a low temperature for factual tasks, and having a person check anything that matters. That is how this book was checked: every number in it was recomputed with separate Python code.

AI safety

AI safety asks how to make AI systems do what people intend, reliably, without causing harm. Its main questions:

• Alignment: does the system pursue the goal we meant, or only the one we wrote down? Reward hacking in Chapter 5 is a small example of misalignment.
• Robustness: does it still work on unusual inputs and under attack? Tiny, invisible pixel changes can fool an image classifier (adversarial examples), and text hidden in a web page or a document can hijack an LLM assistant that reads it (prompt injection).
• Misuse: deepfakes, fraud, disinformation and help for cyberattacks.
• Fairness: models learn the bias in their data. A hiring model trained on past decisions can repeat past discrimination.
• Privacy: training and using AI must respect personal-data law; never paste confidential data into a public chatbot.
• Transparency and accountability: people should know when AI is used and get an explanation of decisions that affect them, and a person or an organization, never “the algorithm”, is responsible for what the system does.
• Human oversight: a person must be able to intervene, correct or stop the system.

AI with a body. When AI controls a robot, a car or a factory machine, a mistake is no longer a wrong sentence but a physical event. Physical AI therefore combines everything in this book with engineering caution: hard safety limits that sit outside the learned model (Chapter 5), calibrated probabilities and cost-based thresholds (Chapter 8), testing in simulation before the real world, and autonomy that grows step by step, with a human able to take over. A language model can plan a robot’s task in words, but it should not be the last line of defence.

Kazakhstan’s Law on Artificial Intelligence

Kazakhstan adopted a dedicated Law on Artificial Intelligence (No. 230-VIII, 17 November 2025). As presented in our course, it puts human welfare, fairness, transparency, accountability, privacy, safety and security at the centre; classifies AI systems by risk (minimal, medium, high) and separately by autonomy (low, medium and high, from “AI recommends, a person decides” to systems a person cannot correct); prohibits manipulative AI that distorts people’s behaviour or limits informed choice; requires people to be told when goods or services are produced with AI and synthetic results to be labelled; and protects as a work only what has a creative human contribution. This summary is for learning, not legal advice; the official text is on the Adilet legal portal.

Epilogue

Qadam’s graduation

Here is how the ten steps fit together. The same agent asks different questions depending on what it knows about its world:

Milestones of AI

• 1763Bayes’ essay on inverse probability is published (Ch. 6).
• 1944Von Neumann and Morgenstern’s Theory of Games and Economic Behavior lays the foundations of game theory and utility theory (Ch. 4, 8).
• 1950Alan Turing proposes the imitation game, the “Turing test” (Ch. 1). Shannon estimates the size of chess (Ch. 4).
• 1956The Dartmouth workshop gives the field its name, “artificial intelligence”.
• 1957Bellman’s Dynamic Programming (Ch. 5).
• 1958Rosenblatt’s perceptron (Ch. 9).
• 1959Dijkstra’s shortest-path algorithm, the ancestor of UCS (Ch. 2).
• 1967Viterbi’s decoding algorithm (Ch. 7); MacQueen names the k-means method (Ch. 8).
• 1968A* is published for the Shakey robot (Ch. 2).
• 1969Minsky and Papert show the limits of single-layer perceptrons (Ch. 9).
• 1977Mackworth formalizes arc consistency for constraint networks (Ch. 3).
• 1983Simulated annealing is introduced for optimization (Ch. 3).
• 1986Backpropagation is popularized (Ch. 9).
• 1988Pearl’s book on probabilistic reasoning and Bayesian networks (Ch. 6).
• 1989Watkins introduces Q-learning (Ch. 5).
• 1997Deep Blue defeats Kasparov (Ch. 4).
• 2001Breiman introduces random forests (Ch. 8).
• 2012AlexNet starts the deep-learning boom (Ch. 10).
• 2015A deep Q-network learns dozens of Atari games from pixels (Ch. 5).
• 2016AlphaGo defeats Lee Sedol (Ch. 4).
• 2017The transformer architecture: “Attention Is All You Need” (Ch. 10).
• 2020Denoising diffusion models start the boom in image generation (Ch. 10).
• 2022Instruction tuning with human feedback (RLHF), and ChatGPT brings large language models to the public (Ch. 10).
• 2025Kazakhstan adopts its Law on Artificial Intelligence (Ch. 10).

AI vs human: who is better at what?

Sources and further reading

1. QAIRU, AIF1303 AI Fundamentals: lecture slides for Weeks 1–9, practical guides, the AI legal-framework lecture and the course syllabus (lecturer Aizhan Sydykova), 2026.
2. Zerilli, J., Danaher, J., Maclaurin, J., Gavaghan, C., Knott, A., Liddicoat, J., & Noorman, M. (2021). A Citizen’s Guide to Artificial Intelligence. MIT Press.
3. Louwerse, M. M. (2025). Understanding Artificial Minds through Human Minds. Routledge.
4. von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press.
5. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
6. UC Berkeley CS188, Introduction to Artificial Intelligence, course notes. inst.eecs.berkeley.edu/~cs188
7. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
8. Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99–118.
9. Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. (1992). Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58(1–3), 161–205.
10. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680.
11. Bellman, R. (1957). Dynamic Programming. Princeton University Press.
12. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
13. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8, 279–292.
14. Mnih, V., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518, 529–533.
15. Clark, J., & Amodei, D. (2016). Faulty reward functions in the wild. OpenAI blog.
16. Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann.
17. Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257–286.
18. Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
19. MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
20. Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32.
21. Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408.
22. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323, 533–536.
23. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press. deeplearningbook.org
24. Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). ImageNet classification with deep convolutional neural networks. NeurIPS 25.
25. Vaswani, A., et al. (2017). Attention is all you need. NeurIPS 30.
26. Ho, J., Jain, A., & Abbeel, P. (2020). Denoising diffusion probabilistic models. NeurIPS 33.
27. Ouyang, L., et al. (2022). Training language models to follow instructions with human feedback. NeurIPS 35.
28. Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., & Mané, D. (2016). Concrete problems in AI safety. arXiv:1606.06565.
29. Silver, D., et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529, 484–489.
30. Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59(236), 433–460.
31. Law of the Republic of Kazakhstan “On Artificial Intelligence” No. 230-VIII ZRK, 17 November 2025. Adilet legal information system. adilet.zan.kz

How this book was made

Format. A single-page interactive HTML book: one story, ten chapters (one per course week), ten browser labs, chapter quizzes, a glossary and this declaration. Nothing needs to be installed, and it works on a phone. The illustrations are drawn as SVG code; no photographs or image-generator pictures are used.

Use of generative AI. Following the AI Use Declaration Form of the course syllabus, and in the spirit of the labelling principle of Kazakhstan’s AI Law (Chapter 10), here is exactly how AI was used.

About the author

Madaminov Salmankhoja studies at QAIRU (Stream 1, practice group 2). QADAM is the author’s EndTerm creative project for AI Fundamentals (AIF1303), autumn 2026: lectures by Aizhan Sydykova, practice classes by Dilnura Ali. The robot-on-the-steppe story continues the robot theme of the author’s midterm project “Rescue Agent”.