Bagaimana cara kerja L-BFGS?

Tujuan dari makalah ini adalah untuk mengoptimalkan beberapa parameter dengan memaksimalkan log-likelihood yang diatur. Kemudian mereka menghitung turunan parsial. Dan kemudian penulis menyebutkan bahwa mereka mengoptimalkan persamaan menggunakan L-BFGS, prosedur kuasi-Newton standar untuk mengoptimalkan fungsi halus dari banyak variabel (tidak ada rincian lebih lanjut).

Bagaimana cara kerjanya ?

Pada dasarnya pikirkan L-BFGS sebagai cara menemukan minimum (lokal) fungsi objektif, memanfaatkan nilai fungsi tujuan dan gradien fungsi tujuan. Level deskripsi itu mencakup banyak metode optimasi selain L-BFGS. Anda dapat membaca lebih lanjut tentang hal ini di bagian 7.2 dari Nocedal dan Wright "Numerical Optimization, 2nd edition" http://www.springer.com/us/book/9780387303031 . Diskusi yang sangat sepintas tentang L-BFGS disediakan di https://en.wikipedia.org/wiki/Limited-memory_BFGS .

Metode urutan pertama berarti gradien (turunan pertama) (dan mungkin nilai fungsi objektif) digunakan, tetapi bukan Hessian (turunan kedua). Pikirkan, misalnya, penurunan gradien dan penurunan paling curam, di antara banyak lainnya.

Metode urutan kedua berarti gradien dan Goni digunakan (dan mungkin nilai fungsi objektif). Metode urutan kedua dapat didasarkan pada

1. Matriks "Tepat" Hessian (atau perbedaan gradien terbatas), dalam hal ini mereka dikenal sebagai metode Newton atau

2. Metode Quasi-Newton, yang mendekati Hessian berdasarkan perbedaan gradien pada beberapa iterasi, dengan memaksakan kondisi "secant" (Quasi-Newton). Ada banyak metode Quasi-Newton yang berbeda, yang memperkirakan Hessian dengan cara yang berbeda. Salah satu yang paling populer adalah BFGS. Perkiraan BFGS Hessian dapat didasarkan pada sejarah penuh gradien, dalam hal ini disebut sebagai BFGS, atau dapat didasarkan hanya pada gradien m terbaru, dalam hal ini dikenal sebagai BFGS memori terbatas, disingkat sebagai L-BFGS. Keuntungan dari L-BFGS adalah bahwa hanya membutuhkan mempertahankan gradien m terbaru, di mana m biasanya sekitar 10 hingga 20, yang merupakan persyaratan penyimpanan yang jauh lebih kecil daripada n * (n + 1) / 2 elemen yang diperlukan untuk menyimpan penuh (segitiga) dari perkiraan Goni, seperti yang dipersyaratkan dengan BFGS, di mana n adalah dimensi masalah. Tidak seperti BFGS (penuh), perkiraan Hessian tidak pernah secara eksplisit dibentuk atau disimpan dalam L-BFGS (meskipun beberapa implementasi BFGS hanya membentuk dan memperbarui faktor Choelsky dari perkiraan Hessian, daripada perkiraan Hessian sendiri); melainkan, perhitungan yang akan diperlukan dengan perkiraan Goni dicapai tanpa secara eksplisit membentuknya. L-BFGS digunakan sebagai pengganti BFGS untuk masalah yang sangat besar (ketika n sangat besar), tetapi mungkin tidak berkinerja sebaik BFGS. Oleh karena itu, BFGS lebih disukai daripada L-BFGS ketika persyaratan memori BFGS dapat dipenuhi. Di sisi lain, L-BFGS mungkin tidak jauh lebih buruk dalam kinerjanya daripada BFGS. perkiraan Hessian tidak pernah secara eksplisit dibentuk atau disimpan dalam L-BFGS (meskipun beberapa implementasi BFGS hanya membentuk dan memperbarui faktor Choelsky dari perkiraan Hessian, daripada perkiraan Hessian sendiri); melainkan, perhitungan yang akan diperlukan dengan perkiraan Goni dicapai tanpa secara eksplisit membentuknya. L-BFGS digunakan sebagai pengganti BFGS untuk masalah yang sangat besar (ketika n sangat besar), tetapi mungkin tidak berkinerja sebaik BFGS. Oleh karena itu, BFGS lebih disukai daripada L-BFGS ketika persyaratan memori BFGS dapat dipenuhi. Di sisi lain, L-BFGS mungkin tidak jauh lebih buruk dalam kinerjanya daripada BFGS. perkiraan Hessian tidak pernah secara eksplisit dibentuk atau disimpan dalam L-BFGS (meskipun beberapa implementasi BFGS hanya membentuk dan memperbarui faktor Choelsky dari perkiraan Hessian, daripada perkiraan Hessian sendiri); melainkan, perhitungan yang akan diperlukan dengan perkiraan Goni dicapai tanpa secara eksplisit membentuknya. L-BFGS digunakan sebagai pengganti BFGS untuk masalah yang sangat besar (ketika n sangat besar), tetapi mungkin tidak berkinerja sebaik BFGS. Oleh karena itu, BFGS lebih disukai daripada L-BFGS ketika persyaratan memori BFGS dapat dipenuhi. Di sisi lain, L-BFGS mungkin tidak jauh lebih buruk dalam kinerjanya daripada BFGS. perhitungan yang akan diperlukan dengan perkiraan Goni dicapai tanpa secara eksplisit membentuknya. L-BFGS digunakan sebagai pengganti BFGS untuk masalah yang sangat besar (ketika n sangat besar), tetapi mungkin tidak berkinerja sebaik BFGS. Oleh karena itu, BFGS lebih disukai daripada L-BFGS ketika persyaratan memori BFGS dapat dipenuhi. Di sisi lain, L-BFGS mungkin tidak jauh lebih buruk dalam kinerjanya daripada BFGS. perhitungan yang akan diperlukan dengan perkiraan Goni dicapai tanpa secara eksplisit membentuknya. L-BFGS digunakan sebagai pengganti BFGS untuk masalah yang sangat besar (ketika n sangat besar), tetapi mungkin tidak berkinerja sebaik BFGS. Oleh karena itu, BFGS lebih disukai daripada L-BFGS ketika persyaratan memori BFGS dapat dipenuhi. Di sisi lain, L-BFGS mungkin tidak jauh lebih buruk dalam kinerjanya daripada BFGS.

Bahkan pada tingkat deskripsi ini, ada banyak varian. Misalnya, metode dapat benar-benar tidak terlindungi, dalam hal apa pun terjadi, dan mereka mungkin tidak bertemu dengan apa pun, bahkan pada masalah cembung. Atau mereka bisa dilindungi. Metode perlindungan biasanya didasarkan pada wilayah kepercayaan atau pencarian garis, dan dimaksudkan untuk memastikan konvergensi dengan sesuatu. Sangat penting, hanya mengetahui bahwa suatu metode adalah L-BFGS tidak dengan sendirinya memberi tahu Anda apa jenis perlindungan, jika ada, yang digunakan. Ini seperti mengatakan bahwa mobil adalah sedan 4 pintu - tetapi tentu saja tidak semua sedan 4 pintu memiliki kinerja atau keandalan yang sama. Ini hanyalah salah satu atribut dari algoritma optimasi.