Μηχανική μάθηση PDF

Μηχανική μάθηση Ενισχυτική μάθηση  Τι είναι η ενισχυτική μάθηση; Ένα σύστημα (πράκτορας) αλληλοεπιδρά με το περιβάλλον εκτελώντας ενέργειες (actions) και λαμβάνοντας ανταμοιβές (rewards). Ενέργεια Πράκτορας Π...

Μηχανική μάθηση Ενισχυτική μάθηση  Τι είναι η ενισχυτική μάθηση; Ένα σύστημα (πράκτορας) αλληλοεπιδρά με το περιβάλλον εκτελώντας ενέργειες (actions) και λαμβάνοντας ανταμοιβές (rewards). Ενέργεια Πράκτορας Περιβάλλον Επόμενη Ανταμοιβή Κατάσταση Η ανταμοιβή μπορεί να μην είναι άμεσα διαθέσιμη και να προκύπτει στο τέλος κάποιας ακολουθίας ενεργειών, πχ. στο τέλος μιας παρτίδας παιχνιδιού (νίκη, ισοπαλία, ήττα). Το σύστημα μπορεί να είναι δυναμικό. Στόχοι μάθησης: § Να εκτιμηθεί η βέλτιστη πολιτική ενεργειών ώστε να μεγιστοποιηθεί η ανταμοιβή § Να εκτιμηθεί η κατανομή πιθανότητας των ανταμοιβών § Αν το σύστημα είναι δυναμικό να αποτιμηθεί η κατάστασή του ή να εκτιμηθεί η πιθανότητα μετάβασης στην επόμενη κατάσταση Μηχανική Μάθηση 2  Κίνητρο και εφαρμογές Νέα κλάση μεθόδων μάθησης διαφορετική από μάθηση με επίβλεψη ή τη μάθηση χωρίς επίβλεψη. Κεντρικές έννοιες: § Εξερεύνηση (Exploration): δοκιμή πολλών διαφορετικών ενεργειών ώστε να καταγραφεί η αντίδραση του περιβάλλοντος § Εκμετάλλευση (Exploitation): χρήση των εκτιμήσεών μας έτσι ώστε να επιλέξουμε τις καλύτερες ενέργειες § Δίλημμα εξερεύνησης/εκμετάλλευσης Εφαρμογές: § Ρομποτική § Λήψη αποφάσεων § Παιχνίδια Μηχανική Μάθηση 3  Περιγραφή προβλήματος μονόχειρων ληστών § Το απλούστερο πρόβλημα ενισχυτικής μάθησης. § Στατικό περιβάλλον χωρίς μνήμη § Ορισμός: Κάθε χρονική στιγμή !, σε μια χρονική ακολουθία ! = 1, … , &, πρέπει να επιλέξουμε 1 ανάμεσα από ' πιθανές ενέργειες. Έστω ((!) η ενέργεια που επιλέγουμε τη στιγμή !. Κάθε ενέργεια + δίνει μια ανταμοιβή , που εξαρτάται μόνο από το + (και όχι από το !). Έτσι έχουμε μια ακολουθία ανταμοιβών -(!): ( ! =+⇒- ! =, Η ανταμοιβή , είναι μια τυχαία μεταβλητή με άγνωστη κατανομή. Ζητάμε την αναμενόμενη ανταμοιβή με δεδομένο το +: / + = 0 - ! |( ! = + = 2 4 , + 5, 3 Στόχος είναι να επιλέξουμε μια ακολουθία ενεργειών ώστε να μεγιστοποιηθεί η συνολική αναμενόμενη ανταμοιβή για τη χρονική περίοδο &. Μηχανική Μάθηση 4  Παραδείγματα εφαρμογών Ιατρικές εφαρμογές: Έστω ότι έχουμε ! θεραπείες για την ίδια ασθένεια. Θέλουμε να βρούμε την καλύτερη θεραπεία για το μέσο πληθυσμό Δεν θέλουμε να δώσουμε κακές ή όχι βέλτιστες θεραπείες σε πολλούς ασθενείς Συστήματα συστάσεων: Θέλουμε να συστήσουμε ! προϊόντα σε χρήστες. Θέλουμε να βρούμε την καλύτερη σύσταση για το μέσο πληθυσμό Δεν θέλουμε να κάνουμε πολλές κακές συστάσεις στους χρήστες Δρομολόγηση (Δίκτυα υπολογιστών): Έχουμε ! δυνατές διαδρομές για ένα μήνυμα Θέλουμε να βρούμε την καλύτερη διαδρομή κατά μέσο όρο Δεν θέλουμε να κάνουμε πολλές κακές δοκιμές Μηχανική Μάθηση 5  Άλλες εφαρμογές Παιχνίδι “Go”. Πρόγραμμα “AlphaGo” της Deep Mind: μέθοδος Monte Carlo με βαθύ συνελικτικό δίκτυο για τη μοντελοποίηση της αξίας καταστάσεων. Νίκησε τον Fan Hui 5/0 και τον Lee Sedol 4/1. Η νεότερη έκδοση “AlphaGo Zero” νίκησε το “AlphaGo” 100/0 και το “AlphaGo Master” 89/11. Σύσταση περιεχομένου Web: Ποια σελίδα να συστήσουμε μεταξύ ! διαφορετικών σελίδων? → Πρόβλημα πολλαπλών μονόχειρων ληστών. Ανταμοιβή = Click-through rate = [αριθμός κλικ στη σελίδα]/[αριθμός επισκέψεων] Βελτιστοποίηση ελεγκτών μνήμης (Βελτιστοποίηση DRAM) Παίξιμο βίντεο-παιχνιδιών σε επίπεδο αντίστοιχο ή καλύτερο του ανθρώπου. Μηχανική Μάθηση 66  Άλλες εφαρμογές Ρομποτική (Έλεγχος βάδισης τετράποδου) Policy Gradient Reinforcement Learning for Fast Quadrupedal Locomotion by Nate Kohl and Peter Stone (Πιάσιμο μπάλας από τετράποδο) Learning Ball Acquisition on a Physical Robot by Peggy Fidelman and Peter Stone (Air Hockey) Learning from Observation Using Primitives, and particularly the movie of a humanoid robot playing air hockey. An example paper. (Active Sensing) Active Sensing Using Reinforcement Learning by Cody Kwok and Dieter Fox. Μηχανική Μάθηση 67  Άλλες εφαρμογές Έλεγχος (Έλεγχος ελικοπτέρων) Inverted autonomous helicopter flight via reinforcement learning, by Andrew Y. Ng, Adam Coates, Mark Diel, Varun Ganapathi, Jamie Schulte, Ben Tse, Eric Berger and Eric Liang. In International Symposium on Experimental Robotics, 2004. Autonomous helicopter control using Reinforcement Learning Policy Search Methods, by J.A. Bagnell and J. Schneider. In Proceedings of the International Conference on Robotics and Automation, 2001. Μηχανική Μάθηση 68  Other applications Επιχειρησιακή Έρευνα (Τιμολόγηση) Opportunities and Challenges in Using Online Preference Data for Vehicle Pricing: A Case Study at General Motors by P. Rusmevichientong, J. A. Salisbury, L. T. Truss, B. Van Roy, and P. W. Glynn. (Δρομολόγηση οχημάτων) Scaling Average-reward Reinforcement Learning for Product Delivery by S. Proper and P. Tadepalli. (Στοχευμένο μάρκετινγκ) Cross Channel Optimized Marketing by Reinforcement Learning, by Naoki Abe, Naval Verma, Chid Apte and Robert Schroko, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2004. Μηχανική Μάθηση 69  Άλλες εφαρμογές Παιχνίδια (Τάβλι) Temporal difference learning and TD-Gammon by Gerald Tesauro, Communications of the ACM, 38(3), March 1995. (Πασιέντζα) Solitaire: Man Versus Machine, by X. Yan, P. Diaconis, P. Rusmevichientong, and B. Van Roy, to appear in Advances in Neural Information Processing Systems 17, MIT Press, 2005. (Σκάκι) The KnightCap program, which went from a rating of 1600 to a rating of 2100 by altering its heuristic evaluation function using TD-lambda. pdf (Ντάμα) Temporal Difference Learning Applied to a High- Performance Game-Playing Program by Jonathan Schaeffer, Markian Hlynka, and Vili Jussila, International Joint Conference on Artificial Intelligence (IJCAI), pp. 529-534, 2001. Μηχανική Μάθηση 70  Άλλες εφαρμογές Human Computer Interaction (Συστήματα Προφορικού Διαλόγου) Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System. S. Singh, D. Litman, M. Kearns and M. Walker. In Journal of Artificial Intelligence Research (JAIR), Volume 16, pages 105-133, 2002 (Software Agent in MOOs) Cobot in LambdaMOO: An Adaptive Social Statistics Agent. C. Isbell, M. Kearns, S. Singh, C. Shelton, P. Stone and D. Korman. Μηχανική Μάθηση 71  Άλλες εφαρμογές Οικονομικά (Trading) Learning to Trade via Direct Reinforcement. John Moody and Matthew Saffell, IEEE Transactions on Neural Networks, Vol 12, No 4, July 2001. Σύνθετες προσομοιώσεις (Robot Soccer) Scaling Reinforcement Learning toward RoboCup Soccer, by Peter Stone and Richard S. Sutton, Proceedings of the Eighteenth International Conference on Machine Learning, pp. 537–544, Morgan Kaufmann, San Francisco, CA, 2001. Μηχανική Μάθηση 72  Ενέργειες και ανταμοιβές Ενέργεια 1 Ανταμοιβή Τραβώ μοχλό Jackpot με πιθαν. #" Αν ξέρουμε !" την αναμενόμενη ανταμοιβή για κάθε Ενέργεια 2 Ανταμοιβή ενέργεια Τραβώ μοχλό Jackpot με πιθαν. #$ τότε θα !$ επιλέγουμε πάντα την ενέργεια με Ενέργεια 3 την Ανταμοιβή Τραβώ μοχλό Jackpot με πιθαν. #% μεγαλύτερη !% ανταμοιβή Μηχανική Μάθηση 6  Εξερεύνηση εναντίον εκμετάλλευσης Εξερεύνηση: Καθώς αρχικά δεν ξέρουμε την κατανομή πιθανότητας για την ανταμοιβή καμίας ενέργειας, πρέπει να την εκτιμήσουμε κάνοντας δοκιμές Εκμετάλλευση: Αφού εκτιμήσουμε τις πιθανότητες ανταμοιβών εκμεταλλευόμαστε τη γνώση αυτή για να κάνουμε την καλύτερη επιλογή ενέργειας. Η Εξερεύνηση είναι απαραίτητη ώστε να συλλεχθούν στατιστικά για τις ανταμοιβές των ενεργειών και να εκτιμηθεί η ενέργεια με την μεγαλύτερη ανταμοιβή. Από την άλλη μεριά, κατά τη διάρκεια της εξερεύνησης μπορεί να δοκιμάζουμε μη βέλτιστες ενέργειες. Το δίλημμα Εξερεύνηση/Εκμετάλλευση: χωρίς εξερεύνηση κάνουμε ενέργειες στα τυφλά. Εφαρμόζοντας πολλή εξερεύνηση κάνουμε πολλές κακές ή μη βέλτιστες ενέργειες. Μηχανική Μάθηση 7  Απλοϊκή προσέγγιση Εξερευνούμε κάθε ενέργεια ! ένα συγκεκριμένο πλήθος φορών έτσι ώστε να εκτιμήσουμε την αναμενόμενη ανταμοιβή #(!). " Κατόπιν, θα επιλέγουμε συνεχώς την ενέργεια με την μεγαλύτερη αναμενόμενη ανταμοιβή: Διάλεξε μια ενέργεια ! επανειλημμένα & φορές Σύλλεξε στατιστικά και εκτίμησε την κατανομή της ανταμοιβής γι’ αυτή την ενέργεια Εκτίμησε την αναμενόμενη ανταμοιβή για την ενέργεια !: Άθροισμα ανταμοιβών (()) όταν επιλέγουμ* ! #" ! = Πλήθος φορών που επιλέξαμε ! Αφού υπολογίσουμε όλα τα #" 1 , … , #(.), " επιλέγουμε πάντα την ενέργεια !∗ με τη μεγαλύτερη αναμενόμενη ανταμοιβή #" !∗. Σημαντική παρατήρηση: έχουμε υποθέσει ότι η στατιστική συμπεριφορά των ανταμοιβών δεν εξαρτάται από το χρόνο 0 αλλά μόνο από την ενέργεια !. Μηχανική Μάθηση 8  Παράδειγμα: 3 bandits Έστω ότι έχουμε 3 δυνατές ενέργειες ! = 0, ! = 1, ! = 2, με ανταμοιβές που ακολουθούν την Γκαουσσιανή κατανομή Ανταμοιβή για ! = 0: & 0 ∼ ( ) = 7, , - = 1 Ανταμοιβή για ! = 1: & 1 ∼ ( ) = 8, , - = 1 Ανταμοιβή Ανταμοιβή για ! = 2: & 2 ∼ ( ) = 6, , - = 1 Ενέργεια Μηχανική Μάθηση 9  Παράδειγμα: 3 bandits Απλοϊκή προσέγγιση: Εξερεύνησε κάθε ενέργεια για 20 χρονικές στιγμές κάθε μια Μέση ανταμοιβή Mean rewards μετά after από 10001000 πειράματα experiments: Εξερεύνησε την ενέργεια 0 Ανταμοιβή 0 Μηχανική Μάθηση 10  Παράδειγμα: 3 bandits Απλοϊκή προσέγγιση: Εξερεύνησε κάθε ενέργεια για 20 χρονικές στιγμές κάθε μια Μέση ανταμοιβή Mean rewards μετά after από 10001000 πειράματα experiments: Εξερεύνησε την ενέργεια 1 1 Ανταμοιβή Μηχανική Μάθηση 11  Παράδειγμα: 3 bandits Απλοϊκή προσέγγιση: Εξερεύνησε κάθε ενέργεια για 20 χρονικές στιγμές κάθε μια Ανταμοιβή Μέση ανταμοιβή Mean rewards μετά after από 10001000 πειράματα experiments: Εξερεύνησε την ενέργεια 2 2 Μηχανική Μάθηση 12  Παράδειγμα: 3 bandits Απλοϊκή προσέγγιση: Εξερεύνησε κάθε ενέργεια για 20 χρονικές στιγμές κάθε μια Μέση ανταμοιβή Mean rewards μετά after από 10001000 πειράματα experiments: Επίλεγε πάντα την ενέργεια 1 διότι έχει τη 1 μεγαλύτερη αναμενόμενη ανταμοιβή Ανταμοιβή Μηχανική Μάθηση 13  Άπληστος αλγόριθμος Εναλλακτικά μπορούμε να εκμεταλλευόμαστε αμέσως τη γνώση που έχουμε συλλέξει μέχρι στιγμής. Αυτό σημαίνει ότι έχουμε μια εκτίμηση "̂ # $ της αναμενόμενης ανταμοιβής για κάθε ενέργεια $ τη στιγμή % με βάση τις μέχρι τώρα παρατηρήσεις μας. Άθροισμα ανταμοιβών ' ( όταν επιλέγω ) πριν τη στιγµή # "̂ # $ = Πλήθος φορών που επέλεξα ) πριν τη στιγμή # ∑;