Artificial Intelligence: Assignment 3
Seung-Hoon Na October 24, 2018
1 명제 논리와 추론 (Propositions and Inference)
1.1 Modus Ponens에 기반한 증명 절차 (proof procedure)
명제 논리가 propositional definite clauses로 주어졌다고 하자. KB가 propo- sitional definite clauses로 구성된 경우에 상향식 증명 절차 (bottom-up proof procedure) 는 다음과 같다.
Algorithm 1 Definite clauses기반 KB상에서 Bottom-up proof procedure
1: procedure P rove DC BU (KB). Returns set of all atoms that are logical consequences of KB
2: C := {} . C is a set of atoms
3: repeat
4: Select h ← a1∧ · · · ∧ amin KB where ai∈ C for all i, and h /∈ C
5: C := C ∪ {h}
6: until No more definite clauses can be selected
7: return C.
8: end procedure
Problem 1 Propositional definite clause의 정의를 기술하시오.
Problem 2 KB가 Propositional definite clause들로 구성되어 있다고 가정하자.
(1) 어떤 KB의 model이란 KB내의 모든 명제를 참으로 하는 interpre- tation을 말한다. KB가 다음과 같을때, 가능한 모든 model을 기술하 시오.
KB = {p, q ← p, r}
(2) KB |= g는 무슨 의미인가?
(3) 주어진 증명 절차(proof procedure)에 대해, KB ` g의 의미는 무엇인 가?
(4) KB |= g와 KB ` g의 차이점을 서술하시오.
Problem 3 Soundness와 Completeness
(1) 주어진 증명 절차가 sound하다는 말은 무슨 의미인가?
(2) 주어진 증명 절차가 complete하다는 말은 무슨 의미인가?
(3) 위의 상향식 증명 절차 P rove DC BU 가 sound함을 증명하시오 (4) 위의 상향식 증명 절차 P rove DC BU 가 complete함을 증명하시오
1
1.2 Negation as Failure
Atom a에 대해 증명이 fail되면, ∼a이라고 쓰고, 이를 Negation as failure (NAF)라고 부른다. KB를 NAF를 포함하는 clauses들로 구성될때 , 확장된 상 향식 증명 절차는 다음과 같다.
Algorithm 2 Bottom-up negation as failure proof procedure
1: procedure P rove N AF BU (KB) . Returns set of literals that follow from the completion of KB
2: C := {} . C is a set of atoms
3: repeat
4: either
5: select r ∈ KB such that r is h ← b1∧ · · · bm, bi∈ C for all i, and h /∈ C
6: C := C ∪ {h}
7: or
8: select h ∈ KB such that ∼ /∈ C and
where for every clause h ← b1∧ · · · ∧ bm∈ KB either for some bi, ∼bi∈ C
or some bi= ∼g and g ∈ C
9: C := C ∪ {∼h}
10: until No more selections are possible
11: return C.
12: end procedure
Problem 1 Monotonic logic은 어떠한 특징을 가진 logic을 말하는가?
Problem 2 Non-monotonic logic이란 어떠한 특징을 가진 logic인가?
Problem 3 KB가 NAF를 포함한 clauses라고 가정하고, Non-monotonic한 특 성을 보이도록 예제를 찾아 보이시오.
즉, NAF를 포함한 clauses로 구성된 KB의 예를 들고, 여기에 어떠한 clause 들을 추가함으로써 이전의 consequence가 취소되는 사례를 보이면 된다.
Problem 4 [Python implementation] 위의 NAF의 상향식 증명 절차를 python 으로 구현하시오.
단, KB를 구성하는 clauses를 파일로부터 읽어들일 수 있도록 하고, 파일 포맷을 위해, negation은 !기호를, NAF를 위해 기호를 사용한다. 즉, !P는
¬P 을 의미하고, P는 ∼P 를 의미한다.
그리고, 한 line당 하나의 clause만이 표현되도록 하여, 파일의 총 line수가 KB에 포함된 clause의 총 갯수수와 일치하도록 한다.
입력 파일의 예는 다음과 같다.
p <- q ˜r p <- s q <- ˜s r <- ˜t
2
t s <- w
위의 입력 파일은 다음 clauses로 구성된 KB를 의미한다.
p ← q ∧ ∼r p ← s q ← ∼s r ← ∼t t
s ← w
구현 및 테스트 요구사항을 정리하면 다음과 같다.
• 상향식 증명 절차 구현: P rove NAF BU를 python으로 구현
• 상향식 증명 절차 Test: 상기 포맷의 입력파일로 부터 KB를 읽어들 이고, 이로부터 구현된 상향식 증명 절차 P rove N AF BU 를 적용하여 주어진 KB로부터 추론 가능한 모든 literal의 집합 C를 얻고,C의 내용 을 출력하는 python 코드를 작성.
다양한 샘플 KB (5개이상)로부터 Test적용 결과를 기술하시오 (보고 서에 테스트 결과 기술).
• 상향식 증명 절차 Non-monotonic Test:
Problem 3의 예제를 적용하여 Non-monotonic특성을 보이는 상황을 테스트하라 (보고서에 테스트 결과 기술).
1.3 Abduction
Abduction을 형식화 하기 위해, hKB, Ai가 주어지고, 여기서 KB는 Horn clauses 들로 구성된 knowledge base를, A를 assumables 집합이라고 하자.
Problem 1 Abduction이란 무엇인가?
Problem 2 hKB, Ai의 scenario에 대한 정의를 기술하시오.
Problem 3 hKB, Ai로부터 명제 g에 대한 explanation의 정의와 minimal ex- planation의 정의를 기술하시오.
Problem 4 KB가 다음 Horn clauses로 구성되고, low ← study none
low ← dif f icult ∧ study normal high ← easy ∧ study normal high ← genius
high ← study hard happy ← high happy ← easy
f alse ← study none ∧ study normal f alse ← study normal ∧ study hard f alse ← study none ∧ study hard
3
Assumables A가 아래와 같다고 가정하자 .
easy, dif f icult, genius, study none, study normal, study hard
(1) high가 observation되었을때의 모든 minimal explanation을 나열하시 오.
(2) 또한, low가 observation되었을때의 모든 minimal explanation을 나열 하시오.
(3) 또한, low ∧ happy가 observation되었을때의 모든 minimal explanation 을 나열하시오.
Problem 5 Abductive diagnosis란 무엇인지 언급하고, Consistency-based diagnosis와 차이점을 간단한 예를 들어 서술하시오.
2 제출 내용 및 평가 방식
본 과제 결과물로 필수적으로 제출해야 내용들은 다음과 같다.
• 문제 풀이 보고서: 서술형 문제에 대한 풀이 결과 (word파일 작성)
• 코드 전체: Problem 1.2.4에 대해서 Python code 전체
• KB 샘플 파일 전체: Problem 1.2.4에서 sample로 사용한 KB 파일들 전체.
• 테스트 결과: Problem 1.2.4에 대한 code 및 해당 로그 또는 출력 결과.
• 결과 보고서: Problem 1.2.4에 대한 구현 방법 및 테스트 결과를 요약한 보 고서 .
본 과제의 평가항목 및 배점은 다음과 같다.
• 전체 문제 풀이 결과의 정확성 및 가독성 (40점)
• 구현 정확성 및 완결성 (40점)
• 코드의 Readability 및 쳬계성 (10점)
• 결과 보고서의 구체성 및 완결성 (10점)
4
