{'fraction_non_alphanumeric': 0.029974489795918366, 'fraction_numerical': 0.015533892128279884, 'mean_word_length': 4.733350744319666, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Siamese Convolutional Networks for Cognate Identification

In this paper, we present phoneme level Siamese convolutional networks for the task of pair-wise cognate identification. We represent a word as a two-dimensional matrix and employ a siamese convolutional network for learning deep representations. We present siamese architectures that jointly learn phoneme level feature representations and language relatedness from raw words for cognate identification. Compared to previous works, we train and test on larger and realistic datasets; and, show that siamese architectures consistently perform better than traditional linear classifier approach.


Introduction
Cognates are words that are known to have descended from a common ancestral language. In historical linguistics, identification of cognates is an important step for positing relationships between languages. An example of cognates are German Fuß and English foot whereas, Hindi chakra and English wheel are cognates that can be traced back to the Proto-Indo-European * k w ek w lo− and do not exhibit similarity on surface.
In NLP, automatic identification of cognates is associated with the task of determining if two words are descended from a common ancestor or not. In NLP, word similarity measures based on number of shared bi-grams, minimum-edit-distance, and length of longest common subsequence are supplied as features for a linear classifier or a sequence labeler on a set of labeled positive and negative examples; and then employ the trained classifier to classify new word pairs. The features for a classifier consist of string similarity scores (Hauer and Kondrak, 2011;Inkpen et al., 2005).
It has to be noted that the Indo-European dating studies (Bouckaert et al., 2012;Chang et al., 2015;Rama, 2016) employ human expert cognacy judgments for inferring phylogeny and internal dates of a well-studied language family. Therefore, there is a need for developing automated cognate identification methods that can be applied to those families of the world that are not as well-studied as Indo-European language family.
The supervised approaches (Kondrak, 2009;Bergsma and Kondrak, 2007) employ orthographic similarities and character alignments as features for training classifiers. In this work, we show how convolutional networks can be employed to extract phonetic features for the purpose of cognate identification. We also include a neural network approach to integrate language features for jointly training the neural networks. To the best of our knowledge, this work is the first to apply convolutional networks (CNN) for the purpose of cognate identification.
The work is organized as follows. In section 2, we define the task of cognate identification. In section 3, we motivate and describe convolutional network architectures for cognate identification. In section 4, we describe the related work for cognate identification. We present the experimental setup in section 5 and results in section 6. Finally, we present our conclusions in section 7.

Cognate detection
In this paper, we work with Swadesh lists (Swadesh, 1952)  English for three meanings "foot", "bell", and "to sew". The lexical items are transcribed in ASJP alphabet which is given in table 2. The cognate class labels, indicated in parentheses, do not carry additional information across meanings. Table 1 shows the cognate class of each lexical item. Within a meaning, if two lexical items belong to a same cognate class, then they are cognates otherwise, they are treated as non-cognates. For example, all word pairs in meaning "foot" belong to the same cognate class "B" and are cognates whereas, the word pairs for English and German are cognate in meaning class "belly" and are not cognate in the meaning class "to sew". The task at hand is to correctly identify if two words from different languages belonging to a meaning class is cognate or not.

Convolutional Networks
In this section, we briefly describe some past work that uses CNNs for NLP tasks such as text classification and part-of-speech tagging. Then, we motivate the use of CNNs for cognate identification task.
The supervised approaches to cognate identification supply string similarity or phonetic similarity scores as features which might not capture all the information in two words. Character alignments extracted from minimum-edit-distance are used to train a linear classifier; and, the alignment features are further augmented by the context to capture processes of sound correspondences between two words (Bergsma and Kondrak, 2007;Ciobanu and Dinu, 2014). In a recent paper, Ciobanu and Dinu (2014) use character alignments from word pairs (extracted from a etymological dictionary) as features to train and test SVM classifiers. This method seems to require thousands of word pairs; and, might not be practically feasible in a low-data scenario. The approach of Bergsma and Kondrak (2007) which learns the alignment weights of characters requires monolingual corpora for source and target languages which is not available for many of the world's languages.
In this context, CNNs can be an alternative way to avoid explicit feature engineering through similarity computation and can extract relevant features from a raw word pair. Also, CNNs do not require explicit character alignment since the weights for non-monotonic shared features between two words can be learned through back-propagation. Collobert et al. (2011) proposed ConvNets for NLP tasks in 2011 and have been applied for sentence classification (Kim, 2014;Johnson and Zhang, 2015;Kalchbrenner et al., 2014;, part-of-speech tagging (dos Santos and Gatti, 2014), and information retrieval (Shen et al., 2014).

CNNs in NLP
Santos and Zadrozny (2014) use character embeddings in conjunction with word embeddings to train a convolutional architecture for the classification of short texts. The authors find that their architecture performs better than the systems reported in Socher et al. (2013). In a recent work,  treat documents as a sequence of characters and transform each document into a sequence of one-hot character vectors. The authors designed and trained two nine layer convolutional networks for the purpose of text classification. The authors report competitive or state-of-the art performance on a wide range of text classification datasets.

Siamese Manhattan CNNs
Formally, we define the supervised problem setting where each training example x i consists of two words x ia , x ib and a label y i ∈ {0, 1}. Each phoneme x iap ∈ R k is a k-dimensional vector. A word is zeropadded or clipped at a pre-determined length n when necessary. A word x ia of length n is represented as: where, ⊕ is a concatenation operator. A convolution operation has a filter W ∈ R hm where h ≤ k and m < n. The window size m defines the size of the filter. The feature map C ∈ R pq where, p = k − h + 1, q = n − m + 1 is formed by convoluting the filter W with word x ia . A max-pooling operation takes as input C ∈ R pq feature map and applies the max(C s×t ) to generate a featureĈ ∈ R p/s q/t . The features generated by multiple filters are passed to a sigmoid function 1 (1+exp(−x)) that computes the probabilities for y i .
In the original siamese architecture proposed by Chopra et al. (2005), the weights are tied for each input x ia , x ib . The 2 -norm (D) between the representations R ia , R ib computed using the shared convolutional networks of x ia , x ib and the label y i is used to train a contrastive loss function y i · D + (1 − y i ) · max{0, m − D} where, m is a constant that can be tuned during training.
In this paper, we extend the siamese architecture to include an element-wise absolute difference layer which can then be stacked with multiple fully-connected layers. The final layer would be a sigmoid layer for binary classes. The idea behind this step is to push the CNNs to learn the phonological differences during training. The absolute difference (−) operation resembles 1 norm and is defined as where, M iab ∈ R r and r is the length of the representation vector at the end of convolutional layer. Hence, we call this architecture as Manhattan CNN. Parts of this architecture is shown in figure 1.

Phoneme encodings
Santos and Zadrozny (2014) train character embeddings for boosting their short text classification system based on CNNs. However, the cognate identification task typically deals with short word lists (∼ 200) and short words (∼ 5). However, many of the languages such as those studied in this paper do not have enough corpora to train character embeddings. Due to these reasons, we use 1-hot and hand-crafted phoneme encodings to train our convolutional networks.
1-hot phoneme CNN In this representation, each phoneme p is represented as 1-hot vector ∈ R |P | where, P is the set of phonemes in a language family. Each word is either zero-padded to attain a length of n or clipped if the length exceeds a fixed length. We use the phonetic alphabet developed by Brown et al. (2008) 1 -for computerized historical linguistics -in our experiments. The ASJP alphabet and its phonetic properties are given in table 2. Word delimiters are represented by 0 vectors. We refer this architecture as CharCNN.
Phonetic features CNN In this representation, we encode each phoneme p as a 1/0 vector of phonetic features. The description of phonetic properties of each phoneme is given in table 2. The features are ordered as they appear in the description of the alphabet in Brown et al. (2008). The first motivation behind this approach is to test if we can use the phonetic information (that is available with the word lists) for cognate identification. The second motivation is to test if CNNs can directly learn the patterns of sound change from underlying phonetic representations for the purpose of cognate identification. We refer this architecture as PhoneticCNN.

Language features
One major limitation of previous work in cognate identification is that the weight training of word similarity features is not performed jointly with language relatedness information. We present an architecture to learn the phonological similarity jointly with weighted language relatedness. We extend the Manhattan architecture to include language relatedness information during training. Some languages share more cognate pairs than other language pairs due to genetic relatedness. We can train the model to learn language relatedness jointly with phonological relatedness by representing the languages as 2-hot vector. Formally, two words x ia , x ib belong to different languages l a , l b ∈ language set L is represented as 2-hot vector ∈ R |L| which is concatenated with the learned representation M iab . The concatenated vector is then passed to a fully-connected layer whose output is then passed to a sigmoid layer. All our models are trained with binary cross-entropy loss function defined as −(y i · log(s i ) + (1 − y i ) · log(s i )) where s i is the score for an instance i at the final sigmoid layer. The architecture with language features and the fully connected layer is shown in figure 1.
We observe that including language relatedness (phylogeny) information seems to be quite challenging. For instance, the work of Bouchard-Côté et al. (2013) uses the inferred phylogeny of Austronesian languages (Greenhill and Gray, 2009) and do not infer the phylogeny themselves. In the case of Indo-European, Bouckaert et al. (2012) infer a Indo-European phylogeny from the cognacy information encoded for 200-word Swadesh lists and do not infer the cognacy judgments jointly with phylogeny. 2 Using the Indo-European phylogeny information given in Glottolog (Nordhoff and Hammarström, 2011) can be circular since the cognacy judgments used by Bouckaert et al. (2012) are also used by human experts to derive the phylogeny information given in Glottolog. Therefore, we include the language information that is available with the word lists and hypothesize that a fully connected neural network layer can learn the weights of the language features jointly with the phonological representations generated by siamese CNNs through back-propagation.

Related work
The past work on cognate identification is mostly based on supervised approaches such as (Hauer and Kondrak, 2011;Bergsma and Kondrak, 2007;Inkpen et al., 2005) and graphical model approaches (Bouchard-Côté et al., 2013). In a different line of work, Kondrak (2000) and List (2012) employ linguistically motivated phoneme correspondence weights for computing the similarity between word pairs. Inkpen et al. (2005) test the efficacy of different machine learning algorithms to determine if a pair of words are cognates or not. They use various orthographic similarity measures as features for the machine learning algorithms. They train and test their models on word pairs extracted from parallel texts and English-French cognate list; and find that there is no single machine learning algorithm that is good at both the datasets.
Hauer and Kondrak (2011) motivate a SVM classifier for the purpose of clustering word pairs within a meaning. They supply string similarity measures as features for their SVM classifier and then use the trained model to score the extracted word pairs from the testing part of their data. In this paper, we compare our neural network models against their classifier. Ciobanu and Dinu (2014) test if character alignments extracted from Longest Common Subsequence alignments can be employed for the purpose of pair-wise cognate detection. They train a binary SVM classifier using the multi-gram character alignments as features for four pairs of Romance languages: Romanian-French, Romanian-Italian, Romanian-Spanish, and Romanian-Portuguese. They find that the SVM classifier trained on character alignments performs better than the orthographic similarity measures such as Edit distance, Longest Common Subsequence Ratio, and number of common bigrams.
Bouchard-Côté et al. (2013) employ a graphical model to reconstruct the word forms in Proto-Austronesian using Swadesh lists. They find that the inferred proto-forms largely agree with the reconstructed proto-forms. However, their method requires cognate information and the phylogeny of the language family to be known beforehand. In this article, we also experiment with a subset of Austronesian language family.

Hyperparameters and training
The number of feature maps in a convolutional layer is fixed at 10. The architecture features a maxpooling layer that halves the output of the previous convolutional layer. We used the dropout technique with 0.5 probability (Srivastava et al., 2014) to prevent a fully-connected layer from over-fitting. A fully connected layer is trained with ReLU non-linearity (max(0, x)). The filter width m is fixed at 2 for 1-hot phoneme CNNs and 3 for phonetic feature CNNs. The filter length h is fixed as the size of |P | for 1-hot phoneme CNNs and 2 for phonetic feature CNNs. The word length parameter n is fixed at 10. We used adadelta optimizer (Zeiler, 2012) with learning rate of 1.0, ρ = 0.95, and = 10 −6 . We fixed the mini-batch size to 128 in all our experiments. Both our architectures are relatively shallow -only three layers -as compared to the text classification architecture of . We trained all our networks using Keras (Chollet, 2015) and Tensorflow (Abadi et al., 2016).

Datasets
We evaluate the performance of phoneme CNNs on three different language families: Austronesian, Indo-European, and Mayan.
Austronesian The Austronesian Basic Vocabulary Database 3 has word lists for 210 concepts in 378 languages. The database also has a cognacy judgment for each word. However, the database is not in an uniform transcription. Hence, we semi-automatically processed the words and converted a subset of 100 languages into uniform ASJP alphabet. We extracted a total of 525, 941 word pairs from the processed data of which 167, 676 are cognates.
Indo-European The second dataset comes from the Indo-European Lexical database which was originally created by Dyen et al. (1992) and curated by Michael Dunn. 4 The database is transcribed in a mix of International Phonetic Alphabet (IPA) and Romanized IPA. The database has word lists for 207 concepts in 139 languages. We extracted word lists for only those languages which are in phonemic transcription in more than 80% of the concepts. This filtering step leaves us with a total of 326, 758 word pairs for 52 languages of which 83, 403 are cognates.
Mayan The third dataset comes from the Mayan language family (Wichmann and Holman, 2013) that is spoken in Meso-America. This dataset has word lists in ASJP format for 100 concepts in 30 languages. We extracted 63, 028 word pairs from the dataset out of which 22, 756 are cognates.

Evaluation metrics
The performance of the baseline and the different CNN models is evaluated using Accuracy (ACC) and F-score. Given W word pairs, Accuracy is defined as the number of word pairs that have been assigned the correct labels (both cognate and non-cognate) divided by W . The F -score is defined as the harmonic mean of the Precision (P ) and Recall (R) ( 2P R P +R ).

Baseline
We compare the performance of CNNs against the SVM classifier system trained on the following features from Hauer and Kondrak (2011). We used a linear kernel and optimized the SVM hyperparameter (C) through ten-fold cross-validation and grid search on the training data.
• Common number of bigrams.
• Length of longest common prefix.
• Lengths of both the words.
• Absolute difference between lengths of words.

Results
For each family, we train our models on word pairs extracted from ∼ 70% of the meanings and test on the remaining meanings. The details of the training and testing datasets are given in  Table 4: Accuracies and F-scores of different CNN models against the system of Hauer and Kondrak (2011). CNNs with language features are denoted with a suffix "+ Langs.".
All the CNN models perform better than the baseline across all the language families. The Phonet-icCNNs perform better than the CharCNN only on the Indo-European language family. In the case of Austronesian language family, joint training of language features improve the performance over baseline. This is reasonable since the Austronesian language family is spread over a wide range of geographical area spreading from Madagascar to Hawaii. The joint training of language features also improves the accuracy and F-score for Mayan language family.
CharCNN performs the best on the Mayan language family. One reason for this could be that the Mayan language family is a geographically proximal family and does not exhibit great amount of phonological divergence. Moreover, the Mayan language family shows less number of average cognate classes per concept as compared to Austronesian or Indo-European (cf. table 3) which can interpreted as a measure of genetic closeness within a family. In the case of Indo-European, the phonetic CNNs trained jointly with language information perform the best.
6.1 Do CNNs work with small training sets?  note that CNNs require large amount of data for training. We test this hypothesis by training our CNNs on a smaller subset of 20 concepts. The results of our experiments are given in table 5.

Systems
Indo-European Austronesian Mayan F-score Accuracy F-score Accuracy F-score Accuracy  In the case of Indo-European and Mayan, the CNNs perform better than the baseline whereas for Austronesian the CNNs do not outperform the baseline system. The results for Indo-European and Mayan (cf. table 5) are similar to that of the results reported in table 4. That is, the CharCNN system performs the best for Mayan language family, while the PhoneticCNN system performs the best for the Indo-European language family. Surprisingly, for the Austronesian family, the baseline system performs better at F-score than the top-performing system for this language family in table 4, namely the CharCNN (with language features); the Accuracy measure of the Baseline system is also higher, but the difference is not statistically significant. The reason for this could be that there is not enough information in the 20 meanings to learn phonological similarity for 100 languages.
The results for Mayan family suggests that the CharCNN can be used with small datasets for a closely related language family. We believe that this is an important result due to the abundance of small number of language families in the world.
To support our claim, we cite family size numbers from Glottolog 5 which show that there are about 50 language families of size between 10 and 100. Due to this reason, we claim that a cognate identification system that can perform well on geographically proximal, closely related languages is useful for identifying cognates, which, in turn, can be used for inferring phylogenies of under-studied language families.

Conclusion
In this article, we proposed siamese CNNs for cognate identification and compared it against a SVM classifier trained on orthographic similarities. Our results suggest that CharCNNs and PhoneticCNNs can be used for the purpose of cognate identification. Our results on Mayan language families suggest that CNNs can be applied for NLP tasks in closely related languages or varieties. The language features improve the performance of CNNs across all the language families.
The performance of CharCNNs suggest that deep learning can be applied for small datasets (language families). Many deep learning systems reported in the NLP literature require huge amount of training data. Here, we show that handcrafted embedding and 1-hot encodings can learn useful representations from raw words for capturing phonological similarities between a word pair.
In the future, we hope to apply CNNs for more language families of the world for the purpose of cognate identification and phylogenetic inference.