Machine Learning Theory ACE

PPT Machine Learning

https://docs.google.com/presentation/d/e/2PACX-1vRzZYCzS7POXEuuaKLwZpWE7RftY5wESlIFcAUco05GkTQDYhLmsPLxlMWIFqNfcXFhieSTHiWhcPAW/pub?start=false&loop=false&delayms=3000

 

 

 

UNIT 1

 Learning - types of learning

Machine learning (ML) is broadly classified into four main types based on how the model learns from data.

1. Supervised Learning

In supervised learning, the model is trained using labeled data, where both the input and the correct output are provided. The goal is to learn the relationship between inputs and outputs so it can predict outcomes for new data.

Examples:

• Email spam detection
• House price prediction
• Disease diagnosis

Common algorithms:

• Linear Regression
• Logistic Regression
• Decision Trees
• Support Vector Machine (SVM)
• Random Forest
• Neural Networks

Example:
A model learns from past house prices and predicts the price of a new house.

---

2. Unsupervised Learning

In unsupervised learning, the model is trained using unlabeled data. It tries to discover hidden patterns or group similar data points.

Examples:

• Customer segmentation
• Market basket analysis
• Fraud detection

Common algorithms:

• K-Means Clustering
• Hierarchical Clustering
• DBSCAN
• Principal Component Analysis (PCA)

Example:
Grouping customers into different categories based on their purchasing behavior.

---

3. Semi-Supervised Learning

Semi-supervised learning uses a small amount of labeled data and a large amount of unlabeled data. It is useful when labeling data is expensive or time-consuming.

Examples:

• Image recognition
• Speech recognition
• Medical image analysis

Example:
Training a model with a few labeled medical images and thousands of unlabeled images.

---

4. Reinforcement Learning

In reinforcement learning, an agent learns by interacting with an environment. It receives rewards for good actions and penalties for bad actions, improving its decisions over time.

Examples:

• Self-driving cars
• Game-playing AI
• Robot navigation

Common algorithms:

• Q-Learning
• Deep Q Networks (DQN)
• Policy Gradient Methods

Example:
A robot learns to navigate a maze by receiving rewards for reaching the goal.

---

Summary Table

Learning Type	Training Data	Goal	Example
Supervised Learning	Labeled	Predict outputs	Spam email detection
Unsupervised Learning	Unlabeled	Find patterns/groups	Customer segmentation
Semi-Supervised Learning	Partially labeled	Improve accuracy with limited labels	Image classification
Reinforcement Learning	Reward/Penalty feedback	Learn optimal actions	Self-driving cars, game AI

 

Supervised Learning

Supervised learning is a type of machine learning in which a model is trained using labeled data. Each training example contains an input (features) and the correct output (label). The model learns the relationship between inputs and outputs so it can predict the output for new, unseen data.

Definition

Supervised Learning is a machine learning technique where an algorithm learns from labeled training data to make predictions or classify new data accurately.

---

How Supervised Learning Works

1. Collect Data
   • Gather historical data with known outputs.
2. Prepare Data
   • Clean missing values.
   • Remove duplicates.
   • Normalize or standardize features if needed.
3. Split the Data
   • Training set (typically 70–80%)
   • Testing set (typically 20–30%)
4. Train the Model
   • The algorithm learns patterns from the training data.
5. Evaluate the Model
   • Measure performance using evaluation metrics.
6. Make Predictions
   • Use the trained model to predict outputs for new data.

---

Types of Supervised Learning

1. Classification

Classification predicts categorical values.

Examples

• Spam or Not Spam
• Disease Positive or Negative
• Cat or Dog
• Fraud or Not Fraud

Algorithms

• Logistic Regression
• Decision Tree
• Random Forest
• Support Vector Machine (SVM)
• Naive Bayes
• K-Nearest Neighbors (KNN)
• Neural Networks

Example

Email Text	Output
Win a free iPhone	Spam
Meeting at 3 PM	Not Spam

---

2. Regression

Regression predicts continuous numerical values.

Examples

• House price prediction
• Temperature prediction
• Salary prediction
• Stock price forecasting

Algorithms

• Linear Regression
• Polynomial Regression
• Decision Tree Regressor
• Random Forest Regressor
• Gradient Boosting
• XGBoost

Example

House Size (sq ft)	Price
1000	₹30 Lakhs
1500	₹45 Lakhs
2000	₹60 Lakhs

---

Common Algorithms

Algorithm	Used For
Linear Regression	Regression
Logistic Regression	Classification
Decision Tree	Both
Random Forest	Both
Support Vector Machine (SVM)	Classification
K-Nearest Neighbors (KNN)	Both
Naive Bayes	Classification
Neural Networks	Both

---

Advantages

• High prediction accuracy with quality labeled data.
• Easy to evaluate because true labels are known.
• Suitable for many real-world prediction tasks.
• Well-established algorithms and tools.

---

Disadvantages

• Requires a large amount of labeled data.
• Labeling data can be expensive and time-consuming.
• Performance depends on the quality of the training data.
• May overfit if the model is too complex.

---

Applications

• Email spam detection
• Face recognition
• Credit card fraud detection
• Medical diagnosis
• Weather forecasting
• Loan approval prediction
• Sentiment analysis
• Handwriting recognition
• Customer churn prediction

---

Evaluation Metrics

For Classification

• Accuracy
• Precision
• Recall
• F1-Score
• ROC-AUC
• Confusion Matrix

For Regression

• Mean Absolute Error (MAE)
• Mean Squared Error (MSE)
• Root Mean Squared Error (RMSE)
• R² Score (Coefficient of Determination)

---

Simple Example

Suppose you want to predict whether a student will pass an exam.

Training Data

Study Hours	Attendance (%)	Result
2	60	Fail
4	70	Pass
6	85	Pass
1	50	Fail

The model learns that students with more study hours and better attendance are more likely to pass.

Prediction

A new student studies 5 hours and has 80% attendance. The model predicts:

Result: Pass

---

Real-World Workflow

Labeled Data
      │
      ▼
Data Preprocessing
      │
      ▼
Train Model
      │
      ▼
Evaluate Performance
      │
      ▼
Predict New Data

Key Points to Remember

• Supervised learning uses labeled data.
• It is mainly divided into classification (predicting categories) and regression (predicting numbers).
• It is one of the most widely used machine learning approaches because of its effectiveness in prediction tasks.
• The quality and quantity of labeled data significantly influence model performance.

The Brain and the Neuron

The human brain is the body's control center. It processes information, makes decisions, stores memories, and controls actions. The basic functional unit of the brain is the neuron (nerve cell), which communicates with other neurons through electrical and chemical signals.

 

 

Biological Neuron vs Artificial Neuron

Biological Neuron	Artificial Neuron (AI)
Receives signals through dendrites	Receives input features
Cell body processes signals	Computes weighted sum of inputs
Axon sends output signal	Produces output value
Synapse controls signal strength	Weights determine connection strength
Learns by changing synaptic strength	Learns by updating weights during training

---

 

Relationship to Machine Learning

Artificial Neural Networks (ANNs) are inspired by biological neurons.

• Inputs correspond to signals entering dendrites.
• Weights represent the strength of synaptic connections.
• The activation function mimics the neuron's decision to fire.
• The output corresponds to the signal sent along the axon.

This biological inspiration is the foundation of many deep learning models used in image recognition, speech recognition, natural language processing, and recommendation systems.

---

Key Points

• The brain is the body's control center and contains about 86 billion neurons.
• A neuron is the basic unit responsible for transmitting information.
• The main parts of a neuron are dendrites, cell body (soma), axon, and axon terminals.
• Neurons communicate through electrical impulses and chemical neurotransmitters across synapses.
• Artificial neural networks are modeled after the way biological neurons receive, process, and transmit information.

 

 

Design of a Learning System

A learning system in machine learning is a framework that enables a computer to learn from data and improve its performance over time without being explicitly programmed for every task.

Definition

A learning system is a combination of data, algorithms, and evaluation methods that learns patterns from past experience and uses them to make predictions or decisions on new data.

---

Components of a Learning System

             Real-World Problem
                     │
                     ▼
              Data Collection
                     │
                     ▼
             Data Preprocessing
                     │
                     ▼
            Feature Engineering
                     │
                     ▼
            Machine Learning Model
                     │
                     ▼
             Model Training
                     │
                     ▼
             Model Evaluation
                     │
                     ▼
               Prediction
                     │
                     ▼
             Performance Feedback
                     │
                     ▼
              Model Improvement

---

Step 1: Problem Definition

Clearly identify the objective.

Examples:

• Predict house prices.
• Detect spam emails.
• Recognize handwritten digits.
• Predict customer churn.

---

Step 2: Data Collection

Gather relevant data from various sources.

Sources:

• Databases
• Sensors
• Websites
• APIs
• Surveys
• IoT devices

Example:
For house price prediction:

• Area
• Number of bedrooms
• Location
• Age of house
• Price

---

Step 3: Data Preprocessing

Prepare the data before training.

Tasks include:

• Remove duplicate records.
• Handle missing values.
• Normalize or standardize features.
• Encode categorical variables.
• Split data into training and testing sets.

---

Step 4: Feature Engineering

Select or create the most informative features.

Examples:

• House size
• Number of rooms
• Distance to city center
• Age of building

Good features improve model accuracy.

---

Step 5: Choose a Learning Algorithm

Select an algorithm based on the problem.

Problem Type	Algorithms
Classification	Logistic Regression, Decision Tree, Random Forest, SVM
Regression	Linear Regression, Random Forest Regressor
Clustering	K-Means, DBSCAN
Deep Learning	CNN, RNN, Transformers

---

Step 6: Model Training

The model learns patterns from the training data by adjusting its parameters to reduce prediction errors.

Training Inputs:

• Features (X)
• Labels (Y)

The learning algorithm finds the relationship between inputs and outputs.

---

Step 7: Model Evaluation

Test the trained model using unseen data.

Classification Metrics

• Accuracy
• Precision
• Recall
• F1 Score
• ROC-AUC

Regression Metrics

• MAE (Mean Absolute Error)
• MSE (Mean Squared Error)
• RMSE (Root Mean Squared Error)
• R² Score

---

Step 8: Prediction

Use the trained model to make predictions on new data.

Example:
Input:

• Area = 1500 sq ft
• Bedrooms = 3

Output:

• Predicted Price = ₹60,00,000

---

Step 9: Feedback and Improvement

Monitor performance and improve the system by:

• Collecting more data.
• Retraining the model.
• Tuning hyperparameters.
• Updating features.
• Choosing a better algorithm.

This continuous cycle helps the system adapt and improve over time.

---

Characteristics of a Good Learning System

• Accuracy: Produces correct predictions.
• Generalization: Performs well on unseen data.
• Scalability: Handles large datasets efficiently.
• Robustness: Works reliably even with noisy or incomplete data.
• Efficiency: Uses computational resources effectively.

---

Example: Email Spam Detection Learning System

Emails
   │
   ▼
Data Collection
   │
   ▼
Preprocessing
(Remove punctuation, tokenize text)
   │
   ▼
Feature Extraction
(Bag of Words / TF-IDF)
   │
   ▼
Train Classifier
(Naive Bayes / Logistic Regression)
   │
   ▼
Evaluate Accuracy
   │
   ▼
Predict
Spam or Not Spam

---

Applications of Learning Systems

• Medical diagnosis
• Fraud detection
• Recommendation systems
• Self-driving cars
• Face recognition
• Speech recognition
• Stock price prediction
• Predictive maintenance
• Customer churn prediction

---

Advantages

• Learns automatically from data.
• Improves performance with more experience.
• Reduces manual effort.
• Can solve complex real-world problems.
• Supports data-driven decision-making.

---

Limitations

• Requires high-quality data.
• Training can be time-consuming.
• May overfit or underfit if not properly designed.
• Performance depends on the choice of algorithm and features.

---

Summary

A machine learning system follows a structured process:

1. Define the problem.
2. Collect data.
3. Preprocess the data.
4. Engineer/select features.
5. Choose a suitable algorithm.
6. Train the model.
7. Evaluate its performance.
8. Make predictions.
9. Continuously improve using feedback.

 

 

Perspectives and Issues in Machine Learning

Introduction

Machine Learning (ML) is a branch of Artificial Intelligence (AI) that enables computers to learn from data and improve their performance without being explicitly programmed. While ML has transformed industries such as healthcare, finance, education, and transportation, it also presents several technical, ethical, and practical challenges.

---

Perspectives of Machine Learning

A perspective refers to the different ways machine learning is viewed and applied.

1. Computational Perspective

• Focuses on developing algorithms that learn from data efficiently.
• Aims to improve prediction accuracy while reducing computation time.

Example: Developing faster algorithms for image recognition.

---

2. Statistical Perspective

• Machine learning is viewed as a statistical method for analyzing data.
• Uses probability and statistical models to make predictions.

Example: Predicting house prices using regression analysis.

---

3. Artificial Intelligence Perspective

• ML is considered a subset of AI.
• Helps machines make intelligent decisions based on experience.

Example: Virtual assistants like Siri or Google Assistant.

---

4. Data Science Perspective

• ML is used to discover patterns and insights from large datasets.
• Supports data-driven decision-making.

Example: Customer segmentation for targeted marketing.

---

5. Business Perspective

• Organizations use ML to improve efficiency, reduce costs, and increase profits.

Applications:

• Sales forecasting
• Recommendation systems
• Fraud detection
• Demand prediction

---

6. Human-Centered Perspective

• Focuses on developing ML systems that are fair, transparent, and beneficial to people.
• Emphasizes user trust and ethical AI.

Example: AI systems that explain why a loan application was approved or rejected.

---

Issues in Machine Learning

1. Data Quality

Machine learning models rely heavily on data quality.

Problems:

• Missing values
• Duplicate records
• Noisy data
• Incorrect labels

Solution:

• Data cleaning
• Data preprocessing
• Data validation

---

2. Overfitting

Overfitting occurs when a model learns the training data too well, including its noise, and performs poorly on new data.

Characteristics:

• High training accuracy
• Low testing accuracy

Solutions:

• Cross-validation
• Regularization
• More training data
• Simpler models

---

3. Underfitting

Underfitting happens when a model is too simple to capture patterns in the data.

Characteristics:

• Low training accuracy
• Low testing accuracy

Solutions:

• Use a more complex model
• Add relevant features
• Train for more iterations

---

4. Bias and Fairness

Bias occurs when the training data or algorithm produces unfair predictions.

Example:
A hiring model trained on biased historical data may unfairly favor certain candidates.

Solutions:

• Use diverse datasets
• Detect and reduce bias
• Regularly audit model performance

---

5. Data Privacy and Security

Many ML applications use sensitive personal information.

Challenges:

• Protecting user privacy
• Preventing unauthorized access
• Complying with data protection laws

Solutions:

• Encryption
• Data anonymization
• Secure data storage
• Access control

---

6. Model Interpretability

Some models, especially deep learning models, are difficult to understand.

Challenge:
Users may not know why a prediction was made.

Solutions:

• Explainable AI (XAI)
• Feature importance analysis
• Model visualization techniques

---

7. Computational Cost

Training advanced ML models often requires significant computational resources.

Challenges:

• High processing time
• Expensive hardware (GPUs/TPUs)
• Large memory requirements

Solutions:

• Cloud computing
• Efficient algorithms
• Model optimization

---

8. Lack of Training Data

Some applications have limited labeled data.

Solutions:

• Data augmentation
• Transfer learning
• Semi-supervised learning
• Synthetic data generation

---

9. Feature Selection

Choosing irrelevant features can reduce model performance.

Solutions:

• Feature engineering
• Principal Component Analysis (PCA)
• Recursive Feature Elimination (RFE)

---

10. Continuous Model Maintenance

Data patterns can change over time (known as concept drift).

Solutions:

• Monitor model performance
• Retrain with updated data
• Update features periodically

---

Advantages of Machine Learning

• Automates decision-making
• Improves prediction accuracy
• Learns from experience
• Handles large datasets
• Supports personalized services
• Enables intelligent automation

---

Limitations of Machine Learning

• Requires large amounts of quality data
• Can be computationally expensive
• May produce biased predictions
• Difficult to interpret complex models
• Needs regular maintenance and updates
• Performance depends on data quality

---

Applications

• Healthcare (disease diagnosis)
• Finance (fraud detection)
• Retail (recommendation systems)
• Manufacturing (predictive maintenance)
• Agriculture (crop yield prediction)
• Transportation (autonomous vehicles)
• Education (personalized learning)

---

Summary Table

Perspective	Description	Example
Computational	Efficient learning algorithms	Image recognition
Statistical	Prediction using probability	House price prediction
AI	Intelligent decision-making	Virtual assistants
Data Science	Knowledge discovery from data	Customer segmentation
Business	Improve efficiency and profit	Sales forecasting
Human-Centered	Fair, transparent, ethical AI	Explainable loan approval

Issue	Impact	Solution
Poor Data Quality	Low accuracy	Data cleaning
Overfitting	Poor generalization	Regularization, cross-validation
Underfitting	Weak performance	Better models, more features
Bias	Unfair decisions	Fair datasets, bias mitigation
Privacy	Data misuse risk	Encryption, anonymization
Interpretability	Hard to explain predictions	Explainable AI (XAI)
High Computational Cost	Slow and expensive training	Cloud computing, optimization
Limited Data	Reduced performance	Data augmentation, transfer learning
Feature Selection	Lower accuracy	Feature engineering, PCA
Concept Drift	Performance degrades over time	Monitoring and retraining

Key Points

• Perspectives describe different viewpoints of machine learning, such as computational, statistical, AI, business, and ethical perspectives.
• Issues include challenges like poor data quality, overfitting, underfitting, bias, privacy concerns, interpretability, computational cost, limited data, feature selection, and concept drift.
• Addressing these issues is essential for building reliable, accurate, and trustworthy machine learning systems.

 

 

Concept Learning Task and Concept Learning as Search

1. Concept Learning

Concept learning is a machine learning task in which a computer learns a concept (or rule) from a set of training examples. The goal is to determine whether a new example belongs to a particular category.

Definition

Concept Learning is the process of inferring a general rule or function from a set of positive and negative training examples.

Example

Suppose we want to learn the concept "Play Tennis."

Weather	Temperature	Humidity	Wind	Play Tennis
Sunny	Warm	Normal	Weak	Yes
Sunny	Cold	High	Strong	No
Rainy	Warm	High	Weak	Yes
Cloudy	Warm	Normal	Strong	Yes

The machine learns a rule such as:

Rule:
If Weather is Sunny or Cloudy, Temperature is Warm, and Wind is Weak, then Play Tennis = Yes.

It can then classify new examples based on the learned concept.

---

Components of a Concept Learning Task

A concept learning task consists of the following components:

1. Instance Space (X)

The set of all possible examples.

Example:

• Weather
• Temperature
• Humidity
• Wind

---

2. Target Concept (C)

The function that correctly classifies every instance.

Example:

Play Tennis = Yes or No

---

3. Hypothesis (H)

A hypothesis is a possible rule describing the target concept.

Example:

IF Weather = Sunny AND Temperature = Warm
THEN Play Tennis = Yes

---

4. Training Examples (D)

A collection of labeled examples used for learning.

Example:

Example	Class
Sunny, Warm	Positive
Rainy, Cold	Negative

---

5. Learning Algorithm

The algorithm searches for the hypothesis that best fits the training data.

Examples:

• Find-S Algorithm
• Candidate Elimination Algorithm
• Decision Tree Learning

---

Steps in Concept Learning

1. Collect training examples.
2. Define the target concept.
3. Select a hypothesis space.
4. Apply a learning algorithm.
5. Evaluate the learned hypothesis.
6. Predict the class of new instances.

---

Concept Learning as Search

Concept learning can be viewed as a search problem.

The learning algorithm searches through a hypothesis space to find the hypothesis that best matches the training examples.

Search Process

Training Examples
        │
        ▼
Hypothesis Space
(H1, H2, H3, H4, ...)
        │
        ▼
Search Algorithm
        │
        ▼
Best Hypothesis
        │
        ▼
Prediction

---

Hypothesis Space

The hypothesis space (H) is the set of all possible hypotheses that the learning algorithm can consider.

Example:

For weather data:

H1 : Weather = Sunny

H2 : Weather = Sunny AND Temperature = Warm

H3 : Weather = Sunny AND Wind = Weak

H4 : TRUE

The algorithm searches among these hypotheses to find the one that best explains the training data.

---

Search Strategies

1. General-to-Specific Search

• Starts with the most general hypothesis.
• Gradually adds conditions to specialize it.

Example:

H0 : Any weather

↓

Sunny

↓

Sunny AND Warm

↓

Sunny AND Warm AND Weak Wind

---

2. Specific-to-General Search

• Starts with the most specific hypothesis.
• Gradually removes restrictions to generalize it.

Example:

Sunny, Warm, Normal, Weak

↓

Sunny, Warm, ?, Weak

↓

Sunny, ?, ?, ?

↓

Any Weather

---

Version Space

The Version Space is the set of all hypotheses that are consistent with the training examples.

It is bounded by:

• Specific Boundary (S): The most specific consistent hypothesis.
• General Boundary (G): The most general consistent hypothesis.

Any hypothesis between S and G is considered consistent with the observed data.

---

Example of Concept Learning as Search

Training Data

Weather	Temperature	Play
Sunny	Warm	Yes
Sunny	Cold	No
Rainy	Warm	No

Initial Hypothesis

<?, ?>

(All values allowed)

After Learning

<Sunny, Warm>

The search algorithm has identified the hypothesis that correctly classifies the given training examples.

---

Applications of Concept Learning

• Email spam detection
• Medical diagnosis
• Product recommendation
• Face recognition
• Credit approval
• Fault detection
• Customer classification

---

Advantages

• Learns general rules from examples.
• Improves prediction accuracy over time.
• Provides interpretable decision rules.
• Forms the basis for many supervised learning algorithms.

---

Limitations

• Requires representative labeled training data.
• Large hypothesis spaces can make search computationally expensive.
• Noisy or inconsistent data can reduce accuracy.
• May struggle with highly complex concepts without advanced models.

---

Difference Between Concept Learning Task and Concept Learning as Search

Concept Learning Task	Concept Learning as Search
Focuses on learning a target concept from labeled examples.	Views learning as searching through a hypothesis space.
Uses training data to infer a rule.	Uses search strategies to identify the best hypothesis.
Includes instances, hypotheses, and target concepts.	Includes hypothesis space, search algorithm, and evaluation.
Goal is accurate classification of new examples.	Goal is finding the hypothesis most consistent with the training data.

Key Points

• Concept Learning is the process of learning a classification rule from labeled examples.
• A concept learning task includes the instance space, target concept, hypothesis space, training examples, and learning algorithm.
• Concept learning as search treats learning as a search through the hypothesis space to find the hypothesis that best matches the training data.
• Important related ideas include the hypothesis space, version space, general-to-specific search, and specific-to-general search.

 

 

Finding a Maximally Specific Hypothesis (Find-S Algorithm)

Introduction

The Find-S Algorithm is one of the simplest algorithms used in concept learning. It finds the most specific hypothesis that is consistent with all positive training examples.

Definition

A maximally specific hypothesis is the most restrictive hypothesis that correctly classifies all positive training examples while excluding as many negative examples as possible.

The algorithm starts with the most specific hypothesis and gradually generalizes it only when necessary.

---

Basic Idea

• Start with the most specific hypothesis (no instance is accepted).
• Examine each positive example.
• If the hypothesis does not cover the example, generalize it minimally.
• Ignore all negative examples.

---

Steps of the Find-S Algorithm

1. Initialize the hypothesis to the most specific possible.
2. For each training example:
   • If it is negative, ignore it.
   • If it is positive:
     • Compare it with the current hypothesis.
     • If an attribute differs, replace that attribute with ? (meaning "any value").
3. Continue until all positive examples have been processed.
4. The final hypothesis is the maximally specific hypothesis.

---

Algorithm

Find-S(H, D)

1. Initialize H to the most specific hypothesis.
2. For each positive training example x:
      For each attribute a:
          If H[a] is empty:
              H[a] = x[a]
          Else if H[a] ≠ x[a]:
              H[a] = ?
3. Return H.

---

Example

Suppose we have the following training data.

Example	Sky	AirTemp	Humidity	Wind	Water	Forecast	Enjoy Sport
1	Sunny	Warm	Normal	Strong	Warm	Same	Yes
2	Sunny	Warm	High	Strong	Warm	Same	Yes
3	Rainy	Cold	High	Strong	Warm	Change	No
4	Sunny	Warm	High	Strong	Cool	Change	Yes

---

Step 1: Initial Hypothesis

H0 = <Ø, Ø, Ø, Ø, Ø, Ø>

(Ø means the most specific value.)

---

Step 2: Process Example 1 (Positive)

Example:

<Sunny, Warm, Normal, Strong, Warm, Same>

Update hypothesis:

H1 = <Sunny, Warm, Normal, Strong, Warm, Same>

---

Step 3: Process Example 2 (Positive)

Example:

<Sunny, Warm, High, Strong, Warm, Same>

Only Humidity differs.

H2 = <Sunny, Warm, ?, Strong, Warm, Same>

---

Step 4: Process Example 3 (Negative)

Negative examples are ignored.

H3 = <Sunny, Warm, ?, Strong, Warm, Same>

---

Step 5: Process Example 4 (Positive)

Example:

<Sunny, Warm, High, Strong, Cool, Change>

Differences:

• Water → ?
• Forecast → ?

Final hypothesis:

H4 = <Sunny, Warm, ?, Strong, ?, ?>

---

Final Maximally Specific Hypothesis

<Sunny, Warm, ?, Strong, ?, ?>

This means:

• Sky must be Sunny
• Air Temperature must be Warm
• Humidity can be any value
• Wind must be Strong
• Water can be any value
• Forecast can be any value

---

Flowchart

Start
   │
   ▼
Initialize Most Specific Hypothesis
   │
   ▼
Read Training Example
   │
   ▼
Positive?
 ┌───────┐
 │  No   │──► Ignore
 └───────┘
      │
     Yes
      │
      ▼
Generalize Hypothesis
      │
      ▼
More Examples?
      │
  Yes ─────► Repeat
      │
      ▼
Return Final Hypothesis

---

Advantages

• Easy to understand and implement.
• Efficient for simple concept-learning problems.
• Produces the most specific hypothesis consistent with positive examples.
• Useful for introducing concept learning.

---

Disadvantages

• Ignores negative examples, so it may produce overly general hypotheses.
• Assumes training data is noise-free.
• Cannot determine whether multiple hypotheses fit the data equally well.
• Limited to conjunctive hypothesis spaces.

---

Applications

• Medical diagnosis
• Email spam detection
• Product recommendation
• Fault detection
• Pattern recognition
• Student performance prediction

---

Summary

Feature	Description
Algorithm	Find-S
Learning Type	Supervised Learning
Uses Positive Examples	Yes
Uses Negative Examples	No
Starting Point	Most Specific Hypothesis
Goal	Find the maximally specific hypothesis consistent with all positive examples

Key Points

• Find-S begins with the most specific hypothesis.
• It updates only using positive training examples.
• When an attribute differs across positive examples, it is replaced with ? to generalize just enough.
• The final result is the maximally specific hypothesis that covers all observed positive examples.

 

 

Version Spaces and the Candidate Elimination Algorithm

Introduction

Version Space and the Candidate Elimination Algorithm are important concepts in concept learning. Unlike the Find-S algorithm, which finds only one hypothesis, the Candidate Elimination Algorithm maintains all hypotheses that are consistent with the training data.

---

Version Space

Definition

A Version Space is the set of all hypotheses in the hypothesis space that are consistent with every training example.

Mathematically,

$$\boxed{\text{Version Space} = \{\, h \in H \mid h \text{ is consistent with all training examples} \,\}}$$

where:

• H = Hypothesis space
• h = A hypothesis

---

Representation of Version Space

A Version Space is represented by two boundaries:

1. Specific Boundary (S)

• Contains the most specific hypothesis consistent with the training data.
• Initially, it is the most restrictive hypothesis.

2. General Boundary (G)

• Contains the most general hypothesis consistent with the training data.
• Initially, it accepts every instance.

Version Space

General Boundary (G)
          │
          ▼
--------------------------
|  All Consistent Rules  |
--------------------------
          ▲
          │
Specific Boundary (S)

---

Candidate Elimination Algorithm

Definition

The Candidate Elimination Algorithm is a concept learning algorithm that updates the Specific (S) and General (G) boundaries whenever a new training example is processed.

It eliminates hypotheses that are inconsistent with the training examples until only the consistent hypotheses remain.

---

Initial Boundaries

Suppose the attributes are:

• Sky
• AirTemp
• Humidity
• Wind
• Water
• Forecast

Initially,

Specific Boundary

S0 = <Ø, Ø, Ø, Ø, Ø, Ø>

(Ø represents the most specific hypothesis.)

General Boundary

G0 = <?, ?, ?, ?, ?, ?>

(? represents any value.)

---

Steps of the Candidate Elimination Algorithm

1. Initialize:
   • $S$ as the most specific hypothesis.
   • $G$ as the most general hypothesis.
2. Process each training example:
   • If the example is positive:
     • Remove hypotheses from G that do not cover the example.
     • Generalize S minimally to include the example.
   • If the example is negative:
     • Remove hypotheses from S that cover the negative example.
     • Specialize G minimally to exclude the example.
3. Repeat until all training examples are processed.
4. The hypotheses between S and G form the Version Space.

---

Example

Training Data

Sky	AirTemp	Humidity	Wind	Water	Forecast	Enjoy Sport
Sunny	Warm	Normal	Strong	Warm	Same	Yes
Sunny	Warm	High	Strong	Warm	Same	Yes
Rainy	Cold	High	Strong	Warm	Change	No

---

Step 1: Initial State

S = <Ø, Ø, Ø, Ø, Ø, Ø>

G = <?, ?, ?, ?, ?, ?>

---

Step 2: First Positive Example

<Sunny, Warm, Normal, Strong, Warm, Same>

Update:

S = <Sunny, Warm, Normal, Strong, Warm, Same>

G = <?, ?, ?, ?, ?, ?>

---

Step 3: Second Positive Example

<Sunny, Warm, High, Strong, Warm, Same>

Humidity differs.

S = <Sunny, Warm, ?, Strong, Warm, Same>

G = <?, ?, ?, ?, ?, ?>

---

Step 4: Negative Example

<Rainy, Cold, High, Strong, Warm, Change>

Since G accepts every instance, specialize it to exclude this negative example while still covering the positive examples.

One possible updated general boundary is:

G =
{
<Sunny, ?, ?, ?, ?, ?>,
<?, Warm, ?, ?, ?, ?>,
<?, ?, ?, ?, ?, Same>
}

The specific boundary remains:

S =
<Sunny, Warm, ?, Strong, Warm, Same>

---

Candidate Elimination Flowchart

Start
   │
   ▼
Initialize S and G
   │
   ▼
Read Training Example
   │
   ▼
Positive Example?
 ┌──────────────┐
 │ Yes          │
 └──────────────┘
        │
Generalize S
Remove inconsistent G
        │
        ▼
No
        │
Specialize G
Remove inconsistent S
        │
        ▼
More Examples?
        │
   Yes ─────► Repeat
        │
        ▼
Return Version Space

---

Difference Between Find-S and Candidate Elimination

Feature	Find-S	Candidate Elimination
Uses Positive Examples	Yes	Yes
Uses Negative Examples	No	Yes
Result	One hypothesis	All consistent hypotheses (Version Space)
Maintains S Boundary	Yes	Yes
Maintains G Boundary	No	Yes
Handles Inconsistent Data	Limited	Better, but assumes noise-free data

---

Advantages

• Uses both positive and negative examples.
• Maintains every hypothesis consistent with the training data.
• More informative than Find-S because it tracks the complete version space.
• Helps understand the uncertainty remaining after learning.

---

Limitations

• Assumes training data is free from noise.
• Can become computationally expensive for large hypothesis spaces.
• Version spaces may grow very large for complex problems.
• Difficult to apply directly to high-dimensional real-world datasets.

---

Applications

• Concept learning
• Rule-based classification
• Educational demonstrations of machine learning
• Knowledge discovery
• Pattern recognition

---

Summary

Concept	Description
Version Space	Set of all hypotheses consistent with the training data
Specific Boundary (S)	Most specific consistent hypothesis
General Boundary (G)	Most general consistent hypotheses
Candidate Elimination	Algorithm that updates both S and G after each training example

Key Points

• A Version Space contains all hypotheses that remain consistent with the observed training data.
• The Specific Boundary (S) stores the most specific consistent hypothesis.
• The General Boundary (G) stores the most general consistent hypotheses.
• The Candidate Elimination Algorithm updates both S and G using positive and negative examples, narrowing the version space until only consistent hypotheses remain.

 

 

Linear Discriminants, Perceptron, Linear Separability, and Linear Regression

These are fundamental concepts in Machine Learning and are widely used in classification and prediction problems.

---

1. Linear Discriminants

Definition

A Linear Discriminant is a function that separates data into different classes using a linear decision boundary (a line in 2D, a plane in 3D, or a hyperplane in higher dimensions).

The discriminant function is:

$$g(x)=w^Tx+b$$

Where:

• x = Input feature vector
• w = Weight vector
• b = Bias (threshold)

Decision Rule

• If g(x) > 0, classify as Class 1
• If g(x) < 0, classify as Class 2
• If g(x) = 0, the point lies on the decision boundary

Example

Suppose

• $w=[2,3]$
• $b=-6$

Then

$$g(x)=2x_1+3x_2-6$$

The line

$$2x_1+3x_2-6=0$$

acts as the decision boundary.

---

Advantages

• Simple and fast
• Easy to interpret
• Works well for linearly separable data

Limitations

• Cannot classify complex nonlinear datasets accurately

---

2. Perceptron

Definition

The Perceptron is the simplest neural network model introduced by Frank Rosenblatt (1958). It is a binary classifier that learns a linear decision boundary.

Structure

Inputs (x1, x2, ..., xn)
        │
        ▼
Multiply by Weights (w1, w2, ..., wn)
        │
        ▼
Weighted Sum + Bias
        │
        ▼
Activation Function
        │
        ▼
Output (0 or 1)

Perceptron Equation

$$y=f(w^Tx+b)$$

where $f$ is the step activation function:

$$f(z)= \begin{cases} 1,& z\ge0\\ 0,& z<0 \end{cases}$$

---

Perceptron Learning Algorithm

1. Initialize weights randomly or to zero.
2. For each training example:
   • Compute the output.
   • Compare with the actual label.
   • Update weights if the prediction is incorrect.
3. Repeat until no errors remain or a stopping criterion is met.

Weight Update Rule

$$w_{\text{new}}=w_{\text{old}}+\eta (t-y)x$$

Where:

• $\eta$ = Learning rate
• $t$ = Target output
• $y$ = Predicted output

---

Advantages

• Easy to implement
• Fast learning
• Suitable for binary classification

Disadvantages

• Works only for linearly separable data
• Cannot solve XOR and similar nonlinear problems

---

3. Linear Separability

Definition

A dataset is linearly separable if a single straight line (or hyperplane) can completely separate the classes.

Linearly Separable Data

○ ○ ○ ○

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

× × × ×

A straight line separates both classes perfectly.

Non-Linearly Separable Data

○    ×

   ○

×      ○

No single straight line can separate these classes.

---

Characteristics

Linearly Separable

• One straight line separates classes.
• Perceptron converges successfully.
• High classification accuracy.

Non-Linearly Separable

• No straight line can separate classes.
• Perceptron fails to converge.
• Requires nonlinear models such as kernel SVMs or multilayer neural networks.

---

4. Linear Regression

Definition

Linear Regression is a supervised learning algorithm used to predict continuous numerical values.

It models the relationship between independent variables and a dependent variable using a straight line.

Simple Linear Regression

$$\boxed{y=\beta_0+\beta_1x}$$

Where:

• $y$ = Predicted value
• $x$ = Input feature
• ${\beta }_0$ = Intercept
• ${\beta }_1$ = Slope

---

Multiple Linear Regression

For multiple input variables,

$$y=\beta_0+\beta_1x_1+\beta_2x_2+\cdots+\beta_nx_n$$

---

Objective

Find the line that minimizes the prediction error.

The error is commonly measured using the Mean Squared Error (MSE):

$$MSE=\frac{1}{n}\sum_{i=1}^{n}(y_i-\hat{y}_i)^2$$

---

Example

Predicting house prices.

Area (sq ft)	Price (₹ Lakhs)
1000	30
1500	45
2000	60

The model learns a line that predicts the price for a new house based on its area.

---

Advantages

• Simple and easy to interpret
• Fast to train
• Effective when the relationship is approximately linear

Limitations

• Assumes a linear relationship
• Sensitive to outliers
• May underperform on complex nonlinear data

---

Difference Between Perceptron and Linear Regression

Feature	Perceptron	Linear Regression
Learning Type	Supervised	Supervised
Task	Classification	Regression
Output	Class label (0/1)	Continuous value
Decision Boundary	Linear	Regression line
Activation Function	Step function	None
Error Function	Classification error	Mean Squared Error (MSE)

---

Difference Between Linear Discriminant and Linear Regression

Linear Discriminant	Linear Regression
Used for classification	Used for prediction of continuous values
Produces class labels	Produces numerical values
Uses a decision boundary	Fits the best regression line
Example: Spam detection	Example: House price prediction

---

Applications

Linear Discriminants

• Face recognition
• Email spam detection
• Medical diagnosis
• Document classification

Perceptron

• Binary image classification
• Character recognition
• Pattern recognition

Linear Regression

• House price prediction
• Sales forecasting
• Stock trend analysis
• Weather prediction

---

Summary

Concept	Purpose	Output
Linear Discriminant	Separate classes using a linear boundary	Class label
Perceptron	Learn a linear classifier	Binary class (0 or 1)
Linear Separability	Property of data that can be separated by a line	Determines whether linear classifiers are suitable
Linear Regression	Predict continuous values using a best-fit line	Numerical prediction

Key Points

• Linear Discriminants classify data using a linear decision boundary.
• Perceptron is the simplest neural network and works only with linearly separable data.
• Linear Separability determines whether a straight line (or hyperplane) can separate different classes.
• Linear Regression predicts continuous values by fitting the best straight line to the data using the least-squares principle.

 

 

 

 

 

 

 

 UNIT 2
A Multilayer Perceptron

A Multilayer Perceptron (MLP) is a type of artificial neural network (ANN) that consists of multiple layers of interconnected neurons. It is one of the most fundamental deep learning models and is widely used for classification and regression tasks.

Structure of an MLP

An MLP has three types of layers:

1. Input Layer
   • Receives the input features.
   • Each neuron represents one input variable.
2. Hidden Layer(s)
   • Perform computations on the inputs.
   • An MLP has one or more hidden layers.
   • Each neuron applies:
     • A weighted sum of inputs
     • A bias
     • An activation function (such as ReLU, Sigmoid, or Tanh)
3. Output Layer
   • Produces the final prediction.
   • The activation function depends on the task:
     • Sigmoid → Binary classification
     • Softmax → Multi-class classification
     • Linear → Regression

Mathematical Operation

For a neuron:

$$z = \sum_{i=1}^{n} w_i x_i + b$$
$$a = f(z)$$

where:

• $x_i$ = inputs
• $w_i$ = weights
• $b$ = bias
• $f$ = activation function
• $a$ = output of the neuron

Training Process

An MLP learns through the following steps:

1. Forward propagation
2. Compute loss (error)
3. Backpropagation
4. Update weights using an optimizer (e.g., Gradient Descent or Adam)

This process is repeated over many training epochs until the model converges.

Common Activation Functions

Activation	Formula	Use
ReLU	$f(x)=\max (0,x)$	Hidden layers
Sigmoid	$1/(1+e^{-x})$	Binary classification
Tanh	$\tanh(x)$	Hidden layers
Softmax	Converts outputs to probabilities	Multi-class classification

Advantages

• Can model complex, non-linear relationships.
• Works well for classification and regression.
• Easy to implement.
• Foundation for many deep learning models.

Limitations

• Requires a large amount of training data for good performance.
• Can overfit without regularization.
• Training can be computationally expensive for deep networks.
• Does not naturally exploit spatial or sequential structure (unlike CNNs or RNNs).

Applications

• Image classification (simple datasets)
• Handwritten digit recognition
• Fraud detection
• Medical diagnosis
• Stock price prediction
• Customer churn prediction
• Sentiment analysis

Example

Suppose you want to classify whether an email is spam or not spam:

• Input layer: Email features (word frequencies, sender information, etc.)
• Hidden layers: Learn patterns that distinguish spam from legitimate emails.
• Output layer: Produces the probability that the email is spam.

In summary, an MLP is a feedforward neural network with one or more hidden layers that learns complex patterns by adjusting weights through backpropagation. It is one of the most important building blocks in modern machine learning and deep learning.

Feedforward and backward propagation (backpropagation) 

Feedforward and backward propagation (backpropagation) are the two main phases used to train a neural network such as a Multilayer Perceptron (MLP).

1. Feedforward

In the feedforward phase, the input data moves from the input layer to the output layer to produce a prediction.

Steps

1. Input features are given to the input layer.
2. Each neuron computes:
   • Weighted sum of inputs
   • Adds a bias
   • Applies an activation function
3. The output of one layer becomes the input to the next layer.
4. The final output (prediction) is generated.

Formula

For each neuron:

$$z = \sum_{i=1}^{n} w_i x_i + b$$
$$a = f(z)$$

where:

• $x_i$ = input
• $w_i$ = weight
• $b$ = bias
• $f$ = activation function
• $a$ = neuron output

Example

Input → Hidden Layer → Output

2,3 → [Neuron] → Prediction = 0.85

If the expected output is 1, the network has made an error of:

Error = Actual − Predicted
      = 1 − 0.85
      = 0.15

---

2. Backward Propagation (Backpropagation)

Backpropagation is the learning phase. It propagates the error backward through the network and adjusts the weights and biases to reduce future errors.

Steps

1. Calculate the prediction error using a loss function.
2. Compute the gradient (how much each weight contributed to the error).
3. Send the error backward from the output layer to the hidden layers.
4. Update weights and biases using an optimization algorithm such as Gradient Descent.

Weight Update Formula

$$w_{new} = w_{old} - \eta \frac{\partial L}{\partial w}$$

where:

• $w$ = weight
• $\eta$ = learning rate
• $L$ = loss function
• $\frac{\partial L}{\partial w}$= gradient of the loss with respect to the weight

---

Flow Diagram

                Feedforward
Input ─────────► Hidden ─────────► Output
                                   │
                                   ▼
                              Compute Loss
                                   │
                                   ▼
          Backpropagation (Error Backward)
Output ◄──────── Hidden ◄──────── Input
            Update Weights

---

Comparison

Feature	Feedforward	Backpropagation
Direction	Input → Output	Output → Input
Purpose	Produce prediction	Learn by reducing error
Uses weights	Yes	Updates weights
Calculates	Output values	Gradients and weight updates
Occurs	Before loss calculation	After loss calculation
Output	Prediction	Improved weights and biases

---

Summary

• Feedforward: The network uses the current weights to compute a prediction by passing data from the input layer to the output layer.
• Backpropagation: The network compares the prediction with the correct output, computes the error, and updates the weights by propagating the error backward, enabling the model to improve over successive training iterations.

Backpropagation error

Backpropagation error is the process of calculating how much each neuron contributed to the prediction error and propagating that error backward through the neural network so the weights can be updated.

Steps in Backpropagation Error

1. Forward pass
   • The network computes the predicted output.
2. Calculate the error
   • Compare the predicted output with the actual (target) output.

   • For a single output neuron:

     $$\text{Error} = \text{Target} - \text{Predicted}$$
     
3. Calculate the loss
   • A loss function measures the overall error.

   • Example (Mean Squared Error):

     $$L = \frac{1}{2}(T - O)^2$$
     

     where:

     • $T$ = Target output
     • $O$ = Predicted output
4. Propagate the error backward
   • Compute the error gradient for the output layer.
   • Use the chain rule to determine how much each hidden neuron contributed to the error.
5. Update weights

   • Adjust each weight to reduce the error:

     $$w_{\text{new}} = w_{\text{old}} - \eta \frac{\partial L}{\partial w}$$

     where:

     • $\eta$ = Learning rate
     • $\frac{\partial L}{\partial w}$ = Gradient of the loss with respect to the weight

---

Error Calculation

Output Layer Error

For an output neuron:

$$\delta_o = (T - O) \times f'(net)$$

where:

• $T$ = Target output
• $O$ = Predicted output
• $f'(net)$ = Derivative of the activation function

Hidden Layer Error

For a hidden neuron:

$$\delta_h = f'(net_h) \sum (\delta_o \times w)$$

This means the hidden layer's error depends on:

• The errors in the next layer.
• The weights connecting the hidden neuron to the next layer.

---

Example

Suppose:

• Target output = 1
• Predicted output = 0.8

Step 1: Error

$$\text{Error} = 1 - 0.8 = 0.2$$

Step 2: Loss

$$L = \frac{1}{2}(1 - 0.8)^2 = \frac{1}{2}(0.2)^2 = 0.02$$

The network then propagates this error backward and updates its weights to reduce the loss in the next training iteration.

---

Flow of Backpropagation Error

Input
   │
   ▼
Hidden Layer
   │
   ▼
Output Layer
   │
   ▼
Calculate Error (Target − Output)
   │
   ▼
Compute Loss
   │
   ▼
Propagate Error Backward
   │
   ▼
Update Weights and Biases
   │
   ▼
Repeat Until Error is Minimized

Key Points

• Backpropagation error is the difference between the predicted and actual output, distributed backward through the network.
• It uses the chain rule from calculus to compute gradients efficiently.
• The calculated gradients are used to update weights and biases, helping the neural network learn and improve its predictions over multiple training iterations.

 

 

Multilayer Perceptron (MLP) in Practice

A Multilayer Perceptron (MLP) is used to solve real-world problems by learning patterns from data. It consists of an input layer, one or more hidden layers, and an output layer, and is trained using feedforward and backpropagation.

Practical Working of an MLP

Step 1: Collect Data

Gather a dataset containing input features and their corresponding target outputs.

Example (Student Pass Prediction):

Study Hours	Attendance (%)	Result
2	70	Fail (0)
5	85	Pass (1)
8	95	Pass (1)

Step 2: Preprocess the Data

• Remove missing values.
• Normalize or standardize features.
• Split the dataset into:
  • Training set (e.g., 80%)
  • Testing set (e.g., 20%)

Step 3: Design the MLP

Input Layer
(Study Hours, Attendance)
          │
          ▼
Hidden Layer 1
     (ReLU)
          │
          ▼
Hidden Layer 2
     (ReLU)
          │
          ▼
Output Layer
(Sigmoid → Pass/Fail)

Step 4: Feedforward

• Inputs are passed through the hidden layers.

• Each neuron computes:

  $$z = \sum wx + b$$
  
• An activation function is applied.
• The network predicts the output.

Step 5: Calculate the Error

Compare the predicted output with the actual result.

Example:

• Actual = 1
• Predicted = 0.82

Error:

$$1 - 0.82 = 0.18$$

Step 6: Backpropagation

• Calculate gradients of the loss.
• Update weights and biases using gradient descent.
• Repeat for many epochs until the error becomes small.

Step 7: Test the Model

Evaluate the trained model on unseen test data.

Example metrics:

• Accuracy
• Precision
• Recall
• F1-score

---

Real-World Applications of MLP

Application	Input	Output
Handwritten digit recognition	Image pixels	Digit (0–9)
Spam email detection	Email features	Spam / Not Spam
Medical diagnosis	Patient symptoms	Disease prediction
Loan approval	Income, credit score	Approved / Rejected
Customer churn prediction	Customer data	Stay / Leave
House price prediction	Area, rooms, location	House price

---

Advantages

• Learns complex, non-linear relationships.
• Suitable for both classification and regression.
• Easy to implement using deep learning libraries.
• Can handle large datasets.

Limitations

• Requires significant training data for good performance.
• Training can be computationally expensive.
• Can overfit if the network is too large.
• Does not exploit image or sequence structure as effectively as CNNs or RNNs.

---

Example Workflow

Training Data
      │
      ▼
Preprocessing
      │
      ▼
Build MLP Model
      │
      ▼
Feedforward
      │
      ▼
Calculate Loss
      │
      ▼
Backpropagation
      │
      ▼
Update Weights
      │
      ▼
Repeat for Multiple Epochs
      │
      ▼
Trained Model
      │
      ▼
Predict New Data

Summary

In practice, an MLP is trained by repeatedly performing feedforward to generate predictions and backpropagation to reduce prediction errors. After training, it can make accurate predictions on new data and is widely used in applications such as image recognition, spam detection, medical diagnosis, financial forecasting, and customer analytics.

 

 

Examples of Using a Multilayer Perceptron (MLP)

A Multilayer Perceptron (MLP) is commonly used for tasks where the input is a fixed set of features and the goal is to predict a class or a numeric value.

1. Handwritten Digit Recognition

Problem: Recognize digits (0–9) written by hand.

• Input: Pixel values of a digit image (e.g., 28 × 28 = 784 pixels)
• Output: Digit (0–9)

Example:

Input Image → MLP → Output: 7

---

2. Spam Email Detection

Problem: Determine whether an email is spam.

• Input: Email features (keywords, sender, links, message length)
• Output: Spam or Not Spam

Example:

Email: "Congratulations! You won a prize."

MLP Output → Spam

---

3. Student Pass/Fail Prediction

Problem: Predict whether a student will pass an exam.

Inputs:

• Study hours
• Attendance
• Assignment marks

Output:

• Pass
• Fail

Example:

Study Hours	Attendance	Assignment Marks	Prediction
7	90%	85	Pass
2	60%	45	Fail

---

4. House Price Prediction

Problem: Estimate the selling price of a house.

Inputs:

• Area
• Number of bedrooms
• Age of the house
• Location rating

Output:

• House price

Example:

Area = 1800 sq.ft
Bedrooms = 3
Location Rating = 8

MLP Output → ₹75,00,000

---

5. Medical Diagnosis

Problem: Predict whether a patient has a disease.

Inputs:

• Age
• Blood pressure
• Blood sugar
• Cholesterol

Output:

• Disease Present
• Disease Absent

Example:

Patient Data → MLP → Diabetes Detected

---

6. Loan Approval Prediction

Problem: Decide whether a loan should be approved.

Inputs:

• Income
• Credit score
• Employment status
• Existing loans

Output:

