Işın Araması (Beam Search)

Yazan: Şadi Evren ŞEKER
Bu yazının amacı, özellikle yapay zeka çalışmaları altında yer alan sezgisel arama algoritmalarının (heuristic search algorithms) bir çeşidi olan ışın araması konusunu anlatmaktır.
Işın arması “en iyi ilk arama” (best first search) tipi arama algoritmalarındandır ve amacı hafıza ihtiyacını azaltmaktır.
En iyi ilk arama yaklaşımını kullanan arama algoritmaları, arama yaptıkları şekil (graph) üzerinde bütün çözüm ihtimallerini belirli bir sezgisel fonksiyona göre sıralarlar. Diğer bir deyişle arama işlemi sırasında sezgisel bir fonksiyona göre, aramada bazı kararlara öncelik verirler. Bu sezgisel fonksiyonun amacı, karar anında verilen kararın, sonuç durumuna (goal state) ne kadar yakın olduğunu yargılayabilmektir.
Işın aramasının bir özelliği de, daha önceden belirlenmiş ve sınırlı sayıdaki, yapmış olduğu seçimleri saklamasıdır.
Işın araması, bir arama ağacı (search tree) oluştururken, sığ öncelikli arama (breadth first search) yaklaşımı kullanır. buna göre ağacın herhangi bir seviyesinde, gidilebilecek düğümlerin sezgisel değerlerini hesaplar ve bunlardan sadece belirli sayıdaki düğümü, daha sonra geri dönülmek üzere hafızasında tutar. Bu değere ışın aramasına özgü olarak ışın genişliği (beam width) ismi verilir.
Işın genişliği arttıkça daha fazla düğüme bakılmaktadır. Işın genişliği azaldıkça da daha fazla düğüm budanmaktadır (prunning). Budama işleminin dez avantajı, şanssız bir şekilde en iyi sonucu verecek düğüme giden yolu budama riskidir. Ancak bu riskten dolayı bütün düğümleri tutmak (yani hiçbir düğümü budamamak) gibi bir karar verirsek, bu karar sonucunda da çok daha fazla hafıza ve işlem ihtiyacımız olacaktır. İşte ışın araması, bu iki karar arasında en iyi (optimum) noktayı bulmayı amaçlar.
Bu amaca yönelik olarak, ışın araması sabit ışın genişliği (fixed beam width) veya değişken ışın genişliği (variable beam width) kullanacak şekilde kodlanabilir. Değişken ışın genişliği alan arama algoritmasında, öncelikle ışın genişliği asgari değerde tutularak arama yapılır. Aranan en iyi sonuca ulaşılamazsa, ışın genişliği arttırılarak arama işlemi sürdürülür. Beklenen sonuca ulaşılana kadar da ışın genişliği arttırılır.

Işın aramasının kullanıldığı yerlerden birisi de bilgisayarlar tarafından otomatik olarak yapılan tercüme işlemleridir. Bilindiği üzere bir kelime, bilgisayar tarafından işlendiğinde, birden fazla anlama gelebilmektedir. İnsanlar kelimenin kullanımından (syntax, pragma) kelimenin anlamını kısa sürede doğru olarak anlayabilmekte ancak bilgisayarlar için bu anlama süreci ve doğru anlamın bulunması (semantics), hatırı sayılır bir süre almaktadır.
Çözüm olarak ışın araması algoritması, çok sayıdaki çeviri ihtimallerinden sadece belirli bir kısmını işleyerek doğru tercümeyi yapmak için kullanılabilir.

Yorumlar

  1. fatih

    “Işın aramasının kullanıldığı yerlerden birisi de bilgisayarlar tarafından otomatik olarak yapılan tercüme işlemleridir.” dediniz. Bu algoritma hız açısından değerlimidir? Çünki benimde hız sebebiyle, yazmak istediğim eşdeğer kelime arama/bulma algoritması ile aynı anlamda.

  2. Şadi Evren ŞEKER Article Author

    Işın araması yapay zeka problemlerinde sezgisel fonksiyon sonuçlarına göre arama yapar. Ağacın oluşturulma süresi BFS (sığ öncelikli arama) ile aynıdır. Ayrıca birden fazla ihtimal aynı anda aranabildiği için paralel çalışmaya müsait bir algoritmadır. Arama algoritmasının başarısı sezgisel fonksiyonun (heuristic function) çalışması ve üretilen düğüm sayısı ve sezgisel arama algoritmasının başarısına bağlıdır. Kabaca anlatacak olursak ışın araması mevcut başka bir sezgisel arama algoritmasının (heuristic search algorithm) paralel hale getirilmesidir.

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir