Automatic Detection of Cognates Using Orthographic Alignment

String alignment is closely related to the task of sequence alignment in computational biology. Therefore, to align pairs of words we employ the Needleman-Wunsch global alignment algorithm [29], which is mainly used for aligning sequences of proteins or nucleotides. Global sequence alignment aims at determining the best alignment over the entire length of the input sequences. The algorithm uses dynamic programming and, thus, guarantees to find the optimal alignment. Its main idea is that any partial path of the alignment along the optimal path should be the optimal path leading up to that point. Therefore, the optimal path can be determined by incremental extension of the optimal subpaths [31]. For orthographic alignment, we consider words as input sequences and we use a very simple substitution matrix, which gives equal scores to all substitutions, disregarding diacritics (e.g., we ensure that e and è are matched).

Using aligned pairs of words as input, we extract features around mismatches in the alignments. There are three types of mismatches, corresponding to the following operations: insertion, deletion and substitution. For example, for the Romanian word exhaustiv and its Italian cognate pair esaustivo, the alignment is as follows:

The first mismatch (between x and s) is caused by a substitution, the second mismatch (between h and -) is caused by a deletion from source language to target language, and the third mismatch (between - and o) is caused by an insertion from source language to target language. The features we use are character $n$-grams around mismatches. We experiment with two types of features:

• i)

  $n$-grams around gaps, i.e., we account only for insertions and deletions;

• ii)

  $n$-grams around any type of mismatch, i.e., we account for all three types of mismatches.

The second alternative leads to better performance, so we account for all mismatches. As for the length of the grams, we experiment with $n\in \left\{1,2,3\right\}$. We achieve slight improvements by combining $n$-grams, i.e., for a given $n$, we use all $i$-grams, where $i\in \left\{1,\mathrm{\dots },n\right\}$. In order to provide information regarding the position of the features, we mark the beginning and the end of the word with a $ symbol. Thus, for the above-mentioned pair of cognates, (exhaustiv, esaustivo), we extract the following features when $n=2$:

For identical features we account only once. Therefore, because there is one feature (xh>s-) which occurs twice in our example, we have 8 features for the pair (exhaustiv, esaustivo).

We use Naive Bayes as a baseline and we experiment with Support Vector Machines (SVMs) to learn orthographic changes and to discriminate between pairs of cognates and non-cognates. We put our system together using the Weka workbench [15], a suite of machine learning algorithms and tools. For SVM, we use the wrapper provided by Weka for LibSVM [5]. We use the radial basis function kernel (RBF), which can handle the case when the relation between class labels and attributes is non-linear, as it maps samples non-linearly into a higher dimensional space. Given two instances $x_i$ and $x_j$, where $x_i\in {ℝ}^n$, the RBF kernel function for $x_i$ and $x_j$ is defined as follows:

where $\gamma$ is a kernel parameter.

We split the data in two subsets, for training and testing, with a 3:1 ratio, and we perform grid search and 3-fold cross validation over the training set in order to optimize hyperparameters c and $\gamma$. We search over $\left\{1,2,\mathrm{\dots },10\right\}$ for c and over $\{{10}^{-5},{10}^{-4},\mathrm{\dots },10{}^4,10{}^5\}$ for $\gamma$. The values which optimize accuracy on the training set are reported, for each pair of languages, in Table 3.

We apply our method on an automatically extracted dataset of cognates for four pairs of languages: Romanian-French, Romanian-Italian, Romanian-Spanish and Romanian-Portuguese. In order to build the dataset, we apply the methodology proposed by Ciobanu and Dinu (2014) on the DexOnline¹¹http://dexonline.ro machine-readable dictionary for Romanian. We discard pairs of words for which the forms across languages are identical (i.e., the Romanian word matrice and its Italian cognate pair matrice, having the same form), because these pairs do not provide any orthographic changes to be learned. For each pair of languages we determine a number of non-cognate pairs equal to the number of cognate pairs. Finally, we obtain 445 pairs of cognates for Romanian-French²²The number of pairs of cognates is much lower for French than for the other languages because there are numerous Romanian words which have French etymology and, in this paper, we do not consider these words to be cognate candidates., 3,477 for Romanian-Italian, 5,113 for Romanian-Spanish and 7,858 for Romanian-Portuguese. Because we need sets of approximately equal size for comparison across languages, we keep 400 pairs of cognates and 400 pairs of non-cognates for each pair of languages. In Tables 1 and 2 we provide, for each pair of languages, the five most relevant 2-gram orthographic changes, determined using the ${\chi }^2$ distribution implemented in Weka, and the five most frequent 2-gram orthographic changes in the cognate pairs from our dataset³³For brevity, we use in the tables the ISO 639-1 codes for language abbreviation. We denote pairs of languages by the target language, given the fact that Romanian is always the source language in our experiments.. None of the top ranked orthographic cues occurs at the beginning of the word, while many of them occur at the end of the word. The most frequent operation in Tables 1 and 2 is substitution.

We propose a method for automatic detection of cognate pairs using orthographic alignment. We experiment with two machine-learning approaches: Naive Bayes and SVM. In Table 3 we report the results of our research. We report the $n$-gram values for which the best results are obtained and the hyperparameters for SVM, c and $\gamma$. The best results are obtained for French and Spanish, while the lowest accuracy is obtained for Portuguese. The SVM produces better results for all languages except Portuguese, where the accuracy is equal. For Portuguese, both Naive Bayes and SVM misclassify more non-cognates as cognates than viceversa. A possible explanation might be the occurrence, in the dataset, of more remotely related words, which are not labeled as cognates. We plan to investigate this assumption and to apply the proposed method on other datasets in our future work.

We investigate the performance of the method we propose in comparison to previous approaches for automatic detection of cognate pairs based on orthographic similarity. We employ several orthographic metrics widely used in this research area: the edit distance [22], the longest common subsequence ratio [24] and the XDice metric [3]⁴⁴We use normalized similarity metrics. For the edit distance, we subtract the normalized value from 1 in order to obtain similarity.. In addition, we use SpSim [11], which outperformed the longest common subsequence ratio and a similarity measure based on the edit distance in previous experiments. To evaluate these metrics on our dataset, we use the same train/test sets as we did in our previous experiments and we follow the strategy described in [17]. First, we compute the pairwise distances between pairs of words for each orthographic metric individually, as a single feature⁵⁵SpSim cannot be computed directly, as the other metrics, so we introduce an additional step in which we use 1/3 of the training set (only cognates are needed) to learn orthographic changes. In order to maintain a stratified dataset, we discard an equal number of non-cognates in the training set and then we compute the distances for the rest of the training set and for the test set. We use the remaining of the initial training set for the next step of the procedure.. In order to detect the best threshold for discriminating between cognates and non-cognates, we run a decision stump classifier (provided by Weka) on the training set for each pair of languages and for each metric. A decision stump is a decision tree classifier with only one internal node and two leaves corresponding to our two class labels. Using the best threshold value selected for each metric and pair of languages, we further classify the pairs of words in our test sets as cognates or non-cognates. In Table 4 we report the results for each approach. Our method performs better than the orthographic metrics considered as individual features. Out of the four similarity metrics, SpSim obtains, overall, the best performance. These results support the relevance of accounting for orthographic cues in cognate identification.