\documentclass{sig-alternate}
\usepackage{wrapfig,cite,url,times}
\newcommand{\aive}{{\"aive}}


\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}}
\pdfpagewidth=8.5in
\pdfpageheight=11in

\begin{document}
\conferenceinfo{PROMISE'08,} {May 12--13, 2008, Leipzig, Germany.} 

\CopyrightYear{2008}

\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{
Optimizing Requirements Decisions With KEYS
%\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{2}
\author{
% 1st. author
\alignauthor
Omid Jalali, Tim Menzies\\
       \affaddr{West Virginia University}\\
       \affaddr{Morgantown, WV, USA}\\
       \email{ojalali@mix.wvu.edu}\\
       \email{tim@menzies.us}
% 3rd. author
\alignauthor
Martin Feather\thanks{This  was carried out at
WVU 
and CalTech's Jet Propulsion Laboratory under a 
contract with NASA.
Reference 
herein to any specific commercial product, process, or service by trade 
name, trademark, manufacturer, or otherwise, does not constitute or im- 
ply its endorsement by the United States Government or the Jet Propulsion 
Laboratory, California Institute of Technology.}\\
       \affaddr{Jet Propulsion Laboratory,}\\
       \affaddr{California Institute of Technology,}\\
       \affaddr{Pasadena, California, USA}\\
       \email{martin.s.feather@jpl.nasa.gov}
}
\date{10 January 2008}

\maketitle
\begin{abstract}
Recent work with NASA's Jet Propulsion Laboratory has allowed for
external access to five of JPL's real-world requirements models,
anonymized to conceal proprietary information, but retaining their
computational nature. Experimentation with these models, reported
herein, demonstrates a dramatic speedup in the computations performed
on them.

These models have a well defined goal: select mitigations that
retire risks which, in turn, increases the number of attainable
requirements.  Such a non-linear optimization is a well-studied
problem.  However identification of not only (a)~the optimal
solution(s) but also (b)~the key factors leading to them is less
well studied. Our technique, called KEYS, shows a rapid way of simultaneously
identifying the solutions and their key factors.  

KEYS improves on prior work by several orders of magnitude.
Prior experiments with simulated annealing or treatment learning
took tens of minutes to hours to terminate.  KEYS runs much faster
than that; e.g for one model, KEYS ran 13,000 times faster than
treatment learning (40 minutes versus 0.18 seconds).

Processing these JPL models is a 
non-linear optimization problem: the fewest mitigations must be selected
while achieving the most requirements.
Non-linear optimization is a well studied problem.
With this paper, we challenge other members of the PROMISE community to improve on
our results with other techniques.
\end{abstract}
\category{i.5}{learning}{machine learning}
\category{d.2.1}{requirements}{tools}
\terms{algorithms,experimentation, measurement}
\keywords{keys, collars, clumps, DDP}

%
%XXX search-based SE
%
% holte: simplicity first
%
% fails on non boolean ranges. amxsat?
%
%XXX other methods, maxwalksat, linear programming.
%
%XXX introduce keys during tar3
%XXX ita from annals paper
%XXX from itar to keys. knowledge comilation
%
%XXX why make it faster?
%	1) not fast enough. success reeds greater expecations
%	2) interactive design support : 2 second rule
%	3) new geenration of stochastic sat solvers~\cite{http://www.cs.rochester.edu/u/kautz/walksat/Maxwalksat20.tgz), markov logics~\cite{rich05} to try
%
% A category with the (minimum) three required fields
%\category{H.4}{???????Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{??????Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{?????Delphi theory}

%\keywords{??????ACM proceedings, \LaTeX, text tagging}


\pagestyle{plain}
\section{Introduction}

Design, said Herbert Simon, is the quintessential human activity~\cite{simon96}.
A design optimization method could be used
in many domains; software or building construction, car manufacturing,
aircraft flight planning, just to name a
few.  As Simon says ``Engineering, medicine, business, architecture
and painting are concerned not with the necessary but with the
contingent - not with how things are but with how they might be -
in short, with design''.

Model-based design  is now a software engineering technique.
Sendall and Kozacaynski argue that
increasing
 productivity and reduced time-to-market for software products can
 accrue when ``using concepts closer to the problem domain ..." via
 modeling~\cite{sendall03}. Hailpern and Tarr observe that
 model-based design ``imposes structure and common vocabularies
 so that artifacts are useful for their main purpose in their
 particular stage in the life cycle'' \cite{hailpern06}. 

Numerous large
organizations now have active model-based SE teams such as Microsoft's
Software Factory~\cite{greenfield04}; Lockheed martin's Model Centric Software 
Development~\cite{waddington03};
the Object Management Group's Common Warehouse Metamodel~\cite{brown06};
and the DDP work at 
NASA's Jet Propulsion Laboratory~\cite{feather08}.  
Such models can 
be queried to find combinations of options that might be otherwise missed.
For example, with DDP,  the goal is a non-linear optimization that seeks
the {\em least} costly project options that {\em most} increases 
the chance of attaining more requirements.

Paradoxically, our prior successes~\cite{fea02a,me03c,feather08} with DDP has
caused a problem. 
Our user community now expects an
automatic model-based cost-benefit analysis for larger and larger JPL
models containing more variants.
Further, as requirements change (as is frequently the case), our users are demanding
a complete re-analysis of all past decisions.
Extrapolating
into the near future, we expect to fall off a computational cliff where
our models will be too complex for automatic analysis. 

Accordingly, we explore optimizations for model-based design.
Prior experiments with simulated annealing~\cite{feather08} 
or treatment learning~\cite{fea02a} 
terminated in minutes to hours.
Our new  method, called ``KEYS'', runs much faster; e.g
for one model, KEYS ran 13,000 times faster than treatment learning
(40 minutes to 0.18 secs).

The rest of this paper described JPL's DDP modeling systems; our prior work; 
the new KEYS algorithm;
and  experiments with KEYS on five DDP models.
The intent of this paper is to promote more repeatable experiments in model-based SE.
Our models
are now available in the PROMISE repository\footnote{
\url{promisedata.org/repository/data/models.zip}
}. This paper will be a success if other researchers try alternate
methods to find better solutions for the DDP models, or the same solutions in less time.

\newpage
\section{DDP: Software Systems Design }

At
JPL, the ``Defect Detection and
Prevention (DDP)'' tool~\cite{corn01,feather08} is in use to organize interactive
knowledge acquisition and decision making sessions with spacecraft
experts. The DDP tool provides an ontology for representing these requirements, risks,
and mitigations, and for reasoning about them.

DDP might be thought of as akin to the mainstream decision support
approach Quality Function Deployment (QFD)~\cite{akao90}, but with
a quantitative, probabilistic basis inspired by risk assessment
techniques. This novel combination places it in a sparsely
populated niche in decision making techniques. We believe this is
why DDP is useful for studying the requirements needs
of a wide variety of technologies, software, hardware and combinations
of the two. Quality requirements feature prominently during these
studies. DDP takes such requirements into consideration by relating
them to ``risks'' (used very generally to represent all the factors
that have the potential to impede the requirements attainment).
Then, DDP's support for locating cost-effective risk ``mitigation''
options can be applied. The net result is an approach that allows
stakeholders to explore alternatives among requirements the designs
to meet them, and the development approaches to follow, taking into
account the costs of those alternatives as they do so.

\begin{figure}[!b]
~\hrule~\\

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. The key ones are \textit{impacts},
each one of which is a quantitative estimate of the proportion of a requirement that would be lost should a risk occur, and
\textit{effects}, each one of which is a quantitative estimate of the proportion by which a risk would be reduced were a
mitigation to be employed (the ontology is also able to capture the phenomenon of a mitigation making some risks \textit{worse}).
\item \textit{Part-of relations}
structure the collections of requirements, risks and mitigations; 
\ei

~\hrule~
\caption{DDP's ontology}
\label{ddpont}
\end{figure}
\begin{figure}[!b]
\begin{center}
~\hrule~
\includegraphics[width=3.5in]{arrt.pdf}
\end{center}

{\small 
\bd
\item[Faces] denote requirements;
\item[Toolboxes] denote mitigations; 
\item[Skulls] denote risks;
\item[Conjunctions] are marked with one arc; e.g. \textit{require1} if
\textit{require2} and \textit{require3}. 
\item[Disjunctions] are marked
with two arcs; e.g. \textit{fault1} if \textit{fault2} or \textit{fault3}.
\item[Numbers] denote weights; e.g. \textit{action5}
 reduces the contribution of \textit{fault3} to \textit{fault1}, \textit{
fault1} reduces the impact of \textit{require5}, and \textit{action1}
reduces the negative impact of \textit{fault1}. 
\item[Oval] denotes
structures that are expressible in the latest version of the JPL
semantic net editor (under construction).
\ed
}
~\hrule~
\caption{A semantic net of the type used at JPL}%~\cite{fea01}} 
\label{arrt}
\end{figure}
The process by which DDP is employed is as follows:

\bi
\item 6 to 20 experts are gathered together for short, intensive knowledge
acquisition sessions (typically, 3 to 4 half-day sessions). These
sessions \textit{must} be short since it is hard to gather together
these experts for more than a very short period of time. 
\item The DDP tool supports a graphical interface for the rapid entry of the
assertions. Such rapid entry is essential, lest using the tool slows
up the debate. 
\item Assertions from the experts are expressed in
using an ultra-lightweight decision ontology (e.g. see Figure~\ref{ddpont}).
The ontology \textit{must} be ultra-lightweight since: 
\bi
\item Only brief assertions can be collected in short knowledge acquisition
sessions. 
\item If the assertions get more elaborate, then experts
may be unable to understand technical arguments from outside their
own field of expertise. 
\ei
\ei


The result of these sessions is a network of influences connecting
project requirements to risks to possible mitigations; see
Figure~\ref{arrt}.

The ontology
of Figure~\ref{ddpont} may appear too weak for useful reasoning. However, in
repeated sessions with DDP, it has been seen that the ontology is
rich enough to structure and guide debates between NASA experts.
For example, DDP has been applied to over a dozen applications to
study advanced technologies such as 
\bi
\item a computer memory device; 
\item gyroscope design; 
\item software code generation; 
\item a low temperature experiments apparatus; 
\item an imaging device;
\item circuit board like fabrication; 
\item micro electro-mechanical devices; 
\item a sun sensor; 
\item a motor controller;
\item photonics; and 
\item interferometry. 
\ei
In those studies, DDP
sessions have led to cost savings exceeding \$1 million in at least two
instances, and lesser amounts (exceeding \$100,000) in some
others. The DDP sessions have also generated numerous design
improvements such as savings of power or mass, and shifting of risks from
uncertain architectural ones to better understood (and hence more predictable and
manageable) design ones. Further, at
these meetings, some non-obvious significant risks have been
identified and mitigated. Lastly, DDP can be used to document
the information and decision making of these studies. Hence, DDP, although not mandated,
remains in use at JPL:

\bi
\item not only for its original purpose (group decision support);
\item but also as a design rationale tool to document decisions. 
\ei

Note that DDP is not just a software design tool. At JPL, software and hardware are
designed together. DDP is best viewed as a {\em software systems engineering} tool
where the interactions between hardware and software can be quickly explored.

\section{Treatment Learning}
Discrete models (like DDP) have ``cliffs'' where the behavior of a
system can change dramatically. Such non-continuous models are not suitable for numeric optimization.
Hence, in our previous work,
we applied data mining 
to find the least cost set of mitigations that lead to the greatest number of attainable
requirements.

The data miner used on DDP was the TAR2 and TAR3
{\em treatment learners}~\cite{hu02,fea02a,me02c,me03c,me03j,clark05,greenwald06,feather08}. 
The premise of treatment learning is that within the space of possible
decisions, there exist a small number of $key$ decisions that
determine all others.  The rest of this section expands on this notion
of $keys$, and their implications.
\subsection{What are ``keys''?}
Imagine that a model supports
chains of {\em reasons} that link inputs 
to desired goals. 
Some links in the chain clash with others, and some of those clashes
are most upstream; i.e. are not dependent on other clashes. 
In the following chains of reasoning 
the clashes are $\{e \neg e\}$, 
$\{g \neg g\}$ 
\& $\{j,\neg j\}$;
item 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}
\]
One
way to optimizing decision making about this model would be to first
decide about the non-dependent clashing links. 
We call these decisions {\em the collars}
since, as we shall see, they have most impact on the rest of the model.

For example, returning to the above reasoning chains,
any of $\{a, b, ..q\}$ is subject to discussion.
However, much of this model is irrelevant to the task of
$input_i\vdash~goal$. For example, 
the $\{e, \neg e\}$ clash is
not exercised in the context of 
the inputs to the above model.
In the context of reaching some $goal$ from 
$input_i$, the only important discussions are
the clashes $\{g,\neg g,j,\neg j\}$.
Further, since $\{j, \neg
j\}$ are fully dependent on $\{g,\neg g\}$, then the core decision
must be about variable $g$ with two disputed values: true and
false. 

We call 
$g$ 
the {\em collar} since it restricts everything else.
The collar may be internal to a model and so may not be directly controllable. A model's $keys$
are the controllable variables that influence the collar.
In this example, those keys are $input_i$.

Using the keys to setting the $collars$ reduces the number of reachable  states inside a model. 
Formally, the reachable states reduces to
just
the cross-product of all the ranges of the collars.
We call this the $clumping$ effect;
i.e. only a small fraction of the possible states are the reachable states.
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\}$.

\subsection{Theoretical Evidence}

Theoretically, clumps and  collars are  
the expected average case properties of any model. 
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 be observed to clump;
i.e. a small 
fraction of states to cover a large portion of the total 
probability space, with the remaining states having
negligible probability. 

Menzies \& Singh~\cite{me03l} 
computed the odds of a system selecting solutions
to goals using complex, or simpler, sets of preconditions.
In their
simulations they found that, at a very high probability,
a system will naturally select for tiny
sets of preconditions (a.k.a. the keys).
The Menzies \& Singh result means, in theory, that search engines can be greatly simplified since they
need only explore for a small number of variables that most effect the rest of the system.
The KEYS system discussed in this paper is a perfect example of how simple a search engine can be,
yet still be effective. In this regard, the Menzies \& Singh paper~\cite{me03l} can be viewed as the
{\em theory} and this paper the {\em practical application} of the theory.



\subsection{Empirical Evidence}
There is much empirical evidence for the validity of these theoretical predictions.
Keys, collars and clumps have been widely reported (albeit by different names).
A sample of those empirical results are offered below (for more, see~\cite{me03l}),

{\em Keys:} 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 that
in numerous datasets, as few as 20\% of the variables are $key$- the remaining
80\% of variables can be ignored 
without degrading a learner's classification accuracy. 

