The ideal result in pattern mining is a small set of patterns that identify the key structure of the data. In this paper we propose NemO, an ecient method for summarising discrete sequences in terms sequential patterns over an ontology. That is, NemO can detect patterns between not only the surface level, but also between the categories the events in the data are part of, and returns a small set of non-redundant patterns that together describe the data well. We formalize the problem in terms of the Minimum Description Length (MDL) principle, and propose an ecient and e↵ective heuristic to mine good models directly from data. Extensive empirical evaluation shows that NemO performs very well in practice, recovering the ground truth in synthetic data, and finds meaningful conceptual and grammatical patterns in text data.
Data often exhibits structure beyond what is apparent on the surface level, that is, beyond the actual observed values. As a toy example, consider both ‘cat meows’ and ‘dog barks’. Whereas these sentences show no syntactic pattern, if we know that ‘cat ’ and ‘dog’ are both nouns, and ‘meows’ and ‘barks’ are verbs, they are clear examples of a pattern noun–verb. If we know that the former two are ‘pets’, and the latter two are cases of ‘make noise’, a more specific pattern would be pet –make noise. In this paper we consider the problem of summarizing event sequences in terms of sequential patterns over an ontology, that is, to discover a small set of non-redundant patterns that describe the data well.
Our empirical evaluation shows that our method indeed discovers relevant patterns. Many of them are intuitive, such as he–Verb or the–Noun. More complex patterns from the Lord of the Rings novels, for example, was he– Verb-Conjunction–he, and matches indirect speech. Other patterns such as the– Adjective–Noun–and, from the same novel, match enumerations.
In particular, we formalize the problem in terms of the Minimum Description
Length (MDL) principle [
In this section, we introduce the notation used throughout the paper and further give a brief primer on MDL. 2.1
Our approach works on discrete sequential data D 2 ⌃ l of length l over an alphabet ⌃ . To address an item at position i, we will write Di. These items are part of an ontology, a directed graph O = G(V, E) where V is a set of vertices and E are directed edges between those vertices. The root node v⌦ is the most general node. The most specific nodes without outgoing edges are called leafs.
To indicate a path or trail from node a to b we write Tab. There are thus edges e1, .., en such that e1 starts at a and en ends at b. There is always a path from a node to itself, Taa, and the number of edges on this trace is specified as |Tnm|. Whenever several paths are possible, we will use the cheapest. The cost of the edges will be explained below. Coming back to v⌦ , we can say that 8 v 2 V T(v⌦ ,v), e.g. we can reach each node starting from the root.
Whenever we want to refer to an arbitrary item from the data D or a node from the ontology O, we will refer to it as entity or word w 2 V . Consider that an entity w that describes some part of the data D need not be part of the data itself, since it can be the ancestor of several items in the data. Consider that a1 and a2 could both be descendants from A, e.g. TAa1 and TAa2 . Then it could be the case that A 2 O, but A 62 D. By combining several entities, we can form a sequential pattern P of l events, i.e. P 2 V l. To refer to the ith entity in P , we write wi 2 P . If we want to cover the data with a pattern, we need to know where it matches the data. Whenever there is a path from w1 2 P to Di, a part of the pattern matches an entity in the data. If we can match all parts of the pattern in the right order, we have found a window D[i, j]. There are thus l data entities D1 . . . Dl 2 D[i, j] such that 1 < 2 . . . < l, l = |P | and 8 x 2 1 . . . l TDxwx where wx 2 P .
In particular, we consider serial episodes as patterns. That is, the occurrences of a pattern P are allowed to contain one or multiple gaps. As a consequence, it can be the case that |P | j i. Further the definition from the window is actually independent from P , so a window might contain none or up to several patterns.
Coming back to our example where A is an ancestor of a and given pattern P =AB and data D =abcab, there are several possibilities to match the pattern. To encounter this issue, we introduce the notion of a minimal window, which does not contain any other window. A window D[i, j] is minimal if ¬9 D[k, m] where k i and m < j or k < i and m j and both match P .
We can now define the support for a pattern by simply counting the number of all minimal windows in the data. The Support S(D, P ) of a pattern P is |{D[i, j])| window is minimal and matches P }|, i.e. cardinality of the set of all minimal windows of P in the data D. 2.2
MDL
The Minimum Description Length (MDL) principle [
Before we can formally define the problem we consider we have to specify both L(M ), the encoded cost of a model, and L(D | M ), the encoded cost of the data given a model. We do this in turn. 3.1
Before we can define how to encode a pattern, and therewith a model consisting
of patterns, we have to define how to reach an entity w in the ontology from a
starting node vs in O. From there onward, we have to identify which edges to
follow. As each edge has a normalized frequency assigned, we have a probability
distribution over the nodes we can reach from a given node. Shannon entropy [
X enm2 Tvt log Pfr n(frennm(e)no) eno2 E where the first part is the number of bits required to indicate whether we have already arrived, or not, at our destination node. In total, this sums up to the number of edges plus one. We then compute the logarithm of the normalized frequency of the individual given frequencies (fr (e)). Knowing how to encode a path in the ontology, we can define how to encode a pattern.
Encoding a Pattern. To encode a pattern, we first encode its length, and then one by one the paths to the entities w 2 X starting from the root node Pattern: A B
A B Gaps: A
X
B
A B
… Model gap fil s simplified: b1
Cover of data with Generalization and Gaps: Data: a1 C B a1 b2 B A b3 a1 c b2 A
A B C A B B A B A B C A Pattern Stream: Specification Stream: Gap Stream: a1 . g f a1 b2 . . b3 a1 b2 f f g f . Single Code:
Ω → B → b1 Generalization:
Ω → B Specification: → b1 b1 b2 C Ω a1
A … … B b3 B b1 of the ontology. As depicted in Fig. 1, the word need not be leaf and can be generalized. The encoded length of a pattern X hence is
L(X | O) = LN(|X|) + X L(w | O, v⌦ ) ,
w2 X
where we first encode the length of the pattern using the MDL optimal Universal
code for integers [
Since we allow pattern occurrences to have gaps, to ensure lossless decoding we have to encode when these happen. We do this with fill and gap codes per pattern. A fill code means that we can simply decode the current entity of the pattern, and advance to the next. A gap code means that we may not yet decode the current entity of the pattern, and have to instead read which entity comes next from the pattern stream (details below, an example is given in Fig. 1). To obtain optimal codes, we again consider the probabilities that gaps and fills are used. Hence, we define usage(X) as the times the pattern is actually used in the data.
To obtain the fill code, consider that we can only use a fills code for all but the first word in the pattern, yielding fills(X) = usage(X)⇥ (|X| 1). With gaps(X), we denote the total number of gaps in how we use P to describe the data. We thus define the codes for gaps and fills based on the particular probabilities, cf (X) =
fills(X) log gap(X)+fills(X) and cg(X) =
gap(X) log gap(X)+fills(X) .
Encoding a Model. A model, M = S [ P , which is a set of patterns P and singletons S. Due to their di↵erent nature, we will treat singletons and patterns in the model die↵rently.
We will start to encode which words from our ontology are actually used as
singletons in the data, and refer to this number by |OD|. We encode this number
again using the MDL optimal universal integer code, adding one in case the data
is empty. To further know which words we actually use in the data, we will use
a so-called data-to-model code [
We thus obtain as constant length for the singleton model L(MS | O) = LN(|OD| + 1) + LU (|O|, |OD|) + LU (|D| 1, |OD| 1). Given some data and an ontology constructed from this data, however, this ontology will not be changed during the mining process. Realizing that this encoding factor is instead constant, we will omit the details here.
Next, we encode the patterns in the model. We first make use of the previously introduced encoding of a pattern. We then add the number of gaps and obtain L(P | O) = X L(X | O) + LN(gaps(X) .
X2 P
Additionally, we need to know the support for the pattern to determine its code. We will proceed here analogously to the singletons, and encode how many patterns there are in total, how often they are used and then use the previously defined data-to-model code to transmit which distribution represents the data.
Further, by encoding the gaps for each pattern, we can compute their fills. We thus define the length of our model for the patterns by L(MP | O) = L(P | O) + LN(|P | + 1) + LN(usage(P ) + 1) + LU (usage(P ), |P |) . The length of our final model is then simply combining the model of the singletons and the patterns, L(M | O) = L(MS | O) + L(MP | O). We have now found a succinct way to represent the patterns and thus our model. Let us now consider how to use these patterns to determine the length of the data. 3.2
Given a model, we now need to specify how to encode the data D in bits given a model M . To do so without loss, we need three code streams. The first, the pattern stream CP , contains codes corresponding to patterns and singletons. As a pattern may generalize the observed data, we need the specification stream CS to reconstruct the actual entities. Last, but not least, as occurrences of patterns may include gaps, we need the gap stream CG to identify when we may decode the next entity of a pattern. An example of the three streams is given in Fig. 1. We call a lossless, complete representation of the data given the model an alignment. The length of this alignment is obtained by adding up all the codewords needed to represent the data.
The length of the pattern stream therewith is simply the length of the concatenation of codes used to describe the data,
L(CP | M, O) = X usage(X)L(c(X) | M ) .
X2 M Analogue, the length of the specification stream is simply the length of all specifications from the entities in the patterns to the entities in the data, L(CS | CP , M, O) = X L(wi | O, vs 2 CP ) .
wi2 D
L(CG | M, O) = Here vs is the starting point which we get from the pattern stream, and wi is the entity given in the data. Finally, for the gap stream we again simply concatenate all the gap and fill codes corresponding,
X
fills(X)cf (X) + gaps(X)cg(X) .
X2 P,|X|>1 The length of the alignment, and thus the length of the data given the model, is then the length of all three streams together: L(D | M, O) = L(CP | M, O) + L(CG | M, O) + L(CS | CP , M, O) . Hence, we also know the length of our data given the alignment, the patterns and the ontology. 3.3
Our aim is to know the total length of our data D when encoded using some model M and ontology O. This is formalized as L(D, M, O) = L(M | O) + L(D | M, O), taking into account the length of the model and the length of the data represented using the model. Resuming, the problem is formalized as finding the model for which we get the shortest description. More formal,
over an alphabet ⌃ and an ontology O (where ⌃ ⇢ O), find the smallest model M 2 M and best cover for D such that L(D, M, O) is minimal.
Discovering the optimal model for given data D and ontology O is hard. Given
an ontology O and a maximum pattern length of n, there are |O|n + |O|n 1 +
|O|n 2 + · · · + |O|2 + |O| di↵erent patterns. Considering arbitrarily large subsets
of these patterns, and the di↵erent ways they can be ordered, ideally we would
have to evaluate |O| ⇥ 1! + |O|2 ⇥ 2! + · · · + |O|n 1 ⇥ (n 1)! + |O|n ⇥ n! di↵erent
models. There are exponentially many alignments for a given model [
Hence, we resort to heuristics.
In this section, we present the necessary algorithms to compute the models and alignments formalized in the previous section. We will start by explaining how to cover a stream and then present our algorithm mining good code-tables. Finally we explain how we evaluate a refined model. 4.1
Given a model, we need to compute L(D | M, O), i.e. we need to find an
optimal alignment. We follow the general idea of Tatti and Vreeken [
This yields the optimal alignment given the current codes, which may be di↵erent from those that the globally optimal alignment would assign; whenever referred to as optimal alignment, we actually mean locally optimal alignment. As a basis, we first define a gain function that we optimize. We use the previously introduced window as D[i, j] from position i till j in the data and define its length as dj X c0(dk) + |X dk,k=i L(D[i, j], P ) = 1|fills(X) + (j i | X| ⇥ gaps(X)) .
We simplified the notation here, c0(dk) actually means c0(dk) = (c(w) at dk ( |X1 | c(X)) + L(w | O, vs 2 w 2 X) at dk if w 62 X if w 2 X In other words, we combine the pattern that spans the given window, its specification as well as all other words contained in the gaps with their singleton codes. This includes as well how many gaps and fills we need. To define a gain, the baseline of the data is L0(W ( , 1, |D|)) = Pwi2 D L(wi | v⌦ 2 O)), where every position is encoded as singleton. For a given window D[i, j] and pattern X we define the gain as gain(D[i, j], X) = L0( , i, j) L(X, i, j).
Given a set of non-overlapping windows, we can calculate the gain for the whole data by simply summing up over the di↵erent parts. The gain of the same pattern might however di↵er for di↵erent positions or windows in the data, since the specification and gaps might be di↵erent. Further the length of the specification can be replaced by |X1 | ⇡ (X), giving preference to di↵erent properties of the pattern. We will denote this gain as gain⇤ (D[i, j], X). In the following, we will always write gain⇤ (D[i, j], X), independent of the use of heuristics.
Additionally, we need function next (D[i, j]) which returns the next (optimal) disjoint window from the current one. We also define gain⇤ (next (D[i, j])) recursively in the sense that we refer not only to the gain of the window referred Algorithm 1: Discovering the optimal alignment
Result: alignment A for given weights 1 curopt 0 2 opt p1, p2, . . . p|D| 3 for i = |D| to 1 do 4 for D[i, j] 2 W do 5 if gain⇤ (D[i, j]) + gain⇤ (next(D[i, j])) > curopt then 6 optj Wi 7 curopt gain⇤ (D[i, j]) + gain⇤ (next(D[i, j])) 8 next(D[i, j]) opte 9 A alignment build using curopt and next() 10 return A to by next (D[i, j]), called D[i0, j0], but also to all best next windows. Thus, gain⇤ (next (D[i, j])) = gain⇤ (next (D[i, j])) + gain⇤ (next (next (D[i, j]))) . . . .
Starting with the best pattern in the beginning of the data, we iterate over next () to obtain our alignment. To do so, however, we first need to run Algorithm 1 first to instantiate next and to know the optimal pattern in the beginning.
We give an example in Fig. 2. We start at the end of the stream, move forwards and determine for each position the window up to this position with the highest gain. Best patterns for each starting position in Fig. 2 are marked by a star. The best option need not be a window that actually starts in this position, but might start at a previous location. Yet, a previous/following pattern might yield a higher gain. This case is marked in Fig. 2 with a gray star.
Additionally, for each pattern, we also determine next () to be the best pattern for the position where the patterns ends. In Fig. 2, to obtain the optimal alignment, we just use all patterns marked with a black star. When reaching the beginning of the data, we have determined the optimal next () for each pattern, and we also know the first pattern with the highest gain. Traversing the patterns calling next () for the first, best pattern yields our alignment. 4.2
Given an alignment, we can define new code lengths based on the frequencies in the given alignment. Di↵erent code lengths, however, influence again the alignment itself. We thus alternate these two steps, computing the alignment and updating the codes, until convergence. At this point, the question of convergence may arise. Since a frequently used pattern will receive a shorter code, it is even more likely to be picked in the next round. As a consequence, it is even more likely to be picked, and so on. For rarely used patterns, the reverse holds.
This results in an improvement of the code length at each iteration. Hence, the code length decreases monotonically and is bounded, since it can not be
Horizontal Pattern a1 b1d1 c d1a1 b2 a1 d2 b2 a2 c d2 A B D C D A B A D B A C D α β δ δ δ α β α δ β α δ δ Ω ΩΩΩΩΩ ΩΩ Ω Ω Ω Ω Ω arbitrarily short. Additionally, since there are only finitely many alignments, the algorithm converges and halts.
Refining a Model. This includes discovering new patterns, which is a complex task, as also illustrated in Fig. 3. A pattern can be either generalized or specified, e.g. we can change it vertically, or we can combine several patterns into a bigger one, which corresponds to a horizontal change. We will deal with this problem how to find new patterns later and for now assume that we have an oracle that returns promising refinements for our model.
We will first define how to evaluate patterns found. Only adding patterns will increasingly harm our model, hence we will discuss pruning it next. Since we will in both cases rely heavily on the computation of the alignment to quantify the use of a pattern, we will afterwards discuss how we can speed up the computation in this case, before we finally discuss how the model can be refined in detail.
Scoring Refinements Given some promising patterns to enhance our model, how do we decide whether we add them or not? Since we optimize L(D, M ), we can actually use this as a heuristic.
We test how each pattern X a↵ects the length of the encoded data. Straightforwardly, we can build the alignment for the model without the pattern, M and M [ X and compare the two lengths. After generating a set of promising candidates, we thus add them one by one to the model and compare whether they improve L(D, M ). If they do, we add them to the model.
Possibly, only the combination of two patterns enhances the model, but each on its own does not. To take this into account, we can as well add all pattern at once, and check them one by one if L(D, M ) L(D, M \X) is better or equal, where equal most likely indicates that the pattern is not used.
In L(D, M ) we also consider L(M ). Patterns that are part of the model and where useful in the beginning might however be replaced by other more complex patterns, and start to harm the size of model. We thus also need to consider pruning, not only enhancing the model.
Pruning a model The model grows as it is refined. Additionally, patterns might be used less, or not at all, as they are replaced. As a consequence, we have to prune our model and exclude patterns that harm the encoded length of model and data, L(D, M ). Yet not all of the patterns might be refined, and are thus worth testing. We will thus only consider patterns which encoding length and thus usage changed in the model. If the model improves without them, we delete the pattern from the model and add it to the set of rejected patterns.
Speeding Up When computing the e↵ect of adding or pruning a single pattern in the model, we do not have to recompute the whole alignment. Since large parts of the alignment will not change at all, we will briefly state how to optimize runtime for this task.
Given an old alignment and a pattern X, we first compute the set of Windows that relate to X, denoted by related (X, M, W ). This means either the windows where X is used, or, in case of a specialized/generalized pattern, where other instances of this pattern are used. In case of composed patterns, the set also contains Windows that contain parts of X. We then walk through this set of windows. In case we encounter windows containing X itself, we want to prune, and just delete the corresponding window. In the other case, given it is possible to insert a window with X, we just add it. In both case we propagate the changes and update all optimal values and return the optimal alignment build by iterating over curopt and next (), as before.
We can then compute the gain by simply comparing the length using the previously assigned patterns, say X, the newly assigned X0 and further consider all patterns that where additionally changed as Y and their replacements Y 0, gain(D[i, j], X0) = L(X, i, j)
L(X0, i0, j0) + X gain(D[k, l], Y 0) ,
Y 02 A where we recursively use gain() which returns the di↵erence of using Y 0 in place of Y . If the replacement is a specification, the sum might be zero, since no other pattens are a↵ected. If we refine horizontally, in contrast, it is very likely that we a↵ect other patterns. The total gain over the whole alignment for X0,
X i,j where X0 gain(X0, D) = gain(D[i, j], X0) , is then just the sum of the single parts where we replaced something by X. We do not need to take into account the other parts of the alignment that we did not change since they would rule out each other anyway.
Finding New Patterns An example is given in Fig. 3, where the refinement of a1 is shown. In each iteration, we refine the pattern only by one step, either vertically or horizontally. For each pattern, we form a tree containing all possible
Data: Data D, Ontology O
Result: Model M 1 M singletons(O, D) 2 A align(D, M ) 3 R ; 4 while L(D, M 0) < L(D, M ) do 5 M 0 M 6 Pnew generate(M, A, R) 7 for X 2 Pnew ordered by gain(X, D) do 8 if L(D, M ) L(D, M [ X) then 9 M M [ X 10 11 (M, R) (M, A) prune(M, D, A, R) align(M, D) 12 return M refinements/generalizations and their frequencies, where we expand the most frequent ones first. Before we start, we prune all combinations from our trees that were already rejected. Each time a new pattern is requested, we return the most promising combination that we have not yet investigated, where ties are broken arbitrarily. Given an updated alignment, we also update the frequencies and further prune accordingly. 4.3
We now present NemO,3 for summarizing event sequences with serial episodes over an ontology. The previously defined algorithm are combined as formalized in Algorithm 2. Given the data D and an ontology O, we first compute a singleton model (line 1), and an alignment for this singleton model M (line 2). We then alternate refining (i.e. adding patterns and pruning, lines 6–10) model M , and re-computing the alignment for the refined model (line 11), until L(D, M ) does not decrease anymore (line 4). 4.4
Given the algorithm, we now briefly analyze the runtime of NemO. To find new patterns we combine each pattern in the model with all nodes from the ontology, yielding O(|M ||O|). To find optimal windows for each pattern we go once through the data, thus O(D). To obtain an alignment we further add all found windows W , O(|W |). To prune, we recompute the alignment once for each pattern, hence O(|M ||D|). Iteratively computing an alignment and updating codes in i iterations takes O(i|M | + |W |). We repeat the whole procedure for n
iterations. The total complexity is thus O(n ⇥ (|M ||O||D||W | + |M ||D| + (i|M | + |W |))), and hence very high. In practice, however, we observe the number of iterations is typically small and the time until termination only some minutes. 5
In this section, we will discuss other approaches that are related to NemO. A
common way to find a patterns from data is frequent pattern mining [
We use MDL to identify the best summarisation. Krimp was the first
approach to use MDL to mine small sets of patterns from transaction data [
Bertens et al. [
In this section, we describe experiments on both synthetic and language data and show that NemO yields promising results. We implemented NemO in Java, and make the implementation available for research purposes.4 All experiments were ran on a Linux server with Intel Xeon E5-2643v2 processors with 64GB ram. 4 http://eda.mmci.uni-saarland.de/nemo/ Data
Model #patterns support |⌃ | = ⇢ [ not
L% iterations
We start with the synthetic data, where we generate data using ten finite
automatons (one for each planted pattern) to vary entities and thus require
generalization to identify them. As real world data, we run NemO on the three
Lord of the Rings books, Romeo and Juliet, Moby Dick and the addresses data
set. In these experiments, we rely on wordnet5 [
We rerun this experiments for length 1 000 and 5 000 and observe similar results. We do, however, observe that the shorter length increases the performance of the algorithm, there are more perfect matches. This is intuitive, since there is a better ratio between structure and noise. We now describe the experiments on language data. Before we discuss the patterns found, we will quickly comment on the runtime and the convergence of 5 http://wordnet.princeton.edu/, accessed March 2016. 6 http://nlp.stanford.edu/software/tagger.shtml, v3.6.0 from September 2015.
Data
Ontology
Model Name |D| |v 2 O| |leaves| |S| |P |
L% time it the algorithm. In general, we observe that the first iteration yields the largest decrease of encoded length. In general, 2 to at most 6 iterations are needed till convergence. We further observe that in contrast to the synthetic data, we improve the encoded length only by on average 10%. Convergence, gain in encoding and number of found patterns relate in a non-trivial way to the complexity of the data.
Before we discuss some mined patterns in detail, we will quickly report on the ontologies. The average depth of the ontology constructed for text data is 2.2 to 2.65, where the first layer is always composed by 17 nodes, corresponding to the 17 categories of the tagger. The number of leaves is strongly dependent on the complexity of the data, and varies between 4 000 and 20 000.
Important Singletons. As the empty model describes every entity in the data with a path from the root node in the ontology, NemO can identify interesting generalised singletons. Examples include Foreign word, Interjection7, in Addresses, that and another being travel 8 in Lord of the Rings, and as in Moby Dick.
Lord of the Rings. Looking closer at the non-singletons discovered in the Lord of the Rings books, we find grammatically correct patterns, such as they Verb or he Verb (as opposed to for example the speeches of the presidents, where I Verb or we Verb prevail). However, also more complex patterns are found. We present the following examples from the first book of the Lord of the Rings, where examples of matches sentences are given emphasized. Take into account that when analyzing the data, we ignore punctuation.
– he Verb Conjunction he: He said that he [did not think Bilbo was dead.] ;
He suspects, but he [does not know – not yet.]
word is found in all three novels, and thus an accurate description of their content. – the Adjective Noun and: [... and] the young Hobbits, and [Boromir.] ; [They dreaded] the dark hours, and [kept watch in pairs by night ...] – Determiner Conjunction and: [Like a dream] the vision shifted and went back, and [he saw the trees again.], [...] the language was that of Elven-song and [spoke of things little known on Middle-earth.] Not shown here, but also in the model are patterns matching simple grammatical structures, such as the Adjective Noun, to Verb or he/it/they Verb, as well as indirect speech and enumerations.
Additionally, we observe that is a guaranteed gap. We observe that such patterns containing allow to capture properties which are not obvious to humans, since they may di↵er a lot in meaning and seemingly in structure.
Moby Dick. Last, we consider the novel Moby Dick by Herman Melville. Example patterns we discover include – Pronoun Verb Noun: [And yesterday] I talked the same to Starbuck [there, ...] :[...,] I took my heavy bearskin jacket[, ...] – the Adjective Noun of : [... one of ] the old settlers of [Nantucket] ; [... and fumbling in] the huge pockets of [his ..] Many patterns start with Pronoun and then contain varying other parts. They di↵er in length between six and eight. Further, nine patterns start with he, ranging in length from three to six, also mutating in content. Additionally, there are 18 patterns beginning with either a or the and then also di↵ering in parts. Two examples for these patterns are presented above. Finally, we have 12 patterns which are composed of two parts, all representing intuitive English structure, such as he Verb, a Adjective, the noun, in determiner, and so on. 7
We considered the problem of summarizing event sequences with serial episodes over an ontology. We formalized the problem in terms of the Minimum Description Length principle, and proposed NemO, an ecient algorithm to mine good summaries directly from data.
Through extensive empirical evaluation we confirmed that NemO yields promising results in practice. On synthetic data, it recovers the ground truth and on text data we observe meaningful patterns that are beyond the surface. Of course the quality of the data influences the results we are able to achieve. Since tagging is an open research question, and current taggers might wrongly tag a word, further work in this area will alleviate this. Also the ontology used influences the results. Promising directions in future work include leveraging all parent nodes provided by wordnet, evaluating di↵erent ontologies for a single text, up to mining good ontologies directly from data.
Although the computation complexity of the summarisation problem is very
high, NemO discovers good models in only minutes. It will be interesting to
see how to leverage ideas from Lash [
The authors are supported by the Cluster of Excellence “Multimodal Computing and Interaction” within the Excellence Initiative of the German Federal Government. This work was supported by the German Federal Ministry of Education and Research (BMBF) through funding for the Center for IT-Security, Privacy and Accountability (CISPA) (FKZ: 16KIS0753).