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

あなたは、遠く離れた惑星に到達するために、小惑星が入り組んだ迷路を航行しようとしている宇宙船のキャプテンだと想像してください。コンピュータサイエンスの世界では、これは「インストラクショナル・シーケンシング（教授順序決定）」に似ています。これは、AIや教師が、新しい概念を学生に教えるための最適な順番を導き出そうとするプロセスです。この迷路にはルールがあります。例えば、「基本的な物理学」を習得するまでは、「ロケットエンジン」について学ぶことはできません。これを「前提条件の依存関係（prerequisite dependency）」と呼びます。

通常、私たちはこの航行において最も困難な部分は「不確実性」であると考えがちです。学生はそのレッスンを理解できるでしょうか？失敗して、やり直す必要があるでしょうか？学習は確率的（ストカスティック）であるため、未来を予測し、あらゆる「もしも」に対して計画を立てるために、高速で複雑なコンピュータが必要だと私たちは想定しがちです。しかし、もし本当の難しさは、予測ゲームにあるのではないとしたらどうでしょう？たとえ学生の反応が完全に分かったとしても、迷路の中を通るルートの数が膨大であること自体が、真の難しさだとしたら？この論文は、その問いを掘り下げています。「学習のランダム性が真の悪役なのか、それともマップ自体の純粋な複雑さが悪役なのか？」という問いです。

この論文の著者であるコンピュータサイエンティストのチームは、学生が一定の概念を学習する様子を数学的なモデルにすることで、この問題に取り組むことにしました。彼らは学習プロセスを、出発点（何も知らない状態）からゴール（すべてを知っている状態）まで、最小限の労力で移動しようとするゲームとして扱いました。彼らのモデルでは、学生が新しい概念を学ぼうとするたびに、成功する確率と失敗する確率が存在します。もし失敗しても、彼らは元の状態のままです。すでに知っていることを失うわけではなく、ただもう一度挑戦しなければならないだけなのです。

ここで、チームが発見した大きな驚きがあります。ランダム性は、実は難しい部分ではなかったのです。 彼らは、不確実性をすべて取り除くことができることを数学的に証明しました。この予測不可能な「成功するかしないか」の学習ゲームを、完全に決定論的なマップへと変えることができるのです。これは、コイン投げがランダムであっても、もし確率を知っていれば、「表が出るまでコインを投げ続ける平均的なコスト」を計算でき、その平均コストを固定価格として扱えるようになることに似ています。一度これを行えば、問題は「予測」することから、巨大で硬固なグリッド上での「最短経路を見つける」ことへと変わります。

しかし、ランダム性がなくなったからといって、問題が簡単になったわけではありません。実際、著者たちは、ランダム性を排除した後でも、これらの概念を教える「完璧な順番」を見つけ出すことは、コンピュータにとって極めて困難であることを発見しました。彼らは、この困難さが、概念同士がどのように「転移」するかという点に起因することを明らかにしました。あることを学ぶことが別のことを容易にする一方で、もしそれらの助けとなる接続関係が複雑に絡み合った網のようになっていると、コンピュータは最適なルートを見つけることができず、行き詰まってしまいます。彼らはこれを「組合せ爆発的な複雑さ（combinatorial complexity）」と呼んでいます。コンピュータが混乱しているのは、学生の気分によるのではなく、可能な学習経路のマップがあまりにも巨大すぎるからなのです。

とはいえ、悪いニュースばかりではありません。論文はまた、多くの現実世界の状況において、マップは実際にはそれほど複雑に絡み合っていないことも明らかにしました。彼らは、コースを見る前に、そのレッスンの順番が実際に重要かどうかを判断できるシンプルな「診断ツール（一種の数学的なテスト）」を開発しました。もしそのツールが、マップが「非循環的（acyclic）」（混乱を招くループがない状態）であると示せば、どのような論理的な順番を選んでも上手くいきます。その場合、完璧なものを見つけるためにスーパーコンピュータを用意する必要はありません。

これを検証するため、研究者たちは7万人以上の学生の相互作用を含む、導入レベルのコンピュータサイエンスコースの実際のデータを用いました。彼らの診断ツールは、この特定のクラスにおいては、「完璧な順番」はそれほど重要ではないことを確認しました。そのコースは、彼らが「二重に容易な領域（doubly easy regime）」と呼ぶ状態にありました。つまり、学生はほぼどのような順番でも学習可能であり、順番を少し間違えたとしても、そのコストは極めて小さいということでした。しかし、彼らは同時に、依存関係が非常に厄介な人工的な例も作成しました。その場合、順番を間違えると大きな後悔（時間の浪費や努力の無駄）が生じることを示し、多くの実際の授業はナビゲートしやすいものの、難しいケースも確かに存在するのだと証明しました。

さらにチームは、マップが難しい場合でも、すべての経路をチェックする必要はないことも示しました。彼らは「A*（エースター）探索」と呼ばれるスマートな探索手法（目的地を知っており、最も有望な道だけをチェックするGPSのようなもの）を使用しました。最もトリッキーで複雑な例においてさえ、このスマートなGPSは、勝者を決定するために、可能な経路のごくわずかな割合を確認するだけで済みました。

では、結論は何でしょうか？もしあなたが子供たちに教えるためのアプリを作っているなら、学生が予測不可能であることにパニックになる必要はありません。あなたは数学的に問題を単純化し、「予測」の部分を取り除くことができます。真の課題は、あなたのカリキュラムが、複雑に絡み合った構造を持っているかどうかを確認することです。もしそうであれば、スマートな探索ツールを使って最適な経路を見つけてください。もしそうでなければ（多くの現実世界の授業のように）、順番が大きな違いを生むことはないはずなので、リラックスして大丈夫です。この論文は、「学習の魔法」とは未来を予測することではなく、マップの形を理解することにあるのだと証明しています。