Edward Gibson
email: egibson@mit.edu

Richard Futrell

Steven T Piantadosi

Isabelle Dautriche

Kyle Mahowald

Leon Bergen

Roger Levy
email: rplevy@mit.edu

How Efficiency Shapes Human Language

Keywords: language evolution, communication, language efficiency, cross-linguistic universals, language learnability, language complexity

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

How Efficiency Shapes Human Language

Why do languages look the way they do?

Depending on how you count, there are 6000-8000 distinct languages on earth. The differences among languages seem pretty salient when you have to learn a new language: you have to learn a new set of sounds, a new set of words, and a new way of putting the words together; nevertheless, linguists have documented a wealth of strong recurring patterns across languages [START_REF] Jackendoff | Foundations of Language: Brain, Meaning, Grammar, Evolution[END_REF][START_REF] Aikhenvald | The Cambridge Handbook of Linguistic Typology[END_REF]. These language universals, which may be exceptionless or instead strong statistical tendencies [START_REF] Joseph | Some universals of grammar with particular reference to the order of meaningful elements[END_REF], are key desiderata for explanatory theories of language structure. Here we review recent progress made in explaining some of these universals through a theoretical framework in which languages must offer communicative efficiency under information processing and learning constraints.

Because language is used for transferring information in social environments, a likely influence on language might be how its structure affects efficiency of use: languages may be under pressure to be structured so as to facilitate easy, rapid, and robust communication [START_REF] Kingsley | Human behaviour and the principle of least-effort[END_REF][START_REF] Charles | The origin of speech[END_REF][START_REF] Slobin | Cognitive prerequisites for the development of grammar[END_REF][START_REF] Comrie | Language Universals and Linguistic Typology[END_REF][START_REF] Givón | Markedness in grammar: Distributional, communicative and cognitive correlates of syntactic structure[END_REF][START_REF] Hawkins | A performance theory of order and constituency[END_REF][START_REF] Croft | Functional approaches to grammar[END_REF][START_REF] Bybee | From usage to grammar: The mind's response to repetition[END_REF][START_REF] Haspelmath | Parametric versus functional explanations of syntactic universals[END_REF]. Traditional theories de-emphasized efficiency of use as a source for similarities of structure across languages, most prominently because of the existence of ambiguity at all levels of linguistic structure: if a component of language is ambiguous, that would arguably make it difficult to use [START_REF] Chomsky | Reflections on language[END_REF]. But recent information-theoretic analyses have shown that the existence of ambiguity is actually not a problem in language use, because context usually disambiguates [START_REF] Steven T Piantadosi | The communicative function of ambiguity in language[END_REF]. Furthermore, the recent availability of large corpora across languages, and natural language processing tools to analyze them, has enabled quantitative evaluation of the possibility that communicative efficiency is a force shaping language structure. We can therefore conceive of a language's utility in terms of not only its learnability (or complexity) but also its efficiency of use, such that more efficient languages might be more useful overall [START_REF] Jaeger | On language 'utility': Processing complexity and communicative efficiency[END_REF]. This article reviews the convergent picture that such studies provide: across levels of linguistic analysis-from words to syntax-the form of human language exhibits a strong tendency to be structured for efficient use. In what follows below, we first define efficiency and other concepts from information theory that will be used in this review [START_REF] Shannon | A mathematical theory of communications[END_REF]. Then we review the evidence that the existence of ambiguity in linguistic structures out of context is actually an argument for the information-theoretic approach and not against it. In the main bulk of the review, we next summarize recent results about cross-linguistic universals that can be explained by concepts related to efficiency. Most of this evidence comes from analyses of large texts across languages (see Box 1 for a summary of this and other methods). We then provide evidence that communicative efficiency must often be balanced against the complexity and learnability of languages.

While it is often possible to formulate these other constraints in information-theoretic terms [e.g. as in 17], it remains to be seen whether this is possible in all cases. Finally, we present some challenges for the efficiency / learnability framework.

What is Communicative Efficiency?

Our notions of 'communication' and 'efficiency' are drawn from information theory, which provides a general yet mathematically precise picture of these concepts. The information-theoretic view of communication is summarized in Figure 1. First, an information source selects a message to be transmitted. Next, the message is encoded into a signal, and that signal is sent to a receiver through some medium called a channel. The receiver then decodes the signal to recover the intended message. Successful communication takes place when the message recovered at the destination is equal to the message selected at the source, or diverges from it only slightly. Efficiency in communication means that successful communication can be achieved with minimal effort on average by the sender and receiver. Typically, effort is quantified using the length of messages, so efficient communication means that signals are short on average while maximizing the rate of communicative success. The task of choosing a code that makes signals short on average, according to the distribution over messages coming out of the information source, is called source coding.

In the case of human language, the speaker is the information source and sender, the utterance is the signal, and the listener is the receiver and destination. Under this view, human languages are codes that enable information to be transmitted through the channel of the acoustic or visual environment. This information-theoretic picture of language is fundamentally usage-based, because communicative efficiency requires that the messages that we often want to send can be transmitted with minimal effort.

The transmission process may be noisy, meaning that there exist errors in transmission. For example, a speaker and listener may be speaking in a noisy room where the listener cannot perceive all the words the speaker says, or the speaker may be making speech errors, or the listener may not be paying full attention: these and all phenomena that introduce error during communication are called noise. Information theory describes codes which enable communicative efficiency even in the presence of noise of various kinds. When a code enables communication despite noise, it is called robust. The task of choosing a code to enable communication in the presence of noise, according to the characteristics of the channel, is called channel coding.

The overall communicative efficiency of a language in this framework boils down to a simple intuition: an efficient language should enable a speaker to transmit many different messages successfully with minimal effort. Note that information theory as specified so far is entirely agnostic to the form and content of messages-it makes no assumptions about the meaning ultimately communicated by an utterance of language.

The underlying messages could be model-theoretic statements about the world, or they could be imperative instructions, or they could contain information about the relative social status of speaker and listener; all that matters from the perspective of information theory is that messages are transmitted accurately, regardless of their content. Despite this extreme generality, it is nevertheless possible to develop a rich mathematical apparatus for describing communicative efficiency, which is summarized in Box 2. The theory was originally developed in applied settings for the development of telecommunications and cryptography systems [START_REF] Shannon | A mathematical theory of communications[END_REF][START_REF] Shannon | Communication theory of secrecy systems[END_REF]. However, it has seen wide application in fields related to cognitive science, including theoretical neuroscience [START_REF] Friston | The free-energy principle: A unified brain theory[END_REF], statistical complexity theory [START_REF] Rohilla | Computational mechanics: Pattern and prediction, structure and simplicity[END_REF][START_REF] Bialek | Predictability, complexity, and learning[END_REF], and models of rational action under information processing constraints [START_REF] Rubin | Trading value and information in MDPs[END_REF][START_REF] Genewein | Bounded rationality, abstraction, and hierarchical decision-making: An information-theoretic optimality principle[END_REF]. Fruitful applications of information theory to language are now possible due to large datasets and computational power that make it possible to estimate information-theoretic quantities such as entropy from language data [START_REF] Pereira | Formal grammar and information theory: together again?[END_REF].

The existence of ambiguity out of context

One domain where theories of efficient use have been argued to have trouble is the existence of ambiguity, a pervasive phenomenon in language that can be observed in lexical, morphological, syntactic, and semantic systems. Perhaps most famously, Chomsky argued that ambiguity is a hallmark of an inefficient communication system because it permits the possibility of confusion [START_REF] Chomsky | Reflections on language[END_REF]. Chomsky has used this to argue that, in fact, language is not "designed" for communication at all, but rather for some other functions (perhaps, e.g., for thinking). Indeed it is unclear why one would ever design an ambiguous communication system or what role ambiguity might serve [START_REF] Wasow | The puzzle of ambiguity. Morphology and the web of grammar: Essays in memory of Steven G. Lapointe[END_REF]. This puzzle is resolved by recognizing the role of the context of usage: to a first approximation, context resolves all communicatively relevant ambiguity [START_REF] Miller | Language and communication[END_REF] (even for children learning their native language [START_REF] Fibla | Learning homophones in context: Easy cases are favored in the lexicon of natural languages[END_REF]), and in natural conversation the participants can easily query each other to rapidly clarify any residual uncertainties [START_REF] Herbert | Using language[END_REF].

