Han et al.: 学ぶ順番が効く場面と効かない場面を、計算量で切り分ける — Fukai が読む

一段落要約

「学ぶ順番は大事だ」とは誰もが言う。パズルゲームのチュートリアルの並び、スキルツリーの解放順、ステージの配置。だが「どれくらい大事なのか」を先に測る方法を、私たちはほとんど持っていない。カリフォルニア大学デービス校の Han らによる新しい preprint は、前提条件でつながった概念群を学ぶ順序の最適化を計算問題として真正面から扱い、三つの答えを出した。ひとつ、学習が失敗してやり直しになるという確率的な厄介さは、コストを成功確率で割るだけで完全に消せる。ふたつ、それでも最適な順序を求めるのは NP 困難である。みっつ、最適化に取りかかる前に「順番をいじって得られる利得の上限」を安く計算できる。

三つめが実務的にいちばん効く。著者らはこの診断量を大学の入門プログラミング科目の実データ、294人・70,893件のやり取りに当て、順序最適化で改善できる余地が期待コストの 0.2% 未満しかないことを確かめた。実際、シラバス通りに一直線に並べただけの順序ですら、最適解とのずれは 0.034% にとどまった。この科目に関しては「順番を最適化しても意味がない」ことが、最適化する前に分かる。

逆の構造を持つカリキュラムも実在する。公開データの Junyi Academy では、探索空間が1000万状態を超える目標が 68 個あった。そして著者らが人工的に組んだ「兄弟転移の罠」では、目先の成功率だけを見て選ぶ貪欲な順序が 28.3% から 45.1% の損をする。順番が効く盤面と効かない盤面があり、それは事前に見分けられる——これが本稿の芯だ。なお本稿は arXiv:2608.05455、2026年8月5日投稿の preprint(査読前原稿)であり、まだ広く議論されていない段階である。

はじめに

著者は Zonglin Han、Yichen Chen、Jiawen Jiang、Tongan Shi、Kristian A. Stevens の5名。Han、Chen、Stevens はカリフォルニア大学デービス校コンピュータサイエンス学科、Jiang は閩江学院(Minjiang University)の International Digital Economy College、Shi は遼寧師範大学のコンピュータサイエンス・人工知能学院に所属する。arXiv:2608.05455、分類は cs.AI および cs.DS、投稿日は 2026年8月5日、本文11ページに図1点・表1点。査読を通った論文ではなく preprint であり、現時点で広く議論されている段階ではない。

私がこの論文を今日選んだ理由を書いておく。パズルを作っていると、レベルの並び順に異様な時間を使う。第3面と第5面を入れ替えるべきか、このギミックの導入は雪だるま式の複合面より前か後か。そして多くの場合、その議論に決着はつかない。決着がつかないのは、判断材料がないからだ。この論文は答えそのものではなく、「その議論に投資する価値があるかどうか」の見積もりを先に出してくる。私はそこが好ましいと思った。

もうひとつ。論文が対象にしているのは教育のカリキュラムだが、使われている語彙——前提条件のある有向非巡回グラフ、習得済み概念の集合、いま挑戦できる手の集合——は、そのままスキルツリーやステージ進行の語彙である。ゲームデザインに翻訳しやすい形をしている。著者らはこの計画問題に「Ariadne(アリアドネ)」という名前を付けている。迷宮に糸を垂らした、あの神話の名前だ。

背景

まず前提を整理する。教育工学の分野では、学習者に何をどの順で提示するかを決める問題を「教育系列化(instructional sequencing、学習内容の並べ方を決める問題)」と呼ぶ。既存研究の多くは「どう並べるか」を作る側に立ってきた。多腕バンディット(multi-armed bandits、複数の選択肢を試しながら当たりを見つけていく枠組み)、強化学習(試行錯誤しながら報酬が高くなる行動を学ぶ枠組み)、部分観測マルコフ決定過程(POMDP、学習者の内部状態が直接は見えない状況での逐次的な計画)、前提条件を織り込んだマルコフ決定過程、そして最近は大規模言語モデル。

