Final Report
for the Period from 15 October 1997 to 14 October 2000

Workpackage #4
Partner No. 5		Partner Name: Institute of Computer Science 
   		                         Polish Academy of Sciences
Acronym:	ICS-MM
Title: 	An HPSG treebank for Polish 
Coordinator:	Prof. L. Bolc
Personnel:	6 persons
e-mail	{bolc,aniak,mm,am,adamp}@ipipan.waw.pl
Web site:	http://www.ipipan.waw.pl/~agn/CRIT.htm	

1.  Objectives

The objective of our proposal has been to create a treebank of syntactic structures of Polish sentences using HPSG (Head-driven Phrase Structure Grammar) for encoding such structures.  Such an HPSG-encoded bank of syntactic structures, or treebank, provides sound linguistic grounds for the evaluation and improvement of formal and computational grammars of Polish, including the HPSG grammar developed and implemented at the Polish Academy of Sciences.

The work within this project has been divided into following tasks: 1) preparation of a set of tags representing linguistic phenomena of Polish, 2) development of a set of test data consisting of Polish sentences annotated with linguistic phenomena names and 3) manual annotation of this selected text corpus with HPSG parses. As there exists no system designed specifically for creating and maintaining HPSG treebanks, we have decided to implement our own system.

2. Background

Linguistic Engineering (LE), or Natural Language Processing, as it is often called, is a dynamically developing field of science and engineering, with many refereed journals, conferences and societies.  

One of the subfields of LE is concerned with creation and evaluation of machine-readable language resources, such as text and speech corpora, lexica, speech synthesis and analysis systems, and formal and computational grammars. For such resources to be of maximal benefit to the scientific community, they should be well-documented, re-useable and evaluated. Especially the need for assessment of existing resources has recently been officially recognised, with a separate conference series devoted to this theme, namely, "International Conference on Language Resources and Evaluation" (LREC). According to the organisers of LREC-2000,

The relevance of evaluation for Language Engineering is increasingly recognised. This involves assessment of the state of the art for a given technology, measuring the progress achieved within a programme, comparing different approaches to a given problem and choosing the best solution, knowing its advantages and drawbacks, assessment of the availability of technologies for a given application, product benchmarking, and assessment of user satisfaction.

                                							 http://www.elda.fr/lrec2000.html

Although various language resources have recently been developed for Polish, most notably morphological analysers, lexica, and formal and computational grammars, there has been no attempt at evaluating or comparing these resources. The aim of this project has been to partially fill this gap.

The formalism used for annotation is Head-driven Phrase Structure Grammar (HPSG).  Although, in the last fifteen years, many methods of describing natural language utterances have been developed, few of them are both widely used and linguistically sound. One of them HPSG, which has extensively been used as a base for theoretical research, as well as a host formalism for many computational applications. This wide acceptance of HPSG is due to the fact that it allows for relatively easy description of various linguistic phenomena and that these descriptions are relatively easily implementable. Unlike some other similar frameworks, the HPSG formalism also has sound logical foundations.

As mentioned above, HPSG is currently one of the leading linguistic formalisms used both in theoretical and in application-oriented research projects.  HPSG grammars have been developed for a number of languages. A large body of research was done for English (mainly in the USA, but also in many other countries), German (Saabruecken, Tuebingen, Stuttgart, Berlin, etc., in cooperation with American research institutions such as Stanford University, Ohio State University or Carnegie-Mellon University) and French (Paris, Lille, Geneve, Stanford). There has also been systematic work on Italian, Spanish, Japanese, Korean, Turkish and various other languages. Among the most important projects involving HPSG grammars are: 
1)	Verbmobil – a large automatic speech-to-speech translation project with partners in Germany, USA and Japan; 
2)	Head-driven Phrase Structure Grammar (theoretical foundations of the formalism based on cross-linguistic generalisations) and English Resource Grammar (computational grammar of English) projects in Stanford, CSLI, USA; 
3)	Phrase Structure Grammar for French (HPSG grammar of French) sponsored by a CNRS-NSF grant.

Recently, the interest in modern language technologies has also been driven to Slavic languages (Czech and Bulgarian so far) and HPSG-based grammars have been used in LaTeSlav (Language Processing Technologies for Slavic Languages), a European Union joint research project. The contribution of Polish is thus a natural extension of this thread of research. The use of a uniform linguistic platform for diverse languages gives the advantage of simplifying potential integration with grammars of other languages.

3. Technical description 

The aim of this project has been to create a treebank of Polish sentences which could be used as a test suite, for assessing the empirical coverage of formal and computational grammars of Polish, and for evaluating the informativeness of parses produced by such grammars. The treebank contains both grammatical and ungrammatical sentences, allowing to assess to what extent grammars undergenerate (do not parse grammatical sentences) and to what extent they overgenerate (incorrectly recognise ungrammatical sentences as grammatical sentences of Polish).  Moreover, each grammatical sentence in the treebank is extensively annotated with syntactic and morphosyntactic information about this sentence (its constituent structure, syntactic categories of particular words, etc.).
The work in this project has been divided into following tasks:
First, we have elaborated the set of linguistic phenomena characteristic for Polish.  The idea of a stable set of linguistic phenomena was based on the solution devised in the European Union TNLP project (Lehnam et al. 1996; Oepen et al. 1998). The project has investigated various aspects of the construction, maintenance and application of systematic test suites as diagnostic and evaluation tools for NLP systems. Starting from the general idea of describing a language by means of linguistic phenomena, a specific set of such phenomena for Polish has been defined.

Next, we have prepared the test data, i.e., a set of constructions (sentences) illustrating all linguistic phenomena devised in the first task.  Sentences included in our test suite are elicited instead of, e.g., being extracted from a text corpus. This allows us to represent in the test suite also less common phenomena which rarely occur in real corpora, and to reduce the number of lexical entries used in examples. The aim of this task has been to obtain a representative sample of the language.

Third, we have created a computational tool for entering, maintaining and displaying the test data together with their annotations.  This tool is underlyingly a database, with a Graphical User Interface facilitating various operations on the data and making it possible to display the data in a variety of formats.

The final task has been to manually annotate the test data prepared in task two, using the tool developed in task three.  In particular, a linguistically motivated set of syntactic parses has been assigned to the test data, using HPSG as the underlying linguistic formalism.

References
Lehman, S., Oepen, S., Regnier-Prost, S., Netter, K., Lux, V., Klein, J., Falkedal, K., Fouvry, F., Estival, D., Dauphin, E., Compagnion, H., Baur, J., Balkan, L. and Arnold, D. (1996). TSNLP – test suites for natural language processing. In Proceedings of COLING 1996, Kopenhagen.
Oepen, S., Netter, K., and Klein, J. (1998) TSNLP — test suites for natural language processing. In J. Nerbonne, editor, Linguistic Databases, CSLI Lecture Notes. CSLI Publications, Stanford.

4. Achievements 

We have developed an extensive classification of phenomena representative for Polish, which has been used for the construction and annotation of the test data (Marciniak, Mykowiecka, Kupść and Węgiel, 2000).

In the project, we distinguish nine main groups of phenomena. Each of these groups is subdivided into more specific phenomena of various levels of specificity, thus forming a hierarchy of linguistic phenomena of Polish. The number of each phenomena group is presented in the following table.   

Phenomena group 	 Number 	
Types of utterances 	    43 	
Verbstypes and forms 	    34 	
Adjectives and Adverbs 	    10 	
Complementation 	    77 	
Modification 	    20 	
Agreement 	    24 	
Coordination 	    20 	
Negation 	    17 	
Word Order 	    19 	
Total 	  264 	

