30
$\begingroup$

I'm trying to implement basic gradient descent and I'm testing it with a hinge loss function i.e. $l_{\text{hinge}} = \max(0,1-y\ \boldsymbol{x}\cdot\boldsymbol{w})$. However, I'm confused about the gradient of the hinge loss. I'm under the impression that it is

$$ \frac{\partial }{\partial w}l_{\text{hinge}} = \begin{cases} -y\ \boldsymbol{x} &\text{if } y\ \boldsymbol{x}\cdot\boldsymbol{w} < 1 \\ 0&\text{if } y\ \boldsymbol{x}\cdot\boldsymbol{w} \geq 1 \end{cases} $$

But doesn't this return a matrix the same size as $\boldsymbol{x}$? I thought we were looking to return a vector of length $\boldsymbol{w}$? Clearly, I've got something confused somewhere. Can someone point in the right direction here?

I've included some basic code in case my description of the task was not clear

#Run standard gradient descent
gradient_descent<-function(fw, dfw, n, lr=0.01)
{
    #Date to be used
    x<-t(matrix(c(1,3,6,1,4,2,1,5,4,1,6,1), nrow=3))
    y<-c(1,1,-1,-1)
    w<-matrix(0, nrow=ncol(x))

    print(sprintf("loss: %f,x.w: %s",sum(fw(w,x,y)),paste(x%*%w, collapse=',')))
    #update the weights 'n' times
    for (i in 1:n)
    {
      w<-w-lr*dfw(w,x,y)
      print(sprintf("loss: %f,x.w: %s",sum(fw(w,x,y)),paste(x%*%w,collapse=',')))
    }
}
#Hinge loss
hinge<-function(w,x,y) max(1-y%*%x%*%w, 0)
d_hinge<-function(w,x,y){ dw<-t(-y%*%x); dw[y%*%x%*%w>=1]<-0; dw}
gradient_descent(hinge, d_hinge, 100, lr=0.01)

Update: While the answer below helped my understanding of the problem, the output of this algorithm is still incorrect for the given data. The loss function reduces by 0.25 each time but converge too fast and the resulting weights do not result in a good classification. Currently the output looks like

#y=1,1,-1,-1
"loss: 1.000000, x.w: 0,0,0,0"
"loss: 0.750000, x.w: 0.06,-0.1,-0.08,-0.21"
"loss: 0.500000, x.w: 0.12,-0.2,-0.16,-0.42"
"loss: 0.250000, x.w: 0.18,-0.3,-0.24,-0.63"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
...  
$\endgroup$
  • $\begingroup$ The gradient is a vector since your loss function has real values. $\endgroup$ – Wok Nov 17 '10 at 7:04
  • 3
    $\begingroup$ your function is not differentiable everywhere. $\endgroup$ – robin girard Nov 17 '10 at 11:40
  • 2
    $\begingroup$ As robin notes hinge loss is not differentiable at x=1. This just means that you need to use sub-gradient descent algorithm $\endgroup$ – Alex Kreimer May 4 '14 at 4:40
34
$\begingroup$

To get the gradient we differentiate the loss with respect to $i$th component of $w$.

Rewrite hinge loss in terms of $w$ as $f(g(w))$ where $f(z)=\max(0,1-y\ z)$ and $g(w)=\mathbf{x}\cdot \mathbf{w}$

Using chain rule we get

$$\frac{\partial}{\partial w_i} f(g(w))=\frac{\partial f}{\partial z} \frac{\partial g}{\partial w_i} $$

First derivative term is evaluated at $g(w)=x\cdot w$ becoming $-y$ when $\mathbf{x}\cdot w<1$, and 0 when $\mathbf{x}\cdot w>1$. Second derivative term becomes $x_i$. So in the end you get $$ \frac{\partial f(g(w))}{\partial w_i} = \begin{cases} -y\ x_i &\text{if } y\ \mathbf{x}\cdot \mathbf{w} < 1 \\ 0&\text{if } y\ \mathbf{x}\cdot \mathbf{w} > 1 \end{cases} $$

Since $i$ ranges over the components of $x$, you can view the above as a vector quantity, and write $\frac{\partial}{\partial w}$ as shorthand for $(\frac{\partial}{\partial w_1},\frac{\partial}{\partial w_2},\ldots)$

