\section{KEYS}

The premise of KEYS is that within the space of possible decisions,
there exist a small number of $key$ decisions that determine all
others~\cite{me07d}. If a model contains keys, then a general search
through a large space of options is superfluous.  A better (faster,
simpler) approach would be to just explore the keys.  KEYS uses
support-based Bayesian sampling to quickly find these important
variables.

There are two main components to KEYS - a greedy search and the BORE
ranking heuristic.

\subsection{Greedy Search}

KEYS searches a space of $M$ mitigations over the course of $M$
``eras''.  Initially, the entire set of mitigations is set randomly.
During each era, one more mitigation is set to $M_i=X_j$, $X_j \in
\{true,false\}$.  Each era $e$ generates a set $<input,score>$ as
follows:
\be
\item[1a:]
$Selected[1{\ldots}(e-1)]$ are settings from previous eras.
\item[1b:]
  $Guessed$ are randomly selected values for unfixed mitigations.  
\item[1c:]
  $Input = selected \cup guessed$.
\item[1d:]
Call {\tt model} to compute $score=ddp(input)$;
\ee
After 100 repeats of steps 1a,1b,1c,and 1d:
\bi
\item[2:] The 100 $score$s are divided into 10\% $best$ and 90\% $rest$. 
\item[3:]
The mitigation values in the $input$ sets are then scored using BORE
(described below).
\item[4:]
The top ranked mitigation value is fixed and stored in
$selected[e]$.\ei KEYS then moves to the era $e+1$ and repeats steps
1,2,3,4.  KEYS stops when every mitigation has a setting.
For full details, see \fig{KEYS}. 
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure KEYS
2. while FIXED_MITIGATIONS != TOTAL_MITIGATIONS
3.   for I:=1 to 100
4.     SELECTED[1...(I-1)] = best decisions up to this step
5.     GUESSED = random settings to the remaining mitigations
6.     INPUT = SELECTED + GUESSED
7.     SCORES= SCORE(INPUT)
8.   end for   
9.   for J:=1 to NUM_MITIGATIONS_TO_SET 
10.    TOP_MITIGATION = BORE(SCORES)       
11.    SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 
12.  end for  
13. end while          
14. return SELECTED \end{verbatim} }
~\hrule~
\caption{Pseudocode for KEYS}
\label{fig:KEYS}
\end{figure}



\subsection{BORE = \underline{B}est \underline{Or} \underline{R}est}


BORE~\cite{clark05} is bayesian ranking measure we use for find those
most influential ``key'' variables.  BORE assumes that the output
scores are divided into two classes - one class for $best$ outcomes
and one for the $rest$.  In such two-class systems, BORE searches for
mitigation values that have a high probability of belonging to the
$best$ set.

BORE divides numeric scores seen over $K$ runs and stores the top 10\%
in $best$ and the remaining 90\% scores in the set $rest$.  It then
computes the probability that a value is found in $best$ using Bayes
theorem.  The theorem uses evidence $E$ and a prior probability $P(H)$
for hypothesis $H\in\{best, rest\}$, to calculate a posteriori
probability $P(H|E)=P(E|H) P(H)\; /\; P(E)$.  Such simple Bayes
classifiers are often called ``na\"ive'' since they assume
independence of each variable.  Domingos and Pazzani have shown that
the independence assumption is a problem in a vanishingly small
percent of cases~\cite{domingos97optimality}. This explains the
repeated empirical result that seemingly na\"ive Bayes classifiers
perform as well as other more sophisticated schemes (e.g. see Table~1
in~\cite{domingos97optimality}).

When applying the theorem, {\em likelihoods} are computed from
observed frequencies. These likelihoods are then normalized to create
probabilities (this normalization cancels out $P(E)$ in Bayes
theorem).  For example, after $K=10,000$ runs are divided into 1,000
{\em best} solutions and 9,000 {\em rest}, the value
\mbox{$mitigation31=false$} might appears 10 times in the $best$
solutions, but only 5 times in the $rest$. Hence:\newline
\begin{minipage}{1.0\linewidth}
{\scriptsize
\begin{eqnarray}\nonumber
E&=& (mitigation31=false)\\\nonumber
P(best)&=&1000/10000 = 0.1\\\nonumber
P(rest)&=&9000/10000 = 0.9\\\nonumber
freq(E|best)&=&10/1000 = 0.01\\\nonumber
freq(E|rest)&=&5/9000 = 0.00056\\\nonumber
like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber
like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66
\end{eqnarray}}
\end{minipage}\newline
Previously~\cite{clark05}, we have found that Bayes theorem is a poor
ranking heuristic since it is easily distracted by low frequency
evidence.  For example, note how the probability of $E$ belonging to
the best class is moderately high even though its support is very low;
i.e. $P(best|E)=0.66$ but $freq(E|best) = 0.01$.

To avoid the problem of unreliable low frequency evidence, we augment
\eq{ten} with a support term.  Support should $increase$ as the
frequency of a value $increases$, i.e.  $like(best|E)$ is a valid
support measure.  Hence, step 3 of our greedy search raks values via
\begin{equation}\label{eq:ps}
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}

\subsection{KEYS2}

For each era, KEYS samples the DDP models and fixes the top $N=1$
settings. $N=1$ is, perhaps, an overly conservative search policy.

At least for the DDP models, the improvement in costs and attainments
generally increase for each era of KEYS.  This lead to the speculation
that we could jump further and faster into the solution space by
fixing $N\ge 1$ settings per era.  Such a {\em jump} policy can be
implemented as a small change to KEYS: \bi
\item Standard KEYS assigns the value of one to\\
{\tt NUM\_MITIGATIONS\_TO\_SET}\\ (see the pseudo-code of \fig{KEYS});
\item Other variants of KEYS assigns larger values.
\ei

KEYS2 sets $i$ settings in each era $i$.  Note that, in era 1, KEYS2
behaves exactly the same as KEYS while in (say) era 3, KEYS2 will fix
the top 3 ranked ranges.  Since it sets more variables at each era,
KEYS2 terminates earlier than KEYS.

\subsection{Areas of Improvement}

KEYS2 achieves a significant improvement in speed by setting an
 increasing number of mitigations at a time which in turn reduces the
 number of model instances generated and scored.  For further speed
 up, we could simply set more mitigations at each era, but prior
 experimentation showed that doing so reduces the algorithm's ability
 to reach more optimal solutions. This may be caused by the
 incremental decrease of support.

Note that in (say) era 5, KEYS2 will fix the top 5 ranked ranges. The
 first key set in this era is selected using BORE on 100
 instances. Let us assume that this key is set to $true$, so
 $Key_{5-1}=true$. For each one of the 100 instances scored in era
 5, there is a 50\% probability that they have $Key_{5-1}=false$,
 rendering half of the instances unfit to rank the second key. Thus,
 $Key_{5-2}$ is selected from about 50 instances. Similarly,
 $Key_{5-3}$ is selected from around 25, and so on. On large models,
 this effect can have some performance consequences.

We therefore need to explore other areas of improvemnt that do not
 affect the cost and attainment performance of the algorithm. One
 effective way to achieve a more efficient algorithm is profiling its
 implementation to find bottlenecks. Running ``gprof'' on KEYS with
 our largest model shows that the algorithm spends 86\% of its runtime
 scoring instances of the model. All other functions run either very
 fast or are not executed as many times.This finding prompted us to
 try find ways to reduce the number of calls to the model without
 compromising support.

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1.  Procedure KEYS
2.  while FIXED_MITIGATIONS != TOTAL_MITIGATIONS
3.   for I:=1 to 100
A.    if INVALID then
4.     SELECTED[1...(I-1)] = best decisions up to this step
5.     GUESSED = random settings to the remaining mitigations
6.     INPUT = SELECTED + GUESSED
7.     SCORES= SCORE(INPUT)
B.    end if
8.   end for   
9.   for J:=1 to NUM_MITIGATIONS_TO_SET 
10.   TOP_MITIGATION = BORE(SCORES)       
11.   SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 
12.  end for
C.   INVALIDS = INPUT $\cup$ SELECTED
13. end while          
14.return SELECTED \end{verbatim} }
~\hrule~
\caption{Pseudocode for KEYS improvement. Additional steps A. B. and C.}
\label{fig:opt}
\end{figure}


A simple way to address both problems is to only call the model for
 the instances that become invalid after each era. This
 can be achieved calling a new function that searches for the roughly
 50\% of mitigations that become invalid for selection of the next
 mitigation, and a slight modification of the original code so that it
 only generates and scores replacement instances for the invalid ones.
  Such method effectively uses valid instances already scored and
 saves roughly 50\% of the calls to the model while always having a
 full set of valid instances to select the next mitigation.
 \fig{opt} displays the pseudo-code for the proposed changes.
