### 1. Implement Bagging on the data generating model of Example 2.8 (use the file Example2.8_Bootstrap.html): (1) set parameter sigma=0.5, N=50; (2) build and visualize one tree model (you can use any software package) on one data sample; (3) manually generate 1000 bootstrap samples and build a bagging model, visualize the resulted prediction on test data, and measure the MSE, Bias, and Variance.

#### Using the data generating model of Example 2.8, as well as creating out of sample data, we have the following code.

#Data generating model
set.seed(135790)
# static parameters
x.min <- -1
x.max <- 1
sigma <- 0.5
# function for generating data
data.gen <- function(N=2) {
x <- runif(n=N, min=x.min, max=x.max)
f.x <- sin(pi * x)
epsilon <- rnorm(n=N, mean=0, sd=sigma)
y <- f.x + epsilon
return(data.frame(x=x, y=y))
}

#Out of Sample data
M <- 10000
x.out <- sort(runif(n=M, min=x.min, max=x.max))  # order the data points by x for easy plots
f.x.out <- sin(pi * x.out)
y.out <- f.x.out + rnorm(n=M, mean=0, sd=sigma)
x.test=data.frame(x=x.out)

#### Generating one data sample size N=50, sigma = 0.5

N=50;
data0 = data.gen(N=N);

#### Build one tree using ‘tree’ library.

#Buiding a tree
tree1 <- tree(y ~ x, data=data0)
summary(tree1)
##
## Regression tree:
## tree(formula = y ~ x, data = data0)
## Number of terminal nodes:  5
## Residual mean deviance:  0.2014 = 9.064 / 45
## Distribution of residuals:
##     Min.  1st Qu.   Median     Mean  3rd Qu.     Max.
## -0.91150 -0.26760 -0.03412  0.00000  0.25330  1.20400

#### and plot decision tree…

# plot the fitted tree
plot(tree1)
text(tree1)

#### Plot the partitions

# plot the partition
plot(data0$x, data0$y)
x <- data0$x[order(data0$x)]
f.x <- sin(pi * x)
lines(x, f.x, lwd=2)
partition.tree(tree1, lwd=2, col="red", add=T)

### bootstrapping

#### function for generating Bootstrap data sample

data.bootstrap <- function(data) {
index <- sample(N, N, replace=TRUE)
return(data[index, ])
}

#### generating 1000 trees and getting the predictions

RUN=1000;
predictions = matrix(rep(0,RUN*M),nrow = RUN, ncol=M)
#generate 1000 bootstrap samples and getting predictions
for (run in 1:RUN) {
data <- data.bootstrap(data = data0);
treeBS = tree(y~x,data=data);
predictions[run,] = predict(treeBS,x.test);
}
y.test = colMeans(predictions)

#### visualizing the non-random forest

test = data.frame(x=x.test, y=y.test)
plot(test$x, test$y);
lines(x.out, f.x.out, lwd=2);

#### Measuring MSE, Bias, and Variance

g_D_x <- predictions;
g_bar_x <-colMeans(g_D_x)

bias = mean((g_bar_x-f.x.out)^2);
var = mean((t(g_D_x)-g_bar_x)^2);
MSE = mean((t(g_D_x)-y.out)^2);

The final numbers are as follows.

Bias Variance MSE
0.0676821 0.0616438 0.3769345

### 2. Show that as the number of bootstrap samples B gets large, the OOB error estimate for a random forest approaches its LOOCV error estimate, and that in the limit, the identity is exact.

We first prove that each bootstrap sample takes about $$2/3$$ of the original sample.

The probability of an observation $$(x_i,y_i)$$ not being selected from selecting from sample of size $$N$$ is $$(1-\frac{1}{N})$$. For a bootstrap sample of size $$N$$, the probability of not selecting $$(x_i,y_i)$$ is $$(1-\frac{1}{N})^N\rightarrow\frac{1}{e}\approx\frac{1}{3}$$ as $$N\rightarrow\infty$$. Hence, each bootstrap sample takes about $$1-\frac{1}{3}=\frac{2}{3}$$ of the observations.

Let $$X$$ be a sample of size $$N$$. Let $$X_t$$ be a sample drawn with repetition from $$X$$, used to build tree $$t$$, then $$X_t$$ is a bootstrap sample of $$X$$ for tree $$t$$. Let $$O_t = X \setminus X_t$$ be the set of out-of-bag elements of tree $$t$$. Then we have

\begin{align*} \text{OOB Error}&=\frac{\sum\limits_{t=1}^{B}\sum\limits_{i=1}^{|O_t|} Error(y_i,f_t(x_i))}{\sum\limits_{t=1}^{B}|O_t|} \end{align*}

To compute the LOOCV, we partition $$X$$ into $$N$$ partitions $$X=\{X_1,X_2,\dots,X_N\}$$, $$X_i\cap X_j=\phi$$, $$|X_i|=1$$ since the sample size is $$N$$. Let $$S_t=X\setminus{X_t}$$ be the sample used for creating the random forest $$t$$. Then we have

\begin{align*} \text{LOOCV error}=\frac{\sum\limits_{t=1}^{N}Error(y_t,f_{S_t}(x_t))}{N} \end{align*} We also proof that with probability 1 each element is selected in at least one of the bootstrap samples. The probability of an observation $$(x_i,y_i)$$ not being selected for a particular bootstrap sample is $$(1-\frac{1}{N})^N$$. Hence, for $$B$$ number of bootstrap samples, the probability of $$(x_i,y_i)$$ not being selected at all is $$(1-\frac{1}{N})^{NB}\rightarrow0$$ as $$B\rightarrow\infty$$. Now we are ready to show the convergence of the OOB Error. \begin{align*} \lim_{B\rightarrow\infty}\text{OOB Error}&=\frac{\lim_{B\rightarrow\infty}\sum\limits_{t=1}^{B}\sum\limits_{i=1}^{|O_t|} Error(y_i,f_t(x_i))}{\lim_{B\rightarrow\infty}\sum\limits_{t=1}^{B}|O_t|}\\ &=\frac{\frac{1}{3}\sum\limits_{i=1}^{N} Error(y_i,f_t(x_i))}{\frac{1}{3}N}\\ &=\frac{\sum\limits_{i=1}^{N} Error(y_i,f_t(x_i))}{N} \end{align*}