Выразительность деревьев решений

С точки зрения логики любая конкретная гипотеза из дерева решений для целевого предиката willWait может рассматриваться как утверждение в следующей форме:
Vs WillWait (s) (Pi(s) v P2(s) v ... v Pn(s))
где каждое условие PL(s) представляет собой конъюнкцию проверок, соответствующих пути от корня дерева к листу с положительным результатом. Хотя это выражение с виду напоминает высказывание в логике первого порядка, оно в определенном смысле является пропозициональным, поскольку содержит только одну переменную, а все предикаты являются унарными. Это дерево решений фактически описывает связь между предикатом WillWait и некоторой логической комбинацией значений атрибутов. Деревья решений не могут использоваться для представления проверок, относящихся к двум или нескольким разным объектам, например, таких проверок, как показано ниже ("Есть ли поблизости более дешевый ресторан?").
3r2 Nearby (г2, г) л Price{r, р) л Price{r2,P2) л Cheaper (р2, р)
Очевидно, что можно было бы ввести еще один булев атрибут с именем CheaperRestaurantNearby (Наличие поблизости более дешевого ресторана), но задача введения всех подобных атрибутов является трудно осуществимой. В главе 19 приведены дополнительные сведения о задаче правильного обучения в логике первого порядка.
Деревья решений в рамках класса пропозициональных языков являются полностью выразительными; это означает, что в виде дерева решений может быть оформлена любая булева функция. Такую задачу можно выполнить тривиально, предположив, что каждая строка в истинностной таблице для данной функции соответствует определенному пути в дереве. Но подобный подход приводит к получению представления в виде дерева решений с экспоненциальными размерами, поскольку количество строк в истинностной таблице увеличивается экспоненциально, тогда как очевидно, что деревья решений позволяют представить многие функции с помощью гораздо меньших деревьев.
Но для некоторых видов функций такая проблема становится вполне реальной. Например, если рассматриваемая функция является функцией определения четности, которая возвращает 1 тогда и только тогда, когда на входах задано четное количество единиц, то потребуется дерево решений, имеющее экспоненциальную величину. Кроме того, сложной является задача использования дерева решений для представления мажоритарной функции, которая возвращает 1, если больше чем на половине ее входов имеется 1.
Иными словами, деревья решений вполне подходят для функций одних типов и не подходят для других. Существует ли представление какого-либо типа, являющееся эффективным для функций всех типов? К сожалению, ответ на этот вопрос отрицателен. Это утверждение можно доказать с помощью такого общего способа. Рассмотрим множество всех булевых функций от п атрибутов. Каково общее количество различных функций в этом множестве? Оно определяется количеством различных истинностных таблиц, которые могут быть составлены на этих атрибутах, поскольку функция определятся своей истинностной таблицей. Истинностная таблица имеет 2П строк, так как для описания вариантов входных данных применяется п атрибутов. Столбец "ответов" такой таблицы может рассматриваться как число, состоящее из 2П битов, которое определяет функцию. Независимо от того, какое представление используется для функций, некоторые из функций (а фактически почти все) должны потребовать для своего представления именно такое количество битов.
Если для определения функции требуется 2П битов, то существует 22 различных функций от п атрибутов. Это число является весьма обескураживающим. Например, при наличии лишь шести булевых атрибутов существует 22 = 18 446 744 073 709 551 616 различных функций, из числа которых может быть сделан выбор. Для поиска совместимых гипотез в таком большом пространстве потребуется некоторые остроумные алгоритмы.







Материалы

Яндекс.Метрика