ML for Robotics

Duration: 300 min BCSE424L Dr. Harini S

Module 2: Supervised
Learning – I

• Chapters 3 and 6 of ”Machine Learning” by Tom Mitchel

• Chapters 4, 6, 15 of “Introduction to Machine Learning” by Alpaydin

Session Overview
• Linear Versus Non-Linear

• Multi-Class Versus Multi- Label Classification

• Linear Regression

• Multilinear Regression

• Naïve Bayes Classifier

• Decision Trees – ID3 – CART

• Fine tuning of algorithms for robotic environment.

Linear Versus
Session Non - Linear
Overview
Multi-Class
Session Versus Multi-Label
Overview
Parametric Versus Non Parametric
Algorithms
• A learning model that summarizes data with a set of
parameters of fixed size (independent of the number of
training examples) is called a parametric model.
• Linear and Multiple Regression
• Logistic Regression
• Linear Discriminant Analysis
• Perceptron
• Naive Bayes
• Simple Neural Networks
Parametric Versus Non Parametric
Algorithms
• Non-parametric learning algorithms are machine learning
algorithms that do not make explicit assumptions about the
functional form of the relationship between inputs and outputs.
• Non-parametric methods are particularly useful when the
underlying distribution of the data is not well-known or when the
relationship between inputs and outputs is highly complex and
cannot be adequately represented by a simple parametric model.
• Examples:
➢ Decision Tree
➢ Random Forest
➢ Support Vector Machines (SVM)
➢ K-Nearest Neighbors (KNN)
➢ Deep Neural Networks
 Regression

• Regression is a statistical way to establish a

relationship between a dependent variable and a set of
independent variable(s)
• e.g., if we say that
Age = 5 + Height * 10 + Weight * 13
• Here we are establishing a relationship between the
Height and weight of a person with his/ Her Age. This is
a very basic example of Regression.
Types of Regression
Simple Linear Regression

• Least Square “Linear Regression” is a statistical method to regress

the data with dependent variable having continuous values whereas
independent variables can have either continuous or categorical
values.
• In other words “Linear Regression” is a method to predict
dependent variable (Y) based on values of independent variables
(X).
• It can be used for the cases where we want to predict some
continuous quantity.
• E.g., Predicting traffic in a retail store, predicting a user’s dwell time
or number of pages visited on a website, etc
Linear Regression Formulae
Linear Regression Line
• While doing linear regression our objective is to fit a line through
the distribution which is nearest to most of the points. Hence
reducing the distance (error term) of data points from the fitted
line.
• For example, here, figure (left) dots represent various data points
and the line (right) represents an approximate line that can
explain the relationship between ‘x’ & ‘y’ axes.
• Through, linear regression we try to find out such a line. For
example, if we have one dependent variable ‘Y’ and one
independent variable ‘X’ – the relationship between ‘X’ & ‘Y’ can
be represented in the form of following equation:

Y = Β0 + Β1X
Where,
Y = Dependent Variable
X = Independent Variable
Β0 = Intercept
Β1 = Slope - Coefficient of relationship between ‘X’ & ‘Y’
Finding a Linear Regression Line
• Using a statistical tool e.g., Excel, R, SAS etc. you will directly find
constants (B0 and B1) as a result of linear regression function. But
conceptually as discussed it works on OLS concept and tries to reduce
the square of errors, using the very concept software packages
calculate these constants.

• For example, let say we want to predict ‘y’ from ‘x’ given in following
table and let’s assume that our regression equation will look like
“y=B0+B1*x”
Regression Equations
Steps to solve Linear Regression
1. Start with the linear model:

(one feature)

(multiple feature)

2. Compute the Error (Loss Function)

Error:

Loss Function:

3. Find w and b that minimize the loss

➢ Two ways to do : 1. Analytical Solution
2. Gradient Descent
1. Analytical Solution
• Works for small datasets
• Use the below mathematical equation directly

Weights/ Slope:

Bias/ Intercept:

• Substitute the values and get the values of w and b

• Not used when

• Data has many features
• Inversion becomes slow or unstable
Example
Common Error Measures in Linear Regression

• Basic residual Error • Mean Absolute • Mean Squared

Error (MAE) Error (MSE)

Average of absolute error – Most important → always

Treats all errors equally positive → large errors are
penalized more
Common Error Measures in Linear Regression

• Root Mean Squared • Mean Absolute

Error (RMSE) Percentage Error
(MAPE)

Same scale as input

Scale independent → easy
to explain percentage
2. Gradient Descent (Most common in ML)
• Initialize w and b with random values
• Compute Predictions
• Compute Loss (MSE):

• Compute Gradients (Slopes of the loss):

• Update Parameters using learning rate

• Continue updating until loss stops decreasing

Pros of Gradient Descent Method

• Gradient descent works even for large datasets

• Learning rate controls step size

• Final w and b represent the best-fit line

Multilinear Regression

• Multilinear Regression (also called Multiple Linear Regression) is an

extension of simple linear regression where one dependent variable

is predicted using two or more independent variables.

Multilinear Regression

• Multilinear Regression (also called Multiple Linear Regression) is an

extension of simple linear regression where one dependent variable

is predicted using two or more independent variables.

Multilinear Regression

• Multilinear Regression (also called Multiple Linear Regression) is an

extension of simple linear regression where one dependent variable

is predicted using two or more independent variables.

Coefficient Expression (in terms of matrix)

• Here, diagonal entries are not interaction

• Non – Diagonal entries mean, how much
they co-vary→ linear dependence
• Even though interaction is used, its
actually alignment

• In the previous slide, it was mentioned x1 → feature. Here x11 means value of first
feature in the first row
Numerical Example for Multi-Linear Regression

• Here, diagonal entries are not interaction

• Non – Diagonal entries mean, how much
they co-vary→ linear dependence
• Even though interaction is used, its
actually alignment

• In the previous slide, it was mentioned x1 → feature. Here x11 means value of first
feature in the first row
Alignment versus Interaction Versus Multicollinearity

• Alignment Alignment refers to how much the vectors of features

“point in the same direction” in the feature space
• Captured by:
➢ Correlation matrix
➢ Off-diagonal entries of 𝑋 𝑇 𝑋
• Interaction
• Interaction exists when the effect of one feature on the output depends on
another feature (multiple features jointly influence y)

• Multicollinearity : Multicollinearity occurs when one or more

independent variables in a regression model have a strong linear
relationship with other independent variables.
How Training works?

1. Initialize coefficients

2. Predict output using the equation

3. Compute loss (usually Mean Squared Error)

4. Update coefficients using Gradient Descent or Normal Equation

5. Repeat until loss is minimized

When to Use Regression (Linear)?
• Target is continuous

• Relationship is approximately linear

• Effect of each feature is additive

• Errors are reasonably well-behaved

• You need interpretability

• Dataset is small to medium

When Not to Use Regression (Linear)?

• Output is categorical

• Strong non-linear patterns

• High multicollinearity

• Many outliers

• Complex feature interactions

Naïve Bayes Classification
What will we learn?
• Why probabilistic classifiers?

• Real-world intuition:
• Spam filtering
• Medical diagnosis
• Text classification

• Core concept of Naïve Bayes Classifier

• Why Naïve?
Probability concepts (needed for Naive Bayes)
• Random variables

• Joint probability - probability of two (or more) events happening

together

• Conditional probability →event A occurring given that event B has

already occurred

• Marginal probability → probability of a single event without

considering other variables

• Bayes Theorem
Probability concepts (needed for Naive Bayes)

• Bayes Theorem

➢ Relates P(A|B) to P(B|A)

➢If we know P(A), given B, what will the P(B) given A?

➢ Posterior = (Likelihood * Prior) / Evidence

• Prior: What I believed before seeing the data (P(A))
• Evidence: Normalization so probabilities sum to 1 (P(B)) (marginal)
• Likelihood: How compatible is the data with my belief (P(B)|P(A))
Naïve Bayes Classifier

• Naïve Bayes Classifier finds the conditional probability of class given

