Knowledge Tracing with Sequential Key-Value Memory Networks

In plain words

Online courses and tutoring systems want to know which skills a student has already mastered, so they can pick the next exercise. This paper tackles that guessing game: given the answers a student has given so far, how likely is the next answer to be correct?

The model keeps a small memory with one slot per hidden skill, and each slot holds the student's current mastery of that skill. When a new question arrives, the model works out which skills it touches and reads the matching slots. After the student answers, the memory is updated: the skills involved are partly forgotten and partly strengthened, depending on whether the answer was right.

A second idea is about history. Questions that touch the same skills are linked together, and a recurrent network walks only along those links instead of through every past answer. The authors report that this gives better predictions than the earlier memory model on each of five benchmark datasets, and that the memory slots line up with question topics reasonably well.

TL;DR

SKVMN combines a DKVMN-style key-value memory with an LSTM whose cells connect only across exercises with the same attention pattern §3.2 §3.3. On five benchmarks the authors report the highest AUC against BKT, DKT and DKVMN, with gains of about 2 points over DKVMN on the four real datasets §5.2 tab. 3. Several details needed to rebuild the model are not stated (see Pitfalls).

Problem

Knowledge tracing (KT) models a student's knowledge state over time from a sequence of exercises. The task is to predict the probability that the student answers the next question correctly, given the question and the exercise history §2. The authors list two gaps in earlier deep KT models: DKT keeps one hidden state for the whole student, so it cannot trace individual concepts, and DKVMN updates its memory only from the latest exercise, so it misses long-range dependencies §1 §6.

The paper assumes questions map to N latent concepts, each with a mastery level that is not observed §2. The paper does not supply concept labels; it says training lets the model discover the concepts §3.4.

Method

Notation: questions are indexed by q in Q; an exercise is (q_t, y_t) with y_t in {0, 1} §2. The model predicts p_t = P(y_t = 1 | q_t, history) §2.

Memory §3.1. A key matrix M^k of size N x d_k is fixed after training. A value matrix M^v of size N x d_v holds the student's concept states and is rewritten after each answer §3.1.

Attention §3.2.1 eq. 1. The question is one-hot encoded and multiplied by an embedding matrix A to give k_t. The attention vector w_t is the softmax over the N slots of the inner products between k_t and the key slots eq. 1. No scaling factor is stated.

Read §3.2.2 eq. 2 eq. 3. The read vector r_t is the w_t-weighted sum of the value slots eq. 2. A tanh layer over the concatenation of r_t and k_t gives the summary vector f_t eq. 3. The text says f_t carries the student's mastery of the question's concepts plus the question's difficulty prior §3.2.2.

Sequential dependency §3.3.1 eq. 8. Each attention vector is mapped to an identity vector d_t: each component is classed as low, medium or high by one of three triangular membership functions eq. 8. Two questions with the same identity vector are treated as similar. Question q_t depends on an earlier exercise at t - lambda if both have the same identity vector and no later exercise in the history has it. The history is thereby split into chains, one per identity §3.3.1 fig. 2.

Hop-LSTM §3.3.2 eq. 9 to eq. 15. At step t, if a dependent earlier exercise exists, the LSTM cell for q_t takes f_t and the hidden state h_{t-lambda} from that exercise, and produces c_t and h_t eq. 9 to eq. 14. The gates are the forget gate (written g_t), input gate i_t and output gate o_t eq. 9 to eq. 11. The prediction is a sigmoid over W_2 applied to h_t eq. 15. Cells are linked only along dependency chains, so unrelated exercises are skipped.

Write §3.2.3 eq. 4 to eq. 7. After the answer y_t is seen, the pair (f_t, y_t) is encoded as a vector of length 2|Q| and multiplied by an embedding matrix B to give a write vector v_t §3.2.3. An erase vector e_t eq. 4 and an add vector a_t eq. 6 are computed from v_t. Each slot i first becomes M~(i) = M(i) * (1 - w_t(i) * e_t) eq. 5, then M_{t+1}(i) = M~(i) + w_t(i) * a_t eq. 7. This write uses the summary vector f_t, which the authors contrast with DKVMN's write, which uses the question and answer only §3.2.3 §5.4.

Training §3.4 eq. 16. The loss is the binary cross-entropy summed over time steps eq. 16. Memory matrices and A, B are Gaussian-initialised; weights use Glorot uniform initialisation. Only parameters of the LSTM cells on the current chain receive gradient from that prediction §3.4.

# Predict p_t for the next question  [§3.1] [eq. 1-3] [eq. 8-15]
# Input:  question (int), key_matrix (N, d_k), value_matrix (N, d_v)
# Output: p_t, probability of a correct answer

def predict(question, key_matrix, value_matrix, lstm_state):
    # Embed the question: one-hot times A  [§3.2.1]
    k_t = one_hot(question) @ A              # (d_k,)
    # Attention over key slots: softmax of inner products  [§3.2.1] [eq. 1]
    w_t = softmax(key_matrix @ k_t)          # (N,)
    # Read: attention-weighted sum of value slots  [§3.2.2] [eq. 2]
    r_t = w_t @ value_matrix                 # (d_v,)
    # Summary vector: tanh over [r_t, k_t]  [§3.2.2] [eq. 3]
    f_t = tanh(W1.T @ concat(r_t, k_t) + b1)
    # Identity vector from the attention vector  [§3.3.1] [eq. 8]
    d_t = identity_vector(w_t)               # rule not stated, see Pitfalls
    # Hop: latest earlier exercise with the same identity  [§3.3.1]
    lam = latest_index_with_identity(d_t)    # no match: not stated
    # Hop-LSTM cell, fed by the state of that exercise  [§3.3.2] [eq. 9-14]
    h_t, c_t = hop_lstm_cell(f_t, lstm_state[lam])
    # Output probability  [§3.3.2] [eq. 15]
    p_t = sigmoid(W2.T @ h_t + b2)
    return p_t, h_t, c_t, f_t, w_t

# Triangular membership: low, medium or high  [§3.3.1] [eq. 8]
# a, b, c per dataset: not stated (set empirically [§4.4])

def membership(x, a, b, c):
    rising = (x - a) / (b - a)
    falling = (c - x) / (c - b)
    return max(min(rising, falling), 0.0)

# Memory write after the answer y_t is observed  [§3.2.3]
# Input:  w_t (N,), f_t (summary before the answer), y_t in {0, 1}
# Output: value matrix for step t+1, (N, d_v)

def write(value_matrix, w_t, f_t, y_t):
    # Encode (f_t, y_t) as a length-2|Q| vector times B  [§3.2.3]
    # How the dense f_t is encoded is not stated, see Pitfalls
    pair = encode_pair(f_t, y_t)             # (2|Q|,)
    v_t = pair @ B                           # (d_v,)
    # Erase and add vectors  [§3.2.3] [eq. 4] [eq. 6]
    e_t = sigmoid(W_e.T @ v_t + b_e)         # (d_v,)
    a_t = tanh(W_a.T @ v_t + b_a)            # (d_v,)
    # Erase, then add, each slot weighted by w_t(i)  [eq. 5] [eq. 7]
    for i in range(N):
        erased = value_matrix[i] * (1 - w_t[i] * e_t)
        value_matrix[i] = erased + w_t[i] * a_t
    return value_matrix

Hyperparameters

Values are as printed in the paper. Every row not marked "not stated" comes from the text or tables named in the Where column.

Results

Author-reported. Metric: area under the ROC curve (AUC, %) on the test split §4.3 §4.4. Baselines follow their original procedures §4.4.

Main comparison tab. 3. Mean ± standard deviation over five runs.

Source: tab. 3. Text: SKVMN is at least 2 points above DKVMN on the four real datasets §5.2.

Memory size and dimension tab. 2. SKVMN and DKVMN were run on the same (d, N) grid. Bold marks the best AUC per dataset and model in the paper. The m column is the parameter count as printed.

Datasets tab. 1. Synthetic-5: 50 questions, 4,000 students, 200,000 exercises. ASSISTments2009: 110, 4,151, 325,637. ASSISTments2015: 100, 19,840, 683,801. Statics2011: 1,223, 333, 189,297. JunyiAcademy: 722, 199,549, 25,628,935 §4.1 tab. 1.

Concept clusters §5.3 fig. 5 tab. 4. On ASSISTments2009, both models are said to find 10 latent concepts over 110 questions. The authors report that SKVMN's clusters overlap less than DKVMN's, and they check a few questions against the textual descriptions in tab. 4. No quantitative clustering metric is reported.

Knowledge-state evolution §5.4 fig. 1. For one student over 50 exercises on ASSISTments2009, the authors show that SKVMN's concept-state updates are smoother than DKVMN's. This is a qualitative, single-student illustration.

Figures. fig. 1 heatmaps of concept states, DKVMN vs SKVMN §1. fig. 2 architecture (embedding, memory, sequence and output layers) and sequential dependencies §3.1. fig. 3 the write process §3.2.3. fig. 4 ROC curves for the four models on five datasets §4.3 §5.2. fig. 5 clusters of ASSISTments2009 questions by DKVMN and SKVMN §5.3.

Runtime. The paper says the Hop-LSTM makes inference faster §1 §3.3.1, but it reports no runtime or FLOP numbers §5.

Paper vs code

No official code.

Searches done for this card, all without a match:

• The arXiv abstract, the LaTeX source and the compiled PDF contain no code link. Their only links are dataset pages in the footnotes of §4.1.
• GitHub repository search for "skvmn", "sequential key-value memory knowledge tracing" and "knowledge tracing memory". The results were DKVMN reimplementations by other people and unrelated projects. None was used.
• GitHub user search for "ghodai" (matching the first author's first name). The account found does not match this paper, so it was not used.

Pitfalls

• Identity vector rule. §3.3.1 says similar attention vectors get the same identity vector, and the example maps each component to low, medium or high §3.3.1. The rule that turns the N component classes into one identity vector is not stated. With N components and three classes, the number of possible identities is large. An implementer has to choose a key, such as the full tuple or a hash, and this choice decides which exercises link.
• Triangular parameters. a, b and c are not given for any dataset §3.3.1 §4.4. Without them, eq. 8 cannot be instantiated.
• No earlier exercise. §3.3.2 defines the Hop-LSTM step only when a dependent exercise exists. The state for the first exercise of a chain, and for an identity that has not occurred, is not stated.
• Forget gate name. The forget gate is written g_t, and the input gate i_t eq. 9 eq. 13. The naming is unusual but the update is standard: keep the forget gate as the multiplier of c_{t-lambda}.
• f_t encoding in the write. §3.2.3 says (f_t, y_t) is a vector of length 2|Q| before multiplication by B. f_t is dense, of size d_k, so a one-hot length-2|Q| vector cannot contain it as printed. How f_t enters the write vector is not stated.
• Optimiser text. §3.4 calls the method stochastic gradient descent, and §4.4 uses Adam with momentum 0.9. Only the Adam description gives hyperparameters, so an implementation should follow §4.4.
• Learning-rate schedule. §4.4 says 0.01, annealed by a cosine function every 15 epochs for 120 epochs, then fixed at 0.001. It does not say whether each 15-epoch cycle restarts at 0.01, or whether the schedule is a single cosine decay from 0.01 to 0.001.
• Choosing N and d. §4.4 says validation chose d_k and d_v. It does not say that N was validated. tab. 2 reports AUC for every grid point with bold maxima, and the bold maxima equal the tab. 3 values (for example 83.63 and 83.6). So tab. 2 appears to report test AUC, but the paper does not say so. Treat the choice as made on test data unless verified.
• Parameter-count claim. §5.1 says SKVMN has fewer parameters on ASSISTments2009 and JunyiAcademy. That compares SKVMN's best row with DKVMN's best row. At matching (d, N), SKVMN has more parameters, for example 7.8k vs 7k at d = 10, N = 10 on ASSISTments2009 tab. 2.
• Sequence length conflict. §3.3.1 gives an average ASSISTments2009 sequence length of 233 ± 100. tab. 1 gives 78 exercises per student, which matches 325,637 / 4,151. The paper does not explain the difference. Check the unit (per sequence or per student) before building a batcher.
• Batch loss and padding. eq. 16 sums the loss over t. Whether the sum is averaged over the batch, and how padded steps are masked, is not stated.
• Datasets. All five are third-party, and the paper gives only URLs in its footnotes §4.1. Their licences are not stated here. Check them before redistributing data.
• Synthetic-5 and single-run gaps. SKVMN beats DKVMN by 1.3 points on Synthetic-5 (84.0 vs 82.7). The text presents this as a clear win §5.2, but the authors give no significance test. The difference is larger than the reported standard deviations.
• Interpretability claims. The concept clusters and the smoothness of the evolution plots rest on visual judgement, one dataset and one student §5.3 §5.4. The paper gives no quantitative measure for these claims.

Lineage

• Builds on: DKVMN (Zhang et al., 2017) for the key-value memory and the erase-and-add write §3.1 §3.2.3 [bib: DKVMN17]. DKT (Piech et al., 2015) for the recurrent sequence model §1 [bib: DKT2015_5654]. Memory-augmented networks (Graves et al., 2016) §6 [bib: Graves2016].
• Changes from DKVMN: the write uses the summary vector f_t, not only the question and answer §3.2.3; an LSTM runs over identity-linked exercises §3.3.2.
• Compared against: BKT (Corbett and Anderson, 1994), DKT and DKVMN §4.2.
• Superseded by: not known from content in this wiki.