基于Earley算法的多功能雷达文法概率快速学习算法

doi:10.11772/j.issn.1001-9081.2016.09.2636

计算机应用 ›› 2016, Vol. 36 ›› Issue (9): 2636-2641.DOI: 10.11772/j.issn.1001-9081.2016.09.2636

基于Earley算法的多功能雷达文法概率快速学习算法

曹帅, 王布宏, 刘新波, 沈海鸥

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

收稿日期:2016-01-25 修回日期:2016-03-08 出版日期:2016-09-10 发布日期:2016-09-08
通讯作者: 曹帅
作者简介:曹帅(1991-),男,陕西西安人,硕士研究生,主要研究方向:多功能雷达告警、句法模式识别;王布宏(1975-),男,山西太原人,教授,博士生导师,博士,主要研究方向:阵列信号处理、网络对抗、多功能雷达告警;刘新波(1984-),男,河南洛阳人,博士研究生,主要研究方向:网络对抗;沈海鸥(1990-),女,甘肃兰州人,博士研究生,主要研究方向:阵列信号处理。
基金资助:
国家自然科学基金资助项目（61172148）；航空基金资助项目（20112090616）。

Fast learning algorithm of grammatical probabilities in multi-function radars based on Earley algorithm

CAO Shuai, WANG Buhong, LIU Xinbo, SHEN Haiou

College of Information and Navigation, Air Force Engineering University, Xi'an Shaanxi 710077, China

Received:2016-01-25 Revised:2016-03-08 Online:2016-09-10 Published:2016-09-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61172148) and the Aviation Foundation of China (20112090616).

摘要/Abstract

摘要： 针对基于随机上下文无关文法（SCFG）建模的多功能雷达（MFR）概率学习问题，在传统Inside-Outside（IO）算法和Viterbi-Score（VS）算法的基础上，提出一种基于Earley算法的多功能雷达文法概率快速学习算法。该算法通过对截获的雷达数据进行预处理，构造可以反映派生过程的Earley剖析表，并且基于最大子树概率原则从剖析表中提取出最优剖析树，利用改进的IO算法和改进的VS算法对文法概率进行学习，实现MFR参数估计，得到文法参数后，再利用Viterbi算法对MFR状态进行估计。理论分析和实验仿真表明，与IO算法和VS算法相比，改进算法在保持估计精度的同时，可以有效降低计算复杂度和减少运行时间，验证了Earley算法能够提高文法概率的学习速度。

关键词: 随机上下文无关文法, 多功能雷达, Earley算法, 参数估计, 状态估计

Abstract: To deal with the probability learning problem in Multi-Function Radar (MFR) based on Stochastic Context-Free Grammar (SCFG) model, a new fast learning algorithm of grammatical probabilities in MFR based on Earley algorithm was presented on the basis of traditional Inside-Outside (IO) algorithm and Viterbi-Score (VS) algorithm. The intercepted radar data was pre-processed 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 sub-tree 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 Context-Free Grammar (SCFG), Multi-Function Radar (MFR), Earley algorithm, parameter estimation, state estimation

中图分类号:

U416.216

曹帅, 王布宏, 刘新波, 沈海鸥. 基于Earley算法的多功能雷达文法概率快速学习算法[J]. 计算机应用, 2016, 36(9): 2636-2641.

CAO Shuai, WANG Buhong, LIU Xinbo, SHEN Haiou. Fast learning algorithm of grammatical probabilities in multi-function radars based on Earley algorithm[J]. Journal of Computer Applications, 2016, 36(9): 2636-2641.

参考文献

[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 mufti-function 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 multi-function radar based on syntactic of parse chart [J]. Acta Electronica Sinica, 2016, 44(2): 392-397.)
[7] LARI K, YOUNG S J. The estimation of stochastic context-free grammars using the inside-outside 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 multi-function radar based on stochastic context-free grammar [J]. Journal of Air Force Engineering University (Natural Science Edition), 2014, 15(3): 24-28.)
[11] EARLEY J. An efficient context-free 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 multi-function 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 syntax-directed 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.)

基于Earley算法的多功能雷达文法概率快速学习算法

Fast learning algorithm of grammatical probabilities in multi-function radars based on Earley algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	欧跃发, 杨鸣坤, 慕德俊, 柯捷, 马文涛. 基于广义最大Versoria准则的稀疏自适应滤波算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3325-3331.
[2]	徐星辰, 程剑, 唐璟宇, 张剑. 非对称成对载波多址信号的相位误差分析及幅度改进算法[J]. 计算机应用, 2019, 39(4): 1138-1144.
[3]	王波, 刘德亮. 基于迭代自适应方法的近场源二维参数联合估计[J]. 计算机应用, 2019, 39(2): 523-527.
[4]	汤启, 何腊梅. 带非线性等式约束无迹卡尔曼滤波方法[J]. 计算机应用, 2018, 38(5): 1481-1487.
[5]	游路瑶, 黄庆卿, 段斯静. 基于卡尔曼滤波估计的一致性时钟同步算法[J]. 计算机应用, 2017, 37(8): 2177-2183.
[6]	田继伟, 王布宏, 尚福特. 基于鲁棒主成分分析的智能电网虚假数据注入攻击[J]. 计算机应用, 2017, 37(7): 1943-1947.
[7]	曹帅, 王布宏, 李龙军, 刘帅琦. 基于随机无穷自动机的多功能雷达辐射源识别方法[J]. 计算机应用, 2017, 37(2): 608-612.
[8]	王董礼, 曹鹏, 黄国策, 孙启禄, 李连宝. 基于隐马尔可夫模型的短波认知频率选择方法[J]. 计算机应用, 2016, 36(5): 1179-1182.
[9]	吴章平, 刘本永. 基于灰度平均梯度和粒子群优化的散焦图像模糊参数估计[J]. 计算机应用, 2016, 36(4): 1111-1114.
[10]	王思秀, 徐舟, 汪晓洁, 汪江桦. 基于部分相关的LFM脉冲全参数估计[J]. 计算机应用, 2016, 36(10): 2927-2932.
[11]	杨陟卓. 基于上下文语境的词义消歧方法[J]. 计算机应用, 2015, 35(4): 1006-1008.
[12]	刘德亮, 刘开华, 于洁潇, 张良, 赵阳. 短快拍条件下宽带chirp信号的波达方向估计[J]. 计算机应用, 2015, 35(2): 351-353.
[13]	赵永历仲恒李定远胡涛. 基于行列式比的阶次和参数同步递推辨识算法[J]. 计算机应用, 2014, 34(2): 538-541.
[14]	丁盛. 基于辅助模型和数据滤波的伪线性回归系统参数估计方法[J]. 计算机应用, 2014, 34(1): 236-238.
[15]	王蕾陈进东潘丰. 引力搜索算法在青霉素发酵模型参数估计中的应用[J]. 计算机应用, 2013, 33(11): 3296-3299.