BİLİŞİM

Rastgele Sayı Üretiminde Yeni Bir Algoritma: FLDR

Hızlı ve etkili bir şekilde rastgele sayı üretebilmek uzun süredir söz konusu olan bir problem. Yüzyıllardır birçok şans oyunu; zar veya yazı-tura atışları veya kullanılan kartların karıştırılması gibi yöntemler kullanarak rastgelelik sağlamaya çalıştı.

20. yüzyılın ikinci yarısından itibaren ise bilgisayarlar; kriptografi, istatistik ve yapay zeka uygulamalarında ve birçok simülasyonda rastgeleliği sağlama görevini üstlenmeye başladı.

Bu bağlamda, geçtiğimiz günlerde MIT’den (Massachusetts Institute of Technology) araştırmacılar yeni bir bilgisayar algoritması geliştirerek en azından bazı durumlarda hız, isabet ve minimum hafıza kullanımı arasındaki dengeyi optimize etmeyi başardılar.

Hızlı Yüklü Zar Atıcı (Fast Loaded Dice Roller veya FLDR) adı verilen bu yöntem MIT’den yüksek lisans öğrencisi Feras Saad, araştırmacılar Cameron Freer ve Vikash Mansinghka ve Profesör Martin Rinard tarafından 23. Uluslararası Yapay Zeka ve İstatistik Konferansı’nda sunulacak.

FLDR Nedir?

Basitçe ifade etmek gerekirse, FLDR’nin bir zar atışını simüle ederek rastgele sayı üreten bir yazılım olduğu söylenebilir. Dahası bu sanal zar, istenilen sayıda yüzeye sahip olacak şekilde ve istenen yüzeyler belirli yüzdelerle gelebilecek şekilde yani “yüklü” olarak ayarlanabiliyor.

Bu durumda da belirli bir atışın sonucunda hangi yüzeyin geleceği önceden bilinemiyor fakat yeterli sayıda atış yapıldığında hangi yüzeylerin hangi yüzdelerle geleceği kontrol altına alınmış oluyor. Bu şekilde örneğin tarafların eşit güçte olmadığı spor karşılaşmalarının sonuçları simüle edilebiliyor.

Zira bir tarafın kazanma ihtimali daha yüksek olsa bile belirli bir karşılaşmanın sonucu bilinemiyor.

FLDR yönteminde zarlar tamamen belirtilen yüzdelere sahip olarak simüle edilebiliyor. Örneğin, 4 taraflı bir zarı tüm yüzeyleri aynı ihtimal ile gelebilecek şekilde (her yüzey %25 ihtimalle) ayarlayabileceğiniz gibi istediğiniz tarafları %1-%20-%30-%49 veya tercih ettiğiniz başka her ihtimalle gelebilecek şekilde de simüle edebiliyorsunuz.

MIT ekibi çok sayıda yüzeyi olan zarları simüle edebilmek için rastgeleliği daha temel bir kaynaktan, yüzde 50’şer ihtimalle 0 veya 1 sonucunu veren, dijitalleşmiş bir yazı tuta atış simülasyonundan sağladılar. Tasarımlarında öne çıkan bir öğe olarak yöntemlerinin etkinliği ise, bu sanal zar atışını kaç kere gerçekleştirmek zorunda olduklarına göre değişiklik gösteriyor.

Esasında, geçmişte bu alanda gerçekleştirilmiş olan ve köşe taşı niteliğindeki bir çalışmada Donald Knuth ve Andrew Yao teorik olarak mümkün olan en yüksek etkinliğe sahip bir zar atış algoritması icat etmişlerdi.

Fakat Saad’a göre “onların algoritması zaman bakımından optimum” yani hızlandırılması imkansız iken, “kullanılan bilgisayar hafızası, yani bilginin saklandığı alan bakımından verimsiz”di.

Gerçekten de, seçilen yüzey sayısı ve başka bazı diğer faktörlere bağlı olarak kullanılan hafıza üstsel olarak artmaktaydı. Bu nedenle de Saad’a göre, teori alanındaki önemine rağmen Knuth ve Yao’nun metodu belirli durumlar haricinde pratik değildi.

FLDR ise bütün bunlar göz önüne alınarak geliştirilmiş. Saad, FLDR’nin “zaman bakımından neredeyse aynı derece verimli” olduğunu ve bunun yanında kullanılan hafıza bakımından çok daha iyi olduğunu ifade ediyor.

FLDR, 10.000 kata kadar daha az bellek alanı kullanabiliyor ve işlem başına Knuth-Yao’nun algoritmasına kıyasla en fazla 1.5 kat fazla zaman harcıyor.

Alias Yöntemi

FLDR’nin en büyük rakibi ise, hali hazırda onyıllardır kullanılmakta olan Alias yöntemi. Freer’e göre, teorik açıdan bakıldığında, FLDR’nin Alias’a göre net bir avantajı var: Temel simülasyonu (sanal yazı-tura atışlarını) daha verimli olarak kullanmak. Ayrıca belli durumlarda FLDR, Alias’a göre daha hızlı bir şekilde yüklü zar atışını simüle edebiliyor.

Öte yandan, FLDR çok yeni bir yöntem olduğu için doğal olarak henüz yaygın olarak kullanılmıyor. Bununla birlikte onu geliştirenler daha şimdiden yazılım ve donanım desteği ile FLDR’den alınan verimi artırmanın yollarını arıyor ve rastgele sayı üretimi dışında başka uygulamalarda da FLDR’den faydalanılmasına çalışıyorlar.

Bu bağlamda Mansinghka, FLDR’nin özellikle Monte Carlo simülasyonlarından (bir sistemde risk ve belirsizliğin etkisini belirlemek için kullanılan bir çeşit teknik) sağlanan etkinliği artırmak için kullanılabileceğini düşünüyor.




Kaynak: https://www.pxfuel.com/en/free-photo-opcjw

Monte Carlo Yöntemi

Örneğin Birleşmiş Milletler, deprem ve nükleer testler gibi olayların nerelerde gerçekleştiğini gösteren sismik aktivite simülasyonlarını kullanıyor. Bu simülasyonlarda eldeki sismik veriler için olası açıklamalar üretmek amacıyla Monte Carlo yöntemine başvuruluyor.

Daha fazla bilgi için: Problem Çözümlerinde Monte Carlo Algoritmasının Yeri

Bu teknikte, ikinci bir Monte Carlo simülasyon serisi çalıştırılarak ele alınan sismik simülasyonlardaki alternatif parametreler test ediliyor ve eldeki veriyi ortaya çıkaran değişken değerleri belirlenmeye çalışılıyor. Bu parametreler de deprem ve nükleer testlerin gerçekte nerede ve ne zaman gerçekleşmiş olabileceğine dair bilgiler içeriyor.

“Monte Carlo çıkarsaması (Monte Carlo inference) Monte Carlo simülasyonlarına göre yüz binlerce kez daha fazla rastgele sayıya ihtiyaç duyuyor.” diyor Mansinghka.

Ona göre; “FLDR’nin fayda sağlayabileceği en önemli noktalardan biri bu. Monte Carlo çıkarsama ve simülasyonları, yapay zekanın bir alt alanı olan ve çok sayıda uygulaması olan olasılıksal programlama için de temel bir öneme sahip.”

FLDR yönteminin ilk ipuçları aslında aynı ekip tarafından 2020 Ocak ayında gerçekleştirilen bir sempozyumda sunulan farklı bir algoritma sırasında verilmişti.

Araştırmacılar bu çalışmada, yüklü bir zar atışını simüle edecek bir bilgisayarda bu işlem için önceden belirli bir bellek alanı belirlendiğinde, algoritmalarının minimum olası hata miktarını, yani zarın her yüzeyi için belirlenen yüzdelere ne kadar yaklaşılabildiğini tespit edebileceğini gösterdiler.

Buna göre, eğer herhangi bir bellek sınırlaması getirilmezse hata payını 0’a kadar düşürmek mümkün fakat Saad FLDR ile hızdan taviz vermeden önemli oranda daha az hafıza kullanan ve 0 hata üreten bir altermatif belirlemiş.

Başta bu yöntem ulaşılması çok zor bir hedef gibi gözükmesine rağmen Freer ısrarlarıyla Saad’ı bu çalışmayı yapmaya ikna etmiş. İşte FLDR bu şekilde başlayan bir yolculuğun sonunda ortaya çıkmış ve şu an rastgele sayı üretimi alanında ana teknoloji haline gelme ihtimalinden söz ediliyor.

Dolayısıyla, büyük oranda rastgele süreçlerle şekillenen günümüz dünyasında FLDR’nin gelecekteki öneminin çok daha dikkate değer boyutta olacağı iddia edilebilir.

Kaynak: https://techxplore.com/news/2020-05-algorithm-quickly-simulates-dice.html

İleri Okuma – Rastgele Sayılar ve Monte Carlo Yöntemi: https://sarkac.org/2018/11/rastgele-sayilar/

Matematiksel

Paylaşmak Güzeldir

Deniz Karagöz

Hukuk eğitimi almış olmama rağmen matematik her zaman ilgimi çeken bir bilim olmuştur. Matematiksel.org bana bu ilgimi üretkenliğe çevirme şansı veren kaliteli bir ortam. Bu yüzden gerek çevirilerim gerekse yazılarımla katkıda bulunabilmek benim için oldukça anlamlı. Aynı zamanda buradan beslenerek öğrenmeye de devam ediyorum. İyi okumalar

Bir cevap yazın

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

Kapalı