决策树查询
我正在尝试理解我的人工智能教科书中的一段内容，并且需要这方面的帮助。
本质上，我的问题是，如果定义一个函数需要 2^n 位，为什么 n 个属性上有 2^(2^n) 个函数？
以下是文本中的段落（来源：AI：现代方法，Stuart Russell 和 Peter Norvig）：
决策树适用于某些类型 功能和对其他人不利。是 有任何一种表示形式 对各种类型都有效 功能？不幸的是，没有。我们可以 以非常普遍的方式展示这一点。 考虑所有布尔值的集合 n 个属性上的函数。多少 这组中有不同的功能吗？ 这只是不同的数量 我们可以写下真值表， 因为函数是由它定义的 真值表。真值表有 2^n 行，因为每个输入案例都是 由n个属性描述。我们可以 考虑“答案”栏 表为 2^n 位数字 定义函数。无论 我们用于函数的表示， 一些功能（几乎所有 事实上，他们）将需要 至少要表示那么多位。
如果需要 2^n 位来定义 函数，则有 2^(2^n) n 个属性上有不同的函数。
第二个问题是：为什么我们需要 2^n 位数字（见上面的粗体），我认为我们只需要 n 位数字，例如如果我们有 3 个属性，我们可以定义 2^3=8 个函数，因此只需 3 位即可定义所有 8 个功能（000、001、010、011 等）。
我已经思考这个问题有一段时间了，不知道是什么让我困惑，感谢您花时间调查这个问题！
I'm trying to understand a para in my AI textbook, and need help with this.
Essentially, my question is why are there 2^(2^n) functions on n attributes if it takes 2^n bits to define a function?
Here is the para from the text (source: AI: A Modern Approach, Stuart Russell and Peter Norvig):
Decision Trees are good for some kinds
of functions and bad for others. Is
there any kind of representation that
is efficient for all kinds of
functions? Unfortunately, no. We can
show this in a very general way.
Consider the set of all Boolean
functions on n attributes. How many
different functions are in this set?
This is just the number of different
truth tables that we can write down,
because the function is defined by its
truth table. The truth table has 2^n
rows, because each input case is
described by n attributes. We can
consider the 'answer' column of the
table as a 2^n-bit number that
defines the function. No matter what
representation we use for functions,
some of the functions (almost all of
them, in fact) are going to require at
least that many bits to represent.If it takes 2^n bits to define the
function, then there are 2^(2^n)
different functions on n attributes.
A second question is: Why do we need 2^n bit number (see bold above), I thought we'd need n bit number only, for example if we have 3 attributes, we can define 2^3=8 functions, thus needing only 3 bits to define all 8 functions (000, 001, 010, 011, etc).
i've been thinking about this for awhile, not sure what eludes me, thank you for your time in looking into this!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
他的意思是这样的：你可以写出 n 个属性的所有可能值：
0 1 2 .. n
0 0 0 0
0 0 0 1
显然行数是 2^n
现在我们通过添加额外的列来定义一个函数。如果该位为 1，则该函数中的值为“true”，否则为 false。由于行数为 2^n，并且我们通过 0 和 0 的所有组合来定义函数。 1 在二进制字符串中，显然有 2^(2^n) 个这样的字符串，因此在 n 个属性上有 2^(2^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) 个函数。
What's he's saying is this: you can write out all possible values for n attributes as:
0 1 2 .. n
0 0 0 0
0 0 0 1
clearly the number of rows is 2^n
Now we define a function by adding an extra column. If the bit is 1, then that value is "true" in that function, otherwise it is false. Since the number of rows is 2^n, and we are defining the function by all combinations of 0's & 1's in a binary string, clearly there are 2^(2^n) such strings, so there are 2^(2^n) functions on n attributes.
Take a simple example: n = 3. The values of the attributes are:
000
001
010
011
100
101
110
111
Now, we can define one function f that is "true" for rows 1 and 2, and "false" for every other row. We could represent this as row1="true" row2="true" row3="false" ...etc. Now, how many different strings like this could we get? we could write out
000000000 000000001 000000010 .. 111111111
Each one of these strings maps to a different function, and there are 2^8 = 2^(2^n) of these, hence 2^(2^n) functions.
我想我明白了，我认为你的答案可能有错误...
让我根据我对 3 个属性的示例的理解进行解释..
n = 3
Row 1 000
Row 2 001
Row 3 010
...
第 8 111 行
函数 0：每行均为 False，因此 0 0 0 0 0 0 0 0（8 '0，因为有 8 行）
函数 1：第 1 行为真，其余为假：00000001
函数 2：第 2 行为真，其余为 false：00000010
...
因此有 2^8 个函数，即 2^(2^3) 即 2^(2^n)。
正确的？
I think I get it, and I think there might be a mistake in your answer...
Let me explain according to my understanding of your example for 3 attributes..
n = 3
Row 1 000
Row 2 001
Row 3 010
...
Row 8 111
Function 0 : False for every row therefore 0 0 0 0 0 0 0 0 (8 '0's as there are 8 rows)
Function 1: True for row 1, false for the rest: 00000001
Function 2: True for row 2, false for the rest: 00000010
...
Thus there are 2^8 functions, which is 2^(2^3) i.e. 2^(2^n).
Correct?
真值表中有 2^n 行。因此，在“答案”列中，我们有 2^n 个槽用于函数输出。对于 2^n 个槽中的每一个，我们都有 2 个选择。这是一个长度为 2^n 的二进制字符串。该字符串的形成方式有 2^(k)，其中 k 是可用槽的数量，在示例中 k=2^n，因此 2^(2^n) 是我们可以形成的布尔函数的数量n 属性。
There are 2^n rows in the truth table. In the "answer" column we thus have 2^n slots for our function outputs. For each of the 2^n slots we have 2 choices. This is a binary string of length 2^n. The number of ways this string can be formed is 2^(k) where k is the number of slots available, in the example k=2^n so 2^(2^n) is the number of Boolean functions we can form over n attributes.
顺便说一句，他说您至少需要那么多位来表示该函数的原因是每个函数必须包含足够的信息来指定该函数的特定输入行是“真”还是“假”。
从信息论的角度来看，很难看出如何在少于 2^(2^n) 位的时间内完成这一任务，或者更简单地说，用 m 位来完成，其中 m 是函数的数量。因为，假设我们实际上已经写出了所有这些函数。我们使用哪一个？我们必须指定它的 id，它需要 m 位。
As an aside, the reason why he says that you will need at least that many bits to represent the function is that each function must include enough information to specify whether a particular row of inputsis "true" or "false" for that function.
From an information-theoretic perspective, it is hard to see how this can be done in fewer than 2^(2^n) bits -- or more simply, than m bits, where m is the number of functions. Because, suppose we had actually written out all of those functions. Which one are we using? We have to specify it's id which takes m bits.