Gradien kehilangan Engsel

25

Saya mencoba menerapkan gradient descent dasar dan saya mengujinya dengan fungsi kehilangan engsel yaitu . Namun, saya bingung tentang gradien kehilangan engsel. Saya mendapat kesan bahwa itu adalahlengsel=maks(0,1-y xw)

wlengsel={-y xjika y xw<10jika y xw1

Tapi bukankah ini mengembalikan matriks dengan ukuran yang sama dengan x ? Saya pikir kami ingin mengembalikan vektor dengan panjang w ? Jelas, saya punya sesuatu yang membingungkan. Bisakah seseorang menunjuk ke arah yang benar di sini?

Saya telah memasukkan beberapa kode dasar jika deskripsi tugas saya tidak jelas

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

Pembaruan: Sementara jawaban di bawah ini membantu saya memahami masalah, output dari algoritma ini masih salah untuk data yang diberikan. Fungsi kerugian berkurang 0,25 setiap kali tetapi konvergen terlalu cepat dan bobot yang dihasilkan tidak menghasilkan klasifikasi yang baik. Saat ini hasilnya terlihat seperti

#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
sumber
Gradien adalah vektor karena fungsi kerugian Anda memiliki nilai nyata.
Wok
3
fungsi Anda tidak dapat dibedakan di mana-mana.
robin girard
2
Sebagai catatan robin kehilangan engsel tidak dapat dibedakan pada x = 1. Ini hanya berarti bahwa Anda perlu menggunakan algoritma keturunan sub-gradien
Alex Kreimer

Jawaban:

27

Untuk mendapatkan gradien kami membedakan kerugian sehubungan dengan komponen ke- dari w .sayaw

Tulis ulang kehilangan engsel dalam bentuk sebagai f ( g ( w ) ) di mana f ( z ) = maks ( 0 , 1 - y z ) dan g ( w ) = xwf(g(w))f(z)=max(0,1y z)g(w)=xw

Menggunakan aturan rantai yang kita dapatkan

wif(g(w))=fzgwi

Istilah derivatif pertama dievaluasi pada menjadi - y ketika xw < 1 , dan 0 ketika xw > 1 . Istilah turunan kedua menjadi x i . Jadi pada akhirnya Anda mendapatkan f ( g ( w ) )g(w)=xwyxw<1xw>1xi

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

Karena berkisar pada komponen x , Anda dapat melihat di atas sebagai jumlah vektor, dan menulis ix sebagai singkatan untuk(w(w1,w2,)

Yaroslav Bulatov
sumber
Terima kasih! Itu menjelaskan bagi saya. Sekarang saya hanya harus melakukannya dengan benar dalam pengaturan yang praktis. Anda tidak tahu mengapa kode di atas tidak berfungsi? Tampaknya konvergen dalam 4 iterasi dengan kerugian mulai dari 1 dan turun 0,25 setiap kali dan konvergen pada 0. Namun, bobot yang dihasilkannya tampak cukup salah.
brcs
1
Anda bisa memeriksa prediksi apa yang diberikannya ke data pelatihan Anda. Jika kehilangan turun ke nol, semua instance harus diklasifikasikan dengan sempurna
Yaroslav Bulatov
Ini adalah kasus untuk klasifikasi biner. Bisakah Anda memberikan derivasi untuk gradien klasifikasi multi kelas menggunakan engsel loss?
Shyamkkhadka
12

Ini terlambat 3 tahun, tetapi mungkin masih relevan untuk seseorang ...

SxsayaRdysaya{-1,1}w

w=Argmin wL.Shsayange(w)=Argmin wsayalhsayange(w,xsaya,ysaya)=Argmin wsayamaks{0,1-ysayawx}
Mencari wmengambil turunan dari total kerugian engsel. Gradien dari setiap komponen adalah:
lhsayangew={0ysayawx1-ysayaxysayawx<1

Gradien dari jumlah adalah jumlah dari gradien.

L.Shsayangew=sayalhsayangew
Contoh Python, yang menggunakan GD untuk menemukan hyperplane separatinig optimal engsel-loss berikut (mungkin bukan kode yang paling efisien, tetapi berfungsi)
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
sumber
Saya ini adalah kasus untuk klasifikasi biner. Bisakah Anda memberikan derivasi untuk gradien klasifikasi multi kelas menggunakan engsel loss?
Shyamkkhadka
1

Saya memperbaiki kode Anda. Masalah utama adalah definisi Anda tentang fungsi engsel dan d_hinge. Ini harus diterapkan satu sampel pada satu waktu. Alih-alih, definisi Anda mengumpulkan semua sampel sebelum mengambil yang 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)

Saya perlu n = 10.000 untuk bertemu.

[1] "kerugian: 0,090000, xw: 1,0899999999999595,9099999999905, -1.19000000000008, -1.6900000000001111" [1] "kerugian: 0.100000, xw: 1.33999999999999999, -0.9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ,00 0,990,9999999999999,9919909900000000000000000000000, bisnis, bisnis, bisnis,,,,,,,,, dalam perkawinan, lebih lanjut, lebih lanjut lagi, lagi, lagi, lagi, lagi, lagi-lebih112100100100100100000000990000000000000000000000000000o0000o990000 usaha_,,,,,,,,,,,,, ... [1] "kerugian: 0.240000, xw: 1.49999999999995.1.2099999999999, -0.760000000000075, -1.3300000000001111" [1] "kerugian: 0.080000, xw: 1.09999999999999999.0.0.91999999999999905, -1.180000000000700, -10000000000700, 0000000000007, 0000, 0000" 1.34999999999995,1.1299999999999, -0.890000000000075, -1.4100000000001111 "[1] "kerugian: 0,210000, xw: 0.949999999999948.0.8399999999995, -1.31000000000007, -1.7600000000001111" [1] "kerugian: 0.380000, xw: 1.65999999999999991.299999999999999, -0.6200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.25999999999995,1.0099999999999, -1.04000000000008, -1.5900000000001111 "[1]" kerugian: 0,000000, xw: 1,259999999999991,19999999999999, -1,0400000000000011 "

John Jiang
sumber
3
People, gradient descent hanyalah tentang algoritma optimasi TERBURUK yang ada, dan harus digunakan hanya ketika tidak ada pilihan. Wilayah kepercayaan atau pencarian baris Algoritma Quasi-Newton, menggunakan nilai fungsi objektif dan gradien, akan meniup gradien turun dari air, dan jauh lebih andal konvergen. Dan jangan menulis solver Anda sendiri kecuali Anda tahu apa yang Anda lakukan, yang sangat sedikit orang lakukan.
Mark L. Stone
2
Saya setuju dengan kedua pernyataan itu. Namun gradient descent dengan berbagai rasa jauh lebih mudah diimplementasikan dalam lingkungan terdistribusi, setidaknya menurut perpustakaan open source yang tersedia di luar sana.
John Jiang