Запрос на деревья решений

Question

Я пытаюсь понять пункт в моем учебнике по искусственному интеллекту, и мне нужна помощь с этим.

По сути, мой вопрос заключается в том, почему существуют 2 ^ (2 ^ n) функции для n атрибутов, если для определения функции требуется 2 ^ n бит?

Вот параграф из текста(источник: AI: Современный подход, Стюарт Рассел и Питер Норвиг):

Деревья решений хороши для одних функций и плохи для других.Есть ли какое-либо представление, которое эффективно для всех видов функций?К сожалению нет.Мы можем показать это в очень общем виде.Рассмотрим множество всех булевых функций по n атрибутам.Сколько разных функций в этом наборе?Это просто количество различных таблиц истинности, которые мы можем записать, потому что функция определяется таблицей истинности.Таблица истинности имеет 2 ^ n строк, потому что каждый входной регистр описывается n атрибутами.Мы можем рассматривать столбец 'answer' таблицы как 2 ^ n-битное число , которое определяет функцию.Независимо от того, какое представление мы используем для функций, некоторым функциям (фактически, почти всем) потребуется по крайней мере столько битов для представления.

Если для определения функции требуется 2 ^ n бит, то для n атрибутов существует 2 ^ (2 ^ n) различных функций.

Второй вопрос: почемунам нужно 2 ^ n битного числа (см. жирный шрифт выше), я думал, что нам нужно только n битное число, например, если у нас есть 3 атрибута, мы можем определить 2 ^ 3 = 8 функций, таким образом, нам нужно всего 3 бита, чтобы определить все8 функций (000, 001, 010, 011 и т. Д.).

Я долго об этом думал, не знаю, что ускользает от меня, спасибо, что уделили время!

Answer 1

Он говорит следующее: вы можете записать все возможные значения для n атрибутов как:

0 1 2 .. n

0 0 0 0 0 0 0 1

ясно, что число строк равно 2 ^ n

Теперь мы определим функцию, добавив дополнительный столбец.Если бит равен 1, то это значение «true» в этой функции, в противном случае оно равно false.Поскольку число строк равно 2 ^ n, и мы определяем функцию по всем комбинациям 0 и 1 в двоичной строке, очевидно, что существует 2 ^ (2 ^ n) таких строк, поэтому существует 2 ^ (2 ^ n) функций для n атрибутов.

Возьмем простой пример: n = 3. Значения атрибутов:

000 001 010 011 100 101 110 111

Теперь,мы можем определить одну функцию f, которая является «истинной» для строк 1 и 2 и «ложной» для каждой другой строки.Мы можем представить это как row1 = "true" row2 = "true" row3 = "false" ... и т. Д.Теперь, сколько разных строк мы можем получить?мы могли бы выписать

000000000 000000001 000000010 .. 111111111

Каждая из этих строк отображается в другую функцию, и есть 2 ^ 8 = 2 ^ (2 ^ n) из них,следовательно, 2 ^ (2 ^ n) функций.

Answer 2

Я думаю, что понял, и думаю, что в вашем ответе может быть ошибка ...

Позвольте мне объяснить в соответствии с моим пониманием вашего примера для 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: True для строки 1, false для остальных: 00000001

Функция 2: True для строки 2, false для остальных: 00000010

...

Таким образом, существует 2 ^ 8 функций, что составляет 2 ^ (2 ^3) т.е. 2 ^ (2 ^ n).

Правильно?

Answer 3

В таблице истинности 2 ^ n строк. Таким образом, в столбце «answer» у нас есть 2 ^ n слотов для выходов нашей функции. Для каждого из 2 ^ n слотов у нас есть 2 варианта. Это двоичная строка длиной 2 ^ n. Количество способов, которым эта строка может быть сформирована, равно 2 ^ (k), где k - количество доступных слотов, в примере k = 2 ^ n, поэтому 2 ^ (2 ^ n) - количество булевых функций, которые мы можем сформировать в течение n атрибутов.

Answer 4

Кроме того, причина, по которой он говорит, что вам понадобится как минимум столько битов для представления функции, заключается в том, что каждая функция должна включать в себя достаточно информации, чтобы указать, является ли конкретная строка входных данных "истинной" или "ложной" для этогоfunction.

С точки зрения теории информации трудно понять, как это можно сделать менее чем за 2 ^ (2 ^ n) бит - или проще, чем m бит, где m - этоколичество функций.Потому что, предположим, мы действительно выписали все эти функции.Какой из них мы используем?Мы должны указать его идентификатор, который занимает m бит.