The basis for the Which machine learner is that it was meant to be an improvement over TAR3.  Both TAR3 and Which are treatment learners.
As was discussed in \sect{tar3}, treatment learners can be used to classify instances in a two class system, which is what several of the
experiments in \chap{experiments} exploit.  TAR3 and Which both create a list of potential treatments that when applied to the data set
will increase the frequency of the higher$-$valued classes in the subset.  There are two very key differences in the processes that they
both take.

The first key difference is in how Which and TAR3 build their rules.  TAR3, as discussed in \sect{tar3}, builds its rules by randomly
selecting $N$ pairs of attributes and their values and then testing the rule.  Which attempts to build rules slowly by attaching
existing rules to new attributes, this process is discussed in more detail in \sect{rulecombo} and \sect{selection}.  This difference
means that Which spends far less time creating and destroying futile rules, because it has more intelligence in its selection
policies.

The second key difference is in the reporting of TAR3 and Which.  TAR3 was constructed to report as many promising rules as it can find,
given the trail constraints.  Which was constructed to find the best possible rule that it can.  While it has the option to report
the top $N$ rules that it found, it is very often the case that those rules are either subsets or supersets of the best rule.  Which
makes no attempts to create multiple rules, any other rules that are promising that are created are simply a side effect of the processes
Which uses to create its best rule.

\section{Idea Behind Which}
\label{idea}
Which is a stochastic best$-$first search.  The idea behind this is a method of searching that relies on previous knowledge that has 
already been discovered.  Essentially,  Which uses what it has previously discovered via expansion to attempt to take great leaps through
the search space to approach a solution quicker.  The following chapter will discuss the different properties of Which.  The beginning of this chapter
discusses the intial idea and creation of Which, \sect{bfs} dicusses the best first search algoritm that Which uses in its search for
treatments, \sect{implementation} discusses the different data structures and code structures used in the Which implementation with
\sect{rulecombo} and \sect{selection} discussing how Which builds its rules and \sect{scoring} discussing how Which scores its rules.

\subsection{Best$-$First Search Implementation}
\label{bfs}
The basic idea of Which is to use a stochastic best first search\cite{beamsearch}.  As described in \cite{beamsearch} a best first search is
a method of searching a tree by exploring the nodes that score well based on a heuristic function first.  This expansion continues down the 
tree until a desired solution is found.  This function may depend on the description of the node, the description of the goal, the description
of the path from the root to the current node, and any heuristic knowledge of the domain.  Which itself mainly uses the path as the description
of the node as well as the description of the goal to score its nodes.  However, as is explained in \sect{scoring}, this scoring heuristic is
completely arbitrary to the core Which functionality.

The idea behind using the best first search here is a little different than the definition above.  Which has no direct root, but instead one 
root for each attribute in isolation.  Which will immediately score each attribute's ranges independently of each other.  After this phase 
Which consists of $n$ attributes each with $m$ nodes expanded.  It is here that Which decides which attribute range to expand next. Its method 
of doing this is to choose two paths from two trees, combine them, and then score them to see if they score well.  If this is a very promising 
path, there is a good chance that Which will attempt to combine this new node with a different node.  This process of combining is further 
explained in \sect{rulecombo} below.  The two attribute-ranges that are picked can be from the same tree.  In this case the rule produced has a 
disjunction, instead of a conjunction.  That is, if two ranges of the same attribute are picked, Which will join them together as a disjunction.
The aforementioned “good chance” above relates to the method in which Which will pick the next to paths to combine.  This is explained below 
in \sect{selection}.  Which will continue to pick two paths, combine them, and score them until one of the possible stopping conditions listed 
in section \sect{stoppingcond} occurs.

This differs from the basic definition of the best$-$first in that a best$-$first search will only add singletons to the current best path.  That is,
once the current paths have been evaluated and the next path has been picked, a best$-$first search will only expand the best path with one more
node.  Which, on the other hand, will happily attach an entire other search path to another path to create a new, possibly significantly more
complex, search path.  More on this method is discussed in \sect{rulecombo}.  An example of this sub$-$tree combination can be seen in
\fig{subtreecombo}.  In this example, our differences to a normal best$-$first search are illustrated.  In \fig{subtreecombo}, the black
nodes represent two disjoint promising paths and the white nodes represent the other expansions that had to occur to find those paths.
A normal best$-$first search would only expand the node with the best score by one more attribute.  In our modified search, however, we graft
the entire other well$-$performing subtree to the other tree.  This allows us to quickly assess deeper paths in the tree.

\begin{figure}[!ht]
\begin{center}
	\includegraphics{figures/chapter3/gratftree.png}
\caption{Example of the Modified Best$-$First Search.}
\label{fig:subtreecombo}
\end{center}
\end{figure}

\section{Implementation}
\label{implementation}
The following sections will describe the actual implementation of Which, instead of just the idea behind it.  Which does not actually have a 
collection of best first trees in it.  It instead uses a simple list to handle its storage.
\subsection{Sorted Linked List}
\label{linkedlist}
Instead of keeping track of the paths that have been expanded by keeping all of the different trees in memory, Which instead uses a linked list 
that is sorted by the score of each path.  In its basic form, all paths that have ever been seen exist in this list and therefore have a chance 
of being combined to other paths to create new paths.  Every time Which creates a new path in the search space, it scores via an arbitrary 
heuristic method and then inserts it into the linked list at its position.  Since this list is sorted, a newly created path will be inserted 
not at the beginning or the end, but at a meaningful location.  This sorting is very important to the probabilistic selection that is described 
\sect{selection}.

This method emulates the tree in terms of the selection algorithm and the expansion explained above in \sect{bfs}.  In fact, it could easily 
be shown that this forest of best first trees could be created from this stack in linear time.  The reason a linked list was chosen over the use 
of the actual tree was its ease of implementation, memory efficiency, and it is faster to traverse a list than it is to traverse a forest.  This 
last point is paramount in the choice because Which will spend most of its time traversing this list and combining different paths from it.  This
process is the most common process in the entire algorithm.

There is actually a second criteria that is used in determining where a newly created traversal is placed in the stack.  The major component of 
the sorting is the score of the path, however the number of nodes in the path is also considered in the case of a tie.  If two paths have an 
equal score but one of them has less nodes than the other, the smaller path is considered better by Which and will be placed ahead of the longer 
path.  This is due to the nature of the selection described in /sect{selection}.  The reason Which values shorter paths more is because it is a goal 
of Which to have shorter, more compact rules than longer.
\subsection{Rule Combination}
\label{rulecombo}
A very important concept in the implementation of Which is its method of jumping about the search space.  This allows Which to attempt to find 
the solution faster by growing its rules faster.  This idea can be explained by considering a best first forest situation where several of the 
trees have been expanded to a height greater than one and each of these expansions is proving to be a promising path to continue on.  This is 
where the idea of jumping about the search space comes in.  Instead of simply picking one path and growing it by one more attribute and scoring 
all of the new nodes, Which may take two paths that have multiple attributes already expanded in them and combine them.  The logic here is that 
if two long paths are both promising, there is reason to believe that combining these two paths together, instead of slowly adding attribute 
ranges one at a time, could lead to a promising path in itself.

The implementation of the combination is essentially a union of sets.  It is very possible that two paths in two different trees in the forest
have shared attribute ranges, especially if these attribute ranges are very good at predicting the goal.  The idea of a union of two sets is 
that all items in the new set are unique.  Also, as mentioned in \sect{bfs}, if two ranges of the same attribute are in this new set, they 
are simply a disjunction.  In other words, it can be envisioned that two paths are being simultaneously traversed in the tree and both are 
equally promising in finding the goal.  If there is ever the case that all possible attribute values are being traversed at the same time, 
that attribute is removed from the current path entirely.  The logic behind this is that ignoring the attribute all together is the same as 
exploring all of the paths of that attribute.
 
A point of interest here is to note the method in which Which will traverse the paths that exist in the best first forest.  If we consider each 
rule in the linked list to be an isolated path in the currently explored best first forest, we can make the point that Which does not actually 
traverse the paths at all.  Instead, Which keeps in its list not paths, but random states of different traversals in the best first forest.  
What this means that instead of traversing paths in a best first manner, it simply jumps from different states in a best first search through 
the act of combining different promising states it has seen so far.  This allows Which to see much further into the future with one combination
than a best first search because it does not have to move through the states by adding one new attribute at a time.  Also, the linked list 
construct combined with the probabilistic selection described in \sect{selection} allows Which to easily select which new state to jump to next.
For ease of explanation, this conjecture will not be used in other description of Which, instead the standard relations of Which to a best first
search will be used.
\subsection{Probabilistic Selection}
\label{selection}
As stated at the beginning of \sect{idea}, Which is a stochastic best first search.  This means that it does not exhaustively explore the search
space, or to put it in terms of the best first search algorithm, not all paths are explored.  Like a best first search, however, Which will rank 
each of the currently explored paths by some arbitrary heuristic and attempt to further explore the most promising paths first.  The key 
difference here is that it is not required for Which to only traverse the most promising path by one more attribute value.  In fact it is not 
required for Which to keep traversing on the current most promising path.  This is where the probabilistic selection comes in.

Which will choose its next traversal by pseudo-randomly selection two already explored paths and combining them.  This pseudo-randomness is a 
core element to the Which algorithm.  Which keeps a sorted linked list to hold its rules because of the probabilistic selection.  This selection
works by the pseudo-code in \fig{randselect} below.

\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
for r in rules
	sum = sum + r.score
	scores[r] = scores[r-1] + r.score
end for
for r in rules
	r.score = r.score/sum
end for
x = random(0,1)
for r in rules
	if x < scores[r] return r
	else x = x – scores[r]
	end if
end for
\end{lstlisting}
\end{center}
\caption{Probabilistic Selection Pseudo Code}
\label{fig:randselect}
\dbsp
\end{figure}

\fig{randselect} above illustrates the randomness of the algorithm.  If the two most promising paths are equal in their score and some order of magnitude
better than the third most promising path, it is very likely that they will be picked and combined, however, it is not a guarantee.  This allows 
Which to sometimes jump off of the current search path and attempt to create a new one that could lead to a different optimal solution.  
\fig{probstack} further illustrates this point.  It consists of a lists of items and shows how they can be combined.
 
 \begin{figure}[!ht]
 \begin{center}
 \resizebox{120mm}{!}{\includegraphics{figures/chapter3/probstack.png}}
 \caption{Illustration of the Pseudo-Code in \fig{randselect}}
 \label{fig:probstack}
 \end{center}
 \end{figure}
 
In the \fig{probstack} there is a 91\% chance that one of the two most promising rules will be picked for combination.  This method of probabilistic
selection allows for a high chance of paths that are very promising to continue to be traversed while adding some chance that a less promising 
path can also be further traversed, or a promising path and a less promising path can be combined to determine where that branch would lead.  
\subsection{Scoring Functionality}
\label{scoring}
One of the very important features of Which is that greatly differentiates it from other machine learners is that its scoring method is arbitrary.
In all of the experiments described below in \chap{experiments}, Which is being used as a contrast set learner.  However, it is not necessary for 
Which to be used as such.  In all of the algorithms that Which uses to search the space, none of them ever make use of the scoring heuristic.  
In fact, Which only uses the value of the scoring heuristic to evaluate if the moves that it is making are promising or not.  The method of 
growing and evaluating the paths is determined by a combination of weighted random samples of the space of paths that have been explored so far. 
Which has no notion of what it is that makes a path promising, just that a path is promising and should be explored further.

This allows Which to be used in applications of search that vary widely.  The implementation of this arbitrary scoring is function pointer that 
is passed into Which before it goes through its initial phase of creating the height one forest.  Which can then use the method to score any new
paths that get created.
 
For instance, the ROC n' Rule paper\cite{rocnrule} discusses several methods of scoring heuristics and compares them to show how some sophisticated methods 
are really much simpler than they seem. For instance, F\"{u}rnkranz et al. make the claim that RIPPER's evaluation metric is actually just a complex 
version of precision.  The authors prove this mathematically but with Which it can easily be shown that they are equivalent empirically by 
running Which several times on the same data using the two scoring methods and comparing the rules that result from it.  The actual end result 
for their proof can be shown in \eq{rip-to-prec} below.

\begin{center}
\begin{equation}
h_{ripper} = 2 * h_{precision} + 1
\label{eq:rip-to-prec}
\end{equation}
\end{center}
 
\subsection{Stopping Conditions}
\label{stoppingcond}
This concept of Which being a stochastic best first search has been shown in the sections above to be an interesting approach to traversing the 
search space.  However, currently there has been no explanation of how Which stops searching.  If Which was an exhaustive search this method of 
jumping about the space would be unnecessary because Which would eventually have to see all paths before quitting, so enumerating all possible 
paths would work just as well.  To solve this problem, Which has two simple stopping criteria.

The first stopping criteria is a ceiling on the total number of times Which can combine things.  The larger this number, the more combinations 
that can occur.  It has been shown empirically that machine learners eventually stop learning new information after a certain point\cite{micro}.  
This upper limit on the number of combinations that Which can do is user defined so it allows this to be tuned to the current application Which is being 
used for.

The second stopping criteria is a check that happens every so many combinations.  While Which does have a maximum number of combinations it is 
allowed to make, there is a chance that this number may be higher than what is really necessary.  The second stopping criteria does a check to 
see if the current best path is a certain amount greater than the best path was so many combinations ago.  The improvement amount and the number 
of combinations to allow before another check occurs is completely user defined.  This stopping criteria is more of an efficiency check than a 
true reason to stop the search.

%\section{Run Time}
%\label{whichruntime}
%It has been shown in \cite{tar3} that the runtime of TAR3 scales linearly with the size of the data set.  The following section will show that
%the main Which algorithm will scale linearly with the data set and that the scoring heuristic that Which uses can drastically alter the run$-$time
%of Which.
%
%For the following descriptions, $n$ will be used as the size of the instance set. The Which algorithm can be trivially divided into three
%different phases: read, score, and select.  The following section will evaluate the individual run times of each of these parts.  The overall
%Which algorithm consists of the sum of the parts.  For all of these run times, let $n$ be the size of the instance set Which is running on, $A$
%the set of attributes, and $A_v$ be the set of attribute values for a given attribute.
%
%\subsection{Read}
%\label{runtimeread}
%Read is the subprocess of Which that is done to read in all of the data and meta$-$data from the file and set up the necessary structures.
%
%Read can be trivially shown to run in $O(n)$ time.  In order to read the data, Which must read each attribute and its values from the file as well
%as instance from the data set.  This means that $f_{read}$ = |A \times A_v| + n$, with number of attributes and values in the data set is a constant
%for the data set.  So $f_{read} = O(n)$.
%
%\subsection{Score}
%\label{runtimescore}
%Score is the subprocess of Which that scores all of the attribute$-$value pairs in isolation.
%
%Score can be trivially shown to run in $O(h(r))$ time, where h(r) is the scoring function to be used when evaluating the rules.  In this phase,
%Which will create a rule for each attribute value pair.  We have discusses that Which uses an infinite stack size by default, so we will use
%that in our calculations.  If we assume the worst case, than Which will need to place each rule at the bottom of the stack.  This process will take:
%
%\begin{center}
%\nonumber \[
%	_\sum {i=1}^{|A \times A_v|} i = \frac{|A \times A_v|(|A \times A_v| + 1)}{2}
%\]
%\end{center}
%
%This operation is constant in the number of steps because as was discussed in \sect{runtimeread}, $|A \times A_v|$ is a constant.  Overall, this phase
%takes $f_{score} = \frac{|A \times A_v|(|A \times A_v| + 1)}{2} * h(r)$ time which has an upper bound of $O(h(r))$.
%
%\subsection{Select}
%\label{runtimeselect}
%The select phase is the phase that combines the rules and places them back in the stack.  As was discussed in \sect{runtimescore}, the worst case
%of placing the items in the stack is \frac{(|A \times A_v|+C)(|A \times A_v| + C + 1)}{2}.  Each new rule requires $h(r)$ time score and up to $C$ of
%these rules are created.  While the stack is infinite in concept and design, the total size of the stack can never exceed the number of attribute
%value pair combinations plus the number of new rules created.  The overall run time of this step is 
%$f_{select} = \frac{(|A \times A_v|+C)(|A \times A_v| + C + 1)}{2} * h(r) * C$, which is $O(h(r)$.

%\subsection{Final}
%\label{runtimefinal}
%The over all run time of this algorithm is %f_{read} + f_{score} + f_{select}, which is bounded above by $O(n + h(r))$.  This says that the
%overall run$-$time of which is entirely dependant on the scoring heuristic that is used.  For instance, $h_{lift}$ and $h_{balance}$ each take
%one pass over the data to calculate the score of the rule, in this case the Which run$-$time would be $O(n)$.

\section{Finite List}
\label{finitelist}
Throughout all of the above descriptions of the list structure used in Which, we have assumed that the size of that list is infinite.  That is, 
every single search path that has been explored so far remains in that list and each of these paths has some likelihood to be selected for 
combination in the future.  It is possible through the parameters given to Which to change this list length so that if so many paths are found to 
be more promising than a different path, that obsolete path is removed from further consideration entirely.  Results of these experiments can be 
found later in this thesis in \sect{listsize}.
\section{Advantages}
\label{advantages}
There are several things that give Which an advantage in not only the traversing of the possible search space but also its flexibility in the 
goal.  As stated under \sect{idea}, a node in a best first tree can be scored based on the description of the node and the description of the 
goal.  In Which's case, the description of the goal could be very different from application to application.   This allows Which to be used in a 
variety of different ways and allows a user of the application to define a different goal function for their specific application.

Another advantage is the method of search that Which uses.  Since Which does not slowly grow a path one attribute value at a time, it has the 
potential to find an optimum path much faster than a standard best first search approach.  Also, the stochastic method in which Which combines 
its path allows it to potentially jump to a path that was not the most promising but when combined with a promising path could lead to a promising
path.
