\chapter{Theory}

\section{Principles and Parameters}

\begin{quotation}
If the child is viewed simply as a {\em tabula rasa}, as having no
predisposition to analyzing data in terms of one formal system rather
than any other one, then it is difficult or impossible to explain how
the child does in fact come to acquire his first language within a
relatively short period of time. \cite[Comrie, pp.2-3]{comrie}
\end{quotation}

The theory of Universal Grammar in linguistics explains the ease with
which children acquire their native language and also formalizes the
similarities and differences between languages. Without some innate
ability to acquire language, it seems hard to believe that children
could acquire their native tongue so rapidly and uniformly.  Somehow,
children exposed to the same language acquire the same grammar even
though they are given different input. For example, one adult English
speaker has basically the same descriptive\footnote{As opposed to {\em
prescriptive}, which is what an English class teaches.} grammar as
another.  Even at an early age, children have knowledge of complex
linguistic rules such as the Binding Principle which was never taught to
them explicitly.  The Binding Principle determines what antecedents are
allowed for a pronoun or a reflexive. Children know that in the sentence
``He told him to go away'' the pronoun ``him'' cannot be bound to the
pronoun ``he''. That is, ``him'' and ``he'' cannot refer to the same
person because a pronoun, like ``him'', must be unbound in its governing
category, which in this case is the whole sentence. Thus, some part of
language must be innate to be able to explain the uniformity and the
ease of language acquisition, especially in the absence of explicit
teaching.  However, it is easy to see that a specific language in its
entirety is not innate, since there are many different languages in the
world and children are not constrained to learn only the language of
their parents and no other. Indeed, children learn whatever
language\footnote{Or even {\em languages}, if they are in a multilingual
environment. Explaining how multiple languages are acquired
simultaneously is beyond the scope of my thesis.} they happen to be
exposed to while they grow up, which could be very different from the
language of their parents.

The Universal Grammar theory also helps explain the similarities and
differences among natural languages. For instance, the Binding Principle
mentioned above is parameterized over the governing category in the UG.
For English, the governing category of a pronoun or reflexive is the
minimal clause with a subject, which is usually just the whole sentence.
Thus, pronouns must be free (unbound) in their governing categories,
while reflexives, such as ``himself'', must be bound in their governing
categories. For example, in the sentence ``John asked me to call him'',
the antecedent of ``him'' can be ``John'' because ``John'' is not in the
governing category of ``him'' and thus ``him'' is free within its
governing category. The governing category for ``him'' is the infinitive
(untensed) clause ``me to call him'' where ``me'' is the subject.  In
Icelandic, however, the governing category for a pronoun is the minimal
enclosing clause having tense. So in the equivalent Icelandic sentence
to ``John asked me to call him'', the pronoun ``him'' cannot refer to
``John'' as its antecedent since the minimal clause with tense is the
entire sentence and ``him'' must therefore not be bound to a noun phrase
within the sentence. The Binding Principle is the same for both English
and Icelandic, however the value of the governing category parameter is
different and explains exactly how binding in English is different from
binding in Icelandic. (See \cite[Wexler]{wexler}.) Thus, in this way,
the Principles and Parameters theory is able to formalize the variations
among languages.

\subsection{Word Order Parameter Theory}

One of the main variations among languages is word order. The Principles
and Parameters theory for the word order of languages involves many
parts. Not only does the ``headedness'' of phrases play a part, but also
the thematic roles of words contribute more information to the final
word order of a language. A phrase can be head-initial or head-final,
meaning that the main part of a phrase (i.e.  the verb in a verb phrase)
either at the beginning or the end of the phrase. For example, in
English, phrases are mainly head-initial; the verb is first in a verb
phrase, the preposition\footnote{It's called a {\em pre}position because
of its position in the phrase. Other languages have {\em post}positional
phrases.} is first in a prepositional phrase, etc.  The structure for
phrases is described by X-bar theory and the headedness of phrases
is determined by parameters which indicate head-initial or head-final.
Word order also comes from the thematic roles of words. Verbs are
subcategorized according to the arguments they take. For example, the
verb ``give'' takes as arguments a ``patient'' and a ``beneficiary''. In
the sentence, ``John gave Mary the dog'', ``the dog'' is the patient, or
the object being given. ``Mary'' is the beneficiary, or recipient of the
object being given. ``John'' is the ``agent'' of the sentence, or the
one doing the action described by the verb phrase. ``Agent'',
``patient'', and ``beneficiary'' are all thematic roles. The order of
the arguments to a verb are usually fixed, in order to avoid confusion
as to which is the patient, etc\footnote{In languages such as Japanese
and Korean, word order is much freer, but special tags indicate the
thematic roles of words in the sentence.}. If the order of the arguments
to the verb ``give'' were not fixed, the above sentence would be
syntactically (and semantically) ambiguous since ``the dog'' could be
the beneficiary and ``Mary'' could be the ``patient''. X-bar theory,
thematic role theory, and several other theories all help determine the
word order of a language.

