# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 2 Preliminaries
### Maximum Deviation  
Let \(\mathcal{M}\) be a probability distribution over a domain set \(\mathcal{Z}\). Let \(\mathcal{F}\) be a set of functions that go from \(\mathcal{Z}\) to \([-1,1]\). Given a function \(f\in\mathcal{F}\), we define the expectation of \(f\) as:  
\[\mathbb{E}(f)=\mathbb{E}_{z\sim\mathcal{M}}[f(z)], \tag{13}\]  
and, given a sample \(Z\) of \(n\) observations \(z_{1},\ldots,z_{n}\) drawn from \(\mathcal{M}\), the empirical average of \(f\) on \(Z\) as:  
\[E(f,Z)=\frac{1}{n}\sum_{i=1}^{n}f(z_{i}). \tag{14}\]  
The _maximum deviation_ is defined as the largest difference between the expectation of a function \(f\) and its empirical average on sample \(Z\) as:  
\[\sup_{f\in\mathcal{F}}|\mathbb{E}(f)-E(f,Z)|. \tag{15}\]  
We now use the maximum deviation to capture quantities of interest for the two mining tasks we consider in this work.  
In the frequent pattern mining scenario, we aim to find good estimates for \(f_{\mathcal{D}}(p)\) for each pattern \(p\). The frequency \(f_{\mathcal{D}}(p)\) is the expectation of a Bernoulli random variable (r.v.) \(X_{\mathcal{D}}(p,t)\) which is \(1\) if the pattern \(p\) appears in a transaction \(t\) drawn uniformly at random from \(\mathcal{D}\):  
\[\mathbb{E}_{t\sim\mathcal{D}}[X_{\mathcal{D}}(p,t)]=\Pr_{t\sim\mathcal{D}}(X_ {\mathcal{D}}(p,t)=1)=Suppp_{\mathcal{D}}(p)/|\mathcal{D}|=f_{\mathcal{D}}(p). \tag{16}\]  
Let \(\mathcal{S}\) be a sample of transactions drawn uniformly and independently at random from \(\mathcal{D}\). We define the frequency \(f_{\mathcal{S}}(p)\) as the fraction of transactions of \(\mathcal{S}\) where \(p\) appears. In this scenario, we have that the frequency \(f_{\mathcal{D}}(p)\) of \(p\) on \(\mathcal{D}\) and the frequency \(f_{\mathcal{S}}(p)\) of \(p\) on the sample \(\mathcal{S}\) represent, respectively, the expectation \(\mathbb{E}(f_{p})\) and the empirical average \(E(f_{p},\mathcal{S})\) of a function \(f_{p}\) associated with a pattern \(p\). Thus, the maximum deviation is:  
\[\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{\mathcal{S}}(p)|. \tag{17}\]  
In the true frequent pattern mining scenario, we aim to find good estimates for \(t_{\pi}(p)\) for each pattern \(p\). Note that the true frequency \(t_{\pi}(p)\) is the expectation of a Bernoulli r.v. which is \(1\) if the pattern \(p\) appears in a transaction drawn from \(\pi\). Moreover, it is easy to prove that the observed frequency \(f_{\mathcal{D}}(p)\) of a pattern \(p\) in a dataset \(\mathcal{D}\) of transactions drawn from \(\pi\) is an unbiased estimator for \(t_{\pi}(p)\), that is: \(\mathbb{E}\left[f_{\mathcal{D}}(p)\right]=t_{\pi}(p)\).  
Therefore, the true frequency \(t_{\pi}(p)\) and the frequency \(f_{\mathcal{D}}(p)\) observed on the dataset \(\mathcal{D}\) represent, respectively, the expectation \(\mathbb{E}(f_{p})\) and the empirical average \(E(f_{p},\mathcal{D})\) of a function \(f_{p}\) associated with a pattern \(p\). Thus, the maximum deviation is:  
\[\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|. \tag{18}\]  
In the next sections, we provide probabilistic upper bounds to the maximum deviation using the VC-dimension and Rademacher complexity which can therefore be used for frequent pattern mining and true frequent pattern mining scenarios.