# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 6 Algorithms for True Frequent Sequential Pattern Mining  
In this section, we describe our approach to find rigorous approximations to the TFSPs. In particular, given a dataset \(\mathcal{D}\), that is a finite bag of \(|\mathcal{D}|\) i.i.d. samples from an unknown probability distribution \(\pi\) on \(\mathbb{U}\), a minimum frequency threshold \(\theta\) and a confidence parameter \(\delta\), we aim to find rigorous approximations of the TFSPs w.r.t. \(\theta\), defined in Definitions 3 and 4, with probability at least \(1-\delta\). The intuition behind our approach is the following. If we know an upper bound \(\mu/2\) on the maximum deviation, that is \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\), we can identify a frequency threshold \(\hat{\theta}\) (resp. \(\bar{\theta}\)) such that the set \(FSP(\mathcal{D},\hat{\theta})\) is a FPF \(\mu\)-approximation (resp. \(FSP(\mathcal{D},\bar{\theta})\) is a \(\mu\)-approximation) of \(TFSP(\pi,\theta)\). The upper bound on the maximum deviation can be computed, as illustrated in the previous sections, with the empirical VC-dimension and with the Rademacher complexity. We now describe how to identify the threshold \(\hat{\theta}\) that allows to obtain a FPF \(\mu\)-approximation. Suppose that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\). In such a scenario, we have that every sequential pattern \(p^{*}\
otin TFSP(\pi,\theta)\), and so that has \(t_{\pi}(p^{*})<\theta\), has a frequency \(f_{\mathcal{D}}(p^{*})<\theta+\mu/2=\hat{\theta}\). Hence, the only sequential patterns that can have frequency in \(\mathcal{D}\) greater or equal to \(\hat{\theta}=\theta+\mu/2\), are those with true frequency at least \(\theta\). The intuition is that if we find a \(\mu\) such that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\), we know that all the sequences \(p\in\mathbb{U}\), that are not true frequent w.r.t \(\theta\), can not be in \(FSP(\mathcal{D},\hat{\theta})\). The following theorem formalizes the strategy to obtain a FPF \(\mu\)-approximation. Algorithm 7 shows the pseudo-code to mine the true frequent sequential patterns. Figure 2: Block diagram representing the relations between our algorithms. Theorem 10 shows how to compute a corrected threshold \(\hat{\theta}\) such that the set \(FSP(D,\hat{\theta})\) is a FPF \(\mu\)-approximation of \(TFSP(\pi,\theta)\), that is, \(FSP(D,\hat{\theta})\) only contains sequential patterns that are in \(TFSP(\pi,\theta)\). It guarantees that with high probability the set \(FSP(\mathcal{D},\hat{\theta})\) does not contain _false positives_ but it has not guarantees on the number of _false negatives_, that is, sequential patterns that are in \(TFSP(\pi,\theta)\) but not in \(FSP(\mathcal{D},\hat{\theta})\). On the other hand, we might be interested in finding all the true frequent sequential patterns in \(TFSP(\pi,\theta)\). The following result shows how to identify a threshold \(\tilde{\theta}\) such that the set \(FSP(\mathcal{D},\tilde{\theta})\) contains all the true frequent sequential patterns in \(TFSP(\pi,\theta)\) with high probability, that is, \(FSP(\mathcal{D},\tilde{\theta})\) is a \(\mu\)-approximation of \(TFSP(\pi,\theta)\). Note that while Theorem 11 provides guarantees on false negatives, it does not provide guarantees on the number of false positives in \(FSP(\mathcal{D},\tilde{\theta})\). Algorithm 7 shows the pseudo-code of the two strategies to mine the true frequent sequential patterns. To compute an upper bound on the maximum deviation, it is possible to use Algorithm 3 based on the empirical VC-dimension or the two procedures _ComputeMaxDevRadeBound_ (Equation (34)) and _ComputeMaxDevRadeApprox_ (Equation (40)) based on the Rademacher complexity. The mining of \(\mathcal{D}\) can be performed with any efficient algorithm for the exact mining of frequent sequential patterns. Figure 2 shows the relations between the algorithms we presented for mining true frequent sequential patterns. **Theorem 10**.