• Approved
• Rejected

Example:

Income	Credit Score	Prediction
₹80,000	780	Approved
₹25,000	520	Rejected

---

7. Customer Churn Prediction

Problem: Predict whether a customer will leave a company.

Inputs:

• Monthly bill
• Contract type
• Customer support calls
• Years as a customer

Output:

• Stay
• Leave

Example:

Customer Data → MLP → Leave

---

8. Sentiment Analysis

Problem: Determine whether a review is positive or negative.

Input:

• Customer review text (converted into numerical features)

Output:

• Positive
• Negative

Example:

Review:
"The product is excellent."

MLP Output → Positive

---

Summary Table

Application	Input	Output
Handwritten digit recognition	Image pixels	Digit (0–9)
Spam email detection	Email features	Spam / Not Spam
Student result prediction	Study hours, attendance	Pass / Fail
House price prediction	House features	Price
Medical diagnosis	Patient health data	Disease / No Disease
Loan approval	Financial information	Approved / Rejected
Customer churn prediction	Customer usage data	Stay / Leave
Sentiment analysis	Text features	Positive / Negative

Key Point

An MLP works best when the data can be represented as a fixed set of numerical features. It is widely used for classification (e.g., spam detection, disease diagnosis, loan approval) and regression (e.g., house price prediction) tasks.

 

 

Derivation of Backpropagation (MLP)

Backpropagation is derived using the chain rule of calculus. It computes how the error changes with respect to each weight in the network, allowing the weights to be updated to reduce the error.

---

Step 1: Consider a Single Neuron

For one neuron:

$$z = \sum_{i=1}^{n} w_i x_i + b$$
$$y = f(z)$$

where:

• $x_i$ = input
• $w_i$ = weight
• $b$ = bias
• $z$ = weighted sum
• $f(z)$ = activation function
• $y$ = output

---

Step 2: Define the Error (Loss) Function

Using Mean Squared Error (MSE):

$$E = \frac{1}{2}(t-y)^2$$

where:

• $t$ = target output
• $y$ = predicted output

The factor $\frac{1}{2}$ simplifies differentiation.

---

Step 3: Goal

We need to determine how the error changes with a weight $w$:

$$\frac{\partial E}{\partial w}$$

Since $E$ depends on $y$, $y$ depends on $z$, and $z$ depends on $w$, we use the chain rule.

---

Step 4: Apply the Chain Rule

$$\frac{\partial E}{\partial w} = \frac{\partial E}{\partial y} \times \frac{\partial y}{\partial z} \times \frac{\partial z}{\partial w}$$

---

Step 5: Compute Each Derivative

(a) Derivative of Error

$$E=\frac12(t-y)^2$$

Differentiate with respect to $y$:

$$\frac{\partial E}{\partial y} = -(t-y) = (y-t)$$

---

(b) Derivative of Activation Function

If the sigmoid activation is used:

$$y=\sigma(z)=\frac{1}{1+e^{-z}}$$

Its derivative is:

$$\frac{\partial y}{\partial z} = y(1-y)$$

---

(c) Derivative of Weighted Sum

$$z=wx+b$$

Differentiate with respect to $w$:

$$\frac{\partial z}{\partial w}=x$$

---

Step 6: Combine the Results

Substitute into the chain rule:

$$\frac{\partial E}{\partial w} = (y-t)\,y(1-y)\,x$$

This is the gradient for a weight connected to the output neuron.

---

Step 7: Update the Weight

Using gradient descent:

$$w_{\text{new}} = w_{\text{old}} - \eta \frac{\partial E}{\partial w}$$

Substitute the gradient:

$$w_{\text{new}} = w_{\text{old}} - \eta (y-t)\,y(1-y)\,x$$

where $\eta$ is the learning rate.

---

Hidden Layer Derivation

For a hidden neuron, the error is not directly known. It is computed from the errors in the next layer.

Let:

• Hidden neuron output = $h$
  
• Output neuron error term = $\delta_o$

The hidden neuron error term is:

$$\delta_h = h(1-h) \sum_j w_{hj}\delta_j$$

where:

• $w_{hj}$ = weight from hidden neuron $h$ to output neuron $j$
• $\delta_j$ = error term of output neuron $j$

The weight update for a hidden-layer weight is:

$$\Delta w = -\eta\,\delta_h\,x$$

---

Complete Backpropagation Algorithm

1. Initialize weights randomly.
2. Perform feedforward to compute the output.
3. Compute the loss.
4. Calculate output-layer error:
      δ = (y − t)f'(z)
5. Calculate hidden-layer errors:
      δh = f'(zh) Σ(wδ)
6. Update weights:
      w = w − ηδx
7. Repeat for all training examples until the error is minimized.

---

Flow Diagram

Input
   │
   ▼
Weighted Sum (z = wx + b)
   │
   ▼
Activation Function
   │
   ▼
Output (y)
   │
   ▼
Loss Function E
   │
   ▼
Compute Gradient using Chain Rule
   │
   ▼
Backpropagate Error
   │
   ▼
Update Weights

Key Formula Summary

Step	Formula
Weighted sum	$z=\sum wx+b$
Activation	$y=f(z)$
Loss	$E=\frac12(t-y)^2$
Chain rule	$\frac{\partial E}{\partial w}=\frac{\partial E}{\partial y}\frac{\partial y}{\partial z}\frac{\partial z}{\partial w}$
Output gradient (sigmoid + MSE)	$\frac{\partial E}{\partial w}=(y-t)\,y(1-y)\,x$
Weight update	$w_{\text{new}}=w_{\text{old}}-\eta\frac{\partial E}{\partial w}$

This derivation shows that backpropagation uses the chain rule to efficiently compute gradients for every weight in the network, enabling gradient descent to minimize the prediction error.

Radial Basis Functions (RBF) and Splines

Radial Basis Functions (RBFs) and Splines are mathematical techniques used for function approximation, interpolation, regression, and pattern recognition. They are widely used in machine learning, neural networks, computer graphics, and numerical analysis.

---

1. Radial Basis Functions (RBF)

Definition

A Radial Basis Function (RBF) is a function whose output depends only on the distance between an input point and a fixed center.

Mathematically,

$$\phi(x)=\phi(\|x-c\|)$$

where:

• $x$ = input vector
• $c$ = center of the RBF
• $\|x-c\|$= Euclidean distance between $x$ and $c$

The output depends only on the distance, not on the direction.

---

Common RBF Functions

(a) Gaussian RBF

$$\phi(r)=e^{-\frac{r^2}{2\sigma^2}}$$

where:

• $r=\|x-c\|$
• $\sigma$ = spread (width)

This is the most commonly used RBF.

---

(b) Multiquadric

$$\phi(r)=\sqrt{r^2+c^2}$$

---

(c) Inverse Multiquadric

$$\phi(r)=\frac{1}{\sqrt{r^2+c^2}}$$

---

(d) Thin Plate Spline

$$\phi(r)=r^2\ln(r)$$

---

RBF Neural Network Structure

Input Layer
      │
      ▼
RBF Hidden Layer
(Gaussian Functions)
      │
      ▼
Output Layer

The hidden neurons compute radial basis functions, and the output layer combines them using weighted sums.

---

Advantages of RBF

• Fast learning
• Good approximation capability
• Handles nonlinear problems
• Simple network architecture

---

Applications

• Pattern recognition
• Image classification
• Time-series prediction
• Function approximation
• Control systems

---

2. Splines

Definition

A Spline is a smooth piecewise polynomial function used to approximate or interpolate data.

Instead of fitting one high-degree polynomial to all the data, splines fit several low-degree polynomials that join smoothly at specific points.

---

Knots

The points where two polynomial pieces meet are called knots.

Example:

Polynomial 1 | Polynomial 2 | Polynomial 3
------------|--------------|-------------
      Knot 1       Knot 2

The function and its derivatives are continuous at the knots.

---

Types of Splines

(a) Linear Spline

Uses straight lines between data points.

---

(b) Quadratic Spline

Uses second-degree polynomials.

---

(c) Cubic Spline

Uses third-degree polynomials.

This is the most commonly used spline because it provides a smooth curve.

---

(d) B-Spline

Uses basis functions to build smooth curves efficiently.

---

(e) Natural Cubic Spline

Assumes the second derivative is zero at the endpoints, producing a smooth boundary behavior.

---

Cubic Spline Equation

For one interval,

$$S(x)=a+bx+cx^2+dx^3$$

The coefficients are chosen so that:

• the spline passes through the data points,
• the first derivative is continuous,
• the second derivative is continuous.

---

Advantages of Splines

• Smooth approximation
• Avoids oscillations common with high-degree polynomials
• Accurate interpolation
• Efficient computation

---

Applications

• Computer graphics
• CAD/CAM
• Image processing
• Data interpolation
• Curve fitting
• Robotics

---

Difference Between RBF and Splines

Feature	Radial Basis Function (RBF)	Splines
Basic idea	Depends on distance from a center	Piecewise polynomial functions
Mathematical form	Radial function	Polynomial segments
Input dependence	Distance from center	Interval between knots
Main purpose	Function approximation and classification	Curve fitting and interpolation
Common function	Gaussian	Cubic spline
Neural network use	Yes (RBF Networks)	Generally no
Smoothness	Controlled by spread parameter ($\sigma$)	Controlled by continuity at knots

---

Example

Suppose the following data points are given:

x	y
1	2
2	4
3	5
4	7

• Using an RBF, each data point can act as a center. The prediction at a new point is obtained by combining the outputs of radial basis functions centered at these points.
• Using a cubic spline, separate cubic polynomials are fitted between each pair of consecutive data points, ensuring the overall curve is smooth at the knots.

---

Summary

• Radial Basis Functions (RBFs) are distance-based functions used in neural networks for nonlinear function approximation, interpolation, and classification.
• Splines are smooth piecewise polynomial functions used to fit curves and interpolate data while maintaining continuity at the knots.
• Both methods are powerful tools for modeling nonlinear relationships, but RBFs are more common in machine learning, whereas splines are widely used in interpolation, computer graphics, and numerical analysis.

RBF Network and the Curse of Dimensionality

Radial Basis Function (RBF) Network

An RBF Network is a type of artificial neural network used for classification, regression, function approximation, and interpolation. It consists of three layers:

