\chapter{Results and Conclusions}

Overall, the genetic algorithm managed to find sets of parameter
settings which parsed the corpus of input successfully. The fact that it
found parameter settings other than the ones expected which worked is
mainly due to the inadequacy of the grammar, parameters, and input. The
input was not specific enough, or did not provide enough positive
evidence, to set the parameters uniquely. The grammar and parameter
system used was too limited, in that it constrained the types of
sentences that could be parsed. Had the grammar allowed richer
grammatical constructions, it is possible that the input could have been
chosen to provide enough examples to set the parameters uniquely. As it
is, though, several other sets of parameter settings were found whose
corresponding grammar could parse the corpus of input perfectly, but not
necessarily correctly in terms of syntax. For example, the parameter
which specifies the order of a verb phrase and its optional complement
phrase could be set to ``head-final'', meaning that the complement
phrase would come before the verb, and the parameter which specifies the
order of a noun phrase and its optional complement phrase could be set
to ``free''. While these are not the settings for English, since a
complement phrase for a verb phrase comes {\em after} the verb phrase,
the interaction between these two parameters is such that a sentence
such as ``The animals that Janna saw thought she had big eyes'' could be
parsed to have a syntactic structure other than the true English syntactic
structure. Thus, this problem does not reflect on the genetic algorithm
as a way to search for a solution; it only shows that the choice of
encoding of the relevant information is faulty and does not define clear
solutions. Given the grammar and input it had to work with, the genetic
algorithm did its best to find an optimal solution, and it usually did.

\begin{figure}
\leavevmode{
\begin{verbatim}
Parameter Settings               Fitness
------------------               -------
0 1 1 0 0 1 2 1 0 0 1 1 0 0      95%
        |
0 1 1 0 2 1 2 1 0 0 1 1 0 0      98%
          |
0 1 1 0 2 2 2 1 0 0 1 1 0 0      100%
\end{verbatim}}
\caption{An example of how the interactions between parameters and the
brute force search method cause overgeneralized solutions to be found.}
\end{figure}

Randomness plays a major part in the genetic algorithm\footnote{How many
times does ``random'' or a variation thereof appear in this paper?} and
thus the results reflect this randomness. The GA could find a solution
within 10 generations, or it could fail to find a solution within 100
generations. The choice of the size of a generation\footnote{The larger
the generation size, the less generations it generally takes to find a
solution, since the variation among a large number of individuals is
greater and the chances that a near optimal solution is among these
individuals is high.} and the mutation rate partially caused this,
however the randomness in mating and mutation is the main cause since it
controls how the genes are varied to create new combinations (after the
zeroth generation). A ``fit'' combination could be stumbled upon in the
first generation, or it could be found in the 99th. Once a near optimal
solution is found, the randomness makes matters worse since the GA
becomes a random walk around an optimal solution. The method for
overcoming this, namely the brute force search used after certain level
of fitness is achieved, did lessen the number of generations generally
needed to find a solution.  However, the brute force search often caused
overgeneralized solutions to be found. The complex interactions among
parameters favor the overgeneralized free-order parameter setting and
since the brute force search changes one parameter at a time, from left
to right, it usually produced overgeneralized solutions. (See figure
4-1.)  The ability to have free-order phrases in itself causes
overgeneralized solutions. For example, the parameter settings ``0 1 2 0
0 0 2 1 0 0 1 1 0 0'' and the corresponding grammar is able to parse
every sentence in the corpus.  The free order setting for the  
Inflection Phrase, the phrase which determines whether the subject comes
before the predicate, or {\em vice versa}, is superfluous. It includes
both orders of the phrase and thus will parse the input correctly,
always using the head-final order. So, solutions with superfluous
free-order phrases were also found by the GA.

Despite these problems, I believe that the concept of using a genetic
algorithm to find the parameter settings of a certain language works.
Genetic algorithms are able to separate the ``good'' traits from the
``bad'' traits and propagate the good traits to future generations to
combine with other good traits until the optimal solution is found. When
the search space is large, this method of find a solution is better than
a method that would have to consider each variable or parameter in turn.
The problems that my program encountered were not due to any fault in
the genetic algorithm method of searching. They were caused by the
limited variety of input sentences and a poor choice of a parameter
system, which allowed multiple solutions to exist in the search space. A
more sophisticated parameter system would allow a greater variety of
input sentences to be used, and both of these together should narrow the
solutions in the search space down to just the one solution which
corresponds to the parameters of the target language. All of the
parameters that determine word order for all languages have yet to be
formalized and thus developing a truly realistic parameter system is
difficult. When such a parameter system is developed, the corpus of
input sentences could theoretically include {\em all} of the parents'
sentences in the English Childes database, given a sufficiently
sophisticated parser. This would solve the problem of having input that
does not provide enough variation since if children can acquire English
from this input, so should the genetic algorithm. Thus, the system I
have developed in this thesis is mainly constrained by the limitations
of the linguistic theory used. I hope to continue working on the
linguistic portion of the system, as well as exploring variations of
genetic algorithms, in an attempt to develop a similar (but more
sophisticated system) which can learn the word order of any natural
language when given only natural sentences from the target language.
