Natural language analysis by stochastic optimization: a progress report on Project APRIL

Publisher Website
Google Scholar
Abstract
Parsing techniques based on rules defining grammaticality are difficult to use with authentic natural-language inputs, which are often grammatically messy. Instead, the APRIL system seeks a labelled tree structure which maximizes a numerical measure of conformity to statistical norms derived from a sample of parsed text. No distinction between legal and illegal trees arises: any labelled tree has a value. Because the search space is large and has an irregular geometry, APRIL seeks the best tree using simulated annealing, a stochastic optimization technique. Beginning with an arbitrary tree, many randomly-generated local modifications are considered and adopted or rejected according to their effect on tree-value: acceptance decisions are made probabilistically, subject to a bias against adverse moves which is very weak at the outset but is made to increase as the random walk through the search space continues. This enables the system to converge on the global optimum without getting trapped in local optima. Performance of an early version of the APRIL system on authentic inputs has been yielding analyses with a mean accuracy upwards of 75%, using a schedule which increases processing linearly with sentence-length; modifications currently being implemented should eliminate many of the remaining errors.

This publication has 6 references indexed in Scilit: