Cseal_논문_리뷰

Exploiting Cognitive Structure for Adaptive Learning

• https://arxiv.org/abs/1905.12470

0. Abstract

• 적응형 학습(Adaptive learning)이란 개별 학습자에게 학습항목(learning item)을 제공하는 것이다.
• 인지구조(cognitive structure)는 지식 수준(knowledge level)과 지식 구조(knowledge structure)로 이뤄져 있는데, 이전 방법들은 둘 중 한 것만 다뤘다면 CSEAL(Cognitive Structure Enhanced framework for Adaptive Learning)은 두 개를 동시에 이용한다.
• 그 과정은 3단계로 나눌 수 있는데 학습자의 지식 수준을 추적하고, 학습 경로를 파악할 지식 구조를 탐색하고, 다음은 무엇을 학습할지 결정하는 것이다.

1. Introduction

• 적응형 학습은 학습자의 현재 지식수준과 학습 항목 간의 선수지식(prerequistie)을 이용해 ‘두 자리 수 더하기’ 후 ‘곱셈’처럼 적절한 학습 경로를 제시하는 것이다.
• 지식 수준 혹은 지식 구조만 이용한 적응형 학습은 부족한 면을 보여왔다. 그래서 두 개념을 모두 이용하는 인지구조를 활용한다면 이 점을 해결할 것이다.
• 이를 위해 3가지 과제가 존재한다.
  • 학습자의 지식 수준은 직접 관찰할 수 있지 않으며, 학습에 의해 계속 변하므로 이를 표현할 방법이 필요하다. –> 지식 추적(knowledge tracing) 모델을 이용해 지식 수준을 파악
  • 지식 구조는 논리적인 학습경로를 가져야한다. –> 인지 탐색(Cognitive Naviagtion)알고리즘을 통해 지식 구조 기반의 후보 학습항목을 선택
  • 한 단계가 아닌 모든 학습경로를 거친 후의 성과가 좋은 학습경로를 추천해야한다. –> Actor-Critic 강화학습 알고리즘을 이용해 이후 학습할 내용을 결정하고 파라미터를 갱신

2. Relation work

• Learing path recommendation
• Cognitive structure
• Reinforcement learning

3. Preliminaries

용어 정리

• Learning session : 학습 세션은 학습 목표(learning target)를 가지고 있으며, 학습자가 학습하기 위한 항목이 나열된 학습경로와 그 학습경로를 통한 학습효과(learning effectiveness)를 측정하기 위한 시험(examinations)으로 구성되어있다.
  • 학습 세션의 효과를 표현하는 점수 \(E_P=\frac{E_e-E_s}{E_{sup}-E_s}\)
  • $E_s$는 학습 시작 시 점수
  • $E_e$는 학습 종료 시 점수
  • $E_{sup}$는 만점
• Prerequistite graph : 지식 그래프의 서브그래프이며, 학습 항목 간의 계층적 구조를 표현하기 위해 DAG형태이다. 즉, 각 개념을 알기 위해 먼저 알아야하는 선수 지식을 표현한 그래프이다.

정의

• target T = {$t_0, t_1, … $} : 학습하기 위한 하나 이상의 학습 항목
• historical learning record H = {$h_0, h_1, …, h_m $} : 이전의 학습 세션에서 만들어진 기록
  • 각 $h_i$는 {k, score}로 이뤄져있으며 이때 k는 학습 항목, score는 문항 응답(보통 0 or 1로 정오표현)이다.
• learning path P = {$p_0, p_1, …, p_N $} : N개의 항목이 나열된 학습 경로
  • 단계 i에서 학습 항목 $p_i$가 추천되고, 그에 대한 기록 $F_i = (p_i, score_i)$가 발생한다.
• 학습 세션이 끝나면 학습 효과 $E_P$를 구할 수 있다.
• 결국 H, T, G(Prerequistite graph)가 주어지면 $E_P$를 최대화하는 경로 P를 구하는 문제

4. CSEAL

Knowledge tracing

• 지식 추적은 이전 학습 기록들 $L_{i-1} = H \oplus F_{0,1,…i-1}$을 이용해 학습자에 내재된 지식 수준 $S_i$를 표현할 수 있다. 즉, DKT 모델을 이용해 이전 학습 기록 $L_t$ = {$p_t, score_t$}마다 $score_t$를 추정한다.
• 이때 embedding 차원은 그래프 G의 노드의 갯수 M을 이용한다. 아웃풋 역시 M차원 벡터이다.
  • DKT에 대한 자세한 내용은 이전 게시글을 참고하자.
  • https://lemma1727.github.io/DKT(Deep_Knowledge_Tracing)_%EB%85%BC%EB%AC%B8_%ED%95%B4%EC%84%9D/

Cognitive naviagtion

• 학습 항목 간의 관계를 표현하는 지식 구조는 논리적으로 배열되어야한다. 그러나 지식 수준과 지식 구조의 결합이 가지는 복잡성 때문에 명확한 해결책을 쉽게 낼 수 없다.
• 대신 빠르게 잠재 후보를 고르는 방법을 선택한다. 이러한 잠재 후보들은 권장 학습 항목이 경로의 논리성을 위반하는 것을 방지할 뿐만 아니라 넓은 검색 공간을 줄일 수 있다.
• 막 학습이 끝난 항목3을 ‘central focus’라고 하자. 그렇다면 선수학습 항목인 0,1,2를 다시 검토하거나, 후행학습 항목인 4를 살펴볼 수 있는데 이들이 바로 후보(candidate)이다.
• 이 후보들 중에서 다음에 학습할 항목을 정한다.
• 알고리즘은 다음과 같다.

Actor-Critic recommender

환경 셋팅

• 우리의 타겟은 인지구조 기반의 맞춤형 학습경로를 제시하는 것이다. 그래서 decision making problem으로 연속적인 학습경로 생성을 모델링하고 이를 MDP(markov decision process)으로 다룬다.
• State
  • 매 스텝마다 $state_i$는 학습 목표 T와 현재 지식 수준 S의 결합으로 표현된다.
  • 학습 목표 T는 원-핫 인코딩으로 표현한다. \(T=\{0,1\}^M ; T^j = \begin{cases}1&if \;j \;in \;the \;learning \;target\\0&otherwise\end{cases}\) 이때 M은 선수지식 그래프의 노드 갯수
  • 그러나 현재 지식 수준은 바로 확인할 수 없어서, 이전 학습을 통한 기록 H과 현재 학습 경로를 따르면서 생긴 기록 $F_{0,…,i-1}$을 합친 $L_{i-1}$으로 대체한다.
• Action
  • 매 스텝마다 $a_i$는 학습 항목 $p_i$을 추천한다.
  • 이는 다음 분포를 따르는 stochastic policy이다 \(\pi_\theta(a \mid state_i) = P_\theta(a \mid H,F_{0,...,i-1},T)\)

  $\theta$는 모델 파라미터이다.

• Reward
  • 행동을 취하게 되면 보상 받게 되는데, 스텝 i에서의 보상 $r_i$는 0으로 설정한다. 이후 행동들에 대한 보상만 고려하기 때문이다.
  • 한 번 learning session이 종료되면 보상은 $E_P$이며, 우리의 목적은 각 스텝마다 discount reward의 합 $R_i$을 최대화 하는 것이다.
  \[R_i = \sum_{j=0}^{N-i} \gamma^jr_{i+j}\]

  $\gamma$는 discount factor이며 0.99로 설정했다.

actor-critic 알고리즘

• 현재 학습 수준에 맞게 적당한 후보를 선정하기 위해 사용됐다.
• actor
  • CN에서 구한 후보 집합 D에서 $\pi_\theta(a \mid state_i)$를 이용해 action을 취하는 policy network
  • policy gradient를 이용해 학습한다. \(\nabla_\theta = log \;\pi_\theta(a \mid state_i)(R_i - v_i)\)
• critic
  • 각 state에서의 expected return을 평가하는 value network
  • $state_i = S_i \oplus T$를 input으로 받아, i단계의 expected return은 다음과 같이 계산한다. \(v_i = V_\theta(state_i) = V_\theta(S_i \oplus T)\)
  • 예상하는 value $v_i$와 실제 보상 $R_i$간의 거리를 최적화하며 학습한다. \(Loss_{value} = \left\| v_i - R_i \right\|^2_2\)
• 최종 loss function \(\left\| V_w(state_i) - R_i \right\|^2_2 + \alpha \cdot log \;\pi_\theta(a \mid state_i)(R_i - v_i) + \beta \cdot -log \;\pi_\theta(a \mid state_i)R_i\)
• 왜 actor-critic일까?
  • 이 Critic은 action value function을 통해 현재의 Policy를 평가하는 역할을 한다. action을 해보고 그 action의 action value function이 높았으면 그 action을 할 확률을 높이도록 policy의 parameter를 update하는데 그 판단척도가 되는 action value function또한 처음에는 잘 모르기 때문에 학습을 해줘야하고 그래서 critic이 필요하다.

구동 방식

• KT 모델을 통해 각 단계별로 이전 학습 기록을 통해 현재 지식 수준 S를 찾는다
• CN을 통해 선수지식 그래프 기반으로 몇몇 후보를 고른다.
• ACR을 통해 모든 학습 경로 중 가장 좋은 경로를 택하는 후보를 선택한다.
• 한 learning session이 끝나면 episode reward를 통해 모델을 업데이트한다.

5. Experiments

데이터 셋

• 학습자id, 개념이름, 세션id, 정오, 타임스템프로 이뤄진 여러 학습자 log와 하나의 지식그래프
• 지식그래프에서 선수지식 그래프를 추출하고 이를 DAG로 표현
• 하나의 세션에서 한 개념을 반복적으로 학습하거나 관련된 개념이 동시에 학습될 수도 있다.

System simulators

• 현실의 데이터는 고정적이다. 다시 말해 실제 학습자가 모델이 추천한 학습 경로를 통해 학습된 데이터는 추가될 수 없기 때문에 새로 학습할 개념에 대해 어떤 대답을 할 지 알 수 없다. 그래서 현재 가진 데이터로 지적 성장을 이뤘는지 확인할 시뮬레이터 환경이 필요하다.
• Knowledge Structure based Simulator(KSS)
  • 질적인 지식 성장 패턴이 지식 구조에 완벽하게 맞는 시뮬레이터
  • 선수지식의 이해도가 새로 배울 지식에 얼마나 영향을 끼치는가?
  • 문항반응이론(IRT)의 $P(\theta)$을 각 $p_i$에 대한 $score_i$의 계산과 reward 계산에 이용한다.
  • 이때 관련 파라미터나 학습자의 능력은 전문가가 제시하는 것이므로 KSS는 rule-based expert 시스템이다.
  • 현실과 잘 맞지 않을 수 있다.
• Knowledge Evolution based Simulator(KES)
  • 학습자의 지식 수준이나 성장을 잘 표현하기 위한 data-driven 시스템
  • DKT모델을 이용해 현재 지식 수준을 기반으로 다음 문항을 맞출 확률을 구해 이를 $p_i$에 대한 $score_i$의 계산과 reward 계산에 이용한다.
  • 지식 구조의 연관성을 표현하는데 문제가 있다.
• 결국 두 시뮬레이터는 상호보완적인 관계이다.

evaluation metrics

• 학습 경로 추천은 학습 효과에 대해 다루기 때문에 기존의 대표적인 추천 시스템과는 다른 결을 가지고 있다. 그렇기 때문에 기존의 metric인 precision이나 recall등을 사용할 수 없다.
• 그래서 시뮬레이터에서 나온 학습 효과 지표 $E_P$와 전문가에 의한 학습 경로 논리성 판단을 합쳐서 평가해야 한다.

experimental results

• baseline 모델보다 좋은 성능을 얻을 수 있다.
• KSS환경에서 지식 구조를 이용한 모델이 그렇지 않은 모델보다 좋은 성능을 내고 있다.
• KES환경에서 지식 수준과 구조를 이용한 모델이 나은 성능을 보이는 것을 보아 지식 수준과 지식 구조를 종합적으로 사용한 인지 구조 활용이 필요해보인다.
• 추천 학습 경로에 대한 여러 전문가의 평점을 보았을때 CSEAL이 높은 점수를 받았다. 또한 CN을 이용한 모델이 높은 점수를 받은 것을 알 수 있다.
• session의 길이 또한 영향을 끼치는데, KES는 모든 세션 길이의 중앙값 정도를 가지는 것이 좋고, KSS는 rule에 의해 만들어져 길이의 한계를 정하지 않았기 때문에 길면 길 수록 성능이 향상한다.
• CSEAL이 다른 모델에 비해 효과적인 학습 경로를 제시한다.

$E_P$ 지표

전문가 평점

CN의 유무에 따른 expected return의 차이

세션 길이에 따른 성능 지표

모델 별 학습 목표에 대한 추천 경로 예시

리뷰

학습 경로를 추천하는 논문을 처음 읽어봤다. 교사에게 있어 학생의 선수지식을 파악하고 이를 바탕으로 학습법을 제시하는 것은 중요한 일이다. 아무리 그 개념을 가르쳐봤자 선수 개념이 없으면 그 학생은 평생 이해하지 못 할 것이다. 이런 교수 학습법을 세 가지 모듈을 통해 구현했다는 점이 재밌었다. 계속 KT모델로 학생 수준 측정만 다루다가 처음 추천 시스템이 결합되니 굉장히 이해하기 어려웠지만, 교육 ai에 대한 안목을 넓힐 수 있는 좋은 기회였다.