Knowledge Representation - Biểu diễn tri thức

Ở phần Search, agent đã có state, action và goal rồi tìm một chuỗi hành động phù hợp. Sang phần Knowledge, câu hỏi đổi thành:

Máy đang biết những gì, biểu diễn chúng ra sao, và làm thế nào để các câu tri thức có nghĩa rõ ràng đối với máy?

Ví dụ, hệ thống hỗ trợ sinh viên biết rằng:

hôm nay có tiết AI;
chưa có thông báo nghỉ;
nếu có tiết AI và không có thông báo nghỉ thì sinh viên cần tới trường.

Để máy xử lý được các thông tin này, ta cần biến câu tiếng Việt thành một dạng hình thức có semantics rõ ràng.

Mục tiêu

Sau bài này, bạn cần:

hiểu knowledge-based agent và Knowledge Base - KB;
phân biệt sentence, proposition, symbol và model;
đọc và viết NOT, AND, OR, implication và biconditional;
chuyển một số câu tiếng Việt đơn giản sang logic mệnh đề;
hiểu vì sao cách chọn representation ảnh hưởng trực tiếp đến khả năng suy luận.

Từ Search sang Knowledge

Search hỏi:

Từ state hiện tại, đi bằng action nào để tới goal?

Knowledge hỏi:

Từ những điều đã biết, kết luận nào bắt buộc phải đúng?

Có thể nhìn hai chủ đề như sau:

Điểm chung là máy vẫn cần một representation - cách biểu diễn tốt. Nếu biểu diễn sai hoặc thiếu thông tin, thuật toán phía sau khó có thể sửa được.

Knowledge-Based Agent

Một knowledge-based agent là agent lưu tri thức dưới một dạng có cấu trúc và sử dụng tri thức đó để suy luận.

Một vòng làm việc đơn giản:

Ví dụ hệ thống hỗ trợ sinh viên:

Fact: HomNayLaThuHai;
Fact: CoTietAI;
Rule: nếu hôm nay là thứ Hai và có tiết AI thì cần tới phòng lab;
Inference: suy ra CanToiPhongLab.

Hệ thống không “hiểu” câu như con người. Ta phải chuyển thông tin thành một ngôn ngữ hình thức để máy xử lý chính xác.

Sentence - câu tri thức

Trong knowledge representation, một sentence là một khẳng định về thế giới được viết bằng ngôn ngữ biểu diễn tri thức.

Ví dụ:

P: Hôm nay có tiết AI.
Q: Tôi cần tới trường.

P và Q không phải biến số theo nghĩa số học. Chúng đại diện cho các proposition - mệnh đề có giá trị True hoặc False.

Propositional Logic - Logic mệnh đề

Proposition là gì?

Một proposition là một phát biểu có thể xác định là đúng hoặc sai.

Ví dụ hợp lệ:

P: Hôm nay là thứ Hai.
Q: Phòng lab đang mở.
R: Minh đã nộp bài.

Các câu sau không phải proposition theo nghĩa đơn giản này:

"Bạn học lớp nào?"      -> câu hỏi
"Hãy nộp bài ngay."     -> mệnh lệnh
"x > 5"                 -> chưa biết True/False nếu chưa biết x

Propositional Symbol

Ta thường dùng các symbol như $P$ , $Q$ , $R$ để đại diện cho proposition.

Ví dụ:

P,\qquad Q

trong đó $P$ là “Sinh viên đã đăng ký môn AI” và $Q$ là “Sinh viên được vào lớp AI”.

Sau đó ta kết hợp các symbol bằng logical connectives - phép nối logic.

Các phép nối logic quan trọng

NOT - phủ định

Ký hiệu:

\neg P

Nếu:

P: Hôm nay có tiết học.

thì:

¬P: Hôm nay không có tiết học.

Bảng chân trị:

$P$	$\neg P$
False	True
True	False

AND - và

Ký hiệu:

P \land Q

Chỉ đúng khi cả hai cùng đúng.

Ví dụ:

P: Sinh viên có thẻ.
Q: Sinh viên đã đăng ký phòng lab.
P ∧ Q: Sinh viên có thẻ và đã đăng ký phòng lab.

$P$	$Q$	$P \land Q$
False	False	False
False	True	False
True	False	False
True	True	True

OR - hoặc

Ký hiệu:

P \lor Q

Trong logic mệnh đề chuẩn, đây là inclusive OR: chỉ cần ít nhất một vế đúng. Nếu cả hai cùng đúng thì toàn biểu thức vẫn đúng.

Ví dụ:

P: Nộp bài qua LMS.
Q: Nộp bài qua email.

Nếu quy định nói “chấp nhận LMS hoặc email”, thì sinh viên nộp bằng cả hai cách vẫn thỏa điều kiện nếu đây là inclusive OR.

$P$	$Q$	$P \lor Q$
False	False	False
False	True	True
True	False	True
True	True	True

