Gradyan ve Gradyan İniş

Gradyan inişi geri yayılımlı yapay sinir ağlarını anlatmaya çalıştığım şu yazıda özetlemiştim. Son zamanlarda kurcaladığım yöntemlerden biri beni temeli gradyana dayanan Lagrange çarpanları yöntemine sürükleyince gradyanı hatırlamak ve gradyan iniş yöntemini detaylandırmak için böyle bir yazı hazırladım. Uzun zamandır faydalı bir şeyler yazacak zaman bulamıyordum zaten.

Bu yazıda bildiklerimizi hatırlamaya, gradyanı ve gradyan inişi ayrıntılı olarak inceleyip kodlarla ve grafiklerle örneklemeye çalışacağız.

Gradyan

En baştan; türevin tanımından başlayalım. Türev, bir fonksiyonun bir değişkeninde meydana gelecek sonsuz küçüklükteki bir değişimin fonksiyonun değerinde meydana getireceği artışın/azalışın, değişkendeki değişime oranıdır. Aşağıdaki şekilde d doğrusunun fonksiyona teğet geçtiği noktayı sonsuz kat büyütme yapan bir mikroskop altında incelediğimizi düşünün. Bu ölçekte f(x) eğrisi düz bir çizgidir. x'e sonsuz küçüklükte bir değer ekleyip, f(x)'te meydana gelecek değişimi x'teki değişime oranladığımızda d doğrusunun eğimini bulmuş oluruz ki bu zaten f(x)'in x noktasındaki türevidir.

O halde tek değişkenli bir fonksiyonun bir noktadaki türevi, temsil ettiği eğriye o noktada teğet olan doğrunun eğimidir. Fonksiyonun ne yönde arttığını anlamak için eğimi kullanabiliriz. Mesela yukarıdaki y=f(x) eğrisinin rastgele bir noktası üzerinde durduğunuzu ve en dip noktaya inmeye çalıştığınızı hayal edin. Bulunduğunuz noktada fonksiyonun türevi, x'i ne yönde değiştirirseniz aşağı veya yukarı çıkacağınızı gösterir. Türev alarak bulduğunuz eğimi azaltmaya yönelik haraket ederseniz (değişkeni eğimin tersi yönünde arttırırsanız) dibe, arttırmaya yönelik haraket ederseniz (değişkeni eğim yönünde arttırırsanız) tepeye çıkabilirsiniz.

Yukarıda tek değişkenli  bir fonksiyondan bahsettik ve y=f(x) olduğu için 2 boyutlu uzaydaydık. Aynı şeyleri 3 boyutlu uzayda hayal edip çok boyutlu uzaylar ve çok değişkenli fonksiyonlar için genellemeye çalışalım. Yeni fonksiyonumuz 3 boyutlu uzayda bir yüzeyi temsil eden z=f(x,y) olsun. Bu durumda değişkenler, 3. boyuttaki z koordinatlarımızı belirliyor. Mantık aynı. Ama bu sefer birden çok değişkenimiz olduğu için türevi her bir değişkene göre ayrı ayrı alıp her adımda diğer değişkenleri sabit kabul ediyoruz. Bu işlemi 3 boyutlu uzaydan 2 boyutlu kesitler almaya benzetebilirsiniz. Bir değişkeni sabit kabul ettiğinizde 2 boyutlu uzaya ilk örnekteki gibi bir eğri düşürürsünüz. İkiden fazla değişkeni olan fonksiyonlar için de aynı şey geçerli.

Fonksiyon kaç değişkenli olursa olsun, bir fonksiyonun kısmi türevlerinin vektörüne gradyan diyoruz. Yine değişken sayısı ne olursa olsun, kısmi türevlerin bileşkesi olan gradyanın yönü, değişkenlerin hangi yönde değişmeleri halinde fonksiyonun artacağını gösterir. O halde gradyan yönünde ilerlenirse maksimuma, gradyanın yönünün tersi takip edilirse minimuma yaklaşılır.

Gradyan hesaplanması gerektiğini göstermek için ters üçgen kullanılır. Nabla veya del işlemcisi olarak anılan bu simge bir fonksiyonun soluna yazıldığında, o fonksiyonun gradyanını temsil eder.

