Memecahkan parameter regresi dalam bentuk tertutup vs gradient descent

Dalam kursus pembelajaran mesin Andrew Ng , ia memperkenalkan regresi linier dan regresi logistik, dan menunjukkan bagaimana menyesuaikan parameter model menggunakan gradient descent dan metode Newton.

Saya tahu gradient descent dapat berguna dalam beberapa aplikasi pembelajaran mesin (misalnya, backpropogation), tetapi dalam kasus yang lebih umum apakah ada alasan mengapa Anda tidak akan menyelesaikan parameter dalam bentuk tertutup - yaitu, dengan mengambil turunan dari fungsi biaya dan penyelesaian melalui Kalkulus?

Apa keuntungan menggunakan algoritma iteratif seperti gradient descent di atas solusi bentuk-tertutup secara umum, ketika tersedia?

regression machine-learning logistic gradient-descent Jeff
sumber

Saya tidak berpikir ada solusi bentuk tertutup untuk MLE dari parameter regresi di sebagian besar glms (misalnya regresi logistik). Regresi linier dengan kesalahan normal adalah satu pengecualian.

Makro

Menarik ... Apakah ini berarti paket statistik yang berbeda mungkin memberikan jawaban yang berbeda untuk regresi logistik tergantung pada, misalnya, pengaturan parameter awal, jumlah iterasi, beberapa minima lokal, dll. - atau apakah ada prosedur konvensional bahwa semua paket statistik yang baik akan mengikuti? (Meskipun saya yakin ada perbedaan, jika memang ada, sangat kecil dalam kebanyakan kasus)

Jeff

(+1) Untuk pertanyaan dan komentar Anda, Jeff. GLM yang menggunakan tautan kanonik (seperti regresi logistik) mendapat manfaat dari sifat-sifat cembung yang bagus. Mungkin ada lebih dari satu algoritma untuk memecahkan masalah seperti itu, tetapi hasil dasarnya adalah bahwa (modulo beberapa detail yang cukup kecil), algoritma numerik yang diterapkan dengan baik akan memberikan hasil yang konsisten di antara mereka.

kardinal

Saya pribadi tidak suka kursus Andrew Ng karena telah membuat orang percaya bahwa Regresi Linier adalah "pembelajaran mesin".

Digio

Terkait: Apakah kita memerlukan gradient descent untuk menemukan koefisien dari model regresi linier

Franck Dernoncourt

Jawaban:

Kecuali jika solusi bentuk tertutup sangat mahal untuk dihitung, umumnya adalah cara yang harus diambil ketika tersedia. Namun,

Untuk sebagian besar masalah regresi nonlinier tidak ada solusi bentuk tertutup.
Bahkan dalam regresi linier (salah satu dari beberapa kasus di mana solusi bentuk tertutup tersedia), mungkin tidak praktis untuk menggunakan formula. Contoh berikut menunjukkan satu cara di mana ini bisa terjadi.

Untuk regresi linier pada model bentuk , di mana adalah matriks dengan peringkat kolom penuh, solusi kuadrat terkecil, $y=X\beta$ $X$

$\hat{\beta} = \arg \min \| X \beta -y \|_{2}$

diberikan oleh

$\hat{\beta}=(X^{T}X)^{-1}X^{T}y$

Sekarang, bayangkan adalah matriks yang sangat besar tetapi jarang. misalnya mungkin memiliki 100.000 kolom dan 1.000.000 baris, tetapi hanya 0,001% dari entri dalam adalah nol. Ada struktur data khusus untuk menyimpan hanya entri bukan nol dari matriks jarang tersebut. $X$ $X$ $X$

Bayangkan juga kita kurang beruntung, dan adalah matriks yang cukup padat dengan persentase entri bukan-nol yang jauh lebih tinggi. Menyimpan angka 100.000 dengan 100.000 elemen padat akan membutuhkan angka floating point (pada 8 byte per angka, ini mencapai 80 gigabyte.) Ini tidak praktis untuk disimpan pada apa pun tapi superkomputer. Lebih lanjut, kebalikan dari matriks ini (atau lebih umum merupakan faktor Cholesky) juga cenderung memiliki sebagian besar entri yang bukan nol. $X^{T}X$ $X^{T}X$ $1 \times 10^{10}$

Namun, ada metode iteratif untuk memecahkan masalah kuadrat terkecil yang tidak memerlukan kapasitas penyimpanan yang lebih dari , , dan dan tidak pernah secara eksplisit membentuk produk matriks . $X$ $y$ $\hat{\beta}$ $X^{T}X$

Dalam situasi ini, menggunakan metode berulang jauh lebih efisien secara komputasi daripada menggunakan solusi bentuk tertutup untuk masalah kuadrat terkecil.

Contoh ini mungkin tampak sangat besar. Namun, masalah kuadrat terkecil berukuran kecil ini secara rutin diselesaikan dengan metode berulang pada komputer desktop dalam penelitian tomografi seismik.

Brian Borchers
sumber

Saya harus menyebutkan bahwa ada juga masalah akurasi numerik yang dapat membuat penggunaan solusi bentuk tertutup untuk masalah kuadrat terkecil tidak dapat disarankan. Namun, ini akan membutuhkan diskusi tentang pengondisian yang tampaknya mungkin berada di luar pemahaman poster asli saat ini.

Brian Borchers

tolong jangan ragu untuk mengirim jawaban karena Anda tidak berpikir saya akan memahaminya. pertama - tidak ada salahnya untuk memberikan lebih banyak informasi, bahkan jika perlu beberapa riset untuk memahami itu. kedua - model stackexchange mengasumsikan bahwa pertanyaan dan jawaban ini akan bermanfaat bagi orang lain di masa depan. dengan kata lain, jangan membodohi jawaban Anda berdasarkan seberapa banyak Anda pikir OP tahu, atau Anda akan merugikan orang lain.

Jeff

@Brian, perasaan saya adalah komentar Anda menyentuh inti masalah dan sedikit berselisih dengan kalimat pertama dalam jawabannya. Saya tidak berpikir setiap kuadrat-software (dalam pikiran kanan) mempekerjakan solusi bentuk tertutup. :)

kardinal

Dalam praktik kardinal, yang terbaik adalah menggunakan faktorisasi QR atau SVD untuk memecahkan masalah skala kuadrat terkecil. Saya berpendapat bahwa solusi menggunakan salah satu faktorisasi ortogonal ini juga merupakan "solusi bentuk tertutup" dibandingkan dengan menggunakan teknik berulang seperti LSQR. Saya tidak menyelidiki hal ini dalam jawaban saya karena itu dengan sia-sia menarik perhatian dari poin utama saya.

Brian Borchers

Pengondisian buruk? Solusi formulir buku teks tertutup? Saya suka bau nomor kondisi kuadrat di pagi hari. Punya nomor kondisi besar? Mengapa tidak membuatnya persegi dan membuatnya lebih besar? Punya jumlah kondisi yang tidak terlalu besar? Mengapa tidak membuatnya persegi dan menjadi besar.

Mark L. Stone

Ada beberapa posting tentang pembelajaran mesin (ML) dan regresi. ML tidak diperlukan untuk menyelesaikan kuadrat terkecil biasa (OLS), karena melibatkan operasi sandwiching satu langkah untuk memecahkan sistem persamaan linear - yaitu, . Fakta bahwa semuanya linier berarti bahwa hanya operasi satu langkah yang diperlukan untuk menyelesaikan koefisien. Regresi logistik didasarkan pada pemaksimalan fungsi kemungkinan , yang dapat diselesaikan dengan menggunakan Newton-Raphson, atau metode pendakian gradien ML lainnya, metaheuristik (pendakian bukit, algoritme genetik, kawanan intelijen, optimisasi koloni semut, dll) . $\boldsymbol{\beta}=(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$ $L=\prod_i{p_i}$

Mengenai kekikiran, penggunaan ML untuk OLS akan sia-sia karena pembelajaran berulang tidak efisien untuk memecahkan OLS.

Sekarang, kembali ke pertanyaan nyata Anda tentang pendekatan derivatif vs ML untuk memecahkan masalah berbasis gradien. Secara khusus, untuk regresi logistik, Newton-Raphson's gradient descent (berbasis-turunan) pendekatan yang umum digunakan. Newton-Raphson mengharuskan Anda mengetahui fungsi obyektif dan turunan parsialnya setiap parameter (kontinu dalam batas dan dapat dibedakan). ML sebagian besar digunakan ketika fungsi objektif terlalu kompleks ("narly") dan Anda tidak tahu turunannya. Misalnya, jaringan syaraf tiruan (JST) dapat digunakan untuk memecahkan masalah perkiraan fungsi atau masalah klasifikasi terawasi ketika fungsi tersebut tidak diketahui. Dalam hal ini, JST adalah fungsinya.

Jangan membuat kesalahan dengan menggunakan metode ML untuk menyelesaikan masalah regresi logistik, hanya karena Anda bisa. Untuk logistik, Newton-Raphson sangat cepat dan merupakan teknik yang tepat untuk menyelesaikan masalah. ML umumnya digunakan ketika Anda tidak tahu apa fungsinya. (Omong-omong, JST berasal dari bidang kecerdasan komputasi, dan bukan ML).

JoleT
sumber