Source-linked AI summary
Knowledge Tracing Machines: Factorization Machines for Knowledge Tracing
Jill-Jênn Vie, Hisashi Kashima
TL;DR
Knowledge tracing must predict student outcomes from chronologically observed, often sparse interactions while accounting for learning and side information. The paper uses classification factorization machines as Knowledge Tracing Machines, showing that they encompass established educational models and perform well across datasets. KTMs also support higher-dimensional, interpretable student models, but the paper is limited to pairwise interactions and vanilla DKT cannot directly handle multiple skills.
Problem
Knowledge tracing requires predicting student outcomes over questions from sparse, chronological observations, while existing approaches use temporal latent-variable or factor-analysis models.
Method
The paper introduces classification factorization machines as Knowledge Tracing Machines, combining sparse feature biases and embeddings with pairwise interactions.
Results
Each existing model is matched or outperformed by a KTM across the reported datasets, including deep neural networks.
Takeaways & Limitations
KTMs provide a testbed for combining side information and learn interpretable log-bilinear embeddings that can support student feedback.
Takeaways & Limitations
The paper is limited to pairwise interactions, while vanilla DKT cannot handle multiple skills directly and instead treats skill combinations as new skills.
Abstract
from arXiv · showhide
Knowledge tracing is a sequence prediction problem where the goal is to predict the outcomes of students over questions as they are interacting with a learning platform. By tracking the evolution of the knowledge of some student, one can optimize instruction. Existing methods are either based on temporal latent variable models, or factor analysis with temporal features. We here show that factorization machines (FMs), a model for regression or classification, encompasses several existing models in the educational literature as special cases, notably additive factor model, performance factor model, and multidimensional item response theory. We show, using several real datasets of tens of thousands of users and items, that FMs can estimate student knowledge accurately and fast even when student data is sparsely observed, and handle side information such as multiple knowledge components and number of attempts at item or skill level. Our approach allows to fit student models of higher dimension than existing models, and provides a testbed to try new combinations of features in order to improve existing models.
Related Work
Prior knowledge-tracing work includes temporal sequence models and factor-analysis models with temporal features. The paper situates KTMs among BKT, DKT, IRT, AFM, PFA, FAST, and factorization-machine approaches.
- BKT models learner knowledge as a hidden Markov process, while FAST extends tracing to questions involving multiple subskills.
- DKT applies LSTM sequence modeling to student outcomes, but factor-analysis models have matched its performance on some Assistments variants.
- Factor analysis generalizes observations through common factors and can incorporate temporal features such as attempt counters.
- The Rasch model predicts outcomes from student ability and question difficulty, and IRT can outperform DKT even without temporal features.
- AFM counts attempts by skill, whereas PFA separates successful and unsuccessful attempts; AFM is a special case of PFA when γ_k = δ_k.
- Prior factorization-machine work used regression for student modeling, whereas this paper introduces its classification form for student modeling.
Knowledge tracing machines
Knowledge Tracing Machines model binary student outcomes from sparse event features using feature biases and embeddings with pairwise interactions. The framework supports arbitrary feature combinations, including student, item, and side-information features.
- KTMs are a family of models introduced for predicting binary right-or-wrong outcomes in knowledge tracing.
- Features may represent students, exercises, knowledge components, learning opportunities, or learning-environment information such as device type.
- Only active features in the sparse event vector contribute to each prediction.
- Each feature has a scalar bias and a d-dimensional embedding, allowing the model to combine logistic-regression terms with pairwise interactions.
Data and encoding of side information
The data encoding represents each chronological student-question event as a sparse feature vector. It can augment student and item indicators with skills, learning-opportunity counters, outcomes, and contextual metadata.
- The encoding process begins by selecting which learning-platform features will be represented in the sparse vector.
- Students and questions are encoded with one-hot features that identify the participants in each observation.
- Knowledge-component features mark the skills involved in the observed question.
- Opportunity counters encode how many chances a student has had to learn an involved skill.
- Separate success and failure features distinguish opportunities following correct from incorrect attempts.
- Additional metadata, including school, teacher, and test type, can be concatenated with the sparse features.
- In the worked example, the encoding uses N = n + m + 3s = 14 features for users, items, skills, wins, and fails.
Relation to existing models
Knowledge tracing machines recover several established educational models as special cases by changing feature encodings, bias structure, and embedding dimension.
- Bias-only models: With d = 0, knowledge tracing machines reduce to weighted sums of feature biases.The pairwise interaction term disappears, leaving only feature biases.
- IRT: One-hot student-and-question features recover the 1-PL IRT, or Rasch, model after reparameterizing student and question biases.Student biases are set to θ_i − µ, while question biases are set to −d_j.
- Factor-analysis models: Skill-level encodings with successful and unsuccessful attempt counters make the model behave like PFA and similarly recover AFM.The encoding uses the q-matrix together with wins and fails for each skill.
- Multidimensional models: For d > 0, knowledge tracing machines become multidimensional IRT models with a user bias.The same user-and-item one-hot encoding is paired with learned embeddings and their inner products.
Training
KTM training minimizes negative log-likelihood under Bayesian parameter priors and uses Gibbs sampling for probit-linked models, with an implementation available through pywFM.
- Objective: Training minimizes negative log-likelihood over observed feature vectors and binary outcomes.The objective is evaluated across S observations and their labels.
- Regularization: Gaussian priors regularize each feature bias and embedding component, while Gaussian and Gamma hyperpriors govern their regularization parameters.Both biases and embedding components use mean µ and precision λ through the stated hierarchical priors.
- Inference: With a probit link, the model can be fitted using Gibbs sampling because the link is the inverse CDF of the normal distribution.The implementation follows the Gibbs-sampling computations described by the cited factorization-machine work.
- Implementation: The authors train KTMs with the MCMC Gibbs sampler in libFM2 through a Python wrapper called pywFM.The sampler implementation is written in C++ and exposed through Python.
Visualizing the embeddings
KTM embeddings provide a visual representation of users, items, and skills, enabling an example-level interpretation of a student's performance.
- Interpretation: A two-dimensional Fraction-dataset embedding links WALLE's item and skill correlations to difficulty solving a specific subtraction item.WALLE correlates positively with most items but not skills 2 and 7, which are required by item 5.
Experiments
The experiments use datasets varying in users, items, skills, observations, sparsity, and repeated attempts, including several sources with knowledge-component metadata.
- Dataset characteristics: Table 2 characterizes datasets by users, items, skills, skills per item, observed entries, sparsity, and average attempts per user-item pair.The table is intended to compare datasets with different shapes and sizes.
- Temporal structure: Temporal datasets allow repeated attempts on the same question, so students may learn between attempts.Repeated observations preserve the chronological structure relevant to knowledge tracing.
- Assistments: The Assistments dataset contains 4,217 students, 26,688 questions, 123 KCs, and 347k observations, with extra school, teacher, action, and tutor-mode information.Its items involve zero to four KCs, with 146 observed KC combinations.
- Berkeley: The Berkeley dataset has 1,730 students, 234 questions, 29 KCs, and 650k entries, with exactly one KC per question.The dataset comes from an online computer-science course.
- Other datasets: The remaining datasets span fully specified user-question observations and include 58,939 students over 17 tasks, 2,922 over 28 language items, 536 over 20 fraction questions, and 757 over 23 TIMSS questions.Their reported KC counts and entry totals vary across CS, language, fractions, and mathematics.
Framework
Knowledge tracing machines encode temporal student interactions and recover several established educational models as special cases. Their evaluation uses cross-validation and standard classification metrics across model encodings.
- Temporal encoding: Temporal datasets convert student-item outcomes into skill-level counts of successful and unsuccessful attempts before KTM training.The preprocessing uses the q-matrix to aggregate wins and fails by skill.
- Evaluation: The experiments use 5-fold cross-validation, training on one partition and predicting outcomes in the held-out partition.Different KTM encodings, including those corresponding to existing models, are evaluated in each fold.
- Evaluation: Performance is averaged across folds using accuracy, area under the curve, and negative log-likelihood.Training runs use dataset-specific epoch counts selected to reach convergence.
- Special cases: AFM corresponds to skills and attempts with d = 0, while PFA corresponds to skills, wins, and fails with d = 0.These encodings are presented as temporal special cases of KTMs.
- Special cases: IRT is represented by users and items with d = 0, whereas MIRT with a user bias is represented by users and items with d > 0.These are listed as special cases applicable across datasets.
Results and Discussion
KTMs match or outperform existing student-modeling approaches across the evaluated datasets. Results show benefits from side information, item-specific biases, and wins-versus-fails features, while higher latent dimensions add little on temporal datasets.
- Overall results: Each existing model is matched or outperformed by a KTM across the evaluated datasets.The experiments report results in Tables 3–7 and Figure 3, with a summary in Table 5.
- Assistments: 0.815 > 0.743 AUC: KTM(iswfe0) outperformed DKT on Assistments while training in 4 minutes 30 seconds versus DKT’s 1 hour.KTM(iswfe0) is logistic regression with items, skills, fails, and extra information at d = 0.
- Assistments: Assistments KTM(iswfe0) achieved higher performance than vanilla DKT by using additional side information and logistic regression.The paper notes that logistic regression is less prone to overfitting.
- Wins and fails: +0.07 AUC for Assistments and +0.01 for Berkeley: wins-and-fails encoding improved performance over attempts-only encoding.KTM models using wins and fails also improved over IRT by +0.07 and +0.02 AUC, respectively.
- Item bias: +0.07 AUC in Assistments and +0.09 in Berkeley: item-specific bias improved KTM(iswf0) over the PFA encoding.The authors attribute this to learning item difficulty, especially when many items differ in difficulty.
- Item bias: Item bias produced a large improvement on all datasets except Fraction.For Fraction, the paper suggests that clearly specified skills may already characterize items sufficiently.
- Latent dimension: Less than +0.01 AUC: higher-dimensional models produced only slight gains on temporal datasets with extensive attempt features.The paper contrasts this with a separate task where d = 20 improved AUC by +0.03 over d = 0.
Further work
The paper discusses how side information could extend deep knowledge tracing and support adaptive testing. It also identifies future extensions and a current limitation to pairwise interactions.
- Deep knowledge tracing: Randomly shuffling students between train and test evaluates generalization to entirely new students.The experiments compare the expressiveness of student-modeling approaches under this split.
- Side information in deep knowledge tracing: Vanilla DKT cannot handle multiple skills without treating skill combinations as new skills, preventing information transfer between skills.The paper suggests that DKT could instead be combined with side information.
- Adaptive testing: KTMs extend IRT and MIRT with extra information such as knowledge components and multiple attempts, supporting possible adaptive-testing use.IRT and MIRT were originally designed to choose the next question based on previous answers.
- Future features: Response time and elapsed time since an item was last asked are proposed as additional features for modeling learning and spaced repetition.The paper cautions against encoding noisy outputs from other machine-learning algorithms.
- Higher-order factorization machines: The method is limited to pairwise interactions, leaving higher-order factorization machines as a future research direction.Higher-order models would generalize interactions to k-way terms.
- Future extensions: Graded outcomes could be modeled with the same KTM framework using thresholds, analogous to graded response models in item response theory.The paper leaves this extension for future work.
Conclusion
Knowledge tracing machines encompass existing EDM models and support classification-based knowledge tracing. Across varied datasets, they estimate parameters under sparse observations, improve predictions, and provide interpretable embeddings for feedback and feature refinement.
- Knowledge tracing machines encompass existing EDM models as special cases for classification-based knowledge tracing.
- Across datasets of varied sizes and characteristics, KTMs estimate user and item parameters despite sparse observations and improve predictions over existing models, including deep neural networks.
- KTMs support refining feature encodings according to observation level, attempt-counting choices, and additional information sources.
- Because KTMs are log-bilinear models, their learned embeddings are interpretable and can provide useful feedback to students.