1 Artificial Intelligence Lecture 3: Knowledge Based System 1. Conflict Resolution Rules 2. Certainty Factor Soongsil University Intelligent Systems Lab.

2 Meta-knowledge  Meta-knowledge is knowledge about knowledge.  For example, knowledge about how an expert system makes decisions would be considered meta-knowledge.  Meta-knowledge might be used for conflict resolution, enabling a system to reach its goal quicker.

3 Meta-rules  meta-rules were introduced in order to re-direct the searc h & obtain a system whose behaviour follows human pro blem solving more closely  Meta-rules can refer in their conditions to facts (including meta-facts) and rules (including other meta-rules). They can check whether a rule contains a particular clause in its conditions or actions. They can also check the conflict set for a particular rule, or check the size of the conflict set.  Meta Rules Rule Group 으로 구성 Priority 가 정해짐 Certainty 가 부여 됨

4 전문가가 시스템을 설계할 시 주로 사용하는 지식표현 방법은 생성규칙인데 (production rule), 생성규칙은 규칙의 조건 부분을 만족시키면 결론 부분을 생성하게 된다. 현재의 상황에 의해서 한 규칙에 있는 조건 부분이 만족될 때 그 규칙은 Triggered 되었다고 하며, 결론 부분이 수행될 때 그 규칙은 Fired 되었다고 한다. 조건은 같지만 결론이 다른 규칙이 있기에 혹은 조건은 틀리지만 결론이 같은 규칙이 중복하여 존재하면 동시에 Triggered 혹은 Fired 될 수 있다. 규칙충돌 해결 (Rule Conflict Resolution) 방법 모순 if a1, a2, a3 then A if a1, a2, a3 then B 중복 if a1, a2, a3 then A if a1, a2 then A if a1, b1 then A if b2, b3 then A

5 작업메모리에 의해서 만족되는 최초의 규칙을 실행한다. 예 1) 규칙 1 (CF=0.8) : if a1 & a2 then A 규칙 2 (CF=0.9) : if a1 & a2 then B 앞에 오는 규칙 1 을 먼저 선택한다. 그러나 확신요인값을 보면 규칙 1 은 0.8, 규칙 2 는 0.9 로 규칙 2 가 신뢰도가 높음을 알수 있다. 가장 높은 우선 순위를 가진 규칙을 실행한다. 예 2) 규칙 1 (CF=0.8) : if a1 & a2 then A CF=0.8 규칙 2 (CF=0.9) : if a1 & a2 then B CF = 0.9 규칙 1 은 CF=0.8, 규칙 2 는 CF = 0.9 로 규칙 2 이므로 CF 값이 큰 규칙 2 를 선택한다. 규칙충돌 해결 (Rule Conflict Resolution) 방법

6 현재의 작업메모리에 만족되는 가장 특수한 규칙을 수행한다. 예 3) 규칙 1: if a1(CF: 0.9) & a2 (CF : 0.6) & a3 (CF: 0.6) & a4 (CF : 0.5) then A (CF : 0.9) 규칙 2: if a1(CF: 0.9) & a2 (CF : 0.8) then A (CF : 0.9) 가장 구체적이고 상세한 규칙을 선택한다. 규칙 1 선택 작업메모리에 삽입된 가장 최근의 정보에 만족되는 규칙을 실행한다. 예 4) 규칙 1: if a1(CF: 0.9) & a2 (CF : 0.9) then A (CF : 0.9) 규칙 2: if a1(CF: 0.9) & a2 (CF : 0.8) then A (CF : 0.9) 규칙 3: if a1(CF: 0.9) & a4 (CF : 0.7) then A (CF : 0.9) 만약 사실 a4 가 가장 최근에 입력된 자료라면 a4 를 포함하고 있는 규칙 3 을 실행하는 것이다. 가장 최근 정보라고 해서 신뢰도가 가장 좋은 것은 아니다. 규칙충돌 해결 (Rule Conflict Resolution) 방법

7 가장 새로운 규칙 즉, 이전에 수행되지 않았던 규칙을 실행한다. 만약 규칙 3 이 어떤 방법에 의하여 선택되었다면 규칙 3 은 작업메모리에서 제거되고, 다음에는 나머지 규칙인 규칙 1 과 규칙 2 중에서 선택 된다는 것이다. 예 5) 규칙 1: if a1(CF: 0.9) & a2 (CF : 0.9) then A (CF : 0.9) 규칙 2: if a1(CF: 0.9) & a2 (CF : 0.8) then A (CF : 0.9) 규칙 3: if a1(CF: 0.9) & a2 (CF : 0.7) then A (CF : 0.9) 규칙충돌 해결 (Rule Conflict Resolution) 방법

