从共现到结构

考虑一个概念网络,其中的顶点是概念,连边是概念之间的逻辑关系。假设连边的存在就保证了两个连在一起的概念以一定的概率共现。于是,我们得到结构矩阵(\Omega)。

定义总和关系矩阵(\Sigma),
\begin{align}
\Sigma = \Omega + \Omega^{2}+\cdots = \frac{1}{1-\Omega} – 1.
\end{align}
于是,
\begin{align}
\Omega = 1-\frac{1}{1+\Sigma}.
\end{align}

然后,我们考虑以下的问题:如果这个网络没有提供给我们,但是,我们获得了一个来自于实证数据的共现矩阵,那么这个共现矩阵就是(\Omega)还是(\Sigma)?

换一种具体过程的语言:假设有一个传染病直接接触传播网络(\Omega),然后,我们同样定义总和接触传播网络(\Sigma),问从实际传染过程可以测得一个同时发病矩阵,这个矩阵是是(\Omega)还是(\Sigma)?

类似的问题还可以是:概念(汉字)之间的内在联系导致的同时被理解和学习——结构矩阵,和,概念(汉字)之间表现出来的可以直接检测出来的同时被认识理解——同识矩阵,之间的关系;pacs代码之间的表现出来的可观察的共现——共现矩阵,和,pacs代码所代表的领域和主题之间的逻辑关系——结构矩阵;英文(或者中文)词之间表观共现和内在逻辑关系。

假如,这个矩阵是(\Sigma),那么,我们就有了一个从观测共现矩阵来计算直接结构矩阵(\Omega)的方法。

可能的应用情景:

  1. 找一个汉字在同一句话里面共现的矩阵,尝试一下,看看算出来的直接共现,是不是代表了意义上的联系。
  2. 找一个汉字同被认的矩阵,尝试一下,看看算出来的直接被认,是不是代表了汉字结构和意义上的联系。
  3. 找一个物理概念同被认的矩阵——例如通过调查问卷来访问被试是否听说过某个概念或者同时在一遍文献中出现,尝试一下,看看算出来的直接被认,是不是代表了物理概念意义上的联系。如果这个能够做成功——需要对比同被认或者共现矩阵给出的信息和处理以后的直接关系矩阵给出的信息,例如集团结构,成功指后者跟概念逻辑关系有很好的联系,那么相当于我们能够从文献中概念的共现或者普通人对概念的同认之中,提取出来概念之间的逻辑关系
  4. 模拟一个传染病传播过程,计算出来任意两点之间的同染病几率,然后计算这个直接联系矩阵,看看是不是反映网络连接。
  5. 找股票关联性的矩阵,尝试一下,看看算出来的直接关系,是不是代表了股票之间的某种有意义的联系。

一个问题:
有的时候,需要计算出来(\Omega^2)以后删除对角元素,然后再计算(\Omega \left(\Omega^2-D_{\Omega^2}\right)),也就是重复剔除自己到自己的传递效益。
[\Sigma=\left(\Omega-D_{1}\right) + \left(\left(\Omega-D_{1}\right)^2-D_{2}\right) + \left(\left(\Omega-D_{1}\right)\left(\left(\Omega-D_{1}\right)^2-D_{2}\right)-D_{3}\right) + \cdots,]
其中,(D_{j})是对第(j)项的简写记号。这个计算有没有简单的实现方式?例如,是否还能够表述成为某种取和形式。反过来,从(\Sigma)计算(\Omega)的时候那些对角元素的如何剔除?是不是一定条件下,当(\Sigma)没有对角元的时候,(\Omega)自然就不会有对角元?原则上,如果求出来的(\Omega)非负就确实是这样的。什么条件下(\Omega)非负呢?

参考文献:小思找出来一篇用同样的思路和方法来讨论同样的问题的文章——Network deconvolution as a general method to distinguish direct dependencies in networks。这个工作讨论了如何从观察到的网络连接矩阵(\Sigma)得到直接关系矩阵(\Omega),问题和公式都是一样的。不过,文章仅仅考虑了能够对角化的矩阵。具体计算的例子用了几个实际网络和几个编出来的网络。在具体系统的应用价值上,在更一般的矩阵的计算上,在对角元的处理上,还是有值得进一步研究的地方。如果要做,做一下这个文章的跟踪,然后,选择上面的一个具体应用问题,再解决一下对角元去掉的问题,还是很有意思的。

一个进一步的问题的解释:为什么(在什么情形下)需要剔除对角元?

考虑一个传染病传播的问题,我们可以分步来考虑。
一步就能传染上的
[p\left(1_{j}, t+1|1_{i},t\right) = p\left(1_{j}|1_{i}\right) =\Omega^{i}{j}]
两步就能传染上的
\begin{align}
p\left(1
{j}, t+2|1_{i},t\right) & = &\sum_{k} p\left(1_{j}, t+2|1_{k}, t+1\right) p\left(1_{k}, t+1|1_{i}, t\right) \notag \
& = & \sum_{k\neq i, j} p\left(1_{j}, t+2|1_{k}, t+1\right) p\left(1_{k}, t+1|1_{i}, t\right) \notag \
& + & p\left(1_{j}, t+2|1_{j}, t+1\right) p\left(1_{j}, t+1|1_{i}, t\right) \notag \
& + & p\left(1_{j}, t+2|1_{i}, t+1\right) p\left(1_{i}, t+1|1_{i}, t\right) \notag \
& = & \sum_{k\neq i, j} \Omega^{k}{j}\Omega^{i}{k} + \Omega^{j}{j}\Omega^{i}{j} + \Omega^{i}{j}\Omega^{i}{i}
\end{align}
以及其他更多步的计算。

如果这个计算直接求和,我们就得到上面的(\Sigma)计算(\Omega)的公式。

但是,我们看到,如果中间某一步出现了对角元(p\left(1_{j}|1_{j}\right)\neq 0),那么,我们得到的第二步之中就包含了第一步的贡献,而且这个贡献不是简单地把第一步的概率包含进来,也就是重复计算——除非出现了(j)顶点被治愈之后再次通过周围顶点的传染而得病,然后再一次感染周围其他顶点的情况(也就是说,是否要去掉对角元,还需要具体问题具体分析)。于是,对角元部分在某些情况下要每次矩阵相乘之后都去掉。

有两种定义矩阵(\Omega)对角元的办法,取做(1),或者取做(0)。我们先来看前者。
\begin{align}
p\left(1_{j}, t+2|1_{i},t\right) = \sum_{k\neq i, j} \Omega^{k}{j}\Omega^{i}{k} + \Omega^{j}{j}\Omega^{i}{j} + \Omega^{i}{j}\Omega^{i}{i} = \sum_{k\neq i, j} \Omega^{k}{j}\Omega^{i}{k} + \Omega^{i}{j} + \Omega^{i}{j}.
\end{align}
出现了两次(\Omega^{i}{j}),不能简单看做“对角元是(1)的(\Omega)矩阵的平方等于对角元是(0)的(\Omega)矩阵的平方加上(\Omega)矩阵”。再来看对角元等于(0)的形式,
\begin{align}
p\left(1
{j}, t+2|1_{i},t\right) = \sum_{k\neq i, j} \Omega^{k}{j}\Omega^{i}{k} + \Omega^{j}{j}\Omega^{i}{j} + \Omega^{i}{j}\Omega^{i}{i} = \sum_{k\neq i, j} \Omega^{k}{j}\Omega^{i}{k}.
\end{align}
因此,计算总和概率的时候,还需要把( \Omega^{i}_{j})再加回去。

同样的情况会出现在更高阶的概率——它们也要通过矩阵相乘来计算——上。于是,不管哪一种对角元取值方式,如何不重复计算对角元的贡献,又能够把各阶概率相叠加,是一个非平庸的技术问题。

当然,如果我们有这样的计算上的结果,那么这个问题也就成了一个简单的问题:任何一个能够表达成(\Sigma=\Omega + \Omega^2 + \cdots )(其中(\Omega)的元素非负)并且不含有对角元的(\Sigma),通过计算(\Omega = 1-\frac{1}{1+\Sigma})得到的(\Omega)必然也不含有对角元。道理上来说是对的,因为(\Omega)的元素非负,因此只有某一项出现了对角元,这个对角元肯定会被待到最后的(\Sigma)中。用具体例子算出来看看。不是随便找一个(\Simga)都满足这样的要求的。

在传染病上的应用

现在我们把上面的从共现到结构的一般框架用来讨论传染病问题,企图从观测到的同病数据来得到个体之间的感染概率,并且进而得到底层网络。考虑到对角元的问题,我们先讨论有向无环网络。

先来看从(\Omega)到(\Sigma)的思路。为简单计,所有个体之间的传染概率,只要相互接触,就是(p)。考虑一个有向无环图1->2->3。于是,
\begin{align}
\Omega = \left[\begin{array}0 & p & 0 \ 0 & 0 & p \0 & 0 & 0\end{array}\right]
\end{align}
代表一步就能传播到其他顶点的概率。接着,两步的传染概率就是
\begin{align}
\Omega^{2} = \left[\begin{array}0 & 0 & p^2 \ 0 & 0 & 0 \0 & 0 & 0\end{array}\right].
\end{align}
三步以及以上都是(0)。因此,
\begin{align}
\Sigma = \left[\begin{array}0 & p & p^2 \ 0 & 0 & p \0 & 0 & 0\end{array}\right],
\end{align}
非常简单。

现在我们看看从什么样的实际数据中,可以得到这样的(\Sigma)。一旦找到了这样的实际系统,也就是得到了(\Sigma)的实证数据值,那么,(\Omega)也就得到了。这个就是反过来从(\Sigma)得到(\Omega)的思路。

(\Omega)的元素是
\begin{align}
\Omega^{i}{j} = p\left(I{j}|I_{i}\right) = \frac{p\left(I_{i},I_{j}\right)}{p\left(I_{i}\right)},
\end{align}
于是,我们猜测,只要从实际传播过过程中获得大量样本,然后计算这个样本里面的(\frac{p\left(I_{i},I_{j}\right)}{p\left(I_{i}\right)}),自然就包含了上面的直接效果(\Omega^{i}_{j})和间接效果。

下面,我们来验证一下这个猜想。我们把这个三顶点有向无环网络上的传染病传播分解成几种情形:初始没有染病顶点的情况(1种),初始染病顶点仅仅只有一个的情况(3种),初始两个的情况(3种),以及初始三个的情况(1种)。

《从共现到结构》有一个想法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注