Jill-Jênn Vie
email: jill-jenn.vie@inria.fr

Hisashi Kashima

Deep Knowledge Tracing is an implicit dynamic multidimensional item response theory model

Keywords: Knowledge Tracing, Item Response Theory, Side Information

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Adaptive testing and personalized learning are precious technologies that have been enabled by tracing the knowledge of previous students. They rely on a response model of the learners: if we know how people learned in the past, we can optimize testing or learning for new students. This is the model-based approach of reinforcement learning, commonly referred to as knowledge tracing in the educational data mining literature.

Formally, knowledge tracing relies in predicting the outcomes of students on some items, given their previous interactions on some items. Numerous models have been proposed for knowledge tracing such as deep knowledge tracing (DKT) proposed by [START_REF] Piech | Deep knowledge tracing[END_REF] that relies on a recurrent neural network (RNN). However, [START_REF] Wilson | Back to the basics: Bayesian extensions of IRT outperform neural networks for proficiency estimation[END_REF] have matched the performance of DKT with a unidimensional item response theory (IRT) model that can be seen as online logistic regression. In order to advance the field, we need to understand what distinguishes these models, and how to build upon them. For example, we can notice that these models do not rely on the exact same data. IRT usually learns a difficulty parameter per item while DKT were initially strictly used on skill data for the sake of the comparison with Bayesian knowledge tracing (BKT).

In this paper, we show how we can bridge both categories of models using an encoder-decoder architecture. These architectures are usually encountered in sequence-tosequence scenarios such as machine translation [START_REF] Cho | Learning phrase representations using RNN encoder-decoder for statistical machine translation[END_REF] and got popular with the rise of transformers [START_REF] Vaswani | Attention is all you need[END_REF]. We open the "black box" of DKT and explain how it relates to existing, well known models.

Our main contribution is an encoder-decoder architecture that takes DKT, IRT and other models such as Performance Factor Analysis (PFA) as special cases. We demonstrate using several real datasets that it seems better to learn unidimensional parameters for item, skills, which is not what the vanilla DKT model does, relying instead on multidimensional parameters for skills. In this paper, we are not so much interested in state-of-the-art performance but in understanding how models are related to each other and how to interpret their parameters, so that they can also be visualized. We notably show that metadata considered can have a considerable impact on performance.

We first expose related work, then our approach: summarize & predict. We subsequently detail our datasets, experiments, and see the influence of specific components of our architecture in the results.

Background and related work

Formally, knowledge tracing can be defined as follows. Let us denote I the set of items of some test, and the number of knowledge components assessed. For each student, at each time step , we know the sequence of items and outcomes already given to the student (here, time is excluded as it is what we want to predict) where q τ ∈ I and a τ ∈ {0 , 1 }. We may as well have some side information about such as the knowledge components (KCs) required by q t denoted , sometimes represented by a binary vector from in a so-called -matrix that indicates which knowledge components are assessed. Using this information, we need to predict outcome using a model that estimates a probability . We will note σ the sigmoid function : σ : x ↦ 1/(1+ exp (-x )). We now describe some models for knowledge tracing, of two different kinds.

Sequence-based architectures

Deep knowledge tracing models. Deep knowledge tracing (DKT) is usually described as a black-box model that takes into input pairs from some student, and outputs a vector of probabilities y such that y k is the probability that the student will answer correctly an item requiring skill k. More precisely, in a DKT model, the actual probability that a certain user correctly answers an item that requires skill k at time t (event R t k =1) is given by: where is a representation of the skill k learned by DKT that does not evolve over time and h t =L S T M ( h t -1 , q t ,a t ) if , otherwise, is a representation of the user that evolves over time. [START_REF] Montero | Does deep knowledge tracing model interactions among skills[END_REF] have shown that DKT can trace knowledge efficiently even when skills are interleaved, and that it shares information between skills. In the original DKT paper, [START_REF] Piech | Deep knowledge tracing[END_REF] assume that each item is only related to one skill among 1 , … , K . They learn a joint representation in for the pair ( s t ,a t ) where s t =K C ( q t ), because they claim that separate representations for s t and a t degraded performance. When there are too many pairs ( s t ,a t ), they use fixed low- dimensional representations instead of {0 ,1 } 2 K , which can be seen as setting a random embedding for each pair. It makes sense to use skill instead of items for encoding the actions of the student, in order to have redundancy and avoid the item cold-start problem. The drawback is that in their vanilla form, DKTs cannot handle multiple skills per item. In this paper, we show in particular how multiple skills can be taken into account, which can be used to improve DKT.

In DKT-DSC, an extension of DKT, [START_REF] Minn | Deep knowledge tracing and dynamic student classification for knowledge tracing[END_REF] use an encoding of the triplet ( s t ,a t , c t ) as input metadata where c t is a dynamic clustering information of the student based on a vector counting successful and unsuccesful attempts, updated at each time step. They managed to outperform DKT on several datasets. [START_REF] Ding | Why deep knowledge tracing has less depth than anticipated[END_REF] have shown that the encoder of DKT with untrained, random weights, is a strong baseline; which seems to indicate that the latent state can be a random embedding of the sequence while the final fully connected layer is mainly responsible for the good predictive performance.

More recently, transformers have been proposed for knowledge tracing [START_REF] Pandey | A self-attentive model for knowledge tracing[END_REF][START_REF] Ghosh | Context-aware attentive knowledge tracing[END_REF]. Self-attention can be used to model how the samples we want to predict relate to previous observations from the student.

Non-sequence-based architectures

Multidimensional item response theory (MIRT). In item response theory, one usually does not assume that the examinee's ability evolves over time. The probability that user i correctly answers item j (event ) is: where is a learned representation of user i called multidimensional ability, is a learned representation of item j called discrimination parameter and is a bias parameter representing the easiness of item j. This model is popular in the psychometric literature, because it can enable computerized adaptive testing: adapting the assessment, given the currently estimated performance of the student. It is indeed possible to make the model dynamic by updating the maximum likelihood estimate (MLE) of at each new observed point, which can take time to estimate. This is exactly what [START_REF] Wilson | Back to the basics: Bayesian extensions of IRT outperform neural networks for proficiency estimation[END_REF] do, to demonstrate a better performance of updated IRT compared to DKT. Maximum likelihood estimation (MLE) is possible with simple models such as IRT, but for more complex architectures or priors, it is not always feasible because it increases time complexity during the test phase. This is why simpler online updates have been proposed such as multivariate Elo [START_REF] Abdi | A multivariate ELO-based learner model for adaptive educational systems[END_REF] to train dynamic MIRT models.

Performance Factor Analysis and count-based models. Several models rely on attempt counts, such as Additive Factor Model (AFM) and Performance Factor Analysis (PFA) proposed by [START_REF] Pavlik | Performance factors analysis-a new alternative to knowledge tracing[END_REF]. The estimated ability of the student at time is a linear function of their number of previous successful and unsuccessful attempts over skill k up to time (again, time information is excluded, as it is not observed yet at prediction time). An important remark is that here, we forget the order in which the items were solved, we are considering mere counts. DAS3H proposed by [START_REF] Choffin | DAS3H: Modeling Student Learning and Forgetting for Optimally Scheduling Distributed Practice of Skills[END_REF] maintains counters in several time windows, which enables the modeling of forgetting. In PFA, p t depends on a weighted sum of the counts, according to the knowledge components that are assessed at time t and specified in : where parameters w= ( β , γ , δ ) are learned, respectively scalar parameters for skills, wins, fails. Please note that this formulation can handle multiple skills.

Knowledge Tracing Machines. [START_REF] Vie | Knowledge Tracing Machines: Factorization Machines for Knowledge Tracing[END_REF] have shown that it is possible to learn representations for all users, items, skills in a test and combine them in a pairwise manner. Interestingly, most existing models for knowledge tracing such as IRT, PFA, MIRT are special cases of KTMs, according to the representations considered in the modeling. In this paper we want to emphasize the importance of metadata. [START_REF] Gervet | When is deep learning the best approach to knowledge tracing?[END_REF] have also shown that predicting performance at the item level instead of at the skill level could improve performance of DKT.

Our approach: summarize & predict

We see all these models through the same lens: our architecture relies on two main components, an encoder E that summarizes prior data and a decoder D that predicts student performance; both are trained jointly. They respectively require an expression of the metadata of former actions from the student and metadata of assessment at time t: which item is being attempted, which skills are being assessed, etc.

In particular, where denotes the empty sequence. In this expression, h t represents the learned representation of the user at time t, and p t the probability that the attempt of the student at time will be correct. Please note that this modeling is rich enough to encompass broader tasks than knowledge tracing, for example we can model the event that some user watched the video of some lesson, with the corresponding metadata. If we can take advantage of this kind of data, we can hopefully recommend new videos to some student to optimize their learning.

Summarize: encoding a dynamic representation of what happened

The encoder is a function of past history. It can either be simple counts to remember how many times a student succeeded or failed an attempt at a single skill, or a more complex function like a RNN in the case of DKT:

E D K T : h t =R N N ( h t -1 , q t , a t ) if , otherwise.
In order to share information across items, it is common to use pairs as sequence inputs where . If is associated with multiple KCs, some tricks consist in taking one at random, or creating a new skill that represents the combination of multiple skills.

Predict: combine the learned representations to make a prediction

The objective of the decoder is to combine the learned representation h t of the student at time t with some parameters involved in the assessment at time t such as which item was administered, which skills were assessed, etc.

In order to build a decoder we need to decide two main characteristics: what is the metadata taken into account for the prediction (item , skills , wins , fails ), and what is the embedding size of those features.

Output metadata

If the output is solely based on item ID, we get a model like IRT or MIRT according to the embedding size of items. If the output is based on skill IDs , number of successful attempts (wins ), number of unsuccessful attempts (fails ), and the embedding size is 1, we get a model similar to PFA.

Decoder of same embedding size as

As an example, MIRT computes a dot product of the user embedding (usually denoted as in the literature, here for consistency) and the embedding of item (usually called discrimination, here ), plus a bias representing the easiness of the item (here, ):

The vanilla DKT model has a fully connected layer that converts the latent state to the prediction of performance of every possible skill. In practice, we are only interested in the skill assessed at time (assumed single by DKT) and DKT implicitly computes a dot product of the user embedding and the skill embedding , leading to the following expression:

Now, what should strike the reader is that the expressions of and are almost the same: only the metadata is different, item ID for MIRT and skill ID for DKT. This is why DKT, in its item output form, can be seen as a dynamic MIRT model, where a RNN looks at the sequence of observations to estimate ability parameters at current time. See Figure 1 for an illustration.

In fact, [START_REF] Gervet | When is deep learning the best approach to knowledge tracing?[END_REF] have shown an improvement in performance when considering items as output of DKT instead of skills as output.

Decoder of different embedding size than encoder

The encoder usually needs a high dimensional embedding to encode learning dynamics, notably if it is a RNN. The item and skill embeddings do not need to be the same dimension as the latent state . Indeed, in practice, most hard baselines for knowledge tracing such as PFA only model skill parameters with one dimension. This is why we suggest reducing the dimension of before making the predictions, using a fully connected layer :

where parameters and are learned. In the most extreme example, can be scalar, i.e. unidimensional, . The advantage is that it drastically reduces the number of parameters. For example, a decoder of embedding size 1 using (item, skill, wins, fails) as metadata would be a blend of IRT and PFA models and would look like this:

where weights are learned for each item and weights are learned for each skill. We will denote such a decoder as "iswf " later on. Another advantage of this decoder compared to vanilla DKT is that it can consider multiple skills associated to . To see how embeddings of higher dimension can be considered for multiple metadata, see [START_REF] Vie | Knowledge Tracing Machines: Factorization Machines for Knowledge Tracing[END_REF].

Evaluation

We optimize the log-loss, also known as mean negative log-likelikood:

L (a , p )= ∑ t=1 T log ( 1 -| a t -p t |) .
This log-loss can be computed for a batch of students, but we have to take into account that all students did not attempt the same number of items, so student sequences within a batch may have different lengths.

Once the parameters of the encoder E and the decoder D have been trained, for a new student it is easy to unroll the encoder on the sequence of outcomes ( q t , a t ) encoded as input metadata, get the corresponding latent states h t , and feed them to the decoder with the output metadata to get the predictions, and compute performance metrics.

We report all results according to their accuracy (ACC) and area under the curve (AUC).

Experiments

The code of our experiments is on GitHub: https://github.com/jilljenn/dktm.

Models

We tried different combinations of encoders and decoders. As sequence-based encoder, we used a RNN of latent dimensionality d where the encoding of actions ( q t , a t ) is sampled from a Gaussian multivariate distribution of dimension d and fixed. We used GRU (Gated Recurrent Unit) because it has fewer parameters than LSTM (Long Short-Term Memory), so it is less prone to overfitting [START_REF] Chung | Gated feedback recurrent neural networks[END_REF]. In the reported results, when encoder is listed as "none", it means only the wins and fails parameters and were counted. Decoders are described by a -gram among letters "iswf", respectively item, skill, wins and fails; and an embedding size . Examples of decoders are given in the previous section. The corresponding baselines are:

• DKT, which has a RNN as encoder and multidimensional embeddings within its decoder. The decoder can either be "s" if DKT makes predictions at skill level or "i" if DKT makes predictions at item level. • PFA just keeps track of successful and unsuccessful attempts so there is no sequence-based encoder; important metadata is skill, wins, fails so "swf" and the embedding size is 1 as scalar parameters are learned. • Decoders "swf " (PFA) and "iswf " are particular cases of logistic regression (LR) with sparse features.

Datasets

We tried our approach on the following datasets that have diverse characteristics.

Fraction. 536 middle-school students attempting 20 fraction subtraction exercises requiring 8 KCs such as, being able to put fractions at the same denominator. All students attempted all items, so this dataset is fully specified. The dataset and description of KCs can be seen in [START_REF] Decarlo | On the analysis of fraction subtraction data: The DINA model, classification, latent class sizes, and the Q-matrix[END_REF]. This dataset is particularly interesting because it is small scale, so complex models may overfit. Also, most items measure several KCs at the same time. As we have access to the full response pattern of all students, we assume that items are solved from item 1 to item 20.

Assistments 2009. 346,860 attempts of 4,217 students over 26,688 math items requiring 123 KCs (Feng et al., 2019). Some of the items require multiple KCs, up to 4. Students attempted between 1 and 1,382 exercises.

Berkeley. 562,201 attempts of 1,730 students over 234 CS-related items in a MOOC provided by Berkeley. Items can be of 29 categories, that we used as KCs. Each item belongs to a single category. Students attempted between 2 and 1,020 exercises. This dataset is private.

Data preparation

We used 5-fold cross-validation: we split each dataset into 5 folds, predict any of them using the remaining ones, and average the results. In practice there are many challenges, fortunately already known in the natural language processing community.

Batching. Whenever there are too many data points, in order to save memory we need to sample a batch of users. So the log-loss is computed on a batch.

Sequences of uneven lengths. Within a batch, different users may have attempted a different number of questions. However for efficiency, it is better to vectorize as much as possible and compute the log-loss over matrices. So we use a mask to know where the sequences end for each student.

Long sequences. On long sequences, DKT is hard to train. First, it may forget information on a long sequence, second the computation of the gradient may take time, vanish to zero or conversely get arbitrary high. As a remedy, we train on windows of fixed size called BPTT: backpropagating through time [START_REF] Werbos | Backpropagation through time: What it does and how to do it[END_REF]. The latent state of the previous batch is fed to the next batch.

Implementation details

We optimize our model using the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] with learning rate γ=0.005 and weight decay λ=0.0005 (equivalent to regularization). We train using 100 minibatches and use time windows of size 100. For the RNN, we used GRU with one layer, no dropout and latent dimensionality 2 or 50. Our implementation is in PyTorch. We ran the Fraction dataset experiments on CPU and the Assistments and Berkeley dataset experiments on GPU. Training was stopped after 200 epochs.

Results and Discussion

Results are shown in Tables 1 to 3 where the best models are shown in bold. For all datasets, we discovered models that outperformed the vanilla DKT model. More precisely, decoders of embedding size outperform decoders of higher embedding size. This seems to indicate that, although sequence-based encoders (GRU) may be better in some cases to learn the dynamics of student knowledge, it is always better to represent assessment information (items, skills) as scalars, to avoid overfitting. Besides improving the performance, reducing parameters induces a speedup in training and allows interpretability.

On the large datasets Assistments and Berkeley, logistic regression, that uses a simple counter of successful and unsuccessful attempts at skill level, is among the top models. It seems to indicate that for big datasets, logistic regression may be enough, because the number of prior successes and failures is enough to predict. What is even more surprising, is that on the small dataset Fraction, the top performing model uses a recurrent neural network as encoder. It may be because the sequences are small: every student only attempts 20 items. So the sequences of successes and failures make students more unique than their counters of successes, inducing a more personalized estimation.

Considering an item bias does not improve a lot the quality of the predictions on the Fraction dataset, maybe because the fraction subtraction task is particularly easy to describe using KCs, so the KCs are enough to characterize the items. However, on Assistments, one can see the improvement when considering an item bias, see the difference between PFA and LR (0.06 improvement in AUC). Same goes for Berkeley (0.09 improvement in AUC), where the KCs are actually mere categories of items.

Conclusion

Most models in the educational data mining literature model users, items and skills with multidimensional parameters. In this study though, we showed that while it is indeed important to model the dynamics of the students with multidimensional parameters, the items do not necessarily need to be multidimensional to come up with really strong models. In particular, logistic regression is among the top models. This is encouraging because we come up with better models that have fewer parameters. DKT may be slow to train not because of the recurrent neural network but because of the fully connected layer at the output, that contains the most parameters. In this paper, we suggest to replace it with a lower-dimensional layer.

As future work, we plan to try to use other kinds of side information. For example, for the Duolingo SLAM dataset [START_REF] Settles | Second language acquisition modeling[END_REF] for second language acquisition modeling, contestants had to predict whether a learner would get a word correct, and the best approaches were combinations of DKT with word embeddings [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. Using word content, be it only -gram features, allows to learn what phonemes are harder for which categories of people. Also we will try to encode richer actions for the encoder, because it is costly for humans to define the knowledge components related to all items, and deep learning models may be able to recover most of those with little supervision, reducing the workload on practitioners.

Figure 1 .

 1 Figure 1. DKT is implicitly a dynamic MIRT model.

Table 1 .

 1 Results on the Fraction Dataset

	Model Ours LR PFA DKT DKT	Encoder GRU None None GRU GRU	Decoder iswf iswf swf i s	ACC 0.880 0.853 0.854 0.772 0.761	AUC 0.944 0.918 0.917 0.844 0.839

Table 2 .

 2 Results on the Assistments Dataset

	Model LR Ours DKT PFA	Encoder None GRU GRU None	Decoder iswf iswf i swf	ACC 0.714 0.711 0.691 0.682	AUC 0.748 0.726 0.701 0.686

Table 3 .

 3 Results on the Berkeley Dataset

	Model Ours LR DKT PFA	Encoder GRU None GRU None	Decoder iswf iswf i swf	ACC 0.707 0.704 0.684 0.630	AUC 0.778 0.775 0.751 0.683

Acknowledgements

We thank Samuel Girard for his insightful comments. This work has been supported by JST CREST Grant Number JPMJCR21D1.