Chương 1 MỘT SỐ KIẾN THỨC NỀN TẢNG Chương này trình bày về một số kiến thức cơ sở liên quan của luận án bao gồm: tổng quan về bài toán cực đại hóa xác suất hậu nghiệm, mô hình đồ thị xác suất và các phương pháp suy diễn, tối ưu ngẫu nhiên, mô hình chủ đề và một số thuật toán học trong mô hình chủ đề. Tối ưu không lồi 1. Bài toán tối ưu tổng quát Mô hình học máy thường được mô tả bởi bộ các tham số và bước học chính là đi tìm tham số tối ưu cho mô hình, từ đó dẫn về một bài toán tối ưu tham số. Nhiệm vụ của một thuật toán tối ưu trong học máy chính là tìm giá trị "tốt nhất" cho tham số của mô hình.
Giả sử tập hợp các tham số mô hình được ký hiệu bằng x, hàm đánh giá của mô hình thường được ký hiệu là f (x). Bài toán tìm tham số "tốt nhất" được đưa về bài toán tối ưu có dạng minx f (x) hoặc maxx f (x). Như vậy, học một mô hình học máy chính là giải một bài toán tối ưu toán. Do đó, tối ưu toán học, đặc biệt là tối ưu không lồi đã trở thành trung tâm của học máy [36].
Một tập Ω ⊆ Rp được gọi là một tập lồi nếu ∀x, y ∈ Ω và 0 ≤ α ≤ 1 ⇒ αx + (1 − α)y ∈ Ω. Một hàm số f xác định trên tập lồi Ω được gọi là hàm lồi trên Ω nếu f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y) ∀x, y ∈ Ω và 0 < α < 1. Chú ý rằng: (i) Một hàm số f xác định trên tập lồi Ω được gọi là lõm nếu −f là lồi trên Ω. (ii) Cho f và g là các hàm lồi trên tập lồi C và D tương ứng.
Khi đó các hàm số αf + βg (∀α, β ≥ 0) và max{f, g} cũng lồi trên C ∩ D. Xét bài toán tối ưu tổng quát min f (x) (1.1) x∈Ω 9 luan an trong đó hàm mục tiêu f (x) là hàm trơn và không lồi trên miền đóng Ω ⊂ Rp. Khi Ω = Rp thì bài toán (1.1) đưa về bài toán tối ưu không ràng buộc có dạng min f (x) (1.2) x∈Rp Do maxx∈Ω f (x) = minx∈Ω [−f (x)], nên bài toán cực đại hóa max f (x) (1.3) x∈Ω được xem xét tương tự như bài toán cực tiểu hóa (1. Cho hàm f xác định và khả vi trên Rp.
Nếu x∗ ∈ Rp là nghiệm cực tiểu địa phương của bài toán (1. Giả sử hàm số f khả vi liên tục hai lần trên Rp. Khi đó: • Nếu x∗ ∈ Rp là điểm cực tiểu địa phương của hàm f trên Rp thì ∇f (x∗ ) = 0 và ∇2 f (x∗ ) = 0 nửa xác định dương. • Ngược lại, nếu ∇f (x∗ ) = 0 và ∇2 f (x∗ ) = 0 xác định dương thì x∗ là điểm cực tiểu địa phương chặt của f trên Rp.
Đối với bài toán tối ưu lồi, nghiệm tối ưu địa phương cũng là tối ưu toàn cục. Do đó, tối ưu lồi đã được nghiên cứu rất đầy đủ trên khía cạnh lý thuyết và ứng dụng, đồng thời có nhiều thuật toán hiệu quả được đề xuất để giải chúng. Ngược lại, giải các bài toán tối ưu không lồi thường gặp nhiều khó khăn bởi tính đa cực trị của hàm mục tiêu. Với mỗi lớp bài toán tối ưu không lồi thường có một số phương pháp giải phù hợp đi kèm.
Một trong những cách tiếp cận phù hợp và hiệu quả hiện nay chính là nhóm phương pháp dựa vào thông tin đạo hàm, trong đó có các phương pháp bậc nhất chỉ dựa vào thông tin đạo hàm cấp một, ví dụ như phương pháp GD hay SGD và các phương pháp bậc hai sử dụng đạo hàm cấp hai như phương pháp Newton và các biến thể [36]. Phương pháp bậc hai thường cho kết quả tốt hơn nhưng chi phí tính toán đạo hàm cấp hai thường tốn kém và thậm chí không tính được. Chính vì vậy, bài toán tối ưu trong học máy thường hay sử dụng phương pháp ngẫu nhiên bậc nhất, đảm bảo đủ đơn giản và độ chính xác cần thiết khi áp dụng. Tối ưu ngẫu nhiên Các phương pháp tối ưu tất định kinh điển thường chỉ áp dụng tốt cho bài toán tối ưu lồi và các bộ dữ liệu huấn luyện nhỏ [9, 36].
Do đó khi đối mặt với 10 luan an các bài toán tối ưu không lồi, các phương pháp tất định thường kém hiệu quả. Các phương pháp tối ưu ngẫu nhiên như SGD [56] ra đời đã khắc phục nhược điểm của tối ưu tất định. Mục đích của một hệ thống học là tìm tham số tối ưu thông qua tối ưu hóa một hàm đánh giá, giả sử đi tìm giá trị cực tiểu hàm hàm kì vọng rủi ro J(w) như sau: Z J(w) , Ez Q(z, w) , Q(z, w)dP (z) (1.4) trong đó w là biến cần tìm để cực tiểu hóa hàm rủi ro J(w), z là các quan sát đã biết và Q(z, w) là hàm mô tả độ rủi ro của hệ thống với quan sát z. Thông thường hàm phân phối của dữ liệu P (z) là không biết trước, nên chúng ta phải xấp xỉ hàm kỳ vọng rủi ro J(w) bởi hàm rủi ro thực nghiệm JˆL (w) dựa trên L quan sát zn , n = 1, 2, .5) L n=1 Để cực tiểu hóa hàm JˆL (w) ta có thể sử dụng thuật toán GD cập nhật giá trị của w sau mỗi vòng lặp theo công thức: L 1 X wt+1 = wt + ρt ▽w JˆL (wt ) = wt − ρt ▽w Q(zn , wt ) (1.6) L n=1 Khi tốc độ học ρt đủ nhỏ, thuật toán hội tụ về cực tiểu địa phương.
Tuy nhiên, chúng tôi thấy rằng, mỗi lần cập nhật tham số, thuật toán GD phải duyệt qua tất cả các quan sát một lần, điều này gây tốn kém về mặt thời gian và bộ nhớ khi làm việc với dữ liệu lớn. Thuật toán tối ưu ngẫu nhiên SGD đã khắc phục được nhược điểm này [56]. Ý tưởng của SGD là thay ∇w JˆL (w) bằng một hàm ngẫu nhiên R(zi , w) thỏa mãn EQ(zi ) R(zi , w) = ∇w JˆL (w) (1.7) với zi là một quan sát ngẫu nhiên lấy theo phân phối đều từ tập quan sát. Việc thay thế như vậy là một xấp xỉ nhiễu tới đạo hàm đúng.
Tuy nhiên, với tốc độ học ρt phù hợp thỏa mãn điều kiện [9, 56]: ∞ X ∞ X ρt → ∞ , ρ2t < ∞ (1.8) t=1 t=1 thì SGD hội tụ tới một cực trị địa phương theo công thức cập nhật như sau: wt+1 = wt − ρt ∇w Q(zi , wt ) (1.9) 11 luan an trong đó zi là một quan sát được chọn ngẫu nhiên trong tập quan sát. Điều này cho phép thuật toán lặp đi lặp lại giữa việc lấy mẫu dữ liệu và điều chỉnh cấu trúc ẩn dựa trên các mẫu được lấy. Một chuỗi ρt thỏa mãn điều kiện trên hay được sử dụng có dạng như sau: ρt = (t + τ )−κ (1. Tham số τ ≥ 0 là gọi là trọng số tiêu biến (decay weight) và κ ∈ (0.5, 1) là tham số quên (forgetting rate).
Tham số τ và κ có thể điều chỉnh thủ công sao cho thuật toán học thu được kết quả tốt nhất. Một lưu ý là thay vì việc lấy ngẫu nhiên một quan sát, ta cũng có thể thực hiện lấy ngẫu nhiên B quan sát, tức là lấy theo mẫu nhỏ (mini-batch) {zi1 ,zi2 ,. Công thức cập nhật khi sử dụng mẫu nhỏ kích thước B như sau: iB 1 X wt+1 = wt − ρt ∇w Q(zb , wt ) (1.11) B b=i1 Phương pháp này sử dụng bộ nhớ ít hơn cách tiếp cận tối ưu "batch" thông thường. Do tối ưu không lồi rất thường gặp trong học máy, nên ngày càng có nhiều nghiên cứu về các thuật toán giải bài toán không lồi trong học máy.
Thuật toán SVRG (Stochastic Variance Reduced Gradient) và Proximal SVRG (Prox- SVRG) [57] có thể áp dụng cho bài toán có hàm mục tiêu là tổng hữu hạn các hàm không lồi. Tuy nhiên, SVRG và Prox-SVRG có hạn chế là có thể không hội tụ đến nghiệm toàn cục. Thuật toán CCCP (Concave-convex procedure) [44] cũng được ứng dụng rộng rãi cho bài toán không lồi. CCCP biến đổi bài toán không lồi thành tổng của các hàm lồi và hàm lõm sau đó tuyến tính hóa hàm lõm.
Tuy nhiên độ phức tạp của CCCP lớn vì phải giải một bài toán quy hoạch toàn phương trong mỗi vòng lặp. GOA (graduated optimization algorithm) [58] cũng được phổ biến cho bài toán tối ưu không lồi nhưng lại đối mặt với việc tính toán trực tiếp các đạo hàm. Tác giả Hazan và các cộng sự [59] đề xuất thuật toán GradOpt (Graduated Optimization) có khả năng hội tụ đến nghiệm tối ưu toàn cục với tham số (a, σ) thích hợp. Hazan cũng chỉ ra GradOpt nhanh hơn mini-batch SGD.
Các tác giả trong [60] đề xuất SVRG-GOA và PSVRG-GOA để giải bài toán không lồi dựa trên GOA, đồng thời chỉ ra GradOpt có một số hạn chế như hội tụ chậm do việc giảm của tốc độ học, điều kiện trên hàm mục tiêu là chặt khiến cho việc ứng dụng GradOpt bị hạn chế. Ngoài ra, một số thuật 12 luan an toán tối ưu đã và đang áp dụng hiệu quả trong trong học máy và học sâu như Adagrad [61], RMSProp [62], Adadelta [63], Adam [64], RSAG [65] Natasha2 [66], NEON2 [67]. Bên cạnh việc đề xuất các thuật toán mới hiệu quả cải tiến về tốc độ hội tụ, các nghiên cứu về việc thoát khỏi điểm yên ngựa trong tối ưu không lồi cũng là được quan tâm bởi Dauphin và các cộng sự [68, 69] hay Rong Ge và cộng sự [53, 70, 71]. Theo tìm hiểu của chúng tôi, để đánh giá sự hiệu quả của một thuật toán tối ưu, thường xem xét thuật toán đó trên rất nhiều khía cạnh: (i) Thuật toán áp dụng thành công trên lớp bài toán nào: bài toán lồi/không lồi, có ràng buộc/không ràng buộc? Ví dụ các phương pháp tất định kinh điển như GD, subgradient hay proximal GD, accelerate proximal GD áp dụng thành công trên tối ưu lồi với mẫu nhỏ, nhưng không hiệu quả khi làm việc với dữ liệu lớn và hàm không lồi.
Mặc dù nhóm ngẫu nhiên như SGD có tốc độ hội tụ chậm, đạt O(T −1/2 ) cho bài toán tối ưu lồi và O(T −1/4 ) cho bài toán không lồi sau T bước lặp, lại thích hợp cho bài toán tối ưu gắn với các mô hình có dữ liệu lớn. Hoặc khi làm việc với bài toán tối ưu có ràng buộc người ta thường hay sử dụng phương pháp Online Frank-Wolfe (OFW) và các biến thể của nó [46, 47, 72].