# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 4 Rademacher Complexity of Sequential Patterns
### Approximating the Rademacher Complexity of Sequential Patterns  
The previous section presents an efficiently computable upper bound to the Rademacher of sequential patterns, which does not require any extraction of frequent sequences from a given dataset. Here we present a simple method that gives us an approximation of the Rademacher complexity of sequential patterns, which provides a tighter bound to the maximum deviation compared to the ones previously presented. In the definition of the Rademacher complexity, a given combination \(\overline{\sigma}\) of the Rademacher r.v. \(\sigma\) splits the dataset \(\mathcal{D}\) of \(n\) transactions in two sub-samples \(\mathcal{D}_{1}(\overline{\sigma})\) and \(\mathcal{D}_{-1}(\overline{\sigma})\): each transaction associated with \(1\) and \(-1\) goes respectively into \(\mathcal{D}_{1}(\overline{\sigma})\) and \(\mathcal{D}_{-1}(\overline{\sigma})\). For a given sequential pattern \(p\in\mathbb{U}\), let \(Supp_{\mathcal{D}_{1}(\overline{\sigma})}(p)\) and \(Supp_{\mathcal{D}_{-1}(\overline{\sigma})}(p)\) be respectively the number of transactions of \(\mathcal{D}_{1}(\overline{\sigma})\) and \(\mathcal{D}_{-1}(\overline{\sigma})\) in which \(p\) appears. Thus, the Rademacher complexity can be rewritten as follows:  
\[R_{\mathcal{D}}=\mathbb{E}_{\sigma}\left[\sup_{p\in\mathbb{U}}\frac{1}{n}\sum _{i=1}^{n}\sigma_{i}\phi_{p}(t_{i})\right]=\mathbb{E}_{\sigma}\left[\sup_{p \in\mathbb{U}}\frac{Supp_{\mathcal{D}_{1}(\sigma)}(p)-Supp_{\mathcal{D}_{-1 }(\sigma)}(p)}{n}\right]. \tag{35}\]  
In our approximation method we generate a single combination \(\overline{\sigma}\) of the Rademacher r.v. \(\sigma\), instead of generating every possible combination and then taking the expectation. Given \(\overline{\sigma}\), the approximation \(\bar{R}_{\mathcal{D}}(\overline{\sigma})\) of \(R_{\mathcal{D}}\) is  
\[\hat{R}_{\mathcal{D}}(\overline{\sigma})=\sup_{p\in\mathbb{U}}\frac{Supp_{ \mathcal{D}_{1}(\overline{\sigma})}(p)-Supp_{\mathcal{D}_{-1}(\overline{ \sigma})}(p)}{n}. \tag{36}\]The first step of the procedure is to mine frequent sequential patterns from \(\mathcal{D}_{1}(\overline{\sigma})\) and \(\mathcal{D}_{-1}(\overline{\sigma})\), given a frequency threshold \(\kappa\). Let \(FSP(\mathcal{D}_{1}(\overline{\sigma}),\kappa)\) and \(FSP(\mathcal{D}_{-1}(\overline{\sigma}),\kappa)\) be the sets of sequential patterns with support greater or equal than \(\kappa\) in \(\mathcal{D}_{1}(\overline{\sigma})\) and \(\mathcal{D}_{-1}(\overline{\sigma})\), respectively. Let us define the following quantities:  
\[\gamma(p)=Supp_{\mathcal{D}_{1}(\overline{\sigma})}(p)-Supp_{\mathcal{D}_{-1}( \overline{\sigma})}(p), \tag{37}\]  
\[\gamma_{1}=\sup\{\gamma(p):p\in FSP(\mathcal{D}_{1}(\overline{\sigma}),\kappa )\cap FSP(\mathcal{D}_{-1}(\overline{\sigma}),\kappa)\}, \tag{38}\]  
and  
\[\gamma_{2}=\sup\{\gamma(p):p\in FSP(\mathcal{D}_{1}(\overline{\sigma}),\kappa )\setminus FSP(\mathcal{D}_{-1}(\overline{\sigma}),\kappa)\}. \tag{39}\]  
If \(\max(\gamma_{1},\gamma_{2})/n\geq\kappa\) then \(\tilde{R}_{\mathcal{D}}(\overline{\sigma})=\max(\gamma_{1},\gamma_{2})/n\), since each pattern \(p\) that is not frequent in both sub-samples has \(\gamma(p)/n\) lower than \(\kappa\). Instead, if \(\max(\gamma_{1},\gamma_{2})/n<\kappa\) the entire procedure is repeated with \(\kappa=\max(\gamma_{1},\gamma_{2})/n\). Note that, since the Rademacher complexity is a non-negative quantity, it is not necessary to look at patterns in \(FSP(\mathcal{D}_{-1}(\overline{\sigma}),\kappa)\setminus FSP(\mathcal{D}_{1}( \overline{\sigma}),\kappa)\) since their \(\gamma(p)\)'s values are negative. The pseudo-code of the method for finding an approximation of \(R_{\mathcal{D}}\) is presented in Algorithm 5. The extraction of frequent sequences from the two sub-samples can be done using one of the many algorithms for mining frequent sequential patterns.