Memahami matematika dari AdaGrad dan AdaDelta

Saya telah membangun beberapa model untuk sebuah proyek, tetapi saya tidak dapat membungkus kepala saya dengan matematika dari algoritma Adagrad dan Adadelta.

Saya mengerti bagaimana cara kerja gradient descent vanilla dan saya telah menulis kode untuk membuatnya bekerja dengan sukses.

Saya akan berterima kasih jika ada yang menjelaskan dua hal ini kepada saya atau menyediakan sumber daya untuk memahaminya.

Berkenaan dengan sumber daya:

• Menurut pendapat saya, ADADELTA: Metode Tingkat Pembelajaran Adaptif (makalah ADADELTA asli) menjelaskan (dalam bagian 1-3) baik ADAGRAD dan ADADELTA dengan cara yang cukup mudah diakses.
• Saya menemukan Metode Subgradien Adaptif untuk Pembelajaran Online dan Optimasi Stochastic menjadi kurang dapat diakses, tetapi itu adalah kertas ADAGRAD asli, jadi mungkin layak dicoba.
• Tinjauan umum tentang algoritma optimasi gradient descent (posting blog oleh Sebastian Ruder) juga membantu saya memahami ADAGRAD dan ADADELTA.
  
  

---

Berikut adalah beberapa kutipan utama dari ADADELTA: Metode Tingkat Pembelajaran Adaptif , bersama dengan beberapa contoh dan penjelasan singkat:

ADAGRAD

Aturan pembaruan untuk ADAGRAD adalah sebagai berikut:

$$\begin{matrix}\Delta x_{t}=-\frac{\eta}{\sqrt{\sum_{\tau=1}^{t}g_{\tau}^{2}}}g_{t} & & & (5)\end{matrix}$$ Di sini penyebut menghitung $l2$norma semua gradien sebelumnya atas dasar per-dimensi dan η adalah tingkat pembelajaran global yang dimiliki oleh semua dimensi.
Meskipun ada tingkat pembelajaran global yang disesuaikan dengan tangan, setiap dimensi memiliki tingkat dinamisnya sendiri.

Yaitu jika gradien dalam tiga langkah pertama adalah $g_{1}=\left(\begin{gathered}a_{1}\\ b_{1}\\ c_{1} \end{gathered} \right)\,,\,g_{2}=\left(\begin{gathered}a_{2}\\ b_{2}\\ c_{2} \end{gathered} \right)\,,\,g_{3}=\left(\begin{gathered}a_{3}\\ b_{3}\\ c_{3} \end{gathered} \right)$, kemudian:

$$\begin{gathered}\Delta x_{3}=-\frac{\eta}{\sqrt{\sum_{\tau=1}^{3}g_{\tau}^{2}}}g_{3}=-\frac{\eta}{\sqrt{\left(\begin{gathered}a_{1}^{2}+a_{2}^{2}+a_{3}^{2}\\ b_{1}^{2}+b_{2}^{2}+b_{3}^{2}\\ c_{1}^{2}+c_{2}^{2}+c_{3}^{2} \end{gathered} \right)}}\left(\begin{gathered}a_{3}\\ b_{3}\\ c_{3} \end{gathered} \right)\\ \downarrow\\ \Delta x_{3}=-\left(\begin{gathered}\frac{\eta}{\sqrt{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}}a_{3}\\ \frac{\eta}{\sqrt{b_{1}^{2}+b_{2}^{2}+b_{3}^{2}}}b_{3}\\ \frac{\eta}{\sqrt{c_{1}^{2}+c_{2}^{2}+c_{3}^{2}}}c_{3} \end{gathered} \right) \end{gathered}$$ Di sini lebih mudah untuk melihat bahwa setiap dimensi memiliki tingkat pembelajaran dinamisnya sendiri, seperti yang dijanjikan.

Masalah ADAGRAD yang coba dilawan oleh ADADELTA

Gagasan yang disajikan dalam makalah ini berasal dari ADAGRAD untuk memperbaiki dua kelemahan utama dari metode ini: 1) peluruhan tingkat pembelajaran terus menerus selama pelatihan, dan 2) kebutuhan untuk tingkat pembelajaran global yang dipilih secara manual.

Kelemahan kedua cukup jelas.

