Ide utama di balik SGD

Sep 30 2020

Pr. Hinton dalam kursus populernya di Coursera mengacu pada fakta berikut :

Rprop tidak benar-benar berfungsi ketika kami memiliki dataset yang sangat besar dan perlu melakukan pembaruan bobot batch-mini. Mengapa tidak berfungsi dengan tumpukan mini? Nah, orang-orang telah mencobanya, tetapi merasa sulit untuk membuatnya berhasil. Alasan mengapa ini tidak berhasil adalah karena itu melanggar gagasan utama di balik penurunan gradien stokastik , yaitu ketika kita memiliki kecepatan pembelajaran yang cukup kecil, itu rata-rata gradien pada tumpukan mini yang berurutan. Pertimbangkan bobotnya, yang mendapatkan gradien 0,1 pada sembilan tumpukan mini, dan gradien -0,9 pada tumpukan mini kesepuluh. Apa yang kami inginkan adalah agar gradien tersebut secara kasar saling meniadakan, sehingga tetap kurang lebih sama. Tapi bukan itu yang terjadi dengan rprop. Dengan rprop, kami menambah bobot 9 kali dan mengurangi hanya sekali, sehingga bobot bertambah jauh lebih besar.

Seperti yang Anda lihat, ide utama di balik SGD adalah bahwa gradien yang berurutan dalam tumpukan-mini harus dirata-ratakan. Apakah ada yang punya sumber resmi yang valid untuk ini? apakah ada pembenaran? Saya belum menemukan bukti apa pun sampai sekarang.

Jawaban

2 JavierTG Oct 07 2020 at 04:39

Pengaruh distribusi pembangkit data

Untuk melihat ini, pertama-tama kita harus menyebutkan bahwa, baik dengan menggunakan penurunan gradien batch (menggunakan seluruh dataset untuk menghitung gradien) maupun menggunakan penurunan gradien batch-mini, kita menghitung nilai gradien yang sebenarnya (tepat).

Untuk menghitung nilai sebenarnya dari gradien kita harus menggunakan himpunan dari semua kemungkinan nilai fitur, $x$, (dan dengan demikian outputnya $y$).

Lebih formal, dan mengacu pada kuantitas yang ingin kita minimalkan sebagai nilai yang diharapkan dari fungsi kerugian per contoh ($J(x,y,\theta)$, dimana $\theta$ adalah parameternya) wrt semua yang mungkin $x,y$ nilai-nilai, gradien sebenarnya $g$ diberikan oleh: $$g = \frac{\partial}{\partial \theta}\mathbb{E}_{x,y\sim p_{data}}(J(x,y,\theta)) $$Dan jika kami mengasumsikan kondisi tertentu, Kami memiliki itu:$$g = \mathbb{E}_{x,y\sim p_{data}}\left(\frac{\partial}{\partial \theta}J(x,y,\theta)\right) $$

Dimana $p_{data}$adalah distribusi pembangkit data (distribusi dari mana nilai$x$ dan $y$ditarik). Namun, distribusi penghasil data ini biasanya tidak diketahui. Kami hanya tahu dataset yang kami berikan.

Karena itu, untuk memperbarui parameter menggunakan semua informasi yang diberikan (set pelatihan), kami menggunakan distribusi empiris yang ditentukan oleh data pelatihan ($\hat{p}_{data}$) yang menempatkan probabilitas $1/m$ di setiap $m$ sampel $(x^{(1)}, y^{(1)}), \,(x^{(2)}, y^{(2)}),\,...\,,(x^{(m)}, y^{(m)})$dari kumpulan data. Jadi gradien didekati dengan:$$ \begin{aligned} \hat{g}&=\frac{\partial}{\partial \theta}\mathbb{E}_{x,y\sim \hat{p}_{data}}(J(x,y,\theta))\\&=\frac{\partial}{\partial \theta}\left(\sum_{i=1}^m \frac{1}{m}J_i(x^{(i)},y^{(i)},\theta)\right)\\ &= \frac{1}{m}\sum_{i=1}^m\frac{\partial }{\partial \theta}J_i(x^{(i)},y^{(i)},\theta) \end{aligned} $$ Mengakhiri dengan penurunan gradien batch.

Tapi apa yang terjadi dengan mini-batch?

Dengan menggunakan pembaruan kamar mandi mini, kami terus melihat data baru (dengan asumsi bahwa kami menghitung hanya satu periode). Jadi dalam kasus ini, menggunakan mini-batch, kami menggunakan distribusi penghasil data.

Ini berarti bahwa pada setiap update mini-batch, dengan mengambil sampel distribusi penghasil data ini, kami akan mendapatkan estimasi ($\hat{g}$) dari gradien sebenarnya ($g$) yang tidak bias yaitu $\mathbb{E}_{x,y\sim p_{data}}(\hat{g})=g$. Untuk melihat ini, dan mempertimbangkan$\text{s-sized}$ tumpukan mini: $$\begin{aligned} \mathbb{E}_{x,y\sim p_{data}}(\hat{g})&=\mathbb{E}_{x,y\sim p_{data}}\left(\frac{g^{(1)}+...+g^{(s)}}{s}\right)\\ &=\frac{1}{s}(\mathbb{E}_{x,y\sim p_{data}}(g^{(1)}+...+g^{(s)}))\\ &=\frac{1}{s}s\,\,g=g \end{aligned} $$Dengan demikian, membuat pembaruan batch mini yang sukses, kami akan cenderung rata-rata (seperti yang ditunjukkan oleh$\mathbb{E}_{x,y\sim p_{data}}(\hat{g})$) untuk memperbarui parameter kita dengan nilai sebenarnya dari gradien. Dan inilah yang menurut saya penulis rujuk dalam kutipan pertanyaan.

Referensi yang bagus:

Buku Deep Learning, Ian Goodfellow et. al Bab 8.1
Jawaban dari sini

1 cmn Oct 09 2020 at 23:07

Dalam langkah penurunan gradien penuh, fungsi kerugian didefinisikan sebagai rata-rata istilah kerugian pada titik sampel individu. Untuk meminimalkan fungsi kerugian, kita perlu melakukan rata-rata pada setiap gradien.

Dalam penurunan gradien stokastik, jika tidak ada bias dalam memilih kelompok, rata-rata atas kelompok akan menghasilkan perkiraan gradien penuh yang tidak bias.