\documentclass{llncs}
\usepackage{Latin2}
%\usepackage[czech]{mylabel}
%\input{psfig.sty}
\hyphenation{ana-lyses}
\hyphenation{ana-lyzer}
\hyphenation{com-prising}
\hyphenation{counter-examples}
\begin{document}
\pagestyle{empty}

\mainmatter

\title{The  Linguistic  Basis\\
of  a  Rule-Based  Tagger  of
Czech\thanks{The work described is funded by the
{\it GA\v{C}R} grant No. 405/96/K214.}}
\author{Karel Oliva\inst{1} \and Milena Hn\'atkov\'a\inst{2}
\and Vladimír Petkevi\v{c}\inst{2} \and Pavel Kv\v{e}to\v{n}\inst{2}}
%\authorrunning{Vladimír Petkevi\v{c}}
\institute{Computational Linguistics, University of Saarland,
Saarbr\"{u}cken, Germany
\email{oliva@coli.uni-sb.de}\\
\and
Faculty of
Arts, Charles University, Prague, Czech Republic\\
\email{\{Milena.Hnatkova,Pavel.Kveton,Vladimir.Petkevic\}@ff.cuni.cz}}
\maketitle
\begin{abstract}
This paper describes the conception of a rule-based tagger (part-of-speech
disambiguator) of Czech
currently developed for tagging the {\it Czech
National Corpus} (cf. \cite{cnk}). The input of the tagger
consists of sentences whose words are assigned all possible
morphological analyses. The tagger disambiguates
this input by successive elimination of tags which
are syntactically implausible in the sentential context of the particular
word. Due to this, the tagger promises substantially higher
accuracy than current stochastic taggers for Czech. This
is documented by the results
concerning the disambiguation of the most frequent
ambiguous word form in Czech -- the word {\it se}.
\end{abstract}

\section{Introduction}
An automatic morphological disambiguation
of large textual corpora is  one  of  the  main tasks
in  contemporary corpus  linguistics.
 The majority of corpora are in English and they are morphologically
disambiguated by stochastic taggers with accuracy over 97 \%. Unlike
English, Czech is characterized
by a high degree of free-word  order  and by the
absence of  the abundant usage of  unambiguous "small" words
(articles,   auxiliary  verbs,  etc.).  Hence   in  Czech  a
stochastic tagger, selecting  the most likely
tag for a  word by considering the immediately neighbouring words, makes
often  incorrect choice because it cannot base its
decision  on the  dense  sentence  skeleton induced  by the
fixed word order in combination with frequent occurrences of
functional words (as is the case in English).

On  the  contrary, the decisions of a  rule-based  tagger  (in the spirit of
\cite{karlsson}) can  be based on the entire sentential context and
hence they  can very often profit from the rich inflection of
Czech.

%The paper consists of two major parts:

%\begin{itemize}
%\item assessment  of stochastic disambiguation  of Czech %(Sect. 2)
%\item description of the  rule-based tagger of Czech using
%unrestricted context (Sect.~3) and report of its first results
%and implementation (Sect.~4)
%\end{itemize}

\section{Assessment of the Stochastic Disambiguation of
Czech}
\label{sect:criticism}

%Stochastic  methods of  morphological  and  part-of-speech
%disambiguation  applied  on  Czech  texts  have brought poor
%results so  far.
 The highest correctness rate hitherto achieved by statistical-based
tagging for Czech
 is 93,85 \%  (cf. \cite{hlad2}).  This number is to be understood,
 however, as resulting from
the combination of  performance of the stochastic tagger used {\it and}
the  ambiguity of  the text. As about 66 \% of
the  tokens in the  {\it Czech
National Corpus} are  unambiguous (i.e.  the
tagger has nothing to decide on these tokens), the  actual success rate of
the tagger is in fact about 71 \%.
After careful inspection of  a portion of  stochastically disambiguated
data we  can summarize the main  reasons for such a state of affairs as
follows:

\begin{itemize}
\item stochastic  methods seem to be very  primitive when applied on  a
syntactically complex, free
word-order language  without an abundance in syntactically fixed points
(such as  Czech);
\item  stochastic  taggers  are  dependent  on  the
training data. If they have not "seen" a particular configuration of tags  in
the training  corpus, they cannot  cope with this  configuration
properly.  In  other  words,  stochastic  taggers  model {\it parole} (in
the de Saussurean wording) rather than {\it langue}.  As there are
immense quantities  of distinct complex manifestations of phenomena (esp.
due to their different combinations and word order variants) in any Czech
text, the  modelling of {\it
parole} -- unlike the modelling of {\it langue} --
cannot be adequate. In other words, the source of many problems of
stochastic tagging is its underlying assumption that texts of a  language
can  be viewed as
accidental  sequences  of word forms, an assumption standing in opposition
to the obvious  fact  that
natural  languages  are systems  {\it sui
generis};
\item stochastic  taggers  are dependent  on  the
size and the repertory of tags. This dependency turns to be
fatal: the more fine-grained  input the morphological analysis
provides (i.e. the  more refined information is  contained in  the
tagset), the worse the overall results are. Closely related to this is also
the fact that a stochastic tagger for a flective language has to use a
large tagset (1100+
tags are reported in \cite{haj:hlad}) and hence it should be trained on a
very  large manually
disambiguated corpus (millions of word forms), but creating  such a  corpus
is infeasible in practice;
\item it is very difficult  to localize and fix the sources of errors which a
stochastic  tagger commits (to {\it debug} the tagger); these taggers  are
black  boxes
driven only by data they encountered, and as such they often behave contrary to
expectations. For one instance out of many: in Czech a preposition can never be
followed by a word form in  the nominative case but the most
successful stochastic tagger of  Czech sometimes does disambiguate such a
word  form  as  nominative (though the sequence could not occur in the
training corpus!);
\item stochastic taggers of  Czech do not make use of information about
the structure  of language which  is, however, available  in
the data. For instance, they do not use the systemic phenomenon consisting
in the vocalization of those occurrences of prepositions that are
immediately followed by
word forms beginning with specific consonant clusters.
%\item stochastic tagging characterizes language (represented
%by  the   texts  in  the   corpus  being  processed)   by  a
%stochastically  achieved  success  rate  (given  in %percentage)
%only.
%\item  stochastic  tagging  neglects   the  fact  that  both
%natural  language as  such and  particular languages  of the
%world in particular (Czech  is no exception  here) are %system(s)  {\it sui
%generis}. Unlike  rules  accounting  for  various  patterns %and
%regularities in the system of language, stochastic methods do
%not use relevant insights into the structure of language;
% and they should be treated as such. Czech is, of
%course, also {\it sui
%generis}  but  its  {\it  genus}
\end{itemize}

As a matter of fact, we consider all  these points to  be true
in general, not only in the particular case of Czech -- even though they
get a substantial confirmation on Czech as a test case. The conclusions
which we draw from this are that the morphological disambiguation of
Czech must be performed in such a way that it will have none
of the  above-mentioned drawbacks of currently available
stochastic taggers of Czech, and, fundamentally, that the disambiguation
must be  based on exploiting
as  much linguistic information provided by the system of language  as possible.

\section{General Conception of the Rule-Based Tagger}
\label{sect:conception}

The core idea of the rule-based tagging process is the combination of a morphological
analyzer (lemmatizer) with linguistically-based tag-elimination rules,
which   has   been   presented   for   the   first  time  in
\cite{karlsson}. In particular, the point is that for a language with
rich inflection such as Czech, the morphological analysis of the text
is an indispensable basis of
any    tagging   (even    a   statistics-based    one,   cf.
\cite{haj:hlad}).
To put things clearly, we consider the morphological analysis to be a
process assigning each word form in the text the set of all possible tags
appurtenant to this word form, irrespectively of its environment
(neighbouring words) as well as of the probability
of an occurrence of the
particular form with the particular tag (i.e. word form with its
"morphological meaning") in a real text (as an example of an intuitively
very unrealistic -- i.e. improbable -- meaning, let us take the word form {\it
\v{c}as} as the form of the imperative of the verb {\it \v{c}asiti (se)}). For
this purpose, we use the morphological analyzer and a tagset developed by
Jan Haji\v{c} (cf. \cite{hajic1}, \cite{hajic2}).

In the entire tagging process, the morphological
analysis (i.e. multiple tag assignment) is then followed by tag elimination,
that is, by a set of procedures (rules) trying to narrow down the set of
tags associated (by the morphological analysis) with a particular word form,
ideally achieving the situation in which only the correct tag is associated
with each word of the input. Unlike
morphological analysis, this elimination makes use of context of the
word form whose tags are to be eliminated, and it is, in fact,
based on this context.

Provided the morphological analysis has been already implemented, the true
task  of rule-based  tagging consists  in  the
development of the tag-elimination
procedures.

As the first step in solving this task, we studied the types of
morphological ambiguity occurring in Czech. Classified
broadly, there are two types of such ambiguity: provisionally, we call them {\it
regular (paradigm-internal)} and {\it casual (lexical)}.

The   regular  (paradigm-internal) ambiguities are those which occur within a
paradigm, i.e. which are common  to all lexemes belonging to
a particular inflection class. As an example, we might take the paradigm of
masculine
inanimate nouns with stems ending in a non-soft consonant (declension
pattern {\it hrad}), with systemic ambiguity among  nominative, accusative
and instrumental case of plural
number (e.g., {\it hrady}). (In this
respect the  inflection is to be taken
rather broadly, including, e.g., regular
derivation of verbal nouns and adjectives, cf. the example of the word form
{\it stav\v{e}ní}, where the  ambiguity goes also between a nominal and an
adjectival reading.)


