Finite state grammar for finding grammatical errors in Swedish text

Incremental parsing

During this reporting period we have experimented with using incremental parsing in a similar way to that described in Aït-Mokhtar and Chanod (1997) in order to overcome the difficulties with the size of the nets that we were compiling as reported during the last reporting period.  This method has given us greater efficiency and flexibility and has enabled us to go back to the original ideas of using finite-state subtraction which we had given up on in view of the problems we were encountering.  We thus report on two experiments using the incremental parsing idea, the first of which does not use subtraction to find errors and the second of which does. 

In progressing from experiment 1 to experiment 2 we felt the need to organize the incremental parser in a somewhat different way to Aït-Mokhtar and Chanod.  It is very often the case in finite state parsing that the distinction between grammar and parser that is important in other parsing technologies disappears.  We felt that it was important to take a modular approach since a large part of the aim of our attempt to find errors while only writing positive grammar rules (rather than writing grammars for errors) was to be able to reuse finite-state grammars for different  applications.  Our system is now divided into three main modules:  the grammar, the parser, the error-finder.  The grammar is further subdivided into a broad grammar and a narrow grammar of the kind that we have reported on earlier.  The grammars contain regular expressions which reflect truths about the grammatical structure of Swedish.  We are attempting to keep this component as declarative as possible and eliminate from it the kind of heuristics (often depending on order of application of the various transducers) which are standard in robust parsing using finite-state methods.  The parser, on the other hand, contains the nets that mark out the various kinds of constituents and the parsing results vary depending on the order in which the various grammatical facts are applied (in terms of how the various transducers are cascaded).  This, of course, makes the parser have a somewhat different nature than what is standardly called a parser in other parsing technologies.  It is normally assumed that the syntactic anlayses are already defined in the grammar and that the parser should respect these.  
Despite this non-standard view of parsing this separation means in principle that a single finite state grammar could be used with different parsing techniques for different applications, i.e. that it is possible to have a statement of grammatical facts in finite state terms without being committed to a given set of heuristic parsing procedures.  This increases the possibilities for portability and experimentation.  In addition separating out the error-finding module means that the grammar and parser could be used directly in a different application.

Experiment 1

With this first experiment with the incremental parsing technique we left the original idea of subtracting the narrow grammar from the broad grammar. To find grammatical errors in the text we first marked VPs, PPs and NPs with the broad grammar, e.g.:

	<np>en liten bilen</np>

Then by just looking within the markings made by the broad grammar we let the narrow grammar mark agreement, e.g.:

	<np num><np gen><np>en liten bilen</np>

We then calculate that if there is some agreement missing and replace the markings from the narrow grammar with a new marking letting us know what the grammatical error is e.g.:

	<np ungr def>en liten bilen</np>

Experiment 2

In experiment 2 we found that the it was possible to go back to our original idea of using subtraction and that by using our new techniques it was possible to obtain smallish nets representing particular errors.  For example, we can use the regular expression 

["<np>" %  [NP - NPDef]  %  "</np>"]

where NP is the part of the broad grammar characterizing broad NP structure and NPDef is the part of the narrow grammar charactierizing definite NPs to find NPs which violate definiteness constraints within NP-boundaries that have been previously marked out by applying the broad grammar.

Eliminating false alarms

The version of our grammar and error finding that we reported on previously found many false alarms and we conjectured that we would be able to reduce the number of false alarms by increasing the grammatical knowledge of the system.  We know feel that we have found a strategy for doing this which combines both enriched grammatical knowledge and a heuristic parsing strategy.  We parse first from the left margin of phrase to their heads and then subsequently extend phrases by adding on complements that have been found during this first phase.  We have found that by applying the first  phase by looking for higher phrases first (a kind of top-down strategy, e.g. vp pp np and then applying the second phase in the reverse order, e.g. np pp vp) we are able to successfully block the false parses that we getting us into trouble.   It also prevents us from finding some of the errors that we found previously, but we are happier with a conservative approach which maybe finds less errors but which is not plagued with false alarms.

Further development 
Optimization

After having consulted Lauri Karttunen he made us aware of that we could do some optimization on our finite-state networks by using

•	reduce labelset which partitions the label alphabet in a finite-state network into classes and eliminates all arcs that is not labeled by the first symbol of some class and

•	optimize net that tries to reduce the number of arcs, often at the cost of introducing more states.

We also speculate that when having enough information in the tags we can substitute the words in the input text with file positions, which would reduce the label alphabet.

Further grammar development and testing

In  the final phase of the project we are pretty confident that we get beyond the toy grammar size that we currently still have and that while we will not have a particularly useable grammar checker we will have something that demonstrates the feasibility of doing efficient grammar checking without writing rules specifically for ungrammatical constructions.  We will test the grammar against errors we have collected and against the SUC corpus to check for false alarms.

References

Aït-Mokhtar, S. and Chanod, J.-P. (1997) Incremental Finite-State Parsing. In Proceedings of ANLP'97, Washington March 31st to April 3rd, pp 72-79.