machine-learning - 决策树中的假设函数空间

Question

我正在阅读 Stuart Russell 和 Peter Norvig 所著的《人工智能》一书(第 18 章)。以下段落来自决策树上下文。

For a wide variety of problems, the decision tree format yields a nice, concise result. But some functions cannot be represented concisely. For example, the majority function, which returns true if and only if more than half of the inputs are true, requires an exponentially large decision tree.

In other words, 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, the answer is no.

We can show this in a 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.

A truth table over "n" attributes has 2^n rows, one for each combination of values of the attributes.

We can consider the “answer” column of the table as a 2^n-bit number that defines the function. That means there are (2^(2^n)) different functions (and there will be more than that number of trees, since more than one tree can compute the same function). This is a scary number. For example, with just the ten Boolean attributes of our restaurant problem there are 2^1024 or about 10^308 different functions to choose from.

1. 作者将表中的“答案”列表示为定义函数的 2^n 位数字是什么意思？

2. 作者如何导出 (2^(2^n)) 个不同的函数？

请详细说明上述问题，最好用简单的例子，例如n = 3。

Answer 1

考虑一个 3 输入函数的通用真值表，其中每个三元组的结果也是 bool 值(1 或 0)，由变量 i 到 'p' 表示:

A  B  C   f(a,b,c)
0  0  0     i
0  0  1     j
0  1  0     k
0  1  1     l
1  0  0     m
1  0  1     n
1  1  0     o
1  1  1     p

我们现在可以将三个变量上的任何函数表示为 8 位数字，ijklmnop。例如，and为00000001； 或是01111111； one_hot(恰好有一个输入True)是01101000。

对于 3 个变量，“答案”中有 2^3 位，即完整的函数定义。由于“答案”中有 8 位，因此我们可以定义 2^8 个可能的函数。

这是否概括了您的理解领域？

有关示例函数的更多详细信息

您只需(一旦看到模式)使八位与表中的整体相对应。例如，one-hot 的表如下所示:

A  B  C   f(a,b,c)
0  0  0     0
0  0  1     1
0  1  0     1
0  1  1     0
1  0  0     1
1  0  1     0
1  1  0     0
1  1  1     0

向下阅读标记为 f(a,b,c) 的“答案”列，您将得到 8 位序列 01101000。该 8 位数字足以完整定义该函数:列出 a、b、c 的所有组合的行都处于固定(数字)序列中。

您可以以模板格式编写任何此类函数:

def and(a, b, c):
    and_def = '00000001'
    index = 4*a + 2*b + 1*c
    return and_def[index]

现在，如果我们将其推广到任何 3 输入二元函数:

def_bin_func(a, b, c, func_def)
    return func_def[4*a + 2*b + 1*c]

如果您愿意，您可以进一步概括输入列表的模板:连接位并使用该整数作为 func_def 字符串的索引。

这样就清楚了吗？