Wasif Razzaq

Christophe Serra
email: ca.serra@unistra.fr

Delphine Chan-Seng
email: delphine.chan-seng@ics-cnrs.unistra.fr

Production of Janus/Hecate microfibers by microfluidic photopolymerization and evaluation of their potential in dyes removal

The microfluidic production of Janus/Hecate polymer microfibers with well-defined interfaces from miscible phases is reported. The process offers tunability of the width and composition of each part of the fibers by controlling in a single step the flow rate and nature of the monomers. The enhanced performances of the fibers are outlined for the simultaneous removal of dyes of opposite charges using amphoteric Janus fibers.

 Their main limitations are (i) the access to diameters in the submicrometer range only, (ii) the incompatibility with biological systems due to high voltage, temperature, and use of solvent, and (iii) the restriction to pre-existing polymers in the presence of a suitable solvent.

Microfluidic spinning is an emerging and promising technique for the continuous fabrication of microfibers. It proceeds by establishing the co-flow between a core phase (Φcore) that will form the fiber material and a sheath phase (Φsheath) which hydrodynamically "spins" the fiber thanks to a microfluidic device. This technique offers advantages over conventional ones such as complete control on the diameter/volume ratio by tuning the flow rates of both core and sheath fluids, 16 multiple solidification methods, 3 easy hydrogel formation, 17 micro-to submicron size range, 18 and compatibility with biological systems. 19 Fibers produced by microfluidic spinning relying on immiscible fluids provide access to jetting conditions only in a very narrow range of flow rates to obtain fibers and thus limits the use of multiple core phases due to the existence of very different interfacial tensions. [20][21][22] Reports using purely miscible core and sheath phases describe the preparation of only single and Janus fibers based on alginate, [23][24][25][26] and also hollow 27 and mosaicked 24 fibers from poly(ethylene glycol) diacrylate until now. However, the preparation of Janus fibers, fibers with a side-by-side arrangement joined at the interface with two parts of different composition offering the possibility to develop materials with unique properties (e.g. differentiated encapsulation abilities and compartmentalized properties), from monomers using miscible fluids has not yet been reported even though this strategy would significantly widen the type of Janus fibers (chemical nature of the different phases, one-step production of hydrogel, etc.) that could be obtained.

Herein we report the use of a side-by-side capillaries-based microfluidic device operating with different miscible phases (core monomer phases) co-flowing with the continuous (sheath) phase to produce Janus and Hecate microfibers. Two photopolymerizable monomer systems were used as core phase 1 (Φcore1) and core phase 2 (Φcore2). Φcore1 was composed of tri(propylene glycol) diacrylate (TPGDA, 80 %v), ethanol (20 %v), Irgacure 369 (3 %w/v) as photoinitiator, while Φcore2 was composed of NOA89 (photocurable acrylate-terminated prepolymer) (80 %v) and ethanol (20 %v). Poly(ethylene glycol) with a molecular weight of 300 g/mol (PEG300) was used as the sheath phase. The core phases were injected at specific flow rates through capillary 1 and capillary 2 arranged side-by-side using syringes pumps (Fig. 1). Φcore1 and Φcore2 exited at the tip of their respective capillary and got in contact to each other spontaneously forming two parallel streams of monomers due to shear imposed by the sheath fluid flow and their laminar flows (ESI, Fig. S1). A second T-junction afforded the introduction of Φsheath using another syringe pump. Exiting this T-junction into a PTFE tubing, the monomer streams were photopolymerized using an UV lamp operating at a wavelength of 365 nm. The polymerized microfibers were collected into a water bath and washed with water and ethanol to remove the residual PEG (Φsheath) present at the surface of the fibers before air-drying them overnight. The fibers were produced using flow rate of Φcore1, Φcore2, and Φsheath (QTPGDA, QNOA89, and Qsheath) of 2.6, 1.0, and 700 µL/min respectively. The fibers were characterized by numerical and scanning electronic microscopies (Fig. 1b and1c) exhibiting the two distinct parts composing the Janus fibers and no significant degradation of the fibers after 8 months (ESI, Fig. S2). Furthermore, an arrangement of three side-by-side capillaries was obtained by adding another T-junction and sleeve arrangement to the capillary based microfluidic system shown in Fig. 1a. Hecate microfibers composed of three different materials originating from three monomers, i.e. TPGDA, NOA89, and poly(ethylene glycol) diacrylate with a molecular weight of 575 g/mol (PEGDA575), delivered through syringe pumps were prepared in a similar manner with a flow rate equal for all three core phases of 0.7 µL/min and Qsheath = 1200 µL/min. Numerical and scanning electronic microscopies (Fig. 1d and 1e) showed the three phases of the Hecate fiber that were well-merged. Morphological characteristics of Janus fibers (e.g. diameter) can be tuned by varying the volume contribution of each individual core phase as reported for electrospinning. 6 The flow rate of one of the core phases, either QTPGDA or QNOA89, was varied while keeping constant the flow rate of the other core phase. For each experiment the widths of both part of the Janus fiber was measured by numerical microscopy (ESI, Fig. S3) and their variations plotted (Fig. 2a and2b). The width and therefore the volume of each part of the fiber increased with an increase in the flow rate of the respective monomer as we reported for single fibers. 26 Due to the faster diffusion of the less viscous core phase into Φsheath, the corresponding part of the Janus fiber had a larger diameter (i.e. TPGDA). However, as expected, the part of Janus microfiber with constant monomer flow rate showed almost the same width. This clearly demonstrated that individual flow rate of core phases can control the volume of each part of the Janus fiber. Dynamic mechanical analysis (DMA) was performed on NOA89/TPGDA Janus microfibers to determine their elastic modulus and compare them to fibers solely composed of NOA89 having a diameter of 162 µm (Fig. 2c). Two Janus microfibers obtained from different ratios of core phase flow (i.e. 3.5/1.5 and 3/2.5) affording fibers with different widths (75/45 µm and 63/71 µm) were considered. The presence of TPGDA increased noticeably the elastic modulus of pure NOA fiber (35 MPa) by almost twice for NOA89/TPGDA 75/45 (74 MPa) and up to five-fold for NOA89/TPGDA 63/71 (155 MPa). The results could not be compared to pure TPGDA fibers due to their high fragility rendering the DMA measurement not possible. The mechanical properties of a microfiber could be thus easily tuned according to the needs of the application by producing Janus fibers from two material having different mechanical properties. It is worth noticing that all the images presented in this work for the Janus microfibers as well as mechanical tests revealed no delamination of the microfibers. This probably originated from the interdiffusion of monomers in each other phases during the co-flow of the core phases which upon UV-induced polymerization strongly linked the materials together. This is another advantage of the microfluidic spinning technique which allows starting from miscible monomer phases. To evaluate the robustness of the microfluidic spinning technique, a library of Janus microfibers (Fig. 3) was produced using different acrylic monomers including NOA74 (another photocurable acrylate prepolymer), acrylamide (Am), N-isopropyl acrylamide (NIPAm), poly(ethylene glycol) diacrylate with a molecular weight of 400 g/mol (PEGA400), n-butyl acrylate (n-BA), and tertbutyl acrylate (tert-BA). In the case of monovinylic monomers, 4 mol% of crosslinker was added (methyl bisacrylamide for Am, PEGDA250 for n-BA and tert-BA) to ensure the fibers to be stable. All the combinations considered showed a clear interface between the two parts of the Janus fibers without delamination regardless of their different chemical natures (hydrophilic, hydrophobic, etc.). Amphoteric Janus fibers were thus prepared using an anionic monomer (acrylic acid, AA, 80 v% in water) as Φcore1 and a cationic one (2-dimethylamino) ethyl acrylate, DMAEA, 80 v% in water) as Φcore2 (Qcore1 = 1.5 µL/min, Qcore2 = 3.0 µL/min, Qsheath = 550 µL/min). Irgacure 2959 (4 wt/v%) was used as photoinitiator instead of Irgacure 369 to be soluble in the core phases. These fibers were investigated for their potential to simultaneously remove cationic and anionic dyes from a solution of different dyes. The dye removal efficiency (RE%) and the associated kinetic were conducted by immersing the fibers into a solution of 20 mg/L of either methylene blue (MB, cationic dye) or alizarin red S (AR, anionic dye) at 20 °C. An aliquot of the solution was withdrawn from the fiber solution at predetermined times for analysis by visible spectroscopy (664 nm for MB and 406 nm for AR). RE% was calculated for each dye and each time point (ESI, Fig. S4I) permitting to determine that the equilibrium was reached after 150 and 300 min for AR and MB respectively reaching a maximal RE% of 80 and 99% respectively. The adsorption mechanism was further studied by considering pseudo-first-order and pseudosecond-order adsorption models (ESI, Fig. S5) exhibiting a better fit for the latter one with theoretical and experimental values of the adsorption capacity at the equilibrium (qe) relatively close for both dyes (ESI, Table S1). These results indicated that the adsorption of MB and AR could be attributed by the electrostatic attractions of oppositely charged active sites on fibers. 28 The adsorption capacity (qe) for both dyes increased with the increase in the initial concentration in dye (Fig 4a ): at lower concentrations the increase was steeper approaching a plateau value at higher concentrations. Higher adsorption capacity at high concentration is due to the presence of large concentration gradient of dye molecules and adsorbents sites which results in the increase in mass transfer between adsorbent and dye molecules due to larger electrostatic attractions. 29 To evaluate the maximum adsorption capacity of the amphoteric Janus fibers, surface properties and interaction of dye molecules with Janus fiber, the Langmuir and Freundlich isotherm models were applied on the data represented in Fig. 4a (ESI, Fig. S7, Table S1). The data better fitted to the Langmuir isotherm for both dyes showing that the adsorption followed a monolayer homogenous mechanism and the separation constant (RL) was comprised between 0 and 1 for both dyes (ESI, Table S2) showing the higher affinity and favorability of adsorption of dyes with the adsorbent. 30 Furthermore, the favorability of adsorption of MB and AR was confirmed through the Freundlich isotherm model, where the value of n for both dyes was found in the region (0 < n < 10). Another parameter of interest is the pH of the solution that was varied between 3 and 11 (Fig. 4b and ESI, Fig. S5). The adsorption of MB increased from pH 4 to 7 reaching 100% of RE% and maintaining a plateau for higher values of pH. The decrease in adsorption at acidic pH was attributed to the protonation of the carboxylic acid groups reducing the charges accessible for adsorption of the dye at the surface of the poly(AA) part of the Janus fibers. Conversely, the adsorption of AR decreased with increased pH values that could be associated to the deprotonation of the amines and thus lowering the number of sites for AR to adsorb. The adsorption capacity of these fibers for either MB or AR are comparable or superior to materials reported in the literature (ESI, Table S3) considering that most reports are on nanofibers which could have a strong influence on the adsorption capacity due to the higher surface to volume ratio. The adsorption capacity of these amphoteric Janus fibers was compared with fibers having a single part produced with both AA and DMAEA using the same feed composition in monomers and flow rate conditions as for the Janus fibers (Fig. 4c). For each dye and concentration considered, the adsorption capacity of the amphoteric Janus fibers was observed to be superior. This could be due to the lower propensity of the comonomers to neutralize their charges in this structure due to the reduced area in which the monomers of opposite charges were in close proximity to the interface between the two parts of the Janus fibers. The simultaneous removal of both dyes by the amphoteric Janus fibers at pH 6.5 showed a slight decrease in adsorption capacity as compared to when only one dye was used (Fig. 4c) which could be due to (i) the specific pH requirement of each dye (pH = 7 for MB, pH = 6 for AR) and (ii) saturation and/or complexation of dyes in the solution leading to their precipitation (ESI, Fig S8). Recycling capability is one of the crucial factors in evaluating the adsorbent performance. Cationic and anionic dyes could be desorbed using acidic and basic solutions. The fibers adsorbed with MB and AR were soaked into a 0.1 mol/L solution of hydrochloric acid and potassium hydroxide. Four cycles of adsorption-desorption were performed showing a very slight decrease in adsorption efficiency without affecting the appearance of the fibers (ESI, Fig. S9). The decrease may be due to incomplete desorption of adsorbate and loss of active sites during regeneration associated to the protonation and deprotonation of the carboxylic acid and amine groups. In summary, Janus and Hecate microfibers were successfully produced using a simple microfluidic spinning technique. Miscible core and sheath phases were considered to avoid the formation of droplets associated to the interfacial forces among immiscible phases. The width, and thus the volume, of each individual part of Janus microfibers can be easily tuned by altering the flow rate of one of the monomer phases. Janus microfibers of various chemical natures were successfully prepared offering systems with increased mechanical properties and adjustable properties.

Fig. 1

 1 Fig. 1 Janus and Hecate fibers prepared using PEG300 as sheath phase: (a) schematics of the microfluidic side-byside capillaries system used to produce Janus fibers using TPGDA and NOA89 as core phases and the characterization of Janus (b, c) and Hecate (d, e) fibers by numerical (b and d, poly(TPGDA) observed in dark color) and scanning electron (c and e, fiber cross-section in inset) microscopies. Scale bars = 100 µm.

Fig. 2

 2 Fig.2 Janus fibers from NOA89/TPGDA: (a) effect of QTPGDA on the width of poly(TPGDA) part () and cured NOA89 part () of Janus fibers for QNOA89 = 1.0 μL/min, (b) effect of QNOA89 on the width of poly(TPGDA) part () and cured NOA89 part () for QTPGDA = 0.5 μL/min, and (c) comparison of the elastic modulus (E) of pure crosslinked NOA89 fibers with crosslinked NOA89/poly(TPGDA) Janus fibers by DMA.

28

 28

Fig. 3

 3 Fig.3 Numerical microcopy images of Janus fibers produced using different monomer combinations (scale bar = 100 μm). The differences in background colors is due to the contrast corrections done to better observe both parts of the Janus microfibers.

Fig. 4

 4 Fig.4 Amphoteric AA/DMAEA Janus fibers and their capacity to adsorb dyes (MB = methylene blue = , AR = alizarin red S = ): effect of the (a) initial dye concentration on the adsorption capacity (qe) and (b) pH on the dye removal efficiency (RE%), and (c) comparison of fibers with a single part of a copolymer of AA and DMAEA (empty bars, grey border) with Janus fibers (green bars) when exposed to a single dye (filled) and both dyes (diagonal stripes) at 200 and 300 mg/L of dye.

Furthermore, the use of Janus fibers conversely to fibers constituted of a single part with the comonomer composition showed superior performances as illustrated for the removal dye. These results pave the way to the development of multiphase microfibers for a wide range of applications, illustrated here with amphoteric Janus fibers that could be used for the simultaneous removal positively and negatively charges species for water depollution. WR acknowledges the Higher Education Commission Pakistan for his PhD scholarship. This work of the Interdisciplinary Institute HiFunMat, as part of the ITI 2021-2028 program of the University of Strasbourg, CNRS and Inserm, was supported by IdEx Unistra (ANR-10-IDEX-0002) and SFRI (STRAT'US project, ANR-20-SFRI-0012) under the framework of the French Investments for the Future Program. The authors thank the electron microscopy facilities at the Institut Charles Sadron and Damien Favier for his help with DMA.

Conflicts of interest

There are no conflicts to declare.

Notes and references


Peggy Cellier

Mireille Ducassé

Sébastien Ferré

Olivier Ridoux

Formal Concept Analysis Enhances Fault Localization in Software

Recent work in fault localization crosschecks traces of correct and failing execution traces. The implicit underlying technique is to search for association rules which indicate that executing a particular source line will cause the whole execution to fail. This technique, however, has limitations. In this article, we first propose to consider more expressive association rules where several lines imply failure. We then propose to use Formal Concept Analysis (FCA) to analyze the resulting numerous rules in order to improve the readability of the information contained in the rules. The main contribution of this article is to show that applying two data mining techniques, association rules and FCA, produces better results than existing fault localization techniques.

Introduction

The execution of a program in a testing environment generates a set of data about the execution, called a trace of the execution. Traces allow the program to be monitored and permit the program to be debugged when some executions fail, namely produce unexpected results. A trace can contain different kinds of information, for example the executed lines, and the verdict of the execution (FAIL or PASS ). Fault localization often investigates the contents of traces to find the reasons of failures. There exist several approaches to crosscheck traces. Some are based on the differences between a passed execution and a failed execution [START_REF] Renieris | Fault localization with nearest neighbor queries[END_REF][START_REF] Cleve | Locating causes of program failures[END_REF]. Others use statistical indicators in order to rank lines of the program [JHS02,LNZ + 05,LYF + 05]. In particular, Jones et al. [START_REF] Jones | Visualization of test information to assist fault localization[END_REF] propose to measure a kind of correlation between executing a given line and failing a test. Denmat et al. [START_REF] Denmat | Data mining and cross-checking of execution traces: a re-interpretation of jones, harrold and stasko test information[END_REF] show that this is similar to search for a restricted form of association rules [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF][START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] and that the restriction leads to limitations.

Searching for association rules is a well-known data mining task with a welldocumented rationale. The knowledge context is represented by a set of transactions (objects) described by a set of items (attributes). Searching that context for association rules consists in searching for implications where the premise and the conclusion are sets of attributes. In order to measure the relevance of the computed rules, some statistical indicators are used, such as support, confidence, or lift. In the framework of association rules, the method of Jones et al. consists in searching for rules with only one line in their premise and only the attribute FAIL in conclusion. Note that the general association rule framework allows for several attributes in the premise. Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] has already been used for several software engineering tasks: to understand the complex structure of programs, in order to "refactor" class hierarchies for example [START_REF] Snelting | Concept lattices in software analysis[END_REF]; to design the class hierarchy of object-oriented software from specifications [START_REF] Godin | Formal concept analysis-based class hierarchy design in object-oriented software development[END_REF][START_REF] Arévalo | Building abstractions in class models: Formal concept analysis in a model-driven approach[END_REF]; to find causal dependencies [START_REF] Pfaltz | Using concept lattices to uncover causal dependencies in software[END_REF]. Tilley et al. [START_REF] Tilley | A survey of formal concept analysis support for software engineering activities[END_REF] presented a survey on applications of FCA for software engineering activities : e.g. architectural design, software maintenance. FCA finds interesting clusters, called concepts, in data sets. The input of FCA is a formal context, i.e. a binary relation describing elements of a set of objects by subsets of properties (attributes). A formal concept is defined by a pair (extent, intent), where extent is the maximal set of objects that have in their description all attributes of intent, and intent is the maximal set of attributes common to the description of all objects of extent. The concepts of the context can be represented by a lattice where each concept is labelled by its intent and extent.

The main contribution of this article is to show that applying two data mining techniques, association rules and FCA, produces better results than existing fault localization techniques. This is discussed in detail Section 6. Another contribution is to propose to build upon the intuition of existing methods: the difference or correlation between execution traces contains significant clues about the fault. We combine the expressiveness of association rules to search for possible causes of failure, and the power of FCA to explore the results of this analysis. The kind of association rules that we use allows some limitations of other methods to be alleviated. The goal of our method is no longer to highlight the faulty line but to produce an explanation of the failure thanks to the lattice.

In the sequel, Section 2 describes the running example used to illustrate the method. Section 3 presents the two contexts used by the method. Section 4 shows how to interpret the rule lattice in terms of fault localization. Section 5 discusses the statistical indicators. Section 6 presents the main contribution, the benefits of our method compared to other methods. Section 7 discusses further work.

Running Example

Throughout this article, we use the Trityp program given in Figure 1 to illustrate our method. It classifies sets of three segment lengths into four categories: sca- The first mutant is used to explain in details the method. For mutant 1, one fault has been introduced at Line 84. The condition (trityp == 2) is replaced by (trityp == 3). That fault implies a failure in two cases. The first case is when trityp is equal to 2. That case is not taken into account as a particular Line Line Line Line Line Line Line Line 66 68 81 84 85 87 90 93 case and thus treated as a default case, at Lines 89 and 90. The second case is when trityp is equal to 3. That case should lead to the test Line 87, but due to the fault it is first tested at line 84. Indeed, if the condition (i+k>j) holds, trityp is assigned to 2. However, (i+k>j) does not always entail (j+k>i), which is the real condition to test when trityp is equal to 3. Therefore, trityp is assigned to 2 whereas 4 is expected.

• • • P ASS F AIL exec1 × × × × exec4 × × × × × × × exec69 × × × exec108 × × × × × × exec113 × × × × × × × exec114 × × × × × × • • • × exec400 × ×
The fault of mutants 2 and 3 are on assignments. The fault of mutants 4 and 5 are on conditions.

Two Formal Contexts for Fault Localization

This section presents the information on which the localization process is based. Firstly, a context is built from execution traces, the trace context. Secondly, particular association rules are used to crosscheck the trace context. Thirdly, a second context is introduced in order to reason on the numerous rules, the rule context. How to interpret the rule lattice, associated to the rule context, is presented in Section 4.

The Trace Context. In order to reason about program executions we use traces of these executions. There are many types of trace information and discussing them is outside the scope of this article (see for example [HRS + 00]). Let us only assume that each trace contains at least the executed lines and the verdict of the execution, P ASS if the execution produces the expected results and F AIL otherwise. This is a common assumption in fault localization research. This forms the trace context. The objects of the trace context are the execution traces. The attributes are all the lines of the program and the two verdicts. Each trace is described by the executed lines and the verdict of the execution.

Table 2 gives a part of the resulting trace context for mutant 1. For instance, during the first execution, the program executes lines 66, 68, . . . and passes2 .

Line Line Line Line Line Line Line Line Line Line Line Line 81 84 87 90 105 66 78 112 113

• • • 17 58 93 r1 × × × × × × × × × × × × r2 × × × × × × × × × × • • • r8 × × × × × × × r9 × × × × × ×
Table 3. Example of the rule context for mutant 1 of the Trityp program with minlif t = 1.25 and minsup = 1.

Association Rules. In order to understand the causes of the failed executions, we use a data mining algorithm [START_REF] Cellier | A parameterized algorithm for exploring concept lattices[END_REF] which searches for association rules. In addition, to reduce the number of association rules, we focus on association rules based on closed itemsets [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF]. Namely, we search for association rules where 1) the premises are the intents of concepts whose extent mostly contains failed execution traces and few passed execution traces (according to the statistical indicators) and 2) the conclusion is the attribute F AIL (Definition 1). This corresponds to the selection of the concepts that are in relation with the concept labelled by F AIL. Note that those concepts can be in relation with the concept labelled by P ASS, too.

Definition 1 (association rules for fault localization). The computed association rules for fault localization have the form: L → F AIL where L is a set of executed lines such that L ∪ {F AIL} is the intent of a concept in the trace context and L ∩ {F AIL} = ∅.

Only the association rules that satisfy the minimum thresholds of the selected statistical indicators are generated. We have chosen the support and lift indicators. The support indicates the frequency at which the rule appears. In our application, it measures how frequently the lines that form the premise of a given rule are executed among the lines in a failure. The lift indicates if the occurrence of the premise increases the probability to observe the conclusion. Relevant rules are thus filtered with respect to a minimum support, minsup, and a minimum lift, minlif t. The threshold minsup can be very low, for instance to cope with failures that are difficult to detect (for details see Section 5). The threshold minlif t is always greater or equal to 1 because otherwise the lift indicates that the premises decrease the probability to observe the conclusion.

The Rule Context. The computation of association rules generates a lot of rules, and especially rules with large premises. Understanding the links that exist between the rules, for example if a rule is more specific than another, is difficult to do by hand. The computed association rules, however, correspond to concepts of the trace context. They are partially ordered according to their premises; indeed L 1 → F AIL is more specific than L 2 → F AIL when L 1 and L 2 are sets of lines such that L 2 ⊂ L 1 . Therefore, in order to help analyze the 3 rules, we propose to build a new context, the rule context. The objects are the association rules; the attributes are lines. Each association rules is described by the lines of its premise.

Table 3 shows

A Rule Lattice for Fault Localization

The rule lattice is the concept lattice associated with the rule context. It allows association rules to be structured in a way that highlights the partial ordering which exists between them. Figure 2 displays the rule lattice associated with the rule context of Table 3 4 . The remaining of this section presents a description of the rule lattice and then gives an interpretation of it.

Description of the Rule Lattice

The rule lattice has the property that each concept can be labelled at most by one object. Indeed, two different rules cannot have the same premise. If, in the trace context, several executions have exactly the same description they are abstracted in a single rule in the rule context.

The rule lattice is presented in a reduced labelling. In that representation each attribute and each object is written only once. Namely, each concept is labelled by the attributes and the objects that are specific to it. It is the most widespread representation. As a consequence, the premise of a rule r can be computed by collecting the attributes labelling all the concepts above the concept that is labelled by r [GW99]. For example, on Figure 2 the premise of the rule which labels Concept 3 is line 85, line 84, line 68, line 101, line 81, line 93, line 58, line 17, plus the other 20 attributes (lines) that label the top concept.

In the rule lattice, the more specific rules are close to the bottom. When the support threshold for searching for association rules is one object and the lift threshold is close to 1, each most specific rule represents a single execution path in the program that leads to a failure. For example, on Figure 2 there are two very specific rules, the two concepts closest to the bottom: Concept 2 and Concept 3. The rule which labels Concept 2 contains in its premise the lines 66, 105, 90, 87, 84, 81 and the label of the top concept. It corresponds to the failure case when trityp is equal to 2 (see Section 2). The rule which labels Concept 3 contains in its premise the lines 85, 84, 68, 101, 81 and the label of the top concept. It corresponds to the failure case when trityp is equal to 3 (see Section 2). By looking at the support value of each rule, we note that three rules relate to 60 failed executions (Concepts 2, 4, 7), in fact failed executions when trityp is equal to 2; three rules relate to 52 failed executions (Concepts 3, 6, 9), in fact failed executions when trityp is equal to 3; and three rules relate to 112 failed executions (Concepts 5, 8, 10), namely all failed executions.

Interpretation for Fault Localization

Navigating in the rule lattice bottom up first displays rules that are in general too specific to explain the error. It then displays rules that are more general and maybe more informative, and finally displays the top of the lattice which is labelled by the attributes (line numbers) that are common to all failed executions.

The bottom concept of the rule lattice in Figure 2 has no attribute in its labelling. During the debugging session two paths are proposed to follow. The leftmost path from the bottom concept, Concept 2, corresponds to the case where variable trityp is equal to 3 and condition (i+k>j) holds whereas the condition (j+k>i) does not hold. It leads to two concepts. The first concept is Concept 7 labelled by line 66, it is the statement which initializes trityp to 2. The second concept is Concept 4 labelled by three line numbers: 105, 90, 87. These lines correspond to the case when the variable trityp is equal to 2 and trityp is assigned to 4 when 2 is expected, i.e. the triangle is labelled as not a triangle instead of isosceles. Those two concepts are too specific but by looking at the rule of the concept upwards, the faulty line is localized. Concept 5 covers the greatest number of failed executions (support=112) and has the greatest lift among rules which have support equal to 112. The same reasoning can be done with the rightmost concept, Concept 3. It also leads to line 85. It corresponds to the then branch of the faulty conditional, i.e. the line where variable trityp is assigned to 2 when 4 is expected. The rule of that concept is too specific to understand the fault, it covers 52 failed executions. Following this path, three paths open upwards: two concepts whose rules have the same support as the rule of the concept that is labelled by line 85, Concept 6, 9; and a concept which This example shows that the rule lattice gives relevant clues for exploring the program. The faulty line is not highlighted immediately but exploring the lattice bottom up guides the user in its task to understand the fault.

More examples

One failed execution path. Figure 3 gives the rule lattice for mutant 2 when association rules are computed with minlif t=1 and minsup=1. Figure 4 gives the rule lattice for mutant 3 when association rules are computed with minlif t=1 and minsup=1. On those two examples the fault is a bad assignment. Only one execution path leads to a failure. We see in those cases that the faulty lines are immediatly highlighted in the label of the bottom concept. For example, in Figure 3 we see the faulty line 79 at the bottom. We remark that the dependencies between lines appear in the labelling. Indeed, in Figure 4 we see that the bottom concept is labelled not only by the faulty line 64 but also by line 79 and line 103. It is explained by two facts. Firstly, the execution of line 64 in a faulty way always implies the execution of line 79 and 103. Secondly, few executions that imply lines 64, 79 and 103 together pass. Note that all association rules of these examples have the same support. They cover all failed execution traces.

Several failed execution paths. The execution of mutant 1 and 4 can fail with different execution paths. Mutant 1 was detailed in the previous section. Figure 5 gives the rule lattice for mutant 4 when association rules are computed with minlif t = 1 and minsup = 1. The fault of mutant 4 is at line 87. In the rule lattice of Figure 5, line 87 labels the concept which is labelled by a rule with the greatest support. In addition, among rules with the greatest support, this one has the greatest lift. In other words, line 87 is one of the common lines of all failed executions and with the least relation with passed executions.

Borderline case. Figure 6 gives the rule lattice for mutant 5 when association rules are computed with minlif t=1 and minsup=1. In the rule lattice, two failed execution paths are highlighted. One covers 33 of the failed executions. The other covers 62 of the failed executions. Looking at the common lines of those two execution paths, we find line 66. The associated rule of line 66 has the greatest lift among rules with support equal to 95. But the faulty line is 65. Line 65 labels the top concept of the rule lattice. The faulty line is thus not highlighted. It is due to the fact that line 65 is an if-statement executed by all executions. The number of failed executions that execute line 65 is thus very low with respect to the number of passed executions that execute line 65. However, line 66 is the then branch of the condition of line 65. The method does not highlight the faulty line but gives clues to find it.

Statistical Indicators

In order to compute and evaluate the relevance of association rules, several statistical indicators have been proposed, for example support, confidence, and lift [START_REF] Brin | Dynamic itemset counting and implication rules for market basket data[END_REF]. The choice of statistical indicators and their thresholds is an im- portant part of the computation of association rules. Depending on the selected thresholds, the rule lattice may significantly vary and so does its interpretation.

Typically, the support is the first filtering criterion for the extraction of association rules. It measures the frequency of a rule. For the fault localization problem, the value of minsup indicates the minimum number of failed executions that should be covered by a concept of the trace context to be selected. Choosing a very high threshold, only the most frequent execution paths are represented in the set of association rules. Choosing a very low threshold, minsup equals to one object, all execution paths that are stressed by the test cases are represented in the set of association rules. In our experiments, we choose minsup equals to one object. It is equivalent to search for all rules that cover at least one failed execution. The threshold can be greater in order to select less rules, but some failed execution paths would be lost, although in fault localization rare paths might be more relevant than common ones.

The other well-known indicator that we use is lift. In our approach, the lift indicates how the execution of a set of lines improves the probability to have a failed execution. The lift threshold can be seen as a resolution5 cursor. On the one hand, if the threshold is high, few rules are computed, therefore few concepts appear in the lattice. It implies that the label of each concept contains a lot of lines, but each concept is very relevant. On the other hand, selecting a low threshold implies that more rules are computed. Those rules are less relevant and the number of concepts in the lattice increases. The number of attributes per label is thus reduced. For example, let us consider mutant 1 of program Trityp. Figure 2, already described in Section 4, shows the result lattice when the lift threshold is equal to 1.25. Figure 7 shows the result lattice when the lift threshold is equal to 1.5. Concept D of Figure 7 merges Concepts 5 and 8 of Figure 2. Concepts D and 5 actually correspond to the same rule. Concept 8 correspond to a more general rule with a lower lift. The same applies to Concepts C and 3, 6.

In addition, the concepts of the rule lattice have two properties thanks to the statistical indicators related to the trace lattice. Property 1 states that the support of rules that label the concepts of the rule lattice decreases when exploring the lattice top down. In the following, label(c)=r means that rule r labels concept c of the rule lattice. The extent of a set of attributes, X, is written ext(X), and Y denotes the cardinal of set Y.

Property 1. Let c 1 and c 2 be two concepts of the rule lattice such that label(c 1 )=r 1 and label(c 2 )=r 2 . If c 2 < c 1 then sup(r 2 ) ≤ sup(r 1 ).

Proof. The fact that c 2 < c 1 implies that the intent of c 2 contains the intent of c 1 . The intent of concept c 1 (resp. c 2 ) is the premise, p 1 (resp. p 2 ), of rule r 1 (resp. r 2 ), thus p 1 ⊂ p 2 . Conversely ext(p 2 ) ⊂ ext(p 1 ). As the definition of the support of a rule

r = p → F AIL is sup(r) = ext(p) ∩ ext(F AIL) , sup(r 2 ) ≤ sup(r 1 ) holds.
Property 2 is about the lift value. If two ordered concepts in the rule lattice are labelled by rules with the same support value, the lift value of the rule which labels the more specific concept is greater. That is why the rule lattice is explored bottom up (see Section 4.2).

Property 2. If c 2 < c 1 and sup(r 2 ) = sup(r 1 ) then lif t(r 2 ) > lif t(r 1 ).

Proof. In the previous proof we have seen that c 2 < c 1 implies that ext(p 2 ) ⊂ ext(p 1 ). The definition of the lift of a rule r = p → F AIL is lif t(r) = sup(r) ext(p) ext(F AIL) * O . As sup(r 2 ) = sup(r 1 ), and ext(p 2 ) < ext(p 1 ) , lif t(r 2 ) > lif t(r 1 ) holds.

Benefits of Using Association Rules and FCA

The contexts and lattice structures introduced in the previous sections allow programmers to see all the differences between execution traces as well as all the differences between association rules. There exists other methods which compute differences between execution traces. Section 6.1 shows that the information about trace differences provided by our first context (and the corresponding lattice) is already more relevant than the information provided by four other methods proposed by Renieris and Reiss [START_REF] Renieris | Fault localization with nearest neighbor queries[END_REF], as well as Zeller et al. [START_REF] Cleve | Locating causes of program failures[END_REF]. Section 6.2 shows that explicitly using association rules with several lines in the premise alleviate many of the limitations of Jones et al.'s method mentioned in the introduction [START_REF] Jones | Visualization of test information to assist fault localization[END_REF]. Section 6.3 shows that reasoning on the partial ordering given by the proposed rule lattice is more relevant than reasoning on total order rankings [JHS02,LNZ + 05,LYF + 05].

The Trace Context Structures Execution Traces

The first context that we have introduced, the trace context, contains the whole information about execution traces (see Section 3). In particular, the associated lattice, the trace lattice, allows programmers to see in one pass all differences between traces. Figure 8 shows the trace lattice of mutant 1.

There exists several fault localization methods based on the differences of execution traces. They all assume a single failed execution and several passed executions. We rephrase them in terms of search in a lattice to highlight their advantages, their hidden hypothesis and limitations.

The union model, proposed by Renieris and Reiss [START_REF] Renieris | Fault localization with nearest neighbor queries[END_REF], aims at finding features that are specific to the failed execution. The method is based on trace differences between the failed execution f and a set of passed executions S: f -s∈S s. The underlying intuition is that the failure is caused by lines that are executed only in the failed execution. Formalized in FCA terms, the concept of interest is the one whose label contains F AIL, and the computed information is the lines contained in the label. For example, in Figure 8 this corresponds to the upper concept on the right-hand side which contains no line in its label, namely the information provided by the union model is empty. The trace lattice presented in the figure is slightly different from the lattice that would be computed for the union model, because it represents more than one failed execution. Nevertheless, the union model often computes an empty information, namely each time the faulty line belongs to failed and passed execution traces. For example, a fault in a condition has a very slight chance to be localized. Our approach is based on the same intuition. However, as illustrated by Figures 8 and2, the lattices that we propose do not lose information and help to navigate in order to localize the faults, even when the faulty line belongs to failed and passed execution traces.

The union model helps localize bug when executing the faulty statement always implies an error, for example the bad assignment of a variable that is the result of the program. In that case, our lattice does also help, the faulty statement label the same concept as F AIL.

The intersection model [START_REF] Renieris | Fault localization with nearest neighbor queries[END_REF] is the complementary of the previous model. It computes the features whose absence is discriminant of the failed execution: s∈S sf . Replacing F AIL by P ASS in the above discussion is relevant to discuss the intersection model and leads to the same conclusions.

The nearest neighbor approach [START_REF] Renieris | Fault localization with nearest neighbor queries[END_REF] computes the Ulam's distance metrics between the failed execution trace and a set of passed execution traces. The computed trace difference involves the failed execution trace, f , and only one passed execution trace, the nearest one, p: fp. That difference is meant to be the part of the code to explore. The approach can be formalized in FCA. Given a concept C f whose intent contains F AIL, the nearest neighbor method search for a concept C p whose intent contains P ASS, such that the intent of C p shares as many lines as possible with the intent of C f . On Figure 8 for example, the two circled concepts are "near", their share all their line attributes except the attributes F AIL and P ASS, therefore f = p and fp = ∅. The rightmost concept fails whereas the leftmost one passes. As for the previous methods, it is a good approach when the execution of the faulty statement always involves an error. But as we see on the example, when the faulty statement can lead to both a passed and a failed execution, the method is not sufficient. In addition, we remark that there are possibly many concepts of interest, namely all the nearest neighbors of the concept which is labelled by F AIL. With a lattice that kind of behavior can be observed directly.

Note that in the trace lattice, the executions that execute the same lines are clustered in the label of a single concept. Executions that are near share a large part of their executed lines and label concepts that are neighbors in the lattice. There is therefore no reason to restrict the comparison to a single pass execution. Furthermore, all the nearest neighbors are naturally in the lattice.

Delta debugging, proposed by Zeller et al. [START_REF] Cleve | Locating causes of program failures[END_REF], reasons on the values of variables during executions rather than on executed lines. The trace information, and therefore the trace context, contains different types of attributes. Note that our approach does not depend on the type of attributes and would apply on traces containing other attributes than executed lines.

Delta debugging computes in a memory graph the differences between the failed execution trace and a single passed execution trace. By injecting the values of variables of the failed execution into variables of the passed execution, the method tries to determine a small set of suspicious variables. One of the purpose of that method is to find a passed execution relatively similar to the failed execution. It has the same drawbacks as the nearest neighbor method.

Association Rules Select a Part of the Trace Context

As it was presented in the introduction, Jones et al. [START_REF] Jones | Visualization of test information to assist fault localization[END_REF] compute association rules with only one line in the premises. Denmat et al. show that the method has limitations, because it assumes that an error has a single faulty statement origin, and lines are independent. In addition, they demonstrate that the ad hoc indicator which is used by Jones et al. is close to the lift indicator.

By using association rules with more expressive premises than the Jones et al. method (namely with several lines), the limitations mentioned above are alleviated. Firstly, the fault can be not only a single line, but the execution of several lines together. Secondly, the dependency between lines is taken into account. Indeed, dependent lines are clustered or ordered together.

The part of the trace context which is important to search for localizing a fault is the set of concepts that are around the concept labelled by F AIL; i.e. those that have a non-empty intersection with the concept labelled F AIL. Computing association rules with F AIL as a conclusion computes exactly those concepts, modulo the minsup and minlif t filtering. In other words the focus is done on the part of the lattice around the concept labelled by F AIL. For example, in the trace lattice of the Trityp program presented in Figure 8, the rule lattice when minlif t is very low (yet still attractive, i.e. minlif t>1), is drawn in bold lines.

The Rule Lattice Structures Association Rules

Jones et al.'s method presents the result of their analysis to the user as a coloring of the source code. A red-green gradient indicates the correlation with failure. Lines that are highly correlated with failure are colored in red, whereas lines that are highly not correlated are colored in green. Red lines typically represents more than 10% of the lines of the program, whithout identified links between them. Some other statistical methods [LNZ + 05,LYF + 05] also try to rank lines in a total ordering. It can be seen as ordering the concepts of the rule lattice by the lift value of the rule in their label. From the concept ordering the lines in the label of those concepts can be ordered.

For example, on the rule lattice of Figure 2, the obtained ranking would be: line 85, line 66, line 68, line 84, . . . No link would be established between the execution of line 85 and line 68 for example.

The user who has to localize a fault in a program has a background knowledge about the program, and can use it to explore the rule lattice. The reading of the lattice gives a context of the fault and not just a sequence of independent lines to be examined, and reduces the number of lines to be examined at each step (concept) by structuring them.

Further work

The process proposed in this article for fault localization is already usable at the end of the debug session. When the programmer has a rough idea of the location of the faults and that only a small part of the execution has to be traced, the current techniques to visualize lattices can be directly used.

However, we conjecture that the technique, with some extensions, can be used to analyze large executions. At present, the information is presented in terms of lines whereas it is not always the most relevant information granularity. For example, given a basic block (i.e. a sequence of instructions with neither branching nor conditional), all its lines always appear in the same label. Displaying the location of the basic block would be more relevant. This will help keeping concept labels to a readable size. We are currently working on the presentation of the results to reduce their size and to give more semantics to them so that they are more tractable for users.

Another further work is the computation of the concepts of the rule context directly from the trace context. Indeed, the concepts of the rule lattice belong to the trace lattice. However, gathering the two computations, association rules from the trace context and concepts from the rule context, is not a trivial task due to the statistical indicators which are not monotonous, for example the lift.

Conclusion

In this article we have proposed a new application of FCA: namely, fault localization. The process combines association rules and formal concept lattices to give a relevant way to navigate into the source code of faulty programs. Compared to existing methods, using a trace lattice has three advantages. Firstly, thanks to the capabilities of FCA to crosscheck data, our approach computes in one pass more information about execution differences than all the cited approaches together. In particular, the information computed by two methods, the union model and the intersection model, can be directly found in the trace lattice. Secondly, the lattice structure gives a better reasoning basis than any particular distance metrics to find similar execution traces. Indeed, all differences between the sets of executed lines of passed and failed executions are represented in the trace lattice. A given distance between two executions can be computed by dedicated reasoning on specific attributes. Thirdly, our approach treats several failed executions together, whereas the presented methods can analyze only one failed execution.

Moreover, the generality of the FCA framework makes it possible to handle traces that contain other information than lines numbers. In summary, casting the fault localization problem in the FCA framework helps analyze existing approaches, as well as alleviate their limitations.

Fig. 2 .

 2 Fig. 2. Rule lattice for mutant 1 associated to the rule context of Table 3

  a part of the rule context for mutant 1 of the Trityp program with the support threshold, minsup, equal to 1 object and the lift threshold minlif t equal to 1.25. The premise of rule 1 contains : line 81, line 84, line 87, line 90, . . . 3 In addition, line 78, line 112, line 113, . . ., line 17, line 58, line 93 are present in all rules which means that they are executed by all failed executions.

Fig. 3 .

 3 Fig. 3. Rule lattice from program Trityp with mutant 2 (faulty line 79) with minlift=1 and minsup=1.

Fig. 4 .

 4 Fig. 4. Rule lattice from program Trityp with mutant 3 (faulty line 64) with minlift=1 and minsup=1.

Fig. 5 .

 5 Fig. 5. Rule lattice from program Trityp with mutant 4 (faulty line 87) with minlift=1 and minsup=1.

Fig. 6 .

 6 Fig. 6. Rule lattice from program Trityp with mutant 5 (faulty line 65) with min-lift=1 and minsup=1.

Fig. 7 .

 7 Fig. 7. Lattice from the rule context of mutant 1 with minlift=1.5 and min-sup=1.

Fig. 8 .

 8 Fig. 8. Lattice from the trace context of mutant 1 of the Trityp program.

Table 1 .

 1 Mutants of the Trityp program.

	Mutant # passed exec. # failed exec. Faulty line
	1	288	112	[84] if ((trityp == 3) && (i+k > j))
	2	384	16	[79] trityp = 0 ;
	3	308	92	[64] trityp = i+1 ;
	4	280	120	[87] if ((trityp != 3) && (j+k > i))
	5	305	95	[65] if (i >= k)

