[Knowledge Tracing] SAKT (A Self-Attentive model for Knowledge Tracing)

논문 링크: https://arxiv.org/abs/1907.06837

SAKT는 학생의 과거 문제풀이 이력으로부터 서로 관련 있는 KC를 규명하고 KC에 대한 학생의 과거 performance를 바탕으로 학생의 performance를 예측한다.

 

Notation

i: i번째 학생
et: t번째 문항
rt: et에 대한 정오답 여부 (0/1)
xt: (et, rt) 쌍
E: 전체 문항 수
n: 모델에서 다루는 최대 시퀀스 길이
M: interaction embedding matrix
P: Positional embedding matrix
E: Exercise embedding matrix
d: latent dimension

 

Input

1~(t-1)번째 이력 x1, x2, …, x(t-1)을 바탕으로, e2, e3, ..., et 문항에 대한 정오답 여부 r2, r3, ..., rt를 예측한다.
이 때, xt = (et, rt)는 yt = et + rt x E 라는 숫자로 표현된다. et가 가질 수 있는 값의 개수는 E이고, rt가 가질 수 있는 값은 정답 혹은 오답 둘 중에 하나이므로, xt가 가질 수 있는 값의 개수는 2E개이다.

 

Embedding layer

input sequence y = (y1, ..., yt)를 같은 길이로 맞춰주기 위해 s = (s1, ..., sn)으로 변환한다. 이 떄 t < n인 경우 t+1 ~ n까지의 값은 padding을 하고, t > n인 경우 시퀀스 길이를 n으로 자른다.
크기가 2E x d인 interaction embedding matrix M, 크기가 n x d인 positional embedding matrix P를 활용하여 interaction을 임베딩하고, 크기가 E x d인 exercise embedding matrix E을 활용하여 문항을 임베딩한다.

 

Self-attention layer

본 논문에서는 scaled dot-product attention mechanism을 사용하여 학생이 과거에 풀었던 문항 간 관련성에 기반한 가중치를 구한다.
먼저, Query, Key, Value는 아래와 같고, WQ, WK, WV는 각각 d x d 크기의 projection matrix이다.

다음으로 attention 가중치를 구하기 위해 scaled dot-product를 실행한다.

서로 다른 시퀀스 공간의 정보에 jointly attend하기 위해서 서로 다른 projection matrix들을 사용하여 Qeury, Key, Value를 h번 반복하여 linear projection한다. (Multiple heads)

본 모델에서 t+1번째 문항의 정답확률을 예측할 때에는 1~t시점까지의 interaction만 활용해야 한다. 즉, Query Qi와 Key Kj가 있을 때 j > i라면 해당 Key는 모델에 활용되면 안된다. 따라서 j > i인 Kj를 masking하는 causality layer를 사용한다. (causality)

 

Feed Forward layer

앞에서 multihead layer로부터 구한 행렬(S)은 여전히 Value Vi의 linear combination이다. 모델에 non-linearity를 더하고 서로 다른 latent dimension간 상호작용을 고려하기 위해 feed forward network를 사용한다.

 

Residual Connections

lower layer feature를 higher layer로 전파하기 위한 것이다. 만약 low layer feature가 예측에 있어서 중요한 역할을 한다면, residual connection을 통해 low layer feature를 예측이 이루어지는 final layer로 전파할 수 있다.
KT의 맥락에서 보자면, 학생들은 특정 KC에 속한 문항을 계속해서 풀면서 그 KC에 대한 능력을 키운다. 따라서 residual connection을 하면 최근에 푼 문항의 임베딩을 final layer로 전파하여 모델로 하여금 low layer information을 더 잘 반영할 수 있도록 한다.
residual connectio은 self-attention과 feed forward layer 이후에 적용된다.

 

Layer normalization

self-attention, feed forward layer 둘다에 반영한다.

 

Prediction layer

원래 트랜스포머와 다르게 softmax 대신 sigmoid를 적용하여 학생의 정답확률을 예측한다.

 

Training

예측된 정답확률 pi와 실제 응답 ri 사이의 cross entropy loss를 최소화 하는 방식으로 파라미터를 학습시킨다.

 

Relevance graph

SAKT의 Attention Layer에서 query에 해당하는 문항과 key에 해당하는 문항간의 attention weight 값이 크면 같은 cluster에 속하도록 하는 방법을 통해 문항들을 clustering하여 graph로 나타낸 것이다. 각 문항을 풀기 위해 요구되는 KC 정보에 따라 문항들이 clustering되는 것을 볼 수 있다. 이로부터 SAKT는 KC에 대한 정보를 입력받지 않아도 KC에 기반한 문제간의 유사도를 모델링할 수 있음을 알 수 있다.

attention weight를 나타낸 히트맵