features

• For a class C and feature vector X=(x_1,x_2,…,x_n):

Why is it called “Naive”?
• Computing P(C|X) is hard because features may be correlated

• So Naïve Bayes makes the below assumption (hence called naïve)

• Features are conditionally independent given the class (features may

be correlated but within class they behave independently)

• Why this assumption?

• If there are ‘n’ features, then the number of parameters (probability
calculation) will grow exponentially. But because of the above assumption,
2n becomes → 2n
Final Naive Bayes decision rule
Naïve Bayes Algorithm
• Naïve Bayes Algorithm (for discrete input
attributes) has two phases
– 1. Learning Phase: Given a training set S,
create probability tables for each attributes
Learning is easy,
just create
probability tables.

Output: conditional probability tables; for

elements Classification is easy, just multiply
probabilities
– 2. Test Phase: Given an unknown instance
, Look up tables to assign the label
Example
• Example: Play Tennis

38
 The learning phase for tennis
example
P(Play=Yes) = 9/14

P(Play=No) = 5/14

We have four variables, we calculate for

each

Outlook Play=Yes Play=No Temperature Play=Yes Play=No

Sunny 2/9 3/5 Hot 2/9 2/5
Overcast 4/9 0/5 Mild 4/9 2/5
Rain 3/9 2/5 Cool 3/9 1/5

Humidity Play=Yes Play=No Wind Play=Yes Play=No

High Strong 3/9 3/5
3/9 4/5
Normal Weak 6/9 2/5
6/9 1/5
 Example

• Given the data as found in last slide:

• Find for a new point in space (vector of values) to which group it

belongs (classify)

40
The test phase for the tennis example
• Test Phase
– Given a new instance of variable values,
x’=(Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong)
– Given calculated Look up tables
P(Outlook=Sunny|Play=Yes) = 2/9 P(Outlook=Sunny|Play=No) = 3/5
P(Temperature=Cool|Play=Yes) = 3/9 P(Temperature=Cool|Play==No) = 1/5
P(Huminity=High|Play=Yes) = 3/9 P(Huminity=High|Play=No) = 4/5
P(Wind=Strong|Play=Yes) = 3/9 P(Wind=Strong|Play=No) = 3/5
P(Play=Yes) = 9/14 P(Play=No) = 5/14

– Use the MAP rule to calculate Yes or No

P(Yes|x’): [P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes) = 0.0053

P(No|x’): [P(Sunny|No) P(Cool|No)P(High|No)P(Strong|No)]P(Play=No) = 0.0206
Example
• Learning Phase
P(Play=Yes) = 9/14 P(Play=No) = 5/14

Outlook Play=Yes Play=No Temperature Play=Yes Play=No

Sunny 2/9 3/5
Hot 2/9 2/5
Overcast 4/9 0/5
Mild 4/9 2/5
Rain 3/9 2/5
Cool 3/9 1/5

Humidity Play=Yes Play=No Wind Play=Yes Play=No

Strong 3/9 3/5
High 3/9 4/5 Weak 6/9 2/5
Normal 6/9 1/5
Test Phase
• Will Alice be able to play tennis when Outlook=Sunny,
Temperature=Cool, Humidity=High, Wind=Strong
Assume X=(Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong)
– Look up tables

P(Outlook=Sunny|Play=Yes) = 2/9 P(Outlook=Sunny|Play=No) = 3/5

P(Temperature=Cool|Play=Yes) = 3/9 P(Temperature=Cool|Play==No) = 1/5

P(Huminity=High|Play=Yes) = 3/9 P(Huminity=High|Play=No) = 4/5

P(Wind=Strong|Play=Yes) = 3/9 P(Wind=Strong|Play=No) = 3/5

P(Play=Yes) = 9/14 P(Play=No) = 5/14

– MAP rule
P(Yes|X): [P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes) = 0.0053 = 0.0053/(0.0053+0.0206) =0.2046

P(No|X): [P(Sunny|No) P(Cool|No)P(High|No)P(Strong|No)]P(Play=No) = 0.0206 = 0.0206 /(0.0053+0.0206) =0.7953

P(X|Yes) =P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes) =
P(Yes) = 9/14
P(X) = P(Yes|X)+P(No|X) =0.259
P(Yes|X) = 0.0053/ (0.0053+0.0206) = 0.204
 P(X|No) =P(Sunny|No)P(Cool|No)P(High|No)P(Strong|No)
P(No) = 5 /14
P(X) = P(Yes|X)+P(No|X) =0.259
P(No|X) = 0.0206/ (0.0053+0.0206) = 0.795

Will Alice be able to play tennis when Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong

No, She will not be able to play

Decision Trees
What will we learn?

• What is Decision Tree?

• Types of Decision Trees

• How does the tree decide the best question?

• Algorithm for Step by Step Tree Construction

• Stopping Criteria

• Gini Index and CART

• Overfitting

• Pros and Cons

 What is a decision tree?
• The core algorithm for building decision trees called ID3 (Iterative Dichotomiser 3)
by J. R. Quinlan employs a top-down, greedy search through the space of possible
branches with no backtracking.

• ID3 uses Entropy and Information Gain to construct a decision tree.

• Decision tree algorithm falls under the category of supervised learning.

• They can be used to solve both regression and classification problems.

Example
 Decision Tree Induction: An Example
age income student credit_rating buys_computer
❑ Training data set: Buys_computer <=30 high no fair no
❑ Resulting tree: <=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes
>40 low yes excellent no
age? 31…40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 overcast
31..40 >40 <=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no
student? yes credit rating?

no yes excellent fair

no yes yes
Components of a Decision Tree
Types of Decision Trees
• Classification Tree
• Output: category

• Example: Spam / Not spam

• Regression Tree
• Output: continuous value

• Example: House price

Algorithm for Decision Tree Induction
• Greedy algorithm that constructs decision tree in top- down, recursive, divide and
conquer manner

• Given: Training data set (data table) with distinguished class attribute

• This training set is recursively partitioned into smaller subsets as the tree is being
built
Algorithm for Decision Tree Induction
Stopping Criteria
Small Example (Manual creation of DT)
• Question: Shall we play outside?
Weather Temperature Play
Sunny Hot No
Rainy Mild Yes
Sunny Mild No
Rainy Cool Yes
• Try Splitting by weather (Pure group)
Weather
• Weather – Sunny→No

• Weather – Rainy → Yes Sunny Rainy

Play - No Play = Yes

• Try splitting by temperature
• Temperature – Hot → No

• Temperature –Cool → Yes

• Temperature – Mild → Both yes / No (Mixed, decision is not clear)

Basic Idea is to
• Minimize Confusion

• Maximize Purity

• Choosing the clearest decision first

• Entropy and Gini Automate the above process

Try Another Example
Weather Umbrella Play
Sunny No No
Rainy Yes Yes
Sunny No No
Rainy Yes Yes

• Question: Shall we play outside?

• Which one will you choose?

• Decision Trees are not Unique

• How to break the tie?

How algorithms break the tie?
• Choose the simpler feature

• Choose the feature appearing earlier

• Choose the feature with fewer branches

• Choose randomly
 More features example
ID Weather Temp Wind Homework Play
• Choose weather (Even though not 1 Sunny Hot Weak No No
2 Sunny Hot Strong Yes No
Perfect, it gives meaningful split) 3 Sunny Mild Weak No Yes
4 Sunny Cool Weak Yes Yes
• Then temp, wind and so on. 5 Rainy Mild Weak No Yes
Weather 6 Rainy Cool Strong Yes No
7 Rainy Mild Strong No No
Sunny Rainy 8 Rainy Cool Weak Yes Yes
Temp Wind

Mild Strong Weak

Hot Cool
Yes Yes No Yes
No
 Entropy and its use in Decision Tree
• Entropy = measure of confusion / uncertainty
➢Low entropy → clear decision
➢High entropy → mixed, confusing outcomes

• Why do we need entropy in decision trees?

➢Multiple features exist
➢None give an obviously perfect split
➢Human intuition can disagree
Brief Review of Entropy

m=2
More information on Entropy
• Entropy converts confusion into a number so that machines can
compare choices

Event Probability
• The negative sign ensures entropy ≥ 0 A 0.5
• Log2(pi) < 0 when 0 < pi < 1 B 0.001
In the above, Event B has
• Certain outcome → no surprise → no uncertainty more uncertainty (entropy)

• If an event has
probability 1, then its
• Rare outcome → big surprise → high uncertainty entropy will be 0
Information Gain (IG)
• Information Gain (IG) measures how much uncertainty is reduced after we
split the data using a feature.

• Information Gain = how much confusion is reduced

• Before split → data is confusing

• After split → data is less confusing

• Reduction in confusion = Information Gain

Attribute Selection Measure: Information Gain (ID3/C4.5)

◼ Select the attribute with the highest information gain

◼ Let pi be the probability that an arbitrary tuple in D belongs to
class Ci, estimated by |Ci, D|/|D|
◼ Expected information (Entropy)
m
needed to classify a tuple in D:
Info( D) = − pi log 2 ( pi )
i =1
◼ Information needed (after using A to split D into v partitions) to
classify D: v | D |
Info A ( D) = 
j
 Info( D j )
j =1 | D |

◼ Information gained by branching on attribute A

Gain(A) = Info(D) − InfoA(D)

In simple terms
• To build a decision tree we need to calculate two types of entropy
➢One for the whole dataset based on class label
➢Another for each attribute based on the class label.

• Then Information gain for each attribute is calculated

• The attribute with the highest value is chosen as the splitting

attribute.
Entropy for the overall dataset Info(D)
Age Income Student Credit Class
<=30 High No Fair No
<=30 High No Excellent No
<=30 Medium No Fair No
<=30 Low Yes Fair Yes m

<=30 Medium Yes Fair Yes Info( D) = − pi log 2 ( pi )

i =1
>40 Medium No Fair Yes
>40 Low Yes Fair Yes
>40 Low Yes Excellent No
>40 Medium Yes Fair Yes
>40 Medium No Excellent No
31 - 40 High No Fair Yes
31 - 40 Low Yes Excellent Yes
31 - 40 Medium No Excellent Yes
31 - 40 High Yes Fair Yes
Attributes in the Dataset

• Age
Entropy for each attribute in the dataset
• Income
is calculated using the below formulae
• Student and InfoA(D)
• Credit rating
v | Dj |
Info A ( D) =   Info( D j )
j =1 |D|

Information Gain of Attribute - Gain(A)

Gain(A) = Info(D) − InfoA(D)

Entropy for Age - InfoAge(D) v
Info A ( D) = 
| Dj |
 Info( D j )
j =1 |D|

Buys Computer
Age Yes No Dj
<=30 2 3 5
31 .. 40 4 0 4
>40 3 2 5
Entropy for Income - Infoincome(D)

Buys Computer
Income Yes No Dj
High 2 2 4
Medium 4 2 6
Low 3 1 4
Entropy for student - Infostudent(D)

Buys Computer
Student Yes No Dj
Yes 6 1 7
No 3 4 7
Entropy for credit rating – Infocredit rating(D)

Buys Computer
Credit Yes No Dj
Rating
Fair 6 2 8
Excellent 3 3 6
Choosing the split attribute
• Gain for all the attributes is calculated
• Gain (Age) = 0.246
• Gain( Income) = 0.029
• Gain( Student) = 0.152
• Gain ( Credit rating) = 0.0483

Choose the attribute with the highest gain as the splitting attribute
Gain (Age) = 0.246
Building the tree choosing age as the root
Building the tree choosing age as the root
Find the splitting attribute using T1
Entropy for the T1 - Info(T1)

Attributes in the Dataset T1

• Income
• Student
• Credit
Entropy for Income - Infoincome(T1)
Entropy for Student - Infostudent(T1)
Entropy for Credit_rating – Infocredit_rating(T1)
Information Gain (T1)
• Gain for all the attributes of T1 is calculated
• Gain( Income) = 0.571
• Gain( Student) = 0.971
• Gain ( Credit rating) = 0.021

