AI summary by TwinMind
XGBoost Part 3 (of 4): Mathematical Details
StatQuest with Josh Starmer
27m 24s
Prerequisites and Introduction
- Assumes knowledge of XGBoost tree building (parts 1 & 2)
- Assumes knowledge of gradient boost details
- Assumes familiarity with Ridge regression
- Focus: derive equations for similarity scores and output values
- Key insight: only difference between regression/classification is loss function
Dataset Setup
- Regression: drug dosage (x-axis) → drug effectiveness (y-axis)
- Classification: drug dosage (x-axis) → probability drug will be effective
- Both start with initial prediction = 0.5
- Residuals show prediction quality
Loss Functions
Regression Loss Function
- Formula: 1/2 × (y_i - P_i)²
- y_i = observed y-axis value
- P_i = prediction corresponding to observation
- Example calculation with initial prediction 0.5 = 104.4
Classification Loss Function
- Formula: negative log likelihood
- y_i = observed value (0 or 1)
- P_i = predicted probability (0 to 1)
Core XGBoost Optimization Equation
- Minimize: Loss Function + Regularization Term
- Regularization: 1/2 × λ × (output value)²
- Similar to Ridge regression
- Omits gamma×T term (pruning penalty) as it doesn't affect output values/similarity scores
- Replace P_i with P_0 + output value from new tree
Finding Optimal Output Value
Without Regularization (λ = 0)
- Test different output values: 0, -1, +1
- Output = 0: loss = 104.4
- Output = -1: loss = 109.4 (worse)
- Output = +1: loss = 102.4 (best so far)
- Optimal at bottom of parabola where derivative = 0
With Regularization
- λ = 4: optimal value shifts closer to 0
- λ = 40: optimal value shifts even closer to 0
- Higher λ → more shrinkage toward 0
Taylor Approximation Method
- XGBoost uses second-order Taylor approximation for both regression/classification
- Regular gradient boost used different methods for each
- Taylor approximation components:
- Loss function for previous prediction
- First derivative (gradient) G_i
- Second derivative (hessian) H_i
- Constant terms omitted from optimization
Deriving Optimal Output Value Formula
- Take derivative with respect to output value
- Set derivative = 0
- Solve for output value
- Final formula: -Σ(G_i) / (Σ(H_i) + λ)
Regression-Specific Formulas
Loss Function Derivatives
- First derivative G_i = -(y_i - P_i) = negative residual
- Second derivative H_i = 1
Output Value Formula
- Numerator: sum of residuals (negatives cancel)
- Denominator: number of residuals + λ
Similarity Score Formula
- (sum of residuals)² / (number of residuals + λ)
Classification-Specific Formulas
Loss Function Derivatives
- First derivative G_i = negative residual
- Second derivative H_i = P_i × (1 - P_i)
Output Value Formula
- Numerator: sum of residuals
- Denominator: Σ(P_i × (1 - P_i)) + λ
Similarity Score Formula
- (sum of residuals)² / (Σ(P_i × (1 - P_i)) + λ)
Similarity Score Derivation
- Start with simplified equation × (-1) to flip parabola
- Optimal output value = x-coordinate of highest point
- Y-coordinate = similarity score
- Original manuscript uses 1/2 factor
- Implementations omit 1/2 (relative measure, scaling doesn't matter)
- Plug in optimal output value solution
- Algebraic manipulation yields final similarity score formula
Cover Definition
- Cover = denominator of similarity score - λ
- Cover = sum of Hessians (H_i)
- Regression: cover = number of residuals (since H_i = 1)
- Classification: cover = Σ(P_i × (1 - P_i))
- Related to minimum residuals required in leaf
Summary Process
- Minimize loss function + regularization term
- Solve for optimal output value using derivatives
- Use output value in similarity score equation
- Configure formulas by plugging in loss function derivatives
- Different G_i and H_i for regression vs classification
