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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome