[Paper Review] Dynamic Key-Value Memory Networks for Knowledge Tracing (DKVMN, 2015)

📝 Dynamic Key-Value Memory Networks for Knowledge Tracing

위 논문 리뷰입니다. 내용을 유지하되, 추가적으로 필요한 내용은 추가하고 순서를 재구성하여 정리하였습니다. 핵심은 하이라이트 표시하였습니다. 논의 및 피드백은 언제나 환영입니다😊

---

2 Related Works

✅ 지식 추적 (Knowledge Tracing, KT)

지식 추적(KT)은 문제 풀이 이력을 기반으로 학생의 지식 상태를 추적하는 작업입니다. KT의 중요한 목적 중 하나는 학습 순서를 개인화하여 학생들이 지식 개념을 효율적으로 학습할 수 있도록 돕는 것입니다. 그러나 베이지안 지식 추적 및 심층 지식 추적과 같은 기존 방법은 미리 정의된 각 개념에 대한 지식 상태를 개별적으로 모델링하거나 학생이 어떤 개념을 잘하거나 익숙하지 않은지 정확히 파악하지 못합니다. 이러한 문제를 해결하기 위해 이 연구에서는 기본 개념 간의 관계를 활용하고 각 개념에 대한 학생의 숙달 수준을 직접 출력할 수 있는 동적 키-값 메모리 네트워크(DKVMN)라는 새로운 모델을 소개합니다.

✅ BKT

BKT는 학생의 지식 상태를 개념별로 분석하며, 각 개념 상태를 독립적으로 모델링합니다. BKT는 이진 잠재 변수를 사용해 개념 상태를 '알고 있음'과 '모르고 있음'으로 나누고, 각 개념 상태의 사후 확률을 갱신하기 위해 히든 마르코프 모델(HMM)을 사용합니다. 하지만 BKT는 개념 간의 관계를 모델링하지 못하며, 개념 상태 전환을 단순한 이진 변수와 전이 모델로 설명하기 때문에 복잡한 개념 상태 전환을 잘 표현하지 못합니다.

✅ DKT

DKT는 장단기 메모리(LSTM)를 사용하여 학생의 지식 상태를 연속적이고 고차원적인 표현으로 가정합니다. DKT는 비선형적인 입력-상태 및 상태 간 전이 모델을 사용하여 BKT보다 더 강력한 표현력을 가지고 있지만, 모든 개념을 하나의 숨겨진 상태에 요약해 학생이 특정 개념을 얼마나 이해하고 있는지 구체적으로 추적하기 어렵습니다.

아래 그림은 BKT, DKT, DKVMN의 모델 차이를 보여줍니다.

BKT (Bayesian Knowledge Tracing)
BKT는 개념 특정적(concept specific)으로 작동합니다. 즉, 각 개념 𝑐𝑖에 대해 별도의 상태 $s^{i}_{t-1}$를 유지합니다. 문제 $q^{i}_{t}$와 그에 대한 응답 $r^{i}_{t-1}$을 바탕으로 학생이 특정 개념에 대한 지식 상태를 갱신합니다. 다음 문제 $q^{i}_{t}$에 대한 응답을 예측하기 위해 이전 상태를 기반으로 판단합니다.

DKT (Deep Knowledge Tracing)
DKT는 종합된(hidden) 상태 벡터 $s_{t-1}$를 사용해 전체적인 지식 상태를 표현합니다. 모든 개념을 하나의 벡터로 통합하여 추적하는 방식입니다. 이전 문제 $q_{t-1}$과 그에 대한 응답 $r_{t-1}$을 사용해 상태 $s_{t-1}$를 갱신하고, 이를 바탕으로 다음 문제 𝑞𝑡에 대한 응답을 예측합니다. 개념별 상태를 구체적으로 다루지는 않지만, 종합적인 지식 상태로 모델링합니다.

