Interactive Optimal Teaching with Unknown Learners

1 Introduction

The use of computer and Internet technology in education has seen an enormous development in recent years, with the appearance of massive open online courses (MOOCs) and intelligent tutoring systems (ITS). MOOCs have created new opportunities for widespread education, while ITS provide personalized contents and/or exercises tailored for each user [Anderson et al., 1995; Koedinger et al., 1997; Nkambou et al., 2010; Clement et al., 2015; Mota et al., 2015].

Typically, ITS do not consider the specific structure of the teaching goal and abstract the teaching experience as the process of providing a teaching item for which a response is received. In contrast, the field of machine teaching (MT) considers directly the task to teach, and seeks to select the smallest amount of information necessary for a student to learn that specific task [Balbach and Zeugmann, 2009; Zhu, 2013; 2015]. Such quantity is often known as the teaching dimension (TD) of that task [Goldman and Kearns, 1995; Shinohara and Miyano, 1991].

Machine teaching has the potential to strongly reduce the effort required from both learner and teacher. For instance, the structural properties of the chemistry domain can be used to accurately estimate the knowledge of a student [Davenport et al., 2012] and use that to drive the selection of new teaching materials.

The main problem with machine teaching-which may partly explain its lack of use in actual ITS systems-is that the assumptions about what is known about the learner are often not realistic. Most methods assume a perfect knowledge about the learner, its learning process, and associated parameters. Such assumption is particularly unrealistic when dealing with human learners, but little work exists in the literature that explicitly addresses this unavoidable mismatch between what the machine teaching systems assume about the learners and the learners themselves.

In this work we take a step towards addressing such problem. Our contributions are two-fold:

• In the first part of the paper (Section 2), we show that, even in the simple situation of Bayesian Gaussian learners, the lack of knowledge regarding the student's learning process significantly deteriorates the performance of machine teaching: while perfect knowledge of the student ensures exact learning with a finite number of samples, incorrect information about the student implies that the latter will only learn asymptotically (i.e., after an infinite number of samples).

The results of such conceptual exercise suggest that the lack of knowledge about the learner hampers the potential usefulness of machine teaching even in the simplest situations and we may expect this effect to be even more severe when interacting with human learners.

• In the second part of the paper (Section 3) we propose interactive teaching as a possible avenue to address the aforementioned mismatch between teacher and learner. In interactive teaching, the teacher interleaves the presentation of novel information with moments in which it seeks to assess the students current state. We show that, in the case of a Bayesian Gaussian learner, the use of interactivity significantly gains in terms of learning performance.

Finally, we conduct a simple study in which human students must learn the average price of an apartment in an unknown city. Our results confirm the main conclusions of our conceptual analysis, namely that (i) the assumptions in the machine teaching system fail to reproduce the students' actual learning process; (ii) such mismatch renders machine teaching no different from a "random sampler"; (iii) the use of interactivity significantly improves the performance of the machine teaching system.

2 Teaching the Mean of a Gaussian Distribution

Let us consider the situation in which a teacher must select samples, {x1, . . . , xN}, from which a learner then estimates the mean of a Gaussian distribution N(µ∗ , τ ), where µ∗ represents the mean of the distribution and τ represents the corresponding precision [Zhu, 2013]. 1

Throughout our derivations, we assume that the precision of the distribution, τ, is known. We also assume the learner is a Bayesian learner with a (conjugate) prior N(µ0, τ0). In other words, upon receiving a sample x, the learner computes the updated estimate

More generally, upon receiving the nth sample, xn, the learner computes the updated estimate

where τn = τ0 + nτ, n ≥ 0.

2.1 Optimal Teaching with Perfect Knowledge

We start by considering the most favorable situation, in which the teacher is fully aware of the learner's model parameters, µ0 and τ0. In this case, if the teacher provides the sample

the learner's updated estimate is

In other words, if the teacher is perfectly aware of the learner's prior, a single sample is sufficient to ensure perfect learning. Any subsequent samples should take the value

which ensure that µn = µ∗ for all n > 0.

In practice, however, the teacher will not have perfect knowledge regarding the learner. Let us then consider the situation in which the learner's parameters do not correspond exactly to the values that the teacher assumes.

1 Given a normal distribution with mean µ and variance σ2 , the precision, τ, is the inverse of the variance, i.e., τ = σ-2 . We use the precision throughout the document for ease of presentation.

2.2 Teaching with theWrong Prior Mean

We first consider the situation where the learner's prior mean-henceforth denoted as µL0 -differs from the value assumed by the teacher-henceforth denoted as µT0 . Repeating the derivations in the previous subsection, the sample provided by the teacher will be

leading to the learner's updated estimate

where ∆µ = µL0 - µT0 . Following the reasoning in the previous section, we again conclude the teacher will then select xn = µ∗ , for all n > 1, leading to the learner's estimates

which asymptotically converges to µ∗ at a rate O( 1n ). 2

We can see that the term ∆µ-corresponding to the mismatch between the parameters assumed by the teacher and their actual values-is responsible for the different behavior of the learner when compared to the previous subsection and, if ∆µ = 0, we recover our previous result.

2.3 Teaching with theWrong Prior Precision

Let us now consider an alternative situation, in which it is the learner's prior precision, denoted that τ L 0 , that differs from the value assumed by the teacher, denoted as τ T 0 . Repeating again the derivations in the previous subsections, we get

where τ T 1 = τ T 0 + τ. The sample x1 leads to the learner's updated estimate

where ∆τ = τ L 0 - τ T 0 . We write µL1 to emphasize the fact that the learner's estimate after the first sample differs from that assumed by the teacher-i.e., the teacher assumes that the learner's updated mean is µT1 = µ∗ . Subsequent samples by the teacher will thus be xn = µ∗ , for n > 1, leading to the general estimate

which again asymptotically converges to µ∗ at a rate O( 1n ).

It is interesting to compare expressions (1) and (3), noting that they have, essentially, the same form: a vanishing term that weights the difference between the learner and the teacher, plus a term that converges to µ∗ . And, once again, if ∆τ = 0, we recover the initial one-step convergence result.

2 In other words, µn = µ∗ + O( 1n ).

2.4 Teaching with theWrong Prior and Precision

We now consider the situation where both µT0 ̸= µL0 and τ T 0 ̸= τ L 0 . The first sample provided by the teacher is

This sample results in the updated estimate

Letting ¯µ0 = 1 2 (µL0 + µT0 ) and ¯ τ0 = 12 (τ L 0 + τ T 0 ), we can rearrange (4) as

Since, as before, µT1 = µ∗ , subsequent samples verify xn = µ∗ , n > 1 and the updated estimates take the general form

Note that (5) subsumes (1) and (3). For example, if τ L 0 = τ T 0 , then ¯ τ0 = τ L 0 = τ T 0 and we recover (1). Similarly, if µL0 = µT0 , then ¯µ0 = µL0 = µT0 and we recover (3). Therefore, as expected, (5) also converges to µ∗ at a rate O( 1n ).

The expression (5) also evidences the impact of the mismatch of each parameter on the performance of the learner.

2.5 Teaching with theWrong Algorithm

Finally, we look at the case where the algorithm used by the learner does not exactly match the one assumed by the teacher. In particular, while the teacher assumes that the learner is a Bayesian learner, in reality the learner uses a standard Robbins-Monro stochastic algorithm, corresponding to

where {αn} is a non-negative step-size sequence satisfying the standard conditions

For our purposes, and following [Polyak, 1977], we consider a step-size sequence {αn, n ∈ N} such that nαn → K ≤ 1. As before, the sample provided by the teacher is

leading to the updated estimate

To facilitate future analysis, let τd = τ T 0 τ and write (6) as

Subsequent samples verify xn = µ∗ , leading to the estimate

We again get asymptotic convergence to µ∗ , since the first and second terms converge to 0 as n → ∞ (see Appendix A for details).

3 Using Interactivity to Overcome Prior Mismatch

In this section we discuss how interactivity can be used to effectively mitigate the impact of a wrong learner model. We assume that the teacher is able to query the learner at any point during the learning process. When queried, the learner responds the value of its current estimate perturbed by noise. This situation can model, for example, the case where there is noise in the communication between teacher and learner, or when the teacher is interacting with a population of learners, not all of which have the same prior over the target parameter.

Formally, we assume that, when queried, the learner responds with a value un = µLn + wn, where wn is a random noise term that is independent of any other entities used in the interaction (namely, µLn ) and such that wn ∼ N(0, σ2n ), where {σn, n ∈ N} is a positive, real-valued sequence such that σn → 0. The teacher assumes that the learner is a Bayesian learner with prior parameters (µT0 , τ T 0 ) and proceeds as follows:

1. Set n = 0.
2. Query the learner. The learner will then respond with the value un = µLn + wn, where wn is the Gaussian noise.
3. Set µTn = un.
4. Provide the sample

where, as before, τ T d = τ T 0 τ . Using the sample xn+1, the learner updates its estimate of the mean, leading to

where we again consider a learner following a standard Robbins-Monro stochastic algorithm. Replacing the expression for xn+1 yields

1. Set n = n + 1 and repeat the process from step 2. Unfolding the recursion, we get

The main differences between (8) and (7) are: (i) the term in ∆µ is absent in (8), while the term in wn is absent in (7); (ii) the coefficient multiplying the term (µL0 -µ∗ ) takes different forms in the two equations.

3.1 Rates of Convergence

To analyze the rate of convergence of the interactive approach, we rewrite (7) and (8) in their incremental form. For the non-interactive approach, we have that

where the NI superscript stands for "non-interactive" and

Considering the interactive approach, we have, for all n,

Since nαn → K ≤ 1, we have that

and it follows that, in expectation, δIn converges to 0 faster than the non-interactive approach. The difference between the two approaches is illustrated in Fig. 1, for the particular case where αn = 1/(n + 1), τd = 1 and ∆µ = 0. The plot clearly illustrates our main conclusion: the interactive approach significantly outperforms the non-interactive one.

4 Results

This section illustrates how the analysis from the previous section translates in actual learning performance. We present two sets of results, the first involving "simulated" students and the second a learning task involving human students. Our results compare interactive and non-interactive learning methods in different scenarios, and showcase the impact that incorrect information about the students can have in the performance of machine teaching.

-0.5

-0.5

4.1 Simulation Experiments

We consider the Bayesian Gaussian learning setting, in which the student is a Bayesian learner with a prior that differs from that of the teacher. Figure 2 presents a comparison between interactive versus non-interactive learning. The error of the non-interactive approach after 20 samples is reached after only 4 samples using interaction. The figure also show the trace of one run of the algorithm to illustrate what happens during the interaction. We can observe the effect of overshooting [Zhu, 2013], where the teaching sample always compensates the student's error: if the student over or underestimates, the teaching sample will take a value that is below or above the target value, respectively. Note also that the answer of the student is not the mean estimated by the student, but a noisy sample thereof, and such noise does not affect the superior performance of the interactive teaching.

4.2 User Study

We conducted a simple user study to assess whether our conclusions from Sections 2 and 3 hold (to some extent) when using a machine teaching system with actual human students.

Experimental design In order to conduct our study, we designed an activity which, to some extent, replicates the Gaussian learning scenario discussed throughout the paper. The task consisted of estimating/learning the average monthly rent of an 1-bedroom apartment in an undisclosed city somewhere in the USA. The information provided was selected to balance the impact of the student's prior knowledge in the task.

The task proceeds in rounds where, in each round, the student is asked its current "guess" for the average monthly rent, after which it receives an example of a rent presented to the student as a real rent practiced in the city under consideration. The task continues until the error in the student's guess is below 50$ up to a maximum of 30 rounds.

Each student repeats the activity three times, each time with a different city:

• "City A" corresponds to a target value (average monthly rent) of 500$;
• "City B" corresponds to a target value of 1000$;
• "City C" corresponds to a target value of 1500$.

The order by which each city is presented to the students is randomized between students.

We investigated the learning performance of the students in 3 different conditions:

• Condition 1: The samples are presented to the student following the interactive teaching approach described in Section 3. The answers provided by the student are used to compute the next "example rent" to be shown. In order to make the examples more believable to the student, we perturb the value prescribed by the algorithm by a small random amount between 1$ and 10$ and enforce that such value is never below 100$.
• Condition 2: The samples presented to the student are selected randomly from a Gaussian distribution with the prescribed mean and a standard deviation of 300$, ignoring the students' responses.
• Condition 3: The samples are presented to the student following the non-interactive machine teaching approach outlined in Section 2. We use the first three responses from the student to estimate the prior parameters used in the algorithm, but subsequent samples ignore the responses by the student.

The study involved a total of 62 engineering students divided uniformly among the three conditions (see Table 1). The average age was 23, with 68%males. In analyzing each activity/condition, we disregarded situations in which the students first estimate corresponded to the target value.

Results

The results of our study are summarized in Fig. 3 and prompt several relevant observations:

• The students were able to learn the target value after 30 rounds in all conditions.
• The interactive teaching approach clearly outperforms the other two approaches-both in terms of the average error and in terms of standard deviation of the estimates. In particular, we performed Mann-Whitney U-tests to compare the distributions obtained by the students after 8 and 30 rounds, and observed that the differences were significant in all cases. 3 This result is in line with our conclusion in Section 3: even if the teacher's assumptions regarding the student are wrong (which is most likely the case in our study), interactivity somewhat mitigates such mismatch, rendering. Similar results are observed if we consider the three activities ("City A", "City B" and "City C") individually, as illustrated in Fig. 4.
• Finally, the observed difference in performance between the interactive and non-interactive conditions is larger than the observed difference in performance between the non-interactive and random. This result is also in line with our conclusions in Section 2: when the teacher's assumptions regarding the student are wrong, the performance of the non-interactive machine teaching system may not be significantly different than that of random sampling.

5 Discussion

In this work we investigate the impact that the strong assumptions usually made in the machine teaching literature can have in the learning performance of the student.

3 p-values at round 8: 4.3 × 10-5 (I vs R) and 0.03 (I vs NI). p-values at round 30: 0.015 (I vs R) and 0.006 (I vs NI).

We conduct a conceptual exercise in which we show that, even in a simple Bayesian Gaussian learning setup, a mismatch between the values of the parameters of the learner and the values assumed by the machine teaching system for those values can have a significant impact on the learning performance of the student. In particular, it renders the machine teaching approach similar to a random sampler.

We then show that, by "closing the loop" between learner and teacher-i.e., by allowing the teacher to interactively assess the state of the learner, the impact of the aforementioned mismatch is significantly mitigated.

A simple user study involving human students confirm our conclusions, showing that-even with a simple learner model-an interactive machine teaching system is able to significantly outperform non-interactive alternatives.

The idea of interactive teaching is not new. However, previous works either continued to have too strong assumptions about the learners or do not provide guarantees on how good interactive learning is [Zilles et al., 2008]. For instance [Liu et al., 2017] provides bounds on the teaching dimension for known learners but not for unknown ones. [Cakmak and Thomaz, 2011] as well as [Suh et al., 2016] suggest a combination of machine teaching and active learning but without formal guarantees. [Milli et al., 2017] explore interpretability in machine teaching.

Our discussion also opens the door for situations with multiple students and uncertainty about the students. For example, [Zhu et al., 2017] considers the teaching dimension (TD) for teaching multiple students. They show that the TD grows sub-linearly with the number of students, which roughly means that the number of teaching examples required to teach N students grows sub-linearly with N. Extending our discussion of interactivity to multi-student settings raises a number of novel very interesting questions-e.g., how to interact with multiple students? How to deal with the individual differences between students? How much does the feedback from one student inform the teacher about the state of the class?-thus opening many challenging avenues for future research.

A Auxiliary Computations

In Section 2.5, it was stated that the two last terms in the righthand side of (7) converged. We now formally establish such statement.

We have that

Using the fact that log(1 - x) ≥ -x, 0 < x < 1, we have that

and hence

This establishes the desired convergence result.

Acknowledgments

This work was partially supported by national funds through the Portuguese Fundac¸ ˜ao para a Ciˆeencia e a Tecnologia under project UID/CEC/50021/2013 (INESC-ID multi-annual funding) and the Carnegie Mellon Portugal Program and its Information and Communications Technologies Institute, under project CMUP-ERI/HCI/0051/2013. Carla Guerra acknowledges the PhD grant SFRH/BD/118006/2016.