Session:

LBP - Late Breaking Papers

Title:

Parsing Probabilistic Context Free Languages with Multi-Objective Genetic Algorithms

Authors:

Ramon Lefuel
Brian J. Ross

Abstract:

An approach to parsing probabilistic context free languages is presented. Given an input sentence, a genetic algorithm is used to evolve parse trees as defined by a given probabilistic context free grammar. Each chromosome in the population represents a candidate parse tree, using a simple indexed representation. The novelty of the approach is the multi-objective treatment of parse tree fitness. One dimension of the fitness space is the number of contiguous words correctly read by the parse. The other dimension incorporates a measurement equivalent to the probability obtained by complete parse trees, and partial probabilities corresponding to incomplete parses. A number of experiments show that this method is both effective and efficient for parsing natural language sentences.