# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 7 Experimental Evaluation
### True Frequent Sequential Patterns Results
In our implementation of Algorithm 4 to compute an upper bound to the empirical Rademacher complexity of sequential patterns, we compute several upper bounds associated with different integer values of \(\eta\in[\overline{\eta}+\beta_{1},\min(\beta_{2},\hat{\eta})]\) for fixed values of \(\beta_{1}\) and \(\beta_{2}\), taking the minimum bound among those computed. In our experiments, we fixed \(\beta_{1}=20\) and \(\beta_{2}=120\). In practice, by increasing the value of \(\eta\) we observe a decreasing trend of the upper bound value until a minimum value is reached. Then, by increasing again the value of \(\eta\) the value of the upper bound increases until it converges to the one achieved with \(\eta=\hat{\eta}\). In addition, for each pseudo-artificial dataset the value of \(\eta\) associated with the minimum value of the upper bound to the maximum deviation is always found in \([\overline{\eta}+\beta_{1},\min(\beta_{2},\hat{\eta})]\), with \(\beta_{1}=20\), \(\beta_{2}=120\). Finally, we evaluated the performance of our two strategies to mine an approximation of the true frequent sequential patterns, the first one with guarantees on the false positives and the second one with guarantees on the false negatives, using the upper bounds on the maximum deviation computed above. We considered the two tightest upper bounds, that are \(\mu_{VC}/2\) and \(\mu_{R}^{a}/2\), computed respectively using the empirical VC-dimension and an approximation of the empirical Rademacher complexity. From each pseudo-artificial dataset, we mined the FSPs using \(\hat{\theta}\), for the first strategy, and \(\hat{\theta}\), for the second one, respectively computed using Theorems 10 and 11, and we compared the sequential patterns extracted with the TFSPs from the ground truth. Table 5 shows the results for the strategy with guarantees on the false positives. Using \(\mu_{VC}/2\) to compute the corrected frequency threshold \(\hat{\theta}_{VC}\), our algorithm performs better than the theoretical guarantees in all the runs, since the number of times the output contains false positives is always equal to zero, while the theory guarantees a probability of at least \(1-\delta=0.9\) to obtain the correct approximation. Obviously, this also happens using \(\mu_{R}^{a}/2\) to compute the corrected frequency threshold \(\hat{\theta}_{R}\), since \(\mu_{VC}>\mu_{R}^{a}\). We also computed the average fraction of TFSPs reported in the output by the algorithm, that is, \(|FSP(\mathcal{D}_{i},\hat{\theta})|/|TFSP|\), since we aim to obtain as many TFSPs as possible. For all the datasets, it is possible to notice that the results obtained with the Rademacher complexity are better than the ones obtained with the VC-dimension, since the Rademacher allows to obtain a higher percentage of TFSPs in output. Table 6 shows the results for the strategy with guarantees on the false negatives. Similar to the previous case, our algorithm performs better than the theoretical guarantees in all the runs, since the number of times the algorithm misses some TFSPs is always equal to zero, with both the VC-dimension and the Rademacher complexity based results. We also report the average fractions of patterns in the output that are TFSPs, that is, \(|TFSP|/|FSP(\mathcal{D}_{i},\tilde{\theta})|\), since we are interested in obtaining all the TFSPs but with less false positives as possible. Again, the results with the Rademacher complexity are better than the ones obtained with the VC-dimension, since the number of sequential patterns in the output of the algorithm that are TFSPs is higher using the Rademacher complexity.