BKT训练及测试-大规模拟合隐马尔科夫模型工具

此命令行工具由C/C++编写，目的是为了在大型数据集中拟合隐马尔可夫模型（HMM）。它针对一种用于教育领域的特殊HMM，称为贝叶斯知识追踪（BKT）模型。

贝叶斯知识追踪

贝叶斯知识训练（Bayesian Knowledge Training，BKT）是一种在智能辅导系统（ITS）领域广泛使用的用户建模方法。在ITS中，通常会使用知识点标记学生正在解答得问题。我们认为学生解答问题的过程是练习了一个或多个技能的过程。学生模型（BKT是其中之一）判断解决问题过程中一系列正确或不正确的结果，以确定该技能是否被掌握。BKT使用隐马尔可夫模型计算学生技能掌握的概率，其中有两种类型的节点：状态节点表示技能掌握情况，它们的值为掌握或未掌握，以及观察节点，它们的值为正确或不正确。

标准BKT中，每一个知识点都有如下的参数：

p-init/P(Lo)：知识点先验已掌握的概率；
p-learn/P(T)：经过学习之后，某一知识点由不会到会的学习转移概率；
p-forget/P(F)：学习过程中，某一知识点由会到不会的遗忘概率；通常情况下p(F)被设为0，不计入参数中；
p-slip/P(S)：在知道某一知识点时，做题表现为错误的失误概率；
p-guess/P(G)：在不知道某一知识点时，做题表现为正确的猜测概率。

BKT参数可以用向量或矩阵形式表示。全局先验的向量包含P(Lo)参数。在先验向量中有N=2个元素，假设P(Lo)是向量的第一个元素。

在状态转移矩阵A中，p(T)是一个元素，涵盖掌握状态变化的概率，其大小为N * N。设置A [1,2]=0将不予捕获遗忘过程（从掌握到未掌握）。P(T)对应于A [2,1] - 从未掌握到掌握。

观测矩阵B中指定了P(G)和P(S)，该矩阵的大小为N*M，其中M是观察数（在标准BKT中为M=2）。第一列对应于正确的观察结果，第二列对应于错误的观察结果。在具有两个观察结果的标准BKT中，P(G)是B[2,1] - 未掌握的技能但是正确的响应，P(S)是B[1,2] - 掌握的技能但是错误的响应。

$掌握知识点的先验概率没有掌握知识点的先验概率$

$掌握知识点未掌握知识点掌握知识点未掌握知识点$

$回答正确回答错误掌握知识点未掌握知识点$

获取并编译代码

标准BKT代码的公开版本可以通过GitHub仓库获得。如果你安装了git工具，使用下面的命令来获取源代码。

1	git clone https://github.com/myudelson/hmm-scalable

使用make all指令编译。如果在Linux上，g++/gcc编译器和Open MP库应该已经安装了。在Mac OX上，你需要通过xcode-select --install命令来安装Xcode命令行工具。g++/gcc编译器与Open MP（默认情况下不再与Mac OS X捆绑）可以从这里下载。如果你是在Windows上，你可能需要安装cygwin，并有g++/gcc编译器可用，并确保也安装make工具。

数据

输入文件

输入的数据文件应该是一个具有Unix行末编码的文本文件。其格式为四个以Tab分隔的列：观测、学生、问题/问题步骤、知识点。观测值是一个以1开头的整数。对于双状态的BKT，建议使用1表示正确，2表示不正确。学生、问题或一个问题步骤、以及知识点都是一个字符串标签。多知识点标签应该由你选择的字符来分隔（不要使用Tab）。下面是一个有几行输入的例子。在这里~被用作分隔符。

-- input file --
2   student_001 unit1-section1-problem5-step1  addition~multiplication
1   student_001 unit1-section1-problem5-step2  multiplication
1   student_001 unit1-section1-problem5-step3  addition
-- input file --

如果某一行的数据没有知识点标签，则使用.符号。在测试数据中，该工具将使用已知的观测值进行训练，并对缺失的观测值进行预测，这些观测值应该有.而不是观测的数值（1、2或其他）。

输出文件

输出文件是模型文件和预测文件。

模型文件

模型文件包含关于数据的一般信息，例如观测数、知识点数和问题/问题步骤的数量，也包括模型的参数。

-- model file --
SolverId    1.1
nK    1
nG    1
nS    2
nO    2
Null skill ratios      1.0000000      0.0000000
0    multiplication-skill
PI    0.45000000    0.55000000
A    1.00000000  0.00000000    0.40000000    0.60000000
B    0.79000000    0.21000000    0.22000000    0.78000000
-- model file --

例子包括

具体的求解器算法（1.1）
一个知识点（nK=1）
一个学生（nG=1）
两个隐藏状态（nS=2）
两个观测值（nO=2）
知识点的编号从0开始
知识点名称为 multiplication-skill
PI对应初始化概率向量；PI的第一个元素p(Lo)=0.45
A对应状态转移矩阵；A的第三个元素p(T)=0.4
B对应confusion矩阵，表示可观察变量与隐藏变量的转换概率；B的第二和第三个元素分别是p(S)=0.21和p(G)=0.22。

预测文件

预测文件由对输入文件的每一行的模型预测组成。根据选项的不同（见下面的参数说明），输出学生回答的概率分布（正确和不正确的概率）。此外还可以输出针对特定知识节点隐藏状态值的概率分布。概率值以Tab分隔。请看下面的输出文件的例子。

-- prediction file --
0.73    0.27
0.88    0.12
0.94    0.06
0.99    0.01
-- prediction file --

上述例子是一个有nO=2个观测值的标准BKT模型，它将包含两列，中间用Tab分隔开。

第一列是BKT模型估计学生在此次观察中回答正确的先验概率。
第二列是对正确概率的补充，也就是答错的概率。

训练BKT模型

trainhmm使用以下的参数：

trainhmm [选项] 输入文件 [[模型文件] 预测文件]

选项：

-s:格式-s 结构.求解器[求解器设置]

结构:
- 1- 知识点
- 2- 用户
求解器:
- 1-Baum-Welch算法
- 2-梯度下降法
- 3-共轭梯度法
  - 1-Polak-Ribière-Polyak
  - 2-Fletcher–Reeves
  - 3-Hestenes-Stiefel
  - 4-Dai-Yuan

例如：-s 1.3.1指按知识点结构，求解器使用共轭梯度下降，求解器设置为Polak-Ribière-Polyak

-s 2.1指按学生结构，求解器使用Baum-Welch。

-S：对前向/后向变量进行缩放：0-关闭（默认），1-打开。只在Baum-Welch求解器中生效-s 1.1，否则自动设置为关闭。

-e：设置允许的终止判据(默认0.001)；可以被计算为对数似然中每个数据点的变化，例如-e 0.00001,l。

-i：最大迭代数（默认200）

-q：无输出的安静模式，0-否（默认），1-是

-n：隐藏状态的个数，应大于等于2（默认2）

-0：逗号分隔的初始参数，用于初始概率、状态转移概率和混淆概率，跳过每个向量（矩阵行）的最后一个值，因为它们的总和应该是1；默认是0.5,1.0,0.4,0.8,0.2。

-l：参数的下限，以逗号分隔的初始概率、状态转移概率和混淆概率（无跳转）；默认为0,0,1,0,0,0,0,0。

-u：参数的上限，用逗号分隔的初始概率、状态转移概率和混淆概率（无跳转）；默认为1,1,1,1,1,1,0.3,0.3,1，滑动和猜测的上限为0.3。

-c：用于 L2 惩罚的 C 权重和中心点的规格，空（默认）。对于标准BKT - 4个逗号分隔的数字：惩罚的C权重和中心点，分别用于PI、A和B矩阵。如果用于有学生效应的iBKT，将使用8个值，其中4个附加值用于学生矩阵。例如，-c 1.0,0.5,0.5,0.0。

-f：拟合为一个知识点，0-否（默认），1-拟合为一个知识点并使用参数作为多知识点的起点，2-强制使用一个知识点。

-m：输出模型拟合指标（AIC、BIC、RMSE） 0-否（默认），1-是。要指定要报告指标的观测值，请在,后面列出。例如，-m 0, -m 1 (默认情况下，假设观测值为1), -m 1,2 (计算观测值2的度量)。与-v选项不兼容。

-v：交叉验证折数、分层采样法、验证目标状态、折数输入/输出文件，默认0（无交叉验证），如-v 5,i,2，5折，项目分层的c.-v.，预测状态2， -v 10 - 10折，主题分层的c.-v. v.默认预测状态1，或者 -v 10,g,1, -v 5,n,2,folds.txt,o - 5折非分层c.-v.预测状态2，[o]输出折叠到folds.txt，这里 -v 5,n,2,folds.txt,i，折叠实际上是从文件中读取[i]n。

-p：输出模型对训练集的预测，0-否（默认），1-是；2-是，加上输出状态概率；与-v和-m参数一起工作。

-U：控制状态的概率分布如何被更新。采取以下格式-U r|g[,t|g]，其中

第一个字符-控制预测如何处理已知观测值
第二个字符-预测如何处理未知观测值
第三个字符-是否输出先验概率。

处理已知观测值r–揭示实际观测值以更新状态概率分布（对模拟实际系统如何工作有意义），g–根据预测结果猜测观测值（arg max）–在比较模型时更合适（这样就不会有关于观测的信息被揭示）。处理未知的观测值（标记为.-点）：t-仅使用过渡矩阵，g-猜测观测值。默认（如果省略）是-U r,t。例如，-U g,g需要使用模型参数和状态分布概率的运行值来猜测观察结果是什么。

-d：分隔符，用于每次观察中的多种知识点；每次观察单一知识点（默认），否则 - 分隔符，例如 -d ~。

-b：将输入文件转换为由inputconvert工具从文本文件创建的二进制输入文件。

-B：分别阻止对先验、过渡或排放参数的重新估计（默认为-B 0,0,0），要阻止对过渡概率的重新估计，请指定-B 0,1,0。???

-P：使用并行处理，

默认 - 0（无并行处理）
1 - 分别拟合单独的知识点/学生
2 - 分别拟合知识点/学生中的单独序列。

-o：除了打印到控制台外，还可以打印输出到该选项中指定的文件（默认为空，不做额外的打印）。

使用模型预测

predicthmm使用以下格式：

predicthmm [选项] 输入文件模型文件 [预测文件]

-q：没有输出的安静模式，0-否（默认），1-是。

-m：输出模型拟合质量评判（赤池信息量（AIC），贝叶斯信息量（BIC），均方根误差（RMSE）），0-否（默认），1-是。要指定要报告哪些指标的观察，请在,之后列出。例如-m 0，-m 1(默认使用观察1)，-m 1,2(为观察2计算度量指标)。不能与-v 同时运行。

-d：每个观察中多种知识点使用分隔符号；每个观察一个知识点（默认），否则使用分隔符，如-d~。

-b：将输入文件视为由inputconvert工具从文本文件创建的二进制文件。

-p：输出模型对训练集的预测，0-否（默认），1-是；2-是，并且加上输出状态概率；与-v和-m参数一起工作

-U：控制状态的概率分布如何被更新。采用-U r|[g,t|g] 其中

第一个字符–控制如何预测已知的观测值
第二个字符–预测如何处理未知的观测值
第三个字符–是否输出先验概率

例子

小样本数据文件toy_data.txt使用一下BKT参数生成的：pLo=0.4, pT=0.35, pS=0.25, pG=0.12.

为了使用EM算法拟合这些数据的BKT模型，运行以下命令：

1	./trainhmm -s 1.1 -m 1 -p 1 toy_data.txt model.txt predict.txt

该模型将有90%的准确性，均方根误差（RMSE）= 0.302691，恢复的BKT参数将是：

pLo=0.00000000，pT=0.16676161，pS=0.00044059，pG=0.00038573。整体的对数似然，在三次迭代中从9.3763477上升到10.4379501。

如果使用-s 1.2参数的梯度下降法来拟合BKT模型，恢复的参数将是

pLo=0.00000000，pT=0.3095828498，pS=0.18955371，pG=0.16195590，准确率仍保持在90%，同时RMSE=0.344145。经过19次迭代后，对数似然从9.3763477变为8.0992564。

运行以下命令生成用先前模型拟合的预测结果：

1	./predicthmm -p 1 toy_data_test.txt model.txt predict.txt

可以使用KDD Cup 2010数据集进行测试，此数据集可以从这里下载，它由训练集和挑战集组成。为了测试该工具，请下载挑战代数集，它有超过3300名学生的大约900万个事务。训练文件应该被修剪成工具的格式。请看下面的shell命令，可以做到这一点。

gawk -F"\t" 'BEGIN{OFS="\t"} {if(NR==1)next; skill=$20; gsub("~~", "~", skill); if(skill=="") skill="."; else { skill=$3"__"skill; gsub(/~/, "~"$3"__",skill);} print 2-$14,$2,$3"__"$4,skill;}' algebra_2008_2009_train.txt > a89_kts_train.txt

为了此数据集能够使用梯度下降法拟合此BKT模型，同时计算拟合指标和预测值，请运行以下命令：

1	./trainhmm -s 1.2 -d ~ -m 1 -p 1 a89_kts_train.txt model.txt predict.txt