Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
460 kez görüntülendi
Ingilizcede gradient descent diye gecen algoritma nasil calisir ?
Teorik Bilgisayar Bilimi kategorisinde (1.6k puan) tarafından  | 460 kez görüntülendi

1 cevap

1 beğenilme 0 beğenilmeme

"Eğim iniş" algoritması olarak da bilinen bu yöntem, bir $f$ fonksiyonunun minimum değerini bulmak amacıyla kullanılır. Ama her zaman bu amaca erişemezsiniz, bulduğunuz minimum yerel minimum da olabilir. Başka numaralar yapmayıp sadece saf haliyle eğim iniş algoritmasını kullanıyorsanız, bulduğunuz yerel minimumun aynı zamanda global minimum olması için dua etmekten başka yapacak birşeyiniz yok malesef. Algoritmayı açıklamaya çalışayım.

Öncelikle kolaylık olsun diye tek değişkenli fonksiyon alalım, $f(x)$ olsun. Bunu minimum yapan $x$ değerini bulmak istiyoruz.

Fonksiyonun kapalı formunu biliyorsak kolay. Türevini alıp sıfıra eşitlersiniz ve yerel maksimum ya da minimum noktalarını bulursunuz. Sonra gerekirse ikinci türev alırsınız, bu $x$ değeri için ikinci türev negatifse maksimum, pozitifse minimum nokta olduğuna karar verirsiniz.

Çoğu uygulamada fonksiyonun kapalı formu bilinmez, ya da türevini almak için çok karmaşıktır. O zaman şöyle basit bir yöntem uygularsınız: rastgele bir $x_0$ noktası alırsınız ve bu noktada $f'(x_0)$ değerini hesaplarsınız. Bu değer pozitifse, fonksiyon $x_0$ noktası civarında artıyor demektir, negatifse azalıyor demektir. Artıyorsa, yerel minimum nokta soldadır(!), azalıyorsa sağdadır(!). 

Yani diyelim fonksiyon artıyor; $f'(x_0)>0$. O zaman $x_0$'ı azıcık azaltırsak, minimuma daha yakın bir nokta buluruz. Eğer fonksiyon azalıyorsa, $x_0$'ı azıcık artırırsak, minimuma daha yaklaşırız. O zaman şöyle bir tanım yapalım:

$$x_1=x_0-\alpha f'(x_0)$$

Burada $\alpha>0$ küçük(!) bir sayı. Dikkat ederseniz, $f'(x_0)>0$ ise $x_1$ değeri, $x_0$'dan azıcık küçük; $f'(x_0)<0$ ise $x_1$ değeri, $x_0$'dan azıcık büyük. Yani tam da istediğimiz gibi, $x_1$, minimum noktaya $x_0$'dan daha yakın.

Eee madem öyle o zaman aynı şeyi $x_1$ için de yapalım:

$$x_2=x_1-\alpha f'(x_1)$$

Ve böyle devam edelim:

$$x_{i+1}=x_i-\alpha f'(x_i)$$

Burada $x_i$ değerleri yerel minimuma yaklaştıkça $f'(x_i)$ değerleri sıfıra yaklaşır, yani $x_{i+1}$ ile $x_i$ arasındaki fark giderek azalır. Beğendiğiniz bir yerde durabilirsiniz, yerel minimumu yaklaşık olarak bulmuş olursunuz.

Elbette ki burada en önemli parametreler, $x_0$ ve $\alpha$. Bunları biz kafamıza göre seçiyoruz. Ve seçtiğimiz değerlere göre farklı sonuçlar elde edebiliriz. Mesela $\alpha$'yı çok küçük seçerseniz, yerel minimuma yavaş yavaş yaklaşırsınız, bulmanız baya uzun sürebilir. Ama eğer çok büyük seçerseniz, bu sefer de yerel minimumu kaçırabilirsiniz, etrafında dönüp durursunuz.

Bu yöntem üzerine daha birçok şey söylenebilir ama şimdilik burada durup çok değişkenli fonksiyonlardan bahsedelim.

 

Çok değişkenli fonksiyonlar

$f$, $n$ değişkenli bir fonksiyon olsun. Yani, $f=f(x_1,x_2,\ldots,x_n)$ olsun. Bunu minimum yapan $(x_1,x_2,\ldots,x_n)$ değerlerini bulmak istiyoruz. Yazım kolaylığı olsun diye, buna ${\bf x}$ vektörü diyelim ve $n$ boyutlu uzayda bir nokta gibi görelim. Aynı zamanda bunu sütun vektörü olarak göreceğiz, ve $f$'yi de vektör fonksiyonu gibi düşüneceğiz, $f=f({\bf x})$ ve ${\bf x}=[x_1\ \ x_2\ \ \ldots \ \ x_n]^T$. 

Fonksiyonun kapalı formu biliniyorsa kolay. Türevini (yani gradyanını) alıp sıfıra (yani sıfır vektörüne) eşitlersiniz ve $n$ bilinmeyenli $n$ denklemi çözerek yerel minimum adayı noktayı ya da noktaları bulursunuz. Sonra Hessian matrisini yazarsınız, pozitif tanımlı ise yerel minimum noktadır. Ama gördüğümüz gibi, bunlar uzun iş. Eğim iniş ile yaklaşık çözüm bulalım.

Tek değişkenli fonksiyonlarda yaptığımızın neredeyse aynısını yapacağız. Öncelikle rastgele bir ${\bf x}_0$ noktası alalım. $f$ fonksiyonunun gradyanını bulup yerine ${\bf x}_0$ değerlerini yazdığınızda elde ettiğiniz vektör, size $f$'nin en hızlı arttığı yönü verir. Bu vektörü $\nabla f({\bf x}_0)$ ile gösterelim. Bu vektörün tersi yön de $f$'nin en hızlı azaldığı yönü verir. Yani bizim ${\bf x}_0$ noktasını, $-\nabla f({\bf x}_0)$ yönünde azıcık hareket ettirirsek, minimum noktaya yaklaşmış oluruz. O zaman tek değişkenli fonksiyonlarda yaptığımızın aynısını yapalım:

$${\bf x}_1={\bf x}_0-\alpha \nabla f({\bf x}_0)$$

Bunun bir vektör denklemi olduğuna dikkat edin. Elbette burada da $\alpha>0$ küçük bir skaler sayı. Daha genel olarak yazarsak:

$${\bf x}_{i+1}={\bf x}_i-\alpha \nabla f({\bf x}_i)$$

Burada da ${\bf x}_i$ değerleri yerel minimuma yaklaşır. Elbette $\alpha$ ve ${\bf x}_0$ seçimi ile ilgili yukarıda söylediklerim yine geçerli.

Bu algoritma üzerine de çok şey söylenebilir ama burada duralım.

(236 puan) tarafından 
Cok guzel bir cevap olmus. Bir iki sey eklemek istedim. $f$ in konveks oldugunu bildigimiz durumda bildigim kadariyla global ekstremum garantisi veriyor bu algoritma. Armijo ve Wolfe kurallarina bakabilirsiniz $\alpha$ yi secmek icin.
Evet, $f$ konveks ise tek bir yerel minimumu vardır diye biliyorum ben de.
20,200 soru
21,726 cevap
73,275 yorum
1,887,770 kullanıcı