Dkvmn_논문_리뷰

DKVMN(Dynamic Key-Value Memory Networks for Knowledge Tracing)

0. Abstract

• DKVMN은 기저에 있는 개념(concept) 사이의 관계와 각 개념 당 학생의 이해도를 표현할 수 있다.
• 위 모델은 key라고 불리는 지식 개념을 저장하는 고정된(staic) metrix와, value라고 불리는 개념에 반응하는 이해도를 저장하고 업데이트하는 역동적(dynamic) metrix로 이뤄져있다.
• 위 모델은 사람이 수행한 것처럼 문항의 개념을 발견할 수 있고, 학생의 지식상태 변화를 그릴 수 있다.

1. 개요

• 학생이 문항을 얼마나 정확히 맞출지는 그 학생이 기저 개념을 얼마나 잘 알고 있는지, 즉 학생의 지식상태에 기반한다.
• KT(knowledge tracing)의 목표는 학생의 과거 문항풀이에 따라 학생의 지식상태를 추적하는 것이다.

과거 모델의 문제를 극복하기 위한 DKVMN

• BKT(Bayesian Knowledge Tracing): 개념을 아는 것과 모르는 것으로 이진 분류를 하기 때문에 다른 개념 사이의 관계를 포착하지 못한다.
• DKT(Deep Knowledge Tracing): 학생의 지식 상태를 하나의 hidden state에 요약하기 때문에 특정 개념을 얼마나 깨우쳤는지 알기 어렵고, 어느 개념에 강하고 약한지 특정하지 못한다.
• DKVMN : 개념 간의 관계를 이용하는 능력과 각 개념 성취 단계를 추적하는 능력의 결합으로 이뤄졌다. 모델은 입력 문항과 기본 개념 사이의 상관관계를 자동으로 학습하고 각 개념에 대한 개념 상태를 유지할 수 있다.
• 각 timestamp마다 오직 관련된 개념 상태만 업데이트 된다. 예를 들어 아래 그림에서, 새 문항 $q_{t}$가 입력되면 모델은 $q_{t}$와 관련된 개념 $c_{j}$와 $c_{k}$를 찾는다. 그런 다음 해당 개념 상태인 $s^j_{(t-1)}$과 $s^k_{(t-1)}$를 읽고 학생이 그 문항에 대한 어떤 대답을 할 것인지 예측한다. 그 문항을 학생이 완료하면, 모델이 두 개념상태를 업데이트하고 그 개념상태는 학생의 지식상태 S이 된다.
• 위 모델은 개념간 표현을 저장하는 고정적 metrix ‘key‘와 학생의 각 개념별 이해도를 저장하는 역동적 metrix ‘value‘를 가지고 있다.(python dictionary와 같이 불변의 key, 변동의 value 구조에서 차용됨) key가 생성되면 test동안에는 고정된다,

2. 모델 구조

• DKVMN은 각 타임스템프에서 문항 $q_{t}$를 받고 응답 p($q_{t}$

  $q_{t}$)의 확률을 출력한 다음, 문항&응답 튜플 ($q_{t}$, $q_{t}$)로 메모리를 업데이트 한다.

  • ($q_{t}$는 문항번호, $r_{t}$는 응답이며 0,1중 하나)
• N개의 잠재 개념 {$c^1, c^2, …, c^N$}을 key metrix(N x $d^k$)안에 저장한다.
• 각 개념에 대한 학생의 이해도(개념상태) {$s^{1}{t}, s^{2}{t}, …, s^{N}_{t}$}를 시간 t에 따라 바뀌는 value metrix(N x $d^v$)에 저장한다.
• DKVMN은 입력 문항과 key metrix에서 계산된 상관 가중치(correlation weight)를 사용하여 value metrix을 읽고 쓰면서 학생의 지식을 추적한다.

Correlation Weight

• 입력 문항 $q_{t}$는 embedding 행렬 A(총 문항 수 Q x $d_{k}$)에 의해 행렬곱하여 $d_{k}$차원의 embedding vector $k_{t}$가 된다. 이 $k_{t}$가 key 행렬 $M^k$의 각 열벡터들과 내적을 통해 N개의 개념들과의 유사도를 계산하고 softmax를 통해 정규화된다.
• 즉 문항 $q_{t}$에서 각 개념 $c_{i}$가 차지하는 비중 $w_{t}(i)$을 구하는 것이다.
• 이는 attention 방법과 같다. embedding $k_{t}$가 query, key 행렬 $M^k$가 key에 해당한다.

• 아래 그림의 파란 부분에 해당한다.

• $w_{t} = Softmax(k^T_{t}M^k)$

Read Process

• 앞에서 구한 correlation weight $w_{t}$과 value 행렬 $M^v_{t}$의 각 열벡터들의 weighted sum으로 학생들의 현 문항에 대한 이해도인 $r_{t}$를 구할 수 있다.
  • $r_{t} = \sum_{i=1}^N w_{t}(i)M^v_{t}(i)$
• 그리고 각 문항이 가진 난이도를 주기 위해 $r_{t}$와 앞서 구한 embedding vector $k_{t}$를 concat하고 fully conneted 레이어를 통과한다.
  • $f_{t} = \tanh (W^T_{1}[r_{t},k_{t}] + b_{1})$
• 한번 더 fully conneted 레이어를 통과해 최종적으로 predict $p_{t}$를 구한다.
  • $p_{t} = softmax (W^T_{2}f_{t} + b_{2})$
• 아래 그림의 회색과 보라색에 해당한다.

Write Process

• 문항 $q_{t}$에 대한 학생의 응답 후, 모델은 학생의 응답의 정오에 따라 value 행렬을 업데이트 한다.
• ($q_{t}, r_{t}$)를 정오에 따른 경우을 표현하기 위해 2Q(문항 수 Q)로 embedding하여 $v_{t}$를 구한다.
• 다음은 LSTM의 input&forget 게이트처럼 기존 상태 $M^v_{t}$를 어떻게 지울지에 대한 earas파트와 어떻게 갱신할지에 대한 add 파트가 존재하는데, 먼저 $v_{t}$로 $e_{t}$, $a_{t}$를 구한다.
  • $e_{t} = \sigma(E^Tv_{t} + b_{e})$
  • $a_{t} = Tanh(D^Tv_{t} + b_{a})$
• 아래 식을 통해 correlation weight $w_{t}$를 통해 기존 개념별 이해도를 지우고 더하면서 새로운 $M^v_{t+1}$를 만드는 것이다.
  • $\hat M_{t+1}^v(i) = M_{t}^v(i)[1 - w_{t}(i)e_{t}]$
  • $M_{t+1}^v(i) = \hat M_{t}^v(i) + w_{t}(i)a_{t}$
• 이 새로운 $M^v_{t+1}$는 다음 문항 $q_{t+1}$를 예측하는데 사용한다.
• 아래 그림의 초록 부분에 해당한다.

training

• $q_{t}$에 대한 predict 값 $p_{t}$와 실제 레이블 $r_{t}$사이의 Binary Cross Entropy Loss를 최소화하는 방식으로 학습을 진행한다.
  • $L = -\sum_t (r_{t}logp_{t} + (1 - r_{t})log(1 - p_{t}))$
• DKVMN 모델은 전부 미분이 가능하기 때문에 stochastic gradient descent(SGD)로 충분히 학습이 가능하다. 모든 데이터셋의 30%는 test set으로 설정. train set의 20%는 validation set으로 설정. learning rate는 100 epoch이 될 때까지 20epoch마다 r/1.5씩 강화. 모멘텀은 0.9. norm clipping threshold는 50. 모든 dataset은 길이를 200단위로 자르고, 200보다 짧은 데이터는 null값으로 패딩.

3. Performance

• DKT와 비교해 모든 데이터셋에서 더욱 적은 parameter 수만으로도 향상된 AUC를 보인다.

4. Concept Discovery

• 위 모델은 전문가가 태깅하는 것처럼 correlation weight를 이용해 문항에 내재된 개념을 찾아내는 힘이 있다. 문항과 개념 간의 correlation weight는 그들의 내적 관계의 정도를 나타낸다.

Knowledge State Depiction

• 위 모델은 학생의 knowledge state를 확인할 수 있다. 학생의 i번째 개념에 대한 이해도를 확인하고 싶다면 correlation weight의 i번째 값만 1로 설정한다. 그 다음 read process를 통해 $r_{t}$를 구하고 마지막 $f_{t}$를 구할 때 문제에 대한 정보 $k_{t}$를 0으로 하고 진행한다. 이렇게 구해진 scalr p가 예측된 개념 이해도이다.

내 생각

• 개념간의 관계를 생각한 점이 인상 깊다.
• attention 기법이 적용될 수 있단 것과 앞으로 나올 kt모델에 attention 기법이 자주 사용된다는 것으로 볼 때 의미가 있는 시초다.
• Deep learning을 최초로 이용한 DKT에서 학생 개념 이해도를 더 세밀하게 분석하려 하여 성능을 발전시킨 점이 고무적이다.