DKVMN
이 모델은 각 개념 𝑐𝑖,𝑐𝑗,𝑐𝑘에 대해 각각의 모든 개념별 상태를 동시에 유지합니다. 각 개념 𝑐𝑖,𝑐𝑗,𝑐𝑘에 대해 각각의 상태 $s^{i}_{t-1}$, $s^{j}_{t-1}$, $s^{k}_{t-1}$을 개별적으로 관리합니다. 따라서 학생의 전체 지식 상태는 모든 개념의 상태들의 집합으로 구성됩니다. 이전 문제 $q_{t-1}$과 응답 $r_{t-1}$을 통해 각각의 개념 상태를 갱신하고, 다음 문제 𝑞𝑡에 대한 응답을 예측합니다. 각 개념에 대한 개별적인 지식 상태를 추적할 수 있기 때문에, 학생의 개념별 학습 진행 상황을 더 세밀하게 모니터링할 수 있습니다.

요약하자면, BKT는 개념별로 지식 상태를 추적하고, DKT는 종합된 지식 상태를 벡터로 표현하며, DKVMN은 개념별 상태를 동시에 관리하여 더 세밀한 지식 상태 추적을 가능하게 한다고 설명합니다.

✅ Neural Turing Machines (NTM)

문헌 (1) 내용을 참고하여 다시 정리하였습니다. DKVMN에서 활용한 MANN은 NTM 모델을 일부 변형하여 만들어졌습니다.

Alex Graves 외(2014)가 제안한 NTM(Neural Turing Machines)은 크게 신경망으로 이루어진 컨트롤러(controller)와 가중치 벡터(weight vector)를 저장하는 메모리로 구성되어 있습니다. NTM의 전체 아키텍처는 Fig. 1.과 같으며, 메모리와 컨트롤러 사이에는 읽기 헤드(read heads)와 쓰기 헤드(write heads)로 구성되어 있습니다.

컨트롤러는 외부 입력값(external input)과 기존 메모리에 존재하던 값을 합쳐 입력 데이터로 활용합니다. 컨트롤러는 읽기 헤드를 이용해 메모리에 저장될 벡터와 메모리에서 읽어야할 벡터를 위해 필요한 값들을 출력합니다. 이렇게 출력된 값들은 읽기 헤드와 쓰기 헤드를 구성하는데 이용됩니다.

읽기/쓰기 헤드에서 값을 읽고 저장하기 위해서는 메모리의 위치를 선택해야 합니다. 위치를 선택하기 위한 매커니즘은 크게 내용 기반 주소 지정 방식(content-based addressing)과 위치 기반 주소 지정 방식(location-based addressing)으로 나눠집니다. 위치 주소 지정 방식은 내부적으로 Interpolation, Convolutional Shift, Sharpening 과정으로 이루어져 있습니다.

컨트롤러가 메모리에서 위치를 찾고 연산하는 전체의 과정은 미분이 가능하기 때문에 기울기 하강 방법을 통해 학습이 가능합니다. 이렇게 학습된 NTM 모델은 임의의 시퀀스 데이터를 입력받아 입력 값을 그대로 출력하는 Copy Problem 실험과 이를 더 확장하여 반복하는 Repeat Copy 실험에서 LSTM보다 더 좋은 성능을 보여주고, 정렬 알고리즘과 같은 간단한 알고리즘을 학습하는 것도 가능합니다.

✅ Memory Augmented Neural Networks (MANN)

문헌 (1) 내용을 추가하였습니다.

A. Santoro 외(2016)가 제안한 MANN(Memory Augmented Neural Networks) 모델은 기존의 NTM 모델에서 일부를 변형한 모델입니다. MANN은 읽기 및 쓰기 작업의 반복성 때문에 RNN(Recurrent Neural Networks)의 특수한 유형입니다. 하지만, MANN은 DKT에서 사용된 전통적인 LSTM과 세 가지 주요 차이점이 있습니다.

	DKT의 전통적 LSTM	MANN
인코딩 방식	단일 숨겨진 상태 벡터를 사용해 시계열 정보를 인코딩	외부 메모리 행렬을 사용해 저장 용량을 증가시킴
상태 전이 처리 방식	전역적으로 처리	읽기 및 쓰기 작업을 통해 지역적인 상태 전이를 유도
매개 변수 수	숨겨진 상태의 크기와 관련이 있음	메모리 슬롯의 수를 늘려도 매개 변수 수가 증가하지 않아 계산 효율성이 더 높음

또한, NTM 모델과의 가장 큰 차이점은 내용 기반의 주소 지정 방식만을 사용하고 LRUA (Least Recent Used Access) 모듈이 추가된 점입니다.

NTM과 같이 메모리를 추가한 모델은 모든 경우의 수를 학습시키는 것이 아닙니다. 사전에 알려주지 않은 정보라도 과거에 저장된 메모리의 값을 이용해 활용 및 추론할 수 있다는 장점이 있습니다. 이때 메모리 업데이트의 시기를 빠르게, 혹은 느리게 조절하면 단기적인 기억은 물론, 장기적인 기억도 추출이 가능하도록 변경할 수 있습니다. 이러한 점을 이용하면 데이터의 유형을 분류하는 방법을 배우는 일종의 메타 학습뿐만 아니라, 정보들의 연관성에 대한 단기 기억에 집중하여 데이터가 소량이거나 충분하지 않을 때에도 효과적으로 활용할 수 있습니다.

MANN 모델의 전체적인 아키텍처는 Fig.2 와 같습니다. MANN 모델의 읽기 메커니즘은 메모리에서 관련성 있는 정보를 판단하기 위해 먼저 컨트롤러의 출력 값인 키 벡터($k_t$)와 메모리의 각 행($M_t(i)$)을 이용해 코사인 유사도를 구합니다. 여기서 i는 메모리 번지를 의미합니다.

MANN 모델은 NTM 모델이 사용하였던 위치기반의 주소지정 방식을 사용하지 않은 대
신, LRUA 모듈을 추가하여 정보와의 연결성에 집중되도록 변형하였습니다. 결국, LRUA 모듈은 미사용된 메모리 위치에 새로운 정보를 쓰고, 마지막으로 사용된 위치에 최근 이용된 정보 또는 연관 정보를 다시 저장하게 하는 모듈로서, 정보 연결성을 강조하는 기능을 합니다. 이렇게 학습된 신경망은 정보들의 연관성을 이용한 분류 방법을 학습하기 때문에 Omniglot 데이터셋과 같은 소량의 데이터를 분류할 때 좋은 성능을 보여줍니다.

3 MODEL : DKVMN

MANN은 기존 LSTM보다 강력한 성능을 보이지만, KT 작업에서는 몇 가지 한계가 있습니다.

1. 읽기와 쓰기 작업이 동일한 메모리 공간에서 이루어지기 때문에, 입력과 예측(문제와 정답)이 서로 다른 타입임에도 이를 동일하게 처리합니다.
2. 개념을 명시적으로 모델링할 수 없어 특정 개념의 지식 상태를 추적하기 어렵습니다.

이를 해결하기 위해 DKVMN은 키-값 쌍을 사용합니다. 입력(문제)은 변하지 않는 키에 매핑되고, 학생의 지식 상태는 값 부분에서 추적됩니다. 각 시간 단계에서 DKVMN은 문제 태그 $qt$를 받아 학생의 정답 확률 $p(rt|qt)$를 출력하고, 그 후 문제와 정답 쌍($qt, rt$)을 메모리의 값 부분에 업데이트합니다.

키 행렬 : 개념을 저장하는 역할 / 변경 X
값 행렬 : 각 개념에 대한 학생의 이해도를 저장하고 갱신하는 역할 / 학생의 학습 상태에 따라 동적으로 변화

DKVMN은 각 시점에서 새로운 문제 $qt$가 주어졌을 때, 해당 문제에 필요한 개념을 찾아 관련된 개념 상태만을 업데이트합니다. 이 모델은 하나의 정적 키(key) 행렬과 하나의 동적 값(value) 행렬을 사용하여 학습을 진행합니다.

키 행렬($Mk$)에는 문제에 대응하는 N개의 잠재 개념이 저장되고, 값 행렬($Mv$)에는 각 개념에 대한 학생의 숙련도가 저장됩니다. 상관 가중치 $wt$는 입력 문제 $qt$의 임베딩 벡터와 키 행렬 $Mk$의 내적을 통해 계산되며, 이는 문제와 잠재 개념 간의 상관 관계를 나타냅니다.

