什么东西驱动人们遵循和挑战社会约定

这两天想起来研究一下这个。找找学生,看看能不能初步开展一下。

Jinshan:
跟你聊一个研究想法:什么东西驱动人们遵循和挑战社会约定–以靠右侧行走为例。选择一个可以挑战右行约定但是,不被惩罚的。例如,操场上的那两个刷卡进入的门。例如,大马路上自行车和电动车的逆行。然后,通过调查问卷的方法来获取数据。

Jinshan:
问诸如这样的问题:1、你同意在这个情况下,还是遵循右行比较好,同意程度,1,0,-1。
2、你选择左行是因为:随便选的、右边排队呢、右边被另一测的左行人占着呢
3、你选择右行是因为:随便选的,遵循习惯,左边排队长,左边被另一个的左行人占着呢

Jinshan:
然后,我们发小礼物或者给一笔小钱。你觉得如何?

Aaron:
单就此事,做显然是没问题的。而且不难在短期内实现。

Jinshan:
我觉得还是有点意义。就是不知道其他人的相关工作

Aaron:
反惯例行为?初步找了一下文献,没看到特别对眼的。不过好的想法可以先通过调研开始,卡尼曼提出行为经济学第一篇science文章就是通过调研方式验证的。与此相关的,还有一种行为叫compliance,遵从行为,研究比较多。是指被法律或制度规定了的非法行为,但审查成本较高的行为,比如纳税遵从。纳税遵从除了有制度设计意义,最终会归结为纳税道德,因为后面是法律。

反惯例我觉得方差比较大,因为得看惯例是什么。往大了讲,挑战权威就是反惯例。往小了讲,左行也是反惯例。

同时,这和文化有关。在美国及有些国家,或许左就是左,右就是右,不能反惯例,老弱病残座位不会有人去坐。但在中国,则不然。

而且,反惯例的成本也因惯例是什么而不同。方差也比较大。

从共现到结构

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

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

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

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

我们认为,概念之间的逻辑关系,可以做为关联的客观表现。以汉字为例,汉字之间通过结构关系相互联系,这一点是客观的(尽管繁体字和简体字在汉字之间是如何从结构上联系起来的这一点上不一样。先考虑例如仅仅简体字)。例如:木——林——森,人——从——众,水——冰——淼,(木,一)——本,(人,本)——体。当然,这个客观的结构联系是否就能代表逻辑联系,是有待讨论的。也就是说,在汉字集合上,存在着一个逻辑关系网络,网络的每一条边代表上面举例中的一个字\(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. 直接共认矩阵和总共认矩阵:先从数学上来说,给定一个两个字的直接共认矩阵——也就是结构联系,是否可以以及如何计算出来两个字的最终共认矩阵?然后,问实际上,如果我们来测量的话,得到的共认概率矩阵,是直接呢还是间接呢?这个问题的讨论见新帖:从共现到结构

科研服务平台的设想

科学家之间的合作越来越普遍。如果促进合作让合作更方便呢?这里提出一个科研服务平台的设想,包含以下几个部分:综述论文整理点评和推荐系统、科研项目文档存储平台、科研众包平台。

综述论文整理点评系统,简称综述文摘,主要收集各个学科的有影响力的综述论文期刊的论文信息,并且,收集用户对这些论文的点评,然后供用户分类浏览这些信息,以及按照一定的方式做推荐。

科研项目文档存储平台,简称科研云盘,提供两项服务:文档存储空间和同步功能、文本文档的协作和版本控制。第一个功能主要实现单一用户在不同客户端上的文档同步。第二个功能主要实现多用户文档协作。

科研众包平台,简称科研众包,主要是提供科研项目里面几个关键点——问题、数据、分析技术、实现研究的人员条件和实现研究的物质条件——的信息分享促进合作。有的科学家有好问题,有的有数据,有的有时间,有的有技术,有这样一个平台来帮助科学家匹配有可能可以取得比依靠科学家个人的匹配更好的效果。

综述文摘项目只要做好综述文章的收集和整理——这个基本没难度,对研究者和学生来说,已经是有意义的事情。相当于综述文章统一门户。如果还能够提供评论的收集整理排序和分享——这个需要依靠草根用户,那就会有很大的促进作用。实际上,导师的作用,很大程度上就是一篇综述文献——对一个领域的更加全面和深入的了解。有了这个,遇到一个对学科认知不太全面和深入的导师,就不是个大问题。有好的导师,则能够相互补充。

科研云盘,一方面提供独立服务,解决每一个科研团队都需要自己来搭建文档协作平台的问题。另一方面,云盘上所存储的信息,可以做为众包平台的基础。同时,现在很多期刊要求数据公开,这个时候这个平台也可以是论文发表的时候所用的补充信息库。这个在技术上没有任何难度。信息加密存储也不是问题。

科研众包,则是想办法更好地发挥现有的科学研究资源。由于学科领域边界的限制,很多研究项目,不太可能完全依靠研究者的个人关系来寻找合作者。但是,这个平台基本上依赖于草根用户的参与。做好有难度。所以,最好通过前面的两个项目来获得人气,来把这个项目打包发展。

这样的纯粹公益性质的服务于一大群人的工作对于提升参与单位的声誉是非常有意义的。就好像Wikipedia还有arXiv,人人都可以收益。

训练学习机用来求解Schrodinger方程

机器学习最近实在是火。各个领域都在用和发展。据说神经网络可以拟合任意的函数。于是,我想起来一个神奇的主意:如果把从势函数求解基态波函数的过程看成一个映射(函数)的话,能不能用机器学习来得到一个这个映射的机器呢?这样,我们就可以用现在已经求解出来的Schrodinger方程的解来训练这个学习机,然后用训练出来的学习机来求解新的Schrodinger方程。我把这个问题叫做:Machine learning-based Schrodinger solver(机器学习Schrodinger方程求解器)。

问题的具体化:以一维量子系统的束缚态问题为例,离散化势函数,得到一个矢量。用数值求解方法得到这个系统的离散化的基态波函数,得到另一个矢量。把这样的输入矢量和输出矢量的对输入合适的学习机,训练学习机。检验这个学习机是否能够求解新的Schrodinger方程。

工作大致思路:如果我们仅仅考虑多项式形式的势函数的话,可以比较简单地得到输入矢量(各阶多项式的系数)。然后我们需要一个Schrodinger方程的数值求解器,在自然边界条件(无穷远处渐近为零)下,来得到训练集的输出矢量。接着需要找到合适的学习机来训练。最后,做检验和泛华。

实际意义:这个从势函数到波函数的映射不是线性的,因此,在数值求解的过程中,除非运用微扰论,已知的方程的解不能重用。也就是说,每一个问题需要数值求解一次微分方程或者转化成矩阵以后计算矩阵的最小本征值对应的本征向量。这样的矩阵通常维数是很高的。更一般地来说,如果学习机的表现能够重用已知的解或者能够降低计算的复杂度,那么,这样的方式可以用在其他的微分方程的求解上,甚至密度泛函理论(DFT)的有效波函数上,这样能够提升量子化学计算等这种需要大量计算多例子系统基态能量和波函数的计算任务的效率。

理论意义:这个所谓的映射实际上比较复杂——实际数值计算是求解这个输入的势函数对应的Schrodinger方程的基态解,那么,这么复杂的映射——不是简单地能够看做对输入的势函数矢量某种操作,还能够通过机器学习来得到吗?更加深刻的问题——实际上,这个方程还有其他激发态的解,如果也能得到的话,这里存在量子态的干涉(叠加)现象,难道机器学习连这个东西都能默默学下来。不过,这个问题暂时不讨论。

相似的问题(竟然已经有人在思考相似的问题):http://www.anl.gov/articles/machine-learning-algorithm-aims-accelerate-materials-discovery
http://www.ipam.ucla.edu/programs/long-programs/understanding-many-particle-systems-with-machine-learning