Ch.3 지식의 표현과 논리.

Presentation on theme: "Ch.3 지식의 표현과 논리."— Presentation transcript:

1 Ch.3 지식의 표현과 논리

2 Contents 지식이란? 지식의 종류 및 표현방법 논리를 이용한 지식 표현 의미 네트워크 프레임 프로덕션시스템
명제 논리 술어 논리 의미 네트워크 프레임 프로덕션시스템 객체 지향 개념

3 지식이란?(1) 데이터, 정보, 지식의 차이 이론화 지식 개념화, 구조화, 체계화 정보 정리 데이터 인지 또는 인식 감각기관
진리,정리, 법칙 이론화 지식 개념화, 구조화, 체계화 정보 정리 데이터 데이터(data) 현실 세계에서 단순히 관찰하거나 측정해 수집한 사실이나 값 정보(information) 의사 결정에 유용하게 활용할 수 있도록 데이터를 처리한 결과물 인지 또는 인식 감각기관 외부세계

4 지식이란?(2) 데이터, 정보, 지식의 차이 지식(knowledge) 지식의 특성 정보를 체계화, 개념화 한 것
이용할 수 있는 형태로 구조화 한 것 어떻게 구조화하는지는 지식의 이용목적에 따라 결정 지식의 특성 양이 많다 정확하게 나타내기 어렵다 끊임없이 변한다

5 지식의 종류 및 표현방법(1) 지식의 종류 사실(fact) 절차적 규칙 (procedural rules)
집적회로(Integrated Circuits)는 전원 단자와  GND(ground) 단자를 가진다. 보잉 747기는 세 개의 엔진으로 안전하게 날 수 있다. 절차적 규칙 (procedural rules) AND 게이트의 입력단자에 모두 논리 1을 가하면 출력은 논리 1이 된다. DC 모터(motor)에 직류전압을 높이 가할수록 회전수는 빨라진다. 경험적 규칙 (heuristic rules) 자동차의 전조등의 불빛이 약하면, 배터리(battery)의 전압이 낮다. 빛의 밝기가 급격히 변화하는 선형의  구조가 있으면, 이는 모서리이다.

6 지식의 종류 및 표현방법(2) 지식 표현(Knowledge representation) :
[정의]문제해결을 위한 지식을 컴퓨터에서 실행 가능한 형태로 나타내는 것 지식은 인공지능에서 가장 핵심 문제 영역이나 문제해결의 효율성을 위해 적절한 지식 표현 방법을 선택하는 것이 매우 중요

7 지식의 종류 및 표현방법(3) 지식 표현의 조건 (1) 정확한 표현 (2) 효율적인 추론이 가능하도록 표현
(3) 새로운 지식의 획득, 효율적인 수정 및 삭제가 가능하도록 표현 (4) 일반성 가질 수 있도록 표현 (5) 사람이 이해하기 쉽도록 표현

8 지식의 종류 및 표현방법(4) 지식 표현 기법 분류 논리를 이용한 지식 표현 규칙을 이용한 지식 표현
명제 논리, 술어 논리 규칙을 이용한 지식 표현 네트워크를 이용한 지식 표현 Semantic Net, Conceptual Dependency Graph 구조적인 지식 표현 Frame, Script

9 지식의 종류 및 표현방법(5) 지식 표현방법의 비교 논리 규칙 네트워크 프레임 창안자 Peano Newell Quilian
논리 규칙 네트워크 프레임 창안자 Peano Newell Quilian Minsky 표현 방법 정형식 (wff) IF(조건) THEN(결론) 대상물간의 관계로써 표현 Slot-Filler 구조 이용 장점 - 지식 삽입 삭제 수정용이 - 효과적,정확한 추론 - 표현의 자연스러움 다양한 추론 방법 가능 - 절차적 표현 가능 - 복잡한 관계표현 용이 - 표현이해 용이 - 사건표현에 유리 단점 - 지식표현의 부자연스러움 표현된 지식의 이해가 어려움 상태공간상에서 상태 수 과다 - 과다한 규칙의 존재 - 규칙 충돌 가능성 - 정형화의 어려움 - 문제풀이 방법 부족 - 규칙간관계 복잡성 - 제어흐름의 모호성 - 규칙추출의 어려움 적용 분야 수학분야(정리증명) 전문가시스템 자연어 처리

10 논리를 이용한 지식 표현(1)

11 논리를 이용한 지식 표현(1) 명제논리 (Propositional Logic) Connectives
기본명제(proposition, atom) 의미가 참 혹은 거짓으로 구분이 가능한 문장(also called formula) 예) 명제들을 연결자(connectives)들로 연결하여 새로운 명제 생성 Connectives P: this book is boring Q: if this book is boring, then I’ll fall asleep R: there are lives on the other planets except the earth connectives meaning Ú Or Ù And ~ Not Implies(if…then) If and only if (iff)

12 논리를 이용한 지식 표현(2) 명제논리 (Propositional Logic)
정형식(Well formed formula (wff) or formula) a) all constant (propositional letters) are formulas b) if P is a formula, so is (~P) c) if P and Q are formulas, so are (P Ú Q), (P Ù Q) (P ® Q) and (P «Q) d) all formulas are obtained in this manner P, Q, R (P Ú Q), (P Ù Q), (P ® Q) and (P «Q) ((~P) ® R)), (((P Ù Q) « (P ® Q)) Ù R ) … (예)

13 논리를 이용한 지식 표현(3) 명제논리 (Propositional Logic)
리터럴(literal) : 기본명제와 그 부정(~) 정형식의 해석(interpretation) :정형식을 구성하고 있는 atom들에게 T, F를 지정하는 과정 의미(meaning) : 해석을 통해서 얻은 정형식의 마지막 진리값 정규형(normal form) 1) 논리합 정규형(disjunctive normal form : DNF) : F = F1  F2    Fn Fi = L1  L2    Lm , Li : 리터럴 2)논리곱 정규형(conjunctive normal form : CNF) : F = F1  F2    Fn Fi = L1  L2    Lm, Li : 리터럴 절(clause) : 리터럴들의 논리합(disjunction of literals) 절형식(clause form) : 절들의 논리곱(conjunction of clauses), 논리곱 정규형(CNF)

14 논리를 이용한 지식 표현(4) 명제논리 (Propositional Logic) De Morgan’s Law
연결자 (connectives) 에 의한 명제의 진리표 De Morgan’s Law Implication P Q ~ P P Ú Q P Ù Q P ® Q P « Q T F ~(P Ú Q)  (~ P Ù ~ Q) ~(P Ù Q)  (~ P Ú ~ Q) (P ® Q)  (~ P Ú Q) (P ↔ Q)  (P → Q) ∧ (Q → P)

15 논리를 이용한 지식 표현(5) 1, 0 Logic instead of T, F P Q ~ P P Ú Q P Ù Q P ® Q

16 논리를 이용한 지식 표현(6) 명제논리 (Propositional Logic) 임의의 wff를 정규형으로 변환하는 방법
1) 와  제거 2) ~ 의 범위 축소 3) 분배법칙 적용 ex) (P  Q)  (Q  R)  ~(~P  Q)  (~Q  R)  (P ~Q)  (~Q  R)  (P ~Q)  ~Q  R : 논리합 정규형 (P  ~Q)  (~Q  R)  (P  ~Q  R)  (~Q  ~Q  R)  (P  ~Q  R)  (~Q  R) : 논리곱 정규형

17 논리를 이용한 지식 표현(7) P  Q ~P  R 명제논리 (Propositional Logic)
도출원리(resolution principle) : 1965년, Robinson clause 형태에 적용 가능한 추론규칙 비교흡수원리 도출(resolution) 부모절(parent clause) 도출절(resolvant) P  Q ~P  R Q  R

18 논리를 이용한 지식 표현(8) 명제논리 (Propositional Logic) P  Q ~P  Q 2) 병합(merge)
추론규칙 1) 모더스 포넌스(modus ponens) P  Q ~P  Q P P Q Q 2) 병합(merge) P V Q ~ P V Q Q 3) 항진(tautology) P  Q ~P  ~Q Q  ~Q = T

19 논리를 이용한 지식 표현(9) 명제논리 (Propositional Logic) 추론규칙-con’d
4) 모순(contradiction) P ~P ----- F 논리적 결과(logical consequence), 논리적으로 따른다(logically follows) : G가 F1, F2,  , Fn 의 논리적 결과  F1 F2    Fn 를 참으로 하는 모든 해석에 대해 G도 참 5) 연쇄(chaining), 삼단논법(syllogism) P  Q ~P  Q Q  R ~Q  R P  R ~P  R

20 논리를 이용한 지식 표현(10) 명제논리 (Propositional Logic)
G가 F1, F2, , Fn 의 논리적 결과임을 증명하는 방법 1) F1 F2    Fn  G 가 항진명제 임을 보임 2) F1 F2    Fn  ~ G 가 모순명제 임을 보임

21 논리를 이용한 지식 표현(11) 명제논리 (Propositional Logic)
도출 반박(resolution refutation)에 의한 정리 증명 (비교흡수부정) S : 사실을 나타내는 절 집합 X : 목표를 나타내는 단일절 X가 S의 논리적 결과  S {~X} 가 모순(거짓)  S {~X} 에 대해 도출을 반복하면 모순(NIL) 이 유도됨

22 논리를 이용한 지식 표현(12) 명제논리 (Propositional Logic) 도출반박(비교흡수부정)의 이론
가정: 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를 논리적으로 따른다

23 논리를 이용한 지식 표현(13) 명제논리 지식 표현과 추론 예 지식표현 Predicates 정의 it is hot : P 예제
Facts: If it is hot and humid, then it will rain. If it is humid, then it is hot. It is humid now. Question: Will it rain? 지식 표현 Predicates 정의 it is hot : P it is humid : Q it will rain : R 지식표현 F1: (P∧Q)  R F2: Q  P F3: Q Goal : R

24 논리를 이용한 지식 표현(14) 명제논리 지식 표현과 추론 예- con’d Deduction Theorem
Given F1, F2, …Fn, G, G is a logical consequence of F1, F2, …Fn iff (F1∧ F2∧… ∧ Fn)  G :True or ~(F1∧ F2∧… ∧ Fn)∨G :True or (F1∧ F2∧… ∧ Fn∧~G) :False 추론 (F1∧ F2∧… ∧ Fn∧~G) = {(P∧Q)  R} ∧ {Q  P} ∧ Q ∧ ~R = False ∴ Goal : R(It will rain) is True. F1: (P∧Q)  R F2: Q  P F3: Q Goal : R

25 논리를 이용한 지식 표현(15) 명제논리 지식 표현과 추론 예- con’d Resolution Refutation Alg.
1. 명제  wff  CNF( (•∨•∨•)∧.. ∧(•∨•∨•) )  Clauses 2. ~Goal을 Clause set에 추가 3. Resolve any two clauses For any two clauses C1, C2, if there is a literal L in C1 and ~L in C2, then delete L, ~L from C1, C2, and construct the disjunction of the remaining clauses. 4. If contradiction, then Goal is true else go to step 3.

26 논리를 이용한 지식 표현(16) 명제논리 지식 표현과 추론 예- con’d C4: ~R C1: ~P∨~Q∨R
추론 (by R.R.A.) F1: (P∧Q)  R ≡ (~P∨~Q∨R) : C1 F2: Q  P ≡ (~Q∨P) : C2 F3: Q : C3 ~Goal: ~R : C4 F1: (P∧Q)  R F2: Q  P F3: Q Goal : R C4: ~R C1: ~P∨~Q∨R C5: ~P ∨~Q C2:~Q∨P C6: ~Q C3: Q Contradiction

27 논리를 이용한 지식 표현(17) 술어 논리(Predicate Logic)
문장의 내부구조까지 논리적으로 표현할 수 있고 높은 표현력이 있으므로 인공지능의 다양한 문장을 정의할 수 있는 논리 1) 기본성분 - 항(term) : 개체(entity) 표현 ① 상수(constant) : 사물(물건, 사람, 개념 등) 표시 대문자나 숫자를 선두로 하는 짧은 string으로 표시. ex) A1, MARY, 3A ② 변수(variable) : 지시하고자 하는 사항을 불명확하게 사용하고자 할 때 소문자로 표시. ex) x, y, z ③ 함수(function) : 함수관계를 소문자로 표시. ex) father(MARY), f(t1,t2,‥‥,tn) - 술어(predicate) : 객체의 성질이나 객체와 객체간의 관계를 표현 대문자를 선두로 하는 짧은 string으로 표시. ex) MAN(x), LIKES(A, B)

28 논리를 이용한 지식 표현(18) 술어 논리(Predicate Logic) 2) 기본 구성요소(Building block)
- 기본식(기초공식, 원소)(atom, atomic formula) : 항을 인자로 가지는 술어(predicate)는 모두 기본식 P : predicate t1,t2, , tn : term P(t1,t2, , tn) : atom ex) WOMAN(MARY) MARRIED(father(JOHN), mother(JOHN)) - 리터럴(literal) : atom or its negation - 논리적 연결자(logical connectives) : ~, , , ,  - 한정자(한정기호)(quantifier)  (for all) : 전체한정자(universal quantifier)  (there exist) : 존재한정자(existential quantifier)

29 논리를 이용한 지식 표현(19) 술어 논리(Predicate Logic)-example " x ( P(x) ® Q(x) )
$x (P(x) ) ∧ " x (Q(x)) ($x P(x))∨Q(x) º ($y P(y))∨Q(x) ($x (" x P(x)) ® Q(x)) º ($x (" y P(y)) ® Q(x)) "John lives in a yellow house“ LIVE(JOHN,HOUSE) ∧ COLOR(HOUSE,YELLOW) All men have a human mother " x ( MAN(x) ® HAS_HUMAN_MOTHER(x) ) There is a man who has a human mother $x ( MAN(x) ∧ HAS_HUMAN_MOTHER(x) ) All men’s mother is human " x ( MAN(x) ® HUMAN(mother(x)) )

30 논리를 이용한 지식 표현(20) 술어 논리(Predicate Logic)-example
정형식(정형공식, 논리식) (well-formed formula, wff) ① atom은 wff ② P, Q가 wff 일 때, ~P, ~Q, (P  Q), (P  Q), (P  Q), (P  Q)는 wff ③ P : wff, x : variable xP(x), xP(x) 는 wff ① ② ③ 에 의해서 구성되는 것은 모두 wff 스콜렘화(skolematization) : 정형식에서 존재변수를 제거하는 것 ① 존재변수의 스콜렘 상수화 존재변수 y가 전체변수 x에 대해 독립적일 때, y를 상수로 치환 ② 존재변수의 스콜렘 함수화 존재변수 y가 전체변수 x에 종속할 때, y를 x를 인수로 하는 스콜렘 함수 y = f(x)로 치환

31 논리를 이용한 지식 표현(21) 술어 논리(Predicate Logic)
3) 도출원리(resolution principle) : Robinson(1965) 비교흡수원리 clause 형태에 적용 가능한 추론규칙 - 임의의 서술논리 형태에 도출원리를 적용하기 위해서는 clause 로의 변환, 단일화(unification)과정 필요 도출(resolution) 부모절(parent clause) 도출절(resolvant)

32 논리를 이용한 지식 표현(22) 술어 논리(Predicate Logic)
도출연역(비교흡수)를 위해 임의의 정형식을 절(clause)로 변환하는 방법 1) Implication(→) 제거, Eqivalence(↔) 제거 ex) A→B ≡ ~A∨B 2) Negation(~) 영역 축소 ex) ~(A∨B) ≡ ~A∧~B , ~(A∧B) ≡ ~A∨~B 3) 각 한정자에 고유한 변수를 가지도록 변수 표준화 ex) (∀x)[P(x) →(∃x)Q(x)] ≡ (∀x)[P(x) →(∃y)Q(y)] 4) 존재한정자(∃) 제거 (∀x)[(∃y)P(y, x)] : y는 x에 종속되어 결정 y를 x에 대한 어떤 함수로 표현: g(x) : Skolem 함수 (∀x)[P(g(x), x)]로 변환 5) 관두형(prenix형)으로 변환: 모든 전체한정자(∀)를 정형식 앞으로 내어 영역을 전체 공식에 미치도록 함 x1 x2  xn (M) prefix(접두사) matrix(한정자가 없는 식) 6) 정형식을 논리곱 정규형(CNF, Clause form)으로 변환(분배법칙) ex) X1 v (X2 ∧ X3) ≡ (X1 v X2) ∧ (X1 v X3) 7) 전체한정자(∀)를 모두 생략. 8) 논리곱(∧)을 생략. Ex) X1 ∧X2 ≡ {X1, X2} 9) 각 절에서 같은 변수명이 없도록 조정(변수 표준화)

33 논리를 이용한 지식 표현(23) 술어 논리(Predicate Logic)-example

34 논리를 이용한 지식 표현(24) p = Knows(John,x) 단일화(unification)
치환을 해서 두 문장 P, Q를 같은 문장으로 만드는 과정 Example: p = Knows(John,x) q = Knows(John, Jane)  = {Jane/x} 치환(substitution) : 리터럴 안의 변수값을 다른 term(상수, 함수, 다른 변수)으로 바꾸는 것  = { t1/v1, t2/v2,  , tn/vn} ti : term vi : variable

35 논리를 이용한 지식 표현(25) 단일화(unification) 표현 E에 치환  적용 : E  or (E)
ex)  = {A/x, f(B)/y, C/z} E1 = P(x, y)  ~ Q(y, z) E2 = P(x, y, z) E1  = P(A, f(B))  ~ Q(f(B), C) E2  = P(A, f(B), C) : 기저예(ground instance)

36 논리를 이용한 지식 표현(26) 단일화(unification) - con’d
치환 가 표현의 집합(E1, E2,  , En) 의 단일자(unifier)  E1 = E2 =  = En 표현들은 단일화가능(unifiable) 단일자 가 가장 일반적인 단일자(most general unifier: mgu)  다른 단일자 에 대해    =  가 되는 치환  존재 ex) P(A, y), P(x, f(z)) 단일자(unifier) = {A/x, f(z)/y} :  (mgu) or {A/x, f(A)/y, A/z} = {A/z} or {A/x, f(f(A))/y, f(A)/z} = {f(A)/z}

37 논리를 이용한 지식 표현(27) Resolution 기초절(ground clause)에 대한 resolution
정의) 기초항(ground term) : term with no variable 기초절(ground clause), 기초 리터럴(ground literal) If clauses C1 contains L1 and C2 contains L2 and L2 = ~ L1 then resolvent (도출절) of C1 and C2 = (C1 - L1)  (C2 - L2) 일반적인 resolution 부모절 {Li} {Mi}, {li}  {Li} {mi}  {Mi}, mi = ~ li {li}{mi} 에 대한 mgu  도출절 = {{Li} - {li}} {{Mi} -{mi}}

38 논리를 이용한 지식 표현(28) resolution con’d
ex) Li = P(x, f(A))  P(x, f(y))  Q(y) Mi = ~ P(z, f(A))  ~Q(z) {Li} = {P(x, f(A)), P(x, f(y)), Q(y)} {Mi} = {~ P(z, f(A)), ~ Q(z)} {li} = {P(x, f(A))} {mi} = {~ P(z, f(A))} {li}{ ~ mi} 에 대한 mgu  = {z/x} {{Li} - {li}} = {P(z, f(y)), Q(y)} {{Mi} -{mi}} = { ~ Q(z)} 도출절 = P(z, f(y))  Q(y)  ~ Q(z)

