Marr 的三个层次

David Marr 研究的是视觉，可他留下来的最重要的想法和眼睛无关。他认为，一个处理信息的系统，只有在你能从三个分开的层次描述它时，才算被理解了：它算的是什么、为什么算这个，它怎么算，以及实际干活的是什么物理东西。我把这个框架用来思考各种系统。讨论原地打转的时候它最有用，因为双方往往在回答不同层次的问题。

基本想法

计算层次说明系统解决什么问题，以及为什么这是该解决的问题。它描述从输入到输出的映射，以及让这个映射说得通的约束，完全不涉及步骤。

算法层次说明怎么算。它为输入和输出选一种表示，再选一个把前者变成后者的过程。

实现层次说明用什么算：真正执行这个过程的物理载体，可能是神经元、晶体管、浏览器里的 JavaScript 引擎，也可能是一排 GPU。

Marr 自己举的例子是收银机。它算的是加法，加法的性质解释了为什么商品扫码的先后顺序不会改变总价。它怎么加，可以是带进位的十进制，也可以是二进制。它用什么加，可以是齿轮，也可以是芯片。每个层次都能单独变化：一个计算可以有很多算法，一个算法可以有很多实现。

这种松散正是关键。认识芯片里的每一个晶体管，并不能告诉你它在做加法。知道它在做加法，也不能告诉你它是不是按十进制进位。Marr 用这个论证反对只从神经元去研究视觉，放到机器学习上同样贴切。损失函数和预测目标属于计算层次，模型类别、特征和优化器属于算法层次，硬件、数值精度和库属于实现层次。有人要求解释一个模型时，先问清楚他要的是哪一层会很有帮助，因为三种回答不能互相替代。

形式化的核心

Marr 的层次是一个思考框架，不是定理，但每一层都有一个可以精确写下来的对象。计算层次是从输入空间到输出空间的一个函数。对下面的工具来说，就是奇数长度列表的中位数，也就是正中间那个次序统计量。

f : \mathcal{X} \to \mathcal{Y}, \qquad \operatorname{median}(x_1, \dots, x_n) = x_{\left(\frac{n+1}{2}\right)} \quad \text{for odd } n

规格必须交代清楚棘手的情况。偶数长度的列表，取哪个中间？工具让 n 始终是奇数，避开了这个问题。

算法层次是一个过程 $A$ ，它和上一层唯一的联系是正确性。任何在所有输入上都返回 $f(x)$ 的过程都算数。

A \text{ is correct for } f \iff A(x) = f(x) \;\; \text{for every } x \in \mathcal{X}

正确的过程之间，代价可以差很多。数基本步骤，得到的是属于算法和输入本身、和任何机器都无关的量。

T_{\text{insertion}}(n) = O(n^2), \quad T_{\text{merge}}(n) = O(n \log n), \quad \mathbb{E}\,T_{\text{quickselect}}(n) = O(n), \quad T_{\text{counting}}(n) = O(n + m)

能用计数法，只是因为取值是 0 到 99 的整数。选择一种表示，就打开了一种算法。

实现层次把步数变成时间，这个换算是测出来的，不是公式推出来的。一个粗略的模型里，每一步有成本 $c$ ，另有固定开销 $t_0$ ，两者都由设备、语言运行时以及数据在内存里的摆放方式决定。

t_{\text{wall}} \approx c \cdot T_A(n) + t_0

大 O 记号藏起了 c 和 t₀。常数差得够多时，两个算法在真实机器上的快慢可以颠倒。

动手试

下面的工具用四种方法，求一个带种子的列表的中位数，列表里是 0 到 99 的整数。用层次切换，一次只读表里的一列。

列表长度

顺序

种子 1

按层次读表

算法层次。同一个答案，步数相差好几个数量级：计数只要 1,049 步，插入排序要 246,802 步。

四个算法处理同一组 1,001 个打乱的值，取值从 0 到 99。
算法	中位数	步数	每次用时
插入排序排序后取中间	47	246,802	未计时
归并排序排序后取中间	47	8,714	未计时
快速选择向中间划分	47	3,290	未计时
计数统计 0 到 99，走到一半	47	1,049	未计时

步数指比较次数，计数法则是计数次数。条形用对数刻度，长度每多一格是倍数，不是差值。

四个算法都找到中位数 47（1,001 个打乱的值）。计数步数最少（1,049），插入排序最多（246,802）。计时之前，时间这一列是空的。

列表带种子，所以给定设置下，中位数和每个步数都是固定的。只有时间那一列来自你的设备。

选“算什么”。每一行报告的中位数都一样。在计算层次上，四个算法是同一件事。
选“怎么算”，列表为 1,001 个打乱的值。插入排序要比较大约 247,000 次，计数法只要大约 1,000 次计数。
把顺序换成“已排序”。插入排序降到 1,000 次比较，四个算法里最少，因为每个新值本来就在正确位置上。步数属于算法和输入的组合。
选 5,001 个打乱的值并计时。归并排序的比较次数比插入排序少大约一百倍。看看在你的设备上它是不是也快了一百倍。它在递归的每一层都新建数组，这个成本是比较次数看不到的。
同一个设置计时两次。时间会有一点浮动，步数纹丝不动。实现层次的数字是测量值，算法层次的数字是计数。

我在哪用到它

容易出错的地方

五个陷阱

把某一层当成真正的解释。完整的说明三层都要有，而且哪一层都推不出另外两层。Marr 当年抱怨的，正是计算层次最常被跳过。
没定清楚“算什么”就开始讨论“怎么算”。如果两个算法在某个输入上结果不同，要么其中一个错了，要么规格从来没说清该返回什么。偶数长度列表的中位数就是典型的漏洞。
在错误的层次上回答。“它跑在八块 GPU 上”解释不了一个预测，“损失函数是交叉熵”也解释不了训练为什么慢。
把步数当成时间。大 O 记号丢掉了常数，在实际规模下，内存分配、缓存和运行时的影响可能盖过步数上的巨大差距。
以为层次是固定的分层。一层在哪里结束，取决于你在解释什么。归并排序里的合并步骤，自己也有规格、算法和实现。

参考资料

VisionMarr，W. H. Freeman，1982。MIT Press 版，2010。第 1 章。三个层次最早的完整表述，收银机的例子就在这里。第一章可以单独读。
From Understanding Computation to Understanding Neural CircuitryMarr 与 Poggio，MIT AI Memo 357，1976。比那本书更早的备忘录，分层次理解的想法最先在这里出现。
The levels of understanding framework, revisedPoggio，Perception 第 41 卷第 9 期，2012，第 1017–1023 页。Marr 的合作者在几十年后重新审视这个框架，认为它需要加上学习这一层。
Marr's three levels: A re-evaluationMcClamrock，Minds and Machines 第 1 卷，1991，第 185–196 页。一位哲学家对三个层次的重新检讨，追问每一层到底在问什么。