Gradyanın, Lagrange çarpanlarının mantığının altında yatan önemli bir özelliğinden bahsedelim. Yalnız bu özellik bazı kaynaklarda yanlış ifade ediliyor. Kaynaklardan birinde bir yüzeyin bir noktadaki gradyanının, kendisine bu noktada dik olduğunu okumuştum. Bu benim kafamı karıştırıp zaman kaybetmeme neden olmuştu. Çünkü bu ifade doğruysa gradyan iniş mümkün olmaz. 3 boyutlu uzayda bir yüzeyi temsil eden z=f(x,y) fonksiyonunun yalnızca x ve y için kısmi türevlerini alıp fonksiyonu sağlayan bir (x,y) noktasını, türevlerde yerine yazdığımızda bulacağımız gradyan vektörü 2 boyutlu olur ve bu vektör, 3 boyutlu yüzeye değil, f(x,y)=c eğrilerine dik olur ki bu eğriler 2 boyutludur. Eğriler diyoruz çünkü c sonsuz farklı değer alabilir ve sonsuz tane eğri bulabiliriz (bu eğrilere seviye eğrileri deniyor). Yine kaynakların birinde z=f(x,y) fonksiyonunu f(x,y)-z=0 şeklinde kapalı yazdığımızda hesaplayacağımız gradyanın yüzeye dik olacağı yazılmış. f(x,y,z)'nin gradyanı, z=f(x,y)'nin kapalı yazılmış halinin gradyanı değil, 4 boyutlu bir yüzeyi temsil eden bir w=f(x,y,z)'nin gradyanıdır ve f(x,y)-z=0 yüzeyi, w hiperyüzeyinin sonsuz sayıdaki seviye yüzeylerinden sadece bir tanesidir. O halde aslında şöyle bir genelleme doğru olur; n boyutlu uzayda yer alan bir yüzeyin (ki bu yüzey n-1 tane değişkeni olan bir fonksiyonla temsil edilebilir) gradyanı kendisine değil, n-1 boyutlu seviye yüzeylerine (n=3 ise, seviye eğrilerine) dik olur.

Şimdi Matlab'in nimetlerinden faydalanarak 4 boyutlu bir hiperyüzeyin 3 boyutlu bir seviye yüzeyini çizelim, gradyanı hesaplayalım ve seviye yüzeyi üzerinde bir noktada gradyanı çizdirip görelim:

%--------------------------------------
% Bir Hiperyüzeyin Gradyanının Seviye
% Yüzeylerine Dikliği
% Hüseyin Atasoy
% www.atasoyweb.net
% Mart 2015
%--------------------------------------

% Grafiği hazırlayalım:
f=figure;hold on;
set(f,'defaultLineLineWidth',2);

% Kullanacağımız semboller:
syms w x y z;

% w=f(x,y,z)=x*x+y*y-z olsun. w=0 alındığında seviye yüzeyinin denklemi
% z=x*x+y*y olacak. Bu durumda w'nin gradyanının, seviye yüzeyine dik
% olmasını bekliyoruz. Bir bakalım...
w=x*x+y*y-z;

% Kısmi türevler:
dwdx = diff(w,x);
dwdy = diff(w,y);
dwdz = diff(w,z);

% w'yi 0 alarak elde ettiğimiz kapalı haldeki seviye fonksiyonunu
% z'yi çözerek açalım (z=x*x+y*y) ve z yüzeyini x,y değişkenlerine [-1 1]
% aralığında değerler vererek çizdirelim:
z=solve(w,z);
ezsurf(z,[-1,1]);

% Gradyanı çizdireceğimiz rastgele bir nokta belirleyelim:
noktax=0.4;
noktay=0.3;
% x ve y değerlerini yerlerine yazıp noktamızın z koordinatını hesaplayalım:
noktaz=subs(subs(z,x,noktax),y,noktay);

% Ve noktamızı işaretleyelim:
scatter3(noktax,noktay,noktaz);

% Gradyan vektörünün belirlediğimiz noktadaki bileşenlerini hesaplayalım:
% (koordinatları gradyanın bileşenlerinde yerlerine yazıyoruz)
gradx=subs(dwdx,x,noktax);
grady=subs(dwdy,y,noktay);
gradz=subs(dwdz,z,noktaz);

% Bileşenleri çizdirelim:
quiver3(noktax,noktay,noktaz,gradx,0,0);
quiver3(noktax,noktay,noktaz,0,grady,0);
quiver3(noktax,noktay,noktaz,0,0,gradz);

% Ve bileşenlerin bileşkeleri, yani yüzeye dik olmasını beklediğimiz
% gradyan vektörü:
quiver3(noktax,noktay,noktaz,gradx,grady,gradz);

% Grafiği sınırlayıp bakış açısını ayarlayalım:
xlim([-1 1]);
ylim([-1 1]);
zlim([-1 1]);
view(151,8);
axis equal;

Yukarıdaki kod şöyle bir grafik elde etmemizi sağlayacak:

Bu grafik w=x*x+y*y-z ile ifade ettiğimiz bir hiperyüzeyin w=0'daki seviye yüzeyinin grafiği. w=0 iken, w'nin (0.4,0.3) noktasındaki gradyanının, seviye yüzeyine dik olduğunu görebiliyoruz. Buradan artık şöyle bir çıkarım yapabiliyor olmamız gerekiyor: değişkenleri grafikte gördüğümüz 3 bileşen yönünde, yani bileşenlerin bileşkeleri olan gradyan vektörünün yönünde arttırırsak, 4. boyuttaki w ekseni üzerinde pozitif yönde ilerlerleriz. Değişkenleri gradyanın tersi yönünde arttırırsak w ekseni üzerinde bu sefer de negatif yönde ilerleriz.

Yeni bir örnek kodlamamıza gerek kalmadan hayal gücümüzü kullanarak şunu da gözlemleyebiliriz; w=0 iken fonksiyonu açtığımızda z=x*x+y*y fonksiyonunu elde ederiz. Bir boyut daha atarsak z=0.25'teki (gradyanı çizdirdiğimiz noktanın z değeri) seviye yüzeyimizin seviye eğrisi 0.25=x*x+y*y olur ki bu denklem x-y düzleminde bir çemberi temsil ediyor. Aynı noktada seviye yüzeyinin gradyanının x ve y bileşenleri, w hiperyüzeyinin gradyanının x ve y bileşenlerine eşit. Bu durumda yeşil ve kırmızı bileşenlerin bileşkesi çembere dik olur. Böylece seviye yüzeyinin gradyanının, gradyanın hesaplandığı noktadaki seviye eğrisine dik olduğunu da gözümüzde canlandırabiliriz.

Aynı grafikte yüzeyin (w yüzeyinin değil, onun seviye yüzeyi olan z yüzeyinin) gradyanı (yeşil ve kırmızı bileşenlerin bileşkeleri) yönünde ilerlersek yüzey üzerindeki noktaların z değerlerinin arttığını, ters yönde ilerlersek, azaldığını (yüzeyin dibine ilerlediğimizi) görmek de mümkün.

Gradyan İniş

Şimdi gradyan iniş yöntemini incelemeye hazırız. Gradyan iniş, bir fonksiyon üzerinde rastgele bir noktadan başlayıp bu noktanın koordinatlarını, kısmi türevlerin tersi (yani gradyan vektörünün tersi) yönünde değiştirerek küçük adımlarla minimum noktaya yaklaşma yöntemidir. Atılacak adımların büyüklüğünü adım katsayısı adını verdiğimiz çarpan belirler.

Eğim, minimuma yaklaşıldıkça azalarak azalır. Bu durumdan yararlanarak gradyan iniş için bir durdurma kriteri belirleyebiliriz. Çünkü bu durum, minimuma yaklaşıldıkça adımların küçülmesine de neden olur. Son atılan adım büyüklüğü (ne yöne atıldığı önemsiz olduğu için - işaretinden arındırmamız gerekiyor), belirlenen bir değerin altına düştüğünde, minimuma ulaştığımızı kabul edip ilerlemeyi durdurabiliriz. Bu değere duyarlılık adı veriliyor.

Şimdi yöntemi adımlar halinde yazıp kodlamaya geçelim:

1. Başlamak için rastgele bir nokta seç ve durdurma kriteri olarak bir duyarlılık değeri belirle.
2. Noktanın her bir koordinatı için:
   • Koordinat değerini, fonksiyonun o koordinata karşılık gelen değişkenine göre kısmi türevinde yerine yaz.
   • Bulduğun değeri -1 (koordinat değerini ters yönde değiştirmek için) ve adım katsayısı ile çarp.
   • Elde ettiğin değeri koordinat değerine ekle.
   • Atılan adım büyüklüğünü (koordinatın yeni değeri ile eski değeri arasındaki farkın mutlak değeri) hesapla.
   • Her bir koordinat için hesapladığın adım büyüklükleri, belirlediğin duyarlılık değerinin altına düşene kadar 2. adımdan başlayarak buraya kadarki işlemleri tekrar et.

Durdurma kriteri sağlandığında varılan nokta ile fonksiyonun minimum noktası arasında önemsenmeyecek kadar küçük bir fark kalır. Yani aslında fonksiyonun minimum değerinde olmasını sağlayacak değerleri bulmuş oluruz.

Kod Örnekleri

Bilgisayarımda şu an yalnızca Matlab ve bir C++ derleyicisi bulunduğu için örnekleri bu iki dille yazacağım.

Gradyan İniş Matlab Kod Örneği

Matlab bize müthiş olanaklar sunduğu için gradyan inişi örneklerken bir yandan da adım adım minimuma ilerleyişimizi bir grafik üzerine çizdirmeye çalışalım.

%--------------------------------
% Gradyan İniş Matlab Kod Örneği
% Hüseyin Atasoy
% www.atasoyweb.net
% Mart 2015
%--------------------------------

% Bir önceki değer ile son bulduğumuz değer bu duyarlılık değerinin altına
% indiğinde hedefe vardığımızı kabul edeceğiz
duyarlilik=0.01;

% Gradyanın tersi yönünde ilerlerken adımlarımızın büyüklüğünü belirleyecek
% katsayı
adimK=0.1;

% Bu kadar adıma rağmen hala minimumu bulamazsak aramayı durduracağız
maxAdimSayisi=100;

% Kullanacağımız semboller
syms f x y

% Değişkenleri bir dizide tut. Bu diziyi değişkenlerin yerine sayı
% yerleştirirken kullanacağız.
degiskenler=[x y];

% Minimize etmeye çalışacağımız fonksiyon
f=x^2+y^2+1;

% Çizim alanını hazırla. (Birazdan çizdireceğimiz yüzeyi renklendirirsek
% çizgiler çok seçilmediği için sadece gri ve tonları kullanılsın.)
figure,colormap(gray),axis equal,hold on;

% f fonksiyonunun temsil ettiği yüzeyi değişkenlere [-1.1 1.1] aralığında
% değerler vererek çiz.
ezsurf(f,[-1.1 1.1]);

% Yüzeydeki çizgileri kaldırmak için. Kötü görünüyorlar.
sekil=findobj('EdgeColor','black');
set(sekil,'LineStyle','none')

% Gradyanı hesapla. Yani f'in her bir değişkene göre ayrı ayrı kısmi
% türevlerini al.
gradyan=[diff(f,x) diff(f,y)];

% Gradyan inişe hangi noktadan başlayalım. Bu rastgele bir nokta olabilir.
nokta=[1 1];

% Bir önceki noktanın koordinatlarını tutacak.
oncekiNokta=zeros(1,2);
z=1;

% Son konum ile önceki konum arasındaki farkları tutacak. (her bir
% koordinat için ayrı ayrı)
farklar=ones(1,2);

% Kaç adım attığımızı saymak için
adimSayisi=0;

iniseDevam=true;
while iniseDevam && adimSayisi<maxAdimSayisi
    % Tümü duyarlılık değerinin altına inerse inişi durduracağız.
    iniseDevam=false;
    
    for i=1:2 % koordinatlar için
        if farklar(i)>duyarlilik % Sıradaki değişken için
            adimSayisi=adimSayisi+1;

            % İniş durmamalı, en az bir bileşende henüz duyarlılığın
            % altına düşemedik.
            iniseDevam=true;
            
            oncekiNokta=nokta; % Son noktayı saklamak için
            
            % Gradyanın sıradaki bileşeninde sıradaki değişkenin değerini
            % yerine yazıp bileşenin yönünü adım katsayısı ile çarp. Sonra
            % da sıradaki değişkeni ters yönde değiştir.
            nokta(i)=nokta(i)-adimK*subs(gradyan(i),degiskenler(i),nokta(i));

            % Sonraki adımda duyarlılığın altına düşüp düşmediğimizi
            % kontrol etmek için
            farklar(i)=abs(oncekiNokta(i)-nokta(i));
        end
        oncekiZ=z;
        
        % Vardığımız yeri çizebilmemiz için şu anki noktanın koordinatlarını
        % fonksiyonda x ve y yerine yazıp sonucu, yani aslında 3. boyuttaki
        % koordinatı hesapla.
        z=subs(subs(f,x,nokta(1)),y,nokta(2));

        % Son vardığımız noktayı çiz.
        scatter3(nokta(1),nokta(2),z,'ored','filled');

        % İlk adımda çizgi çizdirmeye çalışmayalım diye. Çünkü ilk
        % adımda önceki değerler diye bir şey yok
        if adimSayisi>1
            line([oncekiNokta(1) nokta(1)],[oncekiNokta(2) nokta(2)], ...
                 [oncekiZ z],'Color','cyan','Linewidth',2);
        end
    end
end
view(170,-4); % Şekle, noktaları görebileceğimiz bir açıdan bakalım
fprintf('Atılan adım sayısı: %i\n',adimSayisi);
fprintf('Minimum nokta: (%f,%f)\n',nokta(1),nokta(2));

Adımlarımızın dibe indikçe küçüldüğünü ve inişin zikzaklar çizilerek yapıldığını görebilirsiniz. Adımların neden dibe yaklaştıkça küçüldüğünü söylemiştik. Peki bu zikzakların sebebi ne? Sebep, noktalarımızı gradyanın tersi yönünde bir tam adım atmadan çizdirmemiz. Yani her bir koordinatı karşılık gelen gradyan bileşeninin tersi yönünde arttırıp diğer koordinatlarda da bir adım atılmasını beklemeden o anda vardığımız noktayı çizdiriyoruz. Eğer çizdirme işlemini her seferinde tüm koordinatlar birer adım attığında yapsaydık zikzak değil, minimuma düzenli bir biçimde inen noktalar görürdük.

Adım katsayısı ile oynayarak, küçük değerlerin daha çok sayıda adım atılmasını gerektirdiğini, büyük değerlerinse salınıma neden olabileceğini gözlemleyebilirsiniz.

Gradyan İniş C++ Kod Örneği

Aynı fonksiyonu, aynı adım katsayısını ve duyarlılık değerini kullanarak şimdi de C++ ile minimize etmeye çalışalım. Ama bu sefer Matlab'in sağladığı olanaklardan yoksun olduğumuz için kısmi türevleri elle alıp birer fonksiyon olarak tanımlıyoruz ve inişin grafiğini çizdirmiyoruz.

#include<iostream>
#include<cmath>
using namespace std;

/*******************************
 * Gradyan İniş C++ Kod Örneği
 * Hüseyin Atasoy
 * www.atasoyweb.net
 * Mart 2015
 *******************************/

// Minimize etmeye çalışacağımız fonksiyon. Bu, minimumunu elle de
// hesaplayabileceğimiz oldukça basit bir örnek. Buraya yüzlerce
// değişkene sahip daha karmaşık bir fonksiyon da yazabilirsiniz.
// (Geri yayılımlı yapay sinir ağlarının hata fonksiyonunu hatırlayın
// Orada fonksiyonun yüzlerce, binlerce bilinmeyeni olabiliyor.)
double f(double x, double y)
{
    return x*x+y*y+1;
}

// Gradyanın x bileşeni. Eğer türevde y kalsaydı onu da parametre olarak
// almamız ve işleme dahil etmemiz gerekirdi
double f_gradX(double x)
{
    // Yani f'nin x'e göre kısmi türevi
    return 2*x;
}

// Gradyanın y bileşeni. Eğer türevde x kalsaydı onu da parametre olarak
// almamız ve işleme dahil etmemiz gerekirdi
double f_gradY(double y)
{
    // Yani f'nin y'e göre kısmi türevi
    return 2*y;
}

// noktaX ve noktaY: gradyan inişe hangi noktadan başlayacağımızı belirleyecek.
// Bu rastgele bir nokta olabilir.
// duyarlilik: Bir önceki değer ile son bulduğumuz değer arasındaki fark bu
// duyarlılık değerinin altına indiğinde hedefe vardığımızı kabul edeceğiz
// adimK: Gradyanın tersi yönünde ilerlerken adımlarımızın büyüklüğünü
// belirleyecek katsayı
// maxAdimSayisi: Adım sayısı bu değere ulaştığında hala minimumu bulamamışsak
// aramayı durduracağız.
void iniseGec(double &noktaX, double &noktaY,
              double duyarlilik=0.01, double adimK=0.1, int maxAdimSayisi=100)
{
    // Bir önceki noktanın koordinatlarını tutacak.
    double oncekiX=0, oncekiY=0;

    // Son konum ile önceki konum arasındaki farkları tutacaklar.
    double farkX=1, farkY=1;

    // Kaç adım attığımızı sayacak.
    int adimSayisi=0;

    // Ve inmeye başlıyoruz.
    bool iniseDevam=true;
    while(iniseDevam && adimSayisi<maxAdimSayisi)
    {
        iniseDevam=false;
        if(farkX>duyarlilik)
        {
            iniseDevam=true;
            oncekiX=noktaX;
            // Gradyanın tersi yönünde ilerleyeceğiz.
            noktaX=noktaX-adimK*f_gradX(noktaX);
            farkX=abs(noktaX-oncekiX);
        }
        if(farkY>duyarlilik)
        {
            iniseDevam=true;
            oncekiY=noktaY;
            // Gradyanın tersi yönünde...
            noktaY=noktaY-adimK*f_gradY(noktaY);
            farkY=abs(noktaY-oncekiY);
        }
    }
}

int main()
{
    // Rastgele bir noktadan başlayabiliriz:
    double x=1;
    double y=1;
    iniseGec(x,y);
    cout<<"Minimum: ("<<x<<" , "<<y<<")";
}

Her iki örnekte de minimum noktasını bir bakışta söyleyebileceğimiz basit bir fonksiyon olan f(x,y)=x*x+y*y+1 fonksiyonunun minimum noktasına ulaşmaya çalıştık. Bu fonksiyon en küçük değeri olan 1 değerini x ve y 0 iken alır. Kod örneklerinde belirlediğimiz duyarlılık değerinin altına sadece 30 adım sonra düşüldüğü için, son adımda varılan (0.0351844, 0.0351844) noktası fonksiyonun minimum noktası kabul edilir ve ilerleme durdurulur. Duyarlılık eşiğini düşürüp çok daha yakın sonuçlar elde etmek mümkün...

Son olarak yöntemi ne tür problemlere uyarlayabileceğiniz konusunda fikir vermesi açısından, yöntemin geri yayılımlı yapay sinir ağlarının hata fonksiyonunu minimize etmekte kullanıldığını hatırlatayım. Yöntemi bir probleme uyarlamak için probleminize uygun bir hata fonksiyonu modelleyip bu yöntemle o fonksiyonu minimize edebilirsiniz. Bu konuda daha fazla bilgi isterseniz Geri Yayılımlı Yapay Sinir Ağları başlıklı yazıyı okuyabilirsiniz...

Harici Bağlantılar

• Level sets versus the gradient
• Level Surfaces
• Gradient: proof that it is perpendicular to level curves and surfaces
• Method of Steepest Descent

Leave Comment

Comments (6)