39 논리를 이용한 지식 표현(29) 도출반박(비교흡수부정)(resolution refutation)에 의한 정리증명
{x}가 S를 논리적으로 따를 경우 : S가 true가 되는 모든 해석에서는 {x}도 true S가 false가 되는 모든 해석에서는 { ~ x}는 true  S {~x}: false  반복해서 도출연역하면 모순(NIL)에 도달 NIL : 결과의 절이 없음을 나타냄(부모들간의 모순) S = { S1, S2, , Sn} C = { S1, S2, , Sn, ~x} : 기본집합 (1) 절집합 C에서 두개의 절로부터 도출절 rij를 구해 C에 더해 새로운 절집합 만듬 (2) 절차 (1)을 반복해서 NIL이 유도되면 C는 모순

40 논리를 이용한 지식 표현(30) 유도그래프(derivation graph) 반박트리(refutation tree)
node : clause Ci, Cj로 부터의 도출절 rij 는 새로운 node가 됨 Ci, Cj : parent rij : descendent 반박트리(refutation tree) 도출반박을 나타내는 트리 NIL이 root 유도그래프를 확장시켜 root가 NIL이 되면 stop

41 논리를 이용한 지식 표현(31) 실세계 문제 알고있는 사실 증명해야 할 사실 정형식의 절 변환
읽을 수 있으면 글을 안다.→ (∀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)

42 논리를 이용한 지식 표현(32) 실세계 문제 con’d 목표공식의 부정에서 목표절 생성
(∃x)[I(x)∧~R(x)] → 부정 → ~(∃x)[I(x)∧~R(x)] → (∀x)[~I(x)∨R(x)] → ~I(x)∨R(x) → ~I(z)∨R(z) 도출반박(비교흡수 부정)의 적용 ~I(z)∨R(z) I(A) ~R(x) ∨L(x) ~D(y) ∨~L(y) D(A) R(A) L(A) ~D(A) NIL S ~X {A/z} {A/x} {A/y}

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

44 논리를 이용한 지식 표현(34) 예제의 답 유도 지적이고 읽지 못하는 무엇이 있다면, 그것은 무엇인가?
~I(z)∨R(z)∨(I(z)∧~R(z)) I(A) ~R(x) ∨L(x) ~D(y) ∨~L(y) D(A) R(A) ∨(I(A)∧~R(A)) L(A)∨(I(A)∧~R(A)) ~D(A)∨(I(A)∧~R(A)) (I(A)∧~R(A)) {A/z} {A/x} {A/y} 답: 돌고래 A는 지능은 있으나 읽지는 못한다

45 논리를 이용한 지식 표현(35) 술어논리 지식표현과 추론 예 Predicates 정의 지식표현
예제 Facts: Every man is mortal Socrates is a man. Question: Socrates is mortal? 지식표현 Predicates 정의 MAN(x) : x is a man. MORTAL(x) : x is mortal. 지식표현 F1: (∀x) (MAN(x)  MORTAL(x)) F2: MAN(Socrates) Goal : MORTAL(Socrates) ?

46 논리를 이용한 지식 표현(36) 술어논리 지식표현과 추론 예- con’d C3: ~MORTAL(Soc)
추론 (by R.R.A.) F1 : ~MAN(x)∨MORTAL(x) : C1 F2 : MAN(Soc) : C2 ~Goal : ~MORTAL(Soc) : C3 F1: (∀x) (MAN(x)  MORTAL(x)) F2: MAN(Socrates) Goal : MORTAL(Socrates) ? C3: ~MORTAL(Soc) C1: ~MAN(x)∨MORTAL(x) C4:~MAN(Soc) C2: MAN(Soc) Contradiction

47 논리를 이용한 지식 표현(37) 논리표현의 특징 <장점> 1) 수학적인 근거를 바탕으로 논리개념을 자연스럽게 표현
2) 세부적이고 정확하고 이해하기 쉽게 표현가능 3) 선언적 지식표현 방법이므로 모듈성이 뛰어나 지식삽입, 삭제 용이 4) 정형화 과정 명확(정리 증명 : theorem proving) <단점> 1) 절차적 지식표현이 어렵다. 2) 대규모 지식베이스의 경우, 추론과정에서의 조합에 의한 폭발 초래 3) 현실세계의 불확실한 지식 표현이 어렵다.

48 의미 네트워크(1) 1968년 Quillian 인간의 장기기억의 심리학적인 모델로 제안 예제 비디오

49 의미 네트워크(2) 구성 1) 노드(node) : 물체(object), 사건(event),
Ross Quillian 1966, 박사논문으로 Carnegie Institute of Technology (지금의 CMU) 에서 의미망 (Semantic Network) 을 발표하다. 구성 1) 노드(node) : 물체(object), 사건(event), 상황(situation), 개념(concept) 2) 아크(arc) : 노드간의 관계(relationship) - 구체, 절차, 인과, 부분 등의 객체 관계 표현 - ISA는 성질 계승(property inheritance) 아크 - 아크에는 방향을 나타내는 화살표가 있는데, 추상적으로 낮은 개념에서 상위의 개념으로 향한다 - 아크에는 두 노드 사이의 관계의 성질을 표현하는 라벨 (Label) 이 붙는다

50 의미 네트워크(3) example1 Bird Wings Organ Canary Banney Nest-1 Nest
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 OWNS ISA Banney Nest-1 Nest

51 의미 네트워크(4) example2 ISA 관계 : 노드간의 상하관계 표현
HAS-A( IS-PART, PART-OF, HAS-PART) 관계 : 구성요소, 부분 , 특성 Furniture Chair My- Chair Leather Me Tan Leg Brown Person ISA Has-part Color Covering Owner

52 의미 네트워크(5) 컴퓨터 표현 LISP 표현 속성-값(attribute-value)의 메모리구조로 표현
LISP 언어에서는 P-List(property list)구조로 표현 LISP 표현 ATOM PROPERTY LIST CHAIR ((ISA FURNITURE) (HAS-PART LEG)) MY-CHAIR ((ISA CHAIR) (COLOR TAN) (COVERING LEATHER) (OWNER ME)) ME ((ISA PERSON)) TAN ((ISA BROWN))

53 의미 네트워크(6) 서술논리 형태로 표현 ISA(CHAIR, FURNITURE) ISA(ME, PERSON)
COVERING(MY-CHAIR, LEATHER) COLOR(MY-CHAIR, TAN) (1) 성질의 계승(property inheritance) - 하위노드가 상위노드의 속성을 상속 - ISA, HAS-PART : 추이적(transitive) ISA(X, Y) ∧ ISA(Y, Z)  ISA(X, Z) HAS-PART(X, Y) ∧ HAS-PART(Y, Z)  HAS-PART(X, Z)

54 의미 네트워크(7) 서술논리 표현 - con’d (2) 의미네트워크의 이용 추론(inference)
1) 상속(inheritance) : 암묵추론, 디폴트추론(default reasoning) (ex) 앞의 의미네트워크 예에서 “My-Chair는 다리를 가지고 있다” 라는 새로운 사실 추론 2) 패턴 매칭(pattern matching) : matching network structure 질문을 network fragment(목표 네트워크)로 표현, 사실 네트워크와 패턴 매칭

55 의미 네트워크(8) 서술논리 표현 - con’d example
TRIGGER HORSE MAMMAL ANIMAL TAIL BLACK ISA Color HAS-PART TRIGGER is black, also has tail.(property inheritance) Query : “What kind of black mammal has a tail and is named TRIGGER? 질문을 network fragment로 표현

56 의미 네트워크(9) network fragment
TAIL HAS-PART ISA ISA TRIGGER ? MAMMAL Color BLACK ? would be bound to HORSE to satisfy the query. match 되는 것이 없으면 no.

57 의미 네트워크(10) 의미네트워크의 특징 <장점> 1) 선언적 지식표현 방법
2) 매우 복잡한 개념이나 인과 관계 표현에 용이 3) Module성이 좋음 → 지식의 추가나 수정이 용이, 표현과정이 유연 4) 개념의 계층적 표현에 적합 <단점> 1) 정형적으로 뚜렷한 표현 구조 없음 2) 지식량이 커지면 복잡해짐 → 조작이 어려움 3) 추론의 실행과 함께 동적으로 지식을 변화 시킬 필요가 있는 경우, 네트워크 갱신을 위한 특별한 기구 필요

58 프레임(1) 1974년 Minsky 제안 프레임 : 인간 두뇌가 지식을 구조화한 형태로 기억하는 단위
인간의 기억과 인지과정을 모델화하기 위한 지식표현 방법 보편적인 개념 및 상황을 나타내는 표현 방법 대상 중심 표현(object centered representation)

59 Marvin Minsky - “인간은 생각하는 기계다.”
인공지능의 개념을 창시해 ‘인공지능의 아버지’로 불리는 마빈 민스키 미국 매사추세츠공대(MIT) 명예교수가 생전에 남긴 말이다. ‘지식 표현의 프레임워크(A Framework for Representing Knowledge)’ 1974년 발표한 이론 인간의 지식을 프레임이라는 데이터 구조로 표현하고 언어 이해, 패턴 인식, 문제 해결 등과 같은 지적 활동을 외부로부터 입력된 데이터와 내부 프레임의 상호작용으로 보는 연구 방식이다.

60 프레임(2) 프레임의 기본구조 대상 및 대상을 기술하는 속성(attribute)과 속성 값들의 모임
속성을 슬롯(slot) 이라 함 프레임의 구성 1) 프레임 명 : 대상 2) slot : 대상이 가지고 있는 특성 3) facet : data가 어떤 형식으로 구성되어 있는지 표시 4) data : facet명으로 표시된 형으로 기술 프레임 시스템 : domain을 표현하기 위한 interrelated frame 집합으로 이루어짐

61 프레임(3) 프레임(Frame) 데이터와 프로시저를 하나의 구조로 묶는다. slot은 객체의 속성과 속성 값을 채우는 칸
디폴트 값, 프레임 포인터, 규칙, 프로시저 프로시저는 slot 값 요구, 변경, 제거될 때 자동으로 작동되는 일종의 demon(computer program) facet은 slot값을 다양하게 줄 수 있는 키 Value, Default, Data type, Range, If-added, If-needed, If-removed 등 프레임 표현 <프레임 이름>-<슬롯 이름>-<패싯 이름>-<값>

62 프레임(4) slot이 가질 수 있는 것 1) 값, default 값(미리 정해진 값)
2) 다른 slot을 지정해 주는 pointer 3) 값을 만들어 주는 규칙(rule) 4) 계산절차(procedure) : slot의 값이 요구되거나 변하거나 제거될 때 자동적으로 작동되는 demon ① If-added procedure(slot에 새로운 정보 저장될 때 수행) ② If-removed procedure(정보가 slot에서 제거될 때 수행) ③ If-needed procedure(slot에 정보가 필요할 때 수행) 5) lower-level, higher-level frame에 관한 사항(ISA hierarchy) Though a datum is not specified in a slot, the system can system can still get it by consulting knowledge given in other slots when it is needed. For example, if the age of a person is not declared in as slot, but his birthday is declared in another slot, then an IF-NEEDED function will calculate the desired age by subtracting the birthday from the current date. IF-ADDED function can be used to screen erroneous values before they are added to slots. For example, an IF-ADDED function might accept a number as the age of a person only if it is less than 150 and greater than 0.

63 프레임(5) 절차의 부가 facet : sub-slot ① value facet ② data-type facet
③ range facet ④ default facet 절차의 부가 demon : 시스템이 상태를 감시하여 조건이 만족되면 자동적으로 호출되어 실행되는 절차 servant : 사용자의 지시에 따라 기동되는 절차

64 프레임(6) 프레임 예 (FRAME Canary (Is-a (Value Bird)) (Color (Value Yellow))
(Can (Default Sing)) (Breed (Range Africa India)) (Length (If-added Calculate-length) (If-removed Erase-width-weight)) (Width (if-added Calculate-width)) (Weight (If-needed Calculate-weight)))

65 패싯 프로시져 예 FRAME 성인남자 ako 인간 *연령 *키 (내정값=170) *체중 (내정값=65) (IF-needed :
IF 연령 >35 THEN 체중 <- (키 – 100) ELSE 체중 <- (키 – 110) : ) *결혼관계 (IF-written : IF 결혼관계 = 기혼 THEN 배우자이름을 질문하여 슬롯 배우자에 넣는다. 해당되는 배우자 프레임에서 배우자 슬롯에 이 프레임의 이름을 넣으라는 메시지를 보낸다. ) *배우자 When-needed프로시저 동작 When-written프로시저 동작

66 프레임(7) 성질계승 하위 프레임이 상위 프레임이 가지고 있는 성질 계승 복수의 부모 프레임을 갖는 경우 다중상속
ex) 감기 프레임은 상위 프레임인 질병 프레임의 속성 상속 프레임은 지식의 선언적, 절차적 표현 프레임 시스템은 의미 네트워크의 일종 : 의미네트워크의 노드가 프레임

67 프레임(8) 추론 개념의 전형적인 예를 프레임으로 표현, 이 지식을 이용해서 새로운 사건 해석, 문제 해결
새로운 상황에 직면하면 pattern matcher를 통해 호출된 프레임을 사용할 수 있는지 추론(기존 지식에 바탕, 새로운 지식 추론) ① empty slot 을 default값으로 채움 새로운 상황에서 아직 관측되지 않은 사실의 추론 ex) 자동차라는 것을 알았으면 wheel을 가지고 있다는 사실 추론 ② using rules frame에 관한 성질을 추론하기 위해 slot의 값을 알아보는 rule 사용

68 프레임(9) 프레임의 특징 <장점> 1) 문제영역에 대한 정보를 정확히 표현-선언적, 절차적
2) 시스템을 쉽게 확장, 유지할 수 있는 정보의 modularity 가능 3) 속성이 가질 수 있는 값에 대한 제한이 가능(facet) 4) 정보의 상속성 5) 문제영역이나 목적에 따른 추론기구의 자유로운 설계 가능 <단점> 1) 복잡성 때문에 지식작성이 어렵다 2) 지식간의 통일성, 완전성의 검증 곤란 3) 추론방법이 고정되어 있지 않아 시스템 설계자의 부담이 큼

69 Semantic Net and Frame(1)
Example subset Sports Car doors: 2 Automobile doors: 4 Wheels: 4 engine: G. Engine fuel: gasoline cylinders: ? containment member member member My Car owner: Lee I.C. Engine cylinders: 6 Your Car doors: 5 owner: Kim engine: containment

70 Semantic Net and Frame(2)
Example – con’d Inference with semantic nets and frames Automobile doors: 4 Wheels: 4 engine: Sports Car doors: 2 subset G. Engine fuel: gasoline cylinders: ? containment My Car owner: Lee member Your Car doors: 5 owner: Kim I.C. Engine cylinders: 6 How many wheels does My Car have? How may doors does Who is the owner of My Car? What kind of fuels does My Car use? How may cylinders does Your Car have? 예제 비디오 (프레임 시스템) 예제 비디오 (프레임 기반 지식표현)

71 프로덕션시스템(1) 프로덕션 시스템이란? ex) If (A and B) then (C) (A ^ B) → (C)
규칙(rule)(생성규칙(production rule)) : 조건과 행동의 쌍(condition-action pair) IF 부분 : 조건부(condition part, antecedent, LHS) 만족되어야 하는 조건들의 논리곱(AND) 또는 논리합(OR) THEN 부분 : 행동부(action part, consequent, RHS) 조건의 만족시 수행되는 행동 조건이 참이 되면 규칙이 trigger되어 결론 수행(fire) 결론부도 AND, OR로 연결 가능 ex) If (A and B) then (C) (A ^ B) → (C) 결정이나 결론이 요구되는 영역에 유용 프로덕션 시스템에서 사실집합과 규칙집합으로 구분되어 규칙의 가정부분이 사실집합의 일부와 부합될 때 규칙의 결론부분이 실행된다.

72 프로덕션시스템(2) Example 형식 : IF(조건1∧.. ∧조건n) THEN (결론부)
x가 y의 부모이고, y가 z의 부모이면 x가 z의 조상이다. 지식표현 Predicates 정의 PARENT(x,y) : x is a parent of y. ANSCETOR(x,y) : x is a ancestor of y. 지식표현 Rule: IF (PARENT(x,y) ∧ PARENT(y, z) THEN ANCESTOR(x,z)

73 프로덕션시스템(3) 프로덕션 시스템의 구성요소 인식 행동 사이클(recognition action cycle)
① 프로덕션 메모리(production memory) : rule base 생성규칙 들의 모임 ② 작업메모리(working memory) : 정보의 일시적 기억장소 (short-term memory buffer) global database ③ 인터프리터(interpreter) : 시스템의 운영 관장, 추론기구, 실행기구, 추론엔진(inference engine) 인식 행동 사이클(recognition action cycle) ① 패턴인식(pattern recognition) ② 경합해소(conflict resolution) : 규칙 충돌 해결 ③ 실행(action) : 수행(execution)

74 프로덕션시스템(4) 프로덕션 시스템의 실행 방법
① 전향추론(forward reasoning, forward chaining): 전제 구동형 추론(antecedent driven reasoning) ② 후향추론(backward reasoning, backward chaining) : 결론 구동형 추론(consequent driven reasoning)

75 프로덕션시스템(5) 프로덕션 시스템의 실행 방법– con’d A1 Inference Engine Example: 전향추론 모델
Pattern Matching Production Memory by Domain Expert F A1 F1∧F2A2 F3∧F4A3 F1∧F4A1 Conflict Resolution F A1 F3∧F4A3 F1∧F4A1 A1 Working Memory by Problem Domain F1, F3, F4 Knowledge Expansion Inference Engine

76 Forward Chaining Rule 1: A^B → C Rule 2: A → D Rule 3: C^D → E
Rule 4: B^E^F → G Rule 5: A^E → H Rule 6: D^E^H → I Facts: A, B, F Goal: H 76

77 프로덕션시스템(6) 프로덕션 시스템의 실행 방법– con’d Goal : Z F B C D A Example: 후향추론 모델
Production Memory by Domain Expert F∧B  Z C∧D  F A  D Working Memory by Problem Domain A, B, C F B C D A

78 Backward Chaining Rule 1: A^B → C Rule 2: A → D Rule 3: C^D → E
Rule 4: B^E^F → G Rule 5: A^E → H Rule 6: D^E^H → I Facts: A, B, F Goal: H 78

79 프로덕션시스템(7) 경합의 해소 충돌집합(conflict set) :수행 가능한 규칙들의 집합
① 중요도(priority) 우선방법 ② 상세(specific) 규칙 우선방법 ③ 최근 실행 규칙 우선방법 ④ 최근 데이터 우선 방법 ⑤ 병렬 실행 방법 ⑥ 처음 규칙 우선방법

80 프로덕션시스템(8) 프로덕션 시스템의 예 생성메모리 R1 : F1  A1 작업메모리 R2 : F1  F2  A2
F1, F3, F4 인터프리터

81 프로덕션시스템(9) 프로덕션 시스템의 특징 <장점>
1) 각각의 규칙은 독립적이므로 새로운 규칙의 첨가, 제거, 수정이 용이 - 모듈성(modularity) 2) 인간이 문제를 해결할 때 사고하는 과정과 비슷, 이해하기 쉽다. - 자연스러움(naturalness) 3) 지식의 균일한 구조 - 균일성(uniformity), machine readability 4) 결정, 결론이 요구되는 영역에 적합 <단점> 1)프로그램 수행의 비효율성, 문제풀이에 많은 경비 소요 – slowness 2) undesirable interactions among rules 3) 제어가 복잡, 제어(control)의 흐름을 쉽게 추적할 수 없다 - 불투명성(obscure control) 예제 비디오(규칙에 의한 지식표현)

82