Bài giảng Các kỹ thuật suy diễn và lập luận

17 B. Cập nhật Thêm có hại: mâu thuẫn Bớt Dị thƣờng Sửa bất lợi: dƣ thừa ___________________________________________________________________ Bài tập chương 2: B i 1: Biểu diễn một cơ sở tri thức trong thực tế gồm 6 luật. B i 2: Biểu diễn một cơ sở tri thức gồm 8 luật, xác định v xử lý các luật dƣ thừa. B i 3: Biểu diễn một cơ sở tri thức gồm 8 luật, xác định v xử lý các mâu thuẫn. 18 Chương 3: Các kỹ thuật suy diễn và lập luận 3.1. Nhập môn Động cơ, mô tơ hay máy suy diễn gồm 2 bộ phận chính: - Cơ chế suy diễn (Processor) gồm: + Suy diễn tiến Inference (CT, KL, set of facts) và KQ: boolean + Suy diễn lùi R: set of rule - Cơ chế cổ điển (control unit): + chọn hƣớng suy diễn (MACRO) + chọn luật thƣờng có MẸO (heuristc metaknowledge) + phân rã CSTT SD phân tán SD song song + Lọc (tinh) (nhìn thấy cái n o không cần thiết thì loại, xác định cái n o đƣợc chọn trƣớc) 3.2. Phân rã CSTT Fact Precedence Graph (FPG) = (F, A) + Đỉnh : tập các sự kiện + Cung: (a,b)  A   r: left  b  R ; a  left USER Động cơ CSTT Tình huống Kernel 19 D: 1) a  b 2) b  c 3) c  e 4) c  d 5) d  e  f 6) b  h 7) f  h  g Tập sự kiện: F = { a, b, c, d, e, f, g, h} tách ra hai sự kiện: F1 = { a, b, c} R1 = { a  b, b  c} F2 = { e, d, f, g, h} R2 = { d e  f, f h  g} R0 = {c  e, c  d, b  h} F0 = {b, c, d, b, h} Đây l một cách phân rã CSTT eval({F1, F2})  min - Mô hình star a b c c e d f h g R1 R0 F0 R2 R4 R0 R1 R2 R3 20 - Nếu phân rã dựa trên tập luật l m gốc thì dẫn đến full condition - Phân rã theo tập sự kiện hình sao. 3.3. Mô tơ suy diễn A. Suy diễn tiến, lùi (nhắc lại) 1. Suy diễn tiến  tìm kiếm VD: 1) a  b 2) b  c 3) c  e 4)c  d GT = {a} {a}f min {a,b} min {a,b,c} {a,b,c,d} {a} {a, b} {a, b, c} {a, b, h} {a, b, h, c} A b B c C e hed hb dc    ghf  r1 2,6 r2 3,4,6 r3 r1 r2 r6 (3,4,6) (3,4) ..... ..... ..... 5) d  e  f 6) b  h 7) f  h  g 21 SUY DIỄN TIẾN ĐỒ THỊ SUY DIỄN TIẾN 1) GT 2) T.gian (SK đã chứng minh) 3) THOẢ T.Gian  T.Gian  {q} r: left  q r  thoa 4) Kết thúc T.Gian  KL 5) VẾT 1) Đỉnh gốc 2) Nút 3) CUNG T.Gian  T.Gian T.gian = Tgian  {q} 4) Lá 5) Đƣờng đi Chú ý: - Nếu SDT theo vét cạn  độ phức tạp tƣơng ứng với quá trình tìm kiếm trên đồ thị SD. CSD trên(vecan)  Ctìm kiếmVC = 0(BH) B: Branching (độ phân nhánh) v H l chiều cao của cây 2. Suy diễn lùi  tìm kiếm {g} {f, h} {d, e, h} ĐỒ THỊ SUY DIỄN LÙI ( And, or) {g} {f} {h} {d} {e} {} {c} {c} {a} {b} r r1 f r5 r7 r6 r4 r3 {a} 22  Suy diễn lùi  tìm kiếm theo chiều sâu CSDlùi  CTKsâu = 0 (B 'H ) - Trong trƣờng hợp suy diễn lùi mà có chu trình : * Prolog r1 A B  c r2 A C  B GT = {a, b, hc} r3 B C  A KL = {c} r4 a hc  A {c} {A, B} {B, C, B} … r5 b hc  A chỉ số max: {c} {AB} {B}  B. Chọn hƣớng SD - Tình huống GT, KL NSD SD Tiến, Lùi - Tập luật R CTIẾN CLÙI 0(B TH T ) 0(B LH L ) - Cây SD tiến G.thiết Cây SD Lùi KL K.luận GT R R BT (GT, KL, R) BL (GT, KL, R) HT (GT, KL, R) HL (GT, KL, R) BT = max BT(GT, KL, R) G.thiết: + HT HL + Ƣớc lƣợng - BT - BL 1. ƣớc lƣợng BT VD: r1 A r3 A B r1 r5 r4 23 1) a  b  C  c 9) a  b  c  P 2) a  b  ma  c 10) a  b  c  P 3) a  b  mb  c 11) a  b  c  mc 4) A  B  C 12) a  ha  S 5) a  hc  B 13) a  b  C  S 6) b  hc  A 14) a  b  c  P  S 7) a  R  A 15) b  S  hb 8) b  R  B 16) S  p  r F1= {a, b, C}  R1 = {r1, r2} F2 = {a, b, ma}  R2 = {r2} F3 = {a, b, mb}  R3 = {r3} F4 = {A, B}  R4 = {r4} F5 = {a, hc}  R5 = {r5} F6 = {b, hc}  R6 = {r6} F7 = {a, R}  R7 = {r7} F8 = {b,R}  R8 = {r8} F9 = {a, b, c, p}  R9 = {r9, r10, r11, r14} F10 = {a, ha}  R10 = {r12} F11 = {b, S}  R11 = {r15} F12 = {S, p}  R12 = {r16} Ƣớc lƣợng: B m T = max (2, 1, 4) = 4 _ TB = 12 16 = 1,33 24 2.Ƣớc lƣợng BL c có 3 luật C có 1 B có 2 BL max = 3 A có 2 _ LB = 10 16 = 1,6 P có 1 p có 1 mc có 1 S có 3 hb có 1 r có 1 3. Luật (Meta Knowlegde) 1. If BT > BL Then chọn Lùi 2. If BT > BL Then chọn Tiến 3. If BT = BL # GT > # KL Then chọn Lùi 4. # GT < # KL Then chọn Tiến 0. If user thích Then chọn C. Chọn luật trong quá trình SD (B i toán đụng độ luật - Rule Conflict) 1. Suy diễn tiến Tại 1 thời điểm n o đó trong quá trình SD tiến chúng ta có thể dùng nhiều luật cùng một lúc: TGian = {sự kiện f đã CM}; TG = {GT} (Mở) THOẢ = {r: left  q/ left  TGian} tập luật có thể áp dụng (Đóng) VET = {r1… rk} tập những luật đã dùng - Khi # THOA  2  chọn r  thoả ? 25 2 cơ chế chọn: + cứng nhắc (LIFO, FIFO) (sâu, rộng) (max, min) + mềm dẻo Đều l quá trình vét cạn (to n bộ tập luật)  Độ phức tạp 0 (Bh)  Để chọn theo mềm dẻo hàm _ h (r) (heurestic)  Max/ min (extremum) Đánh giá: - # VET  min (c ng ít c ng tốt) - Dƣ  min VD: (*) Gt = {a, b, R}, Kl = {p} {a, b, R} {a, b, R, A} {a b R A B} {a bR AB} {a b RABCc} VET = {r7, r8, r4, r1, r9, r10, r11} A B C c P  Dƣ = 2 Nên theo CS Min VET = {r7, r8, r4, r1, r9, r10, r11} (2) CS Max VET = {r8, r7, r4, r13, r11} (1) FIFO VET = {r7 r8 r4 r11 r13 r9 r10 r11} (3) LIFO VET = {r8 r7 r4 r13 r15 r1 r9 r10 r11} (4) Vậy có cách n o để Dƣ = 0 ? {a, b, R} {a, b, R, A} {a, b, R, A, B} {a, b, R, A, B, C}…... 7,8 CS min r4 rmin … r7 8 r8 1,13 r1 13,9,10,11 7,8 r7 r8 4 r4 1,13 26 Đồ thị FPG (Fact Precedence Graph) Sử dụng để miêu tả mối tƣơng quan giữa điều n y với điều khác Vd (*) hˆ 1(r) = hˆ 1(r: left  q) = UL (a, K, L) = kcFPG (a, KL) Chọn r: hˆ 1(r)  min NXét: 1) f g FPG thì f đƣợc dùng trực tiếp để suy ra G (r: left  g, f  left) 2) Có đƣờng đi P: f  ……  g thì đƣợc dùng gián tiếp để suy ra g. {a,b,r}7,8  {a b R A}8  {a b R A B}4 {a b R A B C}1,13  …….. hˆ 1(r7)=kc(A,p)=3 hˆ 1(r8)=kc(B,p)=3 hˆ 1(r1)=kc(c,p)=1 hˆ 1(r13)=kc(s,p)=  hˆ 1(r9)=kc(P,p)= hˆ 1(r10)=kc(mc,p)= hˆ 1(r11)=kc(p,p)=0 Chọn r1 Chọn r11 hc R A B C a b ma c mb mc P p ha S hb r