One of the great successes of the application of generalized quantifiers to natural language has been the ability to formulate robust semantic universals. When such a universal is attested, the question arises as to the source of the universal. In this paper, we explore the hypothesis that many semantic universals arise because expressions satisfying the universal are easier to learn than those that do not. While the idea that learnability explains universals is not new, explicit accounts of learning that (...) can make good on this hypothesis are few and far between. We propose a model of learning — back-propagation through a recurrent neural network — which can make good on this promise. In particular, we discuss the universals of monotonicity, quantity, and conservativity and perform computational experiments of training such a network to learn to verify quantifiers. Our results are able to explain monotonicity and quantity quite well. We suggest that conservativity may have a different source than the other universals. (shrink)

The ability to process center‐embedded structures has been claimed to represent a core function of the language faculty. Recently, several studies have investigated the learning of center‐embedded dependencies in artificial grammar settings. Yet some of the results seem to question the learnability of these structures in artificial grammar tasks. Here, we tested under which exposure conditions learning of center‐embedded structures in an artificial grammar is possible. We used naturally spoken syllable sequences and varied the presence of prosodic cues. The (...) results suggest that mere distributional information does not suffice for successful learning. Prosodic cues marking the boundaries of the major relevant units, however, can lead to learning success. Thus, our data are consistent with the hypothesis that center‐embedded syntactic structures can be learned in artificial grammar tasks if language‐like acoustic cues are provided. (shrink)

In recent articles Fodor and Lepore have argued that not only do considerations of learnability dictate that meaning must be compositional in the wellknown sense that the meanings of all sentences are determined by the meanings of a finite number of primitive expressions and a finite number of operations on them, but also that meaning must be 'reverse compositional' as well, in the sense that the meanings of the primitive expressions of which a complex expression is composed must be (...) determined by the meaning of that complex expression plus the manner of its composition. I argue against the requirement of reverse compositionality and against the claim that learnability requires it. I consider some objections and close the paper by arguing against the related claim that concepts are reverse compositional. (shrink)

The impetus for this volume developed from the 1982 University of Western Ontario Learnability Workshop, which was organized by the editors and sponsored by that University's Department of Philosophy and the Centre for Cognitive Science. The volume e~plores the import of learnability theory for contemporary linguistic theory, focusing on foundational learning-theoretic issues associated with the parametrized Government-Binding framework. Written by prominent re searchers in the field, all but two of the eight contributions are pre viously unpublished. The editor's (...) introduction provides an overview that interrelates the separate papers and elucidates the foundational issues addressed by the volume. Osherson, Stob, and Weinstein's "Learning Theory and Natural Language" first appeared in Cognition ; Matthews's "The Plausi bility of Rationalism" was published in the Journal of Philosophy. The editors would like to thank the publishers for permission to reprint these papers. Mr. Marin Marinov assisted with the preparation of the indices for the volume. VB ROBERT 1. MATTHEWS INTRODUCTION: LEARNABILITY AND LINGUISTIC THEORY 1. INTRODUCTION Formal learning theory, as the name suggests, studies the learnability of different classes of formal objects under different formal models of learning. The specification of such a model, which specifies a learning environment, a learn ing strategy, and a criterion for successful learning, determines a class of formal objects, namely, the class that can be acquired to the level of the specified success criterion by a learner implementing the specified strategy in the specified enviroment. (shrink)

In the first part of my paper I discuss eight arguments in favour of the theory-dependence of observation: realistic content, guidance function of theories, perception as cognitive construction, expectation-dependence of perception, theory-dependence of scientific data, continuity between observational and theoretical concepts, language-dependence, and meaning holism. I argue that although these arguments make correct points, they do not exclude the existence of observations that are weakly theory-neutral in the sense that they don’t depend on acquired background knowledge. In the second part (...) I suggest an experimental method, the method of ostensive learning experiments, by which the degree of theory- and language-independence of a concept can be tested. (shrink)

In his pioneering work in the field of inductive inference, Gold (Inf Control 10:447–474, 1967) proved that a set containing all finite languages and at least one infinite language over the same fixed alphabet is not identifiable in the limit (learnable in the exact sense) from complete texts. Gold’s work paved the way for computational learning theories of language and has implications for two linguistically relevant classes in the Chomsky hierarchy (cf. Chomsky in Inf Control 2:137–167, 1959, Chomsky in Knowledge (...) of language: its nature, origin, and use, Praeger, 1986; Shieber in Linguist Philos 8:333–343, 1985; Heinz in Linguist Inq 41:623–661, 2010). Within that same framework, Angluin (Inf Control 45:117–135, 1980) provided a complete characterization for the learnability of language families. Mathematically, the concept of identification in the limit from that classical setting can be seen as the use of a particular type of metric for learning in the limit (Wharton in Inf Control 26:236–255, 1974). In this research note, I use Niyogi’s extended version of a theorem by Blum and Blum (Inf Control 28:125–155, 1975) on the existence of locking data sets to prove a necessary condition for learnability in the limit of any family of languages with the Gold property in any given metric. This recovers the most general version of Gold’s Theorem as a particular case. Moreover, when the language family is further assumed to contain all finite languages, the same condition also becomes sufficient for learnability in the limit. Finally, we discuss questions that are left open and outline a research program regarding language learnability in the limit from other input types and cognitive feasibility. (shrink)

In this paper we present learning algorithms for classes of categorial grammars restricted by negative constraints. We modify learning functions of Kanazawa [10] and apply them to these classes of grammars. We also prove the learnability of intersection of the class of minimal grammars with the class of k-valued grammars.

This paper investigates the learnability by positive examples in the sense of Gold of Pregroup Grammars. In a first part, Pregroup Grammars are presented and a new parsing strategy is proposed. Then, theoretical learnability and non-learnability results for subclasses of Pregroup Grammars are proved. In the last two parts, we focus on learning Pregroup Grammars from a special kind of input called feature-tagged examples. A learning algorithm based on the parsing strategy presented in the first part is (...) given. Its validity is proved and its properties are examplified. (shrink)

This interdisciplinary new work explores one of the central theoretical problems in linguistics: learnability. The authors, from different backgrounds---linguistics, philosophy, computer science, psychology and cognitive science-explore the idea that language acquisition proceeds through general purpose learning mechanisms, an approach that is broadly empiricist both methodologically and psychologically. Written by four researchers in the full range of relevant fields: linguistics, psychology, computer science, and cognitive science, the book sheds light on the central problems of learnability and language, and traces (...) their implications for key questions of theoretical linguistics and the study of language acquisition. (shrink)

It is sometimes argued that if PDP networks can be trained to make correct judgements of grammaticality we have an existence proof that there is enough information in the stimulus to permit learning grammar by inductive means alone. This seems inconsistent superficially with Gold's theorem and at a deeper level with the fact that networks are designed on the basis of assumptions about the domain of the function to be learned. To clarify the issue I consider what we should learn (...) from Gold's theorem, then go on to inquire into what it means to say that knowledge is domain specific. I first try sharpening the intuitive notion of domain specific knowledge by reviewing the alleged difference between processing limitations due to shortage of resources vs shortages of knowledge. After rejecting different formulations of this idea, I suggest that a model is language specific if it transparently refer to entities and facts about language as opposed to entities and facts of more general mathematical domains. This is a useful but not necessary condition. I then suggest that a theory is domain specific if it belongs to a model family which is attuned in a law-like way to domain regularities. This leads to a comparison of PDP and parameter setting models of language learning. I conclude with a novel version of the poverty of stimulus argument. (shrink)

Richard Holton has drawn attention to a new semantic universal, according to which (almost) no natural language has contrafactive attitude verbs. This semantic universal is part of an asymmetry between factive and contrafactive attitude verbs. Whilst factives are abundant, contrafactives are scarce. We propose that this asymmetry is partly due to a difference in learnability. The meaning of contrafactives is significantly harder to learn than that of factives. We tested our hypothesis by conducting a computational experiment using an artificial (...) neural network. The results of this experiment support our hypothesis. (shrink)

It is sometimes argued that if PDP networks can be trained to make correct judgements of grammaticality we have an existence proof that there is enough information in the stimulus to permit learning grammar by inductive means alone. This seems inconsistent superficially with Gold's theorem and at a deeper level with the fact that networks are designed on the basis of assumptions about the domain of the function to be learned. To clarify the issue I consider what we should learn (...) from Gold's theorem, then go on to inquire into what it means to say that knowledge is domain specific. I first try sharpening the intuitive notion of domain specific knowledge by reviewing the alleged difference between processing limitatons due to shartage of resources vs shortages of knowledge. After rejecting different formulations of this idea, I suggest that a model is language specific if it transparently refer to entities and facts about language as opposed to entities and facts of more general mathematical domains. This is a useful but not necessary condition. I then suggest that a theory is domain specific if it belongs to a model family which is attuned in a law-like way to domain regularities. This leads to a comparison of PDP and parameter setting models of language learning. I conclude with a novel version of the poverty of stimulus argument. (shrink)

We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequences z is learnable (super-learnable, resp.) if (...) and only if there is a computable probability measure p such that p is Schnorr (Martin-Lof, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences. (shrink)

This paper discusses what kind of quantitative information one can extract under which circumstances from proofs of convergence statements in analysis. We show that from proofs using only a limited amount of the law-of-excluded-middle, one can extract functionals , where L is a learning procedure for a rate of convergence which succeeds after at most B-many mind changes. This -learnability provides quantitative information strictly in between a full rate of convergence and a rate of metastability in the sense of (...) Tao . In fact, it corresponds to rates of metastability of a particular simple form. Moreover, if a certain gap condition is satisfied, then B and L yield a bound on the number of possible fluctuations. We explain recent applications of proof mining to ergodic theory in terms of these results. (shrink)

Holton has drawn attention to a new semantic universal, according to which no natural language has contrafactive attitude verbs. Because factives are universal across natural languages, Holton’s universal is part of a major asymmetry between factive and contrafactive attitude verbs. We previously proposed that this asymmetry arises partly because the meaning of contrafactives is significantly harder to learn than that of factives. Here we extend our work by describing an additional computational experiment that further supports our hypothesis.

We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of strong CPAC learning, and provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple (...) general argument to exhibit such ndecidability, and initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al. (shrink)

Converging findings from English, Mandarin, and other languages suggest that observed “universals” may be algorithmic. First, computational principles behind recently developed algorithms that acquire productive constructions from raw texts or transcribed child-directed speech impose family resemblance on learnable languages. Second, child-directed speech is particularly rich in statistical (and social) cues that facilitate learning of certain types of structures.

It is argued that donald davidson has not succeeded in showing that we need a constructive theory of meaning--A theory for a natural language which davidson considers to have as its base a finite number of semantic primitives--In order to explain language learning and, In particular, Linguistic productivity. This linguistic productivity is the ability of a speaker who has mastered the meaning of a finite stock of words and a finite number of grammatical rules, To produce and understand sentences which (...) he has not constructed or encountered before. (shrink)

According to a “selective” (as opposed to “instructive”) model of human language capacity, people come to know more than they experience. The discrepancy between experience and eventual capacity (the “poverty of the stimulus”) is bridged by genetically provided information. Hence any hypothesis about the linguistic genotype (or “Universal Grammar,” UG) has consequences for what experience is needed and what form people's mature capacities (or “grammars”) will take. This BBS target article discusses the “trigger experience,” that is, the experience that actually (...) affects a child's linguistic development. It is argued that this must be a subset of a child's total linguistic experience and hence that much of what a child hears has no consequence for the form of the eventual grammar. UG filters experience and provides an upper bound on what constitutes the triggering experience. This filtering effect can often be seen in the way linguistic capacity can change between generations. Children only need access to robust structures of minimal (“degree-0”) complexity. Everything can be learned from simple, unembedded “domains” (a grammatical concept involved in defining an expression's logical form). Children do not need access to more complex structures. (shrink)

I want to argue that there is a task of ‘culture research’ other than what is practised in the empirical disciplines such as Social Anthropology or historical disciplines such as Literary Studies. Suppose ‘Cultures’ are looked upon as different legacies of ways of going about in the world resulting from the different pasts of different groups of people. Such ways can be either approached as a phenomena to be explained or as an embodiment of knowledge dispositions to be learnt. However, (...) the predominant tool for approaching knowledge dispositions is to look at them as explicitly or implicitly held propositions. One consequence of this propensity is to construe understanding a culture as arriving at the beliefs held by the community characterised by that culture. I will show that there is a way of extending the Fregean distinction between ‘object’ and ‘concept’ in such a way as to make it serviceable to conceptualise non-propositional forms of knowledge, and consequently, a more adequate tool for identifying the objects of culture research. (shrink)

Theories of relational concept acquisition based on structured intersection discovery predict that relational concepts with a probabilistic structure ought to be extremely difficult to learn. We report four experiments testing this prediction by investigating conditions hypothesized to facilitate the learning of such categories. Experiment 1 showed that changing the task from a category-learning task to choosing the “winning” object in each stimulus greatly facilitated participants' ability to learn probabilistic relational categories. Experiments 2 and 3 further investigated the mechanisms underlying this (...) “who's winning” effect. Experiment 4 replicated and generalized the “who's winning” effect with more natural stimuli. Together, our findings suggest that people learn relational concepts by a process of intersection discovery akin to schema induction, and that any task that encourages people to discover a higher order relation that remains invariant over members of a category will facilitate the learning of putatively probabilistic relational concepts. (shrink)

Since Fitch’s proof that not all propositions are knowable, philosophers have analysed the concept of knowability and sought a schema for the knowable propositions. A recent development in dynamic epistemic logic (DEL) has been to read ‘knowable’ as ‘known after an announcement’. Arbitrary Public Announcement Logic (APAL) and Sequential Public Announcement Logic (SPAL) are two DELs that have depicted this reading of knowability. We argue that neither APAL nor SPAL provide a satisfactory and principled schema of the knowable propositions. Instead, (...) we claim that knowability is linked with settledness; stability of truth. We augment SPAL with a settled operator to create a new logic, Dual Sequential Public Announcement Logic (DSPAL). We prove in DSPAL a principled schema of knowability, that all settled propositions are knowable. (shrink)