分类： 教学思想和技术

对于一个相互没有联系的集合中每个个体的考试，这里考试指检查每一个是不是好的或者是不是被理解掌握好的，我们除了尝试每一个个体没有更好的办法。

然而，如果个体之间存在关联，我们就可以把考试和推断结合起来，找到比尝试每一个个体更高效的方法。然而，有的时候，这样的关联尽管存在但是很难事先知道。例如，在考某个学生的一堆物理概念的掌握程度的时候，尽管物理概念之间的关联肯定存在，但是到底如何关联，需要通过检测这个学生同时掌握哪一些，才知道。然而，我们正好想避开这样的穷举法检测。因此，这是一个相互依赖的难题。那有没有一些可能具有代表性的关联呢，尽管这样的关联在不同的被试身上不一定表现一致，仅仅表现为某种平均意义上的关联？如果有，这样的关联，能不能不依赖于检测得到呢？得到这样的关联之后，又如何和推断结合起来，帮助实现更高效的考试呢？这个帖子尝试回答这些问题，或者说，给出一个回答这些问题的框架。

我们认为，概念之间的逻辑关系，可以做为关联的客观表现。以汉字为例，汉字之间通过结构关系相互联系，这一点是客观的（尽管繁体字和简体字在汉字之间是如何从结构上联系起来的这一点上不一样。先考虑例如仅仅简体字）。例如：木——林——森，人——从——众，水——冰——淼，（木，一）——本，（人，本）——体。当然，这个客观的结构联系是否就能代表逻辑联系，是有待讨论的。也就是说，在汉字集合上，存在着一个逻辑关系网络，网络的每一条边代表上面举例中的一个字$i$成为另一个字$j$的一部分这样的结构关系$A=\left(a^{i}_{j}\right)_{N\times N}$。这个结构关系上面叠加了一层逻辑关系。这个逻辑关系，我们通过下面的几个权重——已知认识一个字，推断另外一个字也认识的条件概率——来表达。任何一个时候每一个字$j$的检测状态记为（$c_{j}k_{j}=\left\{11, 1-1, 01, 00, 0-1\right\}$）分别代表检测过认识，检测过不认识，没有检测过推断认识，没有检测过推断状态为未知，没有检测过推断不认识，这五个状态。注意，凡是检测过的字的状态就不再用下面的条件概率来更新了。

1. 认识上层字$i$，推断下层字认识$j$的概率，$\omega^{i, \left(1\downarrow\right)}_{j}$，和结构矩阵的元素$a^{j}_{i}$有关。原则上可以不遵循结构矩阵，来自于其他实证关系。做为一个简化模型，我们可以假设$\omega^{i, \left(1\downarrow\right)}_{j} =a^{j}_{i}=1$。
2. 认识下层字$i$，推断上层字认识$j$的概率，$\omega^{i, \left(1\uparrow\right)}_{j}$，和结构矩阵的元素$a^{i}_{j}$有关。原则上可以不遵循结构矩阵，来自于其他实证关系。做为一个简化模型，我们可以假设$\omega^{i, \left(1\uparrow\right)}_{j} = 0$。
3. 不认识上层字$i$，推断下层字不认识$j$的概率，$\omega^{i, \left(-1\downarrow\right)}_{j}$，和结构矩阵的元素$a^{j}_{i}$有关。原则上可以不遵循结构矩阵，来自于其他实证关系。做为一个简化模型，我们可以假设$\omega^{i, \left(-1\downarrow\right)}_{j} =0$。
4. 不认识下层字$i$，推断上层字不认识$j$的概率，$\omega^{i, \left(-1\uparrow\right)}_{j}$，和结构矩阵的元素$a^{i}_{j}$有关。原则上可以不遵循结构矩阵，来自于其他实证关系。做为一个简化模型，我们可以假设$\omega^{i, \left(-1\uparrow\right)}_{j} =a^{i}_{j}=1$。

在这里，简化模型的理念是认识更复杂的意味着认识简单的子结构，不认识更简单的子结构则更复杂的合成字肯定不认识。注意，这个是对原始问题的一个极大的简化。

现在，我们有了一个结构网络$A$，四个这个网络上的逻辑关系$\Omega^{\left(1\downarrow\right)}, \Omega^{\left(1\uparrow\right)}, \Omega^{\left(-1\downarrow\right)}, \Omega^{\left(-1\uparrow\right)}$。每一个顶点有五个状态$c_{j}k_{j}=\left\{11, 1-1, 01, 00, 0-1\right\}$。初始时刻，所有顶点的状态都是未检测也无从推断$p\left(0_{j}0_{j},t\right)=1$。在检测过程中，对于确定性模型，任意一个顶点的状态也是以上五个状态之一。对于随机模型，我们有顶点处于状态$c_{j}k_{j}$的几率为
$$p\left(c_{j}k_{j}, t\right).$$
对于给定的顶点$j$，这些概率对$ck$的取和归一。同时，前面两个状态的取值只能是$0,1$，也就是，
$$p\left(1_{j}k_{j}, t\right) = 1,0.$$

由于由这些概率的特殊取值，为了更好地描述后面的动力学过程，我们定义一套新的状态变量。定义一个离散变量$\xi_{j}$和两个连续变量$\eta^{\left(1\right)}_{j}, \eta^{\left(-1\right)}_{j}$更加合适。描述变量采用$\xi_{j}=\pm 1, 0$, $\eta^{\left(\pm1\right)}_{j} \in \left[0, \infty\right]$。$\xi_{j}=1$表示$1_{j}1_{j}$态，$\xi_{j}=-1$表示$1_{j}-1_{j}$态，$\xi_{j}=0$的时候，看$\eta^{\left(\pm1\right)}_{j}$。这个时候推断状态的几率分别是
$$\begin{align} q^{\left(01\right)}=p\left(0_{j}1_{j},t\right) = \frac{\eta^{\left(1\right)}_{j} \left(t\right) – \eta^{\left(-1\right)}_{j} \left(t\right)}{\eta^{\left(1\right)}_{j} \left(t\right) + \eta^{\left(-1\right)}_{j} \left(t\right)}\theta\left(\eta^{\left(1\right)}_{j} \left(t\right) – \eta^{\left(-1\right)}_{j} \left(t\right)\right) \notag \\ p\left(0_{j}0_{j},t\right) = 1-\frac{\left|\eta^{\left(1\right)}_{j} \left(t\right) – \eta^{\left(-1\right)}_{j} \left(t\right)\right|}{\eta^{\left(1\right)}_{j} \left(t\right) + \eta^{\left(-1\right)}_{j} \left(t\right)} \notag \\ q^{\left(0-1\right)}=p\left(0_{j}-1_{j},t\right) = \frac{\eta^{\left(-1\right)}_{j} \left(t\right) – \eta^{\left(1\right)}_{j} \left(t\right)}{\eta^{\left(1\right)}_{j} \left(t\right) + \eta^{\left(-1\right)}_{j} \left(t\right)}\theta\left(\eta^{\left(-1\right)}_{j} \left(t\right) – \eta^{\left(1\right)}_{j} \left(t\right)\right) \end{align}$$
按照这样的状态标记，我们取每一个顶点的状态变量为：$\xi_{j}, \eta^{\left(1\right)}_{j}, \eta^{\left(-1\right)}_{j}$。实际上，我们看到，系统的状态当$\xi_{j}=\pm 1$的时候很简单（就是$1_{j}1_{j},1_{j}-1_{j}$态）。当$\xi_{j}=0$的时候，系统在状态$c_{j}k_{j}=\left\{01, 00, 0-1\right\}$子空间上的概率矢量是，
$$\left[q^{\left(01\right)}, 1-q^{\left(01\right)}, 0\right]^{T},$$
或者
$$\left[0, 1-q^{\left(0-1\right)}, q^{\left(0-1\right)}\right]^{T}.$$
也就是说，状态变量$\xi_{j}$和$\eta^{\left(1\right)}_{j}, \eta^{\left(-1\right)}_{j}$仍然不是反映系统状态的最简单的表达方式（有信息没有被用到）。不过，暂时，我们就以这套状态变量为准：
$$\xi_{j},\eta^{\left(\pm 1\right)}_{j} \Longleftrightarrow p\left(c_{j}k_{j}\right).$$

现在，我们已经清楚了系统状态的描述$P$（每一个字都有一个状态分布函数，整体状态构成一个分布函数大矢量。这个矢量的具体写法可以采用直积或者直和，再说，现在用不着）和初始条件$P\left(0\right)$，我们来构造一个动力学过程$P\left(t-1\right)\rightarrow P\left(t\right)$。将来，我们要讨论这样的问题：在给定成本的情况下，如何让系统尽可能地达到某个预期状态，或者达到某个预期状态所需要的最少的成本。

我们先讨论动力学过程。每一步（记为$t$时刻），我们选择一个汉字$i$来检测是否被试认识。

1. 如果认识（不认识），则更新这个字的状态为$\xi_{i}=1$（$\xi_{i}=-1$）。
2. 然后，考察这个字的一级近邻。对于每一个一级近邻$j$按照如下方式更新其状态：
1. 如果$\xi_{j}=\pm 1$，停止更新$j$的状态
2. 否则（也就是$\xi_{j}=0$的时候），取$\eta^{\left(\pm 1\right)}_{j}$的当前值$\eta^{\left(\pm 1\right)}_{j}\left(t-1\right)$，按照$i$的状态来更新$j$的状态
1. 如果$\xi_{i}=1$，则

$$\begin{align} \eta^{\left(1\right)}_{j}\left(t\right) = \eta^{\left(1\right)}_{j}\left(t-1\right) + \omega^{\left(1\uparrow\right),i}_{j}+ \omega^{\left(1\downarrow\right),i}_{j} \end{align}$$

2. 如果$\xi_{i}=-1$，则

$$\begin{align} \eta^{\left(-1\right)}_{j}\left(t\right) = \eta^{\left(-1\right)}_{j}\left(t-1\right) + \omega^{\left(-1\uparrow\right),i}_{j}+ \omega^{\left(-1\downarrow\right),i}_{j} \end{align}$$

把以上的过程合起来，也就是

1. 对字$i$做检测以后，如果认识（不认识），则更新这个字的状态为$\xi_{i}=1$（$\xi_{i}=-1$）。
2. 然后，考察$i$这个字的一级近邻。对于每一个一级近邻$j$按照如下方式更新其状态：

$$\begin{align} \eta^{\left(\xi_{i}\right)}_{j}\left(t\right) = \eta^{\left(\xi_{i}\right)}_{j}\left(t-1\right) + \left(1+\xi_{j}\right)\left(1-\xi_{j}\right)\left[\left(\omega^{\left(\xi_{i}\uparrow\right),i}_{j}+ \omega^{\left(\xi_{i}\downarrow\right),i}_{j}\right)\right] \end{align}$$

必要的时候可以计算概率$p\left(c_{j}k_{j},t\right)$ 。这个过程描述了测得一个新的字是否认识以后在整个网络上的传播。上面的过程仅仅考虑传播一步，也就$i$的邻居们。一个更加复杂的模型可以考虑多步传播：也就是计算一级近邻的状态概率矢量之后，拿着这个更新了的矢量，再去计算二级近邻的状态矢量。

再来讨论目标。

现在，我们希望得到一个（有顺序的）检测的集合，或者一个按照检测结果实时自适应生成检测顺序的算法。这个算法或者集合要做到以下两个目标中的一个。

1. 给定检测成本$C=\sum_{j}c_{j}$的情况下，最大化以下的目标函数的检测顺序是什么：
   $$K=\sum_{j,c_{j}} \left|p\left(c_{j}1_{j}; C\right) – p\left(c_{j}-1_{j}; C\right)\right|$$
   最后的参数$C$表示$C$时刻，如果记每一次检测新的汉字算一个时间步的话。
2. 或者期望达到某个特定的$K_{aim}$，最小的$C$是多少，实现这样的最小$C$的检测顺序是什么。

用新的状态记号，目标函数可以写做
$$K=\sum_{j} \left(\frac{\left|\eta^{\left(1\right)}_{j}-\eta^{\left(-1\right)}_{j}\right|}{\eta^{\left(1\right)}_{j}+\eta^{\left(-1\right)}_{j}}\right).$$
注意，当$\xi_{j}=\pm 1$的时候，我们强行更新了$\eta^{\pm 1}_{j}$来把前者的信息转入到后者之中，于是，这个目标函数的定义看起来简单一些。

在这个语言下，问题成了：给定一个检测顺序，或者一个检测顺序的自适应算法，整个问题就是一个Markov链，然后这个链需要满足上面两个目标之一的话，怎么办？

当然，不用这个整体系统状态的语言，就是问什么样的集合的选择或者顺序的选择，或者生成顺序的算法的选择，能够保证用最少的检测次数，了解最多的汉字是否被认得。

对于简化模型——关系矩阵$\Omega$的元素就是$0,1$的情况，相当于讨论一个双态的支配集问题：两个状态可以在有向无权网络上传播一步，问某种意义上最小的需要检测出来确定状态的集合是什么。当然，可以预见，这个最小集合会和每一次检测的结果有关系：极端情况，假设每次检测结果都是$1$的最小集合，和每次检测结果都是$-1$的，肯定是不一样的。因此，这个问题，不是单纯的两个单状态支配集问题的相加。

换一个角度来看，在简化模型的情况下，这个问题是双关系网络（同一套顶点，有两种不同状态——$\pm 1$——的可以在各自的网络上传播$\Omega^{\pm 1}$）上的支配集问题。整体目标把两种状态混合了起来，于是就不再是两个单关系网络的相加了。有了这个检测问题的实际问题的背景，提出并解决这个“双关系网络上的支配集问题”，是有一般意义的。在更加一般的关系矩阵$\Omega$取值的条件下，这个问题相当于把双关系网络上的确定性支配集问题，变成了双关系网络上的概率性支配集问题。

简单的算法：暴力搜索，把大量的检测顺序都试一遍，中间可以考虑采用自加强机器学习等人工智能算法（缺陷，计算量大）；或者采用贪心算法，每一步尝试检测一个汉字，然后选择对于目标函数提升最大的汉字做为检测对象（缺陷，不一定是好的顺序，忽略了长程连接）。

有更好的算法吗？

两个注：

1. 可以考虑给每一个顶点增加一个初始信息：在未被检测的时候的可能被认识的概率。初始时刻$\xi_{j}=0, \omega^{\pm 1}_{j}=0$，或者$\xi_{j}=0, \omega^{\pm 1}_{j}=\omega^{\pm 1}_{j,0}$。当然，这个初始权重$\omega^{\pm 1}_{j,0}$如何赋值就引入了这个问题的另外一个变量——目标检测人群的典型识字情形。
2. 直接共认矩阵和总共认矩阵：先从数学上来说，给定一个两个字的直接共认矩阵——也就是结构联系，是否可以以及如何计算出来两个字的最终共认矩阵？然后，问实际上，如果我们来测量的话，得到的共认概率矩阵，是直接呢还是间接呢？这个问题的讨论见新帖：从共现到结构。