Luận án tiến sĩ: Phương pháp ngẫu nhiên cho bài toán cực đại hóa xác suất hậu nghiệm không lồi trong học máy - Bùi Thị Thanh Xuân, Trường Đại học Bách khoa Hà Nội

Bối cảnh nghiên cứu Nghiên cứu về học máy, nghiên cứu sinh nhận thấy quá trình giải một bài toán trong học máy thường gồm ba bước chính: bước mô hình hóa, bước học và bước suy diễn. Trong đó, mô hình hóa là tìm một mô hình thích hợp cho bài toán cần giải quyết, học là quá trình tối ưu các tham số của mô hình và suy diễn là bước dự đoán kết quả đầu ra của mô hình dựa trên các tham số đã huấn luyện. Ký hiệu x là tập các tham số của mô hình, khi đó bước học chính là quá trình ước lượng tham số, tức là tìm tham số x sao cho dữ liệu sẵn có và mô hình khớp với nhau nhất. Việc tối ưu tham số, hay còn gọi là quá trình học tham số, là ý tưởng chính của các bài toán học máy nhằm tìm được mối tương quan giữa các đầu vào và đầu ra dựa trên dữ liệu huấn luyện.

Một phương pháp ước lượng tham số thông dụng được sử dụng trong học máy thống kê chính là phương pháp ước lượng hợp lý cực đại MLE (Maximum Likelihood Estimation) [1, 2]. MLE thực hiện chủ yếu dựa trên các dữ liệu quan sát và thường làm việc tốt trên các mô hình có dữ liệu huấn luyện đủ lớn [3, 4, 5, 6]. Giả sử x là tập các tham số của mô hình và D là tập dữ liệu quan sát, khi đó ước lượng MLE chính là quá trình tối ưu tham số x theo xác suất: x∗ = arg max P (D|x) (0.1) x trong đó xác suất P (D|x) được gọi là likelihood của tham số x. Phương pháp MLE được xây dựng dựa trên hàm likelihood và tìm kiếm giá trị tối ưu của x để xác suất P (D|x) đạt cực đại.

Như đã đề cập, MLE chính là tìm cách giải thích hợp lý cho các dữ liệu quan sát được. Do xác suất P (D|x) thường nhỏ, để tránh sai số tính toán, người ta thường dùng logarit tự nhiên của hàm likelihood để đưa hàm mục tiêu về dạng thuận tiện hơn. Khi đó, bài toán MLE đưa về dạng sau: x∗ = arg max log P (D|x) (0.2) x Nếu chúng ta xem xét bài toán MLE (0.1) dưới góc độ của bài toán tối ưu với hàm mục tiêu P (D|x) thì bài toán MLE (0.1) có thể được giải bằng các phương pháp tối ưu thông dụng như phương pháp nhân tử Lagrange [7], 1 Gradient Descent (GD) [8], Stochastic Gradient Descent (SGD) [8, 9] hay bằng phương pháp Expectation-Maximization (EM) [2, 10, 11]. Tuy nhiên, phương pháp MLE được biết đến với xu hướng phù hợp với dữ liệu, nên hiện tượng quá khớp có thể trở nên nghiêm trọng hơn đối với các mô hình phức tạp liên quan đến dữ liệu trong thế giới thực với số chiều lớn như dữ liệu hình ảnh, tiếng nói và văn bản.

MLE thường làm việc không hiệu quả trong trường hợp có quá ít dữ liệu huấn luyện [12, 13, 14]. Ngoài ra, việc cực đại hóa hàm likelihood của MLE là không dễ dàng khi đạo hàm của nó là khó giải, cũng như không phải lúc nào cũng có thể giải được MLE trực tiếp bằng các phương pháp tích phân giải tích. Khắc phục nhược điểm của MLE, chúng ta có thể ước lượng tham số mô hình theo một cách tiếp cận khác, đó là sử dụng phương pháp cực đại hóa ước lượng xác suất hậu nghiệm MAP (Maximum A Posteriori Estimation) [15]. Khác với MLE, phương pháp MAP không những dựa trên dữ liệu huấn luyện mà còn dựa trên những thông tin đã biết của tham số.

