Συμπερασμός με ανταλλαγή μηνυμάτων ως κατανεμημένος υπολογισμόςΣυμπερασμός με ανταλλαγή μηνυμάτων ως κατανεμημένος υπολογισμόςMessage passing inference as distributed computation Διπλωματική Εργασία Diploma Work 2019-07-182019elΜε χρήση του πιθανοτικού συμπερασμού λύνονται προβλήματα, όπως η εύρεση μιας οριακής συνάρτησης πυκνότητας πιθανότητας, χωρίς διαδοχική ολοκλήρωση ή η λύση συστημάτων γραμμικών εξισώσεων μεγάλων διαστάσεων. Αλγόριθμοι, όπως ο Gaussian Belief Propagation (GaBP), εφαρμόζονται με ανταλλαγή μηνυμάτων σε πιθανοτικά γραφικά μοντέλα, ενώ η εφαρμογή τους γίνεται σε ασύγχρονη και σε σύγχρονη εκδοχή, με διαφορετικά πλεονεκτήματα ανά περίπτωση. Επομένως, είναι απαραίτητη η μελέτη ικανών και αναγκαίων συνθηκών σύγκλισης για κάθε εκδοχή. Οι σύγχρονοι αλγόριθμοι χαρακτηρίζονται από ικανές και αναγκαίες συνθήκες σύγκλισης, πράγμα το οποίο ισχύει και για τον GaBP. Οι ασύγχρονοι χαρακτηρίζονται κυρίως από ικανές (και όχι αναγκαίες) συνθήκες σύγκλισης και έχουν μεγάλο ερευνητικό ενδιαφέρον. Ανταλλαγή μηνυμάτων μπορεί να συμβεί και κατά την ασύγχρονη κατανεμημένη εκδοχή του αλγορίθμου Jacobi, με χρήση ενός πλήθους επεξεργαστών. Ο αλγόριθμος αυτός, αν και δεν ανήκει στην κατηγορία του πιθανοτικού συμπερασμού, μπορεί να προσφέρει χρήσιμες ιδέες στην μελέτη της ασύγχρονης εκδοχής του GaBP. Σημειώνεται ότι ο αλγόριθμος Jacobi αποτελεί ειδική περίπτωση του αλγορίθμου GaBP, όπως πρόσφατα αναφέρθηκε στην βιβλιογραφία. Συγκεκριμένα, αξιοποιούνται πρόσφατα ευρήματα για τον ασύγχρονο Jacobi, όπου το ελάχιστο μονοπάτι στον γράφο που περιγράφει το χρονοδιάγραμμα ανταλλαγής μηνυμάτων, καθορίζει μετρικές σύγκλισης. Στην εργασία αυτή έγινε αξιοποίηση αυτής της μεθοδολογίας στην μελέτη του ασύγχρονου GaBP, κατόπιν παρατήρησης ότι οι αναδρομικές εξισώσεις ανανέωσης των μηνυμάτων του είναι εν μέρει γραμμικές. Το τελευταίο προέκυψε από πρόσφατες μελέτες, όπου φαίνεται ότι ο αλγόριθμος GaBP μπορεί να περιγραφεί μέσω της επίλυσης ενός προβλήματος βελτιστοποίησης, το οποίο καταλήγει σε ένα σύστημα γραμμικών εξισώσεων. Επίσης, μελετήθηκε η συμπεριφορά του ελάχιστου μονοπατιού στο γράφο για μια σειρά προβλημάτων, στα οποία εκτελείται ο ασύγχρονος κατανεμημένος Jacobi.Διπλωματική εργασία που υποβλήθηκε στη σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών για τη μερική εκπλήρωση των απαιτήσεων για τη λήψη του διπλώματος Ηλεκτρολόγου Μηχανικού και Μηχανικού Υπολογιστών.http://creativecommons.org/licenses/by-nc/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών ΥπολογιστώνKaratarakis_Evangelos_Dip_2019.pdfChania [Greece]Library of TUC2019-07-18application/pdf868.6 kBfree Karatarakis Evangelos Καραταρακης Ευαγγελος Bletsas Aggelos Μπλετσας Αγγελος Lagoudakis Michail Λαγουδακης Μιχαηλ Samoladas Vasilis Σαμολαδας Βασιλης Πολυτεχνείο Κρήτης Technical University of Crete Message passing inference Distributed Computation Probabilistic Inference Asynchronous Parallel Jacobi Gaussian Belief Propagation