We address the problem of predicting unseen words by relying on the organization of the vocabulary of a language as exhibited by paradigm tables. We present a pipeline to automatically produce paradigm tables from all the words contained in a text. We measure how many unseen words from an unseen test text can be predicted using the paradigm tables obtained from a training text. Experiments are carried out in several languages to compare the morphological richness of languages, and also the richness of the vocabulary of di↵erent authors.
) The current trend in natural language processing is to extract knowledge from a training corpus, apply this knowledge to perform some task on a test set, and measure the performance. As many techniques are generally first developed for English, they take the typographic word as their basic processing unit. For tasks such as speech recognition or machine translation, the words known by the system constitute the vocabulary of the system. Unseen words, or out-ofvocabulary (OOV) words, or new words, become a problem. Unseen words are in fact of the same kind as hapaxes. Let us recall that hapaxes in any standard English text are estimated to represent between 30 % to 50 % of the vocabulary of the text (44 % on Part A of the British National Corpus) while being of course unfrequent (less than 0.2 % of the total number of words in the same corpus).
In this paper, we address the problem of the predictability of unseen words:
given an unseen word, find all other words that may explain it. We consider
computational analogy as a possible way of explaining unseen words. For instance,
the unseen word inexhaustivity 1 may be explained by: active : inactivity ::
exhaustive : x x = inexhaustivity. In the present work, on the contrary
to, for instance, [
For that, in Sect. 2 we present a pipeline, which relies on already reported research based on computational analogy, to automatically produce paradigm tables from all the words contained in a training text. We measure how many unseen words from an unseen test text can be predicted using these paradigm tables. Again, as we rely only on a computational definition of formal analogies, we do not take meaning into account in this work. In Sect. 3, experiments are carried out in di↵ erent languages from four continents. At the same time, we compare one author against other authors reporting similar events, namely the Gospel of Luke against the three other ones. In this way, we attempt at characterizing the morphological richness of these languages as well as the richness of vocabulary of one author compared to other ones. 2
The following pipeline relies on the notion of computational analogy between
strings of symbols proposed in [
We firstly define the ratio between two words A and B as a vector of features
made of all the di↵erences in number of occurrences in the two words, for all
the characters, whatever the writing system2; plus the distance between the two
words3. See definition in (1). The notation |S|c stands for the number of
occurrences of character c in string S and d(A, B), is the edit distance between two
strings A and B. This definition of ratios captures prefixing and suxing and
more generally infixing. Infixing is mandatory for a proper treatment of semitic
languages [
A : B = 0 |A|a | B|a1 . .
.
Based on the notion of ratio, we then define an analogy, more precisely a proportional analogy of commutation between strings of symbols, as a relationship between four objects where two properties are met: (a) equality of ratios between the first and the second terms on one hand and the third and the fourth terms on the other hand, and (b) exchange of the means. The exchange of the means states that the second and the third terms can be exchanged. The notation and the definition of an analogy are given in (2) at the same time4.
A : B :: C : D ) ( ⇢ A : B = C : D
A : C = B : D
From the entire set of words contained in a text, we compute the set of analogical clusters, i.e., series of word pairs in which any two word pairs is a proportional analogy as defined in (2). Such analogical clusters are defined in (3). Notice that the order of word pairs in analogical clusters has no importance.
A1 : B1 A2 : B2 . .
.
An : Bn ) ( 8 (i, j) 2 { 1, . . . , n}2,
Ai : Bi :: Aj : Bj
To produce the set of analogical clusters, we first group pairs of words by
equal ratio in number of characters using the method proposed in [
We ensure that any two word pairs in a series of word pairs of equal ratio, say, A, B and C, D, also verifies A : C = B : D. 2.2
Individual analogical clusters already give some insight at the organization of the
lexicon. Paradigm tables [
P11 : P12 : · · · : P1m P21 : P22 : · · · : P2m
... ... ...
Pn1 : Pn2 : · · · : Pnm ) ( 8 (i, k) 2 { 1, . . . , n}2, 8 (j, l) 2 { 1, . . . , m}2, Pij : Pil :: Pkj : Pkl (4)
We create paradigm tables from analogical clusters as follows. A paradigm table is first initialized from one analogical cluster and then expanded by adding other analogical clusters to it. There are two possible ways of adding a cluster to a paradigm table. In the first case, if a column in the paradigm table shares at least three words with a column in an analogical cluster, this cluster can be added vertically to it. In the second case, an analogical cluster shares more than three words on a row of the paradigm table, so that the cluster can be transposed and inserted to the paradigm table horizontally.
Algorithm 2 sketches the necessary functions for the production of paradigm tables from analogical clusters. In these functions, the strategy is to process longer analogical clusters first because the possibility of inserting smaller new series in a paradigm table increases with the number of words it contains. To ensure that no insertion is forgotten, the list of series of word pairs of equal ratio is scanned several times. However, because clusters are added only to one paradigm table, the complexity is O(n2) in the worst case with n the number of clusters. Algorithm 1 Building a set of analogical clusters from a set of words function build clusters(set of words) tree from the set of words . Hierarchically group words by their . number of occurrences of characters. repeat top-down exploration of the tree against itself group pairs of words by equal di↵erence
of number of occurrences of characters until last character for all set of word pairs with equal number of occurrences of characters do check distance(set of word pairs) end for end function function check distance(set of word pairs (A1, B1), . . . , (An, Bn)) for all i 2 { 1, . . . , n} do
compute d(Ai, Bi) end for for all set of word pairs (Ai, Bi) with same distance do
check cluster(set of word pairs) end for end function function check cluster(set of word pairs (A1, B1), . . . , (An, Bn))
V {1, . . . , n} . Vertices of the graph. E {(i, j) 2 V 2 / Ai : Aj = Bi : Bj} . Edges of the graph. list nodes in V sorted by non-increasing number of edges not yet covered V repeat i first node in list delete i from list if i 2 not yet covered then clique { i} . Initialize clique to singleton of not yet explored vertex. clique, not yet covered expand clique(clique, list, not yet covered ) return clique . clique is an analogical cluster. end if until not yet covered = ; end function
It is worth noticing that, when creating all possible paradigm tables from a text, not all of the words will necessarily appear in a paradigm table. Reciprocally, paradigm tables extracted from texts may contain blank cells. A paradigm table which does not contain any blank cell is not productive as no new word can be entered in it. On the contrary, we will call any paradigm table which contains at least one blank cell a productive paradigm table. We will call a word that may fill a blank cell in a productive paradigm table a predictable word.
We simply define the size of a paradigm table as its number of rows multiplied by its number of columns. We measure the density of a paradigm table as the ratio of non-blank cells over the total number of cells, i.e., the size of the paradigm table. With this definition a non-productive table has a density of 100 %. Productive paradigm tables have a density less than 100 %.
In the experiments reported hereafter, we monitor the density of the paradigm tables produced by controlling the addition of analogical clusters: we add a cluster to a paradigm table only if the density of the new paradigm table after adding the cluster is above a given threshold. This is done by the condition in the function expand table in Algorithm 2.
Algorithm 2 Building a set of paradigm tables from a set of analogical clusters function build paradigm tables(set of analogical clusters, threshold ) tables ; . Set of paradigm tables, initially empty. list set of analogical clusters sorted by non-increasing order of size repeat analogical cluster first analogical cluster in list delete analogical cluster from list table analogical cluster . Make analogical cluster a paradigm table. . By construction, it has only 2 columns . and a density of 100 %. table, list expand table(table, list, threshold ) tables tables [ { table} until list is empty return tables end function
We selected several languages from four continents. We chose three languages per continent. The choice of a language over another was first driven by the availability of the texts themselves, the availability of a locale for pre-processing and the confidence that we had that segmentation into words, when needed, did not go wrong. We also tried to represent di↵erent linguistic families as much as possible. The selected languages are the following ones.
Africa: Somali (so), Swahili (sw), Xhosa (xh); America: Achuar (acu), Nahuatl (nah), Quichua (qu); Asia: Chinese (zh), Indonesian (id), Telugu (te); Europe: English (en), Finnish (fi), (Modern) Greek (el).
The texts we use in our experiments are texts available in a relatively large number of languages: they are translations of the New Testament collected by Christodoulopoulos5. We insist on using the same text in all languages so as to ensure reliable observations and comparisons across languages to a certain extent. We use Matthew’s Gospel as training data to produce paradigm tables. We use Luke as our test set, i.e., we shall extract all words from Luke which do not appear in Matthew and examine whether these words are predictable from the organization of the vocabulary obtained from Matthew.
Table 2 gives statistics on the number of words in each language. The training and the test sets are similar in subject and size. The numbers of tokens (all words) and types (di↵erent words) are slightly higher in the test set than in the training set. It is the same for the type–token ratio (with the exception of Quichua) but the same variations across languages are observed 3.2
5 http://homepages.inf.ed.ac.uk/s0787820/bible/. This corpus is a continuation
of previous e↵orts described in [
The product of the first three columns in Table 3 directly gives the number of non-blank cells in the paradigm tables, and indirectly, the number of blank cells. For instance for English, with a threshold of 50 %, we have 587 ⇥ 49.5 ⇥ (100 58.3)/100 = 12, 117 blank cells. This is the number of words which are predictable from the organization of the vocabulary given by the paradigm tables. It is of course natural that the number of unseen words which can actually find a place in the paradigm tables be lower for a higher density threshold, in absolute numbers. For instance, for English we observe a decrease from 12, 117 predictable words for a threshold of 50 % to only 115 ⇥ 12.6 ⇥ (100 91.8)/100 = 119 predictable words for a threshold of 90 %. 3.3
We now turn to the experiments in filling paradigm tables with unseen words. The results are also given in Table 3. The number of unseen words in the di↵erent languages ranges from a little bit less than 1,000 (English and Indonesian) to almost 5,000 words (Telugu). This reflects a known fact: Luke would have a richer vocabulary than the other Evangelists, and this seems to have been carried over in translation. In Table 3, these numbers are repeated for the two thresholds.
As for prediction, it is natural to expect that the number of predicted unseen words would decrease for a higher threshold of density, because the number of blank cells in the paradigm tables is smaller. Table 3 shows this phenomenon (Ratio of Unseen words): a reduction from 15 % to around 1 % of predicted unseen words is observed in average. This is the ratio of words from Luke, which were unseen in Matthew but can fill in a blank cell in some of the paradigm tables.
Xhosa Across languages, one observes variations which are not necessarily the same for the two thresholds. As one can interpret the ratio of 90 % to correspond to a safer production of new words, in a same language, the ratio (not given here) between the predicted unseen words for the two thresholds, gives the proportion of reliable words produced. This proportion is quite high for Quichua: 215/900 = 24 %, while it is quite low for English: 1/75 = 1.3 %. These figures characterize in some way the morphological richness of the languages. 4
In this paper, we presented a pipeline for the production of paradigm tables from words contained in a given text by relying on a formalization of analogy. The blank cells in the produced paradigm tables stand for potential word forms. We carried out experiments to see how many of the words used by an author can be predicted from such paradigm tables in comparison to another author. The results obtained in a variety of languages of the world, with two di↵erent thresholds for the density of the paradigm tables produced, can be used to characterize relative morphological richness of languages as well as the richness of the vocabulary of authors.