概念网络上的高效考试方式

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

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

我们认为,概念之间的逻辑关系,可以做为关联的客观表现。以汉字为例,汉字之间通过结构关系相互联系,这一点是客观的(尽管繁体字和简体字在汉字之间是如何从结构上联系起来的这一点上不一样。先考虑例如仅仅简体字)。例如:木——林——森,人——从——众,水——冰——淼,(木,一)——本,(人,本)——体。当然,这个客观的结构联系是否就能代表逻辑联系,是有待讨论的。也就是说,在汉字集合上,存在着一个逻辑关系网络,网络的每一条边代表上面举例中的一个字\(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\),则
      2. \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}

      3. 如果\(\xi_{i}=-1\),则
      4. \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\)按照如下方式更新其状态:
  3. \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. 直接共认矩阵和总共认矩阵:先从数学上来说,给定一个两个字的直接共认矩阵——也就是结构联系,是否可以以及如何计算出来两个字的最终共认矩阵?然后,问实际上,如果我们来测量的话,得到的共认概率矩阵,是直接呢还是间接呢?这个问题的讨论见新帖:从共现到结构

广义投入产出分析方法

考虑一个\(N\)各部门构成的封闭系统。由于数据可获得性,有的时候需要把例如第\(N\)个部门拿出来当成外界。这个时候,系统就成了开放系统。顺便,这个时候计算的时候可能用不到的数据就是部门\(N\)对其他部门的投入,或者其他部门对\(N\)部门的投入。还有的时候,这\(N\)个部门中,仅仅一小部分部门,例如\(M\)个部门,之间的投入产出数据是已知的,那么这个时候,如果这个子集所包含的部门和其他部门之间的交流比子集内部的交流少很多,那么这个子集就是我们的\(M\)部门的封闭系统研究对象。如果联系还挺多,还能获得这个\(M\)个部门到其他部门的投入产出以及其他部门到这\(M\)个部门的投入产出,那就把其他部门合起来当作一个部门。如果仅仅前者或者后者能够获得,则要用开放系统的分析方法。

本文介绍这样的\(N\)部门系统的投入产出分析技术。在这里,我们假设这个\(N\)部门之间的投入产出数据是完全已知的。在假设技术——生产方式——不发生变化的前提下,投入产出技术回答以下的典型问题:

  1. 如果某个部门,例如第\(N\)部门,增加了对其他某个\(j\)部门的投入或者需求——需求的意思就是反过来\(j\)部门到\(N\)部门的投入,整个系统的各个部门的产出会发生什么变化
  2. 各个部门对整体系统的重要程度或者说有影响力
  3. \(j\)部门对其他各个部门的影响力

具体问题在各个技术还会展开说明,但是,以下的分析技术,不管是开放系统还是封闭系统的,是不是就能用来回答所感兴趣的研究问题,就是另外一个问题了。

定义
\(N\)封闭系统各个部门之间的投入产出关系有以下矩阵代表
\[x = \left(x^{i}_{j}\right)_{N\times N},\]
其中\(x^{i}_{j}\)表示部门\(i\)到部门\(j\)的投入。上下指标的区别很重要,上角标是出来的部门,下角标是到达的部门。

定义部门\(i\)的总投入量\(X_i\)和总产出量\(X^i\),
\[X^{i} = \sum_{j}x^{i}_{j}, X_{i} = \sum_{j}x^{j}_{i}.\]

定义矩阵\(B\)如下,
\[B^{i}_{j} = \frac{x^{i}_{j}}{X^{j}}.\]

定义矩阵\(F\)如下,
\[F^{i}_{j} = \frac{x^{i}_{j}}{X_{i}}.\]

定义矩阵\(MB\)如下,
\[MB^{i}_{j} = \frac{x^{i}_{j}}{X^{i}}.\]

定义矩阵\(MF\)如下,
\[MF^{i}_{j} = \frac{x^{i}_{j}}{X_{j}}.\]

