Imputing typological values via phylogenetic inference (2020)

Abstract: This paper describes a workflow to impute missing values in a typological database, a sub- set of the World Atlas of Language Structures (WALS). Using a world-wide phylogeny de- rived from lexical data, the model assumes a phylogenetic continuous time Markov chain governing the evolution of typological val- ues. Data imputation is performed via a Max- imum Likelihood estimation on the basis of this model. As back-off model for languages whose phylogenetic position is unknown, a k- nearest neighbor classification based on geo- graphic distance is performed.

## introduction precise knowledge of the typological diversity of natural languages is essential for several scientific disciplines. it provides clues about cognitive biases in language learning and processing, intrinsic tendencies in language change, a window into deep time regarding prehistoric population spread and population contact, as well as scaffolds for setting up nlp infrastructure for understudied languages. while a growing body of digital data collections has become available in this regard (e.g., @xcite , these resources are sparse and skewed both with respect to the languages and the features covered. given that obtaining high-quality typological qualification for underdocumented languages is a highly demanding task, this situation is likely to persist. it is therefore worthwhile to leverage statistical and machine learning methods to impute missing typological feature values from existing resources. precisely this is the topic of the 2020 shared task foot_0 of the acl special interest group on typology (sigtyp). the organizers made three subset of the wals data @xcite available, see ## general approach the present approach is based on two simplifying assumptions: both assumptions are known to be wrong. the first one is falsified by the manifold findings regarding implicative universals (established in @xcite and amply confirmed in subsequent typological research). the second assumption ignores the impact of language contact on typological properties. research in areal linguistics has established beyond doubt that typological properties can be transmitted horizontally though (see, e.g., @xcite for an overview). it seems worthwhile, however, to test how well a model based on these idealizations fares with regard to typological predictions. this establishes a baseline to be improved upon in future research. the approach pursued here assumes that the phylogeny, i.e. the family tree representing their genealogical interrelatedness, including branch lengths reflecting the time between divergence events, of the languages under consideration is known. i used the techniques described in @xcite to infer such a phylogeny from lexical data (see next section for details). following much work in computational phylogenetics (see, e.g., @xcite if a language splits into two daughter lineages, both daughter branches continue to evolve according to two independent copies of the mother language's ctmc. this is illustrated in figure 1 . let n be the number of values a given feature can assume. by way of a further simplification, i assume that the choice of a mutation target follows a uniform distribution. the probability of a language being in state b at the end of a time interval of length t if it was in state a at the beginning of the interval is given by (1) (known as the jukes-cantor model of molecular evolution, see for instance @xcite . the parameter r (@xmath0, i.e., the expected number of mutations per unit of time. suppose the phylogeny, the parameters of the ctmc and the states at the tips of the phylogeny are observed. it is then possible to compute the posterior probability distribution of the state at the root of the tree via a postorder (bottom-up) recursion through the phylogeny. the likelihood of an observed state at a tip is 1, and the likelihood of all other states is 0. the likelihood of state a at an internal node α, conditional on the observed states at all tips descending from α, is given by the following equation, where dr(α) are the immediate daughter nodes of α. here t α,β is the length of the branch from α to β. applying this equation recursively via postorder traversal through the phylogeny, we obtain the likelihood of the individual states at the root. by assuming a uniform prior over states and applying bayes' rule, the posterior probability of state a at the root of the phylogeny is this algorithm is called ancestral state reconstruction (asr). a detailed study of applications of asr in linguistics for lexical evolution is given in @xcite ). an individual step of the recursion is graphically illustrated in figure 2 . it is a convenient feature of the jukes-cantor model that it is time reversible. this means that the likelihood of a state at a node, given partial knowledge of the states at other nodes, remains constant if the phylogeny is re-rooted and thereby the time arrow at some branches is reversed. due to this property, it is possible to use asr to impute unknown values at a tip of a tree. suppose a phylogeny and the states of a feature at some, but not all, tips is known. to estimate the probability distribution over states at a particular tip α with missing value, the following steps are performed: ## error analysis to assess which factors influence the performance of the phylogenetic imputation method, i conducted a 20-fold cross-validation on all languagefeature pairs for which the language corresponds to a tip in the asjp phylogeny. this provides a dataset of 44,598 language-feature pairs for which both a goldstandard value and an inferred value are available. not surprisingly, the accuracy of the predictions depend on the following three factors: the effect of these predictors is visualized in figure 6 . to test whether each of those three factors are relevant given the other two, i conducted a bayesian mixed-effects logistic regression with accuracy of prediction as dependent variable, feature entropy, log-transformed size of language family and logtransformed feature coverage as fixed effects, and language family and feature as random effects. the analysis was carried out using the r-package brms @xcite , which is based on the the programmning lanuage stan @xcite . the results are shown in it demonstrates that feature entropy has a credible negative effect, and both family size and feature coverage have a credible positive effect on accuracy. ## results and discussion according the evaluation script provided by the organizers of the shared task, this combination of phylogenetic and geographic knn value imputation achieved an overall accuracy of ≈ 0.68 -as compared to ≈ 0.51 both for the frequency baseline and the knn imputation baseline. samples were drawn using sampling(nuts). for each parameter, bulk_ess and tail_ess are effective sample size measures, and rhat is the potential scale reduction factor on split chains (at convergence, @xmath1. as pointed out in the introduction, this model makes several simplifying assumptions. the most serious one is arguably the presumed independence of typological features. the phylogenetics literature contains techniques for dealing with correlated discrete features @xcite . however, applying this approach on a large scale would lead to an explosion of parameters that cannot be estimated with the sparse data available in wals or similar data sources. therefore it seems more promising in the long run to attempt an embedding of discrete typological features into a continuous high-dimensional space and combine this with phylogenetic asr for continuous characters (using, e.g., a brownian motion model of evolution). such an approach can be combined with multivariate techniques like pca to detect correlations between features. furthermore, a principled study of the interplay between vertical/phylogenetic and horizontal transmission mechanisms is called for to make further progress in the task of typological value imputation.