Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs

당신이 먼 행성에 도달하기 위해 소행성 미로를 항해하는 우주선의 선장이라고 상상해 보십시오. 컴퓨터 과학의 세계에서 이것은 AI나 교사가 학생에게 새로운 개념을 가르치는 최적의 순서를 찾아내려는 '교수 순서화(instructional sequencing)'와 유사합니다. 이 미로에는 규칙이 있습니다. 예를 들어, '기초 물리학'을 마스터하기 전에는 '로켓 엔진'에 대해 배울 수 없습니다. 이것을 '선행 학습 의존성(prerequisite dependency)'이라고 부릅니다.

보통 우리는 이 항해에서 가장 어려운 부분이 불확실성이라고 생각합니다. 학생이 수업을 이해할 것인가? 학생이 실패하여 다시 시도해야 할 것인가? 우리는 학습이 예측 불가능(stochastic)하기 때문에, 미래를 예측하고 발생 가능한 모든 '만약의 상황'에 대비해 계획을 세우는 고속 컴퓨터가 필요하다고 가정하곤 합니다. 하지만 정말 어려운 부분이 바로 그 예측 게임이 아닐 수도 있습니다. 만약 우리가 학생의 반응을 정확히 알 수 있다 하더라도, 미로를 통과할 수 있는 가능한 경로의 수가 너무 많다면 어떨까요? 이 논문은 바로 이 질문을 파고듭니다. 학습의 무작위성이 진짜 악당일까요, 아니면 지도 자체의 엄청난 복잡성이 진짜 악당일까요?

이 논문의 저자들인 컴퓨터 과학자 팀은 학생이 일련의 개념을 학습하는 과정을 수학적 모델로 구축하여 이 문제를 해결하기로 했습니다. 그들은 학습 과정을 시작점(아무것도 모르는 상태)에서 도착점(모든 것을 아는 상태)까지 최소한의 노력으로 이동하는 게임처럼 다루었습니다. 이 모델에서 학생이 새로운 개념을 배우려고 시도할 때마다 성공할 확률과 실패할 확률이 존재합니다. 만약 실패한다면, 학생은 이미 알고 있는 것을 잃지는 않지만, 정확히 제자리에 머물러서 다시 시도해야 합니다.

여기서 연구팀이 발견한 놀라운 사실이 있습니다. 무작면성은 핵심적인 문제가 아니었습니다. 그들은 수학적으로 모든 불확실성을 제거할 수 있다는 것을 증명했습니다. 당신은 이 예측 불가능한, '성공할까 실패할까'를 고민하는 학습 게임을 완전히 예측 가능한 결정론적 지도로 바꿀 수 있습니다. 이는 마치 동전 던지기가 무작위적이라 할지라도, 만약 당신이 확률을 알고 있다면 동전이 앞면이 나올 때까지 던지는 데 드는 '평균 비용'을 계산할 수 있고, 그 평균 비용을 하나의 고정된 가격표처럼 취급할 수 있는 것과 같습니다. 일단 이렇게 하면, 문제는 더 이상 '추측'에 관한 것이 아니라 거대하고 단단한 격자 위에서 최단 경로를 찾는 문제가 됩니다.

하지만 무작위성이 사라졌다고 해서 문제가 쉬워지는 것은 아닙니다. 실제로 저자들은 무작위성을 제거하더라도, 이러한 개념들을 가르치는 '완벽한 순서'를 찾는 것은 최악의 시나리오에서 컴퓨터가 해결하기에 여전히 매우 어렵다는 것을 발견했습니다. 그들은 이러한 어려움이 개념들이 서로 '전이(transfer)'되는 방식에서 온다는 것을 보여주었습니다. 즉, 하나를 배우는 것이 다른 것을 배우기 쉽게 만들 수 있지만, 만약 이러한 유익한 연결들이 뒤엉킨 그물처럼 형성된다면 컴퓨터는 최적의 경로를 찾다가 길을 잃게 됩니다. 이것을 그들은 '조합 복잡성(combinatorial complexity)'이라고 부릅니다. 컴퓨터가 학생의 기분을 몰라 혼란스러워하는 것이 아니라, 가능한 학습 경로의 지도가 너무 방대해서 모든 경로를 다 확인할 수 없는 것입니다.

하지만 걱정할 필요는 없습니다. 좋은 소식도 있습니다. 논문은 많은 현실 세계의 상황에서 지도가 실제로는 그렇게 엉켜 있지 않다는 것을 발견했습니다. 연구진은 어떤 과정(course)을 보고 계획을 세우기 전에, 수업의 순서가 실제로 중요한지를 알려주는 간단한 '진단 도구(일종의 수학적 테스트)'를 개발했습니다. 만약 이 도구가 지도가 '비순환적(acyclic, 순환 구조가 없는)'이라고 말한다면, 당신이 어떤 논리적인 순서를 선택하더라도 괜찮으며, 완벽한 것을 찾기 위해 슈퍼컴퓨터를 사용할 필요도 없습니다.

이를 테스트하기 위해 연구진은 7만 명 이상의 학생 상호작용 데이터가 포함된 실제 컴퓨터 과학 입문 과목의 데이터를 살펴보았습니다. 그들의 진단 도구는 이 특정 수업의 경우 '이중로 쉬운 영역(doubly easy regime)'에 있다고 확인해주었습니다. 즉, 학생들은 거의 어떤 순서로든 배울 수 있었으며, 순서를 약간 잘못 선택하더라도 발생하는 비용은 아주 미미했습니다. 그러나 연구진은 의존 관계가 복잡하게 얽힌 인위적이고 까다로운 예시들도 만들었습니다. 그런 경우, 잘못된 순서를 선택하면 엄청난 후회(시간과 노력의 낭비)를 초래한다는 것을 보여줌으로써, 비록 많은 실제 수업은 항해하기 쉽지만, 어려운 수업도 존재한다는 것을 증명했습니다.

또한 연구팀은 지도가 복잡할 때, 모든 경로를 다 확인할 필요는 없다는 것을 보여주었습니다. 그들은 A*라고 불리는 스마트한 탐색 방법(목적지를 알고 있으며 가장 유망한 길만을 체크하는 GPS와 같은 방식)을 사용했습니다. 가장 까다롭고 복잡한 예시에서도, 이 스마트한 GPS는 승자를 찾기 위해 가능한 경로 중 아주 작은 부분만을 살펴봐야 했습니다.

그렇다면 결론은 무엇일까요? 만약 당신이 아이들을 가르치는 앱을 만들고 있다면, 학생들이 예측 불가능하다는 사실 때문에 공포에 질릴 필요는 없습니다. 당신은 수학적으로 문제를 단순화하여 '추측'하는 부분을 제거할 수 있습니다. 진짜 과제는 당신의 커리큘럼이 엉망으로 뒤엉킨 구조를 가지고 있는지 확인하는 것입니다. 만약 그렇다면, 스마트한 탐색 도구를 사용하여 최적의 경로를 찾으십시오. 만약 그렇지 않다면(많은 실제 수업처럼), 수업의 순서가 큰 차이를 만들지 않을 것이므로 안심해도 좋습니다. 이 논문은 학습의 '마법'이 미래를 예측하는 데 있는 것이 아니라, 지도의 형태를 이해하는 데 있다는 것을 증명합니다.