Optimizasyonda Eyer Noktaları: Nedir ve Neden Önemlidir

Fonksiyonunuzdaki her kısmi türev sıfır olsa bile, bir minimumun yakınında olduğunuz garanti edilmez.

Optimizasyon, bir fonksiyonun en düşük veya en yüksek değerini aramaktır ve kullandığınız her yöntem, gradyanın düz olduğu bir nokta arar. Ancak düz bir gradyan, en iyi cevabı bulduğunuz anlamına gelmez. Bazen bu, tam aynı noktada fonksiyonun bir yönde yukarı, başka bir yönde aşağı gittiği anlamına gelir.

Bu noktaya eyer noktası denir; bir yönde aşağı, diğer yönde yukarı gider ve çevresinde düzdür. Eyer noktalarını tanımak önemlidir çünkü algoritmanız orada takılabilir ve düz bir gradyanı gerçek bir minimumla karıştırabilir.

Bu yazıda, bir eyer noktasını matematiksel olarak nasıl tespit edeceğinizi ve neden optimizasyon algoritmalarını sık sık yanılttığını adım adım anlatacağım.

Eyer Noktası Nedir?

Bir eyer noktasında gradyan sıfırdır; tıpkı minimum veya maksimumda olduğu gibi. Ancak eyer noktası ikisi de değildir.

Fonksiyon, tam aynı noktada bazı yönlerde yukarı, diğerlerinde aşağı doğru kıvrılır. Bir eksen boyunca giderseniz değer artar, başka bir eksen boyunca giderseniz düşer. İsim de buradan gelir — at eyerinin ön ve arka tarafa doğru yukarı, yanlara doğru aşağı kıvrılan şeklinden ödünç alınmıştır.

Bunun nasıl göründüğünü göstermek için kullanacağım basit bir iki değişkenli fonksiyon şudur:

İki değişkenli fonksiyon

Orjinde, (0, 0) noktasında, her iki kısmi türev de sıfıra eşittir; dolayısıyla bu bir kritik noktadır (durağan nokta da denir). x-ekseni boyunca ilerlerseniz, x^2 terimi nedeniyle f artar. y-ekseni boyunca ilerlerseniz, -y^2 terimi nedeniyle f azalır.

Bu fonksiyonu 3B olarak çizdirirseniz, yüzey bir yönde yukarı, diğer yönde aşağı kıvrılır ve eyer noktasına adını veren şekli oluşturur.

f(x, y) = x^2 - y^2 için 3B yüzey grafiği

Aynı fonksiyonun kontur grafiği de yukarıdan bakınca aynı hikayeyi anlatır. Orjin çevresindeki kontur çizgileri, minimum veya maksimumda göreceğiniz kapalı döngüler yerine hiperbol gibidir.

f(x, y) = x^2 - y^2 için kontur grafiği

Tam tanım, alana bağlı olarak biraz değişir. Çok değişkenli kalkülüste, eyer noktası yerel minimum veya maksimum olmayan bir kritik noktadır. Optimizasyon ve oyun teorisinde terim, eğrilik yerine minimaks problemlerine bağlı farklı bir anlam taşıyabilir. Bu ayrıma yazının ilerleyen kısmında değineceğim.

Eyer Noktaları vs. Minima ve Maksima

Eyer noktalarını matematiksel olarak nasıl belirleyeceğinize geçmeden önce, bunların diğer iki tür kritik noktayla nasıl karşılaştırıldığını görmek faydalıdır.

Yerel minimum

Yerel minimumda, fonksiyon yakındaki her yönde artar. Bir kaseyi düşünün — tabandan herhangi bir yöne adım attığınızda yukarı çıkarsınız. f(x, y) = x2 + y2 bu şekilde davranır.

Yerel maksimum

Yerel maksimumda, fonksiyon yakındaki her yönde azalır. Minimumun ayna görüntüsüdür; kase yerine kubbe. f(x, y) = -x2 - y2 orjinden uzaklaştıkça her yönde azalır.

