劉張虎，程春玲

(南京郵電大學(xué)計(jì)算機(jī)學(xué)院，南京210003)

(*通信作者電子郵箱lzh1562202171@163.com)

0 引言

潛在狄利克雷分配(Latent Dirichlet Allocation，LDA)［1］受到了越來越多的關(guān)注，它已被公認(rèn)為是最成功的主題建模方法之一。LDA模型通過推斷隱含變量的后驗(yàn)分布可以對(duì)文檔進(jìn)行分析和探索。標(biāo)準(zhǔn)的推理方法主要包括馬爾可夫蒙特卡羅(Markov Chain Monte Carlo，MCMC)［2－3］和變分學(xué)習(xí)(Variational Learning)［4］方法。但是這些傳統(tǒng)方法都是批次學(xué)習(xí)的框架，在每次迭代更新全局參數(shù)時(shí)，它們必須要訪問整個(gè)語料庫(kù)，因此在對(duì)大規(guī)模文本數(shù)據(jù)進(jìn)行建模時(shí)，參數(shù)計(jì)算是十分困難的;這些傳統(tǒng)方法也無法對(duì)以數(shù)據(jù)流形式輸入的數(shù)據(jù)集進(jìn)行在線處理，因?yàn)樗鼈儫o法一次獲取并存儲(chǔ)整個(gè)數(shù)據(jù)集的數(shù)據(jù)。

為了解決這些困難，一些學(xué)者使用并行計(jì)算以加快LDA的推理過程。然而，并行計(jì)算需要配置并行硬件，對(duì)于數(shù)據(jù)通信來說代價(jià)是十分昂貴的。除了并行計(jì)算，一些學(xué)者試圖將這些批量方法擴(kuò)展為在線方法，使得它們適用于處理大規(guī)模數(shù)據(jù)和數(shù)據(jù)流形式的數(shù)據(jù)。Canini等［5］通過在線MCMC算法使用的先前分析的詞，以簡(jiǎn)化主題分配的采樣;Patterson等［6］開發(fā)了一個(gè)可擴(kuò)展的MCMC算法，可以由漸近后驗(yàn)分布來產(chǎn)生樣本。然而MCMC算法難以判斷馬爾可夫鏈的收斂性，且需要預(yù)先設(shè)置采樣次數(shù)，這些問題在實(shí)際應(yīng)用中都影響了算法的效率和準(zhǔn)確性。Hoffman等［7］基于變分學(xué)習(xí)開發(fā)了一個(gè)用于LDA的在線變分貝葉斯算法，基于在線隨機(jī)優(yōu)化與自然梯度步驟，可收斂到變分貝葉斯(Variational Bayes，VB)目標(biāo)函數(shù)的局部最優(yōu)，它可以有效地分析以數(shù)據(jù)流形式到達(dá)的文檔。為提高處理大規(guī)模數(shù)據(jù)集的效率，Hoffman等［8］在在線變分貝葉斯算法［7］的基礎(chǔ)上提出了隨機(jī)變分推理(Stochastic Variational Inference，SVI)，使用隨機(jī)優(yōu)化來優(yōu)化變分目標(biāo)，對(duì)隨機(jī)梯度進(jìn)行噪聲估計(jì)。它從數(shù)據(jù)中逐次推理子采樣，分析子采樣，并且以減小的學(xué)習(xí)速率更新參數(shù)。SVI現(xiàn)已被應(yīng)用于許多類型的模型，包括主題模型［9］、統(tǒng)計(jì)網(wǎng)絡(luò)分析［10］、過程因子分析［11］和高斯過程［12］等。但是由于大規(guī)模文本文檔數(shù)據(jù)的高維，SVI從隨機(jī)數(shù)據(jù)樣本而不是從整個(gè)數(shù)據(jù)庫(kù)計(jì)算得到隨機(jī)梯度，隨機(jī)梯度的噪聲通常比較大，噪聲使其偏離真實(shí)梯度，導(dǎo)致隨機(jī)梯度和真實(shí)梯度的方差較大，因此算法的迭代過程可能需要花費(fèi)大量時(shí)間，導(dǎo)致收斂變慢，性能變差。

針對(duì)SVI算法在處理大規(guī)模數(shù)據(jù)集時(shí)噪聲影響收斂速度的問題，本文基于 SVI算法框架，提出方差減小的 SVI(Varience Reduced SVI，VR-SVI)算法，用于主題模型的參數(shù)推斷。本文主要工作如下:1)為減小SVI算法中噪聲的影響，采用滑動(dòng)窗口的方法處理隨機(jī)采集的數(shù)據(jù)集，針對(duì)滑動(dòng)窗口重新計(jì)算隨機(jī)梯度中噪聲項(xiàng)的值，并以新的噪聲項(xiàng)來構(gòu)建新的隨機(jī)梯度，得出全局變分參數(shù)的更新規(guī)則;2)給出分析VRSVI算法中隨機(jī)梯度方差減小的過程，證明VR-SVI算法的有效性，同時(shí)分析算法的收斂性;3)在大型語料庫(kù)上進(jìn)行實(shí)驗(yàn)，驗(yàn)證算法方差減小的效果，并評(píng)估滑動(dòng)窗口大小對(duì)算法的影響，在此基礎(chǔ)上進(jìn)一步作對(duì)比實(shí)驗(yàn)，比較分析VR-SVI算法和現(xiàn)有的算法性能。