$\endgroup$
  • $\begingroup$ Thanks! That clears things up for me. Now I just have to get it right in a practical setting. You wouldn't happen to have any idea why the above code doesn't work? It seems to converge in 4 iterations with the loss starting at 1 and going down 0.25 each time and converging at 0. However, the weights it produces seem quite wrong. $\endgroup$ – brcs Nov 17 '10 at 11:56
  • 1
    $\begingroup$ You could check what predictions it gives to your training data. If loss goes down to zero, all the instances should be classified perfectly $\endgroup$ – Yaroslav Bulatov Nov 17 '10 at 20:33
  • $\begingroup$ This is the case for binary classification. Could you please give derivation for gradient of multi class classification using hinge loss ? $\endgroup$ – Shyamkkhadka Mar 16 '17 at 10:00
14
$\begingroup$

This is 3 years late, but still may be relevant for someone...

Let $S$ denote a sample of points $x_i \in R^d$ and the set of corresponding labels $y_i \in \{-1,1\}$. We search to find a hyperplane $w$ that would minimize the total hinge-loss: \begin{equation} w^* = \underset{w}{\text{argmin }} L^{hinge}_S(w) = \underset{w}{\text{argmin }} \sum_i{l_{hinge}(w,x_i,y_i)}= \underset{w}{\text{argmin }} \sum_i{\max{\{0,1-y_iw\cdot x}\}} \end{equation} To find $w^*$ take derivative of the total hinge loss . Gradient of each component is: $$ \frac{\partial{l_{hinge}}}{\partial w}= \begin{cases} 0 & y_iw\cdot x \geq 1 \\ -y_ix & y_iw\cdot x < 1 \end{cases} $$

The gradient of the sum is a sum of gradients. $$ \frac{\partial{L_S^{hinge}}}{\partial{w}}=\sum_i{\frac{\partial{l_{hinge}}}{\partial w}} $$ Python example, which uses GD to find hinge-loss optimal separatinig hyperplane follows (its probably not the most efficient code, but it works)

import numpy as np
import matplotlib.pyplot as plt

def hinge_loss(w,x,y):
    """ evaluates hinge loss and its gradient at w

    rows of x are data points
    y is a vector of labels
    """
    loss,grad = 0,0
    for (x_,y_) in zip(x,y):
        v = y_*np.dot(w,x_)
        loss += max(0,1-v)
        grad += 0 if v > 1 else -y_*x_
    return (loss,grad)

def grad_descent(x,y,w,step,thresh=0.001):
    grad = np.inf
    ws = np.zeros((2,0))
    ws = np.hstack((ws,w.reshape(2,1)))
    step_num = 1
    delta = np.inf
    loss0 = np.inf
    while np.abs(delta)>thresh:
        loss,grad = hinge_loss(w,x,y)
        delta = loss0-loss
        loss0 = loss
        grad_dir = grad/np.linalg.norm(grad)
        w = w-step*grad_dir/step_num
        ws = np.hstack((ws,w.reshape((2,1))))
        step_num += 1
    return np.sum(ws,1)/np.size(ws,1)

def test1():
    # sample data points
    x1 = np.array((0,1,3,4,1))
    x2 = np.array((1,2,0,1,1))
    x  = np.vstack((x1,x2)).T
    # sample labels
    y = np.array((1,1,-1,-1,-1))
    w = grad_descent(x,y,np.array((0,0)),0.1)
    loss, grad = hinge_loss(w,x,y)
    plot_test(x,y,w)

def plot_test(x,y,w):
    plt.figure()
    x1, x2 = x[:,0], x[:,1]
    x1_min, x1_max = np.min(x1)*.7, np.max(x1)*1.3
    x2_min, x2_max = np.min(x2)*.7, np.max(x2)*1.3
    gridpoints = 2000
    x1s = np.linspace(x1_min, x1_max, gridpoints)
    x2s = np.linspace(x2_min, x2_max, gridpoints)
    gridx1, gridx2 = np.meshgrid(x1s,x2s)
    grid_pts = np.c_[gridx1.ravel(), gridx2.ravel()]
    predictions = np.array([np.sign(np.dot(w,x_)) for x_ in grid_pts]).reshape((gridpoints,gridpoints))
    plt.contourf(gridx1, gridx2, predictions, cmap=plt.cm.Paired)
    plt.scatter(x[:, 0], x[:, 1], c=y, cmap=plt.cm.Paired)
    plt.title('total hinge loss: %g' % hinge_loss(w,x,y)[0])
    plt.show()

if __name__ == '__main__':
    np.set_printoptions(precision=3)
    test1()
$\endgroup$
  • $\begingroup$ I this is the case for binary classification. Could you please give derivation for gradient of multi class classification using hinge loss ? $\endgroup$ – Shyamkkhadka Mar 16 '17 at 10:00
1
$\begingroup$

I fixed your code. The main problem is your definition of hinge and d_hinge functions. These should be applied one sample at a time. Instead your definition aggregates all the samples before taking the maximum.

#Run standard gradient descent
gradient_descent<-function(fw, dfw, n, lr=0.01)
{
    #Date to be used
    x<-t(matrix(c(1,3,6,1,4,2,1,5,4,1,6,1), nrow=3))
    y<-t(t(c(1,1,-1,-1)))
    w<-matrix(0, nrow=ncol(x))


    print(sprintf("loss: %f,x.w: %s",sum(mapply(function(xr,yr) fw(w,xr,yr), split(x,row(x)),split(y,row(y)))),paste(x%*%w, collapse=',')))
    #update the weights 'n' times
    for (i in 1:n)
    {
      w<-w-lr*dfw(w,x,y)
      print(sprintf("loss: %f,x.w: %s",sum(mapply(function(xr,yr) fw(w,xr,yr), split(x,row(x)),split(y,row(y)))),paste(x%*%w,collapse=',')))
    }
}

#Hinge loss
hinge<-function(w,xr,yr) max(1-yr*xr%*%w, 0)
d_hinge<-function(w,x,y){ dw<- apply(mapply(function(xr,yr) -yr * xr * (yr * xr %*% w < 1),split(x,row(x)),split(y,row(y))),1,sum); dw}
gradient_descent(hinge, d_hinge, 100, lr=0.01)

I need n=10000 to converge.

[1] "loss: 0.090000,x.w: 1.08999999999995,0.909999999999905,-1.19000000000008,-1.69000000000011" [1] "loss: 0.100000,x.w: 1.33999999999995,1.1199999999999,-0.900000000000075,-1.42000000000011" [1] "loss: 0.230000,x.w: 0.939999999999948,0.829999999999905,-1.32000000000007,-1.77000000000011" [1] "loss: 0.370000,x.w: 1.64999999999995,1.2899999999999,-0.630000000000075,-1.25000000000011" [1] "loss: 0.000000,x.w: 1.24999999999995,0.999999999999905,-1.05000000000008,-1.60000000000011" [1] "loss: 0.240000,x.w: 1.49999999999995,1.2099999999999,-0.760000000000075,-1.33000000000011" [1] "loss: 0.080000,x.w: 1.09999999999995,0.919999999999905,-1.18000000000007,-1.68000000000011" [1] "loss: 0.110000,x.w: 1.34999999999995,1.1299999999999,-0.890000000000075,-1.41000000000011" [1] "loss: 0.210000,x.w: 0.949999999999948,0.839999999999905,-1.31000000000007,-1.76000000000011" [1] "loss: 0.380000,x.w: 1.65999999999995,1.2999999999999,-0.620000000000074,-1.24000000000011" [1] "loss: 0.000000,x.w: 1.25999999999995,1.0099999999999,-1.04000000000008,-1.59000000000011" [1] "loss: 0.000000,x.w: 1.25999999999995,1.0099999999999,-1.04000000000008,-1.59000000000011"

$\endgroup$
  • 3
    $\begingroup$ Peoples, gradient descent is just about the WORST optimization algorithm there is, and should be used only when there is no choice. A trust region or line search Quasi-Newton algorithm, using objective function value and gradient, will blow gradient descent out of the water, and much more reliably converge. And don't write your own solver unless you know what you're doing, which very few people do. $\endgroup$ – Mark L. Stone Jul 22 '15 at 20:50
  • 2
    $\begingroup$ I would agree with both statements. However gradient descent with various flavors is much easier to implement in a distributed environment, at least according to the available open source libraries out there. $\endgroup$ – John Jiang Aug 11 '15 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.