深度知识追踪（Deep Knowledge Tracing）

深度知识追踪（Deep Knowledge Tracing）

知识追踪是基于学生行为序列进行建模，预测学生对知识的掌握程度。知识追踪是构建自适应教育系统的核心和关键。在自适应的教育系统中，无论是做精准推送，学生学习的路径规划或知识图谱的构建，第一步都是能够精准预测学生对知识的掌握程度。

知识追踪问题可以描述为： 给定一学生的观测序列$x_0,\dots \dots ,x_t$预测下次表现$x_{t+1}$，通常 x t = { q t , a t } \mathbf { x } _ { t } = \left\{ q _ { t } , a _ { t } \right\} xt​={qt​,at​}，其中$q_t$代表回答的问题成分（如对应的知识点），$a_t$代表对应的回答是否正确，通常 a t = { 0 , 1 } a _ { t }=\left\{0,1\right\} at​={0,1}。 下图描述了一个学生在八年级数学中的知识追踪结果可视化展示。

传统的知识追踪是基于一阶马尔可夫模型，如贝叶斯知识追踪(Bayesian Knowledge Tracing)，2015年 Chris Piech 等人提出利用深度学习来处理知识追踪的任务，之后引发了学者们对利用深度学习来处理知识追踪任务对不断探讨，下面依次介绍相关论文核心内容及思考。

Deep Knowledge Tracing

循环神经网络（RNN）是一种时间序列的模型，天然具有高维连续的隐状态表示的特征，RNN能够利用早期的信息进行预测，因此在2015年 Chris Piech 将RNN应用于知识追踪领域，并取得了较好的结果。

模型：

文章中，作者采用了传统的RNN模型和其变种LSTM，其输入数据为经过编码的$q_t$，输出为$a_t$。对于输入的编码方式有两种：

1. 将输入进行one-hot编码，如模型输入数据涉及M个知识成分（如知识点），每道题有两种结果0，1（分别对应答错和答对），则模型输入长度为2M。例如，对于某题，其知识成分为i，若答对，对应输入为第i+1位为1其余位置为0；若答错，则第i位为1其余位置为0。
2. 将输入进行压缩，若知识成分M巨大时，输入维度过高，可以采用感知压缩使输入从2M降低至$\log (2M)$。

模型输出$y_t$ 长度为M，对应描述了每一个知识成分的掌握程度（即对应知识成分所对应题目的答对概率），模型的核心为使用前$t$时刻的学生做题序列预测$t+1$时刻的知识成分的掌握情况，即：$P(y_{t+1}|x_t,\dots \dots ,x_t)$。
模型的目标函数是观测序列的非负对数似然函数，假设 $\delta \left(q_{t+1}\right)$为$t+1$时刻的编码输入，$l$为二进制交叉上函数，目标函数如下：

$L={\sum }_t\ell \left({\mathbf{y}}_i^T\delta \left(q_{t+1}\right),a_{t+1}\right)$

模型优缺点：

优点：

1. 能够反应长时间的知识关系，基于RNN的特性能够根据学生近期学习表现进行预测（近因效应），也能根据实际学生学习路径进行建模；
2. 能够对复杂的知识点之间的联系进行建模，如构建知识图谱；
3. 能够处理多知识成分的问题。

缺点：

1. 模型无法重构输入，即输入某一知识成分答题错误，模型对该知识成分的预测反而是正确。
2. 在时间序列上，学生对知识点的掌握程度不具有连续一致性，波动情况较大。

Going Deeper with Deep Knowledge Tracing

2016年Xiaolu Xiong等人对DKT和PFA(Performance Factor Analysis)，BKT(Bayesian Knowledge Tracing)模型进行了比较，对DKT模型能碾压其他两种模型的结果进行了怀疑并加以论证，进一步讨论了原论文能够得出上述结果的原因，对进一步使用DKT模型提供了参考。
文章中指出，对于DKT文章中在ASSISTments数据集上取得好的结果的原因进行了分析，得到以下三个原因来说明为什么DKT能够取得碾压BKT的效果：

1. ASSISTments数据集中存在23.6%的重复数据，这部分数据应该舍弃而不应该用于训练或测试。
2. DKT模型在实验中，并没有去除脚手架式的教学问题的做题记录，这就导致DKT模型能够有更多信息引入模型。
3. 由于DKT处理多知识成分的问题时，单条做题记录会被扩展成多条，存在重复利用数据的问题。

作者将上述问题数据依次剔除，形成多个数据集，并采用ACU和$r^2$作指标，对DKT，PFA，BKT模型进行了对比，结果表明DKT相比BKT和PFA没有碾压式的超越但是的确会比其他模型结果要好。
文章中提及，当遇到多知识成分的题目时，使用联合知识成分作为新的知识成分的方式比重复利用做题记录的方式结果要差很多，这也是在我们实际使用DKT模型中需要注意的。

