Bài giảng Trí tuệ nhân tạo - Chương 8: Biểu diễn tri thức

Trí Tuệ Nhân Tạo

Nguyễn Nhật Quang

[email protected]

Viện Công nghệ Thông tin và Truyền thông

Trường Đại học Bách Khoa Hà Nội

Năm học 2009-2010

Nội dung môn học:

Giới thiệu về Trí tuệ nhân tạo

Tác tử

Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc

Logic và suy diễn

Biểu diễn tri thức

Luật sản xuất

Khung

Mạng ngữ nghĩa

Ontology

Suy diễn với tri thức không chắc chắn

Học máy

Lập kế hoặch

Trí Tuệ Nhân Tạo

2

Dữ liệu, Thông tin, Tri thức (1)

Dữ liệu (data) thường được định nghĩa là các sự kiện

(facts) ho

ặ

c các ký hi

ệ

u (symbols)

Thông tin (information) thường được định nghĩa là dữ

li

ệ

u

đ

ã

đượ

c x

ử

lý ho

ặ

c chuy

ể

n

đổ

i thành nh

ữ

ng d

ạ

ng

hoặc cấu trúc phù hợp cho việc sử dụng của con người

Thông tin có

đượ

c sau (ch

ứ

không xu

ấ

t hi

ệ

n tr

ướ

c) d

ữ

liệu

Tri thứ

c (knowledge)

thườ

ng

đượ

c

đị

nh nghĩa là s

ự

hiểu biết (nhận thức) về thông tin

Trí Tuệ Nhân Tạo

3

Dữ liệu, Thông tin, Tri thức (2)

Knowledge on knowledge

(e.g., how/when to apply)

Knowledge-

based

Meta-

Understanding of a

domain. Can be applied to

solve problems

systems

Knowledge

Information

Data

Lower volume. Higher

value. With context and

associated meanings

Management

information

systems

Databases,

transaction

systems

Large volume. Low

value. Usually no

meaning/ context

(Adapted from “Knowledge Engineering course (CM3016), by K. Hui 2008-2009”)

Trí Tuệ Nhân Tạo

4

Dữ liệu, Thông tin, Tri thức (3)

Dữ liệu

Nhi

ệ

t

độ

ngoài tr

ờ

i là 5

độ

C

Thông tin

Ngoài tr

ờ

i th

ờ

i ti

ế

t l

ạ

nh

Tri thức

N

ế

u ngoài tr

ờ

i th

ờ

i ti

ế

t l

ạ

nh thì b

ạ

n nên m

ặ

c áo choàng

ấ

m (khi

đ

i

ra ngoài)

→Giá trị (sử dụng) của dữ liệu tăng lên khi nó được

“chuyển đổi” thành tri thức

→Sử dụng tri thức sẽ cho phép đưa ra các quyết định phù

hợp và hiệu quả

Trí Tuệ Nhân Tạo

5

Biểu diễn tri thức (1)

Biểu diễn tri thức (Knowlegde representation) là một lĩnh

vực nghiên cứu quan trọng của Trí tuệ nhân tạo

Nhằm phát triển các phương pháp, cách thức biểu diễn tri thức và

các công cụ hỗ trợ việc biểu diễn tri thức

Tồn tại nhiều phương pháp biểu diễn tri thức

Luật sản xuất (Production rules)

Khung (Frames)

Mạng ngữ nghĩa (Semantic networks)

Ontology

Các mô hình xác suất

…

Trí Tuệ Nhân Tạo

6

Biểu diễn tri thức (2)

Tính hoàn chỉnh (Completeness)

Ph

ươ

ng pháp bi

ể

u di

ễ

n có h

ỗ

tr

ợ

vi

ệ

c thu th

ậ

p và th

ể

hi

ệ

n m

ọ

i

khía cạnh của tri thức (của một lĩnh vực cụ thể)?

Tính ngắn gọn (Conciseness)

Phương pháp biểu diễn có cho phép việc thu thập tri thức một

cách hiệu quả?

Phương pháp biểu diễn có cho phép việc lưu trữ và truy nhập dễ

dàng tri thức không?

Tính hiệu quả về tính toán (Computational efficiency)

Tính rõ ràng, dễ hiểu (Transparency)

Phương pháp biểu diễn có cho phép diễn giải (để người dùng

hi

ể

u) v

ề

các ho

ạ

t

độ

ng và các k

ế

t lu

ậ

n c

ủ

a h

ệ

th

ố

ng?

Trí Tuệ Nhân Tạo

7

Biểu diễn tri thức bằng luật (1)

Biểu diễn tri thức bằng các luật (rules) là cách biểu diễn phổ

biến nhất trong các h

ệ

cơ sở tri thức

Một luật chứa đựng (biểu diễn) tri thức về việc giải quyết một vấn đề nào

đó

Các luật được tạo nên khá dễ dàng, và dễ hiểu

Một luật được biểu diễn ở dạng:

