tag Arama Algoritması
Bu sayfada Arama Algoritması etiketi ile işaretlenmiş 3 yapay zeka kavramını bulabilirsiniz.
A* (A-yıldız) algoritması, 1968 yılında Peter Hart, Nils Nilsson ve Bertram Raphael tarafından Stanford Araştırma Enstitüsü'nde geliştirilen, graflar ve ağlar üzerinde en kısa yolu bulan sezgisel bir arama algoritmasıdır. Yapay zeka, robotik, oyun geliştirme ve navigasyon sistemlerinde en yaygın kullanılan yol bulma (pathfinding) yöntemi olma özelliğini korumaktadır. A*, Dijkstra algoritmasının garantili optimalliği ile sezgisel arama yöntemlerinin verimliliğini bir araya getirir. Temel değerlendirme fonksiyonu f(n) = g(n) + h(n) formülüyle tanımlanır: g(n) başlangıç noktasından mevcut düğüme ulaşmanın gerçek maliyetini, h(n) ise mevcut düğümden hedef noktaya olan tahmini mesafeyi (sezgisel fonksiyon) ifade eder. Bu iki bileşeni birleştirerek algoritma, hem geçmiş maliyeti hem de gelecekteki tahmini maliyeti optimize eder. Algoritmanın doğruluk ve optimallik garantisi, kullanılan sezgisel fonksiyonun kabul edilebilir (admissible) olmasına bağlıdır. Kabul edilebilir sezgisel, gerçek maliyeti hiçbir zaman olduğundan fazla tahmin etmez. Düzlemsel koordinatlarda sıklıkla kullanılan Öklid ve Manhattan mesafe formülleri bu kriteri karşılar. Sezgisel aynı zamanda tutarlı (consistent/monotone) olduğunda A* keşfedilen düğümleri yeniden ziyaret etmez ve bellek kullanımı azalır. A*, açık liste (open list) ve kapalı liste (closed list) veri yapılarıyla çalışır. Önce başlangıç düğümünü açık listeye ekler; her adımda f değeri en düşük düğümü seçer, komşularını değerlendirir ve listeyi günceller. Bu süreç hedefe ulaşılana veya tüm olası yollar tükenene kadar devam eder. Öncelik kuyruğu (priority queue) ile uygulandığında zaman karmaşıklığı O(E log V) mertebesindedir. Yapay zeka araştırmalarında A*, pekiştirmeli öğrenmede planlama problemlerinin çözümünde, doğal dil işlemede sözdizimi ağaçlarının aranmasında ve konfigürasyon uzaylarında robot hareket planlamasında kullanılmaktadır. Oyun motorlarında ise NPC (Non-Player Character) yapay zekasının temel navigasyon bileşeni olarak yaygındır. Büyük ölçekli harita uygulamalarında A* varyantları (IDA*, D* Lite) bellek ve hız optimizasyonu için tercih edilmektedir.
A* Algoritması (A* Arama Algoritması)
A* (A-yıldız) algoritması, 1968 yılında Peter Hart, Nils Nilsson ve Bertram Raphael tarafından Stanford Araştırma Enstitüsü'nde geliştirilen, graflar ve ağlar üzerinde en kısa yolu bulan sezgisel bir arama algoritmasıdır. Yapay zeka, robotik, oyun geliştirme ve navigasyon sistemlerinde en yaygın kullanılan yol bulma (pathfinding) yöntemi olma özelliğini korumaktadır. A*, Dijkstra algoritmasının garantili optimalliği ile sezgisel arama yöntemlerinin verimliliğini bir araya getirir. Temel değerlendirme fonksiyonu f(n) = g(n) + h(n) formülüyle tanımlanır: g(n) başlangıç noktasından mevcut düğüme ulaşmanın gerçek maliyetini, h(n) ise mevcut düğümden hedef noktaya olan tahmini mesafeyi (sezgisel fonksiyon) ifade eder. Bu iki bileşeni birleştirerek algoritma, hem geçmiş maliyeti hem de gelecekteki tahmini maliyeti optimize eder. Algoritmanın doğruluk ve optimallik garantisi, kullanılan sezgisel fonksiyonun kabul edilebilir (admissible) olmasına bağlıdır. Kabul edilebilir sezgisel, gerçek maliyeti hiçbir zaman olduğundan fazla tahmin etmez. Düzlemsel koordinatlarda sıklıkla kullanılan Öklid ve Manhattan mesafe formülleri bu kriteri karşılar. Sezgisel aynı zamanda tutarlı (consistent/monotone) olduğunda A* keşfedilen düğümleri yeniden ziyaret etmez ve bellek kullanımı azalır. A*, açık liste (open list) ve kapalı liste (closed list) veri yapılarıyla çalışır. Önce başlangıç düğümünü açık listeye ekler; her adımda f değeri en düşük düğümü seçer, komşularını değerlendirir ve listeyi günceller. Bu süreç hedefe ulaşılana veya tüm olası yollar tükenene kadar devam eder. Öncelik kuyruğu (priority queue) ile uygulandığında zaman karmaşıklığı O(E log V) mertebesindedir. Yapay zeka araştırmalarında A*, pekiştirmeli öğrenmede planlama problemlerinin çözümünde, doğal dil işlemede sözdizimi ağaçlarının aranmasında ve konfigürasyon uzaylarında robot hareket planlamasında kullanılmaktadır. Oyun motorlarında ise NPC (Non-Player Character) yapay zekasının temel navigasyon bileşeni olarak yaygındır. Büyük ölçekli harita uygulamalarında A* varyantları (IDA*, D* Lite) bellek ve hız optimizasyonu için tercih edilmektedir.
Beam Search Decoding (Işın Arama Kod Çözme)
Beam search decoding, otomatik çeviriden metin özetlemeye kadar geniş bir yelpazede kullanılan temel bir çıkarım algoritmasıdır. Greedy search her adımda yalnızca en yüksek olasılıklı tek tokeni seçerken; beam search 'ışın genişliği' (beam width, k) kadar hipotezi paralel biçimde takip eder. Her adımda mevcut k hipotezin her biri en olası devamlarıyla genişletilir, ortaya çıkan k×vocab_size aday arasından toplamda en yüksek log-olasılıklı k dizisi bir sonraki adım için korunur. Son token üretildiğinde (veya EOS tokeni görüldüğünde) en yüksek kümülatif olasılıklı dizi çıktı olarak döner. k=1 greedy search ile özdeştir; k arttıkça arama kalitesi artabilir ancak hesaplama ve bellek maliyeti de k katına çıkar. Algoritmanın temel zayıflığı, ham log-olasılık toplamının kısa dizileri kayırmasıdır: her ek token küçük bir negatif değer eklediğinden model kısa ve özlü çıktılar üretmeye yönelir. Bu sorunu gidermek için length penalty (uzunluk cezası) devreye girer; nihai skor dizinin uzunluğu üzerinden normalize edilir ve α parametresiyle ayarlanır, α değeri genellikle 0.6–1.0 arasında seçilir. Çeşitlilik gerektiren görevlerde ise diverse beam search, hipotezler arasına benzerlik cezası ekleyerek tekrarlayan ve birbiriyle örtüşen çıktı dizilerini azaltır. Modern büyük dil modelleri — GPT-4, Claude veya Llama-3 gibi — çoğunlukla beam search yerine greedy arama veya temperature/top-p örneklemeyi tercih eder. Otoregresif üretimde k paralel akışın GPU bellek gereksinimini k katına çıkarması, bunun yanı sıra yüksek kapasiteli modellerde kalite farkının belirgin biçimde azalması bu tercihin başlıca nedenleridir. Makine çevirisi (Google Translate, DeepL), otomatik konuşma tanıma (ASR/STT) ve metin özetleme gibi deterministik ve tekrarlanabilir çıktı gerektiren görevlerde beam search hâlâ endüstri standardıdır. Pratik bir boyutlandırma örneği: k=5 ile 30.000 token'lık sözlükte çalışan bir makine çevirisi modeli her üretim adımında 150.000 kombinasyonu değerlendirir; bu greedy search'e kıyasla yaklaşık 5× hesaplama yükü anlamına gelir. Buna karşın elde edilen BLEU artışı, özellikle kısa ve orta uzunluktaki cümlelerde bu ek maliyeti karşılar. 2015 yılında Sutskever ve ekibinin seq2seq mimarisiyle makine çevirisinde yaptığı çalışma, beam search'in NLP alanında geniş çapta benimsenmesine öncülük etmiştir.
Monte Carlo Tree Search (MCTS) (Monte Carlo Ağaç Araması)
Monte Carlo Tree Search (MCTS), olasılıksal simülasyonlar kullanarak geniş karar ağaçlarında en iyi hamleyi bulan buluşsal bir arama algoritmasıdır. Klasik minimax aramasından farklı olarak tüm dalları değerlendirmek yerine yüzlerce rastgele simülasyon (rollout) çalıştırır ve kaynakları en umut verici bölgelere yoğunlaştırır. Dört aşamalı bir döngü üzerine kuruludur: Seçim aşamasında mevcut ağaçta UCT (Upper Confidence bounds applied to Trees) formülüyle en iyi düğüm seçilir; Genişleme aşamasında seçilen düğüme yeni çocuk düğümler eklenir; Simülasyon (Rollout) aşamasında rasgele ya da ağırlıklı politika oymasıyla bir sonuca gidilir; Geri Yayılım aşamasında simülasyon sonucu ağaçtan köke kadar taşınarak istatistikler güncellenir. Verilen süre ya da iterasyon sayısı dolana dek bu döngü tekrar eder; en çok ziyaret edilen kök çocuğu nihai hamle olarak seçilir. Algoritma 2006 yılında Rémi Coulom tarafından bilgisayarlı Go için önerilmiş, Kocsis ve Szepesvári'nin UCT formülüyle güçlendirilmiştir. 2016'da DeepMind'ın AlphaGo programı MCTS'i derin sinir ağlarıyla birleştirerek dünya Go şampiyonu Lee Sedol'ü 4-1 yenerek tarihin en dikkat çekici yapay zeka başarılarından birini gerçekleştirmiştir. 2017'de AlphaZero, satranç, shogi ve Go'da yalnızca öz-oyun ve MCTS kullanarak insan yazılmış bilgiye ihtiyaç duymaksızın tablo kıran performanslar elde etmiştir. UCT formülünün özü, keşif-sömürü dengesini matematiksel olarak çözmektir. Q_i/N_i terimi mevcut en iyi dalı sömürürken √(ln N / N_i) terimi az ziyaret edilmiş düğümleri keşfetmeyi özendirmektedir; c sabiti bu ikisi arasındaki ağırlığı belirler. MCTS, değerlendirme fonksiyonu tasarlamak güç olmakla birlikte simülasyonların hızlı olduğu board oyunlarından robot planlamasına, ilaç keşfine ve operasyon araştırmasına kadar pek çok alanda tercih edilen güçlü bir karar verme aracıdır. Ayrıca büyük dil modellerinin çıkarım süreçlerinde düşünce ağaçlarını genişletmek için de uyarlanmaktadır.