SparkCRF：一種基于Spark的并行CRFs算法實(shí)現(xiàn)

朱繼召　賈巖濤　徐　君　喬建忠　王元卓　程學(xué)旗

1(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院　沈陽(yáng)　110819)2　　　(中國(guó)科學(xué)院計(jì)算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室　北京　100190)

?

SparkCRF：一種基于Spark的并行CRFs算法實(shí)現(xiàn)

朱繼召1,2賈巖濤2徐君2喬建忠1王元卓2程學(xué)旗2

1(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院沈陽(yáng)110819)2(中國(guó)科學(xué)院計(jì)算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室北京100190)

(zhujzh.paper@gmail.com)

條件隨機(jī)場(chǎng)(conditionrandomfields,CRFs)可用于解決各種文本分析問題，如自然語(yǔ)言處理(naturallanguageprocessing,NLP)中的序列標(biāo)記、中文分詞、命名實(shí)體識(shí)別、實(shí)體間關(guān)系抽取等.傳統(tǒng)的運(yùn)行在單節(jié)點(diǎn)上的條件隨機(jī)場(chǎng)在處理大規(guī)模文本時(shí)，面臨一系列挑戰(zhàn).一方面，個(gè)人計(jì)算機(jī)遇到處理的瓶頸從而難以勝任；另一方面，服務(wù)器執(zhí)行效率較低.而通過升級(jí)服務(wù)器的硬件配置來提高其計(jì)算能力的方法，在處理大規(guī)模的文本分析任務(wù)時(shí)，終究不能從根本上解決問題.為此，采用“分而治之”的思想，基于ApacheSpark的大數(shù)據(jù)處理框架設(shè)計(jì)并實(shí)現(xiàn)了運(yùn)行在集群環(huán)境下的分布式CRFs——SparkCRF.實(shí)驗(yàn)表明，SparkCRF在文本分析任務(wù)中，具有高效的計(jì)算能力和較好的擴(kuò)展性，并且具有與傳統(tǒng)的單節(jié)點(diǎn)CRF++相同水平的準(zhǔn)確率.

大數(shù)據(jù)；機(jī)器學(xué)習(xí)；分布式計(jì)算；Spark；條件隨機(jī)場(chǎng)

條件隨機(jī)場(chǎng)(conditionrandomfields,CRFs)[1]是在已知輸入隨機(jī)變量條件下，輸出隨機(jī)變量的條件概率分布模型.可以用于文本分析、計(jì)算機(jī)視覺、生物信息學(xué)等眾多領(lǐng)域中的預(yù)測(cè)問題，如自然語(yǔ)言處理中的序列標(biāo)記、中文分詞、命名實(shí)體識(shí)別，實(shí)體間關(guān)系抽取等.隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計(jì)算等技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)空間中各類應(yīng)用層出不窮，引發(fā)了數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)[2]，預(yù)計(jì)到2020 年，全球的數(shù)據(jù)總量將達(dá)到35ZB.傳統(tǒng)的運(yùn)行在單節(jié)點(diǎn)上的CRFs工具在處理大規(guī)模計(jì)算任務(wù)時(shí)(任務(wù)的計(jì)算規(guī)模與訓(xùn)練集大小、模板和輸出標(biāo)記數(shù)量有關(guān))，面臨一系列挑戰(zhàn).一方面，個(gè)人計(jì)算機(jī)遇到處理的瓶頸從而難以勝任；另一方面，服務(wù)器執(zhí)行效率較低.在面對(duì)大數(shù)據(jù)[3-4]時(shí)代下的大規(guī)模計(jì)算任務(wù)時(shí)，通過升級(jí)服務(wù)器的硬件配置來提高其計(jì)算能力的方法，終究不能從根本上解決問題.因而，將大規(guī)模計(jì)算任務(wù)轉(zhuǎn)移到分布式集群平臺(tái)上處理，成為了解決以上問題的有效途徑.代表性的批處理系統(tǒng)有MapReduce[5],Storm[6],Spark[7],Scribe,Samza,Flume,Nutch,Dremel[8],Pregel[9]和Trinity[10]等，其中Spark近年來受到了更多用戶的青睞并成為了最活躍、最高效的大數(shù)據(jù)通用計(jì)算平臺(tái).這些優(yōu)秀分布式處理框架，使得開發(fā)分布式應(yīng)用、充分利用集群中的資源變得十分容易，從而大大減小了大規(guī)模數(shù)據(jù)分析任務(wù)的難度.

為了解決CRFs在處理較大數(shù)據(jù)集時(shí)的低效問題，文獻(xiàn)[11]基于多核實(shí)現(xiàn)了CRFs訓(xùn)練過程的并行化;文獻(xiàn)[12]通過將學(xué)習(xí)過程分解為若干更小、更簡(jiǎn)單子問題的方式來處理復(fù)雜的計(jì)算任務(wù);文獻(xiàn)[13]基于MapReduce計(jì)算框架實(shí)現(xiàn)了CRFs的訓(xùn)練過程并行化，在保證訓(xùn)練結(jié)果正確性的同時(shí)，大大減少了訓(xùn)練時(shí)間，性能上也得到了一定的提升.然而，由于MapReduce自身的實(shí)現(xiàn)機(jī)制，每次Mapper需要將計(jì)算結(jié)果寫入磁盤.對(duì)于訓(xùn)練過程需要大量迭代操作的機(jī)器學(xué)習(xí)算法，這在效率上存在瓶頸，尤其針對(duì)大規(guī)模訓(xùn)練數(shù)據(jù)集的計(jì)算任務(wù).

針對(duì)單機(jī)CRFs在處理大規(guī)模訓(xùn)練數(shù)據(jù)集時(shí)存在的問題.我們采用“分而治之”的思想，基于ApacheSpark大數(shù)據(jù)處理框架設(shè)計(jì)并實(shí)現(xiàn)了運(yùn)行在集群環(huán)境下的分布式CRFs——SparkCRF.SparkCRF充分利用了Spark提供的彈性分布式數(shù)據(jù)集(residentdistributeddatasets,RDD)，將所有的數(shù)據(jù)轉(zhuǎn)化成RDD存儲(chǔ)在集群節(jié)點(diǎn)的內(nèi)存中，實(shí)現(xiàn)了基于內(nèi)存的分布式計(jì)算方式.最后，通過設(shè)計(jì)的3組實(shí)驗(yàn)，分別從執(zhí)行效率、可擴(kuò)展性和正確性方面對(duì)SparkCRF進(jìn)行評(píng)估.實(shí)驗(yàn)表明，SparkCRF具有高效執(zhí)行計(jì)算任務(wù)的能力和較好的可擴(kuò)展性，并且具有與CRF++相同水平的預(yù)測(cè)準(zhǔn)確率.

1　背景知識(shí)

1.1條件隨機(jī)場(chǎng)

CRFs作為一種統(tǒng)計(jì)序列模型首先于2001年被Lafferty提出[1]，至今，已被廣泛應(yīng)用到自然語(yǔ)言處理、計(jì)算機(jī)視覺、生物信息學(xué)等眾多領(lǐng)域中.模型思想的主要來源是最大熵模型，是在給定待標(biāo)記的觀察序列條件下的整個(gè)標(biāo)記序列的聯(lián)合概率分布，模型中的概率計(jì)算、學(xué)習(xí)和預(yù)測(cè)3個(gè)問題的解決和隱馬爾可夫模型(hiddenMarkovmodel,HMMs)模型類似，使用到的算法如前向-后向和維特比.

CRFs是一種用來標(biāo)記和切分序列化數(shù)據(jù)的概率統(tǒng)計(jì)模型.通常被用于在給定需要標(biāo)記的觀察序列的條件下，計(jì)算整個(gè)標(biāo)記序列的聯(lián)合概率.標(biāo)記序列的分布條件屬性，可以讓CRFs很好地?cái)M和現(xiàn)實(shí)數(shù)據(jù)，而在這些數(shù)據(jù)中，標(biāo)記序列的條件概率信賴于觀察序列中非獨(dú)立的、相互作用的特征，并通過賦予特征以不同權(quán)值來表示特征的重要程度.

條件隨機(jī)場(chǎng)的定義：設(shè)X與Y是隨機(jī)變量，P(Y|X)是在給定X的條件下Y的條件概率分布.若隨機(jī)變量Y構(gòu)成一個(gè)由無(wú)向圖G=(V,E)表示的馬爾可夫隨機(jī)場(chǎng)(Markovrandomfield,MRF)，即P(Yv|X,Yw,w≠v)=P(Yv|X,Yw,w～v)對(duì)任意節(jié)點(diǎn)v成立，則稱條件概率分布P(Y|X)為條件隨機(jī)場(chǎng)，其中w～v表示在同G=(V,E)中與節(jié)點(diǎn)v有邊鏈接的所有節(jié)點(diǎn)w，w≠v表示節(jié)點(diǎn)v以外的所有節(jié)點(diǎn)，Yv，Yu，Yw為節(jié)點(diǎn)v，u，w對(duì)應(yīng)的隨機(jī)變量.

①https:sourceforge.netprojectscrfpp

條件隨機(jī)場(chǎng)能夠充分地利用上下文信息從而達(dá)到良好的標(biāo)注效果，目前實(shí)際應(yīng)用中最常用的是一階鏈?zhǔn)浇Y(jié)構(gòu)的CRF模型，即線性鏈結(jié)構(gòu)(linear-chainCRFs)，其結(jié)構(gòu)如圖1所示:

Fig. 1　The structure of linear Chain CRFs.圖1　線性鏈條件隨機(jī)場(chǎng)

條件隨機(jī)場(chǎng)的參數(shù)化形式定義：設(shè)P(Y|X)為線性鏈條件隨機(jī)場(chǎng)，則在隨機(jī)變量X 取值為x的條件下，隨機(jī)變量Y 取值為y 的條件概率

其中，

式子中，tk和sl是特征函數(shù)，λk和λl是對(duì)應(yīng)的權(quán)值，Z(x)是規(guī)范化因子，求和是在所有可能的輸出序列上進(jìn)行的.tk是定義在邊上的特征函數(shù)，稱為轉(zhuǎn)移特征，依賴于當(dāng)前和前一個(gè)位置，sl是定義在節(jié)點(diǎn)上的特征函數(shù)，稱為狀態(tài)特征，依賴于當(dāng)前位置.tk和sl都依賴于位置，是局部特征函數(shù).通常，特征函數(shù)tk和sl取值為1或0；當(dāng)滿足特征條件時(shí)取值為1，否則為0.條件隨機(jī)場(chǎng)完全由特征函數(shù)tk，sl和對(duì)應(yīng)的權(quán)值λk、λl確定.

1.2Spark計(jì)算框架

Spark[7]是一種基于內(nèi)存計(jì)算的分布式集群計(jì)算框架.與MapReduce相比具有多方面的改進(jìn)，即較低的網(wǎng)絡(luò)傳輸和磁盤IO使得效率得到提高，Spark使用內(nèi)存進(jìn)行數(shù)據(jù)計(jì)算以便快速處理查詢、實(shí)時(shí)返回分析結(jié)果，Spark提供比Hadoop更高層的API，同樣的算法在Spark中的運(yùn)行速度比Hadoop快10～100倍[7].

Spark是為集群計(jì)算中的特定類型的工作負(fù)載而設(shè)計(jì)，即在并行操作之間重用工作數(shù)據(jù)集(比如機(jī)器學(xué)習(xí)任務(wù))的工作負(fù)載.Spark的計(jì)算架構(gòu)具有3個(gè)特點(diǎn)：

1)Spark擁有輕量級(jí)的集群計(jì)算框架.它將Scala應(yīng)用于其程序架構(gòu)，而Scala這種多范式的編程語(yǔ)言具有并發(fā)性、可擴(kuò)展性以及支持編程范式的特征，與Spark緊密結(jié)合，能夠輕松地操作分布式數(shù)據(jù)集，并且可以輕易地添加新的語(yǔ)言結(jié)構(gòu).

2)Spark包含了大數(shù)據(jù)領(lǐng)域的數(shù)據(jù)流計(jì)算和交互式計(jì)算.Spark可以與HDFS[14]交互取得里面的數(shù)據(jù)文件，同時(shí)Spark的迭代、內(nèi)存計(jì)算以及交互式計(jì)算為數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)提供了很好的框架.

3)Spark有很好的容錯(cuò)機(jī)制.Spark使用了RDD，RDD被表示為Scala對(duì)象分布在一組節(jié)點(diǎn)中的被序列化的、只讀的、具有容錯(cuò)機(jī)制的并且可被并行執(zhí)行的對(duì)象集合.Spark高效處理分布數(shù)據(jù)集的特征使其成為了最活躍、最高效的大數(shù)據(jù)通用計(jì)算平臺(tái).圖2描述了Spark的運(yùn)行模式.

Fig. 2　Operation schema of Spark.圖2　Spark運(yùn)行模式

2　問題提出

在眾多的CRFs算法工具中，最具代表性的是CRF++①.CRF++提供了Linux和Windows2個(gè)版本，是一款開源的用于分詞、序列標(biāo)記等任務(wù)的工具.它的設(shè)計(jì)和實(shí)現(xiàn)基于通用性的目的，并已被應(yīng)用于多種自然語(yǔ)言處理任務(wù).CRF++是單機(jī)程序，它能夠處理的計(jì)算規(guī)模與機(jī)器的硬件配置關(guān)系密切，其中計(jì)算規(guī)模與訓(xùn)練集大小、模板和輸出標(biāo)記數(shù)量有關(guān).這些單機(jī)實(shí)現(xiàn)工具在處理計(jì)算規(guī)模較大的任務(wù)時(shí)，面臨一系列挑戰(zhàn).1)由于個(gè)人計(jì)算機(jī)的處理能力有限，在面對(duì)較大規(guī)模的計(jì)算任務(wù)時(shí)往往難以勝任；2)服務(wù)器處理能力較為強(qiáng)大，但在處理大規(guī)模計(jì)算任務(wù)時(shí)執(zhí)行效率卻不夠高.單純的通過升級(jí)服務(wù)器的硬件配置來獲得更強(qiáng)的處理能力的方法，面對(duì)大數(shù)據(jù)時(shí)代下更大規(guī)模的處理任務(wù)，其終究不能從根本上解決問題.

①http://nlp.fudan.edu.cn//nlpcc2015//

我們以CRF++為例，通過實(shí)驗(yàn)來說明以上問題.實(shí)驗(yàn)設(shè)計(jì)如下：1)實(shí)驗(yàn)環(huán)境：運(yùn)行環(huán)境分別為個(gè)人計(jì)算機(jī)和服務(wù)器，配置信息見表1；2)實(shí)驗(yàn)數(shù)據(jù)：使用NLPCC2015①公開數(shù)據(jù)集，選用中文分詞數(shù)據(jù)集train-POS-EN.txt，該數(shù)據(jù)集大小共3MB，包含10 000個(gè)句子，輸出標(biāo)記共122個(gè)；3)模板配置：分別使用窗口大小為3和5的配置模板用于訓(xùn)練過程中特征抽取.

Table 1　The Configuration of Experiment Platforms表1　實(shí)驗(yàn)平臺(tái)配置信息

對(duì)于個(gè)人計(jì)算機(jī)，我們對(duì)訓(xùn)練集以句子為單位進(jìn)行切分，切分后的訓(xùn)練集包含的句子總數(shù)分別為：100，200，300，400，500，….在每個(gè)訓(xùn)練集上按照實(shí)驗(yàn)的設(shè)計(jì)對(duì)每個(gè)訓(xùn)練過程分別重復(fù)進(jìn)行5次，取5次的平均執(zhí)行時(shí)間作為最終結(jié)果，并統(tǒng)計(jì)對(duì)應(yīng)的特征數(shù)，實(shí)驗(yàn)結(jié)果如圖3所示：

Fig. 3　Experiment results on personal computer.圖3　個(gè)人計(jì)算機(jī)上實(shí)驗(yàn)結(jié)果

從圖3(a)可以看出：窗口大小為3時(shí)，能夠處理的訓(xùn)練集最多為3 000條句子；窗口為5時(shí)，能夠處理的訓(xùn)練集最多為800條句子.當(dāng)訓(xùn)練集大小達(dá)到上限后，若繼續(xù)增加訓(xùn)練句子數(shù)量，將會(huì)導(dǎo)致系統(tǒng)異常而終止程序運(yùn)行.出現(xiàn)這種現(xiàn)象的原因從圖3(b)中可知：隨著訓(xùn)練集句子規(guī)模的增大，對(duì)應(yīng)特征數(shù)量也在增長(zhǎng).但對(duì)于相同規(guī)模的訓(xùn)練集，特征數(shù)量卻不同，這與所使用模板窗口大小有關(guān).對(duì)于不同的窗口設(shè)置，當(dāng)?shù)竭_(dá)機(jī)器所能處理的上限時(shí)，所對(duì)應(yīng)訓(xùn)練集的特征數(shù)基本相同(約1 400萬(wàn)).

對(duì)于服務(wù)器，我們同樣按句子對(duì)訓(xùn)練集進(jìn)行切分，切分后的訓(xùn)練集句子總數(shù)分別為：1 000，2 000，3 000，4 000，5 000，…，10 000.在每個(gè)訓(xùn)練集上按照實(shí)驗(yàn)的設(shè)計(jì)對(duì)每個(gè)訓(xùn)練過程分別重復(fù)進(jìn)行5次，取5次的平均執(zhí)行時(shí)間作為最終結(jié)果，并統(tǒng)計(jì)對(duì)應(yīng)的特征數(shù)，實(shí)驗(yàn)結(jié)果如圖4所示：

Fig. 4　Experiment results on server.圖4　服務(wù)器上實(shí)驗(yàn)結(jié)果

從圖4(a)可知，訓(xùn)練時(shí)間隨訓(xùn)練集的增大不斷增長(zhǎng)；當(dāng)訓(xùn)練集大小從1 000增加到8 000時(shí)，2種窗口情況下的耗時(shí)基本相同.從4(b)可以看出，隨著訓(xùn)練集的增加，特征個(gè)數(shù)成線性增長(zhǎng)；窗口為5時(shí)的增長(zhǎng)速度遠(yuǎn)快于窗口為3時(shí).當(dāng)訓(xùn)練集增加到10 000個(gè)句子時(shí)，整個(gè)訓(xùn)練過程需要7h以上，而此時(shí)的訓(xùn)練集卻僅僅3MB.

實(shí)驗(yàn)告訴我們：對(duì)于個(gè)人計(jì)算機(jī)，其能夠處理的計(jì)算規(guī)模十分有限；而服務(wù)器執(zhí)行效率較低.通過升級(jí)服務(wù)器的硬件配置來提高其計(jì)算能力的方法，在處理大規(guī)模的文本分析任務(wù)時(shí)，終究不能從根本上解決問題.

根據(jù)以上實(shí)驗(yàn)分析設(shè)想：如果將大的訓(xùn)練集合分割成若干個(gè)小的訓(xùn)練集，在多臺(tái)機(jī)器間分布式并行執(zhí)行，即采用“分而治之”的思想?yún)f(xié)同工作，那么可處理的訓(xùn)練集大小將會(huì)成線性增長(zhǎng).本文以此為動(dòng)機(jī)，將傳統(tǒng)的CRFs單機(jī)運(yùn)行模式實(shí)現(xiàn)為分布式集群運(yùn)行模式，采用目前分布式計(jì)算框架Spark，以HDFS[14]作為數(shù)據(jù)存儲(chǔ)平臺(tái).

3　相關(guān)工作

從2001年CRFs被Lafferty提出，已被廣泛應(yīng)用到自然語(yǔ)言處理、計(jì)算機(jī)視覺、生物信息學(xué)等眾多領(lǐng)域中.到目前為止，很多工作致力于CRFs算法工具的實(shí)現(xiàn)，最具代表性的是CRF++.此外，還有CRF-ADF,GRMM,DGM,CRFall,CRFSuite等.以上實(shí)現(xiàn)存在單機(jī)運(yùn)行模式的共同特點(diǎn)，因此，使用這些工具處理大規(guī)模計(jì)算任務(wù)時(shí)必然會(huì)面臨一系列挑戰(zhàn)：1)個(gè)人計(jì)算機(jī)遇到處理的瓶頸從而難以勝任；2)服務(wù)器執(zhí)行效率較低.

文獻(xiàn)[11]為了解決CRFs的訓(xùn)練過程在規(guī)模較大數(shù)據(jù)集耗時(shí)、低效問題，基于多核實(shí)現(xiàn)了CRFs訓(xùn)練過程的并行化.使得CRFs能夠處理的訓(xùn)練集規(guī)模可達(dá)到百上千條序列和百萬(wàn)級(jí)別特征;文獻(xiàn)[12]通過將學(xué)習(xí)過程分解為若干更小、更簡(jiǎn)單子問題的方式，來處理復(fù)雜的計(jì)算任務(wù);文獻(xiàn)[13]通過在CRFs模型中引入懲罰項(xiàng)控制非零系數(shù)的個(gè)數(shù)，同時(shí)又可避免能夠?qū)е麓缶S度參數(shù)設(shè)置的數(shù)字問題.在忽略執(zhí)行時(shí)間因素下，實(shí)現(xiàn)了CRF用于處理幾百個(gè)輸出標(biāo)志和多達(dá)幾十億特征的訓(xùn)練任務(wù);文獻(xiàn)[15]對(duì)CRF采用平均場(chǎng)近似推理及高斯對(duì)勢(shì)函數(shù)，提出一種新的神經(jīng)網(wǎng)絡(luò)CRF-RNN，用作CNN的一部分來得到一種具有CNN和CRF的屬性的深度網(wǎng)絡(luò)應(yīng)用于圖像識(shí)別.

文獻(xiàn)[16]基于MapReduce計(jì)算框架實(shí)現(xiàn)了CRFs的訓(xùn)練過程并行化.該方法確保訓(xùn)練結(jié)果正確性的同時(shí)，大大減少了訓(xùn)練時(shí)間，性能也得到了一定的提升.由于MapReduce自身的機(jī)制，每次Map完成需要將操作結(jié)果存入磁盤，這顯然對(duì)于訓(xùn)練過程需要大量迭代操作的機(jī)器學(xué)習(xí)類算法在實(shí)現(xiàn)效率上存在瓶頸.因此，這種基于MapReduce的實(shí)現(xiàn)雖然能夠處理較大規(guī)模的訓(xùn)練集和特征集，但運(yùn)行效率并不高.

文獻(xiàn)[17]基于Spark提出一種并行蟻群優(yōu)化算法，相比于基于MapReduce平臺(tái)下的實(shí)現(xiàn)，在速度上提升10倍以上；文獻(xiàn)[18]基于Spark實(shí)現(xiàn)了并行化頻繁項(xiàng)集挖掘算法，并在多項(xiàng)基準(zhǔn)實(shí)驗(yàn)上與基于MapReduce的實(shí)現(xiàn)算法進(jìn)行對(duì)比，實(shí)驗(yàn)證明基于Spark的頻繁項(xiàng)集挖掘算法比基于MapReduce的實(shí)現(xiàn)在運(yùn)行速度上平均提升了18倍.語(yǔ)義數(shù)據(jù)在大數(shù)據(jù)時(shí)代下快速增加，傳統(tǒng)的單機(jī)語(yǔ)義推理實(shí)現(xiàn)工具的處理能力面臨了嚴(yán)峻的挑戰(zhàn)；文獻(xiàn)[19]在Spark框架上實(shí)現(xiàn)了一種高效的大規(guī)模RDFSOWL推理工具Cichlid，并具有良好的可擴(kuò)展性和容錯(cuò)能力.

4　SparkCRF的實(shí)現(xiàn)

本節(jié)描述SparkCRF的實(shí)現(xiàn)過程，在工作流程上它包含2個(gè)階段：訓(xùn)練和預(yù)測(cè).SparkCRF在集群中通過創(chuàng)建DriverExecutor進(jìn)程實(shí)現(xiàn)分布式運(yùn)行，對(duì)輸入數(shù)據(jù)格式的要求與CRF++一致.

4.1訓(xùn)練階段

訓(xùn)練階段包含數(shù)據(jù)加載、特征抽取和循環(huán)迭代調(diào)整特征權(quán)重的訓(xùn)練過程，最終生成訓(xùn)練模型.

該階段所用到特征模板、訓(xùn)練集數(shù)據(jù)預(yù)先存儲(chǔ)在HDFS中，將數(shù)據(jù)轉(zhuǎn)換成SparkRDD形式存儲(chǔ)到集群的內(nèi)存，圖5描述了通用的加載過程.

特征模板和訓(xùn)練集數(shù)據(jù)以Block形式存儲(chǔ)在HDFS系統(tǒng)中，由SparkContext對(duì)象通過textFile方法將數(shù)據(jù)轉(zhuǎn)化為以Partition形式存儲(chǔ)的RDD并加載到內(nèi)存中.對(duì)于特征模板RDD調(diào)用filter并傳入規(guī)則，將無(wú)效數(shù)據(jù)過濾，然后分別獲取U和B模板.訓(xùn)練集RDD通過一系列轉(zhuǎn)換(transformations)操作進(jìn)行處理，將原始數(shù)據(jù)以句子為單位根據(jù)自定義的類型轉(zhuǎn)化為句子封裝類，每個(gè)Partition中包含若干個(gè)封裝類單元存儲(chǔ)在集群節(jié)點(diǎn)的內(nèi)存中.

算法1. 訓(xùn)練過程偽代碼.

輸入：訓(xùn)練集RDD、SparkContext對(duì)象、迭代最大次數(shù)和收斂條件；

輸出：特征集合、權(quán)值向量、模型元數(shù)據(jù).

Loop：

Executor：

對(duì)每個(gè)包裝實(shí)例：

重置圖中所有node和edge對(duì)象的cost值；

ForwardBackward()；

Viterbi()；

Driver：

更新期望；

調(diào)用L-BFGS算法模塊更新權(quán)值向量；

EndLoop

算法1描述了訓(xùn)練過程的總體流程.訓(xùn)練集RDD，SparkContext對(duì)象、訓(xùn)練過迭代最大次數(shù)及收斂值作為過程的輸入；這里以NLP中序列標(biāo)記為例進(jìn)行描述，訓(xùn)練過程開始先將特征模板RDD廣播到各個(gè)工作節(jié)點(diǎn).在各工作節(jié)點(diǎn)上，對(duì)訓(xùn)練集以句子為單位進(jìn)行特征抽取并轉(zhuǎn)化成一個(gè)句子包裝類別實(shí)例，這樣訓(xùn)練集RDD被轉(zhuǎn)化為新的RDD存儲(chǔ)在內(nèi)存中.新的RDD中的每個(gè)實(shí)例對(duì)象包含有m×n大小的圖，其中m和n分布代表句子中含有的字個(gè)數(shù)和可能的輸出標(biāo)記個(gè)數(shù).Driver進(jìn)程根據(jù)抽取的特征集大小初始化對(duì)應(yīng)的權(quán)重?cái)?shù)組.訓(xùn)練迭代過程開始，每個(gè)句子包裝對(duì)象中：1)重置圖中節(jié)點(diǎn)對(duì)象和邊對(duì)象的cost值；2)調(diào)用ForwardBackward函數(shù)(見算法2)計(jì)算圖中每個(gè)節(jié)點(diǎn)的α和β值.前向算法是給定到特定觀測(cè)及該觀測(cè)之前的所有連續(xù)觀測(cè)序列，計(jì)算該觀測(cè)下特定狀態(tài)出現(xiàn)的概率，后向算法是給定到特定觀測(cè)及該觀測(cè)之后的連續(xù)觀測(cè)序列，計(jì)算該觀測(cè)下特定狀態(tài)出現(xiàn)的概率.3)計(jì)算每個(gè)特征的期望改變量，以〈index,incremental_value〉對(duì)的形式臨時(shí)存儲(chǔ)下來，待解碼過程完返回給Driver進(jìn)程；4)解碼過程調(diào)用函數(shù)Viterbi(見算法3)實(shí)現(xiàn).Driver進(jìn)程首先更新期望數(shù)組的值，然后使用L-BFGS算法對(duì)權(quán)值數(shù)組進(jìn)行更新.每次迭代過程結(jié)束，判斷是否滿足終止訓(xùn)練的條件.訓(xùn)練過程結(jié)束后，輸出特征的權(quán)值向量、特征集合和模型的元數(shù)據(jù)信息.

算法2.ForwardBackward實(shí)現(xiàn)過程偽代碼.

Fornum_r=1to句子長(zhǎng)度total_lengthdo

Fornum_c=1to輸出標(biāo)記數(shù)tags_numberdo

計(jì)算圖中第num_r行,第num_c列節(jié)點(diǎn)的前向概率α；

計(jì)算圖中第total_length-num_r行,第num_c列節(jié)點(diǎn)的后向概率β；

計(jì)算當(dāng)前節(jié)點(diǎn)所以輸出邊edge的cost值；

EndFor

計(jì)算規(guī)范化因子Z；

EndFor

算法3. 訓(xùn)練Viterbi實(shí)現(xiàn)過程偽代碼.

Fornum_w=1to句子長(zhǎng)度senten_lengthdo

Fornum_t=1to輸出標(biāo)記數(shù)tags_numberdo

初始化變量best_cost, best_node；

獲取第num_w -th行、第num_t -th 列的節(jié)點(diǎn)，用node_w_t表示；

遍歷節(jié)點(diǎn)node_w_t的所有輸出邊edge；

對(duì)節(jié)點(diǎn)的所有輸入邊：

計(jì)算邊的總代價(jià)cost，當(dāng)前節(jié)點(diǎn)node_w_t的cost及前向連接節(jié)點(diǎn)中最小的cost的節(jié)點(diǎn)；

IFcost>best_cost

更新best_cost;

更新best_node;

ENDIF

更新節(jié)點(diǎn)node_w_t的前驅(qū)指針prev；

更新節(jié)點(diǎn)node_w_t的best_cost；

EndFor

EndFor

Return最優(yōu)的路徑，即輸出標(biāo)記序列.

每輪迭代過程，Driver進(jìn)程與Executor進(jìn)程通信2次：1)廣播特征權(quán)值向量；2)接受各個(gè)Executor返回的期望增量集合和局部的梯度改變量.數(shù)據(jù)的傳遞和接受基于Spark內(nèi)在操作機(jī)制完成.

4.2預(yù)測(cè)階段

Driver進(jìn)程首先從HDFS上讀取訓(xùn)練好的模型數(shù)據(jù)和測(cè)試集并轉(zhuǎn)化為RDD存儲(chǔ)在內(nèi)存中，將模型RDD廣播到各個(gè)工作節(jié)點(diǎn)的Executor進(jìn)程.Executor進(jìn)程執(zhí)行特征抽取操作，重置圖中節(jié)點(diǎn)對(duì)象和邊對(duì)象的cost值，通過ForwardBackward算法完成路徑代價(jià)的計(jì)算，最后使用維特比算法解碼找出最優(yōu)的輸出標(biāo)記序列.

①http://www.sighan.org//bakeoff2005//

算法4. 預(yù)測(cè)過程偽代碼.

Driver:

從HDFS加載訓(xùn)練模型和測(cè)試集，轉(zhuǎn)化為RDD；

將模型廣播到工作節(jié)點(diǎn)；

Executor:

對(duì)測(cè)試集RDD進(jìn)行map操作；

對(duì)每個(gè)包裝對(duì)象：

生成特征；

重置圖中所有node和edge對(duì)象的cost值；

ForwardBackward()；

Viterbi()；

輸出預(yù)測(cè)序列.

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

實(shí)驗(yàn)在我們的集群服務(wù)器上進(jìn)行，共有8臺(tái)配置相同的服務(wù)器節(jié)點(diǎn)組成(配置信息見表1)，其中主節(jié)點(diǎn)1臺(tái)、從節(jié)點(diǎn)7臺(tái). 集群服務(wù)器操作系統(tǒng)為CentOS6.6，安裝有JDK1.8.0，SparkCRF的設(shè)計(jì)和實(shí)現(xiàn)基于Spark-1.5.2.其中，HDFS與Spark集群安裝在同一集群服務(wù)器.實(shí)驗(yàn)使用到的數(shù)據(jù)均已存儲(chǔ)到HDFS中，并且數(shù)據(jù)格式與CRF++的輸入數(shù)據(jù)要求一致.

我們?cè)O(shè)計(jì)了3組實(shí)驗(yàn)，分別從執(zhí)行效率、可擴(kuò)展性和正確性方面對(duì)SparkCRF性能進(jìn)行評(píng)估.由于預(yù)測(cè)階段是一個(gè)使用訓(xùn)練過程生成的模型對(duì)測(cè)試數(shù)據(jù)進(jìn)行解碼的過程，各個(gè)工作節(jié)點(diǎn)在獲得Driver進(jìn)程廣播的數(shù)據(jù)后，整個(gè)過程均在各工作節(jié)點(diǎn)的Executor進(jìn)程中執(zhí)行，Executor間不存在數(shù)據(jù)的傳輸.因此，預(yù)測(cè)階段執(zhí)行時(shí)間與參與工作的節(jié)點(diǎn)個(gè)數(shù)成正線性關(guān)系.因此，高效性和可擴(kuò)展性的驗(yàn)證，我們只對(duì)訓(xùn)練階段進(jìn)行.

5.1高效性

為了驗(yàn)證SparkCRF比單機(jī)CRF算法工具更加高效，我們繼續(xù)選用NLPCC2015公開數(shù)據(jù)集中的train-POS-EN.txt數(shù)據(jù)，將其切分為句子條數(shù)為1 000,2 000,3 000,…,10 000的10份數(shù)據(jù)分別用于訓(xùn)練，單機(jī)程序繼續(xù)使用CRF++.考慮到單機(jī)下的訓(xùn)練過程十分耗時(shí)，我們復(fù)用第2節(jié)的實(shí)驗(yàn)數(shù)據(jù).我們將訓(xùn)練數(shù)據(jù)集分別在集群環(huán)境下使用SparkCRF運(yùn)行，實(shí)驗(yàn)在Spark集群可獲取的最大服務(wù)器資源下進(jìn)行.當(dāng)模板窗口大小為3時(shí)，實(shí)驗(yàn)結(jié)果如圖6(a)所示，窗口大小為5時(shí)，結(jié)果如圖6(b)所示.

Fig. 6　CRF++ vs SparkCRF.圖6　CRF++與SparkCRF對(duì)比結(jié)果

5.2可擴(kuò)展性

我們的實(shí)驗(yàn)在第2屆國(guó)際中文分詞公開數(shù)據(jù)集①上對(duì)SparkCRF進(jìn)行可擴(kuò)展性測(cè)試.公開的數(shù)據(jù)集包含4套用于訓(xùn)練和測(cè)試的數(shù)據(jù)，它們分別由微軟亞洲研究院(MicrosoftResearchAsia,MSR)、香港城市大學(xué)(CityUniversityofHongkong,CityU)、臺(tái)灣中央研究院(AcademiaSinica,AS)和北京大學(xué)(PekingUniversity,PKU)提供.根據(jù)我們的了解，這份數(shù)據(jù)集是目前可免費(fèi)獲取到的最大的中文分詞數(shù)據(jù)集，由于其在數(shù)據(jù)格式與SparkCRF對(duì)輸入數(shù)據(jù)的格式要求不一致，因此我們開發(fā)一個(gè)數(shù)據(jù)格式轉(zhuǎn)換程序?qū)ζ溥M(jìn)行預(yù)處理.訓(xùn)練數(shù)據(jù)的詳細(xì)統(tǒng)計(jì)信息見表2所示，其中WT代表WordTypes，SN代表SentencesNumber，PFS代表ProcessedFileSize.

實(shí)驗(yàn)在僅處理器核數(shù)為可變因素、其他所有因素均不變的條件下進(jìn)行.我們將SparkCRF的工作核數(shù)分別設(shè)定為50,70,90,110,130和150來驗(yàn)證其可擴(kuò)展性能.對(duì)每個(gè)訓(xùn)練數(shù)據(jù)，分別在指定的每種處理器核數(shù)下，對(duì)同一實(shí)驗(yàn)重復(fù)進(jìn)行5次，記錄下運(yùn)行時(shí)間，最后對(duì)這5次結(jié)果取平均值作為執(zhí)行時(shí)間.實(shí)驗(yàn)結(jié)果如圖7所示.

Table2StatisticalInformationoftheSecondInternationalChineseWordSegmentationBakeoff

表2　第2屆國(guó)際中文分詞數(shù)據(jù)集統(tǒng)計(jì)信息

Fig. 7　Relationship between core number and execution time on different datasets.圖7　不同數(shù)據(jù)集上核數(shù)與執(zhí)行時(shí)間的關(guān)系

圖7(a)(b)(c)(d)分別描述了在訓(xùn)練數(shù)據(jù)集MSR,CityU,AS和PKU上的實(shí)驗(yàn)結(jié)果.我們從圖7中發(fā)現(xiàn)：1)隨著工作核數(shù)的增加，不同數(shù)據(jù)集上的訓(xùn)練時(shí)間均在減少；2)不同數(shù)據(jù)集間的表現(xiàn)雖有一定的差別，但總體上工作核數(shù)與執(zhí)行時(shí)間均呈現(xiàn)出了線性的關(guān)系.

5.3正確性

為了檢驗(yàn)SparkCRF的正確性，我們選擇與CRF++進(jìn)行實(shí)驗(yàn)對(duì)比.實(shí)驗(yàn)訓(xùn)練數(shù)據(jù)集使用NLPCC2015公開數(shù)據(jù)集中的train-SEG.txt，預(yù)測(cè)數(shù)據(jù)集為對(duì)應(yīng)的test-Gold-SEG.txt.通過2組實(shí)驗(yàn)進(jìn)行驗(yàn)證，特征模板窗口大小分別設(shè)置為3和5，訓(xùn)練集包含的句子數(shù)分別為1 000,2 000,3 000,…,10 000.