先来形式上证明这几个矩阵的本征向量之间的关系,记\(B\)的左右本征矢量分别是\(\left\langle \lambda_{B} \right|\)和\(\left| \lambda_{B} \right\rangle\),类似地定义其他矩阵的本征矢量。我们有,
\begin{align}
\left\langle \lambda_{B} \right| B = \lambda_{B} \left\langle \lambda_{B} \right| \notag \\
\Rightarrow \lambda_{B} \left\langle \lambda_{B} \right| \left. i \right\rangle = \sum_{j} \left\langle \lambda_{B} \right| \left. j \right\rangle \left\langle j \right| B | \left. i \right\rangle = \sum_{j} \left\langle \lambda_{B} \right| \left. j \right\rangle B^{j}_{i} \notag \\
\Rightarrow \lambda_{B} \left\langle \lambda_{B} \right| \left. i \right\rangle = \sum_{j} \left\langle \lambda_{B} \right| \left. j \right\rangle \frac{x^{j}_{i}}{X^{i}} = \sum_{j} \left\langle \lambda_{B} \right| \left. j \right\rangle \frac{x^{j}_{i}}{X^{j}}\frac{X^{j}}{X^{i}} \notag \\
\Rightarrow \lambda_{B} \left\langle \lambda_{B} \right| \left. i \right\rangle X^{i}=\sum_{j} \left\langle \lambda_{B} \right| \left. j \right\rangle X^{j} \frac{x^{j}_{i}}{X^{j}}.
\Rightarrow \lambda_{B} \left\langle \lambda_{B} \right| \left. i \right\rangle X^{i}=\sum_{j} \left\langle \lambda_{B} \right| \left. j \right\rangle X^{j} MB^{j}_{i}.
\end{align}
于是,我们发现\(\left\langle \lambda_{B} \right| \left. i \right\rangle X^{i}\)是矩阵\(MB\)的左本征向量\(\left\langle \lambda_{MB} \right|\)的\(i\)分量。类似地,\(B\)和\(MB\)的右本征矢量也存在类似地关系。同理,\(F\)和\(MF\)之间也存在一样的关系。

同时,我们还注意到\(B\)的最大右本征矢量,就是对应着最大本征值的右本征矢量,是平庸的。本征值是\(1\),本征向量是\(X^{a} = \left(X^{1}, X^{2}, \cdots, X^{N}\right)^{T}\),
\begin{align}
\sum_{j} B^{i}_{j} X^{j} = \sum_{j} \frac{x^{i}_{j}}{X^{j}}X^{j} = X^{i}.
\end{align}
当然,通过上面的两个矩阵的本征矢量的一般关系,我们可以得到\(MB\)矩阵的最大右本征向量也是平庸的,就是\(\left(1, 1, \cdots, 1\right)^{T}\)。同理,\(F\)和\(MF\)的最大右本征向量也是平庸的。

因此,当\(X^{i}=X^{i}\)的时候,矩阵\(B\)在数值上等同于矩阵\(MF\),于是这个时候,最大左右本征矢量都是平庸的。仅当
\[X^{i}\neq X^{i}\]
的时候,\(B\)和\(MB\)的最大左本征向量,\(F\)和\(MF\)的最大右本征向量会有独立于总量\(X^{a}\)以及\(X_{a}\)的含义。因此,当原始矩阵\(x^{i}_{j}\)对称的时候(这时候,\(X^{i}=X^{i}\)),这些所有后来定义的矩阵的本征矢量都没有独立于总量\(X^{a}\)以及\(X_{a}\)的含义。更一般地,我们称满足\(X^{i}=X^{i}\)的系统为投入产出守恒的系统,或者简称守恒系统。守恒系统所有最大本征向量平庸是一个很重要的事实。

传统开放系统投入产出

这一节,我们问这样的问题:第\(N\)部门,增加了对其他某个\(j\)部门的需求,整个系统的各个部门的产出会发生什么变化。有了这个技术,可以回答类似地回答第\(N\)部门增加了对其他某个\(j\)部门的投入,整个系统的各个部门的产出会发生什么变化的问题,就需要用\(F\)矩阵。

我们从\(X^{i}\)的定义开始,
\begin{align}
X^i=\sum^{N-1}_{j=1}x^{i}_{j}+x^i_{N} = \sum^{N-1}_{j=1} x^{i}_{j}+Y^i = \sum^{N-1}_{j=1}\frac{x^i_j}{X^{j}}X^{j}+Y^i \notag \\
\Rightarrow X^{\left(-N\right)} = B^{\left(-N\right)}X + Y^{\left(-N\right)} \notag \\
\Rightarrow X^{\left(-N\right)} = \left(1-B^{\left(-N\right)}\right)^{-1} Y^{\left(-N\right)} \\
\Rightarrow \Delta X^{\left(-N\right)} = \left(1-B^{\left(-N\right)}\right)^{-1} \Delta Y^{\left(-N\right)} = L^{\left(-N\right)}_{B} \Delta Y^{\left(-N\right)}
\end{align}
其中,\(\Delta Y\)可以是\(e^{j}= \left(0, \cdots, 1, 0, \cdots, 0\right)\)这样的单位矢量,表示部门\(N\)仅仅对部门\(j\)增加了需求。\(Y^i=x^{i}_{N}\)是部门\(N\)对部门\(i\)的需求量。这里上角标\(^{\left(-N\right)}\)表示矩阵或者向量中去掉部门\(N\)的相关元素。

