Penurunan gradien batch dibandingkan penurunan gradien stokastik

101

Misalkan kita memiliki beberapa set pelatihan untuk . Juga misalkan kita menjalankan beberapa jenis algoritma pembelajaran terawasi pada set pelatihan. Hipotesa direpresentasikan sebagai . Kita perlu menemukan parameter yang meminimalkan "jarak" antara dan . Biarkan(x(i),y(i))i=1,,mhθ(x(i))=θ0+θ1x(i)1++θnx(i)nθy(i)hθ(x(i))

J(θ)=12i=1m(y(i)hθ(x(i))2

Maka kami ingin menemukan yang meminimalkan . Dalam gradient descent, kami menginisialisasi setiap parameter dan melakukan pembaruan berikut:θJ(θ)

θj:=θjαθjJ(θ)

Apa perbedaan utama antara keturunan gradien batch dan gradien keturunan stokastik?

Keduanya menggunakan aturan pembaruan di atas. Tetapi apakah yang satu lebih baik dari yang lain?

pengguna20616
sumber

Jawaban:

121

Penerapan keturunan atau stochastic gradient descent sangat tergantung pada kesalahan yang berlipat ganda yang diharapkan.

Batch gradient descent menghitung gradien menggunakan seluruh dataset. Ini bagus untuk cembung, atau manifold kesalahan yang relatif mulus. Dalam hal ini, kami bergerak agak langsung menuju solusi optimal, baik lokal maupun global. Selain itu, keturunan gradien batch, diberi tingkat pembelajaran anil, pada akhirnya akan menemukan minimum yang terletak di lembah tariknya.

Stochastic gradient descent (SGD) menghitung gradien menggunakan sampel tunggal. Sebagian besar aplikasi SGD sebenarnya menggunakan minibatch dari beberapa sampel, untuk alasan yang akan dijelaskan sedikit kemudian. SGD bekerja dengan baik (Tidak baik, saya kira, tetapi lebih baik daripada batch gradient descent) untuk manifold kesalahan yang memiliki banyak maxima / minima lokal. Dalam hal ini, gradien yang agak ribut yang dihitung menggunakan jumlah sampel yang dikurangi cenderung menyentak model dari minimum lokal ke dalam wilayah yang diharapkan lebih optimal. Sampel tunggal benar-benar berisik, sementara minibatch cenderung rata-rata mengeluarkan sedikit kebisingan. Dengan demikian, jumlah brengsek berkurang saat menggunakan minibatch. Keseimbangan yang baik tercapai ketika ukuran minibatch cukup kecil untuk menghindari beberapa minimum lokal miskin, tetapi cukup besar sehingga tidak t menghindari global minimum atau minimum lokal berkinerja lebih baik. (Kebetulan, ini mengasumsikan bahwa minima terbaik memiliki daya tarik yang lebih besar dan lebih dalam, dan karenanya lebih mudah untuk jatuh ke dalam.)

Satu manfaat SGD adalah komputasi jauh lebih cepat. Kumpulan data besar seringkali tidak dapat disimpan dalam RAM, yang membuat vektorisasi menjadi jauh lebih efisien. Sebaliknya, setiap sampel atau kumpulan sampel harus dimuat, dikerjakan, hasilnya disimpan, dan sebagainya. SGD minibatch, di sisi lain, biasanya sengaja dibuat cukup kecil untuk dapat dikomputasi secara komputasi.

Biasanya, keunggulan komputasi ini dimanfaatkan dengan melakukan lebih banyak iterasi SGD, membuat lebih banyak langkah daripada penurunan gradien batch konvensional. Ini biasanya menghasilkan model yang sangat dekat dengan apa yang akan ditemukan melalui batch gradient descent, atau lebih baik.

Cara saya suka memikirkan cara kerja SGD adalah membayangkan bahwa saya memiliki satu poin yang mewakili distribusi input saya. Model saya berusaha mempelajari distribusi input tersebut. Sekitar distribusi input adalah area yang diarsir yang mewakili distribusi input dari semua minibatch yang mungkin saya dapat sampel. Biasanya asumsi yang adil bahwa distribusi input minibatch sangat dekat dengan distribusi input yang sebenarnya. Keturunan gradien batch, pada semua langkah, mengambil rute paling curam untuk mencapai distribusi input yang sebenarnya. SGD, di sisi lain, memilih titik acak dalam area yang diarsir, dan mengambil rute paling curam menuju titik ini. Namun, pada setiap iterasi, ia memilih titik baru. Rata-rata dari semua langkah ini akan mendekati distribusi input yang sebenarnya, biasanya cukup baik.

Jason_L_Bens
sumber
13
Dalam praktiknya, tidak ada yang menggunakan Batch Gradient Descent. Ini terlalu mahal secara komputasional untuk tidak terlalu banyak menghasilkan. (Keuntungannya adalah Anda benar-benar mengalah gradien "benar".) Ketika Anda memiliki fungsi kerugian sangat non-cembung Anda hanya perlu melangkah sebagian besar ke arah yang benar dan pada akhirnya Anda akan bertemu pada minimum lokal. Jadi, minibatch SGD.
sabalaba
@Jason_L_Bens Anda punya referensi (makalah atau teks online) di mana saya bisa membaca lebih lanjut tentang algoritma ini?
user110320
1
@ user110320 Bukan dari atas kepala saya, tidak, meskipun mereka adalah algoritma yang sangat umum, dan karenanya harus ada satu ton sumber daya yang tersedia pada topik dengan sedikit pencarian. Jika Anda mencari pendekatan umum, saya akan merekomendasikan membaca beberapa Arsitektur Mendalam Yoshua Bengio untuk AI. Di situlah saya memulai.
Jason_L_Bens
6

Seperti jawaban lain menyarankan, alasan utama untuk menggunakan SGD adalah untuk mengurangi biaya perhitungan gradien sementara sebagian besar masih mempertahankan arah gradien ketika dirata-ratakan atas banyak mini-batch atau sampel - yang pasti membantu membawa Anda ke minimum lokal.

  1. Mengapa minibatch berfungsi ?

Matematika di balik ini adalah bahwa, "benar" gradien dari fungsi biaya (gradien untuk kesalahan generalisasi atau untuk set sampel tak terhingga besar) adalah ekspektasi gradien atas data yang benar menghasilkan distribusi ; gradien aktual yang dihitung pada kumpulan sampel selalu merupakan perkiraan terhadap gradien sebenarnya dengan distribusi data empiris . pdatap^data

g=Epdata(J(θ)θ)
Keturunan gradien batch dapat membawa Anda kemungkinan "optimal" gradien diberikan semua sampel data Anda, itu bukan gradien "benar" sekalipun. Batch yang lebih kecil (minibatch) mungkin tidak seoptimal batch penuh, tetapi keduanya merupakan perkiraan - demikian juga minibatch sampel tunggal (SGD). Perbedaan antara kesalahan standar mereka berbanding terbalik dengan ukuran minibatch. Yaitu, mE p data(g(m))=E p data(J(θ)
SE(g^(n))SE(g^(m))=mn
Yaitu, pengurangan kesalahan standar adalah akar kuadrat dari peningkatan ukuran sampel. Persamaan di atas adalah untuk gradien yang dihitung dalam satu langkah penurunan gradien minibatch. Ketika Anda mengulangi langkah-langkah pembaruan gradien minibatch dan menggunakan semua sampel pelatihan akhirnya dalam satu zaman, Anda benar-benar menghitung rata-rata gradien berdasarkan pada semua sampel yang diberikan. Yaitu, untuk ukuran minibatch , Dari persamaan di atas, kita dapat menyimpulkan bahwa, dengan satu zaman, gradien rata-rata Anda dengan ukuran minibatch yang berbedamm
Ep^data(g^(m))=Ep^data(J(θ)θ)
m (dari satu ke batch penuh) memiliki kesalahan standar yang sama, dan yang lebih penting, mereka semua adalah perkiraan setia ke gradien "benar", yaitu, bergerak ke arah yang benar dari gradien "benar".
  1. Mengapa minibatch dapat bekerja lebih baik .

Pertama, minibatch membuat beberapa masalah pembelajaran dari yang secara teknis tidak dapat diatasi untuk ditangani karena berkurangnya permintaan komputasi dengan ukuran batch yang lebih kecil.

Kedua, mengurangi ukuran bets tidak berarti mengurangi akurasi gradien. Sampel pelatihan banyak memiliki banyak suara atau pencilan atau bias. Sebuah minibatch sampel acak dapat mencerminkan distribusi penghasil data yang sebenarnya lebih baik (atau tidak lebih buruk) daripada batch penuh asli. Jika beberapa iterasi pembaruan gradient minibatch memberi Anda estimasi yang lebih baik, secara keseluruhan hasil rata-rata satu zaman bisa lebih baik daripada gradien yang dihitung dari batch penuh.

Ketiga, minibatch tidak hanya membantu menangani sampel data yang tidak menyenangkan, tetapi juga membantu menangani fungsi biaya tidak menyenangkan yang memiliki banyak minimum lokal. Seperti yang disebutkan Jason_L_Bens, terkadang manifold kesalahan mungkin lebih mudah untuk menjebak gradien reguler ke dalam minimum lokal, sementara lebih sulit untuk menjebak gradien acak sementara yang dihitung dengan minibatch.

Akhirnya, dengan gradient descent, Anda tidak mencapai minimum global dalam satu langkah, tetapi mengulangi manifold erro. Gradient sebagian besar hanya memberi Anda arah untuk beralih. Dengan minibatch, Anda dapat beralih lebih cepat. Dalam banyak kasus, semakin banyak iterasi, semakin baik poin yang bisa Anda capai. Anda tidak benar-benar peduli di semua cuaca, titiknya optimal secara global atau bahkan secara lokal. Anda hanya ingin mencapai model yang masuk akal yang membawa Anda kesalahan generalisasi yang dapat diterima. Minibatch membuatnya lebih mudah.

Anda mungkin menemukan buku "Pembelajaran mendalam" oleh Ian Goodfellow, et al, memiliki diskusi yang cukup bagus tentang topik ini jika Anda membacanya dengan seksama.

Xiao-Feng Li
sumber
Untuk masalah optimasi cembung, apa yang Anda katakan baik-baik saja. Tetapi untuk menggunakan metode gradien pada fungsi non-cembung, Anda melewatkan alasan yang sangat kritis bahwa SGD lebih baik daripada batch GD. Lihat tanggapan saya, datacience.stackexchange.com/questions/16807/…
horaceT
@horaceT Terima kasih atas komentar Anda. Karena poin yang Anda sebutkan telah dijelaskan oleh Jason_L_Bens di atas dengan detail, saya tidak repot untuk mengulangi tetapi merujuk jawabannya di paragraf ketiga terakhir, dengan hormat. Untuk masalah optimasi gradient descent, non-cembung tercermin oleh minimum lokal termasuk titik pelana (lihat paragraf ketiga terakhir); dan demi uraian, jawaban saya menggambarkan SGD sebagai minibatch tetapi dengan ukuran batch 1 (lihat paragraf ketiga).
Xiao-Feng Li
3

Bagi saya, batch gradient menyerupai lean gradient. Dalam lean gradient, ukuran bets dipilih sehingga setiap parameter yang harus diperbarui, juga bervariasi secara independen, tetapi tidak harus ortogonal, dalam bets. Misalnya, jika kumpulan berisi 10 percobaan, 10 baris, maka dimungkinkan untuk membentuk kolom independen. 10 baris memungkinkan pembaruan, tetapi tidak ortogonal, independen dari 512 parameter.2101=512

Sven Ahlinder
sumber