# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 2 Preliminaries
### Sequential Pattern Mining  
Let \(\mathcal{I}=\{i_{1},i_{2},\ldots,i_{h}\}\) be a finite set of elements called _items_. \(\mathcal{I}\) is also called the _ground set_. An _itemset_\(P\) is a (non-empty) subset of \(\mathcal{I}\), that is, \(P\subseteq\mathcal{I}\). A _sequential pattern_\(p=\langle P_{1},P_{2},\ldots,P_{\ell}\rangle\) is a _finite ordered sequence_ of itemsets, with \(P_{i}\subseteq\mathcal{I},1\leq i\leq\ell\). A sequential pattern \(p\) is also called a _sequence_. The _length_\(|p|\) of \(p\) is defined as the number of itemsets in \(p\). The _item-length_\(||p||\) of \(p\) is the sum of the sizes of the itemsets in \(p\), that is,  
\[||p||=\sum_{i=1}^{|p|}|P_{i}|, \tag{1}\]  
where \(|P_{i}|\) is the number of items in itemset \(P_{i}\). A sequence \(a=\langle A_{1},A_{2},\ldots,A_{m}\rangle\) is a _subsequence_ of another sequence \(b=\langle B_{1},B_{2},\)\(\ldots,B_{n}\rangle\), denoted by \(a\sqsubseteq b\), if and only if there exist integers \(1\leq i_{1}<i_{2}<\ldots<i_{m}\leq n\) such that \(A_{1}\subseteq B_{i_{1}}\), \(A_{2}\subseteq B_{i_{2}},\ldots,A_{m}\subseteq B_{i_{m}}\). If \(a\) is a subsequence of \(b\), then \(b\) is called a _super-sequence_ of \(a\), denoted by \(b\sqsupseteq a\).  
Let \(\mathbb{U}\) denote the set of all the sequences which can be built with itemsets containing items from \(\mathcal{I}\). A _dataset_\(\mathcal{D}\) is a finite bag of _(sequential) transactions_ where each transaction is a sequence from \(\mathbb{U}\). A sequence \(p\)_belongs_ to a transaction \(\tau\in\mathcal{D}\) if and only if \(p\sqsubseteq\tau\). For any sequence \(p\), the _support set_\(T_{\mathcal{D}}(p)\) of \(p\) in \(\mathcal{D}\) is the set of transactions in \(\mathcal{D}\) to which \(p\) belongs: \(T_{\mathcal{D}}(p)=\{\tau\in D:p\sqsubseteq\tau\}\). The _support_\(Supp_{\mathcal{D}}(p)\) of \(p\) in \(\mathcal{D}\) is the cardinality of the set \(T_{\mathcal{D}}(p)\), that is the number of transactions in \(\mathcal{D}\) to which \(p\) belongs: \(Supp_{\mathcal{D}}(p)=|T_{\mathcal{D}}(p)|\). Finally, the _frequency_\(f_{\mathcal{D}}(p)\) of \(p\) in \(\mathcal{D}\) is the _fraction_ of transactions in \(\mathcal{D}\) to which \(p\) belongs:  
\[f_{\mathcal{D}}(p)=\frac{Supp_{\mathcal{D}}(p)}{|\mathcal{D}|}. \tag{2}\]  
A sequence \(p\) is _closed_ w.r.t. \(\mathcal{D}\) if for each of its super-sequences \(y\sqsupset p\) we have \(f_{\mathcal{D}}(y)<f_{\mathcal{D}}(p)\), or, equivalently, none of its super-sequence has support equal to \(f_{\mathcal{D}}(p)\). We denote the set of all closed sequences in \(\mathcal{D}\) with \(CS(\mathcal{D})\).  
**Example 1**.: _Consider the following dataset \(\mathcal{D}=\{\tau_{1},\tau_{2},\tau_{3},\tau_{4}\}\) as example:_  
\[\tau_{1} =\langle\{6,7\},\{5\},\{7\},\{5\}\rangle\] \[\tau_{2} =\langle\{1\},\{2\},\{6,7\},\{5\}\rangle\] \[\tau_{3} =\langle\{1,4\},\{3\},\{2\},\{1,2,5,6\}\rangle\] \[\tau_{4} =\langle\{1\},\{2 an item can only occur once in an itemset, but it can occur multiple times in different itemsets of the same sequence. Finally, the sequence \(\langle\{6,7\},\{5\}\rangle\), whose frequency is 3/4, is a closed sequence, since its frequency is higher than the frequency of each of its super-sequences._  
Sections 2.1.1 and 2.1.2 formally define the two problems we are interested in.