Hesaplamalı Öğrenme Kuramı
Hesaplamalı öğrenme kuramı, öğrenmeyi bir hesaplama ve örnek karmaşıklığı problemi olarak ele alarak, hangi kavramların örneklerden verimli bir şekilde öğrenilebileceğini inceler.
Tanım
Hesaplamalı öğrenme kuramı, kavramları örneklerden öğrenmek için gereken veri ve hesaplama kaynaklarının incelenmesidir; muhtemelen yaklaşık olarak doğru (PAC) modelinde, bir kavram sınıfı, bir algoritmanın polinom sayıda örnekten ve polinom zamanda, yüksek olasılıkla doğru olan bir hipotez üretebilmesi durumunda öğrenilebilir kabul edilmektedir.
Kapsam
Bu konu, öğrenilebilirliğin biçimsel modellerini kapsar: bir kavramın polinom sayıda örnek ve hesaplama ile yüksek olasılıkla yüksek doğrulukta ne zaman öğrenilebileceğini sorgulayan muhtemelen yaklaşık olarak doğru (PAC) modeli, hata sınırlı ve çevrimiçi öğrenme modelleri, zayıf ve güçlü öğrenilebilirlik ile güçlendirme (boosting) ve hesaplamalı karmaşıklıkla bağlantıları. Öğrenmenin hem istatistiksel hem de algoritmik uygulanabilirliğini ele almaktadır.
Temel sorular
- Hangi kavram sınıfları örneklerden verimli bir şekilde öğrenilebilir?
- Bir kavramı öğrenmek ne kadar veri ve hesaplama gerektirir?
- Zayıf ve güçlü öğrenilebilirlik arasındaki ilişki nedir?
- Öğrenilebilirlik, hesaplamalı karmaşıklıkla nasıl bir bağlantı kurar?
Temel kuramlar
- Muhtemelen yaklaşık olarak doğru öğrenme
- Valiant'ın modeli, verimli bir algoritmanın polinom sayıda örnekten yüksek olasılıkla düşük hatalı bir hipotez üretebilmesi durumunda bir kavram sınıfını öğrenilebilir olarak tanımlar; bu da öğrenilebilirliği kesin bir hesaplamalı soru haline getirmektedir.
- Zayıf öğrenilebilirlik ve güçlendirme (boosting)
- Merkezi bir sonuç, şans seviyesinden biraz daha iyi öğrenilebilen herhangi bir sınıfın aynı zamanda güçlü bir şekilde öğrenilebilir olduğunu göstermektedir; bu durum, zayıf öğrenicileri doğru olanlara dönüştüren güçlendirme (boosting) algoritmalarına doğrudan yol açmıştır.
- İstatistiksel ve hesaplamalı sınırlar
- Öğrenilebilirlik, hem kapasite ölçütleriyle ilişkili örnek karmaşıklığı hem de hesaplamalı zorluk ile sınırlıdır; bu nedenle bazı sınıflar istatistiksel olarak öğrenilebilir olsa da hesaplamalı olarak çözülemez kabul edilmektedir.
Klinik önem
Hesaplamalı öğrenme kuramı, öğrenme algoritmalarının neler başarabileceği ve neleri başaramayacağı için biçimsel bir temel sunar ve en önemlisi güçlendirme (boosting) olmak üzere pratik yöntemlere doğrudan ilham vermiştir; bu yöntem, zayıf öğrenicilerin güçlü öğrenicilere dönüştürülüp dönüştürülemeyeceği sorusundan ortaya çıkmıştır. Öğrenmeyi titiz bir hesaplamalı disiplin olarak çerçevelemektedir.
Tarihçe
Valiant, 1984 yılında muhtemelen yaklaşık olarak doğru (PAC) modelini tanıtmış, öğrenmeye kesin bir hesaplamalı tanım kazandırarak bu alanı kurmuştur. Sonraki çalışmalar, örnek karmaşıklığı karakterizasyonlarını, güçlendirmeyi (boosting) motive eden zayıf ve güçlü öğrenilebilirliğin eşdeğerliğini ve öğrenmenin hesaplamalı sınırlarını gösteren zorluk sonuçlarını ortaya koymuştur.
Öne çıkan isimler
- Leslie Valiant
- Michael Kearns
- Robert Schapire
İlgili konular
Temel eserler
- valiant1984
- kearns1994
- vapnik1995
Sıkça sorulan sorular
- Muhtemelen yaklaşık olarak doğru ne anlama gelir?
- Rastgele örneklem üzerinde yüksek olasılıkla, öğrenicinin yaklaşık olarak doğru olan, yani gelecekteki verilerde küçük bir hataya sahip olan bir hipotez üretmesi anlamına gelmektedir. Öğrenilebilirlik, bunu yalnızca polinom olarak artan sayıda örnek ve hesaplama miktarıyla başarmayı gerektirmektedir.
- Öğrenme kuramı güçlendirmeye (boosting) nasıl yol açtı?
- Araştırmacılar, rastgele tahminden sadece biraz daha iyi olan bir öğrenicinin yüksek doğrulukta bir öğreniciye dönüştürülüp dönüştürülemeyeceğini sorgulamıştır. Zayıf ve güçlü öğrenilebilirliğin eşdeğer olduğuna dair kanıt yapıcı nitelikteydi ve bu yapı, pratikte yaygın olarak kullanılan güçlendirme (boosting) algoritmalarına dönüşmüştür.