技術要約: KnowPlan

問題提起

学位履修計画の策定は、学生が履修要件、単位制限、および開講時期を満たすように科目を順序立てる必要がある、制約駆動型の意思決定問題である。先行研究では、コース推薦やカリキュラム最適化が扱われてきたが、これらは概して、十分な完成度を持つカリキュラム表現が既に利用可能であることを前提としている。

公開されている大学の情報源からこのような表現を構築することは、本質的に困難である。機関のカリキュラムは、多様な形式（ウェブページ、JSONエンドポイント、PDF）に分散しており、共通のスキーマを持たず、入れ子状の論理節、要件の重複、およびポリシーの例外を含んでいる。既存の文献における重要な未解決の課題は、「獲得と計画の循環性（acquisition–planning circularity）」である。もしパーソナライズされたプランナーが情報源の獲得を制御しているならば、現在の学生の目的によって、どのページが開かれるかが決定されてしまう。その結果、得られる不完全なグラフが「実現可能と思われる計画」を決定し、その同じ不完全なグラフが計画の妥当性検証にも使用される。ルールが見落とされている場合、それは単に取得されなかったために、存在しないものとして扱われるのである。

手法

著者らは、カリキュラムの再構築とパーソナライズされた学位計画を分離することで、この循環性を打破する抽出優先型フレームワークである KnowPlan を提案する。本システムは、以下の2つの明確なステージで動作する。

1. CatalogBrowse: プロファイルに依存しない抽出

CatalogBrowseは、学生のプロファイルにアクセスすることなくカリキュラムデータを取得するために設計された、ウェブ探索エージェントである。

• 状態と観測可能性: エージェントは動的なページグラフと、未開封のリンクのフロンティアを保持する。決定的なことに、ページ内容はアクションが事前にコミットされ、対価が支払われた後にのみ開示されるため、エージェントは内容を事前に検査してアクセスするかどうかを判断することはできない。
• 原子的な義務 (Atomic Obligations): 「容易な成功」を促す重み付きの完了信号に頼るのではなく、エージェントは、インデックス・エントリの発見、エンティティのインスタンス化、必須フィールドの充填、および参照の解決といった、有限の原子的な義務 ($O$) をターゲットとする。
• ポリシー: エージェントは、ソースへのアクセス単位あたりの期待される限界義務利得に対する下限信頼区間（LCB）を用いてアクションを選択する。この保守的なポリシーは、既に検証された証拠を優先し、未知のアクションは、その義務自体が正の期待利得を生み出す場合にのみ追求されることを保証する。
• パースとフォールバック: システムは、API、DOM、およびPDFのための決定論的なプラットフォーム・アダプターを使用する。複雑な論理節については、スパン制約付きの「節からASTへの変換モデル」を採用する。このモデルは、可視スパン内に文字通り存在するトークンに限定され、任意のURLや識別子を出力することはできない。出力は、受理前にページ内のテキスト内で再特定される。
• 終了条件: エージェントは、閉鎖証明書 (closure certificate) が成立したときにのみ停止する。この証明書は、発見されたすべてのインデックス・エントリがエンティティに紐付けられているか、あるいは明示的に失敗したと記録されているか、すべてのスキーマ必須フィールドが紐付けられているか、あるいは明示的に未解決であるか、そしてすべてのプロベナンス・オフセットが、エージェントが開いたページ内の範囲内に存在することを検証する。この証明書は証拠を特定するものであり、事実そのものを裁定するものではない。それはスナップショット相対的であり、ライブなWebについて主張を行わない。
• 出力: このステージは、プロベナンス（由来）と紐付けられた3つのJSONドキュメント（コース/履修要件、プログラム要件、および一般教育フレームワーク）を正確に出力する。

2. DegreeMap: パーソナライズされた計画

DegreeMapは、CatalogBrowseによって生成された3つのJSONドキュメントと、学生固有のリクエストのみを消費する。

• 型付き要件ハイパーグラフ: コンパイラは、JSONドキュメントを型付き要件ハイパーグラフへとマッピングする。これは、複雑な論理構造（例：CHOOSE_N, ALL_OF）をペアワイズの節へと展開せず、ハイパーエッジとして保持することで、「9つの中から3つを選択する」といった制約の厳密な強制を実現する。
• パーソナライズされた効用: システムは、以下の要素に基づき、各コースのスコア $S(c)$ を算出する：
  • 直接的な意味的関心 ($I_0$)。
  • 型付きグラフ拡散 ($I_D$): 充足およびクロスリスティングのエッジを通じて関心を伝播させるが、履修要件（prerequisite）のエッジを通じては伝播させない。
  • 履修要件のアンロック価値 ($U$): 依存関係のパスに沿って、後ろ向きに（backward）関心を伝播させる。
  • メジャー/一般教育の利得、将来の選択肢の価値、ワークロード、リスク、および嫌悪度。
• レキシコグラフィック CP-SAT 最適化: プランナーは、以下のレキシコグラフィック順序に従って、ランク付けされた一連の計画を解く：
  1. 硬い実現可能性（すべての制約を満たすこと）。
  2. 最小の完了期間。
  3. ワークロードとスケジューリングのリスク。
  4. パーソナライズされた効用。
  5. 将来の選択肢の価値。
     各ステージは、前のステージで証明された最適解を硬い制約として固定し、固定されたソルバー予算内での証明可能性を維持する。
• 明確化: 残っている選好仮説の間で最適な計画が変動する場合、システムは後悔（regret）を最小化するための的を絞った質問を行う。

主な貢献

1. 定式化: 本論文は、学位計画の策定を、公開情報からの「獲得と最適化」の二段階問題として定式化し、獲得と計画の循環性を直接測定可能なものにした。
2. CatalogBrowse: 義務駆動型の探索、プロベナンスに紐付けられた抽出、および、発見されたすべてのエントリが処理されたか、あるいは明示的に失敗したことを検証することで、凍結されたスナップショットに対する出力の完全性を保証する証明書ベースの停止規則を備えた、プロファイルに依存しないエージェントを導入した。
3. DegreeMap: 型付き要件ハイパーグラフと厳密なレキシコグラフィック最適化を組み合わせたプランナーを提示し、マスクされたソースおよびペアのゴールド（正解）対抽出済みデータのトラックを通じて評価を行った。

結果

システムは、Broad-100 トラック（100の大学）および Dense-6 トラック（多様な情報源形式を持つ6つの大学）で評価された。

• 抽出性能 (CatalogBrowse):
  • インベントリ・リコール（目録再現率）96.2%、およびマスクされたソースの回復率（隠れたページ背後のエンティティの回収）88.7% を達成した。
  • 全探索型のクローラーよりも 47%少ない ソースアクセスで、Static BFSやGo-Browse形式のエージェントを上回る性能を示した。
  • Broadトラックにおいて、高いTyped F1（79.4）およびAST意味的等価性（77.8）を維持した。
• 計画性能 (DegreeMap):
  • Dense-6トラックにおいて、100.0% の硬い実現可能性を維持した。
  • 最も強力なベースライン（LLMAP型のMSGS）に対し、パーソナライズされた効用を +0.066 向上させた。
  • 完了期間を6.7学期から6.3学期へと短縮した。
• エンドツーエンド性能:
  • フルパイプラインは、計画リクエストの 99.5% を証明（certify）した。
  • 特権的なゴールド・カリキュラム・グラフを用いた計画との効用差は、わずか 0.015 であった。
  • アブレーション研究により、固定点証明（fixed-point certificate）を削除するとリコールが4.4ポイント低下し、重み付き和の目的関数を使用すると証明された実現可能性が4.0ポイント低下することが確認された。

意義

本論文は、KnowPlanが構成上、獲得と計画の循環性を排除していることを主張している。カリキュラムの獲得（学生の目的とは独立したもの）と、計画の最適化を分離することで、データ獲得と使用のインターフェースを、想定ではなく測定可能なものにしている。著者らは、このアプローチが「カリキュラムは既知である」というモデリング上の仮定を、測定可能な量へと変換したことを強調している。これは、信頼できる学位計画には、学生固有の最適化を行う前に、プロファイルに依存しないカリキュラム獲得が必要であることを示している。このフレームワークは、エージェントが後の目的のためにワールドモデルを獲得しなければならないあらゆるドメインに一般化可能であり、その獲得ターゲットが目的を知る前に固定されていることが条件となる。