だが著者らは、その手前に四つの問いが残っていると指摘する。学習の確率的な振る舞いは、本当に確率的な計画を必要とするのか。学習者の状態に依存することが、順序に価値を生むのはどんなときか。どんな「転移(transfer、ある概念を学んだことが別の概念の学びやすさに影響すること)」の構造が順序の衝突を生むのか。そして厳密な探索の難しさは何が決めるのか。本稿は四つとも答える、と冒頭で宣言している。

状態空間そのものには前史がある。数理心理学の知識空間理論(knowledge space theory)は、学習者を「習得済みの項目の部分集合」として表す。前提条件の半順序が入ると、状態は「オーダーイデアル(order ideal、ある要素を含むならその前提条件もすべて含んでいる集合)」の格子になる。著者らは、自分たちの貢献は状態空間の発明ではなく、その上での計画問題——期待コストを最小にする順序を求める問題——の性質を明らかにしたことだ、と自ら位置づけている。

アプローチ

モデルは驚くほど簡素だ。カリキュラムは前提条件の有向非巡回グラフ。学習者の状態は習得済み概念の集合で、前提条件について閉じている。ある状態でいま挑戦できる手は、まだ習得しておらず、かつ前提条件がすべて満たされている概念に限られる。著者らはこれを、ヴィゴツキーの「発達の最近接領域(zone of proximal development、独力ではまだ届かないが支援があれば届く範囲)」のグラフ論的な読み替えだと書いている。1回の挑戦には固定のコストがかかり、ある確率で成功する。失敗しても状態は変わらない。

ここから第一の結果が出る。「失敗しても状態が変わらない」かつ「成功確率が時間によらない」なら、確率は完全に消せる。成功するまで繰り返すときの期待試行回数は成功確率の逆数なので、1回あたりのコストをその成功確率で割った値を、その手の確定的なコストとして置き直せばよい。著者らによれば、元の確率的な問題と、置き直した確定的な最短経路問題は、最適値も最適な手の集合も完全に一致する。実装上の含意もある。ループを含む解を扱うための重い探索機構(LAO* など)は、この問題では出番がなくなる。

第二に、著者らは順序をいじる価値の上限を測る道具を用意する。ひとつの概念について、それが「挑戦可能になっている状態」を全部見渡したとき、置き直したコストの最大値と最小値の差を取る。この差を全概念について足し上げると、どんな正しい順序どうしを比べても、総コストの差はその和を超えない。しかも成功確率が単調(習得済みが増えるほど下がらない)なら、この差は概念ごとにたった2回の問い合わせで正確に求まる。状態格子を1つも展開せずに、順序最適化の伸びしろの上限が手に入るということだ。

第三に、実際に最適解を求めるときは A*(エースター。ゴールまでの残りコストの見積もりを使って、有望な方向から順に探す探索アルゴリズム)を使う。見積もりは「残っている各概念について、最も条件が良いときのコスト」を足し合わせたもの。この見積もりは決して真のコストを上回らないため、A* が返す答えは厳密に最適になる。状態格子は明示的に構築せず、必要になった状態だけをその都度生成する。

発見

計算量の地図が本論文の骨格だ。確率を消した後の順序決定問題は NP 完全である。しかも著者らによれば、前提条件の辺が1本もなく、挑戦コストが全部同じで、転移の強さが0か1しかなく、成功確率が状態について単調で、かつすべて 1/2 以上、という厳しい制限下でも NP 困難のままだという。帰着元はトーナメントにおける最小フィードバック弧集合(総当たり戦の勝敗表を、逆転がなるべく少なくなるように一列に並べる問題)。難しさは前提条件を守ること自体からではなく、状態に依存する転移が生む「順序の衝突」から来ている、と論文は結論している。

ただし難しさは一様ではない。転移の好み(u を先にやると v が楽になる)と前提条件をひとつのグラフにまとめたとき、そのグラフに循環がなければ、トポロジカル順序(矢印の向きに逆らわない並べ方)ならどれでも最適で、線形時間で構成できる。前提条件の半順序の「幅」——同時に並行して進められる系統の最大本数——が固定されていれば、厳密な動的計画法が多項式時間で回る。転移の効きかたが一次式で書ける場合は、循環を壊すのに削るべき辺の数を固定パラメータとした FPT アルゴリズム(そのパラメータが小さければ実用時間で解ける種類のアルゴリズム)が存在する。

実験に移る。カリフォルニア大学デービス校の入門コンピュータサイエンス科目 ECS32A から、294人・70,893件のやり取りを 61 概念の前提条件グラフに対応づけ、10個の目標について評価した。診断量は「順序最適化で改善できる余地は期待コストの 0.2% 未満」と告げる。表1では、最も悪い条件——シラバス通りに一直線に並べた順序——ですら正規化リグレット(最適解からのずれの割合)が 3.385×10⁻⁴、つまり 0.034% にとどまった。ランダムに挑戦可能な手を選ぶ条件でも 2.633×10⁻⁴ である。著者らはこれを、順序の価値も探索空間もどちらも小さい「二重に易しい領域」と呼んでいる。

対照的なカリキュラムも示される。公開データの Junyi Academy は 835 の演習からなり、終端目標の閉包の幅は中央値8・最大18、到達可能な状態数の中央値は 96,608、そして 68 個の目標が1000万状態という列挙の上限を超えた。さらに著者らが組んだ「兄弟転移の罠」——単体では成功しやすく見える兄弟概念が並び、正しい順に通すと転移が連鎖する構造——では、貪欲な順序のリグレットが 28.3% から 45.1% に達した。そしてこの族では、動的計画法の展開状態数が幅に対して指数的に増えるのに対し、A* は幅に比例する程度しか展開しない。順番が本当に効く盤面では、探索も効く。

使いどころ

ひとつめ。倉庫番系のレベル並べ替えに使う。ギミックごとに前提条件グラフを描き、各ギミックについて「先行ギミックを既に理解している人の初回クリア率」と「理解していない人の初回クリア率」をプレイデータから出す。この2つの比が、論文でいう概念ごとの振れ幅にあたる。論文は乗法的な上界も示していて、どんな順序でも最適解に対する比は「この比の最大値」を超えない。もし全ギミックでこの比が1に近ければ、並べ替えの議論は打ち切ってよい。私なら、この比を出すダッシュボードを、並べ替えツールより先に作る。

ふたつめ。ハイパーカジュアルの自動レベル生成に使う。生成器が「次に出すレベル」を選ぶとき、目先のクリア率だけを見る貪欲な選択は、兄弟転移の罠とまったく同じ構造で損をしうる。論文の罠は、単体では簡単に見える兄弟を先に出すと、後続に効く転移を取り逃がす形だった。対策は難しくない。転移の効きかたが一次式で近似できるなら、循環を壊すのに削るべき辺の数だけを見て厳密解が回せる。回らないほど絡んでいるなら、それは設計を絡ませすぎている合図とも読める。

みっつめ。チュートリアルの分岐設計に使う。前提条件の「幅」が探索コストを支配する、というのは設計にそのまま効く数字だ。論文のデータでは、幅が4なら到達可能な状態は最大47個で、全列挙が一瞬で終わる。幅が18になると状態数は1000万を超える。プレイヤーに自由な進行順を与えたいという欲求と、その進行が最適か検証したいという欲求は、幅というひとつの数字の上でトレードオフになっている。幅を設計上の予算として明示的に持つ価値はあると読める。

よっつめ。デイリーパズルの1セッション内の並びに使う。この枠組みは「一度習得したら忘れない」を仮定しており、日をまたぐデイリーの文脈では成り立たない。だが逆に言えば、忘却が効かない範囲——1セッション内のステージ列、あるいはひとつのチュートリアル週——には素直に適用できる。前提条件グラフとひとつの診断量だけで点検し、効かないと分かればその時間を別のことに使う。順序を最適化しないという結論を、根拠つきで出せることに価値がある。

限界

著者自身が認めている限界から。最大のものは評価の閉ループ性である。ECS32A の実験では、計画に使う学習者モデルと、成績を測る評価器が同一である。だから「Ariadne の厳密解のリグレットがゼロ」というのは実験結果ではなく、実験設計上の同一性にすぎない、と著者らは明記している。しかもこのモデルは、保留したセッションに対する予測性能が全特徴で AUC 0.775、履歴を取り除くと 0.611 と、中程度の当たり方でしかない。結論は「このモデルが作り出す計画の風景」についてのものであって、実在の学習者についてのものではない、と著者らは繰り返している。

続く。Junyi Academy の分析は「トポロジーの証拠」であって計画器の評価ではない。第一試行に基づく代理指標(中央値 5.6%、最大 12.5%)は、前提条件を既に習得している学生が系統的に優秀である可能性を排除できず、状態依存を過大に見せうる。著者らはこれを「認定された上界ではなく探索的な診断」と呼んでいる。また、確率を消せるという結果は、失敗が信念を更新する場合、コストが試行履歴に依存する場合、忘却がある場合、結果が3通り以上ある場合、目的関数がリスク回避的な場合には成り立たない。さらに、厳密最適化が裏目に出る現象も報告されている。BKT や DKT を使った条件では、そのモデル自身の目的の下では厳密解が貪欲解に勝つのに、共通の評価器で測ると負けた。モデル誤差を厳密最適化が増幅した、というのが著者らの読みだ。

Fukai がここで指摘するのは、別の二点である。ひとつ、診断量は「並べ替えの利得」の上界であって下界ではない。0.2% という数字は「これ以上は得できない」という意味であり、順序の設計が無意味だという意味ではない。モデルが目的関数に入れていない要素——飽きる、驚く、諦める——は、そもそも測られていない。ふたつ、目的関数が「期待総コストの最小化」であることそのものが、ゲームには合わない。学習コストを下げきったチュートリアルは、たいてい退屈だ。この論文は最短の経路を扱っており、良い経路を扱ってはいない。教育の文脈ではその二つは近いが、遊びの文脈では必ずしも近くない。

Fukai の読み

私はこの研究を、「設計論争に予算をつける」という系譜の中に位置づけたい——ここだけは私の解釈である。設計の現場では、順序・難度・導入タイミングをめぐる議論が、決着しないまま時間だけを消費することが多い。この論文が出しているのは順序の答えではなく、「その議論にどれだけ投資する価値があるか」の見積もりで、しかもその見積もりは最適化に着手する前に、概念あたり2回の問い合わせで出る。設計批評の語彙で言えば、これは「検討に値するかどうかの検討」を自動化したものに近い。もう一点、学習者モデルの精度が中程度のとき厳密最適化がかえって成績を落とした、という観察も引っかかった。著者らは論文を「計画は梃子であり、学習者モデルはその支点である」と締めている。支点が緩んでいるなら、梃子は長くしないほうがいい。プレイヤーモデルの当たりが怪しいまま、レベル選択の最適化だけを精緻にしている実装には、私も心当たりがある。

おわりに

もっと深く知りたい人向けに、周辺の地図を置いておく。まず、ほぼ同時期に公開された Pasechnyuk-Vilensky の「Order-sensitive sequential interventions on ideal lattices」(arXiv:2604.26472)は、同じイデアル格子の上で順序感応性を局所的な指標から特徴づけている。本稿の著者らによれば、その局所的な指標と本稿の大域的な指標は、どちらも他方を一様に支配しない。二本を並べて読むと、「順序が効かない」という性質に少なくとも二通りの測り方があることが見えてくる。

背景の系譜を押さえたいなら、知識トレーシング(knowledge tracing、学習者がどの概念を習得済みかを推定する技術)の流れ——Corbett と Anderson のベイズ知識トレーシング(1995)から Piech らの Deep Knowledge Tracing(2015)まで——を眺めておくと、この論文が「学習者モデルそのものには手を出さない」と繰り返す意味が分かる。ゲーム側からの接続なら、Narvekar らによる強化学習向けカリキュラム学習のサーベイ(2020)が、同じ問題を別の語彙で扱っている。順序の問題は、教育と機械学習とゲームデザインの三方から同じ形をして現れている。

参考文献

本記事で参照した論文と関連資料:

・Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs (Zonglin Han, Yichen Chen, Jiawen Jiang, Tongan Shi, Kristian A. Stevens, 2026, arXiv preprint)

・DOI: 10.48550/arXiv.2608.05455

・関連研究: Order-sensitive sequential interventions on ideal lattices (Pasechnyuk-Vilensky, 2026, arXiv preprint)

・関連研究: Deep Knowledge Tracing (Piech et al., 2015, NeurIPS)

・関連研究: Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey (Narvekar et al., 2020, JMLR)