Machine Learning – Unit 2, Chapter 1: Decision Tree Learning
1. Introduction to Support Vector Machine (SVM)
Definition:
Support Vector Machine (SVM) is a supervised learning algorithm used for classification and
regression tasks.
Key Idea:
• Finds a hyperplane that best separates data into classes.
• Maximizes the margin (distance between hyperplane and nearest data points).
Important Terms:
• Support Vectors: Data points closest to the decision boundary.
• Hyperplane: Decision boundary.
• Margin: Distance between hyperplane and support vectors.
Types:
1. Linear SVM
2. Non-linear SVM (using kernel trick like RBF, polynomial)
Advantages:
• Works well with high-dimensional data
• Effective when clear margin exists
2. Decision Tree Learning Algorithm
Definition:
A decision tree is a tree-like structure used for classification and regression where:
• Internal nodes → tests on attributes
• Branches → outcomes
• Leaf nodes → class labels
Working:
1. Select the best attribute (using Information Gain)
2. Split dataset
3. Repeat recursively until:
o All data belongs to one class OR
o No attributes left
Algorithm (ID3):
1. Start with full dataset
2. Choose attribute with highest Information Gain
3. Split dataset
4. Repeat for each subset
5. Stop when pure or no attributes remain
3. Inductive Bias
Definition:
Inductive bias refers to the assumptions made by a learning algorithm to generalize from
training data.
In Decision Trees:
• Preference for smaller trees
• Preference for attributes with higher information gain
Importance:
• Helps in predicting unseen data
• Prevents overfitting
4. Inductive Inference with Decision Trees
Definition:
Inductive inference means learning general rules from specific examples.
In Decision Trees:
• The model learns rules like:
IF (Outlook = Sunny) AND (Humidity = High)
THEN Play = No
Key Point:
• Converts training data into if-then rules
• Used for prediction on new data
5. Entropy (Information Theory)
Definition:
Entropy measures impurity or randomness in data.
Formula:
𝒏
𝑯(𝑺) = − ∑ 𝒑𝒊 𝐥𝐨𝐠𝟐 𝒑𝒊
𝒊=𝟏
Where:
• 𝒑𝒊 = probability of class i
Interpretation:
Entropy Value Meaning
0 Pure (all same class)
1 (max) Highly impure
Example:
• 50% Yes, 50% No → High entropy
• 100% Yes → Entropy = 0
6. Information Gain
Definition:
Information Gain measures reduction in entropy after splitting data.
Formula:
∣ 𝑺𝒗 ∣
𝑰𝑮(𝑺, 𝑨) = 𝑯(𝑺) − ∑ 𝑯(𝑺𝒗 )
∣𝑺∣
𝒗∈𝑽𝒂𝒍𝒖𝒆𝒔(𝑨)
Where:
• 𝑺= dataset
• 𝑨= attribute
• 𝑺𝒗 = subset after split
Key Idea:
• Choose attribute with highest Information Gain
Purpose:
• Helps in selecting the best split
Relationship Between Concepts
• Entropy → Measures impurity
• Information Gain → Reduces entropy
• Decision Tree → Uses Information Gain to split
• Inductive Bias → Guides tree construction
• Inductive Inference → Creates rules from data
Advantages of Decision Trees
• Easy to understand & interpret
• Requires little data preprocessing
• Handles both numerical & categorical data
Disadvantages
• Prone to overfitting
• Can become complex (deep trees)
Exam Tips
• Always write formula of entropy & information gain
• Mention ID3 algorithm steps
• Define inductive bias clearly
• Add examples of rules in decision trees
• Draw a small tree diagram if possible
Chapter 2: Instance-Based Learning
1. Introduction to Instance-Based Learning
Definition:
Instance-based learning is a lazy learning approach where:
• The model stores training data
• It does not build an explicit model
• Prediction is done using similarity between instances
Key Idea:
“Learn by remembering”
Characteristics:
• No explicit training phase
• Computation happens during prediction
• Uses distance/similarity measures
Examples:
• k-Nearest Neighbors (k-NN)
• Locally Weighted Regression
• Radial Basis Function Networks
Advantages:
• Simple to implement
• Adapts easily to new data
• No assumption about data distribution
Disadvantages:
• High memory usage
• Slow prediction time
• Sensitive to irrelevant features
2. k-Nearest Neighbor (k-NN) Learning
Definition:
k-NN is a supervised learning algorithm that classifies a data point based on the majority
class of its k nearest neighbors.
Working:
1. Choose value of k
2. Calculate distance from test point to all training points
3. Select k nearest neighbors
4. Perform:
- Majority voting (classification)
- Average (regression)
5. Assign output
Distance Metrics:
1. Euclidean Distance:
𝒏
𝒅(𝒙, 𝒚) = √∑( 𝒙𝒊 − 𝒚𝒊 )𝟐
𝒊=𝟏
2. Manhattan Distance:
𝒅(𝒙, 𝒚) = ∑ ∣ 𝒙𝒊 − 𝒚𝒊 ∣
3. Minkowski Distance:
𝒅(𝒙, 𝒚) = (∑ ∣ 𝒙𝒊 − 𝒚𝒊 ∣𝒑 )𝟏/𝒑
Choosing k:
k Value Effect
Small k Overfitting
Large k Underfitting
Example:
Points:
• (1,2) → Class A
• (2,3) → Class A
• (5,6) → Class B
Test: (3,4)
Nearest neighbors → Majority = A
Advantages:
• Easy to understand
• No training required
• Works for multi-class problems
Disadvantages:
• Slow for large datasets
• Sensitive to noise
• Needs feature scaling
3. Locally Weighted Regression (LWR)
Definition:
Locally Weighted Regression is a non-parametric regression method where:
• A model is fit locally around query point
• Nearby points have higher influence
Key Idea:
“Fit model only near the point of interest”
Working:
1. Take query point x
2. Assign weights to training points based on distance
3. Fit regression model locally
4. Predict output
Weight Function (Gaussian):
(𝒊) 𝟐
(𝒙 −𝒙)
−
𝒘(𝒊) = 𝒆 𝟐𝝉𝟐
Where:
• 𝝉= bandwidth parameter
• Smaller τ → more local model
Characteristics:
• No global model
• Flexible and adaptive
• Captures non-linear patterns
Advantages:
• High accuracy for complex data
• Smooth predictions
Disadvantages:
• Computationally expensive
• Requires storing all data
• Sensitive to noise
4. Radial Basis Function (RBF) Networks
Definition:
RBF Network is a neural network model that uses radial basis functions as activation
functions.
Structure:
Input Layer → Hidden Layer (RBF) → Output Layer
Working:
1. Input data is passed
2. Hidden layer applies radial basis function
3. Output layer combines results
Radial Basis Function (Gaussian):
∣∣𝒙−𝒄∣∣𝟐
−
𝝓(𝒙) = 𝒆 𝟐𝝈𝟐
Where:
• 𝒄= center
• 𝝈= spread
Key Features:
• Localized response
• Fast training compared to deep networks
• Good for function approximation
Advantages:
• Handles non-linear problems
• Faster convergence
• Simple architecture
Disadvantages:
• Choosing centers is difficult
• Sensitive to parameters
• May require many neurons
5. Comparison of Instance-Based Methods
Feature k-NN LWR RBF Network
Type Lazy Lazy Hybrid
Model None Local model Neural network
Speed Slow Slow Fast
Complexity Low Medium High
6. Important Concepts
Lazy Learning vs Eager Learning
Lazy Learning Eager Learning
Stores data Builds model
Slow prediction Fast prediction
Example: k-NN Example: Decision Tree
Curse of Dimensionality:
• High dimensions → distance becomes meaningless
• Affects k-NN and LWR
Feature Scaling:
• Required for distance-based methods
• Use normalization or standardization
7. Exam Tips
• Define instance-based learning clearly
• Write k-NN algorithm steps
• Include distance formula (Euclidean)
• Explain weight function in LWR
• Write RBF formula
• Compare methods in table
• Add advantages & disadvantages
Final Quick Revision
• Instance-based → learn by storing data
• k-NN → classify using neighbors
• LWR → local regression with weights
• RBF → neural network with Gaussian functions
UNIT 2 QUESTION BANK (BT Levels 1–4)
2 MARK QUESTIONS (SHORT ANSWERS)
Focus: Definitions, formulas, concepts
BT Levels: L1 (Remember), L2 (Understand)
BT Level 1 – Remember (Direct Questions)
1. Define Decision Tree Learning. (CO4)
2. What is entropy in machine learning? (CO4)
3. Define Information Gain. (CO4)
4. What is inductive bias? (CO4)
5. Define k-Nearest Neighbor algorithm. (CO4)
6. What is instance-based learning? (CO4)
7. What are support vectors in SVM? (CO4)
8. Define hyperplane. (CO4)
9. What is Euclidean distance? (CO4)
10. Define Radial Basis Function (RBF). (CO4)
BT Level 2 – Understand
11. Differentiate between entropy and information gain. (CO4)
12. Explain why decision trees may overfit. (CO5)
13. What is the role of k in k-NN? (CO4)
14. Explain lazy learning with an example. (CO4)
15. Why is feature scaling important in k-NN? (CO3, CO4)
16. Explain inductive inference in decision trees. (CO4)
17. What is kernel trick in SVM? (CO4)
18. State advantages of decision trees. (CO5)
19. What is locally weighted regression? (CO4)
20. What is curse of dimensionality? (CO3, CO4)
5 MARK QUESTIONS (DESCRIPTIVE)
Focus: Explanation, working, comparison
BT Levels: L2, L3
BT Level 2 – Understand
1. Explain Decision Tree Learning with a neat diagram. (CO4)
2. Explain entropy with formula and example. (CO4)
3. Describe Information Gain and its role in decision trees. (CO4)
4. Explain inductive bias and its importance in ML. (CO4)
5. Describe k-NN algorithm with steps. (CO4)
6. Explain working of Locally Weighted Regression. (CO4)
7. Explain structure of Radial Basis Function Network. (CO4)
8. Explain types of SVM with examples. (CO4)
BT Level 3 – Apply
9. Calculate entropy for dataset:
Yes = 6, No = 4. (CO4)
10. Compute Information Gain for given attribute (simple dataset given). (CO4)
11. Given dataset, classify a point using k-NN (k=3). (CO4)
12. Apply Euclidean distance formula to find nearest neighbor. (CO4)
13. Given τ value, explain effect on LWR predictions. (CO4)
HIGH-LEVEL 5 MARK QUESTIONS (BT Level 4 – Analyze)
Focus: Comparison, reasoning, evaluation
BT Level: L4
1. Compare Decision Tree and SVM in terms of performance and complexity. (CO5)
2. Analyze how choice of k affects k-NN performance. (CO4, CO5)
3. Compare instance-based learning and model-based learning. (CO4)
4. Analyze advantages and limitations of decision trees. (CO5)
5. Compare Information Gain and Gain Ratio. (CO4)
6. Analyze overfitting in decision trees and suggest solutions. (CO5)
7. Compare k-NN, LWR, and RBF networks. (CO4, CO5)
8. Analyze effect of high dimensional data on k-NN. (CO3, CO4)
IMPORTANT NUMERICAL / APPLICATION QUESTIONS (VERY
IMPORTANT)
Often asked in exams (BT L3–L4)
1. Calculate entropy and information gain for given dataset. (CO4)
2. Construct decision tree using ID3 algorithm. (CO4)
3. Classify a test sample using k-NN (given dataset). (CO4)
4. Compute distances using Euclidean formula. (CO4)
5. Analyze performance of model based on given output. (CO5)
CO Mapping Summary
CO Covered Topics
CO1 Data basics (indirectly used)
CO2 Data handling (k-NN, LWR)
CO3 Feature scaling, dimensionality
CO4 Algorithms (DT, k-NN, SVM, RBF)
CO5 Evaluation, overfitting, comparison
Most Important Exam Questions (Must Prepare)
These are HIGH probability:
• Entropy + Information Gain (Numerical)
• Decision Tree Algorithm (ID3)
• k-NN working + distance calculation
• Inductive bias explanation
• LWR weight function
• RBF Network diagram
• Overfitting & pruning