

% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps.
% 
% form to use if the first word consists of a single letter:
% \PARstart{A}{demo} file is ....
% 
% form to use if you need the single drop letter followed by
% normal text (unknown if ever used by IEEE):
% \PARstart{A}{}demo file is ....
% 
% Some journals put the first two words in caps:
% \PARstart{T}{his demo} file is ....
% 
% Here we have the typical use of a "T" for an initial drop letter
% and "HIS" in caps to complete the first word.
\section{Introduction}
\PARstart{S}{oftware}
engineering is modeling~\cite{schmidt06}.  
Software engineers build
models at every phase of the life cycle.
Some are paper-based and some are executable but all these artifacts
are 
 \emph{models} which 
Mellor~\cite{mellor03} defines to be
 ``elements
describing something (for example, a
system, bank, phone, or train) built for some
purpose that is amenable to a particular form
of analysis, such as
communication of ideas between people
and machines;
completeness checking;
test case generation; etc.''
Models
are used throughout the software development process --
 from requirements and design to testing and performance evaluation
 -- and that use models will only increase.  

Even with tool support, creation of practical and
 functional models is a resource-intensive activity.
 Effective use of models requires
 that they be allowed to evolve through the software development
 process.  Other researchers  have recognized that ``designers must
 be able to examine various design alternatives quickly and easily
 among myriad and diverse {\em configuration possibilities}''\cite{gray06}.
%Finding an appropriate and effective balance between human intelligence and automation can be a recondite task.  

The number of 
configuration possibilities within a model can be dauntingly large. A model with
20 binary choices has $2^{20}>1,000,000$
possible configurations, far beyond the capability of human
comprehension. Standard model comprehension methods such as design
of experiments have limited utility 
when the model is non-continuous, very large, or 
contains noise. 

Hence, since 2000, we have been
exploring model comprehension using
data miners.
After randomly sampling
those configurations, running the resulting model, scoring
the output with some oracle, our data miners
are used to
configure options that  most improve model output~\cite{burk04,fea02a,gel03a,hu02,me00e,me01e,me02h,me03g,me03i,me03j,me03l,me05e,me06a,me06b,owen02a}.
This paper
synthesizes that prior work 
and presents new case studies.
Originally, our work was inspired by Bratko's combination of qualitative
modeling and data mining~\cite{bratko89}. 
We found that standard data miners 
may be
inadequate for exploring
model configuration possibilities
since they
often
yield results that 
are incomprehensible to humans:
\bi
\item
Neural nets never generate
a succinct generalization of their knowledge~\cite{hinton92};
\item
The random search of genetic algorithms can produce models that are too
complex to understand~\cite{witten99};
\item
Most decision/regression tree learners such as C4.5~\cite{quinlan86}
or CART~\cite{breiman84}
execute in local top-down
search, with no memory between different branches.  Hence, the same concept
can be needlessly repeated many times within the tree.
Consequently, such trees can be  cumbersome, needlessly large, and
difficult to understand.  \ei

The
detailed, complex and arcane output generated by standard data miners is
often superfluous. Firstly, many
human experts can not (or will not)
read complex theories learned by a data miner.
Secondly, 
numerous empirical and theoretical results argue that, in the usual case,
models are controlled by a handful of  of key variables.
If data miners are restricted to just returning models containing those keys,
then the learned model will be very small indeed.

Thus, we propose a different kind of data miner to assist analysts
in exploring the configuration possibilities within their models.
Traditional machine learners like C4.5
generate classifiers that assign a class symbol to an
example.
Our preferred method, called {\em
treatment learning} generates just the {\em differences}
in the key variables
among different outcomes.

