言語処理学会 第25回年次大会 発表論文集 (2019年3月)

Checking the validity of word forms generated to fill empty cells
in analogical grids
Rashel Fam, Pengbo Liu and Yves Lepage
早稲田大学大学院情報生産システム研究科
fam.rashel@fuji.waseda.jp, liupengbo@fuji.waseda.jp, yves.lepage@waseda.jp

Abstract
Analogical grids are constructed from a set of words contained in a text. They tend to look like paradigm tables.
Obviously, not all word forms in a language are foundin a given text or corpus. This leaves empty cells insideanalogical grids. Analogy is a possible way to fill in these
empty cells. However, there is an issue of creating invalid
word forms by analogy. This paper proposes a method toassess the validity of newly generated word forms in such
empty cells. Several features are extracted from analogical grids, empty cell, and the word form itself to classify whether newly generated word form is valid or not.
We carry experiments in different languages with different morphological richness. Experimental results showsthat our model is able to achieve very high accuracies on
invalid samples. It also delivers satisfying performanceon valid samples.

1Introduction

Paradigm tables organise word forms and their lemmas
according to their morpho-syntactic description. They areusually complete. The task in the SIGMORPHON campaigns [3, 4] consists in guessing a word form from alemma and its morpho-syntactic description.

This paper explores the use of various features, to automatically assess the validity of newly generated wordforms. The performance is analysed for languages
with different richness in morphology: from English toFinnish through German.

2

Filling empty cells in analogicalgrids

2.1

Analogical grids

Analogical grids are matrices of strings where any four
strings from any two columns and two rows make a proportional analogy. A proportional analogy is a relation
between four terms, usually noted as A : B :: C : D, whichstates that A is to B as C is to D. Analogical grids can beconstructed by merging correlated analogical clusters [6].
Figure 1 shows an example of an analogical grid in English.
The size of an analogical grid is simply its total number of cells. As can be seen, there may be some empty
cells. These empty cells represent word forms that do
not appear in the corpus used to construct the analogicalgrid. We define the saturation of an analogical grid as thenumber non-empty cells over the total number of cells.
Saturation =play : playing : plays : played
walk : walking : walks : walked
talk :: talks :fill : filling :: filled

2.2

Figure 1: An analogical grid in English
Analogical grids have been proposed [6] to automatically organise the lexicon of a corpus without the help ofmorpho-syntactic description. Empty cells may appear
in such analogical grids. Filling empty cells in analogical grids may lead to correct or erroneous forms. On
sentences, [11] explored the way of improving the average grammaticality of sentences produced in similar
analogical grids by densifying the grids themselves. Onwords, [7] assessed by hand the validity of newly generated words in one language, Indonesian.

Number of non-empty cells
× 100% (1)Total number of cells

Filling empty cells by solving analogicalequations

Empty cells can be filled with word forms generated bysolving analogical equations [12]. These word forms are
unseen words [5, 9, 10, 13]. In this paper, we only consider solving analogical equation on the level of form, noton semantic level. For instance, the word form talked canbe generated by solving the following analogical equation.
walk : walked :: talk : x⇒ x = talked

Each empty cell may be filled in by several word forms
using different analogical equations made out of different
word forms from the analogical grid. Let us consider an― 530 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

analogical grid G with size M × N. We fill an empty cellWyx as follows.
W00 :W01 : · · · :W0m
W10 :W11 : · · · :W1m.. ..
.
. .
W x ..

Table 1: Distribution of n-grams in training data of language models

W ji :Wyi ::W jx : xen(b)dey

Wn0 :Wn1 : · · · :Wnm(a)fiFigure 2: A grid (a) and the analogical equation used tofill in cell Wyx (b)Level ofgranularity
charactermorphemecharactermorphemecharactermorpheme

1-grams

2-grams

3-grams

140
6,243
145
5,593
139
7,061

1,946
63,672
2,031
109,234
1,954
182,096

13,529118,699
16,660262,717
14,638
470,508– Saturation: calculated using Formula 1– Size: total number of cells in an analogical grid3

Validity of word forms

3.1

Assessing newly generated word forms• Features extracted from the position of the empty
cell:– Number of unique possible word forms(type): number of all possible word form generated for this cell

When solving analogical equations on the level of form,
we may create erroneous word forms.
(en)boy : boys :: child : x– Number of possible word forms (token):same as previous feature but in terms of tokens⇒ x = childs

Obviously, childs is not a correct word form in English.
Children is. The rule of form transformation for one word
may not be appropriate for all word forms. This situation
not only exists in English, in any language. Here are also
examples in Japanese and Chinese.
(ja)
(zh)

政治 : 政治家 :: 数学 : x指挥 : 指挥家 :: 调音 : x• Features extracted from the word form itself:⇒ x = 数学家
⇒ x = 调音家The correct word form for mathematician in Japanese is’数学者’, not ’数学家’, and the correct form for tuner in
Chinese is ’调音师’, not ’调音家’.
Traditional methods assess the validity of word forms
using dictionaries. However, it may be inadequate for
newly generated word forms. In particular, dictionaries
usually mention lemma as their entries and do not list up
all possible word forms for an entry. Because of that, wepropose a method to assess the validity of newly generated word forms from analogical grids. We consider assessing the problem as a classification task. We use SVM
to perform a binary classification on word forms: valid orinvalid. In comparison to traditional methods, we use features extracted from analogical grids and the word forms
themselves instead of consulting to dictionaries.

3.2– Percentage of None: percentage of getting
None (no solution) when solving analogicalequations in this cell– Frequency in empty cell: how many times theword form is generated as solution for a particular cell– Percentage of frequency: same as previous
feature but in percentage– Char-LM: score of character-based language
model– Morph-LM: score of morpheme-based language model
These language models are trained using kenlm [8] forunigram, bigram and trigram. To get the morpheme, weuse polyglot [14]. To avoid the influence of the intersection of data set as much as possible, we train the models
on parts of the data set which is not used to construct theanalogical grid. Table 1 shows the distribution of n-gramsin the data used to train language models.

Features used

We extracted several features for our task. These features
can be categorised into three groups based on where they
are extracted from: the analogical grid which the wordform belongs to, the position of the empty cell, and theword form itself.
• Features extracted from the analogical grid:4

Experiment results and analysis

4.1

Experiment protocol

We carry our experiments with analogical grids produced
from the first thousand corresponding lines of the Europarl corpus version 3 in English (en), German (de),― 531 ―

Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

Table 4: Classification accuracy of newly generated wordforms on invalid (×) and valid (X) samples

Table 2: Statistics on generated word forms

endefi

Saturation (%)
21050
2
1050
2
1050

Time (s)
92
1
1
178
1
1149
33t

# of empty cells
67,0094,869
1,231
94,654
4,767
999
96,042
12,8322,900

Filled cell (%)
1027
36
1131
42
7
21
28

Saturation
Char-LM
Morph-LM
Proposalendefi

Precision

RecallF-score1050
9010509010509017.31
15.9414.47
23.22
23.83
21.40
16.09
22.11
14.18

5.87
4.73
3.37
9.25
8.11
6.12
3.87
6.83
3.03

8.77
7.29
5.45
13.23
12.08
9.47
6.24
10.39
4.96

Finnish (fi). We filter the analogical grids using a saturation threshold and randomly choose cells as pseudoempty cells (see Section 4.2). For a pseudo-empty cell,
we generate word forms by solving all possible analogical equations, as mentioned in Section 2.2. For the classification tool, we use libsvm [1] with fselect [2] to optimize the selection of features listed in Section 3.2.

4.2

Filling empty cells

Table 2 shows the results of generating word forms fromreal empty cells in analogical grids for all the three languages. Only around 10 % of the empty cells can be filled
by solving analogical equations. For computation time
reasons, we retain analogical grids above a certain saturation threshold in order to avoid analogical grids with very
low saturation. Analogical grids with very low saturation
are obviously less reliable.
In contrast to Table 2, Table 3 shows the results of filling pseudo-empty cells. We randomly choose 10 % offilled cells in analogical grids. We fill back these cells
and verify whether the generated word forms are equal tothe actual word forms. From these results, no significant
difference between morphologically poor languages andmorphologically rich languages is observed.

4.3

Validity of generated word forms

Table 4 shows the accuracy of classification of newly generated word forms. Because the number of valid and in-de×X
100.000.00
95.60 30.12
98.80 75.90
99.20 73.49

fi×
100.00
99.05
99.43
99.43

X0.00
9.18
84.69
83.67

Table 5: F-score of features used in classification

Table 3: Results of filling back randomly deleted cells in
analogical grids
Saturation (%)

en×X
100 .00
0.00
98.98 21.43
99.32 80.36
99.66 80.36

Featuresendefi

Saturation
Size
Type
Token
None
Frequency% of frequency
Char-LM
Morph-LM

0.000207
0.000785
0.016500
0.000650
0.001904
0.121445
0.040672
0.216378
0.216614

0.000092
0.002371
0.0201290.000671
0.000259
0.093534
0.068653
0.141687
0.181490

0.000135
0.000238
0.002405
0.000001
0.004466
0.159033
0.008720
0.024339
0.150655

valid word forms in the data set are unbalanced, the tableshows the accuracy for both valid and invalid samples.
We used saturation and both scores of language model(character-based and morpheme-based) only as features
to build baseline systems.
We observe that the saturation baseline system is unable to assess valid samples. The character-based language model performs poorly on valid samples in comparison to the morpheme-based language model, whichshows high accuracy on both valid and invalid samples.
Our proposal performs best in English for both valid andinvalid samples. It also achieves the best performance forinvalid samples in German and Finnish and comparably
well on valid samples .
Table 5 shows the individual F-score [2] of each feature
we used in the experiments. Given training vectors xk , k =1, ..., m, the number of positive and negative instances aren+ and n− respectively, the individual F-score of the ith
feature is defined as:
F(i) ≡1n+ −1(x¯i (+) − x¯i )2 + (x¯i (+) − x¯i )2n−(+)(−)∑ (xk,i − x¯i (+) )2 + n−1−1 ∑ (xk,i − x¯i (−) )2
k=1
k=1
n+(2)

where x̄i , x̄i (+) , x̄i (−) are the average of the ith feature of
the whole, positive, and negative data sets, respectively,(+)
xk,i is the ith feature of the kth positive instance, and(−)

xk,i is the ith feature of the kth negative instance. The
numerator indicates the discrimination between the positive and negative sets, and the denominator indicates theone within each of the two sets. The higher the individual
F-score, the more discriminative the feature.

― 532 ―

Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

4.4Analysis on the features used

The language models, both character-based andmorpheme-based, are discriminative features for theclassification of word forms into valid or invalid wordforms especially for morphologically rich languages
like Finnish. However, character-based language modelseems to be not very discriminative for languages use
repeated characters in word forms, as is the case ofFinnish. The word form’s frequency of being generated
in an empty cell is also a discriminative feature forclassification. The intuition is that a frequently produced
word form is more likely to be valid. This feature
contributes a lot in valid sample classification.
Ablation experiments were performed to confirm theresults on individual F-scores. Due to space limitation,
we cannot show detailed results. Character-based language model has a negative influence on valid samples inall three languages while the frequency of the word form
being generated has almost no influence. We also foundthat morpheme-based language model has positive influence on valid samples in German and Finnish. For features with low F-score, we observed that there is a very
limited influence, except for the size of the grid which has
a negative influence on valid samples.

5Conclusions

We proposed a method to fill in empty cells in analogical grids. Useful features are used to assess the validityof newly generated word forms. Ablation experimentsallowed us to investigate the influence of each feature.
Experimental results showed that our model is able toachieve satisfying performance even in the absence ofdictionaries. Experiments in languages with more varying morphological richness and on larger data set are necessary to get a more complete view.

References[1] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A
library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:
27:1–27:27, 2011.
[2] Yi-Wei Chen and Chih-Jen Lin. Combining svms
with various feature selection strategies. Feature extraction, pages 315–324, 2006.
[3] Ryan Cotterell, Christo Kirov, John SylakGlassman, David Yarowsky, Jason Eisner, andMans Hulden. The SIGMORPHON 2016 SharedTask—Morphological Reinflection. In Proceedingsof the 14th SIGMORPHON Workshop, pages 10–22, 2016.

[4] Ryan Cotterell, Christo Kirov, John SylakGlassman, Géraldine Walther, Ekaterina Vylomova, Patrick Xia, Manaal Faruqui, Sandra Kübler,David Yarowsky, Jason Eisner, and Mans Hulden.
CoNLL-SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection in 52 Languages.
In Proceedings of the CoNLL SIGMORPHON 2017
Shared Task, pages 1–30, Vancouver, August 2017.
[5] Etienne Denoual. Analogical translation of unknown words in a statistical machine translation
framework. In Proceedings of Machine Translation
Summit XI, Copenhagen, September 2007.
[6] Rashel Fam and Yves Lepage. Morphological predictability of unseen words using computationalanalogy. In Proceedings of ICCBR-CA-16, pages
51–60, Atlanta, Georgia, 2016.
[7] Rashel Fam, Yves Lepage, Susanti Gojali, and Ayu
Purwarianti. A study of explaining unseen words inIndonesian using analogical clusters. In Proceedings of ICCA-17, pages 416–421, Yangon, Myanmar, February 2017.
[8] Kenneth Heafield, Ivan Pouzyrevsky, Jonathan H.
Clark, and Philipp Koehn. Scalable modified
Kneser-Ney language model estimation. In Proceedings of the 51st ACL, Sofia, Bulgaria, 8 2013.
[9] Philippe Langlais and Alexandre Patry. Translating
unknown words by analogical learning. In Proceedings of the 2007 EMNLP-CoNLL, pages 877–886,2007.
[10] Philippe Langlais, François Yvon, and Pierre
Zweigenbaum. Analogical translation of medicalwords in different languages. In A. Ranta andN. Nordström, editors, Gotal’08, volume 5221 ofLecture Notes in Artificial Intelligence, pages 284–295, Berlin, Heidelberg, 2008. Springer Verlag.
[11] Yves Lepage and Guilhem Peralta. Using paradigm
tables to generate new utterances similar to thoseexisting in linguistic resources. In Proceedings ofLREC 2004, volume 1, pages 243–246, Lisbon,May 2004.
[12] Rafik Rhouma and Phillippe Langlais. Fourteenlight tasks for comparing analogical and phrasebased machine translation. In Proceedings of COLING 2014, pages 444–454, Dublin, August 2014.
[13] Pavol Tekauer. Meaning Predictability in Word Formation: Novel, Context-free Naming Units. John
Benjamins Publishing, 2005.
[14] Sami Virpioja, Peter Smit, Stig-Arne Grönroos, andMikko Kurimo. Morfessor 2.0: Python implementation and extensions for morfessor baseline. In
Aalto University publication series, 2013.

― 533 ―

Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.