# 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
Note that the previous lemma represents a sequential patterns version of Lemma 3 of Reference [5] for itemsets, where the upper bound to the number of closed itemsets in \(\mathcal{D}\) with \(W\) as support set is one (this holds by the nature of the itemsets where the notion of \"ordering\" is not defined). Lemma 1 is crucial for proving the following lemma which provides a bound on the size of the set \(V_{\mathcal{D}}\) of binary vectors. Lemma 2 (Proof in Appendix A): \(V_{\mathcal{D}}=\{v_{\mathcal{D}}(p):\ p\in CS(\mathcal{D})\}\cup\{(0,\ldots,0)\}\) _and \(|V_{\mathcal{D}}|\leq|CS(\mathcal{D})|+1\), that is, each vector of \(V_{\mathcal{D}}\) different from \((0,\ldots,0)\) is associated with at least one closed sequential pattern in \(\mathcal{D}\)._  
Combining a partitioning of \(CS(\mathcal{D})\) with the previous lemma we can define a function \(\bar{w}\), an upper bound to the function \(w\) of Theorem 7, which is efficient to compute with a single scan of \(\mathcal{D}\). Let \(\mathcal{I}\) be the set of items that appear in the dataset \(\mathcal{D}\) and \(<_{o}\) be its increasing ordering by their support in \(\mathcal{D}\) (ties broken arbitrarily). Given an item \(a\), let \(T_{\mathcal{D}}(\langle\{a\}\rangle)\) be its support set on \(\mathcal{D}\). Let \(<_{a}\) denote the increasing ordering of the transactions \(T_{\mathcal{D}}(\langle\{a\}\rangle)\) by the number of items contained that come after \(a\) w.r.t. the ordering \(<_{o}\) (ties broken arbitrarily). Let \(CS(\mathcal{D})=C_{1}\cup C_{2+}\), where \(C_{1}=\{p\in CS(\mathcal{D}):||p||=1\}\) and \(C_{2+}=\{p\in CS(\mathcal{D}):||p||\geq 2\}\). Let us focus on partitioning \(C_{2+}\). Let \(p\in C_{2+}\) and let \(a\) be the item in \(p\) which comes before any other item in \(p\) w.r.t. the order \(<_{o}\). Let \(\tau\) be the transaction containing \(p\) which comes before any other transaction containing \(p\) w.r.t. the order \(<_{a}\). We assign \(p\) to the set \(C_{a,\tau}\). Remember that an item can appear multiple times in a sequence. Given a transaction \(\tau\in T_{\mathcal{D}}(\langle\{a\}\rangle)\), \(k_{a,\tau}\) is the number of items in \(\tau\) (counted with their multiplicity) equal to \(a\) or that come after \(a\) in \(<_{o}\). Let \(m_{a,\tau}\) be the multiplicity of \(a\) in \(\tau\). For each \(k,m\geq 1\), \(m\leq k\), let \(g_{a,k,m}\) be the number of transactions in \(T_{\mathcal{D}}(\langle\{a\}\rangle)\) that contain exactly \(k\) items (counted with their multiplicity) equal to \(a\) or located after \(a\) in the ordering \(<_{o}\), with exactly \(m\) repetitions of \(a\). Let \(\chi_{a}=max\{k:g_{a,k,m}>0\}\). The following lemma gives us an upper bound to the size of \(C_{a,\tau}\). Lemma 3 (Proof in Appendix A): _We have_  
\[|C_{a,\tau}|\leq 2^{k_{a,\tau}-m_{a,\tau}}(2^{m_{a,\tau}}-1). \tag{28}\]  
Figure 1: Graphical representation of the case \(CS_{W}(\mathcal{D})=2\). Sequences \(x_{1}\) and \(x_{2}\) are closed sequences in \(\mathcal{D}\) with the same support set \(W\). Combining the following partitioning of \(CS(\mathcal{D})\) as  
\[CS(\mathcal{D})=C_{1}\cup C_{2+}=C_{1}\cup\left(\bigcup_{\sigma\in\mathcal{I}} \bigcup_{\tau\in\mathcal{D}(\{\sigma\})}C_{\sigma,\tau}\right) \tag{29}\]  
with the previous lemma, we obtain  
\[|CS(\mathcal{D})|\leq|\mathcal{I}|+\sum_{a\in\mathcal{I}}\sum_{\tau\in \mathcal{T}_{\mathcal{D}}(\{\sigma\})}2^{k_{\sigma,\tau}-m_{\sigma,\tau}}(2^{ m_{\sigma,\tau}}-1). \tag{30}\]  
Now we are ready to define the function \(\tilde{w}\), which can be used to obtain an efficiently computable upper bound to \(R_{\mathcal{D}}\). The following lemma represents the analogous of Lemma 5 of Reference [5], adjusted for sequential patterns. Let \(\overline{\eta}\) be the average item-length of the transactions of \(\mathcal{D}\), that is, \(\overline{\eta}=\sum_{\ell\in\mathcal{D}}||t||/n\). Let \(\hat{\eta}\) be the maximum item-length of the transactions of \(\mathcal{D}\), that is, \(\hat{\eta}=\max_{t\in\mathcal{D}}||t||\).