Fast incremental learning of stochastic context-free grammars in radar electronic support

Latombe, Guillaume (2006). Fast incremental learning of stochastic context-free grammars in radar electronic support. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (7MB) | Prévisualisation

Résumé

Radar Electronic Support (ES) involves the passive search for, interception, location, analysis and identification of radiated electromagnetic energy for military purposes. Although Stochastic Context-Free Grammars (SCFGs) appear promising for recognition of radar emitters, and for estimation of their respective level of threat in radar ES systems, the computations associated with well-known techniques for learning their production rule probabilities are very computationally demanding. The most popular methods for this task are the Inside-Outside (IO) algorithm, which maximizes the likelihood of a data set,and the Viterbi Score (VS) algorithm, which maximizes the likelihood of its best parse trees. For each iteration, their time complexity is cubic with the length of sequences in the training set and with the number of non-terminal symbols in the grammar. Since applications of radar ES require timely protection against threats, fast techniques for learning SCFGs probabilities are needed. Moreover, in radar ES applications, new information from a battlefield or other sources often becomes available at different points in time. In order to rapidly refiect changes in operational environments, fast incremental learning of SCFG probabilities is therefore an undisputed asset.

Several techniques have been developed to accelerate the computation of production rules probabilities of SCFGs. In the first part of this thesis, three fast alternatives, called graphical EM (gEM), Tree Scanning (TS) and HOLA, are compared from several perspectives - perplexity, state estimation, ability to detect MFRs, time and memory complexity, and convergence time. Estimation of the average-case and worst-case execution time and storage requirements allows for the assessment of complexity, while computer simulations, performed using radar pulse data, facilitates the assessment of the other performance measures. An experimental protocol has been defined such that the impact on performance of factors like training set size and level of ambiguity of grammars may be observed. In addition, since VS is known to have a lower overall computational cost in practice, VS versions of the original 10-based gEM and TS have also been proposed and compared. Results indicate that both gEM(IO) and TS(IO) provide the same level of accuracy, yet the resource requirements mostly vary as a function of the ambiguity of the grammars. Furthermore, for a similar quality in results, the gEM(VS) and TS(VS) techniques provide significantly lower convergence times and time complexities per iteration in practice than do gEM(IO) and TS(IO). All of these algorithms may provide a greater level of accuracy than HOLA, yet their computational complexity may be orders of magnitude higher. Finally, HOLA is an on-line technique that naturally allows for incremental learning of production rule probabilities.

In the second part of this thesis, two new incremental versions of gEM, called Incremental gEM (igEM) and On-Line Incremental gEM (oigEM), are proposed and compared to HOLA. They allow for a SCFG to efficiently learn new training sequences incrementally, without retraining from the start an all training data. An experimental protocol has been defined such that the impact on performance of factors like the size of new data blocks for incremental learning, and the level of ambiguity of MFR grammars, may be observed. Results indicate that, unlike HOLA, incremental learning of training data blocks with igEM
and oigEM provides the same level of accuracy as learning from all cumulative data from scratch, even for relatively small data blocks. As expected, incremental leaming significantly reduces the overall time and memory complexities associated with updating SCFG probabilities. Finally, it appears that while the computational complexity and memory requirements of igEM and oigEM may be greater than that of HOLA, they both provide the higher level of accuracy.

Titre traduit

Apprentissage incrémental rapide de grammaires stochastiques à contexte libre dans le soutient électronique radar

Résumé traduit

Le Soutien Électronique radar, ou "radar Electronic Support" (ES) en Anglais, comprend la recherche passive, l'interception, la localisation, l'analyse et l'identification d'énergie électromagnétique irradiée à des fins militaires. Bien que les Grammaires Stochastiques à Contexte Libre, ou "Stochastic Context-Free Grammars" (SCFGs) en Anglais, semblent prometteuses pour la reconnaissance d'émetteurs radars, et l'estimation de leur niveau de menace dans les systèmes ES radars, les techniques populaires pour l'apprentissage de leurs règles de production sont très coûteuses en terme de calculs. Les méthodes les plus populaires pour cette tâche sont l'algorithme Inside-Outside (IO), qui maximise la vraisemblance d'un ensemble de données, et l'algorithme Viterbi Score (VS), qui maximise la vraisemblance des meilleurs arbres de dérivation. Pour chaque itération, leur complexité temporelle est cubique par rapport à la taille des séquences de l'ensemble d'entraînement et au nombre de symboles non-terminaux de la grammaire. Comme les applications ES radars nécessitent une protection rapide contre les menaces, des techniques accélérant l'apprentissage des probabilités de SCFGs sont nécessaires. De plus, dans les applications ES radar, de nouvelles informations du champs de bataille ou d'autres sources sont souvent accessibles à des moments différents. Afin de refléter rapidement les changements dans un environnement opérationel, des techniques incrémentales rapides permettant de mettre à jour les probabilités d'une SCFG seraient un avantage capital.

Plusieurs techniques ont été développées afin d'accélérer le calcul des probabilités des règles de production. Dans la première partie de ce mémoire, trois approches rapides, appelées graphical EM (gEM), Tree Scanning (TS) et HOLA, sont comparées sous plusieurs points de vue - perplexité, estimation des états, capacité à détecter des MFRs, complexité temporelle et mémorielle, et temps de convergence. L'estimation du temps d'exécution moyen, du temps d'exécution extrême et des nécessités de stockage permettent d'évaluer la complexité, alors que des simulations informatiques, exécutées à l'aide de données représentant des impulsions radar, permettent d'évaluer les autres mesures de performance. Un protocole expérimental a été défini, de telle manière que l'impact de facteurs tels que la taille de l'ensemble d'entraînement et le degré d'ambiguité puisse être évalué. De plus, puisque VS est connu pour avoir un temps de calcul global plus court en pratique, des variantes VS de gEM et TS sont également proposées et comparées. Les résultats indiquent que gEM(IO) et TS(IO) donnent presque les mêmes résulats en terme de qualité, bien que les ressources requises varient en fonction de l'ambiguité des grammaires. De plus, bien qu'elles aient des résultats similaires en terme de qualité, les techniques gEM(VS) et TS(VS) procurent un temps de convergence et une complexité temporelle significativement plus faibles en pratique que gEM(IO) et TS(IO). Bien que tous ces algorithmes donnent un meilleur niveau de précision que HOLA, leur complexité de calcul est plus importante. Enfin, HOLA est une technique en ligne qui permet naturellement l'apprentissage incrémental des probabilités.

Dans la seconde partie de ce mémoire, deux nouvelles versions incrémentales de gEM, appelées Incremental gEM (igEM) et On-Line Incremental EM (oigEM), sont proposées et comparées à HOLA. Elles permettent aux SCFGs d'apprendre de nouvelles séquences d'entraînement de façon incrémentale, sans avoir à ré-entraîner depuis le début sur toutes les données d'entraînement. Un protocole expérimental a été défini afin d'observer l'impact sur les performances de facteurs tels que la taille des nouveaux blocs de données pour l'apprentissage incrémental et le degré d'ambiguïté des grammaires de RMFs. Les résultats indiquent que, contrairement à HOLA, l'apprentissage incrémental de blocs de données d'entraînement avec igEM et oigEM procurent le même niveau de précision que l'apprentissage sur toutes les données cumulées depuis le départ, et ce même pour des blocs de données relativement petits. Il a été observé que l'apprentissage incrémental diminue de façon significative les complexités temporelles et mémorielles globales associées à la mise à jour des probabilités des SCFG. Enfin, il apparaît que bien que les complexités temporelle et mémorielle de igEm et oigEM soient plus élevées que HOLA, ils procurent tous les deux un meilleur niveau de précision.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"A thesis presented to the École de technologie supérieure in partial fulfillment of the thesis requirement for the degree of masters in automated manufacturing engineering". Bibliogr.: f. [193]-199. Ch. 1. Introduction -- Ch. 2. Grammatical modeling in radar ES -- Ch. 3. A survey of techniques for fast learning of production rule probabilities -- Ch. 4. Incremental derivations of graphical EM -- Ch. 5. Experimental methodology -- Ch. 6. Results and discussions -- Ch. 7. Conclusion -- Ch. 8. Recommendations.
Mots-clés libres:	Apprentissage, Approche, Contexte, Electronique, ES, Grammaire, Incremental, Libre, Radar, Rapide, Soutien, Stochastique, Version
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Granger, Éric
Programme:	Maîtrise en ingénierie > Génie de la production automatisée
Date de dépôt:	14 mars 2011 20:41
Dernière modification:	06 déc. 2016 22:35
URI:	https://espace.etsmtl.ca/id/eprint/527

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt