Knowledge Tracing Paper Review
저번에 리뷰했던 Deep Knowledge Tracing에 이은 논문 리뷰다.
Knowledge Tracing
- BKT : Bayesian Knowledge Tracing) (1995)
- DKT : Deep Knowledge Tracing (15.06)
- DKVMN : Dynamic Key-Value Memory Networks for Knowledge Tracing (16.11)
- SAKT : A Self-Attentive model for Knowledge Tracinig (19.07)
Knowledge Tracing이라는 도메인에서 중요했던 논문들을 간단하게 아이디어들만 짚어보자.
Knowledge Tracing은 학생의 문제 풀이 데이터를 통해 현재 지식 상태를 예측하는 태스크이다. 온라인 교육 사이트가 많아지면서 이 태스크의 필요성이 점점 커지고 있다.
BKT
이 모델은 1995년 맨 처음 탄생하였다. Bayesian Knowledge Tracing 이름에서 알 수 있듯이 Bayesian 정리를 적극 활용한 모델이다. 학습과정에서 학생의 지식 수준을 확률적으로 모델링하여 특정 시점에 학생의 지식 수준을 예측한다. BKT에서는 한 학생이 한 가지 스킬에 대한 지식 수준만을 예측할 수 있다.
model
먼저 총 6가지 확률을 정의한다. 위 4가지 확률은 skill에 대한 정보이며 아래 2가지 확률은 한 학생의 한 skill에 대한 정보이다.
- $P(L_0)$ : 학생이 미리 skill을 알고 있을 확률
- $P(T)$ : skill을 한 번 학습한 후 완전히 이해할 확률
- $P(G)$ : 모르지만 우연히 맞출 확률
- $P(S)$ : skill은 배웠으나 실수할 확률
- $P(L_t)$ : 학생이 t시점에 skill을 알고 있을 확률
- $P(C)$ : 학생이 문제를 맞출 확률
skill k에 대해서 student u가 t=1일 때 미리 skill을 알고 있을 확률에 대한 식이다. 이 땐 skill k의 $p(L_0)$ 값과 같게 된다.
$$ p (L_ {1}) _ {u} ^ {k} = p (L_ {0}) ^ {k} $$
student u가 t 시점에서 문제를 푸는데 필요한 skill이 u인 문제를 맞췄을 때 이 skill u를 알고 있을 확률이다. 조건부 확률에서 $P(A|B) = P(A,B)/P(B)$ 식을 사용한다. 알고있을 때 실수하지 않을 확률 / (알고있을 때 실수하지 않을 확률 + 모를 때 운으로 맞출 확률) 이 된다.
$$ p(L_{t}|obs=correct)_{u}^{k}={\frac {p(L_{t})_{u}^{k}\cdot (1-p(S)^{k})}{p(L_{t})_{u}^{k}\cdot (1-p(S)^{k})+(1-p(L_{t})_{u}^{k})\cdot p(G)^{k}}} $$
student u가 t 시점에서 문제를 푸는데 필요한 skill이 u인 문제를 틀렸을 때 이 skill u를 알고 있을 확률이다.
$$ p(L_{t}|obs=wrong)_{u}^{k}={\frac {p(L_{t})_{u}^{k}\cdot p(S)^{k}}{p(L_{t})_{u}^{k}\cdot p(S)^{k}+(1-p(L_{t})_{u}^{k})\cdot (1-p(G)^{k})}} $$
student u가 t시점에서 문제를 푸는데 필요한 skill이 u인 문제를 풀었을 때 t+1시점에서 u를 알고 있을 확률이다. $P(L_t|obs)=p(L_{t}|obs=wrong) + p(L_{t}|obs=correct)$이다.
$$ p (L_ {t + 1}) _ {u} ^ {k} = p (L_ {t} | obs) _ {u} ^ {k} + (1-p (L_ {t} | obs ) _ {u} ^ {k}) \cdot p (T) ^ {k} $$
t+1시점에서 문제를 푸는데 필요한 skill이 u인 문제를 맞출 확률은 다음과 같이 된다.
$$ p (C_ {t + 1}) _ {u} ^ {k} = p (L_ {t + 1}) _ {u} ^ {k} \cdot (1-p (S) ^ {k }) + (1-p (L_ {t + 1}) _ {u} ^ {k}) \cdot p (G) ^ {k} $$
위 식들로 우리는 점화적으로 $P(L_t)$를 알 수 있게 되고 student의 문제 풀이 기록을 볼 때 특정 시점에서 이 문제를 푸는데 필요한 skill u에 대한 지식 수준을 예측할 수 있게 된다.
result
장점
- 학생이 어떤 skill에 대해 이해했을 확률을 explainable하게 설명가능
단점
- 한 번에 한 가지 skill만 예측 가능
- 초기 4개 확률을 정하기 쉽지 않음
- 모든 문제에 대해 어떤 skill이 사용되는지 라벨링해야함
- 어떤 skill에 대해 알면 관련 문제를 전부 풀 수 있고 아니면 전부 풀 수 없다는 가정이 옳지 않음
DKT
BKT의 단점들을 해결하고자 딥러닝을 이 태스크에 처음 도입한 모델이다.
model
시간에 따른 지식 수준을 RNN을 통해 예측한다. 인풋 데이터로 t번째 시점에 나온 문제와 정답 여부가 들어가며 아웃풋으로 모든 문제에 대한 정답 확률이 나온다. t+1번째 시점에 나온 문제의 정답 확률과 실제 정답 여부 차이를 loss로 하여 training시킨다.
이렇게 training하면 지금까지의 문제 풀이 기록을 통해 다음 나올 문제들에 대한 정답 확률을 예측할 수 있게 된다. 이 정답확률의 평균을 평균 지식 수준이라고 한다면 더 나아가 다음 문제로 어떤 문제가 나올 때 지식 수준이 제일 많이 향상될 것인지도 예측할 수 있다.
result
장점
- hidden vector를 통해 모든 skill을 한번에 다룰 수 있음
- 더 고차원으로 표현하기 때문에 더 많은 정보 수용 가능
- 사람의 라벨링이 필요하지 않음
- skill간의 relationship 계산가능
단점
- 모든 skill을 하나의 vector로 다루다 보니 한 skill에 대해 얼마나 마스터했는지 정확한 판단 어려움
- 모든 문제에 대해 어떤 skill이 사용되는지 라벨링해야함
DKVMN
DKT, BKT의 단점들을 해결하기 위해 탄생한 모델이다. 각 스킬별 마스터 정도를 예측할 수 있고 스킬 간의 relationship 또한 계산할 수 있도록 하였다.
위 사진이 BKT, DKT, DKVMN에 대해 차별점을 보여주는 그림이다. BKT는 컨셉(=스킬)c에 대한 지식 수준만 예측가능하며 c관련 문제를 풀 때는 c에 대한 지식 수준만이 업데이트된다. DKT는 현재 학생의 전체적인 지식 수준을 예측가능하다. DKVMN은 이것을장점만 합쳐 어떤 문제를 풀든 모든 컨셉에 대해 각각의 지식 수준을 업데이트한다.
model
먼저 $M^k$를 보자. 이 matrix는 컨셉 N개에 대한 사람의 지식 수준 정보이다. $M_{t}^{v}$는 컨셉 N개에 대한 각각의 정보이다.
기본적인 구조는 LSTM으로 생각하면 이해하기 쉽다. 먼저 문제 $q_t$가 인풋으로 들어가고 embedding net을 통해 $k_t$로 forward된다. 이 때 $k_t$는 $d_k$차원이다. 이 값과 컨셉 N개에 대한 사람의 지식 수준 정보인 $M^k$를 곱해 N차원짜리 벡터 $w_t$를 구한다. 이 벡터는 각 컨셉별 정답확률이라고 이해하면 된다.
그 후 이 벡터 $w_t$와 $M_{t}^{v}$를 곱해 이 학생의 전체 지식 수준인 N차원짜리 벡터 $r_t$를 구한다. 이 전체 지식 수준에서 linear + tanh + sigmoid를 통해 최종 값을 0에서 1사이 값 scalar로 예측한다. 이 값이 문제 $q_t$를 맞출 확률이다. 이제 이 값과 실제 라벨 값 사이의 cross-entropy 값으로 backward한다.
지금까지는 어떤 문제에 대해 이 문제를 맞출 확률을 예측하여 training하였다면 이제 기존의 문제 풀이 이력을 반영하게 할 차례이다. 기존의 문제 풀이 이력이 매우 길 경우 RNN을 사용하면 무시되기 쉽기 때문에 LSTM의 아이디어를 갖고 와 erase vector와 add vector를 사용한다. $q_t$,$r_t$를 concat한 후 embedding network를 통해 $d_v$차원짜리 벡터로 만든다. 그 후 한쪽으로는 Linear + sigmoid를 통해 $d_v$차원의 erase vector $e_t$를 만들고 한쪽으로는 Linear + Tanh를 통해 $d_v$차원의 add vector $a_t$를 만든다.
아까 사용한 $M_{t}^{v}$ 벡터를 이제 다음과 같은 식으로 업데이트한다.
$$M_t^v(i) = M_{t-1}^v(i) + w_t(i)(a_t - e_t)$$
$w_t$는 $M_k$와 연결되어 있으므로 컨셉 N개의 정보와 컨셉 N개에 대한 사람의 지식 수준 정보까지 모두 업데이트가 되면서 최적화가 된다.
result
장점
- DKT보다 적은 파라미터개수로 더 나은 결과를 보인다.
- 오버피팅을 걱정하지 않아도 된다.
- 컨셉당 지식 수준을 알 수 있다.
단점
- sparse data에 대해 training이 어렵다.
- 모든 문제에 대해 어떤 skill이 사용되는지 라벨링해야함
SAKT
DKVMN은 분명 좋은 모델이지만 실제 세상에서는 한 사람이 모든 knowledge concept에 대해 다루기가 쉽지 않다. 또한 여전히 모든 문제에 대해 어떤 skill이 사용되는지 라벨링이 되어야 한다는 불편함이 존재한다. 이런 sparse한 데이터에서 그리고 라벨링없이 Knowledge Tracing을 하기 위한 모델로 SAKT가 등장하였다.
model
기본적인 아이디어는 트랜스포머에서 시작한다. 이 문제풀이내역이 sequence data이므로 RNN에 적용할 수 있었고 마찬가지로 transformer에도 적용이 가능하다는 것이 이 모델의 메인 아이디어이다. NLP의 발전이 KT의 발전에 큰 영향을 미치는 모습을 볼 수 있다.
여기서 우리는 Decoder만 사용하며 중간에 있는 encoder-decoder attention은 제외한다. 또한 decoder 모듈을 6번 쓰지 않고 한번만 사용한다. 디코더만 사용하는 것이 GPT와 비슷하다고 생각하면 된다. 모델의 디테일은 transformer와 비슷하므로 생략하고 training방법과 인풋아웃풋만 설명하겠다.
전체 문제 개수를 E개라고 하자. 인풋 데이터로는 문제 T개, 정답 여부 T개 총 2T개의 값을 $y_t = e_t + r_t* E$로 T개의 값으로 변경시킨다.
최종적으로는 전체 문제 개수인 E개만큼 나오며 각각 i번째 문제를 맞출 확률을 의미한다. 실제로 우리가 T개의 문제 풀이 내역을 데이터로 쓴다면 t=1일 때 t=2일 때 나올 문제를 예측하고 실제 정답 여부와의 비교를 통해 backward를 할 수 있다. 이렇게 t=1일 때부터 t=T-1일 때까지 전부 training할 수 있다. 그러면 현재 문제 풀이 내역에 대해 다음 나올 문제를 맞출 확률을 예측할 수 있게 된다.
result
장점
- 성능개선
- sparse data 가능
- 라벨링 필요없음
Final
지금까지 KT 태스크에서 유명한 모델들인 BKT, DKT, DKVMN, SAKT에 대해서 알아봤다. 1994년부터 2019년까지의 KT의 역사였는데 2020년의 논문들이 궁금하다면 아래에서 읽어보길 바란다.
Context-Aware Attentive Knowledge Tracing : https://arxiv.org/pdf/2007.12324.pdf
Deep Knwoledge Tracing with Convolutions : https://arxiv.org/pdf/2008.01169.pdf
RKT : Relation-Aware Self-Attention for Knowledge Tracing : https://arxiv.org/pdf/2008.12736.pdf
GIKT: A Graph-based Interaction Model for Knowledge Tracing : https://arxiv.org/pdf/2009.05991.pdf