Choose the attribute with the highest gain as the splitting attribute
Gain (student) = 0.971
Splitting T1
Splitting T1
Splitting T1
Find the splitting attribute using T2
Entropy for the T2 - Info(T2)

Attributes in the Dataset T2

• Income
• Student
• Credit
Entropy for Income - Infoincome(T2)
Entropy for Student - Infostudent(T2)
Entropy for Credit_rating – Infocredit_rating(T2)
Information Gain (T2)
• Gain for all the attributes of T2 is calculated
• Gain( Income) = 0.021
• Gain( Student) = 0.021
• Gain ( Credit rating) = 0.971

Choose the attribute with the highest gain as the splitting attribute
Gain (credit_rating) = 0.971
Splitting attribute in T2 – Credit Rating
Final Decision Tree – for All Electronics Problem
Decision for query given based on Decision Tree
IF Age <=30, Student =Yes, Credit rating =fair, Income = Medium

Will this person buy a computer or NOT = YES

Try for the below sample
CART (Classification And Regression Trees)
• CART builds a binary decision tree by recursively splitting the data to
make child nodes as pure as possible

• Tree type: Binary Tree

• Works for both numerical and categorical

• Gini Index
CART (Classification And Regression Trees)
• CART is a discriminative machine learning
• A discriminative model is a machine-learning model that directly learns the
boundary between classes and models

• Is Entropy based Decision tree, discriminative model?

• Yes

• Using Entropy or Gini separates the class directly without modeling P(x|y)
CART Process
1. Consider all the data at the root

2. Compute Gini Index for all split

3. Choose split with minimum weighted Gini

4. Repeat recursively until:

• Node is pure
Gini Index

• Gini Index measures node impurity — how mixed the classes are

• For a Node with K classes,

How proportion of class different from Probability?

• Example:
• Consider 1 red and 3 blue boxes
• Now proportion will be pred = ¼ and pblue = ¾
• Now Probability will be ”What’s the probability of picking the red box/blue
box?” Answer: ¼ and ¾ respectively. But the meaning in both the cases will be
different
• Will they ever be numerically Different?
Gini Values Interpretation

• Gini Index :0 → Pure

• Gini Index: 0.5 → 2 classes (50-50)

• Gini Index close to 1 → highly mixed

Example 1
• Parent Node Gini Sepal Length Midpoint
Sepal Length Class
Classes : A and B 4.9, 5.0 4.95
4.9 A
No. of A class: 3, No. of B class: 3 5.0, 5.1 5.05
5.0 A
5.1, 6.5 5.8
5.1 A • GiniParent = 1 – (0.52 + 0.52) = 0.5 6.5, 6.7 6.6
6.5 B
6.7, 6.8 6.75
6.7 B • Find mid point (Feature values
6.8 B should be sorted) Sepal
Length<=5.8

• Test the mid-point as split: Sepal

length < = 5.8, classify nodes (works Class A Class B
for this example, left Node: A, Right
Node B)
Example 2
ID Age Income Buys
• At root we have 5 samples
Computer • pyes = 3/5 = 0.6
? • pno =2/5 =0.4
1 25 50K No
2 30 60K No • Giniroot = 1 –(0.42+0.62) = 0.48
3 35 80K Yes
4 40 90K Yes
• Check split on Age and then
5 45 50K Yes

• Buys Computer?
 Example 2 – Split on Age
ID Age Midpoint • If we try Age <=32.5,
• Left Node : 25, 30 → Class No (Gini =0)
1 25 27.5 • Right Node : 35,40,45 → Class Yes (Gini =0)
2 30 • Weighted Gini : (2/5*0)+(3/5*0) =0
32.5 • If we try Age <=37.5
3 35 37.5 • Left Node : 25, 30, 35 → Class No and yes (Pno
4 40 42.5 =2/3, Pyes =1/3, Gini =0.444)
• Right Node : 40,45 → Class Yes (Gini =0)
5 45 - • Weighted Gini: 3/5*0.444+0 =0.2667

• In this case, weighted Gini of Age Age <= 32

=32.5 is better. It can be rounded

of to 32 and the split can be done
Class No Class Yes
 Example 3 – Try Root Split with “Age”
ID Age Income Buys • If we try Age <=32.5,
Computer • Left Node : Impure
?
• Right Node: Impure
1 25 50K No
2 30 60K Yes • Try Next Feature → Income

3 35 80K Yes Age <= 32

4 40 90K Yes
5 45 50K No Income Buys Income Buys
Computer? Compute
r?
• In this case, weighted Gini of Age 50K No 80K Yes
=32.5 is better. It can be rounded 60K Yes 90K Yes

of to 32 and the split can be done 50K No

Example 3 – Try Split with “Income”
• Try Next Feature → Income • Final Tree
• Left Node: Class No and Yes
Income Midpoint
Age <= 32
50K • 55K With 55K as threshold, two pure sub-branches
(No)
60K - Income
(Yes) Income <=
55K <=65K
• Right Node: Class Yes and No

Income Midpoint
• With 65k will have better weighted Gini
• Weighted Gini of 85K : right node gini is 0 Class No Class Yes Class No Class Yes
50K (No 65K
• Left node Gini Pno =1/3, Pyes =2/3 → 1-
80K 85K
(Yes) ((1/3)2+(2/3)2) =0.44
90K - • Weighted Gini of 65K: Both left and right node
(Yes)
Gini →0
Can you solve Example 3 with ID3?

• Numerical features needs to be discretized

• Age:
• Young - <=30
• Middle : 31-40
• Old > 40
CART and Categorical Data
ID Weather Wind Play • Gini at Root:
Tennis?
• Yes =3 , No = 3, GiniRoot = 1 –(3/6)2-(3/6)2 = 0.5
1 Sunny Weak No
2 Sunny Strong No • Now splitting with respect to weather:
• Category needs to be grouped
3 Overcast Weak Yes
• Let’s try Weather ∊ {overcast} vs {Sunny, Rain}
4 Rain Weak Yes • Left Node: Yes =2, No = 0, Gini = 1-(2/2)2-0 = 0
5 Rain Strong No • Right Node: Yes=1, No=3, Gini = 1-(1/4)2-(3/4)2 = 0.375
• Try another Weather ∊ {Sunny} vs {Overcast, Rain}
6 Overcast Strong Yes • Left Node: Yes = 0, No : 2, Gini = 0
• Play Tennis? • Right Node: Yes = 3, No=1→ Gini = 0.375
To choose which can be the • Try, Weather ∊ {Rain} vs {Overcast, Sunny}
• Left Node: Yes = 1, No : 1, Gini = 0.5
root split→ Weather / Wind?
• Right Node: Yes = 2, No=2→ Gini = 0.5
Calculate Gini Index for Weather Split
ID Weather Wind Play • Now splitting with respect to weather:
Tennis?
• Category needs to be grouped
1 Sunny Weak No • Let’s try Weather ∊ {overcast} vs {Sunny, Rain}
2 Sunny Strong No • Left Node: Yes =2, No = 0, Gini = 1-(2/2)2-0 = 0
• Right Node: Yes=1, No=3, Gini = 1-(1/4)2-(3/4)2 = 0.375
3 Overcast Weak Yes
4 Rain Weak Yes • Weighted Gini:
5 Rain Strong No • (2/6)*0+(4/6)*0.375 = 0.25

6 Overcast Strong Yes

GiniWeather = 0.25
• Play Tennis?
To choose which can be the
root split→ Weather / Wind?
Checking Wind for “Root Split”
ID Weather Wind Play • Now splitting with respect to Wind:
Tennis?
• Let’s try Wind ∊ {Weak} vs {Strong}
1 Sunny Weak No • Left Node: Yes =1, No = 2, Gini = 1-(1/3)2-(2/3)2 = 0.44
2 Sunny Strong No • Right Node: Yes=1, No=2, Gini = 1-(1/3)2-(2/3)2 = 0.44

3 Overcast Weak Yes • Weighted Gini:

4 Rain Weak Yes
(3/6) * 0.44 + (3/6)*0.44
5 Rain Strong No
Giniwind = 0.22 + 0.22 =0.44
6 Overcast Strong Yes
Giniwind =0.44

CART chooses GiniWeather since it has less Weighted Gini Index

After Root Split, Checking for next split
Weather = Overcast?
• Now splitting with respect to
remaining weather category.
No • Let’s try Weather ∊ {Sunny} vs
Yes
Weather Wind Play
{Rain}
Class = Yes Tennis? • Both {Sunny} Vs {Rain} and {Rain}
Sunny Weak No Vs { Sunny} yield the same
Sunny Strong No answer.
Rain Weak Yes • Sunny side of the branch will be
Rain Strong No
pure
• Rain side → Impure

To further classify the Rain side of the branch with Wind

After Root Split, Checking for next split
Weather = Overcast? • Now splitting with respect to
No
remaining wind category.
Yes • Let’s try Wind ∊ {Weak} vs
Class = Yes Weather = Sunny? {Strong}
• Both {Weak} Vs {Strong} and
Yes No
{Strong} Vs { Weak} yield the
Weather Wind Play
Class = No Tennis? same answer.
Rain Weak Yes • So split to class Yes and No
Rain Strong No considering Weak/Strong as
the split class
Now Building the tree

Weather = Overcast?

Yes No

Class = Yes Weather = Sunny?

Yes No

Class = No Wind = Weak?

Yes No

Class = Yes Class = No

Regression Tree
Tree-based model for predicting continuous output

• CART classification trees predict a class label, whereas CART regression trees
predict a continuous value.
Pruning in CART
CART grows a tree by greedy splitting until:

• Nodes are pure, or

• Stopping criteria are met

• This may lead to a deep tree → Overfitting, fitting noise data is a problem

• So Pruning can be used

Two types of Pruning
CART supports two pruning strategies:

• Pre-Pruning – During tree growth – stop early

• Post-Pruning – after full tree – cut back

Post Pruning
• Grow maximal tree (T0) with CART Method

• CART – Cost-Complexity Pruning

• Balance Tree Accuracy and Complexity

• Cost Function:
Error Term R(T)
• Classification – Misclassification Error / Gini

• Regression – Mean Squared Error (MSE)

How CART Prunes?
1. Start with full tree T₀
2. For each internal node:
• Calculate error before pruning
• Calculate error after replacing subtree with a leaf
3. Compute

4. Prune subtree with smallest α

5. Repeat → generate
Example
CART Tree Traffic Packets / Duration Class
ID Second
Packets/ Second <= 1 High 200 Attack
High? 2 High 220 Attack
No 3 Medium 120 Attack
Yes
4 Medium 30 Normal
Attack Duration<=50
5 Low 25 Normal
Yes No
6 Low 22 Normal
Attack
Normal
Example
Leaf wise Error

Leaf Samples Predicted error

high 2 attack Attack 0

Low , Medium 3 Normal Normal 0

(<=50)
Medium (>50) 1 attack Attack 0
Example – Candidate for Pruning
• Weakest Link is selected for pruning

• Prune the subtree that contributes the Packets/ Second <=

High?
least to reducing error relative to its
size. Yes No

Attack
• If Duration is pruned, what will be the Normal

error → R(Tt)

• So here, error will be

Example – Compute Complexity

➔(1-0)/(2-1)=1/1 ➔ 1
Packets/ Second <=
• Each removed leaf increases error by 1 High?

Yes No
• We can Prune the sub tree
Attack Normal
• If ∝ < 1, keep subtree

• If ∝ >= 1, Prune Subtree

• Larger ∝, aggressive pruning needed

Example – Compute Complexity

Packets/ Second <=

High?
➔(1-0)/(2-1)=1/1 ➔ 1
Yes No

• Each removed leaf increases error by 1 Attack Normal

• We can Prune the sub tree