Luận á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

i thi¸t lªp tham sè theo nghi¶n cùu [28]: Sè
 1 1
chõ đề K = 100, tham sè Dirichlet α = K và η = K ; tham sè học κ = 0:9 và
τ = 1. 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.
 Chúng tôi kh£o s¡t £nh hưởng cõa vi»c lựa chọn k½ch thước mini-batch, chúng
tôi ti¸n hành thực nghi»m Online-OPE3 tr¶n hai bë dú li»u New York Times và
PubMed với lựa chọn k½ch thước mini-batch l¦n lưñt là 5000, 10000 và 25000.
Chi ti¸t k¸t qu£ được mô t£ trong H¼nh 2.7 và H¼nh 2.8.
 Theo k¸t qu£ mô t£ trong H¼nh 2.7 và H¼nh 2.8, chúng tôi nhªn th§y thuªt
to¡n Online-OPE3 thực hi»n với c¡ch chia bë dú li»u theo k½ch thước mini-batch
là 5000 cho k¸t qu£ tèt hơn trường hñp k½ch thước mini-batch là 10000 và 25000.
Điều đó hoàn toàn phù hñp với tư tưởng cõa c¡c thuªt to¡n học "online" là làm
vi»c ng¨u nhi¶n tr¶n c¡c m¨u nhỏ cõa bë dú li»u lớn, tùc là người ta chia bë dú
li»u thành nhi·u mini-batch nhỏ và ti¸n hành hu§n luy»n tr¶n tøng m¨u nhỏ.
 46
 
 
 
 
      -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¡c 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¡c c¡ch chia k½ch thước mini-batch kh¡c nhau. Độ đo càng cao càng tèt.
Cán khi chia bë dú li»u thành c¡c mini-batch k½ch thước lớn, c¡ch thùc ho¤t
động cõa thuªt to¡n có xu hướng theo c¡ch học "batch" cê điển k²m hi»u qu£
[9, 99].
 Theo hiºu bi¸t cõa chúng tôi, ch§t lượng cõa nghi»m x§p x¿ thu được phụ
thuëc vào sè bước lặp T cõa thuªt to¡n suy di¹n. Tuy nhi¶n, n¸u lựa chọn sè
bước lặp T qu¡ lớn s³ làm m§t nhi·u thời gian thực hi»n, ngược l¤i khi T qu¡
nhỏ s³ làm gi£m ch§t lượng nghi»m thu được. 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 thuªt to¡n suy di¹n OPE3 thông qua thực
nghi»m thuªt to¡n học Online-OPE3 tr¶n hai bë dú li»u New York Times và
PubMed. K¸t qu£ được chi ti¸t trong H¼nh 2.9.
 Theo H¼nh 2.9, chúng tôi nhªn th§y độ đo LPP và NPMI cõa thuªt to¡n học
Online-OPE3 có bi¸n động khi thay đổi sè bước lặp T trong thuªt to¡n suy di¹n
OPE3, nhưng sự bi¸n động tr¶n c¡c độ đo (đặc bi»t là LPP) không qu¡ lớn.
 47
   
 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.
Đồng thời khi t«ng sè bước lặp T (v½ dụ T = 100) cũng không ph£i luôn đảm
b£o t¼m được nghi»m θ phù hñp nh§t. Có thº lý gi£i cho đi·u này là do c¡c
thuªt to¡n OPE, OPE3 và OPE4 có tèc độ hëi tụ nhanh, n¶n không c¦n thực
hi»n qu¡ nhi·u bước lặp đã thu được nghi»m đủ tèt và ên định. Theo H¼nh 2.9,
chúng tôi th§y lựa chọn T = 50 đã đảm b£o k¸t qu£ c¡c độ đo tèt cõa thuªt
to¡n học Online-OPE3 mà không tèn qu¡ nhi·u bước lặp.
 Chúng tôi cũng ti¸n hành đo thời gian thực hi»n thuªt to¡n học: 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 H¼nh 2.10 và
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.
 Chúng tôi thực nghi»m tr¶n hai bë dú li»u New York Times và PubMed với
sè lượng v«n b£n được l§y là tương đương nhau, nhưng độ dài cõa c¡c v«n b£n
trong bë New York Times (trung b¼nh kho£ng 325 tø tr¶n mët v«n b£n) lớn
 48
   
 10
 1 1
 100 1
 
 10 1
 0 00 00 00 00 0 00 00 00 00
  
  
 
  
 
 
 0 00 00 00 00     
 (giây 0ờờờọ)
   
H¼nh 2.10: K¸t qu£ độ đo LPP và NPMI tương ùng với thời gian thực hi»n thuªt to¡n học Online-OPE,
Online-OPE3 và Online-OPE4 (ν = 0:3) tr¶n hai bë dú li»u New York Times và PubMed.
hơn trong bë PubMed (trung b¼nh kho£ng 65 tø tr¶n mët v«n b£n) r§t nhi·u
n¶n thời gian thực hi»n thuªt to¡n tr¶n New York Times nhi·u hơn PubMed.
Hơn núa, tr¶n cùng mët bë dú li»u, thời gian thực hi»n Online-OPE3 là cao
nh§t, cao hơn Online-OPE4 và Online-OPE là th§p nh§t. Sở dĩ Online-OPE3
m§t nhi·u thời gian v¼ sè ph²p to¡n t¤i méi váng lặp cõa OPE3 thường g§p đôi
cõa OPE. Tuy nhi¶n, têng thời gian thực hi»n c¡c thuªt to¡n học không lớn
n¶n sự kh¡c bi»t đó không đáng kº và hoàn toàn có thº ch§p nhªn đánh đổi khi
ch§t lượng độ đo LPP và NPMI cõa Online-OPE3 thu được tèt hơn h¯n so với
Online-OPE.
2.5. Sự hëi tụ cõa c¡c thuªt to¡n đề xu§t
 Tø c¡c k¸t qu£ thực nghi»m ở tr¶n, chúng tôi nhªn th§y OPE3 và OPE4 hi»u
qu£ hơn OPE với hai bë dú li»u thực nghi»m khi ¡p dụng vào thi¸t k¸ hai thuªt
to¡n học với LDA. V¼ vªy, chúng tôi tªp trung vào ph¥n t½ch sự hëi tụ cõa thuªt
to¡n OPE3 và OPE4.
Đị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, 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.
 49
Chùng minh. Tø bài to¡n (2.1), ta th§y hàm mục ti¶u f(θ) là hàm không lồi.
Ti¶u chu©n được sû dụng để ph¥n t½ch hëi tụ r§t quan trọng trong tèi ưu hóa
không lồi. Đối với c¡c bài to¡n tèi ưu không lồi không ràng buëc, gradient cõa
hàm mục ti¶u krf(θ)k được dùng để đánh gi¡ hëi tụ, bởi v¼ krf(θ)k ! 0 đưa
đến hëi tụ đến mët điểm døng. Tuy nhi¶n, ti¶u chu©n này không thº được sû
dụng cho c¡c bài to¡n tèi ưu không lồi có ràng buëc. Thay vào đó, ta sû dụng
ti¶u chu©n "Frank-Wolfe gap" trong [72]. Ký hi»u
 K K
 X X X
 g1(θ) = dj log θkβkj ; g2(θ) = (α − 1) log θk
 j k=1 k=1
Đầu ti¶n, ta xem x²t d¢y fUtg. Gọi at và bt là sè l¦n l§y được thành ph¦n g1 và
g2 tương ùng sau t l¦n lặp để x¥y dựng d¢y fUtg. Chúng ta th§y at + bt = t. Ký
hi»u St = at − bt. Chúng ta có
 2
 U = (a g + b g ) (2.3)
 t t t 1 t 2
 S
 U − f = t (g − g ) (2.4)
 t t 1 2
 S
 U 0 − f 0 = t (g0 − g0 ) (2.5)
 t t 1 2
 u
V¼ ft được chọn theo ph¥n phèi đều tø fg1; g2g n¶n
 1 1 1
 E(f u) = g + g = f
 t 2 1 2 2 2
 t t t
 2 X 2 X 2 X 1 2 t
 E(U ) = E( f u) = E(f u) = = : f = f
 t t h t h t 2 t 2
 h=1 h=1 h=1
 V¼ vªy Ut(θ) là mët ước lượng không ch»ch cõa f(θ). Với méi bước lặp t cõa
 u
OPE3, l§y ft có ph¥n phèi đều tø fg1; g2g, tùc là
 1 1
 P (f u = g ) = ; P (f u = g ) =
 t 1 2 t 2 2
 u
 Thực hi»n tương ùng giúa ft và bi¸n ng¨u nhi¶n Xt có ph¥n phèi đều tø
f1; −1g:
 1 1
 P (X = 1) = ; P (X = −1) =
 t 2 t 2
Sự tương ùng này là ¡nh x¤ mët-mët. V¼ vªy, St = at − bt có thº được biºu
di¹n dưới d¤ng St = X1 + ··· + Xt. Áp dụng luªt logarit lặp LIL [103], ta có
 p
 St
St = O( t log t), d¨n đến t ! 0 khi t ! +1. K¸t hñp với (2.4), ta có d¢y
 0 0
Ut ! f với x¡c su§t 1, đồng thời tø (2.5), d¢y đạo hàm Ut ! f khi t ! +1. Sự
hëi tụ thu được cho mọi điểm θ 2 ∆K.
 50
 Xem x²t
 eu − θ eu − θ eu − θ
 hU 0(θ ); t t i = hU 0(θ ) − f 0(θ ); t t i + hf 0(θ ); t t i
 t t t t t t t t t
 u
 S 0 0 e − θ
 = t hg (θ ) − g (θ ); eu − θ i + hf 0(θ ); t t i
 t2 1 t 2 t t t t t
Ta có g1 và g2 là c¡c hàm Lipschitz li¶n tục tr¶n ∆K. V¼ vªy tồn t¤i mët h¬ng
sè L sao cho:
 0 2
 hf (z); y − zi ≤ f(y) − f(z) + Lky − zk ; 8 y; z 2 ∆K
Do vªy x²t:
 eu − θ
hf 0(θ ); t t i = hf 0(θ ); θu − θ i
 t t t t+1 t
 eu − θ
 ≤ f(θu ) − f(θ ) + Lkθu − θ k2 = f(θu ) − f(θ ) + Lk t t k2
 t+1 t t+1 t t+1 t t
Ta có: θt+1 := arg max u l f(θ), v¼ vªy
 θ2fθt+1;θt+1g
 u
 f(θt+1) ≤ f(θt+1)
 u 0 0 u u 2
V¼ et và θt thuëc ∆K, n¶n jhg1(θt) − g2(θt); et − θtij và ket − θtk đều bị chặn
tr¶n với mọi t. V¼ vªy tồn t¤i mët h¬ng sè c1 > 0 sao cho
 eu − θ jS j c L
 hU 0(θ ); t t i ≤ c t + f(θ ) − f(θ ) + 1 (2.6)
 t t t 1 t2 t+1 t t2
L§y têng cõa (2.6) với mọi t, ta có
 +1 +1 +1
 X 1 X jStj X c1L
 hU 0(θ ); eu − θ i ≤ c + f(θ ) − f(θ ) + (2.7)
 t t t t t 1 t2 +1 1 t2
 t=1 t=1 t=1
 p
Bởi v¼ f(θ) bị chặn n¶n f(θ+1) cũng bị chặn. Ghi nhớ r¬ng St = O( t log t)
 P+1 jStj P+1 L
[103], v¼ vªy t=1 c1 t2 hëi tụ với x¡c su§t 1, và t=1 t2 cũng bị chặn. Do đó,
 0 u 0
v¸ ph£i cõa (2.7) là x¡c định. Ngoài ra, hUt(θt); et i > hUt(θt); θti với b§t kỳ t > 0
bởi v¼ eu = arg max hU 0(θ ); xi. Do vªy, ta có:
 t x2∆K t t
 +1
 X 1
 0 ≤ hU 0(θ ); eu − θ i < 1 (2.8)
 t t t t t
 t=1
 P+1 1 0 u
Nói c¡ch kh¡c, d¢y t=1 t hUt(θt); et − θti hëi tụ tới mët h¬ng húu h¤n. Ta th§y
 0 u
hUt(θt); et − θti ≥ 0 với t b§t kỳ. N¸u tồn t¤i mët h¬ng sè c2 > 0 thỏa m¢n
 0 u P+1 1 0 u
hUt(θt); et − θti ≥ c2 với t không x¡c định, khi đó d¢y t=1 t hUt(θt); et − θti có
thº không hëi tụ đến h¬ng húu h¤n, điều này m¥u thu¨n với (2.8). V¼ vªy,
 0 u
 hUt(θt); et − θti ! 0 as t ! +1 (2.9)
 51
 0 0 0
Bởi v¼ Ut ! f khi t ! 1 và f là li¶n tục, k¸t hñp với (2.9) ta có
 0 u
 hf (θt); et − θti ! 0 as t ! +1 (2.10)
 ∗
Sû dụng ti¶u chu©n "Frank-Wolfe gap" trong [72], tø (2.10) có θt ! θ khi
 ∗
t ! +1. Nói c¡ch kh¡c, θt hëi tụ tới nghi»m tèi ưu θ cõa f(θ).
Đị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, 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(θ).
Chùng minh. Ký hi»u
 K K
 X X X
 g1(θ) = dj log θkβkj; g2(θ) = (α − 1) log θk
 j k=1 k=1
Gọi at và bt là sè l¦n xu§t hi»n thành ph¦n g1 và g2 sau t bước lặp để x¥y dựng
d¢y hàm x§p x¿ fUtg.
 u
 V¼ ft được lựa chọn theo ph¥n phèi đều tø fg1; g2g n¶n
 1 1 1
 E[f u] = E[f l] = g + g = f
 t t 2 1 2 2 2
 t t t
 2 X 2 X 2 X 1
 E[U ] = E[ f u] = E[f u] = f = f
 t t h t h t 2
 h=1 h=1 h=1
Tương tự, gọi ct và dt là sè l¦n xu§t hi»n thành ph¦n g1 và g2 sau t bước lặp
 l
để x¥y dựng d¢y hàm x§p x¿ fLtg. V¼ ft được lựa chọn theo ph¥n phèi đều tø
fg1; g2g n¶n:
 1 1 1
 E[f u] = E[f l] = g + g = f
 t t 2 1 2 2 2
 t t t
 2 X 2 X 2 X 1
 E[L ] = E[ f l ] = E[f l ] = f = f
 t t h t h t 2
 h=1 h=1 h=1
Do vªy
 E[Ft] = νE[Ut] + (1 − ν)E[Lt] = νf + (1 − ν)f = f
 u l u l
Ký hi»u St = at − bt ;St = ct − dt và St = maxfjSt j; jStjg
 52
 Ta có
 2
 U = (a g + b g ) a + b = t
 t t t 1 t 2 t t
 2
 L = (c g + d g ) c + d = t
 t t t 1 t 2 t t
 Su Sl
 U − f = t (g − g ) L − f = t (g − g )
 t t 1 2 t t 1 2
 Su Sl
 U 0 − f 0 = t (g0 − g0 ) L0 − f 0 = t (g0 − g0 )
 t t 1 2 t t 1 2
Do Ft = νUt + (1 − ν)Lt thu được:
 Ft − f = ν(Ut − f) + (1 − ν)(Lt − f)
 Su Sl
 = (ν t + (1 − ν) t )(g − g )
 t t 1 2
 Su Sl
 F 0 − f 0 = (ν t + (1 − ν) t )(g0 − g0 )
 t t t 1 2
V¼ vªy, Ft là mët ước lượng không ch»ch cõa hàm mục ti¶u đúng f. Áp dụng
 p p u
 u l St
luªt LIL [103] ta có St = O( t log t) và St = O( t log t), d¨n đến t ! 0 và
 l
St
t ! 0 khi t ! +1. V¼ vªy, chúng tôi k¸t luªn r¬ng d¢y Ut ! f và d¢y đạo hàm
 0 0
Ut ! f' khi t ! +1. Tương tự, xem x²t với d¢y Lt ! f, và d¢y đạo hàm Lt ! f'
khi t ! +1.
 Xem x²t
 e − θ e − θ e − θ
 hF 0(θ ); t t i = hF 0(θ ) − f 0(θ ); t t i + hf 0(θ ); t t i =
 t t t t t t t t t
 Su Sl e − θ e − θ
 = h(ν t + (1 − ν) t )(g0 (θ ) − g0 (θ )); t t i + hf 0(θ ); t t i
 t t 1 t 2 t t t t
 Chúng ta có g1 và g2 là hàm Lipschitz li¶n tục tr¶n ∆K. V¼ vªy, tồn t¤i mët
h¬ng sè L sao cho:
 0 2
 hf (z); y − zi ≤ f(y) − f(z) + Lky − zk 8y; z 2 ∆K
Do đó:
 e − θ
 hf 0(θ ); t t i = hf 0(θ ); θ − θ i ≤ f(θ ) − f(θ ) + Lkθ − θ k2
 t t t t+1 t t+1 t t+1 t
 e − θ
 = f(θ ) − f(θ ) + Lk t t k2
 t+1 t t
 0 0 u 2
V¼ et và θt đều thuëc ∆K n¶n hg1(θt) − g2(θt); et − θti và ket − θtk bị chặn. Do
đó, tồn t¤i mët h¬ng c1 > 0 sao cho:
 e − θ S c L
 hF 0(θ ); t t i ≤ c t + f(θ ) − f(θ ) + 1 (2.11)
 t t t 1 t2 t+1 t t2
 53
L§y têng hai v¸ cõa (2.11) với mọi t, ta có
 +1 +1 +1
 X 1 X St X c1L
 hF 0(θ ); e − θ i ≤ c + f(θ∗) − f(θ ) + (2.12)
 t t t t t 1 t2 1 t2
 t=1 t=1 t=1
 ∗ p
Bởi v¼ f(θ) bị chặn n¶n f(θ ) bị chặn. Chúng ta th§y St = O( t log t) theo tài
 P+1 St P+1 L
li»u [103], v¼ vªy d¢y t=1 c1 t2 hëi tụ với x¡c su§t 1 và têng t=1 t2 cũng bị
chặn. V¼ vªy, v¸ ph£i cõa (2.12) là húu h¤n.
 Bởi v¼ e = arg max hF 0(θ ); xi n¶n hF 0(θ ); e i > hF 0(θ ); θ i với b§t kỳ
 t x2∆K t t t t t t t t
t > 0. V¼ vªy thu được:
 +1
 X 1
 0 ≤ hF 0(θ ); e − θ i < +1 (2.13)
 t t t t t
 t=1
 P+1 1 0
Nói c¡ch kh¡c, d¢y t=1 t hFt (θt); et − θti hëi tụ tới mët h¬ng sè húu h¤n.
 0
 Ta th§y hFt (θt); et − θti ≥ 0 với b§t kỳ t. N¸u tồn t¤i mët h¬ng sè c3 > 0 thỏa
 0 P+1 1 0
m¢n hFt (θt); et−θti ≥ c3 với t nhªn gi¡ trị vô h¤n, khi đó chuéi t=1 t hFt (θt); et−
θti không thº hëi tụ tới mët h¬ng húu h¤n, điều này tr¡i ngược với (2.13). V¼
vªy
 0
 hFt (θt); et − θti ! 0 khi t ! +1 (2.14)
 0 0 0
