超指数式概念空间（Conceptspace）与简单词语

Superexponential Conceptspace And Simple Words

❦

事物空间（Thingspace），你也许会觉得，是一个相当巨大的空间。它比现实大得多：现实只包含那些实际存在的事物，而事物空间包含一切可能存在的事物。

实际上，按我对事物空间的「定义」方式——为每一种可能的属性都设一个维度（包括密度、体积、质量这类彼此相关的属性）——事物空间可能定义得太差，以至于谈不上你能称之为大小的东西。但能够把事物空间无论如何可视化仍然很重要。当然，如果你看到的只是扑腾着、吱喳乱叫的一团东西，而不是事物空间中的一簇点，那么你就不可能真正理解一群麻雀。

但无论事物空间多么浩瀚，与概念空间的规模相比都根本不值一提。

「概念」（concept），在机器学习中，指的是一条把例子纳入或排除的规则。如果你看到数据 {2:+, 3:-, 14:+, 23:-, 8:+, 9:-}，你也许会猜测这个概念是「偶数」。关于如何从数据中学习概念的文献相当丰富（正如你所料）……给定随机例子、给定挑选过的例子……允许分类中出现错误……而最重要的是，给定不同的可能规则空间。

例如，假设我们想学习这样一个概念：「适合打网球的好日子」。Days 的可能属性是

| Sky: | {Sunny, Cloudy, Rainy} |

||

| AirTemp: | {Warm, Cold} |

| Humidity: | {Normal, High} |

| Wind: | {Strong, Weak}. |

然后我们会看到如下数据，其中 + 表示该概念的正例，− 表示负分类：

| + | Sky: Sunny; | AirTemp: Warm; |

||

|   | Humidity: High; | Wind: Strong. |

| − | Sky: Rainy; | AirTemp: Cold; |

|   | Humidity: High; | Wind: Strong. |

| + | Sky: Sunny; | AirTemp: Warm; |

|   | Humidity: High; | Wind: Weak. |

算法应该从中推断出什么？

一个机器学习算法可能会把符合这份数据的某一个概念表示为：

{Sky: ?; AirTemp: Warm; Humidity: High; Wind: ?}.

在这种表示法中，要判断该概念接受还是拒绝一个例子，我们逐个元素进行比较：? 接受任何取值，而某个具体取值只接受它自己。

因此，上面的概念只会接受 AirTemp = Warm 且 Humidity = High 的 Days，但 Sky 与 Wind 可以取任意值。它与目前数据中的负例与正例都相符——尽管这并不是唯一能做到这一点的概念。

我们也可以把上面的概念表示简化为

{?, Warm, High, ?}.

不展开细节的话，经典算法会是：

• 维护一组与数据相符的最一般假设——在仍符合事实的前提下，尽可能把更多例子判为正例的那些假设。

• 再维护一组与数据相符的最特殊假设——在仍符合事实的前提下，尽可能把更多例子判为负例的那些假设。

• 每当我们看到一个新的负例，就尽可能少地加强所有最一般假设，使新的集合在符合事实的同时再次尽可能一般。

• 每当我们看到一个新的正例，就尽可能少地放松所有最特殊假设，使新的集合在符合事实的同时再次尽可能特殊。

• 如此继续，直到只剩下一个假设为止。这将会是答案——前提是目标概念确实在我们的假设空间里。

在上面的例子中，最一般假设的集合会是

{{?, Warm, ?, ?},{Sunny, ?, ?, ?}},

而最特殊假设的集合只包含一个成员 {Sunny, Warm, High, ?}。

你能找到的任何其他与数据相符的概念，都将严格地比某个最一般假设更特殊，同时又严格地比最特殊假设更一般。

（想了解更多，我推荐 Tom Mitchell 的《Machine Learning》，本例改编自其中。1）

现在你也许已经注意到，上面的格式无法表示所有可能的概念。比如：「当天空晴朗或者气温温暖时就打网球。」这与数据相符，但在上述概念表示法中，并不存在能描述这条规则的四元组取值。

显然，我们的机器学习器并不算通用。为什么不让它能表示所有可能的概念，从而以尽可能大的灵活性去学习呢？

Days 由这四个变量组成：一个变量有 3 个取值，三个变量各有 2 个取值。因此我们可能遇到的 Days 一共有 3 × 2 × 2 × 2 = 24 种。

用于表示概念的格式允许我们对某个变量要求其中任一取值，或把该变量留空。因此，在这种表示法中共有 4 × 3 × 3 × 3 = 108 个概念。为了让「最一般/最特殊」算法运作，我们需要从最特殊的假设「没有任何例子会被判为正例」开始。把它加上，总计就是 109 个概念。

概念的可能数竟然比 Days 的可能数还多，这是否可疑？当然不可疑：毕竟，一个概念可以被看作 Day 的一个集合。一个概念可以看作它判为正例的那些 Day 的集合，或者（同构地）看作它判为负例的那些 Day 的集合。

因此，对 Days 进行分类的所有可能概念空间，就是所有可能的 Days 集合所构成的集合，其大小为 2 的 24 次方，即 224 = 16,777,216。

这个完整空间包含了我们迄今讨论过的所有概念。但它也包含这样的概念：「只把例子 {Sunny, Warm, High, Strong} 与 {Sunny, Warm, High, Weak} 判为正例，并拒绝其他一切」或「只把例子 {Rainy, Cold, High, Strong} 判为负例，并接受其他一切」。它还包含没有紧凑表示法的概念，只能用一份扁平清单列出哪些允许、哪些不允许。

