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

RDF 

 
This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share



Semantic enrichment/homogenization by EKT
2009 (EN)
Επαγωγή γραμματικής ελεύθερης συμφραζομένων από παρατήρηση δομημένων χρονικών διαδικασιών

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

Αντικείμενο της εργασίας αυτής αποτελεί η ανάπτυξη μεθόδων που επιτρέπουν σε ένα υπολογιστικό σύστημα να αναπαριστά με συμπαγή τρόπο δομημένες χρονικές διαδικασίες. Ως δομημένη χρονική διαδικασία νοείται μία διαδικασία που προσδιορίζεται από κανόνες που αφορούν στον χρόνο. Παράδειγμα τέτοιων διαδικασιών είναι η ομιλία, που παρατηρείται σαν ακολουθία ήχων, το γραπτό κείμενο, που παρατηρείται ως σειρά χαρακτήρων και η κίνηση ενός ανθρώπου, που παρατηρείται ως η σχετική μετατόπιση των μελών του σώματός του σε μία ακολουθία εικόνων. Η συμπαγής αναπαράσταση μιας τέτοιας διαδικασίας περιλαμβάνει τον συμπερασμό της δομής της μέσω παρατήρησης πεπερασμένου πλήθους παραδειγμάτων της. Αυτή η ικανότητα αυτοματοποιημένης εξαγωγής συμπαγούς αναπαράστασης παρατηρήσεων είναι εξαιρετικά χρήσιμη σε συστήματα που αποσκοπούν στην συστηματική οργάνωση της γνώσης τους. Στην παρούσα εργασία, η εξαγωγή συμπαγούς αναπαράστασης μιας δομημένης χρονικής διαδικασίας ανάγεται στην επαγωγή μιας γραμματικής ελεύθερης συμφραζομένων, από παρατηρήσεις αυτής της διαδικασίας. Οι παρατηρήσεις μετατρέπονται σε συμβολοσειρές, ενώ για αυτές υποτίθεται ένα μοντέλο θορύβου, που μπορεί να τις αλλοιώνει με εισαγωγές, διαγραφές και αντικαταστάσεις συμβόλων. Η υπόθεση για γνωστό μοντέλο θορύβου, δίνει τη δυνατότητα ορισμού ενός επαναληπτικού σχήματος επαγωγής γραμματικής, που λειτουργεί αυξητικά και ανά παρατήρηση, καταλήγοντας τελικά σε μια γραμματική που αναγνωρίζει το σύνολο των παρατηρήσεων. Πιο συγκεκριμένα, για κάθε νέα παρατήρηση, εξετάζεται εάν αυτή μπορεί να ερμηνευθεί από την υπάρχουσα γραμματική. Εάν αυτό δεν ισχύει, η γραμματική επαυξάνεται ώστε να μπορεί να ερμηνεύσει και την νέα παρατήρηση. Η διαδικασία επαύξησης ελέγχεται από μία συνάρτηση κόστους που ευνοεί την ελάχιστη δυνατή επαύξηση. Η βελτιστοποίηση αυτής της συνάρτησης επιτυγχάνεται με δύο βασικά εργαλεία, τον αλγόριθμο Viterbi σε συνδυασμό με τον αλγόριθμο Levenshtein, και τα Markov Random Fields. Η αποτελεσμτικότητα και η αποδοτικότητα της προτεινόμενη μεθόδου επαγωγής γραμματικής αποτιμάται πειραματικά με χρήση συνθετικών γραμματικών και ορισμό συγκεκριμένων κριτηρίων εγγύτητας γραμματικών. Τελικά, παρουσιάζονται τα συμπεράσματα της πειραματικής αυτής αποτίμησης, εντοπίζονται πιθανές βελτιώσεις και αναδεικνύονται ζητήματα που θα μπορούσαν να αποτελέσουν το αντικείμενο μελλοντικής έρευνας. (EL)
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. (EN)

text

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

2009-04-02




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)