qDKT: Question-centric Deep Knowledge Tracing

이번 포스트에서는 qDKT: Question-centric Deep Knowledge Tracing에 대해서 알아보도록 하겠습니다. 

 

DKT, DKVMN등을 비롯한 대부분의 Knowledge Tracing 모델들은 학생의 knowledge를 skill-level로써 모델링합니다. 즉, 학생의 과거의 interaction = (skill_id, correctness)를 바탕으로 다음 문제의 skill에 해당하는 정오답을 예측합니다. 하지만, 같은 skill을 가지는 문제일지라도 문제 자체는 다르기 같은 skill의 서로 다른 문제들을 하나로 엮는 것은 정보를 잃는다고 생각할 수 있습니다. 또한, 문제의 skill이라는 것이 모든 데이터셋에 대해서 항상 존재한다고 볼 수도 없습니다. (일반적으로 skill은 수작업 labeling이 필요한 경우가 많고, 그렇기 때문에 skill에 대한 정보가 꼭 있다고 볼 수는 없죠.) 

 

그렇다면, 기존 모델들에서 skill이 아니라 question id를 가지고 예측하면 되는 일 아닐까요? 다시 말해서, 각 interaction을 (skill_id, correctness)가 아닌 (question_id, correctness)로 치환해서 생각하자는 것 입니다. 유감스럽게도, 잘 알려진 benchmark ASSISTments2009와 ASSISTments2017에 대해서 실험하게 되면 그렇지 않다는 것을 알게됩니다.

Performance (AUC) of DKT on ASSISTments2009 and ASSISTments2017 benchmarks, Sonkar et. al. 2020

위의 표에서 볼 수 있듯이 ASSISTments2017에 대해서는 question-level KT가 skill-level KT보다 AUC가 높게 나왔지만, ASSISTments2009에 대해서는 반대로 나온 것을 볼 수 있습니다. 이는 ASSISTments2009 dataset이 sparse하기 때문인데요, 전체 문제 수에 비해서 데이터 숫자가 적어서 각 문제가 풀린 횟수가 적기 때문입니다. 이렇게 되면 training set에서 아얘 등장하지 않은 문제가 test set에 등장하는 경우도 있을 수 있고, 그 반대 역시 가능합니다. (일종의 overfitting으로 볼 수 있습니다.) 그렇기 때문에, 단순히 question_id만 사용하는 것은 오히려 성능에 독이 될 수 있습니다.

 

이를 해결하기 위해서 저자들은 Question-centric Deep Knowledge Tracing, 즉 qDKT를 제안합니다. 아이디어는 매우 간단한데, interaction에서 skill_id를 사용하지 않고 question_id만 사용하는 대신에 다음과 같은 Regularlizer를 도입하는 것 입니다. DKT의 output y (각 question 별 predicted correctness probability)에 대해

로 정의합니다. 여기서 1(i, j)는 indicator function으로 question i, j가 같은 skill에 속하면 1, 아니면 0인 함수를 나타냅니다. 이는 같은 skill에 속하는 문제라면 맞출 확률 역시 비슷해야 한다는 직관으로 부터 나왔습니다. 이를 전체 loss에 (scaling factor를 곱해서) 추가해주기만 하면 끝납니다. 본문에서는 이 regularizer를 Laplacian regularizer라고 부르는데, node가 question이고 같은 skill의 question 사이에는 edge가 존재하는 그래프를 생각하게 되면 위의 regularizer는 이 그래프의 Laplacian matrix L = D - A (D는 degree matrix, A는 adjacency matrix)에 대응되는 quadratic form이 되기 때문입니다.

 

더 나아가서, fastText에서 영감을 얻어 question embedding의 '좋은' initialization을 제안합니다. fastText란 Facebook에서 2017년에 발표한 word embedding 방법론으로 기존의 Word2Vec embedding이 언어의 morphological한 특성을 잘 반영하지 못한다는 점과 새로운 단어(OOV, Out-Of-Vocabulary)가 등장하면 처음부터 다시 훈련시켜야 하는 점을 해결하기 위해서 만들어졌습니다. fastText에서는 단어 하나하나를 bag-of-characters로 생각해서 character들의 n-gram의 embedding을 먼저 찾고, 최종적인 word embedding은 n-gram embedding의 합으로 나타내게 됩니다. 이름에서 알 수 있듯이 Word2Vec embedding에 비해서 더 빠르고 더 좋은 embedding을 얻었다고 합니다. 마찬가지로, qDKT에서는 각 question을 하나의 character에 대응시킨 뒤, (question_id, correctness) interaction들을 'q1' 혹은 'q0'의 character 2개짜리 단어들로 보고 (여기서 q는 주어진 question_id에 대응되는 character이고, 1, 0은 각각 맞거나 틀린 응답에 대응됩니다) 2-gram들의 embedding, 즉 'q', 'q1', '1'의 embedding들을 학습한 뒤, 이들의 합으로써 (q, 1)의 embedding을 정의하고 이를 initialization으로써 사용합니다. 이는 학생의 interaction embedding이 맞은것과 틀린것끼리 cluster를 이룬다는 점에서 착안하였다고 합니다. 

 

실험은 ASSISTments2009, ASSISTments2017, STATICS, 그리고 Tutor dataset에 대해서 진행하였고, 결과는 다음과 같습니다. 표에서 알 수 있듯이, Regularizer를 쓰는것과 fastText initialization을 쓰는 것 둘 다 성능 향상에 도움이 되었고, 둘을 같이 사용하는 것이 (ASSISTments2017을 제외하고) 가장 성능이 좋았습니다.

AUC results, Sonkar et. al. 2020

또한, fastText로 얻은 embedding(왼쪽)과 randomized initialization(오른쪽)을 비교했을 때, fastText로 얻은 interaction embedding은 response가 맞았는지(파란색) 틀렸는지(빨간색)에 따라서 cluster를 형성하는 것을 확인할 수 있습니다.