... konulu sunumlar: "Informed Search and Exploration"— Sunum transkripti:
1 Informed Search and Exploration Heuristic Search
2 Arama YöntemleriArama Yöntemleri: Her aşamada hangi düğümün açılacağını belirler.Blind Strategies (Bilgiye dayanmayan arama): Durum bilgisinden yararlanmaz.Heuristic Strategies (Sezgisel arama): Durum bilgisinden yararlanır. Daha umut verici hareketi tercih eder.
4 Sezgisel Olmayan Arama Yöntemleri Breadth-FirstBidirectionalDepth-FirstDepth-limitedIterative deepeningUniform-Cost
5 Karşılaştırma: Sezgisel olmayan aramalar BFS, tamdır, optimaldir ancak yer karmaşıklığı yüksektir.DFS, yer karmaşıklığı etkindir, ancak tam da değildir, optimal de değildir.Iterative Deepening Search, yaklaşık olarak optimaldir.
6 Heuristic Search (Sezgisel Arama) Sezgisel olmayan arama yöntemlerinde düğümlerin açılmasında kullanılan yöntem, başlangıç düğümünden olan uzaklık bilgisine dayanıyordu.Hedefe olan uzaklık kestirilirse ne olur?Gerçek uzaklık tam olarak bilinmese de kestirilebilir. Bu tahmine, Heuristic (Sezgi) yani h(n) denilir.YZ da sezgisellik: insanın sezgisel davranışları makinelere nasıl aktarılabilir ve problem çözümünde nasıl kullanılabilir?Sezgisellik: problem karmaşıklık içerdiğinde çözüm için yolun bulunmasındaki yardımcı anahtardır.İyi seçilmiş anahtar ile çözüm kolayca bulunurken kötü seçilmiş anahtar çözüme ulaşmayı güçleştirir veya geciktirir.
7 Heuristic Search Birçok problem aşağıdaki yaklaşımda çözülür: 1- olası durumlardan herhangi birini al2- ele alınan duruma mümkün gidişler uygulanarak durumun değiştirilmesi3- durumun değerlendirilmesi4- gereksiz durumların atılması5-eğer sonuca ulaşılmış ise çözümü tamamla değilse yeni değeri ele al işlemi tekrarlaAlgoritmik yaklaşımda adımları yer almaktadır.Sezgisel yaklaşımda çözüm ağacının tüm dallarındaki durumlar değil yalnız en avantajlı düğümler incelenir.
8 Sıralı Arama Algoritma adımları genel olarak: Başlangıç durum çözüm ağacının köküne yerleştirilir ve geçerli gidişlerler (operatörlerle) bu durumdan mümkün olan yeni durumlar (çocuklar) elde edilir.Çocuk düğümler için f(x) fonksiyon değerlendirmesi yapılarak minimum değerli düğüm seçilir. Aynı değere sahip düğümlerden herhangi biri seçilirAçılan min değerli düğümün benzer şekilde çocuk düğümleri değerlendirilir. O anki düğümden çocuk düğüm elde edilemiyorsa ve henüz hedefe ulaşılmamışsa üst seviyeye geri dönülerek arama yönü minimum olan fonksiyon yönüne doğru değiştirilir.İşlemler hedefe ulaşılıncaya kadar tekrarlanır. Hedef bulununca başlangıç düğümünden hedefe olan yol saklanır.Greedy Yöntemleri:uzun vadeli sonuçları önemsemeden, kısa vadeli avantajları en iyi duruma getirir.Tam değildirOptimal değildir.Zaman ve Yer Karmaşıklıkları kötüdür (üstel)
9 Durum Uzayında Sezgisel Arama Yöntemleri A* Search8-vezir problemiHill Climbing veya Gradient Descent
10 A* SearchBest-first Search’ün en büyük dezavantajı, uzak görüşlü olmamasıdır.Başlangıç düğümü: s düğümüS düğümünden X düğümüne kadar yol:g(x): şu anki duruma kadar maliyet fonksiyonuX düğümünden hedef f düğümüne kadar yol:h(x): uygun sezgi fonksiyonu olsun.G(x): x durumunun gerçek olan o anki değeriH(x): x düğümünden çözüme olan gidişlerin sezgisel değeriUygun olması, iyimser olması yani hedefe götüren maliyeti hiçbir zaman gerçek değerinden daha yüksek değerde kestirememesi demektir.A* Algoritması:f(x)=g(x)+h(x)
11 A* Search 8-taş problemi için H(x) sezgisel fonksiyonun tasarımı probleme göre değişmektedir.Örnekte 2. sırada açılan durum için derinlik: g(x)=1Hedef duruma göre yerinde olmayan taşların sayısı:h(x)=5O halde f(x)=g(x)+h(x)=1+5=67. durum için g(x)=4, h(x)=3 ve f(x)=7Karelerin üzerindeki sayılar sıra ile açılan düğümleri,Yan tarafındaki sayılar sezgisel skorları ifade eder.Şekildeki gibi h(x)=0 olduğunda algoritma durursa çok fazla derinine arama yapılabilir.Bu nedenle A* algoritmasının 8-taş problemine uygulanmasında farklı sezgisel h’(x) fonksiyonları tanımlanabilir.1- h’(x): ele alınan durumla hedef durum karşılaştırıldığında yerinde olmayan taşların sayısı2-h’(x):taşların hedefteki yerlerine uzaklıkları toplamı
12 A* Search 8-taş problemi için Bu 2 sezgisel fonksiyon için örnek işletimBaşlangıç durumu=Hedef durumu =1-yerinde olmayan taşların toplamı: h’(x)=72-taşların kendi yerlerinden olan uzaklıkları toplamı:h’(x)= =8
16 A* Aramasının Özellikleri Tamdır. Sonuçta, çözüm varsa bulunur. Kökten başlanarak gidilen herhangi bir yolda f tahmini her zaman artar (h, monoton olsa bile). Zaman karmaşıklığı Optimaldir.Zaman ve Yer karmaşıklıkları kötü olsa da iyi bir sezgi ile, düzelecektir.
17 8-Vezir YZ’da en çok araştırılan problemlerdendir. nxn boyutlu bir satranç tahtasına mümkün olduğunca çok sayıda vezirin birbirini görmeyecek şekilde yerleştirilmesi hedeflenmektedir.nxn boyutlu bir tahtaya en çok n sayıda vezir yerleşebilmektedir. Bu durumda problem 8x8 lik bir tahtada 8-vezir problemine dönmüştür..
18 8-Vezir Çözüm ağacı kurulurken, Satırlar boyunca ilk boş hane görüldüğünde bu boş haneye vezir konulur.Yerleştirilen vezirin gördüğü kareler işaretlenir ve sonraki seviyeye geçilir4 vezir için kurulan çözüm ağacı aşağıdaki gibidir.
19 8-VezirSezgisel bir değerlendirme yapılmadığında ağacın tüm dallarında gezinerek çözüm aranmaktadır.Durum uzayı büyüdükçe çözüm ağacının derinliği artar. Örnek durum:
20 8-Vezir-Yaklaşım 1 Vezirlerin konumuna göre çözümün aranması k satıra yerleştirilecek k tane vezir S={y1,y2,…yk} ile gösterilsin.Bir önceki örnek durum için S={d,f,h,c,a,g,e,b}Önceki tarama yönteminden farklı olarak burada yatay yöndeki haneler ardışık biçimde değil, minimum ağırlıklarına (serbestlik derecelerine) göre bakılacaktır.
21 8-Vezir-Yaklaşım 1 Farzedelim ki şu durum için çözüm aranıyor. S={y1,y2,f,c,y5,y6,y7,y8} vektöründeki yi değerlerinin bulunması çözüme karşılık gelmektedir.Vezirler yerleştiğinde hamle altında olabilecek haneler bu vezirin numarası ile işaretlenecektir.Vezirlerin yerleşmediği satırların serbestlik dereceleri (4,3,_,_,3,4,5,4) şeklindedir.Vezirlerin yerleşmediği sütunların serbestlik dereceleri (3,4,_,4,4,_,4,4) şeklindedir.En az ağırlığı olan satırlardan biri 5. satırdır, sütun ağırlıklarına da bakılarak 3. vezir 5. satırın a sütununa yerleştirilir
22 8-Vezir-Yaklaşım 1 3. vezirden sonraki durum: Seçim son iki satır, d ve e sütunu arasından yapılacaktır.D7 ye yerleştirilirse e sütununda serbest yer kalmayacak ve geri dönülerek yeni durumların incelenmesi gerekecektir.O halde 4. vezir e8 ve d6 hanelerinden birine yerleşmelidir.
23 8-Vezir-Yaklaşım 14. vezir e8 hanesine yerleştirilirse ve 8. vezirler mecburi olarak yerleşeceklerdir.Olası çözümlerden biri elde edilmiştir.
24 8-Vezir-Yaklaşım 2 Sezgisel onarım yöntemi: 1-milyon vezir problemi yaklaşık 50 adımda çözülmektedir.İlk önce vezirlerin yerleşimlerinin her satır ve sütuna birer tane olmak üzere rastgele yapıldığı varsayılır.Her sütunda en az tehdit olan satır belirlenir vezir o satıra taşınır.
25 ÖzetSezgisel arama yöntemleri, problem hakkındaki bilgiden yararlanırlar.Sezgi (Heuristic), hedefe ulaşmak için kalan maliyetin tahminidir.İyi bir sezgi, arama süresini, üstelden doğrusala indirir.
26 Dağa Tırmanma(Hill-Climbing) “dağa tırmanma” yönteminin ana fikrinde böyle bir varsayım dayanmaktadır:ormancı gece dağda yolunu kaybetmiştir. Onun evi dağın zirvesindedir.Karanlık olsa da ormancı , her adımının onu amacına yakınlaştırdığını bilmektedirDağa tırmanma yönteminde aramanın yönü her zaman amaca daha yakın düğüme doğrudur.Makine Öğrenmesinde popülerdir.
28 Hill Climbing S A B C D E F G 10.4AB8.9CD6.910.4Dağa tırmanma sezgisel değerlendirmeli derine arama yöntemidir. Düğümler genişlendikçe seçenek sunuyor.Şekilde düğümlerin yanındaki sayılar son ( o anki) düğümlerden amaca kadar olan düz yolun uzunluğunu gösteriyor.3.0EF6.7G
29 Gradient descend Arama Giriş verilerilineer ayrıştırılabilir ise: algılayıcı kuralı başarılı ağırlıklar bulmaktadır.lineer ayrıştırılabilir değilse: delta kuralı hedef fonksiyona en yakın yaklaşıklıkla öğrenme yapabilmektedir.Delta kuralının temel mantığı: olası en iyi ağırlık vektörlerinin hipotez uzayını arayan gradient descent metodudur.Delta kuralı backpropagation algoritmasının temelini oluşturur.
30 Delta KuralıDelta kuralı, eğik değersiz algılayıcı kuralı gibi düşünülebilir ve bir lineer birim çıkışı:Hipoteze ait öğrenme hatası:D: eğitim verileri kümesi,td: d giriş verisi için hedef çıkış,od: d örneği için lineer birim çıkışıKaresel hata vektöreldir
31 Gradient descend Arama Gradient descent araması, bir başlangıç ağırlık vektörü ile başlayıp, sonraki adımlarda güncelleyerek E’yi minimum yapacak ağırlık vektörünü tanımlar.W ağırlık vektörü ile başlaE(W) yi minimum oluncaya kadar ağırlıkları değiştir.
32 Gradient Descent Araması Bir nokta ile başla (tahmini nokta):
37 Hatadaki en dik düşüş?Hata yüzeyindeki en dik düşüşü nasıl hesaplayabiliriz?Bu yön hatanın ağırlık vektörüne göre türevi alınarak bulunabilir.Bu türev vektörü, hatanın ağırlıklara göre gradient’i olarak adlandırılır.