Taking into account semantic similarities in correspondence analysis Mattia Egloff1, François Bavaud1, 2

Abstract

Term-document matrices feed most distributional approaches to quantitative textual studies, without consideration for the semantic similarities between terms, whose presence arguably reduces content variety. This contribution presents a formalism remedying this omission, and makes an explicit use of the semantic similarities as extracted from WordNet. A case study in similarityreduced correspondence analysis illustrates the proposal.

1 Introduction

The term-document matrix N = (nik) counts the occurrences of n terms in p documents, and constitutes the privileged input of most distributional studies in quantitative textual linguistics: chi2 dissimilarities between terms or documents, distancebased clustering of terms or documents, multidimensional scaling (MDS) on terms or documents; and, also, latent clustering by non-negative matrix factorization (e.g., Lee and Seung, 1999) or topic modeling (e.g., Blei, 2012) ; as well as nonlinear variants resulting from transformations of the independence quotients, as in the Hellinger dissimilarities, or transformations of the chi2 dissimilarities themselves (e.g., Bavaud, 2011).

When using the term-document matrix, the semantic link between words is only indirectly addressed through the celebrated “distributional hypothesis,” postulating an association between distributional similarity (the neighbourhood or closeness of words in a text) and meaning similarity (the closeness of concepts) (Harris, 1954) (see also, e.g., Sahlgren, 2008; McGillivray et al., 2008) . Although largely accepted and much documented, the study of the distributional hypothesis seems hardly tackled in an explicit way, by typically computing and comparing the average semantic similarity within documents or contexts to the average semantic similarity between documents or contexts – which supposes the recourse to some hand-crafted semantics, fairly unavailable at the time of Harris’ writings.

The present short study distinguishes both kinds of similarities and constitutes at this stage a proof of concept oriented towards the formalism and the conceptualization rather than large-scale applications – in the general spirit of the COMHUM 2018 conference. It yields a new measure of textual variety taking explicitly into account the semantic similarities between terms, and permits to weigh the usage of the semantic similarity when analyzing the term-document matrix. 2

Data

After manually extracting the paragraphs of each of the p = 11 chapters of Book I of “An Inquiry into the Nature and Causes of the Wealth of Nations” by Adam Smith (Smith, 1776) (a somewhat arbitrary choice among myriads of other possibilities), we tagged the parts of speech and lemma for each word of the corpus using the nlp4j tagger (Choi, 2016) . Subsequently we created a lemma-chapter matrix, retaining only the type of words serving a specific task, such as verbs. Terms i; j present in the chapters were then associated to their first conceptual senses ci; c j, that is to their first WordNet synsets (Miller, 1995) . We inspected several similarity matrices sˆi j = sˆ(ci; c j) between pairs of concepts ci and c j. 3

Semantic similarities

A few approaches for computing similarities between words have been proposed in the literature (see, e.g., Gomaa and Fahmy, 2013) . Recent measures use word embeddings (Kusner et al., 2015) , and tough these approaches are successful at resolving other NLP tasks, they suffer some drawbacks in computing semantic similarity (Faruqui et al., 2016) . Also, the latter methods are directly based on the distributional hypothesis, and hence unadapted to distinguish between distributional and semantic dissimilarities, precisely.

By contrast, the present paper uses WordNet, that is a humanly constructed ontology. The classical WordNet similarities sˆ(ci; c j) between two concepts ci and c j computed on WordNet take on different forms. The conceptually easiest is the path similarity, defined from the number `(ci; c j) 0 of edges of the shortest-path (in the WordNet hierarchy) between ci and c j as follows: 1 sˆpath(ci; c j)= 1 + `(ci; c j) (1)

The Leacock Chodorow similarity (Leacock and Chodorow, 1998) is based on the same principle but considers also the maximum depth D = maxi `(ci; 0) (where 0 represents the root of the hierarchy, occuped by the concept subsuming all the others) of the concepts in the WordNet taxonomy:

sˆlch(ci; c j) = log `(c2iD;c j)

The Wu-Palmer similarity (Wu and Palmer, 1994) is based on the notion of lowest common subsumer ci _ c j, that is the least general concept in the hierarchy that is a hypernym or ancestor of both ci and c j: sˆwup(ci; c j)=

2`(ci _ c j; 0) `(ci; 0) + `(c j; 0)

The following similarities are further based on the concept of Information Content, proposed by Resnik (Resnik, 1993b,a) . The Information Content of a concept c is defined as log(p(c)), where p(c) is the probability to encounter a concept c in a reference corpus. The Resnik similarity (Resnik, 1995) is defined as: The Lin similarity (Lin, 1998) is defined as: sˆres(ci; c j)= log p(ci _ c j)

2 log p(ci _ c j) sˆlin(ci; c j)= log p(ci) + log p(c j)

Finally, the Jiang Coranth similarity (Jiang and Conrath, 1997) is defined as: 1 sˆjch(ci; c j)= log p(ci) log p(c j) + 2 log p(ci _ c j) and obeys sˆjch(ci; ci) = ¥.

Among the above similarities, the path, WuPalmer and Lin similarities obey the conditions sˆi j = sˆ ji 0 and sˆii = 1 : (2) In what follows, we shall use the path similarities when required. 4

A similarity-reduced measure of textual variety

Let fi 0 be the relative frequency of term i, normalized to åin=1 fi. Shannon entropy H = åi fi ln fi constitutes a measure of relative textual variety, ranging from 0 (a single term repeats itself) to ln n (all terms are different). Yet, the entropy does not take into account the possible similarity between the terms, in contrast to the reduced entropy R (our nomenclature) defined as

R = n n å fi ln bi where bi = å sˆi j f j : i=1 j=1 (3) In Ecology, bi is the banality of species i, measuring its average similarity to other species (Marcon, 2016) , proposed by Leinster and Cobbold (2012) , as well as by Ricotta and Szeidl (2006) . By construction, fi bi 1 and thus R H: the larger the similarities, the lower the textual variety as measured by the reduced entropy, as requested.

Returning to the case study, we have, out of the 643 verb lemmas initially present in the corpus, retained the n = 234 verb lemmas occurring at least 5 times (“be” and “have” excluded). Overall term weights fi, chapter weights rk and term weights fik within a chapter obtain from the n p = 234 11 term-document matrix N = (nik) as fi = ni n rk = n k n fik = nik n k (4)

The corresponding entropies and reduced entropies read H = 4:98 > R = 1:60. For each chapter, the corresponding quantities are depicted in figure 1. One can observe the so-called concavity property H > åk rkHk (always verified) and R > åk rkRk (verified here), which says that the variety of the whole is larger than the average variety of its constituents. 5 4 3 2 1 0 0 4 1 0 2 1 0 0 1 0 8 0 6 0 4 0 2 0

Shannon entropy Hk reduced entropy Rk Shannon variety exp(H) reduced variety exp(R)

-2.0 -1.5 -1.0 -0.5 0.0 0.5 dimension 1 : proportion of inertia = 0.17

Shannon variety NShannon = exp(H) n represents the equivalent number of distinct types in a uniformly constituted corpus of same richness or diversity (in the entropy sense) as the currently examined corpus. Likewise, the reduced variety Nreduced = exp(R) NShannon measures the equivalent number of types if the latter were uniformly distributed and completely dissimilar (that is si j = 0 for i 6= j): see figure 2. 5

Ordinary correspondence analysis (recall)

Correspondence analysis (CA) permits a simultaneous representation of terms and documents in the so-called biplot (figure 3). CA results from weighted multidimensional scaling (MDS) applied to the chi2 dissimilarities Dkcl between documents k and l

n Dkcl = å fi(qik i=1 qil )2 where qik = nnikn i n k (5) or equivalently, on MDS applied to the chi2 dissimilarities between terms. Note the qik in (5) to constitute the independence quotients, that is the ratio of the observed counts to their expected value under independence. Figure 3 constitutes the two-dimensional projection of a weighted Euclidean configuration of min(234 1; 11 1) = 10 dimensions, expressing a maximal proportion of 0:17 + 0:15 = 32% of dispersion or inertia D = c 12 åkl rkrlDkl.

Similarity-reduced correspondence analysis In the case where documents k and l, differing by the presence of distinct terms, contain semantically similar terms, the “naive” chi2 dissimilarity (5), which implicitly assumes distinct terms to be completely dissimilar, arguably overestimates their difference. The latter should be downsized accordingly, in a way both reflecting the amount of shared similarity between k and l, and still retaining the squared Euclidean nature of their dissimilarity – a crucial requirement for the validity of MDS. This simple idea leads us to propose the following reduced squared Euclidean distance Dˆ kl between documents, taking into account both the distributional and semantic differences between the documents, namely

D˜ kl = å t˜i j(qik i j qil )(q jk q jl ) (6) seem appear -0.05 0.00 0.05 0.10 dimension 1 : proportion of inertia = 0.19 0.15 -0.5 -0.4 -0.3 -0.2 -0.1 0.0 dimension 1 : proportion of inertia = 0.05 0.1

T˜ = diag( f ) for “naive” similarities Sˆ = I (where I is the identity matrix), in which case D˜ is the usual chi2-dissimilarity T˜ = f f 0 for “confounded types” Sˆ = J (where J is the unit matrix filled with ones), in which case D˜ is identically zero.

Also, one can prove D˜ in (6) to be a squared Euclidean dissimilarity iff S is positive semi-definite, that is iff all its eigenvalues are non-negative, a verified condition for path dissimilarities (see the Appendix). Figure 4 depicts the corresponding MDS.

Semantic MDS on terms Positive semi-definite semantic similarities Sˆ of the form (2), such as the path similarities, generate squared Euclidean dissimilarities as (see the Appendix), and this circumstance allows a weighted MDS on semantic dissimilarities between terms, aimed at depicting an optimal lowdimensional representation of the semantic inertia

A family of similarities interpolating between totally distinct types and confounded types The exact form of similarities Sˆ between terms fully governs the similarity-reduction mechanism investigated so far. Yet, little systematic investigation seems to have been devoted to the formal properties of similarities (by contrast to the study of the dissimilarities families found, for example, in Critchley and Fichet (1994) or Deza and Laurent (2009) , which may obey much more specific properties than (2). In particular, sˆiaj satisfies (2) for a 0 if sˆi j does, and varying a permits to interpolate between the extreme cases of “naive” similarities Sˆ = I and “confounded types” Sˆ = J.

Lists of synonyms1 yield binary similarity matrices si j = 0 or 1. More generally, S can be defined (7)

1. For example: http://www.crisco.unicaen.fr/des/ standard C6A 98 7 2 captured by the general concept of exchange matrix E, giving the joint probability to select a pair of textual positions through textual navigation (by reading, hyperlinks or bibliographic zapping, etc.). E defines a weighted network whose nodes are the textual positions occupied by terms (Bavaud et al., 2015).

The parallel with spatial issues (quantitative geography, image analysis), where E defines the “where”, and the features dissimilarities between positions D defines the “what”, is immediate (see, e.g., Egloff and Ceré, 2018) . In all likelihood, developing both axes, that is taking into account semantic similarities on generalized textual networks, could provide a fruitful extension and renewal of the venerable term-document matrix paradigm, and provide a renewed look to the distributional hypothesis, which can be reframed as a spatial autocorrelation hypothesis.

Acknowledgments

The guidelines and organisation of M. Piotrowski, chair of COMHUM 2018, as well as the suggestions of two anonymous reviewers are gratefully acknowledged.

Bavaud, François (2011). On the Schoenberg transformations in data analysis: Theory and illustrations. Journal of Classification, 28(3):297–314. doi:10.1007/s00357-011-9092-x. ˆ di j = 1 sˆi j = 1 =

`i j 1 + `i j that is dˆ i j = j (`i j), where j (x) = x=(1 + x). The function j (x) is non-negative, increasing, concave, with j (0) = 0. For r 1, its even derivatives j (2r)(x) are non-positive, and its odd derivatives j (2r 1)(x) are non-negative. That, is, j (x) is a Schoenberg transformation, transforming a squared Euclidean dissimilarity into a squared Euclidean dissimilarity (see, e.g., Bavaud, 2011), thus establishing the squared Euclidean nature of D in (7) (and, by related arguments, the p.s.d. nature of S). 2. Provided no terms possess two direct hypernyms, which seems to be verified for the verbs considered here

