Apakah kita memerlukan gradient descent untuk menemukan koefisien model regresi linier?

31

Saya mencoba mempelajari pembelajaran mesin menggunakan materi Coursera . Dalam kuliah ini, Andrew Ng menggunakan algoritma gradient descent untuk menemukan koefisien model regresi linier yang akan meminimalkan fungsi kesalahan (fungsi biaya).

Untuk regresi linier, apakah kita perlu gradient descent? Tampaknya saya dapat secara analitis membedakan fungsi kesalahan dan menetapkannya ke nol untuk menyelesaikan koefisien; Apakah itu benar?

regression machine-learning linear-model gradient-descent Pemenang
sumber
3
Model linier telah ditangani dengan baik sejak 1700-an. Ada banyak cara untuk menanganinya yang tidak memerlukan gradient descent (GD). Ada model nonlinear di mana sebagian besar metode tersebut jatuh datar di wajah mereka. Andrew membuat Anda menggunakan metode yang tidak dikenal tetapi sangat berguna untuk mengatasi masalah yang sangat sederhana sehingga Anda dapat men-debug pendekatan Anda. Ketika Anda baik dengan metode ini, Anda dapat menerapkannya pada masalah nonlinier yang menakjubkan dimana GD adalah satu-satunya metode untuk mendapatkan hasil.
EngrStudent
10
Tidak, Anda tidak harus menggunakan pendekatan seperti gradient descent (itu bukan satu-satunya metode optimasi, dalam hal apa pun). Anda memang dapat secara analitis menyelesaikannya, seperti yang Anda sarankan; Anda membedakan sehubungan dengan setiap parameter, sehingga Anda mendapatkan satu persamaan per parameter. Tetapi berguna untuk memecahkan masalah sederhana yang bisa dilakukan dengan cara lain; jika Anda sudah tahu jawabannya, Anda bisa yakin ketika mendapatkan jawaban yang benar dengan gradient descent.
Glen_b -Reinstate Monica
Jika fungsi biaya adalah penalti kuadrat ('jarak') biasa, ada solusi bentuk tertutup. Namun, penurunan gradien umumnya jauh lebih cepat, itu sebabnya biasanya digunakan.
aginensky
Selain itu, gradient descent dapat digunakan untuk menemukan solusi numerik untuk masalah-masalah yang secara analitik tidak dapat dipecahkan. Saya akan curiga bahwa dia menggunakan gradient descent sejak awal untuk membiasakan diri dengannya. Saya percaya dia kemudian menggunakan gradient descent dengan jaring saraf. Tak perlu dikatakan situasi jaringan syaraf lebih rumit. Saya pikir dari situasi pedagogis, setelah melihatnya sebelumnya, dengan model linier, penurunan gradien untuk digunakan dengan jaring saraf tampaknya lebih masuk akal.
aginensky
3
Terima kasih telah memposting tautan ke video Andre Ng yang saya tonton beberapa. Saya sudah mengetahuinya, meskipun tidak sampai sejauh ini, tetapi menakutkan untuk melihat apa yang dipelajari oleh kebanyakan orang yang belajar optimasi, belum lagi apa yang setidaknya beberapa dari mereka pelajari tentang komputasi statistik. Gene Golub, pelopor dalam komputasi dan menggunakan SVD, akan berguling di kuburnya jika dia tahu apa yang sedang diajarkan sekarang di Stanford Computer Science Dept. Video "terlucu 'adalah youtube.com/watch?v=B3vseKmgi8E , yang merekomendasikan dan membandingkan 2 algoritma TERBURUK untuk kuadrat terkecil
Mark L. Stone

Jawaban:

43

Kotak Linear Least dapat diselesaikan dengan

0) Menggunakan pemecah kuadrat linier kualitas tinggi, berdasarkan SVD atau QR, seperti yang dijelaskan di bawah ini, untuk kuadrat linear tak terbatas, atau berdasarkan versi Quadratic Programming atau Optimasi Konic untuk kuadrat terkecil yang terikat atau dibatasi secara linear, seperti dijelaskan di bawah ini. Pemecah masalah seperti itu sudah dikalengkan, sangat teruji, dan siap digunakan - gunakanlah.

1) SVD, yang merupakan metode yang paling dapat diandalkan dan akurat secara numerik, tetapi juga membutuhkan lebih banyak komputasi daripada alternatif. Dalam MATLAB, solusi SVD dari masalah kuadrat linier tak terbatas A * X = b adalah pinv (A) * b, yang sangat akurat dan dapat diandalkan.

2) QR, yang cukup dapat diandalkan dan akurat secara numerik, tetapi tidak sebanyak SVD, dan lebih cepat dari SVD. Dalam MATLAB, solusi QR dari masalah kuadrat linier tak terbatas A * X = b adalah A \ b, yang cukup akurat dan dapat diandalkan, kecuali ketika A dikondisikan, yaitu, memiliki nomor kondisi yang besar. A \ b lebih cepat untuk dihitung daripada pinv (A) * b, tetapi tidak dapat diandalkan atau akurat.

3) Membentuk persamaan Normal (TERRIBLE dari sudut pandang keandalan dan akurasi numerik, karena menguadratkan angka kondisi, yang merupakan hal yang sangat buruk untuk dilakukan) dan

3a) penyelesaian dengan Cholesky Factorization (tidak baik)

3b) secara eksplisit pembalik matriks (MENGERIKAN)

4) Memecahkan sebagai masalah Pemrograman Quadratic atau masalah Orde Kerucut Kedua

4a) Memecahkan menggunakan perangkat lunak Pemrograman Kuadratik berkualitas tinggi Ini dapat diandalkan dan akurat secara numerik, tetapi membutuhkan waktu lebih lama dari SVD atau QR. Namun, mudah untuk menambahkan batasan linier terikat atau umum, atau hukuman linear atau kuadrat (dua norma) atau ketentuan regularisasi ke fungsi tujuan, dan masih menyelesaikan masalah menggunakan perangkat lunak Pemrograman Quadratic.

4b) Memecahkan sebagai masalah Kerucut Orde Kedua menggunakan perangkat lunak Conic Optimization berkualitas tinggi. Keterangannya sama dengan perangkat lunak Pemrograman Quadratic, tetapi Anda juga dapat menambahkan batasan linier terikat atau umum dan batasan kerucut lainnya atau istilah fungsi tujuan, seperti hukuman atau ketentuan regularisasi dalam berbagai norma.

5) Memecahkan menggunakan perangkat lunak optimasi tujuan umum nonlinear berkualitas tinggi. Ini mungkin masih bekerja dengan baik, tetapi secara umum akan lebih lambat dari Quadratic Programming atau Conic Optimization software, dan mungkin tidak cukup dapat diandalkan. Namun, dimungkinkan untuk memasukkan tidak hanya kendala linear terikat dan umum, tetapi juga kendala nonlinier ke dalam optimasi kuadrat terkecil. Juga, dapat digunakan untuk kuadrat terkecil nonlinier, dan jika istilah nonlinier lainnya ditambahkan ke fungsi objektif.

6) Memecahkan menggunakan algoritma optimasi non-linear tujuan umum yang buruk -> JANGAN PERNAH MELAKUKANNYA.

7) Selesaikan dengan menggunakan algoritma optimisasi tujuan umum non-linear YANG TERBURUK YANG MUNGKIN, yaitu gradient descent. Gunakan ini hanya jika Anda ingin melihat seberapa buruk dan tidak dapat diandalkannya suatu metode solusi. Jika seseorang memberi tahu Anda untuk menggunakan gradient descent untuk menyelesaikan masalah linear least square

7 i) Pelajari tentang komputasi statistik dari seseorang yang mengetahui sesuatu tentang itu

7 ii) Pelajari pengoptimalan dari seseorang yang mengetahui sesuatu tentangnya.

