Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 239
Текст из файла (страница 239)
Предположим, что обучающее множество включает р положительных примеров и л отрицательных. В таком случае оценка информации, содержащейся в правильном ответе, равна: р и 1 р Р Л л 1од~ 1одг р+л р+и/ р+и р+п рел р+л Обучающее множество для задачи с рестораном, приведенное в табл. 18.1, включает количество примеров р=п= 6, поэтому требуется 1 бит информации. Теперь отметим, что обычно проверка по одному атрибуту А не позволит нам получать такой объем информации, но по меньшей мере предоставит часть этой информации.
Мы можем точно измерить, какова эта часть, определяя, сколько еше информации нам потребуется после проверки этого атрибута. Любой атрибут А делит обучающее множество я на подмножества Е,, ..., Е, в соответствии со значениями атрибута А, если А может иметь и различных значений. Каждое подмножество Яз включает р, положительных примеров и л, отрицательных примеров, поэтому после перехода по ветви этого атрибута нам потребуется дополнительно Т(р,/ (р,+и,), и,/ (рь+и,) ) битов информации, чтобы ответить на вопрос. Случайно выбранный пример из обучающего множества содержит 1-е значение рассматриваемого атрибута с вероятностью (р,+и,) 7 (р+л), поэтому в среднем после проверки атрибута А для классификации данного примера потребуется показанное ниже количество бит информации.
"рьи ( р, л, Леоавлбеп(А) = ~ ' * 1 ~ р + и 1 р + и, р, -> и, 2 'в. Приращение информации, полученное в результате проверки атрибута, представляет собой разность между первоначальной потребностью в информации и новой потребностью: Вавл (А) = 1, — — летаТпоел(А) р л рел р+и Эвристика, используемая в функции С)зооэе-)(ссху)зисе, состоит в том, что следует выбирать атрибут с наиболыпим приращением. Возвращаясь к атрибутам, показанным на рис. 18.3, получаем следующее: Г2 4 б 2 41 ВаЯл(раз голе) = 1 — ~ — Г(0, 1) Ь вЂ” 1(1, О) + — 1(-, — )~ = О.
541 бит 'ь12 12 12 5 б ~ Г2 1 1 2 1 1 4 2 2 4 2 21 Ва1п(туре) = 1 — — 1( —, -) е — 1(-, -) + — 1( —, — ) 4 — Е( —, — ) = 0 (12 2 2 12 2 2 12 4 4 12 4 4~ Глава 18. Обучение на основе наблюдений 879 Эти соотношения подтверждают интуитивное предположение о том, что Раскопа — наилучший атрибут, по которому следует выполнять разбиение. В действительности атрибут раскопа позволяет получить наибольшее приращение информации по сравнению с любыми другими атрибутами и должен быть выбран алгоритмом обучения дерева решений в качестве корневого. Оценка производительности обучающего алгоритма Обучающий алгоритм является приемлемым, если он вырабатывает гипотезы, обеспечивающие качественные предсказания в отношении того, к какому классу будут относиться еше не встречавшиеся примеры.
В разделе 18.5 будет показано, как можно заранее оценить качество предсказания. А в данном разделе рассматривается методология оценки качества предсказания после его фактического получения. Очевидно, что предсказание является качественным, если оказалось, что оно— истинное, поэтому можно оценить качество гипотезы, сверяя ее предсказания с правильной классификацией после того, как она становится известной. Такая задача осуществляется с помощью множества примеров, которые принято называть 'сь проверочным множеством.
Дело в том, что если обучение проведено по всем доступным примерам, то приходится возвращаться к действительности и заниматься подбором дополнительных примеров для проведения по ним проверки, поэтому чаше более удобно использовать описанную ниже методологию. 1. Собрать множество примеров большого объема. 2. Разделить его на два непересекаюшихся подмножества: обучаюшее множество и проверочное множество. 3.
Применить обучаюший алгоритм к обучающему множеству для формирования гипотезы )з. 4. Определить, какой процент примеров в проверочном множестве правильно классифицируется с помощью гипотезы й. 5. Повторять этапы 2 — 4 для различных размеров обучающих множеств и различных случайно выбранных обучаюших множеств каждого размера. Результатом применения этой процедуры становится набор данных, которые можно обрабатывать для получения среднего качества предсказаний, которое выражается в виде некоторой функциональной зависимости от размера обучаюшего множества.
Эта функция может быть изображена в виде графика, представляюшего собой так называемую 'в. кривую обучения для данного алгоритма в данной конкретной проблемной области. Кривая обучения для алгоритма пествгоп-тгеег.еагпйпд, полученная с использованием примеров из задачи с рестораном, показана на рис. 18.5. Обратите внимание на то, что качество предсказания повышается по мере увеличения размера обучающего множества (по этой причине подобные кривые часто называют счастливыми графиками). Это — хороший признак, который показывает, что в данных действительно есть какие-то повторяющиеся шаблоны (закономерности) и обучаюший ачгоритм их выделяет.
Безусловно, что обучаюшему алгоритму не должно быть разрешено "касаться" проверочных данных перед тем, как по ним будет проверена изученная гипотеза. К сожалению, часто очень легко можно попасть в ловушку, связанную с тем, что 880 Часть ггг. Обучение алгоритм ск компрометирует проверочные данные.
Компрометация обычно происходит следующим образом: в обучающем алгоритме могут быть предусмотрены всевозможные "регуляторы", предназначенные для настройки его поведения, например различные и разнотипные критерии выбора следующего атрибута в процессе обучения дерева решений. Итак, формируются гипотезы для всевозможных различных установок этих регуляторов, измеряется их производительность на проверочном множестве и формируется отчет о производительности предсказания наилучшей гипотезы. К сожалению, при этом происходит компрометация! Причина этого состоит в том, что гипотеза была выбрана по результатам измерения ее производительности на проверочном множестве, поэтому информация о проверочном множестве проникла в обучающий алгоритм.
Мораль этой истории состоит в том, что в любом процессе, предусматривающем сравнение производительностей гипотез на проверочном множестве, необходимо использовать новое проверочное множество для измерения производительности окончательно выбранной гипотезы. Но на практике такой подход осуществить слишком сложно, поэтому исследователи по-прежнему продолжают выполнять эксперименты на бывших в употреблении множествах примеров. о~ИОВ и Ы И 0,8 3 Я 0,7 й а о сего 05 ол 0 20 40 60 80 100 Размер обггаюшего нножссгаа Рис.!8.5. Кривая обучения для алгоритма обучения дерева решений на 700 случайно сформированных примерок в проблемной области задачи с рестораном.
В атом графике подытожены результаты 20 попыток Шум и чрезмерно тщательная подгонка Как было показано выше, если имеются два или несколько примеров с одинаковым описанием (с точки зрения атрибутов), но с разными классификациями, то работа алгоритма гзесйв1оп-0 сее-ьес спьпд обязательно окончится неудачей, поскольку невозможно будет найти дерево решений, совместимое со всеми примерами.
Кроме того, уже упоминалось, что приемлемый способ решения этой проблемы может предусматривать либо применение в каждом листовом узле мажоритарной классификации для относягцегося к нему множества примеров (если требуется детерминированная гипотеза), либо формирование оценок вероятностей каждой классификации с использованием относительных частот.
К сожалению, описанные выше ситуации не исчерпывают перечень всех возможных нарушений в процессе фор- Глава 18. Обучение на основе наблюдений 88! мирования дерева решений. Вполне возможна такая ситуация (которая действительно часто встречается на практике), что алгоритм обучения деревьев решений формирует дерево решений, совместимое со всеми примерами, даже несмотря на то, что эти примеры не содержат крайне важной информации для данной задачи классификации. Это связано с тем, что в рассматриваемом алгоритме могут использоваться не относящиеся к делу атрибуты (если они имеются), в результате чего проводятся несуществующие различия между примерами.
Рассмотрим задачу, в которой осуществляются попытки предсказать результаты броска игральной кости. Предположим, что эксперименты проводятся в течение продолжительного периода времени с различными игральными костями и что атрибуты, описывающие каждый обучающий пример, являются следующими: 1. пау (День недели). День, в который был выполнен бросок игральной кости (1чоп (Понедельник), тце (Вторник), 1уес) (Среда), тЬи (Четверг)).
2. 1чопсЬ (Месяц). Месяц, в который был выполнен бросок игральной кости (.тап (Январь) или деЬ (Февраль)). 3. Со2оз-(Цвет). Цвет игральной кости (пес1(Красный) или п2ие(Синий)). При условии, что не существует двух примеров с одинаковыми описаниями и разными классификациями, алгоритм Гзес1в топ-Тгее-Пеагпупд позволяет найти точную гипотезу. Чем больше количество используемых атрибутов, тем выше вероятность, что будет найдена точная гипотеза.
Но все такие гипотезы будут полностью не связанными с действительностью, поскольку рассматриваемые атрибуты не влияют на выпадение игральной кости. Требуется лишь то, чтобы алгоритм Песхвзоп-Тгее-Ьеатпзпд возвратил единственный листовой узел с вероятностями, близкими к 1/6, для каждого результата выпадения очков на игральной кости, как только будет получено достаточное количество примеров. Каждый раз, когда приходится сталкиваться с множеством возможных гипотез, имеющим большой объем, необходимо тщательно следить за тем, чтобы возникающая при этом свобода выбора не использовалась для поиска бессмысленных "закономерностей" в данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
