dataesr/scientific-paragraphs-categorization huggingface dataset:
For example, Table  1  is a transactional database built from the set of four items I = {A, B, C, D}. In the rest of this paper, we use this dataset to give some illustrations. Originally, the goal of a pattern sampling technique is to access the pattern space L by an efficient sampling procedure simulating a distribution π: L → [0; 1] which is defined with respect to some interestingness measure m : π(•) = m(•)/Z where Z is a normalization constant, the sum of the interest of all pattern ϕ ∈ L in the dataset T , defined by Z = ϕ∈L m(ϕ, T ). The sampling of k patterns of the language L according to a distribution proportional to an interestingness measure m in the database T can be formulated as follows: Sampℓe k (L, T , m) = k i=1 {ϕ i ∼ m(L, T )} where ϕ ∼ m(L, T ) means that the pattern ϕ is drawn with a probability proportional to its interest m.
Formally, ϕ ∼ m(L, T ) ⇔ π(ϕ) = m(ϕ, T )/Z. In another word, the main objective of the output sampling methods is to have a sample of patterns representative of the set of patterns that can be extracted A B C D from the database. For example, if a pattern ϕ 1 has an interest twice as higher than that of a pattern ϕ 2 according to the interestingness measure chosen by the user, then ϕ 1 is twice as likely to be in the sample as the pattern ϕ 2. In the literature, there are several interestingness measures, but the most used of them is the frequency measure. Definition 1 (Frequency of a pattern). Given a dataset T and its language L. The frequency of the pattern ϕ ∈ L in T is defined as follows: freq(ϕ, T ) = |{t i ∈ T : ϕ ⊆ t i }|. Let m(•) = freq(•) for example, if ϕ 1 and ϕ 2 are two patterns of the language L having respective frequencies freq(ϕ 1 , T ) and freq(ϕ 2 , T ) such that freq(ϕ 1 , T ) = 2 × freq(ϕ 2 , T ), then the probability to draw ϕ 1 according to the frequency is twice that of ϕ 2.
Example 1. Figure  1  gives all patterns defined in T and their corresponding frequency. The normalization constant Z is the sum of the pattern frequency: Z = ϕ∈L(T ) freq(ϕ, T ) = 24. Within the dataset T , we have freq(AB, T ) = |{t 1 , t 4 }| = 2 and freq(AD, T ) = |{t 4 }| = 1. This means that π(AB, L(T )) = 2/24 and π(AD, L(T )) = 1/24. So, the probability to draw AB is twice that of AD in the dataset T. By definition, if there are in the language L at least two patterns having probabilities not null, then the operator Sample k , with k > 0, is non-deterministic. In other words, two draws with the same interestingness measure in the same database may not return the same k patterns. Let's also note that drawing k = k 1 + k 2 patterns following an interestingness measure m in the language L of a database T with Sampℓe k (L, T , m), comes down to draw k 1 patterns in L according to m with Sampℓe k1 (L, D, m), then k 2 patterns of L according to m with Sampℓe k2 (L, D, m).
Definition 2 (Length-based utility measures). A utility u defined from L to R is called a length-based utility if there exists a function f u from N to R such that u(ϕ) = f u (|ϕ|) for each ϕ ∈ L. Given the set U of length-based utilities, M is the set of interestingness measures m u such that for every pattern ϕ and database T , m u (ϕ, T ) = freq(ϕ, T ) × u(ϕ) with u ∈ U. For example, with the frequency, the utility function u freq (ϕ) = 1 for all pattern in L. If we consider the utility function u area (ϕ) = |ϕ|, we obtain the area. More generally, we consider the class of interestingness measures of the form freq(ϕ, T ) × u(ϕ) where u exclusively depends on the length of itemsets  [10]. It is also possible to combine many utility functions to form another one. Diop et al ϕ A B C D AB AC AD BC freq 3 3 3 1 2 2 1 2 marea 3 × 1 3 × 1 3 × 1 1 × 1 2 × 2 2 × 2 1 × 2 2 × ϕ BD CD ABC ABD ACD BCD ABCD freq 1 1 1 1 1 1 1 marea 1 × 2 1 × 2 1 × 3 1 × 3 1 × 3 1 × 3 1 × 4 m decay 1 × 0.
Definition 3 (Trie [27]). A trie is a data structure in the form of a rooted tree such that for any node, its descendants have the common prefix. Example 2. We represent the database T as a trie in Figure  2. To do this, each node of the trie is associated with a value which is the number of transactions of which it is the last element according to the order of insertion of the items, the number of times its label terminates a transaction of the dataset. It is important to note that many representations of the database T as a trie are possible according to the insertion order of the items (decreasing order of their frequencies, ascending order, lexicographic order, etc. ). Challenges in trie-based pattern sampling. Sampling pattern in trie structure is far from easy. In addition to guaranteeing an exact draw of a pattern (with a probability proportional to its weight), we need also to cleverly consider to new length-based utility to avoid time-consuming reprocessing.
In that case, the main challenges that we need to solve are as follows: efficiently build and weight the trie that corresponds to the database, -draw a pattern directly from the trie according to a probability proportional to its interest in the database. Problem statement. These main challenges can be finally solved by answering the following questions that we formulate here. Let T be a transactional database, u, u ′ ∈ U two length-based utilities, and µ and M two positive integers such that µ < M. 1. What additional information should be added to a (classical) trie to be able to directly sample patterns without needing to use the underlying transactional database? 2. How to draw a pattern ϕ from the language L [µ. M ] proportionally to m u (ϕ, T ) directly from the weighted trie? 3. How to compute Sampℓe k1 (L [µ.
TPSpace: Trie-based Pattern Space According to Figure  2 , two occurrences of the same pattern may occur in different paths of a trie, for example AC within the path A → B → C and AC within the path A → C. But they can also be merged, in the case of occurrences of the pattern AB (appearing in transactions of identifiers 1 and 4) which are represented in a single path of the trie. According to this analysis, the approach that we will present in this paper is based on two fundamental notions which are pattern occurrence (or occurrence for short) and language of occurrences. In the rest of this section, we present first the necessary elements to define a trie of occurrences. Then, we present the algorithm named TPSpace which designs a weighted trie of occurrences. We end it with an illustrative example for building a trie of occurrences.
Definition 4 (Occurrence and language fo occurrences). Let T be a transactional database and L [µ. M ] its pattern language under minimum µ and maximum M length constraints. If there is a transaction t of identifier i in T that contains the pattern ϕ ∈ L [µ. M ] , then we denote by ϕ i the occurrence of ϕ in the transaction t i. The set of occurrences in T under length constraint µ and M forms a language of occurrences denoted by L o [µ. M ]. Formally, L o [µ. M ] = {ϕ i : (∃(ϕ, t i ) ∈ L [µ. M ] × T )(ϕ ⊆ t i )}. The length of an occurrence ϕ i of a pattern ϕ ∈ L is equal to the length of ϕ. Note that L o is a set of occurrences while L is a set of patterns, and, unlike a pattern, an occurrence belongs to one and only one transaction. The frequency Diop et al of a pattern in L is the cardinality of the set of its occurrences in L o.
In other words, it is the number of transactions in T containing one of its occurrences. Example 3. If we consider the patterns of length 2, then we note that AB 1 and AB 4 are 2 occurrences of the pattern AB in the database T because AB is contained in transactions of identifier 1 and 4. The frequency of AB is therefore equal to 2. Similarly, AC 2 and AC 4 are 2 occurrences of the pattern AC. BC 3 and BC 4 are 2 occurrences of BC. Patterns AD, BD, and CD have single occurrences in transaction t 4. In this example, to draw a pattern of length 2 proportionally to its frequency in T , it suffices to uniformly draw an occurrence in the set L o [2. 2] (T ) = {AB 1 , AB 4 , AC 2 , AC 4 , BC 3 , BC 4 , AD 4 , BD 4 , CD 4 }. Thus, the probability of drawing the pattern AB in the set S is equal to π(AB, L [2.
2] (T )) = π(AB 1 , L o [2. 2] (T )) + π(AB 4 , L o [2. 2] (T )) = 2 9. Property 1. Let T be a transactional database, L and L o the pattern language and occurrence language of T respectively, and ℓ a positive integer. The probability to draw a pattern ϕ from L is computed from the occurrence language as follows: π(ϕ, L [ℓ. ℓ] (T )) = i π(ϕ i , L o [ℓ. ℓ] (T )). By convention, π(ϕ i , L o [ℓ. ℓ] (T )) = 0 if ϕ i ∈ L o [ℓ. ℓ] (T ). Proof. The proof of Property 1 is trivial and stem from the fact that L o [µ. M ] = {ϕ i : (∃(ϕ, t i ) ∈ L [µ. M ] × T )(ϕ ⊆ t i )} by definition. From Property 1, we know how to draw a pattern of length ℓ proportionally to its frequency among the set of patterns of the same length using a uniform drawing of occurrences. In this case, if we know how to draw a length ℓ proportionally to the sum of the utilities of patterns of length ℓ, so we know how to sample a pattern proportionally to its interest in the database.
Definition 5 (Total order relation between items). Let I be a set of items or literals on which the transactional dataset T is defined. -A total order relation on literals is said a lexicographic-based order and denoted by > lexico I , if it orders the literals of I according to lexicographic order. -A total order relation on literals is said a frequency-based order and denoted by > f req I if it orders the elements of I according to the descending order of their frequencies in T and according to the lexicographic order in case of equal frequency. In the following we denote > I a total order relation between the items of a dataset. Note that there are other types of total order relations in the literature that can be applied to literals. However, we will limit ourselves to the two total order relations previously defined as examples, even if our approach works with any total order relation on literals.
Definition 6 (Node identifier). Given a set of items I = {e 1 , • • • , e n } and a symbol ǫ ∈ I, a trie τ defined on I is a tree where every node η ∈ τ except the root contains a label denoted by η. label belonging to I, η. label ∈ I, and where the root r of the trie contains the label ǫ, r. label = ǫ. Thus, any node η ∈ τ can be identified by the sequence of node labels on the path from the root of τ to the node η. If P = ǫe i1. e i k is this sequence, we write it down more simply P = e i1. e i k for a node that is not the root, and we write P = e i k the label of the identified node η, P = η. label. Example 5. Considering the trie of the dataset T in Figure  2 , the node containing the label B resulting from the transaction t 4 is identified by P 1 = AB. This same node represents the item B coming from t 1.
Besides, the item B of the transaction t 3 is represented by the identifier node P 2 = B. In the following, we will often use the concept of sub-trie of a trie defined below: Definition 7 (Sub-trie). Let τ be a trie and P the identifier of a node. We denote by τ P the sub-trie of τ whose root is the node identifier P. We now define the concatenation operator • as follows: Definition 8 (Concatenation operator •). Let ϕ and ϕ ′ be two itemsets defined in I and ordered according to the total order relation > I , ϕ • ϕ ′ = ϕ ∪ {e ′ ∈ ϕ ′ : (∀e ∈ ϕ)(e > I e ′ )}. If > I is the lexicographic order, then we have B • AC = BC and A • BC = ABC. This concatenation operator allows us to define the notion of prefix that we are going to use in the definition of a projected database.
Definition 9 (Prefix). Let t be a transaction defined in I and P an itemset defined in I and ordered according to the total order relation > I. P is a prefix of transaction t if there is an itemset ϕ ⊆ I such as t = P • ϕ. In the dataset T in Figure  2 , P = AB is a prefix of the transaction t 4 = ABCD but P is not a prefix of the transaction t 3 = BC. According to Definition 9, transactions with a common prefix can be grouped. To identify where the occurrences of a pattern are represented in a trie, i. e. in which sub-trie. We are now going to introduce the notion of a projected database. Our definition is an adaptation of the notion introduced by  [30]. Definition 10 (Projected database). Let > I be a total order relation on all the items I, T a transactional database, and P the identifier of a node.
A projected database of T on P , denoted by T P , is a transactional database which contains for any transaction t of T with prefix P a copy of this transaction without the items of t preceding P. Formally, the projected database of T on P is defined by: T P = {(i, P • ϕ) ∈ N × L : (i, t) ∈ T ∧ t = P • ϕ} Example 6. Let us consider the trie of the transactional database T in Fig. 2. Occurrences in the projected database T AB are the occurrences stored in the sub-trie whose root is identified by the prefix AB: B Now, we will define precisely which are the pattern occurrences represented at the level of the projected database of T on the prefix P , by partitioning these sets of occurrences by their length.
Definition 11 (Computing weights Φ - ℓ and Φ + ℓ ). Let T be a transactional database and P a prefix. The set of occurrences of the projected database on the prefix P and having a length equal to ℓ is defined by: -The set of occurrences of the database projected on the prefix P , having a length equals to ℓ and containing the item P is defined by: φ + ℓ (P, T ) = {(i, ϕ) ∈ φ ℓ (P, T ) : P ∈ ϕ}. Its cardinality is denoted by φ ℓ (P, T ) = {(i, ϕ) ∈ N × L : (i, ϕ ′ ) ∈ T P ∧ ϕ ⊆ ϕ ′ ∧ |ϕ| = ℓ} Φ + ℓ (P, T ) = |φ + ℓ (P, T )|. -The set of occurrences of the database projected on the prefix P , having a length equals to ℓ and not containing the item P is defined by: φ - ℓ (P, T ) = {(i, ϕ) ∈ φ ℓ (P, T ) : P ∈ ϕ}. Its cardinality is denoted by Φ - ℓ (P, T ) = |φ - ℓ (P, T )|. As P is not defined if P is the empty prefix, we consider by convention that φ - ℓ (ǫ, T ) = φ ℓ (ǫ, T ), while φ + ℓ (ǫ, T ) = ∅.
Example 7. Let us consider the projected database T A = {(1, AB), (2, AC), (4, ABCD)}, we have φ + 2 (A, T ) = {(1, AB), (2, AC), (4, AB), (4, AC), (4, AD)} and φ - 2 (A, T ) = {(4, BC), (4, BD), (4, CD)} on the other hand. Then Φ + 2 (A, T ) = 5 and Φ - 2 (A, T ) = 3. Subsequently, at the level of the node identified by P of a trie, we will store as weight the cardinalities of these sets, distinguishing the subsets of occurrences of length ℓ containing or not the item P. 3. Enriched trie of the trie provided by Figure  2  After having introduced the necessary notions and notations for the enrichment of a classic trie to a trie of occurrences, we will explicitly define the latter. In the remainder of this chapter, the notation τ denotes a trie of occurrences. ǫ 10 9 4 A Φ + ℓ 3 5 3 Φ - ℓ 5 3 1 B 2 2 1 2 1 0 C 1 1 0 1 0 0 D 1 0 0 0 0 0 C 1 0 0 0 0 0 B 1 1 0 1 0 0 C 1 0 0 0 0 0 Fig.
TPSpace: Algorithm for building a trie of occurrences Now, we show how to build a trie of occurrences from a transactional database to efficiently take into account any type of length-based utility measure. Note first that this construction is done iteratively by adding the transactions one by one to the trie. In our case, we need to compute the positive and negative contributions of each transaction t within each node of identifier P such that P is a prefix of t. Property 2. Let T = {t 1 , • • • , t n } be a transactional database. We denote by T i the subset of transactions defined by T i = {t k ∈ T : 1 ≤ k ≤ i}. If P is a prefix of t i , then we have: Φ ⋆ ℓ (P, T i ) = Φ ⋆ ℓ (P, T i-1 ) + |t i | -|P | ℓ -ǫ , ǫ = 1 if ⋆ = + 0 if ⋆ = - By convention, Φ - ℓ (P, T 0 ) = 0 whatever the identifier P.
Algorithm 1 TPSpace 1: Input: A transactional database T , the minimum µ and maximum M length constraints 2: Output: A trie of occurrences τ 3: τ ← CreateNode(ǫ) ⊲ Creation of the trie root node 4: for t ∈ T do 5: AddChild(c, η) for ℓ ← µ to M do 6: τ. Φ -[ℓ] ← τ. Φ -[ℓ] + |t| 13: for ℓ ← µ to M do 14: c. Φ + [ℓ] ← c. Φ + [ℓ] + |t|-j ℓ-1 15: c. Φ -[ℓ] ← c. Φ -[ℓ] + |t|-j ℓ 16: η ← c 17: return τ Algorithm 1 describes the TPSpace method to create a trie of occurrences of an input database T according to a total order relation > I. We initialize the trie of occurrences (line 3) by creating an empty node with the CreateNode function. For each transaction t of the input database whose items follow the order relation > I , we start at the root then, using Property 2, we compute its total contribution in the trie according to the lengths which we add to the root (line 6).
Then, for each item t[j] of the transaction being inserted in the trie, if there is not a child node c labelled with the item t[j] according to the SearchChild function (line 9), we create it using the function CreateNode (line 11) then we add it among the children of η with the function AddChild (line 12). Finally, we add the positive Diop et al and negative contributions of the transaction t to the node c (lines 13 to 15) using Property 2. We now go to node c (line 16) and the process starts again with the item at position j +1 in t. Finally, line 17 returns the trie of occurrences τ for the transactional database T. Example 10. In this example, we show how to build a trie of occurrences with Algorithm 1. Let's consider the total order relation > f req I between the items, let us construct the trie of occurrences corresponding to the transactional database T given in Figure  2.
First, we compute the frequency of each item, and then we fix the order of the items. By scanning the database T , we have A > f req I B > f req I C > f req I D according to the example 4. All the items of each transaction in the database must follow this order. Note that this order is important since each path of the trie also follows it. Assuming now that we want to sample patterns of length between µ = 1 and M = 3, we start the construction of the trie by creating the root with the function CreateNode(ǫ). We do not mention the exhaustive list of computations of the weights, but Figure  4  gives all intermediate results for the construction of the trie of occurrences τ corresponding to the database T. Now, we show step by step how to insert transactions into the trie by computing the weight of each node each time an occurrence is counted in it.
Drawing approach To draw a pattern of length ℓ proportionally to a length-based utility multiplied by its frequency in the database, we can uniformly draw an occurrence among the set of occurrences of length ℓ. To do this, we first need to draw an integer ℓ ∈ [µ. M ] proportionally to Φ ℓ (ǫ, T ) × f u (ℓ) with a length-based utility u. Second, we uniformly draw a length ℓ of an occurrence among the set of length ℓ of occurrences in the database, but directly from the trie. The drawing of an occurrence of a given length is not trivial because we do not know a priori where it is in the trie. This means that it is necessary to cleverly scan the nodes of the trie to find the sought occurrence. Of course, there already exist numbering systems for tree traversal (like prefix or postfix orders) but in our case, the goal is not to number the nodes of the trie, but the occurrences of patterns represented by the trie.
Definition 13 (Ranking occurrences by length). If ϕ j is an occurrence of length ℓ from a database T and τ is a trie constructed from T , we denote rank ℓ (ϕ j , τ ) = rank ℓ (ϕ j , τ ǫ ) the rank of this occurrence relative to the trie τ. This rank can be defined recursively as follows: -If ϕ j ∈ φ - ℓ (P, T ), and more precisely if ϕ j ∈ φ ℓ (P • e i , T ) where e i = τ P. child [i] , then rank ℓ (ϕ j , τ P ) = i-1 k=1 Φ ℓ (P • e k , τ ) + rank ℓ (ϕ j , τ P •ei ). -If ϕ j ∈ φ + ℓ (P, T ), then ϕ j = P • ϕ ′ j. And in this case, if ϕ ′ j ∈ φ ℓ-1 (P • e i , T ) where e i = τ P. child [i] , then rank ℓ (ϕ j , τ P ) = Φ - ℓ (P, τ )+ i-1 k=1 Φ ℓ-1 (P •e k , τ )+ rank ℓ-1 (ϕ ′ j , τ P •ei ). -Finally, if ϕ j is an occurrence of length 1, we define rank 1 (ϕ j , τ P ) by: rank 1 (ϕ j , τ P ) = rank > I (ϕ j , φ 1 (P, T )) where > I defined on items is extended to occurrences of length 1 as follows: (i, e) > I (j, e ′ ) if e ′ > I e or e = e ′ and i > j.
In this list of occurrences, to draw a pattern proportionally to its frequency, it suffices to uniformly draw a rank between 1 and the highest rank, and return the occurrence which has that rank. For example, we have 2 occurrences of AB in ranks 6 and 7. This means that the probability of drawing the pattern AB among the set of patterns of length exactly equal to 2 is 2  9 , therefore proportional to its frequency. If the user chooses the frequency as interestingness measure, then from the trie of occurrences, we draw ℓ = 2 with a probability of 9  23. Therefore, we can note that the pattern AB is drawn in the trie with a probability equal to 9  23 × 2 9 = 2 23 , therefore proportional to its frequency in the database.
Trie-based pattern sampling algorithm Algorithm 2 takes as input a trie of occurrences τ , a length-based utility u ∈ U, and minimum µ and maximum M length constraints. It returns a pattern ϕ drawn proportionally to its interest in the database corresponding to the trie. Draw a length ℓ between µ and M. Line 4 draws an integer ℓ between µ and M proportionally to the number of occurrences of length ℓ, i. e. τ. Φ -[ℓ] multiplied by the utility of a length ℓ, f u (ℓ). Uniform drawing of an occurrence of length ℓ. To sample an occurrence of length ℓ, we uniformly draw a rank x in the interval [1. τ. Φ -[ℓ]] (line 5). To find the occurrence corresponding to x, we scan the trie in depth-first search from left to right by looking for the nodes that satisfy the system of inequalities in line 7 which is based on Definition 13.
Correction Property 3 shows that our sampling method TPSampling does an exact draw of a pattern. Property 3. Let τ a trie of occurrences from a transactional database and u a length-based utility, Algorithm 2 draws a pattern ϕ according to a probability proportional to its frequency weighted by its utility. Proof. Let ϕ i be an occurrence of a pattern of length ℓ. The probability that ϕ i is returned is π(ℓ) × π(ϕ i /ℓ). Let Z = ℓ f u (ℓ) × τ. Φ -[l]. We know from line 4 that π(ℓ) = f u (ℓ)×τ. Φ -[l]/Z. According to line 5, the rank of an occurrence ℓ is drawn uniformly among the ranks of the occurrences of the same length. Lines 9 to 12 use the definition 13 in order to access the occurrence of a given rank. So from lines 6 to 13, we have π( ϕ i /ℓ) = 1/τ. Φ -[l]. It follows that π(ϕ i ) = fu(ℓ)×τ.
Space complexity The size of memory occupied by the trie of occurrences is not negligible, especially with large datasets. However, it can be optimized during the preprocessing phase by reducing the number of nodes. For example, considering that the items are ordered according to the decreasing order of their frequencies, the number of nodes in the trie is much lower than the upper bound which is in O(2 |I| ). In that case, a tight upper bound of the number of nodes is detailed in  [31]. The size of a trie of occurrences also depends on the information stored in the nodes. In our case, the higher the maximum length constraint, the larger the arrays and the greater the memory size. This means that if the number of nodes in the trie of occurrence is z, µ and M the minimum and maximum length constraints respectively, then the size in memory of the trie is in O(z × 2 × (Mµ)).