Mirroshandel, Seyed Abolghasem, Alexis Nasr & Joseph Le Roux. 2012. Semi-supervised dependency parsing using lexical affinities. In *Proceedings of the 50th annual meeting of the Association for Computational Linguistics (volume 1: long papers)*, 777–785. Jeju Island, Korea: Association for Computational Linguistics. http://aclweb.org/anthology/P12-1082.

Mirroshandel, Seyed Abolghasem, Alexis Nasr & Benoît Sagot. 2013. Enforcing subcategorization constraints in a parser using sub-parses recombining. In *Proceedings of the 2013 conference of the North American chapter of the Association for Computational Linguistics: Human Language Technologies*, 239–247. Atlanta, Georgia: Association for Computational Linguistics.

Nagy T., István & Veronika Vincze. 2014. VPCTagger: Detecting verb-particle constructions with syntax-based methods. In *Proceedings of the EACL 2014 workshop on MWEs*, 17–25. Gothenburg.

Nakagawa, Tetsuji. 2007. Multilingual dependency parsing using global features. In *Proceedings of the CoNLL shared task session of EMNLP-CoNLL 2007*, 952–956. Prague, Czech Republic: Association for Computational Linguistics. http://www.aclweb.org/anthology/D07-1100.

Nasr, Alexis, Frederic Bechet, Jean-François Rey, Benoît Favre & Joseph Le Roux. 2011. MACAON: An NLP tool suite for processing word lattices. In *Proceedings of ACL 2011 demonstrations*. Portland, Oregon.

Nasr, Alexis, Carlos Ramisch, José Deulofeu & André Valli. 2015. Joint dependency parsing and multiword expression tokenisation. In *53rd annual meeting of the Association for Computational Linguistics*, 1116–1126. Beijing, China.

Nilsson, Jens, Sebastian Riedel & Deniz Yuret. 2007. The CoNLL 2007 shared task on dependency parsing. In *Proceedings of EMNLP/CoNLL 2007 CoNLL shared tasks session*, 915–932.

Nivre, Joakim. 2014. *Transition-based parsing with multiword expressions*. Athens.

Nivre, Joakim, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajič, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty & Dan Zeman. 2016. Universal dependencies v1: A multilingual treebank collection. In *Proceedings of the 10th international conference on Language Resources and Evaluation (LREC 2016)*. Portorož, Slovenia.

Nivre, Joakim, Johan Hall & Jens Nilsson. 2004. Memory-based dependency parsing. In *Proceedings of CoNLL 2004*, 49–56. Boston, Massachusetts.

Nivre, Joakim, Johan Hall, Jens Nilsson, Atanas Chanev, Gülsen Eryigit, Sandra Kübler, Svetoslav Marinov & Erwin Marsi. 2007. MaltParser: A language-independent system for data-driven dependency parsing. *Natural Language Engineering* 13(02). 95–135.
Nivre, Joakim & Jens Nilsson. 2004. Multiword units in syntactic parsing. *Proceedings of Methodologies and Evaluation of Multiword Units in Real-World Applications (MEMURA).*

Pawley, Andrew & Frances Hodgetts Syder. 1983. Two puzzles for linguistic theory: Native-like selection and native-like fluency. In J. C. Richards & R. W. Schmidt (eds.), *Language and communication*, 191–226. London: Longman.

Prins, Robbert. 2005. *Finite-state pre-processing for natural language analysis*. Behavioral & Cognitive Neurosciences (BCN) research school, University of Groningen dissertation.

Ramshaw, Lance A. & Mitchell P. Marcus. 1995. Text chunking using transformation-based learning. In *Proceedings of the 3rd ACL workshop on Very Large Corpora*, 82–94.

Ronan, Patricia & Gerold Schneider. 2015. Determining light verb constructions in contemporary British and Irish English. *International Journal of Corpus Linguistics* 20(3), 326–354.

Rosén, Victoria, Gyri Smørdal Losnegaard, Koenraad De Smedt, Eduard Bejček, Agata Savary, Adam Przepiórkowski, Petya Osenova & Verginica Barbu Mititelu. 2015. A survey of multiword expressions in treebanks. In *Proc. of 14th international workshop on Treebanks and Linguistic Theories (TLT 2015)*, 179–193. Warsaw, Poland.

Sag, Ivan, Timothy Baldwin, Francis Bond, Ann Copestake & Dan Flickinger. 2002. Multiword expressions: A pain in the neck for NLP. In *Proceedings of the 3rd international conference on Computational Linguistics and Intelligent Text Processing* (Lecture Notes in Computer Science 2276), 1–15. Springer.

Sagot, Benoît & Pierre Boullier. 2005. From raw corpus to word lattices: Robust pre-parsing processing with SxPipe. *Archives of Control Sciences* 15(4), 653–662.

Schneider, Gerold. 2008. *Hybrid long-distance functional dependency parsing*. Institute of Computational Linguistics, University of Zurich Doctoral Thesis.

Schneider, Gerold. 2012. Using semantic resources to improve a syntactic dependency parser. In *Proceedings of Semantic Relations II workshop (SEM-II) at LREC 2012*, 67–76. Istanbul, Turkey.

Schneider, Gerold. 2014. Improving PP attachment in a hybrid dependency parser using semantic, distributional, and lexical resources. In *Second PARSEME meeting*. Athens, Greece.

Schneider, Nathan, Spencer Onuffer, Nora Kazour, Emily Danchik, Michael T. Mordowanec, Henrietta Conrad & Noah A. Smith. 2014. Comprehensive annotation of multiword expressions in a social web corpus. In *Proceedings of*
the ninth international conference on Language Resources and Evaluation (LREC 2014), 456–461. Reykyavik.

Seddah, Djamé, Reut Tsarfaty, Sandra Kübler, Marie Candito, Jinho Choi, Richárd Farkas, Jennifer Foster, Iakes Goenaga, Koldo Gojenola, Yoav Goldberg, Spence Green, Nizar Habash, Marco Kuhlmann, Wolfgang Maier, Joakim Nivre, Adam Przepiorkowski, Ryan Roth, Wolfgang Seeker, Yannick Versley, Veronika Vincze, Marcin Woliński, Alina Wróblewska & Eric Villemonte de la Clérgerie. 2013. Overview of the SPMRL 2013 shared task: A cross-framework evaluation of parsing morphologically rich languages. In Proceedings of the fourth international workshop on Statistical Parsing of Morphologically-Rich Languages (SPRML IV). Seattle, WA.

Sekine, Satoshi & Michael Collins. 1997. EVALB bracket scoring program. http://www.%20cs.%20nyu.%20edu/cs/projects/proteus/evalb.

Seretan, Violeta. 2011. Syntax-based collocation extraction (Text, Speech and Language Technology 44). Dordrecht: Springer.

Sinclair, John. 1991. Corpus, concordance, collocation. Oxford: Oxford University Press.

Tesnière, Lucien. 1959. *Eléments de syntaxe structurale*. Klincksieck.

Tjong Kim Sang, Erik F. 2002. Introduction to the CoNLL-2002 shared task: Language-independent named entity recognition. In Proceedings of the 6th conference on Natural Language Learning (CoNLL) – volume 20, 1–4. Taipei, Taiwan.

Tomasello, Michael. 1998. Cognitive linguistics. In W. Bechtel & G. Graham (eds.), *A companion to cognitive science*. Basil Blackwell.

Tu, Yuancheng & Dan Roth. 2011. Learning English light verb constructions: Contextual or statistical. In Proceedings of the ACL 2011 workshop on MWEs, 31–39. Portland, OR.

Vincze, Veronika, István Nagy T. & Gábor Berend. 2011. Multiword expressions and named entities in the Wiki50 corpus. In Proceedings of the international conference Recent Advances in Natural Language Processing 2011, 289–295. Hissar, Bulgaria: Association for Computational Linguistics.

Vincze, Veronika, János Zsibrita & István Nagy T. 2013. Dependency parsing for identifying Hungarian light verb constructions. In Proceedings of the sixth International Joint Conference on Natural Language Processing (IJCNLP), 207–215. Nagoya, Japan: Asian Federation of Natural Language Processing. http://aclweb.org/anthology/I13-1024.

Weeds, Julie, James Dowdall, Gerold Schneider, Bill Keller & David Weir. 2007. Using distributional similarity to organise biomedical terminology. In Fidelia
M. Constant, G. Eryiğit, C. Ramisch, M. Rosner & G. Schneider

Ibekwe-SanJuan, Anne Condamines & M. Teresa Cabré Castellví (eds.), *Appli-cation-driven terminology engineering*. Amsterdam/Philadelphia: Benjamins.

Wray, Alison. 2008. *Formulaic language: Pushing the boundaries*. Oxford University Press.

Yamada, Hiroyasu & Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In *Proceedings of the International Workshop on Parsing Technologies (IWPT)*, vol. 3, 195–206. Nancy, France.
# Chapter 7

# Investigating the effect of automatic
MWE recognition on CCG parsing

Miryam de Lhoneux

Uppsala University

Omri Abend

Hebrew University of Jerusalem

Mark Steedman

University of Edinburgh

We investigate the use of automatic Multiword Expressions (MWEs) recognition in parsing with Combinatory Categorial Grammar. We transform the representation of MWEs in CCGbank by collapsing them to one token. Our model significantly outperforms the baseline on the transformed gold standard showing the benefit of having this information at training time. It also performs significantly better on the transformed gold standard when the transformation is done before parsing as opposed to after parsing which shows that it can help the parser at prediction time. We conclude that despite the limited settings (our transformation algorithm is only able to deal with MWEs that do not cross constituent boundaries), our method can lead to improvements. We obtain different results with MWE recognisers that detect different types of MWE and therefore emphasize the need to experiment with different recognisers to find out which ones this method is best suited to.

# 1 Introduction

## 1.1 Motivation

Multiword Expressions (henceforth MWE(s)) are increasingly receiving attention in NLP. They represent a wide variety of phenomena with different properties but are generally agreed to be a group of multiple lexemes which have some

<figure><img src="image_57.png" /></figure>
level of idiomaticity or irregularity (Sag et al. 2002). They represent varied phenomena but, due to this irregularity, they are all generally considered a problem for NLP tasks and they are often a problem for syntactic parsing.

Recent research is showing that information about MWEs can help the syntactic parsing task (Nivre & Nilsson 2004; Korkontzelos & Manandhar 2010) and inversely, information about syntactic analysis helps MWE identification (Green et al. 2013; Weller & Heid 2010; Martens & Vandeghinste 2010). Working on either of the tasks by using information from the other has thus proven to be a useful thing to do and adding MWE information to the syntactic parsing task has proven useful in that it has helped increase parsing accuracy. Work on adding MWE information to syntactic parsing so far has been restricted to certain types of MWEs (multiword nouns, numerical expressions and compound function words in Nivre & Nilsson (2004), compound nominals, proper names and adjective-noun constructions in Korkontzelos & Manandhar (2010)) and hence leaves room for improvement.

Combinatory Categorial Grammar (henceforth CCG) is a strongly lexicalized formalism that is increasingly being used for parsing in NLP applications because of its computational and linguistic properties and because CCG parsers perform relatively well on the Penn Treebank (PTB). To give just a few examples, CCG is used in Machine Translation (e.g. Birch et al. 2007), sentence realization (e.g. White 2006), semantic parsing and language acquisition (e.g. Krishnamurthy & Mitchell 2012), open-domain question answering and entailment (e.g. Lewis & Steedman 2013).

For these reasons, CCG parsing is an ideal framework to carry on the work on the interaction between syntactic parsing and MWEs and because CCG is a lexicalized formalism and thus encodes a lot of information in the lexicon, it would be useful to work on it by providing it with information about MWEs.

## 1.2 Aims

No work so far has tried to use MWE information to improve CCG parsing which is what we intend to do in this work. Different approaches to using MWE information for improving syntactic parsing have been conducted so far with different syntactic models. We conduct one of them which will be argued to be far from ideal but a necessary first step useful to build a sound baseline. The approach we pursue consists in altering training and test data, i.e. transforming the representation of MWEs so that they form one lexical item in them (and hence retokenize the sentence). We experiment with different MWE recognition methods so as to
find out if the approach works better with certain types of MWEs than with others.

The two research questions we therefore try to answer are first whether or
not we can improve CCG parsing with MWEs and second whether or not apply-
ing the same transformation approach to different types of MWEs can lead to
different results.

1.3 Overview of the chapter

We give an overview of the background literature to further support our motiva-
tions and elaborate on the research questions in Section 2. We then explain and
motivate the methodology we propose to use in order to answer the research
questions in Section 3. We present our experiments and results in Section 4. We
conclude from our study and propose avenues of research in Section 5.

2 Background

## 2.1 Multiword expressions

MWEs is an umbrella term that has been used to characterize a wide variety
of phenomena. The most commonly acknowledged definition of this term since
Sag et al. (2002) is that it is a group of multiple lexemes which have some level
of idiomaticity or irregularity. The multiple lexemes in a MWE are called MWE
units in the remainder of this chapter for convenience. This idiomaticity may be
lexico-syntactic such as in the unusual coordination of a preposition and an ad-
jective in *by and large*. It may be semantic such as in the idiom *kick the bucket* in
which the meaning of the whole is not dividable into the meaning of the parts. It
may be pragmatic such as in *good morning* which has a meaning attached to the
situation in which it is said. Finally, it may be statistical such as the collocation
*strong coffee* in which both units occur more frequently than expected.

Different MWE types present different properties. They vary in flexibility: words may appear between the units of a flexible collocation (*strong home-made coffee*, for example) but not between the units of a lexically fixed figurative expression such as *it's raining cats and dogs*. They also vary in compositionality: *Strong coffee* is fully compositional whereas *kick the bucket* is not and *spill the beans* is semantically decomposable, i.e. the meaning of the whole is not predictable from the meaning of the parts but can be decomposed into its parts: if *spill* is interpreted as *reveal* and *the beans* as *the secret* (Nunberg et al. 1994). Despite these varied properties they are all generally agreed to be hard to deal with in NLP
applications (Sag et al. 2002) and the importance of dealing with them properly has been increasing over the past decade. As described at length in Kim's (2008) thesis, "dealing with" MWEs consists in developing systems and models for various kinds of tasks. For syntactic analysis, it is important to identify them in text and extract them to a dictionary. For semantic understanding, it is important to measure their compositionality, classify and interpret them.

## 2.2 Combinatory Categorial Grammar

### 2.2.1 Presentation

Combinatory Categorial Grammar (Steedman 2000) is a strongly lexicalized grammar formalism which is currently gaining popularity in the NLP community.

CCG was built with the intent of being linguistically aware as well as computationally tractable partly as a reaction to transformationalist ideas which were predominant in formal grammars at the time. It differs from the latter mainly in having one component including syntactic and semantic information instead of having separate modules for each in the grammar. Similarly, instead of having a large amount of rules and a lexicon as is the case in traditional grammars, it has a small set of universal rules and a lexicon which encodes most syntactic information. For the sentence *John buys shares*, a traditional grammar has information in the lexicon: that *John* is an NP, that *buys* is a verb, that *shares* is an NP, and in the grammar: that a V and an NP form a VP and that an NP and a VP form a sentence S, as in Figure 1. By contrast, for the same sentence, CCG has information in its lexicon that *John* is an NP, that *shares* is an NP and that *buys* first takes an NP to its right then an NP to its left to form a sentence S, as in Figure 2.

<figure><img src="image_58.png" /><figcaption>Figure 1: PTB-style tree</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>Figure 2: CCG tree</figcaption></figure>
Without going into too much detail about how this works, lexical categories
work either as functor or as argument and a set of combinatory rules allow them
to combine. For example, the category $(S\NP)/NP$ works as a functor that takes
an NP to the right (indicated by the forward slash followed by an NP). The cate-
gory of *buys* therefore can combine with the category of *shares* to result in the
category $S\NP$ which in turns takes an NP argument to the left (indicated by the
backslash followed by an NP), which it finds in the category of *John* to form a
sentence S.

This grammar architecture allows CCG to deal elegantly with long-range de-
pendencies. Instead of adding a level of representation in the form of a trace as in
Figure 3, the grammar has universal rules which allow the combination of lexici-
cal items, as shown in Figure 4. This has computational advantages and linguistic
plausibility: linguistics is increasingly adopting a view of grammar where syntax
and the lexicon are two modules that are not completely separate in the grammar
but instead interact with each other. It is a tenet of the recently emerging frame-
work of Construction Grammar (Hoffmann & Trousdale 2013). These linguistic
and computational properties have made it a widely used framework across NLP
research.

<figure><img src="image_60.png" /><figcaption>Figure 3: PTB-style tree</figcaption></figure>
<figure><img src="image_61.png" /><figcaption>Figure 4: CCG tree</figcaption></figure>

### 2.2.2 CCG parsing

The first efficient statistical model was the generative model built by Hockenmaier & Steedman (2002) and extended to a discriminative model by Clark & Curran (2007). Both use CCGbank (Hockenmaier & Steedman 2007), a CCG converted version of the PTB. Both models perform close to state-of-the-art although with simpler statistical models which is argued by the authors to be the result of having a more expressive grammar than the PCFGs used by state-of-the-art parsers.

## 2.3 Syntactic parsing and multiword expressions

As mentioned in Section 2.1, the identification of MWEs is important for syntactic analysis. Because they have unusual properties, however, their analysis can be quite problematic. The question of how to deal with MWEs for syntactic parsing has been raised by many researchers. It has been approached in different ways. Researchers working with precision grammars such as HPSG for example have accommodated the lexical entries for MWEs in the lexicon so that MWEs are not a problem for parsing. Researchers on data-induced grammars have accommodated the testing and/or training data before parsing. Recent research has
proposed to both change the lexicon and the parsing algorithm. A last recent approach is to learn MWE representations and dependency trees jointly. We briefly describe each of these approaches in turn. We describe the second approach in more details than the other two because this is the one we use in this work for reasons explained in Section 3.1.

## 2.3.1 Transforming the lexicon

Different types of lexical entries have been proposed for MWEs in the grammar. A lot of research proposes to simply analyse all MWEs as “words-with-spaces”, i.e. group the MWE units together in the syntactic analysis. This analysis has been argued against by many. Sag et al. (2002) have suggested sophisticated ways of representing the different MWE types in a grammar, which have been partly implemented within the framework of the precision grammar HPSG, as described by Copestake et al. (2002). Zhang et al. (2006) established that MWEs are a tremendous source of parse failures when parsing with a precision grammar such as HPSG and henceforth proposed a way of using this information to identify new MWEs and enrich a lexicon: they suggested using parse failures to predict the existence of a MWE.

## 2.3.2 Transforming the data

Since the seminal work of Nivre & Nilsson (2004), research has shown that treating MWEs as one token or a “word-with-spaces” in test and/or in training data before parsing and/or training leads to an improvement in parsing accuracy. Nivre & Nilsson (2004) have shown that to be true for deterministic dependency parsing and Korkontzelos & Manandhar (2010) have shown that to be true for shallow parsing.

The approaches adopted in these two papers are quite different and we describe each in turn.

### 2.3.2.1 Transforming training and test data

Nivre & Nilsson (2004) created two versions of a treebank, one in which MWEs are annotated as if compositional and one in which they are joined as one lexical item. They show that training a parser on the second version of the treebank leads to a better parsing accuracy. They use a corpus with manual MWE annotation to create both versions of the treebank and hence simulate “perfect” MWE recognition. MWE annotation, however, only consists in a few MWE types so it is not comprehensive. They report improvement in parsing accuracy of the MWEs
themselves but also of their surrounding syntactic structure. They opened the
gate for improving syntactic parsing with MWE information but left many ques-
tions unanswered. For example, the question of whether or not their results port
to other syntactic parsing models, whether or not the full potential they obtained
with "perfect" recognition of MWEs can be obtained with an automatic recog-
niser and whether or not this potential can be increased when recognising other
types of MWEs. Some of these questions have been partially addressed since then.
Constant et al. (2012) have shown that with an automatic recogniser, the pars-
ing accuracy improvement is not as dramatic as predicted by Nivre & Nilsson
(2004). Eryiğit et al. (2011) found out that in the case of a morphologically rich
language (e.g., Turkish), the approach works with some types of MWEs but not
with others.

2.3.2.2 Transforming test data

Korkontzelos & Manandhar (2010) reported similar parsing accuracy improve-
ments for shallow parsing, showing that Nivre & Nilsson (2004)'s results do seem
to port to at least one other parsing model. Their technique is, however, quite dif-
ferent. They created a corpus containing a large number of pre-selected MWEs
(randomly chosen from WordNet) and converted it to a version in which the
MWE units are collapsed to one lexical item. They POS-tag the two versions of
the corpus before parsing each. They subsequently analyse the differences in out-
put. In order to do so, they randomly select a sample of output from both parsed
corpora and build a taxonomy of changes they observe from one to the other. For
each class in the taxonomy, they determine whether the change in output led to
increased accuracy, decreased accuracy or did not change the accuracy. They au-
tomatically classify the rest of the output data and observe an overall increase in
accuracy. Their work not only confirms the results obtained from previous work
but also provides an insightful qualitative analysis of changes obtained with their
method. They believe the improvement in accuracy is partly due to the fact that
the parsing model backs off to POS-tags for rare and unseen words. When MWE
units are collapsed to one token, that token is not known by the parser but it still
gets assigned a sensible POS-tag because the POS-tagger uses contextual infor-
mation.

2.3.3 Transforming the lexicon and the parsing algorithm

A lot of work has shown that although MWE information improves syntactic
parsing, the reverse is also true: syntactic analysis improves MWE identification.
Green et al. (2013) successfully tuned a parser for MWE identification, Weller & Heid (2010) and Martens & Vandeghinste (2010) showed that using parsed corpora for MWE identification is beneficial. These findings led Seretan (2013) to propose that neither accommodating the grammar with MWE information, nor recognising MWEs in raw text as a help to parsing are appropriate ways of dealing with the issue of MWEs in syntactic parsing because neither approach takes advantage of the fact that MWE information and syntactic analysis are mutually informative. She proposes instead to have a MWE lexicon and to deal with potential MWEs during parsing.

