E-Locus - Institutional Repository of the University of Crete - Επαγωγή γραμματικής ελεύθερης συμφραζομένων από παρατήρηση δομημένων χρονικών διαδικασιών

Home Επαγωγή γραμματικής ελεύθερης συμφραζομένων από παρατήρηση δομημένων χρονικών διαδικασιών

Results - Details

[Add to Basket]

Identifier

000345389

Title

Επαγωγή γραμματικής ελεύθερης συμφραζομένων από παρατήρηση δομημένων χρονικών διαδικασιών

Author

Κυριαζής, Νικόλαος

Abstract

The aim of this work is to propose methods that enable a computational system to develop compact representations of structured temporal processes. A structured temporal process is a process the evolution of which is determined by temporal rules and constraints. Exemplar structured temporal processes include speech, as it is observed via an acoustic signal, written text, being observed as a string of characters and the motion of a human, that is observed as the relative movement of body parts in an image sequence. The compact representation of such a process amounts to the inference of its structure through the observation of a finite set of examples. The ability to represent compactly observations, is exceptionally useful for systems that aim in the systematic organization of their knowledge.
In the present work, the understanding of a structured temporal process is achieved through the induction of a context free grammar, from observations of this process. The observations are converted into strings. A noise model is assumed, that possibly corrupts ideal input strings with insertions, deletions and replacements of symbols.
The assumption for a known noise model, enables the definition of an iterative grammar induction method that works incrementally, considering a single observation at a time. At each point in time, the grammar is guaranteed to recognize all past observations. For every new observation, the grammar's ability to recognize it is examined. If the grammar fails to recognize the observation, it is appropriately augmented so as to be able to recognize the last observation as well. Grammar augmentation is controlled by a cost function, that favors the minimum possible augmentation. The optimization of this function is achieved by means of two basic tools, the Viterbi algorithm, in conjunction with the Levenshtein algorithm, and Markov Random Fields.
The proposed grammar induction method is experimentally evaluated in terms of its effectiveness and computational efficiency based on synthetic grammars and the definition of specific grammar distance criteria. Finally, the emerging conclusions from this experimental evaluation are presented, possible improvements are identified and potential subjects of future research are highlighted.

Physical description

xxiv, 179 σ. : εικ. ; 30 cm.

Language

Greek

Issue date

2009-04-02

Collection

School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses

Type of Work--Post-graduate theses

Views

503

Digital Documents
	Download document View document Views : 5