Language acquisition with communication between learners

Abstract

We consider a class of students learning a language from a teacher. The situation can be interpreted as a group of child learners receiving input from the linguistic environment. The teacher provides sample sentences. The students try to learn the grammar from the teacher. In addition to just listening to the teacher, the students can also communicate with each other. The students hold hypotheses about the grammar and change them if they receive counter evidence. The process stops when all students have converged to the correct grammar. We study how the time to convergence depends on the structure of the classroom by introducing and evaluating various complexity measures. We find that structured communication between students, although potentially introducing confusion, can greatly reduce some of the complexity measures. Our theory can also be interpreted as applying to the scientific process, where nature is the teacher and the scientists are the students.

Keywords: inductive inference; language learning; population structures in learning.

Figure 1.

A teacher and a group of learners. The teacher is represented as a square and learners as circles. Individuals whose hypothesis is the teacher's language L₁ are shown in red, others in blue (teacher is always red). Possible communications are indicated by edges. When an edge is selected for the communication event, it is shown in bold. (a) An illustration of one possible run of a single round as described in the §2.3 Example. Population structure consists of a teacher, Alice and Bob. There are two non-overlapping languages L₁, L₂. When a learner hears a sentence they do not understand, they switch their hypothesis to the other language with probability 80% (and keep it otherwise). We picked the edges in order B → T, B → A, A → T. In the second step, B switched from correct L₁ to incorrect L₂. (b) An illustration of (p, q)-learning. In one step of the learning process, we select an edge (indicated in bold) and then the listener of that edge updates their language hypothesis. (i) Learner X listens to the teacher and switches to the teacher's language with probability p. (ii) Learner Y already has the same language as the teacher, but due to listening to a learner X who speaks a ‘wrong’ language, Y switches with probability 1 − q to a (possibly different) wrong language. (Online version in colour.)

Figure 2.

Simulations for small graphs. (a) Four distinct structures of the class room, each with one teacher and four learners. Note that graph A is the ‘empty graph’ because there are no communications between the learners. (b) Simulation results for these four graphs showing the average number of rounds that are needed for all learners to converge to the correct language versus the number of languages ℓ in the search space. Here we consider (p, q)-learners with p = q = 1/ℓ. Each point is an average over 100 000 trials. In each round, the communication happens along each edge once, in random order. Graphs B and C are much worse than the empty graph A, but graph D is faster. This simple example shows that communication between learners can both accelerate and decelerate the process. (Online version in colour.)

Figure 3.

Different population structures of language learning. The teacher is shown in red and the learners in blue. (a) The empty graph represents the case where learners only listen to the teacher and do not communicate with each other. (b) The opposite extreme is the complete graph where all possible communications between learners are realized. (c) In the tree graph with branching factor k = 2, the teacher speaks to two learners, who each speak to two learners and so on. (d, e) The two-layered hierarchy and the k-layered hierarchy consist of layers such that each learner from a given layer listens to all individuals from the previous layer. In the special case of exponentially growing layered hierarchies (2-hierarchy and ELH), each layer is exponentially bigger than the previous one. (Online version in colour.)

Figure 4.

Numerical simulation results. The colours represent different graph families: blue, empty graph; orange, 2-hierarchy; green, tree graph. The empty graph is shown in bold because it is the baseline comparison. First, we consider memoryless learners with a helpful teacher, that is p = 2/ℓ, q = 1/ℓ. (a) Rounds complexity against the population size n, for a fixed number of languages ℓ = 10. For the empty graph, the dependency on n is logarithmic, for tree graph, it is also logarithmic but worse by a constant factor, and for the 2-hierarchy graph it is asymptotically better (namely doubly logarithmic). (b,c) Rounds complexity against the number of languages ℓ, for fixed population size n = 30 and n = 100. The 2-hierarchy beats the empty graph in both cases. As the dependency on ℓ in all cases is linear, any value of ℓ would yield an analogous outcome in (a). (d–f) Similar plots for batch learners under symmetric language overlap q = 0.1. (d) Rounds complexity against the population size n, for a fixed number of languages ℓ = 10. As in (a), for the empty graph the dependency is logarithmic, whereas for the 2-hierarchy it is asymptotically better. However, for the tree graph the dependency is linear in n. (e,f) This time the dependency on ℓ is logarithmic in all cases (batch learners are more powerful than memoryless learners). All the values shown are averages over 10 000 trials. (Online version in colour.)