# Gradient boosting (optional unit)

In regression problems, it makes sense to define the signed error as the
difference between the prediction and the label. However, in other types of
problems this strategy often leads to poor results. A better strategy used in
gradient boosting is to:

- Define a loss function similar to the loss functions used in neural networks. For example, the entropy (also known as log loss) for a classification problem.
- Train the weak model to predict the *gradient of the loss according to the
  strong model output*.

Formally, given a loss function $L(y,p)$ where $y$ is a label and $p$ a
prediction, the pseudo response $z_i$ used to train the weak model
at step $i$ is:
$$ z_i = \\frac {\\partial L(y, F_i)} {\\partial F_i} $$

where:

- $F_i$ is the prediction of the strong model.

The preceding example was a regression problem: The objective is to predict a
numerical value. In the case of regression, squared error is a common loss
function:
$$ L(y,p) = (y - p)\^2 $$

In this case, the gradient is:
$$ z = \\frac {\\partial L(y, F_i)} {\\partial F_i} = \\frac {\\partial(y-p)\^2} {\\partial p} = -2(y - p) = 2 \\ \\text{signed error} $$

In order words, the gradient is the signed error from our example with a factor
of 2. Note that constant factors do not matter because of the shrinkage. Note
that this equivalence is only true for regression problems with squared error
loss. For other supervised learning problems (for example, classification,
ranking, regression with percentile loss), there is no equivalence between the
gradient and a signed error.

## Leaf and structure optimization with Newton's method step

Newton's method is an optimization method like gradient descent. However, unlike
the gradient descent that only uses the gradient of the function to optimize,
Newton's method uses both the gradient (first derivative) and the second
derivative of the function for optimization.

A step of gradient descent is as follows:
$$ x_{i+1} = x_i - \\frac {df}{dx}(x_i) = x_i - f'(x_i) $$

and Newton's method as as follows:
$$ x_{i+1} = x_i - \\frac {\\frac {df}{dx} (x_i)} {\\frac {d\^2f}{d\^2x} (x_i)} = x_i - \\frac{f'(x_i)}{f''(x_i)}$$

Optionally, Newton's method can be integrated to the training of gradient
boosted trees in two ways:

1. Once a tree is trained, a step of Newton is applied on each leaf and overrides its value. The tree structure is untouched; only the leaf values change.
2. During the growth of a tree, conditions are selected according to a score that includes a component of the Newton formula. The structure of the tree is impacted.

YDF Code In YDF:

- YDF always applies a Newton step on the leaf (option 1).
- You can enable option 2 with `use_hessian_gain=True`.