LFD Book Forum - *answer* question 13 issue

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)