Towards an Appropriate Query, Key, and Value Computation for Knowledge Tracing

논문 링크 ; arxiv.org/pdf/2002.07033.pdf

 

지금 참여 중인 Kaggle Competition이다.

Riiid! Answer Correctness Prediction

SANTA 앱에서 축적된 유저의 학습 데이터를 가지고, Knowledge Tracing을 하는 대회이고,

유저의 응답 history가 주어졌을 때 다음으로 주어지는 문제를 맞출 확률이 얼마나 되는지 계산해야 한다.

 

관련 논문을 훑다가,

riiid에서 구현한 모델이 있어서 보니 트랜스포머를 사용하고 있었는데,

주어진 데이터를 트랜스포머에 어떻게 입력을 한 것인지 궁금해서 보게 되었다.

Knowledge Tracing?

시간에 따라 달라지는 학생의 지식의 상태(or State of a student's understanding)을

learning activities를 이용하여 모델링하는 것.

 

본 논문에선, Transformer를 이용해서 이 문제를 해결하는 것을 다룬다.

 

transformer의 self-attention을 활용하기 위해 Query, Key, Value를 어떻게 구성하는가?

에 집중해서 보면 좋을 듯하다.

 

이전 모델 및 제안 모델 비교

Knowledge Tracing에 어텐션을 적용했던 이전 모델들을 보면,

깊이가 깊지 못해서 exercises, responses 간의 복잡한 관계를 capture하기 힘들며,

적절한 Query, Key, Value 배치에 대한 고민이 적었다고 한다.

 

본 논문에선 SAINT(Seperated Self-AttentIve Neural Knowledge Tracing) 모델을 제안해서

EdNet 데이터 셋에 대해 가장 좋은 성능을 끌어내었다.

 

Figure 2. 에서

- 주어진 Exercises의 임베딩을 인코더의 Q, K, V로 입력

- 디코더에는 Responses의 임베딩을 Q, K, V로 입력

- 인코더-디코더 사이의 어텐션에서 인코더의 아웃풋을 K, V로 디코더의 어텐션 아웃풋을 Q로 입력

하는 부분을 확인할 수 있다.

 

Exercises와 Responses를 인코더, 디코더 각각에 입력함으로써 얻어낸 distinctive features가

Exercises와 Responses간의 복잡한 관계를 캡쳐하는데 도움을 주고있다고 주장하고 있다.

 

관련 연구

- BKT(Bayesian Knowledge Tracing) ; 고전적인 방법으로 학생의 Knowledge State를 binary values의 튜플로 나타낸다.

각 값은 학생이 각 컨셉을 이해하고 있는지 여부를 나타내며,

값들은 hidden Markov model을 학생들의 응답 데이터에 적용하여 업데이트한다.

- CF(Collaborative Filtering) 

- DL(Deep Learning)

  - EKT(Exercise-aware Knowledge Tracing), NPA(Neural Pedagogical Agent)는 Bi-LSTM 모델과 모델의 최상단 레이어에 어텐션 메커니즘을 적용하였다.

  - SAKT(Self-Attentive Knowledge Tracing)는 Transformer 모델을 사용하였으며,

exercise를 Q로, 과거 interaction(exercise-response 쌍)을 K, V로 활용하였다. 

 

SAINT

주어진 히스토리 데이터는 set of exercises에 대해서 학생이 어떻게 응답했는지,

그 인터랙션이 기록되어있다.

 

어떤 학생의 인터랙션 히스토리가 주어졌을 때,

모델은 새로운 exercise를 학생이 맞출지 여부를 예측해야한다.

 

I = (E, R)

E ; exercise info

R ; response info (0 or 1 ; correct or not)

 

SAINT가 예측하는 확률 모델

입력 표현(Representation)

가장 궁금했던 부분인데,

앞서 살펴본 대로, 인코더에는 Exercises의 임베딩이 들어가고

디코더에는 Responses의 임베딩이 들어가는데

그 임베딩을 어떻게 만든 것일까?

 

위와 같은 메타데이터가 주어질 때,

 

Exercise Embedding은

순서 정보를 반영한 Position Embedding과

나머지 ID, Category에 대해선 임베딩 레이어를 거쳐 Embedding Vector를 뽑는다.

그 이후에 3 개를 합산하여 Exercise 임베딩을 만든다.

 

Response Embedding도 마찬가지로 만들어진다. (Position, Response)

 

Exercise와 Response를 연결해주는 Interaction Embedding이 별도로 없어도

SAINT는 잘 동작하는데, 뒤에 비교 실험이 포함 되어 있음.

 

Deep Self-Attentive Encoder Decoder

트랜스포머 아키텍쳐가 거의 그대로 적용되었다.

차이점은 Encoder에도 masking 메커니즘을 적용하는 것과

Encoder-Decoder 어텐션을 구할 때 Q, K, V의 조합이 다르다는 것 정도.

 

인코더는 k개의 exercise 임베딩을 입력 받고

출력으로는 k개의 임베딩을 뽑아준다.

디코더는 1 개의 Start 토큰 임베딩과 k-1 개의 response embedding을 입력 받고,

k개의 predicted response 임베딩을 출력한다.

정리하면 다음과 같다.

a. Multi-head Attention Networks

Original Transformer와 동일하게 h 개의 projection Q, K, V를 생성한다.

그 이후, Q*K를 통해 어텐션 스코어를 구하고

어텐션 스코어를 V에 곱해서 어텐션이 반영된 벡터를 얻기 전에 Masking을 적용해서

현재 지점을 예측함에 있어 앞의 시퀀스에만 의존하도록 제한해준다.

* mask ; Q*K 결과의 upper triangular part -> 음의 무한대 값으로 세팅 -> softmax를 거친 후 0으로 바뀜

Masked Attention Score가 곱해진 Vi

h 개의 multi head는 concat이 되어서 W0과 곱해진 뒤 입력과 인코더 입력 임베딩과 동일한 크기로 맞춰준다.

 

b. Position-wise Feed-forward Network

Original Transformer와 동일하게 Multi-head attention의 출력은 FFN을 거친다. 

Encoder & Decoder 구현

인코더

Excercises의 관계가 반영된 Vectors가 생성된다.

* 첫 레이어의 Q, K, V는 exercise embedding

 

디코더

인코더의 결과 벡터를 K, V를 삼고, 디코더의 입력 벡터에 대해 어텐션을 적용한 결과를 Q삼아,

Exercise와 Response의 관계가 반영된 Vectors를 만들어 준다. 

* 첫 레이어의 Q, K, V는 디코더의 입력인 Response Embeddings이고, 그 이후 레이어는 이전 레이어의 아웃풋

* O는 인코더의 아웃풋

 

최종 Prediction Layer에서는 linear transform을 적용하고 sigmoid를 통과시켜 확률 값을 반환시켜주면 끝!