\documentclass[onecolumn,draftcls,journal,compsoc]{IEEEtran}
%\documentclass[technote]{IEEEtran}
%\documentclass{sig-alternate}
\usepackage{graphicx}
\usepackage{wrapfig,url,times}
\newcommand{\boxplot}[5]{
	\begin{picture}(100,10)
		\put(0,0){\line(0,1){8}}
		\put(100,0){\line(0,1){8}}
		\put(#1,4){\line(1,0){#2}}
		\put(#3,4){\circle*{6}}
		\put(#4,4){\line(1,0){#5}}
		\put(50,0){\line(0,1){8}}
	\end{picture}
} 
\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}
%\makeatletter
%  \AddToShipoutPicture{%
%    \setlength{\@tempdimb}{.5\paperwidth}%
%    \setlength{\@tempdimc}{.5\paperheight}%
%    \setlength{\unitlength}{1pt}%
%      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.80}{\fontsize{5cm}{5cm}\selectfont{Draft v5}}}}}
%\makeatother
%
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\usepackage{times}
\usepackage{alltt}
\usepackage{url}
% IEEE Computer Society needs nocompress option
% requires cite.sty v4.0 or later (November 2003)
\usepackage{cite}
% normal IEEE
 % \usepackage{cite}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\pdfpagewidth=8.5in
\pdfpageheight=11in
\begin{document}