Mark L. Stone
sumber
Posting yang bagus, mengapa Anda berpikir bahwa Cholesky tidak bagus mengingat sistem Anda adalah PD? (dan tidak dengan angka kondisi konyol) BTW, saya pikir Anda ingin mengatakan (atau menambahkan) gagasan invers umum (kebanyakan digunakan untuk tujuan pendidikan) baik pada titik "SVD" atau "secara eksplisit membalikkan".
usεr11852 mengatakan Reinstate Monic
2
BTW, sangat konyol betapa seringnya matriks dengan angka kondisi sangat tinggi dihasilkan, terutama oleh massa yang tidak dicuci (yaitu, mayoritas orang yang melakukan linear kuadrat terkecil, terutama mengingat demokratisasi akses), yang tidak terbiasa dengan hal itu.
Mark L. Stone
1
mldivide, yaitu. backslash, yaitu, \ menggunakan QR ketika m ~ = n (kuadrat terkecil), seperti yang saya nyatakan dalam kalimat ke-2 paragraf saya (2) di atas. Anda akan terkejut betapa banyak omong kosong yang ada di MATLAB - tidak hanya di kotak peralatan, beberapa di antaranya benar-benar mengerikan, tetapi pada tingkat yang lebih rendah di beberapa fungsi inti juga.
Mark L. Stone
1
@ MarkL.Stone, jawaban yang bagus! bisa tolong jelaskan sedikit lebih banyak tentang mengapa itu tidak disarankan untuk menggunakan keturunan Gradient untuk memecahkan kuadrat terkecil! (Dalam pemahaman saya itu hanya pendekatan berulang dibandingkan dengan yang lain (pendekatan solusi arah) yang telah Anda sebutkan di atas). Selain itu, dapatkah Anda juga mengomentari masalah: "jika saya memiliki n> = 30.000 fitur untuk suatu masalah, metode persamaan Normal akan sangat lambat karena pembalikan matriks n * n akan mengerikan! Di sisi lain, GD akan bekerja dalam hal ini huruf cantik! ada pemikiran tentang bagaimana SVD & QR akan melakukan " setiap saran akan sangat membantu.
anu
1
@ anu Hanya gunakan gradient descent sebagai pilihan terakhir. dan itu hanya akan terjadi jika masalahnya terlalu besar untuk diselesaikan oleh SVD atau QR. Jangan pernah membentuk Persamaan Normal, apalagi secara eksplisit membalikkan matriks untuk menyelesaikan persamaan Normal, TIDAK PERNAH. 30.000 fitur tidak terdengar sangat banyak untuk saat ini.
Mark L. Stone
0

Menemukan koefisien model linier secara teknis adalah proses menemukan solusi untuk seperangkat Persamaan Linear .

Untuk menghitung solusi semacam itu, banyak yang optimization techniquestelah dikembangkan dan Gradient Descentmerupakan salah satunya.
Dengan demikian, Keturunan Gradien bukan satu-satunya cara untuk melakukan itu.

Andrew Ng menggunakannya dalam kursus ini karena mudah dimengerti, tanpa berurusan dengan Aljabar Linear dan Komputasi Angka.

Vikas Raturi
sumber
Meskipun tidak salah, saya pikir jawaban Anda melewatkan gambaran yang lebih besar dengan berfokus pada kasus non-standar. The Sebagian besar dari model regresi linier dilengkapi dengan menggunakan QR menggunakan solusi bentuk tertutup dekomposisi. GD-gradient decent- digunakan sebagai contoh untuk memperkenalkan metode yang lebih maju (mis. SGD- stokastik GD).
usεr11852 mengatakan Reinstate Monic
Bisakah Anda menguraikan apa itu dekomposisi QR?
Victor
3
Ax=bA=QRRQAx=b⇒QRx=b⇔Rx=QTbRQTQ=ISGD. Karena kebanyakan orang tidak memiliki matriks yang sangat besar, dekomposisi QR lebih baik. Secara umum dekomposisi QR telah membentuk dunia numerik; SIAM memilihnya sebagai salah satu dari 10 algoritma terbaik abad ke-20.
usεr11852 mengatakan Reinstate Monic
@ usεr11852 ya tentu saja. Itu karena, saya ingin menjaga jawabannya tetap sederhana, sehingga untuk menghindari konsep seperti dekomposisi QR, tetap relevan dengan domain tingkat kursus Ng.
Vikas Raturi
3
QR adalah salah satu dari 10 algoritma terbaik abad ke-20. Tetapi waktu terus berjalan, dan meskipun algoritma yang efektif untuk menghitung SVD kembali ke tahun 1960-an, Anda harus melihat pentingnya area aplikasi. Karena itu saya percaya SVD adalah algoritma TOP abad ke-21. Sejujurnya, pernahkah Anda mendengar tentang QR yang digunakan untuk merekomendasikan film? Tidak, SVD digunakan untuk aplikasi kritis itu. SVD jelas merupakan algoritme pilihan ketika Twitter mengirimkan rekomendasi yang tidak diminta kepada kakek tua konservatif tentang selebritas remaja mana yang harus mereka ikuti. Mari kita lihat QR melakukan itu !!!
Mark L. Stone