康威梯度:用可微规划反转生活

2020-05-07 19:54:42

现在,有一个魔术戏法。摆在你面前的是一块239乘200英寸的康威的“生活的游戏”(Game Of Life)棋盘:

如果我们从这个配置开始,然后执行游戏的一个步骤,会发生什么呢?以下是下一代的快照:

这个把戏是怎么用的?(这不是恶作剧-您可以使用此RLEfile在copy.sh/life上亲自尝试。)。

那么,让我们从它是怎么不起作用的开始吧。将生命形态性地反转--这是一门“掠夺”的艺术--是一个很难探索的问题,在这种规模上做这件事在计算上是不可行的。想象一下搜索($2^{239\times200}$)可能的配置!那肯定是无望的…。事实上,我链接的演讲分享了一些聪明的算法,尽管如此,它们仍然需要整整10分钟的时间才能为一块10x10英寸的小电路板找到前任。

但事实证明,近似颠倒生命形态要容易得多--我们有一个简单的连续优化问题,可以使用我们最喜欢的算法-梯度下降来解决,而不是棘手的离散搜索问题。

这个想法是这样的:从随机的电路板配置($b$)开始,然后计算($b^\Prime$),这是人生一步之后的结果。现在,对于某些目标图像($t$),计算导数($\frac{\Partial}{\Partial b}\sum|b^\Prime-t|$),这告诉我们如何更改($b$)使($b^\Prime$)更接近($t$)。然后采取渐变下降的步骤,然后冲洗并重复!

好吧,好吧,我知道你在想什么:生活是不可区分的!你说得对。生活是在布尔格上玩的,地图($b\mapstto b^\Prime$)不可能是连续的,更不用说可微了。

但是假设我们可以做出一个“尽最大努力”的可区分的类比呢?让我们在实数网格上玩生活,实数网格中的“死”细胞为0,“活”细胞为1。我们能不能只用可微操作来“实现”生命的一步呢?让我们试一试。

我们将分别查看每个单元格($c$)。第一步是计算我们活着的邻居。嗯,如果“活的”细胞是1,而“死的”细胞是0,那么我们可以简单地将所有8个邻居的值相加,得到我们的活的邻居计数($n$)。事实上,如果我们想变得更聪明,我们可以将其高效地实现为与以下内核的卷积:

\[\BEGIN{bMatrix}1&;1&;1\\1&;0&;1\\1&;1&;1\end{bMatrix}\]。

很好,我们知道($n$),当然也知道我们自己的0/1值($c$)。下一步是弄清楚这个细胞在下一代是否还活着。规则如下:

如果细胞是活的,($c=1$),那么它活着的充要条件是($n=2$)或($n=3$)。

如果细胞死亡,($c=0$),那么当且仅当($n=3$),它才会复活。

让我们先接近(2)。当($n=3$)为1时,什么函数为1,否则为0?当然是“峰值为-3”函数。这是不可微的,但是以3为中心的窄高斯几乎是一样的!如果适当缩放,高斯在输入3处为1,在其他地方几乎为零。请参见此图表:

同样,对于(1)以2.5为中心的适当缩放的高斯可以完成任务。最后,我们可以通过简单的线性插值在门($c$)下对这两种情况进行多路复用。因为($c\约0$)或($c\约1$),我们知道($ca+(1-c)b$)就像写作,如果c,则a,否则b。

请注意,例如使用tanh函数将该函数的输出“钳制”为0或1是值得的。这样,单元格值始终接近0或1。

好的,太好了!现在剩下的工作就是用PyTorch编写这段代码并调用.backward()…。

…。几秒钟之内,它就开始学习了!这里是梯度下降每100步的GIF($b$)。

(注意:此GIF中的目标图像($t$)是一个全白矩形;myjanky PyTorch渐变下降会找到稀疏配置,从而产生“过度填充”的字段,其中几乎90%的细胞都是活的。)。

看着那张GIF,美丽的迷宫图案让我想起了一些看似不相干的东西:巨型河豚的皮肤。这里有一张来自维基百科的图片:

当微小的扰动扰乱不稳定的均匀状态时,就会产生类似河豚身上的图案,这是“对称破缺”的结果。这些想法最先是由艾伦·图灵描述的(因此,这些模式被称为图灵模式)。这是1952年的纸。

我不禁想知道这里是否也有一种反应扩散模型式的效应在起作用,对称性被($b$)的随机初始化打破了。如果是这样的话,它将在细胞、元胞自动机、图灵完备性和图灵模式…之间创建相当好的连接