The Generativist Conceit

Why would we want to do all this? In the first lecture, I introduced what I called the Generativist Conceit: we can learn something about natural language by studying the grammars that describe possible natural languages. The strongest versions of this idea are controversial. But the weaker idea we need here is not. If we want a theory to make testable predictions about language, we need a sufficiently precise way to say what the theory allows. A grammar is one way to do that.

Learning gives us a second reason to care about classes of grammars. Children receive only a finite initial portion of their eventual linguistic experience, yet they come to make judgments about strings they have not heard. We would like to know which classes of possible languages permit this sort of generalization and which do not.

To make that question precise, we will study identification in the limit from text (Gold 1967). This is an idealized learning problem. It leaves out many things that actual children know, including meaning, communicative context, and explicit structural biases. The point of the idealization is to isolate what positive strings can tell a learner.

What counts as the learner’s input in this idealization? Let a text for a language $L$ be an infinite sequence

\[ T=\langle w_0,w_1,w_2,\ldots\rangle \]

whose members all belong to $L$ and in which every member of $L$ eventually appears. Repetition is allowed. Write $T[:n]=\langle w_0,\ldots,w_{n-1}\rangle$ for the finite data observed by time $n$.

A learner does not receive the completed infinite text. At each time, it receives only a finite prefix and proposes a grammar. Gold requires this learner to be effective, so take $f$ to be a computable function:

\[ f:(\Sigma^*)^{<\omega}\rightarrow\mathcal{G}. \]

Here $(\Sigma^*)^{<\omega}$ is the set of finite sequences of strings, and $\mathcal{G}$ is the learner’s hypothesis space. The learner identifies $L$ on a text $T$ when it eventually settles on one grammar $g$ that generates $L$:

\[ \exists N\;\exists g\in\mathcal{G}\;\forall n\geq N: f(T[:n])=g \text{ and } \mathbb{L}(g)=L. \]

The learner may make any finite number of mistakes before stage $N$. It may even switch away from the right answer and later return to it. But after $N$, the grammar name itself must remain fixed. It is not enough to alternate forever among different grammars that happen to generate the same language. The learner identifies a class $\mathcal{L}$ when it identifies every $L\in\mathcal{L}$ on every text for $L$.

Why positive data can be insufficient

Suppose that a hypothesis class contains an infinite language

\[ L_\infty=\{w_0,w_1,w_2,\ldots\} \]

and every finite initial portion

\[ L_i=\{w_0,\ldots,w_i\}. \]

Thus,

\[ L_0\subset L_1\subset L_2\subset\cdots \qquad\text{and}\qquad L_\infty=\bigcup_{i=0}^{\infty}L_i. \]

Assume for contradiction that a learner $f$ identifies every language in this collection. How could that assumption fail? We will construct a text for $L_\infty$ on which $f$ never settles. The construction proceeds in stages.

Begin by presenting strings from $L_0$. Because $f$ must learn $L_0$ on every text for $L_0$, we can continue this presentation until $f$ proposes a grammar for $L_0$.
Now introduce $w_1$ and continue with strings from $L_1$. If we were to continue this way forever, the resulting sequence would be a text for $L_1$. Because $f$ must learn $L_1$ on that text, there is a finite continuation after which it proposes a grammar for $L_1$.
Introduce $w_2$ and repeat the same argument for $L_2$.
Continue in this way, introducing $w_i$ at stage $i$ and waiting until the learner proposes $L_i$.

Every $w_i$ appears at some finite stage, and no string outside $L_\infty$ is ever presented. The resulting infinite sequence is thus a text for $L_\infty$.

But look at the hypotheses chosen at the ends of the stages. The learner proposes $L_0$, then $L_1$, then $L_2$, and so on. Since these languages are all different, its hypotheses do not stabilize on $L_\infty$. This contradicts our assumption that $f$ identifies $L_\infty$ on every text for that language.

The learner is not failing because any one of these languages is especially complicated. It fails because every finite amount of positive evidence from $L_\infty$ is also compatible with a smaller finite language in the hypothesis class. Positive data never announce that more examples are still to come.

Gold’s superfinite obstruction generalizes this argument. Fix a nonempty finite alphabet $\Sigma$. A class that contains every finite subset of $\Sigma^*$ and at least one infinite language cannot be identified in the limit from arbitrary positive text (Gold 1967). Negative evidence, a bound on the hypothesis space, or other information can change the result. The impossibility belongs to this particular learning setup.

Why this matters for phonology

The regular languages contain every finite language and many infinite languages, including $\Sigma^*$. The full regular class is thus not identifiable from positive text in Gold’s model.

This result does not show that finite-state phonology is unlearnable. It shows that a learner cannot search the entire regular class under the assumptions above. A learner might instead search a restricted family, receive negative or structured evidence, or use a prior bias not represented in the text.

This is one reason to study the subregular hierarchy. Some parameter-bounded subregular families can be identified from positive data (Heinz 2010; Jardine and Heinz 2016). The bounds matter: fixing a finite alphabet and a locality parameter gives a restricted hypothesis space, while taking an unrestricted union over all locality parameters may reintroduce Gold’s obstruction. We will keep that distinction in view as we move through the hierarchy.

References

Gold, E. Mark. 1967. “Language Identification in the Limit.” Information and Control 10 (5): 447–74. https://doi.org/10.1016/S0019-9958(67)91165-5.

Heinz, Jeffrey. 2010. “Learning Long-Distance Phonotactics.” Linguistic Inquiry 41 (4): 623–61. https://doi.org/10.1162/LING\_a\_00015.

Jardine, Adam, and Jeffrey Heinz. 2016. “Learning Tier-Based Strictly 2-Local Languages.” Transactions of the Association for Computational Linguistics 4: 87–98. https://doi.org/10.1162/tacl\_a\_00085.

--- title: The Generativist Conceit bibliography: ../references.bib --- Why would we want to do all this? In the first lecture, I introduced what I called the *Generativist Conceit*: we can learn something about natural language by studying the grammars that describe possible natural languages. The strongest versions of this idea are controversial. But the weaker idea we need here is not. If we want a theory to make testable predictions about language, we need a sufficiently precise way to say what the theory allows. A grammar is one way to do that. Learning gives us a second reason to care about classes of grammars. Children receive only a finite initial portion of their eventual linguistic experience, yet they come to make judgments about strings they have not heard. We would like to know which classes of possible languages permit this sort of generalization and which do not. To make that question precise, we will study **identification in the limit from text** [@gold1967language]. This is an idealized learning problem. It leaves out many things that actual children know, including meaning, communicative context, and explicit structural biases. The point of the idealization is to isolate what positive strings can tell a learner. What counts as the learner's input in this idealization? Let a **text** for a language $L$ be an infinite sequence $$ T=\langle w_0,w_1,w_2,\ldots\rangle $$ whose members all belong to $L$ and in which every member of $L$ eventually appears. Repetition is allowed. Write $T[:n]=\langle w_0,\ldots,w_{n-1}\rangle$ for the finite data observed by time $n$. A learner does not receive the completed infinite text. At each time, it receives only a finite prefix and proposes a grammar. Gold requires this learner to be effective, so take $f$ to be a computable function: $$ f:(\Sigma^*)^{<\omega}\rightarrow\mathcal{G}. $$ Here $(\Sigma^*)^{<\omega}$ is the set of finite sequences of strings, and $\mathcal{G}$ is the learner's hypothesis space. The learner **identifies** $L$ on a text $T$ when it eventually settles on one grammar $g$ that generates $L$: $$ \exists N\;\exists g\in\mathcal{G}\;\forall n\geq N: f(T[:n])=g \text{ and } \mathbb{L}(g)=L. $$ The learner may make any finite number of mistakes before stage $N$. It may even switch away from the right answer and later return to it. But after $N$, the *grammar name itself* must remain fixed. It is not enough to alternate forever among different grammars that happen to generate the same language. The learner identifies a class $\mathcal{L}$ when it identifies every $L\in\mathcal{L}$ on every text for $L$. ## Why positive data can be insufficient Suppose that a hypothesis class contains an infinite language $$ L_\infty=\{w_0,w_1,w_2,\ldots\} $$ and every finite initial portion $$ L_i=\{w_0,\ldots,w_i\}. $$ Thus, $$ L_0\subset L_1\subset L_2\subset\cdots \qquad\text{and}\qquad L_\infty=\bigcup_{i=0}^{\infty}L_i. $$ Assume for contradiction that a learner $f$ identifies every language in this collection. How could that assumption fail? We will construct a text for $L_\infty$ on which $f$ never settles. The construction proceeds in stages. 1. Begin by presenting strings from $L_0$. Because $f$ must learn $L_0$ on every text for $L_0$, we can continue this presentation until $f$ proposes a grammar for $L_0$. 2. Now introduce $w_1$ and continue with strings from $L_1$. If we were to continue this way forever, the resulting sequence would be a text for $L_1$. Because $f$ must learn $L_1$ on that text, there is a finite continuation after which it proposes a grammar for $L_1$. 3. Introduce $w_2$ and repeat the same argument for $L_2$. 4. Continue in this way, introducing $w_i$ at stage $i$ and waiting until the learner proposes $L_i$. Every $w_i$ appears at some finite stage, and no string outside $L_\infty$ is ever presented. The resulting infinite sequence is thus a text for $L_\infty$. But look at the hypotheses chosen at the ends of the stages. The learner proposes $L_0$, then $L_1$, then $L_2$, and so on. Since these languages are all different, its hypotheses do not stabilize on $L_\infty$. This contradicts our assumption that $f$ identifies $L_\infty$ on every text for that language. The learner is not failing because any one of these languages is especially complicated. It fails because every finite amount of positive evidence from $L_\infty$ is also compatible with a smaller finite language in the hypothesis class. Positive data never announce that more examples are still to come. Gold's **superfinite obstruction** generalizes this argument. Fix a nonempty finite alphabet $\Sigma$. A class that contains every finite subset of $\Sigma^*$ and at least one infinite language cannot be identified in the limit from arbitrary positive text [@gold1967language]. Negative evidence, a bound on the hypothesis space, or other information can change the result. The impossibility belongs to this particular learning setup. ## Why this matters for phonology The regular languages contain every finite language and many infinite languages, including $\Sigma^*$. The full regular class is thus not identifiable from positive text in Gold's model. This result does not show that finite-state phonology is unlearnable. It shows that a learner cannot search the *entire* regular class under the assumptions above. A learner might instead search a restricted family, receive negative or structured evidence, or use a prior bias not represented in the text. This is one reason to study the [subregular hierarchy](subregular-hierarchy/index.qmd). Some parameter-bounded subregular families can be identified from positive data [@heinz2010learning; @jardine2016learning]. The bounds matter: fixing a finite alphabet and a locality parameter gives a restricted hypothesis space, while taking an unrestricted union over all locality parameters may reintroduce Gold's obstruction. We will keep that distinction in view as we move through the hierarchy.