Snigdha Dagar

Frederic Alexandre

Nicolas Rougier

From concrete to abstract rules : A computational sketch

Keywords: Cognitive control, Prefrontal cortex, Computational model, Abstract rules

A multi-dimensional stimulus can elicit a range of responses depending on which dimension or combination of dimensions is considered. Such selection can be implicit, providing a fast and automatic selection, or explicit, providing a slower but contextualized selection. Both forms are important but do not derive from the same processes. Implicit selection results generally from a slow and progressive learning that leads to a simple response (concrete / first-order) while explicit selection derives from a deliberative process that allows to have more complex and structured response (abstract / second-order). The prefrontal cortex (PFC) is believed to provide the ability to contextualize concrete rules that leads to the acquisition of abstract rules even though the exact mechanisms are still largely unknown. The question we address in this paper is precisely about the acquisition, the representation and the selection of such abstract rules. Using two models from the literature (PBWM and HER), we explain that they both provide a partial but differentiated answer such that their unification offers a complete picture.

Introduction

Two main strategies are generally reported for the selection of behavior [START_REF] Daw | Uncertainty-based competition between prefrontal and dorsolateral striatal systems for behavioral control[END_REF][START_REF] Domenech | Executive control and decision-making in the prefrontal cortex[END_REF]. On the one hand, implicit memory elaborated by slow learning processes can generate a rigid behavior (also called default behavior), robust in stable worlds, easy to generate but difficult to quickly adapt to changes. On the other hand, explicit memory manipulating models of the world can be used for the prospective and explicit exploration of possible behaviors, yielding a flexible and rapidly changing strategy, where behavioral rules can be associated to contexts and selected quickly as the environment changes. In the simplest case, this means learning rules defined as associations between an object's properties and a direct response. Such rules can be called concrete, while more complex or abstract rules may involve the learning of second order relations on top of the first-order rules. The prefrontal cortex (PFC) is believed to provide the ability to contextualize concrete rules that leads to the acquisition of abstract rules [START_REF] Domenech | Executive control and decision-making in the prefrontal cortex[END_REF]. Considering the number of contexts we encounter every day and the ease with which we select appropriate strategies for each, some relevant questions arise : How do we represent these strategies or rules and how do we determine which one is appropriate ? An important way of understanding how the PFC supports contextual learning and implements cognitive control is thus to understand how its representations are organized and manipulated.

There is sufficient evidence to suggest that the PFC is organized hierarchically [START_REF] Badre | Cognitive control, hierarchy, and the rostro-caudal organization of the frontal lobes[END_REF] with more caudal areas learning first-order associations and more rostral areas putting them in context to facilitate learning of abstract rules. This can be done by top-down modulation in the PFC, which underlies the ability to focus attention on task-relevant stimuli and ignore irrelevant distractors, in two ways : either as a result of weight changes in modulated pathways and predictions, or through activationbased biasing provided by a working memory system. These mechanisms have been explored in two prominent models of the PFC. One well established model for cognitive control function through the working memory system is the Prefrontal cortex and Basal ganglia Working Memory model (PBWM) [START_REF] O'reilly | Making working memory work: a computational model of learning in the prefrontal cortex and basal ganglia[END_REF] in which a flexible working memory system with an adaptive gating mechanism is implemented. At the biological level, the model proposes that the PFC facilitates active maintenance for sustaining task-relevant information, while the Basal Ganglia (BG) provides the selective gating mechanism. A hierarchical extension of this model [START_REF] Frank | Mechanisms of hierarchical reinforcement learning in corticostriatal circuits 1: computational analysis[END_REF] proposes that hierarchical control can arise from multiple such nested frontostriatal loops (loops between the PFC and the BG). The system adaptively learns to represent and maintain higher order information in rostral regions which conditionalize attentional selection in more caudal regions.

A second hierarchical model, Hierarchical Error Representation (HER) [START_REF] Alexander | Hierarchical error representation: a computational model of anterior cingulate and dorsolateral prefrontal cortex[END_REF], explains cognitive control in terms of the interaction between the dlPFC (dorsolateral prefrontal cortex) and the mPFC (medial part of the PFC). The dlPFC learns to maintain representations of stimuli that reliably cooccur with outcome prediction error and these error representations are used by the mPFC to refine predictions about the likely outcomes of actions. The error is broadcasted through the PFC in a bottomup manner, and modulated predictions from top-down facilitate selection of an appropriate response. Thanks to its recursive architecture, this model, presented in more details below, can elaborate hierarchical rules on the basis of learning by weight updating, both to select pertinent stimuli and to map a representation inspired with principles of predictive coding [START_REF] Alexander | Frontal cortex function as derived from hierarchical predictive coding[END_REF]. In addition to its elegant recursive mechanism, proposing an original computational mechanism to account for the hierarchical structure of the PFC, the HER model is also very interesting because its proposes to decompose the functioning of the PFC between, on the one hand, the prediction of the outcome and the monitoring of the error of prediction and, on the other hand, the elaboration of contextual (and possibly hierarchical) rules to compensate errors. This distribution of functions has also been reported between respectively the medial and lateral parts of the PFC [START_REF] Domenech | Executive control and decision-making in the prefrontal cortex[END_REF], yielding more importance to the biological plausibility of the HER model. For these reasons, the HER model could be presented as a more elaborated and accurate model of the PFC, except for one point of discussion that we put forward here. All the adaptations of the HER model are made through learning by weight modifications, whereas the property of working memory of the PFC, as it is for example exploited in the PBWM model, is often presented as a key mechanisms for its adaptive capabilities. An important question is consequently to determine up to which point working memory and attentional modulations are necessary for the learning of hierarchical rules in cognitive control.

In the work presented here, we seek to answer specific questions about the nature of top-down modulation and selective attention, through the lens of hierarchical learning and representations. We start from the implementation of the hierarchical HER model and its study for a task in which individual first-order rules can be learned alone or associated within specific contexts to form second-order rules. We then evaluate the performances of the HER model in these different cases and compare them with a case where an attentional mechanism should be deployed to facilitate and orient its learning. As discussed in the concluding part, we observe that the attentional mechanism should be considered not only for the processing of information but also for the learning of rules, particularly in the hierarchical and contextual case.

Methods

This section first summarizes the HER model algorithm and equations, as described in the original paper [START_REF] Alexander | Hierarchical error representation: a computational model of anterior cingulate and dorsolateral prefrontal cortex[END_REF] and subsequently presents the task that we have chosen for our study.

Model Details : HER

Working Memory Gating At each level of the hierarchy, external stimuli presented to the model may be stored in WM based on the learned value of storing that stimulus versus maintaining currently active WM representations. External stimuli are represented as a vector s, while internal representations of stimuli are denoted by r. The value of storing the stimulus represented by s in WM versus maintaining current WM representation r is determined as :

v = X T s (1)
where X is a matrix of weights associating the external stimuli (s) with corresponding WM representations (r). The value of storing stimulus s i (v i ) is compared to the value of maintaining the current contents r j of WM (v j ) using a softmax function :

probability of storings i = (exp βvi + bias) (exp βvi + bias) + exp βvj (2)
Outcome Prediction Following the update of WM, predictions regarding possible responses and outcomes are computed at each hierarchical layer, using a simple feedforward network :

p = W T r (3)
where p is a vector of predictions of outcomes and W is a weight matrix associating r and p Top-Down Modulation Beginning at the top of the hierarchy, predictions are used to modulate weights at inferior layers and modulated predictions are computed, as shown with the red arrows in figure 1.

For a given layer, the prediction signal p' additively modulates stimulus-specific predictions p generated by the lower layer. In order to modulate predictive activity, p' is reshaped into a matrix P' and added to W in order to generate a modulated prediction of outcomes :

m = (W + P ′ ) T r (4)
These modulated predictions are then used to modulate predictions of additional inferior layers (if any exist)

m = (W + M ′ ) T r (5)
Response Selection Actions are learned as response-outcome conjunctions at the lowest layer of the hierarchy. To select a response, the model compares the modulated prediction of correct feedback to the prediction of error feedback, for each candidate response :

u response = m response/correct -m response/error (6)
This is then used in a softmax function to determine a response :

P rob(u i ) = exp γui exp γu (7)
Bottom-up Process Following the model's response, it is given feedback regarding its performance and two error signals are computed at the bottom most hierarchical layer, one comparing the unmodulated predictions to the outcome :

e = a(o -p) (8)
and another comparing the modulated predictions to the outcome :

e = a(o -m) ( 9
)
where o is the vector of observed outcomes and a is a filter that is 0 for outcomes corresponding to unselected actions and 1 everywhere else.

The outer product of the first error signal and the current contents of the WM at the bottom level is used as the feedback signal for the immediately superior layer where this process is repeated (figure 1).

O ′ = re T (10)
Effectively, at the second layer, the outcome matrix is a conjunction of stimuli, actions and outcomes. This matrix is reshaped into a vector o' and used to compute the prediction error at the superior layers :

e ′ = a ′ (o ′ -p ′ ) (11)
Weights Updating The second error signal is used to update weights within the bottom-most hierarchical layer, it updates the weights connecting the WM representation to prediction units (W), as well as weights in the WM gating mechanism (X):

X t+1 = X t + (e T t W t • r t )d T t (12)
An eligibility vector d is used instead of the stimulus vector s. When a stimulus i is presented, the value of d i is set to 1, indicating a currently observed stimulus and at each iteration of the model, d is multiplied by a constant decay parameter indicating gradually decaying eligibility traces.

