\chapter{Introduction}

Natural language acquisition, that is, the way humans learn their native
language, has been the focus of much linguistic and cognitive science
research. The ease and uniformity with which children acquire language
is remarkable, suggesting that some part of language is ``hard-wired''
into the brain at birth. The search for this part of language which is
``universal'' has led to the Universal Grammar theory, which is
parameterized. This theory of a Universal Grammar provides an
opportunity to develop a ``natural'' way for a computer to learn a
language. Natural language acquisition probably does not proceed in the
``survival of the fittest'' way a genetic algorithm searches for the
most optimal solution to a problem.  However, a genetic algorithm
provides a good way to search for an optimal or near-optimal solution in
a large search space. The parameters in the Universal Grammar theory
provides such a space, with a different optimal solution for each
language. Thus, using a genetic algorithm to search for the parameter
settings of a language seems like the best way to wade through all of
the possible parameter settings for a language. Once the parameter
settings for a particular language are found, a computer can understand,
or at least parse, that language.

In linguistics, the Principles and Parameters theory proposes that all
natural languages are based on the Universal Grammar (UG), which is
``hard-wired'' into the brain. Variation between languages comes from
the parameterization of the UG.  For instance, word order varies from
language to language, i.e. the settings of parameters which determine
if the subject of a sentence follows the predicate, if the determiner
comes before the noun in a noun phrase, et cetera, vary from language to
language. When children are exposed to their native language, their
language acquisition device (however it may be manifested in the brain)
is triggered by the presence of certain grammatical constructions. It
sets the parameters corresponding to these constructions to the
appropriate values. In this fashion, it is theorized, all of the
parameters in the UG are set and children ``learn'' their native tongue.

Genetic algorithms (GAs) do not fit this model of learning a language,
but nevertheless they provide a method for finding the correct parameter
settings of a language. GAs are modelled after the survival of the
fittest model of evolution in biology. A search begins with a population
of randomly generated individuals. Given a fitness test, the fitness of
each individual is determined. The more fit an individual is, the more
likely it is to reproduce and thus pass on its traits to the next
generation. This fitness test simulates the competition for mates and
resources, as well as the longevity of an individual. Mating and
mutations provide variation of the ``gene'' pool so that new
combinations of traits can be generated and tested.  This process of
evolution based on reproduction, mating, and mutation continues for
generation after generation and, in this way, the optimal, or near
optimal, individual (or solution) is found. In the case of natural
language parameters, individuals are a series of parameter values. The
fitness test would be the ability of the parameter settings, along with
the corresponding principles, to parse sentences from the target
language.  Given input sentences from a natural language, a genetic
algorithm can be used to search for the correct parameter settings for
that language.

\begin{figure}
\center{\leavevmode{\epsfbox{flow.ps}}}
\caption{Flowchart of the genetic algorithm used in this thesis.}
\end{figure}

The purpose of my thesis was to write a program which would learn the
word order of a language, given only natural sentences from that
language. I used a simple genetic algorithm to search for the values of
word order parameters for English. The parameters consist of the
ordering of the right-hand side of binary grammar rules, such as
``NP$\rightarrow$AP N'' or ``NP$\rightarrow$N AP'' where NP means Noun
Phrase, AP means Adjective Phrase, and N stands for Noun. In English,
the former is the correct ordering. Individuals consist of numbers which
represent the order of each phrase in the grammar. Thus each individual
has a grammar associated with it. The fitness test consists of using an
individual's implicit grammar to parse a corpus of natural English
sentences. The parser that is used is very simple and just returns true
or false, depending on whether a sentence could be parsed with the given
grammar. The more sentences an individual's grammar can parse
successfully, the more fit the individual is. Using the process of
reproduction, mating, and mutation, the genetic algorithm finds the
parameter settings representing a grammar which can correctly parse
all sentences in the corpus. (See figure 1-1.)

\begin{figure}
\begin{verbatim}
> (evolve 50 10 50 0.94)
Generation 1: Best=(0 1 1 0 0 0 0 1 1 0 1 0 1 0), 57% fit
Generation 2: Best=(0 1 1 0 0 1 1 1 0 0 1 0 0 0), 82% fit
Generation 3: Best=(0 1 1 0 0 1 1 1 0 0 1 0 0 0), 82% fit
Generation 4: Best=(0 1 1 0 1 0 0 1 0 1 1 1 0 0), 86% fit
Generation 5: Best=(0 1 1 0 0 0 0 1 0 0 1 0 0 0), 91% fit
Generation 6: Best=(0 1 1 0 0 0 0 1 0 0 1 0 0 0), 91% fit
Generation 7: Best=(0 1 1 0 0 0 0 1 0 0 1 0 0 0), 91% fit
Generation 8: Best=(0 1 1 0 0 0 0 1 0 0 1 0 0 0), 91% fit
Generation 9: Best=(0 1 1 0 0 0 0 1 0 0 1 0 0 0), 91% fit
Generation 10: Best=(0 1 1 0 0 0 0 1 0 0 1 1 0 0), 95% fit
(0 1 1 0 0 0 2 1 0 0 1 1 0 0)
\end{verbatim}
\caption{An example run in which the correct parameter settings are
found after 10 generations, with a generation size of 50 individuals, a
mutation rate of one every 10 generations, and a brute force search used
after the fitness of the best individual exceeded 94\%.}
\end{figure}

For the most part, the general concept worked. (See figure 1-2.) A minor
problem was encountered with the randomness in the genetic algorithm.
When a near optimal solution is found, or when the average fitness is
high, the genetic algorithm becomes a ``random walk'' around the optimal
solution and the fitness does not increase quickly (see section 3.5). It
could take hundreds of generations for the last parameter to click into
place finally. Thus, a brute force search can be used to finish up the
search process once the genetic algorithm has found a near optimal
solution.  Another problem was caused by the ``free order'' parameter
setting. A free order parameter means that a language allows both
orderings of the right-hand side of a binary grammar rule.  In English,
the only free ordering is that of a verb and an adverbial phrase.
However, even though adverbial free ordering is questionable, other
natural languages do have free ordered phrases and thus are necessary
for a general theory of parameters.  Having free ordered phrases not
only increases the time it takes to parse a sentence (since two
orderings must be tested for a phrase), but it also overgeneralizes
parameter settings. Thus, with incomplete input, there may be more than
one grammar which can parse the corpus of input ``perfectly'' because
free ordered phrases can interact in such a way as to parse a given
sentence successfully, but not correctly in terms of English syntax. To
solve this problem, either the ability to have free ordered phrases must
be eliminated (which is not a linguistically realistic solution) or the
input sentences must be specific enough to rule out ``perfect''
overgeneralized parameter settings.

After overcoming the above problems, the genetic algorithm was able to
find the correct parameter settings remarkably well. Due to the
randomness inherent in the genetic algorithm, the time (or number of
generations) required to home in on the solution varied. However, a
solution was usually found within 100 generations\footnote{For the
sample runs included in the appendix, if a solution was found, it was
found with an average of about 30 generations.}, using the brute force
search once the most fit individual exceeded a given fitness level.
Overall, given the results of this simple system, it seems feasible to
use genetic algorithms to enable a computer to ``learn'' a language. The
biggest problem facing the use of GAs to find the correct parameter
settings for languages is that not all of the parameters (or principles,
for that matter) that define languages have been formalized and agreed
upon. Thus, until a complete theory of Principles and Parameters is
reached, GAs can only be used to learn certain features of natural
languages.

