# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 2 Preliminaries
### VC-Dimension  
The Vapnik-Chervonenkis (VC) dimension [2; 23] of a space of points is a measure of the complexity or expressiveness of a family of indicator functions, or, equivalently, of a family of subsets, defined on that space. A finite bound on the VC-dimension of a structure implies a bound of the number of random samples required to approximately learn that structure.  
We define a _range space_ as a pair \((X,\mathcal{R})\), where \(X\) is a finite or infinite set and \(\mathcal{R}\), the _range set_, is a finite or infinite family of subsets of \(X\). The members of \(X\) are called _points_, while the members of \(\mathcal{R}\) are called _ranges_. Given \(A\subseteq X\), we define the _projection_ of \(\mathcal{R}\) in \(A\) as \(P_{\mathcal{R}}(A)=\{r\cap A\ :\ r\in\mathcal{R}\}\).  
We define \(2^{A}\) as the _power set_ of \(A\), that is the set of all the possible subsets of \(A\), including the empty set \(\mathcal{O}\) and \(A\) itself. If \(P_{\mathcal{R}}(A)=2^{A}\), then \(A\) is said to be _shattered by_\(\mathcal{R}\). The VC-dimension of a range space is the cardinality of the largest set shattered by the space.  
Definition 5: Let \(RS=(X,\mathcal{R})\) be a range space and \(B\subseteq X\). The empirical VC-dimension \(EVC(RS,B)\) of RS on \(B\) is the maximum cardinality of a subset of \(B\) shattered by \(\mathcal{R}\). The VC-dimension \(VC(RS)\) of RS is defined as \(VC(RS)=EVC(RS,X)\).  
Example 2: Let \(X=[0,1]\) be the set of all the points in \([0,1]\) and let \(\mathcal{R}\) be the set of subsets \([a,b]\), with \(0\leq a\leq b\leq 1\), that is \([a,b]\subseteq[0,1]\). Let us consider the set \(Y=\{x,y,z\}\), containing \(3\) points \(0\leq x<y<z\leq 1\). It is not possible to find a range whose intersection with the set \(Y\) is \(\{x,z\}\), since all the ranges \([a,b]\), with \(0\leq a\leq b\leq 1\), containing \(x\) and \(z\), also contain \(y\). Then, \(VC(X,\mathcal{R})\) must be less than \(3\). Consider now the set \(Y=\{x,y\}\), containing only \(2\) points \(0\leq x<y\leq 1\). It is easy to see that \(Y\) is shattered by \(\mathcal{R}\), so \(VC(X,\mathcal{R})=2\).  
The main application of VC-dimension in statistics and learning theory is to derive the sample size needed to approximately \"learn\" the ranges, as defined below.  
Definition 6: Let \(RS=(X,\mathcal{R})\) be a range space. Given \(\varepsilon\in(0,1)\), a bag \(B\) of elements taken from \(X\) is an \(\varepsilon\)-bag of \(X\) if for all \(r\in\mathcal{R}\), we have  
\[\left|\frac{|X\cap r|}{|X|}-\frac{|B\cap r|}{|B|}\right|\leq\varepsilon. \tag{10}\]  
Theorem 2.1: _There is a constant \(c>0\) such that if \((X,\mathcal{R})\) is a range space of VC-dimension \(\leq d\), and \(\varepsilon,\delta\in(0,1)\), then a bag \(B\) of \(m\) elements taken with independent random extractions with replacement from \(X\), where_  
\[m\geq\frac{c}{\varepsilon^{2}}\left(d+\ln\frac{1}{\delta}\right), \tag{11}\]  
_is an \(\varepsilon\)-bag of \(X\) with probability \(\geq 1-\delta\)._  
The universal constant \(c\) has been experimentally estimated to be at most \(0.5\)[24]. In the remaining of this work, we will use \(c=0.5\). Note that Theorem 2.1 holds also when \(d\) is an upper bound to the empirical VC-dimension \(EVC(RS,B)\) of \(RS\) on \(B\)[25]. In that case, the bag \(B\) itself is an \(\varepsilon\)-bag of \(X\).