Τροπική Ανάλυση Αλγορίθμων σε Γράφους

Abstract

Η μηχανική μάθηση αποτελεί ένα πεδίο το οποίο έχει βιώσει ραγδαία ανάπτυξη τα τελευταία χρόνια, με το ενδιαφέρον των ερευνητών να κορυφώνεται. ΄Ομως, οι μέθοδοι που αναπτύσσονται συχνά βασίζονται σε ευριστικές οι οποίες δεν έχουν ξεκάθαρα θεμελιωμένο μαθηματικό υπόβαθρο, και συνεπώς υστερούν τόσο από πλευράς διαίσθησης, εννοώντας ότι δεν είναι διαφανείς οι λόγοι που έχουν τις εκάστοτε αποδόσεις, αλλά υστερούν και από πλευράς επεκτασιμότητας, καθώς δεν είναι εμφανές τι ιδέες θα μπορούσαν να εφαρμοστούν για την βελτίωση των μοντέλων.

Τα τελευταία χρόνια έχει υπάρξει μια τάση εισαγωγής αυστηρών μαθηματικών φορμαλισμών και γεωμετρικών στοιχείων στη μηχανική μάθηση. Σε αυτό το πνεύμα, αυτή η εργασία καταπιάνεται με την μοντελοποίηση αλγορίθμων που δρουν σε Weighted Finite State Transducers, τα οποία χρησιμοποιούνται συχνά στην Αυτόματη Αναγνώριση Φωνής και την Επεξεργασία Φυσικής Γλώσσας, στο πεδίο της τροπικής άλγεβρας. Μέσω αυτής της μοντελοποίησης αποσκοπούμε στην προσεκτικότερη μελέτη των ιδιοτήτων τους, και, όπου είναι δυνατό, επιθυμούμε να εκμεταλλευτούμε στοιχεία της τροπικής γεωμετρίας για να αναλύσουμε τους εν λόγω αλγορίθμους.

Συγκεκριμένα, στα πλαίσια της διπλωματικής εργασίας, ασχοληθήκαμε με την μοντελοποίηση των παρακάτω αλγορίθμων: αλγόριθμος προώθησης βαρών, αλγόριθμος αφαίρεσης ε−μεταβάσεων, αλγόριθμος Viterbi, και αλγόριθμος Viterbi με αποκοπή.

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

Τέλος, εφαρμόζουμε τις προτεινόμενες μεθόδους σε σύνολα δεδομένων και αξιολογούμε τα αποτελέσματα, παρουσιάζοντας, παράλληλα, παραδείγματα που υπογραμμίζουν την κομψότητα της μοντελοποίησης στον κύριο κορμό του κειμένου.