Hi,
I am struggling to get the right answer for question 13. I have the algorithm working (in Python). but it's just not good enough to get perfect accuracy (or at least <5%), as every time a few points are not classified correctly. My SVM implementation (copied below) has been working well for other exercises, and I think I added the rbf kernel correctly. Is anyone else having the same issue? I can't figure out what's wrong.
Below is the standalone implementation:
Code:
import numpy as np
import math
import cvxopt
class svm():
''' Model: support vector machines '''
''' Error measure: classification error '''
''' Learning algorithm: support vector machines (linearly separable data) '''
def fit(self, X, y, kernel = 'linear', degree = 2, gamma = 1.):
''' returns the alphas '''
dimension = X.shape[1]
N = X.shape[0]
K = np.zeros(shape = (N,N))
# Computing the inner products (or kernels) for each pair of vectors
if kernel == 'linear':
for i in range(N):
for j in range(N):
K[i,j] = np.dot(X[i], X[j].T)
elif kernel == 'poly':
for i in range(N):
for j in range(N):
K[i,j] = np.square(1 + np.dot(X[i], X[j].T))
elif kernel == 'rbf':
for i in range(N):
for j in range(N):
K[i,j] = np.exp(-gamma * np.linalg.norm(X[i]-X[j]) **2)
# Generating all the matrices and vectors
P = cvxopt.matrix(np.outer(y,y) * K, tc='d')
q = -1. * cvxopt.matrix(np.ones(N), tc='d')
G = cvxopt.matrix(np.eye(N) * -1, tc='d')
h = cvxopt.matrix(np.zeros(N), tc='d')
A = cvxopt.matrix(y, (1,N), tc='d')
b = cvxopt.matrix(0.0, tc='d')
solution = cvxopt.solvers.qp(P, q, G, h, A, b)
a = np.ravel(solution['x'])
# Create a boolean list of non-zero alphas
ssv = a > 1e-5
# Select the corresponding alphas a, support vectors sv and class labels sv_y
a_small = a[ssv] # alphas
sv = X[ssv] # support vectors (Xs)
sv_y = y[ssv] # support vectors (ys)
# Computing the weights w_svm
w_svm = np.zeros((1,dimension))
for each in range(0,len(a_small)):
w_svm += np.reshape(a_small[each] * sv_y[each] * sv[each], (1,dimension))
# Computing the intercept b_svm
b_svm = sv_y[0] - np.dot(w_svm, sv[0].T)
# does not matter if divide by sv_y or not
g = np.sign( np.inner(w_svm,X) + b_svm )
self.a = a
self.a_small = a_small
self.sv = sv
self.sv_y = sv_y
self.w = w_svm
self.b = b_svm
self.g = g
return self
def predict(self, X):
''' returns the g as a column vector '''
self.g = np.sign( np.inner(self.w, X) + self.b )
return self.g
N = 100
gamma = 1.5
run = 100
Ein = []
sep = []
for r in range(0,run):
X = np.random.uniform(-1, 1,size = (N,2))
y = np.sign(X[:,1] - X[:,0] + .25 * np.sin(math.pi * X[:,0]))
X = np.insert(X, 0, 1, axis=1)
svm_RBF = svm()
svm_RBF.fit(X, y, kernel = 'rbf', gamma = 1.5)
result = svm_RBF.predict(X)
Ein.append(1 - np.average(np.equal(result, y)))
sep = np.equal(Ein, 0.)
np.average(sep)