Ước lượng MAP chính là tối ưu tham số x theo xác suất có điều kiện: x∗ = arg max P (x|D) (0.3) x | {z } Posterior trong đó xác suất P (x|D) được gọi là xác suất hậu nghiệm (posterior probability) của tham số x. Thông thường, hàm tối ưu trong (0.3) rất khó xác định trực tiếp [16, 17]. Vì vậy, để giải bài toán MAP, chúng ta thường sử dụng quy tắc Bayes P (D|x) × P (x) P (x|D) = ∝ P (D|x) × P (x) P (D) và đưa bài toán MAP (0.3) về dạng: x∗ = arg max[P (D|x) × P (x)] (0.4) x trong đó xác suất P (x) gọi là xác suất tiên nghiệm (prior) của tham số x. Theo công thức (0.4) thấy rằng xác suất hậu nghiệm P (x|D) tỉ lệ thuận với tích của thành phần likelihood P (D|x) và prior P (x) và khi P (x) là prior liên hợp thì bài toán MAP (0.4) trở nên dễ giải hơn [18].

Như vậy, việc chọn prior phù hợp giúp cho việc tối ưu bài toán MAP được thuận lợi hơn. Trong một số trường hợp, hàm mục tiêu của (0.4) khá nhỏ, sai số tính toán có thể xảy ra. Tận dụng tính chất đơn điệu tăng của hàm logarit, người ta thường lấy logarit hàm mục tiêu của (0.4) và viết lại bài toán MAP (0.4) dưới dạng: x∗ = arg max[log P (D|x) + log P (x)] (0.5) x 2 Như vậy, điểm khác biệt lớn của MAP so với MLE là hàm mục tiêu của MAP có thêm thành phần phân phối tiên nghiệm P (x) của x. Phân phối này chính là những thông tin ta biết trước về x.5), thấy rằng MAP có vai trò là kỹ thuật hiệu chỉnh của phương pháp MLE với log P (D|x) là phần hàm chính, log P (x) là phần hiệu chỉnh.

Theo quan điểm của suy diễn Bayes, MLE là một trường hợp đặc biệt của MAP [19]. MAP là một phương pháp có khả năng giúp mô hình tránh hiện tượng quá khớp, đặc biệt MAP thường mang lại hiệu quả cao hơn MLE trong trường hợp có ít dữ liệu huấn luyện. Ước lượng MAP có vai trò quan trọng trong nhiều mô hình thống kê với các biến ẩn hay các tham số không chắc chắn. Có rất nhiều nghiên cứu liên quan đến ước lượng MAP [20, 21, 22, 23, 24] hay ứng dụng của MAP vào các bài toán ngược của Bayes vô hạn [25], xử lý ảnh [26, 27], phân tích văn bản [28, 29, 30], thậm chí trong vật lý lượng tử [24].

Theo hiểu biết của nghiên cứu sinh, ước lượng MAP được sử dụng nhiều trong mô hình đồ thị xác suất [31, 16, 14, 17]. Có nhiều cách tiếp cận để giải bài toán MAP như suy diễn biến phân [32, 33] hay phương pháp lấy mẫu MCMC [34, 35],. Một hướng tiếp cận khác là xem xét bài toán MAP (0.5) dưới góc nhìn của bài toán tối ưu toán học: x∗ = arg max[f (x) = log P (D|x) + log P (x)] (0.6) x trong đó hàm mục tiêu có dạng f (x) = log P (D|x) + log P (x). Khi đó có thể áp dụng các phương pháp tối ưu ngẫu nhiên để giải chúng [36].

Trong một số trường hợp bài toán MAP có thể được giải hiệu quả bằng các phương pháp tối ưu lồi ngay cả ở trong trường hợp số chiều lớn [8, 27]. Mức độ khó giải của bài toán (0.6) phụ thuộc vào đặc điểm của hàm mục tiêu f (x). Trong thực tế, khi làm việc với các mô hình học máy thống kê, hàm mục tiêu f (x) thường rất phức tạp, khó phân tích và thường là hàm không lồi có thể tốn kém về mặt tính toán khi đánh giá [28, 37, 38]. Bài toán MAP không lồi thường hay xuất hiện gắn liền với các mô hình học máy làm việc với dữ liệu lớn nên các phương pháp giải đúng thường không khả thi.

