
\subsection{Feature Subset Selection}

A repeated result in the data mining community is that simpler
models with  equivalent or higher performance can be built via
{\em feature subset selection}, algorithms that intelligently
prune useless features \cite{hall03}. Features may be pruned for
several reasons: 
\begin{itemize}
\item They may be noisy, i.e.\ contain spurious signals unrelated
  to the target class; 
\item They may be uninformative, e.g.\ contain mostly one value,
  or no repeating values;
\item They may be correlated to other variables, in which case
  they can be pruned since their signal is also present in other
  variables.
\end{itemize}

The reduced feature set has many advantages:
\begin{itemize}
\item Miller has shown that models generally containing fewer
  variables have less variance in their outputs \cite{miller02}.
\item The smaller the model, the fewer are the demands on
  interfaces  (sensors and actuators) to the external environment.
  Hence, systems designed around  small models are easier to use
  (less to do) and cheaper to build.
\item In terms of this article, the most important aspect of
  learning from a reduced features set is that it produces
  smaller models. Such smaller models are easier to explain (or audit).
\end{itemize}

The literature lists many feature subset selectors.  
In the Wrapper method, a {\em target learner} is augmented with a
pre-processor that used a heuristic search to grow subsets of the
available features. At each step in the growth, the target learner
is called  to find the accuracy of the model learned from the
current subset. Subset growth is stopped when the addition of new
features did not improve the accuracy. 
Kohavi and John \cite{kohavi97} report experiments with Wrapper
where 83\% (on average) of the measures in a domain could be
ignored with only a minimal loss of accuracy.

The advantage of the Wrapper approach is that, if some target
learner is already implemented, then the Wrapper is simple to
implement. The disadvantage of the wrapper method is that each
step in the heuristic search requires another call to the target
learner. Since there are many steps in such a search ($N$
features have $2^N$ subsets), Wrappers may be too slow.

Another feature subset selector is Relief.  
This is an instance based learning scheme \cite{Kir92,Kon94}
that works by randomly sampling one instance within the data. It
then locates the nearest neighbors for that instance from not
only the same class but the opposite class as well. The values
of the nearest neighbor features are  then compared to that of
the sampled instance and the feature scores are maintained and
updated based on this. This process is specified for some
user-specified $M$ number of instances. Relief can handle noisy
data and other data anomalies by averaging the values for $K$
nearest neighbors of the same and opposite class for each
instance \cite{Kon94}. For data sets with multiple classes, the
nearest neighbors for each class that is different from that of the
current sampled instance are selected and the contributions are 
determined by using the class probabilities of the class in the dataset.

The experiments of Hall and Holmes \cite{hall03} reject numerous
feature subset selection methods.  Wrapper is their preferred
option, but only for small data sets.  For larger data sets, the
stochastic nature of Relief makes it a natural choice.

Another reason to prefer Relief is that it can take advantage
of Nighthawk's stochastic search.  Currently, Relief is a
batch process that is executed after data generation is
completed.  However, it may not be necessary to wait till the end
of data generation to gain insights into which features are most
relevant.  Given the stochastic nature of the algorithm, we can
see feature work where Relief and a genetic algorithm work in
tandem.  Consider the random selection process at the core of
Relief: a genetic algorithm exploring mutations of the current
set of parents is an excellent stochastic source of data.  In
the future, we plan to apply Relief incrementally and in
parallel to our GAs.

\subsection{Data Collection and Analysis}

We instrumented Nighthawk so that every time a chromosome was
evaluated, it printed the current value of every gene and the
final fitness function score.  (For the two BitSet gene types,
we printed only the cardinality of the set.)
For each of the 16 Collection and Map classes from {\tt java.util},
we ran Nighthawk for 40 generations.  Each class therefore
yielded 800 observations, each consisting of a gene value vector
and the chromosome score.

%Relief assumes continuous data and Nighthawk's performance
Relief assumes discrete data and Nighthawk's performance
scores are continuous.  To enable feature subset selection, we
first discretized Nighthawk's output. A repeated pattern
across all our experiments is that the Nighthawk scores fall
into three regions:
\begin{itemize}
\item The 65\% majority of the scores are within 30\% of the top
  score for any experiment. We call this the {\em high plateau}.
\item A 10\%  minority of scores are less than 10\% of the maximum
  score.  We call this region {\em the hole}.
\item After the high plateau there is a  {\em slope} of
  increasing gradient that falls into {\em the hole}. This {\em
  slope} accounds for 25\% of the results.
\end{itemize}
Accordingly, to select our features, we sorted the results and
divided them into three classes: bottom 10\%, next 25\%, remaining
65\%. Relief then found the subset of features that distinguished
these three regions.  

Using the above discretization policy, we ran Relief 10 times in a 10-way
cross-validation study.
The data set was divided
into $10$ buckets. Each bucket was (temporarily) removed and Relief was
run on the remaining data. This produced a list of ``merit'' figures for
each feature (this ``merit'' value is an internal heuristic measure
generated from Relief, and reflects the difference ratio of neighboring
instances that have different regions). We took the maximum merit ($Max$)
and generated a {\it Selected} list. A feature was {\it Selected} if its merit
$m$ was $m> \alpha Max$ (e.g. at $\alpha=0.5$ then we selected all
features that score at least half the maximum merit).

\begin{figure}

\begin{center}
\begin{tabular}{|c|c|}
$\alpha$ & $| {\it Selected} | $\\\hline
0.9 & 39 \\
\hline
0.8 & 62 \\
\hline
0.7 & 112 \\
\hline
0.6 & 217 \\
\hline
0.5 & 439\\
\hline
\end{tabular} \vspace{2mm} \\
\end{center}

\caption{
  Numbers of selected features for values of $\alpha$.
}
\label{selected-features-fig}
\end{figure}

