Since this is the first use of extreme sampling we wanted to
investigate the effects of different parameter settings
on solution quality.
This study made use of the three DDP models discussed in \tion{ddpDes}.
Recall from \tion{itlMetaheur} that our
discretization method uses two parameters;
$M$, which controls the length of the iteration,
and $N$, which controls how the instances
are labeled $good$ and $bad$.
Also recall from \tion{itlMetaheur} that we 
formulated three different selectors.
We investigated different values of these control parameters to see
what effect they had on the performance of ITL.
Previous informal work had suggested $M$ could be in the hundreds,
so we used $M$ equal to 100, 300, and 500.
For the value of $N$ we used 25, 50, and 75, 
although the case where M = 100, 
N = 75 was omitted because for the \wob selector it was unclear
how to handle cases when $N > \frac{M}{2}$.
We used all three selectors in this study
to see if they effected the performance of ITL.
This gives us 24 $((3 * 3 - 1) * 3)$ different 
parameter combinations.
Each parameter combination was used to optimize
each model, giving us 72 parameter-model combinations.
Finally we ran ten trials for each of the 72 different
parameter-model settings, to give a total of 720 data sets.
Each trial in this study was run for 10 iterations and then stopped;
we did not investigate formulating an automatic stopping condition.
The total time needed to collect these data sets was about 5 weeks,
running on two single processor desktop Windows $^\copyright$ machines.


\subsection{Comparison Methodology}
When attempting to compare two techniques it can be difficult
to define what metric should be used for comparison.
In this section we use {\it delta comparisons}.
A delta is the simple difference between any two trials
that are different according to the effect 
being isolated, but have the same value for all other parameters.
The metric used for this difference is the 
normalized euclidean distance (from \tion{xsampling}).
Using this metric allows deltas from different models
to be compared, since our euclidean distance function normalizes
each coordinate.
Also, since ITL attempts to minimize this distance function,
it would not be useful to then study ITL's performance according to 
another metric.
When we present the deltas that highlight the effects
of $M$, for example, three lists of deltas are made,
one each for the three different settings of $M$ studied.
The deltas for $M=100$ are calculated by comparing each
trial where $M=100$ with every other trial where $M \neq 100$,
when the other three important parameters are the same
($N$, selector, model).
This isolates the effect of $M$ from the effect of the
other parameters.
All deltas for $M=100$ are added to the same list
so that we can see the effect of $M$ across all
the other parameter settings.
The lists of deltas are then sorted,
so that we can identify the quartiles.
Positive deltas indicate that the setting being isolated outperforms
the other possible settings, whereas a negative delta indicates
that the setting is outperformed by the other possible settings.
In this section we present only the median
results for space reasons.
The 1\st, 2\nd, and 3\rd quartile plots can be found in
appendix \ref{sect:settingsApp}.

%\begin{figure}
%\begin{algorithmic}
%\STATE normal objective function
%\end{algorithmic}
%\caption{Delta comparison algorithm}
%\end{figure}

We prefer this method to admittedly simpler statistical methods,
because this method is {\it non-parametric}, \ie
it makes no assumptions about the form of the underlying data.
For example, the commonly used t-tests are 
a parametric method that assume that the underling population 
distribution is Gaussian. 
Recent results suggest that there are 
many statistical issues left to explore regarding how to best to 
apply those t-tests for 
summarizing cross-validation studies \cite{brouck03}. 



\subsection{Experimental Effects of $M$}\label{sect:Msettings}
In this section we present the results of our trials
with the effects of $M$ isolated.
First, we will discuss the comparative performance
of the three $M$ values studied by plotting their
performance after certain numbers of iterations
had been completed by the search,
\ie after certain search depths had been
reached by ITL.
This comparison is shown in \fig{effectsMIter}.
Second, we will discuss the comparative performance
of the three $M$ values studied by plotting their
performance after certain numbers of points
had been generated by the dynamic model,
\ie after certain numbers of evaluations of the objective function.
This comparison is shown in \fig{effectsMGen}.


\fig{effectsMIter} shows the median deltas after 
the trials had completed 3, 5, 8, and 10 iterations.
It is clear that the trials with larger $M$ values
perform better than those with smaller $M$ values.
$M=500$ outperforms $M=300$, which outperforms $M=100$,
and the magnitude of this difference increases through all ten iterations.
Examining \fig{effectsMIterApp} demonstrates that the difference
between the 1\st and 3\rd quartiles is even larger for small numbers
of iterations completed, but the differences between the $M$ values
decreases after 5 to 8 iterations.
This suggests that searches with small $M$ values are not getting
stuck in local optima, but require more iterations to construct
high quality-partial descriptions.

\begin{figure}[th]
\centering
\includegraphics[width=3.95in]{Figures/DDP_figs/M_iter_mean_2nd_alone.pdf}
\caption{Effects of batch size, $M$, versus search depth}
\label{fig:effectsMIter}
\end{figure}

Of course it should not be surprising that a search with a much
larger batch size finds higher quality solutions.
But given a fixed number of objective function evaluations,
does ITL perform better by learning over many small
batches or a few large batches?
\fig{effectsMGen} shows the median deltas after
300, 600, 1000, 1200, 1600, 1900, 2400, 2900, and 3500
evaluations of the objective function.
These values correspond to iteration (learning) boundaries
for $M$ values of 300 and 500.
Notice that the $M=100$ and $M=300$ lines do not extend
to the right side of the graph.
Recall that each trial was run for 10 iterations,
so trials with $M=100$ only evaluated the objective function 1000 times.
Hence the $M=100$ line stops at 1000 objective function evaluations
and the $M=300$ line stops at 3000 objective function evaluations.
It is clear from this figure that for a fixed number of 
objective function evaluations, ITL performs much better by
learning over a larger number of smaller batches.
The $M=100$ trials significantly outperform the two other $M$
settings, and the $M=300$ trials outperform $M=500$, although to
a lesser degree.

\begin{figure}
\centering
\includegraphics[width=3.95in]{Figures/DDP_figs/M_num_mean_2nd_alone.pdf}
\caption{Effects of batch size, $M$, versus objective function evaluations}
\label{fig:effectsMGen}
\end{figure}

\subsection{Experimental Effects of $N$}
In this section we present the results of our trials
with the effects of $N$ isolated, shown in \fig{effectsN}.
The graph showing performance versus search depth
is the only graph shown because the value of $N$ does
not effect the number of times the objective function
is evaluated.
For this parameter the effect is not so pronounced.
While $N=25$ is clearly an underperformer, the
magnitude 
difference between $N=50$ and $N=75$ is not so large,
with $N=75$ being slightly higher performing.
This difference in performance shows that it is important
for there to be enough instances labeled $good$
for the treatment learner to find useful contrasts
between the $good$ and $bad$ instances.

\begin{figure}
\centering
\includegraphics[width=3.95in]{Figures/DDP_figs/N_iter_mean_2nd_alone.pdf}
\caption{Effects of good/bad ratio, $N$}
\label{fig:effectsN}
\end{figure}

\subsection{Experimental Effects of $M/N$ Combinations}
In this section we present the results of our trials
with respect to $M/N$ combinations.
As in \tion{Msettings}, we first show the deltas after certain
numbers of iterations (\fig{effectsMNIter}), and
after a certain number of objective function evaluations,
(\fig{effectsMNGen}).
Note that lines with the same $M$ value have the same line style
(light dashed, dark dashed, light solid),
while lines with the same $N$ value have the marker
(asterisk, X, or cross).

The most interesting effect in \fig{effectsMNIter}
is that while
500/75 and 500/50 (light dashed with an asterisk or X)
clearly outperform the other combinations,
300/75 and 300/50 (dark dashed with an asterisk or X) 
out perform 500/25 (light dashed with a cross).
In fact, 500/25, 300/25, and 100/50 all perform at about the same level,
with 100/25 significantly underperforming compared to all other $M/N$ values.
This shows that having a large batch size is important
to performance, but almost as important is to
have a large enough fraction of the instances labeled $good$.

\begin{figure}[t]
\centering
\includegraphics[width=5.0in]{Figures/DDP_figs/setting_iter_mean_2nd_alone.pdf}
\caption{Effects of $M/N$ combinations, versus search depth}
\label{fig:effectsMNIter}
\end{figure}

\fig{effectsMNGen} repeats the result from \fig{effectsMGen};
using smaller batch sizes for a fixed number of objective functions
evaluations leads to a higher quality solution.  \fig{effectsMNGen}
also shows that this effect is more important than the value of $N$,
since the lines with the same $M$ value (same color) cluster together.

\begin{figure}[t]
\centering
\includegraphics[width=5.0in]{Figures/DDP_figs/setting_num_mean_2nd_alone.pdf}
\caption{Effects of $M/N$ combinations, versus objective function evaluations}
\label{fig:effectsMNGen}
\end{figure}


\subsection{Experimental Effects of Selector}
\begin{figure}[h]
\centering
\includegraphics[width=3.95in]{Figures/DDP_figs/selector_iter_mean_2nd_alone.pdf}
\caption{Effects of selector}
\label{fig:effectsSelector}
\end{figure}


In this section we present the results of our trials
isolating the effects of the
selector used, shown in \fig{effectsSelector}.
Recall that \wob was an attempt to maximize the contrast
between the $good$ and $bad$ instances,
while both \wob and \borep pass only $2N$ instances
to the learner rather than $M$ instances (in our study
it is always the case that $M > 2N$).
\fig{effectsSelector} clearly shows that \wob is an
underperformer in our study.
The difference between \bore and \borep is smaller,
but \bore performs slightly better than \borepns.
\wobns's inferior performance can likely be attributed
to the same cause as the inferior performance of the
smaller values of $N$.
There must be a certain amount of contrast between the $good$
and $bad$ classes for ITL to build useful partial descriptions.
Small values of $N$ reduce the amount of useful contrast by
reducing the number of $good$ of instances.
Since the \wob selector lowers the performance of ITL,
we conjecture that there is useful information being hidden
by only passing on the worst instances to the learning stage
of ITL.
In other words, we conjecture that the $bad$ instances 
used by \wob are more similar to each than the $bad$ instances
used by \borepns.
It is this similarity that reduces the ability of the 
treatment learner to find highly valuable treatments.
Since the \borep selector also performs worse than the \bore
selector, we can conjecture that the smaller number of instances
utilized by the \wob selector is also partially responsible
for its degraded performance, but since the \wob
selector performs significantly worse than the \borep
selector, the primary reason is likely the exact nature
of the instances utilized.
The difference between the $N$ instances with lowest
distance score and the $N$ instances with the highest
distance score seems to be smaller than the difference
between the best $N$ instances and the $N$ instances 
spread out among the $M-N$ instances picked by \borepns.



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "casestudies"
%%% End: 
