Một 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

Nội dung tài liệu: Một 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

1. BË GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HÅC BÁCH KHOA HÀ NËI BÙI THỊ THANH XUÂN MËT 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 TÂM TẮT LUẬN ÁN TIẾN SĨ HỆ THÈNG THÆNG TIN HÀ NËI−2020
2. Công tr¼nh được hoàn thành t¤i: Trường Đại học B¡ch khoa Hà Nëi Người hướng d¨n khoa học: HD1: PGS.TS. Th¥n Quang Kho¡t HD2: TS. Nguy¹n Thị Oanh Ph£n bi»n 1: PGS.TS. Nguy¹n Phương Th¡i Ph£n bi»n 2: PGS.TS. Lương Th¸ Dũng Ph£n bi»n 3: PGS.TS. Nguy¹n Long Giang Luªn ¡n được b£o v» t¤i Hëi đồng đánh gi¡ luªn ¡n ti¸n sĩ c§p Trường họp t¤i Trường Đại học B¡ch khoa Hà Nëi. Vào hồi giờ, ngày th¡ng n«m Có thº t¼m hiºu luªn ¡n t¤i: 1. Thư vi»n T¤ Quang Bûu - Trường ĐHBK Hà Nëi 2. Thư vi»n Quèc gia Vi»t Nam.
3. MÐ ĐẦU 1. Bèi c£nh nghi¶n cùu Nghi¶n cùu v· học m¡y, chúng tôi 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 Maximum Likelihood Estimation (MLE). 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. Kh­c phục nhược điểm cõa MLE, chúng tôi sû dụng phương ph¡p cực đại hóa ước lượng x¡c su§t hªu nghi»m Maximum A Posteriori Estimation (MAP). Kh¡c với MLE, MAP không ch¿ 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 (xjD) (0:3) x | {z } Posterior trong đó x¡c su§t P (xjD) được gọi là x¡c su§t hªu nghi»m (posterior) cõa tham sè x. Thông thường, hàm tèi ưu trong (0.3) khó x¡c định trực ti¸p. V¼ vªy, để gi£i bài to¡n MAP, chúng ta thường sû dụng quy t­c Bayes và đưa bài to¡n MAP (0.3) v· d¤ng: x∗ = arg max[P (Djx) × 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. 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 (Djx) + log P (x)] (0:5) x Theo hiºu bi¸t cõa chúng tôi, ước lượng MAP được sû dụng nhi·u trong mô h¼nh đồ thị x¡c su§t. Có nhi·u c¡ch ti¸p cªn để gi£i bài to¡n MAP như suy di¹n bi¸n ph¥n hay phương ph¡p l§y m¨u MCMC, 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 j x) + log P (x)] (0:6) x trong đó hàm mục ti¶u có d¤ng f(x) = log P (Djx) + log P (x). 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¸, 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 phùc t¤p, khó ph¥n t½ch và là hàm không lồi, có thº tèn k²m v· mặt t½nh to¡n. Mặc dù ước lượng MAP có nhi·u ưu th¸ so với MLE tr¶n c¡c phương di»n như: 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. 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 (Djx) + 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. Chúng ta ph£i đối mặt với th¡ch thùc lớn: Làm th¸ nào để gi£i hi»u qu£ bài to¡n MAP trong c¡c mô h¼nh đồ thị x¡c su§t khi hàm mục ti¶u là không lồi? Do vªy, đề xu§t ra c¡c thuªt to¡n hi»u qu£ đảm b£o 1
4. 2 v· lý thuy¸t và thực nghi»m để gi£i bài to¡n MAP không lồi thu hút sự quan t¥m đồng thời cũng là th¡ch thùc cõa học m¡y thèng k¶. 2. Động lực thúc đẩy Nghi¶n cùu sinh đặt ra bài to¡n c¦n nghi¶n cùu cõa m¼nh là: Nghi¶n cùu đề xu§t c¡c thuªt to¡n ng¨u nhi¶n hi»u qu£ gi£i bài to¡n MAP không lồi xu§t hi»n trong c¡c mô h¼nh đồ thị x¡c su§t được cho dưới d¤ng x∗ = arg max[f(x) = log P (Djx) + log P (x)] x trong đó hàm mục ti¶u f(x) là hàm nhi·u chi·u, không lồi tr¶n mi·n ràng buëc Ω. Khó kh«n cõa bài to¡n đặt ra ở đây ch½nh là hàm mục ti¶u f(x) không lồi có thº xu§t hi»n nhi·u điểm cực trị địa phương/điểm y¶n ngựa, đồng thời f(x) là hàm nhi·u bi¸n có sè chi·u lớn, có thº gặp khó kh«n trong vi»c t½nh trực ti¸p đạo hàm c¡c c§p, do đó bài to¡n MAP không lồi có thº trở thành khó gi£i. Nghi¶n cùu sinh đặt ra mục ti¶u là đề xu§t được mët sè thuªt to¡n tèi ưu ng¨u nhi¶n để gi£i hi»u qu£ bài to¡n MAP không lồi đảm b£o c¡c ti¶u ch½ như sau: (i) C¡c thuªt to¡n ng¨u nhi¶n đảm b£o ch§t lượng v· lý thuy¸t và thực nghi»m, (ii) C¡c thuªt to¡n có tèc độ hëi tụ nhanh, (iii) C¡c thuªt to¡n có t½nh linh ho¤t, t½nh têng qu¡t và kh£ n«ng hi»u ch¿nh tèt. Tø đó có thº ¡p dụng c¡c thuªt to¡n đó rëng r¢i trong nhi·u mô h¼nh trong học m¡y. Để triºn khai được c¡c mục ti¶u đặt ra, nghi¶n cùu sinh đã lựa chọn đề tài "Mët 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" cho luªn ¡n cõa m¼nh. Sự thành công cõa đề tài góp ph¦n gi£i quy¸t tèt hơn bài to¡n ước lượng MAP không lồi, đồng thời có thº mở rëng ¡p dụng để gi£i tèt c¡c bài to¡n tèi ưu không lồi thường xu§t hi»n trong nhi·u mô h¼nh học m¡y. 3. C¡c đóng góp ch½nh cõa luªn ¡n Với mục ti¶u triºn khai thành công đề tài, c¡c nghi¶n cùu cõa luªn ¡n tªp trung ch½nh vào c¡c đề xu§t sau đây: • Đề xu§t bèn thuªt to¡n tèi ưu ng¨u nhi¶n OPE1, OPE2, OPE3 và OPE4 gi£i bài to¡n suy di¹n hªu nghi»m trong mô h¼nh chõ đề có b£n ch§t là bài to¡n tèi ưu không lồi thông qua vi»c sû dụng ph¥n phèi x¡c su§t đều k¸t hñp với dùng hai chuéi bi¶n ng¨u nhi¶n x§p x¿ cho hàm mục ti¶u ban đầu, trong đó c¡c đề xu§t có đảm b£o v· cơ sở lý thuy¸t và thực nghi»m. • Đề xu§t thuªt to¡n tèi ưu ng¨u nhi¶n GOPE gi£i bài to¡n MAP không lồi trong mô h¼nh chõ đề thông qua sû dụng ph¥n phèi Bernoulli với tham sè p 2 (0; 1) th½ch hñp. Tø đó, chúng tôi ¡p dụng GOPE để thi¸t k¸ thuªt to¡n ng¨u nhi¶n Online-GOPE học mô h¼nh chõ đề hi»u qu£. • Sû dụng ng¨u nhi¶n Bernoulli với tham sè p 2 (0; 1) th½ch hñp, k¸t hñp với dùng hai bi¶n ng¨u nhi¶n và nguy¶n lý tham lam, chúng tôi đề xu§t BOPE gi£i bài to¡n MAP không lồi têng qu¡t đảm b£o c¡c ti¶u ch½ quan trọng: tèc đë hëi tụ nhanh, có t½nh linh ho¤t, có t½nh hi»u ch¿nh. Chúng tôi đã ¡p dụng thành công BOPE vào bài to¡n ph¥n t½ch v«n b£n và h» gñi ý. 4. Bè cục cõa luªn ¡n K¸t c§u thành 4 chương, luªn ¡n đã tr¼nh bày trọn vẹn c¡c thuªt to¡n đề xu§t gi£i bài to¡n MAP không lồi trong học m¡y. Như vªy, c¡c nëi dung trong luªn ¡n đã đáp ùng được c¡c mục ti¶u mà chúng tôi đã đề ra.
5. Chương 1 MËT SÈ KIẾN THỨC NỀN TẢNG 1.1. Tèi ưu không lồi 1.1.1. Bài to¡n tèi ưu têng qu¡t 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. X²t bài to¡n tèi ưu têng qu¡t min f(x) (1.1) x2Ω trong đó hàm mục ti¶u f(x) là hàm trơn và không lồi tr¶n mi·n đóng Ω. Bài to¡n tèi ưu trong học m¡y thường hay sû dụng c¡c 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. 1.1.2. Tèi ưu ng¨u nhi¶n 1.2. Mô h¼nh đồ thị x¡c su§t 1.2.1. Giới thi»u Mô h¼nh đồ thị x¡c su§t sû dụng đồ thị để biºu di¹n phụ thuëc có điều ki»n giúa c¡c bi¸n ng¨u nhi¶n mët c¡ch trực quan, trong đó có c¡c đỉnh là c¡c bi¸n ng¨u nhi¶n, c¡c c¤nh 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 đó. Mô h¼nh đồ thị x¡c su§t là mët công cụ m¤nh m³ có nhi·u ùng dụng trong học m¡y, thị gi¡c m¡y t½nh, xû lý ngôn ngú tự nhi¶n và tin sinh học. 1.2.2. Mët sè phương ph¡p suy di¹n a. Phương ph¡p suy di¹n bi¸n ph¥n b. Phương ph¡p Markov Chain Monte Carlo (MCMC) c. Phương ph¡p Gibbs Sampling 1.3. Bài to¡n cực đại hóa x¡c su§t hªu nghi»m 1.3.1. Giới thi»u bài to¡n MAP Bài to¡n MAP có thº được xem x²t dưới d¤ng bài to¡n tèi ưu to¡n học: x∗ = arg max[f(x) = log P (Djx) + log P (x)] (1:18) x Khó kh«n cõa bài to¡n MAP ch½nh là hàm mục ti¶u f(x) = log P (Djx) + log P (x) là hàm không lồi, có thº gặp khó kh«n khi t¼m cực đại, d¨n đến gi£i trực ti¸p bài to¡n MAP không kh£ thi. 1.3.2. Mët sè phương ph¡p ti¸p cªn Theo hiºu bi¸t cõa chúng tôi, có mët sè c¡ch ti¸p cªn để gi£i bài to¡n MAP như sau: • Thông qua c¡c ph²p ph¥n t½ch, khi mèt cõa ph¥n phèi hªu nghi»m được cho dưới d¤ng "close-form" và đây là trường hñp prior li¶n hñp. • Thông qua c¡c phương ph¡p sè như phương ph¡p gradient hoặc phương ph¡p Newton. Tuy nhi¶n, chúng thường y¶u c¦u c¡c đạo hàm bªc nh§t hoặc bªc hai ph£i t¼m được b¬ng phương ph¡p gi£i t½ch hoặc b¬ng phương ph¡p sè. 3
6. 4 • Thông qua vi»c ¡p dụng thuªt to¡n Expectation Maximization (EM). • Thông qua c¡c phương ph¡p Monte Carlo. Đặt g1(x) = log P (D j x) và g2(x) = log P (x). Khi đó, bài to¡n MAP được đưa v· bài to¡n tèi ưu như sau ∗ x = arg max[f(x) = g1(x) + g2(x)] (1:19) x Chúng ta có thº sû dụng c¡c phương ph¡p tèi ưu ng¨u nhi¶n hi»n đại cùng với c¡c c£i ti¸n th½ch hñp để gi£i chúng. 1.4. Mô h¼nh chõ đề 1.4.1. Giới thi»u v· mô h¼nh chõ đề 1.4.2. Mô h¼nh Latent Dirichlet Allocation 1.4.3. Suy di¹n hªu nghi»m trong mô h¼nh chõ đề Với mô h¼nh chõ đề LDA, ph¥n phèi hªu nghi»m ch½nh là P (θ; zjw; α; β) cho méi v«n b£n d. Bài to¡n t½nh ph¥n phèi x¡c su§t này gọi là bài to¡n suy di¹n. Trong mô h¼nh LDA, ph¥n phèi hªu nghi»m cõa bi¸n ©n cho méi v«n b£n d là: P (θ; z; wjα; β) P (θ; zjw; α; β) = P (wjα; β) a. Phương ph¡p Variational Bayes b. Phương ph¡p Collapsed variational Bayes c. Fast collapsed variational Bayes d. Phương ph¡p Collapsed Gibbs sampling 1.5. Thuªt to¡n OPE X²t bài to¡n suy di¹n hªu nghi»m đối với tøng v«n b£n d trong mô h¼nh chõ đề. Ước lượng t¿ l» chõ đề θ 2 ∆K cho mët v«n b£n d, x²t bài to¡n sau: θ∗ = arg max P (d; θjβ; α) = arg max[log P (djθ; β) + log P (θjα)] (1:22) θ2∆K θ2∆K Bài to¡n (1.22) tương ùng với bài to¡n sau: K K ∗ X X X θ = arg max dj log θkβkj + (α − 1) log θk (1:23) θ2∆K j k=1 k=1 trong đó α là tham sè cõa ph¥n phèi ti¶n nghi»m Dirichlet. Trong thực t¸, khi sû dụng mô h¼nh LDA, người ta thường chọn α < 1 d¨n đến hàm mục ti¶u cõa (1.23) là không lãm. Đó là lý do t¤i sao bài to¡n (1.23) không kh£ thi trong trường hñp x§u. Thuªt to¡n Online Frank-Wolfe (OFW) được đề xu§t để gi£i bài to¡n suy di¹n MAP không lồi với mô h¼nh LDA. C£i ti¸n OFW, c¡c t¡c gi£ đã đề xu§t thuªt to¡n c£i ti¸n mới là Online maximum a Posteriori Estimation (OPE). OPE có nhi·u ưu điểm so với c¡c đề xu§t trước đó. Chi ti¸t cõa OPE được tr¼nh bày trong Thuªt to¡n 1.7.
7. 5 Thuªt to¡n 1. 7 OPE: Online Maximum a Posteriori Estimation Đầu vào: V«n b£n d và mô h¼nh fβ; αg P PK PK Đầu ra: θ là cực đại cõa hàm f(θ) = j dj log k=1 θkβkj + (α − 1) k=1 log θk 1: Khởi t¤o θ1 thuëc ∆K 2: for t = 1; 2; :::1 do P PK PK 3: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt 4: Ft := t h=1 fh 0 5: e := arg max t x2∆K t t et−θt 6: θt+1 := θt + t 7: end for 1.6. Mët sè thuªt to¡n ng¨u nhi¶n học LDA Sû dụng c¡c thuªt to¡n suy di¹n như Variational Bayes (VB), Collapsed variational Bayes (CVB0), Collapsed Gibbs sampling (CGS), c¡c phương ph¡p học ng¨u nhi¶n như Online-VB, Online-CVB0, Online-CGS đã được đề xu§t để học mô h¼nh LDA. Sû dụng OPE làm cèt lãi suy di¹n và lược đồ học trực tuy¸n, hai thuªt to¡n ng¨u nhi¶n học mô h¼nh LDA, đặt t¶n là ML-OPE và Online-OPE đã được ph¡t triºn. Chi ti¸t cõa ML-OPE và Online-OPE được tr¼nh bày trong Thuªt to¡n 1.8 và Thuªt to¡n 1.9. Thuªt to¡n 1. 8 ML-OPE học LDA tø dú li»u dáng/dú li»u lớn Đầu vào: Tham sè K; α; τ > 0; κ 2 (0:5; 1] Đầu ra: β 0 1: Khởi t¤o β ng¨u nhi¶n trong mi·n ∆V 2: for t = 1; 2;::: 1 do 3: L§y mini-batch Ct cõa tªp c¡c v«n b£n t−1 4: Suy di¹n b¬ng OPE cho méi v«n b£n d 2 Ct nhªn được θd, cho bởi β t 5: T½nh to¡n β^ như sau: β^t / P d θ kj d2Ct j dk −κ 6: Thi¸t lªp tèc độ học ρt = (t + τ) t t−1 ^ t 7: Cªp nhªt β := (1 − ρt)β + ρtβ 8: end for Thuªt to¡n 1. 9 Online-OPE học LDA tø dú li»u lớn Đầu vào: Tªp hu§n luy»n C với D v«n b£n, K; α; η; τ > 0; κ 2 (0:5; 1] Đầu ra: λ 1: Khởi t¤o λ0 ng¨u nhi¶n 2: for t = 1; 2;::: 1 do 3: L§y m¨u nhỏ Ct bao gồm S v«n b£n, t−1 t−1 4: Sû dụng thuªt to¡n OPE để suy di¹n hªu nghi»m cho méi v«n b£n d 2 Ct, với bi¸n toàn cục β / λ trong bước trước, nhªn được chõ đề hén hñp θd. Sau đó t½nh φd như sau: φdjk / θdkβkj ^ 5: Với méi k 2 f1; 2;:::;Kg, bi¸n toàn cục trung gian λk cho Ct bởi D X λ^ = η + d φ kj S j djk d2Ct t t−1 ^ −κ 6: Cªp nhªt bi¸n toàn cục b¬ng λ := (1 − ρt)λ + ρtλ trong đó ρt = (t + τ) 7: end for 1.7. K¸t luªn chương 1 Chương 1 tr¼nh bày kh¡i qu¡t v· bài to¡n MAP và mët sè c¡ch ti¸p cªn gi£i bài to¡n MAP, ti¸p theo tr¼nh bày mët sè ki¸n thùc cơ b£n v· tèi ưu ng¨u nhi¶n gi£i bài to¡n tèi ưu không lồi thường hay gặp trong học m¡y, mô h¼nh đồ thị x¡c su§t, c¡c phương ph¡p suy di¹n, mô h¼nh chõ đề, Đây là ti·n đề cho c¡c nghi¶n cùu v· c¡c thuªt to¡n ng¨u nhi¶n gi£i bài to¡n MAP không lồi được đề xu§t trong c¡c chương ti¸p theo.
8. Chương 2 NGẪU NHIÊN HÂA THUẬT TOÁN TÈI ƯU GIẢI BÀI TOÁN SUY DIỄN HẬU NGHIỆM TRONG MÆ HÌNH CHỦ ĐỀ 2.1. Giới thi»u Trong chương này, chúng tôi xem x²t bài to¡n suy di¹n hªu nghi»m trong mô h¼nh chõ đề LDA. Đây là mët minh họa cho bài to¡n MAP không lồi trong c¡c mô h¼nh đồ thị x¡c su§t, đối tượng nghi¶n cùu cõa luªn ¡n. Bài to¡n MAP đối với tøng v«n b£n d trong mô h¼nh chõ đề LDA có d¤ng: K K ∗ X X X θ = arg max dj log θkβkj + (α − 1) log θk (2.1) θ2∆K j k=1 k=1 trong đó tham sè Dirichlet α 0 là log prior cõa v«n b£n d. • Hàm mục ti¶u f(θ) = g1(θ)+g2(θ) bị kẹp giúa hai hàm g1 và g2, tùc là g1(θ) < f(θ) < g2(θ). Dựa tr¶n ý tưởng cõa OPE, chúng tôi đề xu§t mët sè thuªt to¡n c£i ti¸n mới s³ được tr¼nh bày trong mục này. Xu§t ph¡t tø thành ph¦n g1, x¥y dựng d¢y hàm fLt(θ)g, xu§t ph¡t tø thành ph¦n g2, x¥y dựng d¢y hàm fUtg dựa vào ph¥n phèi Bernoulli với tham sè p. Hai d¢y hàm ng¨u nhi¶n fUtg và fLtg cùng ti¸n v· hàm mục ti¶u f. (a) X¥y dựng bi¶n tr¶n và bi¶n dưới cõa hàm (b) Luôn lựa chọn điểm tèt hơn trong méi mục ti¶u f(θ) bước lặp H¼nh 2.2. Mô t£ ý tưởng cơ b£n c£i ti¸n thuªt to¡n OPE. Để t«ng t½nh ng¨u nhi¶n cho thuªt to¡n đề xu§t, t¤i méi bước lặp, nghi»m g¦n đúng θt được u l chọn dựa vào hai d¢y fθt g và fθtg b¬ng c¡c ph¥n phèi x¡c su§t th½ch hñp. u l (1) C£i ti¸n thù nh§t: Sau khi x¥y dựng hai d¢y fθt g và fθtg, chúng tôi ti¸n hành lựa chọn u l nghi»m x§p x¿ θt ở l¦n lặp thù t theo ph¥n phèi đều tø hai nghi»m x§p x¿ trung gian fθt ; θtg, tùc là 1 1 P (θ = θu) = ;P (θ = θl) = t t 2 t t 2 thu được thuªt to¡n OPE1 được tr¼nh bày trong Thuªt to¡n 2.1. 6
9. 7 Thuªt to¡n 2. 1 OPE1: Sự lựa chọn đều tø hai bi¶n ng¨u nhi¶n Đầu vào: V«n b£n d và tham sè mô h¼nh fβ; αg ∗ P PK PK Đầu ra: θ là nghi»m cực đại hóa cõa hàm f(θ) = j dj log k=1 θkβkj + (α − 1) k=1 log θk 1: Khởi t¤o θ1 thuëc ∆K l P PK u PK 2: f1 := j dj log k=1 θkβkj; f1 := (α − 1) k=1 log θk 3: for t = 2; 3;:::; 1 do u P PK PK 4: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt u 5: Ut := t h=1 fh 0 6: eu := arg max hU (θ ); xi t x2∆K t t u u et −θt 7: θt+1 := θt + t l P PK PK 8: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt l 9: Lt := t h=1 fh 0 10: el := arg max hL (θ ); xi t x2∆K t t l l et−θt 11: θt+1 := θt + t u l 12: L§y θt+1 có ph¥n phèi đều tø fθt+1; θt+1g 13: end for u l (2) C£i ti¸n thù hai: Nghi»m θt ở bước lặp thù t được lựa chọn ng¨u nhi¶n tø θt và θt theo ph¥n phèi Bernoulli với x¡c su§t qt, tùc là: u l P (θt = θt ) = qt;P (θt = θt) = 1 − qt u exp f(θt ) trong đó qt := u l . Chúng tôi thu được thuªt to¡n c£i ti¸n OPE2 được tr¼nh bày exp f(θt )+exp f(θt) trong Thuªt to¡n 2.2. C¡ch lựa chọn nghi»m x§p x¿ θt trong méi bước lặp ở c£i ti¸n OPE2 đã được làm mịn hơn so với bi¸n thº OPE1 khi chúng tôi sû dụng nhi·u thông tin cõa hàm mục ti¶u f vào trong sự lựa chọn nghi»m θt. Thuªt to¡n 2. 2 OPE2: Làm mịn sự lựa chọn nghi»m tø hai bi¶n ng¨u nhi¶n Đầu vào: V«n b£n d và tham sè mô h¼nh fβ; αg ∗ P PK PK Đầu ra: θ là nghi»m cực đại hóa cõa hàm f(θ) = j dj log k=1 θkβkj + (α − 1) k=1 log θk 1: Khởi t¤o θ1 thuëc ∆K l P PK u PK 2: f1 := j dj log k=1 θkβkj ; f1 := (α − 1) k=1 log θk 3: for t = 2; 3;:::; 1 do u P PK PK 4: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt u 5: Ut := t h=1 fh 0 6: eu := arg max hU (θ ); xi t x2∆K t t u u et −θt 7: θt+1 := θt + t l P PK PK 8: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt l 9: Lt := t h=1 fh 0 10: el := arg max hL (θ ); xi t x2∆K t t l l et−θt 11: θt+1 := θt + t u l 12: L§y θt+1 theo ph¥n phèi x¡c su§t fP (θt+1 = θt+1) = qt;P (θt+1 = θt+1) = 1 − qtg trong đó x¡c su§t qt u exp f(θt+1) được x¡c định bởi qt := u l exp f(θt+1)+exp f(θt+1) 13: end for u l (3) C£i ti¸n thù ba: Sau khi x¥y dựng hai d¢y fθt g và fθtg, chúng tôi ti¸n hành lựa chọn nghi»m x§p x¿ ở bước lặp t là: θ := arg max u l f(θ) và thu được thuªt to¡n OPE3 được t θ2fθt ;θtg tr¼nh bày trong Thuªt to¡n 2.3. (4) C£i ti¸n thù tư: Chúng tôi có mët ý tưởng kh¡c, đó là x§p x¿ hàm mục ti¶u đúng f(θ) bởi hàm x§p x¿ ng¨u nhi¶n Ft(θ) trong đó Ft(θ) là tê hñp tuy¸n t½nh cõa hai bi¶n ng¨u nhi¶n Ut và Lt với tham sè tê hñp ν 2 (0; 1) được lựa chọn th½ch hñp: Ft(θ) := νUt(θ) + (1 − ν)Lt(θ)
10. 8 Thuªt to¡n 2. 3 OPE3: Luôn lựa chọn nghi»m tèt hơn trong méi bước lặp Đầu vào: v«n b£n d và tham sè mô h¼nh fβ; αg ∗ P PK PK Đầu ra: θ là nghi»m cực đại hóa cõa hàm f(θ) = j dj log k=1 θkβkj + (α − 1) k=1 log θk 1: Khởi t¤o θ1 thuëc ∆K l P PK u PK 2: f1 := j dj log k=1 θkβkj ;f1 := (α − 1) k=1 log θk 3: for t = 2; 3; ::; 1 do u P PK PK 4: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj ;(α − 1) k=1 log θkg 2 Pt u 5: Ut := t h=1 fh 0 6: eu := arg max hU (θ ); xi t x2∆K t t u u et −θt 7: θt+1 := θt + t l P PK PK 8: L§y ft có ph¥n phèi đều tø f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt l 9: Lt := t h=1 fh 0 10: el := arg max hL (θ ); xi t x2∆K t t l l et−θt 11: θt+1 := θt + t 12: L§y θt+1 := arg max u l f(θ) θ2fθt+1;θt+1g 13: end for và ti¸n hành t¼m nghi»m θt tương tự như OPE. Chúng tôi thu được OPE4 tr¼nh bày chi ti¸t trong Thuªt to¡n 2.4. Thuªt to¡n 2. 4 OPE4: Sû dụng tê hñp tuy¸n t½nh cõa c¡c bi¶n ng¨u nhi¶n Đầu vào: V«n b£n d, tham sè tê hñp ν 2 (0; 1) và tham sè mô h¼nh fβ; αg ∗ P PK PK Đầu ra: θ là nghi»m cực đại hóa cõa hàm f(θ) = j dj log k=1 θkβkj + (α − 1) k=1 log θk 1: Khởi t¤o θ1 thuëc ∆K l P PK u PK 2: f1 := j dj log k=1 θkβkj ; f1 := (α − 1) k=1 log θk 3: for t = 2; 3; ::; 1 do u P PK PK 4: L§y ft theo ph¥n phèi đều tø tªp f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt u 5: Ut := t h=1 fh l P PK PK 6: L§y ft theo ph¥n phèi đều tø tªp f j dj log k=1 θkβkj;(α − 1) k=1 log θkg 2 Pt l 7: Lt := t h=1 fh 8: Lªp tê hñp tuy¸n t½nh Ft := νUt + (1 − ν)Lt 0 9: e := arg max t x2∆K t t et−θt 10: θt+1 := θt + t 11: end for 2.3. C¡c thuªt to¡n học ng¨u nhi¶n cho mô h¼nh LDA Chúng tôi ti¸n hành thay đổi thuªt to¡n lãi suy di¹n OPE b¬ng c¡c c£i ti¸n mới như OPE1, OPE2, OPE3 và OPE4 và đưa vào trong thuªt to¡n học ML-OPE và Online-OPE. Khi đó, chúng tôi thu được 8 thuªt to¡n ng¨u nhi¶n mới để học mô h¼nh LDA, đó là: ML-OPE1, ML-OPE2, ML-OPE3, ML-OPE4, Online-OPE1, Online-OPE2, Online-OPE3 và Online-OPE4. 2.4. Đánh gi¡ thực nghi»m 2.4.1. C¡c bë dú li»u thực nghi»m Chúng tôi ti¸n hành thực nghi»m cho c¡c c£i ti¸n tr¶n hai bë dú li»u lớn: bë New York Times (NYT) bao gồm 300.000 bài tin tùc và bë PubMed (PUB) bao gồm 330.000 bài b¡o tø trung t¥m PubMed1. 1C¡c bë dú li»u được l§y tø
11. 9 2.4.2. Độ đo đánh gi¡ thực nghi»m Chúng tôi sû dụng hai độ đo thường được dùng trong mô h¼nh chõ đề, đó là Log Predictive Probability (LPP) và Normalised Pointwise Mutual Information (NPMI). 2.4.3. K¸t qu£ thực nghi»m 1 • Tham sè mô h¼nh: Chúng tôi thi¸t lªp sè chõ đề K = 100, tham sè Dirichlet α = K và si¶u 1 tham sè η = K . C¡c tham sè này thường được sû dụng trong c¡c mô h¼nh chõ đề. • Tham sè suy di¹n: Chúng tôi lựa chọn sè bước lặp cõa thuªt to¡n suy di¹n T = 50. Ngoài ra, kh£o s¡t sự £nh hưởng cõa sè l¦n lặp T đến c¡c thuªt to¡n suy di¹n và thuªt to¡n học, chúng tôi cũng ti¸n hành thực nghi»m với c¡c gi¡ trị kh¡c nhau cõa T 2 f20; 30; 40; 50; 100g. Trong thuªt to¡n OPE4, chúng tôi có kh£o s¡t tham sè tê hñp tuy¸n t½nh ν nhªn c¡c gi¡ trị rời r¤c trong f0:01; 0:10; 0:20;:::; 0:90; 0:99g. • Tham sè học: Chúng tôi lựa chọn k½ch thước mini-batch S = jCtj = 5000, thi¸t lªp si¶u tham sè κ = 0:9 và τ = 1 th½ch nghi tèt cho c¡c phương ph¡p suy luªn hi»n có. -OPEx on PUBMED 0 0 0 0 0 15 30 45 60 -OPEx on NYT ốă ốă H¼nh 2.5. K¸t qu£ cõa c¡c thuªt to¡n mới so s¡nh với OPE thông qua độ đo LPP. Độ đo càng cao càng tèt. Chúng tôi th§y r¬ng mët sè thuªt to¡n mới đảm b£o tèt hoặc thªm ch½ tèt hơn OPE. 0 0 0 0 0 0 0 0 0 0 0 Online-OPEx Online-OPEx on NYT 10 6.0 8 4.5 NPMI 3.0 6 1.5 4 0 0 0 (x5000) (x5000) H¼nh 2.6. K¸t qu£ cõa c¡c thuªt to¡n mới so s¡nh với OPE tr¶n độ đo NPMI. Độ đo càng cao càng tèt. Chúng tôi th§y r¬ng mët sè thuªt to¡n mới đảm b£o tèt, thªm ch½ tèt hơn OPE. Chúng tôi ti¸n hành thực nghi»m ML-OPE4 và Online-OPE4 với c¡c gi¡ trị kh¡c nhau cõa ν. Chúng tôi nhªn th§y thuªt to¡n OPE4 phù hñp với tham sè ν có xu hướng g¦n gi¡ trị 0:5 đối với
12. 10 bë New York Times hay g¦n gi¡ trị 1 với bë PubMed. Chúng tôi ti¸n hành thực nghi»m c¡c thuªt to¡n mới đ· xu§t OPE1, OPE2, OPE3 và OPE4 so s¡nh với thuªt to¡n OPE. Chi ti¸t k¸t qu£ được mô t£ trong H¼nh 2.5 và H¼nh 2.6. Chúng tôi th§y r¬ng OPE1 thu được k¸t qu£ k²m nh§t, OPE2 và OPE3 tèt hơn OPE, cán OPE4 (với tham sè tê hñp ν phù hñp) cho k¸t qu£ tèt nh§t. Chúng tôi sû dụng thuªt to¡n học Online-OPE3 để thực nghi»m kh£o s¡t sự thay đêi cõa k½ch thước mini-batch jCtj và sè bước lặp T cõa thuªt to¡n suy di¹n OPE3. -8.068 -8.099 Mini-batch= 5000 -8.17 Mini-batch= 10000 -9.278 -9.305 -9.358 Mini-batch= 25000 N H¼nh 2.7. K¸t qu£ độ đo LPP cõa thuªt to¡n học Online-OPE3 tr¶n hai bë dú li»u New York Times và PubMed với c¡ch chia k½ch thước mini-batch kh¡c nhau. Độ đo càng cao càng tèt. 12 11.442 10.904 Mini-batch= 5000 Mini-batch= 10000 10 Mini-batch= 25000 8.556 8 7.088 7.07 6 5.783 NPMI 4 2 0 New York Times PubMed H¼nh 2.8. K¸t qu£ độ đo NPMI cõa thuªt to¡n học Online-OPE3 tr¶n hai bë dú li»u New York Times và PubMed với c¡ch chia k½ch thước mini-batch kh¡c nhau. Độ đo càng cao càng tèt. 1 1 1 1 ả ả ả ả ả 1 ố ốố)ốăố H¼nh 2.9. K¸t qu£ độ đo LPP và NPMI cõa thuªt to¡n học Online-OPE3 tr¶n hai bë dú li»u New York Times và PubMed khi thay đổi sè bước lặp T trong thuªt to¡n suy di¹n OPE3. Độ đo càng cao càng tèt. Chúng tôi ti¸n hành kh£o s¡t sè bước lặp T 2 f20; 30; 40; 50; 100g trong OPE3 thông qua thuªt to¡n học Online-OPE3 tr¶n hai bë dú li»u New York Times và PubMed. Theo H¼nh 2.9, chúng tôi th§y T = 50 đảm b£o k¸t qu£ c¡c độ đo tèt mà không tèn qu¡ nhi·u bước lặp. Chúng tôi cũng
13. 11 ti¸n hành đo thời gian thực hi»n thuªt to¡n học. Chúng tôi t½nh têng thời gian thực hi»n bước E và bước M cho méi thuªt to¡n học Online-OPE, Online-OPE3 và Online-OPE4. K¸t qu£ chi ti¸t được mô t£ trong B£ng 2.3. Bë dú li»u Phương ph¡p học Thời gian Độ đo LPP Độ đo NPMI Online-OPE 1022.21 -9.32 10.50 New York Online-OPE3 1737.18 -9.28 11.44 Times Online-OPE4 1298.88 -9.30 10.93 Online-OPE 402.23 -8.17 6.01 PubMed Online-OPE3 832.69 -8.07 7.09 Online-OPE4 636.45 -8.15 6.11 B£ng 2.3. B£ng thèng k¶ thời gian thực hi»n và độ đo cõa thuªt to¡n học Online-OPE, Online-OPE3 và Online-OPE4 (ν = 0:3) khi thực nghi»m tr¶n hai bë dú li»u New York Times và PubMed. 2.5. Sự hëi tụ cõa c¡c thuªt to¡n đề xu§t Định lý 2.1 (Sự hëi tụ cõa thuªt to¡n OPE3). Xem x²t hàm mục ti¶u f(θ) trong bài to¡n (2.1), cho trước v«n b£n d, tham sè β và α. X²t thuªt to¡n OPE3, với x¡c su§t 1, chúng ta có: (i) Với θ 2 ∆K , d¢y bi¶n Ut(θ) và Lt(θ) hëi tụ tới f(θ) khi t ! +1; (ii) D¢y nghi»m x§p x¿ fθtg hëi tụ tới điểm dừng/điểm cực trị địa phương cõa hàm mục ti¶u f(θ) khi t ! +1. Định lý 2.2 (Sự hëi tụ cõa thuªt to¡n OPE4). Xem x²t hàm mục ti¶u không lồi f(θ) cõa bài to¡n (2.1), cho trước v«n b£n d, tham sè β và α. X²t thuªt to¡n OPE4, với x¡c su§t 1, chúng ta có: (i) Với θ 2 ∆K , d¢y hàm x§p x¿ Ft(θ) hëi tụ tới f(θ) khi t ! +1, (ii) D¢y nghi»m x§p x¿ θt hëi tụ tới điểm tèi ưu cục bộ/điểm døng cõa hàm f(θ). 2.6. Mở rëng thuªt to¡n đề xu§t cho bài to¡n tèi ưu không lồi 2.7. K¸t luªn chương 2 Chúng tôi têng k¸t mët sè k¸t qu£ đạt được cõa chương như sau: • Trong chương này chúng tôi đã đề xu§t bèn thuªt to¡n tèi ưu mới OPE1, OPE2, OPE3 và OPE4 đº gi£i bài to¡n suy di¹n hªu nghi»m với mô h¼nh chõ đề ©n LDA, trong đó OPE3 và OPE4 thường hi»u qu£ hơn thuªt to¡n OPE. Do vªy, OPE3 và OPE4 đã được chúng tôi nghi¶n cùu mët c¡ch nghi¶m túc và đầy đủ tr¶n hai mặt lý thuy¸t và thực nghi»m. • C¡c c£i ti¸n khai th¡c theo hướng ti¸p cªn ng¨u nhi¶n hóa thông qua vi»c xem x²t hàm mục ti¶u là c¡c x§p x¿ ng¨u nhi¶n, sû dụng ph¥n phèi đều phù hñp với xu th¸ ti¸p cªn phương ph¡p ng¨u nhi¶n gi£i bài to¡n MAP không lồi; • Hơn núa, OPE3 và OPE4 hoàn toàn có thº mở rëng d¹ dàng để gi£i bài to¡n quy ho¤ch DC, mët lớp bài to¡n tèi ưu không lồi khó gi£i min[f(x) = g(x) − h(x)] x2Ω b¬ng c¡ch đặt tương ùng g1 := g và g2 := −h. C¡c k¸t qu£ tr¼nh bày trong chương 2 được chúng tôi tr¼nh bày trong bài b¡o "Stochastic bounds for inference in topic models" xu§t b£n trong kỷ y¸u hëi th£o quèc t¸ ICTA n«m 2016 và bài b¡o "Some methods for posterior inference in topic models" xu§t b£n tr¶n t¤p ch½ RD-ICT cõa Bë thông tin truy·n thông n«m 2018.
14. Chương 3 TÊNG QUÁT HÂA THUẬT TOÁN TÈI ƯU GIẢI BÀI TOÁN MAP KHÆNG LÇI TRONG MÆ HÌNH CHỦ ĐỀ 3.1. Giới thi»u Xem x²t bài to¡n ước lượng MAP trong c¡c mô h¼nh đồ thị x¡c su§t: x∗ = arg max [log P (D j x) + log P (x)] (3.1) x Ký hi»u g1(x) := log P (Djx) và g2(x) := log P (x), (3.1) được đưa v· bài to¡n tèi ưu: ∗ x = arg max [f(x) = g1(x) + g2(x)] (3.2) x Bài to¡n (3.2) khó gi£i khi hàm mục ti¶u f(x) không lãm. Mët v½ dụ minh họa là bài to¡n MAP trong mô h¼nh chõ đề LDA: K K ∗ X X X θ = arg max dj log θkβkj + (α − 1) log θk (3.3) θ2∆K j k=1 k=1 3.2. Thuªt to¡n GOPE Chúng tôi giới thi»u thuªt to¡n mới đặt t¶n là GOPE (vi¸t t­t cõa Generalized Online Maximum a Posteriori Estimation) để gi£i bài to¡n MAP (3.2). GOPE được tr¼nh bày chi ti¸t trong Thuªt to¡n 3.1. Thuªt to¡n 3. 1. GOPE: Generalized Online maximum a Posteriori Estimation Đầu vào: V«n b£n d, tham sè mô h¼nh fβ; αg và tham sè Bernoulli p 2 (0; 1) ∗ Đầu ra: θ là điểm cực đại cõa hàm f(θ) = g1(θ) + g2(θ) 1: Khởi t¤o θ1 trong mi·n ∆K g1 g2 2: G1 := p ; G2 := 1−p 3: for t = 1; 2;:::;T do 4: L§y ft có ph¥n phèi Bernoulli tø fG1(θ);G2(θ)g 5: trong đó fP (ft = G1(θ)) = p; P (ft = G2(θ)) = 1 − pg 1 Pt 6: Ft(θ) := t h=1 fh 0 7: e := arg max hF (θ ); xi t x2∆K t t et−θt 8: θt+1 := θt + t 9: end for GOPE đóng vai trá là bước suy di¹n cèt lãi khi học mô h¼nh LDA. Chúng tôi sû dụng GOPE thay cho OPE trong thuªt to¡n học Online-OPE và nhªn được thuªt to¡n học ng¨u nhi¶n mới đặt t¶n là Online-GOPE. 3.3. Sự hëi tụ cõa thuªt to¡n GOPE Định lý 3.1 (Sự hëi tụ cõa thuªt to¡n GOPE). X²t hàm mục ti¶u f(θ) trong bài to¡n (3.3), cho trước v«n b£n d, tham sè mô h¼nh fβ; αg và tham sè Bernoulli p 2 (0; 1). X²t GOPE, với x¡c su§t 1, chúng ta có: (i) Với b§t kỳ θ 2 ∆K , d¢y hàm Ft(θ) hëi tụ tới f(θ) khi t ! +1; (ii) D¢y nghi»m x§p x¿ θt hëi tụ tới điểm døng/cực đại địa phương cõa hàm mục ti¶u f(θ) với tèc độ hëi tụ là O(1=t). 12
15. 13 3.4. Đánh gi¡ thực nghi»m 3.4.1. C¡c bë dú li»u thực nghi»m Chúng tôi ti¸n hành thực nghi»m cho c¡c c£i ti¸n tr¶n hai bë dú li»u lớn bao gồm c¡c tªp v«n b£n dài: bë dú li»u New York Times (NYT) bao gồm 300.000 bài tin tùc và bë PubMed (PUB) bao gồm 330.000 bài b¡o tø trung t¥m PubMed. 3.4.2. Độ đo đánh gi¡ thực nghi»m Chúng tôi sû dụng hai độ đo thường được dùng trong mô h¼nh chõ đề, đó là Log Predictive Probability (LPP) và Normalised Pointwise Mutual Information (NPMI). 3.4.3. Thi¸t lªp c¡c tham sè 1 • Tham sè mô h¼nh: Chúng tôi thi¸t lªp sè chõ đề K = 100, tham sè Dirichlet α = K và si¶u 1 tham sè η = K . • Tham sè suy di¹n: Chúng tôi chọn sè bước lặp cõa thuªt to¡n suy di¹n T = 50 và tham sè Bernoulli p 2 f0:10; 0:15;:::; 0:85; 0:90g cho méi bë dú li»u và độ đo. • Tham sè học: Chúng tôi chọn k½ch thước mini-batch S = jCtj = 5000, thi¸t lªp tham sè κ = 0:9 và τ = 1. 3.4.4. K¸t qu£ thực nghi»m K¸t qu£ thực hi»n thuªt to¡n Online-GOPE khi thay đổi tham sè p được mô t£ trong H¼nh 3.1. Theo H¼nh 3.1, chúng ta th§y Online-GOPE đạt hi»u qu£ tèt nh§t tr¶n bë New York Times với đë đo LPP khi lựa chọn p = 0:35 và với độ đo NPMI khi lựa chọn p = 0:75, Online-GOPE đạt hi»u qu£ tèt nh§t tr¶n bë PubMed với độ đo LPP khi lựa chọn p = 0:4, và với độ đo NPMI khi lựa chọn p = 0:45. Chúng tôi so s¡nh k¸t qu£ thực hi»n cõa Online-GOPE với gi¡ trị cõa p được lựa chọn tèt với c¡c thuªt to¡n Online-VB, Online-CVB0, Online-CGS và Online-OPE. C¡c k¸t qu£ được mô t£ trong H¼nh 3.2. -GOPE on New York Times 0 p = 0.90 0 p = 0.80 p = 0.70 00 p = 0.60 0 p = 0.50 p = 0.40 0 0 0 0 15 30 45 60 p = 0.30 6.0 p = 0.20 p = 0.10 4.5 p = 0.75 p = 0.65 3.0 p = 0.45 p = 0.35 .5 p = 0.25 p = 0.15 ố(ốố H¼nh 3.1. K¸t qu£ thực hi»n Online-GOPE với tham sè Bernoulli p được lựa chọn kh¡c nhau tr¶n hai độ đo LPP và NPMI. Độ đo càng cao càng tèt.
16. 14 1 1 1 1 1 1 10 1 10 100 0 0 0 0 0 0 6.0 4.5 3.0 1.5 0 0 0 0ă) H¼nh 3.2. Độ đo LPP và NPMI cõa thuªt to¡n học Online-OPE, Online-VB, Online-CVB, Online-CGS và Online-GOPE tr¶n bë dú li»u New York Times và PubMed. Độ đo càng cao càng tèt. 3.5. Mở rëng thuªt to¡n gi£i bài to¡n tèi ưu không lồi Chúng tôi mở rëng thuªt to¡n GOPE cho bài to¡n tèi ưu hóa không lồi (3.2): ∗ x = arg max [f(x) = g1(x) + g2(x)] x Chi ti¸t cõa thuªt to¡n GOPE mở rëng cho bài to¡n không lồi têng qu¡t được tr¼nh bày trong Thuªt to¡n 3.3. Thuªt to¡n 3. 3. GOPE mở rëng cho bài to¡n không lồi têng qu¡t Đầu vào: Tham sè Bernoulli p 2 (0; 1) ∗ Đầu ra: x là điểm cực đại cõa hàm f(x) = g1(x) + g2(x) tr¶n mi·n Ω 1: Khởi t¤o x1 trong mi·n Ω g1 g2 2: G1 := p ; G2 := 1−p 3: for t = 1; 2;:::;T do 4: L§y ft có ph¥n phèi Bernoulli tø fG1;G2g trong đó fP (ft = G1) = p; P (ft = G2) = 1 − pg 1 Pt 5: Ft := t h=1 fh 0 6: at := arg maxx2ΩhFt (xt); xi at−xt 7: xt+1 := xt + t 8: end for 3.6. K¸t luªn chương 3 Trong chương này chúng tôi đã thành công trong vi»c đề xu§t GOPE gi£i hi»u qu£ bài to¡n MAP không lồi trong mô h¼nh chõ đề đảm b£o hëi tụ nhanh được đảm b£o b¬ng cơ sở lý thuy¸t và thực nghi»m. Hơn núa, chúng tôi nhªn th§y: • Trong thuªt to¡n GOPE, vi»c chia hàm mục ti¶u f ban đầu thành hai ph¦n g1 và g2 tương đối d¹ dàng và có thº chia theo nhi·u c¡ch. Điều đó thº thuªt to¡n GOPE đảm b£o linh ho¤t. • C¡ch thùc thực hi»n GOPE không có qu¡ nhi·u ràng buëc tr¶n hàm mục ti¶u f n¶n có thº ¡p dụng tèt với hàm mục ti¶u lồi hoặc không lồi; • Thuªt to¡n GOPE có thº ¡p dụng tèt cho bài to¡n quy ho¤ch DC có hàm mục ti¶u f là hi»u cõa hai hàm lồi f = g − h v¼ có thº đặt g1 := g và g2 := −h, n¶n hàm f được vi¸t l¤i dưới d¤ng f = g1 + g2 có d¤ng trong thuªt to¡n GOPE; • Thuªt to¡n GOPE có thº ¡p dụng để gi£i bài to¡n hi»u ch¿nh θ∗ = arg min L(θ) + λR(θ) trong đó R(θ) là ph¦n hi»u ch¿nh, λ là h» sè hi»u ch¿nh, thông thường λ 2 (0; 1) khi đặt g1 := L(θ) và g2 := λR(θ)
17. Chương 4 NGẪU NHIÊN BERNOULLI CHO BÀI TOÁN MAP KHÆNG LÇI VÀ ỨNG DỤNG Trong chương này chúng tôi ti¸p tục nghi¶n cùu bài to¡n ước lượng MAP không lồi trong c¡c mô h¼nh đồ thị x¡c su§t. Chúng tôi sû dụng ng¨u nhi¶n hóa Bernoulli với x¡c su§t p 2 (0; 1) k¸t hñp với hai bi¶n ng¨u nhi¶n để thi¸t k¸ thuªt to¡n tèi ưu ng¨u nhi¶n BOPE gi£i hi»u qu£ bài to¡n MAP không lồi. Tø đó, chúng tôi ¡p dụng thành công BOPE vào bài to¡n ph¥n t½ch v«n b£n và bài to¡n gñi ý. 4.1. Giới thi»u X²t bài to¡n MAP có d¤ng sau: x∗ = arg max[log P (Djx) + log P (x)] (4.1) x trong đó P (Djx) ký hi»u là likelihood cõa bi¸n quan s¡t D, P (x) ch½nh là prior cõa bi¸n ©n x và P (D) là x¡c su§t bi¶n cõa D. Đóng góp cõa chúng tôi là đề xu§t thuªt to¡n ng¨u nhi¶n BOPE sû dụng ng¨u nhi¶n Bernoulli và hai bi¶n ng¨u nhi¶n. Chúng tôi chùng minh được BOPE hëi tụ với O(1=T ), đ¥y là tèc độ hëi tụ tèt nh§t cho bài to¡n MAP hi»n t¤i. Chúng tôi cũng ph¡t hi»n ra r¬ng BOPE có vai trá hi»u ch¿nh tèt. Sû dụng BOPE là thuªt to¡n suy di¹n thi¸t k¸ thuªt to¡n học ng¨u nhi¶n Online-BOPE học c¡c mô h¼nh chõ đề ở quy mô lớn. Hi»u qu£ cõa BOPE v· mặt thực nghi»m được chúng tôi làm rã thông qua ùng dụng BOPE vào bài to¡n ph¥n t½ch v«n b£n và bài to¡n h» gñi ý. Với c¡c ưu vi»t cõa BOPE, chúng tôi có thº ¡p dụng rëng r¢i BOPE vào gi£i quy¸t cho c¡c bài to¡n không lồi phùc t¤p kh¡c xu§t hi»n trong học m¡y. Chi ti¸t v· BOPE được tr¼nh bày trong Thuªt to¡n 4.1. Thuªt to¡n 4. 1. BOPE gi£i bài to¡n MAP không lồi Đầu vào: Tham sè Bernoulli p 2 (0; 1) Đầu ra: x∗ là điểm cực đại cõa hàm sè f(x) = log P (D j x) + log P (x) tr¶n mi·n Ω 1: Khởi t¤o x1 trong Ω log P (Djx) log P (x) 2: G1(x) := p ; G2(x) := 1−p l u 3: f1 := G1(x) và f1 := G2(x) 4: for t = 2; 3;:::; 1 do l l l 5: L§y ft có ph¥n phèi Bernoulli tø fG1(x);G2(x)g trong đó P (ft = G1) = p; P (ft = G2) = 1 − p 1 Pt l 6: Lt := t h=1 fh l 0 7: at := arg maxx2Ω l l at−xt 8: xt+1 := xt + t u u u 9: L§y ft có ph¥n phèi Bernoulli tø fG1(x);G2(x)g trong đó P (ft = G1) = p; P (ft = G2) = 1 − p 1 Pt u 10: Ut := t h=1 fh u 0 11: at := arg maxx2Ω u u at −xt 12: xt+1 := xt + t 13: xt+1 := arg max u l f(x) x2fxt+1; xt+1g 14: end for 4.2. Thuªt to¡n BOPE gi£i bài to¡n MAP không lồi 4.2.1. Ý tưởng x¥y dựng thuªt to¡n BOPE 4.2.2. Sự hëi tụ cõa thuªt to¡n BOPE Định lý 4.1 (Sự hëi tụ cõa BOPE). Gi£ sû r¬ng g1(x) và g2(x) có đạo hàm li¶n tục tr¶n mi·n đóng Ω. Cho trước tham sè Bernoulli p 2 (0; 1), với x¡c su§t 1, d¢y nghi»m fxtg thu được bởi 15
18. 16 Thuªt to¡n 4.1 đảm b£o hëi tụ đến điểm cực đại địa phương hoặc điểm døng x∗ cõa hàm mục ti¶u f(x) với tèc độ hëi tụ O(1=T ) trong đó T là sè bước lặp thực hi»n. 4.2.3. Vai trá hi»u ch¿nh cõa thuªt to¡n BOPE Định lý 4.2 (T½nh hi»u ch¿nh cõa BOPE). Gi£ sû cho trước tham sè Bernoulli p 2 (0; 1), x²t thuªt to¡n BOPE gi£i bài to¡n MAP không lồi (4.1). Khi đó, thuªt to¡n BOPE đưa v· tèi ưu g1(x) g2(x) hàm mục ti¶u mới có d¤ng f(x) + R(g1; g2; p) với R(g1; g2; p) = h(t; p)( p − 1−p ), trong đó h(t; p) ! 0 khi sè váng lặp t ! 1. Như vªy, BOPE là mët kỹ thuªt hi»u ch¿nh với R(g1; g2; p) là thành ph¦n hi»u ch¿nh và tham sè Bernoulli p là tham sè hi»u ch¿nh. 4.2.4. Mở rëng cho bài to¡n tèi ưu không lồi têng qu¡t Chúng tôi cũng đã làm rã ưu điểm vượt trëi cõa BOPE so với c¡c thuªt to¡n suy di¹n kh¡c như VB, CVB, CGS, FW, OPE, K¸t qu£ đèi chi¸u được chúng tôi têng k¸t trong B£ng 4.1. Phương ph¡p suy di¹n Tèc độ hëi tụ Ng¨u nhi¶n Linh ho¤t Hi»u ch¿nh VB, CVB , CVB0 − − − − SMM, CCCP − − − − CGS − Có − − PMD O(T −1=2) Có − − HAMCMC O(T −1=3) Có − − OPE O(1=T ) Ph¥n phèi đều Có − BOPE O(1=T ) Ph¥n phèi Bernoulli Có Có B£ng 4.1: So s¡nh v· mặt lý thuy¸t cõa c¡c phương ph¡p suy di¹n tr¶n c¡c ti¶u chu©n như tèc độ hëi tụ, t½nh ng¨u nhi¶n, t½nh linh ho¤t và t½nh hi»u ch¿nh. Ký hi»u T là sè l¦n lặp và '-' biºu thị ’không x¡c định’. Chúng tôi ph¡t hi»n BOPE có ưu th¸ vượt trëi so với c¡c phương ph¡p suy di¹n đương đại kh¡c. 4.3. Áp dụng BOPE vào mô h¼nh LDA cho ph¥n t½ch v«n b£n 4.3.1. Suy di¹n MAP cho tøng v«n b£n Chúng tôi ti¸p tục xem x²t bài to¡n MAP đối với tøng v«n b£n d trong mô h¼nh chõ đề: K K ∗ X X X θ = arg max dj log θkβkj + (α − 1) log θk (4.2) θ2∆K j k=1 k=1 trong đó tham sè α < 1. Chúng tôi có thº ¡p dụng BOPE để gi£i tèt bài to¡n (4.2) với hàm P PK PK mục ti¶u f(θ) = j dj log k=1 θkβkj + (α − 1) k=1 log θk được ph¥n r¢ thành 2 thành ph¦n P PK PK g1(θ) = j dj log k=1 θkβkj và g2(θ) = (α − 1) k=1 log θk. Thay th¸ thuªt to¡n OPE trong thuªt to¡n học Online-OPE bởi BOPE, chúng tôi thu được thuªt to¡n học Online-BOPE. 4.3.2. Đánh gi¡ thực nghi»m • C¡c thuªt to¡n suy di¹n: Chúng tôi ti¸n hành so s¡nh thuªt to¡n suy di¹n BOPE với c¡c phương ph¡p suy di¹n đương đại như VB, CVB, CVB0, CGS và OPE. • C¡c phương ph¡p học: Chúng tôi ti¸n hành c¡c thực nghi»m để điều tra t½nh hi»u qu£ cõa Online-BOPE khi so s¡nh với c¡c phương ph¡p học ng¨u nhi¶n kh¡c như: Online-CGS, Online- CVB0, Online-VB, Online-OPE. a. C¡c bë dú li»u thực nghi»m Chúng tôi sû dụng 5 bë dú li»u v«n b£n lớn thuëc hai nhóm dú li»u v«n b£n dài và dú li»u v«n b£n ng­n. Mô t£ chi ti¸t cho tøng tªp dú li»u được hiºn thị trong B£ng 4.2.
19. 17 Bë dú li»u K½ch thước bë dú li»u Độ dài v«n b£n TB Tø điển V New York Times 300,000 325.13 102,661 PubMed 330,000 65.12 141,044 Yahoo 517,770 4.73 24,420 Twitter 1,457,687 10.14 89,474 NYT-Titles 1,664,127 5.15 55,488 B£ng 4.2: B£ng mô t£ n«m bë dú li»u thực nghi»m b. Thi¸t lªp tham sè c. Độ đo đánh gi¡ thực nghi»m Chúng tôi ti¸p tục sû dụng hai độ đo Log Predictive Probability (LPP) và Normalised Pointwise Mutual Information (NPMI) để đánh gi¡ k¸t qu£ thực nghi»m. d. K¸t qu£ thực nghi»m Với dú li»u v«n b£n dài: Chúng tôi so s¡nh Online-BOPE với Online-VB, Online-CVB0, Online- CGS và Online-OPE tr¶n hai bë dú li»u New York Times và PubMed. K¸t qu£ chi ti¸t được mô t£ trong H¼nh 4.3. New New 2 10 8 LPP NPMI 6 4 0 0 0 1ốốốă000ả 10(x5000) ) Pubmed 7.5 6.0 4.5 NPMI 3.0 1.5 1-0 1ă000) H¼nh 4.3. K¸t qu£ cõa c¡c phương ph¡p học ng¨u nhi¶n tr¶n New York Times và PubMed. Độ đo cao hơn th¼ tèt hơn. Chúng tôi nhªn th§y Online-BOPE thường cho k¸t qu£ tèt nh§t. Với dú li»u v«n b£n ng­n: Chúng tôi ti¸p tục điều tra t½nh hi»u qu£ cõa Online-BOPE tr¶n tªp c¡c v«n b£n ng­n như Twitter, NYT-Titles, Yahoo. Chúng tôi cho th§y r¬ng BOPE giúp Online- BOPE tèt hơn c¡c phương ph¡p so s¡nh tr¶n c¡c v«n b£n ng­n ở mët sè kh½a c¤nh như t½nh dự đoán, t½nh têng qu¡t và ng«n chặn sự qu¡ khớp (xem H¼nh 4.4).
20. 18 -TITLES 0 00 00 00 0 100 200 300 4 2 0 .(x5000 ốốố(x5000 ốố−ố(x5000) Online-BOPE Online-OPE Online-VB Online-CVB0 Online-CGS H¼nh 4.4. K¸t qu£ cõa c¡c phương ph¡p học ng¨u nhi¶n tr¶n c¡c bë dú li»u v«n b£n ng­n: NYT-Titles, Twitter và Yahoo. Chúng tôi th§y Online-BOPE thường cho k¸t qu£ tèt nh§t tr¶n c£ hai độ đo LPP và NPMI. Chúng tôi quan s¡t th§y sự qu¡ khớp cõa Online-VB và Online-CVB0 trong H¼nh 4.4. Cụ thº chúng tôi th§y độ đo LPP và NPMI cõa Online-VB và Online-CVB0 bị gi£m theo sè lượng v«n b£n học trong khi độ đo LPP và NPMI cõa Online-CGS, Online-OPE và Online-BOPE v¨n luôn t«ng theo sè lưñng v«n b£n học được. Điều đó có nghĩa là kh£ n«ng têng qu¡t cõa mô h¼nh gi£m khi học bởi Online-VB và Online-CVB và tr¶n ba bë dú li»u v«n b£n ng­n, đặc bi»t là NYT-Titles và Yahoo. -TITLES 0 0 0 0 0 0 0 0 00 00 00 00 0 400 800 1200 6 4 2 0 ă ố)ố.ốă ốốốă) H¼nh 4.5. K¸t qu£ cõa c¡c phương ph¡p học ng¨u nhi¶n tr¶n c¡c dú li»u v«n b£n ng­n: NYT-Titles, Twitter và Yahoo sau 5 epochs. Chúng tôi ph¡t hi»n ra r¬ng Online-BOPE cho k¸t qu£ tèt nh§t. Chúng tôi ph¡t hi»n ch§t lượng cõa Online-BOPE v¨n tèt sau 5 epoch. Tuy nhi¶n, hi»n tượng qu¡ khớp cõa Online-VB và Online-CVB0 x£y ra càng t«ng. Độ đo LPP và NPMI cõa Online-VB và Online-CVB0 có xu hướng gi£m m¤nh theo sè v«n b£n hu§n luy»n, nh§t là độ đo LPP, tùc là kh£ n«ng têng qu¡t cõa mô h¼nh gi£m d¦n theo sè v«n b£n học và sè epochs.
21. 19 4.4. Áp dụng BOPE cho bài to¡n h» gñi ý 4.4.1. Mô h¼nh CTMP Trong qu¡ tr¼nh học mô h¼nh CTMP, chúng ta ph£i cªp nhªt v²c tơ tỷ l» chõ đề θj. Chúng ta có thº t½nh ước lượng điểm cõa tỷ l» chõ đề địa phương θj tø hàm mục ti¶u: ! X X X λ g(θ ) = (α − 1) log θ + cν log θ β − kθ − µ k2 (4:15) j jk j jk kν 2 j j 2 k ν k trong đó hàm mục ti¶u g(θj) là không lồi khi α < 1. Chúng tôi nhªn th§y BOPE có nhi·u ưu th¸ vượt trëi hơn OPE. V¼ vªy, chúng tôi có thº ¡p dụng BOPE để học tham sè θj trong mô h¼nh CTMP. 4.4.2. Đánh gi¡ thực nghi»m a. C¡c bë dú li»u thực nghi»m Chúng tôi sû dụng 2 bë dú li»u CiteULike và Movielens 1M để thực nghi»m so s¡nh mô h¼nh CTMP với thuªt to¡n suy di¹n OPE và BOPE. Bë dú li»u Sè người dùng Sè s£n ph©m Sè x¸p h¤ng Độ dài TB mô t£ CiteULike 5,551 16,890 204,986 66.6 MovieLens 1M 6,040 3,952 1,000,209 4.7 B£ng 4.3: Thèng k¶ c¡c bë dú li»u thực nghi»m. Độ thưa thớt biºu thị tỷ l» cõa c¡c s£n ph©m không có b§t kỳ x¸p h¤ng t½ch cực nào trong méi ma trªn x¸p h¤ng R. b. Độ đo đánh gi¡ thực nghi»m C¡c dự đoán được đánh gi¡ theo độ đo Precision và Recall. Để thuªn ti»n, Precision và Recall t¤i top-M được vi¸t t­t l¦n lượt là pre@M và rec@M được định nghĩa: 1 X M c 1 X M c prec@M = u ; rec@M = u U M U M u u u c trong đó Mu là sè s£n ph©m ch½nh x¡c xu§t hi»n trong đề xu§t top −M cho người dùng u và Mu là sè s£n ph©m mà người dùng u đã đánh gi¡ t½ch cực. c. K¸t qu£ thực nghi»m Chúng tôi xem x²t t½nh hi»u qu£ cõa BOPE thông qua vi»c kh£o s¡t £nh hưởng cõa tham sè ti¶n nghi»m Dirichlet α, tham sè λ và sè chõ đề K trong mô h¼nh CTMP. STT Tham sè cè định Tham sè Bernoulli p Tham sè kh£o s¡t 1 λ = 1000;K = 100 p = 0:9 α 2 f1; 0:1; 0:01; 0:001; 0:0001g 2 α = 0:01; λ = 1000 p = 0:9 K 2 f50; 100; 150; 200; 250g 3 λ = 1000;K = 100 p = 0:7 α 2 f1; 0:1; 0:01; 0:001; 0:0001g 4 α = 1;K = 100 p = 0:7 λ 2 f1; 10; 100; 1000; 10000g 5 α = 1; λ = 1000 p = 0:7 K 2 f50; 100; 150; 200; 250g B£ng 4.4: C¡c kịch b£n kh£o s¡t thực nghi»m cõa chúng tôi. Mô h¼nh CTMP phụ thuëc vào tham sè ti¶n nghi»m Dirichlet α, tham sè λ và sè chõ đề K. Chúng tôi cè định tham sè λ = 1000, sè chõ đề K = 100, kh£o s¡t tham sè ti¶n nghi»m Dirichlet α 2 f1; 0:1; 0:01; 0:001; 0:0001g. K¸t qu£ thực nghi»m được mô t£ trong H¼nh 4.7 và H¼nh 4.10, chúng tôi th§y r¬ng sû dụng thuªt to¡n suy di¹n BOPE cho k¸t qu£ tèt hơn OPE tr¶n hai độ đo và tr¶n hai tªp dú li»u.
22. 20 alpha=1 alpha=0.1 alpha=0.01 alpha=0.001 alpha=0.0001 3.5 4.0 4.0 3.0 3.6 3.6 3.2 3.2 2.5 3.0 3.0 2.4 2.4 2.0 2.4 2.4 1.8 1.8 Precision (%) Precision 1.5 1.6 1.6 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 24 24 20 20 20 20 18 15 15 16 15 12 12 10 10 10 Recall (%) Recall 8 6 5 5 5 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 Top Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.7. Ảnh hưởng cõa tham sè ti¶n nghi»m Dirichlet α đến CTMP khi sû dụng OPE và BOPE suy di¹n tr¶n bë CiteULike. Chúng tôi thi¸t lªp tham sè λ = 1000, sè chõ đề K = 100 và tham sè Bernoulli p = 0:9. Độ đo càng cao càng tèt. alpha=1 alpha=0.1 alpha=0.01 alpha=0.001 alpha=0.0001 20 20 20 20 20 (%) 16 16 16 16 15 12 12 12 12 Precision 10 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 45 40 40 40 40 30 30 30 30 30 20 20 20 20 Recall (%) Recall 15 10 10 10 10 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 Top Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.10. Ảnh hưởng cõa tham sè ti¶n nghi»m Dirichlet α đến CTMP khi sû dụng OPE và BOPE là thuªt to¡n suy di¹n tr¶n bë MovieLens 1M. Chúng tôi thi¸t lªp tham sè λ = 1000, sè chõ đề K = 100 và tham sè Bernoulli p = 0:7. Độ đo càng cao càng tèt. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 1, sè chõ đề K = 100 và chọn tham sè Bernoulli p = 0:7, sau đó thay đêi tham sè λ 2 f1; 10; 100; 1000; 10000g. K¸t qu£ thực nghi»m được tr¼nh bày trong H¼nh 4.11 và H¼nh 4.12.
23. 21 λ = 1 λ = 10 λ = 100 λ = 1000 λ = 10000 5 6.0 6.0 3.0 4 3.0 (%) 4.5 4.5 2.4 3 2.4 3.0 3.0 1.8 2 1.8 Precision 1.5 1.5 1.2 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 24 30 30 24 24 18 20 20 16 16 12 Recall (%) Recall 10 10 8 8 6 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 Top Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.11. Ảnh hưởng cõa tham sè λ đến mô h¼nh CTMP khi sû dụng OPE và BOPE là thuªt to¡n suy di¹n và thực nghi»m tr¶n bë CiteULike. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 1, sè chõ đề K = 100 và tham sè Bernoulli p = 0:7. Độ đo càng cao càng tèt. λ = 1 λ = 10 λ = 100 λ = 1000 λ = 10000 20 20 20 20 20 (%) 16 16 16 16 15 12 12 12 12 Precision 10 8 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 45 40 40 40 40 30 30 30 30 30 20 20 Recall (%) Recall 20 20 15 10 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 25 50 75 100 Top Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.12. Ảnh hưởng cõa tham sè λ đến mô h¼nh CTMP khi sû dụng OPE và BOPE là thuªt to¡n suy di¹n và thực nghi»m tr¶n bë MovieLens 1M. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 1, sè chõ đề K = 100 và tham sè Bernoulli p = 0:7. Độ đo càng cao càng tèt. Lưu ý r¬ng λ là mët tham sè đặc trưng cho dao động cõa µ quanh θ. Qua H¼nh 4.11 và 4.12, chúng tôi th§y r¬ng khi tham sè α = 1 và K = 100, mô h¼nh CTMP tèt hơn với trường hñp λ = 1 và λ = 10, trong trường hñp λ = 1000 hoặc λ = 10000 th¼ mô h¼nh cho k¸t qu£ x§u đi. Đồng thời chúng tôi th§y r¬ng với c¡c λ thực nghi»m th¼ CTMP-BOPE luôn cho k¸t qu£ tèt hơn CTMP-OPE, thªm ch½ trong trường hñp x§u λ = 1000 hay λ = 10000. Để điều tra £nh hưởng cõa sè chõ đề K đến mô h¼nh CTMP, chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 0:01, tham sè λ = 1000 và chọn tham sè Bernoulli p = 0:9, sau đó thay đổi sè chõ đề K 2 f50; 100; 150; 200g. Nhúng k¸t qu£ thực nghi»m này được mô t£ trong H¼nh 4.13 và H¼nh 4.14.
24. 22 K=50 K=100 K=150 K=200 6 6 6 6 (%) 5 5 5 5 4 4 4 4 3 3 3 3 Precision 2 2 2 2 20 40 60 80100 20 40 60 80100 20 40 60 80100 20 40 60 80100 30 30 32 32 24 24 24 24 18 18 16 16 Recall (%) Recall 12 12 6 8 8 20 40 60 80100 20 40 60 80100 20 40 60 80100 20 40 60 80100 Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.13. Ảnh hưởng cõa sè chõ đề K đến mô h¼nh CTMP khi sû dụng OPE và BOPE làm phương ph¡p suy di¹n và ti¸n hành tr¶n CiteULike. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 0:01, tham sè λ = 1000 và tham sè Bernoulli p = 0:9. Độ đo càng cao càng tèt. K=50 K=100 K=150 K=200 21 24 24 21 18 (%) 20 20 18 15 16 16 15 12 12 12 12 Precision 9 9 20 40 60 80100 20 40 60 80100 20 40 60 80100 20 40 60 80100 48 50 50 40 40 40 40 32 32 30 30 24 24 20 Recall (%) Recall 20 16 16 20 40 60 80100 20 40 60 80100 20 40 60 80100 20 40 60 80100 Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.14. Ảnh hưởng cõa sè chõ đề K đến mô h¼nh CTMP khi sû dụng OPE và BOPE làm phương ph¡p suy di¹n và ti¸n hành tr¶n bë MovieLens 1M. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet trước α = 0:01, tham sè λ = 1000 và tham sè Bernoulli p = 0:9. Độ đo càng cao càng tèt. Chúng tôi điều tra sự £nh hưởng cõa sè chõ đề K khi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 1, tham sè λ = 1000 và chọn tham sè Bernoulli p = 0:7. Chúng tôi thay đổi sè chõ đ· K 2 f50; 100; 150; 200; 250g. C¡c k¸t qu£ thực nghi»m này được mô t£ trong H¼nh 4.15 và 4.16. Thông qua H¼nh 4.15 và 4.16 th§y r¬ng £nh hưởng cõa sè chõ đề K rã ràng hơn so với α và λ trong mô h¼nh CTMP. Sè lượng chõ đề ©n K thº hi»n sự phùc t¤p cõa mô h¼nh và phụ thuëc vào tªp dú li»u. Qua c¡c k¸t qu£, chúng tôi th§y r¬ng CTMP-BOPE thường tèt hơn CTMP-BOPE. Theo H¼nh 4.15, CTMP-BOPE đặc bi»t tèt hơn CTMP-OPE khi lựa chọn tham sè Bernoulli p = 0:7 và sè chõ đề K = 200 hoặc K = 250 và tr¶n bë dú li»u CiteULike.
25. 23 K=50 K=100 K=150 K=200 K=250 6.0 6.0 6.0 2.5 3.0 4.5 4.5 4.5 2.0 2.4 3.0 3.0 1.8 3.0 1.5 Precision (%) 1.5 1.5 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 20 32 32 32 24 15 24 24 24 16 10 16 16 16 Recall (%) Recall 5 8 8 8 8 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 Top Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.15. Ảnh hưởng cõa sè chõ đề K đến mô h¼nh CTMP khi sû dụng OPE và BOPE là phương ph¡p suy di¹n và ti¸n hành tr¶n CiteULike. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 1, tham sè λ = 1000 và tham sè Bernoulli p = 0:7. Độ đo càng cao càng tèt. K=50 K=100 K=150 K=200 K=250 24 24 25 20 20 20 (%) 20 20 16 16 16 16 12 15 12 12 12 Precision 10 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 45 40 40 40 40 30 30 30 30 30 20 20 20 20 Recall (%) Recall 15 10 10 10 25 50 75100 25 50 75100 25 50 75100 25 50 75100 25 50 75100 Top Top Top Top Top CTMP-OPE CTMP-BOPE H¼nh 4.16. Ảnh hưởng cõa sè chõ đề K đến mô h¼nh CTMP khi sû dụng OPE và BOPE là phương ph¡p suy di¹n và ti¸n hành tr¶n bë MovieLens 1M. Chúng tôi thi¸t lªp tham sè ti¶n nghi»m Dirichlet α = 1, tham sè λ = 1000 và tham sè Bernoulli p = 0:7. Độ đo càng cao càng tèt. 4.5. K¸t luªn chương 4 Trong chương này, chúng tôi đã đề xu§t thuªt to¡n BOPE sû dụng t½nh ng¨u nhi¶n cõa ph¥n phèi Bernoulli để gi£i bài to¡n MAP đảm b£o ch§t lưñng và tèc độ hëi tụ gièng như OPE, đó là đặc điểm quan trọng nh§t trong sè c¡c phương ph¡p suy di¹n hi»n đại. Chúng tôi chùng minh được BOPE có hi»u qu£ trong bài to¡n ph¥n t½ch v«n b£n và bài to¡n h» thèng gñi ý, đồng thời tham sè Bernoulli p trong BOPE có vai trá quan trọng giúp BOPE có nhúng ưu điểm nêi bªt như t½nh hi»u ch¿nh và t½nh linh ho¤t tèt, gi£m hay tr¡nh hi»n tượng qu¡ khớp đặc bi»t là v«n b£n ng­n. Chúng tôi x¡c nhªn r¬ng BOPE là mët ùng cû vi¶n tèt cho bài to¡n MAP không lồi và hoàn toàn mở rëng cho bài to¡n tèi ưu không lồi têng qu¡t.
26. KẾT LUẬN Trong luªn ¡n chúng tôi đã nghi¶n cùu v· bài to¡n cực đại hóa x¡c su§t hªu nghi»m (MAP) không lồi thường xu§t hi»n trong học m¡y. Qua đó chúng tôi đã t¼m hiºu c¡c c¡ch ti¸p cªn gi£i bài to¡n MAP không lồi. Tr¶n cơ sở đó, luªn ¡n đã đề xu§t được mët sè thuªt to¡n ng¨u nhi¶n gi£i hi»u qu£ bài to¡n MAP không lồi trong mët sè mô h¼nh x¡c su§t. Sự hi»u qu£ cõa c¡c thuªt to¡n đề xu§t được xem x²t đầy đủ tr¶n c£ hai kh½a c¤nh lý thuy¸t và thực nghi»m. C¡c thuªt to¡n đề xu§t được chùng minh đảm b£o hëi tụ với tèc độ nhanh thông qua công cụ ý thuy¸t x¡c su§t thèng k¶ và lý thuy¸t tèi ưu. Thông qua thực nghi»m triºn khai bài to¡n suy di¹n hªu nghi»m trong mô h¼nh chõ đề tr¶n n«m bë dú li»u lớn và triºn khai bài to¡n MAP với mô h¼nh CTMP trong h» gñi ý, chúng tôi đảm b£o r¬ng c¡c đề xu§t hi»u qu£ cao hơn và có kh£ n«ng ¡p dụng tèt so với c¡c phương ph¡p đương đại. Thông qua nghi¶n cùu kỹ lưỡng v· mặt lý thuy¸t và thực nghi»m đã chùng minh được t½nh ưu vi»t cõa c¡c thuªt to¡n đề xu§t. A. K¸t qu£ đạt được cõa luªn ¡n (1) Luªn ¡n đề xu§t mët nhóm thuªt to¡n tèi ưu ng¨u nhi¶n đặt t¶n là OPE1, OPE2, OPE3 và OPE4 dựa tr¶n ph¥n phèi đều cùng với k¸t hñp hai bi¶n ng¨u nhi¶n để gi£i bài to¡n suy di¹n hªu nghi»m với mô h¼nh chõ đề, trong đó OPE3 và OPE4 là hi»u qu£ nh§t. Sự hëi tụ cõa OPE3 và OPE4 được chùng minh nghi¶m túc b¬ng công cụ gi£i t½ch, lý thuy¸t x¡c su§t và tèi ưu. (2) Chúng tôi ti¸p tục đề xu§t GOPE b¬ng sû dụng ph¥n phèi rời r¤c Bernoulli và lý thuy¸t x§p x¿ ng¨u nhi¶n để gi£i bài to¡n MAP không lồi. Thuªt to¡n GOPE có t½nh linh ho¤t và têng qu¡t do có mặt cõa tham sè Bernoulli p 2 (0; 1) đóng vai trá là tham sè hi»u ch¿nh cõa thuªt to¡n. Chúng tôi đã đánh gi¡ sự hi»u qu£ cõa GOPE khi ¡p dụng cho bài to¡n MAP với mô h¼nh chõ đề đầy đủ tr¶n hai phương di»n lý thuy¸t và thực nghi»m với dú li»u đầu vào lớn và cao chi·u. (3) Đề xu§t thuªt to¡n BOPE là mët thuªt to¡n ng¨u nhi¶n hi»u qu£ có t½nh têng qu¡t, linh ho¤t cao vượt trëi hơn c¡c thuªt to¡n kh¡c, đặc bi»t là hi»u ch¿nh. Thông qua khai th¡c ng¨u nhi¶n Bernoulli và c¡c bi¶n ng¨u nhi¶n, chúng tôi đã thu được thuªt to¡n BOPE cho bài to¡n MAP không lồi trong c¡c mô h¼nh đồ thị x¡c su§t. Đồng thời BOPE được ¡p dụng thành công vào bài to¡n ph¥n t½ch v«n b£n và bài to¡n h» gñi ý. Chúng tôi th§y r¬ng c¡c đề xu§t đáp ùng tèt c¡c y¶u c¦u cõa thuªt to¡n tèi ưu cho bài to¡n không lồi xu§t hi»n trong học m¡y: c¡ch vªn hành thuªt to¡n đơn gi£n, th½ch nghi tèt với nhi·u mô h¼nh thực t¸, có tèc độ hëi tụ nhanh đã được kh¯ng định thông qua cơ sở lý thuy¸t và so s¡nh thực nghi»m. B. Định hướng ph¡t triºn C¡c thuªt to¡n tèi ưu ng¨u nhi¶n đ· xu§t để gi£i bài to¡n MAP không lồi được chúng tôi nghi¶n cùu đem đến mët c¡ch ti¸p cªn mới: sû dụng x§p x¿ ng¨u nhi¶n, c¡c ph¥n phèi x¡c su§t ng¨u nhi¶n, đưa hàm mục ti¶u t§t định ban đầu trở thành đại lượng ng¨u nhi¶n có thº t½nh to¡n hi»u qu£. Nhªn th§y c¡ch ti¸p cªn này phù hñp và thực sự hi»u qu£, đặc bi»t khi c¡c bài to¡n MAP không lồi trong học m¡y thèng k¶ thường có hàm mục ti¶u phùc t¤p, xu§t hi»n trong c¡c mô h¼nh với dú li»u lớn, cao chi·u. Do đó trong thời gian tới, chúng tôi ti¸p tục tªp trung ph¡t triºn c¡c thuªt to¡n s¥u và rëng hơn, theo c¡c hướng: • Triºn khai rëng tr¶n nhi·u mô h¼nh bài to¡n kh¡c trong học m¡y có d¤ng không lồi hay bài to¡n quy ho¤ch DC khó gi£i; • Nghi¶n cùu t½nh ch§t ưu vi»t cõa c¡c thuªt to¡n đề xu§t: t½nh têng qu¡t, t½nh hi»u qu£ và kh£ n«ng hi»u ch¿nh. Tø đó nghi¶n cùu thuªt to¡n toàn di»n hơn tr¶n hai mặt lý thuy¸t và thực nghi»m; • Áp dụng thành công vào mët sè bài to¡n ùng dụng: ph¥n t½ch v«n b£n, h» gñi ý, bài to¡n nhªn d¤ng trong xû lý £nh, Ph¡t triºn c¡c nghi¶n cùu không ch¿ làm vi»c tr¶n c¡c dú li»u v«n b£n, có thº mở rëng tr¶n c¡c lo¤i dú li»u đa d¤ng và phùc t¤p hơn đáp ùng tèt hơn c¡c nhu c¦u cõa c¡c bài to¡n thực t¸. 24
27. DANH MỤC CÁC CÆNG TRÌNH ĐÃ CÆNG BÈ CỦA LUẬN ÁN 1. Xuan Bui, Tu Vu, and Khoat Than (2016). Stochastic bounds for inference in topic models. In International Conference on Advances in Information and Communica- tion Technology (pp. 582-592). Springer, Cham. 2. Bui Thi-Thanh-Xuan, Vu Van-Tu, Atsuhiro Takasu, and Khoat Than (2018). A fast algorithm for posterior inference with latent Dirichlet allocation. In Asian Con- ference on Intelligent Information and Database Systems (pp. 137-146). Springer, Cham. 3. Tu Vu, Xuan Bui, Khoat Than, and Ryutaro Ichise (2018). A flexible stochastic method for solving the MAP problem in topic models, Computación y Sistemas journal, 22(4), 2018 (Scopus, ESCI) 4. Xuan Bui, Tu Vu, and Khoat Than (2018). Some methods for posterior inference in topic models, Journal Research and Development on Information and Commu- nication Technology (RD-ICT), Vol E-2, No.15 (T¤p ch½ Công ngh» thông tin và truy·n thông) 5. Khoat Than, Xuan Bui, Tung Nguyen-Trong, Khang Truong, Son Nguyen, Bach Tran, Linh Ngo, and Anh Nguyen-Duc (2019). How to make a machine learn con- tinuously: a tutorial of the Bayesian approach, Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, 110060I, SPIE.