\section{Ranking Methods}
\textbf{There are two ranking methods that can be used by STAR2. These are {\em Bayesian ranking} and {\em Energy ranking}. The former is the main ranking method used by STAR2, while the latter is included in STAR2 for verifying that the Bayesian ranking is valid.}

\subsection{Support-Based Bayesian Ranking}\label{sec:bayrank}

STAR2 ranks the features ranges
seen in $K$ runs of a simulated annealer by dividing the $K$ runs into:
\begin{itemize}
\item {\em Best:} those associated with the  BEST\% solutions
(i.e. those with the BEST\% {\em least} energy);
\item And the {\em rest} (i.e. the other 100-BEST\% of solutions).
\end{itemize}
It then computes the probability that a range is found in $best$.
using Bayes' Theorem.
Informally,
the
theorem says $next=old*new$ i.e. what we'll believe {\em next}
comes
from how {\em new} evidence effects {\em old} beliefs.  More
formally:\begin{equation}\label{eq:n}\small
P(H|E)=P(E|H) P(H)\; /\; P(E)\end{equation}
i.e. using
evidence $E$ and a prior probability $P(H)$ for
hypothesis $H\in\{best, rest\}$.
The theorem calculate a  posteriori  probability
$P(H|E)$.
Simple  Bayes classifiers are often called ``naive'' since they assume
independence of each feature. While this assumption
 simplifies the implementation
(frequency
counts are required only for each feature),
 it is possible
that
correlated events are missed by this ``naive'' approach.
Domingos and Pazzini show theoretically
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that, on average, seemingly naive Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).


When applying the theorem, {\em likelihoods}
are computed from observed
frequencies, then normalize to create
probabilities (this normalization cancels out $P(E)$ in \ref{eq:n}, so it need not be computed).
For example, after $K=10,000$ runs divided into  1,000 lowest 10\% {\em best} solutions and 9,000
{\em rest}, the  range $rely=vh$ might appears 10 times in the $best$ solutions, but only
5 times in the $rest$. Hence:

{\scriptsize
\begin{eqnarray}\nonumber
E&=& (reply=vh)\\\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}}
Previously~\cite{clark05}
we have found that  \ref{eq:ten}
is a poor ranking heuristic
since it is 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 such unreliable low frequency evidence, we augment \ref{eq:ten}
with a support term.
Support should $increase$ as the frequency of a range $increases$,  i.e.
$like(x|best)$ is a valid support measure.
STAR2 hence ranks ranges via
\begin{equation}\label{eq:ps}\small
P(best|E) * support(best|E) = \frac{like(x|best)^2}{like(x|best) + like(x|rest)}
\end{equation}
