Chloé Adam

Antoine Aliotti

Paul-Henry Cournède

Learning from User Workflows for the Characterization and Prediction of Software Crashes

Keywords: Medical Applications, Software Crash, Graph-Of-Word, Graph-Of-Actions, Hierarchical Clustering

Reducing as much as possible the rate of software crashes is crucial especially in medical applications. In this paper, we make the assumption that crashes result from the user workflow, that is to say the sequence of user actions. Our objective is thus to identify root causes of crashes and to anticipate them in real-time, based on the analysis of the sequences of user actions. For these purposes, we introduce two methods. The first one consists in using graph-based representations to detect combinations of user actions having a high probability to provoke a software crash, thus identifying crash signatures and helping for problem resolution. The second one, based on clustering of user sessions, is a real-time monitoring method, computing a crash probability at each new user action. Test cases show promising results for both methods. Our representation of user session as 'Graph-of-Actions' enabled the identification of some significant crash signatures while revealing the impact of successive actions dependence on crash causes. Likewise, our clustering based method for session monitoring resulted in promising values of sensitivity and specificity for some specific clustering configurations.

Introduction

Radiologists use medical imaging solutions on a daily basis for diagnosis, surgery preparation or follow-up treatment, covering a large variety of pathologies. Today's imaging modalities (CT, MR, 3D X-ray, PET and PET/CT) present a huge challenge for the physician workflow: the number of patient exams increases while the time for exam data analysis and reporting decreases. Log files enable to record the evolution of the various software and system parameters during their use as well as the sequence of practitioner actions. A specific problem potentially occurring in the process is the crash of the analysis software with severe consequences on the practitioner workflow. This is all the more true in the case of interventional applications, in which patient safety is put at stake. Therefore, reducing or annulling the crash rate of medical applications is a major line of the continuous improvement effort regarding the global quality and usability of medical software products. The aim of this study is to analyze the log file data for a better management of this crash risk. More specifically, we aim at identifying the root causes of the crashes and anticipate them in real-time.

Several factors such as user actions in the software interface (moves, selected tool, mouse clicks, etc.) or the system status (number of applications running, memory availability, dataset type, etc.) are likely to cause crashes. In this paper we will specifically focus on the user workflow. Thus, we will try to characterize and predict crashes based on the sequences of user actions. No real off-the-shelf solution currently exists, even though there are some comparable methodologies in other sequence learning tasks [START_REF] Lane | Temporal sequence learning and data reduction for anomaly detection[END_REF].

Numerous questions concerning the root causes of the crashes need to be addressed. Indeed, we do not know if crashes result from individual actions or from combinations of successive actions, if the order of actions has an impact... Similarly, we have no information about the exact moment in the session at which the crash is triggered. Answering these questions is even more challenging given the very high variability in the user sequences leading to crashes. To tackle these issues, the first objective of this paper is to propose a method enabling to detect patterns of user actions having a high crash probability. The motivation is here to help the software development teams enabling them to focus on specific program functions.

For this purpose, we will propose graph-based representations of the successive actions recorded in log files. We were greatly inspired by research works in the domain of information retrieval in text document. We used in particular the principle of the traditional bag-of-words filters, comparing relative frequencies of independent terms to detect spam emails or mobile messages [START_REF] Sculley | Relaxed online svms for spam filtering[END_REF]. We then moved to graph-based representations which have been widely investigated and applied in a large range of fields due to their powerful properties. Indeed, they enable to catch the direct dependencies between events. We based a part of our work on the representation used in [START_REF] Eirinaki | Web path recommendations based on page ranking and markov models[END_REF], where user web sessions are transformed into weighted paths. To allow more flexibility to our representation, we also adapted the graph-of-words model proposed by [START_REF] Rousseau | Graph-of-word and tw-idf: new approach to ad hoc ir[END_REF] to our data.

The second objective of this paper is to introduce a real-time monitoring method, computing a crash probability at each new user action, based on the identification of clusters of user session queues (with the underlying assumption that the actions causing a crash are among the last ones before it happens). The motivation here is more related to risk management for the benefit of the users, imagining for example an automatic backup system triggered as soon as the crash probability exceeds a certain threshold. The research questions bear similarities with problems arising in the field of anomaly detection which is very used in the area of computer security, in particular for intrusion detection. A comparison of different approaches of anomaly detection was done in [START_REF] Warrender | Detecting intrusions using system calls: Alternative data models[END_REF]. Several similar methods were developed to detect intrusion using sequences of system calls. The principle is to build up a profile of normal behavior traces, treating deviations from this profile as anomalies [START_REF] Hofmeyr | Intrusion detection using sequences of system calls[END_REF][START_REF] Forrest | A sense of self for unix processes[END_REF]. These techniques slightly vary in the definition of the dissimilarity measure used to compute how much a new sequence differs from existing normal sequences. Given the format of our data, we will in particular use the Hamming distance as in [START_REF] Hofmeyr | Intrusion detection using sequences of system calls[END_REF]. An interesting extrapolation of the same concept to detect network intrusions is based on clustering and classifies each new session as normal or as an attack depending on the dissimilarity measure between this session and the existing clusters [START_REF] Portnoy | Intrusion detection with unlabeled data using clustering[END_REF].

Although not dedicated to anomaly detection, [START_REF] Scherbina | Clustering of web sessions using levenshtein metric[END_REF] is interesting since it uses a customized Levenshtein metric to cluster web sessions of variable lengths, this metric will also be tested for the application of our proposed method.

The paper first introduces a formal grammar enabling to translate the sequences of actions in log files into computational objects. We then propose in section III different representations enabling to detect combinations of user actions having a high probability to provoke crashes, and we compare the different representations on a test case. Section IV finally introduces our real-time monitoring method, computing a crash probability at each new user action, based on hierarchical clustering. Different configurations are tested.

Formalism

Data

In our application, a user session, which will be our reference measurement, corresponds to one patient images analysis by a physician. In other words, each session contains all the necessary mouse clicks to the radiologist to provide relevant medical recommendation to one patient. The sequence of user actions during this session is chronologically recorded in log files.

The dataset we used to test our both methods contains 5598 user sessions of variable lengths (minimal length of 3) and were obtained from identical hardware systems during a two-week radiology congress. 97 of them were prematurely interrupted by a software crash, that is, a crash rate amounting to 1.73%.

These crash sessions are characterized by a high variability in their sequences of actions and no obvious crash signature can be easily identified, making their characterization and prediction a difficult task. Figure 1 shows for each length of crash session, the total number of crash sessions (dark blue) and the number of different crash sequences (light blue). As can be seen, all the crash sessions being longer than or equal to 8 actions are different.

Moreover, regulations in medical applications impose many privacy restrictions regarding patient data, thus making the retrieval of this type of data even more difficult. Indeed, confidential data protection requires relatively complex and time-consuming procedures to ensure that the recovery process of log files is completely secure and that they provide no critical information.

The user mouse clicks recorded in log files actually refer to the corresponding function calls from the software source code. Therefore, the successive actions appear in the log files as strings of different lengths. To facilitate computations and analysis, we introduce a formal language to normalize actions representation into strings of the same length.

Formal Language and Definitions

Let Σ be an alphabet, that is to say a finite set of symbols, and D the dictionary assigning one user action to a symbol of Σ. Let X be a session of N actions, it will thus be represented as a word on the alphabet Σ, that is to say a finite sequence of N symbols in Σ, X = x 1 x 2 ...x N .

Let X be such sequence and consider a set of K symbols in Σ, Ω = {α 1 , α 2 , . . . , α K }. We will define below different types of inclusion relationships of the set of symbols Ω into the sequence X. It will prove useful to extract the significant actions (in terms of probable cause of crashes) from the sequence of actions. Notations:

1. We will denote:

{α 1 , α 2 , . . . , α K } ⊂ X if for all 1 ≤ k ≤ K, α k ∈ X - {α 1 , α 2 , . . . , α k-1 }.
It simply implies that all symbols in Ω belong to X, irrespective of the order. If α i = α j = α with i = j, and Ω ⊂ X, then it means that α appears twice in X.

2. We will denote:

α 1 α 2 . . . α K ⊂ X if there exists i such that: α 1 α 2 . . . α K = x i x i+1 . . . x i+K-1
, that is to say that X contains the exact sequence α 1 α 2 . . . α K .

3. Finally, we will denote

[α 1 α 2 . . . α K ] W ⊂ X if there exists i, i 1 , i 2 , . . . , i K-1 , with i k < W for all 1 ≤ k ≤ K -1, such that: α 1 α 2 . . . α K = x i x i+i1 x i+i1+i2 . . . x i+i1+i2+•••+i K-1 .
Here, it means that X contains the sequence α 1 α 2 . . . α K , but the consecutive terms α i , α i+1 may be separated by up to W -2 symbols. For example, if

X = α 1 ββα 2 , [α 1 , α 2 ] 4 ⊂ X.
W is the maximal length of the "window" containing the symbols of interest.

In practice, considering the number of potential actions in the medical software of interest in this study, we choose without loss of generality to work with symbols composed of three letters, Σ = {< < <, > > >, aaa, aba, ..., zzz}.

The symbol < < < stands for the beginning of a session, thus for all sessions x 1 =< < <. Likewise, > > > stands for a clean exit of the software application, that is to say the end of a session without crash. All the other symbols represent actions.

With these notations we can easily distinguish normal sessions from crashes: a session of length N is a normal session when x N => > >, while if x N => > >, it is a crash. The set of normal sessions will be denoted S while C will represent the the set of crash sessions.

Beside, we will denote by Q T the queue of length T of a session, corresponding to the T last symbols of a session different from > > >.

Finally, for a finite set Ω, |Ω| will denote its cardinal.

Detection of Sequences of Actions with High Crash Probability

This section is dedicated to the detection of actions or sequences of actions which may cause the crash of a session with a high probability. For this purpose, we propose representations largely inspired by methods developed for information retrieval in text document. A review of the main graph-based representations of document is given in [START_REF] Blanco | Graph-based term weighting for information retrieval[END_REF].

We will first compute the frequency of actions or groups of actions in crashes, with the underlying assumption that each action is independent from the others, as in the traditional bag-of-words model [START_REF] Sculley | Relaxed online svms for spam filtering[END_REF]. We will then use two graphbased representations, with elementary actions as graph nodes. The first one represents the sequences of actions as paths [START_REF] Eirinaki | Web path recommendations based on page ranking and markov models[END_REF], the second one relies on the graph-of-words representation principle [START_REF] Rousseau | Graph-of-word and tw-idf: new approach to ad hoc ir[END_REF]. This last formalism allows capturing dependencies between actions while not being affected by potential transparent actions.

The computation of crash probability will remain the same in each of the following approaches, being simply equal to the number of times the studied actions or sequences of actions occur in crash sessions divided by the number of occurrences of these actions in both normal and crash sessions.

The three proposed representations will be described below. They will be illustrated on the specific case of the identification of couples of actions.

Representation 1 -Independent Actions

The first method consists in calculating the crash probability given a set of K independent actions {α 1 , α 2 ,. . . , α K } in a user session X, as follows:

P Crash ({α 1 , α 2 , ..., α K }) := P (X ∈ C | {α 1 , α 2 , . . . , α K } ⊂ X) = |C α1,α2,...,α K | |C α1,α2,...,α K | + |S α1,α2,...,α K | Where: • C α1,α2,...,α K denotes {X ∈ C | {α 1 , α 2 , . . . , α K } ⊂ X} and thus |C α1,α2,...,α K |
is the number of crash sessions containing simultaneously all the symbols in {α 1 , α 2 , . . . , α K }.

Likewise: This representation does not take into account the connection between the different actions. This is probably not relevant, especially in the case of long user sessions. Indeed, the combination of actions occurring at the beginning and at the end of the session have probably no real interaction, contrary to actions occurring close to each other. This representation does not allow the distinction between the two cases.

• S α1,α2,...,α K denotes {X ∈ S |

Representation 2 -Graph-of-Actions

We propose a graph-based representation in which the dependence between user actions is captured via paths in the graph. We construct a directed and weighted graph from all the user sessions available in our database. Each directed edge uv will represent an occurrence of the sequence composed of the action u followed by the action v. We will use bidimensional weights, corresponding to (|C uv | , |S uv |) where: Each session will be successively added to the graph with the following process: the whole session is browsed, making an edge from every pair of successive actions. If the edge already exists, the bidimensional weight of the respective edge is updated, otherwise a new edge is created [START_REF] Eirinaki | Web path recommendations based on page ranking and markov models[END_REF]. Edge occurrences in crash sessions will be distinguished from edge occurrences in normal sessions. The final graph vertices will represent all elementary actions available in the dataset. The principle of transformation of one user session into a path is illustrated in Figure 2.

• C uv := {X ∈ C | uv ⊂ X}
This representation enables to capture proximity and order between actions. The aim is then to detect in the final graph, patterns or sequences of actions, which may lead to a high probability of crash. When we consider the detection of an ordered pair of actions, this problem simply corresponds to the computation of the crash probability per edge with the bidimensional weights as follows:

P Crash (uv) = |C uv | |C uv | + |S uv |
For sequences of length strictly greater than 2, the method is less direct since it is the probability of the path itself which needs to be computed and it can become very greedy from a computational point of view.

Representation 3 -Graph-of-Actions with Sliding Window

As there is a high variability in the sequences of actions leading to crash sessions, we make the assumption that there exist transparent actions in the sequences with no impact on crashes even if they appear in these sessions. To take this phenomenon into account, we take advantage of an idea proposed in [START_REF] Rousseau | Graph-of-word and tw-idf: new approach to ad hoc ir[END_REF] for graph-of-words in which they need to cope with meaningless words, in a situation very similar to our transparent actions.

The principle of construction of the graph is the same as in the previous method, except that one action will be linked by an edge to the W -1 next following actions in the sequence, W being the length of the sliding window used to browse the user sessions. The Figure 3 shows an example of the construction principle with a sliding window of length equal to 3, meaning that each action will be directly linked to the first following action but also to the second one. These soft links enable to bypass eventual non influential actions that might skew the previous probability computations. The computation of the crash probability per edge thus adapts accordingly:

P Crash ([uv] W ) = C [uv] W C [uv] W + S [uv] W

Performance Evaluation

We test the different representations on the dataset introduced in Section 2.1.

The aim is to detect pairs of actions having a high probability to cause a session crash, but also which occur several times, giving this way more weight and more significance to the results. The Table 1 provides for each method the number of detected couples of actions having a crash probability of 1 (N ) and the number of times these couples occurred in crashes (O). Only the couples that occurred at least twice in crashes are recorded in the table. The first method, Independent Actions enables to highlight 13 couples of actions, each of these couples occurred only twice and systematically the session in which they appeared ended with a crash. However, the very low number of occurrences prevents any significant analysis. In practice, the couple of actions thus determined did not help in understanding the causes of the crashes.

The second method, Graph-of-Actions, provides better results. 10 couples of actions among the 13 couples outlined by the first method are also detected, but also occurring only twice. More interestingly, 2 additional couples are detected, one also occurring twice, but the other one occurring 9 times, which clearly becomes significant. Taking into account the dependence between action clearly improves the capacity of detection. The couple of actions when occurring independently appear more often in normal sessions, and consequently their associated crash probability is reduced with the first mode of representation. The third method, Graph-of-Actions with Sliding Window enables to further improve the results: 7 couples occurring 3 times are detected. In addition, two other couples occurring respectively 4 and 6 times are detected. Finally, a pair of ordered actions leading 24 times to a crash is identified.

A crucial result is that the best detected pairs with the second and the third method, in bold in Table 4, actually correspond to the same couple of actions. This result provides precious information on the signature of the related crash. Let us note this couple {α, β}, representing the succession of actions α and β in a user workflow. The second method shows that this combination when occurring, is systematically leading to a crash, it happened 9 times in this dataset. The third method, reveals that in 15 additional cases, the combination αγβ leads to a crash, γ being a non influential action.

For our specific application, two remarkable results were thus obtained: first, there is an impact of the combination of dependent actions to cause session crashes, and second there exist actions that are non-influential in terms of session crash and can be inserted in sequences of dependent (influential) actions without interfering. The representation of the sequences of actions as a graph with soft links obtained from a sliding window as in [START_REF] Rousseau | Graph-of-word and tw-idf: new approach to ad hoc ir[END_REF] seems a proper description of the software sessions for this purpose. A direct consequence was the identification of some significant crash signatures on our dataset, thus providing keys to the application developers to understand and solve the crash causes.

Beside this crash characterization, it would be particularly useful if we could provide a way to anticipate crash risks, in order for example to save automat-ically the session, notify the user or force a clean exit of the application. The next session will propose such method, monitoring the crash risk resulting from the sequence of actions.

Real-Time Monitoring

Principle

The principle of our method is to use hierarchical clustering to define groups of sessions from our training dataset based on some similarity measure and to compute crash probabilities for the resulting clusters from the observations. Afterwards, during a working session, a crash probability is computed at each new user action based on the session assignment to the predefined clusters. Should this probability exceed a predetermined threshold, the current working session would be automatically saved and the user notified. The proposed method is largely inspired by [START_REF] Portnoy | Intrusion detection with unlabeled data using clustering[END_REF], the main difference lies in the fact that we dispose of labeled sessions. We are thus able to compute a crash probability per cluster during the training step.

Hierarchical Session Clustering

To perform hierarchical clustering, three specifications have to be chosen:

• The metric that will be used to compute distances between observations,

• The linkage method,

• The dendrogram cutting height, determining the number of resulting clusters.

Each of these specifications will be detailed below and different configurations will be compared in the test section.

Metric

We make the assumption that crashes occur at the end of the sessions and we will cluster only the queues Q T of the sessions (last T symbols of the session).

To group the queues of the sessions into clusters, we need to compute a distance between the sequences of symbols contained in the queues. Considering our research problem and the remaining uncertainties, we have tested two existing measures of dissimilarity between strings (Hamming and Levenshtein) and a third metric that we have proposed (Intersection). These three measures are defined below, note that we will work with sequences of the same length.

• Hamming: the number of positions at which the corresponding symbols differ [START_REF] Hofmeyr | Intrusion detection using sequences of system calls[END_REF].

• Levenshtein: the minimum number of edition operations (insertions, deletions, substitutions) to transform one sequence of symbols into the other [START_REF] Scherbina | Clustering of web sessions using levenshtein metric[END_REF], [START_REF] Ristad | Learning string-edit distance[END_REF].

• Intersection: the difference between the length of the studied sequences and the number of common symbols between both sequences.

Each of these metrics provides more or less flexibility regarding the position and the dependence of the user actions in the sequences. The Hamming measure imposes the strongest constraints in terms of similarity while the Intersection measure is the most permissive.

Linkage Method

Hierarchical clustering merges at each construction step the closest pair of clusters. Let G and H represent two clusters and d ii the pairwise observation dissimilarities between an element i in cluster G and an element i in cluster H. We recall the three classical main linkage methods to compute the dissimilarity d(G, H) between G and H [START_REF] Hastie | The Elements of Statistical Learning[END_REF].

• Single linkage: d Single (G, H) = min i∈G,i ∈H d ii
• Average linkage:

d Average (G, H) = 1 N G N H i∈G i ∈H d ii
Where N G and N H are the respective number of observations in each group.

• Complete linkage:

d Complete (G, H) = max i∈G,i ∈H d ii

Number of Clusters

Rather than computing the optimal number of clusters for each dendrogram, we have chosen to empirically determine the best cutting height for our problem.

Crash Probability per Cluster

For a given cutting height H of the dendrogram, we obtain K H different clusters Ω i of session queues, for 1 = i = K H . Each cluster Ω i is partitioned into C i , corresponding to the crash sessions, and S i , for the normal sessions. The crash probability will be computed for each of these clusters, as follows:

P Crash (Ω i ) = |C i | |C i | + |S i |

Crash Probability at each New User Action

The aim is then to go through an unlabeled session, crash or normal session, using a sliding window of length T , the same length as the clustered queues. At each step or each new user action, we will be able to assign the current session to a cluster and then derive a crash probability to the sequence contained in the sliding window based on the previous clustering. An example of the described process is given in Figure 4, using a sliding window of size 4.

At each new user action, a crash probability is computed for the sequence contained in the sliding window (corresponding to the last T actions of the current session). However, the corresponding sequence of T actions might be assigned to several clusters. These potential clusters may have different crash probabilities. Thus, we will consider the 3 following possibilities to assign the crash probability to the current session queue:

• MinimumProba: the smallest crash probability of all the potential clusters to which the sequence contained in the sliding window might be assigned.

• MaximumProba: the highest crash probability of all the potential clusters to which the sequence contained in the sliding window might be assigned.

• AverageProba: the average crash probability over all the potential clusters to which the sequence contained in the sliding window might be assigned.

Performance Evaluation

Crash Detection Threshold and Criteria

Let τ be the detection threshold, we list below the chosen classification criteria: • An actual crash will be considered as detected if the crash probability value (Minimum, Maximum and Average will be tested) is above τ at least at one position of the sliding window during the whole monitoring of the user session.

• An actual normal session will be classified as a normal session if the crash probability value (Minimum, Maximum and Average will be tested) never exceeds τ .

Confusion Matrix

Given our binary problem, there are four possible outcomes (see Table 2):

• True Negative: an actual normal session which is predicted as normal.

• True Positive: an actual crash which is predicted as a crash.

• False Negative: an actual crash which is not detected.

• False Positive: an actual normal session which is detected as a crash.

Performance Metrics

Since we are in the case of highly imbalanced classes (around 2% of the sessions ended by a crash), we will use Specificity (also known as the True Negative Rate) and the Sensitivity (also known as the True Positive Rate), both defined below, to evaluate our method. Indeed, unlike the accuracy, these metrics do no depend on class distributions [START_REF] Fawcett | An introduction to roc analysis[END_REF].

• Specif icity = T N T N +F P

• Sensitivity = T P T P +F N

Results

Data Set Description

From the original dataset, we extract 1750 user sessions of length greater than or equal to 7, containing 33 crashes. The sessions were randomly split into a training set (80%), for the computation of the reference clusters, and a testing set (20%) composed of sessions on which we will test our method. As explained previously, three specifications have to be chosen for the hierarchical clustering (the metric, the linkage method and the cutting height) and two additional specifications relative to our method have to be defined (the length of the clustered queues and the probability score). All the possible configurations for each of these five specifications (described in Table 3) were tested, providing 216 different configurations of the type {M e}_{L}_{Q T }_{T M }_{P }.

Note that we decided to set the crash detection threshold to 0.2 to first determine the most promising configurations. Further work consists in varying this threshold value to build associated ROC curve. This representation will enable us to determine a threshold and a configuration providing the best tradeoff between specificity and sensitivity given our initial problem.

Best Configurations Obtained

The best configurations we obtained are listed in the Table 4. Four of them, printed in bold, outperform the others. Three of them, marked with an asterisk (*), are very similar. Their specificities and sensitivities are both above 0.80. The fourth one, marked with two asterisks (**) only provides a sensitivity of 0.77, however it ensures a specificity value of 0.91. From the user perspective, this configuration is probably the best compromise between the true negative rate and the true positive rate, avoiding too many false alerts and still detecting 77% of the crashes.

Concerning the best specifications, the Levenshtein metric, an intermediate dissimilarity measure in terms of flexibility between Hamming and Intersection, appears in two of the four best configurations. The most appropriate linkage strategies seem to be the average and the complete linkage methods. The clustering of the queues of length equal to 6 and a cutting height of 2 provided the best performances, such as the choice of the minimum crash probability when assigning the sequence contained in the sliding window to a cluster. The ROC curves were computed for the 4 best configurations (see Figure 5). Although the configuration (**) we initially identified as the most relevant one does not provide the largest area under curve, it is still the one that best fits our application needs: indeed, the proportion of crashes is very low (around 2 %), which means that having a high proportion of "false positive" predictions would end up in interrupting normal sessions far too often. Moreover, this configuration provides even better results with a detection threshold lowered to 0.125, increasing this way its sensitivity to 0.79 while maintaining a specificity of 0.91.

Conclusion

In this paper we proposed two methods. The first one aims at identifying the combination of actions with high probability to provoke crashes. The different representations tested for this purpose allowed us to conclude that there is an impact of the combination of successive actions to make sessions crash. Moreover, we showed that non-influential actions could be inserted in these sequences of dependent actions without interfering in the probability of session crash and should thus be handled with in order to identify the proper crash signatures, otherwise we would miss the connection between the influential actions. Graphs with soft links to represent sequences of actions seem a proper description of the software user sessions for this purpose. Further work in this direction will concern the detection of longer paths.

The second method, real-time crash monitoring, provided promising results. Indeed we detected clustering configurations ensuring a specificity of 91% while still detecting 79% of the crashes. Another perspective of this work might be replacing the clustering of the session queues by the clustering of their graphbased representations based for example on the graph edit distance [START_REF] Cao | Measuring similarity between graphs based on the levenshtein distance[END_REF].

For both proposed approaches, we insisted on the methodology rather than on the exploitation of the outcomes. Indeed, a deeper analysis of the high crash probability couples detected in terms of software functions should be performed on a larger database of user sessions. This also applies for the determination of the optimal configuration in the case of the crash monitoring method based on clustering. However, it is important to note that data recovery can be quite complicated due to the regulations applied to medical devices.

Figure 1 :

 1 Figure 1: Number of different crash sessions per length.

  is the set of crash sessions containing the edge uv and |C uv | is their number, • S uv := {X ∈ S | uv ⊂ X} is the set of normal sessions containing the edge uv and |S uv | is their number.

Figure 2 :

 2 Figure 2: Graph construction from the example sequence of actions on the left side.

Figure 3 :

 3 Figure 3: Graph construction with a sliding windows of length 3 from the example sequence of actions on the left side.

Table 1 :

 1 Detection of couples systematically leading to a session crash and occurring more than twice Number of couples N Occurrences O

Figure 4 :

 4 Figure 4: Real-Time Monitoring example on a user session

Figure 5 :

 5 Figure 5: ROC curves for the 4 best configurations obtained.

Table 2

 2

		: Confusion Matrix
		Predicted Negative Predicted Positive
	Actual Negative	TN	FP
	Actual Positive	FN	TP

Table 3 :

 3 Tested values of the specifications

	Specifications	Tested Values
	Metric	M e = {Hamming, Levenshtein, Intersection}
	Linkage Method	L = {Single, Average, Complete}
	Queues Length (Q T )	T = {3, 4, 5, 6}
	Cutting Height (D M )	M = {2, 3}
	Probability Score	P = {Minimum, Average, Maximum}
	Detection Threshold	τ = 0.2
	4.6.2 Tested Configurations

Table 4 :

 4

	Real-Time Monitoring Best Configurations
	Configurations	Specificity Sensitivity
	HAM_COMPLETE_Q6D3_MIN	0.80	0.79
	HAM_COMPLETE_Q6D2_MIN	0.84	0.82
	HAM_AVERAGE_Q6D3_MIN	0.76	0.81
	HAM_AVERAGE_Q6D2_MIN*	0.83	0.87
	HAM_AVERAGE_Q6D2_AVE	0.77	0.89
	HAM_AVERAGE_Q5D2_MIN	0.80	0.81
	HAM_AVERAGE_Q5D2_AVE	0.75	0.82
	INT_AVERAGE_Q6D2_MIN**	0.91	0.77
	INT_AVERAGE_Q6D2_AVE	0.84	0.81
	LEV_COMPLETE_Q6D2_MIN*	0.86	0.84
	LEV_COMPLETE_Q6D2_AVE	0.73	0.84
	LEV_AVERAGE_Q6D3_MIN	0.80	0.79
	LEV_AVERAGE_Q6D2_MIN*	0.84	0.89
	LEV_AVERAGE_Q6D2_AVE	0.78	0.89
	LEV_AVERAGE_Q5D2_MIN	0.80	0.79
	LEV_AVERAGE_Q5D2_AVE	0.73	0.81
	4.6.4 ROC Curves

Acknowledgment

We would like to thank the reviewers for their useful feed-backs which helped us to improve the article clarity.


Erik Tjong

Kim Sang

Improving Part-of-Speech Tagging of Historical Text by First Translating to Modern Text

We explore the task of automatically assigning syntactic tags (known as part-of-speech tags) like Noun and Verb to words in seventeenth-century Dutch text. Tools exist for performing this task for modern texts but they perform poorly on historical texts because of language changes. We test several methods for translating the words in the historical text to modern equivalents before applying the tag assignment tools. We show that this additional translation step improves the quality of the automatic syntactic analysis. Further improvements are possible when the lexicons and text collections used for developing the translation process, are extended in size.

Introduction

Nederlab1 [START_REF] Brugman | Nederlab: Towards a Single Portal and Research Environment for Diachronic Dutch Text Corpora[END_REF] is a large-scale effort to provide to the research community digital versions of texts of the past millennium that are written in Dutch. In order to enable various types of linguistic and historical research, the project aims at providing linguistic annotations with the text. Because of the large volumes of text that are involved, most of the annotations will be generated by automatic tools. Most of the present tools have been built to process twentieth century newspaper text. Since the language Dutch has changed considerably in the last centuries [START_REF] Van Der Sijs | Chronologisch woordenboek: De ouderdom en herkomst van onze woorden en betekenissen[END_REF], the tools perform poorly on historical texts.

There are two ways to improve the quality of automatic linguistic annotation. One is to retrain the tools on historical texts [START_REF] Rem | Tagging and Lemmatization Manual for the corpus van Reenen-Mulder and the Adelheid 1.0 Tagger-Lemmatizer[END_REF]. However, this requires that gold standard training data are created for all relevant linguistic annotation tasks and for all relevant time periods: an enormous task. The second method relies on translating the historical texts to a modern variant which can then be processed by the available language processing tools. The expected quality of the annotations will be somewhat lower than of the special purpose tools but the gold standard annotation requirements for this approach are more manageable.

In this paper, we explore the preprocessing method of text translation with the goal of improving the quality of linguistic annotation tools on processing historical text. We focus on one language (Dutch), one time period (the seventeenth century) and one annotation task (assigning syntactic part-of-speech tag to words). We examine four different methods for translating the texts and present a comparison of their effects on tagging quality.

A good quality of the syntactic analysis of texts is important for being able to find specific words in texts. For example, if a linguist or a historian wants to know which historical texts use the verb ship, correct syntactic annotation will speed up the search process tremendously. When texts have no syntactic annotation, the researcher must examine many irrelevant documents before finding the ones that he or she needs. The same is true when the syntactic annotations contain errors, when noun versions of the search word are often incorrectly annotated as verb. And when verb occurrences of ship have mistakenly been annotated as noun, these will not be found by a search process looking for ship tagged as verb.

The text translations produced in our work, can be used for other purposes than improving syntactic annotation. However, for us they serve only this purpose. We will not use the translations for replacing the original texts. The translations may also not be what people expect of them. Translation is a difficult process to automate. For example, the Dutch historical word beroert has several equivalents in modern language, like touched, hit and sick. For our purposes, it is not important that the translation process finds the word with correct meaning, but only that the syntactic class of the translation is the same as the one of the historical word (in this case: adjective).

After this introduction, we discuss related work in section two. In section three we describe the four methods we have used for translating historical text to modern Dutch. Section four presents the evaluation results of these approaches for part-of-speech tagging. In section five we conclude.

Related work

The field of domain adaptation [START_REF] Plank | Domain Adaptation for Parsing[END_REF][START_REF] Jiang | A literature survey on domain adaptation of statistical classifiers[END_REF] deals with the problem of applying and improving language tools for text types they have not been developed for. Such adaptations are not only necessary for texts written in older variants of languages but also for texts from different genres, as McClosky et al. [START_REF] Mcclosky | Automatic domain adaptation for parsing[END_REF] shows, with a 30% performance drop for a parser processing text from an out-of-training-domain topic. Recently there have also been attempts to create tools that perform well in different text domains [START_REF] Schnabel | Flors: Fast and simple domain adaptation for partof-speech tagging[END_REF].

Archer et al. [START_REF] Archer | Guidelines for normising Early Modern English corpora: Decisions and justifications[END_REF] developed VARD (VARiant Detector), a tool which can be used to convert historical texts to a modern version with standardized spelling, which can then be processed by language tools trained on modern text. The tool has been applied to Early Modern English [START_REF] Schneider | Parsing Early and Late Modern English corpora[END_REF] and to seventeenth-century Dutch [START_REF] Wijckmans | [END_REF]. Hupkes and Bod [START_REF] Hupkes | POS-tagging of Historical Dutch[END_REF] explored semi-supervised learning for tagging historical Dutch texts. Reynaert [START_REF] Reynaert | Text-Induced Spelling Correction[END_REF] developed TiCCl, a tool for normalizing Dutch texts by performing automatic spelling correction. The program Adelheid has specifically been developed for lemmatizing and tagging fourteenth-century Dutch [START_REF] Rem | Tagging and Lemmatization Manual for the corpus van Reenen-Mulder and the Adelheid 1.0 Tagger-Lemmatizer[END_REF].

Het eerste Capittel. translation: Het eerste hoofdstuk. 'De Mensch, het edel dier, by Godes hant geschapen. translation: 'De Mens, het edel dier, door Gods hand geschapen. Was, om in stage jeught, sijn lust te mogen rapen; translation: Was, om in stage jeugd, zijn lust te mogen rapen; Was in het schoon prieel: en waer hy immer ging, translation: Was in het mooie prieel: en waar hij steeds ging. Daer was hy aengesien als heer van alle ding: translation: Daar werd hij gezien als heer van alle dingen: Hy vont een schoon gesicht alwaer de boomen groeyden, translation: Hij vond een mooi uitzicht waar de bomen groeiden, Hy vont een soet geluyt alwaer de beken vloeyden, translation: Hij vond een zoet geluid waar de beken vloeiden, Fig. 1. Example of seventeenth-century Dutch: the first seven lines of the book Schat der Gesontheyt by Johan van Beverwijck, edition 1663 with their translation to modern Dutch (italic characters preceded by translation:) [START_REF] Koomen | Van Beverwijck, Schat der Gesontheyt[END_REF]. The historical Dutch is similar enough to modern Dutch to be understood by speakers of contemporary Dutch but different enough to cause problems for processing by language tools. Social media messages suffer from the same variety in spelling as historical texts. Techniques used for converting such messages to standardized spelling [START_REF] Han | Lexical normalisation of short text messages: Makn sens a# twitter[END_REF][START_REF] Kaufmann | Syntactic normalization of twitter messages[END_REF], can also be applied to text from centuries ago.

Translation methods

We examine four different methods for translating seventeenth-century Dutch to modern Dutch. An example of the translation task can be found in Figure 1. The two language variants are quite similar but the differences are large enough to create problems for language processing tools.

Machine translation

Converting seventeenth-century Dutch to modern Dutch is similar to translating one language to another. General machine translation systems have been developed exactly for this purpose. In order to get an idea of the performance of these systems, we applied a state-of-the-art general purpose machine translation system to this task: Moses [START_REF] Koehn | MOSES -Statistical Machine Translation System -User Manual and Code Guide[END_REF]. We trained Moses with two versions of the Dutch bible Statenvertaling, one from the year 1637 [START_REF]Biblia, dat is De gantsche H. Schrifture (Statenvertaling 1637)[END_REF] and one from 1888 [START_REF]Statenvertaling Jongbloededitie 1888. Statenvertaling[END_REF]. After the training phase, Moses required extra data for the the tuning phase. For this purpose, we used the first chapter of the book Schat der Gesontheyt by Johan van Beverwijck from 1663 and its translation to contemporary Dutch [START_REF] Koomen | Van Beverwijck, Schat der Gesontheyt[END_REF].

We tested the quality of the translation system by applying it to the first 100 lines of the second chapter of the book by Van Beverwijck. We used BLEU [START_REF] Papineni | BLEU: a method for Automatic Evaluation of Machine Translation[END_REF] Historical [START_REF]Statenvertaling Jongbloededitie 1888. Statenvertaling[END_REF] is mentioned between brackets. The lemmas chosen as best modern variant for the historical words are shown in bold face: either the modern lemma which is identical to the historical word (like the pair de-de) or the modern lemma with the highest bible frequency if no identical variant is available (like the pair hy-hij).

as evaluation metric. The translation made by Moses achieved a BLEU score of 0.283 when compared with the gold standard translation by Koomen [START_REF] Koomen | Van Beverwijck, Schat der Gesontheyt[END_REF]. We did not know how to interpret this number, so we performed an additional manual translation of the text and compared it with the gold standard. The manual translation obtained a BLEU score of 0.345 while the original text from 1663 was assigned a BLEU score of 0.124. These two scores can be seen as upper and lower bound for the machine translation performances on the test text. The BLEU score achieved by Moses was closer to the upper bound than to the lower bound. In fact, we later found out that no other automatic method evaluated by us achieved a better BLUE score than Moses on the test texts (see Table 1). Moses requires a large number of computer resources, taking about one hour to start at our machine (Mac mini, 2.3 Ghz, 4Gb). Furthermore, during translation Moses sometimes inserts or deletes words. While this may be the best option for achieving good translations, it complicates the task of linking annotations of modern words back to the original historical words. Therefore we looked for alternative translation methods, that required fewer computational resources and preserved the word positions.

Historical lexicons

The Dutch Institute for Lexicography (INL) offers the Integrated Language Bank (GTB) [7], an online collection of historical dictionaries, with links of historical words to their modern counterparts [8]. The lexicon service makes it possible to retrieve modern lemmas for historical words. As a test, we retrieved the modern lemmas for the words that occurred five times or more in the Dutch Statenvertaling bible version of 1637 [START_REF]Biblia, dat is De gantsche H. Schrifture (Statenvertaling 1637)[END_REF]. This resulted in a list of 8,563 words. About 20% of these words were not found in the lexicon, most of these were proper nouns (names). These words were left untranslated. Some of the words had several alternative lemmas assigned to them, see Figure 2. If this was the case, we chose the modern lemma which was equal to the historical word, if one was present among the alternatives, and otherwise we chose the lemma which was most frequent in the modern (1888) version of the Statenvertaling bible [START_REF]Statenvertaling Jongbloededitie 1888. Statenvertaling[END_REF]. All together 3,948 words (46%) were mapped to themselves. Translating the test text, the first 100 lines of the second chapter of Schat der Gesontheyt (1663) by Johan van Beverwijck [START_REF] Koomen | Van Beverwijck, Schat der Gesontheyt[END_REF], with the 8,563-word lexicon resulted in a text with a BLEU score of 0.191, better than the baseline of 0.124 but worse than the score of Moses (0.283, see Table 1). However, it should be taken into account that the fact that this method produces lemmas rather than words as present in the gold standard translation, negatively influences its BLUE score.

Extracting lexicons from parallel text

The translation lexicon used in the previous section links historical words to modern lemmas. The lemmas can be used to determine coarse part-of-speech tags like noun and verb. However, finer distinctions like plural versus singular cannot be derived from the lemmas because the required morphological clues have been lost in the translations process. We do not have parallel word-toword translation lexicons available but we do have a large parallel text from which such a lexicon could be derived. For this purpose, we examined K-vec, a method for extracting lexicons from unaligned text, put forward by Fung and Church [START_REF] Fung | K-vec: A New Approach for Aligning Parallel Texts[END_REF]. It divides the text and its translation in K parts of approximately equal size and constructs binary word vectors of length K which state in which parts of the original text or the translated text the word is present. Translated words are likely to appear in the related contexts and thus have similar vectors. We used the Dutch Statenvertaling bible versions of the years 1637 [START_REF]Biblia, dat is De gantsche H. Schrifture (Statenvertaling 1637)[END_REF] and 1888 [START_REF]Statenvertaling Jongbloededitie 1888. Statenvertaling[END_REF] as a training corpus. The texts were sentence-aligned so we could use sentences as parts. There were 37,100 sentences in the corpus and from these Kvec identified 16,201 word translation pairs. With the resulting parallel lexicon, we generated a word-by-word translation of the test text Schat der Gesondheyt [START_REF] Koomen | Van Beverwijck, Schat der Gesontheyt[END_REF]. The translated text proved to be better than the baseline: BLEU score 0.219 compared to 0.124 (see Table 1).

Orthographic rules

In the evolution of Dutch over the past centuries, changed spelling of words often could be expressed in orthographic rules. Some examples of this can be found in the text in Figure 1: groeyden became groeiden and vloeyden became vloeiden. The orthographic rule y⇒i could have been used here to generate the modern variant from the historical variant but the context could also have played a role. In order to find reliable orthographic rules, we collected all sequences of one, two and three characters from words in the 16,201-word learned lexicon from the previous section as well as their possible corresponding translations. We restricted the word pairs to those where the translation had the same number of characters as the historical word (8,724 word pairs), where the translation was one character shorter [START_REF] Brugman | Nederlab: Towards a Single Portal and Research Environment for Diachronic Dutch Text Corpora[END_REF]969) or where the translation was one character longer (682). Two additional characters were added to each word: a start-ofword character at the beginning and an end-of-word character at the end so that specific rules dealing with the start and the end of a word could be expressed [START_REF] Kim | Machine Learning of Phonotactics[END_REF]. We collected all non-identical pairs of character strings which occurred at least ten times in the learned lexicon and in which the historical part corresponded with the same translated part in at least ninety percent of the cases. This resulted 86 rules of pairs of the same length, four rules which removed a single character and no rules that added a character (see Figure 3). When the 90 rules were applied to the test text Schat der Gesontheyt, [START_REF] Koomen | Van Beverwijck, Schat der Gesontheyt[END_REF] it resulted in a translation with a BLEU score of 0.160. This is the lowest score of the four evaluated translation methods. However, the rule set was able to improve both the learned lexicon output (from 0.219 to 0.229) and that of the historical lexicon (from 0.191 to 0.198) when combined with these methods as a post-processor.

Part-of-speech tagging evaluation

In order to evaluate the performance effect of the four translation methods discussed in the previous section, on part-of-speech (POS) tagging, we needed gold standard seventeenth-century POS tagged text. Hupkes [START_REF] Hupkes | POS-tagging of Historical Dutch[END_REF] supplied us with the two texts she used for evaluating her seventeenth-century POS tagger: a selection of the shipping logbook Journael ofte gedenckwaerdige beschrijvinge from the year 1646 by Willem IJsbrantsz Bontekoe (1565 tokens) and a selection of the Dutch bible Statenvertaling from the year 1637 (1370 tokens). The texts were annotated with POS tags according to the CGN format [START_REF] Van Eynde | Part of Speech Tagging and Lemmatizing of the Corpus Gesproken Nederlands (Spoken Dutch Corpus)[END_REF]. Only coarse tags were used which means that the tags expressed the differences between POS classes like verb, adjective and noun, but not the subtle distinctions within these classes, like plural versus singular or past versus present tense.

For tagging the texts, we used Frog [START_REF] Van Den Bosch | An efficient memorybased morphosyntactic tagger and parser for Dutch[END_REF], a state-of-the-art POS tagger for modern Dutch. The tagger assigns fine-grained POS tags to words. Only the coarse-grained parts of these tags have been used for evaluation. It would have been useful to see which words the tagger did not know: we could then have focused the translation process on these words. Unfortunately, the tagger did not report which words were unknown. Frog did report a tag confidence score for each word but it was not possible to derive from this if the input word was known or not.

Before the evaluation of the four translation methods, we tested three alternative part-of-speech tagging approaches. First, we tagged the two seventeenthcentury texts with the modern tagger without any text modification. This resulted in accuracy scores of 68.2% for the Bontekoe text and 63.7% for the Statenvertaling text. Clearly there is much room for improvement as Frog is reported to achieve an accuracy of 98.6% on this task for modern text [START_REF] Van Den Bosch | An efficient memorybased morphosyntactic tagger and parser for Dutch[END_REF].

In order to assess the upper performance ceiling of the translation approaches, we tagged manually created word-by-word translations of the two texts. This time we achieved accuracy scores of 88.8% for the Bontekoe text and 91.2% for the Statenvertaling text. The latter score shows that the translation approach is potentially as strong as retraining a tagger: Hupkes and Bod [START_REF] Hupkes | POS-tagging of Historical Dutch[END_REF] reported that their retrained POS tagger achieves accuracies of 84% on the Bontekoe text and 92% on the Statenvertaling texts. Although human translation is expensive and infeasible for the corpus sizes we aim to process, it is an option we consider for smaller texts for which high quality POS tags are required.

As a third alternative method, we evaluated the performance of the Adelheid tagger [START_REF] Rem | Tagging and Lemmatization Manual for the corpus van Reenen-Mulder and the Adelheid 1.0 Tagger-Lemmatizer[END_REF], a tagger which was specifically trained for processing Middle Dutch (1200-1500). Adelheid does not use the CGN tag set but it was possible to convert its output tags to the CGN format. Adelheid performed slightly better than the baseline for the Bontekoe text (71.4% compared to 68.2%) and a lot better for the Statenvertaling text (82.9% compared to 63.7%). It is unclear what is causing this performance difference.

