\section{Conclusions}

Requirements tools such as the Defect Detection and Prevention model (used at NASA for early life-cycle discussions), 
contain a
shared
group memory that stores all of the requirements, risks, and mitigations of each member of this group.
Software tools can explore this shared memory to find consequences and interactions that may have been
overlooked.

Studying that group memory is a non-linear optimization task:
possible benefits (like the attainment of requirements) must be traded off against the increased cost of applying various mitigations.
Harman~\cite{harman01} cautions that solutions to non-linear problems 
may be ``brittle.'' That is, small changes to the search results
may dramatically alter the effectiveness of the solution. Hence, when 
reporting an analysis of this
shared group memory, it is vitally important to comment on the robustness of the solution.

Decision ordering diagrams (Sections \ref{sec:dod} and \ref{sec:dodresults}) are one such solution robustness assessment method.
These diagrams
rank all of the possible decisions from most-to-least influential. Each point $x$ on
the diagrams shows the effects on imposing the conjunction of decisions $1 \le j \le x$.
These diagrams can comment on the robustness and neighborhood of
solution $\{d_1.. d_x\}$ using two operators:
\be
\item By considering the variance of the performance statistics after applying $\{d_1 .. d_x\}$.
\item By comparing the results of using the first $x$ decisions to that of using the first $x-1$ or $x+1$ actions.
\ee
Since the decisions are sorted by importance, this analysis of robustness and neighborhood takes, at most, time linear of the number
of decisions made.
That is, theoretically, it takes linear time to {\em use} a decision ordering diagram (see \ref{sec:dod}).

Empirically, it take low-order polynomial time to {\em generate} a decision ordering diagram using the KEYS2 algorithm.
This algorithm makes the ``keys'' assumption - that a small group of variables control all of the others -  and uses Bayesian
ranking mechanism to quickly find those keys. As discussed in the Section \ref{sec:keys}, this assumption holds over a wide range 
of models used in a wide range of domains. The keys assumption can be remarkably
effective: empirical results show that KEY2 can generate decision ordering diagrams 
faster than both standard and state-of-the art techniques in the search field (Section \ref{sec:bk2}). 
Better yet, curve fits to our empirical results in Section \ref{sec:scaleup}
show that KEYS runs in $O(N^{2})$ and, thus, should scale to very large models.

Prior to this work, two pre-experimental concerns were that:
\bi
\item
An algorithm would need to trade solution robustness against solution quality.
More robust solutions may not have the highest quality.
\item
Demonstrating solution robustness requires multiple calls to an analysis procedure.
\ei
At least for the models studied here, neither concern  was realized. KEYS2 generated the highest
quality solutions (lowest cost, highest attainments) and did so 
more quickly than the other methods (full results in Section \ref{sec:bk2}).

In Section \ref{sec:dod} it was argued that 
decision ordering diagrams are useful when they are 
{\em timely} to generate while being  {\em well-behaved} and {\em tame}.
KEYS2's results are the most {\em timely} (fastest to generate) of all 
of the methods
studied here. As to the other criteria,
\fig{in5} shows that KEYS2's decision ordering diagrams:
\bi
\item Move smoothly to a plateau with only a small amount of variance;
\item Have very low spreads, compared to the median results.
\ei
That is, at least for the models explored here, KEYS2 generated
decision ordering diagrams they are both {\em well-behaved} and {\em tame}.

In summary, I recommend KEYS2 for generating decision ordering diagrams since, apart from the (slightly 
slower) KEYS algorithm, I am currently unaware of other search-based software engineering 
methods that enable such a rapid reflection of solution robustness. 

\section{Recommendations for Future Work}\label{sec:fwork}

The scale-up study conducted in Section ~\ref{sec:scaleup} states that, by 2013, DDP models will be more than twice their current size. 
As these DDP models grow, it is not just the number of variables that grow. Larger models are more densely interconnected. 
More mitigations affect more risks, and more risks affect more requirements. Our current top
optimization techniques terminate in a matter of milliseconds. 
They effectively report real-time results for current models. However, further optimization is required in order 
to support the models that we expect to see in the future. 

Furthermore, by setting multiple mitigations
per round, KEYS2's judgments are based on less {\em evidence}
and thus contain more {\em variance} (that is, less tame). 
The small amount of variance in KEYS2 is within acceptable bounds, but other attempts
to fix a higher number of configurations per round have fallen outside
of these limits.

Research into how to improve the KEYS algorithm revealed that over $70\%$ of the execution time is spent 
polling the model for the cost and attainment performance values.
Each round, both KEYS and KEYS2 generate one-hundred sets of mitigation
configurations and score them. 
They use these instances to set the optimal mitigations to fixed values.
This instance generation step is the chief bottleneck in the KEYS 
algorithm. However, a large number of instances is needed to 
provide the {\em support} necessary to accurately rank mitigations. 
If fewer instances are generated, the algorithm's result variance 
will still fall outside of appropriate limits. 
Therefore, the basis for future research should be in how to 
retain high support while executing the model fewer times.

One attempt, KEYS-R, focused on reusing existing configuration sets 
that recieved high scores from the objective function (for more, see Section \ref{sec:keysr}). 
This KEYS variation was fast, but its results
were notably poor. It failed because it tried to reuse high-scoring
items without
regard for whether or not they still provided an adequate level of
support. 
One possible future extension to the KEYS formula could solve the issues of 
the 
original algorithm by using {\em active learning}~\cite{cohn94} to reflect over the space of past decisions.
Think of a natural thought process; someone who is looking for a 
specific book would not
search every shelf of a store in order of appearance.
Instead, they would walk directly to the
appropriate section. The same idea guides active learning.
Most machine learning algorithms are passive, they simply
read over (or randomly generate) a set of examples with no regard 
for the contents of that sample population. 
In contrast, an algorithm that makes use of active learning 
is able to exercise some level of control over the input that
it trains on.

In short, the performance of KEYS could be improved by - rather than attempting to {\em reuse} instances -
saving them and providing a quick method of {\em looking up} 
previously assessed model configurations.  
This proposed improvement clusters an
initial set of configurations, sorts these clusters into a cover tree,
and only consults the model for a score when an instance's 
performance cannot be assessed from the space of past judgments. 

KEYS (and its extension, KEYS2)is a powerful algorithm 
because it only explores a small fraction
of the total number of configurations. It is a safe expectation that,
out of the sheer number of possible settings, that 
not all possible configurations of the mitigations will lead to 
different effects.
By extension, it becomes possible that KEYS can assess new configurations
of the model without actually executing the model, but rather by 
remembering what happened with past settings.

\begin{figure}
\begin{center}
\includegraphics[width=5in]{cache.png}
\end{center}
\caption{The data architecture of a KEYS variant using a cache.} 
\label{fig:cachearch}
\end{figure}

\fig{cachearch} shows the dataflow of a KEYS variant extended
with an automated cache. In this system, KEYS will track the configurations used in the past as well as their unique score. 
Past data can be efficiently grouped, and a nearest-neighbor technique could extrapolate new combinations. 
By clustering the old results by their performance scores, KEYS could
reflect over old settings in order to offer potentially ideal new combinations.
Likewise, KEYS can pull out performance scores of 
configurations that fall into regions 
explored in the past (that is, the {\em smooth} regions where results
can be extrapolated).

A cluster can be said to be linear if, on average, performance scores 
can be interpolated from neighboring instances. 
If a cluster is linear and contains three items ${x, y, z}$ 
and ${y, z}$ are the nearest neighbors to $x$, then the 
$(cost,attainment)$ score pair of $x$ should
be the same as a linear interpolation between $y$ and $z$. 
The assumption behind this theory is based on analogy-based effort 
estimation ~\cite{shepperd97} - the $kth$ nearest neighbors to the test 
instance are linear. 
The performance score for one instance can be averaged from its 
neighbors. Consequently, if a new proposed set of mitigation settings
falls into a linear cluster, then KEYS needs not waste CPU time polling
the model for a score.
Instead, it can just interpolate the result in linear time.

For this cache-enabled variant of KEYS to outperform the original 
algorithm, it is essential that the clustering and processing of cache
entries takes less time than executing all possible configurations 
during each round. For this to succeed, KEYS must be able to 
quickly and incrementally cluster a large vector space. Without
efficient clustering, KEYS will not scale well to models with a 
large number of mitigations. 
Numerous studies ~\cite{jiang08a,nsf61,me08g,me09b}
have looked at the clustering of large vectors of settings, and they
have found that many existing tools require complex and costly 
computations that must be repeated with every new set of configurations.

One way to avoid some of the computational overhead when dealing with
new data is to do a single clustering on the initial set of one-hundred
configurations that KEYS proposes. 
Once these clusters are computed, the algorithm can 
assign a unique identifier to each one.  
A cover-tree algorithm can be run on these clusters in order to generate
a hierarchical distance tree. 
The generation of this tree will be much faster if the data is in a set
number of clusters, rather than having to process every initial 
set of mitigation settings.
From this point, every unseen set of configurations can be quickly 
mapped to the most appropriate cluster by dropping it through the tree.

Interestingly, once linear clusters are identified, 
KEYS could be trained to avoid them.
New configurations that fall into linear clusters, especially those
clusters associated with worse performance scores, add no information 
about the effects of different configurations. 
Once these regions are known, the KEYS algorithm can rule out large 
sections of the search space by ignoring regions which are linear or, 
on average, produce results that are significantly
worse than other regions.

An interesting, and open, research question is how many clusters are
appropriate and how many data items should {\em "fall"} into a region
before any sort of re-clustering occurs. The fewer the clusters, the
more approximate the reasoning. 
Until this hypothetical version of KEYS is implemented, it is 
impossible to know the space of trade-offs between efficiency and
cluster size; however, one potential approach is to use the 
PID incremental discretizer, as proposed by Gama and Pinto ~\cite{gama06}.
This discretizer maintains two arrays - a {\em lower} and {\em upper} -
each with different discretizers. 
The upper array is filled with new data, and if the frequency counts 
grow too large, PID splits each bin into two new bins. 
At certain intervals, the upper array migrates its contents into a 
summarized set of breakpoints in the lower array.
This simple scheme has been recommended by Yang and Webb ~\cite{yang02}
because it is simple to implement and because, by only propagating 
frequency counts to the lower array, PID has been shown to be 
seven to ten times more efficient than other algorithms.

Unfortunately, any change in the bin boundaries of the data will require
the recreation of clusters. This is an expensive process, as it also 
requires a rebuilding of the cover tree and a complete pass through all 
of the data. Incremental re-clustering is necessary to maintain the 
accuracy of KEYS' predictions, but how often this should occur remains
an open question. 

Research following the development of KEYS2 has revealed a 
limiting factor in further attempts to improve the algorithm.
Over $70\%$ of the execution time is spent polling the model for the 
cost and attainment values associated with a particular configuration. 
This proposed extension to KEYS solves such issues by utilizing
active learning. An
initial set of configurations is generated and clustered, 
these clusters are sorted into a cover tree,
and the model is only consulted when a configuration's 
performance cannot be assessed from the space of past judgments. 
This caching concept should see a performance gain for the KEYS 
algorithm, which could be further increased by training KEYS to avoid
linear (i.e. smooth) areas of data where performance is less than ideal.
