Skip to content
Kembali ke hasil pencarian

Stochastic Gradient Descent (SGD)

Diperkenalkan oleh
Robbins, H. & Monro, S.
Tahun
1951
Jenis
First-order iterative optimization algorithm

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Stochastic Gradient Descent (SGD) adalah algoritma optimisasi iteratif orde pertama, berakar pada kerangka kerja aproksimasi stokastik yang diperkenalkan oleh Robbins dan Monro pada tahun 1951, yang meminimalkan fungsi objektif dengan memperbarui parameter model menggunakan gradien yang dihitung pada satu contoh pelatihan yang dipilih secara acak (atau mini-batch kecil) di setiap langkah.

Ini adalah mesin optimisasi inti di balik pembelajaran mesin modern dan pembelajaran mendalam, yang memungkinkan pelatihan model pada kumpulan data yang terlalu besar untuk dimuat dalam memori.

Intuisi di balik metode

Gradient descent biasa menghitung gradien eksak dari kerugian (loss) pada semua contoh pelatihan sebelum melakukan satu pembaruan parameter — benar tetapi sangat lambat pada kumpulan data besar. SGD menukar ketepatan dengan kecepatan: ia memilih satu contoh (atau batch kecil) secara acak, menghitung perkiraan gradien yang berderau (noisy), dan segera memperbarui parameter. Kebisingan (noise) bukan sekadar gangguan; ia bertindak sebagai regularisasi implisit, membantu pengoptimal lolos dari minimum lokal yang dangkal dan titik pelana (saddle points). Selama banyak iterasi, langkah-langkah yang berderau tersebut rata-rata dan parameter konvergen menuju minimum dari kerugian, mirip dengan jalan orang mabuk yang masih tiba di tujuan.

Sejarah

Dasar teoretis untuk SGD diletakkan oleh Herbert Robbins dan Sutton Monro dalam makalah mereka tahun 1951 'A Stochastic Approximation Method', yang membuktikan bahwa pembaruan berderau iteratif dengan ukuran langkah yang menurun konvergen ke akar fungsi regresi. Hubungan dengan optimisasi berbasis gradien dibuat eksplisit oleh Kiefer dan Wolfowitz (1952) dan kemudian oleh aturan LMS Widrow dan Hoff (1960) untuk penyaringan adaptif. SGD mendapatkan perhatian dalam pembelajaran mesin melalui karya LeCun dan kolaborator pada akhir 1980-an dan 1990-an untuk melatih jaringan saraf melalui backpropagation. Publikasi eksperimen skala besar oleh Bottou dan kolaborator pada tahun 2000-an menunjukkan keunggulan SGD dibandingkan metode batch pada kumpulan data industri. Formulasi mini-batch SGD modern menjadi universal dengan kebangkitan deep learning sekitar tahun 2012 (AlexNet), dan algoritma ini tetap menjadi pengoptimal dominan di bidang ini, dengan varian seperti Adam (Kingma & Ba, 2014) dibangun langsung di atas aturan pembaruannya.

Kapan digunakan

SGD adalah metode pilihan kapan pun kumpulan pelatihan cukup besar sehingga menghitung gradien penuh per pembaruan terlalu mahal, yang mencakup hampir semua pelatihan jaringan saraf modern dan penyesuaian model linier skala besar. Ini berlaku untuk fungsi kerugian yang dapat diturunkan (differentiable). Asumsi utama: kerugian dapat diturunkan (atau sub-diturunkan) terhadap parameter, titik data diambil sampelnya secara independen, dan estimator gradien tidak bias. Untuk tujuan yang sangat konveks (strongly convex), SGD mencapai konvergensi O(1/T); untuk tujuan non-konveks umum (misalnya, jaringan dalam), ia menemukan titik stasioner dalam praktiknya, meskipun tidak ada jaminan optimalitas global. Mini-batch SGD (ukuran batch 32–512) biasanya lebih disukai daripada SGD murni per contoh karena memberikan estimasi gradien dengan varians lebih rendah dan memanfaatkan paralelisme pada perangkat keras modern. Ketika kumpulan data cukup kecil untuk gradient descent seluruh batch dan tujuannya terkondisi dengan baik, metode orde kedua seperti L-BFGS mungkin konvergen lebih cepat.