Eyer noktası

Eyer noktasında, fonksiyon bazı yönlerde artar, diğerlerinde azalır. Bu, önceki bölümdeki örnek olan f(x, y) = x2 - y2 fonksiyonunu minimum veya maksimum yerine eyer noktası yapan şeydir: x-ekseni boyunca yukarı, y-ekseni boyunca aşağı gider; hem de aynı noktada.

İşte üçünün yan yana karşılaştırması:

Yerel minimum, yerel maksimum ve eyer noktasının yan yana 3B yüzey grafikleri

Eyer Noktası Nasıl Bulunur

Eyer noktası bulmak; türevleri almak, nerede sıfırlandıklarını bulmak ve sonra fonksiyonun o nokta etrafında nasıl kıvrıldığını incelemekle ilgilidir.

Aynı önceki fonksiyonu kullanacağım:

Başvuru fonksiyonu

İşte süreç, adım adım.

1. İlk kısmi türevleri hesaplayın

y sabit kabul edilerek x'e göre f'in türevini alın, sonra aynısını y için yapın:

İlk kısmi türevlerin hesaplanması

2. Sıfıra eşitleyin

Her iki kısmi türevin aynı anda sıfırlandığı noktayı çözün:

Türevlerin sıfıra eşitlenmesi

Bu, x = 0 ve y = 0 sonucunu verir; dolayısıyla (0, 0) bir kritik noktadır. İlk türevler bunun türünü söylemez.

3. İkinci türevleri hesaplayın

Üçüne ihtiyacınız var: f_x'in x'e göre türevi, f_y 'nin y'ye göre türevi ve karışık türev:

İkinci türevler

4. Kritik noktayı eğrilikle sınıflandırın 

f_xx = 2 pozitiftir; bu nedenle f x-ekseni boyunca yukarı kıvrılır. f_yy = -2 negatiftir; bu nedenle f y-ekseni boyunca aşağı kıvrılır. Aynı noktada bir yön yukarı, diğer yön aşağı kıvrılıyorsa — işte bu eyer noktasıdır.

Bu dört adımlık süreç, iki kez türevlenebilir herhangi bir fonksiyon için çalışır.

Bir sonraki iki bölümde, iki değişkenin ötesine ölçeklenen araçlarla 4. adımı resmileştireceğim: Hessian matrisi ve ikinci türev testi.

Hessian Matrisi Eyer Noktalarını Nasıl Belirler

Hessian matrisi, önceki bölümdeki tüm ikinci türevleri tek bir nesnede toplar ve bir kritik noktanın minimum mu, maksimum mu yoksa eyer mi olduğunu söyleyen araçtır.

İki değişkenli bir fonksiyon için Hessian şu şekildedir:

İki değişkenli bir fonksiyon için Hessian

Her bir eleman eğriliği açıklar: f_xx ve f_yy sırasıyla x ve y eksenleri boyunca eğriliği, f_xy ise bu iki yönün nasıl etkileştiğini tanımlar. Önceki bölümdeki ikinci türevleri yerine koyarsanız, örnek fonksiyonumuzun Hessian'ı şöyle görünür:

Başvuru fonksiyonu için Hessian

Tek başına bir matris pek bir şey anlatmaz. Önemli olan onun özdeğerleridir — fonksiyonun özvektör adı verilen belirli yönler boyunca nasıl kıvrıldığını anlatan sayılar.

• Pozitif bir özdeğer, fonksiyonun ilgili özvektör yönünde yukarı kıvrıldığı anlamına gelir
• Negatif bir özdeğer, fonksiyonun o yönde aşağı kıvrıldığı anlamına gelir
• Pozitif ve negatif özdeğerlerin karışımı, fonksiyonun bazı yönlerde yukarı, bazılarında aşağı kıvrıldığını gösterir (eyer noktası)

Örneğimizin Hessian'ı diyagonal olduğundan, özdeğerler doğrudan diyagonal üzerindedir: 2 ve -2. Özvektörleri x-ekseni ve y-ekseni yönlerini gösterir; bu da önceki bölümde el yordamıyla bulduğunuz eğrilikle birebir aynıdır. f, oradaki özdeğer pozitif olduğu için x boyunca yukarı, oradaki özdeğer negatif olduğu için y boyunca aşağı kıvrılır.

Çoğu fonksiyonun Hessian'ı diyagonal olmayacaktır; dolayısıyla özvektörler x ve y eksenleriyle düzgün hizalanmaz ve onları matrise bakarak okumak yerine doğrudan çözmeniz gerekir. Ancak bir pozitif ve bir negatif özdeğer, bir eyer noktasının üzerinde durduğunuz anlamına gelir.

Eyer Noktaları İçin İkinci Türev Testi

Her seferinde özdeğerleri elle hesaplamanız gerekmez. İki değişkenli fonksiyonlar için, Hessian'ın determinantından türetilen bir kestirme yol vardır — ikinci türev testi.

Aynı ikinci türevleri kullanarak determinant şöyle olur:

Determinant

D, Hessian'ın determinantıdır ve işareti — f_xx'in işaretiyle birlikte — kritik noktayı sınıflandırır:

• D > 0 ve f_xx > 0: Yerel minimum

• D > 0 ve f_xx < 0: Yerel maksimum

• D < 0: Eyer noktası

• D = 0: Belirsiz

Örneğimiz için f_xx = 2, f_yy = -2 ve f_xy = 0'dır:

Başvuru fonksiyonu için ikinci türev testi

D negatiftir, bu nedenle test (0, 0) noktasının bir eyer noktası olduğunu doğrular.

Bu test, önceki bölümdeki özdeğer kuralının, özvektörleri çözmeden hesaplayabileceğiniz bir biçimde yeniden yazılmış halidir. D iki özdeğerin çarpımıdır ve f_xx + f_yy toplamlarıdır. D negatif olduğunda, özdeğerler zıt işaretler taşımak zorundadır ve eyer noktası tam da budur. D sıfır olduğunda, en az bir özdeğer sıfırdır; dolayısıyla o yöndeki eğrilik düzdür ve ne test ne de tek başına özdeğerler orada neler olduğunu söyleyebilir.

Optimizasyonda Eyer Noktaları

Buraya kadar anlatılanların tamamı, zaten elinizde bir fonksiyon varken bir eyer noktasını tanımlamakla ilgiliydi. Ancak optimizasyonda, en iyi noktayı önceden nerede olduğunu bilmeden ararsınız ve gradyan temelli yöntemler durmayı sıfır gradyanla karar verir.

Tam da burada eyer noktaları sorun çıkarır.

Gradyan temelli bir optimize edici, amaç fonksiyonunu en hızlı azaltan yönde hareket eder ve gradyan sıfıra yaklaşana kadar devam eder. Ancak sıfıra yakın bir gradyan, algoritmaya bir minimum mu yoksa bir eyer noktası mı bulduğunu söylemez.

Pozitif eğrilik yönleri fonksiyonu yukarı iter ve algoritma, oraya adım atmanın işleri kötüleştirdiğini zaten öğrenmiştir. Negatif eğrilik yönleri ise hâlâ oradadır ve çıkış yoludur — ancak yalnızca gradyana güvenen bir algoritma, tam eyer noktasında bu yönlerdeki gradyan da sıfıra yakın olduğundan, onları gözden kaçırabilir.

Ayrıca optimizasyonun yavaşladığı yer de burasıdır.

Gradyan büyüklüğü, herhangi bir durağan noktaya yaklaşırken küçülme eğilimindedir; dolayısıyla adımlarını gradyan büyüklüğüne göre ölçekleyen bir algoritma, gerçekten aradığı minimumun yakınında olmasa bile, eyer noktasının yakınında küçük adımlar atar.

