Bagaimana penurunan gradien stokastik dapat menghemat waktu dibandingkan dengan penurunan gradien standar?

Keturunan Gradien Standar akan menghitung gradien untuk seluruh dataset pelatihan.

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad

Untuk jumlah zaman yang ditentukan sebelumnya, pertama-tama kita menghitung vektor gradien weights_grad dari fungsi kerugian untuk seluruh dataset menggunakan parameter vektor parameter kami.

Stochastic Gradient Descent secara kontras melakukan pembaruan parameter untuk setiap contoh pelatihan x (i) dan label y (i).

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

SGD dikatakan jauh lebih cepat. Namun, saya tidak mengerti bagaimana bisa jauh lebih cepat jika kita masih memiliki perulangan di semua titik data. Apakah perhitungan gradien dalam GD jauh lebih lambat daripada perhitungan GD untuk setiap titik data secara terpisah?

Kode berasal dari sini .

Jawaban singkat:

• Dalam banyak pengaturan data besar (katakan beberapa juta titik data), menghitung biaya atau gradien membutuhkan waktu yang sangat lama, karena kita perlu menjumlahkan semua titik data.
• Kita TIDAK perlu memiliki gradien yang tepat untuk mengurangi biaya dalam iterasi yang diberikan. Beberapa perkiraan gradien akan bekerja dengan baik.
• Stochastic gradient decent (SGD) memperkirakan gradien hanya menggunakan satu titik data. Jadi, mengevaluasi gradien menghemat banyak waktu dibandingkan dengan menjumlahkan semua data.
• Dengan jumlah iterasi yang "masuk akal" (jumlah ini bisa beberapa ribu, dan jauh lebih sedikit dari jumlah titik data, yang mungkin jutaan), gradien stokastik yang layak mungkin mendapatkan solusi yang baik dan masuk akal.

Jawaban panjang:

Notasi saya mengikuti kursus pembelajaran mesin Andrew NG Coursera. Jika Anda tidak terbiasa dengan itu, Anda dapat meninjau seri ceramah di sini .

Mari kita asumsikan regresi pada kuadrat kerugian, fungsi biayanya

dan gradiennya adalah

untuk gradient decent (GD), kami memperbarui parameter dengan

Untuk gradien stokastik yang layak kita hilangkan jumlah dan $1/m$ konstan, tetapi dapatkan gradien untuk titik data saat ini $x^{(i)},y^{(i)}$, di mana muncul penghematan waktu.

Inilah mengapa kami menghemat waktu:

Misalkan kita memiliki 1 miliar titik data.

• Dalam GD, untuk memperbarui parameter sekali, kita perlu memiliki gradien (tepat). Ini membutuhkan jumlah 1 miliar data poin ini untuk melakukan 1 pembaruan.

• Dalam SGD, kita dapat menganggapnya sebagai mencoba untuk mendapatkan gradien yang diperkirakan alih-alih gradien yang tepat . Perkiraannya datang dari satu titik data (atau beberapa titik data yang disebut kumpulan mini). Karenanya, dalam SGD, kami dapat memperbarui parameter dengan sangat cepat. Selain itu, jika kita "mengulangi" semua data (disebut satu zaman), sebenarnya kita memiliki 1 miliar pembaruan.

Kuncinya adalah, dalam SGD Anda tidak perlu memiliki 1 miliar iterations / update, tetapi iterations / update, katakanlah 1 juta, dan Anda akan memiliki model "cukup baik" untuk digunakan.

Saya menulis kode untuk mendemonstrasikan ide tersebut. Pertama-tama kita memecahkan sistem linear dengan persamaan normal, kemudian menyelesaikannya dengan SGD. Kemudian kami membandingkan hasilnya dalam hal nilai parameter dan nilai fungsi tujuan akhir. Untuk memvisualisasikannya nanti, kita akan memiliki 2 parameter untuk disesuaikan.

set.seed(0);n_data=1e3;n_feature=2;
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)
res1=solve(t(A) %*% A, t(A) %*% b)

sq_loss<-function(A,b,x){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1])
}

sq_loss_gr_approx<-function(A,b,x){
  # note, in GD, we need to sum over all data
  # here i is just one random index sample
  i=sample(1:n_data, 1)
  gr=2*(crossprod(A[i,],x)-b[i])*A[i,]
  return(gr)
}

x=runif(n_feature)
alpha=0.01
N_iter=300
loss=rep(0,N_iter)

for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr_approx(A,b,x)
  loss[i]=sq_loss(A,b,x)
}

Hasil:

as.vector(res1)
[1] 0.4368427 0.3991028
x
[1] 0.3580121 0.4782659

Catatan, meskipun parameternya tidak terlalu dekat, nilai kerugiannya adalah $124.1343$ dan $123.0355$ yang sangat dekat.

Berikut ini adalah nilai fungsi biaya atas iterasi, kita dapat melihatnya secara efektif dapat mengurangi kerugian, yang menggambarkan ide: kita dapat menggunakan subset data untuk memperkirakan gradien dan mendapatkan hasil "cukup baik".

Sekarang mari kita periksa upaya komputasi antara dua pendekatan. Dalam percobaan, kami punya$1000$titik data, menggunakan SD, mengevaluasi gradien sekali perlu menjumlahkannya data. TETAPI dalam SGD, sq_loss_gr_approxfungsinya hanya menjumlahkan 1 titik data, dan secara keseluruhan kita lihat, algoritma kurang dari satu$300$ iterasi (perhatikan, tidak $1000$ iterasi.) Ini adalah penghematan komputasi.