Bayesian Decision Theory Jeonghun Yoon
Terms Random variable Bayes rule Classification Decision Theory Bayes classifier Conditional independence Naive Bayes Classifier Laplacian smoothing MLE / Likehood / Prior
Random Variable 주사위를던졌을때 3이나올확률은 ⅙ 이다. 이것을수학적으로표현해보자. 주사위를던졌을때 3이나오는사건을 " 라고하자. 사건을실수에대응시키는함수를 # 라고하자. 여기서 #(") = 3 이다. 만약주사위를던졌을때 6이나오는사건을 ( 라고하면 #(() = 6 이다. 여기서 # 를랜덤변수라고한다. 즉사건을실수에대응시켜주는함수가랜덤변수이다. 따라서주사위를던졌을때 3일나올확률을수학적으로표현해보면 *(+(, = -)) = ⅙ 이다. 이것을간단히표현하면 * + = - = ⅙ 또는 * - = ⅙ 이라고표현할수있다.
Bayes rule 주머니 A B A A A A A A A A B B 질문 : 파란공을뽑았다. 이파란공은 A 에서나왔을까? B 에서나왔을까?
Bayes rule 대답 1) B 에서나왔을것같다. B 에들어있는파랑공이훨씬더많기때문이다. 이것을수학적으로표현하면, 상자 A 에서파란공을뽑을확률! 파랑 " = $ $% 보다상자 B 에서파랑공을 뽑을확률! 파랑 & = $' 가더크다라고할수있다. $( 이조건부확률을우도 (Likelihood) 또는우도함수라고한다. A B
Bayes rule 대답 2) 주머니속을보면상자 A 제비가 8 개상자 B 제비가 2 개이다. 따라서파랑공은 A 에서나왔을것이다. 이것 을수학적으로표현하면, 상자 A를선택할확률! " = $ ( 이상자 B를선택할확률! ' = 할수있다. 이확률은사전확률 (prior probability) 이라고한다. %& %& 보다높다라고 주머니 A A A A A A A A B B
Bayes rule 다음질문들은동치다. l 파란공을뽑았다. 이파란공은 A에서나왔을까? B에서나왔을까? l 파랑공이관찰된조건하에, 파랑공이 A에서나왔을확률이높을까? B에서나왔을확률이높을까? l!(# 파랑 ) >!(' 파랑 ) 인가? 또는!(# 파랑 ) <!(' 파랑 ) 인가? 이조건부확률을사후확률 (Posterior probability) 이라부른다.
Bayes rule Bayes rule 를수학적으로유도해보자.! ", $ =!($, ")! "!($ ") =!($)!(" $)! " $ = *(+,)*, *(+)! $ =,! $ "! "
Bayes rule 주머니 A B A A A A A A A A B B! " #$%& =! #$%& "!(")!(#$%&) = 1 10 ( 8 10 ) 24 100 = 1 3! 2 #$%& =! #$%& 2!(2)!(#$%&) = 12 15 ( 2 10 ) 24 100 = 2 3 ( 사후확률 ) 신뢰도 0.66 으로파랑공은 B 에서나왔다.
Bayes rule likelihood ( 우도값 ) prior ( 사전확률 )! " # =! # "!(")! # "!(") posteriori ( 사후확률 ) l 사후확률 : 관찰값들이관찰된후에모수 (parameter) 의발생확률을구한다. l 사전확률 : 관찰값들이관찰되기전에모수의발생확률을구한다. l 우도값 : 모수의값이주어졌을때관찰값들을관찰할수있는함수값
Spam 메일분류 Mailbox 에서 spam 설정을한적이없다. ( 물론수동으로조건을입력하면더잘작동한다.) 그런데어떻게아래와같은알고리즘이작동하는걸까? 새로운 mail 이도착 Yes Spam 인가? No spam 분류시스템 받은 mail 함으로이동 Spam mail 함으로이동 How?
Classification Feature vector 특성벡터 Classifier 분류기 Class 부류 E-mail (Words) Web Site (Words) 꽃 ( 꽃의생김새 ) Spam or Not Sports or Science or News Line-flower or Mass-flower For example, (visit, money, buy, girl, Viagra) Spam
Decision Theory 이미지분류 ( 처리 ) 에서 decision thoery 를적용했을때 processing 과정 images Image processing measurement! Decision rule " # Cancer " $ normal 가정 : - 이미지를 measurements(!) 로만들고, 그것을이용하여암인지아닌지를분류하는것 - Measuremetns 와그것이속하는부류 (class) 의결합확률분포를이용 %!, " ' = %! " ' %(" ' ) 목표 : Make the "Best" how to define? decision.
Classification using decision theory Decision rule 은결정경계 decision boundaries 를이용하여입력공간 input space 을결정구역 decision regions 으로나눈다. - 입력공간 : measurement 가존재하는공간 ( 그림에서는 1 사분면전체 ) 결정경계 (decision boundaries)! " - 결정구역 : 결정경계를기준으로나눠진 공간. 결정구역에속한 measurement 는 해당구역으로할당 (classify) 된다.! #! $ - 결정경계 : 각 class 를구분짓는경계
Classification using decision theory 예제 ) 2 차원 vector measurement 의 2 부류 class 결정경계! "! #
Decision boundary 결국우리가해결해야하는것은결정경계를찾는것이다. Decision theory 의가정에서언급했던것처럼 measurement(feature) 와 class 의결합확률밀도!(#, %) 를이용할것이다. 그러면결합확률밀도함수를이용하여 decision boundary 를어떻게찾을까? 강의처음에언급했던 Bayes rule 을이용할것이다.
Bayes classifier Bayes rule 을이용하여결정경계를찾고그것을기준으로 measurement(feature) 를각 class 로분류하는분 류기를 Bayes classifier 라고한다. Bayes classifier 의 2 가지기준 l 오분류비율의최소화 l 기대손실의최소화
Decision Boundary for average error 2 class decision (! 는 1 차원 ) "($, & ' ) : $ 와 & ) 의결합확률. $ 가 & ) 와함께존재하는확률또는 $ 가 & ) 에실제로존재하는확률로해석하면된다. 결정경계가정해지고난이후에, * ' 에속하면 & ' 으로분류 * + 에속하면 & + 으로분류 그림출처 : PRML 책
Decision Boundary for average error 2 class decision (! 는 1 차원 ) 2 3 는 misclassifications( 오분류 ) 이최소가되는지점. 이영역에서주황색영역이사라지고녹색만남는다. ', - "!,. / +! ', 0 "!,. 1 +! 4! 을기준으로분류할경우, 오분류영역을살펴보자. -. 1 에속하는데 5 / 으로분류하는경우 ( 보라색영역 ) -. / 에속하는데 5 1 으로분류하는경우 ( 연두색 + 주황색영역 ) " #$$%$ = ' ) () " #$$%$,! +! = ' "!,. / +! ' "!,. 1 +!, -, 0
Bayes Decision Rule (error) 결합확률분포! ", $ % 가큰 $ % 에 " 를할당 l! ", $ & l! ", $ & >!(", $ ) ) 이면, " 를 $ & 에할당 <!(", $ ) ) 이면, " 를 $ ) 에할당! ", $ % =! $ % "!(") 조건부확률 ( 아직 bayes rule 은나오지않았다.) 사후확률분포!($ % ") 가큰 $ % 에 " 를할당 l! $ & " >!($ ) ") 이면, " 를 $ & 에할당 l! $ & " <!($ ) ") 이면, " 를 $ ) 에할당
Bayes error Bayes error 는오분류확률을나타낸다.! "##$# = '( (! "##$#, * +* =,-! *,. / +*,0! *,. 1 +* =,-!. / *!(*)+*,0!. 1 *!(*)+* 5, -! *,. / +* 5, 0! *,. 1 +*
Reject option 확실하지않은영역에대해서는분류하지않는다. *(# ( %) *(# ) %)! " # $ % <! ' ( ' )
Bayes classifier ( 오분류비율의최소화 ver.) 사후확률분포!(# $ &) 가큰 # $ 에 & 를할당 l! # ( & >!(# * &) 이면, & 를 # ( 에할당 l! # ( & <!(# * &) 이면, & 를 # * 에할당, (&) = arg max 4 = arg max 4 5(6 = 7 8 = &) 5 8 = & 6 = 7 5(6 = 7) - Class conditional density - Likelihood Gaussian class conditional densities (1-dim) 5 8 = & 6 = 7 = 1 exp( (& A = * ) * ) * :< :;< = =
Loss matrix 비용함수 (cost function), 손실함수 (loss function) 을도입 Loss matrix : 오분류에따른손실을행렬로표현한것 암 (actual value) 정상 (actual value) 암 (prediction value) 0 1 정상 (prediction value) 1000 0
Bayes classifier ( 기대손실의최소화 ver.) Bayes risk! " # $ : True status 는 %, 선택된 action 은 & 일때발생하는 loss * #)! " # $ = ( * " # + ),(+ ) $) ) action measurement Loss matrix 0 1 is rejected. 0 1 is not rejected. 암 (actual value) 정상 (actual value) Prediction : 0 2 Prediction : 0 1 암 (prediction value) 0 1 (type 1 error) 정상 (prediction value) 1000 (type 2 error) 0
Bayes classifier ( 기대손실의최소화 ver.) Input :!, output : "($ %, $ ' ) 인경우 (2 class) l $ % 으로분류했을때의 risk l ) * %! =, %% - $ %! +, %' - $ '! =, %% - / =! 0 = $ % -(0 = $ % ) +, %' - / =! 0 = $ ' 1(0 = $ ' ) l $ ' 로분류했을때의 risk l ) * '! =, '% - $ %! +, '' - $ '! =, '% - / =! 0 = $ % -(0 = $ % ) +, '' - / =! 0 = $ ' 1(0 = $ ' ) l Decision rule l ) * %! > ) * '! 이면 $ ' 로분류 l ) * %! < ) * '! 이면 $ % 으로분류 Bayes decision rule : Bayes risk 를최소화하는 action 을선택 4* 5 = arg min < = )(* 5!)
Naïve Bayes Classifer Goal l!"# $"%& '" (#) %*+,-+ 라는문장이주어졌을때, 이문장이 Spam 문장인지, Ham 문장인지분류하자. How l 사후확률 (Posterior probability) 사용 l Bayes 정리이용 But. /0+1!"# $"%& '" (#) %*+,-+ = 사후확률 (Posterior probability) 우도 (likelihood) l Likelihood( 우도 ) 를직접계산하는방법은쉽지않다..!"# $"%& '" (#) %*+,-+ /0+1.(/0+1).(!"# $"%& '" (#) %*+,-+) 사전확률 (Prior probability) 주변우도 (marginal probability)
Conditional independence X is conditionally independent of Y given Z : Probability distribution governing X is independent of the value of Y, given the value of Z! " = $ % = &, ( = ) =! " = $ ( = )! ", % ( =! " (!(% ()
Naïve Bayes Conditional independence 가정에의하여,! "#$ %#&' (# )$* &+,-., /0,1 =! "#$ /0,1! %#&' /0,1! (# /0,1! )$* /0,1! &+,-., /0,1 이성립한다. 특정한조건이주어지면문장에서각각의단어가나올확률은서로독립이라는것이다. 문장구조안에서각단어는의존성을띄는데, 이것을무시하는것이다. 그러면이가정을왜사용하려고하는가? Bayesian probability 를계산하는데필요한 parameters 수를줄이기위해서이다.
Parameters in Naïve Bayes 번개가치는것을예측해보자 (L). 아래의두조건은 conditionally independent 하다. l 천둥 (T) l 비 (R) Conditionally independent 조건이없을때 l L 이주어졌을때의 likelihood!(#, % ') 를계산하기위한 parameter 의개수 : 2 * 1 2 = 6 Conditionally independent 조건이있을때 l!(#, % ') =!(# ')!(% ') 를계산하기위한 parameter 의개수 : 2 1 2 + 2 1 2 = 4
Parameters in Naïve Bayes 필요한 parameter 수를계산하자.! = ($ %, $ ',, $ ) ) 라고하자. 전체 word 의크기를 +, class 의수를, 라고 하자. -!. -. = - $ %, $ ',, $ ). -(.) 의 parameters 수 : / 0 2 3 + 3 2 = / 0 3 2 -!. -. = - $ %, $ ',, $ ). -. = - $ %. - $ '. - $ ). -(.) 의 parameters 수 : 03 + 3 2
Naive Bayes Classifier 분류조건! "#$% &'( )'*+,' -(. */$01$ =! &'( )'*+,' -(. */$01$ "#$%!("#$%)!(&'( )'*+,' -(. */$01$)! "#$% &'( )'*+,' -(. */$01$ =! &'( "#$%! )'*+ "#$%!,' "#$%! -(. "#$%! */$01$ "#$%!("#$%)!(&'( )'*+,' -(. */$01$)
Naive Bayes Classifier 분류조건 Decision rule l! ",! $,,! & : ' 개의 word 즉 corpus 의크기를의미하고, ( 는 target class 를의미한다. l 각클래스에서 ' 개의단어가동시에발생하는확률을구하고, 발생확률이가장높은클래스를선택한다. ) *+, = arg max 3 4! ",,! & ( 4 ( = arg max 3 5 67" l 만약 2 개의클래스 (Spam/Ham) 가존재한다고가정하자. & l 67" & l 67" & 4! 6 ;<=> 4(;<=>) > 67" 4! 6 h=> 4(h=>) 이면 Spam으로분류한다. & 4! 6 ;<=> 4(;<=>) < 67" 4! 6 h=> 4(h=>) 이면 Ham으로분류한다. & 4! 6 ( 4(()
Naive Bayes Classifier 예제 복권 / 백만 / 수신취소 3개의단어를이용하여 Ham / Spam을분류하자. 예를들어, 복권이수신취소되었습니다. 라는단어는 bag of words vector로 (1, 0, 1) 로표현된다. 총 100개의메일이있다고할때, 각단어에대한 likelihood를표로만들면다음과같다. 복권이라는단어는총 22개의 spam 메일중 3개의메일에서존재했고, 19개의메일에서는존재하지않았다. 수신취소라는단어는총 78개의일반메일중 21개의메일에서존재, 57개의메일에서는존재하지않았다. 복권 백만 수신취소 Likelihood 있음 없음 있음 없음 있음 없음 전체 Spam 3/22 19/22 11/22 11/22 13/22 9/22 22 Ham 2/78 76/78 15/78 63/78 21/78 57/78 78 전체 5/100 95/100 26/100 74/100 34/100 66/100 100
Naive Bayes Classifier 예제 복권이수신취소되었습니다. 라는문장에대해서 Spam 여부를판단하고자한다.! "#$% 복권 ~ 백만 수신취소 = ) 복권 ~ 백만 수신취소 +,-. )(+,-.) )( 복권 ~ 백만 수신취소 ) = ) 복권 +,-. ) ~ 백만 +,-. ) 수신취소 +,-. )(+,-.) )( 복권 ~ 백만 수신취소 ) 3 44 55 44 53 44 44 566 = 0.008864 복권 백만 수신취소 Likelihood 있음 없음 있음 없음 있음 없음 전체 Spam 3/22 19/22 11/22 11/22 13/22 9/22 22 Ham 2/78 76/78 15/78 63/78 21/78 57/78 78 전체 5/100 95/100 26/100 74/100 34/100 66/100 100
Naive Bayes Classifier 예제 복권이수신취소되었습니다. 라는문장에대해서 Ham 여부를판단하고자한다.! "#$ 복권 ~ 백만 수신취소 = ( 복권 ~ 백만 수신취소 *+, ((*+,) = (( 복권 ~ 백만 수신취소 ) ( 복권 *+, ( ~ 백만 *+, ( 수신취소 *+, ((*+,) (( 복권 ~ 백만 수신취소 ) 1 23 45 23 16 23 23 677 = 0.004349 0.008864 보다는작다. 따라서 Spam 확률이더높다. 복권 백만 수신취소 Likelihood 있음 없음 있음 없음 있음 없음 전체 Spam 3/22 19/22 11/22 11/22 13/22 9/22 22 Ham 2/78 76/78 15/78 63/78 21/78 57/78 78 전체 5/100 95/100 26/100 74/100 34/100 66/100 100
Weakness of Naïve Bayes 약점 1 Naïve Bayes Assumption( 가정 ) l Naïve Bayes는, data에서 conditional independency 가정이지켜지지않더라도, 좋은성능을보인다. l 사실, 특성들 (features) 은아래와같이 conditional independency를가지고있지않음 :!(# $,, # ' Y),!(# -.) l 그럼에도불구하고, Naive Bayes 는가장많이사용되어지는 classifier 중하나임. -
Weakness of Naïve Bayes 약점 2 불충분한양의 training data 만약,! = # 일때, $ % = & 인 training sample 를본적이없다고가정하자. 예를들어, y= {b=spam}, $ % = {a='earn'} 이라고하고, Spam 클래스에서는 Earn 이라는 feature 가존재하지않다고 하자. ( = $ % = &! = # = 0 따라서, 나머지 $ *,, $ - 의값에는상관없이항상 ( = $ % = &, $ *,, $ -! = # = 0 ( $ % = &, $ *,, $ /! = # = (($ % = &! = #) - 45* (($ 4! = #) 이럴때는어떻게해야하는가? Laplacian Smoothing
Laplacian Smoothing Multinomial random variable! 라고하자.! 는 1 부터 " 까지의값을가질수있다. # 개의독립인 sample! $,,! ' 이주어졌고, 우리는이것을통해서 multinomial distrbution 을구하고싶다. 즉, ((! = 1), ((! = 2),, ((! = ") 를구하고싶다. 추정값 ( 많은경우 MLE 를사용한다.) 은, (! =. = 01$ ' 2{! 0 =.} # 이다. 여기서 2. 는지시함수이다. 관찰값내에서의빈도수를사용하여추정한다. 예를들어 {1, 2, 2, 1, 5, 2, 2, 2, 2, 1} 이면, (! = 1 = 0.3, (! = 2 = 0.6, (! = 5 = 0.1 이다.
Laplacian Smoothing 한가지주의할것은, 우리가추정하려는값은모집단 (population) 에서의모수!(# = %) 라는것이다. 추정하기위하여 sample 을사용하는것뿐이다. 예를들어, # (') 3 for all % = 1,, - 이라면,! # = 3 = 0 이되는것이다. 10 개의샘플에서 3 을보지못했다고해서,! # = 3 = 0 라고결론내리는것이옳을까? 이것은, 통계적으로볼때, 좋지않은생각이다. 단지, 표본집단에서보이지 않는다는이유로우리가추정하고자하는모집단의모수값을 0 으로한다는것은 통계적으로좋지않은생각이다. (MLE 의약점 )
Laplacian Smoothing 이것을극복하기위해서는, 1 분자가 0 이되어서는안된다. 2 추정값의합이 1 이되어야한다. " # $ = & =1 ( 확률의합은 1 이되어야함 ) 따라서, 이라고하자. # $ = & = ()* +, $ ( = & + 1 / + 0
Laplacian Smoothing 1 의성립 : sample 내에! 의값이없어도, 해당추정값은 0 이되지않는다. 2의성립 : " ($) =! 인 data의수를 ' ( 라고하자. ) " = 1 = +,-. /-0,, ) " = 3 = + 4-. /-0 이다. 각추정값을다더하게되면 1 이나온다. 이것이바로 Laplacian smoothing 이다. " 가될수있는값이 1 부터 3 까지균등하게나올수있다는가정이추가되었다고 직관적으로알수있다.
Laplacian smooting in Naïve Bayes Classifier ) Training data : (" #, % # ) #'(, " # = + ( (#), +, (#),, +. (#) / + = 0 % = 1 = (2h4 567148 9: ; 0 " > 05? % > = 1) + 1 (2h4 567148 9: ; % > = 1) + B B : + # 의값이될수있는 words 의수 / % = 1 = (2h4 567148 9: ; % > = 1) + 1 (2h4 2920C 567148 9: 280D5D5E?020) + F F: H 의값이될수있는 class 의수
Laplacian example 복권이발신취소되었습니다. 라는문장에대해서 Spam 여부를판단하고자한다. 발신취소는데이터셋에아예없는단 어이거나 spam dataset 에없던단어이다.! "#$% 복권 ~ 백만 발신취소 = ) 복권 ~ 백만 발신취소 +,-. )(+,-.) )( 복권 ~ 백만 수신취소 ) = ) 복권 +,-. ) ~ 백만 +,-. ) 발신취소 +,-. )(+,-.) )( 복권 ~ 백만 발신취소 ) 3 44 55 44 6 44 44 566 4 25 12 25 1 25 23 102