Ukuran langkah gradient descent adaptif ketika Anda tidak dapat melakukan pencarian baris

Saya memiliki fungsi objektif bergantung pada nilai , di mana adalah solusi untuk PDE. Saya mengoptimalkan dengan gradient descent pada kondisi awal PDE: . Yaitu, saya memperbarui dan kemudian harus mengintegrasikan PDE untuk menghitung residu saya. Itu berarti, jika saya melakukan pencarian baris untuk ukuran langkah gradient descent (sebut saja ), untuk setiap nilai potensial dari saya harus mengintegrasikan PDE dari awal lagi. $E$ $\phi(x, t = 1.0)$ $\phi(x, t)$ $E$ $\phi(x, t = 0.0)$ $\phi(x, t = 0.0)$ $\alpha$ $\alpha$

Dalam kasus saya itu akan sangat mahal. Apakah ada opsi lain untuk ukuran langkah gradient descent adaptif?

Saya tidak hanya mencari skema berprinsip matematis di sini (walaupun tentu saja itu lebih baik jika ada sesuatu), tetapi akan senang dengan apa pun yang umumnya lebih baik daripada ukuran langkah statis.

Terima kasih!

optimization pde conjugate-gradient NLi10Me
sumber

Saya tidak berpikir saya ingin memodifikasi cara saya mengintegrasikan PDE saat ini, karena bagi saya itu akan menjadi penulisan ulang kode utama. Juga, tidak terlalu sulit karena PDE itu rumit, karena saya harus menyelesaikannya pada grid yang sangat padat dalam ruangwaktu karena saya membutuhkan akurasi angka yang sangat tinggi.

NLi10Me

Di sisi lain, metode BB (yang saya tidak kenal) tampaknya cukup bagus; yang harus saya lakukan adalah melacak negara dan gradien iterasi sebelumnya dan saya mendapatkan perkiraan urutan kedua ... yang tampaknya sangat bagus. Namun, derivasi mengasumsikan kuadrat cembung dan masalah saya hampir pasti tidak. Meskipun, saya juga pasti menemukan (dan senang dengan) lokal daripada minimum global. Apakah Anda tahu seberapa baik kinerja BB pada masalah dimensi yang sangat tinggi?

NLi10Me

Saya kira apa yang saya maksud tentang minimum lokal adalah bahwa, di lingkungan minimum lokal, bukankah ada fungsi kira-kira kuadrat? Saya pikir keadaan awal saya cukup dekat dengan minimum, karena untuk banyak kasus saya mendapatkan konvergensi yang lancar bahkan dengan ukuran langkah statis. Jadi, meskipun dimensinya sangat tinggi, dan secara umum jika Anda menganggap seluruh ruang pencarian masalahnya adalah non-cembung / non-kuadrat, bisakah BB masih menjadi pilihan yang baik tanpa pencarian garis?

ϕ^{(0)} (x, t = 0.0)

$\phi^{(0)}(x, t = 0.0)$

NLi10Me

"Bahan" lainnya untuk adalah data gambar eksperimental. mencoba melengkungkan satu gambar untuk "mencocokkan" yang lain (diukur oleh beberapa fungsional yang cocok seperti norma L2 yang diintegrasikan dengan voxels). Untuk beberapa pasangan gambar, saya mendapatkan konvergensi yang lancar dengan (pilihan saya saat ini) ukuran langkah statis. Untuk pasangan gambar lain, saya mendapatkan banyak osilasi. Sistem harus sepenuhnya otomatis, jadi saya tidak bisa kembali dan tangan mengedit ukuran langkah untuk pasangan gambar yang merepotkan.

E

$E$

ϕ (x, t = 1.0)

$\phi(x, t = 1.0)$

NLi10Me

Benar, saya harus menyelesaikan sistem adjoint untuk mendapatkan gradien (yang merupakan sistem nastier dan membutuhkan waktu lebih lama). Ok, saya pikir saya akan mencoba BB dengan menelusuri garis belakang. Terima kasih sangat banyak untuk saran; penasihat saya sering sulit untuk dikenali dan banyak dari mereka tidak tertarik pada implementasi hanya sebagai model. Saya menemukan metode numerik adalah komponen penting untuk menunjukkan apakah model itu bagus atau tidak, jadi terima kasih lagi saya sangat menghargainya.

NLi10Me

Saya akan mulai dengan komentar umum: informasi urutan pertama (yaitu, hanya menggunakan gradien, yang menyandikan kemiringan) hanya dapat memberi Anda informasi arah: Ini dapat memberi tahu Anda bahwa nilai fungsi menurun dalam arah pencarian, tetapi tidak untuk berapa lama . Untuk memutuskan seberapa jauh untuk pergi sepanjang arah pencarian, Anda memerlukan informasi tambahan (gradient descent dengan panjang langkah konstan dapat gagal bahkan untuk masalah kuadrat cembung). Untuk ini, Anda pada dasarnya memiliki dua pilihan:

Gunakan informasi urutan kedua (yang menyandikan kelengkungan), misalnya dengan menggunakan metode Newton alih-alih gradient descent (yang Anda selalu dapat menggunakan panjang langkah cukup dekat dengan minimizer). $1$
Trial and error (maksud saya menggunakan pencarian baris yang tepat seperti Armijo).

Jika, saat Anda menulis, Anda tidak memiliki akses ke turunan kedua, dan mengevaluasi fungsi objektif sangat mahal, satu-satunya harapan Anda adalah untuk berkompromi: gunakan informasi perkiraan tingkat kedua yang cukup untuk mendapatkan panjang langkah kandidat yang baik sehingga garis pencarian hanya memerlukan evaluasi (yaitu, paling banyak kelipatan konstan (kecil) dari upaya yang Anda perlukan untuk mengevaluasi gradien Anda). $\mathcal{O}(1)$

Salah satu kemungkinan adalah menggunakan panjang langkah Barzilai - Borwein (lihat, misalnya, Fletcher: Pada metode Barzilai-Borwein . Optimasi dan kontrol dengan aplikasi, 235–256, Optimasi Aplikasi, 96, Springer, New York, 2005 ). Idenya adalah untuk menggunakan perkiraan perbedaan yang terbatas dari kelengkungan di sepanjang arah pencarian untuk mendapatkan perkiraan ukuran langkah. Secara khusus, pilih sewenang-wenang, atur dan kemudian untuk : $\alpha_0>0$ $g^0:=\nabla f(x^0)$ $k=0,...$

Set dan $s^k = -\alpha_k^{-1} g^k$ $x^{k+1}=x^k+s^k$
Evaluasi dan set $g^{k+1}=\nabla f(x^{k+1})$ $y^k = g^{k+1}-g^{k}$
Set $\alpha_{k+1} = \frac{(y^k)^Ty^k}{(y^k)^Ts^k}$

Pilihan ini dapat ditunjukkan untuk menyatu (dalam praktik sangat cepat) untuk fungsi kuadrat, tetapi konvergensi bukan monoton (yaitu, nilai fungsi dapat lebih besar dari , tetapi hanya sesekali; lihat plot pada halaman 10 di kertas Fletcher). Untuk fungsi non-kuadrat, Anda perlu menggabungkan ini dengan pencarian garis, yang perlu dimodifikasi untuk menangani non-monotonicity. Salah satu kemungkinan adalah memilih (misalnya, dengan menelusuri ulang) sedemikian rupa sehingga mana adalah parameter Armijo khas dan $f(x^{k+1})$ $f(x^k)$ $\sigma_k \in (0,\alpha_k^{-1})$

f (x^{k} - σ_{k} g^{k}) \leq max_{max (k - M, 1) \leq j \leq k} f (x^{j}) - γ σ_{k} (g^{k})^{T} g^{k},

$f(x^k - \sigma_k g^k) \leq \max_{\max(k-M,1)\leq j\leq k} f(x^j) - \gamma \sigma_k (g^k)^Tg^k,$

γ \in (0, 1)

$\gamma\in(0,1)$

M

$M$ mengontrol tingkat monotonitas (mis., ). Ada juga varian yang menggunakan nilai gradien alih-alih nilai fungsi, tetapi dalam kasus Anda gradien bahkan lebih mahal untuk dievaluasi daripada fungsinya, sehingga tidak masuk akal di sini. (Catatan: Anda tentu saja dapat mencoba secara membabi buta menerima panjang langkah BB dan memercayai keberuntungan Anda, tetapi jika Anda membutuhkan segala jenis kekuatan - seperti yang Anda tulis dalam komentar Anda - itu akan menjadi ide yang sangat buruk.)

M = 10

$M=10$

Alternatif (dan, menurut saya, jauh lebih baik) pendekatan akan menggunakan pendekatan perbedaan hingga ini sudah dalam perhitungan arah pencarian; ini disebut metode kuasi-Newton . Idenya adalah untuk secara bertahap membangun perkiraan Hessian dengan menggunakan perbedaan gradien. Misalnya, Anda dapat mengambil (matriks identitas) dan untuk menyelesaikan dan set dengan seperti di atas dan . (Ini disebut pembaruan Broyden $\nabla^2 f(x^k)$ $H_0=\mathrm{Id}$ $k=0,\dots$

\begin{matrix} (1) & H_{k} s^{k} = - g^{k}, \end{matrix}

$H_{k}s^{k} = -g^{k},\label{cc1}\tag{1}$

H_{k + 1} = H_{k} + \frac{(y^{k} - H_{k} s^{k})^{T} (s^{k})^{T}}{(s^{k})^{T} s^{k}}

$H_{k+1} = H_k + \frac{(y^k-H_ks^k)^T(s^k)^T}{(s^k)^Ts^k}$

y^{k}

$y^k$

x^{k + 1} = x^{k} + s^{k}

$x^{k+1} = x^k +s^k$ dan jarang digunakan dalam praktik; pembaruan yang lebih baik tetapi sedikit lebih rumit adalah pembaruan BFGS , di mana - dan lebih banyak informasi - saya merujuk pada buku Nocedal dan Wright's Numerical Optimization .) Kelemahannya adalah a) ini akan membutuhkan penyelesaian sistem linear pada setiap langkah (tetapi hanya dari ukuran yang tidak diketahui yang dalam kasus Anda merupakan kondisi awal, maka upaya tersebut harus didominasi oleh pemecahan PDE untuk mendapatkan gradien, juga, ada aturan pembaruan untuk perkiraan Hessian terbalik , yang hanya memerlukan komputasi matriks tunggal -Vektor produk) dan b) Anda masih memerlukan pencarian garis untuk menjamin konvergensi ...

Untungnya, dalam konteks ini terdapat pendekatan alternatif yang memanfaatkan setiap evaluasi fungsi. Idenya adalah bahwa untuk simetris dan pasti positif (yang dijamin untuk pembaruan BFGS), menyelesaikan setara dengan meminimalkan model kuadratik Dalam metode wilayah kepercayaan , Anda akan melakukannya dengan kendala tambahan yang , di mana adalah radius wilayah trust yang dipilih dengan tepat (yang memainkan peran sebagai panjang langkah ). Gagasan kuncinya adalah sekarang untuk memilih jari-jari ini secara adaptif, berdasarkan langkah yang dihitung. Secara khusus, Anda melihat rasionya $H_k$ $\eqref{cc1}$

q_{k} (s) = \frac{1}{2} s^{T} H_{k} s + s^{T} g^{k} .

$q_k(s) = \frac12 s^T H_k s + s^T g^k.$

‖ s ‖ \leq Δ_{k}

$\|s\| \leq \Delta_k$

Δ_{k}

$\Delta_k$

σ_{k}

$\sigma_k$

ρ_{k} := \frac{f (x^{k}) - f (x^{k} + s^{k})}{f (x^{k}) - q_{k} (s^{k})}

$\rho_k := \frac{f(x^k)-f(x^k+s^k)}{f(x^k)-q_k(s^k)}$ dari pengurangan aktual dan nilai fungsi yang diprediksi. Jika sangat kecil, model Anda buruk, dan Anda membuang dan coba lagi dengan . Jika mendekati , model Anda baik, dan Anda mengatur dan meningkatkan . Kalau tidak, Anda hanya mengatur dan meninggalkan sendirian. Untuk menghitung minimalizer dari

ρ_{k}

$\rho_k$

s^{k}

$s^k$

Δ_{k + 1} < Δ_{k}

$\Delta_{k+1}<\Delta_k$

ρ_{k}

$\rho_k$

1

$1$

x^{k + 1} = x^{k} + s^{k}

$x^{k+1}=x^k+s^k$

Δ_{k + 1} > Δ_{k}

$\Delta_{k+1}>\Delta_k$

x^{k + 1} = x^{k} + s^{k}

$x^{k+1}=x^k+s^k$

Δ_{k}

$\Delta_k$

s^{k}

$s^k$

min_{‖ s ‖ \leq Δ_{k}} q_{k} (s)

$\min_{\|s\|\leq \Delta_k} q_k(s)$ , terdapat beberapa strategi untuk menghindari keharusan menyelesaikan masalah optimisasi terbatas penuh; favorit saya adalah metode CG terpotong Steihaug . Untuk lebih jelasnya, saya kembali merujuk ke Nocedal dan Wright.

Christian Clason
sumber

Saya baru saja melihat ini lagi, dan menyadari saya punya pertanyaan. Pada langkah ketiga untuk metode BB Anda memiliki ; di mana dan . Pembilang dan penyebut dalam ekspresi untuk terlihat seperti produk dalam. Dalam kasus saya, , di mana adalah ruang vektor dengan metrik Riemannian non-sepele: K. Yaitu, . Apakah itu memengaruhi definisi ?

α_{k + 1} = \frac{(y^{k})^{T} y^{k}}{(y^{k})^{T} s^{k}}

$\alpha_{k+1} = \frac{(y^k)^Ty^k}{(y^k)^Ts^k}$

y^{k} = g^{k + 1} - g^{k}

$y^{k} = g^{k+1} - g^k$

s^{k} = - α_{k}^{- 1} g^{k}

$s^k = -\alpha_k^{-1}g^k$

α_{k + 1}

$\alpha_{k+1}$

g^{k} \in V^{*}

$g^k \in V^*$

V^{*}

$V^*$

⟨ g^{k}, g^{k} ⟩_{V^{*}} = ⟨ g^{k}, K g^{k} ⟩_{L_{2}}

$\langle g^k, g^k \rangle _{V^*} = \langle g^k, Kg^k \rangle_{L_2}$

α_{k + 1}

$\alpha_{k+1}$

NLi10Me

Ya, jika Anda memiliki struktur ruang vektor non-sepele, Anda harus menghargai itu dalam algoritma. Secara khusus, Anda harus membedakan antara produk dalam dari dua fungsi dalam ruang yang sama (misalnya, dan ) dan produk dualitas antara fungsi dalam ruang dan satu di ruang ganda (misalnya, dan ) - untuk yang terakhir, Anda perlu memasukkan pemetaan Riesz untuk mengubahnya menjadi produk dalam terlebih dahulu. (Ini dapat ditafsirkan sebagai prasyarat.)

y^{k}

$y^k$

y^{k}

$y^k$

s^{k}

$s^k$

y^{k}

$y^k$

Christian Clason

Dr. Clason, saya akan mengirimkan makalah ke ISBI 2017 yang merinci beberapa percobaan yang telah saya lakukan menggunakan metode pencarian garis BB + untuk tugas registrasi gambar difeomorfik. Apakah Anda ingin dimasukkan sebagai penulis naskah? Saya belum menulisnya, tetapi saya memiliki sebagian besar eksperimen baik yang lengkap atau sedang berlangsung. Tolong beritahu saya.

NLi10Me

@ NLi10Me Terima kasih atas tawarannya yang baik, tapi saya belum melakukan apa pun yang pantas mendapatkan kepenulisan bersama - semua yang saya tulis adalah bahan buku teks standar. Jika Anda merasa kuat tentang hal itu, Anda dapat berterima kasih kepada saya untuk "komentar yang membantu (apa pun yang membantu)", tetapi bahkan itu tidak diperlukan. Mengetahui apa yang saya tulis cukup membantu!

Christian Clason

Maaf, Anda benar, itu kesalahan ketik - diperbaiki! (Kondisi Armijo sering ditulis sebagai , di mana adalah arah pencarian - belum tentu negatif gradien - dan ukuran langkah, yang seharusnya memperjelas apa yang terjadi.)

f (x + σ s) - f (x) \leq γ \nabla f (x)^{T} (σ s)

$f(x+\sigma s) - f(x) \leq \gamma\nabla f(x)^T(\sigma s)$

s

$s$

σ

$\sigma$

Christian Clason

Ukuran langkah gradient descent adaptif ketika Anda tidak dapat melakukan pencarian baris

Jawaban: