Искусственный интеллект. Современный подход

ОБУЧЕНИЕ АНСАМБЛЯ

До сих пор в этой главе рассматривались методы обучения, в которых для получения предсказаний использовалась отдельная гипотеза, выбранная из пространства rv ютсз. В отличие от этого, идея методов обучения ансамбля состоит в том, что из ространства гипотез следует выбрать целую коллекцию, или так называемый ансамбль гипотез, и в дальнейшем комбинировать предсказания, полученные с помощью гипотез этого ансамбля. Например, может быть сформировано сто разных деревьев решений из одного и того же обучающего множества, после чего проведено голосование для определения наилучшей классификации нового примера.
В основе стремления использовать обучение ансамбля лежит простая причина. Рассмотрим ансамбль из м=5 гипотез и предположим, что их предсказания комбинируются с использованием несложного мажоритарного голосования. Для того чтобы этот ансамбль неправильно классифицировал новый пример, его должны неправильно классифицировать по меньшей мере три из пяти гипотез. Однако вполне можно рассчитывать на то, что данная ситуация является гораздо менее вероятной по сравнению с ошибочной классификацией при использовании единственной гипотезы. Допустим, что предполагается, будто каждая гипотеза hL в ансамбле допускает ошибку с вероятностью р. Иными словами, вероятность того, что случайно выбранный пример будет неправильно классифицирован гипотезой hi9 равна р. Кроме того, допустим, что предполагается, будто ошибки, допущенные с применением каждой гипотезы, являются независимыми. В таком случае, если вероятность р мала, то вероятность одновременного появления большого количества ошибок классификации становится микроскопической. Например, простой расчет (упр. 18.14) показывает, что использование ансамбля из пяти гипотез позволяет сократить частоту ошибок от величины 1/10 до величины меньше чем 1/100. Тем не менее очевидно, что предположение о независимости гипотез неоправданно, поскольку во всех гипотезах, скорее всего, будут возникать одинаковые искажения, вызванные одними и теми же искажающими их аспектами одинаковых обучающих данных. Но если гипотезы хоть немного отличаются друг от друга, что приводит к уменьшению корреляции между их ошибками, то обучение ансамбля может оказаться очень полезным.
Еще один способ трактовки идеи ансамбля состоит в том, что ансамбль — это универсальный метод расширения пространства гипотез. Это означает, что сам ансамбль может рассматриваться как гипотеза, а новое пространство гипотез — как множество всех возможных ансамблей, которые могут быть сформированы из гипотез первоначального пространства. Как показано на рис. 18.6, такой подход может привести к созданию более выразительного пространства гипотез. Если первоначальное пространство гипотез допускает возможность использовать простой и эффективный алгоритм обучения, то метод формирования ансамбля предоставляет возможность формировать в процессе обучения гораздо более выразительный класс гипотез без значительного дополнительного увеличения вычислительной или алгоритмической сложности.
Наиболее широко используемый метод формирования ансамбля называется усилением. Для того чтобы понять, как он работает, необходимо вначале ознакомиться с идеей взвешенного обучающего множества. В таком обучающем множестве с каждым примером связан вес Wj>0. Чем больше вес примера, тем выше важность, присвоенная ему в процессе изучения какой-то гипотезы. Рассматриваемые до сих пор в этой главе алгоритмы обучения несложно модифицировать для работы со взвешенными обучающими множествами.
Процедура усиления начинается с задания Wj = l для всех примеров (т.е. с обычного обучающего множества). На основании этого множества вырабатывается первая гипотеза hl9 которая классифицирует одни обучающие примеры правильно, а другие — неправильно. Желательно, чтобы следующая гипотеза лучше справлялась с неправильно классифицированными примерами, поэтому веса последних увеличиваются, а веса правильно классифицированных примеров уменьшаются. По этому обучающему множеству со вновь назначенными весами вырабатывается гипотеза п2. Описанный процесс продолжается таким же образом до тех пор, пока не будет выработано м гипотез, где м становится входом для алгоритма усиления. Окончательная гипотеза-ансамбль представляет собой взвешенную мажоритарную комбинацию из всех м гипотез, каждой из которых назначен вес, соответствующий тому, насколько высокую производительность она показала при обработке обучающего множества. На рис. 18.7 показана концептуальная иллюстрация работы алгоритма. Эта основная идея усиления имеет много вариантов, в которых применяются различные способы корректировки весов и комбинирования гипотез. В листинге 18.2 показан один из конкретных алгоритмов, называемый AdaBoost. Хотя подробные сведения о том, как происходит корректировка весов, не имеет столь важного значения, алгоритм AdaBoost обладает очень важным свойством: если входной обучающий алгоритм L является слабым обучающим алгоритмом (а это означает, что L всегда возвращает гипотезу со взвешенной ошибкой на обучающем множестве, которая лишь ненамного лучше по сравнению со случайным угадыванием, например, равным 50% при булевой классификации), то алгоритм AdaBoost при достаточно большом значении м возвращает гипотезу, идеально классифицирующую обучающие данные. Таким
образом, этот алгоритм значительно повышает точность первоначального обучающего алгоритма применительно к обучающим данным. Такой результат остается в силе независимо от того, насколько невыразительным является первоначальное пространство гипотез, а также от того, насколько сложна изучаемая функция.
Листинг 18.2. Один из вариантов метода усиления для обучения ансамбля, представленный в виде алгоритма AdaBoost. Этот алгоритм вырабатывает гипотезу, последовательно корректируя веса обучающих примеров. Функция Weighted-Majority вырабатывает гипотезу, которая возвращает выходное значение с наивысшими результатами голосования из числа гипотез, относящихся к вектору h, где результаты голосования взвешиваются с помощью вектора z
function AdaBoost(examples, L, M) returns взвешенная мажоритарная комбинация гипотез inputs: examples, множество из N размеченных примеров (xi,yi),..., (xN/yN) L, обучающий алгоритм М, количество гипотез в ансамбле local variables: w, вектор из N весов примеров, первоначально равных 1/N h, вектор из М гипотез z, вектор из М весов гипотез
for т = 1 to М do
h[jn] <— L(examples, w)
error <— 0
for j - 1 to N do
Рассмотрим, насколько хорошо метод усиления действует применительно к данным о ресторане. Выберем в качестве первоначального пространства гипотез класс одноузловых деревьев решений, представляющих собой деревья решений только с одной проверкой, в корневом узле. Нижняя кривая, приведенная на рис. 18.8, я, показывает, что неусиленные одноузловые деревья решений не очень эффективно действуют применительно к этому набору данных, достигая производительности предсказания, составляющей только 81% в расчете на 100 обучающих примеров. А после применения метода усиления (при м=5) производительность становится выше и достигает 93% после обработки 100 примеров.
По мере увеличения размера ансамбля м обнаруживается интересное явление. На рис. 18.8, б показана производительность обучающего множества (на 100 примерах) как функция от м. Обратите внимание на то, что ошибка достигает нуля (как и следует из определения метода усиления), когда Остановится равным 20; это означает, что взвешенная мажоритарная комбинация из 20 одноузловых деревьев решений вполне позволяет определить точное соответствие для 100 примеров. По мере введения в ансамбль дополнительных одноузловых деревьев решений ошибка остается равной нулю. Этот график также показывает, что производительность обработки проверочного множества продолжает возрастать в течение долгого времени после того, как ошибка на обучающем множестве достигает нуля. При М-2 0 производительность на проверочном множестве равна 0,95 (что соответствует 0,05 ошибки) и после чего увеличивается до 0,98 при таком большом значении, как м=13 7, прежде чем постепенно уменьшиться до 0,95.
Эта особенность, которая неизменно проявляется в самых разных наборах данных и пространствах гипотез, после ее обнаружения впервые показалась исследователям весьма неожиданной. Согласно принципу бритвы Оккама, не следует создавать гипотезы, более сложные, чем необходимо, а этот график говорит нам о том, что по мере усложнения гипотезы-ансамбля предсказания улучшаются! Для объяснения этого феномена было предложено несколько трактовок. Один из подходов к анализу такого явления состоит в том, что в процессе усиления аппроксимируется байесовское обучение (см. главу 20), притом что можно доказать, что байесовский алгоритм является оптимальным обучающим алгоритмом, а аппроксимация улучшается по мере введения дополнительных гипотез. Еще одно возможное объяснение состоит в том, что введение дополнительных гипотез позволяет добиться того, что ансамбль проводит все более определенное различие между положительными и отрицательными примерами, а это свойство способствует лучшей классификации новых примеров.