The rest of this paper is structured as follows. 
The twin topics of
model-based SE and search-based SE are introduced.
A special case of {\em hard models} are discussed that are difficult
to manage using standard methods.
Evidence is then presented that, often,
the key variables that control a
model are few in number.
The problem of hard models therefore can be reduced to just the
problem of understanding the key variables.
This will motivate the design of the TAR2 {\em treatment learner}.
Case studies will then be presented showing that, in many domains,
TAR2 finds a small number of controlling variables.
Such succinct controllers have many
advantages:
\bi
\item
Smaller models are easier to explain (or audit).
\item 
Miller has shown that models
generally containing fewer variables
have less variance in their outputs~\cite{miller02}.
\item
The smaller the model, the fewer are the demands on interfaces 
(sensors and actuators) to the
external environment.
Hence, systems designed around 
small models
are easier to use (less to do)
and cheaper to build.
\ei

In short,  for a certain class of {\em hard modeling}
problems, the TAR2 treatment learner can dramatically simplify the
task of understanding the configuration
possibilities within model-based SE.
Hence, our conclusion will be that it is useful to augment standard modeling methods
with treatment learning.
As to other modeling problems,
TAR2 is {\em not} indicated  
for low-dimensionality
linear continuous models built in domains that have no noise or other
uncertainties, and where managers have full control over all model inputs.


\section{Modeling and Search}

\PARstart{A}nthropologists argue that the ability to build abstract models is
what gives homo sapiens their competitive
edge.   In his article ``What Models Mean" \cite{seidewitz03},
Seidewitz describes the interactions and relationships among the
concepts of a model.  
He asserts that ``a model's meaning has two
aspects: the model's relationship to what's being modeled and to
other models derivable from it.  Carefully considering both aspects
can help us to understand how to use models to reason about the
systems we build ..."  These are the aspects of a model's meaning on which we focus
in \emph{model-based} software engineering.

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

The utility of model-based SE is widely
acknowledged.
For example, the 
Object Management Group
(OMG) has recently adopted a \emph{model-driven architecture}
framework with goals of ``portability, interoperability and reusability
through architectural separation of concerns." \cite{omg03}  
%(See also \cite{frankel03}.)  OMG uses the established standard of UML,
%the Common Warehouse Metamodel, and the Meta-Object Facility to
%provide system interoperability in a vendor-neutral form. \cite{brown06}.
Also, Microsoft has been developing a \emph{Software Factory} concept
that leverages models with the goal of automation of the software
development process~\cite{greenfield04}.  And, at Lockheed Martin, engineers
have developed an integrated modeling method
called \emph{Model Centric Software Development}
that uses ``automated generation of partial
implementation artifacts," reverse engineering to integrate legacy
assets, and model verification and checking~\cite{waddington03 }
 
 The importance of models and the model-driven approach is not
 limited to software design and UML. 
Many tools exist for 
modeling such as distributed agent-based
simulations~\cite{clancey96a}, discrete-event
simulation~\cite{law00,harrell00,kelton02,raffo05b,raffo05c},
continuous
simulation (also called system dynamics)~\cite{hamid91,sterman00},
state-based simulation (which includes petri net and data flow
approaches)~\cite{akhavi93,harel90,martin00},
hybrid-simulation (that combines discrete event simulation and systems
dynamics)~\cite{martin01,donzelli01,setamanit07},
logic-based and qualitative-based methods~\cite[chapter
20]{bratko01}~\cite{iwasaki89}, and rule-based
simulations~\cite{mi90}. 
One can find
 models used in the requirements phase (see the DDP method and tool
 \cite{feather03} which are a risk-based approach and visual tool
 to support requirements engineering), refactoring of designs using
 patterns \cite{france03}, software integration \cite{denno03},
 model-based security \cite{jurjens06}, and performance assessment
 \cite{bals04}.


Model are useful since
humans can review/audit/improve an explicit representation of their
systems. 
%But manual inspection is often insufficient to reveal the subtleties of a model.
%Even very simple models can hide a surprising number of errors.
%Consider, for example, a simple mathematical model of 
%population growth.  
%\begin{equation} \label{eq11} \frac{dN}{dT} = rN \end{equation}
%Here, \emph{r} is a constant reflecting environmental conditions, \emph{T} is time, and \emph{N} is the
%population. Note that this model is not accurate since population growth must taper off as it
%approaches \emph{c}, the maximum carrying capacity of the environment; i.e.
%\begin{equation}
%\label{eq2}
%\frac{dN}{dT} = rN\left(1-\frac{N}{c}\right)
%\end{equation}
%Before reading further, we ask the reader to consider whether
%equation \#\ref{eq2} is an appropriate model of population growth?
%If the reader cannot see all the subtleties in a one-line model, then we
%should be suspicious of claims that the truth status of larger
%models can be accurately determined by manual analysis.
%Although equation \#\ref{eq2} does model our intuition in some
%cases, there is one situation in which it is clearly incorrect.
%Consider the case of over-population in an hostile environment: $N
%> c, r < 0$.  Our intuition is that, in that situation,
%the population will fall.
%However, with these assumptions $rN(1-(N/c)) > 0$.  That is, our
%model concludes that the population will {\em increase}  (example
%taken from \cite{puccia85}.)   
%
%Our experience has been that this error in this simple
%model is not apparent to many people.  Myers~\cite{myers77} reports
%a similar conclusion, but using  a 63 line model.  In this
%experiment, 59 experienced IT professionals searched for errors in
%a very simple text formatter that consisted of 63 lines of PL/1
%code. Even with unlimited time and the use of three different
%methods, 73 of the experts could only find (on average) 5 of the
%15 errors in this 63 line model \cite{myers77}. This result, despite
%its age, and the previous thought experiment do not inspire confidence
%that experts can accurately assess larger models.
%%
%%This phenomenon of models hiding errors is not limited to software.  Consider the  results
%%of the Feldman and Compton study in which 109 of 343 (32\%) of the
%%known data points from six studied papers could not be explained
%%using a glucose regulation model developed from international
%%refereed publications~\cite{fecosm89a, fecosm89b, smythe89}. A
%%subsequent study corrected some modeling errors of Feldman and
%%Compton to increase the inexplicable percentage from 32\% to 45\%.
%%A similar study successfully faulted another smaller published
%%scientific theory \cite{menzies92}.
%
But as models grow in complexity, it becomes difficult for a manual
analysis to reveal all their subtleties.
Hence, many researchers propose
support environments
to help explore the increasingly complex models that engineers are
developing. Gray, at al, \cite{gray06} have developed the
Constraint-Specification Aspect Weaver (C-Saw) that uses aspect-oriented
approaches \cite{filman04} to help engineers in the process of
model transformation.  Cai and Sullivan \cite{cai05} describe a
formal method and tool called \emph{Simon} that ``supports interactive
construction of formal models, derives and displays design structure
matrices ... and supports simple design impact analysis."  Other tools
of note are lightweight formal methods such as ALLOY~\cite{jackson02}
and SCR~\cite{heitmeyer02} as well as  various UML tools that
allow for the execution of life cycle specifications (e.g.
the
CADENA scenario editor~\cite{child06}).

Recently, AI has been successful
applied to
model-based SE.
For example,
Whittle uses deductive learners to
generate lower-level UML designs (state charts)
from higher-level constructs (use case diagrams)~\cite{whittle06}.
More generally, the field of
{\em search-based SE} augments
model-based SE with \emph{meta-heuristic} techniques, like genetic
algorithms, simulated annealing, etc., to explore
a model.
Such heuristic methods are hardly complete but, as Clarke
et.al.~\cite{clarke03} remark: ``...software engineers face problems
which consist, not in finding \emph{the} solution, but rather, in
engineering an \emph{acceptable} or \emph{near optimal solution}
from a large number of alternatives."~\cite{clarke03}.

Search-based SE
is most often used to optimizing software
testing~\cite{jones96a, jones98, pargas99, tracey98}
but it has
had
application in numerous other areas.
With Feather, we  have used
search-based SE for requirements analysis~\cite{feather03}.
Other researchers~\cite{harman02, lutz01}
use genetic algorithms to examine ways of modularizing
software~\cite{clarke03} or developing effort
estimators~\cite{aguilar01,dolado00, dolado01}.  
In all,
Rela~\cite{rela04} lists 123 publications where search-based
methods have been applied
to the above applications as well as
automatic synthesis  of software defect predictors; assisting in
component design; developing multiprocessor schedules; re-engineering
old systems into a better one; and searching for compiler optimizations.

To use a search-based approach, software engineers have to reformulate their 
problem by:
\bi
\item
Finding a {\em representation of the problem} that can be 
symbolically manipulated (e.g. simulated or mutated). 
Such representations always exist with model-based SE.
\item
Defining a {\em fitness function} (a.k.a. ``utility function'''' or
``objective function''); i.e.
an ``oracle'' that
scores a model configuration. Current model-based SE methods rarely offer
such a function (exception: formal methods that generate temporal constraints). In our experience, generating such a fitness function is
usually possible, albeit requiring days of work with the domain experts~\cite{me99j}.
\item 
Determining an appropriate set of {\em manipulation operators} 
to select future searches based on the prior
searches~\cite{harman01}.  
\ei

Data mining is one way to implement automatic manipulation operators.
A data miner  searches through the space of possible concepts for
a combination of concepts that describes some target
theory~\cite{mitchell97}.  Given, say, the output from a Monte Carlo
simulation of  a model, a $21^{st}$ century data miner can sift
through gigabytes of data looking for the core concepts that most
select for preferred output.


\section{``Hard Modeling'' Problems}\label{sec:easyhard}
\PARstart{B}efore describing our research into data mining for automatically
generating manipulation operators,
we must motivate why we don't use
traditional methods. 
As argued in the section, we seek constraints to model inputs that
are
{\em satisficing} (so, not necessary optimal),
stable in the face of uncertainty,
automatically generated, that reduce cognitive overload, and which
work for large non-linear and noisy models. 
Such constraints are called ``solutions to hard modeling problems''.

Traditional methods may not yield such solutions.
For example,
one simple traditional method is {\em binary plotting}.
After sampling the model, all model inputs might be plotted against the output score
in two-dimensional binary plots.
The best constraints on the inputs are those
that select for the best output. 
However,
if noise in a models yields plots that are not smooth,
then it becomes a time-consuming and subjective task to examine binary 
plots to detect a region of input parameters that most improves the outputs.
Also, studying binary plotting will not find
conjunctions of multiple input constraints
that
contribute to better output.
Further, as the dimensionality 
of model input increases, the cognitive effort required to 
study the plots can become prohibitively expensive.

\begin{figure}[!b]
\centerline{\includegraphics[width=3.5in]{../tim/mat_den_SD.pdf}}
\caption{A visualization tool for scientific data. From~\cite{treinish98}.}
\label{fig:treinish}
\end{figure}
Many researchers have developed impressive visual environments for
decreasing the cognitive overload associated with exploring
a multi-dimensional space. For example, \fig{treinish} shows a tool
developed at IBM that augments a standard three-dimensional display
with visual cues relating to higher-dimensional data; e.g.,
supplementary dimensions are shown bottom right; blue circles around
the axle show circular motion information; and a color key, shown
bottom left, indicates how colors in  the display relate to density
information~\cite{treinish98}. 

Such visualizations help analysts
explore visual information, but they present their own challenges.
There are still
limits on how many dimensions can be displayed (e.g. we have yet
to see effective visualizations for more than a ten dimensionality space).
Also, note how the tool shown in \fig{treinish} contains
numerous controls that allow analysts to change various visualization
options.  As the visualization environment grows more sophisticated,
some users find they have traded a data browsing problem with the
new problem of exploring the full range of the effects of all the
controls. 

When manual exploring of options fail, automatic methods can be
applied.  Optimization packages can be applied to data or the
equations of a system to find ``sweet spots'' that maximize the
score resulting from model outputs.  
Related methods include {\em sensitivity analysis}~\cite{saltelli00} 
and {\em design of experiments} (DOE) methods~\cite{boning94}
A canonical sensitivity analysis method might be to compute
eigenvectors of a linear system in order to understand its long-term
temporal behavior~\cite{ishida89,puccia85}. 
As for design of experiments,  DOE exercises an                      
existing model and helps shed light on the response surface of the            
model. DOE does identify gradients and key parameters for a model.

While useful for some models, these automatic methods do not apply to all models.
For example,
optimization methods can fail for non-linear models.   Any model with an
``if'' statement introduces a ``cliff'' 
where the effects of inputs on outputs abruptly  changes.
For such models, there is no linear continuous solution that applies either side
of the ``cliff''.
Model uncertainty also complicates sensitivity analysis.
For example, the eigenvector technique described would
yield 
spurious results if the coefficients on the models are not known with certainty.
Lastly, a DOE analysis can be complicated by
the dimensionality, noise, and visualization problems
described above.

It should be noted that DOE, sensitivity analyis, and
all learning methods (even the treatment learning method discussed below)
are
limited by the input range of inputs and the outputs generated. That is
to say that in order to detect a ``cliff'', the input range of the learning
set must span the cliff. Some researchers have overcome this limitation of traditional
sensitivity and DOE approaches by expanding the input range for critical
parameters including Wakeland et. al~\cite{wakeland04}. At the same time, their
{\em Broad Range Sensitivity Analysis} approach relies on modeler judgment to
select the parameters for inclusion in the expanded analysis. This
approach although informed by data and model knowledge may not be
(guaranteed) optimal.
Unlike traditional sensitivity analysis and
DOE, it is usual practice in our method to expand the input range beyond that of
traditional sensitivity analysis and DOE. Moreover, the key benefit of 
the our
method discussed is that
it  extracts a more compact model that can be heuristically
used to traverse the response surface for the subset of parameters under
consideration.

More generally, traditional methods 
tacitly assume total knowledge and total control of the input
space. This is often impractical.
Consider, for example, Mintzberg~ \cite{mintz75} study of how real-world
decisions are made. He found:
\bi
\item  56 U.S. foremen who
     averaged 583 activities in an eight-hour shift (one every 48 seconds).
    \item  160 British managers who
     worked for half an hour or more without interruption only once every
     two days. \ei
These empirical observations
do
not fit a traditional optimization model of decision making
were
all options are systematically studied, organized,
co-ordinated
and controlled.
In {\em hard modeling problems}, human agents must make decisions
using:
\bi \item
limited time and computational ability; \item
 limited computational ability (or
limited time for computation); \item limited knowledge about
decision alternatives;\item uncertainty about possible outcomes of
decisions\item uncertainty about pay-offs; \item no more than a
partial ordering of preferences; \item limited information about
probabilities of outcomes. \ei 
Herbert Simon~\cite{simon82} 
defined and explored such hard modeling problems using a data structure
called {\em state space}~\cite{rosen93}.
In terms of model-based SE, state space is the set of options and option
selection operators within a model. 
Further, in hard modeling problems, large portions of the state space are uncertain.
Simon argued that in such state spaces,
searching for optimal solutions is a spurious goal.
Rather,
agents can only make just enough decisions that are just good enough.
In Simon's terminology, such decisions are {\em satisficing}.

Our contribution to hard modeling is to comment that (1)~{\em satisficing}
solutions can be achieved by
ignoring
certain irrelevant or redundant details within a model; (2)~surprisingly simple methods
can find what irrelevancies to ignore.  
Treatment learners propose ``treatments''; i.e.
constraints on a small subset of the model inputs. The other inputs
are left to vary at random. That is, apart from generating very succinct solutions,
treatment learning offers solutions that are 
stable
despite uncertainty in the  non-treated variables.

