Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (9): 2636-2641.DOI: 10.11772/j.issn.1001-9081.2016.09.2636

Previous Articles     Next Articles

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

CAO Shuai, WANG Buhong, LIU Xinbo, SHEN Haiou   

  1. 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).

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

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

  1. 空军工程大学 信息与导航学院, 西安 710077
  • 通讯作者: 曹帅
  • 作者简介:曹帅(1991-),男,陕西西安人,硕士研究生,主要研究方向:多功能雷达告警、句法模式识别;王布宏(1975-),男,山西太原人,教授,博士生导师,博士,主要研究方向:阵列信号处理、网络对抗、多功能雷达告警;刘新波(1984-),男,河南洛阳人,博士研究生,主要研究方向:网络对抗;沈海鸥(1990-),女,甘肃兰州人,博士研究生,主要研究方向:阵列信号处理。
  • 基金资助:
    国家自然科学基金资助项目(61172148);航空基金资助项目(20112090616)。

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

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

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

CLC Number: