Fast learning of grammatical probabilities in radar electronic support


  1. Latombe, G.
  2. Granger, E.
  3. Dilkes, F.A.
Corporate Authors
Defence R&D Canada - Ottawa, Ottawa ONT (CAN)
Although Stochastic Context-Free Grammars appear promising for the recognition and threat assessment of complex radar emitters, the computational requirements for learning their production rule probabilities can be onerous. The two most popular methods, the Inside-Outside (IO) algorithm and the Viterbi Score (VS) algorithm, are both iterative. Although VS has lower overall computational costs in practice, both algorithms can be impractical for complex grammatical models. Several techniques have been previously developed to accelerate the learning. Two fast implementations of the traditional Inside-Outside algorithm, known as graphical Expectation-Maximization (gEM(IO)) and Tree-Scanning (TS(IO)), are reviewed in this paper, along with a third technique called HOLA. In addition, two novel algorithms are proposed that apply the graphical Expectation-Maximization (gEM(VS)) and Tree-Scanning (TS(VS)) principles to the Viterbi technique. An experimental protocol is defined and implemented so that the performance of all five techniques (gEM(IO), TS(IO), gEM(VS), TS(VS) and HOLA) can be compared using simulated training sets of complex radar signals. Several performance measures are used to evaluate the techniques including perplexity (the likelihood of a test data set), error rate on estimated states, time complexity per iteration, memory complexity per iteration, and convergence time. Estimation of the average-case and worst-case execution time and storage requirements allows for

Il y a un résumé en français ici.

Context Free Grammars;Electronic Support;Electronic Warfare;Expectation-Maximization;Multi-Function Radar;Stochastic Context-Free Grammar;Emitter identification;Emitter classification
Report Number
DRDC-OTTAWA-TM-2009-053 — Technical Memorandum
Date of publication
01 Jun 2009
Number of Pages
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: