# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 7 Experimental Evaluation
### True Frequent Sequential Patterns Results  
In this section, we describe the results of our algorithms for mining the true frequent sequential patterns. In all these experiments, we fixed \(\delta=0.1\). First of all, for each real dataset we generated 4 pseudo-artificial datasets \(\mathcal{D}_{i}\), \(i\in[1,4]\) from the same ground truth. We mined the set \(FSP(\mathcal{D}_{i},\theta)\), and we compared it with the TFSPs, that is, the set \(FSP(\mathcal{D},\theta)\), where \(\mathcal{D}\) is the ground truth. Such experiments aim to verify whether the sets of the FSPs extracted from the pseudo-artificial datasets contain false positives and miss some TFSPs. Table 3 shows the fractions of times that the set \(FSP(\mathcal{D}_{i},\theta)\) contains false positives and misses TFSPs from the ground truth. We ran this evaluation over the four datasets \(\mathcal{D}_{i}\), \(i\in[1,4]\), of the same size from the same ground truth and we reported the average. For each dataset, we report the results with two frequency thresholds \(\theta\). In almost all the cases, the FSPs mined from the pseudo-artificial datasets contain false positives and miss some TFSPs. In particular, with lower frequency thresholds (and, therefore, a larger number of patterns), the fraction of times we find false positives and false negatives usually increases. These results emphasize that, in general, the mining of the FSPs is not enough to learn interesting features of the underlying generative process of the data, and techniques like the ones introduced in this work are necessary. Then, we compute and compare the upper bounds to the maximum deviation introduced in the previous sections, since our strategy to find an approximation to the true frequent sequential patterns hinges on finding a tight upper bound to the maximum deviation. For each pseudo-artificial dataset, we computed the upper bound \(\mu_{VC}/2\) to the maximum deviation using the VC-dimension based bound (ComputeMaxDevVC, Algorithm 3), the Rademacher complexity based bound \(\mu_{R}^{b}/2\) (ComputeMaxDevRadeBound, Equation (34)), and the Rademacher complexity approximation \(\mu_{R}^{a}/2\) (ComputeMaxDevRadeApprox, Equation (40)). Table 4 shows that the two methods for computing the upper bound to the maximum deviation using an upper to the empirical VC-dimension and Rademacher complexity are similar for BMS1 and BMS2, but for the other samples the VC-dimension-based algorithm is better than the one based on the Rademacher complexity bound by a factor between 2 and 3, that is, \(\mu_{R}^{b}/\mu_{VC}\in[2,3]\). Tighter upper bounds to the maximum deviation are provided by the method that uses the approximation of the Rademacher complexity. \begin{table}
\begin{tabular}{l r r r r} \hline \hline
**Ground Truth** & \(\theta\) & **[TFSP]** & **Times FPs** & **Times FNs** \\ \hline \multirow{2}{*}{BIBLE} & 0.1 & 174 & 50\% & 100\% \\  & 0.05 & 774 & 100\% & 100\% \\ \hline \multirow{2}{*}{BMS1} & 0.025 & 13 & 50\% & 0\% \\  & 0.0225 & 17 & 0\% & 25\% \\ \hline \multirow{2}{*}{BMS2} & 0.025 & 10 & 0\% & 0\% \\  & 0.0225 & 11 & 0\% & 0\% \\ \hline \multirow{2}{*}{KOSARAK} & 0.06 & 23 & 100\% & 0\% \\  & 0.04 & 41 & 50\% & 25\% \\ \hline \multirow{2}{*}{LEVIATHAN} & 0.15 & 225 & 75\% & 100\% \\  & 0.1 & 651 & 100\% & 100\% \\ \hline \multirow{2}{*}{MSNBC} & 0.02 & 97 & 75\% & 25\% \\  & 0.015 & 143 & 100\% & 50\% \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average fraction of times that \(FSP(\mathcal{D}_{i},\theta)\), with \(\mathcal{D}_{i}\) a pseudo-artificial dataset, contains false positives, Times FPs, and misses true frequent sequential patterns (TFSPs) (false negatives), Times FNs, over 4 datasets \(\mathcal{D}_{i}\) from the same ground truth.