# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 3 VC-Dimension of Sequential Patterns  
In this section, we apply the statistical learning theory concept of VC-dimension to sequential patterns. First, we define the range space associated with a sequential dataset. Then, we show a computable efficient upper bound on the VC-dimension and, finally, we present two applications of such upper bound. The first one is to compute the size of a sample that guarantees to obtain a good approximation for the problem of mining the frequent sequential patterns. The second one is to compute an upper bound on the maximum deviation to mine the true frequent sequential patterns. Remember that a range space is a pair \((X,\mathcal{R})\) where \(X\) contains points and \(\mathcal{R}\) contains ranges. For a sequential dataset, \(X\) is the dataset itself, while \(\mathcal{R}\) contains the sequential transactions that are the support set for some sequential patterns. **Definition 7**. : _Let \(\mathcal{D}\) be a sequential dataset consisting of sequential transactions and let \(\mathcal{I}\) be its ground set. Let \(\mathbb{U}\) be the set of all sequences built with itemsets containing item from \(\mathcal{I}\). We define \(RS=(X,\mathcal{R})\) to be a range space associated with \(\mathcal{D}\) such that:_  
* \(X=\mathcal{D}\) _is the set of sequential transactions in the dataset;_
* \(\mathcal{R}=\{T_{\mathcal{D}}(p):p\in\mathbb{U}\}\) _is a family of sets of sequential transactions such that for each sequential pattern_ \(p\)_, the set_ \(T_{\mathcal{D}}(p)=\{\tau\in\mathcal{D}:p\sqsubseteq\tau\}\) _is the support set of_ \(p\) _on_ \(\mathcal{D}\) _._  
The VC-dimension of this range space is the maximum size of a set of sequential transactions that can be shattered by the support sets of the sequential patterns. **Example 3**. : _Consider the following dataset \(\mathcal{D}=\{\tau_{1},\tau_{2},\tau_{3},\tau_{4}\}\) as an example:_  
\[\tau_{1} =\langle\{1\},\{2,3\},\{4,5,6\}\rangle\] \[\tau_{2} =\langle\{1\},\{3\},\{4\}\rangle\] \[\tau_{3} =\langle\{7\},\{3,4\}\rangle\] \[\tau_{4} =\langle\{4\},\{5\}\rangle\]  
_The dataset above has 4 transactions. We now show that the VC-dimension of the range space RS associated with \(\mathcal{D}\) is 2. Let us consider the set \(A=\{\tau_{2},\tau_{3}\}\). The power set \(2^{A}\) of \(A\) is \(2^{A}=\{\emptyset,\{\tau_{2}\},\{\tau_{3}\},\{\tau_{2},\tau_{3}\}\}\). \(A\) is shatter by \(\mathcal{R}\) since the projection \(P_{\mathcal{R}}(A)\) of \(\mathcal{R}\) in \(A\) is equal to \(2^{A}\) (remember that \(P_{\mathcal{R}}(A)=\{r\cap A\ :\ r\in\mathcal{R}\}\)):_  
\[\emptyset =A\cap T_{\mathcal{D}}(\langle\{6\}\rangle),\] \[\{\tau_{2}\} =A\cap T_{\mathcal{D}}(\langle\{1\}\rangle),\] \[\{\tau_{3}\} =A\cap T_{\mathcal{D}}(\langle\{3,4\}\rangle),\] \[A =\{\tau_{2},\tau_{3}\} =A\cap T_{\mathcal{D}}(\langle\{3\}\rangle).\]  
_Since \(|A|=2\) and \(A\) is shattered by \(\mathcal{R}\), then the range space associated with \(\mathcal{D}\) has VC-dimension \(\geq 2\). Analogously, the sets \(\{\tau_{1},\tau_{3}\}\),\(\{\tau_{1},\tau_{4}\}\),\(\{\tau_{2},\tau_{4}\}\) and \(\{\tau_{3},\tau_{4}\}\) are shattered by \(\mathcal{R}\). The set \(B=\{\tau_{1},\tau_{2}\}\) is instead not shattered by \(\mathcal{R}\): since \(\tau_{2}\sqsubseteq\tau_{1}\), there is not a sequential pattern \(p^{*}\) such that \(B\cap T_{\mathcal{D}}(p^{*})=\{\tau_{2}\}\). The sets \(C=\{\tau_{1},\tau_{3},\tau_{4}\}\) and \(E=\{\tau_{2},\tau_{3},\tau_{4}\}\) are not shattered by \(\mathcal{R}\) either: there is not a sequential pattern \(p^{\prime}\) such that \(\{\tau_{3},\tau_{4}\}=C\cap T_{\mathcal{D}}(p^{\prime})\) or \(\{\tau_{3},\tau_{4}\}=E\cap T_{\mathcal{D}}(p^{\prime})\). Thus, the VC-dimension of the range space associated with \(\mathcal{D}\) is exactly 2._  
The exact computation of the (empirical) VC-dimension of the range space associated with a dataset \(\mathcal{D}\) is computationally expensive. The \(s\)-index, introduced by [PERSON] et al. [8], provides an efficiently computable upper bound on the VC-dimension of sequential patterns.