Gradient utraty zawiasu

25

Próbuję zaimplementować podstawowe zejście gradientu i testuję go za pomocą funkcji utraty zawiasu, tj. . Jestem jednak zdezorientowany co do gradientu utraty zawiasu. Mam wrażenie, że tak jestlhinge=max(0,1y xw)

wlhinge={y xif y xw<10if y xw1

Ale czy to nie zwraca macierzy tego samego rozmiaru co x ? Myślałem, że chcemy zwrócić wektor długości w ? Najwyraźniej mam gdzieś coś zagubionego. Czy ktoś może tutaj wskazać właściwy kierunek?

Dołączyłem podstawowy kod na wypadek, gdyby mój opis zadania nie był jasny

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

Aktualizacja: Chociaż poniższa odpowiedź pomogła mi zrozumieć problem, dane wyjściowe tego algorytmu są nadal niepoprawne dla danych. Funkcja strat zmniejsza się za każdym razem o 0,25, ale zbiega się zbyt szybko, a uzyskane masy nie skutkują dobrą klasyfikacją. Obecnie wygląda to na wynik

#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"
...  
brcs
źródło
Gradient jest wektorem, ponieważ funkcja utraty ma rzeczywiste wartości.
Wok
3
Twoja funkcja nie jest wszędzie rozróżnialna.
robin girard
2
Jak zauważa rudzik, utraty zawiasu nie można rozróżnić przy x = 1. Oznacza to po prostu, że musisz użyć algorytmu opadania pod gradientem
Alex Kreimer

Odpowiedzi:

27

Aby uzyskać gradient, różnicujemy stratę w odniesieniu do tego składnika .wiw

Przepisać straty zawiasu pod względem jako , gdzie if ( g ( w ) ) f ( z ) = max ( 0 , 1 - y z ) g ( w ) = xwwf(g(w))f(z)=max(0,1y z)g(w)=xw

Używając reguły łańcucha, otrzymujemy

wif(g(w))=fzgwi

Pierwszy składnik pochodny jest oceniany przy staje się gdy , i 0, gdy . Drugi termin pochodny staje się . Więc w końcu dostajesz - y xw < 1 xw > 1 x i f ( g ( w ) )g(w)=xwyxw<1xw>1xi

f(g(w))wi={y xiif y xw<10if y xw>1

Ponieważ rozciąga się na składowe , możesz zobaczyć powyższe jako wielkość wektorową i napisać jako skrót dlax ix (w(w1,w2,)

Jarosław Bułatow
źródło
Dzięki! To mi wyjaśnia. Teraz muszę to zrobić właściwie w praktycznym otoczeniu. Nie miałbyś pojęcia, dlaczego powyższy kod nie działa? Wydaje się, że zbiega się w 4 iteracjach, a strata zaczyna się od 1, a za każdym razem spada o 0,25 i zbliża się do zera. Jednak wytwarzane przez nią wagi wydają się całkiem błędne.
brcs
1
Możesz sprawdzić, jakie prognozy daje twoje dane treningowe. Jeśli strata spadnie do zera, wszystkie przypadki powinny zostać idealnie sklasyfikowane
Jarosław Bułatow
Dotyczy to klasyfikacji binarnej. Czy możesz podać pochodną gradientu klasyfikacji wieloklasowej z wykorzystaniem utraty zawiasu?
Shyamkkhadka
12

Spóźnia się to o 3 lata, ale może być przydatne dla kogoś ...

Niech oznacza próbkę punktów i zestaw odpowiednich etykiet . Szukamy hiperpłaszczyzny , która minimalizuje całkowitą utratę zawiasów: Aby znaleźć oblicz pochodną całkowitej utraty zawiasu. Gradient każdego komponentu to: x iR d y i{ - 1 , 1 } w w = argmin  w L h i n g e S ( w ) = argmin  w i l h i n g e ( w , x i , y i ) = argmin  w i max { 0 ,SxiRdyi{1,1}ww l h i n g e

w=argmin wLShinge(w)=argmin wilhinge(w,xi,yi)=argmin wimax{0,1yiwx}
w
lhingew={0yiwx1yixyiwx<1

Gradient sumy jest sumą gradientów. przykład Python, który wykorzystuje GD do znalezienia następuje optymalna separacja hiperpłaszczyzny zawiasu (prawdopodobnie nie jest to najbardziej wydajny kod, ale działa)

LShingew=ilhingew
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()
Alex Kreimer
źródło
I tak jest w przypadku klasyfikacji binarnej. Czy możesz podać pochodną gradientu klasyfikacji wieloklasowej z wykorzystaniem utraty zawiasu?
Shyamkkhadka
1

Naprawiłem twój kod. Głównym problemem jest twoja definicja funkcji zawiasów i d_hinge. Należy je nakładać pojedynczo. Zamiast tego twoja definicja agreguje wszystkie próbki przed pobraniem maksimum.

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

Potrzebuję n = 10000, aby się zbiegać.

[1] "strata: 0,090000, xw: 1,08999999999995,0.90999999999999905, -1.19000000000008, -1.69000000000011" [1] "strata: 0.100000, xw: 1.33999999999995,1,1199999999999, -0,900000000000075, -1,420000000000, 11,420000000000, 11,420000000000, 11,42000000000000, 11,4000000000000, 11,4000000000000, 11,4000000000000, 11,4000000000000, 11,4000000000000 0,939999999999948,0.829999999999905, -1.32000000000007, -1.77000000000011 Strata „[1]”: 0,370000, xw: 1,64999999999995,1,2899999999999, -0,630000000000075, -1,25000000000011 ”[1]” strata: 0,000000 [1] "strata: 0,240000, xw: 1,49999999999995,1.2099999999999, -0,760000000000075, -1.33000000000011" [1] "strata: 0,080000, xw: 1,09999999999995,05,0, 9199999999995, -1.18000000000007, -1.680000000000, 11.68000000000000, 11.68000000000000, 11.68000000000000 1.34999999999995,1,129999999999, -0,880000000000075, -1.41000000000011 "[1] "strata: 0.210000, xw: 0,949999999999948,0.839999999999905, -1.31000000000007, -1.76000000000011" [1] "strata: 0.380000, xw: 1.65999999999995,1,999999999999, -0,62000000000074, -11,0000000000, x1,1100 1,25999999999995,1,009999999999999, -1.0400000000000008, -1.59000000000011 Strata „[1]”: 0,000000, xw: 1,25999999999995,1,009999999999999, -1,04000000000008, -1,500000000000011 ”

John Jiang
źródło
3
Ludzie, opadanie gradientu dotyczy tylko algorytmu optymalizacji WORST i należy go stosować tylko wtedy, gdy nie ma wyboru. Algorytm Quasi-Newtona przeszukujący region lub linię, wykorzystujący wartość funkcji celu i gradient, wysadzi gradient z wody i znacznie bardziej niezawodnie zbiegnie się. I nie pisz własnego solvera, chyba że wiesz, co robisz, co robi bardzo niewiele osób.
Mark L. Stone,
2
Zgodziłbym się z obydwoma stwierdzeniami. Jednak zejście gradientowe o różnych smakach jest znacznie łatwiejsze do wdrożenia w środowisku rozproszonym, przynajmniej zgodnie z dostępnymi bibliotekami open source.
John Jiang,