1

我正在尝试理解我的 AI 教科书中的一段，需要帮助。

本质上，我的问题是，如果定义一个函数需要 2^n 位，为什么在 n 个属性上有 2^(2^n) 个函数？

这是文本中的段落（来源：AI：现代方法，Stuart Russell 和 Peter Norvig）：

决策树对某些功能有好处，对另一些功能不好。是否有任何一种对各种功能都有效的表示？很不幸的是，不行。我们可以用一种非常笼统的方式来展示这一点。考虑 n 个属性上所有布尔函数的集合。这个集合中有多少种不同的功能？这只是我们可以写下的不同真值表的数量，因为函数是由它的真值表定义的。真值表有 2^n 行，因为每个输入案例由 n 个属性描述。我们可以将表格的“答案”列视为2^n 位数字定义函数。无论我们对函数使用什么表示，一些函数（实际上几乎所有函数）都将需要至少那么多位来表示。

如果定义函数需要 2^n 位，那么在 n 个属性上就有 2^(2^n) 个不同的函数。

第二个问题是：为什么我们需要 2^n 位数（见上面的粗体），我以为我们只需要 n 位数，例如如果我们有 3 个属性，我们可以定义 2^3=8 个函数，因此只需要 3 位来定义所有 8 个功能（000、001、010、011 等）。

我一直在考虑这个问题，不知道是什么让我难以理解，感谢您花时间研究这个问题！

4

4 回答 4

2

他的意思是：您可以将 n 属性的所有可能值写为：

0 1 2 .. n

0 0 0 0 0 0 0 1

显然行数是 2^n

现在我们通过添加一个额外的列来定义一个函数。如果该位为 1，则该值在该函数中为“真”，否则为假。由于行数是 2^n，并且我们通过二进制字符串中 0 和 1 的所有组合来定义函数，显然有 2^(2^n) 个这样的字符串，所以有 2^(2^n ) 对 n 个属性的函数。

举个简单的例子：n = 3。属性的值是：

000 001 010 011 100 101 110 111

现在，我们可以定义一个函数 f，第 1 行和第 2 行为“true”，每隔一行为“false”。我们可以将其表示为 row1="true" row2="true" row3="false" ...等。现在，我们能得到多少这样的不同字符串？我们可以写出

000000000 000000001 000000010 .. 111111111

这些字符串中的每一个都映射到一个不同的函数，其中有 2^8 = 2^(2^n) 个，因此有 2^(2^n) 个函数。

于 2011-04-15T02:41:34.997 回答
1

我想我明白了，我认为你的答案可能有错误......

让我根据我对你的例子的理解来解释3个属性..

n = 3

第 1 000 行

第 2 001 行

第 3 010 行

...

第 8 111 行

功能 0 ：每行都为 False，因此 0 0 0 0 0 0 0 0 （8 '0' 因为有 8 行）

功能 1：第 1 行为真，其余为假：00000001

函数 2：第 2 行为真，其余为假：00000010

...

因此有 2^8 个函数，即 2^(2^3) 即 2^(2^n)。

正确的？

于 2011-04-15T03:04:42.380 回答
1

真值表中有 2^n 行。因此，在“答案”列中，我们有 2^n 个插槽用于函数输出。对于 2^n 个插槽中的每一个，我们有 2 个选择。这是一个长度为 2^n 的二进制字符串。可以形成此字符串的方式数为 2^(k) 其中 k 是可用槽的数量，在示例中 k=2^n 所以 2^(2^n) 是我们可以形成的布尔函数的数量n 属性。

于 2018-03-27T21:56:51.460 回答
0

顺便说一句，他说您至少需要那么多位来表示函数的原因是每个函数必须包含足够的信息来指定特定行的输入对于该函数是“真”还是“假”。

从信息论的角度来看，很难看出这是如何在少于 2^(2^n) 位或更简单的情况下完成的，而不是 m 位，其中 m 是函数的数量。因为，假设我们实际上已经写出了所有这些函数。我们使用的是哪一个？我们必须指定它的 id，它需要 m 位。

于 2011-04-15T02:58:13.493 回答