def grad$($beta$,$ b$,$ xTr$,$ yTr$,$ xTe, yTe, C$,$ kerneltype, kpar$=1)$:

$"""$

INPUT:

beta : n dimensional vector that stores the linear combination coefficient

xTr : nxd dimensional matrix $($training set, each row is an input vector$)$

yTr : n dimensional vector $($training label, each entry is a label$)$

b : scalar $($bias$)$

xTe : mxd dimensional matrix $($test set, each row is an input vector$)$

yTe : m dimensional vector $($test label, each entry is a label$)$

C : scalar $($constant that controls the tradeoff between l$2-$regularizer and hinge$-$loss$)$

kerneltype: either 'linear','polynomial',$\text{'}$rbf$\text{'}$

kpar : kernel parameter $($inverse kernel width gamma in case of RBF$,$ degree in case of polynomial$)$

OUTPUTS:

beta$\_$grad : n dimensional vector $($the gradient of the hinge loss with respect to the alphas$)$

bgrad : constant $($the gradient of he hinge loss with respect to the bias, b$)$

$"""$

n$,$ d $=$ xTr$.$shape

beta$\_$grad $=$ np$.$zeros$($n$)$

bgrad $=$ np$.$zeros$(1)$

# compute the kernel values between xTr and xTr

kernel$\_$train $=$ computeK$($kerneltype$,$ xTr$,$ xTr$,$ kpar$)$

# compute the kernel values between xTe and xTr

kernel$\_$test $=$ computeK$($kerneltype$,$ xTe, xTr$,$ kpar$)$

# # YOUR CODE HERE

Tests:

xTr$\_$test, yTr$\_$test $=$ generate$\_$data$()$

n$,$ d $=$ xTr$\_$test.shape

# Checks whether grad returns a tuple

def grad$\_$test$1()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

out $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

return len$($out$)==2$

# Checks the dimension of gradients

def grad$\_$test$2()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

return len$($beta$\_$grad$)==$ n and np$.$isscalar$($bgrad$)$

# Checks the gradient of the l$2$ regularizer

def grad$\_$test$3()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $0,\text{'}$rbf$\text{'})$

beta$\_$grad$\_$grader, bgrad$\_$grader $=$ grad$\_$grader$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $0,\text{'}$rbf$\text{'})$

return $($np$.$linalg.norm$($beta$\_$grad $-$ beta$\_$grad$\_$grader$)<1$e$-5)$ and $\backslash$

$($np$.$linalg.norm$($bgrad $-$ bgrad$\_$grader$)<1$e$-5)$

# Checks the gradient of the square hinge loss

def grad$\_$test$4()$:

beta $=$ np$.$zeros$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $1,\text{'}$rbf$\text{'})$

beta$\_$grad$\_$grader, bgrad$\_$grader $=$ grad$\_$grader$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $1,\text{'}$rbf$\text{'})$

return $($np$.$linalg.norm$($beta$\_$grad $-$ beta$\_$grad$\_$grader$)<1$e$-5)$ and $\backslash$

$($np$.$linalg.norm$($bgrad $-$ bgrad$\_$grader$)<1$e$-5)$

# Checks the gradient of the loss

def grad$\_$test$5()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

beta$\_$grad$\_$grader, bgrad$\_$grader $=$ grad$\_$grader$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

return $($np$.$linalg.norm$($beta$\_$grad $-$ beta$\_$grad$\_$grader$)<1$e$-5)$ and $\backslash$

$($np$.$linalg.norm$($bgrad $-$ bgrad$\_$grader$)<1$e$-5)$

runtest$($grad$\_$test$1,$ 'grad$\_$test$1\text{'})$

runtest$($grad$\_$test$2,$ 'grad$\_$test$2\text{'})$

runtest$($grad$\_$test$3,$ 'grad$\_$test$3\text{'})$

runtest$($grad$\_$test$4,$ 'grad$\_$test$4\text{'})$

runtest$($grad$\_$test$5,$ 'grad$\_$test$5\text{'})$xTr$\_$test, yTr$\_$test $=$ generate$\_$data$()$

n$,$ d $=$ xTr$\_$test.shape

# Checks whether grad returns a tuple

def grad$\_$test$1()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

out $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

return len$($out$)==2$

# Checks the dimension of gradients

def grad$\_$test$2()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

return len$($beta$\_$grad$)==$ n and np$.$isscalar$($bgrad$)$

# Checks the gradient of the l$2$ regularizer

def grad$\_$test$3()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $0,\text{'}$rbf$\text{'})$

beta$\_$grad$\_$grader, bgrad$\_$grader $=$ grad$\_$grader$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $0,\text{'}$rbf$\text{'})$

return $($np$.$linalg.norm$($beta$\_$grad $-$ beta$\_$grad$\_$grader$)<1$e$-5)$ and $\backslash$

$($np$.$linalg.norm$($bgrad $-$ bgrad$\_$grader$)<1$e$-5)$

# Checks the gradient of the square hinge loss

def grad$\_$test$4()$:

beta $=$ np$.$zeros$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $1,\text{'}$rbf$\text{'})$

beta$\_$grad$\_$grader, bgrad$\_$grader $=$ grad$\_$grader$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $1,\text{'}$rbf$\text{'})$

return $($np$.$linalg.norm$($beta$\_$grad $-$ beta$\_$grad$\_$grader$)<1$e$-5)$ and $\backslash$

$($np$.$linalg.norm$($bgrad $-$ bgrad$\_$grader$)<1$e$-5)$

# Checks the gradient of the loss

def grad$\_$test$5()$:

beta $=$ np$.$random.rand$($n$)$

b $=$ np$.$random.rand$(1)$

beta$\_$grad, bgrad $=$ grad$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

beta$\_$grad$\_$grader, bgrad$\_$grader $=$ grad$\_$grader$($beta$,$ b$,$ xTr$\_$test, yTr$\_$test, $10,\text{'}$rbf$\text{'})$

return $($np$.$linalg.norm$($beta$\_$grad $-$ beta$\_$grad$\_$grader$)<1$e$-5)$ and $\backslash$

$($np$.$linalg.norm$($bgrad $-$ bgrad$\_$grader$)<1$e$-5)$

runtest$($grad$\_$test$1,$ 'grad$\_$test$1\text{'})$

runtest$($grad$\_$test$2,$ 'grad$\_$test$2\text{'})$

runtest$($grad$\_$test$3,$ 'grad$\_$test$3\text{'})$

runtest$($grad$\_$test$4,$ 'grad$\_$test$4\text{'})$

runtest$($grad$\_$test$5,$ 'grad$\_$test$5\text{'})$