Source-linked AI summary
Towards an Appropriate Query, Key, and Value Computation for Knowledge Tracing
Youngduck Choi, Youngnam Lee, Junghyun Cho, Jineon Baek, Byungsoo Kim, Yeongmin Cha, Dongmin Shin, Chan Bae, Jaewe Heo
TL;DR
Knowledge tracing needs better ways to model complex exercise-response relations and to choose attention queries, keys, and values. The paper proposes SAINT, a Transformer encoder-decoder that separately processes exercise and response embeddings, and reports state-of-the-art performance with a 1.8% AUC improvement over the current state-of-the-art model.
Problem
Knowledge tracing models use shallow attention and have not thoroughly explored alternative query, key, and value constructions for modeling student learning activities.
Method
SAINT is a Transformer-based encoder-decoder model that separately feeds exercise embeddings to the encoder and response embeddings to the decoder.
Results
1.8% AUC improvement over the current state-of-the-art model, SAKT, was reported on the large-scale EdNet knowledge tracing dataset.
Takeaways & Limitations
Separately processing exercises and responses with deep self-attentive computations is reported as effective for knowledge tracing.
Takeaways & Limitations
Prior knowledge tracing models evaluated in the paper commonly use shallow attention and the same exercise-query, interaction-key/value recipe, limiting the explored design space.
Abstract
from arXiv · showhide
Knowledge tracing, the act of modeling a student's knowledge through learning activities, is an extensively studied problem in the field of computer-aided education. Although models with attention mechanism have outperformed traditional approaches such as Bayesian knowledge tracing and collaborative filtering, they share two limitations. Firstly, the models rely on shallow attention layers and fail to capture complex relations among exercises and responses over time. Secondly, different combinations of queries, keys and values for the self-attention layer for knowledge tracing were not extensively explored. Usual practice of using exercises and interactions (exercise-response pairs) as queries and keys/values respectively lacks empirical support. In this paper, we propose a novel Transformer based model for knowledge tracing, SAINT: Separated Self-AttentIve Neural Knowledge Tracing. SAINT has an encoder-decoder structure where exercise and response embedding sequence separately enter the encoder and the decoder respectively, which allows to stack attention layers multiple times. To the best of our knowledge, this is the first work to suggest an encoder-decoder model for knowledge tracing that applies deep self-attentive layers to exercises and responses separately. The empirical evaluations on a large-scale knowledge tracing dataset show that SAINT achieves the state-of-the-art performance in knowledge tracing with the improvement of AUC by 1.8% compared to the current state-of-the-art models.
INTRODUCTION
Knowledge tracing supports personalized educational agents by modeling students’ understanding from learning activities over time. The paper identifies shallow attention and unexamined query-key-value choices as limitations, then proposes SAINT, which separates exercise and response processing in an encoder-decoder Transformer.
- Motivation: Knowledge tracing predicts a student’s understanding from learning activities, supporting resource assignment tailored to individual ability and needs.It can estimate the probability that a student correctly answers a given exercise.
- Limitations: Previous attention-based models use shallow attention layers that may miss complex relationships among exercises and responses over time.Several prior models use only one attention layer, and one reported decreased performance when self-attention was stacked.
- Limitations: Prior models also commonly use exercises as queries and interactions as keys and values, while alternative query-key-value combinations remain insufficiently explored.The paper motivates testing choices such as self-attention on exercises or responses.
- Proposed approach: SAINT uses an encoder-decoder Transformer that separately processes exercise embeddings and response embeddings with repeated self-attention and encoder-decoder attention.The encoder processes exercises as queries, keys and values; the decoder processes responses and attends to encoder outputs.
- Evaluation: SAINT was evaluated on EdNet, a large-scale dataset containing 627,347 users, 72,907,005 response data points, and 16,175 exercises.The study compares SAINT with current state-of-the-art models and Transformer-based variants.
- Results: 1.8% AUC gain was reported for SAINT compared with the current state-of-the-art knowledge tracing model.The paper reports state-of-the-art performance in knowledge tracing.
RELATED WORKS
Knowledge tracing models student knowledge from learning activities over time, evolving from traditional approaches to neural architectures. Deep learning models outperform traditional methods but retain shallow attention and underexplored query, key, and value configurations.
- Knowledge Tracing: Knowledge tracing models a student’s state of knowledge over time to predict performance on exercises and tailor educational resources.The task uses learning-activity histories to estimate the probability of correctly answering a target exercise.
- Traditional Approaches: Bayesian Knowledge Tracing represents knowledge as binary concept states updated by a hidden Markov model using student responses.
- Deep Learning Approaches: Deep learning models such as EKT, NPA, and SAKT have outperformed traditional knowledge-tracing models.EKT and NPA use attention-enhanced Bi-LSTMs, while SAKT uses a Transformer with exercises as queries and past interactions as keys and values.
- Limitations: Existing deep knowledge-tracing models use shallow attention layers that may not capture complex sequential relationships among exercises and interactions.SAKT uses a single attention layer, while EKT and NPA use deep LSTMs but still only one attention layer between interactions and exercises.
- Limitations: Existing models also use a common exercise-query, interaction-key/value recipe without thoroughly exploring alternative feature combinations.Self-attention over exercises or responses is identified as an unexplored possibility.
Input Representation
SAINT represents exercise and response histories as separate embedding sequences built by summing vectors for their constituent attributes. The input attributes include exercise identity, category, position, response value, elapsed time, and timestamp information.
- Input Representation: SAINT maps exercise and response information to latent vectors, producing separate exercise and response embedding sequences.The response sequence is one position shorter because the model predicts the next response from prior responses.
- Response Embeddings: Response embeddings include vectors for response values, with response values encoded as 0 or 1.
- Shared Attributes: Position embeddings represent sequence positions and are shared across the exercise and response sequences.
- Temporal Attributes: Elapsed response time is rounded to integer seconds, represented from 0 through 300, and capped at 300 seconds.
- Temporal Attributes: Timestamp embeddings encode each possible combination of month, day, and hour when an exercise was received.
- Exercise Embeddings: Exercise embeddings sum vectors for exercise ID, exercise category, and sequence position.
Transformer-based variants of deep knowledge tracing models
SAINT uses a Transformer encoder-decoder architecture that processes exercise and response embeddings separately. Causal masking prevents predictions from using future information.
- Encoder-Decoder Architecture: The encoder processes the exercise embedding sequence and passes its output to the decoder.The encoder output is denoted O and contains one processed representation for each exercise position.
- Encoder-Decoder Architecture: The decoder combines the encoder output with a response-embedding sequence beginning with a start token to produce predicted responses.
- Network Components: The encoder and decoder stack multi-head attention networks followed by feed-forward networks.
- Causal Masking: SAINT masks future inputs in every multi-head attention network so each prediction depends only on preceding exercises and responses.
- Input Embeddings: Exercise embeddings combine exercise ID, category, and position, while response embeddings combine response value and position; interaction embeddings are not used in SAINT.
Multi-head Attention Networks
SAINT’s multi-head attention projects queries, keys, and values into latent spaces, weights values by query-key relevance, and aggregates multiple attention heads. Causal masking removes attention to subsequent positions.
- Attention Inputs: Multi-head attention receives sequences of queries, keys, and values and applies attention repeatedly with different projection matrices.The repeated attention computations form multiple heads over the same input sequence.
- Projection: The attention layer projects queries, keys, and values into a latent space using separate matrices.
- Attention Weights: Query-key dot products determine each value’s relevance to a given query.
- Causal Masking: Future-position masking replaces upper-triangular attention scores with −∞, causing subsequent attention weights to become zero after softmax.
- Attention Computation: Each attention head multiplies values by masked attention weights, with dot products scaled by the square root of the query-key dimension.
- Head Aggregation: The model concatenates the attention heads and multiplies them by an output matrix to aggregate their outputs.
Feed-Forward Networks
SAINT applies position-wise feed-forward networks after multi-head attention to add non-linearity, with encoder layers repeated identically and using skip connections and layer normalization.
- Position-wise feed-forward networks add non-linearity to the multi-head attention output.
- Weight matrices and bias vectors are shared across different M_i operations.
- The encoder is built from N identical layers combining feed-forward and multi-head attention networks.
- Skip connections and layer normalization are applied to each encoder sub-layer.
Decoder
The decoder stacks identical attention and feed-forward layers, using response embeddings as its initial input and encoder outputs for cross-attention before producing response probabilities.
- The decoder is a stack of N identical layers containing multi-head attention followed by feed-forward networks.
- The decoder layer applies two multi-head attention operations, with the second using encoder output O alongside M1.
- The first decoder layer uses the response sequence with start-token embeddings as queries, keys, and values.
- The final prediction layer applies a linear transformation and sigmoid to produce a sequence of probability values.
Transformer based Variants of Deep Knowledge Tracing
The paper compares SAINT with three deeply stacked Transformer-based knowledge-tracing variants that differ in masking strategy, input sequence, or attention organization.
- The compared variants are LTMTI, UTMTI, and SSAKT, alongside SAINT.
- LTMTI: LTMTI encodes past interactions and decodes with the current exercise as queries, using the encoder output as keys and values.
- LTMTI: LTMTI uses lower triangular masks, restricting each output to the exercise and the most recent preceding interactions.
- LTMTI: LTMTI effectively augments training by learning from histories truncated to multiple lengths.
- UTMTI: UTMTI follows SAINT’s architecture but uses past interactions in the encoder and the exercise sequence in the decoder.
SSAKT
SSAKT extends SAKT by applying self-attention to exercises before exercise-interaction attention, and the experiments use the large-scale EdNet dataset and Santa application context.
- SSAKT: SSAKT applies self-attention to exercise embeddings before using them as queries in exercise-interaction attention.
- SSAKT: SSAKT addresses the reported decrease in AUC when SAKT’s attention block is stacked multiple times.
- Dataset: EdNet records each user’s Timestamp, Exercise ID, Exercise category, Response, and Elapsed time.
- Dataset: Santa is an AI tutoring system supporting self-study for the TOEIC Listening and Reading Test.
- Dataset: EdNet contains 16,175 exercises, 72,907,005 responses, and 627,347 users solving more than one exercise.
Training Details
SAINT is evaluated against established knowledge-tracing and collaborative-filtering models using standard metrics, while attention visualizations examine how its encoder and decoder distribute attention.
- Evaluation: SAINT is compared with MLP, NCF, NPA, and SAKT using AUC and ACC.AUC measures sensitivity against 1−specificity, while ACC measures the proportion of correct predictions.
- Attention Analysis: SAINT’s encoder attention is sparse, whereas its decoder self-attention is dense across responses.The encoder attends to a few relevant exercises, while decoder attention values spread over many responses.
- Attention Analysis: Encoder-decoder attention heads show either diagonal focus on corresponding exercises or vertical stripes across selected exercises.These patterns indicate different ways decoder heads attend to the exercise sequence.
- Attention Analysis: Later decoder blocks distribute attention more evenly than early blocks, indicating broader attention over response values.The paper interprets this progression as increasingly complex relationships being incorporated through successive decoder blocks.
Ablation Study
Ablation studies identify a strong SAINT configuration and test whether richer response embeddings improve performance. The reported results favor deep, separately applied attention layers, while additional response metadata does not improve results.
- Architecture: SAINT gives the best result among the evaluated architectures when deep attention layers are applied separately to exercises and responses.The comparison varies model architectures and hyper-parameters, including stacked attention layers.
- Architecture: The best-performing SAINT model has 4 layers, latent dimension 512, ACC 0.7368, and AUC 0.7811.LTMTI models also show high ACC and AUC overall, with the paper attributing this to lower-triangular-mask data augmentation.
- Embedding Ablation: Using exercise category, timestamp, and elapsed time in response embeddings did not improve results over the simpler embedding configuration.Embedding B adds these features to the positional information and response value used by Embedding A.
- Conclusion: The conclusion identifies separately feeding exercise and response sequences to the encoder and decoder as ideal for the evaluated knowledge-tracing tasks.The paper also reports that attention patterns differ between encoder and decoder.
- Conclusion: SAINT outperforms existing state-of-the-art knowledge-tracing models on the evaluated large-scale dataset.This conclusion follows the paper’s reported evaluation of the proposed model.