References

5 1 .0 .01 = a itr ine .05 f o n itroo .00 p o r :p2 .-50 n o i sen .-10 m i d 5 1 .0 .01 = a itr ine .05 f o n itroo .00 p o r :p2 .-50 n o i sen .-10 m i d 10 10 1 3 Bavaud , François, Christelle Cocco , and Aris Xanthos ( 2015 ). Textual navigation and autocorrelation . In G. Mirkros and J. Macutek, eds., Sequences in Language and Text , pages 35 - 56 . De Gruyter Mouton.

Blei , David M ( 2012 ). Probabilistic topic models . Communications of the ACM , 55 ( 4 ): 77 - 84 .

doi:10.1145/2133806 .2133826.

Choi , Jinho D. ( 2016 ). Dynamic Feature Induction: The Last Gist to the State-of-the-Art . In Proceedings of the 15th Annual Conference of the North American Chapter of the Association for Computational Linguistics, NAACL'16 , pages 271 - 281 . San Diego, CA. URL https://aclweb.org/anthology/N/ N16/N16-1031.pdf.

Critchley , Frank and Bernard Fichet ( 1994 ). The partial order by inclusion of the principal classes of dissimilarity on a finite set, and some of their basic properties .

In Bernard Van Cutsem, ed., Classification and Dissimilarity Analysis , pages 5 - 65 . New York, NY: Springer.

doi:10 .1007/978-1- 4612 -2686- 4 _ 2 .

Deza , Michel and Monique Laurent ( 2009 ). Geometry of cuts and metrics , vol. 15 of Algorithms and Combinatorics. Berlin/Heidelberg: Springer.

doi:10 .1007/978-3- 642 -04295-9.

Egloff , Mattia and Raphaël Ceré ( 2018 ). Soft textual cartography based on topic modeling and clustering of irregular, multivariate marked networks . In Chantal Cherifi , Hocine Cherifi, Márton Karsai, and Mirco Musolesi, eds., Complex Networks & Their Applications VI , vol. 689 of Studies in Computational Intelligence, pages 731 - 743 . Cham: Springer. doi: 10 .1007/978-3- 319 -72150-7_ 59 .

Faruqui , Manaal, Yulia Tsvetkov, Pushpendre Rastogi, and Chris Dyer ( 2016 ). Problems with evaluation of word embeddings using word similarity tasks . In Proceedings of the 1st Workshop on Evaluating Vector Space Representations for NLP , pages 30 - 35 . Association for Computational Linguistics . URL https: //aclweb.org/anthology/W/W16/W16-2506.pdf.

Gomaa , Wael H . and Aly A Fahmy ( 2013 ). A survey of text similarity approaches . International Journal of Computer Applications , 68 ( 13 ): 13 - 18 .

doi:10 .5120/ 11638 - 7118 .

Harris , Zellig S. ( 1954 ). Distributional structure . Word , 10 ( 2-3 ): 146 - 162 .

Jiang , Jay J. and David W. Conrath ( 1997 ). Semantic similarity based on corpus statistics and lexical taxonomy . In Proceedings of International Conference on Research in Computational Linguistics (ROCLING X) , pages 19 - 33 .

Kusner , Matt, Yu Sun, Nicholas Kolkin, and Kilian Weinberger ( 2015 ). From word embeddings to document distances . In Francis Bach and David Blei, eds., Proceedings of the 32nd International Conference on Machine Learning , vol. 37 of Proceedings of Machine Learning Research , pages 957 - 966 .

PMLR. URL http://proceedings.mlr.press/ v37/kusnerb15.html.

Leacock , Claudia and Martin Chodorow ( 1998 ). Combining local context and WordNet similarity for word sense identification . In Christiane Fellbaum and George A . Miller, eds., WordNet: An Electronic Lexical Database, chap. 11 , pages 265 - 284 . Cambridge, MA: MIT Press.

Lee , Daniel D. and H. Sebastian Seung ( 1999 ). Learning the parts of objects by non-negative matrix factorization . Nature , 401 : 788 - 791 . doi: 10 .1038/44565.

Leinster , Tom and Christina A. Cobbold ( 2012 ). Measuring diversity: the importance of species similarity .

Ecology , 93 ( 3 ): 477 - 489 . doi:10. 1890 /10- 2402 .1.

Lin , Dekang ( 1998 ). An information-theoretic definition of similarity . In Proceedings of the Fifteenth International Conference on Machine Learning, ICML '98 , pages 296 - 304 . San Francisco, CA, USA: Morgan Kaufmann.

Marcon , Eric ( 2016 ). Mesurer la Biodiversité et la Structuration Spatiale . Thèse d'habilitation, Université de Guyane. URL https: //hal-agroparistech. archives-ouvertes .fr/ tel-01502970.

McGillivray , Barbara, Christer Johansson , and Daniel Apollon ( 2008 ). Semantic structure from correspondence analysis . In Proceedings of the 3rd Textgraphs Workshop on Graph-Based Algorithms for Natural Language Processing , pages 49 - 52 . Association for Computational Linguistics . URL https://aclweb.org/ anthology/W/W08/W08-2007.pdf.

Miller , George A. ( 1995 ). WordNet: a lexical database for English . Communications of the ACM , 38 ( 11 ): 39 - 41 . doi: 10 .1145/219717.219748.

Resnik , Philip ( 1993a ). Selection and information: a class-based approach to lexical relationships . Tech.

Rep . IRCS- 93 -42, University of Pennsylvania Institute for Research in Cognitive Science. URL http: //repository.upenn.edu/ircs_reports/200.

Resnik , Philip ( 1993b ). Semantic classes and syntactic ambiguity . In Proceedings of the Workshop on Human Language Technology (HLT '93) , pages 278 - 283 . Association for Computational Linguistics . URL https: //www.aclweb.org/anthology/H93-1054.pdf.

Resnik , Philip ( 1995 ). Using information content to evaluate semantic similarity in a taxonomy . In Proceedings of the International Joint Conference for Artificial Intelligence (IJCAI-95) , pages 448 - 453 .

Ricotta , Carlo and Laszlo Szeidl ( 2006 ). Towards a unifying approach to diversity measures: bridging the gap between the Shannon entropy and Rao's quadratic index . Theoretical Population Biology , 70 ( 3 ): 237 - 243 .

doi:10 .1016/j.tpb. 2006 . 06 .003.

Sahlgren , Magnus ( 2008 ). The distributional hypothesis . Rivista di Linguistica , 20 ( 1 ): 33 - 53 . URL http:// linguistica.sns.it/RdL/20.1/Sahlgren.pdf.

Smith , Adam ( 1776 ). An Inquiry into the Nature and Causes of the Wealth of Nations; Book I. Urbana, Illinois: Project Gutenberg . Also known as: Wealth of Nations . URL http://www.gutenberg.org/ebooks/ 3300.

Wu , Zhibiao and Martha Palmer ( 1994 ). Verbs semantics and lexical selection . In Proceedings of the 32nd annual meeting of the Association for Computational Linguistics , pages 133 - 138 . Association for Computational Linguistics . URL https://www.aclweb.org/ anthology/P94-1019.pdf.

Appendix: Proof of the squared Euclidean nature of D in (7).

The number `i j of edges is the shortest path (in the WordNet hierarchical tree) linking the concepts associated to i and j is a a tree dissimilarity2, and hence a squared Euclidean dissimilarity (see , e.g., Critchley and Fichet , 1994 ). Hence, (1) and (7) entail