曹帥　王布宏　劉新波　沈海鷗

摘要：

針對基于隨機(jī)上下文無關(guān)文法（SCFG）建模的多功能雷達(dá)（MFR）概率學(xué)習(xí)問題，在傳統(tǒng)InsideOutside（IO）算法和ViterbiScore（VS）算法的基礎(chǔ)上，提出一種基于Earley算法的多功能雷達(dá)文法概率快速學(xué)習(xí)算法。該算法通過對截獲的雷達(dá)數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)造可以反映派生過程的Earley剖析表，并且基于最大子樹概率原則從剖析表中提取出最優(yōu)剖析樹，利用改進(jìn)的IO算法和改進(jìn)的VS算法對文法概率進(jìn)行學(xué)習(xí)，實現(xiàn)MFR參數(shù)估計，得到文法參數(shù)后，再利用Viterbi算法對MFR狀態(tài)進(jìn)行估計。理論分析和實驗仿真表明，與IO算法和VS算法相比，改進(jìn)算法在保持估計精度的同時，可以有效降低計算復(fù)雜度和減少運(yùn)行時間，驗證了Earley算法能夠提高文法概率的學(xué)習(xí)速度。

關(guān)鍵詞：

隨機(jī)上下文無關(guān)文法；多功能雷達(dá)；文法概率快速學(xué)習(xí)算法【只是本文提出的算法吧；Earley算法；參數(shù)估計；狀態(tài)估計

中圖分類號：

U416.216

文獻(xiàn)標(biāo)志碼：A

Abstract：

To deal with the probability learning problem in MultiFunction Radar （MFR） based on Stochastic ContextFree Grammar （SCFG） model， a new fast learning algorithm of grammatical probabilities in MFR based on Earley algorithm was presented on the basis of traditional InsideOutside （IO） algorithm and ViterbiScore （VS） algorithm. The intercepted radar data was preprocessed to construct an Earley parsing chart which can describe the derivation process. Furthermore， the best parsing tree was extracted from the parsing chart based on the criterion of maximum subtree probabilities. The modified IO algorithm and modified VS algorithm were utilized to realize the learning of grammatical probabilities and MFR parameter estimation. After getting the grammatical parameters， the state of MFR was estimated by Viterbi algorithm. Theoretical analysis and simulation results show that compared to the conventional IO algorithm and VS algorithm， the modified algorithm can effectively reduce the computation complexity and running time while keeping the same level of estimation accuracy， which validates that the grammatical probability learning speed can be improved with the proposed method.

英文關(guān)鍵詞Key words：

Stochastic ContextFree Grammar （SCFG）； MultiFunction Radar （MFR）； grammatical probabilities fast learning algorithm； Earley algorithm； parameter estimation； state estimation

0引言

雷達(dá)告警接收機(jī)（Radar Warning Receiver， RWR）系統(tǒng)通過測量與分析照射到載機(jī)上的雷達(dá)信號，對截獲雷達(dá)數(shù)據(jù)與雷達(dá)威脅數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行匹配來確定威脅雷達(dá)輻射源的類型、工作狀態(tài)、方位、威脅等級等信息，從而對飛行員提供有效建議，采取有效措施[1]。對于常規(guī)體制雷達(dá)，采用基于參數(shù)的雷達(dá)告警技術(shù)[2]便可對雷達(dá)輻射源型號和工作狀態(tài)進(jìn)行有效識別。多功能雷達(dá)（MultiFunction Radar， MFR）為新體制雷達(dá)，是一種有源相控陣火控雷達(dá)[3]，采用電子掃描技術(shù)和復(fù)雜的軟件算法對波束進(jìn)行控制，極大地提高了目標(biāo)探測和跟蹤能力；但這也導(dǎo)致雷達(dá)信號參數(shù)空間成指數(shù)增長，對RWR系統(tǒng)的數(shù)據(jù)存儲和處理能力有著極高的要求，而且常規(guī)體制雷達(dá)的5大參數(shù)，即射頻（Radio Frequency， RF）、到達(dá)方向（Direction Of Arrival， DOA）、到達(dá)時間（Time Of Arrival， TOA）、脈沖寬度（Pulse Width， PW）以及脈沖幅度（Pulse Amplitude， PA），無法描述MFR工作模式的快速變化，使得RWR系統(tǒng)的工作性能急劇下降[4]。為了克服MFR的動態(tài)性問題，Visnevski[5]利用形式語言中的隨機(jī)上下文無關(guān)文法（Stochastic ContextFree Grammar， SCFG）對MFR信號產(chǎn)生機(jī)制和工作模式進(jìn)行動態(tài)分析和數(shù)學(xué)建模，提出了模式類的雷達(dá)告警技術(shù)。

