Many AI problems are really search problems. The agent starts in some situation. It wants to reach a goal. At each step it can take some actions. Search means: try actions in a smart order until you find a path to the goal.

State space

The state space is the set of all possible situations (states) the problem can be in. Think of it as a big graph:

• Each node = one state.
• Each edge = one action that moves you from one state to another.
• Searching = finding a path from the initial state to a goal state in this graph.

Problem formulation (5 parts)

To define a search problem formally, we give five things:

1. Initial state — where we start.
2. Actions — what moves are allowed in each state.
3. Transition model — the result of doing an action in a state.
4. Goal test — a check: "is this state a goal?"
5. Path cost — the total cost of a path (often the sum of step costs).

Uninformed (blind) search

Uninformed search means the algorithm knows nothing extra about the problem. It only knows the graph structure. It cannot guess which state is "closer" to the goal. The main uninformed strategies:

• BFS (Breadth-First Search): expand the shallowest node first. Uses a queue (FIFO). Explores level by level.
• DFS (Depth-First Search): expand the deepest node first. Uses a stack (LIFO) or recursion. Goes deep down one branch before backing up.
• UCS (Uniform-Cost Search): expand the node with the lowest path cost \( g(n) \) first. Uses a priority queue. It is Dijkstra's algorithm used for search.
• DLS (Depth-Limited Search): DFS, but stop going deeper after a fixed depth limit \( \ell \). This avoids DFS getting lost in infinite paths.
• IDS (Iterative Deepening Search): run DLS with limit 0, then 1, then 2, ... until the goal is found. It combines BFS's completeness with DFS's low memory. Repeating shallow levels sounds wasteful, but the top levels are small, so the extra work is minor.

Here \( b \) = branching factor (children per node), \( d \) = depth of the shallowest goal, \( m \) = maximum depth, \( \ell \) = depth limit, \( C^* \) = optimal cost, \( \epsilon \) = smallest step cost.

Uninformed search is blind. Informed (heuristic) search uses extra knowledge to guess which node looks promising. That guess is called a heuristic.

What is a heuristic?

A heuristic function \( h(n) \) is an estimate of the cost from node \( n \) to the goal. It is cheap to compute and usually not exact. A good heuristic makes search much faster because we expand fewer useless nodes.

Admissible and consistent heuristics

• Admissible: \( h(n) \) never overestimates the true cost to the goal. Formally \( h(n) \le h^*(n) \) for all \( n \), where \( h^*(n) \) is the true optimal cost. Admissible = "optimistic".
• Consistent (monotone): for every node \( n \) and its child \( n' \) reached by an action with cost \( c \): \( h(n) \le c + h(n') \). It is a triangle-inequality condition. Every consistent heuristic is also admissible (the reverse is not always true).

Greedy best-first search

Greedy best-first always expands the node with the smallest \( h(n) \) — the one that looks closest to the goal. It is fast but not optimal and can even loop. It ignores the cost already paid.

A* search (the star of the exam)

A* fixes greedy's mistake. For each node it uses:

Hill climbing and the local maximum problem

Hill climbing is a local search: from the current state, move to the best neighbor; repeat; stop when no neighbor is better. It uses almost no memory. But it can get stuck:

• Local maximum: a peak that is better than its neighbors but worse than the global best. Hill climbing stops there.
• Plateau: a flat area — no neighbor is better, so the search wanders or halts.
• Ridge: a narrow high path where every single move looks downhill.

Fixes: random restarts (run again from random starts), or simulated annealing (sometimes accept a worse move with a probability that shrinks over time).

BUET (April 2024) directly asked the difference between these two families. Learn it as two ideas:

• Heuristic search uses domain knowledge: a heuristic estimate \( h(n) \) of "how close is this node to the goal". The estimate guides a deterministic exploration — run it twice on the same input and you get the same node order. Examples: A*, greedy best-first search, hill climbing.
• Probabilistic (stochastic) search uses randomness as its main tool. It makes random moves, random restarts, or accepts worse states with some probability. The randomness lets it escape local optima and explore parts of the space a greedy climber would never visit. Two runs can give different answers. Examples: simulated annealing, genetic algorithms, random-restart hill climbing, Monte Carlo methods.

They are not enemies — simulated annealing still uses the objective value like a heuristic, but it adds randomness on top so it does not get stuck.

Minimax for games

