Bootstrap options

The parameter affects the following important aspects of choosing a split for a tree when building the tree structure:

Regularization

To prevent overfitting, the weight of each training example is varied over steps of choosing different splits (not over scoring different candidates for one split) or different trees.
Speeding up

When building a new tree, CatBoost calculates a score for each of the numerous split candidates. The computation complexity of this procedure is $\text{[math]}$ , where:
- $\text{[math]}$ is the number of numerical features, each providing many split candidates.
- $\text{[math]}$ is the number of examples.
Usually, this computation dominates over all other steps of each CatBoost iteration (see Table 1 in the paper). Hence, it seems appealing to speed up this procedure by using only a part of examples for scoring all the split candidates.

Depending on the value of the parameter, these ideas are implemented as described in the table below.


Bootstrap type	Description	Associated parameters
Bayesian	The weight of an example is set to the following value: $\text{[math]}$ $\text{[math]}$ is defined by the bootstrap_type parameter $\text{[math]}$ , where $\text{[math]}$ is independently generated from Uniform[0,1] . This is equivalent to generating values $\text{[math]}$ for all the examples according to the Bayesian bootstrap procedure (see D. Rubin “The Bayesian Bootstrap”, 1981, Section 2). Note. The Bayesian bootstrap serves only for the regularization, not for speeding up.	bagging_temperature Command-line version: --bagging-temperature Defines the settings of the Bayesian bootstrap. It is used by default in classification and regression modes. Use the Bayesian bootstrap to assign random weights to objects. The weights are sampled from exponential distribution if the value of this parameter is set to “1”. All weights are equal to 1 if the value of this parameter is set to “0”. Possible values are in the range $\text{[math]}$ . The higher the value the more aggressive the bagging is. This parameter can be used if the selected bootstrap type is Bayesian. sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
Bernoulli	Corresponds to Stochastic Gradient Boosting (SGB, refer to the paper for details). Each example is independently sampled for choosing the current split with the probability defined by the subsample parameter. All the sampled examples have equal weights. Though SGB was originally proposed for regularization, it speeds up calculations almost $\text{[math]}$ times.	subsample Command-line version: --bagging-temperature Sample rate for bagging. This parameter can be used if one of the following bootstrap types is selected: Poisson Bernoulli sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
MVS (supported only on CPU)	Implements the importance sampling algorithm called Minimum Variance Sampling (MVS). Scoring of a split candidate is based on estimating of the expected gradient in each leaf (provided by this candidate), where the gradient $\text{[math]}$ for the example $\text{[math]}$ is calculated as follows: $\text{[math]}$ , where $\text{[math]}$ is the loss function $\text{[math]}$ is the target of the example $\text{[math]}$ $\text{[math]}$ is the current model prediction for the example $\text{[math]}$ (see the Algorithm 2 in the paper ). For this estimation, MVS samples the mvs_head_fraction examples $\text{[math]}$ with the highest values of $\text{[math]}$ with probability $\text{[math]}$ and samples each other example $\text{[math]}$ with probability $\text{[math]}$ , where $\text{[math]}$ is the minimum of $\text{[math]}$ among top-mvs_head_fraction examples. Then, the unbiased estimate of the expected gradient is calculated as follows: $\text{[math]}$ $\text{[math]}$ is the number of examples in the leaf. Theoretical basis This algorithm provides the minimum variance for a given expected number of sampled examples: $\text{[math]}$ . If $\text{[math]}$ is equal to 1, this statement coincides with the case of Proposition 3.1 described in the paper, where $\text{[math]}$ (regularization is absent), the parameter vector $\text{[math]}$ is scalar (a value in the leaf under consideration) and $\text{[math]}$ , and the gradients are taken at $\text{[math]}$ : $\text{[math]}$ Noteworthy, according to this statement, though examples are sampled once for all candidates for the current split, this sampling provides minimal variance of estimation for each leaf with some leaf-specific value of $\text{[math]}$ . MVS can be considered as an improved version of the Gradient-based One-Side Sampling (GOSS, see details in the paper) implemented in LightGBM, which samples a given number of top examples by values $\text{[math]}$ with the probability 1 and samples other examples with the same fixed probability. Due to the theoretical basis, MVS provides a lower variance of the estimate $\text{[math]}$ than GOSS. Note. MVS may not be the best choice for regularization, since sampled examples and their weights are similar for close iterations.	mvs_head_fraction Command-line version: --mvs-head-fraction Controls the fraction of the highest by absolute value gradients taken for the minimal variance sampling. Possible values are in the range $\text{[math]}$ . This parameter can be used if the selected bootstrap type is MVS. sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
Poisson (refer to the paper for details; supported only on GPU)	The weights of examples are i.i.d. sampled from the Poisson distribution with the parameter $\text{[math]}$ providing the expected number of examples with positive weights equal to the subsample parameter . If subsample is equal to 0.66, this approximates the classical bootstrap (sampling $\text{[math]}$ examples with repetitions).	subsample Command-line version: --bagging-temperature Sample rate for bagging. This parameter can be used if one of the following bootstrap types is selected: Poisson Bernoulli sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
No	All training examples are used with equal weights.	sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .


Bootstrap type	Description	Associated parameters
Bayesian	The weight of an example is set to the following value: $\text{[math]}$ $\text{[math]}$ is defined by the bootstrap_type parameter $\text{[math]}$ , where $\text{[math]}$ is independently generated from Uniform[0,1] . This is equivalent to generating values $\text{[math]}$ for all the examples according to the Bayesian bootstrap procedure (see D. Rubin “The Bayesian Bootstrap”, 1981, Section 2). Note. The Bayesian bootstrap serves only for the regularization, not for speeding up.	bagging_temperature Command-line version: --bagging-temperature Defines the settings of the Bayesian bootstrap. It is used by default in classification and regression modes. Use the Bayesian bootstrap to assign random weights to objects. The weights are sampled from exponential distribution if the value of this parameter is set to “1”. All weights are equal to 1 if the value of this parameter is set to “0”. Possible values are in the range $\text{[math]}$ . The higher the value the more aggressive the bagging is. This parameter can be used if the selected bootstrap type is Bayesian. sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
Bernoulli	Corresponds to Stochastic Gradient Boosting (SGB, refer to the paper for details). Each example is independently sampled for choosing the current split with the probability defined by the subsample parameter. All the sampled examples have equal weights. Though SGB was originally proposed for regularization, it speeds up calculations almost $\text{[math]}$ times.	subsample Command-line version: --bagging-temperature Sample rate for bagging. This parameter can be used if one of the following bootstrap types is selected: Poisson Bernoulli sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
MVS (supported only on CPU)	Implements the importance sampling algorithm called Minimum Variance Sampling (MVS). Scoring of a split candidate is based on estimating of the expected gradient in each leaf (provided by this candidate), where the gradient $\text{[math]}$ for the example $\text{[math]}$ is calculated as follows: $\text{[math]}$ , where $\text{[math]}$ is the loss function $\text{[math]}$ is the target of the example $\text{[math]}$ $\text{[math]}$ is the current model prediction for the example $\text{[math]}$ (see the Algorithm 2 in the paper ). For this estimation, MVS samples the mvs_head_fraction examples $\text{[math]}$ with the highest values of $\text{[math]}$ with probability $\text{[math]}$ and samples each other example $\text{[math]}$ with probability $\text{[math]}$ , where $\text{[math]}$ is the minimum of $\text{[math]}$ among top-mvs_head_fraction examples. Then, the unbiased estimate of the expected gradient is calculated as follows: $\text{[math]}$ $\text{[math]}$ is the number of examples in the leaf. Theoretical basis This algorithm provides the minimum variance for a given expected number of sampled examples: $\text{[math]}$ . If $\text{[math]}$ is equal to 1, this statement coincides with the case of Proposition 3.1 described in the paper, where $\text{[math]}$ (regularization is absent), the parameter vector $\text{[math]}$ is scalar (a value in the leaf under consideration) and $\text{[math]}$ , and the gradients are taken at $\text{[math]}$ : $\text{[math]}$ Noteworthy, according to this statement, though examples are sampled once for all candidates for the current split, this sampling provides minimal variance of estimation for each leaf with some leaf-specific value of $\text{[math]}$ . MVS can be considered as an improved version of the Gradient-based One-Side Sampling (GOSS, see details in the paper) implemented in LightGBM, which samples a given number of top examples by values $\text{[math]}$ with the probability 1 and samples other examples with the same fixed probability. Due to the theoretical basis, MVS provides a lower variance of the estimate $\text{[math]}$ than GOSS. Note. MVS may not be the best choice for regularization, since sampled examples and their weights are similar for close iterations.	mvs_head_fraction Command-line version: --mvs-head-fraction Controls the fraction of the highest by absolute value gradients taken for the minimal variance sampling. Possible values are in the range $\text{[math]}$ . This parameter can be used if the selected bootstrap type is MVS. sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
Poisson (refer to the paper for details; supported only on GPU)	The weights of examples are i.i.d. sampled from the Poisson distribution with the parameter $\text{[math]}$ providing the expected number of examples with positive weights equal to the subsample parameter . If subsample is equal to 0.66, this approximates the classical bootstrap (sampling $\text{[math]}$ examples with repetitions).	subsample Command-line version: --bagging-temperature Sample rate for bagging. This parameter can be used if one of the following bootstrap types is selected: Poisson Bernoulli sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .
No	All training examples are used with equal weights.	sampling_unit Command-line version: --sampling-unit The sampling scheme. Possible values: Object — The weight $\text{[math]}$ of the i-th object $\text{[math]}$ is used for sampling the corresponding object. Group — The weight $\text{[math]}$ of the group $\text{[math]}$ is used for sampling each object $\text{[math]}$ from the group $\text{[math]}$ .

The frequency of resampling and reweighting is defined by the sampling_frequency parameter:

PerTree — Before constructing each new tree
PerTreeLevel — Before choosing each new split of a tree

Tip.

It is recommended to use MVS when speeding up is an important issue and regularization is not. It is usually the case when operating large data. For regularization, other options might be more appropriate.

Bootstrap options

Related papers