Introduction to AdaBoost

• Educational video by Josh Stormer on Stack Quest
• Covers AdaBoost combined with decision trees (most common implementation)
• Prerequisites: knowledge of decision trees and random forests

Three Core Concepts Behind AdaBoost

• Concept 1: AdaBoost uses weak learners (stumps) vs full-sized trees
  • Random forest: full-sized trees with no predetermined max depth
  • AdaBoost: uses stumps (one node + two leaves)
  • Stumps are weak learners but effective when combined
• Concept 2: Weighted voting vs equal voting
  • Random forest: each tree has equal vote
  • AdaBoost: some stumps get more say than others based on performance
• Concept 3: Sequential vs independent creation
  • Random forest: trees made independently
  • AdaBoost: order matters - each stump learns from previous stumps' mistakes

Dataset and Initial Setup

• Heart disease prediction dataset
• Variables: chest pain, blocked arteries, patient weight
• Initial sample weights: 1/8 for each sample (8 total samples)
• All samples equally important initially

Creating First Stump

• Test each variable for best classification performance
• Chest pain: 3 correct, 2 incorrect (with chest pain); 2 correct, 1 incorrect (without)
• Blocked arteries: similar analysis
• Patient weight: threshold at 176 pounds determined optimal
• Gini index calculation shows patient weight has lowest value
• First stump: patient weight > 176

Determining Stump Voting Weight (Amount of Say)

• Formula: Amount of say = 1/2 × log((1 - total error) / total error)
• Total error = sum of sample weights for incorrectly classified samples
• First stump error: 1/8 (one misclassified sample)
• Amount of say = 0.97
• Graph shows relationship between error and voting weight:
  • Low error → large positive say
  • 0.5 error → zero say
  • High error → large negative say

Sample Weight Modification Process

• Increase weights for incorrectly classified samples
• Formula: new weight = old weight × e^(amount of say)
• Decrease weights for correctly classified samples
• Formula: new weight = old weight × e^(-amount of say)
• Incorrectly classified sample: 1/8 × 2.64 = 0.33
• Correctly classified samples: 1/8 × 0.38 = 0.05
• Normalize weights to sum to 1

Creating Subsequent Stumps

• Two approaches for using modified weights:
  1. Weighted Gini index calculation
  2. Bootstrap sampling based on sample weights
• Bootstrap method:
  • Create new dataset same size as original
  • Sample with replacement based on weight distribution
  • Misclassified sample appears 4 times in new dataset
  • Reset all sample weights to equal values
• Process repeats: errors influence next stump creation

Final Classification Process

• Each stump votes on classification
• Multiply each vote by stump's "amount of say"
• Sum votes for each class
• Classify based on highest sum
• Example: "has heart disease" stumps total > "no heart disease" stumps total

Summary of AdaBoost Key Points

1. Combines many weak learners (stumps) for classification
2. Some stumps have more influence than others based on performance
3. Each stump considers previous stumps' mistakes through weighted sampling