Estimating and visualizing language similarities using weighted alignment and force-directed graph layout

Proceedings of the EACL 2012 Joint Workshop of LINGVIS & UNCLH, pages 81–88, Avignon, France, April 23 - 24 2012. c⃝2012 Association for Computational Linguistics Estimating and visualizing language similarities using weighted alignment and force-directed graph layout Gerhard J¨ager University of T¨ubingen, Department of Linguistics gerhard.jaeger@uni-tuebingen.de Abstract The paper reports several studies about quantifying language similarity via pho- netic alignment of core vocabulary items (taken from Wichman’s Automated Simi- larity Judgement Program data base). turns out that weighted alignment accord-It ing to the Needleman-Wunsch algorithm yields best results. For visualization and data exploration pur- poses, we used an implementation of the Fruchterman-Reingold algorithm, a version of force directed graph layout. This soft- ware projects large amounts of data points to a two- or three-dimensional structure in such a way that groups of mutually similar items form spatial clusters. The exploratory studies conducted along these ways lead to suggestive results that provide evidence for historical relation- ships beyond the traditionally recognized language families. 1 Introduction The Automated Similarity Judgment Program (Wichmann et al., 2010) is a collection of 40-item Swadesh lists from more than 5,000 languages. The vocabulary items are all given in a uniform, if coarse-grained, phonetic transcription. In this project, we explore various ways to com- pute the pairwise similarities of these languages based on sequence alignment of translation pairs. As the 40 concepts that are covered in the data base are usually thought to be resistant against borrowing, these similarities provide information about genetic relationships between languages. To visualize and explore the emerging pat- terns, we make use of Force Directed Graph Lay- out. More specifically, we use the CLANS1 im- plementation of the Fruchterman-Reingold algo- rithm (Frickey and Lupas, 2004). This algorithm takes a similarity matrix as input. Each data point is treated as a physical particle. There is a re- pelling force between any two particles — you may think of the particles as electrically charged with the same polarity. Similarities are treated as attracting forces, with a strength that is positively related to the similarity between the correspond- ing data points. All data points are arranged in a two- or three- dimensional space. The algorithm simulates the movement of the particles along the resulting force vector and will eventually converge towards an energy minimum. In the final state, groups of mutually similar data items form spatial clusters, and the distance between such clusters provides information about their cumulative similarity. This approach has proven useful in bioinfor- matics, for instance to study the evolutionary his- tory of protein sequences. Unlike more com- monly used methods like SplitsTree (or other phy- logenetic tree algorithms), CLANS does not as- sume an underlying tree structure; neither does it compute a hypothetical phylogenetic tree or net- work. The authors of this software package, Tan- cred Frickey and Andrei Lupas, argue that this approach is advantageous especially in situations were a large amount of low-quality data are avail- able: “An alternative approach [...] is the visualization of all-against-all pairwise 1Cluster ANalysis …

Content truncated to 500 words