Makine Öğrenimi, Kolmogorov Karmaşıklığı​

Makine Öğrenimi

Makine Öğreniminin, geleneksel yöntemlerle nasıl çözüleceğini bilmediğimiz karmaşık sorunların üstesinden gelmek için oldukça güçlü bir araç olduğunu biliyoruz. Görüntü sınıflandırma gibi problemler Makine Öğrenmesi ile etkili bir şekilde çözülebilir, çünkü günün sonunda, bu tür bir görev için veri toplamak, bu kadar karmaşık ve zor bir problem için elle yazılmış kurallara uymaktan çok daha kolaydır.

Fakat ne çözeceğimizi zaten bildiğimiz durumlarda ne olacak? Makine Öğrenimini, halihazırda bilmiş olduğumuz çözümlere uygulamak için ne yapacağız? Fizik simülasyonu gibi görevler, görevi yöneten kural ve denklemlerin zaten iyi biliniyor bu durumlarda ne olacak?

Pek çok durumda, bunu yapmak için bilgisayar bilimlerindeki ezberleme ve hesaplama arasındaki denge gibi ilginç kavramlar ve Kolmogorov karmaşıklığı olarak adlandırılan bir kavram iyi bir çözüm gibi duruyor.

Bu konuda düşünmeye başlamanın yolu şudur: açık olmasa da, ilgilendiğimiz herhangi bir fenomen, problem veya matematiksel işlev için (ilk etapta cevap bulmak için bir yol olması şartıyla) her zaman bir yol vardır. Yalnızca ne kadar hesaplama yaptığımız ve ne kadar hafıza kullandığımız arasında bir değişim yapmaktayız.

Örneğin, sin(x)'i hesaplayan çok basit bir Python programını ele alalım:

def f(x):
    return np.sin(x)

Bu, sin işlevinin “doğrudan” bir hesaplaması olarak adlandırdığımız şeydir, ancak
sin işlevinin varsayımsal olarak hesaplanması için pahalı bir işlem olduğunu varsayıyoruz. Bu durumda farklı bir yaklaşım almak isteyebiliriz.
Örneğin, birçok farklı x değeri için sin(x) ön hesaplama değerleri
ve bunları aşağıdaki gibi büyük bir arama tablosunda dizeleyin:

def f(x):
    return {
        0.00: 0.00,
        0.34: 0.34,
        0.69: 0.64,
        1.04: 0.86,
        1.39: 0.98,
        ... :  ...,
        1.74: 0.98,
        2.09: 0.86,
        2.44: 0.64,
        2.79: 0.34,
        3.14: 0.00,
    }[x]

Şimdi, bazı pahalı işlemlerle sin(x) değerini “doğrudan” hesaplamak yerine, arama tablosundaki girişimizin değerine bakarak anında sin(x) değerini “hesaplayabiliriz”. Dezavantajı şudur – şimdi sin fonksiyonunu yüz binlerce kez önceden hesaplamamız ve tüm önceden hesaplanmış sin(x) değerlerini bellekte tutmamız gerekir. Daha az hesaplama karşılığında daha fazla bellek kullanımı (ve ön hesaplama) yaptık. Her ne kadar arama tablosu aşılmaz derecede büyük olabilse de ve karmaşık fonksiyonlar için önceden hesaplama zamanı delice büyük olsa da, teoride bu aynı numara, sin gibi sadece çok basit fonksiyonlar için değil, ilgilendiğimiz her fonksiyon için de geçerlidir.

İki uç veri noktası gibi bu iki programı düşünebiliriz – aynı işlevi çok farklı hesaplama ve bellek kullanımlarıyla hesaplamanın iki farklı yolu. Eğer onların hafıza kullanımlarını ve hesaplama zamanlarını ölçmek ve bunları bir grafiğe çizmek isteseydik, muhtemelen şöyle bir şey olurdu:

Bundan sonra sorulacak doğal soru, bu iki uç arasında bir yerde yer alan herhangi bir jenerik program olup olmadığıdır. Hafızayı ve hesaplamayı, hesapladıkları temel fonksiyona uygun bir şekilde işlemden geçiren programlar. (Bu program aslında var) Örneğin, yeniden hesaplamayı önlemek için hesaplamaları önbelleğe alan genel bir program yazabiliriz. Bu, bazı ek bellek kullanımlarının maliyeti karşılığında çıktıyı zaten hesapladığımız bir girdi elde edersek, bazı performans tasarrufu sağlar:

