学习玩混沌游戏

又到了圣诞节！我们可以谈谈树木吗？这篇文章是关于我的新假期爱好：使用我们的老朋友，梯度下降使树形分形产生幻觉。

但是-让我从头开始。由于各种原因，本月我一直在想着道格拉斯·霍夫施塔特（Douglas Hofstadter）的《我是一个奇怪的循环》（I我是一个怪圈）。我一直在想着通过将照相机对准显示照相机所看到内容的投影仪所产生的这张精美图像。现代术语：如果您共享屏幕共享窗口，该怎么办？有时候是这样的：

这样的“反馈循环”递归经常迅速收敛到惊人的固定点。 NYC MoMath甚至具有艺术品装置，可让您使用相机和投影仪的设置来制作精美的图案。

您可以想象，这里有一个数学理论。尽管不编写任何方程式，但冒着破坏神秘之谜的危险，我将告诉您。 :-)理论是迭代功能系统的理论，几乎完全像听起来那样。从一组仿射函数开始（仿射，因为这就是相机-投影仪系统的工作），然后将它们重复应用于一组点，并在每一步进行合并。无论从何处开始，您都将很快得到分形结构，它是系统的固定点。为什么分形？ -因为自相似性来自仿射函数的无限嵌套组成。

有定理可以确保此定点在极限处收敛并具有唯一性，但是…足够可信，您认为吗？根据您的直觉，您可以使用IFS来构建Sierpinski Triangles和BarnsleyFerns以及各种其他美丽的结构。我想请您参阅Prusinkiewicz和Lindenmayer（是的，那个Linddenmayer）撰写的《植物的算法之美》第8.2节，以获得更多的植物联系。

现在这是我一直在思考的问题：如果我给您一张关于分形蕨的图片，您能给我一套仿射函数，其固定点是那个蕨吗？这是IFS的逆问题。根据Wikipedia的说法，此问题在实际应用中存在图像压缩，但通常很难做到。

嗯有趣。至少在近似意义上，我们最喜欢的工具（梯度下降）能否抢救？回想一下，二维仿射函数实际上只是一个3x3矩阵（具有6个自由参数），用于编码转换的细节。如果我们可以轻松地从一组矩阵中​​计算IFS固定点的图像，那么也许我们可以尝试优化这些矩阵的参数，使固定点看起来像我们想要的样子。

当然，挑战在于有效地找到固定点-反复在图像上进行仿射变换的栅格化和合成听起来很昂贵-并以不同的方式听起来像是可伸缩性的噩梦！ “混乱的游戏。”无需将所有功能密集地应用到平面上的所有点，而是可以按如下方式稀疏地逼近固定点：从一个点开始-任何点！ —并随机选择IFS的仿射功能之一并将其应用到该点。对新点重复此过程。事实证明，在极限情况下，此漂移点留下的“足迹”会收敛到IFS的固定点。 （这也是一个定理，但是我认为我不要求证明就足够了。）这就是Sierpinski三角形的“混沌游戏”。请注意，点的盐和胡椒粉很快就会大胆地收敛到我们知道和喜欢的分形中（这是动画-凝视几秒钟）。

因此，这是一个计划：我们从一个点开始，然后使用当前的IFS矩阵进行混沌游戏，以获得随机近似于固定点的点云。然后，我们将该点云与目标蕨图像进行比较以获得“损失”。最后，我们更新IFS矩阵参数以最大程度地减少此损失，直到最后将定点收敛到目标图像为止。实际上，这仅仅是“机器学习”：我们正在学习玩混沌游戏！

＃初始化IFSF = [ran_3x3_affine（）for _ in range（4）] o = torch.optim.Adam（F，lr = 0.0001）for step in range（100_000）：o.zero_grad（）＃从原点开始v =火炬.tensor（[0。，0.，1.]）＃一旦trace = []为range（200）中的_，则进行混沌游戏：＃应用仿射函数只是＃矩阵乘法！ v = torch.matmul（random.choice（F），v）trace.append（v）＃将跟踪视为点云损失= compare（target_image，trace）＃更新参数loss.backward（）o.step（）

啊!实际上，我需要解释一个细节：如何比较点云和图像？我的想法是通过均匀地从目标图像中采样点，例如通过拒绝采样，将目标图像转换为第二点云。然后，您可以通过所谓的“倒角距离”来比较两个点云，“倒角距离”是从每个点到相对点云中最近的邻居的平均距离。这是二次计算时间，是整个操作中最昂贵的部分，但是每组中只有约100个点，这是完全可行的。

除了教学方法外：请注意，这里的“技巧”实际上是对变更的表述。在点云上比在光栅图像上更容易解决此优化问题！一个重要的教训，适用于图形语言的机器学习领域……并且更广泛地适用于所有可区分的编程企业。

值得注意的是，这种滑稽的计划效果很好！让我们尝试一下。 （心动，因为它是一种简单的低熵的形状，而且因为它相对于霍夫施塔特关于灵魂之内，灵魂之内的更广泛的哲学构想具有象征意义。）

当我们用4个随机仿射变换初始化系统时，混乱博弈留下的痕迹非常令人印象深刻。稀疏性是因为对于梯度下降的每一步，仅模拟混沌游戏的200步-当然，在任何形式的SGD中，噪声和计算时间之间都要进行权衡。

好的。是时候优化了！这是使用Adam优化器进行10万步优化后的样子（在我的旧MacBook上，大约需要40分钟的计算时间）。看起来不错，你不觉得吗？倒角距离方案有效！

现在，我们可以从PyTorch中导出四个仿射矩阵，并使用更昂贵的脱机计算（例如，通过模拟几百万步的混沌游戏）来计算“真”固定点。看起来像这样-不够完美，而且确实是蜡笔涂抹式的，但是显然发生了一些有趣的事情，其结果令人信服地令人心动。

分形结构藏在这颗心中在哪里？这需要一些实用化工具才能清楚地看到。经过一番JS画布攻击之后：这是心脏的GIF，它揭示了其定点结构。

当我第一次看到该动画完整播放时，我会承认眨了几次-我没想到它会起作用，甚至现在我发现自己对这种创造感到惊奇吗？发现？用24个数字编码的心脏的轮廓。

但是看起来仍然不太正确-分形并不明显。为什么呢？这是因为我们的仿射变换将心脏延伸并压缩到几乎无法识别的斑点中。最后自然的改进是迫使我们的仿射变换严格，以使分形中没有任何挤压或歪斜。实际上这并不太难实现：约束问题的解决方案通常是重新参数化，实际上，在这种情况下，我们可以简单地根据旋转，各向异性（等向性）和平移重新矩阵化。现在，我们从6个参数permatrix降至4个，甚至更神奇！结果是一个“明显”的分形固定点，这仅仅是因为当您的眼睛进行刚性运动时，它可以更轻松地识别出结构递归。

自从我答应过你树后，这里是一些分形的叶子。目标图像是枫叶的图片！我以前从没想过，但实际上，那片整齐的叶子内含着整棵树的回声。 （完整披露：它需要进行几次随机重启才能获得令人印象深刻的结果-分形参数化的低维性导致相同的局部优化问题陷入困境，可分化的渲染对象始终都在面对这些问题……）

这个仅使用三个矩阵-在实验上，三个矩阵往往很难获得真正好的结果，而更多的只是导致非常繁忙和拥挤的分形。 （我不知道IFS中是否有“地图数量”这个词，但是我们称它为IFS的工具。在此术语中，我喜欢三元IFS。）

最后的动画实际上绝对让我感到困惑。在某种程度上，这是由于分形的树状效果所致-在这里，它与我优化的轮廓相对。您能想象这仅由12个参数编码吗？奇。

但更令人困惑的是：递归的实际几何形状与您和我习惯于CS106的树递归几何形状完全不同！将上面的GIF与Barnsley的Fern进行比较：Barnsley将每张完整的叶子变成带有“语义”仿射图的两张较小的叶子，而这棵圣诞树却完成了各种奇怪的无法解释的车轮，最终以某种方式神奇地发挥了作用。这让我着迷，我一次只能凝视它几分钟。

当您考虑它时，令人震惊的是，圣诞树是这3个刚性仿射贴图的唯一固定点。 “美丽”不是这个词的意思，也不是“怪诞的”（尽管这两个词已被我与之分享的各种各样的人使用）。神奇的东西从三个矩形中突然冒出来的方式令人着迷。也许我应该要求那个定理的证明……

关于这一切，还有更多要说的。哪种形状最容易IFSify，为什么？在更高的维度上，我们可以将IFS视为一种针对数据（即文字点云）的SVD式降维方案吗？这样做对哪种数据有意义？在哪里找到空间自相似性？点云是否具有固有的IFS“维数”（例如，获得良好逼近所需的仿射变换数量）？通过更多的工作，SGD是否可以作为分形压缩开放问题的合法解决方案？

有很多要考虑的问题-但就目前而言……好吧，加尔文和霍布斯加格首先以加尔文说“我一直在想”，霍布斯打断“在一个周末吗？”这就是我这个寒假的感觉！现在是时候关闭jupyter内核并休息一下— 2021年，Comeded Number将会回归！