Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων
Κύριος στόχος της παρούσας διπλωματικής εργασίας είναι η ανάλυση κάποιων βασικών μεθόδων επίλυσης αραιών γραμμικών συστημάτων καθώς και η δημιουργία, με χρήση τεχνικών μηχανικής μάθησης, ενός μοντέλου στο οποίο όταν δοθεί σαν είσοδος ένα αραιό γραμμικό σύστημα θα προτείνει μία από τις παραπάνω μεθόδ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2017
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/10473 |
| id |
nemertes-10889-10473 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Αραιά συστήματα γραμμικών εξισώσεων Μηχανική μάθηση Sparse linear systems Machine learning 003.74 |
| spellingShingle |
Αραιά συστήματα γραμμικών εξισώσεων Μηχανική μάθηση Sparse linear systems Machine learning 003.74 Κωτσαλένης, Χρήστος Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| description |
Κύριος στόχος της παρούσας διπλωματικής εργασίας είναι η ανάλυση κάποιων βασικών μεθόδων επίλυσης αραιών γραμμικών συστημάτων καθώς και η δημιουργία, με χρήση τεχνικών μηχανικής μάθησης, ενός μοντέλου στο οποίο όταν δοθεί σαν είσοδος ένα αραιό γραμμικό σύστημα θα προτείνει μία από τις παραπάνω μεθόδους ως βέλτιστη για την επίλυσή του.
Αρχικά, παρουσιάζεται το απαραίτητο θεωρητικό υπόβαθρο για την κατανόηση των μεθόδων επίλυσης αραιών γραμμικών συστημάτων οι οποίες αναλύονται στη συνέχεια της διπλωματικής εργασίας. Πιο συγκεκριμένα, παρουσιάζονται κάποιες βασικές έννοιες της γραμμικής άλγεβρας σχετικά με τα διανύσματα, τα μητρώα, τους διανυσματικούς χώρους και τις προβολές.
Έπειτα, ακολουθεί μια αναφορά στα γραμμικά συστήματα εξισώσεων και αναλύονται οι βασικές τεχνικές αποθήκευσης αραιών μητρώων και οι επαναληπτικές μέθοδοι Generalized Minimal Residual , Conjugate Gradient, Biconjugate Gradient και Quasi Minimal Residual οι οποίες αναζητούν την προσεγγιστική λύση σε κάποιον υπόχωρο Krylov για την επίλυση αραιών γραμμικών συστημάτων.
Στη συνέχεια της διπλωματικής εργασίας γίνεται μια εισαγωγή στη μηχανική μάθηση η οποία αποτελεί έναν από τους βασικότερους κλάδους της Υπολογιστικής Νοημοσύνης. Δίνεται ιδιαίτερη έμφαση στην επιβλεπόμενη μάθηση και στο πρόβλημα της κατηγοριοποίησης. Παρουσιάζονται κάποιες εκ των βασικών προσεγγίσεων της επίλυσης του παραπάνω προβλήματος, όπως είναι τα Δέντρα Απόφασης, τα Τεχνητά Νευρωνικά Δίκτυα, η οικογένεια Μπεϋζιανών Ταξινομητών, οι Μηχανές Διανυσμάτων Υποστήριξης και ο αλγόριθμος των k- Κοντινότερων Γειτόνων. Επιπλέον, περιγράφεται η παλινδρόμηση ως μορφή επιβλεπόμενης μάθησης και αναλύονται οι αλγόριθμοι Linear Regression και Μ5.
Στο τελευταίο μέρος της εργασίας παρουσιάζεται η υλοποίηση ενός μοντέλου κατηγοριοποίησης για την επιλογή της βέλτιστης μεθόδου επίλυσης, από τις μεθόδους που χρησιμοποιήσαμε, όταν δοθεί σαν είσοδος ένα αραιό σύστημα γραμμικών εξισώσεων. Στην λήψη της απόφασης, λαμβάνονται υπόψη οι ιδιότητες (δείκτης κατάστασης, ίχνος, Ευκλείδεια νόρμα κ.α) του μητρώου των συντελεστών των αγνώστων ώστε με βάση αυτές να επιλεγεί η καταλληλότερη μέθοδος από άποψη χρόνου επίλυσης. Επιπλέον, κατασκευάζονται και τρία μοντέλα παλινδρόμησης, για πρόβλεψη του χρόνου επίλυσης ενός δοθέντος αραιού γραμμικού συστήματος με την χρήση των μεθόδων Biconjugate Gradient, Quasi Minimal Residual και Generalized Minimal Residual αντίστοιχα. |
| author2 |
Γράψα, Θεοδούλα |
| author_facet |
Γράψα, Θεοδούλα Κωτσαλένης, Χρήστος |
| format |
Thesis |
| author |
Κωτσαλένης, Χρήστος |
| author_sort |
Κωτσαλένης, Χρήστος |
| title |
Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| title_short |
Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| title_full |
Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| title_fullStr |
Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| title_full_unstemmed |
Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| title_sort |
χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων |
| publishDate |
2017 |
| url |
http://hdl.handle.net/10889/10473 |
| work_keys_str_mv |
AT kōtsalenēschrēstos chrēsētechnikōnmēchanikēsmathēsēsgiatēnepilogēbeltistoualgorithmougiatēnepilysēaraiōngrammikōnsystēmatōn AT kōtsalenēschrēstos useofmachinelearningtechniquesforselectingtheoptimalalgorithmforsolvingsparselinearsystems |
| _version_ |
1771297195657527296 |
| spelling |
nemertes-10889-104732022-09-05T09:41:47Z Χρήση τεχνικών μηχανικής μάθησης για την επιλογή βέλτιστου αλγόριθμου για την επίλυση αραιών γραμμικών συστημάτων Use of machine learning techniques for selecting the optimal algorithm for solving sparse linear systems Κωτσαλένης, Χρήστος Γράψα, Θεοδούλα Κωτσιαντής, Σωτήρης Ανδρουλάκης, Γεώργιος Kotsalenis, Christos Αραιά συστήματα γραμμικών εξισώσεων Μηχανική μάθηση Sparse linear systems Machine learning 003.74 Κύριος στόχος της παρούσας διπλωματικής εργασίας είναι η ανάλυση κάποιων βασικών μεθόδων επίλυσης αραιών γραμμικών συστημάτων καθώς και η δημιουργία, με χρήση τεχνικών μηχανικής μάθησης, ενός μοντέλου στο οποίο όταν δοθεί σαν είσοδος ένα αραιό γραμμικό σύστημα θα προτείνει μία από τις παραπάνω μεθόδους ως βέλτιστη για την επίλυσή του. Αρχικά, παρουσιάζεται το απαραίτητο θεωρητικό υπόβαθρο για την κατανόηση των μεθόδων επίλυσης αραιών γραμμικών συστημάτων οι οποίες αναλύονται στη συνέχεια της διπλωματικής εργασίας. Πιο συγκεκριμένα, παρουσιάζονται κάποιες βασικές έννοιες της γραμμικής άλγεβρας σχετικά με τα διανύσματα, τα μητρώα, τους διανυσματικούς χώρους και τις προβολές. Έπειτα, ακολουθεί μια αναφορά στα γραμμικά συστήματα εξισώσεων και αναλύονται οι βασικές τεχνικές αποθήκευσης αραιών μητρώων και οι επαναληπτικές μέθοδοι Generalized Minimal Residual , Conjugate Gradient, Biconjugate Gradient και Quasi Minimal Residual οι οποίες αναζητούν την προσεγγιστική λύση σε κάποιον υπόχωρο Krylov για την επίλυση αραιών γραμμικών συστημάτων. Στη συνέχεια της διπλωματικής εργασίας γίνεται μια εισαγωγή στη μηχανική μάθηση η οποία αποτελεί έναν από τους βασικότερους κλάδους της Υπολογιστικής Νοημοσύνης. Δίνεται ιδιαίτερη έμφαση στην επιβλεπόμενη μάθηση και στο πρόβλημα της κατηγοριοποίησης. Παρουσιάζονται κάποιες εκ των βασικών προσεγγίσεων της επίλυσης του παραπάνω προβλήματος, όπως είναι τα Δέντρα Απόφασης, τα Τεχνητά Νευρωνικά Δίκτυα, η οικογένεια Μπεϋζιανών Ταξινομητών, οι Μηχανές Διανυσμάτων Υποστήριξης και ο αλγόριθμος των k- Κοντινότερων Γειτόνων. Επιπλέον, περιγράφεται η παλινδρόμηση ως μορφή επιβλεπόμενης μάθησης και αναλύονται οι αλγόριθμοι Linear Regression και Μ5. Στο τελευταίο μέρος της εργασίας παρουσιάζεται η υλοποίηση ενός μοντέλου κατηγοριοποίησης για την επιλογή της βέλτιστης μεθόδου επίλυσης, από τις μεθόδους που χρησιμοποιήσαμε, όταν δοθεί σαν είσοδος ένα αραιό σύστημα γραμμικών εξισώσεων. Στην λήψη της απόφασης, λαμβάνονται υπόψη οι ιδιότητες (δείκτης κατάστασης, ίχνος, Ευκλείδεια νόρμα κ.α) του μητρώου των συντελεστών των αγνώστων ώστε με βάση αυτές να επιλεγεί η καταλληλότερη μέθοδος από άποψη χρόνου επίλυσης. Επιπλέον, κατασκευάζονται και τρία μοντέλα παλινδρόμησης, για πρόβλεψη του χρόνου επίλυσης ενός δοθέντος αραιού γραμμικού συστήματος με την χρήση των μεθόδων Biconjugate Gradient, Quasi Minimal Residual και Generalized Minimal Residual αντίστοιχα. The aim of this thesis is the analysis of some basic methods of solving sparse linear systems and the creation, by the use of machine learning techniques, of a model in which when given as input a sparse linear system will recommend one of the above methods as best to solve it. In the first part, is presented the necessary theoretical background for understanding the methods of solving sparse linear systems which are analyzed in the thesis. Specifically, some basic concepts of linear algebra on vectors, matrices, vector spaces and projections are presented. Then follows a reference to systems of linear equations and are analyzed the main storage techniques for sparse matrices and the iterative methods Generalized Minimal Residual, Conjugate Gradient, Biconjugate Gradient and Quasi Minimal Residual which search for an approximate solution from a krylov subspace for solving a sparse linear system. Next, there is an introduction to machine learning which is one of the main subfields of Computational Intelligence. There is particular emphasis on supervised learning and the problem of classification. Moreover, some of the main approaches for solving the above problem such as Decision Trees, Artificial Neural Networks, the family of Bayesian classifiers, the Support Vector Machines and the algorithm of k- nearest neighbors are presented. Moreover, regression as a form of supervised learning is described and the algorithms Linear Regression and M5 are presented. In the last part of the thesis is presented the implementation of a classification model for selecting the optimal solving method from the methods used, when given as input a sparse system of linear equations. In making the decision, taking into account the properties (condition number, trace, Euclidean norm, etc.) of the coefficient matrix and based on them the model select the most suitable method in terms of solving time. Furthermore, three regression models are created in order to predict the solving time of a given sparse linear system using the methods Biconjugate Gradient, Quasi Minimal Residual and Generalized Minimal Residual respectively. 2017-08-22T06:41:03Z 2017-08-22T06:41:03Z 2017-05-02 Thesis http://hdl.handle.net/10889/10473 gr 0 application/pdf |
