Bài giảng Học máy (IT 4862) - Bài 3: Các phương pháp học dựa trên xác suất - Nguyễn Nhật Quang

Học Máy
(IT 4862)
ễ hậNguy n N 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 ô hung m n ọc:
„ Giới thiệu chung
„ Đánh giá hiệu năng hệ thống học máy
Cá h há h d t ê á ất„ c p ương p p ọc ựa r n x c su
„ Các phương pháp học có giám sát
„ Các phương pháp học không giám sát
„ Lọc cộng tác
„ Học tăng cường
2
Học Máy – IT 4862
Các phương pháp học dựa trên xác suất
„ Các phương pháp thống kê cho bài toán phân loại
Phâ l i d t ê ột ô hì h á ất ở„ n oạ ựa r n m m n x c su cơ s
„ Việc phân loại dựa trên khả năng xảy ra (probabilities) 
của các phân lớp 
„ Các chủ đề chính:
• Giới thiệu về xác suất 
• Định lý Bayes
• Xác suất hậu nghiệm cực đại (Maximum a posteriori)
• Đánh giá khả năng có thể nhất (Maximum likelihood estimation)
• Phân loại Naïve Bayes
• Cực đại hóa kỳ vọng (Expectation maximization)
3Học Máy – IT 4862
Các khái niệm cơ bản về xác suất
„ Giả sử chúng ta có một thí nghiệm (ví dụ: đổ một quân xúc sắc) mà kết 
quả của nó mang tính ngẫu nhiên (phụ thuộc vào khả năng có thể xảy 
ra)
„ Không gian các khả năng S. Tập hợp tất cả các kết quả có thể xảy ra
Ví dụ: S {1 2 3 4 5 6} đối với thí nghiệm đổ quân xúc sắc = , , , , , 
„ Sự kiện E. Một tập con của không gian các khả năng
Ví dụ: E= {1}: kết quả quân súc xắc đổ ra là 1
Ví d kết ả â ú ắ đổ là ột ố lẻ ụ: E= {1,3,5}: qu qu n s c x c ra m s 
„ Không gian các sự kiện W. Không gian (thế giới) mà các kết quả của sự 
kiện có thể xảy ra
ồ ấ ầ ổ ắVí dụ: W bao g m t t cả các l n đ súc x c
„ Biến ngẫu nhiên A. Một biến ngẫu nhiên biểu diễn (diễn đạt) một sự 
kiện, và có một mức độ về khả năng xảy ra sự kiện này
4Học Máy – IT 4862
Biểu diễn xác suất
P(A): “Phần của không gian (thế giới) mà trong đó A là đúng”
Không gian sự kiện 
của (không gian của 
Không gian mà 
trong đó A là 
tất cả các giá trị có 
thể xảy ra của A)
đúng
Không gian mà 
trong đó A là sai
[ cs cmu edu/~awm/tutorials]
5Học Máy – IT 4862
. . .
Các biến ngẫu nhiên 2 giá trị
„ Một biến ngẫu nhiên 2 giá trị (nhị phân) có thể nhận một 
trong 2 giá trị đúng (true) hoặc sai (false) 
„ Các tiên đề
•0 ≤ P(A) ≤ 1 
•P(true)= 1
•P(false)= 0 
•P(A V B)= P(A) + P(B) - P(A ∧ B)
„ Các hệ quả 
•P(not A)≡ P(~A)= 1 - P(A)
•P(A)= P(A ∧ B) + P(A ∧ ~B) 
6Học Máy – IT 4862
Các biến ngẫu nhiên đa trị
Một biến ngẫu nhiên nhiều giá trị có thể nhận một trong số 
k (>2) giá trị {v1,v2,,vk} 
jivAvAP ji ≠==∧= if 0)(
P(A=v1 V A=v2 V ... V A=vk) = 1
∑ ===∨∨=∨= i vAPvAvAvAP )()(
1)( ==∑k jvAP
=j
ji
1
21 ...
1=j
[ ]( ) )(...21 jii vABPvAvAvABP =∧==∨∨=∨=∧ ∑
[] 1j=
7Học Máy – IT 4862
Xác suất có điều kiện (1)
„ P(A|B) là phần của không gian (thế giới) mà trong đó A
ề ếlà đúng, với đi u kiện (đã bi t) là B đúng
„ Ví dụ
• A: Tôi sẽ đi đá bóng vào ngày mai
• B: Trời sẽ không mưa vào ngày mai
• P(A|B): Xác suất của việc tôi sẽ đi đá bóng vào ngày mai nếu 
(đã biết rằng) trời sẽ không mưa (vào ngày mai)
8Học Máy – IT 4862
Xác suất có điều kiện (2)
Định nghĩa: ),()|( BAPBAP 
)(BP
=
Không 
gianCác hệ quả: 
mà 
trong 
đó B
đú
P(A,B)=P(A|B).P(B)
ng
Không gian mà 
trong đó A đúng
P(A|B)+P(~A|B)=1
∑k )|(
=
==
i
i BvAP
1
1
9Học Máy – IT 4862
Các biến độc lập về xác suất (1)
„ Hai sự kiện A và B được gọi là độc lập về xác suất nếu 
xác suất của sự kiện A là như nhau đối với các trường 
hợp:
• Khi sự kiện B xảy ra, hoặc 
Khi kiệ khô ả h ặ• sự n B ng x y ra, o c
• Không có thông tin (không biết gì) về việc xảy ra của sự kiện B
Ví d„ ụ
•A: Tôi sẽ đi đá bóng vào ngày mai
•B: Tuấn sẽ tham gia trận đá bóng ngày mai 
•P(A|B) = P(A)
→ “Dù Tuấn có tham gia trận đá bóng ngày mai hay không cũng không 
ế ềảnh hưởng tới quy t định của tôi v việc đi đá bóng ngày mai.”
10Học Máy – IT 4862
Các biến độc lập về xác suất (2)
Từ định nghĩa của các biến độc lập về xác suất 
( | ) ( ) hú t th đ á l ật hP A B =P A , c ng a u ược c c u n ư sau
•P(~A|B) = P(~A)
•P(B|A) = P(B)
•P(A,B) = P(A). P(B)
•P(~A,B) = P(~A). P(B)
•P(A ~B) = P(A) P(~B), . 
•P(~A,~B) = P(~A). P(~B)
11Học Máy – IT 4862
Xác suất có điều kiện với >2 biến
„ P(A|B,C) là xác suất của A đối với (đã 
biết) à C B v 
„ Ví dụ
B C
• A: Tôi sẽ đi dạo bờ sông vào sáng mai
• B: Thời tiết sáng mai rất đẹp
C Tôi ẽ dậ ớ à á i
A
P(A|B C)• : s y s m v o s ng ma
• P(A|B,C): Xác suất của việc tôi sẽ đi dạo 
dọc bờ sông vào sáng mai, nếu (đã biết rằng) 
,
thời tiết sáng mai rất đẹp và tôi sẽ dậy sớm 
vào sáng mai
12Học Máy – IT 4862
Độc lập có điều kiện
„ Hai biến A và C được gọi là độc lập có điều kiện đối với 
biến B nếu xác suất của A đối với B bằng xác suất của A , 
đối với B và C
„ Công thức định nghĩa: P(A|B,C) = P(A|B) 
„ Ví dụ
• A: Tôi sẽ đi đá bóng vào ngày mai
• B: Trận đá bóng ngày mai sẽ diễn ra trong nhà
• C: Ngày mai trời sẽ không mưa
• P(A|B C) P(A|B), =
→ Nếu biết rằng trận đấu ngày mai sẽ diễn ra trong nhà, thì xác 
suất của việc tôi sẽ đi đá bóng ngày mai không phụ thuộc 
vào thời tiết 
13Học Máy – IT 4862
Các quy tắc quan trọng của xác suất
„ Quy tắc chuỗi (chain rule)
• P(A B) = P(A|B) P(B) = P(B|A) P(A), . .
• P(A|B) = P(A,B)/P(B) = P(B|A).P(A)/P(B)
• P(A,B|C) = P(A,B,C)/P(C) = P(A|B,C).P(B,C)/P(C) 
= P(A|B,C).P(B|C)
Độc lập về xác suất và độc lập có điều kiện„ 
• P(A|B) = P(A); nếu A và B là độc lập về xác suất
• P(A,B|C) = P(A|C).P(B|C); nếu A và B là độc lập có điều 
kiện đối với C
• P(A1,,An|C) = P(A1|C)P(An|C); nếu A1,,An là độc lập 
có điều kiện đối với C 
14Học Máy – IT 4862
Định lý Bayes
)(
)().|()|(
DP
hPhDPDhP =
• P(h): Xác suất trước (tiên nghiệm) của giả thiết (phân loại) h
• P(D): Xác suất trước (tiên nghiệm) của việc quan sát được 
dữ liệu D
• P(D|h): Xác suất (có điều kiện) của việc quan sát được dữ 
liệu D, nếu biết giả thiết (phân loại) h là đúng
• P(h|D): Xác suất (có điều kiện) của giả thiết (phân loại) h là 
đúng, nếu quan sát được dữ liệu D
¾Các phương pháp phân loại dựa trên xác suất sẽ sử 
dụng xác suất có điều kiện (posterior probability) này! 
15Học Máy – IT 4862
Định lý Bayes – Ví dụ (1)
Giả sử chúng ta có tập dữ liệu sau (dự đoán 1 người có chơi tennis)?
Ngày Ngoài trời Nhiệt độ Độ ẩm Gió Chơi tennis
N1 Nắng Nóng Cao Yếu Không
N2 Nắng Nóng Cao Mạnh Không
N3 Â Nó C Yế Cóm u ng ao u
N4 Mưa Bình thường Cao Yếu Có
N5 Mưa Mát mẻ Bình thường Yếu Có
ẻN6 Mưa Mát m Bình thường Mạnh Không
N7 Âm u Mát mẻ Bình thường Mạnh Có
N8 Nắng Bình thường Cao Yếu Không
ắ ếN9 N ng Mát mẻ Bình thường Y u Có
N10 Mưa Bình thường Bình thường Yếu Có
N11 Nắng Bình thường Bình thường Mạnh Có
N12 Âm u Bình thường Cao Mạnh Có
[Mitchell, 1997]
16Học Máy – IT 4862
Định lý Bayes – Ví dụ (2)
„ Dữ liệu D. Ngoài trời là nắng và Gió là mạnh
Giả thiết ( hâ l i) A h t h i t i„ p n oạ h. n a c ơ enn s
„ Xác suất trước P(h). Xác suất rằng anh ta chơi tennis (bất kể 
Ngoài trời như thế nào và Gió ra sao) 
„ Xác suất trước P(D). Xác suất rằng Ngoài trời là nắng và Gió
là mạnh
„ P(D|h). Xác suất Ngoài trời là nắng và Gió là mạnh, nếu biết 
rằng anh ta chơi tennis
P(h|D) Xác suất anh ta chơi tennis nếu biết rằng Ngoài trời„ . , 
là nắng và Gió là mạnh
→ Chúng ta quan tâm đến giá trị xác suất sau (posterior probability) 
à !n y
17Học Máy – IT 4862
Xác suất hậu nghiệm cựu đại (MAP)
„ 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ó xác suất hậu nghiệm 
cực đại (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)
18Học Máy – IT 4862
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
19Học Máy – IT 4862
Đánh giá khả năng có thể nhất (MLE)
„ 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 có 
thể 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 có thể (likelihood) của 
dữ liệu D đối với h
„ Giả thiết có khả năng nhất (maximum likelihood hypothesis)
)|(maxarg hDPhML =
Hh∈
20Học Máy – IT 4862
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!
21Học Máy – IT 4862
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ậ h t đó ỗi í d h đ biể diễ là• p ọc D_train, rong m v ụ ọc x ược u n 
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, thì 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 P ,...,, 21 ni
Cc
MAP zzzcc
i∈
=
)(
)().|,...,,(
maxarg 21 iin
C
MAP zzzP
cPczzzPc = (bởi định lý Bayes)
,...,, 21 nci∈
22Học Máy – IT 4862
Phân loại Naïve Bayes (2)
„ Để tìm được phân lớp có thể nhất đối với z
)().|,...,,(maxarg 21 iin
Cc
MAP cPczzzPc
i∈
= (P(z1,z2,...,zn) là 
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 ijiNB czPcPc )|().(maxarg
=∈ jCci 1
23Học Máy – IT 4862
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) c ∈C i
• 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 
ủ iá t ị th ộ tí h đó đối ới ột hâ lớ P( | )c a g r u c n v m p n p ci: xj ci
„ 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 c ∈C tính giá trị của biểu thức: i , 
∏
=
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 cxPcPc* )|().(maxarg
=∈ jCci 1
24Học Máy – IT 4862
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
14 Old Medium No Excellent No
/~cse634/lecture_notes/0
7classification.pdf
25Học Máy – IT 4862
Phân lớp Naïve Bayes – Ví dụ (2)
„ Biểu diễn bài toán phân loại
= (Age=Y Income=M di Student=Y Credit Rating=F i )•z oung, e um, es, _ a r
• 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=Medium|c1) = 4/9; P(Income=Medium|c2) = 2/5
• 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_ _
26Học Máy – IT 4862
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!
27Học Máy – IT 4862
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 PP
„ Giải pháp: Sử dụng phương pháp Bayes để ước lượng P(xj|ci)
.
1
=
=j
iji cxc
• 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
28Học Máy – IT 4862
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)|(li ⎟⎞⎜⎛∏n Pm
1
=⎟⎠⎜⎝ =∞→ j ijn
cx
„ 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
29Học Máy – IT 4862
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( )( ) TdtdnctP 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 d )tn
ik mcDd Tt mk
+∈ ∈_ , k
30Học Máy – IT 4862
Phân loại văn bản bằng NB (2)
„ Giai đoạn phân lớp đối với một văn bản mới d
• Từ văn bản d trích ra tập T d gồm các từ khóa (keywords) t đã , _ j 
được định nghĩa trong tập T (T_d ⊆ T)
• Giả sử (assumption). Xác suất từ khóa tj xuất hiện đối với lớp 
là độc lập đối với vị trí của từ khóa đó trong văn bảnci 
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
j
ctPcP
_
)|().(
Phâ lớ ă bả h ộ à lớ *• n p v n n d t u c v o p c
∏
∈∈
=
dTt
iji
Cci
ctPcPc* )|().(maxarg
j _
31Học Máy – IT 4862
Phân loại Naïve Bayes – Tổng kết
„ Một trong các phương pháp học máy được áp dụng phổ biến 
nhất trong thực tế
„ Dựa trên định lý Bayes
„ Việc phân loại dựa trên các giá trị xác suất của các khả năng 
xảy ra của các giả thiết (phân loại) 
„ Mặc dù đặt giả sử về sự độc lập có điều kiện của các thuộc 
tính đối với các phân lớp, nhưng phương pháp phân loại 
N ï B ẫ th đ á kết ả hâ l i tốt ta ve ayes v n u ược c c qu p n oạ rong 
nhiều lĩnh vực ứng dụng thực tế
„ Khi nào nên sử dụng?
• Có một tập huấn luyện có kích thước lớn hoặc vừa
• Các ví dụ được biểu diễn bởi một số lượng lớn các thuộc tính
• Các thuộc tính độc lập có điều kiện đối với các phân lớp 
32Học Máy – IT 4862
Cực đại hóa kỳ vọng – EM (1)
„ Trong một số bài toán học máy, dữ liệu chỉ có thể quan 
sát được một phần 
•Đối với một thuộc tính, giá trị của nó không quan sát 
được (unobservable) – nhưng chúng ta biết dạng tổng 
quát của hàm phân bố xác suất đối với thuộc tính đó
•Đối với một thuộc tính, giá trị của nó có lúc quan sát 
được có lúc không quan sát được (vd: thuộc tính 
thiếu giá trị)
• Giá trị của thuộc tính phân loại (nhãn lớp) là không 
biết
33Học Máy – IT 4862
Cực đại hóa kỳ vọng – EM (2)
„ Phương pháp học EM thường được sử dụng trong 
những bài toán tồn tại các biến (thuộc tính) không quan 
sát được (ẩn)
• EM tìm các đánh giá có thể nhất (maximum likelihood 
ốestimates) của các tham s trong một mô hình xác 
suất phụ thuộc vào các biến không quan sát được 
(unobserved variables)
• Không sử dụng tốc độ học (vd: như phương pháp học 
mạng nơ-ron nhân tạo)
ố•Đảm bảo tìm được một giá trị t i ưu cục bộ (a local 
optimum) của xác suất likelihood, cùng với các giá trị 
ước lượng được của các biến không quan sát được 
34Học Máy – IT 4862
EM – Phát biểu bài toán (1)
„ Xét một tập dữ liệu gồm m ví dụ X={x1,,xm}, trong đó mỗi ví 
dụ có một phần (một tập các thuộc tính) quan sát được và một 
ầph n không quan sát được
• Phần quan sát được: Y = {y1,,ym}
• Phần không quan sát được: Z = {z1,,zm}
• Đối với mỗi ví dụ: xi = yi ∪ zi
„ Tập dữ liệu X được sinh ra (generated) bởi một hàm phân bố 
xác suất cơ sở P(X|θ) và hàm phân bố này phụ thuộc vào – , 
(được biểu diễn bằng) một tập các tham số θ (chưa biết, và sẽ 
được ước lượng!)
„ Phần dữ liệu không quan sát được Z được xem như một biến 
ngẫu nhiên mà hàm phân bố xác suất của nó phụ thuộc vào
• Các tham số chưa biết giá trị θ, và
• Phần dữ liệu quan sát được Y
35Học Máy – IT 4862
EM – Phát biểu bài toán (2)
„ Phương pháp EM lặp lại 2 bước sau đây
• Tính toán giá trị kỳ vọng (Expectation step). Với các giá trị được ước 
ố ếlượng hiện tại của các tham s θ, tính toán các giá trị kỳ vọng của các bi n 
không quan sát được
• Cực đại hóa (Maximization step). Với các giá trị kỳ vọng được gán cho các 
biến không quan sát được (tính ở bước trên E step) tính toán lại các – - , 
đánh giá có thể nhất (maximum likelihood estimates) của các tham số θ
„ Ký hiệu E[P(X|θ)] là giá trị kỳ vọng của khả năng có thể 
(likelihood) của tập dữ liệu X đối với các giá trị ước lượng hiện , 
tại của các tham số θ
• Giá trị (trung bình) kỳ vọng được tính toán dựa trên các giá trị có thể của 
phần dữ liệ không q an sát đ ợc Z u u ư ,
• Gắn trọng số (weighting) mỗi giá trị có thể với xác suất xảy ra của giá trị đó
„ Giải thuật EM tìm các đánh giá có thể nhất (maximum likelihood 
estimates) θ* giúp cực đại hóa (cục bộ) giá trị E[P(X|θ)]
36Học Máy – IT 4862
Cực đại hóa kỳ vọng – Giải thuật
„ Ký hiệu θ(i) là các giá trị ước lượng của các tham số θ tại 
bước lặp thứ i
„ Ký hiệu Q(θ|θ(i)) là một hàm của θ, đối với các đánh giá 
(ước lượng) hiện thời θ(i) và phần dữ liệu quan sát được Y
(của tập dữ liệu X):
Q(θ|θ(i))= E[ln P(X|θ)|θ(i),Y]
„ Giải thuật EM tổng quát:
Initialize θ(0), Thres_Val, i=0
Do
i=i+1
Compute Q(θ|θ(i)) // Bước tính kỳ vọng (E-step)
θ(i+1) = argmaxθ Q(θ|θ(i)) // Bước cực đại hóa (M-step)
Until Q(θ(i+1)|θ(i))-Q(θ(i)|θ(i-1))≤Thres Val // Không có cải thiện _ 
Return θ(i+1)
37Học Máy – IT 4862
Phân loại văn bản bằng EM (1)
„ Trong thực tế, chúng ta thường có một tập nhỏ các văn bản có 
nhãn lớp và một tập lớn hơn các văn bản không có nhãn lớp
Tậ á ă bảp c c v n n D = DL ∪ DU
•DL: Tập các văn bản có nhãn lớp
•DU: Tập các văn bản không có nhãn lớp
|DL| << |DU|• 
„ Mục tiêu: Gán nhãn lớp chính xác cho các văn bản trong tập DU
„ Tại sao chúng ta không xây dựng (học) một bộ phân loại dựa 
trên tập các văn bản có nhãn trong DL, và sau đó sử dụng bộ 
phân loại đó để phân loại các văn bản không có nhãn?
→Cần khai thác các thông tin ẩn trong tập DU để nâng cao hiệu năng 
của bộ phân loại học được
• Khai thác các phân bố kết hợp của các từ khóa đối với các phân lớp
• Khai thác sự tương đồng giữa các văn bản (vd: một văn bản có nhãn 
à ột ă bả khô ó hã ù hứ ột ố á từ khó )v m v n n ng c n n c ng c a m s c c a
38Học Máy – IT 4862
Phân loại văn bản bằng EM (2)
„ Trong bài toán phân loại văn bản
• Các tham số chưa biết giá trị là: P(ci) và P(tj|ci)
ế ủ ả• Bi n không quan sát được là: nhãn lớp c a các văn b n trong DU
„ Giải pháp: Kết hợp EM với phân loại Naïve Bayes
„ Sử dụng tập dữ liệu có nhãn DL và phương pháp phân loại Naïve 
Bayes để khởi tạo các giá trị của các tham số chưa biết giá trị: 
P(0)(ci) và P(0)(tj|ci)
Ở b ớ lặ thứ k„ ư c p 
• Bước tính kỳ vọng (E-step). Đối với mỗi văn bản không có nhãn dU
và mỗi lớp ci, sử dụng các giá trị ước lượng hiện tại P(k-1)(ci) và 
(k 1)( | ) à h há hâ l i N ï B để đá hP - tj ci v p ương p p p n oạ a ve ayes n 
giá P(k)(ci|dU): ∏ −−−− == t ijkikikiUkUk j ctPcPcPcdPdcP )|().()().|()|( )1()1()1()1()( ∑ ∈ −−− Cc qkqUkUki q cPcdPdP )().|()( )1()1()1(
39Học Máy – IT 4862
Phân loại văn bản bằng EM (3)
„ Ở bước lặp thứ k (tiếp tục)
• Bước cực đại hóa (M-step). Đối với mỗi từ khóa tj và mỗi phân 
lớ đá h iá l i á th ố ủ hâ bố á ất ( ủ t àp ci, n g ạ c c am s c a p n x c su c a o n 
bộ tập văn bản D)
∑ ∑
∑
∈ ∈
∈
+
+=
Dd Tt qi
k
jDd i
k
ij
k
q
tdndcPT
tdndcP
ctP
),().|(||
),().|(1
)|( )(
)(
)(
∑ ∈= Dd ikik dcPDcP )|(|| 1)( )()(
-Đóng góp của giá trị của tần suất xuất hiện từ khóa n(d t ) trong văn , j 
bản d đối với phân lớp ci được gán trọng số (weighted) bởi P(ci|d) – giá 
trị xác suất của văn bản d thuộc vào lớp ci
-Đối với một văn bản có nhãn d (∈DL) và nhãn lớp gắn với nó cd,
P(ci|d)=1 if ci≡cd, and P(ci|d)=0 if ci≠cd
„ Lặp lại 2 bước (E-step, M-step) cho đến khi thỏa mãn đk hội tụ
Ví dụ: % của thay đổi về nhãn lớp được gán cho các văn bản không có 
nhãn (trong DU) giữa 2 bước lặp kế tiếp nhỏ hơn một giá trị ngưỡng.
40Học Máy – IT 4862
Các phương pháp học dựa trên xác suất
„ Dựa trên lý thuyết xác suất
Nhằm học (xấp xỉ) một mô hình xác suất sinh ra dữ liệu„ 
„ Định lý Bayes đóng vai trò trung tâm
„ Kết hợp tri thức tiên nghiệm (các xác suất tiên nghiệm) 
với dữ liệu quan sát được
„ Tính toán trực tiếp các xác suất xảy ra đối với các giả thiết
(phân lớp)
„ Cung cấp các giải thuật học máy có tính ứng dụng thực
ế h hâ l i N ï B h ặ EMt , n ư p n oạ a ve ayes o c
„ Cung cấp cơ sở lý thuyết (khái niệm) để hiểu và đánh giá
các giải thuật học máy khác
41Học Máy – IT 4862