A Conceptual Model for End-to-End Causal Discovery in Knowledge Tracing

Nischal Ashok Kumar, Wanyong Feng, Jaewook Lee, Hunter McNichols, Aritra Ghosh, Andrew S. Lan

TL;DR

This paper introduces a novel "Causal GRU" module designed to discover prerequisite relationships between educational skills directly from student response data. By utilizing a differentiable permutation matrix and a learnable dependency structure, the model can perform end-to-end causal discovery while simultaneously predicting student performance, a significant step forward for automated curriculum design.

What Problem Does This Paper Address?

Knowledge Tracing (KT) is the task of modeling a student's mastery of skills over time based on their past performance. While deep learning models like Deep Knowledge Tracing (DKT) are excellent at predicting whether a student will get the next question right, they usually treat skills as a "flat" list. They fail to capture the underlying causal structure—for example, the fact that a student must master "Counting" before they can understand "Addition."

Traditionally, these prerequisite maps are built by human experts, which is time-consuming and hard to scale. Discovering these relationships automatically from observational data (student logs) is a "causal discovery" problem. The challenge is making this process end-to-end and differentiable so that the model can learn the causal graph and the student's knowledge state at the same time.

Methods

The authors propose a Causal Gated Recurrent Unit (GRU). The core innovation lies in how they mask the weight matrices of the GRU to enforce a causal structure.

  1. The Causal Mask ($M$): The model defines a mask $M = PLP^T$.
  2. $P$ (Permutation Matrix): Learns the causal ordering (which skill comes first).
  3. $L$ (Lower-Triangular Matrix): Represents the causal dependency (which specific skills influence others).
  4. The Sinkhorn Operator: Since permutation matrices are discrete and non-differentiable, the authors use the Sinkhorn operator. This relaxes the matrix into a "doubly stochastic" matrix, allowing the model to learn the ordering via standard backpropagation.
  5. Skill Embeddings: Instead of simple one-hot encodings, the model uses learnable dense embeddings (300D) to represent skills, which significantly increases the model's representational capacity.
  6. Adaptive Training: They use an adaptive strategy for the Sinkhorn operator, starting with a "soft" relaxation and gradually making it "harder" (closer to a true permutation) over the course of training.

Datasets

The model was evaluated using the dataset from Task 3 of the NeurIPS 2022 Challenge on Causal Insights for Learning Paths in Education.

  • Source: Eedi (an online education platform).
  • Scale: 1,855 unique skills (constructs) and 6,468 students.
  • Content: Student responses to multiple-choice diagnostic math questions.

Key Insights and Ideas

  • Separation of Order and Structure: By decomposing the mask into $P$ and $L$, the model can independently learn the sequence of skills and how densely they are connected.
  • Differentiable Discovery: The use of the Sinkhorn operator is the "secret sauce" that allows a discrete structural problem (finding a DAG) to be solved using gradient descent.
  • Embeddings are Essential: A major finding was that moving from no embeddings to 300-dimensional skill embeddings nearly tripled the $F_1$ score. This suggests that the "identity" and "context" of a skill are just as important as the causal link itself.
  • Sparsity vs. Density: The authors found that making the $L$ matrix learnable (rather than assuming every skill depends on all previous skills) improved results. This confirms that real-world learning paths are sparse; a skill usually only has a few direct prerequisites.

Key Results

The model was ranked among the top entries on the NeurIPS 2022 Challenge leaderboard. The authors performed an ablation study to show the impact of their design choices:

Model Variant Leaderboard $F_1$ Score
No Embeddings / No Adaptive Strategy 0.11
No Embeddings / With Adaptive Strategy 0.17
300D Embeddings / Adaptive Strategy 0.33
300D Embeddings / Adaptive / Learnable $L$ 0.43

Qualitatively, the model successfully recovered logical chains, such as: Counting $\rightarrow$ Fractions $\rightarrow$ Area of Simple Shapes $\rightarrow$ Volume.

Limitations and Future Work

  • Evaluation Constraints: Because the ground-truth causal structure of the challenge dataset was not publicly released, the authors could only evaluate based on leaderboard scores rather than a detailed local analysis.
  • Model Architecture: The current approach is tied to a GRU (RNN) architecture. The authors suggest that future work should explore applying this causal module to more modern, attention-based (Transformer) KT models.
  • Human-AI Collaboration: The authors envision a "human-in-the-loop" system where data-driven causal discovery assists human experts in refining curricula, rather than replacing them entirely.

Summary updated

Abstract

In this paper, we take a preliminary step towards solving the problem of causal discovery in knowledge tracing, i.e., finding the underlying causal relationship among different skills from real-world student response data. This problem is important since it can potentially help us understand the causal relationship between different skills without extensive A/B testing, which can potentially help educators to design better curricula according to skill prerequisite information. Specifically, we propose a conceptual solution, a novel causal gated recurrent unit (GRU) module in a modified deep knowledge tracing model, which uses i) a learnable permutation matrix for causal ordering among skills and ii) an optionally learnable lower-triangular matrix for causal structure among skills. We also detail how to learn the model parameters in an end-to-end, differentiable way. Our solution placed among the top entries in Task 3 of the NeurIPS 2022 Challenge on Causal Insights for Learning Paths in Education. We detail preliminary experiments as evaluated on the challenge's public leaderboard since the ground truth causal structure has not been publicly released, making detailed local evaluation impossible.
BibTeX
@inproceedings{kumar2023conceptual,
  author = {Nischal Ashok Kumar and Wanyong Feng and Jaewook Lee and Hunter McNichols and Aritra Ghosh and Andrew S. Lan},
  title = {{A Conceptual Model for End-to-End Causal Discovery in Knowledge Tracing}},
  booktitle = {EDM},
  year = {2023},
  url = {https://openreview.net/forum?id=58rxsu0Xi0},
}

Loading related content...

Figure