[AI]Logical Reasoning/Logical Inference

Logical Reasoning(Entailment)

 

Entailment란 하나가 참인 world에서 다른 하나가 참임이 entail 되는 것을 의미한다.

the sentence A entails the sentece B라고 표현하는데

A가 true인 모델 M에서 B가 항상 true가 된다는 것이다. 

 

기호로 표현 하면 밑의 그림과 같고 아래 의미는 beta 로부터 alpha가 entail 된다는 것이다.

beta가 보다 구체적인 많은 경우의 Possible world를 가지는 것이다.

 

예시는 아래 그림과 같다.

 

 

Wumpus World에 대해선 어떠한지 알아보자.

 

이전 글에서 한칸 움직인 상황에서 가능한 Possible world가 8가지 있다고 했고 그 경우 대해서 적용해보자.

 

 

이때 KB = wumpus-world rules + observation이다. wumpus-world의 규칙과 관찰로 판단되는 경우는 3가지 뿐인 것이다.

 

그럼 여기서 새로운 set of senteces 를 만들어보자

 

새로운 sentences 를 a1이라고 했을 때 a1이 KB를 포함하고 있으므로 a1이 KB를 entail 한다고 판단이 가능하다.

 

그렇다면 이경우는 어떨까 a2가 KB를 모두 포함하고 있지 않으므로 entail 한다고 할 수 없다.

 

Logical Inference

Logic inference : KB가 a를 entail 하는지 안하는지 어떻게 결정하느냐 

 

즉 Entailment 를 찾아내는 알고리즘을 의미한다.

아래 그림과 같은 기호로 표현되고 의미는 sentence alpha가 KB로부터 i 과정에 의해 유도되었다는 것을 의미한다.

그 과정 중 하나가 Model checking이라고 하며 all possible models를 세며 true인지 check 하는 과정이다.

inference algorithm i 가 KB로부터 alpha를 derive 할수 있음 이라는 의미인 것이다.

 

Entailment vs Inference

entailment A 라는 것은 기존 KB로부터 추론될 수 있는 true sentence를 말하는 것이고

Inference는 어떠한 알고리즘에 의해 위의 entailment A를 찾아내는 알고리즘이라고 보면된다.

 

Soundness, Completeness

어떤 알고리즘에 대해 soundness, completeness라는 특성이 있다고 말을 하는데

soundness란 algorithm이 entailed sentence만을 derive 하는, 맞는 것만 유도하면 해당 알고리즘은 sound 하다 라고 말을한다.

이는 맞는 것을 다 찾을 필요는 없다는 것이고 찾은 것이 모두 맞기만 하면 되는 경우이다.

 

completeness란 algorithm이 모든 true sentence들은 inference 할 수 있느냐 하는 특성인데 이말인 즉슨 entail된 모든 sentence를 derive 할 수 있으면 completeness하다고 말을한다. 결국 entail 한 모든 sentence만 찾으면 되므로 그 것 이외의 다른 것을 찾아도 괜찮다는 것이다.