In a two-player game (chess, tic-tac-toe), my opponent works against me. Minimax assumes both players play perfectly:

• MAX (me) picks the child with the largest value.
• MIN (opponent) picks the child with the smallest value.
• Leaf values come from a utility/evaluation function. Values flow up the tree.

An intelligent agent needs to store what it knows and reason with it (derive new facts). Knowledge representation is about how to write knowledge so a computer can use it.

Logic for KR

Propositional logic: the world is described by simple true/false statements (propositions) joined by connectives:

• \( \neg \) (NOT), \( \wedge \) (AND), \( \vee \) (OR), \( \rightarrow \) (implies), \( \leftrightarrow \) (if and only if).
• Example: \( Rain \rightarrow WetRoad \) means "if it rains, the road is wet."

First-order logic (FOL): more powerful. It adds objects, relations, functions, and quantifiers:

• \( \forall \) = "for all", \( \exists \) = "there exists".
• \( \forall x \; Human(x) \rightarrow Mortal(x) \) — "all humans are mortal."
• \( Human(Socrates) \) is a fact. From the rule + fact, we can infer \( Mortal(Socrates) \).

A knowledge base (KB) is a set of such facts (known truths) and rules (if–then statements). An inference engine applies rules to facts to produce new facts. The key inference rule is Modus Ponens: from \( P \) and \( P \rightarrow Q \), conclude \( Q \).

Forward chaining vs backward chaining

• Forward chaining (data-driven): start from known facts. Fire every rule whose conditions are satisfied. Add the new facts. Repeat until the goal appears (or nothing new is produced). "From facts, move forward to conclusions."
• Backward chaining (goal-driven): start from the goal. Ask: which rule can conclude this goal? Then try to prove that rule's conditions as sub-goals. Recurse down to known facts. "From the goal, move backward to facts." Prolog works this way.

Other KR methods

• Semantic network: a graph of concepts. Nodes = objects/concepts, labeled edges = relations. Common links: is-a (Sparrow is-a Bird), has-a (Bird has-a Wings). Properties can be inherited down is-a links: Sparrow inherits "can fly" from Bird.
• Frames: a record-like structure for one concept, with slots (attributes) and fillers (values or defaults). Example: frame Bird with slots legs: 2, flies: yes. Frames are basically the ancestor of objects/classes in OOP.
• Ontology: a formal, agreed vocabulary of the concepts in a domain and the relations between them (a shared "map of meaning").

Rule-based expert systems

An expert system tries to act like a human expert in a narrow field (medical diagnosis, machine troubleshooting). Its parts:

• Knowledge base: if–then rules collected from experts.
• Inference engine: applies rules (forward or backward chaining).
• Working memory: the current known facts of a session.
• User interface and an explanation facility ("why did you conclude this?").

Famous classic example: MYCIN, which suggested antibiotics for blood infections using about 600 rules.

Machine Learning (ML) means: instead of writing rules by hand, we show the computer data and let it learn patterns from the data. AI, ML, and Deep Learning fit inside each other:

• AI: the big field — making machines act intelligently (search, logic, planning, learning, everything).
• ML: a part of AI — systems that improve from data/experience.
• Deep Learning (DL): a part of ML — learning with many-layered neural networks.

Dataset words you must know

• Feature: one input property of an example (age, size, pixel value). A row's features form the input vector \( x \).
• Label (target): the correct answer \( y \) for that example (e.g., "spam" / "not spam", or a price).
• Training set: data used to fit the model (commonly ~60–80%).
• Validation set: data used to tune choices (hyperparameters, which model). The model does not train on it.
• Test set: kept locked until the very end; used once to report the final honest performance.

Overfitting vs underfitting

• Underfitting: the model is too simple. It does badly on training data and new data. (High bias.)
• Overfitting: the model is too complex. It memorizes the training data — great training accuracy, bad accuracy on new (test) data. (High variance.)
• Good fit: in between — learns the true pattern, ignores the noise.

Bias–variance idea

Prediction error has two main parts:

• Bias: error from wrong assumptions — the model is too simple to capture the truth. High bias → underfitting.
• Variance: error from being too sensitive to the particular training sample — the model changes a lot if the data changes slightly. High variance → overfitting.

There is a trade-off: making a model more complex lowers bias but raises variance. We want the sweet spot in the middle.

Cross-validation

