- 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:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Béchet
given: Denis
- family: Foret
given: Annie
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Dediu
given: Adrian-Horia
- family: M. Matos
given: Joana
- family: Moraga
given: Claudio
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Groz
given: Roland
- family: Oriat
given: Catherine
- family: Brémond
given: Nicolas
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Clark
given: Alexander
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Boiret
given: Adrien
- family: Lemay
given: Aurélien
- family: Niehren
given: Joachim
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Strother-Garcia
given: Kristina
- family: Heinz
given: Jerey
- family: Hwangbo
given: Hyun Jin
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Siyari
given: Payam
- family: Gallé
given: Matthias
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Fukunaga
given: Shouhei
- family: Takabatake
given: Yoshimasa
- family: I
given: Tomohiro
- family: Sakamoto
given: Hiroshi
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Arrivault
given: Denis
- family: Benielli
given: Dominique
- family: Denis
given: François
- family: Eyraud
given: Remi
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Pellegrino
given: Gaetano
- family: Hammerschmidt
given: Christian
- family: Lin
given: Qin
- family: Verwer
given: Sicco
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Balle
given: Borja
- family: Eyraud
given: Rémi
- family: Luque
given: Franco M.
- family: Quattoni
given: Ariadna
- family: Verwer
given: Sicco
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Shibata
given: Chihiro
- family: Heinz
given: Jeffrey
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Liza
given: Farhana Ferdousi
- family: Grześ
given: Marek
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Sato
given: Ichinari
- family: Chubachi
given: Kaizaburo
- family: Diptarama
given:
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Hammerschmidt
given: Christian
- family: Loos
given: Benjamin
- family: State
given: Radu
- family: Engel
given: Thomas
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Xi
given: Du
- family: Zhuang
given: Dai
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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:
- family: Zhao
given: Yanpeng
- family: Chu
given: Shanbo
- family: Zhou
given: Yang
- family: Tu
given: Kewei
editor:
- family: Verwer
given: Sicco
- family: Zaanen
given: Menno van
- family: Smetsers
given: Rick
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