Saddle Point dalam Optimisasi: Apa Itu dan Mengapa Penting

Bahkan jika setiap turunan parsial pada fungsi Anda bernilai nol, Anda tidak dijamin berada dekat titik minimum.

Optimisasi adalah pencarian nilai terendah atau tertinggi dari suatu fungsi, dan setiap metode yang Anda gunakan mencari titik tempat gradiennya datar. Namun, gradien yang datar tidak menjamin Anda telah menemukan jawaban terbaik. Terkadang itu berarti fungsi naik pada satu arah dan turun pada arah lain, tepat pada titik yang sama.

Titik itu disebut saddle point dan turun pada satu arah, naik pada arah lain, serta datar di sekelilingnya. Mengenali saddle point penting karena algoritme Anda bisa terpaku di sana dan menyalahartikan gradien datar sebagai minimum sebenarnya.

Dalam artikel ini, saya akan memandu Anda cara mengenali saddle point secara matematis dan mengapa sering membingungkan algoritme optimisasi.

Apa Itu Saddle Point?

Pada saddle point, gradien bernilai nol, sama seperti pada minimum atau maksimum. Namun, saddle point bukan keduanya.

Fungsi melengkung ke atas pada beberapa arah dan ke bawah pada arah lain, tepat pada titik yang sama. Jika Anda bergerak sepanjang satu sumbu, nilainya naik, dan jika Anda bergerak sepanjang sumbu lain, nilainya turun. Itulah gagasan di balik namanya—mengacu pada bentuk pelana kuda, yang melengkung ke atas ke arah depan dan belakang serta ke bawah ke arah samping.

Berikut fungsi dua variabel sederhana yang akan saya gunakan untuk menunjukkan tampilannya:

Fungsi dua variabel

Di titik asal, (0, 0), kedua turunan parsial bernilai nol, sehingga ini adalah titik kritis (juga disebut titik stasioner). Bergerak sepanjang sumbu x, f meningkat karena suku x^2. Bergerak sepanjang sumbu y, f menurun karena suku -y^2 .

Jika Anda memplot fungsi ini dalam 3D, permukaannya melengkung ke atas pada satu arah dan ke bawah pada arah lain, membentuk bentuk yang menjadi asal nama saddle point.

Plot permukaan 3D f(x, y) = x^2 - y^2

Plot kontur dari fungsi yang sama menyampaikan hal serupa dari atas. Garis kontur di sekitar titik asal tampak seperti hiperbola, bukan loop tertutup yang Anda lihat di sekitar minimum atau maksimum.

Plot kontur f(x, y) = x^2 - y^2

Definisi persisnya sedikit berbeda tergantung bidangnya. Dalam kalkulus multivariabel, saddle point adalah titik kritis yang bukan minimum atau maksimum lokal. Dalam optimisasi dan teori permainan, istilah ini bisa bermakna berbeda, terkait masalah minimax alih-alih kelengkungan. Saya akan membahas perbedaan itu nanti di artikel ini.

Saddle Point vs. Minimum dan Maksimum

Sebelum Anda masuk ke cara mengidentifikasi saddle point secara matematis, ada baiknya melihat perbandingannya dengan dua jenis titik kritis lainnya.

Minimum lokal

Pada minimum lokal, fungsi meningkat pada setiap arah di sekitarnya. Bayangkan mangkuk—ketika Anda melangkah menjauh dari dasar ke arah mana pun, Anda naik. Fungsi f(x, y) = x2 + y2 berperilaku seperti ini.

Maksimum lokal

Pada maksimum lokal, fungsi menurun pada setiap arah di sekitarnya. Ini adalah bayangan cermin dari minimum, kubah alih-alih mangkuk. Fungsi f(x, y) = -x2 - y2 menurun pada setiap arah saat Anda menjauh dari titik asal.

Saddle point

Pada saddle point, fungsi meningkat pada beberapa arah dan menurun pada arah lain. Itulah yang membuat f(x, y) = x2 - y2, contoh pada bagian sebelumnya, menjadi saddle point alih-alih minimum atau maksimum: naik sepanjang sumbu x dan turun sepanjang sumbu y, pada titik yang sama.

Berikut perbandingan ketiganya berdampingan:

Plot permukaan 3D berdampingan dari minimum lokal, maksimum lokal, dan saddle point

Cara Menemukan Saddle Point

Menemukan saddle point bergantung pada mengambil turunan, mencari di mana turunan itu lenyap, lalu melihat bagaimana fungsi melengkung di sekitar titik tersebut.

Saya akan menggunakan fungsi yang sama seperti sebelumnya:

Fungsi referensi

Berikut prosesnya, langkah demi langkah.

1. Hitung turunan parsial pertama

Ambil turunan f terhadap x dengan memperlakukan y sebagai konstanta, lalu lakukan hal yang sama untuk y:

Menghitung turunan parsial pertama

2. Samakan dengan nol

Cari titik tempat kedua turunan parsial lenyap sekaligus:

Menyamakan turunan dengan nol

Itu menghasilkan x = 0 dan y = 0, sehingga (0, 0) adalah titik kritis. Turunan pertama tidak akan memberi tahu jenisnya.

3. Hitung turunan kedua

Anda memerlukan tiga di antaranya: turunan f_x terhadap x, turunan f_y terhadap y, dan turunan campuran:

Turunan kedua

4. Klasifikasikan titik kritis menggunakan kelengkungan 

f_xx = 2 bernilai positif, sehingga f melengkung ke atas sepanjang sumbu x. f_yy = -2 bernilai negatif, sehingga f melengkung ke bawah sepanjang sumbu y. Satu arah melengkung ke atas, arah lain melengkung ke bawah, pada titik yang sama—itulah saddle point.

Proses empat langkah ini berlaku untuk fungsi yang terdiferensialkan dua kali.

Pada dua bagian berikutnya, saya akan memformalkan langkah 4 dengan alat yang skala melampaui dua variabel: matriks Hessian dan uji turunan kedua.

Bagaimana Matriks Hessian Mengidentifikasi Saddle Point

Matriks Hessian menyatukan semua turunan kedua dari bagian terakhir ke dalam satu objek, dan inilah alat yang memberi tahu Anda apakah suatu titik kritis adalah minimum, maksimum, atau saddle.

Untuk fungsi dua variabel, Hessian terlihat seperti ini:

Hessian untuk fungsi dua variabel

Setiap entri menggambarkan kelengkungan: f_xx dan f_yy menggambarkan kelengkungan sepanjang sumbu x dan y, dan f_xy menggambarkan bagaimana kedua arah itu saling berinteraksi. Jika Anda memasukkan turunan kedua dari bagian sebelumnya, Hessian untuk fungsi contoh kita terlihat seperti ini:

Hessian untuk fungsi referensi

Matriks itu sendiri tidak banyak memberi tahu. Yang penting adalah nilai eigen—angka yang menggambarkan bagaimana fungsi melengkung sepanjang sekumpulan arah khusus yang disebut vektor eigen.

• Nilai eigen positif berarti fungsi melengkung ke atas sepanjang arah vektor eigennya
• Nilai eigen negatif berarti fungsi melengkung ke bawah sepanjang arah tersebut
• Campuran nilai eigen positif dan negatif berarti fungsi melengkung ke atas pada beberapa arah dan ke bawah pada arah lain (saddle point)

Karena Hessian contoh kita bersifat diagonal, nilai eigennya berada tepat pada diagonal: 2 dan -2. Vektor eigennya mengarah sepanjang sumbu x dan sumbu y, yang persis sesuai dengan kelengkungan yang Anda temukan secara manual pada bagian sebelumnya. f melengkung ke atas sepanjang x karena nilai eigennya di sana positif, dan ke bawah sepanjang y karena nilai eigennya di sana negatif.

Kebanyakan fungsi tidak memiliki Hessian diagonal, sehingga vektor eigennya tidak akan selaras rapi dengan sumbu x dan y, dan Anda perlu menyelesaikannya secara langsung alih-alih membacanya dari matriks. Namun satu nilai eigen positif dan satu nilai eigen negatif berarti Anda berada pada saddle point.

Uji Turunan Kedua untuk Saddle Point

Anda tidak perlu menghitung nilai eigen secara manual setiap kali. Untuk fungsi dua variabel, ada jalan pintas—uji turunan kedua—yang dibangun dari determinan Hessian.

Berikut determinannya, menggunakan turunan kedua yang sama seperti sebelumnya:

Determinan

D adalah determinan dari Hessian, dan tandanya—dikombinasikan dengan tanda f_xx—mengklasifikasikan titik kritis:

• D > 0 dan f_xx > 0: Minimum lokal

• D > 0 dan f_xx < 0: Maksimum lokal

• D < 0: Saddle point

• D = 0: Tidak konklusif

Untuk contoh kita, f_xx = 2, f_yy = -2, dan f_xy = 0:

Uji turunan kedua untuk fungsi referensi

D bernilai negatif, sehingga uji ini menegaskan bahwa (0, 0) adalah saddle point.

Uji ini adalah aturan nilai eigen dari bagian sebelumnya, ditulis ulang dalam bentuk yang dapat Anda hitung tanpa menyelesaikan vektor eigen. D adalah hasil kali dua nilai eigen, dan f_xx + f_yy adalah jumlahnya. Ketika D negatif, nilai eigennya harus bertanda berlawanan, dan itulah definisi saddle point. Ketika D nol, setidaknya satu nilai eigen adalah nol, sehingga kelengkungan pada arah itu datar, dan baik uji ini maupun nilai eigen saja tidak dapat memberi tahu apa yang terjadi di sana.

Saddle Point dalam Optimisasi

Semua pembahasan sejauh ini adalah tentang mengidentifikasi saddle point ketika Anda sudah memiliki sebuah fungsi. Namun dalam optimisasi, Anda mencari titik terbaik tanpa mengetahui sebelumnya di mana letaknya, dan metode berbasis gradien menggunakan gradien nol untuk memutuskan kapan harus berhenti.

Di situlah saddle point menimbulkan masalah.

Pengoptimal berbasis gradien bergerak ke arah yang paling cepat mengurangi fungsi objektif, dan terus bergerak hingga gradien mendekati nol. Namun gradien yang hampir nol tidak memberi tahu algoritme apakah ia menemukan minimum atau saddle point.

Arah dengan kelengkungan positif mendorong fungsi naik, dan algoritme sudah belajar bahwa melangkah ke sana membuat keadaan memburuk. Arah dengan kelengkungan negatif tetap ada, dan itulah jalan keluarnya—tetapi algoritme yang hanya mengandalkan gradien bisa melewatkannya, karena tepat di saddle point, gradien pada arah-arah itu juga mendekati nol.

Di sinilah optimisasi juga melambat.

Magnitudo gradien cenderung menyusut saat Anda mendekati titik stasioner mana pun, sehingga algoritme yang menskalakan langkahnya terhadap besar gradien akan mengambil langkah kecil di dekat saddle, terlepas dari apakah itu dekat dengan minimum yang sebenarnya dicari atau tidak.

Menemukan titik stasioner tidak sama dengan menyelesaikan optimisasi. Anda masih memerlukan cara untuk memastikan bahwa gradien yang hampir nol berasal dari saddle point dan bukan minimum, serta cara menemukan arah yang terus memperbaiki objektif setelah Anda mengetahuinya.

Saddle Point dalam Pembelajaran Mesin

Fungsi loss jaringan saraf adalah fungsi dari setiap bobot dan bias dalam jaringan, terkadang berukuran jutaan atau miliaran dimensi. Jauh dari contoh dua variabel sederhana.

Dalam analisis optimisasi non-konveks berdimensi tinggi, Dauphin dan kolega berargumen bahwa seiring bertambahnya jumlah dimensi, titik kritis jauh lebih mungkin menjadi saddle point daripada minimum atau maksimum lokal. Setiap dimensi menambah satu arah lagi tempat kelengkungan bisa ke salah satu sisi, dan hanya butuh satu arah kelengkungan negatif untuk menjadikan titik kritis sebagai saddle alih-alih minimum.

Hal ini penting selama pelatihan karena penurunan gradien hanya dapat melihat gradien tempat ia berada saat ini.

Di dekat saddle point, gradien mengecil ke segala arah—sinyal yang sama seperti saat mendekati minimum sebenarnya. Pelatihan bisa melambat atau terjebak di wilayah yang sama sekali tidak optimal, dan tidak ada cara untuk mengetahuinya hanya dari kurva loss apakah Anda dekat minimum atau terjebak di saddle.

Inilah mengapa saddle point sering muncul bersamaan dengan minimum lokal saat orang membahas pelatihan jaringan saraf. Namun itu bukan satu-satunya hambatan. Gradien yang menghilang, kelengkungan yang buruk kondisinya, dan skala ruang pencarian semuanya membuat optimisasi berdimensi tinggi menjadi sulit.

Bagaimana Algoritme Optimisasi Menangani Saddle Point

Semua ini tidak berarti pelatihan berbasis gradien pasti gagal di dekat saddle point. Ada beberapa teknik yang dapat membantu Anda melewatinya, masing-masing dari sudut yang berbeda.

Stochastic gradient descent

Stochastic gradient descent menghitung gradien dari subset acak data pelatihan alih-alih seluruh dataset, dan subset itu berubah pada setiap langkah.

Kebisingan yang diperkenalkan membuat estimasi gradien jarang sekali tepat nol, bahkan di wilayah tempat gradien sebenarnya mendekati nol. Kebisingan itu bisa cukup untuk mendorong pengoptimal keluar dari saddle point dan memasuki arah kelengkungan negatif, alih-alih macet tepat saat gradien lenyap.

Momentum

Momentum menyimpan rata-rata berjalan dari gradien masa lalu dan menggunakannya, bukan hanya gradien saat ini, untuk menentukan langkah berikutnya.

Di sekitar saddle point, ini penting karena pengoptimal tiba dengan sudah bergerak ke arah tertentu, dibawa oleh gradien sebelum ia sampai di sana. Gerakan terakumulasi itu dapat membawanya melewati wilayah datar di sekitar saddle, alih-alih melambat begitu gradien lokal mendekati nol.

Metode orde dua

Metode orde dua menggunakan informasi kelengkungan secara langsung.

Dengan bekerja menggunakan Hessian atau pendekatannya, metode ini dapat membedakan antara arah kelengkungan positif dan arah kelengkungan negatif pada titik kritis. Itulah perbedaan yang menjadi inti saddle point, sehingga metode orde dua dapat mengidentifikasi arah menurun dan melangkah ke sana, alih-alih memperlakukan setiap gradien yang hampir nol dengan cara yang sama.

Saddle Point vs. Konsep Terkait

Beberapa istilah sering tertukar dengan saddle point sehingga layak dibahas.

Saddle point vs. minimum lokal

Minimum lokal melengkung ke atas pada setiap arah di dekatnya, sehingga kelengkungannya positif secara konsisten, ke segala arah. Saddle point hanya melengkung ke atas pada beberapa arah dan ke bawah pada arah lain. Begitu Anda menemukan satu saja arah dengan kelengkungan negatif, Anda tidak sedang melihat minimum lagi.

Saddle point vs. maksimum lokal

Logika yang sama berlaku sebaliknya untuk maksimum lokal. Kelengkungan tetap negatif pada setiap arah di dekatnya. Saddle point menambahkan setidaknya satu arah kelengkungan positif di samping yang negatif.

Saddle point vs. titik belok

Titik belok adalah gagasan satu dimensi. Ini adalah titik tempat kurva beralih dari cekung ke atas ke cekung ke bawah, atau sebaliknya, sepanjang satu variabel.

Saddle point memerlukan setidaknya dua variabel, karena seluruh konsepnya bergantung pada membandingkan kelengkungan di berbagai arah pada titik yang sama. Fungsi satu variabel dapat memiliki titik belok, tetapi tidak dapat memiliki saddle point, karena tidak ada arah kedua untuk melengkung ke sisi lain.

Saddle point vs. titik stasioner

Setiap saddle point adalah titik stasioner, karena gradien di sana bernilai nol. Namun sebaliknya tidak benar. Titik stasioner hanyalah titik mana pun tempat gradien bernilai nol—bisa berupa minimum lokal, maksimum lokal, atau saddle point. Anda memerlukan informasi kelengkungan dari Hessian atau uji turunan kedua untuk mengetahui yang mana yang Anda miliki.

Berikut gambaran yang lebih visual tentang perbandingannya:

Perbandingan saddle point dengan konsep lain

Saddle Point dalam Optimisasi Minimax

Sejauh ini, "saddle point" digunakan untuk menggambarkan kelengkungan titik kritis. Ada makna kedua yang lebih lama dari teori permainan, dan muncul juga dalam pembelajaran mesin modern.

Dalam optimisasi minimax, satu pemain meminimalkan suatu fungsi sementara pemain lain memaksimalkannya, dan saddle point adalah pasangan nilai tempat tidak ada pemain yang dapat memperbaiki hasilnya dengan mengubah geraknya sendiri saja.

