Ο φοιτητής του προγράμματος Βασίλης Μαργώνης θα παρουσιάσει την διπλωματική του εργασία με θέμα:
Μείωση διάστασης για την αναζήτηση προσεγγιστικού κοντινού γείτονα στη μετρική Μανχάταν
την Πέμπτη 11 Απριλίου 2019 και ώρα 14:00, στην αίθουσα Α56 του Τμήματος Πληροφορικής και Τηλεπικοινωνιών του ΕΚΠΑ.
Σύνοψη Διπλωματικής:
Οι τυχαίες προβολές αποτελούν μια απο τις πιο διαδεδομένες μεθόδους για το χειρισμό δεδομένων μεγάλης διάστασης. Ξεκινώντας από το περίφημο Johnson-Lindenstrauss Lemma, τέτοιου είδους προβολές έχουν μελετηθεί αρκετά για την Ευκλείδια $(\ell_2)$ μετρική, και πολύ λιγότερο για τη μετρική Μανχάταν $(\ell_1)$. Σε αυτή την εργασία εστιάζουμε στο πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στη μετρική Μανχάταν, εκμεταλλεύοντας την αποφαντική εκδοχή του προβλήματος, που λέγεται προσεγγιστικός \textit{κοντινός} γείτονας και επιβάλει ένα --περίπου-- λογαριθμικό κόστος.
Το 2007, οι Indyk και Naor, εισήγαγαν την έννοια των εμβυθίσεων που διατηρούν τον κοντινότερο γείτονα (nearest neighbor-preserving embeddings). Αυτές οι εμβυθίσεις είναι τυχαιοκρατικές και εγγυόνται για την αλλοίωση μόνο $n$ αποστάσεων (μεταξύ ενός σημείου-query και $n$ σημείων), αντί για όλες τις δυνατές $O(n^2)$. Τέτοιου είδους εμβυθίσεις υπάρχουν για τις μετρικές $\ell_2$ και $\ell_1$, καθώς και για διπλασιάζοντα (doubling) υποσύνολα της $\ell_2$.
Η συνεισφορά αυτής της εργασίας είναι μια συνάρτηση εμβύθισης για μείωση διάστασης, η οποία διατηρεί τον \textit{κοντινό} γείτονα (\textit{near} neighbor-preserving embedding) για διπλασιάζοντα υποσύνολα της $\ell_1$. Η τεχνική που εφαρμόζουμε είναι να προβάλουμε τυχαία όχι τα ίδια τα σημεία, αλλά ένα σύνολο αντιπροσώπων τους. Μελετούμε δύο είδη αντιπροσώπων, approximate nets και randomly shifted grids, και τα συγκρίνουμε ως προς την νέα διάσταση και το χρόνο υπολογισμού της συνάρτησης-εμβύθισης.
Η Επιτροπή,
Ιωάννης Εμίρης (Επιβλέπων),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Άρης Παγουρτζής,
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Δημήτρης Φωτάκης,
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