Berikut adalah contoh ketika kelemahan pertama adalah masalah:
Pertimbangkan kasus di mana nilai absolut dari setiap komponen$g_2$jauh lebih besar dari nilai absolut dari masing-masing komponen gradien pada langkah lainnya.
Untuk apapun$t>2$, itu menyatakan bahwa setiap komponen $\sqrt{\sum_{\tau=1}^{t}g_{\tau}^{2}}$ lebih besar dari nilai absolut dari masing - masing komponen $g_2$. Tetapi nilai absolut dari setiap komponen$g_2$ jauh lebih besar dari nilai absolut dari masing - masing komponen $g_t$, dan sebagainya $\Delta x_t$sangat kecil.
Selain itu, seiring dengan kemajuan algoritma, semakin dekat ke minimum, sehingga gradien semakin kecil, dan seterusnya$\Delta x_t$menjadi lebih kecil dan lebih kecil.
Jadi, mungkin saja algoritma tersebut hampir macet sebelum mencapai minimum.

ADADELTA

Alih-alih mempertimbangkan semua gradien yang dihitung, ADADELTA hanya mempertimbangkan yang terakhir $w$ gradien.

Sejak menyimpan $w$gradien kuadrat sebelumnya tidak efisien, metode kami mengimplementasikan akumulasi ini sebagai rata-rata peluruhan gradien kuadrat secara eksponensial. Asumsikan tepat waktu$t$ rata-rata berjalan ini $E\left[g^{2}\right]_{t}$ maka kami menghitung:

$$\begin{matrix}E\left[g^{2}\right]_{t}=\rho E\left[g^{2}\right]_{t-1}+\left(1-\rho\right)g_{t}^{2} & & & (8)\end{matrix}$$ dimana $\rho$adalah konstanta peluruhan [...]. Karena kami memerlukan akar kuadrat dari jumlah ini di pembaruan parameter, ini secara efektif menjadi$\text{RMS}$ dari gradien kuadrat sebelumnya hingga waktu $t$: $$\begin{matrix}\text{RMS}\left[g\right]_{t}=\sqrt{E\left[g^{2}\right]_{t}+\epsilon} & & & (9)\end{matrix}$$ dimana konstan $\epsilon$ ditambahkan ke kondisi penyebut yang lebih baik

($\text{RMS}$singkatan dari Root Mean Square .)

Demikian pula:

$$E\left[\Delta x^{2}\right]_{t-1}=\rho E\left[\Delta x^{2}\right]_{t-2}+\left(1-\rho\right)\Delta x_{t-1}^{2}$$ $$\text{RMS}\left[\Delta x\right]_{t-1}=\sqrt{E\left[\Delta x^{2}\right]_{t-1}+\epsilon}$$ Dan akhirnya:

[...] perkiraan $\Delta x_{t}$ dengan menghitung peluruhan secara eksponensial $\text{RMS}$ di atas jendela ukuran $w$ dari sebelumnya $\Delta x$ untuk memberikan metode ADADELTA:

$$\begin{matrix}\Delta x_{t}=-\frac{\text{RMS}\left[\Delta x\right]_{t-1}}{\text{RMS}\left[g\right]_{t}}g_{t} & & & (14)\end{matrix}$$ di mana konstan yang sama $\epsilon$ ditambahkan ke pembilang $\text{RMS}$demikian juga. Konstanta ini berfungsi baik untuk memulai iterasi pertama di mana$\Delta x_{0}=0$dan untuk memastikan kemajuan terus dilakukan bahkan jika pembaruan sebelumnya menjadi kecil.
[...]
Pembilang berfungsi sebagai istilah akselerasi, mengakumulasi gradien sebelumnya dalam rentang waktu [...]

Yaitu jika gradien dalam langkah $r$ adalah $g_{r}=\left(\begin{gathered}a_{r}\\ b_{r}\\ c_{r} \end{gathered} \right)$ dan $\Delta x_{r}=\left(\begin{gathered}i_{r}\\ j_{r}\\ k_{r} \end{gathered} \right)$, kemudian:

$$\begin{gathered}\Delta x_{t}=-\frac{\text{RMS}\left[\Delta x\right]_{t-1}}{\text{RMS}\left[g\right]_{t}}g_{t}=-\frac{\sqrt{E\left[\Delta x^{2}\right]_{t-1}+\epsilon}}{\sqrt{E\left[g^{2}\right]_{t}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho E\left[\Delta x^{2}\right]_{t-2}+\left(1-\rho\right)\Delta x_{t-1}^{2}+\epsilon}}{\sqrt{\rho E\left[g^{2}\right]_{t-1}+\left(1-\rho\right)g_{t}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho\left(\rho E\left[\Delta x^{2}\right]_{t-3}+\left(1-\rho\right)\Delta x_{t-2}^{2}\right)+\left(1-\rho\right)\Delta x_{t-1}^{2}+\epsilon}}{\sqrt{\rho\left(\rho E\left[g^{2}\right]_{t-2}+\left(1-\rho\right)g_{t-1}^{2}\right)+\left(1-\rho\right)g_{t}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho^{2}E\left[\Delta x^{2}\right]_{t-3}+p^{1}\left(1-\rho\right)\Delta x_{t-2}^{2}+p^{0}\left(1-\rho\right)\Delta x_{t-1}^{2}+\epsilon}}{\sqrt{\rho^{2}E\left[g^{2}\right]_{t-2}+p^{1}\left(1-\rho\right)g_{t-1}^{2}+p^{0}\left(1-\rho\right)g_{t}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\rho^{t-1}E\left[\Delta x^{2}\right]_{0}+\overset{t-1}{\underset{r=1}{\sum}}\rho^{t-1-r}\left(1-\rho\right)\Delta x_{r}^{2}+\epsilon}}{\sqrt{\rho^{t-1}E\left[g^{2}\right]_{1}+\overset{t}{\underset{r=2}{\sum}}\rho^{t-r}\left(1-\rho\right)g_{r}^{2}+\epsilon}}g_{t} \end{gathered}$$

$\rho$ adalah konstanta peluruhan, jadi kami memilihnya sedemikian rupa $\rho\in\left(0,1\right)$ (khas $\rho\ge0.9$).
Oleh karena itu, dikalikan dengan kekuatan tinggi$\rho$hasil dalam jumlah yang sangat kecil.
Membiarkan$w$ menjadi eksponen terendah sehingga kami anggap produk mengalikan nilai waras dengan $\rho^w$dapat diabaikan.
Sekarang, kita bisa memperkirakan$\Delta x_{t}$ dengan menjatuhkan istilah yang diabaikan:

$$\begin{gathered}\Delta x_{t}\approx-\frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)\Delta x_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)g_{r}^{2}+\epsilon}}g_{t}=\\ \\ -\frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)\left(\begin{gathered}i_{r}^{2}\\ j_{r}^{2}\\ k_{r}^{2} \end{gathered} \right)+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)\left(\begin{gathered}a_{r}^{2}\\ b_{r}^{2}\\ c_{r}^{2} \end{gathered} \right)+\epsilon}}\left(\begin{gathered}a_{t}\\ b_{t}\\ c_{t} \end{gathered} \right)\\ \downarrow\\ \Delta x_{t}\approx-\left(\begin{gathered}\frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)i_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)a_{r}^{2}+\epsilon}}a_{t}\\ \\ \frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)j_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)b_{r}^{2}+\epsilon}}b_{t}\\ \\ \frac{\sqrt{\overset{t-1}{\underset{r=t-w}{\sum}}\rho^{t-1-r}\left(1-\rho\right)k_{r}^{2}+\epsilon}}{\sqrt{\overset{t}{\underset{r=t+1-w}{\sum}}\rho^{t-r}\left(1-\rho\right)c_{r}^{2}+\epsilon}}c_{t} \end{gathered} \right) \end{gathered}$$

Dari quora Anda akan menemukan panduan yang lebih lengkap, tetapi ide utamanya adalah bahwa AdaGrad mencoba untuk menandai masalah ini dalam pemilihan tingkat gradien pembelajaran dalam pembelajaran mesin:

1 Pemilihan tingkat pembelajaran secara manual η.

2 Vektor gradien gt diskalakan secara seragam oleh tingkat pembelajaran skalar η.

3 Tingkat pembelajaran η tetap konstan selama proses pembelajaran.

Ini menyelesaikan masalah 2 dan 3 hanya dengan membagi setiap komponen gradien saat ini dengan norma L2 dari gradien yang diamati di masa lalu untuk komponen tertentu.

Itu sendiri memiliki masalah berikut:

1 Tingkat pembelajaran yang terus membusuk η.

2 Pemilihan tingkat pembelajaran secara manual η.

AdaDelta menyelesaikan kekhawatiran AdaGrad 1 dengan menjumlahkan gradien hanya dalam jendela tertentu W.

Solusi Concern 2 berkaitan dengan ketidakcocokan dalam satuan gradien dan karenanya

proses akumulasi aktual diimplementasikan menggunakan konsep dari momentum.

Perhitungan terakhir membutuhkan pemahaman tentang teori momentum dan itu dijelaskan secara singkat di artikel.

Gagasan saya adalah untuk memberikan penyebab utama di balik apa yang dimaksudkan, mungkin itu membuat membaca lebih mudah.