Bởi v¼ Ft ! f khi t ! 1 và f là c¡c hàm li¶n tục, k¸t hñp với (2.14) có:
 0
 hf (θt); et − θti ! 0 khi t ! +1:
 ∗
Sû dụng ti¶u chu©n "Frank-Wolfe gap" [72], ta có θt ! θ as t ! +1. Như vªy,
 ∗
θt hëi tụ theo x¡c su§t đến điểm dừng/cực đại địa phương θ of hàm mục ti¶u
f(θ).
2.6. Mở rëng thuªt to¡n đề xu§t cho bài to¡n tèi ưu không lồi
 Ph¥n t½ch đặc điểm cõa OPE3 và OPE4, chúng tôi nhªn th§y có thº sûa
đổi OPE3 và OPE4 d¹ dàng đº gi£i bài to¡n tèi ưu không lồi têng qu¡t có
d¤ng như trong (2.2), tùc là gi£i bài to¡n tèi đa hóa hàm mục ti¶u có d¤ng
f(x) = g1(x) + g2(x) tr¶n mi·n ràng buëc Ω. Do đó bước t¼m et trong OPE3 hay
OPE4 s³ là mët bài to¡n quy ho¤ch tuy¸n t½nh có thº gi£i đưñc. X²t bài to¡n
tèi ưu không lồi têng qu¡t:
 max[f(x) = g1(x) + g2(x)] (2.15)
 x2Ω
Chi ti¸t cõa thuªt to¡n OPE3 và OPE4 têng qu¡t để gi£i bài to¡n (2.15) được
tr¼nh bày trong Thuªt to¡n 2.7 và Thuªt to¡n 2.8.
 54
Thuªt to¡n 2.7 OPE3 gi£i bài to¡n tèi ưu không lồi têng qu¡t
 ∗
Đầu ra: x là nghi»m cực đại hóa cõa hàm f(x) = g1(x) + g2(x) tr¶n mi·n Ω
 1: Khởi t¤o x1 thuëc Ω
 l u
 2: f1 := g1(x); f1 := g2(x)
 3: for t = 2; 3; ::; 1 do
 u
 4: L§y ft có ph¥n phèi đều tø fg1(x); g2(x)g
 2 Pt u
 5: Ut := t h=1 fh
 u 0
 6: at := arg maxx2ΩhUt (xt); xi
 u
 u at −xt
 7: xt+1 := xt + t
 l
 8: L§y ft có ph¥n phèi đều tø fg1(x); g2(x)g
 2 Pt l
 9: Lt := t h=1 fh
 l 0
 10: at := arg maxx2ΩhLt(xt); xi
 l
 l at−xt
 11: xt+1 := xt + t
 12: xt+1 := arg max u l f(x)
 x2fxt+1;xt+1g
 13: end for
Thuªt to¡n 2.8 OPE4 gi£i bài to¡n tèi ưu không lồi têng qu¡t
Đầu vào: Tham sè tê hñp ν 2 (0; 1)
 ∗
Đầu ra: x là nghi»m cực đại hóa cõa hàm f(x) = g1(x) + g2(x) tr¶n mi·n Ω
 1: Khởi t¤o x1 thuëc Ω
 l u
 2: f1 := g1(x) ; f1 := g2(x)
 3: for t = 2; 3; ::; 1 do
 u
 4: L§y ft có ph¥n phèi đều tø fg1(x); g2(x)g
 2 Pt u
 5: Ut := t h=1 fh
 l
 6: L§y ft có ph¥n phèi đều tø fg1(x); g2(x)g
 2 Pt l
 7: Lt := t h=1 fh
 8: L§y Ft := νUt + (1 − ν)Lt
 0
 9: at := arg maxx2ΩhFt (xt); xi
 at−xt
 10: xt+1 := xt + t
 11: end for
 Sự hëi tụ cõa OPE3 và OPE4 trong trường hñp têng qu¡t này có thº chùng
