Learning regular languages over large alphabets

Abstract

Learning regular languages is a branch of machine learning, a domain which has proved useful in many areas, including artificial intelligence, neural networks, data mining, verification, etc. In addition, interest in languages defined over large and infinite alphabets has increased in recent years. Although many theories and properties generalize well from the finite case, learning such languages is not an easy task. As the existing methods for learning regular languages depend on the size of the alphabet, a straightforward generalization in this context is not possible. In this thesis, we present a generic algorithmic scheme that can be used for learning languages defined over large or infinite alphabets, such as bounded subsets of N or R or Boolean vectors of high dimensions. We restrict ourselves to the class of languages accepted by deterministic symbolic automata that use predicates to label transitions, forming a finite partition of the alphabet for every state. Our learning algorithm, an adaptation of Angluin's L*, combines standard automaton learning by state characterization, with the learning of the static predicates that define the alphabet partitions. We use the online learning scheme, where two types of queries provide the necessary information about the target language. The first type, membership queries, answer whether a given word belongs or not to the target. The second, equivalence queries, check whether a conjectured automaton accepts the target language and provide a counter-example otherwise. We study language learning over large or infinite alphabets within a general framework but our aim is to provide solutions for particular concrete instances. For this, we focus on the two main aspects of the problem. Initially, we assume that equivalence queries always provide a counter-example which is minimal in the length-lexicographic order when the conjecture automaton is incorrect. Then, we drop this "strong'' equivalence oracle and replace it by a more realistic assumption, where equivalence is approximated by testing queries, which use sampling on the set of words. Such queries are not guaranteed to find counter-examples and certainly not minimal ones. In this case, we obtain the weaker notion of PAC (probably approximately correct) learnability and learn an approximation of the target language. All proposed algorithms have been implemented and their performance, as a function of automaton and alphabet size, has been empirically evaluated.

Η εκμάθηση τυπικών (regular) γλωσσών είναι ένας κλάδος της μηχανικής μάθησης (machine learning) που έχει συμβάλλει σημαντικά σε πολλούς τομείς, όπως η τεχνητή νοημοσύνη (artificial intelligence), τα νευρωνικά δίκτυα (neural networks), η εξόρυξη δεδομένων (data mining), η επαλήθευση συστημάτων (system verification) κ.λπ. Τα τελευταία χρόνια παρουσιάζεται αυξητική τάση στον αριθμό των εφαρμογών που κάνουν χρήση γλωσσών που ορίζονται σε μεγάλα και άπειρα αλφάβητα και αυτό έχει ως συνέπεια να έχει αυξηθεί και η ανάγκη για την ανάπτυξη αλγορίθμων για την εκμάθηση τους. Καθώς οι υπάρχουσες μέθοδοι εκμάθησης τυπικών γλωσσών εξαρτώνται από το μέγεθος του αλφαβήτου αυτό το εγχείρημα δεν είναι εύκολο και μια απλή γενίκευση σε άπειρα αλφάβητα δεν είναι δυνατή. Στην παρούσα διατριβή, παρουσιάζουμε ένα γενικευμένο αλγοριθμικό σχήμα που μπορεί να χρησιμοποιηθεί για την εκμάθηση γλωσσών που ορίζονται σε μεγάλα ή άπειρα αλφάβητα, όπως υποσύνολα των φυσικών (Ν) ή πραγματικών (R) ή Boolean διανύσματα μεγάλων διαστάσεων. Περιοριζόμαστε στην κατηγορία των τυπικών γλωσσών που γίνονται δεκτές από ντετερμινιστικά συμβολικά αυτόματα (deterministic symbolic automata), τα οποία χρησιμοποιούν λογικές εκφράσεις για να ορίσουν τις μεταβάσεις μεταξύ των καταστάσεων και σχηματίζουν μία πεπερασμένη διαμέριση του αλφαβήτου σε κάθε κατάσταση. Οι αλγόριθμοι που προτίνουμε, συνδυάζουν την εκμάθηση αυτομάτων μέσω χαρακτηρισμού καταστάσεων, όπως αυτή γίνεται στον αλγόριθμο L* της Angluin, με την εκμάθηση των λογικών εκφράσεων που ορίζουν τις μεταβάσεις μεταξύ των καταστάσεων. Το online σχήμα μάθησης που χρησιμοποιούμε κάνει χρήση δύο τύπων ερωτημάτων που παρέχουν τις απαραίτητες πληροφορίες σχετικά με τη γλώσσα-στόχο. Τα ερωτήματα αφορούν τις ιδιότητες του ανήκει και της ισοδυναμίας. Σε περίπτωση μη ισοδυναμίας επιστρέφεται ένα αντιπαράδειγμα το οποίο θα χρησιμοποιηθεί από τον αλγόριθμο ώστε να βελτιωθεί το αυτόματο μέχρις ότου επέλθει η σύνγκλιση και ο τερματισμός. Σε περίπτωση που δεν μπορεί να ελεγθεί η ιδιότητα της ισοδυναμίας, προτίνεται ένας προσαρμοσμένος αλγόριθμος που στον τερματισμό του θα επιστρέψει ένα αυτόματο που θα αναγνωρίζει τη γλώσσα-στοχο προσεγγιστικά κάνοντας χρήση της παραδοχής PAC (probably approximately correct). Όλες οι μέθοδοι και αλγόριθμοι που προτίνονται έχουν υλοποιηθεί προγραμματιστικά και έχουν χρησιμοποιηθεί για την πραγματοποίηση προσομοιώσεων και εμπειρικής αξιολόγησης των αλγορίθμων.

L'apprentissage de langages réguliers est un sous-ensemble de l'apprentissage automatique qui s'est révélé utile dans de nombreux domaines tels que l'intelligence artificielle, les réseaux de neurones, l'exploration de données, la vérification, etc. De plus, l'intérêt dans les langages définis sur des alphabets infinis ou de grande taille est croissant au fil des années. Même si plusieurs propriétés et théories se généralisent à partir du cas fini, l'apprentissage de tels langages est une tâche difficile. En effet, dans ce contexte, l'application naïve des algorithmes d'apprentissage traditionnel n'est pas possible. Dans cette thèse, nous présentons un schéma algorithmique général pour l'apprentissage de langages définis sur des alphabets infinis ou de grande taille, comme par exemple des sous-ensembles bornés de N or R ou des vecteurs booléens de grandes dimensions. Nous nous restreignons aux classes de langages qui sont acceptés par des automates déterministes symboliques utilisant des prédicats pour définir les transitions, construisant ainsi une partition finie de l'alphabet pour chaque état. Notre algorithme d'apprentissage, qui est une adaptation du L* d'Angluin, combine l'apprentissage classique d'un automate par la caractérisation de ses états, avec l'apprentissage de prédicats statiques définissant les partitions de l'alphabet. Nous utilisons l'apprentissage incrémental avec la propriété que deux types de requêtes fournissent une information suffisante sur le langage cible. Les requêtes du premier type sont les requêtes d'adhésions, qui permettent de savoir si un mot proposé appartient ou non au langage cible. Les requêtes du second type sont les requêtes d'équivalence, qui vérifient si un automate proposé accepte le langage cible; dans le cas contraire, un contre-exemple est renvoyé. Nous étudions l'apprentissage de langages définis sur des alphabets infinis ou de grande tailles dans un cadre théorique et général, mais notre objectif est de proposer des solutions concrètes pour un certain nombre de cas particuliers. Ensuite, nous nous intéressons aux deux principaux aspects du problème. Dans un premier temps, nous supposerons que les requêtes d'équivalence renvoient toujours un contre-exemple minimal pour un ordre de longueur-lexicographique quand l'automate proposé est incorrect. Puis dans un second temps, nous relâchons cette hypothèse forte d'un oracle d'équivalence, et nous la remplaçons avec une hypothèse plus réaliste où l'équivalence est approchée par un test sur les requêtes qui utilisent un échantillonnage sur l'ensemble des mots. Dans ce dernier cas, ce type de requêtes ne garantit pas l'obtention de contre-exemples, et par conséquent de contre-exemples minimaux. Nous obtenons alors une notion d'apprent-issage PAC (Probably Approximately Correct), permettant l'apprentissage d'une approximation du langage cible. Tout les algorithmes ont été implémentés, et leurs performances, en terme de construction d'automate et de taille d'alphabet, ont été évaluées empiriquement.