Grammatical inference algorithms routines and applications

Studies in Computational Intelligence 673 Wojciech Wieczorek Grammatical Inference Algorithms, Routines and Applications Studies in Computational Intelligence Volume 673 Series editor Janusz Kacprzyk, Polish Academy of Sciences, Warsaw, Poland e-mail: kacprzyk@ibspan.pl About this Series The series “Studies in Computational Intelligence” (SCI) publishes new develop- ments and advances in the various areas of computational intelligence—quickly and with a high quality. The intent is to cover the theory, applications, and design methods of computational intelligence, as embedded in the fields of engineering, computer science, physics and life sciences, as well as the methodologies behind them. The series contains monographs, lecture notes and edited volumes in computational intelligence spanning the areas of neural networks, connectionist systems, genetic algorithms, evolutionary computation, artificial intelligence, cellular automata, self-organizing systems, soft computing, fuzzy systems, and hybrid intelligent systems. Of particular value to both the contributors and the readership are the short publication timeframe and the worldwide distribution, which enable both wide and rapid dissemination of research output.

More information about this series at http://www.com/series/7092 Wojciech Wieczorek Grammatical Inference Algorithms, Routines and Applications 123 Wojciech Wieczorek Institute of Computer Science University of Silesia Faculty of Computer Science and Materials Science Sosnowiec Poland ISSN 1860-949X ISSN 1860-9503 (electronic) Studies in Computational Intelligence ISBN 978-3-319-46800-6 ISBN 978-3-319-46801-3 (eBook) DOI 10.1007/978-3-319-46801-3 Library of Congress Control Number: 2016952872 © Springer International Publishing AG 2017 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer International Publishing AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland Preface Grammatical inference, the main topic of this book, is a scientific area that lies at the intersection of multiple fields. Researchers from computational linguistics, pattern recognition, machine learning, computational biology, formal learning theory, and many others have their own contribution.

Therefore, it is not surprising that the topic has also a few other names such as grammar learning, automata inference, grammar identification, or grammar induction. To simplify the location of present contribution, we can divide all books relevant to grammatical inference into three groups: theoretical, practical, and applicable. In greater part this book is practical, though one can also find the elements of learning theory, combinatorics on words, the theory of automata and formal languages, plus some reference to real-life problems. The purpose of this book is to present old and modern methods of grammatical inference from the perspective of practitioners.

