Dkt(deep_knowledge_tracing)_논문_해석

Deep Knowledge Tracing

• https://stanford.edu/~cpiech/bio/papers/deepKnowledgeTracing.pdf

논문 설명(서론)

• 지식추적(Knowledge Tracing)은 학생이 학습과정과 상호작용한 지식을 모델링한 것이며, 컴퓨터 지원 교육에서 잘 확립된 문제입니다. 이에 RNN계열 모델을 이용해 학생 지식의 더 복잡한 표현을 포착할 수 있으며, 다양한 지식 추적 데이터 셋에 대한 예측 성능이 향상되고 이를 학습한 모델은 지능형 커리큘럼 설계에 많은 도움을 줄 수 있습니다.

논문 설명(본론)

• 이미 기존의 수작업으로 만든 지능형 튜터링 시스템은 학생의 학습 추이를 볼 때 이런 추세라면 나중에는 어느 문제까지 풀 수 있고, 또 그러지 못할 것이란걸 알 수 있습니다.
• 이때 머신러닝을 접목시키므로서 학생에게 일대일과외의 효과를 부여할 수 있고, 또한 고품질의 개인화 교육을 무료로 제공할 수 도 있습니다.
• 지식 추적문제는 인간의 뇌와 지식 간의 복잡성에 기반을 두고 있기 때문에 본질적으로 어렵습니다. 그러나 교육 분야에서 대부분은 한계를 가진 1차 마르코프 모델을 사용했다고 합니다.

RNN기법을 적용한 ‘Deep’ Knowledge Tracing

• 이 논문에선 유연한 RNN 기법을 접목시켜서 Deep Knowledge Tracing(DKT) 방식을 제공합니다. 이 모델은 유동적인 잠재지식 상태를 표현하고, 데이터 기반 학습을 통해 학생 지식의 잠재적 변수를 표현합니다.

• 이 작업의 주요 기여는 다음과 같습니다.

  1) RNN의 입력으로서 학생 상호작용을 새로 표현하는 법

  2) 과거의 결과보다 AUC가 25% 증가

  3) 전문적인 주석이 필요하지 않는 지식 추적 모델임을 증명

  4) 학습의 영향력의 발견과 교육과정의 발전

• 학생 한 명이 50 문제를 풀고 그에 대한 정답률

• 지식 추적은 다음과 같이 공식화된다.

  • 학생의 특정 학습 과제에서 관찰된 상호작용 : x0 ~ xt
  • 다음 상호작용에 대한 예측 : x(t + 1)
  • 튜플 형태의 상호작용 (문제태그, 정답 여부): xt = (qt, at)

• 예측을 할 때, 이 모델은 답변된 문제의 태그(qt)를 제공받고, 정답여부(at)를 반드시 예측한다.

• 위 그림은 8학년 학생의 지식을 추적해 시각화 한 것이다. 첫 제곱근 문제는 맞췄지만, x절편 문제는 틀렸다. 47번의 문제풀이 이후 학생은 x절편, y절편, 그래프 문제를 풀었다.
• 매 번 학생은 한 문제씩 풀고, 다음 문제에서 각 문제 종류별로 맞출 확률이 얼마인지 예측을 할 수 있었다.
• 대부분의 이전 지식 추정 연구들은 인간 전문가가 하나 하나 개념을 입력해야 했다면, 이 모델은 필수적이지 않고 자율적으로 학습할 수 있다.

관련 연구

• 인간이 학습하는 방식을 모델링하고 예측하는 연구는 교육, 심리학 등 다양한 분야에서 알려졌다. 사회과학적 관점에서 학습이란 주변영향, 동기, 정체성 등 거시적 수준에서 영향받는다고 알렸다. 그러나 현재는 좀 더 미시적 수준까지 봐야한다.
• 인지 과학 분야에서 특히 관련된 두 가지 문제는 인간의 마음과 그 학습과정이 반복적이고, 유추에 의한 것이다. 이때문에 모든 인지 과정을 포착할 수는 없지만 최대한 유요한 모델을 만드는 것이 관련 연구들의 주 목표였다.

1) 베이지안 지식추적(Bayesian Knowledge Tracing)

