진리값 유지 시스템

진리값 유지 시스템 (믿음 개정 (belief revision) 과 개정 유지 (revision maintenance) 시스템으로도 알려져 있다.) 은 추론 시스템에 대하여 쌍을 이루는 구성 부분이다. 진리값 유지 시스템의 주된 일은 어떤 추론 기능을 수행하는 것이 아니라 문제 풀이기 (problem solver) 에 의하여 사용될 지식의 일치성을 유지하는 것이다. 그것으로, 문제 풀이기는 일치성에 관한 염려는 할 필요가 없어지고 문제 풀이 측면에만 집중할 수 있다. 진리값 유지 시스템은 추론 구성 부분이 비단조 추론을 할 수 있도록 해준다. 새로운 것이 발견될 경우, 보다 최근의 정보는 더 이상 정당하지 않는 이전의 결론을 교체할 수 있다. 이와 같은 방법으로 문제 풀이가 접근 가능한 믿음의 집합은 최신의 (current) 것, 그리고 일치된 것을 유지하고 있다.

그림 1 은 문제 풀이기 부분으로서 진리값 유지 시스템의 역할을 나타낸다. 추론 기관 (inference engine:IE) 은 현재의 믿음 집합에 바탕을 두어서 영역 문제를 풀고, 반면에 진리값 유지 시스템은 최신의 활성 믿음 집합 (current active belief set) 을 가지고 있다. 갱신 과정은 증가적인 것이다. 각 추론 후에 2 개의 구성 부분 사이에서 정보가 교환된다. 추론 기관은 진리값 유지 시스템에게 자신이 수행한 연역 (deduction) 을 알려준다. 교대로, 진리값 유지 시스템은 최신의 믿음과 실패 이유에 관한 질문을 한다. 이것은 새로운 지식이 추가되거나 삭제되어도 추론 기관이 작동할 수 있도록 일치된 믿음의 집합을 가지게 된다.

예를 들어, 지식 베이스가 명제 , 와 모더스 포넨스만 가지고 있다고 하자. 여기서, 추론 기관은 를 적법하게 결론 지어서 지식 베이스에 이 결론을 추가할 수 있다.  나중에, 가 타당한 것을 알게 되면, 이것이 지식 베이스에 추가되어 모순을 일으킨다. 결과적으로, 불일치를 없애기 위해서 를 제거하는 것이 필요하게 된다. 그러나, 가 제거되었으므로, 는 더 이상 정당한 믿음 (justified belief) 이 아니다. 이것 역시 제거되어야 한다. 이런 유형의 믿음 개정이 진리값 유지 시스템이 하는 일이다.

실제로, 진리값 유지 시스템은 와 같은 결론을 위에서 제시한 것처럼 버리지는 않는다. 이것은 낭비적이다. 왜냐하면 가 다시 정당한 것이 될 수 있고, 이렇게 되면 와 에 의해서 정당화되었던 사실들은 재유도 (redrive) 되어야 하기 때문이다. 대신에, 진리값 유지 시스템은 이런 모든 결론에 대해서 의존 레코드 (dependency records) 를 가진다. 이들 레코드는 믿음의 어떤 집합이 최신인지를 (어떤 것이 추론 기관에 의해서 사용될 것인가를) 결정한다. 그래서, 를 실제로 삭제하는 것이 아니라, 이들 레코드에 적절한 갱신을 함으로써 최신의 믿음 집합으로부터 제거된다. 를 버리는 것이 아니므로, 가 다시 정당화되어도 이것의 재유도는 필요하지 않다. 진리값 유지 시스템은 믿음에 대한 이유 (reasons) 혹은 정당성 (justifications) 의 완전한 레코드를 가진다. 적어도 하나의 타당한 정당성을 가진 각 명제나 문은 최신의 믿음 집합의 일부가 되고 있다. 받아들일 수 있는 정당성이 부족한 문은 이 집합으로부터 배제된다. 모순이 발견되었을 때, 이 모순에 책임있는 문들을 확인한 다음 적절한 것을 철회한다. 이것은 교대로 또 다른 철회와 추가가 일어날 수 있다. 이 과정을 수행하는 프로시쥬어를 의존성을 이용한 역행 (dependency-directed backtracking) 이라 한다. 이 과정은 뒤에 가서 논한다.

그림 1 진리값 유지 시스템을 가진 문제 풀이기의 구조

진리값 유지 시스템은 추론 기관이 항상 최신 믿음 집합을 알 수 있도록 하기 위하여 철회와 추가를 나타내는 레코드를 가진다.

레코드는 의존 망 (dependency network) 형태로 유지된다. 이 망에서 노드는 전제, 결론, 추론 규칙 따위의 지식 베이스 엔트리 (entry) 를 나타낸다. 노드에 부착되어 있는 것은 그 노드가 유도된 추론 단계를 나타내는 정당성이다. 믿음 집합에 있는 노드는 타당한 정당성을 가져야 한다. 전제 (premise) 는 항상 참으로 여겨지는 기본 믿음이다. 전제는 어떤 정당성도 필요로 하지 않는다. 이들은 현재 활동 중인 모든 다른 노드가 타당한 정당성의 관점에서 설명되어질 수 있는 근거를 마련하고 있다.

노드에 대한 정당성 레코드는 2 종류가 있다 : 지원 리스트 (support lists) 와 개념 의존 (conceptual dependencies) 이다. 지원 리스트는 가장 흔한 형태이다. 이것은 노드에 대한 지원 정당성을 제공해 준다. 지원 리스트에 사용되는 자료구조는 2리스트의 다른 의존 노드 이름을 가진다 : in-리스트와 out-리스트.

이것의 형태는

 (SL  <in-list>  <out-list>)

이다.

한 노드가 활성화되어서, 믿음 집합이 IN 이 되기 위해서는, 그것의 지원 리스트는 in-리스트에서 적어도 하나의 정당한 노드를 가져야만 하고, 만약 존재한다면 out-리스트로 명명된 모든 노드는 믿음 집합의 OUT 으로 표시되어야 한다. 예를 들어, Cybil 은 날 수 없는 새 (일종의 타조) 라는 것을 나타내고 있는 현재의 믿음 집합은 표 1 과 같이 나타날 수 있다. 표 1 에 주어진 각 IN-노드는 현재의 믿음 집합의 일부분이다. 노드 n1 과 n5 는 전제이다. 이들은 정당성을 필요로 하지 않는 전제이므로 빈 지원 리스트 (empty support lists) 를 가진다. "Cybil can fly" 라는 믿음인 노드 n2 는 정당한 노드 n3 가 n2 의 out-리스트에 있기 때문에 out이다.

표 1 의존 망에서 노드의 예

Cybil 이 타조가 아니라는 사실이 발견되어서, n5 가 철회되었다고 (이것의 상태 (status) 를 OUT 으로 표기) 가정하자. 그러면, n5 에 의존하는 n3 역시 철회되어야 한다. 이것은 차례로 n2 의 상태를 정당한 노드로 만든다. 결과적인 믿음 집합은 이제 "The bird Cybil fly" 가 된다.

믿음 망을 표현하기 위하여, 그림 2 에서 보여지는 기호 약속이 종종 사용된다. 그림에서 보여지는 노드의 의미는,  (1) 전제는 정당성 (justification) 을 필요로 하지 않는 명제이다.  (2) 가정 (assumption) 은 변할 수도 있는 현재의 믿음이다.  (3) 한 자료는 현재 가정된 혹은 추론 기관이 유도한 믿음이다.  (4) 정당성은 지원 전제 노드 (supporting antecedent node) 링크와 결론 노드 링크로 구성되는 믿음 (노드) 지원이다.

그림 2 믿음 망 노드 의미

전형적인 망 표현의 예가 그림 3 에 주어져 있다. 노드 T, U, W 는 P 로부터의 필요한 지원이 없기 때문에 OUT 이다. 만약 P 로 명명된 노드가 어떤 이유로 인해 IN 이 된다면, 진리값 유지 시스템은 노드 P 에 의해서 제공되는 "innes" 지원을 파급시켜서 T, U, W 노드를 IN 으로 만드는 방식으로 망을 갱신한다.

그림 3 믿음 망의 전형적인 부분

앞에서 언급한대로, 모순이 발견되면 진리값 유지 시스템은 모순의 근원을 찾아서 해당 근원 중에서 하나를 철회하는 방식으로 이를 고친다. 이것을 수행하는 방식은 모순 노드의 지원 리스트를 살펴보고 모순의 근원으로 바로 간다. 이것은 정당성을 지원하는 의존 구조 (dependency structure) 를 검사해서 위반 노드 (offending nodes) 를 결정하는 방법으로 근원에 바로 가게 된다. 이것은 연역트리를 노드별로 순차적으로 탐색해서 모순 노드에 다다르는 순수한 역행 접근법과는 대조적이다. 모순을 일으키는 노드로 바로 가는 역행은 의존성을 이용한 역행 (dependency-directed backtracking:DDB) 이다. 이것은 분명히 연대기적역행 (chronological backtracking) 보다는 보다 효과적인 탐색 전략이다. 이 과정은 그림 4 에서 보여지는데, 여기서 A 와 D 는 모순으로 가정하였다.

그림 4 진리값 유지 시스템에서 의존성을 이용한 역행

모순의 근원에서 바로 역행 (E 에서 A로 dashed line) 함으로써, 추가 탐색 시간이 소요되지 않는다.

개념 의존 정당성 (CP justification) 은 지원 리스트보다 사용 빈도가 낮다. 이들은 정당한 가설 논법 (hypothetical argument) 의 형태로 노드를 정당화한다.

 (CP <consequent>  <inhypotheses>  <outhypotheses>)

in-hypotheses 내의 각 노드가 IN 이고, out-hypotheses 내의 각 노드가 OUT 일 경우에는 언제나 결론 노드 (consequent node) 가 IN 이라면, 하나의 CP는 정당하다. 2 개의 별도의 가설 노드가 사용된다. 왜냐하면 노드들은 IN 인 노드들과 OUT 인 다른 노드들로부터 유도될 수 있기 때문이다.

CP 는 연역 시스템에서 전형적으로 일어나는 조건 증명에 해당한다. 이런 조건 증명에 사용되는 가설은 CP 에서 in-hypotheses 에 대응한다. CP 의 기능은 약간 복잡하므로, 그 주요 기능을 예를 들어 밝힌다.

민영 항공을 위한 항공기와 승무원을 계획하는데 사용되는 시스템을 가정해보자. 주어진 항공에서 보통 항공기의 종류는 737 이고, 필요한 승무원은 A 급이다. 이러한 사실에 대한 노드와 정당성은 다음과 같이 될 수 있다.

여기서 n1 에 대한 정당성은 n2 (OUT 상태) 이고, n3 에 대한 것은 n8, .., n22 노드인데 이들은 기장, 부기장, A 급 자격의 기타 승무원을 나타낸다. 이제, 완전히 A 급 승무원만으로 구성할 수 없다는 것이 알려졌다고 가정하자. 비행 계획을 완성하기 위해서 시스템은 다른 항공기, 가령 L400 를 선택해야 한다. 이를 위해서 추론 기관은 n2 의 상태를 IN 으로 변경한다. 그러나 이는 모순을 일으키고, 따라서, 다음의 노드를 생성하게 된다.

모순은 이제 진리값 추론 시스템에서 의존성을 이용한 역행 프로시쥬어를 가동시켜서 위반되는 가정을 찾는다. 이런 노드는 단지 n1 하나뿐이므로, 철회는 곧장 이루어진다. 이것에 대해서, 진리값 유지 시스템은 CP 정당성을 이용해서 "nogood" 노드를 생성한다.

불일치를 없애기 위해서, 진리값 유지 시스템은 다음으로 n5 를 다음과 같이 정당화함으로써 n2 를 IN 노드로 만든다.

이것은 차례로 n1 을 OUT 으로 만든다 (가정에서 n1 은 하나의 차있는 out-list 를 가지기 때문) . 또한, n4 가 n1 에 의하여 정당화되었으므로 이것 역시 OUT 이 되어야 한다. 이것은 다음과 같은 노드 집합을 제공한다.

CP 정당성은 "nogood" 노드를 위하여 n2 의 원형관계 (cirular relation) 를 방지하기 위해서 필요했다는 것을 주의하라. 만약 n5 를 위해서 in-list 정당성에 n4 노드가 있는 지원 리스트 (support list) 를 사용했다면, n5 는 n4 이후에는 OUT 이 되었을 것이고, 다시 n2 를 OUT 으로 만들게 된다.

CP 를 다루는 프로시쥬어는 꽤 복잡하고, 이들은 주로 지원 리스트로 바뀌기 때문에, 여기서는 이들의 주요 기능만 다룬다. 좀더 상세한 설명을 위해서는 Doyle (1979) 을 보라.

여기서는 간단히 JTMS 에 대해서만 다루었는데, 이것이 가장 간단하고 광범위하게 사용되기 때문이다. 이런 유형의 TMS 는 또한 비단조 TMS (NMTMS) 로 알려져 있다. JTMS 의 결점을 보충하고 다른 요구 사항을 충족시키기 위하여 여러 다른 유형이 개발되었다. 이들은 논리-베이스 TMS (LTMS) , 가정-베이스 TMS (ATMS) , 기타 (de Kleer, 1986a and 1986b) 가 있다.

* 「인공지능개론」김영렬, 김우성, 김정규, 박용범, 정목동, 1993, Introduction to Artificial Intelligence and Expert Systems, Dan W. Patterson 1990.