Συντάχθηκε 17-09-2019 11:13
Ενημερώθηκε:
18-09-2019 14:40
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΧΡΗΣΤΟΥ ΚΟΛΟΜΒΑΚΗ
με θέμα
ΑΠΟΔΟΤΙΚΟΙ ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΕΠΕΞΕΡΓΑΣΙΑ ΤΑΝΥΣΤΩΝ ΚΑΙ ΥΛΟΠΟΙΗΣΗ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΠΕΡΙΒΑΛΛΟΝΤΑ
EFFICIENT PARALLEL ALGORITHMS FOR TENSOR DECOMPOSITIONS AND IMPLEMENTATION IN DISTRIBUTED ENVIRONMENTS
Εξεταστική Επιτροπή
Καθηγητής Αθανάσιος Λιάβας (επιβλέπων)
Καθηγητής Γεώργιος Καρυστινός
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς
Περίληψη: Οι τανυστές είναι μαθηματικές δομές οι οποίες έχουν γίνει τα τελευταία χρόνια δημοφιλείς στα πεδία της επεξεργασίας σήματος και της μηχανικής μάθησης. Αυτό είναι λόγω της ικανότητάς τους να μπορούν να μοντελοποιούν τις σχέσεις και τις εξαρτήσεις μεταξύ πολλών αντικειμένων. Για ένα πλήρες data set, όπου δεν υπάρχουν στοιχεία που δεν μας είναι διαθέσιμα, οι αποσυνθέσεις τανυστών μας δίνουν την δυνατότητα να κάνουμε μοντελοποίηση των δεδομένων, ενώ κάποιες συγκεκριμένες αποσυνθέσεις μας δίνουν την δυνατότητα να πετύχουμε συμπίεση των δεδομένων. Για ένα data set στο οποίο λείπουν στοιχεία, μπορούμε να χρησιμοποιήσουμε αποσυνθέσεις έτσι ώστε να συμπεράνουμε στοιχεία που λείπουν. Οι τανυστές ωστόσο πάσχουν από την “κατάρα της διαστατικότητας”. Ο αριθμός των στοιχείων ενός τανυστή αυξάνεται εκθετικά με την τάξη του, και ως αποτέλεσμα, υπάρχει η ανάγκη για την ανάπτυξη αποδοτικών αλγορίθμων που πραγματοποιούν τις αποσυνθέσεις.
Σε αυτήν την εργασία, θα επικεντρωθούμε στην αποσύνθεση CP ή PARAFAC. Αρχικά αναφέρουμε κάποιες έννοιες από την γραμμική άλγεβρα, και στην συνέχεια αναφερόμαστε σε προβλήματα ελαχίστων τετραγώνων για πίνακες. Μετά από μία εισαγωγή στην άλγεβρα τανυστών, παρουσιάζουμε την αποσύνθεση PARAFAC. Το πρόβλημα που καλούμαστε να αντιμετωπίσουμε είναι η επιτάχυνση ενός πολλαπλασιασμού πινάκων κατά την διάρκεια του αλγορίθμου αποσύνθεσης. Το γινόμενο είναι γνωστό στην βιβλιογραφία ως matricized—tensor Khatri—Rao product (MTTKRP) και αποτελεί το πιο απαιτητικό υπολογιστικά στάδιο του αλγορίθμου. Προς αυτό τον σκοπό, χρησιμοποιούμε μια δομή η οποία λέγεται dimension tree. Το δέντρο αποθηκεύει ποσότητες οι οποίες μπορούν να επαναχρησιμοποιηθούν στον αλγόριθμο αποσύνθεσης, με σκοπό την επιτάχυνση του υπολογισμού του MTTKRP.
Τέλος, περιγράφουμε μια παράλληλη υλοποίηση σε κατανεμημένο περιβάλλον αυτού του αλγορίθμου, και παρουσιάζουμε αποτελέσματα για διάφορους τανυστές, και για ένα εύρος επεξεργαστών.
Abstract: Tensors are mathematical objects that have recently become popular in the fields of machine learning and signal processing. This is due to their ability to describe multi-way relations and dependencies. For a complete data set, where we have no missing entries, tensor decompositions can help us model the data set, while others give us the potential to perform compression. For a data set with missing entries, we can use decompositions to infer missing values. Tensors however, suffer from the curse of dimensionality. The number of elements increases exponentially with respect to the order of a tensor. As a result, it is necessary to develop fast and scalable algorithms to perform these decompositions.
In this thesis, we focus on the CP decomposition, or PARAFAC decomposition. We begin this work by introducing some definitions from linear algebra, followed by matrix least squares problems. These chapters are succeded by an introduction to tensor algebra, and a presentation of the PARAFAC decomposition. The problem we deal with in this thesis is the speeding of a matrix multiplication during the decomposition algorithm. This product is known in the bibliography as the matricized--tensor Khatri-Rao product (MTTKRP) and constitutes the computational bottleneck of the algorithm. To this end, we use a data structure called a dimension tree. The tree stores intermediate results that can be reused in the decomposition algorithm, in order to speed up the MTTKRP.
Finally, we describe a parallel implementation in a distributed environment of this algorithm, and present results for various tensors and a range of processors.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 137Π-39,-38
Έναρξη: 19/09/2019 11:00
Λήξη: 19/09/2019 12:00
