Matematik Ne İşe Yarar?

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

Olasılık kavramı, paranın yazı mı yoksa tura mı geleceğini kestirmek için hesap yapmak kadar basit bir matematik işlemiyle anlatılamaz. Temelinde aksiyomlar ve kendine ait kurallar yer alır. Kolmogorov Karmaşıklığı adıyla da bilinen Algoritmik Bilgi Teorisini anlamak için kısaca olasılığın temelindeki kavramları bilmek gerecektir.

Olasılığın matematiksel ifadesinin oluşumu on yedinci yüzyıla dayanır. Kombinatorik adı verilen hesaplama yöntemlerini geliştiren Blaise Pascal 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‘dur. İkinci 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 Aksiyomları Nedir?

Andrey Nikolaevich Kolmogorov
Andrei Nikolayevich Kolmogorov (1903-1987) 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.

Olasılık teorisinde Kolmogorov aksiyomları, temelde üç aksiyomdur. Birinci aksiyom bir olayın olasılığının negatif-olmayan bir reel sayı olduğunu söyler. İkinci aksiyoma göre örnekleme uzayının tümünü kapsayan bir basit olayın ortaya çıkması için olasılık her zaman birdir. Üçüncü aksiyom ise birbiri ile bağlantısız olayların olasılıklarının toplanabileceğini söyler. Okullarda öğrendiğimiz bu üç aksiyom bizlerin olasılıkta hesaplama yapabilmemizi sağlar. Ancak olasılık ile ilgili bilinmesi gereken şeyler bu kavramlar ile sınırlı değildir.

1960 yılında Ray Solomonoff (ABD’li matematikçi 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 arar. Aslında Solomonoff’a kadar olasılık hesabı klasik hesaplama yöntemine dayanır. Sonrasında ise modern olasılık hesabı başlar. 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. Bu kavram enformasyon kuramına da (bilgi teorisi) yeni bir bakış açısı kazandırır.

Algoritmik Olasılık Nedir?

Bu yazıda ne kadar bilgi var? Söylemesi zor. Uzunluğu açıkça bir gösterge değil çünkü bu bizim kelime seçimimize bağlı olacaktır. Eğer değerlendirmeyi başarır ve içinde sadece bir tane bilgi olduğuna karar verirseniz bu makale karmaşık sayılmaz. Ancak bir bilgi parçasının karmaşıklığını ölçmek mümkün mü?

Matematikçiler buna evet cevabını verdiler. Bilgiye bilgisayarın bakış açısından baktılar. Bir makine için bir bilgi parçası yalnızca bir sembol dizisidir ve ikili sayı dizisine (0 ve 1) dayanır. İkili sayı dizgesini kullanarak her bilgiyi karşı tarafa iletme şansı doğar.

Şimdi bir örneğe bakalım. 20 kez bir bozuk para atalım. Yazı gelince 0, tura gelince 1 yazalım. Sonuçlar 01010101010101010101 veya 01101100110111100010 biçiminde ya da bambaşka bir biçimde olabilir. İnsanlar ilk diziye bakınca bunun rasgele bir dizi olmadığını anlar. Ancak ikinci dizi için rakamların resadüf eseri dizildiğini düşüneceklerdir. Ancak bir bilgisayar iki dizilim arasındaki farkı algılayamaz. Bilgisayara göre bir paranın yirmi kere atılması deneyinde 220 olasılık vardır. Bu iki dizilimde bu olasılıklardan ikisini temsil eder.

Bu algı probleminin temel çözümü algoritmik olasılıkta yatar. Diyelim ki 20 kere değil de 20 katrilyon zar atalım. Sonuçlar yukardaki gibi olsun. Bu durumda ilk mesaj için komut olarak 10 katrilyon kere 01 yaz demek yeterli olur. Ancak ikinci mesaj için kısaltma yapılamaz. Tüm sayı dizisinin yazılması yani 20 katrilyonun hepsinin komut olarak girilmesi gerekir. Kısacası Kolmogorov karmaşıklığı teorisi olarak da bilinen Algoritmik Bilgi Teorisi (AIT) basit bir gözleme dayanmaktadır: Karmaşık nesneler kısa bir programla tanımlanamaz 

Kolmogorov Karmaşıklığı Nedir?

Belirli bir dizeyi üreten ve sonra duran (sonsuz döngüler istemiyoruz) en kısa bilgisayar programının uzunluğu Kolmogorov karmaşıklığı olarak adlandırılır. Diğer bir deyiş ile 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.

Bir dizinin Kolmogorov karmaşıklığını, bu dizideki bit cinsinden ölçülen “bilgi miktarı” olarak yorumlamak bizi bazı pratik sonuçlara götürür. Keyfi sonlu nesnelerin (grafikler vb.) Kolmogorov karmaşıklığını, ikili kodlamalarının karmaşıklığı olarak tanımlamamızı sağlar.

Bilgi teorisinde, Kolmogorov karmaşıklığı, bir şeyi tanımlamak için ne kadar hesaplama gerektiğini tanımlar. 
(Örneğin, 2 + 2 eklemek için bir komut dosyası, bir metin-konuşma programından daha düşük Kolmogorov karmaşıklığına sahiptir.) 

Konuyu daha basit bir biçimde düşünmek gerekirse Kolmogorov karmaşıklığı “sıkıştırılmış boyut” anlamına gelir. Zip, gzip, bzip2, sıkıştırma, rar, arj, vb. gibi programlar, bir dosyayı (metin, resim veya diğer bazı veriler) muhtemelen daha kısa bir dosya biçiminde sıkıştırır. Orijinal dosya daha sonra bir “açma” programı ile geri yüklenir. Düzenli bir yapıya sahip bir dosya önemli ölçüde sıkıştırılacaktır.

Öte yandan, düzenliliği olmayan bir dosya pek sıkıştırılamaz ve sonucunda sıkıştırılmış boyutu orijinal boyutuna yakındır. Bu örneklem çok yüzeysel olsa da yine de oldukça karmaşık bir konu hakkında bir ön fikriniz olmasını sağlayacaktır.

Konu hakkında daha fazla bilgi edinmek isterseniz bu makaleye göz atmanızı öneririz. Information is complexity; https://plus.maths.org/content/information-complexity


Matematiksel

Başa dön tuşu