역방향 체인

Backward chaining
후방 체인(적용된 행동 분석) 또는 후방 체인과 혼동하지 마십시오.

역방향 체인(또는 역방향 추론)은 구어적으로 목표로부터 역방향으로 작용하는 것으로 묘사되는 추론법이다. 자동화된 정리 추진기, 추론 엔진, 증명 보조기, 그리고 다른 인공지능 어플리케이션에 사용된다.[1]

게임 이론에서, 연구자들은 그것을 게임의 해결책을 찾기 위해 서브게임에 적용하는데, 이것은 역유도라고 불리는 과정이다. 체스에서는 역행 분석이라고 하며, 컴퓨터 체스의 체스 엔딩을 위한 테이블 베이스를 생성하는 데 사용된다.

후방 체인은 SLD 분해능에 의한 로직 프로그래밍에서 구현된다. 두 규칙 모두 추론법칙에 기초한다. 그것은 추론 규칙과 논리적 함의를 가지고 가장 일반적으로 사용되는 두 가지 추론 방법 중 하나이다. 다른 하나는 전진 체인이다. 후진 체인 시스템은 보통 깊이 우선 검색 전략을 사용한다. 예를 들어 Prolog.[2]

작동 방식

역방향 체인은 목표(또는 가설)의 목록으로 시작하여 결과에서 선행자까지 거꾸로 작용하여 데이터가 이러한 결과 중 하나를 지원하는지 여부를 확인한다.[3] 역방향 체인을 사용하는 추론 엔진은 원하는 목표와 일치하는 결과(다음 조항)를 찾을 때까지 추론 규칙을 검색할 수 있다. 만약 그 규칙의 선행(만약의 조항)이 사실이라고 알려지면, 그것은 목표 목록에 추가된다(자신의 목표가 확정되려면 이 새로운 규칙을 확인하는 자료도 제공해야 한다).

예를 들어, 새로운 애완동물인 프리츠가 프리츠에 대한 두 가지 사실과 함께 불투명한 상자에 담겨 있다고 가정하자.

  • 프리츠가 울다.
  • 프리츠는 파리를 먹는다.

다음 4가지 규칙을 포함하는 규칙 기반을 바탕으로 프리츠가 녹색인지 여부를 결정하는 것이 목표다.

An Example of Backward Chaining.
역방향 체인의 예.
  1. 만약 X가 크로와 X가 파리를 먹는다면 – 그렇다면 X는 개구리 입니다.
  2. X가 짹짹거리고 X가 노래하면 X는 카나리아다.
  3. X가 개구리라면 X는 녹색이다.
  4. X가 카나리아인 경우 – X가 노란색인 경우

역추론 엔진은 프리츠가 녹색인지 여부를 4단계로 판단할 수 있다. 우선, 이 질문은 "프리츠는 녹색이다"라는 것을 증명해야 할 목표 주장으로 표현된다.

1. 프리츠는 규칙 #3에서 X를 대신하여 결과물이 골과 일치하는지 확인하므로 규칙 #3은 다음과 같이 된다. 

 프리츠가 개구리라면 – 프리츠는 녹색이다.

결과적으로 골("Fritz is green")과 일치하기 때문에, 규칙 엔진은 선행("Fritz is a frog")이 증명될 수 있는지 여부를 확인해야 한다. 그러므로 선행자는 새로운 목표가 된다. 

 프리츠는 개구리

2. 다시 프리츠를 X로 대체하면 규칙 #1은 다음과 같이 된다. 

 프리츠가 으르렁거리고 프리츠가 파리를 먹는다면 – 프리츠는 개구리 입니다.

그 결과 현재의 목표("Fritz는 개구리")와 일치하기 때문에, 추론 엔진은 선행("Fritz는 으르렁거리고 파리를 먹는다")이 증명될 수 있는지 확인할 필요가 있다. 그러므로 선행자는 새로운 목표가 된다. 

 프리츠가 으르렁거리고 프리츠는 파리를 먹는다.

3. 이 목표는 두 개의 문장이 결합된 것이기 때문에 추론 엔진은 그것을 두 개의 하위 골로 나누는데, 이 두 가지 모두 증명되어야 한다. 

 프리츠 사기꾼 프리츠는 파리를 먹는다.

4. 이러한 두 가지 하위 목표를 모두 증명하기 위해 추론 엔진은 이 두 하위 목표가 모두 초기 사실로서 주어졌다고 본다. 따라서 연결은 다음과 같다. 

 프리츠가 으르렁거리고 프리츠는 파리를 먹는다.

따라서 규칙 #1의 선행은 참이며 그 결과는 참이어야 한다. 

 프리츠는 개구리

따라서 규칙 #3의 선행은 참이며 그 결과는 참이어야 한다. 

 프리츠는 초록색이다.

그러므로 이러한 파생은 추론 엔진이 프리츠가 녹색이라는 것을 증명할 수 있게 한다. 규칙 #2와 #4는 사용되지 않았다.

목표는 항상 확인된 의미 결과 버전과 일치하며(모더스 요금에서와 같이 부정된 버전은 아님), 그 이전 버전은 새로운 목표로 간주된다(결과에 대해 긍정하는 결론은 아님). 이는 궁극적으로 알려진 사실과 일치해야 한다(일반적으로 개미의 결과로 정의됨).추론은 항상 진실이다) 따라서, 사용된 추론 규칙은 모드스 폰이다.

목표 리스트는 어떤 규칙을 선택하고 사용하는지를 결정하기 때문에, 이 방법을 데이터 중심의 전진 체킹 추론과는 대조적으로 목표 중심이라고 한다. 역방향 체인 접근방식은 전문가 시스템에 의해 채택된다.

Prolog, Knowledge Machine 및 ECLiPSe와 같은 프로그래밍 언어는 추론 엔진 내에서 역방향 체인을 지원한다.[4]

참고 항목

참조

  1. ^ Feigenbaum, Edward (1988). The Rise of the Expert Company. Times Books. p. 317. ISBN 0-8129-1731-6.
  2. ^ Michel Chein; Marie-Laure Mugnier (2009). Graph-based knowledge representation: computational foundations of conceptual graphs. Springer. p. 297. ISBN 978-1-84800-285-2.
  3. ^ 깊이 우선 검색 방법으로 역방향 체인을 정의:
  4. ^ 이전 체인을 지원하는 언어:

외부 링크