## 2.3.4 Joint learning of MWE identification and parsing

Based on the same observation that the tasks of MWE identification and parsing can inform each other, Constant & Nivre (2016) propose to learn both jointly. They use corpora that both have dependency and MWE annotations and modify the parsing algorithm so as to learn both representations jointly. They show that this approach is effective.

## 2.3.5 Advantages and caveats of the different approaches

All of these researchers have shown the importance of MWEs for syntactic parsing but all of the approaches presented have caveats. Research on HPSG seems to have found the most sophisticated methods of dealing with MWEs but parsing with precision grammars is known to be much less robust (Zhang & Kordoni 2008) than parsing with data-induced grammars which make it a suboptimal solution for practical parsing. Learning MWE representations and syntactic parsing jointly is probably the most promising approach but it requires a lot of manual work since it requires a corpus that is annotated both with MWEs and dependency trees. As far as other solutions are concerned, they are often very much limited by the type of MWEs that have been dealt with. All other solutions presented as a matter of fact concentrate on a few types of MWEs. However, as argued by Kim (2008), because of the different but interrelated properties of MWEs, it is neither appropriate to try and generalize from MWEs and find a single representation which works for all types, nor is it appropriate to deal with each MWE type at a time. An approach for improving syntactic parsing on all MWE types is still lacking and previous approaches leave the question of whether the results can be reproduced with different types of MWEs unanswered.
## 2.4 Research questions and objectives

In Section 2.3, it was said that MWE identification information improves syntactic parsing although current approaches to doing so leave room for improvement. Trying to improve syntactic parsing with MWE information therefore looks like a promising avenue of research. In Section 2.2, arguments for working with CCG parsing were put forward.

Very little attention has, however, been given to MWEs in CCG parsing. Constant & Curran (2009) modified CCGbank to have a better representation of verb-particle constructions but did not report any parsing accuracy improvement. No work has tried to establish whether CCG parsing accuracy could be improved by adding information about MWEs which is what we intend to do in this work. Our aim is twofold: we want to find out whether or not MWE information can improve CCG parsing and we wish to find out if using methods that have been used for a restricted set of types of MWEs can be extended to different types of MWEs.

# 3 Methodology

## 3.1 Approach

As explained in the last section, in this work we concentrate on an approach that consists in transforming the representation of MWEs in treebanks. In Section 2.3.2, two different versions of this kind of approach have been described. In the first, manual annotation is used to create two versions of the treebank. This left questions unanswered, two of which being whether or not the approach can work with automatic recognition and whether or not the approach can work with different types of MWEs. In this work, we conduct the type of approach described by Nivre & Nilsson (2004) using an automatic recogniser to answer the first of these questions in the context of CCG parsing. We also experiment with the recogniser by using different versions of it to answer the second of these two questions. This approach is especially interesting in that, as has been shown in Schneider et al. (2014) who attempted a comprehensive annotation of MWEs in a corpus, even manual annotation of MWEs is a difficult task and experimenting with different MWE recognisers could lead to interesting results.

Our approach therefore involves transforming both training and test data. Transforming the training data can help the parsing model learn more sensible representations of language. For example in the tree for *part of speech, of speech* is
considered a modifier of *part* as in Figure 5 which does not make much sense. Instead, grouping the three lexical items as in Figure 6 gives a better representation of this group of words.

<figure><img src="image_62.png" /><figcaption>Figure 5: Traditional tree for *Part of Speech*</figcaption></figure>

<figure><img src="image_63.png" /><figcaption>Figure 6: Tree for *Part of Speech* where tokens are grouped</figcaption></figure>

Transforming the test data by for example collapsing the three lexical items *part*, *of* and *speech* to one token *part+of+speech* can help the parser make sensible decisions locally by telling it to consider the three words as one. For example, if this token is followed by a coordinator, the parser knows that coordinating one of the units is not a possibility. In the sentence *it gives part+of+speech and lemma information*, the parser cannot coordinate *speech* with *lemma* which would be a possibility otherwise. Transforming MWEs in training and test data leads to two different effects of adding MWE information to the syntactic parsing pipeline and it is best if we can differentiate both in the experiments. We call the first type of effect *training effect* and the second *parsing effect*. We repeat the definition of these two effects below.

**Training effect:** the parser learns more sensible representations of MWEs and its units.

**Parsing effect:** the parser is helped locally in its decision by considering the MWE units as one unit.
## 3.2 Parsing model

As mentioned in Section 2.2, both generative and discriminative models exist for parsing with CCG. There are different generative models with different properties. We chose to use StatOpenCCG, developed by Christodoulopoulos (2008) and recently further expanded by Deoskar et al. (2014) because of its ease of use, flexibility and fast training. The expansion of the parser by Deoskar et al. (2014) is particularly well suited to our purposes: it was extended so that it works better on unknown lexical items. Joining lexical items to one token will increase the sparsity of the data and being able to deal with unknown data is therefore a concern for our approach. More particularly, the model proposed by Christodoulopoulos (2008) and Deoskar et al. (2014) is based on one of Hockenmaier (2003)'s models called LexCat which conditions probabilities on lexical categories. Deoskar et al. (2014) make use of this LexCat model instead of the fully lexicalized model which conditions it on words precisely so that the parser is better equipped to deal with unseen lexical items. They introduce a smoothed lexicon to deal with these. They POS-tag the test data in a pre-processing stage and use POS-information to determine the lexical categories of words by using probabilities of lexical categories that appear with each POS-tag of unseen word in the seen data. Because, as mentioned in Section 2.3.2.2, Korkontzelos & Manandhar (2010) have shown that POS-tags assigned automatically to MWEs were useful when parsing, the LexCat model therefore looks ideal for our purposes. We follow Deoskar et al. (2014) in using the C&C tools (Curran et al. 2007) to POS-tag our test data so as to have a model that is comparable with theirs.

## 3.3 Extending the parsing model with MWE information

As explained in Section 3.1, the objective is first to recognise MWEs in the unlabeled version of CCGbank and then to collapse MWEs to one lexical item in the annotated version of the treebank and in the unlabeled test data. The MWE recognition part is described in Section 3.3.1 and the CCGbank conversion is described in Section 3.3.2.

### 3.3.1 Recognising MWEs

For MWE recognition, we use a tool developed by Finlayson & Kulkarni (2011). It can be used to build an index of MWEs with information about their probability. It can also be used with a default index which contains all the MWEs and inflections extracted from Wordnet 3.0 and Semcor 1.6 and statistics for each MWE. There are three different tools of interest to us. Simple detectors detect MWEs in
text. There is a detector to find proper nouns, one to find all types of MWEs that are in the index, one that finds MWEs that contain only stop words, etc. These simple detectors can also be combined to form a complex detector. There are filters which filter the results of detectors. One for example only accepts MWEs that are continuous, one throws out MWEs which have a score under a certain threshold, one only keeps MWEs under a certain length. The last tool we need is called a RESOLVER and it resolves conflicts when lexical items are assigned to more than one MWE. Conflicts can be resolved in different ways: one resolver picks the leftmost MWE. For example, let us say we have an input sentence that includes *new york life insurance*. If the MWE index contains *new york life* and *life insurance*, the resolver will return *new york life* but will not consider *insurance* as part of a MWE. Another resolver picks the longest matching MWE. For example, let us say we have an input sentence which contains *new york stock exchange*. If the MWE index contains *stock exchange*, *new york* but also *new york stock exchange*, the longest matching resolver will return *new york stock exchange* as a match.

Let us take the following sentence as an example of input for a resolver:

(1) Mr. Spoon said the plan is not an attempt to shore up a decline in ad pages in the first nine months of 1989; Newsweek's ad pages totaled 1,620, a drop of 3.2% from last year, according to Publishers Information Bureau.

The resolver returns a list of its MWEs from left to right. In the case of our example (1), the output for example looks like this:

(2) mr_spoon, shore_up, according_to, publishers_information_bureau

The presented protocol can work with any type of MWE recogniser, provided that it is filtered to output only continuous MWEs and resolved so that any word can only appear in one MWE. This library therefore serves our purposes perfectly since it leaves quite a lot of room for experiments. Experiments are described in Section 4.

### 3.3.2 Transforming the treebank

The algorithm collapses the MWE units to one node when they form a constituent in the tree. The label of the node is the label of that constituent. For example, given the MWE *publishers_information_bureau* and the subtree in Figure 7, the algorithm returns the subtree in Figure 8.
<figure><img src="image_64.png" /><figcaption>Figure 7: Original subtree</figcaption></figure>

<figure><img src="image_65.png" /><figcaption>Figure 8: Transformed subtree</figcaption></figure>

The algorithm discards MWEs if they do not form a constituent in the tree. An example of tree in which MWE units (e.g., *according to*) are not siblings in the tree is given in Figure 9. The ideal way in which it should be transformed is given in Figure 10 but attempting to find an algorithm which would work for all non-sibling cases is beyond the scope of this work. We tried our algorithm with a good recogniser, collected statistics and found that 79.5% of the cases (42,309/53,208) were siblings in the tree which we considered a good basis for experimentation. Note, however, that modifying those non-sibling MWEs would make bigger changes to the tree as it would not only remove the lexical categories of MWE units but it would additionally remove the parent category of the MWE units involved and create a new category for the whole MWE. As we will see in Section 4, dealing only with sibling MWEs leads to slight improvements, we hypothesize that an improved algorithm that can deal with non-sibling MWEs can lead to more substantial improvements.

<figure><img src="image_66.png" /><figcaption>Figure 9: Tree with MWE units that are not siblings</figcaption></figure>

Because, as explained in Section 3.5, we evaluate our method on dependency trees (which can be read off CCG trees), we also need to modify the gold standard dependency trees. Transforming dependency trees involves merging nodes
<figure><img src="image_67.png" /><figcaption>Figure 10: Ideal MWE non-sibling transformation</figcaption></figure>

in the graph and changing edges according to the new nodes. When the nodes
are merged, edges from the original dependency graph fall into three different
categories. Let us take the dependency graph in Figure 11 as an example in which
*Mr. Vinken* is a MWE. There are edges between two units of a MWE such as the
one between *Mr.* and *Vinken*. We call these **INTERNAL EDGES** for convenience. Our
algorithm removes them as shown in Figure 12. There are edges between a MWE
unit and another word in the sentence such as the edge between *Vinken* and *is*.
We call this type of edge a **MEDIATING EDGE**. In the transformed graph, the whole
MWE becomes the node of that incoming or outgoing edge. The edge between *is*
and *chairman* does not connect any MWE and does not need changing. We call
it **EXTERNAL EDGE**.

<figure><img src="image_68.png" /><figcaption>Figure 11: Dependency graph</figcaption></figure>

<figure><img src="image_69.png" /><figcaption>Figure 12: Transformed dependency graph</figcaption></figure>

The downside of this algorithm is that it can create cyclic dependencies be-
tween lexical items, i.e. two nodes are connected by two edges going in the op-
posite direction. We tested the algorithm on the CCGbank and found that in
practice this is not a major issue: only 7 cyclic dependencies were created in the
~48,000 sentences.

3.4 Training and parsing

We follow the tradition and use sections 01–22 of CCGbank for training, section 00 for development and section 23 for testing.

Using the same parameters as in Deoskar et al. (2014) to train and parse the
test data, we obtain around 87% of correct lexical categories, which is similar to
the result they report. This model serves as our baseline and we henceforth call it *model*<sub>A</sub>.

For each experiment, we run the MWE recogniser on an unlabeled version of
the CCGbank<fnref n="1" />. We then apply our cascaded algorithms described in the previous
section to every sentence from the CCGbank. We train the model and parse the
test file. We call the transformed treebank CCGbank<sub>B</sub> and the model trained on
it *model*<sub>B</sub>.

3.5 Evaluation

The traditional parsing accuracy metric PARSEVAL has been argued (for example
by Clark & Hockenmaier (2002)) to be too harsh on CCG derivation trees because
they are always binary, as opposed to PTB-style trees which can have flat con-
structions with more than one branching node. This binary nature of CCG trees
make them prone to having more errors. Consequently evaluation of dependen-
cies has generally been preferred for CCG parsing. As further argued by Clark
& Hockenmaier (2002), it also makes sense to use dependencies to evaluate CCG
parsing since one of the advantages of CCG over other formalisms is precisely
its treatment of long-range dependencies.

In order to evaluate our models, we can thus extract dependencies from the
parsed files and compare them with the gold standard. Because we changed the
gold standard as compared to *model*<sub>A</sub> (as defined in the previous subsection),
however, the results obtained from comparing our parsed files with our gold
standard are not directly comparable with the results obtained when applying
the same evaluation scheme to *model*<sub>A</sub>. Therefore, we cannot directly compare
*model*<sub>A</sub> with our *model*<sub>B</sub> (as defined in the previous subsection) which is essen-
tial in answering our research questions. Instead, we have to transform the data
of one of the models so as to compare each of the models with the same gold
standard. Because we assume that we have created a sensible gold standard with
our transformation algorithm, we mainly use gold standard<sub>B</sub> for evaluation.

As mentioned in Section 3.1, transforming training and test data can lead to
two different effects which can lead to an improved parsing accuracy, i.e. train-
ing (the parser learns useful information during training) and parsing effects (the
trained parser is helped in its decisions by MWE information) which we would
like to differentiate. This can be achieved by conducting different experiments
with our existing models. We can assess training effect by testing whether or
not *model*<sub>B</sub> can outperform *model*<sub>A</sub> when evaluated on the same gold standard.

<footnote n="1">¹We created an unlabeled version of CCGbank from the tree leaves to make sure the data is compatible with the trees we work with when transforming trees.</footnote>
We can assess parsing effect by testing whether or not *model*<sub>A</sub> can outperform
itself when given transformed test data. We discuss these evaluation schemes in
Section 3.5.1.

If there is training and/or parsing effect, we can assume that automatic recog-
nition of MWEs can be used to improve syntactic parsing. We can verify this
by testing whether or not we can use information from *model*<sub>B</sub> to outperform
*model*<sub>A</sub> on gold standard<sub>A</sub>. We use a second evaluation scheme where we com-
bine information from output *model*<sub>A</sub> and output from *model*<sub>B</sub> (henceforth
called MODEL COMBINATION) to test this which we discuss in Section 3.5.2.

As mentioned in Section 2.4, we not only want to know whether or not infor-
mation about MWEs can help CCG parsing but we are also interested in find-
ing out whether or not different types of MWEs impact parsing accuracy in
different ways. As will be explained in Section 4, we created different versions
of CCGbank<sub>B</sub> and different versions of *model*<sub>B</sub> with these. Because we created
different gold standard for each of these models, they cannot directly be com-
pared. Instead, comparing how different *model*<sub>B</sub>s can improve *model*<sub>A</sub> is possible
by comparing their combination with it against gold standard<sub>A</sub>. Again then we
can use model combination and combine information from output from *model*<sub>A</sub>
with information from output *model*<sub>B</sub>. We compare this combined model
output against gold standard<sub>A</sub> and compare the results when combining *model*<sub>A</sub>
with different versions of *model*<sub>B</sub>. We discuss how this can be achieved in Sec-
tion 3.5.3.

## 3.5.1 Assessing training and parsing effects

Modifying the output from *model*<sub>A</sub> so that it is comparable with the gold stan-
dard from *model*<sub>B</sub> is straightforward: we just need to apply the transformation
algorithms to the output from *model*<sub>A</sub> with the MWEs found in the test data. We
can also test *model*<sub>A</sub> on data transformed before parsing.

3.5.1.1 Parsing effect

Testing whether there is a parsing effect can be done by testing whether or not
*model*<sub>A</sub> can perform better on test data transformed before parsing than on test
data transformed after parsing. We conduct this evaluation. There is a caveat
in this evaluation, however: we are using information from the gold standard
in the test data, i.e. we know which MWEs are siblings in the test data. This
introduces an artefact which makes the results somewhat difficult to interpret:
the transforming before parsing method has sibling information which the trans-
forming after parsing method does not. There can be parsing and sibling effects
and the two cannot be decoupled. A way to circumvent this problem is to transform MWEs regardless of their sibling status (i.e. treat all detected MWEs as if they were siblings) and compare the model when we transform before parsing with the model when we transform after parsing. Transforming all MWEs in unlabeled test data is straightforward. As mentioned in Section 3.3.2, we do not have an algorithm to transform MWEs that are not siblings in trees so we cannot transform the output parse trees. However, since we are working only with dependencies for evaluation, it is possible to transform all MWEs in all the dependencies of the sentence. The problem with this evaluation is that the output cannot perform well on gold standard<sub>B</sub> because it is not tokenized in the same way and we treat dependencies wrongly tokenized as errors. However, both transforming before and transforming after parsing suffer from the same problem and the comparison between the two is fair.

### 3.5.1.2 Training effect

Testing whether there is a training effect consists in comparing the results of *model*<sub>A</sub> on transformed data with the results of *model*<sub>B</sub> on transformed data. In this evaluation, the caveat that we are using information from the gold standard in the test data can also be considered problematic because *model*<sub>B</sub> is trained on data with information about siblings. This information is unseen by *model*<sub>A</sub>. We therefore test both models on data where only siblings are transformed (called GOLD TEST for convenience) and on data where all MWEs are transformed (called FULLY TRANSFORMED TEST for convenience). Again, the problem with this evaluation is that the output cannot perform well on gold standard<sub>B</sub> because it is not tokenized in the same way. Again, however, both models suffer from the same problem and the comparison between the two is fair.

### 3.5.2 Verifying whether or not automatic recognition of MWEs can improve CCG parsing on the original gold standard

Results which will be discussed in Section 4 seem to indicate that there is both a training and a parsing effect and that *model*<sub>B</sub> performs better than *model*<sub>A</sub> on some dependencies. Our findings support the claim that automatic recognition of MWEs can improve CCG parsing. These results, however, led us to want to verify whether or not *model*<sub>B</sub> can improve the score on the standard evaluation benchmark, i.e. on gold standard A. This involves “detransforming” the output from *model*<sub>B</sub> and splitting MWEs back into their units. However, by transforming the data, we have lost information about some dependencies in the sentence.
We have no *internal edges* (edges between MWE units of the same MWE) and when there is a *mediating edge* (edges between MWE units of any MWE and other words in the sentence) we do not know which MWE unit of the MWE should the incoming or outgoing node of that edge. In Figure 12 reproduced in Figure 13 for convenience, we do not know whether the label between *is* and *mr._vinken* should come from *mr* or *vinken*. For this reason, we propose to combine information obtained from parsing the test data with our transformed model *model*<sub>B</sub> with information obtained from parsing the test data with the original model *model*<sub>A</sub>. We therefore take some dependencies from *output*<sub>A</sub> and some from *output*<sub>B</sub>.

<figure><img src="image_70.png" /><figcaption>Figure 13: Transformed dependency graph</figcaption></figure>

*External edges* can be taken from *output*<sub>B</sub>. *Internal edges* do not exist in *output*<sub>B</sub>. Hence we propose to take them from *output*<sub>A</sub>. For *mediating edges*, there are different possibilities. We can take them from *output*<sub>A</sub> and therefore only test whether or not *model*<sub>B</sub> performs better than *model*<sub>A</sub> on *external edges*. We call this combination method *medFromA*. If we want to test *model*<sub>B</sub> on *mediating edges*, we can take *mediating edges* from *output*<sub>B</sub>. For this to work, the model combining algorithm needs to choose one node as the incoming or outgoing node of that edge: in our example, it should either be *Mr.* or *Vinken*. We use two additional combination methods. We use one in which the rightmost node is chosen as incoming or outgoing node for *mediating edges* from *output*<sub>B</sub> which we call the *rightmostMed* scheme. We also use one in which the leftmost node is chosen which we call the *leftmostMed* scheme. In order for the model combining algorithm to work, we need to recover information about MWEs and their units and hence to know for each dependency if we are dealing with an *internal*, *external* or *mediating edge*. This can easily be done because MWE and their units are annotated in the unlabeled data.<fnref n="2" />

When these models are combined in these three different ways, we have a new combined model that we can compare with *model*<sub>A</sub> on gold standard<sub>A</sub>. In this case, using “gold test” data is again problematic. As a matter of fact, if we use *output*<sub>B</sub> as obtained after parsing “gold test” data, we are using information obtained during the conversion of the gold standard and we are using a parsing

<footnote n="2">²Our MWE recogniser joins MWE units of a MWE by a “+” symbol.</footnote>
pipeline which is not fully automatic. In order to make sure that we can outperform *model*<sub>A</sub> in a fully automatic way, we can use parses of *model*<sub>B</sub> tested on the “fully transformed test” data set as described in Section 3.5.1, and combine them in the same three ways as described above.

### 3.5.3 Testing whether or not different MWE types impact the results differently

As mentioned before, we use different MWE recognisers to create different versions of CCGbank<sub>B</sub> and hence different versions of *model*<sub>B</sub>. Because we created a different gold standard for each, results from different models are not directly comparable. We can, however, convert output parses using the model combination algorithm described in Section 3.5.1 and test each model against gold standard<sub>A</sub>. In this way, different versions of *model*<sub>B</sub> can be compared.

## 3.6 Summary of the experimental setup

Figures 14 and 15 summarize our experimental setup.

<figure><img src="image_71.png" /><figcaption>Figure 14: Pipeline of an experiment on one version of one application of MWE recognition to the parsing pipeline with all the evaluation schemes that can be applied to it. The transforming before parsing of *model*<sub>A</sub> (see Section 3.5.1) is omitted for clarity and given in Figure 15.</figcaption></figure>
# 7 Investigating the effect of automatic MWE recognition on CCG parsing

<figure><img src="image_72.png" /><figcaption>Figure 15: Pipeline of the “transforming before parsing” against the “transforming after parsing experiment.”</figcaption></figure>

