基于Earley算法的多功能雷達文法概率快速學習算法

曹帥　王布宏　劉新波　沈海鷗

摘要：

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

關鍵詞：

隨機上下文無關文法；多功能雷達；文法概率快速學習算法【只是本文提出的算法吧；Earley算法；參數估計；狀態估計

中圖分類號：

U416.216

文獻標志碼：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.

英文關鍵詞Key words：

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

0引言

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

在MFR文法建模的基礎上，利用截獲的雷達數據對文法產生式概率進行學習[6]，對MFR參數和狀態進行估計是模式類雷達告警技術中的核心問題。IO（InsideOutside）算法[7]和VS（ViterbiScore）算法[8]是兩種常見的參數估計方法，文獻[9]將期望最大化（ExpectationMaximization， EM）算法應用到IO算法和VS算法中對文法產生式概率進行學習，實現對

MFR參數的估計，在得到文法參數后，再利用Viterbi算法實現對MFR狀態的

估計[10]。IO算法通過尋求訓練數據集的全局最大似然對文法產生式概率進行學習，計算量較大；而VS算法只尋求訓練數據集的全局最優解的最大似然對文法產生式概率進行學習，相對于IO算法，雖然減小了計算量，但卻犧牲了精度，所以這兩種算法都無法滿足RWR系統的實用需要。

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

1MFR文法建模

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

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

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

2Earley算法描述

由文獻[15]可知，一個隨機文法GS從初始符S開始產生序列η∈Lg（Gs）的最左導出稱為η的派生過程。文法產生式序列的派生過程僅與文法結構有關，而與文法概率參數無關，所以本文利用Earley算法對每個雷達數據進行預處理，構造能描述派生過程的剖析表，并從中提取出最優剖析樹，以降低計算復雜度和減少運行時間。

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

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

1）當前參與匹配的產生式是A→αβ；

2）產生式右部的α已匹配，而β將被匹配；

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

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

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

3MFR文法概率快速學習方法

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

4.2算法性能分析

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

4.2.1實驗一

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

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

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

4.2.2實驗二

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

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

5結語

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

參考文獻：

[1]

周帆，陳興凱，韓壯志，等.機載雷達告警接收機的現狀及技術發展趨勢[J].飛航導彈，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].長沙：國防科學技術大學，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].雷達與對抗，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]

代鸝鵬，王布宏，沈海鷗，等.基于文法派生解析表的多功能雷達快速參數估計方法[J].電子學報，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建模的多功能雷達狀態估計算法[J].空軍工程大學學報（自然科學版），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]

馬爽，柳征，姜文利.基于幅度變化點檢測的多功能雷達脈沖列解析方法[J].電子學報，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]

陸玲，周書民.形式語言與自動機及程序設計[M].哈爾濱：哈爾濱工業大學出版社，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].濮群，譯.北京：清華大學出版社，1984：84-88.（GONZALEZ R C， MANNING G T. Syntactic Pattern Recognition [M]. PU Q， translated. Beijing： Tsinghua University Press， 1984： 84-88.）

[15]

劉海軍，樊昀，李悅，等.多功能雷達建模中的雷達字提取技術研究[J].國防科技大學學報，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]

韓習武，HAUSSER R.基于擴展Viterbi路徑的概率Earley算法[J].計算機科學，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]

張磊. 基于關系代數的語法語義分析單元設計[D].大連：大連交通大學，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算法的英語句法剖析系統[J].數字通信，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]

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

[20]

吳曉降，李云鵬，李娜.基于SCFG的雷達信號處理中概率學習算法的研究[J].火控雷達技術，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.）