Chuyển bài toán chứng minh logic vềbài toán SAT
Ph há hứ ihbằ hả hứ Phương phápchứng minh bằng phảnchứng
Việcchứng minh sựmâu thuẫncủa: (KB ∧¬α)
Tươngđươngviệcchứngminhsựbaohàm: KB╞α Tươngđươngviệcchứngminh sựbaohàm: KB╞ α
Luật suy diễnhợpgiải (Resolution rule)
NếucácbiểuthứctrongtậpKBvàbiểuthức(cầnchứngminh)α NếucácbiểuthứctrongtậpKBvàbiểuthức(cầnchứngminh) α
đềuởdạng CNF, thì áp dụng luật suy diễnhợpgiảisẽxácđịnh
tính (không) thỏamãnđượccủa (KB ∧¬α
559 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 3604 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Giáo trình Trí tuệ nhân tạo Bách Khoa Hà Nội, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
một tập mờ A của miền giá trị X được định nghĩa
(được xác định) bởi hàm µA(x)
µA(x) được gọi là hàm phụ thuộc (membership function) của tập
mờ A
A = {µA(x1)/x1, µA(x2)/x2, ..., µA(xn)/xn}
µA(x) : X Æ {0, 1}, với: µA(x) = 1, nếu x hoàn toàn thuộc trong A
µA(x) = 0, nếu x không thuộc trong A
0 < µA(x) < 1, nếu x thuộc một phần trong A
Đối ới ỗi hầ tử ( iá t ị) ủ iề iá t ị X hà h th ộ v m p n g r x c a m n g r , m p ụ u c µA(x)
chỉ ra mức độ tương ứng mà x là một thành phần của A
Mức độ này (là một giá trị trong khoảng từ 0 đến 1) biểu diễn mức
độ phụ thuộc của phần tử x trong tập A
23Trí tuệ nhân tạo
Biểu diễn tập chính xác và tập mờ
Tall Men
Muc do
phu thuoc
Thap Trung binh Short Cao
1,0
0,8
Tap chinh xac
0,2
0,4
0,6
Những
người
150 210170 180 190 200160
Chieu cao
Muc do
phu thuoc
0,0
Tap mo
đàn
ông
thấp,
1,0
0,6
0,8
Thap Trung binh Cao
trung
bình,
cao
150 210180 190 200
0,0
0,2
0,4
160 170
24Trí tuệ nhân tạo
(Negnevitsky, Pearson Education, 2002)
Phần bù (Complement)
Tập chính xác (crisp set): Phần tử nào không thuộc vào
tập hợp?
Tập mờ (fuzzy set): Mức độ một phần tử không thuộc
à tậ h ?v o p ợp
Nếu A là một tập mờ, thì phần bù của A (ký hiệu là ¬A)
được định nghĩa như sau:
µ¬A(x) = 1 - µA(x); với mọi phần tử x
25Trí tuệ nhân tạo
Tập bao hàm (Container)
Tập chính xác: Những tập nào là
tập con (subset) của các tập khác
Trong lý thuyết tập mờ, nếu tập A
là một tập con của B, thì: B
µA(x) ≤ µB(x), ∀x
Mỗi thành phần sẽ có mức độ phụ
thuộc (membership value) vào tập A
A
nhỏ hơn hoặc bằngmức độ phụ vào tập
B
Ví dụ: A là tập “Những người đàn ông
rất cao”, B là tập “Những người đàn
ông cao”
26Trí tuệ nhân tạo
Giao (Intersection)
Tập chính xác: Những phần tử nào thuộc vào cả 2 tập?
Tập mờ: Mức độ mỗi phần tử thuộc vào cả 2 tập?
Phần giao mờ (fuzzy intersection) được xác định bởi giá
trị phụ thuộc thấp nhất đối với 2 tập mờ
Gi ủ 2 tậ ờ ũ là ột tậ ờ đ đị h hĩ ao c a p m c ng m p m , ược n ng a
như sau:
µA∩B(x) = min{µA(x), µB(x)}, ∀x
27Trí tuệ nhân tạo
Hợp (Union)
Tập chính xác: Những phần tử nào thuộc vào một trong
hai tập?
Tập mờ: Mức độ mỗi phần tử thuộc vào một trong hai
tập?
Phần hợp mờ (fuzzy union) được xác định bởi giá trị
phụ thuộc cao nhất đối với 2 tập mờ
Hợp của 2 tập mờ cũng là một tập mờ, được định nghĩa
như sau:
µA∪B(x) = max{µA(x), µB(x)}, ∀x
28Trí tuệ nhân tạo
Các thao tác trên tập mờ
1
μ ( x )
A
1
B
A
μ ( x )
0 x
1
Not A
0 x
1
B
A
Complement
0 x Containment
0 x
μ(x) μ(x)
0 x
1
A B
0 x
1
A B
0 x
1
0 x
1
A B∪
A B∩
29Trí tuệ nhân tạo
Intersection Union (Bogdan L. Vrusias, CS 289, 2006)
Các thuộc tính của tập mờ
Sự tương đương của 2 tập mờ
Sự bao hàm giữa 2 tập mờ
Kích thước của một tập mờ
Một tập mờ rỗng
t ( l h t) α-cu a p a-cu
30Trí tuệ nhân tạo
Sự tương đương của 2 tập mờ
Một tập mờ A được gọi là tương đương (equal) với tập
mờ B nếu và chỉ nếu:,
µA(x) = µB(x), ∀x
Ví dụ
A = {0,3/x, 0,5/y, 1/z}
B = {0 3/x 0 5/y 1/z} , , , ,
A và B là 2 tập mờ tương đương
31Trí tuệ nhân tạo
Sự bao hàm giữa 2 tập hợp
Một tập mờ A được gọi là bao hàm (includes) một tập
mờ B nếu và chỉ nếu:,
µA(x) ≥ µB(x), ∀x
Ví dụ
A = {0,37/x, 0,72/y, 1/z}
B = {0 3/x 0 5/y 1/z} , , , ,
A bao hàm B
32Trí tuệ nhân tạo
Kích thước của một tập mờ
Kích thước (cardinality) của một tập chính xác là số phần
tử của tập
Kích thước của một tập mờ là tổng các giá trị mức độ
h th ộ ủ á thà h hầp ụ u c c a c c n p n
cardA = µA(x1) + µA(x2) + ... + µA(xn) = Σi=1..n µA(xi)
Ví dụ
A = {0,3/x, 0,5/y, 1/z}
cardA = 0,3 + 0,5 + 1 = 1,8
33Trí tuệ nhân tạo
Tập mờ rỗng
Một tập mờ A được gọi là rỗng (empty), nếu:
( ) 0 ∀µA x = , x
Ví dụ:
A = {0/x, 0/y, 0/z}
A là một tập mờ rỗng
34Trí tuệ nhân tạo
Alpha-cut
Một α-cắt (một tập mức α) của một tập mờ A là một tập
chính xác (crisp set) A sao cho: α
Aα = {x∈X: µA(x) ≥ α}
Ví dụ:
A = {0,3/x, 0.5/y, 1/z}
A0 5 = {y, z},
A0,2 = {x, y, z}
A1 = {z}
35Trí tuệ nhân tạo
Các khái niệm với tập mờ
Một tập mờ A được gọi là tập mờ chuẩn (normal), nếu tồn tại
ít nhất một phần tử x sao cho µ (x) =1 A
Độ cao (height) của một tập mờ A là giá trị phụ thuộc lớn
nhất của các thành phần
heightA = maxx{µA(x)}
Tập hỗ trợ (support) của A là một tập chính xác, chứa các
hầ từ ó ứ độ h th ộ ( à A) >0p n c m c p ụ u c v o
support(A) = {x∈X: µA(x) > 0}
Tập cơ sở (core) của A là một tập chính xác chứa các phần ,
từ có mức độ phụ thuộc (vào A) =1
core(A) = {x∈X: µA(x)=1}
36Trí tuệ nhân tạo
Các phép toán trên tập mờ
Nhân với một giá trị số học
aA {a ( ) ∀ X} = μA x , x∈
Ví dụ
A = {0,5/x, 0,3/y, 0,2/z, 1/w}
a = 0,5
aA = {0,25/x, 0,15/y, 0,1/z, 0,5/w}
Phé tí h ũ (lũ thừ ) p n m y a
Aa = {μA(x)a, ∀x∈X}
Ví dụ
A = {0,5/x, 0,3/y, 0,2/z, 1/w}
a = 2
Aa = {0 25/x 0 09/y 0 04/z 1/w} , , , , . ,
37Trí tuệ nhân tạo
Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang
quangnn-fit@mail.hut.edu.vn
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
Suy diễn với tri thức không chắc chắn
Học máy
Giới thiệu về học máy
Phân lớp Naïve Bayes
Học dựa trên các láng giềng gần nhất
Lập kế hoặch
Trí Tuệ Nhân Tạo
2
Giới thiệu về Học máy
Các định nghĩa về Học máy (Machine learning)
→ Một quá trình nhờ đó một hệ thống cải thiện hiệu suất (hiệu quả hoạt
động) của nó [Simon, 1983]
→ Một quá trình mà một chương trình máy tính cải thiện hiệu suất của nó
trong một công việc thông qua kinh nghiệm [Mitchell, 1997]
→ Việc lập trình các máy tính để tối ưu hóa một tiêu chí hiệu suất dựa trên
các dữ liệu ví dụ hoặc kinh nghiệm trong quá khứ [Alpaydin, 2004]
Biể diễ ộ bài á h á u n m t to n ọc m y [Mitchell, 1997]
Học máy = Cải thiện hiệu quả một công việc thông qua kinh nghiệm
• Một công việc (nhiệm vụ) T
• Đối với các tiêu chí đánh giá hiệu suất P
• Thông qua (sử dụng) kinh nghiệm E
Trí Tuệ Nhân Tạo 3
Các ví dụ của bài toán học máy (1)
Bài toán lọc các trang Web theo sở
thích của một người dùng
T: Dự đoán (để lọc) xem những trang
Web nào mà một người dùng cụ thể
thí h đc ọc
P: Tỷ lệ (%) các trang Web được dự
đoán đúng
Interested?
E: Một tập các trang Web mà người
dùng đã chỉ định là thích đọc và một tập
các trang Web mà anh ta đã chỉ định là
không thích đọc
Trí Tuệ Nhân Tạo 4
Các ví dụ của bài toán học máy (2)
Bài toán phân loại các trang Web theo các chủ đề
T Phâ l i á t W b th á hủ đề đã đị h t ớ : n oạ c c rang e eo c c c n rư c
P: Tỷ lệ (%) các trang Web được phân loại chính xác
E: Một tập các trang Web trong đó mỗi trang Web gắn với một ,
chủ đề
Which
cat.?
Trí Tuệ Nhân Tạo 5
Các ví dụ của bài toán học máy (3)
Bài toán nhận dạng chữ
viết tay
T: Nhận dạng và phân loại các
từ trong các ảnh chữ viết tay
P: Tỷ lệ (%) các từ được nhận
dạng và phân loại đúng
E: Một tập các ảnh chữ viết
Which word?
tay, trong đó mỗi ảnh được gắn
với một định danh của một từ
rightdo in waywe the
Trí Tuệ Nhân Tạo 6
Các ví dụ của bài toán học máy (4)
Bài toán robot lái xe tự động
T: Robot (được trang bị các
camera quan sát) lái xe tự động
trên đường cao tốc
P: Khoảng cách trung bình mà
robot có thể lái xe tự động
trước khi xảy ra lỗi (tai nạn)
Which steering
command?
E: Một tập các ví dụ được ghi
lại khi quan sát một người lái xe
trên đường cao tốc trong đó
Go
straight
Move
left
Move
right
Slow
down
Speed
up
,
mỗi ví dụ gồm một chuỗi các
ảnh và các lệnh điều khiển xe
Trí Tuệ Nhân Tạo 7
Quá trình học máy
Tập học
(Training set)
Tập dữ liệu
(Dataset)
Huấn luyện
hệ thống
Tập tối ưu
(Validation set)
Tối ưu hóa
Tập thử nghiệm
các tham số
của hệ thống
(Test set) Thử nghiệm
hệ thống
đã học
Trí Tuệ Nhân Tạo 8
Học có vs. không có giám sát
Học có giám sát (supervised learning)
Mỗi ví dụ học gồm 2 phần: mô tả (biểu diễn) của ví dụ học và ,
nhãn lớp (hoặc giá trị đầu ra mong muốn) của ví dụ học đó
Bài toán học phân lớp (classification problem)
D train = {( )}_ _ _ _ , _ _ _
Bài toán học dự đoán/hồi quy (prediction/regression problem)
D_train = {(, )}
Học không có giám sát (unsupervised learning)
Mỗi ví dụ học chỉ chứa mô tả (biểu diễn) của ví dụ học đó - mà
không có bất kỳ thông tin nào về nhãn lớp hay giá trị đầu ra mong
muốn của ví dụ học đó
Bài toán học phân cụm (Clustering problem)
Tập học D train = {()}_ _ _ _
Trí Tuệ Nhân Tạo 9
Bài toán học máy – Các thành phần chính (1)
Lựa chọn các ví dụ học (training/learning examples)
• Các thông tin hướng dẫn quá trình học (training feedback) được chứa
ngay trong các ví dụ học, hay là được cung cấp gián tiếp (vd: từ môi
trường hoạt động)
• Các ví dụ học theo kiểu có giám sát (supervised) hay không có giám sát
(unsupervised)
• Các ví dụ học phải tương thích với (đại diện cho) các ví dụ sẽ được sử
dụng bởi hệ thống trong tương lai (future test examples)
Xác định hàm mục tiêu (giả thiết, khái niệm) cần học
• F: X → {0,1}
• F: X → {Một tập các nhãn lớp}
• F: X → R+ (miền các giá tri số thực dương)
• …
Trí Tuệ Nhân Tạo 10
Bài toán học máy – Các thành phần chính (2)
Lựa chọn cách biểu diễn cho hàm mục tiêu cần học
• Hàm đa thức (a polynomial function)
• Một tập các luật (a set of rules)
• Một cây quyết định (a decision tree)
• Một mạng nơ-ron nhân tạo (an artificial neural network)
• …
Lựa chọn một giải thuật học máy có thể học (xấp xỉ)
được hàm mục tiêu
• Phương pháp học hồi quy (Regression-based)
• Phương pháp học quy nạp luật (Rule induction)
• Phương pháp học cây quyết định (ID3 hoặc C4.5)
• Phương pháp học lan truyền ngược (Back-propagation)
• …
Trí Tuệ Nhân Tạo 11
Các vấn đề trong Học máy (1)
Giải thuật học máy (Learning algorithm)
ể ấ• Những giải thuật học máy nào có th học (x p xỉ) một hàm
mục tiêu cần học?
Với hữ điề kiệ à ột iải th ật h á đã h• n ng u n n o, m g u ọc m y c ọn
sẽ hội tụ (tiệm cận) hàm mục tiêu cần học?
• Đối với một lĩnh vực bài toán cụ thể và đối với một cách
biểu diễn các ví dụ (đối tượng) cụ thể, giải thuật học máy
nào thực hiện tốt nhất?
Trí Tuệ Nhân Tạo 12
Các vấn đề trong Học máy (2)
Các ví dụ học (Training examples)
• Bao nhiêu ví dụ học là đủ?
• Kích thước của tập học (tập huấn luyện) ảnh hưởng thế
à đối ới độ hí h á ủ hà tiê h đ ?n o v c n x c c a m mục u ọc ược
• Các ví dụ lỗi (nhiễu) và/hoặc các ví dụ thiếu giá trị thuộc
tính (missing value) ảnh hưởng thế nào đối với độ chính -
xác?
Trí Tuệ Nhân Tạo 13
Các vấn đề trong Học máy (3)
Quá trình học (Learning process)
ế ố• Chi n lược t i ưu cho việc lựa chọn thứ tự sử dụng (khai
thác) các ví dụ học?
Cá hiế l l h à là th đổi ứ độ hứ• c c n ược ựa c ọn n y m ay m c p c
tạp của bài toán học máy như thế nào?
• Các tri thức cụ thể của bài toán (ngoài các ví dụ học) có
thể đóng góp thế nào đối với quá trình học?
Trí Tuệ Nhân Tạo 14
Các vấn đề trong Học máy (4)
Khả năng/giới hạn học (Learning capability)
• Hàm mục tiêu nào mà hệ thống cần học?
Biểu diễn hàm mục tiêu: Khả năng biểu diễn (vd: hàm tuyến
tính / hàm phi tuyến) vs. Độ phưc tạp của giải thuật và quá
trình học
• Các giới hạn (trên lý thuyết) đối với khả năng học của các giải thuật
học máy?
Khả ă khái át hó ( li ) ủ hệ thố từ á í d h ?• n ng qu a genera ze c a ng c c v ụ ọc
Để tránh vấn đề “over-fitting” (đạt độ chính xác cao trên tập học,
nhưng đạt độ chính xác thấp trên tập thử nghiệm)
ố ổ ể ễ ấ• Khả năng hệ th ng tự động thay đ i (thích nghi) bi u di n (c u trúc)
bên trong của nó?
Để cải thiện khả năng (của hệ thống đối với việc) biểu diễn và học
hà tiêm mục u
Trí Tuệ Nhân Tạo 15
Vấn đề over-fitting (1)
Một hàm mục tiêu (một giả thiết) học được h sẽ được gọi
là quá khớp/quá phù hợp (over-fit) với một tập học nếu
tồn tại một hàm mục tiêu khác h’ sao cho:
• h’ kém phù hợp hơn (đạt độ chính xác kém hơn) h đối với tập
h học, n ưng
• h’ đạt độ chính xác cao hơn h đối với toàn bộ tập dữ liệu (bao
gồm cả những ví dụ được sử dụng sau quá trình huấn luyện)
Vấn đề over-fitting thường do các nguyên nhân:
• Lỗi (nhiễu) trong tập huấn luyện (do quá trình thu thập/xây dựng
tập dữ liệu)
• Số lượng các ví dụ học quá nhỏ, không đại diện cho toàn bộ tập
(phân bố) của các ví dụ của bài toán học
Trí Tuệ Nhân Tạo 16
Vấn đề over-fitting (2)
Giả sử gọi D là tập toàn bộ các ví dụ, và D_train là tập
các ví dụ học
Giả sử gọi ErrD(h) là mức lỗi mà giả thiết h sinh ra đối
với tập D và ErrD t i (h) là mức lỗi mà giả thiết h sinh , _ ra n
ra đối với tập D_train
Giả thiết h quá khớp (quá phù hợp) tập học D train _
nếu tồn tại một giả thiết khác h’:
• ErrD_train(h) < ErrD_train(h’), và
• ErrD(h) > ErrD(h’)
Trí Tuệ Nhân Tạo 17
Vấn đề over-fitting (3)
Trong số các giả thiết (hàm mục tiêu)
học được, giả thiết (hàm mục tiêu) nào Hàm mục tiêu f(x) nào
ấkhái quát hóa tốt nhất từ các ví dụ học?
Lưu ý: Mục tiêu của học máy là để
đạt được độ chính xác cao trong
đạt độ chính xác cao nh t
đối với các ví dụ sau này?
dự đoán đối với các ví dụ sau này,
không phải đối với các ví dụ học
O ’ Ư tiê h hà
f(x)
ccam s razor: u n c ọn m
mục tiêu đơn giản nhất phù hợp (không
nhất thiết hoàn hảo) với các ví dụ học
Khái át hó tốt h→ qu a ơn
→Dễ giải thích/diễn giải hơn
→Độ phức tạp tính toán ít hơn
x
Trí Tuệ Nhân Tạo 18
Vấn đề over-fitting – Ví dụ
Tiếp tục quá trình học cây quyết định sẽ làm giảm độ chính xác đối
với tập thử nghiệm mặc dù tăng độ chính xác đối với tập học
Trí Tuệ Nhân Tạo 19
[Mitchell, 1997]
Phân lớp Naïve Bayes
Là các phương pháp học phân lớp có giám sát và dựa
trên xác suất
Dựa trên một mô hình (hàm) xác suất
Việ hâ l i d t ê á iá t ị á ất ủ á khả c p n oạ ựa r n c c g r x c su c a c c
năng xảy ra của các giả thiết
Là một trong các phương pháp học máy thường được
sử dụng trong các bài toán thực tế
Dựa trên định lý Bayes (Bayes theorem)
Trí Tuệ Nhân Tạo 20
Định lý Bayes
)().|()|( hPhDPDhP =
• P(h): Xác suất trước (prior probability) rằng giả thiết (phân
)(DP
lớp) h là đúng
• P(D): Xác suất trước rằng tập dữ liệu D được quan sát (thu
được)
• P(D|h): Xác suất của việc quan sát được (thu được) tập dữ
liệu D với điều kiện giả thiết h là đúng,
• P(h|D): Xác suất của giả thiết h là đúng, với điều kiện tập
dữ liệu D được quan sát
Trí Tuệ Nhân Tạo 21
Định lý Bayes – Ví dụ (1)
Xét tập dữ liệu sau đây:
Day Outlook Temperature Humidity Wind Play Tennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 O t H t Hi h W k Yvercas o g ea es
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
Trí Tuệ Nhân Tạo 22
D12 Overcast Mild High Strong Yes
[Mitchell, 1997]
Định lý Bayes – Ví dụ (2)
Tập ví dụ D. Tập các ngày mà thuộc tính Outlook có giá trị Sunny và
thuộc tính Wind có giá trị Strong
Giả thiết (phân lớp) h. Anh ta chơi tennis
Xác suất trước P(h). Xác suất anh ta chơi tennis (không phụ thuộc
vào các thuộc tính Outlook vàWind)
Xác suất trước P(D). Xác suất của một ngày mà thuộc tính Outlook
có giá trị Sunny và thuộc tính Wind có giá trị Strong
ấ P(D|h). Xác su t của một ngày mà thuộc tính Outlook có giá trị
Sunny và Wind có giá trị Strong, với điều kiện (nếu biết rằng) anh ta
chơi tennis
P(h|D). Xác suất anh ta chơi tennis, với điều kiện (nếu biết rằng)
thuộc tính Outlook có giá trị Sunny và Wind có giá trị Strong
→ Phương pháp phân lớp Naïve Bayes dựa trên xác suất có điều
kiện (posterior probability) này!
Trí Tuệ Nhân Tạo 23
Cực đại hóa xác suất có điều kiện
Với một tập các giả thiết (các phân lớp) có thể H, hệ thống học
sẽ tìm giả thiết có thể xảy ra nhất (the most probable
hypothesis) h(∈H) đối với các dữ liệu quan sát được D
Giả thiết h này được gọi là giả thiết cực đại hóa xác suất có
điều kiện (maximum a posteriori – MAP)
)|(maxarg DhPhMAP =
Hh∈
)(
)().|(maxarg
DP
hPhDPh
Hh
MAP ∈
= (bởi định lý Bayes)
)().|(maxarg hPhDPh
Hh
MAP ∈
= (P(D) là như nhau
đối với các giả thiết h)
Trí Tuệ Nhân Tạo 24
MAP – Ví dụ
Tập H bao gồm 2 giả thiết (có thể)
• h1: Anh ta chơi tennis
• h2: Anh ta không chơi tennis
Tính giá trị của 2 xác xuất có điều kiện: P(h1|D), P(h2|D)
Giả thiết có thể nhất hMAP=h1 nếu P(h1|D) ≥ P(h2|D); ngược
lại thì hMAP=h2
Bởi vì P(D)=P(D h )+P(D h ) là như nhau đối với cả 2 giả, 1 , 2
thiết h1 và h2, nên có thể bỏ qua đại lượng P(D)
Vì vậy, cần tính 2 biểu thức: P(D|h1).P(h1) và
P(D|h2).P(h2), và đưa ra quyết định tương ứng
• Nếu P(D|h1).P(h1) ≥ P(D|h2).P(h2), thì kết luận là anh ta chơi tennis
N l i thì kết l ậ là h t khô h i t i• gược ạ , u n an a ng c ơ enn s
Trí Tuệ Nhân Tạo 25
Đánh giá khả năng xảy ra cao nhất
Phương pháp MAP: Với một tập các giả thiết có thể H, cần
tìm một giả thiết cực đại hóa giá trị: P(D|h).P(h)
Giả sử (assumption) trong phương pháp đánh giá khả năng
xảy ra cao nhất (maximum likelihood estimation – MLE):
Tất cả các giả thiết đều có giá trị xác suất trước như nhau:
P(hi)=P(hj), ∀hi,hj∈H
Phương pháp MLE tìm giả thiết cực đại hóa giá trị P(D|h);
trong đó P(D|h) được gọi là khả năng xảy ra (likelihood) của
dữ liệu D đối với h
Giả thiết cực đại hóa khả năng xảy ra (maximum likelihood
hypothesis)
)|(maxarg hDPh
Hh
MLE ∈
=
Trí Tuệ Nhân Tạo 26
MLE – Ví dụ
Tập H bao gồm 2 giả thiết có thể
• h1: Anh ta chơi tennis
• h2: Anh ta không chơi tennis
D: Tập dữ liệu (các ngày) mà trong đó thuộc tính Outlook có giá trị Sunny
và thuộc tính Wind có giá trị Strong
Tính 2 giá trị khả năng xảy ra (likelihood values) của dữ liệu D
đối với 2 giả thiết: P(D|h1) và P(D|h2)
• P(Outlook=Sunny Wind=Strong|h )= 1/8, 1
• P(Outlook=Sunny, Wind=Strong|h2)= 1/4
Giả thiết MLE hMLE=h1 nếu P(D|h1) ≥ P(D|h2); và ngược
lại thì hMLE=h2
→ Bởi vì P(Outlook=Sunny, Wind=Strong|h1) <
P(Outlook=Sunny, Wind=Strong|h2), hệ thống kết luận rằng:
Anh ta sẽ không chơi tennis!
Trí Tuệ Nhân Tạo 27
Phân loại Naïve Bayes (1)
Biểu diễn bài toán phân loại (classification problem)
• Một tập học D train trong đó mỗi ví dụ học x được biểu diễn là _ ,
một vectơ n chiều: (x1, x2, ..., xn)
• Một tập xác định các nhãn lớp: C={c1, c2, ..., cm}
• Với một ví dụ (mới) z, z sẽ được phân vào lớp nào?
Mục tiêu: Xác định phân lớp có thể (phù hợp) nhất đối với z
)|(maxarg zcPc i
Cc
MAP
i∈
=
)|(maxarg 21iMAP zzzcPc = ,...,, n
Cci∈
),...,,(
)().|,...,,(
maxarg
21
21
n
iin
Cc
MAP zzzP
cPczzzPc
i∈
= (bởi định lý Bayes)
Trí Tuệ Nhân Tạo 28
Phân loại Naïve Bayes (2)
Để tìm được phân lớp có thể nhất đối với z…
)()|( (P(z z z ) là.,...,,maxarg 21 iin
Cc
MAP cPczzzPc
i∈
= 1, 2,..., n
như nhau với các lớp)
Giả sử (assumption) trong phương pháp phân loại Naïve
Bayes. Các thuộc tính là độc lập có điều kiện (conditionally
independent) đối với các lớp
n∏
=
=
j
ijin czPczzzP
1
21 )|()|,...,,(
Phân loại Naïve Bayes tìm phân lớp có thể nhất đối với z
∏
=∈
=
n
j
iji
Cc
NB czPcPc
i 1
)|().(maxarg
Trí Tuệ Nhân Tạo 29
Phân loại Naïve Bayes – Giải thuật
Giai đoạn học (training phase), sử dụng một tập học
Đối với mỗi phân lớp có thể (mỗi nhãn lớp) ci∈C
• Tính giá trị xác suất trước: P(ci)
• Đối với mỗi giá trị thuộc tính xj, tính giá trị xác suất xảy ra
của giá trị thuộc tính đó đối với một phân lớp c : P(x |c ) i j i
Giai đoạn phân lớp (classification phase), đối với một ví dụ mới
• Đối với mỗi phân lớp ci∈C, tính giá trị của biểu thức:
∏
=
n
j
iji cxPcP
1
)|().(
• Xác định phân lớp của z là lớp có thể nhất c*
∏∈=
n
iji
Cc
cxPcPc
1
* )|().(maxarg
Trí Tuệ Nhân Tạo 30
=ji
Phân lớp Naïve Bayes – Ví dụ (1)
Một sinh viên trẻ với thu nhập trung bình và mức đánh giá tín dụng bình thường sẽ mua một cái máy tính?
Rec. ID Age Income Student Credit_Rating Buy_Computer
1 Young High No Fair No
2 Young High No Excellent No
3 Medium High No Fair Yes
4 Old M di N F i Ye um o a r es
5 Old Low Yes Fair Yes
6 Old Low Yes Excellent No
7 Medium Low Yes Excellent Yes
8 Young Medium No Fair No
9 Young Low Yes Fair Yes
10 Old Medium Yes Fair Yes
11 Young Medium Yes Excellent Yes
12 Medium Medium No Excellent Yes
13 Medium High Yes Fair Yes
Trí Tuệ Nhân Tạo 31
14 Old Medium No Excellent No
/~cse634/lecture_notes/0
7classification.pdf
Phân lớp Naïve Bayes – Ví dụ (2)
Biểu diễn bài toán phân loại
•z = (Age=Young Income=Medium Student=Yes Credit Rating=Fair) , , , _
• Có 2 phân lớp có thể: c1 (“Mua máy tính”) và c2 (“Không mua máy tính”)
Tính giá trị xác suất trước cho mỗi phân lớp
• P(c1) = 9/14
• P(c2) = 5/14
Tính giá trị xác suất của mỗi giá trị thuộc tính đối với mỗi phân lớp
• P(Age=Young|c1) = 2/9; P(Age=Young|c2) = 3/5
• P(Income=M di | ) = 4/9; P(Income=M di | ) = 2/5e um c1 e um c2
• P(Student=Yes|c1) = 6/9; P(Student=Yes|c2) = 1/5
• P(Credit_Rating=Fair|c1) = 6/9; P(Credit_Rating=Fair|c2) = 2/5
Trí Tuệ Nhân Tạo 32
Phân lớp Naïve Bayes – Ví dụ (3)
Tính toán xác suất có thể xảy ra (likelihood) của ví dụ z đối với mỗi
phân lớp
ố• Đ i với phân lớp c1
P(z|c1) = P(Age=Young|c1).P(Income=Medium|c1).P(Student=Yes|c1).
P(Credit_Rating=Fair|c1) = (2/9).(4/9).(6/9).(6/9) = 0.044
• Đối với phân lớp c2
P(z|c2) = P(Age=Young|c2).P(Income=Medium|c2).P(Student=Yes|c2).
P(Credit_Rating=Fair|c2) = (3/5).(2/5).(1/5).(2/5) = 0.019
Xác định phân lớp có thể nhất (the most probable class)
• Đối với phân lớp c1
P(c ) P(z|c ) = (9/14) (0 044) = 0 0281 . 1 . . .
• Đối với phân lớp c2
P(c2).P(z|c2) = (5/14).(0.019) = 0.007
→Kết luận: Anh ta (z) sẽ mua một máy tính!
Trí Tuệ Nhân Tạo 33
Phân lớp Naïve Bayes – Vấn đề (1)
Nếu không có ví dụ nào gắn với phân lớp ci có giá trị thuộc tính xj…
P(xj|ci)=0 , và vì vậy: 0)|()( =∏n cxPcP
Giải pháp: Sử dụng phương pháp Bayes để ước lượng P(xj|ci)
.
1=j
iji
)(
• n(ci): số lượng các ví dụ học gắn với phân lớp ci
mcn
mpxcn
cxP
i
ji
ij +
+=
)(
,
)|(
• n(ci,xj): số lượng các ví dụ học gắn với phân lớp ci có giá trị thuộc tính
xj
• p: ước lượng đối với giá trị xác suất P(xj|ci)
→Các ước lượng đồng mức: p=1/k, với thuộc tính fj có k giá trị có thể
• m: một hệ số (trọng số)
→Để bổ sung cho n(ci) các ví dụ thực sự được quan sát với thêm m
mẫu ví dụ với ước lượng p
Trí Tuệ Nhân Tạo 34
Phân lớp Naïve Bayes – Vấn đề (2)
Giới hạn về độ chính xác trong tính toán của máy tính
P( | )<1 đối với mọi giá trị thuộc tính và phân lớp• xj ci , xj ci
• Vì vậy, khi số lượng các giá trị thuộc tính là rất lớn, thì:
0)|(lim =⎟⎟
⎞
⎜⎜
⎛∏n cxP
1 ⎠⎝ =∞→ j ijn
Giải pháp: Sử dụng hàm lôgarit cho các giá trị xác suất
⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎥⎦
⎤⎢⎣
⎡= ∏
=∈
n
j
iji
Cc
NB cxPcPc
i 1
)|().(logmaxarg
⎟⎟⎠
⎞
⎜⎜⎝
⎛ += ∑
=∈
n
j
iji
Cc
NB cxPcPc
i 1
)|(log)(logmaxarg
Trí Tuệ Nhân Tạo 35
Phân loại văn bản bằng NB (1)
Biểu diễn bài toán phân loại văn bản
• Tập học D_train, trong đó mỗi ví dụ học là một biểu diễn văn bản gắn với
một nhãn lớp: D = {(dk, ci)}
• Một tập các nhãn lớp xác định: C = {ci}
Giai đoạn học
• Từ tập các văn bản trong D_train, trích ra tập các từ khóa
(keywords/terms): T = {tj}
• Gọi D ci (⊆D train) là tập các văn bản trong D train có nhãn lớp ci _ _ _
• Đối với mỗi phân lớp ci
-Tính giá trị xác suất trước của phân lớp ci: D
cD
cP ii
_
)( =
-Đối với mỗi từ khóa tj, tính xác suất từ khóa tj xuất hiện đối với lớp ci( )( ) TtdtdnctP ik cDd jkij ++= ∑ ∑∑ ∈ _ )( 1),()|( (n(dk,tj): số lần xuất hiện của từ khóa tj trong văn bản dk)
Trí Tuệ Nhân Tạo 36
n
ik mcDd Tt mk∈ ∈_ ,
Phân loại văn bản bằng NB (2)
Để phân lớp cho một văn bản mới d
Giai đoạn phân lớp
• Từ văn bản d, trích ra tập T_d gồm các từ khóa (keywords) tj đã
được định nghĩa trong tập T (T_d ⊆ T)
Giả ử ( ti ) Xá ất từ khó ất hiệ đối ới lớ• s assump on . c su a tj xu n v p
ci là độc lập đối với vị trí của từ khóa đó trong văn bản
P(tj ở vị trí k|ci) = P(tj ở vị trí m|ci), ∀k,m
• Đối với mỗi phân lớp ci, tính giá trị likelihood của văn bản d đối
với ci ∏
∈ dTt
iji ctPcP )|().(
j _
• Phân lớp văn bản d thuộc vào lớp c*
∏= iji ctPcPc* )|().(maxarg
Trí Tuệ Nhân Tạo 37
∈∈ dTtCc ji _
Học dựa trên láng giềng gần nhất
Một số tên gọi khác của phương pháp học dựa trên láng giềng
gần nhất (Nearest neighbor learning)
• Instance-based learning
• Lazy learning
• Memory-based learning
Ý tưởng của phương pháp học dựa trên láng giềng gần nhất
• Với một tập các ví dụ học
─ (Đơn giản là) lưu lại các ví dụ học
─ Không cần xây dựng một mô hình (mô tả) rõ ràng và tổng quát
của hàm mục tiêu cần học
• Đối với một ví dụ cần phân loại/dự đoán
─ Kiểm tra (xét) quan hệ giữa ví dụ đó với các ví dụ học để gán
giá trị của hàm mục tiêu (một nhãn lớp, hoặc một giá trị thực)
Trí Tuệ Nhân Tạo 38
Học dựa trên láng giềng gần nhất
Biểu diễn đầu vào của bài toán
• Mỗi ví dụ x được biểu diễn là một vectơ n chiều trong không gian
các vectơ X∈Rn
• x = (x1,x2,…,xn), trong đó xi (∈R) là một số thực
C ể húng ta xét 2 ki u bài toán học
• Bài toán phân lớp (classification)
─ Để học một hàm mục tiêu có giá trị rời rạc (a discrete-valued target
function)
─ Đầu ra của hệ thống là một trong số các giá trị rời rạc đã xác định
trước (một trong các nhãn lớp)
• Bài toán dự đoán/hồi quy (prediction/regression)
─ Để học một hàm mục tiêu có giá trị liên tục (a continuous-valued
target function)
─ Đầu ra của hệ thống là một giá trị số thực
Trí Tuệ Nhân Tạo 39
Phân lớp dựa trên NN – Ví dụ
Xét 1 láng giềng gần
Lớp c1 Lớp c2
nhất
→Gán z vào lớp c2
Ví dụ cần
phân lớp z
Xét 3 láng giềng gần
nhất
→Gán z vào lớp c1
Xét 5 láng giềng gần
nhất
→Gán z vào lớp c1
Trí Tuệ Nhân Tạo 40
Giải thuật phân lớp k-NN
Mỗi ví dụ học x được biểu diễn bởi 2 thành phần:
• Mô tả của ví dụ: x=(x1 x2 x ) trong đó xi∈R , ,…, n ,
• Nhãn lớp : c (∈C, với C là tập các nhãn lớp được xác định trước)
Giai đoạn học
• Đơn giản là lưu lại các ví dụ học trong tập học D = {x}
Giai đoạn phân lớp: Để phân lớp cho một ví dụ (mới) z
• Với mỗi ví dụ họcx∈D, tính khoảng cách giữa x và z
• Xác định tập NB(z) – các láng giềng gần nhất của z
Gồ k í d h t ầ hất ới tí h th ột hà→ m v ụ ọc rong D g n n v z n eo m m
khoảng cách d
• Phân z vào lớp chiếm số đông (the majority class) trong số các lớp
của các ví dụ học trong NB(z)
Trí Tuệ Nhân Tạo 41
Giải thuật dự đoán k-NN
Mỗi ví dụ học x được biểu diễn bởi 2 thành phần:
• Mô tả của ví dụ: x=(x1 x2 x ) trong đó xi∈R , ,…, n ,
• Giá trị đầu ra mong muốn: yx∈R (là một số thực)
Giai đoạn học
• Đơn giản là lưu lại các ví dụ học trong tập học D
Giai đoạn dự đoán: Để dự đoán giá trị đầu ra cho ví dụ z
ố ỗ• Đ i với m i ví dụ học x∈D, tính khoảng cách giữa x và z
• Xác định tập NB(z) – các láng giềng gần nhất của z
→ Gồm k ví dụ học trong D gần nhất với z tính theo một hàm khoảng
cách d
• Dự đoán giá trị đầu ra đối với z: ∑= )(1 NB xz yy
Trí Tuệ Nhân Tạo 42
∈ zxk
Xét một hay nhiều láng giềng?
Việc phân lớp (hay dự đoán) chỉ dựa trên duy nhất một láng
giềng gần nhất (là ví dụ học gần nhất với ví dụ cần phân
lớp/dự đoán) thường không chính xác
• Nếu ví dụ học này là một ví dụ bất thường, không điển hình (an
outlier) – rất khác so với các ví dụ khác
• Nếu ví dụ học này có nhãn lớp (phân lớp sai) – do lỗi trong quá
trình thu thập (xây dựng) tập dữ liệu
ầ ấ ầ Thường xét k (>1) các ví dụ học g n nh t với ví dụ c n phân
lớp, và gán ví dụ đó vào lớp chiếm số đông trong số k ví dụ
học gần nhất này
k thường được chọn là một số lẻ, để tránh cân bằng về tỷ lệ
phân lớp (ties in classification)
• Ví dụ: k= 3, 5, 7,…
Trí Tuệ Nhân Tạo 43
Hàm tính khoảng cách (1)
Hàm tính khoảng cách d
• Đóng vai trò rất quan trọng trong phương pháp học dựa trên láng
giềng gần nhất
• Thường được xác định trước, và không thay đổi trong suốt quá
trình học và phân loại/dự đoán
Lựa chọn hàm khoảng cách d
• Các hàm khoảng cách hình học: Dành cho các bài toán có các
thuộc tính đầu vào là kiểu số thực (xi∈R)
• Hàm khoảng cách Hamming: Dành cho các bái toán có các
thuộc tính đầu vào là kiểu nhị phân (xi∈{0,1})
• Hàm tính độ tương tự Cosine: Dành cho các bài toán phân lớp
văn bản (xi là giá trị trọng số TF/IDF của từ khóa thứ i)
Trí Tuệ Nhân Tạo 44
Hàm tính khoảng cách (2)
Các hàm tính khoảng cách hình học (Geometry distance
functions)
• Hàm Manhattan: ∑
=
−=
n
i
ii zxzxd
1
),(
• Hàm Euclid: ( )∑
=
−=
n
i
ii zxzxd
1
2),(
p/1⎞⎛
• Hàm Minkowski (p-norm):
n
i
p
ii zxzxd
1
),( ⎟⎠⎜⎝ −= ∑=
p/1⎞⎛• Hàm Chebyshev:
zx −= max
n
i
p
iip
zxzxd
1
lim),( ⎟⎠⎜⎝ −= ∑=∞→
Trí Tuệ Nhân Tạo 45
iii
Hàm tính khoảng cách (3)
Hàm khoảng cách
H i ∑=
n
ii zxDifferencezxd ),(),(amm ng
• Đối với các thuộc tính đầu
vào là kiểu nhị phân
=i 1
⎩⎨
⎧
=
≠=
)(,0
)(,1
),(
baif
baif
baDifference
• Ví dụ: x=(0,1,0,1,1)
n
Hàm tính độ tương tự
Cosine
• Đối với đầu vào là một vectơ ∑∑
∑
===
nn
i
ii zx
zx
zxzxd
22
1.),(
các giá trị trọng số (TF/IDF)
của các từ khóa
== i
i
i
i zx
11
Trí Tuệ Nhân Tạo 46
Chuẩn hóa miền giá trị thuộc tính
Hàm tính khoảng cách Euclid: ( )∑
=
−=
n
i
ii zxzxd
1
2),(
Giả sử mỗi ví dụ được biểu diễn bởi 3 thuộc tính: Age, Income (cho
mỗi tháng), và Height (đo theo mét)
• x = (Age=20, Income=12000, Height=1.68)
• z = (Age=40, Income=1300, Height=1.75)
Khoảng cách giữa x và z
• d(x z) = [(20-40)2 + (12000-1300)2 + (1 68-1 75)2]1/2, . .
• Giá trị khoảng cách này bị quyết định chủ yếu bởi giá trị khoảng cách (sự
khác biệt) giữa 2 ví dụ đối với thuộc tính Income
→Vì: Thuộc tính Income có miền giá trị rất lớn so với các thuộc tính khác
Cần phải chuẩn hóa miền giá trị (đưa về cùng một khoảng giá trị)
• Khoảng giá trị [0,1] thường được sử dụng
Đối với mỗi thuộc tính i: = /giá trị cực đại đối với thuộc tính i• xi xi _ _ _ _ _ _ _ _
Trí Tuệ Nhân Tạo 47
Trọng số của các thuộc tính
Hàm khoảng cách Euclid: ( )∑
=
−=
n
i
ii zxzxd
1
2),(
• Tất cả các thuộc tính có cùng (như nhau) ảnh hưởng đối với giá trị
khoảng cách
Các thuộc tính khác nhau có thể (nên) có mức độ ảnh hưởng khác
nhau đối với giá trị khoảng cách
Cần phải tích hợp (đưa vào) các giá trị trọng số của các thuộc tính
trong hàm tính khoảng cách n
•wi là trọng số của thuộc tính i:
Làm sao để xác định các giá trị trọng số của các thuộc tính?
( )∑
=
−=
i
iii zxwzxd
1
2),(
• Dựa trên các tri thức cụ thể của bài toán (vd: được chỉ định bởi các
chuyên gia trong lĩnh vực của bài toán đang xét)
• Bằng một quá trình tối ưu hóa các giá trị trọng số (vd: sử dụng một tập
học để học một bộ các giá trị trọng số tối ưu)
Trí Tuệ Nhân Tạo 48
Khoảng cách của các láng giềng (1)
Xét tập NB(z) – gồm k ví dụ học gần
nhất với ví dụ cần phân lớp/dự đoán z test instance z
• Mỗi ví dụ (láng giềng gần nhất) này có
khoảng cách khác nhau đến z
ề ả ở• Các láng gi ng này có nh hư ng như
nhau đối với việc phân lớp/dự đoáncho
z? → KHÔNG!
Cần gán các mức độ ảnh hưởng (đóng
góp) của mỗi láng giềng gần nhất tùy
theo khoảng cách của nó đến z
• Mức độ ảnh hưởng cao hơn cho các
láng giềng gần hơn!
Trí Tuệ Nhân Tạo 49
Khoảng cách của các láng giềng (2)
Gọi v là hàm xác định trọng số theo khoảng cách
• Đối với một giá trị d(x,z) – khoảng cách giữa x và z
•v(x,z) tỷ lệ nghịch với d(x,z)
Đối với bài toán phân lớp: ∑∈∈= )( ))(,().,(maxarg)( zNBx jCc xccIdenticalzxvzc j
⎧
⎩⎨ ≠
==
)(,0
)(,1
),(
baif
baif
baIdentical
∑ )().,( xfzxv
Đối với bài toán dự đoán (hồi quy): ∑
∈
∈=
)(
)(
),(
)(
zNBx
zNBx
zxv
zf
Lựa chọn một hàm xác định trọng số theo khoảng cách:
)(
1),(
zxd
zxv += α 2)]([
1),(
zxd
zxv += α
2
2),(
),( σ
zxd
ezxv
−=
Trí Tuệ Nhân Tạo 50
, ,
Học NN – Khi nào?
Các ví dụ được biểu diễn là các vectơ trong không gian số thực (Rn)
Số lượng các thuộc tính (số chiều của không gian) đầu vào không lớn
Tập học khá lớn (nhiều ví dụ học)
Các ưu điểm
Khô ầ b ớ h (hệ thố hỉ đ iả là l l i á í d h )• ng c n ư c ọc ng c ơn g n ưu ạ c c v ụ ọc
• Hoạt động tốt với các bài toán có số lớp khá lớn
→ Không cần phải học riêng rẽ n bộ phân lớp cho n lớp
ể ỗ• Phương pháp học k-NN (k >>1) có th làm việc được cả với dữ liệu l i
→ Việc phân lớp/dự đoán dựa trên k láng giềng gần nhất
Các nhược điểm
• Phải xác định hàm tính khoảng cách phù hợp
• Chi phí tính toán (về thời gian và bộ nhớ) tại thời điểm phân lớp/dự đoán
• Có thể phân lớp/dự đoán sai do các thuộc tính không liên quan (irrelevant ,
attributes)
Trí Tuệ Nhân Tạo 51
Tài liệu tham khảo
• E. Alpaydin. Introduction to Machine Learning. The MIT
Press, 2004.
• T. M. Mitchell. Machine Learning. McGraw-Hill, 1997.
• H. A. Simon. Why Should Machines Learn? In R. S.
Michalski, J. Carbonell, and T. M. Mitchell (Eds.):
M hi l i A tifi i l i t lli hac ne earn ng: n ar c a n e gence approac ,
chapter 2, pp. 25-38. Morgan Kaufmann, 1983.
Trí Tuệ Nhân Tạo 52
Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang
quangnn-fit@mail.hut.edu.vn
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
S diễ ới t i thứ khô hắ hắ uy n v r c ng c c c n
Học máy
ế Lập k hoạch
Trí Tuệ Nhân Tạo
2
Lập kế hoạch của con người (1)
Hành động mà không có kế hoạch (rõ ràng)
ố ầ Đ i với các mục tiêu g n (tức thì)
Ví dụ: Bật máy tính lên
Đối với các hành động (hoạt động) đã được huấn luyện (tập
luyện) kỹ
Ví dụ: Lái xe ô-tô
Khi một quá trình hành động có thể được thay đổi thoải mái
Ví dụ: Đi mua sắm ở siêu thị
Trí Tuệ Nhân Tạo 3
Lập kế hoạch của con người (2)
Hành động theo kế hoạch
Khi giải quyết một tình huống mới – Vd: Chuyển nhà (đến một nơi
ở mới)
Đối với các nhiệm vụ (công việc) phức tạp – Vd: Xây dựng kế
hoạch học tập cho một học kỳ
Khi môi trường hoạt động có chứa nguy cơ rủi ro/chi phí cao –
Vd: Quản lý nhà máy năng lượng hạt nhân
Khi cần hoạt động cộng tác với những người khác Vd: Xây –
dựng một ngôi nhà
Con người thường chỉ lập kế hoạch khi thực sự cần thiết
Bởi vì việc lập kế hoạch là phức tạp và tốn thời gian (chi phí vs.
lợi ích)
Con người thường chỉ cần các kế hoạch tốt hơn là tối ưu
Trí Tuệ Nhân Tạo 4
Lập kế hoạch của máy tính
Lập kế hoạch (Planning) của máy tính
Là quá trình tính toán của máy tính để lựa chọn và tổ chức các
hành động, dựa trên dự đoán (trước) các kết quả của các hành
động đó
Nhằm mục đích đạt được một số mục tiêu (objectives) xác định
Lập kế hoạch tối ưu: Đạt được các mục tiêu một cách tối ưu nhất
Các kiểu bài toán lập kế hoạch
Với các ràng buộc về thời gian (Time constraints)
Với các ràng buộc về thời gian và tài nguyên (Time and resource
constraints) – Bài toán lập lịch (Scheduling)
Với các ràng buộc về thời gian và tài nguyên, các điều kiện áp
dụng (applicability conditions) của các hành động, và các tác
động (effects) của các hành động đối với trạng thái của bài toán
Trí Tuệ Nhân Tạo 5
Mô hình khái niệm
Mô hình khái niệm (Conceptual model) cho bài toán lập
kế hoạch được biểu diễn bằng một hệ chuyển trạng thái
Một hệ chuyển trạng thái (State-transition system)
được biểu diễn bởi 4 thành phần: Σ = (S,A,E,γ)
S={s1,s2,…}: Tập hữu hạn các trạng thái (states) có thể của bài
toán
A={a1,a2,…}: Tập hữu hạn các hành động (actions) có thể được
thực hiện
E={e e }: Tập hữu hạn các sự kiện (events) có thể xảy ra trong1, 2,…
quá trình thực hiện kế hoạch
γ: S×A×E→S: Hàm chuyển trạng thái (a state-transition function)
Trí Tuệ Nhân Tạo 6
Biểu diễn bằng đồ thị
Một hệ chuyển trạng thái Σ = (S, A, E,γ) có thể được biểu
diễn bằng một đồ thị có nhãn và có hướng (a directed
labelled graph) G = (NG, EG), trong đó:
Mỗi nút biểu diễn một trạng thái trong tập S
Tức là: NG≡S
Mỗi cạnh liên kết từ s đến s′ (s, s′∈NG) có nhãn là (a,e) với a∈A,
e∈E
Tức là: Một cạnh (s,(a,e),s’)∈EG, nếu và chỉ nếu s′∈γ(s,a,e)
Trí Tuệ Nhân Tạo 7
Biểu diễn bằng đồ thị – Ví dụ
Các trạng thái S: s0…s5 (phụ thuộc vào các đối tượng: rô-bốt, cần trục, thùng hàng, …)
Các hành động A: cần trục nhấc (đặt) thùng hàng khỏi (lên) tấm nâng, rô-bốt di
chuyển giữa 2 vị trí, cần trục nhấc (đặt) thùng hàng khỏi (lên) rô-bốt
s0crane s2crane s5cranemove1
Không có sự kiện E = ∅
location1 location2
palletcont.
location1 location2
palletcont.
robotrobot
location1 location2
pallet
robot
cont.
move2
s1crane s3crane s4crane
take put
move1
take put
load
move2move1
location1 location2
pallet
cont.
location1 location2
pallet
cont.
location1 location2
pallet
robot robot robot
cont.
move2 unload
Trí Tuệ Nhân Tạo 8
(
Hệ chuyển trạng thái
Chuyển trạng thái: γ(s,a,e)
Sự kiện trung tính (neutral event), được ký hiệu là ε, được
dùng để biểu diễn đối với các chuyển trạng thái gây nên bởi
chỉ các hành động
Chuyển trạng thái γ(s a ε) với s∈S a∈A: được ký hiệu (ngắn gọn) , , , ,
bằng γ(s,a)
Hành động trung tính (neutral action), được ký hiệu là no-
op được dùng để biểu diễn đối với các chuyển trạng thái gây,
nên bởi chỉ các sự kiện
Chuyển trạng thái γ(s,no-op,e) , với s∈S, e∈E : được ký hiệu
(ngắn gọn) bằng ( ) γ s,e
Trong biểu diễn bằng đồ thị
Nhãn (a,ε) được ký hiệu ngắn gọn bằng a
Nhãn (no-op,e) được ký hiệu ngắn gọn bằng e
Trí Tuệ Nhân Tạo 9
Các hành động vs. Các sự kiện
Cả hành động (action) và sự kiện (event) đều ảnh hưởng đến
sự tiến triển của một hệ chuyển trạng thái
Các hành động: Thể hiện các chuyển trạng thái được điều
khiển bởi bộ thực hiện kế hoạch (plan executor)
Nếu hành động A và ( ) ≠ ∅ thì được gọi là có thể áp a∈ γ s, a, ε , a
dụng được đối với trạng thái s
Áp dụng hành động a ở trạng thái s sẽ làm hệ thống chuyển đến
trạng thái ′ ( ) s ∈ γ s, a
Các sự kiện: Thể hiện các chuyển trạng thái xảy ra ngẫu
nhiên
Nếu sự kiện e∈E và γ(s, no-op, e) ≠ ∅, thì e được gọi là có thể
xảy ra đối với trạng thái s
Sự xuất hiện (xảy ra) sự kiện e ở trạng thái s sẽ làm hệ thống
chuyển đến trạng thái s′∈ γ(s, e)
Trí Tuệ Nhân Tạo 10
Kế hoạch và Mục tiêu
Kế hoạch (Plan): Là một cấu trúc (chuỗi có thứ tự) các
hành động phù hợp cần thực hiện để đạt được một mục
tiêu từ một trạng thái ban đầu
Các kiểu mục tiêu (Objective)
Trạng thái đích (goal state), hoặc một tập các trạng thái đích
Thỏa mãn một tập các điều kiện (conditions) đối với chuỗi các
trạng thái đã duyệt qua
Tối ưu hóa một hàm tiện ích (utility function) được định nghĩa đối
ới á t thái đã d ệtv c c rạng uy qua
Một nhiệm vụ (task) cần hoàn thành
Trí Tuệ Nhân Tạo 11
Lập kế hoạch và thực hiện
Bộ lập kế hoạch (Planner)
Đầu vào: Mô tả của hệ chuyển trạng
hái hái đầ iê Trạng
Mô tả của Σ
t Σ, trạng t u, mục t u
Đầu ra: Kế hoạch để đạt được mục tiêu
đó
Planner
thái đầu
Mục tiêu
Kế h h Bộ điều khiển (Controller)
Đầu vào: Kế hoạch cần thực hiện, trạng
thái hiện thời (thông qua hàm quan sát
S O ới O là tậ á át ó thể)
Controller
oạc
η: → , v p c c quan s c
Đầu ra: Hành động (tiếp theo) cần thực
hiện
ể
System Σ
Hành độngQuan sát
Hệ chuy n trạng thái (State-
transition system)
Tiến triển tùy thuộc vào các hành động
đ th hiệ à á kiệ ả
Sự kiện
( inf ed ac uk/teaching/ược ực n v c c sự n x y ra
Trí Tuệ Nhân Tạo 12
. . . .
courses/plan/)
Lập kế hoạch động (1)
Vấn đề: Thế giới thực tế có thể
khác với mô hình được biểu diễn Trạng
Mô tả của Σ
bởi Σ
Sự khác biệt này cần phải được
xử lý bởi bộ điểu khiển (Controller)
Planner
thái đầu
Mục tiêu
Kế h h
Mô hình thực tế: Kết hợp đan
xen giữa lập kế hoạch và thực
Controller
oạcTình trạng thực
hiện
hiện
Giám sát kế hoạch (Plan
supervision): để phát hiện những System Σ
Hành độngQuan sát
khi kết quả quan sát được khác
với mong muốn Sự kiện
( inf ed ac uk/teaching/
Trí Tuệ Nhân Tạo 13
. . . .
courses/plan/)
Lập kế hoạch động (2)
…
Sửa lại kế hoạch (Plan revision): Trạng
Mô tả của Σ
để thay đổi thích nghi kế hoạch (đã
lập) theo những tình huống mới
Lập lại kế hoạch (Re-planning): để
Planner
thái đầu
Mục tiêu
Kế h h
sinh ra kế hoạch mới từ trạng thái
hiện thời (hoặc từ trạng thái đầu)
ế
Controller
oạcTình trạng thực
hiện
Lập k hoạch động (Dynamic
planning): Quá trình lặp lại giữa
bộ lập kế hoạch và bộ điều khiển System Σ
Hành độngQuan sát
thực hiện
Tùy thuộc tình trạng của việc thực
hiện kế hoạch
Sự kiện
( inf ed ac uk/teaching/
Trí Tuệ Nhân Tạo 14
. . . .
courses/plan/)
Giả thiết A0: Tập các trạng thái
Giả thiết A0: Tập các trạng thái (trong biểu diễn của Σ)
là hữu hạn
Nới lỏng điều kiện của giả thiết A0
Để biểu diễn các hành động tạo nên (làm xuất hiện) các đối
tượng mới của bài toán
Để cho phép làm việc với các biến trạng thái kiểu số (numerical-
valued state variables) – chứ không chỉ với các biến trạng thái
kiểu định danh (nominal-valued state variables)
Vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A0
Khả năng quyết định được (decidability) và khả năng kết thúc
(termination) của các bộ lập kế hoạch sẽ không được bảo đảm
Trí Tuệ Nhân Tạo 15
Giả thiết A1: Quan sát đầy đủ
Giả thiết A1: Hệ thống có thể quan sát được đầy đủ (fully observable)
Planner và Controller có tri thức (quan sát) đầy đủ về trạng thái của thế giới
hxung quan
Hàm quan sát η cho phép xác định chính xác trạng thái tương ứng với
quan sát
Nới lỏng điều kiện của giả thiết A1
Để làm việc với các trạng thái mà trong đó các khía cạnh (của một trạng
thái) không được quan sát (nhận biết) đầy đủ
ế ể ắ Ví dụ: Trong bài toán lập k hoạch lộ trình có th xảy ra t c đường, thì
trạng thái của bài toán là không thể nhận biết (quan sát) được đầy đủ
Các vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A1
Với hàm quan sát η: η(s)=o, thì η-1(o) thường sẽ trả về nhiều hơn một trạng
thái có thể – vấn đề nhập nhằng
Các quan sát không hoàn toàn xác định được trạng thái hiện tại
Làm sao để xác định trạng thái tiếp theo là gì?
Trí Tuệ Nhân Tạo 16
Giả thiết A2: Chuyển trạng thái
Giả thiết A2: Kết quả của mỗi chuyển trạng thái là một trạng
thái xác định (duy nhất)
Với trạng thái s∈S, hành động a∈A, và sự kiện e∈E, thì không thể
xảy ra γ(s,a,e)={s’, s’’} (với s’, s’’ là 2 trạng thái khác nhau)
ề ế Nới lỏng đi u kiện của giả thi t A2
Để lập kế hoạch cho các bài toán mà trong đó việc thực hiện một
hành động có thể đưa đến các kết quả khác nhau
Các vấn đề gặp phải khi nởi lỏng điều kiện của giả thiết A2
Controller phải quan sát được các kết quả thực tế của một hành
động
Kế hoạch được xây dựng có thể bao gồm thêm các thành phần
để xử lý với các hành động có nhiều kết quả
Trí Tuệ Nhân Tạo 17
Giả thiết A3: Các sự kiện
Giả thiết A3: Hệ thống là tĩnh, không có các sự kiện
(ngẫu nhiên) xảy ra (E=∅)
Σ = (S,A,∅,γ); hay biểu diễn ngắn gọn là: (S,A,γ)
Nới lỏng điều kiện của giả thiết A3
Để biểu diễn (mô hình hóa) các bài toán lập kế hoạch trong đó có
xảy ra các sự kiện ngẫu nhiên
Vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A3
Đối với Planner, thì môi trường hoạt động của hệ thống trở nên
không xác định
Trí Tuệ Nhân Tạo 18
Giả thiết A4: Mục tiêu hạn chế
Giả thiết A4: Planner làm việc với một trạng thái đích,
hoặc với một tập các trạng thái đích
Nới lỏng điều kiện của giả thiết A4
Để lập kế hoạch cho các bài toán mà trong đó mục tiêu được biểu
diễn bằng:
các ràng buộc đối với các trạng thái và kế hoạch, hoặc
hàm tiện ích hoặc ,
nhiệm vụ cụ thể
Vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A4
Làm thế nào để biểu diễn và suy diễn đối với các ràng buộc, các
hàm tiện ích, và các nhiệm vụ?
Trí Tuệ Nhân Tạo 19
Giả thiết A5: Chuỗi hành động
Giả thiết A5: Một kế hoạch được xây dựng là một chuỗi hữu
hạn có thứ tự của các hành động được thực hiện liên tiếp nhau
Nới lỏng điều kiện của giả thiết A5
Để lập kế hoạch cho các bài toán trong đó có xảy ra các sự kiện
ngẫu nhiên (Xem giả thiết A3)
Để tạo nên các kiểu kế hoạch khác nhau (kế hoạch có điều kiện rẽ
nhánh, kế hoạch trong đó có những phần mà các hành động được
thực hiện không theo thứ tự,…)
Các vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A5
ầ ố Không được tạo thêm công việc (yêu c u) đ i với Controller
Suy diễn với các cấu trúc dữ liệu phức tạp hơn
Trí Tuệ Nhân Tạo 20
Giả thiết A6: Thời gian
Giả thiết A6: Trong hệ chuyển trạng thái Σ, các hành động và
các sự kiện không có khoảng thời gian xảy ra
Các chuyển trạng thái xảy ra tức thì – không có biểu diễn rõ ràng
về thời gian
Nới lỏng điều kiện của giả thiết A6
Để làm việc với các hành động thực hiện trong một khoảng thời
gian, các hành động xảy ra đồng thời, và các thời hạn hoàn thành
(deadines)
Các vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A6
Biểu diễn và suy diễn về thời gian (do các kế hoạch chứa các
thông tin về thời gian)
Controller phải đợi cho đến khi có được kết quả (tác động) của
các hành động (vì mỗi hành động xảy ra trong một khoảng thời
gian, chứ không tức thời)
Trí Tuệ Nhân Tạo 21
Mô hình giới hạn
Mô hình giới hạn (restricted model) sẽ đặt ra tất cả các
điều kiện trong 7 giả thiết nêu trên (A0-A6)
Mô hình giới hạn được sử dụng trong lập kế hoạch cổ điển
(classical planning)
ể ễ ế Bi u di n hình thức của bài toán lập k hoạch P=(Σ,si,Sg)
Σ = (S,A,γ): là hệ chuyển trạng thái
si∈S: là trạng thái đầu
Sg ⊂ S: là tập các trạng thái đích
Yêu cầu: Tìm một chuỗi các hành động ۃa1,a2,…,akۄ,
tương ứng với một chuỗi các chuyển trạng thái
ۃsi,s1,…,skۄ, sao cho: s1= γ(si,a1), s2= γ(s1,a2), …, sk= γ(sk-
a ) and s ∈S1, k , k g
Trí Tuệ Nhân Tạo 22
Ví dụ: Rô-bốt bốc dỡ hàng
Bài toán lập kế hoạch cho rô-
bốt bốc dỡ hàng ở một cầu
cảng
Một cầu cảng với một số vị trí
(cho việc cập bến, các con tàu
cần bốc dỡ hàng, các nhà kho,
các nơi đỗ xe tải,…)
Các thùng hàng (containers)
cần được bốc lên/dỡ xuống
tàu hàng (hoặc kho hàng)
ố ầ
(M. Ghallab, ESSLLI 2002)
Rô-b t và c n trục (crane) di
chuyển các thùng hàng để
bốc/dỡ hàng lên/xuống tàu
Trí Tuệ Nhân Tạo 23
Các đối tượng (1)
Các vị trí locations {loc1, loc2, …}
Nhà kho các chỗ neo đậu tàu tàu được bốc dỡ hàng hay nơi đỗ , , ,
xe tải
Các rô-bốt bốc dỡ hàng robots {robot1, robot2, …}
Các rô-bốt (xe di chuyển thùng hàng)
Các rô-bốt có thể di chuyển giữa các vị trí gần kề
Tại mỗi vị trí (location) chỉ có tối đa 1 rô bốt đang làm việc , -
Các cần trục bốc dỡ hàng cranes {crane1, crane2, …}
Mỗi cần trục gắn (cố định) với một vị trí nhất định
Di chuyển các thùng hàng giữa các rô-bốt và các cọc hàng (piles)
- thuộc cùng một vị trí (the same location)
Trí Tuệ Nhân Tạo 24
Các đối tượng (2)
Các cọc hàng piles {pile1, pile2, …}
Mỗi cọc hàng nằm ở (thuộc về) một vị trí nhất định
Tấm nâng hàng (pallet) nằm ở dưới đáy của các cọc hàng – trên
một tấm nâng hàng có thể có các thùng hàng
Các thùng hàng containers {cont1, cont2, …}
Được xếp trong một cọc hàng nằm trên một tấm nâng hàng
Được đặt trên rô bốt hoặc nắm (giữ) bởi cần trục - ,
Tấm nâng hàng pallet
Được đặt dưới đáy của một cọc hàng
Chỉ cần một ký hiệu duy nhất (pallet), vì mỗi tấm nâng được xác
định (gắn với) một cọc hàng
Trí Tuệ Nhân Tạo 25
Các quan hệ cố định
Các quan hệ cố định (topology) là các quan hệ không
thay đổi theo thời gian
Quan hệ adjacent(l,l′)
Vị trí l là gần kề với vị trí l’
Quan hệ attached(p,l)
Cọc hàng p thuộc về (gắn với) vị trí l
Quan hệ belong(k,l)
Cầ t k là iệ ở ( ắ ới) ị t í l n rục m v c g n v v r
Trí Tuệ Nhân Tạo 26
Các quan hệ có thể thay đổi (1)
Quan hệ occupied(l)
Vị trí l hiện tại có một rô-bốt đang làm việc
Lưu ý: Mỗi vị trí chỉ có tối đa 1 rô-bốt đang làm việc
Quan hệ at(r,l)
Rô-bốt r đang làm việc ở vị trí l
Quan hệ loaded(r,c)
Rô-bốt r hiện đang chở thùng hàng c
Quan hệ unloaded(r)
Rô-bốt hiện đang không chở thùng hàng nào cả
Lưu ý: loaded(r,c) có nghĩa là not unloaded(r)
Trí Tuệ Nhân Tạo 27
Các quan hệ có thể thay đổi (2)
Quan hệ holding(k,c)
Cần trục k hiện tại đang giữ thùng hàng c
Quan hệ empty(k)
Cần trục k hiện tại không giữ bất kỳ thùng hàng nào
Quan hệ in(c,p)
Thùng hàng c hiện tại đang ở trong cọc hàng p
Quan hệ on(c,c′)
Thùng hàng c hiện tại đang nằm ở trên cọc hàng/tấm nâng c′
Quan hệ top(c,p)
Thùng hàng/tấm nâng c hiện tại đang nằm trên đỉnh của cọc hàng
p
Trí Tuệ Nhân Tạo 28
Các hành động
Hành động move(r,l,l’)
Rô-bốt r di chuyển từ vị trí l đến vị trí l’ (không có rô-bốt khác đang
làm việc ở l’)
Hành động take(c,k,p)
Tại cùng vị trí l: cần trục k (hiện không giữ thùng hàng nào) lấy thùng
hàng c khỏi cọc hàng p
Hành động put(c,k,p)
Tại cùng vị trí l: cần trục k đặt thùng hàng c lên đỉnh của cọc hàng p
Hành động load(r,c,k)
Tại cùng vị trí l: cần trục k đặt thùng hàng c vào rô-bốt r (hiện không
giữ thùng hàng nào)
Hành động unload(r,c,k)
Tại cùng vị trí l: cần trục k (hiện không giữ thùng hàng nào) lấy thùng
hàng c khỏi rô-bốt r
Trí Tuệ Nhân Tạo 29
Các ứng dụng thực tế
Các kết quả nghiên cứu của lĩnh vực Lập kế hoạch
(planning) đã được áp dụng thành công trong nhiều bài
toán thực tế
Không gian vũ trụ, Hàng không, Đường sắt
Rô-bốt và lập kế hoặch di chuyển
CAD/CAM
Lập kế hoạch giải quyết các tình huống khẩn cấp
Điều khiển các quá trình công nghiệp
Các trò chơi (games)
…
Trí Tuệ Nhân Tạo 30
Các file đính kèm theo tài liệu này:
- Giáo trình Trí tuệ nhân tạo Bách Khoa Hà Nội.pdf