Robust algorithms for linear and nonlinear regression via sparse modeling methods

Η εύρωστη παλινδρόμηση κατέχει έναν πολύ σημαντικό ρόλο στην Επεξεργασία Σήματος, τη Στατιστική και τη Μηχανική Μάθηση. Συνήθεις εκτιμητές, όπως τα «Ελάχιστα Τετράγωνα», αποτυγχάνουν να εκτιμήσουν σωστά παραμέτρους, όταν στα δεδομένα υπεισέρχονται ακραίες παρατηρήσεις, γνωστές ως "outliers". Το πρόβλημα αυτό είναι γνωστό εδώ και δεκαετίες, μέσα στις οποίες διάφορες μέθοδοι έχουν προταθεί. Παρόλα αυτά, το ενδιαφέρον της επιστημονικής κοινότητας για αυτό αναζωπυρώθηκε όταν επανεξετάστηκε υπό το πρίσμα της αραιής μοντελοποίησης και των αντίστοιχων τεχνικών, η οποία κυριαρχεί στον τομέα της μηχανικής μάθησης εδώ και δύο δεκαετίες. Αυτή είναι και η κατεύθυνση η οποία ακολουθήθηκε στην παρούσα διατριβή. Το αποτέλεσμα αυτής της εργασίας ήταν η ανάπτυξη μιας νέας προσέγγισης, βασισμένης σε άπληστες τεχνικές αραιής μοντελοποίησης. Το μοντέλο που υιοθετείται βασίζεται στην ανάλυση του θορύβου σε δύο συνιστώσες: α) μια για το συμβατικό (αναμενόμενο) θόρυβο και β) μια για τις ακραίες παρατηρήσεις (outliers), οι οποίες θεωρήθηκε ότι είναι λίγες (αραιές) σε σχέση με τον αριθμό των δεδομένων. Με βάση αυτή τη μοντελοποίηση και τον γνωστό άπληστο αλγόριθμο "Orthogonal Matching Pursuit" (OMP), δύο νέοι αλγόριθμοι αναπτύχθηκαν, ένας για το γραμμικό και ένας για το μη γραμμικό πρόβλημα της εύρωστης παλινδρόμησης.Ο προτεινόμενος αλγόριθμος για τη γραμμική παλινδρόμηση ονομάζεται "Greedy Algorithm for Robust Demoising" (GARD) και εναλλάσσει τα βήματά του μεταξύ της μεθόδου Ελαχίστων Τετραγώνων (LS) και της αναγνώρισης των ακραίων παρατηρήσεων, τεχνικής που βασίζεται στον OMP. Στη συνέχεια, ακολουθεί η σύγκριση της νέας μεθόδου με ανταγωνιστικές της. Συγκεκριμένα, από τα αποτελέσματα παρατηρείται ότι ο GARD: α) δείχνει ανοχή σε ακραίες τιμές (εύρωστος), β) καταφέρνει να προσεγγίσει τη λύση με πολύ μικρό λάθος και γ) απαιτεί μικρό υπολογιστικό κόστος. Επιπλέον, προκύπτουν σημαντικά θεωρητικά ευρήματα, τα οποία οφείλονται στην απλότητα της μεθόδου. Αρχικά, αποδεικνύεται ότι η μέθοδος συγκλίνει σε πεπερασμένο αριθμό βημάτων. Στη συνέχεια, η μελέτη επικεντρώνεται στην αναγνώριση των ακραίων παρατηρήσεων. Το γεγονός ότι η περίπτωση απουσίας συμβατικού θορύβου μελετήθηκε ξεχωριστά, οφείλεται κυρίως στα εξής: α) στην απλοποίηση απαιτητικών πράξεων και β) στην ανάδειξη σημαντικών γεωμετρικών ιδιοτήτων. Συγκεκριμένα, προέκυψε κατάλληλο φράγμα για τη σταθερά της συνθήκης «Περιορισμένης Ισομετρίας» ("Restricted Isometry Property" - (RIP)), το οποίο εξασφαλίζει ότι η ανάκτηση του σήματος μέσω του GARD είναι ακριβής (μηδενικό σφάλμα). Τέλος, για την περίπτωση όπου ακραίες τιμές και συμβατικός θόρυβος συνυπάρχουν και με την παραδοχή ότι το διάνυσμα του συμβατικού θορύβου είναι φραγμένο, προέκυψε μια αντίστοιχη συνθήκη η οποία εξασφαλίζει την ανάκτηση του φορέα του αραιού διανύσματος θορύβου (outliers). Δεδομένου ότι μια τέτοια συνθήκη ικανοποιείται, αποδείχθηκε ότι το σφάλμα προσέγγισης είναι φραγμένο και άρα ο εκτιμητής GARD ευσταθής.Για το πρόβλημα της εύρωστης μη γραμμικής παλινδρόμησης, θεωρείται, επιπλέον, ότι η άγνωστη μη γραμμική συνάρτηση ανήκει σε ένα χώρο Hilbert με αναπαραγωγικούς πυρήνες (RKHS). Λόγω της ύπαρξης ακραίων παρατηρήσεων, τεχνικές όπως το Kernel Ridge Regression (KRR) ή το Support Vector Regression (SVR) αποδεικνύονται ανεπαρκείς. Βασισμένοι στην προαναφερθείσα ανάλυση των συνιστωσών του θορύβου και χρησιμοποιώντας την τεχνική της αραιής μοντελοποίησης, πραγματοποιείται η εκτίμηση των ακραίων παρατηρήσεων σύμφωνα με τα βήματα μιας άπληστης επαναληπτικής διαδικασίας. Ο προτεινόμενος αλγόριθμος ονομάζεται "Kernel Greedy Algorithm for Robust Denoising" (KGARD), και εναλλάσσει τα βήματά μεταξύ ενός εκτιμητή KRR και της αναγνώρισης ακραίων παρατηρήσεων, με βάση τον OMP. Αναλύεται θεωρητικά η ικανότητα του αλγορίθμου να αναγνωρίσει τις πιθανές ακραίες παρατηρήσεις. Επιπλέον, ο αλγόριθμος KGARD συγκρίνεται με άλλες μεθόδους αιχμής μέσα από εκτεταμένο αριθμό πειραμάτων, όπου και παρατηρείται η σαφώς καλύτερη απόδοσή του. Τέλος, η προτεινόμενη μέθοδος για την εύρωστη παλινδρόμηση εφαρμόζεται στην αποθορύβωση εικόνας, όπου αναδεικνύονται τα σαφή πλεονεκτήματα της μεθόδου. Τα πειράματα επιβεβαιώνουν ότι ο αλγόριθμος KGARD βελτιώνει σημαντικά την διαδικασία της αποθορύβωσης, στην περίπτωση όπου στον θόρυβο υπεισέρχονται ακραίες παρατηρήσεις.