%\conferenceinfo{PROMISE'09,} {May 18--19, 2009, Vancouver, Canada} 

%\CopyrightYear{2009}

%\crdata{978-1-60558-036-4/08/05}


%\CopyrightYear{2008} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.

\title{
Early-lifecycle Decision Making in Real-time
%\titlenote{Submitted to the PROMISE 2008 workshop on repeatable SE experiments.
%%A draft version of this paper may be downloaded fro
%\url{http://menzies.us/pdf/08keys.pdf}
%}
}

%\numberofauthors{1}
%
\author{
%% 1st. author
\alignauthor Gregory Gay, Tim Menzies, Omid Jalali
\\~\\
       \affaddr{Dept of CS\& EE, West Virginia University, Morgantown, WV, USA}\\
       \email{gregoryg@csee.wvu.edu, tim@menzies.us, ojalali@mix.wvu.edu}
}
%
\date{8 May 2009}

%\maketitle
\begin{abstract}

Early life cycle risk models can represent the requirements that a development group would want to achieve, the risks that could prevent these requirements from being met, and mitigations that could alleviate those risks. Our task is the selection of the least expensive set of mitigations that achieve the highest attainment of requirements.

These models are used by a large group of debating scientists as part of the design process. Thus, as the risk models grow larger, the demand for faster optimization methods also increases. These experts require results to appear as fast as decisions are made. The goal of this research is real-time requirements optimization.

Prior work has focused on the KEYS algorithm, a novel Bayesian technique that identifies both the useful set of mitigations as well as cost-attainment tradeoffs for partial solutions. This paper reports new research in the further optimization of the KEYS algorithm as well as the experiments that confirm the usefulness of these new methods.

\end{abstract}
%\category{i.5}{learning}{machine learning}
%\category{d.2.8}{software engineering}{product metrics}
%\terms{algorithms,experimentation, measurement}
%\keywords{[TBD]}

\section{Introduction}

Software models are, without a doubt, becoming an increasingly important factor in the world of 
Software Engineering. It is easy to see why this is the case. 
The use of models imposes structure and a common vocabulary ~\cite{hailpern06}. 
Models allow developers to see a problem more clearly, which in turn reduces 
time-to-market and increases productivity ~\cite{sendall03}. 
It is for this reason that firms as diverse as Microsoft ~\cite{greenfield04} 
and Lockheed Martin  have accepted model-based SE as the norm. 

One model of particular interest is the Defect Detection and Prevention (DDP) model ~\cite{corn01,feather08}
proposed and used by NASA's Jet Propulsion Lab. In the simplest terms, DDP allows a team of experts to
find the least costly project options that most increase the chance to meet more goals. By visually displaying 
the connections between the objectives and risks, these software researchers can find important combinations 
of options that might have been missed. 

Often, it is not possible for human experts to debate all N options within a DDP
model. Many of these models contain dozens to hundreds of options and it would be impossible to 
debate all $2^{N}$ combinations of those options. Typically, these scientists focus on a set number
of "what-if" scenarios. This focus introduces a "blind-spot" into the requirements analysis, certain 
potentially important issues are completely overlooked in the expert's debates. 

In order to probe those blind spots, we study model-optimization algorithms. For each 
potential scenerio, an optimization algorithm looks over a model and imposes constraints.
These algorithms propose settings to the un-constrained options that would most increase the benefits
while minimizing the cost. In a surprisingly large number of cases, our optimization studies have offered 
recommendations thst the human experts missed.

In order to provide useful blind-spot exploration, our DDP optimization tools must run fast
enough that humans can get feedback before they must move on to other issues. 
Several techniques have been previously proposed for DDP optimization ~\cite{feather08,fea02a,gay08}. 
Our previous solutions to the DDP optimization problem are too slow. 
Ideally, we wish for requirements optimization to occur in "real-time"; i.e. to offer advice before 
an expert's attention wanders to other issues. Neilson ~\cite[chp5]{neilson93} reports 
that "the basic advice regarding response times has been about the same for thirty years; i.e.
\bi
\item 1.0 second is about the limit for the user's flow of thought to stay uninterrupted, 
even though the user will notice the delay
\item 10 seconds is the limit for keeping a user's attention focused on the dialogue."
\ei

\begin{figure}[!t]
\centering
\small
\begin{tabular}{r|l}
Year & Num. Variables\\\hline
2004 & 30 \\
2008 & 100 \\
2010 & 300\\
2013 & 800\\\hline
\end{tabular}
\caption{Growth trends; number of variables in DDP's data dictionary.} 
\label{fig:numVariables}
\end{figure}

\fig{numVariables} shows the growth rate (historically and projected) of the number of variables within a 
DDP model. It is expected that, by 2013, DDP models will be roughly eight times 
larger than they are today.
As DDP models grow, it is not just the number of variables that grow. Larger models have more interconnections. 
More mitigations affect more risks, and more risks effect more requirements. Our current top
optimization techniques (the KEYS and KEY2 algorithms, explained later) terminate in a matter of miliseconds. 
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. 

The rest of this paper describes our current progress as well as a new variation of the KEYS technique that
is expected to scale to future models. 

\section{Defect Detection and Prevention}
\subsection{What are DDP Models?}

In a typical design session at the NASA Jet Propulsion Lab, a larger group of
designers refine a project's high-level design document. These designers are
NASA's top experts, and their time is important. Therefore, it is crucial that 
this design process be as efficient as possible. Tools are chosen for their ability to
provice interactive design advice in a clear and timely manner. 
Only brief assertions can be collected during these short design sessions. If 
more complicated assertions were to emerge, these experts may be unable to 
understand technical arguments from outside their field of expertise. 
Therefore, the chosen modeling tool must support a lightweight ontology. 

DDP is based on the following principles:
\bi
\item {\em Earlier is Better:} The case for ``earlier is better'' is well established. Fark et al. ~\cite{fa07} noted that ``80\% of all design decisions are taken in the first 20\% of the design time.'' It is obvious that design tools not designed to operate early in the life cycle can only affect a small portion of the remaining decisions.
Not only is earlier design critical, but rapid improvement of those designs is also critical. 
Fixing defects costs exponentially more the longer that those defects remain in the system. Boehm and Papaccioa advise that reworking software
is cheaper earlier in the life cycle ``by factors of 50 to 200.'' ~\cite{boehm88}
\item {\em Use Risk-driven SE:} In risk-driven SE ~\cite{boehm86}, there are three primary modeling constructs. The engineering {\em requirements} are mapped to a series of {\em risks},  a representation of any of the 
factors that could prevent a goal from being reached. 
{\em Mitigations} are measures that may be implemented in order to alleviate, or at least reduce, risks. 
During interactive sessions, DDP models are projected on a screen where teams and designers review and extend the network.
This information can influence the entire design process and may lead to a more efficient development cycle.
\item {\em Use Value-based SE:} DDP is also a {\em value-based SE} ~\cite{bi05} tool where the {\em benefits} of a design variant are weighed against their {\em cost}. Each mitigation in a DDP model has an associated cost so that optimization tools can 
guide and optimize decision making. For example, on a fixed budget, KEYS can find the cheapest mitigations that retire the most risks and hence
allow for the attainment of the most requirements. 
This can repeat this process for different cost levels to generate a cost-benefit diagram of the search space.  
\ei

The "Defect Detection and Prevention" (DDP) tool is commonly used because it provides a 
succinct ontology for representing this design process. These models represent three core
concepts: requirements, risks, and risk-removing mitigations. These models are a powerful method
of modeling the relationships between project factors, yet are simple enough to meet the efficiency requirement.

DDP assertions are either:

\bi
\item \textit{Requirements} (free text) describing the objectives
and constraints of the mission and its development process; 
\item \textit{Weights} (numbers) associated with requirements, reflecting
their relative importance; 
\item \textit{Risks} (free text) are
events that damage requirements; 
\item \textit{Mitigations}: (free
text) are actions that reduce risks; 
\item \textit{Costs}: (numbers) effort associated with mitigations, and repair costs for
correcting Risks detected by Mitigations; 
\item \textit{Mappings}: directed edges between
requirements, mitigations, and risks that capture quantitative relationships among them. 
\item \textit{Part-of relations}
structure the collections of requirements, risks and mitigations; 
\ei

Past DDP models have 
been applied to dozens of hardware and software applications. Some examples of these include gyroscope design, 
software code generation, circuit board fabrication, and a motor controller.
Clear project improvements have been seen from these DDP sessions. Cost savings in at least two sessions have exceeded \$1 million, 
while savings of over \$100,000 have resulted in others. Cost savings are not the only benefits of these DDP sessions. 
Numerous design improvements such as savings of power or mass have come out of these debates.
Likewise, a shifting of risks has been seen from uncertain architectural ones to more predictable and manageable ones. 
At some of these meetings, non-obvious significant risks have been identified and subsequently mitigated. \
For all of these reasons, DDP remains in use at JPL not only for its original purpose of group decision support but also as a design rationale tool. 

It is important to note that DDP is not just a software design tool. Software and hardware are frequently designed together at JPL. DDP models are
better viewed as a {\em software systems engineering} tool where the interactions between hardware and software, and the possible incompatibilities, can be quickly explored.


\begin{figure}[!t]
\includegraphics[width=3.5in]{ddpMoldel2.pdf}
\includegraphics[width=3.5in]{arrt.pdf}
\caption{Representations of DDP models}
\label{fig:modelpic}
\end{figure}
 
\subsection{The DDP Model format}

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
#include "model.h"

#define M_COUNT 2
#define O_COUNT 3
#define R_COUNT 2

struct ddpStruct
{
    float oWeight[O_COUNT+1];
    float oAttainment[O_COUNT+1];
    float oAtRiskProp[O_COUNT+1];
        float rAPL[R_COUNT+1];
    float rLikelihood[R_COUNT+1];
    float mCost[M_COUNT+1];
    float roImpact[R_COUNT+1][O_COUNT+1];
    float mrEffect[M_COUNT+1][R_COUNT+1];
};

ddpStruct *ddpData;

void setupModel(void)
{
    ddpData = (ddpStruct *) 
		malloc(sizeof(ddpStruct));
    ddpData->mCost[1]=11;
    ddpData->mCost[2]=22;
    ddpData->rAPL[1]=1;
    ddpData->rAPL[2]=1;
    ddpData->oWeight[1]=1;
    ddpData->oWeight[2]=2;
    ddpData->oWeight[3]=3;
    ddpData->roImpact[1][1] = 0.1;
    ddpData->roImpact[1][2] = 0.3;
    ddpData->roImpact[2][1] = 0.2;
    ddpData->mrEffect[1][1] = 0.9;
    ddpData->mrEffect[1][2] = 0.3;
    ddpData->mrEffect[2][1] = 0.4;
}

void model(float *cost, float *att, float m[])
{
    float costTotal, attTotal;
    ddpData->rLikelihood[1] = ddpData->rAPL[1] * (1 - m[1] 
				* ddpData->mrEffect[1][1]) 
        			* (1 - m[2] 
				* ddpData->mrEffect[2][1]);
    ddpData->rLikelihood[2] = ddpData->rAPL[2] * (1 - m[1] 
				* ddpData->mrEffect[1][2]);
    ddpData->oAtRiskProp[1] = (ddpData->rLikelihood[1] 
				* ddpData->roImpact[1][1]) 
        			+ (ddpData->rLikelihood[2] 
				* ddpData->roImpact[2][1]);
    ddpData->oAtRiskProp[2] = (ddpData->rLikelihood[1] 
				* ddpData->roImpact[1][2]);
    ddpData->oAtRiskProp[3] = 0;
    ddpData->oAttainment[1] = ddpData->oWeight[1] 
				* (1 - minValue(1, 
				ddpData->oAtRiskProp[1]));
    ddpData->oAttainment[2] = ddpData->oWeight[2] 
				* (1 - minValue(1, 
				ddpData->oAtRiskProp[2]));
    ddpData->oAttainment[3] = ddpData->oWeight[3] 
				* (1 - minValue(1, 
				ddpData->oAtRiskProp[3]));
    attTotal = ddpData->oAttainment[1] 
				+ ddpData->oAttainment[2] 
				+ ddpData->oAttainment[3];
    costTotal = m[1] * ddpData->mCost[1] + m[2] 
				* ddpData->mCost[2];

    *cost = costTotal;
    *att = attTotal; 
}
\end{verbatim}}
~\hrule~
\caption{A trivial DDP model after knowledge compilation}
\label{fig:ddpExample}
\end{figure}

The large visual models projected for the rooms of NASA experts are a great visualization tool, 
but they are not as useful for optimization studies. These large models must be {/em compiled}
into a format that can be used by a variety of algorithms.  
Knowledge compilation is a technique whereby certain information is compiled into a target language.
These compiled models are used to rapidly answer a large number of
queries while the main program is running~\cite{selman96knowledge,darwiche02}.  
A simple {\em knowledge compiler} exports the DDP models into a form accessible by our search engines.
Previous work with knowledge compilation has focused
on compilation languages utilizing CNF equations, state machines,
or BDD~\cite{darwiche02,biere99:bmc}.  For this work, a procedural
target language was sufficient. Hence, the DDP models were compiled
into a structure used by the C programming language.  

Knowledge compilation pushes some  percentage
of the computational overhead into the compilation phase. This cost
is amortized over time as we increase the number of on-line queries.
This is a very useful feature in our application since
some of the algorithms that we use make thousands of calls to these
DDP models. By using pre-compiled models, the runtimes of our model-optimization
algorithms are dramatically reduced. 

In standard DDP, requirements form a tree and the relative influence of each leaf requirement is computed via
a depth-first search from the root down to the leaves.  
This computation is repeated each time the relative influence of a requirement is required.
Our knowledge compilation process stores a flattened form of the DDP requirements tree. 
In this compiled form, the computation is performed once 
and added as a constant to each reference of the requirement.

For example, here is a trivial DDP model
where  {\tt mitigation1} costs \$10,000 to apply and each requirement is of equal
value (100): 
\[\overbrace{mitigation1}^{\$10,000} \underbrace{\rightarrow}_{0.9} risk1 \rightarrow
\left< \begin{array}{c} \overbrace{\rightarrow}^{0.1} (requirement1=100) \\ 
\underbrace{\rightarrow}_{0.99} (requirement2=100) \end{array} \right.\]
(The other numbers show the impact of mitigations on risks, and the impact of risks
on requirements).

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|r|c|} \hline
No.&Baseline&IRRF with N=1&IRRF with N=3&IRRF with N=5\\ \hline
Corpus 1:&&&&\\ \hline 
1&54&1 (16m/15r)&11 (51m/16r)&36 (50m/10r) \\ \hline
2&17,42,47&99, 1, 2 (9m/8r)&4, 1, 2 (7m/3r)&6, 4, 14 (9m/2r) \\ \hline
3&1K+, 368, 531, 1K+, 108, 139&1K+, 1K+, 1K+, 1K+, 1K+, 1K+ (2m/2r)&1K+, 1K+, 1K+, 1K+, 1K+, 1K+ (7m/2r)&1K+, 1K+, 1K+, 1K+, 1K+, 1K+ (11m/2r) \\ \hline
4&9&1 (5m/5r)&1 (23m/8r)&4 (10m/2r) \\ \hline
5&8&1 (2m/2r)&1 (4m/2r)&2 (7m/2r) \\ \hline
6&428&448 (5m/5r)&3 (48m/16r) &5 (46m/9r)\\ \hline
7&583,56&1K+, 781 (2m/2r)&604, 1 (37m/13r)&1K+, 1K+ (20m/4r)\\ \hline
Corpus 2:&&&&\\ \hline
1&40,87,22&70, 60, 50 (8m/7r)&39, 7, 42 (22m/7r)&30, 5, 33 (26m/5r)\\ \hline
2&296&1 (37m/36r)&289 (12m/4r)&5 (41m/9r)\\ \hline
3&7&1 (6m/4r)&1 (5m/2r)&1 (7m/2r)*\\ \hline
4&47&216 (2m/2r)&242 (9m/3r)&146 (10m/2r)\\ \hline
5&354&98 (5m/5r)&3 (36m/12r)&3 (28m/6r)\\ \hline
6&151&238 (4m/4r)&38 (48m/16r)&35 (50m/10r)\\ \hline
Corpus 3:&&&&\\ \hline
1&15,550&1, 11 (8m/7r)&3, 109 (17m/5r)&1, 81 (12m/3r)\\ \hline
2&122&613 (6m/3r)&1K+ (8m/2r)&1K+ (12m/2r)\\ \hline
3&7&1 (3m/2r)&1 (5m/2r)&1 (7m/2r)*\\ \hline
4&58&141 (4m/3r)&1 (13m/5r)&1 (16m/4r)\\ \hline
5&52&1 (3m/3r)&2 (5m/2r)&2 (7m/2r)\\ \hline
\end{tabular}
\end{center}
\caption{Details of our DDP Models. For artifically-generated models, the first number 
in the name (2,4, or 5) comes from the model they are based on. 
The second number is a size multiplier. }
\label{fig:resultsTable}
\end{figure}

The knowledge compiler converts this trivial DDP model into {\tt setupModel} and {\tt model} functions 
similar to those in \fig{ddpExample}.
The {\tt setupModel} function is called only once and sets several constant values. 
The {\tt model} function is called whenever new cost and attainment values are needed.
The topology of the mitigation network is represented as terms in equations within these functions. 
As our models grow more complex, so do these equations. 
\fig{ddpModels} shows the models used in our most recent experiments. Our largest model, model4-16, contains 800 objectives, 
496 risks, and 928 mitigations. Its compiled form contains over 19000 lines of code.   

\section{Keys and the KEYS Algorithm}
\subsection{What are "Keys?"}

The premise of the KEYS algorithm is that, within the space of possible
decisions, there exist a small number of $key$ decisions that
determine all others~\cite{me07d}. 
Before explaining the KEYS algorithm, it is important to explore 
the general concept of ``keys''.

Within a model, there are chains that link inputs to the desired goals.
As might be expected, some of the links in the chain clash with others. 
Some of those clashes are not dependent on other clashes, i.e they are the most {\em upstream}. 
In the following chains of reasoning 
the clashes are $\{e, \neg e\}$, 
$\{g, \neg g\}$ 
\& $\{j,\neg j\}$;
the most upstream clashes 
are
$\{e \neg e\}$, 
\& $\{g \neg g\}$, 
\[\begin{array}{r@{}l@{}l}
&a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e\\
input_1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
input_2 \longrightarrow  &k \rightarrow \neg g \longrightarrow l \longrightarrow m \rightarrow \neg j & \longrightarrow goal\\
&n \longrightarrow o \longrightarrow p \longrightarrow q \longrightarrow
\neg e
\end{array}
\]

In order to make decisions and optimize this model, we must first decide about these {\em upstream} clashes.
We refer to these important decisions as {\em the collars}, which restrict the rest of the model.

Returning to the above chain example,
any of $\{a, b, ..q\}$ are subject to discussion. 
However, most of this model is completely irrelevant to the task of
$input_i\vdash~goal$. For example, 
the $\{e, \neg e\}$ clash is
unimportant to the decision making process
as no reason uses $e$ or $\neg e$. 
In the context of reaching $goal$ from 
$input_i$, the only important discussions are
the clashes $\{g,\neg g,j,\neg j\}$.
Since $\{j, \neg j\}$ are dependent on $\{g,\neg g\}$, then the core decision
must be about variable $g$ with two disputed values: true and
false. 

In this example, we call $g$ 
the {\em collar} since it restricts the entire model.
The collar may be internal to a model and may not be directly controllable. 
We refer to the controllable variables that can influence the collar as the   $keys$
In the previous example, those key is $input_i$.

Using the keys to set the $collars$ reduces the number of reachable states within the model. 
Formally, the reachable states reduce to
the cross-product of all of the ranges of the collars.
We call this the $clumping$ effect. Only a small fraction of the possible states are actually reachable.
The effects of clumping can be quite dramatic.
Without knowledge of these chains and the collar, the above model has $2^{20} > 1,000,000$ possible consistent states.
However, in the context of 
$input_i\vdash~goal$,
those 1,000,000 states clumps to just the following two states: 
$\{input_1,f,g,h,i,j,goal\}$ or
$\{input_2,k,\neg g,l,m,\neg j,goal\}$.

KEYS and KEYS2 were designed under this assumption. 
The behavior of a large system is
determined by a very small number of {\em collar} variables.
For a system with collars, the state space within the model {\em clumps} to a small fraction of
the possible reachable states.

The concepts of $keys,collars,clumps$  have been discovered and rediscovered
many times.  Elsewhere ~\cite{me03l}, we have documented
dozens of papers that have reported this effect
under different names including {\em
narrows, master-variables, back doors,} and {\em feature subset
selection}. A few examples from software engineering literature include:
\bi
\item
Amarel ~\cite{Amarel86} observed that msny search problems contain {\em narrow} sets of variables or collars that must be used in any solution.
In such a search space, what matters is not so much how you arrive at these collars, but what decision are made when you get there.
Amarel defined macros encoding paths between {\em narrows}, effectively permitting a search engine to jump between them.
\item
Druzdel~\cite{druzdel94} represented a model
as the product of
distributions of the model's variables.
Given  enough  variance in the individual priors 
and conditional probabilities of the variables, the 
frequency of model states will exhibit a 
log-normal distribution. Such a system would show the clumping effect; a small 
fraction of the states would cover a large portion of the total 
probability space, with the remaining states being negligible. 
He studied one piece of software
where the reached states were a vanishingly small fraction of the set of possible states.
In one diagnosis system 
with a total of
525,312 possible internal 
states, he found that there were a total of 49 states that were reached 91\% of the time and only one state was ever reached 52\% of the time.  
\item
Numerous researchers have examined {\em feature subset selection};
i.e. what happens when a data miner deliberately ignores some of
the variables in the training data. For example, Kohavi and
John~\cite{kohavi97} showed in numerous datasets that as few as
20\% of the variables are $key$ - the remaining 80\% of variables
can be ignored without degrading a learner's classification accuracy.
\item
Williams et.al.~\cite{williams03} discuss how
to use keys  (which they call ``back doors'') to optimize search.
Constraining these back doors also constrains the rest of the program. 
So, to quickly search a program, they suggest imposing some set values on the key variables.
They showed that setting the keys
can reduce
the solution time of certain hard problems from exponential to polytime, provided that the
keys can be cheaply located, an issue on which Williams et.al. are curiously silent.
\ei

\subsection{The KEYS algortihm}

There are two main components to KEYS - a greedy search and the BORE ranking heuristic.

The greedy
search within KEYS explores a space of $M$ 
mitigations over a series of "eras" (equal to $M$). 
The entire set of mitigations is initially set at random. 
During each era, one additional mitigation is locked down by setting it to $M_i=X_j$, $X_j \in \{true,false\}$. 

Each era $e$ generates
a set $<input,score>$ as follows:
\be
\item[1:]
$MaxTries$ times repeat:
\bi
\item
$Selected[1{\ldots}(e-1)]$ are settings from previous eras.
\item
        $Guessed$ are randomly selected values for unfixed mitigations.  
\item
        $Input = selected \cup guessed$.
\item
Call {\tt model} to compute $score=ddp(input)$;
\ei
\item[2:] The $MaxTries$ $score$s are divided into $\beta$\% ``best'' while
the remainder are sent to  ``rest''. 
\item[3:]
The mitigation values in the $input$ sets are then scored using BORE
(described below).
\item[4:]
The top ranked mitigations (the default is one, but the user may fix multiple mitigations at once) are fixed and stored in $selected[e]$.\ee
The search moves to era $e+1$ and repeats steps 1,2,3,4.
This process stops 
when every mitigation has a setting.  
The exact settings for $MaxTries$ and $\beta$ must be set via engineering judgment.
After some experimentation, we used $MaxTries=100$ and $\beta=10$.
For full details, see \fig{KEYS}. 
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure KEYS
2. while FIXED_MITIGATIONS != TOTAL_MITIGATIONS
3.    for I:=1 to 100
4.       SELECTED[1...(I-1)] = best decisions up to this step
5.       GUESSED = random settings to the remaining mitigations
6.       INPUT = SELECTED + GUESSED
7.       SCORES= SCORE(INPUT)
8.    end for   
9.    for J:=1 to NUM_MITIGATIONS_TO_SET 
10.      TOP_MITIGATION = BORE(SCORES)       
11.      SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 
12.   end for  
13. end while          
14. return SELECTED \end{verbatim} }
~\hrule~
\caption{Pseudocode for KEYS}
\label{fig:KEYS}
\end{figure}

KEYS ranks mitigations using BORE ~\cite{clark05} (short for ``best or rest''), a Bayesian ranking heuristic.
BORE divides scores seen over the past $K$ runs into the top 10\%  $best$ and the remaining 90\% scores (the $rest$). 
The $best$ set is computed by studying the difference of each score and the best score seen in any era.
BORE then computes the probability that a value is found in $best$
using Bayes' theorem.
The theorem uses evidence $E$ and a prior probability $P(H)$ for
hypothesis $H\in\{best, rest\}$,
to calculate the  posterior  probability
$P(H|E)=P(E|H) P(H)\; /\; P(E)$.
When applying the theorem, {\em likelihoods}
are computed from observed
frequencies. These likelihoods (called "like" below) are then normalized to create
probabilities. This normalization cancels out the $P(E)$ factor in Bayes theorem.
For example, $K=10,000$ runs are divided into  the 1,000 {\em best} and 9,000
{\em rest}, the  value \mbox{$mitigation31=false$} might appear 10 times in the $best$ solutions, but only
5 times in the $rest$. Hence:\newline
\begin{minipage}{1.0\linewidth}
{\scriptsize
\begin{eqnarray}\nonumber
E&=& (mitigation31=false)\\\nonumber
P(best)&=&1000/10000 = 0.1\\\nonumber
P(rest)&=&9000/10000 = 0.9\\\nonumber
freq(E|best)&=&10/1000 = 0.01\\\nonumber
freq(E|rest)&=&5/9000 = 0.00056\\\nonumber
like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber
like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66
\end{eqnarray}}
\end{minipage}\newline

To avoid the problem of unreliable low frequency evidence ~\cite{clark05}, \eq{ten}
is modified to include a support term.
the value of support should increase as the frequency of a value increases. 
Step 3 of KEYS' greedy search ranks values  via
\begin{equation}\label{eq:ps3}\small
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}

\subsection{KEYS2 - A faster KEYS}

For each era, KEYS only fixes the top $N=1$ settings.
For the DDP models, costs and attainment improvements generally increase
for each era of KEYS.
KEYS could jump further and faster into the solution space by 
fixing $N\ge 1$ settings  per era.
Research evidence suggests that multiple equations could be safely fixed at once.
Therefore, KEYS2 improves the speed of KEYS by locking down an increasing number of mitigations each round.

Such a {\em jump} policy 
can be implemented as a
small change to KEYS:
\bi
\item
Standard KEYS
assigns the value of one to  \newline{\tt NUM\_MITIGATIONS\_TO\_SET} (see the pseudo-code of \fig{KEYS});
\item
Other variants of KEYS assigns larger values.
\ei
Several variants were experimented with before deciding that $i$ settings will be set during era $i$ .
Note that, in era 1, KEYS2 behaves exactly the same as KEYS
while
in (say) era 3, KEYS2 will
fix the top 3 ranked ranges. 
Since it sets more variables at each era,
KEYS2 terminates earlier than KEYS.

\subsection{KEYS-R and Instance Retention}

While KEYS2 represents a massive runtime improvement over the original KEYS, 
it contains a fundamental flaw. By setting multiple mitigations each round, the 
algorithm loses the "support" built by the one-hundred instances generated each round. 
Therefore, while KEYS2 is faster than the original KEYS, its results contain more {\em variance}.

The additional variance in KEYS2 is still within acceptable boundaries; therefore,
it has found some use in DDP-related experiments. However, this has limited the further improvements that could be made to the KEYS 
algorithm. Numerous other variations on how to set multiple mitigations per round have shown result variance far outside acceptable 
values. Other methods have not shown variance problems, but these versions of KEYS were slower than KEYS2, limiting their possible use. 
This issue prompted a new round of research. If the key to speeding up the KEYS algorithm was not in setting additional mitigations
each round, where was it? 

When a software profiler was used on KEYS2, one interesting point was revealed. Nearly {\em 70\%} of the runtime was spent in calling the model
(i.e. sending a new set of mitigations to the precompiled model and recieving back a new cost and attainment value).
Each round, both KEYS and KEYS2 generate one-hundred sets of mitigations and score them. They use these instances to find the best set of mitigations
to fix for that round. The instance generation step is the chief bottleneck in the KEYS algorithm. However, a large number of instances is needed to 
provide the {\em support} neccesary to accurately rank mitigations. If fewer instances are generated, you have the same issue as when too many mitigations
are set. There is a larger variance in results, and those results tend to contain higher cost and lower attainment values.
Therefore, the question is how to call the model {\em fewer} times while retaining {\em high} support for your instance set.

A new variant of the KEYS algorithm, KEYS-R addresses this issue by retaining certain subsets of previously-generated instances and reusing them in later rounds. KEYS-R begins by calculating two {\em threshold} values. These values are the highest possible cost (i.e. the cost if all mitigations are used)
and the highest possible attainment. 
The central loop (instance generation, ranking, and mitigation fixing) commence in the same way as the original KEYS. 
One hundred new instances are generated and stored. The key difference comes in the next step. Once an instance is scored, its cost and attainment 
values are compared to the previously-calculated threshold values. If an instance scores within ten percent of these values (if its cost is less than 10\% of the highest possible cost and its attainment is greater than 90\% of the model's possible attainment), it is stored in a collection of the {\em best} 
instances. If the instance's cost value is within 10\% to 35\% of the cost threshold and its attainment is from 65\% to 90\% of the possible attainment value, it is stored in a collection of {\em middle} instances. 

Each round, before a new set of instances is generated, a random subset of the {\em top} and {\em middle} sets are used instead of generating new instances. In order to ensure that support is maintained, new instances must be generated. Therefore, up to 33 instances can come from each set, adn the remaining 34 will be randomly generated new instances. 

As individual mitigations are fixed, these previously used instances will begin to lose their support value. That is to say,
results will lose their rigidity and variance will increase. Therefore, it is still important that we not reuse an instance too many times. 
A balance must be maintained between the stored instances and the newly-generated ones. To address this, a decay timer is attached to each instance when it is added to either the {\em top} or {\em middle} subsets. Whenever a new instance is added to once of these subsets, it will immediately replace an instance whose decay timer has expired. This allows support to be maintained while reducing the number of new instances that must be generated each round.  

\section{Experimental Results}

While our prior work ~\cite{gay08} has focused on a static set of DDP models donated from the NASA Jet Propolsion Lab, it was neccesary to create
new models that reflect the growth that we expect to see in the future. An {\em instance generator} was constructed based on a set of key rules in the
DDP models. It was used to create new models based on three of our original models as well as new models that ranged from 2-16x larger than those existing
models. These largest models represent massive projects that, while unheard of in the present day, will likely be commonplace within the next decade. 

For each of our generated models, we ran each KEYS variant one-hundred times in order to filter for outliers and obtain stable results. 
For each algorithm and model, the final attainment, cost, and runtimes were recorded. The results are presented below. 

\subsection{Attainment and Costs}

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
Original:&&&\\ \hline
model2.c& 7325   &7325         &6250           \\ \hline
model4.c& 876500   &921500        &711500          \\ \hline
Artificially Generated:&&&\\ \hline
model2-1.c& 0   &0         &0           \\ \hline
model2-2.c& 0   &140         &140          \\ \hline
model2-4.c& 125   &710         &1055            \\ \hline
model2-8.c& 1080   &3435         &5540          \\ \hline
model2-16.c& 10815   &22030         &35050           \\ \hline
model4-1.c& 0  &0        &0           \\ \hline
model4-2.c& 1000  &36500        &39500           \\ \hline
model4-4.c& 35500   &146000        &226000          \\ \hline
model4-8.c& 220000   &577000        &670000        \\ \hline
model4-16c& 1422500   &2733000        &5285000            \\ \hline
model5-1.c&1000    &6000        &7000           \\ \hline
model5-2.c&13575    &43050        &59500         \\ \hline
model5-4.c&93000    &228000        &325500            \\ \hline
model5-8.c&430050    &796650        &1233575           \\ \hline
\end{tabular}
\end{center}
\caption{Median results for each of our algorithms run on each model.}
\label{fig:costs}
\end{figure}

When the artificially-created versions of models 2 and 4 were ran, trhey both returned cost results of 0, 
while still obtaining top attainment values. This should not be possible, as the basic principle of the problem states that 
to gain high attainment, some risks must be mitigated. It is likely that some glitch in the model creation process resulted in
two models where the risks did not actually effect the important objectives. To address this problem, the original verisons
of models 2 and 4 were run to obtain comparable values. 

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
Original:&&&\\ \hline
model2.c& 0.7   &0.7         &0.7           \\ \hline
model4.c& 3013.1   &3010.6        &2857.7          \\ \hline
Artificially Generated:&&&\\ \hline
model2-1.c& 25   &25         &25           \\ \hline
model2-2.c& 54   &54         &54          \\ \hline
model2-4.c& 112   &112         &112            \\ \hline
model2-8.c& 228   &228         &228          \\ \hline
model2-16.c& 460   &460         &460           \\ \hline
model4-1.c&2591   &2591        &2591           \\ \hline
model4-2.c&3835 &3835       &3835           \\ \hline
model4-4.c&8727   &8727        &8727          \\ \hline
model4-8.c&18492   &18492       &18492          \\ \hline
model4-16c&34974.8   &34974.8       &34974.8            \\ \hline
model5-1.c &255.1      &255.1         &255.1           \\ \hline
model5-2.c&523.3    &523.3       &523.3         \\ \hline
model5-4.c&845.2    &845.2       &845.2            \\ \hline
model5-8.c&1787.9    &1787.9        &1787.9           \\ \hline
\end{tabular}
\end{center}
\caption{Median attainment results for each of our algorithms run on each model.}
\label{fig:attains}
\end{figure}

As expected, the original KEYS obtains the absolute best pair of cost and attainment. 
Unfortunately, KEYS-R does not do very well in comparison to KEYS2. KEYS-R returns much higher cost values.
It would be acceptable if its results were closer to KEYS2, but in certain extreme cases like model5-8, it returns a cost
estimater three times the value given by the original KEYS. These median results were compared to Mann-Whitney U tests,
only to reach the same conclusion. KEYS outperforms KEYS2, which outperforms KEYS-R. The results for nearly every model for the Mann-Whitney tests
were two wins for KEYS, two lossses for KEYS-R, and a win and a loss for KEYS2.

What is clearly occuring here is that KEYS-R, though designed to maintain support, clearly fails to do so. The
rules governing instance decay are clearly too simple. Future versions of KEYS-R, if pursued, will require stonger heuristics governing 
the use and reuse of stored instances. 

One point of interest is that KEYS-R performed very differently on the original models versus the generated ones. 
The results are not neccesarly better, they have just gone in the opposite direction. When run  on the original models, 
KEYS-R returns pairs with lower costs than KEYS or KEYS2 (good) but lower attainments (bad) as well.
It actually appears that the same
rules that were too loose for the artificially-generated models are too strict on the original models. Very few things are scored as 
"best." In one trial involving model5 from the original set, only three things were stored in the best subset. In the artificial version of
model5-1, one-hundred (the limit before decayed instances are replaced) examples are stored. This implies that KEYS-R is very dependent on
the actual construction of the model. Things like the number of connections between elements seems to drastically change the type of results that
appear.

\begin{figure}[!h]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
Original:&&&\\ \hline
model2.c& 0.00881   &0.00497         &0.00838          \\ \hline
model4.c& 0.04724   &0.01523        &0.03763          \\ \hline
Artificially Generated:&&&\\ \hline
model2-1.c& 0.00833   &0.00775        &0.00671           \\ \hline
model2-2.c& 0.02720   &0.02216         &0.0197          \\ \hline
model2-4.c& 0.10398   &0.04964         &0.07067            \\ \hline
model2-8.c& 0.44088   &0.13736         &0.30278          \\ \hline
model2-16.c& 1.76741   &0.48072         &1.29550           \\ \hline
model4-1.c& 0.04375  &0.01911        &0.02502           \\ \hline
model4-2.c& 0.17386  &0.05003        &0.09178           \\ \hline
model4-4.c& 0.73049   &0.15686        &0.39623          \\ \hline
model4-8.c& 2.97024   &0.59174        &1.83779         \\ \hline
model4-16c& 12.60780   &1.88267        &8.8363            \\ \hline
model5-1.c& 0.12882    &0.04055        &0.07276           \\ \hline
model5-2.c& 0.49749    &0.11666        &0.29788         \\ \hline
model5-4.c& 1.97696    &0.37918        &1.34306            \\ \hline
model5-8.c& 8.05896    &1.35119        &5.97226           \\ \hline
\end{tabular}
\end{center}
\caption{Runtime results for each of our algorithms run on each model.}
\label{fig:runtimes}
\end{figure}

\subsection{Runtime Analysis}

As \fig{runtimes} shows, KEYS-R falls right between KEYS and KEYS2 in terms of runtime. 
This is crucial, as standard KEYS is too slow to provide realtime results on the largest of 
our models. Even though KEYS returns results in less than a second on most models, 
it takes over twelve seconds on our largest model. By the year 2013, we expect a large number of 
complex DDP models to be equal to or greater than the size of model4-16. 

KEYS2 and KEYS-R both perform much better on those larger models. The fact that KEYS-R does so well
, even though it is setting a single mitigation each round, gives hope for future improvement.
If KEYS-R's cost values were more in line with expectations (i.e. if its support were improved),
it could be augmented to set more than one mitigation per round in the same vein as KEYS2. 
This would undoubtedly lead to much better runtimes and better scalability on future models.

\section{Conclusions}

Defect Detection and Prevention models are used by groups of experts
at NASA's Jet Propulsion Laboratory.
These experts have a limited amount of time to debate a massive number of issues. 
That is why it is crucial that constrain suggestions are returned in {\em real-time}. 
Solutions must be proposed before an expert's attention begins to wander, which is in about
ten seconds. 

As models continue to grow larger and larger, this goal becomes harder and harder.
Our KEYS tool provides the best cost and attainment solution pairs that we have seen out of the 
various machine learning approached employed in order to study these models.  
We attribute much of the  success of KEYS to 
the presence of $keys$ in the DDP models, those variables that
control everything else.  These key variables were exploited by KEYS using two methods:
BORE finds promising keys with high probabilistic support; and
KEY's greedy search constrains the most promising mitigation,
before exploring the remaining options. 
Therefore, the focus of our work has shifted from finding {\em better} results to finding {\em faster} results.

The issue in finding faster results is that the stability of the conclusions drops. To achieve a faster speed, 
the algorithm must either constrain more options in each round, or it must assess the model less.
Prior work has yielded the KEYS2 algorithm, which constrains more and more solutions on each pass through the generated instances. 
However, this type of solution has a strict limit. As you set more and more things, you lose {/em support} for those choices. The 
generated instances lose their usefulness. 

Therefore, this paper has focused on the second approach - assessing the model less. In the KEYS algorithm,
one-hundred new instances are generated each round. This bottleneck takes approximately 70\% of the processing time.
It would be useful to create fewer instances. The KEYS-R algorithm stores instances that meet with certain thresholds and reuses 
them in future rounds. To maintain stability, a decay timer has been implemented such that {\em decayed} instances are replaced by new ones.

However, KEYS-R yielded poor results on the models that we have created to represent the large models of the future. Its costs were higher than
those from KEYS or KEYS2. While it did not meet with our expectations, the idea behind it will form the basis of future work. That is, 
the key to providing real-time results on future DDP models is to find a way to maintain stability while generating fewer new instances.  

Currently, we continue to recommend that for real-time optimization of DDP-like requirements models, we recommend
knowledge compilation and KEYS2.


\bibliographystyle{plain}
\bibliography{refs}

%\begin{thebibliography}{10}


%\end{thebibliography}


\end{document}

