KT-IDEM: Introducing Item Difficulty to the Knowledge Tracing Model, Pardos+ (w/ Neil T. Heffernan), UMAP11

[AkihikoWatanabe]

http://web.cs.wpi.edu/~nth/pubs_and_grants/papers/2011/UMAP/Pardos%20Introducing%20Item%20Difficulty.pdf

[AkihikoWatanabe]

モチベーション

computer educationやassessmentのモデルでは項目困難度を考慮している。たとえば、Computer Adaptive Testing (CAT) で利用されるIRTは項目ごとの難易度パラメータを学習する。難易度パラメータの学習がstudent performanceを予測する際に大きく寄与しているが、学習プロセスにコストがかかり、生徒が特定のスキルに習熟したか否かを決定する際には実用的ではない。一方、Cognitive TutorsではKnowledge Tracingモデルを生徒がスキルに習熟したか否かを判断するのに利用している。KTが使用されるのは、それが生徒と教師の両方にとって有益なCognitive Diagnostic Assessment (i.e. 測定対象となっている領域・分野の学習や理解に必要なattributeを設定し、個々のattributeの習得状況を推定するようなアセスメント)であるためである。KTモデルのパラメータの学習は一度で済み、典型的にはschool yearの頭に前年のデータを利用する。そして、ここの生徒のスキルの習熟度は非常に少量の計算コストで算出できる。IRTのような項目困難度を考慮したモデルは予測精度が高い一方で、KTのような個々のスキルの習熟度を推定するcognitive diagnostic resultsは非常に有用である。これらが一つのResearch Questionを提起する：KTが項目困難度を考慮するように拡張したら予測性能が改善するのか？

※ CDAについてはこちらに説明されている：https://www.jstage.jst.go.jp/article/jltajournal/23/0/23_37/_pdf

モデルの気持ち

通常のBKTでは、4つのパラメータをデータからスキルごとに学習する。これらのパラメータは学生のそのスキルに対する正解/不正解の系列を時系列に並べたときに、その学生が該当スキルを知っている確率を推測する。現在の知識が与えられたとき、生徒のあるquestionに対するパフォーマンスを決定するのは2つのパラメータであり、それはguessとslipパラメータである。そして、これらのパラメータに対して我々はquestion levelのdifficultyを追加することを検討する。
高いguess rateを持つスキルは直感的には簡単と考えられる（e.g. multiple choice questionとか）。同様に、低いguess、あるいは高いslip率を持つスキルは困難なスキルだと考えられる。この直感から、項目困難度もguessとslipパラメータからとらえることができると考える。従って、我々の目的は、それぞれのquestionに固有のguessとslipパラメータを与えることで、項目ごとの難易度をモデリングすることである。

モデル

通常のBKTにmultinomial item nodeを追加する。これはすなわち、もし10個の異なる項目がスキルデータに存在する場合、ite, nodeは1~10の値をとる。このitem nodeはquestion nodeと接続し、これにより、questionのguess/slipがitem nodeによって条件づけられる。10個の項目があるデータセットの例では、モデルは10個のguess parameterとslip parameter、learn rate, priorを持つことになり、合計で22パラメータを持つ事になる（一方、通常のBKTでは4つのパラメータである）。
項目ごとに十分な量のデータポイントが存在しない場合、モデルが過剰なパラメータを持つ可能性があるが、データポイントど同等、またはそれ以上のパラメータを持つモデルが有効であるトレンドにあることはNetflix challengeや2010 KDD Cupで示されている。

上図がBKTにextra nodeを加えたものを図示している。通常のKTモデルでは単一のP(G), P(S)を持つが、KT-IDEMでは、項目ごとにP(G), P(S)を持つ。たとえば、P(G|I=1), P(G|I=2)k ..., P(G|I=10)であり、項目ノードの値が与えられると異なるguessパラメータをとる。図の例だと、生徒は項目ID 3, 1, 5, そして2に取り組んでいるが、この情報は観測可能であり、モデルトレーニングに使える。従って、P(G|I), P(S|I)をfittingすることができる。そして、predictionの際は、どの項目に生徒が取り組んでいるかを知らせれば推論ができる。

データセット

ASSISTmentsデータと、Cognitive Tutorデータセットを利用した。
ASSISTmentsデータセットでは、problem templateを項目とみなしたが。一方Cognitive Tutoerデータセットでは、problem（stepのコレクション）を項目とみなした。

ASSISTments Platform

ASSISTmentsはwebベースのturoring platformで、4年生から12年生までの数学のコンテンツを扱っている。下図は、ASSISTmentsにおける数学の項目の例であり、生徒が問題に不正解、あるいはhelpを要請した場合に表示されるチュートリアルヘルプの様子である。チュートリアルヘルプは、個々のproblemを解くのに必要な知識を学習するために、problemをsub questionに分解して（scaffoldingと呼ぶ）生徒にquestionを解くためのヒントを与える。questionは、生徒がヘルプのリクエスト無しでfirst attemptで正解した場合のみ「正解」したとみなす。

ASSISSTmentsにおけるItem template

skill building datasetは、複数のitem templateによって生成される複数のquestionに対するresponseによって構成される。
テンプレートは、コンテンツ開発者が Web ベースのビルダー アプリケーションで作成した問題の骨組みである。たとえば、テンプレートでピタゴラスの定理の問題を指定できますが、問題の数字は記入されていない。この例では、問題のテンプレートは次のようになる："辺の長さが X と Y の直角三角形の斜辺は何ですか?"。ここで、X と Y は、質問がテンプレートから生成されるときに値が入力される変数である。解答も、コンテンツ開発者が指定した解答テンプレートから動的に決定される。この例では、解答テンプレートは「Solution = sqrt(X^2+Y^2)」となる。変数の値の範囲を指定することができ、開発者は動的グラフ、表、単語問題のランダムに選択されたカバーストーリーなど、より高度なテンプレート機能を利用できる。テンプレートは、テンプレート項目のチュートリアルヘルプを構築するためにも使用される。これらのテンプレートから生成された項目は、学生が特定のスキルを練習するための大量の項目を提供する実用的な方法として、skill building problemセットで広く使用されている。

Skill building datasets

Skill buildingは、同じスキル、またはスキルグループに関連する多数の異なるテンプレートから生成された数百の項目で構成されるASSISTmentsの問題セットの一種である。生徒は、helpを要請せずに3つの項目に連続して正解すると、問題セットを完了したとみなされる。この問題セットでは、項目はランダムな順番で選択される。学生がSkill building problem setの10項目に連続して3つ正解せずに解答した場合、システムは学生が翌日までその問題セットを続行するように強制する。Skill building problem setは、Cognitive Tutorのmastery learningに似ているが、Cognitive Tutorでは、生徒が0.95以上の確率で生徒が該当スキルを知っているとKTモデルが推論した場合に習熟したと見做される。ASSISTmentsの他の問題セットと同様に、skill builder problem setは教員の最良で割り当てられる。そして、割り当てられる問題セットは、多くの場合学区が従う特定の数学カリキュラムに準拠している。

本研究では、2009年〜2010年の学年度の最もデータが多い10個のskill builder datasetを利用した。各問題セットの生徒数は637人〜1285人であり、テンプレートの数は2~6である。これは、最大で6つの問題セット内の項目に関連づけられたguess/slipパラメータが存在することを意味する。1日あたり10項目の制限があるため、問題セットごとに学生の最初の10項目に対する回答のみを考慮し、残りの回答は吐きした。オリジナルのquestionに対する回答のみを考慮し、scaffoldに対する回答は利用しないようにした。

The Cognitive Tutor: Mastery Learning datasets

Cognitive Tutor datasetは、2006-2007年におけるBridge to Algebraシステムに基づいている。このデータは2010年のKDD Cup competitionにも提供されている。Cognitive TutorはASSISTmentsとは異なるデザインがなされている。
非常に重要な違いの1つは、Cognitive Tutorが多くのスキルに関するquestion（stepと呼ばれる）にyほって構成されるproblemを提示することである（下図）。

生徒はproblemに関する様々なquestionへの回答を回答グリッドに入力できる（下図）。

Cognitive Tutorでは、Knowledge Tracingを生徒がスキルに習熟したかどうかを決定するために利用している。problemは異なるスキルのquestionによって構成されている場合もある。しかしながら、生徒がスキルを習得したとKTが判断した場合、生徒はproblem内の該当スキルのquestionに応える必要はなくなりますが、未修得のスキルに関連するquestionには応える必要がある。
Cognitive Tutorデータセットのスキル数は、ASSISTmentsデータセットよりも非常に大きいものとなっている。全てのスキルを処理する代わりに、ランダムにサンプルした12個のスキルを今回は選択した。複数のスキルによって構成されるquestionも存在する。こういった場合、各スキルを分離するのではなく、questionに関連づけられた一連のスキルを一つの単独のスキルとして扱った。Cognitive TutorはlessonsをUnitsと呼ばれる単位に区切っている。あるUnitに登場するスキル名が、別のUnitに登場する場合は別のスキルとして扱った。Cognitive Tutorには「ウィンドウを閉じる」や「enterを押す」などの瑣末なスキルも存在する。このような数学と関係ないスキルは無視した。ASSSISTmentsデータで使用される生徒ごとのデータ量との一貫性を維持するために、スキルごとの生徒ごとの回答の最大数も最初の10項目に制限した。

