Limitations of Logic

* The Search Space Problem

Logic 에서 Theorem Prover 의 속도는 매우 중요하다 . 지식베이스 rule 이 500 개 이상 있다고 가정하면 실제로 전문가 시스템의 경우 수 백 혹은 수 천 개의 rule 은 보통 갖게 된다 ) 추론을 하기 위해서 엄청난 inferencing 이 일어날 수 있다

예를 들어 resolution inference 의 경우 임의로 2 개의 clause 를 잡아 resolution 을 시도한다면 원하는 답을 얻기 위해 많은 inferencing 이 일어나 시스템의 효율이 떨어진다 . 그러므로 rule 이 늘어 남에 따라 시스템 속도는 급속히 떨어질 수 있다

이러한 문제를 해결하기 위한 heuristic algorithm 등 소프트웨어 적인 접근과 병렬처리 기능인 는 PROLOG machine 등도 생각하게 되었다.

 

 

 

* Decidability and Incompleteness

=> Decidability 하다는 것은 주어진 문제는 언제나 멈추고 항상 풀 수 있다.

=> 명제 논리에서 sound & complete 한 theorem prover 는 truth table 이다.

=> 1차 서술 논리는 semi-decidable 하다.

 

 

* Complexity

- Decidable Problems: If there exist algorithms to solve the problems.

=> 문제를 풀 수 있는 알고리즘 존재

- Undecidable Problems: If no algorithms

=> 문제를 풀 수 있는 알고리즘 미존재

- Semi decidable problems: If there exist procedures, but no algorithms to solve them, that is If the answer is “yes”, then there is an algorithm. If not, it may run forever without answering. (Halting Problem)
Turing Machine(TM) can solve semidecidable , but there are problems that TM can not solve.(ref to Godelization)

=> 문제를 풀 수 있는 알고리즘이 존재할 수도 있고, 미존재하는 경우도 있다.

 

 

 

* The Flying Penguin

논리의 약점 중의 하나는 불확실한 지식을 표현하기 어렵다는 점이다. 왜냐하면 Logic 은 monotonic 하기 때문이다. 즉 Logic 에서 formula 가 참이면 새로운 지식이 들어와도 여전히 그 formula 는 참이기 때문이다. 인공지능 분야에 불확실한 지식의 예로 Flying Penguin 이라는 문제가 있다.

 

Example 1.

=> logic은 monotonic하므로 새로운 지식이 들어와도 logic을 변경할 수 없다.

 

=> qualification problems 이란,

아무리 조건을 끼워 맞춰서 문제를 해결하더라도 충분히 다른 예외 조건이 생길 수 있다.

 

 

* The ravem Abraxas

Example 2.

 

 

* Frame Problems

세상에 있는 많은 문제들은 보통 시간과 관련이 있을 수 있다. 시간이 지나감에 따라 관찰되는 내용이 달라질 수 있다. 사람이 움직이면 시간에 따라 그 위치가 바뀐다. 그러나 시간이 지나가도 잘 변치 않는 것도 있다. 예를 사람의 이름, 벽의 색깔 등은 시간이 지나도 잘 변치 않는다. 이렇게 시간이 연관된 지식을 표현할 때 모든 Logic formula 의
파라미터로 time ( 예를 들어 time stamp) 을 사용하여 확장한 언어를 Situation Calculus 라고 한다. 이 경우 지식베이스는 시간이 지남에 따라 방대하게 커져 지식기반 시스템의 효율성이 떨어지게 된다. 이러한 문제를 조금 완화하기 위하여 시간이 지나도 변치 않는 속성 등은 axiom 으로 표현하여 필요시 이를 사용하게 된다. 이러한 axiom 을 Frame axiom 이라고 부른다.

 

Example 3.

=> 시간에 따라 집의 색이 바뀌어 contradiction이 발생하였다.

 

=> 위 logic 들로 문제를 해결하려 많은 연구를 진행했지만,

문제 해결에 완벽하게 적용이 가능하지는 않다.

 

 

* Modelling Uncertainty

Example 4.

=> 오늘날 많은 model 들이 확률을 기반으로 한 확률 model 이다.

 

 

 

 아주대학교 정보통신대학원 김민구 교수님의 인공지능 강의를 바탕으로 작성하였습니다.

 학습 목적으로 포스팅 합니다.