8/26/2012 Tuần 1 (Week 1) Pham Van Hai Email: haivnu@yahoo.com Hai V Pham hai@spice.ci.ritsumei.ac.jp 1 Mã M số: IT4361 Kh K ối lư l ợng n : 2 ◦ Lý thuyết: 30 giờ
◦ Bài tập/BTL: 15 giờ (dự án theo nhóm môn học) ◦ Thí nghiệm: 0
Yêu cầu: SV tham gia > 85% lớp học Hai V Pham hai@spice.ci.ritsumei.ac.jp 2
Học phần nhằm cung cấp sinh viên những kỹ
thuật cơ bản nhằm xây dựng các bộ sinh hệ cơ sở
tri thức (công cụ tạo lập hệ cơ sở tri thức, hệ cơ
sở tri thức vỏ, hệ cơ sở tri thức rỗng), trên cơ sở
đó cài đặt các hệ cơ sở tri thức ứng dụng cụ thể.
Học phần còn yêu cầu sinh viên thực hiện, thể
nghiệm các hệ cơ sở tri thức ứng dụng sử dụng
môi trường/ngôn ngữ lập trình cụ thể. Học phần
giúp sinh viên nắm được các khái niệm cơ bản về
hệ cơ sở tri thức, biết cách phân tích, thiết kế và
xây dựng các hệ chuyên gia/hệ cơ sở tri thức ứng dụng. Hai V Pham hai@spice.ci.ritsumei.ac.jp 3 1 8/26/2012
Nội dung học phần bao gồm các phần cơ bản sau:
Fại cương về hệ cơ sở tri thức (Cấu trúc một hệ cơ sở tri thức)
Quá trình tạo lập hệ cơ sở tri thức
Sự khác biệt giữa hệ cơ sở tri thức và các hệ tin học truyền thống
Các lớp bài toán thực tế Phạm vi áp dụng
Thu thập tri thức; Quản trị tri thức; Mô tơ suy
diễn; Giao diện hệ thống; Mô đun giải thích;
Các bước xây dựng hệ cơ sở tri thức ứng dụng; Hai V Pham hai@spice.ci.ritsumei.ac.jp 4
1 . Stuart Russell, Peter Norvig, “Artificial Intelligence: A modern approach”, Pearson Education, 2007
2. Donald Waterman. A guide to Expert System Addision - Wesley Publishing company, 1987.
3. Bruce G.Buchanan, Edward h. Shortliffe. Rule - based ES: The MTCIN experirments of
the Standford heuristic programming project, Addision - Wesley Publishing company, 1988.
4. Robert I. Levine, Diane E. Drang, Biarry Edelson. A compehensive guide to AI & ES,
Mc. Graw - Hill book company, 1999
5. Michel Gondran. An introduction to ES, McGraw Hill Book Com.,1984 6.
S. Weiss, C. Kulikowski. A practical guide to desining ES, Rowman & Allanhed Publishers, 1988
7. I. Bratko. PROLOG programming for AI, Addision - Wesley Publishing company, 1986
8. A. Kabbaj. IA en LISP et PROLOG, Masson. 1991
9. A. Walker, M. Mc Cord, J. Sowa, W. Wilson. Knowledge Systems and Prolog, Addison-
Wesley Publishing company, 1987 10.
Jean - Louis Ermine. Systèmes Experrs: Technique et Documentation, Lavoisier, 1989
11. W. Black. Systèmes intelligents basés sur connaissance, Maisson, 1985.
12. Nguyễn Thanh Thủy, “Kỹ nghệ xử lý tri thức và hệ cơ sở tri thức”, FHBKHN
13. http://opencyc.org/doc/tut/?expand_all=1 Hai V Pham hai@spice.ci.ritsumei.ac.jp 5 DECISI S ON O S UPPORT R T SYSTEM E S M Hai V Pham 6 hai@spice.ci.ritsumei.ac.jp 2 8/26/2012 Inputs Outputs Computer Quản lý tri thức Các hệ CSTT Khám phá tri thức Knowledge Knowledge Base Knowledge Management Systems Discovery Tiếp nhận và tối ưu Cấu trúc của một Các kỹ thuật để khám hóa CSTT Hệ CSTT phá tri thức Hai V Pham hai@spice.ci.ritsumei.ac.jp 7
Hệ CSTT là chương trình máy tính được thiết
kế để giải quyết các vấn đề của chuyên gia
Hệ CSTT là hệ thống dựa trên tri thức để giải
quyết các bài toán phức tạp và các tri thức của chuyên gia. Hệ CSTT bao gồm:
◦ Cơ sở tri thức (tri thức chuyên gia): sự kiện, các luật, và các khái niệm
◦ Fộng cơ suy diễn (lập luận): mô hình hóa các lập luận của chuyên gia Hai V Pham hai@spice.ci.ritsumei.ac.jp 8 Fưa tri th t ức vào máy tính
Nhận thức: bằng cách tiếp nhận và tối ưu hóa CSTT Hai V Pham hai@spice.ci.ritsumei.ac.jp 9 3 8/26/2012 Tri thức Bộ tiếp nhận tri thức Vùng nhớ làm việc Knowledge editor Working memory Giao diện Fộng cơ suy diễn Interface Inference Engine Tìm kiếm Search Fiều khiển Control Chuyên gia Bộ xử lý ngôn Hệ giải thích Expert ngữ tự nhiên Explanation system Natural Processing Language Hai V Pham hai@spice.ci.ritsumei.ac.jp 10 Nội dung Chương trình truyền Hệ CSTT th t ống n Cấu trúc Tập các dòng lệnh Khối tri thức <-> thông qua thuật toán CSTT cụ thể
Khối điều khiển <-> Fộng cơ suy diễn Tính phức tạp Bài toán cụ thể, cơ Bài toán phức tạp bản Kinh nghiệm, tri thức Thuật toán <-> cài mới được cập nhật đặt Qui trình cài đặt Chuẩn phần mềm: Xây dựng hệ CSTT cấu trúc, hướng đối theo miền ứng dụng tượng cụ thể Phạm vi Ứng dụng nhỏ và vừa Ứng dụng lớn, phức mang tính cụ thể tạp giống tư duy của bộ não con người Hai V Pham hai@spice.ci.ritsumei.ac.jp 11 Hệ CSTT Một số loại khác Knowledge B ased L Others ựa chọn S Selection ystem Phân loại Diễn giải Classification Intepration D T ự báo ối ưu Forecast/ Optimization Prediction Kế hoạch, giám sát Giảng dạy Chuẩn đoán Planning/ Instruction Diagnosics mornitoring Hai V Pham hai@spice.ci.ritsumei.ac.jp 12 4 8/26/2012
1. Dự báo đường chứng khoán VN index/ SP500 / Nasdaq
2. Hệ chuyên gia chuẩn đoán bệnh
3. Dự báo thời tiết, thiên tai và thảm họa
4. Bán hàng trực tuyến thông minh qua mạng
5. Tính toán hiệu năng máy khoan hầm / mỏ
6. Hệ thống học trực tuyến thông minh
7. Giám sát tiến độ dự án ..etc Hai V Pham hai@spice.ci.ritsumei.ac.jp 13
SV chọn một trong các bài toán ứng dụng thực tế trên cơ sở:
1. Bài toán truyền thống đã có
2. Bài toán áp dụng hệ CSTT
So sánh yêu cầu giữa hai kiểu bài toán truyền thống và hệ CSTT
Phân tích các yêu cầu thực tế của bài toán ứng dụng đó Hai V Pham hai@spice.ci.ritsumei.ac.jp 14
Chuẩn bị: 4-5 sinh viên hình thành 01 nhóm
Chọn bài tập lớn – dự án theo nhóm
Trình bày và thảo luận ý tưởng bài tập dự án môn học Hai V Pham hai@spice.ci.ritsumei.ac.jp 15 5 8/28/2012 Tuần 2 (Week 2) Pham Van Hai Email: haivnu@yahoo.com Hai V Pham hai@spice.ci.ritsumei.ac.jp 1 Tập các sự ki k ện (Facts) F={f1,f ,…,f } là t các s ki 1,f , 2,…,fm} } à l tập các sự k ện ◦ f1: s ki 1: : sự k ện A ◦ f2: s ki B 2: : sự ki k ện B ◦ … ◦ fm: s ki m: : sự k ện n Tập lu l ật (Rulebase s s) R1: I F < conditi t on n 1 > T HEN n 1 > R2: IF i io i n 2 > T HEN i n 2 > … Rn: IF t on n n > T HEN n n > Hai V Pham hai@spice.ci.ritsumei.ac.jp 2
Mô tả luật ( Rule): một luật bao gồm nhiều sự
kiện được chia làm 2 phần: IF Gi G ả thiết THEN Kết lu l ận Gi G ả thiết đư
đ ợc kết nối các toán tử AND ho h ặc NOT Hai V Pham hai@spice.ci.ritsumei.ac.jp 3 1 8/28/2012 Bài tập trên lớp:
1. Tạo lập hệ CSTT dự báo thời tiết và thiên tai
2. Tạo lập hệ CSTT kiểm tra máy chủ mạng
Sinh viên làm bài tập 10 phút và thảo luận trên lớp Hai V Pham hai@spice.ci.ritsumei.ac.jp 4
Các sự kiện của tập F Tập luật R f = nắng 1 f = mây 2
R1: IF gió to AND mưa nhiều THEN bão f = gió 3 f = sét 4
…………………………………………. f = sao 5
………………………………………….. f = trăng 6 f = sương 7 …… Rm: IF AND hiện
tượng khác> THEN f = hiện-tượng m báo> Hai V Pham hai@spice.ci.ritsumei.ac.jp 5 Tri th t ức th t ủ tục Tri th t ức cấu trúc Mô tả cách thức giải Mô tả tri thức có quyết vấn đề hoặc cấu trúc công việc cụ thể Tri th t ức khai báo Siêu tri th t ức Tri th t ức Heuristic i s Mô tả vấn đề đó Mô tả tri thức về tri Mô tả tri thức về tri như thế nào thức thức Hai V Pham hai@spice.ci.ritsumei.ac.jp 6 2 8/28/2012 Ti T ếp nh n ận tri th t ức Ch C ng n (m T ủ động ở) Th T ụ động n (đóng) -Tri thức kinh
-Tri thức tự phân tích suy nghiệm diễn -Tri thức gián tiếp -Khám phá tri thức mới Hai V Pham hai@spice.ci.ritsumei.ac.jp 7 Cơ C sở tri th t ức Sộng n cơ c suy di d ễn Knowledg ed e B ase Inferenc n e E ngine
•Các định nghĩa, định lý
•Các định nghĩa, định lý •Các tiên đề •Các tiên đề Hệ CSTT K Sưa các chứng minh nowle l dge g B ase S ystem
và kết quả mới vào CSTT •Chứng minh •Các kết quả mới Hai V Pham hai@spice.ci.ritsumei.ac.jp 8
Hệ CSTT dựa vào logic mệnh đề và logic vị từ
Hệ CSTT dựa vào luật dẫn
Hệ CSTT dựa trên đối tượng Hệ CSTT dựa trên Frame
Hệ CSTT dựa trên mạng ngữ nghĩa
Hệ CSTT kết hợp phương pháp biểu diễn
Hệ CSTT kết hợp với Cơ sở dữ liệu Hai V Pham hai@spice.ci.ritsumei.ac.jp 9 3 8/28/2012 Hệ chuyên gia
Hệ trợ giúp quyết định Hệ logic mờ Hệ thống thông minh Intelligent Hybrid System
Thảo luận các ứng dụng tại lớp Hai V Pham hai@spice.ci.ritsumei.ac.jp 10
Chuẩn bị: 4-5 sinh viên hình thành 01 nhóm
Chọn bài tập lớn – dự án theo nhóm
Trình bày tên dự án bài tập lớn môn học
Trình bày ý tưởng dự án –bài tập lớn môn học
Thông tin học liệu môn học:
http://ritsumei.academia.edu/HaiVPham/Teaching/ Hai V Pham hai@spice.ci.ritsumei.ac.jp 11 4 9/11/2012 Tuần 3&4 (Week 3&4) Pham Van Hai Email: haivnu@yahoo.com Hai V Pham hai@spice.ci.ritsumei.ac.jp 1
Hệ MYCIN là một hệ chuyên gia ra đời từ
những năm 1970 tại đại học Standford, Hoa Kỳ.
MYCIN sử dụng hệ lập luận gần đúng để xử lý
các luật và diễn giải dựa trên độ đo chắc chắn Nguồn học liệu:
◦ The MYCIN Experiments of the Stanford Heuristic Programming Project
◦ Website http://aitopics.net/RuleBasedExpertSystems Hai V Pham hai@spice.ci.ritsumei.ac.jp 2
(Trích nguồn tài liệu: The MYCIN Experiments of the Stanford Heuristic Programming Project) Hai V Pham hai@spice.ci.ritsumei.ac.jp 3 1 9/11/2012
Chuẩn đoán bệnh của bệnh nhân: Thông qua tiểu
sử, bệnh án và các triệu chứng bệnh nhân sau đó
đưa ra gợi ý bệnh có thể xảy ra của người bệnh.
Phương pháp điều trị của bác sĩ: Theo diễn biến
tình trạng bệnh nhân, pháp đồ điều trị và đối
thoại trực tiếp với bệnh nhân.
Dự đoán kết quả và diễn biến của bệnh nhân:
Thông qua diễn biến của bệnh theo trình tự logic.
Tư vấn pháp đồ điều trị của bác sĩ và sử dụng thuốc, dược phẩm. Hai V Pham hai@spice.ci.ritsumei.ac.jp 4
Xuất phát từ bài toán nhiều loại thuốc kháng
sinh, kháng vi cũng như có nhiều loại vi trùng
với các cách xử lý khác nhau, nên chỉ có các
thầy thuốc chuyên gia thuộc lĩnh vực này mới
có thể có liệu pháp chữa trị hiệu quả. Lặc điểm:
◦ Yêu cầu thông tin về lâm sàng, > 450 luật (Rules)
◦ Tri thức chuyên gia về lĩnh vực kháng sinh ◦ Khả năng phán đoán
◦ Suy luận những tri thức hiện có
◦ Lưa ra phán đoán và lời khuyên Hai V Pham hai@spice.ci.ritsumei.ac.jp 5 Hai V Pham hai@spice.ci.ritsumei.ac.jp 6 2 9/11/2012 CSDL tĩnh (Static Database) Static i c D B bao gồm: •Rules •Meta-Rules •Templates •Rule Properties •Context Properties •Knowledge Acquisition System Hai V Pham hai@spice.ci.ritsumei.ac.jp 7 Dynamic DB Bao gồm: Patient Data Laboratory Data Context Tree Built by Consultation System Used by Explanation System Hai V Pham hai@spice.ci.ritsumei.ac.jp 8
Mạng ngữ nghĩa là một phương pháp biểu
diễn tri thức sử dụng đồ thị (grapth) trong đó:
◦ Nút (node) biểu diễn đối tượng (object)
◦ Cung biểu diễn quan hệ giữa các đối tượng là Hiện tượng Cảm cúm Triệu Sốt chứng Thời tiết thay đổi do Hai V Pham hai@spice.ci.ritsumei.ac.jp 9 3 9/11/2012 Hai V Pham hai@spice.ci.ritsumei.ac.jp 10
Các kiểu giá trị trong MYCIN Hai V Pham hai@spice.ci.ritsumei.ac.jp 11 Nội dung:
◦ Chọn tên dự án môn học
◦ Số lượng 20 nhóm: 5 sinh viên / nhóm
◦ Trưởng nhóm trình bày ý tưởng và tên dự án môn học Hai V Pham hai@spice.ci.ritsumei.ac.jp 12 4 9/18/2012 Tuần 5 (Week 5) Pham Van Hai Email: haivnu@yahoo.com Hai V Pham hai@spice.ci.ritsumei.ac.jp 1
Các kiểu giá trị trong MYCIN Hai V Pham hai@spice.ci.ritsumei.ac.jp 2 Ví dụ:
Ngữ cảnh Tham biến Giá trị CF Đầu Cảm giác Paracetamon .15 đau Mũi Nhạy cảm dị Penicillin -1.0 ứng Ngữ cảnh:
• các đối tượng được thảo luận bởi Mycin
•Các kiểu đối tượng khác nhau: bệnh nhân, thuốc, …
•2ược tổ chức trong một cây Hai V Pham hai@spice.ci.ritsumei.ac.jp 3 1 9/18/2012 Bệnh n nhân A VIRUS cúm A VIRUS cúm B VIRUS cúm C Thuốc kháng sinh Thuốc kháng sinh Thuốc cảm và thuốc cảm Câu hỏi:
1. VIRUS cúm có ảnh hưởng như thế nào?
2. Tại sao sử dụng thuốc kháng sinh và thuốc cảm cúm đồng thời.
3. Sử dụng các thuốc kháng sinh có ảnh hưởng đến sức khỏe như thế nào?
4. Thuốc cảm có tác dụng điều trị cúm như thế nào? Hai V Pham hai@spice.ci.ritsumei.ac.jp 4
Sources: Stanford Univ. Hai V Pham hai@spice.ci.ritsumei.ac.jp 5
Cơ chế suy diễn lùi (Backward changing)
◦ 2ưa giả thuyết sau đó kiểm chứng
◦ Tập trung vào kết quả sau đó rồi tìm trong cơ sở tri thức
thích đáng với bài toán đang xét
Các sự kiện, luật, các kỹ thuật suy diễn nhằm diễn
giải tình huống cho người sử dụng hệ thống dựa
trên lý thuyết chắc chắn của Standford. Lý thuyết
chắc chắn là một hình thức hóa tiếp cận heuristic
vào suy luận với sự không chắc chắn
MYCIN gồm các luật đơn giản, phức tạp và nhiều luật có cùng kết luận. Hai V Pham hai@spice.ci.ritsumei.ac.jp 6 2 9/18/2012
MB (Measurement of Belief): 2ộ đo tin cậy
MD (Measurement of Disbelief): 2ộ đo thiếu tin cậy
CF (Certain Factor): Hệ số tin cậy
H (Hypothesis): Giả thuyết H E (Evidence): Chứng cứ E Hai V Pham hai@spice.ci.ritsumei.ac.jp 7 Các chuyên gia có c th
t ể đặt sự tự tin vào các mối quan hệ mà m không ph p ải có c cảm giác là l nó n không n đúng. MB(H | E ) đo đ độ tin tư t ởng n của gi g ả thuyết H H khi có c hứng c ớ E MD(H | E ) đo đ độ không n tin tư t ởng n của gi g ả thuy u ết H H khi có c ch c ứng n cớ E 0 < M B(H | E ) < 1 trong n khi MD(H | E ) = 0 0 < M D(H | E ) < 1 trong n khi MB(H | E ) = 0 CF ( H | E ) = M B(H | E ) – MD(H | E ) Hai V Pham hai@spice.ci.ritsumei.ac.jp 8 Lu L ật đơn gi g ản: I f(e) t hen ( c)
CF(e) là độ do chắc chắn của chứng cớ
CF(r) là độ đo chắc chắn của luật suy diễn
Khi dó: CF(c) là độ đo chắc chắn của kết luận CF(c) = CF(e) * CF(r)
CF(c) ∈[-1,1] được kết luận như sau:
2ại lượng CF tiến về 1 cho thấy sự tin tưởng kết luận là đúng
2ại lượng CF tiến về -1 cho thấy sự tin tưởng kết luận là không đúng
2ại lượng CF bằng 0 kết luận ý kiến trung lập Hai V Pham hai@spice.ci.ritsumei.ac.jp 9 3 9/18/2012 Lu L ật ghép If(e1 A ND e 2) t hen CF ( e1 A ND e 2) = M IN(C ( F C (e ( 1 e ), ) , C F(e2)) ) if ( e1 O R e 2) t hen ( c) CF ( e1 O R e 2) = M AX(C ( F C ( F e ( 1), 1) , C F(e2)) 2) Lu L ật ph p ức tạp if ( (e1 A ND e 2) O R e 3) t hen ( c) CF ( (e1 A ND e 2) O R e 3) = M AX(M ( I M N( N C ( F C (e ( 1), 1) , CF(e2)) 2) , ) C F(e3)) 3) Hai V Pham hai@spice.ci.ritsumei.ac.jp 10 Ví V dụ: : Lu L ật ghép
CF(bệnh nhân bị đau đầu) = 0.7
CF(bệnh nhân bị viêm họng) = 0.5
CF(bệnh nhân bị đau đầu And bệnh nhân bị viêm họng) = 0.5
CF(bệnh nhân đau đầu Or bệnh nhân bị viêm họng) = 0.7 Hai V Pham hai@spice.ci.ritsumei.ac.jp 11
Các nhóm thực hiện dự án môn học với tiến độ
giữa học kỳ bao gồm các phần như sau: 1. Mục đích 2. Phạm vi
3. Các sự kiện, ngữ cảnh và cách biểu diễn tri thức
4. 2ộng cơ suy diễn, các luật và diễn giải của luật
5. Sơ đồ kiến trúc hệ thống (system architechture)
Ghi chú: các đề mục nêu trên có thể thêm, bớt
hoặc thay đổi tùy thuộc vào mỗi dự án Hai V Pham hai@spice.ci.ritsumei.ac.jp 12 4 9/25/2012 Tuần 6 (Week 6) Pham Van Hai Email: haivnu@yahoo.com Hai V Pham hai@spice.ci.ritsumei.ac.jp 1 Lu L ật có c dạng n NOT CF(NOT O e) e = - CF(e) Kết hợp các lu l ật (Rule l ) có c cùng kết lu l ận
- Rule 1: If(e1) then (c) CF(r1)
- Rule 2: If(e2) then (c) CF(r ( 2 CF C là l kêt lu l ận của Rule 1 & 2 ◦ Trong trường n hợp CF(t1) và v Cf(t2) đều dương
Ctong = CF(t1) + CF(t2) – CF(t1) * CF(t2) ◦ Trong trường n hợp CF(t1) và v Cf C (t ( 2) đều âm â thì:
Ctong = CF(t1) + CF(t2) + CF(t1) * CF(t2) ◦ Trong trường
n hợp CF(t1) khác dấu với CF(t2) thì: Cto t n o g = (C ( F(t ( 1) + CF C (t ( 2)) ) / (1 – MIN(A ( BS(C ( F(t ( 1)) ) , ) ABS(C ( F( F t2)) ) )) ) Hai V Pham hai@spice.ci.ritsumei.ac.jp 2 If (e) then (c) Áp dụng: CF( sốt VIRUS cúm) = 0.75
CF (IF sốt VIRUS cúm THEN chuẩn đoán bị cúm) = 0.5
=> CF (chuẩn đoán bị cúm) = 0.75*0.5 Hai V Pham hai@spice.ci.ritsumei.ac.jp 3 1 9/25/2012
Suy diễn luật đơn giản
Suy diễn luật với toán tử AND Hai V Pham hai@spice.ci.ritsumei.ac.jp 4
Suy diễn luật với toán tử OR
Suy diễn luật với toán tử NOT Hai V Pham hai@spice.ci.ritsumei.ac.jp 5
Cho các luật và các độ đo tin cậy như sau: R1: A B CF(R1) = 0,5 CF(A) = 0,25 R2: C D CF(R2) = 0,25 CF(C) =0,5
R3: (- F) G CF(R3) = 0,75 CF(F) = -0,5
R4: (B∧-D)∨I J CF(R4) = 0,25 CF(I) = 0,4 a. Tính CF(J)=?
b. Biểu diễn mạng ngữ nghĩa cho các luật Hai V Pham hai@spice.ci.ritsumei.ac.jp 6 2 9/25/2012 Công cụ (Tools) Chuyên gia (Expert) Công cụ tạo lập hệ Kỹ sử xử lý chuyên gia tri thức (Tools for creating KBs) Hệ CSTT / Hệ chuyên ê gia/ / Knowledge Based Systems Người sử dụng (Users) Hai V Pham hai@spice.ci.ritsumei.ac.jp 7
Thu thập cơ sở tri thức (Knowledge Acquisition)
Biểu diễn tri thức (Knowledge Representation)
Kiểm tra và đánh giá (Test and Evaluation)
Vận hành và bảo trì (Operation and Maintainance) Hai V Pham hai@spice.ci.ritsumei.ac.jp 8
Thu thập cơ sở tri thức (Knowledge Acquisition)
◦ Là thành phần chính của hệ chuyên gia /hệ CSTT
◦ Quá trình diễn ra do kỹ sư tri thức đảm nhiệm để
biểu diễn các thông tin và tri thức của chuyên gia cho máy tính hiểu được
◦ Quá trình tích lũy các tri thức của chuyên gia đưa vào hệ thống Tri thức của chuyên gia Kinh nghi Tri th ệm giải quyết Kinh nghiệm và phương ức v chuyên sâu ấn đề pháp thực hiện Hai V Pham 9 hai@spice.ci.ritsumei.ac.jp 3