# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 3 VC-Dimension of Sequential Patterns
Such upper bound is based on the notion of _capacity_\(c(p)\) of a sequence \(p\). The capacity \(c(p)\) of a sequence \(p\) is the number of distinct subsequences of \(p\), that is, \(c(p)=|\{z:z\sqsubseteq p\}|\). The exact capacity can be computed usingthe algorithm described in Reference [27], but it is computationally expensive and may be prohibitive for large datasets. Instead, Reference [8] proposed an algorithm to compute a more efficient upper bound \(\tilde{c}(p)\geq c(p)\). Let us consider that a first simple bound is given by \(2^{||p||}-1\), that may be a loose upper bound of \(c(p)\) because it is obtained by considering all the items contained in all the itemsets in \(p\) as distinct, that is, the capacity of the sequence \(p\) is \(2^{||p||}-1\) if and only if all the items contained in all the itemsets of the sequence \(p\) are different. The bound proposed by Reference [8] can be computed as follows. When \(p\) contains, among others, two itemsets \(A\) and \(B\) such that \(A\subseteq B\), subsequences of the form \(\langle C\rangle\) with \(C\subseteq A\) are considered twice in \(2^{||p||}-1\), \"generated\" once from \(A\) and once from \(B\). To avoid over-counting such \(2^{|A|}-1\) subsequences, Reference [8] proposes to consider only the ones \"generated\" from the longest itemset that can generate them. Then, the \(s\)-index is defined as follows. Definition 8 ([8]): Let \(\mathcal{D}\) be a sequential dataset. The \(s\)-index of \(\mathcal{D}\) is the maximum integer \(s\) such that \(\mathcal{D}\) contains at least \(s\) different sequential transactions with upper bound to their capacities \(\tilde{c}(p)\) at least \(2^{s}-1\), such that no one of them is a subset of another, that is the \(s\) sequential transactions form an anti-chain. The following result from Reference [8] shows that the \(s\)-index is an upper bound to the VC-dimension of the range space for sequential patterns in \(\mathcal{D}\). Theorem 2 (Lemma 3 [8]): _Let \(\mathcal{D}\) be a sequential dataset with \(s\)-index \(s\). Then, the range space \(RS=(X,\mathcal{R})\) corresponding to \(\mathcal{D}\) has VC-dimension \(\leq s\)._  
While an upper bound to the \(s\)-index can be computed in a streaming fashion, it still requires to check whether a transaction is a subset of the set of other transactions currently maintained in memory and that define the current value of the \(s\)-index. In addition, the computation of the upper bound \(\tilde{c}(p)\) on the capacity of a sequence \(p\) requires to check whether the itemsets of \(p\) are subsets of each others. To avoid such expensive operations, we define an upper bound to the \(s\)-index, that we call \(s\)_-bound_, which does not require to check whether the transactions form an anti-chain. Definition 9: Let \(\mathcal{D}\) be a sequential dataset. The \(s\)-bound of \(\mathcal{D}\) is the maximum integer \(s\) such that \(\mathcal{D}\) contains at least \(s\) different sequential transactions with item-length at least \(s\). Algorithm 1 shows the pseudo-code to compute an upper bound to the \(s\)-bound in a streaming fashion. It uses an ordered set to maintain in memory the set of transactions that define the current value of the \(s\)-bound. The ordered set stores pairs composed by a transaction and its item-length, sorted by decreasing item-length. In addition, it uses a hash set to speed up the control on the equal transactions. In practice, it is quite uncommon that the long sequences that define the value of the \(s\)-index are subsequences of other sequences, thus, removing the anti-chain constraint, the bound does not deteriorate. In addition, the usage of the naive algorithm to compute the upper bound on \(c(p)\), that is \(2^{||p||}-1\), it is equivalent to consider the transactions that have item-length at least \(s\) to calculate the \(s\)-bound, making the computation much faster without worsening the bound on the VC-dimension in practice. ```
Data: Dataset \(\mathcal{D}\). Result: Upper bound \(d\) on the \(s\)-bound of \(\mathcal{D}\).