第七章两条记录,四种情况
第六章的签只有两栏,一栏写删前,一栏写删后。只有一条记录可以删的时候,这就够了,做最大耦合就行。
可是助手记着的不止一条。还是那个周六:助手记着记录 A“周六要去看电影”,也记着记录 B“不喜欢太吵的地方”。A 是记错了的;B 呢,你后来可能改了主意。两条都可以单独删掉,先删哪条随你。
于是“还保留着哪些记录”一共有四种情况:两条都在,只剩电影,只剩怕吵,两条都删了。我们用花括号写出还保留的记录,分别记作 、、 和 。最后这个符号读作“空集”,表示这两条记录都不在了。助手别的信息都还在,比如聊过的话、别的记忆,没了的只是这两条。
只差一条记录的两种情况,我们叫它们相邻,比如“两条都在”和“只剩电影”。从一种情况删掉一条记录,就走到和它相邻的另一种情况。
从两条都在走到两条都删,有两条路线:先删电影再删怕吵,或者先删怕吵再删电影。两条路线的终点是同一种情况,剩下的信息一模一样。我们自然希望,不管走哪条路线,最后看到的回答都一样。
分布一样,还不够
终点的分布只有一个,就是两条都删以后,只拿剩下的信息从头再问一次助手时的那个签盒。这一点不成问题。可是分布一样,不等于实际的回答一样。两个人从同一个签盒里各摸一张签,摸到的可能一张是公园、一张是图书馆。如果两条路线走到终点时各自重新抽一次,实际的回答仍然可能不同。
所以我们给自己加了一个更强的要求:先为四种情况一起抽一次签。签上有四栏,每栏写好一种情况下的回答。以后不管沿哪条路线走,走到哪种情况,就读哪一栏。终点是同一栏,读到的自然是同一个回答。
瀚林撕了一张纸条,画成四格,写好以后举起来给我们看:
| 两条都在 | 只剩电影 | 只剩怕吵 | 两条都删 |
|---|---|---|---|
| 电影院 | 电影院 | 公园 | 公园 |
“先删哪条都行。”瀚林点了点最后一格,“最后都读这儿。”
先删电影,读到的依次是电影院、公园、公园;先删怕吵,依次是电影院、电影院、公园。两条路线中间读的格子不同,最后读的是同一格。
这样一张为每种情况都写好去处的四栏签,我们叫它答案单。助手手里有许多种答案单,每次按一定的机会抽出一张。所有可能的答案单,连同各自被抽中的机会,合起来就是一个四栏的联合分布。
这样做并不需要预先知道你会按什么顺序删记录,答案单上已经为所有可能走到的情况都写好了回答。每次重新抽签,结果可以不同,可是在同一张答案单上,回到同一种情况,读到的一定是同一个回答。
这个要求是我们自己定的,后来在论文里叫它顺序无关:最后读到的回答,只取决于最后还剩哪些记录,和删除的先后顺序无关。这样一来,我们要找的就是答案单的一种抽法。
多发一条记录,再把它撤回,就是从一种情况走到相邻的情况,再走回来。回到原来那种情况,读的还是原来那一栏,回答和发出之前一模一样。第三章说过,机器上的删除可以比人彻底,像那条记录从来没有过;在答案单上就真是这样。
点和线
韵吉和祺乐讨论的时候,祺乐在草稿纸上写了四个花括号, 在最上面, 在最下面,把只差一条记录的两两连起来。韵吉把纸转了四十五度,看了一眼:“正方形?”
祺乐拿笔沿着四条线描了一圈:“你看,绕一圈能回到原处。”
画到这一步,电影、怕吵这些名字都可以去掉了,剩下的是四个点和四条线。
数学里说的图,就是一些点,加上点与点之间的一些连线。点叫顶点,线叫边。在我们的问题里,每个顶点代表一种保留情况,带着它自己的那张概率表,也就是这种情况的签盒;每条边代表一次删除,连着删除前后两种情况。
删除是有方向的,可是“两端的回答相不相同”不分方向,两张表的全变差距离也不分方向。所以在数学里,我们只用不带箭头的边。
用答案单的话说,我们要每一栏单独看都正好像那种情况自己的签盒,每走一步删除,答案单上换地方的机会都尽量小。换成数学的说法:
图上每个顶点有一张给定的概率表。找一个联合分布,也就是一种“每张签上给每个顶点写一个回答”的抽签方法,使得:每个顶点那一栏的边际分布正好是它自己的表;每条边两端那两栏不同的机会,尽量接近这条边两张表的全变差距离。
画成图以后,还要给“接近”定一个衡量办法,我们在第九章细说。韵吉把两人定下的这段数学说法写下来,交给 AI 检查,问它是否严谨。有了图,我们才能接着问图的形状会不会影响难度。
只有一条边的图,做最大耦合就完事了。如果图里有一个圈,比如刚才的正方形,事情还会这么简单吗?
不只是正方形
如果有 条记录可以分别删除,保留情况就有 种:每条记录都有“在”和“不在”两种可能。相差一条记录的两种情况之间连一条边,得到的图叫 维超立方体,这里的 就是记录的条数。我们在第二十二章会见到它。两条记录时它就是正方形,三条记录时是立方体的八个顶点和十二条棱。
祺乐又在正方形旁边画了一个三角形:“那这个呢?”
韵吉问:“哪三种情况互相都只差一条记录?”
我们找了一会儿,找不出来。“两条都在”的邻居是“只剩电影”和“只剩怕吵”,可这两种情况之间差了两条记录。第二十二章会说明,删记录得到的图里为什么一个三角形也没有。
不过,为了看清图的形状到底怎样影响难度,我们还是决定把问题放宽到任意的图:三角形、五边形、把每两个顶点都连起来的“完全图”,等等。三角形、五边形和三个顶点以上的完全图,都不能由删记录得到,讲到它们时我们只用顶点的编号。不过它们同样可以用来表示哪些情况两两之间需要协调。先在一般的图上把道理弄清楚,再回到删记录的那些图上来。