OLASILIK / İSTATİSTİK

Kolmogorov Karmaşıklığı ve Algoritmik Olasılık

Hayatı boyunca pek çok ödül almış olan Kolmogorov, daha çok Olasılık Kuramıyla tanınsa da; harmonik analiz ve algoritmalarla modern matematiğe büyük katkılarda bulunmuştur. Bilginin taşınması ve işlenmesi konusunda yaptığı araştırmalarla, Kolmogorov Karmaşıklığı adıyla da bilinen Algoritmik Bilgi Teorisini geliştirerek günümüz bilgisayarlarının gelişiminin öncüsü olmuştur.

Gerçek dünyadaki anlaşılamayan olguları ya da şans oyunlarını düşündüğümüzde kavram olarak karşımıza rasgelelik çıkar. Belirsizlik ile birlikte rasgele olduğu düşünülen olaylar, ilk zamanlardan bu yana insanları hem ürkütür hem de meraklandırır.

Örnek olarak deprem, sel vb. doğa felaketlerinin ne zaman olacağını öngörememek ya da borsada daha fazla nasıl kazançlı çıkılacağını kestirememek, rasgeleliğin doğurduğu sonuçlardan bazılarıdır.

Rasgele, rastgele, seçkisizlik, gelişigüzel, tesadüfilik gibi kelimelerle eş anlamlı olarak kullanılır rasgelelik.

TDK’de bilgiye, isteğe, kurala veya belli bir sebebe dayanmaksızın oluveren karşılaşma, tesadüf diye geçerken İstatistik Bilim’inde bir sürecin olasılıksal yapıda olduğunu belirten terim olarak anlatılır. Yani nesneler kümesinden seçilecek her bir öğenin eşit seçilme şansının olmasıdır.

Kolmogorov Karmaşıklığını anlatmadan önce bazı kavramlara açıklık getirmek gerekir.

Olasılık ve Rasgelelik

Olasılık kavramı, gerçek dünyaya ait örnekleri de içeren geniş bir kavramdır. Paranın yazı mı yoksa tura mı geleceğini kestirmek için hesap yapmak kadar basit bir matematik işlemiyle anlatılamaz.

Temelinde aksiyomların ve kendine ait kuralların yer aldığı bu kavram, istatistik bilim dalı olma yolunda ilerlerken tarihsel süreçte ilk adımını oluşturur.

Olasılık, matematiğin aksiyomlarına (Kolmogorov’un Aksiyomları gibi), istatistiğin teoremlerine ve kanunlarına (merkezi limit teoremi ve büyük sayılar yasası gibi) ve fiziki bilimlerdeki kuramlara (evrim teorisi, termodinamiğin ilkeleri, kuantum mekaniği ve kimyada gazların yasalarını oluştururken gibi) kadar uzanır.

Olasılığın matematiksel ifadesinin oluşumu on yedinci yüzyıla dayanır. Kombinatorik adı verilen hesaplama yöntemlerini geliştiren Blaise Pascal (Fransız Matematikçi, 1623-1662) ve çağdaşları, olasılık kuramına büyük katkı sağlarlar.

Yakın tarihe damga vuran iki bilim insanı ise bu kuramı daha da ileriye götürür. Bu bilim insanlarından ilki, 1933 yılında kendi adına aksiyomları sunan Andrey Nikolaevich Kolmogorov (1903–1987) olurken, ikinci bilim insanı ise biyoistatistik alanına yakın olanların da iyi bileceği ve kendi adına regresyon denklemi bulunan Richard Threlkeld Cox (1898-1991)’tur.

Kolmogorov, gerçek dünyada yer alan olayların olasılık ölçüsü ilkelerini sunarken; Cox ise olasılığı daha ilkel bir kavram olarak ele alıp temel özelliklerini ortaya çıkarır.

Aslında aradaki fark, Kolmogorov aksiyomlarında olasılık sayılabilir toplamsalken, Cox için olasılık sonlu toplamsal olarak incelenir.

Kolmogorov Aksiyomları

Andrey Nikolaevich Kolmogorov
Andrei Nikolayevich Kolmogorov (1903-1987)

Ω bir Örnek Uzay ve U , Ω ’da bir σ toplanabilirlik varsayımına uygun küme olsun. Bir P: U → R fonksiyonu;

  • ∀ A ∈ U için P(A) ≥ 0,
  • P(Ω) =1 
  • A1, A2,… An’ler ayrık olaylar olmak üzere

koşullarını sağlarsa olasılık ölçüsü olarak nitelendirilir.

Görüldüğü gibi olasılık kuramı sağlam matematiksel temeli olan aksiyomlara dayanır ki bunlardan biri de yukarıda özellikleri verilen Kolmogorov Aksiyomlarıdır.

Algoritmik Olasılık

1960 yılında Ray Solomonoff (ABD’li matematikçi ve mucit, 1926-2009), algoritmik olasılığı keşfeder. Algoritmik olasılık, felsefik yapı olarak Bayes’in nedensellik kuralını temel alır.

Hangi durum ya da olay, diğer olayın ya da durumun oluşmasını ortaya çıkarır? Aralarındaki ilişki nasıldır? gibi sorulara yanıt arayan nedensellik ilkesinde Bayes, tümevarım ve olasılıksal yaklaşım yöntemini tercih ederken; klasik yöntem temelinde tümdengelim yaklaşımını ele alır.

Solomonoff’a kadar olasılık hesabı klasik yöntemine dayanırken kendisiyle birlikte modern olasılık hesabının önü açılır.

1960’lı yılların ortalarında ise birbirinden bağımsız ve habersiz iki bilim insanı Kolmogorov ve Chaitin’de (ABD’li matematikçi ve bilgisayar bilimci, 1947- ) algoritmik olasılığın kurallarını ortaya koyar.

Yani bu üç bilim insanıyla birlikte bu kavram, olasılığın rasgelelik ilkesine ayrıntılı bakış açısı sunmasının yanında enformasyon kuramına da (bilgi teorisi) yeni bir bakış açısı kazandırır.

Aşağıdaki iki örnekle konuyu ayrıntılanacaktır. Örnekler Chaitin’e aittir.

Gregory Chaitin

Birinci örnekte, Dünya Uzay Merkezi, uzak bir gezegene araştırmacı gönderir. Araştırmacı hesaplamalarını yapmak için yanına trigonometri cetvelini almayı unutur. Merkezden bu cetvelin kendisine gönderilmesini talep eder.

Oysaki bu uzak gezegenle herhangi bir iletişim aracı (telefon, fax vb.) ile iletişimde kalmak oldukça pahalıdır. Merkez ücreti ödemeyi göze alarak yirmi haneli bu geniş trigonometrik cetveli göndermeyi kabul eder. Diğer bir yandan merkezde bir matematikçi bulunur ve bu masraflı işi yapmak yerine aşağıdaki formül kısa mesajla iletilir. Bu kısa formülde araştırmacının ihtiyacını karşılayacaktır.

İkinci örnekte ise aradan bin yıl geçer ve araştırmacı artık hobilerine zaman ayırmak ister. Merkezden geçmiş yıllara ait basketbol maçlarını, hangi sporcunun kaç sayı attığını ve maç sonuçlarını ister. Merkez bu isteğin hemen yerine getirilmesini emreder.

Fakat sorun şudur ki istenen bilgiler için matematikçiler dâhil kimse bu bilgilerin tamamını içeren mesajın kısa halini yazamaz, yüksek ücret karşılığında bilgilerin gönderilmesine karar verilir.

İki örnekten de anlaşılacağı gibi bazı bilgileri kısaltabilirken bazı bilgileri kısaltmak mümkün olmayabilir. Enformasyon bilimi burada devreye girer.

Bilgisayar terminolojisi ikili sayı dizisine (0 ve 1) dayanır. Bu ikili dizgede 0 ve 1 sayaklarından oluşan hanelere bit denir. Bir bit’te ya 0 ya da 1 sayağı vardır.

İkili sayı dizgesini kullanarak her bilgiyi karşı tarafa iletme şansı doğar. Şöyle ki harfler, kelimeler ya da cümleler 0 ya da 1 sayakların belirli bir dizilimi ile bir sıra oluşturur. Burada mesajın ne kadar uzağa iletileceğinin yani mesafenin göz ardı edilmesi koşuluyla, mesajları 0 ve 1 sayaklarından oluşan diziler olarak ve uzak gezegeni de bilgisayar çıktısı olarak algılayabiliriz.

Mesajların iletilmesi için bilgisayara komut girmek gereklidir. Bu komutlara da algoritma adı verilir. Bir varsayım daha eklensin ve algoritma eğer doğruysa mesaj kesinlikle yerine ulaşacaktır bilgisi elimizde olsun. Örneğimize şöyle devam edelim.

20 kez atılan paranın yazı ve tura geliş dizisi aşağıdaki gibi olsun. Yazı gelince 0, tura gelince 1 sayağı kullanılsın. Yani aşağıdaki dizi 01’in on kez düzenli yazılmasıyla meydana gelsin.

01010101010101010101

Aynı durum tesadüfi olarak tekrar edilsin ve aşağıdaki dizi oluşsun.

01101100110111100010

İnsanlar ilk diziye bakınca bunun rasgele bir dizi olmadığını anlarken ikinci dizi için tesadüfi dizilim olduğunu söylerler. Oysaki bu insan algısı için geçerli bir durumdur. Bilgisayar iki dizilim arasındaki farkı algılamaz. Bilgisayara göre bir paranın yirmi kere atılması deneyinde 220 olasılık vardır ve bu iki dizilimde bu olasılıklardan ikisini temsil eder. Bilgisayara göre iki dizinin de gelme şansları birbirine eşittir.

