Beyond Recursion

Quine，或者说可以打印自己源代码的程序，通常被认为是比递归更神奇的东西，我以前也聊过这个话题。这次再提起来，是因为发现了另一个有趣的例子。

真相是，今天早上实验室网络检修，没法上网，而且由于考试周的接近自习室和图书馆都成了人山人海，几乎没有我等“散户”的容身之地，于是无聊中就把昨天下载的一篇传说很有趣的论文翻出来看了——发现果然很有趣。其实就是 Dahua 之前曾经介绍过的今年 CVPR 会议上分发的一篇最有趣的论文 Paper Gestalt。论文主要是讲了如何用 Computer Vision 的方法来自动判别提交到会议的论文的好坏并决定是否 accept，Dahua 的 blog 上已经介绍得很详细了，我在这里也就不多说了。总的来说，推荐去看一看论文原文，现在可以可以下载到了，语言既严谨又诙谐，简直就是给不幸被断网的小朋友的最佳读物啊！ 😀 看到赫然出现的麦克斯韦方程组的时候，我就乐坏了，当然我认为这篇论文的作者并不是 seriously 真的想要用这个系统来作为以后审稿的辅助工具的，但是这个确实很好玩，更重要的是，我看到作者对这个学术社区现状的反思，当然除了诙谐，还略带一些讽刺的意味。所以呀，学术圈也是有可爱的人以及不无聊的事的！ ^_^

不过我看到关于这篇论文的介绍的时候，第一时间想到的问题就是：不知道用它自己的这个方法来测试它自己这篇论文，结果会怎样呢？等我看了论文，才发现原来它已经做了这个实验了，根据论文里说的结果，后验概率是 88.4% （adaboost 我不熟悉，不知道这个概率如何得来的，呼唤 kily），也就是说显然这篇论文应该被 CVPR 录用的。 🙂

那么有意思的地方在哪里呢？这里的问题就和你试图构造一个打印自身的程序是会碰到的几乎一模一样。因为论文里说了，88.4% 的后验概率，这个数字是论文的一部分，也就是说如果没有这个数字的话，这篇论文还是不完整的，也就是说这个 88.4% 的概率应该是那篇不完整的论文的概率。那么好了，我填上 88.4% 之后再运行，这个时候，如果出来的结果不是 88.4% 就惨了，是不是需要再更新一下论文，然后再跑？也许这样永远轮回都达不到目标。这里必须要找到一个“不动点”一样的东西，这个 x% 填到论文这里，再运行分类器，得到的结果刚好也是 x%，看起来算是一个方程，如果说对于printf来说还可以巧妙地构造解的话，对于一个（即使相对简单的）分类器来说大概还是有些困难了。

不过其实这里的问题也没有那么严重，因为论文里用的方法是把一篇 paper 的 PDF 文件转换为图片再连接起来，最后抽取一些诸如 Histograms of Oriented Gradients 一类的视觉feature来进行分类。可以想像一个数字的变动对于这样 feature 抽取的影响其实是非常小的，所以几乎可以忽略不计啦。

只是这篇论文它又给自己出了第二个难题：为了展示算法的工作方式（当然，也许仅仅是为了在视觉上欺骗分类器获得更高的 accept 的概率 :p ），作者在论文中给出了本论文的 PDF 文件在转化为图片之后连接起来的结果。问题出来了：这张图片里，应该是包含它本身的一个缩略图的，这成了一个循环依赖，要完成论文的内容，必须先有一张论文的缩略图，而论文的缩略图必须是基于论文完整的内容的。

当然缩略图嵌套到一定小的范围内人眼不能分辩了之后，就可以作假了，所以这样的图，或者说至少看起来像这样的图，还是可以构造出来的。不过，在这篇论文里，作者似乎没有去钻这个牛角尖，仔细看它的缩略图，其中的布局也和最终版本的论文有些出入，也许只是简单地用了论文的某一个之前的版本吧。看来还不够完美啊！ 😀

最后，记得之前在 Google Reader 上看到很多奇特的递归图，不过怎么也找不到是哪个网站了，只找到这一张照片，贴在这里吧：

因为到了太小的尺度就可以“糊弄过关”了，所以奇特的图片还是可以做出来的，而且，有些特殊的例子也不难“做”出来，以前曾经尝试过在虚拟机里通过 X11vnc 远程桌面到本地，于是屏幕就递归了…… :p