8 Forward Reasoning 시 규칙 충돌 해결기법 1. 규칙의 결론 부분의 CF 중 가장 높은 것을 선택하고 2. 규칙의 결론 부분의 CF 값이 같을 때, 작업 메모리에서 만족하는 최초의 규칙을 선택한다. 모순의 예 ) 규칙 1: if a1, a2, a3 then A 규칙 2: if a1, a2, a3 then B 규칙충돌 해결 (Rule Conflict Resolution) 방법

9 Backward Reasoning 시 규칙 충돌 해결기법 1. 규칙의 결론 부분의 CF 값 중 가장 높은 것을 선택하고 2. 규칙의 결론 부분의 CF 값이 같을 때, 조건부분의 조합된 CF 값 중 가장 높은 것을 선택 한다. 3. 규칙 조건부분의 조합된 확신요인값이 서로 같을 시 작업 메모리에 의해서 만족되는 최초의 규칙을 선택한다. 중복의 예 ) 규칙 1: if a1, a2, a3 then A 규칙 2: if a1, a2 then A 규칙 3: if a1, b1 then A 규칙 4: if b2, b1 then A 규칙충돌 해결 (Rule Conflict Resolution) 방법

10 지식은 불완성 (Incompletness) 을 가질 수 있다. 예 ) “ 예쁜 내 여친 ”, “ Valve 를 돌려라 ”, “ 급 질문 ”, “ 엄친아 ” 지식표현의 애매성 (Vagueness) 또는 모호함 (Ambiguity) 을 가질 수 있다. 예 ) “ 날씬 한 몸매 ”, “ 요즘 젊은 사람은 … 하다 ” 지식의 오류 (Incorrectness) 가 있을 수 있다. 전문지식의 부족과 논리적 오류에 기인 예 ) “A 라는 기계가 고장이 나지 않았기 때문에 A 는 앞으로 고장이 나지 않을 것이다.” 라 는 추론은 오류가 된다. 측정의 오류 (Errors of Measurement) 가 있을 수 있다. 실제로 특정 대상에 적용을 시킬때 규칙의 조건과 실제 대상과의 연계에서 오류가 발생할 수 도 있다. 예 ) “2 억 이상의 부동산을 담보로 대출한다 ” 시가인가 공시지가 인가 ???? “29 평 아파트를 선호한다.” 분양평수인가 ? 실평수인가 ? Uncertainty

11 확률 : 사건 (event) H 가 발생 될 확률 P(H) 는 사건 H 가 속하는 원소의 수 = 표본공간 (sample space) 의 전체 원소 수 확률 P(H) 는 0 와 1 사이의 값이다. 0 <= P(H) <= 1 모든 발생 가능한 사건들의 확률의 합은 1 이다. 확률에 기초한 추론

12 상호배타적 (Mutually exclusive) k 개의 사건이 일어날 확률 은 각각의 발생 확률의 합이다. 어떤 사건 ( 또는 가설 ) 과 그 사건의 여집합 (complement) 이 발생할 확률의 합이 1 이다. P(H) + P( ￢ H) = 1 확율적 접근법

13 확율적 접근법 P(A∩B) = P(A)P(B) : 독립 사건일 때 * A 와 B 사건은 서로에게 영향을 주지 않음 * B 사건에 영향 받아 ( 발생 후에 ) A 가 일어날 확률 * A 와 B 가 상호배타적이면 P(A∩B)=0 이므로 P(A|B) = P(B|A) = 0 * A 와 B 가 독립적이면 P(A|B) = P(A), P(B|A) = P(B) ( ∵다른 사건에 영향 없음 ) P(A ∪ B) = P(A) + P(B) - P(A∩B) * A 와 B 가 상호배타적이면 P(A∩B)=0 : 조건확률 - 일반적인 다수 사건 공간에서의 사건들 사이의 관계

14 Bayes 의 정리

15 Bayes 정리의 활용 예 예 ) 겨울철에 어떤 지역의 기침하는 사람이 감기일 확률은 ? 겨울철에 이 지역 주민 15% 가 감기에 걸림 보통 감기 걸린 사람의 50% 가 기침을 함 지역주민의 20% 는 감기와 상관없이 기침을 함 해 ) P( 감기 ) = 0.15 P( 기침 | 감기 ) = 0.5 P( 기침 ) = 0.2 해답 : P( 감기 | 기침 )=P( 기침 | 감기 )P( 감기 )/P( 기침 ) =0.5 Ⅹ 0.15/0.2=0.375 Bayes 의 정리

