Robust multidimensional scaling using a maximum correntropy criterion
Creators: name: Μανδάνας, Φώτιος Δημητρίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Πολυδιάστατη κλιμάκωση
Συσχεντροπία
Ευρωστία
Multidimensional scaling
Correntropy
Robustness

description: Η πολυδιάστατη κλιμάκωση ανήκει σε μία κατηγορία τεχνικών μείωσης διαστάσεων, οι οποίες εφαρμόζονται με τέτοιο τρόπο στα ζεύγη μεταξύ των υφιστάμενων αντικειμένων, ώστε οι προκύπτουσες αποστάσεις μεταξύ των σημείων στην τελική διαμόρφωση να προσεγγίζουν όσο το δυνατόν περισσότερο τα αρχικά ζεύγη ανομοιοτήτων. Η πολυδιάστατη κλιμάκωση βρίσκει εφαρμογή σε ένα ευρύ φάσμα προβλημάτων, τόσο ως αυτοτελές μοντέλο όσο και ως υποπρόβλημα σε περισσότερο πολύπλοκα προβλήματα. Αυτή η ευρεία εφαρμογή οδήγησε τους ερευνητές στην αναζήτηση γρήγορων και αποδοτικών αλγορίθμων για την επίλυσή του. Παρόλο που το συγκεκριμένο πρόβλημα έχει μελετηθεί για αρκετά χρόνια, οι παραδοσιακοί αλγόριθμοι επίλυσής του είναι ιδιαίτερα ευάλωτοι στην ύπαρξη παράτυπων σημείων, καθιστώντας την τελική λύση ανακριβή, λόγω του υψηλού βαθμού παραμόρφωσης που εισάγεται. Στην παρούσα εργασία προτείνεται ένα ενοποιημένο πλαίσιο, όπου το πρόβλημα της πολυδιάστατης κλιμάκωσης αντιμετωπίζεται ως μεγιστοποίηση του κριτηρίου συσχεντροπίας. Το εν λόγω πρόβλημα επιλύεται με τετραγωνική κατά το ήμισυ ελαχιστοποίηση, με χρήση είτε πολλαπλασιαστικών, είτε προσθετικών μαθηματικών διατυπώσεων. Με αυτόν τον τρόπο, η πολυδιάστατη κλιμάκωση μπορεί να διαχειριστεί επιτυχώς έναν αρχικό πίνακα ανομοιοτήτων, ο οποίος έχει μολυνθεί με ακραίες τιμές, διότι, όπως αποδεικνύεται, η συσχεντροπία συνδέεται άμεσα με τους Μ-εκτιμητές. Τρεις νέες προσεγγίσεις, μία προσθετική και δύο πολλαπλασιαστικές μελετώνται στην παρούσα εργασία. Η απόδοση των προτεινόμενων αλγορίθμων αξιολογείται τόσο θεωρητικά όσο και πειραματικά για διαφορετικές επιλογές συναρτήσεων. Για σκοπούς αξιολόγησης, τρεις επιπρόσθετες υψηλού επιπέδου τεχνικές υλοποιήθηκαν υπό τις ίδιες συνθήκες. Τα πειραματικά αποτελέσματα καταδεικνύουν ότι οι προτεινόμενοι αλγόριθμοι, βασιζόμενοι στη θεωρία των Μ-εκτιμητών, παρουσιάζουν σημαντικά καλύτερες επιδόσεις από τις προαναφερθείσες υψηλού επιπέδου ανταγωνιστικές τεχνικές.
description: Multidimensional Scaling (MDS) refers to a class of dimensionality reduction techniques that operate on pairwise dissimilarities between entities, so that the interpoint distances approximate the initial pairwise dissimilarities as closely as possible. However, traditional methods for solving the MDS are immensely susceptible to outliers, rendering the final solution inaccurate, due to the high degree of distortion. A unified framework is proposed where MDS is treated as maximization of a correntropy criterion, which is solved by half-quadratic optimization with either multiplicative or additive formulations. By doing so, MDS can cope with an initial dissimilarity matrix contaminated with outliers, because correntropy criterion is closely related to the M-estimators. Three novel approaches, one additive and two multiplicative, are studied. The performance of the proposed algorithms is assessed both theoretically and experimentally for different choices of the potential functions. For evaluation purposes, three state-of-the-art MDS techniques (SMACOF, REE, RMDS) have been implemented and tested under the same conditions. The experimental results indicate that the proposed algorithms, relying on the M-estimators, perform substantially better than the aforementioned state-of-the-art competing techniques.