代鸝鵬,王布宏,曹　帥,沈海鷗

(空軍工程大學信息與導航學院,陜西西安 710077)

?

基于最優(yōu)解析樹提取的多功能雷達狀態(tài)快速估計方法

代鸝鵬,王布宏,曹帥,沈海鷗

(空軍工程大學信息與導航學院,陜西西安 710077)

摘要：針對基于文法建模的多功能雷達(Multi-Function Radar,MFR)參數(shù)估計領域中常規(guī)算法具有的高運算復雜度問題,提出一種快速估計算法.該算法利用文法的派生過程僅與文法結(jié)構(gòu)有關,而與文法概率參數(shù)無關這一事實,利用庫克-楊-卡塞米(Cocke-Younger-Kasami,CYK)算法對截獲雷達數(shù)據(jù)序列進行預處理,構(gòu)造出可以反映該序列派生過程的解析表,進而從該解析表中提取出序列的最優(yōu)解析樹,然后利用改進的Viterbi-Score算法對雷達文法概率參數(shù)進行快速估計.論文仿真分析了該算法的計算復雜度、存儲復雜度和估計精度,實驗結(jié)果表明了該算法相對于常規(guī)算法,可以減少60%左右的計算量.

關鍵詞:多功能雷達;隨機上下文無關語法;解析表;解析樹

1引言

電子支援系統(tǒng)(Electronic Support,ES)通過分析戰(zhàn)場截獲的雷達輻射源信號,向我方飛行員提供該輻射源所處的方位、狀態(tài)和威脅等級等情報[1].對于傳統(tǒng)的機械掃描雷達,ES系統(tǒng)可以通過分析輻射源信號的載頻、脈寬等瞬時特性,采用參數(shù)類的統(tǒng)計方法便可實現(xiàn)有效告警[2].但對于多功能雷達(Multi-Function Radars,MFR)而言,由于MFR采用軟件算法對波束進行控制,其波束掃描是無慣性的,且MFR采用了復雜多變的信號模式,使得MFR能夠同時對多個目標進行操作.由于MFR的這些特性,基于參數(shù)類的威脅告警技術(shù)已無法滿足MFR的建模需求[3].為了對MFR的這種多功能性、多工作模式進行有效描述,Nikita與Wang將Markov鏈與隨機上下文無關文法(Stochastic Context-Free Grammars,SCFG)相結(jié)合,提出模式類的MFR建模方法[4],該方法將語言學中的知識引入到雷達信號處理領域,為今后的研究提供了新的思路.

給定能夠描述MFR雷達動態(tài)行為的文法結(jié)構(gòu),如何利用截獲的信號序列對MFR的文法概率參數(shù)進行估計是模式類ES系統(tǒng)面臨一個關鍵問題.通常的方法是將期望最大化算法(Expectation-Maximization,EM)應用于語言學中的Inside-Outside(IO)算法[5]和Viterbi-Score(VS)算法[6]對概率參數(shù)進行迭代求精,但是這兩種方法的收斂速度和計算復雜度均無法滿足ES系統(tǒng)的實時性要求.文獻[7]針對上述問題,提出gEM(IO)和gEM(VS)算法,但這兩種算法只針對單個文法的訓練,無法對多個文法進行并行訓練.本文將解析表應用于VS算法,提出P(VS)算法對多個雷達文法的參數(shù)進行并行快速估計,并通過理論分析與仿真實驗證明P(VS)算法相對于IO、VS和基于解析表的IO算法(P(IO)),可以有效降低運算復雜度.

2MFR雷達的系統(tǒng)結(jié)構(gòu)分析

MFR通過軟件程序?qū)θ蝿者M行調(diào)度,并將每一種任務映射為基本的脈沖波形進行發(fā)射,每個基本脈沖波形稱為一個雷達字,雷達字為MFR的最小輻射單元[8].由此可見,MFR為了滿足不同的功能需求而使用了分層的信號結(jié)構(gòu),因此可利用分層的雷達信號結(jié)構(gòu)模型對MFR進行建模.該方法首先將雷達的狀態(tài)轉(zhuǎn)換視為隨機離散事件,雷達在每個狀態(tài)采用特定的隨機形式語言交流信息,然后在電子情報基礎上利用能夠捕獲MFR復雜信號特征的文法對該語言進行建模,將每一部MFR在威脅數(shù)據(jù)庫中對應一個文法語言模型,最后利用機器翻譯和解碼技術(shù)對雷達狀態(tài)進行解析.

MFR依據(jù)自身所處的戰(zhàn)術(shù)環(huán)境選擇雷達需要執(zhí)行的任務狀態(tài),然后將該任務狀態(tài)通過映射機制轉(zhuǎn)換為雷達字序列,最后將該雷達字序列映射為相應的脈沖序列進行發(fā)射.因此,雷達狀態(tài)選擇機制為一個Markov過程,即在每個MFR周期選擇一個合適的任務狀態(tài)ei,并依據(jù)狀態(tài)ei所定義的調(diào)度規(guī)則對雷達字進行調(diào)度[9].從ESM系統(tǒng)角度來講,雷達內(nèi)部工作機制是未知的,因此將每一次調(diào)度行為建模為概率性事件,概率值大小代表雷達的資源分配方案.

利用SCFG對其調(diào)度方式建模,可得到MFR的信號產(chǎn)生機制如圖1所示.該建模方法利用馬爾科夫鏈描述雷達狀態(tài)的動態(tài)轉(zhuǎn)移情況,利用SCFG描述MFR產(chǎn)生雷達信號的調(diào)度機制.

對于CFG而言,其產(chǎn)生的終止符序列η可觀測得到,但是產(chǎn)生η的具體過程無法直觀得到.由文獻[11]可知,文法產(chǎn)生η的派生過程僅與文法結(jié)構(gòu)有關,而與文法的概率值無關,因此可以利用CYK算法[12]或Early算法[13]對每個序列η進行預處理,構(gòu)造可以精確描述該派生過程的解析表,并從中提取出最優(yōu)解析樹,在概率重估時,只有最優(yōu)解析樹參與重估過程,從而減少算法計算復雜度(計算復雜度定義為對一個訓練序列進行一次迭代所需要的乘法和除法運算次數(shù)).

3基于解析表的MFR參數(shù)快速估計算法

3.1CYK圖表解析算法

對序列η進行分析,意味著需要確定一個文法導出η的產(chǎn)生式序列.CYK算法作為一種描述性算法,已應用于語音識別領域.CYK算法要求所處理的文法產(chǎn)生式為A→w或者A→BC兩種結(jié)構(gòu)[14],其中A,B,C∈V,w∈N.根據(jù)不同的產(chǎn)生式定義不同的子樹結(jié)構(gòu)來確定η的子序列母節(jié)點,其中產(chǎn)生式A→a對應的子樹結(jié)構(gòu)為A(j,j)→a,表示wj=a,且A→wj∈R.產(chǎn)生式A→BC對應的子樹結(jié)構(gòu)為A(i,j)→B(i,k)C(k+1,j),表示文法以A為母節(jié)點產(chǎn)生子序列wiwi+1…wj,在該子序列中,wiwi+1…wk以B為母節(jié)點,wk+1…wj以C為母節(jié)點,且A→BC∈R.

對于給定的長度為L的序列,解析表T是一個三角形表,每個表中第i行第j列的參數(shù)為T(i,j),其中1≤i≤L,1≤j≤L+1-i.對于η的某個子串,若有A?wiwi+1…wj,則把A(i,j)→…存入T(i,j)中.在構(gòu)造出解析表后,當且僅當S(1,L)→…存在于T(1,L)中時,η∈Lg(Gs),且可從該解析表中抽取出該序列的最左導出.

對于序列η=w1w2…wL,可以從左到右、從最高行到最低行順次構(gòu)造解析表.由于G必須符合Chomsky正則形式表示,使得我們能按照下列步驟對η構(gòu)造此解析表:

步驟1按照i=1到i=L的次序求T(i,i),若R中存在產(chǎn)生式A→wi時,將A(i,i)→wi填入T(i,i).

步驟2假設對1≤i≤L已經(jīng)求出T(i,j-1),現(xiàn)在求T(i,j).對于i=L-1:1,有j=i+1:L,則對于1≤k≤j-1中的任何一個k值,當A→BC∈R,且B(i,k)→…∈T(i,k),C(k+1,j)→…∈T(k+1,j),則將A(i,j)→B(i,k)C(k+1,j)填入T(i,j).

步驟3重復第二步直至完成此表或表的整行都是空項.

通過對每個序列提前構(gòu)造解析表可以發(fā)現(xiàn),解析表中的子樹結(jié)構(gòu)參數(shù)描述了文法產(chǎn)生η的所有派生過程,我們可在算法每次迭代過程中利用解析表排除不參與派生的參數(shù),從而可以減少計算量.

3.2MFR文法概率快速估計算法

令x1:m=(x1,x2,…,xm)為MFR狀態(tài)序列,xk∈Nr.η1:m=(η1,η2,…,ηm)表示截獲得到的MFR產(chǎn)生的m個終結(jié)符序列,其中ηi=w1w2…wLi,Li表示ηi的長度.為了對文法進行解析,首先引入內(nèi)部概率αA(i,j)=P(wij|A,Gs),該概率表示Gs從非終結(jié)符A開始,生成終結(jié)符序列wiwi+1…wj的概率.

(1)

對于每個母節(jié)點為A(i,j)(i

(2)

因此,母節(jié)點A(i,j)對應的最大內(nèi)部概率為所有以A(i,j)為母節(jié)點的子樹分支概率的最大值:

(3)

對于每個母節(jié)點A(i,j),使得式(3)最大的子樹分支稱為最優(yōu)子樹分支,定義為:

(4)

令Φ保存每個最優(yōu)子樹的路徑,即:

(5)

步驟3概率重估.在得到文法產(chǎn)生每個序列的產(chǎn)生式期望使用次數(shù)以后,文法產(chǎn)生式的概率便可估計為:

(6)

其中ξt(i,j)=P(xt=ei,xt+1=ej|η1:m)表示在t時刻MFR處于ei狀態(tài),t+1時刻處于ej狀態(tài)的概率.χt(i,j)=P(xt=ei|η1:m)表示MFR在t時刻處于狀態(tài)ei的概率.則雷達管理模塊對應的Markov鏈狀態(tài)轉(zhuǎn)移概率可估計為:

(7)

通過上述步驟進行迭代計算,直至文法概率參數(shù)變化非常小時結(jié)束.每經(jīng)過一次迭代,模型對于給定觀測數(shù)據(jù)的似然性都會增加,這樣就保證了每次迭代都會產(chǎn)生更優(yōu)的模型參數(shù).通過P(VS)算法得到文法的概率參數(shù)后,便可利用Viterbi算法對MFR所處狀態(tài)進行估計[15].

4算法分析與仿真

為了驗證本文的算法,我們首先對四種算法的計算復雜度進行理論分析,并利用表1所示文法進行仿真驗證.在該文法基礎上,我們設計兩個實驗:第一個實驗對算法時間復雜度進行分析.第二個實驗對算法的收斂時間和精度進行分析.

4.1算法資源分析

為了對算法資源進行理論分析,首先定義以下變量:L表示訓練序列的平均長度;Mt表示輻射規(guī)則的數(shù)目;Mtm表示文法終結(jié)符的數(shù)目;Mnt表示文法非終結(jié)符的數(shù)目;|φt|表示解析表中轉(zhuǎn)移規(guī)則的平均數(shù);|Δe|表示解析表中輻射規(guī)則的平均數(shù);|Δlt|表示解析表中每個轉(zhuǎn)移規(guī)則對應的平均子樹的個數(shù);|Δle|表示左部參數(shù)相同的輻射規(guī)則平均數(shù).由于算法在產(chǎn)生式概率均勻分布時計算復雜度最大,則在該條件下有:

(8)

|φe|=Mnt·L

(9)

(10)

則對于IO算法而言,其計算復雜度TIO為:

(11)

對于VS算法而言,其計算復雜度TVS為:

(12)

對于P(IO)算法,其平均計算復雜度TP(IO)為:

(13)

對于P(VS)算法,其平均計算復雜度TP(VS)為:

(14)

定義算法對一個序列進行一次迭代時需要存儲的參數(shù)個數(shù)為算法的存儲復雜度.因此,IO算法的存儲復雜度MIO為:

(15)

VS算法的存儲復雜度MVS為:

(16)

由于P(IO)與P(VS)算法在對訓練進行預處理時,需對解析表進行存儲,對于長度為L的序列,其解析表需要存儲的參數(shù)個數(shù)為:

(17)

因此,于P(IO)與P(VS)算法的存儲復雜度分別為:

MP(IO)=MIO+MCYK

(18)

MP(VS)=MVS+MCYK

(19)

參數(shù)|φt|和|Δlt|反應了文法的模糊性,因此P(IO)和P(VS)的平均計算復雜度與文法固有的模糊性具有很大關聯(lián).文獻[4]中所描述的“水星”MFR部分文法產(chǎn)生式為S→ACQRR、ACQ→ACQNA|W1W1|W2W2|W3W3|W4W4|、NA→S1T、RR→RRNA|RRpACQ、T→W2W5、NAp→W2|W3、RRp→W4|W5、S1→W1|W2|W3、W1→w1、W2→w2、W3→w3、W4→w4和W5→w5,其非終止符集V={S,ACQ,RR,NA,S1,T,NAP,RRP,W1,W2,W3,W4,W5},終止符集N={w1,w2,w3,w4,w5},初始符為S.由該文法產(chǎn)生序列構(gòu)造的解析表中,|Δlt|max=3,將其帶入上面各式,可得到不同序列長度與不同算法的計算復雜度、存儲復雜度比較結(jié)果,如圖2與圖3所示.

4.2算法時間復雜度分析

假設MFR有兩個狀態(tài),分別對應文法G(1)和G(2),由狀態(tài)轉(zhuǎn)移矩陣為A=(0.7,0.3;0.4,0.6)的Markov鏈隨機產(chǎn)生50個雷達狀態(tài),每個狀態(tài)依據(jù)文法G(1)或G(2)隨機產(chǎn)生一個終結(jié)符序列,然后對產(chǎn)生式概率和狀態(tài)轉(zhuǎn)移概率進行估計.經(jīng)過100次Monte Carlo實驗,得到算法實驗結(jié)果如圖4和圖5所示.

算法的計算復雜度反應到程序中,便為程序的運行時間,我們通過不同迭代次數(shù)、不同序列個數(shù)與算法的運行時間進行驗證.由圖4和圖5可知,隨著迭代次數(shù)和訓練序列的增加,IO算法的運行時間也急劇增加,這導致了其在實際應用中具有局限性.VS算法只對最大解析樹進行求解,算法對序列進行一次迭代運行時間比IO算法減少一半左右.P(IO)與P(VS)算法對訓練序列進行了預處理,其中,P(IO)算法對解析表中的所有路徑求解,P(VS)算法只對解析表定義的最優(yōu)解析樹求解,其算法運行時間比IO與VS算法降低了一半以上,且實驗值可以很好的符合理論分析.

4.3算法性能分析

該實驗通過對比IO、VS、P(IO)和P(VS)算法收斂后的估計結(jié)果與真實值的誤差平方和與MFR狀態(tài)估計概率來判別算法性能.定義第n+1次迭代結(jié)果和第n次迭代結(jié)果的誤差平方和小于0.001時結(jié)束.經(jīng)過100次Monte Carlo實驗,結(jié)果如圖6、7所示.

由圖6可知,四種算法隨著迭代次數(shù)的增加,其估計值與真實值的誤差會逐漸降低,趨于收斂時,P(IO)和IO算法的估計誤差相同,而VS與P(VS)算法的估計誤差值始終比P(IO)和IO算法大0.4左右.文法概率參數(shù)的估計精度會影響到最終MFR狀態(tài)的估計,不同迭代次數(shù)與MFR狀態(tài)估計結(jié)果如圖7所示,由圖可知,IO算法的與P(IO)算法在收斂后的狀態(tài)估計概率在0.91左右,而VS與P(VS)算法的估計概率為0.94左右.

5結(jié)論

本文針對基于SCFG建模的MFR參數(shù)快速估計算法進行研究,提出一種基于解析表的參數(shù)估計算法.該算法通過CYK解析算法對截獲的訓練序列集預先構(gòu)造解析表,在序列集解析表的基礎上排除未參與序列派生過程的產(chǎn)生式,并尋找出最優(yōu)解析樹,且只有最優(yōu)解析樹參與重估過程,大大的減少了算法復雜度.本文通過理論分析與試驗仿真證明,該方法在減少運算量的同時,可以確保其精度與IO、P(IO)算法大致相同,在ES系統(tǒng)的實際應用中具有重要意義,如何減少該算法的存儲需求,是下一步的研究方向之一.

參考文獻

[1]劉海軍,李悅,柳征,周一宇.基于隨機文法的多功能雷達識別方法[J].航空學報,2010,31(9):1809-1817.

LIU Hai-jun,LI Yue,ZHOU Yi-yu.Approach to multi-function radar identification based on stochastic grammars[J].Acta Aeronautica Et Astronautica Sinica,2010,31(9):1809-1817.(in Chinese)

[2]Wang A,Krishnamurthy V.Signal interpretation of multi-function radars:modeling and statistical signal processing with stochastic context free grammar[J].IEEE Transactions on Signal Processing,2008,56(3):1106-1119.

[3]劉海軍.雷達輻射源識別關鍵技術(shù)研究[D].長沙:國防科學技術(shù)大學,2010.

[4]N Visnevski.Syntactic Modeling of Multi-function Radars[D].Canada:McMaster University,2005.

[5]K Lari,S Young.The estimation of stochastic context-free grammars using the inside-outside algorithm[J].Computer Speech and Language,1990,4(1):35-56.

[6]H Ney.Stochastic Grammars and Pattern Recognition[M].New York:Springer Verlag,1992.

[7]Latombe G,Granger E,Dilkes F A.Fast learning of grammar production probabilities in radar electronic support[J].IEEE Transactions on Aerospace and Electronic Systems,2010,46(3):1262-1289.

[8]馬爽,柳征,姜文利.基于幅度變化點檢測的多功能雷達脈沖列解析方法[J].電子學報,2013,41(7):1436-1441.

MA Shuang,LIU Zheng,JIANG Wen-li.A method for multi-function radar pulse train analysis based on amplitude change point detection[J].Acta Elcctronica Sinica,2013,41(7):1436-1441.(in Chinese)

[9]Visnevski N,Krishnamurthy V,Wang A,Haykin S.Syntactic modeling and signal processing of multi-function radars:a stochastic context-free grammar approach[J].Proceedings of the IEEE,2007,95(5):1000-1025.

[10]D Manning,H Schutze.統(tǒng)計自然語言處理基礎[M].范春法,等,譯.北京:電子工業(yè)出版社,2002.241-256.

[11]R C Gonzalez,M G Thomason.句法模式識別[M].濮群,譯.北京:清華大學出版社,1984,84-88.

[12]Tsuruoka Y,Tsujii J.Iterative CYK parsing for probabilistic context-free grammars[A].First International Joint Conference on Natural Language Processing[C].Hainan,China:IJCNLP,2005.52-60.

[13]J Early.An efficient context-free parsing algorithm[J].Communication of the ACM,1970,13(2):84-102.

[14]陸玲,周書民.形式語言與自動機及程序設計[M].哈爾濱:哈爾濱工業(yè)大學出版社,2014,11-16.

[15]代鸝鵬,王布宏,蔡斌,劉軍利.基于SCFG建模的多功能雷達狀態(tài)估計算法[J].空軍工程大學學報·自然版,2014, 15(3):24-28.

DAILi-peng,WANG Bu-hong,CAI Bin,LIU Jun-li.A method for states estimation of multi-function radar based on stochastic context-free grammar[J].Journal of Air Force Engineering University(Natural Science Edition),2014,15(3):24-28.(in Chinese)

代鸝鵬男,1989年1月出生于甘肅省平?jīng)鍪?現(xiàn)為空軍工程大學信息與導航學院碩士研究生.主要研究方向為多功能雷達信號處理.

E-mail:dlipeng@163.com

王布宏男,1975年12月出生于山西省太原市.現(xiàn)為空軍工程大學教授、博士生導師.主要從事陣列信號處理、陣列校正等方面的研究工作.

E-mail:wbhyl@aliyun.com

曹帥男,1991年11月出生于陜西省西安市.現(xiàn)為空軍工程大學信息與導航學院碩士研究生.主要研究方向為陣列信號處理.

E-mail:465782523@qq.com

Approach to Multi-function Radar Parameters Fast Estimation Based on Best Parse Tree Extract

DAI Li-peng,WANG Bu-hong,CAO Shuai,SHEN Hai-ou

(SchoolofInformationandNavigation,AirForceEngineeringUniversity,Xi’an,Shaanxi710077,China)

Abstract:To deal with the huge computing burden of the existing multi-function radar (MFR) syntactic model parameters learning algorithms,a fast learning algorithm is proposed in light of the derivation only relevant to the syntactic architecture but the probabilities.In our method,each training sequence is pre-processed by the Cocke-Younger-Kasami(CYK) parsing algorithm,the parse chart is constructed to accurately describe the sequence derivation.Furthermore,the best parse tree is extracted from the parse chart,and the probabilities are estimated based on the best parse tree with a modified Viterbi-Score algorithm (VS).The time complexity,memory complexity and accuracy are also explored.Simulation results show that compared with the conventional algorithm,more than 60% operation time can be reduced with our proposed algorithm.

Key words:multi-function radar;stochastic context free grammar;parsing chart;parsing tree

作者簡介

DOI:電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.003

中圖分類號:TN918.1

文獻標識碼：A

文章編號：0372-2112 (2016)03-0514-06

基金項目:國家自然科學基金(No.61172148)

收稿日期:2014-08-13;修回日期:2014-11-25;責任編輯:覃懷銀