# Guidelines for Experimental Algorithmics:
## 7 Evaluating Results with Statistical Analysis
### Bayesian Inference
#### 7.4.2 Bayes Factor  
Bayes factors are a way to compare the _relative fit_ of several models and hypotheses to a given set of observations. To compute this relative fit of two hypotheses \(H_{1}\), \(H_{2}\) to an observation \(A\), we apply the Bayes theorem (Equation (9)) to both and consider their ratios:  
\[\frac{P\left(H_{1}\middle|\mathrm{A}\right)}{P\left(H_{0}\middle|\mathrm{A} \right)}=\frac{P\left(\mathrm{A}\middle|H_{1}\right)}{P\left(\mathrm{A} \middle|H_{0}\right)}\ \frac{P\left(H_{1}\right)}{P\left(H_{0}\right)}\]  
Crucially, the ratio of prior probabilities, which is subjective, is a separate factor from the ratio of likelihoods, which is objective. This objective part, the ratio \(P\left(\mathrm{A}\middle|H_{1}\right)/P\left(\mathrm{A}\middle|H_{0}\right)\), is called the _Bayes factor_. It models how much the _posterior odds ratio_\(P\left(H_{1}\middle|\mathrm{A}\right)/P\left(H_{0}\middle|\mathrm{A}\right)\) differs from the _prior odds ratio_\(P\left(H_{1}\right)/P\left(H_{0}\right)\) due to making observation \(A\). The first obvious difference to NHST is that calculating a Bayes Factor consists of comparing the fit of _both_ hypotheses to the data, not only the null hypothesis. It thus requires that an alternate hypothesis is stated explicitly, including a probability distribution over observable outcomes. If the alternative hypothesis is meant to be vague, for example just that two distributions are different, an uninformative prior with a high variance should be used. However, specific hypotheses like \"the new algorithm is at least 20% faster\" can also be modeled explicitly. This explicit modeling allows inference in both directions; using NHST, on the other hand, one can only ever infer that a null hypothesis is unlikely or that the data is insufficient to infer this. Using Bayes factors, it is possible to infer that \(H_{1}\) is more probable than \(H_{0}\), or that the observations are insufficient to support this statement, or that \(H_{0}\) is more probable than \(H_{1}\). \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **HPD 2.5** & **Mean** & **HPD 97.5** \\ \hline \(\log\alpha_{A/B}\) & \(-7.05\) & \(-5.27\) & \(-3.48\) \\ \(\beta_{A/B}\) & \(0.72\) & \(1.04\) & \(1.36\) \\ \(\sigma_{A/B}\) & \(0.85\) & \(1.19\) & \(1.59\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Posterior distribution of parameter values. In the previous running time analysis, we hypothesized a better scaling behavior, which was not confirmed by the experimental measurements. However, a cursory complexity analysis of the KADABRA algorithm suggests that the diameter has an influence on the running time. Might also the relative scaling of KADABRA and RK depend on the diameter? To answer this question, we compare the fit of two models: The first model is the same as discussed earlier (Equation (8)), it models the expected running time of KADABRA on instance \(x\) as \(e^{\alpha}\cdot T_{\text{RK}}(x)^{\beta}\), where \(T_{\text{RK}}(x)\) is the running time of RK on the same instance. The second model has the additional free parameter \(\gamma\), controlling the interaction between the diameter and running times:  
\[\log(T(x))\sim\mathcal{N}(\log(\alpha)+\beta\log(T_{\text{RK}}(x))+\gamma\log (\text{diam}_{x}),\ \sigma_{\epsilon}). \tag{10}\]  
Comparing for example the errors of a least-squares fit of the two models would not give much insight, since including an additional free parameter in a model almost always results in a better fit. This does not have to mean that the new parameter captures something interesting. Instead, we calculate the Bayes factor, for which we integrate over the prior distribution in each model (if favoring frequentist methods, one could compare whether the correlation of running times and diameter is significantly higher than expected by chance). Since this integral over the prior distribution also includes values of the new parameter which are not a good fit, models with too many additional parameters are automatically penalized.