(5th sem) AIML Chapter 3: Complete Concepts Guide

13.1 Introduction to Decision Tree LearningCopy Anchor Link

Definition: Decision Tree Learning is a supervised learning technique that constructs a tree-structured model for classification and prediction by recursively partitioning training data based on attribute values.

Key Concepts:

• Machine Learning Classification: The process of assigning data instances to predefined classes by learning a mapping between input attributes and output labels.
• Decision Tree: A tree-structured model consisting of nodes and branches representing decision rules.
• Supervised Learning: Learning from labeled training examples where the correct output is known.

How It Works:

1. Start with the entire dataset at the root node.
2. Select the best attribute to split the data based on a splitting criterion.
3. Partition the data into subsets based on attribute values.
4. Repeat recursively for each subset until a stopping condition is met.
5. Leaf nodes provide the final classification.

Advantages of Decision Trees:

Classification Process:

Training Data → Learning Algorithm → Classification Model → New Instance → Prediction

13.2 Decision Tree ComponentsCopy Anchor Link

Four Structural Components:

Structure:

                [Root Node: Weather]
               /         |          \
          Sunny       Rainy        Cloudy
            |           |            |
    [Internal: Humidity] [Leaf: Play=No] [Internal: Wind]
         /      \                        /      \
      High     Low                   Strong    Weak
       |        |                       |         |
   [Leaf: No] [Leaf: Yes]          [Leaf: No] [Leaf: Yes]

13.3 Applications of Decision TreesCopy Anchor Link

13.4 Characteristics of Decision Tree LearningCopy Anchor Link

UNIT 14: DECISION TREE REPRESENTATIONCopy Anchor Link

14.1 Decision Tree RepresentationCopy Anchor Link

Tree Structure:

• Hierarchical arrangement of nodes and branches
• Starting from root node, data instances travel through branches based on attribute values
• Ending at leaf nodes that provide final classification

Attribute-Based Splitting:

• Process of dividing a dataset into subsets based on attribute values
• Objective: Create subsets more homogeneous than the original dataset
• Attribute selection uses measures like Entropy and Information Gain

Splitting Process:

Dataset → Weather? → Sunny / Rainy / Cloudy
                     ↓
              Subset1 / Subset2 / Subset3

14.2 Appropriate Problems for Decision Tree LearningCopy Anchor Link

14.3 EntropyCopy Anchor Link

Definition: Entropy measures the impurity, uncertainty, or disorder in a dataset.

Mathematical Formula:

Where:

• $p_i$ = proportion of instances belonging to class $i$
• $c$ = number of classes

Interpretation:

Example Calculation:

• Dataset: 9 Positive, 5 Negative (Total = 14)
• P(Positive) = 9/14, P(Negative) = 5/14
• Entropy = −(9/14)log₂(9/14) − (5/14)log₂(5/14) ≈ 0.94

14.4 Information GainCopy Anchor Link

Definition: Information Gain measures the reduction in entropy achieved after splitting the dataset on a particular attribute.

Mathematical Formula:

Where:

• $S$ = dataset
• $A$ = attribute
• $S_v$ = subset of $S$ where attribute $A = v$

Attribute Selection Process:

1. Calculate dataset entropy
2. Split dataset using an attribute
3. Calculate entropy of each subset
4. Compute weighted average entropy
5. Subtract from original entropy
6. Select attribute with highest Information Gain

Example:

UNIT 15: ID3 ALGORITHMCopy Anchor Link

15.1 Introduction to ID3 AlgorithmCopy Anchor Link

History: Developed by Ross Quinlan in 1986. One of the earliest and most influential decision tree learning algorithms.

Purpose:

• Construct decision tree by repeatedly selecting attribute with highest Information Gain
• Minimize classification errors
• Reduce uncertainty
• Generate understandable rules
• Build compact decision trees

15.2 Working of ID3 AlgorithmCopy Anchor Link

Selection of Root Node:

1. Compute entropy for each attribute
2. Calculate Information Gain
3. Choose attribute with highest gain as root

Recursive Partitioning:

• After root selection, dataset partitioned into subsets
• Same process repeated recursively for each subset
• Each subset treated as new dataset

Termination Conditions:

• All examples belong to same class
• No attributes remain
• Dataset becomes empty

Tree Construction: Top-down approach

15.3 Steps of ID3 AlgorithmCopy Anchor Link

Algorithm Flow:

Start → Calculate Entropy → Calculate Information Gain → Select Best Attribute
→ Create Node → Partition Data → Recurse → Stop

15.4 Illustrative ExampleCopy Anchor Link

Training Dataset:

Information Gain Values:

• Outlook = 0.45
• Humidity = 0.18

Result: Outlook becomes root node (highest gain)

Classification Example:

• New instance: Outlook = Sunny, Humidity = Normal
• Path: Outlook → Sunny → Humidity → Normal → Play = Yes

15.5 Advantages and Limitations of ID3Copy Anchor Link

UNIT 16: INTRODUCTION TO ARTIFICIAL NEURAL NETWORKSCopy Anchor Link

16.1 Introduction to Artificial Neural NetworksCopy Anchor Link

Definition: ANNs are computational systems inspired by the structure and functioning of the human brain, consisting of interconnected artificial neurons that work together to solve complex problems.

Inspiration from Biological Neurons:

• Human brain contains ~86 billion neurons connected through trillions of synapses
• Biological neuron components: Dendrites, Cell Body (Soma), Axon, Synapses
• Dendrites receive signals; cell body processes; axon transmits; synapses connect

History of Neural Networks:

Characteristics of Neural Networks:

16.2 Biological versus Artificial NeuronsCopy Anchor Link

Biological Neuron Structure:

Artificial Neuron Model:

• Receives inputs
• Multiplies each input by a weight
• Sums weighted inputs
• Applies activation function
• Produces output

Mathematical Formula:

Comparison:

16.3 Applications of Neural NetworksCopy Anchor Link

UNIT 17: NEURAL NETWORK REPRESENTATIONCopy Anchor Link

17.1 Neural Network ArchitectureCopy Anchor Link

Three Layer Types:

Architecture Diagram:

Input Layer    Hidden Layer    Output Layer
   x1 ──┐
        ├──→ h1 ──┐
   x2 ──┤        ├──→ y
        ├──→ h2 ──┤
   x3 ──┘        └──→

17.2 Components of Neural NetworksCopy Anchor Link

Activation Functions:

Neuron Computation:

Inputs → Weights Applied → Summation + Bias → Activation Function → Output

17.3 Appropriate Problems for Neural NetworksCopy Anchor Link

17.4 Types of Neural NetworksCopy Anchor Link

UNIT 18: PERCEPTRON MODELCopy Anchor Link

18.1 Introduction to PerceptronCopy Anchor Link

Definition: A perceptron is a computational model that simulates a biological neuron by receiving inputs, processing them through weighted connections, and generating an output based on an activation function.

Mathematical Formula:

Historical Background:

18.2 Structure of a PerceptronCopy Anchor Link

Components:

Structure Diagram:

x1 ──(w1)──┐
           │
x2 ──(w2)──┼──→ Σ ──→ Activation ──→ Output
           │
x3 ──(w3)──┘
           │
     Bias ─┘

Example Calculation:

• x₁=1, x₂=0, x₃=1
• w₁=0.5, w₂=0.3, w₃=0.8
• Bias = 0.2
• Net = (1×0.5) + (0×0.3) + (1×0.8) + 0.2 = 1.5
• If threshold = 1, Output = 1

18.3 Perceptron Learning RuleCopy Anchor Link

Weight Initialization: Small random values (e.g., w₁=0.2, w₂=0.4, w₃=0.1)

Error Calculation:

Weight Update Mechanism:

Where:

• η = Learning rate
• x = Input value

Learning Rate Effects:

Example Weight Update:

• Input = 1, Weight = 0.4, Target = 1, Output = 0, η = 0.2
• w_new = 0.4 + 0.2(1-0)(1) = 0.6

Learning Cycle:

Training Data → Prediction → Calculate Error → Update Weights → Repeat Until Error = 0

18.4 Applications of PerceptronsCopy Anchor Link

18.5 Limitations of PerceptronsCopy Anchor Link

Linear Separability Constraint:

• Perceptron can only classify linearly separable data
• A dataset is linearly separable if a straight line can divide the classes

XOR Problem:

• No single straight line can separate XOR output classes
• Single-layer perceptron cannot solve XOR problem

Other Limitations:

• Limited learning capability
• Binary output restriction
• No hidden layers
• Poor performance on complex data

Solution: Multi-Layer Perceptrons (MLPs) and Backpropagation Algorithm

UNIT 19: BACKPROPAGATION ALGORITHMCopy Anchor Link

19.1 Introduction to BackpropagationCopy Anchor Link

Definition: Backpropagation is a supervised learning algorithm used for training Multi-Layer Perceptrons by adjusting connection weights based on errors produced during prediction.

Need for Backpropagation:

• Perceptron learning rule works only for single-layer networks
• Real-world problems require multiple hidden layers
• Hidden layer weights cannot be directly determined
• Backpropagation calculates each neuron’s contribution to overall error

Multi-Layer Learning:

• Input Layer
• One or More Hidden Layers
• Output Layer
• All layers learn simultaneously

Concept Flow:

Training Data → Forward Propagation → Predicted Output → Error Calculation
→ Backward Propagation → Weight Adjustment → Improved Prediction

19.2 Forward PropagationCopy Anchor Link

Definition: First phase where input data passes through network layer by layer until output is generated.

Steps:

1. Input Processing: Present input data to input layer
2. Weighted Sum Calculation: Net = Σwᵢxᵢ + b
3. Activation Function Application: Apply sigmoid, ReLU, etc.
4. Output Generation: Produce final prediction

Forward Propagation Flow:

Input Data → Weighted Sum → Activation Function → Hidden Layer
→ Output Layer → Prediction

19.3 Error ComputationCopy Anchor Link

Definition: Evaluating prediction accuracy by computing error between predicted and actual output.

Error Function (Mean Squared Error):

Example:

• Target = 1, Predicted = 0.8
• E = ½(1−0.8)² = 0.02

Performance Measures:

• Mean Squared Error (MSE)
• Accuracy
• Precision
• Recall

Error Computation Process:

Target Output → Compare → Predicted Output → Error Calculation

19.4 Backward PropagationCopy Anchor Link

Definition: Heart of backpropagation; error propagates backward through network to adjust weights.

Error Propagation:

1. Output layer receives error first
2. Error transmitted backward to hidden layers
3. Each neuron receives error proportional to its contribution
4. Network determines which connections need adjustment

Gradient Descent:

• Optimization technique to minimize error
• Moves weights in direction opposite to error gradient
• Continuously moves toward minimum error point

Error Propagation Flow:

Output Error → Output Layer → Hidden Layer → Input Layer

19.5 Weight Update ProcessCopy Anchor Link

Learning Rate (η):

Weight Adjustment Formula:

Where:

• w_old = Current weight
• η = Learning rate
• ∂E/∂w = Error gradient

Training Cycle:

Initialize Weights → Forward Propagation → Calculate Error
→ Backward Propagation → Update Weights → Repeat Training

19.6 Advantages and ApplicationsCopy Anchor Link

Advantages:

Applications:

CHAPTER 3 SUMMARY TABLECopy Anchor Link

KEY FORMULAS REFERENCECopy Anchor Link