X-bar theory is perhaps the simplest to understand: a phrase is simply a
head with its arguments. The arguments are all on one side of the head
or another. Thus, the grammar consists of a set of binary rules and the
parse trees it generates consist of binary branching
nodes\footnote{Berwick, 6.863, Spring 1992}. For example, a verb phrase
could look like figure 2-1. The bar above the V stands for ``phrase'' and
indicates that the verb is the head of the phrase. This can also be
denoted by V'.  Double-bar phrases (also denoted with double quotes,
i.e. V'') indicate complements to the single-bar phrases they dominate.
The complement of a verb phrase, for example, could be an adverb. Thus,
the V'' structure that appears in figure 2-2  consists of the argument
and the complement to the verb. The head of the V'' is the V' and the
argument is the adverb which complements the V'.  In this way, the word
order of a language can be specified through the headedness of each of
the phrases in the binary grammar. Of course, a binary grammar cannot
give the order of multiple arguments of verbs.  That must be done
through the theory of thematic roles and other principles. But a
parameterized X-bar theory can give the general framework of the word
order of a language.

\begin{figure}
\center{\leavevmode{\epsfbox{xbar1.ps}}}
\caption{The structure of a verb phrase under X-bar theory.}
\end{figure}

\begin{figure}
\center{\leavevmode{\epsfbox{xbar2.ps}}}
\caption{The structure of a V'' phrase, which includes a verb, its
argument, and its complement.}
\end{figure}

\subsection{Word Order Parameters Used}

In my thesis, I have used a set of binary grammar rules loosely modelled
after the X-bar theory described above. I have ignored the contribution
of thematic roles to word order, since thematic roles would greatly
complicate the parser and system needed to interpret these parameters.
Thus, the word order parameters in my system are merely the headedness
of each of the phrases in the grammar: i.e., head-final, head-initial,
or free order. Free order means that the head of a phrase can appear
first or last.  The only example of this in English is the position of
an adverbial phrase with respect to the verb. Figure 2-3 shows the
``template'' grammar, upon which the parameters are based.
``Head-initial'' versus ``head-final'' for each phrase in a specific is
defined relative to the headedness of the phrases in the template
grammar.

\begin{figure}
\begin{verbatim}
                            C'   --> (C) I'' 
                            I''  --> I' (Aux)
                            I'   --> VP' D' 
                            D'   --> (D) NP'
                            VP'  --> VP (C')
                            NP'  --> NP (C')
                            VP   --> V' (Adv')
                            NP   --> N' (A') 
                            V'   --> V+o (P')
                            N'   --> N (P')
                            Adv' --> Adv (Spec)
                            A'   --> Adj (Spec)
                            P'   --> P D' 
                            V+o  --> V (D') 
\end{verbatim}
\caption{The template grammar from which word order parameters are
derived consists of 14 phrases. C stands for Complement, e.g. ``what''.
I stands for Inflection.  Aux stands for Auxiliary verb. VP is Verb
Phrase, NP is Noun Phrase, D is Determiner, Adv is Adverb, A and Adj are
Adjective, V is Verb, N is Noun, P is P-position, and Spec is Specifier
(e.g.  ``very''). V+o substitutes for the full subcategorization of
verbs and simply allows zero or one object for any verb. Parentheses
around a phrase or part of speech on the right side of a grammar rule
means that that phrase or part of speech is optional.}
\end{figure}

Thus there are 14 word order parameters in my system, one for each
phrase in the template grammar. For a given language, the majority of
the parameters should be the same, since languages are usually primarily
head-initial or head-final. For example, English is mainly head-initial.
However, the grammar that I have outlined is by no means linguistically
realistic, so the head-initial {\em vs.} head-final parameter setting might
not mean much in terms of the actual headedness of a natural language.

\section{Genetic Algorithms}

\nocite{goldberg}

Nature uses a particularly well-known search and optimization algorithm:
genetics and the survival of the fittest. Creatures everywhere undergo
this process at one time or another. Good survival traits get passed on
to future generations as the fittest mate and reproduce. Characteristics
of the population change slowly with time as these traits win out over
other less optimal traits. Genes provide the encoding of the traits.
Competition among individuals for resources and mates provides a
``fitness test'' which determines which individuals' traits are the most
likely to survive to the next generation.  Mating passes traits (as
genes) on, in various combinations, to the offspring. Every so often, a
mutation will occur which will alter a gene. If this mutation provides a
good survival trait, it might be passed on to future generations.

Genetic algorithms in computer science follow this natural pattern of
search and optimization. For some problem for which the optimal or near
optimal solution is sought, an encoding of the relevant material that
makes up a solution must be devised. This corresponds to the genes. Then
a fitness test must be created that can determine the fitness of each
proposed solution (individual). This corresponds to the competition
among individuals in a population. Once the fitness of all the
individuals in a generation are known, replicas of individuals are
placed in a gene pool. The number of replicas of an individual is based
on the fitness of that individual; the fitter the individual, the more
replicas of it go into the gene pool. Then individuals in the gene pool
are randomly mated and mutation, if any, is introduced. The resulting
individuals constitute the next generation and the whole process of
reproduction, mating, and mutation starts over. Eventually an optimal or
near-optimal individual appears and the search is over.