类似的,从矩阵\(F\)我们可以有
\begin{align}
X_i=\sum^{N-1}_{j=1}x^{j}_{i}+x^{N}_{i} = \sum^{N-1}_{j=1} x^{j}_{i}+V_i = \sum^{N-1}_{j=1}\frac{x^{j}_{i}}{X_{j}}X_{j}+V_i \notag \\
\Rightarrow X^{\left(-N\right)} = XF^{\left(-N\right)} + V^{\left(-N\right)} \notag \\
\Rightarrow X^{\left(-N\right)} = V\left(1-F^{\left(-N\right)}\right)^{-1} \\
\Rightarrow \Delta X^{\left(-N\right)} = \Delta V^{\left(-N\right)} \left(1-F^{\left(-N\right)}\right)^{-1} = \Delta V^{\left(-N\right)} L^{\left(-N\right)}_{F}
\end{align}
注意,这里分量为\(X^{j}\)的矢量和分量为\(X_{j}\)的矢量不一样,前者放在矩阵右边,后者左边。习惯上,我们称前者为列矢量,后者为行矢量。物理上有两种方法对这样的矢量作区分,记作\(X^{a}\)和\(X_{a}\),或者记作\(\left| X \right\rangle\)和\(\left\langle X \right|\)。前者的记号来自于Einstein,后者来自于Dirac。这个记号非常方便。我们下面会采用这两套记号。

有了这个逆矩阵\(L^{\left(-N\right)}_{B}\)(\(L^{\left(-N\right)}_{F}\))之后,我们就可以通过计算第\(j\)个列和(行和)来回答前面提出的问题了。

传统开放系统投入产出HEM

Hypothetical Extraction Method (HEM)的意思是假想地从系统中去掉一个部门,然后看一看,在这个新的系统中,如果我们还要实现同样的需求(或者提供同样的投入,针对\(F\)),各个部门的总产出的变化。具体计算如下。

定义\(L^{\left(-N-j\right)}_{B}\),
\begin{align}
L^{\left(-N-j\right)}_{B} = \left(1-B^{\left(-N-j\right)}\right)^{-1}.
\end{align}
然后,比较\(L^{\left(-N-j\right)}_{B}\)和\(L^{\left(-N\right)}_{B}\),例如
\begin{align}
L^{\left(-N-j\right)}_{B} Y^{\left(-j\right)}, \left(L^{\left(-N\right)}_{B} Y\right)^{\left(-j\right)}.
\end{align}
后者表示计算完成之后再去掉元素\(j\)。当然,为了提供一个数字来相互比较,当\(X\)矢量的每一个元素可以相加(不一定可以,需要统一的单位)的时候,我们还可以计算上面两个矢量的和来相比。直觉上,我们可以认为,如果这个差别非常大,那么去掉这个部门\(j\)的影响很大,于是回答了一开始的部门对系统整体影响力的问题。相互影响的问题也可以通过考察这个差别矢量来讨论。

实际计算矩阵逆的时候,可以考虑用迭代方法:下面这个方程的不动点和上面的求逆是一样的。
\begin{align}
X^{\left(-j\right)}\left(m+1\right)= B^{\left(-N-j\right)} X^{\left(-j\right)}\left(m\right) + Y^{\left(-j\right)}
\end{align}
其中\(m\)是迭代次数,初始条件可以取\(X\left(0\right)=\left(1, \cdots, 1\right)^{T}\)。更高效的计算可以运用Dyson方程。

\(F\)的问题可以做类似分析。

目标外界投入产出HEM

以上两个分析方法,主动或者被迫,先把封闭系统看作开放系统——把部门\(N\)独立出来,然后再来分析。在经济学中,部门\(N\)是最终消费者,独立出来有很好的理由。其到产业系统的投入\(V\)非常不容易跟踪。其内部的再生产时间也远远比产业系统的再生产时间长。在大量的其他系统中,这样的分隔可能是不合适的。我们已经看到,经过这个分隔,实际上,我们讨论了部门\(N\)对部门\(i\)增加一个需求或者投入所带来的效果。现在,我们对任意一个部门\(k\)来运用这个分析。我们相当于问这样的问题:如果部门\(k\)增加了对某一个部门\(j\)的需求或者投入,在不改变系统结构的情况下,各个部门的总产出会如何变化。和传统HEM相比,我们发现:传统HEM实际上是,不仅仅增加或者减少\(k\)部门对\(j\)部门的需求或者投入,还不允许部门\(k\)出现在产业系统中,会发生什么。也就是说,传统HEM是结构性重要性,我们是外源性(增加需求或者投入)重要性。具体计算如下。

定义\(L^{\left(-k\right)}_{B}\),
\begin{align}
L^{\left(-k\right)}_{B} = \left(1-B^{\left(-k\right)}\right)^{-1}.
\end{align}
这个矩阵的列和代表了如果部门\(k\)增加了对某一个部门\(j\)的需求,在不改变系统结构的情况下,各个部门的产出之和(在能够取和的情况下,否则就只好直接分析得到的列向量了)。我们把这个和记作\(Z^{k}_{j} = \sum_{l} \left(L^{\left(-k\right)}_{B}\right)_{jl}\)。于是,从这个矩阵,我们可以得到一个新的影响力矩阵
\begin{align}
Z_{B} = \left(Z^{k}_{j}\right)_{N\times N}.
\end{align}
得到这个矩阵之后的分析,还有待于进一步研究。

\(F\)的问题可以做类似的分析。

本征向量HEM

上面的目标外界HEM方法回答了某个部门\(k\)增加(或者减少)一个单位的对\(j\)部门的投入(或者需求)在整个系统内传播的效果。现在,还是封闭系统,我们来讨论另外一个分析方法——本征向量HEM。

对于封闭系统,矩阵\(B\)的右本征矢量定义是
\begin{align}
B \left| 1 \right\rangle_{B} = \left| 1 \right\rangle_{B},
\end{align}
其元素是
\begin{align}
\left| 1 \right\rangle_{B} = \left(X^{1}, X^{2}, \cdots, X^{N}\right)^{T}.
\end{align}
这个很容易验证。因此,这个矢量就是由各个部门总产出构成的,平庸的,不用通过计算本征向量来获得。顺便,这个矩阵的左本征矢量,
\begin{align}
\left\langle 1 \right|_{B} B = \left\langle 1 \right|_{B},
\end{align}
可能是非平庸的。实际上,这个左本征矢量和下一节的PageRank矢量是有密切联系的。于是,这个右本征矢量看起来就不能给我们的进一步分析带来太多价值。真的是这样吗?

我们注意到这个右本征矢量的另外一个解释:如果我们按照这个比例来投入产业系统的话,所有的原材料都会被用掉,不会浪费;所有的生产所需要的原材料也会得到满足,不会缺。因此我们把这个组合称作最优组合。这个时候,我们来看以下的矩阵\(B^{\left(-k\right)}\)的最大本征值和相应的本征向量(假设本征矢量唯一,其存在性由Perron-Frobenius定理保证,唯一性需要矩阵非退化),
\begin{align}
B^{\left(-k\right)}\left| \lambda^{\left(-k\right)}_{Max} \right\rangle_{B^{\left(-k\right)}} = \lambda^{\left(-k\right)}_{Max} \left| \lambda^{\left(-k\right)}_{Max} \right\rangle_{B^{\left(-k\right)}}.
\end{align}
我们发现,最大本征向量基本上可以看做新的去掉部门\(k\)之后的系统的最优组合,而最大本征值则是这个组合的效率。于是,我们定义
\begin{align}
IOF^{k} = 1-\lambda^{\left(-k\right)}_{Max} ,
\end{align}
解释成\(k\)部门对系统整体的影响力(Input-Output Factor, IOF),而把向量\(\left| \lambda^{\left(-k\right)}_{Max} \right\rangle_{B^{\left(-k\right)}} \)的\(j\)元素看做\(k\)对\(j\)的影响(Input-Output Mutual Influences, IOMI),
\begin{align}
IOMI^{k}_{j} = \left\langle j \left| \right. \lambda^{\left(-k\right)}_{Max} \right\rangle_{B^{\left(-k\right)}} – \left\langle j \left| \right. 1 \right\rangle_{B}.
\end{align}

