[논문] Dynamic Key-Value Memory Networks for Knowledge Tracing (2017)

guungyul 2025. 1. 23. 21:50

기존 모델들인 Bayesian Knowledge Tracing과 Deep Knowledge Tracing은 각 개념에 대한 지식 수준을 분리해서 나타낸다는 단점과 어느 개념을 학생이 어려워하거나 잘하는지 알 수 없는 문제가 있다. 본 논문에서는 Dynamic Key-Value Memory Networks (DKVMN)을 소개한다. 이 모델은 문제에 내포되어있는 개념을 이용하고 학생의 숙련도를 직접적으로 출력할 수 있다. 모델은 지식 개념들을 나타내는 정적인 matrix key와 학생의 숙력도를 나타내는 동적인 matrix value를 사용한다.

이 포스트는 논문의 모든 내용을 포함하지 않는다.

1. Introduction

Bayesian Knowledge Tracing (BKT)

학생의 지식 수준$s_t$은 서로 다른 개념 수준 {$s_t^I$}로 분석된다
- 각 개념 수준을 따로따로 나타낸다
각 개념 수준을 binary latent variable로 나타내고 Hidden Markov 모델을 사용해 사후 분포를 업데이트한다
단점
- 따라서 BKT는 다른 개념간 관계를 포착할 수 없다
- 또 각 개념 수준의 evolvement를 너무 간략화해 모델링한다

Deep Knowledge Tracing (DKT)

Long short-term memory (LSTM)을 활용
- Underlying 지식 수준 S를 고차원 연속적인 공간으로 나타낸다
단점
- DKT는 모든 개념에 대한 학생의 지식 수준을 하나의 hidden state로 표현
  - 학생의 각 개념에 대한 숙련도를 알 수 없음

Dynamic Key-Value Memory Networks (DKVMN)

각 개념 간 관계를 활용할 수 있다
- Input 문제와 underlying 개념들의 상관관계를 자동으로 학습 가능
각 개념에 대한 개념 지식 수준을 추적할 수 있다
- 각 timestamp에 연관된 개념들만 업데이트가 됨

3 Model

3.2 Dynamic Key Value Memory Networks

DKVMN에서는 기억 구조를 모델링하기 위해 두가지 matrix를 사용한다.

각 timestamp에 exercise tag $q_t$를 입력 받고 정오답 확률 $p(r_t|q_t)$를 출력한다.

$q_t$는 Q개의 서로 다른 exercise tag 중 하나
$r_t$는 0 또는 1

추가로 모든 문제에 대한 N개의 잠재적인 개념 {$c^1, c^2, ..., c^N$}이 존재한다 가정한다.

Key matrix $M^k$: 잠재적인 개념들이 저장됨
Value matrix $M_t^v$: 학생의 각 개념에 대한 숙련도 {$s_t^1, s_t^2, ..., s_t^N$}이 저장됨

DKVMN은 input 문제와 key matrix로 계산된 correlation weight로 value matrix에 쓰고 읽으면서 학생의 지식 수준을 추적한다.

3.2.1 Correlation Weight

Input은 문제 $q_t$는 먼저 embedding matrix A와 곱해져 연속적인 embedding vector $k_t$로 나타내진다.

$k_t$는 각 key matrix의 column과 곱해지고 softmax를 거쳐 correlation weight를 계산한다.

$w_t(i) = Softmax(k_t^TM^k(i))$
- $w_t$는 문제와 각 latent concpet 사이의 상관관계를 나타낸다.

3.2.2 Read process

각 문제 $q_t$에 대해 read content $r_t$는 value matrix의 모든 메모리 slot들의 weighted sum으로 계산된다:

$r_t = \sum_{i=1}^N w_t(i) , M_t^v(i).$
$r_t$는 이 문제에 대한 학생의 숙련도 summary로 취급된다

Read content $r_t$와 input 문제 embedding $k_t$를 연결한 후 Tanh activation의 fully connected layer를 통과시켜 summary vector $f_t$를 얻는다.

$f_t=Tanh(W_1^T[r_t,k_t]+b_1)$
$f_t$는 학생의 숙련도와 문제의 prior difficulty를 포함한 summary로 취급된다

최종적으로 $f_t$는 또다른 fully connected layer를 통과해 학생의 성과를 예측한다.

$p_t = Sigmoid(W_2^Tf_t+b_2)$
$p_t$는 문제의 정오답률

3.2.3 Write Process

학생이 문제를 답한 후 학생의 정오답에 따라 value matrix를 업데이트 한다.

$(q_t, r_t)$의 joint embedding과 위와 같은 correlation weight $w_t$를 사용해 value matrix를 업데이트 한다.

Tuple $(q_t, r_t)$를 embedding matrix B에 곱해 knowledge growth $v_t$를 계산한다.

학생의 knowledge growth를 value 부분에 더할 때 memory는 먼저 삭제된다. (LSTM의 forget gate에서 영감받음)

이 erase vector $e_t$는 $v_t$와 correlation weight로 계산된다:

$e_t = Sigmoid(E^Tv_t+b_e)$
- $e_t$는 $d_v$ 차원의 column vector

이전 timestamp의 value component 안에 있는 memory vector들은 다음과 같이 변경된다:

$\tilde{M}t^v(i) = M{t-1}^v(i)\left[1 - w_t(i)e_t\right],$

Memory 삭제 후 add vector $a_t$로 각 memory slot을 업데이트 한다.

$\mathbf{a}_t = \text{Tanh}(\mathbf{D}^T \mathbf{v}_t + \mathbf{b}_a)^T,$
- $a_t$는 $d_v$ 차원의 row vector

Value memory는 각 timestep마다 다음과 같이 업데이트 된다:

$M_t^v(i) = \tilde{M}_{t-1}^v(i) + w_t(i)\mathbf{a}_t.$

위 erase-followed-by-add 기법은 학습 과정에서 각 개념 수준에 대한 학생의 망각과 강화를 가능하게 한다.

3.2.4 Training

훈련 과정에서는 모든 embedding matrix A와 B, 다른 parameter들, 그리고 $M^k$와 $M^v$의 초기값이 cross enthropy loss를 줄이는 방향으로 학습된다:

$\mathcal{L} = -\sum_t \left(r_t \log p_t + (1 - r_t) \log(1 - p_t)\right).$

DKVMN은 fully differentiable하고 stochastic gradient descent 기법으로 쉽게 학습 가능하다.

4 Experiments

4.3 Student Performance Prediction

특이점으로 DKVMN 모델은 overfitting에 취약하지 않다.

Figure 3을 보면 validation error와 training error가 epoch가 늘어나도 큰 차이를 보이지 않는다