Yani insan, sadece dizilime bakarak rasgelelik konusunda karar vermez. Deneyimleri de rasgeleliğe bakış açısını yönlendirir. Bilgisayarlar ise dizilimler hakkında yorum yapmak yerine sadece verilen komutları algılar.

Konuya ilişkin başka bir örnek ise 3.14159 26535 89793 23846… sayısı yani pi sayısı olsun. Bir kişi eğer pi sayısının dizilimi hakkında bilgi sahibiyse bu diziyi rasgele olarak değil, bilinçli seçilmiş bir dizi olarak algılar.

Öte yandan pi sayısının basamakları hakkında bilgi sahibi olmayan kişi, bu dizilimi rasgele dizi olarak düşünür.

Görüldüğü gibi bu algı probleminin temel çözümü algoritmik olasılıkta yatar. Diyelim ki 20 kere değil de aynı komut 20 katrilyon kere iki defa yazılsın. Fakat ilkinde 01 dizisi ardışık, ikincisinde ise rasgele dizilsin. Bu durumda ilk mesaj için komut olarak 10 katrilyon kere 01 yaz demek yeterli olurken ikinci mesaj için kısaltma yapılamaz.

Tüm sayı dizisinin yazılması yani 20 katrilyonun hepsinin komut olarak girilmesi gerekmektedir. Diğer bir deyişle mesajın tamamını göndermekten başka algoritma yazılamamaktadır.

Rasgelelik kavramına sunulan yukarıdaki bakış açısı, olasılığın temelini güçlendiren bir sonuca iter. Bu modern tanım ile olasılık aksiyomları ve olasılık kavramının geçerliliği ve bilim dalları arasındaki kullanımı daha sağlam bir yolda olur.

Kolmogorov Karmaşıklığı

Bir iletiyi karşı tarafa mesaj olarak göndermek için sonsuz sayıda algoritma oluşturulabilir. Örneğin 100 sayısı; 50*2, 25*4, 98+2, 105-5… gibi sayısız algoritma üzerinden mesaj haline getirilebilir.

Fakat burada amaçlanan minimal algoritma yoluyla mesajı komut haline getirmektir. Bir dizi için minimal algoritma tek ya da daha fazla sayıda da olabilir.

Oluşturulan dizi ister rasgele seçime dayansın isterse bilinçli bir seçim olsun bu noktada minimal algoritma rasgele olmak zorundadır. Eğer bu koşul sağlanmazsa aynı mesajı iletecek o diziden daha minimal bir algoritma vardır ve dolayısıyla bu dizi minimal algoritma olma koşulunu sağlayamaz.

Yukarıda verilen bilgiler ışığında Kolmogorov karmaşıklığı tanımı şöyledir: Bir dizinin karmaşıklığı, o diziyi ileten minimal algoritmanın uzunluğuna eşittir. Dolayısıyla bit sayısı Kolmogorov karmaşıklığına yaklaşık olarak eşit olan dizi, rasgeledir.

Bu tanım bizi çok önemli bir sonuca yani “rasgeleliğin ölçüsüne” götürür. Matematiksel olarak şu şekilde ifade edilir.

Rasgele minimal algoritma (m), Kolmogorov karmaşıklığı da K(k) olarak tanımlansın.

olur. K1 ve K2 karmaşıklık fonksiyonları varken eğer her m için d sabiti elde ediliyorsa;

olur. Yani tüm m dizileri için öyle bir d sabiti vardır ki bu sabit aşağıdaki eşitsizliği sağlar:

K1(m) ≤ K2(m) + d

Eşitsizlikten de anlaşılacağı gibi bir dizi oluşturulduğunda onun rasgele oluşmadığını göstermek için o dizinin mesajını iletecek algoritmadan daha kısa bir algoritmayı bulmak yani o dizinin minimal algoritma olmadığını göstermek yeterliyken; amaçlanan dizinin rasgele seçim olduğunu kanıtlamaksa o dizinin minimal algoritmalı dizi olduğunu göstermek yeterlidir.

Sonuç olarak modern çağa damga vuran algoritmik bilgi teorisi, istatistik ve matematiğin yanında uygulama alanları ile bilgisayar ve iletişim bilimlerinin de ötesini görmenin yollarını artıracaktır.

Bu yazı Timur Karaçay’ın “Olasılığın Matematiksel Modelleri adlı makalesinden uyarlanmıştır.

Matematiksel

Olgun Duran

Ömür boyu öğrencilik felsefesini benimsemiş amatör tiyatro oyuncusu, TEGV'de gönüllü aktivist; kitaplarından, doğaya hayranlığından, yeni yerleri görmekten, gittiği yerlerin kültürünü keşfetmekten ve bunların uğruna çabalamaktan vazgeç(e)meyen kişi...  

Bir cevap yazın

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

Başa dön tuşu