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

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

불확실성 (Uncertainty) 현실세계: 복잡, 예측이 어렵다. 비논리적, 상호 모순적인 상황들로 얽혀있다. → 과학, 공학: 단순화, 규칙성 부여 시스템 내외부에 존재하는 불확실성에 대처할 필요 단순화된 모델, 정형화된 기법의 한계 불확실성 해결 기법 불확실하고 상호 모순적인 정보로부터 지식베이스의 일관성 유지 불확실성을 정량화 하는 확률적 기법 여전히 제한적 인간의 불확실성에 대한 대처능력과는 비교 불가능 CMU’s 무인 주행 자동차, NAVLAB 컴퓨터 외에 카메라, 레이더, 레이저 거리탐지기 같은 센서들, 다수의 통신용 안테나를 갖고 있지만, 주행 중 돌발상황 대처 부족 Vs. 미로 주행하는 마이크로 마우스

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

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

비단조 추론 (Nonmonotonic Reasoning) 비단조 추론의 개념: 그림 4.2 M1: Wff F1에 해당하는 모델 비단조 추론 시스템 (Non-monotonic Reasoning System) 새로운 지식이 첨가될 경우 기존의 지식을 정리

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

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

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

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

추정법 추정법 실패 예: 예제 4.2 추정법의 다른 문제점 추정법 x, Seoulite (x)  suffer_from_traffic(x) suffer_from_traffic(P):M Seoulite(P) Seoulite(P) 결론은 “교통혼잡으로 고통을 받으면 서울 사람이다” 맞지 않음 앞 예와의 차이점은 직접적 원인이 아님 추정법의 다른 문제점 다수의 결론이 가능 예: 어떤 사람이 한기를 느끼는 원인 여러가지 추정법 부재 추론의 특별한 경우 결론이 다른 사실과 상충될 수 있으므로 비단조 추론 주어진 사실로부터 원인을 찾아내는 데 유용

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

사실유지 시스템 (Truth Maintenance System: TMS) 비단조 시스템에 의해 추론된 결과는 이전의 참을 부정할 수 있음 특정 시스템 내에 상호 모순되는 사실들을 정리하여 일관성을 유지시키는 시스템 예제 4.3 KB: “식물은 지능이 없다”, “지능이 없는 것은 반응하지 않는다” 추론: “식물은 반응하지 않는다”  KB에 추가 “식물은 지능이 있다”가 참으로 받아들여져 입력된다면? “식물은 지능이 없다” 삭제되어야 “식물은 반응하지 않는다”도 삭제되어야 실제로는 삭제하지 않고 별도 관리 지식들 사이의 관계를 나타낼 필요

사실유지 시스템 (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 동작 예 노드 상호간의 관계를 사용하여 모순의 원인을 찾아 제거 현재 TMS의 IN, OUT 상태가 다음과 같다고 가정 IN 1, 2, 4 OUT 3, 5 → 즉, 현재는 낮이며, 맑고, 따뜻한 상태가 정당함 얼마 후 추론 시스템이 “비가 온다”라고 결론을 내리면 IN, OUT이 어떻게 변경되어야 하는지 → 노드 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)

확률에 기초한 추론 확률에 기초한 추론 확률기초 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) (∵다른 사건에 영향 없음)

확률에 기초한 추론 예제 4.5: 카드 놀이 임의의 카드가 heart 일 확률은? 13/52 다른 무늬는 상호 배타적 임의의 카드가 king이고 heart 일 확률은? king과 heart는 서로 독립적 P(king ∩ heart) = P(king)P(heart) = 4/52 * 13/52 = 1/52 임의의 카드가 king이거나 heart 일 확률은? P(king ∪ heart) = P(king) + P(heart) - P(king ∩ heart) = 4/52 + 13/52 – 1/52 = 16/52 상호배타적? No

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