Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/13D3200B-5E1B-4DF9-87FD-F0FFF229F1AE | ||
| Year | 2019 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Evangelos Karatarakis, "Message passing inference as distributed computation", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2019 https://doi.org/10.26233/heallink.tuc.82729 | ||
| Appears in Collections |
Με χρήση του πιθανοτικού συμπερασμού λύνονται προβλήματα, όπως η εύρεση μιας οριακής συνάρτησης πυκνότητας πιθανότητας, χωρίς διαδοχική ολοκλήρωση ή η λύση συστημάτων γραμμικών εξισώσεων μεγάλων διαστάσεων. Αλγόριθμοι, όπως ο Gaussian Belief Propagation (GaBP), εφαρμόζονται με ανταλλαγή μηνυμάτων σε πιθανοτικά γραφικά μοντέλα, ενώ η εφαρμογή τους γίνεται σε ασύγχρονη και σε σύγχρονη εκδοχή, με διαφορετικά πλεονεκτήματα ανά περίπτωση. Επομένως, είναι απαραίτητη η μελέτη ικανών και αναγκαίων συνθηκών σύγκλισης για κάθε εκδοχή. Οι σύγχρονοι αλγόριθμοι χαρακτηρίζονται από ικανές και αναγκαίες συνθήκες σύγκλισης, πράγμα το οποίο ισχύει και για τον GaBP. Οι ασύγχρονοι χαρακτηρίζονται κυρίως από ικανές (και όχι αναγκαίες) συνθήκες σύγκλισης και έχουν μεγάλο ερευνητικό ενδιαφέρον. Ανταλλαγή μηνυμάτων μπορεί να συμβεί και κατά την ασύγχρονη κατανεμημένη εκδοχή του αλγορίθμου Jacobi, με χρήση ενός πλήθους επεξεργαστών. Ο αλγόριθμος αυτός, αν και δεν ανήκει στην κατηγορία του πιθανοτικού συμπερασμού, μπορεί να προσφέρει χρήσιμες ιδέες στην μελέτη της ασύγχρονης εκδοχής του GaBP. Σημειώνεται ότι ο αλγόριθμος Jacobi αποτελεί ειδική περίπτωση του αλγορίθμου GaBP, όπως πρόσφατα αναφέρθηκε στην βιβλιογραφία. Συγκεκριμένα, αξιοποιούνται πρόσφατα ευρήματα για τον ασύγχρονο Jacobi, όπου το ελάχιστο μονοπάτι στον γράφο που περιγράφει το χρονοδιάγραμμα ανταλλαγής μηνυμάτων, καθορίζει μετρικές σύγκλισης. Στην εργασία αυτή έγινε αξιοποίηση αυτής της μεθοδολογίας στην μελέτη του ασύγχρονου GaBP, κατόπιν παρατήρησης ότι οι αναδρομικές εξισώσεις ανανέωσης των μηνυμάτων του είναι εν μέρει γραμμικές. Το τελευταίο προέκυψε από πρόσφατες μελέτες, όπου φαίνεται ότι ο αλγόριθμος GaBP μπορεί να περιγραφεί μέσω της επίλυσης ενός προβλήματος βελτιστοποίησης, το οποίο καταλήγει σε ένα σύστημα γραμμικών εξισώσεων. Επίσης, μελετήθηκε η συμπεριφορά του ελάχιστου μονοπατιού στο γράφο για μια σειρά προβλημάτων, στα οποία εκτελείται ο ασύγχρονος κατανεμημένος Jacobi.
Copyright © DIAS 2013
