TigerCow.Door


안녕하세요. 이번 포스팅에서는 전방 연쇄(Forward chaining)와 후방 연쇄(Backward chaining)에 대해서 알아보겠습니다. 


1. 전방 연쇄(Forward chaining)


먼저 전방 연쇄란, 기존의 알려진 사실들로 하여금 새로운 사실을 추리하면서 나아가는 방법입니다. 이름처럼 원래 알고 있는 것을 바탕으로 앞으로 나아가는 방법이죠. 즉, 한 문장, 함의에 대한 모든 전제가 알려져 있는 사실이라면 그것에 대한 결론을 새로운 사실로써 지식기지에 추가합니다.


예를 들어, A라는 사실과 B라는 사실을 알고 있을 때, 지식기지에 AB=>C 가 있다면 C를 하나의 사실로써 추가할 수 있습니다.

이러한 과정을 통해 알고자 하는 사실 Q에 도달하거나 더 이상 추리가 불가능 할때 까지 반복합니다.

아래의 알고리즘을 살펴보면 전방연쇄가 선형시간으로 실행되는 것을 확인할 수 있습니다.



전방연쇄는 위에서 언급한 바와 같이 진행되며 이를 보면 연역법과 비슷하다는 것을 알 수 있습니다.

이러한 전방연쇄는 건전하며 완결적입니다.

전방연쇄가 건전하다는 것은 쉽게 확인할 수 있는데, 모든 추리는 본질적으로 전건 긍정의 적용이기 때문입니다.

그리고 함축된 원자적 문장들이 모두 유도되기 때문에 완결적임을 알 수 있습니다.

전방연쇄를 아래 그림을 통해 확인하면 보다 쉽게 이해할 수 있습니다.



위의 그림에서 알려진 사실들은 A와 B입니다. 그리고 그래프는 AND-OR 그래프로써 여러 링크가 하나의 호로써 결합된 것은 AND, 논리곱을 의미하며 여러 링크가 호 없이 결합된 것은 OR, 논리합을 의미합니다. 논리곱을 증명하기 위해서는 연결된 모든 링크가 증명해야 하며 논리합에 대해서는 최소 하나의 링크가 참일때 참을 알 수 있습니다.

그림에 대한 이해를 해본다면, 먼저 알려진 사실 A와 B를 통해 AB=>L 에서 L이라는 사실을 추가합니다. 그리고 BL=>M

을 통해 M이라는 사실을 추가하고 이어서 LM=>P를 통해서 P라는 사실을 추가합니다. 그리고 P=>Q를 통해 Q라는 사실 또한 추가할 수 있습니다.



2. 후방 연쇄(Backward chaining)


이번에는 후방 연쇄(Backward chaining)에 대해서 알아보겠습니다. 후방연쇄는 그 단어에서도 알 수 있듯이 먼저 확인하고자 하는 사실 Q로부터 시작하여 Q를 사실로써 추가하기 위해 지식기지에서 결론이 Q인 함의, 문장을 찾습니다.

예를 들어, Q라는 사실을 확인하고자 하고 지식 기지에 MN=>Q 이 있다면 이제 우리는 각각 M, N에 대해서 동일하게 후방 연쇄를 진행합니다. 그리고 원래 알고 있던 사실, A와 B에 도달 했을 때 그 반복을 멈추게 됩니다.




전방연쇄에서 사용되었던 예시를 통해 후방 연쇄의 과정을 살펴보겠습니다.

먼저 Q라는 사실을 확인하려고 합니다. 지식기지에 P=>Q가 있으므로 우리는 P에 대한 후방연쇄를 진행합니다.

그리고 지식기지에 LM=>P가 있으므로 다시 L와 M에 대해서 후방연쇄를 진행합니다.

먼저 L에 대해서 진행하면, 지식기지에 AP=>L과 AB=>L이 있습니다. 이때 A와 B는 우리가 미리 알고있는 사실이기 때문에 L에 대한 후방연쇄는 AB=>L을 통해서 증명됩니다.

그리고 이제 M에 대해서 후방연쇄를 진행하면, 지식기지에서 BL=>M을 확인하고 B는 우리가 이미 알고 있는 사실이며 L은 방금 위에서 후방연쇄를 통해 추가된 사실이기 때문에 M 또한 후방연쇄를 통해 사실로써 추가합니다.

그럼 다시 LM=>P가 후방연쇄를 통해 P가 사실로써 추가될 수 있으며, P=>Q 또한 후방연쇄를 통해 증명되었기에 Q를 사실로써 추가할 수 있습니다.

이러한 후방 연쇄의 효율적인 구현은 선형 시간으로 전방 연쇄와 같습니다.


헌데 후방 연쇄는, 목표 지향적 추론(goal-directed reasoning)의 한 형태로써 종종 후방 연쇄의 비용이 지식 기지 크기의 선형적인 시간보다 훨씬 적을 수 있습니다. 그 이유는, 후방 연쇄가 추론 과정에서 오직 유관한 사실들만 확인하기 때문입니다.




전방 연쇄와 후방 연쇄에 대해 비교한다면,


전방연쇄는 기존의 사실들로써 과정을 시작하는, data-driven 입니다.

반대로 후방연쇄는 확인하고자 하는 목표부터 과정을 시작하는, goal-driven 입니다.

후방 연쇄에서의 설명처럼, 후방연쇄는 해결하고자 하는 문제, 확인하고자 하는 목표에 대해 유관한 것들만 접근하게 되므로 그 복잡도가 지식기지에 있는 크기의 선형시간보다 훨씬 작을 수 있습니다.


이렇게 해서 전방 연쇄(Forward chaining)와 후방 연쇄(Backward chaining)에 대해서 알아보았습니다.

추가적으로 궁금하신 점이나 내용에 대한 피드백은 언제나 댓글을 이용해주세요 :)


블로그 이미지

Tigercow.Door

Back-end / Python / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요