IF A₁AND A₂AND … AND A_nTHEN B

A_i

Là các điều kiện (conditions, antecedents, premises)

B

Là kết luận (conclusion, consequence, action)

Trí Tuệ Nhân Tạo

8

Biểu diễn tri thức bằng luật (2)

Mệnh đề điều kiện của một luật

Không c

ầ

n s

ử

d

ụ

ng toán t

ử

logic OR

Một luật với toán tử logic OR trong mệnh đề điều kiện, thì sẽ

được chuyển thành một tập các luật tương ứng không chứa OR

Ví dụ: Luật (IF A₁∨A₂THEN B) được chuyển thành 2 luật (IF

A₁THEN B) và (IF A₂THEN B)

M

ệ

nh

đề

k

ế

t lu

ậ

n c

ủ

a m

ộ

t lu

ậ

t

Không cần sử dụng toán tử logic AND

Một luật với toán tử logic AND trong mệnh đề kết luận, thì sẽ

được chuyển thành một tập các luật tương ứng không chứa AND

Ví dụ: Luật (IF … THEN B₁∧B₂) được chuyển thành 2 luật (IF

… THEN B₁) and (IF … THEN B₂)

Không cho phép sử dụng toán tử OR!

Trí Tuệ Nhân Tạo

9

Các kiểu luật

Các kiểu luật khác nhau để biểu diễn các kiểu tri thức

khác nhau

Quan hệ liên kết

IF addressAt(x, Hospital) THEN heathIs(x, Bad)

Quan hệ nguyên nhân (kết quả)

IF diseaseType(x, Infection) THEN tempIs(x,

High)

Tình huống và hành động (gợi ý)

IF diseaseType(x, Infection) THEN

takeMedicine(x, Antibiotic)

Quan hệ logic

IF tempGreater(x, 37) THEN isFever(x)

Trí Tuệ Nhân Tạo

10

Đồ thị AND/OR (1)

IF (Shape=long) AND (Color=(green OR yellow)) THEN (Fruit=banana)

IF (Shape=(round OR oblong)) AND (Diam > 4) THEN (Fruitclass=vine)

IF (Fruitclass=vine) AND (Color=green) THEN (Fruit=watermelon)

Shape=long

Shape=round

Shape=oblong

Diam > 4

Fruit = banana

AND

OR

Fruitclass = vine

Color=green

Color=yellow

Fruit = watermelon

Trí Tuệ Nhân Tạo

11

Đồ thị AND/OR (2)

Luật IF (Shape=long) AND (Color=(green OR yellow))

THEN (Fruit=banana)

đượ

c t

ạ

o nên b

ở

i các lu

ậ

t:

IF (Shape=long) AND (Color=green) THEN (Fruit=banana)

IF (Shape=long) AND (Color=yellow) THEN (Fruit=banana)

Luật IF (Shape=(round OR oblong)) AND (Diam > 4)

THEN (Fruitclass=vine) được tạo nên bởi các luật:

IF (Shape=round) AND (Diam > 4) THEN (Fruitclass=vine)

IF (Shape=oblong)

AND

(Diam > 4) THEN (Fruitclass=vine)

Trí Tuệ Nhân Tạo

12

Các vấn đề với biểu diễn luật

Các luật có chứa các vòng lặp

IF A THEN A

{IF A THEN B, IF B THEN C, IF C THEN A}

Các luật có chứa mâu thuẫn

{IF A THEN B, IF B THEN C, IF A AND D THEN ¬C}

Các kết luận không thể suy ra được (từ các luật hiện có)

Khó khăn trong việc thay đổi (cập nhật) cơ sở tri thức

Cơ sở tri thức cũ: {IF A₁THEN B₁, IF A₂THEN B₂, …, IF A_n

THEN B_n}

Cần bổ sung thêm điều kiện C vào tất cả các luật

Cơ sở tri thức mới: {IF A₁AND C THEN B₁, IF A₂AND C THEN

B₂, …, IF A_nAND C THEN B_n}

Trí Tuệ Nhân Tạo

13

Sử dụng các luật trong suy diễn

So khớp mẫu (Pattern matching)

Để

ki

ể

m tra m

ộ

t lu

ậ

t có th

ể đượ

c s

ử

d

ụ

ng (áp d

ụ

ng) hay không

Ví dụ: Nếu cơ sở tri thức chứa đựng tập các luật {IF A₁THEN

B₁, IF A₁AND A₂THEN B₂, IF A₂AND A₃THEN B₃} và các

s

ự

ki

ệ

n (

đượ

c l

ư

u trong b

ộ

nh

ớ

làm vi

ệ

c) bao g

ồ

m

A₁

và

A₂

, thì 2

luật đầu tiên có thể được sử dụng

Chuỗi suy diễn (chuỗi áp dụng các luật)

Xác định trật tự áp dụng các luật trong quá trình suy diễn

Với một tập các luật và một tập các sự kiện (các giả thiết), các

lu

ậ

t nào nên

