Intelligent Explorer – Q-Learning Robot Navigation in a Grid

King Fahd University of Petroleum and Minerals

College of Computing and Mathematics

COE 292

Introduction to Artificial Intelligence

Topic 01: Introduction

Topic 3 COE 292 Introduction to Artificial Intelligence 2

❖ 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

Outline

Topic 3 COE 292 Introduction to Artificial Intelligence 3

❖ Learning and intelligence are related to each other.

❖ It is usually agreed that a system capable of learning deserves

to be called intelligent; and conversely, a system being

considered as intelligent is, among other things, usually

expected to be able to learn.

What is Learning?

Learning

The acquisition of knowledge or skills through study, experience, or being taught and using that knowledge to solve problems.

Learning is the ability to improve behavior based on experience.

Topic 3 COE 292 Introduction to Artificial Intelligence 4

❖ AI agent solves problems:

• Following specific algorithms

▪ Generate and test(Topics 1)

▪ Problem Reduction(Topics 2)

▪ Search(Topic 6&7)

• Knowledge Representation

❖ This topic is about solving problems thorough Learning

• Machine Learning (understanding the world using data):

▪ Let the computer learns from provided data or feedback, rather than giving

explicit instructions

• Similar to how a human learns to perform tasks

AI Techniques

Topic 3 COE 292 Introduction to Artificial Intelligence 5

AI and Machine Learning

Programs can sense, reason, act and adapt

Algorithms whose performance improve as they expose to more

data over time

Multilayered neural networks learn from vast amount of data

Topic 3 COE 292 Introduction to Artificial Intelligence 6

❖ A computer observes some data, builds a model based

on the data, and uses the model as both a function and

an algorithm to solve problems

Machine Learning (ML)

Example: Image classification, navigate through a maze

It is extremely difficult to come up with precise rules to visually

differentiate objects.

Machine Learning models infer them from labeled data.

Topic 3 COE 292 Introduction to Artificial Intelligence 7

Machine Learning Approaches

The algorithm is presented

with inputs and their

desired outputs

The algorithm is presented

with inputs without labels

A computer program operates in a

dynamic environment to achieve a

goal, using reward-like feedback

to guide its actions and maximize

performance.

Topic 3 COE 292 Introduction to Artificial Intelligence 8

Typical Problems for ML?

• Predict the type of disease based on patient symptoms

and test results.

• Predict the selling price of a house based on its features

• Group customers into segments based on

purchasing behavior

• Group genes with similar expression patterns

across samples.

• Rank/order web pages based on their relevance

to a user query.

• Rank courses for a student based on interest,

• Find items that are frequently bought together

• Recommend content based on past user behavior.

• Identify symptom and disease co-occurrence

patterns.

Supervised Learning

Topic 3 COE 292 Introduction to Artificial Intelligence 10

❖ Given a dataset of input-output pairs, SL is about learning a model to map inputs to outputs/labels as accurately as possible

❖ Example:

• Regression:

▪Compute y given x

• Classification

▪Map each image to a digit

Supervised Learning (SL)

Topic 3 COE 292 Introduction to Artificial Intelligence 11

❖ Classification is a supervised learning task of

learning a function/model that maps an input

to a discrete category.

• Predict a category or class label for given input data.

• Such function/model is also called a classifier.

❖ Real-World Examples:

• Email filtering (spam vs. not spam)

• Digit recognition

• Medical diagnosis (disease A, B, or healthy)

• Document categorization (news, sports, politics, tech)

• Face recognition

• Credit risk assessment (low, medium, high risk)

Supervised Learning - Classification

classifier

1

2

3

4

5

6

7

8

9

cl as

si fi

er

cat

tiger

horse

classifier

Topic 3 COE 292 Introduction to Artificial Intelligence 12

❖ Example: Predicting Weather

• Will it rain tomorrow?

• Problem Statement:

▪ Given: Labeled data in the form of input-output pairs: 𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒,ℎ𝑢𝑚𝑖𝑑𝑖𝑡𝑦,... ⟶ Rain or No Rain

▪ Can you tell predict wither it will rain tomorrow or not.

• Objective: Learn a function/model that can predict the weather based on input features.

• Prediction Task: Classify a given day as either: Raining or Not Raining

• How many classes are involved in this classification task?

Supervised Learning - Classification

Topic 3 COE 292 Introduction to Artificial Intelligence 13

❖ Classification algorithms learn from labeled data instances in

the form of (features, class). e.g., (ℎ𝑢𝑚𝑖𝑑𝑖𝑡𝑦,𝑝𝑟𝑒𝑠𝑠𝑢𝑟𝑒),𝑅𝑎𝑖𝑛

• Learn a function that map input features to a class

f(humidity, pressure) = class

• Examples: f(93,999.7) = Rain, f(49,1015.5) = No Rain

• This function can then be used to predict the class for new

unseen data.

Classification Example – Predicting Weather

features label/class

Date Humidity Pressure Rain

January 1 93% 999.7 Rain

January 2 49% 1015.5 No Rain

January 3 79% 1031.1 No Rain

January 4 65% 984.9 Rain

January 5 90% 975.2 Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 14

❖ Towards predicting weather

• Each sample, the (humidity, pressure) of a given day, is represented

by a point 𝑥 = (𝑥1, 𝑥2)

• Plot the data

• Points colored either

▪Blue if that day was rainy, or

▪Red if the day was not rainy.

Questions:

• Plot is 2-D, why?

• What if there are more classes?

• What if there are more features?

Classification Example – Predicting Weather

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 15

❖ Classification Problem

• Given a new, unlabeled data point, which class does it belong to?

• Goal: Find a model that classifies new data points based on past labeled

examples.

❖ Example:

• What is the class of the new

data point (shown in black)?

▪ Rain or No Rain?

• Why?

• What classification approach would you use?

Classification Example – Predicting Weather

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 16

❖ Classification By Similarity

• Nearest Neighbor Algorithm (1-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

Classification Approaches

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 17

❖ How about the new shown point?

• The new point is classified as red (No Rain).

• Its nearest neighbor is a red point

Classification By Similarity

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 18

❖ How about the new shown point?

❖ Is it blue (Rain) or red (No Rain)?

Classification By Similarity

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 19

❖ k-Nearest Neighbor Algorithm (k-NN)

• Classify based on k nearest neighbors; the most frequent class label

among the k nearest neighbors

• Example:

▪ Classification based on 3 nearest neighbors

Classification By Similarity

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 20

❖ Measuring Similarity

• To find the nearest neighbors of a given unclassified point,

k-NN requires a function to calculate the similarity between

data points.

k-Nearest Neighbor Algorithm (k-NN)

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 21

❖ Given 2 points represented in a n-D space

A = (𝑎1, 𝑎2, ⋯ , 𝑎𝑛) and B = 𝑏1, 𝑏2, ⋯ , 𝑏𝑛

1. Euclidean distance 𝒅 𝐚, 𝒃

𝒅 𝒂, 𝒃 = ෍

𝒊=𝟏

𝒏

𝒂𝒊 − 𝒃𝒊 𝟐

2. Manhattan distance 𝒅 𝒂, 𝐛

𝒅 𝒂, 𝒃 = ෍

𝒊=𝟏

𝒏

𝒂𝒊 − 𝒃𝒊

3. Cosine similarity

sim 𝐀, 𝐁 = cos 𝜃 = 𝐀.𝐁

𝐀 𝐁

where A.B is the dot product.

What if sim(a,b) is 0 ? is 1 ? Is -1?

Measuring Similarity

Find the Manhattan distance between A = (3,5) and B = (1,2).

d A, B = 3 − 1 + 5 − 2 = 5

Find the Euclidean distance between A= (3,5) and B= (1,2).

d A, B = (3 − 1)2+(5 − 2)2= 3.6

Find the cosine similarity between A = (1,1) and B

= (-1,1).

sim A, B = 𝐴. 𝐵

𝐴 |𝐵| =

1 ∗ −1 + 1 ∗ 1

2 2 = 0

𝐀𝐁

Topic 3 COE 292 Introduction to Artificial Intelligence 22

K-Nearest Neighbor Algorithm

Topic 3 COE 292 Introduction to Artificial Intelligence 23

k-NN: Example

Classification with k = 7

Class 1

Class 2

Class 3 New data point

To classify a new (unlabeled) point, the algorithm

must compare it to all existing points in the dataset.

Topic 3 COE 292 Introduction to Artificial Intelligence 24

𝑑 𝑎, 𝑏 = ෍

𝑖=1

𝑛

𝑎𝑖 − 𝑏𝑖 2

k-Nearest Neighbor Algorithm (k-NN)

P 𝑥1 𝑥2 Class/

Label Distance Pi to (3,7)

Rank based on

(minimum distance)

P1 7 7 Bad (7 − 3)2+(7 − 7)2= 4 3

P2 7 4 Bad (7 − 3)2+(4 − 7)2= 5 4

P3 3 4 Good (3 − 3)2+(4 − 7)2= 3 1

P4 1 4 Good (1 − 3)2+(4 − 7)2= 3.6 2

New

point 3 7 ?

Majority Vote: We have 2 Good and 1 Bad. Therefore, the new data point

is classified as Good based on majority voting.

❖ Given the following 4 labeled points:

• 𝑝1 = 7,7 labeled “Bad”

• 𝑝2 = 7,4 labeled “Bad”

• 𝑝3 = 3,4 labeled as “Good”

• 𝑝4 = 1,4 labeled as “Good”

Classify the new point (3,7) using 3-NN and using

Euclidean distance as the measure of similarity? Good class Bad class

Topic 3 COE 292 Introduction to Artificial Intelligence 25

❖ Consider the figure below which shows a data set with 8

labeled points and one unlabeled point P = (4, 4). Using 5-NN

and utilizing the Manhattan distance as the similarity measure,

classify the point p = (4, 4)? What about k =3?

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 26

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 27

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 28

❖ KNN assumes that nearby data points tend to belong to the same class.

• When a new data point is introduced, it’s classified based on the majority class among its K nearest neighbors in the training data.

❖ Pros

• Simple algorithm to implement

• Does not require training; does not build a model; No computation; Very fast

❖ Cons

• Slow in classifying a new point: All the computation happens at classification time

▪ Calculate the distance between the new point and every point in the training set

• Not efficient with high dimensional data

▪ data points become sparser, and the distance between points becomes less meaningful.

• Sensitive to scale of features, k and distance metric

❖ k-NN Demo: http://vision.stanford.edu/teaching/cs231n-demos/knn

k-NN Characteristics

Topic 3 COE 292 Introduction to Artificial Intelligence 29

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 30

❖ k-NN classifies a new point based on a majority vote among the 𝑘nearest

neighbors.

❖ To ensure that the negative class wins in the majority vote, the number of −

neighbors in the group must be more than the number of + neighbors.

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 31

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 32

❖ The Iris Flower Dataset involves predicting the flower species

given measurements of iris flowers.

❖ There are 150 observations with 4 input variables and 1 output

variable. The variable names are as follows:

• Variable 1: Sepal length in cm.

• Variable 2: Sepal width in cm.

• Variable 3: Petal length in cm.

• Variable 4: Petal width in cm.

• Output: Class

Hands-On KNN: Iris Flower Classification

Image Credit: StatQuest

Topic 3 COE 292 Introduction to Artificial Intelligence 33

Hands-On KNN: Iris Flower Classification

KNN_Iris_Classification_Final.ipynb

Topic 3 COE 292 Introduction to Artificial Intelligence 34

Iris Flower Classification

Best value for k is 4

Accuracy is 97%

Topic 3 COE 292 Introduction to Artificial Intelligence 35

❖ The decision boundary is smoother with very

large values of k.

❖ A very small value of k makes the algorithm

highly sensitive to noisy data (overfitting)

Hands-On KNN: Decision Boundary

Topic 3 COE 292 Introduction to Artificial Intelligence 36

❖ The digits dataset consists of 8 × 8 pixel images representing handwritten digits.

❖ To apply a classifier on this data, we need to flatten the images, turning each 2-D array of grayscale values from shape (8, 8) into shape (64,).

❖ There are 1797 images

❖ Encoding: image is a vector of intensities:

❖ The intensities range from 0 to 1, or 0 to 255 where 0 represents white and 1 represents black.

Hands-On KNN: Hand-written Digits Recognition

Topic 3 COE 292 Introduction to Artificial Intelligence 37

Hands-On KNN: Hand-written Digits Recognition

Accuracy is 97% KNN_Digits_Classification_Final.ipynb

Other Classification Approaches

Topic 3 COE 292 Introduction to Artificial Intelligence 39

❖ So far …

• Classification was done by

comparing a new point to

its neighbors using the k-

NN Algorithm

• Are there other

approaches?

Other Classification Approaches

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 40

❖ Classification By creating Decision Boundary between classes

• Decision Boundary is a surface (line, curve, or hyperplane) that divides feature

space into two or more regions; separates different classes.

• A new point is classified based on where it falls relative to the decision boundary

Other Classification Approaches

❖ Example (Weather):

• The yellow line represents one possible

decision boundary

▪ separates rainy days from non-rainy days

▪ Blue (Rain) points below the line; class

1 ( positive class)

▪ Red (No Rain) points above the line;

class -1 or 0 ( negative class)

• What is the class of the shown new points?

?

?

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 41

❖ Several algorithms can be used to find the best decision boundary

❖ Decision boundary

• In 2-D, it is a line or a curve

• In 3-D, it is a plane

• In n-D, it is a hyperplane

❖ Warning: data points may not be completely separable

❖ In general, goal is to find the best possible decision boundary

• Need to compare different possible decision boundaries

❖ Question: Is the shown line the best one? Why?

Classification By Decision Boundary

?

?

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 42

❖ Finding the Decision Boundary

• Let’s consider the 2-D case

• The decision boundary is a line h

• Different weights give different lines

• How to find the best line?

Decision Boundary – Perceptron Algorithm

𝑨𝒙 + 𝑩𝒚 + 𝑪 = 𝟎

𝒚 = 𝒎𝒙 + 𝒃

Rain No Rain

𝑤1𝑥 + 𝑤2𝑦 + 𝑤0 = 0

Topic 3 COE 292 Introduction to Artificial Intelligence 43

Topic 3 COE 292 Introduction to Artificial Intelligence 44

❖ Finding the best Decision Boundary

• Using vector notation and Using 1 for Rain, 0 for No Rain

Decision Boundary – Perceptron Algorithm

More compact vector form

𝑨𝒙 + 𝑩𝒚 + 𝑪 = 𝟎

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 45

❖ Consider the perceptron algorithm with weight vector 𝑊 = (𝑊0 , 𝑊1 ,

𝑊2, 𝑊3) = (−5, 2, −1, 3). What will be the class

assigned to the new point X = 𝑥1, 𝑥2, 𝑥3 = (3, 2, 4)?

Pop-up Question

𝑊 = −5 2 − 1 3 𝑋 = 1 3 2 4

Topic 3 COE 292 Introduction to Artificial Intelligence 46

Perceptron Algorithm: Idea

Step 1 Step 2 Step 3 Step 4 Step 5

Topic 3 COE 292 Introduction to Artificial Intelligence 47

❖ 𝑋 = : 𝑥0, 𝑥1, 𝑥2 … , 𝑥𝑛, 𝑦 data points

❖ 𝑊 = (𝑤0, 𝑤1, 𝑤2, … , 𝑤𝑛): the weight

vector

❖ y: class 1 or 0

❖ α: learning rate: controls weight updates

Perceptron Algorithm: Learning Rule

𝑊 = 𝑊 + 𝛼 𝑎𝑐𝑡𝑢𝑎𝑙 − 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑒𝑑 × 𝑋

Perceptron learning rule:

Given data point 𝑋 𝑎𝑛𝑑 its class y, update

weight according to:

𝑾 = 𝑾 + 𝜶 𝒚 − 𝒉𝒘 𝒙 × 𝑿

For each w

𝑤𝑖 = 𝑤𝑖 ∓ 𝛼 ∗ 𝑥𝑖

𝑊 = 𝑊 ∓ 𝛼 ∗ 𝑋 vector notation Rain No Rain

If actual > predicted:

add x,

weight update is in the direction of x

If actual < predicted:

subtract x

weight update is in the opposite direction of x

Topic 3 COE 292 Introduction to Artificial Intelligence 48

❖ Given T training instances (𝑋1, 𝑦1), (𝑋2, 𝑦2), … , (𝑋𝑇, 𝑦𝑇)

• 𝑋𝑖: input feature vector

• 𝑌𝑖: the actual class ( 1 and 0)

❖ Output: a decision boundary 𝑊 = < 𝑤0, 𝑤1, 𝑤2, … , 𝑤𝑛 >

Perceptron Learning Algorithm

Initialize W

Do

for i = 1 to T

W = W + α (Yi – h(Xi) )* Xi

Until min classification error

Topic 3 COE 292 Introduction to Artificial Intelligence 49

❖ Given the following initial weight vector 𝑊 = (𝑤0, 𝑤1, 𝑤2) =

(0.5, −1, 1) and a learning rate α = 1. What is the new weight

vector if we use the data point (𝑥1, 𝑥2) = (2, −1) with the

correct label y = 1?

❖ A) W = (0.5, -1, 1)

B) W = (2.5, -2, 2)

C) W = (1.5, 1, 0)

D) W = ( 1 , 2, -1)

Pop-up Question

𝑾 = 𝑾 + 𝜶 𝒚 − 𝒉(𝑿) × 𝑿

Topic 3 COE 292 Introduction to Artificial Intelligence 50

❖ Suppose that we want to train a perceptron with the

following data points and corresponding label:

• 𝑝1 = (1,1) with label 1

• 𝑝2 = (2,0.4) with label 0

• 𝑝3 = (−2,0) with label 1

❖ The algorithms picks the training points as follows: 𝑝1,

𝑝2, 𝑝3, and stops when no point is misclassified.

❖ If the weight vector chosen randomly at the start was 𝑊 = (2, −1,1) and the learning rate α = 0.1 is selected.

What will be the final value of the weight vector?

Perceptron Classifier: Example

𝑾 = 𝑾 + 𝜶 𝒚 − 𝒉(𝑿) × 𝑿

𝒉𝒘 𝑿 = ቐ 𝟏 𝒊𝒇 𝑾. 𝑿 ≥ 𝟎

𝟎 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆

Topic 3 COE 292 Introduction to Artificial Intelligence 51

❖ Training data points shown in the table, Learning rate α = 0.1

❖ Current weight vector: 𝑊 = (2, −1,1) = (𝑤0, 𝑤1, 𝑤2) ❖ For each training instance, Classify with current weights:

• If correct (i.e., target=predicted), no change!, If wrong: adjust the weight

Perceptron Classifier (updating weights example)

Features Y(Actual) w0 w1 w2 Predicted (h) = σ 𝒘𝒊 𝒙𝒊

Update weights

W = w +α*(actual – predicted) *xx0 x1 x2

1 1 1 1 2 -1 1

W=[ 2 -1 1]

X = [ 1 1 1]

---------------------

sum(2, -1, 1) =2 ≥ 0 → h = 1

y = 1, h = 1 (match)

no update

1 2 0.4 0 2 -1 1

W = [2 -1 1]

X = [1 2 0.4]

---------------------

sum(2, -2, 0.4) =0.4 ≥ 0 → h = 1

y = 0, h = 1 (no match)

W+0.1*(0-1)*X=W- 0.1*X

[ 2 -1 1 ]

[-0.1 -0.2 -0.04]

-------------------------------

[1.9 -1.2 0.96]

1 -2 0 1 After updating weight

1.9 -1.2 0.96

W = [1.9 -1.2 0.96]

X = [ 1 -2 0]

---------------------

sum(1.9, 2.4, 0) =4.3 ≥ 0 → h = 1

y = 1, h = 1 (match)

no update

Topic 3 COE 292 Introduction to Artificial Intelligence 52

❖ Training data points shown in the table, Learning rate α = 0.1

❖ Current weight vector: 𝑊 = (2, −1,1) = (𝑤0, 𝑤1, 𝑤2) ❖ For each training instance, Classify with current weights:

• If correct (i.e., target=predicted), no change!, If wrong: adjust the weight

Perceptron Classifier (updating weights example)

Features Y(Actual) w0 w1 w2 Predicted (h) = σ 𝒘𝒊 𝒙𝒊

Update weights

W = w α*(actual – predicted) *xx0 x1 x2

1 1 1 1 1.9 -1.2 0.96

W = [1.9 -1.2 0.96]

X = [ 1 1 1]

---------------------

sum(1.9, -1,2, 0.96) =1.66 ≥0→ h=1

y = 1, h = 1 (match)

no update

1 2 0.4 0 1.9 -1.2 0.96

W = [1.9 -1.2 0.96]

X = [ 1 2 0.4]

---------------------

sum(1.9,-2,4, 0.384) = -0.1160→h=0

y = 0, h = 0 (match)

no update

1 -2 0 1 1.9 -1.2 0.96

W = [1.9 -1.2 0.96]

X = [ 1 -2 0]

---------------------

sum(1.9, 2,4, 0) = 4.3 ≥ 0 → h = 1

y = 1, h = 1 (match)

no update

Topic 3 COE 292 Introduction to Artificial Intelligence 53

❖ Find the hyperplane σ𝑖=0 𝑁 𝑊𝑖𝑋𝑖 = 0 that perfectly

separates the two groups of points

❖ Note that 𝑊 = [𝑤0, 𝑤1, … 𝑤𝑁] is a vector that is

orthogonal to the hyperplane

Perceptron Learning Algorithm

Note that W.X is the vector

dot product = |W| |X| Cos ,

where  is the angle between

vectors W and X.

Topic 3 COE 292 Introduction to Artificial Intelligence 54

❖ Initialize: Randomly initialize the hyperplane (i.e.

randomly initialize the normal vector W)

• Example: 𝑤 = (𝑤1, 𝑤2) = (−1, 1 )

Perceptron Learning Algorithm: Example 1

❖ Classification Rule:

• Points(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 class

Topic 3 COE 292 Introduction to Artificial Intelligence 55

Perceptron Learning: Example 1

• 𝑤 = (−1, 1 ) • Line: −𝑥 + 𝑦 = 0 • 𝑦 = 𝑥

• Choose point

𝑥 = (−2, −3)

• It is classified as 0 while its

actual class is 1

• → (actual -predicted) = 1

• Update w

• 𝑤 = 𝑤 + 𝑥

• 𝑤 = −1,1 + −2, −3 = (−3, −2)

Class 1 Class 0

Topic 3 COE 292 Introduction to Artificial Intelligence 56

Perceptron Learning: Example 1

Class 1 Class 0

• 𝑤 = (−1, 1 ) • Line: −𝑥 + 𝑦 = 0 • 𝑦 = 𝑥

• Choose point

𝑥 = (−2, −3)

• It is classified as 0 while its

actual class is 1

• → (actual -predicted) = 1

• Update w

• 𝑤 = 𝑤 + 𝑥

• 𝑤 = −1,1 + −2, −3 = (−3, −2)

Topic 3 COE 292 Introduction to Artificial Intelligence 57

Perceptron Learning: Example 1

Class 1 Class 0

• 𝑤 = (−1, 1 ) • Line: −𝑥 + 𝑦 = 0 • 𝑦 = 𝑥

• Choose point

𝑥 = (−2, −3)

• It is classified as 0 while

its actual class is 1

• → (actual -predicted) = 1

• Update w

• 𝑤 = 𝑤 + 𝑥

• 𝑤 = (−1,1) + (−2, −3) = (−3, −2)

• Line: 𝑦 = 3

−2 𝑥

Topic 3 COE 292 Introduction to Artificial Intelligence 58

Perceptron Learning: Example 1

• 𝑤 = (−3, −2) • Line: −3𝑥 − 2𝑦 = 0

• −2𝑦 = 3𝑥

• 𝑦 = 3

−2 𝑥

• Choose point 𝑥 = (1, −3)

• It is classified as 1 while

its actual class is 0

• → (actual -predicted)= -1

• Update w

• 𝑤 = 𝑤 − 𝑥

• 𝑤 = −3, −2 − (1, −3)

• 𝑤 = (−4,1) Class 1 Class 0

Topic 3 COE 292 Introduction to Artificial Intelligence 59

Perceptron Learning: Example 1

Class 1 Class 0

• 𝑤 = (−3, −2) • Line: −3𝑥 − 2𝑦 = 0

• −2𝑦 = 3𝑥

• 𝑦 = 3

−2 𝑥

• Choose point 𝑥 = (1, −3)

• It is classified as 1 while

its actual class is 0

• → (actual -predicted)= -1

• Update w

• 𝑤 = 𝑤 − 𝑥

• 𝑤 = −3, −2 − (1, −3)

• 𝑤 = (−4,1)

Topic 3 COE 292 Introduction to Artificial Intelligence 60

Perceptron Learning: Example 1 Summary

𝑤 = 𝑤 + 𝑥

𝑤 = −1,1 + −2, −3 = (−3, −2)

𝑤 = 𝑤 − 𝑥

𝑤 = −3, −2 − (1, −3) 𝑤 = (−4,1)

Topic 3 COE 292 Introduction to Artificial Intelligence 61

Perceptron Learning Algorithm: Example 2

Update weight vectorMisclassified blue instance, add it to W Updated weight vector

Misclassified red instance, subtract it from W Update weight vector Updated weight vector

Perfect classification, no more updates

Topic 3 COE 292 Introduction to Artificial Intelligence 62

❖ Perceptron is a linear classification algorithm.

• It learns a decision boundary that separates two classes using a line,

represented by the weight vector w, (called a hyperplane) in the feature

space. Different weight vectors give different lines

• As such, it is appropriate for those problems where the classes can be

separated well by a line or linear model, referred to as linearly separable.

❖ Training Time: All the computation happens at training. It learns a model

by adjusting weights over multiple passes (epochs) through the data.

❖ Prediction Time: Very fast. Just computes a dot product between input

features and weights, then applies a sign function

Perceptron Algorithm: Summary

𝑊 = 𝑊 + 𝛼 𝑦 − ℎ(𝑋) × 𝑋1. Classification

rule

2. Weight update or learning rule

Topic 3 COE 292 Introduction to Artificial Intelligence 63

❖ Consider two separate classes

of data shown in the figure

below where the first class of

data points shown as circles

are classified as label “+1”

and the other class data

shown as triangles are

classified as “-1”. Draw a

possible decision boundary

and the vector W.

Pop-up Question

[-2 -1 1]

Topic 3 COE 292 Introduction to Artificial Intelligence 64

❖ The decision boundary, the

line, is essentially a hard

threshold function; output is

either 0 or 1

❖ Soft threshold: Output is a real

number in the interval (0,1)

❖ Question:

• How accurate is the classification

of the two shown points 1 and 2?

• How confident?

Decision Boundary – Perceptron Algorithm

Rain No Rain

Topic 3 COE 292 Introduction to Artificial Intelligence 65

Hands on Perceptron

Support Vector Machines

Topic 3 COE 292 Introduction to Artificial Intelligence 67

❖ A popular algorithm to calculate decision boundaries

between two classes

❖ Consider the shown data:

• Which line will be returned by the perceptron?

• Which line is the best? Why?

• We want to find the best line that

separates any two sets of data.

Support Vector Machines : Motivation

1

2

3

Topic 3 COE 292 Introduction to Artificial Intelligence 68

❖ Unlike the perceptron algorithm which finds any

separator, SVM finds a maximum margin separator -

i.e., a decision boundary with the largest possible

distance between the hyperplane (the decision

boundary) and the CLOSEST data points from each

class.

Support Vector Machines SVM aims to find the best hyperplane as it places that boundary

as far away as possible from the closest points of either class.

Topic 3 COE 292 Introduction to Artificial Intelligence 69

❖ Support vectors:

• Data points that are closer to the hyperplane

• They influence the position and orientation of the hyperplane.

• Moving the support vectors will change the margin - position

of the 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 • It finds the support vectors that

maximize the margin

Topic 3 COE 292 Introduction to Artificial Intelligence 70

❖ Using these support vectors, we maximize the margin

of the classifier:

• Our goal is to search for the largest margin classifier

• Maximum margin linear classifier is the linear classifier with

the maximum margin

Support Vector Machines

Topic 3 COE 292 Introduction to Artificial Intelligence 71

❖ Define the hyperplanes H such that:

• 𝑤 ∙ 𝑥𝑖 + 𝑏 ≥ +1 𝑤ℎ𝑒𝑛 𝑦𝑖 = +1

• 𝑤 ∙ 𝑥𝑖 + 𝑏 ≤ −1 𝑤ℎ𝑒𝑛 𝑦𝑖 = −1

❖ H1and H2 are the planes:

• H1: 𝑤 ∙ 𝑥𝑖 + 𝑏 = +1

• H2: 𝑤 ∙ 𝑥𝑖 + 𝑏 = −1

❖ The plane H0 is the median in between, where 𝑊. 𝑋 + 𝑏 = 0

• d+ = the shortest distance to the closest positive point

• d- = the shortest distance to the closest negative point

• The margin of a separating hyperplane is d+ + d–

Decision Boundary – Support Vector Machines

Topic 3 COE 292 Introduction to Artificial Intelligence 72

❖ 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

𝐖

❖ 𝑊 vector is always unique

and orthogonal to H0

and in the direction of H1

Decision Boundary – Support Vector Machines

𝑊. 𝑋 + 𝑏 = 0

Topic 3 COE 292 Introduction to Artificial Intelligence 73

❖ Suppose that you train SVM on a dataset with 6 points as shown in the following figure. This dataset contains three samples with class label -1, and three samples with class label +1.

❖ What is the equation that corresponds to the decision boundary?

❖ In practice to solve SVM,

• Lagrange multiplier method

• Dynamic programming method

❖ However, we can use analytical methods to find decision boundary.

SVM: Finding the Decision Boundary: Example 1

Topic 3 COE 292 Introduction to Artificial Intelligence 74

❖ To find the decision boundary,

first we need to identify Two

Nearest Points

• A pair of points which belongs to

different classes and have smallest

distance between them

❖ The “Two Nearest Points” are

𝑝1 = (1,2) and 𝑛1 = (3,4)

Finding Decision Boundary : Example 1

p1

n1

Topic 3 COE 292 Introduction to Artificial Intelligence 75

❖ Let H1 be pivoted at point p2(1,2), while H2 be pivoted

at point n1(3,4)

❖ The margin between H1 and H2 depends on the slope of

these lines.

❖ Changing the slope of H1 and H2 changes the value

of the margin. For the figure on the right:

• Margin is equal to zero, if slope of H1 and H2 is equal to 1.

• Margin is equal to 2 if H1 and H2 are vertical lines.

❖ We want to find the slope that allows for the largest

margin while correctly classifying the data points.

❖ What slope will give maximum margin 𝑑?

• The maximum margin is achieved when H1 and H2 are

orthogonal to line p2 n1.

Finding Decision Boundary : Example 1

Topic 3 COE 292 Introduction to Artificial Intelligence 76

❖ Step1: the closest points (vector-pairs) are

• n1(3,4) and p2(1,2)

❖ Slope of line (p2,n1) denoted by m1

▪ 𝑚1 = 4−2

3−1 =

2

2 = +1

• Since 𝑊 is orthogonal to H0, H1 or H2,

• Slope of 𝑊 is equal to 𝑚1 = 𝑤2

𝑤1 = 1; → 𝑤1 = 𝑤2

❖ Since H1 is parallel to H2 and orthogonal to

line (p2, n1), the slope of H1 (or H2) denoted

as m2 is 𝑚2 = −1

𝑚1 =

−1

1 = −1

❖ Slope of H1is − 𝑤1

𝑤2 → −

𝑤1

𝑤2 = −1 → 𝑤1 = 𝑤2

• We proceed to compute the weight vector

𝑊 = 𝑤1, 𝑤2

Finding Decision Boundary : Example 1

Slope of 𝑾 is equal to = 𝒘𝟐

𝒘𝟏

Slope of 𝑯𝟏 is equal to = − 𝒘𝟏

𝒘𝟐

Note: The 𝑊 vector is always orthogonal

to the H0 line and in the direction of the

+ve data points (or H1 line).

Topic 3 COE 292 Introduction to Artificial Intelligence 77

❖ Step2: Now, we have the following equations: w1 = w2

• H1:𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = 1 𝑢𝑠𝑖𝑛𝑔 1,2 , 𝑤𝑒 𝑔𝑒𝑡 𝑤1 1 + 𝑤2 2 + 𝑏 = 1

• H2:𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = −1 𝑢𝑠𝑖𝑛𝑔 3,4 , 𝑤𝑒 𝑔𝑒𝑡 𝑤1 3 + 𝑤2 4 + 𝑏 = −1

• Substitute 𝑤1with 𝑤2

• H1: 𝑤2 1 + 𝑤2 2 + 𝑏 = 1

• H2: 𝑤2 3 + 𝑤2 4 + 𝑏 = −1

❖ Solving these equations, we get: 𝑤1 = 𝑤2 = −1/2, and 𝑏 = 5/2

❖ Summary of results:

• 𝐖 = 𝒘𝟏, 𝒘𝟐 = − 𝟏

𝟐 , −

𝟏

𝟐 ; 𝑊 = −

1

2

2 + −

1

2

2 =

1

2

• Margin 𝑑 = 2

| 𝑊 | =

2 1

2

= 2 2 ≈ 2.8284

• Equations are:

Finding Decision Boundary : Example 1

H1 and H2 are the planes:

• H1: 𝐖. 𝐗 + 𝑏 = +1

• H2: 𝐖. 𝐗 + 𝑏 = −1

Note: The 𝑊 vector is always orthogonal

to the H0 line and in the direction of the

+ve data points (or H1 line).

Since 𝑊 points always to the positive

samples (i.e. points south-west), this means

𝑤2 should be negative and 𝑤1 should be

negative.

H1: − 𝟏

𝟐 𝒙𝟏 −

𝟏

𝟐 𝒙𝟐 +

𝟓

𝟐 = +𝟏,

H2: − 𝟏

𝟐 𝒙𝟏 −

𝟏

𝟐 𝒙𝟐 +

𝟓

𝟐 = −𝟏,

H0: − 𝟏

𝟐 𝒙𝟏 −

𝟏

𝟐 𝒙𝟐 +

𝟓

𝟐 = 𝟎

H2

H1

H0

Topic 3 COE 292 Introduction to Artificial Intelligence 78

❖ In linear algebra, to find the equation of H, we use

the point p2 with the slope (m2 = -1)

❖ For slope 𝑚2 = −1, using slope-point formula

𝑚2 = (𝑥2−𝑥′

2)

(𝑥1−𝑥′ 1)

• H1 : 𝑥2 + 𝑥1 − 3 = 0

❖ Similarly, for H2, we will get

• H2: 𝑥2 + 𝑥1 − 7 = 0

❖ However, equations of H1 or H2 do not specify

the values of 𝑤1 and 𝑤2. Why? They tell the

direction of the vector w. They merely specify the

relationship between 𝑤1 and 𝑤2. 𝑤1

𝑤2 =

1

1 → 𝑤1 = 𝑤2

❖ 𝑤1 and 𝑤2 must satisfy the equations of H0, H1, and H2

Finding Decision Boundary : Example 1

The margin = −7− −3

12+12 =

2 2 ≈ 2.8284

H1: 𝑊𝑋 + 𝑏 = +1 H2: 𝑊𝑋 + 𝑏 = −1

One can verify the margin 𝑑 using

the distance between two parallel

lines formula as:

H2

H1

H0

Note: the perpendicular distance between the two parallel lines: 𝑎𝑥2 + 𝑏𝑥1 + 𝑐1 = 0 and 𝑎𝑥2 + 𝑏𝑥1 + 𝑐2 = 0 is given by 𝑐2−𝑐1

𝑎2+𝑏2

Topic 3 COE 292 Introduction to Artificial Intelligence 79

❖ Find the decision boundary and the margin of the SVM

classifier shown below?

❖ Step1: Find H1 slope

▪𝑚 = 1−2

2−4 → 𝑚 =

1

2

• Find the relation between w1 and w2

• 𝑤1

𝑤2 =

−1

2 → 𝑤2 = −2𝑤1

Pop-up Question

𝑤 = 𝑤1, 𝑤2 = 2

5 , −

4

5

H1: 2

5 𝑥1 −

4

5 𝑥2 + 1 = +1

H0: 2

5 𝑥2 −

4

5 𝑥2 + 1 = 0

H2: 2

5 𝑥1 −

4

5 𝑥2 + 1 = −1Slope of 𝑾 is equal to =

𝒘𝟐

𝒘𝟏

Slope of 𝑯𝟏 is equal to = − 𝒘𝟏

𝒘𝟐

Topic 3 COE 292 Introduction to Artificial Intelligence 80

Topic 3 COE 292 Introduction to Artificial Intelligence 81

❖ Step2: Now, we have the following equations:𝑤2 = −2𝑤1

• H1: 𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = 1 𝑢𝑠𝑖𝑛𝑔 4,2 , 𝑤𝑒 𝑔𝑒𝑡 4𝑤1 + 2𝑤2 + 𝑏 = 1

• H2: 𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = −1 𝑢𝑠𝑖𝑛𝑔 3,4 , 𝑤𝑒 𝑔𝑒𝑡 3𝑤1 + 4𝑤2 + 𝑏 = −1

• Substitute 𝑤2with − 2𝑤1

• H1: 4𝑤1 − 4𝑤1 + 𝑏 = 1 → 𝑏 = 1

• H2: 3𝑤1 − 8𝑤1 + 𝑏 = −1 → −5𝑤1 + 1 = −1 → 𝑤1 = −2

−5

❖ Solving these equations, we get: 𝑤2 = −2𝑤1= −4

5 , and 𝑏 =1

❖ Summary of results:

• 𝐖 = 𝒘𝟏, 𝒘𝟐 = 𝟐

𝟓 , −

𝟒

𝟓 ; 𝑊 = 𝑤1

2 + 𝑤2 2 =

4

25 +

16

25 =

4

5 =

2

5

• Margin 𝑑 = 2

| 𝑊 | =

2 2

5

= 5

• Equations are:

Pop-up Question

𝑤 = 𝑤1, 𝑤2 = 2

5 , −

4

5 H1:

2

5 𝑥1 −

4

5 𝑥2 + 1 = +1

H0: 2

5 𝑥2 −

4

5 𝑥2 + 1 = 0

H2: 2

5 𝑥1 −

4

5 𝑥2 + 1 = −1

Topic 3 COE 292 Introduction to Artificial Intelligence 82

❖ Note that lines H1 and H2 perpendicular to

line p1n1 can be SVM decision boundaries

ONLY AND ONLY IF there are no data

points that violate the margin (i.e. fall in

the area between H1 and H2), as in this

case.

• The points n1 and p1 are support vectors as

removing any one of them will result in

increasing the margin.

• While point (0, 3) lies on the line H1 but not in

the margin, it is not a support vector as it did

not prevent H1 from having the slope that

results in the maximum margin 𝑑.

Notes on Decision Boundary

H2

H1

H0

Support Vector Machines Example2: More than one set of support vectors

Topic 3 COE 292 Introduction to Artificial Intelligence 84

❖ If removing a vector results in increasing

the margin, then this vector is considered

a support vector. e.g. (3,4) , (1,2)

❖ However, removing a support vector may

NOT result in increasing the margin

❖ It might happen that removing individual

vectors will not increase the margin, but

removing a subset of them will result in

increasing the margin.

• In this case, some of the vector pairs in the

subset must be support vectors

Identification of Support Vectors

Note: NOT all points that lie on the decision boundaries are support vectors

Topic 3 COE 292 Introduction to Artificial Intelligence 85

❖ Using the previous explained method on the data

shown, we can arrive at the suggested H1 and

H2 on the right. The margin is to 2 2=2.8284

• When the lines H1 and H2 are made perpendicular

to line p1n1 →Two points p2=(0,2) and n2=(4,4) are

INSIDE the margin (violate the margin criterion!).

❖ Therefore, there is a need to tilt lines H1 and H2

such that these two points are not inside the

margin.

❖ Choose any point and adjust the slope so that the

point is OUTSDIE the margin.

❖ Repeat until all points are in the correct side of

the margin.

Support Vectors : Example 2

Topic 3 COE 292 Introduction to Artificial Intelligence 86

Support Vectors : Example 2 - Solution 1

removing both n2=(0,2) and p2=(4,4) allow the margin to be 2.8284

p2 and n2 will limit (i.e. reduce) the distance between H1 and H2

Either n2=(0,2) or p2=(4,4) NEED to be a support vector;

This graph chooses n2 This graph chooses p2

Solution 1 Solution 2

Topic 3 COE 292 Introduction to Artificial Intelligence 87

❖ Both solutions 1 and 2 are correct

❖ In both solutions:

• the vector (1,4) is a support vector as removing it

will increase the margin to 3

• the vector (3,2) is a support vector as removing it

will increase the margin to 3

• Removing only (0,2) will not increase the margin

• Removing only (4,4) will not increase the margin

❖ However, removing both (0,2) and (4,4) will

result in margin violation (points in the

wrong side of the margin) (the margin is

2.83). Thus, one of the vectors (0,2) (

solution 1) or (4,4) ( solution 2) needs to be

a support vector

Support Vectors : Example 2

Topic 3 COE 292 Introduction to Artificial Intelligence 88

❖ Step1: Find H2 slope (1,4), (0,2)

▪ 𝑚 = 4−2

1−0 → 𝑚 = 2

• Find the relation between w1 and w2

• - 𝑤1

𝑤2 = 2 → 𝑤1 = −2𝑤2

❖ Step2: Now, we have the following equations: w1 = −2w2

• H1:𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = 1 𝑢𝑠𝑖𝑛𝑔 3,2 , 𝑤𝑒 𝑔𝑒𝑡 𝑤1 3 + 𝑤2 2 + 𝑏 = 1

• H2:𝑤1𝑥1 + 𝑤2𝑥2 + 𝑏 = −1 𝑢𝑠𝑖𝑛𝑔 1,4 , 𝑤𝑒 𝑔𝑒𝑡 𝑤1 1 + 𝑤2 4 + 𝑏 = −1

• Substitute 𝑤1with 𝑤2

• H1: −2𝑤2 3 + 𝑤2 2 + 𝑏 = 1

• H2: −2𝑤2 1 + 𝑤2 4 + 𝑏 = −1

❖ Solving these equations, we get: 𝑤2 = −1/3, and 𝑏 = −1/3

❖ Summary of results:

• 𝐖 = 𝒘𝟏, 𝒘𝟐 = 𝟐

𝟑 , −

𝟏

𝟑 ; 𝑊 = −

2

3

2 + −

1

3

2 =

5

3

• Margin 𝑑 = 2

| 𝑊 | =

2

5

3

= 6

5 = 2.6831

Decision Boundary: Example 2

H1: −4𝑤2 + 𝑏 = 1 H2: 2𝑤2 + 𝑏 = −1

H1: 2

3 𝑥1 −

1

3 𝑥2 −

1

3 = +1

H0: 2

3 𝑥1 −

1

3 𝑥2 −

1

3 =0

H2: 2

3 𝑥1 −

1

3 𝑥2 −

1

3 = −1

Topic 3 COE 292 Introduction to Artificial Intelligence 89

❖ Identify the support vectors in the SVM figure below?

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 90

❖ Find the two closest points that belong to different classes; Let

these points be p1 and n1.

❖ Find the slope (m1) of the perpendicular line connecting these

two points

❖ Find the equation of H1 and H2 using point slope formula with

slope 𝑚2 = −1/𝑚1

❖ If

• NO points violate the margin criterion, then the maximum margin classifier is

obtained

• THERE ARE multiple points that violate the margin, Go to step 5;

▪ Gradually adjust the margin boundaries (i.e. H1 and H2 lines) until NO point is

violating the margin lines. You can use your tilted H1 and H2 to compute 𝑊.

Summary of SVM Steps for finding Largest Margin

Topic 3 COE 292 Introduction to Artificial Intelligence 91

1. Select ANY two points on the lines of the maximum decision

boundary, such that one is on H1, call it a, and the other on H2 call it

b, such that a is the CLOSEST point to b and b is the CLOSEST

point to a.

2. Draw auxiliary margin (perpendicular to the line connecting a to b)

3. If (a) There are no points that violate the auxiliary margin, then the

support vectors are only a and b.

4. (b) There are point(s) violate the auxiliary margin, then the support

vectors are: a, b and one of the points that violate the auxiliary

margin if they lie on H1 or H2 of the obtained maximum margin

classifier

Note: Clearly you can find multiple different sets of support vectors

following the above 4 steps.

Summary of SVM Steps for Support Vector Identification

Topic 3 COE 292 Introduction to Artificial Intelligence 92

❖ Let X be a set of vectors lying on the margins (boundaries) of

the hyperplanes H₁ and H₂, and let Y represent all other vectors

on those same boundaries but not included in X. The vectors in

X qualify as support vectors if the following conditions are

both satisfied:

1. Irrelevance of Y: Removing all vectors in Y does not change (i.e.,

increase) the margin.

2. Essentiality of Each v ∈ X: Removing all vectors in Y and removing any

single vector v ∈ X results in an increase in the margin.

How to TEST for Support Vectors?

Topic 3 COE 292 Introduction to Artificial Intelligence 93

❖ Identify the support vectors in the SVM figure below?

• Closest two points: (p1,n1) or (p2, n2) or (p3,n3) or (p4,n4)

• Selection 1: If we consider (p1,n1) as support vectors, and draw the

margins H1 and H2, no point violate the margin criteria →These are the

final decision boundaries and hence (p1 and n1) are only the support

vectors

Example 3: Identifying Support Vectors

• Similarly, if we select (p2, n2), they are

only the support vectors

• Similarly, if we select (p3, n3), they are

only the support vectors

• Similarly, if we select (p4, n4), they are

only the support vectors

p1 p2 p3 p4

n1 n2 n3 n4

(p1,n1) or (p2,n2) or (p3,n3) or (p4,n4)

Note removing BOTH of these support vectors DOES NOT increase the margin!

For this problem:

Distance (p1, n1) = 3.0

𝑊 = (0, 2/3); Margin = 3.0

H1: 0 𝑥1 + 2

3 𝑥2 + −

5

3 = +1

H2: 0 𝑥1 + 2

3 𝑥2 + −

5

3 = −1

Topic 3 COE 292 Introduction to Artificial Intelligence 94

p1 p2 p3 p4

n1 n2 n3 n4

Topic 3 COE 292 Introduction to Artificial Intelligence 95

❖ Let X={p1,n1} and Y={p2,p3,p4,n2,n3,n4}

• Removing all vectors in Y does not increase the margin

• Removing all vectors in Y and p1 increases the margin

• Removing all vectors in Y and n1 increases the margin

• Thus, X={p1,n1} is a set of support vectors.

❖ Let X={p2,n1} and Y={p1,p3,p4,n2,n3,n4}

• Removing all vectors in Y increases the margin from 3 to

3.1623. distance between p2 and n1

• Thus, X={p2,n1} is NOT a set of support vectors.

Example 3: Checking Support Vectors

p1 p2 p3 p4

n1 n2 n3 n4

Topic 3 COE 292 Introduction to Artificial Intelligence 96

❖ Identify the support vectors in the SVM figure below?

❖ Selection 1: One can select p3 and n3 as support vectors,

as they are closest to each other;

• This makes point n2 and n1 violating the margin as shown in

figure

• Hence, we can have {p3, n3, n1} or {p3, n3, n2} as support

vectors

❖ Selection 2: Another selection could be selecting p1 and

n1 as support vectors as they are closest to each other.

• This makes point p2, n2, and n3 violate the margin as shown in

figure

• Hence, we can have {p1, n1, p2}, {p1, n1, n2}, or {p1, n1, n3}

as support vectors

• Several sets may exist depending on your initial selection of a

support vector.

Example 4: Identifying Support Vectors

p1

p2

p3

n3

n2

n1

Auxiliary margin lines perpendicular to line p3 n3

p1

p2

p3

n3

n2

n1

Auxiliary margin lines perpendicular to line p1 n1

Topic 3 COE 292 Introduction to Artificial Intelligence 97

p1

p2

p3

n3

n2

n1

Auxiliary margin lines perpendicular to line p3 n3

p1

p2

p3

n3

n2

n1

Auxiliary margin lines perpendicular to line p1 n1

Topic 3 COE 292 Introduction to Artificial Intelligence 98

❖ Let X={p3, n3, n1} and Y={p1,p2,n2}

• Removing all vectors in Y does not increase

the margin

• Removing all vectors in Y and p3 increases

the margin to 4.024

• Removing all vectors in Y and n3 increases

the margin to 4.217

• Removing all vectors in Y and n1 increases

the margin to 2.6926

• Thus, X={p3, n3, n1} is a set of support

vectors.

Example 4: Checking Support Vectors

p1

p2

p3

n3

n2

n1

Auxiliary margin lines perpendicular to line p3 n3

For this problem:

Distance (p3, n3) = 2.6926 Distance (p1, n1) = 2.8284

𝑊 = ( −2

3 ,

1

3 ); Margin = 2.68

H1: −2

3 𝑥1 +

1

3 𝑥2 +

1

3 = +1

H2: −2

3 𝑥1 +

1

3 𝑥2 +

1

3 = −1

Topic 3 COE 292 Introduction to Artificial Intelligence 99

p1

p2

p3

n3

n2

n1

Auxiliary margin lines perpendicular to line p3 n3

Topic 3 COE 292 Introduction to Artificial Intelligence 100

❖ Graph below shows data representing mouse weights:

• red dots = non-obese (Class 1), green dots = obese (Class 2).

❖ Using SVM, Maximum Margin Classifier, we can find

the best line that classifies the data points as being

obese or not as shown below.

Support Vector Machines – 1D Example

Topic 3 COE 292 Introduction to Artificial Intelligence 101

❖ What if our training data looked like this?

❖ There is an outlier that will cause the Maximum

Marginal Classifier to look like this.

❖ The outlier node is classified as not obese but lies

much closer to the obese.

Support Vector Machines: Hard vs Soft Margin

Topic 3 COE 292 Introduction to Artificial Intelligence 102

❖ 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 and closer to the obese.

❖ The Maximum Marginal Classifiers are very sensitive

to outliers.

❖ What can we do about it?

Support Vector Machines: Hard vs Soft Margin

Topic 3 COE 292 Introduction to Artificial Intelligence 103

❖ 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 margin is called a

soft margin.

❖ When we use a soft margin to classify the data, we often refer

to it as Support Vector Classifier.

Support Vector Machines: Hard vs Soft Margin

Best soft margin is found

using cross validation

Topic 3 COE 292 Introduction to Artificial Intelligence 104

❖ Hard Margin refers to that kind of decision boundary that

makes sure that all the data points are classified correctly.

❖ It can also cause the margins to shrink thus making the whole

purpose of running an SVM algorithm futile

• The data is noisy (outliers)

Hard Margin Vs. Soft Margin

Soft margin allows some misclassification

error.

Hard margin does not allow any

misclassification error.

Topic 3 COE 292 Introduction to Artificial Intelligence 105

❖ 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.

Support Vector Classifiers

Topic 3 COE 292 Introduction to Artificial Intelligence 106

❖ 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

(𝑛 − 1) dimensional hyperplane.

Linear Separability

❖ Many real-world problems are not linearly separable in the original feature space

but separable by a nonlinear boundary.

❖ One common way to learning a nonlinear model is to introduce nonlinearity into the

feature space through a transformation.

❖ This is done using a mapping function 𝜙 which transforms the original features

into a new set of features.

Topic 3 COE 292 Introduction to Artificial Intelligence 107

❖ Suppose we have the data of a drug dosage where the red

dots represent patients that got not cured while the green

dot represents 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 data? Finding a line that

separates classes becomes infeasible

Linear Separability: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 108

❖ Transform the problem to a higher

dimension by mapping the data

using the function 𝜙(𝑥) = (𝑥, 𝑥2)

❖ Plotting the 2-D data we get the

figure on the right

Linear Separability: Example

❖We now can draw a support vector classifier and use it to

classify a new point (𝑥,𝑥2); if it's above the classifier line, the

dosage won't cure, and if below, it will.

❖ In general, taking the data to a higher dimension may lead to

better classification.

Topic 3 COE 292 Introduction to Artificial Intelligence 109

❖ Kernels are a set of functions used to

transform data from lower dimension to

higher dimension

❖ SVM uses several kernels to map data to

higher dimensions

❖ Examples:

• Linear:

K 𝑥, 𝑦 → 𝑥𝑦

• Polynomial Kernel of degree up to d:

K 𝑥, 𝑦 → 1 + 𝑥𝑦 𝑑

• Radial Basis Function (RBF):

K 𝑥, 𝑦 → 𝑒𝑥𝑝 − 𝑥−𝑦 2

2𝜎2

❖ We just must try each one to find the best

kernel for the considered data set

Linear Separability: The Kernel Trick

Topic 3 COE 292 Introduction to Artificial Intelligence 110

❖ Given a set of non-linearly separable points.

• Transform the data using a kernel

• Find a SVM classifier

• Project back to original space

Linear Separability: The Kernel Trick

Topic 3 COE 292 Introduction to Artificial Intelligence 111

❖ Regularization capabilities: SVM has good

generalization capabilities which prevent it from over-

fitting.

❖ Handles non-linear data efficiently: SVM can

efficiently handle non-linear data using Kernel trick.

❖ Stability: A small change to the data does not greatly

affect the hyperplane and hence the SVM. So, the

SVM model is stable.

❖ Optimality: SVM has a nature of Convex

Optimization which helps in finding globally best

model.

Advantages of SVMs

Topic 3 COE 292 Introduction to Artificial Intelligence 112

❖ A bakery owner wants a program that can classify recipes as

cupcakes or muffins.

Hands-On SVM: Recipes Classification

SVM_Muffin.ipynb

Topic 3 COE 292 Introduction to Artificial Intelligence 113

Hands-On SVM: Recipes Classification

Topic 3 COE 292 Introduction to Artificial Intelligence 114

Hands on: Banknote Authentication

for model Perceptron: Accuracy: 98.25%

for model SVC: Accuracy: 99.71%

for model KNeighborsClassifier: Accuracy: 99.71%

for model GaussianNB: Accuracy: 86.59%

Topic 3 COE 292 Introduction to Artificial Intelligence 115

❖ Using a loss function - calculate how good or poorly

our decision boundary performs

❖ Our objective is to minimize the loss

Model Evaluation

0-1 loss function: Number of misclassified points

L(actual, predicted) =

0 if actual = predicted,

1 otherwise

A loss function quantifies the difference between

a model's predictions and the observed values

Topic 3 COE 292 Introduction to Artificial Intelligence 116

❖ 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”

Model– Evaluation

Red(0) Blue(1)

Red(0) TN FP

Blue(1) FN TP

Classified As:

C o

rr ec

t La

b el

:

Red(-) Blue(+)

Red(-) 12 2

Blue(+) 2 14

Classified As:

C o

rr ec

t La

b el

:

Did the model get it right? True/False

What was the prediction? Positive/Negative

Topic 3 COE 292 Introduction to Artificial Intelligence 117

❖ The confusion matrix below summarizes the observed and

predicted outcomes from a classification model. Fill in the

table and match each value with the appropriate definition?

Popup Question

Definition Value

True positive

True negative

False positive

False negative

Predicted (0) Predicted (1)

Actual (0) 30 1

Actual (1) 7 2

Topic 3 COE 292 Introduction to Artificial Intelligence 118

❖ Several evaluation metrics may be used; Three basic ones are:

❖ Precision: Out of all the examples that predicted as positive, how many are positive? The proportion of correct positive predictions

❖ Recall: Out of all the positive examples, how many are predicted as positive? the proportion of correctly predicted positive instances

Model– Evaluation

Accuracy = TP + TN

TP + TN + FP + FN

Precision = TP

TP + FP

Recall = TP

TP + FN

If recall/precision is 0, what does it mean?

If recall/precision is 100, what does it mean?

precision and recall often show an inverse relationship, where improving one of them worsens the other.

+ -

+ TP FN

- FP TN

Topic 3 COE 292 Introduction to Artificial Intelligence 119

❖ From the confusion matrix below, calculate the recall,

precision and the accuracy of the classifier?

Popup Question

Precision

Accuracy

Recall

Predicted

(1)

Predicted

(0)

Actual (1) 2 7

Actual (0) 1 30

Topic 3 COE 292 Introduction to Artificial Intelligence 120

❖ Fill in the table below so that it satisfies each of the

following conditions:

• the recall is 100%?

• the precision is 100%?

• Recall is 0%

• Precision is 0%

• both recall and precision are 100%?

• Accuracy is 0%

Popup Question

Predicted

(1+)

Predicted

(-0)

Actual

(+1)

Actual

(-0)

If recall/precision is 0, what does

it mean?

If recall/precision is 100, what

does it mean?

Topic 3 COE 292 Introduction to Artificial Intelligence 121

❖ Accuracy measure is not good when the data is imbalanced

• A model can achieve high accuracy by simply predicting the

majority class all the time—but it's not performing well.

❖ Example: Consider that we are building a model to predict

whether a pilot will land safely or crash.

❖ Example:

• 100 data samples

▪ 90 +ve samples for landing safely

▪ 10 –ve samples for crashing);

• ML algorithm correctly classifies all +ve samples (i.e. TPs);

• but all –ve samples are misclassified as FPs

• TP = 90, TN = 0, FP = 10, and FN = 0;

• Accuracy = (90+0)/(90+0+10+0) = 90%

Model– Evaluation

Even when the model fails to predict any

crashes, its accuracy could be 90%!

Topic 3 COE 292 Introduction to Artificial Intelligence 122

❖ All the measures give us important information about how well

is our classification model.

Model– Evaluation

Measure When is it better? Example

Recall it is important to minimize

false-negatives (ideally

should be zero)

Missing a positive case

(False Negative) is very

costly or dangerous

+ve samples (cancer exists) while –ve samples

(cancer does not exist).

False-negatives (FNs) are cases where cancer

exists but identified as “no cancer”!

Precision it is important to minimize

false-positives (ideally

should be zero)

False positives are

expensive or problematic

+ve samples (email is SPAM) while –ve

samples (email is not SPAM) .

False positive (FP): a not-spam email ends up

being blocked/identified as a SPAM email.

Precision = TP

TP + FP Recall =

TP

TP + FN

Topic 3 COE 292 Introduction to Artificial Intelligence 123

❖ Considering the figure below with 9 points and the

classifier W =(w0, w1, w2) = (−1, −1, 1), what is

confusion matrix and the accuracy of the classifier?

Pop-up Question

Accuracy is 5/9

Recall is 2/5

+ -

+ 2 3

- 1 3

Precision is 2/3

+ -

+ TP FN

- FP TN

Precision = TP/(TP + FP)

Recall = TP/(TP + FN)

Classified As:

A ct

u al

Topic 3 COE 292 Introduction to Artificial Intelligence 124

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 125

❖ The accuracy of the perceptron is 100% if …..?

❖ Only recall is 100% if ………..

❖ Only precision is 100% if ………

Pop-up Question

+ -

+ TP FN

- FP TN

+ -

+ TP FN

- FP TN

Topic 3 COE 292 Introduction to Artificial Intelligence 126

❖ The accuracy of the perceptron is 100% if …..?

❖ Only recall is 100% if ………..

❖ Only precision is 100% if ………

Pop-up Question

+ -

+ TP FN

- FP TN

+ -

+ TP FN

- FP TN

Model Training and Cross Validation

Topic 3 COE 292 Introduction to Artificial Intelligence 128

❖ 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

Training and Testing

data

Trained

Model

T ra

in in

g

Trained

Model

Predicted

output New data

T es

ti n

g

Topic 3 COE 292 Introduction to Artificial Intelligence 129

❖ Therefore, in Machine Learning:

• We need the data to train the 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

Training and Testing

Topic 3 COE 292 Introduction to Artificial Intelligence 130

❖ 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?

❖ Training and testing machine learning models on a single

testing set can be misleading and sometimes yield overly

optimistic results.

Training and Testing

Training Set Testing Set

Training SetTesting Set

This one or this one

Training Set Testing Set

Topic 3 COE 292 Introduction to Artificial Intelligence 131

❖ 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 FOLDS

Cross-validation

❖ Example: a Five-Fold cross validation: the data is divided into FIVE equal sets as

shown below:

Cross-validation uses different subsets of the

data for training and testing

Learned parameters are not utilized from one round to the next; Each round is completely independent of

the other rounds in terms of ML parameters.

Topic 3 COE 292 Introduction to Artificial Intelligence 132

❖ 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

Cross-validation

Topic 3 COE 292 Introduction to Artificial Intelligence 133

❖ 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?

Underfitting and Overfitting

Topic 3 COE 292 Introduction to Artificial Intelligence 134

❖ 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

Underfitting and Overfitting

Oversimplifies the complexity in the data

Topic 3 COE 292 Introduction to Artificial Intelligence 135

❖ 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

Underfitting and Overfitting

Topic 3 COE 292 Introduction to Artificial Intelligence 136

❖ Idea 2:

• We can find the "wavey" curve

that best fits all the points in the

training set as shown below:

❖ Now if we use the curve with

test data, we get the

following:

• As can be seen that many test

points are not classified correctly.

• This is what we call Overfitting

Underfitting and Overfitting

Fits the varying

training data

very well

Does not do well

with the testing data

Topic 3 COE 292 Introduction to Artificial Intelligence 137

❖ 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

❖ Ideal Model:

• The ideal model achieves a balance between underfitting and overfitting

— it's complex enough to capture the underlying structure but simple

enough to generalize to unseen data.

Underfitting and Overfitting

Topic 3 COE 292 Introduction to Artificial Intelligence 138

❖ Overfitting

• A model learns the training data too well,

including noise and outliers.

• As a result, it performs very well on training

data but poorly on unseen test data.

• It generates a low error rate on the training

set and high error are on testing set

❖ Underfitting

• The model is too simple and cannot capture

the relationship between the input and

output variables accurately. Why?

• As a result, it performs poorly on both the

training data and the test data

• It generates a high error rate on both the

training set and testing set ( unseen data)

Underfitting and Overfitting Typically, the testing error is higher than the training error

Topic 3 COE 292 Introduction to Artificial Intelligence 139

Underfitting and Overfitting: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 140

❖ Which of the following statements represents

overfitting, based on the given accuracies of the

training and testing samples?

(a) Training Accuracy = 80%, Testing Accuracy = 78%

(b) Training Accuracy = 98%, Testing Accuracy = 78%

(c) Training Accuracy = 78%, Testing Accuracy = 98%

(d) Training Accuracy = 98%, Testing Accuracy = 96%

Pop-up Question

(b) Training Accuracy = 98%, Testing Accuracy = 78%

Unsupervised Learning

Topic 3 COE 292 Introduction to Artificial Intelligence 142

❖ 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 (to be covered later)

❖ Applications

• Clustering

• Finding patterns in data

• Data compression

• Retrieving similar objects

• Exploratory data analysis

• Generating new examples

Unsupervised Learning

Topic 3 COE 292 Introduction to Artificial Intelligence 143

❖ Assume that we have 12 items that are described by two

features: Feature A and Feature B.

❖ Using visualization, scatterplot, we can start to see some

patterns emerge simply based on visual inspection.

• By evaluating how close each of the items are to each other,

we can group them into three distinct clusters

Unsupervised Learning

Topic 3 COE 292 Introduction to Artificial Intelligence 144

❖ The Clustering Problem

• Organizing a set of objects into groups in such a way that similar

objects fall in the same group

• Items within a particular cluster are as similar as possible

• Items within one cluster are as dissimilar as possible with items in

other clusters

• The degree of similarity between two items is often quantified

based on a distance measure, e.g.. Euclidean distance

❖ Some Clustering Applications

• Market research, Image segmentation, Medical imaging, Social

network analysis, Genetic research.

Unsupervised Learning It is based on how similar the items within a cluster are

and how different they are from items in other clusters.

Topic 3 COE 292 Introduction to Artificial Intelligence 145

❖ An algorithm partitions 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

k-means Clustering: The Idea

Topic 3 COE 292 Introduction to Artificial Intelligence 146

❖ Given n items, let’s assume that the items in the

dataset are to be grouped into k different clusters.

K-Means Clustering Algorithm

1. Choose k random points as the initial centers for the clusters.

2. Each item is assigned to the cluster that is represented by the

center closest to it.

3. Re-calculate the true center for each cluster.

4. Repeat step 2 and 3 until convergence

Topic 3 COE 292 Introduction to Artificial Intelligence 147

❖ Step 1

• Suppose we want 3 clusters, i.e. 𝑘 = 3

• 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’s represents the mean of that cluster

k-Means Clustering - Example

Topic 3 COE 292 Introduction to Artificial Intelligence 148

❖ Step 2

• Next, assign every point to a cluster based on which cluster

center it is closest to; measure distance

▪These will be the initial clusters based on our first initial

random centers

• Question: How can we improve?

k-Means Clustering - Example

Topic 3 COE 292 Introduction to Artificial Intelligence 149

❖ Step 3:

• Re-compute the centers

(means) of the clusters

• Mid point

▪( σ 𝑥

𝑛 ,

σ 𝑦

𝑛 )

❖ Step 4

• Re-assign points based

on the new centers

(means) of the clusters

k-Means Clustering - Example

Topic 3 COE 292 Introduction to Artificial Intelligence 150

❖ 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

k-Means Clustering - Example

Final Clusters …

Topic 3 COE 292 Introduction to Artificial Intelligence 151

❖ Pros

• Simple to understand

• Easy to implement

• Guarantees convergence

K-Means Clustering: Pros and Cons

❖ Cons

• Choosing k manually,

requires knowledge about

the problem domain

• Sensitive to outliers

• Not good at modeling

clusters that have a complex

geometric shape

Topic 3 COE 292 Introduction to Artificial Intelligence 152

❖ What is the cluster center for the following 3 points

(2, 1), (3, 3), and (4, 3)?

Pop-up Question

𝑐𝑒𝑛𝑡𝑒𝑟 = 2 + 3 + 4

3 , 1 + 3 + 3

3 = (3,

7

3 )

Topic 3 COE 292 Introduction to Artificial Intelligence 153

❖ For the following data points and using 2-means

algorithm with initial cluster centers of c1 = (2, 2) and

c2 = (4, 4), What is the new cluster centers?

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 154

❖ Consider performing K-Means Clustering on a 1-D

dataset containing five sample points:

p1=5, p2=7, p3=10, p4=12 and p5=13. Using k = 2 and

the initial centroids are c1 = 3.0 and c2 = 15.0