Inclusive OR và XOR

Câu đời thường “chọn một trong hai” đôi khi lại có nghĩa chỉ được đúng một lựa chọn. Đó là Exclusive OR - XOR.

Có thể viết XOR bằng:

(P \lor Q) \land \neg(P \land Q)

Nghĩa là:

ít nhất một trong hai đúng;
nhưng không được cả hai cùng đúng.

Implication - nếu… thì…

Ký hiệu:

P \to Q

Đọc là:

Nếu $P$ thì $Q$ .

Ví dụ:

P: Sinh viên đạt ít nhất 80% điểm chuyên cần.
Q: Sinh viên đủ điều kiện dự thi.

P \to Q

Trong đó:

$P$ là antecedent - tiền đề;
$Q$ là consequent - hệ quả.

Bảng chân trị:

$P$	$Q$	$P \to Q$
False	False	True
False	True	True
True	False	False
True	True	True

Dòng thường gây khó hiểu nhất là:

P = False
Q = False hoặc True
=> P -> Q vẫn True

Vì sao antecedent False thì implication True?

Câu:

Nếu tôi đạt ít nhất 80% chuyên cần thì tôi đủ điều kiện dự thi.

Chỉ bị chứng minh là sai khi:

Tôi đạt >= 80% chuyên cần
nhưng
Tôi không đủ điều kiện dự thi

Nếu tôi chỉ đạt 60% chuyên cần, câu trên không hứa điều gì về trường hợp của tôi. Tôi có thể được dự thi vì một quy định khác, hoặc không được dự thi. Không trường hợp nào làm sai lời khẳng định ban đầu.

Vì vậy implication chỉ False trong trường hợp:

P=True,\quad Q=False

Một cách rất hữu ích để nhớ là:

P \to Q \equiv \neg P \lor Q

Sai lầm phổ biến: đảo chiều implication

Từ:

P \to Q

không được tự động kết luận:

Q \to P

Ví dụ:

Nếu trời mưa thì sân ướt.
Sân đang ướt.

Không thể chắc chắn kết luận trời mưa, vì sân có thể vừa được tưới nước.

Đây là lỗi suy luận rất phổ biến: affirming the consequent.

Biconditional - khi và chỉ khi

Ký hiệu:

P \leftrightarrow Q

Đọc là:

$P$ khi và chỉ khi $Q$ .

Nó tương đương với hai implication:

(P \to Q) \land (Q \to P)

Bảng chân trị:

$P$	$Q$	$P \leftrightarrow Q$
False	False	True
False	True	False
True	False	False
True	True	True

Biconditional đúng khi hai vế có cùng giá trị chân trị.

Bảng tóm tắt phép nối

Tên	Ký hiệu	Ý nghĩa ngắn
Not	$\neg P$	đảo True/False
And	$P \land Q$	cả hai phải đúng
Or	$P \lor Q$	ít nhất một đúng
Implication	$P \to Q$	nếu P thì Q
Biconditional	$P \leftrightarrow Q$	P khi và chỉ khi Q

Từ câu tiếng Việt sang logic

Đây là phần rất quan trọng vì bài toán thực tế thường đến bằng ngôn ngữ tự nhiên.

Giả sử:

P: Có tiết AI.
Q: Có thông báo nghỉ.
R: Tôi tới trường.

“Có tiết AI và không có thông báo nghỉ”

P \land \neg Q

“Nếu có tiết AI và không có thông báo nghỉ thì tôi tới trường”

(P \land \neg Q) \to R

“Tôi tới trường khi và chỉ khi có tiết AI”

R \leftrightarrow P

Cẩn thận với ngoặc. Hai biểu thức sau không giống nhau:

P \to (Q \land R)

và

(P \to Q) \land R

Trong biểu thức đầu, $R$ chỉ là một phần của consequent. Trong biểu thức sau, $R$ được khẳng định độc lập là True.

Model - một thế giới có thể

Một model là một phép gán giá trị True/False cho mọi propositional symbol đang xét.

Ví dụ có hai symbol:

P: Hôm nay có tiết AI.
Q: Trời mưa.

Một model có thể là:

{
    "P": True,
    "Q": False,
}

Nó mô tả một thế giới trong đó:

có tiết AI;
trời không mưa.

Với $n$ symbol độc lập, có tối đa:

2^n

model có thể.

Ví dụ:

Số symbol	Số model tối đa
1	2
2	4
3	8
10	1,024
20	1,048,576
30	1,073,741,824

Đây là dấu hiệu đầu tiên cho thấy cách thử mọi model sẽ nhanh chóng trở nên đắt.

Knowledge Base - KB

Knowledge Base, thường viết là KB, là tập các sentence mà agent biết hoặc giả định là đúng.

Ví dụ:

P: Có tiết AI.
Q: Có thông báo nghỉ.
R: Tôi tới trường.

Knowledge Base:

KB = P \land \neg Q \land ((P \land \neg Q) \to R)

Đọc bằng lời:

Có tiết AI.
Không có thông báo nghỉ.
Nếu có tiết AI và không có thông báo nghỉ thì tôi tới trường.

Từ KB này, ta muốn hỏi:

Query: R có bắt buộc đúng không?

Knowledge Engineering - biểu diễn tri thức mới là phần khó

Knowledge Engineering là quá trình quyết định:

cần symbol nào;
mỗi symbol có nghĩa gì;
rule nào mô tả đúng bài toán;
constraint nào phải được thêm vào;
thông tin nào có thể bỏ qua.

Một inference engine rất tốt vẫn cho kết luận sai nếu knowledge được mã hóa sai.

Ví dụ: xếp sinh viên vào phòng lab

Giả sử có hai sinh viên An, Binh và hai ca Ca1, Ca2.

Nếu dùng Propositional Logic, ta có thể tạo:

AnCa1
AnCa2
BinhCa1
BinhCa2

Muốn nói “An phải thuộc ít nhất một ca”:

AnCa1 \lor AnCa2

Muốn nói “An không được thuộc cả hai ca”:

\neg(AnCa1 \land AnCa2)

Với vài sinh viên thì ổn. Nhưng với 500 sinh viên và 20 ca, số symbol tăng rất nhanh.

Đây là một lý do ta sẽ cần First-Order Logic ở cuối bài.

Một ví dụ Knowledge Base gần với sinh viên

Giả sử xây hệ thống kiểm tra điều kiện làm đồ án.

Các symbol:

P: Đã qua môn Lập trình Python.
D: Đã qua môn Cấu trúc dữ liệu.
A: Được đăng ký đồ án AI.

Rule:

(P \land D) \to A

Facts:

P

D

KB:

P \land D \land ((P \land D) \to A)

Ta có thể dùng Modus Ponens để suy ra:

A

Nhưng nếu chỉ biết $A$ thì sao?

Không được kết luận ngay:

P \land D

vì có thể nhà trường cho phép ngoại lệ, hoặc có một rule khác cũng dẫn tới $A$ .

Đây là lý do phải đọc implication đúng chiều.

Consistency - Knowledge Base có tự mâu thuẫn không?

Một KB không nhất quán có thể chứa:

P

và:

\neg P

Ví dụ dữ liệu hệ thống ghi đồng thời:

"An đã nộp bài"
"An chưa nộp bài"

Trong classical logic, inconsistency là vấn đề nghiêm trọng. Trước khi suy luận, hệ thống thực tế thường cần:

kiểm tra nguồn dữ liệu;
ưu tiên timestamp mới hơn;
xác định độ tin cậy nguồn;
hoặc dùng một hệ logic khác phù hợp với dữ liệu không chắc chắn.

Chủ đề Uncertainty ở bài sau sẽ xử lý trường hợp tri thức không hoàn toàn chắc chắn bằng xác suất. Logic trong bài này chủ yếu giả sử sentence được xem là True hoặc False một cách rõ ràng.

Chốt lại

Một hệ AI dựa trên tri thức cần hai thứ trước khi nói đến thuật toán suy luận:

Representation - ta chọn symbol, sentence và rule nào để mô tả bài toán.
Semantics - mỗi biểu thức phải có nghĩa rõ ràng để xác định khi nào nó True hoặc False.

Trong bài tiếp theo, ta dùng các sentence đã biểu diễn để trả lời câu hỏi quan trọng hơn:

Knowledge Base có bắt buộc dẫn tới một kết luận nào đó hay không?

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

Knowledge Representation - Biểu diễn tri thức

Mục tiêu

Từ Search sang Knowledge

Knowledge-Based Agent

Sentence - câu tri thức

Propositional Logic - Logic mệnh đề

Proposition là gì?

Propositional Symbol

Các phép nối logic quan trọng

NOT - phủ định

AND - và

OR - hoặc

Inclusive OR và XOR

Implication - nếu… thì…

Vì sao antecedent False thì implication True?

Sai lầm phổ biến: đảo chiều implication

Biconditional - khi và chỉ khi

Bảng tóm tắt phép nối

Từ câu tiếng Việt sang logic

“Có tiết AI và không có thông báo nghỉ”

“Nếu có tiết AI và không có thông báo nghỉ thì tôi tới trường”

“Tôi tới trường khi và chỉ khi có tiết AI”

Model - một thế giới có thể

Knowledge Base - KB

Knowledge Engineering - biểu diễn tri thức mới là phần khó

Ví dụ: xếp sinh viên vào phòng lab

Một ví dụ Knowledge Base gần với sinh viên

Nhưng nếu chỉ biết AAA thì sao?

Consistency - Knowledge Base có tự mâu thuẫn không?

Chốt lại

Nhưng nếu chỉ biết $A$ thì sao?