Mengapa metode Newton tidak banyak digunakan dalam pembelajaran mesin?

Ini adalah sesuatu yang telah mengganggu saya untuk sementara waktu, dan saya tidak dapat menemukan jawaban yang memuaskan secara online, jadi begini:

Setelah meninjau satu set ceramah tentang optimasi cembung, metode Newton tampaknya menjadi algoritma yang jauh lebih unggul daripada gradient descent untuk menemukan solusi optimal secara global, karena metode Newton dapat memberikan jaminan untuk solusinya, itu affine invariant, dan sebagian besar semuanya menyatu dalam langkah yang jauh lebih sedikit. Mengapa algoritma optimisasi orde dua, seperti metode Newton tidak banyak digunakan sebagai keturunan gradien stokastik dalam masalah pembelajaran mesin?

Gradient descent memaksimalkan fungsi menggunakan pengetahuan turunannya. Metode Newton, algoritma pencarian akar, memaksimalkan fungsi menggunakan pengetahuan turunan keduanya. Itu bisa lebih cepat ketika turunan kedua diketahui dan mudah untuk dihitung (algoritma Newton-Raphson digunakan dalam regresi logistik). Namun, ekspresi analitik untuk turunan kedua sering rumit atau tidak dapat dilaksanakan, membutuhkan banyak perhitungan. Metode numerik untuk menghitung turunan kedua juga membutuhkan banyak perhitungan - jika nilai diperlukan untuk menghitung turunan pertama, diperlukan untuk turunan kedua.$N$$N^2$

Lebih banyak orang harus menggunakan metode Newton dalam pembelajaran mesin *. Saya mengatakan ini sebagai seseorang dengan latar belakang dalam optimasi numerik, yang telah mencoba-coba pembelajaran mesin selama beberapa tahun terakhir.

Kelemahan dalam jawaban di sini (dan bahkan dalam literatur) tidak menjadi masalah jika Anda menggunakan metode Newton dengan benar. Selain itu, kelemahan yang penting juga memperlambat penurunan gradien jumlah yang sama atau lebih, tetapi melalui mekanisme yang kurang jelas.

• Menggunakan pencarian garis dengan kondisi Wolfe atau menggunakan atau mempercayai daerah mencegah konvergensi ke poin sadel. Implementasi gradient descent yang tepat harus melakukan ini juga. The kertas dirujuk dalam jawaban Cam.Davidson.Pilon ini menunjukkan masalah dengan "metode Newton" di hadapan poin pelana, tetapi memperbaiki mereka menganjurkan juga merupakan metode Newton.

• Menggunakan metode Newton tidak memerlukan pembangunan seluruh (padat) Hessian; Anda dapat menerapkan kebalikan dari Hessian ke vektor dengan metode berulang yang hanya menggunakan produk-produk matriks-vektor (misalnya, metode Krylov seperti gradien konjugat). Lihat, misalnya, metode wilayah kepercayaan CG-Steihaug.

• Anda dapat menghitung produk-produk vektor-matriks Hessian secara efisien dengan menyelesaikan dua persamaan adjoint orde tinggi dari bentuk yang sama dengan persamaan adjoint yang sudah digunakan untuk menghitung gradien (misalnya, karya dua langkah propagasi balik dalam pelatihan jaringan saraf).

• Pengondisian yang buruk memperlambat konvergensi dari pemecah linear yang berulang, tetapi juga memperlambat penurunan gradien secara merata atau lebih buruk. Menggunakan metode Newton daripada gradient descent menggeser kesulitan dari tahap optimisasi nonlinier (di mana tidak banyak yang dapat dilakukan untuk memperbaiki situasi) ke tahap aljabar linier (di mana kita dapat menyerang dengan seluruh arsenal teknik prakondisi aljabar linear numerik).

• Juga, perhitungan bergeser dari "banyak langkah murah" ke "beberapa langkah mahal", membuka lebih banyak peluang untuk paralelisme pada tingkat sub-langkah (aljabar linier).

Untuk informasi latar belakang tentang konsep-konsep ini, saya merekomendasikan buku "Numerical Optimization" oleh Nocedal dan Wright.

* Tentu saja, metode Newton tidak akan membantu Anda dengan L1 atau penginderaan terkompresi / sparsity serupa lainnya yang mempromosikan fungsi penalti, karena tidak memiliki kelancaran yang diperlukan.

Saya baru-baru ini belajar sendiri - masalahnya adalah proliferasi titik sadel di ruang dimensi tinggi, yang ingin disatukan oleh metode Newton. Lihat artikel ini: Mengidentifikasi dan menyerang masalah titik sadel dalam optimasi non-cembung dimensi tinggi .

Memang rasio jumlah titik sadel ke minimum lokal meningkat secara eksponensial dengan dimensi N.

Sementara dinamika penurunan gradien diusir dari titik sadel ke kesalahan yang lebih rendah dengan mengikuti arah kelengkungan negatif, ... metode Newton tidak memperlakukan titik sadel dengan tepat; sebagaimana didalilkan di bawah ini, sadel-poin malah menjadi menarik di bawah dinamika Newton.

Kombinasi dua alasan:

• Metode Newton menarik untuk poin pelana;
• poin sadel umum dalam pembelajaran mesin, atau bahkan optimasi multivariabel.

Lihatlah fungsi

$$f=x^2-y^2$$

Jika Anda menerapkan metode multivarian Newton , Anda mendapatkan yang berikut ini.

$$\mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{H}f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n)$$

Mari kita dapatkan Hessian :

$$\mathbf{H}= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

$$\mathbf{H}= \begin{bmatrix} 2 & 0 \\[2.2ex] 0 & -2 \end{bmatrix}$$

Balikkan:

$$[\mathbf{H} f]^{-1}= \begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix}$$

Dapatkan gradien:

$$\nabla f=\begin{bmatrix} 2x \\[2.2ex] -2y \end{bmatrix}$$

Dapatkan persamaan final:

$$\mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_{n+1} = \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n -\begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix} \begin{bmatrix} 2x_n \\[2.2ex] -2y_n \end{bmatrix}= \mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_n - \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n = \begin{bmatrix} 0 \\[2.2ex] 0 \end{bmatrix}$$

Jadi, Anda melihat bagaimana metode Newton membawa Anda ke titik pelana di .$x=0,y=0$

Sebaliknya, metode gradient descent tidak akan mengarah ke titik pelana. Gradien adalah nol pada titik pelana, tetapi langkah kecil keluar akan menarik optimasi seperti yang Anda lihat dari gradien di atas - gradiennya pada variabel-y adalah negatif.

Anda mengajukan dua pertanyaan: Mengapa tidak lebih banyak orang menggunakan metode Newton, dan mengapa begitu banyak orang menggunakan penurunan gradien stokastik? Pertanyaan-pertanyaan ini memiliki jawaban yang berbeda, karena ada banyak algoritma yang mengurangi beban komputasi metode Newton tetapi sering bekerja lebih baik daripada SGD.

Pertama: Metode Newton membutuhkan waktu yang lama untuk setiap iterasi dan membutuhkan banyak memori. Seperti yang ditunjukkan jwimberley, Metode Newton membutuhkan komputasi turunan kedua, , yaitu , di mana adalah jumlah fitur, sedangkan komputasi gradien, , hanya . Tetapi langkah selanjutnya adalah , yang merupakan untuk dihitung. Jadi, sementara menghitung Hessian itu mahal, membalikkannya atau memecahkan kuadrat terkecil seringkali lebih buruk. (Jika Anda memiliki fitur yang jarang, asimptotik terlihat lebih baik, tetapi metode lain juga berperforma lebih baik, sehingga sparsity tidak membuat Newton relatif lebih menarik.)O ( N 2 ) N g O ( N ) H - 1 g O ( N 3$H$$O(N^2)$$N$$g$$O(N)$$H^{-1} g$$O(N^3)$

Kedua, banyak metode, bukan hanya gradient descent, digunakan lebih sering daripada Newton; mereka sering tiruan dari metode Newton, dalam arti bahwa mereka mendekati langkah Newton dengan biaya komputasi yang lebih rendah per langkah tetapi mengambil lebih banyak iterasi untuk bertemu. Beberapa contoh:

• Karena biaya membalikkan Hessian, metode `quasi-Newton" seperti BFGS mendekati Hessian terbalik , , dengan melihat bagaimana gradien telah berubah selama beberapa langkah terakhir.$H^{-1}$

• BFGS masih sangat intensif dalam pengaturan dimensi tinggi karena memerlukan penyimpanan seluruh perkiraan Hessian terbalik. Memori terbatas BFGS (L-BFGS) menghitung arah langkah selanjutnya sebagai perkiraan Hessian terbalik kali gradien, tetapi hanya membutuhkan menyimpan beberapa pembaruan gradien terakhir; itu tidak secara eksplisit menyimpan perkiraan Goni terbalik.$O(N^2)$

• Ketika Anda tidak ingin berurusan dengan perkiraan turunan kedua sama sekali, gradient descent menarik karena hanya menggunakan informasi urutan pertama saja. Keturunan gradien secara implisit mendekati Hessian terbalik sebagai laju pembelajaran dikali matriks identitas. Saya, secara pribadi, jarang menggunakan gradient descent: L-BFGS juga mudah diimplementasikan, karena hanya membutuhkan menentukan fungsi dan gradien objektif; ia memiliki pendekatan Hessian terbalik yang lebih baik daripada gradient descent; dan karena gradient descent memerlukan penyetelan laju pembelajaran.

• Terkadang Anda memiliki jumlah pengamatan (titik data) yang sangat besar, tetapi Anda bisa belajar hampir juga dari jumlah pengamatan yang lebih kecil. Ketika itu terjadi, Anda dapat menggunakan "metode batch", seperti keturunan gradien stokastik, yang siklus melalui menggunakan himpunan bagian dari pengamatan.

Arah penurunan gradien lebih murah untuk dihitung, dan melakukan pencarian garis ke arah itu adalah sumber kemajuan yang lebih andal dan stabil menuju yang optimal. Singkatnya, penurunan gradien relatif dapat diandalkan.

Metode Newton relatif mahal karena Anda perlu menghitung Hessian pada iterasi pertama. Kemudian, pada setiap iterasi berikutnya, Anda dapat menghitung ulang sepenuhnya Hessian (seperti dalam metode Newton) atau hanya "memperbarui" Hessian iterasi sebelumnya (dalam metode kuasi-Newton) yang lebih murah tetapi kurang kuat.

Dalam kasus ekstrem dari fungsi berperilaku sangat baik, terutama fungsi kuadrat sempurna, metode Newton adalah pemenang yang jelas. Jika kuadrat sempurna, metode Newton akan bertemu dalam satu iterasi tunggal.

Dalam kasus ekstrim yang berlawanan dari fungsi yang berperilaku sangat buruk, gradient descent akan cenderung menang. Ini akan memilih arah pencarian, mencari ke bawah arah itu, dan pada akhirnya mengambil langkah kecil tapi produktif. Sebaliknya, metode Newton akan cenderung gagal dalam kasus-kasus ini, terutama jika Anda mencoba menggunakan pendekatan kuasi-Newton.

Di antara gradien keturunan dan metode Newton, ada metode seperti algoritma Levenberg-Marquardt (LMA), meskipun saya telah melihat nama-nama itu agak membingungkan. Intinya adalah menggunakan lebih banyak informasi pencarian gradien-keturunan ketika semuanya kacau dan membingungkan, kemudian beralih ke pencarian metode-Newton lebih informasi ketika semuanya menjadi lebih linier dan dapat diandalkan.

Untuk dimensi besar, Goni biasanya mahal untuk disimpan dan penyelesaian untuk arah bisa mahal. Ini juga lebih sulit untuk diparalelkan.$Hd = g$

Metode Newton bekerja dengan baik ketika dekat dengan solusi, atau jika Hessian perlahan bervariasi, tetapi membutuhkan beberapa trik untuk mengatasi kurangnya konvergensi dan kurangnya kepastian.

Seringkali perbaikan dicari, bukan solusi yang tepat, dalam hal ini biaya tambahan metode Newton atau Newton tidak dibenarkan.

Ada berbagai cara untuk memperbaiki hal di atas seperti metrik variabel atau metode wilayah kepercayaan.

Sebagai catatan, dalam banyak masalah masalah utama adalah penskalaan dan Hessian memberikan informasi penskalaan yang sangat baik, meskipun dengan biaya. Jika seseorang dapat mendekati Hessian, sering kali dapat meningkatkan kinerja secara signifikan. Hingga taraf tertentu, metode Newton memberikan penskalaan 'terbaik' karena metode ini afinitas invarian.

Ada banyak kesulitan terkait penggunaan metode Newton untuk SGD, terutama:

• perlu matriks Hessian - bagaimana memperkirakannya misalnya dari gradien bising dengan presisi yang cukup dalam biaya yang masuk akal?

• Hessian penuh terlalu mahal - kita lebih membutuhkan pembatasan, misalnya ke subruang (subruang yang mana?),

• itu membutuhkan , apa yang mahal dan sangat tidak stabil untuk estimasi bising - dapat dikaburkan di sekitar membalikkan hingga tak terbatas,$H^{-1}$$\lambda=0$

• Metode Newton secara langsung menarik untuk menutup titik dengan gradien nol ... yang biasanya merupakan pelana di sini. Bagaimana cara mengusir mereka? Misalnya Newton bebas pelana membalikkan arah kelengkungan negatif, tetapi itu membutuhkan tanda-tanda kontrol nilai eigen,

• akan lebih baik untuk melakukannya secara online - daripada melakukan banyak perhitungan dalam satu titik, cobalah untuk memecahnya menjadi banyak langkah kecil yang mengeksploitasi lebih banyak informasi lokal.

Kita dapat beralih dari urutan pertama ke urutan kedua dalam langkah-langkah kecil, misalnya menambahkan pembaruan hanya 3 rata-rata ke metode momentum, kita dapat secara bersamaan MSE menyesuaikan parabola dalam arahnya untuk pilihan ukuran langkah yang lebih cerdas ... pemodelan urutan kedua dalam ruang subruang dimensi rendah kita masih dapat menggunakan koordinat yang tersisa untuk penurunan gradien simultan.