Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 238
Текст из файла (страница 238)
Но для некоторых видов функций такая проблема становится вполне реальной. Например, если рассматриваемая функция является 'ж функцией определения четности, которая возвращает 1 тогда и только тогда, когда на входах задано четное количество единиц, то потребуется дерево решений, имеюшее экспоненциальную величину. Кроме того, сложной является задача использования дерева решений для представления 'в. мажоритарной функции, которая возвращает 1, если больше чем на половине ее входов имеется 1. Иными словами, деревья решений вполне подходят для функций одних типов и не подходят для других. Сушествует ли представление какого-либо типа, являюшееся эффективным для функций всех типов? К сожалению, ответ на этот вопрос отрицателен.
Это утверждение можно доказать с помощью такого обшего способа. Рассмотрим множество всех булевых функций от и атрибутов. Каково обшее количество различных функций в этом множестве? Оно определяется количеством различных истинностных таблиц, которые могут быть составлены на этих атрибутах, поскольку функция определятся своей истинностной таблицей. Истинностная таблица имеет 2" строк, так как для описания вариантов входных данных применяется и атрибутов.
Столбец "ответов" такой таблицы может рассматриваться как число, состояшее из Глава 18. Обучение на основе наблюдений 873 Индуктивный вывод деревьев решений на основе примеров Пример для булева дерева решений состоит из вектора входных атрибутов хи одного булева выходного значения у. Множество примеров (Х„у,), ..., (Х„,у„] показано в табл. 18.1. Положительными примерами являются те, в которых цель в7111вгазс имеет истинное значение (х,, х„.. ), а отрицательными — те, в которых эта цель имеет ложное значение (Х,, Х,, ... ) . Полное множество примеров называется гж обучающим множеством.
Таблипа 18.1. Примеры лля проблемной области зааачн с рестораном Атрибуты Цель Пример А)г Ват рт( Наи Ра( Росс Ка(и Ксз Туре Еаг тугвтуа)г УЕя гти гти УЕя 5ОтЕ *** гЧО УЕя РГЕПОВ 0-10 УЕя Хг Лго Лго Тла 9'. Уея Лго Лго г'ея Ри11 * 30 — 60 лго Хг Но Но Вигяег 0-10 Уея Воте * Хг Но Уея Во Во Уея Во Тнат Уея Но Уея Уея Ри11 * Уея Уея Лго Уея Лго Ри11 *** Лго Уея Ргепо)г 760 Во Хб 1"ея Уея геа19'.ап 0-).0 Уея Уея Лго Вигяег 0-10 Но гзо Уея Лго Уея Воте ** Хб агапе * Хг Л'о 1"ее Л'о Лго О-10 Уея Лби Лго гто Уея 5оте ** Уея Уея Тваг Хб Уея Лго Вигяег 760 Во Во Уея Уея Л)о Ри11 * Хг Уея Уея Уея Уея Ри11 *** Л7О Уея гга1гап 10-30 Лго Хг9 твдг 0-10 Лго Во Но Но Л)о лопе * Уея Уея Уея Уея Ги11 * Хи Лго Но Лго Но Вигяег 30-60 Уея Хгг Проблема поиска дерева решений, которое согласуется с обучающим множеством, на первый взгляд может показаться сложной, но фактически имеет простейшее решение.
Можно просто сформировать дерево решений, в котором имеется по одному пути к листовому узлу для каждого примера, где в пути проверяется каждый атрибут по очереди и происходит переход к значению для данного примера, а листовой узел содержит классификацию лля данного примера. После повторного поступления того же примера' дерево решений обеспечивает правильную классификацию. Но, к сожалению, оно не позволяет учесть какие-либо иные случаи! 3 При этом нужно различать тот жс пример или пример с тем жс описанием; зто различие очень важно, н мы всрнсмся к нему а главе ) 9. 2" битов, которое определяет функцию. Независимо от того, какое представление используется для функций, некоторые из функций (а фактически почти все) должньг потребовать для своего представления именно такое количество битов.
Если лля определения функции требуется 2" битов, то существует 2' различных функций от п атрибутов. Это число является весьма обескураживающим. Например, при наличии лишь шести булевых атрибутов существует гб 2' = 18 446 744 073 709 551 616 различных функций, из числа которых может быть сделан выбор. Для поиска совместимых гипотез в таком большом пространстве потребуется некоторые остроумные алгоритмы. 874 Часть М. Обучение Недостатком такого простейшего дерева решений является то, что в нем просто запоминаются результаты наблюдений.
Оно не позволяет извлечь какие-либо закономерности из примеров, поэтому нельзя надеяться на то, что оно даст возможность экстраполировать примеры, которые еще не встречались. Применяя принцип бритвы Оккама, необходимо вместо этого найти наименьшее дерево решений, совместимое с рассматриваемым примером. К сожалению, применительно к любому обоснованному определению понятия "наименьший" задача поиска наименьшего дерева является трудноразрешимой. Однако с помощью некоторой простой эвристики можно многого достичь в направлении поиска "меньшего" дерева. Основная идея, лежащая в основе алгоритма Ресзэзоп-тгее-ьеагпгпд, состоит в том, что в первую очередь следует проверять наиболее важный атрибут. Под "наиболее важным" атрибутом подразумевается такой атрибут, который вносит наибольшее различие в классификацию примера.
Таким образом, можно рассчитывать на обеспечение правильной классификации с помощью небольшого количества проверок, а это означает, что все пути в дереве будут короткими, а само дерево в целом окажется небольшим. На рис. 18.3 показано, как начинается работа алгоритма. Ему предъявляются 12 обучающих примеров, которые классифицированы на множества положительных и отрицательных примеров. После этого принимается решение о том, какой атрибут должен использоваться для первой проверки дерева.
На рис. 18.3, а показано, что туре — неподходящий атрибут, поскольку после его проверки остаются четыре возможных результата, каждый из которых содержит одинаковое количество положительных и отрицательных примеров. С другой стороны, на рис. 18.3, б можно вилеть, что Ра г гопэ — довольно важный атрибут, поскольку если его значение равно иоле или Боте, то остаются такие множества примеров, для которых можно сразу же получить определенный ответ (ГГо и уев соответственно).
А если значением является ди22, то остается смешанное множество примеров. Вообще говоря, после того, как проверка первого атрибута разбивает множество примеров на подмножества, каждый результат сам становится определением новой задачи обучения дерева решений с меньшим количеством примеров и количеством атрибутов, сократившимся на единицу. Ниже описаны четыре случая, которые следует рассматривать при анализе подобных рекурсивных задач. 1.
Если имеются некоторые положительные и отрицательные примеры, то следует выбрать наилучший атрибут для выполнения по нему разбиения. Как показано на рис. 18.3, б, для разбиения оставшихся примеров используется атрибут нипсгту. 2. Если все оставшиеся примеры являются положительными (или отрицательными), то работа закончена и можно дать ответ уев или вга. На рис. 18.3, б показаны примеры достижения этой цели в случаях дГопе и Боте.
3. Если не осталось ни одного примера, это означает, что соответствующие примеры не наблюдались, поэтому следует возвратить применяемое по умолчанию значение, вычисленное на основании мажоритарной классификации в родительском узле данного узла. 4. Если не осталось ни одного атрибута, но имеются и положительные и отрицательные примеры, то налицо проблема.
Такая ситуация означает, что данные примеры имеют полностью одинаковое описание, но классифицированы по- Г «и !Я ~Ж ~ цм м~ 'м е и Я.~ и й 87~ Чз -и, Ъ1! ГЪ6 и юи 877 Глава 18. Обучение на основе наблюдений дерево? Ниже, после рассмотрения подробных сведений об этапе выбора атрибутов, будет показано, как проводить экспериментальный анализ этого вопроса.
Выбор проверок атрибутов Подход к выбору атрибутов, используемый в обучении дерева решений, предназначен для минимизации глубины окончательно сформированного дерева. Идея этого подхода состоит в том, что следует выбирать в первую очередь такой атрибут, который позволяет сразу же выполнить максимально возможный объем работы по обеспечению правильной классификации примеров.
Илеальный атрибут позволяет разделить множество примеров на подмножества, целиком состоящие из положительных или отрицательных примеров. Атрибут ра сгопв не идеален, но является достаточно приемлемым. С другой стороны, действительно бесполезный атрибут, такой как туре, создает подмножества примеров приблизительно с такими же соотношениями положительных и отрицательных примеров, как и в первоначальном множестве.
Таким образом, нам достаточно лишь определить формальный критерий оценки понятий "достаточно приемлемый" и "действительно бесполезный", после чего появится возможность реализовать функцию С)зооэе-)(сск1Ьцсе, применяемую в алгоритме, который приведен в листинге 18.1. Этот критерий должен принимать максимальное значение, когда атрибут является идеальным, н минимальное значение, когда атрибут полностью бесполезен.
Одним из подходящих критериев является ожидаемый объем Ъ. информации, предоставляемый атрибутом; в данном определении термин "информация" используется в математическом смысле, впервые определенном Шенноном и Уивером (1394]. Чтобы понять суть концепции информации, достаточно представить себе, что она является ответом на вопрос, например, о том, упадет ли подброшенная монета орлом вверх.
Объем информации, содержащийся в ответе на этот вопрос, зависит от наших априорных знаний. Чем меньше мы знаем, тем больше получим информации. В теории информации информационное содержание ответа измеряется в битах. Один бит информации является достаточным для ответа "да" или "нет" на вопрос о том, что полностью неизвестно, например, каков результат подбрасывания подлинной монеты. Вообще говоря, если возможные ответы кь имеют вероятности Р(кь), то информационное содержание 1 фактического ответа определяется с помощью следующего уравнения: Г(Р(к~), ..., Р(к ) ) = ~) -Р(ш) 1одг Р(Ю) Для проверки этого уравнения рассмотрим случай с подбрасыванием подлинной монеты. При этом будет получено следующее: У1 1) 1 1 1 1 г~-,-~ = -21оц22 — 21оп22 = 1 бит 2 2 А если центр тяжести монеты смещен таким образом, что в 99% выпадает орел, то будет получено 1(1/100, 99/100) = О.
08 битов, а поскольку вероятность выпадения орла приближается к 1, информационное содержание фактического ответа приближается к О. 878 Часть |Ч. Обучение Что касается обучения деревьев решений, то необходимо найти ответ на вопрос — какова правильная классификация для данного примера? Правильное дерево решений должно позволить найти ответ на этот вопрос. Оценка вероятностей возможных ответов, полученная перед тем, как будет выполнена проверка какого-либо из этих атрибутов, определяется соотношениями положительных и отрицательных примеров в обучающем множестве.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
