TigerCow.Door


안녕하세요.

이번 포스팅부터는 1차 논리(first-order logic)에 대해서 살펴봅니다.


우리는 지난 포스팅에서 명제논리를 사용하여 지식 기반 에이전트가 자신이 속한 세계를 표현하는 방법과 다음에 취할 동작을 연역하는 방법을 살펴보았습니다. 하지만 명제논리는 복잡한 환경에 대한 지식을 간결하게 나타내기에는 표현력이 너무 약합니다. 따라서 우리는 이번 포스팅 부터하여 우리가 가진 상식의 상당 부분을 표현하기에 충분한 표현력을 가진 1차 논리(first-order logic)에 대해서 살펴보겠습니다.


1. 1차 논리(First-order logic)


1차 논리에서는 명제 논리의 장점, 문맥 독립적이고 모호하지 않은 선언적, 조합적 의미론을 기반으로 삼고 자연어의 단점들은 제외하고 표현력이 큰 착안들만 가져왔습니다. 

1차 논리에서는 다음과 같은 것들을 포함합니다.


- 객체(Objects): 사람, 집, 수, 이론, 색, 야구, 전쟁, 세기, ...

- 관계(Relations): 빨갛다. 둥글다, 가짜, 다층, ... / 형제이다, ~보다 크다, ~안에, ~의 일부, ...

- 함수(Functions): ~의 아버지, ~의 절친, ~보다 하나 많다, ~의 시작, ...


1차논리의 언어는 객체들과 관계들을 중심으로 구축됩니다.

명제 논리와 1차 논리의 주된 차이점은 두 언어의 존재론적 함의(ontological commitment)사이에 놓여 있습니다. 즉, 둘은 현실의 본성에 대해 무엇을 가정하는지와 관련해서 크게 다릅니다.

명제 논리에서는 어떤 세계에서 성립하거나 성립하지 않는(그러나 둘 다는 아닌) 사실들이 존재합니다.

하지만 1차 논리는 더 많은 것을 가정합니다. 구체적으로, 1차 논리는 객체들로 세상이 구성되며 그 객체들 사이에는 성립하거나 성립하지 않는 관계들이 있습니다.


논리들을 인식론적 함의(epistemological)로써도 바라볼 수 있습니다.

이는 각 사실에 관해 허용되는 가능한 지식 상태가 얼마나 많은지에 관련된 것입니다. 명제논리와 1차 논리에서는 하나의 문장이 하나의 사실을 표현하며, 에이전트는 그 문장이 참이라고 믿거나 아니면 거짓이라고 믿거나 아니면 아무런 의견이 없습니다.


아래 표는 다섯가지 논리의 존재론적 함의와 인신론적 함의를 정리한 것입니다.




2. 기호와 해석


1차 논리의 기본적인 구문 요소는 객체와 관계, 함수를 나타내는 기호들 입니다. 따라서 기호들은 총 세가지로 나뉘게 됩니다.

- 객체를 나타내는 상수 기호(Constant symbol)

- 관계를 나타내는 술어 기호(Predicate symbol)

- 함수를 나타내는 함수 기호(Function symbol)



3. 항(Term)


항(term)이란 하나의 객체를 지칭하는 논리식입니다. 따라서 상수 기호는 항입니다.

예를 들어, LeftLeg(John)이라는 것이 있을 때 John을 하나의 항이라고 합니다.

특별히 위의 예시와 같은 경우는 복합항이라고 하는데, 하나의 함수 기호와 그 함수 기호에 대한 인수로서의 항들을 감싼 괄호쌍으로 구성됩니다. 복합항또한 하나의 이름일 뿐임을 기억해야 합니다.



4. 원자적 문장(Atomic sentences)


객체들을 지칭하는 항들과 관계들을 지칭하는 술어 기호들이 갖추어졌다면, 그 둘을 조합해서 원자적 문장(atomic sentences)를 만들 수 있습니다. 원자적 문장은 술어 기호가 반드시 하나 있어야 하며, 그 뒤에 괄호로 감싼 항들이 올 수도 있는 형태입니다. 원자적 문장의 인수가 복합항일수도 있습니다.


주어진 모형 안에서, 원자적 문장의 술어 기호가 지칭하는 관계가 그 인수들이 지칭하는 객체들 사이에서 성립하면 그 원자적 문장은 참입니다.


그리고 이러한 원자적 문장들을 논리 접속사들을 이용하여 좀 더 복합적인 문장을 만들 수 있습니다. 그리고 그러한 문장을 복합문장(complex sentences)이라고 합니다.



5. 전칭 한정사(Universal quantification)


어떤 논리가 객체들을 지원할 때, 객체들이 가진 속성을 그 객체들의 이름으로 일일이 열거하지 않고 간결하게 표현하는 용도로 한정사가 사용됩니다. 한정사에서는 크게 전칭 한정사(Universal quantification)과 존재(existential) 한정사가 존재합니다. 먼저 전칭 한정사에 대해서 살펴보겠습니다.


먼저 하나의 예시를 들어보겠습니다. 다음의 문장은, '모든 왕은 사람이다'를 의미합니다.


편의를 위해 전칭 한정사를 A로 표현하겠습니다.(원 표기는 위 문장의 표기가 맞습니다.)

보통의 경우 A는 "모든 ~에 대해"라고 읽습니다. 따라서 위의 문장은, "모든 x에 대해, 만일 x가 왕이면 x는 사람이다."라는 뜻입니다.

전칭 한정사의 경우 논리곱을 사용하는 데에 있어서 주의를 기울여야 합니다.

예를 들어, 책을 보는 사람은 모두 똑똑하다를 나타내면,

Ax readBook(x) => smart(x)

입니다. 하지만, 

Ax readBook(x) ∧ smart(x)

와 같이 나타내면, 우리가 의도했던 바와 달리, 세상에 존재하는 모든 것이 smart 하게 됩니다.

다시말해, 아래의 문장은, 모든 사람은 책을 읽고 모든 사람은 똑똑하다라는 의미를 나타냅니다.



6. 존재 한정사(Existential quantification)


전칭 한정은 모든 객체에 대한 주장을 표현합니다. 이와 달리 존재 한정은 일부 객체들에 대한 주장을 표현합니다.

예들 들어 다음과 같이 사용됩니다.


편의를 위해 존재 한정사를 E로 표현하겠습니다.(원 표기는 위 문장의 표기가 맞습니다.)

보통 Ex는 "~를 만족하는 x가 존재한다.'로 읽거나 "어떤 x에 대해 ~" 라고 읽습니다.

직관적으로 말해, Ex P 라는 문장은 P가 적어도 하나 이상의 x에 대해 참임을 말합니다.

존재 한정사에서도 주의할 점이 있습니다.

예를 들어, 책을 읽고, 똑똑한 누군가가 존재한다를 나타내면,

Ex readBook(x) ∧ smart(x)

입니다. 하지만,

Ex readBook(x) => smart(x)

와 같이 나타내면, 책을 읽는 누군가가 한명이라도 존재하면 문장이 참이 됩니다.



7. 한정사의 중첩


한정사를 중첩하여 사용할 때는 그 의미를 위해 주의를 기울여야 합니다.

Ax Ey Loves(x,y)

는 모든 사람은 누군가를 사랑한다라는 의미이지만,

Ex Ay Loves(x,y)

는 모두가 사랑하는 사람이 있다라는 의미이기 때문입니다.


따라서 한정사에 있어서는 교환법칙이 성립되지 않습니다.



이후 내용에 대해서는 다음 포스팅부터 진행하도록 하겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요. 이번 포스팅에서는 전방 연쇄(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

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요.

이번에는 분해(resolution) 증명에 대해서 알아보도록 하겠습니다.

분해 증명에 대해 이해 하기 위해, 분해(resolution), 논리곱 표준형(CNF: Conjunctive Normal Form), 분해 알고리즘에 대해서 함께 알아보겠습니다.


1. 분해(Resolution)


우리는 앞의 포스팅들에서 증명을 이끌어 내는데 사용할 수 있는 추리규칙에 대해서 알아보았습니다.

그러한 추리규칙들이 건전하다. 올바르다라는 점을 함께 알아보았지만 아직 부족한 한가지는, 그러한 추리규칙들을 사용하는 추리 알고리즘이 완결적인지 알아보지 않았습니다. 여기서 완결적이라는 것은, 해당 알고리즘이 도달 가능한 목표가 존재할 때, 그것을 반드시 찾아낼수 있는가에 대한 것입니다.


따라서 이번에는 분해(Resolution)라는 추리규칙을 알아보는데, 이러한 규칙을 완결적 검색 알고리즘과 함께 사용하면 완결적인 추리 알고리즘이 도출되는 것을 함께 보도록 하겠습니다.


먼저 지금까지 다루고 있던 웜푸스 세계에 분해 규칙을 바로 적용해보도록 하겠습니다.

다음 과정에서는 분해 규칙이 어떻게 사용되는지를 보여주니 간단하게 보시면 되겠습니다.

아래의 그림에서 7.4(a)에 도달하는 단계에 대해서 생각해보겠습니다.



즉, 현재 에이전트는 [2,1]에서 [1,1]로 돌아와서 [1,2]로 가고 거기서 악취(S)를 지각하지만 미풍(B)은 지각하지 않습니다.

이를 위해 우리는 지식기지에 다음과 같은 사실을 추가합니다.


R11: ~B12

R12: B12 <=> (P11 v P22 v P13)


이렇게 두개의 사실관계를 추가하면 지금까지의 지식기지는 아래와 같습니다.

   R1 : 


   R2 : 

   R3 : 


   R4 : 

   R5 : 


출처: http://doorbw.tistory.com/55?category=684964 [Tigercow.Door]


R6 : 

R7 : 


R8 : 

R9 : 

R10 : 


출처: http://doorbw.tistory.com/55?category=684964 [Tigercow.Door]


R11: ~B12

R12: B12 <=> (P11 v P22 v P13)


R1~R10에 대한 설명은 출처를 참고하시길 바랍니다.

우리는 R10을 도출했던 방식과 같이, 아래의 방식으로 [2,2]와 [1,3]에 구덩이가 없다는 것을 알 수 있습니다.


먼저 R12에서 상호조건 소거를 적용하여, (P11 v P22 v P13) => B12를 얻을 수 있습니다.

그리고 대우명제 법칙을 적용하면, ~B12 => ~(P11 v P22 v P13) 을 얻을 수 있습니다.

이후 R11으로 전건긍정을 적용하면 ~(P11 v P22 v P13) 을 얻을 수 있으며 마지막으로 이것에 드모르간 법칙을 적용하면 ~P11과 ~P22, ~P13이라는 사실을 얻을 수 있습니다.


~P11은 이미 에이전트가 알고있기 때문에 따로 지식기지에 추가하지 않고, ~P22와 ~P13을 지식기지에 추가합니다.

R13: ~P22

R14: ~P13


이제 R3에 상호조건 소거를 이용해 다음을 얻습니다.

B21 => (P11 v P22 v P31) 그리고 R5로 전건긍정을 적용하여 다음의 사실을 지식기지에 추가할 수 있습니다.

R15: P11 v P22 v P31


이제 분해규칙을 사용합니다.

R13의 리터럴, 즉 R13의 사실 ~P22과 R15의 리터럴 R22을 분해하면 다음과 같은 분해식(Resolvent)을 얻을 수 있습니다.

R16: P11 v P31


이를 표현하면, 만일 [1,1]이나 [2,2], [3,1] 중 하나에 구덩이가 있고 [2,2]에 구덩이가 존재하지 않다면 [1,1]이나 [3,1] 중에 구덩이가 있다라고 표현할 수 있습니다.


그리고 또 한번 분해규칙을 사용합니다. R1의 리터럴 ~P11과 R16의 리터럴 P11을 통해 다음과 같은 사실을 알 수 있습니다.

R17: P31


이를 표현하면 만일 [1,1]이나 [3,1] 중 하나에 구덩이가 있고 [1,1]에 구덩이가 존재하지 않다면 [3,1]에 구덩이가 존재한다라고 표현할 수 있습니다.


위의 과정에서 마지막 부분에 두 번의 분해규칙 추리가 이용되었습니다.

이러한 단계는 이제 소개해드릴 단위 분해(unit resolution) 추리 규칙의 예시 입니다.



여기서 각 l을 리터럴이라고 합니다. 그리고 li와 m은 서로 상보 리터럴(complementary literal)입니다. 즉 하나가 다른 하나의 부정인 리터럴입니다. 분해 규칙을 정리해보자면, 절(clause, 리터럴 들의 논리합) 하나와 리터럴 하나(또는 또다른 절에서의 리터럴)로부터 새로운 절을 산출하는 것입니다.

단위 분해 규칙을 다음과 같은 완전한 분해 규칙으로 일반화 할 수 있습니다.



위의 식에서 li와 mj는 서로 상보 리터럴들입니다. 이식에서 분해가 두 개의 절을 취해서 두 절의 리터럴 중 서로 상보인 리터럴들을 제외한 모든 리터럴을 담은 하나의 새 절을 산출할 수 있습니다.

다음과 같이 예를 들 수 있습니다.



좌측의 절에서 P11이라는 리터럴과 우측의 절에서 ~P12라는 리터럴은 서로 상보리터럴입니다.

따라서 이를 제외환 새로운 절, P31 v ~P22를 얻을 수 있습니다.


분해규칙에서는 인수분해(factoring)이라는 추가적인 행동이 필요합니다.

인수분해란, 리터럴의 중복된 복사본들을 제거하는 것입니다. 예를 들어 (A v B)를 (A v ~B)로 분해하면 (A v A)가 나오는데 이는 인수분해를 통해 하나의 A로 축약될 수 있습니다.


분해규칙의 건전성은 다른 절의 리터럴 mj에 상보적인 리터럴 li를 생각해보면 쉽게 확인할 수 있습니다.

분해 규칙에서 더 놀라운 사실은, 이것이 완결적인 추리 절차들이 속한 모임의 기저를 형성한다는 점입니다. 분해 기반 정리 증명기는 명제 논리의 임의의 문장 a 와 b에 대해 a|=b의 진리를 결정할 수 있습니다. 분해가 이를 어떻게 달성하는지 함께 알아보겠습니다.



2. 논리곱 표준형(CNF: Conjunctive Normal Form)


분해 규칙은 절에만 적용되는 것을 보았습니다. 즉 절들로 이루어진 지식기지와 질의에만 유관한 것으로 보입니다. 그렇다면 우리는 분해규칙으로 모든 명제 논리를 위한 완결적인 추리 절차를 얻을 수 있을까요?

그 답은, 모든 명제 논리 문장은 절들의 논리곱과 논리적으로 동치라는 것입니다.

절들의 논리곱 형태로 이루어진 문장을 가리켜 우리는 논리곱 표준형(CNF)이라고 합니다.

그럼 문장을 CNF로 변환하는 절차를 함께 보도록 하겠습니다.


B11 <=> (P12 v P21) 이라는 문장을 CNF로 변환합니다.


1. <=>을 소거합니다. 즉, a<=>b 를 (a=>b)∧(b=>a) 으로 대체합니다.

(B11 => (P12 v P21)) ∧ ((P12 v P21) => B11)


2. =>를 제거합니다. 즉, a=>b를 ~a v b로 대체합니다.

(~B11 v (P12 v P21)) ∧ (~(P12 v P21) v B11)


3. CNF에는 ~이 리터럴에만 있어야합니다. 이를 위해 아래의 세개 방식 중 적절한 것을 적용하여 ~을 괄호 안으로 옮깁니다.



지금의 예에서는 세번째 규칙을 한번만 적용하면 됩니다.

(~B11 v P12 v P21) ∧ ((~P12 ∧ ~P21) v B11)


4. 이제 ∧, v 연산자와 리터럴들로 이루어진 부분들이 중첩된 형태의 문장이 나왔습니다. 이제 분배법칙을 적용해서 v를 ∧에 대해 적절히 분배합니다.

(~B11 v P12 v P21) ∧ (~P12 v B11) ∧ (~P21 v B11)


이렇게 해서 원래의 문장이 세개의 절의 논리곱 형태로 된 CNF로 변환되었습니다.

이전보다 언어로써 표현하기는 힘들지만 완결적인 분해 절차의 입력으로써 사용될 수 있습니다.



3. 분해 알고리즘(Resolution algorithm)


분해 규칙에 기초한 추리 절차들은 이전 포스팅에서 소개드렸던 귀류법(모순에 의한 증명)의 원리를 이용합니다.

즉, (KB∧~a)가 만족 불가능임을 보임으로써 KB|=a가 참임을 증명합니다.

분해 알고리즘은 다음 사진과 같습니다.



위의 알고리즘은 우선 (KB∧~a)를 CNF로 변환합니다. 그리고 그 CNF의 절들에 대해서 분해 규칙을 적용합니다. 상보 리터럴을 담은 각 쌍을 분해해서 제외한다음 새 절을 산출하고 그것을 절들의 집합에 추가합니다. 절들의 집합에는 중복이 허용되지 않습니다. 그러한 과정을 반복하면서 다음 두 조건 중 하나가 만족할 때 결과를 출력합니다.


- 추가할 수 있는 새로운 절이 더이상 없다. 이 경우 KB는 a를 함축하지 않습니다.

- 두 개의 절이 빈 절로 분해된다. 이 경우 KB는 a를 함축한다.


이 때, 빈 절이라는 것은 성분이 하나도 없는 논리합으로써 False와 동치입니다. 즉, (KB∧~a)에 대해 False이기에 KB는 a를 함축하는 것입니다. P와 ~P처럼 서로 상보적인 단위 절을 분해한다면 빈 절이 발생합니다.


그럼 위의 분해 절차를 웜푸스 세계에 적용해 보도록 하겠습니다.

에이전트가 [1,1]에 있을 때에는 미풍을 지각하지 못합니다. 따라서 이웃 칸에는 구덩이가 있을 수 없습니다. 이를 나타내는 지식기지는 다음과 같습니다.


KB = R2 ∧ R4 = (B11 <=> (P12 v P21)) ∧ ~B11




이제 위의 지식기지를 통해 ~P12라는 문장 a를 증명하려고 합니다. (KB∧~a)를 CNF로 변환하면 위의 그림 중 상단의 4개의 절이 나옵니다. 그리고 그 아래의 절들은 상단 절들의 쌍들을 분해한 결과입니다. 그리고 P12과 ~P12 를 분해하면 빈 절이 나오게 됩니다 이를 통해 KB는 a, 즉 ~P12를 함축합니다.


이렇게 해서 분해라는 추리규칙과 논리곱 표준형, CNF를 중심으로 알아보았습니다.

다음 포스팅에서는 전방연쇄와 후방 연쇄에 대해 알아보도록 하겠습니다.

궁금하거나 내용에 대한 피드백언 언제든지 댓글을 남겨주세요.


블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요.

지난 포스팅에서는 명제 정리 증명에 있어서 필요한 몇가지 개념에 대해서 알아보았습니다.

이번에는 증명을 이끌어 내는데 사용할 수 있는 추리 규칙(Inference rule)에 대해서 알아보도록 하겠습니다.


1. 전건 긍정(Modus Ponens)


증명이라는 것은 어떤 원하는 목표로 향해가는 결론들, 문장들의 사슬입니다.

그러한 증명을 만들어 내는데 사용되는 가장 잘 알려진 규칙은 아래와 같이 표기하는 전건 긍정(Modus Ponens)입니다.



위의 표기는, 와  형태의 임의의 문장들이 주어졌을 때, 문장 를 추리할 수 있다는 것입니다.



2. 논리곱 소거(AND-elimination)


또 다른 유용한 추리규칙으로는 논리곱 소거(AND-elimination)이 있습니다.

논리곱으로 주어진 문장에서 임의의 논리곱 성분을 추리할 수 있음을 뜻하며 다음과 같이 표기합니다.



와 같은 논리곱 문장의 참(True) 또는 거짓(False)를 알고 있기 때문에, 임의의 논리곱 성분( 또는 ) 또한 알 수 있습니다.



3. 건전한 추리(Sound inference)


 와 의 가능한 진릿값들을 생각해본다면 전건 긍정과 논리곱 소거 모두 전적으로 건전한 추리임을 알수 있기 때문에, 위에서 알아본 두가지 추리규칙을 통해 전체적인 모형을 열거하지 않고도 건전한 추리를 이끌어 낼 수 있습니다.


지난 포스팅에서 모형점검방식으로 다루어 보았던 웜푸스 세계에 대해서 이 추리 규칙들과 동치들을 활용해보도록 하겠습니다.


- [1,1]에 구덩이가 없다.

   R1 : 


- 에이전트가 하나의 칸에 존재함 그 이웃칸에 구덩이가 있으면, 그리고 오직 그럴때에만 미풍을 지각할 수 있다.

   R2 : 

   R3 : 


- 앞의 문장들은 모든 웜푸스 세계에서 참이다. 이제 에이전트가 있는 특정한 세계에서 처음 방문한 두 칸에 대한 미풍 지각을 위한 문장들을 명시한다.

   R4 : 

   R5 : 


출처: http://doorbw.tistory.com/39?category=679148 [Tigercow.Door]


목표는 [1,2]에 구덩이가 없음을, 즉 가 참임을 증명하는 것입니다.


우선 R2에서 상호조건 소거를 적용하여 다음을 얻도록 합니다.

R6 : 


그리고 위에서 알아본 논리곱 소거를 이용해서 다음을 얻습니다.

R7 : 


이어서, R7에 대한 대우 명제를 통해 논리적 동치 명제를 얻습니다.

R8 : 


그리고 R8과 사전에 지식기지에 있던 R4로 전건 긍정을 적용하여 다음을 얻을 수 있습니다.

R9 : 


그리고 드모르간 법칙을 적용하여 다음과 같은 결론을 얻을 수 있습니다.

R10 : 


R10을 통해 [1,2]와 [2,1]에는 구덩이가 없다는 것을 알 수 있습니다.


이러한 증명을 손으로 직접 이끌어 내었지만, 임의의 검색 알고리즘을 이용해서 증명을 구성하는 일련의 단계들을 찾아내는 것도 가능합니다. 증명 문제를 다음과 같이 정의하기만 하면 됩니다.


초기상태(Initial-State) : 초기 지식 기반

동작들(Actions) : 추리 규칙의 상단 절반에 부합하는 모든 문장에 적용되는 모든 추리 규칙에 해당하는 동작들의 집합

결과(Result) : 한 동작의 결과는 문장을 추리 규칙의 하단 절반에 추가하는 것

목표(Goal) : 목표는 증명하고자 하는 문장을 담은 상태


즉, 증명을 찾는 것은 모든 모형들을 열거하는 방법의 한 대안입니다. 실제 문제들에서는 증명을 찾는 것이 더 효율적인 경우가 많은데, 이는 증명과 무관한 명제들은 무시할 수 있기 때문입니다.



4. 단조성(monotonicity)


논리 체계에서 마지막으로 살펴볼 것은 단조성(monotonicity)입니다. 이는 특정 지식기지에 정보, 문장이 추가된다면 이는 함축된 문장들의 집합이 항상 커지기만을 의미할 뿐이지, 추가된 것에 의해 이미 추리된 결론이나 기타 결론에 영향을 주지 않는다는 것입니다.

즉, 지식 기지에서 추리를 통해 얻어낸 결론 A가 존재할 때, 또 다른 단언 명제 B가 추가된다면 이는 추가적인 결론들을 이끌어내는데 도움이 될 수도 있겠지만, 이미 추리된 결론 A는 무효화되지 않습니다.

단조성을 통해 우리는 지식 기지에서 적절한 전제를 찾았다면 언제라도 추리 규칙들을 적용할 수 있음을 알 수 있습니다.

추리 규칙의 결론은 지식 기지에 있는 또 다른 지식과는 무관하게 옳아야 하기 때문입니다.


이렇게 하여 증명을 이끌어 내는 몇가지 추리규칙과 단조성에 대해서 알아보았습니다.

다음 포스팅에서는 분해증명에 대해서 알아보도록 하겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요. 문범우입니다.

이번 포스팅 부터 약 2~3번에 거쳐 명제 정리 증명에 대한 이야기를 해보겠습니다.

먼저 오늘은 정리 증명 알고리즘의 세부사항에 앞서, 함축과 관련된 몇가지 추가적인 개념을 알아보도록 하겠습니다.


1. 명제 정리 증명 개요


지난 포스팅을 통해 우리는 모든 모형들을 열거하면서 문장이 모든 모형에서 성립하는지 점검하는 모형 점검 방식에 대해 알아보았습니다. 이제는 정리 증명(Theorem proving)을 이용하여 함축 관계를 확인하는 방법에 대해서 알아보겠습니다. 우리가 앞으로 알아볼 접근 방식에서는 주어진 문장의 증명을 구축하여 함축관계를 확인하기 위해서 지식 기지(KB)에 있는 문장들에 여러가지 추리 규칙들을 적용할 것 입니다. 우리가 앞에서 살펴본 모형 점검 방식에 비해, 모형이 많을 수록 또는 정리 증명의 내용이 짧을 수록 보다 효율적인 증명 알고리즘이 될 것입니다.

그리고 먼저, 인사말에서 언급하였듯이 정리 증명 알고리즘의 세부사항에 앞서, 함축과 관련된 몇가지 추가적인 개념을 소개하겠습니다.



2. 논리적 동치(Logical equivalence)


논리적 동치(Logical equivalence)란, 두 문장 a와 b가 동일한 모형들에서 참일 때, 그 두 문장은 동치관계라고 하는 것 입니다. 즉, 논리적 동치라는 개념은 수학에서 항등식과 아주 비슷한 역할을 하는 것 입니다. 이러한 논리적 동치관계는 ab 라고 표기하기도 합니다. 

그리고 아래와 같이 정의할 수도 있습니다.


- 임의의 두 문장 a와 b는 만일 하나가 다른 하나를 함축하면, 그리고 오직 그럴 때에만 동치이다.

- 만일 이고 이면, 그리고 오직 그럴 때에만, a  b



3. 유효성(validity)


특정 문장을 유효한 문장이라고 할 때가 있습니다. 이때 말하는 '유효한'의 의미는, 모든 모형에서 참인 문장이라는 것입니다. 예를 들어, 이라는 문장은 유효한 문장입니다. P가 참인 문장일 때는 not P 가 거짓일 것이고, P가 거짓인 문장일 때는 not P가 참인 문장일 것 인데, 논리합(or)으로 연결된 복합문장이므로 해당 문장은 항상 모든 모형에서 참, 즉 유효한 문장입니다.

또한 유효한 문장을 동어반복(tautology)라고 말하기도 합니다. 동어반복은 필연적으로 참입니다.


앞에서 배운 논리적 동치라는 개념과 함께 생각해볼까요?

문장 True는 모든 모형에서 언제나 참이므로, 모든 유효한 문장, 동어반복은 True와 논리적 동치입니다.


이러한 개념이 왜 있을까요? 모든 모형에서 참이라는 문장, 즉 유효한 문장은 왜 필요할까요?

그 이유는 간단합니다.

유효한 문장을 통해서 함축의 정의에서 연역 정리(deduction theorem)을 이끌어 낼 수 있기 때문입니다.


연역 정리란,

임의의 문장 와 에 대해, 오직 가 유효할 때에만 이다.

라는 것입니다.


따라서 가 참인지 알아내려면, 1. 모든 모형에서 가 참인지 확인하거나, 2. 가 True와 동치임을 증명하면 됩니다.

반대로, 연역 정리는 모든 유효한 함의 문장이 적법한 추리를 서술한다라는 것을 말해 줍니다.



4. 만족 가능성(satisfiability)


마지막으로 알아볼 개념은 만족 가능성(satisfiability) 이라는 것 입니다. 주어진 문장이 참이 되는 모형이 존재하면, 다시말해서 주어진 문장을 만족하는 모형이 존재하면, 그 문장은 만족 가능한 문장입니다. 즉 모든 모형 중에서 하나 이상의 모형이 주어진 문장을 만족했을때 그 문장은 만족 가능하다라고 말합니다.

만족 가능성은 문장을 만족하는 모형이 하나이상 나올 때 까지 모든 가능한 모형들을 확인합니다.

이러한 만족 가능성이라는 개념은 위에서 알아본 유효성 개념과 많은 관계를 가지고 있습니다.

예를 들어, A라는 문장은 오직 not A가 만족 불가능일 때에만 유효한 문장입니다. 또한 그 대우(contrapositive) 또한 역시 참입니다. 이를 바꿔말해서, A라는 문장은 not A가 유효하지 않을 때에만 만족 가능한 문장입니다.

그리고 아래와 같은 관계도 존재합니다.

가 만족 불가능일 때에만 이다.

만족 불가능성을 확인해서 로 부터 를 증명하는 것은 수학의 표준적인 증명 방법인 귀류법(reductio ad absurdum: 불합리한 것으로의 환원)이라고 합니다.

또한 귀류법은 반박(refutation)에 의한 증명 또는 모순(contradiction)에 의한 증명이라고 부르기도 합니다.

귀류법에서는 일단 문장 가 거짓이라고 가정하고, 이후 이러한 가정이 알려져 있던 공리 에 대해서 모순임을 보입니다. 그리고 이러한 모순은 문장 가 만족 불가능이라고 말하는 것과 정확히 같은 의미입니다.


이렇게 해서 명제 정리 증명에 앞서 몇가지 세부적인 개념에 대해 알아보았습니다.

다음 포스팅에서는 증명을 이끌어 내는 데 사용할 수 있는 추리규칙들에 대해서 알아보겠습니다.





블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요. 문범우입니다.

이번포스팅에서는 명제 논리와 모형 점검 방식에 대해서 알아보도록 하겠습니다.


1. 명제 논리(Propositional logic)


1-1. 구문(Syntax)


명제 논리의 구문(syntax)은 허용되는 문장들을 정의합니다. 즉, 어떻게 문장을 구성해야 하는지를 이야기합니다.

하나의 문장, 원자적 문장(atomic sentence)은 하나의 명제 기호(proposition symbol)로 구성됩니다. 그리고 그러한 기호는 참(true)이거나 거짓(false)인 하나의 명제를 나타 냅니다. 예를 들어 P, Q, R, North 등이 명제 기호입니다.

이때, 항상 고정적 의미를 가진 명제가 있는데 자주 보셨듯이 True와 False 입니다. True는 항상 참인 명제이며 False는 항상 거짓인 명제입니다.

또한 우리는 간단한 문장들을 괄호와 논리 접속사(logical connective)로 연결해서 복합 문장을 만들 수 있습니다.

일반적인 접속사(연산자)는 아래와 같습니다.


 (부정)

부정(negation)이라고 부른다. 

리터럴(literal)은 원자적 문장 또는 원자적 문장의 부정인데, 전자를 긍정 리터럴(positive literal), 후자를 부정 리터럴(negative literal)이라고 부른다.

(논리곱)

논리곱 성분(conjunction) 이라고 부른다.

또는 연언문이라고 부른다.

(논리합)

논리합 성분(disjunction) 이라고 부른다.

또는 선언문이라고 부른다. 역사적으로는 '또는'을 뜻하는 라틴어 'vel'에서 비롯되었다.

(함의)

함의(implication) 또는 조건부 문장이라고 부른다.

또한 함의 문장을 규칙(rule)이나 if-then 문장이라고 부르기도 한다.

 (동치)

동치, 상호조건(biconditional)이라고 부른다.

문장들을 이러한 접속사(연산자)를 이용하여 복합 문장을 만들어 내면 그 또한 문장입니다.




1-2. 의미론(Semantics)


명제 논리의 구문을 살펴보았으니, 이제 명제 논리의 의미론을 살펴보도록 하겠습니다.

의미론(semantics)이란 특정 모형에 대한 문장의 진리를 결정하는 규칙들을 정의합니다. 명제 논리에서 모형은 모든 명제 기호의 진릿값(truth value), 즉 참(true) 또는 거짓(false)을 고정하는 역할만 합니다.


명제 논리의 의미론은 주어진 모형에 대해 임의의 문장의 진릿값을 계산하는 방법을 명시해야 합니다. 모든 문장은 원자적 문장과 위에서 본 다섯가지 접속사로 구성됩니다. 따라서 원자적 문장의 진릿값을 계산하는 방법과 각 접속사로 만들어지는 문장의 진릿값을 계산하는 방법을 명시해야 합니다.

원자적 문장에 대한 의미론은 다음과 같습니다.


- True는 모든 모형에서 참이고 False는 모든 모형에서 거짓이다.

- 다른 모든 명제 기호의 진릿값은 반드시 모형 자체에 명시되어 있어야 한다.


복합 문장에 대해서는 다섯 가지 규칙이 존재합니다.

이러한 규칙들은 임의의 모형 m 안의 임의의 문장 P와 Q에 대해 성립합니다.


P는 오직 m에서 P가 거짓일 때에만 참이다.

- P Q는 오직 m에서 P와 Q가 모두 참일 때에만 참이다.

- P Q는 오직 m에서 P 또는 Q가 참일 때에만 참이다.

- P Q는 m에서 P가 참이고 Q가 거짓이 아닌 한 참이다.

- P Q는 오직 m에서 P와 Q가 둘 다 참이거나 둘 다 거짓일 때에만 참이다.



이러한 규칙들은 복합 성분의 진릿값을 나열한 진리표(truth table)로 표현할 수 있습니다.



이러한 표를 이용하면 임의의 모형 m에 대한 임의의 문장 s의 진릿값을 간단한 재귀적 평가를 통해서 구할 수 있습니다.

즉, 아래와 같은 예시를 쉽게 참 또는 거짓을 구분할 수 있습니다.


논리곱, 논리합 등과 같은 논리 접속사에서는 일상적인 자연어로 이야기 할 때 다소 혼동되는 부분들이 있을 수 있습니다.

하나씩 살펴보도록 하겠습니다.


논리곱과 논리합, 부정의 진리표는 영어 문장에서의 해당 영어 단어 and, or, not의 의미를 잘 반영합니다. 그러나 헷갈리는 부분이 역시나 존재합니다.  라는 것은 P 또는 Q가 참일 때는 물론이고 둘 다 참일 때에도 참입니다. 하지만 단순히 or이라는 의미는 P 또는 Q가 참일 때 참이라는 의미만 가지고 있어서 헷갈릴 수 있습니다.

또한 이와는 다른 접속사인 '배타적 논리합(exclusive or, 줄여서 "xor")'은 두 논리합 성분이 모두 참일 때에는 거짓을 산출 합니다.

논리곱, 논리합, 부정은 크게 혼동되지는 않을 터이나 이제 설명드릴 함의와 같은 논리접속사에 대해서는 의미적으로 많은 혼동이 있을 수 있으니 천천히 이해하시길 바랍니다.


논리 접속사 (함의)에 대한 지리표는 언뜻 보면 "P가 Q를 함의한다" 또는 "만일 P이면 Q이다"라는 문장에 대한 우리의 직관적 이해와 잘 맞지 않는 것처럼 보입니다. 한 예시를 들어보도록 하겠습니다. 명제 논리에서는 P와 Q사이에 어떤 인과관계가 있어야 한다고 요구하지 않습니다. 즉, P와 Q사이에는 전혀 무관할 수 있습니다. "만일 5이 홀수이면 서울은 한국의 수도이다."는 일상 언어의 감각으로는 상당이 엉뚱합니다. 하지만 명제논리에서는 해당 복합 문장을 참이라고 말합니다.(통상적인 해석하에서) 복합 문장을 만들어 내는 각각의 문장에 대한 서로의 인과관계는 필요 없기 때문입니다.

또 다른 혼란스러운 점은, 전제가 거짓인 명제 논리 문장은 결론과는 무관하게 무조건 참입니다. 예를 들어, "만일 3이 짝수라면 범우는 똑똑하다."는 범우가 똑똑한지 똑똑하지 않은지와 상관없이 무조건 참인 문장입니다. 이상하게 느껴질지 모르겠지만, '만일 3이 짝수라면' 이라는 전제가 거짓이기 때문에 결론을 신경쓸 필요없이 해당 복합문장은 참이기 때문입니다.

이를 보다 의미적으로 쉽게 다가가기 위해서, PQ 라는 문장을 "만일 P가 참이면 나는 Q가 참이라고 주장한다. 참이 아니면 나는 어떠한 주장도 하지 않는다."라는 문장으로 생각하면 이해가 될 것 입니다. 이런 문장은 오직 P가 참이고 Q가 거짓일 때에만 거짓이기 때문입니다. 



1-3. 웜푸스 세계에서의 간단한 지식 기지


명제 논리의 구문과 의미론에 대해서 알아보았으니 이제 그것들을 기초로 하여 지난 포스트에서 살펴본, 웜푸스 세계의 지식 기지를 구축해 보도록 하겠습니다. 현재는 웜푸스 세계가 변하지 않는, 불변이(immutable) 측면들에 초점을 맞출 것이며 가변(mutable)적인 측면들은 나중에 살펴보겠습니다. 우선, 아래와 같은 명제 기호에 대한 정의를 가지고 시작하겠습니다.


는 만일 [x, y]에 구덩이가 있으면 참이다.

는 만일 [x, y]에 웜푸스가 있으면(죽음과 상관없이) 참이다.

는 만일 에이전트가 [x, y]에서 미풍을 지각하면 참이다.

는 만일 에이전트가 [x, y]에서 악취를 지각하면 참이다.


지난 포스트에서 우리는 (1,2)에 구덩이가 없음을 비공식적으로 유도하였습니다. 따라서 그에 해당 하는 문장인 을 공식적으로 유도하기 위해 명제 논리 문장들을 작성해 보도록 하겠습니다. Ri는 이후 편하게 문장을 사용할 수 있도록 문장에 각각의 문장을 나타냅니다.


- [1,1]에 구덩이가 없다.

   R1 : 


- 에이전트가 하나의 칸에 존재함 그 이웃칸에 구덩이가 있으면, 그리고 오직 그럴때에만 미풍을 지각할 수 있다.

   R2 : 

   R3 : 


- 앞의 문장들은 모든 웜푸스 세계에서 참이다. 이제 에이전트가 있는 특정한 세계에서 처음 방문한 두 칸에 대한 미풍 지각을 위한 문장들을 명시한다.

   R4 : 

   R5 : 


이렇게 하여 기본적인 지식 기지를 구축해 보았습니다.



1-4. 웜푸스 세계에서의 간단한 추리 절차(모형 점검 방식)


우리의 목표는 지식기지(KB)에서 KB|=a 인 문장 a가 존재하는지를 알아내는 것 입니다.

즉, 위에서 구축한 KB가 를 함축하는지 알아내야 합니다.

이를 알아내기 위해서 진행할 첫 번째 추리 알고리즘은 함축의 정의를 직접 구현하는, 모형 점검 접근방식의 알고리즘입니다.

다시말해 이번에 살펴볼 추리 절차는 모든 모형들을 나열하면서 이에 대해 지식 기지(KB)가 참인지 거짓인지 확인합니다. 그리고 지식 기지가 참인 모든 모형들에서 문장 a가 참인지 점검합니다. 


웜푸스 세계로 돌아 간다면 유관한 명제 기호는  입니다. 명제 기호가 총 7개 이므로 가능한 모형은 총 128개(2의 7승)입니다. 이를 전부 나열했을때 지식 기지가 참인 것을 확인하면 총 3가지의 모형을 볼 수 있습니다.



지식기지가 참이 되는 세가지 모형을 보면 우리가 알아내려한 가 참인 것을 알 수 있습니다. 따라서 (1,2)에는 구덩이가 없습니다. 반면 는 세가지 모형 중 둘에서는 참이고 하나에서는 거짓이므로 (2,2)에 구덩이가 있는지 없는지 알 수 없습니다.


이러한 추리 방법은 이전에 비공식적으로 (1,2)에 구덩이가 없다는 것을 추리한 것보다 보다 엄밀한 추리 방법입니다. 알고리즘에서 함축의 정의를 직접적으로 구현 하기때문에 건전합니다.(sound) 그리고 KB와 a에 대해 작동하고 반드시 종료되므로 완결적(complete) 입니다. 알고리즘이 반드시 종료된다는 것은, 확인할 모형의 개수가 유한하기 때문입니다.


하지만 확인할 모형의 개수가 유한하다는 것은 '적다'라는 의미와는 다릅니다. KB와 a의 기호가 총 n개 일떄 확인해야 할 모형은 총 2^n개 입니다. 따라서 알고리즘의 시간 복잡도는 O(2^n)입니다. 그렇다면 보다 많은 경우에서 우리가 확인한 것보다 더 많은 모형을 확인해야 할 것입니다. 따라서 우리는 훨씬 효율적인 알고리즘들을 뒤에서 살펴보겠습니다.


아래는 표준적인 논리 동치 관계들을 나타내는 것으로써 각각의 문장들로 인한 복합문장들의 참 또는 거짓을 구별할 때 사용됩니다.


이렇게 하여 명제 논리와 모형 점검 방식에 대해 알아보았습니다.

다음 포스팅에서는 정리 증명(theorem proving)을 이용해서 함축 관계를 확인하는 방법을 살펴보도록 하겠습니다.

궁금한 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)