{\em Clumps:} Druzdzel~\cite{druzdel94}
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
525,312 possible internal 
states, he found that only one state was ever reached  52\% of the time and only 49
states were reached 91\% of the time.  

{\em Collars:} 
Williams et.al.~\cite{williams03} discuss how
to use keys  (which they call ``back doors'') to optimize search.
They showed that setting the keys
can reduce
the solution time of some hard problems from exponential to polytime- provided that the
keys can be cheaply located- an issue on which Williams et.al. are curiously silent.

\subsection{Finding the keys}

A traditional  approach to key-based reasoning is to find the
funnels using some  dependency-directed backtracking tool such as
the ATMS~\cite{deKleer86} or HT4~\cite{me97a}. Dependency-directed
backtracking is very slow, both theoretically and in
practice~\cite{me97a}. Further, in the presence of narrow collars,
it may be unnecessary. There is no need to {\em search} for the
collar in order to {\em exploit} it. Any chain of reasoning to
goals must pass through the collars (by definition). Hence, all
that is required is to find variables that most influence 
the output score.

One way to find those most influential variables is
the
``lift'' heuristic implemented in the
TAR3 treatment learner~\cite{hu02,me07} using
a table of model output, each column being one input variable, and each
row being one run of the model.
An extra column adds $s_i$; i.e. the score assigned to the output of that
run by some oracle function. Assuming $X$ rows, and that the scores coming from
$|c|$ discrete values with frequency $c_i$, then
this table has a weighted  baseline score of 
$before= \sum_i^cs_ic_i/X$. 
A particular conjunction of variable values, called the treatment $Rx$
can be used to
select for 
some $Y \le X$ rows by rejecting 
all rows
inconsistent with $Rx$.  The scores in the
selected set contains $|d|$
discrete values with frequency $d_i$.
This selected subset has a weighted sum of
$after= \sum_i^ds_id_i/Y$ 

The $lift$ of $Rx$ is $\frac{after}{before}$.
The most influential variables are found in the treatments 
with most impact on improving the score distributions;
i.e. those with highest lift. To find those treatments:
\be
\item TAR3 creates one treatment from all
variable values;
\item These singleton treatments are sorted by lifts;
\item A $cache$ is created to hold the best treatments;
\item A single rule of size $Max$
is created by selecting randomly from the sorted list of variable
values, favoring those with higher lift. 
$Max$ is selected at random from 1 to some user-specified maximum value.
\item 
If the new rule has a lift within
the top $M$ treatments, add it to $cache$ (and if the cache has now
grown beyond size $M$, delete the worst lifting cached
rule).
\item After creating $N$ new rules, if $cache$ has changed,
goto 4. 
\item Otherwise, return the $cache$ of $M$ best treatments.
\ee
Typical values for $\{Max,M,N\}$  are $\{10,10,100\}$, respectively.

Formally, TAR3 is a stochastic minimal 
contrast learner for weighted classes~\cite{bay99,cai98}.
TAR3 uses a stochastic algorithm since that
 scales linearly on number of attributes
and size of training set~\cite{hu02}.
Also, in a result consistent with the prevalence  of $keys$,
TAR3's fast stochastic search
nearly always returns the same treatments as the slower deterministic search
of early versions of this algorithm~\cite{hu02}.
  \subsection{Experiments with Treatment Learning}

\begin{figure}[!b]
\centerline{\includegraphics[width=2.0in]{jpl.png}}
\caption{DDP results.}\label{fig:jpl}
\end{figure}

%\begin{wrapfigure}{r}{2in}
%\centerline{\includegraphics[width=2.0in]{jpl.png}}
%\caption{DDP results.}\label{fig:jpl}
%\end{wrapfigure}
\fig{jpl} shows one application of  TAR3~\cite{fea02a}
on a DDP models with  
99 possible mitigations; i.e.
$2^{99}\approx10^{30}$ possibilities.

After 10,000 random selections of the mitigations 
the resulting $costs$ (i.e. sum cost of the mitigations) and $benefits$
(i.e. number of attained requirements) are shown  
{\em below} the black line (top left) of \fig{jpl}. 
All the dots {\em above} this line represent high benefit, 
low-cost projects found by iterative applications of 
treatment learning
At each iteration, researchers gave the simulator's output to the treatment
learner. TAR3 scored these outputs using  the distance of the associated costs-benefits
to the ``sweet spot'' of maximum benefits and minimum costs (the top left corner of
\fig{jpl}). 
Researchers 
then imposed the top treatment found by TAR3 found onto
the simulator for subsequent iterations. 


In a result consistent with the DDP models having small $keys$,
TAR3 found 
30 (out of 99) mitigations that crucially affected 
cost-benefit. 
This means TAR3
also found $99 - 30 = 69$ arbitrary decisions that 
could be made with minimal software impact. 

Greenwald~\cite{greenwald06} benchmarked TAR3 against
simulated annealing~\cite{kirkpatrick83}.
TAR3 achieves the same cost-benefit
point as simulated annealing~\cite{kirkpatrick83}, but does so using $\approx \frac{1}{10}$-th the evaluations
and using $\approx \frac{1}{4}$-th  the constraints required by SA.
Up until this current paper, Greenwald's results where the high-water
mark in learning mitigations for DDP models.

\newpage
\section{KEYS: a Faster TAR3 for DDP}

While TAR3 is a useful tool, \fig{jpl} took 40 minutes to generate. Ideally,
our design advisors should run faster than designers could change their models;
i.e. orders of magnitude faster than TAR3.
Hence, we tried five techniques, discussed below:  
{\em greedy search}, 
{\em BORE}, 
{\em knowledge compilation}, and some {\em systems tricks}. 

\subsection{Greedy Search}

Step 6 of the TAR3 algorithm (described above) generates hundreds
of treatments, then prunes all but the best $M$.  KEYS was an
experiment in building one rule per variable, with no post-pruning.  
KEYS therefore runs much faster than TAR3.

KEYS
searches a space of $M$ 
mitigations in 
$M$ ``eras'' (large steps in the search space). Initially, mitigations are free
to take  any value. At each era, one more
mitigation is set to $M_i=X_j$, $X_j \in \{true,false\}$. 
Each era $e$ generates
a sets of $<input,score>$ as follows:
\be
\item[1a:]
$Selected[1{\ldots}(e-1)]$ are  settings from previous eras.
\item[1b:]
	$Guessed$ are randomly  selected values for   other mitigations.  
\item[1c:]
	$Input = selected \cup guessed$.
\item[1d:]
Call DDP to compute $score=ddp(input)$;
\ee
After 100 repeats of steps 1a,1b,1c,and 1d:
\bi
\item[2:] The 100 $score$s are divided into 10\% $best$ and 90\% $rest$. 
\item[3:]
The mitigation values in the $input$ sets are then scored using BORE
(described below).
\item[4:]
The top ranked mitigation value becomes a setting to
one more mitigation and is  stored in $selected[e]$.\ei
KEYS then moves to the era $e+1$ and repeats steps  1,2,3,4.
KEYS stops
when all mitigations have settings.  

KEYS slowest step is 1d; i.e. the call to DDP. 
For a model with 100 mitigations, this call is repeated 100*100=10,000 times.
We optimize step 1d using knowledge compilation (discussed below).

\subsection{BORE = \underline{B}est \underline{Or} \underline{R}est}

TAR3's lift calculation is a heuristic measure with no theoretical basis. It can favor
treatments based on very small portions of the training set. KEYS
uses an alternative Bayesian ranking measure, better founded in theory, and one that includes a 
support measure.

BORE~\cite{clark05} assumes that the output scores are divided into 
one class for $best$ outcomes and one for the $rest$.
In such a two-class systems, TAR3's lift calculation
can be replaced with a search for mitigation values that have a high probability
of belonging to $best$.

BORE divides numeric scores seen in $K$ runs
into  $best$ and $rest$, storing the top 10\% and the remaining 90\% scores (respectively). 
It 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 a  posteriori  probability
$P(H|E)=P(E|H) P(H)\; /\; P(E)$.
Such simple  Bayes classifiers are often called ``n\aive'' since they assume
independence of each variable. 
Domingos and Pazzani show 
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that seemingly n{\aive} Bayes classifiers perform as well
as other more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).

When applying the theorem, {\em likelihoods}
are computed from observed
frequencies, then normalized to create
probabilities (this normalization cancels out $P(E)$ in Bayes theorem).
For example, after $K=10,000$ runs divided into  1,000 {\em best} solutions 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
Previously~\cite{clark05}
we have found that  Bayes theorem
is a poor ranking heuristic
since it is distracted by low frequency evidence.
For example, note how
the probability of $E$ belonging to the best class
is moderately high even though its support is very low; i.e. $P(best|E)=0.66$ but
$freq(E|best) = 0.01$. 

To avoid such unreliable low frequency evidence, we augment \eq{ten}
with a support term.
Support should $increase$ as the frequency of a value $increases$,  i.e. 
$like(best|E)$ is a valid support measure.
 Hence, step 3 of our greedy search ranks values  via
\begin{equation}\label{eq:ps}\small
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}

\subsection{Knowledge Compilation}

In knowledge compilation, a theory is compiled off-line into a target 
language, which is then used on-line to answer a large number of queries, 
very rapidly~\cite{selman96knowledge,darwiche02}.
The 
motivation behind knowledge compilation is to push as much of the computational overhead into 
the off-line compilation phase, which is amortized over numerous on-line queries;
e.g. 
the thousands  of calls to the DDP
models made by step 1d of the greedy search.

The SE and AI literature has thus far focused mostly on 
target compilation languages which are combinations of one or more 
combinations of conjunctive normal form, state machines, or 
binary decision diagrams~\cite{darwiche02,biere99:bmc}.
For our purposes, it was convenient not to use
declarative forms. Instead,
our  knowledge compiler outputs a ``C'' function.

This knowledge compiler computes and caches a flattened form of the
 the DDP requirements tree. In standard DDP:
\bi
\item 
Requirements form a tree;
\item
The relative influence of each leaf requirement is computed via
a depth-first search from the root down to the leaves.  
\item
This computation is repeated each time the relative influence of a requirement is required.
\ei
In our 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 risks
on requirements).

Our knowledge compiler converts this trivial DDP model into the {\tt model}  function 
of \fig{ddpExample}. Note that
The topology of the network is represented as terms in equations
at the bottom of the function. As the topology grows more complex, 
so do these equations. For example,
our biggest model, containing 99 mitigations, generates 1412 lines of {\tt model}.

The {\tt model} function is called by step 1d of the greedy search
and 
an array of boolean mitigations {\tt m[]}. It
returns the total cost of the selected mitigations ({\tt *cost}) and the
number of reachable requirements  ({\tt *att}).
These two scores are then normalized to a single score $s$ representing the distance
to the ``sweet spot'' of maximum benefits and minimum costs, as follows:
\[
s=1 - \frac{\sqrt{((1-\overline{cost})^2 + \overline{att}^2}}{\sqrt{2}}
\]
Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Hence, our scores ranges $0 \le s \le 1$ and
{\em higher} scores are {\em better}.

The form of \fig{ddpExample} is not optimal.
Observe that all the computation
in  lines 5 to 28 
is always the same, regardless of what
values are passed in with the {\tt m[]} array.
Hence, in future versions of this tool, it might be
wise to split the {\tt model} function into a
{\tt model-setup} function (that only gets called once)
and a {\tt model-run} function that uses variables
set up by {\tt model-setup}.

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
     1	#include "tool.h"
     2	
     3	void model(float *cost, float *att, float m[]) 
     4  {
     5	  float costTotal, attTotal;
     6	  int oCount = 2;
     7	  float oWeight[oCount+1];
     8	  float oAttainment[oCount+1];
     9	  float oAtRiskProp[oCount+1];
    10	  int rCount = 1;
    11	  float rAPL[rCount+1];
    12	  float rAggrevatedImpact[rCount+1];
    13	  float rLikelihood[rCount+1];
    14	  int mCount = 1;
    15	  int m[mCount+1];
    16	  float mCost[mCount+1];
    18	  float roImpact[rCount+1][oCount+1];
    19	  float mrEffect[mCount+1][rCount+1];
    20	  mCost[1] = 10000;
    21	  rAPL[1] =1;
    22	  rAggrevatedImpact[1]=1;
    23	  oWeight[1]=100;
    24	  oWeight[2]=100;
    25	  roImpact[1][1] = 0.1;
    26	  roImpact[1][2] = 0.99;
    27	  mrEffect[1][1] = 0.9;
    28	  rLikelihood[1] = rAPL[1];
    29	  /* Mitigation effects on Risk likelihoods */
    30	  rLikelihood[1] = rLikelihood[1] * 
    31	                   (1 - m[1] * mrEffect[1][1]);
    32	  /*Risk impacts on Objective attainment proportions*/
    33	  oAtRiskProp[1] = (rLikelihood[1] * 
    34	       rAggrevatedImpact[1] * roImpact[1][1]);
    35	  oAtRiskProp[2] = (rLikelihood[1] * 
    36	       rAggrevatedImpact[1] * roImpact[1][2]);
    37	  /* Objective attainments */
    38	  oAttainment[1] = oWeight[1] * 
    39	            (1 - minValue(1, oAtRiskProp[1]));
    40	  oAttainment[2] = oWeight[2] * 
    41	            (1 - minValue(1, oAtRiskProp[2]));
    42	  attTotal = oAttainment[1] + oAttainment[2];
    43	  costTotal = m[1] * mCost[1];
    44	  
    45	  *cost = costTotal;
    46	  *att = attTotal;  
    47 }
\end{verbatim}}
~\hrule~
\caption{A trivial DDP model}
\label{fig:ddpExample}
\end{figure}

This knowledge compiler is not just an algorithms optimization tool. It is also a method that
lets JPL retain proprietary    information
while allowing  researchers outside of JPL
to access JPL models. 
The resulting models are anonymized to conceal 
proprietary information, while retaining their
computational nature. 
In our experiments, JPL ran the knowledge compiler and passed
to West Virginia University models like those shown in
\fig{ddpExample}.
Consequently, JPL could assure
its clients that their secrets were safe while, at the same time, allowing
researchers outside of JPL to perform experiments like those shown in this paper.


\subsection{Systems Tricks}

The results of \fig{jpl} where generated using
a Visual Basic version of  DDP and a ``C'' version of TAR3.
These  ran as separate processes
communicating via shell scripts and temporary files. 
KEYS employs some systems tricks to optimize that rig.

KEYS  runs a {\tt make} file to 
build one ``C'' program containing the greedy search, BORE, and the {\tt model}
generated by the knowledge compiler. This single executable runs in RAM.
Consequently:
\bi
\item The slower Visual Basic code is replaced by faster ``C'' code;
\item
The learner and the model can 
communicate without time consuming disc I/O.
\ei
%\begin{figure*}[!t]
%~\hrule~
%{\scriptsize
%\begin{verbatim}
%#include "tool.h"
%
%void model(float *cost, float *att, float m[])
%{
%        float costTotal, attTotal;
%        int oCount = 3;
%        float oWeight[oCount+1];
%        float oAttainment[oCount+1];
%        float oAtRiskProp[oCount+1];
%        int rCount = 2;
%        float rAPL[rCount+1];
%        float rAggrevatedImpact[rCount+1];
%        float rLikelihood[rCount+1];
%        int mCount = 3;
%        float mCost[mCount+1];
%        float roImpact[rCount+1][oCount+1];
%        float mrEffect[mCount+1][rCount+1];
%        mCost[1]= 11;
%        mCost[2]= 22;
%        mCost[3]= 0;
%        rAPL[1]=0.4;
%        rAggrevatedImpact[1]=1;
%        rAPL[2]=1;
%        rAggrevatedImpact[2]=1;
%        oWeight[1]=1;
%        oWeight[2]=2;
%        oWeight[3]=3;
%        roImpact[1][1] = 0.1;
%        roImpact[1][2] = 0.3;
%        roImpact[2][1] = 0.2;
%        mrEffect[1][1] = -0.2;
%        mrEffect[2][1] = 0.1;
%        mrEffect[3][1] = -1.7;
%        mrEffect[1][2] = 0.3;
%        rLikelihood[1] = rAPL[1];
%        rLikelihood[2] = rAPL[2];
%        /* Mitigation effects on Risk likelihoods */
%        /* Phase 1 Mitigation effects */
%        rLikelihood[1] = minValue(1, (rLikelihood[1] - m[1] * mrEffect[1][1]));
%        rAggrevatedImpact[1] = rAggrevatedImpact[1] * (1 - m[3] * (1 + mrEffect[3][1]));
%        rLikelihood[2] = rLikelihood[2] * (1 - m[1] * mrEffect[1][2]);
%        /* Phase 2 Mitigation effects */
%        rLikelihood[1] = rLikelihood[1] * (1 - m[2] * mrEffect[2][1]);
%        /* Phase 3 Mitigation effects */
%        /* Risk impacts on Objective attainment proportions */
%        oAtRiskProp[1] = (rLikelihood[1] * rAggrevatedImpact[1] * roImpact[1][1]) + \
%                     (rLikelihood[2] * rAggrevatedImpact[2] * roImpact[2][1]);
%        oAtRiskProp[2] = (rLikelihood[1] * rAggrevatedImpact[1] * roImpact[1][2]);
%        oAtRiskProp[3] = 0;
%        /* Objective attainments */
%        oAttainment[1] = oWeight[1] * (1 - minValue(1, oAtRiskProp[1]));
%        oAttainment[2] = oWeight[2] * (1 - minValue(1, oAtRiskProp[2]));
%        oAttainment[3] = oWeight[3] * (1 - minValue(1, oAtRiskProp[3]));
%        attTotal = oAttainment[1] + oAttainment[2] + oAttainment[3];
%        costTotal = m[1] * mCost[1] + m[2] * mCost[2] + m[3] * mCost[3];
%
%        *cost = costTotal;
%        *att = attTotal;
%}
%\end{verbatim}}
%~\hrule~
%\caption{model3.c}
%\label{fig:model3}
%\end{figure*}
%
%
%\section{KEYS Approach for DDP Models}
%
%The KEYS approach is a method of optimizing a DDP model by controlling
%the values of mitigations. Since each mitigation has a value of \textit{on} or \textit{off},
%there are $2^m$ possible combinations of mitigations
%that must be considered for $m$ mitigations. However, using KEYS, we consider $c*m$ combinations
%where $c$ is a constant (usually set to 100). It is clear that KEYS requires much fewer CPU cycles,
%especially for large number of mitigations used in JPL's DDP models.
%On average, KEYS is 200,000 times faster than the current tool used in JPL
%to optimize DDP models while offering better results.
%
%\begin{figure}[!t]
%~\hrule~\\
%
%\textbf{Input}: DDP model with $m$ mitigations\\
%\textbf{Output}: total cost and total attainment\\
%\textbf{Constant}: $c$ = number of runs\\
%{\small
%\begin{verbatim}
%for era in 1..m
%   for run in 1..c
%      for each mitigation i
%         if (i is not fixed)
%            choose a random value of 0 or 1 for i
%      calculate total cost and total attainment
%
%   normalize the results of all runs
%   find their distance from (cost=0,attainment=1)
%
%   for each non-fixed mitigation i
%      score i's distance using x% best or rest
%
%   rank non-fixed mitigations
%   fix the highest ranking mitigation
%\end{verbatim}}
%
%~\hrule~
%\caption{KEYS's Algorithm}
%\label{ddpAlgo}
%\end{figure}
%
%KEYS's algorithm is described in Figure~\ref{ddpAlgo}. There are a few points
%about how this algorithm works:
%\begin{itemize}
%\item The Euclidean distance of each combination of mitigations is measured from a 
%\textit{sweet spot}. In a two dimensional space, this spot is located at $(cost,attainment) = (0,1)$.
%\item To score each mitigation, \textit{on} and \textit{off} values are treated individually.
%Therefore, for $x <= m$ non-fixed mitigations, we obtain $2*x$ scores.
%\item We use the best or rest method for scoring. Each \textit{on} (or \textit{off}) mitigation
%has two counts: \textit{best} and \textit{rest}. If its distance is in the top x\%, the \textit{best} count is incremented by one.
%Otherwise, the \textit{rest} count is incremented by one.
%\item The score of each mitigation's value is calculated using $best^2/(best+rest)$.\footnote{Note to Tim: needs explanation.}
%\item The $2*x$ scores are sorted and the highest score determines the mitigation (and its value) that
%will be fixed in the rest of the runs.
%\item In each era, one mitigation is fixed, requiring a total of $m$ eras.
%\end{itemize}
%
%KEYS's algorithm is faster than current practices in JPL for optimizing DDP models for several reasons:
%\begin{itemize}
%\item KEYS requires fewer computations due its smaller search space which makes use of
%a locally guided search space (unlike TAR2). The complete
%search space consists of $2^m$ combination of mitigations. Therefore, it is exponential.
%KEYS is polynomial in the number of mitigations, $m$, and its constant, $c$, can be adjusted 
%to smaller values if needed.
%\item The current methods such as simulated annealing and TAR2 do not 
%search the whole space either (although they may require more computations). 
%Nonetheless, they have slower algorithms due to their design that uses 
%multiple IO cycles to learn the model and adjust it repeatedly using files. 
%KEYS's algorithm is completely processed in RAM.
%\item KEYS uses the output model in C syntax that is compiled into ZZZ's code.
%Before, the model was built in Visual Basic as a tree
%that worked out the relative importance of each node by calling up the tree.
%\end{itemize}
%

\begin{figure}[!b]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|c|c|} \hline
Model&LOC&Objectives&Risks&Mitigations&Run-Time*\\ \hline
model1.c&  43  &3         &2    &2          &0.0018   \\ \hline
model2.c& 260   &1         &30   &31         &0.0139   \\ \hline
model3.c& 58   &3         &2    &3          &0.0019   \\ \hline
model4.c& 1226   &50        &31   &58         &0.0906   \\ \hline
model5.c&1412    &32        &70   &99         &0.1751   \\ \hline
\end{tabular}
\end{center}
{\small *average over 100 runs (in seconds)}
\caption{Details of Five DDP Models. }
\label{fig:ddpModels}
\end{figure}

\begin{figure}[!b]
\begin{center}
\includegraphics[width=2.3in]{cost.pdf}
\includegraphics[width=2.3in]{att.pdf}
\end{center}
\caption{KEYS running on model 5.} 
\label{fig:medianSpread}
\end{figure}


\section{Results}

KEYS was run on the five JPL requirements models.
As shown in \fig{ddpModels}
models one and three were relatively small and were used to debug KEYS.
Models two, four, and five
are more interesting.
Model 4 was discussed in~\cite{me03n} in detail. 
The largest, model5 was processed previously by DDP/TAR4~\cite{fea02a}.

The cost-benefits obtained by KEYS were very similar to (or better than)
those found by simulated annealing and TAR3. 
Also, KEYS found those solutions very quickly.
KEYS' runtimes (last column of 
\fig{ddpModels}) are quite fast: always less than a second, sometimes much less.
Better yet, these times are much faster than with TAR3.  For example, TAR3
took 40 minutes to process model5 as compared to KEYS' 
0.18 seconds ($\frac{0.18}{40*60} \approx  10^4$ times faster).

A typical run of KEYS is shown in \fig{medianSpread} (these are results from model5).
At $era=0$, all mitigations are selected at random. At each era after that, one more
mitigation is set to true or false. The upper/lower lines in each plot shows median/spread
values seen in 100 calls to model5 at each era. Here, ``median'' is the 50\% percentile
value and ``spread'' is a measure of deviation around the median (calculated as
75\% percentile value - median). Note that
 the deviations are quite small, compared to the median. That is, our median estimates
are good descriptions of the central tendencies of these models.
Also,  KEYS reduced the cost while increasing the
attainment. Model5 was the exception: attainment remained steady while the cost was
greatly reduced. 

In \fig{medianSpread},
the improvements in cost are dramatic up until era=30, after which improvements
are much slower. If management wanted a parsimonious set of mitigations, they could
hence use the true/false values in the mitigations from eras 0 to 30. 



\section{Discussion}
\begin{raggedleft}
{\em 
Perfection is achieved not when there is \\
nothing more to add, but rather when\\
 there is nothing more to take away.\\
 -- Antoine de Saint-Exupéry }

\end{raggedleft}

~\\

Our results call to mind the
``simplicity-first'' recommendations of Holte~\cite{holte93}. 
Sophistication is
superfluous if simpler methods perform as well as complex methods.
Working
with tree-based classification learners, Holte found that extremely
small trees were often as accurate as more complex trees.
He hence cautioned the machine
learning community to benchmark their supposedly more sophisticated
algorithms  against simpler alternatives. 

This study has compared  a simple method (KEYS) with a more
complex method (TAR3) for solving DDP problems.
 Not only were the cost-benefit results competitive
with (or better than) 
prior results but the simpler method ran orders of magnitude
($10^4$) times faster than the complex one.

We attribute most of the  success of KEYS to 
the presence of $keys$ in the DDP models; i.e. a small set of variables that
set everything else.  These key variables were exploited using two methods:
\be
\item[1.] BORE finds promising keys with high support;
\item[2.] KEYS' greedy search sets the most promising key,
before exploring the remaining options;
\ee
We also employed three other methods:
\be
\item[3.] Before we used Visual Basic and ``C''. KEYS just uses ``C''.
\item[4.] KEYS avoids the disk I/O needed by TAR3 talking to DDP.
\item[5.]
Our knowledge compiler transforms the DDP requirements tree into a set of equations
that can be rapidly evaluated.
\ee

\section{Future Work}

It is unclear which of the above five factors was most influential in speeding up KEYS.
In future work, we would like to explore $2^5=32$ variants of KEYS
that disable some combination of the 
above five methods. Note that such an exploration is not required to validate this work-
only to isolate the most important features of this implementation which we should
retain in all future work.

More importantly, it is important that KEYS runs faster.
While the current tools is certainly fast enough for most of the
 current generation of DDP models,
in the very near future, it needs to run much faster. 
As soon as we give our users 
more elaborate model-based design tools, they try to build more elaborate designs.
Also, as mentioned in the introduction, they want to see a complete analysis of all
older designs.
Even the $10^4$  fold increase in the processing
of model5 is not fast enough to handle the requirements models expected in the near future;
or the complete set of all past requirement models.

For example, often, families of models are proposed and 
model-based design methods are asked
to assess which subset of, say, 12 alternatives should be used.  
Allowing 0.2 seconds for each of these $2^{12}$ models, this would take thirteen
minutes to
process. Ideally, we seek two second response time (or less) in order to keep up
with interactive design discussions. 
That is, we need at least to run at least 1000 times
faster, just to keep up some of the larger design discussions we plan to support in the
near future.

Also,
if we want to scale KEYS to more  models with a more complex ontology, 
then some modifications may be required.
This paper has shown that KEYS has promise for
 models with binary variables. However, in other work,
we have seen disappointing
results with models containing variables with much larger ranges.

One approach to speeding up KEYS is to do as much work as possible
{\em before} the model is run. In \S4.3, there was some comment
along those lines (recall the discussion on splitting the {\tt model} function
into {\tt model-setup} and {\tt model-run}). 

More generally, there might be
a better internal format for the model than ``C''.
The latest generation of stochastic SAT solvers 
(e.g. MAXWALKSAT~\cite{kautz97} or 
the optimized Markov Logic reasoning within
ALCHEMY~\cite{rich05}) use conjunctive normal form. 
KEYS could be a useful sub-routine of these stochastic tools.
For example,
stochastic algorithms like  MAXWALKSAT and the optimizations inside ALCHEMY
all make random choices. Perhaps KEYS could be used to bias random choices
towards values that might be part of the $keys$. The effects of such an optimization
could be dramatic- recall from the above discussion that Williams et.al.~\cite{williams03}
report that setting ``back doors'' (the keys) can reduce the solution time of hard problems
from exponential time to polytime.


\section{Summary}
\noindent
In this work we have:
\bi
\item
Described five public-domain real-world requirements models, stored in the
PROMISE repository;
\item
Showed how new methods (KEYS) improve on older ones (TAR3);
\item
Defined baseline results on the new methods (see \fig{ddpModels});
\item
Proposed a challenge problem for improving these methods (three orders of magnitude faster than
\fig{ddpModels}).
\item 
Offered some suggestions on how to meet that challenge (stochastic search methods like  MAXWALKSAT
or ALCHEMY, possibly augmented by KEYS to better bias their random selections).
\ei
We would welcome
collaborations with the PROMISE community
on methods to speed up solutions to DDP optimization problem.

Finally, all the software used in this study 
is  free for download and use\footnote{See 
\url{http://unbox.org/wisp/tags/keys/1.0}}. We recommend that, where possible,
other PROMISE authors offer their results in such a repeatable and improve-able manner.

\bibliographystyle{abbrv}
%\bibliography{refs} 

\begin{thebibliography}{10}

\bibitem{akao90}
Y.~Akao.
\newblock {\em Quality Function Deployment}.
\newblock Productivity Press, Cambridge, Massachusetts, 1990.

\bibitem{hailpern06}
b.~hailpern and p.~tarr.
\newblock model-driven develpment: the good, the bad, and the ugly.
\newblock {\em ibm systems journal}, 45(3):451--461, 2006.

\bibitem{bay99}
S.~Bay and M.~Pazzani.
\newblock Detecting change in categorical data: Mining contrast sets.
\newblock In {\em Proceedings of the Fifth International Conference on
  Knowledge Discovery and Data Mining}, 1999.
\newblock Available from
  \url{http://www.ics.uci.edu/~pazzani/Publications/stucco.pdf}.

\bibitem{biere99:bmc}
A.~Biere, A.~Cimatti, E.~M. Clarke, and Y.~Zhu.
\newblock Symbolic model checking without bdds.
\newblock In {\em In Proceedings of Tools and Algorithms for the Analysis and
  Construction of Systems}, page 193207, May 1999.

\bibitem{brown06}
A.~Brown, S.~Iyengar, and S.~Johnston.
\newblock A rational approach to model-driven development.
\newblock {\em IBM Systems Journal}, 45(3):463--480, 2006.

\bibitem{cai98}
C.~Cai, A.~Fu, C.~Cheng, and W.~Kwong.
\newblock Mining association rules with weighted items.
\newblock In {\em Proceedings of International Database Engineering and
  Applications Symposium (IDEAS 98)}, August 1998.
\newblock Available from
  \url{http://www.cse.cuhk.edu.hk/~kdd/assoc_rule/paper.pdf}.

\bibitem{me03j}
E.~Chiang and T.~Menzies.
\newblock Simulations for very early lifecycle quality evaluations.
\newblock {\em Software Process: Improvement and Practice}, 7(3-4):141--159,
  2003.
\newblock Available from \url{http://menzies.us/pdf/03spip.pdf}.

\bibitem{clark05}
R.~Clark.
\newblock Faster treatment learning, {C}omputer {S}cience, {P}ortland {S}tate
  {U}niversity.
\newblock Master's thesis, 2005.

\bibitem{corn01}
S.~Cornford, M.~Feather, and K.~Hicks.
\newblock {DDP} a tool for life-cycle risk management.
\newblock In {\em IEEE Aerospace Conference, Big Sky, Montana}, pages 441--451,
  March 2001.

\bibitem{darwiche02}
A.~Darwiche and P.~Marquis.
\newblock A knowledge compulation map.
\newblock {\em Journal of Artifical Intelligence Research}, 17:229--264, 2002.
\newblock Available from \url{ww.jair.org/media/989/live-989-2063-jair.pdf}.

\bibitem{deKleer86}
J.~DeKleer.
\newblock An {A}ssumption-{B}ased {TMS}.
\newblock {\em Artificial Intelligence}, 28:163--196, 1986.

\bibitem{domingos97optimality}
P.~Domingos and M.~J. Pazzani.
\newblock On the optimality of the simple bayesian classifier under zero-one
  loss.
\newblock {\em Machine Learning}, 29(2-3):103--130, 1997.

\bibitem{druzdel94}
M.~Druzdzel.
\newblock Some properties of joint probability distributions.
\newblock In {\em Proceedings of the Tenth Annual Conference on Uncertainty in
  Artificial Intelligence (UAI-94)}, pages 187--194, 1994.
\newblock Available from
  \url{http://www.pitt.edu/AFShome/d/r/druzdzel/public/html/abstracts/uai94.ht%
ml}.

\bibitem{feather08}
M.~Feather, S.~Cornford, K.~Hicks, J.~Kiper, and T.~Menzies.
\newblock Application of a broad-spectrum quantitative requirements model to
  early-lifecycle decision making.
\newblock {\em IEEE Software}, 2008.
\newblock Available from \url{http://menzies.us/pdf/08ddp.pdf}.

\bibitem{fea02a}
M.~Feather and T.~Menzies.
\newblock Converging on the optimal attainment of requirements.
\newblock In {\em IEEE Joint Conference On Requirements Engineering ICRE'02 and
  RE'02, 9-13th September, University of Essen, Germany}, 2002.
\newblock Available from \url{http://menzies.us/pdf/02re02.pdf}.

\bibitem{greenfield04}
J.~Greenfield and K.~Short.
\newblock {\em Software factories : assembling applications with patterns,
  models, frameworks, and tools}.
\newblock Wiley Publishing, Indianapolis, IN, 2004.

\bibitem{greenwald06}
J.~Greenwald.
\newblock A novel metaheuristic search technique: Iterative treatment learning.
\newblock Master's thesis, Computer Science, Portland State University, 2007.
\newblock Available from
  \url{http://unbox.org/wisp/var/jeremy/Greenwald06Thesis.pdf}.

\bibitem{holte93}
R.~Holte.
\newblock Very simple classification rules perform well on most commonly used
  datasets.
\newblock {\em Machine Learning}, 11:63, 1993.

\bibitem{hu02}
Y.~Hu.
\newblock Treatment learning: Implementation and application.
\newblock Master's thesis, Department of Electrical Engineering, University of
  British Columbia, 2003.
\newblock Masters Thesis.

\bibitem{kautz97}
H.~Kautz, B.~Selman, and Y.~Jiang.
\newblock A general stochastic approach to solving problems with hard and soft
  constraints.
\newblock In D.~Gu, J.~Du, and P.~Pardalos, editors, {\em The Satisfiability
  Problem: Theory and Applications, New York, NY}, pages 573--586, 1997.
\newblock Available on-line at \url{http://citeseer.ist.psu.edu/168907.html}.

\bibitem{kirkpatrick83}
S.~Kirkpatrick, C.~D. Gelatt, and M.~P. Vecchi.
\newblock Optimization by simulated annealing.
\newblock {\em Science, Number 4598, 13 May 1983}, 220, 4598:671--680, 1983.

\bibitem{kohavi97}
R.~Kohavi and G.~H. John.
\newblock Wrappers for feature subset selection.
\newblock {\em Artificial Intelligence}, 97(1-2):273--324, 1997.

\bibitem{me02c}
T.~Menzies, E.~Chiang, M.~Feather, Y.~Hu, and J.~Kiper.
\newblock Condensing uncertainty via incremental treatment learning.
\newblock In T.~M. Khoshgoftaar, editor, {\em Software Engineering with
  Computational Intelligence}. Kluwer, 2003.
\newblock Available from \url{http://menzies.us/pdf/02itar2.pdf}.

\bibitem{me97a}
T.~Menzies and P.~Compton.
\newblock Applications of abduction: Hypothesis testing of
  neuroendocrinological qualitative compartmental models.
\newblock {\em Artificial Intelligence in Medicine}, 10:145--175, 1997.
\newblock Available from \url{http://menzies.us/pdf/96aim.pdf}.

 \vfill\eject
\bibitem{me03c}
T.~Menzies and Y.~Hu.
\newblock Data mining for very busy people.
\newblock In {\em IEEE Computer}, November 2003.
\newblock Available from \url{http://menzies.us/pdf/03tar2.pdf}.

\bibitem{me07}
T.~Menzies and Y.~Hu.
\newblock Just enough learning (of association rules): The {TAR2} treatment
  learner.
\newblock In {\em Artificial Intelligence Review}, 2007.
\newblock Available from \url{http://menzies.us/pdf/07tar2.pdf}.

\bibitem{me03n}
T.~Menzies, J.~Kiper, and M.~Feather.
\newblock Improved software engineering decision support through automatic
  argument reduction tools.
\newblock In {\em SEDECS'2003: the 2nd International Workshop on Software
  Engineering Decision Support (part of SEKE2003)}, June 2003.
\newblock Available from \url{http://menzies.us/pdf/03star1.pdf}.

\bibitem{me03l}
T.~Menzies and H.~Singh.
\newblock Many maybes mean (mostly) the same thing.
\newblock In M.~Madravio, editor, {\em Soft Computing in Software Engineering}.
  Springer-Verlag, 2003.
\newblock Available from \url{http://menzies.us/pdf/03maybe.pdf}.

\bibitem{rich05}
M.~Richardson and P.~Domingos.
\newblock Markov logic networks, February 206.

\bibitem{selman96knowledge}
B.~Selman and H.~Kautz.
\newblock Knowledge compilation and theory approximation.
\newblock {\em Journal of the ACM}, 43(2):193--224, 1996.
\newblock Available from
  \url{http://citeseer.nj.nec.com/article/selman96knowledge.html}.

\bibitem{sendall03}
S.~Sendall and W.~Kozacaynski.
\newblock Model transformation: The heart and soul of model-driven software
  development.
\newblock {\em IEEE Software}, 20(5):42--45, Sept.-Oct. 2003.

\bibitem{simon96}
H.~Simon.
\newblock {\em The Science of the Artificial (third edition)}.
\newblock MIT Press, 1996.

\bibitem{waddington03}
D.~Waddington and P.~Lardieri.
\newblock Model-centric software development.
\newblock {\em IEEE Computer}, 39(2):28--29, February. 2006.

\bibitem{williams03}
R.~Williams, C.~Gomes, and B.~Selman.
\newblock Backdoors to typical case complexity.
\newblock In {\em Proceedings of IJCAI 2003}, 2003.
\newblock \url{http://www.cs.cornell.edu/gomes/FILES/backdoors.pdf}.

\end{thebibliography}
\end{document}
