Memahami Gradien Rata-rata Stokastik

Gradient descent merupakan teknik pengoptimalan yang paling populer dalam pemodelan machine learning (ML). Algoritme tersebut meminimalkan kesalahan antara nilai prediksi dan kebenaran dasar. Karena teknik tersebut mempertimbangkan setiap titik data untuk memahami dan meminimalkan kesalahan, kinerjanya bergantung pada ukuran data pelatihan. Teknik seperti Stochastic Gradient Descent (SGD) dirancang untuk meningkatkan kinerja perhitungan tetapi dengan mengorbankan akurasi konvergensi.

Stochastic Average Gradient menyeimbangkan pendekatan klasik, yang dikenal sebagai Full Gradient Descent dan SGD, dan menawarkan kedua manfaat tersebut. Namun sebelum kita dapat menggunakan algoritme tersebut, pertama-tama kita harus memahami signifikansinya untuk pengoptimalan model.

Mengoptimalkan Tujuan Pembelajaran Mesin dengan Gradient Descent

Setiap algoritma ML memiliki fungsi kerugian terkait yang bertujuan untuk meminimalkan atau meningkatkan kinerja model. Secara matematis, kerugian dapat didefinisikan sebagai:

Itu hanyalah perbedaan antara keluaran aktual dan keluaran yang diprediksi, dan meminimalkan perbedaan ini berarti model kita semakin mendekati nilai kebenaran dasar.

Algoritma minimisasi menggunakan penurunan gradien untuk melintasi fungsi kerugian dan menemukan nilai minimum global. Setiap langkah penelusuran melibatkan pembaruan bobot algoritma untuk mengoptimalkan keluaran.

Turunan Gradien Polos

Algoritme penurunan gradien konvensional menggunakan rata-rata semua gradien yang dihitung di seluruh kumpulan data. Siklus hidup satu contoh pelatihan terlihat seperti berikut:

Persamaan pembaruan berat terlihat seperti berikut:

Di mana W mewakili bobot model dan dJ/dW adalah turunan fungsi kerugian terhadap bobot model. Metode konvensional memiliki tingkat konvergensi yang tinggi tetapi menjadi mahal secara komputasi ketika menangani kumpulan data besar yang terdiri dari jutaan titik data.

Penurunan Gradien Stokastik (SGD)

Metodologi SGD tetap sama dengan GD biasa, tetapi alih-alih menggunakan seluruh kumpulan data untuk menghitung gradien, ia menggunakan sebagian kecil dari input. Metode ini jauh lebih efisien tetapi mungkin terlalu banyak melompati minimum global karena setiap iterasi hanya menggunakan sebagian data untuk pembelajaran.

Gradien Rata-rata Stokastik

Pendekatan Stochastic Average Gradient (SAG) diperkenalkan sebagai jalan tengah antara GD dan SGD. Pendekatan ini memilih titik data acak dan memperbarui nilainya berdasarkan gradien pada titik tersebut dan rata-rata tertimbang dari gradien masa lalu yang disimpan untuk titik data tertentu tersebut.

Mirip dengan SGD, SAG memodelkan setiap masalah sebagai jumlah terbatas dari fungsi konveks yang dapat dibedakan. Pada setiap iterasi, ia menggunakan gradien saat ini dan rata-rata gradien sebelumnya untuk pembaruan bobot. Persamaan tersebut berbentuk sebagai berikut:

Tingkat Konvergensi

Di antara dua algoritma populer, gradien penuh (FG) dan penurunan gradien stokastik (SGD), algoritma FG memiliki tingkat konvergensi yang lebih baik karena memanfaatkan seluruh set data selama setiap iterasi untuk perhitungan.

Meskipun SAG memiliki struktur yang mirip dengan SGD, tingkat konvergensinya sebanding dengan dan terkadang lebih baik daripada pendekatan gradien penuh. Tabel 1 di bawah ini merangkum hasil dari percobaan Schmidt dan kawan-kawan .

Modifikasi Lebih Lanjut

Meskipun kinerjanya menakjubkan, beberapa modifikasi telah diusulkan pada algoritma SGD asli untuk membantu meningkatkan kinerja.

• Pembobotan Ulang pada Iterasi Awal: Konvergensi SAG tetap lambat selama beberapa iterasi pertama karena algoritme menormalkan arah dengan n (jumlah total titik data). Ini memberikan estimasi yang tidak akurat karena algoritme belum melihat banyak titik data. Modifikasi menyarankan normalisasi dengan m, bukan n, di mana m adalah jumlah titik data yang terlihat setidaknya sekali hingga iterasi tertentu.
• Mini-batch: Pendekatan Gradien Stokastik menggunakan mini-batch untuk memproses beberapa titik data secara bersamaan. Pendekatan yang sama dapat diterapkan pada SAG. Hal ini memungkinkan vektorisasi dan paralelisasi untuk meningkatkan efisiensi komputer. Pendekatan ini juga mengurangi beban memori, tantangan utama bagi algoritma SAG.
• Eksperimen Ukuran Langkah: Ukuran langkah yang disebutkan sebelumnya (116L) memberikan hasil yang menakjubkan, tetapi penulis selanjutnya bereksperimen dengan menggunakan ukuran langkah 1L. Ukuran langkah terakhir memberikan konvergensi yang lebih baik. Akan tetapi, penulis tidak dapat menyajikan analisis formal dari hasil yang lebih baik. Mereka menyimpulkan bahwa ukuran langkah harus diujicobakan untuk menemukan ukuran yang optimal untuk masalah tertentu.

Pemikiran Akhir

Gradient descent merupakan optimasi populer yang digunakan untuk menemukan titik minimum global dari fungsi objektif yang diberikan. Algoritme menggunakan gradien fungsi objektif untuk melintasi lereng fungsi hingga mencapai titik terendah.

Full Gradient Descent (FG) dan Stochastic Gradient Descent (SGD) adalah dua variasi algoritma yang populer. FG menggunakan seluruh kumpulan data selama setiap iterasi dan memberikan tingkat konvergensi yang tinggi dengan biaya komputasi yang tinggi. Pada setiap iterasi, SGD menggunakan sebagian data untuk menjalankan algoritma. Cara ini jauh lebih efisien tetapi dengan konvergensi yang tidak pasti.

Stochastic Average Gradient (SAG) adalah variasi lain yang memberikan manfaat dari kedua algoritme sebelumnya. Algoritme ini menggunakan rata-rata gradien masa lalu dan sebagian dari kumpulan data untuk memberikan tingkat konvergensi yang tinggi dengan komputasi yang rendah. Algoritme ini dapat dimodifikasi lebih lanjut untuk meningkatkan efisiensinya menggunakan vektorisasi dan mini-batch.