Signal processing on graphs
Authors: Μανδάνας Φώτιος 
Published: April 2023

Η παρούσα διατριβή πραγματεύτηκε μοντέλα επεξεργασίας σήματος που εφαρμόζονται σε γραφήματα. Η τετραγωνική κατά το ήμισυ ελαχιστοποίηση, οι εύρωστοι εκτιμητές, όπως ο διάμεσος και οι Μ-εκτιμητές, η κανονικοποίηση μέσω της l21 νόρμας, η ομαδική μέθοδος των ελαχίστων τετραγώνων αποτελούν τη βάση των προτεινόμενων προσεγγίσεων. Συγκεκριμένα, για να διορθωθεί η τρωτότητα από λανθασμένες ενσωματώσεις στο πρόβλημα της πολυδιάστατης κλιμάκωσης, εξαιτίας της παραμόρφωσης που εισάγουν οι ακραίες τιμές, προτείνεται ένα ενοποιημένο πλαίσιο όπου το πρόβλημα της πολυδιάστατης κλιμάκωσης αντιμετωπίζεται ως μεγιστοποίηση ενός κριτηρίου συσχεντροπίας, το οποίο επιλύεται με τετραγωνική κατά το ήμισυ ελαχιστοποίηση με χρήση πολλαπλασιαστικών ή προσθετικών μαθηματικών διατυπώσεων. Προκύπτουν τρεις νέοι αλγόριθμοι. Η απόδοσή τους αξιολογείται πειραματικά έναντι τριών σύγχρονων τεχνικών πολυδιάστατης κλιμάκωσης: Κλιμάκωση Μεγιστοποιώντας μία Περίπλοκη Συνάρτηση, Εύρωστη Ευκλείδεια Ενσωμάτωση, και Εύρωστη Πολυδιάστατη Κλιμάκωση. Τα πειραματικά αποτελέσματα καταδεικνύουν ότι οι προτεινόμενοι αλγόριθμοι αποδίδουν σημαντικώς καλύτερα από τις προαναφερθείσες ανταγωνιστικές τεχνικές. Επιπλέον, προτείνεται ένα άλλο ενοποιημένο πλαίσιο για την επίλυση του προβλήματος της πολυδιάστατης κλιμάκωσης, το οποίο χρησιμοποιεί, ομοίως, τετραγωνική κατά το ήμισυ ελαχιστοποίηση, αξιοποιώντας συναρτήσεις των M-εκτιμητών σε συνδυασμό με έναν περιορισμό κανονικοποίησης της l21 νόρμας. Τα πειραματικά δεδομένα κατέδειξαν ότι οι προτεινόμενοι αλγόριθμοι αποδίδουν καλύτερα από τις σύγχρονες ανταγωνιστικές τεχνικές. Επιπροσθέτως, εξετάστηκε μία ακόμη παραλλαγή του προταθέντος πλαισίου η οποία περιλαμβάνει τη χρήση M-εκτιμητών σε συνδυασμό με έναν περιορισμό κανονικοποίησης της πυρηνικής νόρμας. Ομοίως, απεδείχθη ότι οι προτεινόμενοι αλγόριθμοι υπερτερούν έναντι των σύγχρονων τεχνικών. Στη συνέχεια, έλαβε χώρα η συμπερίληψη πολλών αλγορίθμων μείωσης διαστάσεων σε ένα ενιαίο πλαίσιο, γνωστό ως ενσωμάτωση γραφήματος. Η εφαρμογή της ορθογωνικότητας στο γραμμικό πίνακα προβολής, εντός αυτού του πλαισίου, απεδείχθη ζωτικής σημασίας, καθώς οι «ορθογώνιοι» αλγόριθμοι μείωσης διαστάσεων ξεπερνούν σε ποσοστό αναγνώρισης τους αντίστοιχους μη «ορθογώνιους», με τη χρήση του ταξινομητή του πλησιέστερου γείτονα. Για να επιτευχθούν αραιές γραμμές στον πίνακα προβολής, επιβλήθηκε ταυτόχρονα η l21 νόρμα στο συγκεκριμένο πίνακα, οδηγώντας στο γνωστό μοντέλο της από κοινού επιλογής χαρακτηριστικών και μάθησης υποχώρων. Αποδεικνύεται ότι η χρήση των ορθογώνιων αλγορίθμων στο προαναφερθέν πλαίσιο έναντι των αντίστοιχων μη ορθογώνιων αλγορίθμων δεν βελτιώνει το ποσοστό αναγνώρισης του ταξινομητή του πλησιέστερου γείτονα. Στη συνέχεια, εξετάζεται η περίπτωση που ένα τυχαία επιλεγμένο υποσύνολο πρακτόρων μοιράζεται με τους γείτονές του τοπικές πληροφορίες οι οποίες έχουν αλλοιωθεί εσκεμμένα από μεγάλα σφάλματα. Προτείνονται τρεις παραλλαγές των υφιστάμενων αλγορίθμων χωροχρονικής διάχυσης σε προσαρμοστικά δίκτυα. Πρώτα απ’ όλα, οι πράκτορες εφαρμόζουν την ομαδική μέθοδο των ελαχίστων τετραγώνων εκμεταλλευόμενοι στο πεδίο του χρόνου μια περιορισμένη μνήμη προηγούμενων διανυσμάτων παλινδρόμησης καθώς και προηγούμενες εκτιμήσεις της απόστασης από το στόχο. Δεύτερον, οι πράκτορες προχωρούν, στο πεδίο του χρόνου, σε εκτίμηση των συνδυαστικών βαρών χρησιμοποιώντας τη συνάρτηση στάθμισης των M-εκτιμητών της απόστασης κάθε μίας από τις ενδιάμεσες εκτιμήσεις από τη μέση τιμή αυτών των εκτιμήσεων. Τρίτον, οι πράκτορες προχωρούν, στο πεδίο του χώρου, σε εκτίμηση των συνδυαστικών βαρών βασιζόμενοι στα εκθετικά της αρνητικής απόστασης των ενδιάμεσων εκτιμήσεων θέσεως, εντός της γειτονιάς τους, από τη μεσαία τιμή αυτών των εκτιμήσεων. Οι πειραματικές καμπύλες μάθησης κατέδειξαν ότι, σε βάρος ορισμένων επιπλέον υπολογιστικών απαιτήσεων, οι προτεινόμενοι αλγόριθμοι εξομαλύνουν αποτελεσματικότερα την επίδραση των παράτυπων σημείων σε σχέση με τις σύγχρονες στρατηγικές.