这就是试图构建一个「完全通用」的归纳学习器所面临的问题：在看到实例空间中的每一个可能例子之前，它们无法学习概念。

如果我们给 Days 增加更多属性——比如水温，或明天的天气预报——那么可能的 Day 数量就会随属性数量呈指数增长。但这对我们受限的概念空间来说不是问题，因为你可以用对数数量的例子把一个很大的空间缩小下来。

假设我们给 day 加上 Water: {Warm, Cold} 这个属性，那么就会有 48 种可能的 Days 与 325 个可能的概念。再假设我们看到的每一个 Day，通常都会被当前仍然可行的概念中大约一半判为正例、另一半判为负例。于是，当我们得知该例子的真实分类时，就会把兼容概念的空间砍掉一半。因此，可能只需要 9 个例子（29 = 512）就能把 325 个可能概念缩小到 1 个。

即便 Days 有 40 个二元属性，要把可能的概念缩小到 1 个，所需的数据量也仍然是可控的：如果每个例子都会被剩余概念中的一半判为正例，那么只需要 64 个例子。当然前提是，那条真实规则本来就是我们能表示出来的那一种！

如果你想把所有可能性都考虑进来，那就祝你好运吧。所有可能概念的空间会随属性数量以超指数式方式增长。

当你谈论的数据有 40 个二元属性时，可能例子的数量已经超过一万亿——但可能的概念数量已经超过「2 的一万亿次方」。要缩小这个超指数式的概念空间，在你能说清楚哪些在集合内、哪些在集合外之前，你得看过超过一万亿个例子。事实上，你得看完每一种可能例子。

注意，这还只是 40 个二元属性。40 比特，也就是 5 字节，只需要被简单地判为「Yes」或「No」。40 比特意味着 240 个可能例子，以及 2240 个把这些例子判为正例或负例的可能概念。

因此，在真实世界里，对象的描述远不止 5 字节而且我们拿不到一万亿个例子而且训练数据里还存在噪声，我们甚至只会去考虑那些高度规律的概念。人的大脑——乃至整个可观测宇宙——都远远不够大，无法把其他所有假设都纳入考量。

从这个视角看，学习并不仅仅依赖于归纳偏置，它几乎完全就是归纳偏置——当你把先验排除掉的概念数量，与仅凭证据排除掉的概念数量相比时。

但这（你会问）与词语的恰当使用又有什么关系呢？

这正是词语既有内涵也有外延的根本原因。

在上一篇文章中，我总结道：

把现实沿着它的关节处切开的方法，是在概率密度异常高的聚集处画出边界。

我在这句（略作编辑的）话里刻意省略了一个关键限定，因为直到现在我才有办法解释它。更好的说法是：

把现实沿着它的关节处切开的方法，是在事物空间中概率密度异常高的聚集处画出简单的边界。

否则你就只是在事物空间里搞「杰利蝾螈式」划界：画出一些非常古怪、彼此不连通的边界，把你观察到的例子统统圈进去——而这些例子无法用比你观察本身更短的消息来描述——然后宣称：「这就是我以前见过的东西，也是我期望未来还会见到更多的东西。」

在现实世界里，分子层级以上的东西没有任何会完全重复。Socrates 的形状与那些同样会被毒芹毒死的其他人类很相似，但他并不完全与他们一样。因此，你猜测 Socrates 是「人类」，依赖于在事物空间里围绕人类簇画出简单的边界；而不是：「形状完全像[5 兆字节形状规格 1]并且具有[许多其他特征]，或者形状完全像[5 兆字节形状规格 2]并且具有[许多其他特征]，……的东西，都是人类。」

如果你不围绕自己的经验画出简单的边界，你就无法用它们进行推断。因此，你会尝试用诸如「其目的在于为了激发而激发任何复杂情绪的东西」这样的内涵定义来描述「艺术」，而不是仅仅指着一长串东西，说哪些是艺术、哪些不是艺术。

事实上，上面那句关于「如何沿关节切开现实」的话有点像「先有鸡还是先有蛋」：在你至少做过一点切割之前，你无法评估真实观测的密度。而概率分布来自你画出的边界，而不是相反——如果你已经拥有了概率分布，那么你就拥有推断所需的一切，又何必费劲去画边界呢？

这也提示了另一个——是的，又一个——理由，让我们对「你可以按自己喜欢的方式定义一个词」这种说法保持怀疑。当你考虑到概念空间的超指数式规模时，你就会明白：把某个特定概念单独拎出来加以考虑是一种相当大胆的举动——不仅对我们如此，对任何计算能力有限的心智亦然。

向我们介绍一个词「wiggin」，并把它定义为「黑发绿眼的人」，却不给出任何理由说明为什么要把这个特定概念提升到我们刻意思考的层面，这就很像一位侦探在说：「嗯，我对究竟是谁谋杀了那些孤儿，完全没有任何一丝一毫的证据支持哪一边……甚至连直觉都没有，明白吗……但我们有没有考虑过住在 1234 Norkle Rd 的 John Q. Wiffleheim，把他当作嫌疑人？」

Tom M. Mitchell，《Machine Learning》（McGraw-Hill Science/Engineering/Math，1997）。 ↩︎