Massive as this kind of ambiguity is, it is relatively easy to discover and
classify since  it is paradigmatical  and hence it can  be read
off   the  inflection  tables  of   Czech
morphology.

More intricate is the study of the casual (lexical, paradigm-external)
morphological ambiguity. This ambiguity is lexically specific and hence
cannot be investigated via paradigmatics.
Nevertheless, a detailed knowledge of this ambiguity is essential for the
aim of tagging, since only
after grasping the ambiguity classes, it becomes clear {\it which}
ambiguities are to be resolved, and strategies can be
developed {\it how} to
do this. As a result of work in this field we arrived at a listing of
approximately 125 classes of such ambiguous word forms (where a class is
constituted by word forms displaying the same kind of ambiguity, e.g., the
forms which have a reading as a noun in a particular case and number, and
a verbal reading, or nominal feminine and
masculine  reading, etc.),  apart from hundreds of forms which are,
as a rule, unique (the "class" has just one member) but display triple or
more ambiguity\footnote{ The highest level of lexical ambiguity, fivefold,
 which has been discovered is represented by the
word {\it kose}; together with
paradigmatical ambiguity, this adds up to seven different morphological
analyses of this word form.}.

The general idea following from this is then that the rules
of  the tagger  are organized  into packages,  each aimed at
resolving one ambiguity class by stepwise   discarding the contextually
impossible tags of a word (cf. again \cite{karlsson}). The set of all
(packages of) elimination
rules we use can be classified according to two criteria: according to
locality/nonlocality of their operation and according to the
level of reliability a rule can be assigned.

The most important feature of the approach is the possibility for the tag
elimination process to operate on a
context whose range is not fixed in advance. The beneficial impact of this
becomes clear in comparison
with both the statistical taggers and
the Brill taggers (\cite{brill}), where in both cases the
limitation  of the
operational scope of the tagger to a  local
context (window of a fixed size) seems to be the
source of most errors.

The importance of non-locality, obvious even for English,
becomes truly crucial for languages with so-called "free word-order" (such
as Czech). Thus, for example, in deciding the status of the word {\it
se} which is ambiguous between a preposition and a reflexive
particle/pronoun, a rule-based tagger can take into consideration the
presence/absence of a reflexive tantum verb in the sentence (in any
position of the sentence, not just in the immediate neigbourhood
of {\it se}), which brings along a
decisive advantage over the locally operating
methods which commit errors in this point exactly due to the
lack of globality.

However, obviously nothing prevents us also from the use
of purely local linguistic
strategies: to take another example from the package of rules devoted to
solving the ambiguity of {\it se}, it is a linguistically trivial fact that
the prepositional reading of {\it se} can be available only in local
contexts requiring the vocalization of the basic form of the preposition
{\it s} resulting in the form {\it se}.

Another profound conceptual difference between a rule-based tagger
and a stochastic one is that the rules
(and hence also results) of
the former can be assigned reliability (either as binary opposition
"fully reliable"/"not fully reliable" or on a more fine-grained scale,
discrete or continuous\footnote{ Currently we use only the binary scale,
and we set the reliability manually -- however, there is work in progress
which should result in a continuous scale of reliability of rules measured
automatically by the percentage  of errors a rule makes when
resolving ambiguity within a testing corpus.}) which seems to be in principle
impossible with the latter (this is to say, the results of a stochastic
tagger can never be claimed as fully reliable).

