\documentstyle[jair,twoside,11pt,mynamed,theapa,psfig]{article}
\input epsf %% at top of file
\jairheading{6}{1997}{177-209}{10/96}{5/97}

\newcommand{\ie}{i.e.,\ }
\newcommand{\eg}{e.g.,\ }
\newcommand{\ea}{et al.\ }
\newcommand{\kbann}{{\sc Kbann}}
\newcommand{\topgen}{{TopGen}}
\newcommand{\strawman}{{\sc strawman}}
\newcommand{\regent}{{\sc Regent}}
\newcommand{\addemup}{{\sc Addemup}}
\newcommand{\mymax}{{\sc Max}}
\newcommand{\seta}{{\tt A}}
\newcommand{\setb}{{\tt B}}
\newcommand{\myand}{{\sc and}}
\newcommand{\myor}{{\sc or}}

\renewcommand{\topfraction}{0.9}
\renewcommand{\bottomfraction}{0.9}
\renewcommand{\textfraction}{0.0}
\renewcommand{\floatpagefraction}{0.7}
\setcounter{topnumber}{5}
\setcounter{bottomnumber}{5}

\firstpageno{177}

\ShortHeadings{Connectionist Theory Refinement}
{Opitz \& Shavlik}

\begin{document}

\title{Connectionist Theory Refinement: \\ Genetically Searching
the Space of Network Topologies}
\author{\name David W. Opitz
\email opitz@cs.umt.edu \\
\addr Department of Computer Science  \\
University of Montana \\
Missoula, MT 59812  USA
\AND
\name Jude W. Shavlik
\email shavlik@cs.wisc.edu \\
\addr Computer Sciences Department \\
University of Wisconsin \\
1210 W. Dayton St. \\
Madison, WI 53706  USA
}

\maketitle
%\vspace{0.75in}

\begin{abstract}
\input{abstract}
\end{abstract}

%\pagenumbering{arabic}

\input{intro.tex}
\input{background.tex}
\input{kbann.topgen.tex}
\input{regent.tex}
\input{results.tex}
\input{discussion.tex}
\input{related.tex}
%\input{future.tex}
\input{conclusions.tex}

\acks{This work was supported by Office of Naval Research grant 
N00014-93-1-0998 and National Science Foundation grant IRI 95-02990.
Thanks to Richard Maclin, Richard Sutton, and three anonymous reviewers
for their helpful comments.
This is an extended version of a paper published in
{\it Machine Learning: Proceedings of the Eleventh International Conference},
pp. 208-216, New Brunswick, NJ, Morgan Kaufmann.
David Opitz completed a portion of this work while a graduate
student at the University of Wisconsin and a professor 
at the University of Minnesota, Duluth.}

%\def\baselinestretch{1.0} \small\normalsize
\bibliography{abbrev,wisc_ml,my}
\bibliographystyle{theapa}

\end{document}
An algorithm that learns from a set of examples should ideally be
able to exploit the available resources of (a) abundant computing power and
(b) domain-specific knowledge to improve its ability to generalize.
Connectionist theory-refinement systems, which use
background knowledge to select a neural network's topology
and initial weights, have proven to be 
effective at exploiting domain-specific knowledge; however,
most do not exploit available computing power.  This weakness occurs because 
they lack the ability to refine the topology of the neural networks they 
produce, thereby limiting generalization, especially when given impoverished
domain theories.  
We present the \regent\ algorithm which uses 
(a)~domain-specific knowledge to help create an initial 
{\it population} of knowledge-based neural networks
and (b)~genetic operators of crossover and mutation 
(specifically designed for knowledge-based networks) to 
continually search for better network topologies.
Experiments on three real-world domains indicate
that our new algorithm is able to significantly increase generalization  
compared to a standard connectionist theory-refinement system, 
as well as our previous algorithm for growing knowledge-based networks.
\section{Using Data, Prior Knowledge, and Available CPU Cycles}

A system that learns from a set of labeled examples is called an
{\it inductive learner} (alternately, a {\it supervised}, {\it empirical}, or
{\it similarity-based} learner).
The output for each example is provided by a teacher, and the set 
of labeled examples given to a learner is called the {\it training} set.
The task of inductive learning is to generate from the training set a concept
description that correctly predicts the output of all future examples, not
just those from the training set.
Many inductive-learning algorithms have been previously studied
(\eg Michalski, 1983; Quinlan, 1986; Rumelhart et al., 1986).
\nocite{michalski.aij83,mitchell.aij82,quinlan.mlj86,rumelhart.pdp86a}
These algorithms differ both in their concept-representation language, and in
their method (or {\it bias}) for constructing a concept within this language.
These differences are important since they determine which concepts
a classifier will induce.

An alternative to the inductive learning paradigm is to build a concept 
description not
from a set of examples, but by querying experts in the field and directly
assembling a set of rules that describe the concept (\ie build an
{\it expert system}; Waterman, 1986).
\nocite{waterman.book86}
A problem with building expert systems is that the 
theories derived from interviewing the
experts tend to be only approximately correct.
Thus, while the expert-provided domain theory
is usually a good first approximation of the concept 
to be learned, inaccuracies are frequently exposed during empirical testing.

{\it Theory-refinement systems}
\cite{ginsberg.aaai90,ourston.aij94,pazzani.mlj92,towell.aij94}
are systems that revise a theory on the basis of a collection of 
examples.  These systems try to improve the theory by making minimal repairs
to the theory to make it consistent with the training data.
Changes to the initial domain theory should be kept to a minimum
because the theory presumably contains useful information,
even if it is not completely correct.
These hybrid learning systems are designed to learn from both theory and data,
and empirical tests have shown them to achieve high generalization with
significantly fewer examples than purely inductive-learning techniques
\cite{ourston.aij94,pazzani.mlj92,towell.aij94}.
Thus, an ideal inductive-learning system should be able to incorporate any
background knowledge that is available in the form of a domain theory
to improve its ability to generalize.

As indicated earlier, available computer time is also an important
resource since (a)~computing power is rapidly increasing, and
(b) for most problems an expert is willing to wait a lengthy period
for an improved concept.
For these reasons, one should develop ``anytime'' learning algorithms that can
continually improve the quality of their answer over time.
Dean and Boddy \citeyear{dean.aaai88} defined the criteria for
an anytime algorithm to be: (a) the algorithm can be suspended
and then resumed with minimal overhead, (b) the algorithm can be
stopped at any time and return an answer, and (c) the algorithm must
return answers that improve over time.
While these criteria were created for planning and scheduling algorithms,
they can apply to inductive learning algorithms as well.\footnote{
Our use of the term {\it anytime learning} differs from that of Grefenstette 
and Ramsey \citeyear{grefenstette.mlc92}; they use it to mean continuous 
learning in a changing environment.}
 
Most standard inductive learners,
such as backpropagation \cite{rumelhart.pdp86a} and ID3 \cite{quinlan.mlj86},
are unable to continually improve their answers (at least until
they receive additional training examples).
In fact, if run too long, these algorithms tend to ``overfit'' the training
set \cite{holder.thesis}.
Overfitting occurs when the learning algorithm produces a concept
that captures too much information about the training examples, and
not enough about the general characteristics of the domain as a whole.
While these concepts do a great job of classifying the training instances,
they do a poor job of generalizing to new examples -- our ultimate
measure of success.
To help illustrate this point, consider the typical regression case shown in
Figure~\ref{idraw.overfit}.  Here, fitting noisy data
with a high-degree polynomial is likely to lead to poor generalization.
 
\begin{figure}
\centerline{\psfig{figure=idraw.overfit,height=2.5in}}
\caption[Example of overfitting from regression.]
{This is a classical regression
example where a smooth function (the solid curve) that does not fit all
of the noisy data points (the x's) is probably a
better predictor than a high-degree polynomial (the dashed curve).}
\label{idraw.overfit}
\rule{\textwidth}{0.5pt}
\end{figure}

The general framework we use for encouraging our algorithm to
improve its answer over time is quite simple.
We spend our computer time considering many different possible
concept descriptions, scoring each possibility, and always keeping the
description that scores the best.
Our framework is {\it anytime} with respect to the scoring function.
The scoring function is only an {\it approximate} measure of 
generalization and is obviously still prone to the problems of overfitting;
thus there is no guarantee that generalization will monotonically 
decrease over time.  
Nevertheless, assuming an {\it accurate} scoring function, then as long as 
we are considering a wide range of {\it good} possibilities, the quality
of our best concept is likely to improve for a longer period of time.

\section{Conclusion}

An ideal inductive-learning algorithm should be able to
exploit the available resources of extensive computing power and 
domain-specific knowledge to improve its ability to generalize.
\kbann\ \cite{towell.aij94} has been shown to be effective at translating a 
domain theory into a neural network; however, \kbann\ suffers in that it
does not alter its topology.  \topgen\ \cite{opitz.kbsys95}
improved the \kbann\ algorithm by using available
computer power to search for effective places to add nodes to the
\kbann\ network; however, we show empirically that \topgen\ suffers from
restricting its search to expansions of the \kbann\ network,
and is unable to improve its performance after searching beyond
a few topologies.  Therefore \topgen\ is unable to exploit all available
computing power to increase the correctness of an induced concept.

We present a new algorithm, \regent, that uses a specialized genetic
algorithm to broaden the types of topologies considered during \topgen's search.
Experiments indicate that \regent\ is able to significantly
increase generalization over \topgen; hence, our new algorithm is successful
in overcoming \topgen's limitation of only searching a
small portion of the space of possible network topologies.
In doing so, \regent\ is able to generate a good solution quickly, by using
\kbann, then is able to continually improve this
solution as it searches concept space.
Therefore, \regent\ takes a step toward a true anytime theory refinement 
system that is able to make
effective use of problem-specific knowledge and available computing cycles.

\section{Discussion and Future Work}
\label{section.discuss}

Towell \citeyear{towell.thesis} showed \kbann\ generalized better than
many other machine learning algorithms on the promoter and splice-junction 
domains (the RBS dataset did not exist then).
Despite this success, \regent\ is able to effectively use available computer 
cycles to significantly improve generalization over both \kbann\ and our
previous improvement to \kbann, the \topgen\ algorithm.
\regent\ reduces \kbann's test-set error by 12\% for the RBS domain,
22\% for the splice-junction domain, and 33\% for the promoter domain; it
reduces \topgen's test-set error by 10\% for the RBS domain,
17\% for the splice-junction domain, and 21\% for the promoter domain.
Also, \regent's ability to use available computing time is further aided by
being inherently parallel, since we can train many networks simultaneously.

Further results show that \regent's two genetic operators complement each other.
The crossover operator considers a large variety of network topologies
by probabilistically combining rules contained within two ``successful'' KNNs.
Mutation, on the other hand, makes smaller, directed improvements
to members of the population, while at the same time adding diversity
to the population by adding new rules to the population.
Equal use of both operators, therefore, allows a wide variety of topologies
to be considered as well as allowing incremental
improvements to members of the population.

Since \regent\ searches through many candidate networks, it is important for it
to be able to recognize the networks that are likely to generalize the best.
With this in mind, our first planned extension of \regent\ is to develop
and test different network-evaluation functions.
We currently use a validation set; however, validation sets have several 
drawbacks.
First, keeping aside a validation set decreases the number of training
instances available for each network.
Second, the performance of a validation set can be a noisy approximator
of the true error \cite{mackay.nc92a,weigend.ijns90}.
Finally, as we increase the number of networks searched, \regent\ may start
selecting networks that overfit the validation set.  In fact, this
explains the occasional upward trend in test-set error,
from both \topgen\ and \regent, in Figure~\ref{regent.dna.plot}.

To avoid the problem of overfitting the data, a common regression trick is
to have a cost function that includes a ``smoothness'' term along with
the error term.
The best function, then, will be the smoothest function that also fits the data
well.
For neural networks, one can add to the estimated error a smoothness
component that is a measure of the complexity of the network.
The complexity of the network cannot simply be estimated by counting
the number of possible parameters, since there tends to be significant
duplication in the function of each weight in a network, especially
early in the training process \cite{weigend.cmss93}.
Two techniques that try to take into account the {\it effective} size
of the network are Generalized Prediction Error \cite{moody.nips4}
and Bayesian methods \cite{mackay.nc92a}.

Quinlan and Cameron-Jones \citeyear{quinlan.ijcai95}
propose adding an additional term to the accuracy and smoothness term
that takes into account length of time spent searching.
They coin the term ``oversearching'' to describe the phenomenon where
more extensive searching causes lower predictive accuracy.
Their claim is that oversearching is orthogonal to overfitting, and thus these
complexity-based methods alone cannot prevent oversearching.
As we increase the number of networks we consider during a search,
we too may start oversearching, and thus plan to investigate
adding an oversearching penalty term as well.

As indicated earlier, \regent\ is Lamarckian in that it passes 
local optimizations of individuals (\ie the trained weights of a network)
to offspring.  A viable alternative, called the Baldwin effect 
\cite{ackley.alife2,baldwin.1896,belew.book96,hinton.complexsys87},
is to have local search still change the
fitness of an individual (backpropagation learning in this case),
but then not pass these changes on to the offspring (this form of 
evolution is Darwinian in nature).
Even though what is learned is not explicitly coded into the genetic material,
individuals who are best able to learn will
have the most offspring; thus learning still impacts evolution.
In fact this form of evolution can sometimes outperform forms of Lamarckian 
evolution that employ the same local search strategy \cite{whitley.ppsn94}.
Future work is to investigate the utility of the Baldwin effect on \regent.
In this case we would not cross over the trained networks, but instead
cross over the initial weight settings {\it before} backpropagation
learning took place.

%\cite{bala.evcomp96,harvey.evcomp96,turney.evcomp96}

Finally, often times there are multiple, even conflicting, theories about a domain.
Future work, then, is to investigate ways of using
all of these domain theories to seed the initial population.
Although the results in Section~\ref{regent.init.res} show that including
randomly generated networks degrades generalization performance, seeding the
population with multiple approximately correct theories should not degrade
generalization, assuming the networks will have about the same initial
correctness.
Thus \regent\ should be able to naturally combine good parts of multiple
theories.
Also, for a given domain theory, there are many different but equivalent
ways to represent that theory using a set of propositional rules.
Each representation leads to a different network topology, and even though
each network starts with the same theory, some topologies may be more
conducive to neural refinement.

\section{Future Work on REGENT}

Since \regent\ is searching through many candidate networks, it is important
to be able to recognize the networks that are likely to generalize the best.
I currently use a validation set; however, MacKay \citeyear{mackay.nc92a}
has shown that a validation set can be a noisy estimate of the true error.
Also, as I increase the number of networks searched, \regent\ may start
selecting networks that overfit the validation set.  In fact, this may be
a possible explanation for the occasional upward trends in test-set error,
from both \topgen\ and \regent, in Figure~\ref{regent.dna.plot}.
Future work, then, is to investigate selection methods that do not use a
validation set, which would also allow \regent\ to use all the training 
instances to train the networks.  

Often times, there are multiple, even conflicting, theories about a domain.
Future work, then, is to investigate ways of using
all of these domain theories to seed the initial population.
Although the results in Section~\ref{regent.init.res} show that including
randomly generated networks degrades generalization performance, seeding the
population with multiple approximately correct theories should not degrade
generalization, assuming the networks will have about the same initial 
correctness.
Thus \regent\ should be able to naturally combine good parts of multiple
theories.  
Also, for a given domain theory, there are many different but equivalent
ways to represent that theory using a set of propositional rules.
Each representation leads to a different network topology, and even though 
each network starts with the same theory, some topologies may be more 
conducive to neural refinement.
\section{Introduction}
Many scientific and industrial problems can be better understood by
learning from samples of the task.
For this reason, the machine learning and statistics communities
devote considerable research effort to {\it inductive-learning} algorithms.
%algorithms that learn from a set of examples.
Often, however, these learning algorithms fail to capitalize on
a number of potentially available resources, such as domain-specific knowledge 
or computing power, that can improve their ability to generalize.
Using domain-specific knowledge is desirable because
inductive learners that start with an approximately correct theory
can achieve improved ``generalization''  (accuracy on examples
not seen during training) with significantly fewer training examples
\cite{ginsberg.aaai90,ourston.aij94,pazzani.mlj92,towell.aij94}.
Making effective use of available computing power is desirable because,
for many applications, it is more important to obtain
concepts that generalize well than it is to induce concepts quickly.
In this article, we present an algorithm, called \regent\ 
(REfining, with Genetic Evolution, Network Topologies), that utilizes available
computer time to extensively search for a neural-network topology that best
explains the training data while minimizing changes to a domain-specific 
theory.

Inductive learning systems that utilize a set of approximately correct,
domain-specific inference rules (called a {\it domain theory})
which describe what is currently known about the domain, are called
{\it theory-refinement} systems.
Making use of this knowledge has been shown to be important since these 
rules may contain insight not easily obtainable from the current set of 
training examples \cite{ourston.aij94,pazzani.mlj92,towell.aij94}.
For most domains, an expert who created the theory
is willing to wait for weeks, or even months,
if a learning system can produce an improved theory.
Thus, given the rapid growth in computing power, we believe it is 
important for learning techniques to be able to trade off the expense
of large numbers of computing cycles for gains in predictive accuracy.
Analogous to {\it anytime planning} techniques \cite{dean.aaai88}, we believe
machine learning researchers should create 
better {\it anytime learning} algorithms.
%\footnote{  
%Our use of the term {\it anytime learning} differs from Grefenstette \& Ramsey
%(1992); they use it to mean continuous learning in a changing environment.}
Such learning algorithms should produce a good concept
quickly, then continue to search concept space,
reporting the new ``best'' concept whenever one is found.

We concentrate on connectionist theory-refinement systems,
since they have been shown to frequently generalize
better than many other inductive-learning and theory-refinement
systems \cite{fu.consci89,lacher.nn92,towell.thesis}.
\kbann\ \cite{towell.aij94} is an example of such a
connectionist system; it translates the provided domain theory into a neural
network, thereby determining the network's topology, and then refines
the reformulated rules using backpropagation \cite{rumelhart.pdp86a}.
However, \kbann, and other connectionist theory-refinement systems 
that do not alter their network topologies, suffer when given {\it impoverished}
domain theories -- ones that are missing rules needed to
adequately learn the true concept \cite{opitz.kbsys95,towell.aij94}.
\topgen\ \cite{opitz.kbsys95} is an improvement over these systems; it
heuristically searches through the space of possible network topologies
by adding hidden nodes to the neural representation of the domain theory.
\topgen\ showed statistically significant improvements over \kbann\
in several real-world domains \cite{opitz.kbsys95};
however, in this paper we empirically show that \topgen\ 
nevertheless suffers because it 
only considers simple expansions of the \kbann\ network. 

To address this limitation, we broaden the types of topologies that \topgen\ 
considers by using genetic algorithms (GAs).
We choose GAs for two reasons.
First, GAs have been shown to be effective optimization techniques because
of their efficient use of global information
\cite{goldberg.book89,holland.book75,mitchell.book96}.
Second, GAs have an inherent quality which makes them suitable for anytime
learning.
In ``off-line'' application mode \cite{dejong.thesis},
GAs simulate many alternatives and output the best alternative seen so far.

Our new algorithm, \regent, proceeds by first trying to generate, from
the domain theory, a diversified initial population.  It then
produces new candidate networks via the genetic operators of
{\it crossover} and {\it mutation}, after which these networks
are trained using backpropagation.
\regent's crossover operator tries to maintain the rule structure of 
the network, while its mutation operator adds nodes to a network by using the
\topgen\ algorithm.  Hence, our genetic operators are specialized for
connectionist theory refinement.
Experiments reported herein show that \regent\
is better able to search for network topologies than \topgen.

The rest of the paper is organized as follows.  In the next section,
we briefly argue for the importance of effectively exploiting data, theory, and 
available computer time in the learning process.
We then review the \kbann\ and \topgen\ algorithms.
We present the details of our \regent\ algorithm in Section 4.
This is followed by empirical results from three Human Genome Project domains.
In Section 6, we discuss these results, as well as future work.
We then review related work before concluding.

\section{Review of KBANN and TopGen }

The goal of this research is to exploit both prior knowledge and 
available computing cycles to search for the neural 
network that is most likely to generalize the best.
We proceed by choosing, as an initial guess,
the network defined by the \kbann\ algorithm.
We then continually refine this topology to find the best network
for our concept.
Before presenting our new algorithm (\regent), we give an overview of the
\kbann\ algorithm as well as our initial approach of refining a \kbann-created network's
topology (TopGen).

\subsection{The KBANN Algorithm}
\label{section.kbann}

\kbann\ \cite{towell.aij94}
works by translating a domain theory consisting of a set of propositional rules
directly into a neural network (see Figure~\ref{kbann.translation}).
Figure~\ref{kbann.translation}a shows a Prolog-like rule set that
defines membership in category $a$.  Figure~\ref{kbann.translation}b
represents the
hierarchical structure of these rules, with solid lines representing necessary
dependencies and dotted lines representing prohibitory dependencies.
Figure~\ref{kbann.translation}c represents the network \kbann\ creates
from this translation.
\begin{figure}[b]
%\rule{\textwidth}{0.5pt}
\centerline{\psfig{figure=idraw.kbann.trans,width=\textwidth}}
\caption[\kbann's translation process]
{KBANN's translation of a knowledge base into a neural network.
{\rm Panel (a) shows a sample propositional rule set in
Prolog \protect{\cite{clocksin.book87}} notation, panel (b) illustrates this
rule set's corresponding {\sc and}/{\sc or}
dependency tree, and panel (c) shows the resulting
network created by \kbann's translation.}}
\label{kbann.translation}
%\rule{\textwidth}{0.5pt}
\end{figure}
It sets the biases so that nodes representing
disjuncts have an output near 1 only when at least one of their
high-weighted antecedents is satisfied,
while nodes representing conjuncts must have all of
their high-weighted antecedents satisfied (\ie near 1 for positive links and
near 0 for negative links).  Otherwise activations are near 0.
\kbann\ creates nodes $b1$ and $b2$ in Figure~\ref{kbann.translation}c to
handle the two rules disjunctively defining $b$.
The thin lines in Figure~\ref{kbann.translation}c represent low-weighted links
that \kbann\ adds to allow these rules to add new antecedents
during backpropagation training.
Following network initialization,
\kbann\ uses the available training instances to refine the network links.
Refer to Towell \citeyear{towell.thesis}
or Towell and Shavlik \citeyear{towell.aij94} for more details.

\kbann\ has been successfully applied to several real-world problems, such as
the control of a chemical plant \cite{scott.nc92},
protein folding \cite{maclin.mlj93},
finding genes in a sequence of DNA \cite{opitz.kbsys95,towell.aij94},
and ECG patient monitoring \cite{watrous.inbook93}.
In each case, \kbann\ was shown to produce improvements in generalization
over standard neural networks for small numbers of training examples.
In fact, Towell \citeyear{towell.thesis} favorably compared \kbann\ with a
wide variety of algorithms, including purely symbolic theory-refinement
systems, on a version of the promoter and splice-junction tasks that
we include as testbeds in Section 5.

While training the \kbann-created network alters the antecedents of existing
rules, it does not have the capability of inducing new rules because
it does not add any additional hidden nodes during training.
For instance, \kbann\ is unable to add a third rule for inferring $b$
in Figure~\ref{kbann.translation}'s example.
To help illustrate this point, consider the following example.
Assume that Figure~\ref{kbann.translation}'s target concept consists 
of Figure~\ref{kbann.translation}a's domain theory plus the rule:
\begin{center}
$b$ :- not $d$, $e$, $g$.
\end{center}
Although we trained the \kbann\ network shown in Figure~\ref{kbann.translation}c
with all possible examples of this target concept, it was unable to completely
learn the conditions under which $a$ is true.
The topology of the \kbann\ network must be modified in order
to learn this new rule.
 
Studies show \cite{opitz.kbsys95,towell.thesis}
that while \kbann\ is effective at removing extraneous rules and antecedents
in an expert-provided domain theory,
its generalization ability suffers when given ``impoverished''
domain theories -- theories that are missing rules or antecedents needed
to adequately learn the true concept.
%The reason for this behavior results from the fact that \kbann\ is unable to
%modify its topology; thus, if many rules are missing, \kbann\ has to compress
%all required rules into few hidden nodes, perhaps beyond its capacity.
{\it An ideal connectionist theory-refinement
algorithm, therefore, should be able to dynamically expand the
topology of its network during training.}

\subsection{The TopGen Algorithm}

TopGen \cite{opitz.kbsys95} addresses \kbann's limitation by heuristically 
searching through the space of possible expansions to a
knowledge-based neural network  -- a network whose topology 
is determined by the direct mapping of the dependencies of a domain theory
(\eg a \kbann\ network).
TopGen proceeds by first training the \kbann\ network, then placing it on
a search queue.  In each cycle, TopGen takes the best network from
the search queue, estimates where errors occur in the network, adds
new nodes in response to these estimates, trains these
new networks, then places them back on the queue.
TopGen judges where errors occur in a network by 
using training examples to increment two counters for
each node, one for false negatives and one for false positives.

Figure~\ref{topgen.additions} illustrates the possible ways TopGen can add
nodes to one of its networks.
In a symbolic rule base that uses negation-by-failure,
%\cite[Chapter 5]{rich.book83}.
one can decrease false negatives by either dropping
antecedents from existing rules or adding new rules to the rule base.
\kbann\ is effective at removing antecedents from existing rules, 
but is unable to add new rules; therefore,
TopGen adds nodes, intended for decreasing false negatives,
in a fashion that is analogous to adding a new rule to the rule base.
If the existing node is an {\sc or} node, TopGen adds a new node as its child
(see Figure~\ref{topgen.additions}a), and fully connects this new node to the
input nodes.  When the existing node is an {\sc and} node,
TopGen creates a new {\sc or} node that is the
parent of the original {\sc and} node and another new node that TopGen
fully connects to the inputs (see Figure~\ref{topgen.additions}c);
TopGen moves the outgoing links of the original node (A in
Figure~\ref{topgen.additions}c) to become the outgoing links of the new {\sc or}
 node.
 
\begin{figure}
\centerline{\psfig{figure=idraw.possible.adds,width=\textwidth}}
\caption[TopGen's method for adding new nodes to a KNN.]
{Possible ways to add new nodes to a knowledge-based neural network
(arcs indicate AND nodes).
{\rm To decrease false negatives, we wish to broaden the applicability of the
node.  Conversely, to decrease false positives, we wish to further
constrain the node.}}
\label{topgen.additions}
%\rule{\textwidth}{0.5pt}
\end{figure}
 
In a symbolic rule base, one can decrease false positives by either adding
antecedents to existing rules or removing rules from the rule base.
\kbann\ can effectively remove rules, but it
is less effective at adding antecedents to rules and is unable to invent
(\ie constructively induce; Michalski, 1983)  \nocite{michalski.aij83}
new terms as antecedents.  Thus TopGen adds
new nodes, intended to decrease false positives, in a fashion that is
analogous to adding new constructively induced antecedents to the network.
Figures~\ref{topgen.additions}b and~\ref{topgen.additions}d illustrates
how this is done (analogous to Figures~\ref{topgen.additions}a
and~\ref{topgen.additions}c explained above).
Refer to Opitz and Shavlik (1993; 1995) for more details.
%or Opitz and Shavlik \citeyear{opitz.kbsys95} for more details.

\topgen\ showed statistically significant improvements over \kbann\
in several real-world domains, and comparative experiments
with a simpler approach to adding nodes verified that new nodes must be added
in an intelligent manner \cite{opitz.kbsys95}.
In this article, however, we increase the number of networks \topgen\
considers during its search and show that the increase
in generalization is primarily limited to the first few networks considered.
Therefore, \topgen\ is not so much an ``anytime'' algorithm, but rather
is a first step towards one.
This is mostly due to the fact that \topgen\ only considers
larger networks that contain the original \kbann\ network as subgraphs;
however, as one increases the number of networks considered, one should
also increase the variety of networks considered during the search.
{\it Broadening the range of networks considered during the search through
topology space is the major focus of this paper.}

\section{The REGENT Algorithm}
\label{chapter.regent.algo}

Our new algorithm, \regent, tries to broaden the types of networks 
that \topgen\ considers with the use of GAs.
We view \regent\ as having two phases: {\mbox (a) genetically} searching 
through topology space, and {\mbox (b) training} each network using
backpropagation's gradient descent method.
\regent\ uses the domain theory to aid in both phases.
It uses the theory to help guide its search through topology space and to
give a good starting point in weight space.

Table 1 summarizes the \regent\ algorithm.
\regent\ first sets aside a {\it validation} set (from part of the
{\it training} instances) for use in scoring the different networks.
It then perturbs the \kbann-produced network to create an initial set of   
candidate networks.  Next, \regent\ trains these networks using
backpropagation and places them into the population.
In each cycle, \regent\ creates new networks by crossing over
and mutating networks from the current population that are
randomly picked proportional to their fitness (\ie validation-set correctness).
It then trains these new networks and places them into the population.
As it searches, \regent\ keeps the network that has the lowest
validation-set error as the best concept seen so far, breaking ties
by choosing the smaller network in an application of Occam's Razor.
A parallel version of \regent\ trains many candidate networks at the same time
using the Condor system 
\cite{litzkow.icdcs88}, which runs jobs on idle workstations.
\input{regent.table}

A diverse initial population will broaden the types of networks
\regent\ considers during its search; however, since the domain theory may
provide useful information that may not be present in the training set, it is
still desirable to use this theory when generating the initial population.
\regent\ creates diversity around the domain theory by randomly perturbing
the \kbann\ network at various nodes.
\regent\ perturbs a node by either deleting it, or by
adding new nodes to it in a manner analogous to one of \topgen's four methods
for adding nodes.
(Should there happen to be multiple theories about a domain, all of them can
be used to seed the population.)

\subsection{REGENT's Crossover Operator}

\regent\ crosses over two networks by first dividing the nodes in each parent
network into two sets, \seta\ and \setb,
then combining the nodes in each set 
to form two new networks (\ie the nodes in the two \seta\ sets form 
one network, while the nodes in the two \setb\ sets form another).
Table 2 summarizes \regent's method for crossover and 
Figure~\ref{crossover.fig} illustrates it with an example.
\regent\ divides nodes, one level\footnote{
Although one can define {\it level} several different ways, we define
a node's {\it level} as the longest path from it to an output node.}
at a time, starting at the level nearest the output nodes.
When considering a level, if either set \seta\ or set \setb\
is empty, it cycles through each node in that level and randomly assigns it
to either set.
If neither set is empty, nodes are probabilistically placed into a set. 
\input{crossover.table}
\begin{figure}[t]
\centerline{\psfig{figure=idraw.crossover,width=\textwidth}}
\caption[Example of \regent's crossover.]
{REGENT's method for crossing over two networks.  {\rm The hidden nodes
in each original network
are divided into the sets \seta\ and \setb; the nodes in the two \seta\ 
sets form one new network, while the nodes in the two \setb\ sets form 
another.  Grey lines represent low-weighted links that
are added to fully connect neighboring levels.}}
\label{crossover.fig}
\rule{\textwidth}{0.5pt}
\end{figure}
The following equation calculates the probability of a given node being 
assigned to set \seta:
\begin{equation}
\label{crossover.prob.eq}
Prob(node \ i \in set A) = \frac{\sum_{j\in A}\left|{w_{ji}}\right|}
                       {\sum_{j\in A}\left|{w_{ji}}\right| +
                        \sum_{j\in B}\left|{w_{ji}}\right|},
\end{equation}
where $j \in A$ means node $j$ is a member of set $A$ and 
$w_{ji}$ is the weight value from node $i$ to node $j$.  
The probability of belonging to set \setb\ is one minus this probability.
With these probabilities, \regent\ tends to assign to the same set those
nodes that are heavily linked together.
This helps to minimize the destruction of the rule structure of the 
crossed-over networks, since nodes belonging to the same syntactic rule
are connected by heavily linked weights.
Thus, \regent's crossover operator produces new networks by
crossing-over rules, rather than simply crossing-over nodes.

\regent\ must next decide how to connect the nodes of the newly created
networks.  
First, a new network inherits all weight values from its parents on links that
(a) connect two nodes that are both inherited by the new network,
(b) connect an inherited hidden node and an input or output node, or
(c) directly connect an input node to an output node.
%connect two nodes that either it inherited, or are input or output nodes.
It then adds randomly set, low-weighted links between unconnected nodes
on consecutive levels.

Finally, it adjusts the bias of all \myand\ or \myor\ nodes to help
maintain their {\it original} function.
For instance, if \regent\ removes a positively weighted incoming link for 
an \myand\ 
node, it decrements the node's bias by subtracting the product of the link's 
magnitude and the average activation (over the set of training examples)
entering that link.  We do this because the bias for an \myand\ node needs to be
slightly less than the sum of the {\it positive} weights 
on the incoming links (see Towell and Shavlik, 1994 for more details).
\regent\ increments the bias for an \myor\ node by an analogous amount when 
it removes negatively weighted incoming links (since the bias for an \myor\
node should be slightly greater than the sum of the {\it negative} weights 
on the incoming links so that the node is inactive only when all
incoming negatively weighted linked nodes are active and all
positively weighted linked nodes are inactive). 

\subsection{REGENT's Mutation Operator}

\regent\ mutates networks by applying a variant of \topgen.
\regent\ uses \topgen's method for incrementing the false-negatives and
false-positives counters for each node.
\regent\ then adds nodes, based on the values of these counters,
the same way \topgen\ does.  
Since neural learning is effective at removing unwanted antecedents and rules
from KNNs (see Section~\ref{section.kbann}), \regent\ only
considers adding nodes, and not deleting them, during mutation.  
Thus,
this mutation operator adds diversity to a population, while still maintaining 
a directed, heuristic-search technique for choosing where to add nodes;
this directedness is necessary because we currently are unable to
evaluate more than a few thousand possible networks per day.

\subsection{Additional Details}

\regent\ adds newly trained networks to the population only if their
{\mbox validation-}set correctness is better than or equal to an existing member
of the population.
When \regent\ replaces a member, it replaces the member having the lowest 
correctness (ties are broken by choosing the oldest member). 
Other techniques \cite{goldberg.book89}, such as replacing the
member nearest the new candidate network, can promote diverse populations;
however, we do not want to promote diversity at the expense of decreased
generalization.
As a future research topic,
we plan to investigate incorporating diversity-promoting techniques
once we are able to consider tens of thousands of networks.

\regent\ can be considered a Lamarckian\footnote{
Lamarckian evolution is a theory based on the inheritance of characteristics
acquired during a lifetime.},
genetic-hillclimbing algorithm \cite{ackley.book87}, since it 
performs local optimizations on individuals, then passes the successful
optimizations on to offspring.
The ability of individuals to learn can smooth the fitness landscape
and facilitate subsequent learning.
% \cite{hinton.complexsys87}.
Thus, Lamarckian learning can lead to a large increase in learning speed and
solution quality \cite{ackley.alife3,farmer.alife2}.
\section{Related Work}

\regent\ mainly differs from previous work
in that it is an``anytime'' theory-refinement system that continually searches,
in a non-hillclimbing manner, for improvements to the domain theory.
In summary, our work is unique in that it provides a connectionist approach 
that attempts to effectively utilize available background knowledge and
available computer cycles to generate the best concept possible.
We have broken the rest of this section into four parts:
(a) connectionist theory-refinement algorithms, 
(b) purely symbolic theory-refinement algorithms, (c) algorithms that find 
an appropriate domain-specific neural-network topology, and
(d) optimization algorithms wrapped around induction algorithms.

\subsection{Connectionist Theory-Refinement Techniques}

We begin our discussion with connectionist theory-refinement systems.
These systems have been developed to refine many types of rule bases.  
For instance, a number of systems have been proposed for revising 
certainty-factor
rule bases \cite{fu.consci89,lacher.nn92,mahoney.consci93}, finite-state
automata \cite{maclin.mlj93,omlin.mlc92}, push-down automata \cite{das.nips5},
fuzzy-logic rules \cite{berenji.mlc91,masuoka.fuzzy90}, and mathematical
equations \cite{roscheisen.nips4,scott.nc92}.
Most of these systems work like \kbann\ by first translating the domain 
knowledge into a neural network, then modifying the weights of this 
resulting network.
Few attempts (which we describe next) have been made to dynamically
adjust the resulting network's topology during training
(as \regent\ does).

Like both TopGen and \regent, Fletcher and Obradovic 
\citeyear{fletcher.consci93} present an approach
that adds nodes to a \kbann\ network.  Their system constructs a
single layer of nodes, fully connected between the input and output nodes,
``off to the side'' of the \kbann\ network.
They generate new hidden nodes using a variant of Baum and Lang's
\citeyear{baum.nips3} constructive algorithm.  Baum and Lang's
algorithm first divides the feature space with hyperplanes.
They find each hyperplane by randomly selecting two points from different
classes, then localizing a suitable split between these points.
Baum and Lang repeat this process until they generate a fixed number 
of hyperplanes.
Fletcher and Obradovic then map each of Baum and Lang's hyperplanes 
into one new hidden node, thus
defining the weights between the input layer and that hidden node.
Fletcher and Obradovic's algorithm does not change the weights of the \kbann\ 
portion of the network, so modifications to the initial rule base
are solely left to the constructed hidden nodes.
Thus, their system does not take advantage of \kbann's strength of
removing unwanted antecedents and rules from the original rule base.
In fact, TopGen compared favorably to a similar technique that also added 
nodes off to the side of \kbann\ \cite{opitz.ijcai93} and \regent\
outperformed TopGen in this article's experiments.

{\sc Rapture} \cite{mahoney.mlc94} is designed for domain theories
containing probabilistic rules.
Like most connectionist theory-refinement systems, {\sc Rapture} first
translates the domain theory into a neural network, then refines
the weights of the network with a modified backpropagation algorithm.
Like \regent, {\sc Rapture} is then able to
dynamically refine the topology of its network.
It does this by using the {\sc Upstart} algorithm \cite{frean.nc90} to add new
nodes to the network.
Aside from being designed for probabilistic rules, {\sc Rapture} differs
from \regent\ in that it adds nodes with the intention of completely
learning the training set, not generalizing well.
Thus, while {\sc Rapture} hillclimbs until the training set is learned,
\regent\ continually searches topology space looking for a network
that minimizes the scoring function's error.
Also, {\sc Rapture} initially only creates links that are specified
in the domain theory, and only explicitly adds links through ID3's
\cite{quinlan.mlj86} information-gain metric.
\regent, on the other hand, fully connect consecutive layers
in their networks, allowing each rule the possibility of adding
antecedents during training.

The {\sc Daid} algorithm \cite{towell.aaai92} is an extension to \kbann\
that uses the domain theory to help {\it train} the \kbann\ network.
Since \kbann\ is more effective at dropping antecedents than adding them,
{\sc Daid} tries to find potentially
useful inputs features not mentioned in the domain theory.
It does this by backing-up errors to the lowest level of the
domain theory, then computing correlations with the features.
{\sc Daid} then increases the weight of the links from the potentially
useful input features based on these correlations.
{\sc Daid} mainly differs from \regent\ in that it does not refine the
topology of the \kbann\ network.
Thus, while {\sc Daid} addresses \kbann's limitation of not
effectively adding antecedents, it is still unable to introduce new rules or
constructively induce new antecedents.
{\sc Daid} will therefore suffer with impoverished domain theories.
Also notice that since {\sc Daid} is an improvement for training KNNs,
\regent\ can use {\sc Daid} to train each network it considers during
its search (however, we have not done so).

Opitz and Shavlik \citeyear{opitz.consci96} used a variant of \regent\ as their
learning algorithm when generating a neural network ``ensemble.''
A neural-network ensemble is a very successful technique where the outputs
of a set of separately trained neural networks are combined to form one unified
prediction
\cite{drucker.mlc94,hansen.ieeetpami90,perrone.thesis}.
Since \regent\ considers many networks, it can select a subset of the
final population of networks as an ensemble at minimal extra cost.
Previous work, though, has shown that an ideal ensemble is one where
the networks are both accurate and make their errors on
different parts of the input space \cite{hansen.ieeetpami90,krogh.nips7}.
As a result, Opitz and Shavlik \citeyear{opitz.consci96} changed the
scoring function of \regent\ so that a ``fit'' network was now one that was
both accurate and disagreed with the other members of the population as much
as possible.
In addition, their algorithm (\addemup) actively tries to generate good 
candidates by emphasizing the
current population's erroneous examples during backpropagation training.
As a result of these alterations, \addemup\ is able to create enough diversity
among the population of networks to be able to effectively exploit the
knowledge of the domain theory.
Opitz and Shavlik \citeyear{opitz.consci96} show that \addemup\ is able
to generate a significantly better ensemble using the domain theory than
either running \addemup\ without the benefit of the theory or simply
combining \regent's final population of networks.
Actively searching for a highly diverse population, however, does not
aid in searching for the single best network.
In fact, the single best network produced by \addemup\ is significantly
worse than \regent's single best network on all three domains.

\subsection{Purely Symbolic Theory-Refinement Techniques}

Additional work related to \regent\ includes purely symbolic theory-refinement 
systems that modify the domain theory directly in its initial form.
Systems such as {\sc Focl} \cite{pazzani.mlj92}
and {\sc Forte} \cite{richards.mlj95}
are first-order, theory-refinement systems that revise predicate-logic theories.
One drawback to these systems is that they currently do not
generalize as well as connectionist approaches
on many real-world problems, such as the DNA promoter task \cite{cohen.mlc92}.

There have been several genetic-based, first-order logic, multimodal 
concept learners \cite{greene.ml93,janikow.ml93}.
Giordana and Saitta \citeyear{giordana.msl93} showed how to integrate
one of these system, {\sc Regal} \cite{giordana.mlc94,neri.pami96},
with the deductive engine of ML-SMART \cite{bergadano.mlc89}
to help refine an incomplete or inconsistent domain theory.
This version works by first using an automated theorem prover to recognize
unresolved literals in a proof, then uses the GA-based {\sc Regal} to induce 
corrections to these literals.
\regent, on the other hand, use genetic algorithms (along with neural 
learning) to refine the {\it whole} domain theory at the same time.

{\sc Dogma} \cite{hekanaho.mlc96} is a recently proposed
GA-based learner that can use background knowledge to learn
the same description language as {\sc Regal}.
Current restrictions, however, force the 
representation language of the domain theory to be propositional rules.
{{\sc Dogma} converts a ``flat'' set of background rules
(\ie it does not handle intermediate conclusions) into individual bitstrings
that are used as building blocks for a higher-level concept.
{\sc Dogma} does not focus on theory refinement, rather it
builds a completely new theory using substructures from the 
background knowledge.
They term their approach as being more theory-suggested than theory-guided
\cite{hekanaho.mlc96}.


Several systems, including ours, have been proposed for refining
{\it propositional} rule bases.
Early such approaches could only handle
improvements to overly specific theories \cite{danyluk.mlc89}
or specializations to overly general theories \cite{flann.mlj89}.
Later systems such as {\sc Rtls} \cite{ginsberg.aaai90}, 
{\sc Either} \cite{ourston.aij94}, {\sc Ptr} \cite{koppel.jair94}, 
and {\sc Tgci} \cite{donoho.jair95} were later able to handle both types 
of refinements.
We discuss the {\sc Either} system as a representative of these
propositional systems.

{\sc Either} has four theory-revision operators: (a) removing antecedents
from a rule, (b) adding antecedents to a rule, (c) removing rules
from the rule base, and (d) inventing new rules.
{\sc Either} uses these operators to make revisions to the domain theory 
that correctly classify some of the previously misclassified training examples 
without undefining any of the correctly classified examples.
{\sc Either} uses inductive learning algorithms to invent new rules;
it currently uses ID3 \cite{quinlan.mlj86} as its induction component.

Even though \regent's mutation operator add nodes in a manner analogous 
to how a symbolic system adds antecedents and rules, its underlying 
learning algorithm is ``connectionist.''
Towell \citeyear{towell.thesis} showed that \kbann\ outperformed
{\sc Either} on the promoter task, and \regent\ outperformed \kbann\
in this article.
\kbann's power on this domain is largely attributed to its ability to make
``fine-grain'' refinements to the domain theory \cite{towell.thesis}.
Because of {\sc Either}'s difficulty on this domain, 
Baffes and Mooney \citeyear{baffes.ijcai93}
presented an extension to it called {\sc Neither-MofN}
that is able to learn $M$-of-$N$ rules -- rules that are true if $M$ of the
$N$ antecedents are true.  This improvement generated a concept
that more closely matches \kbann's generalization performance.

While we want to minimize changes to a theory, we do not want to
do it at the expense of accuracy; however,
Donoho and Rendell \citeyear{donoho.jair95} demonstrate that most
existing theory-refinement systems, such as {\sc Either}, suffer
in that they are only able to make small, local changes to
the domain theory.
Thus, when an accurate theory is significantly far in structure
from the initial theory, these systems are forced to either
become trapped in a local maximum similar to the initial theory,
or are forced to drop entire rules and replace them with new rules
that are inductively created purely from scratch.
\regent\ does not suffer from this in that it translates the
theory into the less restricting representation of neural networks
\cite{donoho.jair95}.  Also, \regent\ is able to further
reconfigure the structure of the domain with genetic algorithms.

Many authors have reported results using varying subsets of the 
splice junction domain 
(\eg Donoho and Rendell 1995; Mahoney 1996;
Neri and Saitta 1996, and Towell and Shavlik 1994).
\nocite{donoho.jair95,mahoney.thesis,neri.pami96,towell.aij94}
While these authors used different training set sizes, it is
nevertheless worthwhile to qualitatively discuss some of their conclusions here.
Towell and Shavlik \citeyear{towell.aij94} compared \kbann\ with numerous
machine learning algorithms where each learning algorithm was
given a training set of 1000 examples; \kbann's generalization ability
compared favorably with these algorithms on the splice domain and 
\regent, in turn, compared favorably with \kbann\ in this article.
Donoho and Rendell \citeyear{donoho.jair95} showed their 
purely symbolic approach converged to the performance of \kbann\
at around 200 examples. 
Mahoney \citeyear{mahoney.thesis} showed, using training set
sizes of up to 400 examples, that his {\sc Rapture} algorithm
generalized better than \kbann\ on this domain;
his results look similar to those of \regent.
Finally, Neri and Saitta \citeyear{neri.pami96} showed that the generalization
ability of the GA-based {\sc Regal} compares favorably to other
purely symbolic, non-GA based techniques; while they used slightly different
training set sizes than we did in this article, \regent\ compares well 
to the results reported in their paper.

\subsection{Finding Appropriate Network Topologies}
\label{section.gann}

Our third area of related work covers techniques that attempt to find
a good domain-dependent topology by dynamically refining their network's
topology during training.
Many studies have shown that the generalization ability of a neural
network depends on the topology of the network \cite{baum.nc89,tishby.ijcnn89}.
When trying to find an appropriate topology, 
one approach is to construct or modify a topology in an
incremental fashion.  
{\it Network-shrinking} algorithms
start with too many parameters, then remove nodes and weights during training
\cite{hassibi.nips5,lecun.nips2b,mozer.consci89}.
{\it Network-growing} algorithms, on the other hand,
start with too few parameters, then add more nodes and weights during training
\cite{blanzieri.mlc96,fahlman.nips2,frean.nc90}.
The most obvious difference between \regent\ and these algorithms is that
\regent\ uses domain knowledge and symbolic rule-refinement techniques 
to help determine the network's topology.
Also, these other algorithms restructure their network based solely on 
training-set error, while \regent\ minimized validation-set error.

Instead of incrementally finding an appropriate topology, one can mount 
a ``richer'' search than hillclimbing through the space of topologies.
One common approach is to combine genetic algorithms
and neural networks (as \regent\ does).
Genetic algorithms have been applied to neural networks in two different ways:
(a) to optimize the connection weights in a fixed topology, and
(b) to optimize the topology of the network.
Techniques that solely use genetic algorithms to optimize weights
\cite{montana.ijcai89,whitley.icga89} have performed competitively
with gradient-based training algorithms;
however, one problem with genetic algorithms is their inefficiency in
fine-tuned local search, thus the scalability of these
methods are in question \cite{yao.ijns93}.
Kitano \citeyear{kitano.aaai90} presents a method that combines genetic 
algorithms with backpropagation.  He does this by using the genetic 
algorithm to determine the starting weights for a network, which are then
refined by backpropagation.
\regent\ differs from Kitano's method in that we use a 
domain theory to help determine each network's starting weights
and genetically search, instead, for appropriate network topologies.

Most methods that use genetic algorithms to optimize a network topology
are similar to \regent\ in that they also
use backpropagation to train each network's weights.
Of these methods, many directly encode each link in the network
\cite{miller.icga89,oliker.complexsys92,schiffmann.tr92}.
These methods are relatively straightforward to implement, and are good
at fine tuning small networks \cite{miller.icga89}; however, they do
not scale well since they require very large matrices to represent
all the links in large networks \cite{yao.ijns93}.
Other techniques \cite{dodd.icnn90,harp.nips2,kitano.complexsys90}
only encode the most important features of the network, such as
the number of hidden layers, the number of hidden nodes at each layer, etc.
These indirect encoding schemes can evolve different sets of parameters
along with the network's topology and have been shown to have good
scalability \cite{yao.ijns93}.
Some techniques \cite{koza.ijcnn91,oliker.complexsys92} evolve both
the architecture and connection weights at the same time; however, the
combination of the two levels of evolution greatly increases the search space.

\regent\ mainly differs from genetic-algorithm-based training methods in 
that it is designed for {\it knowledge-based} neural networks.  
Thus \regent\ uses domain-specific knowledge and symbolic rule-refinement
techniques to aid in determining the network's topology and initial weight
setting.
\regent\ also differs in that it does not explicitly encode its networks;
rather, in the spirit of Lamarkian evolution,
it passes {\it trained} network weights to the offspring.
A final difference is that most of these other algorithms restructure their
network based solely on training-set error, while \regent\ minimizes
validation-set error.

\subsection{Wrapping Optimization Around Learning}

We end our related work discussion with a brief overview of methods that 
combine global and local optimization strategies.
Local search algorithms iteratively improve their estimate of the 
minimum by searching in only a local neighborhood of the current solution; 
local minima are not guaranteed to be global minima.
(Many inductive learning methods are often equated with
local optimization techniques; Rumelhart et al., 1986.)
Global optimization methods (such as GAs), on the other hand, perform a more 
sophisticated search across multiple local minima and are good at finding 
regions of the search space where near-optimal solutions can be found; however, 
they are usually not as good at refining a solution (once it is close to a
near-optimal solution) as local optimization strategies
\cite{hart.thesis}.
Recent research has shown that it is desirable to emply both
a global and local search strategy \cite{hart.thesis}.

Hybrid GAs (such as \regent) combine local search with a more
traditional GA.
While we focus on hybrid-GA algorithms in this section, this
two-tiered search strategy has been employed by other researchers as well
\cite{kohavi.aij97,provost.ml95,schaffer.ml93}.
GAs have been combined with many local search methods 
\cite{bala.ijcai95,belew.complexsys90,hinton.complexsys87,turney.jair95}.
Neural networks are the most common choice for the 
local search strategy of hybrid GA systems and
we discussed GA/neural-network hybrids in the Section~\ref{section.gann}.
There are two common forms of hybrid GAs: Lamarckian-based evolution and
Darwinian-based evolution (the Baldwin effect).
Lamarckian evolution encodes its local improvements directly into its
genetic material, while Darwinian evolution leaves the genetic
material unchanged after learning.
As discussed in Section~\ref{section.discuss},
most authors use Lamarckian local search techniques and 
many have shown numerous cases where Lamarckian evolution
outperforms non-Lamarckian local search 
\cite{belew.alife2,hart.thesis,judson.ijqc92}.

%With the Baldwin effect, the improvements from the local search
%do not change the genetic makeup of the individual.
%The Baldwin effect has gotten a lot of recent attention
%\cite{bala.evcomp96,belew.book96,harvey.evcomp96,turney.evcomp96}
%and in some cases can be more effective than Lamarckian approaches
%\cite{whitley.evcomp93}.
%\regent\ currently uses Lamarckian evolution; however, as indicated
%earlier, we also plan to test a Darwinian-based approach.

\section{Experimental Results}
\label{section.results}

In this section, we test \regent\ on three real-world Human Genome Project 
problems that aid in locating genes in DNA sequences
(recognizing {\it promoters}, {\it splice-junctions}, and
{\it ribosome-binding sites}).
In these domains, the input is a short segment of DNA
nucleotides (about 100 elements long) and the task is learn to predict
if this DNA subsequence contains a biologically important site.
Each domain is also accompanied by a domain theory generated by
a DNA expert (M. Noordewier).

The promoter domain contains 234 positive
examples, 702 negative examples, and 31 rules.
The splice-junction domain contains 1,200 examples
distributed equally among three classes, and 23 rules.
Finally, the ribosome binding sites (RBS) domain, contains 366 positive
examples, 1,098 negative examples, and 17 rules.
(Note that the promoter data set and domain theory is a later version of the
one that appears in Towell, 1994.)
These domains are available at the University of Wisconsin Machine
Learning (UW-ML) site via the World Wide Web
{\tt (ftp://ftp.cs.wisc.edu/machine-learning/shavlik-group/datasets/)}
or anonymous ftp ({\tt ftp.cs.wisc.edu}, then 
{\tt machine-learning/shavlik-group/datasets}).

We first directly compare \regent\ with TopGen and \kbann.
We then perform a lesion study\footnote{
%{\renewcommand{\baselinestretch}{1}
A {\it lesion study} is one where components of an algorithm are individually
disabled to ascertain their contribution to the full algorithm's performance
\cite{kibler.ewsl88}.}
on \regent.  In particular, we investigate the value of
adding randomly created networks to \regent's initial population and
examine the utility of \regent's genetic operators.

\subsection{Experimental Methodology}

All results in this article are from ten-fold cross validation runs.
For each ten-fold cross validation the data set is first partitioned into
ten equal-sized sets, then each set is in turn used as the test set while
the classifier trains on the other nine sets.
In each fold, \regent\ is run with a population size of 20.
Each network is trained using backpropagation.
Parameter settings for the neural networks include a learning rate of 0.10,
a momentum term of 0.9, and the number of training epochs of 20;
the first two are standard settings and while 20 epochs may be
fewer than typically found in the neural network literature, we set
it at 20 to help avoid overfitting.
We set aside a validation set consisting of 10\% of the training examples
for \regent\ to use as its scoring function.

\subsection{Generalization Ability of REGENT}

This section's experiments compare the test-set accuracy (\ie generalization)
of \regent\ with \topgen's.
Figure~\ref{regent.dna.plot} shows the test-set error of \kbann, \topgen,
and \regent\ as they search through the space of network topologies.
\begin{figure}
\centerline{\psfig{figure=idraw.regent.dna.plot,width=\textwidth}}
\caption[\regent's test-set error on the DNA problems.]
{Error rates on the three Human Genome problems.}
\label{regent.dna.plot}

\vspace*{0.25in}
\end{figure}
The horizontal line in each graph results from the \kbann\ algorithm.
We drew a horizontal line for the sake of visual comparison;
recall that \kbann\ only considers a single network.
The first point of each graph, after one network is considered, is nearly 
the same for all three algorithms, since they all start with the \kbann\
network; however, \topgen\ and \regent\ differ slightly from \kbann\ since
they must set aside part of the training set to score their candidate networks.
Notice that \topgen\ stops improving after considering 10 to 30 networks and
that the generalization ability of \regent\ is better than \topgen's after
this point.  The reason for the occasional upward movements in 
Figure~\ref{regent.dna.plot} is due to the fact that a validation
set (or any scoring function) is an inexact estimate of the true generalization 
error (as are the results of the ten-fold cross validation).

Figure~\ref{regent.dna.bar} presents the test-set error of \topgen\ and
\regent\ after they each consider 500 candidate topologies.
\begin{figure}[b]
%\rule{\textwidth}{0.5pt}
%\vspace*{0.2in}
\centerline{\psfig{figure=idraw.regent.dna.bar,height=2.3in}}
\caption[\regent's test-set error on DNA problems - final results.]
{Test-set error rates after TopGen and REGENT each consider 500 networks.
{\rm Pairwise, one-tailed {\it t}-tests indicate that \regent\ differs from 
Standard NN, \kbann, and TopGen at the 95\% confidence level on all three 
problems.}}

\vspace*{0.05in}
\label{regent.dna.bar}
%\rule{\textwidth}{0.5pt}
\end{figure}
The standard neural network results are from a fully connected, single-layer,
feed-forward neural network; for each fold, we trained 20
networks containing up to 100 hidden nodes and used a validation set
to choose the best network.  
Our results show \kbann\ generalizes much better than the best of these
standard networks, thus further confirming \kbann's effectiveness
in generating good network topologies.
While \topgen\ is able to improve on the \kbann\ network, \regent\ is
able to significantly decrease the error rate over both \kbann\ and \topgen.
(For benchmark purposes, \regent\ has an error rate of 3.9\% from a
ten-fold cross validation on the full Splice Junction dataset of 
3190 examples commonly used by machine learning researchers.)

Table 3 contains the number of hidden nodes in the final 
networks produced by \kbann, TopGen, and \regent.
The results demonstrate that \regent\ produces networks that are 
larger than both \kbann's and TopGen's networks (even though TopGen
only {\it adds} nodes during its search).
While \regent's networks are larger, it does not necessarily 
mean that they are more ``complex.''
We inspected sample networks and found that there are large portions
of the network that are either not used (\eg their weights are insignificantly
small) or are functional duplications of other groups of hidden nodes.

\begin{table}
{\renewcommand{\baselinestretch}{1}
\small\normalsize
\begin{center}

\vspace*{0.15in}
\begin{tabular}{|c|c|c|c|} \hline
\rule{0in}{0.12in} Domain  & \kbann & \topgen & \regent \\ \hline
\rule{0in}{0.125in} RBS & 18 & 42.1~~(9.3) & 70.1~~(25.1) \\
Splice Junction & 21 & 28.4~~(4.1) & 32.4~~(12.2) \\
Promoters       & 31 & 40.2~~(3.3) & 74.9~~(38.9) \\ \hline
\end{tabular}
\end{center}

\caption[Size of network generated by \regent.]
{Number of hidden nodes in the networks produced by KBANN, TopGen, and REGENT.
{\rm The columns show the mean number of hidden nodes found
within these networks.
Standard deviations are contained within parentheses; we do not report
standard deviations for \kbann\ since it uses only one network. }}
\rule{\textwidth}{0.5pt}
}
\end{table}

One could prune weights and nodes during \regent's search; however,
such pruning can prematurely reduce the variety of structures
available for recombination during crossover \cite{koza.book92}.
Real-life organisms, for instance, have superfluous DNA
that are believed to enhance the rate of evolution 
\cite{watson.book87}.
However, while pruning network size {\it during} genetic search may be unwise,
one could prune \regent's final network using, say,
Hassibi and Stork's \citeyear{hassibi.nips5}
Optimal Brain Surgeon algorithm.
This post-pruning process may increase the future classification speed of the 
network, as well as increase its comprehensibility and possibly
its accuracy.

\subsection{Lesion Study of REGENT}

In this section, we describe a lesion study we performed on \regent.
Since a single run of \regent\ takes about four CPU days to consider 500 
networks, a single ten-fold cross validation takes (a minimum of)
40 CPU days.
Therefore, given the inherent similarity of investigating various aspects
of \regent\ over multiple datasets, it is not feasible to run all experiments
in this section until a 95\% confidence level is reached in all cases
(assuming that such a level actually exists).
Nonetheless, these results convey important information about
various components of \regent, and, as shown in the previous section,
the complete \regent\ algorithm does generate statistically significant 
improvements over existing algorithms.

\subsubsection{Including Non-KNNs in REGENT's Population}
\label{regent.init.res}
 
The correct theory may be quite different from the initial domain theory.
Thus, in this section 
we investigate whether one should include, in the initial population of 
networks, a variety of networks not obtained directly from the domain theory.
Currently, \regent\ creates its initial population by always perturbing the
\kbann\ network.
To include networks that are not obtained from the domain theory, we 
first randomly pick the number of hidden nodes to include in a network, then 
randomly create {\it all} of the hidden nodes in this network.
We do this by adding new nodes to a randomly selected output or hidden node
using one of \topgen's four methods for adding new nodes
(refer to Figure~\ref{topgen.additions}).
Adding nodes in this manner creates random networks whose node
structure is analogous to dependencies found in symbolic rule bases, thus
creating networks suitable for \regent's crossover and mutation operators.

Table 4 shows the test-set error of \regent\
with various percentages of knowledge-based neural networks (KNNs)
present in the initial population.
The first row contains the results of initializing \regent\ with
a purely random initial population (\ie the population contains no KNNs).
The second row lists the results when \regent\ creates half its
population with the domain theory, and the other half randomly.
Finally, the last row contains the results of seeding the entire population
with the domain theory.
\begin{table}[t]
%\rule{\textwidth}{0.5pt}
{\renewcommand{\baselinestretch}{1} \small\normalsize
\begin{center}

\vspace{0.15in}
\begin{tabular}{|c|c|c|c|} \hline
\rule{0in}{0.12in} & ~~~~~RBS~~~~~ & Splice Junction & ~~Promoters~~ \\ \hline
\rule{0.0in}{0.1250in}~~~0\% KNN & 9.7\% & 6.3\% & 5.1\%\\ 
~~50\% KNN & 8.6\% & 4.3\% & 4.6\% \\ 
100\% KNN & 8.2\% & 4.1\% & 4.2\% \\ \hline
\end{tabular}
\end{center}
\caption[Adding non-KNNs to \regent's initial population.]
{Test-set error after considering 500 networks.
{\rm Each row gives the pergentage of KNNs present in the initial population.
Pairwise, one-tailed {\it t}-tests indicate that initializing \regent\ 
with 100\% KNNs differs from 0\% KNNs at the 95\% confidence level 
on all three domains; however, the difference between the runs of
50\% and 100\% KNNs is not significant at this level. }}
\rule{\textwidth}{0.5pt}
%\vspace*{-0.125in}
}
\end{table}

These results suggest that including, in the initial 
population, networks that were not created from the domain theory 
increases \regent's test-set error on all three domains.
This occurs because the randomly generated networks are not as correct
as the KNNs, and thus offspring of the original KNN
quickly replace the random networks.
Hence, diversity in the population suffers compared to methods
that start with a whole population of KNNs.
Assuming the domain theory is not ``malicious,''
it is therefore better to seed the entire population from the \kbann\ network.
Should the domain theory indeed be malicious and contain information that
promotes spurious correlations in the data, it would then
be reasonable to randomly create the ``whole'' population.
Running \regent\ both with and without the domain theory 
allows one to investigate the utility of that theory.

These results are also interesting from a GA point of view.
Forrest and Mitchell \citeyear{forrest.mlj93}
showed that GAs perform poorly on complex problems where the
basic {\it building blocks} either (a) are non-trivial to find
or (b) get split during crossover.
Seeding the initial population with a domain theory (as \regent\ does)
can help define the basic building blocks for these problems.

\subsubsection{Value of REGENT's Mutation}

Typically with GAs, mutation is a secondary operation that is only sparingly
used \cite{goldberg.book89}; 
however, \regent's mutation is a directed approach that heuristically
adds nodes to KNNs in a provenly effective manner (\ie it uses \topgen).
It is therefore reasonable to hypothesize that one should apply
the mutation operator more frequently than traditionally done in GAs.
The results in this section test this hypothesis.

Figure~\ref{idraw.dna.mutation} presents the test-set error of
\regent\ with varying percentages of mutation (versus crossover) when
creating new networks in step 3a of Table 1.
\begin{figure}[btp]
\vspace*{-0.2in}
\centerline{\psfig{figure=idraw.dna.mutation,width=\textwidth}}
\vspace*{-0.15in}
\caption[Value of \regent's mutation.]
{Error rates of REGENT with different fractions of mutation
versus crossover after considering 500 networks.
{\rm Arguably due to the inherent similarity of the algorithms, and the limited
number of runs due to their computational complexity,
the results are not significant at the 95\% confidence level.}}
\label{idraw.dna.mutation}

\vspace*{0.25in}
\end{figure}
Each graph plots four curves: (a) 0\% mutation 
(\ie \regent\ only uses crossover),
(b) 10\% mutation, (c) 50\% mutation, and (d) 100\% mutation.
Performing no mutations tests the value of solely using crossover, while
100\% mutation tests the efficacy of the mutation operator by itself.
Note that 100\% mutation is just \topgen\ with a different search strategy;
instead of keeping an OPEN list for heuristic search, a population of KNNs 
are generated
and members of the population are improved proportional to their fitness.
The other two curves (10\% and 50\% mutation) test the synergy between 
the two operators.
Performing 10\% mutation is closer to the traditional GA viewpoint 
that mutation is a secondary operation, while 50\% mutation means that
both operations are equally valuable.
(Previous experiments in this section used 50\% mutation and 50\% crossover.)

While the differences are not all statistically significant, the results 
nevertheless suggest that a synergy exists between the two operations.
Except for the middle portion of the promoter domain, 
the results show that, qualitatively, using both operations at the same time
is better than using either operation alone.
In fact, equally mixing the mutation and crossover operator is better than 
the other three curves on all three domains once \regent\ has
considered 500 networks.
This result is particularly pronounced on the splice-junction domain.

\subsubsection{Value of REGENT's Crossover}

\regent\ tries to cross over the rules in the networks, rather than
just blindly crossing over nodes.  
It does this by probabilistically dividing the nodes in the network 
into two sets where nodes belonging to the same rule tend
to belong to the same set.
In this section, we test the efficacy of \regent's crossover by comparing it to
a variant of itself where it {\it randomly} assigns nodes to two sets
(rather than using {\bf DivideNodes} in Table 2).

Table 5 contains the results of this test after
250 networks were considered.
In the first row, {\tt \regent-random-crossover}, \regent\ randomly breaks
its hidden nodes into two sets, while in the second row,
\regent\ assigns nodes to two sets according to Table 2.
In both cases, \regent\ creates half its networks with its mutation operator,
and the other half with crossover operator.
Although the differences are not statistically significant,
the results suggest that keeping the rule structure of the networks intact
during crossover is important; otherwise, the basic building blocks of
the networks (\ie the rules) get split during crossover, and studies
have shown the importance of keeping intact the basic building blocks
during crossover \cite{forrest.mlj93,goldberg.book89}.
\begin{table}[thb]
{\renewcommand{\baselinestretch}{1}
\small\normalsize
\begin{center}

\vspace{0.15in}
\begin{tabular}{|c|c|c|c|} \hline
\rule{0in}{0.12in}  &   Promoters & Splice Junction &  RBS \\ \hline
\rule{0in}{0.125in} {\tt \regent-random-crossover} & 4.6\% & 4.7\% & 9.1\% \\
{\tt \regent} &  4.4\% & 4.1\% & 8.8\% \\ \hline
\end{tabular}
\end{center}

\caption[Value of \regent's crossover.]
{Test-set error of two runs of REGENT: (a) randomly 
crossing over ``nodes'' in the networks, and (b) one with crossing over
``rules'' in the network (defined by  Equation~\ref{crossover.prob.eq}).
{\rm Both runs considered 250 networks and used half crossover, half mutation.
The results are not significant at the 95\% confidence level;
there is only a slight difference between the learning algorithms and 
the long run-times limited runs to a ten-fold cross validation.}}

\vspace*{-0.125in}}
\end{table}
\begin{table}
%\rule{\textwidth}{0.5pt}
\label{crossover.table}

\small
%\vspace{0.2in}
{\large {\bf Crossover Two Networks:}} \\[0.1in]
{\bf GOAL:} Crossover two networks to generate two new network topologies.
\begin{enumerate}
  \item Divide each network's hidden nodes into sets \seta\ and
        \setb\ using {\bf DivideNodes}.
  \item Set \seta\ forms one network, while set \setb\ forms
	another.  Each new network is created as follows:
  \begin{enumerate}
    \item A network inherits weight $w_{ji}$ from its parent
          if nodes $i$ and $j$ either are also inherited or are
	  input or output nodes.
    \item Link unconnected nodes between levels with near-zero weights.
    \item Adjust node biases to keep original \myand\ or \myor\ function 
of each node (see text for explanation).
  \end{enumerate}
\end{enumerate}
\vspace{0.2in}
{\large {\bf DivideNodes:}} \\[0.1in]
{\bf GOAL:~~} Divide the hidden nodes into sets {\tt A} and {\tt B},
while probabilistically maintaining each \\
\hspace*{0.62in} network's rule structure.
\begin{description}
  \item[] While some hidden node is not assigned to set \seta\ or \setb:
  \begin{description}
    \item[{\bf (i)}~] Collect those unassigned hidden nodes whose output
    is linked only to either previously-assigned nodes or output nodes.
    \item[{\bf (ii)}] {\bf If} set \seta\ or set \setb\ is empty: \\
\hspace*{0.225in} For each node collected in part (i), randomly assign 
it to set \seta\ or set \setb.\\[0.025in]
\vspace*{-0.25in}
    \begin{description}
       \item[Else]  ~~\\ Probabilistically add the nodes collected
in part~(i)~to set \seta\ or set \setb. Equation~\ref{crossover.prob.eq}
shows the probability of being assigned to set \seta.
The probability of being assigned to set \setb\ is one minus this value.
    \end{description}
\end{description}
\end{description}
\normalsize

\vspace*{0.25in}
\caption{REGENT's method for crossing over networks.}

\rule{\textwidth}{0.5pt}
\end{table}
\begin{table}[b]
\rule{\textwidth}{0.5pt}
\label{regent.table}

\small
%\vspace{0.2in}
{\bf GOAL:} Search for the best network topology describing the domain theory
and data.
\begin{enumerate}
  \item Set aside a validation set from the training instances.
  \item Perturb the \kbann-produced network in multiple ways to create 
  initial networks, then train these networks using backpropagation 
  and place them into the population.
  \item Loop forever:
  \begin{enumerate}
    \item Create new networks using the crossover and mutation operators.
    \item Train these networks with backpropagation, score with the validation set, 
    and place into the population.
%\vspace*{-0.05in}
    \item If a new network is the network with the lowest validation-set error 
seen so far (breaking ties by preferring the smallest network), report it as the current best concept.
  \end{enumerate}
\end{enumerate}
\normalsize
\normalsize

\caption{The REGENT algorithm.}

\end{table}


