2 Related work

The problem of syntactic error detection and correction has been addressed since the early years of natural language processing. For the treatment of the significant amount of errors that result in valid words (Heidorn et al. Reference Heidorn, Jensen, Miller, Byrd and Chodorow1982; Weischedel and Sondheimer Reference Weischedel and Sondheimer1983) different techniques have been proposed:

• • Grammar-based techniques that use the results of a parser as input. Two kinds of parsers can be used for this purpose:

  • – Parsers based on manually developed grammars that describe correct structures. Special methods have been devised for error detection: chart-based methods (Min and Wilson Reference Min and Wilson1998), relaxation of syntactic constraints (Douglas and Dale Reference Douglas and Dale1992) or edit-distance methods (Gusfield Reference Gusfield1997).

  • – Statistical parsers can analyse any sentence, but they do not easily distinguish correct and incorrect sentences, although they can make a probabilistic approximation of grammaticality (Wagner and Foster Reference Wagner and Foster2009).

• • Error patterns (Kukich Reference Kukich1992; Golding and Schabes Reference Golding, Schabes, Joshi and Palmer1996; Mangu and Brill Reference Mangu and Brill1997), which are either hand-coded rules or automatically learned ones. Most of these approaches use finite-state techniques, for example the Constraint Grammar (CG) formalism (Karlsson et al. Reference Karlsson, Voutilainen, Heikkila and Anttila1995) is used in Arppe (Reference Arppe2000), Birn (Reference Birn2000), and Badia et al. (Reference Badia, Gil, Quixal and Valentín2004) for error detection in Swedish and Catalan, or the Xerox Finite State Tool (xfst; Karttunen et al. Reference Karttunen, Gaál and Kempe1997) for finding grammar errors in Swedish texts written by children (Hashemi, Cooper and Andersson Reference Hashemi, Cooper and Andersson2003).

Kukich (Reference Kukich1992) surveyed the state of the art in syntactic error detection. She estimates that between 25% and over 50% of the total errors in written texts are in fact valid words. On the other hand, Atwell and Elliot (Reference Atwell, Elliot, Garside, Sampson and Leech1987) made a manual study concluding that 55% of these errors are detectable examining the local syntactic context, 18% are due to global syntactic errors (involving long-distance syntactic dependencies, which need a full parse of the sentence), and 27% are semantic errors. Since then, new technologies have extended the possibilities of other types of texts, such as e-mails or chats, where the chance of finding errors increases considerably, and so does the applicability of error detection systems (Foster Reference Foster2010).

Errors in date expressions can be deemed as representative of local syntactic errors. A similar work to the one presented here is that ofKarttunen (Reference Karttunen2006), which describes a system that maps numbers to numerals in Finnish. Finnish has in common with Basque the inflection of linguistic structures, and agreement in case of some of their components that makes the transduction process more complex than in languages like English, with a simpler morphology. Constant (2009) gives a similar account of a finite-state grammar describing measurement phrases in French.

Recognisers for date expressions are used as a part of the task of Named Entity Recognition (ner; Friburger and Maurel Reference Friburger and Maurel2004; Traboulsi Reference Traboulsi2009). However, these applications either do not take the problem of incorrect dates into account or otherwise they define a loose description of dates that covers incorrect dates as well.

Regarding the treatment of Basque date expressions, Gojenola and Oronoz (Reference Gojenola and Oronoz2000) present a system that detects errors using a unification based partial parser. This work extends that system using a finite state approach instead of unification, with a more comprehensive set of error types and including also the task of error correction.

There are several general-purpose libraries for the creation of transducers. While some of them are proprietary software, such as xfst (Karttunen et al. Reference Karttunen, Gaál and Kempe1997), there are also alternatives based on free software, like Nooj (http://www.nooj4nlp.net/NooJManual.pdf, based on intex (Gross Reference Gross1997)) or Foma (Hulden Reference Hulden2009b). xfst is the result of long-term research at the Xerox Palo Alto Research Center since the early 1980s. Foma is a free software tool to specify finite-state automata and transducers in a similar fashion to at&t's FSM Library (Mohri, Pereira and Riley Reference Mohri, Pereira and Riley2000), xfst and the sfst toolkit (Schmid Reference Schmid, Yli-Jyrä, Karttunen and Karhumäki2005). One of Foma's main design goals was its compatibility with xfst. In an earlier experiment in Machine Translation transfer (transferring verb chains), we evaluated the Nooj-fsa tool, concluding that it was less time-efficient than xfst and Foma. This is the reason why we selected them for this work.

The problem of using either a positive or a negative approach is a well studied problem (Laporte Reference Laporte1998) whose practical consequences are still not settled. We will evaluate both methods in the context of syntactic error detection and correction.

3 Linguistic resources

For the analysis of the input text we use the Basque shallow syntactic analyser (see Figure 1), based mainly on finite-state technology (Aduriz et al. Reference Aduriz, Aldezabal, Alegria, Arriola, Díaz de Ilarraza, Ezeiza and Gojenola2003). The recognition of errors in date expressions only needs morphosyntactic information (lemma, POS category and features like syntactic case and number).

Fig. 1.

Morphosyntactic analysis and disambiguation.

Figure 1 shows the morphosyntactic analyser together with the modules in charge of disambiguation. The process starts with the output of the morphosyntactic analyser (morfeus), which was created following the two-level morphology (Koskenniemi Reference Koskenniemi1983), and deals with all the lexical units of a text, both simple words and multi-word units. The tagger/lemmatiser eustagger obtains the lemma, category and morphosyntactic features of each form and also performs disambiguation using information on part of speech, fine-grained part of speech or case. The disambiguation process is carried out by means of linguistic rules using CG and stochastic rules based on Hidden Markov Models (Ezeiza Reference Ezeiza2002), which reduces the high word-level ambiguity to a limited amount of interpretations per wordform.

All the information in the analysis chain is exchanged by means of standardised xml files (Artola et al. Reference Artola, Díaz de Ilarraza, Soroa and Sologaistoa2009). The full system provides a robust basis, essential not only for any NLP treatment based on corpora, but also for error detection.

4 The error grammar approach

The process for error detection and correction starts after analysing the input text. The system (see Figure 2) is composed of two groups of fsts: (i) for error detection (see Section 4.1) and (ii) for the generation of correct dates (see Section 4.2). Let us consider the date expression ‘1995eko maiatzaren 15’ (15th of May, 1995). It is incorrectly written because in Basque the day number after a month in genitive case must take a case marker. The process will go through the following modules:

1. (1) ‘From xml to xfst’ filter. This preprocessing filter (a C++ program) changes the morphosyntactic information to the format suitable for the fsts. The text labelled (1) in Figure 2 shows the result of the analysis represented by means of feature structures that gather the lemma and morphosyntactic information of the incorrect date example, including pos, fpos (fine-grained part of speech), case, num (number) and mug (definite/indefinite article). The text labelled (2) in Figure 2 represents the corresponding simplified format¹ needed for the next step.

2. (2) fsts for date error detection. We have sequentially applied nine finite-state transducers, one for each kind of error defined (see Table 1), creating a cascade of fsts. The beginning and end of the incorrect linguistic structures are marked by means of tags describing each type of error. The text labelled (3) in Figure 2 shows how the incorrect structure is surrounded by two error tags (beginerror4 and enderror4). Figure 5 presents the set of transducers defined to detect the error number four (in Table 1).

3. (3) ‘To numbers’ FST. Once the errors in date expressions are tagged (it is frequent to find more than one error in each date expression), the correction process starts. The ‘To numbers’ FST obtains a numbered expression with the format ‘YYYY/MM/DD’ for each date expression tagged with an error. The ‘To numbers’ transducer is very simple because it only has to match the numbers corresponding to the year and the day and translate the name of the months to the corresponding number.

4. (4) fsts for date generation. The correction module uses fsts that change numbers representing date expressions to their corresponding full-text equivalences. The text numbered (5) in Figure 2 shows two correction candidates for correcting the example. There are two standard forms (with variants) for Basque date expressions, and the input date is corrected to one of them. In this respect, this process could better be defined as normalisation instead of correction. Figure 6 presents the set of transducers defined for date generation.

Fig. 2.

General architecture of the system.

4.1 Error detection

Inflection in date expressions is a common source of errors, not detectable by a spelling checker. Figure 3 shows one of the formats of a valid date expression.

Fig. 3.

Format of a valid date expression.

After a preliminary study, we chose the most frequent error types (see Table 1). Errors 0, 3, 4, 5 and 6 are idiosyncratic errors of date expressions, while errors 1, 2, 7 and 8 can be considered general errors that can be found in other contexts. A group of error detection patterns has been defined for each of the error types, and after compiling them, a cascade of fsts is applied to the input text.

The error pattern rules were devised considering that several mistakes could co-occur. As a result, we designed error patterns bearing in mind not only the correct expression, but also its erroneous versions. This strategy had associated the risk of increasing the number of false alarms. This means that when writing rules for the detection of one kind of error, we took the transducers for correct dates as a basis, but we had to relax these definitions for correct dates, so that other kinds of date errors could also have co-occurred together with the currently treated error. This softening on what can be considered a correct date has the problem of marking as erroneous text units that do not correspond to dates (for example, expressions containing case-marked months and years but not corresponding to a date). As a consequence, error detecting rules were considerably more complex when adapting them to the possible co-occurrence of other errors. For example, Figure 5 shows the error detecting rules for the fourth kind of error, where the rules take both correct and possibly incorrect definitions of years and months. As the interactions among errors grow considerably with the number of errors, we based our error patterns on the combinations actually found in the corpus, so that in practice that number can be considerably reduced.

Figure 5 shows the error pattern for the fourth kind of error: the day number after a month in genitive case must have a case mark. We have used the fst operators presented in Figure 4. Rules 1--4 define regular expressions describing years and months in both their correct and incorrect variants. Rules number 5 and 6 define two regular expressions describing a year (Year) and a month (Month) (both the correct and incorrect variants are defined, using the disjunction ( | ) operator). This way, the error-description patterns will consider the possibility that other error patterns co-occur. The error pattern is defined in rule 7 (a month (Month) followed by a non inflected number), and named Err_Type4. Finally, rule 8 describes a transducer (Mark_Err4) that uses the longest-match left-to-right replace operator (@->), to surround the incorrect pattern by two error tags (beginerror4 and enderror4). To further restrict the application of the rule, the left context for the error (Year) is defined, to assure that the rule is only applied to dates, thus avoiding false alarms.

Fig. 4.

List of the main fst operators.

Fig. 5.

Regular expressions and relations for an error pattern.

4.2 Error correction

For correction we took a group of already defined two-tape transducers that was created to map numbers representing date, time and number expressions to text (Otaegi Reference Otaegi2006), and adapted a subset of them in order to correct date expressions.

According to The Royal Academy of the Basque Language, the most appropriate ways to express a date are those in which the locative (place name) and the declension of the day agree in absolutive or inessive cases (in the text labelled (5) in Figure 2 the first date expression agrees in absolutive and the second one in inessive), so we decided that the system should create date expressions in this format.

An fst has been used for each of the cases. These transducers, however, do not create the word indicating the location and the comma after it, but an fst is used to generate the locative in inessive case, using morphological generation by means of lexc (Beesley and Karttunen Reference Beesley and Karttunen2003). The comma is generated after checking that a proper name indicating a locative (LocPn in Figure 2) precedes the date.

The process of creating a full-text date is simple. Let us explain the rules for specifying the fst that generates dates in inessive case (see Figure 6). The input comes in the format: year/month/day. Rule number 1 replaces the slash after the year number (using the conditional replacement operator ->) by a genitive locative² morpheme (‘-ko’). Months are mapped from numbers to text (actually, we make use of multi-character symbols such as ‘maiatzaren’) by means of replacement operators that are restricted to the date context (rule 2 shows an example). Rule 3 composes transducers of different months by means of the composition operator (.o.). Finally, the inessive singular morpheme (‘-an’) is added to the day (Translate_Day, rule number 4). There are several exceptions to these mappings: when the year or day number finishes in a consonant, an epenthetic ‘-e’ is added to the genitive locative case in the year (‘-e’ + ‘-ko’ = ‘-eko’), and to the inessive case (‘-e’ + ‘an’ = ‘-ean’) in the day (Add_E_Day, rule number 6). The last two rules compose the defined transducers.

Fig. 6.

Regular relations for date generation.

This method, based on the generation of correct date expressions, guarantees the correction of all the errors in the expression even if not all of them were detected. For example, if only two errors out of three are detected, all of them are properly corrected.

5 An alternative: a recognition-based method

A simpler, more general, and also less-labour-intensive alternative than developing incorrect date error patterns, is to develop a simpler fst for date identification and to use edit-distance based techniques to detect errors. In this case the type of error will not be identified (the diagnosis capability of the system is lost) but simple errors will be detected and corrected. For this purpose we have used an fst based on the ideas from Karttunen (Reference Karttunen2006) which can identify correct dates obtained from the low-side language in a transducer that converts dates from number to text. So, we will use the lower-side of a number-to-text transducer. The simplified grammar of this date recogniser is shown in Figure 7. The grammar follows the syntax already presented in the previous figures, so we have explained it by means of comments. The grammar accepts expressions such as Donostia, 2010eko apirilaren 10a.

Fig. 7.

Regular relations for date identification.

Related to agreement in the inessive case (the ‘n’ suffix appearing in error number 0 in Table 1) two rules have been designed in order to constrain its correctness. If the suffix appears attached to the place name, it should also appear attached to the day. Figure 8 shows one of the rules, which forbids the second ‘n’ (day) if it is not linked to a corresponding ‘n’ attached to the place name.

Fig. 8.

Enforcing case agreement.

For identification and correction of errors we can use the med (minimum edit distance) option in the Foma compiler (Hulden Reference Hulden2009a, Reference Hulden2009b). The med option applies a fast algorithm for finding approximate matches of a string in a finite-state automaton (which can also be seen as an identity transducer), given some metric of similarity. The algorithm can be adapted to use a variety of metrics to determine the distance between two words. Without any parameter, the same cost is assigned to all the possible variations (deletion, insertion and substitution), but a matrix can be defined when different costs are assigned.

For example, in the matrix in Figure 9, a lower cost (1 against 2 for the general changes) is assigned to the changes corresponding to errors 0, 1, 2, 3 and 8 in Table 1. The change corresponding to the 7th error type can not be included because the character (hyphen) is not in the defined language.

Fig. 9.

Matrix for defining the minimum edit-distance costs.

The three first lines in Figure 9 express that general insertions, substitutions and deletions have a cost of two. The other two lines define a cost of one for well-known errors. Each of these errors is specified by a pair of characters separated by a colon. Additions are represented by pairs without the left character, and deletions by pairs without the right character. Looking at the last line, we can distinguish:

• • 6 substitutions. The last six pairs specify substitutions among lower-case and upper-case.

• • 3 additions. ‘:n,’ ‘:e’ and ‘:a’ specify the addition of ‘n,’ ‘e’ and ‘a'.

• • 4 deletions: ‘n:,’’ ‘,:’, ‘e:’ and ‘a:’; deletion of ‘n’, ‘,’, ‘e’ and ‘a’.

As an example, when analysing the wrong date expression Donostia, 2010eko apirilaren 10 using med it will give as alternative the correct Donostia, 2010eko apirilaren 10a date with a cost of 1. So, using the med option, erroneous dates can be identified and corrected. The med-cutoff option can limit the cost terminating a search. Based on the matrix in Figure 9 with the med-cutoff parameter set to 3, expressions with a single change (insertion, deletion or substitution) and a special change (one of the lower cost) will be corrected. For example in Donostia, 2010eko apirillaren 10 there are two errors, the deletion of the a (cost 1) and one general insertion (apirilaren → apirillaren) (cost 2). Depending on the value of these parameters, different trade-offs for precision/recall/time can be obtained.

6 Evaluation

The evaluation corpus (development + test, see Table 2) is composed of 267 essays written by students (with a high proportion of errors) and texts from newspapers and magazines, more than 500,000 words altogether. Out of them we chose 658 sentences, including correct dates, incorrect dates and also structures similar to dates. Compared to other kinds of errors, it was relatively easy to obtain test data because date expressions contain several cues (month names, year numbers) that help in the process of semiautomatically finding test sentences.

Table 2.

Test data

The corpus was compiled with the double objective of both finding errors and also testing false alarms (see Table 2), that is, correct dates or sentences similar to dates that could be flagged as erroneous. The problem of false alarms is one of the biggest challenges we must face when dealing with unrestricted texts. As a result of the selection procedure, the proportion of errors was higher than in normal texts. Therefore, we divided our data into two groups. One of them was used for development and we left the second one for the final test. The proportion of correct dates was higher in the case of test data than in the development corpus, so that the effect of false alarms could be evaluated with more accuracy.

6.1 Error grammar

Table 3 shows the results. As the development corpus could be inspected during the refinement of the patterns, the results in the number of detected and undetected errors in the development corpus can be understood as an upper limit of the system in its current state, with 95.9% recall³ and 100% precision⁴ (93 error proposals).

Table 3.

Evaluation results (error pattern grammar)

The system obtains 92.1% recall over the corpus of previously unseen 247 test items. Regarding precision the system correctly detects 35 errors. If the false alarms are divided by the number of test items (1/247) of the test corpus, we can estimate the false alarm rate to be around 0.4% over the number of dates in real texts. Figure 10 shows the unique false alarm and its cause.

Fig. 10.

False alarm. The unknown word Primakov is interpreted as locative.

The correction guarantees that all the errors in dates are corrected even when some of them could not be detected. That is, even when a sentence contains more than one error, once one is detected, it is transformed to its corresponding number format and, as the correct date is generated, all the errors are corrected.

6.2 Positive grammar

The recognition of date errors using a general, positive fst gives competitive results when compared to the first method. Correct dates are recognised correctly and, in the case of incorrect dates, the main difference is that it is not possible to give a diagnosis. Nevertheless, and similarly to the system based on error patterns, most of the errors are identified and the corresponding right spelling proposed.

After doing different tests on the development corpus the med cutoff value was set to 4, resulting in a good trade-off between coverage and precision. In addition to this, bigger values would significantly slow the correction process.

The only difference between the two systems is that there are five undetected date errors (compared to three with the specific error transducer presented in Section 3). All the rest of the incorrect dates are identified and corrected. The number of false alarms on the test data is the same (one false alarm) as in the previous approach.

Table 4 gives a measure of the complexity of the nine transducers for the errors in Table 1, in terms of their number of states and transitions. It is worth noting that the error-marking transducers mark both the beginning and end of the error, which considerably increases the size of the corresponding transducer. This can be clearly seen in the table, where the error-marking transducers are sometimes two orders of magnitude bigger than their recognising counterparts. Table 5 shows that the transducer for error identification and the date-generation transducer are relatively simple compared to the size of the error-marking transducers.

Table 4.

Size of the implemented transducers for error detection

Table 5.

Size of the finite state machines for date generation and recognition

Regarding the speed of the transducers, we measured the application of the 9 error detection fsts to 1,000 date expressions, obtaining the result in 41 seconds, that is, 0.041 seconds per expression. This test was made in an Unix machine (1xSPARC64 VII + Quad Core) with a processor of 2.75 GHz and 8 Gigas of RAM memory.

7 Conclusions and future work

This work shows an application of finite state transducers (fst) for syntactic error detection and correction in date expressions. The reported experiment is based on a corpus, and tested on real examples of both correct and incorrect sentences. This approach needs the existence of big corpora and manual annotation.

We have applied two alternative methods and two tools, xfst and Foma, to the task of error detection. As a first method, we have experimented a negative approach, using a set of error patterns. In order to detect several types of errors in the same expression, the error patterns have been written considering the formats for valid sentences as well as their incorrect variants. The results show that regular expressions and relations compiled to automata and transducers are suitable for the definition of complex error patterns based on linguistic units. The second approach was based on the definition of correct dates, and the application of edit-distance techniques to detect errors. As the results have shown (see Section 6) both systems obtain good results in terms of precision/recall, although the first one allows the identification of the error type(s), which can be more explanatory in contexts like an error correction system or a language learning environment. This second approach (see Section 5) can be useful when diagnosis is not necessary and rapid development is an issue. In both methods we are able to obtain the corrections without having to detect all the errors occurring in the ungrammatical date expression.

From our experiments we can conclude that if a diagnosis is not necessary for the checker the second solution is better because it is a less labour-intensive option and because the solution is less dependent on the language. However when a diagnosis is necessary only the first solution is suitable.

We are currently exploring extensions to the system to detect new kinds of errors by combining rule-based error detection and automatic acquisition of error patterns. This could counteract the scaling-up problem associated with the increase in the number of rules, as well as the amount of work involved in the process of hand-coding them. Using either hand-coded rules or automatically learned ones, both methods still pose the problem of obtaining and marking big test corpora. Some experiments with the automatic creation of errors (Sjöbergh and Knutsson Reference Sjöbergh and Knutsson2005; Foster and Andersen Reference Foster and Andersen2009) seem to be a possible solution to this bottleneck.

In the future, we plan to extend the error detection system to other qualitatively different types of errors such as those involving for example, determiner-noun agreement errors that could be treated using fsts. Although the number of potential syntactic errors is huge, in our opinion the treatment of the most frequent kinds of errors with high recall and precision can result in useful grammar-checking tools.