Chapter 6: Machine Learning

09/22/2025 INTRODUCTION TO AI 1
Outline
• Introduction
• Supervised Learning
◦ Classification Problem
◦ Classification by Similarity - Nearest neighbor Algorithm (k-NN)
◦ Classification by Boundary-Decision (Perceptron Algorithm, SVM)
• Unsupervised Learning
◦ Clustering Problem
◦ K-mean Algorithm
• Reinforcement Learning
◦ Q-Learning Algorithm
09/22/2025 INTRODUCTION TO AI 2
Problem Solving through Learning
So far in this class … An AI solves
problems following general approaches
◦ Generate and Test
◦ Problem Reduction
◦ Knowledge (logic)
◦ search algorithm
This topic is about solving problems
through Learning
◦ Machine Learning: Let the computer learn
from provided data or feedback, rather than
giving explicit instructions
◦ Similar to how a human learns to perform
tasks

09/22/2025 INTRODUCTION TO AI 3
AI and Machine Learning

[Link]

09/22/2025 INTRODUCTION TO AI 4
Machine Learning Approaches
• Machine learning main approaches:
◦ Supervised learning: The computer is presented with example inputs
and their desired outputs, and the goal is to learn a general
function/model that maps any input to the correct output.
◦ Unsupervised learning: No labels are given to the learning algorithm,
leaving it on its own to find structure in its input.
◦ discovering hidden patterns in data
◦ Reinforcement learning: A computer program interacts with a dynamic
environment in which it must perform a certain goal (such as driving a
vehicle or playing a game against an opponent). As it navigates its
problem space, the program is provided feedback that's analogous to
rewards, which it tries to maximize.
09/22/2025 INTRODUCTION TO AI 5
Typical Problems for ML?
Classification:
Predict a class label for an input

Reinforcement Learning

09/22/2025 INTRODUCTION TO AI 6
 Supervised
Learning (SL)

09/22/2025 INTRODUCTION TO AI 7
Supervised Learning
Learn how
Dataset
inputs are
(input-output)
mapped to
examples
output

• Given a dataset of input-output pairs, learn a function or model to

map inputs to outputs
• Examples: handwritten numbers recognition
◦ Dataset contains examples of how each
number is written.

09/22/2025 INTRODUCTION TO AI 8
Supervised Learning - Classification
• Classification is one of the most important problems solved by SL.
• The computer learns to classify things into categories based on
given examples
◦ Similar to how students learn from solved examples.
• Specifically, classification is a supervised learning task of learning a
function/model that maps an input point to a discrete category
◦ Such function/model is also called a classifier

09/22/2025 INTRODUCTION TO AI 9
Supervised Learning - Classification
• Example: Predicting Weather
◦ Is it going to rain tomorrow or not?
◦ Can you tell based on historical data?
◦ Given labeled data pairs of [temperature,
humidity, ..] <-> rain or not
◦ Can you come up with a Function/Model to
predict the weather?
◦ Predict = classify a certain day into raining or not raining
◦ Question: how many classes are there in this
example?
09/22/2025 INTRODUCTION TO AI 10
Classification Example – Predicting Weather
features label/class

• Supervised learning:
◦ Computer learns from given data instances in the form of (features, class)
◦ Come up with an estimate of function f(humidity, pressure) = class
◦ f(93, 999.7) = Rain, f(49, 1015.5) = No Rain , …etc.

09/22/2025 INTRODUCTION TO AI 11
Classification Example – Predicting Weather
Towards predicting weather
◦ Plot the data
◦ Each point represents the (humidity,
pressure) of a given day
◦ Points colored either
◦ Blue if that day was rainy, or
◦ Red if the day was not rainy.

Questions:
◦ Plot is 2-D - why? Rain
No Rain
◦ What if there are more classes?
◦ What if there are more features?
09/22/2025 INTRODUCTION TO AI 12
Classification Example – Predicting Weather
Classification Problem
◦ Given a new data point without a
known class
◦ What is the class of the new point?
◦ Goal: Training the computer to do
classification automatically
?

Example:
◦ What is the class of the shown new
data point (white)? Rain or No Rain? Rain
No Rain
◦ Why?
◦ What approach would you use?
09/22/2025 INTRODUCTION TO AI 13
Classification Approaches
Classification By Similarity
◦ Nearest Neighbor Algorithm (NN)
◦ Classify a new point based on the class of
its nearest neighbor

Example: ?
◦ The new point is classified as blue
(Rain).
◦ Its nearest neighbor is a blue point
Rain
No Rain

09/22/2025 INTRODUCTION TO AI 14
Classification Approaches
Classification By Similarity
◦ Nearest Neighbor Algorithm (NN)
◦ Classify a new point based on the class of
its nearest neighbor
?

Example:
◦ How about the new shown point?

Rain
No Rain

09/22/2025 INTRODUCTION TO AI 15
Classification Approaches
Classification By Similarity
◦ Nearest Neighbor Algorithm (NN)
◦ Classify a new point based on the class of
its nearest neighbor
?

Example:
◦ How about the new shown point?
◦ The new point is classified as red (No
Rain).
◦ Its nearest neighbor is a red point Rain
No Rain

09/22/2025 INTRODUCTION TO AI 16
Classification Approaches
Classification By Similarity
◦ Nearest Neighbor Algorithm (NN)
◦ Classify a new point based on the class of
its nearest neighbor ?

Example:
◦ How about the new shown point?
◦ Is it blue (Rain) or red (No Rain)?

Rain
No Rain

09/22/2025 INTRODUCTION TO AI 17
Classification Approaches
Classification By Similarity
◦ k-Nearest Neighbor Algorithm (NN)
◦ Classify based on k nearest neighbors
?

◦ Shown example – classification based

on 3 nearest neighbors
◦ Question: What is the class? Is it Red
or Blue?

Rain
No Rain

09/22/2025 INTRODUCTION TO AI 18
k-Nearest Neighbor Algorithm (k-NN) Euclidean distance as a
measure of similarity
Measuring Similarity
◦ k-NN requires a function to calculate
the similarity between any two points
◦ Needs to find the nearest neighbors ?
of a given unclassified point

Euclidean distance

Rain
No Rain

09/22/2025 INTRODUCTION TO AI 19
k-Nearest Neighbor Algorithm (k-NN) Euclidean distance as a
measure of similarity
Euclidean distance

◦ Example (2-D): Find the distance

between and 

Rain
No Rain

09/22/2025 INTRODUCTION TO AI 20
k-Nearest Neighbor Algorithm (k-NN) - Example
Worked Example: Given the following 4 labeled x2

data points:
7 ?
 with some class labeled as “Bad” 6
 with some class labeled as “Bad”
 with some class labeled as “Good” 5

 with some class labeled as “Good” 4

classify a new data point if the coordinates of
the new point is (3,7) using 3-NN and using 3
Euclidean distance as the measure of similarity.
2

x1
1 2 3 4 5 6 7

Class Bad Class Good ? Unknown Class

09/22/2025 INTRODUCTION TO AI 21
 Euclidean distance as a
k-Nearest Neighbor Algorithm (k-NN)measure
- Example
of similarity

√
𝑛
Worked Example: Given the following 4 labeled data points,
classify (3,7) using K-NN.
𝑑 ( 𝐱 , 𝐲 )= ∑ ( 𝑦𝑖 −𝑥𝑖) 2

𝑖=1

Euclidean distance to Rank minimum Is it included Y= category of

X1 X2 Y query instance (3,7) distance in 3-NN nearest neighbour
7 7 Bad √(7-3)^2+(7-7)^2=4 3 yes Bad
7 4 Bad √(7-3)^2+(4-7)^2=5 4 no -
3 4 Good √(3-3)^2+(4-7)^2=3 1 yes Good
1 4 Good √(1-3)^2+(4-7)^2=3.6 2 yes Good
We have 2 good and 1 bad then we conclude that the new sample is included in Good
3 7 ? category
Instance
Query

09/22/2025 INTRODUCTION TO AI 22
Nearest-Neighbor (k-NN) Dot product as a
measure of similarity
• Nearest neighbor for digits images:
◦ Take new image 0
◦ Compare to all training images
◦ Assign based on closest example 1
• Encoding: image is vector of intensities:
2
◦ The intensities range from 0 to 1, where 0 represents white
and 1 represents black.
0
• What’s the similarity function?
◦ Dot product of two images vectors?
1

09/22/2025 INTRODUCTION TO AI 23
Nearest-Neighbor (k-NN) Dot product as a
measure of similarity

• What’s the similarity function?

◦ Dot product of two images vectors?

• Usually vectors are normalized; For a vector  , where denotes

the magnitude of the vector , where , i.e. the square root of the
dot product of x with itself.
Note that in general that can be
◦ min = 0 (when?), max = 1 (when?) between -1 and +1 when ; but it is
◦ The dot product calculation is straightforward (the simplest) — and between 0 and +1 when all
components of and are positive, as
this gives us benefits in terms of computation time it is the case for the example of
pixel intensity.

09/22/2025 INTRODUCTION TO AI 24
k-Nearest Neighbor Algorithm (k-NN)
• Pros
◦ Simple algorithm to implement
◦ Does not require training a model apriori
• Cons
◦ Slow in classifying a new point
◦ requires measuring distances to every training example
◦ Not efficient with high dimensional data
• k-NN Demo
◦ [Link]
active-example/
09/22/2025 INTRODUCTION TO AI 25
Other Classification Approaches
So far …
◦ Classification was done by comparing
a new point to its neighbors using the
k-NN Algorithm

◦ Are there other approaches?

Rain
No Rain