• 베이지안 지식추적은 학생 학습의 연속적 모델을 만드는데 가장 유명한 접근법이다. 학습자의 잠재 지식 상태를 한 개념에 대한 이해와 비이해 두 변수로 모델링하였으며, HMM(Hidden Markov Model)이 주어진 문제에 대한 대답으로 이진 변수의 확률을 조정한다. 원래는 한 번 배우면 잊지 않는다는 가정하에 만들어졌으나, 최근에는 다양한 확장이 이뤄졌다.
• 문제는 이러한 확장과 관계없이 다양한 문제를 가지고 있는데, 학생 이해에 대한 이진 표현이 비현실적이단 점, 숨겨진 변수와 의미가 문제에 대한 매핑이 모호하고 문제 당 단일 개념에 대한 모델 기대치를 충족시키지 못한 점, 현재 기준 인지 분석 작업이 전문가가 학생이 문제를 해결하는 동안의 사고과정을 힘들고 반복적으로 체크해한다는 점, 마지막으로 이진 분류 데이터는 다양한 모델을 사용하는데 제한적이란 점이다.

2) 기타 동적 모델

• POMDP(Partially Observable Markov Decision Processes): 학생이 해답에 도달하기 위한 자유로운 방법을 따르는 경우 시간에 따른 행동을 모델링하기 위해 사용한다.
• Performance Factors Analysis(PFA) & Learning Factors Analysis(LFA): 앙상블 기법을 사용해 BKT와 PFA를 결합하기도 했다. 다양한 Feedfoward 신경망이 좋은 결과를 냈지만, 정확한 개념 라벨링에 대한 요구 사항을 포함한 한계에 부딛친다.
• IRT(Item Response Theory): 최근 연구에선 IRT모델을 비선형 kalman필터 및 지식 추적과 결합하려는 시도가 있었다. 이런 연구가 유망하지만, 현재로서는 DKT보다 기능적 형대가 제한적이고 더 비싸다.

3) Recurrent Neural Networks

• 순환신경망(RNN)은 시간에 따른 인공뉴런을 연결하는 유연한 동적모델군이다. 정보의 전파는 시스템에 대한 입력과 그 이전의 행동을 기반으로 숨겨진 뉴련이 발전하는 방식이 반복적으로 이뤄진다. 특히 RNN은 은닉 마르코프 모델에 비해 높은 차원의 연속적 잠재 상태를 표현할 수 있다. 이런 RNN의 이점이 나중 시점의 예측에 예전 정보를 사용할 수 있단 것이다.(특히 LSTM)

Modeling

우리는 인간의 학습이 물질, 맥락, 시간의 흐름, 개인적 경험 등 다양한 속성에 의해 이뤄진다고 생각한다. 그러나 이런 다양한 속성들은 문제에 할당하거나 모델을 구축하는 제1원칙에만 의존해서 수량화할 수 없다. 그래서 두 RNN - vanilla RNN with sigmoid, LSTM- 을 이용해서 학생의 과거에 기반해 미래를 예측하는 문제에 적용시킨다.

1) Model

• 전통적인 RNN들은 input vector(x1, …, xt)를 output vector(y1, …, yt)로 매핑하는 것이다. 이는 미래 예측에 효과적인 과거로부터의 관련 정보를 성공적으로 인코딩하는 hidden state(h1, …, ht)의 시퀀스를 계산하면서 발전해간다.

• 변수들은 다음과 같은 방정식에 의해 정의된 간단한 네트워크로 이뤄진다.

• tanh와 sigmoid는 σ로 표현되며 elementwise다
• Whx는 input 가중치 행렬
• Whh는 hidden state 가중치 행렬
• h0는 초기 state
• Wyh는 readout 가중치행렬

• bh and by는 latent와 readout의 bias

• LSTM은 RNN보다 복잡하여 더욱 강력하다. LSTM의 latent unit는 ‘forget gate’의 작동에 의해 완전히 지워질때까지 값을 유지한다. 더 쉽게 학습하기 위해 많은 step동안 정보가 자연스럽게 유지된다. 추가적으로 hidden unit은 제곱 상호작용으로 업데이트 되고, 같은 수의 latent unit에 대해 더 복잡한 변환을 수행할 수 있다.

2) Input과 Output Time Series

• RNN나 LSTM으로 학생 상호작용을 학습하기 위해 이 상호작용을 고정된 길이의 입력 벡터 x(t)의 튜플으로 변환시켜야 한다.

• 작은 문제 수 M정도의 데이터셋을 위해 우리는 x(t)을 문제가 답변 되었는지, 답변이 정답인지에 대한 학생 상호작용 tuple h(t) = {q(t), a(t)}을 원-핫 인코딩 형식으로 만들어야한다.

• 넓은 feature 공간에서, 원-핫 인코딩은 빠르게 비현실적으로 커진다. 대신에 많은 문제의 데이터 셋에서 input 튜블에 랜덤 벡터를 할당한다.(n q,z ~ N(0, I)) 각각의 입력 벡터 xt에 해당하는 랜덤 벡터 xt = n q(t),a(t) 을 설정한다. 이 높은 차원의 원-핫 벡터의 작은 차원으로의 랜덤 표현은 압축 센싱에서 착안했다.d 차원의 k-sparse(희박) 신호 압축 센싱 상태는 정확히 klogd 랜덤 선형 투영에서 복구될 수 있다.원-핫 인코딩이 1-sparse 신호 일 때, 학생 상호작용 튜플은 정확하게 고정된 랜덤 가우시안 입력 벡터(길이가 ~log2M)로 할당되어진다.

• output yt는 문제 수와 같은 길이의 벡터인데, 각각의 값은 학생이 특정 문제를 정확하게 답변할 예측 확률이다. 그렇기에 a(t+1) 의 예측은 yt의 q(t+1)에 의해서 예측된다

3) Optimization

• 학습 목적은 모델에 의한 학생 반응 시퀀스의 negative log likelihood이다. δ(qt+1) 을 t+1 시점의 답변의 원-핫 인코딩이라고 하고 l을 binary cross entrop라 하자. 주어진 한 예측에 대한 loss는 l(yTδ(qt+1), at+1)이고, 한 학생에 대한 loss는 아래와 같이 표현된다.

• 이 목적은 SGD(stochastic gradient descent)를 이용해 최소화하는 것이다. overfitting을 방지하기 위해, yt가 계산되 나올때 ht에 Dropout을 시행하지만, ht+1계산에서는 사용하지 않는다. 또한 exploding을 막기 위해 threshold보다 높은 평균의 gradient의 길이를 줄여 역전파를 실시했다. 이 논문의 모든 모델은 hidden차원은 200, 미니배치는 100의 크기로 정했다.

교육적 활용

• 지식 추적을 위한 학습 목표는 학생의 과거 활동에 기반해 미래 실력을 예측하는 것이다. 이는 매우 유용한데, 임시적 공식 시험없이 학생의 능력을 지속적으로 평가할 수 있기 때문이다.

1) 커리큘럼 개선

• 이 모델의 가장 큰 잠재적인 점은 현재 학생이 최고의 학습아이템을 선택할 수 있다는 것이다. 추저된 잠재학습력을 학생이 주어지면, RNN에 물어서 특정 문제를 제시할 경우 예상되는 지식 상태를 계산할 수 있다.
• 두 가지 고전적 교과과정 규칙을 테스트 하는데 훈련된 DKT를 사용했다. (다른 주제가 혼합된 mixing, 동일한 타입의 문제에 대답하는 blocking)

2) 문제 관계 개선

• DKT 모델은 인간 전문가가 수행하는 작업인 데이터의 잠재구조 또는 개념 발견에 추가로 적용할 수 있다. 문제 i 와 j의 모든 직접적인 pair에 대해 영향 Jij를 할당해 이 문제에 접근했다.
• y(j|i)는 첫 번째에서 문제 i를 정확하게 맞췄을 때 다음 스탭에서 문제 j를 맞출 확률이다. 이런 RNN에 의해 나타난 종속에 의한 특징이 문제와 관련된 전제조건을 복구한다.

Datasets

• 시뮬레이션 데이터, Khan Academy 데이터, Assistment 벤치마크 데이터, 세 개로 학생 성과를 예측하는 능력을 테스트했다. 각 데이터 세트에서 AUC를 측정한다. 시뮬레이션 되지 않은 데이터의 경우 5-fold 교차검증을 실시했다. 이런 결과를 BKT결과와 단순계산한 확률과 비교했다.

결과

• 세 데이터셋에서 모두 DKT가 이전 방법보다 좋은 결과를 가져왔다. 칸 데이터에선 기존 BKT방식보다 LSTM모델을 이용해 AUC수치에서 훨씬 좋은 값을 얻었다. 이는 Assistment 데이터에서도 마찬가지였다. 아래 그림을 보면, 높은 수준의 정확도를 얻기위해서 모델은 잠재 개념, 각 문제의 난이도, 학생 수준의 사전정보와 문제를 풀고난 후의 향상된 지식 세 가지를 통합하는 기능을 모방해야 한다.

• 이런 예측률을 이용해 DKT모델이 숨겨진 문제간의 구조를 찾아낼 수도 있다. 아래 그림을 통해 이모델이 5개의 숨겨진 구조를 완벽하게 clustering한 것을 그래프로 볼 수 있다.