{"content":[{"text":"Comparing Complexity Measures","bbox":{"left":0.353773,"top":0.073353,"width":0.310118,"height":0.019463999999999995}},{"text":"Benoît Sagot \n Alpage, Inria & Université Paris–Diderot, Paris, France \n benoit.sagot@inria.fr","bbox":{"left":0.308892,"top":0.110968,"width":0.39969899999999997,"height":0.04857200000000002}},{"text":"Given the range of ways morphological complexity is quantitatively defined and used in the recent \n literature, understanding precisely what the term complexity could and should denote in this context \n remains an open question. In this work, we aim at providing a global picture of the major approaches to \n morphological complexity, discuss some of their limitations — some to be found in the literature, some \n being unveiled here — and suggest one path towards a more satisfying way to quantify one particular point \n of view on morphological complexity. \n We shall leave aside basic approximations such as counting category instances (McWorther 2001; \n Bickel & Nichols 2005; Shosted 2006). Indeed, the very possibility to count, for example, genders and \n cases within morphological systems in a clear-cut and language-independent way is arguably dubious. \n More interestingly, complexity has been introduced within the paradigm of Information Theory, and used \n in a morphological context, in at least two ways, on which our work focuses: data description length and \n predictability of a new data instance. The intuition behind description length has been formalized by \n Kolmogorov (1965), and is therefore known as Kolmogorov Complexity (KC). The idea is to measure \n how random is the data at hand, e.g., a large-scale morphological lexicon. This randomness is assessed by \n defining complexity as the smallest quantity of information required for describing the data: KC captures \n any structure underlying the data, be it intuitive and meaningful or not. However, KC cannot be computed \n exactly. One usual way to approximate it (but not the only one, see Juola (1998)) is to use a formal \n description language that suits the data, and find the description of the data within that language that \n contains as little information as possible (information being considered here as entropy times length): one \n compares the compactness of descriptions. If the formal (morphological) description language that is used \n captures “meaningful” structures only, compactness results will better match human intuition. This leads to \n a formalism-dependent definition of morphological complexity (Bane 2008; Sagot & Walther 2011). \n KC-based approaches are sometimes criticized because of their being formalism-dependent. Several \n authors have therefore used another definition of the notion of complexity, Shannon’s Entropy (SE). One \n can consider and model the data (a corpus, a lexicon…) as a set of data instances (sentences/words, lexical \n units…) emitted by a system. Shannon’s (1948) entropy is a way to assess the amount of uncertainty \n expected in a new data instance given a model of the system built based on previously seen data instances. \n This requires encoding the data as a sequence of independent and identically distributed random variables \n according to a probabilistic model, which is difficult in practice. Still, it has been used directly on corpora \n (Moscoso del Prado Martín et al., 2004; Moscoso del Prado Martín, 2010; Pellegrino et al., 2007, 2010), \n and also to model interpredictability between cells within a paradigm: this is Ackerman and colleagues’ \n Paradigm Cell Filling Problem (PCFP). This formulation leads its authors to defining morphological \n complexity, in their case paradigm complexity, as the average of all conditional entropies of each cell \n given each other cell. This measures computes how reliable are implicative patterns for guessing one cell \n from another (Ackerman et al. 2009; Malouf & Ackerman 2010). However, Bonami et al. (2011) have \n identified four issues concerning Ackerman et al.’s approach, which can be rephrased as follows: type \n frequency is ignored (each inflection class counts just as much as another), the way the inventory of \n inflection classes is built alters the results, the use of manually segmented data biases the results (the \n boundary between stem and suffix is given), and (mor)phonology is embedded in the data, so one does not \n measure morphological complexity only. We have performed a set of quantitative experiments, using the \n same French verbal data as above, which corroborate these remarks. Using type frequency from the Lefff \n lexicon or from a corpus or ignoring type frequency, ignoring rare inflection classes or not, using manually \n or automatically segmented data, ignoring morphonology or not, all these parameters lead to paradigm \n entropies that range from 0.08 to 0.72 for the same data! But there are two deeper issues. First, this \n entropy-based measure is no less formalism-dependent than the description-length-based one mentioned \n above. For example, if a cell is always filled by the reduplication of the content of another cell given, the","bbox":{"left":0.120851,"top":0.180803,"width":0.7759499999999999,"height":0.7335860000000001}}],"images_bbox":[],"images_bbox_not_text_overlap":[]}