Mengapa gradient descent diperlukan?

10

Ketika kita dapat membedakan fungsi biaya dan menemukan parameter dengan menyelesaikan persamaan yang diperoleh melalui diferensiasi parsial sehubungan dengan setiap parameter dan mencari tahu di mana fungsi biaya minimum. Juga saya pikir mungkin untuk menemukan banyak tempat di mana turunannya nol, dengan demikian kita dapat memeriksa semua tempat tersebut dan dapat menemukan minimum global

mengapa gradient descent dilakukan sebagai gantinya?

Niranjan Kotha
sumber
2
Bagaimana cara seseorang menetapkan turunannya menjadi 0 untuk suatu fungsi? Dengan algoritma, seperti gradient descent.
Cliff AB
3
Anda dapat menganggap gradient descent sebagai metode yang digunakan untuk menyelesaikan persamaan yang Anda maksud. Jika Anda berada di bawah keyakinan bahwa Anda secara umum dapat menyelesaikan persamaan tersebut dengan manipulasi aljabar yang cerdas, saya mengundang Anda untuk mencoba melakukannya untuk regresi logistik.
Matthew Drury
3
Kemungkinan duplikat Memecahkan parameter regresi dalam bentuk tertutup vs penurunan gradien
Glen_b -Reinstate Monica
1
Lihat juga stackoverflow.com/questions/26804656/…
Glen_b -Reinstate Monica
Anda tidak dapat menyelesaikan semuanya secara analitis. Bahkan jika Anda bisa, jika ada katakan, jumlah nol yang tak terhitung, maka Anda akan membutuhkan waktu lama untuk memeriksa semua poin penting.
Pinocchio

Jawaban:

8

Bahkan dalam kasus, katakanlah, model linier, di mana Anda memiliki solusi analitis, mungkin masih lebih baik menggunakan pemecah iteratif seperti itu.

Sebagai contoh, jika kita mempertimbangkan regresi linier, solusi eksplisit membutuhkan pembalikan matriks yang memiliki kompleksitas . Ini menjadi penghalang dalam konteks big data.O(N3)

Juga, banyak masalah dalam pembelajaran mesin adalah cembung, jadi menggunakan gradien memastikan bahwa kita akan sampai ke ekstrem.

Seperti yang telah ditunjukkan, masih ada masalah non-cembung yang relevan, seperti jaringan saraf, di mana metode gradien (backpropagation) menyediakan pemecah yang efisien. Sekali lagi ini sangat relevan untuk kasus pembelajaran mendalam.

jpmuc
sumber
2
Membalikkan sebuah matriks agak sulit di sini karena dekomposisi QR dengan pivot parsial lebih akurat dan lebih cepat, tapi ya, QR masih . Saya setuju bahwa untuk sistem yang cukup besar (mis.> 10.000 variabel) yang dapat mulai menjadi masalah. Kemudian, pendekatan teknologi tinggi untuk memperkirakan solusi dengan metode ruang bagian Krylov iteratif (misalnya, gradien konjugat, GMRES). O(n3)
Matthew Gunn
1
Suatu hal yang mungkin membingungkan beberapa orang adalah bagaimana menyelesaikan sistem linear masalah optimasi? Jawabannya tentu saja adalah bahwa penyelesaian sistem linear dapat dibingkai ulang sebagai meminimalkan tujuan kuadratik. Beberapa metode iteratif untuk menyelesaikan sistem linear lebih mudah dipahami dari perspektif bahwa mereka meminimalkan tujuan kuadratik secara iteratif. (Misalnya, metode ruang bagian Krylov konjugat arah langkah gradien didasarkan pada gradien ... itu terkait longgar dengan gradient descent.)
Matthew Gunn
12

Keturunan gradien tidak diperlukan. Ternyata penurunan gradien seringkali merupakan algoritma optimasi yang sangat tidak efisien! Untuk metode berulang, sering kali mungkin untuk menemukan arah yang lebih baik untuk bergerak daripada kemiringan terjal.