Addressing Two Problems in Deep Knowledge Tracing viaPrediction-Consistent Regularization

Chun-Kit Yeung等人在2018年6月发表论文中指出DKT模型现存的缺点，即对输入序列存在重构问题和预测结果的波动性，进而论文提出了改善上述问题的方法：增加对应的正则项，得到DKT+（增强的DKT模型）。

如上图所示，纵轴$S_i$表示知识成分，横轴为学生在各个知识成分上的答题情况。
问题1对应的是在$6^{th}$step，$S_{45}$的评估结果相比前一时刻是增加了的即使当前的输入是$S_{45}$做错了的。
问题2对应为在上述图描述的学习过程中，$S_{32},S_{33},S_{45}$和$S_{55}$预测做对的概率随着 $S_{32},S_{33}$的学习有着非常大的波动，这和我们实际情况是不相符的，我们总是期望知识成分的变化是随着时间缓慢变化的，而不是在掌握和没掌握之间跳跃。

对于问题1，作者认为出现这种情况是由于，在DKT模型采用的损失函数中并没有考虑到时间t时刻的输入值，只是考虑了t时刻的输出值和t+1时刻的输入值。为了解决上述问题，作者在损失函数中引入正则项，并在正则项中引入了时间t时刻的输入值，正则项r如下：

$r=\frac{1}{{\sum }_{i=1}^n\left(T_i-1\right)}\left({\sum }_{i=1}^n{\sum }_{t=1}^{T_i-1}l\left({\mathbf{y}}_t^i\cdot \mathbf{\delta }\left(q_t^i\right),a_t^i\right)\right)$

对于问题2，作者认为可能是由于RNN的隐层表示问题，RNN的隐含层${\mathbf{h}}_t$依赖于前一隐含层的输出${\mathbf{h}}_{t-1}$和当前输入${\mathbf{x}}_t$，隐含层表示了潜在的学生知识掌握程度，但是很难说清隐含层的每个状态是如何影响对知识成分的预测。所以简答起见，直接对输出结果进行正则约束（L1，L2正则），使预测结果能够平滑输出，所加正则项如下：

$w_1=\frac{{\sum }_{i=1}^n{\sum }_{t=1}^{T_i-1}{\Vert {\mathbf{y}}_{t+1}^i-{\mathbf{y}}_t^i\Vert }_1}{M{\sum }_{i=1}^n\left(T_i-1\right)}$ $w_2^2=\frac{{\sum }_{i=1}^n{\sum }_{t=1}^{T_i-1}{\Vert {\mathbf{y}}_{t+1}^i-{\mathbf{y}}_t^i\Vert }_2^2}{M{\sum }_{i=1}^n\left(T_i-1\right)}$
综合上述正则项，最终模型的损失函数为： ${\mathcal{L}}^{\prime }=\mathcal{L}+{\lambda }_{r}r+{\lambda }_{w_1}{w}_1+{\lambda }_{w_2}{w}_2^2$

Does Deep Knowledge Tracing Model Interactions Among Skills?

Shirly Montero 等人在2018EDM上发表的paper，通过对比DKT和BKT的不同，来分析得到为何DKT能够获得比较好的结果的原因，论文从三个方面进行了比较：1）模型规模上，DKT是一个具有多自由参数的神经网络模型，而BKT是一个概率模型，拥有有限的自由参数。2）DKT对一个领域内所有skill建模，而BKT是根据skill构造模型。3）DKT是多skill的交叉输入，而BKT是按照skill进行拆分的。最终得到的结论是1),3)是DKT取得好的效果的关键。
为验证，通过如下方式区分DKT和BKT的不同模型：

• DKT是随着时间的推移，所有的skill都是交织在一起的，并按照顺序对每个问题做预测，而BKT是根据技能单独做成对应的序列，这种区别对应于combined sequence (CS)和 separate sequence (SS)。
• DKT是通过一个model学习所有的skill，而BKT假设对每个skill训练单独的model，这种区别对应于combined model(CM) 和 separate model(SM)。
• DKT基于神经网络而BKT基于概率模型。因此DKT相比BKT拥有更多的自由变量。

基于上述不同，作者分别采用了四种模型在三种数据集上做了验证，来证明是哪些特征使得DKT拥有比较好的效果，结果如下：

上述结果中BKT-SM-SS对应于标准的BKT模型，DKT-SM-SS是对不同对skill采用不同对model建模，对应的输入也是当前skill 的序列。DKT-CM-SS使用同一个model对所有skill做预测，区别于标准的DKT是输入是按照skill进行分割的。DKT-CM-CS则对应于标准的DKT模型。
通过上述结果我们可以得到：

• DKT可以通过交织的都skill序列获得增益。
• 对比DKT-SM-SS和DKT-CM-SS的结果可以看到，通过一个模型对按照skill进行分割的数据做预测并不能得到增益。
• DKT并没有像BKT一样引入强人类学习理论，这或许可以解释简单的全有或全无的学习——没有遗忘的BKT假设的理论过于简单。

Incorporating Features Learned by an Enhanced Deep Knowledge Tracing Model for STEM/Non-STEM Job Prediction

该模型是Chun-Kit Yeung等人在参加2017 ASSISTments Data Mining 竞赛中使用的方案，该竞赛是使用中学的学生行为预测高中/大学的结果。本文章在DKT和DKT+的基础上，使用了其他学生相关的综合特征，实验结果表明使用了其他特征的效果要比基础模型好。该文章为我们提供了引入其他学生行为特征的方法。
本文提出的模型主要思想是利用DKT+学习序列数据，得到${\mathbf{X}}_{KT}$代表学生的最新的知识状态，然后结合学生其他特征${\mathbf{X}}_{SP}$得到feature set${\mathbf{x}}_f=\left[{\mathbf{x}}_{SP},{\mathbf{x}}_{KT}\right]$送入机器学习模型(如GBDT， LR，LDA， SVM等)得到最终的预测结果。
上述模型的思想比较简单，可以看作集成模型Stacking的一种方式，整个模型的框架如下：

Prerequisite-Driven Deep Knowledge Tracing

Penghe Chen等人在使用DKT时考虑到数据的稀疏性(skill空间比较大，学生做题比较有限)，为解决由于数据稀疏性带来的模型评估不准确，提出了将知识结构的信息纳入模型来解决上述问题，具体是指考虑来知识的前后置关系。
核心观点在于如果$K_1$是$K_2$的前置，则$K_2$的掌握程度要小于等于$K_1$，即后置的掌握程度要小于等于前置的掌握程度。
具体过程如下：
如果$K_1$是$K_2$的前置，则：

• $P(M_{i,k_2,t_2}=1)$很大，则$P(M_{i,k_1,t_1}=1)$更大：
  即学生i如果在$t_2$时刻掌握了$K_2$，则说明在前一时刻，学生已经掌握了其前置知识$K_1$；
• $P(M_{i,k_1,t_1}=1)$很小，则$P(M_{i,k_2,t_2}=1)$更小：
  即学生i如果在$t_1$时刻没有掌握$K_1$，则说明在下一时刻，学生更不可能掌握其后置知识$K_2$；

上述知识结构上的信息体现在model中是通过修改损失函数的方式实现的，具体损失函数如下：

${\max }_{\Theta }\log {\prod }_i{\prod }_{t}P\left(y_{i,\pi (i,t),t}|{\mathbf{s}}_i,\Theta \right)$
s.t. $P\left(m_{i,k_2,t_2}=1\right)\le P\left(m_{i,k_1,t_1}=1\right)$
$\forall \left(k_1,k_2\right)\in E\&y_{i,\pi \left(i,t_1\right),t_1}=y_{i,\pi \left(i,t_2\right),t_2}$
对上述进行变形，将强约束变为弱正则引入模型，损失函数为： ${\max }_{\Theta }{\sum }_i{\sum }_t\log P\left(y_{i,\pi (i,t),t}|{\mathbf{s}}_i,\Theta \right)+$
$\lambda {\sum }_i{\sum }_{k_1,k_2}{\sum }_t{\sum }_{t_2}\delta (\ast )\left[\log P\left(m_{i,k_1,t_1}\right)-\log P\left(m_{i,k_2,t_2}\right)\right]$

下面分两部分来解释上面的loss：

• 第一部分，其中${\mathbf{s}}_i$表示学生i的做题序列，$\Theta$表示模型的所有参数，$\pi (i,t)$表示学生i在t时刻回答的题目，$y_{i,\pi (i,t),t}$对应学生i在t时刻回答题目的answer，因此loss的第一部分是在给定模型和序列下的结果最大化。
• 第二部分，对应于知识结构的前置约束，其中$\delta (\ast )=\delta \left(y_{i,\pi \left(i,t_1\right),t_1}=y_{i,\pi \left(i,t_2\right),t_2}\right)$，即只有前后两个时刻的answer一致且存在前后置关系时，第二部分的正则才会有效。

最终实验结果表明，加入知识结构信息的model比原始DKT结果要好，具体详见paper。
(PS: 笔者在本公司的数据集上验证并没有得到提升?)

---

参考文献:

1. Deep Knowledge Tracing
2. Addressing Two Problems in Deep Knowledge Tracing via Prediction-Consistent Regularization
3. Going Deeper with Deep Knowledge Tracing
4. How Deep is Knowledge Tracing?
5. Incorporating Features Learned by an Enhanced Deep Knowledge Tracing Model for STEM/Non-STEM Job Prediction
6. Does Deep Knowledge Tracing Model Interactions Among Skills?
7. Prerequisite-Driven Deep Knowledge Tracing