Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 245
Текст из файла (страница 245)
Совместно с Майклом Кернсом [783] Валиант показал, что задача РАС-обучения некоторых классов концепций является трудноразрешимой, даже если в примерах присутствует достаточный объем информации. Некоторые положительные результаты были получены для таких классов, как списки решений [1293]. В статистике сложилось независимое направление анализа выборочной сложности, начиная с одной важной работы Вапника и Червоненкиса по ж теории равномерной сходимости [1538]. Понятие так называемой 'в.
УС-размериости (УС вЂ” сокращение от Уарп!й — С[зегхопепЫз) позволяет получить критерий, приблизительно аналогичный, но более обший, чем критерий 2п] гг ~, полученный на основе анализа РАС-обучения. В частности, критерий УС-размерности может применяться к непрерывным классам функций, на которые не распространяется стандартный анализ РАС-обучения. Теория РАС-обучения и теория УС-размерности были впервые связаны в единое целое группой ученых, называемых "четырьмя немцами" (хотя ни один из них фактически не является немцем), — Блумером, Эренфойхтом, Хаусслером и Вармутом [141]. Дальнейшие исследования в области теории УС-размерности привели к открытию понятия машины поддерживающих векторов, или БУМ (Бпрроп Уес!ог Мас)ппе) [156], [1537], которая будет описана в главе 20.
Большое количество важных статей по машинному обучению было собрано в книге Яеаг((пхзш Масйте Теагтп8 [1399]. Кроме того, много важных статей, а также огромные библиографические справочники содержатся в двух томах, МасЬие йеагптк 1 [1039] и Масйте Т.епгят8 2 [1040]. В [! 565] дано широкое введение в область методов изучения функций, применяемых в машинном обучении, статистике и нейронных сетях.
Исследования, намного превосходяшие по своей широте все прочие работы в области сравнения производительности обучаюших алгоритмов, 899 Глава 18. Обучение на основе наблюдений были проведены в рамках проекта 5гайо8 (Н047]. Результаты продуктивных современных исследований по машинному обучению публикуются в ежегодном сборнике трудов конференций 7п!егпапвлл! Соп~егелсе ол МасЫпе ?еагтлк и Сол(егепсе ол селга! !луогтаг(оп Ргосеззтх 5узгетз, в журналах МасМпе ?.еаглщх и золгла! о7 Масйле ?еигл(лл Яезеагсл, а также в основных журналах по искусственному интеллекту.
Кроме того, трупы в области теории вычислительного обучения публикуются в материалах ежегодного семинара АСМ И Ьг)сговор ол Соглришггола(?еагл(л8 ?леогу (СО( Т), а само это направление представлено в книгах (34) и (786). УП РАЖ Н ЕН ИЯ 18.1. Рассмотрим проблему, стоящую перед младенцем, который учится говорить и понимать язык. Объясните, как этот процесс вписывается в общую модель обучения, указывая по мере необходимости каждый из компонентов этой модели.
18.2. Повторите упр. (8А для случая обучения игре в теннис (или обучения какомуто другому виду спорта, с которым вы знакомы). Относится ли оно по своему типу к контролируемому обучению или обучению с подкреплением? 18.3. Составьте дерево решений для задачи принятия решения о том, следует ли двигаться вперед на уличном перекрестке в той ситуации, когда на светофоре только что загорелся зеленый свет. 18.4. Мы никогда не проверяем дважды один и тот же атрибут вдоль одного пути в дереве решений. Почему этого не делается? 18.5.
Предположим, что на основе дерева решений сформировано обучающее множество, а затем к этому обучающему множеству применен алгоритм обучения дерева решений. Можно ли рассчитывать на то, что этот обучающий алгоритм в конечном итоге возвратит правильное дерево, по мере того как размер обучающего множества будет стремиться к бесконечности? Почему да или почему нет? 18.6. Хороший обучающий алгоритм со "спарринг-партнером" состоит в следующем.
Вначале создать таблицу из всех обучающих примеров и выяснить, какие выходные результаты встречаются наиболее часто среди всех обучающих примеров; назовем их й. Затем, после получения входных данных, которые отсутствуют в таблице, возвращать просто данные из множества с(, а для входных ланных, которые имеются в таблице, возвращать связанные с ними выходные данные (если же количество выходных данных больше единицы, возвращать наиболее часто встречающиеся выходные данные). Реализуйте этот алгоритм и определите, насколько хорошо он действует в проблемной области задачи с рестораном. Это позволит вам получить представление о точке отсчета для этой проблемной области — о минимальной производительности, которую должен быть способным достичь любой алгоритм.
18.7. Предположим, что вы проводите эксперименты по обучению с помощью нового алгоритма. У вас имеется набор данных, состоящий из 25 примеров каждого из двух классов. Вы планируете использовать перекрестную проверку с исключением одного примера и для определения точки отсчета выполняете прогон вашей экспериментальной системы на простом мажоритарном клас- 900 Часть Ч(. Обучение сификаторе. (Мажоритарный классификатор получает на входе множество обучающих данных, а затем всегда выводит тот класс, который имеет преимущественное распространение в обучающем множестве, независимо от входных данных.) Вы предполагаете, что мажоритарный классификатор в среднем должен позволить получить оценку около 50% при перекрестной проверке с исключением одного примера, но, к вашему удивлению, он выдает оценку нуль.
Можете ли вы объяснить причины, по которым получен такой результат? При рекурсивном формировании деревьев решений иногда происходит так, что в листовом узле остается смешанное множество положительных и отрицательных примеров, даже несмотря на то, что были использованы все атрибуты. Предположим, что количество положительных примеров равно р, а количество отрицательных примеров — п. а) Покажите, что решение, используемое в алгоритме песзэьоп-Тгеепеагпьпд, в котором выбирается мажоритарная классификация, минимизирует абсолютную ошибку на множестве примеров в листовом узле. б) Покажите, что 'ек вероятность класса р7 (р~-и) минимизирует сумму квадратичных ошибок.
Предположим, что в обучающем алгоритме предпринимается попытка найти совместимую гипотезу, притом что фактически классификации примеров являются случайными. Имеется и булевых атрибутов, а примеры извлекаются с помощью равномерного распределения из множества 2" возможных примеров. Рассчитайте количество примеров, которые требуется получить, прежде чем вероятность обнаружения противоречия в данных достигнет 0,5. 18.8.
18.9. 18.10. Предположим, что некоторый атрибут разбивает множество примеров к на подмножества я, и что каждое подмножество включает р, положительных примеров и п, отрицательных примеров. Покажите, что этот атрибут строго обеспечивает положительное приращение информации, если отношение р,/ (р,+и,) не является одинаковым для всех 1. 18.11. Модифицируйте алгоритм песзэьоп-тгее-пеатпзпд, для того чтобы в нем применялось 2'-отсечение. Для ознакомления с подробными сведениями по этой теме вам может потребоваться обратиться к [1257].
ной главе, не учитываются такие случаи, в которых отдельные примеры имеют отсутствующие значения атрибутов. а) Прежде всего необходимо найти способ классификации таких примеров, если дано дерево решений, включающее проверки по атрибутам, для которых могут отсутствовать значения. Предположим, что в некотором примере зг отсутствует значение для атрибута л и что в дереве решений выполняется проверка атрибута л в узле, достигнутом примером х.
Один из способов справиться с такой ситуацией состоит в том, чтобы предположить, что в этом примере заданы все возможные значения для данного атрибута, но взвесить каждое значение с учетом его частоты среди всех примеров, достигших этого узла в дереве решений. Алгоритм классификации должен проследовать по всем ветвям в каждом узле, для которого 18.12. Й В стандартном алгоритме песзвйоп-ттее-г.ес спьпд, описанном в дан- Глава 18, Обучение на основе наблюдений 901 отсутствует некоторое значение, и умножить полученные значения на веса вдоль каждого пути.
Напишите модифицированный алгоритм классификации для деревьев решений, который действует по такому принципу. б) Теперь необходимо внести изменения в расчеты приращения информации таким образом, чтобы в любой конкретной коллекции примеров С в любом конкретном узле дерева в процессе его формирования в качестве значений любого из оставшихся атрибутов присваивались "предполагаемые" величины, соответствующие частотам этих значений в множестве С. 18.13. В данной главе было отмечено, что при использовании атрибутов со многими различными возможными значениями могут возникать проблемы, связанные с применением критерия приращения информации. Такие атрибуты, как правило, разбивают примеры на многочисленные небольшие классы или даже одноэлементные классы, из-за чего они начинают казаться в высшей степени релевантными в соответствии с критерием приращения информации.
Критерий коэффициента приращения позволяет выбирать атрибуты с учетом отношения между соответствующим им приростом и свойственным им информационным содержанием, т.е. количеством информации, содержащемся в ответе на вопрос "Каково значение этого атрибута?" Поэтому при использовании критерия коэффициента приращения предпринимается попытка измерить, насколько полно этот атрибут предоставляет информацию о правильной классификации некоторого примера. Запишите математическое выражение для информационного содержания атрибута и реализуйте критерий коэффициента приращения в алгоритме пес1вйоп-тгее-г.еагп1пд.
18.14. Рассмотрите алгоритм обучения ансамбля деревьев решений, в котором используется простое мажоритарное голосование среди и изучаемых гипотез. Предположим, что каждая гипотеза имеет ошибку е и что ошибки, допущенные в каждой гипотезе, не зависят от ошибок в других гипотезах. Составьте формулу для ошибки в алгоритме обучения ансамбля в терминах зчи е и проведите по ней вычисления для тех случаев, когда М=5, 10 и 20, а е=О. 1, О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
