## Description

## Problem 1: SPAM, SPAM, HAM (50 pts)

For this problem, you will use the spam data set provided with this problem set. The data has

been divided into three pieces spam train.data, spam validation.data, and spam test.data. These

data sets were generated using the UCI Spambase data set (follow the link for information about

the format of the data). Note that the class label is the last column in the data set.

## 1. Primal SVMs

(a) Using gradient descent or quadratic programming, apply the SVM with slack formulation

to train a classifier for each choice of

c ∈ {1, 10, 102

, 103

, 104

, 105

, 106

, 107

, 108} without using any feature maps.

(b) What is the accuracy of the learned classifier on the training set for each value of c?

(c) Use the validation set to select the best value of c. What is the accuracy on the validation

set for each value of c?

(d) Report the accuracy on the test set for the selected classifier.

## 2. Dual SVMs with Gaussian Kernels

(a) Using quadratic programming, apply the dual of the SVM with slack formulation to

train a classifier for each choice of

c ∈ {1, 10, 102

, 103

, 104

, 105

, 106

, 107

, 108} using a Gaussian kernel with

σ

2 ∈ {.1, 1, 10, 100, 1000}.

(b) What is the accuracy of the learned classifier on the training set for each pair of c and

σ

2

?

(c) Use the validation set to select the best value of c and σ

2

. What is the accuracy on the

validation set for each pair of c and σ

2

?

(d) Report the accuracy on the test set for the selected classifier.

3. What is the accuracy of the k-nearest neighbor classifier for k = 1, 5, 11, 15, 21? You don’t

need to implement the k-dimensional tree version.

4. Which of these approaches (if any) should be preferred for this classification task? Explain.

1

## Problem 2: Method of Lagrange Multipliers (20 pts)

Suppose that we modified the objective function in the SVM with slack formulation to be a quadratic

penalty instead of a linear penalty, that is minimize 1

2

||w||2+c

P

i

ξ

2

i

subject to the same constraints

as the standard SVM with slack. What is the dual of this new quadratic penalized SVM with slack

problem for a fixed c? Can the kernel trick still be applied?

## Problem 3: Poisonous Mushrooms? (30 pts)

For this problem, you will use the mushroom data set provided with this problem set. The data has

been divided into two pieces mush train.data and mush test.data. These data sets were generated

using the UCI Mushroom data set (follow the link for information about the format of the data).

Note that the class label is the first column in the data set.

1. Assuming you break ties using the attribute that occurs first (left to right) in the data, draw

the resulting decision tree and report the maximum information gain for each node that you

added to the tree.

2. What is the accuracy of this decision tree on the test data?

3. Now consider arbitrary input data. Suppose that you decide to limit yourself to decision

trees of height one, i.e., only one split. Is the tree produced by the information gain heuristic

optimal on the training data (that is, no other decision tree has higher accuracy)?

2