Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/3867AFDB-00B1-4B4A-9A71-A2965C218584 | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.83406 | - |
| Γλώσσα | en | - |
| Μέγεθος | 65 pages | el |
| Τίτλος | Αποδοτικοί παράλληλοι αλγόριθμοι για επεξεργασία τανυστών και υλοποίηση σε κατανεμημένα περιβάλλοντα | el |
| Τίτλος | Efficient parallel algoriths for tensor decompositions and implementation in distributed environments | en |
| Δημιουργός | Kolomvakis Christos | en |
| Δημιουργός | Κολομβακης Χρηστος | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Liavas Athanasios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Λιαβας Αθανασιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Karystinos Georgios | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Καρυστινος Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Samoladas Vasilis | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Σαμολαδας Βασιλης | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | Οι τανυστές είναι μαθηματικές δομές οι οποίες έχουν γίνει τα τελευταία χρόνια δημοφιλείς στα πεδία της επεξεργασίας σήματος και της μηχανικής μάθησης. Αυτό είναι λόγω της ικανότητάς τους να μπορούν να μοντελοποιούν τις σχέσεις και τις εξαρτήσεις μεταξύ πολλών αντικειμένων. Για ένα πλήρες data set, όπου δεν υπάρχουν στοιχεία που δεν μας είναι διαθέσιμα, οι αποσυνθέσεις τανυστών μας δίνουν την δυνατότητα να κάνουμε μοντελοποίηση των δεδομένων, ενώ κάποιες συγκεκριμένες αποσυνθέσεις μας δίνουν την δυνατότητα να πετύχουμε συμπίεση των δεδομένων. Για ένα data set στο οποίο λείπουν στοιχεία, μπορούμε να χρησιμοποιήσουμε αποσυνθέσεις έτσι ώστε να συμπεράνουμε στοιχεία που λείπουν. Οι τανυστές ωστόσο πάσχουν από την “κατάρα της διαστατικότητας”. Ο αριθμός των στοιχείων ενός τανυστή αυξάνεται εκθετικά με την τάξη του, και ως αποτέλεσμα, υπάρχει η ανάγκη για την ανάπτυξη αποδοτικών αλγορίθμων που πραγματοποιούν τις αποσυνθέσεις. Σε αυτήν την εργασία, θα επικεντρωθούμε στην αποσύνθεση CP ή PARAFAC. Αρχικά αναφέρουμε κάποιες έννοιες από την γραμμική άλγεβρα, και στην συνέχεια αναφερόμαστε σε προβλήματα ελαχίστων τετραγώνων για πίνακες. Μετά από μία εισαγωγή στην άλγεβρα τανυστών, παρουσιάζουμε την αποσύνθεση PARAFAC. Το πρόβλημα που καλούμαστε να αντιμετωπίσουμε είναι η επιτάχυνση ενός πολλαπλασιασμού πινάκων κατά την διάρκεια του αλγορίθμου αποσύνθεσης. Το γινόμενο είναι γνωστό στην βιβλιογραφία ως matricized—tensor Khatri—Rao product (MTTKRP) και αποτελεί το πιο απαιτητικό υπολογιστικά στάδιο του αλγορίθμου. Προς αυτό τον σκοπό, χρησιμοποιούμε μια δομή η οποία λέγεται dimension tree. Το δέντρο αποθηκεύει ποσότητες οι οποίες μπορούν να επαναχρησιμοποιηθούν στον αλγόριθμο αποσύνθεσης, με σκοπό την επιτάχυνση του υπολογισμού του MTTKRP. Τέλος, περιγράφουμε μια παράλληλη υλοποίηση σε κατανεμημένο περιβάλλον αυτού του αλγορίθμου, και παρουσιάζουμε αποτελέσματα για διάφορους τανυστές, και για ένα εύρος επεξεργαστών. | el |
| Περίληψη | 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. | en |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2019-10-04 | - |
| Ημερομηνία Δημοσίευσης | 2019 | - |
| Θεματική Κατηγορία | Αποσυνθέσεις τανυστών | el |
| Θεματική Κατηγορία | Optimization | en |
| Θεματική Κατηγορία | Tensor decompositions | en |
| Θεματική Κατηγορία | Βελτιστοποίηση | el |
| Θεματική Κατηγορία | Distributed computing | en |
| Θεματική Κατηγορία | Προγραμματισμός σε κατανεμημένα περιβάλλοντα | el |
| Βιβλιογραφική Αναφορά | Χρήστος Κολομβάκης, "Αποδοτικοί παράλληλοι αλγόριθμοι για επεξεργασία τανυστών και υλοποίηση σε κατανεμημένα περιβάλλοντα", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019 | el |
| Βιβλιογραφική Αναφορά | Christos Kolomvakis, "Efficient parallel algoriths for tensor decompositions and implementation in distributed environments ", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2019 | en |
Copyright © DIAS 2013