在MFR文法建模的基礎(chǔ)上，利用截獲的雷達(dá)數(shù)據(jù)對文法產(chǎn)生式概率進(jìn)行學(xué)習(xí)[6]，對MFR參數(shù)和狀態(tài)進(jìn)行估計是模式類雷達(dá)告警技術(shù)中的核心問題。IO（InsideOutside）算法[7]和VS（ViterbiScore）算法[8]是兩種常見的參數(shù)估計方法，文獻(xiàn)[9]將期望最大化（ExpectationMaximization， EM）算法應(yīng)用到IO算法和VS算法中對文法產(chǎn)生式概率進(jìn)行學(xué)習(xí)，實現(xiàn)對

MFR參數(shù)的估計，在得到文法參數(shù)后，再利用Viterbi算法實現(xiàn)對MFR狀態(tài)的

估計[10]。IO算法通過尋求訓(xùn)練數(shù)據(jù)集的全局最大似然對文法產(chǎn)生式概率進(jìn)行學(xué)習(xí)，計算量較大；而VS算法只尋求訓(xùn)練數(shù)據(jù)集的全局最優(yōu)解的最大似然對文法產(chǎn)生式概率進(jìn)行學(xué)習(xí)，相對于IO算法，雖然減小了計算量，但卻犧牲了精度，所以這兩種算法都無法滿足RWR系統(tǒng)的實用需要。

針對上述問題，本文提出基于Earley算法[11]的MFR文法概率快速學(xué)習(xí)算法，在原有IO算法和VS算法的基礎(chǔ)上得到兩種新的算法，即E（IO）算法和E（VS）算法。E（IO）算法通過對截獲雷達(dá)數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)造Earley剖析表；加入點(diǎn)規(guī)則減少匹配中的冗余操作，以及能夠反映規(guī)則匹配的狀態(tài)；剖析表中的文法產(chǎn)生式都參與重估過程；E（VS）算法在E（IO）算法的基礎(chǔ)上，基于最大子樹概率原則從剖析表提取出最優(yōu)剖析樹，只有最優(yōu)剖析樹上的文法產(chǎn)生式參與重估過程。通過構(gòu)造剖析表和加入點(diǎn)規(guī)則，可以解決有歧義文法產(chǎn)生式重復(fù)剖析、無效文法產(chǎn)生式重復(fù)剖析以及排除未參與派生過程的產(chǎn)生式等問題，從而對MFR參數(shù)和狀態(tài)進(jìn)行估計。通過理論分析和實驗仿真，與IO算法和VS算法在計算復(fù)雜度、運(yùn)行時間和狀態(tài)估計精度等方面進(jìn)行比較可知，E（IO）算法和E（VS）算法在保持估計精度的同時可以有效減少計算復(fù)雜度和運(yùn)行時間，驗證了Earley算法可以提高文法概率的學(xué)習(xí)速度。

1MFR文法建模

對MFR進(jìn)行文法建模，需要引入雷達(dá)脈沖信號、雷達(dá)字、雷達(dá)短語3個層級的雷達(dá)信號結(jié)構(gòu)的概念。雷達(dá)字是MFR的最小輻射單元[12]，為有限個數(shù)的雷達(dá)脈沖信號的固定排列，能夠反映MFR的工作狀態(tài)和威脅等級；而雷達(dá)短語是有限個數(shù)的雷達(dá)字的固定排列，每個短語對應(yīng)一個雷達(dá)功能狀態(tài)。因此可將MFR信號當(dāng)成依據(jù)某種特定文法產(chǎn)生的形式語言，從而利用文法分析技術(shù)對MFR參數(shù)和狀態(tài)進(jìn)行估計。

其中上下文無關(guān)文法（ContextFree Grammar， CFG）結(jié)構(gòu)簡單、表達(dá)能力強(qiáng)、描述性好[13]，因此可以利用CFG對MFR進(jìn)行建模。一個CFG是一個四元組G={V，N，R，S}，其中：V為非終結(jié)符的非空有窮集，表示雷達(dá)短語集合；N是終結(jié)符的非空有窮集，即雷達(dá)字集合，且N∩V=；R為產(chǎn)生式的非空有窮集，R中的元素具有形式A→λ，其中A∈V，λ∈（V∪N）+， A→λ被稱為產(chǎn)生式；S∈V，為文法G的開始符號。SCFG為CFG的擴(kuò)展，它是一個五元組GS={V，N，R，S，P}，P為CFG文法產(chǎn)生式的概率，且P必須滿足∑λP（A→λ）=1的約束條件[14]。

基于SCFG建模的RWR系統(tǒng)如圖1所示。基于SCFG建模的RWR系統(tǒng)首先利用MFR信號模擬器模擬多部交錯的雷達(dá)脈沖信號，通過接收機(jī)對雷達(dá)脈沖信號進(jìn)行截獲，脈沖序列中的脈沖描述字通過脈沖串分析器去交錯后，利用TOA模板庫進(jìn)行雷達(dá)字提取[15]。每一路雷達(dá)字通過序列識別模塊進(jìn)行MFR輻射源識別，每個SCFG模板對應(yīng)一部特定的MFR。在確定MFR類型之后，再進(jìn)行MFR文法概率快速學(xué)習(xí)，從而進(jìn)行MFR參數(shù)和狀態(tài)估計，最后進(jìn)行威脅估計和態(tài)勢分析，判定威脅等級，本文研究MFR文法概率快速學(xué)習(xí)的內(nèi)容。

2Earley算法描述

由文獻(xiàn)[15]可知，一個隨機(jī)文法GS從初始符S開始產(chǎn)生序列η∈Lg（Gs）的最左導(dǎo)出稱為η的派生過程。文法產(chǎn)生式序列的派生過程僅與文法結(jié)構(gòu)有關(guān)，而與文法概率參數(shù)無關(guān)，所以本文利用Earley算法對每個雷達(dá)數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)造能描述派生過程的剖析表，并從中提取出最優(yōu)剖析樹，以降低計算復(fù)雜度和減少運(yùn)行時間。

Earley算法是一種基于線圖的、兼具自頂向下和自底向上優(yōu)勢的句法剖析方法，可以在O（n3）時間內(nèi)處理任何上下文無關(guān)文法。它在剖析過程中加入了點(diǎn)規(guī)則[16]，所謂點(diǎn)規(guī)則，是在規(guī)則的右部的終結(jié)符或非終結(jié)符之間的某一位置上加上一個圓點(diǎn)，表示右部被匹配的程度，可以反映規(guī)則匹配的狀態(tài)，進(jìn)一步減少了規(guī)則匹配中的冗余操作。

約定下文中使用以下記號[17]：A，B，C，…代表任意非終結(jié)符；a，b，c，…代表任意終結(jié)符；α， β，γ，…代表由非終結(jié)符或終結(jié)符組成的任意序列。算法運(yùn)算過程中輸入符號串從左向右掃描，每讀入輸入符aj，分析器產(chǎn)生一個狀態(tài)集Sj。狀態(tài)集由形如[A→α·β，i]的分析項目組成，表示：

1）當(dāng)前參與匹配的產(chǎn)生式是A→αβ；

2）產(chǎn)生式右部的α已匹配，而β將被匹配；

3）已匹配部分在輸入串中的位置是i。

在構(gòu)造剖析表時，為了能正確地列出所有項目，要完成Earley算法的三個操作：首先進(jìn)行掃描運(yùn)算，再進(jìn)行完成運(yùn)算，最后進(jìn)行預(yù)測運(yùn)算，直到剖析表穩(wěn)定為止，這樣就可以不遺漏所有的狀態(tài)集[18]。

則A→BC兩種形式的產(chǎn)生式，A，B，C∈V，wj∈N，還是文法產(chǎn)生式結(jié)構(gòu)為任意形式的產(chǎn)生式，通過構(gòu)造Earley剖析表、加入點(diǎn)規(guī)則和反映規(guī)則匹配的狀態(tài)，能有效減少冗余操作，解決迭代過程中歧義產(chǎn)生式重復(fù)剖析、無效產(chǎn)生式重復(fù)剖析以及排除未參與派生過程的產(chǎn)生式等問題。所以將Earley算法應(yīng)用到MFR文法概率快速學(xué)習(xí)中，可以大大降低計算復(fù)雜度和減少運(yùn)行時間。

3MFR文法概率快速學(xué)習(xí)方法

由式（29）可得，E（IO）算法和E（VS）算法通過對截獲的雷達(dá)數(shù)據(jù)進(jìn)行預(yù)處理，分別構(gòu)造剖析表和最優(yōu)剖析樹，可以有效解決迭代過程中有歧義產(chǎn)生式重復(fù)剖析、無效產(chǎn)生式重復(fù)剖析以及排除未參與派生過程的產(chǎn)生式等問題，能夠大幅度降低IO算法和VS算法的計算復(fù)雜度。

4.2算法性能分析

為了驗證Earley剖析算法的正確性，本文利用上述“水星”MFR部分產(chǎn)生式進(jìn)行分析[20]，設(shè)計了兩個實驗。

4.2.1實驗一

實驗一通過改變訓(xùn)練序列個數(shù)和迭代次數(shù)，對算法的運(yùn)行時間進(jìn)行比較。假設(shè)“水星”MFR有兩個狀態(tài)，對應(yīng)隨機(jī)上下文無關(guān)文法G1和G2，根據(jù)上述“水星”MFR部分文法產(chǎn)生式，令非終結(jié)符V={S，ACQ，RR，NAT，S1，TM，RRP，W1，W2，W3，W4，W5}，終結(jié)符N=（w1，w2，w3，w4，w5），S為初始符。設(shè)狀態(tài)轉(zhuǎn)移矩陣A′=（0.8，0.2；0.3，0.7），先令A(yù)′的Markov鏈隨機(jī)產(chǎn)生一系列雷達(dá)狀態(tài)，再對文法參數(shù)進(jìn)行估計，最后經(jīng)過100次蒙特卡洛實驗，得到結(jié)果如圖4、5所示。

由圖4、5可知，隨著序列數(shù)和迭代次數(shù)的增加，算法的運(yùn)行時間逐漸增加，其中IO算法的運(yùn)行時間最長，VS算法相對于IO算法只對訓(xùn)練數(shù)據(jù)集最優(yōu)解進(jìn)行訓(xùn)練，運(yùn)行時間大大減少。E（IO）算法和E（VS）算法的運(yùn)行時間相比VS算法減小

了1/10以上，大大降低了算法的時間復(fù)雜度，實驗所得的MFR參數(shù)估計值符合理論分析。

4.2.2實驗二

實驗二通過對比四種算法在序列數(shù)和迭代次數(shù)增加時狀態(tài)估計精度的變化情況來判別算法性能。當(dāng)?shù)趎+1次迭代結(jié)果與第n次迭代結(jié)果的均方誤差和小于0.1%時結(jié)束迭代，完成概率參數(shù)估計，得到文法參數(shù)后，利用Viterbi算法對MFR狀態(tài)進(jìn)行估計。設(shè)狀態(tài)轉(zhuǎn)移初始概率矩陣為A′0=（0.9，0.1；0.1，0.9），經(jīng)過100次蒙特卡洛實驗，結(jié)果如圖6、7所示。

由圖6、7可以看出，隨著序列數(shù)和迭代次數(shù)的增加，狀態(tài)估計精度會越來越高，IO算法和E（IO）算法的狀態(tài)估計概率相同，而VS與E（VS）算法的狀態(tài)估計精度相同。這說明E（IO）和E（VS）算法在有效降低計算復(fù)雜度和減少運(yùn)行時間的前提下，始終可以保持狀態(tài)估計精度，驗證了Earley算法可以提高文法概率學(xué)習(xí)速度。

5結(jié)語

本文針對基于SCFG建模的MFR參數(shù)和狀態(tài)估計方法進(jìn)行研究，在原有IO算法和VS算法的基礎(chǔ)上，提出了E（IO）算法和E（VS）算法兩種MFR文法概率快速學(xué)習(xí)算法。E（IO）算法通過對截獲的雷達(dá)數(shù)據(jù)集進(jìn)行預(yù)處理，在派生過程中加入點(diǎn)規(guī)則，構(gòu)造Earley剖析表；E（VS）算法基于最大子樹概率準(zhǔn)則從剖析表中提取出最優(yōu)剖析樹。通過構(gòu)造剖析表和最優(yōu)剖析樹，E（IO）算法和E（VS）算法可以解決迭代過程中有歧義產(chǎn)生式重復(fù)剖析、無效產(chǎn)生式重復(fù)剖析以及能排除未參與派生過程的產(chǎn)生式等問題，有效進(jìn)行MFR參數(shù)估計。在得到文法參數(shù)后，利用Viterbi算法對MFR狀態(tài)進(jìn)行估計。通過理論分析和建模仿真表明，E（IO）算法和E（VS）算法在降低計算復(fù)雜度和減少運(yùn)行時間的同時，可以有效保持狀態(tài)估計精度，驗證了Earley算法可以提高文法概率學(xué)習(xí)速度。

參考文獻(xiàn)：

[1]

周帆，陳興凱，韓壯志，等.機(jī)載雷達(dá)告警接收機(jī)的現(xiàn)狀及技術(shù)發(fā)展趨勢[J].飛航導(dǎo)彈，2014（2）：41-46.（ZHOU F， CHEN X K， HAN Z Z， et al. Status and trends of the airborne radar warning receiver [J]. Aerodynamic Missile Journal， 2014（2）： 41-46.）

[2]

劉海軍.雷達(dá)輻射源識別關(guān)鍵技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2010：3-5. （LIU H J. Researches on identification key technology for radar emitter [D]. Changsha： National University of Defense Technology， 2010： 3-5.）

[3]

李健偉，劉璘，吳宏超，等.機(jī)載有源相控陣?yán)走_(dá)給告警器帶來的威脅[J].雷達(dá)與對抗，2014，34（2）：14-17.（LI J W， LIU L， WU H C， et al. Threats to radar warning receiver that airborne active phased array radars bring [J]. Radar & ECM， 2014， 34（2）： 14-17.）

[4]

WANG A， KRISHNAMURTHY V. Signal interpretation of multifunction radars： modeling and statistical signal processing with stochastic context free grammar [J]. IEEE Transactions on Signal Processing， 2008， 56（3）： 1106-1119.

[5]

VISNEVSKI N A. Syntactic modeling of muftifunction radars [D]. Hamilton： McMaster University， 2005： 8-10.

[6]

代鸝鵬，王布宏，沈海鷗，等.基于文法派生解析表的多功能雷達(dá)快速參數(shù)估計方法[J].電子學(xué)報，2016，44（2）：392-397.（DAI L P， WANG B H， SHEN H O， et al. Fast parameter estimation of multifunction radar based on syntactic of parse chart [J]. Chinese Journal of ElectronicsActa Electronica Sinica， 2016， 44（2）： 392-397.）

[7]

LARI K， YOUNG S J. The estimation of stochastic contextfree grammars using the insideoutside algorithm [J]. Computer Speech and Language， 1990， 4（1）： 35-56.

[8]

NEY H. Stochastic grammars and pattern recognition [M]// LAFACE P， DE MORI R. Speech Recognition and Understanding. Berlin： Springer， 1992， 75： 319-344.

[9]

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.

[10]

代鸝鵬，王布宏，蔡斌，等.基于SCFG建模的多功能雷達(dá)狀態(tài)估計算法[J].空軍工程大學(xué)學(xué)報（自然科學(xué)版），2014，15（3）：24-28.（DAI L P， WANG B H， CAI B， et al. A method for states estimation of multifunction radar based on stochastic contextfree grammar [J]. Journal of Air Force Engineering University （Natural Science Edition）， 2014， 15（3）： 24-28.）

[11]

EARLEY J. An efficient contextfree parsing algorithm [J]. Communications of the ACM， 1970， 13（2）： 94-102.

[12]

馬爽，柳征，姜文利.基于幅度變化點(diǎn)檢測的多功能雷達(dá)脈沖列解析方法[J].電子學(xué)報，2013，41（7）：1436-1441.（MA S， LIU Z， JIANG W L. A method for multifunction radar pulse train analysis based on amplitude change point detection [J]. Acta Electronica Sinica， 2013， 41（7）： 1436-1441.）

[13]

陸玲，周書民.形式語言與自動機(jī)及程序設(shè)計[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2014：11-16.（LU L， ZHOU S M. Formal Language， Automaton and Program Design [M]. Harbin： Harbin Institute of Technology Press， 2014： 11-16.）

[14]

GONZALEZ R C， MANNING G T. 句法模式識別[M].濮群，譯.北京：清華大學(xué)出版社，1984：84-88.（GONZALEZ R C， MANNING G T. Syntactic Pattern Recognition [M]. PU Q， translated. Beijing： Tsinghua University Press， 1984： 84-88.）

[15]

劉海軍，樊昀，李悅，等.多功能雷達(dá)建模中的雷達(dá)字提取技術(shù)研究[J].國防科技大學(xué)學(xué)報，2010，32（2）：91-96.（LIU H J， FAN S， LI Y， et al. Research on extracting of radar words in modeling of multifunction radar [J]. Journal of National University of Defense Technology， 2010， 32（2）： 91-96.）

[16]

韓習(xí)武，HAUSSER R.基于擴(kuò)展Viterbi路徑的概率Earley算法[J].計算機(jī)科學(xué)，2011，38（1）：207-209.（HAN X W， HAUSSER R. Probabilistic Earley algorithm based on extended Viterbi path [J]. Computer Science， 2011， 38（1）： 207-209.）

[17]

張磊. 基于關(guān)系代數(shù)的語法語義分析單元設(shè)計[D].大連：大連交通大學(xué)，2012：5-6.（ZHANG L. Syntactic analysis and syntaxdirected translation based on extended relational model [D]. Dalian： Dalian Jiaotong University， 2012： 5-6.）

[18]

唐建，趙川.基于Earley算法的英語句法剖析系統(tǒng)[J].數(shù)字通信，2013，40（1）：84-87.（TANG J， ZHAO C. English grammar parsing system based on Earley algorithm [J]. Digital Communication， 2013， 40（1）： 84-87.）

[19]

傅京孫.模式識別應(yīng)用[M].北京：北京大學(xué)出版社，1990：68-69.（FU J S. Application of Pattern Recognition [M]. Beijing： Beijing University Press， 1990： 68-69.）

[20]

吳曉降，李云鵬，李娜.基于SCFG的雷達(dá)信號處理中概率學(xué)習(xí)算法的研究[J].火控雷達(dá)技術(shù)，2015，44（2）：32-36.（WU X J， LI Y P， LI N. Study on algorithm of probabilities learning in radar signal processing based on SCFG [J]. Fire Control Radar Technology， 2015， 44（2）：32-36.）