To this end, the Python program- ming language has been chosen as the way of presenting all the methods. Included listings can be directly used by the paste-and-copy manner to other programs, thus students, academic researchers, and programmers should find this book as the valuable source of ready recipes and as an inspiration for their further development. A few issues should be mentioned regarding this book: an inspiration to write it, a key for the selection of described methods, arguments for selecting Python as an implementation language, typographical notions, and where the reader can send any critical remarks about the content of the book (subject–matter, listings etc. There is a treasured book entitled “Numerical recipes in C”, in which along with the description of selected numerical methods, listings in C language are provided.

The reader can copy and paste the fragments of the electronic version of the book in order to produce executable programs. Such an approach is very useful. We can find an idea that lies behind a method and immediately put it into practice. It is a guiding principle that accompanied writing the present book.

For the selection of methods, we try to keep balance between importance and complexity. It means that we introduced concepts and algorithms which are essential to the GI practice and theory, but omitted that are too complicated or too v vi Preface long to present them as a ready-to-use code. Thanks to that, the longest program included in the book is no more than a few pages long. As far as the implementation language is concerned, the following requirements had to be taken into account: simplicity, availability, the property of being firmly established, and allowing the use of wide range of libraries.

Python and FSharp programming languages were good candidates. We decided to choose IronPython (an implementation of Python) mainly due to its integration with the optimization modeling language. We use a monospaced (fixed-pitch) font for the listings of programs, while the main text is written using a proportional font. In listings, Python keywords are in bold.

The following persons have helped the author in preparing the final version of this book by giving valuable advice. I would like to thank (in alphabetical order): Prof. Skinderowicz, and Ph. Sosnowiec, Poland Wojciech Wieczorek 2016 Contents 1 Introduction .1 The Problem and Its Various Formulations .1 Mathematical Versus Computer Science Perspectives .2 Different Kinds of Output .2 Assessing Algorithms’ Performance .1 Measuring Classifier Performance .3 5  2 Cross-Validated Paired t Test .2 Classification of Proteins.

16 2 State Merging Algorithms .2 Evidence Driven State Merging .4 Grammatical Inference with MDL Principle .1 The Motivation and Appropriate Measures .2 The Proposed Algorithm. 31 3 Partition-Based Algorithms.2 The k-tails Method .3 Grammatical Inference by Genetic Search .1 What Are Genetic Algorithms?. 37 vii viii Contents 3.2 Basic Notions of the Genetic Algorithm for GI.4 CFG Inference Using Tabular Representations .1 Basic Definitions. 45 4 Substring-Based Algorithms .1 Error-Correcting Grammatical Inference .1 The GI Algorithm .2 Alignment-Based Learning.

56 5 Identification Using Mathematical Modeling .1 From DFA Identification to Graph Coloring .2 From NFA Identification to a Satisfiability Problem .3 From CFG Identification to a CSP. 67 6 A Decomposition-Based Algorithm.1 Prime and Decomposable Languages .2 Cliques and Decompositions .1 The GI Algorithm. 75 7 An Algorithm Based on a Directed Acyclic Word Graph .2 Constructing a DAWG From a Sample. 81 8 Applications of GI Methods in Selected Fields .1 Discovery of Generating Functions .2 The Schützenberger Methodology .2 Minimizing Boolean Functions .1 Background and Terminology .3 Use of Induced Star-Free Regular Expressions .1 Definitions and an Algorithm .2 An Application in Classification of Amyloidogenic Hexapeptides .3 An Application in the Construction of Opening Books.

109 Appendix A: A Quick Introduction to Python. 111 Appendix B: Python’s Tools for Automata, Networks, Genetic Algorithms, and SAT Solving. 129 Appendix C: OML and its Usage in IronPython. 139 Acronyms CFG Context-free grammar CGT Combinatorial game theory CNF Chomsky normal form CNF Conjunctive normal form CSP Constraint satisfaction problem DFA Deterministic finite automaton DNF Disjunctive normal form EDSM Evidence driven state merging GA Genetic algorithm GI Grammatical inference GNF Greibach normal form ILP Integer linear programming LP Linear programming MDL Minimum description length MILP Mixed integer linear programming NFA Non-deterministic finite automaton NLP Non-linear programming NP Non-deterministic polynomial time OGF Ordinary generating function OML Optimization modeling language PTA Prefix tree acceptor RPNI Regular positive and negative inference SAT Boolean satisfiability problem TSP Traveling salesman problem XML Extensible markup language xi Chapter 1 Introduction 1.1 The Problem and Its Various Formulations Let us start with the presentation of how many variants of a grammatical inference problem we may be faced with.

Informally, we are given a sequence of words and the task is to find a rule that lies behind it. Different models and goals are given by response to the following questions. Is the sequence finite or infinite? Does the sequence contain only examples (positive words) or also counter-examples (negative words)? Is the sequence of the form: all positive and negative words up to a certain length n? What is meant by the rule: are we satisfied with regular acceptor, context- free grammar, context-sensitive grammar, or other tool? Among all the rules that match the input, should the obtained one be of a minimum size? 1.1 Mathematical Versus Computer Science Perspectives The main division of GI models comes from the size of a sequence. When it is infinite, we deal with mathematical identification in the limit.

The setting of this model is that of on-line, incremental learning. After each new example, the learner (the algorithm) must return some hypothesis (an automaton or a CFG). Identification is achieved when the learner returns a correct answer and does not change its decision afterwards. With respect to this model the following results have been achieved: (a) if we are given examples and counter-examples of the language to be identified (learning from informant), and each individual word is sure of appearing, then at some point the inductive machine will return the correct hypothesis; (b) if we are given only the examples of the target (learning from text), then identification is impossible for any super-finite class of languages, i., a class containing all finite languages and at least one infinite language.

In this book, however, we only consider the situation when the input is finite, which can be called a computer science perspective. We are going to describe algorithms the part of which base on examples only, and the others base © Springer International Publishing AG 2017 1 W. Wieczorek, Grammatical Inference, Studies in Computational Intelligence 673, DOI 10.1 A DFA accepting a b c aa∗ bb∗ cc∗ a b c S A B C on both examples and counter-examples. Sometimes we will demand the smallest possible form of an output, but every so often we will be satisfied with an output that is just consistent with the input.

Occasionally, an algorithm gives the collection of results that gradually represent the degree of generalization of the input.2 Different Kinds of Output The next point that should be made is that how important it is to pinpoint the kind of a target. Consider the set of examples: {abc, aabbcc, aaabbbccc}. If a solution is being sought in the class of regular languages, then one possible guess is presented in Fig. This automaton matches every word starting with one or more as, followed by one or more bs, and followed by one or more cs.

If a solution is being sought in the class of context-free languages, then one of possible answers is the following grammar: S → ABC A → a|aAB B→b C →c|CC It is clearly seen that the language accepted by this CFG is {am bm cn : m, n ≥ 1}. Finally, if a solution is being sought in the class of context-sensitive languages, then even more precise conjecture can be made: S →aBc a A → aa b A → Ab B → Ab B c B c → bc Now, the language accepted by this grammar is {am bm cm : m ≥ 1}. It is worth emphasizing that from the above-mentioned three various acceptors, the third one can not be described as a CFG or a DFA, and the second one can not be described as a DFA (or an NFA). In the book we will only consider the class of regular and context- free languages.