ФОРМИРОВАНИЕ ДЕРЕВЬЕВ РЕШЕНИЙ НА ОСНОВЕ ОБУЧЕНИЯ

Индуктивный логический вывод деревьев решений представляет собой одну из простейших и вместе с тем наиболее успешных форм алгоритмов обучения. Эта тема может служить хорошим введением в проблематику индуктивного обучения, а алгоритмы, разработанные в ее рамках, легко поддаются реализации. В настоящем разделе вначале описан производительный элемент проекта агента, а затем показано, как обеспечить его обучение. В ходе этого изложения представлены основные понятия, которые применяются во всех областях индуктивного обучения.
Деревья решений, рассматриваемые как производительные элементы
Дерево решений принимает в качестве входных данных объект или ситуацию, описанную с помощью множества атрибутов, и возвращает "решение" — предсказанное выходное значение, соответствующее входным данным. Входные атрибуты могут быть дискретными или непрерывными. На данный момент подразумевается, что входные данные являются дискретными. Выходные значения также могут быть дискретными или непрерывными; процесс формирования в ходе обучения функции с дискретными значениями называется обучением классификации; формирование в ходе обучения непрерывной функции называется обучением регрессии. Вначале мы сосредоточимся на булевой классификации, согласно которой каждый пример обозначается как истинный положительный) или ложный
отрицательный).
Дерево решений позволяет перейти к содержащемуся в нем решению путем выполнения последовательности проверок. Каждый внутренний узел в дереве соответствует проверке значения одного из свойств, а ветви, исходящие из этого узла, обозначены возможными значениями результатов проверки. Каждый листовой узел в дереве задает значение, возвращаемое после достижения этого листа. По-видимому, представление в виде дерева решений кажется людям вполне естественным; в действительности многие инструктивные руководства (например, по ремонту автомобилей) полностью оформлены в виде одного дерева решений, разбросанного по нескольким сотням страниц.
Несколько более простой пример может быть основан на применении методов обучения к задаче, в которой клиент ждет, пока освободится место за столиком в ресторане. Цель состоит в том, чтобы изучить определение для целевого предиката WillWait (Следует ли ждать). Подготавливая данный пример для использования в качестве задачи обучения, необходимо вначале определить, какие атрибуты доступны для описания примеров ситуаций в данной проблемной области. В главе 19 будет показано, как автоматизировать выполнение этого этапа, а на данный момент предположим, что решено использовать приведенный ниже список атрибутов.
1. AI terna te (Альтернативный вариант). Есть ли поблизости подходящий ресторан такого же класса.
Ваг (Бар). Имеется ли в ресторане уютный бар, в котором можно подождать.
Fri /Sat (Уик-энд). Принимает истинное значение по пятницам и субботам.
Hungry (Чувство голода). Испытывает ли посетитель чувство голода.
Patrons (Посетители). Сколько людей находится в ресторане; значениями этого атрибута являются None (Ресторан пуст), Some (В ресторане есть посетители) и Full (Ресторан заполнен).
Price (Цены). Ценовая категория ресторана (*, **, ***).
Raining (Дождь). Идет ли дождь на улице.
Reservation (Бронирование). Забронировано ли место за посетителем.
Туре (Тип). Тип ресторана (ресторан с французской (French), итальянской (Italian), тайской (Thai) кухней или ресторан-закусочная (Burger)).
10. WaitEstimate (Оценка продолжительности ожидания). Продолжительность ожидания, оценка которой сделана метрдотелем (0-10, 10-30, 30-60, >60 минут).
Дерево решений, обычно используемое одним из авторов (Стюартом Расселом), для данной проблемной области, показано на рис. 18.2. Обратите внимание на то, что в этом дереве не используются атрибуты Price и Туре; по сути это означает, что лицо, принимающее решение, рассматривает их как малозначимые. Обработка примеров ситуаций с помощью этого дерева начинается от корня и проходит по соответствующей ветви до тех пор, пока не будет достигнут какой-то лист. В частности, пример ситуации, в которой Patrons=Full и WaitEstimate= 0-10 будет рассматриваться как положительный (да, следует дождаться освобождения столика).







Материалы

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