An agent-based evolutionary computing approach to memory-based syntactic parsing of natural language

This thesis introduces GrAEL (grammar evolution) as one of the first research efforts that investigates an agent-based evolutionary computing approach as a possible machine learning method for data-driven grammar optimization and induction. Using the same architecture, but different information sources, GrAEL can be shown to handle a diverse range of grammar engineering tasks, which can help resolve common issues in corpus-based parsing systems, such as insufficient grammar coverage and the suboptimal distribution of probability mass.; After describing a memory-based data-driven parser that applies structure to sentences by direct reference to grammatical information stored in memory, we apply different instantiations of GrAEL to alleviate its aforementioned inherent problematic issues. GrAEL is a distributed system, a computational environment in which agent communicate and co-evolve according to neo-darwinist principles. In the GrAEL environment, each agent is given a partial solution to a problem. By interacting with each other in an evolutionary context, the grammars are optimized in a practical context, on the basis of pre-defined fitness functions.; The first instantiation GrAEL-1 does not alter the content of the corpus-induced grammar and therefore only serves to redistribute the probability mass of the statistical weights of the grammar rules. Experiments show that a careful selection of parameters pertaining to the evolutionary aspects of the environment, can improve performance significantly. The redistributed probability mass can be considered to reflect useful statistics for the task of parsing, rather than mirror the distribution of the original training set.; Grammar-rule discovery can be implemented by allowing the agents in the society to make minor alterations to the rules in the corpus-induced grammar. The evolutionary computing approach then not only serves as a way to redistribute the probability mass, but also to evaluate the validity of newly created grammar rules. Unsupervised grammar induction can likewise be performed in a GrAEL environment if we allow the agents to build up their own structures, using a minimalist grammar induction approach that employs concepts of information theory to bootstrap structure.; By further reducing the information source, we can leave the engineering aspect behind and transform GrAEL into a computational environment in which we can simulate the emergence of grammatical principles in an artificial language of a group of communicating agents. In this view, GrAEL provides a computational simulation of a possible model for the emergence of grammar in early hominids.