Batasan dan pertimbangan

  • Estimasi gradien berderau, yang menyebabkan kerugian berfluktuasi daripada menurun secara monoton, membuat konvergensi lebih sulit didiagnosis.
  • Sangat sensitif terhadap laju pembelajaran: terlalu besar menyebabkan divergensi; terlalu kecil membuat pelatihan sangat lambat.
  • Konvergensi ke minimum global tidak dijamin untuk tujuan non-konveks seperti jaringan saraf dalam.
  • Pembaruan isotropik memperlakukan semua dimensi parameter secara setara, membuatnya kurang cocok untuk permukaan kerugian dengan kelengkungan yang sangat berbeda di sepanjang sumbu yang berbeda — memotivasi varian laju adaptif.
  • Memerlukan penyesuaian jadwal laju pembelajaran yang cermat; jadwal yang buruk secara substansial menurunkan kinerja akhir.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Skalabilitas ke kumpulan data yang sangat besar karena setiap pembaruan hanya memerlukan satu contoh atau mini-batch, menjaga memori dan komputasi per langkah tetap konstan.
  • Kebisingan bawaan memberikan regularisasi implisit dan membantu lolos dari minimum lokal yang dangkal dan titik pelana dalam lanskap non-konveks.
  • Sangat umum: berlaku untuk fungsi kerugian yang dapat diturunkan, termasuk cross-entropy, mean squared error, hinge loss, dan tujuan khusus.
  • Membentuk dasar dari hampir semua pengoptimal modern (Adam, RMSProp, AdaGrad, Nesterov momentum) — memahami SGD adalah prasyarat untuk memahaminya.
  • Mudah diimplementasikan dan diparalelkan di seluruh GPU menggunakan mini-batch.

Penerapan

  • Pelatihan jaringan saraf dalam untuk klasifikasi gambar, pengenalan ucapan, dan pemrosesan bahasa alami.
  • Penyesuaian model regresi logistik skala besar dan SVM linier dalam klasifikasi teks dan sistem rekomendasi.
  • Pengaturan pembelajaran online (online learning) di mana contoh datang secara berurutan dan model harus diperbarui secara real-time.
  • Metode gradien kebijakan pembelajaran penguatan (reinforcement learning policy gradient methods), di mana pengembalian yang diharapkan dioptimalkan menggunakan lintasan yang diambil sampelnya.
  • Faktorisasi matriks untuk penyaringan kolaboratif dalam sistem rekomendasi.

Cara kerjanya

Cara kerjanya

1

Tujuan pelatihan adalah rata-rata kerugian pada semua n contoh. Untuk tugas-tugas seperti klasifikasi dengan cross-entropy atau regresi dengan squared error, jumlah ini dapat memiliki miliaran suku, membuat evaluasi penuh di setiap iterasi menjadi tidak praktis.

Rumus
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)
2

Pada langkah t, satu contoh pelatihan (atau mini-batch) diambil sampelnya secara seragam secara acak. Gradien dari kerugian pada sampel tersebut adalah estimator tak bias dari gradien sebenarnya, sehingga rata-rata pembaruan mengarah ke arah yang benar meskipun berderau untuk setiap langkah individu.

Rumus
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})
3

Vektor parameter digerakkan ke arah yang berlawanan dengan perkiraan gradien, diskalakan oleh laju pembelajaran eta_t. Laju pembelajaran yang lebih kecil membuat pembaruan berhati-hati tetapi lambat; laju yang lebih besar mempercepat konvergensi tetapi berisiko melampaui (overshooting). Satu baris ini — pembaruan Robbins–Monro — adalah inti dari hampir setiap pengoptimal modern.

Rumus
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_t
4

Kondisi Robbins–Monro (jumlah laju divergen, jumlah kuadrat laju konvergen) menjamin konvergensi untuk tujuan konveks. Dalam praktiknya, jadwal umum meliputi penurunan bertahap (step decay), pendinginan kosinus (cosine annealing), dan permulaan ulang hangat (warm restarts); kondisi tersebut memberikan dasar teoretis mengapa jadwal yang menurun diperlukan.

