基于最优解析树提取的多功能雷达状态快速估计方法

代鹂鹏,王布宏,曹　帅,沈海鸥

(空军工程大学信息与导航学院,陕西西安 710077)



基于最优解析树提取的多功能雷达状态快速估计方法

代鹂鹏,王布宏,曹帅,沈海鸥

(空军工程大学信息与导航学院,陕西西安 710077)

摘要：针对基于文法建模的多功能雷达(Multi-Function Radar,MFR)参数估计领域中常规算法具有的高运算复杂度问题,提出一种快速估计算法.该算法利用文法的派生过程仅与文法结构有关,而与文法概率参数无关这一事实,利用库克-杨-卡塞米(Cocke-Younger-Kasami,CYK)算法对截获雷达数据序列进行预处理,构造出可以反映该序列派生过程的解析表,进而从该解析表中提取出序列的最优解析树,然后利用改进的Viterbi-Score算法对雷达文法概率参数进行快速估计.论文仿真分析了该算法的计算复杂度、存储复杂度和估计精度,实验结果表明了该算法相对于常规算法,可以减少60%左右的计算量.

关键词:多功能雷达;随机上下文无关语法;解析表;解析树

1引言

电子支援系统(Electronic Support,ES)通过分析战场截获的雷达辐射源信号,向我方飞行员提供该辐射源所处的方位、状态和威胁等级等情报[1].对于传统的机械扫描雷达,ES系统可以通过分析辐射源信号的载频、脉宽等瞬时特性,采用参数类的统计方法便可实现有效告警[2].但对于多功能雷达(Multi-Function Radars,MFR)而言,由于MFR采用软件算法对波束进行控制,其波束扫描是无惯性的,且MFR采用了复杂多变的信号模式,使得MFR能够同时对多个目标进行操作.由于MFR的这些特性,基于参数类的威胁告警技术已无法满足MFR的建模需求[3].为了对MFR的这种多功能性、多工作模式进行有效描述,Nikita与Wang将Markov链与随机上下文无关文法(Stochastic Context-Free Grammars,SCFG)相结合,提出模式类的MFR建模方法[4],该方法将语言学中的知识引入到雷达信号处理领域,为今后的研究提供了新的思路.

给定能够描述MFR雷达动态行为的文法结构,如何利用截获的信号序列对MFR的文法概率参数进行估计是模式类ES系统面临一个关键问题.通常的方法是将期望最大化算法(Expectation-Maximization,EM)应用于语言学中的Inside-Outside(IO)算法[5]和Viterbi-Score(VS)算法[6]对概率参数进行迭代求精,但是这两种方法的收敛速度和计算复杂度均无法满足ES系统的实时性要求.文献[7]针对上述问题,提出gEM(IO)和gEM(VS)算法,但这两种算法只针对单个文法的训练,无法对多个文法进行并行训练.本文将解析表应用于VS算法,提出P(VS)算法对多个雷达文法的参数进行并行快速估计,并通过理论分析与仿真实验证明P(VS)算法相对于IO、VS和基于解析表的IO算法(P(IO)),可以有效降低运算复杂度.

2MFR雷达的系统结构分析

MFR通过软件程序对任务进行调度,并将每一种任务映射为基本的脉冲波形进行发射,每个基本脉冲波形称为一个雷达字,雷达字为MFR的最小辐射单元[8].由此可见,MFR为了满足不同的功能需求而使用了分层的信号结构,因此可利用分层的雷达信号结构模型对MFR进行建模.该方法首先将雷达的状态转换视为随机离散事件,雷达在每个状态采用特定的随机形式语言交流信息,然后在电子情报基础上利用能够捕获MFR复杂信号特征的文法对该语言进行建模,将每一部MFR在威胁数据库中对应一个文法语言模型,最后利用机器翻译和解码技术对雷达状态进行解析.

MFR依据自身所处的战术环境选择雷达需要执行的任务状态,然后将该任务状态通过映射机制转换为雷达字序列,最后将该雷达字序列映射为相应的脉冲序列进行发射.因此,雷达状态选择机制为一个Markov过程,即在每个MFR周期选择一个合适的任务状态ei,并依据状态ei所定义的调度规则对雷达字进行调度[9].从ESM系统角度来讲,雷达内部工作机制是未知的,因此将每一次调度行为建模为概率性事件,概率值大小代表雷达的资源分配方案.

利用SCFG对其调度方式建模,可得到MFR的信号产生机制如图1所示.该建模方法利用马尔科夫链描述雷达状态的动态转移情况,利用SCFG描述MFR产生雷达信号的调度机制.

对于CFG而言,其产生的终止符序列η可观测得到,但是产生η的具体过程无法直观得到.由文献[11]可知,文法产生η的派生过程仅与文法结构有关,而与文法的概率值无关,因此可以利用CYK算法[12]或Early算法[13]对每个序列η进行预处理,构造可以精确描述该派生过程的解析表,并从中提取出最优解析树,在概率重估时,只有最优解析树参与重估过程,从而减少算法计算复杂度(计算复杂度定义为对一个训练序列进行一次迭代所需要的乘法和除法运算次数).

3基于解析表的MFR参数快速估计算法

3.1CYK图表解析算法

对序列η进行分析,意味着需要确定一个文法导出η的产生式序列.CYK算法作为一种描述性算法,已应用于语音识别领域.CYK算法要求所处理的文法产生式为A→w或者A→BC两种结构[14],其中A,B,C∈V,w∈N.根据不同的产生式定义不同的子树结构来确定η的子序列母节点,其中产生式A→a对应的子树结构为A(j,j)→a,表示wj=a,且A→wj∈R.产生式A→BC对应的子树结构为A(i,j)→B(i,k)C(k+1,j),表示文法以A为母节点产生子序列wiwi+1…wj,在该子序列中,wiwi+1…wk以B为母节点,wk+1…wj以C为母节点,且A→BC∈R.

对于给定的长度为L的序列,解析表T是一个三角形表,每个表中第i行第j列的参数为T(i,j),其中1≤i≤L,1≤j≤L+1-i.对于η的某个子串,若有A⟹wiwi+1…wj,则把A(i,j)→…存入T(i,j)中.在构造出解析表后,当且仅当S(1,L)→…存在于T(1,L)中时,η∈Lg(Gs),且可从该解析表中抽取出该序列的最左导出.

对于序列η=w1w2…wL,可以从左到右、从最高行到最低行顺次构造解析表.由于G必须符合Chomsky正则形式表示,使得我们能按照下列步骤对η构造此解析表:

步骤1按照i=1到i=L的次序求T(i,i),若R中存在产生式A→wi时,将A(i,i)→wi填入T(i,i).

步骤2假设对1≤i≤L已经求出T(i,j-1),现在求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重复第二步直至完成此表或表的整行都是空项.

通过对每个序列提前构造解析表可以发现,解析表中的子树结构参数描述了文法产生η的所有派生过程,我们可在算法每次迭代过程中利用解析表排除不参与派生的参数,从而可以减少计算量.

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

令x1:m=(x1,x2,…,xm)为MFR状态序列,xk∈Nr.η1:m=(η1,η2,…,ηm)表示截获得到的MFR产生的m个终结符序列,其中ηi=w1w2…wLi,Li表示ηi的长度.为了对文法进行解析,首先引入内部概率αA(i,j)=P(wij|A,Gs),该概率表示Gs从非终结符A开始,生成终结符序列wiwi+1…wj的概率.

(1)

对于每个母节点为A(i,j)(i

(2)

因此,母节点A(i,j)对应的最大内部概率为所有以A(i,j)为母节点的子树分支概率的最大值:

(3)

对于每个母节点A(i,j),使得式(3)最大的子树分支称为最优子树分支,定义为:

(4)

令Φ保存每个最优子树的路径,即:

(5)

步骤3概率重估.在得到文法产生每个序列的产生式期望使用次数以后,文法产生式的概率便可估计为:

(6)

其中ξt(i,j)=P(xt=ei,xt+1=ej|η1:m)表示在t时刻MFR处于ei状态,t+1时刻处于ej状态的概率.χt(i,j)=P(xt=ei|η1:m)表示MFR在t时刻处于状态ei的概率.则雷达管理模块对应的Markov链状态转移概率可估计为:

(7)

通过上述步骤进行迭代计算,直至文法概率参数变化非常小时结束.每经过一次迭代,模型对于给定观测数据的似然性都会增加,这样就保证了每次迭代都会产生更优的模型参数.通过P(VS)算法得到文法的概率参数后,便可利用Viterbi算法对MFR所处状态进行估计[15].

4算法分析与仿真

为了验证本文的算法,我们首先对四种算法的计算复杂度进行理论分析,并利用表1所示文法进行仿真验证.在该文法基础上,我们设计两个实验:第一个实验对算法时间复杂度进行分析.第二个实验对算法的收敛时间和精度进行分析.

4.1算法资源分析

为了对算法资源进行理论分析,首先定义以下变量:L表示训练序列的平均长度;Mt表示辐射规则的数目;Mtm表示文法终结符的数目;Mnt表示文法非终结符的数目;|φt|表示解析表中转移规则的平均数;|Δe|表示解析表中辐射规则的平均数;|Δlt|表示解析表中每个转移规则对应的平均子树的个数;|Δle|表示左部参数相同的辐射规则平均数.由于算法在产生式概率均匀分布时计算复杂度最大,则在该条件下有:

(8)

|φe|=Mnt·L

(9)

(10)

则对于IO算法而言,其计算复杂度TIO为:

(11)

对于VS算法而言,其计算复杂度TVS为:

(12)

对于P(IO)算法,其平均计算复杂度TP(IO)为:

(13)

对于P(VS)算法,其平均计算复杂度TP(VS)为:

(14)

定义算法对一个序列进行一次迭代时需要存储的参数个数为算法的存储复杂度.因此,IO算法的存储复杂度MIO为:

(15)

VS算法的存储复杂度MVS为:

(16)

由于P(IO)与P(VS)算法在对训练进行预处理时,需对解析表进行存储,对于长度为L的序列,其解析表需要存储的参数个数为:

(17)

因此,于P(IO)与P(VS)算法的存储复杂度分别为:

MP(IO)=MIO+MCYK

(18)

MP(VS)=MVS+MCYK

(19)

参数|φt|和|Δlt|反应了文法的模糊性,因此P(IO)和P(VS)的平均计算复杂度与文法固有的模糊性具有很大关联.文献[4]中所描述的“水星”MFR部分文法产生式为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.由该文法产生序列构造的解析表中,|Δlt|max=3,将其带入上面各式,可得到不同序列长度与不同算法的计算复杂度、存储复杂度比较结果,如图2与图3所示.

4.2算法时间复杂度分析

假设MFR有两个状态,分别对应文法G(1)和G(2),由状态转移矩阵为A=(0.7,0.3;0.4,0.6)的Markov链随机产生50个雷达状态,每个状态依据文法G(1)或G(2)随机产生一个终结符序列,然后对产生式概率和状态转移概率进行估计.经过100次Monte Carlo实验,得到算法实验结果如图4和图5所示.

算法的计算复杂度反应到程序中,便为程序的运行时间,我们通过不同迭代次数、不同序列个数与算法的运行时间进行验证.由图4和图5可知,随着迭代次数和训练序列的增加,IO算法的运行时间也急剧增加,这导致了其在实际应用中具有局限性.VS算法只对最大解析树进行求解,算法对序列进行一次迭代运行时间比IO算法减少一半左右.P(IO)与P(VS)算法对训练序列进行了预处理,其中,P(IO)算法对解析表中的所有路径求解,P(VS)算法只对解析表定义的最优解析树求解,其算法运行时间比IO与VS算法降低了一半以上,且实验值可以很好的符合理论分析.

4.3算法性能分析

该实验通过对比IO、VS、P(IO)和P(VS)算法收敛后的估计结果与真实值的误差平方和与MFR状态估计概率来判别算法性能.定义第n+1次迭代结果和第n次迭代结果的误差平方和小于0.001时结束.经过100次Monte Carlo实验,结果如图6、7所示.

由图6可知,四种算法随着迭代次数的增加,其估计值与真实值的误差会逐渐降低,趋于收敛时,P(IO)和IO算法的估计误差相同,而VS与P(VS)算法的估计误差值始终比P(IO)和IO算法大0.4左右.文法概率参数的估计精度会影响到最终MFR状态的估计,不同迭代次数与MFR状态估计结果如图7所示,由图可知,IO算法的与P(IO)算法在收敛后的状态估计概率在0.91左右,而VS与P(VS)算法的估计概率为0.94左右.

5结论

本文针对基于SCFG建模的MFR参数快速估计算法进行研究,提出一种基于解析表的参数估计算法.该算法通过CYK解析算法对截获的训练序列集预先构造解析表,在序列集解析表的基础上排除未参与序列派生过程的产生式,并寻找出最优解析树,且只有最优解析树参与重估过程,大大的减少了算法复杂度.本文通过理论分析与试验仿真证明,该方法在减少运算量的同时,可以确保其精度与IO、P(IO)算法大致相同,在ES系统的实际应用中具有重要意义,如何减少该算法的存储需求,是下一步的研究方向之一.

参考文献

[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]刘海军.雷达辐射源识别关键技术研究[D].长沙:国防科学技术大学,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.统计自然语言处理基础[M].范春法,等,译.北京:电子工业出版社,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].哈尔滨:哈尔滨工业大学出版社,2014,11-16.

[15]代鹂鹏,王布宏,蔡斌,刘军利.基于SCFG建模的多功能雷达状态估计算法[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月出生于甘肃省平凉市.现为空军工程大学信息与导航学院硕士研究生.主要研究方向为多功能雷达信号处理.

E-mail:dlipeng@163.com

王布宏男,1975年12月出生于山西省太原市.现为空军工程大学教授、博士生导师.主要从事阵列信号处理、阵列校正等方面的研究工作.

E-mail:wbhyl@aliyun.com

曹帅男,1991年11月出生于陕西省西安市.现为空军工程大学信息与导航学院硕士研究生.主要研究方向为阵列信号处理.

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;责任编辑:覃怀银