인공지능(AI) #7_ 전방 연쇄(Forward chaining), 후방 연쇄(Backward chaining)

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

---

1. 전방 연쇄(Forward chaining)

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

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

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

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

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

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

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

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

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

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

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

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

2. 후방 연쇄(Backward chaining)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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