# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 4 Rademacher Complexity of Sequential Patterns
### An Efficiently Computable Upper Bound to the Rademacher Complexity of Sequential Patterns  
For any pattern \(p\in\mathbb{U}\), let us define the following \(|\mathcal{D}|\)-dimensional vector  
\[v_{\mathcal{D}}(p)=(\phi_{p}(t_{1}),\ldots,\phi_{p}(t_{|\mathcal{D}|})) \tag{24}\]  
and let \(V_{\mathcal{D}}=\{v_{\mathcal{D}}(p),p\in\mathbb{U}\}\), where \(t_{1},t_{2},\ldots,t_{|\mathcal{D}|}\) are the \(|\mathcal{D}|\) transactions of \(\mathcal{D}\). Note that all the infinite sequences of the universe \(\mathbb{U}\) which do not appear in \(\mathcal{D}\) are associated with the vector \((0,\ldots,0)\) of \(|\mathcal{D}|\) zeros. This implies the finiteness of the size of \(V_{\mathcal{D}}\): \(|V_{\mathcal{D}}|<\infty\). In addition, defining \(|\mathbb{U}(\mathcal{D})|\) as the number of sequential patterns that appear in \(\mathcal{D}\), we have that potentially \(|V_{\mathcal{D}}|\ll|\mathbb{U}(\mathcal{D})|\), since there may be two or more patterns associated with the same vector \(v_{\mathcal{D}}\in V_{\mathcal{D}}\) (i.e., these patterns appear exactly in the same transactions). The following two theorems derive from known results of statistical learning theory (Thm. 3.3 of Reference [3]). Both theorems have been used for mining frequent itemsets [5], and can be applied for sequential pattern mining. **Theorem 6**. : _(Massart's Lemma)_  
\[R_{\mathcal{D}}\leq\max_{p\in\mathbb{U}}||v_{\mathcal{D}}(p)||\,\frac{\sqrt{2 \ln|V_{\mathcal{D}}|}}{|\mathcal{D}|} \tag{25}\]  
_where \(||\cdot||\) indicates the Euclidean norm._  
The following theorem is a stronger version of the previous one. **Theorem 7**. : _Let \(w:\mathbb{R}^{+}\to\mathbb{R}^{+}\) be the function_  
\[w(s)=\frac{1}{s}\ln\sum_{v\in V_{\mathcal{D}}}\exp\left(\frac{s^{2}||v||^{2}} {2|\mathcal{D}|^{2}}\right), \tag{26}\]  
_then_  
\[R_{\mathcal{D}}\leq\min_{s\in\mathbb{R}^{+}}w(s). \tag{27}\]  
The upper bound on \(R_{\mathcal{D}}\) of Theorem 7 is not directly applicable to sequential pattern mining since it requires to mine every pattern that appear in \(\mathcal{D}\) in order to determine the entire set \(V_{\mathcal{D}}\). However, the set \(V_{\mathcal{D}}\) is related to the set of closed sequential patterns on \(\mathcal{D}\). The following two results give us an upper bound to the size of \(V_{\mathcal{D}}\) which depends on the number of closed sequential patterns of \(\mathcal{D}\). **Lemma 1** (Proof in Appendix A). : _Consider a subset \(W\) of the dataset \(\mathcal{D}\), \(W\subseteq\mathcal{D}\). Let \(CS_{W}(\mathcal{D})\) be the set of closed sequential patterns in \(\mathcal{D}\) whose support set in \(\mathcal{D}\) is \(W\), that is, \(CS_{W}(\mathcal{D})=\{p\in CS(\mathcal{D}):T_{\mathcal{D}}(p)=W\}\), with \(C=|CS_{W}(\mathcal{D})|\). Then the number \(C\) of closed sequential patterns in \(\mathcal{D}\) with \(W\) as support set satisfies: \(0\leq C\leq|CS(\mathcal{D})|\)._A simple example where \(C=2\) is depicted in Figure 1. Note first of all that each super-sequence of \(x_{1}\) but not of \(x_{2}\) has support lower than the support of \(x_{1}\), and each super-sequence of \(x_{2}\) but not of \(x_{1}\) has support lower than the support of \(x_{2}\). Let \(\mathbf{y}_{\tau}=\tau_{x_{1}x_{2}}\) be the subsequence of transaction \(\tau\) restricted to only the sequences \(x_{1}\) and \(x_{2}\), preserving the relative order of their itemsets. Then \(y_{\tau_{1}}=y_{\tau_{3}}\
eq y_{\tau_{2}}\) which implies \(|T_{W}(y_{\tau_{1}})|\), \(|T_{W}(y_{\tau_{2}})|\), and \(|T_{W}(y_{\tau_{3}})|\) be lower than \(|T_{W}(x_{1})|=|T_{W}(x_{2})|=|W|\). Therefore each super-sequence of both \(x_{1}\) and \(x_{2}\) has support lower than the support of \(x_{1}\) (i.e. equal to the one of \(x_{2}\)). Thus, \(x_{1}\) and \(x_{2}\) are closed sequences in \(\mathcal{D}\) with the same support set \(W\).