# A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
## 5 Analysis  
In this section, the experimental results and the machine learning models behind them are analysed with the intention of deriving insights into why certain algorithm-graph pairings are stronger than others and to determine which features of a graph are the most predictive. We begin by analysing the importance of features for a Random Forest model trained on 50% of Dataset B. We chose to train a separate model, instead of using one from our cross-validation, because those models are all trained on all but one samples. We chose that dataset because of its class distribution--the two solvers that are strong on average (**tdlib** and **tamaki**) have nearly equal results and the third solver (**jdrasil**) is still best for a significant number of problem instances, unlike in Dataset A. This guarantees that the hybrid algorithm's task is the hardest, as the trivial 'winner-takes-all' approach would be the least effective. We used the feature importance functionality that is built into the _scikit-learn_ package. The results are presented in Figure 2. The results indicate that almost all features are important for the classification and their importance varies within relatively tight bounds. In order to gain further insight, we decided to exclude certain features from the dataset, retraining the model on the reduced dataset and measuring its accuracy against the baseline of the original full model, which is **76.5%**. In order to obtain more statistically robust results, we made multiple runs of 10-fold cross-validation and kept their scores. Afterwards, the scores were compared to the baseline of using all features using the Wilcoxon Signed-Rank Test with an alpha of 0.05. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c} \hline \hline
**VE** & **v** & **e** & **v/e** & **e/v** & **Density** & **q1** & **Median** & **q3** & **Minimum** & **Mean** & **Maximum** & **Variation** & **Entropy** \\ \hline
0.58 & \(-\)0.01 & 0.33 & \(-\)0.17 & 0.36 & 0.30 & 0.36 & 0.36 & 0.36 & 0.32 & 0.36 & 0.00 & \(-\)0.02 & 0.12 \\
0.25 & 0.55 & 0.09 & 0.15 & 0.00 & \(-\)0.07 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.55 & 0.55 & 0.24 \\
0.08 & \(-\)0.14 & 0.21 & 0.63 & 0.05 & \(-\)0.44 & 0.07 & 0.06 & 0.04 & 0.02 & 0.05 & \(-\)0.18 & \(-\)0.17 & 0.52 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The individual components in the Principal Component Analysis. Each row refers to one of the three components. The leftmost column shows how much of the total variance of the data is explained by that component; all other columns show how the respective feature is factored into the component. Figure 2: Feature importance for the Random Forest model trained on Dataset B (Section 4.2). We refer the reader to Section 3.1 for the list of features used. Each bar indicates the fraction of impurity in the dataset that is removed by splits on the relevant feature in all trees of the model. At first, we attempted excluding single features. We did 10-fold cross-validation 50 times for every excluded feature. No result was statistically significantly different from the baseline. Next, we attempted excluding two features at a time. Again, we did 10-fold cross-validation 50 times for every excluded set of features. Two pairs of features obtained a statistically significant worse accuracy score--**variation** and **minimum degree**, as well as **variation** and **entropy**. Finally, we attempted excluding three features at a time. This time, we did 10-fold cross-validation only 5 times, as here the computational cost of doing otherwise was prohibitive. While there were 14 sets of features that led to significantly worse scores, the magnitude of the change was rather small--the worst performance was **74.5%** and was achieved by removing **minimum degree**, **maximum degree** and **variation**. Of note is also the fact that 13 of 14 sets contained at least two of these same features and one set contained only one of them.