Development of Multidimensional Scaling Algorithms with Application to Natural Language Representation Problems

Abstract

Στην παρούσα διπλωματική εργασία εξετάζουμε και αναπτύσσουμε αλγορίθμους Συνολοθεωρητικής Πολυδιάστατης Κλιμάκωσης και μείωσης διαστατικότητας. Εστιάζουμε σε αλγορίθμους που μπορούν να απλοποιήσουν δεδομένα με πολύπλοκη και μη γραμμική δομή, έτσι ώστε να γίνουν καλύτερα αντιληπτές από τον άνθρωπο και να αποκαλύψουν πιθανές συσχετίσεις μεταξύ των δεδομένων. Η συνεισφορά της διπλωματικής αποτελείται από δύο μέρη. Στο πρώτο μέρος της διπλωματικής βελτιστοποιούμε μια επέκταση της κλασικής μεθόδου πολυδιάστατης κλιμάκωσης (Multidimensional Scaling) χρησιμοποιώντας τεχνικές βελτιστοποίησης χωρίς παραγώγους. Η αξιολόγηση του αλγορίθμου μας έγινε σε συνθετικά και πραγματικά δεδομένα και το συμπέρασμα μας είναι ότι ο αλγόριθμος μπορεί να εκτιμήσει με ακρίβεια την γεωμετρία των δεδομένων που είναι ενσωματωμένα σε χώρους με υψηλές διαστάσεις.Στο δεύτερο μέρος, ορίζουμε το πρόβλημα του Set-MDS όπου η ιδιαιτερότητα είναι ότι τα δεδομένα μας αποτελούνται από σύνολα σημείων και όχι από μεμωνομένα σημεία, και στην συνέχεια προτείνουμε μία προσεγγιστική λύση μέσω του αλγορίθμου COSMOS. Αφού αναλύσουμε τον αλγόριθμο, παρουσιάζουμε τα αποτελέσματα των πειραμάτων μας.