Quantifying Semantics using Complex Network Analysis

Proceedings of COLING 2012: Technical Papers, pages 263–278, COLING 2012, Mumbai, December 2012. Quantifying Semantics Using Complex Network Analysis Chris Biemann Stefanie Roos Karsten Weihe Computer Science Department Technische Universität Darmstadt Hochschulstr. 10 64289 Darmstadt, Germany {biem,weihe}@cs.tu-darmstadt.de, stefanie.roos@cased.de ABSTRACT Though it is generally accepted that language models do not capture all aspects of real language, no adequate measures to quantify their shortcomings have been proposed until now. We will use n-gram models as workhorses to demonstrate that the differences between natural and generated language are indeed quantifiable. More specifically, for two algorithmic approaches, we demonstrate that each of them can be used to distinguish real text from generated text accurately and to quantify the difference. Therefore, we obtain a coherent indication how far a language model is from naturalness. Both methods are based on the analysis of co-occurrence networks: a specific graph cluster measure, the transitivity, and a specific kind of motif analysis, where the frequencies of selected motifs are compared. In our study, artificial texts are generated by n-gram models, for n = 2, 3, 4. We found that, the larger n is chosen, the narrower the distance between generated and natural text is. However, even for n = 4, the distance is still large enough to allow an accurate distinction. The motif approach even allows a deeper insight into those semantic properties of natural language that evidently cause these differences: polysemy and synonymy. To complete the picture, we show that another motif-based approach by Milo et al. (2004) does not allow such a distinction. Using our method, it becomes possible for the first time to measure generative language models deficiencies with regard to semantics of natural language. KEYWORDS: quantitative linguistics, network analysis, motif analysis, co-occurrence networks, language models. 263 1 Introduction Language models are used in many text processing systems (e.g. machine translation, document classification, language generation etc.) and are undoubtedly a standard building block of natu- ral language processing. However, there exist hardly any methods that characterize language models quantitatively, in order to measure their deficiencies with respect to real language: the commonly used perplexity measure is known to be insensitive to semantic aspects (Chang et al., 2009). To this end, we propose an automatic approach that not only can distinguish language-model-generated text from real text, it also quantifies their distance. Moreover, we can quantify language model shortcomings with respect to two semantic phenomena of natural language, namely polysemy and synonymy. The ability to measure, to what extent language models in fact model these and other characteristics of real language, is a prerequisite for improving language models to closer adhere to the many-layered structure of natural language. Before laying out the details of our approach, we would like to briefly sketch the general idea: If we accept that different language models capture natural language semantics to different extents, and if we had a measure that indicates and quantifies this extent, then this measure enables us to drive the development of language models towards a better reflection of …

Content truncated to 500 words