Formal Theories of Language Acquisition: Practical and Theoretical Perspectives

Formal Theories of Language Acquisition: Practical and Theoretical Perspectives

Daniel N. Osherson Center for Cognitive Sc ience M I T

Cambr idge. MA 02139 USA

~lichael Stob Department of ~~athematics Ca lvin College Grand Rapids, MI 49506 USA

Scott IJei ns tei n Department of Philosophy University of Pennsylvania Philadelphia, PA 19104 USA

AilS TRACT

Learning Theory is the study of systems that impl eme nt functions from evidential sta t es to theories. The theoretical framework developed in the th eory makes po ss ibl e t he comparison of c lasses of algorithms whi c h embody distinct l ea l'ning s trat eg i es along a variety of dimensions. Such comparisons yield valuab le information to those concerned with in f e r e nce problems in Cogniti ve Sc it!nce a nd Artifi c ial Intelligence. Th e present paper employs the fr amework of Learning Theory to s tudy the design spec ifica t ions of inductive systems which are of interest in the domain of l a ng uage acquisition .

Section 0: Introduction

Learning Theory is the investigation of systems that implement functions from evidential states to theo ries. Of central concern is the characterization of conditions under wh ic h such functions stabilize to accurate theories of a given environment. Within the theory, the informal notions of "evidence," "theory," "stab "ilization, " "accuracy," and "environme nt" are replaced by precise definitions. Alternative formulations of these concepts yield alternative models within the theory: The vigorous development of Learning Th eo ry began witll a celebrated paper by Gold (1967) . Angluin & Smith (1982) provide a valuable review of formal

results.

Learning Theory is mot iva ted by both scientific and technological concerns. Scientifically, the theory has proved useful in the analysis of human learning , particularly, language acquisition (see Osherson, Stob & Weinstein, forthcoming, for a review of issues) . Technologically, the theory help s specify what is learnable in principle, and may thus guide the con s truction of practical systems of

inductive inference.

Learning Theory yields potentially valuable insights about problems of inductive inference in the context of Cognitive Science and Artificial Intelligence. The theory provides the framework for systematic comparison of various learning algorithms. Such comparisons are particularly useful in determining the relati ve strength of classes of algorithms which embody distinct abstract learning strategies, in assessing their resource requirements, and in predicting their behavior in various environments. When combined with empirical studies of language acquisition, Learning Theory may provide constraints on the cha racte r of the learning strategies implemented by children, and reflect in turn on the character of the class of languages wl1ich may be acqui rerl. Such studies in Cognitive Science may be of importance to system builders in Artificial Intelligence. They suggest that the search for ideal learning strategies' is not well motivated. Rather, by focussing on learners who embody different "styles" of learning, and by investigating their properties, the theory allows a comparison of the optimality of distinct approaches to learning along a multitude of dimensions . In add it ion, through the analysis of classes of algorithms that embody distinct learning strategies, this theoretical framework may provide a useful complement to studies of ad hoc systems built to perform inductive inference in problem domains of limited scope.

The present paP'er reviews some of our recent work on pr-actical inference and relates it to problems in ·language acquisition. We consider design specifications for inductive systems relevant to (a) the speed of inference, (b) the simplicity of inferred theories, (c) the likelihood of inferential success, and (d) the resilience of such systems in environments subject to

informational imperfection. Attention is restricted to learning paradigms in which only "positive information" is available about the language or data-set to be inferred; direct information about nonmembership is not offnred to the learner; Angluin & Smith (1982) survey results relevant to learning paradigms in which both positive and negative information is assumed available.

Oui' expos ition is organized as follows. The next section provides definitions and construals at the heart of contemporary learning theory. Sect ion 2 exhibits theorems proper to the topics (a) (d) listed above. Proofs of these theorems can be found in Osherson, Stob & Weinstein (1982, 1983d). In Section 3 we consider the relation between results reviewed here and language acquisition by children.

Section 1: The Gold modol

1.1 Sequences, languages, texts

N is the set of natural numbers. We take the notions finite sequence (in N) and infinite sequence (in N) to be basic. The set of all finite sequences is denoted: SEQ. For· n E N, and infinite sequence, t: rng(t) is the set of numbers appearing in t: tn is the nth member of t; and {n is the finite se quence of length n in t.

Let <p 0 · cp 1 , ... , cpi, ... be a fixed list of all partial recursive functions of one variable, and assume the list to be acceptable in the sense of Rogers (1967, Ch . 2) . For i E N, let Wi domain cpi· the recursively enumerable subset of N with index i. Languages are identified with nonempty members of {Wili E N} . The collection of all languages is denoted: ':R,S. For L E ':R,S, i E N, if L = Wi, then i is said to be

for L.

A text for L E ':R,S, is any infinite sequence such that rng(t) L. The class of all texts for L is denoted: TL. Given a collection, L, of languages. "Tt" denotes UL E L TL, the class of all texts for languages in L.

1.2 Learning functions

Let G be a fixed, computable isomorphism between SEQ and N. A learning function is any function from N into rJ : such a function will be thought of as operating on rnembe rs of SEQ (vi a G), yielding indices for recursively enumerable sets. Learning functions may be total or partial, recursive or nonrecursive. The (partial) recursive learning functions are just cpa, cpl····· cpi,.... The class of all learning functions is denoted: <J. The class of all recursive learning functions (partial or total) is denoted : <J rec .

1.3 Convergence , identification

Let f E <J, t E Tc:M· i E N. \~e say that f converges to i on t just in case (a) f(a) is defined for all a in t, and (b) for all but finitely many n E N~ f({n) = i. Intuitively, f converges to i on t just in case (a) f never becomes "s tuck" in examining ever longer finite sequences in t, and (b) f eventually conjectures i, and never departs from it

thereafter .

Let f E ~. t E T<],g· f is said to identify t just in case f converges to an index, i. on t such that Wi = rng(t). f identifies L E <;R,g just in case f identifies every t E TL . f identifies L ~ <;R,g just in case f identifies every t E T,t: in this case L is said to be identifiable.

Gold's Theorem include all finite infinite language. identifiable. (1967): languages Then L Let and is L any not

Section 2: Practical learning

2.1 Efficient fnference

Useful learning must not take too much time. This vague admonition can be resolved into two demands: ( i) the learner must not examine too many inputs before settling for good on a correct hypothesis , and (ii) the learner must not spend too long examining each input. Lear·ners satisfying (i) will be called

"text-efficient;" learners satisfying

(ii) will be called "t ime- eff icient" learners satisfying both (i) and (i will be called "efficient." In th s section these requirements are formulated precisely and examined for their impact on identifiability.

2.1. 1 Text-efficiency

Following Gold (1967, Section 10), we define the partial functional CONV:'!f x T':R,g __, N as follows. For all f E '!f, t E T':R,g.

CONV(f,t) f(~m - 1))]. JLn[(\fm >

CONV is defined on f E GJ, t E T':R,g if f converges on t, in which case CONV(f, t) is the length of the smal lest a E SEQ in t suc h that f 's last revised conjecture in l is made on a.

Now let F E GJ, L ~ ':R,g, We say that f identifies L text efficiently just in case f identifies L, and for all g E GJ that identify L,

( " ) if (3t E Tt)(CONV(g,t) < CONV(f,t)), then (3 s E Tt)(CONV(f,s) < CONV(g,s)).

f is said to identify L text efficiently w"ith respect to GJrec just in case f identifies L, and for all g E <.free that identify L, (*) holds.

Intuitively, f identifies L t ext-efficiently [with respect to <.free] just in case no other [recursive] learning function that identifies Lis strictly faster than f i n terms of convergence delay . This notion of text efficiency yields:

Proposition 1: p, collection, L, of langu ages is identifiable if and only if some f E GJ identifies L text efficiently.

Proposition efficiency is not a feature relative to shows that text restrictive design the class of all lear·ning functions. In contrast, the next proposition s hows that text efficiency is restri cti ve relative to the class of recursive learning functions.

Proposition 2: There is some L ~ ':R,g such that ( i) some f E 'j'rec identifies L, but ( i i) no f E 'j'rec identifies L text efficiently with respect to GJrec.

2.1.2 Time efficiency

A learner is time efficient if it reacts quickly to new inputs. We formalize this notion only for the case of recursive le a rning functions. A computational comple~ity measure in the sense of Blum (1967a) is imposed upon our acceptable ordering of partial recursive functions. ihe meas ure justifies reference to the number of "steps" required for <Fi to halt on j (i . j E N). For i,s,k E N, we let <pi,s(k) be the output (if any) after s steps in the computation of 'Pi( k); " j<pi(k)l" denotes JLS[~i.s(k) halts].

Now let L ~ ':R,g, let i E N, and let h :N --+ N be a total recursive function. We say that 'Pi identifies L h-time efficiently just in case (i) <pi identifies L, and (ii) for every t E T1 , there is a k E N such that for all j > k:

Intuitively, 'Pi identifies L h-t ime efficiently if for every t E Tt, 'Pi even tua ll y takes no more than h( tn+ 1) additional steps to respond to {n+1 than to respond to tn; that is, except for a constant. the growth in 'Pi's response time to ever longer initial segments of t is hounded by h. h-time efficiency turns out not to restrict the classes of languages identifiable by recursive l ea rning function . This is the burden of the next proposition.

Proposition 3: There is a recursive function, h, such that for all .1.. ~ ':R,g, some f E GJrec identifies L if and only if some 'Pi E GJrec identifies L h- time efficiently.

Indeed, any h such that h(x) ;::: x almost everywhere can be chosen in P1·oposition 3.

2.1.3 Efficiency

Let L (,;; 'Poe, and let h be a total recursive function. <pi is said to identify L h-efficiently just in case (i) <pi identifies L text efficiently with respect to ':free (in particular, 'Pi identifies L), and (ii) 'Pi is h-time efficient for L. h-efficiency, that is, comb ines the virtues of text efficiency (with respect to ':free) and h-time efficiency . The next proposition shows that, For any h, h-efficiency is more re s trictive than text efficiency as a design feature of recursive learning functions.

Proposition 4: For every total l'ecursive function, h, there is a collection, 1, of languages such that (i) some f E ':free identifies L text e fficiently, but (ii) no <pi E ':free identifies L h-eff iciently.

Proposition 5: recursive function, h , such that (i) some f E text efficiently, identifies L h-time (iii) no <pj identifies For some total there is L (,;; 'Pol> ':free identifies L (ii) some <pi efficiently, but L h-efficiently.

2.2 Simple conjectures

To be useful, a learner shou ld not only converge rapidly to a correct theory of its environment, it should also converge to a relatively simple theory: excessively complex theories, even if true, are of 1 ittle practical use. To study the impact of such simplicity constraints on learnability, a total recursive size measure, S:N -t N, is now imposed on our acceptable orde ring of partial recursive functions. Intuitively, S may be conceived as mapping indices to sizes, S(i) being the length of the program for <pi correspond i ng to index i. The measure is governed by the following two axioms, due to Blum (1967b).

Axiom 1 : For a 1 1 i E N , there are only finitely many j E N such that S(j)

= i.

Axiom 2 : The predicate "j E s- 1 (i)," for i,j EN, is decidable.

Define the fur.ct ion t-1S:'Jbe _. N as follows. For L E ':R,e , ~1S(L) pj[(3k)(Wk = L & S(k) = j]. Thus, ~IS(L) is the size of the smallest program that accepts L. Concern about simple conjectures may take the following form. Let g be a total recurs i ve function, let f E 'J, and let L (,;; 'Pol>. f is said to identify L g-simply just in case f identifies L, and for all t E T1, f converges on t to an index, j, such that S(j) ~ g(MS(rng(t)) . To exemplify, let g be f.x.2x. Then f id en tifies L g-simply just in case f identifies L, and for al l L E L and t E TL, f converges on t to an index of size no greater than twice ~1 S (L) (the size of the smallest program that accepts L = rng(t)).

Text are more recursive is alone. efficiency and g-simplicity restr ic tive design Fea tures of learning func t ions than either This is the content of the next proposition.

Propos it ion 6: There is L (,;; 'Pol> such that (i) some f E g rec identifies L text efficiently, ( ii) for any total recursive function, g. such that g(x) ~ x for all x E N, some f E 'Jrec identifies L g-simply , but (iii) for every f E 'irec, and every total recursive function, h, iff identifies L text efficiently with respect to 'irec, then f does not identify L h-simply.

2.3 Learning in likely environments 1

In some environments each potential e lement of a language is associated with a fixed probability of occurrence, invariant through time. Such environments may be thought of as infinite sequences of stochastically independent events , the probab ·i 1 ity of a given element, e, appear ing in the n+lst position being independent of th~ contents of positions 0 through n.

To study such environments, each L E 'Pol> is associated with a probability measure, ml, on N such that for all x E N, x E L if and only if ml({x}) > 0. (Recall that every L E 'Pol> is nonempty; see Section 1. 1.) Next, we impose on T'.R,g its Baire topology, ':f'Pog: that is, for each a E SEQ, we take Ba = {t E T'.R,glo- is in t} to be a basic open set of ':~''Pol>· For each L E '.R,S, we define the

(unique) complete probability measure, ML , on <r~e: by stipulating that for all u E SEQ, t~L(Bu) = nj < lh{u)mL(uj). We now assume the existence of a fixed collection, {MLIL E ~8} of measures on correponding members of {TLIL E ~8}. Intuit i vel y , for me as u r a b l e S C: T L , ML(S) is the probability that an arbitrarily selected text for L is drawn

from S.

The following facts are easy to

est a b l i s h . For all L , L ' E ~8,

(II) for f E "J, ML{{t E TLJf identifies t}) is defined.

In the s tochastic context just di sc usse d , the Gold definition of l anguage identification seems needlessly restrictive. Rather than requ ·iring identificat ion of every text for a given l anguage, L, it seems enough to require identification of any subset of TL of sufficient probability. We are thus led to the following definition. Let f E ".f, L E ~8. f is said to measure-one identify L jus t in case t\({t E TLif identifies t}) 1. f measure ··one iden tifies L C: %8 just in case f meas ure-one identifies every L E L; in this case. Lis said to be measure-one iden tifiable. The definition of meas ure-one identifiability is inspired by Wexler & Culicover (1980, Ch. 3).

Measure-one identification of a language differs from ordinary identification only by a set of measure zero. The next proposition reveals the significance of this small difference.

Proposition 7: ~8 is measure-one

identifiable.

Let L = {Li I i E N} be an indexed collection of languages, and let {Pili E N} be the corresponding measures on them. L is said to be uniformly measured just in case the predicates "x E Ly" and "Px( {y}) = z" are decidable {the decidability of the latter predicate actually implies that of the former) . Minor modifications in the proof of Proposition 7 yield the following.

Proposition 8: Let L uniformly measured collection languages. Then, some f E be a of grec

measure-one identifies L.

Thus, in contrast to Gold's Theorem (Section 1.3, above), any uniformly measured collection of languages consisting of all finite sets and any infinite set is measure-one

identifiable.

2 . 4 Imperfect environments

2 . 4 . 1 Noisy texts

A noisy text for a language, L, is any text for a language of the form LUO, where 0 is a finite set. Thus, a noisy text for a language, · L, can be pictured as a text for L into which any number of intrusions from a f'inite set have been inserted. Since the empty set is finite, texts for L count as noisy texts for L. We say that a learning function, f, identifies a language, L, on noisy text just in case f converges to an index for L on every noisy text for L. A learning function, f, identifies a co71ection, L, of languages on noisy text just in case f identifies every language in L on noisy text.

It is clear that noisy text renders impossible the identification of the collection of all finite languages. The following proposition provides a less obvious example of the disruptive effects of such environments for recursive learning functions.

Proposition 9: There is a collection, L, of languages such that (a) every language in L is infinite and disjoint from every other language in L, {b) some recursive learning function identifies L, and (c) no recursive learning function identifies L on noisy

text.

2.4.2 Incomplete texts

An incomplete text for a language, L, is defined to be a text for L-0, where 0 is any finite set. An incomplete text for a language, L, can be pictured as a t~xt for L from which a1.l occ11rrences of a given finite set of sentences have been removed . Texts for L count as incomplete texts for L. We say that a learning function, f, id.;nt ifies a language, L, on incomp Jete text just in case f converges to an index for L on every incomplete text for L. Identifiability of collections of language s on incomplete text is defined straightforwa rdly .

Proposition 10: There is a collection, 1, of langu ages such that (a) every language in 1. is infinite and di s joint from every other language in 1, {b) some recursive learning function identifies 1, and (c) no recursive l earning function identifies 1 on incomplete text.

1. compared Noisy and incomplete text
2. Let ex be the family of all collections. 1., of languages such that 1. can be identified {by arbitrary learning function) on noisy text. Define ej similarly with respect to incomplete text. We have:

Proposition 11: subset of ej. ex is a proper

1. Finite-difference identification on imperfect text

Let L, L' E ':R,I5. L is said to be a finite vilriant of L' just in case (L - L') U (L - L') is finite. A learning function, f, is said to finite-difference identify a language, L, on noisy text just in case for every noisy text, t, for L, f converges on t to an index for a finite-variant of L; f finite-difference identifies a collection, 1., of languages on noisy text just in case for every LE1, f finite-difference identifies L on noisy text. Finite-difference identification on incomplete text is defined similarly.

Given the margin of error tolerated in finite-difference identification, one might doubt that imperfect ion restricts this kind of learning. It is thus

natural to conjecture:

• 1 is finite-difference identifiable [by recurs~ve learning function] if and only if 1. is finite-difference identifiable on noisy text [by recursive learning function]; and

1 is finite-difference identifiable [by recursive learning function] if and onl y if 1 is finite - difference identifiable· on incomplete text [by recursive learning function].

The next two propos itions show th at both versions of both conjectures are false.

Proposition 12: There is a collection , 1., of languages such that some recursive learning function identifies 1., but no ·learning function (recursive or not) finite-difference identifies 1. on noisy text.

Proposition 13: There is a collection, 1., of languages such that some recursive lea r n1ng function identifies 1., but no le ar ning function (recursive or not) finite-difference

identifies 1. on incomplete text.

Section 3 : Language acquisition and formal models of inference

The circumstances of normal language acquisition by children appear to share a fundamental feature with the inference paradigms discussed above. Infants apparently have no direct access to the nonsentences (so labeled) of the target language. This assertion rests on evidence that children are seldom corrected for ungrammatical utterances per se, nor do they communicate more successfully with grammatical than with ungrammatical sentences (Brown & Hanlon, 1970). In short, chi 1 dren learn their language on texts.

As a consequence of this shared environmental feature, the propositions adduced above are relevant to the study of language acquisition. Thus: (a) Propositions 1 - 4 reveal some of the consequences of efficient learning by children; if languag e acquisition proceeds efficiently in the senses earlier defined, the class of learnable 1 anguages is narrower on this account. {b) If the class of natural languages is infinite, then a corollary of results in Sect ion 2. 2 shows that infinitely many grammars conjectured by children are wildly oversized {by any reasonable measure of size). (c) If each se ntence in the target language can be associated with a lower bound on the probability of its occurrence in the child's linguistic environment. then Proposition 7 shows that the set of languages that can be learned with certainty is very large. And {d) Propos it ions 9 and 10 reveal the surprising consequences for language acquisition of even mild imperfections in children's linguistic environments. These kinds of connections between Formal Learning Theory and language acquisition by children have become increasingly central to 1 inguistic theory and developmental psycholinguistics (see Wexler & Culicover, 1980; Osherson, Stob & Weinstein 1983a).

The results reviewed in this paper represent only one of several perspectives on language acquisition offered by Formal Le a rning Theory. Thus, in addition to effic ·iency, several other learning strategies plausibly a ttributed to children have been investigated from the learning theoretic point of view (Osherson, Stob & Weinstein 1983b). These include such response tendencies as (a) restriction to hypotheses compatible with available data, {b) gradual shifts in hypotheses rather than large leaps, (c) pe rseveration on conjectures that predict the available linguistic data, {d) restriction to grammars with nontrivial "recursive" rules, and {e) exclusion of long-past data in hypothesis selection. Additionally, criteria of successful acquisition less stringent than identification have been fOI'mulated and studied in the context of contemporary linguistic theory and language acquisition . These issues are discussed in Osherson & Weinstein {1983c).