01.04.2014
MEH535 Örüntü Tanıma
2. Karar Teorisi
Doç.Dr. M. Kemal GÜLLÜ
Elektronik ve Haberleşme Mühendisliği Bölümü
web: http://akademikpersonel.kocaeli.edu.tr/kemalg/
E-posta: [email protected]
Karar Teorisi
Doğru karar vermek…
2
1
01.04.2014
Karar Teorisi – Olabilirlik Oran Testi
• Ele alınan bir x ölçümünü sınıflandırma problemi için
kabul edilebilir bir sezgisel karar kuralı:
– “Ölçülen x özniteliği tarafından sağlanan kanıtın daha
benzer olduğu sınıfı seç”
– Matematiksel olarak, “her sınıfın P(ωi|x) sonsal olasılığını
bul ve içlerinden en büyük olasılığı veren sınıfı seç”
• 2 sınıf problemi için karar kuralı:
• Daha sade şekilde:
3
Karar Teorisi – Olabilirlik Oran Testi
• Bayes Kuralı uygulandığında
• P(x) kararda etkili olmadığından atılabilir!
Λ(x) olabilirlik oranı (likelihood ratio); karar kuralı da
olabilirlik oran testi (likelihood ratio test) olarak
adlandırılır.
• Not: Eğer P(ωi|x) sonsalı hesaplanmak isteniyor ise
P(x) gereklidir.
4
2
01.04.2014
Karar Teorisi – Olabilirlik Oran Testi
• Örnek: Aşağıdaki sınıf koşullu olasılık yoğunlukları üzerinden
LRT ile karar kuralı oluşturmak isteniyor (önseller eşit)
LRT:
İşaretler değiştirilip log alındığında:
Sonuçta:
5
Karar Teorisi – Olabilirlik Oran Testi
• Örnek: Önsel olasılıkların eşit olmadığı durum (P(ω1)= 2P(ω2) )
LRT:
  x 
2e
e



1
 x  4 2 1
2
1
 x 10 2
2
1


2
1
1
1
2
2
In  x   In2   x  4    x  10   0
2
2

1
 x  4    x  10   2In2
2
2


2
2
1
x  7.115
• Eşik sağa kaydı. Yorum?


2
7.115
6
3
01.04.2014
Karar Teorisi – Hata Olasılığı
• İkili hipotez durumunda bölgeler ve kararlar (Van
Trees):
7
Karar Teorisi – Hata Olasılığı
• Karar kuralının performansı hata olasılığı (P[error]) ile
değerlendirilir
• Sınıf koşullu olasılıkları:
• Örn; 2 sınıf probleminde:
8
4
01.04.2014
Karar Teorisi – Hata Olasılığı
• Eşit önsel olasılıklı 2 sınıf problemindeki karar kuralı
için hata olasılığı:
9
Karar Teorisi – Hata Olasılığı
• LRT karar kuralı ne derecede iyi?
• P[error], sonsal hata üzerinden ele alındığında
• En uygun karar kuralı, her x için P[error|x] olasılığını en
küçükleyecektir.
• ωj kararı verildiğinde her x’ noktasında P[error|x’] değeri
P[ωi |x’] olasılığına eşittir
ALT: Arbitrary Likelihood ratio Test
10
5
01.04.2014
Karar Teorisi – Hata Olasılığı
• Herhangi bir x’ değeri için LRT
karar kuralı daima daha düşük
P[error|x’]’e sahip olacaktır
• Dolayısıyla, x-ekseni üzerinden
integral alındığında LRT daha
düşük P[error] vermektedir.
• Verilen bir problem için en küçük hata olasılığı LRT ile
elde edilir.
• Bu hata olasılığı Bayes Hata Oranı (Bayes Error Rate)
olarak bilinir ve sınıflandırıcının yapabileceğinin EN
İYİSİDİR
11
Karar Teorisi – Bayes Riski
• Hatalı sınıflandırma cezası her zaman eşit olmayabilir.
Örn;
– Kanser hastasına “hasta değil” tanısı koymak diğer
durumla karşılaştırıldığında ciddi sorun oluşturacaktır.
• Farklı risk durumları Cij ile gösterilen bir
maliyet fonksiyonu (cost func.) ile gösterilir
– Cij, ωj sınıfı doğru iken ωi sınıfına karar verme
maliyetidir
• Bayes Riski (2-sınıf için):
12
6
01.04.2014
Karar Teorisi – Bayes Riski
• Bayes riskini en küçükleyecek karar kuralı ne olmalı?
• Risk:
• Olabilirlik
13
Karar Teorisi – Bayes Riski
• Risk ifadesinde olabilirlik toplamı kullandığında Bayes
riski:
• Tüm integraller R1 bölgesinde tanımlandığında:
14
7
01.04.2014
Karar Teorisi – Bayes Riski
• Bayes riskini en küçükleme (ilk 2 terim R1’de tanımlı
değil, atılır):
• R1’i seç eğer:
LRT
15
Karar Teorisi – Bayes Riski
• Örnek: 2-sınıf probleminde,
• Yoğunluklar? LR?
•
küçükleyen karar kuralı?
için hata olasılığını en
16
8
01.04.2014
Karar Teorisi – LRT Türevleri
• Bayes Ölçütü:
• En Büyük Sonsal (Maximum A Posteriori - MAP) Ölçütü:
• En Büyük Olabilirlik (Maximum Likelihood - ML) Ölçütü:
17
Karar Teorisi – LRT Türevleri
• Neyman-Pearson Ölçütü: Algılama-kestirim teorisinde
kullanılır ve LRT’de bir sınıfın hata olasılığını sabit tutarak,
diğer sınıfın hata olasılığını en küçüklemeye çalışır.
– Örn; balık sınıflandırma probleminde somonların levrek olarak hatalı
sınıflandırılması için devletin koyduğu %1 sınırını geçmeyecek şekilde
diğer durumun hata olasılığını en küçükle
– Önsellerin bilgisine ve bir maliyet fonksiyonuna gerek yoktur
• Minimax Ölçütü: Oyun teorisinde kullanılır ve Bayes
ölçütünden çıkartılmıştır.
– En büyük Bayes riskini en küçüklemeyi hedefler
– Önsellerin bilgisine gerek yoktur ancak bir maliyet fonksiyonu gerekir
18
9
01.04.2014
Karar Teorisi – Minimum Hata Kuralı
• “Çoklu Sınıf Problemi” için hata olasılığını en küçükleyen
karar kuralı:
• Doğru atama yapma olasılığı:
• Hata olasılığı:
• Hata olasılığını en küçükleme ≡ Doğru atama olasılığını en
büyükleme:
19
Karar Teorisi – Minimum Hata Kuralı
• P[correct] olasılığını en büyüklemek için integralinin her
birinin en büyüklenmesi gerekmektedir
• Bu integral, en büyük P[ωi|x]’i veren ωi sınıfı seçilerek en
büyüklenebilir
20
10
01.04.2014
Karar Teorisi – Minimum Hata Kuralı
• Çoklu sınıf problemi için en küçük Bayes riski:
– αi : ωi sınıfını seçme kararı
– α(x) : x özniteliklerini ωi: α(x)→{α1,α2,…, αc} sınıflarına eşleyen toplam
karar kuralı olsun
• x’i ωi sınıfına atama koşullu riski
:
• α(x) karar kuralı ile ilişkilendirilen Bayes riski:
3
x
21
Karar Teorisi – Ayırtaç Fonksiyonları
• gi(x), i=1,…,C ayırtaç fonksiyonları ile sınıflandırma:
• Temel Karar Kuralları ve ayırtaç fonksiyonları:
22
11
Download

Sunu21.49 MB