文章探讨了衡量神经网络泛化能力中“简单”概念的定义。传统Kolmogorov复杂度以程序长度衡量概念的简单性，但无法区分随机映射和连贯概念。文章提出基于条件Kolmogorov复杂度的概念，即概念相对于人类大脑的复杂度K(C|B)。这种方法考虑了人类已有的世界模型，例如“热狗”概念，只需简单指向即可。相比之下，随机点映射需要大量特殊情况。因此，基于人类认知的条件Kolmogorov复杂度更适合衡量对人类而言“简单”的概念。

🧠传统Kolmogorov复杂度通过程序长度衡量概念的简单性，但无法区分随机映射和连贯概念，例如，随机点映射的程序可能比热狗分类器更短，但直觉上热狗概念更简单。

💡文章提出基于条件Kolmogorov复杂度的概念复杂度衡量方法K(C|B)，其中C代表概念，B代表人类大脑。这种方法衡量的是在已知人类大脑模型的前提下，描述一个概念所需的最小程序长度。

🌭对于人类而言，热狗概念已经存在于大脑中，因此用条件Kolmogorov复杂度来描述热狗，只需要简单地指向大脑中已有的概念即可。而随机点映射则需要单独描述每个点的情况。

🔑文章将“人类概念”定义为{C|K(C|B)<τ}，即条件Kolmogorov复杂度低于某个阈值τ的概念集合。这为理解神经网络泛化能力提供了一个新的视角。

Published on May 26, 2025 11:45 AM GMT

When thinking about neural network generalization, I want to be able to refer to "simple" concepts. But what do I mean by simple?

One (classic) answer: a concept is simple if it has low Kolmogorov complexity. If we think of a concept as program transforming inputs to 0 or 1, then simple concepts have short programs.

But this definition fails to capture some intuitive notion of complexity. Consider two concepts: the first defines a randomly sampled mapping of 10 points in the $(x,y)$ plane to $\{0,1\}$. The second maps high resolution images to {hot-dog, no-hot-dog}. The program for the point mapping (a small lookup table) will certainly be shorter then the visual processing program required for the hotdog classier. But in a certain sense of complexity, this feels off. The point map is all special cases. Hotdogs are a coherent category. And if we already "have" the concept of hotdog, all that's required is to point to it.

When defining the complexity of concepts then, we want to be able to reference our existing model of the world. We already "have" the concept of a hotdog - the concept just needs to point to it.

To capture this notion formally, we can use the notion of conditional Kolmogorov complexity. For programs $P$and $Q$, let $K\left(P|Q\right)$ denote the length of the shortest program that encodes $P$ given access to the program $Q$. We want to define the conditional complexity of a concept with respect to...the human brain. With  $C:X\to \{0,1\}$  a concept, and $B$ a human brain, we get the complexity measure $K\left(C|B\right)$. Imagining the brain mapping inputs to a dictionary of concepts, we can specify the hotdog with a simple lookup:

def hotdog(x, brain):    return "hotdog" in brain(x)

but assuming a worst-case assignment, the point mapping require 10 separate cases:

def point_map(x):    if (x,y) == (3,2):        return True     elif (x,y) == (-1, 5):        return False     ...

There's some hand-waving going on here - a brain API would not be this clean. But the conditional Kolmogorov complexity seems to be capturing what we want out of a definition of "simple-to-human" concepts. 

Given this complexity measure, we can now define "human concepts" more generally as the set$\left\{C|K\right(C|B)<\tau \}$ for some threshold $\tau$. 

There's a separate question of how unique/contingent human concepts are, which I hope to cover in a future post. 

Discuss