The test suite proper, i.e., a set of Polish test sentences representing the whole spectrum of linguistic phenomena has been developed and the sentences have been annotated with the names of the phenomena that they illustrate (or violate, in case of ungrammatical sentences).  This annotated test suite constitutes the core of the treebank and it has been made available on the web (Marciniak, 2000).

Sentences contained in the database are divided into several groups on the basis of their grammaticality and complexity. Each group is labeled with a name of ‘correctness marker’. These markers are defined and entered during the initialization of the database. We assumed two-step classification consisting of 6 markers. The main classification divides sentences into correct and incorrect. In the second step we partition both correct and incorrect sentences into three subgroups: basic constructions, complex constructions and very complex or peripheral constructions. The number of sentences labeled with each correctness and complexity marker is presented in the following table.

Marker 	  Number 	
correct–basic 	 116 	
correct–complex 	   68 	
correct–peripheral 	     9 	
                                        Subtotal 	 193 	
incorrect–basic 	   83 	
incorrect–complex 	   58 	
incorrect–peripheral 	     6 	
                                        Subtotal 	 147 	
Total 	 340 	

We have also designed and implemented a computational tool for entering, storing and maintaining HPSG structures (Bartkowski, 2000; Marciniak, Mykowiecka, Kupść and Przepiórkowski, 1999, 2000). This system, called BRG (Baza Rozbiorów Gramatycznych), has been implemented in Delphi (Borland) in the Microsoft Windows NT environment. The system comprises:
•	Conversion of an HPSG signature into relational database description.
There are two text files restricting the content of the database and its interpretation. One of them contains an HPSG signature, i.e., the multiple inheritance hierarchy of types, and names of attributes appropriate for each type, as well as possible values of these attributes. The other file contains the hierarchy of linguistic phenomena of Polish covered by the test suite. 
The HPSG signature is converted into a database description. This signature should be created prior to the creation of the database but some modifications of it are possible also afterwards. 
•	Graphical user interface allowing for the input of the linguistic information and its modification.
The interface facilitates the construction of AVMs by generating their parts semi-automatically. At every stage only a limited number of types is presented to the user. After choosing a type, a list of values of attributes appropriate for this type automatically pops up. Values of attributes must then be filled in manually, in any order. 
•	Dictionary maintenance.
The dictionary is a separate part of the database. It consists of AVM structures of inflectional forms used in sentences contained in the test suite. Each inflectional form is linked to the base form of the word. If the base form of some inflectional form is not present in the dictionary, the user is asked to enter it. 
•	Searching procedures covering both simple queries and queries in a form of regular expressions.
There are several search operations which can be performed over the test suite. In all cases, the search result is a list of sentences together with their parses. It is possible to output search results (sentences with indices) to a file as an ASCII text. 
There are two ways of selecting data from a database. A simple query can consist of one word form, one base form of a word, one phenomena name, one correctness marker or one name of an HPSG type. 
If this simple search mechanism is not sufficient, we can formulate a query being a regular expression combining the equality and non-equality relations over word forms, phenomena names, type names and correctness markers.
•	Output module.
The parses of a sentence can be shown on the screen in two formats simultaneously: as trees and as AVM structures. Sentences and their parses can be also printed in an appropriate size and format (selected attributes can be minimized or hidden).

Many theoretical problems concerning the proper HPSG representation of particular linguistic constructions have been solved. The research concerned the problem of the representation of:
•	clitics (Kupść, 1999a, 1999b), 
•	relative clauses (Mykowiecka 1999a, 1999b), 
•	verbal negation (Przepiórkowski 1999a, 1999b), 
•	case assignment and agreement (Przepiórkowski, 2000a, 2000b),
•	co-ordinated structures (Kupść, Marciniak, Mykowiecka and Przepiórkowski, 1999, 2000).  
The general problems concerning the application of HPSG to Slavic languages have been addressed in Przepiórkowski 2000c.

5.  Concluding remarks and future plans

The test suite developed within this project will be used to evaluate existing computational grammars of Polish, most notably, the HPSG grammar developed at the Polish Academy of Sciences and the syntactic analyser of Polish developed by Bień et al. 1999.

