- title: 'International Conference on Grammatical Inference 2016: Preface' volume: 57 URL: http://proceedings.mlr.press/v57/verwer16.html PDF: http://proceedings.mlr.press/v57/verwer16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-verwer16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 1-2 id: verwer16 issued: date-parts: - 2017 - 1 - 16 firstpage: 1 lastpage: 2 published: 2017-01-16 00:00:00 +0000 - title: 'Simple K-star Categorial Dependency Grammars and their Inference' abstract: 'We propose a novel subclass in the family of Categorial Dependency Grammars (CDG), based on a syntactic criterion on categorial types associated to words in the lexicon and study its learnability. This proposal relies on a linguistic principle and relates to a former non-constructive condition on iterated dependencies. We show that the projective CDG in this subclass are incrementally learnable in the limit from dependency structures. In contrast to previous proposals, our criterion is both syntactic and does not impose a (rigidity) bound on the number of categorial types associated to a word.' volume: 57 URL: http://proceedings.mlr.press/v57/bechet16.html PDF: http://proceedings.mlr.press/v57/bechet16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-bechet16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Denis family: Béchet - given: Annie family: Foret editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 3-14 id: bechet16 issued: date-parts: - 2017 - 1 - 16 firstpage: 3 lastpage: 14 published: 2017-01-16 00:00:00 +0000 - title: 'Query Learning Automata with Helpful Labels' abstract: 'In the active learning framework, a modified query learning algorithm benefiting by a nontrivial helpful labeling is able to learn automata with a reduced number of queries. In extremis, there exists a helpful labeling allowing the algorithm to learn automata even without counterexamples. We also review the correction queries defining them as particular types of labeling. We introduce minimal corrections, maximal corrections, and random corrections. An experimental approach compares the performance and limitations of various types of queries and corrections. The results show that algorithms using corrections require fewer queries in most of the cases.' volume: 57 URL: http://proceedings.mlr.press/v57/dediu16.html PDF: http://proceedings.mlr.press/v57/dediu16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-dediu16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Adrian-Horia family: Dediu - given: Joana family: M. Matos - given: Claudio family: Moraga editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 15-29 id: dediu16 issued: date-parts: - 2017 - 1 - 16 firstpage: 15 lastpage: 29 published: 2017-01-16 00:00:00 +0000 - title: 'Inferring Non-resettable Mealy Machines with $n$ States' abstract: 'Automata inference algorithms are used to extract behavioural models of software components. However, when the software system cannot be reset, inference must be done from a single trace. This paper proposes an active learning algorithm that can infer a Mealy model under the assumption that the number of the states of the machine is known and that a characterization set for it is provided. This algorithm improves on a previous paper that used a looser assumption on the number of states. The complexity is polynomial in the number of states of the Mealy machine.' volume: 57 URL: http://proceedings.mlr.press/v57/groz16.html PDF: http://proceedings.mlr.press/v57/groz16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-groz16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Roland family: Groz - given: Catherine family: Oriat - given: Nicolas family: Brémond editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 30-41 id: groz16 issued: date-parts: - 2017 - 1 - 16 firstpage: 30 lastpage: 41 published: 2017-01-16 00:00:00 +0000 - title: 'Testing Distributional Properties of Context-Free Grammars' abstract: 'Recent algorithms for distributional learning of context-free grammars can learn all languages defined by grammars that have certain distributional properties: the finite kernel property (FKP) and the finite context property (FCP). In this paper we present some algorithms for approximately determining whether a given grammar has one of these properties. We then present the results of some experiments that indicate that with randomly generated context-free grammars in Chomsky normal form, which generate infinite languages and are derivationally sparse, nearly all grammars have the finite kernel property, whereas the finite context property is much less common.' volume: 57 URL: http://proceedings.mlr.press/v57/clark16.html PDF: http://proceedings.mlr.press/v57/clark16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-clark16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Alexander family: Clark editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 42-53 id: clark16 issued: date-parts: - 2017 - 1 - 16 firstpage: 42 lastpage: 53 published: 2017-01-16 00:00:00 +0000 - title: 'Learning Top-Down Tree Transducers with Regular Domain Inspection' abstract: 'We study the problem of how to learn tree transformations on a given regular tree domain from a finite sample of input-output examples. We assume that the target tree transformation can be defined by a deterministic top-down tree transducer with regular domain inspection (DTOPIreg). An RPNI style learning algorithm that solves this problem in polynomial time and with polynomially many examples was presented at Pods’2010, but restricted to the case of path-closed regular domains. In this paper, we show that this restriction can be removed. For this, we present a new normal form for DTOPIreg by extending the Myhill-Nerode theorem for DTOP to regular domain inspections in a nontrivial manner. The RPNI style learning algorithm can also be lifted but becomes more involved too.' volume: 57 URL: http://proceedings.mlr.press/v57/boiret16.html PDF: http://proceedings.mlr.press/v57/boiret16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-boiret16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Adrien family: Boiret - given: Aurélien family: Lemay - given: Joachim family: Niehren editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 54-65 id: boiret16 issued: date-parts: - 2017 - 1 - 16 firstpage: 54 lastpage: 65 published: 2017-01-16 00:00:00 +0000 - title: 'Using Model Theory for Grammatical Inference: a Case Study from Phonology' abstract: 'This paper examines the characterization and learning of grammars defined by conjunctions of negative and positive literals (CNPL) where the literals correspond to structures in an enriched model theory of strings. CNPL logic represents an intermediate between conjunctions of negative literals (CNL) and a propositional-style logic, both of which have been well-studied in terms of the language classes they describe. Model-theoretic approaches to formal language theory have traditionally assumed that each position in a string belongs to exactly one unary relation. Using enriched models (which do no satisfy this assumption) presents a new avenue for investigation with potential applications in several fields including linguistics, planning and control, and molecular biology. We demonstrate the value of such structures and CNPL logic with a particular learning problem in phonology.' volume: 57 URL: http://proceedings.mlr.press/v57/strother-garcia16.html PDF: http://proceedings.mlr.press/v57/strother-garcia16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-strother-garcia16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Kristina family: Strother-Garcia - given: Jerey family: Heinz - given: Hyun Jin family: Hwangbo editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 66-78 id: strother-garcia16 issued: date-parts: - 2017 - 1 - 16 firstpage: 66 lastpage: 78 published: 2017-01-16 00:00:00 +0000 - title: 'The Generalized Smallest Grammar Problem' abstract: 'The Smallest Grammar Problem – the problem of finding the smallest context-free grammar that generates exactly one given sequence – has never been successfully applied to grammatical inference. We investigate the reasons and propose an extended formulation that seeks to minimize non-recursive grammars, instead of straight-line programs. In addition, we provide very efficient algorithms that approximate the minimization problem of this class of grammars. Our empirical evaluation shows that we are able to find smaller models than the current best approximations to the Smallest Grammar Problem on standard benchmarks, and that the inferred rules capture much better the syntactic structure of natural language.' volume: 57 URL: http://proceedings.mlr.press/v57/siyari16.html PDF: http://proceedings.mlr.press/v57/siyari16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-siyari16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Payam family: Siyari - given: Matthias family: Gallé editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 79-92 id: siyari16 issued: date-parts: - 2017 - 1 - 16 firstpage: 79 lastpage: 92 published: 2017-01-16 00:00:00 +0000 - title: 'Online Grammar Compression for Frequent Pattern Discovery' abstract: 'Various grammar compression algorithms have been proposed in the last decade. A grammar compression is a restricted CFG deriving the string deterministically. An efficient grammar compression develops a smaller CFG by finding duplicated patterns and removing them. This process is just a frequent pattern discovery by grammatical inference. While we can get any frequent pattern in linear time using a preprocessed string, a huge working space is required for longer patterns, and the whole string must be loaded into the memory preliminarily. We propose an online algorithm approximating this problem within a compressed space. The main contribution is an improvement of the previously best known approximation ratio Ω(\frac1\lg^2m) to Ω(\frac1\lg^*N\lg m) where m is the length of an optimal pattern in a string of length N and \lg^* is the iteration of the logarithm base 2. For a sufficiently large N, \lg^*N is practically constant. The experimental results show that our algorithm extracts nearly optimal patterns and achieves a significant improvement in memory consumption compared to the offline algorithm.' volume: 57 URL: http://proceedings.mlr.press/v57/fukunaga16.html PDF: http://proceedings.mlr.press/v57/fukunaga16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-fukunaga16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Shouhei family: Fukunaga - given: Yoshimasa family: Takabatake - given: Tomohiro family: I - given: Hiroshi family: Sakamoto editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 93-104 id: fukunaga16 issued: date-parts: - 2017 - 1 - 16 firstpage: 93 lastpage: 104 published: 2017-01-16 00:00:00 +0000 - title: 'Sp2Learn: A Toolbox for the Spectral Learning of Weighted Automata' abstract: 'Sp2Learn is a Python toolbox for the spectral learning of weighted automata from a set of strings, licensed under Free BSD. This paper gives the main formal ideas behind the spectral learning algorithm and details the content of the toolbox. Use cases and an experimental section are also provided.' volume: 57 URL: http://proceedings.mlr.press/v57/arrivault16.html PDF: http://proceedings.mlr.press/v57/arrivault16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-arrivault16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Denis family: Arrivault - given: Dominique family: Benielli - given: François family: Denis - given: Remi family: Eyraud editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 105-119 id: arrivault16 issued: date-parts: - 2017 - 1 - 16 firstpage: 105 lastpage: 119 published: 2017-01-16 00:00:00 +0000 - title: 'Learning Deterministic Finite Automata from Infinite Alphabets' abstract: 'We proposes an algorithm to learn automata infinite alphabets, or at least too large to enumerate. We apply it to define a generic model intended for regression, with transitions constrained by intervals over the alphabet. The algorithm is based on the Red & Blue framework for learning from an input sample. We show two small case studies where the alphabets are respectively the natural and real numbers, and show how nice properties of automata models like interpretability and graphical representation transfer to regression where typical models are hard to interpret.' volume: 57 URL: http://proceedings.mlr.press/v57/pellegrino16.html PDF: http://proceedings.mlr.press/v57/pellegrino16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-pellegrino16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Gaetano family: Pellegrino - given: Christian family: Hammerschmidt - given: Qin family: Lin - given: Sicco family: Verwer editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 120-131 id: pellegrino16 issued: date-parts: - 2017 - 1 - 16 firstpage: 120 lastpage: 131 published: 2017-01-16 00:00:00 +0000 - title: 'Results of the Sequence PredIction ChallengE (SPiCe): a Competition on Learning the Next Symbol in a Sequence' abstract: 'The Sequence PredIction ChallengE (SPiCe) is an on-line competition that took place between March and July 2016. Each of the 15 problems was made of a set of whole sequences as training sample, a validation set of prefixes, and a test set of prefixes. The aim was to submit a ranking of the 5 most probable symbols to be the next symbol of each prefix.' volume: 57 URL: http://proceedings.mlr.press/v57/balle16.html PDF: http://proceedings.mlr.press/v57/balle16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-balle16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Borja family: Balle - given: Rémi family: Eyraud - given: Franco M. family: Luque - given: Ariadna family: Quattoni - given: Sicco family: Verwer editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 132-136 id: balle16 issued: date-parts: - 2017 - 1 - 16 firstpage: 132 lastpage: 136 published: 2017-01-16 00:00:00 +0000 - title: 'Predicting Sequential Data with LSTMs Augmented with Strictly 2-Piecewise Input Vectors' abstract: 'Recurrent neural networks such as Long-Short Term Memory (LSTM) are often used to learn from various kinds of time-series data, especially those that involved long-distance dependencies. We introduce a vector representation for the Strictly 2-Piecewise (SP-2) formal languages, which encode certain kinds of long-distance dependencies using subsequences. These vectors are added to the LSTM architecture as an additional input. Through experiments with the problems in the SPiCe dataset, we demonstrate that for certain problems, these vectors slightly—but significantly—improve the top-5 score (normalized discounted cumulative gain) as well as the accuracy as compared to the LSTM architecture without the SP-2 input vector. These results are also compared to an LSTM architecture with an input vector based on bigrams.' volume: 57 URL: http://proceedings.mlr.press/v57/shibata16.html PDF: http://proceedings.mlr.press/v57/shibata16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-shibata16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Chihiro family: Shibata - given: Jeffrey family: Heinz editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 137-142 id: shibata16 issued: date-parts: - 2017 - 1 - 16 firstpage: 137 lastpage: 142 published: 2017-01-16 00:00:00 +0000 - title: 'A Spectral Method that Worked Well in the SPiCe’16 Competition' abstract: 'We present methods used in our submission to the Sequence Prediction ChallengE (SPiCe’16). The two methods used to solve the competition tasks were spectral learning and a count based method. Spectral learning led to better results on most of the problems.' volume: 57 URL: http://proceedings.mlr.press/v57/liza16.html PDF: http://proceedings.mlr.press/v57/liza16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-liza16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Farhana Ferdousi family: Liza - given: Marek family: Grześ editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 143-148 id: liza16 issued: date-parts: - 2017 - 1 - 16 firstpage: 143 lastpage: 148 published: 2017-01-16 00:00:00 +0000 - title: 'Evaluation of Machine Learning Methods on SPiCe' abstract: 'In this paper, we introduce methods that we used to solve problems from the sequence prediction competition called SPiCe. We train a model from sequences in train data on each problem, and then predict a next symbol following each sequence in test data. We implement several methods to solve these problems. The experiment results show that XGBoost and neural network approaches have good performance overall.' volume: 57 URL: http://proceedings.mlr.press/v57/sato16.html PDF: http://proceedings.mlr.press/v57/sato16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-sato16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Ichinari family: Sato - given: Kaizaburo family: Chubachi - given: family: Diptarama editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 149-153 id: sato16 issued: date-parts: - 2017 - 1 - 16 firstpage: 149 lastpage: 153 published: 2017-01-16 00:00:00 +0000 - title: 'Flexible State-Merging for Learning (P)DFAs in Python' abstract: 'We present a Python package for learning (non-)probabilistic deterministic finite state automata and provide heuristics in the red-blue framework. As our package is built along the API of the popular scikit-learn package, it is easy to use and new learning methods are easy to add. It provides PDFA learning as an additional tool for sequence prediction or classification to data scientists, without the need to understand the algorithm itself but rather the limitations of PDFA as a model. With applications of automata learning in diverse fields such as network traffic analysis, software engineering and biology, a stratified package opens opportunities for practitioners.' volume: 57 URL: http://proceedings.mlr.press/v57/hammerschmidt16.html PDF: http://proceedings.mlr.press/v57/hammerschmidt16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-hammerschmidt16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Christian family: Hammerschmidt - given: Benjamin family: Loos - given: Radu family: State - given: Thomas family: Engel editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 154-159 id: hammerschmidt16 issued: date-parts: - 2017 - 1 - 16 firstpage: 154 lastpage: 159 published: 2017-01-16 00:00:00 +0000 - title: 'Model Selection of Sequence Prediction Algorithms by Compression' abstract: 'This paper describes estimating performance of sequence prediction algorithms and hyperparameters by compressing the training dataset itself with the probablities predicted by the trained model. With such estimation we can automate the selection and tuning process of learning algorithms. Spectral learning algorithm are experimented with.' volume: 57 URL: http://proceedings.mlr.press/v57/xi16.html PDF: http://proceedings.mlr.press/v57/xi16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-xi16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Du family: Xi - given: Dai family: Zhuang editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 160-163 id: xi16 issued: date-parts: - 2017 - 1 - 16 firstpage: 160 lastpage: 163 published: 2017-01-16 00:00:00 +0000 - title: 'Sequence Prediction Using Neural Network Classiers' abstract: 'Being able to guess the next element of a sequence is an important question in many fields. In this paper we present our approaches used in the Sequence Prediction ChallengE (SPiCe), whose goal is to compare the different approaches to that problem on the same datasets. We model sequence prediction as a classification problem and adapt three different neural network models to tackle it. The experimental results show that our neural network based approaches produce better overall performance than the baseline approaches provided in the competition. In the actual competition, we won the second place using these approaches.' volume: 57 URL: http://proceedings.mlr.press/v57/zhao16.html PDF: http://proceedings.mlr.press/v57/zhao16.pdf edit: https://github.com/mlresearch//v57/edit/gh-pages/_posts/2017-01-16-zhao16.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of The 13th International Conference on Grammatical Inference' publisher: 'PMLR' author: - given: Yanpeng family: Zhao - given: Shanbo family: Chu - given: Yang family: Zhou - given: Kewei family: Tu editor: - given: Sicco family: Verwer - given: Menno van family: Zaanen - given: Rick family: Smetsers address: Delft, The Netherlands page: 164-169 id: zhao16 issued: date-parts: - 2017 - 1 - 16 firstpage: 164 lastpage: 169 published: 2017-01-16 00:00:00 +0000