\documentclass{llncs} 

\begin{document}

\title{Automatic Tagging of Compound Verb Groups in Czech Corpora\thanks{
       This research has been partially supported by the Czech Ministry
       of Education under the grant VS97028.}
}

\author{Eva \v{Z}\'a\v{c}kov\'{a}, Lubo\v{s} Popel\'{\i}nsk\'{y} 
        and Miloslav Nepil
}

\institute{
   NLP Laboratory, Faculty of Informatics, Masaryk University\\
   Botanick\'{a} 68, CZ-602~00 Brno, Czech Republic \\
   E-mail: {\tt \{glum,popel,nepil\}@fi.muni.cz}
}

\maketitle


\begin{abstract}
\noindent
In Czech corpora compound verb groups are usually tagged in
word-by-word manner. As a consequence, some of the morphological tags
of particular components of the verb group loose their original
meaning.  We present an improved method for automatic synthesis of
verb rules that describe all compound verb groups frequent in Czech.
Using these rules we can find compound verb groups in unannotated
texts with high accuracy.  The system for tagging compound verb groups
in an annotated corpus that exploits the verb rules is described.
\\[1mm]
{\bf Keywords:} compound verb groups, corpora, 
morphosyntactic tagging, inductive logic programming
\end{abstract}

\section{Compound Verb Groups}
Recognition and analysis of the predicate in a sentence is fundamental
for the meaning of the sentence and its further (semantic) analysis.
In more than half of Czech sentences the predicate contains
the compound verb group.  
%
E.g. in the sentence \emph{Mrz\'\i{} m\v e, \v ze jsem 
o t\'e konferenci nev\v ed\v ela, byla bych se j\'\i{} z\'u\v castnila.}
(literary translation: {\em I am sorry that I did not know about the conference,
I would have participated 
in it.}) there are three verb groups
\\[2mm] 
$<$vg$>$ {\em Mrz\'\i{}} $<$/vg$>$ {\em m\v e, \v
ze} $<$vg$>$ {\em jsem} {\em o t\'e konferenci} {\em nev\v ed\v
ela} $<$/vg$>$, $<$vg$>$ {\em byla bych se} {\em j\'\i{}}
{\em z\'u\v castnila.} $<$/vg$>$
\\[2mm] 
{\em I} $<$vg$>$ {\em am sorry} $<$/vg$>$ {\em that I} $<$vg$>$ {\em did not 
know} $<$/vg$>$ {\em about the conference, I}
$<$vg$>$ {\em would have participated} $<$/vg$>$ {\em in it.}
\\[2mm]
Verb groups are often split into more parts
with so called gap words. In the second verb group the gap words are {\em 
o t\'e konferenci}  ({\em about the conference}).
%
In annotated Czech corpora, including DESAM \cite{SOFSEM97-Pala},
compound verb groups are usually tagged in word-by-word manner. As a
consequence, some of the morphological tags of particular components
of the verb group loose their original meaning.
%
In the sentence above 
the word \emph{jsem} is tagged as a verb in present tense, but the whole 
verb group
to which it belongs -- \emph{jsem nev\v ed\v ela (I did not know)} -- is in the past tense. 
Similar situation appears in \emph{byla bych se j\'\i{} z\'u\v castnila (I would 
have participated in it)} where 
\emph{z\'u\v castnila} is tagged as past tense while it is only a part of
past conditional. 
\\[2mm]
We consider a compound verb group to be a list of cohesive verbs and
maybe reflexive pronouns {\em se, si}.  Such a group is obviously
compound of auxiliary and full-meaning verbs, e.g. {\em budu se
sm\'at} where {\em budu} is auxiliary verb (like {\em will} in English),
{\em se} is the reflexive pronoun and {\em sm\'at} means {\em to laugh}.
%
As word-by-word tagging of verb groups is
confusing, it is useful to find and assign a new tag to the whole group.
This tag should contain information about the beginning and
the end of the group and about the particular components of the verb 
group. It must also contain information about relevant 
grammatical categories that characterize the verb group as a whole.  
%
Without finding all parts of a compound verb group and without tagging
the whole group (what is necessary dependent on other parts of the
compound verb group) it is impossible to continue with any kind of
semantic analysis.
In \cite{TSD99} a proposal of the method for automatic
finding of compound verb groups in the corpus DESAM is introduced. 
We describe here an improved method that
results in definite clause grammar rules - called verb rules
- that contain information about all components of a particular 
verb group and about their tags. 
%
We describe also some improvements that allow to increase the accuracy
of verb group recognition.


\section{Learning Verb Rules}
The process of learning verb rules \cite{TSD99} 
is split into three steps: finding verb chunks 
(i.e. finding boundaries of simplex sentences in compound or in complex
sentences, and  elimination of gap words),
generalization of the chunk and verb rule synthesis.

\subsection{Verb Chunks}
The observed properties of a verb group are the following: their
components are either verbs or reflexive pronoun \emph{se}
(\emph{si}); a verb group cannot cross the boundary of a sentence; and
between two components of the verb group there can be a gap consisting
of an arbitrary number of non-verb words or even a whole sentence.
\\[2mm]
In the first step, the boundaries of all simplex sentences are found.
Then each gap is replaced by tag {\tt gap}.  The method exploits only
the lemma of each word (nominative singular for nouns, adjectives,
pronouns and numerals, infinitive for verbs) and its tag.  We will
demonstrate the whole process using the third simplex sentence of the
clause mentioned in the first section
({\em byla bych se jí z\'u\v castnila (I would have participated in it)}\/):\\[1mm]
\texttt{\hbox to 0.4cm{}být/k5eApFnStMmPaI by/k5eAp1nStPmCaI si/k3xXnSc4}\\
\texttt{\hbox to 0.4cm{}on/k3xPgFnSc2p3 z\'u\v castnit/k5eApFnStMmPaP}\\[1mm]
After substitution of gaps we obtain\\[1mm]
\texttt{\hbox to 0.4cm{}být/k5eApFnStMmPaI by/k5eAp1nStPmCaI si/k3xXnSc4}\\
\texttt{\hbox to 0.4cm{}gap}\\ 
\texttt{\hbox to 0.4cm{}z\'u\v castnit/k5eApFnStMmPaP}

\subsection{Generalization}
The lemmata and the tags are now being generalized. Three
generalization operations are employed: elimination of (some of)
lemmata, generalization of grammatical categories and finding
grammatical agreement constraints.

\paragraph{Elimination of lemmata.}
      All lemmata except forms of auxiliary verb \emph{b\'{y}t (to be)}
        (b\'yt, by, aby, kdyby)
      are rejected. Lemmata of modal verbs and verbs with similar behaviour
      are replaced by tag {\tt modal}. These verbs have been
      found in the list of more than 15\,000 verb valencies.
      In our example it is the verb {\em z\'u\v castnit} that is removed.
\begin{verbatim}
  být/k5eApFnStMmPaI by/k5eAp1nStPmCaI k3xXnSc4
  gap k5eApFnStMmPaP
\end{verbatim}

\paragraph{Generalization of grammatical categories.}
By exploiting linguistic knowledge we can observe that 
some grammatical categories are
not important for verb group description. These categories may also be 
removed.  Very often it is negation (e), or aspect (a). For some of
verbs even person (p) can be removed. Values of those
grammatical categories have been replaced by {\tt ?} in our example.
\begin{verbatim}
  být/k5e?pFnStMmPa? by/k5e?p?nStPmCa? k3xXnSc? 
  gap k5e?pFnStMmPa?
\end{verbatim}

\paragraph{Finding grammatical agreement constraints.}
Another situation appears when two or more values of some category are related.
In the simplest case they have to be the same -- e.g. the value of attribute
person (p) in the first and the last word of our example.
More complicated is the relation among the values of attribute number (n).
They should be the same except when the polite way of addressing occurs,
e.g. in {\em byl byste se j\'\i{} z\'u\v castnil (you would have participated 
in it)}. Thus we have to check whether the values are the same or the 
conditions of polite way of addressing are satisfied.
For this purpose we add the
predicate \texttt{check\_num()} that ensures agreement in the
grammatical category number and we obtain
\begin{verbatim}
  být/k5e?p_n_tMmPa? by/k5e?p?n_tPmCa? k3xXnSc? 
  gap k5e?p_n_tMmPa? check_num(n)
\end{verbatim}

\subsection{DCG Rules Synthesis.}
Finally the verb rule is constructed by rewriting the
result of the generalization phase.
\begin{verbatim}
verb_group(vg(Be,Cond,Se,Verb), Gaps) -->
  be(Be,_,P,N,tM,mP,_),                 % být/k5e?p_n_tMmPa?
  cond(Cond,_,_,Ncond,tP,mC,_),         % by/k5e?p?n_tPmCa?
   {check_num(N,Ncond,Cond,Vy)},            
  reflex_pron(Se,xX,_,_),               % k3xXnSc? 
  gap([],Gaps),                         % gap
  k5(Verb,_,_,P,N,tM,mP,_).             % k5e?p_n_tMmPa?
\end{verbatim}
The meanings of non-terminals used in the rule are following:
\texttt{be()} represents auxiliary verb \emph{b\'yt}, \texttt{cond()}
represents various forms of conditionals \emph{by, aby, kdyby},
\texttt{reflex\_pron()} stands for the reflexive pronoun \emph{se (si)},
\texttt{gap()} is a special predicate for manipulation with gaps, and
\texttt{k5()} stands for an arbitrary non-auxiliary verb.  The particular
values of some arguments of non-terminals represent required
properties. Simple cases of grammatical agreement are treated through
binding of variables. More complicated situations are solved by employing
constraints like the predicate \texttt{check\_num()}.  
\\[2mm]
The method has been implemented in Perl.  126 definite clause grammar
rules were constructed from the annotated corpus that describe all
verb groups that are frequent in Czech.
%
Although the method described displays quite good accuracy on the test set
(the correct verb rule has been corrrectly assigned to 92.3\% verb groups), 
it has some drawbacks.
% >> vynechan text o motivaci k auto,. hledani slovesnych skupin
In about 13\% of complex sentences, some of compound verb
groups were not correctly recognized.  It was observed that almost
46\% of errors were caused by incorrect lemma recognition. 


\section{Fixing Misclassification Errors}
To fix the most frequent error -- incorrectly recognised lemma of a
word in the verb group -- we combined two approaches.  Rules that
recognised a word-lemma couple of a very small frequency in the corpus 
(actually those
that did not appear there) were supposed to be
incorrect.  The second approach that exploits inductive logic programming (ILP)
techniques reads the context of the
lemma-ambiguous word and results in disambiguation rules
\cite{pkdd99}. 

For testing we randomly chose the set of 600 examples including
compound or complex sentences. 251 sentences contained only one verb.
The results obtained are in Tab.~\ref{fixing}. The first line contains
the number of examples used. In the following line there are results
for the original method.  Then the results with the word-lemma couple
of a very small frequency have been removed; the accuracy is in the
third line.  In the last line is the percentage of correct rules
after the lemma disambiguation was employed. The column
'$>$ 1 verb' concerns the sentences where at least two verbs appeared.
The last column displays accuracy for all sentences.
\begin{table}
\caption{Fixing}\label{fixing}
\begin{center}
\begin{tabular}{|l c c|} \hline
~~~~~~~~~~~~& number of correct rules(\%) & \\ 
            & $>$ 1 verb & all \\ \hline
number of examples       &  349 & 600 \\
original method          &  86.8 & 92.3\\
$-$ not frequent lemmata     &  91.1 & 94.8 \\
$+$ lemma dis. employed      &  92.8 & 95.8  \\
\hline
\end{tabular}
\end{center}
\vspace*{-5mm}
\end{table}


\section{Tagging Verb Groups}

We now describe a method for compound verb group
tagging in morphologically annotated corpora. We
decided to use SGML-like notation for tagging because it allows to
incorporate the new tags very easily into DESAM corpus.
The beginning and the end of the whole verb group and
beginnings and ends of its particular components are marked.  For
the sentence \emph{byla bych se j\'\i{} z\'u\v castnila (I would have 
participated in it)} we receive\\[2mm]
\texttt{<vg tag="eApFnStPmCaPr1v0" fmverb="z\'u\v castnit">}\\
\texttt{\hbox to 0.4cm{}<vgp>byla</vgp>}\\
\texttt{\hbox to 0.4cm{}<vgp>bych</vgp>}\\
\texttt{\hbox to 0.4cm{}<vgp>se</vgp>} \\
\texttt{\hbox to 0.4cm{}jí}\\
\texttt{\hbox to 0.4cm{}<vgp>z\'u\v castnila</vgp>}\\
\texttt{</vg>}\\[2mm]
where 
\texttt{<vg> </vg>} point out the beginning and the end of the verb group,  
\texttt{<vgp> </vgp>} mark components (parts) of the verb group.  
The assigned tag -- i.e. values of significant morphologic categories -- 
of the whole
group is included as a value of attribute called {\tt tag} in the starting
mark of the group. Value of the attribute {\tt fmverb} is the
full-meaning verb; this information can be exploited e.g. for searching and 
processing of verb valencies afterwards.
The value of attribute {\tt tag} is computed automatically from the verb rule 
that describes the compound verb group. \\[2mm]
We are also able to detect  
other properties of compound verb groups. In the example above the new 
category {\tt r} is introduced.
It indicates that the group is reflexive ({\tt r1}) or not ({\tt r0}). 
The category {\tt v} enables to mark whether
the group is in the form of polite way of addressing ({\tt v1}) or not 
({\tt v0}). 
The differences of the {\tt tag} values can be observed comparing
the previous and the following examples ({\em nebyl byste se j\'\i{} 
z\'u\v castnil (you would not have participated
in it)}\/)\\[2mm]
\texttt{<vg tag="eNpMnStPmCaPr1v1" fmverb="z\'u\v castnit">}\\
\texttt{\hbox to 0.4cm{}<vgp>nebyl</vgp>}\\
\texttt{\hbox to 0.4cm{}<vgp>byste</vgp>}\\
\texttt{\hbox to 0.4cm{}<vgp>se</vgp>} \\
\texttt{\hbox to 0.4cm{}jí}\\
\texttt{\hbox to 0.4cm{}<vgp>z\'u\v castnil</vgp>}\\
\texttt{</vg>}\\[2mm]
The set of attributes can be also enriched e.g. with the number of components.
We also plan to include into the attributes of \texttt{<vg>} compound verb 
group type. It will enable to find the groups of the same type 
but with different word order or the number of components.
 
\section{Conclusion}
Let us notice that sometimes compound verb groups are
defined in a less general way. 
In contrast to these approaches  
we include into the groups also some verbs which are in fact infinitive
participants of verb valencies. However, we are able to detect such cases and
recognize the ``pure'' verb groups afterwards. 
We believe that for some kind of
shallow semantic analysis -- e.g. in dialog systems -- our approach is
more convenient. 
% jeste by se dalo dopsat, ze pri partial parsingu se snazime co nejjednoduseji
%najit co nejvic veci a stejne se ty valence nekdy najit musi 
%
We are also able to recognize the form of polite way of addressing a
person (which has not equivalent in English, but similar phenomenon
appears e.g. in French or German). As it is quite important for
understanding the sentence we extend the tag of a verb group with this
information.  E.g. in \emph{\v{s}el jste (vous \^{e}tes all\'e)} the
word \emph{jste} should be counted as singular although it is always
tagged as plural.
\\[2mm]
Another approach that deals with the recognition and morphological tagging
of compound verb groups in Czech appeared in \cite{klara}.  Basic compound
verb groups in Czech like active present, passive past tense, present
conditional etc., are defined in terms of grammatical categories used
in DESAM corpus.  Two drawbacks of this approach can be observed.
First, verb groups may only be compound of a reflexive pronoun, verbs
\emph{to be} and not more than one full-meaning verb.  Second, the gap
between two words of the particular group cannot be longer than three
words.  The verb rules defined here are less general then the basic
verb groups \cite{klara}. Actually verb rules make partition of them. Thus
we can tag all the basic verb groups without the limitations mentioned
above.
\\[2mm]

\begin{thebibliography}{1}

\bibitem{klara}
K.~Osolsob\v{e}.
\newblock Morphological Tagging of Compound Verb Forms in Czech Corpus.
\newblock Technical report, Studia Minora Facultatis Philosophicae
  Universitatis Brunensis Brno, 1999.

\bibitem{SOFSEM97-Pala}
K.~Pala, P.~Rychl\'{y}, and P.~Smr\v{z}.
\newblock {DESAM} -- Annotated Corpus for Czech.
\newblock In {\em Pl\'{a}\v{s}il F., Jeffery K.G.(eds.): Proceedings of
  SOFSEM'97, Milovy, Czech Republic. LNCS 1338}, pages 60--69. Springer, 1997.

\bibitem{pkdd99}
T.~Pavelek and L.~Popel\'{\i}nsk\'{y}.
\newblock Mining Lemma Disambiguation Rules from Czech Corpora.
\newblock In {\em Principles of Knowledge Discovery in Databases: Proceedings
  of PKDD'99 Conference, LNAI 1704}, pages 498--503. Springer, 1999.

\bibitem{TSD99}
E.~\v{Z}\'{a}\v{c}kov\'{a} and K.~Pala.
\newblock Corpus-Based Rules for Czech Verb Discontinuous Constituents.
\newblock In {\em Text, Speech and Dialogue: Proceedings of TSD'99 Workshop,
  LNAI 1692}, pages 325--328. Springer, 1999.


\end{thebibliography}

\end{document}