읽기 과정에서는 문제와 관련된 학생의 숙련도를 요약한 값을 얻고, 이 값을 문제의 난이도와 결합해 학생의 성취도를 예측합니다. 쓰기 과정에서는 학생이 문제를 푼 후, 그에 따른 지식 상태 변화 $vt$를 메모리에 쓰기 위해 먼저 메모리를 지우고, 새로운 정보를 추가합니다. 이 과정에서 학생의 학습에 따른 개념 상태가 강화되거나 잊혀집니다.

DKVMN 모델은 크로스 엔트로피 손실 함수를 통해 학습되며, 학습 중 모든 매개 변수와 초기 메모리 상태가 최적화됩니다. 이 모델은 전적으로 미분 가능하며, 확률적 경사 하강법(SGD)으로 효율적으로 학습할 수 있습니다.

DKVMN의 주요 특징을 정리하면 다음과 같습니다.

1. 메모리 증강 신경망(MANNs)을 활용하여 학생의 학습 과정을 보다 효과적으로 시뮬레이션
2. 정적 키 행렬과 동적 값 행렬을 도입하여 개념 상태 추적
3. 개념 자동 발견 : 보통 사람이 수행하는 개념 발견 작업을 자동으로 수행하며, 학생의 지식 상태 변화를 추적
4. 성능 향상 : BKT와 DKT보다 우수한 성능

4 Experiments

실험 결과를 요약하면 다음과 같습니다.

1. DKVMN은 네 개의 데이터셋에서 표준 MANN과 최신의 DKT 모델보다 뛰어난 성능을 보였습니다.
2. DKVMN은 DKT보다 적은 매개변수로 더 나은 결과를 도출했습니다.
3. DKVMN은 DKT가 겪는 과적합 문제를 겪지 않았습니다.
4. DKVMN은 입력된 문제에 대한 잠재 개념을 정확하게 발견할 수 있었습니다.
5. DKVMN은 시간에 따라 학생의 개념 상태를 묘사할 수 있었습니다.

✅ 데이터셋

실험에 사용된 네 개의 데이터셋은 다음과 같습니다.

Synthetic-5

이 데이터셋은 2,000명의 가상 학생들이 50개의 문제를 푸는 과정을 시뮬레이션한 것으로, 훈련 및 테스트 데이터셋 모두 동일합니다. 각 문제는 다섯 가지 숨겨진 개념 중 하나에서 출제되며, 난이도가 다릅니다. 훈련 과정에서 개념 레이블에 접근할 수 없으며, DKVMN 모델의 개념 발견 결과를 평가하기 위해서만 사용됩니다.

ASSISTments2009

온라인 튜터링 플랫폼 ASSISTments에서 수집된 데이터셋입니다. 중복된 기록 이슈로 인해 업데이트된 버전인 "skill-builder" 데이터셋을 사용했습니다. 사전 처리 과정에서 스킬 이름이 없는 기록은 제외하여, 총 4,151명의 학생이 110개의 서로 다른 문제 태그로 구성된 325,637개의 문제를 푼 데이터를 사용했습니다.

ASSISTments2015

이 데이터셋은 100개의 스킬에 대한 학생 응답만을 포함하며, 사전 처리 후 19,840명의 학생으로부터 683,801개의 유효한 기록을 얻었습니다. 각 문제 세트는 하나의 스킬과 연관되어 있습니다. 이 데이터셋은 기록 수는 가장 많지만, 학생당 평균 기록 수는 가장 적습니다.

Statics2011

대학 수준의 공학 정역학(statistics) 강좌에서 수집된 데이터셋으로, 333명의 학생이 1,223개의 문제 태그로 구성된 189,297번의 시도를 포함합니다. 실험에서는 문제 이름과 단계 이름을 결합하여 문제 태그로 사용했습니다. 이 데이터셋은 가장 많은 문제 태그와 학생당 평균 기록 수를 가지고 있습니다.

✅ 구현 세부사항

입력 데이터 표현

문제 데이터를 신경망에 원-핫(One-hot) 벡터로 표현했습니다. 총 Q개의 서로 다른 문제가 있을 때, 문제 태그 $qt$는 길이 Q의 벡터로 표현되며, $qt$번째 요소만 1이고 나머지는 0입니다. 값(value) 메모리 부분의 결합 입력 $xt = (qt, rt)$는 길이 2Q의 벡터로, $xt = qt + rt * Q$ 위치에 1이 위치합니다.

메모리 초기화

키(key)와 값(value) 메모리의 초기값은 훈련 과정에서 학습됩니다. 키 메모리의 각 슬롯은 개념 임베딩이며, 테스트 과정에서는 고정됩니다. 값 메모리의 초기값은 각 개념의 초기 난이도를 나타냅니다.

데이터 분할

모든 데이터셋에서 30%의 시퀀스를 테스트 세트로 사용했으며(합성 데이터셋은 훈련과 테스트 데이터셋 크기가 동일), 훈련 세트의 20%는 검증 세트로 사용했습니다.

훈련 설정

매개변수는 평균이 0이고 표준편차가 σ인 가우시안 분포에서 무작위로 초기화했습니다. 학습률은 데이터셋마다 다르게 설정했으며, 에포크 20마다 학습률을 γ/1.5로 감소시켰습니다. DKT 구현에는 LSTM을 사용했고, 표준 MANN은 코사인 유사도 읽기 어텐션 메커니즘과 LRUA 쓰기 어텐션 메커니즘을 사용했습니다. 모든 실험에서 모멘텀 0.9와 노름 클리핑 임계값 50.0을 사용하여 확률적 경사 하강법으로 모델을 학습했습니다. 입력 시퀀스의 길이가 다양하므로, 모든 시퀀스를 길이 200(합성 데이터셋은 길이 50)으로 설정하고, 짧은 시퀀스는 null 심볼로 패딩했습니다.

하이퍼파라미터 튜닝

모든 경우에 5겹 교차 검증을 사용하여 하이퍼파라미터를 튜닝했습니다. 테스트 AUC는 100개의 에포크 중 검증 AUC가 가장 높은 모델을 사용하여 계산했습니다. 각 훈련을 서로 다른 초기화 σ로 5회 반복하여 평균 테스트 AUC와 표준편차를 도출했습니다.

✅ 학생 수행 예측

평가 지표

AUC(곡선 아래 면적)를 측정했습니다. AUC 50%는 무작위 추측과 동일한 수준이며, AUC 값이 높을수록 예측 성능이 좋음을 의미합니다.

결과 비교

DKVMN 모델을 MANN, 최신의 DKT, 표준 BKT 모델과 비교했습니다. 우리의 LSTM 구현은 원본 논문보다 더 높은 AUC를 달성했는데, 이는 그래디언트 클리핑과 조기 종료를 사용하여 과적합 문제를 개선했기 때문입니다.

DKVMN은 모든 데이터셋에서 다른 방법들보다 우수한 성능을 보였으며, 특히 문제의 종류가 많은 Statics2011 데이터셋에서 두드러졌습니다. 이는 DKVMN이 많은 수의 문제를 가진 상황에서도 학생의 지식 상태를 잘 모델링할 수 있음을 보여줍니다.

✅ 자동 개념 발견

DKVMN 모델은 전통적으로 전문가가 주석을 다는 개념을 자동으로 발견할 수 있습니다. 상관 가중치 $w$를 사용하여 문제와 개념 간의 내적 관계를 파악합니다.

Figure 4 : Synthetic-5 데이터셋을 활용한 개념 발견 결과입니다. 각 문제는 5개의 숨겨진 개념 중 하나에서 출제되며, DKVMN은 메모리 크기가 5일 때 각 문제를 정확하게 해당 개념에 할당했습니다.

Figure 5 : ASSISTments2009 데이터셋을 활용한 개념 발견 결과입니다. 문제 태그명을 사용하였습니다. t-SNE를 사용하여 다차원 상관 가중치를 2D로 투영한 클러스터링 그래프에서, 유사한 문제들이 합리적으로 군집화된 것을 확인했습니다. 예를 들어, "분수 정렬", "정수 정렬", "양의 소수 정렬", "실수 정렬"과 같은 문제가 같은 클러스터에 속해 기본 산술 개념을 드러냈습니다.

✅ 지식 상태 묘사

DKVMN은 학생의 개념 상태 변화를 시간에 따라 묘사할 수 있습니다. 이는 온라인 학습 플랫폼 사용자들에게 유용하며, 학생들이 자신의 강점과 약점을 파악하고 학습 격차를 독립적으로 메울 수 있도록 도와줍니다.

먼저, 특정 개념의 상관 가중치를 1로 설정하여 해당 개념의 값(value) 메모리 내용을 읽어옵니다. 그 후, 입력 임베딩의 가중치를 마스킹하여 문제 정보의 영향을 배제합니다. 최종적으로 해당 개념의 숙련도 수준을 예측하는 스칼라 값을 계산합니다.

Figure 6에서는 한 학생의 다섯 가지 개념 상태 변화를 보여줍니다. 초기 상태는 개념마다 다르며, 학생이 각 문제를 풀 때마다 해당 개념의 상태가 증가하거나 감소합니다. 예를 들어, 학생이 처음 세 문제를 맞추면 두 번째와 다섯 번째 개념 상태가 증가하고, 네 번째 문제를 틀리면 세 번째 개념 상태가 감소합니다. 50개의 문제를 푼 후, 학생은 두 번째, 세 번째, 네 번째 개념을 숙달했지만 다섯 번째 개념은 이해하지 못한 것으로 나타났습니다.

---

💡 Insight

웅진씽크빅 에듀테크 연구소에서는 DKVMN과 SAKT 두 모델을 각각 다음과 같이 연계하는 방식으로 학습 모델을 구현하였다고 합니다.

DKVMN
문항 간 관계를 자동으로 탐지하여 지식개념 추출

SAKT
산출된 지식개념을 메타정보로 활용하여 학생들의 지식수준의 이해도를 예측

DKVMN이 실 활용에 있어서 강점을 지니는 부분이 바로 위와 같은 활용, 즉 개념 추출 방식이라고 생각하는데요. 이때 헷갈리지 말아야 할 점은, 개념 추출이 오토태깅은 아니라는 것입니다. 오토태깅처럼 특정 항목에 새로운 태그를 지정하는 것이 아니라, 항목들 간 숨겨진 구조나 관계를 찾아내어 그룹화하거나(유사한 개념끼리 클러스터링) 태그명 목록에서 할당하는 것을 의미합니다.

DKT

• 문항에 대한 지식 개념을 직접적으로 학습하거나 추출 X
• 입력으로 주어진 문항에 대한 레이블(knowledge concept)에 대해 학생의 학습 이력을 바탕으로 다음에 맞힐 확률을 예측 (문항이 이미 특정 지식 개념과 연결되어 있어야 하며, 개념을 자동으로 발견하는 기능은 X)
  
  DKVMN
• 문항 간의 관계를 자동으로 탐지하고, 이를 통해 지식 개념(knowledge concepts)을 추출
• 외부 메모리 구조를 사용하여 학생의 상호작용 데이터를 저장하고, 문항과 지식 개념 간의 관계를 학습
• key-value 메모리 구조를 통해 자동적으로 문항에 해당하는 지식 개념을 찾아내어, 사람이 일일이 개입하지 않아도 자동으로 지식 개념 학습 가능

이전에 유사도 챗봇을 만들어 보면서 제로샷 분류 모델을 사용했었는데요. 제로샷 분류를 위해서는 클래스에 대한 설명 정보가 필요했습니다. 이와 DKVMN의 자동 개념 추출은 또 다르지만 지식 추적 결과에 따른 맞춤 문항 제공을 위해 문항 분류가 필수적이기에, 일일이 사람이 수작업으로 태깅하는 것보다 DKVMN의 활용이 효율적일 수 있겠다고 생각했습니다. DKVMN으로 갖고 있는 데이터셋에 자동 개념 추출 작업을 시도해 보고 싶네요.

---

참고문헌

(1) 강민철 and 김휘강. (2018). 메모리 추가 신경망을 이용한 희소 악성코드 분류. 정보보호학회논문지, 28(4), 847-857.