optimizasyon -1
Giriş ve çıkış arasındaki ilişkiyi bulmanın 2 temel faydası var. İlki veriyi anlamak diğeri bir giriş için çıkışı tahmin edebilmek. Bunun için veriyi modellememiz gerekir. Burada da devreye fonksiyonlar giriyor.
y=f(x) bir fonksiyon. x: d, y: 1 boyutlu. Örneğin x’in (2,3) değeri için y=5. Bu şekilde bize birçok x,y değerleri verilmiş olsun. Amacımız elimizdeki bu verilere en uygun f fonksiyonunu bulmak. Bir fonksiyonun modeli ve parametreleri olur. Örneğin f(x)=3*x²–5*x fonksiyonunun modeli f(x)=w1*(x^w2)+w3*x olarak tanımlanabilir. Buradaki w1, w2 ve w3 ise modelin parametreleridir.
Bize model ve x,y değerleri verilirse modelin parametrelerini bulabilir miyiz?
Örneğin x’in sırasıyla -2, -1, 1, 3 değerleri için y’nin -3, 0, 6, 12 değerleri verilmiş olsun. Model ise f(x)=w1*x+w2 olarak verilsin. Soru: w1 ve w2 nedir?
w1 ve w2’nin sayı olduğunu biliyoruz ama sınırları yok. Tam sayı oldukları söylenirse bir de sınırları verilirse en basiti (!) tüm olasılıkları deneriz. Her birinin 100 olasılığı olsa 10 bin deneme. Peki bu denemelerde ne yaparız. Her tahminimizi fonksiyonda yerine koyarız. Sonra elimizdeki x’ler için y’leri buluruz ve gerçek y’lerle aralarındaki farkları/hatayı hesaplarız. Burada pozitif ve negatif hatalar birbirini götürmesin diye farkların karelerinin toplamını almak mantıklı olacaktır. Denemelerimizden de az hataya sahip olanı çözüm olarak ilan ederiz.
Bunu yapalım. Şekil 1’de tabanın eksenleri w1 ve w2’nin denenen değerleri, yükseklik ise x,y leri kullanarak hesapladığımız hata değerlerini göstermektedir.
Hatanın 0 olduğu yer çözümümüz olacaktır. Merak edenler için [3,3] :)
Bu tarz bir çözümde parametre sayısına ve parametrelerin olası değer sayısına bağlı olarak deneme sayımızın üstel olarak artacağı belli. Peki daha az deneme ile çözüme erişebilir miyiz?
Bir parametreyi sabit tutup diğerinde denemeler yapabiliriz. Bunlardan en iyisini bulup bu sefer onu sabit tutup diğerinde denemeler yapabiliriz. Eğer d tane parametremiz varsa d-1’ini sabit tutup geri kalanında deneme yaparız. Gerisini anladınız :) Bu yöntemin daha az deneme içerdiği belli ama her zaman başarı sağlar mı? Ya da ne gibi durumlarda başarı sağlar? Bunlar üzerinde düşünmeyi size bırakıyorum :)
Ama bu yöntem bize bir fikir veriyor. Bir noktadan başlayıp hatayı azaltacak şekilde ilerlemek. Şimdi bu hata yüzeyini bu fikre göre biraz inceleyelim. Herhangi bir yerden başladığımızı düşünelim. Hangi yöne doğru gitmeliyiz? Çözüme doğru evet ama çözümü bilmiyoruz. Ama çözümü bilmesek bile bu hata yüzeyinin bulunduğumuz noktadaki eğimini bulabilirsek bunun tersi yönde yani yokuş aşağı ilerleyebiliriz. Bu ise hata yüzeyini oluşturan fonksiyonun parametrelere göre türevini alabiliyorsak mümkün olacaktır.
Diğer bir deyişle türevi alınabilen bir fonksiyonun minimum değerini bulmak istiyoruz. Bu fonksiyon hata değerini veriyorsa minimum noktası hatanın minimum olduğu yer olacaktır. O halde verilen x,y lere ve modele göre en uygun model parametrelerini bulmayı bir fonksiyonun minimum değerini bulmak olarak düşünebiliriz.
O halde fikirlerimizi toparlayalım. Türevi alınabilen bir fonksiyon var. Minimum değerini bulmak istiyoruz. Bir tahminle başlayıp her adımda tahminimizi iyileştirelim.
Genel algoritma:
İlk tahmini yap
İyileşme anlamlı olduğu ve maksimum adım sayısına erişmediğimiz sürece tahmini iyileştir
Tahminin iyileşme yönü fonksiyonun mevcut tahmininin etrafına verdiği cevaplarla belirlenir. Örneğin bir yöne doğru gittiğimizde fonksiyonun değeri artıyorsa tersi yöne doğru gitmeliyiz.
Elimizde Şekil 2’deki tek boyutlu fonksiyonumuz f(x)=x² olsun. Bu fonksiyonun minimum olduğu x değerini bulmak isteyelim. İlk tahminimizde -2.7 olsun. Bir sonraki tahminimiz ne olmalı. x’in değerini azaltırsak fonksiyonun değeri artacak, arttırırsak azalacaktır. O halde x’i arttırmalıyız. Peki ne kadar? Diğer bir deyişle adım büyüklüğümüz ne olmalı?
Örneğin 0.1’lik sabit adımlar atabiliriz. Ama sanki çözümden uzakken büyük çözüme yakınken küçük adımlar atsak daha iyi olur. Peki çözüme uzak olduğumuzu nasıl anlayabiliriz? Fonksiyonu incelersek eğimin çözümün etrafında küçük, tam çözümde 0, çözümden uzakken büyük olduğunu görebiliriz. Ayrıca eğimin işareti de çözümün ne tarafta olduğunu söyler.
Artık genel algoritmamız için olası bir iyileşme adımını tanımlayabiliriz.
x_yeni = x_eski-adım_büyüklüğü * f’in_x_eski_deki_türevi
Elimizde tek boyutlu bir fonksiyon varken yukarıdaki büyüklüklerin hepsi birer sayı olacaktır. Örneğin Şekil 2’de -2.7’den nereye gideceğimize bakalım. Adım büyüklüğümüz 0.1 olsun.
x_yeni= -2.7- 0.1*2*(-2.7) = -2.7 + 0.54 = -2.16 olacaktır.
Elimizde d boyutlu bir fonksiyon varken yukarıdaki büyüklükler d*1 boyutlu vektörler olacaktır. Örneğin d=2 için [2 ; 3] noktasından [2.3 ; 2.5] noktasına hareket edebiliriz. Bu durumda f’in_x_eski_deki_türevi de yine d*1 boyutlu bir vektör olacaktır. Bu vektörün her bir boyutu f fonksiyonunun o boyuta göre türevini içerecektir.
Örneğin f(x1,x2)=3*x1²+x2² fonksiyonunun minimum noktasını x=[2; 4] den başlayarak bulmak istersek, adım büyüklüğü (eps) 0.1 için bir sonraki nokta
olarak bulunacaktır.
Şekil 3’te benzer bir fonksiyonun minimum noktasını bulurken atılan ardışık adımlar gösterilmiştir. Adımlar arası büyüklüğün giderek azalmasının sebebi çözüme yaklaşırken türevlerin küçülmesidir.
Şimdi başlangıçtaki (Şekil 1) hata fonksiyonumuza dönelim. Bu fonksiyonda 2 parametre / boyut içermektedir. Ancak f(x1,x2)=3*x1²+x2² gibi basitçe yazılamamaktadır. Çünkü f(w1,w2) in değeri verilen x,y ikililerine ve modelin yapısına bağlıdır. Herhangi bir [w1 ; w2] noktası için f’in değeri
olacaktır. Buradaki n elimizdeki x,y ikililerinin sayısıdır. Bunu açarsak
Buradaki a,b,c ve d katsayıları kolaylıkla bulunabilir. Bunun ardından da bu hata fonksiyonunun w1 ve w2’ye göre türevleri bulunur.
Modelin daha karmaşık olması izleyeceğimiz yolu değiştirmez tabi türevi alınabilen bir ifade olduktan sonra.
Şimdi çok daha genel bir problem ele alalım.
Verilen datalar {x_i , y_i } i=1…n (n= nokta sayısı)
y=g(w,x) (g verilen model, w: bulmak istediğimiz parametreler)
x = n*d boyutlu matris (x’ler d boyutlu)
y= n*1 boyutlu matris
r_i=y_i-g(w,x_i)
r_i = i. örnek için w ile üretilen tahminin g(w,x_i) gerçek değerle y_i farkı (n*1 matris)
w = hata fonksiyonunun minimum değerini bulmak için değiştireceğimiz parametreler
Hata fonksiyonumuz:
Amacımız L’nin en küçük değerine karşılık gelecek w’yi bulmak. Bunun için w’yi rasgele bir yerden başlatıp hatanın (L) azaldığı yöne doğru ilerleteceğiz. Bunun için L’nin w’ye göre türevine ihtiyacımız olacak. Ardından da iterasyon adımımızı yazabiliriz:
Yukarıdaki w_k ve w_(k+1) d*1 boyutlu vektörler, eps: bir sayı, r: n*1 boyutlu bir vektör, dr/dw : n*d boyutlu bir matris. Dolayısıyla dr/dw’nin tranpozesi (d*n boyutlu bir matris) ile r (n*1 boyutlu bir vektör) çarpılınca d*1 boyutlu bir vektör elde ederiz. Bu da eps ile çarpılıp eski w’den çıkarılarak yeni ve yine d *1 boyutlu w elde edilir.
Biraz ölçeklendirme üzerine konuşalım. Bu işlemdeki en büyük matris n*d boyutlu. Çalışmalar göstermiş ki tüm örnekler üzerinden hatayı hesaplamak yerine rasgele bir kısmı üzerinden de hesaplasak biraz gürültülü olsa da hedefe doğru ilerleyebiliyoruz. Bu durumda n’i istediğimiz kadar küçültebiliriz. 1 milyon örneğimiz varsa her w güncellemesi için mesela 1000 tanesini kullanabiliriz. Bu sayede her bir güncelleme için gerekli hafıza miktarı ve işlem sayısı azaltılabilir ama tabi güncelleme sayımız artacaktır.
Aslında gidilecek yönü tahmin etmede daha başarılı bir yöntem daha var. Ancak 2.dereceden türev içeriyor. Bu da d*d’lik bir matris demek. Ama bu başka bir yazı konusu.
Şimdi bu yöntemin bir uygulamasını görelim:
Y=sin(w*X) modeli ve x,y ikilileri (Şekil 4'teki mavi noktalar) verilmiş olsun. Burada bulmak istediğimiz bu ikililere en uygun w değeri. Şekil 4’te başlangıçtan sona kadar ki tahminler görülmektedir.
Şekil 4 incelendiğinde tahminlerin giderek iyileştiği ve en sonunda verilere uygun bir w değerinin bulunduğu görülmektedir.
W için ilk tahminimizin -1 olduğunu söylemiştik. Acaba başka bir ilk değer seçseydik yine aynı sonuca varabilir miydik? Görelim. Şekil 5’te w_0=-2’den başladığımızdaki süreç görülmekte.
Sonuç (kırmızı çizgi) pek tatmin edici değil.
Biraz geri çekilip düşünelim. Hata fonksiyonunu sürekli azaltan güncellemeler yapıyoruz burada. Acaba w’nin farklı değerleri için hata fonksiyonunun aldığı değerleri incelersek ne görürüz? Şekil 6’ya bakalım.
Şekil 6, farklı başlangıçların neden farklı sonlandığını açıklıyor. İlk denememizde -1’den başlamış ve minimum hataya ulaşmıştık. İkinci denememizde ise -2’den başlayınca eriştiğimiz hata daha yüksek çıkmıştı. Bu olaya lokal/yerel minimuma takılma deniyor. Sadece eğime bakan bir yöntemin lokal bir minimumdan kurtulması pek kolay değil. En kestirme çözüm farklı ilk değerlere süreci tekrarlamak :)
Başka bir örnek yapalım.
Aşağıdaki model ve x,y ikilileri verilmiş olsun.
Burada w, 2 boyutlu [w1;w2]. Yani w0=[4;3] gibi bir noktadan başlayacağız ve veriye en uygun w1,w2 ikilisini bulmaya çalışacağız. Süreci Şekil 7’de görelim.
Şekil 7’de veri ile uyumlu bir sonuca ulaştığımız görülüyor. Acaba başka bir ilk değerle başlasaydık ne olurdu? Bunun için Şekil 8’deki parametre hata yüzeyini inceleyelim.
Şekil 8 incelendiğinde bu yüzeyin Şekil 6’dakinden daha iyi olduğunu söyleyebiliriz. Evet problemli başlangıçlar var ama lokal minimumların ikisi de yeterince iyiler. Simetriyi görebilirsiniz. Bu simetrinin sebebi modelde saklı :)
Elimizdeki modele ve x,y ikililerine göre bu parametre hata yüzeyleri farklılaşırlar. 2 tane parametre olduğunda bu yüzeyi görmek mümkün ama 100 bin parametreye sahip bir model için bu hayal.
100 bin parametreli model olur mu? Olur :)
Olmalı mı? Büyük bir soru. Geçelim :)
Buraya kadar bize hep modelin verildiğini varsaydık. Sadece x,y ikililerinin verilmesi durumunda ne yapacağız? Modelimiz olmadan optimize edeceğimiz bir hata fonksiyonu tanımlayamayacağımız için bir şey yapamayız. O halde bir model uydurabiliriz. Verilerimizin bu modele uyduğunu varsayarız. Peki bu varsayımımızın doğru olduğunu nasıl bilebiliriz? Burada evrensel modeller devreye giriyor. Yani yeterince parametreye sahip olduklarında her türlü veriye uyum sağlayabilen modeller. Bu tür modellere örnek olarak karar ağaçları, yapay sinir ağları, Fourier ve Taylor dönüşümleri verilebilir. Ama bu ayrı bir yazının konusu.
Peki tüm bunları nerede mi kullanacağız? İstediğiniz yerde :)
Daha fazlası ve kodlar için https://sites.google.com/view/mfatihamasyali/optimization-techniques
