Μέθοδοι ενισχυτικής μάθησης σε συστήματα πρακτόρων

Abstract

This dissertation pertains to the area of Machine Learning and especially to the subfield of Reinforcement Learning. Reinforcement learning comprises an appealing solution to problems with limited environmental feedback. The reinforcement learning framework provides the appropriate tools for solving complex problems, unlike other machine learning frameworks where correct labeled examples are necessary. For example, it is possible that the environment that an autonomous agent will act, may be unknown. Despite the research efforts and the successes in reinforcement learning, several research topics are still open. The contribution of this thesis is two-fold: a) it concerns the deployment of methods in multiagent systems and b) it uses the reinforcement learning framework to solve complex problems like focused crawling and ensemble pruning. Firstly, the thesis concentrates on the problem of coordinating a group of autonomous agents in order to achieve a common goal. For dealing with this problem, a reinforcement learning method is presented that is based on learning a set of strategies. Using a fusion procedure the individual decisions are combined, in order to follow a common strategy. Additionally, a method is presented for accelerating the learning procedure in reinforcement learning agents that can be applied in both multiagent and single agent systems. The proposed method uses multiple mapping functions, in order to transfer knowledge from a source task to a more complicated target task. Furthermore, an approach for focused crawling is proposed, which is based on the reinforcement learning framework. More specifically, the proposed approach learns a policy of selecting an appropriate classifier for link scoring during the crawling process. This is an indirect way to face the problem of focused crawling, without requiring the direct learning of selecting a link to follow or not. Finally, the problem of pruning an ensemble of classifiers is modeled as a reinforcement learning problem. The agent learns a policy of inserting or not a classifier in the ensemble. The proposed approach uses a general definition of the reward function in order to stress the capability of using different instantiations of the performance metric, the performance evaluation method depending on the requirements of the domain or the preferences of the data analyst. Additionally, a taxonomy of the existing ensemble pruning methods is proposed.

Η παρούσα διατριβή εντάσσεται στον χώρο της μηχανικής μάθησης και ιδιαίτερα την υπο- περιοχή της ενισχυτικής μάθησης. Η ενισχυτική μάθηση αποτελεί μια βασική προσέγγιση εκπαίδευσης αυτόνομων πρακτόρων οι οποίοι λαμβάνουν περιορισμένη πληροφορία για την εκπαίδευσή τους από το περιβάλλον. Το πλαίσιο της ενισχυτική μάθησης παρέχει τη δυνατό- τητα λύσης πολύπλοκων προβλημάτων χωρίς την προϋπόθεση εξωτερικής επίβλεψης που συναντάται σε άλλες οικογένειες μεθόδων μηχανικής μάθησης (π.χ. εκμάθηση ταξινομη- τών). Αυτό είναι σημαντικό γιατί το το περιβάλλον στο οποίο πρόκειται να δραστηριοποι- ηθεί ένα αυτόνομος πράκτορας συχνά δεν είναι γνωστό εκ των προτέρων. Παρά τη μεγάλη ερευνητική δραστηριότητα και τις επιτυχίες σε διάφορα πεδία, πολλά ερευνητικά θέματα παραμένουν ανοιχτά στον χώρο της ενισχυτικής μάθησης. Η παρούσα διατριβή κινείται σε δύο άξονες: α) στην ανάπτυξη μεθόδων για συστήματα πολλαπλών πρακτόρων και β) στην μοντελοποίηση πολύπλοκων προβλημάτων μέσω της ενισχυτικής μάθησης. Αρχικά, η διατριβή επικεντρώνεται στο πρόβλημα του συντονισμού μιας ομάδας πρα- κτόρων για την επίτευξη ενός κοινού στόχου. Για την αντιμετώπιση του προβλήματος αυ- τού προτείνεται μία μέθοδος ενισχυτικής μάθησης που βασίζεται στη μάθηση ενός συνόλου στρατηγικών. Μέσω μιας διαδικασίας συγχώνευσης των επιμέρους αποφάσεων, οι πράκτο- ρες επιλέγουν από κοινού τη στρατηγική που θα ακολουθήσουν. Επίσης, προτείνεται μία μέθοδος για την επιτάχυνση της διαδικασία της ενισχυτικής μά- θησης σε πράκτορες η οποία μπορεί να εφαρμοστεί τόσο σε συστήματα όπου δρουν πολλα- πλοί πράκτορες, όσο και σε συστήματα όπου ενεργεί ένας μόνο πράκτορας. Η προτεινόμενη μέθοδος χρησιμοποιεί πολλαπλές συναρτήσεις απεικόνισης για να μεταφέρει τη γνώση από μια πηγαία εργασία σε μια δυσκολότερη εργασία στόχο. Επιπλέον, προτείνεται μία μέθοδος που συνδυάζει την ενισχυτική μάθηση με την επι- λογή ταξινομητών από μια ομάδα. Πιο συγκεκριμένα, η προτεινόμενη προσέγγιση έχει ως σκοπό τη μάθηση μιας βέλτιστης συμπεριφοράς επιλογής του κατάλληλου ταξινομητή για τη βαθμολόγηση των συνδέσμων κατά τη διαδικασία της εστιασμένης περιήγησης στον Παγκόσμιο Ιστό. Με αυτό τον συνδυασμό ενισχυτικής μάθησης και ομάδας ταξινομητών επιτυγχάνεται η εκπαίδευση ενός πράκτορα σ’ ένα αχανές και μεταβαλλόμενο περιβάλλον όπως αυτό του Ιστού. Επεκτείνοντας αυτή τη φιλοσοφία, προτείνεται μια μέθοδος ενισχυτικής μάθησης για το κλάδεμα μιας ομάδας ταξινομητών με σκοπό τη βελτίωση της απόδοσης πρόβλεψης. Ο πράκτορας μαθαίνει μία πολιτική εισαγωγής ή όχι των ταξινομητών στην ομάδα. Η μοντε- λοποίηση που προτείνεται χρησιμοποιεί έναν γενικό ορισμό της ανταμοιβής έτσι ώστε να παρέχεται η δυνατότητα της χρήσης διαφορετικών μετρικών της απόδοσης ανάλογα με τις απαιτήσεις του πεδίου. Επίσης, προτείνεται και μία ταξινόμηση των μεθόδων κλαδέματος ταξινομητών που έχουν παρουσιαστεί στη βιβλιογραφία.