39 Bootstrapping ensembles

Bootstrapping ensembles repeatedly resample the training set, train a separate model on each sample, and average their predictions. This can reduce variance.

Bootstrap for Estimating Epistemic Uncertainty

Predictive uncertainty can be written as a sum of aleatoric and epistemic uncertainty :

$$\begin{array}{rl}y-\hat{f}(x;S)& =y-{\hat{f}}_{\hat{\theta }}(x)\\ & =\underset{\text{Aleatoric uncertainty}}{\underbrace{y-f_{{\theta }^{\ast }}(x)}}+\underset{\text{Epistemic uncertainty}}{\underbrace{f_{{\theta }^{\ast }}(x)-f_{\hat{\theta }}(x)}}\end{array}$$

where ${\theta }^{\ast }$ are the true parameters of the function we try to learn : Hard to disentangle the two uncertainties of different nature :

• We directly observe the predictive uncertainty $y-\hat{f}(x;S)$
• But ${\theta }^{\ast }$ is unknown.

Epistemic Uncertainty

• The epistemic uncertainty is :

$$\text{Epistemic}(x)=f_{{\theta }^{\ast }}(x)-\hat{f}(x)$$

Note Epistemic(x) is a random function of the random sample S. Thus Epistemic(x) is itself a random variable

• Goal : Estimate the distribution $Epistemic(x)$
• Assumption : Our model is unbiased (i.e. we need to assume its Bias is zero).

$${\mathbb{E}}_S[{\hat{f}}_{\theta }(x)]=f_{{\theta }^{\ast }}(x)$$

• But $S\sim \underset{\text{i.i.d.}}{\mathcal{D}}$ but $\mathcal{D}$ is an unknown distribution.

What if we know $\mathcal{D}$ ?

• we could take $k$ (a very large number of) samples of size $n$, each i.i.d. from $\mathcal{D}$, train the model on each.
• Then ${\left\{f_{\hat{\theta }}^{(i)}(x)-f_{{\theta }^{\ast }}(x)\right\}}_{i=1}^k$ are i.i.d. samples from $Epistemic(x)$.
• By our unbiasedness assumptions :

$$f_{{\theta }^{\ast }}(x)={\mathbb{E}}_S\left[{\hat{f}}_{\theta }(x)\right]\approx \frac{1}{k}\sum _{i=1}^k{f}_{\hat{\theta }}^{(i)}(x)=\hat{\mu }(x)$$

• ${\left\{f_{\hat{\theta }}^{(i)}(x)-\hat{\mu }(x)\right\}}_{i=1}^k$ are approximately i.i.d samples from $Epistemic(x)$.
• Problem : We don’t have access to unlimited number samples from $\mathcal{D}$, but only have a single sample, $S$.

Bootstrap

• Idea : Given samples $x_1,\dots ,x_n\sim \mathcal{D}$, we can approximate the unknown probability distribution $\mathcal{D}$ by (here, $\delta (x-x_i)$, denotes a Dirac delta centred on $x_i$):

$$\begin{array}{rl}P(x)& =\mathrm{Pr}(X=x)\\ & \approx \frac{1}{n}\sum _{i=1}^n\delta (x-x_i)\\ & =\hat{P}(x)\end{array}$$

• This can be made to work for continuous distributions using the probability density function :

$$\begin{array}{rl}p(x)& \approx \hat{p}(x)\\ & =\frac{1}{n}\sum _{i=1}^n\delta (x-x_i)\\ & =\hat{p}(x)\end{array}$$

• Now use this in place of the unknown $\mathcal{D}$.

Practical Algorithm of Estimating Epistemic Uncertainty

Algorithm Bootstrap (sample $S=\{(x_i,y_i){\}}_{i=1}^n$)

• Define empirical distribution :

$$p(x)=\frac{1}{n}\sum _{i=1}^n\delta (x-x_i)$$

• Generate $k$ bootstrap datasets $S_1,\dots ,S_k\sim \hat{P}$.
• Train models on each dataset : ${\hat{f}}^{(i)}=\text{train}(S_i)$
• Return epistemic uncertainty estimate :

$$U(x)={\left\{{\hat{f}}^{(i)}(x)-\hat{\mu }(x)\right\}}_{i=1}^k$$

where $\hat{\mu }(x)=\frac{1}{k}{\sum }_{i=1}^k{\hat{f}}^{(i)}(x)$