BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------
Vũ Văn Tú
PHƯƠNG PHÁP SUY DIỄN NHANH CHO BÀI TOÁN
CỰC ĐẠI HOÁ PHÂN PHỐI HẬU NGHIỆM
NGƯỜI HƯỚNG DẪN:
TS. Thân Quang Khoát
Hà Nội – 10/2018
2
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn : Vũ Văn Tú
Đề tài luận văn: Phương pháp suy diễn nhanh cho bài toán cực đại hoá phân phối
hậu nghiệm
Chuyên ngành: Công nghệ thông tin – Thạc sĩ kĩ thuật
Mã số SV: CB160544
Tác giả, Người hướng dẫ n khoa học và Hội đồng chấm luận văn xác nhận
tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày 27/10/2018 với
các nội dung sau:
- Chỉnh sửa lại chương mục đối với luận văn.
- Rút gọn số lượng chương mục của luận văn.
Ngày 30 tháng 10 năm 2018
Giáo viên hướng dẫn Tác giả luận văn
CHỦ TỊCH HỘI ĐỒNG
3
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Mục lục Trang
Lời cam đoan .................................................................................................................................. 4
Danh sách các từ viết tắt và thuật ngữ ............................................................................................ 6
Danh sách các kí hiệu dùng trong luận văn .................................................................................... 6
Danh sách hình vẽ ........................................................................................................................... 7
Danh sách bảng ............................................................................................................................... 7
MỞ ĐẦU ........................................................................................................................................ 8
Chương 1 - TỔNG QUAN .............................................................................................................. 9
Chương 2 - CƠ SỞ LÝ THUYẾT LIÊN QUAN .......................................................................... 11
2.1 Các kiến thức về xác suất thống kê ............................................................................................11
2.1.1 Phân phối Multinomial ......................................................................................................11
2.1.2 Phân phối Dirichlet ............................................................................................................12
2.2 Mô hình đồ thị xác suất ..............................................................................................................12
2.3 Các thuật toán tối ưu cơ bản trong học máy ...............................................................................15
2.3.1 Gradient Descent ...............................................................................................................17
2.3.2 Expectation-Maximization ................................................................................................18
2.3.3 Conditional Gradient Descent (Frank Wolfe) ....................................................................20
Chương 3 - MÔ HÌNH CHỦ ĐỀ VÀ BÀI TOÁN CỰC ĐẠI HOÁ PHÂN PHỐI HẬU NGHIỆM
TRONG MÔ HÌNH CHỦ ĐỀ ....................................................................................................... 23
3.1 Mô hình chủ đề Latent Diriclet Allocation [1] ...........................................................................23
3.2 Bài toán suy diễn trong mô hình chủ đề .....................................................................................28
3.3 Thuật toán Online Maximum a Posteriori Estimation (OPE) ....................................................30
Chương 4 – THUẬT TOÁN CẢI TIẾN GENERALIZED ONLINE MAXIMUM A
POSTERIORI ESTIMATION (G-OPE) ....................................................................................... 34
Chương 5 – KẾT QUẢ THỰC NGHIỆM .................................................................................... 37
5.1 Thuật toán Online-OPE ..............................................................................................................37
5.2 Các độ đo thử nghiệm .................................................................................................................38
5.2.1 Độ đo xác suất dự đoán (Log Predictive Probability) .......................................................38
5.2.2 Độ đo chất lượng chủ đề (Normalized Pointwise Mutual Information) ............................39
5.3 Dữ liệu và các tham số khi thử nghiệm ......................................................................................40
5.4 G-OPE với các tham số ! khác nhau ..........................................................................................41
5.5 So sánh Online-GOPE với các thuậ t toán học khác cho LDA ...................................................43
KẾT LUẬN ................................................................................................................................... 46
TÀI LIỆU THAM KHẢO ............................................................................................................ 47
4
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Lời cam đoan
Tôi – Vũ Văn Tú – cam kết luận văn này là công trình nghiên cứu của bản thân tôi
dưới sự hướng dẫn của TS. Thân Quang Khoát.
Các kết quả nghiên cứu trong luận văn là trung thực, không phải sao chép của bất
cứ công trình đã được công bố nào khác. Tất cả các trích dẫn đều được tham chiếu rõ
ràng.
Hà Nội, ngày 7 tháng 9 năm 2018
Tác giả luận văn
Vũ Văn Tú
Xác nhận của người hướng dẫn
5
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
LỜI CẢM ƠN
Đầu tiên, em xin được gửi lời cảm ơn chân thành đến các thầy, cô giáo thuộc trường
đại học Bách Khoa Hà Nội, đặc biệt là các thầy cô trong viện Công nghệ thông tin và truyền
thông. Các thầy cô đã trang bị cho em những kiến thức quý báu trong thời gian em học tập
tại trường. Đồng thời, em cũng xin gửi lời cảm ơn đến các thầy cô trong Data Science Lab,
đặc biệt là TS Thân Quang Khoát, NCS Bùi Thị Thanh Xuân, đã tận tình hướng dẫn giúp
đỡ em hoàn thành luận văn này.
6
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Danh sách các từ viết tắt và thuật ngữ
LDA
Latent Dirichlet Allocation
Dir
Phân phối Dirichlet
VB
Variational Bayesian
CVB
Collapsed Variational Bayesian
CGS
Collapsed Gibbs Sampling
MAP
Maxium A Posteriori
LPP
Log Predictive Probability
NPMI
Normalized Poitwise Mutual Information
Danh sách các kí hiệu dùng trong luận văn
"
Hàm Digamma
#
Hàm Gamma
$
Kí hiệu “được cho là”
%
Tốc độ học hai tham số &' (
)
Vector tỉ lệ các chủ đề của một văn bản
*
Ma trận +,-, mỗi hàng của ma trận là phân phối chủ đề theo các từ
+
Số lượng chủ đề
.
/
Từ thứ 0 trong văn bản
1
/
Chủ đề của từ thứ 0 trong văn bản
2
Tham số của phân phối tiên nghiệm cho *
3
Tham số của phân phối tiên nghiệm cho )
4
Tham số của phân phối biến phân ứng với )
5
Tham số của phân phối biến phân ứng với 6
7
Tham số của phân phối biến phân ứng với *
V
Tập hợp từ điển, bao gồm các từ 89 : 9;' <' = = -
>' ?
Văn bản (bao gồm các từ)
9999@
A
Số lượng từ thứ 8 trong văn bản >
7
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Danh sách hình vẽ Trang
Hình 1: Ví dụ về đồ thị xác suất ....................................................................................... 13!
Hình 2:Ví dụ về một đồ thị xác suất có hướng ................................................................. 14!
Hình 3:Cách biểu diễn thu gọn trong mô hình đồ thị xác suất ......................................... 15!
Hình 4:Minh hoạ thuật toán Gradient Descent ................................................................. 18!
Hình 5:Minh hoạ thuật toán Expectation-Maximization .................................................. 20!
Hình 6:Minh họa thuật toán Frank-Wolfe ........................................................................ 21!
Hình 7:Kết quả 10 chủ đề học được từ mô hình LDA ...................................................... 24!
Hình 8:Tỉ lệ chủ đề của một văn bản mẫu trong mô hình LDA ....................................... 25!
Hình 9:Biểu diễn mô hình sinh LDA ................................................................................ 27!
Hình 10:Minh họa hoạt động của thuật toán OPE bằng cách xây dựng dãy hàm xấp xỉ
ngẫu nhiên B
C
D ' B
E
D ' B
F
GDH … tiến dần về IGDH ................................................ 32!
Hình 11:G-OPE trên bộ NYT với các tham số p khác nhau ............................................. 42!
Hình 12:G-OPE trên bộ Pubmed với các tham số p khác nhau ........................................ 43!
Hình 13:So sánh các thuật toán suy diễn trên bộ NYT ..................................................... 44!
Hình 14:So sánh các thuật toán suy diễn trên bộ Pubmed ................................................ 45!
Danh sách bảng Trang
Bảng 1: Thống kê về tập dữ liệu sử dụng trong thí nghiệm ............................................. 40!
Bảng 2: Giá trị p tốt nhất cho từng độ đo trên từng bộ dữ liệu ........................................ 42!
8
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
MỞ ĐẦU
Tối ưu là một trong những nền tảng cơ bả n và quan trọng trong lĩnh vực học máy. Bài
toán cốt lõi trong mỗi mô hình học máy đều là đưa ra một hàm mục tiêu để tối ưu. Với các
bài toán tối ưu lồi, ta đã có nhiều công cụ mạnh để giải quyết hiệu quả. Tuy nhiên, các bài
toán tối ưu trong học máy chủ yếu là các bài toán tối ưu không lồi, do đó không tồn tại một
thuật toán hiệu quả để áp dụng cho hầu hết mọi bài toán. Thông thường, người ta sử dụng
các thuật toán xấp xỉ ngẫu nhiên để tìm cực trị đị a phương cho các bài toán này. Trong luận
văn này, em trình bày một phương pháp ngẫu nhiên để giải quyết bài toán cực đại hóa phân
phối hậu nghiệm Maximum a Posteriori (MAP). Bài toán cực đại hóa phân phối hậu nghiệ m
là bài toán thường gặp trong học máy, dùng để ước lượng tham số cho mô hình. Bài toán
MAP trong các mô hình học máy thường là bài toán tối ư u không lồi. Luận văn đề xuất
phương pháp Generalized Online Maximum a Posteriori Estimation (G-OPE) [21], là một
phương pháp cải tiến và tổng quát hóa của thuật toán Online Maximum a Posterior
Estimation (OPE). OPE [6] đã được áp dụng hiệu quả trong mô hình chủ đề Latent Dirichlet
Allocation (LDA) [1] cả về mặt lí thuyết lẫn kết quả thực tế. G-OPE tổng quát hơn OPE,
đồng thời kết quả thực nghiệ m đã chứng minh G-OPE cho kết quả tốt hơn OPE và các
phương pháp suy diễn khác của trong mô hình LDA. Ngoài ra, ý tưởng thiết kế thuật toán
ngẫu nghiên G-OPE có khả năng mở rộng áp dụng trong các bài toán MAP khác ngoài các
mô hình chủ đề.
9
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Chương 1 - TỔNG QUAN
Ngày nay, học máy là lĩnh vực đang được nghiên cứu và phát triển rất mạnh mẽ trong
ngành khoa họ c máy tính. Các thuật toán trong học máy là nền tảng cơ bản cho các bài
toán xử lí, phân tích dữ liệu lớn. Các mô hình học máy thường đề xuất một hàm mục tiêu
dựa trên các giả thiết sử dụng các công cụ trong xác suất thống kê, sau đó sử dụng các công
cụ trong tối ưu để tìm cực trị cho hàm mục tiêu này. Với rất nhiều bài toán, hàm mục tiêu
là các hàm không lồi, ví dụ bài toán K-Means [16], các hàm mục tiêu của mô hình chủ đề
[1, 20] … Các thuật toán thường sử dụ ng dựa trên Gradient Descent (GD) hay Coordinate
Descent. Các thuật toán này là các phương pháp lặp, nếu không có tính ngẫu nhiên thì kết
quả là các điểm cực trị địa phương và chất lượng thuật toán phụ thuộc rấ t lớn vào điểm
khởi tạo ban đầu. Các tác giả đã nghiên cứu, cải tiến các phương pháp này, bằng cách thêm
tính ngẫu nhiên vào các thuật toán để làm cho các thuật toán vượt ra khỏi cực trị địa phương,
đi đến cực trị toàn cục. Các thuật toán ngẫu nhiên như Stochastic Gradient Descent (SGD)
làm việc khá hiệu quả trong các bài toán thực tế. Tuy nhiên, còn rất nhiều thách thức trong
giải quyết các bài toán tối ưu không lồi như vấn đề về sự hội tụ của thuậ t toán, vấn đề về
điểm yên ngựa hay cực trị địa phương.
Trong lĩnh vự c thống kê hay học máy, bài toán cực đại hóa phân phối hậu nghiệm
(Maximum a Posteriori - MAP) được quan tâm trong rấ t nhiều mô hình khác nhau. MAP
được sử dụng để ước lượng một tham số nào đó, dựa trên giả thiết về một phân phối tiên
nghiệm cho tham số đó (prior) và các dữ liệu quan sát được (likelihood). Ví dụ, ta quan sát
được dữ liệu J và muốn ước lượng tham số D từ dữ liệu này. Đầu tiên, ta giả sử D có phân
phối tiên nghiệm đã biết trước K D . Ta cũng giả thiết về phân phối của dữ liệu J khi biết
tham số D là K J D . Dựa vào định lí Bayes, ta có phân phối hậu nghiệ m (posteriori)
K D J :
L M 9N9L J D
L O
. Khi đó D được ước lượng là:
D
N
: PQRSPT
M
9K D J : PQRSPT
M
9K D N KG JUDH
10
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Ta có thể thấy, hàm mụ c tiêu MAP bao gồm hai thành phần là prior K D 9và likelihood
KGJUDH. Thành phần tiên nghiệm K D là đại lượng đặc trưng cho tri thức (giả thiết) của
ta về tham số. Thành phần likelihood KGJUDH là đại lượng đặc trưng cho tri thức quan sát
được từ dữ liệu. Tham số D ước lượng được khi cực đại hóa phân phối hậu nghiệm là tri
thức ta thu được kết hợp từ hai thành phần trên.
Trong luận văn này, em sẽ nghiên cứu giải quyết bài toán MAP trong các mô hình chủ
đề và một phương pháp tối ưu ngẫu nhiên để giải quyết nó. Mô hình chủ đề được sử dụng
thành công trong việc phân tích dữ liệu văn bản. Mô hình chủ đề giúp ta phân tích được
các chủ đề ẩn trong các văn bản, cũng như những từ liên quan với nhau cùng nói về một
chủ đề ẩn nào đó. Vấn đề chính khi nghiên cứu các mô hình chủ đề là bài toán suy diễn.
Bài toán suy diễn trả lời hai câu hỏi: chủ đề của các từ là gì và văn bả n này nói về những
chủ đề nào. Tuy nhiên, bài toán suy diễn cho mô hình chủ đề là bài toán NP-khó [24]. Do
đó các tác giả không giải trực tiếp bài toán đó mà giải bài toán xấp xỉ của bài toán gốc. Bài
toán MAP trong mô hình chủ đề là một cách để giải quyết bài toán suy diễn này và đây là
bài toán tối ưu không lồi. Luận văn này đưa ra một phương pháp xây dựng các thuật toán
ngẫu nhiên để giải quyết bài toán MAP cho mô hình chủ đề, đề xuất một cách thiết kế các
thuật toán ngẫu nhiên có chủ đích, dựa vào cách lấy mẫu ngẫu nhiên của phần tiên nghiệm
(prior) và phần likelihood trong hàm mục tiêu MAP.
Bố cục của luận văn được trình bày như sau: phần 2 trình bày các kiến thức liên quan
đến xác suất, thống kê, công cụ đồ thị xác suất, các thuật toán tối ưu cơ bả n như Gradient
Descent, Frank-Wolfe. Phần 3 sẽ trình bày về mô hình chủ đề Latent Dirichlet Allocation
(LDA) [1] và bài toán suy diễn bằng MAP cho mô hình LDA. Phần 4 trình bày về thuật
toán đề xuất là Generalized Online Maximum a Posteriori Estimation (G-OPE). Phần 5 là
kết quả thực nghiệm. Cuối cùng, phần 6 là kết luận và hướng nghiên cứu trong tương lai.
11
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Chương 2 - CƠ SỞ LÝ THUYẾT LIÊN QUAN
Trong phần này, em xin trình bày các kiến thức liên quan đế n xác suất thống kê và tối
ưu được sử dụng trong luận văn. Đầu tiên, em xin trình bày về các hàm phân phối sử dụng
trong mô hình chủ đề LDA, mô hình đồ thị xác suất được sử dụng để biểu diễn các mô hình
chủ đề và ý tưởng xây dựng các thuật toán tối ư u hay được sử dụng để làm nền tảng so
sánh với thuật toán đề xuất G-OPE.
2.1 Các kiến thức về xác suất thống kê
2.1.1 Phân phối Multinomial
Giả sử một người thực hiện thí nghiệm lấy ra 0 quả bóng từ một túi gồm các quả bóng có
V màu khác nhau, trả lại bóng sau vào túi sau khi lấy một quả bóng. Các quả bóng từ các
màu khác nhau là tương đương. Xét các biến ngẫu nhiên là số lượng quả bóng từ các màu
khác nhau lấy được W
X
9GY9 : 9;' < Z VH và xác suất để lấy được quả bóng màu Y là !
X
GY9 :
9;' < Z VH= Hàm phân bố xác suất của các biến ngẫu nhiên W
X
là :
! W
C
: T
C
9[9W
E
: T
E
[ Z [W
\
: T
\
: 9
0]
T
C
] Z T
\
]
!
C
^
_
Z !
\
^
`
9.ab0 9 9 T
X
\
XcC
: 0
d99efabQ.Ygb
Viết dưới dạng hàm Gamma:
! W
C
: T
C
9[9W
E
: T
E
[ Z [W
\
: T
\
: 9
#G T
XX
h ;H
#GT
X
h ;H
X
9 !
X
^
i
\
XcC
Kí hiệu #GTH là hàm Gamma với biế n T. -jY9T k l9fam9# T : T n ; ].
Tính chất của phân phối Multinomial:
o W
X
: 0 N !
X
9-PQ W
X
: 0 N !
X
N G ; n !
X
H
Phân phối Multinomial được sử dụng để mô hình hóa các thí nghiệm ngẫu nhiên, trong đó
kết quả của thí nghiệm là một mẫu có thể thuộc một trong nhiề u lớp với xác suất đã biết.
12
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
2.1.2 Phân phối Dirichlet
Simplex +-chiều được định nghĩa là p
q
: rs k t
q
u T
X
v d9wY : ;' < Z +x9 T
X
q
XcC
: ;y.
Biến ngẫu nhiên W : W
C
' W
E
Z W
q
k p
q
được gọi là tuân theo phân phối Dirichlet với bậc
+ v <, và các tham số z
X
v d9Y : ;' < Z +, kí hiệu là JYQ z ' {jY9Gz : Gz
C
' Z z
q
H nếu
hàm mật độ của nó có dạng :
I T
C
' Z T
q
x z
C
' Z z
q
: 9
|G}
i
H
~
`•_
|G }
i
~
`•_
H
T
X
}
i
€C
q
XcC
Một số tính chất của phân phối Dirichlet :
Đặt z
•
: z
\
q
\cC
, ta có :
o W
X
:
z
X
z
•
9
-PQ W
X
:
z
X
z
•
n z
X
z
•
E
z
•
h ;
9
o ‚ƒ„ W
X
: " z
X
n "Gz
•
H
Với9" T 9 là hàm Digamma.
Phân phố i Dirichlet thư ờng đượ c sử dụng để làm phân phối tiên nghiệm cho các
phân phối Multinomial trong các mô hình thống kê Bayesian.
2.2 Mô hình đồ thị xác suất
Mô hình đồ thị xác suất (graphical models) là công cụ để biểu diễn các biến ngẫu
nhiên. Trong đó các đỉ nh của đồ thị là các biến ngẫu nhiên, các cạnh của đồ thị biểu diễn
sự phụ thuộc lẫn nhau của các biến ngẫu nhiên. Cả đồ thị biểu diễn một phân phối đồng
thời của tất cả các biến ngẫu nhiên đó. Trong nhiều mô hình thống kê, khi số lượng các
biến ngẫu nhiên lớn và sự phụ thuộc của các biến ngẫu nhiên nhiều thì đồ thị xác suất là
công cụ hữ u hiệu để biểu diễn toàn bộ mô hình. Đồ thị xác suất được sử dụng nhiều trong
13
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
lý thuyết xác suất và thống kê, trong đó đặc biệt là trong thống kê Bayesian và trong học
máy.
Hình 1 là ví dụ đơn giản về mô hình đồ thị xác suất biểu diễn hệ thống dự đoán thời tiết
để xem cỏ có bị ướt hay không. Biến Cloudy biểu diễn bầu trời có đang nhiều mây hay
không với xác suất nhiều mây và không nhiều mây bằng nhau và đều bằng 0.5. Biến
Sprinkler biểu diễn trời có mù sương hay không, biến này phụ thuộc vào biến Cloudy. Nếu
trời nhiều mây (Cloudy = True) thì xác suất để trời mù sương (Sprinkler = True) là 0.9 và
trời không mù sương (Sprinkler = False) là 0.1. Nếu trời không nhiều mây (Cloudy = False)
thì xác suất để trời mù sương và trời không mù sương bằng nhau. Tương tự như vậy với
biến trời mưa (Rain). Biến Rain phụ thuộc vào biến Cloudy. Cuối cùng là biế n cỏ có ướt
hay không (WetGrass). Biến WetGrass phụ thuộc vào cả 2 biến Sprinkler và Rain với xác
suất trong hình 1.
Hình 1: Ví dụ về đồ thị xác suất
14
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
Có hai loại mô hình đồ thị xác suất là đồ thị có hướng và đồ thị vô hướng. Các mô
hình đồ thị vô hướng điển hình là Markov networks hay Markov Random Fields, được sử
dụng phổ biến trong các lĩnh vực như vật lí. Các mô hình đồ thị có hướng có nhiều dạng:
Bayesian networks, belief networks, các mô hình sinh, mô hình nhân quả… được sử dụng
phổ biến trong lĩnh vực trí tuệ nhân tạo và học máy. Trong luậ n văn này, em tìm hiểu các
mô hình đồ thị có hướng liên quan đến các mô hình sinh.
!
Hình 2:Ví dụ về một đồ thị xác suất có hướng
Hình 2 là một ví dụ về một đồ thị có hướng với 7 đỉnh biểu diễn các biến ngẫu nhiên,
các cạnh biểu diễn quan hệ cha con trong lý thuyế t đồ thị và biểu diễn quan hệ phụ thuộc
của các biến ngẫu nhiên. Nế u có cạnh nối từ đỉnh A sang đỉnh B ta nói A sinh ra B, hay B
phụ thuộc A. Trong hình 2, biến ngẫu nhiên T
…
phụ thuộc vào T
C
' T
E
' T
F
. Ta gọi T
…
là đỉnh
con, T
C
' T
E
' T
F
là các đỉnh cha của đỉnh A.
Toàn bộ đồ thị này biểu diễn hàm phân phối đồng thời của các biến ngẫu nhiên là :
! T : 9! T
C
! T
E
! T
F
! T
…
T
C
' T
E
' T
F
!GT
†
UT
…
H!GT
‡
UT
…
' T
ˆ
H
Kí hiệu ‰GTH là tập các đỉnh cha của đỉnh T thì một đồ thị xác suất với + node
T
C
' T
E
' Z T
q
biểu diễn một hàm phân phối đồng thời:
15
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
! T : 9 !GT
\
U‰ T
\
H
q
\cC
Để thuận tiện cho việc biểu diễn đồ thị , ta có các biểu diễn gộp các biến ngẫu nghiên
cùng sinh ra từ một biến cha, sử dụng hình chữ nhật như sau (hình 3):
...
X
Y$
Y$ Y$
X
Y$
Hình 3:Cách biểu diễn thu gọn trong mô hình đồ thị xác suất
Mô hình đồ thị xác suất rất thích hợp để biểu diễn khái niệm độc lập có điều kiện trong
lí thuyết xác suất. Xét 3 biến ngẫu nhiên P' Š' ‹ , ta nói P' Š độc lập với điều kiện ‹ nếu :
! P9 9Š' ‹ : ! P9 ‹H
Khi đó ta kí hiệu : P9 Œ Š9U9‹=
Trong đồ thị, các biến ngẫu nhiên quan sát được được kí hiệu bằng các hình tròn in
đậm, các biến ẩ n (hay các biến không quan sát được) được kí hiệu bằng các hình tròn không
in đậm.
Các kiến thức trong mục này được tham khảo trong [15].
2.3 Các thuật toán tối ưu cơ bản trong học máy
Trong mục này, em xin trình bày về ý tưởng chung của một số thuật toán tối ưu lặp
hay gặp trong học máy. Tối ưu là một trong những lĩnh vực quan trọng của học máy. Trong
mỗi mô hình, tác giả đều giải quyết một bài toán tối ưu nào đó, thông qua các hàm mục
tiêu cụ thể. Tùy vào tính chất của từng hàm mục tiêu mà ta chọn các phương pháp tối ưu
16
Học viên thực hiện: Vũ Văn Tú, CB160544, Lớp: Thạc sĩ CNTT 2016B
khác nhau. Các hàm mục tiêu thườ ng phức tạp, nên ta không tìm được công thức tường
minh để tính ra kết quả trực tiếp mà phải sử dụng các phương pháp lặp để xấp xỉ nghiệm
mong muốn tìm kiếm.
Bài toán tối ưu là: •Ž•
•k‘
IGTH hoặc •’“
•k‘
IGTH. Phương pháp lặp để tìm kiếm nghiệm
T
N
tối ưu có sơ đồ chung như sau:
Bước 1: Khởi tạo giá trị T
C
k J bất kì
Bước 2: Lặp cho đến khi hội tụ
Tính T
/”C
: 9RGT
/
' T
/€C
' Z T
C
H
Giá trị T
/
cuối cùng thu được là giá trị T
N
xấp xỉ cần tìm.
Các thuật toán tối ưu khác nhau ở cách xây dựng hàm RGTH. RGTH là công thức cập
nhật T
/”C
theo các biến T
/
' T
/€C9
' Z T
C
đã tính ở bước trước, để dãy số T
/
hội tụ về T
N
.
Thông thường ta thiết kế thuật toán với T
/”C9
chỉ phụ thuộc vào T
/
. Để có công thức cập
nhật RGT
/
H, tại mỗi bước lặp, ta xấp xỉ IGTH bằng một hàm nào đó aGTH dễ tính hơn và có
tính chất IGT
/
H 9 : aGT
/
H, sau đó minimize (hoặc maximize) aGTH bằng công thức tường
minh nào đó (có thể dựa trên phương trình gradient của aGTH bằng 0). Đ ó là công thức cho
RG TH.
Ý tưởng này được minh họa trong thuật toán tối ưu như Gradient Descent,
Expectation-Maximization, Conditional Gradient Descent (Frank-Wolfe). Cách xây dựng
các thuật toán này làm nền tảng cơ bản để xây dựng nhiều thuật toán tối ưu khác nhau.
Dưới đây em sẽ trình bày ý tưở ng về cách xây dựng các hàm xấp xỉ cho hàm mục tiêu IGTH
của các thuật toán tối ưu này.
