[23-01/인공지능] 지식표현과 추론 - 2

1. 명제 논리 (Propositional Logic)

명제논리 표현 (Translating English Sentences)

■ 명제 논리에서 영어 문장을 변환

- 원자 명제를 정의하고 명제 변수를 사용해 표현함

- 적절한 논리적 기호를 결정함

"If I go to Harry's or to the country, I will not go shopping."
p : I go to Harry's.
q : I go to the country.
r : I will go shopping.
(q ⋁ q) → ¬r

memo : 한국어는 이러한 패턴이 잘 안보임. 영어는 조건과 결과가 잘 보이고, If 이러한 구조가 있으면 조건이고, 뒤에는 실행하는 결과가 나온다면 이것은 항상 implication관계를 가짐. 콤마(,)는 then의 의미.

 

■ Example (Student)

"You can access the Internet from campus only if you are a computer science major or you are not a freshman."
One Solution: Let a, c, and f represent respectively
"You can access the internet from campus," "You are a computer science major," and "You are a freshman."
a ↔ (c ⋀ ¬f)

memo : only if는 대부분 연결자 ↔ 

 

■ Example (System Specifications)

- 시스템 및 소프트웨어 엔지니어는 영어로 요구사항을 처리하고 논리에 기반한 정확한 사양 언어로 표현함

"The automated reply cannot be sent when the file system is full"
Solution : One possible solution : Let p denote "The automated reply can be sent" and q denote "The file system is full."
p : The automated reply can be sent
q : The file system is full
q → ¬p (파일 시스템이 가득차면 응답을 보내지 않음)

 

지식베이스(KB) 표현 (Wumpus world case)

■ 좌표를 이용해 명제 표현

- Pₓ,ᵧ = True

    - 만약 [x, y]지점에 Pit(구덩이)가 있을 경우 True

- Bₓ,ᵧ = True

    - 만약 [x,y]지점에서 Agent가 Breeze(미풍)을 느낄 경우 True

- Sₓ,ᵧ = True

    - 만약 [x,y]지점에서 Agent가 Stench(악취)를 느낄 경우 True

- Wₓ,ᵧ = True

    - 만약 [x,y]지점에 Wumpus (dead or alive)가 있을 경우 True

 

■ 규칙 정의

- Agent가 움직이면서 관찰한 정보를 지식베이스에 저장함

- [1,1]에는 Pit가 없음

    - Rule1 : ¬P₁,₁

- 만약 Pit에 인접한 칸이라면 Breeze를 감지

    - Rule2 : B₁,₁ ↔ (P₁,₂ ⋁ P₂,₁)

    - Rule3 : B₂,₁ ↔ (P₁,₁ ⋁ P₂,₂ ⋁ P₃,₁)

- Breeze와 관련된 정보는 (1,1),(2,1)에서 감지되었음

    - Rule4 : ¬B₁,₁

    -Rule5 : B₂,₁

∴ KB는 B₁,₁  , B₂,₁ , P₁,₁ , P₁,₂ , P₂,₁ , P₂,₂ , P₃,₁ (총 7개)에 대한 정보를 알고 있으며, 총 2⁷ = 128개 조합 가능 (중복순열)

 

■ Truth Table for Inference

- 항상 추론할 수 있는거 아님. 규칙이 더 추가되면 가능할 수도있음.

- 하지만 이것은 효율적이지 않음 다 저장 불가능.

- 작은 명제에서는 가능하지만 커지면 불가능.

- 기본적인 원리는 이런 방법

 

추론 규칙

- 추론 규칙은 우리가 가지고 있는 지식(KB)과 이미 알고있는 사실(Observation)으로 부터 새로운 사실을 유추해내는 것 (결과에 대한 증명을 이끌어 내는데 사용 가능)

1. Moudus Ponens (전건긍정)

- A가 True인 것으로 정의하면, B도 True라는 결론을 얻는 논리규칙

2. Modus Tollens (부정논법)

- 규칙의 결론이 False인 경우 해당 조건 또한 False로 추론하는 것

3. AND-Elimination (AND조건의 삭제)

- A가 True이며 A ∧ B의 결론이 True인 경우, B또한 True로 추론하는 것

4. Syllogism (삼단논법)

- 두개의 규칙을 연쇄적으로 작용시켜 새로운 규칙을 도출해내는 추론 방법

 

Moudus Ponens (전건긍정)

- A가 True인 것으로 정의하면, B도 True라는 결론을 얻는 논리 규칙

규칙 : A->B
사실 : A
-------------------
결론 B

ex)
"홍길동이 세계 일주 중이라면 -> 로또에 당첨된 것이다."
"홍길동은 세계 일주 중이다."
-------------------------------------------------------------------------------
∴ "홍길동은 로또에 당첨된 것이다."

 

Moudus Tollens (부정논법)

- 규칙의 결론이 False인 경우 해당 조건 또한 False로 추론하는 것

규칙 : A -> B
사실 : NOT B
-------------------------
결론 : NOT A

ex)

"어떤 동물이 강아지라면 -> 어떤 동물은 4개의 다리를 가지고 있다."

"어떤 동물은 4개의 다리를 가지고 있지 않다."

--------------------------------------------------------------------------------------------

∴ "어떤 동물은 강아지가 아니다."

 

AND-Elimination (AND조건의 삭제, Identify raw(항등법칙))

- A가 True이며 A ∧ B의 결론이 True인 경우, B 또한 True로 추론하는 것

규칙 : A ∧ B
사실 : A
----------------------
결론 B

ex)

"어떤 동물이 강아지이고 4개의 다리를 가지고 있다."

"어떤 동물은 강아지이다."

------------------------------------------------------------------------

∴ "강아지는 4개의 다리를 가지고 있다."

 

Syllogism (삼단논법)

- 두개의 규칙을 연쇄적으로 작용시켜 새로운 규칙을 도출해내는 추론 방법

규칙 : A -> B
사실 : B -> C
------------------
결론 A -> C

ex)

"소크라테스는 인간이다."

"인간은 모두 죽는다."

---------------------------------------

∴ "소크라테스는 죽는다"

 

추론 규칙의 3가지 증명

■ Forward Chaining (전방 연쇄 / 순방향 추론)

- 알려진 사실로부터 출발하여 결론을 이끌어내는 방법

- LHS to RHS

- Data - Driven

- Model checking 방법

 

■ Backward Chaining (후방 연쇄 / 역방향 추론)

- 목표를 설정하고, 이를 증명하는 증거를 찾는 방법

- RHS to LHS

- Goal-Driven

- Model checking 방법

 

■ Resolution Refutation (Theorem Proving)

- CNF(논리곱) 표준형, Resolution(분해법칙)을 적용

- 모순(Contradiction) 또는 반박 (Refutation)을 통해 결론을 이끌어내는 방법

- 추론 규칙 적용 방법

 

Forward Chaining (전방 연쇄/순방향 추론)

- 알려진 사실에 의거하여 KB에 있는 규칙들을 실행하고, 발견된 지식을 KB에 추가

- A와 B라는 사실(Fact)를 알게 되면 A ∧ B ⇔ L 라는 규칙을 통해 새로운 L이라는 사실을 알 수 있음

memo : 모든 곳 다 방문함. 약간 BFS 같은 느낌

 

Backward Chaining (후방 연쇄 / 역방향 추론)

- 목표에서 시작하여 사실 데이터가 이러한 목표를 지원하는지 확인하는 방법

memo : 모든 경로 다 보지 않아도 됨. 약간 DFS 같음

 

Forward Chaining vs. Backward Chaining

- Forward Chaining은 Data-Driven 방법 (즉 사실을 모은 후 이를 바탕으로 추론)

    - e.g.) object recognition, routine decision에 활용

- Forward Chaining의 경우 목표(goal)과 관련없는 규칙들에 대해서도 살펴봐야함 (BFS 방법과 유사)

 

- Backward Chaining은 Goal-Driven 방법 (즉 목표에서 시작하여, 데이터들이 목표를 지원하는지 확인)

    - e.g.) Problem-Solving에 활용

- Backward Chaining은 Forward Chaining보다 Complexity가 낮음 (DFS 방법과 유사)

    - 즉 일반적으로 Backward Chaining은 Forward Chaining 보다 빠름 (효과적)

    - 하지만 Backward Chaining의 경우 Complete (완전성), Optimal (최적성)을 보장 못함

 

Resolution (분해법칙/도출원리)

추론규칙을 통해 증명(Proof)하기 위해서는 우선 주어진 지식이나 사실을 논리식으로 표현한 다음, 1) CNF(논리곱 표준형)으로 변환하고 2) Resolution(분해법칙) 및 논리적 동치 관계(Logically Equivalent)를 활용하여 논리식을 소거하면서 마지막으로 증명된 식이 참이거나 모순된 상황이 나오면 멈춤

 

■ CNF (Conjunctive Normal Form, 논리곱 표준형)

- 명제 P와 명제 부정의 ￢P를 리터럴(Literal)이라함 (P ∨ ￢P) = True (always)

- 리터럴들이 논리합(∨)으로만 연결되거나, 논리곱(∧)으로 연결되면 절(Clause)이라고 함

    - e.g.) P ∨ Q ∨ ￢R (논리합 절) / P ∧ Q ∧ ￢R (논리곱 절)