Next, we processed the Bontekoe text with three of the four translation methods and sent the results to the Frog parser. The machine translation system Moses was not used for translation because it does not preserve the word order of the original text and we had no automatic method for linking the POS tags back to the original words. The Statenvertaling text was not used for this part of the evaluation. All four methods have used the Statenvertaling in one way or another in their development phase and therefore evaluation scores on this text would be unreasonably high.

The POS accuracies of the three methods can be found in Table 1. The translations produced with the historical lexicon proved to be as useful for POS tagging (82.0%) as the translation produced with the learned lexicon (82.1%). This shows that translating to lemmas rather than to words is a valid approach for improving the quality of assigning coarse-grained POS tags. For fine-grained POS tags, lemmas will be insufficient since the morphological clues required for such tags are lost in the translation process. The orthographic rules performed considerably worse than the two lexicon methods (73.4%). Like in the tests in section 3.4, they improved the BLUE scores of the lexicon methods when combined with them as a post-processor. However the associated POS accuracy scores did not improve (82.0% and 81.9%, respectively). While the two lexicon-based translation methods offer a considerable increase in POS tagging accuracy, there is still some room for improvement in comparison with the manual translation. One way of achieving further improvement would be use a larger historic lexicon or a larger parallel corpus for deriving the learned lexicon. We estimated the effects of these steps by evaluating the performance of smaller historical lexicons and a smaller parallel corpus. The smaller corpora were chosen by selecting the first 10, 100, 1000 and 10,000 sentences of the Statenvertaling bible. The smaller historical lexicons were produced by choosing the first 10, 100 and 1000 words of the words of the Statenvertaling bible sorted by decreasing frequency.

The evaluation scores are summarized in the graphs in Figure 4. The performance of the historical lexicon reaches 82% for 8,563 words (left graph). The shape of the graph suggest that increase of the lexicon size to about 60,000 would lead to a performance increase of 4%. A similar performance increase could be obtained by increasing the training text for the learned lexicon from the current 37,100 words to about 140,000 words (right graph). It will require a considerable effort to create such a large relevant sentence aligned corpus. However, the Institute of Dutch Lexicography already has compiled a historical lexicon of the required size, so there lies an interesting opportunity for further improving the quality of this approach. Estimated from these graphs, a historical lexicon of about 60,000 words and a parallel corpus of about 140,000 words would both lead to an increase in POS tagging accuracy from 82% to 86% (dashed lines).

Concluding remarks

We explored methods for improving the performance of natural language processing tools on texts written in a historical version of a language. Since the tools have been developed for processing contemporary language and languages may change considerably over time, the performance of the tools on century-old texts is usually poor. Our proposed solution is not to rebuild the tools but to translate the texts to a modern-language variety so that then they can be processed by any available tool. We found that in order for this approach to work for the task of part-ofspeech tagging, it is important that the translation was done word by word. This made it hard to employ general machine translation software for this task because it optimizes text quality by inserting, deleting and reordering words in the translated text. This makes it difficult to link annotations assigned to the modern language words back to the original historical equivalents.

Instead, we have evaluated three word-by-word translation methods for improving the quality of coarse-grained part-of-speech tag assignment to seventeenth-century Dutch text. The first was based on an online historical word to modern lemma lexicon. The second used on a lexicon that was learned from two versions of a Dutch bible, one from the seventeenth century and one from the nineteenth century. The third method employed orthographic rules learned from the learned lexicon. The rules converted historical character sequences to their modern equivalent.

We found that the two lexicon-based method performed equally well, 82% POS accuracy, where the baseline was 68% and a human translation reached 89% (see Table 1). An important difference between the two methods is that the historical lexicon method translates words to lemmas, thus eliminating the possibility of accurately assigning fine-grained POS tags. The learned lexicon does not have this disadvantage. The orthographic rules performed worse than the two lexicon methods (73%) but they remain interesting as a possible postprocessing method applied to the output of the lexicon methods.

The performance of the two lexicon-based methods is dependent on the size of the historical lexicon and the size of the parallel training texts. Based on performances with smaller lexicons and smaller training texts, we have estimated that a seven-fold increase of the size of the historical lexicon and a four-fold increase of the training corpus would both lead to a 4% improvement of POS accuracy, thus overcoming a large part of the remaining gap with the performance of human translation.

Our future work plans are all connected to extending the training and evaluation data. The available historical lexicons for Dutch are larger than the material used in this paper and we would like examine the effect of the larger lexicons on part-of-speech tagging accuracy. This study has focused on tagging texts from the seventeenth century and it would be interesting to apply these methods to other natural language processing tasks and to material of other time periods. This requires more historical material with gold standard annotation. Fortunately, today more of such data are becoming available (for example [START_REF] Rutten | Letters as Loot. A sociolinguistic approach to seventeenth-and eighteenth-century Dutch[END_REF]).

Fig. 4 .

 4 Fig.[START_REF] Fung | K-vec: A New Approach for Aligning Parallel Texts[END_REF]. POS accuracies for different lexicon sizes of the historical lexicon (left, solid line) and different corpus sizes of the learned lexicon (right, solid line). Estimated from these graphs, a historical lexicon of about 60,000 words and a parallel corpus of about 140,000 words would both lead to an increase in POS tagging accuracy from 82% to 86% (dashed lines).

  Fig. 2. Modern lemmas of seventeenth-century Dutch words, provided by the Lexicon Service of the Dutch Institute for Lexicography [8]. The number of times each lemma occurs in a modern bible version

	variant Lemmas
	ende en (57642) einde (318) eend (0)
	de de (41141) doen (1658)
	van van (22251) vinden (160)
	het het (21009) hebben (3018)
	den de (41141) den (11521)
	in en (57642) in (14785)
	hy hij (9498) hei (0)
	die die (11676)
	dat die (11676) dat (9629)
	tot tot (10878) totten (0)

Table 1 .

 1 Evaluation scores for the three alternative approaches and the four translation methods. Part-of-speech (POS) tagging accuracies concern base tags only. No POS scores are available for the machine translation method because of the difficulty of linking POS tags from its output back to the original words. The Statenvertaling was used as training material for the translation methods and therefore these methods have not been evaluated on those data.

		Gesontheyt	Bontekoe	Statenvertaling
	Method \ Measure	BLEU	POS accuracy POS accuracy
	Modern tagger	0.124	68.2%	63.7%
	Historical tagger	0.124	71.4%	82.9%
	Manual translation	0.345	88.8%	91.2%
	Machine translation	0.283	NA
	Historical lexicon	0.191	82.0%
	Learned lexicon	0.219	82.1%
	Orthographic rules	0.160	73.4%

nederlab.nl