기타2007.10.19 15:44

조건부 확률(베이지안)의 이해를 위한 예제 및 풀이

v1.0 2007/10/11 Copyleft by 전경헌@사이냅소프트
v1.1 2007/10/16 Copyleft by 전경헌@사이냅소프트 , 몬티홀 문제에 대한 커멘트 추가
v1.2 2011/03/17 Copyleft by 전경헌@사이냅소프트 , 몬티홀 문제를 별도 블로그로 기록함

베이스의 정리(Bayes' theorem)
는 공부할 때마다 새로운 느낌이 든다.
매번 아하 그렇지 라는 생각이 들다가도 좀 지나면 다시 기억이 안난다.
내가 기억하는 것만으로도 베이스의 정리는 최소 3번이상 공부한 것 같다.

정리자체는 매우 단순한데... 적용할 때마다 확신이 잘 안서는 것 같아서
이번에는 베이스의 정리를 잘 드러내주는 예제들을 10개쯤 모아 보기로 하였다.
(머리나쁜 사람이 공부하기에는 예제가 최고!!! ^^)

먼저 베이스의 정리를 다시 살펴보자.(위키피디아 참조)
 
P(A|B) = P(B|A)P(A)/P(B)

여기에서
P(A|B) - 사건B가 발생한 상태에서 사건A가 발생할 조건부 확률
P(B|A) - 사건A가 발생한 상태에서 사건B가 발생할 조건부 확률
P(A) - 사건A가 발생할 확률, B에 대한 어떠한 정보도 없는 상태에서 A가 발생할 확률
P(B) - 사건B가 발생할 확률, A에 대한 어떠한 정보도 없는 상태에서 B가 발생할 확률

간단하게 공식이 어떻게 유도되는 지 보자.

사용자 삽입 이미지

P(B|A) = P(A^B)/P(A) 이므로
P(A^B) = P(B|A)P(A)라고 쓸 수 있다.

따라서
P(A|B) = P(A^B)/P(B) = P(B|A)P(A)/P(B)

벤다이어그램을 통하여 정리자체를 이해하는 건 참 쉬워보인다.
그럼 이제 예제를 공부하여 확실하게 알아두자.


예제1) 하얀별사탕, 분홍별사탕

건빵 2봉지를 샀다. 그래서 별사탕도 2봉지다. 첫번째 봉지에는 하얀별사탕이 10개, 분홍별사탕이 30개 들었고, 두번째 봉지에는 각각 20개씩 들었다. 두봉지의 별사탕을 하나의 접시에 담고, 눈을 감은채 별사탕하나를 집어들었다. 눈을 뜨고 집어든 별사탕을 지그시 살펴보니 분홍별사탕이다. 이 별사탕이 첫번째 봉지에서 나왔을 확률은?

별사탕이 40개씩 들었다는게 알려지면 엄청 잘팔리겠군.
음... 첫번째봉지에 분홍별사탕이 더 많이 있었으니,
아무리못해도 50%이상의 확률이 나와야 한다.

풀어보자. 일단 문제를 확률적으로 표현해보면 아래와 같다.
P(첫번째봉지|분홍별사탕) = P(분홍별사탕|첫번째봉지)P(첫번째봉지)/P(분홍별사탕)

P(분홍별사탕|첫번째봉지) = 30/40
P(첫번째봉지) = 40/80
P(분홍별사탕) = 50/80

각각의 확률을 적용하면,
P(첫번째봉지|분홍별사탕) = (30/40) * (40/80) / (50/80)
 = (30 * 40 * 80) / (40 * 80 * 50) = 30/50 = 60/100 = 60%

따라서, 답은 60%이다.



예제2) 불량 노트북 공장

두개의 노트북 조립라인을 가진 공장에서 생산된 1000대씩의 노트북들을 같은 화물 창고에 쌓아 놓았다. 각각의 조립라인을 정밀하게 조사하여, 1번 조립라인에서 생산된 노트북의 10%가 불량이고, 2번 조립라인에서 생산된 노트북의 15%가 불량임을 알았다. 화물 창고의 노트북을 하나꺼내 조사한 결과 불량이었을 때, 이 노트북이 1번 조립라인에서 생산되었을 확률은?

P(1|불량) = P(불량|1)P(1)/P(불량)

 =             P(불량|1)P(1)              
     P(불량|1)P(1) + P(불량|2)P(2)

P(1) = P(2) 이므로 분자와 분모에서 P(1),P(2)를 제거하고
값을 대입하면

P(1|불량) = 0.1 / (0.1 + 0.15) =  0.4

답은 40%



예제3) 99% 폐암진단시약

우리나라 충청,전북 등 자연적으로 우랴늄 함량이 높은 지역 일부에서 평생 1백명 가운데 1명이 폐암에 걸려 사망할 위험이 있는 등 라돈 농도가 위험수위인 것으로 밝혀졌다. 해당지역 주민한명이 폐암을 99% 진단하는 시약으로 진단한 결과 폐암 양성반응을 확인했을 경우, 이 주민이 실제로 폐암에 걸렸을 확률은?

가정이 많이 필요한 문제로군.
먼저, 흡연자 비흡연자 성별, 직업 등 다른 모든 조건은 별개로 하고
해당지역주민이 폐암에 걸릴 확률은 1%라고 하자.

(음... 폐암에 걸려 사망한 사람을 전체주민에서 빼게되면,
문제가 복잡해진다. 폐암에 걸려도 사망하지 않는다고 하고)
문제를 좀 더 간단히 해서 전체주민의 1%가 폐암환자라고 하자.

99% 진단이라는 건 무슨 뜻일까?
알려진 폐암환자 100명을 대상으로 했을 때 99명을 양성으로 판정하고,
알려진 정상인 100명을 대상으로 했을 때 1명을 양성으로 판정한다고 보면 되겠군.

풀어보자. 문제를 확률적으로 표현해보면 아래와 같다.

P(폐암|양성) = P(양성|폐암)P(폐암)/P(양성)

P(양성|폐암) = 99/100
P(폐암) = 1/100
P(양성) = ??? 여기서 한번 생각을 해야하는군...

모든 주민을 대상으로 진단했을 때 양성반응이 나올 확률은?
(주민은 99%의 정상인과 1%의 폐암환자로 구성됨을 기억하자)
P(양성) = P(양성|정상)P(정상) + P(양성|폐암)P(폐암)
= (1/100)*(99/100) + (99/100)*(1/100) = 198/10000
따라서 대략2%정도가 된다

여기서 잠깐! 베이스의 정리의 형태를 조금 수정해보자.
베이스의 정리에서 P(B) = P(B|A)P(A) + P(B|~A)P(~A) 로 쓸 수 있으므로

P(A|B) = P(B|A)P(A)/P(B)

 =           P(B|A)P(A)            
   P(B|A)P(A) + P(B|~A)P(~A)


공식의 새로운 형태는 P(B)의 계산을 아예 공식에 적용한 것이다.

이제, 각각의 확률을 적용하면,
P(폐암|양성) = (99/100) * (1/100) / (198/10000) = 1/2 = 50%

따라서, 답은 50%이다. 양성반응이 나와도 조금만 겁먹자.
확률은 반반이니까...



예제4) 두명의 자식

전경헌씨에게는 두명의 자식이 있다. 한명이 아들이라는 것만 알고 있을 때, 다른 한명이 아들일 확률은?

음... 실제 전경헌씨한테 사랑스런 아들이 둘 있다는 것을
알고 있는 상태에서 문제를 풀어야 하는 게 좀 그렇군.

내가 모르는 동명이인이라고 하고, 문제를 풀어보자.

복잡한 확률 계산이전에 상식수준에서 문제를 보면
전씨가 두명의 자식을 낳았을 경우 동일한 확률의 4가지 경우가 있다
첫째가 아들,둘째도 아들
첫째가 아들,둘째는 딸
첫째가 딸,둘째는 아들
첫째가 딸,둘째도 딸
이제 한명이 아들이라는 정보를 알고 있으므로 4번째 경우는 제거된다.
(아들,아들), (아들,딸), (딸,아들)의 3가지 경우에서 한명이 아들일 경우
나머지 한명이 아들인 경우는 (아들,아들) 1경우 이므로 답은 1/3 = 33.33..%

베이스정리를 이용하여 문제를 풀어보자.
P(둘다아들|한명이아들) = P(한명이아들|둘다아들)P(둘다아들)/P(한명이아들)

P(한명이아들|둘다아들) = 1
P(둘다아들) = 1/4
P(한명이아들) = 3/4
이 값을 원식에 대입하면

P(둘다아들|한명이아들) = 1 * (1/4) * (4/3) = 1/3
그러므로 답은 1/3 = 33.33..% 이다.

이 문제를 확률이 반반인 다양한 경우로 변형할 수 있다.

동전2개를 던져서 한면이 앞면임을 알았을 때
다른 한면이 앞면일 확률은?

주사위 두개를 던져서 하나가 홀수임을 알았을 때
다른 하나도 홀수일 확률은?



예제5) 전자회로 스위치

아래 그림처럼 전류가 a에서 b로 흐르도록 회로를 구성하였다.
 

사용자 삽입 이미지

즉, 2개의 스위치 1,2중 하나만 on 되면 전류가 흐르는 병렬회로이다. 스위치가 불량일 확률이 10%라고 하자. 만약 두개의 스위치를 모두 켰을 때 전류가 흘렀다면, 1번 스위치가 정상일 확률은?

스위치가 정상이라면 켰을 때 전류가 흐르는 것이고, 불량이라고하면 켰을 때도 전류가 흐르지 않는다고 봐야겠군.
 
스위치 1이 정상일 확률을 P(1)이라하면 문제에서 P(1) = 0.9 이고,
병렬회로이므로 전류가 흐를 확률 P(전류) 는 1 - (0.1)(0.1) =  0.99 이다.

베이스정리에 의하여,

P(1|전류) = P(전류|1)P(1)/P(전류) 이므로
= 1 * 0.9 / 0.99 = 0.909... = 90.91 %

병렬회로에서 전류가 흘렀음을 알고 있다고 해도 정상일 확률은 단1%도 안 올라간다.
답은 대략 90.91%이다.

사용자 삽입 이미지

위 그림처럼 스위치를 하나 더 붙여서 회로를 구성하였고, 스위치를 모두 on 시켰을 때 a에서 b로 전류가 흘렀음을 확인하였다면 이 경우 스위치 1이 정상일 확률은?


예제6) 범죄현장의 DNA

살인사건의 용의자 3명이 잡혔다. 이중에 한명의 소행임이 분명하나, 세명다 범행을 완강히 부인하고 있어 진범을 못찾고 있는 가운데 국과수에서 연락이 왔다. 범죄현장에서 살인자의 것으로 추정되는 DNA가 발견됐고 용의자중 1명의 DNA와 일치한다고 하며, 이런 일치는 100만명중 1명꼴이라고 한다. 해당 용의자가 진범일 확률은?

잡혔는데도 자백안하다니 일도이부삼백사전을 아는 놈 아닌가? 나쁜 놈.
어째튼 문제를 풀자.

P(진범|일치) = P(일치|진범)P(진범)/P(일치)

P(일치|진범) = (10**6 - 1)/10**6
P(진범) = 1/3, (용의자 3명중 한명이므로)
P(일치) = ??? 그러고보니 항상 이게 쉽지 않군...

P(일치) = P(일치^진범) + P(일치^무죄)
= P(일치|진범)P(진범) + P(일치|무죄)P(무죄)
= ((10**6 - 1)/10**6)*(1/3) + (1/10**6)*(2/3)
= (10**6 + 1) / 3 * 10**6

좀 복잡해 보이긴 한데... 대입해보자
P(진범|일치) = (10**6-1)/10**6 * 1/3 * 3*10**6 /(10**6 + 1)
= (10**6 - 1)/(10**6 + 1) = 0.999998...

그렇군, 99.9998%이상의 확률로 범인이군.
빽이나 돈써서 빠져나가지 못하기를...

문제를 푸는 김에 조금 더 해보자. 이 사건이 서울에서 발생했고,
서울시민이 딱 1000만이며 서울시민만이 이 사건에 관계된다고 하자.
용의자가 한명도 없는 상태에서 지하철로 집에가는 당신을 붙잡아
DNA검사를 했는 데 우연히도 일치 했다면 당신이 범인일 확률은?

얼라리요? 애거사크리스티의 추리소설 분위기네...
내가 범인으로 몰리는 불상사가 생길 수도 있군...

P(당신|일치) = P(일치|당신)P(당신)/P(일치)

P(일치|당신) = (백만 - 1)/백만, 이것은 변함없고
P(당신) = 1/천만, (천만 서울시민중 한명이므로)
P(일치) = P(일치^진범) + P(일치^무죄)
= P(일치|진범)P(진범) + P(일치|무죄)P(무죄)
= ((백만 - 1)/백만)*(1/천만) + (1/백만)*((천만-1)/천만)
= (천만 + 백만 - 2) / (백만*천만)

대입해서 계산해보자.
P(진범|일치) = (백만 - 1)/(천만 + 백만 - 2) = 999999/10999998 = 0.0909...

그렇다면, 대략 9.1%의 확률로 당신이 범인일 수 있겠군요.

대충 생각해도 백만분의 1의 일치도에 천만명이라면
10명은 일치한다는 뜻이니, 그 10명중 1명이라면 범인인 확률은 10% 정도겠군


예제7) 몬티 홀(Monty Hall)

빨강,노랑,파랑 3개의 문이 있다. 이중 하나에만 상품이 있다. 당신은 단 하나의 문만 열 수 있고, 열어서 상품이 있다면 당신 것이다. 당신이 빨강문을 가르켰다. 어느 문에 상품이 들어있는 지 알고 있는 사회자가 노랑문을 열어보이며 상품이 없음을 보여준다. 당신은 선택을 바꿔 파랑문을 선택할 것인가? 아니면 그대로 빨강문을 고수할 것인가? 확률적으로 어느쪽이 유리할까?

좋은 풀이는 [위키피디아의 몬티 홀 문제]를 참조한다.



예제8) 스팸 필터

겨울연가를 성공적으로 마친 배용준씨는 인기만큼 스팸메일도 많이 받는 편이다. 지금까지 배용준씨가 받은 이메일의 80%는 스팸메일이었다. 메일의 단어들을 조사해보니 95%의 스팸메일에서 '대출'을 볼 수 있고, 정상메일의 2%에서도 '대출'을 볼 수 있었다. 방금전 받은 메일에 '대출'이라는 단어가 들어있을 경우 이 메일이 스팸일 확률은?

앞서 예제들을 다 풀어봤다면 매우 단순한 문제다.
먼저 수식화를 하자.

P(스팸|대출) = P(대출|스팸)P(스팸)/P(대출)

이제 각각의 값을 구하고

P(대출|스팸) = 0.95
P(스팸) = 0.80
P(대출) = P(대출|스팸)P(스팸) + P(대출|정상)P(정상)
=0.95 * 0.80 + 0.02 * 0.20  =  0.764

원식에 대입하면,

P(스팸|대출) = 0.95 * 0.80 / 0.764 = 99.5%

답은 99.5% 이다.

'대출'이 들어간 모든 메일을 스팸이라고 처리한다면,
정상메일의 2%는 스팸으로 분류되겠군요.(false positive)

파이썬으로된 오픈소스 베이지안 스팸필터 소스는 아래에서 받으실 수 있습니다.
Bayesian anti-spam classifier written in Python.


예제9) 스팸 필터 #2

2008년7월 은퇴할 모든 준비를 마친 빌게이츠(Bill Gates)씨는 남는 건 시간뿐이라서 자신이 지난 한달간 전세계로 부터 받은 10만통의 메일을 하나씩 조사해보았다. 조사 결과는 아래와 같다.

. 전체 메일의 70%가 스팸메일이다.
. 스팸메일의 90%는 단어 'click'을 포함하고 있다.
. 스팸메일의 80%는 단어 'teens'를 포함하고 있다.
. 정상메일의 20%는 단어 'click'을 포함하고 있다.
. 정상메일의 5%는 단어 'teens'를 포함하고 있다.

만약 새로운 메일이 click과 teens만을 포함하고 있다고 할때, 빌게이츠씨가 지난 한달간의 메일로 학습시킨 베이지안 스팸필터를 통하여 스팸이라고 판단할 확률은?


'큰 부는 사회에 되돌려 줄 큰 책임이 따르며, 또 최선의 방식으로 돌려줘야 한다'
빌게이츠가 자신의 말대로만 한다면 그는 노벨만큼 역사에 남을 정말로 멋쟁이 부자.

자~ 베이스의 정리에 맞게 수식을 적어보자.

P(스팸|click&teens) = P(click&teens|스팸)P(스팸)/P(click&teens)

 =  
                   P(click&teens|스팸)P(스팸)                       
   P(click&teens|스팸)P(스팸) + P(click&teens|~스팸)P(~스팸)
 
읔... 여기서 문제가 발생했다.

P(click&teens|스팸) 이걸 어떻게 구하지?
P(click|스팸)과 P(teens|스팸)은 주어졌는데...
그걸로 P(click&teens|스팸)을 구할 수 있을까?

이를 위해서는 한가지 커다란 가정을 해야한다.

두 단어 click과 teens는 서로 아무런 관계 없이 독립적으로 나타난다고 하자.

이 가정을 이용하면,

P(click&teens|스팸) = P(click|스팸)P(teens|스팸)

이라고 쓸 수 있다.

   
                   P(click&teens|스팸)P(스팸)                       
   P(click&teens|스팸)P(스팸) + P(click&teens|~스팸)P(~스팸)

=  
                         P(click|스팸)P(teens|스팸)P(스팸)                               
   P(click|스팸)P(teens|스팸)P(스팸) + P(click|~스팸)P(teens|~스팸)P(~스팸)

이제 값을 적용할 수 있는 수식을 만들어 냈으므로 값을 대입하면,

=  
                 0.9 * 0.8 * 0.7                
      0.9 * 0.8 * 0.7   +   0.2 * 0.05 * 0.3

=99.41...%

따라서 답은 대략 99.41%이다.


예제10) 스팸 필터 #3

폴 그레이엄(Paul Graham)씨는 벤처기업 Viaweb을 창업하여 부자가 되긴 했지만  빌게이츠(Bill Gates)씨만큼의 돈과 시간을 가지진 않았기 때문에 자신의 전자메일함에 있는 모든 단어를 수작업으로 하나씩 검토하기 보다는 자신의 해커적 기질을 발휘한 간단한 리스프(lisp)프로그램을 작성하여 분석하기로 하였다.

폴그레이엄씨는 먼저 정상메일과 스팸메일에 각각에 대하여 등장하는 모든 단어에 대한 빈도수를 나타내는 해쉬테이블을 만들었다.
 
정상메일의 갯수를 ngood 라 하고,
정상메일에 대한 단어별 빈도수 해쉬테이블을 good 라 하자.
또한, 스팸메일의 갯수를 nbad 라 하고,
스팸메일에 대한 단어별 빈도수 해쉬테이블을 bad 라 하자.

그리고, 또 하나의 해쉬테이블을 만들어 특정한 단어가 포함된 이메일이 스팸일 확률을 담고 있도록 하였다. 이메일이 스팸일 확률은 아래 리스프 코드로 계산된다.

(let ((g (* 2 (or (gethash word good) 0)))
      (b (or (gethash word bad) 0)))
   (unless (< (+ g b) 5)
     (max .01
          (min .99 (float (/ (min 1 (/ b nbad))
                             (+ (min 1 (/ g ngood))  
                                (min 1 (/ b nbad)))))))))


이 세번째 해쉬테이블을 통하여 단어 '섹스'가 포함된 이메일이 스팸일 가능성이 97%이고 '섹시'가 포함된 이메일이 스팸일 가능성이 99%라고 했을 때, 두 단어를 모두 포함하고 있는 이메일이 스팸일 확률은?

폴그레이엄이 좋아하는 언어가 일반 프로그램들이 잘 모르는 리스프 코드라서 조금 설명이 필요할 것 같군. 리스프는 코드가 짧아서 좋긴 하지만, 상용제품이 너무 없고, 괄호가 너무 많아서, 초보자가 익숙해 지는데는 시간이 많이 필요할 것 같아.

let (g (* 2 (or (gethash word good) 0))) ...
g를 계산할 때 2를 곱해주는 것은 정상메일을 두번씩 수신한 효과가 있겠군. 다른 부작용은 없으니 일단 인정.
 
(unless (< (+ g b) 5) ...
단어의 등장횟수가 5번이상일 때만 확률을 따지게 했고,

(float (/ (min 1 (/ b nbad))
            (+ (min 1 (/ g ngood))  
                (min 1 (/ b nbad)))))
위 코드를 수식으로 다시 쓰자면 아래와 같다.

         b/nbad      
 b/nbad + g/ngood

생김새는 베이지안처럼 보이는데, 살짝 다르다.
내가 간단히 계산해 본 바에 의하면, 베이지안에서 한가지 추가적인 가정
즉, n개의 이메일에 있는 단어갯수의 총합은 n**2에 비례한다를 해야만 한다.

폴그레이엄은  false positive를 피하기 위하여 이렇게 가정했다고 하는데,
선뜻 이해가 되지는 않지만, 그냥 폴그레이엄을 믿고 스팸일 확률을 따져보자.

폴 선생이 제시한 조합확률에 의하면 출현이 독립적인 단어들에 대하여
아래처럼 확률을 계산 할 수 있다는데...

P(스팸|섹스&섹시)
=                          P(스팸|섹스)P(스팸|섹시)                        
  P(스팸|섹스)P(스팸|섹시) + (1-P(스팸|섹스))(1-P(스팸|섹시))

허걱~ 지금까지 공부한 것과 영 다른 새로운 공식이다.
이 공식이 성립하기 위해서는 섹스와 섹시가 독립적이어야 한다는 독립조건외에도
황당하지만 P(스팸) = P(정상) 이라는 가정이 필요하다.
이 식에 대해서는 [팀 피터스의 공식분석]을 참조하기 바란다.

여기에 값을 대입하면,

=             0.97 * 0.99              
  0.97 * 0.99 + (1-0.97)(1-0.99)

= 99.97.. %


베이지안을 스팸탐지에 활용하는 것에 대한 폴그레이엄의 멋진 글은 아래에서 보세요.
A Plan for Spam



나이브 베이지안 분류기(Naive Bayesian Classifier)

지금까지 조건부 확률, 베이스의 정리에 대하여 배우고, 10개의 예제를 풀어보았다. 앞서의 예제가 어떤 사건이 일어나느냐 아니냐의 이분법적인 확률을 따졌다고 한다면, 여기서는 여러개의 카테고리 중에서 어느 카테고리에 가장 잘 매칭하는 가 하는 분류기법으로 베이지안을 사용하는 방법을 공부한다.

단어들로 이루어진 문서들을 미리 분류된 카테고리 중 하나로 분류하는 상황이라고 하자.  즉, 카테고리를 c라하고 특정문서에 들어있는 단어들을 w1,w2,...,wN 이라 한다면,
우리가 구해야 하는 값은 P(c| w1,w2,...,wN ) 이고, 베이스의 정리를 이용하면,

P(c| w1,w2,...,wN) = P(w1,w2,...,wN |c) P(c) / P(w1,w2,..., wN )

베이스의 정리를 이용하면, 이미 알고 있는 확률들을 이용하여 특정한 문서가 어느 카테고리에 들어갈 지를 결정할 수 있다. 즉, 확률이 가장 높은 카테고리에 들어갈 가능성이 가장 높은 것이다.

위의 공식들을 잘 살펴보자. 모든 카테고리에 대하여 확률을 계산하고, 이중 가장 큰 것을 찾아야 하는데, 모든 카테고리의 확률계산에서 분모는 모두 P(w1,w2,...,wN)으로 같다. 따라서, P(w1,w2,...,wN)을 계산할 필요가 없다.

그리고, P(w1,w2,...,wN | c)의 계산은 또 다시 어려운 문제이다. 그러나, 과감한 가정을 통하여 이 계산을 단순화 할 수 있다. 즉, 모든 w들은 서로 독립적이라고 가정하여,

P(w1,w2,...,wN |c ) = P(w1|c)P(w2|c)P(w3|c)...P(wN|c)

이렇게 쓸 수 있으며, 바로 이 조건이 베이지안을 Naive 하게 만든 요소이다.

폴 그레이엄선생처럼 모든 c에 대하여 P(c)를 같게 만들면 계산이 훨씬 더 쉬워지지만,
거기까지는 가정하지 말자.

이제 결론이다.

Max P(c| w1,w2,...,wN) = Max Mul P(wi|c) P(c)
   c                                   c


위 식에서 P 가 Max가 되는 c를 찾으면 Naive Bayesian Classifier 이다.

이를 프로그램으로 구현하기 위해서는...
각 카테고리마다 단어의 빈도수 해쉬테이블을 하나씩 가지고,
모든 카테고리에서의 문서빈도수를 알고 있어야 한다.

- 끝 -
Posted by 전경헌