1.1 Related Work

A widespread type of multiword recognition is Named Entity (NE) Recognition (NER). NEs are phrases that represent entities belonging to predefined categories: people, geographical objects, dates etc. NER often makes use statistical methods e.g. maximum entropy model (Tjong Kim Sang and De Meulder 2003) or HMMs that can be combined with predefined syntactic and semantic rules as well as gazetteers, e.g. Zhou and Su (2002) for English, Piskorski et al. (2004) for Polish. Wikipedia has also been used as a source for NER. One could use links and definitions (Nothman et al. 2009) or categories and interwiki links (Richman and Schone 2008) as the training data. Although these attempts often reached F1 (F-measure) of 70–90% on various corpora, they were limited to carefully selected NE categories (usually the ones giving best results) and used manual rules or gazetteers. As our goal is to detect all nominal MWEs without any rules or limits, we must look for a more general approach.

For some languages, e.g. French, MWEs are included in dictionaries and corpora (Constant et al. 2012), what makes it possible to recognise them with F1 over 70%. For other languages, one could use association measures such as Mutual Information (MI), χ ² or Permutation Entropy (Zhang et al. 2006). Ramisch et al. (2008) evaluated these methods on simple structures (e.g. adjective-noun), but although they used language-dependent information, precision remained low. Attia et al. (2010) used Wikipedia to extract nominal semantic non-decomposable MWEs relying on Crossligual Correspondence Asymmetries. The extraction results were promising with F1 over 60%, but there was no recognition test on a corpus. Finally, Farahmand et al. (2014) used a manually tagged sample of 10K negative and positive English MWE examples to train an SVM classifier. The results were very positive (89% F1) but the test was performed only on the predefined examples. Our approach differs from the previous attempts as no MWE resources are used, inflection information is extracted, we do not limit the nominal MWEs in any way and we test various algorithms by tagging a corpus sample.

1.2 Anatomy of Polish Nominal MWEs

A multiword expression consists of two or more tokens: words, numbers or punctuation marks. A token that is a Polish word can be either fixed or inflectable. Inflectable words form the core of the MWE. They are mostly nouns and adjectives, but can also be numerals and participles. In the base form, all inflectable tokens must occur in nominative case. The number is usually singular, but there are also some pluralia tantum – all inflectable tokens must be plural for them. The inflectable tokens need not have the same gender, e.g. “kobieta kot” (catwoman).

Example: “Związek Lekkoatletyczny Krajów Bałkańskich” (Athletic Association of Balkan Countries). This expression begins with an inflectable non-animate male noun “związek” followed by an inflectable non-animate male nominative adjective “lekkoatletyczny”, followed by two fixed words: a noun and an adjective, both in genitive case. The instrumental case of this expression would be “Związkiem Lekkoatletycznym Krajów Bałkańskich” – inflectable tokens change their form accordingly. We consider it illegal to change the gender of any word or to modify their order. We use SFJP for word recognition.

2.1 Extraction Using the Wikipedia as a Dictionary

The simplest way to use the Wikipedia for MWE recognition is to treat it as a dictionary. We filtered out headwords with only one token as well as the ones for which we could not extract semantic labels (Chrząszcz 2012). The remaining headwords were used to create patterns that consist of one entry for each token. For words that can be inflectable, the pattern contains the word ID (from SFJP) and the grammatical categories⁴⁹. For fixed tokens (punctuation, words not in SFJP, prepositions, verbs etc. as well as words in non-nominative cases) the pattern contains just the token itself.

Example: For the headword “Związek Lekkoatletyczny Krajów Bałkańskich” the pattern is shown below in a simplified form. ’?’ means maybe inflectable. It is not possible to tell if “związek” should be capitalised because all Wikipedia headwords are capitalised.

2.2 Extraction Using Syntactic Patterns

The performance of DM is limited to the headwords of Wikipedia, so that method is incapable of recognising any unknown words. One can observe that there are groups of MWEs which share similar syntactic structure, e.g. “tlenek węgla” (carbon dioxide) and “chlorek sodu” (sodium chloride) both contain one inflectable male noun and one fixed male noun in genitive case. What is more, they both often appear in the text in similar context – e.g. in genitive case after a noun (“roztwór chlorku sodu” – a solution of sodium chloride, “reakcja tlenku węgla” – a reaction of carbon dioxide) or after the preposition “z” (with) in instrumental case (“reakcja . . . z chlorkiem sodu” – a reaction of . . . with sodium chloride). We decided to automatically create syntactic patterns that would express these regularities and recognise them in text using an automaton similar to the one used for DM. The matching algorithm is called Syntactic pattern Matching (SM). The patterns should not be created by hand – otherwise they would be limited to the structures known to their author. We tested several possible pattern structures and chose the one presented below. For each token of the MWE the pattern contains one entry:

• – For inflectable words, it begins with an asterisk (*) and contains the POS and (when possible) gender, number and case of the base form. Each of these features can be ambiguous.
• – For prepositions and some punctuation marks, the token itself is the pattern.
• – For fixed words that are in SFJP, it contains the POS and (when possible) gender and case. Each of these features can be ambiguous.
• – For other tokens it contains the category of the token (word, number, punctuation, other).

Example. The pattern for “czarna dziura” (black hole) is:

To include the information about the context, we decided that each pattern may be connected to one or more context patterns that have a similar structure to the core pattern (of course context tokens are not inflectable). The context covers one word before and one after the MWE. For example, if “czarna dziura” occurs in the expression: “(...) masywnej czarnej dziury.”, the context pattern will be:

2.3 Compound Methods

In an attempt to improve recognition performance, one can combine the two methods described above. The most important possibilities are listed below. Some of them are using Wikipedia Corpus (WC) that we created from the whole Wikipedia text. We also tried an iterative approach, but it did not provide significant improvement.

DM for words with patterns (pDM) Like DM, but the input headwords are limited to the ones for which syntactic patterns were created. This allows identifying inflectable tokens and lowercase first tokens. The matches are scored according to the number of occurrences of the pattern for the given word. The main drawback is that the number of words is reduced.

DM for SM results (SM-DM) Like pDM, but uses a second dictionary, created from the results of SM on WC. To obtain this dictionary, SM results are grouped by lemma (they also need some disambiguation and conflict resolution). A concept of word score is introduced – it is the sum of all scores of the contributing matches. SM-DM provides scores for results – they are pDM scores from the first dictionary and word scores from the second one. This method significantly increases recall at the cost of precision.

SM for SM results (SM-SM) Like SM, but uses a second set of patterns. It is created from the results of SM on WC. A dictionary is constructed (like for SM-DM) and the syntactic patterns are created from that dictionary. The goal of the first SM phase is to find more words that can be used to create patterns.

SM for pDM results (pDM-SM) Like SM-SM, but the dictionary is created using pDM, not SM. The pDM phase aims at providing additional context patterns for SM.

SM for DM results (DM-SM) This method is an attempt to create the syntactic patterns using the whole Wikipedia – a dictionary is created from the results of DM on WC and it is used to create the patterns for SM. The main drawback is that a lot of inflection ambiguities remain from the DM phase.

3.1 Test Results

Table 2 shows results optimized for best F1 score of the structural test. Basic dictionary algorithms have high precision but low recall, because Wikipedia does not contain all possible MWEs. DM has poor syntactic test results because the inflection patterns are unknown. SM0 is SM without the pattern contexts. SM preforms a bit better because of the contexts, but it is limited by sparse link connections in Wikipedia. The only compound method that brings significant improvement is SM-DM. Fig. 1 (left) presents precision-recall graphs for the best performing methods.

All the errors for the best performing method, SM-DM, were analysed one by one. It turned out that in many cases the identified phrases are not completely wrong. Such problematic cases are:

Tab. 2: Results of the test on a sample of 100 tagged PAP press releases.

Fig. 1: Left: precision-recall graphs for the structural test. Right: Quality of the dictionary created by the SM phase of SM-DM as a function of changing dictionary size after applying different word score thresholds. From top to bottom: % of true MWEs in the dictionary created by the SM phase, % of true MWEs with correctly identified base forms, precision, F1 and recall of SM-DM.

• – Overlapping expressions difficult to choose from (even for a human): “Piłkars-ka reprezentacja Brazylii” contains two MWEs: a term “reprezentacja piłkars-ka” with altered token order (a football team) and a named entity “reprezentacja Brazylii” (Brazilian team).
• – Unusually long names, spelling and structural errors: “Doroty Kędzierzwskiej” (misspelled surname), “Polska Fundacja Pomocy humanitarnej ‘Res Humanae’” (unusual structure and an accidental lowercase letter).
• – Phrases that are not MWEs in the particular (semantic) context: “osoba paląca sporadycznie” contains the term “osoba paląca” (a smoker) while it means a person smoking sporadically.
• – For the inflection errors: one of the words is not in SFJP (usually a surname): “Janusz Steinhoff”, “Władysław Bartoszewski”.

The SM phase of SM-DM produces a dictionary of 4.45 million words that can be filtered by score to achieve either high precision or recall. The threshold of 150 yielded best results (65.5% F1 for SM-DM), so we analysed the quality of the dictionary for a random sample of 1000 entries above that score. About 79% of the resulting 1.05 million words were correct MWEs and further 6% were MWEs, but had wrong base forms. This quality can be further increased at the cost of dictionary size and SM-DM recall (fig. 1, right). Although it is difficult to estimate the target size of an MWE lexicon as it is unclear how large human lexicons are (Church 2013), the results make us consider SM a good method for building MWE lexicons.

3.2 Future Work

There seems to be some significant room for further improvement, especially in the SM algorithm. The first step would be to eliminate the errors that are results of words missing from SFJP either by adding another dictionary (e.g. Morfologik) or by filling missing people (sur)names directly in SFJP. We also remind that one of our assumptions was not to use any user-defined rules. However, there were many false positives in the dictionary that could be eliminated by manual patterns, e.g. “wrzesień 2011” (September 2011), “część Sztokholmu” (a part of Stockholm ), “pobliże Jerozolimy” (vicinity of Jerusalem). This could improve the dictionary quality and increase the precision of SM-DM accordingly. We could also use other Polish corpora instead of the Wikipedia content. The tests could also be improved to allow overlapping words (they are not necessarily errors). After improving the algorithms, we plan to incorporate the resulting MWEs into SFJP and transfom SM-DM into an integral part of this dictionary.