# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 6 Algorithms for True Frequent Sequential Pattern Mining
: _Given \(\delta\in(0,1)\), such that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\) with probability at least \(1-\delta\), and given \(\theta\in(0,1]\), the set \(FSP(\mathcal{D},\hat{\theta})\), with \(\hat{\theta}=\theta+\mu/2\), is a FPF \(\mu\)-approximation of the set \(TFSP(\pi,\theta)\) with probability at least \(1-\delta\)._  
Proof. : Suppose that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\). Thus, we have that for all the sequential patterns \(p\in\mathbb{U}\), it results \(f_{\mathcal{D}}(p)\in[t_{\pi}(p)-\mu/2,t_{\pi}(p)+\mu/2]\). This also holds for the sequential patterns in \(\mathcal{G}=FSP(\mathcal{D},\hat{\theta})\). Therefore, the set \(\mathcal{G}\) satisfies Property 3 of Definition 4. Let \(p^{*}\) be a sequential pattern such that \(t_{\pi}(p^{*})<\theta\), that is, it is not a true frequent sequential pattern w.r.t. \(\theta\). Then, \(f_{\mathcal{D}}(p^{*})<\theta+\mu/2=\hat{\theta}\), that is, \(p^{*}\
otin\mathcal{G}\), which allows us to conclude that \(\mathcal{G}\) also has Property 1 from Definition 4. Now, let \(p^{\prime}\) be a sequential pattern such that \(t_{\pi}(p^{\prime})\geq\theta+\mu\). Then, \(f_{\mathcal{D}}(p^{\prime})\geq\theta+\mu/2\), that is \(p^{\prime}\in\mathcal{G}\), which allows us to conclude that \(\mathcal{G}\) also has Property 2 from Definition 4. Since we know that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\) with probability at least \(1-\delta\), then the set \(\mathcal{G}\) is a FPF \(\mu\)-approximation of \(TFSP(\pi,\theta)\) with probability at least \(1-\delta\), which concludes the proof. **Theorem 11**. : _Given \(\delta\in(0,1)\), such that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\) with probability at least \(1-\delta\), and given \(\theta\in(0,1]\), the set \(FSP(\mathcal{D},\tilde{\theta})\), with \(\tilde{\theta}=\theta-\mu/2\), is a \(\mu\)-approximation of the set \(TFSP(\pi,\theta)\) with probability at least \(1-\delta\)._  
Proof. : Suppose that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\). Thus, we have that for all the sequential patterns \(p\in\mathbb{U}\), it results \(f_{\mathcal{D}}(p)\in[t_{\pi}(p)-\mu/2,t_{\pi}(p)+\mu/2]\). This also holds for the sequential patterns in \(\mathcal{E}=FSP(\mathcal{D},\tilde{\theta})\). Therefore, the set \(\mathcal{E}\) satisfies Property 3 of Definition 3. It also means that for all \(p\in TFSP(\pi,\theta)\), \(f_{\mathcal{D}}(p)\geq\theta-\mu/2=\tilde{\theta}\), that is, \(p\in\mathcal{E}\), which allows us to conclude that \(\mathcal{E}\) also has Property 1 from Definition 3. Now, let \(p^{*}\) be a sequential pattern such that \(t_{\pi}(p^{*})<\theta-\mu\). Then, \(f_{\mathcal{D}}(p^{*})<\theta-\mu/2\), that is \(p^{*}\
otin\mathcal{E}\), which allows us to conclude that \(\mathcal{E}\) also has Property 2 from Definition 3. Since we know that \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu/2\) with probability at least \(1-\delta\), then the set \(\mathcal{E}\) is a \(\mu\)-approximation of \(TFSP(\pi,\theta)\) with probability at least \(1-\delta\), which concludes the proof. ```
Data: Dataset \(\mathcal{D}\); \(\delta\in(0,1)\); \(\theta\in(0,1]\) Result: Set \(\mathcal{G}\) that is a FPF \(\mu\)-approximation (resp. \(\mu\)-approximation) to \(TPSP(\pi,\theta)\) with probability \(\geq 1-\delta\). 1\(\mu/2\leftarrow\) ComputeMaxDeviationBound\((\mathcal{D},\delta)\); \(\mathcal{G}\gets FSP(\mathcal{D},\theta+\mu/2)\); /* resp. \(\theta-\mu/2\) to obtain a \(\mu\)-approximation */ return\(\mathcal{P}\);
```  
**Algorithm 7**Mining the True Frequent Sequential Patterns.