16 Bayes 의 정리 Bayes 정리의 확장 (by Laplace) )B(A)B )B )BB(BA SAA 때 사건일 임의의 :A 상호배타적 는 B,B 임의의 }B,,B,{BS 전체공간 :S N21 N21 jiN21        

17 Bayes 의 정리 Bayes 정리의 확장 (by Laplace)

18 확장된 Bayes 정리 S 상의 임의의 부분 B i 과 임의의 사건 A 에 대해서 Bayes 정리의 활용 E: 주어진 증거 (evidence) H k (k=1, 2, …, N): 고려할 수 있는 상호배타적인 N 개의 가설 중 하나 에 대해서, 증거 E 가 주어졌을 때 가설 H k 이 참일 확률은 증거없이 특정한 가설 H k 를 신뢰할 수 있는 확률 H k 이 참일 때 E 라는 증거를 얻을 수 있는 확률 증거 E 에 대한 원인으로 H k 를 고려할 수 있는 정도 ( 원인 확률의 정리 ) Bayes 의 정리

19 확율적 접근의 한계 실제문제 적용상의 문제 1) 조건부 확률 P(H i |E) 를 알기 위해 사전 확률 P(H i ) 와 조건부 확률 P(E|H i ) 을 알아야 한다. 2) 위 식에서 각 사건 H i 는 서로 배타적인 조건을 만족하지 않는 경우가 있다. 예 ) H1: 소화불량이다. H2: 위암이다. 은 성립 되는가 ?

20 확율적 접근의 한계 실제문제 적용상의 문제 3) 새로운 증상들이 추가될 때 을 구하기 위하여 더욱 복잡한 증상들의 조건부 확율들이 주어져야 한다. 4) 확률은 정의 상 이나 새로운 질병이 추가된다면 이들의 사전 확율값과 새로운 질병과 관련 된 각 증상들의 조건부 확률을 추가시켜야 한다.

21 실제문제 적용상의 문제 5) 확율값의 추정에 있어서 부족한 데이터 등으로 인해 사전의 계산이나 사후의 실험으로 여러 확율값을 구할 수 없는 경우 주관적 확율값을 추정 할 수 있다. 예 ) 세가지 증상 E1, E2, E3 모두 사실일 때 H 라는 질병이라는 것을 0.7 정도로 가능성이 있다고 어느 전문가가 제시했다면, 여기서 0.7 은 주관적 확율값 이다. 또한 질병 H 가 아닐 가능성이 0.3 이라고 이야기 할 수 있는 것은 아니다. 확율적 접근의 한계

22 Certainty Theory  Principle features of MYCIN is managing inexact information  Inexact information has significant in medical domain because of time constraints such as emergency room  Majority of the rules used in medicine is inexact

23 Certainty Theory  Some uncertain phrases: probably it is likely that it almost seems certain that

24 Certainty Factors  Certainty Factor CF(x) is a measure of how confident we are in x  Range from –1 to +1 CF = -1 very uncertain CF = +1 very certain CF = 0 neutral  Certainty factors are relative measures  Do not translate to measure of absolute belief

25 Certainty Factors

26 Certainty Theory: Definitions 1. Measures of Belief, MB(H, E) Number that reflects the measure of increased belief in a hypothesis H based on evidence E  E 로 인한 H 에 대한 증가된 확신정도 0  MB  1 2.Measures of Disbelief, MD (H, E) Number that reflects the measure of increased disbelief in a hypothesis H based on evidence E  E 로 인한 H 에 대한 증가된 불확신의 정도 0  MD  1

27 Certainty Theory: Definitions 3.Certainty Factor, CF(H,E) Number that reflects the net level of belief in a hypothesis given available information -  증거 E 가 주어졌을 때 가설 H 에 대한 확신도, CF(H,E) = MB(H,E) - MD(H, E) -1  CF  1 확신도는 확신과 불확신을 결합한 수치로 표현하며, 확신의 정도 (Degree of confirmation) 를 나타낸다.

28 각 값의 범위 주의 : 확신도에서는 어떤 증거로 인해 가설을 CF(H, E) 만큼 확신한다 고 해서 그 가설에 대한 불확신 정도가 1-CF(H, E) 을 의미하지는 않는 다. 즉, 다음이 성립한다. Certainty factor : CF

