ENID
Lensa ML

Konveksitas, Minimum, dan Saddle Point

Langkah 1 dari 6: Konveks vs Non-Konveks

Kenapa bentuk fungsi menentukan optimasi

xf(x)Konveks (bentuk mangkuk)
KonveksKelengkungan: 0.00Bergelombang
Minimum Lokal
1
Konveks?
Ya
Min Global
0.00

Fungsi konveks melengkung ke atas di semua titik dan membentuk satu mangkuk. Minimum lokal mana pun adalah minimum global, jadi langkah menurun selalu menemukannya.

Geser slider Kelengkungan dari Konveks ke Bergelombang. Kurvanya x² + t·1.8·sin(2.5x), dan turunan keduanya 2 − 11.25·t·sin(2.5x). Nilai itu tetap non-negatif hanya selama t di bawah sekitar 0,18, jadi suku bergelombang yang kecil pun sudah merusak konveksitas. Definisi formalnya f(λa + (1−λ)b) ≤ λf(a) + (1−λ)f(b) untuk semua a, b, dan λ di antara 0 dan 1. Jumlah fungsi konveks tetap konveks, jadi menambahkan penalty L2 ke loss yang konveks tidak merusak konveksitasnya.

Langkah 2 dari 6: Minimum Lokal vs Global

Titik awal menentukan titik akhir

xf(x)basin of attraction (warna = minimum yang dicapai)globallokalawal
Kirix Awal: 2.00Kanan
x Awal
2.00
x Konvergen
1.57
f(x) di min
1.19

Dari x=2.0, gradient descent mengikuti kemiringan masuk ke minimum lokal di x=1.6. Gradient di sana nol, jadi ia tidak bisa keluar. Minimum global ada di x=-0.5. Pindahkan titik awal ke basin dengan warna lain.

Geser slider x Awal, atau tekan Tampilkan 4 titik awal sekaligus. Kurva ini punya dua minimum, minimum global di dekat x = −0.54 dan minimum lokal di dekat x = 1.56. Setiap percobaan memakai learning rate tetap 0,05 selama 120 langkah. Gradient descent hanya melihat kemiringan di tempatnya berdiri, jadi titik awal saja yang menentukan hasilnya. Menjalankan beberapa random restart dan menyimpan hasil terbaik adalah pertahanan paling sederhana, dan ini praktik umum untuk k-means dan metode non-konveks lainnya.

Langkah 3 dari 6: Saddle Point

Datar, tetapi bukan minimum

xyf > 0f < 0saddle point
x: 0.00
y: 0.00
df/dx
0.00
df/dy
0.00
|grad|
0.00

Di dekat saddle point, gradient mendekati nol, tetapi ini bukan minimum: f(x,y) = x² − y² melengkung ke atas pada x dan ke bawah pada y. Metode berbasis gradient bisa macet di sini.

Geser slider x dan y menuju titik asal dan lihat |grad| turun. Pada x² − y², Hessian punya satu eigenvalue positif dan satu negatif, dan itulah uji untuk saddle point. Di dimensi tinggi, saddle point jauh lebih umum daripada minimum lokal: titik kritis hanya menjadi minimum kalau kelengkungannya positif di setiap arah, dan dengan jutaan arah, hampir selalu ada yang negatif. Noise kecil dari gradient mini-batch biasanya mendorong optimizer keluar dari saddle point.

Langkah 4 dari 6: Uji Konveksitas

Turunan kedua menunjukkan kelengkungan

xf(x)
f(x)f''(x)garis singgung
KonkafBentuk: 0.50Konveks
x Uji: 0.50
f(x)
2.05
f'(x)
0.88
f''(x)
-1.23
Konveks?
Tidak

f''(x) < 0 di sini (garis putus-putus merah muda di bawah nol), jadi daerah ini konkaf. Fungsinya tidak konveks.

Geser Bentuk dari Konkaf ke Konveks, lalu geser x Uji untuk memeriksa tanda f''(x) di berbagai titik. Uji turunan kedua mensyaratkan f'' ≥ 0 di setiap titik, bukan satu titik saja, dan karena itu readout Konveks? memindai seluruh rentang. Untuk fungsi banyak variabel, uji ini menjadi syarat matriks: Hessian harus positive semidefinite di semua titik, artinya semua eigenvalue-nya non-negatif. Loss regresi logistik lolos uji ini, jadi tidak punya minimum palsu.

Langkah 5 dari 6: Loss Landscape

Neural network di dunia nyata

parameterlossinputhidden (4)output
Sempit (1)Lebar: 4Lebar (20)
Lebar
4
Minimum Lokal
5
Min Global
-0.92

Network dengan lebar sedang. Tonjolan mengecil seiring lebar bertambah.

Geser slider Lebar dari Sempit (1) ke Lebar (20) dan lihat tonjolannya mendatar terhadap mangkuk di bawahnya. Di sini tinggi tonjolan berskala 1/lebar, tiruan sederhana dari efek sungguhan. Readout Minimum Lokal turun dari 5 pada lebar 4 ke 3 pada lebar 10, dan mencapai 1 mulai lebar 15. Permukaan loss sungguhan punya jutaan dimensi, jadi gambarnya hanyalah irisan berdimensi rendah. Li et al. (2018) memakai irisan dua dimensi acak untuk menunjukkan bahwa skip connection dan lebar yang lebih besar membuat permukaan di sekitar solusi yang bagus tampak lebih halus.

