Q1: The goal is to find the decision boundary (hyperplane) with maximum margin => the optimization problem is to maximize the margin.

Q2: This is the definition of a support vector.

Q3: During training, we compute dot products between pairs of training vectors; during testing – between the testing example and the support vectors. Note that d) can be immediately ruled out as it is a product of a vector and coefficient; dot product is a product of 2 vectors.

Q4: Bagging can be applied to both classification and regression problems. In regression problems, the individual predictions will be averaged (see slide 14 of lecture10b).

Q5: There is no guarantee that an ensemble of classifiers (including Boosting) will produce better accuracy than the single classifier it uses. In practice, ensembles often perform better but there is no guarantee.

Exercise 2. Bagging, Boosting and Random Forest

a) What are the similarities and differences between Bagging and Boosting?

Answer: See the lecture slides (slide 31)

b) What are the 2 main ideas that are combined in Random Forest?

Answer: Bagging and random selection of features

Exercise 3 Boosting

Continue the example from slides 24-25. The current probabilities of the training examples to be used by AdaBoost are given below:

From these, a training set T2 has been created and using T2 a classifier C2 has been generated. Suppose that C2 misclassifies examples x2 and x9 . Show how the probabilities of all training examples are recalculated and normalized.

Solution:

1.   Initial probabilities:

2.   Examples 2 and 9 are misclassified => their errors e are 1, while the errors of the other 8 examples are 0

The weighed error of the classifier C2 will be: 2=0.07*1+0. 17*1=0.24

3.   The term for the probability modification will be: 2=2 /(1- 2)=0.24/0.76=0.32

4.   Calculating the new probabilities by modifying (reducing) only the probabilities of the correctly classified examples by: p(xj)=p(xj)* 2

The new probabilities are:

5.  Normalization:

Sum of all probabilities: 0.022*6+0.054*2+0.07+0. 17=0. 132+0. 108+0.24=0.48

Normalized probabilities:

We can see that the weights of the misclassified examples (x2 and x9) have increased while the weights of the correctly classified examples (the remaining 8 examples) have decreased. In the next iteration x2 and  x9 will have a higher chance to be selected for the new training set, i.e. the next classifier will focus on learning to classify these more difficult examples.

Exercises using Weka

Exercise 4. SVM in Weka – Binary classification

1. Load the diabetes data (diabetes.arff) or another binary classification data. The two classes is the diabetes data are “tested_positive” and “tested_negative” .

Choose 10-fold cross validation. Run the SVM (SMO located under “functions”). This implementation of SVM uses John Platt's sequential minimal optimization algorithm to solve the optimization problem (i.e. to train SVM classifier) and shows the computed decision boundary.

Examine the output.

a) What type of SVM is used – linear or non-linear? What type of kernel function is used? Where is the equation of the decision boundary?

Answer:

Linear SVM. This is evident from “Linear Kernel: K(x,y) = ” . This is the default option in Weka.

The equation of&n