In this light, ambiguity becomes a communicatively desirable feature of language: by leaving out information inferrable from context, we can speak more concisely. This fact can be proven rigorously in information theory [START_REF] Steven T Piantadosi | The communicative function of ambiguity in language[END_REF], and can be appreciated intuitively by looking at places where we attempt to communicate with zero ambiguity, such as legal contracts and computer programming languages. Both of these often end up being wordy or pedantic to an extent that feels unnecessary. The extra effort it would take to make utterances unambiguous (even out of context) would simply be wasted in ordinary language use settings.

Evidence of Communicative Efficiency in Human Language

Evidence of communicative efficiency is provided below, at the levels of the lexicon, syntax, and morphology.

The Lexicon

The lexicon (or dictionary) is the set of words or lexemes that a speaker of a human language knows. Each lexical entry consists of a sequence of sounds paired with a meaning. It is estimated that the average American adult knows about 40,000 words [START_REF] Brysbaert | How many words do we know? practical estimates of vocabulary size dependent on word definition, the degree of language input and the participant's age[END_REF].

Word Length. One of the simplest domains in which communicative efficiency has been studied is in word lengths. A well-known statistical law of linguistics, popularized by George K. Zipf [START_REF] Zipf | The Psycho-Biology of Language: An Introdution to Dynamic Philology[END_REF], is that more frequent words tends to be shorter (e.g. "the" vs "accordion"). This makes intuitive sense: if signals that are sent most frequently are shorter, then we can decrease the average length of a message. For this reason, communication systems like Morse Code also have this principle (e.g. the dot sequence for a frequent letter like "e",".", is shorter than for an infrequent one like"q","--. -"). However, Zipf worked before information theory provided a mathematical framework for understanding optimal codes. In an optimal code, the length of a signal will depend on its probability in context, not its overall frequency [START_REF] Ian H Witten | Arithmetic coding for data compression[END_REF]. For instance, if context tells us that there are only two ways for the British to land, Paul Revere can get by with just a single-bit message (one vs. two lights in the Old North Church) instead of having to signal out an entire sentence. Likewise, since language processing mechanisms use contextual information and previous linguistic input to make predictions [START_REF] Marslen-Wilson | Sentence perception as an interactive parallel process[END_REF], a more information-theoretically refined version of Zipf predicts that, if language is functioning in a communicatively efficient manner, word length should depend on predictability in context rather than frequency: words that tend to be predicted by context should be even shorter than their frequency predicts. This was shown to be true in a variety of languages by showing that a word's probability in context in a corpus was a stronger determinant of its length than the word's overall frequency [START_REF] Steven T Piantadosi | Word lengths are optimized for efficient communication[END_REF] (see Figure 2). This pattern likely reflects lexicalization of processes that shorten predictable words, observable both in language production choices and in historical change. The existence of information-theoretically efficient shortening processes in production choice is demonstrated in [START_REF] Mahowald | Info/information theory: Speakers choose shorter words in predictive contexts[END_REF], who show that speakers are more likely to choose the short form of a near synonymous pair like "chimp"/"chimpanzee" in a predictive context than in a neutral context. Together, these results indicate that the processes shaping both the lexicon and word choice are influenced by information-theoretic considerations of predictability-over and above frequency, and exactly as should be expected for an efficient communication system.

The partitioning of semantic space in the lexicon. Beyond the form of words, there has been a great deal of research over the past 70 years on why a language has the words that it does, within a variety of semantic domains, including kinship relations [e.g., [START_REF] Peter | Social structure[END_REF][START_REF] Nerlove | Sibling terminology and cross-sex behavior 1[END_REF], color [START_REF] Berlin | Basic color terms: Their university and evolution[END_REF][START_REF] Kay | The linguistic significance of the meanings of basic color terms[END_REF], spatial relations [START_REF] Bowerman | Learning how to structure space for language: A crosslinguistic perspective[END_REF][START_REF] Talmy | How language structures space[END_REF][START_REF] Stephen | Natural concepts' in the spatial topological domain-adpositional meanings in crosslinguistic perspective: an exercise in semantic typology[END_REF][START_REF] Majid | Can language restructure cognition? The case for space[END_REF], and numeral systems [START_REF] Joseph | Generalizations about numeral systems[END_REF][START_REF] Comrie | Numeral bases[END_REF].

Principles of efficient communication play an increasing role in our understanding of the evolution of word meanings, exemplified by the influential work of [START_REF] Regier | Word meanings across languages support efficient communication[END_REF][START_REF] Kemp | Semantic typology and efficient communication[END_REF][START_REF] Zaslavsky | Efficient compression in color naming and its evolution[END_REF]. The idea is that perhaps lexica are optimized to balance (i) informativeness-that is, how well words allow us to make communicatively relevant distinctions about states of the world; against (ii) complexity-that is, how well the system of meaning distinctions represented by the lexicon can be mentally represented and learned. In one influential example, it is shown that the kinship systems of all the world's languages lie near the Pareto frontier, or the range of optimal possible tradeoffs, between informativeness and complexity [START_REF] Kemp | Kinship categories across languages reflect general communicative principles[END_REF] (Figure 3A). For example, in some languages, such as Swedish, there are unique words for all 4 grandparents. While this improves the kinship system's ability to uniquely identify people by removing the linguistic ambiguity of "grandmother" and "grandfather" (which could refer either to the maternal or paternal side), it comes at the cost of increased complexity. According to this analysis, the kinship systems of human languages could not be improved in terms of communicative usefulness without increasing complexity, nor made simpler without incurring communicative cost.

A similar idea has also been applied to the domain of color words. It is well known that color term inventories vary a great deal across languages, from as few as two or three (corresponding to English black, white, and red) to as many as 12 that everyone in the culture knows, as in many modern industrialized communities today [START_REF] Berlin | Basic color terms: Their university and evolution[END_REF][START_REF] Kay | The linguistic significance of the meanings of basic color terms[END_REF][START_REF] Lucy | The linguistics of "color[END_REF][START_REF] Jameson | It's not really red, green, yellow, blue: an inquiry into perceptual color space[END_REF][START_REF] Delwin | Universality of color names[END_REF]. It turns out that the communicativity of the set of color words within a language is partially optimized according the perceptual properties of color [START_REF] Regier | Color naming reflects optimal partitions of color space[END_REF][START_REF] Steels | Coordinating perceptually grounded categories through language: A case study for colour[END_REF][START_REF] Baronchelli | Modeling the emergence of universality in color naming patterns[END_REF], as defined by the CIELAB color space [START_REF] David | Color appearance and color difference specification[END_REF], across the World Color Survey, a large database of how people name colors from all over the world. The idea here is that when culture necessitates the use of a new color term, both the previous and the new color word partition are driven by the shape of the perceptual color space. This approach has the advantage of explaining why unrelated languages seem to get similar color term partitions. Such an analysis seems ripe for other sense domains, when adequate domain models can be figured out [e.g., [START_REF] Majid | Hunter-gatherer olfaction is special[END_REF][START_REF] Majid | Differential coding of perception in the world's languages[END_REF]].

An alternative motivation for the set of color words in a language is usefulness in describing the objects in the world [START_REF] Delwin | World color survey color naming reveals universal motifs and their within-language diversity[END_REF][START_REF] Gibson | Color naming across languages reflects color use[END_REF]. To evaluate this idea, one can first compute a color score associated with each color chip in an array of colors, which reflects how easy it is to communicate that color to a listener, using a word. Consider an arbitrary color, say a light blue. And now consider a word that one might use to label this color, say "blue". We can compute a color score associated with this color and label as a product of of two factors: (a) a production factor: how likely a person would be to use that label for that color (if it's a really good blue, then that probability may be greater than .5); and a comprehension factor: how difficult it would be for a listener to pick the correct physical color from the set of choices, given the label "blue". If there are a lot of other colors that might also be labeled with the same word, then this difficulty is relatively high. Formally, this difficulty is computed as the surprisal of the color, given the word. We can then compute the average color score for a color over all words, by summing all the scores for each label for that color. The resulting average color score is the optimal number of yes-no guesses it takes a listener to guess which chip the speaker meant: the number of bits it takes to convey that information. Given this simple information-theoretic score, it turns out that all languages convey warm colors (yellow, red, orange, brown) using fewer bits of information than cool colors (blue, green) (Figure 3B) [START_REF] Gibson | Color naming across languages reflects color use[END_REF]. Furthermore, objects in the world tend to be warm-colored, whereas backgrounds tend to be cool-colored (blues and greens) (Figure 3C). This suggests a causal explanation for the warm/cool ease of communication generalization that we observe across languages: people invent words to describe objects, not backgrounds. So perhaps color words are introduced into the space according to their usefulness in discriminating among objects [cf. 59].

Under the usefulness hypothesis, all languages have the same underlying perceptual color structure. What differs is the extent to which these perceptual categories are useful in a culture, which can evolve over time, depending on what needs to be labeled. Evidence for this idea comes from analyses of Hadza [START_REF] Delwin T Lindsey | Hunter-gatherer color naming provides new insight into the evolution of color terms[END_REF] and Tsimane' [START_REF] Gibson | Color naming across languages reflects color use[END_REF], both of which have similar color term structure to industrialized languages, despite having relatively low total information in the World Color Survey [START_REF] Kay | The world color survey[END_REF][START_REF] Kay | Color appearance and the emergence and evolution of basic color lexicons[END_REF].

Syntax

Syntax is the way words are combined compositionally to form sentences. The most general notation for describing syntactic dependencies among words is called dependency syntax [START_REF] Richard | English word grammar[END_REF]. Dependency syntax considers only the order in which individual words must be combined together in order to derive the meaning of a sentence. For example, in Example (1) below, the adjective "red" modifies the noun "car", not the noun "woman", and this is indicated by drawing a dependency link from the dependent, "car", to its head, "red". Headship is a key element of all contemporary syntactic frameworks [START_REF] Pollard | Head-Driven Phrase Structure Grammar[END_REF][START_REF] Kaplan | Lexical-Functional Grammar: A formal system for grammatical representation[END_REF][START_REF] Chomsky | The Minimalist Program[END_REF] and can (for the most part) be determined in a relatively theory-neutral way [START_REF]Heads in Grammatical Theory[END_REF], rendering the work described here robust to a range of particular assumptions about finer details of syntactic structure.

The woman saw the red car ROOT Language understanding requires recovering the dependency structure given the words of a sentence. To study efficiency in syntax, researchers ask whether the word order and morphology of languages are optimized to make this process easy and accurate.

Order of subject, verb, and object. One main focus for efficiency-based explanations of word order has been the order of subject, verb, and object. For example, in the sentence "Sam ate oranges", the subject is "Sam", the verb is "ate", and the object is "oranges". English word order is Subject-Verb-Object (SVO); across languages, the most common orders are (in order) SOV, SVO, and VSO, a distant third [START_REF] Matthew | SVO languages and the OV:VO typology[END_REF]. There are a number of proposed explanations for the prevalence of SOV and SVO word order: some based in dependency locality (see below) [START_REF] Ferrer I Cancho | The placement of the head that minimizes online memory[END_REF], and some based in the theory of Uniform Information Density: that the information content of an utterance per unit time should be roughly constant [START_REF] Fenk | Konstanz im Kurzzeitgedächtnis-Konstanz im sprachlichen Informationsfluß[END_REF][START_REF] Genzel | Entropy rate constancy in text[END_REF][START_REF] Levy | Speakers optimize information density through syntactic reduction[END_REF]. Based on co-occurrence statistics for a small set of subjects, verbs, and objects, [START_REF] Maurits | Why are some word orders more common than others? a Uniform Information Density account[END_REF] argue that SVO order produces the most uniform information profile, followed by SOV and VSO.

Another theory for the distribution of SOV and SVO order arises from principles of robust sentence understanding through a noisy communicative channel [START_REF] Levy | A noisy-channel model of rational human sentence comprehension under uncertain input[END_REF][START_REF] Levy | Eye movement evidence that readers maintain and act on uncertainty about past linguistic input[END_REF][START_REF] Gibson | Rational integration of noisy evidence and prior semantic expectations in sentence interpretation[END_REF]. In this noisy-channel theory, a transmitter sends a message of the form SVO or SOV, and then the receiver might receive a corrupted version where a word has been deleted. Under these circumstances, SVO order more robustly communicates which noun is the subject and which is the object when these are confusable [START_REF] Gibson | A noisy-channel account of crosslinguistic word-order variation[END_REF][START_REF] Futrell | Cross-linguistic gestures reflect typological universals: A subject-initial, verb-final bias in speakers of diverse languages[END_REF]. However, there is evidence that SOV order is favored by more general, still not fully understood cognitive biases: it is the preferred order in emergent sign languages and ad-hoc gestural communication [START_REF] Goldin-Meadow | The natural order of events: How speakers of different languages represent events nonverbally[END_REF][START_REF] Schouwstra | The semantic origins of word order[END_REF], although these languages and communication systems are typically not strictly SOV. The noisy-channel theory suggests that languages with SOV order must use some other strategy to robustly communicate subject and object: in fact these languages usually have morphological case-marking distinguishing subject from object [START_REF] Matthew | Case distinctions, rich verb agreement, and word order type (comments on Hawkins' paper)[END_REF], and in ad-hoc gestural communication the preferred order switches to SVO when subject and object are confusable [START_REF] Gibson | A noisy-channel account of crosslinguistic word-order variation[END_REF].

Dependency locality. Dependency locality is a theory that the linear distance between words linked in dependencies (dependency length) should be as short as possible [START_REF] Rijkhoff | Explaining word order in the noun phrase[END_REF][START_REF] Hawkins | A performance theory of order and constituency[END_REF][START_REF] Gibson | Linguistic complexity: Locality of syntactic dependencies[END_REF][START_REF] Wasow | Postverbal behavior[END_REF][START_REF] Ferrer I Cancho | Euclidean distance between syntactically linked words[END_REF][START_REF] Liu | Dependency distance as a metric of language comprehension difficulty[END_REF][START_REF] Gildea | Do grammars minimize dependency length?[END_REF][START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF][START_REF] Liu | Dependency distance: a new perspective on syntactic patterns in natural languages[END_REF][START_REF] Temperley | Minimizing syntactic dependency lengths: Typological/cognitive universal?[END_REF]. Minimizing dependency length increases processing efficiency because it minimizes the difficulty associated with working memory retrievals during incremental production and comprehension. From the perspective of communicative efficiency, dependency length is a component of the effort involved in sending and receiving utterances, beyond utterance length. For example, in Figure 4A, sentence 4 is notably awkward-sounding, in part because of the long dependency between "threw" and "out". Such long dependencies cause measurable online comprehension difficulty [START_REF] Grodner | Consequences of the serial nature of linguistic input for sentenial complexity[END_REF][START_REF] Bartek | In search of on-line locality effects in sentence comprehension[END_REF].

Dependency locality provides a unified explanation for several word order phenomena. First, it explains the harmonic word order correlations, a set of correlated word order patterns across languages (for example, languages where numerals precede nouns usually also have adjectives preceding nouns) [START_REF] Joseph | Some universals of grammar with particular reference to the order of meaningful elements[END_REF][START_REF] Vennemann | Theoretical word order studies: results and problems[END_REF][START_REF] Matthew | The Greenbergian word order correlations[END_REF][START_REF] Hawkins | A performance theory of order and constituency[END_REF], in addition to certain exceptions to these correlations [START_REF] Gildea | Do grammars minimize dependency length?[END_REF]. Second, it explains the general preference to place short constituents before long constituents in certain languages such as English [START_REF] Stallings | Phrasal ordering constraints in sentence production: Phrase length and verb disposition in heavy-NP shift[END_REF][START_REF] Wasow | Postverbal behavior[END_REF], and the reverse preference in other languages such as Japanese [START_REF] Yamashita | Long before short" preference in the production of a head-final language[END_REF]. Third, it possibly explains why dependency trees rarely have crossing links [START_REF] Ferrer I Cancho | Why do syntactic links not cross? EPL[END_REF], which correspond to deviations from context-free syntax [START_REF] Kuhlmann | Mildly non-projective dependency grammar[END_REF].

Numerous corpus studies provide evidence for dependency locality as a pressure on word order [START_REF] Wasow | Postverbal behavior[END_REF][START_REF] Liu | Dependency distance as a metric of language comprehension difficulty[END_REF][START_REF] Park | Minimal-length linearizations for mildly context-sensitive dependency trees[END_REF][START_REF] Gildea | Do grammars minimize dependency length?[END_REF][START_REF] Rajkumar | Investigating locality effects and surprisal in written English syntactic choice phenomena[END_REF]. For example, [START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF] show that dependency length in hand-parsed corpora of 37 languages is minimized compared to several random baselines instantiating other independently-motivated constraints on word order (see Figure 4B). A dependency locality bias also emerges in artificial language learning [START_REF] Fedzechkina | Human information processing shapes language change[END_REF], suggesting it may influence languages causally via learning biases (see also [START_REF] Culbertson | Learning biases predict a word order universal[END_REF], who find a learning bias in favor of harmonic word orders).

A tight integration of dependency locality with information theory is possible via recent developments in models of online comprehension difficulty [START_REF] Hale | A probabilistic earley parser as a psycholinguistic model[END_REF][START_REF] Levy | Expectation-based syntactic comprehension[END_REF][START_REF] Levy | Integrating surprisal and uncertain-input models in online sentence comprehension: formal techniques and empirical results[END_REF][START_REF] Nathaniel | The effect of word predictability on reading time is logarithmic[END_REF]. Under the assumption that comprehenders' memory for linguistic context is noisy, a principle of information locality can be derived, such that all words with high mutual information should be close for processing efficiency, where mutual information is a measure of how strongly the distribution of two words is constrained [START_REF] Futrell | Noisy-context surprisal as a human sentence processing cost model[END_REF]. Under this hypothesis, linguistic heads and dependents are word pairs that have especially high mutual information, meaning that dependency locality becomes a special case of information locality. Information locality extends the theoretical reach of dependency locality from strictly syntactic dependencies to all statistical dependencies. Information locality might thus potentially explain word order phenomena that go beyond traditional dependency locality, such as preferences in the relative order of adjectives [START_REF] Scontras | Subjectivity predicts adjective ordering preferences[END_REF][START_REF] Hahn | An information-theoretic explanation of adjective ordering preferences[END_REF].

Morphology

Morphology refers to the ways in which word forms change in order to express gradations in meaning: for example, English marks plural number on nouns by adding an "-s". Across languages, morphological marking indicates dimensions of meaning such as number, gender, the person of the subject and object of verbs, and more generally the syntactic relationships among words.

Tradeoff of morphology and fixed word order. Languages adopt two basic strategies to indicate syntactic dependency structure: it can be encoded in fixed word order-as in English-or in morphology, in which words are marked with morphemes which encode their dependency relations to other words. Such marking can take the form of case marking or agreement [START_REF] Nichols | Head-marking and dependent-marking grammar[END_REF][START_REF] Greville | Agreement[END_REF]. Fixed word order and morphology are two means by which a latent tree structure can be encoded into a sequence of words.

A basic efficiency prediction is that when a language has fixed word order, it does not need morphology, because dependency-marking morphemes would be redundant. Furthermore, if a language has morphology, then it does not need fixed word order with respect to dependency structure: word order can instead be repurposed to convey other aspects of meaning, such as information structure [START_REF] Arnold | Information structure: linguistic, cognitive, and processing approaches[END_REF]. Thus morphological marking should trade off with fixed word order. Such a trade-off has long been described qualitatively in the linguistic literature [START_REF] Sapir | Language: An introduction to the study of speech[END_REF][START_REF] Kiparsky | The rise of positional licensing[END_REF][START_REF] Mcfadden | On morphological case and word-order freedom[END_REF] and has recently been quantified in corpus studies: an information-theoretic measure of word-order freedom correlates negatively with the presence of morphological marking in dependency-parsed corpora for certain dependency structures [START_REF] Futrell | Quantifying word order freedom in dependency corpora[END_REF], and more generally there is a tradeoff of word-order and word-internal information content [START_REF] Koplenig | The statistical trade-off between word order and word structure-large-scale evidence for the principle of least effort[END_REF]. Such a tradeoff also emerges in artificial language learning [START_REF] Fedzechkina | Language learners restructure their input to facilitate efficient communication[END_REF].

One possible factor influencing why some languages opt for more rigid word order as opposed to morphology is population structure: languages spoken by populations with more second language speakers tend to disprefer morphology [START_REF] Lupyan | Language structure is partly determined by social structure[END_REF][START_REF] Bentz | Learning pressures reduce morphological complexity: Linking corpus, computational and experimental evidence[END_REF], possibly because morphological rules are harder for second language speakers to learn [START_REF] Bentz | Learning pressures reduce morphological complexity: Linking corpus, computational and experimental evidence[END_REF].

Redundancy in morphology.

One puzzling property of languages from the perspective of efficiency is that they often go out of their way to redundantly mark apparently irrelevant properties of words, such as gender marking for inanimate nouns [121]. In many cases, the gender marking assigned to nouns is nearly arbitrary. More generally, noun classification systems divide nouns into potentially dozens of arbitrary categories which must be marked. How does such an arbitrary and difficult-to-learn aspect of language fit in with the idea that languages are shaped by efficiency?

A recent line of research has proposed that redundant marking of features such as gender may ease language processing effort. Among word classes and across languages, the part of speech associated with most difficulty is nouns [START_REF] Seifart | Nouns slow down speech across structurally and culturally diverse languages[END_REF]. Since language processing effort is associated with predictability [START_REF] Hale | A probabilistic earley parser as a psycholinguistic model[END_REF][START_REF] Levy | Expectation-based syntactic comprehension[END_REF], an element that makes nouns more predictable in context would make them easier to produce and comprehend. Grammatical gender marking serves exactly this purpose: knowing ahead of time whether a noun is "masculine" or "feminine" reduces uncertainty about lexical identity [START_REF] Futrell | German noun class as a nominal protection device[END_REF][START_REF] Dye | A functional theory of gender paradigms[END_REF]. In languages without gender marking, this same role may be filled by redundant prenominal adjectives [START_REF] Dye | Alternative solutions to a language design problem: The role of adjectives and gender marking in efficient communication[END_REF]. More generally, such redundant marking may play a role similar to parity bits in information-theoretic codes: they provide redundancy that makes the linguistic signal robust to noise.

Intriguingly, from the communicative perspective, the arbitrariness of gender systems could be a feature, not a bug. It has been argued that if gender markers were not arbitrary-if they were totally predictable-they would not provide unique information about nouns [START_REF] Dye | A functional theory of gender paradigms[END_REF]. From the purely communicative perspective, the most useful gender system might thus be an entirely random mapping of nouns to genders-but an entirely arbitrary mapping of nouns to genders would be complex to learn and deploy, suggesting that a complexity-efficiency tradeoff may exist in gender systems. Pending further investigation into this and related hypotheses, the possibility that communicative efficiency considerations play a causal role in shaping the mapping from noun to gender remains speculative.

How Learnability interacts with Efficiency

Traditional theories of language, especially in the generative tradition, have emphasized the problem of learnability: the idea that certain languages may be impossible to learn by children without strong innate principles [START_REF] Gold | Language identification in the limit[END_REF]. Such theories hypothesized that universals arise due to these innate principles, [START_REF] Chomsky | Reflections on language[END_REF], but had difficulty explaining and predicting the empirical range of variation found in languages [START_REF] Haspelmath | Parametric versus functional explanations of syntactic universals[END_REF][START_REF] Evans | The myth of language universals: Language diversity and its importance for cognitive science[END_REF]. More recent arguments based on language learnability have focused on the idea that linguistic systems can be differentially complex, with the more complex systems being harder to learn (but not impossible) [START_REF] Ray | A formal theory of inductive inference[END_REF][START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF]. Then universals can be explained under the assumption that simpler systems are preferred [START_REF] Smith | Language learning, language use and the evolution of linguistic variation[END_REF][START_REF] Kemp | Semantic typology and efficient communication[END_REF].

The efficiency perspective on learnability is somewhat different from the traditional perspective in formal linguistics in terms of Universal Grammar (UG) [START_REF] Chomsky | Approaching UG from below[END_REF]. In typical UG theories, certain languages are learnable because they are compatible with UG, and languages incompatible with UG are unlearnable. More recent work has taken a graded approach to learnability: within the space of languages that can be learned at all, we can ask whether certain languages might be harder or easier to learn. Essentially, a language that is more complex is harder to learn than one which is simpler, a general property of algorithmic and statistical theories of learning [START_REF] Chater | Simplicity: A unifying principle in cognitive science[END_REF][START_REF] Chater | Ideal learning' of natural language: Positive results about learning from positive evidence[END_REF][START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF].

The emergence of compositionality in language transmission

An even more basic question than the explanation of lexical and syntactic universals is the origin of linguistic structure itself. For example, in the section on syntactic efficiency, we discussed how languages use word order and morphology to indicate syntactic dependency trees, but a deeper question is why sentences consist of words that can be arranged in dependency trees in the first place.

A potential solution to this problem lies in the classic learning problem for language: how learners can acquire facility with an infinitely expressive system mapping forms to meanings from limited exposure? For the most frequently intended meanings, learners encounter sufficient learning instances to support a holistic, memorized relationship between utterance form and meaning, such as the English greeting "Hello". But in light of the complete repertoire of utterance meanings that a speaker may need to convey or understand, the totality of any native speaker's linguistic experience is extraordinarily sparse. For our species, the solution to this problem is that language is compositional: smaller meaningful forms can be put together into a novel, larger form whose meaning is a predictable function of its parts [START_REF] Charles | The origin of speech[END_REF]. By mastering the basic units and composition functions of a compositional system through simplicity principles [START_REF] Ray | A formal theory of inductive inference[END_REF][START_REF] Chater | Ideal learning' of natural language: Positive results about learning from positive evidence[END_REF], a learner can acquire an infinitely expressive set of form-meaning mappings. Humans might have a strong inductive bias constraining language learning to some set of compositional systems, which may have emerged as a side effect of multiple evolutionary events in our lineage [START_REF] Berwick | A bird's eye view of human language evolution[END_REF] or which may have been selected for directly [START_REF] Pinker | Natural language and natural selection[END_REF]. An alternative, usage-based possibility is that languages might have become compositional through diachronic selection from the transmission bottleneck in their cultural evolution [START_REF] Kirby | Syntax without natural selection[END_REF][START_REF] Kirby | Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language[END_REF][START_REF] Kirby | Compression and communication in the cultural evolution of linguistic structure[END_REF]. Even if a non-compositional system were perfectly human-learnable from sufficient evidence, it could not survive over generations, due to input sparsity for any individual learner.

Learnability beyond compositionality: Iconicity & Systematicity

Since the advent of Saussurean structural linguistics [START_REF] De | Course in general linguistics[END_REF], the relationship between a word's form and its meaning is generally seen to be arbitrary [START_REF] Charles | The origin of speech[END_REF]. The world's languages offer many examples of arbitrariness: for instance, English speakers use the sound sequence "shoe" to label footwear, while French speakers use the same sequence of sounds to label cabbage. This arbitrariness of the sign frees speakers to easily coin new words to suit communicative needs. But if wordforms themselves give no clues as to meaning, it poses an acquisition challenge: any given caregiver utterance of "shoe", for example, is compatible with a vast range of plausible intended meanings from among which an infant learner would have to guess [START_REF] Van Orman Quine | Word and object[END_REF].

However, accumulating evidence [START_REF] Perniss | Iconicity as a general property of language: evidence from spoken and signed languages[END_REF][START_REF] Dingemanse | Arbitrariness, iconicity, and systematicity in language[END_REF], both experimental [START_REF] Nuckolls | The case for sound symbolism[END_REF][START_REF] Benjamin K Bergen | The psychological reality of phonaesthemes[END_REF][START_REF] Reilly | Non-arbitrariness in mapping word form to meaning: Cross-linguistic formal markers of word concreteness[END_REF] and computational [START_REF] Monaghan | How arbitrary is language? Phil[END_REF][START_REF] Damián E Blasi | Sound-meaning association biases evidenced across thousands of languages[END_REF][START_REF] Gutiérrez | Finding non-arbitrary form-meaning systematicity using string-metric learning for kernel regression[END_REF][START_REF] Dautriche | Words cluster phonetically beyond phonotactic regularities[END_REF][START_REF] Dautriche | Wordform similarity increases with semantic similarity: An analysis of 100 languages[END_REF][START_REF] Liu | Discovering phonesthemes with sparse regularization[END_REF], suggests less arbitrariness in the lexicons of both spoken and signed languages [START_REF] Strickland | Event representations constrain the structure of language: Sign language as a window into universally accessible linguistic biases[END_REF] than previously appreciated. For example, it has been shown that the lexicons of natural languages show significantly more phonological clustering over and above phonotactic and morphological regularities [START_REF] Dautriche | Words cluster phonetically beyond phonotactic regularities[END_REF] (Figure 5). That is, given the constraints imposed by their phonotactic rules, the lexicons of natural languages use a smaller portion of the phonological space available to them. The clustered nature of the lexicon may result from a non-arbitrary relationship between semantics and phonology. Non-arbitrariness can involve iconicity, whereby certain acoustic or visual characteristics of sounds or signs are intrinsically good matches to meanings for the human mind (e.g., certain vowel contrasts corresponding to contrasts in magnitude). Non-arbitrariness can also involve language-specific systematicity, such as correlations between sound and grammatical category (in English, nouns' stressed syllables tend to contain back vowels like "school", whereas verbs' stressed syllables tend to contain front vowels like "meet" [START_REF] Michael | Using sound to solve syntactic problems: The role of phonology in grammatical category assignments[END_REF]), or between sound and meaning (in English, words beginning with the phonaestheme "gl-", like "glimmer" and "glow" often relate to light; words beginning with "sn-", like "sneeze" or "sniff", often relate to the nose [START_REF] Benjamin K Bergen | The psychological reality of phonaesthemes[END_REF]).

Advances in computing power, natural language processing methods, and statistical analysis have made possible large-scale quantitative analysis of the lexicon to reveal the degree and nature of clustering between form and meaning below the level of the morpheme. For example, positive correlations have been found between word-pair phonological distances and vector space-representation semantic distances significantly above what would be expected under random wordform assignment, in a variety of languages [START_REF] Dautriche | Words cluster phonetically beyond phonotactic regularities[END_REF]. Other work using nonparametric regression techniques has recovered the best-known English phonaesthemes like "gl-" and "sn-" [START_REF] Gutiérrez | Finding non-arbitrary form-meaning systematicity using string-metric learning for kernel regression[END_REF]. These form-meaning regularities exist in a wide range of typologically unrelated languages [START_REF] Damián E Blasi | Sound-meaning association biases evidenced across thousands of languages[END_REF][START_REF] Dautriche | Wordform similarity increases with semantic similarity: An analysis of 100 languages[END_REF] over and above what would be expected by chance [START_REF] Monaghan | How arbitrary is language? Phil[END_REF] suggesting a fundamental drive for phonological and semantic clustering in the lexicon.

Non-arbitrariness may help learners bootstrap their way into language [START_REF] Imai | The sound symbolism bootstrapping hypothesis for language acquisition and language evolution[END_REF]. Consistent with that hypothesis, corpus analyses have demonstrated that the first words acquired by children display more non-arbitrariness than later acquired words [START_REF] Laing | A phonological analysis of onomatopoeia in early word production[END_REF][START_REF] Monaghan | How arbitrary is language? Phil[END_REF][START_REF] Lynn K Perry | Iconicity in English and Spanish and its relation to lexical category and age of acquisition[END_REF], suggesting that non-arbitrariness plays a crucial role in early language acquisition. Experimental studies have also contributed to the evidence that non-arbitrariness benefits learning: Non-arbitrariness helps to bootstrap the acquisition of individual words at the onset of vocabulary development [START_REF] Brand | The changing role of sound-symbolism for small versus large vocabularies[END_REF] and, as the vocabulary grows, aids learning broad categorical distinctions such as nouns vs. verbs, and supports categorical generalization to novel words [START_REF] Imai | Sound symbolism facilitates early verb learning[END_REF][START_REF] Stanka A Fitneva | From sound to syntax: Phonological constraints on children's lexical categorization of new words[END_REF][START_REF] Brand | The changing role of sound-symbolism for small versus large vocabularies[END_REF].

If non-arbitrariness in the lexicon facilitates learning, then learning might in turn shape the structure of the lexicon. This hypothesis is supported by experiments on language evolution in the laboratory [e.g., 137], where arbitrary signals can become systematic after repeated generations of language transmission [START_REF] Silvey | Word meanings evolve to selectively preserve distinctions on salient dimensions[END_REF][START_REF] Kirby | Compression and communication in the cultural evolution of linguistic structure[END_REF][START_REF] Verhoef | Emergence of systematic iconicity: Transmission, interaction and analogy[END_REF]. As language learners learn the meanings and the functions of words, arbitrary and non-arbitrary mappings each will bring their own selective advantages and disadvantages [START_REF] Monaghan | How arbitrary is language? Phil[END_REF]. Over generations of learners, such advantages and disadvantages will shape vocabulary structure, influencing the presence and the distribution of (non-)arbitrary form-meaning mappings within and across languages.

Challenges for the Efficiency Approach

There are many challenges for the efficiency-based approach to explaining language structure, both methodological and empirical. These challenges primarily have to do with sharpening the theory to extend its empirical reach while maintaining consistent notions of efficiency and constraints on efficiency.

Specification and measurement of complexity. While communicative

efficiency can be quantified using information-theoretic concepts, there is less agreement on how to characterize the complexity/learnability of a language. In particular, the complexity of a language may be measured as the length of its description in some meta-language, e.g. as in [START_REF] Kemp | Kinship categories across languages reflect general communicative principles[END_REF], but this measure depends on the particular description meta-language used. While complexity estimates of this form are to some extent independent of the meta-language [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF], they may still vary by large magnitudes. The precise specification of the proper complexity metric will be necessary to further formalize and make precise the relationship between learnability, compositionality, systematicity, and iconicity.

Specification of null hypotheses.

To show that an aspect of language is efficient in terms of communication and learnability, it is often necessary to contrast the observed language data with some counterfactual baseline indicating what a language might look like without a pressure for efficiency. For example, in an analysis of kinship systems, natural language kinship systems are compared with an enumeration of logically possible kinship systems [START_REF] Kemp | Kinship categories across languages reflect general communicative principles[END_REF], and in an analysis of syntactic dependencies, dependency lengths in real sentences are compared to dependency lengths in randomly reordered sentences [START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF]. Specification of these counterfactual baselines is often the most challenging part of making an efficiency claim. Consider for example if we wanted to claim that a particular utterance is the most efficient way to express a certain message in some context: to make this claim most rigorously, we would have to compare the utterance against all the other things a speaker might have said, given all the degrees of freedom available to the speaker, including pragmatics. The generation of such baseline utterances would be enormously complex. Currently there is no method of generating baseline utterances and languages which is general and satisfactory across all cases.

Measurement of information-theoretic quantities.

To quantify communicative efficiency, the information content / entropy, etc., of words, sentences, and messages needs to be estimated. These values are estimated by fitting probability distributions from corpora. However, it is difficult to get reliable estimates of these information-theoretic quantities without very large datasets [START_REF] Paninski | Estimation of entropy and mutual information[END_REF][START_REF] Bentz | The entropy of words-Learnability and expressivity across more than 1000 languages[END_REF]. For example, [START_REF] Steven T Piantadosi | Word lengths are optimized for efficient communication[END_REF] use web-scale n-gram corpora provided by Google. The dependence on large datasets makes empirical studies of many languages difficult and confines many studies to modern English, for which the most data is available.

Specification of communicative utility. The information-theoretic notion

of efficiency has to do with how well a language communicates arbitrary messages. However, in real natural language communication, there are other factors influencing the utility of an utterance. For example, languages are often embedded in societies that dictate taboo words: words which must be avoided lest the speaker incur social repercussions. The avoidance of such words must figure into the calculation of the utility of an utterance: an utterance containing a taboo word will be avoided even if it is otherwise efficient. It is currently unclear whether such factors can be expressed as part of general communicative efficiency as described above, or if they require additional terms to be added to the equations describing communicative utility. Nor is it clear whether such phenomena have an explanation based in efficiency.

Differences across populations and cultures.

Languages around the world vary in sound inventories, grammatical rules, and the organization of the lexicon. The populations in which these languages are spoken vary in many other ways, too: from social organization to technology to culture-specific values. These latter differences can change the distribution of communicative needs: in some populations it will more often be important to convey a given type of meaning than in others. These differences in communicative needs rapidly affect the lexicon-new technologies immediately lead to new words to name and describe them, for example-and in some cases may be reflected in specialized grammaticalized subsystems within the language, such as the grammar of honorific expressions in Japanese [START_REF] Mizutani | Taiguu hyougen no sikumi (structure of honorific expressions)[END_REF]. Differences in factors such as population structure [START_REF] Lupyan | Language structure is partly determined by social structure[END_REF] and prevalence of non-native speakers [START_REF] Bentz | Learning pressures reduce morphological complexity: Linking corpus, computational and experimental evidence[END_REF] may affect the amount of common knowledge shared among speakers, which might in turn affect the linguistic encodings of intended speaker meanings required to ensure accurate communication. But the extent to which these considerations can lead to explanatory theories of cross-linguistic differences remains unclear.

Pathways of historical change. The variation among languages across the world suggests a diversity of ways that a language can be organized that offers a good solution to the language user and learner's problem of efficiency-complexity tradeoff. Major typological features of languages can change rapidly, but not all changes are equally likely. For example, a language's preferred ordering of subject, object, and verb can change completely in the span of a few hundred years, as happened in early English [START_REF] Brady | A stochastic optimality theory approach to syntactic change[END_REF], but not all changes among the six logically possible orderings are equally likely [START_REF] Gell-Mann | The origin and evolution of word order[END_REF][START_REF] Maurits | Tracing the roots of syntax with bayesian phylogenetics[END_REF]. Models of historical language change are crucial to an explanatory theory of the variations seen in linguistic structure [START_REF] Thomas | Language evolution by iterated learning with bayesian agents[END_REF][START_REF] Daniel | Building social cognitive models of language change[END_REF][START_REF] Mitchell G Newberry | Detecting evolutionary forces in language change[END_REF], but our understanding of the constraints on these models remains limited.

Concluding remarks

The rich collection of studies reviewed here reveals numerous linguistic phenomena which are driven by considerations of efficiency, balancing efficient use and complexity. These results highlight that theories of the evolutionary and ontogenetic origins of language systems are likely to be most productively constrained by the social and communicative function of language.

Interestingly, many of the results have applied tools from information theory-which assumes an idealized version of communication-in order to understand language. One of the most productive directions for ongoing work will be continuing to connect information theory to empirically testable cognitive processes: after all, information is quantified via probabilistic expectations, and so the psychological capacity for and limitations to computing these expectations will tightly constrain our theories. These constraints can only be discovered by further work to understand the mechanisms of language processing. Thus, a compelling future for language research lies in connecting linguistics, information theory, and cognitive psychology in order to provide formalized accounts of how language communicates information, in comprehension and learning alike.

Outstanding Questions

When communicative efficiency and learnability come into conflict, what generalizations can be made about how this conflict is resolved? What features and structures in language reflect such conflict, and how?

To what extent can principles of efficient communication and learnability help explain finer-grained grammatical phenomena investigated in generative linguistics, such as syntactic island?

Can the cognitive constraints shaping communicative efficiency and learnability be connected to and grounded in neural principles of human brain organization?

To what extent does variability within human populations, including individual differences in language processing capabilities and social dynamics, also shape language structure? Can principles of efficiency in usage and learnability also help us understand symbolic systems used by humans other than natural language, such as gesture, programming languages, and mathematics?

In usage-based theories, the distribution of messages that people want to communicate plays a crucial causal role in influencing language structure. But to what extent does a language's structure in turn influence the distribution of messages that its speakers want to communicate?

Box 1: Methods to investigate cross-linguistic generalizations

The development and testing of efficiency-based hypothesis makes heavy use of analysis of corpora [START_REF] Steven T Piantadosi | Word lengths are optimized for efficient communication[END_REF][START_REF] Dautriche | Wordform similarity increases with semantic similarity: An analysis of 100 languages[END_REF][START_REF] Monaghan | How arbitrary is language? Phil[END_REF][START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF][START_REF] Levy | Speakers optimize information density through syntactic reduction[END_REF]-collection of linguistic data, typically collected from naturalistic sources, such as books, newspapers, websites, radio or television broadcasts, or spontaneous conversations recorded with the consent of the participants. Naturalistic sources play a key role because efficiency in communication and learning must be evaluated with respect to the distribution of messages that speakers intend to convey to one another, and with respect to the distribution of linguistic forms to which a comprehender or learner is exposed. Corpora must often be manually or automatically annotated for additional linguistic structure, such as word boundaries in languages that are not tokenized, morphological structure within words, and syntactic trees within sentences. Advances in natural language processing have played a crucial enabling role in corpus-based work. In work on the partitioning of semantic spaces in the lexicon, electronic dictionaries and similar databases amenable to computational analysis have played a parallel role [START_REF] Kay | The world color survey[END_REF][START_REF] Kemp | Kinship categories across languages reflect general communicative principles[END_REF][START_REF] Gibson | Color naming across languages reflects color use[END_REF][START_REF] Zaslavsky | Efficient compression in color naming and its evolution[END_REF].

Achieving a complete understanding of the range and character of linguistic structure also involves deep analysis of single languages [START_REF] Chomsky | Reflections on language[END_REF][START_REF] Kaplan | Lexical-Functional Grammar: A formal system for grammatical representation[END_REF][START_REF] Bresnan | Locative inversion in Chiche ŵa: a case study of factorization in grammar[END_REF][START_REF] Talmy | How language structures space[END_REF][START_REF] Pollard | Head-Driven Phrase Structure Grammar[END_REF]. Many languages have structures which are highly creative, but also extremely infrequent, and therefore difficult to observe in natural corpora. For example, the sentence "Onto the table jumped the cat" involves locative inversion, in which the positions of the subject "the cat" and the locative phrase "onto the table" are swapped relative to ordinary English word order. This construction is quite rare in everyday speech and writing, but it is perfectly understandable by fluent English speakers, and native speakers command a sophisticated tacit understanding of its conditions of felicitous use. This construction appears in many languages, in variable yet constrained forms [START_REF] Bresnan | Locative inversion in Chiche ŵa: a case study of factorization in grammar[END_REF]. Detailed study of such structures is a central focus of generative linguistics. Just as rare neurological conditions may reveal unexpected properties of how the brain is organized, these infrequent linguistic phenomena can give considerable insight into the computational properties of human language.

Discovering cross-linguistic empirical generalizations and testing hypotheses about universality or relative prevalances of various aspects of language structure often makes use of typological databases [START_REF] Joseph | Some universals of grammar with particular reference to the order of meaningful elements[END_REF][START_REF] Matthew | SVO languages and the OV:VO typology[END_REF]. Some degree of typological information is available for thousands of languages [START_REF]WALS Online[END_REF], but for the vast majority of these languages the available information remains highly limited. A key future methodological direction for language science is to make corpus resources and deep linguistic analyses available for a wider range of languages. Such resources and analysis can play a transformative enabling role in testing and developing theories of language structure based on principles of efficiency [START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF], learnability, and formal parsimony.

Frequently, efficiency-based theories make predictions that can be tested experimentally using the behavioral methods of psychological science [START_REF] Mahowald | Info/information theory: Speakers choose shorter words in predictive contexts[END_REF][START_REF] Grodner | Consequences of the serial nature of linguistic input for sentenial complexity[END_REF]. These methods allow dense data to be collected to help understand structures that are rare in naturalistic use, to deconfound by experimental design factors that are correlated in naturalistic data, and to perform interventions to clarify causal relationships. Experimental studies can also involve artificial languages [START_REF] Fedzechkina | Language learners restructure their input to facilitate efficient communication[END_REF][START_REF] Culbertson | Learning biases predict a word order universal[END_REF] with researcherdesigned grammatical properties to test learnability, the role of the communicative channel, and consequences of iterated transmission [START_REF] Kirby | Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language[END_REF][START_REF] Kirby | Compression and communication in the cultural evolution of linguistic structure[END_REF][START_REF] Silvey | Word meanings evolve to selectively preserve distinctions on salient dimensions[END_REF].

Computational modeling plays an increasingly central role in formalizing and testing efficiency-based theories. Computational models help verify the formal soundness of informally stated theoretical proposals [START_REF] Hale | A probabilistic earley parser as a psycholinguistic model[END_REF][START_REF] Levy | A noisy-channel model of rational human sentence comprehension under uncertain input[END_REF], estimate quantities (such as conditional word probabilities or vector-based word meaning representations) that play key roles in these theories from corpora [START_REF] Steven T Piantadosi | Word lengths are optimized for efficient communication[END_REF][START_REF] Gutiérrez | Finding non-arbitrary form-meaning systematicity using string-metric learning for kernel regression[END_REF][START_REF] Futrell | Noisy-context surprisal as a human sentence processing cost model[END_REF][START_REF] Dautriche | Wordform similarity increases with semantic similarity: An analysis of 100 languages[END_REF], clarify the structural tendencies of human languages by comparing them against counterfactual simulated languages lacking efficiency-based properties [START_REF] Gildea | Do grammars minimize dependency length?[END_REF][START_REF] Monaghan | How arbitrary is language? Phil[END_REF][START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF][START_REF] Dautriche | Wordform similarity increases with semantic similarity: An analysis of 100 languages[END_REF], and gain insight into theoretical dynamics of language change through simulated intergenerational transmission [START_REF] Kirby | Syntax without natural selection[END_REF][START_REF] Kirby | Compression and communication in the cultural evolution of linguistic structure[END_REF].

Box 2: Fundamental Concepts from Information Theory

Information theory is the mathematical theory linking the notions of probability, information, and efficient communication [START_REF] Shannon | A mathematical theory of communications[END_REF][START_REF] Cover | Elements of Information Theory[END_REF].

The fundamental insight of information theory is that the information content of a discrete event x is given by its log inverse probability, or surprisal:

h(x) = log k 1 p(x) . ( 1
)
When the logarithm is taken in base k = 2, then information content is measured in bits; base k = 10 corresponds to units of bans, and the natural logarithm corresponds to units of nats. Information content gives the length of the shortest uniquely decipherable code that can be written for the event x given an alphabet of k distinct letters. Going forward we assume k = 2. Given a random variable X, the entropy of X is the average information content of samples from X:

H[X] = x p(x) log 1 p(x) . ( 2
)
Entropy can be interpreted as the degree of uncertainty about the value X. Entropy is non-negative. Given two random variables X and C in a joint distribution, we can ask how much uncertainty remains about X after an observer learns the value of C. This quantity is conditional entropy:

H[X|C] = x c p(x, c) log 1 p(x|c) . ( 3
)
Conditional entropy has a value between zero and unconditional entropy: 0

≤ H[X|C] ≤ H[X]
for all X and C [START_REF] Cover | Elements of Information Theory[END_REF]. This fact is key for the proof of the utility of ambiguity in [START_REF] Steven T Piantadosi | The communicative function of ambiguity in language[END_REF].

When two random variables X and C predict each other, then intuitively we say that they share information content. The amount of shared information content is given by the mutual information:

I[X : C] = H[X] -H[X|C], (4)
which is the difference between the unconditional entropy of X and the conditional entropy of X given C (or vice versa). Mutual information measures how many bits of information you get about X on average when you learn the value of C. For all X and C, mutual information is non-negative and symmetric in its two arguments:

I[X : C] = I[C : X] ≥ 0. ( 5
)
Communicative success in information theory is defined as the event where the information source's intended message is reconstructed accurately at the destination (see Figure 1). The success criterion may be that the received message is exactly equal to the intended message, or it may be that the reconstructed message is only approximately equal. The study of communicative efficiency under the criterion of approximate equality is called rate-distortion theory, in which rate quantifies the amount of information transferred through the channel, and distortion is a measure of the divergence of the reconstructed message from the intended message.

Glossary

Arbitrariness of the sign is a central property of natural language that was emphasized in early European linguistics, especially by Ferdinand de Saussure.

Channel coding:

The task of choosing a code to enable communication in the presence of noise, according to the characteristics of the channel.

CIELAB color space: is a color space defined by the International Commission on Illumination (CIE) in 1976.

The communicativity color score of a color c, is a score reflecting how easy it is to communicate c given a distribution of words w for c in the language.

Compositional: Two words combine / compose together to make a larger phrase, with a meaning that is composed of the meanings of the parts.

Crossing links: Most dependency links in human languages do not cross other dependency links in the same sentence.

Dependency syntax / trees: Two words are in a dependency relation if they combine together in a phrase to make a larger meaning, such as "the" and "dog", or "dog" and "sleeps", in the sentence "the dog sleeps".

Dependency length: the length in words between two words that are dependent on one another for meaning.

Dependency locality: Words in sentences of all human languages tend to be closer together than any reasonable baseline.

Efficiency: A code is efficient if successful communication can be achieved with minimal effort on average by the sender and receiver, usually by minimizing the message length.

Harmonic word orders:

A set of correlated word order patterns across languages. For example, languages with prepositions will tend to have verbs before their objects; languages with postpositions will tend to have verbs following their objects [START_REF] Joseph | Some universals of grammar with particular reference to the order of meaningful elements[END_REF].

Iconic: An iconic sign is one where its form somehow resembles its meaning. Minimal pair: two words that differ on only one sound / phoneme, such as "dog" vs. "log"; and "dog" vs. "dot".

Information theory: the mathematical theory linking the notions of probability, information, and efficient communication.

Information locality:

The hypothesis that all words with high mutual information should be close, for processing efficiency [START_REF] Futrell | Noisy-context surprisal as a human sentence processing cost model[END_REF].

Language utility:

The overall usefulness of a language, including both communicative efficiency and complexity as factors.

Pareto efficiency: a state of allocation of resources from which it is impossible to reallocate so as to make any one individual or preference criterion better off without making at least one individual or preference criterion worse off.

Pareto frontier: the set of all Pareto efficient allocations. Source coding: The task of choosing a code that makes signals short on average, according to the distribution over messages coming out of the information source.

Surprisal: the negative log probability of a discrete event. The total information of a set of color terms the weighted average of the communicativity of each color in the space.

Uniform information density:

The hypothesis that the information content of an utterance per unit time should be roughly constant [START_REF] Fenk | Konstanz im Kurzzeitgedächtnis-Konstanz im sprachlichen Informationsfluß[END_REF][START_REF] Genzel | Entropy rate constancy in text[END_REF][START_REF] Levy | Speakers optimize information density through syntactic reduction[END_REF] Universal Grammar (UG) is the name given to the Chomksyan hypothesis that certain aspects of language are innate to humans [START_REF] Chomsky | Approaching UG from below[END_REF]. There is no consensus on the details of what these aspects might be.

The World Color Survey is a set of color labels from languages from 110 non-industrialized cultures around the world [START_REF] Kay | The world color survey[END_REF][START_REF] Kay | Color appearance and the emergence and evolution of basic color lexicons[END_REF]. It includes labels from 20-30 participants for each of 330 colors. Solid bars show correlations between word length and a word's predictability according to the two previous words (3-grams). Dashed bars show correlations between word length and word frequency. The predictability correlations are higher than the frequency correlations across languages [START_REF] Steven T Piantadosi | Word lengths are optimized for efficient communication[END_REF].

Figure 3 . Efficient word meanings in kinship and color labels cross-linguistically

A: An analysis by Kemp and Regier [START_REF] Kemp | Kinship categories across languages reflect general communicative principles[END_REF] suggests that human languages lie on or near an optimal frontier of efficient trade-off between informativeness and complexity in the domain of kinship labels. B: Color chips rank-ordered by their average surprisal for all languages in the world color survey, and English, Bolivian-Spanish and Tsimane' (from Gibson et al. [START_REF] Gibson | Color naming across languages reflects color use[END_REF]). Each row shows data for a given language, and the languages are ordered according to their overall communication efficiency. C: The color statistics of objects predicts the average surprisal of colors. Probability of a pixel being in a foreground object of the Microsoft Research Asia (MRSA) database of 20,000 natural images compared with the rank-order of average surprisal of a color, in the Tsimane' language. There is a similar relationship for other languages. A: Syntactic dependency structures for four English sentences. Sentence 4, with a long-distance dependency between the verb "threw" and the particle "out" is more awkward than sentence 3, with a local dependency between these words, thus illustrating dependency locality. B: For each language analyzed, the average dependency length (blue line) is less than a random baseline (red line) as the sentences get longer [START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF]. We show results from a replication of [START_REF] Futrell | Large-scale evidence of dependency length minimization in 37 languages[END_REF] on 50 languages. [START_REF] Dautriche | Words cluster phonetically beyond phonotactic regularities[END_REF] compared the amount of phonological clustering present in the lexicons of 4 languages to a set of simulated lexicons, that acted as a baseline, and that were probabilistically generated based solely on phonotactic and articulatory information. The measure presented here is the total number of minimal pairs (pairs of words that differ on only one phoneme) for each language (red dot) together with the distribution of minimal pairs counts across 30 simulated lexicons (histograms). Vertical black lines represent 95% confidence intervals. For all four languages, the lexicon has significantly more minimal pairs than predicted by a phonotactic baseline. Similar results were found across a variety of phonological clustering measures.

Figure 2 .

 2 Figure 2 . Words' 3-gram predictability correlates with length, cross-linguistically.

Figure 4 .

 4 Figure 4 . Languages minimize syntactic dependency lengths cross-linguistically.

Figure 5 .

 5 Figure 5 . The lexicon has more minimal pairs than expected

Proceedings of theNational Academy of Sciences, 106(50):21086-21090, 2009.

First, the information source selects a message to be transmitted. Next, the message is encoded into a signal, and that signal is sent to a receiver through some medium called a channel. The receiver then decodes the signal to recover the intended message. Successful communication means that the message recovered at the destination is approximately or exactly equal to the message selected at the source.