Knowledge Practice - Bài tập biểu diễn và suy luận

Bài này dùng để nối toàn bộ module Knowledge thành một quy trình hoàn chỉnh:

bài toán thực tế
-> representation
-> Knowledge Base
-> query
-> inference
-> kiểm tra kết luận

Không nên chỉ nhìn đáp án. Với mỗi bài, hãy tự viết symbol, truth assignment hoặc từng bước suy luận trước.

Mục tiêu

Sau bài thực hành, bạn nên làm được:

• chuyển câu tiếng Việt sang logic;
• phát hiện implication bị đảo chiều;
• kiểm tra entailment ở bài nhỏ;
• dùng De Morgan, CNF và Resolution;
• viết predicate và quantifier cơ bản;
• nhận ra khi representation chưa mô tả đúng yêu cầu của bài toán.

Các lỗi tư duy cần tránh

1. Nhầm “có thể đúng” với “bắt buộc đúng”

Entailment yêu cầu query đúng trong mọi model thỏa KB, không chỉ một model.

2. Đảo implication

Từ:

không suy ra:

3. Nhầm OR với XOR

$P \lor Q$ cho phép cả hai cùng True.

4. Quên ngoặc

$P \to (Q \land R)$ khác $(P \to Q) \land R$.

5. Dùng $\exists$ như “duy nhất một”

$\exists x$ chỉ có nghĩa là tồn tại ít nhất một $x$.

6. Đổi vị trí $\forall$ và $\exists$ tùy ý

$\forall x\exists y$ thường không tương đương $\exists y\forall x$.

7. Nghĩ representation chỉ là bước phụ

Trong Knowledge, cách mã hóa facts và rules thường quyết định phần lớn độ đúng của hệ thống.

Một quy trình giải bài Knowledge

Khi gặp bài mới, có thể đi theo checklist:

Câu hỏi nên tự hỏi:

• mỗi symbol có nghĩa duy nhất không;
• có rule nào đang bị viết ngược chiều không;
• OR là inclusive hay exclusive;
• có constraint “ít nhất một” nhưng quên constraint “không quá một” không;
• KB có mâu thuẫn không;
• query cần chứng minh hay chỉ cần tìm một model thỏa mãn;
• số symbol có quá lớn cho brute-force model checking không.

Bài tự kiểm tra 1 - đọc biểu thức

Cho:

P: Có bài tập.
Q: Có deadline hôm nay.
R: Tôi học tối nay.

Biểu thức:

Hãy đọc bằng lời.

Đáp án: Nếu có bài tập và deadline là hôm nay thì tôi học tối nay.

Bài tự kiểm tra 2 - implication

Biết:

và:

Có được suy ra $P$ không?

Đáp án: Không. $Q$ có thể đúng vì một nguyên nhân khác.

Bài tự kiểm tra 3 - entailment

Biết:

Query:

Có:

không?

Đáp án: Có. Mọi model thỏa cả $P$ và $P \to Q$ đều buộc $Q=True$.

Bài tự kiểm tra 4 - De Morgan

Biến đổi:

Đáp án:

Bài tự kiểm tra 5 - CNF

Chuyển:

Loại implication:

Phân phối:

Đây là CNF.

Bài tự kiểm tra 6 - Resolution

Cho:

và:

Suy ra gì?

Đáp án:

Bài tự kiểm tra 7 - First-Order Logic

Các predicate:

Student(x): x là sinh viên.
Course(y): y là môn học.
Enrolled(x, y): x đăng ký y.

Viết câu:

Có ít nhất một môn học mà An đã đăng ký.

Một đáp án:

Bài tự kiểm tra 8 - phân biệt hai lượng từ

Giải thích khác biệt giữa:

và:

Đáp án:

• câu đầu: mỗi người thích ít nhất một thứ, có thể mỗi người thích một thứ khác nhau;
• câu sau: tồn tại một thứ mà tất cả mọi người đều thích.

Bài nhỏ để tự code

Hãy thử xây một knowledge base cho hệ thống quyết định sinh viên có được vào phòng thi hay không.

Giả sử:

C: đủ chuyên cần
F: đã đóng học phí
I: có giấy tờ tùy thân
E: được vào phòng thi

Rule:

Mức 1

Tạo truth table cho 4 symbol và xác định các model thỏa KB khi biết:

Mức 2

Viết một hàm Python brute-force thử mọi truth assignment và kiểm tra:

Mức 3

Thêm một trường hợp ngoại lệ:

X: có giấy xác nhận đặc biệt

và rule:

Sau đó giải thích vì sao từ $E$ không được suy ra $C \land F \land I$.

Bài tập tổng hợp 1 - Minesweeper như một Knowledge Base

Minesweeper là ví dụ tốt vì mỗi lần mở một ô, ta có thêm tri thức mới.

Giả sử một ô số 1 kề ba ô chưa mở A, B, C:

A B C
  1

Ta biết chính xác một ô trong ba ô chứa mìn. Có thể dùng representation theo domain:

{A, B, C} = 1

Nếu sau đó xác định A chắc chắn là mìn, cập nhật knowledge:

{B, C} = 0

Từ count bằng 0, suy ra:

B safe
C safe

Câu hỏi

1. Nếu biết {A, B, C} = 1 và C safe, sentence còn lại nên được cập nhật thế nào?
2. Nếu tiếp tục biết A mine, suy ra gì về B?
3. Vì sao representation {cells} = count tiện hơn việc viết toàn bộ tổ hợp proposition bằng tay?

Gợi ý đáp án:

1. {A, B} = 1.
2. B safe.
3. Representation giữ trực tiếp thông tin quan trọng của domain: tập ô chưa biết và số mìn còn lại. Việc cập nhật knowledge trở nên ngắn và ít lỗi hơn.

Bài tập tổng hợp 2 - đăng ký học phần

Cho predicates:

Student(x): x là sinh viên.
Passed(x, y): x đã qua môn y.
Prerequisite(y, z): y là môn tiên quyết của z.
CanRegister(x, z): x được đăng ký môn z.

Viết bằng First-Order Logic:

Nếu một sinh viên đã qua một môn và môn đó là tiên quyết của AI101 thì sinh viên đó có thể đăng ký AI101.

Một cách viết đơn giản:

Thử mở rộng

Nếu AI101 yêu cầu tất cả các môn tiên quyết chứ không phải chỉ một môn, rule trên đã đủ chưa?

Đáp án: Chưa. Rule trên nói chỉ cần tồn tại một cặp Passed(x,y) và Prerequisite(y,AI101) phù hợp là có thể suy ra CanRegister. Bài toán “đã qua tất cả prerequisite” cần representation hoặc công thức mạnh hơn để lượng hóa trên toàn bộ các môn tiên quyết.

Đây là ví dụ cho thấy viết được công thức chưa đồng nghĩa với mô hình hóa đúng yêu cầu.

Bài tập tổng hợp 3 - tìm counterexample

Cho:

Một bạn kết luận:

Hãy tìm một model chứng minh kết luận này không hợp lệ.

Chọn:

P = False
Q = True

Khi đó:

• $P \to Q$ là True;
• $Q \to P$ là False.

Chỉ một counterexample như vậy là đủ để bác bỏ suy luận.

Checklist trước khi kết thúc module Knowledge

Bạn nên tự trả lời được các câu sau mà không nhìn tài liệu:

• Knowledge Base là gì?
• $P \to Q$ khác $P \models Q$ ở đâu?
• Model là gì và vì sao $n$ symbol có tối đa $2^n$ model?
• Model Checking đang kiểm tra điều kiện nào?
• Modus Ponens dùng hai premise nào?
• De Morgan đổi AND và OR thế nào?
• Clause và CNF là gì?
• Vì sao Resolution thêm $\neg\alpha$ khi muốn chứng minh $KB \models \alpha$?
• Empty clause có ý nghĩa gì?
• $\forall x\exists y$ khác $\exists y\forall x$ ở đâu?
• Khi nào FOL gọn hơn Propositional Logic?

Nếu còn vướng từ 3 câu trở lên, nên quay lại đúng bài tương ứng thay vì học tiếp bằng cách ghi nhớ công thức.

Kết thúc module Knowledge

Nếu Search trả lời câu hỏi “đi như thế nào để tới goal?”, Knowledge trả lời câu hỏi “từ những gì đã biết, điều gì bắt buộc phải đúng?”.

Module tiếp theo chuyển sang Uncertainty - Bất định. Khi đó, agent không còn được giả sử mọi sentence đều chắc chắn True hoặc False, mà phải làm việc với mức độ tin cậy và xác suất.

Bản tiếng Anh đang soạn.