Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/10435
Title: Algorithms for the fast estimation of statistical leverage scores
Other Titles: Αλγόριθμοι για την ταχεία εκτίμηση τιμών στατιστικής μόχλευσης
Authors: Sobczyk, Alexandros
Keywords: Statistical leverage
Algorithms
Fast estimation
Linear algebra
Keywords (translated): Στατιστική μόχλευση
Αλγόριθμοι
Ταχεία εκτίμηση
Γραμμική άλγεβρα
Abstract: In this thesis we consider algorithms for fast estimations of leverage scores. Statistical leverage scores are a powerful tool for data analysis and statistics and have been successfully used for outlier detection in datasets, locating important nodes in graphs and more recently applied to numerical linear algebra algorithms. In order to build estimators, we consider dimensionality reduction techniques that use randomization in combination with iterative methods for solving linear systems with multiple right hand sides. Based on these techniques we try to overcome certain limitations of the current state-of-the-art algorithms and propose an approach which provably returns good estimations of leverage scores, scales well in parallel/distributed environments and effectively utilizes sparsity. We present our results on synthetic and real world data sets and evaluate its performance, and discuss the advantages and drawbacks relative to all considered approaches.
Abstract (translated): Στην παρούσα εργασία μελετώνται αλγόριθμοι για την ταχεία εκτίμηση τιμών μόχλευσης σε σύνολα δεδομένων. Οι τιμές στατιστικής μόχλευσης αποτελούν ισχυρό εργαλείο για την ανάλυση δεδομένων και τη στατιστική και έχουν χρησιμοποιηθεί επιτυχώς για τον εντοπισμό έκτοπων τιμών σε σύνολα δεδομένων, εύρεση σημαντικών κόμβων σε γράφους, ενώ πρόσφατα έχουν εφαρμοσθεί σε αλγόριθμους τυχαιοποιημένης γραμμικής άλγεβρας. Για την κατασκευή εκτιμητών αναλύουμε διάφορες τεχνικές μείωσης διαστατικότητας που χρησιμοποιούν τυχαιότητα σε συνδυασμό με επαναληπτικές μεθόδους για την επίλυση γραμμικών συστημάτων με πολλά δεξιά μέλη. Βασισμένοι σε αυτές τις τεχνικές προσπαθούμε να προσπεράσουμε συγκεκριμένους περιορισμούς που εντοπίζονται στις μέχρι στιγμής βέλτιστες προσεγγίσεις και προτείνουμε έναν αλγόριθμο ο οποίος αποδεδειγμένα επιστρέφει καλές εκτιμήσεις των τιμών μόχλευσης, παρουσιάζει καλή απόδοση σε υπολογισμούς κλίμακας σε παράλληλα/κατανεμημένα περιβάλλοντα και διαχειρίζεται αποδοτικά αραιά μητρώα. Παρουσιάζουμε τα αποτελέσματά μας σε τεχνητά και πραγματικά σύνολα δεδομένων και παρέχουμε σχολιασμό των αποτελεσμάτων και συζητήσεις σχετικά με τα πλεονεκτήματα και μειονεκτήματα διαφόρων αλγορίθμων.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
leverage_scores.pdf3.78 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.