블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


이번에는 지난 포스팅에 이어서 논리와 추론, 모형에 대해서 알아보도록 하겠습니다.

내용을 설명하면서 이해를 돕기 위해 웜푸스 세계에 대한 이야기를 가져오는 경우도 있으니, 웜푸스 세계에 대해서 대략적으로라도 확인하지 못하신 분들은 지난 포스팅을 참고하시길 바랍니다.


1. 논리(Logics)


이번에는 논리적 표현과 추론의 근본 개념들을 소개합니다.

지난 포스팅에서 지식 기지에 대해서 알아보았습니다. 그리고 지식 기지는 문장들로 구성된다고 하였습니다. 여기서 문장들은 표현 언어의 구문(Syntax)을 따릅니다. 표현 언어의 구문은 적격(well-formed)인 문장을 규정합니다. 쉽게 말해서 구문은, 문장을 만드는 규칙을 말합니다. 예를 들어, "x+y=1"이라는 문장은 적격이지만 "+x1y="은 적격이지 않습니다.

논리는 문장의 의미론(Semantics), 즉 문장의 뜻도 함께 정의해야 합니다. 의미론은 각각의 가능한 세계(possible world)에 대한 문장의 진리(truth: 참 또는 거짓)를 정의합니다. 예를 들어 "x+y=2"라는 문장은 x가 1이고 y가 1인 세계에서 참이지만 x가 1이고 y가 0인 세계에서는 거짓입니다. 표준적인 논리에서 모든 문장은 각각의 가능한 세계에서 진리를 표현, 즉 참 또는 거짓이어야 합니다. 참도 아니고 거짓도 아닌 애매한 문장은 존재하지 않습니다. 아래의 예시들로 다시 한번 정리할 수 있습니다.


