i=1

MEH535 Örüntü Tanıma
2. Karar Teorisi
Detection
Theory
Agdamn
Decision
Tons I
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]
Theory
Karar Teorisi
Doğru karar vermek…
2
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ı:
)
wzlx
>P(
)
PCWIIX
Ejer
wesmifini
eihsihaldewz
PCW
Ses
,
,
wzlx )
,1×)¥P(
Wz
3
Karar Teorisi – Olabilirlik Oran Testi
• Bayes Kuralı uygulandığında;
PKhgy.is#wwzMxlwdPe
/
pay
±*D¥iI
:#
ola
bililik
( likelihood
o
ran
ratio )
4
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)
Excited
"Ypwu=Ett¥¥w
olabibilikfnk
"
Wick
Pklud
.
(likelihood fund
a*iH¥¥*
=v÷*#÷
rn.EE#...nZjt=lnAw=lnhFln.ioBgb
vX8u+t6
Tntwu rooty
-
-
^2u£j84 u3gi7
5
Karar Teorisi – Olabilirlik Oran Testi
• Örnek: Önsel olasılıkların eşit olmadığı durum (P(ω1)= 2P(ω2) )
)
plxlwn
pcxlwz )
,=r÷e# 4
'
⇐
tech
-4
'
=2¥giIe
-
aE¥*
lnAw=h2
(
kh
-
Each
¥÷{¥n
w
)t÷(kto5£i
)t(kyo)¥t2lm2
:27 .nl5
°
2
WL
6
.
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ı:
plerroDzIjPkrrorlwilP@DtoplE-olaslysTplerror.WilPError1wiTPCchoosevjlwiHfpCxlwildx.R
;
• Örn; 2 sınıf probleminde:
p[
error
]=PCwD,{
Plxlwidxtplwd
xx
,{
pklwddx
8
Karar Teorisi – Hata Olasılığı
• Eşit önsel olasılıklı 2 sınıf problemindeki karar kuralı
için hata olasılığı:
I
(
P fer rod
=
w
i
)
not
[=P P@D 9
it
[#:
4
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
Plwilxl
=
Pku
*
Pal will
ALT: Arbitrary Likelihood ratio Test
10
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
1
maliyetidir
Cz
sinif Item 2 sin fen
,
atanma
• Bayes Riski (2-sınıf için):
R=£H÷{§÷i ;
(
.
,
KY
Pcwijiseauxew ;)
÷
nahyeh
'
'
=Eki¥
PCWJ )
12
Karar Teorisi – Bayes Riski
• Bayes riskini en küçükleyecek karar kuralı ne olmalı?
-
-
• Risk:
k¥4
,
,{
+
-
Ku
Plwi
PKIW
)
P ( we
)
PKI
.
we
) +42 P ( w
)
+
G
,
~
)
P ( xlw
Plwz ) P ( ×
I
W
,
,
Dd
×
) ] DX
olabilirlik
i
xlw . ) dxt
{ Plxluaddx
pfnjpklw
=
,
I dx
=
1
,
13
Karar Teorisi – Bayes Riski
• Risk ifadesinde olabilirlik toplamı kullandığında Bayes
riski:
cuptitcnphd
}
R=c ,Plw
R=G#
,
.la?Pk1w.ldxtGzPluD,fPCxlwddx+CnPlwp/PCx1wnldxtCzzPlwyfp/ywddxtCz.Plw.l/Plx1wi1dxtGzPlwy/Pk1w.
-
Cupcw
,
)
,{
pklw
,
)dx
-
GzPCwy{ pklwddx
Bbalsinhdetanmlamayapltfntas
pup
.ir#+kn-cu)PlwyfPNuldx-Ki9;YPlx1w.1dx
14
:
Karar Teorisi – Bayes Riski
• Bayes riskini en küçükleme (ilk 2 terim R1’de tanımlı
değil, atılır):
tax
÷
• R1’i seç eğer:
Cu
-
Cu ) P lwn )
P
KI
w
D
Tg ku GDP W
-
¥e¥n¥a÷m¥
,
P
(x
I w
15
2)
Karar Teorisi – Bayes Riski
• Örnek: 2-sınıf probleminde,
×
×
• Yoğunluklar? LR?
•
küçükleyen karar kuralı?
a
ath'd
için hata olasılığını en
r÷ e÷÷
Eternity
'*
hgAH=
k¥+÷hi&lo
-
"
"
-
4n+4
-
;D ¥0
tnntnzno
Eet
!XE"9ts×
nt6ne6=G
nniIY?I_=
16
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
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ığı:
)=§jPwi,{
Planet
Pl
error
)
=
enhiauhlue
Morath
1-
-
Mxlwildx
Planet )
Ubiifihlene
,§ ,{ ilxlwilpwildx
.
;
.in#wilxlPlxHx
enbjskhih
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
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