3장을 시작하기 전에… AI의 두가지 접근법 연결주의 기호주의 연결주의(connectionism)와 기호주의(symbolism) 연결주의 McCulloch, Pitts, Hebb 등 신경망에 대한 연구 AI의 초기(40-60년대) 80년대 이후 중흥기(Hopfield, Rumelhart) “How does brain act”에 관한 연구 9장에서 신경망을 다룸 기호주의 McCarthy, Newell, Simon등 추론, 학습, 문제해결 등을 위한 지식의 표현 문제 AI의 초기부터 연구의 주류 “What does brain do”에 관한 연구 3장에서 지식의 표현에 대해 다룸

지식표현(Knowledge Representation) 지식은 인공지능에서 가장 핵심 지식표현 연구는 지식을 체계적으로 조직, 저장하고 이를 효율적으로 이용하도록 하는 방법의 연구 문제 영역이나 문제해결의 효율성을 위해 적절한 지식표현 방법을 선택하는 것이 매우 중요하다. 지식표현의 종류 논리(Logic) 의미망(Semantic Net) 프레임(Frame) 규칙(Rule) 객체지향 표현기법(Object-Oriented Representation)

논리(Logic) 논리 수학, 논리학에서 사용된 명제논리나 서술논리 사용 “If x is a bird, then x has wings”란 사실(규칙)의 표현  (x) {Is-a(x, Bird)  has(x, Wings)}  정형공식(wff: well-formed formular) 이해 장점 수학적인 근거를 바탕으로 논리개념을 자연스럽게 표현 지식의 정형화 영역에 적합(정리 증명 : theorem proving) 지식의 첨가와 삭제가 용이하고 단순 단점 절차적, 결정적 지식표현이 어렵다. 사실의 구성법칙이 부족하므로 실세계의 복잡한 구조를 표현하기 어렵다.

논리(Logic) 명제 논리 서술(술어) 논리 단위는 명제: 참, 거짓을 판별할 수 있는 문장 연결자: And, Or, Not, Implies, Equivalent복합문 예 명제 X가 참이고 명제 Y가 거짓이라면 “X And Y”는 거짓 서술(술어) 논리 단위는 하나의 객체(object) 객체에 대한 문장을 서술문(predicate) 연결자를 이용하여 하나의 서술문 작성 한정자 (Forall, Exists) 사용 “Canary is a Bird”  (Is-a Canary Bird) “If X is a Bird, Then X has Wings.”(Forall(X)(If(Is-a X Bird)(Has X Wings)))

항(Term)과 기초공식(Atomic Formula) 1) 상수, 변수는 항 2) 함수 f가 항 x를 인자로 가지면 f(x)는 항 3) 1), 2)에 의해 구성되는 것은 모두 항 기초공식 항을 인자로 가지는 서술어(predicate)는 모두 기초공식이다. Ex) Woman(MARY), Married(father(JOHN), mother(JOHN)) 정형공식(Wff : well formed formula) 1) 기초공식 F는 wff 2) F, G가 wff면, (F∨G), (F∧G), ∼F, (F→G), (F↔G)도 wff 3) F가 wff면, (∀x)F, (∃x)F도 wff 4) 1), 2), 3)의 과정에 의해서만 구성되는 것은 모두 wff

비교흡수 부정 비교흡수 부정(Resolution Refutation) 두개의 기초절(부모절(parent clause)이라 함)에서 P1 ∨P2 ∨ … ∨PN 과 ~P1 ∨Q2 ∨ … ∨ QM 이 두개의 부모절(parent clause)을 논리합을 취해서 새로운 비교흡수절(resolvent)을 생성(비교흡수) (P1∨ ~P1)∨(P2 ∨ … ∨PN ∨Q2 ∨ … ∨ QM) 항상 참값 비교흡수절 비교흡수 부정 방법 비교흡수 부정에서의 모든 절은 논리합으로만 된 정형공식 정형공식 집합 S에 특정 정형공식 X가 논리적으로 따름(logically follow)을 증명하기 위한 것 P=S∪{~X}  P에 대해 비교흡수 수행  비교흡수절 Ri 생성  P∪Ri에 대해 비교흡수 반복  모순(NIL)이 생성되면 종결

비교흡수부정의 이론 가정: S에 X가 논리적으로 따른다고 가정  S를 만족하는 모든 해석은 X를 만족(satisfy)함  S를 만족하는 모든 해석은 S∪{X}를 만족함(satisfiable)  S를 만족하는 모든 해석은 ~X를 만족하지 않음  S를 만족하는 모든 해석은 S∪{~X}를 불만족(unsatisfiable) 즉, 불만족인 집합내에는 어떤 절 Ci에 대해, Ci와 ~Ci가 공존하는 상황(모순)으로 볼 수 있다.  어떤 해석이 주어져도 Ci와 ~Ci를 동시에 만족할 수 없다  이러한 절들에 대한 비교흡수는 결국 NIL(모순) 생성  이는 S에 논리적으로 따르는 X를 부정(~X)한 결과는 모순을 초래하므로 결국 X는 S를 논리적으로 따른다