The BRG program can be used for creating other similar test suites (not necessarily for Polish).  We are also planning to re-use it for the educational purpose of teaching the HPSG formalism.

Our involvement in this project has substantially increased our interest in the area of linguistic resources. As a result, we have submitted to the Polish Committee of Scientific Research (KBN) a grant proposal aimed at construction of a large annotated corpus of Polish.  We are also preparing a NATO grant proposal for cooperation with two leading corpus research centres, namely, the University of Tuebingen, Germany, and the Charles University, Prague, the Czech Republic.

Finally, the project has shown both the advantages and the limitations of the annotation schema adopted in the treebank.  While the annotations are exhaustive and conform to international linguistic and computational linguistic standards, the sophistication and sheer size of these annotations have made the manual annotations both time-consuming and error-prone.  Two solutions to this problem that could be explored in the future are: 
1)	making the annotations linguistic-theory-neutral and, at the same time, more rudimentary, and 
2)	extracting relevant grammatical information from sentences automatically, using grammar-induction techniques.  
The disadvantage of solution 1) is that some grammatical information would be lost in annotations which would make evaluation and comparison of grammars less reliable, while the disadvantage of solution 2) is that automatic grammar induction is a relatively new and still developing field.  

References
Bień, J. S., Szafran, K. and Woliński, M. Experimental parsers of Polish. In Proceedings of FDSL3, Leipzig, 1999.

6.  List of Project’s:

6.1 Final deliverables (such as prototypes, developed soft- and hardware tools, etc.):

1. BRG (Baza Rozbiorów Gramatycznych, Database of Syntactic Parses) – a program for creating and maintaining HPSG treebanks.  Implemented in Delphi (Borland) in Microsoft Windows NT environment.  The program is available with Polish and English interfaces.

2. A classification of linguistic phenomena of Polish being a relatively exhaustive list of syntactic constructions which have to be analysed by any formal or computational grammar of Polish

3. A test set of Polish sentences annotated with names of linguistic phenomena illustrated by a particular sentence.

6.2  Publications (published, accepted, submitted)

Kupść, A.: A Syntactic Analysis of Clitic Climbing in Polish, text of a talk delivered at the 6th HPSG Conference, Edinburgh, August 4-6, 1999a. 
Kupść, A., Marciniak, M. and Mykowiecka A.: Constituent Coordination in Polish: An Attempt at an HPSG Account, Proceedings of the General Linguistics in Poland Conference, 13-14 November, Warsaw, 1999, IPI PAN.
 Kupść, A.: An HPSG Account of Clitic Climbing in Polish Verb Clusters, Proceedings of the General Linguistics in Poland Conference, 13-14 November, 1999b.
Kupść, A., Marciniak M., Mykowiecka A., Przepiórkowski, A.:  Składnikowe konstrukcje współrzędne w języku polskim: Próba opisu w HPSG,  IPI PAN Report 914, 2000.
Marciniak, M.: Zestaw zdań testowych wraz z anotacją zjawiskami lingwistycznymi, 2000, http://www.ipipan.waw.pl/~agn/sentences.htm.
Marciniak, M., Mykowiecka, A., Kupść, A., Węgiel, M.: Klasyfikacja zjawisk syntaktycznych na potrzeby testowego zbioru wyrażeń języka polskiego z przykładami jej wykorzystania. IPI PAN Report 908, 2000.
Marciniak M., Mykowiecka A., Przepiórkowski, A. & Kupść A.: An HPSG-Annotated Test Suite for Polish. Proceedings of the Third European Conference on Formal Description of Slavic Languages, 1-3 December 1999, Leipzig (to appear).
Marciniak, M., Mykowiecka, A., Przepiórkowski, A., Kupść, A.: An HPSG-Annotated Test Suite for Polish, Proceedings of  the Linguistic Resources and Evaluation Conference, Athens, 31 May – 2 June 2000.
Mykowiecka, A.: Polish Relative Pronouns – An HPSG Approach, Proceedings of the General Linguictics in Poland Conference, Warsaw, 13-14 November, 1999a.
Mykowiecka, A.: Który vs. kto – Polish Noun-Modifying Relative Clauses, Proceedings of the Formal Description of Slavic Languages Conference, Leipzig, 1-3 December, 1999b (to appear).
Przepiórkowski, A.: Optional and Multiple Long Distance Genetive of Negation in Polish, Proceedings of the General Linguistics in Poland Conference, Warsaw, 13-14 November, 1999a.
Przepiórkowski, A.: A Note on Optional and Multiple Long Distance Genetive of Negation in Polish, Proceedings of the Formal Description of Slavic Languages Conference, Leipzig, 1-3 December, 1999b (to appear)
Przepiórkowski, A.: Predicative Case Agreement with Quantifier Phrases in Polish. Paper presented at the UNC Linguistics Colloquium, University of North Carolina, Chapel Hill, April 8, 2000a.
Przepiórkowski, A.: Case Agreement in Polish Predicates. To appear in S. Franks, L. Gabriele and T. King (eds.), Annual workshop on Formal Approaches to Slavic Linguistics: The Bloomington Meeting 2000. Ann Arbor: Michigan Slavic Publications.  2000b.
Przepiórkowski, A.: Slavic Linguistics Formally.  To appear in G. Fowler (ed.), The future of Slavic linguistics.  Bloomington: Slavica Publishers. 2000c.
Przepiórkowski, A.: Long Distance Genetive of Negation in Polish.  To appear in the Journal of Slavic Linguistics.

6.3  Practical Experiments

Many internal tests of subsequent program versions have been performed.

6.4  Public Demonstrations

Public demonstrations at:
•	Formal Description of Slavic Languages Conference, Leipzig, 1-3 December, 1999,
•	Computational Linguistics in the Netherlands Tenth CLIN Meeting, Utrecht, 10 December 1999,
•	a seminar of the Department of Polish Language, October, 1999, Warsaw University, 
•	the LREC 2000 Conference, Athens, 31 May-2 June 2000.

6.5 Scientific/industrial contacts - dissemination incl. exploitation/technology transfer (when applicable)

The test set of Polish sentences is available under the following address:
http://www.ipipan.waw.pl/~agn/sentences.htm

The BRG program can be obtained on request (agn@ipipan.waw.pl or mm@ipipan.waw.pl).

6.6  Research/professional degrees

One Master of Science thesis is in preparation: 
Wiesław Bartkowski, Komputerowa baza analiz gramatycznych w formalizmie HPSG. Faculty of Mathematics, Informatics and Mechanics, Warsaw University, 2000.

6.7  EU project proposals being prepared/submitted and their status: none

7.  List of participants and national/international collaboration, affiliations (references)

List of participants: 

Prof. Leonard Bolc, Institute of Computer Science, Polish Academy of Sciences.
Wiesław Bartkowski, Faculty of Mathematics, Informatics and Mechanics, Warsaw University.
MSc Anna Kupść, Institute of Computer Science, Polish Academy of Sciences.
MSc Małgorzata Marciniak, Institute of Computer Science, Polish Academy of Sciences.
PhD Agnieszka Mykowiecka, Institute of Computer Science, Polish Academy of Sciences. 
PhD Adam Przepiórkowski, Institute of Computer Science, Polish Academy of Sciences.
Prof. Marek Świdziński, Department of Polish Language, Warsaw University.
PhD Maria Węgiel, Institute of Polish Language, Polish Academy of Sciences.

The project was discussed with:

Prof. Wolfgang Wahlster, DFKI, Saarbruecken.
Prof. Hans Uszkoreit, DFKI, Saarbruecken.
PhD Wojciech Skut, University of Saarbruecken.

8.  Any additional information a workpackage believes to be helpful as reference material