09/22/2025 INTRODUCTION TO AI 26
Other Classification Approaches
Classification By creating Decision
Boundary between classes
◦ A new point is classified based on where
it falls relative to a decision boundary
?
Example (Weather):
◦ The yellow line represents one possible
?
decision boundary
◦ separates rainy days from non-rainy days
◦ Blue (Rain) points below the line
◦ Red (No Rain) points above the line Rain
◦ What is the class of the shown new No Rain
points?
09/22/2025 INTRODUCTION TO AI 27
Other Classification Approaches
Classification By creating Decision
Boundary between classes
◦ Several algorithms can be used to find the
best decision boundary
◦ decision boundary in 2-D is a line, in 3-D,
is a plane, and in n-D, is a hyperplane
◦ Caveat: data points may not be
completely separable
◦ In general, goal is to find the best possible
decision boundary
◦ Need to compare different possible decision
Rain
boundaries No Rain
◦ Question: Is the shown line the best one?
Why?
09/22/2025 INTRODUCTION TO AI 28
Decision Boundary – Perceptron Algorithm
𝑤0 + 𝑤1 𝑥 1+ 𝑤2 𝑥 2=0
Finding the best Decision
Boundary
◦ Let’s consider the 2-D case
◦ The decision boundary is a line

𝑥2
h ( 𝑥 1 , 𝑥 2 )= {
N o Rain 𝑤 0 +𝑤1 𝑥 1 +𝑤2 𝑥 2 ≥ 0
Rain otherwise
𝑥1
Rain
◦ Different weights give different lines No Rain
◦ How to find the best line?

09/22/2025 INTRODUCTION TO AI 29
Decision Boundary – Perceptron Algorithm
𝑤0 + 𝑤1 𝑥 1+ 𝑤2 𝑥 2=0
Finding the best Decision
Boundary
◦ Using vector notation
◦ Using 1 for No Rain, 0 for Rain

𝑥2
𝑥1
Rain
No Rain

09/22/2025 INTRODUCTION TO AI 30
Decision Boundary – Perceptron Algorithm
𝑤0 + 𝑤1 𝑥 1+ 𝑤2 𝑥 2=0
Finding the best Decision
Boundary
◦ More compact vector form

𝑥2
𝑥1
Rain
No Rain

09/22/2025 INTRODUCTION TO AI 31
Decision Boundary – Perceptron Algorithm

◦ For

𝑥2
◦ (1, pressure, humidity) – data point
◦ Note , pressure, humidity 𝑥1
◦ 1 or 0 – class Rain
No Rain
◦ : learning rate – controls weight
updates
09/22/2025 INTRODUCTION TO AI 32
Decision Boundary – Perceptron Algorithm

◦ If actual value > estimate, weight

update is positive
◦ Increase estimate
◦ If actual value < estimate, weight
update is negative Rain
◦ decrease estimate No Rain

09/22/2025 INTRODUCTION TO AI 33
Decision Boundary – Perceptron Algorithm

Step 1 Step 2 Step 3 Step 4 Step 5

09/22/2025 INTRODUCTION TO AI 34
Perceptron Learning Algorithm
• Find the hyperplane that perfectly separates the two groups of
points
• Note that is a vector that is orthogonal to the hyperplane

Note that is the dot product

where is the angle between

𝐖 vectors and .

09/22/2025 INTRODUCTION TO AI 35
Perceptron Learning Algorithm
________________________________________________________

Input: T training instances (X0, Y0), (X1, Y1), …, (XT-1, YT-1), where
Xi : N input feature vector < xi,0 , xi,1 , …, xi,N-1 >
Yi is the corresponding actual (correct) class
Output: A decision boundary hyperplane - W = <w0, w1, …, wN-1>
________________________________________________________
Initialize W
Do
For i = 0 to T-1
For j = 0 to N-1
wj = wj + α ( Yi - h(Xi)) × xi,j
Until min classification error
09/22/2025 INTRODUCTION TO AI 36
Perceptron Learning Algorithm: Example
• Initialize: Randomly initialize the hyperplane (i.e. randomly initialize
the normal vector W)
• Classification Rule:
◦ Vectors on the same side of the hyperplane as W will be assigned
1 class, and those on the other side will be assigned 0

09/22/2025 INTRODUCTION TO AI 37
Perceptron Learning Algorithm: Example

Misclassified blue instance Updated weight vector

Misclassified blue instance,
add it to W

09/22/2025 INTRODUCTION TO AI 38
Perceptron Learning Algorithm: Example
Misclassified red instance

Perfect classification,
no more updates
Updated hyperplane
Updated hyperplane
Misclassified red instance,
subtract it from W

09/22/2025 INTRODUCTION TO AI 39
Perceptron Classifier (updating weights example)
-Current weight vector: W=(2,-1,1), -Training data points: as shown in the table, -Perceptron update α = 0.1
For each training instance:
◦ Classify with current weights: If correct (i.e., target=predicted), no change!, If wrong: adjust the weight vector
F(X) features Y(Actual) W0 W1 W2 Predicted Update weights
x0 x1 x2 2 -1 1
1 1 1 1 No update 1*2+1*-1+1*1 = 2>0 (matching Target=1, predicted=1
2 -1 1 the target) (no update)
1 2 0.4 0 After updating step 1*2+ 2*-1 + 0.4*1 = 0.4 >0 W+0.1*(0-1)*X=W-0.1*X
1.9 -1.2 means it is 1, (Not matched) W0=2-0.1*1=1.9
0.96 W1=-1-0.1*2=-1.2
W2= 1-0.1*0.4=0.96

1 -2 0 1 No update 1*1.9-2*-1.2+0*0.96=4.3 >0 Target=1, predicted=1 (no

1.9 -1.2 (matching the target) update)
0.96

09/22/2025 INTRODUCTION TO AI 40
Perceptron Classifier (updating weights example)
-Perceptron update α =0.1
For each training instance:
◦ Classify with current weights: If correct (i.e., target=predicted), no change!, If wrong: adjust the weight vector
F(X) features Y(Actual) W0 W1 W2 Predicted Update weights
x0 x1 x2 1.9 -1.2
0.96
1 1 1 1 No update Target=1, predicted=1
1.9 -1.2 1*1.9+1*-1.2+1*0.96 = 1.66>0 (no update)
0.96 (matching the target)
1 2 0.4 0 No update 1*1.9+ 2*-1.2 + 0.4*0.96 = - Target=0, predicted=0 (no
1.9 -1.2 0.1116<0 means it is 0, update)
0.96 (matching the target)

1 -2 0 1 No update 1*1.9-2*-1.2+0*0.96=4.3 >0 Target=1, predicted=1 (no

1.9 -1.2 (matching the target) update)
0.96
09/22/2025 INTRODUCTION TO AI 41
Decision Boundary – Perceptron Algorithm

𝐖 . 𝐗 <0 𝐖 .𝐗≥0
2
◦ Decision boundary line is essentially a
threshold function (0 or 1) 1
◦ Question:
◦ How accurate is the classification of the
two shown points 1 and 2?
◦ How confident?
09/22/2025 INTRODUCTION TO AI 42
Decision Boundary – Perceptron Algorithm

2
◦ Soft threshold
◦ Output is a real number in the interval 1

◦ Logistic function
◦ More about this later …

09/22/2025 INTRODUCTION TO AI 43
Decision Boundary – Support Vector Machines
Support Vector Machines (SVM)
◦ A popular algorithm to calculate
decision boundaries between classes 2
◦ Consider the shown data..
◦ Which of the 3 boundary lines is
considered the best? Why?

1
3

09/22/2025 INTRODUCTION TO AI 44
Decision Boundary – Support Vector Machines
Support Vector Machines (SVM)

◦ Finds a maximum margin separator -

i.e., boundary that maximizes the
distance between any of the data
points

◦ Unlike the perceptron algorithm which

finds any separator

09/22/2025 INTRODUCTION TO AI 45
Decision Boundary – Support Vector Machines
Support Vector Machines (SVM)

◦ Support Vectors are those datapoints

that the margin pushes up against
margin
◦ Together, the two support vectors
form the margin

◦ Maximum margin linear classifier is

the linear classifier with the
maximum margin Support vectors

09/22/2025 INTRODUCTION TO AI 46
Decision Boundary – Support Vector Machines
•SVMs maximize the margin around
the separating hyperplane

d+
d-
•The margin of example w.r.t. a
linear separator is the distance
from to the plane .
•Recall that and are raw vectors
𝐖 . 𝐗 +𝑏=0
given as , and
d+=d- represents ½ of the margin width

09/22/2025 INTRODUCTION TO AI 47
Decision Boundary – Support Vector Machines
•The decision function is fully specified by a (usually very small)
subset of training samples, the support vectors.
•Our goal is to search for a large margin classifier … SVM

09/22/2025 INTRODUCTION TO AI 48
Decision Boundary – Support Vector Machines
•The optimization algorithm to generate the weights proceeds in
such a way that only the support vectors determine the weights
and thus the boundary

09/22/2025 INTRODUCTION TO AI 49
Decision Boundary – Support Vector Machines
•Define the hyperplanes H such that:
• if
• if
where is the ith sample of features vector

•H1 and H2 are the planes:

• H1:
• H2:
𝐖 . 𝐗 +𝑏=+1

•The plane H0 is the median in between, where 𝐖 . 𝐗 +𝑏=0

• d+ = the shortest distance to the closest positive point 𝐖 . 𝐗 +𝑏=−1
• d- = the shortest distance to the closest negative point
• The margin of a separating hyperplane is (d+) + (d–)
09/22/2025 INTRODUCTION TO AI 50
Decision Boundary – Support Vector Machines
•The decision boundary should be
as far away from the data of both
classes as possible
•We should maximize the margin,
•It can be shown that the total
distance between H1 and H2 is
given by

2
𝑑=
‖𝐖‖
09/22/2025 INTRODUCTION TO AI 51
Support Vector Machines – 1D Example
•Consider the given data representing the weight
of mice where a red dot represents a not-obese
mouse while a green dot represents obese mouse.
•To classify a new mouse as obese or not, need to
define a threshold as a cut point between being margin

obese or not.
•The distance between the edge observation of a
cluster to the threshold is called a margin.
Maximum Margin
•When we use the threshold that gives the Classifier

maximum margin to make classification we call it

Maximum Margin Classifiers
09/22/2025 INTRODUCTION TO AI 52
Support Vector Machines: Hard vs Soft Margin
•What if our training data looked
like this?

•There is an outlier that will cause

the Maximum Margin Classifier to
look like this.
•The outlier node is classified as
not obese but lies much closer to
the obese.

09/22/2025 INTRODUCTION TO AI 53
Support Vector Machines: Hard vs Soft Margin
•If we try to classify a new
observation shown in black, we will
classify it as not obese! Although it is
very far away from the not obese New observation
and closer to the obese.
•The Maximum Margin Classifiers are
very sensitive to outliers.
•What can we do about it?

09/22/2025 INTRODUCTION TO AI 54
Support Vector Machines: Hard vs Soft Margin
•How about if we allow some misclassification
(i.e. allow some error) to help us classify new
observations better.
•Some misclassification may classify some
training data incorrectly but increases the
correct classification of the new observed data
(a good trade off)
•Since we allowed some misclassification, the Best soft margin is found
margin is called a soft margin. using cross validation
•When we use a soft margin to classify the
data, we often refer to it as Support Vector
Classifier
09/22/2025 INTRODUCTION TO AI 55
Support Vector Machines: Hard vs Soft Margin
•Hard margin does not allow any •Soft margin allows some errors.
error.

09/22/2025 INTRODUCTION TO AI 56
Support Vector Classifiers
•In 1-D, a support vector classifier is a
single dot within the 1-D space.
•In 2-D, a support vector classifier is a
line within the 2-D space.
•In 3-D, a support vector classifier is a
plane or surface within the 3-D
space.
•In higher dimensions, a support
vector classifier is a hyperplane
within the same dimension.
09/22/2025 INTRODUCTION TO AI 57
Linear Separability
•Two sets of data points in a two
dimensional space are said to be
linearly separable when they can
be completely separable by a
single straight line.
•In general, two groups of data
points are separable in a n-
dimensional space if they can be
separated by an n-1 dimensional
hyperplane.
09/22/2025 INTRODUCTION TO AI 58
Support Vector Machines - The Kernel Trick
•Suppose we have the data of a drug
dosage where the red dots represent
patients that got not cured while the
green dots represent those that got
cured.
•The data has lots of overlap
•Basically what the data is pointing out is
the fact that if the dosage is too little or
too high the drug does not work. It will
only work if the dosage is right.
•How can we classify this problem?
09/22/2025 INTRODUCTION TO AI 59
Support Vector Machines – The Kernel Trick
•Transform the problem to a higher

the 𝑦-axis as
dimension by computing the values on

•We will use

•Plotting the 2-D data we get the figure
on right
•We now can draw a support vector
classifier to classify the data, this will
help us in classifying the group of
people who got cured and those who
did not get cured.
09/22/2025 INTRODUCTION TO AI 60
Support Vector Machines – The Kernel Trick
• Now we can classify any new observation by plotting it
onto the new 2-D (i.e. at point ) and compare it with
our soft classifier line. If it is above, the dosage will not
cure and if it is below the patient will be cured.
• In general, taking the data to a higher dimension may
lead to better classification.
• SVM can use several kernel functions to map data to
higher dimensions such as the polynomial and radial
Decision boundary
functions.
• We just have to try each one to find the best kernel for
the considered data set

09/22/2025 INTRODUCTION TO AI 61
Support Vector Machines – The Kernel Trick
1. Given a set of non-linearly 3. Find a SVM classifier
separable points.

4. Project back to original space

2. Transform the data using a kernel

09/22/2025 INTRODUCTION TO AI 62
Advantages of SVMs
1. Regularization capabilities: SVM has good generalization
capabilities which prevent it from over-fitting.
2. Handles non-linear data efficiently: SVM can efficiently handle
non-linear data using Kernel trick.
3. Stability: A small change to the data does not greatly affect the
hyperplane and hence the SVM. So the SVM model is stable.
4. Optimality: SVM has a nature of Convex Optimization which helps
in finding globally best model.

09/22/2025 INTRODUCTION TO AI 63
Decision Boundary – Evaluation
Evaluation

◦ Using a loss function - calculate how

good or poorly our boundary
performs

09/22/2025 INTRODUCTION TO AI 64
Decision Boundary – Evaluation
Evaluation
◦ Using a loss function - calculate how
good or poorly our boundary
performs
◦ Our objective is to minimize the loss

09/22/2025 INTRODUCTION TO AI 65
Decision Boundary – Evaluation
Evaluation
◦ TP (True Positives) = examples that were correctly
labeled as “1”
◦ FN (False Negatives) = examples that should have
been “1”, but were labeled as “0”
◦ FP (False Positives) = examples that should have
been “0”, but were labeled as “1”
◦ TN (True Negative) = examples that were correctly
labeled as “0”
◦ A table of these values is called a “confusion matrix”
Classified As: Classified As:
Correct Label:

0 1
Correct Label:

0 1
0 TN FP 0 12 2 To link the example above to the table, consider blue as 1
and red as 0
1 FN TP 1 2 14
Confusion Matrix
09/22/2025 INTRODUCTION TO AI 66
Decision Boundary – Evaluation
• Several evaluation metrics may
be used; Two basic ones are:
◦ Accuracy, and
◦ Precision

Accuracy = (TP + TN)/(TP + TN + FP + FN)

Precision = TP/(TP + FP)

09/22/2025 INTRODUCTION TO AI 67
Decision Boundary – Cross-validation
• Given a set of data with labels, how can we use it to build a machine learning
model and evaluate its performance?
• We need to do two things with this data:
1. Estimate the parameters of the machine learning model, i.e. use it to
guess the shape of the decision boundary that best fits the data.
◦ Parameters estimation is called Training the model.

2. Evaluate how well do the learned parameters work, i.e. we need to test
how good a job will the decision boundary do when we present it with
data it has never seen before.
◦ Evaluating a method is called Testing the model.
09/22/2025 INTRODUCTION TO AI 68
Decision Boundary – Cross-validation
• Therefore in Machine learning:
◦ We need the data to train the machine learning model.
◦ We need to test the trained model on data it hasn’t seen in
training, to make sure that it generalizes well.
• Question: where can we get training and testing data?
◦ Using the same data for training and testing does not work since
we do not know how the algorithm performs when it is given a set
of data it has not been trained on.
◦ Using all the data for training will not leave any data for testing

09/22/2025 INTRODUCTION TO AI 69
Decision Boundary – Cross-validation
• Answer: Divide the collected labeled data into a training set and
testing set.
◦ A common practice in Machine Learning is to use 75% of the data
for training and 25% of data for testing. This is called the holdout
method
◦ The question is which 25% to choose for testing and which 75% to choose for
training?

09/22/2025 INTRODUCTION TO AI 70
Decision Boundary – Cross-validation
• We use k-fold cross-validation method:
◦ Break the training data into k equally sized subsets (folds)
◦ Train the ML model on k-1 subsets (the training set)
◦ Test the model on the remaining 1 set (the testing set)
◦ Do this k times, each time testing on a different set
◦ Calculate the average error over the k validation sets

09/22/2025 INTRODUCTION TO AI 71
Decision Boundary – Cross-validation
• Example: a Four-Fold cross validation: the data is divided into FOUR
equal sets as shown below:

• We then train and test the Machine Learning algorithm as follows:

◦ Sets 1,2,3 training and Set 4 for testing
◦ Sets 1,2,4 training and Set 3 for testing
◦ Sets 2,3,4 training and set 1 for testing
◦ ...etc (all possible combinations)
• In practice, its is common to use 10-fold Cross validation.
09/22/2025 INTRODUCTION TO AI 72
Decision Boundary – Cross-validation
• k-fold cross-validation can help us to obtain reliable estimates of the
model’s generalization performance, that is, how well the model
performs on unseen data.
• But the main disadvantage is increased computational cost

09/22/2025 INTRODUCTION TO AI 73
Decision Boundary – Underfitting and Overfitting
• Suppose we have the dataset as shown below
◦ Data is labeled, red circles and blue circles
• How can we train and obtain the best classifier?

09/22/2025 INTRODUCTION TO AI 74
Decision Boundary – Underfitting and Overfitting
• Idea 1: Let us try a linear classifier
represented by a straight line:
◦ As can be seen that there are many blue
points above the line that are
misclassified
◦ No matter how we rotate or shift the line,
we will always have high misclassification
rate in training and testing
◦ This is known as Underfitting
Over simplifies the
complexity in the data

09/22/2025 INTRODUCTION TO AI 75
Decision Boundary – Underfitting and Overfitting
• Idea 2:
◦ Let us use a curve that best can separate the red from the blue
classes
◦ Let us divide our data into training and testing as shown below

Training set Testing set

09/22/2025 INTRODUCTION TO AI 76
Decision Boundary – Underfitting and Overfitting
• Idea 2:
◦ We can find the "wavey" curve that best fits all the points in the
training set as shown below:
Fits the varying
training data
very well

09/22/2025 INTRODUCTION TO AI 77
Decision Boundary – Underfitting and Overfitting
• Idea 2:
◦ Now if we use the curve to test with data we get the following:

Does not do well

with the testing data

◦ As can be seen that many test points are not classified correctly.
◦ This is what we call Overfitting
09/22/2025 INTRODUCTION TO AI 78
Decision Boundary – Underfitting and Overfitting
• Idea 3:
◦ Allow for some misclassification and we can get:

◦ This curve does not overfit nor underfit

◦ There are some misclassifications but within an acceptable range
09/22/2025 INTRODUCTION TO AI 79
 Unsupervised
Learning

09/22/2025 INTRODUCTION TO AI 80
Unsupervised Learning
Unsupervised Learning
◦ Given input data without feedback, the
goal is to learn patterns
◦ No feedback means …
◦ Unlike supervised learning, the data is not
labeled
◦ Unlike reinforcement learning, no
reward/punishment

◦ Example: Unlabeled data

◦ Question: What patterns can be learned
from this data?
09/22/2025 INTRODUCTION TO AI 81
Unsupervised Learning
The Clustering Problem
◦ Organizing a set of objects into groups
in such a way that similar objects fall in
the same group
Some Clustering Applications
◦ Market research
◦ Image segmentation
◦ Medical imaging
◦ Social network analysis.
◦ Genetic research
09/22/2025 INTRODUCTION TO AI 82
Unsupervised Learning - k-means Clustering
k-means Clustering
◦ An algorithm divides all of our data
points into k different clusters
◦ Clustering data based on repeatedly
assigning points to clusters and
updating those clusters' centers
◦ k: a parameter indicating the number
of clusters
◦ Unknown – requires experimentation

09/22/2025 INTRODUCTION TO AI 83
k-Means Clustering - Example
Step 1
◦ Suppose we want 3 clusters, i.e.
◦ Initially, we choose 3 random centers
of those 3 clusters
◦ The 3 centers are indicated with Blue,
Red and Green diamonds.
◦ Center of a cluster represents the mean
of that cluster

09/22/2025 INTRODUCTION TO AI 84
k-Means Clustering - Example
Step 2
◦ Next, assign every point to a
cluster based on which cluster
center it is closest to
◦ These will be the initial clusters
based on our first initial random
centers

◦ Question: How can we improve?

09/22/2025 INTRODUCTION TO AI 85
k-Means Clustering - Example
Step 3
◦ Re-compute the centers (means) of
the clusters

09/22/2025 INTRODUCTION TO AI 86
k-Means Clustering - Example
Step 4
◦ Re-assign points based on the new
centers (means) of the clusters

09/22/2025 INTRODUCTION TO AI 87
k-Means Clustering - Example
Step 5
◦ Re-compute the centers (means) of
the clusters

◦ Algorithm repeats ..
◦ Re-assigning point to closest centers
◦ Re-computing centers (means)
◦ Eventually ..
◦ There will be no changes and algorithm
stops

09/22/2025 INTRODUCTION TO AI 88
k-Means Clustering - Example
Final Clusters …
◦ Shown the final clusters ..

09/22/2025 INTRODUCTION TO AI 89
 Reinforcement
Learning
SEMI-SUPERVISED LEARNING

09/22/2025 INTRODUCTION TO AI 90
Reinforcement Learning
Building an AI agent that learns from
experience
◦ Agent can be physical (e.g., Robot) or a program
◦ The agent is put in an environment, in which it
learns from its actions
◦ When the agent takes an action, it moves to a
new state
◦ For every action, there is a reward or
punishment,
◦ Agent learns what to do and what not to do in
the future actions
09/22/2025 INTRODUCTION TO AI 91
Reinforcement Learning
Examples: Robots learning to walk
◦ Robot learns through reward or punishment

[Link]
[Link]
[Link]

09/22/2025 INTRODUCTION TO AI 92
Reinforcement Learning - Markov Decision Process
Markov Decision Process (MDP): a
formal method to model decision-
making, representing states,
actions, and their rewards

◦ Set of states: S - circles

◦ Set of actions: ACTIONS(s) – arrows
◦ Transition model P(s' | s, a)
◦ What is the probability P of going to state
s’, if agent is in state s taking action a
◦ Reward function R(s, a, s')
◦ reward of going from state s to s’ after
taking action a
09/22/2025 INTRODUCTION TO AI 93
Reinforcement Learning - Markov Decision Process
Example: Simulated 4 x 5 world
navigated by a robot

◦ Robot

◦ Goal - green room

◦ Agent receives reward

◦ Bad places- red rooms

◦ Agent receives punishment

◦ Initially, the agent does not know what’s

good or bad!
09/22/2025 INTRODUCTION TO AI 94
Reinforcement Learning - Markov Decision Process
Good action – take in future
Example: Simulated 4 x 5 world
navigated by a robot

◦ Robot

◦ Goal - green room

◦ Agent receives reward

◦ Bad places- red rooms

◦ Agent receives punishment

◦ Initially, the agent does not know what’s Bad actions – avoid in future
good or bad!
09/22/2025 INTRODUCTION TO AI 95
Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning method
◦ Method for learning a function Q(s, a),
representing estimate of the reward
value of performing action a in state s

◦ Initially, Q(s, a) is unknown – but values

are learned through trying different
actions in different states

Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 96
Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning Overview:
◦ Start with Q(s, a) = 0 for all s, a
◦ When we take an action and receive a
reward:
◦ Estimate the value of Q(s, a) based on current
reward and expected future rewards
◦ For future rewards, rewards of taking a later
action
◦ Update Q(s, a) to take into account old
estimate as well as our new estimate
Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 97
Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning

◦ α is the learning rate [0,1]

◦ Controls how Q-function is updated
◦ Large α means we value new information
more than old information
Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 98
Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning

◦ Old value estimate = Q(s, a)

◦ What is the “new value estimate”?

Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 99
Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning

◦ New value estimate:

◦ reward r received after taking action a
◦ expected future reward estimates from
this state onwards
Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 100

Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning

◦ Future reward estimates:

◦ maxa' Q(s', a')
◦ maximum value across all possible
actions a’ taken from next state s’
Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 101

Reinforcement Learning - Q-learning method
Good action – take in future
Q-learning

◦ Future reward estimates (variation):

◦ is parameter controlling how future
rewards are valued over current rewards

Bad actions – avoid in future

09/22/2025 INTRODUCTION TO AI 102

Reinforcement Learning - Q-learning method
Good action – take in future
Greedy Decision-Making Policy

◦ After training … an agent adopts a

policy to choose an action from all
possible actions

◦ One possible policy is Greedy policy

◦ When in state s, choose action a with

highest Q(s, a)
Bad actions – avoid in future
◦ Is this the best policy? Why?
09/22/2025 INTRODUCTION TO AI 103
Reinforcement Learning - Q-learning method
Greedy Decision-Making Policy

◦ May not be the best policy

◦ Consider the shown two paths

◦ May choose the longer path over the

short path
◦ Never tried the top path

09/22/2025 INTRODUCTION TO AI 104

Reinforcement Learning - Q-learning method
-Greedy Decision-Making Policy
◦ Explore vs. Exploit
◦ Exploit: take the move with best reward
◦ Explore: try random move –if it may later
give better reward

09/22/2025 INTRODUCTION TO AI 105

Q-learning: Numerical Example
•Let us consider a game that has 6 states {A, B, C, D, E, F}. We can
start at any state but the game ends when we reach to state F.
•Let us assume that and
•Initially the Q matrix will be set to 0
•Let us assume the following reward matrix R
•A dash (-) in the matrix means that it is
not possible to go from a state to another state

09/22/2025 INTRODUCTION TO AI 106

Q-learning Numerical Example
•Let us assume that we start at state B.
•Looking at the 2nd row of matrix R, there are
two possible actions for the current state B, to
go to state D or state F.
•Let us assume that by random selection, F is
selected.
•Now let us consider that we are in state F.
From state F, there are 3 possible actions to
go to state B, E or F.
09/22/2025 INTRODUCTION TO AI 107
Q-learning Numerical Example
•Q(state, action) = R(state, action)+ max[Q(next state, all actions)]
•Q(B,F) = 100 + (0.8)max[Q(F,B), Q(F,E), Q(F,F)] = 100 + 0.8 * 0 = 100
•Note that since Q matrix is initially 0, Q(F,B)=Q(F,E)=Q(F,F)=0
•The next state F becomes the current state. Since F is the goal state,
the game ends and the agent now contains the following updated
Q matrix

09/22/2025 INTRODUCTION TO AI 108

Q-learning Numerical Example
•For the next game, let us assume that we started at
state D.
•From D, there are 3 possible actions to go to B, C or E.
•Let us assume that by random selection, we selected B.
•W need to compute Q(D,B)
•Q(D,B) = R(D,B) + (0.8) max[Q(B,D), Q(B,F)] = 0 +
0.8*100 = 80
•The Q matrix gets updated as shown.

09/22/2025 INTRODUCTION TO AI 109

Q-learning Numerical Example
•The next state B becomes the current state.
•From B we can go either to D or F. Let us assume that
we selected F.
•Q(B,F) = 100 + 0.8 Max[Q(F,B), Q(F,E), Q(F,F)] = 100 + 0.8
* 0 = 100
•The result does not change the Q matrix.

09/22/2025 INTRODUCTION TO AI 110

Q-learning Numerical Example
•If our agent learns more through playing many
more games, it will finally reach convergence
values of Q matrix as shown.
•The Q matrix can be then normalized by
dividing valid entries by the maximum value as
shown
•Using the Q matrix, the agent can reach the
goal in an optimum way.

09/22/2025 INTRODUCTION TO AI 111

Reinforcement Learning - Example
Playing Games
◦ Common application of reinforcement learning is in game playing

◦ Let the AI agent play a game many times

◦ Reward received when the game is over – wining (+1) or losing (-1)

◦ The AI agent eventually learns how to play the game

09/22/2025 INTRODUCTION TO AI 112

Reinforcement Learning - Example
Nim Game
◦ 2-players game
◦ Piles (rows) of objects
◦ At each turn, a player removes one or
more objects from one pile
◦ The player who removes the last
object loses!
State: is a tuple of remaining Demo
piles, e.g. (1, 1, 4, 4) nim folder
Action (i, j): represents the action Modify the file (play)
of removing j items from pile i Watch video
09/22/2025 INTRODUCTION TO AI 113
Machine Learning Summary
Supervised Learning Reinforcement Learning Unsupervised Learning
◦ Labelled data ◦ Rewards (evaluative ◦ Unlabeled data (no
(instructive feedback) feedback) feedback)
◦ Classification ◦ Playing games ◦ clustering

09/22/2025 INTRODUCTION TO AI 114

Credit and References
• CS50’s Introduction to Artificial Intelligence with Python
• [Link]
• [Link]
• [Link]
• [Link]
ng/[Link]

09/22/2025 INTRODUCTION TO AI 115