1 相關(guān)工作

隨機(jī)變分推理擴(kuò)展了變分推理算法，使復(fù)雜的概率模型適用于分析海量數(shù)據(jù)集，其主要思想是使用隨機(jī)梯度優(yōu)化，通過重復(fù)地對(duì)數(shù)據(jù)子采樣產(chǎn)生帶有噪聲的梯度來迭代更新參數(shù)。針對(duì)該算法噪聲導(dǎo)致隨機(jī)梯度方差較大的問題，本文從隨機(jī)優(yōu)化的角度對(duì)相關(guān)解決方案進(jìn)行調(diào)研。

隨機(jī)優(yōu)化中的平均梯度(Average Gradient，AG)［13］和隨機(jī)平均梯度(Stochastic Average Gradient，SAG)［14］等方法能夠取得更快的收斂效果，已成功應(yīng)用在許多問題中。但是，AG和SAG并不能完全適用于SVI。首先，SVI更新是用前一個(gè)參數(shù)和新的噪聲項(xiàng)的凸組合來更新變分參數(shù)，它具有將參數(shù)保持在可行空間中的特性;而AG遵循隨機(jī)梯度序列的平均值，不具有這種特性。第二，SAG迭代更新全梯度中的子集項(xiàng)，需要存儲(chǔ)迭代過程中的所有漸變梯度;而在SVI算法的大多數(shù)應(yīng)用中，每個(gè)數(shù)據(jù)點(diǎn)都有一個(gè)目標(biāo)梯度，若使用SAG，所需要的存儲(chǔ)空間代價(jià)太大。受隨機(jī)平均梯度的思想啟發(fā)，Johnson等［15］在優(yōu)化算法中提出一種隨機(jī)方差減小梯度(Stochastic Variance Reduced Gradient，SVRG)的方法來減小隨機(jī)梯度的方差，SVRG的主要思想是在原有單個(gè)樣本的梯度計(jì)算中引入一個(gè)修正量，該修正量是由所有樣本梯度的平均值組成的，和僅使用單個(gè)樣本梯度的標(biāo)準(zhǔn)隨機(jī)優(yōu)化算法相比，修正后的梯度可以明顯減小方差。與SAG不同的是，SVRG不需要存儲(chǔ)目標(biāo)函數(shù)的梯度，減小了內(nèi)存開銷。Xiao等［16］提出一種新的近鄰隨機(jī)梯度法Prox-SVRG，將正則化項(xiàng)和損失函數(shù)分開考慮，保持正則化項(xiàng)不變，僅對(duì)損失項(xiàng)的梯度進(jìn)行優(yōu)化，利用SVRG方法，采用多階段方案逐步減少隨機(jī)梯度的方差，但是該方法和SVRG一樣，仍需要用全梯度來修正單個(gè)樣本梯度，從而迭代過程中不得不多次遍歷所有樣本，雖然減小方差的效果明顯，但和批處理算法一樣，需要大量的計(jì)算時(shí)間。朱小輝等［17］在SVRG的基礎(chǔ)上考慮求解非光滑損失問題隨機(jī)優(yōu)化算法COMID(Composite Objective MIrror Descent)的方差減小問題，在COMID中引入減小方差的策略，得到一種隨機(jī)優(yōu)化算法α-MDVR。相比SVRG，α-MDVR每次迭代時(shí)只使用部分樣本來修正梯度，因此雖有更快的實(shí)際收斂速率，但是其方差的減小效果卻達(dá)不到SVRG中使用全部樣本時(shí)的效果。Reddi等［18］探索了SVRG方法應(yīng)用于求解非凸優(yōu)化問題的情況，證明了對(duì)于非凸優(yōu)化問題，SVRG非漸近收斂速率可以比隨機(jī)梯度下降(Stochastic Gradient Descent，SGD)更快，并在非凸問題的子類上分析出SVRG可以線性收斂到全局最優(yōu)。

另外，通過其他優(yōu)化方法也可平滑隨機(jī)梯度中的噪聲，減小隨機(jī)梯度方差，從而加快算法的收斂過程。Ouyang等［19］采用動(dòng)量項(xiàng)來平滑隨機(jī)梯度的噪聲，并提出在線LDA的擴(kuò)展形式，即動(dòng)量在線LDA(Momentum Online LDA，MOLDA)。動(dòng)量是以前迭代過程的梯度的加權(quán)和，每一個(gè)隨機(jī)梯度都包含了采樣所得到的樣本信息，這樣加權(quán)和就可以包含整個(gè)數(shù)據(jù)集所有信息，同時(shí)可以用動(dòng)量參數(shù)來控制不同隨機(jī)梯度的權(quán)值，最終可使得全局變分參數(shù)達(dá)到局部最優(yōu)解。但是這種方法的動(dòng)量參數(shù)是固定常量，無法隨著迭代過程根據(jù)樣本對(duì)隨機(jī)梯度的權(quán)值做出相應(yīng)調(diào)整，這會(huì)限制其收斂速度。Wang等［20］提出了一個(gè)方差減小隨機(jī)梯度優(yōu)化(Variance Reduction for Stochastic Gradient Optimization，VRSGO)總體框架來處理隨機(jī)梯度優(yōu)化算法中的噪聲，它是一個(gè)解決普遍存在于不同模型的所有隨機(jī)梯度優(yōu)化算法中的噪聲梯度問題的通用方法。VRSGO使用低階信息來構(gòu)建控制變量，然后使用這些控制變量來減小隨機(jī)梯度的方差。雖然VRSGO可以減小方差，但是其前提是需要構(gòu)建合適的控制變量，如果構(gòu)建的控制變量難以計(jì)算的話，這種方法會(huì)使每次迭代計(jì)算的代價(jià)變得很高。

2 改進(jìn)算法VR-SVI

首先介紹應(yīng)用于LDA模型的傳統(tǒng)的批次變分推理方法［1］以及 Hoffman等［8］提出的 SVI算法，并對(duì)其過程進(jìn)行分析，然后在SVI的基礎(chǔ)上提出本文的改進(jìn)算法VR-SVI。

2.1 用于LDA的批次變分推理

LDA模型中，詞的生成過程如下:首先從一個(gè)Dirichlet分布得出主題下詞的分布βk～Dirichlet(η)。然后對(duì)于每個(gè)文檔D，可采樣文檔中的主題分布θd～Dirichlet(α)，對(duì)于文檔中的每個(gè)單詞，生成詞的主題zd，n～ Multinomial(θd)，從主題中生成單詞 wd，n～ Multinomial(βzd，n)。該模型具有以下聯(lián)合概率分布:

其中:β是全局參數(shù);θ和 z是局部參數(shù)。將最小化散度KL((q(β，θ，z))‖(p(β，θ，z，w))) 轉(zhuǎn)化為最大化 L(q(β，θ，z))，使用期望最大化(Expectation Maximization，EM)算法求解 L(q(β，θ，z)) 中的參數(shù)，L(q(β，θ，z)) 被稱為證據(jù)下界(Evidence Lower BOund，ELBO)，且有:

在每次EM迭代中，首先對(duì)于語料庫(kù)的每個(gè)文檔，迭代更新局部變分參數(shù)，獲得每個(gè)文檔最優(yōu)的Φ和γ，更新規(guī)則如下:

然后更新全局變分參數(shù)λ，更新規(guī)則如下:

2.2 用于LDA的SVI

傳統(tǒng)的批次變分算法必須在更新全局變分參數(shù)之前先計(jì)算所有文檔的局部變分參數(shù)，這導(dǎo)致對(duì)大規(guī)模文檔和在線文檔流的計(jì)算量會(huì)非常大。Hoffman等［8］提出的隨機(jī)變分推理方法使用隨機(jī)梯度下降算法加快LDA模型的變分推理過程，具體方法如下:對(duì)于第t次EM迭代，隨機(jī)采集語料庫(kù)的樣本Bi{1，2，…，D}。對(duì)于樣本 Bi中的每個(gè)文檔，按照式(3)、(4)迭代更新局部變分參數(shù)Φ和γ，然后計(jì)算出全局變分參數(shù)λ的隨機(jī)梯度，計(jì)算式如下:

其中M是樣本中文檔的數(shù)目。為方便說明，令:

最后計(jì)算全局變分參數(shù)λ，給定一個(gè)減小的學(xué)習(xí)率ρt＜1，可得到λ的更新規(guī)則:=+。

2.3 VR-SVI算法

隨機(jī)變分推理在每次迭代時(shí)，只采集語料庫(kù)的部分文檔來對(duì)參數(shù)進(jìn)行計(jì)算，這提高了算法效率，相比傳統(tǒng)的變分推理方法，隨機(jī)變分推理更適用于大規(guī)模數(shù)據(jù)以及在線數(shù)據(jù)的分析。然而使用該方法時(shí)需要考慮樣本的大小，如果太小，樣本中包含的信息相對(duì)整個(gè)數(shù)據(jù)集的信息太少，這會(huì)導(dǎo)致隨機(jī)梯度產(chǎn)生較大的噪聲;如果太大，則會(huì)導(dǎo)致隨機(jī)變分推理向批次變分推理靠近，需要遍歷較大的樣本空間，失去其快速運(yùn)算的優(yōu)勢(shì)。由于向隨機(jī)梯度中引入了噪聲，隨機(jī)梯度具有較大的方差，可能導(dǎo)致算法花費(fèi)大量時(shí)間跳轉(zhuǎn)，使算法收斂變慢，甚至可能收斂到壞的解。為減小噪聲影響，本文提出一種方差減小的隨機(jī)變分推理(VR-SVI)算法，引入滑動(dòng)窗口的概念，在迭代過程中采用滑動(dòng)窗口方法降低隨機(jī)梯度的噪聲，減小隨機(jī)梯度的方差，使得隨機(jī)梯度的方向和值盡可能接近真實(shí)梯度，從而提高隨機(jī)變分推理算法的性能。

定義1 單位數(shù)據(jù)Bt。對(duì)原始數(shù)據(jù)集進(jìn)行分組，隨機(jī)采樣的每組數(shù)據(jù)Bt={d1，d2，…，dM}作為一個(gè)單位數(shù)據(jù)。

定義2 滑動(dòng)窗口SW。對(duì)于正整數(shù)R(R∈N*)，文檔集D={B1，B2，…，BR}進(jìn)入到窗口大小為R的窗口SW中，窗口每次迭代時(shí)會(huì)向前移動(dòng)1個(gè)單位數(shù)據(jù)大小的位置，該窗口SW即為滑動(dòng)窗口。

由2.2節(jié)對(duì)SVI過程的描述可知，由于SVI算法采取隨機(jī)采集部分樣本來更新局部變分參數(shù)的方式，使得隨機(jī)梯度噪聲較大，具體表現(xiàn)為式(6)中的噪聲項(xiàng)。不同于傳統(tǒng)批次變分推理重復(fù)使用所有樣本來計(jì)算隨機(jī)梯度，SVI算法在每次迭代時(shí)，采集部分樣本計(jì)算隨機(jī)梯度，在更新全局變分參數(shù)后，只使用一次的樣本會(huì)被丟棄，這使隨機(jī)梯度偏離真實(shí)梯度。本文使用滑動(dòng)窗口SW保留迭代采集的樣本，對(duì)于t次迭代，當(dāng) t≤ R 時(shí)，Bt進(jìn)入窗口 SW，D={B1，B2，…，Bt} 直到構(gòu)成滑動(dòng)窗口SW;當(dāng)t＞R時(shí)，將滑動(dòng)窗口SW的最左邊t－R項(xiàng)單位數(shù)據(jù)移出，新采集的Bt進(jìn)入滑動(dòng)窗口，構(gòu)成新的滑動(dòng)窗口數(shù)據(jù)集。在保持隨機(jī)變分推理高效率的同時(shí)，擴(kuò)大用來計(jì)算噪聲項(xiàng)所包含的樣本信息。

當(dāng)滑動(dòng)窗口SW保留過去采集的樣本信息后，便可使用滑動(dòng)窗口中各單位數(shù)據(jù)噪聲項(xiàng)的加權(quán)和，取代當(dāng)前迭代的單位數(shù)據(jù)的噪聲項(xiàng)。由于每個(gè)數(shù)據(jù)單位都是隨機(jī)采集，且在原始數(shù)據(jù)集中，它們各自的狀態(tài)都是相同的，可對(duì)滑動(dòng)窗口內(nèi)各數(shù)據(jù)單位的影響同等看待，因此各噪聲項(xiàng)的權(quán)重均取1/R，計(jì)算得到新的噪聲項(xiàng)的值，其計(jì)算公式為:

由式(8)可以看出，相比SVI，滑動(dòng)窗口變相擴(kuò)大了樣本信息，以此改進(jìn)噪聲項(xiàng)的計(jì)算方法，可以減小隨機(jī)梯度的噪聲，使采用滑動(dòng)窗口計(jì)算得到的噪聲項(xiàng)更加接近批次變分推理中的值，噪聲變小使得該隨機(jī)梯度相較于SVI算法會(huì)更偏向真實(shí)梯度，隨機(jī)梯度的方差相比SVI也會(huì)減小，最終算法收斂速度會(huì)變快;而且當(dāng)滑動(dòng)窗口后移時(shí)，窗口樣本信息相應(yīng)改變，下一個(gè)噪聲項(xiàng)的計(jì)算包含了上一次采集的樣本信息，這使得噪聲得以平滑。

為避免重復(fù)計(jì)算滑動(dòng)窗口每個(gè)單位數(shù)據(jù)的噪聲項(xiàng)，而導(dǎo)致的時(shí)間復(fù)雜度的增加，VR-SVI算法可以在每次迭代時(shí)，存儲(chǔ)當(dāng)前Bt的噪聲項(xiàng)用于下次迭代計(jì)算，所以算法需要花費(fèi)滑動(dòng)窗口大小的空間代價(jià)來存儲(chǔ)窗口中單位數(shù)據(jù)的噪聲項(xiàng)。VR-SVI算法的偽代碼如算法1所示。

算法1 VR-SVI算法。

輸入 原始數(shù)據(jù)集的文檔數(shù)目D，樣本B的文檔數(shù)目M，學(xué)習(xí)率ρt，超參數(shù)α和η;

輸出 局部變分參數(shù)Φ和γ，全局變分參數(shù)λ。

初始化λ(0)、α和η，迭代計(jì)數(shù)變量t=0，學(xué)習(xí)率ρt，滑動(dòng)窗口隊(duì)列SW，窗口大小R

Repeat

從數(shù)據(jù)集中隨機(jī)采樣M篇文檔

Bt={1，2，…，M}

If t＜R

滑動(dòng)窗口SW←SW+Bt

Else

SW ← SW － SWt－R

SW←SW+Bt

初始化 γd，k=1，k ∈ {1，2，…，K}

Repeat

For d ∈ Bt，且 n ∈ {1，2，…，N}

使用式(4) 計(jì)算 γd，k

Until局部變分參數(shù)Φ和γ收斂

For k∈ {1，2，…，K}

If t＜R

Else

Until全局變分參數(shù)λ收斂

3 算法分析

本章首先分析本文提出的算法可在SVI基礎(chǔ)上實(shí)現(xiàn)隨機(jī)梯度方差減小的目標(biāo)。其次，由于滑動(dòng)窗口大小需要手動(dòng)取值，本章從算法角度分析R值大小對(duì)算法的影響，并在下面用實(shí)驗(yàn)來詳細(xì)描述其對(duì)算法的真實(shí)影響。最后，根據(jù)滑動(dòng)窗口內(nèi)樣本數(shù)據(jù)的交叉情況，對(duì)算法收斂性進(jìn)行分析。

3.1 方差減小分析

由式(8)、(10)、(12) 可以得到:

將式(13)中的項(xiàng)展開得到:

由于滑動(dòng)窗口的R次迭代中，SVI中隨機(jī)梯度的方差變化極小，可看作不變，E［(－)2］ =E［(－)2］。可得:

結(jié)合式(13)、(15)、(17)，則有:

由以上推理過程可以得知，本文提出的VR-SVI算法中隨機(jī)梯度與全梯度的方差是SVI算法的1/R，與真實(shí)梯度的方差也小于SVI算法中的方差，這表明本文提出的方法可達(dá)到減小方差、快速收斂的目的。

3.2 R值大小的影響分析

對(duì)于R值的取值，若R=1，意味著VR-SVI算法中滑動(dòng)窗口中的數(shù)據(jù)和SVI算法每次迭代時(shí)采集的樣本數(shù)據(jù)相同，那么VR-SVI算法隨機(jī)梯度的方差相比SVI沒有減小;若R＞1，算法的方差將會(huì)減小，由式(17)可以看出，隨著R值的增大，VR-SVI算法的方差減小效果越好;當(dāng)R增大到一定數(shù)值時(shí)，由于樣本包含信息增多，方差減小的效果將到達(dá)一個(gè)瓶頸。另外，由算法過程可以看出R值的增大并未使得算法的時(shí)間復(fù)雜度增加，但算法需要存儲(chǔ)最近的值來計(jì)算平均值，所需存儲(chǔ)空間會(huì)隨著R值的增大而增大。

為進(jìn)一步選取確定窗口大小R值，根據(jù)式(18)計(jì)算得到平方偏差(Square Bias，SB)、方差(Variance，VAR)和平方誤差(Square Error，SE):

其中:平方偏差通常隨著R值增大而增加。因?yàn)樵撈羁梢员３諶次迭代的記憶，所以能顯示復(fù)雜的時(shí)間演變，如果在平滑梯度上失去其對(duì)初始狀態(tài)的記憶，則通常帶有較大偏差。通常在迭代R次后，方差會(huì)變得近似平穩(wěn)。平方誤差的值則恰好是平方偏差和方差之和的近似值。由于平滑梯度的長(zhǎng)時(shí)間記憶，可以將“慣性”與R值相關(guān)聯(lián)。R值越大，VAR越小，其慣性越大。而在一個(gè)非局部最優(yōu)化的優(yōu)化設(shè)置中，慣性太多是有害的，會(huì)有最終陷入局部最佳狀態(tài)的危險(xiǎn)。在涉及LDA典型參數(shù)K=102和V=104情況下，權(quán)衡以上三個(gè)指標(biāo)，選擇100以內(nèi)的R值可產(chǎn)生最小的均方誤差。

3.3 收斂性分析

LDA模型目標(biāo)函數(shù)是非凸的，本文提出的VR-SVI算法是基于用于LDA模型的SVI算法改進(jìn)而來，需要判定算法是否能收斂到最優(yōu)解。由式(10)可以看出，VR-SVI算法的隨機(jī)梯度和SVI算法中的隨機(jī)梯度相比，變化的是噪聲項(xiàng)。在特殊情況下，它可以用來近似SVI算法中的期望值，如果滑動(dòng)窗口中的單位數(shù)據(jù)都是對(duì)完全不相交的文檔進(jìn)行采樣，那么VR-SVI算法的隨機(jī)梯度與SVI使用R×M尺寸樣本得到的隨機(jī)梯度沒有差別，即E［］≈E［］，則有E［］=E［－+ η +］≈E［－+η+=E［］。給定學(xué)習(xí)率ρt，算法可以收斂到最優(yōu)解［7］。而在一般情況下，如果滑動(dòng)窗口中的數(shù)據(jù)存在采集樣本交叉的情況，由4.1節(jié)可知，VR-SVI算法采用平均噪聲項(xiàng)的方法可平滑SVI算法的噪聲影響，隨機(jī)梯度方差減小，即E［(－ gt)2］≤E［(－ gt)2］，給定學(xué)習(xí)率ρt，算法同樣可以收斂到最優(yōu)解，由于噪聲平滑后的隨機(jī)梯度可以更接近真實(shí)梯度，算法的收斂速度會(huì)更快。

4 實(shí)驗(yàn)與結(jié)果分析

本章對(duì)提出的VR-SVI算法的性能進(jìn)行實(shí)驗(yàn)驗(yàn)證。首先，在文檔集上驗(yàn)證本文提出方差減小算法的有效性，并與SVI算 法［8］、Prox-SVRG 算 法［16］以 及 mini-batch SVRG 算法［18］作對(duì)比;其次，分析R值的不同取值對(duì)算法性能的影響，并討論如何選取R值;最后，對(duì)LDA模型分別應(yīng)用VR-SVI、SVI、Prox-SVRG和mini-batch SVRG算法，在大型文檔集上評(píng)估算法性能。本文實(shí)驗(yàn)中所涉及的參數(shù)設(shè)置利用了相關(guān)文獻(xiàn)［8，16，18］中的實(shí)驗(yàn)結(jié)果，選擇目標(biāo)函數(shù)下降最快的一組參數(shù)作為本文的實(shí)驗(yàn)參數(shù)，具體在以下實(shí)驗(yàn)中給出。

實(shí)驗(yàn)環(huán)境為4個(gè)節(jié)點(diǎn)組成的Hadoop集群，每個(gè)節(jié)點(diǎn)配置為Intel i5 1.8 GHz CPU、4 GB內(nèi)存和500 GB硬盤。節(jié)點(diǎn)之間通過千兆交換機(jī)相連，運(yùn)行Ubuntu 16.04.3 LTS和 Apache Hadoop 2.6.0?；贛apReduce并行計(jì)算框架設(shè)計(jì)并實(shí)現(xiàn)了VR-SVI算法，算法的處理步驟如下:

1)為各個(gè)數(shù)據(jù)點(diǎn)分配文檔，該過程的并行化由Map函數(shù)執(zhí)行。Map函數(shù)的輸入輸出的數(shù)據(jù)格式分別為〈文檔序號(hào)，局部參數(shù)〉和〈窗口序號(hào)，噪聲項(xiàng)〉。運(yùn)行過程中Map函數(shù)通過計(jì)算得到基于收斂的局部參數(shù)的噪聲項(xiàng)，輸出結(jié)果。

2)計(jì)算各個(gè)數(shù)據(jù)點(diǎn)的均值來更新噪聲項(xiàng)，該過程的并行化由Reduce函數(shù)執(zhí)行。Reduce函數(shù)輸入輸出的數(shù)據(jù)格式為〈窗口序號(hào)，噪聲項(xiàng)〉和〈窗口序號(hào)，全局參數(shù)〉。在運(yùn)行過程中Reduce函數(shù)把數(shù)據(jù)按照其被分配的窗口進(jìn)行整合，使得屬于同一窗口的數(shù)據(jù)被同一個(gè)Reduce函數(shù)接收，然后計(jì)算噪聲項(xiàng)的均值，進(jìn)而得到全局參數(shù)。

Map-Reduce算法內(nèi)容如下。

VR-SVI::Map(each mapper)。

輸入 樣本B的文檔數(shù)目M，超參數(shù)α和η;

輸出 鍵值對(duì)〈窗口序號(hào)，噪聲項(xiàng)〉。

隨機(jī)采樣M篇文檔

Repeat

For d ∈ Bt，且 n ∈ {1，2，…，N}

使用式(4) 計(jì)算 γd，k

Until局部變分參數(shù)Φ和γ收斂

For k∈ {1，2，…，K}

VR-SVI::Reduce(each reducer)。

輸入 鍵值對(duì)〈窗口序號(hào)，噪聲項(xiàng)〉;

輸出 鍵值對(duì)〈窗口序號(hào)，全局參數(shù)〉。

For窗口序號(hào)相同的鍵值對(duì)〈窗口序號(hào)，噪聲項(xiàng)〉

實(shí)驗(yàn)數(shù)據(jù)集存放在分布式文件系統(tǒng)中，兩個(gè)數(shù)據(jù)集均可以從UC Irvine Machine Learning Repository網(wǎng)站獲得，下載地址 為 http://archive.ics.uci. edu/ml/machine-learningdatabases/bag-of-words/。表1給出文檔集的詳細(xì)信息。

表1 文檔集描述Tab.1 Document set description

4.1 方差減小效果對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)的目的是驗(yàn)證VR-SVI算法的實(shí)際方差減小效果，并與 SVI、Prox-SVRG以及 mini-batch SVRG算法進(jìn)行對(duì)比。算法中的樣本Bi的大小設(shè)置為M=300，主題數(shù)設(shè)置為K=100，超參數(shù)α =0.5，η =0.01，學(xué)習(xí)率固定為ρ=10－3。3種算法方差比較的結(jié)果如圖1所示，橫坐標(biāo)表示算法的迭代次數(shù)t，縱坐標(biāo)表示算法的方差var，即每次迭代時(shí)所用梯度與真實(shí)梯度之間差值的平方，圖中結(jié)果是每個(gè)算法運(yùn)行10次得到的平均值，VR-SVI(10)、VR-SVI(20)和VR-SVI(30)分別表示R值為10、20和30的VR-SVI算法。

由圖1可以看出，VR-SVI算法的方差減小程度明顯優(yōu)于SVI和mini-batch SVRG算法，但比Prox-SVRG算法的方差減小效果要差。同時(shí)，隨著R值的增大，VR-SVI算法方差減小的效果超過mini-batch SVRG，更接近Prox-SVRG算法，原因是Prox-SVRG算法每次迭代時(shí)都是使用全部樣本計(jì)算梯度的，而VR-SVI算法每次迭代時(shí)只是使用窗口中的樣本計(jì)算梯度，減少了計(jì)算次數(shù)，不過隨著R值的增大，窗口內(nèi)的樣本數(shù)量增加，其計(jì)算得到的梯度更加接近真實(shí)梯度，方差減小的效果也會(huì)越好。

圖1 算法方差減小比較Fig.1 Comparison of algorithms on variance reduction

4.2 R值對(duì)算法的影響

由于VR-SVI算法是基于滑動(dòng)窗口計(jì)算隨機(jī)梯度，R值的變化對(duì)應(yīng)滑動(dòng)窗口大小的變化，本實(shí)驗(yàn)在兩個(gè)數(shù)據(jù)集上研究R值的不同取值對(duì)算法實(shí)際性能的影響，提出對(duì)R值的合理設(shè)置。實(shí)驗(yàn)采取的算法性能評(píng)價(jià)指標(biāo)是詞匯似然度(likelihoodpw)［14，20－21］，將文檔集分為將數(shù)據(jù)集劃分成 10 份，每次是其中的4份作為訓(xùn)練集Dtrain訓(xùn)練模型，剩余的6份作為測(cè)試集Dtest檢測(cè)模型性能。再將測(cè)試集平均分為wd1和wd2兩個(gè)部分。對(duì)數(shù)據(jù)集進(jìn)行交叉驗(yàn)證，執(zhí)行10次，計(jì)算wd2中在wd1和Dtrain條件下詞的預(yù)測(cè)對(duì)數(shù)似然，取平均值。對(duì)wd1有較好的預(yù)測(cè)分布應(yīng)該能夠給出對(duì)wd2更高的對(duì)數(shù)似然，意味著算法性能更好。likelihoodpw計(jì)算方法如下:

其中:|wd2|表示wd2中的詞匯數(shù)量。對(duì)p(wd2|wd1，Dtrain)的估計(jì)如下:

不同R值的VR-SVI算法的likelihoodpw變化如圖2所示。其中，由3.2節(jié)的分析，R值分別取100內(nèi)的5個(gè)數(shù)值，算法在兩個(gè)數(shù)據(jù)集上有效運(yùn)行時(shí)間的最大值設(shè)為10 h，縱坐標(biāo)表示likelihoodpw的值。

圖2 不同R值的likelihoodpw變化趨勢(shì)比較Fig.2 Comparison of likelihoodpwvariation trend with different R values

由圖2可以看出，在兩個(gè)數(shù)據(jù)集上可以觀察到非常相似的趨勢(shì)，較大的R值表現(xiàn)優(yōu)于較小值。對(duì)于Wikipedia，R=30和R=60時(shí)，likelihoodpw的值最大，兩者表現(xiàn)幾乎相同;對(duì)于New York Times，R=30和R=60時(shí)，likelihoodpw的值的分?jǐn)?shù)較大，且明顯超過其他R值的表現(xiàn)。隨著R值增大，算法達(dá)到收斂的運(yùn)行時(shí)間也在變長(zhǎng)。事實(shí)上，在每次迭代中，VR-SVI的隨機(jī)梯度實(shí)際上由R×M文件生成。隨機(jī)梯度的質(zhì)量主要取決于這些文件與整個(gè)語料庫(kù)之間的信息差異，這種差異可用詞頻來大致地評(píng)估，每個(gè)詞的詞頻等于其數(shù)目除以出現(xiàn)的詞的總數(shù)。表2顯示了在隨機(jī)迭代中，Wikipedia中不同R值的五個(gè)隨機(jī)詞的單詞頻率，可以發(fā)現(xiàn)在R=30和R=60時(shí)的單詞頻率接近真實(shí)值，R=30和R=60時(shí)的差異明顯小于其他R值的差異，這種情況也和在Wikipedia上實(shí)驗(yàn)的結(jié)果相近。考慮到R=60時(shí)，算法花費(fèi)的時(shí)間以及空間代價(jià)相對(duì)較大，可以選取R=30作為4.3節(jié)實(shí)驗(yàn)的參數(shù)設(shè)置。

表2 Wikipedia中不同R值的五個(gè)隨機(jī)單詞的詞頻 %Tab.2 Word frequencies for five random words with different R values in Wikipedia %

4.3 算法性能比較

本節(jié)在大型文檔集上對(duì)比 VR-SVI、SVI、Prox-SVRG和mini-batch SVRG算法性能。由4.2節(jié)可得，VR-SVI算法中R值設(shè)置為30，實(shí)驗(yàn)采取的算法性能評(píng)價(jià)指標(biāo)是likelihoodpw，實(shí)驗(yàn)的其余參數(shù)M=300，主題數(shù)為K=100，超參數(shù)α =0.5、η =0.01，學(xué)習(xí)率固定為ρ=10－3。每個(gè)算法應(yīng)用于LDA主題模型，各運(yùn)行10 次，取平均值。圖3為VR-SVI、SVI、Prox-SVRG及mini-batch SVRG算法在LDA模型中運(yùn)行的性能likelihoodpw隨時(shí)間變化的趨勢(shì)。

圖3 不同算法的likelihoodpw變化趨勢(shì)比較Fig.3 Comparison of likelihoodpwvariation trend of different algorithms

由圖3可以看出，相比SVI和mini-batch SVRG，VR-SVI的likelihoodpw值在所有情況下都明顯比較大;對(duì)于Prox-SVRG，VR-SVI的likelihoodpw值很接近，這表明本文所提的算法對(duì)平滑SVI中隨機(jī)梯度的噪聲有積極的影響，其性能接近于使用全梯度來修正單個(gè)樣本梯度的Prox-SVRG算法，實(shí)現(xiàn)了更好的性能。而且由兩個(gè)數(shù)據(jù)庫(kù)上得到的likelihoodpw的變化趨勢(shì)可以看出，VR-SVI能夠比其他算法更快地收斂。對(duì)于Wikipedia語料庫(kù)，VR-SVI在約2 h后收斂，但是SVI在約4 h后才收斂，mini-batch SVRG和Prox-SVRG在約3 h后收斂;對(duì)于New York Times語料庫(kù)，VR-SVI約2 h后收斂，但SVI、Prox-SVRG和mini-batch SVRG均在約4 h后才開始收斂?？偟恼f來，本實(shí)驗(yàn)進(jìn)一步驗(yàn)證了，相比SVI、Prox-SVRG以及mini-batch SVRG算法，VR-SVI算法能夠有效地減少隨機(jī)梯度的噪聲，并且獲得更快的收斂速度，其擁有更好的綜合性能以及更高的效率。

5 結(jié)語

針對(duì)主題模型處理大規(guī)模文檔應(yīng)用中平滑噪聲并達(dá)到快速收斂的目標(biāo)，本文基于隨機(jī)變分推理的思想提出了一種可以減小梯度方差的算法VR-SVI，該算法設(shè)置了一個(gè)滑動(dòng)窗口，主動(dòng)平滑隨機(jī)梯度的噪聲，為算法中隨機(jī)梯度的構(gòu)建和全局變分參數(shù)的更新提供了一個(gè)新思路。在處理隨機(jī)梯度的噪聲時(shí)，該算法兼顧了方差減小的效果和算法的效率，從而使得算法能夠達(dá)到快速收斂，提高算法性能。然而，VR-SVI算法為保證計(jì)算效率，在對(duì)隨機(jī)梯度的噪聲進(jìn)行平滑時(shí)，需要保存滑動(dòng)窗口中迭代得到的R個(gè)噪聲項(xiàng)，雖有利于對(duì)隨機(jī)梯度的重新計(jì)算，但導(dǎo)致少部分的內(nèi)存占用。另外，本文僅在大規(guī)模數(shù)據(jù)集上對(duì)R值大小的影響進(jìn)行了實(shí)驗(yàn)，如何快速有效地判定滑動(dòng)窗口R值的大小也成為一個(gè)關(guān)鍵問題。因此，下一步的工作是研究更加高效的R值選取方式，使其能夠針對(duì)數(shù)據(jù)集進(jìn)行適應(yīng)變化，并將所設(shè)計(jì)的方法用于主題模型處理大規(guī)模數(shù)據(jù)集上，檢驗(yàn)其有效性。