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
Giải
thuật
di
truyền
(Genetic algorithm)
Giải
thuật
di
truyền
(Genetic
algorithm)
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
Giải thuật di tru
y
ền
–
Giới thiệu
Dựa trên (bắt chước) quá trình tiến hóa tự nhiên trong sinh học
Á
p
d
ụ
n
g
p
hươn
g
p
há
p
tìm kiếm n
g
ẫu nhiên
(
stochastic search
)
pụgp gp p g()
để tìm được lời giải (vd: một hàm mục tiêu, một mô hình phân
lớp, …) tối ưu
Giảithuậtditruyền (Generic Algorithm
GA) có khảnăng tìm
Giải
thuật
di
truyền
(Generic
Algorithm
–
GA)
có
khả
năng
tìm
được các lời giải tốt thậm chí ngay cả với các không gian tìm
kiếm (lời giải) không liên tục rất phức tạp
Mỗikhả ă ủ lờiiảiđbiểdiễbằ ộ hỗihị
Mỗi
khả
n
ă
ng c
ủ
a
lời
g
iải
đ
ược
biể
u
diễ
n
bằ
ng m
ộ
t c
h
u
ỗi
n
hị
phân (vd: 100101101) – được gọi là nhiễm sắc thể
(chromosome)
•Việc biểu diễn này phụ thuộc vào từng bài toán cụ thể
GA cũng được xem như một bài toán học máy (a learning
bl
)d tê átì htốihó (
ti i ti
)
3
Học Máy – IT 4862
p
ro
bl
em
)
d
ựa
t
r
ê
n qu
á
t
r
ì
n
h
tối
ưu
hó
a
(
op
ti
m
i
za
ti
on
)
Giải thuật di tru
y
ền
–
Các bước chính
Xây dựng (khởitạo) quầnthể(population) ban đầu
•Tạo nên mộtsốcác giảthiết(khảnăng củalờigiải) ban đầu
Mỗi
giả
thiết
khác
các
giả
thiết
khác
(
vd
:
khác
nhau
đối
với
các
giá
trị
của
một
•
Mỗi
giả
thiết
khác
các
giả
thiết
khác
(
vd
:
khác
nhau
đối
với
các
giá
trị
của
một
sốtham sốnào đócủa bài toán)
Đánh giá quầnthể
Đánh
giá
(
cho
điểm
)
mỗi
giả
thiết
(
d
bằng
cách
kiểm
tra
độ
chính
ác
của
•
Đánh
giá
(
cho
điểm
)
mỗi
giả
thiết
(
v
d
:
bằng
cách
kiểm
tra
độ
chính
x
ác
của
hệthống trên mộttậpdữliệukiểmthử)
•Trong lĩnh vựcsinhhọc, điểmđánh giá này củamỗigiảthiếtđượcgọilàđộ
phù
hợp
(fitness)
của
giả
thiết
đó
phù
hợp
(fitness)
của
giả
thiết
đó
•Xếphạng các giảthiết theo mứcđộ phù hợpcủa chúng, và chỉgiữlại các giả
thiếttốtnhất(gọilàcác giảthiết phù hợpnhất – survival of the fittest)
Sản
sinh
ra
thế
hệ
tiếp
theo
(next generation)
Sản
sinh
ra
thế
hệ
tiếp
theo
(next
generation)
•Thay đổingẫu nhiên các giảthiếtđể sảnsinhrathế hệtiếp theo (gọilàcác
con cháu – offspring)
Lặp
lại
quá
trình
trên
cho
đến
khi
ở
một
thế
hệ
nào
đó
có
giả
thiết
tốt
nhất
có
độ
4
Học Máy – IT 4862
Lặp
lại
quá
trình
trên
cho
đến
khi
ở
một
thế
hệ
nào
đó
có
giả
thiết
tốt
nhất
có
độ
phù hợp cao hơn giá tri phù hợp mong muốn(định trước)
GA(Fitness, θ, n, rco, rmu)
Fit
A f ti th t d th (fit ) i h th i
Fit
ness:
A
f
unc
ti
on
th
a
t
pro
d
uces
th
e score
(fit
ness
)
g
i
ven a
h
ypo
th
es
i
s
θ: The desired fitness value (i.e., a threshold specifying the termination condition)
n: The number of hypotheses in the population
r
co: The percentage of the population influenced by the crossover operator at each step
rmu: The percentage of the population influenced by the mutation operator at each step
Initialize the population:
H
Randomly generate
hypotheses
Initialize
the
population:
H
←
Randomly
generate
n
hypotheses
Evaluate the initial population. For each h∈H: compute Fitness(h)
w
hile (max
{h
∈
H
}
Fitness(h) <
θ
)
do
{h
∈
H
}
Hnext ← ∅
Reproduction (Replication). Probabilistically select (1-rco).nhypotheses of
H
to add to
H
next
H
to
add
to
H
next
.
The probability of selecting hypothesis hifrom His:
∑
=n
j
i
i
)Fitness(h
)Fitness(h
)P(h
=
j
1
5
Học Máy – IT 4862