$4.$ Ensemble Methods

In this question, you will implement several ensemble methods including Bagging and AdaBoost on a simple dataset. The methods will learn a binary classification of $2$ D datapoints in $\backslash ([-1,1]^\{2\}\backslash ).$

$($a$)$ Weak learner

To begin with, you will implement a weak learner to do the binary classification.

A decision stump is a one$-$level decision tree. It looks at a single feature, and then makes a classification by thresholding on this feature. Given a dataset with positive weights assigned to each datapoint, we can find a stump that minimizes the weighted error:

$\backslash [$

L$=\backslash$sum$\_\{$i$=1\}^\{$n$\}$ w$^\{($i$)\}\backslash$cdot $\backslash$mathbf$\{1\}\backslash$left$($y$^\{($i$)\}$

eq $\backslash$widehat$\{$y$\}^\{($i$)\}\backslash$right$)$

$\backslash ]$

Here $\backslash ($ w$^\{($i$)\}\backslash )$ is the weight of the $\backslash ($ i $\backslash )-$th datapoint, and the prediction $\backslash (\backslash$widehat$\{$y$\}^\{($i$)\}\backslash )$ is given by thresholding on the $\backslash ($ k $\backslash )-$th feature of datapoint $\backslash (\backslash$boldsymbol$\{$x$\}^\{($i$)\}\backslash )$ :

$\backslash [$

$\backslash$widehat$\{$y$\}^\{($i$)\}=\backslash$left$\backslash \{\backslash$begin$\{$array$\}\{$ll$\}$

s$,$ & $\backslash$text $\{$ if $\}$ x$\_\{$k$\}^\{($i$)\}\backslash$geq t $\backslash \backslash$

$-$s$,$ & $\backslash$text $\{$ otherwise $\}$

$\backslash$end$\{$array$\}\backslash$right$.$

$\backslash ]$

For the $2$D dataset we have, the parameters of this stumps are the sign $\backslash ($ s $\backslash$in$\backslash \{+1,-1\backslash \}\backslash ),$ the feature dimension $\backslash ($ k $\backslash$in$\backslash \{1,2\backslash \}\backslash ),$ and the threshold $\backslash ($ t $\backslash$in$[-1,1]\backslash ).$ In this question, your task is to find out the best stump given the dataset and weights.

Learning a decision stump requires learning a threshold in each dimension and then picking the best one. To learn a threshold in a dimension, you may simply sort the data in the chosen dimension, and calculate the loss on each candidate threshold. Candidates are midpoints between one point and the next, as well as the boundaries of our range of inputs.

Please implement the Stump class in hw$5.$py$.$ You may define your own functions inside the class, but do not change the interfaces of $\_\_$init$\_\_()$ and predict$().$ Please read template file for further instructions.

$($b$)$ Weak learner's predictions

Now test your implementation of Stump on the dataset given by get$\_$dataset$\_$fixed$().$ Suppose all the datapoints are equally weighted. Please answer the following questions in your written submission:

$-$ What is your decision function?

$-$ How many datapoints are mis$-$classified?

$-$ Using the helper function visualization$(),$ include a visualization of your stump's predictions.

$($c$)$ Bagging

As we have learned from the class, we can utilize ensemble methods to create a strong learner from weak learners we have for part $($a$).$ Please complete bagging$()$ in hw$5.$py$.$ This function should take the whole dataset as input, and sample a subset from it in each step, to build a list of different weak learners.

Please do not change the random sampling of sample$\_$indices, and use the default random seed$=0,$ so that your code can behave consistently in the autograder.

class Stump$()$:

# gettingdata and changing their type from tuple to array

def $\_\_$init$\_\_($self$,$ data, labels, weights$=$None$)$:

$\text{'}\text{'}\text{'}$

Initializes a stump $($one$-$level decision tree$)$ which minimizes

a weighted error function of the input dataset.

In this function, you will need to learn a stump using the weighted

datapoints. Each datapoint has $2$ features, whose values are bounded in

$[-1\mathrm{.}0,1\mathrm{.}0].$ Each datapoint has a label in $\{+1,-1\},$ and its importance

is weightedby a positive value.

The stump will choose one of the features, and pick the best threshold

in that dimension, so that the weighted error is minimized.

Arguments:

data: An ndarray with shape $($n$,2).$ Values in $[-1\mathrm{.}0,1\mathrm{.}0].$

labels: An ndarray with shape $($n$,).$ Values are $+1$ or $-1.$

weights: An ndarray with shape $($n$,).$ The weights of each

datapoint, all positive.

$\text{'}\text{'}\text{'}$

# You may choose to use the following variables as a start

# The feature dimension which the stump will decide on

# Either $0$ or $1,$ since the datapoints are $2$D

self.dimension $=0$

# The threshold in that dimension

# May be midpoints between datapoints or the boundaries $-1\mathrm{.}0,1\mathrm{.}0$

self.threshold $=-1\mathrm{.}0$

# The predicted sign when the datapoint's feature in that dimension

# is greater than the threshold

# Either $+1$ or $-1$

self.sign $=1$

pass

def predict$($self$,$ data$)$:

$\text{'}\text{'}\text{'}$

Arguments:

data: An ndarray with shape $($n$,2).$ Values in $[-1\mathrm{.}0,1\mathrm{.}0].$

Returns:

prediction: An ndarray with shape $($n$,).$ Values are $+1$ or $-1.$

$\text{'}\text{'}\text{'}$

pass

def bagging$($data$,$ labels, n$\_$classifiers, n$\_$samples, seed$=0)$:

$\text{'}\text{'}\text{'}$

Arguments:

data: An ndarray with shape $($n$,2).$ Values in $[-1\mathrm{.}0,1\mathrm{.}0].$

labels: An ndarray with shape $($n$,).$ Values are $+1$ or $-1.$

n$\_$classifiers: Number of classifiers to construct.

n$\_$samples: Number of samples to train each classifier.

seed: Random seed for NumPy.

Returns:

classifiers: A list of classifiers.

$\text{'}\text{'}\text{'}$

classifiers $=[]$

n $=$ data.shape$[0]$

for i in range$($n$\_$classifiers$)$:

np$.$random.seed$($seed $+$ i$)$

sample$\_$indices $=$ np$.$random.choice$($n$,$ size$=$n$\_$samples, replace$=$False$)$

# complete the rest of the loop

pass

def adaboost$($data$,$ labels, n$\_$classifiers$)$:

$\text{'}\text{'}\text{'}$

Arguments:

data: An ndarray with shape $($n$,2).$ Values in $[-1\mathrm{.}0,1\mathrm{.}0].$

labels: An ndarray with shape $($n$,).$ Values are $+1$ or $-1.$

n$\_$classifiers: Number of classifiers to construct.

Returns:

classifiers: A list of classifiers.

weights: A list of