Table 2 .

 2 Example of the trace context for mutant 1 of the Trityp program.

http://www.irisa.fr/lande/gotlieb/resources/Java exp/trityp/

Complete context: http://www.irisa.fr/LIS/cellier/icfca08/trace context.txt

Complete rule context: http://www.irisa.fr/LIS/cellier/icfca08/rules context.rl

The lattice was generated with the ToscanaJ tool (http://toscanaj.sourceforge.net/)

The word "resolution" is used here as in "image display resolution".


Maud Ehrmann
email: maud.ehrmann@epfl.ch

Matteo Romanello
email: matteo.romanello@unil.ch

Antoine Doucet
email: antoine.doucet@univ-lr.fr

Simon Clematide
email: simon.clematide@uzh.ch

Introducing the HIPE 2022 Shared Task: Named Entity Recognition and Linking in Multilingual Historical Document

Keywords: named entity processing, information extraction, text understanding, historical documents, digital humanities

We present the HIPE-2022 shared task on named entity processing in multilingual historical documents. Following the success of the first CLEF-HIPE-2020 evaluation lab, this edition confronts systems with the challenges of dealing with more languages, learning domain-specific entities, and adapting to diverse annotation tag sets. HIPE-2022 is part of the ongoing efforts of the natural language processing and digital humanities communities to adapt and develop appropriate technologies to efficiently retrieve and explore information from historical texts. On such material, however, named entity processing techniques face the challenges of domain heterogeneity, input noisiness, dynamics of language, and lack of resources. In this context, the main objective of the evaluation lab is to gain new insights into the transferability of named entity processing approaches across languages, time periods, document types, and annotation tag sets.

Introduction

Through decades of massive digitisation, an unprecedented amount of historical documents became available in digital format, along with their machine-readable texts. While this represents a major step forward in terms of preservation and accessibility, it also bears the potential for new ways to engage with historical documents' contents. The application of machine reading to historical documents is potentially transformative and the next fundamental challenge is to adapt and

The version of record is available at https://doi.org/10.1007/978-3-030-99739-744.

develop appropriate technologies to efficiently search, retrieve and explore information from this 'big data of the past' [START_REF] Kaplan | Big Data of the Past[END_REF]. Semantic indexing of historical documents is in great demand among humanities scholars, and the interdisciplinary efforts of the digital humanities (DH), natural language processing (NLP), computer vision and cultural heritage communities are progressively pushing forward the processing of facsimiles, as well as the extraction, linking and representation of the complex information enclosed in transcriptions of digitised collections [START_REF] Ridge | The past, present and future of digital scholarship with newspaper collections[END_REF]. In this regard, information extraction techniques, and particularly named entity (NE) processing, can be considered among the first and most crucial processing steps.

Yet, the recognition, classification and disambiguation of NEs in historical texts are not straightforward, and performances are not on par with what is usually observed on contemporary well-edited English news material [START_REF] Ehrmann | Diachronic evaluation of NER systems on old newspapers[END_REF]. In particular, NE processing on historical documents faces the challenges of domain heterogeneity, input noisiness, dynamics of language, and lack of resources [START_REF] Ehrmann | Named Entity Recognition and Classification on Historical Documents: A Survey[END_REF]. Although some of these issues have already been tackled in isolation in other contexts (with e.g., user-generated text), what makes the task particularly difficult is their simultaneous combination and their magnitude: texts are severely noisy, and domains and time periods are far apart.

In this regard, the first CLEF-HIPE-2020 edition5 [START_REF] Ehrmann | Extended Overview of CLEF HIPE 2020: Named Entity Processing on Historical Newspapers[END_REF] proposed the tasks of NE recognition and classification (NER) and entity linking (EL) in ca. 200 years of historical newspapers written in English, French and German and successfully showed that the progress in neural NLP -specifically driven by Transformerbased approaches -also translates into improved performances on historical material, especially for NER. In the meantime, several European cultural heritage projects have prepared additional annotated text material, thereby opening a unique window of opportunity for organising a second edition of the HIPE evaluation lab in 2022.

Motivation and Objectives

As the first evaluation campaign of its kind on multilingual historical newspaper material, HIPE-2020 brought together 13 enthusiastic teams who submitted a total of 75 runs for 5 different task bundles. The main conclusion of this edition was that neural-based approaches can achieve good performances on historical NERC when provided with enough training data, but that progress is still needed to further improve performances, adequately handle OCR noise and small-data settings, and better address entity linking. HIPE-2022 will attempt to drive further progress on these points, and also confront systems with new challenges. HIPE-20226 will focus on named entity processing in historical documents covering the period from the 18th to the 20th century and featuring several languages. Compared to the first edition, HIPE-2022 introduces several novelties, with:

the addition of a new type of document alongside historical newspapers, namely classical commentaries 7 ; the consideration of a broader language spectrum, with 5 languages for historical newspapers (3 for the previous edition), and 3 for classical commentaries; the confrontation with the issue of the heterogeneity of annotation tag sets and guidelines.

Overall, HIPE-2022 will confront participants with the challenges of dealing with more languages, learning domain-specific entities, and adapting to diverse annotation schemas. The evaluation lab will therefore contribute to gain new insights on how best to ensure the transferability of NE processing approaches across languages, time periods, document and annotation types, and to answer the question whether one architecture/model can be optimised to perform well across settings and annotation targets in a cultural heritage context. In particular, the following research questions will be addressed:

1. How well can general prior knowledge transfer to historical texts? 2. Are in-domain language representations (i.e. language models learned on the historical document collections) beneficial, and under which conditions? 3. How can systems adapt and integrate training material with different annotations? 4. How can systems, with limited additional in-domain training material, (re)target models to produce a certain type of annotation?

Recent work on NERC showed encouraging progress on several of these topics: Beryozkin et al. [START_REF] Beryozkin | A joint named-entity recognizer for heterogeneous tag-sets using a tag hierarchy[END_REF] proposed a method to deal with related, but heterogeneous tag sets. Several researchers successfully applied meta-learning strategies to NERC in order to improve transfer learning: Li et al. [START_REF] Li | Few-shot named entity recognition via meta-learning[END_REF] improved results for extreme low-resource few-shot settings where only a handful of annotated examples for each entity class are used for training; Wu et al. [START_REF] Wu | Enhanced meta-learning for cross-lingual named entity recognition with minimal resources[END_REF] presented techniques to improve cross-lingual transfer; and Li et al. [START_REF] Li | Metaner: Named entity recognition with meta-learning[END_REF] tackled the problem of domain shifts and heterogeneous label sets using meta-learning, proposing a highly data-efficient domain adaptation approach.

Significance of the Evaluation Lab

HIPE-2022 will benefit the NLP and DH communities, as well as cultural heritage professionals.

Benefits for the NLP community -NLP and information extraction practitioners will have the possibility to test the robustness of existing approaches and to experiment with transfer learning and domain adaptation methods, whose 7 Classical commentaries are scholarly publications dedicated to the in-depth analysis and explanation of ancient literary works. As such, they aim to facilitate the reading and understanding of a given literary text. More information on the HIPE-2022 classical commentaries corpus in Section 3.2.

performances could be systematically evaluated and compared on broad historical and multilingual data sets. Beside gaining new insights with respect to domain and language adaptation and advancing the state of the art in semantic indexing of historical material, the lab will also contribute a set of multilingual NE-annotated datasets that could be used for further training and benchmarking.

Benefits for the DH community -DH researchers are in need of support to explore the large quantities of text they currently have at hand, and NE processing is high on their wish list. Such processing can support research questions in various domains (e.g. history, political science, literature and historical linguistics) and knowing about performances is a must in order to do an informed usage of the enriched data. This lab's outcome (datasets and systems) will be beneficial to DH practitioners insofar as it will help identify state-of-the-art solutions for NE processing of historical texts.

Benefits for cultural heritage professionals -Libraries, archives and museums (LAM) increasingly focus on advancing the usage of artificial intelligence methods on cultural heritage text collections, in particular NE processing [START_REF] Padilla | Responsible Operations: Data Science, Machine Learning, and AI in Libraries[END_REF][START_REF] Gregory | AI in relation to GLAMs task FOrce -Report and Recommendations[END_REF]. This community is eager to collaborate and provide data (when copyright allows) for high-quality semantic enrichment. Subtask 1.2 -NERC-Fine: includes 'NERC-Coarse', plus the detection and classification at sub-type level and the detection of NE components (e.g. function, title, name). This subtask will be proposed for English, French and German only.

Overview of the Evaluation Lab

Task 2: Named Entity Linking (EL) This task corresponds to the linking of named entity mentions to a unique item ID in Wikidata, our knowledge base of choice, or to a NIL node if the mention does not have a corresponding item in the KB. We will allow submissions of both end-to-end systems (NERC and EL) and of systems performing exclusively EL on gold entity mentions provided by the organizers (EL-only).

Data Sets

Corpora The lab's corpora will be composed of historical newspapers and classic commentaries covering ca. 200 years. We benefit from published and todate unpublished NE-annotated data from organisers' previous research project, from the previous HIPE-2020 campaign, as well as from several ongoing research projects which agreed to postpone the publication of 10% to 20% of their annotated material in order to support HIPE-2022.

Historical newspapers. The historical newspaper data is composed of several datasets in English, Finnish, French, German and Swedish which originate from various projects and national libraries in Europe:

-Le Temps data: an unpublished, annotated diachronic dataset composed of historical newspaper articles from two Swiss newspapers in French (19C-20C) [START_REF] Ehrmann | Diachronic evaluation of NER systems on old newspapers[END_REF]. This dataset contains 10,580 entity mentions and will be part of the training, dev and test sets. -HIPE-2020 data: the datasets used during the first HIPE-2020 campaign, composed of newspaper articles from Swiss, Luxembourgish and American newspapers in French, German and English (19C-20C). These datasets contain 19,848 linked entities and will be part of the training sets. -HIPE-2020 unpublished data: a set of unpublished diachronic annotated data composed of newspaper articles from Swiss newspapers in French and German (19C-20C). These data will be part of the test sets. -NewsEye data8 : a partially published annotated dataset composed of newspaper articles from newspapers in French, German, Finnish and Swedish (19C-20C) [START_REF] Hamdi | A Multilingual Dataset for Named Entity Recognition, Entity Linking and Stance Detection in Historical Newspapers[END_REF]. The already published part contains 30,580 entities and will be part of the training and dev sets. The unpublished one (roughly 20% of the total) will be part of the test set. -SoNAR data: an annotated dataset composed of newspaper articles from the Berlin State library newspaper collections in German (19C-20C), produced in the context of the SoNAR project 9 . The (soon to be) published part of this dataset will be part of the training and dev sets, while the unpublished lot will integrate the HIPE-2022 test set. -Living With Machines data10 : an annotated dataset composed of newspaper articles from the British Library newspapers in English (18C-19C), and annotated exclusively with geographical locations following ad-hoc annotation guidelines. The already published portion of the data [START_REF] Coll | Dataset for Toponym Resolution in Nineteenth-Century English Newspapers[END_REF] contains 3,355 annotated toponyms and will be included in the training and dev sets. The unpublished portion will be part of the test set.

Historical commentaries. The classical commentaries data originates from the Ajax Multi-Commentary project and is composed of OCRed 19C commentaries published in French, German and English [START_REF] Romanello | Optical Character Recognition of 19th Century Classical Commentaries: the Current State of Affairs[END_REF], annotated with both universal NEs (person, location, organisation) and domain-specific NEs (bibliographic references to primary and secondary literature). In the field of classical studies, commentaries constitute one of the most important and enduring forms of scholarship, together with critical editions and translations. They are information-rich texts, characterised by a high density of NEs.

Annotation In terms of annotation, the common requirement for most of these datasets is to have person, location and organisation entity types, and entity links towards Wikidata. The guidelines used to annotate many datasets derive from related directives (Quaero and impresso-HIPE-2020 guidelines) 11 , yet they do differ in some respects such as granularity of annotations (coarse vs fine-grained), treatment of metonymy and inclusion of entity components.

Evaluation

To accommodate the different dimensions that characterise our datasets (languages, document types, domains, entity tag sets) and foster research on transferability, the evaluation lab will be organised around two main 'challenges', namely a multilingual challenge and an adaptation challenge, each featuring several task 'tracks'. They will ensure that participants will have to work across settings, e.g. with documents in at least two different languages or annotated according to two different tag sets or guidelines, while keeping a clear and defined evaluation frame.

Evaluation will be performed with the open source HIPE scorer 12 , which was developed for the first edition of the shared task. Evaluation metrics implemented in the scorer include (macro and micro) Precision, Recall, and F-measure and evaluation settings will include strict (exact matching) and relaxed (fuzzy matching) evaluation scenarios.

Conclusion

Following a first and successful shared task on NE processing on historical newspapers, the HIPE-2022 evaluation lab proposes to confront systems with the new challenges of dealing with more languages, learning domain-specific entities, and adapting to diverse annotation tag sets. The overall objective is to assess and advance the development of robust, adaptable and transferable named entity processing systems in order to support information extraction and text understanding of cultural heritage data.

3. 1

 1 Task Description HIPE-2022 focuses on the same tasks as CLEF-HIPE-2020, namely: Task 1: Named Entity Recognition and Classification (NERC) Subtask 1.1 -NERC-Coarse: this task includes the recognition and classification of high-level entity types (Person, Organisation, Location, Product and domain-specific entities, e.g. mythological characters or literary works in classical commentaries).

https://impresso.github.io/CLEF-HIPE-2020

https://hipe-eval.github.io/HIPE-2022/

https://www.newseye.eu/

https://sonar.fh-potsdam.de/

https://livingwithmachines.ac.uk/

Impresso[START_REF] Ehrmann | Impresso Named Entity Annotation Guidelines[END_REF] and SoNAR guidelines[START_REF] Menzel | Guidelines for Full Text Annotations in the SoNAR (IDH) Corpus[END_REF] were derived from Quaero guidelines[START_REF] Rosset | Entités nommées structurées : Guide d'annotation Quaero[END_REF], while NewsEye guidelines correspond to a subset of the impresso guidelines.

https://github.com/impresso/CLEF-HIPE-2020-scorer

The NewsEye project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 770299

Acknowledgements

We are grateful to the research project consortia and teams who kindly accepted to retain the publication of part of their NE-annotated datasets to support HIPE-2022: the NewsEye project 13 ; the Living with Machine project, in particular Mariona Coll'Ardanuy; and the SoNAR project, in particular Clemens Neudecker. We also thank Sally Chambers, Clemens Neudecker and Frédéric Kaplan for their support and guidance as part of the lab's advisory board.