Bài giảng Suy diễn lùi

27 Nhận xét: #VET +Complexity hˆ x m ii)Đồ thị RPG(Rule Precedence Graph) RPG=(R,A) Trong đó R: Tập các đỉnh A: l tập các cạnh sao cho: r  r’, r:left  q  q  left’ r’:left  q’ VD:Xây dựng đồ thị RPG cho ví dụ trên ta có: *Xây dụng h m hˆ 2 (r)? hˆ 2 (r)=? RKL={r:left  q/q  KL} R hˆ 2 (r)=kcRPG(r,RKL) Chọn r sao cho hˆ 2 (r) min Xét ví dụ sau: GT={a b R}, KL={r} {a,b,r}7,8  {a b R A}8  {a b R A B}4 {a b R A B C}1,13  {a b R A B C c}9,10,11  ……..KL hˆ 2 (r7)=kcRPG(r7, r16)=3 r5 r13 r6 r4 r1 r+9 r7 r2 r10 r8 r3 r11 r16 r14 r12 r15 28 hˆ 2 (r8)=kcRPG(r8, r16)=3 hˆ 2 (r1)=kcRPG(r1, r16)=2 hˆ 2 (r13)=kcRPG(r13, r16)=1 hˆ 2 (r15)=kcRPG(r15, r16)= hˆ 2 (r10)=kcRPG(r10, r10)=1 hˆ 2 (r11)=kcRPG(r11, r16)=1 hˆ 2 (r14)=kcRPG(r14, r16)=1 hˆ 2 (r16)=kcRPG(r16, r16)=0 2. Suy diễn lùi Đồ thị FPG Tình huống đụng độ khi suy diễn lùi: Goal= Tập những sự kiện cần chứng minh; ban đầu Goal=KL Xét f  Goal. Có nhiều luật suy ra f. Ta chọn luật bằng các thử sai v quay lui. Để tránh phải quay lui ta cần chọn luật nhƣ thế n o. Nhắc lại các cách chọn có quay lui: + cứng nhắc: - Chỉ số max: chọn luật có chỉ số lớn nhất trong tập luât thoả - Chỉ số min: chọn luật có chỉ số nhỏ nhất trong tập luât thoả + mềm dẻo : hˆ (r)  max/min: Đánh giá tốt hay không dựa v o quay lui, c ng nhiều cáng kém VD: GT={a b R} {S}12,13,14  {a b c p} {a b mb p}  ……. * Cách tính hˆ 3(r) hˆ 3(r)= hˆ 3(left  f)=kc(GT,left) Chọn r: hˆ 3(r)  min Kc(GT, left)=max(GT,a) a  left Chọn r13 29 Kc(GT, left)=max(b,a) b  GT VD: GT={a b R}, KL={S} {S}12,13,14  {a b c p} {a b mb p}  ……. hˆ 3(r12)=kc(a b R,a ha)=  hˆ 3(r13)=kc(a b R,a a b C)= 2 hˆ 3(r14)=kc(a b R,a b c p)= 4 hˆ 3(r6)=kc(a b R,b hc)=  hˆ 3(r17)=kc(a b R,a R)= 0 hˆ 3(r5)=kc(a b R,a hc)=  hˆ 3(r8)=kc(a b R,b R)= 0 ii) Đồ thị RPG. * Cách tính hˆ 4(r)? hˆ 4(r)=kcRPG(RGT , r) Chọn r: hˆ 4(r)  min RGT={r: left  q/left  GT} VD: GT={a b R} KL={S} {S}12,13,14  {a b c p} {a b mb p}  ……. Tính hˆ 4(r) ta có: ……. D. Hạn chế các ứng viên trong quá trình suy diễn 1. Suy diễn tiến Giả sử xét tại một thời điểm trong quá trình suy diễn : + Thời gian + THOẢ= LỌC(R, TGian)={r: left  q/ left  TGian} THOẢ’ THOẢ . Khi đó lựa chọn trong THOẢ’ bằng phƣơng pháp vét cạn hay heuristic. Chọn r13 Chọn r7 Chọn r8 (Hạn chế các ứng viên) 30 1. Suy diễn lùi Xét 1 sự kiện thuộc Goal. hˆ () =  /min XACDINH (f) = {r; left  f} = 0/max Kĩ sƣ tri thức XACDINH’(f)  XACDINH (f) Kết luận: Nâng cao hiẹu quả quá trình suy diễn - Chọn hƣớng suy diễn - Chọn luật - Phân tách cơ sở tri thức (CSTT) - Hạn chế ứng viên 3.4. Biểu diễn TRI THỨC bằng LOGIC vị từ và SUY DIỄN Luật ri P1 (…)  P2 (…)  ……  Pn (…)  q (…) Pi (…) l vị từ / predicate: l những phát biểu có phụ thuộc v o các biến q (…) hay tham số VD: Các định lý hình học 1.tđ(U,XY)  tđ(V,XZ)  SS(UV,XZ) 2.SS(UV,XY)  SS(UV,ST)  SS(ST,XY) 3.SS(XY,UV)  SS(XZ,UV)  Thang(X,Y,Z) 4.SS(XY,UV)  Thang(X,Y,Z)  SS(UV,XZ) tđ(U,XY)  tđ(U,YX) SS(XY,UV)  SS(UV,XY) SS(XY,UV)  SS(VU,YX) A. Suy diễn tiến GT: tđ (P, AB); tđ (Q, AC) tđ (I, BQ); tđ (J, CP) tđ (E, CQ) KL { SS (PS, BC) Control mechanisms Explicit Implici t A P Q B C I J 31 B ' 1 : TG0 = GT THOA = {(r1,  1), (r1,  2), (r1,  3), (r1,  4)}  1 = {A/X; B/Y; C/Z; P/U; Q/V}  2 = {C/X; Q/Y; P/Z; E/U; J/V}  3 = ...  4 = .... Chọn (r1,  1) TG1 = TG0  {SS (UV, YZ), 1} = TG0  {SS (PQ, BC)} B ' 2 : TG1 = THOA = {(r1,  2), (r1,  3), (r1,  4) …. Vđề: L m nhƣ thế n o để xác định (ri,  i) B. Suy diễn lùi. Nói chung suy diễn tiến v suy diễn lùi đều giống nhƣ nhau trong logic mệnh đề vì đều l quá trình hợp nhất (Unification) Để rõ hơn ta hãy xét ví dụ sau: GT tđ(P,AB), tđ(Q,AC), tđ(I,PQ), tđ(J,CP), tđ(E,QC) KL SS(IJ, BC) Ta áp dụng thủ tục suy diễn lùi, nhƣng co khó khăn l khi không tiếp tục đƣợc ta lại phải quay lui.Từ đây ta có thể đƣa ra nhận xét sau: Sự giống v khác nhau giữa suy diễn lùi của logic vị từ v suy diễn Prolog - Giống nhau: cả trong prolog cv logic vị từ đều có phép hợp nhất v quá trình thử sai - Khác nhau: Tính chất trong prolog l chúng minh suy ra điều vô lý, còn suy diễn lùi l suy ra goal=0. Cơ chế của prolog l theo chỉ số min v đi từ trái sang phải. Còn trong logic vị từ thì có thể áp dụng hất mọi cacchs đi thông thƣờng: Trai, phải v ngƣợc lại hay l trên duới v ngƣợc lại. 32 3.5. Ứng dụng các kỹ thuật suy diễn vào xây dựng hệ chuyên gia 3.5.1. Giao diện 3.5.1.1. Mở đầu Đầu tiên chúng ta xét đến các loại ngƣời sử dụng hệ chuyên gia. Bao gồm 4 loại sau: - Ngƣời sủ dụng không chuyên, đầu cuối. - Ngƣời sử dụng chuyên , thƣờng sử dụng hệ thống ở trình độ không cao. - Ngƣời sủ dụng l kĩ sƣ tri thức - Ngƣời sử dụng la chuyên gia ở góc độ tƣ vấn cần giải quyết các vấn đề sau: Tƣ vấn + Tình huống: +Đã biết + Điều cần biết + Thu thập giả thiết + Chất vấn v giải thích Nhƣ vậy chúng ta có thể cùng đi đến một định nghĩa về giao diên: Ngƣời sử dụng nhằm mục đích thu thập thong tin ban đầu về tình huống cần tƣ vấn. Các vấn đề cần phải giải quyết: - Xác định tập HỎI: những điều cần hỏi - Phƣơng thức hỏi: Thân thiện với ngƣời sử dụng( ta có thể đƣa về gần ngôn ngữ tự nhiên bao nhiêu c ng tốt bấy nhiêu) hay Tránh hỏi thừa. 3.5.1.2 Xác định tập những sự kiện cần hỏi. A. Khi biết kết luận. Khi đó tập các sự kiện cần hỏi l : HỎI = Tập các sự kiện liên quan đến kết luận (xét trong liên quan đến tập luật) i) Phƣơng thức hỏi gần Ta xét ví dụ sau: 1. a  b  c 2. d  e  f 3. c  e  g Thƣờng là tƣ vấn Làm việc chủ yếu với phần soạn thảo tri thức 33 4. d  b  h 5. m  g 6. m  a  h 7. f  h  k 8. g  c  k KL={k} Khi đó ta có: HỎIgần= U{lefti / r:left qi , qi  KL} = {f c g h} Nhận xét: HỎIgần={f/  (f,g) FPG, g  KL} ii) Hỏi xa HỎIxa= {f/ đƣờng đi p FPG, p= f  … g, g KL} TRÁI=  m ii lefti PHẢI={q1……qn} R={r1…..rm} ri: left i  qi HỎIxa={f  TRAI\ PHẢI/  đƣờng đi p:f  ….. g, g  KL} B. Không biết kết luận HỎI= TRÁI \ PHẢI Xét vid dụ ở trên: TRÁI={ a b c m n f g h} PHẢI={c f g h k} HỎI=TRÁI \ PHẢI={a b d e m n} 3.5.1.3. Phƣơng thức hỏi gần A. Hỏi thân thiện HỎI={đau,…..}  f  HỎI  Câu hỏi (f) l một văn bản hiện lên m n hình để nhằm gợi ý ngƣời dùng đƣa thông tin về sự kiện f 34 B. Tránh câu hỏi thừa Hỏi có tính đến kết quả trả lời của các câu hỏi trƣớc  KỊCH BẢN HỎI/ CÂY HỎI 1. Hỏi xa. 2. Hỏi gần 3.5.1.4 Giao diện ngƣời sử dụng Giao diện l hiển thị cở sở tri thức bằng đồ hoạ Các loại hiển thị: + Tuyến tính: ri: lefti  q1 ……….. rm: leftm  qm  f  F  Diễn giải (f) r1: p1 ….  pn  q Nếu nhƣ diễn giải p1 v ….. diễn giải pn thì diễn giải q + Phi tuyến: . Đồ thị FPG . Đồ thị RPG . Cây lồng nhau 35 3.5.2. Modul giải thích 3.5.2.1. Mở đầu Trợ giúp đ o tạo: Cho NSD thông tin về vấn đề n o đó: +CSTT: Why + Suy diễn : How Yếu tố tâm lý với ngƣời dùng: Tăng sức thuyết phục . Phân loại câu hỏi hỏi ngƣời sử dụng. Why f? Tại sao lại cần có thông tin có thông tin về sự kiện f. Why r? Tại sao lại có luật r trong CSTT How f? L m thế n o đƣa ra Kết Luận, nhận định f How not f Tại sao lại không có kết luận, sự kiện f. Câu hỏi giả định: What If……1) what if thêm f 2) what if thêm r 3.5.2.2 Câu hỏi why f. Phiên l m việc user gồm 2 phần Phiên HỎI Phiên sử dụng( hình vẽ) User G D MTSD CSTT 36 Muc đích của câu hỏi why - Ngƣời sƣr dụng muốn biết tầm quan trọng/ sự liên quan của f với quá trình sử dụng Hệ thống chỉ ra mối liên hệ của f với mục đích sƣ dụng Về mặt kĩ thuật : xác định xem f……KL có mối quan hệ n o không Phƣơng thức trả lời: Có hai phƣơng thức đó l : - Phƣơng thức 1:Dựa trên đồ thị FPG( Khi đó ta tìm xem có đƣờng đi từ f đến KL ?) Ma trận liên thuộc G=(N,A) Biểu diễn ma trận Mnxm Trong đó: ………. - Phƣơng thức 2:Dựa v o phƣơng pháp xác định hỏi( xa, gần) . Phƣơng pháp n y cần phải biết kết luận trƣớc 3.5.2.3. Why? Mục đích: Tại sao lại có luật/ tri thức R trong cơ sở tri thức. Xuất sứ, nguồn thu thâph tri thức r. Hệ thống: Chỉ rõ đƣợc phƣơng thức có đƣợc tri thức r Kĩ thuật:  Rr kèm theo xuất sứ: - Nguồn t i liệu+ Kĩ sƣ tri thức/ chuyên gia - Ý kiến chuyên gia Sử dụng phƣơng pháp n o đó KDD v trên nguồn thông tin n o Thu nạp một cách tự động. Tóm lại hệ thống cần đảm bảo cho ngƣời sử dụng đƣợc cung cấp thông tin một cách có xuất sứ. TRẢ LỜI User G D MTSD f ? f ! WHY f? CSTT