Online appendix for Estimating Combinatorial t-way Coverage based on Matrix Complexity Metrics

A. Full Results

This appendix collects all RMSEs from all conducted experiments. It includes the RMSE for each instance and a corresponding maximal residual, thus extending the results displayed in the main text in Figure 3. These results, i.e., the RMSE and the corresponding maximal residuals, are compiled in Table 1. The inclusion of the maximal residuals provides a metric that addresses the volatility of both our trained machine learning models and the baseline to which we compare, i.e., the probabilistic coverage estimate. The maximal residual answers the question: How wrong can my estimator be?.

However, considering the results displayed in Table 1, we observe that the maximal residual generally exhibits the same behavior as the RMSE, i.e., if the RMSE of our models is below the baseline, the maximal residual of our models is also below that of the baseline and vice versa.

The heatmaps shown in Figures 1 and 2 show the performance of different models for estimating the t-way coverage. Each heatmap characterizes a table where the rows represent the size of the alphabet, and the columns represent the number of columns of the analysed randomly generated test set. The heatmaps are organised such that each model has an associated column and each t-strength has one row.

The probabilistic estimator, Lasso and LightGBM are assessed at various strengths ( $t\in \left\{2,3,4\right\}$ ). The shades of red indicate the magnitude of errors (e.g., RMSE - Root Mean Squared Error) across the analysed scenarios (alphabet size $v\in \left\{2,3,4,5\right\}$ and number of columns $k\in \{20,50,100,200,1000\})$. Darker reds suggest higher errors, whereas lighter shades imply lower errors. This visual encoding offers a quick comparison of how model performance scales with increasing values for t, v and k.

Consistent with the results presented in Section 5, we see that machine learning models generally outperform the probabilistic baseline for binary test sets, except when the test sets are very large (high number of tests), where the performance of LightGBM and the probabilistic baseline converge. Notably, the Lasso model without the probabilistic baseline performs significantly worse, while the Lasso model with the probabilistic baseline performs increases to a performance level comparable to the other models.

B. Feature Importances

The following are the outcomes considering all features of our feature importance analysis for both LightGBM and the Lasso regressor, with their respective importance plotted as bars, see Fig. 3. We averaged these feature importance scores over all our experiments, meaning that we conducted an experiment for each combination of alphabet v, strength t, and number of columns k, as shown in Table 1. We then averaged over v, t, and k for both regressors but differentiated between datasets with the baseline included and datasets without the baseline.

C. Runtime analysis

In order to compare our best results, i.e., our best-performing LightGBM model, in terms of computational efficiency, we performed a run-time analysis of our ML approach compared to a state-of-the-art tool to compute the t-way coverage of a randomly generated test set — CAmetrics. Here, we averaged the time it takes to compute the coverage for 10 different test sets using the Cametrics tool and the developed ML approach. We further separated between the time it takes to calculate the SVD of the regarded test sets and the prediction time using a trained model. These runtimes are shown in Table 2. One thing that seems counterintuitive about these runtimes is that it takes longer to predict test sets with fewer tests using our trained models. However, we cannot come up with a definite explanation for this except that our approach requires more complex models for smaller matrices, and thus the prediction time increases with increasing matrix size. This might also be linked to the fact that smaller matrices provide fewer singular values. Thus, the metrics are less expressive, requiring more complex LightGBM model architectures in terms of tree-based, boosted structures within the model.