Automatic Language Classification by means of Syntactic Dependency Networks

Abstract

This article presents an approach to automatic language classification by means of linguistic networks. Networks of 11 languages were constructed from dependency treebanks, and the topology of these networks serves as input to the classification algorithm. The results match the genealogical similarities of these languages. In addition, we test two alternative approaches to automatic language classification – one based on n-grams and the other on quantitative typological indices. All three methods show good results in identifying genealogical groups. Beyond genetic similarities, network features (and feature combinations) offer a new source of typological information about languages. This information can contribute to a better understanding of the interplay of single linguistic phenomena observed in language.

ACKNOWLEDGEMENTS

This work was supported by the Linguistic Networks project (http://www.linguistic-networks.net/) funded by the German Federal Ministry of Education and Research (BMBF), and by the German Research Foundation Deutsche Forschungsgemeinschaft (DFG) in the Collaborative Research Center 673 “Alignment in Communication”.

We are grateful to Ramon Ferrer i Cancho, Barbara Job, Tatiana Lokot and the anonymous reviewers for their useful comments.

Notes

¹This notion goes back to Ferrer i Cancho et al. (2004) and will be explained in more detail below.

²Cognates are pairs of words from different languages that originate from the same ancestor language. The common origin is determined by regular phonetic change from one language to another and by related meaning of the two words. Borrowed words are not cognates (Kruskal et al., 1992).

³This model is based on the Graph eXchange Language GXL (Holt et al., 2006). Pustylnikov and Mehler (2008); Pustylnikov et al. (2008) adapted this format in order to model syntactic trees. See the TreebankWiki (http://ariadne.coli.uni-bielefeld.de/wikis/treebankwiki/) for all details on the conversion process.

⁴Ferrer i Cancho et al. (2004, p. 2).

⁵Note that weights of edges are not considered by this model; that is, if two words occur more than once in a modifier-head relation it does not result in an increase of degrees of these words.

⁶ C ₂ is a variant of C ₁ that weights the single c(v_i )s by their vertex degrees.

⁷Note, that all indices are computed only for the largest connected component (LCC). This is, of course, an abstraction and some information might become lost.

⁸The DC is 1 for a “star graph” (i.e. all vertices have degree d = 1, and one vertex has degree d = |V| − 1).

⁹The features γ(S) and R ² _γS (G) represent the power-law fit of the distribution of connected components of G, and lcc is the fraction of the largest connected component of G (see Features F ₁₀ and F ₁₁ in Table 2).

¹⁰We selected 300 n-grams as suggested by Cavnar and Trenkle (1994) for n = {1, … , 6}.

¹¹We selected these indices since they could be applied to our sort of data, i.e. dependency treebanks.

¹²29 is the maximal number of samples with 1000 tokens that can be taken from the smallest treebank (i.e. from Slovene). That is, we select 29 as the least common number of samples for each treebank.

¹³This and the following indices were calculated on a sample of 1499 sentences from each treebank. This number is the smallest common number of sentences obtainable from each treebank.

¹⁴The example is taken from Altmann and Lehfeldt (1973).

¹⁵ m is the maximal value of the index j (see Dm), i.e. the deepest level in the dependency tree.

¹⁶All the computations of the cluster analysis are made using MATLAB version 7.11.0.584 7. (R2010b) including the Statistics and Curve Fitting Toolboxes (www.mathworks.de).

¹⁷We have computed the pairwise correlations among all features. Here and in the following paragraphs we show only results that are statistically significant.

¹⁸Note that all correlations exemplified here are significant with a p-value < 0.05.