PagerRank和PageRank的HEM

上面的分析方法关注矩阵的最大右本征矢量,现在我们来关心矩阵的最大左本征矢量。除了对付完全随机跳跃的那部分,PageRank矢量实际上用了如下的本征矢量,
\begin{align}
\left\langle 1 \right|_{MB} MB = \left\langle 1 \right|_{MB}.
\end{align}
我们已经证明 \(\left\langle 1 \right|_{MB}\)和\(\left\langle 1 \right|_{B}\)一一对应,仅相差一个向量的元素乘积。这个就是PageRank。通过它,我们可以得到对部门重要性的一种排名。另外,我们还可以做一个这个本征矢量的HEM。定义如下。
\begin{align}
\left\langle \lambda^{\left(-k\right)}_{Max} \right|_{MB^{\left(-k\right)}} MB^{\left(-k\right)}= \lambda^{\left(-k\right)}_{Max} \left\langle \lambda^{\left(-k\right)}_{Max} \right|_{MB^{\left(-k\right)}}.
\end{align}
可以证明,这个本征值和上面基于\(B\)的定义是一样的(这个本征向量的含义还不太清楚)。或者下面的定义,
\begin{align}
\left\langle 1 \right|_{\hat{MB}^{\left(-k\right)}} \hat{MB}^{\left(-k\right)}= \left\langle 1 \right|_{\hat{MB}^{\left(-k\right)}}.
\end{align}
其中,\(\hat{MB}^{\left(-k\right)}\)是对矩阵\(MB^{\left(-k\right)}\)的重新回一化得到的概率转移矩阵。重新归一化以后最大本征值重新成了\(1\)。然后我们通过对比两个向量来反映\(k\)部门的重要性,例如,
\begin{align}
PRF^{k} = 1- \left\langle 1 \right|_{\hat{MB}^{\left(-k\right)}} \left(\left| 1 \right\rangle_{MB}\right)^{\left(-k\right)} .
\end{align}
最后的矢量\(\left(\left| 1 \right\rangle_{MB}\right)^{\left(-k\right)}\)就是从\(\left\langle 1 \right|_{MB}\)先去掉第\(k\)个元素,然后转化成右矢量得到的。
\begin{align}
PRMI^{k}_{j} = \left\langle 1 \right|_{\hat{MB}^{\left(-k\right)}} \left| j \right\rangle – \left\langle 1 \right|_{MB} \left| j \right\rangle .
\end{align}
这个分析方法的应用还有所反映的重要性的含义,还有待于进一步讨论。

系统生物学流平衡分析方法

原则上,上面的HEM方法可以考虑同时去掉多个的影响——其不一定等于单个的效果的相加——也就是出现了交叉项、相干项。

在化学反应网络的层次,一个部门牵涉到多个产出,产出的数量和部门的数量不一样。这个时候,需要把部门(也就是化学反应)和投入产出产品(反应物和生成物),分别拿出来处理。实际上,这个可以看做是一个特殊的二层网络。这个时候,广义投入产出理论需要张量这个数学工具。还需要考虑平衡态、最优态甚至流的再次分配问题来寻找最终的每个部门在扰动之后的流。在化学反应和系统生物学领域,这个理论,被叫做流平衡分析。

我们做了统一和发展(待续)。

多层网络上的广义投入产出
由于我们的投入产出分析允许\(X^{i} \neq X_{i}\),甚至\(X_{i}\)就不存在,我们就可以处理\(\sum_{j} x^{j}_{i}\)完全不能相加,没有统一单位和统一的意义,的情形。于是,对于多层网络问题,里面自然有多种不同性质的关系的时候,我们的广义投入产出就可以用来讨论这样的系统。

待续。

目前几个工作的总结

  1. 小思科学学的工作提出和运用了本征向量HEM
  2. 小勇的工作运用了传统HEM并且正在考察目标外界HEM
  3. 秦磊的工作考虑运用目标外界HEM
  4. 崔浩川城市的工作先运用本征向量HEM方法,将来再对比多个方法
  5. 小思方法对比的工作需要做各个方法的对比
  6. 李梦辉关于专利和文献合起来的领域相互影响的问题,考虑用封闭系统方法(本征向量HEM和目标外界HEM)
  7. 张江在贸易网络上的工作就相当于用了传统的当作开放系统的HEM(并且进一步讨论了体量和影响力的关系,以及这个关系的幂律指数的含义)
  8. 当作封闭系统的国家之间贸易网络的工作还没有人做
  9. Dyson方程的工作解决的是以上各个技术中计算简化的问题

边的PageRank值,多层网络传播问题、PageRank以及投入产出分析,还有PageRank k-core项目

最近,由于找到了科学学的三层网络数据关系数学模型:作者、文章、概念(主题),在思考如何利用这个数学模型来描述之前前人已经提出和解决的问题(这里就是换一个描述方式),提出还没有解决的问题(这里需要新的分析技术),以及新的问题(这里问题和技术都需要用好这个三层网络数学模型)。有了几个可以试试的想法。

第一,作者姓名识别、作者主领域识别是一个科学学的基础问题。大量后续研究依赖于这个问题的解决。通常的有首字母加上姓的简单粗暴识别方式,考虑合作关系,考虑引文关系,考虑机构名称,考虑主工作领域等多个方向,计算分析的技术也有多样。大多数在一个维度上做研究,例如考虑如何把合作关系用来改进简单粗暴识别,或者考虑多个维度,例如同时考虑合作者和引文关系,然后想办法把两个考虑的因素结合起来。这些分开维度又合起来的研究,基本上都是相当于把三层网络投影到其中的一层上来做分析,基本上没有直接在多层网络上作研究的。

现在,我们在三层网络模型的基础上提出来,先把每一篇文章的每一个作者(同时,也带着机构标记)看做独立的作者,然后通过在三层网络上的传播算法来计算作者的相似性的方式来合并作者。传播过程的理念当然还是:主题相近的姓名相近的科学家是同一个人的可能性比较高,合作者相近的姓名相近的科学家是同一个人的可能性比较高。这些理念都不奇怪。关键是,现在在这个三层网络上,通过文章的引用关系(也可以通过合作关系来传播主题,还可以跟之前的研究工作类似单纯地考虑合作者或者引用的效果而不是通过传播主题标记的方法)可以把作者的主题标记扩大和传播起来,然后可以通过主题的相似性来合并作者(当然,需要考虑姓名和机构)。

一石二鸟,也体现多层网络模型直接计算不投影的特点。至于是不是问题解决更好了,就看结果了。

第二,考虑间接效益的k-core定义。k-core相比较度k来说,好处就是一定程度上,通过迭代消去的过程,考虑了非局域信息,也就是间接效益。考虑到这个特点,我在思考把k-core的定义修改成不是依靠k的值来消去,而是依靠PageRank值(迭代的每一次都计算每个顶点的PageRank值,然后小于某个阈值的顶点都去掉)。具体来说,每一步计算,
[ p = p M]
其中(M)就是当前剩下的网络的邻接矩阵(W)对应的概率转移矩阵。然后,设定
[p^{*} = \frac{k_{c}}{\sum_{W}},]
其中(\sum_{W})是矩阵(W)的所有元素之和。

这个定义显然和k-core有联系,守恒网络((W^{i}=W_{i}))直接回到通常k-core定义——迭代删除总强度小于某个(k_{c})的顶点。但是,一般情况下,由于考虑了间接效益,应该是不一样的。因此,第一个这个方面的工作就可以是对比这两个k-core,然后,找一个动力学过程来和两个k-core的结果来对比,就像Stanley在nature physics的工作一样。顺便,Stanely的这个工作里面(M(k_{s}, k))图很有说服力。第二个这个方面的工作就是把通常的k-core和PR k-core推广到多层网络上去来解决具体问题。例如,讨论一下核心科学家、文章和概念的选择的问题。

第三,把单层网络的PageRank和投入产出分析推广到多层。由于投入产出分析不要求所流动的物质的一致性——我们区分了(X^{i})和(X_{i}),例如都是钱、能量、点击注意时间等,在多层网络上可能后者更加具有一般意义。

其中,多层网络PageRank的问题可以有两个层次:第一,把原来单层网络上的定义放到由边和顶点都成的等价的二部分图上来做同样的传播计算,看看是否得到的结果一致。如果一致,那么这个计算的额外好处就是得到了边的PR值。这个已经是有意义的结果。第二,把PageRank直接做在真的多层网络中,来解决多层网络中的多种个体的重要性度量的问题。这个问题从技术上和所回答的问题上,都和前一项关于k-core的研究有关。