\documentclass[global,twocolumn]{svjour}
\journalname{Annals of Software Engineering, special issue on
Computational Intelligence. To appear.\\}
\date{WP ref: 02/annals. \today}
%\documentclass[twoside,twocolumn]{ase}

%\documentclass[11pt]{article}\renewcommand{\baselinestretch}{1.62}

\topmargin -1cm

%\usepackage{../../tex/syntax}
%\usepackage{../../tex/cite}
\usepackage{syntax,cite,bar}
\usepackage{color,ifthen,times,alltt,url,graphicx,amssymb}
%\usepackage{../../tex/lineno}\runninglinenumbers\modulolinenumbers[10]

%\documentstyle[alltt,icse2000,twocolumn,url,bar,epsfig,times,alltt,array,amssymb,graphicx,ifthen,color]{article}

% Changes:
%  Page limit: 10 pages
%  Abstract limit: 200 words
%  Contact information is now gall@infosys.tuwien.ac.at
%  URL for author kit changed: needs to be filled in.
%  All other font and sizing information is the same:
%    check whether it still applies.


%\makeatletter
%\def\fnum@figure{\sffamily\figurename~\thefigure}
%\def\fnum@table{\sffamily\tablename~\thetable}
%\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{code}{\begin{alltt}\small}{\normalsize\end{alltt}}

\newenvironment{ccode}{\begin{code}\begin{center}}{\end{center}\end{code}}

\begin{document}

\newcommand{\sq}[2]{%
    \definecolor{thiscol}{gray}{.#2}%
        \ifthenelse{#2<50}%
            {\color{white}}%
            {\color{black}}%
        \colorbox{thiscol}{\makebox[2em]{#1}}}


\title{Condensing Uncertainty via Incremental
Treatment Learning}

%XXX add that inc chart

\author{  Tim Menzies\inst{1}
\and Eliza Chiang\inst{2}, Martin Feather\inst{3}, Ying Hu\inst{2}
\and James D. Kiper\inst{4}}

\institute{ Lane Department of Computer Science,
       University of West Virginia,
       PO Box 6109, Morgantown,
       WV, 26506-6109, USA;\\ \url{http://tim.menzies.com}; \email{
tim@menzies.com} \and
 Electrical  \& Computer Engineering
University of British Columbia;
\email{yingh@ece.ubc.ca;echiang@interchange.ubc.ca} \and
 Jet Propulsion Laboratory, California Institute of Technology;
 \email{Martin.S.Feather@Jpl.Nasa.Gov}
\and Computer Science \& Systems Analysis, Miami University;
\email{kiperjd@muohio.edu}}

\newcommand{\DO}  {{\sffamily \{}}
\newcommand{\FOR}{{\underline {\sffamily for}}}
\newcommand{\DONE}{ {\sffamily \}}}
\newcommand{\IF}{{\underline {\sffamily if}}}
\newcommand{\FI}{{\underline {\sffamily fi}}}
\newcommand{\THEN}{{\underline {\sffamily then}}}
\newcommand{\ELSE}{{\underline {\sffamily else}}}
\newcommand{\WHEN}{{\underline {\sffamily when}}}
\newcommand{\UNTIL}{{\underline {\sffamily until}}}
\newcommand{\AND}{{\underline {\sffamily and}}}
\newcommand{\TO}{{\underline {\sffamily to}}}
\newcommand{\IS}{ {\sffamily $\leftarrow$}}

\newcommand{\NIL}{ {\sffamily $\emptyset$}}
\newcommand{\REPEAT}{{\underline {\sffamily repeat}}}
\newcommand{\RETURN}{{\underline {\sffamily return}}}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\shortverb{!}


\maketitle
%\copyrightspace
%
% If you want to print drafts of the paper with a draft
% notice in the copyright space, comment out the \copyrightspace
% line above and include the \submitspace line below instead.
%
%\submitspace{Draft of paper submitted to ASE 2000.
%\\WP:b/00/ase/whatif(\today).}


% Page number on the initial page can be omitted in both the review and
% final submission (and should be removed in the final submission).  The
% line below does that.

\thispagestyle{empty}  % suppresses page number on first page

% In the review submission, page numbers should appear (they can be omitted
%  from the first page).  The pagestyle command below puts them in.
% In the final submission of accepted papers, page numbers should be
%  omitted; remove or comment out the pagestyle line below to omit them.

\pagestyle{plain}

\begin{abstract}
 Models
constrain the range of possible behaviors defined for a domain.
When parts of a model are uncertain, the possible behaviors may be
a {\em data cloud}: i.e. an overwhelming range of possibilities
that bewilder an analyst. Faced with  large data clouds, it is
hard to demonstrate that any particular decision leads to a
particular outcome.

%XXX in partnership with humans in an interaticve cycle

Even if we can't make definite decisions from such models, it is
possible to   find
decisions that reduce the variance of values within a data
cloud. Also, it is possible to change the range of these future
behaviors such that the cloud condenses to some improved mode.

Our approach uses two tools. Firstly, a model simulator is
constructed that knows the range of possible values for uncertain
parameters. Secondly, the TAR2 treatment learner uses the output
from the simulator  to incrementally learn better constraints. In
our {\em incremental treatment learning} cycle, users review newly
discovered treatments before they are added to a growing pool of
constraints used by the model simulator.
\end{abstract}


\section{Introduction}

Often, during early lifecycle decision making in software
engineering, analysts know the {\em space} of possibilities, but
not the {\em constraints} on that space. For example: \bi \item
They might know qualitatively that the {\em more} shared data, the
{\em less}  modifiable is a software system. However, they may not
know the exact quantitative values for this relationship. \item
Their experience might tell them that their source lines of code
estimates are inaccurate by 50\%. \ei

What are our analysts to do? One possibility is to demand more
budget and time to perform further analysis which removes these
uncertainties. For example,  metrics collection programs might be
commenced to collect values for  uncertain parameters. Elsewhere,
we have documented the impressive results that can come from such
a methodology/process~\cite{me00p}.

When elaborate metrics collection is too expensive however,
computational intelligence methods may be useful. If domain experts
can offer a rough description of how (e.g.) variable A effects
variable B, then fuzzy logic methods~\cite{elkan93,Zadeh1973a} can be
used to perform inference over the model, perhaps using the methods
of Jahnke et al.~\cite{jahnke97}. If the model represents a situation
for which we have historical data, then genetic algorithms can be
used to mutate the current model towards a model that best covers the
historical data~\cite{back91}. Alternatively, we could throw away the
current model and use the historical data to auto-generate  a new
neural net model~\cite{sieg95}.

The premise of this paper is {\em metrics starvation}; i.e.
situations in which we can access neither the relevant domain
expertise required for fuzzy logic, nor the historical data
required for genetic algorithms or neural nets. Our experience is
that metrics starvation is common. For example, the majority of
software development organizations do not conduct systematic data
collection. As evidence for this, consider the Software
Engineering Institute's capability
    maturity model (CMM~\cite{paulk93}),
     which categorizes software
organizations into one
    of
    five levels based on the maturity of their software development process.
Below CMM level 4, there may be no systematic and reliable data
collection.
    Below CMM level 3, there may not even be a written definition of the  software
    process.   Many organizations exist below CMM
    level 3\footnote{Personal communication with SEI
    researchers.}.
    Hence
       reliable data on SE projects is   scarce, or hard to interpret.

However, a lack of systematic data does not mean that no
inferences can be made about some software development process. If
we can't constrain the range of model behavior with domain
metrics, we can still make decisions by surveying the range of
possible behaviors. Suppose we have a model expressing what is
known within a domain. If we are uncertain over parts of that
model, then we
 might supply {\em ranges} for those
uncertain parameters. When we run this model, if we ever require
some  uncertain parameter, we might {\em select} and {\em cache} a
value for that parameter, based on the supplied ranges. To survey
the range of possible behaviors, we just re-run the model many
times, taking care to clear the cache between each run. Many
variants on this scheme have been discussed in the literature. For
example: \bi \item This scheme is the same as Monte Carlo
simulations when  uncertain parameters are just system inputs.
\item This scheme is the same as abductive
inference~\cite{kakas98} where the uncertain parameters are truth
assignments to assumptions within the model, and some global
invariant checking executes before a new value is assigned. \ei

The advantage of this ``select and cache'' method is that the
range of possible behaviors can be explored {\em without}
expensive further analysis. The disadvantage of this approach is
{\em data clouds}: an overwhelming amount of data that clouds and
confuses the issues. For example, \fig{clouds}.i and
\fig{clouds}.ii show data clouds generated from case studies
described later in this paper. In these figures, each mark
represents the {\em cost} and {\em benefits} associated with a set
of decisions about the structure of a software project. Note the
large variance in the possible cost and benefits from the
different possible decisions.
\begin{figure}
\begin{center}
{\footnotesize
\includegraphics[width=1.7in]{archb4.eps}\includegraphics[width=1.7in]{jplb4.eps}\\
{\em \fig{clouds}.i: Cloud1 (from \tion{casea})~~~~~~~~~~
\fig{clouds}.ii:  Cloud2 (from \tion{casec})}\\~\\
\includegraphics[width=1.7in]{archafter.eps}\includegraphics[width=1.7in]{jplafter.eps}\\
{\em \fig{clouds}.iii: Cloud1, condensed~~~~~~~~
\fig{clouds}.iv:Cloud2, condensed} }
\end{center}
\caption{Examples of condensing clouds. The right-hand model's
cost values are continuous while the left-hand model has discrete
costs. }\label{fig:clouds}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[width=3.3in]{cycle.eps}
\end{center}
\caption{Incremental treatment learning }\label{fig:cycle}
\end{figure}

Faced with such large data clouds,  it is hard to demonstrate that
any particular decision leads to a particular outcome. What is
required is some method for condensing these clouds of uncertainty
{\em without} expensive data collection for all the uncertain
parameters. Ideally, condensation
 methods should be {\em minimal}; i.e.  they require a
commitment to only a small portion of the  uncertain variables
within a model.

This papers experiments with minimal condensation using the  TAR2
{\em treatment
learner}~\cite{hu02,me01f,me01g,me01h,me02a,fea02a}. A treatment
learner seeks the  {\em least number} of attribute ranges that
{\em most differentiate} between desired and undesired behavior.
\fig{cycle} shows how TAR2 can be applied incrementally to explore
data clouds. A simulator executes a model generated by some manual
modelling process. TAR2 reduces the data generated by the
simulator to a set of {\em proposed treatments}. After some
discussion, users add the {\em approved treatments} to a growing
set of  constraints for the simulation. The cycle repeats until
users see no further improvement in the behavior of the simulator.
Experiments with this approach have shown that   TAR2 can: \bi
\item {\em Reduce the variance} of values within a data cloud
\item {\em Improve the mean} of values within data clouds \ei For
example, \fig{clouds}.iii and \fig{clouds}.iv show the results of
applying incremental  treatment learning  to \fig{clouds}.i and
\fig{clouds}.ii.
 Note
that in both studies, the mean of the benefits increased, the mean
of the costs decreased, and the variance in both measures was
greatly decreased.


The notion that extra constraints can reduce the space of
uncertainties is hardly surprising. However, what is surprising is
 {\em how few} extra constraints TAR2 needs to
condense (e.g.) \fig{clouds}.ii to \fig{clouds}.iv; and
 how {\em
easily} TAR2 can  automatically
 find those constraints. The claim
of this paper is that: \begin{quote}
 \em In the average case,
 a
simple algorithm (TAR2) can quickly find a very small number of
key constraints that result in massive condensations of data
clouds towards some desired goal.
\end{quote}
There are three implications of this claim. Firstly, even when we
don't know exactly what is going on within a model, it is possible
to define minimal strategies to grossly decrease the uncertainty
in that model's behavior.

Secondly, even if we aren't sure about the impact of certain
decisions, we can be sure that certain other decisions will be
ineffective. Decisions about treatment variables will override
decisions about variables not found within a treatment. Hence,
decisions about variables outside the treatments are redundant.

Thirdly, incremental treatment learning can reduce the cost of
software modelling.  Before applying elaborate modelling techniques
or tools, it is wise to try cheaper and simpler techniques. Our
results here show that even hastily built incomplete models can be
used for effective decision making. Since much can be learnt, even
from sketchy data, it may be possible to avoid elaborate and
extensive  and expensive metrics collection. Further, once the
treatments are known, then a minimal metrics collection program can
be defined, just for the few variables in the treatments.

%precise model control needs elabote data collection and inference
%5 but when condensation is enough, svery simple architecture

The rest of this paper describes the details of our condensation
technique. TAR2 was motivated by  {\em funnel theory} which is a
claim that most decisions are redundant or irrelevant. In models
containing funnels, a small number of key variables are enough to
control a model, despite the large range of possibilities outside
the funnel. Funnel theory is discussed in \S2. Our algorithm for
finding the key decisions within the funnels  is discussed in \S3.
Case studies are then explored in \S4 where TAR2 can reduce the
variance and improve the mean of three case studies.  After that,
\S5  discusses when this approach may not be appropriate and \S6
discusses related work.


%XXX given growing data sets. why not ga and nn?

\section{Funnel Theory}\label{sec:rel}

The premise of this paper is that within the space of possible
decisions, there exist a small number of key decisions that
determine all others. After Menzies, Easterbrook,
 Nuseibeh, and Waugh, we call this premise
{\em funnel theory}-  the metaphor being that all processing runs
down the same narrow funnel~\cite{me99a}.

To introduce funnels, we first say that a decision space supports
{\em reasons}; i.e. chains of reasoning that link inputs in a
certain context to desired goals. Chains have links of at least
two types. Firstly, there are links that clash with other links.
Secondly, there are the links that depend on other links. One
method of optimizing the decision making process would be to first
decide about the non-dependent clashing links. These are the {\em
key decisions} since they determine most of the other non-key
decisions.

For example, suppose the following decision space is explored
using the invariant $nogood(X,\neg X)$ and everything that is not
a $context$ or a $goal$ is open to debate:
%\begin{center}{\foonotesize
\[
\begin{array}{r@{}l@{}l}
&a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e\\
context1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
context2 \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}
\]
% }\end{centre}
Like any model, any of $\{a,b,..q\}$ is subject to discussion.
However, in the context of reaching some specified goals from {\em
context1} and {\em context2}, the only important discussions are
the clashes $\{g,\neg g,j,\neg j\}$ (the $\{e, \neg e\}$ clash is
not exercised in the context of $context1,context2~\vdash~goal$,
since no reason uses $e$ or $\neg e$). 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.

The {\em funnel} of a decision space contains the non-dependent
clashing links; e.g. $\{g\}$. The decisions with {\em greatest
information content} are the decisions about the funnel variables,
since these variables set the others. If the space contains {\em
narrow funnels} (i.e. funnels with small cardinality) then the total
decision space can be greatly reduced to a small number of highly
informative disputes about funnel variables. Analysts are still free
to debate whatever they want (and they will, seemingly endlessly),
but with this approach, a funnel-aware analyst can steer the
discussion towards the issues that tell us most about a domain. The
net effect can be less argument. Suppose our analysts agree that {\em
g} is true, then in the context of arguing about how
 $context1,context2~\vdash~goal$, the decision space reduces
 to:
\[
\begin{array}{r@{}l@{}l}
context1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
\end{array}
\]
The reasoning starting with $k$ has been culled since, by endorsing
{\em g}, we must reject all lines of reasoning that use $\neg g$. In
addition, the reasoning starting with $a,n$ are ignored since they
are irrelevant in this context; i.e. they do not participate in
reaching a desired goal. Further, in this context, there is little
point arguing about $\{f,h,i,j\}$ since if any of these are false,
then no goal can be reached.

This small example suggests how funnels can condense data clouds.
Data clouds are the result of a wide variation in model behavior.
Such variation come from choices within a model relating to uncertain
ranges. The more commitments we make about funnel variables, the more
we  collapse the space of possibilities outside the funnel. Hence,
decisions about funnel variables condense data clouds, since they
restrict the behavior of a system. Decision making in spaces
containing funnels can be simple and short.  Once values for the
funnel variables are decided, all other decisions become redundant.
In the above example, we have a decision space containing potentially
$2^{17}=131,072$ debates about 16 boolean variables $\{a..q\}$. A
decision about one variable (i.e. ``is $g$ true or false?'') has
reduced this space to one option.

Relying on narrow funnels may seem an overly  optimistic approach.
Yet a literature review suggests that such optimism is
well-founded. There are many examples of funnel-like behavior in
the literature.   For example Horgan \& Mathur~\cite{horgan96}
report that testing often exhibits a {\em saturation} effect; i.e.
most program paths get exercised early with little further
improvement as testing continues. Saturation is consistent with
funnels controlling the reachable parts of a program. If these
funnels were narrow, there would be few options in a program's
execution and test inputs would quickly sample them all. Further
testing over systems with narrow funnels would yield little
further information since anything not connected to the funnels
would be, by definition, unreachable.

An analogous effect to saturation is {\em homogenous propagation}.
Despite numerous perturbations on data values using a program
mutator\footnote{A {\em mutant} of a program is a syntactically
valid but randomly selected variation to a program; e.g. swapping
all plus signs to a minus sign.}, Michael found that in 80 to 90\%
of cases, there were no changes in the behavior of a range of
programs~\cite{michael97}. Another study compared results using
X\% of a library of mutators, randomly selected \mbox{(X $\in$
\{10,15,\ldots40,100\})}. Most of what could be learnt from the
program could be learnt using only X=10\% of the mutators; i.e.
after a very small number of mutators, new mutators acted in the
same manner as previously used mutators~\cite{wong95}. The same
observation has been made elsewhere in the mutation
literature~\cite{budd80,acree80}. Like saturation, homogenous
propagation is consistent with funnel theory. If the overall
behavior of a system is determined by a small number of key
variables, then random mutation is unlikely to find those
variables and the net effect of those mutations would be very
small.


Homogenous propagation is observed in procedural programs. An
analogous effect has been seen in declarative systems; i.e. most
choices within a declarative set of constraints have little effect on
the average behavior. Menzies \& Waugh studied choices in millions of
mutations of a nondeterministic system. In their {\em abductive
framework}~\cite{kakas98,me97a}, a consistent set of choices
generated a {\em world} of belief. Given $N$ binary choices, there
are theoretically $2^N$  possible worlds. However, after studying
millions of generated worlds they found the maximum number of goals
found in any world was often close to the number of goals found in a
world selected at random~\cite{me98f} (on average, the difference was
less than 6\%). This observation is inexplicable without narrow
funnels. If choices had a large impact on what was reached within a
declarative system, then there should be much variability in what is
found in each world. Since the observed variability was so small, the
number of critical choices (a.k.a. funnel variables) must also be
small.

 In fact,  the concept of a
funnel has been reported in many domains under a variety of names
including: \bi \item {\em Master-variables} in
scheduling~\cite{crawford94}; \item {\em Prime-implicants} in
model-based diagnosis~\cite{rymon94an} or machine
learning~\cite{rymon93setree}, or fault-tree
analysis~\cite{lutz99}. \item {\em Backbones} in
satisfiability~\cite{parkes99lifted,singer00backbone}; \item {\em
The dominance filtering} used in  Pareto optimization of
designs~\cite{joseph98}; \item {\em Minimal environments} in the
ATMS~\cite{deKleer86}; \item The {\em base controversial
assumptions} of HT4~\cite{me97a}. \ei Whatever the name, the core
intuition in all these terms is the same: what happens in the
total space of a system can be controlled by a small critical
region. The frequency of the funnel effect  have made Menzies \&
Singh suspect that funnels are some average case phenomenon that
is emergent in  decision spaces~\cite{me00t}. To test this, they
consider a device that can choose between a narrower and a wider
funnel.  Let some goal in a system be reachable by a narrow funnel
$M$ or a wide funnel $N$ shown in \fig{fun}.
\begin{figure}
\[ \left.
\begin{array}{r}
\stackrel{a_1}{\longrightarrow} M_1\\
\stackrel{a_2}{\longrightarrow} M_2\\
 \ldots\\
\stackrel{a_m}{\longrightarrow} M_m
\end{array}
\right\} \stackrel{c}{\longrightarrow} goal_i
\stackrel{d}{\longleftarrow} \left\{
\begin{array}{r}
N_1\stackrel{b_1}{\longleftarrow} \\
N_2 \stackrel{b_2}{\longleftarrow}\\
N_3 \stackrel{b_2}{\longleftarrow}\\
N_4 \stackrel{b_2}{\longleftarrow}\\
 \ldots\\
N_n\stackrel{b_n}{\longleftarrow}
\end{array}
\right.
\]
\caption{Alternate funnels that lead to some goal.}\label{fig:fun}
\end{figure}
Under what circumstances will the narrow funnel be favored over
the wide funnel?  The following definitions let us answer this
question: \bi \item Let the cardinality of the narrow funnel and
wide funnels be $m$ and $n$ respectively. \item Each $m$ members
of the narrow funnel are reached via a path with probability $a_i$
while each $n$ members of the wider funnel are reached via a path
with probability $b_i$. \item Two paths exist from the funnels to
this goal: one from the narrow neck with probability $c$ and one
from the wide neck with probability $d$. Therefore, the
probability of reaching the goal via the narrow pathway is
\mbox{$narrow = c\prod^m_{i=1}a_i$} while the probability of
reaching the goal via the wide pathway is \mbox{$wide =
d\prod^n_{i=1}b_i$}. \ei With these definitions, the Menzies \&
Singh study can be redefined as the search for conditions under
which \begin{equation}\label{eq:t}
\left(\frac{narrow}{wide}=R\right)>t\end{equation} where $t$ is
some threshold value.

To explore \eq{t},
  Menzies \& Singh built a small
  simulator of \fig{fun}, and performed 150,000  runs using different
  distributions for $a_i,b_i,c,d$ and a wide range of
  values for $m,n$. The results are shown in \fig{alp}. For comparison purposes,
  the size of the two funnels is expresses as  a ratio $alpha$ where $n=alpha*m$.
As might be expected, at $alpha=1$ the funnels are the same size
and the odds of using one of them is 50\%.  As $alpha$ increases,
then increasingly $R>t$ is satisfied and the narrower funnel is
 preferred to
the wider funnel.  The effect is quite pronounced. For example,
for all the studied distributions, after the wider funnel is 2.25
times bigger than the narrow funnel, then in 75\% or more of the
random searches, accessing the narrow funnel is at least 1,000,000
times more  likely as accessing the wider funnel (see the lower
graph of \fig{alp}). Interestingly, as the probability of using
any of $a_i,b_i, c_i,d_i$ decreases,
 the odds
of using the narrow funnel increase (see the {\em pessimistic
curves} in \fig{alp}). That is, narrow funnels are  likely,
especially in spaces that are difficult to search.


   \begin{figure}[!t]
\centerline{\includegraphics[width=2.5in]{sum20.eps}}
\caption{10,000 runs of  the funnel simulator. Y-axis shows what
percentage of the runs satisfies
$\left(\frac{narrow}{wide}=R\right)>t$. The $pessimistic$,
$lognormal$,
 and $optimistic$ distributions assume a worst-case, average-case,
and best-case (respectively) distribution for $\{a_i,b_i,c_i,d_i\}$. For more
details, see~\cite{me00t}.}\label{fig:alp}
\end{figure}

The average case analytical result of Menzies \& Singh is
suggestive evidence, but not conclusive evidence, that narrow
funnels are common. Perhaps a more satisfying  test for narrow
funnels would be to check if, in a range of applications, a small
number of variables are enough to control the other variables in a
model. The rest of this paper implements that check.

\section{Finding the Funnel}\label{sec:funn}

A traditional  approach to funnel-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 funnels,
it may be unnecessary. There is no need to {\em search} for the
funnel in order to {\em exploit} it. Any reasoning pathway to
goals must pass through the funnels (by definition). Hence, all
that is required is to find attribute ranges that are associated
with desired behavior.


\begin{figure}
{\small {\em
\begin{center}
\begin{tabular}{rcccl}
outlook & temp($^o$F) &  humidity & windy? & class
\\\hline
sunny&  85&     86&     false&  none\\
sunny&     80&     90&     true&   none\\
sunny&     72&     95&     false&  none\\
rain&  65&     70&     true&         none\\
rain&        71&     96&     true&   none\\\hline
      rain&         70&     96&     false&      some\\
      rain&      68&     80&     false&      some\\
      rain&      75&     80&     false&  some\\\hline
      sunny&    69&     70&     false&  lots \\
      sunny&    75&     70&     true&   lots\\
      overcast&  83&     88&     false&  lots\\
      overcast&  64&     65&     true&   lots\\
      overcast&  72&     90&     true&   lots\\
     overcast&  81&     75&     false&  lots\\\hline
\end{tabular}\end{center}}}
\caption{A log of some golf-playing behavior.}
\label{fig:golfdata}
\end{figure}

TAR2 is a machine learning method for finding attribute ranges
associated with desired behavior. Traditional machine learners
generate classifiers that assign a class symbol to an
example~\cite{quinlan86}. TAR2 finds the difference between
classes. Formally, the algorithm is a {\em contrast set
learner}~\cite{bay99} that uses {\em weighted
classes}~\cite{cai98} to steer the inference towards the preferred
behavior. The algorithm differs from other learners in that it
seeks contrast sets of {\em minimal} size.

TAR2 can best be introduced via example. Consider the log of golf
playing behavior shown in \fig{golfdata}. This log contains four
attributes and 3 classes. Recall that TAR2 accesses a {\em score}
for each class. For a golfer, the classes in \fig{golfdata} could
be scored as {\em none=2} (i.e. worst), {\em some=4}, {\em lots=8}
(i.e. best).

TAR2  seeks attribute ranges that occur more frequently in the
highly scored classes than in the lower scored classes. Let $a.r$
be some attribute range e.g. {\em outlook.overcast}.
$\Delta_{a.r}$ is a heuristic measure of the worth of $a.r$ to
improve the frequency of the $best$ class. $\Delta_{a.r}$ uses the
following definitions:
\begin{description}
\item[$X(a.r)$:]  the number of occurrences of that attribute
range in class $X$; e.g. {\em lots(outlook.overcast)=4}.
\item[$all(a.r)$:] total number of occurrences of that attribute
range in all classes; e.g. {\em all(outlook.overcast)=4}.
\item[$best$:]  the highest scoring class; e.g. $best=lots$;
\item[$rest$:]   the non-best class; e.g. $rest=\{none,some\}$;
\item[$\$Class$:]  score of a class $Class$ is $\$Class$.
\end{description}
 $\Delta_{a.r}$ is
calculated as follows:

{\footnotesize
\[
\Delta_{a.r}=\frac{\sum_{X{\in}rest}(\$best-\$X)*
(best(a.r)-X(a.r))}{all(a.r)}
\]
}{\noindent}When {\em a.r} is {\em outlook.overcast}, then
$\Delta_{outlook.overcast}$ is calculated as follows:
\[\frac{\overbrace{((8-2)*(4-0))}^{lots \rightarrow none}+\overbrace{((8-4)*(4-0))}^{lots \rightarrow some}}{4+0+0}=\frac{40}{4}=10
\]


\noindent The attribute ranges in our golf example generate the
$\Delta$ histogram shown in \fig{dels}. Note that {\em
outlook=overcast}'s $\Delta$ is the highest, potentially most
effective, attribute range.

%-----------------------------------
% deltaf distribution of Golf data
%-----------------------------------

\begin{figure}
\begin{center}
{\small
\begin{tabular}{c}
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
 \setstretch{8}\sethspace{0.5} \setyaxis{0}{3}{1}
\setxaxis{-5}{10}{1}
 \bar{0}{8} % -5
 \bar{1}{1} %-4
 \bar{0}{8} % -3
 \bar{0}{8} % -2
 \bar{1}{1}  % -1
  \bar{3}{1} % 0
  \bar{3}{1} % 1
\bar{2}{1} % 2
 \bar{0}{8} %3
\bar{0}{8} %4
\bar{1}{8} %5
\bar{1}{8} %6
\bar{0}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\bar{1}{8} %10
\end{barenv}
\end{tabular}
}
\end{center}
\caption{$\Delta$ distribution seen in golf data sets.
The X-axis shows the range of $\Delta$ values seen in the gold data set.
The Y-axis shows the
number of attribute ranges that have a particular $\Delta$.
Outstandingly high $\Delta$ values shown in black.
}
\label{fig:dels}
\end{figure}



A {\em treatment} is a subset of the attribute ranges with an {\em
outstanding} $\Delta_{a=r}$ value. For our golf example, such
attributes can be seen in \fig{dels}: they are the outliers with
outstandingly large $\Delta$s on the right-hand-side. (These
outliers include {\em outlook=overcast}).

%-----------------------------------
% treatment of Golf data
%-----------------------------------

\begin{figure}
\begin{minipage}{.70\linewidth}
{\small\begin{center}
\begin{tabular}{p{1.1in}p{1.1in}l}
$no\; change$  & $outlook=\newline
overcast$\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
     \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{5}{1}
 \bar{3}{4}
 \bar{6}{8}
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{0}{1} \bar{0}{4} \bar{4}{8}
\end{barenv}
\end{tabular}
\end{center}
}\end{minipage}\hfill
\begin{minipage}{.3\linewidth}
\begin{raggedleft}
{\footnotesize
\begin{tabular}{r@{}l}
\protect\legend1{~}&\begin{raggedright}= none
(worst)\end{raggedright}
\\
\protect\legend4{~}&\begin{raggedright}= some\end{raggedright}\\
\protect\legend8{~}&\begin{raggedright}= lots
(best)\end{raggedright}
\end{tabular}}
\end{raggedleft}
\end{minipage}
\caption{Finding treatments that can improve golf playing
behavior. With no treatments, we only play golf lots of times in
$\frac{6}{5+3+6}= 57\%$ of cases. With the restriction that {\em
outlook=overcast}, then we play golf lots of times in 100\% of
cases. } \label{fig:golft}
\end{figure}


To {\em apply}  a treatment,   TAR2 rejects all example entries
that contradict the conjunction of   attribute ranges in the
treatment. The ratio of classes in the remaining examples is
compared to the ratio of classes in the original example set. The
{\em best treatment} is the one that most increases the relative
percentage of preferred classes. In the case where $N$ treatments
increase the relative score by the same amount, then $N$ {\em best
treatments} are generated and TAR2 picks one at random. In our
golf example, a single  best treatment was generated containing
{\em outlook=overcast}; \fig{golft} shows the class distribution
before and after that treatment, i.e. if we choose a vacation
location that is generally overcast,  then in 100\% of cases we
should be playing lots of golf, all the time.

\begin{figure*}
\begin{minipage}{.65\linewidth}
 \includegraphics[width=7.5in,height=4.48in,angle=90]{arch.eps}
\end{minipage}\hfill\begin{minipage}{.35\linewidth}
{\small
 \begin{tabular}{|r@{  }p{1.6in}|}\hline
  Claim : & Notes \\\hline
  c1 : & ``among the few vital goals'' \\
  c2 : & ``a claim by David Parnas''~\cite{Parnas72}\\
  c3 : & ``few assumptions among interacting modules''\\
  c4 : & ``expected size of data is huge''\\
  c5 :& ``many implementors familiar
 with ADTs'' (from
 domain experts)\\\hline

 \multicolumn{2}{c}{ }\\\hline
\multicolumn{2}{|l|}{Inference rules:}\\\hline
 \multicolumn{2}{|p{2in}|}{The $benefit$ of the this network
is the $benefit$ computed for  the top-level node $good$. This
$benefit$ is defined recursively as follows:
\bi
\item
The benefit of a leaf node is 1 if it is selected, or 0 otherwise.
Leaf nodes represent choices in the network. Leaf nodes are shown in gray.
\item
The benefit of a non-leaf node is computed from its input influences.
\item An
 influence of an edge on an upstream node
 is the product of the edge weight and the $benefit$
of the downstream node.
 \item Edge weights are set
by tables that
 offer numeric values for  {\em \{++,+,=,-,--\}}.
\item Nodes are either disjunctions or conjunctions. Conjunctions
are shown as diamonds. The benefit of a conjunction is minimum of
the input influences. The benefit of a disjunction is  the average
of the input influences. \ei For a rationale on why these rules
were selected, see~\cite{chiang03}. In summary: these rules were
not unreasonable and the users wanted it that way. Future
experiments in this domain will explore variants to these
rules.}\\\hline
\end{tabular}
}
\end{minipage}
\caption{A model that assesses architectural choices within software.
Options within the model are the leaf nodes shown in gray. These
options can be architectural decisions such as the use of {\em
abstract data types, implicit invocation, pipe \& filter} methods, or
{\em shared data}. Some links in the model are dependant of various
claims $c1..c5$ shown top, right of the diagram. For example, {\em
claim[c2]} is Parnas's~\cite{Parnas72} argument that having a single
share data model across an entire application has a negative impact
on the modifiability of that process.  The inference rules of this
diagram are shown middle, right.}\label{fig:arch}
\end{figure*}

\section{Case Studies}

This section presents three examples of incremental treatment
learning. The examples are sorted by model size: smallest to largest.
The largest and final model is too detailed to explain here but the
second largest model is explained in sufficient detail for the reader
to reproduce the entire experiment. In all examples, the objective of
incremental treatment learning is to find a subset of all possible
decisions that {\em reduces the variance} and {\em improves the mean}
of the important variables within a data cloud.


\subsection{Case Study A: Software
Architectures}\label{sec:casea}


\fig{arch} shows some architectural assessment knowledge taken from
Shaw \& Garlan's Software Architectures book~\cite{shaw96}. The
knowledge is  expressed in our variant of the {\em softgoal} notation
of Chung et al.~\cite{chung00}. In the softgoal approach, a {\em
softgoal} is   distinguished from  a normal goal as follows: \bi
\item While a $goal$ has well-defined non-optional feature of a
system that {\em must} be available,  a $softgoal$ is a goal that has
no clear cut criteria for success. \item While goals can be
conclusively demonstrated to be {\em satisfied} or {\em not
satisfied}, softgoals can only be {\em satisfied} to some degree. \ei

Much is under-constrained in \fig{arch}. In fact, there are
$4^{21}*2^9\approx 10^{15}$ possibilities within this model:

\bi \item The nine boolean choices in the model are  leaf nodes
representing software architecture options or claims about the
application. Hence, there are $2^9$ combinations of these choices.
\item Edges between nodes in \fig{arch} are annotated with a symbol
denoting how strongly the downstream node impacts the upstream node.
These annotations are $\{++, +, =, - , --\}$ denoting $makes, helps,
equals,
 hurts, breaks$ (respectively).
For the sake of exposition, we say that
  the values for four of these
 annotations come from a range of 21 possible values

{\small\begin{eqnarray}\nonumber &1 \ge X_{makes} > X_{helps}
> X_{hurts} > X_{breaks} \ge -1&\\&X_I \in \{-1,
-0.9,-0.8,.. 0,... 0.9, 1\}&\label{eq:one}
\end{eqnarray}}
(The exact value of $equals$ is not varied since this annotation
is used to propagate influences unchanged over an edge; i.e.
$weight(equals)=1$.)

Hence, in the worst case, there are $4^{21}\approx10^{12}$
possible edge weights. \ei

These possibilities generate a wide range of behavior. Our
softgoal interpreter~\cite{chiang03}  computes a $cost$ and
$benefit$ figure resulting from a selection of edge weights and
choices in diagrams like \fig{arch} (the details of this
computation are discussed in the {\em inference rules}
table of \fig{arch}). \fig{clouds}.i
shows the range of $benefit$s and $cost$s seen after  10,000
random selection of choices and edge weights. Note the large
variance in these figures.



To apply incremental treatment learning for this case study, we
first require a scoring scheme for the different classes. In
10,000 runs of \fig{arch}, with no constraints on any selections,
the observed $costs$ ranged from 1 to 4 and the $benefit$ ranged
from -18 to 12 (see \fig{clouds}.i). Since high $benefit$ and low
$cost$ is preferable to high $cost$ and low $benefit$, these
ranges were scored as shown in \fig{utils1}. In that figure, the
best range is $benefit \ge 12$ and $cost =1$ and the worst range
is $benefit \le -18$ and $cost=4$.

\begin{figure}
\begin{center}
{\footnotesize {\bf scoring
function:}\begin{tabular}{c|rrrr}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &  1    &2    & 3    & 4    \\\hline
 12         &    1   &  2     &  3    & 4          \\
 6           &   5   &   6   &   7   &  8         \\
 0           &   9   &   10   &  11  & 12       \\
 -6          &   13   &   14   &  15   &  16          \\
 -12         &   17   &  18   &   19   &  20       \\
 -18          &  21   &  22    &   23 &  24   \\\hline
\end{tabular}}
\end{center}
\caption{Class scoring function.}\label{fig:utils1}\end{figure}



TAR2 was applied to \fig{arch} four times. Each round comprised
10,000 runs where: \bi \item Edge weights were selected at random
at the start of each run from \eq{one}. \item From the space of
remaining choices, architectural options and claims were selected
at random. \ei

Initially, no restrictions were imposed on the architectural
options and  claims. This generated the ranges of $cost$ and
$benefit$ shown in \fig{clouds}.i. Such a data cloud is hard to
read. A more informative representation is the {\em percentile
matrix} of \fig{rzero}. Each cell of this matrix shows the percent
of  runs that falls into a certain range. Each cell is colored on
a scale ranging from white (0\%) to
 black (100\%).


\begin{figure}
\begin{center}
{\footnotesize {\bf round 0:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}
\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5} Benefit
& 1 &2    & 3    & 4   &  Totals\\\hline
 12         &       &       &      &    &       \\
 6           &       &  \sq{1}{99}   & \sq{2}{98}     &  \sq{1}{99}  & \sq{4}{96}      \\
 0           &   \sq{13}{87}  & \sq{19}{83}     &  \sq{15}{85}  & \sq{4}{96}  & \sq{51}{51}      \\
 -6          &   \sq{10}{90}  & \sq{12}{88}     &  \sq{4}{96}    & \sq{1}{99}   & \sq{27}{73}       \\
 -12         &   \sq{4}{96}    &  \sq{6}{94}    & \sq{2}{98}     &    &    \sq{12}{88}    \\
 -18          &  \sq{3}{97}    &   \sq{2}{98}    & \sq{1}{99}  & \sq{1}{99}  &
 \sq{7}{93}\\\hline
Totals        &   \sq{30}{70}    & \sq{40}{62}      &  \sq{24}{76}
& \sq{6}{94} & \sq{100}{2}
\\\hline
\end{tabular}}
\end{center}
\caption{Percentage distributions of $benefit$s and $cost$s seen
in 10,000 runs of \protect\fig{arch}, assuming \protect\eq{one}
and a random selection of architectural options and claims.
}\label{fig:rzero}\end{figure} \fig{rounds} shows the results of
applying incremental treatment learning to  \fig{arch}. Each round took the key
decisions learnt by TAR2 from 10,000 examples generated in the
previous round. 10,000 more runs were then performed, with the
selection of architectural options and claims restricted according
to the current set of key decisions.  Note that as the key
decisions accumulate, the variance in the behavior decreases and
the means improve (decreased $cost$ and increased $benefit$).

\begin{figure}[!t]
\begin{center}
{\footnotesize \begin{eqnarray}\nonumber KEY_1&=&
(claim[c1]=yes)\\\nonumber
   & & \wedge (pipe \& filter[target \,system]=yes)
\end{eqnarray}
{\bf round 1:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit  &     1    &2    & 3    & 4   &  Totals\\\hline

 12            &       &  \sq{1}{99}    &  \sq{2}{98}  & \sq{1}{99}  & \sq{4}{96}     \\
 6             &       &  \sq{5}{95}  &   \sq{9}{91}   &  \sq{3}{97}&  \sq{17}{83}    \\
 0          &  \sq{11}{89}    &  \sq{30}{70}  & \sq{26}{74}    & \sq{7}{93}   &  \sq{74}{26}      \\
 -6           & \sq{1}{99}    &  \sq{2}{98} & \sq{1}{99}  & \sq{1}{99} &     \sq{5}{95}   \\
 -12           &    &   &    & &        \\
 -18           &     &  &     &    &       \\\hline Totals&
  \sq{12}{88} &  \sq{38}{62} & \sq{38}{62}  & \sq{12}{88}  &   \sq{100}{1}  \\\hline
\end{tabular}
\begin{eqnarray}\nonumber
KEY_2&=& KEY_1 \wedge (shared\, data[target\, systems]=yes)
\\\nonumber
   &  & \wedge (implicit\, invocation [target\, system]=no)
   \end{eqnarray}
{\bf round 2:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit  &     1 &2    & 3    & 4   &  Totals\\\hline

 12            &       &  \sq{3}{97}    &  \sq{6}{94}  &   &   \sq{9}{91}   \\
 6             &   \sq{4}{96}    &  \sq{17}{83} &  \sq{14}{86}  &  &   \sq{35}{65}  \\
 0           &   \sq{28}{72}   &  \sq{28}{74}   &      &    &  \sq{56}{46}      \\
 -6           &     &   &   &  &        \\
 -12           &    &   &    & &        \\
 -18           &     &  &     &    &       \\\hline
Totals       &  \sq{32}{68}    &  \sq{48}{54}   &  \sq{20}{80} &
\sq{~}{99}& \sq{100}{2}
\\\hline
\end{tabular}
\begin{eqnarray}\nonumber
KEY_3&=& KEY_2 \wedge (abstract\, data\, type[target\,
systems]=no)\\\nonumber
   & & \wedge (claim[c3]=no)
   \end{eqnarray}
{\bf round 3:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit  &    1 &2    & 3    & 4   &  Totals\\\hline
 12            &       &  \sq{12}{88}    &      &    &  \sq{12}{88}    \\
 6             &       &  \sq{39}{61}    &      &    &  \sq{39}{61}    \\
 0             &       &  \sq{48}{52}    &      &    &   \sq{48}{52}     \\
 -6            &       &  \sq{1}{99}    &      &    &    \sq{1}{99}    \\
 -12          &       &      &      &    &        \\
 -18           &       &      &      &    &       \\\hline
Totals        &  \sq{~}{99}     & \sq{100}{1}     &  \sq{~}{99} &
\sq{~}{99}& \sq{100}{1}
\\\hline
\end{tabular}
\begin{eqnarray}\nonumber
KEY_4&=& KEY_3 \wedge (claim[c2]=yes) \\\nonumber
   &  & \wedge (claim[c4]=yes)
   \end{eqnarray}
{\bf round 4:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit     &  1 &2    & 3    & 4   &  Totals\\\hline
 12            &       &  \sq{20}{80}    &      &    &  \sq{20}{80}  \\
 6            &       &  \sq{38}{62}    &      &    &  \sq{38}{62}    \\
 0           &       &   \sq{42}{57}   &      &    &  \sq{42}{57}      \\
 -6          &       &      &      &    &        \\
 -12        &       &      &      &    &        \\
 -18          &       &      &      &    &       \\\hline
Totals        &     \sq{~}{99}  &   \sq{100}{1}   &  \sq{~}{99} &
\sq{~}{99} & \sq{100}{1}
\\\hline
\end{tabular}
}
\end{center}
\caption{Percentile matrices showing four rounds of incremental  treatment learning for
\fig{arch}}\label{fig:rounds}
\end{figure}

 This experiment stopped after
four rounds since there was little observed improvement between
round 3 and round 4. \fig{clouds}.iii shows the results of the round 3, not round 4;
i.e. this experiment returned the
results from round 3, and not round 4. By stopping at round 3,
analysts can avoid excessive decision making since they need never
discuss $c2,c4,c5$ with their users. Alternatively, if in some
dispute situation, an analyst could use $c2,c4,c5$  as bargaining
chips. Since these claims have little overall impact, our analyst
could offer them in any configuration as part of some compromise
deal in exchange for the other $key$ decisions being endorsed.

\subsection{Case Study B: Circuit Design}\label{sec:caseb}

Our next example contains a model somewhat more complex than
\tion{casea}. This example is based on  models first developed by
Bratko to demonstrate principles of qualitative
reasoning~\cite{bratko01}.

While our last example generated cost and benefit figures for a
software project, this example is a qualitative model of a circuit
design shown in \fig{cirttiny}. Such qualitative descriptions of a
planned piece of software might appear early in the software
design process.
\begin{figure}
\begin{center}
\includegraphics[width=1.7in]{cirttiny.eps}
\end{center}
\caption{A qualitative circuit. From~\cite{bratko01}.}
\label{fig:cirttiny}
\end{figure}
We will
assume that the goal of this circuit is to illuminate some area; i.e.
{\em the more bulbs that glow, the better}.

For exposition purposes, we assume that much is unknown about our
circuit. All we will assume  is that the topology of the circuit
is known, plus  some general knowledge about electrical devices
(e.g. the voltage across components in series is the sum of the
voltage drop across each component). What we don't know about this
circuit are the precise quantitative values describing each
component.

When quantitative knowledge is unavailable, we can use
qualitative models. A qualitative model is a quantitative mode
whose numeric values $x$ are replaced by a qualitative value $x'$
having one of three qualitative states: +, -, 0; i.e.

{\footnotesize\begin{eqnarray}
x'\;=\;+& if & x > 0\nonumber\\
x'\;=\;0&if & x = 0\nonumber\\
x'\;=\;-&if& x < 0\nonumber
\end{eqnarray}}

\begin{figure}
{\scriptsize \begin{alltt}
%sum(X,Y,Z).
 sum(+,+,+).   sum(+,0,+). sum(+,-,Any).
 sum(0,+,+).   sum(0,0,0). sum(0,-,-).
 sum(-,+,Any). sum(-,0,-). sum(-,-,-).
\end{alltt}}
\caption{Qualitative mathematics using a Prolog
syntax~\protect\cite{bratko01}. } \label{fig:sum}
\end{figure}

The {\tt sum} relation of \fig{sum} describes our qualitative
knowledge of addition using a Prolog notation.  In Prolog,
variables start with upper case letters and constants start with
lower-case letters or symbols. For example, \[{\tt sum(+,+,+)}\]
says that the addition of two positive values is a positive value.
There is much uncertainty within  qualitative arithmetic. For
example \[{\tt sum(+,-,Any)}\] says that we cannot be sure what
happens when we add a positive and a negative number.

\begin{figure}
{\scriptsize
\begin{alltt}
%bulb(Mode,Light,Volts,Amps)
 bulb(blown,dark,  Any, 0).
 bulb(ok,   light, +,   +).
 bulb(ok,   light, -,   -).
 bulb(ok,   dark,  0,   0).

%num(Light, Glow).   %switch(State,Volts,Amps)
 num( dark,  0).      switch(on,    0,    Any).
 num( light, 1).      switch(off,   Any,  0).
\end{alltt}}
\caption{Definitions of qualitative bulbs and switches. Adapted
from \protect\cite{bratko01}.} \label{fig:bulb4}
\end{figure}

The {\tt bulb} relation of \fig{bulb4} describes our qualitative
knowledge of bulb behavior. For example, \[ {\tt
bulb(blown,dark,Any,0)}\] says that a blown bulb is dark, has zero
current across it, and can have any voltage at all. Also shown in
\fig{bulb4} are the {\tt num} and {\tt switch} relations. {\tt
Num} defines how bright a dark or light bulb glows while  {\tt
switch}
  describes our qualitative knowledge of
electrical switches. For example \[ {\tt switch(on,0,Any)}\] says
that if a switch is on, there is zero voltage drop across it while
any current can flow through it.

%  combos = 3.8*10^{19}
\begin{figure}
{\scriptsize \begin{alltt}
  1  circuit(switch(Sw1,VSw1,C1),
  2          bulb(B1,L1,VB1,C1),
  3          switch(Sw2,VSw2,C2),
  4          bulb(B2,L2,VB2,C2),
  5          switch(Sw3,VSw3,CSw3),
  6          bulb(B3,L3,VB3,CB3),
  7          Glow) :-
  8      VSw3 = VB3,
  9      sum(VSw1, VB1, V1),   %  9 options
 10      sum(V1,VB3,+),        %  1 option
 11      sum(VSw2,VB2,VB3),    %  9 options
 12      switch(Sw1,VSw1,C1),  %  2 options
 13      bulb(B1,L1,VB1,C1),   %  4 options
 14      switch(Sw2,VSw2,C2),  %  2 options
 15      bulb(B2,L2,VB2,C2),   %  4 options
 16      switch(Sw3,VSw3,CSw3),%  2 options
 17      bulb(B3,L3,VB3,CB3),  %  4 options
 18      sum(CSw3,CB3,C3),     %  9 options
 19      sum(C2,C3,C1),        %  9 options
 20      num(L1,N1),
 21      num(L2,N2),
 22      num(L3,N3),
 23      Glow is N1+N2+N3.

\end{alltt}}
\caption{\fig{cirttiny}, modelled in Prolog.
   Adapted from~\cite{bratko01}.}
   \label{fig:cirt}
\end{figure}


The {\tt circuit} relation of \fig{cirt} describes  qualitative
knowledge of a circuit using {\tt bulb, num, sum} and {\tt
switch}. This relation just records what we know of circuits wired
together in series and in parallel. For example:
\begin{smallitem}
\item {\tt Switch3} and {\tt Bulb3} are wired in parallel. Hence,
the voltage drop across these components must be the same (see
line 8). \item {\tt Switch2} and {\tt Bulb2} are wired in series
so the voltage drop across these two devices is the sum of the
voltage drop across each device. Further, this summed voltage drop
must be the same as the voltage drop across the parallel component
{\tt Bulb3} (see line 11). \item {\tt Switch1} and {\tt Bulb1} are
in series so the same current {\tt C1} must flow through both (see
line 12 and line 13)
\end{smallitem}


\begin{figure}[!t]
\begin{center}
\includegraphics[width=3.3in]{cirt.eps}
\end{center}
\caption{A device modelled using the Prolog of \fig{cirtt}.}
\label{fig:cirtt}
\end{figure}


\begin{figure}
{\scriptsize
\begin{alltt}
%inf(Sign,Bulb,Switch)
 inf(Inf,bulb(_,Shine,_,_),switch(Pos,_,_)) :-
    inf1(Inf,Shine,Pos).

%inf1(Sign,Glow,SwitchPos)
 inf1(+,dark,  off). inf1(+,light, on).
  inf1(-,dark,  on). inf1(-,light, off).
\end{alltt}}
\caption{The {\tt inf1/3} predicate used to connect bulb
brightness to switches. } \label{fig:inf3}
\end{figure}

\begin{figure*}
\begin{minipage}{.45\linewidth}
{\scriptsize \begin{alltt}
  1 circuits :-
  2    % some initial conditions
  3    value(light,bulb,B1a),
  4    % Uncomment to constrain Sw2c
  5    % value(off,switch,Sw2c),
  6    % Uncomment to constrain Sw1c
  7    % value(on,switch,Sw1c),
  8    % Uncomment to constrain Sw3c
  9    % value(on,switch,Sw3c),
 10    % explore circuit A
 11    circuit(Sw1a,B1a,Sw2a,B2a,Sw3a,B3a,GlowA),
 12    % let circuit A influence circuit B
 13    inf(+,B1a,Sw1b),
 14    inf(-,B2a,Sw3b),
 15    % let circuit B influence circuit C
 16    circuit(Sw1b,B1b,Sw2b,B2b,Sw3b,B3b,GlowB),
 17    % propagate circuit B to circuit C
 18    inf(-,B3b,Sw2c),
 19    inf(+,B2b,Sw3c),
 20    % explore circuit C
 21    circuit(Sw1c,B1c,Sw2c,B2c,Sw3c,B3c,GlowC),
 22    % compute total shine
 23    Shine is GlowA+GlowB+GlowC,
 \end{alltt}}
 \end{minipage}\hfill
 \begin{minipage}{.45\linewidth}
 {\scriptsize \begin{alltt}
 24    % make one line of the examples
 25    format('~p,~p,~p,~p,~p,~p,~p,~p,~p',
 26    [Sw1a,Sw2a,Sw3a,Sw1b,Sw2b
 27    ,Sw3b,Sw1c,Sw2c,Sw3c]),
 28    format('~%,~%,~%,~%,~%,~%,~%,~%,~%,~p',
 29    [B1a,B2a,B3a,B1b,B2b,B3b
 30    ,B1c,B2c,B3c,Shine]),nl.
 31
 32 data :- tell('circ.data'),
 33    forall(circuits,true), told.
 34
 35 % some support code
 36 value(Sw,    switch, switch(Sw,_,_)).
 37 value(Light, bulb,bulb(_,Light,_,_)).
 38
 39 :- format_predicate('%',bulbIs(_,_)).
 40
 41 bulbIs(_,bulb(X,_,_,_)) :-
 42      var(X) -> write('?') |write(X).
 43
 44 portray(X) :- value(Y,_,X), write(Y).
\end{alltt}}
\end{minipage}
\caption{\fig{cirtt} expressed in Prolog.} \label{fig:cirtt1}
\end{figure*}
\begin{figure*}
\begin{center}
{\em {\scriptsize
\begin{tabular}{l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l@{,~}l}
Sw1a&Sw2a&Sw3a&Sw1b&Sw2b&Sw3b&Sw1c&Sw2c&Sw3c&
        B1a&B2a&B3a&B1b&B2b&B3b&B1c&B2c&B3c&
        Shine\\\hline
on&off&off&on&off&on&off&on&off&ok&blown&ok&blown&blown&blown&blown&blown&blown&2\\
on&off&off&on&off&on&off&on&off&ok&blown&ok&blown&blown&blown&blown&blown&blown&2\\
on&off&off&on&off&on&off&on&off&ok&blown&ok&blown&blown&blown&blown&blown&blown&2\\
on&off&off&on&off&on&off&on&off&ok&blown&ok&blown&blown&blown&ok&blown&blown&2\\
on&off&off&on&off&on&off&on&off&ok&blown&ok&blown&blown&ok&blown&blown&blown&2\\
on&off&off&on&on&on&off&on&off&ok&blown&ok&blown&blown&blown&blown&blown&ok&2\\\hline
on&off&off&on&off&on&off&on&off&ok&blown&ok&ok&blown&ok&blown&ok&blown&3\\
on&off&off&on&off&on&off&on&off&ok&blown&ok&ok&blown&ok&blown&ok&ok&3\\
on&off&off&on&off&on&off&on&off&ok&blown&ok&ok&blown&ok&blown&blown&blown&3\\\hline
on&off&off&on&off&on&on&on&off&ok&blown&ok&ok&blown&blown&ok&ok&blown&5\\\hline
\end{tabular}
}}
\end{center}
\caption{Some output seen in {\tt circ.data} generated using {\tt
data} (line 32 of \protect\fig{cirtt1}). Columns denote values
from \protect\fig{cirtt}. For example, Sw1a and Sw1b denotes
switch~1 in ciruit~A  and ciruit~A  respectively.}
\label{fig:outs}
\end{figure*}


In order to stress test our method, our case study will wire up
three copies of \fig{cirt} in such a way that solutions to one
copy won't necessarily work in the other copies. \fig{cirtt} shows
our circuit connected by a set of {\em openers} and {\em closers}
that open/close switches based on how much certain   bulbs are
glowing. For example, the {\em closer} between bulb {\em B2A} and
switch {\em Sw1B} means that if {\em B2A} glows then {\em Sw1B}
will be closed. These openers and closers are defined in
\fig{inf3}. The full model is shown in \fig{cirtt1}.



%XXXX circuit seems simple enough- but the openeres anc closers
%ensure that we cant jsut copy treatments from circuit A to B to C since
%what works in one circut might have to be reversed in the next
%circuit.
%Further, even this simple circuit generates a surprising num,ber\of behaviours: 25,000






The less that is known about  a model, the greater the number of
possible behaviors. This effect can easily be seen in our
qualitative model. Each line of \fig{cirt} is labelled with the
number of possibilities it condones: i.e.\[
9*1*9*2*4*2*4*2*4*9*9=3,359,232\]Copied three times, this implies
a space of up to $3,359,232^3=10^{19}$ options. Even when many of
these possibilities are ruled out by inter-component constraints,
the {\tt circuits} relation of \fig{cirtt1} can still succeed
35,228 times (some sample output is shown in \fig{outs}).

Given the goal that the {\em more} lights that shine, the better
the circuit, we assume 10 classes: $0,1,2,3,..9$, one for every
possible number of glowing bulbs. As shown in \fig{baseline},
within the 35,228 runs, there are very few lights shining. In
fact, on average within those runs,  only two lights are shining.
TAR2's mission is to explore the space, trying to find key
decisions which, when applied to the circuit, can most improve
this low level of lighting.

\subsubsection{Round 1} After learning treatments from the all
35,228 initial runs, and applying them to the data, TAR2 generated
\fig{whatif1}.

\begin{figure}[!t]
{\footnotesize
\begin{center}
\begin{tabular}{c}
Untreated circuit \\
\begin{barenv} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setstretch{1} \setyaxis{0}{45}{15}
\setxaxis{0}{9}{1}
\bar{0}{8}  %0
\bar{22}{8} %1
\bar{43}{8} %2
\bar{21}{8} %3
\bar{6}{8}  %4
 \bar{6}{8} %5
\bar{1}{8}  %6
\bar{0}{8}  %7
\bar{0}{8}  %8
\bar{0}{8}  %9
\end{barenv}
\end{tabular}
\end{center}}
\caption{Frequency count of number of bulbs glowing in the 35,228
solutions of {\tt circuits} of
\fig{cirtt1}.}\label{fig:baseline}\label{fig:run1}
\end{figure}
\begin{figure}[!t]
\begin{center}
{\footnotesize
\begin{tabular}{cc}
if Sw2C=off then ... & if Sw3C=on then ...~\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{48}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{47}{8} %4
 \bar{48}{8} %5
\bar{3}{8} %6
\bar{2}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1}  \setyaxis{0}{46}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{15}{8} %4
 \bar{46}{8} %5
\bar{35}{8} %6
\bar{4}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{tabular}}
\end{center}
\caption{Run\#1 of TAR2 over the data seen in
\protect\fig{run1}.}\label{fig:whatif1}
\end{figure}
In summary, \fig{whatif1} is  saying that making a single
decision will change the average illumination of the circuit from
2 to 5 (if Sw2C=off) or 6 (if Sw3C=on).

\indent For exposition purposes, this example assumed that
something prevents our users from making this key decision; i.e.
Sw3C=on. Our experience with incremental treatment learning is
that this is often the case. When users are presented with the
next key decision, they often recall some key knowledge that they
neglected to mention previously. In this case, we assumed that it
is preferable if switch~3 in circuit~C is not  closed- since that
would violate (say) the warranty on circuit~C. Our analysts
therefore agreed to the next best treatment, i.e. Sw2C=off; shown
in \fig{whatif1}, left hand side (LHS).

\subsubsection{Round 2} After constraining the model to
Sw2C=off (i.e. by uncommenting line 5 in \fig{cirtt1}), fewer
behaviors were generated: 3,264 as compared to the 35,228
solutions  seen previously. The frequency distribution of the
shining lights in this new situation is shown in \fig{run2}.
\begin{figure}[!ht]
{\footnotesize
\begin{center}
\begin{tabular}{c}
\protect\fig{cirtt1} when Sw2C=off \\
\begin{barenv} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setstretch{1} \setyaxis{0}{48}{15}
\setxaxis{0}{9}{1}
\bar{0}{8}  %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{47}{8}  %4
 \bar{48}{8} %5
\bar{3}{8}  %6
\bar{2}{8}  %7
\bar{0}{8}  %8
\bar{0}{8}  %9
\end{barenv}
\end{tabular}
\end{center}}
\caption{Frequency count of number of bulbs glowing in the 3,264
solutions of {\tt circuits} of \protect\fig{cirtt1} when
Sw2C=off.} \label{fig:run2}
\end{figure}
\begin{figure}[!b]
\begin{center}
{\footnotesize
\begin{tabular}{cc}
when Sw2c=off then&  when Sw2c=off then\\
if Sw1C=on  then ... & if  B3C=ok then ...~\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{48}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{41}{8} %4
 \bar{42}{8} %5
\bar{9}{8} %6
\bar{8}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1}  \setyaxis{0}{46}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{15}{8} %4
 \bar{46}{8} %5
\bar{35}{8} %6
\bar{4}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{tabular}}
\end{center}
\caption{Run \#2 of TAR2 over the data seen in
\fig{run2}.}\label{fig:whatif2}
\end{figure}
\begin{figure}[!ht]
{\footnotesize
\begin{center}
\begin{tabular}{c}
\protect\fig{cirtt1} when Sw2C=off and Sw1C=on\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{48}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{41}{8} %4
 \bar{42}{8} %5
\bar{9}{8} %6
\bar{8}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{tabular}
\end{center}}
\caption{Frequency count of number of bulbs glowing in the 648
solutions of {\tt circuits} of \protect\fig{cirtt1} when Sw2C=off
and Sw1C=on.}\label{fig:run3}
\end{figure}
\begin{figure}[!b]
\begin{center}
{\footnotesize
\begin{tabular}{cc}
when Sw2C=off & when Sw2C=off \\
and Sw1C=on then &  and Sw1C=on then \\
if  B3C=ok  then ... & if Sw3C=on then ...~\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{32}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{18}{8} %4
 \bar{21}{8} %5
\bar{32}{8} %6
\bar{29}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1}  \setyaxis{0}{50}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{0}{8} %4
 \bar{25}{8} %5
\bar{50}{8} %6
\bar{25}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{tabular}}
\end{center}
\caption{Run\#3 of TAR2 over the data seen in
\fig{run3}.}\label{fig:whatif3}
\end{figure}

Happily, \fig{run2} has the same distribution as
\fig{whatif1}.LHS; i.e. in this case, when the constraints
proposed by TAR2's best treatment were applied to the model, the
resulting new  behavior of the model matched the new behavior
predicted by the treatment.

Executing TAR2 again found the next most informative decision, as
shown in~\fig{whatif2}. Here, TAR2 said that our best treatment
would be to guarantee that bulb~3 in circuit~C is never blown.
Perhaps this is possible if we were to use better light bulbs with
extra long life filaments. However, for the sake of exposition, we
 assumed that there is no budget for such expensive hardware.
Hence, to avoid this expense, our analysts agreed that always
closing switch~1 in circuit~C (as proposed by \fig{whatif2}.LHS)
is an acceptable action.

\subsubsection{Round 3} After  constraining the model to
\mbox{Sw1C=on} (i.e. by uncommenting line 7 in \fig{cirtt1}), fewer
behaviors were generated: 648  as compared to the 3,264  solutions
seen previously. The frequency distribution of the shining lights in
this new situation is shown in \fig{run3}.


\fig{run3} has  the same distribution as \fig{whatif2}.LHS. That
is, once again, TAR2's predictions proved accurate. Executing TAR2
again generated~\fig{whatif3} and finds the next most informative
decision.


The cycle could stop here since the next best treatments are not
acceptable. \fig{whatif3}.LHS wants to use overly expensive hardware
to ensure that bulb~3 in circuit~C is always not blown.
\fig{whatif3}.RHS wants to use an undesirable action and close
switch~3 in circuit~C. However, our engineers have enough information
to propose some options to their manager: if they increase their
hardware budget, they could make the improvements shown in
\fig{whatif3}.LHS. Alternatively, if there was some way to
renegotiate the warranty, then the improvements shown in
\fig{whatif3}.RHS could be achieved.

To verify this, our engineers continue constraining \fig{cirtt1}
to the case of Sw3c=on  by uncommenting line 9 in \fig{cirtt1}.
The resulting distributions looked exactly like \fig{whatif3}.RHS.
Further, only 64 solutions were found. Note that this observation
is consistent with funnel theory:  resolving three of the top
treatments proposed by TAR2 constrained our system to one fifth of
one percent of its original 35,228 behaviors.
\subsection{Case
Study C: Satellite Design}\label{sec:casec}

Our third example is much larger that then two previous. For
reasons of confidentiality, the full details of this third model
cannot be presented here. Further, this model  uses so much
domain-specific knowledge of satellite design that the general
reader might learn little from its full exposition.





Analysts at the Jet Propulsion Laboratory sometimes debate design
issues by building a semantic network connecting design decisions
to requirements~\cite{corn01}. This network links {\em faults} and
risk mitigation {\em actions} that effect a tree of {\em
requirements} written by the stakeholders (see \fig{arrt}).
Potential faults within a project are modelled as influences on
the edges between requirements. Potential fixes are modelled as
influences on the edges between faults and requirements edges.

This kind of requirements analysis seeks to maximize benefits
(i.e., our coverage of the requirements) while minimizing the
costs of the risk mitigation actions. Optimizing in this manner is
complicated by the interactions inside the model - a requirement
may be impacted by multiple faults, a fault may impact multiple
requirements, an action may mitigate multiple faults, and a fault
may be mitigated by multiple actions. For example, in \fig{arrt},
{\em fault2} and {\em require4} are inter-connected: if we cover
{\em require4} then that makes {\em fault2} more likely which, in
turn, makes {\em fault1} more likely which reduces the
contribution of {\em require5} to {\em require3}.

The net can be executed by selecting actions and seeing
what benefits results.  One such network included 99
possible actions; i.e. $2^{99}\approx 10^{30}$ combinations
of actions.
The data cloud of \fig{clouds}.ii was generated after 10,000 runs where each
run selected at random from the 99 options. Note the wide variance
in the possible behaviors.



The results of incremental treatment learning is shown in
\fig{jpleg}. The first percentile matrix (called {\bf round 0})
summarizes \fig{clouds}.ii. As with all our other examples, as
incremental treatment learning is applied, the variance is reduced
and the mean values improve (compare {\bf round 0} with {\bf round
4} in \fig{jpleg}). In a result consistent with funnel theory,
TAR2 could search a space of $10^{30}$  decisions to find 30 (out
of 99) that crucially effected the cost/benefit of the satellite;
i.e. TAR2
 found 99-30=69 decisions that can be ignored~\cite{fea02a}.



\begin{figure}[!t]

\begin{center}
\includegraphics[width=3.5in]{arrt.eps}
\end{center}

{\small \begin{description} \item[Faces] denote requirements;
\item[Toolboxes] denote actions; \item[Skulls] denote faults;
\item[Conjunctions] are marked with one arc; e.g. {\em require1} if
{\em require2} and {\em require3}. \item[Disjunctions] are marked
with two arcs; e.g. {\em fault1} if {\em fault2} or {\em fault3}.
\item[Numbers] denote impacts; e.g. {\em action5}
 reduces the contribution of {\em fault3} to {\em fault1}, {\em
fault1} reduces the impact of {\em require5}, and {\em
action1} reduces the negative impact of {\em fault1}.
\item[Oval]   denotes structures that are expressible in
the latest version of the JPL semantic net editor (under construction).
\end{description}}
  \caption{Above: a
   semantic net of the type used at JPL~\cite{fea01} Below: explanation of symbols.
  }\label{fig:arrt}
\end{figure}
\begin{figure}[!t]
\begin{center}
{\footnotesize {\bf round 0:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &             &   \sq{6}{94}     &  \sq{15}{85}     &   \sq{5}{95}    &   \sq{26}{74}    \\
 200          &   \sq{1}{99}      &  \sq{22}{78}       & \sq{27}{75}      &  \sq{4}{96}      &  \sq{54}{48}      \\
 150          &   \sq{1}{99}    &   \sq{6}{94}      &   \sq{5}{95}     &   \sq{1}{99}   &   \sq{13}{87}    \\
 100          &             &   \sq{3}{97}      &   \sq{3}{97}    &         &  \sq{6}{94}   \\
 50           &             &   1\%      &         &         &    \sq{1}{99}   \\\hline
 Totals       &   \sq{2}{98}      &  \sq{38}{62}    & \sq{50}{52}  &  \sq{10}{90} &  \sq{100}{2} \\\hline
\end{tabular}\vspace{0.25in}

{\bf round 1:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &       \sq{7}{93}      &  \sq{45}{44}    &  \sq{13}{87}      &         &    \sq{65}{35}    \\
 200          &      \sq{12}{88}      & \sq{22}{78}     &   \sq{1}{99}    &         &    \sq{35}{65}     \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &      \sq{19}{81}      &  \sq{67}{33}       &  \sq{14}{86}   & \sq{~}{99} &   \sq{100}{1}    \\\hline
\end{tabular}\vspace{0.25in}


{\bf round 2:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &        \sq{9}{91}   &   \sq{8}{92}      & \sq{7}{93}     &         &  \sq{24}{76}      \\
 200          &     \sq{18}{82}      &  \sq{58}{41}    &       &         &      \sq{76}{23}   \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &       \sq{27}{73}     &   \sq{66}{33}      & \sq{7}{93}    &  \sq{~}{99}  &     \sq{101}{1}  \\\hline
\end{tabular}\vspace{0.25in}


{\bf round 3:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &    \sq{9}{91}    &  \sq{70}{30}     &   \sq{11}{89}     &         & \sq{90}{10}      \\
 200          &    \sq{3}{97}      &    \sq{7}{93}      &       &         &  \sq{10}{90}       \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &     \sq{12}{88}     &   \sq{77}{23}      & \sq{11}{89}    &  \sq{~}{99}  &   \sq{100}{1}   \\\hline
\end{tabular}\vspace{0.25in}


{\bf round
4:}\begin{tabular}{c|@{~}rrrr|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &      \sq{1}{99}       &  \sq{81}{18}     &  \sq{17}{83}      &         &  \sq{99}{1}      \\
 200          &             &   \sq{1}{99}      &       &         &       \sq{1}{99}  \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &   \sq{1}{99} &  \sq{82}{17}     & \sq{17}{83}    &   \sq{~}{99} &     \sq{100}{1}  \\\hline
\end{tabular}
}\end{center} \caption{Percentile matrices showing four rounds of incremental
treatment learning for   JPL
satellite design. The data clouds for {\bf round 0} and {\bf round 4} appear
as \fig{clouds}.ii and \fig{clouds}.iv (respectively).}\label{fig:jpleg}
\end{figure}



For comparison purposes, a genetic algorithm  (GA) was also
applied  to the same problem of optimized satellite
design~\cite{corn02}. The GA also found decisions that generated
high benefit, low cost projects. However, each such GA solution
commented on every possible decisions and there was no apparent
way to ascertain which of these are the most critical decisions.
The TAR2 solution was deemed superior to the GA solution by the
domain experts, since the TAR2 solution required just 30 actions.



\section{When Not to Use Incremental Treatment Learning}\label{sec:whennot}

Our approach  is an inexpensive method of generating coarse-grained
controllers from rapidly written models containing uncertainties.
This kind of solution is inappropriate for certain classes of
software such as mission critical or safety critical systems. For
those systems, analysts should move beyond TAR2 and apply more
elaborate modelling methods and extensive data collection to ensure
exact and optimal solutions.

There are several other situations where incremental treatment
learning should not be used. When trusted and powerful heuristics
are available for a model, then a heuristic search for model
properties may yield insight than   random trashing within a
model. Such heuristics might be modelled via (e.g.) fuzzy
membership functions or bayesian priors reflecting expert
intuitions on how variables effect each other. Of course, such
heuristics must be collected, assessed, and implemented. When the
cost of such collection and assessment and implementation is too
great, then our approach could be a viable alternative.

Also, our approach requires running models many thousands of times
and therefore can't be applied to models that are too expensive or
too slow to execute many times. For example: \bi \item It may be
too expensive or dangerous to conduct Monte Carlo simulations of
in-situ  process control systems for large chemical plants or
nuclear power stations. \item Suppose some embedded piece of
software must be run on a specialized hardware platform. In the
case where several teams must access this platform (e.g. the test
team, the development team, the government certification team, and
the deployment team), then it may be impossible to generate
sufficient runs for incremental treatment learning.

\item Many applications connect user actions on some graphical
user interface   to database queries and updates.  Monte Carlo
simulations of such applications may be very slow since each
variable reference might require a slow disk access or a user
clicking on some ``OK'' button.  An ideal application suitable for
incremental treatment learning comprises a {\em separate  model}
for the business logic which can be executed without requiring
(e.g.) screen updates or \\database accesses.

\ei

\section{Related Work}\label{sec:related}


\subsection{Prior TAR2 Results}
Other publications on treatment learning
 have assumed a ``one-shot'' use of TAR2~\cite{hu02,me01f,me01h,me02a}.
 This paper assumes an iterative
 approach. Our experience with users is that this iterative approach encourages
 their participation in the process and increases their sense of ownership
 in the conclusions.

\subsection{Entropy-Based Learners}

TAR2's treatments might be viewed as the attributes that most inform
the decision making process. Holders of that view might therefore
argue that treatments could be better formed using entropy measures
of information content.  Many machine learners have used such
measures including the top-down decision tree induction algorithm
C4.5~\cite{quinlan92}. The attribute  that offers the largest {\em
information gain} is selected as the root of a decision tree. The
example set is then divided up according to which examples do/do not
satisfy the test in the root. For each divided example set, the
process is then repeated recursively. The {\em information gain} of
each attribute is calculated as follows. A tree $C$ contain $p$
examples of some class  and $n$ examples of other classes. The {\em
information required} for the tree $C$ is as
follows~\cite{quinlan86}:

{\small
\[ I(p,n) =
-\left(\frac{p}{p+n}\right)log_2\left(\frac{p}{p+n}\right) -
\left(\frac{n}{p+n}\right)log_2\left(\frac{n}{p+n}\right)\]}

\noindent
Say that some attribute $A$ has values $A_1, A2,... A_v$. If
we select $A_i$ as the root of a new sub-tree within $C$, this will
add a sub-tree $C_i$ containing those objects in $C$ that have $A_i$.
We can then define the expected value of the information required for
that tree as the weighted average:

{\small \begin{equation}\label{eq:v}
E(A) =
\sum^{v}_{i=1}\left(\frac{p_i + n_i}{p + n}\right)I(p_i,
n_i)\end{equation}}

\noindent The information gain of branching on $A$ is therefore:

{\small
\[ gain(A) = I(p,n) - E(A)
\]}

\noindent \fig{tree}.A shows the kind of decision tree generated
using C4.5 from 506 examples. \fig{tree}.B shows the treatment learnt
by TAR2 from the same data. Note that the treatment is much smaller
that the tree learnt by C4.5. It turns out that C4.5's information
measure is not the best method for forming treatments. \eq{v} selects
attributes that most reduce the diversity of classes seen in the
examples that fall into a subtree. Treatment learners needs a
different kind of measure; i.e. one that that finds attribute ranges
which  occur more frequently in desired classes than in the undesired
classes.
\begin{figure*}
{\em \fig{tree}.A: A learnt decision tree from C4.5. Classes
(right-hand-side), top-to-bottom, are
 ``high'',
``medhigh'', ``medlow'', and ``low'' This indicates median value of
owner-occupied homes in \$1000's.}
\begin{center}
\includegraphics[height=5in,width=5in]{tree.eps}
\end{center}

{\em \fig{tree}.B: Treatments learnt in the same domain:}
{\scriptsize
\begin{center}
\begin{tabular}{|c|c|c|}\hline
Treatment & nothing & $6.7         \leq RM       < 9.8$    \\
                &   & $\wedge 12.6 \leq PTRATION < 15.9 $  \\\hline
&&\\
&&\\
Results& ~~~~\begin{barenv} \setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}\sethspace{0.5} \setyaxis{0}{100}{25}
  \bar{21}{1}
 \bar{21}{2}
 \bar{29}{4}
 \bar{29}{8}
\end{barenv}
& ~\begin{barenv} \setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}\sethspace{0.5} \setyaxis{0}{100}{25}
   \bar{0}{1}
 \bar{0}{2}
 \bar{3}{4}
 \bar{97}{8}
\end{barenv}
\\&&\\\hline
N &506& 38 \\\hline
\end{tabular}
\end{center}}
\caption{Theories learnt by C4.5 and TAR2 from the 506 cases in
HOUSING example from the UC Irvine machine learning repository
(\protect\url{http://www.ics.uci.edu/~mlearn/MLRepository.html}). The
bottom table shows the distributions of the classes in the example
set (left-hand-side) and the results of the learnt treatment
(right-hand-side). In the treatment ``PTRATIO'' denotes the
pupil-teacher ratio by town and ``RM'' denotes the average number of
rooms per dwelling. }\label{fig:tree}
\end{figure*}

Decision tree learners like C4.5 can be used as a pre-processor to
treatment learning. The TAR1 system (called TARZAN)~\cite{me00e}
swung through the decision trees generated by C4.5 and 10-way
cross-validation. TARZAN returned the smallest treatments that
occurred  in most of the ensemble that {\em increased} the percentage
of branches leading to some preferred highly weighted classes and
{\em decreased} the percentage of branches leading to lower weighted
class. TAR2 was as experiment with applying TARZAN's tree pruning
strategies directly to the C4.5 example sets. The resulting system is
simpler, fast to execute, generates smaller theories that C4.5, and
does not require calling a learner such as C4.5 as a sub-routine.


\subsection{Association Rule Learning}

Another way to categorize TAR2 is a {\em weighted-class minimal
contrast-set} association rule learner that uses {\em confidence
measures} but not {\em support-based pruning}. This section discusses
those terms.

Top-down decision tree classifiers like C4.5 and
CART~\cite{breiman84} learn rules with a single attribute pair on the
right-hand side; e.g. {\em class= goodHouse}. Association rule
learners like APRIORI~\cite{agrawal94} generate rules containing
multiple attribute pairs on both the left-hand-side and the
right-hand-side of the rules. That is, classifiers have a small
number of pre-defined targets (the classes) while, for association
rule learners, the target is less constrained.

General association rule learners like APRIORI input a set of $D$
transactions of items $I$ and  return associations between items of
the form $LHS \Rightarrow RHS$ where $LHS \subset I$ and $RHS \subset
I$ and $LHS \cap RHS = \emptyset$. In the terminology of APRIORI, an
association rule has {\em support} $s$ if $s\%$ of the $D$ contains
$X \wedge Y$; i.e. $s=\frac{|X \wedge Y| }{|D|}$ (where $|X \wedge
Y|$ denotes the number of examples containing both $X$ and $Y$). The
{\em confidence} $c$ of an association rule is the percent of
transactions containing $X$ which also contain $Y$; i.e. $c=\frac{|X
\wedge Y|}{|X|}$. Many association rule learners use {\em
support-based pruning} i.e. when searching for rules with high
confidence, sets of items $I_i,... I_k$ are only be examined only if
all its subsets are above some minimum support value.

Specialized association rule learners like CBA~\cite{liu98} and  TAR2
impose restrictions on the right-hand-side. For example, TAR2's
right-hand-sides show a prediction of the  {\em change} in the class
distribution if the constraint in the left-hand-side were applied.
The CBA learner finds {\em class association rules}; i.e. association
rules where the conclusion is restricted to one classification class
attribute. That is, CBA acts like a classifier, but can process
larger datasets that (e.g.) C4.5. TAR2 restricts the right-hand-side
attributes to just those containing criteria assessment.

A common restriction with classifiers is that they assume the entire
example set can fit into RAM. Learners like APRIORI   are designed
for data sets that need not reside in main memory. For example,
Agrawal and Srikant report experiments with association rule learning
using very large data sets with 10,000,000 examples and size
843MB~\cite{agrawal94}. However, just like Webb~\cite{webb00}, TAR2
makes the ``memory-is-cheap assumption''; i.e. TAR2 loads all it's
examples into RAM.

Standard classifier algorithms such as C4.5  or CART have no concept
of class {\em weighting}. That is, these systems have no notion of a
{\em good} or {\em bad} class. Such learners therefore can't filter
their learnt theories to emphasize the location of the {\em good}
classes or {\em bad} classes. Association rule learners such as
MINWAL~\cite{cai98}, TARZAN~\cite{me00e} and TAR2  explore
  {\em weighted   learning} in which
     some items are given a higher priority weighting that
     others.
     Such
      weights can focus the learning  onto issues that are of
     particular interest
     to some audience.

Support-based pruning is impossible in weighted
  association rule learning since  with
  weighted items, it is not always true that subsets of
  {\em interesting} items (i.e. where the weights are high) are also
  interesting~\cite{cai98}.
Another reason to reject support-based pruning is that it can force
the learner to only miss
  features that apply to a small, but interesting subset
  of the examples~\cite{wang00}.
 Without support-based pruning,
association rule learners rely on confidence-based pruning to reject
all rules that fall below a minimal threshold of adequate confidence.
TAR2's analogue of confidence-based pruning is the   $\Delta$ measure
shown in \tion{funn}.

 One interesting specialization of association
rule learning is {\em contrast set learning}. Instead of finding
rules that describe the current situation, association rule learners
like STUCCO~\cite{bay99} finds rules that differ meaningfully in
their distribution across groups. For example, in STUCCO, an analyst
could ask "what are the differences between people with Ph.D. and
bachelor degrees?". TAR2's variant on the STUCCO strategy is to
combine contrast sets with weighted classes with minimality. That is,
TAR2 treatments can be viewed as the smallest possible contrast sets
that distinguish situations with numerous highly-weighted classes
from situations that contain more lowly-weighted classes.





\subsection{Funnel Theory}
 Our development on funnel theory owes much to the
deKleer's ATMS (assumption-based truth maintenance
system)~\cite{deKleer86}.
 As new inferences are made,
the ATMS updates its network of dependencies and sorts out the
current conclusions into maximally consistent subsets (which we would
call worlds). {\em Narrow funnels} are analogous to  {\em minimal
environments of small cardinality} from the ATMS research. However,
funnels differ from the ATMS. Our view of funnels assume a
set-covering semantics and not the consistency-based semantics of the
ATMS (the difference between these two views is detailed in
~\cite{console91}). The worlds explored by funnels only contain the
variables seen in the subset of a model exercised by the supplied
inputs. An ATMS world contains a truth assignment to every variable
in the system. Consequently, the user of an ATMS may be overwhelmed
with an exponential number of possible worlds. In contrast, our
heuristic exploration of possible worlds, which assumes narrow
funnels, generates a more succinct output. Further, the ATMS is only
defined for models that generate logical justifications for each
conclusion. Iterative treatment learning is silent on the form of the
model: all it is concerned with is that a model, in whatever form,
generates outputs that can be classified into desired and undesired
behavior.

\subsection{Fault Trees}

We are not the first to note variability in knowledge extracted
from users. Leveson~\cite{levenson96} reports very large variances
in the calculation of root node  likelihood in software fault tree
analysis: \bi \item In one case study of 10 teams from 17
companies and 9 countries, the values computed for root node
likelihood  in trees from different teams differed by a factor of
up to 36. \item When a unified fault tree was produced from all
the teams, disagreements in the internal probabilities of the tree
varied less, but still by a factor of   10. \ei

The work presented here suggests a novel method to resolve
Leveson's problem with widely varying root node liklihoods. If
funnel theory is correct, then   within the space of all
disagreements in the unified fault tree, there exist a very small
number  of key values that crucially impact the root node
likelihood. Using TAR2 the feuding teams could restrict their
debates to just those key decisions.

\subsection{Bayesian Reasoning}

We do not use
 Bayesian reasoning for uncertain
 models for the same reason we don't use computational
 intelligence methods. Recall from our introduction that this work assumes
 {\em metrics starvation}:
 i.e. the absence of relevant domain expertise or
 specific numeric values in the domain being studied.
 Bayesian methods
 have been used  to sketch out
subjective knowledge (e.g. our software management oracle), then
assess and tune that knowledge based on available data. Success
with this method includes the COCOMO-II effort estimation
tool~\cite{chulani99} and defect prediction
modelling~\cite{fenton99}.    In the domains   where statistical
data on   cause-and-effect are lacking (e.g. our metrics starved domains),
 we have to approximate (i.e guess/make-up) some
values to describe the model. Since there are too many
uncertainties  within the model, Bayesian reasoning may not yield
stable result.


\subsection{Simulation for Decision Making}

Other research has explored simulation for making design decisions.
Bricconi et al.~\cite{bricc00} built a simulator of a server on a
network, then assessed different network designs based on their
impact on the server. Menzies and Sinsel assessed software project
risk by running randomly selected combinations of inputs through a
software risk assessment model~\cite{me00e}. Josephson et
al.~\cite{joseph98} executed all known options in a car design to
find designs that were best for city driving conditions. Bratko et
al.~\cite{bratko89} built qualitative models of electrical circuits
and human cardiac function. Where uncertainty existed in the model,
or in the propagation rules across the model, a Bratko-style system
would backtrack over all possibilities.


Simulation is usually paired with some
  summarization technique. Our research was prompted by certain short-comings
  with the summarization techniques
   of others. Josephson et al. used {\em dominance filtering}
   (a Pareto
decision technique) to reduce their millions of designs down to a few
thousand options. However, their techniques are silent on automatic
methods for determining the difference between dominated and
undominated designs. Bratko et al. used standard machine learners to
summarize their simulations. Menzies and Sinsel attempted the same
technique, but found the learnt theories to be too large to manually
browse. Hence, they evolved a tree-query language (TAR1) to find
attribute ranges that were of very different frequencies on decision
tree branches that lead to different classifications. TAR2 grew out
of the realization that all the TAR1 search operations could be
applied to the  example set directly, without needing a decision tree
learner as an intermediary. TAR2 is hence much faster than TAR1
(seconds, not hours).

\section{Conclusion}

When not all values within a model are known with certainty,
analysts have at least three choices. Firstly, they can take the
time to nail down those uncertain ranges. This is the preferred
option. However, our experience strongly suggests that funding
restrictions and pressing deadlines often force analysts to make
decisions when many details are uncertain.

Secondly,  analysts might use some sophisticated uncertainty
reasoning scheme like
 bayesian inference or the computational intelligence methods such as neural nets,
genetic algorithms or fuzzy logic. These techniques require some minimal knowledge of
expert opinion, plus perhaps some historical data to tune that knowledge. In situations
of metrics starvation, that knowledge is unavailable.

This paper has explored a third option: try to understand a model
by surveying the space of possible model behaviors. Such a survey
can generate
 a data cloud: a dense mass
of possibilities with  such a wide variance of output values that
they can confuse, not clarify, the thinking of our analysts. However,
in the case of data clouds generated from models containing narrow
funnels, there exist key decisions which can condense that cloud.

Incremental treatment learning is a method for controlling the
condensation of  data clouds. At each iteration, users are
presented with list of treatments that have most impact on a
system. They select some of these and the results are added to a
growing set of constraints for a model simulator. This
human-in-the-loop approach increases user ``buy-in'' and allows
for some human control of where a data cloud condenses. In the
case studies shown above, data clouds where condensed in such a
way as to decrease variance and improve the means of the behavior
of the model being studied.

As stated in the introduction, there are several implications of
this work. Even when we don't know exactly what is going on with a
model, it is often possible to: \bi \item Define minimal
strategies that grossly decrease the uncertainty in that model's
behavior. \item Identify which decisions are redundant; i.e. those
not found within any funnel.\ei Also, when modelling is used to
assist decision making, it is possible to reduce the cost of that
modelling: \bi \item Even hastily built models containing much
uncertainty can be used for effective decision making. \item
Further, for models with narrow funnels, elaborate and extensive
and expensive data collection may not be required prior to
decision making.\ei

TAR2 exploits narrow funnels and is a very simple method for finding
treatments at each step of iterative treatment learning. Iterative
treatment learning is applicable to all models with narrow funnels.
Empirically and theoretically, there is much evidence that many
real-world models have narrow funnels. To test if a model has narrow
funnels, it may suffice just to try TAR2 on model output. If a small
number of key decisions can't be found, then iterative treatment
should be rejected in favor of more elaborate techniques.

\section*{Acknowledgements}

This paper benefitted greatly from the remarks of the anonymous
reviewers.  This research was conducted at West Virginia University;
the University of British Columbia, Vancouver, Canada; and at the Jet
Propulsion Laboratory, California Institute of Technology under NASA
contract NCC2-0979. The work was sponsored by the NASA Office of
Safety and Mission Assurance under the Software Assurance Research
Program led by the NASA IV\&V Facility.  Reference herein to any
specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States Government or the Jet Propulsion
Laboratory, California Institute of Technology.

\bibliographystyle{abbrv}
{\footnotesize \bibliography{refs}}

\end{document}

In our preferred model of arguing about uncertainties: \bi \item
Humans {\em grow} the space of options by writing a model. \item
Next,  the computer {\em culls} the less useful options and
reports the key decisions that most effect the system's behavior.
\ei This can be a fruitful partnership. Focusing experts attention
on the relatively small number of most critical decision
alternatives makes much more effective use of their skill and
knowledge. Further, assuming narrow funnels, the number of key
decisions will be very small and experts will have to argue less;
i.e. only about the small number of key values.

This approach   reduces the number of total decisions to a small
number of key decisions. However, this approach does not {\em
resolve} or {\em remove} those key arguments. This is quite
deliberate. Arguments will not and should not go away. Arguments
are an important part of any collaborative work. To be human, to
be an expert, to be an individual, implies that you often take a
different stance to your peers. Arguing such different stances
generates heat and light and insights into a domain that may
remain hidden otherwise.

Nevertheless, we cannot endorse arguments unless we also show how
to prevent the unconstrained arguments that block the unification
of work pieces generated in parallel. Humans must be free to argue
about anything they like. But in a resource-bounded situation
(e.g. any software development process), we can argue less by
sorting our arguments according to their ability to reduce the
variance and improve the mean behavior of a model.