Teori permainan menggunakan ini untuk menggambarkan strategi ekuilibrium dalam permainan kompetitif. Optimisasi adversarial meminjam struktur yang sama untuk masalah di mana satu proses mencari kasus terburuk yang harus dipertahankan oleh proses lain.

Generative adversarial networks (GAN) adalah contoh pembelajaran mesin terbaik. Generator meminimalkan loss-nya dengan menghasilkan data palsu yang meyakinkan, sementara diskriminator memaksimalkan kemampuannya membedakan data asli dari yang palsu. Melatih GAN berarti mencari saddle point dalam arti minimax ini, atau keseimbangan tempat generator dan diskriminator masing-masing menemukan respons terbaik terhadap yang lain.

Saddle point minimax ini terkait dengan saddle point titik kritis dari awal artikel, tetapi keduanya tidak dapat dipertukarkan.

Versi titik kritis menggambarkan kelengkungan pada satu titik dari satu fungsi. Versi minimax menggambarkan ekuilibrium antara dua objektif yang bersaing. Keduanya menggunakan kata yang sama karena sama-sama melibatkan campuran perilaku "naik" dan "turun", tetapi menyamakannya tidak akan membantu jika Anda mencoba menerapkan uji berbasis Hessian pada permainan dua pemain.

Kesalahan Umum Saat Bekerja dengan Saddle Point

Kebingungan tentang saddle point umumnya bermuara pada beberapa kesalahan berulang. Berikut yang perlu Anda ketahui.

Mengasumsikan gradien nol berarti minimum

Gradien nol hanya memberi tahu bahwa Anda menemukan titik kritis, bukan jenisnya. Periksalah kelengkungan sebelum berasumsi Anda sudah selesai karena saddle point juga memiliki gradien nol.

Mengklasifikasikan titik hanya dengan turunan pertama

Turunan pertama menemukan titik kritis tetapi tidak dapat mengklasifikasikannya. Anda memerlukan turunan kedua, melalui Hessian atau uji turunan kedua, untuk membedakan minimum dari maksimum dan dari saddle point.

Mengabaikan perbedaan arah kelengkungan

Sebuah fungsi dapat melengkung ke atas sepanjang sumbu x dan tetap menjadi saddle point secara keseluruhan, jika ada arah lain yang melengkung ke bawah. Periksa setiap arah, atau gunakan nilai eigen dari Hessian, yang mencakup semuanya sekaligus.

Menyamakan saddle point dengan titik belok

Titik belok menggambarkan perubahan kelengkungan pada satu variabel. Saddle point menggambarkan kelengkungan campuran di beberapa variabel pada titik yang sama. Keduanya berhubungan secara gagasan umum, tetapi tidak berlaku pada jenis fungsi yang sama, dan matematikanya tidak dapat dipertukarkan.

Menganggap semua penggunaan "saddle point" identik

Saddle point titik kritis dan saddle point minimax berbagi nama, bukan definisi. Sebelum Anda menerapkan uji berbasis Hessian atau argumen nilai eigen, periksa makna mana yang sebenarnya dimaksud—teori permainan dan optimisasi adversarial menggunakan versi minimax, dan itu tidak dapat direduksi menjadi pemeriksaan kelengkungan pada satu fungsi.

Kesimpulan

Saddle point melengkung ke atas pada beberapa arah dan ke bawah pada arah lain, pada koordinat yang sama—itulah sebabnya ia bukan minimum maupun maksimum, meskipun gradien menjadi nol di sana seperti halnya pada keduanya.

Gradien menemukan titik kritis. Nilai eigen Hessian, atau uji turunan kedua, memberi tahu jenis titik yang Anda dapatkan. Dalam dimensi tinggi, pembedaan itu sangat penting karena saddle point lebih banyak jumlahnya dibanding minimum lokal, dan algoritme pelatihan seperti SGD dan momentum sebagian dibuat untuk melampauinya.

Satu hal terakhir yang perlu dibedakan adalah bahwa saddle point minimax dari teori permainan dan GAN memiliki nama yang sama tetapi bukan matematikanya—jadi pastikan Anda tahu yang mana yang Anda maksud.

Jika Anda tertarik dengan gagasan di balik saddle point, Anda akan menyukai Deep Learning Track in Python kami. Selain teori, Anda akan menggunakan PyTorch untuk membuat jaringan saraf untuk berbagai jenis masalah.