1. Input Layer
2. Hidden Layer (contains Radial Basis Function neurons, usually Gaussian)
3. Output Layer

Input Layer → RBF Hidden Layer → Output Layer

Each hidden neuron computes its activation based on the distance between the input vector and its center.

The Gaussian RBF is:

$$\phi(x)=\exp\left(-\frac{\|x-c\|^2}{2\sigma^2}\right)$$

where:

• $x$ = input vector
• $c$ = center of the RBF
• $\sigma$ = spread (width)
• $\|x-c\|$ = Euclidean distance

---

Curse of Dimensionality

The curse of dimensionality refers to the difficulties that arise when the number of input features (dimensions) becomes very large.

As the number of dimensions increases:

• The input space grows exponentially.
• Data points become sparse.
• Much more training data is needed to cover the input space.
• Learning and generalization become harder.

---

Why It Affects RBF Networks

RBF networks rely on distance between the input and the centers.

In high-dimensional spaces:

1. Distances Become Less Informative

In low dimensions, nearby and distant points are clearly distinguishable.

Example (2D):

Center ●

Nearby point  ○
Far point     ○──────────

In high dimensions, the distances between points tend to become similar, making it harder for Gaussian RBFs to distinguish between "near" and "far" points.

---

2. More Hidden Neurons Are Needed

Each RBF neuron covers only a small region of the input space.

As dimensions increase, many more centers are required to adequately represent the data.

For example:

Dimensions	Approximate Number of Centers Needed
2	100
5	Thousands
10	Millions (may be required)

This greatly increases memory and computation.

---

3. Training Becomes Expensive

A larger number of hidden neurons means:

• More parameters to estimate.
• More computation during training.
• Slower predictions.

---

4. Poor Generalization

When data are sparse in high-dimensional spaces:

• The model may overfit the training data.
• It may perform poorly on unseen data because it has not observed enough examples across the input space.

---

Example

Suppose an RBF network predicts house prices.

Case 1: 2 Features

• Area
• Number of bedrooms

The model can learn effectively with a moderate amount of data.

Case 2: 100 Features

• Area
• Bedrooms
• Age
• Income
• Nearby schools
• Crime rate
• Transport access
• Weather
• ... (many more)

Now:

• The feature space becomes extremely large.
• More training samples are needed.
• More RBF centers are required.
• Training becomes much slower.

---

How to Reduce the Curse of Dimensionality

1. Feature Selection
   • Keep only the most relevant features.
2. Dimensionality Reduction
   • Use techniques such as Principal Component Analysis (PCA) or autoencoders to reduce the number of features while preserving important information.
3. Increase Training Data
   • More data helps cover the high-dimensional space, although this is not always practical.
4. Choose Appropriate Width ($\sigma$)
   • Selecting a suitable Gaussian spread can improve performance, but it cannot completely eliminate the curse of dimensionality.
5. Regularization
   • Apply regularization techniques to reduce overfitting.

---

Advantages of RBF Networks Despite This Limitation

• Fast learning compared to some multilayer networks.
• Good at approximating nonlinear functions.
• Simple architecture.
• Effective for low- and moderate-dimensional problems.

---

Summary

The curse of dimensionality is a major limitation of RBF networks because they depend on distance-based calculations. As the number of input features increases, the input space grows exponentially, distances become less discriminative, many more RBF centers are required, and training becomes more computationally expensive. Techniques such as feature selection, dimensionality reduction, and regularization help reduce these effects and improve the performance of RBF networks on higher-dimensional data.

Interpolation and Basis Functions

1. Interpolation

Definition

Interpolation is the process of estimating unknown values that lie between known data points. It constructs a function that passes exactly through the given data points.

If the known data points are:

$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$

then interpolation finds a function $f(x)$such that:

$$f(x_i)=y_i,\quad i=1,2,\ldots,n$$

Example

Given the data:

x	y
1	2
2	4
3	6

To estimate the value at $x=\mathrm{2.5\; interpolation\; may\; give:}$

$$f(2.5)=5$$

This value lies between the known points.

---

Types of Interpolation

1. Linear Interpolation

• Uses straight lines between two consecutive points.
• Simple and fast.

Formula:

$$y=y_1+\frac{(x-x_1)}{(x_2-x_1)}(y_2-y_1)$$

---

2. Polynomial Interpolation