❖ What are the initial cluster assignments? (Which

sample points are in cluster c1 and which sample

points are in cluster c2?

Pop-up Question

Cluster1 = {P1, P2}, Cluster2 = {P3, P4, P5}

Topic 3 COE 292 Introduction to Artificial Intelligence 155

Hands On K-means: Image Segmentation

Topic 3 COE 292 Introduction to Artificial Intelligence 156

Image Segmentation using K Means Clustering

Reinforcement Learning

SEMI-SUPERVISED LEARNING

Topic 3 COE 292 Introduction to Artificial Intelligence 158

❖ Reinforcement Learning is about

• learning the optimal behavior

• through interactions with environments

• to obtain maximum reward.

❖ Goal: Learn a function that maps from states to

actions

• The goal of any RL algorithm is to establish a policy that

maximizes the accumulative rewards.

❖ Similar to children exploring the world around them.

Reinforcement Learning

Topic 3 COE 292 Introduction to Artificial Intelligence 159

Motivation

Topic 3 COE 292 Introduction to Artificial Intelligence 160

❖ 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

Reinforcement Learning

Topic 3 COE 292 Introduction to Artificial Intelligence 161

❖ Examples: Robots learning to walk

• Robot learns through reward or punishment

Reinforcement Learning

https://www.youtube.com/watch?v=goxCjGPQH7U

https://www.youtube.com/watch?v=3gi6Ohnp9x8 https://www.youtube.com/watch?v=Rdm2ggtFvmQ

Topic 3 COE 292 Introduction to Artificial Intelligence 162

❖ Markov Decision Process (MDP): a formal method

to model decision-making, representing states,

actions, and their rewards

❖ A set of states: S - circles

❖ A set of actions: ACTIONS(s) – arrows

❖ A 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

Markov Decision Process

Topic 3 COE 292 Introduction to Artificial Intelligence 163

❖ Example: Simulated 4 x 4 world navigated by a robot

• Environment: 4 x 4 board

• Agent: Robot

• Actions:

▪move up, move down,

▪move right, and move left

• States:

▪ square (1,1), … square(4,5)

• Goal - green room

▪Agent receives reward

• Bad places- red rooms

▪Agent receives punishment

• Initially, the agent does not know what’s good or bad!

Markov Decision Process

Bad actions – avoid in future

Good action – take in future

Topic 3 COE 292 Introduction to Artificial Intelligence 164

❖ 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

Q-learning

Topic 3 COE 292 Introduction to Artificial Intelligence 165

❖ 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; rewards of taking

a later action

• Update Q(s, a) to take into account

▪old estimate

▪new estimate

Q-learning Overview

Topic 3 COE 292 Introduction to Artificial Intelligence 166

❖ Old value estimate = Q(s, a)

• What is the “new value estimate”?

❖ α is the learning rate [0,1]

• Controls how Q-function is updated

• Large α means we value new information more than old information

Q-learning method

❖ New value estimate:

• Immediate reward r received

after taking action a

• expected future reward

estimates from this state

onwards

Topic 3 COE 292 Introduction to Artificial Intelligence 167

❖ Future reward estimates:

• maxa' Q(s', a')

• maximum value across all possible

actions a’ taken from next state s’

Q-learning method

❖ Future reward estimates (variation):

▪ ϒ is parameter controlling how future

rewards are valued over immediate

rewards

decrementing 𝛾

Topic 3 COE 292 Introduction to Artificial Intelligence 168

❖ During 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)

• Is this the best policy? Why?

▪ 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

Greedy Decision-Making Policy

Topic 3 COE 292 Introduction to Artificial Intelligence 169

❖ Explore vs. Exploit

• Exploit: take the move with best reward

▪States and actions already learned

• Explore: try random move – it may

later give better reward.

▪Unknow states and actions to gather

new information

❖ What is the best value for ?

-Greedy Decision-Making Policy

-Greedy:

: how often we want to move randomly

With

probability

explore exploit

 1-

random move best known move A random move: from ALL possible moves not

excluding the best move. If  =1 ?, If  = 0?

Topic 3 COE 292 Introduction to Artificial Intelligence 170

❖ At the beginning of the algorithm,

• random moves → useful to help the agent learn about the

environment

• epsilon is initialized to 1

❖ Near the end of the training process,

• exploiting much more AND exploring much less

• try existing known good actions more and more

• DECREASE epsilon as the agent takes more and more steps

-Greedy Decision-Making Policy

Topic 3 COE 292 Introduction to Artificial Intelligence 171

❖ Start with Q(s, a) = 0 for all s, a

❖ For each episode (set of actions that starts on the initial state and ends on the goal state)

• While state is not a goal state:

▪At the current state s, take an action a, and move to the next state s’

▪Receive intermediate reward

▪Update the table entry for Q(s,a) as follows

▪ s  s’

Q-Learning Algorithm

𝑄 𝑠, 𝑎 ← 𝑄 𝑠, 𝑎 + 𝛼( 𝑅(𝑠, 𝑎) + 𝛾 𝑚𝑎𝑥𝑎′𝑄 𝑠′, 𝑎′ − 𝑄 𝑠, 𝑎 )

𝑖𝑓 𝛼 ==0 ?

𝑖𝑓 𝛼 == 1 ?

𝑖𝑓 𝛾 == 0 ?

Topic 3 COE 292 Introduction to Artificial Intelligence 172

❖ Consider a robot that needs to learn how to leave a house with the best path possible, on this example we have a house with 5 rooms, and 1 "exit" room.

❖ All rooms are nodes

❖ The arrows are the actions that can be taken on each node.

❖ The arrow values, are the immediate rewards that the agent receive by taking some action on a specific room.

Q-learning: Example

A

B

C

D

E

F

Topic 3 COE 292 Introduction to Artificial Intelligence 173

❖ We choose our reinforcement

learning environment to give

• 0 reward for all rooms that are not

the target room.

• 100 for the target room

❖ To summarize:

• States: A, B, C, D, E, F

• Actions: go to A, B, C, D, E, F

• Rewards: 0, 100

• Goal state: F

Q-learning: Example

A

B

C

D

E

F

Topic 3 COE 292 Introduction to Artificial Intelligence 174

❖ We have 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 𝛼 = 1 and ϒ = 0.8 ❖ 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

Q-learning: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 175

Q-learning: Example

Episode Q update

B→F Q(B,F) = R(B,F) + 0.8 *Max[Q(F,B), Q(F,E), Q(F,F)] = 100 + 0.8 * 0 = 100

D→B→F Q(D,B) = R(D,B) + 0.8 Max[Q(B,D), Q(B,F)] = 0 + 0.8[max(0,100)] = 80

Q(B,F) =R(B,F) + 0.8 Max[Q(F,B), Q(F,E), Q(F,F)] = 100 + 0.8 * 0 =100

→ →

𝑄 𝑠, 𝑎 ← 1 − 𝛼 𝑄 𝑠, 𝑎 + 𝛼 ( 𝑅(𝑠, 𝑎) + 𝛾 𝑚𝑎𝑥𝑎′𝑄 𝑠′, 𝑎′ )

This slide is a summary of the next 4 slides

Topic 3 COE 292 Introduction to Artificial Intelligence 176

❖ Episode: B, F • 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

▪ to go 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.

Q-learning: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 177

❖ Q(state,action) = R(state,action)+ ϒ Max[Q(next state, all

actions)]

• Q(B,F) = R(B,F)+ 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

Q-learning: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 178

❖ Episode: D, B, F

• For the next game, let us start 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[max(0,100)] =

80

• The Q matrix gets updated as shown.

Q-learning: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 179

❖ 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) =R(B,F)+ 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.

Q-learning: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 180

❖ 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

Q-learning: Example

Normalized Q matrix Final Q matrix

The Q-Value is the maximum expected reward an agent can reach by taking a given action A in the state S

Topic 3 COE 292 Introduction to Artificial Intelligence 181

❖ Using the Q matrix, the agent can reach the goal in an

optimum way. e.g. if we start at C, we choose the

actions C→D→B→F

Q-learning: Example

Topic 3 COE 292 Introduction to Artificial Intelligence 182

Pop-up Question

𝑄 𝑠, 𝑎 ← 1 − 𝛼 𝑄 𝑠, 𝑎 + 𝛼 ( 𝑅(𝑠, 𝑎) + 𝛾 𝑚𝑎𝑥𝑎′𝑄 𝑠′, 𝑎′ )

Topic 3 COE 292 Introduction to Artificial Intelligence 183

❖ Using Q0, what is the updated Q value after taking the

action (B, right)? The player receives a reward of +10

in F. For all other actions that do not lead to state F,

the reward is -1

Pop-up Question

𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 ← (1 − 0.5)𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 + 0.5( 𝑅(𝐵, 𝑟𝑖𝑔ℎ𝑡) + 0.5 𝑚𝑎𝑥𝑎′𝑄 𝑠′, 𝑎′ )

𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 ← 2.5 + 0.5 −1 + 0.5 ∗ max 7,5 = 2.5 − 0.5 + 1.75 = 3.75

𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 ← 𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 + 0.5( 𝑅(𝐵, 𝑟𝑖𝑔ℎ𝑡) + 0.5 𝑚𝑎𝑥𝑎′𝑄 𝑠′, 𝑎′ −𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 )

𝑄 𝐵, 𝑟𝑖𝑔ℎ𝑡 ← 5 + 0.5 −1 + 0.5 ∗ max 7,5 − 5 = 5 − 1.25 = 3.75

Topic 3 COE 292 Introduction to Artificial Intelligence 184

❖ Which action is supposed to be taken from state D if

Using Q0 as a starting point and

• a greedy decision-policy?

• ε-greedy decision-policy?

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 185

❖ If the agent is in state B, what is the maximum

expected reward it can achieve?

❖ If the agent in state B and uses the ϵ-Greedy decision-

making policy with ϵ = 0.8, what is the agent’s next

state?

Pop-up Question

Topic 3 COE 292 Introduction to Artificial Intelligence 186

❖ 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

❖ 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 piles, e.g. (1, 1, 4, 4)

• Action (i, j): represents the action of removing j items

from pile i

RL Example: Hands on nim

https://cs50.harvard.edu/ai/2020/weeks/4/

Demo: Watch video

Topic 3 COE 292 Introduction to Artificial Intelligence 187

Machine Learning Summary

Supervised Learning

Labelled data (instructive feedback)

Classification

Unsupervised Learning

Unlabeled data (no

feedback)

clustering

Reinforcement Learning

Rewards (evaluative feedback)

Playing games

Topic 3 COE 292 Introduction to Artificial Intelligence 188

❖ CS50’s Introduction to Artificial Intelligence with

Python

❖ https://www.youtube.com/watch?v=efR1C6CvhmE

❖ https://www.youtube.com/watch?v=_YPScrckx28

❖ https://www.youtube.com/watch?v=ny1iZ5A8ilA

❖ https://people.revoledu.com/kardi/tutorial/Reinforcem

entLearning/Q-Learning-Example.html

Credit and References