0
$\begingroup$

enter image description here

Above is the pseudocode for gradient boosting. In Step 2.3, we're computing a multiplier (or step length) $\gamma_m$. Suppose the loss function $L(y_i, \hat{y}_i) = \frac{1}{2}(y_i - \hat{y}_i)^2$. Then to find $\gamma_m$, we would have

$\begin{align*} \gamma_m &= \text{arg min}_\gamma \frac{1}{2}\sum_{i = 1}^n (y_i - F_{m-1}(x_i) - \gamma h_m(x_i))^2 \end{align*}$

Taking the derivative wrt $\gamma$, we have

\begin{align*} \frac{\partial}{\partial \gamma} \frac{1}{2}\sum_{i = 1}^n (y_i - F_{m-1}(x_i) - \gamma h_m(x_i))^2 &= -\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i) - \gamma h_m(x_i))\\ &= -\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i) + \gamma \sum_{i=1}^n h_m^2(x_i)\\ & \overset{set}{=}0\\ \Rightarrow \gamma_m &= \frac{\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i))}{\sum_{i=1}^n h_m(x_i)^2} \end{align*}

Is this correct? If so, what's the intuition behind this step length $\gamma$? In my own implementation of this algorithm, I've been computing $\gamma_m = \frac{\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i))}{\sum_{i=1}^n h_m(x_i)^2}$ and the values of $\gamma_m$ are all very close to 1. What does that suggest about my algorithm?

$\endgroup$
2
  • $\begingroup$ This is too hand-wavey to be a rigorous answer, but I believe $\gamma_i$ are the multipliers for the weight of each weak learner (which corresponds to a "step size" parameter as you specified). Your optimum $\gamma$ calculation seems correct, though I haven't seen that particular expression before. Intuitively, as the loss of the previous learner $F_{m-1}(x_i)$ decreases, so does $\gamma$, and vice versa; your $\gamma$ expression satisfies this. The fact that $\gamma \approxeq 1$ in your empirical case might suggest lack of shrinkage -- is the model learning? $\endgroup$ – tchainzzz Jun 19 '20 at 22:45
  • $\begingroup$ @tchainzzz Thank you for your comment. Can you please explain to me why $\gamma \approx 1$ suggests that the model is not learning? $\endgroup$ – Adrian Jun 20 '20 at 2:41
1
+50
$\begingroup$

Boosting can be seen as gradient descent performed in function space $\mathcal{H}$ of weak learners (see e.g. [1, 2]). From the point of view of empirical risk minimization, at time step $m$ we would like to take a step in the negative gradient direction $-\nabla_{F_{m-1}} L(y, F_{m-1})$, whose coordinate projection on the observed dataset equals to the vector of pseudo residuals $(r_{1m}, \dots, r_{nm})^{\mathsf{T}}$ defined in the question. Since the set of weak learners $\mathcal{H}$ does not necessarily contain a function $h$ such that $h(x_{i}) = r_{im}$, it is a job of the weak learning algorithm to select a function $h_{m} \in \mathcal{H}$ which best correlates (in some way) with the negative gradient direction given by the vector of pseudo residuals. For more details on the specific case of quadratic loss see [3].

Once we think of $h_{m}$ as an approximation to the negative gradient direction, choosing the step size $\gamma_{m}$, as defined in the question, is known as line-search in optimization literature. In words, it simply selects a step-size that yields a maximum decrease of the empirical (i.e., training) loss function. Hence, in your case, $\gamma \approx 1$ suggests that a model can fit the data further (that is, taking a gradient descent step is able to further minimize the training loss). Once $\gamma$ reaches $0$, a local minimum or a saddle point has been reached and the optimization procedure (i.e., empirical risk minimization) stops.

Note that other step size schemes are also possible (e.g., a constant step size $\gamma_{m} = \gamma_{0}$, a decreasing step sizes scheme $\gamma_{m} = \gamma_{0}/\sqrt{m}$, etc.). Different step size schemes can provide the same guarantees on the training loss (e.g., ensure convergence to a local minimum of the training loss) that hold under different assumptions of the empirical training loss and/or the weak learning algorithm. However, modifying the step size scheme can affect the generalization properties of the algorithm in ways that to the best of my knowledge are not yet fully understood.

[1] Mason et. al. Boosting Algorithms as Gradient Descent. NIPS 1999.

[2] Friedman. Greedy Function Approximation: a Graident Boosting Machine. Ann. Statist. 2001.

[3] Buhlmann and Yu. Boosting with the $L_{2}$-Loss: Regression and Classification.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.