Tapi itu sedikit jawaban yang terbalik. Pertanyaan Anda seharusnya, "mengapa kita membutuhkan metode berulang?" Misalnya. mengapa tidak langsung menuju solusi jika masalahnya cembung, kondisi Slater berlaku, dan kondisi urutan pertama diperlukan dan kondisi yang memadai untuk optimal? Artinya, ketika solusinya dapat digambarkan sebagai solusi untuk sistem persamaan, mengapa tidak hanya memecahkan sistem? Jawabannya adalah:

  • Untuk masalah optimisasi kuadrat, kondisi urutan pertama adalah sistem persamaan linear, dan kita dapat langsung menuju solusi karena sistem linier dapat diselesaikan secara efisien! Kami tidak menggunakan kondisi urutan pertama dan memecahkan sistem (misalnya. Dengan QR dekomposisi, peringatan di bawah ini).
  • Lebih umum lagi, kondisi urutan pertama mendefinisikan sistem persamaan non-linear dan sistem non-linear mungkin cukup sulit untuk dipecahkan! Bahkan, cara Anda sering menyelesaikan sistem persamaan non-linear secara numerik adalah Anda merumuskannya kembali sebagai masalah optimisasi ...
  • Untuk sistem linier yang sangat besar , menyelesaikan sistem secara langsung dengan dekomposisi QR dan pivoting parsial menjadi tidak layak. Apa yang orang-orang lakukan?! Metode berulang! (mis. metode ruang bagian Krylov yang berulang ...)
Matthew Gunn
sumber
7

Dalam kalkulus 101 kita belajar tentang bagaimana mengoptimalkan suatu fungsi menggunakan "metode analitik": kita hanya perlu mendapatkan turunan dari fungsi biaya dan mengatur turunan ke 0 lalu menyelesaikan persamaannya. Ini benar-benar masalah mainan dan hampir tidak akan pernah terjadi di dunia nyata.

Dalam dunia nyata, banyak fungsi biaya tidak memiliki turunan di mana-mana (Selanjutnya, fungsi biaya mungkin terpisah dan tidak memiliki turunan sama sekali). Selain itu, bahkan Anda dapat menghitung turunannya, Anda tidak bisa menyelesaikan persamaannya secara analitis (misalnya, pikirkan tentang bagaimana menyelesaikan analitik? Saya dapat memberi tahu Anda jawaban numerik adalah , tetapi tidak tahu solusi analitis). Kita harus menggunakan beberapa metode numerik (periksa mengapa di sini pada kasus polinomial Abel Ruffin Theorem ).x7+x352+ex+log(x+x2)+1/x=0x=1.4786

Metode berulang sangat bagus untuk digunakan, dan sangat intuitif untuk dipahami. Misalkan Anda ingin mengoptimalkan satu fungsi, alih-alih menyelesaikan persamaan dan mendapatkan jawabannya, Anda mencoba meningkatkan jawaban Anda dengan jumlah iterasi / langkah-langkah setelah iterasi yang cukup, Anda akan mendapatkan jawaban yang dekat dengan "jawaban yang benar". Katakanlah jika Anda menggunakan kalkulus untuk meminimalkan , Anda langsung mendapatkan , tetapi menggunakan metode numerik, Anda mungkin mendapatkan .f(x)=x2x=0x=1.1234×1020

Sekarang, penting untuk memahami bagaimana metode berulang ini bekerja. Konsep kuncinya adalah mengetahui cara memperbarui parameter input Anda untuk mendapatkan solusi yang lebih baik. Misalkan Anda ingin meminimalkan(perhatikan fungsi biaya ini tidak dapat dibedakan di mana-mana, tetapi dapat dibedakan ada di "sebagian besar tempat", ini cukup baik bagi kami, karena kami tahu cara memperbarui di "sebagian besar tempat".), saat ini Anda berada di , dan biayanya , sekarang Anda ingin memperbarui untuk membuat fungsi objektif lebih kecil. Bagaimana Anda akan melakukannya? Anda mungkin mengatakan saya ingin mengurangi keduanya , tetapi mengapa? Bahkan Anda menggunakan implisitf(x1,x2)=x12+x22+|x1+x2|(1,1)4.0(x1,x2)x1 x2konsep gradien "mengubah sejumlah kecil , apa yang akan terjadi pada ". xy. Dalam , turunannya adalah , jadi gradien negatif dikali laju pembelajaran katakan , adalah , jadi kami memperbarui solusi kami dari hingga yang mana biayanya lebih baik.(1,1)(3,3)α=0.0011 , 1 ( 0,997 , 0,997 )(0.003,0.003)1,1(0.997,0.997)

Haitao Du
sumber
informasi lebih lanjut dapat ditemukan di pos terkait
Haitao Du
4

Pendekatan yang Anda sebutkan hanya dapat digunakan untuk menyelesaikan satu set persamaan linear misalnya dalam kasus regresi linier, tetapi katakan untuk menyelesaikan satu set persamaan non linear, dalam kasus seperti jaringan saraf dengan aktivasi sigmoid, gradient descent adalah pendekatan pergi untuk. Jadi Gradient Descent adalah pendekatan yang lebih umum.

Bahkan untuk persamaan linear, ukuran matriks yang diberikan oleh himpunan persamaan linear sangat besar, dan bisa sulit untuk membatasi kebutuhan memori.

Amitoz Dandiana
sumber