비교흡수를 위한 정형공식의 절 변환 1) Implication() 제거 Ex) A→B ≡ ~A∨B 2) Negation(~) 영역 축소 Ex) ~(A∨B) ≡ ~A∧~B 3) 각 한정기호에 고유한 변수를 가지도록 변수 표준화 Ex) (∀x)[P(x) →(∃x)Q(x)] ≡ (∀x)[P(x) →(∃y)Q(y)] 4) 존재한정기호(∃) 제거 (∀y)[(∃x)P(x, y)] : x는 y에 종속되어 결정 x를 y에 대한 어떤 함수로 표현: g(y) : Skolem 함수 (∀y)[P(g(y), y)]로 변환 5) Prenix 형으로 변환: 모든 전체한정기호(∀)를 정형공식 앞으로 내어 영역을 전체공식에 미치도록 함 6) 정형공식을 논리곱 정규형으로 변환 Ex) X1  (X2  X3) ≡ (X1  X2)  (X1  X3) 7) 전체한정기호를 모두 생략. 8) 논리곱을 생략. Ex) X1  X2 ≡ {X1, X2} 9) 각 절에서 같은 변수명이 없도록 조정

예)

실세계 문제 알고있는 사실 증명해야 할 사실 정형공식의 절 변환 읽을 수 있으면 글을 안다.→ (∀x)[R(x)⇒L(x)] 돌고래는 글을 모른다.→ (∀x)[D(x)⇒~L(x)] 어떤 돌고래는 지능이 있다.→ (∃x)[D(x) ∧I(x)] 증명해야 할 사실 지능이 있는 어떤 동물은 읽을 수 없다. → (∃x)[ I(x) ∧~R(x)] 정형공식의 절 변환 ~R(x) ∨L(x), ~D(y) ∨~L(y) (∃x)[D(x) ∧I(x)] → x가 종속되는 변수가 없다. → Skolem 함수는 없음 → Skolem 상수화 → x를 임의의 상수 A로 대치 → D(A) ∧I(A) → D(A), I(A)

목표공식의 부정에서 목표절 생성 비교흡수 부정의 적용 S ~X ~I(z)∨R(z) I(A) ~R(x) ∨L(x) (∃x)[I(x)∧~R(x)] → 부정 → ~(∃x)[I(x)∧~R(x)] → (∀x)[~I(x)∨R(x)] → ~I(x)∨R(x) → ~I(z)∨R(z) 비교흡수 부정의 적용 S ~X ~I(z)∨R(z) I(A) ~R(x) ∨L(x) ~D(y) ∨~L(y) D(A) {A/z} 비교흡수부정: A를 z에 대입 유도된 비교흡수절 R(A) {A/x} 비교흡수부정: A를 x에 대입 유도된 비교흡수절 L(A) {A/y} 비교흡수부정: A를 y에 대입 유도된 비교흡수절 ~D(A) 비교흡수부정: 상쇄 유도된 비교흡수절 NIL S  ~X가 Unsatisfiable =>X가 S에 논리적으로 뒤 따른다.

S = {~R(x) ∨L(x), ~D(y) ∨~L(y), D(A), I(A)} [A: 돌고래] ~X = ~I(z)∨R(z) P = S ∪ ~X = {~R(x) ∨L(x), ~D(y) ∨~L(y), D(A), I(A), ~I(z)∨R(z)} 첫번째 비교흡수부정: I(A) ∨ ~I(z)∨R(z)  {A/z} R(A) 유도된 비교흡수절 P = P ∪ R(A) = {~R(x) ∨L(x), ~D(y) ∨~L(y), D(A), I(A), ~I(z)∨R(z), R(A)} 두번째 비교흡수부정: R(A) ∨ ~R(x) ∨L(x)  {A/x} L(A) 유도된 비교흡수절 P = P ∪ R(A) = {~R(x) ∨L(x), ~D(y) ∨~L(y), D(A), I(A), ~I(z)∨R(z), R(A), L(A)} 세번째 비교흡수부정: L(A) ∨ ~D(y) ∨~L(y)  {A/y} ~D(A) 유도된 비교흡수절 P = P ∪ R(A) = {~R(x) ∨L(x), ~D(y) ∨~L(y), D(A), I(A), ~I(z)∨R(z), R(A), L(A), ~D(A)} 네번째 비교흡수부정: ~D(A) ∨ D(A)  {상쇄} NIL 유도된 비교흡수절 S  ~X가 Unsatisfiable =>X가 S에 논리적으로 뒤 따른다. A를 z에 대입

답의 유도 존재를 나타내는 변수가 무엇인가? 기초집합 S에 논리적으로 따르는 (∃x)W(x)에서 x가 구제적으로 무엇인가를 유도 비교흡수 부정 방법을 이용한 답 유도과정 1) 비교 흡수 부정과정에 의한 트리 생성 2) 목표절의 Skolem 함수의 변수는 새로운 이름으로 대치 3) 부정된 목표절과 이것의 부정된 절을 논리합하여 기초절에 추가 → 항진명제 → 기초절에 항상 참인 절을 추가해도 무관 4) 1)의 트리를 바탕으로 수정된 증명 트리 생성 5) 증명트리의 뿌리노드의 절이 답이 된다.

