Блог

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

По сути, мой вопрос заключается в том, почему существует 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 и т.д.).

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

Он говорит следующее: вы можете записать все возможные значения для 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) функции.

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

Позвольте мне объяснить в соответствии с моим пониманием вашего примера для 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).

Правильно?

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

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

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