Bir durağan nokta bulmak, bir optimizasyonu bitirmekle aynı şey değildir. Sıfıra yakın bir gradyanın bir eyer noktasına mı yoksa bir minimuma mı ait olduğunu söylemenin ve bunu bildikten sonra amacı iyileştirmeye devam eden yönü bulmanın bir yoluna ihtiyacınız vardır.

Makine Öğreniminde Eyer Noktaları

Bir sinir ağının kayıp fonksiyonu, ağdaki her ağırlık ve biasın bir fonksiyonudur; bazen milyonlarca veya milyarlarca boyutludur. İki değişkenli oyuncak bir örnekten çok uzaktır.

Yüksek boyutlu dışbükey olmayan optimizasyon analizinde, Dauphin ve çalışma arkadaşları, boyut sayısı arttıkça kritik noktaların yerel minimum veya maksimumdan çok daha yüksek olasılıkla eyer noktaları olduğunu savunur. Her boyut, eğriliğin her iki yöne de gidebileceği başka bir yön ekler ve bir kritik noktayı minimum yerine eyer yapan şey, yalnızca tek bir negatif eğrilik yönünün bulunmasıdır.

Bu, eğitim sırasında önemlidir çünkü gradyan inişi yalnızca üzerinde durduğu gradyanı görebilir.

Bir eyer noktasının yakınında, gradyan her yönde küçülür — gerçek bir minimuma yaklaşırken göreceğiniz sinyalin aynısı. Eğitim, hiç de optimal olmayan bir bölgede yavaşlayabilir veya takılabilir ve yalnızca kayıp eğrisinden, bir minimumun yakınında mı yoksa bir eyer üzerinde mi olduğunuzu anlamanın yolu yoktur.

Bu nedenle, sinir ağı eğitimi konuşulurken eyer noktaları sık sık yerel minimumlarla birlikte gündeme gelir. Ancak tek engel değillerdir. Kaybolan gradyanlar, kötü koşullandırılmış eğrilik ve arama uzayının ölçeği de yüksek boyutlu optimizasyonu zorlaştırır.

Optimizasyon Algoritmaları Eyer Noktalarıyla Nasıl Baş Eder

Bunların hiçbiri, gradyan temelli eğitimin bir eyer noktasının yakınında mahkûm olduğu anlamına gelmez. Farklı açılardan yardımcı olabilecek birkaç teknik vardır.

Stokastik gradyan inişi

Stokastik gradyan inişi, gradyanı tüm veri kümesi yerine eğitim verilerinin rastgele bir altkümesinden hesaplar ve bu altküme her adımda değişir.

Bunun getirdiği gürültü, tahmin edilen gradyanın, gerçek gradyanın sıfıra yakın olduğu bir bölgede bile, nadiren tam olarak sıfır olmasını sağlar. Bu gürültü, optimize ediciyi bir eyer noktasından itmeye ve gradyanın kaybolduğu yerde oyalanmak yerine negatif eğrilik yönüne sokmaya yetecek kadar olabilir.

Momentum

Momentum, geçmiş gradyanların hareketli bir ortalamasını tutar ve bir sonraki adıma yalnızca mevcut olan yerine bunu karar vermede kullanır.

Bir eyer noktasının çevresinde bu önemlidir çünkü optimize edici, oraya varmadan önceki gradyanların taşıdığı hareketle zaten bir yönde ilerleyerek gelir. Bu birikmiş hareket, yerel gradyan sıfıra yaklaştığı anda yavaşlamak yerine, eyer çevresindeki düz bölgeden onu taşıyabilir.

İkinci mertebe yöntemler

İkinci mertebe yöntemler, eğrilik bilgisini doğrudan kullanır.

Hessian ya da onun bir yaklaşımıyla çalışarak, bu yöntemler bir kritik noktada pozitif eğrilik yönleriyle negatif eğrilik yönleri arasındaki farkı ayırt edebilir. Eyer noktası bu ayrıma dayanır; dolayısıyla ikinci mertebe bir yöntem, azalan yönü tanımlayıp o yöne adım atabilir; her sıfıra yakın gradyanı aynı şekilde ele almak yerine.

Eyer Noktaları ve İlgili Kavramlar

Eyer noktalarıyla sıkça karıştırılan birkaç terim var; bunlara değinmeye değer.

Eyer noktası vs. yerel minimum

Yerel minimum, çevresinde her yönde yukarı kıvrılır; yani her tarafta tutarlı biçimde pozitif eğrilik vardır. Eyer noktası ise yalnızca bazı yönlerde yukarı, diğerlerinde aşağı kıvrılır. Negatif eğrilik olan tek bir yön bulduğunuz anda artık bir minimuma bakmıyorsunuz demektir.

Eyer noktası vs. yerel maksimum

Yerel maksimum için de aynı mantık tersinden geçerlidir. Çevresinde her yönde eğrilik negatiftir. Eyer noktası, negatif olanların yanına en az bir pozitif eğrilik yönü ekler.

Eyer noktası vs. eğrilik değişim noktası

Eğrilik değişim noktası tek boyutlu bir fikirdir. Bir eğrinin tek bir değişken boyunca konkav yukarıdan konkav aşağıya (veya tersi) geçtiği yerdir.

Eyer noktası en az iki değişken gerektirir; çünkü tüm kavram, aynı noktada farklı yönlerdeki eğriliği karşılaştırmaya dayanır. Tek değişkenli bir fonksiyonun eğrilik değişim noktası olabilir; fakat eyer noktası olamaz; zira diğer yöne kıvrılacak ikinci bir yön yoktur.

Eyer noktası vs. durağan nokta

Her eyer noktası bir durağan noktadır; çünkü orada gradyan sıfırdır. Ancak tersi doğru değildir. Durağan nokta, yalnızca gradyanın sıfır olduğu herhangi bir noktadır — yerel minimum, yerel maksimum veya eyer noktası olabilir. Hangisiyle karşı karşıya olduğunuzu bilmek için Hessian'dan ya da ikinci türev testinden gelen eğrilik bilgisine ihtiyacınız vardır.

İşte bunların nasıl karşılaştırıldığına daha görsel bir bakış:

Eyer noktalarının diğer kavramlarla karşılaştırması

Minimaks Optimizasyonda Eyer Noktaları

Buraya kadar "eyer noktası" terimi, bir kritik noktanın eğriliğini tanımlamak için kullanıldı. Oyun teorisinden gelen ikinci, daha eski bir anlamı daha vardır ve modern makine öğreniminde de karşımıza çıkar.

Minimaks optimizasyonda bir oyuncu bir fonksiyonu minimize ederken diğeri maksimize eder ve eyer noktası, taraflardan hiçbirinin tek başına kendi hamlesini değiştirerek sonucunu iyileştiremeyeceği değerler çiftidir.

Oyun teorisi bunu rekabetçi oyunlarda denge stratejilerini tanımlamak için kullanır. Çekişmeli optimizasyon, bir sürecin diğerinin savunmak zorunda olduğu en kötü durumu aradığı problemler için aynı yapıyı ödünç alır.

Üretici çekişmeli ağlar (GAN'ler) en iyi makine öğrenimi örneğidir. Bir üretici, inandırıcı sahte veriler üreterek kaybını minimize ederken; bir ayırt edici, gerçek veriyi sahte olandan ayırma yeteneğini maksimize eder. Bir GAN'i eğitmek, bu minimaks anlamında bir eyer noktası, yani üretici ve ayırt edicinin birbirlerine karşı en iyi yanıtlarını buldukları bir denge aramak demektir.

Bu minimaks eyer noktası, bu yazının önceki kısımlarındaki kritik nokta eyer noktasıyla ilişkilidir; ancak ikisi birbirinin yerine geçmez.

Kritik nokta versiyonu, tek bir fonksiyonun tek bir noktasındaki eğriliği tanımlar. Minimaks versiyonu, iki rakip amaç arasındaki dengeyi açıklar. Her ikisi de aynı kelimeyi kullanır çünkü ikisi de "yukarı" ve "aşağı" davranışın bir karışımını içerir; ancak bir Hessian tabanlı testi iki oyunculu bir oyuna uygulamaya kalkarsanız, bunları birbirine karıştırmak işe yaramaz.

Eyer Noktalarıyla Çalışırken Yapılan Yaygın Hatalar

Eyer noktası karmaşasının çoğu, birkaç tekrar eden hataya dayanır. Bilmeniz gerekenler şunlardır.

Sıfır gradyanın minimum olduğu varsayımı

Sıfır gradyan yalnızca bir kritik nokta bulduğunuzu söyler; türünü değil. İşinizin bittiğini varsaymadan önce eğriliği kontrol edin; çünkü bir eyer noktasında da gradyan sıfırdır.

Yalnızca birinci türevlerle sınıflandırma

Birinci türevler kritik noktaları bulur; ancak onları sınıflandıramaz. Bir minimumu maksimumdan ve eyer noktasından ayırmak için Hessian ya da ikinci türev testi üzerinden ikinci türevlere ihtiyacınız vardır.

Farklı eğrilik yönlerini yok sayma

Bir fonksiyon, x-ekseni boyunca yukarı kıvrılıyor olsa bile, başka bir yönde aşağı kıvrılıyorsa genel olarak hâlâ bir eyer noktası olabilir. Her yönü kontrol edin ya da hepsini birden kapsayan Hessian'ın özdeğerlerini kullanın.

Eyer noktalarını eğrilik değişim noktalarıyla karıştırma

Eğrilik değişim noktası, tek bir değişkende eğriliğin değişimini açıklar. Eyer noktası ise aynı noktada birden çok değişken boyunca karışık eğriliği açıklar. Genel fikirde akrabadırlar; ancak aynı tür fonksiyona uygulanmazlar ve arkalarındaki matematik birbirinin yerine geçmez.

"Eyer noktası"nın tüm kullanımlarını aynı görmek

Kritik nokta eyer noktası ile minimaks eyer noktası bir ismi paylaşır; bir tanımı değil. Hessian tabanlı bir testi veya özdeğer argümanını uygulamadan önce, hangi anlamın söz konusu olduğunu kontrol edin — oyun teorisi ve çekişmeli optimizasyon minimaks versiyonu kullanır ve bu, tek bir fonksiyondaki eğrilik kontrolüne indirgenemez.

Sonuç

Bir eyer noktası, aynı koordinatlarda bazı yönlerde yukarı, bazılarında aşağı kıvrılır — bu yüzden, gradyan orada da tıpkı diğerlerinde olduğu gibi sıfıra gitmesine rağmen, ne minimumdur ne maksimum.

Gradyanlar kritik noktayı bulur. Hessian'ın özdeğerleri veya ikinci türev testi ise hangisine sahip olduğunuzu söyler. Yüksek boyutlarda bu ayrım çok önemlidir; çünkü eyer noktalarının sayısı yerel minimumlardan fazladır ve SGD ile momentum gibi eğitim algoritmaları kısmen bunların üstesinden gelmek için vardır.

Ayrı tutmanız gereken son bir şey de oyun teorisi ve GAN'lerdeki minimaks eyer noktasının ismi ortak olsa da matematiğinin farklı olduğudur — bu yüzden hangisinden bahsettiğinizi netleştirdiğinizden emin olun.

Eyer noktalarının ardındaki fikri ilginç buluyorsanız, Python ile Derin Öğrenme Yolumuzu seveceksiniz. Kuramın yanında, farklı türdeki problemler için PyTorch kullanarak sinir ağları oluşturacaksınız.