- 논리합 절들이 논리곱으로 연결되어 있으면 CNF라고 함

 

■ Resolution (분해법칙/도출원리)

- 두 개의 논리합 절이 같은 기호의 긍정과 부정의 리터럴을 서로 포함하고 있을 때, 해당 리터럴들을 제외한 나머지 리터럴들의 논리합절을 만들어 내는 것

P ∨ q, ￢P ∨ r ⊢ q ∨ r  ( 논리 도출식(resolvent) )

 

● Resolution을 활용한 증명(Proof)

- 다음 3가지 명제가 참이라고 주어져 있을 때 R이 참이라는 것을 증명하는 법

    P ∨ Q    P → R    Q → R

 

① CNF 적용

    (P ∨ Q) ∧ (￢P ∨ R) ∧ (￢Q ∨ R)

② 모순을 유도해내기 위해 증명할 명제 부정(R이 거짓)

    ￢R    (P ∨ Q) ∧ (￢P ∨ R) ∧ (￢Q ∨ R) ∧ ￢R

③ P ∨ Q와 ￢P ∨ R에 Resolution 적용

    Q ∨ R

④ Q ∨ R와 ￢Q ∨ R에 Resolution 적용

    R

모순 발생 (2번에서 명제를 부정) -> 즉 원래 명제 R은 참!!

 

Pros and Cons (명제논리의 장단점)

■ Pros (장점)

- 명제논리는 문맥이 독립적이고 모호하지 않은 선언적 의미론을 기반으로 함

    -> Syntax는 Fact(사실)에 해당

- 명제논리는 (대부분의 자료구조 및 데이터베이스와는 달리) 부분(partial), 분리(disjunction), 부정(negation) 정보를 허용

- 명제논리는 구성적(Compostional)임

 

■ Cons (단점)

- 명제논리는 (자연어와는 달리) 표현력이 매우 제한적임 (Limited Expressive Power)

-> "Pits(구덩이)와 인접한 칸에는 Breeze(미풍)이 분다"와 같은 문장을 표현하기 위해서는 각 칸마다 논리 형태로 표현해야 함 (e.g. B₁,₁ ⇔ ( P₁,₂ ∨ P₂,₁) )

 

2. 1차 논리 (First-order Logic)

1차 논리 (First-orderLogic, FOL)란?

● FOL, 술어논리(Predicate Logic) 이라고 함

- 명제(Proposition)의 내용을 다루기 위해 변수, 함수 등을 도입하고, 이들의 값에 다라 True, False가 결정되도록 명제논리를 확장한 논리

    -> 명제 논리의 경우 Facts만 포함

- FOL의 경우 아래의 요소들을 추가적으로 논리에 포함 가능

    - Objects (객체) : nouns(명사) and noun phrases(명사구)

    - e.g.) people, house, numbers, theories, Ronald McDonald, Colors, Baseball games, wars, centuries ...

- Relations (Predicate, 관계) : verbs (동사) and verb phrases(동사구)

- Functions(함수) : 주어진 input에 대해 오직 한가지 value(값)을 가질 수 있는 Relations

 

FOL의 Syntax와 Semantics

■ FOL의 Syntax(구문)

● Quantifiers (한정사)

- 전칭 한정사(Universal quantifier)

∀x P(x) is read as "For allx,P(x)" or "For every x, P(x)"

    - For all (모든 ...에 대해)

    - Syntax(구문)

        ∀ <variables> <sentences>

    - Semantics(의미)

        P가 임의의 논리식일때, '∀x P(x)라는 문장은 모든(all) 객체 x에 대해 P가 참이다'라는 것을 의미

    - 일반적으로, ⇒(Implication)은 ∀ 기호와 주로 연결되어 있음 (∧과 연결해서 사용하면 너무 강한 주장이 됨)

 

- 존재 한정사(Existential quantifier)

∃x P(x) is read as "For some x, P(x)", or as "There is an x such that P(x)," or "For at least one x, P(x)."

    - For some ... , or There exists (어떤 ...에 대해)

    - Syntax(구문)

        ∃ <variables> <sentences>

    - Semantics(의미)

        P가 임의의 논리식일 때, '∃x P(x)라는 문장은 일부(some) 객체 x에 대해 P가 참이다'라는 것을 의미

   - 일반적으로 ∧은, ∃기호와 주로 연결되어 있음 (⇒기호와 연결해서 사용하면 너무 약한 주장이 됨)

 

● Equality (상등)

- 2개의 terms(항)이 같다는 것을 보임 (원자적 문장)

    Father(John) ⇒ Henry

 

● BNF (Bacus-Naur Form)