Figure \ref{selected-features-fig} shows the number of features
that were {\it Selected} in
our 19 examples, using different values for $\alpha$. Note that as
$\alpha$ increases, we selected fewer and fewer features.
That is, this method allowed us to discover the genes that were most
important in selecting
for the {\em high plateau} and not the {\em slope} or {\em hole}.

\begin{figure}

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
Gene type & $\alpha=0.9$ & $\alpha=0.5$ & Best avg ranks & Best merit \\
\hline
{\tt candidateBitSet}         & 18 & 106 & 1, 1, 1          & 0.373 \\
\hline
{\tt chanceOfNull}            &  0 &   3 & 24.1, 24.3, 25.4 & 0.166 \\
\hline
{\tt chanceOfTrue}            &  2 &   7 & 1, 3.9, 5.7      & 0.150 \\
\hline
{\tt lowerBound}              &  1 &   9 & 4.1, 5.6, 7.2    & 0.129 \\
\hline
{\tt methodWeight}            &  0 &  11 & 7.5, 7.8, 10.6   & 0.144 \\
\hline
{\tt numberOfCalls}           &  0 &   1 & 7.2, 8.4, 16.7   & 0.195 \\
\hline
{\tt numberOfValuePools}      &  0 &   6 & 14.1, 17.9, 20   & 0.186 \\
\hline
{\tt numberOfValues}          &  0 &  28 & 5.2, 5.2, 7.4    & 0.160 \\
\hline
{\tt upperBound}              &  8 &  16 & 1, 1, 1          & 0.267 \\
\hline
{\tt valuePoolActivityBitSet} & 10 & 252 & 1, 1.4, 2        & 0.267 \\
\hline
\end{tabular}
\end{center}

\caption{
  Merit analysis of Nighthawk gene types.
}
\label{genes-merit-fig}
\end{figure}

Since our goal was to identify gene types that were not useful and
that could therefore possibly be eliminated from chromosomes, we
tabulated the properties of each of the different types of genes.
Figure \ref{genes-merit-fig} shows the result.  The three most
useful types of genes for the software under test were clearly
{\tt candidateBitSet},
{\tt valuePoolActivityBitSet}, and
{\tt upperBound},
since genes of these types sometimes had merit 90\% or more of
the maximum merit, often were ranked first or second in merit,
and were the only gene types such that some genes of that type
had merit greater than $0.2$ on some runs.  This result confirms
our intuition that changing the value reuse policy encoded in
the genes of type 
{\tt candidateBitSet} and
{\tt valuePoolActivityBitSet}
is an important way of improving the performance of a Nighthawk
chromosome.
The good performance of {\tt upperBound} is attributable to the
fact that for all the hash table-related units, adjusting this
parameter caused a ``load factor'' parameter in some of the
constructors to be able to take on values that led to the table
being reallocated frequently.

Just as clearly, the two least useful gene types for the
software under test were
{\tt chanceOfNull} and
{\tt numberOfValuePools}, since neither were ranked better than
than 14th in merit for any run.
This does not indicate that null values and multiple value pools
for each type were not important, only that changing the default
values of these genes (3\% chance of choosing null, and two
value pools) did not usually result in improved performance.

\subsection{Optimization and Performance Comparison}

In order to see whether our analysis was useful, we optimized
the Nighthawk code.
We decided to retain the four gene types with
the highest maximum merit
({\tt candidateBitSet},
{\tt valuePoolActivityBitSet},
{\tt upperBound}, and {\tt numberOfCalls}),
and also two other gene types:
{\tt lowerBound}, because it was paired with 
{\tt upperBound}; and
{\tt numberOfValues}, because it had the highest maximum
merit of the remaining well-ranked gene types.

Accordingly, we adjusted Nighthawk's code to delete all
references to the other four gene types
({\tt chanceOfNull},
{\tt numberOfValuePools},
{\tt chanceOfTrue}, and
{\tt methodWeight}).  We changed the code that depended on the
values stored for such genes in the current chromosome, so that
it instead used the default initial values for those gene types.
 
On each of the 16 Collection and Map classes,
we performed one run of the original Nighthawk,
and one run of the new, optimized version.
For each version of Nighthawk, we then
performed the same analysis that is reflected in Figures
\ref{collection-map-cov} and
\ref{collection-times};
that is, we asked RunChromosome to run 10 test cases with the
winning chromosome and measured the coverage, and we calculated
the clock time taken by Nighthawk to achieve the highest
coverage it achieved.  We then compared the original and
optimized Nighthawk.

The chromosomes resulting from the optimized Nighthawk achieved
slightly higher coverage than those from the original, though a
$t$ test concluded that the difference was not statistically
significant ($p=0.058$).  However, the optimized Nighthawk was
faster to a statistically significant degree ($p=0.010$).  The
time ratio between the original and optimized systems
was 1.46, i.e.\ the
optimized system was 46\% faster.  We can therefore say that
the process of analyzing the usefulness of the genes resulted
in a system that ran substantially more quickly but achieved the
same high coverage of the SUT.

\subsection{Discussion}

The feature subset selection and optimization procedure worked
well for us when we collected data from a set of classes and
then optimized Nighthawk for those classes.  This does not mean
that the optimized Nighthawk would necessarily work
well for other classes.  For instance, for some classes there
might be a great deal of code that is accessible only by giving
null pointers as parameters; we could expect our newly optimized
version of Nighthawk to perform poorly on such classes, since
there would be a fixed 3\% chance of choosing null.

However, the results of the optimization exercise indicate that
FSS-based analysis is a valuable adjunct to the GA in this
application.  It is for this reason that we envision in the
future integrating FSS into a genetic-random testing algorithm,
so that the algorithm can improve its performance dynamically,
while GA mutation and recombination is going on.