그림 3.2

그림 3.3

예제의 답 유도 지적이고 읽지 못하는 무엇이 있다면, 그것은 무엇인가? ~I(z)∨R(z)∨(I(z)∧~R(z)) I(A) 동치명제 = 목표정형공식∨ ~목표정형공식 기초절 ~I(z)∨R(z)∨(I(z)∧~R(z)) I(A) ~R(x) ∨L(x) ~D(y) ∨~L(y) {A/z} 비교흡수부정 D(A) 유도된 비교흡수절 R(A) ∨(I(A)∧~R(A)) {A/x} 비교흡수부정 유도된 비교흡수절 L(A)∨(I(A)∧~R(A)) {A/y} 비교흡수부정 유도된 비교흡수절 ~D(A)∨(I(A)∧~R(A)) 비교흡수부정 (I(A)∧~R(A)) 유도된 비교흡수절 답: 돌고래 A는 지능은 있으나 읽지는 못한다

제약조건만족 문제표현방식: 논리표현, 네트워크표현 문제풀이방법: 생성과 검사 방법, 역행방법, 일관성 알고리즘 Map coloring problem Cross word puzzle problem N-queens problem

의미망 의미망(Semantic Network) 지식, 인간의 기억, 실세계를 망 구조로 표현 노드에는 객체, 개념, 사건 등을 표현 링크는 노드들간의 관계를 묘사 구체, 절차, 인과, 부분 등의 객체 관계 표현 isa는 성질 계승(property inheritance) 링크 장점 매우 복잡한 개념이나 인과 관계 표현에 용이 단점 지식량이 커지면 복잡해짐 → 조작이 어려움

의미망의 예 has isa Bird Wings Organ isa Canary isa owns isa Baney Nest-1 Canary is a Bird. A Bird has Wings. Banney is a Canary. Banney owns a Nest. Wings is a Organ. has isa Bird Wings Organ isa Canary isa instance class owns isa Baney Nest-1 Nest

프레임 프레임(Frame) 의미망 한 종류로서 객체와 그 속성의 구조적 기술 프레임 객체 구조 내에 슬롯이라는 속성 묘사에 중점 데이터와 프로시저를 하나의 구조로 묶는다. 프레임들은 계층적으로 구성 슬롯(slot)은 객체의 속성과 속성값을 채우는 칸 디폴트값, 프레임 포인터, 규칙, 프로시저 프로시저는 슬롯 값 요구, 변경, 제거될 때 자동으로 작동되는 일종의 demon 패싯(facet)은 슬롯 값을 다양하게 줄 수 있는 키 Value, Default, Range, If-added, If-needed 등 프레임 표현 <프레임 이름>-<슬롯 이름>-<패싯 이름>-<값>

프레임 예 장점 단점 (FRAME Canary (Is-a (Value Bird)) (Color (Value Yellow)) (Can (Default Sing)) (Breed (Range Africa India)) (Length (If-added Calculate-width) (If-removed Erase-width-weight)) (Width (if-added Calculate-weight)) (Weight (If-needed Calculate-weight))) 장점 지식 표현이 일반적이고 자연스러우며 강력한 방법 단점 복잡성 때문에 지식작성이 어렵다.

규칙 규칙(Rule) 가정(if-part, LHS)과 결론(then-part, RHS)의 문장으로 표현 Ex) If (A and B) then (C) (A, B) → (C) 결정이나 결론이 요구되는 영역에 유용 규칙기반 시스템에서 사실집합과 규칙집합으로 구분되어 규칙의 가정부분이 사실집합의 일부와 부합될 때 규칙의 결론부분이 실행된다. 장점 모듈화. 독립적으로 추가, 삭제 변경 용이 특정 표현 방법에 따라 구조를 달리할 수 있다. 결정, 결론이 요구되는 영역에 적합 단점 문제풀이에 많은 경비 소요, 제어가 복잡

객체지향 개념 객체지향 (Object-Oriented) 개념 클래스와 객체, 인스턴스 클래스의 계층구조 계승, 다중계승, 재사용성 메시지, 메소드 캡슐화, 정보 은닉 객체 모델링 객체지향 언어의 장점 현실세계의 개념적 개체는 단일 개념의 객체로 묘사 가능 데이터 사이에 존재하는 일반화와 집단화를 쉽게 표현 multimedia 데이터 처리가 용이 시스템 설계 및 구축시 생산성 향상 동시 처리를 자연스럽게 지원 편리한 사용자 인터페이스 지원

지식 표현 이슈 모든 문제 영역에 필요한 아주 기본적인 속성이 있는가? 속성들 사이에 존재하는 관련성 지식 표현의 크기 정도(granularity) 결정 객체들의 집합 표현 적합한 구조