đượ

c s

ử

d

ụ

ng, và theo tr

ậ

t t

ự

nào,

để đạ

t t

ớ

i (suy ra)

một kết luật cần chứng minh?

2 chiến lược suy diễn: tiến (forward) vs. lùi (backward)

2 chiến lược suy diễn này đã được trình bày trong bài trước!

Trí Tuệ Nhân Tạo

14

Giải quyết xung đột

Một xung đột (conflict) xảy ra khi có nhiều hơn một luật

có th

ể

áp d

ụ

ng

đượ

c (phù h

ợ

p v

ớ

i các s

ự

ki

ệ

n trong b

ộ

nhớ làm việc)

Lưu ý, một xung đột không phải là một mâu thuẫn của tập luật

Trong trường hợp xảy ra xung đột, cần một chiến lược

gi

ả

i quy

ế

t xung

độ

t (conflict resolution strategy - CRS)

để

quyết định luật nào được (ưu tiên) áp dụng

Sự lựa chọn thích hợp một chiến lược giải quyết xung

đột có thể mang lại những cải thiện đáng kể đối với quá

trình suy diễn của hệ thống

Trí Tuệ Nhân Tạo

15

Chiến lược giải quyết xung đột

Áp dụng luật xuất hiện đầu tiên (theo thứ tự) trong cơ sở

tri th

ứ

c

Không áp dụng các luật sinh ra các kết quả (sự kiện) đã

có trong bộ nhớ làm việc

Áp dụng luật cụ thể nhất (luật có nhiều điều kiện nhất)

Áp dụng các luật phù hợp với các sự kiện được đưa vào

trong bộ nhớ làm việc gần thời điểm hiện tại nhất

Không áp dụng lại một luật, nếu nó vẫn sinh ra cùng một

tập các sự kiện (giống như lần áp dụng trước của nó)

Áp dụng luật có độ tin cậy (chắc chắn) cao nhất

…

Kết hợp của các chiến lược trên

Trí Tuệ Nhân Tạo

16

Hệ thống suy diễn dựa trên luật (1)

Kiến trúc điển hình của một hệ thống suy diễn dựa trên luật (Rule-

based system – RBS)

Dữ liệu quan sát được

Working

memory

Lựa chọn

Cập nhật

Rule

memory

Interpreter

Áp dụng

Kết quả

(http://www.cwa.mdx.ac.uk/bis2040/johnlect.html)

Trí Tuệ Nhân Tạo

17

Hệ thống suy diễn dựa trên luật (2)

Bộ nhớ làm việc (Working memory)

L

ư

u gi

ữ

các s

ự

ki

ệ

n (các gi

ả

thi

ế

t

đ

úng,

đ

ã

đượ

c ch

ứ

ng minh)

Các sự kiện này sẽ quyết định những luật nào được áp dụng (bởi

thành phần Interpreter)

Bộ nhớ các luật (Rule memory)

Chính là cơ sở tri thức của hệ thống

Lưu giữ các luật có thể áp dụng

Bộ diễn dịch (Interpreter)

Hệ thống bắt đầu bằng việc đưa một sự kiện (dữ liệu) phù hợp

vào bộ nhớ làm việc

Khi sự kiện (dữ liệu) trong bộ nhớ làm việc phù hợp với các điều

kiện của một luật trong bộ nhớ các luật, thì luật đó sẽ được áp

dụng

Trí Tuệ Nhân Tạo

18

RBS – Ưu điểm (1)

Cách biểu diễn (diễn đạt) phù hợp

Rất gần với cách diễn đạt trong ngôn ngữ tự nhiên

Rất dễ dàng để diễn đạt các tri thức bởi các luật

Dễ hiểu

Các luật dạng IF-THEN rất dễ hiểu (có lẽ là dễ hiểu nhất) đối với

người sử dụng

Trong một lĩnh vực (bài toán) cụ thể, cách biểu diễn bằng luật

giúp các chuyên gia trong lĩnh vực này có thể đánh giá và cải tiến

các luật

Trí Tuệ Nhân Tạo

19

RBS – Ưu điểm (2)

Một cách biểu diễn tri thức theo kiểu khai báo

(declarative)

Kỹ sư tri thức thu thập các tri thức (ở dạng các luật IF-THEN) về

một lĩnh vực cụ thể, và đưa chúng vào trong một cơ sở các luật

(rule base)

Kỹ sư tri thức (có thể) không cần phải quan tâm đến khi nào, làm

thế nào, và theo trật tự nào mà các luật được sử dụng – Hệ thống

sẽ tự động đảm nhận các nhiệm vụ này

Dễ dàng mở rộng cơ sở tri thức

Chỉ việc bổ sung thêm các luật mới (các tri thức mới) vào cuối

của cơ sở các luật

Trí Tuệ Nhân Tạo

20

Bài giảng Trí tuệ nhân tạo - Chương 8: Biểu diễn tri thức - Nguyễn Nhật Quang