Vì vậy một hướng tiếp cận phổ biến và hiệu quả hơn cho bài toán MAP không lồi này chính là các phương pháp xấp xỉ. Theo tìm hiểu, một số phương pháp xấp xỉ như phương pháp Variational Bayes (VB) [39], collapsed Variational Bayes (CVB) [40, 41], CVB0 [42], Collapsed Gibbs Sampling (CGS) [43], Concave- Convex procedure (CCCP) [44], Stochastic Majorization-Minimization (SMM) [45], Frank-Wolfe (FW) [46], Online-FW [47] hay Block-coordinate Frank-Wolfe 3 [48] có thể được áp dụng để giải bài toán ước lượng hậu nghiệm. Ngoài ra, phương pháp Particle Mirror Decent (PMD) [49] và HAMCMC [50] cũng đã được đề xuất cho bài toán ước lượng phân phối hậu nghiệm đầy đủ. Các phương pháp đề cập có thể coi là các phương pháp suy diễn tiên tiến.

Tuy nhiên khi nghiên cứu và phân tích đặc điểm của chúng, nhận thấy trong các phương pháp đề cập vẫn còn một số nhược điểm tồn tại. Ví dụ, một số phương pháp đã nêu chỉ áp dụng được cho một mô hình cụ thể hoặc chúng chưa đáp ứng được các tiêu chuẩn quan trọng như sự hội tụ, tốc độ hội tụ, tính linh hoạt hay tính hiệu chỉnh. Chúng tôi chưa nhìn thấy bất kỳ phân tích lý thuyết nào về khả năng suy diễn nhanh của các phương pháp như VB, CVB, CVB0 và CGS. Mặc dù phương pháp CCCP và SMM đảm bảo hội tụ đến một điểm dừng của bài toán suy diễn, tuy nhiên tốc độ hội tụ của CCCP và SMM chưa được xác định đối với bài toán không lồi tổng quát [44, 45].

FW là một phương pháp tổng quát giải bài toán tối ưu lồi. [51] và [52] đã chỉ ra rằng thuật toán FW có thể được sử dụng hiệu quả để suy diễn cho các mô hình chủ đề. OFW là một biến thể ngẫu nhiên của FW cho các bài toán lồi. Một đặc điểm quan trọng của FW và OFW chính là chúng có thể hội tụ nhanh và cho nghiệm thưa.

Tuy nhiên, hạn chế của chúng là chỉ áp dụng cho các bài toán lồi, chưa đáp ứng cho các mô hình không lồi trong học máy. Thuật toán PMD [49] và HAMCMC [50] đều dựa trên lấy mẫu để ước lượng phân phối xác suất hậu nghiệm, trong đó PMC có tốc độ hội tụ O(T −1/2 ) trong khi HAMCMC có tốc độ hội tụ O(T −1/3 ) với T là số bước lặp của thuật toán. Thuật toán Online Maximum a Posteriori Estimation (OPE) [28] đã được đề xuất để giải bài toán MAP trong các mô hình đồ thị xác suất với tốc độ hội tụ là O(1/T ). OPE là một thuật toán tối ưu ngẫu nhiên được cải tiến từ thuật toán OFW [47] để giải bài toán MAP không lồi và có tốc độ hội tụ nhanh vượt qua nhiều thuật toán ngẫu nhiên hiện có khi giải bài toán MAP không lồi.

Mặc dù ước lượng MAP có nhiều ưu thế so với MLE trên phương diện có thể làm việc với dữ liệu huấn luyện ít, có khả năng hiệu chỉnh, tuy nhiên, tìm đến các phương pháp hiệu quả giải bài toán MAP là việc khó khăn. Và nguyên nhân chính dẫn đến khó khăn của bài toán MAP nằm ở chỗ hàm mục tiêu f (x) = log P (D|x) + log P (x) trong nhiều trường hợp là hàm không lồi, khó tìm được cực đại, dẫn đến giải trực tiếp bài toán MAP không khả thi [37].