Chapter 6.3: Cross-validation, boosttrap and tree-based methods - Boosting

Question 1

Recap:

What is PAC(strong) learnability?

What is weak PAC learning?

Which one must imply the other?

Answer 1

The question becomes, can we turn a weak PAC learning algorithm into a strong one

Question 2

What is the difference between Bagging and Boosting?

Answer 2

Bagging is done in parallel, boosting is done sequentially

Question 3

What was Robert Schapire’s rough sketch of how to implement boosting?

Answer 3

• f-hat³ acts as the referee when the other two dont agrees, whatever it says will become what we classify it as due to majority vote.
• in our case they are NOT independent (as we are training the classifier on each point misclassified by the previous)

Question 4

What is the adaptive boosting (AdaBoost) algorithm?

Answer 4

So for each iteration, you minimise the weighted empirical risk, then you assign some sort of contribution factor to that classification function to determine your final weighted classification function

Question 5

What loss function do you use here for AdaBoost?

Answer 5

• weights go up or down based on whether the classifier has the same sign as Y??

** CHECK THIS

Question 6

Is there a closed-form solution

Answer 6

Question 7

What is a decision stump?

Answer 7

decision stump –> decision tree with only one split

Question 8

What are the properties of AdaBoost?

What is the VC dimension of boosting combinations of m weak classifiers?

Answer 8

Question 9

If we can use AdaBoosting in the discrete classification setting, what do we use in the continuous regression setting?

What is the general idea behind this process?

Answer 9

• With Gradient descent

Question 10

What is the idea behind Gradient Boosting?

Answer 10

• Note that for the squared loss function, we know the theoretical risk minimiser is f* = E[Y|X] –> Setting Y equal to the partial derivative essential guarentees we are minimising the risk under the l².
• It is called a pseudo residual as L=(Y-θ)^2 so taking the partial derivative gives dL/dθ = 2(Y-θ) = 2 (f-hat(X)-Y) –> so you are not looking at the residual itse lf but a measure between your Y and your previously fitted function

Question 11

What is the Gradient Boost Algorithm?

Answer 11

• At some point, you are going to risk overfitting if you continue, as you will keep fitting to the residuals, which reduces the bias but increases the variance

Question 12

What are the two ensemble methods we have considered in the course, and what are their focuses?

Answer 12

Bagging can be done in parallel, but boosting must be done sequentially