Đề Cương Nhập Môn Trí Tuệ Nhân Tạo PTIT
Cấu trúc đề thi trí tuệ nhân tạo PTIT
Câu 1: 2 điểm
- 1 trong 4 thuật toán tìm kiếm mù ( DFS, BFS, UCS, IDS)
- 1 trong 3 thuật toán tìm kiếm có thông tin ( A*, tham lam, IDA*)
Câu 2: 2 điểm
- Chuyển các câu sang logic vị từ + chuẩn hóa dạng CNF ( Clause Form )
- Sử dụng 1 trong 4 thủ tục suy diễn để chứng minh câu truy vấn
( suy diễn tiến , suy diễn lùi, phép giải , phép giải + phản chứng )
Câu 3: 3 điểm
- Xây dựng mạng bayes
- Tính xác xuất nhân quả ( chuẩn đoán ) ( dạng P(A|B) )
- Dạng P(A|B,C)
Câu 4: 3 điểm
- Tìm nút gốc cho cây quyết định sử dụng thuật toán ID3
- Thuật toán k láng giềng hoặc phương pháp phân loại Bayes đơn giản.
Phần 1: Các thuật toán tìm kiếm
- Tìm kiếm mù
- Tìm kiếm theo chiều rộng (BFS)
*Nguyên tắc: Trong số những nút biên chọn những nút nông nhất (gần nút gốc nhất) để mở rộng
*Xử lí nút lặp: KHÔNG đưa nút đã được duyệt (mở rộng) hoặc đang thuộc tập biên O vào tập biên.
Ví dụ 1.1:
BFS
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As, Bs |
| 2 | A | Bs, Ca,Da |
| 3 | B | Ca,Da |
| 4 | C | Da,Gc |
| 5 | D | Gc |
| 6 | G | Đích |
Đường đi: G←C← A← S
Độ sâu: d = 3
Ví dụ 1.2:
BFS
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As, Bs |
| 2 | A | Bs, Ca,Da |
| 3 | B | Ca, Da |
| 4 | C | Da, Ec |
| 5 | D | Ec, Fd |
| 6 | E | Fd, Ge |
| 7 | F | Ge |
| 8 | G | Đích |
Đường đi: G← E← C← A← S
Độ sâu d = 4
Ví dụ: 1.3
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As,Bs,Gs |
| 2 | A | Bs,Gs,Ca,Da |
| 3 | B | Gs,Ca,Da |
| 4 | G | Đích |
Đường đi: G← S
Độ sâu: d = 1
- Tìm kiếm theo chiều sâu (DFS)
*Xử lí nút lặp:
- Có lặp các nút ĐANG THUỘC TẬP BIÊN
- Không đưa các nút ĐÃ ĐƯỢC DUYỆT vào tập biên
Ví dụ 2.1:
DFS
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As,Bs,Gs |
| 2 | A | Ca,Da,Bs,Gs |
| 3 | C | Gc,Da,Bs,Gs |
| 4 | G | Đích |
Đường đi: G← C← A← S
Độ sâu: d = 3
Ví dụ 2.2:
DFS
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ba,Ca,Da,Bs |
| 3 | Ba | Cb,Ca,Da,Bs |
| 4 | Cb | Dc,Gc,Ca,Da,Bs |
| 5 | Dc | Gd,Gc,Ca,Da,Bs |
| 6 | Gd | Đích |
Đường đi: G← D← C← B← A← S
Độ sâu d = 5
Ví dụ 2.3:
DFS
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ba,Ca,Da,Ga,Bs |
| 3 | Ba | Cb,Ca,Da,Ga,Bs |
| 4 | Cb | Gc,Ca,Da,Ga,Bs |
| 5 | Gc | Đích |
Đường đi: G← C← B← A← S
Ví dụ 2.4:
DFS
| STT | Nút được mở | Tập biên O |
| 0 | S | |
| 1 | S | As,Bs |
| 2 | A | Ca,Da,Bs |
| 3 | C | Ec,Da,Bs |
| 4 | E | Ge,Da,Bs |
| 5 | G | Đích |
Đường đi: G← E← C← A← S
Độ sâu d = 4
- TÌm kiếm theo giá thành thống nhất (UCS)
**g(m) min
*Xử lí nút lặp: Nếu nút có chi phí tốt hơn:
+ĐƯA LẠI vào danh sách nếu ĐÃ MỞ RỘNG
+CẬP NHẬT thay nút cũ nếu ĐANG TRONG DANH SÁCH
Ví dụ 3.1:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S(0) | |
| 1 | S | As(3),Bs(2) |
| 2 | Bs | As(3),Cb(6) |
| 3 | As | Ca(4),Da(6) |
| 4 | Ca | Dc(5),Gc(7) |
| 5 | Dc | Gc(7) |
| 6 | Gc | Đích |
Đường đi: G← C← A← S
chi phí c = 7
Ví dụ 3.2:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As(3),Bs(1) |
| 2 | Bs | As(3),Cb(5) |
| 3 | As | Ca(4),Da(6),Ga(7) |
| 4 | Ca | Da(6),Ga(7) |
| 5 | Da | Ga(7) |
| 6 | G | Đích |
Đường đi: G← A← S
chi phí : c = 7
Ví dụ 3.3:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S | |
| 1 | S | As(3),Bs(5) |
| 2 | As | Bs(5),Ca(7),Da(4) |
| 3 | Da | Bs(5),Ca(7),Ed(5),Fd(6) |
| 4 | Bs | Ca(7),Ed(5),Fd(6) |
| 5 | Ed | Ca(7),Fd(6),Ge(11) |
| 6 | Fd | Ca(7),Ge(11) |
| 7 | Ca | Ge(11) |
| 8 | Ge | Đích |
Đường đi: G← E← D← A← S
chi phí c = 11
Ví dụ 3.4:
| STT | Nút được mở | Tập biên O |
| 0 | S | |
| 1 | S | As(1),Bs(2),Gs(9) |
| 2 | As | Bs(2),Gs(9),Ca(3),Da(4) |
| 3 | Bs | Gs(9),Ca(3),Da(4) |
| 4 | Ca | Gc(7),Da(4) |
| 5 | Da | Gc(7) |
| 6 | Gc | Đích |
Đường đi: G← C← A← S, chi phí c = 7
- Tìm kiếm sâu dần (IDS)
**IDS từng độ sâu
*Xử lí nút lặp: Vì bản chất là DFS nên ở mỗi độ sâu c :
+KHÔNG đưa các nút ĐÃ DUYỆT vào tập biên
+LẶP các nút ĐANG THUỘC TẬP BIÊN
Ví dụ 4.1:
| STT | Nút được mở rộng | Tập biên O |
| C = 0 | ||
| 0 | S | |
| S | ||
| C = 1 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Bs |
| 3 | Bs | |
| C = 2 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ba,Ca,Da,Bs |
| 3 | Ba | Ca,Da,Bs |
| 4 | Ca | Da,Bs |
| 5 | Da | Bs |
| 6 | Bs | |
| c = 3 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ba,Ca,Da,Bs |
| 3 | Ba | Cb,Ca,Da,Bs |
| 4 | Cb | Ca,Da,Bs |
| 5 | Ca | Dc,Gc,Da,Bs |
| 6 | Dc | Gc,Da,Bs |
| 7 | Gc | Đích |
Đường đi: G← C← A← S
Độ sâu d = 3
Ví dụ 4.2:
| STT | Nút được mở rộng | Tập biên O |
| C = 0 | ||
| 0 | S | |
| 1 | S | |
| c = 1 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Bs |
| 3 | Bs | |
| C = 2 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ba,Ca,Da,Ga,Bs |
| 3 | Ba | Ca,Da,Ga,Bs |
| 4 | Ca | Da,Ga,Bs |
| 5 | Da | Ga,Bs |
| 6 | Ga | Đích |
Đường đi : G← A←S
Độ sâu d = 2
Ví dụ 4.3:
| STT | Nút được mở rộng | Tập biên O |
| C = 0 | ||
| 0 | S | |
| 1 | S | |
| C= 1 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Bs |
| 3 | Bs | |
| C = 2 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ca,Da,Bs |
| 3 | Ca | Da,Bs |
| 4 | Da | Bs |
| 5 | Bs | |
| C = 3 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ca,Da,Bs |
| 3 | Ca | Ec,Da,Bs |
| 4 | Ec | Da,Bs |
| 5 | Da | Fd,Bs |
| 6 | Fd | Bs |
| 7 | Bs | |
| C = 4 | ||
| 0 | S | |
| 1 | S | As,Bs |
| 2 | As | Ca,Da,Bs |
| 3 | Ca | Ec,Da,Bs |
| 4 | Ec | Ge,Da,Bs |
| 5 | Ge | Đích |
Đường đi: G← E← C← A← S
Độ sâu d = 4
Ví dụ 4.4:
| STT | Nút được mở rộng | Tập biên O |
| C = 0 | ||
| 0 | S | |
| S | ||
| C = 1 | ||
| 0 | S | |
| 1 | S | As,Bs,Gs |
| 2 | As | Bs |
| 3 | Bs | Gs |
| 4 | Gs | Đích |
Đường đi: G← S
Độ sâu d = 1
- Tìm kiếm tham lam
**h(n) min
*Xử lý nút lặp:
Ví dụ 5.1:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S(6) | |
| 1 | S | As(3),Bs(4) |
| 2 | As | Bs(4), Ca(2),Da(2),Ga(0) |
| 3 | Ga | Đích |
Đường đi: G← A← S
Chi phí c = 7
- Tìm kiếm A*
*f(m) = g(m)+h(m) min
*Xử lí nút lặp: Nếu nút có chi phí tốt hơn:
- Đưa lại vào danh sách nếu đã mở rộng
- Cập nhật nút cũ có giá thành kém hơn nếu đang trong tập biên
Ví dụ 6.1
| STT | Nút được mở rộng | Tập biên O |
| 0 | S(6) | |
| 1 | S | As(7),Bs(6) |
| 2 | Bs | As(7),Cb(8) |
| 3 | As | Ca(6),Da(8) |
| 4 | Ca | Dc(7),Gc(7) |
| 5 | Dc | Gc(7) |
| 6 | Gc | Đích |
Đường đi: G← C← A← S
Chi phí c = 7
Ví dụ 6.2:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S(6) | |
| 1 | S | As(6),Bs(5) |
| 2 | Bs | As(6),Cb(6) |
| 3 | As | Cb(6),Da(8),Ga(7) |
| 4 | Cb | Da(8),Ga(7) |
| 5 | Ga | Đích |
Đường đi: G← A← S chi phí c = 7
Ví dụ 6.3:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S(4) | |
| 1 | S | As(8), Bs(6) |
| 2 | Bs | As(8), Db(13) |
| 3 | As | Da(8),Ca(9) |
| 4 | Da | Ca(9),Ed(8),Fd(12) |
| 5 | Ed | Ca(9),Fd(12),Ge(11) |
| 6 | Ca | Fd(12),Ge(11) |
| 7 | Ge | Đích |
Đường đi:
G← E← D← A← S chi phí: 11
Ví dụ 6.4:
| STT | Nút được mở rộng | Tập biên O |
| 0 | S(6) | |
| 1 | S | As(7),Bs(2),Gs(9) |
| 2 | Bs | As(7),Gs(9),Db(8) |
| 3 | As | Gs(9),Db(8),Ca(4) |
| 4 | Ca | Gc(7),Db(8), |
| 5 | Gc | Đích |
Đường đi: G← C← A← S
Chi phí c = 7
- Tìm kiếm IDA*
IDA* = DFS + A*
-Thuật toán duyệt theo DFS
-f(n) chỉ dùng để xét ngưỡng cho nút
Xử lí nút lặp: Vì bản chất là DFS nên với mỗi ngưỡng i:
+KHÔNG lặp các nút ĐÃ ĐƯỢC MỞ RỘNG
+LẶP các nút ĐANG NẰM TRONG TẬP BIÊN
Ví dụ 7.1:
alpha = 8
| STT | Nút được mở rộng | Tập biên O |
| i=0 | ||
| i = 8 | ||
| 0 | S(4) | |
| 1 | S | As(8),Bs(6) |
| 2 | As | Da(8),Bs(6) |
| 3 | Da | Ed(8),Bs(6) |
| 4 | Ed | Bs(6) |
| 5 | Bs | |
| i = 16 | ||
| 0 | S(4) | |
| 1 | S | As(8),Bs(6) |
| 2 | As | Ca(9),Da(8),Bs(6) |
| 3 | Ca | Ec(11),Da(8),Bs(6) |
| 4 | Ec | Ge(14),Da(8),Bs(6) |
| 5 | Ge | Đích |
Đường đi: G← E← C← A← S
Chi phí c = 14
Phần 2: Logic Vị Từ
- Logic mệnh đề
- Các quy tắc suy diễn
- Logic vị từ
- Các quy tắc duy diễn
III. Chuẩn hóa dạng CNF và Caluse Form
**1 trong 2 dạng:
-Dạng 1: A1 v A2 v.. Am
-Dạng 2: A1 ( các câu đơn )
**Tóm Tắt:
Bước 1: Khử tương đương ⇔, kéo theo⇒ bên trong ヨ,∀
Bước 2: Khử ヨ,∀
+Khử ヨ: –TH1: ヨx P(x) ☰ P(C) { x/C}
-TH2: ∀xヨyP(x,y) ☰ ∀x P( x, f(x) )
+Khử ∀: ∀x( P(x) v Q(x) ) ☰ P(x) v Q(x)
Bước 3: Đưa về 1 trong 2 dạng:
Dạng 1: A1 v A2 v A3 v.. An
Dạng 2: A1 ( câu đơn )
Ví dụ:
Boy( Nam ) ^ Handsome( Nam )
Áp dụng luật loại trừ và ta có 2 câu mới: Boy(Nam) (1)
Handsome( Nam ) (2)
Bước 4: Chuẩn hóa tên sao cho mỗi câu có biến của riêng mình.
Ví dụ 8.1:
Biểu diễn các câu sau ở dạng logic vị từ và viết chúng ở dạng chuẩn CNF (clause Form):
Giải:
1.∀x ( Boy(x) ⇒ Like(x, Football) )
☰∀x ( ㄱBoy(x) v Like(x, Football ) )
☰ㄱBoy(x) v Like(x, Football)
2..∀x ( Like( x, Football ) ⇒ Have( x , Shoes ) )
☰ ∀x ( ㄱLike(x,Football) v Have( x, Shoes ) )
☰ ㄱLike(x,Football) v Have( x, Shoes )
☰ ㄱLike(y,Football) v Have( y, Shoes )
3.Boy(Nam)
Ví dụ 8.2:
1.∀x ( M(x) ⇒ N(x) )
≣ ∀x ( 乛M(x) v N(x) )
≣ 乛M(x) v N(x)
2..∀x ( T(x) ⇒ 乛N(x) )
≣ .∀x ( 乛T(x) v 乛N(x) )
≣ 乛T(x) v 乛N(x)
≣乛T(y) v 乛N(y)
- Ǝx( T(x) ^ R(x) )
≣ Ǝx( T(x) ^ R(x) )
≣ T(C) ^ R(C) {x/C} : Luật loại trừ tồn tại
Áp dụng luật loại trừ và
3.1. T(C) 3.2. R(C)
- Suy diễn tiến
4.1. Định nghĩa
*Bắt đầu từ các câu trong KB, sử dụng GMP và các quy tắc suy diễn để sinh ra các câu mới cho đến khi sinh không thể sinh ra câu nào nữa.
*Trong bài thường gặp 2 dạng GMP:
*Dạng 1:
p1 và p1’ có thể hợp nhất tại phép thế Ө
Ví dụ:
⇒
*Dạng 2:
p1 và p1’ , p2 và p2’ có thể hợp nhất tại phép thế Ө
Ví dụ:
- Like( Tom, Fish )
⇒
tại { x/Tom, y/Fish }
4.2. Các ví dụ suy diễn tiến
*Ví dụ 4.2.1
*Chứng minh câu truy vấn trong phần a sử dụng phương pháp suy diễn tiến.
∀x( Dalmatian(x) ⇒ Dog(x) ) (1)
Dalmatian( Bo ) (2)
∀x( Dalmatian(x) ⇒ Like( x, Milk ) (3)
Circus( Bo ) (4)
Q: Ǝx( Dog(x) ^ Like( x, Milk ) ^ Circus (x) )
*Cách làm:
-Suy diễn tiến: Sử dụng KB và GMP để suy ra câu :
Dog(Bo) ^ Like( Bo, Milk) ^ Cirus( Bo)
-Sử dụng nhập đề tồn tại
Giải:
GMP (1),(2) ⇒ Dog( Bo ) {x/Bo} (5)
GMP (2),(3) ⇒ Like( Bo, Milk ) {x/Bo} (6)
Nhập đề và: (5),(6),(7)
⇒ Dog(Bo) ^ Like( Bo, Milk) ^ Cirus( Bo) (7)
Nhập đề tồn tại ⇒ Ǝx( Dog(x) ^ Like( x, Milk ) ^ Circus (x) ) ( dpcm )
*Ví dụ 4.2.2
∀x( M(x) ⇒ N(x) ) (1)
∀x( T(x) ⇒ -N(x) ) (2)
Ǝx ( T(x) ^ R(x) ) (3)
Q: Ǝx( R(x) ^ -N(x) )
-Chuẩn hóa câu (3) ta được 2 câu: T(C) (4)
R(C) (5)
GMP (2),(4) ⇒ -N(C) (6)
Nhập đề và (5),(6) ⇒ R(C) ^ -N(C) (7)
Nhập đề tồn tại cho (7) ⇒ Ǝx( R(x) ^ -N(x) ) ( đpcm )
Ví dụ 4.2.3
*Chứng minh câu truy vấn trong phần a sử dụng phương pháp suy diễn tiến.
∀x( Child(x) ⇒ Like( x, Ipad ) (1)
∀x∀y( Child(x)^Like(x,y) ⇒ Buy(x,y)) (2)
Child(Nam) (3)
Q: Buy( Nam, Ipad)
GMP (1) (2) ⇒ Like( Nam,IPad) (4)
GMP (2),(3),(4) ⇒ Buy(Nam,Ipad) (dpcm)
Ví dụ 4.2.4:
∀x( P(x) ^ C(x) ⇒ W(x) ) (1)
∀x( P(x) ⇒ C(x) ) (2)
∀x( IT(x) ⇒ P(x) ) (3)
IT(Nam) (4)
Q: W(Nam)
GMP (3),(4) ⇒ P(Nam) (5)
GMP (2),(5) ⇒ C(Nam) (6)
GMP (1),(5),(6) ⇒ W(Nam) (đpcm)
Ví dụ 4.2.5:
∀x( Hoc(x) ⇒ VanHoa(x) ) (1)
∀x(Trom(x) ⇒ -VanHoa(x) ) (2)
Ǝx( Trom(x) ^ ThongMinh(x) ) (3)
Q: Ǝx( ThongMinh(x) ^ -Hoc(x) )
Chuẩn hóa CNF (3) ta được 2 câu:
Trom( C ) (4)
ThongMinh( C ) (5)
*Ý tưởng: sử dụng GMP để suy ra câu ThongMinh(C) ^ -Hoc(C)
sau đó dùng nhập đề tồn tại suy ra đpcm.
GMP (2),(4) ⇒ -VanHoa( C ) (6)
Modus Tollens (1), (6) ⇒ -Hoc( C ) (7)
Nhập đề và (5),(7) ⇒ ThongMinh( C ) ^ -Hoc( C )
Nhập đề tồn tại ⇒ Ǝx( ThongMinh(x) ^ -Hoc(x) ) ( đpcm )
- Suy diễn lùi
5.1. Định nghĩa
– Ngược lại với suy diễn tiến, suy diễn lùi bắt đầu từ cầu truy vấn, sau đó tìm các sự kiện và quy tắc trong KB cho phép chứng minh câu truy vấn là đúng.
Thủ tục suy diễn lùi:
-Với mỗi câu q, nếu tồn tại q’ hợp nhất được với q thì trả về hợp từ
q được chứng minh
Ví dụ:
KB: Cat( Tom )
Q: Cat( Tom ) ?
câu truy vấn Q hợp nhất được với Cat( Tom ) trong KB → Q được chứng minh.
-Với mỗi quy tắc có vế phải q’ hợp nhất được với q cố gắng chứng minh các phần từ vế trái bằng suy diễn lùi:
Ví dụ:
KB: ∀x( Hoc(x) ^ Gioi( x ) ⇒ VanHoa(x) )
Q: VanHoa(Nam)
câu truy vấn Q hợp nhất được với vế phải của KB
⇒ cần chứng minh vế trái Hoc(Nam) ^ Gioi( Nam ) bằng suy diễn lùi.
*Chú ý:
Nếu câu truy vấn Q có dạng các câu đơn hội với nhau:
A ^ B ^ C..
ta chứng minh từng câu đơn bằng suy diễn lùi.
vì nếu các câu đơn đúng, áp dụng luật nhập đề và thì các câu đơn hội với nhau cũng tất nhiên đúng.
5.2. Các ví dụ suy diễn lùi
Ví dụ 5.2.1:
∀x( Child(x) ⇒ Like( x, Ipad ) (1)
∀x∀y( Child(x) ^ Like(x,y) ⇒ Buy(x,y) ) (2)
Child( Nam ) (3)
Q: Buy( Nam, Ipad ) ?
Ví dụ 5.2.2
- Suy diễn sử dụng phép giải
6.1. Phương pháp: Sử dụng phép giải và các quy tắc suy diễn để chứng minh câu truy vấn cần tìm.
*Chú ý: khi sử dụng phép giải cần đưa hết các câu về dạng CNF
( A v B v C, hoặc A )
-Trong logic mệnh đề:
–Trong logic vị từ:
p2 và -(-p2’) có thể hợp nhất bởi phép thế θ
Ví dụ 1:
Giàu( x ) v Giỏi (x) (1)
-Gioi( Bắc ) v Đẹp Trai ( Bắc ) (2)
Áp dụng phép giải ⇒ Giàu(Bắc) v Đẹp Trai( Bắc )
Ví dụ 2:
Cao(x) v DepTrai(x) (3)
-Cao(Nam) (4)
Áp dụng phép giải ⇒ DepTrai(Nam)
6.2. Các ví dụ suy diễn sử dụng phép giải
Ví dụ 6.2.1:
KB:
ㄱDalmatian(x) v Dog(x) (1)
Dalmatian( Bo ) (2)
ㄱDalmatian(y) v Like( y, Milk ) (3)
Circus( Bo ) (4)
Q: Ǝx( Dog(x) ^ Like( x, Milk ) ^ Circus (x) )
cần chứng minh câu Dog(Bo) ^ Like(Bo, Milk) ^ Circus(Bo)
sau đó áp dụng nhập đề tồn tại
⇒ chứng minh từng câu Dog(Bo) , Like(Bo, Milk) , Circus(Bo) sử dụng phép giải.
Giải:
Áp dụng phép giải (1),(2) ⇒ Dog( Bo) (5)
Áp dụng phép giải (2),(3) ⇒ Like( Bo, Milk) (6)
Nhập đề và (4),(5),(6) ⇒ Dog(Bo) ^ Like(Bo, Milk) ^ Circus(Bo)
Nhập đề tồn tại ⇒ đpcm
Ví dụ 6.2.2
ㄱM(x) v N(x) (1)
ㄱT(y) v ㄱN(y) (2)
T(C) (3)
R(C) (4)
Q: Ǝx( R(x) ^ -N(x) )
Áp dụng phép giải (2),(3) ⇒ -N( C ) (5)
Nhập đề và (5),(4) ⇒ R(C) ^ -N(C) (6)
Nhập đề tồn tại cho (6) ⇒ Ǝx( R(x) ^ -N(x) ) ( đpcm )
Ví dụ 6.2.3
ㄱChild( x ) v Like( x, Ipad ) (1)
ㄱChild(z) v ㄱLike( z,y) v Buy (z,y ) (2)
Child(Nam) (3)
Q: Buy( Nam, Ipad)
Áp dụng phép giải đơn vị (2),(3) ⇒ ㄱLike( Nam,y) v Buy (Nam,y ) (4)
Áp dụng phép giải đơn vị (1),(3) ⇒ Like( Nam,Ipad) (5)
Áp dụng phép giải (4),(5) ⇒ Buy(Nam,Ipad) (đpcm)
Ví dụ 6.2.4:
-P(x) v -C(x) v W(x) (1)
-P(y) v C(y) (2)
-IT(z) v P(z) (3)
IT(Nam) (4)
Q: W(Nam)
Áp dụng phép giải (3),(4) ⇒ P(Nam) (5)
Áp dụng phép giải (2),(5) ⇒ C(Nam) (6)
Áp dụng phép giải (1),(5),(6) ⇒ W(Nam) (đpcm)
Ví dụ 6.2.5:
-Hoc(x) v VanHoa(x) (1)
-Trom(y) v -VanHoa(y) (2)
Trom(C) (3)
ThongMinh(C) (4)
Q: Ǝx( ThongMinh(x) ^ -Hoc(x) )
Áp dụng phép giải (2),(3) ⇒ -VanHoa(C) (5)
Áp dụng phép giải (1),(5) ⇒ -Hoc(C) (6)
Nhập đề và (4),(6) ⇒ ThongMinh(C) ^ -Hoc(C)
Nhập đề tồn tại ⇒ (đpcm)
VII. Suy diễn sử dụng phép giải và phản chứng
7.1. Phương pháp
*Tóm tắt:
+Thêm ㄱQ vào KB
+While( KB không chứa False )
{
-Chọn 2 câu trong KB có thể áp dụng được phép giải
-Thêm kết quả vào KB
}
*Lưu ý:
-Do sử dụng phép giải nên các câu trong KB cần đưa về dạng CNF
7.2. Các ví dụ suy diễn sử dụng phép giải và phản chứng
Ví dụ 7.2.1:
KB:
ㄱDalmatian(x) v Dog(x) (1)
Dalmatian( Bo ) (2)
ㄱDalmatian(y) v Like( y, Milk ) (3)
Circus( Bo ) (4)
Q: Ǝx( Dog(x) ^ Like( x, Milk ) ^ Circus (x) )
Thêm vào KB:
ㄱ(Ǝx( Dog(x) ^ Like( x, Milk ) ^ Circus (x) ) )
☰∀x( ㄱ(Dog(x) ^ Like( x, Milk ) ^ Circus (x) ) )
☰∀x( ㄱDog(x) v ㄱLike(x, Milk) v ㄱCircus(x) )
☰ㄱDog(x) v ㄱLike(x, Milk) v ㄱCircus(x)
☰ㄱDog(z) v ㄱLike(z, Milk) v ㄱCircus(z) (5)
Áp dụng phép giải (4),(5) ⇒ ㄱDog(Bo) v ㄱLike(Bo, Milk) (6)
Áp dụng phép giải (1),(2) ⇒ Dog(Bo) (7)
Áp dụng phép giải (2),(3) ⇒ Like(Bo,Milk) (8)
Áp dụng phép giải (6),(7) ⇒ ㄱLike(Bo, Milk) (9)
Áp dụng phép giải (8),(9) ⇒ False( đpcm)
Ví dụ 7.2.2:
ㄱM(x) v N(x) (1)
ㄱT(y) v ㄱN(y) (2)
T( C ) (3)
R( C ) (4)
Q: Ǝx( R(x) ^ -N(x) )
Thêm vào KB:
ㄱ( Ǝx( R(x) ^ -N(x) ) )
☰ ∀x ( ㄱR(x) v N(x) )
☰ㄱR(z) v N(z) (5)
Áp dụng phép giải (4),(5) ⇒ N(C) (6)
Áp dụng phép giải (2),(6) ⇒ ㄱT(C) (7)
Áp dụng phép giải (3),(7) ⇒ False
Phần 3: Suy diễn với Mạng Bayes
- Các tiên đề xác xuất và một số tính chất cơ bản
- Suy diễn với Mạng bayes
- Tính chất đặc biệt của Mạng bayes
*Mỗi nút V độc lập có điều kiện với tất cả các nút không phải hậu duệ của V, nếu biết giá trị các nút bố mẹ của V.
Ví dụ 1.1:
H độc lập có điều kiện với L,O,B nếu biết D
P( H | L,O,B,D ) = P( H | D )
Ví dụ 1.2:
P( ㄱB,ㄱC,ㄱA,ㄱD,ㄱH)
= P( ㄱB | ㄱC,ㄱA,ㄱD,ㄱH ). P( ㄱC |ㄱA,ㄱD,ㄱH )
.P( ㄱA | ㄱD,ㄱH ). P( ㄱD |ㄱH ). P( ㄱH)
= P( ㄱB | ㄱA, ㄱH) . P( ㄱC | ㄱA,ㄱD ). P(ㄱA). P(ㄱH). P( ㄱD)
= ( 1 – 0.7 ). ( 1 – 0.8 ). (1 – 0.5 ) . ( 1 – 0.2 ). ( 1 – 0,4 )
= …
- Suy diễn chuẩn đoán và suy diễn nhân quả
Ví dụ 2.1:
*Tính P(B\A):
*Tính (B\-A):
*Mạng đã cho có dạng Polytree do giữa 2 nút bất kì chỉ có 1 đường đi.
Ví dụ 2.2:
*Tính P( A|B,C ):
P(A|B,C) == ( * )
P(B,C|A) = =
P(A|B,C) + P(ㄱA|B,C) = 1 ( ** )
P(ㄱA|B,C) = =
⇒ Tính được P(B,C) từ ( ** )
thay vào (*) ⇒ P(A|B,C)
*Lời giải chi tiết:
Phần 4: Học Máy
- Thuật toán ID3
Ví dụ 4.1:
