Χρήστης:Vtoutz/πρόχειρο

Μέθοδος Μόντε Κάρλο

Οι μέθοδοι Μόντε Κάρλο (Monte Carlo) είναι μεγάλη κατηγορία υπολογιστικών αλγορίθμων που στηρίζονται σε τυχαία δειγματοληψία με σκοπό την εξαγωγή αριθμητικών αποτελεσμάτων.^[1]

Κοινό στοιχείο σε πολλά προβλήματα μελέτης στοχαστικών συστημάτων είναι η αριθμητική τους επίλυση με μεθόδους Μόντε Κάρλο. Βασικό χαρακτηριστικό των στοχαστικών μαθηματικών μοντέλων αποτελεί η τυχαιότητα στις μεταβλητές οι οποίες ακολουθούν συνήθως μια συγκεκριμένη κατανομή πιθανότητας.Πρακτικά γίνεται χρήση της τυχαιότητας για να επιλυθούν προβλήματα ντετερμινιστικής φύσεως.

Τα περισσότερα προβλήματα στα οποία βρίσκουν επίλυση οι μέθοδοι Μόντε Κάρλο μπορούν να κατηγοριοποιηθούν ως εξής:

Υπολογισμός ολοκληρωμάτων (Ολοκλήρωση Monte Carlo): Δηλαδή ο υπολογισμός αναμενόμενων τιμών (expected values) συναρτήσεων μιας ή περισσοτέρων ανεξάρτητων (τυχαίων) μεταβλητών.
Εύρεση ελαχίστου ή μεγίστου συναρτήσεων (Βελτιστοποίηση Monte Carlo): Σε πολλά προβλήματα κυρίως από τη βελτιστοποίηση διεργασιών, καταλήγουμε σε υπολογισμούς που αφορούν ακρότατα συναρτήσεων.^[1]

Κοινό στοιχείο σε ζητήματα που αφορούν ολοκλήρωση Μόντε Κάρλο αποτελεί η δημιουργία τυχαίων αριθμών από μία κατανομή μέσω μιας Γεννήτριας, δηλαδή η δειγματοληψία της συγκεκριμένης κατανομής.

Γεννήτρια Τυχαίων Αριθμών ονομάζεται ο αλγόριθμος δημιουργίας τυχαίων αριθμών σε κάποιο διάστημα ακολουθώντας κανονική κατανομή. Συνήθως το διάστημα είναι το [0,1] και οι αριθμοί δημιουργούνται ούτως ώστε να ακολουθούν Ομοιόμορφη Κατανομή (Uniform Distribution) , δηλαδή την U[0,1].^[1]

Η κεντρική ιδέα της μεθόδου είναι η επανάληψη ενός πειράματος πολλές φορές μέχρι να προκύψουν κάποια αποτελέσματα, κάνοντας χρήση του Νόμου των Μεγάλων Αριθμών καθώς και άλλες μεθόδους στατιστικής συμπερασματολογίας.

Από μαθηματική άποψη μπορούμε να αντιληφθούμε τη μεθοδολογία ως εξής : οτιδήποτε χρειάζεται να γνωρίζουμε για μία τυχαία μεταβλητή Χ μπορούμε να το μάθουμε μέσα από την επαναλαμβανόμενη δειγματοληψία στη συνάρτηση κατανομής της Χ, δηλαδή την F(X).^[2]

Οι μέθοδοι Μόντε Κάρλο είναι αρκετά δημοφιλείς για τους εξής λόγους:

Ευκολία και Αποδοτικότητα : Οι αλγόριθμοι Μόντε Κάρλο τείνουν να είναι απλοί, ευέλικτοι και επιδέχονται περαιτέρω ανάπτυξης. Όταν εφαρμόζονται σε φυσικά συστήματα, οι τεχνικές Μόντε Κάρλο μπροούν να περιορίσουν πολύπλοκα μοντέλα σε μια σειρά βασικών γεγονότων και αλληλεπιδράσεων. Έτσι παρέχεται η δυνατότητα να κωδικοποιηθεί η συμπεριφορά ενός μοντέλου μέσα από μια σειρά κανόνων πλήρως εφαρμοσμένων σε ηλεκτρονικό υπολογιστή. Κατ’επέκταση, πολύ γενικά μοντέλα υψηλής τυχαιότητας μπορούν να εφαρμοστούν και να μελετηθούν σε υπολογιστή ευκολότερα από ότι με τη χρήση αναλυτικών μεθόδων. Επίσης, οι αλγόριθμοι Μόντε Κάρλο είναι εξαιρετικά αποδοτικοί, αφού προσφέρουν τη δυνατότητα παράλληλου υπολογισμού. Συγκεκριμένα, μπορεί να γίνει καταμερισμός σε μικρότερες εργασίες και κάθε εργασία να διεκπεραιώνεται παράλληλα σε διαφορετικούς υπολογιστές ή επεξεργαστές, μειώνοντας κατά πολύ τον υπολογιστικό χρόνο.
Τυχαιότητα: Η έμφυτη τυχαιότητα των Μόντε Κάρλο μεθόδων δεν είναι μόνο απαραίτητη για την προσομοίωση ρεαλιστικών μοντέλων, αλλά αποτελεί και ένα μεγάλο πλεονέκτημα για ντετερμινιστικούς αριθμητικούς υπολογισμούς. Π.χ. η τυχαιότητα επιτρέπει στους στοχαστικούς αλγοριθμους να διαφεύγουν τοπικά ακρότατα και έτσι ευνοείται η ανακάλυψη μεγαλύτερου χώρου στο μοντέλο.
Έρευνα: Υπάρχει έντονη δραστηριότητα για μαθηματική και στατιστική υποστήριξη των τεχνικών Μόντε Κάρλο, προκειμένου να αυξηθεί η ακρίβεια των εκτιμητών Μόντε Κάρλο και της αποδοτικότητας των αλγορίθμων. Ταυτόχρονα, ερευνώνται σειρές κανόνων και παραμέτρων ώστε να μειωθεί ο χρόνος υπολογισμού και να αυξηθεί η βελτιστοποιήση.^[3]