• Fits one polynomial through all data points.
• Accurate for a small number of points.
• May oscillate if many points are used (Runge's phenomenon).

---

3. Spline Interpolation

• Fits several low-degree polynomials between intervals.
• Produces a smooth curve.
• Cubic splines are the most common.

---

4. RBF Interpolation

• Uses radial basis functions centered at the data points.
• Works well for scattered and multidimensional data.

---

2. Basis Functions

Definition

A basis function is a building block used to construct a more complex function.

Instead of representing a function directly, it is expressed as a weighted sum of basis functions:

$$f(x)=\sum_{i=1}^{n} w_i\phi_i(x)$$

where:

• $w_i$ = weights (coefficients)
• $\phi_i(x)$= basis functions

---

Common Basis Functions

(a) Polynomial Basis

$$\phi_1(x)=1$$
$$\phi_2(x)=x$$
$$\phi_3(x)=x^2$$
$$\phi_4(x)=x^3$$

Function:

$$f(x)=w_0+w_1x+w_2x^2+w_3x^3$$

---

(b) Gaussian Basis Function

$$\phi(x)=e^{-\frac{(x-c)^2}{2\sigma^2}}$$

Used in:

• RBF Networks
• Function approximation
• Interpolation

---

(c) Sigmoid Basis Function

$$\phi(x)=\frac{1}{1+e^{-x}}$$

Used in neural networks.

---

(d) Trigonometric Basis

$$\phi(x)=\sin(x),\quad \cos(x)$$

Used in Fourier series and signal processing.

---

Relationship Between Interpolation and Basis Functions

Interpolation often represents the unknown function as a weighted sum of basis functions:

$$f(x)=\sum_{i=1}^{n}w_i\phi_i(x)$$

The weights are chosen so that:

$$f(x_i)=y_i$$

for every known data point.

---

Example Using Gaussian Basis Functions

Suppose the data points are:

x	y
1	2
2	5
3	4

Choose Gaussian basis functions centered at each data point:

$$\phi_i(x)=\exp\left(-\frac{(x-c_i)^2}{2\sigma^2}\right)$$

The interpolating function is:

$$f(x)=w_1\phi_1(x)+w_2\phi_2(x)+w_3\phi_3(x)$$

The weights $w_1, w_2, w_3$ are computed so that the function passes exactly through all three data points.

---

Applications

• Function approximation
• Machine learning
• Neural networks (RBF Networks)
• Computer graphics
• Signal processing
• Image processing
• Curve fitting
• Scientific computing

---

Difference Between Interpolation and Basis Functions

Feature	Interpolation	Basis Functions
Purpose	Estimate unknown values between known points	Build complex functions from simpler components
Output	A curve or function passing through data	Building blocks used to form the function
Depends on	Known data points	Chosen mathematical functions
Examples	Linear, spline, RBF interpolation	Polynomial, Gaussian, sigmoid, trigonometric
Use	Curve fitting and estimation	Function representation and approximation

Summary

• Interpolation estimates unknown values between known data points by constructing a function that passes through the given data.
• Basis functions are the elementary functions (such as polynomials or Gaussians) combined with weights to represent more complex functions.
• In many interpolation methods, including RBF interpolation and spline interpolation, the interpolating function is expressed as a weighted sum of basis functions.

Support Vector Machine (SVM)

A Support Vector Machine (SVM) is a supervised machine learning algorithm used for classification and regression. It is mainly used for binary classification problems and works by finding the best separating boundary (hyperplane) between different classes.

---

Definition

An SVM finds the optimal hyperplane that separates data points of different classes while maximizing the margin between them.

---

Basic Idea

Consider two classes:

• Class A (●)
• Class B (▲)

An SVM tries to find a line (in 2D) or a hyperplane (in higher dimensions) that separates the two classes with the largest possible margin.

        ▲      ▲

----------------------  ← Optimal Hyperplane

●      ●      ●

The larger the margin, the better the model is expected to generalize to new data.

---

Important Terms

1. Hyperplane

A hyperplane is the decision boundary that separates different classes.

• In 2D: a line
• In 3D: a plane
• In n dimensions: a hyperplane

Equation of a hyperplane:

$$w^T x + b = 0$$

where:

• $w$ = weight vector
• $x$ = input vector
• $b$ = bias

---

2. Support Vectors

Support vectors are the data points closest to the hyperplane.

They determine the position and orientation of the decision boundary.

▲     ▲
   ▲

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

   ●
●      ●

The nearest points (support vectors) are the most important points in training the SVM.

---

3. Margin

The margin is the distance between the hyperplane and the nearest data points from each class.

Support Vector
      ▲
      |
------|---------------- Hyperplane
      |
      ●
Support Vector

SVM aims to maximize this margin.

---

Mathematical Representation

The hyperplane is:

$$w^T x+b=0$$

Classification rule:

$$\begin{cases} w^T x+b\ge0 & \text{Class +1} \\ w^T x+b<0 & \text{Class -1} \end{cases}$$

Margin:

$$\text{Margin}=\frac{2}{\|w\|}$$

Maximizing the margin is equivalent to minimizing $\|w\|$.

---

Types of SVM

1. Linear SVM

Used when the data are linearly separable.

▲ ▲ ▲

-----------

● ● ●

---

2. Non-Linear SVM

Used when a straight line cannot separate the classes.

A kernel function maps the data into a higher-dimensional space where a linear separator may exist.

---

Kernel Functions

A kernel computes similarity between points without explicitly transforming them into higher dimensions.

Common kernels include:

1. Linear Kernel

$$K(x,y)=x^T y$$

Suitable for linearly separable data.

---

2. Polynomial Kernel

$$K(x,y)=(x^T y+c)^d$$

Captures polynomial relationships.

---

3. Radial Basis Function (RBF) Kernel

$$K(x,y)=\exp(-\gamma\|x-y\|^2)$$

One of the most widely used kernels for nonlinear classification.

---

4. Sigmoid Kernel

$$K(x,y)=\tanh(\alpha x^T y+c)$$

Resembles the activation function used in neural networks.

---

Advantages of SVM

• Effective in high-dimensional feature spaces.
• Works well for both linear and nonlinear classification.
• Maximizes the margin, which often improves generalization.
• Uses only the support vectors, making the decision boundary compact.
• Can also be adapted for regression (Support Vector Regression, SVR).

---

Disadvantages of SVM

• Training can be slow for very large datasets.
• Choosing the right kernel and its parameters can be challenging.
• Less effective when classes overlap significantly or when the data contain substantial noise.
• Model interpretation is less intuitive than for simple linear models.

---

Applications

• Spam email detection
• Face recognition
• Handwritten digit recognition
• Text classification
• Medical diagnosis
• Image classification
• Bioinformatics (e.g., gene classification)

---

Example

Suppose we want to classify emails as Spam or Not Spam.

Input features:

• Number of links
• Number of suspicious words
• Sender reputation

The SVM learns the optimal decision boundary from labeled training data. When a new email is received, it determines on which side of the hyperplane the email lies and classifies it accordingly.

---

SVM Workflow

Training Data
      │
      ▼
Choose Kernel
      │
      ▼
Find Support Vectors
      │
      ▼
Construct Maximum-Margin Hyperplane
      │
      ▼
Train SVM Model
      │
      ▼
Predict Class for New Data

---

Summary

Feature	SVM
Learning type	Supervised learning
Main purpose	Classification (also regression)
Decision boundary	Hyperplane
Key data points	Support vectors
Goal	Maximize the margin
Handles nonlinear data	Yes, using kernels
Common kernels	Linear, Polynomial, RBF, Sigmoid

Key Point

A Support Vector Machine (SVM) is a powerful supervised learning algorithm that finds the maximum-margin hyperplane to separate classes. By relying on support vectors and kernel functions, SVMs can solve both linear and nonlinear classification problems effectively.

Learning with Trees: Decision Trees, Construction, CART

Decision Trees are supervised machine-learning algorithms used for both classification and regression. They make predictions by repeatedly splitting data according to feature values, forming a tree-like structure.

---

1. Learning with Trees

A decision tree consists of:

• Root node – starting point of the tree
• Internal/decision nodes – conditions based on features
• Branches – outcomes of those conditions
• Leaf nodes – final prediction

Example:

                 Weather
                /       \
             Sunny      Rain
              /           \
        Humidity          Wind
        /     \           /   \
      High    Normal    Weak  Strong
       |         |        |      |
      No        Yes      Yes     No

Here, the tree predicts whether a person will play tennis based on weather conditions.

Why use decision trees?

• Easy to understand and interpret
• Can handle numerical and categorical features
• Requires relatively little data preprocessing
• Can model nonlinear relationships
• Useful for both classification and regression

---

2. Decision Trees

A decision tree learns a sequence of if–then rules from training data.

For example:

IF income > ₹50,000
    IF age > 30
        → Loan Approved
    ELSE
        → Loan Rejected
ELSE
    → Loan Rejected

The algorithm tries to choose splits that make the resulting groups as pure as possible.

Classification tree

The target is a category.

Examples:

• Spam / Not Spam
• Disease / No Disease
• Pass / Fail
• Fraud / Not Fraud

Regression tree

The target is a numerical value.

Examples:

• House price
• Sales
• Temperature
• Revenue

---

3. Constructing Decision Trees

The general process is:

Training Data
     ↓
Select the best feature/split
     ↓
Split the data
     ↓
Create child nodes
     ↓
Repeat recursively
     ↓
Stopping condition
     ↓
Leaf prediction

The important question is:

How do we choose the best split?

Different decision-tree algorithms use different criteria.

---

3.1 Entropy

Entropy measures the impurity or uncertainty in a dataset.

For a binary classification problem:

$$Entropy(S)=-p_1\log_2(p_1)-p_2\log_2(p_2)$$

where $p_1$ and $p_2$ are the proportions of the two classes.

Example

Suppose a node contains:

• 5 Yes
• 5 No

Then:

$$p(Yes)=0.5$$ $$p(No)=0.5$$

Therefore:

$$Entropy=-0.5\log_2(0.5)-0.5\log_2(0.5)=1$$

This represents maximum uncertainty for a binary node.

If all observations belong to one class:

$$Entropy=0$$

So:

Node composition	Entropy
10 Yes, 0 No	0
8 Yes, 2 No	0.722
5 Yes, 5 No	1
2 Yes, 8 No	0.722
0 Yes, 10 No	0

---

4. Information Gain

Information Gain measures how much a split reduces uncertainty.

$$IG(S,A)=Entropy(S)- \sum_{v \in Values(A)} \frac{|S_v|}{|S|}Entropy(S_v)$$

The feature with the largest information gain is selected as the split.

Simple example

Suppose:

Before split:
Entropy = 1.0

After splitting:
Weighted entropy = 0.4

Then:

$$IG=1.0-0.4=0.6$$

A larger information gain indicates a stronger reduction in impurity.

---

5. Gini Impurity

Another popular splitting criterion is Gini impurity.

$$Gini(S)=1-\sum_{i=1}^{K}p_i^2$$

For binary classification:

$$Gini=1-p_{Yes}^2-p_{No}^2$$

For 50% Yes and 50% No:

$$Gini=1-(0.5)^2-(0.5)^2$$ $$Gini=0.5$$

For a completely pure node:

$$Gini=0$$

Lower Gini impurity is better.

---

6. Classification and Regression Trees — CART

CART stands for:

Classification and Regression Trees

It is a popular decision-tree methodology used for both classification and regression.

CART generally creates binary splits.

                Feature X < 50?
                 /          \
               Yes           No
              /               \
           Node 1            Node 2

Unlike some tree algorithms that can create multiple branches from a categorical feature, CART typically divides a node into two child nodes.

---

6.1 CART Classification

For classification, CART commonly uses Gini impurity to select splits.

The algorithm searches for a split that minimizes the weighted impurity of the resulting child nodes.

Conceptually:

$$Impurity_{split} = \frac{N_L}{N}I(L) + \frac{N_R}{N}I(R)$$

where:

• $N_L$ = number of samples in left node
• $N_R$ = number of samples in right node
• $N$ = total samples
• $I(L), I(R)$ = impurity of the child nodes

The split producing the lowest weighted impurity is selected.

---

7. CART Regression

For regression, the target variable is continuous.

Example:

                    Area < 1500?
                   /            \
                 Yes             No
                /                 \
          Price prediction    Price prediction

CART regression commonly chooses splits that minimize squared error.

A leaf prediction is usually the mean target value of the training observations reaching that leaf.

For example:

Leaf contains:

₹40 lakh
₹45 lakh
₹50 lakh

Prediction:

$$\frac{40+45+50}{3}=45$$

So the regression tree predicts:

₹45 lakh

---

8. Least-Squares Regression

Regression trees are closely related to minimizing squared prediction error within leaves.

For a leaf $R_j$, the prediction can be written as:

$$\hat{y}= \frac{1}{|R_j|} \sum_{x_i\in R_j}y_i$$

The objective is to minimize:

$$\sum_i(y_i-\hat{y}_i)^2$$

$\hat{y} = b_0 + b_1x$

$\hat{y} = 8.49 - 0.54x$

R² = 0.72 · b₀ = intercept · b₁ = slope · least squares minimizes squared vertical residual gaps.

Focus

DataLinePredictionsResiduals

Drag a point to refit the line.

---

9. Stopping Criteria

A tree can continue splitting until every leaf contains only a few observations. This can cause overfitting.

Common stopping conditions include:

• Maximum tree depth reached
• Minimum number of samples required for splitting
• Minimum number of samples in a leaf
• No useful improvement from a split
• Maximum number of leaf nodes reached

For example:

DecisionTreeClassifier(
    max_depth=5,
    min_samples_split=10,
    min_samples_leaf=5
)

---

10. Overfitting and Pruning

A very deep tree may memorize the training data.

Small tree                  Very deep tree

     X                         X
    / \                       / \
   X   X                     X   X
  / \ / \                   / \ / \
 ... ...                   ... ... ...

Overfitting

Training accuracy: 99%
Testing accuracy: 72%

The model has learned the training data too specifically.

Pruning

Pruning removes unnecessary branches to improve generalization.

Two approaches are:

Pre-pruning

Stop tree growth early using parameters such as:

• max_depth
• min_samples_split
• min_samples_leaf

Post-pruning

First grow a larger tree and then remove branches that provide insufficient benefit.

---

11. Decision Tree Algorithm — Summary

                 Training Dataset
                        ↓
                Calculate impurity
                        ↓
             Evaluate possible splits
                        ↓
              Select best split
                        ↓
                  Split dataset
                   /          \
                  /            \
             Child node     Child node
                  ↓            ↓
              Repeat recursively
                        ↓
                 Stopping rule
                        ↓
                  Leaf prediction

Classification

Input → Decision Tree → Class
                    ↓
             Gini / Entropy

Regression

Input → Decision Tree → Numerical value
                    ↓
             Squared Error

---

12. Classification vs Regression Trees

Feature	Classification Tree	Regression Tree
Target	Categorical	Numerical
Example	Spam/Not Spam	House price
Common CART criterion	Gini impurity	Squared error
Leaf prediction	Class / class probability	Mean value
Output	Category	Number
Evaluation	Accuracy, Precision, Recall, F1	MAE, MSE, RMSE, R²

---

13. Advantages

Decision trees:

• Easy to interpret
• Easy to visualize
• Handle nonlinear relationships
• Can handle categorical and numerical variables
• Do not require feature scaling
• Can be used for classification and regression

14. Limitations

• Can overfit easily
• Small changes in data can produce a different tree
• Individual trees may have lower predictive performance than ensemble methods
• Deep trees can become difficult to interpret
• Greedy split selection does not necessarily produce a globally optimal tree

---

Exam-Oriented Quick Revision

Decision Tree: A supervised learning model that recursively divides data using feature-based rules.

Entropy: Measures uncertainty/impurity.

$$H(S)=-\sum p_i\log_2p_i$$

Information Gain: Reduction in entropy after a split.

$$IG=H(parent)-H(children)$$

Gini Impurity:

$$Gini=1-\sum p_i^2$$

CART: Classification and Regression Trees; commonly uses binary splits.

Classification Tree: Predicts discrete classes.

Regression Tree: Predicts continuous numerical values.

Pruning: Removes unnecessary tree branches to reduce overfitting.