Jika Hessians sangat baik untuk optimasi (lihat misalnya metode Newton ), mengapa berhenti di situ? Mari kita gunakan derivatif ketiga, keempat, kelima, dan keenam? Kenapa tidak?

Saya menafsirkan pertanyaan sebagai "Mengapa metode Newton hanya menggunakan turunan pertama dan kedua, bukan turunan ketiga atau lebih tinggi?"

Sebenarnya, dalam banyak kasus, pergi ke turunan ketiga memang membantu; Saya sudah melakukannya dengan barang-barang khusus sebelumnya. Namun, secara umum, pergi ke turunan yang lebih tinggi menambah kompleksitas komputasi - Anda harus menemukan dan menghitung semua turunan itu, dan untuk masalah multivariat, ada lebih banyak turunan ketiga daripada turunan pertama! - yang jauh melebihi penghematan dalam hitungan langkah yang Anda dapatkan, jika ada. Misalnya, jika saya memiliki masalah 3 dimensi, saya memiliki 3 turunan pertama, 6 turunan kedua, dan 10 turunan ketiga, jadi pergi ke versi urutan ketiga lebih dari dua kali lipat jumlah evaluasi yang harus saya lakukan (dari 9 ke 19), belum lagi meningkatnya kerumitan menghitung arah langkah / ukuran setelah saya melakukan evaluasi tersebut, tetapi hampir pasti tidak akan memotong jumlah langkah yang harus saya ambil setengah.

Sekarang, dalam kasus umum dengan variabel , koleksi turunan parsial akan berjumlah , jadi untuk masalah dengan lima variabel, jumlah total ketiga , turunan parsial keempat, dan kelima akan sama dengan 231, peningkatan lebih dari 10 kali lipat dari jumlah turunan parsial pertama dan kedua (20). Anda harus memiliki masalah yang sangat, sangat dekat dengan polinomial orde kelima dalam variabel untuk melihat pengurangan yang cukup besar dalam jumlah iterasi untuk menebus beban komputasi ekstra.$k$$n^{th}$${k+n-1} \choose {k-1}$

Saya tidak benar-benar melihat apa aspek statistik dari pertanyaan ini, jadi saya akan menjawab bagian pengoptimalan.

Ada 2 bagian untuk konvergensi: biaya iterasi & jumlah iterasi

Cukup banyak setiap jawaban di sini berfokus hanya pada biaya iterasi dan mengabaikan iterasi count . Tapi keduanya penting. Metode yang berulang dalam 1 nanosecond tetapi butuh iterasi untuk bertemu tidak akan ada gunanya bagimu. Dan metode yang meledak tidak akan membantu, tidak peduli seberapa murah biaya iterasinya.$10^{20}$

Mari kita cari tahu apa yang terjadi.

Jadi: Mengapa tidak menggunakan> derivatif urutan ke-2?

Sebagian karena (dan ini juga berlaku untuk orde kedua, tetapi lebih dari itu dalam sedikit):

Metode tingkat tinggi umumnya hanya bertemu lebih cepat ketika mendekati optimal .

Di sisi lain, mereka meledak lebih mudah ketika mereka lebih jauh dari yang optimal!

(Tentu saja, ini tidak selalu benar; misalnya kuadrat akan menyatu dalam 1 langkah dengan metode Newton. Tetapi untuk fungsi sewenang-wenang di dunia nyata yang tidak memiliki properti bagus, ini umumnya benar.)

Ini berarti bahwa ketika Anda berada jauh dari optimal, Anda umumnya menginginkan metode tingkat rendah (baca: tingkat pertama). Hanya ketika Anda dekat Anda ingin meningkatkan urutan metode.

Jadi mengapa berhenti di urutan ke-2 ketika Anda berada di dekat root?

Karena perilaku konvergensi "kuadratik" benar-benar "cukup baik"!

Untuk melihat mengapa, pertama Anda harus memahami apa "kuadrat konvergensi" berarti .

Secara matematis, konvergensi kuadrat berarti bahwa, jika adalah kesalahan Anda pada iterasi , maka yang berikut ini berlaku untuk beberapa konstanta :$\epsilon_k$$k$$c$

$$\lvert\epsilon_{k+1}\rvert \leq c\ \lvert\epsilon_{k}\rvert^2$$

Dalam bahasa Inggris yang sederhana, ini berarti bahwa, setelah Anda mendekati yang optimal (penting!), Setiap langkah tambahan menggandakan jumlah digit akurasi .

Mengapa? Sangat mudah untuk melihat dengan contoh: untuk dan , Anda memiliki , , dll. Yang sangat cepat . (Ini super-eksponensial !)$c = 1$$\lvert\epsilon_1\rvert = 0.1$$\lvert\epsilon_2\rvert \leq 0.01$$\lvert\epsilon_3\rvert \leq 0.0001$

Mengapa tidak berhenti di pesanan pertama dan bukan pesanan kedua?

Sebenarnya, orang sering melakukan ini ketika turunan orde dua menjadi terlalu mahal. Tetapi konvergensi linier bisa sangat lambat. mis. jika Anda mendapat maka Anda mungkin memerlukan 10.000.000 iterasi dengan konvergensi linier untuk mendapatkan , tetapi hanya 23 iterasi dengan konvergensi kuadrat. Jadi Anda dapat melihat mengapa ada perbedaan drastis antara konvergensi linier dan kuadratik. Ini tidak benar untuk konvergensi orde 2 dan 3, misalnya (lihat paragraf berikutnya).$\epsilon_k = 0.9999999$$\lvert\epsilon\rvert < 0.5$

Pada titik ini, jika Anda mengetahui ilmu komputer, Anda memahami bahwa dengan konvergensi orde 2, masalahnya sudah terpecahkan . Jika Anda tidak melihat alasannya, inilah alasannya: tidak ada cara praktis untuk memperoleh tiga kali lipat jumlah iterasi daripada menggandakannya — apa yang akan Anda beli? Lagi pula, di komputer, bahkan angka double-prisi memiliki presisi 52 bit, yaitu sekitar 16 digit desimal. Mungkin itu akan mengurangi jumlah langkah yang Anda butuhkan dari 16 menjadi 3 ... yang terdengar hebat, sampai Anda menyadari itu harus dibayar dengan harus menghitung turunan ketiga pada setiap iterasi, yang merupakan kutukan dimensi.memukulmu dengan keras. Untuk masalah dimensi, Anda hanya membayar faktor untuk mendapatkan faktor , yang bodoh. Dan di dunia nyata masalah memiliki setidaknya ratusan dimensi (atau bahkan ribuan atau bahkan jutaan), bukan hanya ! Jadi Anda mendapatkan faktor mungkin 20 dengan membayar faktor, katakanlah, 20.000 ... bukan trade-off yang bijaksana.$6$$6$$\approx 5$$6$

Tetapi sekali lagi: ingat kutukan dimensi adalah setengah dari cerita .

Setengah lainnya adalah bahwa Anda biasanya mendapatkan perilaku yang lebih buruk ketika Anda jauh dari optimal, yang umumnya mempengaruhi jumlah iterasi yang harus Anda lakukan.

Kesimpulan

Dalam pengaturan umum, metode tingkat tinggi dari 2 adalah ide yang buruk. Tentu saja, jika Anda dapat membawa asumsi tambahan yang bermanfaat ke tabel (mis. Mungkin data Anda memang menyerupai polinomial tingkat tinggi, atau Anda memiliki cara untuk membatasi lokasi yang optimal, dll.), Maka mungkin Anda dapat menemukan bahwa itu adalah ide yang bagus — tapi itu akan menjadi keputusan khusus masalah, dan bukan aturan umum yang harus dijalani.

Bahkan menghitung Hessians cukup banyak pekerjaan:

$$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}.$$

Sekarang lihat bagaimana turunan ketiga terlihat seperti: Ini adalah matriks tiga dimensi. Begini tampilannya:

$$\partial H/\partial x=\begin{bmatrix} \dfrac{\partial H}{\partial x_1}\\ \dfrac{\partial H}{\partial x_2}\\ \vdots\\ \dfrac{\partial H}{\partial x_n} \end{bmatrix}$$ $$(\partial H/\partial x)_{ijk}=\dfrac{\partial^3 f}{\partial x_i\partial x_j\partial x_k}$$

Turunan keenam akan menjadi matriks enam dimensi:

$$\dfrac{\partial^6 f}{\partial x_i\partial x_j\partial x_k\partial x_l\partial x_m\partial x_n}$$

Biasanya, trade-off tidak menguntungkan untuk mengejar lebih tinggi dari Hessian. Maksud saya trade-off antara potensi gain dalam kecepatan melalui menggunakan pendekatan orde yang lebih tinggi vs amplifikasi noise Anda selalu memiliki derau dalam input karena kita berbicara tentang aplikasi statistik. Kebisingan ini akan diperkuat oleh turunannya.

Jika Anda bermain golf maka analogi dalam optimasi adalah untuk pertama-tama mengayunkan mencoba untuk mendapatkan ke hijau, tidak perlu khawatir banyak tentang lubang. Sekali, di atas hijau, kita akan membidik lubang.

Biasanya, ketika Anda menganalisis efektivitas algoritma seperti itu, Anda akan menemukan hasil seperti satu langkah dari algoritma urutan keempat memiliki kurang lebih efektivitas yang sama dengan dua langkah dari algoritma urutan kedua.

Jadi pilihan algoritma mana yang akan digunakan relatif sederhana: jika satu langkah dari algoritma urutan keempat membutuhkan kerja dua kali lebih banyak atau lebih dari satu langkah dari algoritma urutan kedua, Anda harus menggunakan yang terakhir sebagai gantinya.

Itu adalah situasi khas untuk jenis metode ini: algoritma klasik memiliki rasio kerja-ke-efektivitas yang optimal untuk masalah umum. Meskipun ada beberapa masalah di mana pendekatan urutan yang lebih tinggi tidak mudah untuk dihitung dan dapat mengungguli varian klasik, mereka relatif tidak umum.

Anda dapat menganggap urutan turunan sebagai urutan perkiraan polinomial terhadap fungsi. Kebanyakan rutinisasi optimasi bergantung pada konveksitas. Polinomial kuadrat akan menjadi cembung / cekung di mana-mana sedangkan orde 3 atau polinomial yang lebih tinggi tidak akan cembung di mana-mana. Sebagian besar rutinisasi optimasi bergantung pada perkiraan fungsi cembung dengan kuadratik untuk alasan ini. Perkiraan kuadratik yang cembung membutuhkan kondisi ketetapan positif yang harus diberlakukan agar kuadratik menjadi cembung.

Biarkan saya menjadi satu-satunya di sini yang mempertahankan metode urutan ke-3 untuk konvergensi SGD, tetapi jelas tidak di seluruh ruang apa yang akan membutuhkan koefisien 3/6, tetapi misalnya hanya dalam satu arah, yang hanya membutuhkan satu koefisien tambahan jika sudah memiliki model pesanan ke-2 dalam arah ini.$\approx dim^3/6$

Mengapa model single direction 3 order dapat bermanfaat? Misalnya karena turunan mendekati nol detik pada arah ini pada dasarnya berarti dua skenario alternatif: dataran tinggi atau titik belok - hanya yang pertama membutuhkan ukuran langkah yang lebih besar, dan turunan ke-3 memungkinkan untuk membedakannya.

Saya percaya kita akan pergi ke arah metode multi-order hybrid: metode urutan ke-2 dalam subruang dimensi rendah misalnya dari PCA dari gradien baru-baru ini, apa yang masih memungkinkan untuk penurunan gradien simultan urutan pertama ke arah bagian dari gradien ortogonal ke subruang ini ... dan tambahan Saya akan menambahkan misalnya model urutan ke-3 untuk satu arah paling relevan.