УПРАЖНЕНИЯ
18.1. Рассмотрим проблему, стоящую перед младенцем, который учится говорить и понимать язык. Объясните, как этот процесс вписывается в общую модель обучения, указывая по мере необходимости каждый из компонентов этой модели.
18.2. Повторите упр. 18.1 для случая обучения игре в теннис (или обучения какому-то другому виду спорта, с которым вы знакомы). Относится ли оно по своему типу к контролируемому обучению или обучению с подкреплением?
18.3. Составьте дерево решений для задачи принятия решения о том, следует ли двигаться вперед на уличном перекрестке в той ситуации, когда на светофоре только что загорелся зеленый свет.
18.4. Мы никогда не проверяем дважды один и тот же атрибут вдоль одного пути в дереве решений. Почему этого не делается?
18.5. Предположим, что на основе дерева решений сформировано обучающее множество, а затем к этому обучающему множеству применен алгоритм обучения дерева решений. Можно ли рассчитывать на то, что этот обучающий алгоритм в конечном итоге возвратит правильное дерево, по мере того как размер обучающего множества будет стремиться к бесконечности? Почему да или почему нет?
18.6. Хороший обучающий алгоритм со "спарринг-партнером" состоит в следующем. Вначале создать таблицу из всех обучающих примеров и выяснить, какие выходные результаты встречаются наиболее часто среди всех обучающих примеров; назовем их d. Затем, после получения входных данных, которые отсутствуют в таблице, возвращать просто данные из множества d, а для входных данных, которые имеются в таблице, возвращать связанные с ними выходные данные (если же количество выходных данных больше единицы, возвращать наиболее часто встречающиеся выходные данные). Реализуйте этот алгоритм и определите, насколько хорошо он действует в проблемной области задачи с рестораном. Это позволит вам получить представление о точке отсчета для этой проблемной области — о минимальной производительности, которую должен быть способным достичь любой алгоритм.
18.7. Предположим, что вы проводите эксперименты по обучению с помощью нового алгоритма. У вас имеется набор данных, состоящий из 25 примеров каждого из двух классов. Вы планируете использовать перекрестную проверку с исключением одного примера и для определения точки отсчета выполняете прогон вашей экспериментальной системы на простом мажоритарном классификаторе. (Мажоритарный классификатор получает на входе множество обучающих данных, а затем всегда выводит тот класс, который имеет преимущественное распространение в обучающем множестве, независимо от входных данных.) Вы предполагаете, что мажоритарный классификатор в среднем должен позволить получить оценку около 50% при перекрестной проверке с исключением одного примера, но, к вашему удивлению, он выдает оценку нуль. Можете ли вы объяснить причины, по которым получен такой результат?
18.8. При рекурсивном формировании деревьев решений иногда происходит так,
что в листовом узле остается смешанное множество положительных и отрица-
тельных примеров, даже несмотря на то, что были использованы все атрибуты.
Предположим, что количество положительных примеров равно р, а количест-
во отрицательных примеров — п.
а) Покажите, что решение, используемое в алгоритме Decision-Tree-
Learning, в котором выбирается мажоритарная классификация, мини-
мизирует абсолютную ошибку на множестве примеров в листовом узле.
б) Покажите, что .вероятность класса р/ (р+п) минимизирует сумму
квадратичных ошибок.
18.9. Предположим, что в обучающем алгоритме предпринимается попытка найти совместимую гипотезу, притом что фактически классификации примеров являются случайными. Имеется п булевых атрибутов, а примеры извлекаются с помощью равномерного распределения из множества 2П возможных примеров. Рассчитайте количество примеров, которые требуется получить, прежде чем вероятность обнаружения противоречия в данных достигнет 0,5.
18.10. Предположим, что некоторый атрибут разбивает множество примеров Е на подмножества EL и что каждое подмножество включает pL положительных примеров и ni отрицательных примеров. Покажите, что этот атрибут строго обеспечивает положительное приращение информации, если отношение Pi/ (Pi+i) не является одинаковым для всех i.
18.11. Модифицируйте алгоритм Decision-Tree-Learning, для того чтобы в нем применялось х2-отсечение. Для ознакомления с подробными сведениями по этой теме вам может потребоваться обратиться к [1257].
18.12. (Sfe] В стандартном алгоритме Decision-Tree-Learning, описанном в данной главе, не учитываются такие случаи, в которых отдельные примеры имеют отсутствующие значения атрибутов.
а) Прежде всего необходимо найти способ классификации таких примеров, если дано дерево решений, включающее проверки по атрибутам, для которых могут отсутствовать значения. Предположим, что в некотором примере X отсутствует значение для атрибута А и что в дереве решений выполняется проверка атрибута А в узле, достигнутом примером X. Один из способов справиться с такой ситуацией состоит в том, чтобы предположить, что в этом примере заданы все возможные значения для данного атрибута, но взвесить каждое значение с учетом его частоты среди всех примеров, достигших этого узла в дереве решений. Алгоритм классификации должен проследовать по всем ветвям в каждом узле, для которого
отсутствует некоторое значение, и умножить полученные значения на веса вдоль каждого пути. Напишите модифицированный алгоритм классификации для деревьев решений, который действует по такому принципу, б) Теперь необходимо внести изменения в расчеты приращения информации таким образом, чтобы в любой конкретной коллекции примеров С в любом конкретном узле дерева в процессе его формирования в качестве значений любого из оставшихся атрибутов присваивались "предполагаемые" величины, соответствующие частотам этих значений в множестве С.
18.13. В данной главе было отмечено, что при использовании атрибутов со многими различными возможными значениями могут возникать проблемы, связанные с применением критерия приращения информации. Такие атрибуты, как правило, разбивают примеры на многочисленные небольшие классы или даже одноэлементные классы, из-за чего они начинают казаться в высшей степени релевантными в соответствии с критерием приращения информации. Критерий коэффициента приращения позволяет выбирать атрибуты с учетом отношения между соответствующим им приростом и свойственным им информационным содержанием, т.е. количеством информации, содержащемся в ответе на вопрос: "Каково значение этого атрибута?" Поэтому при использовании критерия коэффициента приращения предпринимается попытка измерить, насколько полно этот атрибут предоставляет информацию о правильной классификации некоторого примера. Запишите математическое выражение для информационного содержания атрибута и реализуйте критерий коэффициента приращения в алгоритме Decision-Tree-Learning.
18.14. Рассмотрите алгоритм обучения ансамбля деревьев решений, в котором используется простое мажоритарное голосование среди м изучаемых гипотез. Предположим, что каждая гипотеза имеет ошибку е и что ошибки, допущенные в каждой гипотезе, не зависят от ошибок в других гипотезах. Составьте формулу для ошибки в алгоритме обучения ансамбля в терминах Ми е и проведите по ней вычисления для тех случаев, когда м=5, 10 и 2 0, а Е=0 .1, 0.2 и 0.4. Возможно ли, что ошибка алгоритма обучения ансамбля будет хуже, чем е, если предположение о независимости будет исключено?
18.15. Это упражнение касается вопроса о выразительности списков решений (раздел 18.5).
а) Покажите, что списки решений позволяют представить любую булеву
функцию, если размер проверок не ограничен.
б) Покажите, что если проверки могут включать самое большее к литералов
каждая, то списки решений позволяют представить любую функцию, ко-
торая может быть представлена с помощью дерева решений с глубиной к.