The present paper describes Treex (formerly decision process (such as searching for optimal feature TectoMT), a multi-purpose open-source framework for de- weights and other model parameters) is then entirely veloping Natural Language Processing applications. It fa- left to the learning algorithm. cwialirteatmesodthueledseavlerleoapdmyeinnttebgyraetxepdloiintiTngreaexw, isduecrhaansgetoooflssoffotr- Recent developments in NLP show that another sentence segmentation, tokenization, morphological analy- paradigm shift might be approaching with unsupersis, part-of-speech tagging, shallow and deep syntax pars- vised and semi-supervised algorithms, which are able ing, named entity recognition, anaphora resolution, sen- to learn from data without hand-made annotations. tence synthesis, word-level alignment of parallel corpora, However, such algorithms require considerably more and other tasks. The most elaborate application of Treex is complex models and for most NLP tasks they have an English-Czech machine translation system with trans- not outperformed supervised solutions based on handfer on deep syntactic (tectogrammatical) layer. Besides re- annotated data so far. search, Treex is used for teaching purposes and helps students to implement morphological and syntactic analyzers of foreign languages in a very short time.
plinary eld combining computer science, mathematics and linguistics, whose main aim is to allow computers to work with information expressed in human (natural) language.
The history of NLP goes back to 1950s. Early NLP systems were based on hand-written rules founded by linguistic intuitions. However, roughly two decades ago the growing availability of language data (especially textual corpora) and increasing capabilities of computer systems lead to a revolution in NLP: the eld became dominated by data-driven approaches, often based on probabilistic modeling and machine learning.
In such data-driven scenario, the role of human experts was moved from designing rules rather to (i) preparing training data enriched with linguistically relevant information (usually by manual annotation), (ii) choice of an adequate probabilistic model, proposing features (various indicators potentially useful for making the desired predictions), and (iii) specifying an objective (evaluation) function. Optimization of the ? The presented research is supported by the grants MSM0021620838 and by the European Commission's 7FP grant agreement n 231720 (EuroMatrix Plus). We would like to thank Martin Popel for useful comments on the paper.
Nowadays, researched NLP tasks range from relatively simple ones (like sentence segmentation, language identi cation), through tasks which already need a higher level of abstraction (such as morphological analysis, part-of-speech tagging, parsing, named entity recognition, coreference resolution, word sense disambiguation, sentiment analysis, natural language generation), to highly complex systems (machine translation, automatic summarization, or question answering). The importance of (and demand for) such tasks increases along with the rapidly growing amount of textual information available on the Internet.
ules chained in a pipeline (such as a sentence segmenter and part-of-speech tagger prior to a parser). However, if state-of-the-art solutions created by different authors { often written in di erent programming languages, with di erent interfaces, using different data formats and encodings { are to be used, a signi cant e ort must be invested into integrating the tools. Even if these issues are only of technical nature, in real research they constitute one of limiting factors for building more complex NLP applications.
We try to eliminate such problems by introducing a common NLP framework that integrates a number of NLP tools and provides them with uni ed objectoriented interfaces, which hide the technical issues from the developer of a larger application. The framework's architecture seems viable { tens of researchers and students have already contributed to the system and the framework has been already used for a number of research tasks carried out at the Institute of Formal and Applied linguistics as well as at some other research institutions. The most complex application implemented within the framework is English-Czech machine translation. The framework is called Treex.1
The remainder of the paper is structured as follows. Section 2 overviews related work that had to be taken into account when developing such framework. Section 3 presents the main design decisions Treex is build on. English-Czech machine translation implemented in Treex is described in Section 4, while other Treex applications are mentioned in Section 5, which also concludes. 2 2.1
Related work
nomenon. Modeling the language in its entirety would be extremely complex, therefore its description is often decomposed into several subsequent layers (levels). There is no broadly accepted consensus on details concerning the individual levels, however, the layers typically roughly correspond to the following scale: phonetics, phonology, morphology, syntax, semantics, and pragmatics.
One of such strati cational hypotheses is
Functional Generative Description (FGD), developed by
Petr Sgall and his colleagues in Prague since the
1960s [
Each sentence is tokenized and each token is annotated with a lemma (basic word form, such as nominative singular for nouns) and morphological tag (describing morphological categories such as part of speech, number, and tense).
Each sentence is represented as a shallow-syntax dependency tree (a-tree). There is one-to-one correspondence between m-layer tokens and a-layer nodes (a-nodes). Each a-node is annotated with the so-called analytical function, which represents the type of dependency relation to its parent (i.e. its governing node).
Each sentence is represented as a deep-syntax dependency tree (t-tree). Autosemantic (meaningful) words are represented as t-layer nodes (t-nodes). Information conveyed by functional words (such as auxiliary verbs, prepositions and subordinating conjunctions) is represented by attributes of t-nodes. Most important attributes of t-nodes are: tectogrammatical lemma, functor (which represents the semantic value of syntactic dependency relation) and a set of grammatemes (e.g. tense, number, verb modality, deontic modality, negation).
Edges in t-trees represent linguistic dependencies except for several special cases, the most notable of which are paratactic structures (coordinations).
notation manuals distributed with PDT 2.0.
This annotation scheme has been adopted and further modi ed in Treex. One of the modi cations consists in merging m-layer and a-layer sentence representations into a single data structure.2
Treex also pro ts from the technology developed during the PDT project, especially from the existence of the highly customizable tree editor TrEd, which is used as the main visualization tool in Treex, and from the XML-based le format PML (Prague Markup Language, [14]), which is used as the main data format in Treex. 2.2
Treex is not the only existing general NLP
frame1 The framework was originally called TectoMT since work. We are aware of the following other frameworks
starting its development in autumn 2005 [
building annotated German text corpora. The architecture of Treex is based on the following
{ Apertium [
In our opinion, none of these frameworks seems feasible (or mature enough) for experiments on MT based on deep-syntactic dependency transfer. The only exception is ETAP-3, whose theoretical assumptions are similar to that of Treex (its dependency-based strati cational background theory called Meaning-Text Theory [13] bears several resemblances to FGD), however, it is not an open-source project. 2.3
MT is a notoriously hard problem and it is studied
by a broad research eld nowadays: every year there
are several conferences, workshops and tutorials
dedicated to it (or even to its sub elds). It goes beyond the
scope of this work even to mention all the
contemporary approaches to MT, but several elaborate surveys
of current approaches to MT are already available to
the reader elsewhere, e.g. in [
A distinction is usually made between two MT paradigms: rule-based MT (RBMT) and statistical MT (SMT). The rule-based MT systems are dependent on the availability of linguistic knowledge (such as grammar rules and dictionaries), whereas statistical MT systems require human-translated parallel text, from which they extract the translation knowledge automatically. One of the representatives of the rst group is the already mention system ETAP-3.
Nowadays, the most popular representatives of the
second group are phrase-based systems (in which the
term `phrase' stands simply for a sequence of words,
not necessarily corresponding to phrases in constituent
syntax), e.g. [
Even if phrase-based systems have more or less dominated the eld in the recent years, their translation quality is still far from perfect. Therefore we believe it makes sense to investigate also alternative approaches.
MT implemented in Treex lies somewhere between the two main paradigms. Like in RBMS, sentence representations used in Treex are linguistically interpretable. However, the most important decisions 3 http://opennlp.sourceforge.net 4 http://weblicht.sfs.uni-tuebingen.de/englisch/index.shtml { Treex is primarily developed in Linux. However, platform independent solutions are searched for wherever possible. { The main programming language of Treex is Perl.
However, a number of tools written in other languages have been integrated into Treex (after providing them with a Perl wrapper). { Linguistic interpretability { data structures representing natural language sentences in Treex must be understandable by a human (so that e.g. translation errors can be traced back to their source). Comfortable visualization of the data structures is supported. { Modularity { NLP tools in Treex are designed so that they are easily reusable for various tasks (not only for MT), { Rules-vs-statistics neutrality { Treex architecture is neutral with respect to the rules vs. statistics opposition (rule-based as well as statistical solutions are combined). { Massive data { Treex must be capable of processing large data (such as millions of sentence pairs in parallel corpora), which implies that distributed processing must be supported. { Language universality { ideally, Treex should be easily extendable to any natural language. { Data interchange support { XML is used as the main storage format in Treex, but Treex must be able to work with a number of other data formats used in NLP. 3.2
In Treex, representations of a text in a natural language is structured as follows: { Document. A Treex document is the smallest independently storable unit. A document represents a piece of text (or several parallel pieces of texts in the case of multilingual data) and its linguistic representations. A document contains an ordered sequence of bundles. { Bundle. A bundle corresponds to a sentence (or a tuple of sentences in the case of parallel data) and its linguistic representations. A bundle contains a set of zones. { Zone. Each language (languages are distinguished using ISO 639-2 codes in Treex) can have one or more zones in a bundle.5 Each zone corresponds to one particular sentence and at most one tree for each layer of linguistic description. { Tree. All sentence representations in Treex have the shape of an oriented tree.6 At this moment there are four types of trees: (1) a-trees { morphology and surface-dependency (analytical) trees, (2) t-trees { tectogrammatical trees, (3) p-trees { phrase-structure (constituency) trees, (4) n-trees { trees of named entities. { Node. Each nodes contains (is labeled by) a set of attributes (name-value pairs). { Attribute. Some node attributes are universal (such as identi er), but most of them are speci c for a certain layer. The set of attribute names and their values for a node on a particular layer is declared using the Treex PML schema.7 Attribute values can be further structured.
Of course, there are also many other types of data structures used by individual integrated modules (such as dictionary lists, weight vectors and other trained parameters, etc.), but they are usually hidden behind module interfaces and no uniform structure is required for them. 3.3
There are two basic levels of processing units in Treex: { Block. Blocks are the smallest processing units in
dependently applicable on a document. { Scenario. Scenarios are sequences of blocks. When a scenario is applied on a document, the blocks from the sequence are applied on the document one after another. 5 Having more zones per language is useful e.g. for comparing machine translation with reference translation, or translation outputs from several systems. Moreover it highly simpli es processing of parallel corpora, or comparisons of alternative implementations of a certain tasks (such as di erent dependency parsers). 6 However, tree-crossing edges such as anaphora links in a dependency tree can be represented too (as node attributes). 7 There are also \wild" attributes allowed, which can store any Perl data structure without its prior declaration by PML. However, such undeclared attributes should serve only for tentative or rapid development purposes, as they cannot be validated.
(a) Simple Treex scenario: Util::SetGlobal language=en # do everyth. in English zone Block::Read::Text # read a text from STDIN W2A::Segment # segment it into sentences W2A::Tokenize # divide sentences into words W2A::EN::TagMorce # morphological tagging W2A::EN::Lemmatiz # lemmatization (basic word forms) W2A::EN::ParseMST # dependency parsing W2A::EN::SetAfunAuxCPCoord # fill analytical functions W2A::EN::SetAfun # fill analytical functions Write::CoNLLX # print trees in CoNLLX format Write::Treex # store trees into XML file (b) Input text example: When the prince mentions the rose, the geographer explains that he does not record roses, calling them "ephemeral".
The prince is shocked and hurt by this revelation. The geographer recommends that he visit the Earth. (c) Fragment from the printed output (simpli ed): 1 The the DT 2 prince prince NN 3 is be VBZ 4 shocked shock VBN 5 and and CC 6 hurt hurt VBN 7 by by IN 8 this this DT 9 revelation revelation NN 10 . . .
English-Czech machine translation in Treex { blocks for sentence analysis { blocks for tokeniza- The translation scenario implemented in Treex comtion, morphological tagging, parsing, anaphora poses of three steps described in the following secresolution, etc. tions: (1) analysis of the input sentences up to tec{ blocks for sentence synthesis { blocks for propa- togrammatical layer of abstraction, (2) transfer of the gating agreement categories, ordering words, in- abstract representation to the target language, and ecting word forms, adding punctuation, etc. (3) synthesis (generating) of sentences in the target { blocks for transfer { blocks for translating a com- language. See an example in Figure 2. ponent of a linguistic representation from one language to another, etc. { blocks for parallel texts { blocks for word align- 4.1 Analysis
ment, etc. { writer and reader blocks { block for storing/loading Treex documents into/from les or The analysis step can be decomposed into three phases other streams (in the PML or other format),9 corresponding to morphological, analytical and tec{ auxiliary blocks { blocks for testing, printing, etc. togrammatical analysis.
In the morphological phase, a text to be trans
If possible, we try to implement blocks in a lan- lated is segmented into sentences and each sentence
guage independent way. However, many blocks will re- is tokenized (segmented into words and punctuation
main language speci c (for instance a block for moving marks). Tokens are tagged with part of speech and
clitics in Czech clauses can hardly be reused for any other morphological categories by the Morce
tagother language). ger [
There are large di erences in complexity of blocks. In the analytical phase, each sentence is parsed usSome blocks contain just a few simple rules (such as ing the dependency parser [12] based on Maximum regular expressions for sentence segmentation), while Spanning Tree algorithm, which results in an analytiother blocks are Perl wrappers for quite complex prob- cal tree for each sentence. Tree nodes are labeled with abilistic models resulting from several years of research analytical functions (such as Sb for subject, Pred for (such as blocks for parsing). predicate, and Adv for adverbial).
As for block granularity, there are no widely agreed Then the analytical trees are converted to the
tecconventions for decomposing large NLP applica- togrammatical trees. Each autosemantic word with its
tions.10 We only follow general recommendations for associated functional words is collapsed into a
sinsystem modularization. A piece of functionality should gle tectogrammatical node, labeled with lemma,
funcbe performed by a separate block if it has well de ned tor (semantic role), formeme,11 and semantically
ininput and output states of Treex data structures, if it dispensable morphologically categories (such as tense
can be reused in more applications and/or it can be with verbs and number with nouns, but not number
(at least potentially) replaced by some other solution. with verbs as it is only imposed by subject-predicate
agreement). Coreference of pronouns is also resolved
and tectogrammatical nodes are enriched with
information on named entities (such as the distinction
between location, person and organization) resulting
from Stanford Named Entity Recognizer [
11 Formemes specify how tectogrammatical nodes are
realized in the surface sentence shape. For instance,
n:subj stands for semantic noun in the subject
position, n:for+X for semantic noun with preposition for,
v:because+ n for semantic verb in a subordinating
clause introduced by the conjunction because, adj:attr for
semantic adjective in attributive position. Formemes do
not constitute a genuine tectogrammatical component
as they are not oriented semantically (but rather
morphologically and syntactically). However, they have been
added to t-trees in Treex as they facilitate the transfer.
Fig. 2. Analysis-transfer-synthesis translation scenario in Treex applied on the English sentence \However, this very
week, he tried to nd refuge in Brazil.", leading to the Czech translation \Presto se tento prave tyden snazil naj t
utociste v Braz lii.". Thick edges indicate functional and autosemantic a-nodes to be merged.
4.2 Transfer labelling is then revealed by the tree-modi ed Viterbi
algorithm [
The transfer phase follows, whose most di cult part Originally, we estimated the translation model simconsists in labeling the tree with target-language lem- ply by using pair frequencies extracted from Englishmas and formemes. Changes of tree topology and of Czech parallel data. A signi cant improvement was other attributes12 are required relatively infrequently. reached after replacing such model by Maximum En
Our model for choosing the right target-language tropy model. In the model, we employed a wide range
lemmas and formemes in inspired by Noisy Channel of features resulting from the source-side analysis. The
Model which is the standard approach in the contem- weights were optimized using training data extracted
porary SMT and which combines a translation model from the CzEng parallel treebank [
can be used which estimates how well some translation equivalent ts to the surrounding context.13 Finally, surface sentence shape is synthesized from the
Unlike in the mainstream SMT, in tectogrammat- tectogrammatical tree, which is basically a reverse
ical transfer we do not use this idea for linear struc- operation for the tectogrammatical analysis: adding
tures, but for trees. So the translation model estimates punctuation and functional words, spreading
morphothe probability of source and target lemma pair, while logical categories according to grammatical
agreethe language tree model estimates the probability of ment, performing in ection (using Czech morphology
a lemma given its parent. The globally optimal tree database [
tion quality of outputs of MT systems: (1) the quality
can be judged by humans (either using a set of criteria
such as grammaticality and intelligibility, or relatively
by comparing outputs of di erent MT systems), or
(2) the quality can be estimated by automatic met- { linguistic data processing service for other research
rics, which usually measure some form of string-wise carried out in other institutions, such as data
analoverlap of an MT system's output with one or more yses for prosody prediction for The University of
reference (human-made) translations. West Bohemia [
Both types of evaluation are used regularly during
the development of our MT system. Automatic metrics Treex signi cantly simpli es code sharing across
are used after any change of the translation scenario, individual research projects in our institute. There are
as they are cheap and fast to perform. Large scale around 15 programmers (postgraduate students and
evaluations by volunteer judges are organized annu- researchers) who have signi cantly contributed to the
ally as a shared task with the Workshop on Statistical development of Treex in the last years; four of them
Machine Translation.14 Performance of the tectogram- are responsible for developing the central components
matical translation increases every year in both mea- of the framework infrastructure called Treex Core.
sures, and it already outperforms some commercial as Last but not least, Treex is used for teaching
purwell as academic systems. Actually, it is the participa- poses in our institute. Undergraduate students are
tion in this shared task (a competition, in other words) supposed to develop their own modules for
morphowhat provides the strongest motivation momentum for logical and syntactic analysis for foreign languages of
Treex developers. their choice. Not only that the existence of Treex
enables the students to make very fast progress, but their
5 Final remarks and conclusions contributions are accumulated in the Treex
Subversion repository too, which enlarges the repertory of
Even if tectogrammatical translation is considered as languages treatable by Treex.15
the main application of Treex, Treex has been used for There are two main challenges for the Treex
devela number of other research purposes as well: opers now. The rst challenge is to continue improving
the tectogrammatical translation quality by better
ex{ other MT-related tasks { Treex has been used for ploitation of the training data. The second challenge
developing alternative MT quality measures in [