Langkah 6 dari 6: Lolos dari Minimum Lokal

Momentum dan learning rate sebagai jalan keluar

xf(x)awal
RendahMomentum: 0.50Tinggi
KecilLearning Rate: 0.080Besar
Momentum
0.50
LR
0.080
Loss
3.69
Langkah
0

Momentum sedang mengumpulkan kecepatan dari gradient sebelumnya, sehingga membantu menembus minimum lokal yang dangkal sambil tetap stabil.

Atur Momentum dan Learning Rate, lalu tekan Putar atau jalankan langkah demi langkah. Pembaruannya v ← μ·v − η·∇f, lalu x ← x + v, mulai dari x = 2.5 hingga maksimal 200 langkah. Dengan momentum μ, gradient yang konstan membangun kecepatan sampai 1/(1 − μ) kali langkah biasa, jadi μ = 0.9 bergerak sekitar sepuluh kali lebih jauh. Adam dan SGD dengan momentum memakai rata-rata berjalan yang sama dari gradient sebelumnya. Dalam praktik, μ = 0.9 adalah nilai default yang umum.

Apa itu optimasi konveks?

Optimasi konveks (convex optimization) adalah masalah meminimalkan fungsi konveks pada himpunan konveks. Sebuah fungsi disebut konveks kalau garis lurus di antara dua titik mana pun pada grafiknya tidak pernah turun ke bawah grafik itu, sehingga fungsinya hanya punya satu mangkuk tanpa dasar palsu. Setiap minimum lokal pada masalah konveks adalah minimum global, jadi masalah ini bisa diselesaikan dengan andal.

Banyak model ML klasik bersifat konveks: regresi linear dan logistik, ridge dan lasso, serta support vector machine. Pada model-model ini, training menemukan parameter terbaik di mana pun titik awalnya. Deep network tidak konveks, jadi permukaan loss-nya punya minimum lokal, saddle point, dan daerah datar. Mengetahui sifat mana yang hilang menjelaskan kenapa inisialisasi, momentum, dan pilihan learning rate begitu berpengaruh pada network seperti ini.

Ide utama

  • Fungsi konveks berada di bawah setiap tali busur antara dua titik pada grafiknya.
  • Pada masalah konveks, setiap minimum lokal adalah minimum global.
  • Fungsi yang dua kali terdiferensialkan bersifat konveks kalau turunan keduanya, atau Hessian-nya, non-negatif di semua titik.
  • Fungsi non-konveks bisa punya banyak minimum lokal, dan titik awal menentukan minimum mana yang ditemukan gradient descent.
  • Saddle point punya gradient nol, tetapi melengkung ke atas di sebagian arah dan ke bawah di arah lain.
  • Momentum merata-ratakan gradient sebelumnya, sehingga optimizer terbantu menggelinding melewati tonjolan kecil dan daerah datar.

Pertanyaan umum

Model machine learning mana yang punya loss function konveks?

Regresi linear dengan squared error, regresi logistik dengan cross-entropy, regresi ridge dan lasso, serta linear support vector machine semuanya konveks terhadap parameternya. Menambahkan hidden layer dengan aktivasi non-linear merusak konveksitas, karena menukar dua unit hidden menghasilkan kumpulan weight berbeda dengan loss yang sama.

Kenapa neural network bisa dilatih dengan baik walaupun non-konveks?

Network besar tampaknya punya banyak minimum bagus dengan loss yang mirip, jadi mendarat di salah satunya biasanya sudah cukup. Sebagian besar titik kritis yang buruk di dimensi tinggi adalah saddle point, bukan minimum, dan gradient yang ber-noise bisa melewatinya. Over-parameterization juga cenderung menghubungkan solusi-solusi bagus lewat jalur dengan loss rendah.

Apa itu himpunan konveks?

Sebuah himpunan bersifat konveks kalau ruas garis lurus di antara dua titik mana pun di dalamnya tetap berada di dalam himpunan itu. Bola, kotak, half-space, dan probability simplex bersifat konveks; cincin atau bulan sabit tidak. Optimasi konveks membutuhkan fungsi objektif yang konveks dan feasible set yang konveks.

Bagaimana masalah konveks diselesaikan dalam praktik?

Masalah yang mulus memakai metode gradient atau metode Newton; masalah dengan constraint sering memakai interior-point method. Pustaka seperti CVXPY memungkinkan kamu menulis masalah dalam bentuk matematis lalu meneruskannya ke solver. Untuk masalah ML berskala besar, metode orde pertama seperti SGD atau coordinate descent biasanya lebih dipilih karena setiap langkahnya murah.

Penjelasan terkait

Referensi

  1. Boyd & Vandenberghe, "Convex Optimization", Cambridge University Press (free PDF)
  2. Dauphin et al. (2014), "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization"
  3. Li et al. (2018), "Visualizing the Loss Landscape of Neural Nets"
  4. Goodfellow, Bengio & Courville, "Deep Learning", ch. 8 Optimization for Training Deep Models

Terakhir diperbarui