按照實(shí)驗(yàn)的設(shè)計(jì)，1)分別使用CRF++和SparkCRF在訓(xùn)練集集合上進(jìn)行訓(xùn)練，分別生成的模型；2)使用生成的模型分別用于對(duì)標(biāo)準(zhǔn)測(cè)試集進(jìn)行預(yù)測(cè)；3)統(tǒng)計(jì)預(yù)測(cè)的準(zhǔn)確率.圖8(a)展示了窗口大小為3時(shí)的結(jié)果，圖8(b)為窗口大小為5時(shí)的結(jié)果.

Fig. 8　Relationship between sentence number of corpus and accuracy.圖8　訓(xùn)練集句子個(gè)數(shù)與預(yù)測(cè)正確率的關(guān)系

實(shí)驗(yàn)結(jié)果表明：1)2種窗口大小下，CRF++和SparkCRF預(yù)測(cè)的準(zhǔn)確率均隨著訓(xùn)練規(guī)模的增大而提高；2)不同窗口下，二者在相同訓(xùn)練集上的準(zhǔn)確率稍有差別.窗口為3時(shí)，SparkCRF略低于CRF++的準(zhǔn)確率，窗口為5時(shí)，SparkCRF預(yù)測(cè)的準(zhǔn)確率稍高于CRF++，但總體上二者的預(yù)測(cè)準(zhǔn)確率基本相同；3)窗口為3時(shí)，當(dāng)訓(xùn)練集句子增加到8 000后，此時(shí)CRF++和SparkCRF的準(zhǔn)確率分別為94.12%和94.14%，增加訓(xùn)練集包含的句子數(shù)對(duì)該測(cè)試集預(yù)測(cè)準(zhǔn)確率的提高不明顯；窗口為5時(shí)，當(dāng)訓(xùn)練集增加到9 000條句子時(shí)，CRF++SparkCRF對(duì)應(yīng)的準(zhǔn)確率為93.73%94.04%，10 000條句子時(shí)對(duì)應(yīng)的準(zhǔn)確率為94.07%94.33%.通過分析可知，模型中包含的該測(cè)試集所需特征的比重是影響預(yù)測(cè)準(zhǔn)確率的根本因素.

6　總　　結(jié)

針對(duì)傳統(tǒng)的運(yùn)行在單節(jié)點(diǎn)上的條件隨機(jī)場(chǎng)在處理大規(guī)模文本時(shí)，面臨一系列挑戰(zhàn).本文采用“分而治之”的思想，基于ApacheSpark的大數(shù)據(jù)處理框架設(shè)計(jì)并實(shí)現(xiàn)了運(yùn)行在集群環(huán)境下的分布式CRFs.通過對(duì)文本分析任務(wù)進(jìn)行的實(shí)驗(yàn)，證明了SparkCRF具有高效的計(jì)算能力和較好的擴(kuò)展性，并且具有與傳統(tǒng)的單節(jié)點(diǎn)CRF++相同水平的準(zhǔn)確率.

在理論上，SparkCRF能夠處理大規(guī)模的數(shù)據(jù)集.由于可獲得標(biāo)準(zhǔn)訓(xùn)練集有限，我們僅對(duì)幾十兆級(jí)大小的數(shù)據(jù)集進(jìn)行了測(cè)試.因此，還有待進(jìn)一步在大規(guī)模數(shù)據(jù)集上對(duì)SparkCRF驗(yàn)證；在應(yīng)用方面，利用SparkCRF工具提升文本處理的效果也是一個(gè)有待嘗試的工作.例如，與知識(shí)表示[20]工作相結(jié)合，提升領(lǐng)域知識(shí)的抽取效果.以上兩個(gè)方面也是我們未來的工作重點(diǎn).

[1]LaffertyJ,McCallumA,PereiraFCN.Conditionalrandomfields:Probabilisticmodelsforsegmentingandlabelingsequencedata[C] //ProcoftheIntConfonMachineLearning.Francisco,CA:MorganKaufmann, 2001: 282-289

[2]WangYuanzhuo,JiaYantao,LiuDawei,etal.OpenWebknowledgeaidedinformationsearchanddatamining[J].JournalofComputerResearchandDevelopment, 2015, 52(2): 456-474 (inChinese)

(王元卓, 賈巖濤, 劉大偉, 等. 基于開放網(wǎng)絡(luò)知識(shí)的信息檢索與數(shù)據(jù)挖掘[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 456-474

[3]WangYuanzhuo,JinXiaolong,ChengXueqi.Networkbigdata:Presentandfuture[J].ChineseJournalofComputers, 2013, 36(6): 1125-1138 (inChinese)

(王元卓, 靳小龍, 程學(xué)旗. 網(wǎng)絡(luò)大數(shù)據(jù):現(xiàn)狀與挑戰(zhàn)[J].計(jì)算機(jī)學(xué)報(bào), 2013, 36(6): 1125-1138)

[4]ChengXueqi,JinXiaolong,WangYuanzhuo,etal.Surveyonbigdatasystemandanalytictechnology[J].JournalofSoftware, 2014, 25 (9): 1240-1252 (inChinese)

(程學(xué)旗, 靳小龍, 王元卓, 等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J]. 軟件學(xué)報(bào), 2014, 25(9): 1889-1908.)

[5]DeanJ,GhemawatS.MapReduce:Simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM, 2008, 51(1): 107-113

[6]ToshniwalA,TanejaS,ShuklaA,etal.Storm@Twitter[C] //Procofthe2014ACMSIGMODIntConfonManagementofData.NewYork:ACM, 2014: 147-156

[7]ZahariaM,ChowdhuryM,FranklinMJ,etal.Spark:Clustercomputingwithworkingsets[C] //Procofthe2ndUSENIXWorkshoponHotTopicsinCloudComputing.Berkeley,CA:USENIXAssociation, 2010: 10-10

[8]MelnikS,GubarevA,LongJJ,etal.Dremel:Interactiveanalysisofweb-scaledatasets[J].ProceedingsoftheVLDBEndowment, 2010, 3(1//2): 330-339

[9]MalewiczG,AusternMH,BikAJC,etal.Pregel:Asystemforlarge-scalegraphprocessing[C] //Procofthe2010ACMSIGMODIntConfonManagementofData.NewYork:ACM, 2010: 135-146

[10]ShaoBin,WangHaixun,LiYatao.Trinity:Adistributedgraphengineonamemorycloud[C] //Procofthe2013ACMSIGMODIntConfonManagementofData.NewYork:ACM, 2013: 505-516

[11]PhanHX,NguyenML,HoriguchiS,etal.ParalleltrainingofCRFs:Apracticalapproachtobuildlarge-scalepredictionmodelsforsequencedata[C] //ProcofIntWorkshoponParallelDataMining.Berlin:Springer, 51-63

[12]BradleyJK.Learninglarge-scaleconditionalrandomfields[D].Pittsburgh:CarnegieMellonUniversity, 2013

[13]LavergneT,CappéO,YvonF.PracticalverylargescaleCRFs[C] //Procofthe48thAnnualMeetingoftheAssociationforComputationalLinguistics.Stroudsburg,PA:ACL, 2010: 504-513

[14]ShvachkoK,KuangH,RadiaS,etal.Thehadoopdistributedfilesystem[C] //Procofthe2010IEEE26thSymponMassStorageSystemsandTechnologies.Piscataway,NJ:IEEE, 2010: 1-10

[15]ZhengShuai,JayasumanaS,Romera-ParedesB,etal.Conditionalrandomfieldsasrecurrentneuralnetworks[C] //ProcoftheIEEEIntConfonComputerVision.Piscataway,NJ:IEEE, 2015: 1529-1537

[16]LiuTao,LeiLin,ChenLuo,etal.AparalleltrainingresearchofChinesewordspart-of-speechtaggingCRFmodelbasedonMapReduce[J].ActaScientiarumNaturaliumUniversitatisPekinensis, 2013 (1): 147-152 (inChinese)

(劉滔, 雷霖, 陳犖, 等. 基于MapReduce的中文詞性標(biāo)注CRF模型并行化訓(xùn)練研究[J]. 北京大學(xué)學(xué)報(bào): 自然科學(xué)版, 2013 (1): 147-152)

[17]WangZhaoyuan,WangHongjie,XingHuanlai,etal.AntcolonyoptimizationalgorithmbasedonSpark[J].JournalofComputerApplication, 2015, 35(10): 2777-2780, 2797(王詔遠(yuǎn), 王宏杰, 邢煥來, 等. 基于Spark的蟻群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(10): 2777-2780, 2797)

[18]QiuHongjian,GuRong,YuanChunfeng,etal.YAFIM:AparallelfrequentitemsetminingalgorithmwithSpark[C] //Procofthe2014IEEEIntConfonParallel&DistributedProcessingSympWorkshops.Piscataway,NJ:IEEE, 2014: 1664-1671

[19]GuRong,WangShanyang,WangFangfang,etal.Cichlid:EfficientlargescaleRDFS//OWLreasoningwithSpark[C] //Procofthe2015IEEEIntConfonParallelandDistributedProcessingSymposium.Piscataway,NJ:IEEE, 2015: 700-709

[20]JiaYantao,WangYuanzhuo,LinHailun,etal.Locallyadaptivetranslationforknowledgegraphembedding[C]

//Procofthe30thAAAI’6.PaloAlto,CA:AAAI, 2016: 992-998

ZhuJizhao,bornin1986.PhDcandidate.Hismainresearchinterestsincludeopenknowledgenetwork,representationlearningandparallelcomputing.

JiaYantao,bornin1983.PhD,assistantprofessor.Hismainresearchinterestsincludeopenknowledgenetwork,socialcomputingandcombinatorialalgorithm.

XuJun,bornin1979.Professor,PhDsupervisor.Hismainresearchinterestsincludeinformationretrieval,machinelearningandbigdataanalysis.

QiaoJianzhong,bornin1964.Professor,PhDsupervisor.Hismainresearchinterestsincludeoperationsystem,parallelanddistributedcomputing.

WangYuanzhuo,bornin1978.PhD,associateprofessor.IEEEmemberandseniormemberofChinaComputerFederation.Hismainresearchinterestsincludesocialcomputing,openknowledgenetwork,networksecurityanalysis,stochasticgamemodel,etc.

ChengXueqi,bornin1971.Professor,PhDsupervisor.Hismainresearchinterestsincludenetworkscience,Websearch&datamining.

SparkCRF:AParallelImplementationofCRFsAlgorithmwithSpark

ZhuJizhao1,2,JiaYantao2,XuJun2,QiaoJianzhong1,WangYuanzhuo2,andChengXueqi2

1(College of Computer Science and Engineering, Northeastern University, Shenyang 110819)2(Key Laboratory of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)

Conditionrandomfieldshasbeensuccessfullyappliedtovariousapplicationsintextanalysis,suchassequencelabeling,Chinesewordssegmentation,namedentityrecognition,andrelationextractioninnaturelanguageprocessing.ThetraditionalCRFstoolsinsingle-nodecomputermeetmanychallengeswhendealingwithlarge-scaletexts.Foronething,thepersonalcomputerexperiencestheperformancebottleneck;Foranother,theserverfailstotackletheanalysisefficiently.Andupgradinghardwareoftheservertopromotethecapabilityofcomputingisnotalwaysfeasibleduetothecostconstrains.Totackletheseproblems,inlightoftheideaof“divideandconquer”,wedesignandimplementSparkCRF,whichisakindofdistributedCRFsrunningonclusterenvironmentbasedonApacheSpark.WeperformthreeexperimentsusingNLPCC2015andthe2ndInternationalChineseWordSegmentationBakeoffdatasets,toevaluateSparkCRFfromtheaspectsofperformance,scalabilityandaccuracy.Resultsshowthat: 1)comparedwithCRF++,SparkCRFrunsalmost4timesfasteronourclusterinsequencelabelingtask; 2)ithasgoodscalabilitybyadjustingthenumberofworkingcores; 3)furthermore,SparkCRFhascomparableaccuracytothestate-of-the-artCRFtools,suchasCRF++inthetaskoftextanalysis.

bigdata;machinelearning;distributedcomputing;Spark;conditionrandomfields(CRFs)

喬建忠(qiaojianzhong@mail.neu.edu.cn)

2016-03-21；

2016-06-08

國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2014CB340405，2013CB329602)；國(guó)家重點(diǎn)研發(fā)計(jì)劃基金項(xiàng)目(2016YFB1000902);國(guó)家自然科學(xué)基金項(xiàng)目(61173008，61232010，61272177，61303244，61402442)；北京市自然科學(xué)基金項(xiàng)目(4154086)

TP181

ThisworkwassupportedbytheNationalBasicResearchProgramofChina(973Program) (2014CB340405, 2013CB329602),NationlalKeyResearchandDevelopmentProgramofChina(2016YFB1000902),theNationalNaturalScienceFoundationofChina(61173008, 61232010, 61272177, 61303244, 61402442),andtheNaturalScienceFoundationofBeijing(4154086).