Introduction and Prerequisites

• Gradient boost classification appears scary but isn't complex
• Part 4 of gradient boost series focusing on classification
• Requires understanding of first three parts and logistic regression concepts
• Need knowledge of log odds and log likelihood roles in logistic regression
• Uses small training dataset with stumps instead of trees for clarity
• In practice: gradient boost uses trees with 8-32 leaves

Training Dataset Description

• 3 people dataset with features:
  • Whether they like popcorn
  • Age
  • Favorite color
  • Target variable: whether they loved movie Troll 2
• X sub I: row of measurements for prediction
• Y sub I: whether someone loves Troll 2

Loss Function for Classification

• Need differentiable loss function for classification
• Uses negative log likelihood as loss function
• Visual representation: Y-axis = probability of loving Troll 2
  • Red dot (probability = 0): person who doesn't love Troll 2
  • Blue dots (probability = 1): two people who love Troll 2
• Predicted probability example: 0.67
• Log likelihood calculation using summation formula
• For people who love Troll 2: Y sub I = 1, leaves log(P)
• For person who doesn't love Troll 2: Y sub I = 0, leaves log(1-P)
• Better predictions → larger log likelihood
• Multiply by -1 to create loss function (smaller values = better fit)
• Remove summation for single sample processing

Loss Function Transformation

• Transform from predicted probability P to predicted log odds
• Mathematical derivation steps:
  • Distribute minus sign through equation
  • Combine terms using logarithm properties
  • log(P) - log(1-P) = log(P/(1-P)) = log(odds)
  • Convert log(1-P) to function of log odds
  • Final form: -observed×log(odds) + log(1 + e^log(odds))
• Derivative calculation:
  • First part derivative: -observed
  • Second part derivative using chain rule
  • Can express as function of log odds or probability P

Step 1: Initial Prediction

• Find optimal initial prediction using loss function minimization
• Use arg min over gamma (log odds value)
• Take derivative, set equal to zero, solve
• Result: initial predicted probability P = 2/3
  • 2 people love Troll 2 out of 3 total
• Convert to log odds: log(2/1) = 0.69
• F sub 0 of X = 0.69 (initial leaf prediction)

Step 2: Building Trees (M=1)

Part A: Calculate Pseudo Residuals

• Use derivative of loss function with respect to predicted log odds
• Formula: observed - predicted probability
• Residual calculation for each sample:
  • Convert F sub 0 of X to predicted probability P
  • Calculate observed - predicted for each sample
  • R sub 1,1 = 0.33, R sub 2,1 = 0.33, R sub 3,1 = -0.67

Part B: Build Regression Tree

• Fit regression tree using features (likes popcorn, age, favorite color)
• Predict residuals calculated in Part A
• Create terminal regions: R sub 1,1 and R sub 2,1
• Tree splits based on "likes popcorn" feature

Part C: Calculate Output Values

• Compute gamma sub J,M for each leaf
• Minimize loss function for samples in each leaf
• Use second-order Taylor polynomial approximation
• Derivative approach:
  • Take derivative of approximated loss function
  • Set equal to zero, solve for gamma
  • Result: gamma = residual / (P × (1-P))
• For leaf R sub 1,1: gamma = 1.5
• For leaf R sub 2,1:
  • Sum of residuals / sum of P×(1-P) for samples in leaf
  • gamma = -0.77

Part D: Make New Predictions

• F sub 1 of X = F sub 0 of X + learning_rate × gamma values
• Learning rate ν = 0.8
• New predictions:
  • Sample 1: 1.89 (better prediction)
  • Sample 2: 0.07 (worse than before)
  • Sample 3: 0.07 (better than before)

Iteration Process

• Set M = 2, repeat steps A-D
• Calculate new residuals using F sub 1 of X predictions
• Build new regression tree
• Calculate new output values
• Make F sub 2 of X predictions
• In practice: M = 100 or more iterations

Step 3: Final Output

• Assuming Big M = 2, F sub 2 of X is final output
• Making predictions on new data:
  • Calculate predicted log odds using F sub 2 of X
  • Example result: 3.4 log odds
  • Convert to probability: 0.97
  • Apply threshold (0.5): since 0.97 > 0.5, person loves Troll 2

Algorithm Completion

• Successfully implemented gradient boost for classification
• Covered both regression and classification applications
• Complex mathematical derivations simplified through step-by-step approach