불확실성 (Lecture Note #11) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides by SciTech Media 불확실성 (Lecture Note #11) 인공지능 이복주 단국대학교 컴퓨터공학과

Outline 불확실성 비단조 추론 (Non-monotonic Reasoning) 부재 추론 (Default Reasoning) 추정법 (Abduction) 사실 유지 시스템 (Truth Maintenance System) 확률에 기초한 추론 Dempster-Shafer 이론

Bayes의 정리 Bayes의 정리 Bayes 정리의 확장(by Laplace)

신뢰할 수 있는 확률 (사전확률: priori probability) (사후 확률: posteriori probability) 확장된 Bayes 정리 확장된 Bayes 정리 S상의 임의의 부분 Bi과 임의의 사건 A에 대해서 Bayes 정리의 활용 E: 주어진 증거(evidence) Hk(k=1, 2, … , N): 고려할 수 있는 상호배타적인 N개의 가설 중 하나에 대해서, 증거 E가 주어졌을 때 가설 Hk이 참일 확률은 증거없이 특정한 가설 Hk를 신뢰할 수 있는 확률 (사전확률: priori probability) 증거 E에 대한 원인으로 Hk를 고려할 수 있는 정도 (사후 확률: posteriori probability) Hk이 참일 때 E라는 증거를 얻을 수 있는 확률

Bayes의 정리 Bayes 정리 = 원인확률정리 (cause probability theorem) 응용 PROSPECTOR: 광물탐사용 전문가 시스템 MYCIN: 질병 진단과 처방용 전문가 시스템 로봇에서 여러 센서 정보의 융합

Bayes 정리의 활용 예 Bayes 정리의 활용 예 예: 겨울철 어떤 지역의 기침하는 사람이 감기일 확률 해: 겨울철 이 지역 주민 15%가 감기에 걸림 보통 감기 걸린 사람의 50%가 기침을 함 지역주민의 20%는 감기와 상관없이 기침을 함 해: P(감기) = 0.15 P(기침|감기) = 0.5 P(기침) = 0.2 해답: P(감기|기침)=P(기침|감기)P(감기)/P(기침) =0.5Ⅹ0.15/0.2=0.375 예: 인공지능, 복학생 P(복학생) = 0.6 P(A학점|복학생) = 0.35 P(A학점|~복학생) = 0.25 P(복학생|A학점) = ? P(복학생|A학점) = P(A학점|복학생) P(복학생) / (P(A학점|복학생) P(복학생) + P(A학점|~복학생) * P(~복학생)) = 0.35 * 0.6 / (0.35 * 0.6 + 0.25 * 0.4) = 0.677

Bayes 정리 Bayes 정리의 활용의 어려움 n개의 증거, m개의 가설 예: 500가지의 질병, 2000가지의 증상 (nm개의 조건확률)+(n개의 증거확률)+(m개의 가설확률) 예: 500가지의 질병, 2000가지의 증상 약 500*2000 개의 확률이 계산되어야 제한된 영역, 간단한 문제

확신인자 (Certainty factor: CF) 주어진 증거들로부터 어떤 결론이나 가설을 신뢰할 것인지 아닌지에 대한 정도를 정량화 하기 위한 방법 의료용 전문가 시스템인 MYCIN에서 채택 예: if 환절기이고, 환자가 기침을 하고, 콧물을 흘리면 then 환자가 감기에 걸렸다 (with CF=0.8) 신뢰척도 (measure of belief: MB)와 불신척도 (measure of disbilief: MD) MB[c,e]: 주어진 증거 e에 의해 결론 c가 신뢰 받을 수 있는 척도 [0..1]의 값 가짐. 1: 절대적 신뢰 MD[c,e]: 주어진 증거 e에 의해 결론 c가 불신되는 척도 [0..1]의 값 가짐. 1: 절대적 불신 CF[c,e] = MB[c,e] - MD[c,e] (0  MB, MD  1이므로 –1  CF  1인 실수)

확신인자 (Certainty factor: CF) 누적확신인자 (Cumulative certainty factor) 하나의 결론에 대해 다수의 증거나 규칙이 존재하는 경우 CF [c,ec] = MB[c,ef] - MD[c,ea] ec : 결론 c에 대해 현재까지의 모든 증거 ef : 결론 c를 신뢰(for)하게 하는 모든 증거 ea : 결론 c를 불신(against)하게 하는 모든 증거

확신인자 (Certainty factor: CF) 누적 신뢰척도 MB[c,ef]와 누적 불신척도 MD[c,ea]를 계산 e1: 기존의 증거, e2: 새로운 증거 MB[c, e1&e2] = 0 if MD[c, e1&e2] = 1 = MB[c,e1] + MB[c,e2](1-MB[c,e1]) otherwise MD[c, e1&e2] = 0 if MB[c, e1&e2] = 1 = MD[c,e1] + MD[c,e2](1-MD[c,e1]) otherwise e1, e2 서로 독립적 Counter example: “라디오 소리 작아짐”, “전지의 전압 떨어짐” 확신인자 예 결론: 환자는 감기에 걸렸다 규칙1: 콧물이 흐르면 감기에 걸렸을 수 있다 (CF=0.5) 규칙2: 기침으로 고생하면 감기에 걸렸을 수 있다 (CF=0.3) 규칙3: 식욕이 왕성하면 감기에 걸렸을 수 있다 (CF=-0.2) 규칙1 적용: MB=CF=0.5, MD=0 여기에 규칙2 적용: MB=0.5+0.3(1-0.5)=0.65, MD=0 여기에 규칙3 적용: MB=0.65, MD=0+0.2(1-0)=0.2 누적 확신인자 CF=CF [c,ec] = MB[c,ef] - MD[c,ea] = 0.65-0.2=0.45

확신인자 (Certainty factor: CF) 하나의 증거가 다수의 결론에 도달 예: e: 기침을 한다, c1: 감기, c2: 천식 누적 신뢰척도 MB[c,ef]와 누적 불신척도 MD[c,ea]를 계산 MB[c1c2, e] = min (MB[c1,e], MB[c2,e]) MD[c1c2, e] = min (MD[c1,e], MD[c2,e] MB[c1c2, e] = max (MB[c1,e], MB[c2,e]) MD[c1c2, e] = max (MD[c1,e], MD[c2,e])

확신인자 (Certainty factor : CF) 예 증거 : 컴파일시 이상 없었는데 실행시키니 컴퓨터 화면이 이상 가능한 여러가지 결론 c1: 검사용 프로그램을 실행 (CF=0.6) c2: 문제는 소프트웨어 (CF=0.9) c3: 컴퓨터 바이러스에 감염 (CF=0.3) c4: 프로그램에 버그 (CF=0.5) 결론 “문제는 소프트웨어이며 바이러스 감염 또는 프로그램 버그이어서 검사용 프로그램 실행해야 함” 의 신뢰척도는? MB[c1c2(c3c4), e] = min(MB[c1,e], MB[c2,e], MB[c3c4,e]) = min(MB[c1,e], MB[c2,e], max(MB[c3,e], MB[c4,e])) = min(0.6, 0.9, max(0.3, 0.5)) = 0.5

확신인자 (Certainty factor : CF) Bayes 정리와 다른 점은? CF: 결론에 관련된 각 법칙의 기여도 P(c|e) 와 비슷 c에 e가 유일할 때 사용 c에 e가 유일하지 않을 때는 결합 확률 사용됨 (Bayes 쪽) 독립적인 법칙들을 다룰 때는 CF가 간편 규칙의 독립성은 규칙 작성자의 몫 CF 할당의 어려운 점 전문가가 CF 숫자에 익숙치 않음 동일한 기준을 갖지 않음 0 (그렇지 않다) 또는 1 (확실하다) 또는 0.5 (모르겠다)로 나오는 경우 많음

Dempster-Shafer 이론 [Dempster68, Shafer76] Theory of evidence [Bel(h), Pl(H)] 확률 대신에 구간으로 표시 증거구간 (evidential interval): 그림 4.3 Bel (Belief): 주어진 증거에 의해 H가 지원 받는 정도 Pl (Plausibility): H가 부정되지 않고 남아있을 정도 Pl(H) = 1 – Bel(~H) Pl(H) – Bel(H)가 의미하는 바는? 불확실성 구간이 넓을수록 불확실

기존 불확실성의 문제점 예: 점원이 손님의 소리만 들었을 때 남자 손님일 가능성 증거구간 예 확률론에서는 0.5 0.5라는 숫자를 보고 이 것이 어떤 증거를 가지고 부여된 것인지 아니면 단순히 아는 것이 없어서 부여된 것인지 알 수 없음 Dempster-Shafer 이론에서는 [0, 1] 지원 증거 없고 (Bel = 0) 부정 할 증거도 없음 (Pl = 1) 증거구간 예 [0, 0]: H를 지원하는 증거 없음 (0). 부정하는 증거는 절대적 (1). 가설은 거짓 [1, 1]: 지원하는 증거만 있으므로 가설은 참 [0.25, 1]: 부정하는 증거는 없고 (0), 지원하는 증거는 약간 있다 (0.25) [0, 0.75]: 지원하는 증거는 없고, 부정하는 증거 약간 (0.25) [0.25, 0.75]: 지원하는 증거와 부정하는 증거가 0.25만큼 있다. H가 참일 가능성이 0.25와 0.75 사이에 있음

결합 규칙 (Combination Rule) 개별적인 증거들의 결합 가정 어떤 증거 E1이 서로 배타적인 N개의 가설을 지원하는 경우  (Frame of Discernment): N개 가설의 집합 2N개의 부분집합 기본 확률배당 (basic probability assignment) m1: {Sn|Sn  }  [0, 1] Sn: 부분집합의 하나 Sn이 지원 받는 정도 m1() = 0 공집합은 0에 할당 Sn   m1(Sn) = 1 모든 부분집합에 할당된 확률 값의 합은 1

결합 규칙 (Combination Rule) 예  = {H1, H2, H3} 아무런 증거가 없을 때: m1() = 1 가설중의 일부에 해가 있다 어떤 증거로부터 m1(H2, H3) = 0.3 에 사상 m1() = 0.7: 나머지는 전체 중 어딘가에 할당 {H2, H3}의 증거구간: [0.3, 1] ~{H2, H3}에 대한 증거 없음 불확실성은 0.7 복수 증거에 의한 확률의 결합 m1(S1)과 m2(S2)의 결합은 S1  S2에 m1(S1)m2(S2)로 계산 새로운 bpa함수 m3: S1  S2 =S3 m1(S1) m2(S2)  직교합 (orthogonal sum) S1  S2 =S3 인 모든 S1, S2의 pair에 대해 곱해서 더함

결합 규칙 (Combination Rule) 예  = {비, 눈, 햇빛} 서로 배타적 어떤 증거에 의해 bpa m1이 다음과 같다면 m1(비, 눈) = 0.7 m1() = 0.3 다른 어떤 증거에 의해 bpa m2가 다음과 같다면 m2(비, 햇빛) = 0.6 m2() = 0.4 m1과 m2의 직교합: 표 4.4 Note 공집합은 나오지 않은 경우 m3의 합은 1이 됨 {비, 눈}: 0.7에서 0.28로 낮아짐 {비, 햇빛}: 0.6에서 0.18로 낮아짐 2003.10.02

수정된 결합 규칙 (Combination Rule) S1  S2 =S3 m1(S1) m2(S2)의 문제점 S1  S2 = 이면 0을 할당해야 하는 데, 그렇지 않음 m1() = 0에 위배 수정된 결합 규칙 S1  S2 =S3 m1(S1) m2(S2) 1 - S1  S2 =  m1(S1) m2(S2) 교집합해서  이 나오는 S1, S2 pair 를 곱해서 더한 것을 1에서 뺀 것으로 normalize m() = 0, Sn   m(Sn) = 1 만족

수정된 결합 규칙 예 앞의 예 m3에 새로운 증거 m4가 추가 m4(햇빛) = 0.8 m4() = 0.2 S1  S2 =S3 m1(S1) m2(S2) 식을 사용 공집합 부분이 0.56 매우 큼: 증거들 사이에 일관성이 없음 공집합 아닌 부분 다 더하면 0.44 1-0.56 = 0.44로 정규화 (p. 92) {햇빛}은 두 군데

수정된 결합 규칙 송신기 문제 (예제 4.12) 풀이 직교합 (p. 93) 5개의 송신기 E1, …, E5  Hypothesis 수신기 하나 어떤 송신기가 신호를 보냈는지 identify하려고 함 RF (radio frequency)와 PW (pulse width)에 의해 판단 mRF(<E1, E2, E3, E4, E5>) = <0.13, 0.22, 0.35, 0, 0> mPW(<E1, E2, E3, E4, E5>) = <0.26, 0.085, 0.17, 0.034, 0.26> 풀이 mRF() = 0.3, mPW() = 0.2 직교합 (p. 93)

수정된 결합법칙 풀이 (계속) 공집합의 합 E1에 대한 합성 bpa 계산 E2, E3, E4, E5에 대해 같은 방식으로 0.011 + 0.022 + … + 0.091 = 0.453 E1에 대한 합성 bpa 계산 (0.034 + 0.026 + 0.078) / (1 – 0.453) = 0.25 E2, E3, E4, E5에 대해 같은 방식으로 mRF&PW(<E1, …, E5>) = <0.25, 0.16, 0.33, 0.018, 0.14> 합은 0.898 불확실성은 0.102 Shafer 표현법 E1의 경우 0.25이외에 0.102만큼의 가능성 (plausibility) 갖는다 E1 [0.25, 0.352] E2 [0.16, 0.262] E3 [0.33, 0.342] E4 [0.018, 0.12] E5 [0.14, 0.242] 결론: 수신된 신호는 E3로 부터 방출되었다고 추정 불확실성 0.102가 전적으로 E1이라면 E1은 0.352 이것은 0.33보다 큼 E1이라고 결론지어 질 가능성도 있음

Summary 불확실성 비단조 추론 (Non-monotonic Reasoning) 부재 추론 (Default Reasoning) 추정법 (Abduction) 사실 유지 시스템 (Truth Maintenance System) 확률에 기초한 추론 Dempster-Shafer 이론