Rumus
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \infty

Kesalahan umum

  • Menggunakan laju pembelajaran konstan sepanjang pelatihan tanpa jadwal penurunan apa pun, menyebabkan pengoptimal berosilasi di sekitar minimum daripada menetap di dalamnya.
  • Memilih ukuran batch tanpa mempertimbangkan efek regularisasi implisit: batch yang sangat besar mengurangi kebisingan dan dapat merusak generalisasi dibandingkan dengan batch yang lebih kecil pada jumlah epoch yang sama.
  • Lupa mengacak (shuffle) kumpulan data pelatihan sebelum setiap epoch, yang dapat menimbulkan bias sistematis ketika data diurutkan berdasarkan kelas atau waktu.
  • Menyesuaikan laju pembelajaran hanya pada kerugian validasi sekali daripada memantau kurva pelatihan, melewatkan tanda-tanda divergensi atau plateau prematur.
  • Memperlakukan SGD sebagai pengoptimal kotak hitam tanpa memahami sifat konvergensinya, kemudian beralih secara membabi buta ke Adam ketika konvergensi tampak lambat tanpa mendiagnosis akar penyebabnya.

Pertanyaan yang sering diajukan

Apa perbedaan antara SGD, mini-batch SGD, dan gradient descent seluruh batch?

Gradient descent seluruh batch menghitung gradien eksak pada semua n contoh pelatihan per pembaruan — akurat tetapi biaya O(n) per langkah. SGD murni menggunakan tepat satu contoh yang dipilih secara acak per pembaruan — biaya O(1) tetapi sangat berderau. Mini-batch SGD menggunakan subset acak kecil (biasanya 32–512 contoh) — kompromi praktis yang mengurangi kebisingan sambil menjaga biaya tetap terkelola dan memanfaatkan paralelisme GPU. Dalam penggunaan modern, 'SGD' hampir selalu berarti mini-batch SGD.

Bagaimana cara mengatur laju pembelajaran?

Tidak ada jawaban universal, tetapi praktik umum adalah memulai dengan nilai sedang (misalnya, 0,01 atau 0,1), memantau kurva kerugian pelatihan, dan menerapkan jadwal penurunan seperti penurunan bertahap, pendinginan kosinus, atau permulaan ulang hangat. Pencari laju pembelajaran (menjalankan laju pada beberapa batch dan mengamati kerugian) dapat mengidentifikasi nilai awal yang baik. Teori Robbins–Monro mensyaratkan laju menurun menjadi nol, tetapi dalam praktiknya penurunan sering diterapkan secara lembut untuk menghindari perlambatan prematur.

Mengapa SGD terkadang menggeneralisasi lebih baik daripada Adam?

Pengoptimal laju adaptif seperti Adam sering kali konvergen lebih cepat tetapi dapat mengalami overfitting lebih banyak, terutama pada tugas klasifikasi gambar. Kebisingan yang lebih tinggi dalam SGD — terutama pada ukuran batch kecil — bertindak sebagai regularisasi implisit, membantu model menemukan minimum yang lebih datar yang menggeneralisasi lebih baik. Beberapa studi empiris (misalnya, Wilson et al., 2017) telah mendokumentasikan fenomena ini, itulah sebabnya SGD dengan momentum masih lebih disukai untuk melatih model visi komputer seperti ResNet.

Apakah SGD menjamin penemuan minimum global?

Hanya untuk tujuan yang sangat konveks, di bawah kondisi ukuran langkah Robbins–Monro. Untuk tujuan non-konveks (hampir semua jaringan dalam), SGD memberikan konvergensi ke titik stasioner (di mana gradien adalah nol), yang dalam praktiknya cenderung menjadi minimum lokal yang baik daripada titik pelana atau minimum global. Secara empiris, solusi yang ditemukan seringkali cukup baik untuk kinerja state-of-the-art.

Metode terkait

Sumber

  1. Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.

    Buka referensi DOI
    Disalin.
  2. Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.

    ISBN: 978-0-262-03561-3
    Disalin.