Học Máy
(IT 4862)
ễhậ
Nguy
ễ
n N
hậ
t Quang
quangnn-fit@mail.hut.edu.vn
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ thông tin và truyền thông
Năm học 2011-2012
Nội
d
ô
h
Nội
d
ung m
ô
n
h
ọc:
Giới thiệu chun
g
g
Đánh giá hiệunăng hệthống họcmáy
Các phương pháp họcdựatrênxácsuất
Các
phương
pháp
học
dựa
trên
xác
suất
Các phương pháp họccógiámsát
Học
quy
nạp
luật
(Rule induction)
Học
quy
nạp
luật
(Rule
induction)
Các phương pháp học không giám sát
L
ộ
tá
L
ọcc
ộ
ng
tá
c
Họctăng cường
2
Học Máy – IT 4862
Quy nạ
p
luật
–
Giới thiệu (1)
p
Để họcmộttậpcácluật (IF-THEN) cho bài toán phân loại
•
Phù
hợp
khi
hàm
mục
tiêu
(
phân
loại
)
có
thể
được
biểu
diễn
bằng
•
Phù
hợp
khi
hàm
mục
tiêu
(
phân
loại
)
có
thể
được
biểu
diễn
bằng
mộttậpcácluật (IF-THEN)
Hàm mục tiêu:
h
≡{
L
uật
1
,
L
uật
2
, ...,
L
uật
m
}
Luậtj≡IF (Điều-kiệnj1 ΛĐiều-kiệnj2 Λ... ΛĐiều-
kiệnjn) THEN Kếtluậnj
Các luật (IF-THEN)
•Mộtphương pháp phổbiếnđể biểudiễntri thức
•Phương pháp biểudiễndễhiểunhấtđốivớingười dùng
3
Học Máy – IT 4862
Quy nạ
p
luật
–
Giới thiệu (2)
p
Nhắclại: Học cây quyết định (Decision tree learning) cũng
có cho
p
hé
p
h
ọ
c m
ộ
tt
ập
các lu
ậ
t lo
g
ic đ
ị
nh đề
pp
ọ
ộ
ập
ậgị
•Bước 1: Học cây quyết định
•Bước 2: Biểudiễnmỗiđường đi trong cây (từnút gốcđến nút lá)
thành
một
luật
tương
ứng
thành
một
luật
tương
ứng
Học mộttậpcácluật
•H
ọ
c câ
y
q
u
y
ết đ
ị
nh: T
ập
các lu
ậ
t lo
g
ic đ
ị
nh đề đư
ợ
c h
ọ
c đồn
g
thời
ọ
y
qy ị
ập
ậg
ị
ợ ọ
g
•Học quy nạpluật: Tậpcácluật logic định đề/vịtừđược học tuầntự
(từng luật một)
Cá
iải
th ật
khá
h
để
h
á
kiể
lật
khá
h
Cá
cg
iải
th
u
ật
khá
cn
h
au
để
h
ọc c
á
c
kiể
u
l
u
ật
khá
cn
h
au
•Các luật logic định đề (chỉsửdụng các ký hiệuhằng)
•Các lu
ậ
t lo
g
ic v
ị
từ
(
sửd
ụ
n
g
cảcác k
ý
hi
ệ
ubiếnvà các k
ý
hi
ệ
uv
ị
từ
)
ậg
ị
(
ụg
ý
ệ
ý
ệ
ị
)
–khảnăng diễnđạt cao hơn
4
Học Máy – IT 4862
Quy nạ
p
luật
–
Ví dụ(1)
p
Học mộttậpcácluật logic định đề
Vd: Hàm m
ụ
ctiêu
(
p
hân lo
ạ
i
)
B
u
y
Com
p
uter đư
ợ
c biểudiễnbởi:
ụ
(
p
ạ
)
y
_
p
ợ
IF (Age=Old ΛStudent=No) THEN Buy_Computer=No
IF (Student=Yes) THEN Buy_Computer=Yes
IF (Age=Medium ΛIncome=High) THEN Buy_Computer=Yes
Học
một
tập
các
luật
logic
vị
từ
Học
một
tập
các
luật
logic
vị
từ
Vd: Hàm mục tiêu (khái niệm) Ancestor được biểudiễnbởi:
IF Parent
(
x,y
)
THEN
A
ncestor
(
x
,y
)
(
,y
)
(
,y
)
IF Parent(x,y) ΛAncestor(y,z) THEN Ancestor(x,z)
(
Parent
(
x
,y
)
là m
ộ
tv
ị
từthểhi
ệ
n
y
là cha/m
ẹ
của
x
)
(
(
,y
)
ộ
ị
ệ
y
ẹ
)
5
Học Máy – IT 4862