蔣志鵬 關(guān)毅

電子病歷是醫(yī)務(wù)人員在醫(yī)療活動過程中使用醫(yī)療機構(gòu)信息系統(tǒng)生成的文字、符號、圖表、圖形、數(shù)據(jù)、影像等數(shù)字化信息,并能實現(xiàn)存儲、管理、傳輸和重現(xiàn)的醫(yī)療記錄[1?2].電子病歷是一種極其寶貴的知識資源,通過對電子病歷進行自動分析,可以為用戶健康知識獲取提供有力支持.近幾年,電子病歷的知識獲取成為研究的熱點問題[3?5],其獲取過程一般分為語言分析和信息抽取兩個階段進行,詞法分析和句法分析是主要的語言分析手段,能夠為信息抽取提供必要的條件.例如,電子病歷的句子可能包含多種藥物信息及不同的用藥說明.傳統(tǒng)的規(guī)則表示僅在藥名抽取上具有較高精度,而用藥頻率、計量等重要信息的抽取需要結(jié)合上下文環(huán)境,是規(guī)則表示無法處理的.句法分析技術(shù)通過對句子進行結(jié)構(gòu)化處理,能夠解析復(fù)雜的上下文環(huán)境,為信息抽取提供豐富的上下文信息,已經(jīng)成為構(gòu)建高精度信息抽取系統(tǒng)的重要組成部分.

中文電子病歷(Chinese electronic medical records,CEMR)文本不同于一般的限定領(lǐng)域文本.語料構(gòu)建方面,CEMR的標注工作要求兼顧醫(yī)學(xué)和語言學(xué)的相關(guān)知識,增加了標注者的學(xué)習(xí)成本,整個標注過程更加費時費力.文本差異方面,除了詞匯層面的差異外,CEMR文本特有的書寫方式加劇了與開放領(lǐng)域的文本差異.具體表現(xiàn)為,從文本構(gòu)造上看,CEMR是結(jié)構(gòu)化數(shù)據(jù)和自由文本的結(jié)合,自然語言處理的對象通常指的是自由文本.根據(jù)CEMR詞性標注準確率與未登錄詞率的相關(guān)性分析[6],CEMR的自由文本可以分為敘述部分和羅列部分,敘述部分多以長句的形式描述癥狀、檢查等信息,例如診療計劃、診斷依據(jù)、病例特點、主訴等,羅列部分多為醫(yī)學(xué)術(shù)語及其修飾語的簡單羅列,例如臨床初步診斷、臨床確定診斷、門診收治診斷、治療效果等.其中,羅列部分充斥著開放領(lǐng)域語料鮮有的醫(yī)學(xué)術(shù)語,例如“腦梗死”在賓州中文樹庫(Penn Chinese treebank,PCTB)中從未出現(xiàn)過,使得該部分的句法分析難以利用PCTB中學(xué)習(xí)的知識.CEMR文本重復(fù)度高的特點導(dǎo)致敘述部分呈現(xiàn)強模式化現(xiàn)象,例如“伸舌”、“示齒”這類縮略詞構(gòu)成的動賓短語在病例特點中頻繁出現(xiàn),該類短文本多以標點符號分隔描述病情,在PCTB中同樣較少使用.CEMR自由文本的這兩部分特點使得直接應(yīng)用PCTB訓(xùn)練的句法分析模型性能下降更為嚴重,Berkeley parser[7]與Stanford parser[8]相比,中文開放領(lǐng)域的最好結(jié)果下降了30%左右.

本文將CEMR自由文本中重復(fù)出現(xiàn)的模式形式化為樹片段,樹片段主要用于句法樹重排序和面向數(shù)據(jù)句法分析(Data-oriented parsing,DOP).句法樹重排序一般分為兩步:1)由基本的句法分析器為每個句子產(chǎn)生一組候選句法樹,候選句法樹的初始概率為最初排序的依據(jù);2)根據(jù)句法樹的額外的結(jié)構(gòu)特征訓(xùn)練重排序模型,對這組候選句法樹重新排序,通常使用樹片段作為重排序的額外特征.盡管重排序模型對句法分析精度有較大提升,但是時空復(fù)雜度較高的缺點限制了其實際應(yīng)用.DOP技術(shù)首先由Scha在1990年提出,之后由Bod逐步發(fā)展,具體表達了如下假設(shè):人類對語言的領(lǐng)悟和創(chuàng)造依賴于以往具體的語言經(jīng)驗,而不是依賴于抽象的語法規(guī)則[9].模型首先預(yù)設(shè)了一個具有帶標短語結(jié)構(gòu)樹標注的語料庫,然后從這個語料庫中抽取所有任意大小規(guī)模和復(fù)雜結(jié)構(gòu)的片段.其次,通過對語料庫中片段的組合操作來實現(xiàn)新輸入的分析,然后考慮輸入的所有派生結(jié)果的概率總和的大小來選擇最有可能性的分析結(jié)果[10].

在前期工作中,我們對CEMR語料進行了詞法統(tǒng)計分析[6],其中逐點互信息的結(jié)果說明CEMR相比中文開放語料和英文EMR模式化程度更強,這是由于CEMR的編寫具有更強的目的性,力求表述清晰、簡潔,導(dǎo)致重復(fù)使用相似的句法結(jié)構(gòu),形成模式化的表述.同時,CEMR中包含不同的部分,每個部分意圖不同,重復(fù)使用的短語結(jié)構(gòu)也不盡相同,這種模式化表述一般與陳述性語句混合使用.以首次病程記錄為例,包括主訴、既往史、主觀癥狀、客觀檢查、評估和診斷、診療計劃六個部分,其中頻繁出現(xiàn)的重復(fù)結(jié)構(gòu)如表1所示,而傳統(tǒng)的PCFG文法將句法樹層數(shù)限制為2,難以直接表示這些模式,例如“伴心率失常室早”、“伴心率失常房顫”、“伴心動過速”會形成兩類重復(fù)模式,即“伴心率失常+疾病名”和“伴+疾病組”,這兩類模式均不屬于PCFG文法.DOP希望抽取所有可能的樹片段(不限制層數(shù)),能夠更加直觀、形象地表現(xiàn)CEMR中的模式.我們以樹片段替換的方式對初始的句法分析結(jié)果進行糾錯,類似于引入了句法樹重排序中的結(jié)構(gòu)特征,但相比句法樹重排序按模板抽取結(jié)構(gòu)特征,DOP的優(yōu)勢在于不限制樹片段的形式,能夠保證其多樣性,并且在增加新語料時不需要重新訓(xùn)練模型.盡管DOP的文法歸納過程不需要訓(xùn)練模型,但是樹片段的數(shù)量隨樹庫規(guī)模呈指數(shù)級增長,抽取樹庫中所有可能的樹片段難以實現(xiàn).

層次句法分析是一種快速的完全句法分析方法,在前期工作中,我們改進了層次句法分析模型[11],并標注了小規(guī)模CEMR句法樹庫[12?13],本文希望充分利用CEMR模式化強的特點,進一步提升層次句法分析模型的精度.本文的工作屬于后處理融合,基于改進的樹片段的抽取算法,將DOP中樹片段的選擇和替換操作融入層次句法分析過程中,最終在CEMR上句法分析的F1值超過了目前最優(yōu)的Berkeley parser和Stanford parser.模型整體架構(gòu)如圖1所示.

表1 重復(fù)模式樣例Table 1 Pattern samples repeated

圖2為面向數(shù)據(jù)句法分析與層次句法分析的融合示例,輸入為經(jīng)過詞性標注的CEMR句子“對光反射存在,雙眼運動自如,無面舌癱”.該句子依次經(jīng)過詞匯詞性混合匹配、初選、篩選和組合過程,獲得了一個最優(yōu)的樹片段集合,最終通過樹片段替換的方式改進了層次句法分析結(jié)果.圖中虛線框部分為該實例中兩個有效的替換.

1 相關(guān)工作

樹核方法一般用于量化兩棵句法樹的相似程度,并不能明確給出這兩棵句法樹的共有結(jié)構(gòu),Sangati等[14]在2010年首次將樹核應(yīng)用到樹片段抽取中,Sangati將樹片段分為標準片段和局部片段,抽取時對樹庫中所有樹結(jié)點進行兩兩比較,并提出基于樹核的局部片段抽取算法,該算法不只計算公共結(jié)點數(shù)量,還保留了重復(fù)出現(xiàn)的最大公共樹片段.盡管Sangati能夠從樹庫中抽取有效的樹片段,但是使用二次樹核(Quadratic tree kernel,QTK)在樹片段抽取時效率不高.與Sangati相類似,Moschitti[15]同樣對樹片段進行了劃分,并提出了基于快速樹核(Fast tree kernel,FTK)的樹結(jié)點匹配算法,該算法的效率要高于Sangati,但是僅保留了樹庫的公共結(jié)點集而不是樹片段.van Cranenburgh[16]將Moschitti的快速樹核算法改進為矩陣形式抽取樹片段,算法時間復(fù)雜度降為線性平均時間,但整個抽取過程只適用于二叉樹,并且只抽取樹庫中的局部片段.本文的樹片段抽取以Sangati的工作為基礎(chǔ),借鑒動態(tài)規(guī)劃思想改進了標準樹片段抽取算法,并使用Moschitti的快速樹核算法替換Sangati的二次樹核算法,提高了整個算法的執(zhí)行效率.

中文方面DOP相關(guān)研究較少,早期張 杰等[10]提出基于DOP框架的中文句法分析方法.整個分析過程中,句子需要依次經(jīng)過詞匯層與詞性層的初選,再從樹片段庫中獲得與句子相匹配的片段組合形式,利用Kullback-Leibler距離函數(shù)評估句子與初選結(jié)果的相似度,分析結(jié)果為相似度大于閾值或相似度最高的片段組合.本文的樹片段處理過程相當于在張 杰工作的基礎(chǔ)上,提出了一套適用于CEMR的樹片段選擇和替換方法.由于我們的目的是通過樹片段替換融合層次句法分析模型,所以沒有保留張 杰的組合分析過程.

層次句法分析是一種高效的完全句法分析方法,但是逐層組塊分析導(dǎo)致錯誤累積問題嚴重,在前期工作中,我們提出了一種簡單可行的錯誤預(yù)判及協(xié)同糾錯算法[11],每層組塊分析時跟蹤預(yù)判錯誤標注結(jié)果進入下一層,利用兩層預(yù)測分數(shù)相結(jié)合的方式協(xié)同糾錯.實驗結(jié)果表明,加入糾錯方法后,層次句法分析在保證解析速度的同時,獲得了與主流中文句法分析器相當?shù)慕馕鼍?近幾年,由于單一模型的解析結(jié)果仍然存在局限性,模型融合成為提高現(xiàn)有句法分析水平的主要途徑.模型融合一般指將不同句法分析器的結(jié)果融合成一個最終結(jié)果,常見的融合方式包括將不同結(jié)果雜合成為一個結(jié)果[17?18],或按照某些標準從多個結(jié)果中選擇一個最優(yōu)的結(jié)果[19].

2 標點符號分割與糾錯算法

圖1 融合模型框架Fig.1 The framework of integrated model

圖2 面向數(shù)據(jù)句法分析與層次句法分析融合示例Fig.2 The sample integrating DOP and hierarchical parsing

通過對CEMR標注語料進行統(tǒng)計分析[6],我們發(fā)現(xiàn)標點符號在CEMR中所占比例高達21.69%,僅次于名詞位居第二位,并且高于開放領(lǐng)域文本6.4%之多.由于層次句法分析框架是自底向上逐層序列化標注,CEMR標點符號的頻繁使用使得下列問題更為突出:1)句法樹中高層標點符號成分較難確定;2)并列結(jié)構(gòu)中標點符號成分難確定;3)逐層標注的錯誤累積導(dǎo)致標點對的內(nèi)容無法成為單棵句法樹.CEMR中最常見的標點對為雙引號和圓括號,其內(nèi)容經(jīng)常被CRF模型分割成多棵句法樹,后續(xù)部分提及的標點對也默認為雙引號和圓括號.

CEMR中標點符號的使用同樣有較強規(guī)律性,例如,經(jīng)常出現(xiàn)在高層句法樹中的標點符號多用于連接并列句法結(jié)構(gòu).為緩解上述問題,一方面,本文圍繞標點符號設(shè)計了辨識度更高的特征,形成上下文詞典,以詞典糾錯的方式改進標點符號的標注效果.另一方面,使用標點對分割句子,優(yōu)先解析標點對的內(nèi)部成分,采用分割組合的方式進行句法分析.

結(jié)合層次句法分析模型[13]在調(diào)試語料上的錯誤分析結(jié)果,我們設(shè)計了上下文詞典對標點符號進行糾錯,關(guān)鍵詞為標點符號,詞典項如表2所示.其中,第1行為通用項?father,lfather,rfather?,father表示父結(jié)點,lfather表示父結(jié)點的左兄弟結(jié)點,rfather為父結(jié)點的右兄弟結(jié)點.第2行aword為相鄰詞,相鄰詞的選取與Collins的頭詞類似,目的是對子樹邊界位置的標點符號進行消歧,如果父結(jié)點是NP,則aword為左相鄰詞,否則aword為右相鄰詞,當 aword為空時?lgfather,rgfather,lbword,rbword?生效,lgfather和rgfather分別為祖先結(jié)點的左兄弟和右兄弟結(jié)點,lbword為lfather的最右子結(jié)點,rbword為rfather的最左子結(jié)點.第3行和第4行的詞典項與句法樹高度相關(guān),即句子邊界有助于高層標點符號糾錯,固定搭配有助于低層標點符號糾錯.當標點符號所在層數(shù)大于3時,?lbbegin,rbend?判斷當前位置是否為句首或句尾,若不是則直接比對aword項.

表2 上下文詞典項概括Table 2 Summary of elements of context dictionary

標點符號的上下文詞典糾錯算法能夠與多層協(xié)同糾錯算法[11]很好地配合使用.當歧義項為標點符號時,優(yōu)先檢索上下文詞典,選擇匹配成功的候選結(jié)果作為最優(yōu)解,否則進入多層協(xié)同糾錯算法消歧.在檢索上下文詞典時,為了減少詞典中人工錯誤帶來的干擾,我們規(guī)定只有當前條件對應(yīng)的元組完全匹配時,才算匹配成功.

由于閉合的標點對必然會成為一個句法樹,所以省去了訓(xùn)練模型識別獨立語塊的過程,在進行句法分析時,如果存在標點對,則優(yōu)先解析標點對的內(nèi)容,再將標點對的句法樹與其余部分重組成新的輸入,進行新一輪解析.引入標點符號分割和糾錯算法的層次句法分析流程如圖3所示,其中“CRF序列化標注”和“多層協(xié)同糾錯”是前期構(gòu)建的基礎(chǔ)模型CLP[11].

3 樹片段抽取

由于樹片段不限制層數(shù)和結(jié)構(gòu),導(dǎo)致其數(shù)量隨語料規(guī)模呈指數(shù)級增長,抽取時間遠長于統(tǒng)計機器學(xué)習(xí)模型的訓(xùn)練時間,當需要從更大規(guī)模語料中抽取樹片段時,抽取時間將成為其實際應(yīng)用的瓶頸問題,所以在樹片段抽取上的改進工作主要圍繞抽取效率展開.

圖3 引入標點符號分割和糾錯的句法分析流程Fig.3 The parsing process with segmentation and error correction for punctuation

3.1 樹片段相關(guān)定義

參照Sangati等[14]對樹片段的劃分方式,首先給出標準樹片段和局部樹片段的相關(guān)定義,然后為兩類樹片段分別設(shè)計算法抽取公共樹片段,形成兩個樹片段庫.

定義 1(標準樹片段).標準樹片段stf是句法樹T的連通子圖,并且stf中任意結(jié)點的子結(jié)點或為空,或與T中對應(yīng)結(jié)點的子結(jié)點相同.

定義 2(局部樹片段).局部樹片段ptf是句法樹T的任意連通子圖.

定義 3(公共樹片段).公共樹片段ctf是在句法樹庫中至少出現(xiàn)兩次的標準樹片段或局部樹片段.

定義4(公共葉結(jié)點).公共葉結(jié)點ct屬于公共樹片段ctf,并且ct的子結(jié)點或為空,或不屬于ctf.

定義5(公共非葉結(jié)點).公共非葉結(jié)點cnt的子結(jié)點不為空,并且cnt及其子結(jié)點全部屬于公共樹片段ctf.

從上述定義可以看出,標準樹片段相當于局部樹片段的特殊形式,所以其抽取和匹配的耗時更少,為了對比兩類樹片段對模型融合的貢獻,本文分別抽取了兩個樹片段庫.公共樹片段可以較好地表現(xiàn)CEMR中重復(fù)出現(xiàn)的模式,下文提及的標準樹片段和局部樹片段都默認為公共樹片段.

以CEMR中的句法樹為例,圖4(a)為CEMR句法樹,圖4(b)和圖4(c)分別表示從該句法樹中抽取的部分標準樹片段和局部樹片段.共現(xiàn)模式是CEMR中的高頻模式,圖4中實線框內(nèi)的標準樹片段能夠體現(xiàn)“心率失?！焙汀笆以纭边@兩個病癥的共現(xiàn)模式,而通過將“室早”泛化為名詞詞性,形成虛線框內(nèi)的局部樹片段,則能夠表現(xiàn)“心率失常”與其他病癥的共現(xiàn)模式,例如常見的“心動過速”、“房顫”等.由此可見,CEMR中的共現(xiàn)模式與樹片段能夠很好地吻合,所以本文將其形式化為樹片段,用于改善句法分析模型在CEMR上的解析效果.

3.2 標準樹片段抽取

Sangati等[14]抽取標準樹片段的過程由兩部分組成,第1部分遍歷句法樹庫中每一對樹結(jié)點,算法時間復(fù)雜度為O(n2m2),其中n為句法樹的數(shù)量,m為單棵句法樹的最大結(jié)點數(shù),第2部分抽取父子結(jié)點均相同的片段,最壞情況下,算法時間復(fù)雜度為O(m2),最終算法時間復(fù)雜度為O(n2m4).為避免重復(fù)比對問題,我們利用動態(tài)規(guī)劃思想改進了Sangati的抽取算法,如算法1所示.

圖4 句法樹及其片段樣例Fig.4 Examples of a parsing tree and its fragments

算法1.標準樹片段抽取算法

不同于Sangati的抽取算法,本文的標準樹片段抽取算法圍繞公共非葉結(jié)點展開,其中,SIZE函數(shù)用于計算樹庫中句法樹的數(shù)量,CHILD-SIZE函數(shù)返回子結(jié)點數(shù)目,算法第1～5行是樹庫結(jié)點對的遍歷過程,第6行的變量visited用于保存已訪問的公共非葉結(jié)點對.在調(diào)用EX-TREE-STF函數(shù)抽取標準樹片段之前需要查找visited,visited中存在的公共非葉結(jié)點對不再遍歷.算法第11～26行用于識別公共非葉結(jié)點,具體地,在遍歷結(jié)點對時,當兩個結(jié)點相同并且子結(jié)點數(shù)也相同時,遞歸調(diào)用EX-TREE-STF算法遍歷所有子結(jié)點,如果所有子結(jié)點相同,則該結(jié)點對為公共非葉結(jié)點對;否則,當兩個結(jié)點相同,但其子結(jié)點不同或為空時,該結(jié)點對則為公共葉結(jié)點對.由于不需要重復(fù)遍歷公共非葉結(jié)點,使得EX-TREE-STF算法時間復(fù)雜度降至O(d),d為單個結(jié)點的最大子結(jié)點數(shù),整個算法的時間復(fù)雜度降為O(n2m2d).

3.3 局部樹片段抽取

與標準樹片段抽取算法類似,Sangati等[14]在抽取局部樹片段時同樣需要先遍歷句法樹庫中每一對樹結(jié)點,再抽取局部樹片段.不同之處在于,兩個樹結(jié)點可能共享多個公共子結(jié)點序列,形成多種公共局部樹片段的組合.為抽取所有可能的公共局部樹片段,Sangati等提出了基于二次樹核的結(jié)點映射算法,該算法類似于最長公共子序列查找,需要遍歷每個子結(jié)點對,其時間復(fù)雜度為O(d4),d為單個結(jié)點的最大子結(jié)點數(shù),整個算法的時間復(fù)雜度為O(n2m2d4).

事實上,在抽取公共樹片段時,如果兩個父結(jié)點的產(chǎn)生式不同,其子結(jié)點沒有必要再進行比較.Moschitti[15]提出了基于快速樹核的結(jié)點映射算法,只考慮父結(jié)點產(chǎn)生式相同的結(jié)點匹配情況.受該思想啟發(fā),本文利用Moschitti的快速樹核替換二次樹核算法,獲取樹結(jié)點映射集,算法2是改進后的局部樹片段抽取算法.

算法2.局部樹片段抽取算法

算法2中,SORT函數(shù)將結(jié)點的產(chǎn)生式按字母順序排序,POP函數(shù)返回有序表中首個結(jié)點并將其彈出,PROD函數(shù)返回結(jié)點所在的整個產(chǎn)生式,NEXT函數(shù)返回有序表中當前結(jié)點的下一個結(jié)點.第1～3行為樹庫的遍歷過程,該過程與算法1相同.第4～17行為基于快速樹核的結(jié)點映射算法,該算法首先對樹的結(jié)點按字母順序排序,然后逐個比較產(chǎn)生式相同的結(jié)點,對所有公共結(jié)點進行標記,與標準樹片段抽取不同,這里不需要區(qū)分公共葉結(jié)點和非葉結(jié)點.第18行遞歸調(diào)用EX-TREE-PTF算法獲取ni和nj的公共局部樹片段集合,該算法與Sangati等[14]提出的算法3相同,功能是對結(jié)點映射組maps進行合并,最終加入到整個局部樹片段集合中.

由于產(chǎn)生式排序過程在進行結(jié)點映射之前僅執(zhí)行一次,時間復(fù)雜度為O(mlogm),結(jié)點映射過程最壞情況下執(zhí)行m2次,而EX-TREE-PTF算法對整棵樹也只需遍歷一次,所以改進后的局部樹片段抽取算法時間復(fù)雜度為O(n2m4).

4 DOP與層次句法分析的融合模型

前文將CEMR重復(fù)出現(xiàn)的模式形式化為樹片段,并分別抽取標準樹片段和局部樹片段,形成了兩個樹片段庫.與樹片段關(guān)聯(lián)最緊密的句法分析框架就是DOP框架,然而單獨使用DOP模型進行句法分析的效果并不理想.模型融合是提高模型解析精度的有效方法,將DOP與層次句法分析模型進行融合,既合理利用了CEMR模式化強的特點,又避免了單獨使用DOP模型精度不高的問題.

目前常用的模型融合方式包括特征融合和后處理融合,特征融合通過融合多個模型的特征,對其進行共同訓(xùn)練,聯(lián)合解碼.后處理融合則更傾向于多個模型結(jié)果的重組或選擇.由于特征融合并不適用于DOP模型,所以我們選擇后處理融合進行擴展,提出了面向CEMR的DOP與層次句法分析融合模型.

4.1 預(yù)處理

預(yù)處理階段的工作分為兩部分:1)樹片段的匹配;2)基于匹配結(jié)果的樹片段初選.張 杰等[10]在匹配樹片段時先匹配詞匯再匹配詞性,只有詞匯完全匹配的樹片段才能直接成為最終結(jié)果.與張 杰等的做法不同,我們沒有將詞匯和詞性單獨處理,而是采用詞匯和詞性混合的方式匹配樹片段,不局限于詞匯完全匹配的約束條件,充分發(fā)揮詞性在樹片段匹配過程中的泛化作用.樹片段初選主要選擇兩類樹片段,一類是能夠與輸入句子完全匹配的樹片段,另一類樹片段與輸入句子部分匹配,且存在不包含邊界結(jié)點的獨立子樹,這里邊界結(jié)點特指處于樹片段最左端或最右端的結(jié)點.其中,第一類樹片段能夠直接成為輸出結(jié)果,第二類樹片段是后續(xù)樹片段組合替換的基礎(chǔ).

初選的第二類樹片段可能是不規(guī)范或不合法的樹片段,圖5虛線框內(nèi)為不規(guī)范的樹片段,該類樹片段可能包含多棵子樹,將在第4.2節(jié)中進一步篩選.另外,僅依靠詞匯詞性匹配會抽取到不合法樹片段,如圖5實線框所示,由于只匹配到““(雙引號)腦卒中、(頓號)”,所以形成了錯誤的NP,為了避免抽取這類樹片段,增加了“存在不包含邊界結(jié)點的獨立子樹”的約束,在該約束條件下,用于替換的樹片段必須從初選樹片段內(nèi)部獲得(不含邊界結(jié)點),該約束條件雖然減少了初選樹片段的數(shù)量,但也解決了后續(xù)步驟中不合法樹片段帶來的錯誤替換問題.

圖5 初選樹片段樣例Fig.5 The sample of selected tree fragment

受連續(xù)公共子序列查找算法啟發(fā),本文提出了詞匯詞性混合初選算法,如算法3所示.

算法3.詞匯詞性混合初選算法

算法3中,ls1為樹片段的葉結(jié)點及其父結(jié)點集合,ls2為輸入句子的詞匯和詞性集合.UPDATE函數(shù)用于詞匯和詞性的混合匹配,同時將局部樹片段擴展為標準樹片段,具體分為4種情況:1)詞匯與葉結(jié)點匹配,直接返回TRUE;2)詞性與葉結(jié)點匹配,將詞匯追加為該葉結(jié)點的子結(jié)點,返回TRUE;3)詞性與父結(jié)點匹配,將詞性替換為父結(jié)點,返回TRUE;4)詞匯、詞性均不匹配,返回FALSE.算法第11行和第17行是第二類樹片段的約束條件,由于在后續(xù)工作中,用于替換的句法樹必須在樹片段內(nèi)部且獨立,所以我們抽取的第二類樹片段至少包含三個結(jié)點,或處于句子邊界位置且包含兩個結(jié)點.該算法最后返回所有匹配的邊界對,除了樹片段與句子完全匹配的情況,當局部樹片段邊界包含句子邊界,并且局部樹片段為獨立句法樹時,該局部樹片段也能夠直接輸出,否則該句子進入層次句法分析模型解析階段.算法單次執(zhí)行的時間復(fù)雜度為O(m×w),由于需要遍歷整個樹片段庫,所以最終時間復(fù)雜度為O(n×m×w),其中,n為樹片段個數(shù),m和w分別為樹片段葉結(jié)點數(shù)以及輸入句子的詞數(shù).

4.2 后處理融合

后處理階段是基于預(yù)處理初選的樹片段集和層次句法分析結(jié)果,進行樹片段的篩選、組合與替換,進一步改進句法分析結(jié)果.為了不影響層次句法分析結(jié)果中其他樹片段,用于替換的樹片段必須從初選樹片段內(nèi)部獲得,并且是高度大于1的標準樹片段,即不考慮僅包含詞匯和詞性的樹片段.初選樹片段可能包含多棵子樹,也可能與其他樹片段發(fā)生交叉,所以需要先對初選樹片段進行篩選.篩選后的樹片段集合是不含邊界結(jié)點的全部標準樹片段,以圖6為例,圖6(a)和圖6(b)分別為初選樹片段與篩選后的樹片段集合.

張 杰等采用先拼接再計算相似度的方式組合樹片段[10],在實驗中我們也嘗試了他們的最左優(yōu)先原則拼接樹片段,但該方式會生成更多無效句法樹,帶來更多噪聲.我們的最終目的是以樹片段替換方式改進已有句法樹,所以組合樹片段時可以繞開拼接過程,轉(zhuǎn)變?yōu)樽畲蠡~結(jié)點替換數(shù)目.基于動態(tài)規(guī)劃思想,本文提出最大樹片段組合算法,如算法4所示.

算法4.最大樹片段組合算法

圖6 初選樹片段與篩選樹片段集合Fig.6 The selected tree fragment and its filtered tree fragments

算法4不需要考慮拼接時邊界結(jié)點的匹配情況,而是直接獲得葉結(jié)點數(shù)最大時的樹片段集合.算法三個參數(shù)分別為:當前樹片段的右邊界(end),按右邊界從小到大排序的樹片段邊界集合(borders),所有右邊界對應(yīng)的最大樹片段集合(spans).now和max用于保存當前樹片段集合及當前右邊界對應(yīng)的最大樹片段集合,SPAN函數(shù)為now或max包含的葉結(jié)點數(shù).當兩個樹片段集合葉結(jié)點數(shù)相同時,遵循高度優(yōu)先原則,選擇層數(shù)更高的樹片段集合,因為葉結(jié)點相同時層數(shù)高的樹片段往往會包含層數(shù)低的樹片段.最大樹片段組合算法的時間復(fù)雜度為O(p2),p為篩選后的樹片段個數(shù).

基于最大樹片段組合算法獲得樹片段集合,下一步進行樹片段替換工作.樹片段替換依然遵循高度優(yōu)先原則,首先利用廣度優(yōu)先搜索遍歷層次句法分析模型輸出的句法樹中所有非終結(jié)符,當非終結(jié)符的葉結(jié)點與樹片段的葉結(jié)點完全匹配時,用樹片段替換以該非終結(jié)符為根結(jié)點的子樹,直到集合內(nèi)所有樹片段替換完成后,輸出新的句法分析結(jié)果.樹片段替換算法的時間復(fù)雜度為O(p×s×m),其中p為篩選后的樹片段個數(shù),s為層次句法分析模型輸出的句法樹中非終結(jié)符個數(shù),m為單個樹片段的最大葉結(jié)點數(shù).另外,在實驗中發(fā)現(xiàn),先對最大樹片段集合按葉結(jié)點數(shù)進行排序,再選擇前5個樹片段替換,比直接使用集合中的全部樹片段替換效果更好.

5 實驗結(jié)果與分析

在前期的工作中,我們以PCTB標注規(guī)范為基礎(chǔ),通過迭代的方式不斷調(diào)整規(guī)范,結(jié)合CEMR中特有的標注樣例對PCTB規(guī)范進行細化、擴充、刪減,首次提出了適用于中文電子病歷的分詞、詞性和句法標注規(guī)范,并獲得了較高的標注一致性和準確率,其詞性和句法標注體系與PCTB完全相同.本文實驗所用語料為前期標注的CEMR句法樹庫[12?13].該樹庫為神經(jīng)內(nèi)科和普通外科的出院小結(jié)和首次病程記錄,共138份CEMR,包含2555棵句法樹,語料統(tǒng)計信息如表3所示.語料采用的5折交叉驗證的方式構(gòu)造,每次隨機平分為5份,4份作為訓(xùn)練集,1份作為測試集,同時從訓(xùn)練集隨機抽取1/5作為調(diào)試集.

表3 CEMR句法樹庫統(tǒng)計信息Table 3 Corpus statistics of CEMR treebank

5.1 樹片段抽取實驗

為了對比句法分析模型,每次交叉驗證從上述訓(xùn)練語料中抽取出現(xiàn)2次以上的標準樹片段和局部樹片段,形成了兩個樹片段庫,并改進兩類樹片段的抽取算法,從而提高抽取效率.樹片段抽取結(jié)果如表4所示,實驗環(huán)境為64位Ubuntu系統(tǒng),1.2GHz的CPU.從抽取速度可以看出,利用FTK算法改進后,抽取效率明顯提高,抽取速度相當于QTK的4倍左右.表4中給出樹片段種類數(shù)而非樹片段數(shù),是因為樹片段種類的多少與文本模式化強弱相關(guān),直接影響DOP的性能,通常來說,文本模式化越強樹片段的種類應(yīng)該越少.從表中可以看出,局部樹片段的種類約為句子數(shù)的19倍,明顯多于標準樹片段,所以相比標準樹片段抽取速度也更慢.

表4 樹片段抽取結(jié)果Table 4 Results of fragment extraction

5.2 DOP與層次句法分析模型融合實驗

本文的對比模型包括引入標點符號糾錯和分割算法的層次句法分析模型(CLPU)、引入DOP的融合模型,以及開放領(lǐng)域最優(yōu)的Stanford parser和Berkeley parser.首先在單一科室CEMR上進行訓(xùn)練測試,即神經(jīng)內(nèi)科CEMR按5折劃分,隨機抽取1/5作為測試集,其余作為訓(xùn)練集.實驗結(jié)果如表5所示,在前期工作中,CLP和Berkeley parser在開放領(lǐng)域測試集(TCT)上句法分析精度相近[11],這里利用上下文詞典進一步修正了CLP結(jié)果中的標點符號錯誤,并引入標點對分割組合策略,得到了CLPU模型,句法分析F1值達到78.23%.受語料規(guī)模影響,Berkeley parser產(chǎn)生了52個空輸出,導(dǎo)致F1值降為78.17%,落后于CLPU結(jié)果.為解決Berkeley parser的空輸出問題,本文對產(chǎn)生空輸出的句子使用另一個PTCB訓(xùn)練的Berkeley parser解析,最后Berkeley parser(CEMR+PCTB)的F1值能夠提高到79.8%,由于其他模型不涉及空輸出問題,所以不需要額外訓(xùn)練模型解析.

在模型融合方面,本文首先對比了引入標準樹片段(SDOP)和局部樹片段(PDOP)的模型效果.可以看出,引入標準樹片段和局部樹片段后F1值均有較大的提升,最多提高了2.64%.雖然標準樹片段產(chǎn)生錯誤替換的可能性更小,但也限制了樹片段的多樣性,導(dǎo)致最終與局部樹片段的F1值相差1.32%.另一方面,通過錯誤分析發(fā)現(xiàn),單個樹片段匹配的葉結(jié)點越多,錯誤替換的概率越小,所以對篩選組合后的樹片段集合先排序再替換,實驗證明保留前5個樹片段進行替換的F1值最高,達到80.87%,獲得了目前CEMR上句法分析的最優(yōu)結(jié)果.

表5 神經(jīng)內(nèi)科CEMR句法分析結(jié)果Table 5 Parsing results on CEMR of neurology department

為了對比各模型在不同領(lǐng)域中的性能,本文在PCTB上進行了句法分析實驗.為公平起見,PCTB上采用與CEMR相同的實驗設(shè)置,僅從PCTB中隨機抽取1207句訓(xùn)練,277句測試,實驗結(jié)果如表6所示.根據(jù)已公布的結(jié)果,當訓(xùn)練語料充足時(訓(xùn)練測試語料的比例達到50倍),Stanford parser和Berkeley parser在PCTB上句法分析F1值能夠達到84% 左右,而在表6中,當PCTB的訓(xùn)練語料規(guī)模與CEMR同樣小時,Berkeley parser的F1值最高只有64%左右,Stanford parser更下降到61.16%,相比之下,CEMR在僅需要少量標注語料的情況下,F1值卻能夠達到80%左右,在一定程度上也證明了其模式化強,句法清晰的特點.進一步對比各模型的實驗結(jié)果,DOP在PCTB上無論是解析速度還是F1的增幅上都有較大下降.究其原因,解析速度變慢是由于從PCTB中抽取的樹片段庫相比CEMR規(guī)模要大,其局部樹片段種類達到句子數(shù)的43倍之多,所以在樹片段的遍歷匹配時需要消耗大量時間.如此多的樹片段種類說明PCTB并不像CEMR模式化那么強,導(dǎo)致DOP帶來的增幅僅為0.42%.同時,標點符號在PCTB所占比例的下降,使得CLPU的F1值只有63.6%,最終引入DOP后仍落后Berkeley parser 0.36%.盡管本文提出的融合模型在PCTB上的表現(xiàn)并不理想,但是也從另一個角度驗證了其更加適用于模式化強的子語言文本的假設(shè).

在跨科室句法分析實驗中,本文選擇已標注的兩個科室上進行交叉測試,實驗設(shè)置與表5相同.分析結(jié)果如表所示.從表7可以看出,由于不同科室間的詞匯存在較大差異,使得詞性標注時未登錄詞率升高,各模型詞性標注準確率均有不同程度的下降,最終句法分析F1值只能達到69%左右.其中受未登錄詞率影響最大的是Stanford parser,特別是在普通外科訓(xùn)練、神經(jīng)內(nèi)科測試時,Stanford parser詞性標注準確率僅為75.23%,導(dǎo)致最后句法分析F1值只有57.85%.相比之下,本文提出的CLPU及融合模型表現(xiàn)出色,盡管在詞性標注準確率上也有所下降,但是標點符號的高使用率、文本模式化強的特點是不同科室的共性,所以兩個模型的跨科室性能相比Stanfrod parser和Berkeley parser有較大的優(yōu)勢,融合DOP后F1值能夠超過最好結(jié)果2%以上.但是,在進行錯誤分析時,我們發(fā)現(xiàn)詞匯差異使DOP錯誤替換的幾率增加,導(dǎo)致引入DOP后詞性標注準確率反而有較大下降,所以相比CLPU的提升只有1%左右.

最后,綜合比較各模型在單一科室CEMR,PCTB以及跨科室CEMR的句法分析性能.Stanford parser的解析速度最快,但是也最不穩(wěn)定,容易受未登錄詞影響,當未登錄詞率較高時,句法分析F1值有較大幅度的下降.Berkeley parser的性能中規(guī)中矩,但是對語料規(guī)模依賴較強,當標注語料充足時,句法分析性能更好,但是考慮到CEMR的文本特殊性,除了數(shù)據(jù)來源受限,還要求標注者同時具備語言學(xué)和醫(yī)學(xué)相關(guān)知識,所以構(gòu)建大規(guī)模CEMR語料庫更加困難.本文提出的CLPU和DOP的融合模型在CEMR上的句法分析性能要優(yōu)于Stanford parser和Berkeley parser,特別是跨科室句法分析時表現(xiàn)更為突出,證明引入樹片段對于模式化強的子語言分析是行之有效的方法.進一步對比DOP中各算法的時間復(fù)雜度,由于初選過程需要遍歷整個樹片段庫,而樹片段庫的量級遠大于其他參數(shù),占用了大量的解析時間,導(dǎo)致融合模型的句法分析速度相比Stanford parser和Berkeley parser差距較大.但是,由于目前還沒有在樹片段的存儲和查找上做任何優(yōu)化工作,所以未來在解析速度上仍有上升空間,例如遍歷樹片段庫時引入剪枝策略,通過對樹片段進行編碼提高匹配效率等.

表6 PCTB句法分析結(jié)果Table 6 Parsing results on PCTB

表7 跨科室CEMR句法分析結(jié)果Table 7 Parsing results on cross-department CEMR

6 結(jié)論

本文針對CEMR模式化強的特點,提出以樹片段形式化CEMR復(fù)用的模式.首先描述了樹片段的相關(guān)概念,舉例說明標準樹片段和局部樹片段的區(qū)別,然后針對標準樹片段的重復(fù)比對問題,提出更加高效的標準樹片段抽取算法,又利用快速樹核算法替換二次樹核算法,降低了局部樹片段抽取算法的時間復(fù)雜度,并通過實驗對比了改進前后局部樹片段抽取速度的變化,最終獲得了標準樹片段庫和局部樹片段庫.基于抽取的樹片段庫,提出了DOP與層次句法分析的融合模型,該模型屬于后處理融合,以模型融合的方式避免了單獨使用DOP模型精度較低的問題.在預(yù)處理階段,提出了詞匯詞性混合匹配的初選策略,充分發(fā)揮詞性在匹配時的泛化作用.在后處理階段,一方面,從初選樹片段內(nèi)部篩選標準樹片段,減少了錯誤樹片段的替換,另一方面,提出了最大化樹片段組合算法,簡化DOP組合分析過程,緩解了無效樹片段帶來的噪聲.實驗結(jié)果表明,DOP與層次句法分析的融合模型能夠利用CEMR模式化強的特點,有效改善句法分析效果.

CEMR模式化強的特點為DOP創(chuàng)造了更大的發(fā)展空間.未來的工作,一方面可以探索更加深入的模型融合方法,進一步提高DOP在融合模型中的比重;另一方面,CEMR高昂的句法標注成本使得無監(jiān)督句法分析方法更具實用價值,如何充分發(fā)揮DOP在無監(jiān)督句法分析上的優(yōu)勢,提出適用于CEMR的無監(jiān)督DOP模型是值得研究的問題.