In Section 2, we motivated our study and identified two research questions: whether or not information about MWEs can improve CCG parsing and whether or not different types of MWEs can influence parsing accuracy in different ways. In this Section, we proposed a methodology for testing this. We refined the first research questions: what we want to find out is whether or not automatic recognition of MWEs can improve CCG parsing. Additionally, we separated it into two further research questions: whether we can observe a parsing effect (the parser is helped in its decisions by transformed data) and/or whether we can observe a training effect (the parser learns something useful). We proposed to use different MWE recognisers to answer the second question. When defining an algorithm for transforming the treebank, however, we could not find a straightforward algorithm to transform MWEs that are not siblings in the tree and decided to settle for an algorithm that only transforms siblings. This led to further complications in the evaluation schemes because it makes it harder to give a fair evaluation of our models. We found ways to circumvent the problems: we proposed different evaluation schemes together with cross-validations. We now turn to the results of our experiments.

# 4 Results

In this section, we look at each of the research questions in turn. To assess statistical significance of our best results, we use a one-tailed randomized shuffling test with 10,000 iterations. We use the software created by Padó (2006) (slightly modified in order to make it a one-tailed test instead of a two-tailed one) for our tests.
## 4.1 MWE recognition

We use the jMWE library described in Section 3.3.1 with the default index which contains MWEs from Wordnet 3.0 and Semcor 1.6. We use the library's three different tools which were explained in that section. Those tools are detectors which detect MWEs in text, filters which filter through the results of one or more detectors and resolvers which resolve conflicts between MWEs when one word is assigned to more than one MWEs by the detector.

We use the following tools:

* Detectors:

- Proper Nouns: detects proper nouns, like *wall street*.

- Stop words: detects MWEs that only contain stop words, like *instead of*.

- Exhaustive: finds all MWEs that are in the index.

* Filters:

- MoreFreqAsMWE: only keeps MWEs if its units appear more often together than apart in the corpora in which they were collected.

- ConstrainLength: only keeps MWEs that have 2 units.

* Resolvers:

- Longest: always picks the longest matching MWEs.

- Leftmost: picks the MWE that starts earliest in the sentence.

We build 5 different MWE recognisers with different combinations of these tools. This means that the study is by no means exhaustive. Information about our recognisers and statistics about the MWEs they detect are summarized in Table 1. The numbers in column “ID” denote the recognisers used in the remainder of this section. Similarly, each *model*<sub>B</sub> is denoted by the recogniser which was used to train it as indicated by this number.

## 4.2 Can we improve CCG parsing accuracy with automatic MWE recognition?

As explained in Section 3.5, we use different evaluation schemes to answer this question. First we evaluate *model*<sub>B</sub> and *model*<sub>A</sub> against gold standard<sub>B</sub> and determine whether there is training and/or parsing effects. Then we verify whether
<table><caption>Table 1: Description (detector, filter and resolver) of MWE recognisers used and statistics of MWEs collected with them in the treebank</caption><thead><tr><th>ID</th><th>detector</th><th>filter</th><th>resolver</th><th>MWE #</th><th>Sibling #</th><th>Sibling %</th></tr></thead><tbody><tr><td>1</td><td>Exhaustive</td><td>MoreFreqAsMWE</td><td>Longest</td><td>53,208</td><td>42,309</td><td>79.51</td></tr><tr><td>2</td><td>Exhaustive</td><td>MoreFreqAsMWE</td><td>Leftmost</td><td>51,543</td><td>21,532</td><td>41.85</td></tr><tr><td>3</td><td>Proper Nouns</td><td>no filter</td><td>Longest</td><td>32,583</td><td>28,068</td><td>86.14</td></tr><tr><td>4</td><td>Exhaustive</td><td>ConstrainLength</td><td>Leftmost</td><td>49,587</td><td>19,984</td><td>40.30</td></tr><tr><td>5</td><td>Stop words</td><td>no filter</td><td>Longest</td><td>13,623</td><td>286</td><td>2.09</td></tr></tbody></table>

we can use *model*<sub>B</sub> to improve over *model*<sub>A</sub> on gold standard<sub>A</sub> by using model combination with *model*<sub>A</sub> and *model*<sub>B</sub>. We deal with each of these in turn. We test all evaluation schemes on all of our versions of *model*<sub>B</sub>. Results fluctuate according to the recognisers as discussed in Section 4.3. We give general remarks about results and report our best results in this Section.

### 4.2.1 Can representing MWEs as one token introduce a training effect?

In order to find out whether or not training data on an MWE-informed corpus can lead to an improved accuracy, i.e. leads to training effect, we compare the output of *model*<sub>B</sub> against the output of *model*<sub>A</sub> tested on the “gold test” data. 3 out of our 5 *model*<sub>Bs</sub> outperform *model*<sub>A</sub> on unlabeled<sub>B</sub>, although generally by a slight margin. The best results are obtained by *model*<sub>B3</sub> and are given in Table 2. *Model*<sub>B</sub> significantly outperforms *model*<sub>A</sub> by 0.24% (*p* = 0.006) which supports the hypothesis that there is indeed a training effect.

<table><caption>Table 2: Precision (P), recall (R), and F<sub>1</sub>-measure of unlabelled dependencies against gold standard B with recogniser 3</caption><thead><tr><th>model</th><th>test data</th><th>P</th><th>R</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>A</td><td>gold test</td><td><strong>84.53</strong></td><td>84.76</td><td>84.64</td></tr><tr><td>B3</td><td>gold test</td><td>84.48</td><td><strong>85.28</strong></td><td><strong>84.88</strong></td></tr></tbody></table>

Because using gold test data gives *model*<sub>B</sub> an unfair advantage, we also test these models on the “fully transformed test” data. In this case 3 of our 5 *model*<sub>Bs</sub> outperform *model*<sub>A</sub> again although by an even slight margin. The biggest difference in results is obtained with *model*<sub>B1</sub> and results are given in Table 3. Although the margin is smaller, *model*<sub>B</sub> still significantly outperforms *model*<sub>A</sub> by 0.15% (*p* = 0.047) which shows that there is a training effect.
<table><caption>Table 3: Precision (P), recall (R), and F₁-measure of unlabelled dependencies against gold standard B with recogniser 1</caption><thead><tr><th>model</th><th>test data</th><th>P</th><th>R</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>A</td><td>fully transformed test</td><td>73.15</td><td>72.38</td><td>72.77</td></tr><tr><td>B1</td><td>fully transformed test</td><td>73.08</td><td>72.74</td><td>72.92</td></tr></tbody></table>

### 4.2.2 Can representing MWEs as one token introduce a parsing effect?

In order to test whether there can be a parsing effect, we compare the output of *model*<sub>A</sub> when data are transformed before parsing with *model*<sub>A</sub> when data are transformed after parsing. In this case *model*<sub>B</sub> always outperforms *model*<sub>A</sub>. Our best results are shown in Table 4 in which *model*<sub>B</sub> highly significantly outperforms *model*<sub>A</sub> (*p* < 0.0001).

<table><caption>Table 4: Precision (P), recall (R), and F₁-measure of unlabelled dependencies against gold standard B with recogniser 1 when transforming before parsing uses gold sibling information and only siblings are transformed after parsing</caption><thead><tr><th>model</th><th>transformed</th><th>P</th><th>R</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>A</td><td>before parsing</td><td><strong>83.88</strong></td><td><strong>84.24</strong></td><td><strong>84.06</strong></td></tr><tr><td>A</td><td>after parsing</td><td>78.92</td><td>79.41</td><td>79.17</td></tr></tbody></table>

The problem with these results is that “transforming before parsing” method has gold standard information about siblings which the “transforming after parsing” method does not. In order to cross-validate our result, we transform all MWEs both before and after parsing and compare the results. In this case, *model*<sub>A</sub> when data are transformed before parsing outperforms *model*<sub>A</sub> when data are transformed after parsing only in one of the 5 cases which undermines a little the previous argument about the parsing effects showing that there can also be undesirable effects to transforming test data. It could, however, be partly due to the fact that we transformed non-siblings, which may have triggered errors during parsing. In any case, our best results still show a significant improvement with the “transforming before parsing” method over the “transforming after parsing” method. These results are obtained when using *recogniser<sub>3</sub>* and are given in Table 5. *Model*<sub>A</sub> transformed before parsing significantly outperforms *model*<sub>A</sub>
transformed after parsing by 0.20% (p = 0.008). This indicates that there can be a
parsing effect.

<table><caption>Table 5: Precision (P), recall (R), and F₁-measure of unlabelled dependencies against gold standard B with recogniser 3 when all MWEs are considered siblings</caption><thead><tr><th>model</th><th>transformed</th><th>P</th><th>R</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>A</td><td>before parsing</td><td>79.83</td><td>79.54</td><td>79.69</td></tr><tr><td>A</td><td>after parsing</td><td>79.38</td><td>79.60</td><td>79.49</td></tr></tbody></table>

### 4.2.3 Can we improve the parsing model on the original gold standard?

We now verify if we can also outperform the baseline on the untransformed gold standard. This means testing whether or not *model*<sub>B</sub> improves over *model*<sub>A</sub> on *external edges* and/or on *mediating edges*. We test this by combining dependency edges obtained from *model*<sub>A</sub> and *model*<sub>B</sub>. We combine these edges with 3 different methods. *Internal edges* are always taken from *model*<sub>A</sub> and *external edges* are always taken from *model*<sub>B</sub>. *Mediating edges* are taken from A in the *medFromA* evaluation and from B in the 2 other cases. In the *rightmostMed* evaluation, the rightmost MWE unit is always chosen as incoming or outgoing node and in the *leftmostMed* evaluation, it is the leftmost MWE unit that is always taken as incoming or outgoing node. Our best results are given in Table 6 in which *model*<sub>B</sub> only outperforms *model*<sub>A</sub> in the *medFromA* case by 0.13% which is not significant (p > 0.05). This seems to show that *model*<sub>B</sub> may perform better than *model*<sub>A</sub> on *external edges* but as far as *mediating edges* are concerned, the picture is unclear. If we take the *mediating edge* from B, it seems clearly better to choose the rightmost MWE unit as incoming or outgoing node (which is not surprising since compound nouns are almost always right-headed) but doing so does not seem to be a big help in parsing accuracy. *Model*<sub>B</sub> might perform better than *model*<sub>A</sub> on *mediating edges* if we had a better mechanism to recover the head word but with our simple method we cannot say whether or not this is the case.

In this result, *model*<sub>B</sub> is again helped in the parsing decisions by being told which MWEs are siblings. In order to test whether we can improve on *model*<sub>A</sub> in a fully automatic manner, we test *model*<sub>B</sub> on the “fully transformed test” data which is a version of the test data obtained automatically, i.e. by transforming all MWEs in the text instead of only the siblings. All MWEs are then parsed as a unit. When we combine the models, we have more MWEs than we should
<table><caption>Table 6: Precision (P), recall (R), and F₁-measure of unlabelled dependencies against gold standard A using recogniser 3</caption><thead><tr><th>model</th><th>combination type</th><th>P</th><th>R</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>A</td><td></td><td><strong>85.27</strong></td><td>85.02</td><td>85.15</td></tr><tr><td>A+B3</td><td>medFromA</td><td>84.89</td><td><strong>85.68</strong></td><td><strong>85.28</strong></td></tr><tr><td>A+B3</td><td>rightmostMed</td><td>84.84</td><td>85.46</td><td>85.15</td></tr><tr><td>A+B3</td><td>leftmostMed</td><td>81.43</td><td>82.02</td><td>81.72</td></tr></tbody></table>

have and consequently, more edges are considered to be *mediating* and *internal* edges and less edges are considered to be *external* edges. Hence, we are led to choose edges from *model*<sub>A</sub> where *model*<sub>A</sub> is not expected to perform better than *model*<sub>B</sub>. When combining both models with the *medFromA* method, however, we still outperform *model*<sub>A</sub> by 0.04% when using *recogniser*<sub>3</sub> showing that *model*<sub>B</sub> may have learnt something useful although there is no significant evidence for it at this point.

## 4.3 Does using different MWE recognisers impact parsing accuracy differently?

As explained in Section 3.5.3, the last experiment we conduct is to test our model using different recognisers, combine the output using the model combination algorithm explained in Section 3.5.1 and compare it to gold standard<sub>A</sub>. This provides a way to compare different versions of our *model*<sub>B</sub>.

As can be seen in Table 7, different MWE recognition methods seem to make a difference in results. There is a significant difference between our best model (based on *recogniser*<sub>3</sub>) and our worst model (based on *recogniser*<sub>2</sub>) of 0.26 (p = 0.01). Some recognisers lead to decreases in parsing accuracy while others lead to increases. It appears from the table that using a leftmost resolver (a resolver that always chooses the leftmost MWE when there is a conflict) has a bad impact on parsing accuracy. Looking at the different models, it is interesting to note that there is a much lower percentage of MWEs that are siblings in the tree and hence a much lower amount of changes made in the treebank. It is interesting to note that the best model is based on a detector that only detects proper nouns. This seems to show that they are the best candidates for being treated as words-with-spaces. This is not surprising because they are not flexible and never get inflected. For other types of MWE, an analysis as word-with-spaces might not
be the most appropriate, as argued by many researchers (Sag et al. 2002) to give just one example, see Section 2).

<table><caption>Table 7: F₁-measure of unlabelled dependencies against gold standard A using different recognisers from the model<sub>A</sub> combining method</caption><thead><tr><th>model</th><th>detector type</th><th>resolver type</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>A</td><td></td><td></td><td>85.15</td></tr><tr><td>B1</td><td>exhaustive</td><td>longest</td><td>85.18</td></tr><tr><td>B2</td><td>exhaustive</td><td>leftmost</td><td>85.02</td></tr><tr><td>B3</td><td>Proper Nouns</td><td>longest</td><td><strong>85.28</strong></td></tr><tr><td>B4</td><td>Length 2</td><td>leftmost</td><td>85.07</td></tr><tr><td>B5</td><td>Stop words</td><td>longest</td><td>85.19</td></tr></tbody></table>

## 4.4 Summary of our findings

We summarise our findings in Table 8.

<table><caption>Table 8: Summary of our findings</caption><thead><tr><th>question</th><th>answer</th><th>tables concerned</th></tr></thead><tbody><tr><td>Can there be a parsing effect?</td><td>yes</td><td>Table 2 and 3</td></tr><tr><td>Can there be a training effect?</td><td>yes</td><td>Table 4 and 5</td></tr><tr><td>Can we improve parsing on the untransformed gold standard?</td><td>not significantly</td><td>Table 6</td></tr><tr><td>Do different types of MWEs impact the results differently?</td><td>yes</td><td>Table 7</td></tr></tbody></table>

Table 2 and 3 are respectively upper and lower bounds on the training effect that can be obtained with our method with these recognisers. Similarly, Table 4 and 5 are respectively upper and lower bounds on the parsing effect that can be obtained. Given that the lower bounds are still significantly above the baselines in both cases, we can conclude that there can be both a training and a parsing effect, and that we can improve CCG parsing with information about MWEs.
# 5 Conclusion

## 5.1 Contributions

Our main contributions in this work are:

* Improvements on CCG parsing with automatic MWE recognition

* Significant results despite limited settings

* An algorithm to automatically transform MWEs in a treebank

* Techniques for distinguishing training from parsing effects

* Empirical support that there is both training and parsing effects

* Interesting differences in results when using different recognisers

The task we have been trying to improve in this work is the task of syntactic parsing. Adding MWE information to CCG parsing was singled out as a useful direction because it has proven useful in the past with other parsing frameworks and because it seemed an interesting approach to attempt within the framework of a lexicalized grammar. We built on previous work which had shown the benefits of giving information about MWEs to a syntactic parser. It had been shown to work for deterministic dependency parsing, shallow parsing and deterministic constituency parsing but not for statistical constituency parsing. We implemented an existing pipeline which consists in transforming the representation of MWEs in training and test data by collapsing its units to one token and adapted it to our purposes. We gave further evidence supporting these studies and showed that statistical constituency parsing with a lexicalized grammar too can benefit from MWE information. Our study provided further empirical support to the hypothesis that MWE information can improve syntactic parsing by showing that we can improve CCG parsing with information about MWEs.

MWE identification was also identified as a notoriously difficult task although important for many applications because MWEs violate usual compositional rules and can be the source of many errors if not handled properly. We have shown that using an existing automatic recogniser as a source of MWE information was useful which had so far been left a bit unclear in the literature.

Our results have shown small but significant improvements over previous models which is very encouraging given the restricted settings we have worked with. We have as a matter of fact hypothesized that the results were very much limited by the methodology used and have suggested ways of improving the current approach. Our biggest contributions, however, are not in the results we
obtained but in the techniques we proposed. The study has proposed novel tech-
niques to improve on previous pipelines. We have proposed an algorithm to au-
tomatically transform MWEs in a treebank which can be used with other for-
malisms although this algorithm is limited to transforming MWEs which form
a constituent in the tree. More importantly, we have proposed ways of experi-
menting with our models in a way that we can distinguish parsing (the parser
is helped in its decisions by transformed data) from training effects (the parser
learns something useful) in the evaluation and have shown evidence for both. In
addition, we have proposed to experiment with different MWE recognisers and
study the impact of different MWE recognition methods on parsing accuracy.
This is especially interesting in that it is never quite clear in the literature what
counts as an MWE. Experimenting with recognisers that detect different types
of MWEs can help find out what types of MWEs this method is most suitable for.
Our results in this work have shown that collapsing MWE units to one token is
most useful for MWEs that are made of proper nouns. It makes intuitive sense
that treating them as words with spaces is appropriate since they are not flexible
and do not get inflected.

## 5.2 Future work

We propose the following for future work:

* Extending the transformation algorithm to the non-sibling case

* Testing more MWE recognition methods

* Conducting error analysis

A lot more interesting research can still be done on the interaction between
MWE identification and syntactic parsing. Theoretical research has emphasized
the need to give different syntactic representations for different types of MWEs
but a lot of empirical work is still needed if we want to automatically assign sensi-
ble syntactic representations to MWEs. Extending our transformation algorithm
to the non-sibling case would allow conducting more extensive experiments. We
also believe that testing more recognition methods could lead to interesting dis-
cussions where we could find out more about what type of MWE is dealt best
with by what method. This could also help discover interesting properties of
MWEs. Conducting error analysis could also lead to further insight into why
the method is sometimes successful, sometimes less successful.

In the meantime, we believe to have offered new perspectives in the study of
the integration between syntactic parsing and MWE identification especially in
relation to CCG parsing. We have given encouraging results on a difficult task and suggested ways of improving them. We have given further evidence that the integration of MWE identification with syntactic parsing is a promising and exciting research direction.

## References

Birch, Alexandra, Miles Osborne & Philipp Koehn. 2007. CCG supertags in fac-tored statistical machine translation. In *Proceedings of the second workshop on Statistical Machine Translation*, 9–16.

Christodoulopoulos, Christos. 2008. *Creating a natural logic inference system with Combinatory Categorial Grammar*. University of Edinburgh MA thesis.

Clark, Stephen & James Curran. 2007. Wide-coverage efficient statistical parsing with CCG and log-linear models. *Computational Linguistics* 4(33). 493–552.

Clark, Stephen & Julia Hockenmaier. 2002. Evaluating a wide-coverage CCG parser. In *Proceedings of the LREC 2002 beyond PARSEVAL workshop*, 60–66.

Constable, James & James Curran. 2009. Integrating verb-particle constructions into CCG parsing. In *Proceedings of the Australasian Language Technology Association workshop 2009*, 114–118. Sydney, Australia. http://aclweb.org/anthology/U09-1017.

Constant, Mathieu & Joakim Nivre. 2016. A transition-based system for joint lexical and syntactic analysis. In *Proceedings of the 54th annual meeting of the Association for Computational Linguistics*, vol. 1: *Long papers*, 161–171. Berlin, Germany: Association for Computational Linguistics. http://www.aclweb.org/anthology/P16-1016.

Constant, Mathieu, Anthony Sigogne & Patrick Watrin. 2012. Discriminative strategies to integrate multiword expression recognition and parsing. In *Proceedings of the 50th annual meeting of the Association for Computational Linguistics: Long papers*, vol. 1 (ACL ’12), 204–212. Jeju Island, Korea: Association for Computational Linguistics. http://dl.acm.org/citation.cfm?id=2390524.2390554.

Copestake, Ann, Fabre Lambeau, Aline Villavicencio, Francis Bond, Timothy Baldwin, Ivan Sag & Dan Flickinger. 2002. Multiword expressions: Linguistic precision and reusability. In *Proceedings of the third international conference on Language Resources and Evaluation (LREC 2002)*, 1941–1947. Las Palmas, Canary Islands, Spain.
Curran, James, Stephen Clark & Johan Bos. 2007. Linguistically motivated large-scale NLP with C&C and Boxer. In *Proceedings of the 45th annual meeting of the Association for Computational Linguistics, companion volume, proceedings of the demo and poster sessions*, 33–36. Prague, Czech Republic: Association for Computational Linguistics.

Deoskar, Tejaswini, Christos Christodoulopoulos, Alexandra Birch & Mark Steedman. 2014. Generalizing a strongly lexicalized parser using unlabeled data. In Gosse Bouma & Yannick Parmentier (eds.), *Proceedings of the 14th conference of the European chapter of the Association for Computational Linguistics (EACL’2014)*, 126–134. Gothenburg.

Eryiğit, Gülşen, Tugay İlbay & Ozan Arkan Can. 2011. Multiword expressions in statistical dependency parsing. In *Proceedings of the second workshop on Statistical Parsing of Morphologically Rich Languages*, 45–55. Dublin, Ireland.

Finlayson, Mark Alan & Nidhi Kulkarni. 2011. Detecting multi-word expressions improves word sense disambiguation. In *Proceedings of the workshop on Multiword Expressions: From parsing and generation to the real world (MWE ’11)*, 20–24. Stroudsburg, PA, USA: Association for Computational Linguistics.

Green, Spence, Marie-Catherine de Marneffe & Christopher D. Manning. 2013. Parsing models for identifying multiword expressions. *Computational Linguistics* 39(1). 195–227.

Hockenmaier, Julia. 2003. *Data and models for statistical parsing with Combinatory Categorial Grammar*. University of Edinburgh dissertation.

Hockenmaier, Julia & Mark Steedman. 2002. Generative models for statistical parsing with Combinatory Categorial Grammar. In *Proceedings of the 40th annual meeting on Association for Computational Linguistics (ACL ’02)*, 335–342. Stroudsburg, PA, USA: Association for Computational Linguistics.

Hockenmaier, Julia & Mark Steedman. 2007. CCGbank: A corpus of CCG derivations and dependency structures extracted from the Penn Treebank. *Computational Linguistics* 33(3). 355–396.

Hoffmann, Thomas & Graeme Trousdale. 2013. Construction Grammar: Introduction. In Thomas Hoffmann & Graeme Trousdale (eds.), *The Oxford handbook of Construction Grammar* (Oxford Handbooks in Linguistics), 1–14. Oxford University Press.

Kim, Su Nam. 2008. *Statistical modeling of multiword expressions*. University of Melbourne dissertation.

Korkontzelos, Ioannis & Suresh Manandhar. 2010. Can recognising multiword expressions improve shallow parsing? In *Proc. of the 11th annual conference of the North American chapter of the Association for Computational Linguistics*:
*Human Language Technologies NAACL/HLT 2010, 636–644.* Los Angeles, California.

Krishnamurthy, Jayant & Tom M Mitchell. 2012. Weakly supervised training of semantic parsers. In *Proceedings of the 2012 joint conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL)*, 754–765.

Lewis, Mike & Mark Steedman. 2013. Combining distributional and logical semantics. *Transactions of the Association for Computational Linguistics* 1. 179–192.

Martens, Scott & Vincent Vandeghinste. 2010. An efficient, generic approach to extracting multi-word expressions from dependency trees. In *Proceedings of the workshop on Multiword Expressions: From theory to applications (MWE 2010)*, 84–87. Beijing, China: Association for Computational Linguistics.

Nivre, Joakim & Jens Nilsson. 2004. Multiword units in syntactic parsing. In *Workshop on Methodologies and Evaluation of Multiword Units in Real-World Applications*, 39–46.

Nunberg, Geoffrey, Ivan Sag & Thomas Wasow. 1994. Idioms. *Language* 70(3). 491–538.

Padó, Sebastian. 2006. *User's guide to sigf: Significance testing by approximate randomisation*.

Sag, Ivan, Timothy Baldwin, Francis Bond, Ann Copestake & Dan Flickinger. 2002. Multiword expressions: A pain in the neck for NLP. In *Proceedings of the 3rd international conference on Computational Linguistics and Intelligent Text Processing* (Lecture Notes in Computer Science 2276), 1–15. Springer.

Schneider, Nathan, Spencer Onuffer, Nora Kazour, Emily Danchik, Michael T. Mordowanec, Henrietta Conrad & Noah A. Smith. 2014. Comprehensive annotation of multiword expressions in a social web corpus. In *Proceedings of the ninth international conference on Language Resources and Evaluation (LREC 2014)*, 456–461. Reykyavik.

Seretan, Violeta. 2013. On collocations and their interaction with parsing and translation. *Informatics* 1(1). 11–31.

Steedman, Mark. 2000. *The syntactic process*. Cambridge, MA, USA: MIT Press.

Weller, Marion & Ulrich Heid. 2010. Extraction of German multiword expressions from parsed corpora using context features. In Nicoletta Calzolari, Khalid Choukri, Bente Maegaard, Joseph Mariani, Jan Odijk, Stelios Piperidis, Mike Rosner & Daniel Tapias (eds.), *Proceedings of LREC 2010*, 3195–3201. Valletta: European Language Resources Association.

