Description
Support vector machines are a popular method for classification within the machine learning community. Essentially, a linear classifier f is generated as f(x) = w
0x + γ such that if f(x) > 0 then x is
in class P+ whereas if f(x) < 0 then x ∈ P−.
To generate this classifier a quadratic optimization model is solved:
minw,γ,ψ
1
2w
0w + C
P
i ψi
s.t. yi
[w
0xi + γ] ≥ 1 − ψi
, i = 1, . . . , m
ψi ≥ 0
Here m runs over a set of training examples, and yi is 1 if i ∈ P+ and −1 if i ∈ P−. xi are the values
of the predictor variables.
The dual problem of this quadratic program is:
maxα
P
i αi −
1
2
P
i,j αiαjyiyjx
0
ixj
s.t. P
i
yiαi = 0
C ≥ αi ≥ 0
1.1 Problem
You should formulate both these problems in GAMS. Note that for the dual problem, you may want
to introduce some intermediate variables
vk =
X
i
αiyixik
and express the objective function as
X
i
αi −
1
2
X
k
v
2
k
where k runs over the predictor features. Solve (the easiest one) using the qcp solver of your choice,
and the use the multiplier information from this first solve to set the starting values for the second
solve. Try to make the second solve take as little time as possible. You should use the data that is
provided in the abalone.gdx file and choose an appropriate value of C. What you should attempt to
predict is whether the “number of rings” is greater than 10 or not. You should allow the value of C to
be changed at the command line as shown in class. For your information the data fields are:
Problem 1 Page 1
Sex nominal M, F, and I (infant)
Length continuous mm Longest shell measurement
Diameter continuous mm perpendicular to length
Height continuous mm with meat in shell
Whole weight continuous grams whole abalone
Shucked weight continuous grams weight of meat
Viscera weight continuous grams gut weight (after bleeding)
Shell weight continuous grams after being dried
Rings integer +1.5 gives the age in years
Note that the first nominal value has been converted to 3 binary values and can be treated as separate
data for this assignment. Use the first 4000 data points for training your classifier, and report the
number of errors that you make with your classifier to a file ’error.txt’ on the remaining 177 samples.
