Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17091
Title: Τροπική Ανάλυση Αλγορίθμων σε Γράφους
Authors: Θεοδώσης, Εμμανουήλ
Μαραγκός Πέτρος
Keywords: Τροπική Άλγεβρα
Τροπική Γεωμετρία
Μηχανική Μάθηση
Μαθηματική Μοντελοποίηση
Βελτιστοποίηση
Issue Date: 11-Oct-2018
Abstract: Η μηχανική μάθηση αποτελεί ένα πεδίο το οποίο έχει βιώσει ραγδαία ανάπτυξη τα τελευταία χρόνια, με το ενδιαφέρον των ερευνητών να κορυφώνεται. ΄Ομως, οι μέθοδοι που αναπτύσσονται συχνά βασίζονται σε ευριστικές οι οποίες δεν έχουν ξεκάθαρα θεμελιωμένο μαθηματικό υπόβαθρο, και συνεπώς υστερούν τόσο από πλευράς διαίσθησης, εννοώντας ότι δεν είναι διαφανείς οι λόγοι που έχουν τις εκάστοτε αποδόσεις, αλλά υστερούν και από πλευράς επεκτασιμότητας, καθώς δεν είναι εμφανές τι ιδέες θα μπορούσαν να εφαρμοστούν για την βελτίωση των μοντέλων. Τα τελευταία χρόνια έχει υπάρξει μια τάση εισαγωγής αυστηρών μαθηματικών φορμαλισμών και γεωμετρικών στοιχείων στη μηχανική μάθηση. Σε αυτό το πνεύμα, αυτή η εργασία καταπιάνεται με την μοντελοποίηση αλγορίθμων που δρουν σε Weighted Finite State Transducers, τα οποία χρησιμοποιούνται συχνά στην Αυτόματη Αναγνώριση Φωνής και την Επεξεργασία Φυσικής Γλώσσας, στο πεδίο της τροπικής άλγεβρας. Μέσω αυτής της μοντελοποίησης αποσκοπούμε στην προσεκτικότερη μελέτη των ιδιοτήτων τους, και, όπου είναι δυνατό, επιθυμούμε να εκμεταλλευτούμε στοιχεία της τροπικής γεωμετρίας για να αναλύσουμε τους εν λόγω αλγορίθμους. Συγκεκριμένα, στα πλαίσια της διπλωματικής εργασίας, ασχοληθήκαμε με την μοντελοποίηση των παρακάτω αλγορίθμων: αλγόριθμος προώθησης βαρών, αλγόριθμος αφαίρεσης ε−μεταβάσεων, αλγόριθμος Viterbi, και αλγόριθμος Viterbi με αποκοπή. Μετά το πέρας της μοντελοποίησης, εκμεταλλευόμαστε στοιχεία της τροπικής γεωμετρίας, όπου αυτά εφαρμόζονται, έτσι ώστε να ορίσουμε γεωμετρικές οντότητες στον χώρο λύσεων των αλγορίθμων, προσφέροντας μια καινούργια οπτική, και εισάγουμε μετρικές οι οποίες μπορούν να χρησιμοποιηθούν στο σχεδιασμό συστημάτων. Τέλος, εφαρμόζουμε τις προτεινόμενες μεθόδους σε σύνολα δεδομένων και αξιολογούμε τα αποτελέσματα, παρουσιάζοντας, παράλληλα, παραδείγματα που υπογραμμίζουν την κομψότητα της μοντελοποίησης στον κύριο κορμό του κειμένου.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17091
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Theodosis_Thesis_finalArtemisv2.pdf1.25 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.