W t+1 = W t + α(e t r T t ) (13)

Task

To design our task, we consider the framework introduced by [START_REF] Koechlin | The architecture of cognitive control in the human prefrontal cortex[END_REF] which is composed of three subtasks where the stimuli are letters having three dimensions: color (red, green or black), case (upper or lower) and sound (vowel or consonant). In the first subtask (Block 1 in figure 1(b)), black color indicates to ignore the stimulus and green color indicates to discriminate the case (rule T1: left button for upper, right button for lower). In the second one (Block 2 in figure 1(b)), black color indicates to ignore the stimulus and red color indicates to discriminate the sound (rule T2: left button for vowel, right button for consonant). The third one (Block 3 in figure 1(b)) is a random mix of trials from the other two blocks. This framework is interesting because, whereas rules T1 and T2 in blocks 1 and 2 require the subject to attend to a single dimension of the stimulus, block 3 requires to pay attention to both and to decide which rule to apply based on the third (contextual) dimension. Let us also mention here that, while there is no apparent difficulty with such tasks, it is actually harder than it appears depending on the way a task is learnt. During block 1, one can either learn the rule : "green means case and black ignore" or the rule: "black ignore, else case". The same is true for block 2 with sound. If we now consider block 3 and depending on how a subject learnt the first two blocks, she may succeed or fail immediately. In this latter case, this means block 3 cannot exploit previous learning and has to be (re)learnt.

The original task was cued by instruction and corresponding performances were reported in the paper [START_REF] Koechlin | The architecture of cognitive control in the human prefrontal cortex[END_REF]. Here, we wish to explore the inherent capability of a model to learn an abstract and hierarchical rule task without instructional cues, as in the paradigm reported by [START_REF] Badre | Frontal cortex and the discovery of abstract action rules[END_REF] and also to consider how the hierarchy can be learnt, depending on how information is represented in the model. We used two types of learning paradigms for the simulations : the first paradigm in which rules T1 and T2 were learned one after the other, and the performance of the model was then tested on random trials interleaved from rule T1 and T2 (to say it differently, we apply successively block 1, 2 and 3). In the second paradigm, an entire abstract rule that we call T3, corresponding to the selection on rules T1 and T2 depending on the contextual cue 'color' was directly learned (block 3 applied first) and performance of the model was subsequently tested on rule T1 and T2 (blocks 1 and 2). In the next section, we report performances observed with the HER model and with an adapted version that we propose subsequently.

Results

We have first studied how the HER model, as it has been designed (cf section 2.1), can address the tasks defined above, under the two mentioned paradigms (cf section 2.2). Due to the design of the HER model, each layer can only map or process one stimulus value, thus requiring as many layers as there are stimulus dimensions. The mapping in the model is also highly sensitive to the stimulus dimensions relative to one another, particularly higher-dimensional stimulus are preferentially mapped onto the lowest hierarchical layer. This rests on the assumption that stimulus dimensions better able to predict and reduce uncertainty about the response are mapped to lower layers.

This may not always be the case in real life situations though. We often have to adapt and generalize the same rules over several different contexts. In the task we consider as well, the context is determined by the color, which has 3 possible values -one of which always maps to the same response (to ignore) and the other 2 determine the response based on other stimulus dimensions.

Learning Curves

Performance observed for the first and second learning paradigms are reported in figures 2 (a) and (b) respectively. We see in the figure 2 (b) that due to its hierarchical structure, when there is an underlying abstract rule to learn (rule T3), the model is able to use the hierarchical information to acquire the rule while retaining performance in each of the sub-rules (Rule T1 and T2). It does so by monitoring an "error of errors" at each hierarchical layer, broadcasting this error to superior layers (bottom-up processing) that put it in context with the stimulus feature being attended to and finally sends this prediction information to the lower layers (top-down modulation) which are able to then select the appropriate response. In the figure 2 (a), we show that when the composite rules are first learnt sequentially, the model is not able to compose them into a single rule, but instead has to relearn its representations to reach optimal performance.

Next we show that due to the design of the model, a task which has only one level of hierarchy, such as the one considered here, can not be learnt with a model with 2 layers. In figure 2 (c) we see that with 2 layers, the model is able to learn the subparts of the rule (rules T1 and T2), but performance on the composite rule T3 saturates at 80%. By exploiting the gating mechanism, each sub-rule can be learnt individually by gating the 2 relevant feature dimensions at the 2 layers (color, vowel/consonant for rule T1 and color, lower/upper case for rule T2). However, in the third rule T3 when the 2 relevant features change from trial to trial to determine the correct response, the model fails to learn, since the contextual stimulus features don't provide top-down information about "which" other stimulus feature to attend to at the lower layer.

Gating weights

In the model, the gating weights determine both, when to update or maintain a stimulus feature, and also which of the stimulus features is to be gated. We observed the adjusted weights after each rule that is learned. In the first block, vowel, consonant and black have high values of getting updated at the lowest layer, while in rule T3 all the "lower level" cues have high values of getting updated. In such a case, there is again competition between which one of them to gate, and both can win with close probabilities, in the absence of any information from the superior layers. Depending on what is gated into the top two layers, any of those mappings could emerge.

Prediction weights

The prediction weights at layer 0 are Stimulus-Action-Outcome conjugations and the gating mechanism determines which stimulus and in turn which action-outcome association is to be selected. The selected associations are then modulated by superior layers and used the determine the response. At layer 1, the prediction errors of layer 0 are contextualized to make SxSxAxO conjugations and so on.

In the task considered for all our simulations, there are 5 concrete rules or S-A-O predictions to learn : Black -Action3, Vowel, Lower case -Action1 and Consonant, Upper case -Action2 (figure 1 (b)). In figure 3, we present examples of how a model with 3 layers selects a response by additive prediction modulation. We observed that elaborating a mapping between the stimulus and what is gated into the internal representation (r) at different layers could be done in different ways, including randomly, as long as these mappings led to orthogonal and mutually exclusive activation of predictions (in W). For example, in figure 3 (e), in Block 2, the color red was not gated into the internal representation, but the random gating of the other 2 dimensions still led to an appropriate modulated prediction that could initiate the correct response.

New Model

To explain the deficit of attentional mechanism in the HER model, and illustrate the advantage of our proposal, we performed some simple simulations. The model was trained individually on the two discrimination tasks ie, on the two concrete rules (T1 -vowel/consonant and T2 -lower/upper case), to obtain prediction weights or Stimulus-Action-Outcome associations as in figure 4 (b). We tested the ability of the HER model with 2 layers, to use this information and contextualize it to learn the abstract rule. The bottom layer of the model was initialized to the predictions previously learned and moreover, it was "frozen" such that no learning happened at this level, implying that these behaviors were rigid. At the upper layer, the gating weights were biased to update the internal representation with the context, which was the color in this case, implying saliency to previously unattended cues. As expected, the model failed to learn the abstract rule with these modifications. With the modified model, we used the same protocol ie the bottom layer was kept frozen, and there was a bias added (c) (d) to the upper layer to encourage gating of the color. However, instead of an independent gating at the bottom layer, we included an output gating from the upper layer, which used the prediction errors at the upper layer to select which stimulus dimension was going to be gated into the bottom layer (figure 4 (a)). To put it more generally, the bottom layer was responsible for response selection while the upper layer was responsible for action-set selection through targeted attention (cf [START_REF] Domenech | Executive control and decision-making in the prefrontal cortex[END_REF] for more details about the structuring concept of action-set and its role in PFC information processing). Our modified model achieved optimal performance fairly quickly, as shown in 4 (c).

R1/C R1/E R2/C R2/E R3/C R3/E L 2 -C L 1 -W L 0 -W L 0 -m o d u
R1/C R1/E R2/C R2/E R3/C R3/E L 2 -U L 1 -G L 0 -V L 0 -m o d u
R1/C R1/E R2/C R2/E R3/C R3/E L 2 -V L 1 -G L 0 -G L 0 -m o d u
R1/C R1/E R2/C R2/E R3/C R3/E L 2 -V L 1 -U L 0 -U L 0 -m o d u

Discussion

The PFC plays a major role in cognitive control and particularly for learning, selecting and monitoring hierarchical rules. For example, in experimental paradigms, discrimination or categorization tasks can be considered as first-order rules which could be learned individually. However, when conflicting stimuli are presented simultaneously, a contextual cue is needed to identify which of the first order rules is to be applied, thus forming second-order rules.

The inner mechanisms of the PFC have been studied in computational models and among them, the property of working memory used for biasing by selective attention in the PBWM model and, more recently in the HER model, the separation between outcome prediction error monitoring, and hierarchical rule learning. Considering the indisputable progress brought by the design of the HER model, we questioned whether it was now a standalone model of the PFC to be used in any circumstances or if the contribution of certain mechanisms like selective attention was still to be considered in some cases and possibly added to the general framework of PFC modeling. More specifically, considering the deployment of cognitive control in realistic behavioral tasks and considering that most hierarchical representations arise from the intersection between agents and the problems they face, and are created over time in a learning process, in a rapid and flexible way, our question was to know if the HER model could account for this kind of process. Using a task elaborated along two paradigms, we show that, when concrete rules are already learnt and need to be contextualized, the use of a biasing selective attention mechanism is more effective than modulated weights changes in displaying effective cognitive control. When concrete rules are acquired first, superior layers must learn to select the appropriate concrete rule by targeted attention, rather than by relearning representations. We observe that a subject can perform optimally on a given task even though she uses a different rule representation compared to the official one. On a single task, this has no consequence and there is actually no way to know which exact rule is used internally. However, when this rule needs to be composed with another rule such as to form a new rule, this may pose problem and lead to bad performance. This has been illustrated on the task: if a subject uses any of the alternative rules for tasks T1 or T2, she'll be unable to solve task T3 even though this task is merely made of a mix of T1 or T2 trials. The reason for the failure of the HER model in this case is to be found in the failure to attend the relevant dimension of the task, here, color, thus claiming for considering and incorporating this mechanism to a versatile PFC model. Analyzing these results in a more general view, we can remark that most experimental paradigms that study hierarchy break down the complexity of a task by providing instructional cues to the participant. Even in studies with rodents and non-human primates, shaping is used in learning paradigms to enable the learning of complex or abstract rules. In developmental learning, this kind of shaping is called curriculum learning. It is evident that such breaking down of complexity must facilitate the acquisition of abstract rules, and hence modeling approaches must demonstrate these behavioral results.

From a more conceptual point of view, the term hierarchy can be used in many different ways, two common ones being processing hierarchies and representational hierarchies. In the first, higher levels exert control over lower levels, for example by controlling the flow of information or by setting the agenda for lower levels [START_REF] Miller | An integrative theory of prefrontal cortex function[END_REF]. In the second one, higher levels form abstractions over lower levels, such that lower levels contain concrete, sensory and fine-grained information, whereas higher levels contain general, conceptual and integrated information [START_REF] Badre | Cognitive control, hierarchy, and the rostro-caudal organization of the frontal lobes[END_REF], [START_REF] Tenenbaum | How to grow a mind: Statistics, structure, and abstraction[END_REF]. It is thus important that a model of the PFC to exploit both views, suggesting to incorporate an attentional mechanism for the flexible and controlled design of hierarchical rules from previously learned concrete rules, as we proposed in the new model sketched here.

Fig. 1 :

 1 Fig. 1: (a) Model Schematics : Figure adapted from [1] (b) Task schematics : Figure adapted from [8]

Fig. 2 :

 2 Fig.2: Performance of the model with 3 layers for the two paradigms (a, b), plotted as an average over 100 runs, only for the runs that reached convergence criteria. The convergence criteria was defined as having a performance greater than 85% in the last 200 trials. (c) Performance for the model with 2 layers on the first learning paradigm.

Fig. 3 :

 3 Fig. 3: Examples of how the model solves different cases of stimuli. The matrix shows the prediction values at different layers (first 3 rows), given the internal representation of the stimulus, and how they are modulated additively (row 4) to give the final Action-Outcome predictions that are used for response selection. a, b show the case when the stimulus is black, in rules 1 and 2 respectively. d, e show the case when the stimulus is Green, Vowel (rule T1) and Red, Upper case (rule T2). c, f show the case for Green, Vowel and Red, Upper case in rule T3

Fig. 4 :

 4 Fig. 4: (a) The modified model with output gating from layer 1. The gating weights in layer 1 (X 1 ) learn over time to gate the context into r 1 . The selected prediction units from layer 1 (p 1 ) are then used to make a decision on which value of the stimulus s is gated into r 0 (the output gate). (b) Prediction weights (W 0 ) for the concrete rules at layer 0. These weights are pre-learned by training the model with rules T1 and T2, independently. (c) Performance of the original model compared to the modified model over a 100 runs, when layer 0 is fixed to the weights in figure (b) and only layer 1 prediction weights (W 1 ) and gating weights (X 1 ) are learned.


Alexandre Duret-Lutz

Etienne Renault
email: renault@lrde.epita.fr

Maximilien Colange

Florian Renkin
email: frenkin@lrde.epita.fr

Alexandre Gbaguidi

Philipp Schlehuber-Caissier
email: philipp@lrde.epita.fr

Thomas Medioni

Antoine Martin
email: amartin@lrde.epita.fr

Jérôme Dubois
email: jdubois@lrde.epita.fr

Clément Gillard

Henrich Lauko

Evaluation Artifact Reusable CAV Evaluation Artifact From Spot 2.0 to Spot 2.10: What's New?

Spot is a C ++ 17 library for LTL and ω-automata manipulation, with command-line utilities, and Python bindings. This paper summarizes its evolution over the past six years, since the release of Spot 2.0, which was the first version to support ω-automata with arbitrary acceptance conditions, and the last version presented at a conference. Since then, Spot has been extended with several features such as acceptance transformations, alternating automata, games, LTL synthesis, and more. We also shed some lights on the data-structure used to store automata.

Availability, Purpose, and Evolution

Spot is a library for LTL and ω-automata manipulation, distributed under a GPLv3 license. Its source code is available from https://spot.lrde.epita. fr/. We provide packages for some Linux distributions like Debian and Fedora, but other packages can also be found for Conda-Forge [START_REF]The conda-forge project: Community-based software distribution built on the conda package format and ecosystem[END_REF] (for Linux & Darwin), Arch Linux, FreeBSD... Spot can be used via three interfaces: a C ++ 17 library, a set of commandline tools that give easy access to many features of the library, and Python bindings, that makes prototyping and interactive work very attractive. Our web site now contains many examples of how to perform some tasks using these three interfaces, and we have a public mailing list for questions.

In our last tool paper [START_REF] Duret-Lutz | Spot 2.0 -a framework for LTL and ω-automata manipulation[END_REF], Spot 2.0 had just converted from being a library for working on Transition-based Generalized Büchi Automata and had become a library supporting ω-automata with arbitrary Emerson-Lei [START_REF] Emerson | Modalities for model checking: Branching time logic strikes back[END_REF][START_REF] Safra | On ω-automata and temporal logic[END_REF] acceptance conditions, as enabled by the development of the HOA format [START_REF] Babiak | The Hanoi Omega-Automata Format[END_REF].

In the HOA format, transitions can carry multiple colors, and acceptance conditions are expressed as a positive Boolean formulas over atoms like Fin(i) or Inf(i) that tell if a color should be seen finitely or infinitely often for a run to be accepting. Table 1 gives some examples.

While Spot 2.0 was able to read automata with arbitrary acceptance conditions, not all of its algorithms were able to support such a generality. For instance Table 1. Acceptance formulas corresponding to classical names.

Büchi

Inf(0) generalized Büchi i Inf(i) Fin-less [START_REF] Bloemen | Model checking with generalized Rabin and Fin-less automata[END_REF] any positive formula of Inf(...) co-Büchi Fin(0) generalized co-Büchi i Fin(i) Rabin i (Fin(2i) ∧ Inf(2i + 1)) generalized Rabin [START_REF] Křetínský | Deterministic automata for the (F,G)-fragment of LTL[END_REF] i (Fin(i)

∧ j∈J i Inf(j)) Streett i (Inf(2i) ∨ Fin(2i + 1)) parity min even Inf(0) ∨ (Fin(1) ∧ (Inf(2) ∨ (Fin(3) ∧ . . .))) parity min odd Fin(0) ∧ (Inf(1) ∨ (Fin(2) ∧ (Inf(3) ∨ . . .))) parity max even (((Inf(0) ∧ Fin(1)) ∨ Inf(2)) ∧ Fin(3)) ∨ . . . parity max odd (((Fin(0) ∨ Inf(1)) ∧ Fin(2)) ∨ Inf(3)) ∧ . . .
testing an automaton for emptiness or finding an accepting word, would only work on automata with "Fin-less" acceptance conditions. For other conditions, Spot 2.0 would rely on a procedure called remove_fin() to convert automata with arbitrary acceptance conditions into "Fin-less" acceptance conditions [START_REF] Bloemen | Model checking with generalized Rabin and Fin-less automata[END_REF]. This was ultimately fixed by developing a generic emptiness check [START_REF] Baier | Generic emptiness check for fun and profit[END_REF]. Additionally the support for arbitrary acceptance conditions has allowed us to implement many useful algorithms; the most recent being the Alternating Cycle Decomposition [START_REF] Casares | Optimal transformations of games and automata using Muller conditions[END_REF][START_REF] Casares | Practical applications of the alternating cycle decomposition[END_REF] a powerful data structure with many applications (conversion to parity acceptance, degeneralization, typeness checks...) 3 .

There have been 56 releases of Spot since version 2.0, but only 10 of these are major releases. Releases are numbered 2.x.y where y is updated for minor upgrades that mostly fix bugs, and x is updated for major release that add new features. (The leading 2 would be incremented in case of a serious redesign of the API.) Table 2 summarizes the highlights of the various releases in chronological order. Not appearing in this list are many micro-optimizations and usability improvements that Spot has accumulated over the years.

Use-cases of Spot, and Related Tools

As it is a library, there are many ways to use Spot. We are mostly aware of such uses via citations 4 . Historical and frequent uses-cases are to use Spot for translating LTL formulas to automata (Winners of the sequential LTL and parallel LTL tracks of RERS'19 challenge [START_REF] Jasper | RERS 2019: Combining synthesis with real-world models[END_REF] both used Spot to translate the properties into automata, many competitors on the Model Checking Contest [START_REF] Kordon | Complete results for the 2021 edition of the Model Checking Contest[END_REF] also use Spot this way), or to use it as a research/development toolbox, since it provides helper tools for generation of random formulas/automata, verification of LTLto-automata translation, simplifications, syntax conversions, etc. Nowadays, the algorithms for ω-automata implemented in Spot are often used as baseline for

2.5

New command-line tool ltlsynt for synthesis of AIGER circuits from LTL specifications. [START_REF] Michaud | Reactive synthesis from LTL specification with Spot[END_REF] Conversions to co-Büchi [START_REF] Boker | Co-Büching them all[END_REF]. Utilities for converting between parity acceptance conditions. Detection of stutter-invariant states. Determinization optimized.

2.6

Compile-time option to support more than 32 colors. Specialized translation for formulas of the type GF(φ) if φ is a guarantee. New translation mode to output automata with unconstrained acceptance condition. Semi-deterministic complementation [START_REF] Blahoudek | Complementing semi-deterministic Büchi automata[END_REF]. Faster detection of obligation properties. Online LTL translator replaced by a new web application (see Figure 4).

2.7

LAR-based paritization in ltlsynt. Generic emptiness check [START_REF] Baier | Generic emptiness check for fun and profit[END_REF]. Detection of liveness properties [START_REF] Alpern | Recognizing safety and liveness[END_REF].

2.8

Accepting run extraction for arbitrary acceptance. Introduction of an "output_aborter" to abort constructions that are too large. Support for SVA's delay syntax, and first_match operator [1]. Minimization of parity acceptance [START_REF] Carton | Computing the Rabin index of a parity automaton[END_REF]. 2.9

Better paritization, partial degeneralization, and acceptance simplifications [START_REF] Renkin | Practical "paritizing" of Emerson-Lei automata[END_REF]. Weak and strong variants of X. Xor product of automata, used while translating formulas to automata with unconstrained acceptance. 2.10 C ++ 17 ltlsynt overhauled [START_REF] Renkin | Improvements to ltlsynt[END_REF]. Support for games and Mealy machines.

Mealy machines simplifications. Multiple encodings from Mealy machine to AIGER. Experimental twacube class for parallel algorithms. Support for transition-based Büchi. Zielonka Trees and Alternating Cycle Decomposition [START_REF] Casares | Optimal transformations of games and automata using Muller conditions[END_REF][START_REF] Casares | Practical applications of the alternating cycle decomposition[END_REF] studying better algorithms [e.g., [START_REF] Löding | New optimizations and heuristics for determinization of büchi automata[END_REF][START_REF] Křetínský | Index appearance record with preorders[END_REF][START_REF] Havlena | Complementing Büchi automata with Ranker[END_REF][START_REF] Doveri | FORQ-based language inclusion formal testing[END_REF], but we also see some new applications built on top of ω-automata algorithms from Spot [e.g., [START_REF] Brotherston | A generic cyclic theorem prover[END_REF][START_REF] Bruyère | Pareto-rational verification[END_REF].

The projects that have the largest intersections of features with Spot seem to be GOAL [START_REF] Tsai | Goal for games, omega-automata, and logics[END_REF] and Owl [START_REF] Kretínský | Owl: A library for ω-words, automata, and LTL[END_REF]. These are two Java-based frameworks that deal with similar objects and provide a range of algorithms. Owl and Spot share a similar and traditional Unix view of the command-line experience, where multiple commands are expected to be chained with pipes, and they both communicate smoothly via the HOA format [START_REF] Babiak | The Hanoi Omega-Automata Format[END_REF]. GOAL is centered on a graphical interface in which the user can edit automata, and apply algorithms listed in menu entries. Using GOAL from the command-line is possible by writing short scripts in a custom language.

As far as interfacing goes, the most important feature of Spot is probably that it exposes its algorithms and data structures in Python. Beside being usable as a glue language between various tools, this allows us (1) to leverage Python's ecosystem and (2) to quickly prototype new algorithms in Python.

Automata Representation

In this section and the next three, we focuses on how the storage of automata evolved to support alternation, games, and Mealy machines.

The main automaton class of Spot is called twa_graph and inherits from the twa class. The letters twa stand for Transition-based ω-Automaton.

The class twa implements an abstract interface that allows on-the-fly exploration of an automaton similar to what had been present in Spot from the start: essentially, one can query the initial state, and query the transitions leaving any known state. In particular, before exploring the state-space of a twa, it is unknown how many states are reachable. Various subclasses of twa are provided in Spot, for instance to represent the state-space of Promela or Divine models [START_REF] Duret-Lutz | Spot 2.0 -a framework for LTL and ω-automata manipulation[END_REF]. Users may create subclasses, for instance to create a Kripke structure on-the-fly. 5The class twa_graph, introduced in Spot 2.0, implements an explicit, graphbased, representation of an automaton, in which states and edges are designated by integers. This makes for a much simpler interface 6 and usually simplifies the data structures used in algorithms (since states and edges can be used as indices in arrays). The data structure is best illustrated by using the show_storage() method of the Python bindings, as shown by Figure 1. A twa_graph is stored as two C ++ vectors: a vector of states, and a vector of edges. For each state, the first vector stores two edge numbers: succ is the first outgoing edge, and succ_tail is the last one. These number are indices into the edge vector, which stores five pieces of information per edge. Four of them are related to the identity of the edge: src, dst, cond, acc are respectively the source, destination, guard, and color sets of the edge. The remaining field, next_succ gives the next outgoing edge, effectively creating a linked list of all edges leaving a given state. There is no edge 0: this value is used as terminator for such lists. Outgoing edges of the same state are not necessarily adjacent in that structure. When a new edge is added to the automaton, it is simply appended to the edge vector, and the succ_tail field of the state is used to update the previous end of the list.

To iterate over successors of state 1 in C ++ or Python, one can ignore the above linked list implementation and write one of the following loops:

for (auto& e: aut->out(1))

// use e.cond, e.acc, e.dst for e in aut.out(1): # use e.cond, e.acc, e.dst

The twa_graph::out methods simply returns a lightweight temporary object which can be iterated upon using iterators that will follow the linked list. Then the object e is effectively a reference to a column of the edge vector. As seen on Figure 1, the automaton additionally stores an initial state (Spot only supports a single initial state), a number of colors (num_sets), an acceptance condition, a list of atomic propositions (Spot only supports alphabets of the form 2 AP ), and 10 fields storing structural properties of the automaton.

These property fields have only three possible values: they default to maybe, but can be set to no or yes by algorithms that work on the automaton. They can also be read and written in the HOA format. For instance if prop_universal is set to yes, it means that automaton does not have any existential choice (a.k.a. non-determinism). Spot's is deterministic() algorithm can return in constant time if prop_universal is known, otherwise it will inspect the automaton and set that property before returning, so that the next call to is deterministic() will be instantaneous. Some algorithms know how to take advantage of any hint they get from those properties: for instance the product() of two automata is optimized to use fewer colors when one of the arguments is known to be weak (i.e., in an SCC all transitions have the same colors).

Note that algorithms that modify an automaton in place have to remember to update those properties. This has caused a couple of bugs over the years.

Introduction of Alternating Automata

Support for alternating ω-automata, as defined in the HOA format, was added to Spot in version 2.3 without introducing a new class. Rather, the twa_graph class was extended to support alternation in such a way that existing algorithms would not require any modification to continue working on automata without universal branching. This was done by reserving the sign bit of the destination state number of each transition to signal universal branching. Figure 2 shows an example of Alternating automaton (top-left) with co-Büchi acceptance. In many works on alternating automata, it is conventional to not represent accepting sinks, and instead have transition without destination. The top-right picture shows that Spot has a rendering option to hide accepting sinks.

The bottom of the figure shows that the automaton has prop_state_acc set, which means that the automaton is meant to be interpreted as using state-based acceptance. Colors are still stored on edges internally, but all edges leaving a state have the same colors. Seeing that the condition is co-Büchi (Fin(0)), the display code automatically switched to the convention of using double-circles for rejecting states.

Destinations with the sign bit set are called universal destination groups and appear as pink in the figure. There are two groups here: ~0 and ~3. The complement of these numbers can be used as indices in the dests vector, that actually store the destination groups. At the given index, one can read the size n of the destination group, followed by the state number of the n destinations.

Algorithms that work on alternating automata need to be able to iterate over all destinations of an edge. The process of checking the sign bit of the destination to decide if its a group, and to iterate on that group is hidden by the univ_dests() method: Note that this code works on non-universal branches as well: if e.dst is unsigned, univ_dests(e) will simply iterate on that unique value.

Spot has two alternation removal procedures. One is an on-the-fly implementation of the Breakpoint construction [START_REF] Miyano | Alternating finite automata on ω-words[END_REF] which transforms an n-state alternating Büchi automaton into a non-alternating Büchi automaton with at most 3 n states. For very weak alternating automata, it is known that a powerset-based procedure can produce a transition-based generalized Büchi automaton with 2 n states [START_REF] Gastin | Fast LTL to Büchi automata translation[END_REF]; in fact that algorithm even works on ordered automata [START_REF] Boker | Alternation removal in Büchi automata[END_REF], i.e., alternating automata where the only rejecting cycles are self-loops. The second alternation removal procedure of Spot is a mix between these two procedures but does not work on the fly: it takes a weak automaton as input, and uses the break-point construction on rejectings SCCs that have more than one state, and uses the powerset construction for other SCCs.

Extending Automata via Named Properties

Spot's automata have a mechanism to attach arbitrary data to automata, called named properties. (This is similar to the notion of attributes in the R language.) An object can be attached to the automaton with: aut->set_named_prop("property-name", new mytype(...)); and later retrieved with: mytype* data = aut->get_named_prop<mytype>("property-name");

Ensuring that mytype is the correct type for the retrieved property is the programmer's responsability.

Spot has grown a list of many such properties over time. 7 For instance automaton-name stores a string that would be displayed as the name of the automaton. The highlight-edges and highlight-states properties can be used to color edges and states. The state-names is a vector of strings that gives a name to each state, etc. While those examples are mostly related to the graphical rendering of the automata, some algorithms store useful byproducts as properties. For instance the product() algorithm will define a product-states named property that store a vector of pairs of the original states.

These named properties are sometimes used to provide additional semantics to the automaton, for instance to obtain a game or a Mealy machine.

Games, Mealy Machines, and LTL Synthesis

The application of Spot to LTL synthesis was introduced in Spot 2.5 in the form of the ltlsynt tool [START_REF] Michaud | Reactive synthesis from LTL specification with Spot[END_REF], but the inner workings of this tool were progressively redesigned and publicly exposed until version 2.10.

An automaton can now be turned into a game by attaching the state-player property to it. 8 Only two-player games are supported, so state-player should be a std::vector<bool>. Currently, Spot has solvers for safety games and for games with parity max odd acceptance, but we plan to at least generalize the latter to any kind of parity condition. Once a game has been solved, it contains two new named properties: state-winner (a std::vector<bool> indexed by state numbers indicating the player winning in each state), and strategy (a std::vector<unsigned> that gives for each state the edge that its owner should follow to win). Figure 3 shows an example of game generated by ltlsynt, and how we can display the winning strategy once the game is solved. The winning strategy can be extracted and converted into a Mealy machine, which is just an automaton that uses the synthesis-output property to specify which atomic propositions belong to the output. Such a Mealy machine can then be encoded into an ANDinverter graph, and saved into the AIGER format [START_REF] Biere | AIGER 1.9 and beyond[END_REF]. Here L0 represents a latch, i.e., one bit of memory, that stores the previous value of a so that the circuit can output b if and only if a is true in the present and in the previous step.

Online Application for LTL Formulas

The Python ecosystem makes it easy to develop web interfaces for convenient access to a subset of features of Spot. For instance Figure 4 shows screenshots of a web application built using a React frontend, and running Spot on the server. It can transform LTL formulas into automata, can display many properties of a formula (membership to the Manna & Pnueli hierarchy [START_REF] Manna | A hierarchy of temporal properties[END_REF], Safety/Liveness classification [START_REF] Alpern | Recognizing safety and liveness[END_REF], Rabin and Streett indices [START_REF] Carton | Computing the Rabin index of a parity automaton[END_REF], stutter-invariance [START_REF] Michaud | Practical stutter-invariance checks for ω-regular languages[END_REF]), or simply compare two formulas using a Venn diagram.

This application has been found to be useful for teaching about LTL and its relation with automata, but is also a helpful research tool. While Spot has been used for many applications, there are two recurrent issues: they are related to the types used for some fields of the edge vector (see Figures 12). By default, the set of colors that labels an edge (the acc field) is stored as a 32-bit bit-vector, the transition label (cond, a formula over 2 AP ), is stored as a BDD identified by a unique 32-bit integer, and the other three fields (src, dst, next_succ) are all 32-bit integers. One edge therefore takes 20 bytes.

While limiting the number of states to 32-bit integers has never been a problem so far, the limit of 32 colors can be hit easily. Spot 2.6 added a compile-time option to enlarge the number of supported colors to any multiple of 32; this evidently has a memory cost (and therefore also a runtime cost) as the acc field will be larger for each edge. However this constraint generally means that all the algorithms we implement try to be "color-efficient", i.e., to not introduce useless colors. For instance while the product of an automaton with x colors and an automaton with y colors is usually an automaton with x + y colors, the product() implementation will output fewer colors in presence of a weak automaton.

The use of BDDs as edge labels causes another type of issues. Spot uses a customized version of the BuDDy library, with additional functions, and several optimizations (more compact BDD nodes for better cache friendliness, most operations have been rewritten to be recursion-free). However BuDDy is inherently not thread safe, because of its global unicity table and caches. This prevents us from doing any kind of parallel processing on automata. A long term plan is to introduce a new class twacube that represent an automaton in which edges are cubes (i.e., conjunctions of literals) represented using two bit-vectors. Such a class was experimentally introduced in Spot 2.10 and is currently used in some parallel emptiness check procedures [START_REF] Renault | Variations on parallel explicit model checking for generalized Büchi automata[END_REF].

Fig. 1 .

 1 Fig. 1. Internal representation of a twa_graph as two vectors.

Fig. 2 .

 2 Fig. 2. Internal representation of alternating automata.

Fig. 3 .

 3 Fig. 3. (top) Solving a game to display the strategy. States with green borders are winning for player 1, who wants to satisfy the acceptance condition, by following the green arrows. States with red color are winning for player 0, who wants to fail the acceptance condition, by following the red arrows. (bottom) Conversion of the winning strategy to a Mealy machine and then an AIGER circuit.

Fig. 4 .

 4 Fig. 4. A web application, built on top of Spot. https://spot.lrde.epita.fr/app/

Table 2 .

 2 Milestones in the history of Spot. ++ 14 New command-line tools: autcross to check and compare automata transformations, genaut to generate families of automata. Dualiza-

	0.x C ++ 03 Prehistory of the project. [20]
	0.9	Support for some PSL operators.
	1.0	Command-line tools, mostly focused on LTL/PSL input [19]. In-
		cludes ltlcross, a clone of LBTT [42]. Python bindings.
	1.1	Automatic detection of stutter-invariant formulas. [36]
	1.2	SAT-based minimization [3, 4]. ltlcross and the new dstar2tgba
		can read Rabin and Streett automata produced by ltl2dstar [27].
	2.0 C ++ 11 Rewrite of the LTL formulas representation. Rewrite of the au-
		tomaton class to allow arbitrary acceptance. Support for the HOA
		format. More command-line tools, now that automata can be ex-
		changed with other tools. [21] New determinization procedure.
	2.1	Conversion to generalized Streett or Rabin. Small usability im-
		provements all around (like better support for CSV files).
	2.2	LTLf→LTL conversion [24]. Faster simulation-based reduction of
		deterministic automata.
	2.3	Initial support for alternating automata and alternation removal.
		400% faster emptiness check. Incremental SAT-based minimization.
		Classification in the temporal hierarchy of Manna & Pnueli [34].
	2.4 C

tion of automata. Conversion from Rabin to Büchi

[START_REF] Krishnan | Deterministic ω-automata vis-a-vis deterministic Büchi automata[END_REF]

updated to support transition-based input. Relabeling of LTL formulas with large Boolean subformulas to speedup their translation.

https://spot.lrde.epita.fr/ipynb/zlktree.html

Our previous tool paper[START_REF] Duret-Lutz | Spot 2.0 -a framework for LTL and ω-automata manipulation[END_REF] has over 250 citations according to Google scholar

As demonstrated by https://spot.lrde.epita.fr/tut51.html

Contrast on-the-fly and explicit APIs at https://spot.lrde.epita.fr/tut50.html.

https://spot.lrde.epita.fr/concepts.html#named-properties

https://spot.lrde.epita.fr/tut40.html illustrates how a game can be used to decide if a state simulates another one.

https://zenodo.org/record/6521395.


Kostadin Dabov

Alessandro Foi

Vladimir Katkovnik

Karen Egiazarian

BM3D Image Denoising with Shape-Adaptive Principal Component Analysis

We propose an image denoising method that exploits nonlocal image modeling, principal component analysis (PCA), and local shape-adaptive anisotropic estimation. The nonlocal modeling is exploited by grouping similar image patches in 3-D groups. The denoising is performed by shrinkage of the spectrum of a 3-D transform applied on such groups. The effectiveness of the shrinkage depends on the ability of the transform to sparsely represent the true-image data, thus separating it from the noise. We propose to improve the sparsity in two aspects. First, we employ image patches (neighborhoods) which can have data-adaptive shape. Second, we propose PCA on these adaptive-shape neighborhoods as part of the employed 3-D transform. The PCA bases are obtained by eigenvalue decomposition of empirical second-moment matrices that are estimated from groups of similar adaptive-shape neighborhoods. We show that the proposed method is competitive and outperforms some of the current best denoising methods, especially in preserving image details and introducing very few artifacts.

I. INTRODUCTION

Image denoising is a vivid research subject in signal processing because of its fundamental role in many applications. Some of the most recent and successful advances are based on: Gaussian scale mixtures (GSM) modeling in overcomplete multiscale transform domain [START_REF] Guerrero-Colón | Image denoising using mixtures of Gaussian scale mixtures[END_REF], [START_REF] Portilla | Image denoising using a scale mixture of Gaussians in the wavelet domain[END_REF], [START_REF] Guerrero-Colon | Two-level adaptive denoising using Gaussian scale mixtures in overcomplete oriented pyramids[END_REF]; learned dictionaries of atoms to Þlter small square neighborhoods [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF]; steering kernel regression [START_REF] Takeda | Kernel regression for image processing and reconstruction[END_REF] (also combined with learned dictionaries [START_REF] Chatterjee | Clustering-based denoising with locally learned dictionaries[END_REF]); shape-adaptive DCT (SA-DCT) on neighborhoods whose shapes are adaptive to the image structures [START_REF] Foi | Pointwise Shape-Adaptive DCT for high-quality denoising and deblocking of grayscale and color images[END_REF]; nonlocal Þltering based on the assumption that there exist mutually similar blocks in natural images [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], [START_REF] Kervrann | Optimal spatial adaptation for patchbased image denoising[END_REF], [3], [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF]. Among these different strategies, the nonlocal Þltering, which originates from the work of Buades et al. [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], is the one that demonstrates the biggest potential. In particular, the transform-based BM3D Þlter [3] can be considered stateof-the-art in image denoising [START_REF] Lansel | DenoiseLab[END_REF].

The BM3D Þlter exploits a speciÞc nonlocal image modeling [START_REF]Spatially adaptive support as a leading model-selection tool for image Þltering[END_REF] through a procedure termed grouping and collaborative Þltering. Grouping Þnds mutually similar 2-D image blocks and stacks them together in 3-D arrays. Collaborative Þltering produces individual estimates of all grouped blocks by Þltering them jointly, through transform-domain shrinkage of the 3-D arrays (groups). In doing so, BM3D relies both on nonlocal and local characteristics of natural images, namely the abundance of mutually similar patches and that the image data is locally highly correlated. If these characteristics are veriÞed, the group enjoys correlation in all three dimensions and a sparse representation of the true signal is obtained by applying a decorrelating 3-D transform on the group. The effectiveness of the subsequent shrinkage depends on the sparsity of the true signal; i.e. the true signal can be better separated from the noise when its energy is compactly represented in the 3-D transform domain. We have shown [3] that even if square image patches and a Þxed 3-D transform are used, the denoising performance is very high and the obtained MSE results are still beyond the capabilities of most of the more recent and advanced algorithms. However, square image blocks containing Þne image details, singularities, or sharp and curved edges are examples where a non-adaptive transform is not able to deliver a sparse representation. Thus, for these blocks, the BM3D Þlter may introduce certain artifacts and the denoising is not very effective. Unfortunately, these are often the very parts of the image where the visual attention is mainly focused.

In order to further increase the sparsity of the true signal in the 3-D spectra, in [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF] we proposed a generalization of the BM3D Þlter, which uses grouping of mutually similar adaptive-shape neighborhoods. The employed 3-D transform there is a separable composition of the (2-D) SA-DCT and a 1-D orthonormal transform. This transform is applied on 3-D groups that are generalized cylinders with adaptiveshape cross sections (as opposed to square prisms in BM3D). The adaptive-shape neighborhoods enable local adaptivity to image features so that the true signal in such a neighborhood is mostly homogeneous. Thus, the spatial correlation improves the sparsity as compared with the BM3D. However, even though the neighborhoods have adaptive shapes, the SA-DCT basis are Þxed for any given shape; i.e. the basis elements do not adapt to the signal within the grouped neighborhoods.

In this paper, to enable adaptivity of the applied shapeadaptive transform basis to the input data, we propose principal component analysis (PCA) as part of the 3-D transform used for collaborative Þltering. For a 3-D group of adaptiveshape image patches, we obtain a PCA basis by eigenvalue decomposition of an empirical second-moment matrix computed from these patches. As principal components (PC), we select only the eigenvectors whose corresponding eigenvalues are greater than a threshold that is proportional to noise variance. Hence, the overall 3-D transform is a separable composition of the PCA (applied on each image patch) and a Þxed orthogonal 1-D transform in the third dimension.

In the sequel we present the developed denoising method and show that it is competitive and outperforms some of the current best denoising methods, particularly in preserving image details and producing very few artifacts.

II. BM3D-SAPCA ALGORITHM

A. Algorithm outline

Following is an outline of the proposed algorithm, which we denominate BM3D-SAPCA, and which is illustrated in Figure 1. The input noisy image is assumed to be corrupted by an additive white Gaussian noise with variance σ 2 and zero mean.

• The input image is processed in raster scan where at each processed pixel the following operations are performed: 1) Obtain adaptive-shape neighborhood centered at the current pixel using the 8-directional LPA-ICI exactly as in [START_REF] Foi | Pointwise Shape-Adaptive DCT for high-quality denoising and deblocking of grayscale and color images[END_REF], [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF]. The neighborhood is enclosed within a Þxed-size and non-adaptive square block, which we term reference block. We denote the number of pixels in the neighborhood by N el . 2) Find blocks that are similar to the reference one using block-matching and extract an adaptive-shape neighborhood from each of these matched blocks using the shape obtained in Step 1. The number of matched blocks is denoted by N gr . 3) Determine the transform to be applied on the adaptiveshape neighborhoods. We have two cases, depending on whether N el ≥ τ , we consider that we have found a suf-Þcient number of mutually similar neighborhoods to reliably estimate a second-moment matrix. The eigenvectors of this matrix constitute the shapeadaptive PCA basis. Subsequently, we retain only those eigenvectors whose corresponding eigenvalues are greater than a predeÞned threshold, thus obtaining a trimmed shape-adaptive PCA transform. b) If N gr N el < τ, we deem there are not enough similar neighborhoods to use as training data and we resort to the Þxed (i.e. non data-adaptive) SA-DCT, exactly as in [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF]. 4) Form a 3-D array (called group) by stacking together the min (N gr , N 2 ) adaptive-shape neighborhoods with highest similarity to the reference one, where N 2 is a Þxed parameter that restricts the number of Þltered neighborhoods.

B. Trimmed PCA

Since the main contribution of the proposed method is the application of the shape-and data-adaptive PCA transform on groups of adaptive-shape neighborhoods, we explain in detail what is done in Step 3a, while we refer the reader to our previous works [3], [START_REF] Foi | Pointwise Shape-Adaptive DCT for high-quality denoising and deblocking of grayscale and color images[END_REF], [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF] for details on the other steps of the algorithm. The input for Step 3a is a group of N gr adaptive-shape neighborhoods that are found to be mutually similar. We represent each of these 2-D neighborhoods as a 1-D column vector -→ v i of length N el , i = 1, . . . , N gr . An N el × N el sample second-moment matrix is then computed by matrix multiplication,

C = £ -→ v 1 -→ v 2 . . . -→ v Ngr ¤ £ -→ v 1 -→ v 2 . . . -→ v Ngr ¤ T , (1)
and subsequently its eigenvalue decomposition yields

U T CU = S = diag ³ s 1 , s 2 , . . . , s N el
´,

where U is orthonormal matrix and S is a diagonal matrix containing eigenvalues ordered by magnitude,

s 1 > s 2 > • • • > s N el .
Finally, the PCs used for the decomposition of the adaptive-shape neighborhoods are the Þrst N trim columns of U , where N trim is the number of eigenvalues greater than λσ 2 , λ being a Þxed threshold. An illustration of trimmed PCs is given in Figure 2.

C. Iterative reÞnement

Similarly to [3], [START_REF] Foi | Pointwise Shape-Adaptive DCT for high-quality denoising and deblocking of grayscale and color images[END_REF], [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF], the above algorithm can be applied in more than one iteration. In this work, we propose a threeiteration approach. In the Þrst iteration, the shrinkage is performed by hard-thresholding and the search for similar blocks is performed in the noisy image, since this is the only available input. In the following two iterations, we utilize the estimate image from each previous iteration in the following manner:

• the search for similar blocks is done in the estimate image, • the sample second-moment matrix ( 1) is computed from neighborhoods extracted from the estimate image, • for the third iteration, the shrinkage is performed by empirical Wiener Þltering.

The improvement contributed by the second and by the third iteration can be justiÞed as follows. Because noise has already been attenuated in the estimate images, both the blockmatching and the estimation of the second moments are more accurate when these operations are carried out on an estimate image. It results in sparser 3-D group spectra, as both the mutual similarity within each group and decorrelation due to PCA are enhanced. In addition, the empirical Wiener Þltering is more effective than hard-thresholding when the estimate image from the second iteration is used for providing a reliable estimate of the power spectrum of the 3-D groups.

III. RESULTS

We present results obtained with the proposed threeiteration BM3D-SAPCA. We use different values for τ and λ in each iteration: τ = 1.3, λ = 49 in the Þrst iteration, τ = 1, λ = 13 in the second iteration, and τ = 0.7, λ = 13 in the third iteration. The complexity of the algorithm is linear with respect to the number of pixels in the input image and the computation time of our Matlab-only implementation (M-Þle) takes approximately 4 minutes on a 2.0-GHz Pentium machine for a 256×256 image.

The PSNR and the mean structural similarity index map (MSSIM) [START_REF] Wang | Image quality assessment: From error measurement to structural similarity[END_REF] results of the proposed method are provided in Table I. In Figure 3 we compare denoised images of the proposed method and the methods that it extends: BM3D [3], P.SA-DCT [START_REF] Foi | Pointwise Shape-Adaptive DCT for high-quality denoising and deblocking of grayscale and color images[END_REF], and SA-BM3D [START_REF]A nonlocal and shape-adaptive transform-domain collaborative Þltering[END_REF]. Relatively high noise standard deviations (σ = 35 and σ = 25) were used in order to emphasize the differences in the results by each method. From the Þgure, we observe that the proposed method effectively reconstructs Þne details and at the same time introduces less artifacts than the other methods. This observation is also supported by the improvement in terms of MSSIM and PSNR over the other methods.

IV. DISCUSSION AND CONCLUSIONS

Regardless of the shape of the adaptive-shape neighborhood obtained in Step 2 of our algorithm, we use block-matching of square blocks to Þnd similar neighborhoods, just as it is done in the original BM3D algorithm [3]. There arises the question why the matching is not done between adaptiveshape neighborhoods. In the presence of noise, the employed distance measure (/ 2 -norm of the difference between two neighborhoods) used for the matching can be reliably computed only if the number of elements in the neighborhood is greater than a number that depends on the signal-tonoise ratio (SNR) in these blocks (an illustration of such "breakdown point" can be seen in [3]). Thus, considering that a shape-adaptive neighborhood may consist only of a single pixel and that the SNR can be relatively low, we conclude that the matching cannot be done among the adaptive-shape neighborhoods with sufÞcient reliability.

It is worth discussing the condition for using the PCA instead of the Þxed SA-DCT, i.e.

Ngr N el ≥ τ . Let us remark that the effectiveness of the PCA crucially depends on the sample second-moment matrix S (1). The ideal case would be to compute the second moments from the noise-free image (i.e., from an oracle), but in reality we can only estimate them either from the noisy data (as in the Þrst iteration of the algorithm) or from otherwise distorted data (for the second and third iterations, the matrix is computed from the image estimate produced by the Þrst and second iteration, respectively). A reasonable assumption is that greater N gr results in better estimation of the second-moment matrix. When N gr is small (say N gr < τN el ), the second moments cannot be reliably estimated due to limited training data and we resort to the Þxed SA-DCT transform. We recall that in the three iterations we use τ = 1.3, 1, 0.7, respectively. Note that already in the case N gr < N el (when τ < 1), we have N el -N gr null eigenvalues whose corresponding eigenvectors do not convey meaningful information. However, these eigenvectors will be trimmed since we basically keep only those eigenvectors corresponding to the larger eigenvalues. In fact, this trimming can be considered as part of the shrinkage as it is equivalent to unconditional truncation to zero of the transform coefÞcients that would have corresponded to the discarded eigenvectors. We note that the PC trimming approach, though a standard procedure in the practical application of the PCA (e.g., Section 2.8.5. of [START_REF] Jackson | A User's Guide to Principal Components[END_REF], Chapter 6 of [START_REF] Jolliffe | Principal Component Analysis[END_REF]), is quite coarse and better ways could be devised to incorporate the eigenvalue magnitudes in the shrinkage itself.

Let us brießy compare our method with the K-SVD [6] and the local PCA denoising [START_REF] Muresan | Adaptive principal components and image denoising[END_REF], both of which employ data-adaptive transform bases. The K-SVD performs training of a global (overcomplete, in general) dictionary of basis elements on small square patches; the training can be done on a set of noise-free images or directly on the noisy image. The efÞcacy of the subsequent denoising (performed on noisy image patches) depends on the ability of the dictionary elements to sparsely represent true-image data and thus separate it from the noise. The local PCA denoising [START_REF] Muresan | Adaptive principal components and image denoising[END_REF] exploits PCA on square image blocks, where the covariance matrix used by the PCA is estimated from all blocks in a given neighborhood. The proposed approach exploits adaptive-shape neighborhoods, which allows for further adaptation to image details and it estimates the second-moment matrix for the PCA using similar adaptive-shape neighborhoods as training data -and not just any local neighborhoods. Furthermore, the sparsity of the true data is further increased by applying a transform along the third dimension of the grouped adaptiveshape neighborhoods.

The experimental results shown in Section III are very promising and demonstrate that by employing shape-adaptive PCA we can further improve the state-of-the-art denoising performance of the BM3D algorithm. Future work shall address novel shrinkage criteria, which are adaptive with respect to the utilized transforms, and the use of adaptive transforms for the third-dimension of the group.

Fig. 1 .

 1 Fig. 1. Flowchart of the proposed BM3D-SAPCA image denoising method. Operations surrounded by dashed lines are repeated for each processed coordinate of the input image.

NgrN

  el is larger or smaller than a Þxed threshold τ . a) If N gr

5 )

 5 Apply the transform obtained in Step 3 on each of the grouped adaptive-shape neighborhoods. Subsequently, apply a 1-D orthogonal transform (e.g., Haar wavelet decomposition) along the third dimension of the 3-D group. 6) Perform shrinkage (hard-thresholding or empirical Wiener Þltering) on the 3-D spectrum. 7) Invert the 3-D transform from Step 5 to obtain estimatesfor all of the grouped adaptive-shape neighborhoods. 8) Return the obtained estimates to their original locations using weighted averaging in case of overlapping.

Fig. 2 .

 2 Fig. 2. Illustration of the PCs (shown on the right side) after trimming for four particular adaptive-shape neighborhoods. The green overlay is used to show the found similar neighborhoods used to form a 3-D group. The PCs are listed in decreasing magnitude of their corresponding eigenvalues. One can observe that the Þrst few PCs have the strongest similarity with the noise-free signal in the neighborhood.

TABLE I PSNR

 I (DB) AND MSSIM RESULTS OF THE PROPOSED BM3D-SAPCA IMAGE DENOISING ALGORITHM. (THE MSSIM RESULTS ARE IN THE LOWER ROW OF EACH TABLE CELL.)

		C.man	House	Peppers Montage	Lena	Barbara	Boats	Man	Couple	Hill
	σ/ PSNR	256 2	256 2	256 2	256 2	512 2	512 2	512 2	512 2	512 2	512 2
	5/ 34.16	38.53	39.99	38.30	41.40	38.82	38.34	37.47	38.03	37.63	37.30
		0.9622 0.9589	0.9563	0.9818	0.9454	0.9655	0.9434 0.9565	0.9529	0.9455
	15/ 24.61	32.36	35.15	32.94	35.72	34.42	33.30	32.29	32.20	32.24	32.05
		0.9089 0.8987	0.9063	0.9555	0.8976	0.9253	0.8568 0.8740	0.8784	0.8455
	25/ 20.18	29.81	32.95	30.43	32.96	32.22	30.99	30.03	29.81	29.82	29.96
		0.8635 0.8602	0.8685	0.9291	0.8643	0.8938	0.8037 0.8111	0.8214	0.7788
	35/ 17.25	28.17	31.37	28.74	30.88	30.72	29.35	28.51	28.29	28.23	28.62
		0.8269 0.8374	0.8357	0.9030	0.8367	0.8605	0.7613 0.7633	0.7730	0.7299

ACKNOWLEDGMENT This work was supported by the Academy of Finland (project no. 213462, Finnish Programme for Centres of Excellence in Research 2006-2011, project no. 118312, Finland Distinguished Professor Programme 2007-2010, and project no. 129118, Postdoctoral Researcher's Project 2009-2011) and by Tampere Graduate School in Information Science and Engineering (TISE).


Maxime Raynal

Marc-Olivier Buob

Georges Quénot

A novel pattern-based edit distance for automatic log parsing: Implementation and reproducibility notes

Keywords: Edit distance, log clustering, dynamic programming, reproducible research

This paper presents a detailed and reproducible description of the algorithms and experiments published in "A novel pattern-based edit distance for automatic log parsing". We provide a detailed explanation of the algorithm's implementation, methodology, and experimental setup. We also provide a more complete set of our experiments and results, with a discussion on the metrics used and the influence of main parameters.

Introduction

Unstructured data is ubiquitous, and its lack of structure makes it difficult to analyze. As a sequel, it often ends up being unused [START_REF] Terrizzano | Data wrangling: The challenging yourney from the wild to the lake[END_REF]. In practice, processing unstructured data forces to develop dedicated parsers to convert it to a more convenient and structured format. This problem arises in network management, especially when analyzing system logs 3 or system command outputs. Unfortunately, developing parsers is often tedious, time consuming and error prone.

To automate log parsing, it is required to better understand the structure of the file that must be processed. In the literature, grouping the lines of a log having the same underlying structure and semantics is often referred to as the log clustering (and sometimes, log parsing) problem. To solve this problem, we propose in [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF] a novel pattern-based distance and a clustering algorithm built on top of it. As a result, our clustering algorithm partitions input log lines so that each group of lines conforms to a same underlying structure (template). It worth noting that the templates are not known a priori and are inferred during the log clustering step.

This companion paper details how to reproduce our experiments. Section 2 explains some of our implementation choices. Section 3 describes how to install, setup and run our module and provides a minimal example to use our algorithm. Section 4 recalls the main steps of our algorithm and details how to tune each hyper-parameter. Section 5 presents how we compared though experiments our proposal against two state of the art solutions and discusses the influence of each hyper parameter.

Implementation considerations

The pattern clustering code architecture involves C++ and Python 3 code. The core algorithm is implemented in C++, while the Python wrapping eases its usage. Implementing the core algorithm in C++ improves the performance of the pattern clustering by a factor of 100 and hence allows to process larger log files. The Python wrapping is realized thanks to libpython and the Boost.python libraries [START_REF]Boost C++ library[END_REF] 4

We could have restricted to libpython, but we decided to also use the Boost library for two reasons. First, Boost.python allows to keep the C++ core independent from the implementation details imposed by libpython. Second, wrapping C++ objects usable from the python interpreter imposes to build the appropriate libpython objects; this task is significantly eased by using the Boost.python library.

In our case, the pattern distance and pattern clustering primitives take in parameter pattern automata and vectors [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF]. All these variables are represented C++-side by using vectors. As vectors are not handy to craft automata, we require an intermediate automaton-like class. We could have used Boost.graph, but for sake of simplicity, we kept the graph aspects in the Python module.

To do so, we decided to rely on the pybgl Python module [10] for two reasons. First, pybgl provides an automaton class that can easily extended to implement pattern automata. Second, it provides all the primitives required to build an automaton from an arbitrary regular expression. Once the pattern automata are built, the Python/C++ binding allows to transparently convert them to C++ vectors (as well as Python lists), and conversely, to transform C++ results (vectors) to Python lists.

Installation steps

The installation steps are described in the wiki of the pattern clustering

repository 5 [9].
They involve the installation of the libboost-dev and libpython3-dev libraries, which prevented us from allowing a simple installation though PIP. This would require to compile a version for every target operating system and Python version. Unfortunately, doing so is not straightforward, even using projects like ManyLinux [START_REF]ManyLinux GitHub repository[END_REF], and that is why we decided to provide only a source-based installation.

Once installed, the end-user can run the following minimal example:

1 from pattern_clustering import pattern_clustering Listing 1.1: Minimal example using the pattern clustering function.

To obtain more user-friendly results, we refer the user to the Jupyter notebooks provided in the pattern clustering repository.

Pattern clustering usage

This section presents the parameters of our module and more advanced usages than the one provided in Section 3. It also discusses how to tune each hyperparameter if the default setting is not satisfactory.

As explained in [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF], our pattern clustering primitive takes the following parameters:

lines: an iterable object (e.g., a list) of strings corresponding to each input log line. As the pattern clustering algorithm is greedy, one could pass an iterator allowing to process an input log file in a streaming fashion. map name dfa: a dictionary mapping pattern names with the corresponding deterministic finite automaton (DFA). In [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF], this corresponds to the pattern collection denoted by P. We detail this parameter in Section 4.1. densities: the density of each pattern is a value between 0 and 1 reflecting how strict is a pattern. In [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF], this corresponds to results returned by the density function ρ. The vector of densities offers the opportunity to use alternative density functions. threshold: this value, between 0 and 1, indicates how close must be the elements involved in a cluster from the cluster's representative. In [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF], this corresponds to D. Small values tend to increase the number of output clusters.

use async: a Boolean indicating whether the pattern clustering computations must be parallelized. make mg: the strategy used to build pattern automata from string according to P. The end-user should keep the default value to conform to our reproduce the pattern automata simplifications and experiments presented in [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF].

The value returned by the pattern clustering primitive is detailed in Section 4.2. Section 4.3 discusses two manners to perform the clustering.

Pattern collection

In our implementation, each pattern is identified by a string. Some patterns are predefined in our module and one can get the whole list of supported patterns by running the following snippet:

1 from pattern_clustering import get_pattern_names 2 print ( get_pattern_names () )

Listing 1.2: Predefined patterns.

One may tune the default pattern collection by discarding some keys, modifying some automata, or inject custom patterns. The example below shows how to inject a custom pattern named letters.

1 from pattern_clustering import * 2 from pybgl . regexp import compile_dfa In the details, the compile dfa processes the input regular expression using the Shunting Yard algorithm [START_REF] Dijkstra | Algol 60 translation: An algol 60 translator for the x1 and making a translator for algol 60[END_REF]. By using the Thompson transformation [START_REF] Thompson | Programming techniques: Regular expression search algorithm[END_REF], it progressively builds a non-deterministic finite automaton (NFA). Finally, the NFA is transformed to its corresponding minimal DFA using the Moore algorithm [START_REF] Moore | Gedanken-experiments on sequential machines[END_REF].

Returned value

Once the clustering is computed, each input line is remapped with the appropriate cluster. The pattern clustering returns a list where each element represents a cluster. The i th element of this list gathers the line number of the lines belonging to the i th cluster.

Dropping duplicated pattern automata

Our module allows to drop duplicated pattern automata. This feature is relevant if the end-user considers that every line conforming to the same pattern automaton must always fall in the same cluster. Dropping duplicated pattern automata limits the number of elements to cluster and thus accelerates the processing. However, we did not use this feature in our experiments. Indeed, we observed that it could affect the quality of the clustering, as in some situations, two lines conforming to the same pattern automaton should fall in distinct clusters.

Experimental setup

In [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF], we compare the pattern clustering (PC) against two state of the art algorithms, namely Drain [START_REF] He | Drain: An online log parsing approach with fixed depth tree[END_REF] and LogMine [START_REF] Hamooni | Logmine: Fast pattern recognition for log analytics[END_REF]. Our experimental setup is quite similar to the one described in [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF]. This section presents the main differences.

Drain and LogMine integration

The standard implementations of Drain [START_REF]Drain 3 original repository[END_REF] and LogMine [7] are not verbose enough, as they do not map input lines with the corresponding cluster. That is why we have forked the standard implementation and adapted the outputs returned by LogMine and Drain [START_REF]Drain 3 forked repository[END_REF][START_REF]Logmine forked repository[END_REF]. Our modifications are minor, they do not affect the results returned by these algorithms and only induce negligible running time overhead.

Loghub dataset

We perform our experiments on the Loghub dataset, which involves 16 log files. The Loghub repository [START_REF]Loghub: A large collection of system log datasets for AI-powered log analytics[END_REF] provides a small excerpt of each log file, whereas the Zenodo repository [START_REF]Zenodo repository containing the full Loghub logs[END_REF] contains the complete logs. A detailed description of each log (size, number of messages, labeling, etc.),is available in [START_REF] He | Loghub: A large collection of system log datasets towards automated log analytics[END_REF].

Ground truth

The Loghub repository [START_REF]Loghub: A large collection of system log datasets for AI-powered log analytics[END_REF] provides for each log file the corresponding ground truth. A ground truth maps templates (i.e., a string involving some wildcards denoted by <*>) with the corresponding lines of log.

It's worth noting that each ground truth has been manually obtained. During our experiments, we have observed several inconsistencies. In particular, we have found some clusters that have no reason to be split. For example, the original Android ground truth distinguishes the three following templates:

-animateCollapsePanels:flags=<*>, force=false, delayed=false, mExpandedVisible=false -animateCollapsePanels:flags=<*>, force=false, delayed=false, mExpandedVisible=true -animateCollapsePanels:flags=<*>, force=true, delayed=true, mExpandedVisible=true ... while it would be more natural to merge them in a single template:

-animateCollapsePanels:flags=<*>, force=<*>, delayed=<*>, mExpandedVisible=<*>

We have checked each ground truth and fixed all the inconsistencies we have found. The original and the fixed versions of the ground truths are made available in [START_REF]Ground truth templates[END_REF] and may be easily compared using any diff-like utility.

Experimental parameters

The three considered clustering algorithms mainly require two parameters, namely the pattern collection and the clustering threshold.

For each dataset, our experiments consider two pattern collections:

-Minimal collection. Our initial motivation is to design a generic log clustering tool, and thus this collection only includes universal patterns (i.e., patterns like dates, times, network addresses, numerical values). -Specific collections. In [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF], the authors tailor dataset-dependant to see how good each algorithm with a high prior knowledge could be. As a sequel, the resulting collection is highly dependent on the input dataset and requires significant end-user intervention.

To get a full benchmark, our experiments compare for each dataset the results obtained with the dedicated specific pattern collection and the minimal collection.

As done in [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF], the threshold is calibrated by running the experiments with several values. We keep the best results obtained w.r.t the tested thresholds.

To make our experiments easily reproducible, all the simulation parameters are made available in our repository. We also provide notebooks allowing to run our experiment pipeline.

Accuracy

The accuracy of each clustering algorithm is evaluated by computing two performance metrics (namely, the parsing accuracy and the adjusted Rand index). Both require a ground truth -we used the fixed on see 5.3.

The parsing accuracy has been introduced in [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF]. More formally, given two partitions C 1 , C 2 of a set E, the pattern accuracy is defined by:

P A(C 1 , C 2 ) = 1 |E| C∈C1∩C2 |C|
By definition, this metric only rewards clusters that exactly matches those listed in the ground truth. As a sequel, if a cluster is slightly different in the inference and in the ground truth, it is not rewarded; and the bigger the cluster, the bigger the penalty. This means that algorithms returning clustering with small errors can have a very low parsing accuracy. Conversely, slight modifications on the ground truth may drastically change the parsing accuracy, especially if they impact large clusters. The adjusted Rand index [START_REF] Hubert | Comparing partitions[END_REF] is designed to be less sensitive to small variations and hence alleviate all the limitations inherent to the parsing accuracy. This value is an adjusted-for-chance version of the Rand index and is based on the number of correct and incorrect pairwise assignments.

Conclusion

This companion paper shows how to reproduce the experiments presented in [START_REF] Raynal | A novel pattern-based edit distance for automatic log parsing[END_REF] and highlights several contributions of this work. First, we have presented several code optimizations (core algorithm written in C++, parallelization) that allow to run our algorithm on real logs of average size. Second, we have packaged our code so that it is documented, tested, and easy to install. Third, we have provided all the technical material needed to reproduce our experiments which allows researchers to easily compare their proposal against LogMine, Drain and the pattern clustering algorithm. Fourth, this work has been the opportunity to enhance the ground truths provided by the Loghub dataset. For all these reasons, we hope that our contributions will be reused in the future works dealing with log clustering and automatic parsing.

2 3 6 7

 26 FILENAME = " / var / log / Xorg .0. log " # Or any arbitrary log file 4 with open ( FILENAME ) as f : 5 LINES = [ line . strip () for line in f . readlines () ] print ( pattern_clustering ( LINES ) )

3 4

 3 MAP_NAME_DFA = make_map_name_dfa () 5 MAP_NAME_DFA [ " letters " ] = compile_dfa ( " [a -zA -Z ]+ " ) 6 print ( pattern_clustering ( LINES , map_name_dfa = MAP_NAME_DFA ) ) Listing 1.3: Custom pattern collection.

Logs are text files, where each line usually corresponds to a timestamped message.

This means that once compiled, the pattern clustering module works for the python version corresponding to the libpython and Boost.python libraries.

https://github.com/nokia/pattern-clustering/wiki/Installation