minh tương tự như Định lý 2.1 và Định lý 2.2 bởi c¡c qu¡ tr¼nh chùng minh
không bị phụ thuëc vào hàm thành ph¦n g1(x) và g2(x) cụ thº.
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
 55
 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 [104], 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.
 56
 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Ủ ĐỀ
 Trong chương này, nghi¶n cùu sinh ti¸p tục đề xu§t thuªt to¡n GOPE theo
hướng ng¨u nhi¶n thông qua sû dụng ph¥n phèi Bernoulli hñp lý và x§p x¿ ng¨u
nhi¶n để gi£i bài to¡n MAP không lồi. Sự hi»u qu£ cõa thuªt to¡n GOPE được
xem x²t tr¶n c£ hai mặt lý thuy¸t và thực nghi»m, trong đó sû dụng GOPE là
thuªt to¡n suy di¹n cho bài to¡n MAP trong c¡c 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 (Djx) + log P (x)] (3.1)
 x
Ký hi»u g1(x) := log P (Djx) và g2(x) := log P (x), bài to¡n (3.1) được đưa v· bài
to¡n tèi ưu có d¤ng:
 ∗
 x = arg max [f(x) = g1(x) + g2(x)] (3.2)
 x
trong đó hàm mục ti¶u f(x) được ph¥n t½ch thành têng cõa hai thành ph¦n
g1(x) và g2(x). Bài to¡n (3.2) là khó gi£i khi hàm mục ti¶u f(x) là hàm không
lãm.
 Mët v½ dụ điển h¼nh cho bài to¡n (3.2) ch½nh 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
trong đó α là tham sè cõa ph¥n phèi ti¶n nghi»m Dirichlet. [37] đã ch¿ ra r¬ng
bài to¡n (3.3) thuëc lớp NP-khó khi tham sè α < 1. Trong trường hñp α ≥ 1,
d¹ dàng ch¿ ra r¬ng bài to¡n (3.3) là tèi ưu lãm, khi đó có thº được gi£i quy¸t
trong thời gian đa thùc. Thªt không may, trong thực t¸ mô h¼nh LDA, tham sè
α thường nhỏ, tùc α < 1 [42, 92], khi¸n cho bài to¡n (3.3) trở thành bài to¡n tèi
ưu không lãm (non-concave). Đó là lý do t¤i sao (3.3) không kh£ thi trong c¡c
trường hñp x§u.
 57
 Chương 2 đã xem x²t bài to¡n (3.3) với c¡c c£i ti¸n OPE1, OPE2, OPE3 và
OPE4, đặc bi»t OPE3 và OPE4 là hai thuªt to¡n hi»u qu£ nh§t. Chúng tôi ti¸p
tục ti¸p cªn theo hướng ng¨u nhi¶n hóa để đề xu§t c¡c thuªt to¡n hi»u qu£ gi£i
bài to¡n MAP không lồi. Đồng thời đảm b£o thuªt to¡n đề xu§t có t½nh linh
ho¤t, d¹ dàng mở rëng cho bài to¡n không lồi kh¡c xu§t hi»n trong học m¡y.
Chúng tôi nhªn th§y ph¥n phèi Bernoulli là ph¥n phèi rời r¤c đơn gi£n nhưng
têng qu¡t hơn ph¥n phèi đều và có nhi·u ùng dụng trong thực t¸. Đây là mët ý
tưởng để chúng tôi c£i ti¸n thuªt to¡n OPE và đưa ra thuªt to¡n mới đảm b£o
t½nh têng qu¡t và hi»u qu£ hơn dựa tr¶n ph¥n phèi Bernoulli và x§p x¿ ng¨u
nhi¶n.
3.2. Thuªt to¡n Generalized Online Maximum a Posteriori Es-
 timation
 X²t bài to¡n MAP (3.3) với mô h¼nh chõ đề:
 K K
 ∗ X X X
 θ = arg max dj log θkβkj + (α − 1) log θk
 θ2∆K
 j k=1 k=1
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.3).
 Ký hi»u
 K