We show how to answer analogy questions A : B :: C : D of unknown D between word forms, by essentially relying on the basic arithmetic equality D[iB iA + iC ] = B[iB] A[iA] + C[iC ] on characters and positions at the same time. We decompose the problem into two steps: speci cation and decoding. We examine several techniques to implement each of these two steps. We perform experiments on a set of positive and negative examples and assess the accuracy of combinations of techniques. We then evaluate the performance of the best combination of techniques on a large set of more than 40 million analogy questions from the training data of a shared task in morphology. We obtain the correct answer in 94 % of the cases.
In this paper, we address the problem of answering analogy questions of the type A : B :: C : D between word forms where the unknown is D. Our proposal consists in relying essentially on the intuitive basic arithmetic equality D = B A + C: We propose to write this arithmetic equality using characters and positions at the same time:
D[iB iA + iC ] = B[iB]
A[iA] + C[iC ]
(1)
The use of this arithmetic equality is directly inspired by the famous equality
between vectors proposed in [
Copyright © 2017 for this paper by its authors. Copying permitted for private and academic purpose. In Proceedings of the ICCBR 2017 Workshops. Trondheim, Norway
This paper gives empirical support for the use of Equality (1) to answer analogy questions (which only involve commutation1) between word forms (not meaning). For relevance to morphology, no knowledge other than equality of characters is used, i.e., order of letters in an alphabet, or the like, is not used.
The rest of the paper is structured as follows. Section 2 shows how the answer to an analogy question can be speci ed by a character{position matrix computed using Equality (1). Speci cation re nements are introduced to solve problematic cases. Section 2 shows that decoding the answer from the character{position matrix can be viewed as an assignment problem and thus solved using a standard algorithm. Section 4 summarises the two previous sections by giving an algorithm for the proposed method. This proposed method is validated by two series of experiments in Section 5. 2 2.1
From previous research [
jAj + jCj
jDjc = jBjc
jAjc + jCjc; 8c
where jXj stands for the length of string X and jXjc for the number of
occurrences of character c in string X. The above equations are yet another instance
of the general arithmetic equality D = B A + C. In addition, some work [
To summarise the previous remarks, Proposition (6), which embeds Equality (1), can be laid as a hypothesis to be tested. Importantly, it only makes sense if either A[iA] = B[iB] or A[iA] = C[iC ] holds, i.e., if either (iA; iB) or (iA; iC ) are match points in the matrices representing A : B and A : C (see Figure 1). Enforcing Proposition (6) allows to specify the solution of an analogy question as illustrated in Figure 1. For each index in the string D, all possible combinations of indices in A, B and C corresponding to match points in matrices A : B and A : C are examined and the number of instances of Equality (1) for that index in D is memorised in matrices B : D and C : D. By adding up these values for each character that we know will appear in D, and for each index in D, a character{ position matrix can be built, from which the answer can ultimately be decoded. b a Fig. 1. Speci cation of the answer of the analogy question ab : ac :: db : x using character{position arithmetic. The characters in the answer and their number of occurrences are known: f c : 1; d : 1g. The black squares ( ) in the upper part on the left visualise the match points in the matrices A : B and A : C. The lower part gives the number of instances of Equality (1) in each cell of matrices B : D and C : D using the match points and character{position arithmetic. In the middle, the character{position matrix summarises the evidence for each character and position (. stands for zero). This character{position matrix can be decoded into the answer dc on the right. 2.4
We now turn to a rst problematic case where Proposition (6) is not veri ed, although it should be: work : sing :: you work : you sing. In this case, no triple of indices in A, B and C can be found for the rst position in D corresponding to the character y. The character y in D can only come from the same character in C in the rst position, as it does not appear in B. However, no character in A is equal to any character in B, so that there is no match point. So Proposition (6) does not hold.
Now, Proposition (6) holds for `worka : `singa :: `you worka : `you singa
where beginning and end markers are added in the previous example. In that
case, for position iD = 1 in D corresponding to character y, the triple of indices
(iA = 0; iB = 0; iC = 1) in A, B and C is such that: D[1 = 0 0 + 1] = C[
We turn to a second problematic case for Proposition (6). Taking all possible
match points into account may give too much weight for some of them, leading
to wrong answers. This is the case for leaf : leaves :: wolf : D. Taking into
account all possible match points in the matrices A : B and A : C leads to 10
instances of Equation (1) voting in favour of D[
The work in [
jXj + s(X; Y )
iY
iX
jY j
s(X; Y )
(7)
On the previous example, restricting to match points inside diagonal bands
delimited by Inequality (7) in all matrices yields more instances of Equality (1)
favouring D[
We turn to a third and last problematic case for Proposition (6). For the analogy
question in German setzen : setzte :: lachen : D, the character{position matrix
built as described above somehow hesitates for the but last position between t
and e: 2 instances of Equality (1) support D[
The situation is similar to the one encountered in statistical machine
translation where word-to-word correspondence probabilities should be re-estimated
from the mere evidence that they appear in corresponding sentences. The answer
consists in using the expectation{maximisation (EM) algorithm to estimate a
probability distribution that will maximise the entropy over all possible
word-toword correspondences. The problem here is similar. Words in the source and
target languages in machine translation correspond to character and positions in the
character{position matrix. When applying the EM algorithm to the character{
position matrix on the previous example, the probabilities for the previous
characters and positions are re-estimated as follows: p(D[
In the previous section, we showed how a character{position matrix can be built
which assigns a probability to each character and position in the answer D of
an analogy question A : B :: C : D. The nal problem is thus an optimal
assignment problem where each position should receive a character and each
character should go to a position in D without con ict. This problem can be
solved by the Hungarian method, or Kuhn's algorithm [
It has also been shown that the Hungarian method is in fact the limit of
an entropy maximisation problem [
This strategy is more prone to fail than the Hungarian method, and should thus be considered as a loose baseline. 3.2
There may be no answer, one answer or several answers to an analogy question. For instance, the analogy question abcabc : gh :: mnkl : D has no solution; the analogy question easy : uneasy :: known : D has only one possible answer: D = unknown; and the analogy question aa : ab :: aaa : x has two possible answers only, aab or aba, if considered as an analogy of commutation (see Footnote 1).
From the solution delivered by the Hungarian method, it is possible to look in the character-position matrix and enumerate all other solutions of same cost by performing all possible exchanges between characters and positions. 4 4.1
Algorithm 1 Solving an analogy question A : B :: C : x: def Solve(A, B, C): # 1. Specify the answer by a character-position matrix, M . ComputeKnownFeatures(A, B, C) M [iD][cD] = 0 for all cD 2 D and iD 2 f1; : : : ; jDjg for each (iA; iB) / InsideDiagonal(iA; iB) and A[iA] == B[iB]: for each (iC, iD = iB iA + iC) / InsideAllDiagonals(iA, iB, iC, iD):
M [iD][ C[iC] ] += 1
Do same thing as above by exchanging B and C. # ...
M = ExpectationMaximisation(M ) # 2. Decode the character-position matrix. list of pairs (iD; cD) = HungarianMethod(M ) return EnumerateAllSolutions(M, list of pairs (iD; cD))) def ComputeKnownFeatures(A, B, C): s(A; B); s(A; C) = similarity(A; B), similarity(A; C) s(B; D); s(C; D) = s(A; C) jAj + jBj; s(A; B) jAj + jCj jDj = jBj jAj + jCj for each character c:
occ]_in_D[c] = occ]_in_B[c] - occ]_in_A[c] + occ]_in_C[c] def InsideDiagonal(iX , iY ): return jXj + s(X; Y ) iY iX
jY j s(X; Y ) def InsideAllDiagonals(iA, iB, iC, iD): return all(InsideDiagonal(iX ; iY ) for (X; Y ) in [(A; C), (B; D), (C; D)]) Algorithm 1 sketches the method as already illustrated in Figure 1. After computing the features of the answer, a character{position matrix is built and its cells are lled using the character-position arithmetic. The values in the character{position matrix are then re-estimated using the expectation{maximisation algorithm. Decoding is performed using the Hungarian method. This outputs one answer. An enumeration of all character{position exchanges of same cost yields all possible answers. 4.2
We give a very rough analysis of the complexity of the method. Computation of similarities or enumeration of the match points are basically square in the length of the strings, so that the most costly component in the algorithm is solving the assignment problem by the Hungarian method, known to be cubic in the size of the square matrix, i.e., cubic in the length of the solution in its best implementation. The convergence of the EM algorithm is di cult to estimate2.
It is interesting to observe that the method is linear in the size of D in the best case, i.e., when A = B. In that case, the diagonal band is reduced to the main diagonal in the matrix A : B. Consequently, the character{position matrix exhibits a degenerated form where each character in C is assigned the same position in D as in C. Such a matrix is a degenerated case for the Hungarian method, which returns a solution in one pass over the matrix. 5
To inspect the accuracy of our proposed method, we use an in-house data set of 160 examples, 113 positive examples and 47 negative examples. Most of the positive examples are from various languages: Arabic, Chinese, English, German, etc. They address complex phenomena, like parallel in xing, as in: (German) sprechen : ihr aussprachet :: nehmen : ihr ausnahmet In addition, some formal positive examples address incrementing problems: abc : abcabc :: abcabcabc : abcabcabcabc ab : aabb :: aaaaaabbbbbb : aaaaaaabbbbbbb The purpose of the negative examples is to test the ability of our method not to deliver an incorrect answer. The negative examples are of the type: ab : aabb :: aaabbb : aaabbbba where the answer proposed, aaabbbba, is incorrect; the only correct answer, when restricting to analogies of commutation, is aaaabbbb. In this case, an algorithm that would blindly output all possible combinations of four a's and four b's in any order would have the incorrect answer in its set of solutions; it would thus fail the test.
We test di erent combinations of components: for the speci cation of the answer, use of all possible match points vs. only those inside diagonal bands 2
We set the convergence threshold to the reciprocal of the number of cells in the character{position matrix, i.e., 1=jDj2. In general we observe convergence after a very small number of steps. (Sect. 2.5), and use of the EM algorithm to re-estimate values in the character{ position matrix vs. no use (Sect. 2.6); for decoding, use of the Hungarian method vs. our loose baseline (increasing entropies) (Sect. 3.1).
The results in Table 1 show that each of the components contributes to accuracy. Considering only match points inside diagonal bands allows to jump from below 66 % accuracy to almost 80 % and above. The EM algorithm may be of no utility or may add around 5 % in accuracy. As expected, the Hungarian method always beats our loose baseline by at least 5 % in accuracy. The best accuracy obtained is 91 % when decoding using the Hungarian method.
Match points inside diagonal band
No Yes
EM algorithm Decoding method Recall Precision Accuracy
No Yes No Yes
Increasing entropies Hungarian method Increasing entropies Hungarian method Increasing entropies Hungarian method Increasing entropies Hungarian method
This relatively low precision will now be nuanced by results on a much larger dataset which supposedly re ects more real analogy questions. This dataset is from Task 1 of Track 1 of SIGMORPHON 2016 Shared Task: Morphological Rein ection. We use all the o ered languages: Arabic, Finnish, Georgian, German, Hungarian, Maltese, Navajo, Russian, Spanish and Turkish.3 We extract analogy questions from such data by considering all analogies of form ltered by morphological features. For each analogy, four di erent analogy questions can be asked, each of the four terms becoming the answer.4 As an example in Spanish, the four following questions correspond to the same analogy: alterado : alterada :: adeudados : x alterada : alterado :: adeudadas : x adeudadas : adeudados :: alterada : x adeudados : adeudadas :: alterado : x ) x = adeudadas ) x = adeudados ) x = alterado ) x = alterada The number of analogy questions obtained in each language is given in Table 3. The total number over all languages exceeds 40 million analogy questions. For half of the languages, the percentage of correct answers is equal to or higher than 95 %. The total number of correct answers over all questions in each language reaches 94 %.
Number of anal- % of correct Language ogy questions answers Arabic Finnish Georgian German Hungarian Maltese Navajo Russian Spanish Turkish Total We showed how to answer analogy questions A : B :: C : D of unknown D between strings of characters, by essentially relying on an intuitive basic arithmetic equality: D[iB iA + iC ] = B[iB] A[iA] + C[iC ]: We decomposed the problem into two steps: speci cation and decoding. We performed experiments on a set 3 https://github.com/ryancotterell/sigmorphon2016/tree/master/data/. We use all the les of the type <language>-task1-train. 4 This is not the task proposed in SIGMORPHON Shared Task, which consists in a machine learning task: predicting a word form given a lemma and morphological features after having learnt from the training data. of positive and negative examples and measured the contribution of each of the components in accuracy. We further assessed the precision of the method on a very large set of more than 40 million analogy questions from the dataset of a shared task in morphology. We obtained the correct answer in 94 % of the cases.
As future direction, we want to carry on in testing the e ciency of the character{position arithmetic. For instance, it remains to inspect whether restricting further to those match points lying on edit distance traces helps or harms and whether we can dispense with the EM algorithm.