本文将介绍在教育模型中理论基础最完善且使用最广泛的自适应算法：计算机自适应测评系统(Computerized Adaptive Testing, CAT)。大家耳熟能详的一些计算机测评服务，例如ETS的GRE和TOEFL，都采用CAT作为推荐引擎。此外，CAT所依赖的测评理论，即项目反应理论（Item Response Theory, IRT），是心理测量学（psychometrics）的中流砥柱，有逾40年的理论研究基础，发展非常完善。最后，中国大部分教育技术公司在使用的自适应算法，可能不超过CAT的范畴。
本文首先介绍CAT的直觉基础，然后简要介绍其所依赖的IRT模型，并描述一种最简单的CAT工程设计。文章最后简单批判CAT作为一种学习算法的不足。
相较于传统的纸笔考试，CAT的优点是在相同题目数量下所达到的测评精度更高。或者反过来说，为了达到相同的测评精度，CAT所需要的题目更少。CAT能够实现更高效测评的直觉原因就是它能针对不同的作答挑选信息量最大（aka最具有甄别性）的考题。IRT模型是对于考题对于考生的信息量的定量评估的方法论基础。
I.自适应测评的理论基础
假设纸笔考试和计算机考试（CAT）的唯一区别在于是否存在自适应，那么什么时候CAT比纸笔考试好？这个小节将回答这个问题。
在这个小节中，我们将假设学生可以从一个能力维度上被分为两类人：学霸和学渣。顾名思义，学霸能力强，学渣能力弱。假设学霸和学渣在人群中各占50%。
（A）
假设有两道题，分别为送分题（易）和压轴题（难）。学霸和学渣都可以做出送分题，但只有学霸能做出压轴题。
假设你的目标是区分一个学生究竟是学霸和学渣，那么你应该出一张怎么样的卷子？
如果把送分题给学生做，不论是学霸和学渣都会做出来；其结果对于判定学生类型毫无帮助。如果把压轴题给学生做，做出来的就是学霸，做不出来的就是学渣；其结果对于判定学生类型非常有帮助。
让我们用更加严谨的数学语言来翻译上面的直觉推理（假设你熟悉贝叶斯定理）。假设你给了学生难题(
)，学生答对了（1）。此时，这个学生是一个学霸(X=1)的后验概率为
![\[P(X=1|Y_h=1) =\frac{P(X=1,Y_h=1)}{P(Y_h=1)}=1\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-ebd015eff587c989c2147382d3d135eb_l3.png "Rendered by QuickLaTeX.com")
与此相反，如果学生答错了，他为学霸的后验概率为0%。如果我们给了学生易题，学生答对了，他是学霸的后验概率依然是50%，和先验概率没有改变。（注意当给学生送分题时，不可能出现错误）
| 考卷/答案组合 | 1 | 0 |
|---|---|---|
| 难 | 100% | 0% |
| 易 | 50% | NA |
上表（计算过程参见这个链接的例1）列举了所有试卷/答案组合下的学霸后验概率。给定答案的组合，最优的试卷组合应该给与尽可能极端的后验概率（即最小化信息熵）。例如，当学生答对时，难题优于易题（100%>50%）。
综上所述，在这个情况下，卷子里只要有压轴题就够了。最优试卷方案唯一，因此纸笔考试和CAT一样。
（B）
案例A的结论主要来自于学生水平和解题结果存在确定关系的超强假设。而事实上两者的关系有不确定性。学霸也有失手的可能，学渣也有蒙对的希望。不可观察的学生能力和可观察的解题结果之间的不确定性是学习数据分析的根本问题。
现在假设有难中易三道题，其中：
（1）难题学霸有60%的概率做出来，学渣有10%的概率做出来；
（2）中题学霸有80%的概率做出来，学渣有60%的概率做出来；
（3）易题学霸有95%的概率做出来，学渣有90%的概率做出来。
假设你的目标是尽可能的精确地判断学生类型，你应该怎么出卷子？
答案是三道题全做。每一道题都有一定的区分度，信息量不为0。如果我们希望最精准的类型判断，每一道题都有价值。因此，如果可以不计代价地进行测评，选题没有什么价值，纸笔考试和CAT一样好。
（C）
然而事实上测评这件事情本身是有成本的，主要体现在时间成本；因此，大部分的考试都有时间限制。所以一个更加现实的目标是：
假设目标是在两道题内尽可能精确地判断学生类型，你应该怎么出卷子？
让我先给出答案：最优的测试方案取决于学生回答。因为CAT可以根据学生的作答进行选择，而纸笔考试不行。因此，给定相同题库和相同测试长度，CAT比纸笔测试要强。
[1] 纸笔考试
根据贝叶斯概率公式，我们可以得到全部试题+答案组合的学霸后验概率（具体计算过程请查看这个链接的例2[1]）。因为只有两类学生，所以只要最佳辨认学霸的方法也是最佳辨认学渣的方法。
| 考卷方案/答案组合 | 11 | 10 | 01 | 00 |
|---|---|---|---|---|
| 难+中 | 89% | 75% | 37% | 18% |
| 难+易 | 86% | 75% | 31% | 18% |
| 中+易 | 58% | 40% | 34% | 20% |
类似的，给定答案组合，后验概率最为极端的试题组合为最优。例如，当两题都答对时，难题加中题的组合最优，因为它的后验概率最大（89%>86%,89%>56%）。上表告诉我们，大部分情况下（除了第三列之外），难中的组合是最优的试卷组合。因此纸笔试卷会选择“难题+中题”的组合。
[2] CAT出题
CAT的优势在于它在出第二道题时，已经观察到了第一道题的结果。因此，它在第二题可以做出更好的选择。
通过类似于（A）中的计算，CAT的第一题会选择难题。假设学生做对了，他是学霸的后验概率为86%，他是学渣的后验概率为31%。第一题的后验概率会成为第二题的先验概率；并且此时我们从题库中刨去难题，只需考虑中题和易题。
| 第一题结果 | 对 | 对 | 错 | 错 |
|---|---|---|---|---|
| 试卷/答案 | 1 | 0 | 1 | 0 |
| 中 | 89% | 75% | 36% | 18% |
| 易 | 86% | 75% | 31% | 18% |
上表告诉我们，当学生第一题做对时，第二题应该出中题；当学生第二题做错时，第二题应该出易题。因此，CAT的选择是 难+中（第一题对）/难+易（第一题错）。
在这个具体例子中，CAT在学生第一题做错，第二题做对的情况下比纸笔考试的后验概率方差有所降低，尽管差距并不是很明显(0.1476 Vs. 0.1474)。
2. IRT模型
第一节简单介绍了CAT的原理。因为测试题对于隐藏能力的探测具有不确定性，而且相同测试题对于不同能力的学生而言，不确定性不同。因为CAT可以根据应试者的回答动态选择测评不确定性最小的题目，因此和纸笔考试相比，它达到相同的精度需要更少的题目，或者使用相同的题目数获取更好的精度。
第一节的分析做了一些非常强的假设：
（1）我们知道学生的类型（学霸Vs学渣）
（2）我们知道不同类型的学生在各个测试题上的正确率（eg，学霸难题60%正确率）
在现实中，这两个假设都不成立。因此我们需要一个模型来提供这两个重要的信息。项目反应理论（Item Response Theory，IRT）是提供这些信息的最流行的模型。关于IRT模型的较为详细的介绍在可以参见这个链接（ETS在2013年提供了一个IRT发展的综述）。常见的IRT会做了以下的假设：
（1）被试者能力是一维的（
）
（2）被试者能力是连续的（即不存在学霸VS学渣这样的有限多且可被解释分组，但是不同学生间可以排序）
（3）题目参数（
）和学生能力（）关于正确率（
，假设题目只有对错两种）的函数对应是
![\[P(Y=1|\theta,\alpha,\beta) = \frac{e^{\alpha(\theta-\beta)}}{1+e^{\alpha(\theta-\beta)}}\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-39bc9fd0dbdda0f737c98ccc1ccc4355_l3.png "Rendered by QuickLaTeX.com")
通过数据估计
就可以得到学生能力的分布以及不同学生在同一道题上的正确率分布。此外，这个结构式对于某些CAT选题算法而言，也是必须的。
3. 最简CAT的工程设计
上面两节介绍了CAT的原理以及IRT的概要，这一节将描述一个最简单（也是最经典）的CAT工程设计。这一节将以数学和符号为主，只想大概了解CAT的读者可以直接跳到讨论CAT扩展的第四节。
题目选择的算法有很多。这里我们介绍历史最悠久的一种：最大信息原则（Maximum Information Criterion）。
记学生id为
。学生i的真实能力值为
，学生i在第t道测试题的预估能力值为
。
记题目id为
。题目j的参数为
。在二参数IRT模型中（第二节的例子），
。
我们只把学生能力当做变量，把题目参数和做题结果都当做常量。
在二参数IRT模型下，记题目参数和学生参数与正确率的对应关系为
![\[p^i_j(\theta^i) = P(Y^i_j=1,\theta^i|\Theta_j) = \frac{e^{\alpha_j(\theta^i-\beta_j)}}{1+e^{\alpha_j(\theta^i-\beta_j)}}\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-2c5c75a36eaef8b9045faff5d2c105de_l3.png "Rendered by QuickLaTeX.com")
这种函数设定的好处是，Fisher information function（一种度量信息的方法）是线性可加的。因此，假设学生已经做了k-1题，第k题的Fisher Information就是
![\[I_j(\theta^i) = \frac{[p^i_j'(\theta^i)]^2}{p^i_j'(\theta^i)[1-p^i_j'(\theta^i)]}\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-6bc8b9342f6126af69d44c7f5aed11fa_l3.png "Rendered by QuickLaTeX.com")
其中
![\[p^i_j'(\theta^i) = \frac{\partial}{\partial \theta^i} p^i_j(\theta^i)\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-2c949322df3dc343b5ec9430fc3797d8_l3.png "Rendered by QuickLaTeX.com")
如果是已知的，那我们就可以计算每道题的Fisher Information，然后选取最大的那个题。然而遗憾的是，我们并不知道。所以在每一步中，我们都用估计值来替代。这个估计值可以这么估算
（1）初始化
给定学生能力值的先验概率分布
![\[\hat{\theta}^i_1 = \int \theta g(\theta) d\theta\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-06e1d996877663ea8cab35b242e90cdc_l3.png "Rendered by QuickLaTeX.com")
（2）后续迭代
之后每一步的
都是似然函数的最大似然估计值（Maximum Likelihood Estimator），其中似然函数是
![\[L(\theta) = \prod_{j=1}^{k-1} \frac{(e^{\alpha_j(\theta-\beta_j)})^{Y^_j}}{1+e^{\alpha_j(\theta-\beta_j)}}\]](http://www.fengjunchen.com/wp-content/ql-cache/quicklatex.com-0422599f2e9685f96f648837fc7c2c58_l3.png "Rendered by QuickLaTeX.com")
4. CAT的高阶话题
CAT作为一个有近30年历史的学科，其理论深度和宽度远远超过本文所讨论的内容。有兴趣的朋友可以阅读由Wim J. van der Linden和Cees A.W. Glas编辑的Computerized Adaptive Testing: Theory and Practice。这本书覆盖了2000年左右CAT发展。
大体上说，一个完善的CAT系统需要解决以下几个麻烦的问题：
（1） 第三节假设题目参数是已知的，而实际上题目参数是未知的。怎么解决题目参数估计误差所导致的题目选择偏差？
（2）因为学生能力估计是有误差的，如果选择区分度高的题，可能导致估计该步信息失准
(3) 怎么评估题库题目的质量?怎么确保题库有足够多的题目可以应付多场考试?(例如GRE要保证70套完整题目组)怎么确保题库题目更新迭代不影响不同考试间的可比性(GRE题目的寿命是3个月)
(4)如果能力是多元的怎么办？更麻烦的是(对于国内中高考尤其是如此)，如果一道题涉及多个能力项怎么办?
(5)怎么处理额外的试卷限制，例如考试时长，平均分限制和题目曝光总量控制
5.CAT作为自适应“学习”算法的不足
CAT作为一种测评算法已经被证明是可行且高效的。 随着人机交互界面的改善和算法的进步，计算机将不仅可以完全兼容纸笔试题（主要是主观题），而且可以实现许多纸笔考试难以完成的试题（例如VR支持的实验动手测试）。因此，CAT将会在测评领域取得更进一步的发展，这是毋庸置疑的。
然而，作为一种学习算法，CAT却是先天不足。CAT假设学生在做题过程中，其能力值是不变的；这从根本上否定了学习的可能性。一个否定学习可能性的算法，如何用来指导教学推荐呢？因此，仅仅是CAT（或者IRT）是不能够独立支撑起一个学习推荐系统的。
当自适应学习发生在知识点间时（参考我的这篇文章），CAT可以作为测评模块，配合知识空间理论（比如ALEKS）或者专家系统（比如Khan Academy）的教学模块，组成一个智能学习推荐系统。