This paper presents an information-theoretical model of syntactic generalization.We study syntactic generalization from the perspective of the capacity to disentangle semantic and structural information, emulating the human capacity to assign a grammaticality judgment to semantically nonsensical sentences.In order to isolate the structure, we propose to represent the probability distribution behind a corpus as the product of the probability of a semantic context and the probability of a structure, the latter being independent of the former.We further elaborate the notion of abstraction as a relaxation of the property of independence.It is based on the measure of structural and contextual information for a given representation.We test abstraction as an optimization objective on the task of inducing syntactic categories from natural language data and show that it significantly outperforms alternative methods.Furthermore, we find that when syntax-unaware optimization objectives succeed in the task, their success is mainly due to an implicit disentanglement process rather than to the model structure.On the other hand, syntactic categories can be deduced in a principled way from the independence between structure and context.

This article presents genetic wave function collapse (WFC), a procedural level generation algorithm that mixes genetic optimization with WFC, a local adjacency constraints propagation algorithm. We use a synthetic player to evaluate the novelty, safety, and complexity of the generated levels. Novelty is maximized when the synthetic player goes on tiles not visited for a long time, safety is related to how far it can see, and complexity evaluates the variability of the surrounding tiles. WFC extracts constraints from example levels, and allows us to perform the genetic search on levels with few local asset placement errors, while using as little level design rules as possible. We show that we are able to rely on WFC while optimizing the results, first by influencing WFC asset selection and then by reencoding the chosen modules back to our genotype, in order to optimize crossover. We compare the fitness curves and best maps of our method with other approaches. We then visually explore the kind of levels we are able to generate by sampling different values of safety and complexity, giving a glimpse of the variability that our approach is able to reach.

This paper is a theoretical contribution to the debate on the learnability of syntax from a corpus without explicit syntax-specific guidance.Our approach originates in the observable structure of a corpus, which we use to define and isolate grammaticality (syntactic information) and meaning/pragmatics information.We describe the formal characteristics of an autonomous syntax and show that it becomes possible to search for syntax-based lexical categories with a simple optimization process, without any prior hypothesis on the form of the model.

We derive a spectral method for unsupervised learning of Weighted Context Free Grammars.We frame WCFG induction as finding a Hankel matrix that has low rank and is linearly constrained to represent a function computed by inside-outside recursions.The proposed algorithm picks the grammar that agrees with a sample and is the simplest with respect to the nuclear norm of the Hankel matrix.

Finite-State Transducers (FST) are a standard tool for modeling paired input-output sequences and are used in numerous applications, ranging from computational biology to natural language processing. Recently Balle et al. presented a spectral algorithm for learning FST from samples of aligned input-output sequences. In this paper we address the more realistic, yet challenging setting where the alignments are unknown to the learning algorithm. We frame FST learning as finding a low rank Hankel matrix satisfying constraints derived from observable statistics. Under this formulation, we provide identifiability results for FST distributions. Then, following previous work on rank minimization, we propose a regularized convex relaxation of this objective which is based on minimizing a nuclear norm penalty subject to linear constraints and can be solved efficiently.

One of the main problems in probabilistic grammatical inference consists in inferring a stochastic language, i.e. a probability distribution, in some class of probabilistic models, from a sample of strings independently drawn according to a fixed unknown target distribution p. Here, we consider the class of rational stochastic languages composed of stochastic languages that can be computed by multiplicity automata, which can be viewed as a generalization of probabilistic automata. Rational stochastic languages p have a useful algebraic characterization: all the mappings up: v → p(uv) lie in a finite dimensional vector subspace Vp* of the vector space ℝ 〈〈Σ〉〉 composed of all real-valued functions defined over Σ*. Hence, a first step in the grammatical inference process can consist in identifying the subspace Vp*. In this paper, we study the possibility of using Principal Component Analysis to achieve this task. We provide an inference algorithm which computes an estimate of this space and then build a multiplicity automaton which computes an estimate of the target distribution. We prove some theoretical properties of this algorithm and we provide results from numerical simulations that confirm the relevance of our approach.