It is obvious that it is desirable to perform the tagging with as
many fully reliable rules as possible. As a matter of fact, our
rules are currently divided into two classes ("fully reliable"/"not fully
reliable") as follows:

\begin{itemize}
\item all tag-elimination rules reflecting general syntactic
regularities of Czech belong to the class of fully reliable rules (not only
wrt. some testing corpus, but generally)
\item apart from these general rules, we have implemented a number of
rules coping with idioms and collocations; since it is (next to) always
possible to construct an example where the construction otherwise
interpreted as an idiom or a collocation can also get a literal meaning, this
module cannot be considered as  fully reliable\footnote{ Let us remark,
however,  that in
the body of the {\it Czech National Corpus} comprising 100.000.000+
words we did not encounter a construction where
an incorrect tag would be assigned by using this module
(and hence it is obvious that the counterexamples are of only rather
theoretical nature).}.
\end{itemize}

\section{First Implemented Results}
\label{sect:results}

Although the  work on  the tagger started
 only in
spring this year, we can already present the first results and compare
them to those obtained by the stochastic and
Brill-like  taggers developed  for Czech (\cite{haj:hlad},
\cite{hlad2}).

The first package of rules created concerns the disambiguation of the
word form {\it se} (ambiguous between a reflexive particle/pronoun and a
preposition), since this is the most frequent ambiguous form in Czech
(according  to  \cite{jelinek},  {\it se}  is the
eighth most frequent
Czech word, and the most frequent one among all ambiguous words;
in the corpus formed by the current
Czech translation of George Orwell's {\it 1984} it is the most
frequent Czech word form at all -- cf. 
%\cite{petkevic1},
 \cite{petkevic2}). After implementing
 slightly more than twenty general
syntactic rules concerning {\it se}, we arrived at
disambiguating 94.34 \% of occurrences of {\it se}
(700 out of 742) within a
sample text of 39.000+ words (one issue of the scientific
magazine {\it Vesmír} dated 1992). These figures are to be interpreted
as follows: 94.34 \% of occurrences
of {\it se} are decided correctly,
while the rest, i.e.  5.66 \%, remains ambiguous\footnote{ This
is to be compared
with the statistical tagger currently in experimental use for tagging the
{\it Czech National Corpus}, where the success rate of resolving the ambiguity
of {\it se} ranks at the level of about 61 \% of occurrences,
while the remaining cca 39 \% are not left unresolved but are disambiguated
incorrectly.}. In  the particular task of the disambiguation of {\it se},
the incorporation of the
module processing idioms and collocations did not bring much progress in
this case, as the number of disambiguated occurrences of {\it se} rose to 702
only, thus yielding the total of 94.60~\% success rate and leaving 5.40 \%
unresolved. However, after inspecting  the undecided cases we are
developing additional rules, with the prospect of arriving finally at the
stage where only genuinely
syntactically ambiguous cases are left undecided at last.


\section{Remarks on Computer Implementation}
\label{sect:implementation}


The system (i.e. the rules and the software environment needed for their
application) is currently
implemented in C++ under the Linux
operating system. In particular, the rules are created by linguists in a
semi-formal format and only then programmed in C++. This makes the
implementation of a rule slow and above all error-prone as well as slightly
difficult to debug (redecoding C++ program code back to a "human" language
is not entirely simple). Therefore we are currently
developing
a "rule language", i.e. a language in which the linguist can
write the rules directly. The development of such a rule language
involves the definition of the language itself and the interpreter
or compiler of the rules transforming them to their executable form.


\begin{thebibliography}{9}
%
\bibitem{brill}
Brill, E.: A Simple Rule-Based Part-of-Speech Tagger. Proceedings of the
Third  Conference  on  Applied  Natural Language Processing.
Trento (1992)
%
\bibitem{cnk}
Czech National Corpus. Faculty of Arts, Charles University.
http://ucnk.ff.cuni.cz
%
\bibitem{hajic1}
Haji\v{c}, J.: Unification Based Morphology Grammar. PhD Thesis. MFF UK (1994)
%
\bibitem{hajic2}
Haji\v{c}, J.:  Morfologick\'e zna\v{c}ky pro u\v{z}ití  v \v{C}esk\'em n\'arodním
korpusu. ms.
%
\bibitem{haj:hlad}
Haji\v{c}, J., Hladk\'a, B.: Probabilistic and Rule-Based Tagger of an
Inflective Language -- a Comparison. Proceedings of the Fifth Conference
on  Applied  Natural  Language  Processing.  Washington D.C.
(1997)
%
\bibitem{hlad2}
Hladk\'a, B.: Czech Language Tagging. PhD Thesis. MFF UK (2000)
%
\bibitem{jelinek}
Jelínek, J.,  Be\v{c}ka, J. V., T\v{e}\v{s}itelov\'a,  M.: Frekvence slov,
slovních druh\r{u} a tvar\r{u} v \v{c}esk\'em jazyce. Praha (1961)
%
\bibitem{karlsson}
Karlsson,  F.,  Voutilainen,  A.,  Heikkil\"{a}, J., Antilla, A.
(eds.): Constraint Grammar. A Language-Independent System for Parsing
Unrestricted Text. Mouton de Gruyter, Berlin New York (1995)
%
%\bibitem{petkevic1}
%Petkevi\v{c},  V.:  Czech  Translation  of  G.  Orwell's '1984':
%Morphology  and  Syntactic  Patterns  in  the  Corpus. Text,
%Speech and Dialogue.  Second International Workshop, TSD'99.
%Plze\v{n}, Czech Republic (1999). Springer Verlag, Berlin %Heidelberg New
%York (1999) 77-82
%
\bibitem{petkevic2}
Petkevi\v{c},  V.: Korpus rom\'anu George Orwella '1984'. In prep.
%
\end{thebibliography}
\end{document}






