Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 241
Текст из файла (страница 241)
Обучающий алгоритм должен выработать решение о том, когда следует прекратить разбиение и приступить к применению метода линейной регрессии с использованием оставшихся атрибутов (или некоторого их подмножества). Система обучения деревьев решений для реальных приложений должна быть способной решать все эти проблемы. Особенно важной является обработка переменных с непрерывными числовыми значениями, поскольку числовые данные применяются, например, в физических и финансовых процессах.
Было разработано несколько коммерческих пакетов, соответствующих этим критериям, которые использовались для создания нескольких сотен проблемно-ориентированных систем. Во многих областях промышленности и торговли деревья решений обычно становятся первым методом, к которому пытаются прибегнуть, когда из некоторого набора данных необходимо извлечь соответствующий ему метод классификации.
Одним из важных свойств деревьев решений является то, что вывод обучающего алгоритма доступен для понимания людей (а в действительности в этом также состоит законодательное требование к финансовым решениям, на которые распространяются законы против дискриминации).
Таким свойством не обладают нейронные сети (см. главу 20). 18.4. ОБУЧЕНИЕ АНСАМБЛЯ До сих пор в этой главе рассматривались методы обучения, в которых для полу~сния предсказаний использовалась отдельная гипотеза, выбранная из пространства отез. В отличие от этого, идея методов Ъ. обучения ансамбля состоит в том, что из 885 Глава 18.
Обучение на основе наблюдений пространства гипотез следует выбрать целую коллекцию, или так называемый ансамбль гипотез, и в дальнейшем комбинировать предсказания, полученные с помощью гипотез этого ансамбля. Например, может быть сформировано сто разных деревьев решений из одного и того же обучающего множества, после чего проведено голосование для определения наилучшей классификации нового примера. В основе стремления использовать обучение ансамбля лежит простая причина. Рассмотрим ансамбль из м=б гипотез и предположим, что их предсказания комбинируются с использованием несложного мажоритарного голосования. Для того чтобы этот ансамбль неправильно классифицировал новый пример, его должны неправильно классифицировать по меныцей мере три из пяти гипотез.
Однако вполне можно рассчитывать на то, что данная ситуация является гораздо менее вероятной по сравнению с ошибочной классификацией при использовании единственной гипотезы. Допустим, что предполагается, будто каждая гипотеза Лг в ансамбле допускает ошибку с вероятностью р. Иными словами, вероятность того, что случайно выбранный пример будет неправильно классифицирован гипотезой п„равна р. Кроме того, допустим, что предполагается, будто ошибки, допущенные с применением каждой гипотезы, являются независимыми. В таком случае, если вероятность р мала, то вероятность одновременного появления большого количества ошибок классификации становится микроскопической.
Например, простой расчет (упр. 18.14) показывает, что использование ансамбля из пяти гипотез позволяет сократить частоту ошибок от величины 1/1О до величины меньше чем !/100. Тем не менее очевидно, что предположение о независимости гипотез неоправданно, поскольку во всех гипотезах, скорее всего, будут возникать одинаковые искажения, вызванные одними и теми же искажающими их аспектами одинаковых обучающих данных. Но если гипотезы хоть немного отличаются друг от друга, что приводит к уменьшению корреляции между их ошибками, то обучение ансамбля может оказаться очень полезным.
Еще олин способ трактовки идеи ансамбля состоит в том, что ансамбль — это универсальный метод расширения пространства гипотез. Зго означает, что сам ансамбль может рассматриваться как гипотеза, а новое пространство гипотез — как множество всех возможных ансамблей, которые могут быть сформированы из гипотез первоначального пространства. Как показано на рис. 18.6, такой подход может привести к созданию более выразительного пространства гипотез. Если первоначальное пространство гипотез допускает возможность использовать простой и эффективный алгоритм обучения, то метод формирования ансамбля предоставляет возможность формировать в процессе обучения гораздо более выразительный класс гипотез без значительного дополнительного увеличения вычислительной ипи алгоритмической сложности.
Наиболее широко используемый метод формирования ансамбля называется Ъ. усилением. Для того чтобы понять, как он работает, необходимо вначале ознакомиться с идеей 'ги взвешенного обучающего множества. В таком обучающем множестве с каждым примером связан вес ы;>О. Чем больше вес примера, тем выше важность, присвоенная ему в процессе изучения какой-то гипотезы. Рассматриваемые до сих пор в этой главе алгоритмы обучения несложно модифицировать для работы со взвешенными обучающими множествами'.
' Имеются также такие обучающие алгоритмы, которые ие предосгавяяют подобной возможности. Но дяя иих вместо этого можно создать тиражировавиое обучающее множество, в котором «-й пример появяяется и, раз, а для учета иецепочиспеииых значений весов используется раидомизация. 88б Часть И. Обучение Рис. 18.б. Схема, показывающая, что обучение ансамбля позволяет добиться повышения выразительной мощи гипотез. Здесь представлены три линеиные пороговые гипотезы, каждая из которых формирует пояожительную классификацию на незаштрихованной стороне, а в целом как положительные классифицируются все примеры, которые являются положительными согласно всем трем гипотезам.
Полученная в итоге треугольная область представляет собой гапотезу, которая не может быть выражена в первоначальном пространстве гипотез Процедура усиления начинается с задания ее,=1 для всех примеров (т.е. с обычного обучающего множества). На основании этого множества вырабатывается первая гипотеза Л,, которая классифицирует одни обучающие примеры правильно, а другие — неправильно. Желательно, чтобы следующая гипотеза лучше справлялась с неправильно классифицированными примерами, поэтому веса последних увеличиваются, а веса правильно классифицированных примеров уменьшаются. По этому обучающему множеству со вновь назначенными весами вырабатывается гипотеза )зз. Описанный процесс продолжается таким же образом до тех пор, пока не будет выработано зц гипотез, где 1Ч становится входом для алгоритма усиления. Окончательная гипотеза-ансамбль представляет собой взвешенную мажоритарную комбинацию из всех и гипотез, каждой из которых назначен вес, соответствующий тому, насколько высокую производительность она показыа при обработке обучающего множества.
На рис. 18П показана концептуальная иллюстрация работы алгоритма. Эта основная идея усиления имеет много вариантов, в которых применяются различные способы корректировки весов и комбинирования гипотез. В листинге 18.2 показан один из конкретных алгоритмов, называемый дс)апооэе. Хотя подробные сведения о том, как происходит корректировка весов, не имеет столь важного значения, алгоритм йс1авоовс обладает очень важным свойством: если входной обучающий алгоритм и является 'оь слабым обучающим алгоритмом (а это означает, что ъ всегда возвращает гипотезу со взвешенной ошибкой на обучаюгцем множестве, которая лишь ненамного лучше по сравнению со случайным угадыванием, например, равным 50% при булевой классификации), то алгоритм дс1авооэ с при достаточно большом значении м возвращает гипотезу, идеально классифицирующую обучающие данные.
Таким Часть Ч[. Обучение хЕ Ь[щ] (хз) М Уз Еиеп ехгог < — еггог + ы[ЭЧ Еог у = 1 Ео От([о з е ь [т] (хз) =у, еьеп ы[б] ь — ы[у] еггоз ) (1-еггоз ) ы ь — Ногпщ11ае(ы) г[щ1 < — 1од(1-егзоз)(еггог геепгп нейе)теес)-назог1еу(Ь, г) Рассмотрим, насколько хорошо метод усиления действует применительно к данным о ресторане. Выберем в качестве первоначального пространства гипотез класс 'суъ одноузловых деревьев решений, представляюших собой деревья решений только с одной проверкой, в корневом узле. Нижняя кривая, приведенная на рис. 18.8, а, показывает, что неусиленные одноузловые деревья решений не очень эффективно действуют применительно к этому набору данных, достигая производительности предсказания, составляющей только 81% в расчете на 100 обучающих примеров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