k-fold cross-validation: split the data into \( k \) equal folds (say \( k = 5 \)). Train on \( k-1 \) folds, test on the remaining fold. Repeat \( k \) times so every fold is the test fold once. Average the \( k \) scores. This gives a more reliable estimate than one single split, especially with small datasets.

For a two-class problem (Positive / Negative), the confusion matrix counts four outcomes:

• TP (True Positive): actually positive, predicted positive. ✔
• TN (True Negative): actually negative, predicted negative. ✔
• FP (False Positive): actually negative, but predicted positive. ("false alarm", Type I error)
• FN (False Negative): actually positive, but predicted negative. ("missed case", Type II error)

Both are supervised learning. The difference is the type of output:

• Regression: predict a continuous number (house price, temperature).
• Classification: predict a category (spam / not spam, digit 0–9).

Linear regression

We assume the output is roughly a straight-line function of the input:

Logistic regression + sigmoid

Despite the name, logistic regression is a classification method. It computes \( z = wx + b \), then squashes \( z \) into a probability between 0 and 1 using the sigmoid function:

K-Nearest Neighbors (KNN)

KNN is a lazy, simple classifier: to classify a new point, find the \( K \) closest training points (usually Euclidean distance) and take a majority vote of their classes. No real "training" happens — the data itself is the model. Choose odd \( K \) to avoid ties.

Decision trees: entropy & information gain

A decision tree asks feature questions ("Is Wind = Strong?") and splits the data at each node. Which feature to split on first? The one with the highest information gain. First we need entropy — a measure of impurity/uncertainty of a set \( S \):

Naive Bayes

Naive Bayes uses Bayes' theorem with one big ("naive") assumption: features are independent given the class.

SVM idea: margin and hyperplane

A Support Vector Machine separates two classes with a hyperplane (a line in 2D, a plane in 3D). Among all separating lines, SVM picks the one with the maximum margin — the widest gap between the line and the nearest points of each class. Those nearest points are the support vectors; only they decide the boundary. For data that is not linearly separable, the kernel trick maps points to a higher dimension where a line can separate them.

Perceptron and neural network basics

A perceptron is the simplest artificial neuron:

1. Multiply each input by a weight: \( z = w_1 x_1 + w_2 x_2 + \dots + b \).
2. Pass \( z \) through an activation function (step, sigmoid, or ReLU \( = \max(0, z) \)).
3. Output the result.

A single perceptron can only learn linearly separable functions — famously, it cannot learn XOR. Stacking neurons in layers (input → hidden → output) gives a neural network, which can learn XOR and much more. Training uses backpropagation: compute the output error, send it backwards through the layers using the chain rule, and adjust every weight a little in the direction that reduces the error (gradient descent): \( w \leftarrow w - \eta \frac{\partial E}{\partial w} \), where \( \eta \) is the learning rate.

Quick recap: supervised learning has labels; unsupervised learning does not. Clustering is the main unsupervised task: group similar points together without being told any classes. The algorithm invents the groups itself.

K-means clustering

K-means groups \( n \) points into \( K \) clusters. Steps:

1. Choose K and pick \( K \) initial centroids (cluster centers), often random points.
2. Assignment step: assign every point to its nearest centroid (Euclidean distance).
3. Update step: move each centroid to the mean of the points assigned to it.
4. Repeat steps 2–3 until assignments stop changing (convergence).

K-means minimizes the total within-cluster squared distance: \( \sum_k \sum_{x \in C_k} \lVert x - \mu_k \rVert^2 \). It always converges, but possibly to a local optimum — so people run it several times with different starts.

Choosing K: the elbow method

Run K-means for K = 1, 2, 3, ... and plot the total within-cluster squared distance (WCSS/inertia) against K. The curve always goes down, but at some K it stops dropping fast and bends like an elbow. Pick that K — after the elbow, extra clusters buy little improvement.

Hierarchical clustering & dendrogram

Agglomerative (bottom-up) hierarchical clustering: start with every point as its own cluster; repeatedly merge the two closest clusters; stop when one cluster remains. The merge history is drawn as a tree called a dendrogram — the height of each merge shows how far apart the merged clusters were. Cutting the dendrogram at some height gives the clusters, so you do not need to fix K in advance. Cluster-to-cluster distance can be measured by single linkage (closest pair), complete linkage (farthest pair), or average linkage.