cache = {}

def f(x):
    if x in cache:
        return cache[x]
    else:
        y = np.sin(x)
        cache[x] = y
        return y

Daha önce olduğu gibi, hesaplama için belleği takas etmenin “genel” bir yolunu bulduk.
Hangi fonksiyonla ilgilenirsek ilgilenelim (en azından teoride) çalışabilir.

Ayrıca, fonksiyonumuza yaklaştığımız programları da bulabilirsiniz. Daha hızlı ve daha az doğru hesaplama karşılığında biraz daha fazla bellek kullanarak bilgi işlem yapmakta mümkün. İşte sin işlevi için bir yaklaşım:

def f(x):
    x = x % (2*np.pi)
    return (
        (16*x*(np.pi - x)) / 
        (5*np.pi*np.pi - 4*x*(np.pi - x)))

İlk önce bu işlevlerde ek bellek kullanımının nerede olduğu açık olmayabilir, ancak bu durumda 2, 16, 5, 4, ve
pi tıpkı arama tablosundaki gibi ek “özel” değerlerdir – bunlar “bellek” dir. Ve bu belirli yaklaşımsin, ile sınırlı olsa da, bu programın benzer görünen ancak herhangi bir işlevi basitçe farklı uygun sabit değerler bularak bulabilen genel bir versiyonunu bulmak o kadar zor değildir.

Bu iki ekleme göz önüne alındığında sorulacak başka bir soru şudur: Şimdiye kadar sunduğumuz gibi, grafiğin sol alt kısmındaki noktada yatan – çok fazla bellek kullanmamak – kullanmamayı sağlayacak genel bir program var mı? Sorusunu önümüze getiriyor.

Bize yol gösterecek yön Makine Öğrenimidir- çünkü işlevi çevrimdışı olarak değerlendirmekle ilgilenirsek, eğitim verilerini toplayabilir ve daha sonra işlevi yaklaştırmak için genel Makine Öğrenimi algoritmasıyla eğitebiliriz. Makine Öğrenimi’nde, performanslarını görmek için grafiğimize ekleyebileceğimiz farklı bir genel algoritma sınıfımız var.

Örnek olarak, Sinir Ağları’na bir göz atalım – Sinir Ağlarının hesaplama özelliklerini incelersek, muhtemelen denemek zorunda kalmadan bu grafik üzerinde nerede durabileceklerini tahmin edebiliriz.

Her şeyden önce, hesaplama zamanına bakalım. Şimdi, bir Sinir Ağının hesaplama süresi temel olarak sahip olduğu ağırlıkların sayısıyla orantılıdır ve sahip olduğu ağırlıkların sayısı da bellek kullanımını belirler. Bu yüzden hesaplama süresi ve bellek kullanımı standart bir Sinir Ağında birleştirilmiştir – görsel olarak Sinir Ağları her zaman grafiğin köşesinde bir yerde bulunur.

Diğer soru ise “Sinir Ağında” kaç tane ağırlığa ihtiyacımız olduğunu ne belirler? Kabaca, bu iki şey tarafından belirlenir – Sinir Ağının ne kadar doğru olmasını istediğimiz ve uydurduğumuz fonksiyonun ne kadar karmaşık olduğu. Eğer bütün bu özelliklere birlikte bakarsak, bunun gibi bir şey görürüz.

            Computation Time     is proportional to     Memory Usage
            Memory Usage         is proportional to     Accuracy
            Accuracy   is inversely proportional to     Complexity

Bu nedenle, Sinir Ağımızın köşegeninin ne kadar uzağa gideceği, nihayetinde istediğimiz doğruluk ve uydurmak istediğimiz fonksiyonun karmaşıklığı ile yönetilir. Bu hem iyi hem de kötü bir haberdir – iyi, çünkü yaklaştırmak istediğimiz işlev karmaşık değilse, o zaman kendimize güveneceğimizden emin olabiliriz – düşük hesaplama süresi ve düşük bellek kullanımı – ve çünkü kötü yanı ise pahalı ve çok fazla bellek kullanımına sebep oluyor.

Fakat bir fonksiyonun karmaşıklığı ile tam olarak ne kastediyoruz? Bunu daha iyi sezgisel bir şekilde anlayabilseydik, Sinir Ağları’nın tatlı noktaya ne zaman vurabileceğini daha doğru tahmin edebiliyor olurduk. Bir işlevin ne kadar karmaşık olduğuna karar vermek işte Kolmogorov Karmaşıklığı’nın devreye girdiği yer burasıdır.

Kolmogorov Karmaşıklığı

Basitçe söylemek gerekirse, bazı fonksiyonların Kolmogorov Karmaşıklığı, verilen tüm girdiler için fonksiyonla tamamen aynı çıktıları üretebilen mümkün olan en kısa programın uzunluğudur. Ayrıca, Kolmogorov Karmaşıklığı kurallarına göre, programların herhangi bir şekilde dosya açmasına veya dış dünyayla iletişim kurmasına izin verilmez – tüm veriler kaynak kodunda saklanmalıdır.

Örneğin, hiçbir girdi almayan ve dizgiyi çıkaran işlev:

abababababababababababababababab

basitçe küçük program tarafından üretilebilir:

def f():
    print "ab" * 16

Bu, tekrarlayan ab  bu işlevi ifade eden çıktı, özellikle karmaşık bir işlev değildir. Öte yandan, girdi ve dizgeyi üreten işlev:

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

nispeten daha karmaşıktır – temelde verbatim dizesini basmak için bir program gerektirir:

def f():
    print "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

Bu dizginin saklanması programı çok daha büyük yapar, bu da onu üreten işlevin karmaşık olması gerektiği anlamına gelir.

Burada dikkat edilmesi gereken ilginç bir şey var – ilk program (* operatörünü kullanarak) bir şey hesaplar, ikincisi ise sadece dizgiyi ezberler. Bu hemen bize iyi bir yönlemdirme verir: ezberlemesi gereken işlevler genellikle daha karmaşıktır.

Ve Kolmogorov Karmaşıklığı, dizeleri çıkaran işlevlerle sınırlı değildir. Resimler, fizik simülasyonları veya başka herhangi bir şey üreten fonksiyonlar için aynı analizi kullanabiliriz. Aşağıdaki görüntüleri göz önüne alın, ikisinin de karmaşık işlevlerden üretildiğini düşünüyor muyuz?

Aslında pek değil – muhtemelen her iki resmi de oluşturabilecek basit bir program var – oluşturmak için basit kurallar almış gibi görünüyorlar. Peki ya bu görüntüler?

Şimdi bunlar çok daha karmaşık. Program içinde çok fazla ham veri depolamaksızın bu görüntülerden herhangi birini üretebilecek bir program düşünmek zor görünüyor. Burada başka bir sezgi kazanıyoruz: bu doğal veriler genellikle karmaşık ve ezber gerektiriyor. Peki ya bu iki resim?

Aha – bu sefer hileli bir soru. İlk görüntü elbette bir fraktaldır – karmaşık görünen ama aslında bizim bildiğimiz gibi bir görüntüyü oluşturmak için kullanılabilecek basit bir program vardı.

İkincisi rasgele gürültüdür – ve iki cevabı olabilir. Eğer bu gürültü sözde rasgele sayı üretecinden geliyorsa veya sadece bu kesin gürültüyü değil, gürültü üretmek istiyorsak, sözde rastgele sayı üreteçlerinin göreceli olarak basit programlar olduğunu bildiğimiz için teknik olarak karmaşık değildir – ancak – eğer bu gerçek rastgele gürültü ise ve tam olarak çoğaltmak istiyoruz, o zaman maksimum derecede karmaşıktır – basitçe saklamak ve yazmadan oluşturmak için mümkün bir program yoktur. Bu bize başka bir sezgiyi verir: sadece giriş ve çıkışlarını gözlemleyerek bir fonksiyonun karmaşıklığını bilmek son derece zordur.

Peki ya fizik simülasyonu gibi bir şey? Kenar kasaları unutun ve şu an için soruları kandırın ve topun hareketi göz önüne alındığında bu videodaki kumaşın hareketini üretmek için bir program yazmanız gerektiğini hayal edin. Peki bu karmaşık mı?