'x + 2 >= y' is a sentence; x2+y>= is not sentence

'x + 2 >= y' is true iff the number x + 2 is no less than the number y

'x + 2 >= y' is true in a world where x=7, y=1

'x + 2 >= y' is false in a world where x=0, y=6



2. 추론(Entailment)


논리적 추론에서는 위에서 알아본 문장들 사이의 논리적 함축(entailment) 관계가 관여합니다.

함축이란, 한 문장이 다른 문장을 '논리적으로 따른다(follow)'는 개념을 나타내는 용어입니다. 함축은 아래와 같은 표기법으로 나타낼 수 있습니다.

이는 모든 문장 (이후 a라고 표기)가 문장 (이후 b라고 표기)를 함축한다는 뜻 입니다.

함축이란 용어의 형식적인 정의는 다음과 같습니다. 만일 a가 참인 모든 가능한 세계에서 b 역시 참일때에만 a|=b 이다.

즉 위의 표기법에서 a가 b 보다 더 강한 문장입니다. 


이러한 함축이라는 개념을 웜푸스 세계의 예제에도 적용할 수 있습니다.



에이전트는 (1,1)의 방에서는 아무것도 감지하지 못했지만 (2,1)에서는 미풍을 감지하였습니다. 이러한 지각들과 웜푸스 세계의 규칙들에 대한 에이전트의 지식이 합쳐져서 에이전트의 지식 기지를 형성합니다. 에이전트 입장에서는 (1,2)와 (2,2), (3,1)에 구덩이가 있는지가 관심의 대상입니다. 그 세칸에는 각각 구덩이가 존재하는지 존재하지 않는지의 경우가 존재하므로 가능한 세계의 수는 2의 3승, 총 8개 입니다. 이러한 세계를 도형으로 나타내면 아래와 같습니다.




위의 그림에서 각각의 선이 의미하는 바는 다음과 같습니다.


KB = 에이전트가 가지고 있는 지식 기반

= "(1,2)에 구덩이가 없다." (이후 a1 이라고 표기)

= "(2,2)에 구덩이가 없다." (이후 a2 라고 표기)


a1이 가능한 세계들과 a2가 가능한 세계들이 위의 그림에 표현되어 있습니다.

이들로 부터 우리는 다음과 같은 사실을 알 수 있습니다.


KB가 참인 모든 가능한 세계에서 a1도 참이다.


따라서 KB|=a1 입니다. 즉 (1,2)에는 구덩이가 없습니다. 또한 다음과 같은 사실도 알 수 있습니다.


KB가 참인 가능한 세계중 a2가 거짓인 가능한 세계들이 존재한다.


따라서 KB|=a2가 아닙니다. 즉 에이전트는 (2,2)에 구덩이가 없다는 사실을 도출할 수 없습니다. 마찬가지로 (2,2)에 구덩이가 있다는 사실 또한 도출할 수 없습니다.


이러한 예시는 함축관계를 보여줄 뿐만 아니라, 함축의 정의를 이용해서 결론을 이끌어 내는 방법, 즉 논리적 추리를 수행하는 방법 또한 보여줍니다.


함축과 추리의 이해에 도움이 되기 위해 KB의 모든 결과의 집합이 건초 더미이고 a가 하나의 바늘이라고 생각하면, 함축은 건초 더미에 바늘이 존재한다는 것에 해당하고, 추리는 그 바늘을 찾는 것에 해당합니다.

이러한 구분을 형식적 표기법으로 나타낼 수 있습니다.

추리 알고리즘 i가 KB로부터 a를 도출할 수 있을 때, 이를

로 표현할 수 있습니다. 이것은 'a가 i에 의해 KB로부터 유도된다' 또는 'i는 KB로부터 a를 유도한다'로 말 합니다.


함축된 문장들만 유도하는 추리 알고리즘을 가리켜 건전한(sound) 또는 진리를 보존하는(true-preserving) 알고리즘이라고 말합니다. 반대로 생각해본다면, 건전하지 않은 추리 절차는 추리과정에서 무언가를 근거 없이 만들어 냅니다.

완결성(completencess) 역시 바람직한 속성입니다. 함축된 임의의 문장을 유도할 수 있는 추리 알고리즘은 완결적 입니다. 실제 건초 더미의 경우 지푸라기들을 체계적으로 조사한다면 그 건초 더미에 바늘이 있는지의 여부를 항상 결정할 수 있음이 명핵합니다. 그러나 지식 기지 중에는 결과들의 건초 더미가 무한한 것들이 많기 때문에 완결성이 중요한 문제가 됩니다. 다행히, 여러 지식 기지를 다루기에 충분한 표현력을 가진 완결적인 논리적 추리 절차들이 많이 있습니다.


지금까지 전제들이 참인 세계에 대해서는 결론이 반드시 참인 추론 공정을 알아보았습니다.

정리하자면, 만일 실제 세계에서 KB가 참이면, 건전한 추리 절차를 이용해서 KB로부터 유도한 임의의 문장 a도 실제 세계에서 참입니다.



3. 모형(Model)


앞서 논리에 대한 이야기를 진행하면서 '가능한 세계'라는 표현을 많이 사용하였습니다. 헌데, 좀 더 엄밀한 정의가 필요할 때 '가능한 세계'대신 '모형(Model)'이라는 용어를 사용합니다.

가능한 세계는 에이전트가 처할 수도 있고 그렇지 않을 수도 있는, 잠재적인 실제 환경이라고 생각할 수 있는 반면, 모형은 수학적인 추상입니다. 각각의 모형은 그냥 모든 유관한 문장의 참 또는 거짓을 고정시킨 것입니다. 

문장 a가 모형 m에서 참일 떄, 이를 'm이 a를 만족한다'라고 말할 수 있습니다. 때에 따라서는 'm이 a의 모형이다'라고 말할 수도 있습니다. 또한 a의 모든 모형의 집합을 M(a)로 표기합니다.


다음 포스팅에서는 명제논리라는 것에 대해서 알아보겠습니다.

명제논리의 구문과 그 의미론을 설명하고 그런 다음 어떤 문장이 다른 어떤 문장을 따른다는 함축 관계를 살펴보도록 하겠습니다.

내용에 대한 피드백이나 궁금한 점은 언제든지 댓글을 이용해주세요 :)

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


최근 인공지능에 대해서 기본적인 이론과 개념을 공부중에 있습니다.

따라서 공부하면서 내용을 정리해서 포스팅을 진행하려 합니다.

'인공지능:현대적 접근' 이라는 책을 기반으로 학습 중이며 내용 중간중간 있는 사진과 도표 및 수도코드의 출처는 해당 책임을 밝힙니다.

내용에 대한 피드백이나 궁금한 점은 언제든지 댓글을 통해 말씀해주시면 감사하겠습니다.


이번 포스팅에서는 논리적 에이전트와 웜푸스 세계에 대해서 알아보도록 하겠습니다.

그리고 이어지는 내용인 논리와 추론, 명제에 대한 내용은 다음 포스팅에서 정리하고 명제 논리에 대해서는 그 다음에 살펴보도록 하겠습니다..


1. 논리적 에이전트(Logical Agents)


사람은 여러가지의 지식을 가지고 있습니다. 그리고 그러한 지식을 표현(representation)할때 문장(sentence)를 사용합니다. 당연히 그러한 문장은 무의미하지 않습니다. 즉, 인간은 무언가에 대한 반응으로 단순한 반사작용의 메커니즘이 아니라 자신이 가지고 있는 지식의 내부 표현들에 작용하는 추론(reasoning) 공정들로 달성됩니다.

인공지능에서는 지식 기반 에이전트(knowledge-based agent)라는 것은 지능에 대한 위와 같은 접근방식을 포함하는 것을 말합니다.


부분 관찰 가능 환경(partially observable)에서 에이전트가 현재 상태에 관해 아는 것을 표현하는 유일한 방식은, 모든 가능한 구체적 상태들을 단순하게 나열하는 것일 뿐입니다. 커다란 환경에서는, 실제 환경에서는 그러한 표현 방식이 비현실적일 확률이 아주 높습니다.

따라서 '논리적 에이전트'에서는 복잡한 세계의 표현을 형성할 수 있고 추리 공정을 이용해서 세계에 대한 새로운 표현들을 유도할 수 있으며 그러한 새 표현들을 이용해서 다음에 할 일을 연역할 수 있는 에이전트를 설계할 수 있도록 공부합니다.

즉, 논리(logic)를 지식 기반 에이전트가 가능한 표현들의 일반적 부류(class)로 취급하고 그러한 에이전트는 정보를 다양한 목적에 맞게 조합 및 재조합할 수 있게 됩니다.

따라서 이러한 지식 기반 에이전트는 명시적으로 서술된 목표의 형태로 새 과제들을 받을 수 있으며, 환경에 대한 새로운 지식을 제공받거나 스스로 습득하고 환경의 변화에 적응하거나 유관한 지식을 갱신할 수 있습니다.


우선 처음에 '지식 기반 에이전트'에 대한 전반적인 설계를 살펴보고, 간단하지만 새로운 환경인 웜푸스 세계를 소개하고 지식 기반 에이전트의 작동 방식을 기술적인 세부사항 없이 알아보겠습니다. 그리고 다음 포스팅 부터 논리의 일반적인 원리들을 살펴보고 이후 좀 더 구체적인 명제 논리의 원리들을 살펴보겠습니다.


2. 지식 기반 에이전트(Knowledge-based agent)


지식 기반 에이전트의 핵심 구성요소는 기본의 지식 베이스, 지식 기지(knowledge base)라고 불리는 것 입니다.

이러한 지식 기지는 문장들의 집합입니다. (Knowledge base is set of sentences in a formal language)

여기서 '문장'이라는 것은 기술 용어입니다. 영어나 한국어 등의 문장과 관련이 있기는 하지만 같은 것은 아니므로 혼동되지 않도록 천천히 이해하시길 바랍니다.


기본적으로 지식 기지라는 것에 새로운 문장, 즉 새로운 지식을 추가하는 방법과 지식 기지에 있는 문장을 질의하는 방법이 필요합니다. 이때, 새로운 문장을 추가하는 방법을 TELL이라 말하며 지식 기지에 있는 문장을 질의하는 방법을 ASK라고 합니다. 그리고 두 연산의 과정 속에는 추리(inference), 즉 기존의 문장들에서 새로운 문장을 이끌어 내는 공정이 존재합니다.

추리라는 것은 누군가가 ASK 연산을 수행했을때 그에 대한 답이 반드시 과거에 지식 기지에 TELL 연산을 통해 추가된 어떠한 지식(문장)에서 도출되어야 한다는 요구조건을 만족해야 합니다. 다시 말해 추리의 공정이 근거 없이 말을 꾸며내는 것이 되면안된다는 것 입니다.


아래의 사진은 지식 기반 에이전트 프로그램의 기본적인 큰 틀입니다. 해당 에이전트는 지각 하나를 입력받고 동작 하나를 반환합니다. 그리고 에이전트는 지식 기지(KB)를 유지하고 있습니다. 그리고 에이전트는 사전에 자신의 지식 기지에 일정한 배경 지식(background knowledge)를 가지고 있을 수 있습니다.



TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t)) 에서는 주변의 환경을 지각하여(percept) 지식 기지(KB)에 알려주는 TELL연산을 수행합니다. 그리고 지식 기지에 행동(action)을 요청하는 ASK 연산을 수행하고 자신이 선택한 행동을 다시 지식 기지에 알려주는 TELL연산을 수행한 후에 행동을 반환합니다.


위에서 알아본 TELL과 ASK 연산의 정의를 생각해본다면 지식 기반 에이전트는 단순히 특정 동작들을 계산을 통해 도출해내는 프로그램이 아닙니다. 지식 기반 에이전트는 지식 수준(knowledge level)에서의 서술, 정의를 준수합니다. 위에서 언급했듯이 특정한 지식을 통한 근거있는 행동만을 반환하는 것 입니다.

이러한 수준에서 개발자는 에이전트가 현재 알고 있는 것과 에이전트의 목표를 결정해준다면 에이전트의 행동을 바로잡고 예측할 수 있습니다.

예를 들어서 A장소에서 B장소로 가는 것이 목표인 에이전트가 있는데 두 장소를 연결하는 유일한 경로 p라는 것을 에이전트가 알고 있다고 가정하겠습니다. 그렇다면 개발자는 에이전트가 p라는 경로를 통해 움직일 것을 충분히 예상할 수 있습니다. 그것이 에이전트 자신이 목표를 달성하는 유일한 방법임을 자신의 지식 기지에서 도출해 낼 수 있기 때문입니다.


개발자는 에이전트가 알아야 할, 가져야 할 지식을 단순히 TELL연산으로 알려주는 방법으로 하여금 프로그램을 설계할 수 있습니다. 즉 에어전트의 지식 기지가 비어있는 상태에서 에이전트가 주어진 환경에서 적절하게 행동을 반환할 수 있을 때 까지 문장(지식)들을 TELL 연산으로 하나씩 주입할 수 있는 것 입니다. 그리고 이것을 선언적(Declarative) 시스템 구축 접근방식이라고 부릅니다. 또한, 이와 다르게 절차적(procedural) 시스템 구축 접근방식이 존재합니다. 절차적 접근방식은 바람직한 행동을 프로그램 코드에 직접 입력합니다.

그리고 현재에 있어서는 성공적인 에이전트의 설계에 선언적 요소와 절차적 요소가 모두 들어 있는 경우가 많다는 점과 선언적 지식을 좀 더 효율적인 절차적 코드 안에 조합해 넣을 수 있는 경우가 많다는 점이 알려져 있습니다.



3. 웜푸스 세계(Wumpus world)


이번엔 위에서 학습한 내용들을 바탕으로, 지식 기반 에이전트의 가치를 볼 수 있는 웜푸스 세계(Wumpus world)라는 환경을 살펴보겠습니다.



위와 같은 웜푸스 세계에 대해 간략히 설명한다면, 웜푸스 세계는 여러 개의 방이 통로로 연결된 동굴입니다. 동굴 어딘가에는 거대한 괴물인 웜푸스가 존재합니다. 그림을 보면 1열 3행에 존재함을 알 수 있습니다. 웜푸스를 만나면 에이전트는 사망하게 됩니다. 에이전트는 웜푸스를 화살로 쏴서 죽일 수 있지만 화살은 딱 하나만 존재합니다. 그리고 특정 방에는 바닥이 없는 구덩이(pit)이 존재합니다. 구덩이가 존재하는 방에 들어가면 마찬가지로 에이전트가 죽게됩니다. 그리고 금 더미가 놓인 방이 있습니다. 이를 정리해 보면 웜푸스 세계에 존재하는 요소는 웜푸스, 구덩이, 금으로 총 3가지 입니다. 

각각의 요소는 특징을 가지고 있습니다. 그림을 보면 확인 할 수 있듯이 웜푸스가 존재하는 방에 인접한 방은 악취(stench)가 존재하고, 구덩이가 존재하는 방에 인접한 방은 미풍(breeze)이 존재하며, 금이 존재하는 방에는 반짝임(glitter)이 존재합니다.


이러한 환경에 처한 에이전트의 주된 난제는, 초기에 환경의 구성에 대해 전혀 무지하다는 것 입니다. 이러한 무지를 극복하기 위해서는 에이전트에게 추론이 필요합니다. 그럼 에이전트가 웜푸스 세계의 환경을 헤쳐나가는 과정을 확인해보도록 하겠습니다.


먼저, 에이전트의 초기 지식 기지에는 위에서 서술한 환경의 규칙들이 들어있습니다. 먼저 에이전트는 현재 자신이 존재하는 방, (1,1)의 방에 안전함(OK)과 현재 에이전트 자신이 존재하는 곳임을 알리는 A를 기록합니다. 즉, 에이전트 자신은 현재 (1,1)에 존재하며 (1,1)에서는 악취, 미풍 및 반짝임이 존재하지 않습니다. 따라서 (1,1)에는 안전함이 기록되어 있으므로 이러한 지식 기지를 통해 에이전트는 (1,2) 또는 (2,1)의 방이 안전함을 추리할 수 있습니다. 즉 (1,2)와 (2,1)에 안전함을 기록합니다.

에이전트는 오직 안전함이 기록된 곳으로만 이동할 것입니다. 그렇지 않으면 자신이 죽을 수도 있는, 즉 목표를 이루지 못하한다는 것을 알 수 있기 때문입니다. 

이후 에이전트는 (2,1)에서 미풍을 감지하게 됩니다. 따라서 에이전트는 (2,1)에 미풍을 감지했다는 B를 기록합니다. 이로 인해 (2,2)와 (3,1)은 아직 에이전트에게 위험한, 미지의 방입니다. 에이전트가 존재하는 (2,1)의 방에서 이웃한 방은 (1,1), (2,2), (3,1)로 총 세개인데 (1,1)의 방은 안전함이 기록되어 있으므로 (2,2)와 (3,1)의 방에 구덩이가 존재할 수도 있다는 P? 를 기록합니다.

그리고 에이전트는 안전함이 기록되어 있는 또 다른 방 (1,2)로 이동합니다. 그리고 (1,2)에서는 악취를 감지하므로 S를 기록합니다.  또한 같은 방식으로 (1,3)과 (2,2)의 방에 웜푸스가 존재할 수도 있다는 W?를 기록해야 합니다. 하지만 만약 (2,2)에 웜푸스가 존재했다면 (2,1)에서 또한 악취를 감지했어야 합니다. 따라서 웜푸스는 (1,3)에 존재한다는 것을 추리를 통해 알 수 있습니다. 그렇기 때문에 에이전트는 (1,3)에 웜푸스가 존재한다는 W를 기록합니다. 그리고 현재 (2,2)에 구덩이가 존재할 수도 있다는 P? 가 기록되어 있는데 (2,2)에 구덩이가 정말로 존재한다면 (1,2)의 방에서도 미풍을 감지해야 합니다. 하지만 (1,2)의 방에서는 미풍이 감지되지 않으므로 (2,2)에는 구덩이가 존재하지 않음을 알 수 있기에 P? 기록을 지우고 안전함을 기록합니다. 동시에 (3,1)에 구덩이가 존재한다는 P를 기록합니다. 

위와 같은 방식을 통해 에이전트는 (2,3)으로 이동합니다. 해당방에서 에이전트는 반짝임을 감지합니다. 따라서 금을 획득하게 되고 다시 안전함으로 기록되어 있는 방들을 통해 시작지점으로 돌아가게 됩니다.


웜푸스 세계를 통한 에이전트의 행동 및 추리를 보았습니다. 에이전트가 주어진 정보(배경 지식 또는 지식 기지)로 부터 어떠한 결론(행동)을 이끌어 낼 때마다, 만일 주어진 정보가 정확하다면 그 결론 역시 정확함을 보장한다는 것에 주목하시길 바랍니다. 이러한 것은 우리가 처음에 알아 본 것과 같이 추리, 논리적 추론의 근본적인 속성입니다. 




이제 이러한 웜푸스 세계는 잠시 내려두고, 다음 포스팅에서 부터는 논리와 추론, 모델에 대해서 알아 보겠습니다. 논리와 명제 논리에 대해 알아보면서 웜푸스 세계에 대한 내용을 바탕으로 서술되는 부분들이 있으니 꼭 웜푸스 세계에 대한 전체적인 과정을 확인하시길 바랍니다.


블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc