Mixture Modeling of Individual Learning Curves

ABSTRACT

We show that student learning can be accurately modeled using a mixture of learning curves, each of which specifies error probability as a function of time. This approach generalizes Knowledge Tracing, which can be viewed as a mixture model in which the learning curves are step functions. We show that this generality yields order-of-magnitude improvements in prediction accuracy on real data. Furthermore, examination of the learning curves provides actionable insights into how different segments of the student population are learning.

To make our mixture model more expressive, we allow the learning curves to be defined by generalized linear models with arbitrary features. This approach generalizes Additive Factor Models and Performance Factors Analysis, and outperforms them on a large, real-world dataset.

1. INTRODUCTION

In the mid-1980s, a now-famous study demonstrated the potential impact of adaptive, personalized education: students tutored one-on-one outperformed those taught in a conventional classroom by two standard deviations. Remarkably, subsequent research has achieved similar gains using interactive, computerized tutors that maintain an accurate model of the student’s knowledge and skills. In the past few years, widespread access to smartphones and the web has allowed such systems to be deployed on an unprecedented scale. Duolingo’s personalized language courses have enrolled over 90 million students, more than the total number of students in all U.S. elementary and secondary schools combined.

A central component of an intelligent tutoring system is the student model, which infers a student’s latent skills and knowledge from observed data. To make accurate inferences from the limited data available for a particular student, one must make assumptions about how students learn. How do students differ in their learning of a particular skill or concept? Is the primary difference in the initial error rate, the rate at which error decreases with time, the shape of the learning curve, or something else? The answers to these questions have implications for the choice of model class (e.g., Hidden Markov Model, logistic regression), as well as the choice of model parameters.

Previous approaches to student modeling typically make strong assumptions about the shape of each student’s learning curve (i.e., the error rate as a function of the number of trials). Additive Factor Models use the student and the number of trials as features in a logistic regression model, which implies a sigmoidal learning curve with the same steepness for each student, but different horizontal offset. Knowledge Tracing is a two-state Hidden Markov Model where, conditioned on the trial t at which the student first transitions from not knowing the skill to mastering it, the learning curve is a step function.

In empirical studies, it has been observed that aggregate learning curves often follow a power law, a phenomenon so ubiquitous it has been called the power law of practice. Later work suggested that, although error rates follow a power law when averaged over an entire population, individual learning curves are more accurately modeled by exponentials. That is, the power law curve observed in aggregate data is actually a mixture of exponentials, with each student’s data coming from one component of the mixture.

These observations led us to seek out a more general approach to student modeling, in which individual learning curves could be teased apart from aggregate data, without making strong assumptions about the shape of the curves. Such an approach has the potential not only to make the student model more accurate, but also to explain and summarize the data in a way that can produce actionable insights into the behavior of different subsets of the student population.

This work makes several contributions to student modeling. First, we present models of student learning that generalize several prominent existing models and that outperform them on real-world datasets from Duolingo. Second, we show how our models can be used to visualize student performance in a way that gives insights into how well an intelligent tutoring system "works", improving upon the population-level learning curve analysis that is typically used for this purpose. Finally, by demonstrating that relatively simple mixture models can deliver these benefits, we hope to inspire further work on more sophisticated approaches that use mixture models as a building block.

1.1 Related Work

The problem of modeling student learning is multifaceted. In full generality it entails modeling a student’s latent abilities, modeling how latent abilities relate to observed performance, and modeling how abilities change over time as a result of learning and forgetting. For an overview of various approaches to student modeling, see.

This work focuses on the important subproblem of modeling error probability as a function of trial number for a particular task. Following the influential work of Corbett and Anderson, Knowledge Tracing has been used to solve this problem in many intelligent tutoring systems. Recent work has sought to overcome two limitations of the basic Knowledge Tracing model: its assumption that each observed data point requires the use of a single skill, and its assumption that model parameters are the same for all students. To address the first limitation, Additive Factor Models and Performance Factors Analysis use logistic regressions that include parameters for each skill involved in some trial. The second limitation has been addressed by adapting the basic Knowledge Tracing model to individual students, for example by fitting per-student odds multipliers, or by learning per-student initial mastery probabilities.

Our work seeks to address a third limitation of Knowledge Tracing: its strong assumptions about the shape of the learning curve. Following Knowledge Tracing, we first attempt to model performance on a task that requires only a single skill. In we generalize this approach to obtain a mixture model that includes both Additive Factor Models and Performance Factors Analysis as special cases, and that outperforms both on a large, real-world dataset.

2. SINGLE-TASK MIXTURE MODEL

In this section we present a simple mixture model that is appropriate for use on datasets with a single task. This model is a viable alternative to the basic (non-individualized) version of Knowledge Tracing, and is useful for exploratory data analysis. In we generalize this model to handle datasets with multiple tasks.

2.1 The Probabilistic Model

A student’s performance on a task after T trials can be represented as an error vector v \in {0,1}^T, where v_t = 1 if the student made an error on trial t and is 0 otherwise. Thus a task, together with a distribution over students, defines a distribution over binary error vectors. In this work, we model this distribution as a mixture of K distributions, where each component of the mixture is a learning curve, or equivalently a product of Bernoulli distributions (one for each trial).

To formally define this model, define the probability of observing outcome o \in {0,1} when sampling from a Bernoulli distribution with parameter p as

$$ \mathcal{B}(p,o)=\begin{cases}{p}&{o=1}\ {1-p}&{o=0\ .}\end{cases} $$

A learning curve q \in [0;1] specifies, for each trial t, the probability q_t that the student makes an error on trial t. The probability of the error vector v according to learning curve q is

$$ \prod_{t}\mathcal{B}(q_{t},v_{t}) $$

Inference in a mixture model consists of applying Bayes’ rule to compute a posterior distribution over the K components of the mixture, given an observed error vector. The model parameters can be fit from data using the EM algorithm, pseudo code for which is given in Algorithm 1.

Algorithm 1 EM Algorithm for single-task mixture model Parameters: number of components K, error vector v for each student s, prior parameters 1, 1.

Initialize p and q with random values. while not converged do

// Expectation step
Compute likelihoods and responsibilities.
// Maximization step
Update model parameters according to responsibilities.

end while

To make Algorithm 1 perform well when data is sparse, it is useful to place a Bayesian prior over the set of possible learning curves. In this work we use a product of Beta distributions for the prior: \mathbb{P}[q]=\prod_{t}\mathrm{Beta}(\alpha,\beta)(q_{t}). This choice of prior gives a simple closed form for the maximization step of the EM algorithm, which can be thought of computing the maximum-likelihood estimate of q after hallucinating 1 correct response and 1 error.

2.2 Knowledge Tracing as a Mixture Model

Knowledge Tracing is typically presented as a two-state Hidden Markov Model, where the student’s state indicates whether or not they have mastered a particular skill. In this section, we show that if the maximum number of trials is T, Knowledge Tracing can also be thought of as a mixture model with T + 1 components, each of which is a step function. Thus, Knowledge Tracing can be viewed as a constrained mixture model, in contrast to the unconstrained model discussed in the previous section.

To see this relationship, recall that in a Knowledge Tracing model, the student makes an error with slip probability p_s if they have mastered the skill, and with probability 1 - p_g otherwise, where p_g is the probability of a correct guess. The probability of mastery is p_0 initially, and after each trial, a student who has not yet mastered the skill transitions to the mastered state with probability p_T.

Let V be an error vector, so V_t = 1 if the student makes an error on trial t and is 0 otherwise, and let M be the state vector: M_t = 1 if the student has mastered the skill at the beginning of trial t and is 0 otherwise. The distribution over error vectors defined by Knowledge Tracing is given by

$$ \mathbb{P}[V=v]=\sum_{m}\mathbb{P}[M=m]\mathbb{P}[V=v|M=m]. $$

Because the student never leaves the mastered state after reaching it, there are only T + 1 possibilities for the state vector M. Letting m be the jth possibility (m_t= 0 if t < j, 1 otherwise), we have

$$ \mathbb{P}[V=v]=\sum_{j=1}^{T+1}p^{j}\cdot\mathbb{P}[V=v|M=m^{j}]. $$

Because the components of V are conditionally independent given M, it follows that $$ \mathbb{P}[V=v|M=m^{j}]=\prod_{t=1}^{T}\mathcal{B}(q_{t}^{j},v_{t}).$$

Thus, viewing Knowledge Tracing in this way, it is natural to consider generalizations that remove some of the constraints, for example allowing the step functions to have different initial or final heights. In the model presented in we simply remove all the constraints, allowing us to fit a mixture model over learning curves of arbitrary shape.

2.3 Statistical Consistency

A model is statistically consistent if, given enough data, it converges to the ground truth. In this section we show that the hard version of EM algorithm is consistent, provided the number of components in the mixture model grows with the amount of available data. For simplicity we assume the number of trials T is the same for all students, but this is not essential. Also, though the data requirements suggested by this analysis are exponential in T, in practice we find that near-optimal predictions are obtained using a much smaller number of components.

2.4 Use in an Intelligent Tutoring System

How should the predictions of a mixture model be used to schedule practice within an intelligent tutoring system? When using Knowledge Tracing, a typical approach is to schedule practice for a skill until the inferred probability of having mastered it exceeds some threshold such as 0.95. With a mixture model, we can no longer take this approach since we don’t make explicit predictions about whether the student has mastered a skill. Nevertheless, we can define a reasonable practice scheduling rule in terms of predicted future performance.

In particular, note that another way of formulating the scheduling rule typically used in Knowledge Tracing is to say that we stop practice once we are 95% confident that performance has reached an asymptote. With a mixture model, it is unlikely that the marginal value of practice will be exactly 0, so this precise rule is unlikely to work well. However, we can compute the expected marginal benefit of practice, and stop scheduling practice once this drops below some threshold.

3. EXPERIMENTS WITH SINGLE-TASK MODEL

In this section we evaluate the single-task mixture model on data from Duolingo. These experiments serve two purposes. First, they show that the mixture model can give much more accurate predictions than Knowledge Tracing on real data. Second, inspection of the learning curves produced by the mixture model reveals interesting facts about the student population that are not apparent from conventional learning curve analysis.

3.1 The Duolingo Dataset

We collected log data from Duolingo, a free language learning application with over 90 million students. Students who use Duolingo progress through a sequence of lessons, each of which takes a few minutes to complete and teaches certain words and grammatical concepts. For these experiments, we focus on listen challenges, in which the student listens to a recording of a sentence spoken in the language they are learning, then types what they hear.

For these experiments we use a simple bag-of-words knowledge component (KC) model. There is one KC for each word in the correct answer, and a KC is marked correct if it appears among the words the student typed.

3.2 Prediction Accuracy

To evaluate the mixture model’s prediction accuracy, we divided the Duolingo dataset into equal-sized training and test sets by assigning each student to one of the two groups at random. We then ran the EM algorithm on the training data to fit mixture models with various numbers of components, as well as a Knowledge Tracing model, and computed the predictions of these models on the test data.

1. Average log-likelihood. Average log-likelihood measures how probable the test data is according to the model.
2. AUC. AUC evaluates the accuracy of the model’s predictions when they are converted from probabilities to binary values by applying a threshold.

4. GENERAL MIXTURE MODEL

The single-task model is appropriate for datasets where there is a single knowledge component (KC) and many students. In an actual intelligent tutoring system, a student will learn many KCs, and prediction accuracy can be improved by using student performance on one KC to help predict performance on other, not yet seen KCs. In this section we present a more general mixture model that accomplishes this.

In this more general model, student performance is again modeled as a mixture of K learning curves. However, instead of treating each point on the learning curve as a separate parameter, we let it be the output of a generalized linear model with features that depend on the student, task, and trial number. For a student s and task i, the probability of a performance vector is given as an equation based on the link function for the generalized linear model.

5. EXPERIMENTS WITH GENERALIZED MODEL

In this section, we demonstrate the potential of the generalized mixture model by using it to learn a mixture of Additive Factor Models which models student performance on Duolingo listen challenges. We present how to perform inference for a new student, and discuss the implications of parameter sharing across components.

6. CONCLUSIONS

In this work we explored the use of mixture models to predict how students’ error rates change as they learn. This led to order-of-magnitude improvements over Knowledge Tracing in terms of prediction accuracy on single-task datasets from Duolingo. We hope this will inspire the use of mixture modeling more broadly as a general-purpose diagnostic tool for intelligent tutoring systems.