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

Presentation on theme: "불확실성 (Lecture Note #11) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides"— Presentation transcript:

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

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

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

4 신뢰할 수 있는 확률 (사전확률: 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라는 증거를 얻을 수 있는 확률

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

6 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.4) = 0.677

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

8 확신인자 (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인 실수)

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

10 확신인자 (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= (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.45

11 확신인자 (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])

12 확신인자 (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

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

14 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)가 의미하는 바는? 불확실성 구간이 넓을수록 불확실

15 기존 불확실성의 문제점 예: 점원이 손님의 소리만 들었을 때 남자 손님일 가능성 증거구간 예 확률론에서는 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 사이에 있음

16 결합 규칙 (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

17 결합 규칙 (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에 대해 곱해서 더함

18 결합 규칙 (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로 낮아짐

19 수정된 결합 규칙 (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 만족

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

21 수정된 결합 규칙 송신기 문제 (예제 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)

22 수정된 결합법칙 풀이 (계속) 공집합의 합 E1에 대한 합성 bpa 계산 E2, E3, E4, E5에 대해 같은 방식으로
… = 0.453 E1에 대한 합성 bpa 계산 ( ) / (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이라고 결론지어 질 가능성도 있음

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