불확실성(Uncertainty) 현실세계: 복잡, 예측이 어렵다. 비논리적, 상호 모순적인 상황들로 얽혀있다. → 과학, 공학: 단순화, 규칙성 부여 시스템 내외부에 존재하는 불확실성에 대처할 필요 단순화된 모델, 정형화된 기법의 한계 불확실성 해결 기법 불확실하고 상호 모순적인 정보로부터 지식베이스의 일관성 유지 불확실성을 정량화 하는 확률적 기법 ↓ 여전히 제한적 인간의 불확실성에 대한 대처능력과는 비교 불가능 DARPA의 Grand Challenge 컴퓨터 외에 카메라, 레이더, 레이저 거리탐지기 같은 센서들을 갖춘 무인주행 차량이 사막(2004), 혹은 도시(2007)에서 목표지점까지 주행 중 발생할 수 있는 다양한 불확실성에 대한 대처가 현실적 관건

불확실성 요인 데이터의 불확실성 지식의 불확실성 정보의 불완전성 확률적 불규칙성 센서 장치로부터 얻어지는 데이터는 불완전 여러 요인에 의한 오차가 포함된 데이터 지식의 불확실성 지식은 모호하고 휴리스틱한 절차에 의해 입수 동일한 전문 영역의 지식도 불일치 가능 표현 및 저장시의 문제점 정보의 불완전성 불완전하고 부분적인 정보로부터 판단해야 할 경우 무인주행 자동차: 경로상의 모든 상황에 대한 방대한 정보 입수불가 확률적 불규칙성 예측 불가능한 요인에 의해 발생하는 불규칙성

비단조 추론(Nonmonotonic Reasoning) 기존 논리체계 문제해결에 필요한 모든 정보 존재 또는 1차 논리로 유도(완전성: Completeness) 정보 상호간에 모순이 없다(일관성:Consistency) 참으로 알려진 정보의 숫자는 줄지 않는다. 새로운 사실이 기존의 사실을 부정하게 되는 경우가 없다(단조성: Monotonicity) 비단조 추론 위의 가정이 적합하지 않은 문제에 대한 추론이 요구될 때 새로운 사실이 기존의 참인 사실과 모순될 수도 있다. 기존 지식 중 일부를 부정할 수도 있다. → 새로운 지식의 취득이 계속되어도 전체적으로 참인 사실의 수는 감소할 수도 있다.(단조 증가가 아니다) 비단조 추론이 필요한 상황: 불완전한 정보, 가변적 조건, 추론이 불가능할 때 그 상황에서 적절히 가정을 세울 수 있을 때.

비단조 추론 예 (예제 1) 상황: 서울 → 대구 운전, 고속도로 정체, 대전 전에 국도진입, 초행이며 밤이고 인적 없음, 남동쪽으로 추정하면서 운전, 큰 강을 잇는 다리 지남(현재 상황) 여행에 관련된 운전자의 지식 사실1: 대전의 남쪽에는 전라도와 경상도가 있다 사실2: 전라도는 서쪽에 경상도는 동쪽에 있다. ... ... 사실25: 전라도 사람의 대부분은 전라도 사투리를 사용한다. 사실26: 경상도 사람의 대부분은 경상도 사투리를 사용한다. 사실27: 북쪽에서 전라도로 남향하면 만경강을 만나게 된다. 사실28: 북쪽에서 경상도로 남향하면 낙동강을 만나게 된다. 사실29: 낙동강을 지나면 대구까지는 자동차로 1시간 정도 걸린다. ... ... 사실50: 대구는 경상도에 있다.

다리를 건넌 뒤 라디오 청취(전라도 사투리 사용하는 것을 들음) 후 새롭게 획득한 지식 현 상황에서의 운전자의 인식 사실 다리를 건넌 뒤 라디오 청취(전라도 사투리 사용하는 것을 들음) 후 새롭게 획득한 지식 전라도 지역 방송 청취로 상황 인식 변화 새로운 지식의 획득이 신뢰 상황 모두를 변화시킴 새로운 지식의 획득이 신뢰 상황을 증가시키지 못함 신뢰1: 현재 남동쪽으로 여행 중이다. 신뢰2: 현재 경상도내에 있다. 신뢰3: 금방 지난 다리는 낙동강 위에 있다. 신뢰4: 목적지까지는 1시간 정도 걸린다. 신뢰1: 현재 전라도내에 있다. 신뢰2: 현재 남서쪽으로 여행 중이다. 신뢰3: 금방 지난 다리는 만경강 위에 있다

부재 추론(Default Reasoning) 환경변수나 조건의 값이 부재 → 기본 값을 사용하여 추론 대부분 참일 것으로 추정되는 사항을 기초로 하여 결론을 이끌어 냄 a라는 전제조건이 증명가능하고, 이로부터 일관성 있게 b라고 가정할 수 있다면, b라고 결론 내릴 수 있다. 예) 어떤 사람이 동시에 현실적이고 이론적일 수는 없다고 하면, 두 결과는 서로 상충하게 된다. 두 규칙 중 하나만 적용 → 최근 규칙이 우선이라고 가정 → practical(x)는 삭제됨 → 모순 해결 규칙의 적용순서에 상관없는 단조추론과는 비교됨

추정법(Abduction) 인과적 형태로 주어진 지식에 근거 결과로부터 원인을 추정하는 것이 일관성이 있으면 그 원인을 단정지음 (a → b)와 b로부터 a를 추정하는 것이 일관성이 있으면 a라고 결론짓는다.(부재 추론의 한 방법) 예) “자동차 축전지가 방전되면 시동이 걸리지 않는다”는 지식 이용 시동이 걸리지 않으면 축전지 방전이라고 결론 내릴 수 있다(단, 일관성이 유지되어야 함) 자동차의 다른 전기 장치들이 제대로 작동되면 축전지 방전에 대한 결론은 일관성을 잃음

폐세계 가정(Closed World Assumption) 특정의 닫힌 세계의 지식만으로 추론 → 닫힌 세계의 지식만으로 H라는 가설을 증명하는 것이 불가능하면 ~H가 참이라고 가정 예) 어떤 회사에 홍길동이 있는가?의 질의 → 회사의 데이터베이스 조회(이 데이터베이스는 전 사원에 대한 데이터를 가진다고 가정) → 조회결과가 없으면 답은 No. 문제세계 내에서 증명될 수 없는 사실은 그 역이 존재한다고 결론내림 ~H를 페세계에 추가하는 것이 타당한가? 예1) 지구 밖의 우주에 생명체의 존재를 증명할 수 없다고 생명체가 없다고 결론 내릴 수 있는가? 예2) 어떤 사람 P가 학교 정문으로 들어가면 P는 학생 또는 교직원 P가 학생이라고 증명 불가 P가 교직원이라고 증명 불가 일관성이 없는 지식 학생(P)∨교직원(P) ~학생(P) ~교직원(P)

사실유지 시스템(Truth Maintenance System; TMS) 특정 시스템 내에 상호 모순되는 사실들을 정리하여 일관성을 유지시키는 시스템(∵비단조 시스템에 의해 추론된 결과는 이전의 참을 부정할 수 있음) 지원목록(Support List) 이용 지식들 사이의 지원(참으로 될 근거) 관계를 표현 지식1 [SL (참노드 리스트)(거짓노드 리스트)] 참노드는 지식1이 참이 되기 위해 IN되어야 할 노드 리스트 거짓노드는 지식1이 참이 되기 위해 OUT되어야 할 노드 리스트 날씨에 관련된 지식과 지원목록 예 노드번호 지식 지 원 목 록 1 날씨가 맑다 [SL (2)(3)] 2 낮이다 [SL ( )( )] ← 전제(Premise) 3 비가 온다 [SL ( )(1)] 4 따듯하다 [SL (1)(3)] 5 습도가 높다 [SL (3)( )] ← Normal Deduction

TMS 동작예 현재 TMS의 IN, OUT 상태 IN 1, 2, 4 OUT 3, 5 → 즉, 현재는 낮이며, 맑고, 따뜻한 상태가 정당함 얼마 후 추론 시스템이 “비가 온다”라고 결론을 내리면 TMS는 → 노드 3을 IN에 넣는다. → 노드 3의 거짓리스트에 1이 있으므로 노드 1은 OUT된다. → 노드 3은 노드 4의 거짓리스트에 있으므로 노드 4는 OUT 된다. → 노드 3에 대해 normal deduction인 노드 5는 바로 IN된다. IN 2, 3, 5 OUT 1, 4 → 즉, 현재는 낮이며, 비가 오며 습도가 높은 상태가 정당함 노드 상호간의 관계를 사용하여 모순의 원인을 찾아 제거 →의존성에 의한 역추적(dependency-directed backtracking)

확률에 기초한 추론 여기서 다루게 될 3가지 확률기반 추론기법 Bayes의 정리와 전통적 확률론 확신 인자(Certainty Factor) Dempster-Shafer의 정리 확률의 기초 P(E): 사건 E가 일어날 확률 (0~1사이의 실수) 제한된 수의 상호 배타적인 사건들의 확률의 합은 1 일반적인 다수 사건 공간에서의 사건들 사이의 관계 P(A∪B) = P(A) + P(B) - P(A∩B) A와 B가 상호배타적이면 P(A∩B)=0 P(A∩B) = P(A)P(B) : 독립 사건일 때 A와 B 사건은 서로에게 영향을 주지 않음 P(A|B) = P(A∩B)/P(B) : 조건확률 B사건에 영향 받아(발생 후에) A가 일어날 확률 A와B가 상호배타적이면 P(A∩B)=0이므로 P(A|B) = P(B|A) = 0 A와B가 독립적이면 P(A|B) = P(A), P(B|A) = P(B) (∵다른 사건에 영향 없음)

Bayes의 정리 Bayes의 정리 Bayes 정리의 확장(by Laplace) B A A  B B1 B2 B3 … BN A

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

Bayes 정리의 활용 예 예) 겨울철 어떤 지역의 기침하는 사람이 감기일 확률 해) Bayes 정리의 활용의 어려움 겨울철 이 지역 주민 15%가 감기에 걸림 보통 감기 걸린 사람의 50%가 기침을 함 지역주민의 20%는 감기와 상관없이 기침을 함 해) P(기침|감기) = 0.5 P(감기) = 0.15 P(기침) = 0.2 해답: P(감기|기침)=P(기침|감기)P(감기)/P(기침) =0.5Ⅹ0.15/0.2=0.375 Bayes 정리의 활용의 어려움 n개의 증거, m개의 가설 (nm개의 조건확률)+(n개의 증거확률)+(m개의 가설확률) 제한된 영역, 간단한 문제에 유용

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

누적 신뢰척도 MB[c,ef]와 누적 불신척도 MD[c,ea]를 계산 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 확신인자 예) 결론 : 환자는 감기에 걸렸다 규칙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.2 누적 확신인자 CF=0.65-0.2=0.45

누적 신뢰척도 MB[c,ef]와 누적 불신척도 MD[c,ea]를 계산 하나의 증거가 다수의 결론에 도달 누적 신뢰척도 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]) 예) 증거 : 컴파일시 이상 없었는데 실행시키니 컴퓨터 화면이 이상 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

Dempster-Shafer의 증거이론(Theory of Evidence) 어떤 가게에서 점원이 잠시 창고에 간 동안 누군가 가게에 들어왔다가 나가는 소리를 들었다. 그 사람은 남자였을까 아니면 여자 였을까? 기존의 확률론: P(남자)=0.5, P(여자)=0.5 그러나 0.5라는 숫자는 별다른 의미가 없이, 인구에 대한 성별비율만 나타냄 Dempster와 Shafer에 의해 제안된 증거이론은 이러한 상황에 대한 보다 명확한 서술법을 제시한다: 여자 or 남자?

Shafer의 표시법에 의한 어떤 가설 H의 표시법 표시법: [Bel(H), Pl(H)] Bel(H): 가설 H가 주어진 증거에 의해 신뢰되어지는 정도 Bel(~H): 가설 H가 주어진 증거에 의해 불신되어지는 정도 Pl(H): 가설 H가 차후 주어질 증거에 의해 최대로 신뢰될 수 있는 가능성 Pl(H)= 1-Bel(~H) Pl(H)-Bel(H): 현재 주어진 증거에 의해 신뢰도 불신도 되지 못하고 남아 있는 부분. 즉, 불확실성의 크기 앞 Page의 예를 Shafer의 표시법으로 표시하면? 아무런 증거도 없으므로, Bel(남자)=0, Bel(~남자)=0 이므로 [0,1] 로 표시할 수 있고, 불확실성(Pl(남자)=1)이다. 여자의 가능성에 대해서도 마찬가지의 표시법으로 나타낼 수 있다. 기타 예제 4.10 참조 Pl(H) Bel(~H) Bel(H)

See next page Dempster의 결합규칙(combination rule) 예를 들어 상호 배타적인 가설에 의해 구성된 집합을 고려한다  = {H1, H2, H3} 어떤 증거에 의해 H2와 H3에 어느 정도의 가능성을 두게 되었다면 m1(H2, H3) = 0.3  Shafer의 증거구간 표시법 [0.3, 1] 나머지 확률은 전체집합에 둠: m1()=0.7 새로운 증거에 의해 H3가 0.4만큼 증거되는 경우 m2(H3) = 0.4, 따라서 m2()=0.6 상기의 m1과 m2에 의해 확률값이 주어진 부분집합 S1과 S2는 직교합의 형태로 합쳐져 S3에 대해 m3를 얻는다 (그림 4.4 참조) See next page

m1 {H2, H3} 0.3 {} 0.7 m2 {H1} 0.4 {ø} 0.12 {H1} 0.28 {} 0.6 m2(H1) = 0.4, m2()=0.6 m1 {H2, H3} 0.3 {} 0.7 m2 {H1} 0.4 {ø} 0.12 {H1} 0.28 {} 0.6 {H2, H3} 0.18 {} 0.42 m3()=0.12, m3(H1)=0.28, m3(H2,H3}=0.18, m3{)=0.42 그러나 m3는 주어진 가설외(즉, 공집합)에 가능성을 배정하였다. 따라서 다음과 같은 식으로 앞 Page의 식을 수정한다.

결어: 불확실성(Uncertainty) Uncertainties everywhere around our world 사람은 이처럼 불확실한 환경에서 잘 생활해 나가지만 기계에게는 무척 어려운 일 (Bicentennial Man의 로빈 윌리암스를 제외하고) 따라서 불확실성에 대한 보다 체계적 연구와 그 성과는 AI의 진정한 실현에 중요한 요구조건 다음 장에서 다루는 퍼지(Fuzzy) 이론은 인간세상에 존재하는 불확실성을 간단한 방식으로 처리하는 공학적 기법으로서 성공적으로 사용되고 있음 So many uncertainties here!