Iterative Treatment Learning has been previously
introduced by Menzies \etal \cite{me01g,me02c}.
But this previous work has not placed ITL in the 
context of metaheuristic search.
This section will introduce the reader
to several important features of ITL as they
relate to ITL's use as a metaheuristic search
technique.


\subsection{Search Components}\label{sect:itlGlance}
ITL has the following three key steps
\begin{enumerate} \itemsep -14pt
\item objective function evaluation
\item discretization
\item treatment learning
\end{enumerate}
The three steps together make an {\it iteration}.
\fig{ITL} shows these steps, as well as the types of
inputs to each step.

\begin{figure}
\centerline{
\xymatrixcolsep{2.7pc}\xymatrix @L=6pt @R=10pt
{ 
& & 
\framebox{partial description} \ar `l[ldl] _{input\: vector\: selection\: informed\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:} 
                             ^{by\: partial\: description}
			     [lld]
\\
\framebox{input selection} \ar[r]^-{\: \: \: \vec{i}} &
\framebox[8.3ex]{obj func} \ar[r]^-{instance}_-{set} & 
\framebox[10.2ex]{discretizer} \ar[r]^-{instance}_-{set} & 
\ar `u[ul] 
     [ul] _{\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:new\: treatment}
\framebox[7.0ex]{learner} 
}
}
\caption{Diagrammatic view of ITL}
\label{fig:ITL}
\end{figure}

The objective function decodes candidate solutions
and scores each instance according to some criteria
the user has decided on.
As with the other search techniques described,
the only restriction on the form of the objective function is
that it outputs a single numeric value.
Since treatment learning only targets ordinal target classes,
ITL must discretize the output of the objective function
before calling the treatment learner.
The discretizer used by ITL will be discussed in \tion{xsampling}.
%The sampling policy used by ITL determines how the objective
%score is converted to the final value seen by the treatment learner.  
%This value is from the set $\{bad, good\}$.
The treatment learner is responsible for generating
the small theories that ITL accumulates as the last step
of each iteration.  It is the conjunction of these
theories that constitutes ITL's solution when it
finishes searching.


\subsection{Solution Form}\label{sect:solutionForm}
Recall from \tion{tar3Details} that the theories returned
by treatment learners comment on only a few of
the available attributes.  This means that after
several iterations the candidate solution found
by ITL does not comment on all the available attributes.
We call this a {\it partial description}.
Contrast this with the {\it complete descriptions} returned
by the search techniques discussed in \tion{metaheur}.
These complete descriptions comment on all the available
attributes.  
For example, when solving a scheduling problem they 
would return an exact schedule, like the one shown in \ble{complete}.
\begin{table}
\centering
\begin{tabular}{cc}
task number & schedule position \\
$task_1$ & 6  \\
$task_2$ & 7  \\
$task_3$ & 32 \\
$task_4$ & 2  \\
\multicolumn{2}{c}{$\ldots$}    \\
$task_n$ & 41 \\
\end{tabular}
\caption{Complete description for a hypothetical scheduling problem}
\label{table:complete}
\end{table}
%$task_3, task_2, task_{19}, \ldots, task_{31}$.
A partial description only assigns values or ranges to
some of the attributes.
In the scheduling example a partial description would
resemble the one shown in \ble{partial}.
\begin{table}
\centering
\begin{tabular}{cc}
task number & schedule position \\
$task_1$ & $6 \leq p_1 \leq 10$  \\
$task_2$ & unassigned  \\
$task_3$ & unassigned \\
$task_4$ & $p_4 > 36$ \\
\multicolumn{2}{c}{$\ldots$}    \\
$task_n$ & $40 \leq p_n \leq 41$ \\
\end{tabular}
\caption{Partial description for a hypothetical scheduling problem}
\label{table:partial}
\end{table}


We assert that these partial descriptions have value,
particularly for management decisions.
Because partial descriptions don't comment on all 
available attributes and don't necessarily assign a 
specific value to the attributes it does comment on,
the descriptions are intrinsically more flexible.
If new design constraints arise at a later date, they will be less
likely to contradict a partial description.
Put another way, if a single attribute of a complete
description cannot be assigned the way it was
assigned in the solution, there is no way to know
its effect on solution quality without re-evaluating
the new solution and possibly conducting a new search.
Since a change to the allowed attribute values may not 
invalidate the entire region describe by the partial description,
solutions in the set of solutions allowed by the partial description 
can still be used.
%contradict a partial description, the change
%may not require any re-evaluation.
The difficulty of conducting a new search should not be understated.
Expertise in metaheuristic search is not likely to ever become
a common skill among business managers.
If the expert who conducted the original search is not available
to the business user, a complete description that is no longer
possible becomes worthless.



A possible drawback of partial descriptions is
that, since they don't describe a single solution,
but rather a set of solutions,
the variance in that set could be so high that the
partial description is not usable.
Without going into the particulars of feature subset selection
\cite{hall03,witten99,me07b},
the success of techniques that throw away attributes
before training on the remaining attributes is indisputable.
Building theories without commenting on all the
available attributes is exactly what ITL does,
so we have good reason to conjecture that it
is possible that the variance of partial
descriptions will be low.
We investigate this conjecture in \tion{variance}.

This concern may seem at odds with Miller's work \cite{miller02},
which suggests that removing attributes
{\it reduces} the variance when using machine learners.
But Miller is concerned with the learned theories
from machine learners and whether the exact form of
theories learned from different slices of the same data set
will be similar to each other.
The variance in the theories is reduced because
by removing attributes available to the learner,
the learned theory is less over-fit to the 
particularities of the data set.
\tion{variance} investigates the variance
of the {\it performance} of partial descriptions,
not the variance of the different partial
descriptions themselves.





\subsection{ITL's Metaheuristic Search Characteristics}\label{sect:itlChars}
Since ITL is being presented as a metaheuristic search
technique, ITL should also be described in the same
terms as the metaheuristic techniques presented in
\tion{metaheur}.
Some of the deficiencies mentioned in this section will
be discussed further in \chap{futurework}.
These characteristics are
\begin{enumerate} \itemsep -14pt
\item global search strategy
\item neighborhood defined by partial description
\item solution is encoded as a conjunction of attribute-value pairs
\item no turning knob for exploration vs.\ exploitation
\item no explicit mechanism to escape from local optima
\end{enumerate}
Since ITL initially samples from the entire search space
and only modestly reduces the size of the portion of that
space each iteration, it should be considered a global
search strategy.
Although the neighborhood of the current solution
is never enumerated during ITL's search,
it can be thought of as all possible solutions that
agree with the current partial description.
This means that only points that agree with the current
partial description are explored in the next iteration.
As discussed earlier in this chapter,
the candidate solution for ITL is encoded as
a conjunction of attribute-value pairs.
The most undesirable characteristic of ITL at the current time
is the absence of some way to tune the
exploration vs.\ exploitation trade-off to a specific domain.
Nor is there any way for the technique to
dynamically adjust the trade-off during its search.
Instead, ITL becomes monotonically more exploitative
as treatments are added to the candidate solution and the
search space is reduced in size each iteration.

Once a treatment is added to the partial solution
there is no operation that might remove that treatment,
so there is no mechanism for ITL to escape from local optima.
This is not as big a problem for ITL as it for some other
techniques, such as hill climbing.
Recall that hill climbing is a local search, 
therefore if a local optimum has a large basin of attraction
any initial solution starting in that basin will
get stuck in that local optimum.
ITL is a global search and hence is less suspectible to 
the presence of local optimum.
Furthermore, since each iteration only reduces the size of
the search space by a small amount 
(recall from \tion{tar3Details} the small size of typical treatments),
it is unlikely that many near-optimal
solutions will be excluded from the search.
See \fig{itlSearch} for a simple 2-D example of how the
search space might be reduced during a typical search by ITL.
\begin{figure}
\centering
\includegraphics[width=3.0in]{Figures/itl_search}
\caption{Search space sampling}\label{fig:itlSearch}
\end{figure}

\subsection{Extreme Sampling}\label{sect:xsampling}

Treatment learners (\tion{tar3Details})
produces theories that predict for ordinal classes
(discrete classes that have an ordering),
but since most useful objective functions
produce real valued outputs,
ITL must have some type of discretization policy.
Note that while 
most discretization policies are applied to
the input attributes,
ITL needs a policy that discretizes the target
class.
%The choice of learning technique is often
%dictated by the form of the output class.
%Some learners, \eg M5' or linear regression,
%produced theories that predict for 
%continuous classes, while others,
%\eg \naive Bayes or J4.8, produced theories
%that predict for discrete classes.

%Since many models 
%for the output vector, $\vec{o}$, before invoking
%the learner.


The original ITL work on cost/benefit models
used a {\it striping} discretization policy.
Four zones were demarcated by parallel lines
drawn at $45^{\circ}$  from the cost-axis.
The zones were given exponentially increasing
values, going from high cost/low benefit solutions
to low cost/high benefit solutions.
Figure \ref{fig:diagonal} shows this policy graphically.
Note that the diagonal lines are lines of constant
benefit-to-cost ratios.

\begin{figure}[h]
\begin{center}
\includegraphics[height=2.0in]{Figures/borediag.pdf}
\end{center}
\caption{Diagonal striping}\label{fig:diagonal}
\end{figure}

In this thesis we introduce a new discretization policy
called {\it extreme sampling}.
The intuition behind this idea is that, 
if treatment learning is going to be used as a search heuristic, 
having multiple target classes is unnecessary.
There are only two classes, those
that are close to the current best solution, {\it good},
and those that are not, {\it bad}.
We developed a two-step process that takes a set 
of output vectors, $\{\vec{o}\}$, 
and labels some or all of them good or bad, shown in \fig{twoStep}.
The first step is to take the n-dimensional $\vec{o}$ and map
it to a single real number.
We choose the euclidean distance function, which
is simple and efficient and can work with
any number of dimensions.
The value for each coordinate is normalized
by the maximum value for that coordinate
to eliminate unit effects in the distance calculation.
The distance is calculated from the theoretical
best solution, which in our cost-benefit model
is the point $(0,1)$ in the cost-benefit plane
(remember our coordinates have been normalized at this point).
Now the distance values have to be mapped to our two classes,
good and bad.
\begin{figure}[th]
\centerline{
\xymatrixcolsep{3.5pc}\xymatrix
{\vec{o} ~\ar[r]^<<<<<<<<{objective} & [0-1] ~\ar[r]^{selector}& {good,bad}}
}
\caption{Extreme sampling}\label{fig:twoStep}
\end{figure}

We developed three extreme sampling variants, which we call 
{\it selectors}, to map the distance values to our two classes
shown in \fig{selectors}.
Each of our selectors  has two control parameters, 
{\it M} and {\it N}. $M$ is the batch size, 
\ie the number of instances generated during each iteration.
The first selector we developed, Best Or REst, \borens,
takes the $N$ instances with the smallest distance and labels
them good (shown in \fig{bore}).  
The rest of the instances are labeled bad.
After some initial experiments 
we developed two additional selectors.
\borep (\fig{borep}) puts $N$ instances in the good class and a random
sample of $N$ instances from the rest and puts them in the bad class.
It was thought this would allow $M$ to be scaled up without
increasing the runtime needed by the underlying learner
(since the learner would only see $2N$ instances, instead of $M$
instances).
\wob (\fig{wob}), Worst Or Best, 
labels the $N$ instances with the smallest distance measure as good
and the $N$ instances with the largest distance as bad.
This selector was motived by the idea that the worst and the
best instances might have the greatest contrast.
And similar to \borepns, \wob only passes $2N$ instances
to the underlying learner.

\begin{figure}[h]
\centering
\subfloat[\bore]{\label{fig:bore}{\includegraphics[height=1.69in]{Figures/borestrat.pdf}}}
\subfloat[\borep]{\label{fig:borep}{\includegraphics[height=1.69in]{Figures/boreprimestrat.pdf}}}
\subfloat[\wob]{\label{fig:wob}{\includegraphics[height=1.69in]{Figures/wobstrat.pdf}}}
\caption{Three selectors developed}\label{fig:selectors}
\end{figure}

%\begin{figure}[h]
%\centering
%\subfigure[\bore]{\includegraphics[height=1.69in]{Figures/borestrat.pdf}}\label{fig:a}
%\subfigure[\borep]{\includegraphics[height=1.69in]{Figures/boreprimestrat.pdf}}
%\subfigure[\wob]{\includegraphics[height=1.69in]{Figures/wobstrat.pdf}}
%\caption{Three selectors developed}\label{fig:bore}
%\end{figure}


\subsection{Search Strategy}\label{sect:searchStrategy}
In the original work on ITL it was imagined that a human
expert would want to validate each treatment.
In keeping with recasting ITL as a search heuristic,
no human expert was used in the current implementation
of ITL (see figure \ref{fig:ITL}).
Instead a simple greedy strategy was used to 
decide what treatment to use at the end of each
iteration.
The treatment learner suggests several treatments
each time it is run, but ranks them according to their
lift (with ties being broken by support).
The best treatment returned by the treatment learner each iteration
was used to constrain the next iteration.
This strategy is also a strictly forward search;
there is no back-tracking currently in ITL.
Once a treatment is added to the partial description
it cannot be removed by the search strategy.
%{\it beam search is a good buzz word}
%{\it so is general-to-specific search, which is what ITL does}


\subsubsection{Investigation into alternative search strategies}
Initially we were concerned that 
search strategies that explore more might perform better than
our simple greedy search.
Therefore, we conducted a short study into using two different
strategies, benchmarking them against our greedy
search.
The first alternative strategy completely ignored
the current candidate solution when generating
half the instances during each iteration.
For example, if the current batch size was 500,
250 instances would be generated according to the
current partial description, while another 250
would be drawn from the entire search space.
The second alternative strategy 
was designed to allow ITL to search through
multiple hyper-rectangles in the search space.
At the end of each iteration, when the treatment learner
returned several treatments, instead of just using the top
treatment, all treatments that had a lift
(see \tion{tar3Details} for a definition of lift)
within 20\% of the lift of the best treatment
were written to a list.
Each iteration created a new list of treatments,
and each list was remembered for the entire search.
Only points that passed at least one treatment
from each of the previous iterations were
searched during the current iteration.
\fig{altSearch2} shows these lists with two
example paths through the lists.
Each path through the lists was randomly
generated, biased according the individual 
treatment's lift.

\begin{figure}
\centerline{
\xymatrixcolsep{3.2pc}\xymatrix@L=6pt@R=6pt
{ 
iteration_1 & iteration_2 & iteration_3 & iteration_4 \\
treatment_{1a} \ar[rd] & treatment_{2a} \ar[r] & treatment_{3a} \ar[rd] & treatment_{4a}\\
treatment_{1b} & treatment_{2b} \ar[rd] & treatment_{3b} & treatment_{4b}\\
treatment_{1c} \ar[ruu] & treatment_{2c} & treatment_{3c} \ar[ruu] \\
treatment_{1d} & & treatment_{3d} \\
}
}
\caption[Maintaining multiple lists of treatments]
{Maintaining multiple lists of treatments.  Notice
that not all iterations find the same number of treatments
that pass the restriction for inclusion into the table.}
\label{fig:altSearch2}
\end{figure}

This study utilized the circuit model,
which has a cursory description below.
For a complete description of the model see \cite{me02c}.


\subparagraph{Circuit model}
A qualitative model, previously developed in \cite{me02c},
was used to see if either of the new strategies developed
could outperform the original greedy search.
The model is built from {\it switches, bulbs, openers} and
{\it closers}.
A basic element was built using three bulbs and three switches.
Elements were then connected using the openers and closers.
The openers and closers connected a bulb from 
one element to a switch from another and forced the switch
open or closed depending on whether the bulb was lit or dark.
\fig{cirtt} shows a three element circuit.
In this study we used two different sized models, one with three 
elements and one with six elements.
In addition each model could be optimized in one
dimension, maximizing the total number of shining bulbs,
or in two dimensions, maximizing the ratio of shining
bulbs to closed switches.

\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{Figures/cirt.pdf}
\end{center}
\caption[A qualitative network]
{A qualitative network: $Sw_i$, $B_i$ denote switches and bulbs.
The network repeats the structure three times with labels
$\{A,B,C\}$. Between each repetition are 
connectors that {\em open} or {\em close}  switches depending on
whether or not some bulb is lit or dark.
}
\label{fig:cirtt}
\end{figure}

When compared to the original greedy search neither
alternative strategy did well.
The greedy search converged faster in all four versions
of the circuit model, and found a higher quality
solution in three of them.


\subparagraph{Possible explanation for the performance of the greedy search}
Why does our greedy search seem to work so well?
\fig{greedy} is a depiction of our greedy search 
through the treatments returned by our learner.
But this is not the only searching being done by ITL.
Recall from \tion{tar3Details} that our treatment learner
searches through dozens or hundreds of potential treatments
according to its own ordering heuristic, {\it lift\sub{1}}.
\fig{full} is a depiction of
ITL's search including the heuristic search
done by the treatment learner in between each iteration.
Because the {\it lift\sub{1}} heuristic works so well
and the treatment learner does its own searching
according to this heuristic,
the search through the treatments can perform well
without any additional exploring.

%This makes the full search of ITL a hybrid beam search
%and iterative deepening search,
%where the beam width is defined by the maximum number
%of the treatments generated by the treatment
%and the ordering heuristic is the {\it lift\sub{1}}s
%and depth

\begin{figure}[!h]
\centering
\subfloat[greedy search between iterations]{
\label{fig:greedy}{\includegraphics[height=1.850in]{Figures/greedy.pdf}}}
\subfloat[search done by ITL including learner search]{
\label{fig:full}{\includegraphics[height=1.850in]{Figures/triangleSearch.pdf}}}
\caption{Different views of ITL's search}\label{fig:searching}
\end{figure}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../thesis"
%%% End: 
