Deep Factorization Machines for Knowledge Tracing

Deep Factorization Machines for Knowledge Tracing

Jill-Jenn Vie
RIKEN Center for Advanced Intelligence Project
Nihonbashi 1-4-1, Mitsui Building 15F
Chuo-ku, 103-0027 Tokyo, Japan
vie@jill-jenn.net

Abstract

This paper introduces our solution to the 2018 Duolingo Shared Task on Second Language Acquisition Modeling (SLAM). We used deep factorization machines, a wide and deep learning model of pairwise relationships between users, items, skills, and other entities considered. Our solution (AUC 0.815) hopefully managed to beat the logistic regression baseline (AUC 0.774) but not the top performing model (AUC 0.861) and reveals interesting strategies to build upon item response theory models.

1 Introduction

Given the massive amount of data collected by online platforms, it is natural to wonder how to use it to personalize learning. Students should receive based on their estimated knowledge, tailored exercises and lessons, so they can be guided through databases of potentially millions of exercises.

With this objective in mind, numerous models have been designed for student modeling (Desmarais and Baker, 2012). Based on the outcomes of students, one can infer the parameters of these so-called student models, measure knowledge, and tailor instruction accordingly.

In the 2018 Duolingo Shared Task on Second Language Acquisition Modeling (Settles et al., 2018), we had access to attempts of thousands of students over sentences (composed of thousands of possible words, each of these being labeled as correct or incorrect), and we had to predict whether a student would write correctly or not the words of a new sentence. Sentences were annotated with precious side information such as lexical, morphological, or syntactic features. This problem is coined as knowledge tracing (Corbett and Anderson, 1994) or predicting student performance (Minaei-Bidgoli et al., 2003) in the literature. In this particular challenge, it is done at the word level.

In this paper, we explain the motivations that led us to our solution, and show how our models handle typical models in educational data mining as special cases. In Section 2, we show related work. In Section 3, we present the existing model of DeepFM and clarify how it can be applied for knowledge tracing, notably the SLAM task. In Section 4, we detail the data preparation, in order to apply DeepFM. Finally, we expose our results in Section 5 and further work in Section 6.

2 Related Work

Item Response Theory (IRT) models (Hambleton et al., 1991) have been extensively studied and deployed in many real-world applications such as standardized tests (GMAT). They model the ability (level information) of students, and diverse parameters of items (such as difficulty), and involve many criteria for the selection of items to measure the ability of examinees.

Related work in knowledge tracing consists in predicting the sequence of outcomes for a given learner. Historically, Bayesian Knowledge Tracing (BKT) modeled the learner as a Hidden Markov model (Corbett and Anderson, 1994), but with the advent of deep learning, a Deep Knowledge Tracing (DKT) model has been proposed (Piech et al., 2015), relying on long short-term memory (Hochreiter and Schmidhuber, 1997). However, Wilson et al. (2016) have shown that a simple variant of IRT could outperform DKT models.

All of these IRT, BKT or DKT models do not consider side information, such as knowledge components, which is why new models naturally rose. Vie and Kashima (2018) have used Bayesian factorization machines for knowledge tracing, and recovered most student models as special cases.

3 DeepFM for knowledge tracing

Each instance can be encoded as a sparse vector $ \boldsymbol{x} $ of size N: each component will be set at a certain value (for example, 1 if the category of the corresponding entity is discrete, the value itself if it is continuous, and 0 if the entity is not present in the observation). For each instance, our model will output a probability $ p(\boldsymbol{x})=\psi(y_{FM}+ y_{DNN}) $ , where $ \psi $ is a link function such as the sigmoid $ \sigma $ or the cumulative distribution function (CDF) $ \Phi $ of the standard normal distribution.

$$ p(x)=\psi(y_{F M}+ $$

The DeepFM model is made of two components, the FM component and the Deep component.

3.1 FM component

Given an embedding size d $ \in $ N, the output of a factorization machine is the following:

$$ y_{F M}=\sum_{k=1}^{N}w_{k}x_{k}+\sum_{1\leq k<l\leq N}x_{k}x_{l}\langle v_{k},v_{l}\rangle $$

The first term shows that a bias $ w_{k}\in \mathbf{R} $ is learned for each entity k. The second term models the pairwise interactions between entities by learning a vector $ v_{k}\in \mathbf{R}^{d} $ for each entity k.

Wide and deep learning models have been proposed by Google (Cheng et al.,2016) to learn outputs based on categorical and continuous inputs in learning tasks.

3.2 Deep component

The deep component is a L-layer feedforward neural network that outputs:

$$ y_{D N N}=\mathrm{R e L U}(W^{(L)}a^{(L)}+b^{(L)}) $$

where each layer $ 0\leq \ell < L $ verifies:

$$ a^{(\ell+1)}=\text{ReLU}(W^{(\ell)}a^{(\ell)}+b^{(\ell)}) $$

For learned parameters W, a,b for each layer; the first layer is given by the corresponding $ v_{i_c} $ embeddings of the activated entities.

3.3 Training

Training is performed by minimizing the log loss of the output probabilities compared to the true outcomes of the students over the tokens. For all models trained, the optimizer was Adam (Kingma and Ba, 2014), with learning rate $ \gamma=10^{-3} $ and minibatches of size 1024.

4 Encoding the Duolingo Dataset

4.1 Fundamental, discrete categories

4.2 Noisy discrete categories

Duolingo was providing the SyntaxNet features (morphosyntactic rules) such as:

4.3 Continuous categories

4.4 Encoding

In the baseline model provided by Duolingo, all fundamental features were encoded as a concatenation of n-hot encoders. Then they used logistic regression and achieved AUC 0.772. Here are the models we considered:

ACC AUC NLL F1
IRT+attempts 0.833 0.739 0.411
Basic IRT 0.838 0.752 0.399
LR baseline 0.838 0.772 0.391 0.284
Vanilla FM 0.824 0.773 0.414
DeepFM* 0.811 0.382
DeepFM 0.815 0.329

Table 1: Performance of all tested algorithms.

5

We first tried different models on a validation set.

5.1 On validation set

A vanilla FM was used considering $ \psi=\Phi $ the CDF of the standard normal distribution as link function. Then, for our experiments, we used the TensorFlow implementation of DeepFM provided by Alibaba on GitHub.

5.2 On test set

The DeepFM model managed to improve the baseline by 3 points AUC. We got AUC 0.815, while the top performing solution had AUC 0.861.

6 Further Work

We could embed the dependency graph provided by Duolingo in the encoding of the vanilla FM. Ensemble methods such as xgboost (Chen and Guestrin, 2016) could be considered, as typically encountered in challenges.

7 Conclusion

In this paper, we showed how to use deep factorization machines for knowledge tracing. Our findings show interesting combinations of features, together with embeddings provided by deep neural networks. In some way, it shows how to learn dense embeddings from the sparse features typically encountered in learning platforms.

References