Οι αλγόριθμοι Μόντε Κάρλο χρησιμοποιούνται ευρέως σε προβλήματα φυσικής, μηχανικής, επιστήμης υπολογιστών, χρηματοοικονομικών, εφαρμοσμένης στατιστικής, κοινωνικών επιστημών, καθώς και στην υπολογιστική βιολογία και στην βιοπληροφορική.^[4]^[5]

Μαρκοβιανή αλυσίδα Μόντε Κάρλο (Markov Chain Monte Carlo , MCMC)

Όταν η κατανομή πιθανότητας της μεταβλητής είναι παραμετροποιημένη, πολλές φορές γίνεται χρήση της Mαρκοβιανής Αλυσίδας Μόντε Κάρλο.

Οι μέθοδοι Μαρκοβιανής αλυσίδας Μόντε Κάρλο (Markov chain Monte Carlo, MCMC) βασίζονται στη δημιουργία μιας λογικής μαρκοβιανής αλυσίδας με μια προκαθορισμένη στάσιμη κατανομή πιθανότητας.

Όπως αναφέρθηκε προηγουμένως, ο Νόμος των Μεγάλων Αριθμών αποτελεί τη βάση των μεθόδων Μόντε Κάρλο και μπορεί να εφαρμοστεί εξίσου και στις μεθόδους MCMC καθώς αυτό μας επιτρέπει να αγνοήσουμε παντελώς την εξάρτηση μεταξύ των τιμών της μαρκοβιανής αλυσίδας, αφού μπορούμε να υπολογίσουμε από τις τιμές τα χαρακτηριστικά που μας ενδιαφέρουν. Κοινώς, αν γνωρίζουμε τη στάσιμη κατανομή της αλυσίδας τότε μπορούμε να λάβουμε πληροφορίες για χαρακτηριστικά όπως πληθυσμιακός μέσος, τυπική απόκλιση κλπ, απλά περιμένοντας να συγκλίνει η αλυσίδα δηλαδή να επιτευχθεί στασιμοτητα ή ισορροπία.

Είναι επιθυμητό οι τιμές του δείγματος να προσομοιάζουν τις τιμές από τη ζητούμενη συνάρτηση κατανομής.

Η αρχή λειτουργίας των MCMC μεθόδων μπορεί να περιγραφεί συνοπτικά ως εξής:

Έστω ότι γνωρίζουμε μια συνάρτηση πυκνότητας πιθανότητας ή μια συνάρτηση μάζας πιθανότητας, την f, τότε δημιουργούμε ένα μαρκοβιανό πυρήνα Κ με μία στάσιμη κατανομή και μετά παράγουμε μία μαρκοβιανή αλυσίδα {Χ_t} κάνοντας χρήση του πυρήνα έτσι ώστε η στάσιμη κατανομή να είναι η f.Η μεγαλύτερη δυσκολία έγκειται στην κατασκευή του πυρήνα Κ.

Η συνθήκη της εργοδικότητας είναι απαραίτητη έτσι ώστε η Μαρκοβιανή αλυσίδα να μπορεί να περάσει από όλες τις δυνατές καταστάσεις με πεπερασμένο πλήθος βημάτων.

Πιθανά προβλήματα των MCMC μεθόδων:

Συνήθως χρειάζεται πολύ μεγάλο χρονικό διάστημα μέχρι η μαρκοβιανή αλυσίδα να συγκλίνει στη στάσιμη κατανομή της.
Τα αποτελέσματα που προκύπτουν από MCMC δειγματοληψίες έχουν συχνά μεγαλύτερη διασπορά σε σχέση με δείγματα που προκύπτουν από δειγματοληψία ανεξάρτητων και ισόνομων δειγμάτων.
Επίσης, τα δείγματα που προκύπτουν από μια δειγματοληψία μεθόδου MCMC έχουν μεγάλη συσχέτιση μεταξύ τους.

Αλγόριθμος Metropolis-Hastings

Βασική ιδέα του αλγορίθμου Metropolis-Hastings είναι η προσομοίωση μιας αλυσίδας Μαρκόφ με στάσιμη κατανομή (δηλαδή την κατανομή στόχο). Χρησιμοποιείται επίσης μια κατανομή δικής μας πρότασης.Από τον αλγόριθμο Metropolis-Hastings προκύπτει μία αλυσίδα Μαρκόβ καθώς η τελική τιμή εξαρτάται μόνο από την τωρινή κατάσταση και όχι από τις προηγούμενες καταστάσεις.

Ο αλγόριθμος Metropolis-Hastings είναι στην ουσία μια διαδικασία αποδοχής-απόρριψης.

Το πρώτο βήμα είναι να επιλέξουμε ένα αυθαίρετο σημείο εκκίνησης. Στη συνέχεια μετά από κάθε βήμα i η κατάσταση της αλυσίδας προσομοιώνεται ως εξής: κάθε βήμα παρέχει μία υποψήφια κατάσταση και αυτή γίνεται αποδεκτή ή απορριπτέα. Το κριτήριο αποδοχής εξαρτάται από τη συνάρτηση πυκνότητας πιθανότητας. Αν η τωρινή κατάσταση έχει μεγαλύτερη συνάρτηση πυκνότητας πιθανότητας από την προηγούμενη τότε η τωρινή είναι αποδεκτή. Όταν η τωρινή κατάσταση δεν είναι αποδεκτή, απορρίπτεται και τότε η προηγούμενη κατάσταση επαναλαμβάνεται.

Ένα από τα σημαντικότερα πλεονεκτήματα του αλγορίθμου Metropolis-Hastings είναι ότι εξασφαλίζει υπό ελάχιστες συνθήκες τη σύγκλιση μιας ακολουθίας η οποία προσομοιώνεται στην κατανομή στόχο που θέτουμε. Επίσης, είναι αρκετά δημοφιλής διότι σε πάρα πολλά ρεαλιστικά προβλήματα αρκεί να γνωρίζουμε την συναρτησιακή μορφή της κατανομής στόχου και της κατανομής-πρότασης, αφού ο αναλυτικός υπολογισμός αυτών των σταθερών είναι εξαιρετικά δύσκολος και σε πολλές περιπτώσεις αδύνατος.

Μια ειδική περίπτωση του αλγορίθμου Metropolis-Hastings είναι ο λεγόμενος τυχαίος περίπατος (random walk).

↑ ^1,0 ^1,1 ^1,2 1. Κομηνέας Σ., 2. Χαρμανδάρης Ε. (2016). Στοχαστικά Συστημάτα – Μέθοδοι Monte Carlo. ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ ΚΑΙ ΕΦΑΡΜΟΣΜΕΝΩΝ ΜΑΘΗΜΑΤΙΚΩΝ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ. σελ. 151.
↑ Ταπίρη Ε. (2013). «Στοχαστική προσομοίωση με μεθόδους Markov Chain Monte Carlo (MCMC)» (PDF).
↑ Kroese, Dirk P.; Brereton, Tim; Taimre, Thomas; Botev, Zdravko I. (2014-06-20). «Why the Monte Carlo method is so important today» (στα αγγλικά). Wiley Interdisciplinary Reviews: Computational Statistics 6 (6): 386–392. doi:10.1002/wics.1314. ISSN 1939-5108. https://onlinelibrary.wiley.com/doi/abs/10.1002/wics.1314.
↑ Ρούσσος Ι. (2009). «Μελέτη των Self – avoiding Random Walks» (PDF).
↑ Mode, Charles (2011). Applications of Monte Carlo Methods in Biology, Medicine and Other Fields of Science. Ινδία. σελ. 1. ISBN 978-953-307-427-6.

[:0-1] 1,0 ^1,1 ^1,2 1. Κομηνέας Σ., 2. Χαρμανδάρης Ε. (2016). Στοχαστικά Συστημάτα – Μέθοδοι Monte Carlo. ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ ΚΑΙ ΕΦΑΡΜΟΣΜΕΝΩΝ ΜΑΘΗΜΑΤΙΚΩΝ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ. σελ. 151.

[2] Ταπίρη Ε. (2013). «Στοχαστική προσομοίωση με μεθόδους Markov Chain Monte Carlo (MCMC)» (PDF).

[3] Kroese, Dirk P.; Brereton, Tim; Taimre, Thomas; Botev, Zdravko I. (2014-06-20). «Why the Monte Carlo method is so important today» (στα αγγλικά). Wiley Interdisciplinary Reviews: Computational Statistics 6 (6): 386–392. doi:10.1002/wics.1314. ISSN 1939-5108. https://onlinelibrary.wiley.com/doi/abs/10.1002/wics.1314.

[4] Ρούσσος Ι. (2009). «Μελέτη των Self – avoiding Random Walks» (PDF).

[5] Mode, Charles (2011). Applications of Monte Carlo Methods in Biology, Medicine and Other Fields of Science. Ινδία. σελ. 1. ISBN 978-953-307-427-6.

[1]

[2]

[3]

[4]

[5]