Gradiente de la Bisagra de la pérdida de

Question

Estoy tratando de implementar básicos de gradiente de la pendiente y lo estoy probando con una bisagra de la función de pérdida es decir $l_{\text{hinge}} = \max(0,1-y\ \boldsymbol{x}\cdot\boldsymbol{w})$. Sin embargo, estoy confundido acerca de la pendiente de la bisagra de la pérdida. Yo estoy bajo la impresión de que es

$$ \frac{\partial }{\partial w}l_{\text{bisagra}} = \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{casos} $$

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}$? Claramente, tengo algo confundido en algún lugar. Alguien puede apuntar en la dirección correcta aquí?

He incluido algunas código básico en caso de que mi descripción de la tarea no fue claro

#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)

Actualización: Mientras que la respuesta a ayudado a mi entender el problema, la salida de este algoritmo sigue siendo incorrecta de los datos. La función de pérdida se reduce a 0.25 cada vez, sino que convergen demasiado rápido y la resultante de los pesos no son el resultado de una buena clasificación. En la actualidad se ve el resultado

#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"
...  

Answer 1

Para obtener el gradiente de podemos diferenciar la pérdida con respecto a $i$ésima componente de $w$.

La reescritura de la bisagra de la pérdida en términos de $w$ $f(g(w))$ donde $f(z)=\max(0,1-y\ z)$ $g(w)=\mathbf{x}\cdot \mathbf{w}$

Usando la regla de la cadena obtenemos

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

Primera derivada término se evalúa en $g(w)=x\cdot w$ convertirse $-y$ al $\mathbf{x}\cdot w<1$, y 0 $\mathbf{x}\cdot w>1$. En segundo término derivado vuelve $x_i$. Así que al final se consigue $$ \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{casos} $$

Desde $i$ rangos de los componentes de $x$, puede ver la anterior como una cantidad vectorial, y escribir $\frac{\partial}{\partial w}$ como abreviación $(\frac{\partial}{\partial w_1},\frac{\partial}{\partial w_2},\ldots)$

Answer 2

Se trata de 3 años tarde, pero aún así puede ser relevante para alguien...

Deje $S$ denotar una muestra de puntos de $x_i \in R^d$ y el conjunto de etiquetas correspondientes a $y_i \in \{-1,1\}$. La búsqueda para encontrar un hyperplane $w$ que minimicen el total de la bisagra de la pérdida: \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} Para encontrar$w^*$, derivado del total de la bisagra de la pérdida . Gradiente de cada componente es: $$ \frac{\partial{l_{bisagra}}}{\partial w}= \begin{cases} 0 & y_iw\cdot x \geq 1 \\ -y_ix & y_iw\cdot x < 1 \end{casos} $$

El gradiente de la suma es la suma de los gradientes. $$ \frac{\partial{L_S^{bisagra}}}{\partial{w}}=\sum_i{\frac{\partial{l_{bisagra}}}{\partial w}} $$ Python ejemplo, que utiliza GD para encontrar la bisagra de la pérdida óptima separatinig hyperplane de la siguiente manera (probablemente no es la más eficiente de código, pero funciona)

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()

Answer 3

He arreglado el código. El principal problema es su definición de la bisagra y d_hinge funciones. Estos deben ser aplicados en una muestra en un momento. En cambio, la definición de los agregados de todas las muestras antes de tomar el máximo.

#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)

Necesito n=10000 a converger.

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