評価

5-fold cross validationを行った（生徒ごとに区切る）。パラメータの学習はBKT, KT-IDEM共にEMアルゴリズムによって行った。EMアルゴリズムはデータの尤度が最大となるパラメータを探索し、指定したmax numberの回数だけiteractionを行ったら、あるいは尤度の改善が一定の閾値を下回った場合に探索を終了する。max iteractino countは200にセットし、閾値は0.001とした。パラメータの初期値としては、両モデルに対して：P(G)=0.14, P(S)=0.09, P(L_0)=0.5, P(T)=0.14とした。この値は、ASSISTmentsデータを以前分析した際のスキル全体に対する平均値である。
生徒のfirst responseを予測する場合、項目の識別子以外の情報は与えられない。そのため、モデルのpriorとguess/slipパラメータ単独でモデルは予測を実施することとなる。これはすなわち、BKTでは全ての生徒に対してfirst responseは同じ予測結果を与える。一方KT-IDEMは生徒が最初に取り組む項目が異なるため、項目のguess/slipパラメータが異なっているため、全生徒の予測結果が同様のものとはならない。

評価結果

ASSISTments dataset

10個のデータセットに対して9つのデータセットでKT-IDEMがBKTを有意にoutperformした。BKTのAUCの平均は0.669に対し、KT-IDEMのAUCの平均は0.69であった。

Cognitive Tutor

全体のパフォーマンスとしては、BKT, KT-IDEM共に勝ち負けが入り混じっている。BKTの平均AUCは0.6457、KT-IDEMは0.6441であるが、これは統計的に有意差はなかった。前に述べたように、over parameterizationが項目ごとにguess/slipパラメータを用意することの懸念ん点であった。このデータセットでは、ASSISTments のテンプレートの数 (平均 3) と比較して、問題の数 (平均 311) がかなり多いため、この問題が明らかになります。問題の数が多く、パラメータの数も多いため、問題あたりのデータポイントの比率(dpr)が非常に重要となります。dpr>6を超えている5つのデータセットでは、KT-IDEMの予測性能が高い。これらのデータセットでは、BKTのAUCは0.6124、対してKT-IDEMでは0.7108である。この差は統計的に有意であった。dpr<6のデータセットについては、スキル6を除いて、lossは比較的少ないものであった（~0.04程度）。このスキルデータセットには396の問題があり、最も頻度の高い問題はデータポイントの25%を占め、2番目に頻度の高い問題はわずか0.3%だった。これは④ポカのスキルセットと比べて非常にバランスが取れておらず、KT-IDEMがうまく機能しないタイプのデータセットの例と言える。

Discussion

トレーニングデータに存在しない項目のguess/slipパラメータをどうするかという課題がある。対策としては、全ての学習されたslip/guessパラメータの平均値とするか、あるいはBKTモデルのguess/slipパラメータで置き換えるという対策がある。
Cognitive Tutorの実験結果より、問題ごとのデータポイントの平均数によって、KT-IDEMの精度がBKTよりも改善するか否かが決まることが示された。スキルデータセット内の一部の問題には大量のデータが含まれている一方、一部の問題には少量のデータしか含まれない可能性がある。KT-IDEMの制度を向上させるために、データが少ない問題のguess/slipパラメータをBKTが推定したguess/slipパラメータで置き換える方法がある。また、平均正答率の値や、ヒントをリクエストした回数などの情報を利用してguess/slipパラメータの初期値を決めることで、パラメータfittingが改善する可能性がある。

また、future workとしては、CATにおいてKT-IDEMのguess/slipパラメータを用いて、より少ない問題数でassesmentを実現することなどが挙げられている（KT-IDEMのguess/slipがIRTにおける項目の識別力に相当するとみなせる。また、質問に正解した場合、あるいは不正解だった場合に確率の変化が最大となる質問を選択することができるため。ただし、この質問には正しいguess/slipパラメータが推定されている必要があり、そのための十分なデータが必要となる）。