29 증거수집에 따른 확신과 불신의 증가 MB(H,E+) 는 H 에 대한 지지 증거들이 점점 발견 될 수록 1 에 가까이 증가하 며, H 를 논리적으로 확실히 확신케 하는 증거가 있을 때만 MB 는 1 이 된다. MD(H,E-) 는 H 에 대해 불신을 증가시키는 증거들이 점점 발견될 수록 1 에 가까이 증가하고, H 를 논리적으로 확실히 부정하는 증거가 있을 때만이 MD 는 1 이된다. 증거수집에 따른 확신과 불확신의 증가 - 증거 E+ 로 인한 MB(H, E+) = 1 이면 불신의 증거 E- 가 어떠한 정 도이든 MD(H, E-) = 0 이다. 따라서 CF(H, E+) = 1 - 증거 E- 로 인한 MD(H,E-)=1 이면 확신의 증거 E+ 가 어떠한 정도이 든 MB(H, E+) = 0 이다. 따라서 CF(H, E-) = -1 - MB(H, E+) = MD(H, E-) = 1 인 경우는 모순 이여서 CF 는 정의가 안된다. 확신도 (Certainty Factor)

30 Certainty Theory: Values Interpretation Definitely Not-1.0 Almost certainly not-0.8 Probably not-0.6 Maybe not-0.4 Unknown-0.2 to 0.2 Maybe 0.4 Probably 0.6 Almost Certainly0.8 Definitely 1.0

31 Certainty Theory: Representation UNCERTAIN EVIDENCE Representing uncertain evidence CF (E) = CF (It will probably rain today) = 0.6 Similar to P(E), however, CF are not probabilities but measures of confidence Degree to which we belief evidence is true In ES written as exact term but add CF value to it Example: It will rain today CF 0.6

32 Certainty Theory : Representation Basic structure of rule in certainty model IF E THEN H CF(Rule) CF(Rule) = level of belief of H given E Given that E is true, we believe H according to: CF (H, E) = CF(Rule)

33 Certainty Theory : Representation Example: IFThere are dark cloud - E THEN It will rain - H CF = 0.8 This rule reads: “If there are dark clouds then it will almost certainly rain” CF (H, E) similar P (H|E)

34 Certainty Factor Propagation (C.F.P) CFP FOR SINGLE PREMISE RULE Concerned with establishing the level of belief in rule conclusion (H) when the available evidence (E) contained in the rule premise is uncertain. CF (H, E) = CF (E) X CF (RULE) Example From previous rule: CF(E) = 0.5 C.F.P. is CF(H, E) = 0.5 x 0.8 = 0.4 # In words: It maybe raining IF There are dark cloud - E THEN It will rain - H CF = 0.8

35 Stanford Certainty Factor Algebra  There are rules to combine CFs of several facts (CF(x1) AND CF (x2)) = min(CF(x1), CF(x2)) (CF(x1) OR CF (x2)) = max(CF(x1), CF(x2))  A rule may also have a certainty factor CF(rule) CF(action) = CF (condition) * CF(rule)

36 Example CF(shep is a dog) = 0.7 CF(shep has wings) = -0.5 CF(Shep is a dog and has wings) = min(0.7, -0.5) = -0.5 Suppose there is a rule If x has wings then x is a bird (CF = 0.8) Let the CF of this rule be 0.8 IF (Shep has wings) then (Shep is a bird) CF(H, E) = -0.5 * 0.8 = -0.4

37 Certainty Factors – Conjunctive Rules IF,, … THEN {rule CF} CF(H, E1  E2  …  En) = min[CF(E1), CF(E2)… CF (En)] x CF

38 Certainty Factors – Conjunctive Rules For example IF sky is clear AND forecast is sunny THEN wear sunglasses (CF = 0.8) CF(sky is clear) = 0.9 CF(forecast is sunny) = 0.7 CF(action)  CF(H, E) =CF (condition) * CF(rule) = min[0.9,0.7] * 0.8 =0.56

39 Certainty Factors – Disjunctive Rules IF OR OR … THEN {rule CF} CF(H, E1  E2  …  En) = max[CF(E1), cf(E2)… cf(En)] x CF

40 Certainty Factors – Disjunctive Rules For example IF sky is overcast OR forecast is rain THEN take umbrella CF{0.9} CF(sky is overcast)=0.6 CF(forecast is rain)=0.8 CF(action)  CF(H, E) = CF (condition) * CF (rule) = max[0.6,0.8] * 0.8 = 0.72

Refreshment !!  다음 ? 에 들어갈 알맞은 숫자는 ? 41

42 Certainty Factor Propagation (C.F.P) FORMULA FOR INCREMENTALLY ACQUIRED EVIDENCE CF combined (CF1, CF2) = CF1 + CF2 * (1 - CF1)Both  0 = CF1 + CF2 One  min {|CF1|,|CF2|} = CF1 + CF2 * (1 + CF1)Both  0 where, CF1 = confidence in H established by one rule (RULE 1) CF2 = confidence in it established by one rule (RULE 2) CF1 = CF1 (H, E) CF2 = CF2 (H, E)

43 Certainty Factor Propagation (C.F.P) Example Consider Rain Prediction: Rule 1 and 2 Explore several cases Case 1: Weatherman and Farmer Certain in Rain CF (E1) = CF (E2) = 1.0 CF1 (H, E1)= CF (E1) * CF (RULE 1) = 1.0 * 0.8 = 0.8 CF2 (H, E2)= CF (E2) * CF (RULE 2) = 1. 0 * 0.8 = 0.8 Single Premise Rule IF There are dark cloud - E THEN It will rain - H CF = 0.8

44 Certainty Factor Propagation (C.F.P) Since both > 0, CF combine (CF1, CF2)= CF1 + CF2 * (1 - CF1) = * ( ) = 0.96 # CF supported by > 1 rule can be incrementally increase more confident

45 Case 2: 증거가 상반 되는 경우, CF(E1) = 1.0CF(E2) = -1.0 CF1(H, E1)= CF (E1) * CF (RULE 1) = 1.0 * 0.8 = 0.8 CF2 (H, E2) = CF (E2) * CF (RULE 2) = -1.0 * 0.8 = -0.8 Since either one < 0 CF combined (CF1, CF2) = CF1 + CF2 1 - min {|CF1|,|CF2|} = (-0.8) 1 - min {0.8,0.8} = 0 # 서로 상반된 증거는 CF  unknown !! Certainty Factor Propagation (C.F.P) Weatherman certain in rain, Farmer certain no rain

46 Case 3: Weatherman and Farmer believe at different degrees that it is going to rain CF (E1) = -0.8CF (E2) = -0.6 CF1 (H, E1)= CF (E1) * CF (RULE 1) = -0.8 x 0.8 = CF2 (H, E2)= CF (E2) * CF (RULE 2) = -0.6 * 0.8 = Since both < 0 CF combined (CF1, CF2) = CF1 + CF2 * (1 + CF1) = * ( ) = # 한가지 이상의 불확신 증거가 점진적인 CF 에 대한 불신을 확대하는 것을 보임 Certainty Factor Propagation (C.F.P)

47 Certainty Factor Propagation (C.F.P) Case 4: Several Sources Predict Rain at the same level of belief but one source predicts no rain If many sources predict rain at the same level, CF(Rain) = 0.8, the CF value converge towards 1 CF combined (CF1, CF2..) = CF old CF old = collected old sources info. If new source say negative CF new = -0.8 then, CF combined (CF old, CF new ) = CF old + CF new 1 - min { |CF old |, |CF new |} = = 단 하나의 부정적 증거는 전체의 CF 에 크게 영향을 미치지 못하는 것을 보임

48 교환법칙 (Commulativity) E2 보다 E1 가 먼저 발견된 증거라고 할때 - MB(H, E 1 ∧ E 2 ) = MB(H, E 2 ∧ E 1 ) - MD(H, E 1 ∧ E 2 ) = MD(H, E 2 ∧ E 1 ) - CF(H, E 1 ∧ E 2 ) = CF(H, E 2 ∧ E 1 ) 즉, 증거의 발견 순서는 가설의 확신과 불신에 영향을 미치지 않는다. 확신도 (Certainty Factor)

49 Certainty Factors  Practical alternative to Bayesian reasoning  Heuristic manner of combining certainty factors  Not mathematically pure  Does mimic thinking process of human expert

50 Comparison of Bayesian Reasoning & Certainty Factors  Probability Theory Oldest & best-established technique forecasting & planning 분야에는 잘 맞음 통계자료와 확률에 대한 값이 주어져야 함 대부분 ES 시스템은 신뢰할만한 통계정보를 가지고 있지 않 다 조건에 대한 independence 가정이 주어져 있지 않다 Leads to dissatisfaction with method

51 Comparison of Bayesian Reasoning & Certainty Factors  Certainty Factors 확률의 수학적 정확성 부족 진단과 의료분야에서 Bayesian reasoning 보다 우수하다 확률이 알려지지 않거나 얻기가 어려운 경우 적절 Evidential reasoning 증거가 점차적으로 출현되는 경우도 용이하게 적용 Hypotheses 의 AND, OR 에도 적용 Belief 의 다양한 정도에 따른 Evidences