White, Michael. 2006. Efficient realization of coordinate structures in combinatorial Categorial Grammar. *Research on Language and Computation* 4(1). 39–75.
Zhang, Yi & Valia Kordoni. 2008. Robust parsing with a large HPSG grammar. In *Proceedings of the sixth international Language Resources and Evaluation conference (LREC'08)*, 1888–1893. Marrakech, Morocco.

Zhang, Yi, Valia Kordoni, Aline Villavicencio & Marco Idiart. 2006. Automated multiword expression prediction for grammar engineering. In *Proceedings of the workshop on Multiword Expressions: Identifying and Exploiting Underlying Properties* (MWE '06), 36–44. Stroudsburg, PA, USA: Association for Computational Linguistics.
<figure><img src="image_73.png" /></figure>
# Chapter 8

## Multilingual parsing and MWE detection

Vasiliki Foufi

University of Geneva

Luka Nerima

University of Geneva

Eric Wehrli

University of Geneva

Identifying multiword expressions (MWEs) in a sentence in order to ensure their proper processing in subsequent applications, like machine translation, and performing the syntactic analysis of the sentence are interrelated processes. In our approach, priority is given to parsing alternatives involving collocations, and hence collocational information helps the parser through the maze of alternatives, with the aim to lead to substantial improvements in the performance of both tasks (collocation identification and parsing), and in that of a subsequent task (machine translation).

## 1 Introduction

Multiword expressions (MWEs) are lexical units consisting of more than one word (in the intuitive sense of *word*). There are several types of MWEs, including idioms (*a frog in the throat*, *break a leg*), fixed phrases (*per se*, *by and large*, *rock'n roll*), noun compounds (*traffic lights*, *cable car*), phrasal verbs (*look up*, *take off*), etc. While easily mastered by native speakers, their detection and/or their interpretation pose a major challenge for computational systems, due in part to their flexible and heterogeneous nature.

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>
In our research, MWEs are categorized in five subclasses: compounds, discontinuous words, named entities, collocations and idioms. While the first three are expressions of lexical categories (N, V, Adj, etc.) and can therefore be listed along with simple words, collocations and idioms are expressions of phrasal categories (NPs, VPs, etc.). The identification of compounds and named entities can be achieved during the lexical analysis, but the identification of discontinuous words (e.g., particle verbs or phrasal verbs), collocations and idioms requires grammatical data and should be viewed as part of the parsing process.

In this chapter, we will primarily focus on collocations, roughly defined as arbitrary and conventional associations of two words (not counting grammatical words) in a particular grammatical configuration (adjective-noun, noun-noun, verb-object, etc.). Throughout this chapter, we will refer to words belonging to such associations as *CONTENT WORDS*. We will argue that the identification of collocations and parsing are interrelated processes – in the sense that one cannot precede the other – and we will show how this has been achieved in the Fips multilingual parser (Wehrli 2007; Wehrli & Nerima 2015).

Section 2 will give a brief review of MWEs and previous work. Section 3 will describe how Fips handles MWEs and the way they are represented in our lexical database. Section 4 will be concerned with the treatment of collocation types which present a fair amount of syntactic flexibility (e.g. verb-object). For instance, verbal collocations may undergo syntactic processes such as passivization, relativization, interrogation and even pronominalization, which can leave the collocation constituents far away from each other and/or reverse their canonical order. Section 5 will present the collocation extraction process, which will be evaluated in Section 6. Finally we will conclude in Section 7.

## 2 Multiword expressions: A brief review of related work

The standard approach in dealing with MWEs in parsing is to apply a “words-with-spaces” preprocessing step, which marks the MWEs in the input sentence as units which will later be integrated as single blocks in the parse tree built during analysis (Brun 1998; Zhang & Kordoni 2006). This method is not really adequate for processing collocations. Unlike other expressions that are fixed or semi-fixed, several collocation types do not allow a “words-with-spaces” treatment because they have a high morphosyntactic flexibility. On the other hand, Alegria et al. (2004) and Villavicencio et al. (2007) adopted a compositional approach to the encoding of MWEs, able to capture more morphosyntactically flexible MWEs. Alegria et al. (2004) showed that by using a MWE processor in the preprocessing
stage, a significant improvement in the POS tagging precision is obtained. Villavicencio et al. (2007) found that the addition of 21 new MWEs to the lexicon led to a significant increase in the grammar coverage (from 7.1% to 22.7%), without altering the grammar accuracy. However, as argued by many researchers (e.g., Heid 1994; Seretan 2011), collocation identification is best performed on the basis of parsed material. This is due to the fact that collocations are co-occurrences of lexical items in a specific syntactic configuration. For that reason, we have chosen the identification of collocations as soon as possible during parsing. Finkel & Manning (2009) have built a joint model of parsing and named entity recognition, based on a discriminative feature-based constituency parser. They tested their model on the OntoNotes annotated corpus<fnref n="1" /> and they achieved a remarkably good performance on both parsing and recognition of named entities. Green et al. (2013) have developed two structured prediction models with the aim to identify arbitrary-length, contiguous MWEs in Arabic and French. The first is based on context-free grammars and the second uses tree substitution grammars, a formalism that can store larger syntactic fragments. They claim that these techniques can be applied to any language for which a syntactic treebank, a MWE list, and a morphological analyzer exist. Nasr et al. (2015) have developed a joint parsing and MWE identification model for the detection and representation of ambiguous complex function words. Constant & Nivre (2016) developed a transition-based parser which combines two factorized substructures: a standard tree representing the syntactic dependencies between the lexical elements of a sentence and a forest of lexical trees including MWEs identified in the sentence.

## 3 The Fips parser

Fips is a multilingual parser, available for several languages, i.e. French, English, German, Italian, Spanish, Modern Greek, Romanian and Portuguese. It relies on generative grammar concepts and is basically made up of a generic parsing module which can be refined in order to suit the specific needs of a particular language. Fips is a constituent parser that functions as follows: it scans an input string from left to right, without any backtracking. The parsing algorithm, iteratively, performs the following three steps:

* get the next lexical item and project the relevant phrasal category (X → XP);

* merge XP with the structure in its left context (the structure already built);

<footnote n="1">¹http://www.gabormelli.com/RKB/OntoNotes_Corpus, last accessed 26 February 2019.</footnote>
* (syntactically) interpret XP, triggering procedures

– to build predicate-argument structures

– to create chains linking preposed elements to their trace

– to find the antecedent of (3rd person) personal pronouns

– to identify collocations.

The parsing procedure is a one-pass (no pre-processing, no post-processing) scan of the input text, using rules to build up constituent structures and (syntactic) interpretation procedures to determine the dependency relations between constituents (grammatical functions, etc.), including cases of long-distance dependencies. One of the key components of the parser is its lexicon, which contains detailed morphosyntactic and semantic information, selectional properties, valency information, and syntactico-semantic features that are likely to influence the syntactic analysis.

## 3.1 The Fips lexicon

The lexicon was built manually and contains fine-grained information required by the parser. It is organized as a relational database with four main tables:

words, representing all morphological forms (spellings) of the words of a language, grouped into inflectional paradigms;

lexemes, describing more abstract lexical forms which correspond to the syntactic and semantic readings of a word (a lexeme corresponds roughly to a standard dictionary entry);

collocations, which describe multiword expressions combining two lexical items, not counting function words;

variants, which list all the alternatives written forms for a word, e.g. the written forms of British English vs American English, the spellings introduced by a spelling reform, presence of both literary and modern forms in Greek, etc.

## 3.2 Representation of MWEs in the lexicon

In the introduction we mentioned that in our research, MWEs are categorized in five subclasses, i.e. compounds, discontinuous words, named entities, collocations and idioms. We will now describe how they are represented in the lexical database.
Compounds and named entities are represented by the same structure as simple words. An entry describes the syntactic and (some) semantic properties of the word: lexical category (POS), type (e.g., common noun, auxiliary verb), subtype, selectional features, argument structure, semantic features, thematic roles, etc. Each entry is associated with the inflectional paradigm of the word, that is all the inflected forms of the word along with the morphological features (number, gender, person, case, etc.). The possible spaces or hyphens of the compounds are processed at the lexical analyzer level in order to distinguish those that are separators from those belonging to the compound.

Discontinuous words, such as particle verbs or phrasal verbs, are represented in the same way as simple words as well, except that the orthographic string contains the bare verb only, the particle being represented separately in a specific field. The benefit of such an approach is that the phrasal verb inherits the inflectional paradigm of the basic verb. For agglutination, a lexical analyzer will detect and separate the particle from the basic verb.

Collocations are defined as associations of two lexical units (not counting function words) in a specific syntactic relation (for instance adjective-noun, verb-object, etc.). A lexical unit can be a word or a collocation. The definition is therefore recursive and enables to encode collocations that have more than two words (Nerima et al. 2010). For instance, the French collocation *tomber en panne d'essence* ('to run out of gas') is composed of the word *tomber* (lit. 'fall') and the collocation *panne d'essence* (lit. 'failure of gas'). Similarly, the English collocation *guaranteed minimum wage* is composed of the word *guaranteed* and the collocation *minimum wage*.

In addition to the two lexical units, a collocation entry encodes the following information: the citation form, the collocation type (i.e., the syntactic relation between its two components), the preposition (if any) and a set of syntactic frozenness constraints.

Some examples of entries are given in (1), (2) and (3).

(1) ein Schlaglicht werfen (DE) 'to highlight'
    type: verb-direct object
    lexeme #1: Schlaglicht 'spotlight', noun-noun collocation
    lexeme #2: werfen 'throw', _ NP PP verb
    preposition: Ø
    features: {}

(2) κινητό τηλέφωνο (kinitó tiléfono) (MG) 'mobile phone'
    type: adjective-noun
    lexeme #1: κινητό (kinitó) 'mobile', adjective
lexeme #2 : τηλέφωνο (tiléfono) ‘phone’, noun

preposition : Ø

features : {}

(3) *banc de poissons* (FR) ‘shoal of fish’

type : noun-prep-noun

lexeme #1 : *banc* ‘bench’, noun

lexeme #2 : *poisson* ‘fish’, noun

preposition : *de* ‘of’

features : {determiner-less complement, plural complement}

For the time being, we represent idioms as collocations with more restric-
tion features (cannot passivize, no modifiers, etc.). They are, therefore, stored in
the same database table. Reducing idioms to collocations with specific features
though convenient and appropriate for large classes of idioms is nevertheless not
general enough. In particular, it does not allow for the representation of idioms
with fixed phrases, such as *to get a foot in the door*.

3.3 Fips and collocations

3.3.1 Collocation identification mechanism

The collocation identification mechanism is integrated in the parser. In the pre-
sent version of Fips, collocations, if present in the lexicon, are identified in the
input sentence during the analysis of that sentence, rather than at the end. In this
way, priority is given to parsing alternatives involving collocations, and colloca-
tional information helps the parser through the maze of alternatives. To fulfill
the goal of interconnecting the parsing procedure and the identification of collo-
cations, we have incorporated the collocation identification mechanism within
the constituent attachment procedure (see Section 3.3.2). The Fips parser, like
many grammar-based parsers, uses left attachment and right attachment rules to
build respectively left subconstituents and right subconstituents. The grammar
used for the computational modelling comprises rules and procedures. Attach-
ment rules describe the conditions under which constituents can combine, while
procedures compute properties such as long-distance dependencies, agreement,
control properties, argument-structure building, and so on.

3.3.2 Treatment of collocations

The identification of compounds and named entities can be achieved during the
lexical analysis, but the identification of discontinuous words, collocations and
idioms requires grammatical data and are, therefore, part of the parsing process. The identification of a collocation occurs when the second lexical unit of the collocation is attached, either by means of a left attachment rule (e.g., adjective-noun, noun-noun) or by means of a right-attachment rule (e.g., noun-adjective, noun-prep-noun, verb-object), as shown in example (4).

(4) Paul took up a new challenge.

[TP [DP Paul][VP took up [DP a [NP [AP new] challenge]]]]

When the parser reads the noun *challenge* and attaches it (along with the prenominal adjective) as complement of the incomplete [DP a] direct object of the verb *take up*, the identification procedure considers iteratively all the governing nodes of the attached noun and checks whether the association of the lexical head of the governing node and the attached element constitutes an entry in the collocation database. The process stops at the first governing node of a major category (noun, verb or adjective). In our example, going up from *challenge*, the process stops at the verb *take up*. Since *take up - challenge* is an entry in the collocation database and its type (verb-object) corresponds to the syntactic configuration, the identification process succeeds.

In several cases the two constituents of a collocation can be very far apart, or
do not appear in the expected order. We will turn to such examples in Section 4.
To handle them, the identification procedure sketched above must be slightly
modified so that not only the attachment of a lexical item triggers the identifi-
cation process, but also the attachment of the trace of a preposed lexical item.
In such a case, the search will consider the antecedent of the trace. This shows,
again, that the main advantage provided by a syntactic parser in such a task is
its ability to identify collocations even when complex grammatical processes dis-
turb the canonical order of constituents.

4 Detection of collocations in free word-order languages

Just as other types of MWEs, collocations are problematic for NLP because they
have to be recognized and treated as a whole, rather than compositionally (Sag
et al. 2002). On the other hand, there is no systematic restriction on lexical forms
which constitute a collocation, on the order of items in a collocation, or on the
number of words that may intervene between these items especially in free word-
order languages. In such languages, the direct object of a verbal collocation can be
found either before or after the verb, with or without intervening material. This is
illustrated in the following examples with the Greek verb-object collocation κάνω
έκκληση (káno éklisi) ‘to make an appeal’. In (5a), the direct object follows the verb, while in (5b), it precedes the verb, with several intervening words between them:

(5) a. Ο Υπουργός Παιδείας έκανε έκκληση στους διοικητικούς Ο Ipurgós Pedías ékane éklisi stus diikitikús υπαλλήλους να σταματήσουν την απεργία. ipalílus ná stamatísun tín aperyía ‘The Minister of Education made an appeal to the administrative staff to stop the strike.’

b. Έκκληση στους διοικητικούς υπαλλήλους να σταματήσουν την Έklisi stus diikitikús ipalílus ná stamatísun tín απεργία έκανε ο Υπουργός Παιδείας. aperyía ékane ο Ipurgós Pedías ‘An appeal to the administrative staff to stop the strike made the Minister of Education.’

## 4.1 Nominal collocations

Modifier can often be attached within a nominal collocation, separating the two terms. For example, between the constituents of a nominal collocation in the form of adjective-noun, other lexemes may interfere. Table 1 shows a part of the analysis of a sentence where the possessive determiner του (tu) ‘his’ occurs between the adjective παρθενικό (parthenikó) ‘maiden’ and the noun ταξίδι (taxídi) ‘voyage’ of the collocation παρθενικό ταξίδι (parthenikó taxídi) ‘maiden voyage’. Note that, for the POS tagset, we opted for the universal tagset (Petrov et al. 2012).

<table><caption>Table 1: Identification of the nominal collocation παρθενικό ταξίδι (parthenikó taxídi) ‘maiden voyage’</caption><thead><tr><th>word</th><th>tag</th><th>position</th><th>collocation</th></tr></thead><tbody><tr><td>Το (to) ‘the’</td><td>DET</td><td>1</td><td></td></tr><tr><td>παρθενικό (parthenikó) ‘maiden’</td><td>ADJ</td><td>4</td><td></td></tr><tr><td>του (tu) ‘his’</td><td>PRON</td><td>14</td><td></td></tr><tr><td>ταξίδι (taxídi) ‘voyage’</td><td>NOUN</td><td>18</td><td>παρθενικό ταξίδι ‘maiden voyage’</td></tr></tbody></table>
## 4.2 Verbal collocations

Verb-object collocations may undergo syntactic processes such as passivization, relativization, interrogation and even pronominalization, which can leave the collocation constituents far away from each other and/or reverse their canonical order.

### 4.2.1 Passive

In passive constructions, the direct object is promoted to the subject position leaving an empty constituent in the direct object position. The detection of a verb-object collocation in a passive sentence is thus triggered by the insertion of the empty constituent in direct object position. The collocation identification procedure checks whether the antecedent of the (empty) direct object and the verb constitute a verb-object collocation. In example (6), the noun *απόφαση* (απόfasi) ‘decision’ of the collocation *παίρνω απόφαση* (pérno apófasi) ‘to make a decision’ precedes the verb and is in the nominal case, the usual case for subjects.

(6) Η απόφαση πάρθηκε.
Ι απόfasi párthike.
‘The decision was made.’

### 4.2.2 Pronominalization

Another transformation that can affect some collocation types is pronominalization. In such cases, it is important to identify the antecedent of the pronoun which can be found either in the same sentence or in the context. Example (7) illustrates a phrase where the pronoun *it* refers to the noun *money*. Since the pronoun is the subject of the passive form *would be well spent*, it is interpreted as the direct object of the verb and therefore stands for an occurrence of the collocation *to spend money*.

(7) ... though where the money would come from, and how to ensure that *it* would be well *spent*, is unclear.

In example (8) and Table 2, both the verb *να αναλάβουν* (na analávun) ‘to take’ of the verb-object collocation *αναλαμβάνω ευθύνη* (analamváno efthíni) ‘to take responsibility’ and the pronominalized object *τις* (tis) ‘them’ are found in another sentence.
(8) Ας αναλογιστούν τις ευθύνες τους. Να τις αναλάβουν.
As analogistún tis efthínes tus. Na tis analávun.
‘Let them consider their responsibilities. Should they take them.’

<table><caption>Table 2: Identification of a verbal collocation</caption><thead><tr><th>word</th><th>tag</th><th>position</th><th>collocation</th></tr></thead><tbody><tr><td>Ας (as) ‘Let them’</td><td>PRT</td><td>1</td><td></td></tr><tr><td>αναλογιστούν (analogistún) ‘consider’</td><td>VERB</td><td>4</td><td></td></tr><tr><td>τις (tis) ‘the’</td><td>DET</td><td>17</td><td></td></tr><tr><td>ευθύνες (efthínes) ‘responsibilities’</td><td>NOUN</td><td>21</td><td></td></tr><tr><td>τους (tus) ‘their’</td><td>PRON</td><td>21</td><td></td></tr><tr><td>.</td><td>PUNC</td><td>33</td><td></td></tr><tr><td>Να (Na) ‘Should’</td><td>CONJ</td><td>35</td><td></td></tr><tr><td>τις (tis) ‘them’</td><td>PRON</td><td>35</td><td></td></tr><tr><td>αναλάβουν (analávun) ‘take’</td><td>VERB</td><td>42</td><td>αναλαμβάνω την ευθύνη<br>‘take responsibility’</td></tr><tr><td>.</td><td>PUNC</td><td>51</td><td></td></tr></tbody></table>

Example (9) and Table 3 concern French and show again two sentences. Each one of them contains a collocation with the noun *record*: *établir un record* ‘to set up a record’ in the first one, and *battre un record* ‘to break a record’ in the second one, where the noun is pronominalized in the form of a clitic pronoun (*le* ‘it’).

(9) Ce *record* a été établi l’été dernier. Paul espère *le battre* bientôt. This record has been set up last summer. Paul hopes it break soon. ‘This record was set up last summer. Paul hopes to break it soon.’

The parser detects collocations in which the nominal element has been pronominalized thanks to the anaphora resolution component incorporated in Fips (Wehrli & Nerima 2013).

### 4.2.3 Wh-constructions

Our parser can also cope with long-distance dependencies, such as the ones found in wh-questions.<fnref n="2" /> In sentence (10) and Table 4, the direct object constituent

<footnote n="2">²wh-words are interrogative (or relative) words such as *who*, *what*, *which*, etc. For a general discussion of wh-constructions, see (Chomsky 1977).</footnote>
<table><caption>Table 3: Identification of verbal collocations, one with pronominalized object</caption><thead><tr><th>word</th><th>tag</th><th>position</th><th>collocation</th></tr></thead><tbody><tr><td>Ce</td><td>DET</td><td>1</td><td></td></tr><tr><td>record</td><td>NOUN</td><td>4</td><td></td></tr><tr><td>a</td><td>VERB</td><td>11</td><td></td></tr><tr><td>été</td><td>VERB</td><td>13</td><td></td></tr><tr><td>établi</td><td>VERB</td><td>17</td><td>établir un record</td></tr><tr><td>l'</td><td>DET</td><td>24</td><td></td></tr><tr><td>été</td><td>NOUN</td><td>26</td><td>été dernier</td></tr><tr><td>dernier</td><td>ADJ</td><td>30</td><td></td></tr><tr><td>.</td><td>PUNC</td><td>37</td><td></td></tr><tr><td>Paul</td><td>NOUN</td><td>1</td><td></td></tr><tr><td>espère</td><td>VERB</td><td>6</td><td></td></tr><tr><td>le</td><td>PRON</td><td>13</td><td></td></tr><tr><td>battre</td><td>VERB</td><td>16</td><td>battre un record</td></tr><tr><td>bientôt</td><td>ADV</td><td>23</td><td></td></tr><tr><td>.</td><td>PUNC</td><td>30</td><td></td></tr></tbody></table>

occurs at the beginning of the sentence. Again, assuming a generative grammar analysis, we consider that such pre-posed constituents are connected to so-called canonical positions. The fronted element being a direct object, the canonical position is a post-verbal DP position immediately dominated by the VP node. The parser establishes such a link and returns the structure from (10), where [DP e]<sub>i</sub> stands for the empty category (the “trace”) of the preposed constituent Ποιο ρεκόρ (Pxó rekór) ‘Which record’.

(10) Ποιο ρεκόρ θέλει να σπάσει ο Μελισσανίδης? [CP [DP Ποιο ρεκόρ]<sub>i</sub>] [TP Ρχó rekór théli na spási ο Melisanídis θέλει] [CP να] [TP σπάσει] [VP [DP e]<sub>i</sub>] [DP ο Μελισσανίδης] ‘Which record does Melissanidis want to break?’

In such cases, the collocation identification process is triggered by the insertion of an empty constituent in the direct object position of the verb. Since the empty constituent is connected to the pre-posed constituent, such examples can be easily treated as a minor variant of the standard case described in Section 3.3.1. All so-called wh-constructions are treated in a similar fashion, that is relative clause and topicalization.
<table><caption>Table 4: Identification of verbal collocation in a wh-question</caption><thead><tr><th>word</th><th>tag</th><th>position</th><th>collocation</th></tr></thead><tbody><tr><td>Ποιο (Pio) 'Which'</td><td>DET</td><td>1</td><td></td></tr><tr><td>ρεκόρ (rekór) 'record'</td><td>NOUN</td><td>6</td><td></td></tr><tr><td>θέλει (théli) 'wants'</td><td>VERB</td><td>12</td><td></td></tr><tr><td>να (na) 'to'</td><td>CONJ</td><td>18</td><td></td></tr><tr><td>σπάσει (spási) 'break'</td><td>VERB</td><td>21</td><td>σπάζω το ρεκόρ<br>'break the record'</td></tr><tr><td>ο (ο) 'the'</td><td>DET</td><td>28</td><td></td></tr><tr><td>Μελισσανίδης (Melisanídis) 'Melisanidis'</td><td>NOUN</td><td>30</td><td></td></tr></tbody></table>

### 4.2.4 Tough-movement constructions

In such constructions, the matrix subject is construed as the direct object of the infinitival verb governed by a *tough* adjective. Following Chomsky's (1977) analysis of such constructions, the parser will hypothesize an abstract wh-operator in the specifier position of the infinitival clause, which is linked to the matrix subject. Like all wh-constituents, the abstract operator will itself be connected to an empty constituent later on in the analysis, giving rise to a chain connecting the subject of the main clause and the direct object position of the infinitival clause. The structure as computed by the parser is given in (11), with the chain marked by the index *i*.

(11) `[TP [DP this record]i seems[AP difficult[TP [DP e]i to[VP break[DP e]i]]]]]`

## 4.3 Complex collocations

As observed by Heid (1994), among others, collocations can involve more than two content words. Such complex expressions can be described recursively as collocations of collocations. Our identification procedure has been extended to handle such cases. For example, the Greek noun-noun collocation *απεργία πείνας* (apyryía pínas) 'hunger strike', which combines with the verb *κάνω* (káno) 'to do', yields the larger verb-object collocation *κάνω απεργία πείνας* (káno aperyía pínas) 'to go on hunger strike', where the object is itself a noun-noun collocation. Given the strict left-to-right processing order assumed by the parser, the system will first identify the collocation *κάνω απεργία* (káno aperyía) 'to go on strike' when attaching the word *απεργία* (apyryía) 'strike'. Then, reading the last word, *πείνας* (pínas) 'hunger' (here in genitive case), the parser will identify the collocation
απεργία πείνας (apyeryía pínas) ‘hunger strike’. The search succeeds with the verb κάνω (káno) ‘to do’, and the collocation κάνω απεργία πείνας (káno aperyía pínas) ‘to go on hunger strike’ is identified.

Moreover, the Greek lexical database comprises nominal collocations formed by a simple noun and a collocation or by two collocations. For example, δύναμη πολιτικής προστασίας (dínami politikís prostasías) ‘civil protection force’ is for-
med by a simple noun, δύναμη (dínami) ‘force’, and a nominal collocation in geni-
tive case, πολιτικής προστασίας (politikís prostasías) ‘of civil protection’. The col-
location πυρηνικός σταθμός παραγωγής ενέργειας (pirinikós stathmós paragoyís
enéryias) ‘nuclear power station’ is formed by the collocations πυρηνικός σταθμός
(pirinikós stathmós) ‘nuclear station’ and παραγωγής ενέργειας (paragoyís enéry-
ias) ‘of energy production’.

5 Collocation extraction

As already mentioned, the parser can only identify collocations that are part of
its lexical database. Therefore, it is crucial to have as good a coverage of col-
locations as possible in the database. To help the linguist/lexicographer in the
time-consuming task of inserting collocations, we have designed a collocation
extraction tool (Seretan 2011), dubbed FipsCo. Applied to a corpus, FipsCo parses
all the sentences, extracting all the pairs of lexical items which co-occur in pre-
defined grammatical configurations (adjective-noun, noun-noun, subject-verb,
verb-object, etc.). All those pairs are considered as potential collocations.

Once the corpus has been completely parsed, a statistical filter is used to rank
the potential collocations according to their degree of association. By default, we
use the log-likelihood ratio measure (LLR), since it was shown to be particularly
suited to language data (Dunning 1993). In our extractor, the items of each candi-
date expression represent base word forms (lemmas) and they are considered in
the canonical order implied by the given syntactic configuration (e.g., for a verb-
object candidate, the object is postverbal in subject-verb-object (SVO) languages
like Greek). Even if the candidate occurs in corpus in different morphosyntactic
realizations, its various occurrences are successfully identified as instances of the
same type thanks to the syntactic analysis performed by the parser.

Figure 1 displays a list of verb-object collocations extracted from an English
corpus taken from the magazine *The Economist*. On the left, candidate colloca-
tions are listed and at the same time they are shown in their context.

Our system recognizes a large range of collocation types (more than 30 types),
including several nominal and verbal ones. The most frequent types are:
* Adjective-noun, e.g. *nuclear war*;

* Noun-noun, e.g. *flower shop*;

* Noun-preposition-noun, e.g. *casco di banane* ('bunch of bananas');

* Verb-object where the object is a bare noun, e.g. *take part*;

* Verb-preposition-noun, e.g. *bring to light*;

* Verb-adverb, e.g. *put together*.

Once filtered and ordered by means of standard association measures, the candidate collocations are manually validated and added to the lexical database. The current content of the database for six European languages is shown in Table 5.

# 6 Evaluation and results

The Fips parser performs well compared to other “deep” linguistic parsers (Delphin,<fnref n="3" /> ParGram,<fnref n="4" /> etc.) in terms of speed. Parsing time depends on two main factors: (i) the type and complexity of the corpus, and (ii) the selected beam size (maximum number of alternatives allowed). By default, Fips runs with a beam size of 40 alternatives, which gives it a speed ranging from 150 to 250 tokens (word, punctuation) per second. At that pace, parsing a one million word corpus takes approximately 2–3 hours. We are going to present the experiments that were performed for Modern Greek and English in order to evaluate the performance of our parser.

## 6.1 Modern Greek

The evaluation measures the performance of our parser to identify collocations that are lexicalized (i.e. collocations that are present in the lexical database). We also measure the impact of the collocation knowledge on the performance of the parser (in percentage of complete analyses). To achieve the evaluation, we took a small newspaper corpus of about 20,000 words and we manually identified

<footnote n="3">³International consortium developing HPSG grammars and other tools, cf. http://www.delphin.net/wiki/index.php/Home.</footnote>

<footnote n="4">⁴ParGram is an international consortium for the development of LFG-based grammars, see http://pargram.b.uib.no.</footnote>
<figure><img src="image_76.png" /><figcaption>Figure 1: Extraction of verb-object collocations</figcaption></figure>

<table><caption>Table 5: Number and types of collocations in the Fips lexical database</caption><thead><tr><th>collocation type</th><th>English</th><th>French</th><th>German</th><th>Italian</th><th>Spanish</th><th>Greek</th></tr></thead><tbody><tr><td>Adjective-noun</td><td>3,049</td><td>5,935</td><td>490</td><td>1,325</td><td>1,621</td><td>20,131</td></tr><tr><td>Noun-noun</td><td>5,671</td><td>454</td><td>2,476</td><td>131</td><td>66</td><td>471</td></tr><tr><td>Noun-prep-noun</td><td>555</td><td>7,846</td><td>22</td><td>1,246</td><td>988</td><td>11</td></tr><tr><td>Verb-object</td><td>850</td><td>1,560</td><td>197</td><td>250</td><td>1,098</td><td>382</td></tr><tr><td>Others</td><td>932</td><td>2,963</td><td>330</td><td>209</td><td>592</td><td>126</td></tr><tr><td>Total</td><td>11,057</td><td>18,758</td><td>3,515</td><td>3,161</td><td>4,365</td><td>21,122</td></tr></tbody></table>
638 collocations (both nominal and verbal). We ran the parser twice on the corpus: the first time before and the second time after enrichment of the collocation database. On the first run, the parser achieved 43.26% of complete analyses and identified 124 collocations. On the second run, after enrichment of the lexicon, the percentage of complete analyses increased to 44.33% and nearly three quarters of the corpus collocations were identified (482/638). Over this small corpus, the parser achieved a 100% precision in the collocation identification task, with a recall of 75.54% and an F-measure of 86%. The collocations that were not identified (156 out of 638) were part of sentences for which the parser did not achieve a complete analysis.

## 6.2 English

We have also conducted an evaluation over a corpus with approximately 6,000 sentences taken from *The Economist*. The research questions were specifically focused on the statistical significance of ambiguity resolution based on collocation knowledge and on how frequently, in a given corpus, the detection of a collocation helps the parser make the “right” decision. To answer those questions, we parsed the corpus twice, first with the collocation detection component turned on and then with the component turned off. We then compared the results of both runs. Since it was difficult to compare phrase-structure representations, we used the Fips tagger, that is the Fips parser with part-of-speech output. It is indeed much easier to compare POS-tags than phrase-structures. Tables 6 and 7 illustrate the Fips tagger output for the segment in boldface of the sentence *The researchers estimated the total worldwide labour costs for the iPad at $33, of which China's share was just $8*.

Table 6 gives the results obtained with the collocation detection component turned on, and Table 7 the results obtained with the component turned off.

<table><caption>Table 6: Parser output with collocation knowledge</caption><thead><tr><th>word</th><th>tag</th><th>position</th><th>collocation</th></tr></thead><tbody><tr><td>the</td><td>DET</td><td>27</td><td></td></tr><tr><td>total</td><td>ADJ</td><td>31</td><td></td></tr><tr><td>worldwide</td><td>ADJ</td><td>37</td><td></td></tr><tr><td>labour</td><td>NOUN</td><td>47</td><td></td></tr><tr><td>costs</td><td>NOUN</td><td>54</td><td>labour costs</td></tr></tbody></table>
<table><caption>Table 7: Parser output *without* collocation knowledge</caption><thead><tr><th>word</th><th>tag</th><th>position</th><th>collocation</th></tr></thead><tbody><tr><td>the</td><td>DET</td><td>27</td><td></td></tr><tr><td>total</td><td>ADJ</td><td>31</td><td></td></tr><tr><td>worldwide</td><td>ADJ</td><td>37</td><td></td></tr><tr><td>labour</td><td>NOUN</td><td>47</td><td></td></tr><tr><td>costs</td><td>VERB</td><td>54</td><td></td></tr></tbody></table>

The sentence segment *the total worldwide labour costs* is displayed in both tables with the words in the first column, the part-of-speech tag in the second column and the position – expressed as position of the first character of each word starting from the beginning of the sentence – in the third column. As we can see, the word *costs* is taken as a noun in the first analysis, as a verb in the second. The (correct) choice of a nominal reading in the first analysis is due to the detection of the collocation *labour costs*. In the second run, given the absence of collocational knowledge, the parser opts for the verbal reading. Both output files could easily be manually compared using a specific user interface as illustrated in the screenshot in Figure 2, where POS differences are displayed in red.

<table><caption>Table 8: POS-tagging with and without collocation knowledge</caption><thead><tr><th></th><th>with collocations</th><th>without collocations</th></tr></thead><tbody><tr><td>complete analyses</td><td>73.41%</td><td>72.95%</td></tr><tr><td>POS-tag differences</td><td>727</td><td>-</td></tr><tr><td>better tags</td><td>382</td><td>106</td></tr><tr><td>number of collocations</td><td>1668</td><td>-</td></tr></tbody></table>

A summary of the results of the evaluation is given in Table 8. The first line shows the number of complete analyses. Collocational knowledge increases the number of complete analysis by approximately 0.5%, or about 30 sentences for our corpus of 6,000 sentences. 727 tags are different between the two runs. Of those, excluding differences which do not really matter (some words can be analyzed either as predicative adjectives or as adverbs without much semantic differences, etc.), in 382 cases the tags were better in the first run (with collocational knowledge), and 106 cases better in the second run (without collocational knowledge).
<figure><img src="image_77.png" /><figcaption>Figure 2: The evaluation user interface</figcaption></figure>
knowledge). In other words, collocational knowledge helped the parser make the better decision four times more than it penalized it. Notice finally that 1,668 collocations were detected in the corpus (more than one in four sentences), which clearly stresses the high frequency of this phenomenon in natural language.

## 7 Conclusion

In this chapter, we have argued in favour of a treatment of collocations, and by extension of all MWEs, fully integrated in the parsing process. The argument is rather simple. On the one hand, we have shown that the identification of collocations must be based on analyzed data, and therefore cannot be performed before parsing. On the other hand, we have also shown that collocation identification can help the parser, for instance to solve lexical as well as syntactic ambiguities, provided that the identification is done before the end of parsing. The solution to this apparent paradox – collocation identification cannot be done before and cannot be done after parsing – is clear: collocation identification must be part of the parsing process and must be performed as early as possible, that is at the time the parser attaches the second constituent of the collocation, or inserts the trace of that constituent.

## Abbreviations

Tagset from Petrov et al. (2012).

ADJ adjective

ADP adposition

ADV adverb

CONJ coordinating conjunction

DET determiner

NOUN noun

NUM numeral

PRON pronoun

PRT particle

PUNC punctuation

VERB verb

X other

## References

Alegria, Iñaki, Olatz Ansa, Xabier Artola, Nerea Ezeiza, Koldo Gojenola & Ruben Urizar. 2004. Representation and treatment of multiword expressions in Basque. In Takaaki Tanaka, Aline Villavicencio, Francis Bond & Anna Korhonen (eds.), *Second ACL workshop on multiword expressions: Integrating processing*, 48–55. Barcelona, Spain: Association for Computational Linguistics.
Brun, Caroline. 1998. Terminology finite-state preprocessing for computational LFG. In *COLING 1998 volume 1: The 17th international conference on Computational Linguistics*, 196–200. Montreal, QC.

Chomsky, Noam. 1977. On Wh-movement. In P.W. Culicover, T. Wasw & A. Akmajian (eds.), *Formal syntax*. San Francisco, London: Academic Press.

Constant, Mathieu & Joakim Nivre. 2016. A transition-based system for joint lexical and syntactic analysis. In *Proceedings of the 54th annual meeting of the Association for Computational Linguistics*, vol. 1: *Long papers*, 161–171. Berlin, Germany: Association for Computational Linguistics. http://www.aclweb.org/anthology/P16-1016.

Dunning, Ted. 1993. Accurate methods for the statistics of surprise and coincidence. *Computational Linguistics* 19(1). 61–74. http://dl.acm.org/citation.cfm?id=972450.972454.

Finkel, Jenny Rose & Christopher D. Manning. 2009. Joint parsing and named entity recognition. In *Proceedings of Human Language Technologies: The 2009 annual conference of the North American chapter of the Association for Computational Linguistics*, 326–334. Boulder, Colorado: Association for Computational Linguistics. http://www.aclweb.org/anthology/N/N09/N09-1037.

Green, Spence, Marie-Catherine de Marneffe & Christopher D. Manning. 2013. Parsing models for identifying multiword expressions. *Computational Linguistics* 39(1). 195–227.

Heid, Ulrich. 1994. On ways words work together: Topics in lexical combinatorics. In Willy Martin et al. (ed.), *Proceedings of the VIth Euralex international congress (EURALEX’94)*, 226–257. Amsterdam. Eingeladener Hauptvortrag.

Nasr, Alexis, Carlos Ramisch, José Deulofeu & André Valli. 2015. Joint dependency parsing and multiword expression tokenisation. In *53rd annual meeting of the Association for Computational Linguistics*, 1116–1126. Beijing, China.

Nerima, Luka, Eric Wehrli & Violeta Seretan. 2010. A recursive treatment of collocations. In *Proceedings of the seventh international conference on Language Resources and Evaluation (lrec’10)*, 634–638. Valletta, Malta.

Petrov, Slav, Dipanjan Das & Ryan McDonald. 2012. A universal part-of-speech tagset. In Nicoletta Calzolari, Khalid Choukri, Thierry Declerck, Mehmet Uğur Doğan, Bente Maegaard, Joseph Mariani, Asuncion Moreno, Jan Odijk & Stelios Piperidis (eds.), *Proceedings of the eighth international Language Resources and Evaluation Conference, LREC 2012*, 2089–2096. Istanbul, Turkey. http://www.lrec-conf.org/proceedings/lrec2012/summaries/274.html.

Sag, Ivan, Timothy Baldwin, Francis Bond, Ann Copestake & Dan Flickinger. 2002. Multiword expressions: A pain in the neck for NLP. In *Proceedings of the*
*3rd international conference on Computational Linguistics and Intelligent Text Processing* (Lecture Notes in Computer Science 2276), 1–15. Springer.

Seretan, Violeta. 2011. *Syntax-based collocation extraction* (Text, Speech and Language Technology 44). Dordrecht: Springer.

Villavicencio, Aline, Valia Kordoni, Yi Zhang, Marco Idiart & Carlos Ramisch. 2007. Validation and evaluation of automatically acquired multiword expressions for grammar engineering. In *Proceedings of the 2007 joint conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (emnlp-conll)*, 1034–1043. Prague, Czech Republic: Association for Computational Linguistics. http://www.aclweb.org/anthology/D/D07/D07-1110.

Wehrli, Eric. 2007. Fips: A “deep” linguistic multilingual parser. In *Proceedings of the ACL 2007 workshop on Deep Linguistic Processing*, 120–127. Prague, Czech Republic: Association for Computational Linguistics. http://www.aclweb.org/anthology/W/W07/W07-1216.

Wehrli, Eric & Luka Nerima. 2013. Anaphora resolution, collocations and translation. In J. Monti, R. Mitkov, G. Corpas Pastor & V. Seretan (eds.), *Proceedings of the workshop on Multiword Units in Machine Translation and Translation Technology (MUMTT’2013)*. Nice.

Wehrli, Eric & Luka Nerima. 2015. The Fips multilingual parser. In N. Gala, R. Rapp & G. Bel-Enquix (eds.), *Language production cognition, and the lexicon, Festschrift in honour of Michael Zock*, 473–489. Springer.

Zhang, Yi & Valia Kordoni. 2006. Automated deep lexical acquisition for robust open texts processing. In *Proceedings of the 5th international conference on Language Resource and Evaluation (LREC-2006)*, 275–280. Genoa, Italy.
<figure><img src="image_78.png" /></figure>
Chapter 9

Extracting and aligning multiword
expressions from parallel corpora

Nasredine Semmar

CEA LIST, Vision and Content Engineering Laboratory

Christophe Servan

University of Grenoble Alpes – Grenoble Informatics Laboratory
SYSTRAN

Meriama Laib

CEA LIST, Vision and Content Engineering Laboratory

Dhouha Bouamor

Actimos, Groupe Accord

Morgane Marchand

eXenSa

Bilingual lexicons of multiword expressions play a vital role in several natural lan-
guage processing applications such as machine translation and cross-language in-
formation retrieval because they often characterize domain-specific vocabularies.
Word alignment approaches are generally used to construct bilingual lexicons au-
tomatically from parallel corpora. We present in this chapter three approaches to
align multiword expressions from parallel corpora. We evaluate the bilingual lexi-
cons produced by these approaches using two methods: a manual evaluation of the
alignment quality and an evaluation of the impact of this alignment on the transla-
tion quality of the phrase-based statistical machine translation system Moses. We
experimentally show that the integration of the bilingual lexicons of multiword
expressions in the translation model improves the performance of Moses.

<figure><img src="image_79.png" /></figure>

Nasredine Semmar, Christophe Servan, Meriama Laib, Dhouha Bouamor & Morgane Marchand. 2019. Extracting and aligning multiword expressions from parallel corpora. In Yannick Parmentier & Jakub Waszczuk (eds.), *Representation and parsing of multiword expressions: Current trends*, 239–268. Berlin: Language Science Press.

DOI:10.5281/zenodo.3264764

<figure><img src="image_80.png" /></figure>
# 1 Introduction

A MultiWord Expression (MWE) is a combination of words for which syntactic or semantic properties of the whole expression cannot be obtained from its parts (Sag et al. 2002). Such units could be collocations, compound words, named entities, etc. They constitute an important part of the lexicon of any natural language (Jackendoff 1997). Bilingual lexicons of MWEs play a vital role in several Natural Language Processing (NLP) applications such as Machine Translation (MT) and Cross-Language Information Retrieval (CLIR) because they generally characterize domain-specific vocabularies. The manual construction of these lexicons is often costly and time consuming. Word alignment approaches are generally used to automatically construct bilingual lexicons from parallel or comparable corpora. Several word alignment approaches have been explored (Daille et al. 1994; Blank 2000; Barbu 2004) and many automatic word alignment tools are available, such as GIZA++ (Och & Ney 2000). However, most of these tools are efficient only to align single words (Fraser & Marcu 2007).

The chapter is organized as follows. We survey in Section 2 previous works addressing the tasks of extracting and aligning MWEs from parallel corpora. We define in Section 3 the notion of MultiWord Expression and describe different types of MWEs with examples. In Section 4, we introduce three approaches to build bilingual lexicons of MWEs from sentence aligned parallel corpora. The experimental results are reported and discussed in Section 5. Finally, we present in Section 6 the conclusion and future work.

# 2 Related work

There are mainly two strategies to extract bilingual MWEs from parallel corpora. The first strategy consists to acquire translations of phrases from parallel corpora in one step. Phrases are not necessarily MWEs, they can be contiguous sequences of a few words that encapsulate enough context to be translatable (DeNero & Klein 2008). The second strategy firstly, identifies monolingual MWE candidates and then applies alignment approaches to find bilingual correspondences (Daille et al. 1994; Blank 2000; Gaussier & Yvon 2011; Barbu 2004).

In the second strategy, MWEs extraction can be processed by using symbolic methods based on morpho-syntactic patterns, or, through statistical approaches, which use automatic measures to rank MWE candidates. Finally, MWEs extraction can be done by using hybrid approaches, which combine the two first strategies.
Dagan & Church (1994) proposed to use syntactic analysis to extract terminol-
ogy. MWEs are extracted by grouping linguistically related terms. In the same
way, Okita et al. (2010) proposed to link across two languages MWEs accord-
ing to their syntactic and lexical information. Tufiş & Ion (2007) and Seretan &
Wehrli (2007) introduce a linguistic approach in which they claim that MWEs
keep in most cases the same morpho-syntactic structure in the source and target
languages.

Statistical approaches also have proven to be useful in collecting bilingual MWEs from parallel corpora. Kupiec (1993) introduced the use of machine learning algorithms such as the Expectation Maximization (EM) to extract MWEs. Similarly, Vintar & Fišer (2008) proposed to extract bilingual MWEs by translating MWEs from a well known language (English) to a low resource language (Slovene) by using machine translation. They have shown that their translation-based approach performs better than using linguistic approaches. But they did not combine these two kind of approaches. The combination of such approaches enables to extract finer MWEs (Daille 2001). In this way Wu & Chang (2003) and later Boulaknadel et al. (2008), proposed to use syntactic and statistical analysis to extract bilingual MWEs from a parallel corpus. The main aspect of their approach is a monolingual parsing to extract MWEs combined with statistical detection in each language, then, they confront candidates from each side to find bilingual MWEs.

Other approaches proposed to use machine translation to translate MWEs can-
didates found with a syntactic analysis (Seretan & Wehrli 2007). Again, the first
step is done on each language independently and then, a second step aims to
match candidates across languages.

3 Multiword expressions

3.1 Definition

In NLP, a multiword expression refers to a non-compositional sequence of words
whose exact and unambiguous meaning, connotation and syntactic properties
cannot be derived from the meaning or connotation of its components (Choueka
1988; Sag et al. 2002). MWEs are frequently used in written texts and constitute
a significant part of the language lexicon.

Jackendoff (1997) considers that the frequency of their use is equivalent to that
of single words. Although MWEs are easily computed, stored and used by hu-
mans, their identification is a major issue for different type of NLP applications,
namely for syntactic analysis (Nivre & Nilsson 2004; Constant et al. 2011), auto-
matic summarization (Hogan et al. 2007), information extraction (Vechtomova
2005) and especially for machine translation and cross-language information re-
trieval (Carpuat & Diab 2010; Ren et al. 2009).

3.2 Multiword expressions typology

In the literature, MWEs are presented under different names or classifications
such as idioms, lexicalized phrases or collocations and several authors (Ramisch
et al. 2013) give a list of examples instead of giving an exact description of them.
According to Calzolari et al. (2002), MWEs are “different but related phenomena”
and “At the level of greatest generality, all of these phenomena can be described
as a sequence of words that acts as a single unit at some level of linguistic anal-
ysis”.

Sag et al. (2002) classify them into two main categories: lexicalized phrases and institutionalized phrases (Figure 1). Lexicalized phrases “have at least partially idiosyncratic syntax or semantics, or contain “words” which do not occur in isolation”. Institutionalized phrases are “semantically and syntactically compositional, but statistically idiosyncratic”.

<figure><img src="image_81.png" /><figcaption>Figure 1: Typology of multiword expressions by Sag et al. (2002)</figcaption></figure>
3.2.1 Lexicalized phrases

In a decreasing order of lexical rigidity, these MWEs are broken down into three classes: fixed expressions, semi-fixed expressions and syntactically-flexible expressions.

3.2.1.1 Fixed expressions

Fixed expressions are non-compositional sequences of words. They are syntac-
tically and morphologically rigid and undergo neither internal modification nor
morphological and syntactical variations (e.g. *nest of vipers* in English or *pomme
de terre* in French). To determine whether or not a sequence of words is a fixed ex-
pression, we can use linguistic criteria such as using synonyms or adding words
between its components (cf. *nest of many black vipers* in English or *pomme de jolie
terre lointaine* in French). Fixed expressions can be considered as single entries
in the dictionary.

3.2.1.2 Semi-fixed expressions

A semi-fixed expression is a non-compositional sequence of words whose compo-
nents do not contribute to its figurative meaning. Semi-fixed expressions should
respect a strict word order and some of them undergo limited lexical and mor-
phological variability such as inflection and some variation in the reflexive form.
According to their characteristics, they can be broken down into three basic cate-
gories: non-decomposable idioms, proper names and some compound nominals
(Sag et al. 2002).

Non-decomposable idioms do not undergo syntax variability but their compo-
nents accept lexical changes such as pronominal reflexivity form (e.g. *wet himself*,
*wet themselves*), verbal inflection (*kick the bucket*, *kicked the bucket*) or passiviza-
tion (e.g. *briser le silence* or *le silence est brisé* in French). Proper names "are syn-
tactically highly idiosyncratic" (Sag et al. 2002). They can be complex with two
or three proper names as components, including person, places and organization
names.

Compound nominals are syntactically unalterable and undergo number inflec-
tion (e.g. *car park(s)* in English or *pomme(s) de terre* in French).

3.2.1.3 Syntactically-flexible expressions

Unlike semi-fixed expressions, syntactically-flexible expressions undergo a wide
degree of syntactic variation such as passivation (e.g., *The cat was let out of the*
bag) and allow external elements to intervene between their components (e.g., *slow the car down*). This type of expressions includes verb-particle constructions, decomposable idioms. Particle verbs constructions are made up of a verb whose meaning is modified by one or more particles. They can be either semantically idiosyncratic such as *brush up on* or compositional such as *take after, look out, go back* and *run over*. Decomposable idioms tend to be syntactically flexible to some degree that is unpredictable (Riehemann 2001). Semantically, they behave as if their components were linked parts contributing independently to the figurative interpretation of the expression as a whole.

### 3.2.2 Institutionalized phrases

Institutionalized phrases are semantically and syntactically fully compositional, but statistically idiosyncratic (Sag et al. 2002). They occur in a high frequency and their idiosyncrasy is statistical rather than linguistic. They generally allow one available meaning. Institutionalized phrases often refer to “collocations” (Barz 1996; Riehemann 2001; Burger 2010), described as sequences of words that statistically have a high probability to appear together whether they are contiguous or not (e.g., *make love* or *make a difference*).

## 4 Construction of bilingual lexicons of MWEs from parallel corpora

In this section, we describe three approaches to build bilingual lexicons of MWEs from a sentence aligned parallel corpus. The first two approaches are composed of two steps. The first step identifies MWEs present in the parallel corpus, and the second step establishes correspondence relations between the MWEs of the source text and their translations in the target text. The third approach performs the terminology extraction and alignment tasks in one step.

### 4.1 Statistical approach for MWEs alignment

The statistical approach for MWEs alignment consists first in identifying the relevant word groups through the use of *n*-gram statistics in both the source and target languages. Then for each source MWE extracted we compile a list of candidate translations through the use of two distance metrics. The list of candidates is then pruned through the use of heuristics like the length of each MWE, and a translation is “found” if it satisfies confidence threshold on the distance metric and the heuristics.
The alignment process has the following four steps (Semmar et al. 2010):

1. Monolingual extraction of MWEs: The role of this step consists to identify all the *n*-grams (up to 6-grams) that may represent a MWE. This is done through frequency analysis and heuristic scoring. This step outputs two lists of terms, which we will refer to as SC (MWE in the Source Language) and TC (MWE in the Target Language).

2. Frequency distance calculation: This step calculates for all source MWEs in SC the distance to each of the target MWEs in TC. The main idea of this metric is that if two MWEs are translations of each other then they must appear together in the corpus segments, and only together. Their frequency distance is then calculated as follows:

$$ (1) \qquad \mathrm{FD}(s, t) = \frac{|f(s) - f(t)|}{\max(f(s), f(t))} $$

Where $f(s)$ is the frequency of the source MWE and $f(t)$ is the frequency of the target MWE under consideration.

We observe that if $t$ is the translation of $s$, $f(s) = f(t)$ then we have distance equal to 0. Also, if two MWEs always occur together but one is much more frequent than the other, the distance could have a value other than 0 and they would not be considered translations of each other. Here we chose to apply a threshold of 0.25 as the maximum allowable distance. This threshold is calculated empirically and can be tuned to achieve better precision.

3. Co-occurrence distance (CD): The previous step only considers frequencies so it may be possible for two completely unrelated MWEs to achieve a low distance score. To refine extraction results, we also check for a co-occurrence score as follows:

$$ (2) \qquad \mathrm{CD}(X, Y) = \frac{\sqrt{\sum (X_i - Y_i)^2}}{N} $$

Where, $X_i$ is the number of occurrences of $s$ in the $i^{th}$ segment of the SL, $Y_i$ is the number of occurrences of $t$ in the $i^{th}$ segment of the TL and $N$ is the number of segments.

This check allows the rejection of the MWEs that fortuitously have similar frequency. Since they would not appear in the same segments, the terms $X_i - Y_i$ would increase. The candidate list can be ordered through CD.
4. Pruning MWEs candidates: After obtaining an ordered list of target MWEs candidates, we remove:

* The candidates which have a length different from the source MWE;

* The candidates which have been previously aligned with another source MWE and where the co-occurrence score was better.

Because of the statistical nature of this approach, it performs much better for MWEs that occur often in the corpus. Table 1 illustrates some MWEs and their translations extracted from the bi-sentence *Approval of the Minutes of the previous sitting/Approbation du procès-verbal de la séance précédente*. It should be noted that before applying the MWEs alignment approach, we lemmatize the parallel corpus. This lemmatization is achieved using the CEA LIST Multilingual Analyzer LIMA (Besançon et al. 2010).

<table><caption>Table 1: Some examples of aligned MWEs with the statistical approach</caption><thead><tr><th>English MWE</th><th>French MWE</th></tr></thead><tbody><tr><td>minute</td><td>procès-verbal</td></tr><tr><td>approval of the minute</td><td>approbation du procès-verbal</td></tr><tr><td>previous sitting</td><td>séance précédent</td></tr></tbody></table>

## 4.2 Hybrid approach for MWEs alignment based on morpho-syntactic patterns

The hybrid approach for MWEs alignment is composed of the following two steps (Bouamor et al. 2012a,c,b):

1. MWEs identification: The method used to extract MWEs is based on a symbolic approach relying on morpho-syntactic patterns.

2. MWEs alignment: After extracting MWE candidates, context vectors from the parallel corpus are separately built and similarity scores between one MWE and all target MWEs are computed.

### 4.2.1 MWEs extraction

The method to extract monolingual MWEs from a parallel corpus is based on a symbolic approach relying on morpho-syntactic patterns. It handles both frequent and infrequent expressions and do not use any lexicon. This method involves a full morpho-syntactic analysis of source and target texts. The analysis
is done using the CEA LIST Multilingual Analysis platform LIMA (Besançon et al. 2010), which produces Part-of-Speech (POS) tags and lemmas associated to each word. Since most MWEs consist of noun, adjectives and prepositions, we adopted a linguistic filter. It consists in keeping only *n*-gram (*n* from 2 to 4) units, which match with a list of a hand created morpho-syntactic patterns. Such process is used to keep only specific strings and filter out undesirable ones such as candidates composed mainly of stop words (*of a, is a, that was*). The algorithm operates on lemmas instead of surface forms which can draw on richer statistics and overcome the data sparseness problems.

In Table 2, we give an example of MWEs produced for each pattern. There exists extraction patterns (or configurations) for which no MWE has been generated (i.e., Noun-Adj). To this list are added some prepositional idiomatic expressions (*in particular, in the light of, as regards, etc.*) and named entities (*Middle East, South Africa, United States of America, etc.*) recognized by the morpho-syntactic analyzer LIMA. Then, we scored all extracted MWEs with their total frequency of occurrence in the corpus. To avoid an over-generation of MWEs and remove irrelevant candidates from the process, a redundancy cleaning approach is introduced. In this approach, if a MWE is nested in another, and they both have the same frequency, we discard the smaller one. Otherwise we keep both of them. We consider also the case in which a MWE appears in a high number of terms and discard all longer ones.

Our approach does not use any additional correlations statistics such as Mutual Information or Log Likelihood Ratio. It finds translations for all extracted MWEs (both frequent and infrequent ones).

<table><caption>Table 2: Example of morpho-syntactic patterns used to detect MWEs in each language independently</caption><thead><tr><th>pattern</th><th>English MWE</th><th>French MWE</th></tr></thead><tbody><tr><td>Adj-Noun</td><td>plenary meeting</td><td>libre circulation</td></tr><tr><td>Noun-Noun</td><td>member state</td><td>état membre</td></tr><tr><td>Noun-Prep-Noun</td><td>point of view</td><td>point de vue</td></tr><tr><td>Noun-Prep-Adj-Noun</td><td>court of first instance</td><td>court de première instance</td></tr></tbody></table>

### 4.2.2 MWEs alignment

MWEs alignment aims to find for each MWE in a source language its adequate translation in the target one. This task used to be handled through an external
linguistic resource such as bilingual lexicons or single words alignment tools. Our approach for MWEs alignment is resource-independent and uses a parallel corpus and a list of input MWEs candidates to translate. It associates a specific representation to each expression (source and target).

We associate to each MWE an *N* sized vector, where *N* is the number of sentences in the corpus, indicating whether it appears or not in each sentence of the corpus. Our algorithm is based on the Vector Space Model (Salton et al. 1975). This vector space representation will serve, eventually, as a basis to establish a translation relation between each pair of MWEs.

To extract translation pairs of MWEs, we propose an iterative alignment algorithm operating as follows:

1. Find the most frequent MWE *exp* in each source sentence;

2. Extract all target translation candidates, appearing in all parallel sentences to those containing *exp*;

3. Compute a confidence value $V_{\text{Conf}}$ for each translation relation between *exp* and all target translation candidates;

4. Consider that the target MWE maximizing $V_{\text{Conf}}$ is the best translation;

5. Discard the translation pair from the process and go back to 1.

To compute the confidence value $V_{\text{Conf}}$, we adopted the *Jaccard Index*. This measure is based on the number $I_{st}$ of sentences shared by each target and a source MWE. $I_{st}$ is normalized by the sum of the number of sentences where the source and target MWEs appear independently of each other (respectively $V_s$ and $V_t$) decreased by $I_{st}$.

$$ (3) \qquad Jaccard = \frac{I_{st}}{V_s + V_t - I_{st}} $$

We illustrate in Table 3, a sample of aligned MWEs by means of the algorithm described above. When we observe MWE pairs, we noticed that our method has two advantages. On the one hand, it allows the translation of MWEs aligned in most previous work (Dagan & Church 1994; Ren et al. 2009) using single words alignment tools to establish word-to-word alignment relations. The approach can capture the semantic equivalence between expressions such as *insulaire en développement* and *small island developing* in a different way. On the other hand, the approach enables the alignment of idioms such as *à nouveau* ('once more').
<table><caption>Table 3: Some examples of aligned MWEs with the hybrid approach based on morpho-syntactic patterns</caption><thead><tr><th>English MWE</th><th>French MWE</th></tr></thead><tbody><tr><td>european parliament</td><td>parlement européen</td></tr><tr><td>military coup</td><td>coup d'état</td></tr><tr><td>in favour of</td><td>en faveur de</td></tr><tr><td>no smoking area</td><td>zone non fumeur</td></tr><tr><td>small island developing</td><td>insulaire en développement</td></tr><tr><td>good faith</td><td>de bonne foi</td></tr><tr><td>competition policy</td><td>politique de concurrence</td></tr><tr><td>process of consultation</td><td>processus de consultation</td></tr><tr><td>railway sector</td><td>chemin de fer</td></tr><tr><td>with regard to</td><td>en ce qui concerne</td></tr><tr><td>once more</td><td>à nouveau</td></tr><tr><td>cut in forestation</td><td>coupe forestière</td></tr></tbody></table>

## 4.3 Hybrid approach for MWEs alignment based on linear programming

This section describes a hybrid approach combining linguistic and statistical information which performs terminology extraction and alignment of MWEs from parallel texts in one step (Marchand & Semmar 2011).

Most of works on MWEs alignment are divided in two tasks: a monolingual step in which candidate terms are extracted and a bilingual step in which these terms are aligned with their translations (Gaussier & Yvon 2011). Word alignment techniques are generally used to achieve the bilingual step. These approaches in multiple steps have the disadvantage to potentially propagate errors.

The main idea of the hybrid approach for MWEs alignment based on linear programming is to consider the global task of selection and alignment as an optimization problem. The challenge when we deal with alignment of MWEs is the exponential complexity of such a task. The possible number of fragments in a sentence improves exponentially according to the number of the words of the sentence. Several works impose some constraints on the number of fragments of a MWE. In our approach, the only restriction we made on MWEs is contiguity. The advantage to assume the continuity is to enable a linearized formulation of the optimization problem to solve. We use an integer linear programming approach inspired by the work described in DeNero & Klein (2008) to quickly find an approximated optimal solution.
### 4.3.1 Linear programming model

A sentence pair consists of two word sequences: e and f. $e_{ij}$ is the MWE from between-word positions i to j of e. $f_{kl}$ is the same for f. A link is an aligned pair of MWEs, denoted ($e_{ij}, f_{kl}$). Each $e_{ij}$ is allowed to be linked with several $f_{kl}$ and each $f_{kl}$ with several $e_{ij}$. An alignment a of the sentence pair (e, f) is a segmentation of the two sentences in MWEs with the set of links between these MWEs. We use a real-valued function $\phi: \{e_{ij}\} \times \{f_{kl}\} \rightarrow R$ to score links. The score of an alignment is then the product of all the links inside it:

$$ (4) \qquad \phi(a) = \prod_{(e_{ij}, f_{kl}) \in a} \phi(e_{ij}, f_{kl}) $$

<figure><img src="image_82.png" /><figcaption>Figure 2: Example of alignment</figcaption></figure>

In the example shown in Figure 2, the score of the alignment is computed as follows:

$$ (5) \qquad \phi(a) = \phi(e_{0,2}, f_{0,2}) \times \phi(e_{2,3}, f_{2,3}) $$

Formally this function has no constraints other than that of being real. In practice, we choose a function that gives an idea about the relevance to align such fragments. The higher the score, the higher the relevance of alignment is important. Therefore, we look for the alignment (segmentation + links) that maximizes the score described above.

First, we introduce binary variables $A_{i,j,k,l}$ denoting whether ($e_{ij}, f_{kl} \in a$). Furthermore, we introduce binary indicators $E_{i,j}$ and $F_{k,l}$ that denote whether some ($e_{ij}, \cdot$) or ($\cdot, f_{kl}$) appears in a, respectively. Finally, we will use $W_{i,j,k,l} = \log \phi(e_{ij}, f_{kl})$ to transform the product into a sum. When optimized<fnref n="1" />, the integer program yields the optimal alignment:

<footnote n="1">¹We used the open source solver GLPK (GNU Linear Programming Kit), available at http://www.gnu.org/s/glpk/.</footnote>
$$
(6) \quad \left\{
\begin{array}{@{}l@{\quad}l@{}}
\max & \displaystyle\sum_{i,j,k,l} W_{i,j,k,l} A_{i,j,k,l} \\[1ex]
\forall x : & 1 \le x \le |e| \qquad \sum_{i,j: i<x \le j} E_{i,j} = 1 \qquad (1) \\[1ex]
\forall y : & 1 \le y \le |f| \qquad \sum_{k,l: k<y \le l} F_{k,l} = 1 \qquad (2) \\[1ex]
\forall i, j & \sum_{k,l} A_{i,j,k,l} \ge E_{i,j} \qquad (3) \\[1ex]
\forall k, l & \sum_{i,j} A_{i,j,k,l} \ge F_{k,l} \qquad (4) \\[1ex]
\forall i, j, k, l & 2 \cdot A_{i,j,k,l} \le E_{i,j} + F_{k,l} \qquad (5)
\end{array}
\right.
$$

With the following constraints:

$$
(7) \quad \left\{
\begin{array}{lll}
0 \le i < |e|, & 0 < j \le |e|, & i < j \\
0 \le k < |f|, & 0 < l \le |f|, & k < l
\end{array}
\right.
$$

Constraints (1) and (2) indicate that a word is inside exactly one phrase. Con-
straint (3) ensures that each phrase in the selected partition of *e* appears in at
least one link (and likewise constraint (4) for *f*). Finally, constraint (5) ensures
that if a link exists between *e*<sub>ij</sub> and *f*<sub>kl</sub> (i.e. *A*<sub>i,j,k,l</sub> = 1) then *e*<sub>ij</sub> and *f*<sub>kl</sub> are in the
selected partitions of *e* and *f*.

In that way, our approach differs from the one proposed in DeNero & Klein
(2008). Their work focuses on bijective alignments while we consider surjective
alignments. We have also modified constraints (3) and (4) and added constraint
(5) to allow a phrase to be aligned with several other phrases. We have chosen this
formalism because phrases are not necessarily composed of contiguous words.

This integer program can work with any real-valued scoring function.

4.3.2 Co-occurrence based metric

We use a corpus aligned sentence-by-sentence to compute co-occurrence dis-
tance. For each MWE, we consider the presence or absence in each sentence.
Then the score between two MWEs e<sub>ij</sub> and f<sub>kl</sub> is calculated as follows:

$$
(8) \quad \phi_c(e_{ij}, f_{kl}) = \frac{\sum_{s' \in S} N_{s'}(e_{ij}) \times N_{s'}(f_{kl})}{\sum_{s \in S} N_s(e_{ij}) + N_s(f_{kl}) - N_s(e_{ij}) \times N_s(f_{kl})}
$$
Where $N_s(e_{ij})$ is 1 if the phrase $e_{ij}$ of the first language is present in the sentence $s$ of the corpus $S$ and 0 otherwise. $N_s(f_{kl})$ is similar for the other language.

This score calculates the number of common presence of both phrases divided by the number of total presence of either phrase. Note that if none of $e_{ij}$ or $f_{kl}$ appears in the whole corpus, the score is set to 0. Indeed, if two MWEs appear exactly in the same bi-sentences, they are probably translation of each other and the score will be 1. The example in Table 4 illustrates this score.

<table><caption>Table 4: Example of ambiguous translation of MWEs</caption><tr><td>Je mange un <i>avocat</i> - I'm eating an <i>avocado</i></td></tr><tr><td>L'<i>avocat</i> prend la parole - The <i>lawyer</i> takes the floor</td></tr></table>

In this small corpus, $N_1(\text{avocat}) = 1$, $N_1(\text{avocado}) = 1$, $N_2(\text{avocat}) = 1$ and $N_2(\text{avocado}) = 0$. Thus, the co-occurence score for the bi-gram $\text{avocat}/\text{avocado}$ has the value:

$$ (9) \qquad \phi_c(\text{avocado}, \text{avocat}) = \frac{(1 \times 1) + (1 \times 0)}{(1 + 1 - 1 \times 1) + (1 + 0 - 1 \times 0)} = \frac{1}{2} $$

We observed after aligning some sentences that when both sentence structures are similar, the aligner performs well as shown in Figure 3. The segmentation is word to word or MWE to MWE depending on what is more frequent in the corpus. Moreover, the surjective formulation of the problem allows us to begin to detect expressions in two parts. We can see that *rôle* is linked to both *role* and *play* (Figure 3, Alignment 3).

This would have been impossible with the bijective formulation of DeNero & Klein (2008). This result is encouraging but not yet sufficient. Actually this expression is partially recognized because it includes two plain words. Expressions with postponed prepositions would not be recovered this way because the prepositions are too common to be statistically relevant. If the structure is different we have more difficulties (as shown in Figure 4). Some sentences are also difficult to align because they are not perfect translation: *They/la population* or adverbs like *also* or *very* which are not translated.

We also observe that, for common words, the distribution of apparition is meaningless: *to* is linked with *de* and *a*. We should use a measure of information as suggested in Gao (1998). In addition, the program is powerless if it finds an unknown word or if a word co-occurs with no other word of the translated sentence. In that case, all links containing this word will obtain the score of 0 as
<figure><img src="image_83.png" /><figcaption>Figure 3: Good alignments with co-occurrence based metric</figcaption></figure>

<figure><img src="image_84.png" /><figcaption>Figure 4: Bad alignments with co-occurrence based metric</figcaption></figure>
they never occur. And as we use a multiplicative metric, the global score of the alignment will be 0 whatever the other links of the alignment. Unknown links should have a small, non-null score to allow the discovery of new links. Moreover, we can use an external resource such as a bilingual lexicon of single words which can improve the alignment of phrases.

### 4.3.3 Bilingual dictionary based metric

The bilingual dictionary gives us several word-to-word alignments. We want to comply with these alignments as often as possible as we infer that they are mostly correct. The dictionary also gives negative alignment information. Of course if two words are not aligned by the dictionary we cannot take for sure that they should not. But we have to take that into account.

The bilingual dictionary score is calculated as follows:

$$ (10) \qquad \phi_c(e_{ij}, f_{kl}) = \frac{a \times R_1 + b \times R_0}{a \times R_1 + b \times R_0 + c \times N_1 + d \times N_0} $$

$R_1$ is the number of respected links, $R_0$ is the number of respected non-links, $N_1$ is the number of non-respected links, and $N_0$ is the number of non-respected non-links.

The coefficients $a, b, c$ and $d$ can be adapted to balance the relative influence of the four terms. We analyzed a small corpus that allowed us to empirically choose the use of the following values: $a = b = c = 1$ and $d = 0.5$. The score is calculated for each part of the bi-phrase and then the two of them are multiplied. We have to take into account $R_0$ and $N_0$ because otherwise the whole bi-sentence would be the optimal segmentation.

As we can see, this metric has a double effect. First, it gives a high score if bi-phrases respect dictionary word to word alignment. And second, due to $R_0$, it sets a threshold score for unknown couples. Both effects can have a positive role in alignment task as we will see in the following examples. The dictionary-based metric is not intended to be used separately. It is mixed with co-occurrence score. We used an English-French bilingual dictionary containing 243,539 entries with doubles.<fnref n="2" />

In Figure 5, we observe some degradation of alignments. For these sentences, the threshold for unknown couples is too high relatively to the statistical score.

<footnote n="2">²http://catalog.elra.info/product_info.php?products_id=666.</footnote>
<figure><img src="image_85.png" /><figcaption>Figure 5: Degradation of alignments – (a) Alignments without the bilingual dictionary and (b) Alignments with the bilingual dictionary</figcaption></figure>

So we lose the benefit of the co-occurrence metric. This problem should be partially solved by scaling the two metrics. However we have already observed some improvements, as presented in Figure 6. In the first example, the bilingual dictionary gives the alignments: *be/être, decided/décidé and there/y*. So the program manages to reconstruct the whole expression *is to be decided on there/doit y être décidé*. Moreover the links *concrete/concret and programme/programme* are strengthened. The second example is difficult to align due to the difference of structure. The alignment with dictionary is not perfect but is far more better. In this case the dictionary only gives links *verdict/jugement and request/requête* which were already aligned. However they are strengthened and others links are weakened. That is why we can observe an improvement.

Finally in the last example, the dictionary gives no links because the words are not lemmatized. The good result is here exclusively due to the threshold effect. The programme is allowed to consider links with no co-occurrence as long as others links have a good co-occurrence score.
<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>

<figure><img src="image_89.png" /></figure>

<figure><img src="image_90.png" /></figure>

<figure><img src="image_91.png" /><figcaption>Figure 6: Amelioration of alignments – (a) Alignments without the bilingual dictionary and (b) Alignments with the bilingual dictionary</figcaption></figure>
# 5 Experimental results

The quality of alignment of MWEs and the impact of using MWEs on machine translation have been evaluated, firstly, manually, by comparing the results of the three MWEs aligners with a reference alignment; and secondly automatically by using the results of the three MWEs aligners to build the translation model of the state-of-the-art statistical machine translation system Moses (Koehn et al. 2007).

## 5.1 Manual evaluation

The three approaches for MWEs alignment and the baseline Giza++ (Och & Ney 2000) have been evaluated using the following evaluation metrics. Given an alignment A, and a gold standard alignment (reference alignment) G, each such alignment set eventually consisting of two sets ($A_s, A_p$), and ($G_s, G_p$) where “s” and “p” correspond respectively to “sure” and “probable” alignments. The following measures are defined (where T is the alignment type, and can be set to either S or P). Each word aligner was evaluated in terms of Precision ($P_T$), Recall ($R_T$) and F-Measure ($F_T$).

$$ (11) \qquad P_T = \frac{A_T \cap G_T}{A_T}; \quad R_T = \frac{A_T \cap G_T}{G_T}; \quad F_T = \frac{2 \times P_T \times R_T}{P_T + R_T} $$

The corpus used to evaluate the performance of the English-French MWE aligners is composed of a set of 1992 parallel sentences extracted from Europarl (European Parliament Proceedings). This parallel corpus is composed of 46265 English words and 49332 French words and has been used to build manually the reference alignment by the Yawat tool (Germann 2008).

Table 5 summarizes the results of the three approaches for English-French MWEs alignments and the baseline (Giza++) in terms of precision, recall and F-measure.

The first observation is that, the hybrid approach based on morpho-syntactic patterns performs better than all the other methods. It clearly appears that the morpho-syntactic patterns used to extract the MWEs present in source and target texts has had a significant impact on the precision of the alignment. On the other hand, the statistical approach has the lower recall but it is better than the recall of the baseline (Giza++). And as a second observation, adding information coming from a bilingual lexicon to the co-occurrence metric used in the hybrid approach based on linear programming, certainly has improved the precision but the recall has dropped.
<table><caption>Table 5: Performance of the different English-French MWE aligners</caption><thead><tr><th>MWE aligner</th><th>precision</th><th>recall</th><th>f-measure</th></tr></thead><tbody><tr><td>Baseline (Giza++)</td><td>0.83</td><td>0.37</td><td>0.51</td></tr><tr><td>Statistical</td><td>0.81</td><td>0.39</td><td>0.52</td></tr><tr><td>Hybrid using morpho-syntactic patterns</td><td>0.87</td><td>0.55</td><td>0.67</td></tr><tr><td>Hybrid using co-occurrence</td><td>0.61</td><td>0.63</td><td>0.61</td></tr><tr><td>Hybrid using co-occurrence + lexicon</td><td>0.85</td><td>0.54</td><td>0.66</td></tr></tbody></table>

## 5.2 Alignment evaluation through a translation task

The unavailability of a reference alignment of a significant size for MWEs does not allow us to achieve a large evaluation and to compare our approaches with the state-of-the-art work. That’s why we decided to study the impact of MWEs on the quality of translation by integrating the results of our word aligners in the training corpus used to extract the translation model of the phrase based statistical machine translation system Moses. We use the factored translation model (Koehn & Hoang 2007) as our baseline system. It is an extension of the phrase based models which are limited to the mappings of phrases without any explicit use of linguistic information. The factored model enables the use of additional markup at the word level (Figure 7).

Our model operates on lemmas instead of surface forms, in which the translation process is broken up into a sequence of mapping steps that either:

* Translate source lemmas into target’s ones.

* Generate surface forms given the lemma.

The features used in the baseline system include: (1) four translation probability features, (2) two language models, (3) one generation model and (4) word penalty.

The goal of these experiments is to study in what respect MWEs are useful to improve the performance of Moses. In Moses, phrase tables are the main knowledge source for the machine translation decoder. The decoder consults these tables to figure out how to translate an input sentence into the target language. These tables are built automatically using the open source word alignment tool Giza++ (Och & Ney 2000). However, Giza++ could produce errors in particular when it aligns multiword expressions (Fraser & Marcu 2007). In order to integrate into Moses the bilingual lexicon which is extracted automatically by the MWE alignment approaches, we propose the following three methods:
<figure><img src="image_92.png" /><figcaption>Figure 7: Factored model used in the SMT baseline system</figcaption></figure>

**CORPUS:** In this method, we add the extracted bilingual lexicon as a parallel corpus and retrain the translation model. By increasing the occurrences of the MWEs and their translations, we expect a modification of alignment and probability estimation.

**TABLE:** This method consists in adding the extracted bilingual lexicon into Moses's phrase table. We use a smoothed probability estimator to construct a translation probability for each MWE of the bilingual lexicon. This estimator is based on the similarity measure provided by each word alignment approach.

**FEATURE:** In this method, we extend the “TABLE” method by adding a new feature indicating whether a MWE comes from the bilingual lexicon or not (1 or 0 is introduced for each entry of the phrase table).
### 5.2.1 Data and experimental setup

In order to study the impact of the bilingual lexicon of MWEs on the performance of Moses, we conducted our experiments on two English-French parallel corpora (Table 6): Europarl (European Parliament Proceedings) and Emea (European Medicines Agency Documents). These corpora were extracted from the open parallel corpus OPUS (Tiedemann 2012). For each MWE alignment approach, we achieved three runs and two test experiments for each run: In-Domain and Out-Of-Domain. For this, we randomly extracted 500 parallel sentences from Europarl as an In-Domain corpus and 500 pairs of sentences from Emea as Out-Of-Domain corpus. The domain vocabulary is represented in the case of our baseline (Moses) respectively by the specialized parallel corpus Emea which is added to the training data (Europarl). Afterwards, we extracted bilingual MWEs from the training corpus and applied the three methods described above. For the three integration methods (CORPUS, TABLE, FEATURE), the domain vocabulary is identified by a bilingual lexicon which is extracted automatically from the specialized parallel corpus Emea using the different MWEs alignment approaches.

<table><caption>Table 6: Europarl and Emea corpora details used to train language and translation models of Moses (K refers to $10^3$)</caption><thead><tr><td>Run n°.</td><td>Training (# sentences)</td><td>Tuning (# sentences)</td></tr></thead><tbody><tr><td>1</td><td>150K+10K (Europarl+Emea)</td><td>2K+0.5K (Europarl+Emea)</td></tr><tr><td>2</td><td>150K+20K (Europarl+Emea)</td><td>2K+0.5K (Europarl+Emea)</td></tr><tr><td>3</td><td>150K+30K (Europarl+Emea)</td><td>2K+0.5K (Europarl+Emea)</td></tr></tbody></table>

### 5.2.2 Results and discussion

The performance of the SMT system Moses is evaluated using the BLEU score (Papineni et al. 2002) on the two test sets for the three runs described in the previous section. Note that we consider one reference per sentence. The obtained results are reported in Tables 7, 8, 9 and 10.

As shown in Tables 6, 7, 8 and 9, for In-Domain texts, Moses achieve a relatively high BLEU score and the scores of Moses when using the results of the hybrid approach based on morpho-syntactic patterns are better in all the runs. The best improvement is achieved using the “FEATURE” method. The “CORPUS” method (when compared to the baseline system) comes next with a slightly higher BLEU score with an improvement for In-Domain sentences and Out-Of-Domain texts.
9 Extracting and aligning multiword expressions from parallel corpora

<table><caption>Table 7: BLEU scores of Moses when using the results of the statistical approach</caption><thead><tr><th rowspan="2">Run n°.</th><th colspan="4">In-Domain (Europarl)</th><th colspan="4">Out-Of-Domain (Emea)</th></tr><tr><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th></tr></thead><tbody><tr><td>1</td><td>32.62</td><td>32.41</td><td>32.36</td><td>32.55</td><td>22.96</td><td>22.82</td><td>22.75</td><td>22.91</td></tr><tr><td>2</td><td>33.81</td><td>33.76</td><td>33.71</td><td>33.79</td><td>23.30</td><td>23.09</td><td>23.04</td><td>23.27</td></tr><tr><td>3</td><td>34.25</td><td>34.23</td><td>34.21</td><td>34.24</td><td>24.55</td><td>24.49</td><td>24.45</td><td>24.52</td></tr></tbody></table>

<table><caption>Table 8: BLEU scores of Moses when using the results of the hybrid approach based on morpho-syntactic patterns</caption><thead><tr><th rowspan="2">Run n°.</th><th colspan="4">In-Domain (Europarl)</th><th colspan="4">Out-Of-Domain (Emea)</th></tr><tr><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th></tr></thead><tbody><tr><td>1</td><td>32.62</td><td>32.82</td><td>32.15</td><td>32.88</td><td>22.96</td><td>23.45</td><td>23.11</td><td>23.69</td></tr><tr><td>2</td><td>33.81</td><td>34.05</td><td>33.48</td><td>34.09</td><td>23.30</td><td>24.09</td><td>23.76</td><td>24.18</td></tr><tr><td>3</td><td>34.25</td><td>34.64</td><td>34.11</td><td>34.67</td><td>24.55</td><td>25.43</td><td>25.05</td><td>25.48</td></tr></tbody></table>

<table><caption>Table 9: BLEU scores of Moses when using the results of the hybrid approach based on linear programming</caption><thead><tr><th rowspan="2">Run n°.</th><th colspan="4">In-Domain (Europarl)</th><th colspan="4">Out-Of-Domain (Emea)</th></tr><tr><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th></tr></thead><tbody><tr><td>1</td><td>32.62</td><td>32.69</td><td>32.64</td><td>32.72</td><td>22.96</td><td>23.03</td><td>22.97</td><td>23.06</td></tr><tr><td>2</td><td>33.81</td><td>33.88</td><td>33.85</td><td>33.91</td><td>23.30</td><td>23.37</td><td>23.34</td><td>23.40</td></tr><tr><td>3</td><td>34.25</td><td>34.30</td><td>34.27</td><td>34.33</td><td>24.55</td><td>24.59</td><td>24.56</td><td>24.62</td></tr></tbody></table>

<table><caption>Table 10: BLEU scores of Moses when using the results of the hybrid approach based on linear programming and using a bilingual dictionary</caption><thead><tr><th rowspan="2">Run n°.</th><th colspan="4">In-Domain (Europarl)</th><th colspan="4">Out-Of-Domain (Emea)</th></tr><tr><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th><th>Baseline</th><th>CORPUS</th><th>TABLE</th><th>FEATURE</th></tr></thead><tbody><tr><td>1</td><td>32.62</td><td>32.71</td><td>32.68</td><td>32.73</td><td>22.96</td><td>23.06</td><td>22.97</td><td>23.07</td></tr><tr><td>2</td><td>33.81</td><td>33.89</td><td>33.87</td><td>33.92</td><td>23.30</td><td>23.39</td><td>23.32</td><td>23.39</td></tr><tr><td>3</td><td>34.25</td><td>34.32</td><td>34.29</td><td>34.32</td><td>24.55</td><td>24.62</td><td>24.56</td><td>24.63</td></tr></tbody></table>
In order to show the impact of the domain vocabulary (represented by the bilingual MWEs extracted with the aligner based on the hybrid approach with morpho-syntactic patterns), on the translation quality of Moses, we manually analyzed an example of translations drawn from the Out-Of-Domain test corpus (Table 11).

<table><caption>Table 11: Translations produced by Moses for an Out-Of-Domain sentence</caption><tr><td>Input sentence</td><td>in the 12 week acute phase of three clinical trials of duloxetine in patients with diabetic neuropathic pain, small but statistically significant increases in fasting blood glucose were observed in duloxetine-treated patients.</td></tr><tr><td>Reference translation</td><td>lors de la phase aiguë de 12 semaines de trois essais cliniques étudiant la duloxétine chez les patients souffrant de douleur neuropathique diabétique, des augmentations faibles, mais statistiquement significatives de la glycémie à jeun ont été observées chez les patients sous duloxétine.</td></tr><tr><td>Moses translation with the “CORPUS” integration method</td><td>dans le 12 semaines de la phase aiguë trois études cliniques de duloxetine chez les patients avec douleur neuropathique diabétique, petites mais statistiquement significatives augmentations de répréhensible glycémie artérielle a été observée chez les patients traités duloxetine.</td></tr><tr><td>Moses translation with the “TABLE” integration method</td><td>dans le 12 semaine de la phase aiguë de trois essais cliniques de duloxetine dans les patients avec douleur neuropathique diabétique, petites mais statistiquement augmentations considérables dans le sang répréhensible glucose ont été constatées dans les patients duloxetine traités.</td></tr><tr><td>Moses translation with the “FEATURE” integration method</td><td>dans le 12 semaines de la phase aiguë de trois essais cliniques chez les patients avec douleur neuropathique diabétique, petites mais des augmentations statistiquement significatives de la glycémie à jeun ont été observées chez les patients traités duloxetine.</td></tr></table>
After analyzing the translations of this example, it is clear that in some cases, it is just impossible to perform a word-to-word alignment between two MWEs that are translation of each other. For example, the “FEATURE” method proposes the compound word *glycémie à jeun* as a translation for the expression *fasting blood glucose* which is correct, but, “CORPUS” and “TABLE” methods propose respectively the translations *répréhensible glycémie artérielle* and *sang répréhensible glucose* which are completely wrong. However, all the integration methods translate correctly the multiword expressions *diabetic neuropathic pain/douleur neuropathique diabétique* and *acute phase/phase aiguë*. The multiword expression *clinical trials/essais cliniques* is translated correctly by “TABLE” and “FEATURE” methods. Likewise, the translation provided by the “CORPUS” method for this expression is also correct *clinical trials/études cliniques* but it is different from the translation of the reference. It seems that the probabilities of the alignments proposed by Giza++ for these multiword expressions were very high and helped Moses decoder to choose these alignments. On the other hand, as we can see, all the translations have many spelling and grammatical errors, and in particular, the translations of some multiword expressions (‘statistically significant increases’/*statistiquement significatif augmentations*, ‘statistically significant increases’/*statistiquement augmentations considérables*) produced by the “CORPUS” and “TABLE” methods are very approximate. This result can be explained by the fact that, on the one hand, statistical machine translation toolkits like Moses have not been designed with grammatical error correction in mind, and on the other hand, Giza++ could produce errors in particular when it aligns multiword expressions (Fraser & Marcu 2007). For the multiword expression *duloxetine-treated patients*, the methods “FEATURE” and “CORPUS” provide a same translation which is more or less correct (*patients traités duloxetine*). However, the method “TABLE” provides a translation in a poor grammar (*patients duloxetine traités*).

Finally on this point, we can observe that the major issues of Moses concern errors produced by Giza++ when aligning multiword expressions (translation model), and incorrect spelling and poor grammar generated by the decoder (language model). To handle the first issue, we proposed to take into account the specialized bilingual lexicon extracted with the MWEs aligner into Moses’s phrase table and we added a new feature indicating whether a word comes from this lexicon or not (“FEATURE” method). However, for spelling and grammar errors, Moses has no specific treatment.
# 6 Conclusion and future work

We have described, in this chapter, three approaches aiming to extract and align MWEs in English-French parallel corpora. We have also presented an experimental evaluation of the impact of integrating the results of these MWEs alignment approaches on the performance of the statistical machine translation system Moses. We have more specifically shown that, on the one hand, the hybrid approach based on morpho-syntactic patterns performs better than the other approaches and the “FEATURE” integration method achieves the best improvement, and on the other hand, using MWEs as additional parallel sentences to train the translation model of Moses improves its BLEU score.

This study offers several open issues for future work. First, we should explore machine learning approaches to extend the morphosyntactic patterns to take into account other forms of MWEs. The second perspective is to explore the integration of bilingual MWEs into other machine translation models such as rule-based translation ones. We also expect to explore the use of LSTM (Long Short-Term Memory) recurrent neural network language models for rescoring the *n*-best translations produced by Moses in order to reduce grammar errors.

# References

* Barbu, Ana Maria. 2004. Simple linguistic methods for improving a word alignment algorithm. In *Proceedings of the 7th international conference on the Statistical Analysis of Textual Data (JADT 2004)*, 88–98. Louvain-la-Neuve, Belgium.

* Barz, Irmhild. 1996. Komposition und Kollokation. In Clemens Knobloch & Burkhard Schaeder (eds.), *Nomination – fachsprachlich und gemeinsprachlich*, 127–146. Springer.

* Besançon, R., G. De Chalendar, O. Ferret, F. Gara, M. Laib, O. Mesnard & N. Semmar. 2010. LIMA: A multilingual framework of linguistic analysis and linguistic resources development and evaluation. In *Proceedings of the seventh international conference on Language Resources and Evaluation (LREC 2010)*, 3697–3704.

* Blank, Ingeborg. 2000. Terminology extraction from parallel technical texts. In *Parallel text processing*, 237–252. Springer.

* Bouamor, Dhouha, Nasredine Semmar & Pierre Zweigenbaum. 2012a. A study in using English-Arabic multiword expressions for statistical machine translation. In *Proceedings of the fourth international conference on Arabic Language Processing (CITALA-2012)*, 71–76. Rabat, Morocco.
Bouamor, Dhouha, Nasredine Semmar & Pierre Zweigenbaum. 2012b. Automatic construction of a multiword expressions bilingual lexicon: A statistical machine translation evaluation perspective. In *Proceedings of the 3rd workshop on Cognitive Aspects of the Lexicon (CogALex-III)*, 95–108. Mumbai, India.

Bouamor, Dhouha, Nasredine Semmar & Pierre Zweigenbaum. 2012c. Identifying bilingual multi-word expressions for statistical machine translation. In *Proceedings of the eighth international conference on Language Resources and Evaluation (LREC 2012)*, 674–679. Istanbul, Turkey.

Boulaknadel, Siham, Béatrice Daille & Driss Aboutajdine. 2008. A multiterm extraction program for Arabic language. In *Proceedings of the international conference on Language Resources and Evaluation (LREC 2008)*, 1485–1488. Marrakech, Morocco.

Burger, H. 2010. Phraseologie: Eine Einführung am Beispiel des Deutschen [Phraseology: An introduction for German]. *Grundlagen der Germanistik* 36(4).

Calzolari, Nicoletta, Alessandro Lenci, Francesca Bertagna & Antonio Zampolli. 2002. Broadening the scope of the EAGLES/ISLE lexical standardization initiative. In *COLING ’02: proceedings of the 3rd workshop on Asian Language Resources and International Standardization*, 1–8. Morristown, NJ, USA: Association for Computational Linguistics.

Carpuat, Marine & Mona Diab. 2010. Task-based evaluation of multiword expressions: A pilot study in statistical machine translation. In *Human Language Technologies: the 2010 annual conference of the North American chapter of the Association for Computational Linguistics (NAACL/HLT 2010)*, 242–245.

Choueka, Yaacov. 1988. Looking for needles in a haystack or locating interesting collocational expressions in large textual databases. In *Proceedings of the 2nd international conference on Computer-Assisted Information Retrieval (recherche d'information assistée par ordinateur) - RIAO'88*, 609–624. Cambridge, MA, USA.

Constant, Mathieu, Isabelle Tellier, Denys Duchier, Yoann Dupont, Anthony Siggogne & Sylvie Billot. 2011. Intégrer des connaissances linguistiques dans un CRF: application à l'apprentissage d'un segmenteur-étiqueteur du français. In *Taln*, vol. 1, 321.

Dagan, Ido & Ken Church. 1994. Termight: Identifying and translating technical terminology. In *Proceedings of the fourth conference on Applied Natural Language Processing (ANLP'94)*, 34–40.

Daille, Béatrice. 2001. Extraction de collocation à partir de textes. In *Actes de la 8ème conférence sur le Traitement Automatique des Langues Naturelles (TALN)*, 3–8. Tours, France: Association pour le Traitement Automatique des Langues.
Daille, Béatrice, Eric Gaussier & Jean-Marc Langé. 1994. Towards automatic extraction of monolingual and bilingual terminology. In *Proceedings of the 15th international conference on Computational linguistics (COLING 1994)*, 515–521.

DeNero, John & Dan Klein. 2008. The complexity of phrase alignment problems. In *Proceedings of the 46th annual meeting of the Association for Computational Linguistics on Human Language Technologies: Short papers*, 25–28.

Fraser, Alexander & Daniel Marcu. 2007. Measuring word alignment quality for statistical machine translation. *Computational Linguistics* 33(3). 293–303.

Gao, Zhao-Ming. 1998. Automatic acquisition of a high-precision translation lexicon from parallel Chinese-English corpora. *Language* 248. 254.

Gaussier, Éric & François Yvon. 2011. *Modèles statistiques pour l'accès à l'information textuelle*. Lavoisier.

Germann, Ulrich. 2008. Yawat: Yet another word alignment tool. In *Proceedings of the ACL-08: HLT demo session*, 20–23. Columbus, Ohio, USA: Association for Computational Linguistics. https://www.aclweb.org/anthology/P08-4006.

Hogan, Deirdre, Conor Cafferkey, Aoife Cahill & Josef Van Genabith. 2007. Exploiting multi-word units in history-based probabilistic generation. In *Proceedings of the joint conference on Empirical Methods in Natural Language Processing (EMNLP) and Computational Natural Language Learning (CoNLL)*, 267–276. Prague, Czech Republic.

Jackendoff, Ray. 1997. *The architecture of the language faculty*. Cambridge, MA, USA: MIT Press.

Koehn, Philipp & Hieu Hoang. 2007. Factored translation models. In *Proceedings of the 2007 joint conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)*, 868–876.

Koehn, Philipp, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcoello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin & Eva Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In *Proceedings of the 45th annual meeting of the ACL on interactive poster and demonstration sessions*, 177–180. Prague, Czech Republic.

Kupiec, Julian. 1993. An algorithm for finding noun phrase correspondences in bilingual corpora. In *Proceedings of the 31st annual meeting on Association for Computational Linguistics*, 17–22.

Marchand, Morgane & Nasredine Semmar. 2011. A hybrid multi-word terms alignment approach using word co-occurrence with a bilingual lexicon. In *Proceedings of the fifth Language and Technology Conference: Human language technologies as a challenge for computer science and linguistics*, 430–434. Poznań, Poland.
Nivre, Joakim & Jens Nilsson. 2004. Multiword units in syntactic parsing. In *Workshop on Methodologies and Evaluation of Multiword Units in Real-World Applications*, 39–46.

Och, F. J. & H. Ney. 2000. Improved statistical alignment models. In *Proceedings of the 38th annual meeting on Association for Computational Linguistics (acl 2000)*, 440–447.

Okita, Tsuyoshi, Alfredo Maldonado Guerra, Yvette Graham & Andy Way. 2010. Multi-word expression-sensitive word alignment. In *4th international workshop on Cross Lingual Information Access at COLING 2010*, 26–34. Beijing, China.

Papineni, Kishore, Salim Roukos, Todd Ward & Wei-Jing Zhu. 2002. BLEU: A method for automatic evaluation of machine translation. In *Proceedings of the 40th annual meeting on Association for Computational Linguistics (ACL 2002)*, 311–318.

Ramisch, Carlos, Aline Villavicencio & Valia Kordoni. 2013. Introduction to the special issue on multiword expressions: From theory to practice and use. *ACM Transactions on Speech and Language Processing (TSLP)* 10(2). 3.

Ren, Z., Y. Lü, J. Cao, Q. Liu & Y. Huang. 2009. Improving statistical machine translation using domain bilingual multiword expressions. In *Proceedings of the workshop on Multiword Expressions: Identification, Interpretation, Disambiguation and Applications*, 47–54.

Riehemann, Susanne. 2001. *A constructional approach to idioms and word formation*. Stanford University dissertation.

Sag, Ivan, Timothy Baldwin, Francis Bond, Ann Copestake & Dan Flickinger. 2002. Multiword expressions: A pain in the neck for NLP. In *Proceedings of the 3rd international conference on Computational Linguistics and Intelligent Text Processing* (Lecture Notes in Computer Science 2276), 1–15. Springer.

Salton, G., A. Wong & C. S. Yang. 1975. A vector space model for automatic indexing. *Communications of the ACM* 18(11). 613–620.

Semmar, Nasredine, Christophe Servan, Gaël De Chalendar, Benoît Le Ny & Jean-Jacques Bouzaglou. 2010. A hybrid word alignment approach to improve translation lexicons with compound words and idiomatic expressions. In *Proceedings of the 32nd Translating and the Computer conference (ASLIB 2010)*. London, UK.

Seretan, Violeta & Eric Wehrli. 2007. Collocation translation based on sentence alignment and parsing. In *Actes de la 14ème conférence sur le Traitement Automatique des Langues Naturelles (TALN 2007)*, 401–410. Toulouse, France.
Tiedemann, Jörg. 2012. Parallel data, tools and interfaces in OPUS. In *Proceedings of the eighth international conference on Language Resources and Evaluation (LREC-2012)*, 2214–2218. Istanbul, Turkey.

Tufiş, Dan & Radu Ion. 2007. Parallel corpora, alignment technologies and further prospects in multilingual resources and technology infrastructure. In *Proceedings of the 4th international conference on Speech and Dialogue Systems*, 183–195.

Vechtomova, Olga. 2005. The role of multi-word units in interactive information retrieval. In *European conference on Information Retrieval*, 403–420.

Vintar, Špela & Darja Fišer. 2008. Harvesting multi-word expressions from parallel corpora. In *Proceedings of the 6th edition of the Language Resources and Evaluation conference (LREC 2008)*, 1091–1096.

Wu, Chien-Cheng & Jason S Chang. 2003. Bilingual collocation extraction based on syntactic and statistical analyses. In *Proceedings of Research on Computational Linguistics conference XV (ROCLING’2003)*, 33–55. Hsinchu, Taiwan: The Association for Computational Linguistics & Chinese Language Processing (ACLCLP). http://aclweb.org/anthology/O03-1003.
Chapter 10

Cross-lingual linking of multi-word
entities and language-dependent
learning of multi-word entity patterns

Guillaume Jacquet

European Commission, Joint Research Centre, Ispra, Italy

Maud Ehrmann

Swiss Federal Institute of Technology in Lausanne (EPFL) – Digital Humanities Laboratory

Jakub Piskorski

European Commission, Joint Research Centre, Ispra, Italy

Hristo Tanev

European Commission, Joint Research Centre, Ispra, Italy

Ralf Steinberger

European Commission, Joint Research Centre, Ispra, Italy

We address large-scale multilingual multi-word entity (MWEntity) recognition and variant matching. Firstly, we recognise MWEntities in 22 different languages, identify monolingual variant spellings and link equivalent groups of variants across all languages. We then use the previously recognised MWEntities to learn new recognition rules based on distributional patterns. Not requiring any linguistic tools, the method is suitable for our highly multilingual environment. When adding the new rules to the original rule-based NER system, F1 performance for Spanish increases from 42.4% to 50% (18% increase) and for English from 43.4% to 44.5% (2.5% increase). Besides aiming at turning free text into semi-structured data for search and for machine-processing purposes, we use the system to link related news over time and across languages, as well as to detect trends.

Guillaume Jacquet, Maud Ehrmann, Jakub Piskorski, Hristo Tanev & Ralf Steinberger.
2019. Cross-lingual linking of multi-word entities and language-dependent learning of multi-word entity patterns. In Yannick Parmentier & Jakub Waszczuk (eds.), *Represen-tation and parsing of multiword expressions: Current trends*, 269–297. Berlin: Language

<figure><img src="image_93.png" /></figure>

<figure><img src="image_94.png" /></figure>
# 1 Introduction

Named Entities (NEs) such as persons, organisations, locations and events are major bearers of information in text as they provide answers to the text representation questions Who did What to Whom, Where and When. For this reason, work on NER and Classification is abundant (Nadeau & Turney 2005) and NEs have been linked to knowledge bases (Rao et al. 2013; McNamee & Dang 2009). Major challenges are homographic entity names belonging to different classes or within the same class and the existence of variant spellings within the same or across different languages, as well as morphological inflection (Steinberger et al. 2013). An additional challenge for names of organisations and events is that they may be referred to as multi-word expressions or acronyms, e.g., Economic Community of West African States (abbreviated as ECOWAS), and that name parts are likely to be translated, e.g., the equivalent Portuguese Comunidade Económica dos Estados da África Ocidental (abbreviated as CEDEAO). Users searching for such an entity will want to retrieve all mentions, independently of their spelling or abbreviation or language.

Our interest in entity variants originally stems from our multiannual work on the Europe Media Monitor (EMM), which is a freely accessible meta-news web platform<fnref n="1" /> that has been online since 2002 (Steinberger et al. 2009; 2015). EMM currently gathers an average of 300,000 news articles per day in about 70 languages from about 8,000 news websites (HTML pages and RSS feeds). News items are classified into thousands of categories and related news (e.g., from different news sources) are grouped into clusters. EMM-NewsBrief and the medical information system EMM-MediSys group the newest articles every ten minutes and show intra-day trends, while EMM-NewsExplorer groups related articles published on the same calendar day and follows trends over longer periods of time. For each news article and for each news cluster, the system displays extracted meta-information, which includes the news category, entity names found (persons, organisations and geo-locations), quotations by and about entities, as well as various types of statistics, trends and analysis results. Entity mentions are disambiguated according to entity types (e.g., Paris Hilton is a person) and geographical reference (e.g., there are about fifteen places world-wide called Paris). Spelling variants of the same person or organisation name are mostly recognised as belonging to the same real-world entity. For instance, the spellings Jean-Claude Juncker, Jean Cloud Junker, Jean-Claude Juencker, Жан-Клод Юнкер, Ζαν Κλοντ Γιούνκερ, جان کلود جونکر, Ζαν Κλοντ Γιούνκερ, 让-克洛德·容克 and many

<footnote n="1">¹See http://emm.newsbrief.eu/overview.html and http://emm.newsexplorer.eu/</footnote>
others are all identified as referring to the 12th President of the European Com-
mission. Such multilingual entity variants – and also disambiguated place names
– are a major ingredient for the successful identification of related news across
languages in EMM-NewsExplorer. The system was entirely developed by the Eu-
ropean Commission’s Joint Research Centre (JRC) with the purpose of providing
media monitoring functionality for the European institutions, for national au-
thorities of the European Union (EU) Member States, for international organisa-
tions such as the United Nations or the African Union, as well as for EU partner
country organisations. However, the results are also freely accessible to the wider
public through web pages and as customisable mobile applications.

Person name recognition is rather well-implemented in EMM, but the coverage
of multi-word organisation and event names has traditionally been rather poor
because they behave like free text, i.e. they may include lower-case words, prepo-
sitions, determiners, etc. Recognising such complex MWEntity types would ben-
efit from using syntax parsers, part-of-speech taggers, morphological analysers
and generic dictionaries, but EMM cannot use these because of its need to pro-
cess very large volumes of text data in near-real time and because such resources
are not easily available nor quick to develop (Steinberger et al. 2013). In response
to this shortcoming, the EMM team has engaged in less knowledge-intensive
ways of recognising multi-word entities such as those presented in this chapter.
Our general idea is to collect large numbers of known entities using patterns to
recognise acronyms and their long-forms (presented in Section 3) and then to
use these to learn light-weight recognition patterns for such complex MWEnti-
ties (Section 4). In order to validate this last step independently of the quality of
the initially automatically created resource, we did our first experiments using
MWEntity lists derived from the BabelNet resource to learn recognition patterns
in a couple of languages.

In the following sections, we will first summarise the state-of-the-art for the
recognition of acronyms and other multi-word entities, as well as for the recog-
nition of monolingual and cross-lingual entity variants (Section 2). Section 3 fo-
cuses on methods and results to recognise acronyms and their expansions (e.g.,
*EC* – *European Commission*) and to identify the variant spellings and translations.
In Section 4, we present different pattern learning methods that will help with
the recognition of multi-word entities that are not found next to their acronyms
and we will compare their relative performance. We will conclude our chapter
with a summary and with pointers to future work.
## 2 Related work

As mentioned in the introduction, multi-word entity recognition is strongly related to acronym recognition. This statement will be further developed in the following sections.

Work in the domain of abbreviation processing is abundant, but it mostly focuses on the biomedical domain and on the English language. Since the pioneer work of Taghva & Gilbreth (1999), research has developed into three main directions, namely acronym extraction and mapping to their expansions; acronym variant clustering; and, more recently, acronym disambiguation. While the extraction of acronym/expansion pairs corresponds to the primary stage of lexical unit acquisition, variant clustering resembles sense inventory organisation, which can eventually serve as reference for disambiguation. We report here on the first two aspects.

With regard to acronym extraction, existing work almost exclusively focuses on English biomedical literature (Schwartz & Hearst 2003; Okazaki & Ananiadou 2006; James et al. 2001; Wren & Garner 2002; Adar 2004; Chang et al. 2002; Nadeau & Turney 2005). Results are good and the extraction-recognition step can be considered a mature technology for this combination of domain and language. However, there is very little work on other languages: Kokkinakis & Danélls (2006) investigate the specificity of Swedish, Siklósi et al. (2014) carry out Hungarian abbreviation processing, both on medical texts. Kompara (2010) and Hahn et al. (2005) seem to be the only ones to work with acronyms *across* languages, with preliminary work on Slovene, English and Italian for the former, and acronym alignment across English, German, Portuguese and Spanish based on an interlingua for the latter.

As mentioned previously, the variety and the number of acronyms is very large so that it is useful to organise the acronym dataset on a semantic basis by grouping related variants under the same acronym identifier. The aim is thus – for each set of expansions having the same acronym – to identify those which are conceptually related. Previous related work focused mainly, anew, on biomedical literature in English. Adar (2004) experimented with k-means clustering based on an n-gram similarity measure and on a MeSH term similarity measure. Results showed that the n-gram based clustering performs actually better than that based on the MeSH resource. Okazaki et al. (2010) designed a more complex clustering approach, using a similarity metric based on a mixture of several features. Once the best feature setting has been acquired (by supervised machine learning), hierarchical clustering is used to induce the final variant grouping. The features used to build the similarity metric are themselves similarity measures, such as