Kesinlikle diğer örneklerimizle kıyaslandığında öyle duruyor, belki de ilk bakışta düşündüğünüz kadar karmaşık değildir – bence kumaşın hareketini sadece hareketin aşamasını bilerek oldukça doğru bir şekilde tahmin etmenin mümkün olacağını düşünüyorum. Topun İçimdeki duygu, zekice bir şey yaparsanız, sadece bir parametreyi alıp cevaben kumaşın durumunu iyi bir şekilde tahmin edebilecek basit bir programın olabileceğidir. Peki ya bu?

Tamam, şimdi bu karmaşık – devam eden her tür küçük kıvrımlar ve kaotik hareketler var ve bu kesin davranışı üretmek için büyük bir karmaşık program yazmanız gerekecek gibi görünüyor.

Ancak, karmaşıklığı doğrudan sezgimizle hissetmek yerine doğrudan hesaplayabilmemizin bir yolu var mı? Genel durumda bunun imkansız olduğu gösterilmiştir – ancak buna Temel Bir Bileşen Analizi (PCA) adı verilen bir algoritma ile yaklaşık bir hesaplama yapabiliriz. PCA’yı bazı verilere uyguladığınızda, geri aldığınız şey, belirli bir hata eşiği için ne kadar sayıya ihtiyaç duyulabileceğine dair tahmin veren basit bir algoritmadır.

Bunu bir fizik simülasyondan toplanan bazı verilere uygulamayı deneyelim. İlginçtir ki, fiziksel simülasyon verilerine uygulandığında, PCA özel bir davranış sergiler – bize simülasyonun “karmaşıklığını” söylemenin yanı sıra, ilgilendiğimiz fiziksel olarak simüle edilen nesne için ana deformasyon eksenlerini de çıkarır:

Karmaşıklığı, orijinal hareketi yeniden yapılandırmak için bu deformasyon eksenlerinin ne kadarının gerekli olduğunu inceleyerek ölçebiliriz. İleri geri sallanan kumaş tabakamız gibi basit bir hareket için hareketi neredeyse tamamen yeniden yapılandırabilmek için sadece bir veya iki eksene ihtiyaç duyarız, karmaşık ince kıvrımlı kumaşlarımız için yüzlerce hatta binlerce ekseneihtiyacımız vardır.

Aşağıda, bir karaktere bağlı bir pelerin hareketini yeniden yapılandırmak için farklı sayıda eksen seçersek neler olduğunun bir karşılaştırmasını görebilirsiniz. Daha az eksenle daha az ayrıntı elde edersiniz – karmaşıklık etkili bir şekilde azaltılır. Bu durumda, orijinal kumaşın yaklaşık 3000 köşesi olmasına rağmen, kumaşın durumunu, kalite, detay ve karmaşıklık açısından çok fazla kayıp olmadan temsil etmek için sadece 256 eksene (bazen Temel olarak da adlandırılır) ihtiyacımız vardır.

Bu bize fizik simülasyonlarının neredeyse her zaman ilk bakışta göründüklerinden daha az karmaşık olduğu gösteriyor.(bunun da kısıtlama teorisine dayanarak iyi bir nedeni var). Tüm bunlarda bize, Sinir Ağı ile oldukça basit bir fizik simülasyonu yaklaştırmaya çalışırsak, hesaplama ve ezberleme arasındaki tatlı noktaya ulaşma şansımızın yüksek olduğunu gösteriyor!

Sonuç

Sinir Ağları sadece nasıl çözeceğimizi bilmediğimiz şeyler için iyi değildir, nasıl çözeceğimizi bildiğimiz problemlerde büyük performans kazanımları sağlayabilirler. Aslında, Sinir Ağları’nın bir görevde ne kadar iyi bir performans göstermesini beklediğimizi anlamak ve bir çeşit sezgi elde etmek için Kolmogorov Karmaşıklığı kavramını kullanabiliriz (ve hatta PCA’yı basit bir önlem için kullanabiliriz).

Ancak geleceğe baktığımızda, tüm bunlarla ilgili hala garip bir şey var – ki aslında yapmak istediğimiz şeyi yapmadık – bellek kullanımı için kolayca işlem yapmanın bir yolunu bulduk – Standart Sinir Ağları’nda ikisi birleştiler ve hesaplama zamanı her zaman ağırlık sayısıyla orantılıydı. Tüm bunların ışığında, karmaşıklık azsa tatlı noktaya varabileceğimiz sonucuna varıyoruz.