Abstract
dc:descriptionLearning 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.
Degree
thesis:*- Grantor dc:publisher
- Institutes outside Greece
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Mens, Irini-Eleftheria
- Μένς, Ειρήνη-Ελευθερία
Subjects
dc:subject × 34- Μηχανική μάθηση
- Μηχανική εκμάθηση
- ΑΥΤΟΜΑΤΑ ΠΕΠΕΡΑΣΜΕΝΩΝ ΚΑΤΑΣΤΑΣΕΩΝ
- Γενικευμένα αυτόματα
- Συμβολικά αυτόματα
- Τεχνιτή νοημοσύνη
- Machine learning
- Machine learning methods
- Artificial intelligence
- regular languages
- Finite state automata
- finite state machines
- Symbolic automata
- System identification
- Online learning
- Active learning
- black box learning
- apprentissage automatique
- intelligence artificielle
- langages réguliers
- automate fini
- Μαθηματικά
- Φυσικές Επιστήμες
- Μαθηματικά, άλλοι τομείς
- Εφαρμοσμένα μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Τεχνητή νοημοσύνη
- Mathematics
- Natural Sciences
- Mathematics (miscellaneous)
- Applied Mathematics
- Computer and Information Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/53415