Методы ансамблирования обучающихся алгоритмов

Транскрипт

1 Министерство образования и науки Российской Федерации Московский физико-технический институт (государственный университет) Факультет управления и прикладной математики Кафедра «Интеллектуальные системы» при Вычислительном центре им. А. А. Дородницына РАН Гущин Александр Евгеньевич Методы ансамблирования обучающихся алгоритмов Прикладные математика и физика Выпускная квалификационная работа бакалавра Научный руководитель: д.ф.-м.н. Дьяконов Александр Геннадьевич Москва 2015 г.

2 Содержание 1 Введение 3 2 Постановка задачи и используемые обозначения 5 3 Обзор известных методов ансамблирования Голосование и смесь экспертов Бустинг Бэггинг Метод случайных подпространств Стекинг Экспериментальная часть Необходимые пояснения Поставленные эксперименты Обобщение результатов экспериментов Заключение 39 2

3 Аннотация В задачах обучения с учителем, в которых требование качества решения превалирует над ограничением его вычислительной сложности, применяются различные способы ансамблирования обучающихся алгоритмов. Одним из наиболее общих и эффективных в смысле достигаемого качества методов ансамблирования является стекинг, идея которого состоит в использовании предсказаний базовых алгоритмов в качестве признаков для некоторого метаалгоритма. Использование предложенных ранее модификаций стекинга для небольших по объему выборок имеет различные ограничения, по большей части связанные с недостаточно эффективным использованием обучающей выборки. В данной работе предлагается модификация стекинга, стремящаяся компенсировать эти недостатки. 1 Введение При решении сложных задач классификации, регрессии, прогнозирования часто оказывается, что ни один из алгоритмов не обеспечивает желаемого качества восстановления зависимости. В таких случаях имеет смысл строить композиции алгоритмов, в которых ошибки отдельных алгоритмов взаимно компенсируются. Наиболее общее определение алгоритмической композиции даётся в алгебраическом подходе Ю. И. Журавлёва [8]. Наряду с множеством объектов и множеством соответствующих им значений целевой функции вводится вспомогательное множество, называемое пространством оценок. Рассматриваются алгоритмы, в которых функция, называющаяся алгоритмическим оператором, устанавливает соответствие между множеством объектов и пространством оценок, а функция, называющаяся решающим правилом, устанавливает соответствие между пространством оценок и множеством значений целевой функции. Таким образом, рассматриваемые алгоритмы имеют вид суперпозиции алгоритмического оператора и решающего правила. Многие алгоритмы классификации имеют именно такую структуру: сначала вычисляются оценки принадлежности объекта классам, затем решающее правило переводит эти оценки в номер класса. Значением оценки может быть вероятность принадлежности объекта классу, расстояние от объекта до разделяющей поверхности, степень уверенности классификации и т. п. Существует несколько наиболее известных методов объединения базовых алгоритмов в композиции: голосование, взвешенное голосование, смесь экспертов (Mixture of Experts [19]). Эти методы часто применяются, когда базовые алгоритмы существенно отличаются друг от друга. В случаях, когда необходимо построить композицию используя один базовый алгоритм, широко применяется бэггинг (bagging, boostrap aggregation) [4]. Идея бэггинга состоит в том, что базовый алгоритм многократно обучается на случайных подвыборках с повторениями из обучающей выборки. Такой метод генерации подвыборок принято называть бутсрап (bootsrap). Похожим на бэггинг методом является метод случайных подпространств (random subspace method, RSM [10]). Его идея заключается в создании вариативности при обучении с помощью выбора случайных подмножеств признаков. Широко известным примером использования бэггинга и RSM является случайный лес [5]. 3

4 Другим известным способом ансамблирования базовых алгоритмов является бустинг. Идея бустинга состоит в жадном выборе очередного алгоритма для добавления в композицию так, чтобы он лучшим образом компенсировал имеющиеся на этом шаге ошибки. Широко известные примеры бустинга AdaBoost [6] и градиентный бустинг (Gradient boosting [7]). Стекинг (Stacked generalization) был впервые предложен Д. Волпертом в 1992 году в работе [2] в достаточно общем виде. Основная идея стекинга заключается в использовании базовых классификаторов для получения предсказаний (метапризнаков) и использовании их как признаков для некоторого обобщающего алгоритма (метаалгоритма). Иными словами, основной идеей стекинга является преобразование исходного пространства признаков задачи в новое пространство, точками которого являются предсказания базовых алгоритмов. Предлагается сначала выбрать набор пар произвольных подмножеств из обучающей выборки, затем для каждой пары обучить базовые алгоритмы на первом подмножестве и предсказать ими целевую переменную для второго подмножества. Предсказанные значения и становятся объектами нового пространства. В частности, автором рассматривается случай выбора всевозможнных пар подмножеств, в которых второе подмножество состоит из единственного объекта, а первое множество из всей обучающей выборки кроме этого объекта (leave-one-out). Очевидно, что такой способ позволяет перевести каждую точку исходного пространства признаков в точку нового пространства. Автор обобщает идею стекинга тем, что предлагает, обучая базовые классификаторы (первого уровня) над метапризнаками (первого уровня), получать метапризнаки второго уровня и так далее. Развитие идеи стекинга для задач многоклассовой классификации происходит в работах [17], [16]. В первой работе предлагается свести задачу мноклассовой классификации к набору задач одноклассовой классификации, которые решают базовые классификаторы, и обучения метаклассификатора над их предсказаниями. Во второй работе предлагается усложнить эту схему с помощью использования дополнительного уровня базовых классификаторов, построенных на предсказаниях базовых классификаторов первого уровня. Стекинг являлся основным способом ансамблирования базовых алгоритмов команд-победителей известного соревнования по машинному обучению Netflix [12]. Командой BigChaos [15] было использовано разбиение обучающей выборки на K непересекающихся блоков (K-fold). В этом случае формирование метапризнаков осуществляется с помощью всевозможных пар подмножеств, где вторым подмножеством является один из блоков, а первым - все оставшиеся блоки. Очевидно, что использование такого разбиения позволяет породить метапризнаки для всех объектов в обучающей выборке. Недостатком такого подхода является то, что распределение значений метапризнаков для разных блоков будут различаться из-за того, что для обучения соответствующих базовых классификаторов обучающие выборки (первое подмножество в паре) будут отличаться друг от друга. В этом же соревновании был успешно использован другой вариант стекинга, названный блендингом (blending, stacking ensembling) [13]. Он заключается в выполнении всего одной пары разбиений обучающей выборки (hold-out). Преимуществами такого подхода являются меньшая вычислительная сложность решения и отсутствие риска переобучения, недостатком - неэффективное использование обучающей выборки и необходимость подбора параметров разбиения. 4

5 Другими участниками этого же соревнования был предложен Feature-Weighted Linear Stacking [14], идея которого заключается в том, чтобы настраивать веса взвешенной суммы ответов базовых алгоритмов как линейную комбинацию нескольких специально отобранных признаков. Оригинальным использованием стекинга в нейронных сетях является архитектура Deep Stacking Network, предложенная в работе [18]. Предлагается одновременно использовать упорядоченный набор однослойных нейронных сетей в качестве базовых алгоритмов. Каждая сеть в наборе обучается на исходных признаках и на метапризнаках, предсказанных всеми предыдущими сетями, таким образом образуя в совокупности глубокую архитектуру. В данной работе предлагается модификация идеи стекинга, которую можно рассматривать как частный случай предложенного Д. Волпертом общего подхода к формированию обучающей выборки с помощью базовых алгоритмов. Модернизация заключается в том, чтобы получить метапризнак усреднением предсказаний, полученных с помощью различных разбиений на K непересекающихся блоков (K-fold). На реальных данных продемонстрировано, что полученные с усреднением метапризнаки лучше метапризнаков без усреднений в смысле получаемого метаклассификатором качества. 2 Постановка задачи и используемые обозначения Пусть X множество описаний объектов, Y множество ответов, и существует неизвестная целевая зависимость отображение f : X Y значения которой известны только на объектах конечной обучающей выборки (X, Y ) = {(x 1, y 1 ),..., (x (X,Y ), y (X,Y ) )}. Требуется построить алгоритм a : X Y, аппроксимирующий целевую зависимость на всем множестве X. Наряду с множествами X и Y вводится вспомогательное множество R, называемое пространством оценок. Рассматриваются алгоритмы, имеющие вид суперпозиции a(x) = C(b(x)), где функция b : X R называется алгоритмическим оператором, функция C : R Y решающим правилом. Многие алгоритмы классификации имеют именно такую структуру: сначала вычисляются оценки принадлежности объекта классам, затем решающее правило переводит эти оценки в номер класса. Значением оценки b(x) может быть вероятность принадлежности объекта x классу, расстояние от объекта до разделяющей поверхности, степень уверенности классификации и т. п. Определение 1 Композицией T алгоритмов a t (x) = C(b t (x)), t = 1,..., T называется суперпозиция алгоритмических операторов b t : X R, корректирующей операции F : R T R и решающего правила C : R Y : a(x) = C(F (b 1 (x),..., b T (x)), x X Алгоритмы a t, а иногда и операторы b t, называют базовыми алгоритмами. Суперпозиции вида F (b 1,..., b T ) являются отображениями из X в R, то есть, опять-таки, алгоритмическими операторами. Это позволяет строить иерархические композиции, применяя определение 1 рекурсивно. 5

6 Обозначим множество базовых классификаторов как A. Используя сформулированные выше термины, идеей стекинга является использование в качестве алгоритмических операторов b t базовых классификаторов A A, а в качестве корректирующей операции F некоторого метаклассификатора M. 3 Обзор известных методов ансамблирования 3.1 Голосование и смесь экспертов Существует несколько наиболее известных корректирующих операций: простое голосование (Simple Voting): b(x) = F (b 1 (x),..., b T (x)) = 1 T T b t (x); t=1 взвешенное голосование (Weighted Voting): b(x) = F (b 1 (x),..., b T (x)) = T w t b t (x), t=1 T w t = 1, w t 0; t=1 смесь экспертов (Mixture of Experts [19]): b(x) = F (b 1 (x),..., b T (x)) = T w t (x)b t (x), t=1 T w t (x) = 1, x X. t=1 Очевидным является факт, что простое голосование это лишь частный случай взвешенного голосования, а взвешенное голосование является частным случаем смеси экспертов. Также стоит отметить, что из-за наличия большого числа степеней свободы обучение смеси экспертов происходит значительно дольше других алгоритмов построения композиции, поэтому их практическая применимость обоснована только в случае априорной информации о функциях компетенции g t (x), которые чаще всего определяются: признаком f(x): w t (x; ?, ?) = ?(?f(x) + ?), ?, ? R; направлением ? R n : w t (x; ?, ?) = ?(x T ? + ?), ? R n, ? R; 6

7 расстоянием до ? R n w t (x; ?, ?) = exp( ? x ? 2 ), ? R n, ? R; более сложными способами (при помощи оценки плотности распределения данных и т.п.). 1 сигмо- 1 + e z В приведенных выше формулах функций компетенции ?(z) = ида. 3.2 Бустинг Рассмотрим задачу классификации на два класса, Y = { 1, +1}. Допустим, что решающее правило фиксировано, C(b) = sign(b), базовые алгоритмы возвращают ответы -1, 0, +1. Ответ b t (x) = 0 означает, что базовый алгоритм b t отказывается от классификации объекта x, и ответ b t (x) не учитывается в композиции. Искомая алгоритмическая композиция имеет вид: a(x) = C(F (b 1 (x),..., b T (x)) = sign( T ? t b t P n ), x X Пусть теперь при добавлении в композицию слагаемого ? t b t (x) оптимизируется только базовый алгоритм b t и коэффициент при нём ? t, а все предыдущие слагаемые ? 1 b 1 (x),..., ? t 1 b t 1 (x) полагаются фиксированными. Определим функционал качества композиции как число ошибок, допускаемых ею на обучающей выборке: Q t = t=1 l T [y i ? t b t (x i ) < 0] i=1 t=1 Пороговая функция потерь в функционале Q t аппроксимируется (заменяется) непрерывно дифференцируемой оценкой сверху. Аппроксимируя функцию потерь экспонентой, получим AdaBoost [6]. 3.3 Бэггинг Метод бэггинга (bagging, bootstrap aggregation) был предложен Л. Брейманом в 1996 году [4]. Из исходной обучающей выборки длины l формируются различные обучающие подвыборки той же длины l с помощью бутстрепа случайного выбора с возвращениями. При этом некоторые объекты попадают в подвыборку по несколько раз, некоторые ни разу. Можно показать, что доля объектов, оказавшихся в каждой подвыборке, стремится к 1 e при l inf. Базовые алгоритмы, обученные по подвыборкам, объединяются в композицию с помощью простого голосования. Эффективность бэггинга объясняется двумя обстоятельствами. Во-первых, благодаря различности базовых алгоритмов, их ошибки взаимно компенсируются при голосовании. Во-вторых, объекты-выбросы могут не попадать в некоторые обучающие подвыборки. Тогда алгоритм, построенный по подвыборке, может оказаться 7

8 даже точнее алгоритма, построенного по полной выборке. Бэггинг особенно эффективен на малых выборках, когда исключение даже небольшой доли обучающих объектов приводит к построению существенно различных базовых алгоритмов. В случае сверхбольших избыточных выборок приходится строить подвыборки меньшей длины l 0 l, при этом возникает задача подбора оптимального значения l Метод случайных подпространств В методе случайных подпространств (random subspace method, RSM) базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом [10]. Этот метод предпочтителен в задачах с большим числом признаков и относительно небольшим числом объектов, а также при наличии избыточных неинформативных признаков. В этих случаях алгоритмы, построенные по части признакового описания, могут обладать лучшей обобщающей способностью по сравнению с алгоритмами, построенными по всем признакам. Широко известным алгоритмом, использующим одновременно метод случайных подпространств и бэггинг, является случайный лес. Разбиение объектов в вершине случайного леса ищется среди случайного подмножества признаков, а обучение каждого дерева в композиции происходит на выборке, полученной с помощью операции бутстрапа. 3.5 Стекинг Для определенности будем рассматривать задачу классификации (задача регрессии рассматривается аналогично). Постановка задачи классификации звучит следующим образом. Пусть X множество описаний объектов, Y конечное множество номеров (имён, меток) классов. Существует неизвестная целевая зависимость отображение f : X Y значения которой известны только на объектах конечной обучающей выборки (X, Y ) = {(x 1, y 1 ),..., (x (X,Y ), y (X,Y ) )}. Требуется построить алгоритм a : X Y, способный классифицировать произвольный объект x X. Для начала введем дополнительные обозначения: (X 0, Y 0 ) валидационная выборка; A базовый классификатор, использующийся для построения метапризнака; A.fit(X, Y ) функция обучения классификатора A на (X, Y ); A.predict(X) функция, предсказывающая целевую переменную для X классификатором A; M некоторый метаклассификатор; M F (X, A) метапризнак, полученный классификатором A для выборки X; P финальное предсказание стекинга для валидационной выборки; concatv(x i, X j ) операция конкатенирования X i и X j по столбцам; concath(x i, X j ) операция конкатенирования X i и X j по строкам. Идея стэкинга состоит в том, чтобы обучить метаклассификатор M на (1) исходных признаках, матрице X, и (2) на предсказаниях (метапризнаках), полученных с помощью базовых классификаторов (для простоты здесь мы часто будем рассматри- 8

9 вать единственный классификатор A). Метапризнаки, полученные с помощью классификатора A для выборки X будем обозначать M F (X, A). Принятым также является представление стекинга в виде многоуровневой схемы, где признаки обозначаются как уровень 0, метапризнаки, полученные с помощью обучения базовых классификаторов на признаках, как уровень 1, и так далее. В простейшем виде [13] получение предсказания для тестовой выборки P с помощью стекинга выглядит следующим образом (Рисунок 1): Алгоритм 1 разбить обучающую выборку (X, Y ) на две части: (X 1, Y 1 ) и (X 2, Y 2 ). A.fit(X 1,Y 1 ) MF (X 2, A) := A.predict(X 2 ) MF (X 0, A) := A.predict(X 0 ) M.fit(concatV(X 2, MF (X 2, A)), Y 2 ) P := M.predict(concatV(X 0, MF (X 0, A))) Рис. 1: Алгоритм 1, стекинг по схеме hold-out Недостатком этого варианта стекинга является то, что M обучается только на части X 2 обучающей выборки, а другая часть X 1 им не используется. Чтобы избежать этого, мы можем повторить алгоритм, поменяв местами (X 1, Y 1 ) и (X 2, Y 2 ). В таком случае мы получим два предсказания для валидационной выборки, которые мы можем усреднить. Более эффективным в смысле достижимого качества решением этой проблемы является следующая идея: мы можем повторить Алгоритм 1, 9

10 каждый раз используя различные разбиения и затем усреднить полученные предсказания: Алгоритм 2 сделать разбиения {{(X n1, Y n1 ), (X n2, Y n2 )}, n = 1... N} для n=1... N A n := A A n.fit(x n1, Y n1 ) MF (X n2, A n ) := A n.predict(x n2 ) MF (X 0, A n ) := A n.predict(x 0 ) M n := M M n.fit(concatv(x n2, MF (X n2, A n )), Y 2 ) P n := M n.predict(concatv(x 0, MF (X 0, A n ))) N P := 1 P N n n=1 Можно сделать Алгоритм 2 более эффективным, если осуществлять разбиения по принципу бутстрапа. Логика для использования такого подхода следующая: мы знаем, что эффективно использовать бэггинг для классификаторов. Однако, мы также можем использовать объекты, которые при этом не попадают в обучающую выборку для каждого классификатора. Таким образом, при построении очередного классификатора в бэггинге из обучающей выборки формируется выборка X 2 той же длины с возвращениями. Все объекты, которые не попали в эту обучающую выборку, помещаются в множество X 1 [11]. Отметим, что Алгоритм 1 и Алгоритм 2 с легкостью модернизировать для любого множества базовых классификаторов A. Однако, в любом случае описанные выше алгоритмы не решают проблемы уменьшения размера обучающей выборки с каждым следующим уровнем стекинга, а также возникающей дополнительной вычислительной сложности при повторном обучении метаклассификатора N раз при добавлении нового базового алгоритма в множество A. Очевидным способом решения возникшей проблемы является получение метапризнака MF (X, A) для всей обучающей выборки [3]: Видно, что описанный алгоритм (как и те, которые будут описаны ниже) на самом деле состоит из двух частей: получения метапризнака M F (X, A) и использования метаклассификатора M для осуществления предсказания P для валидационной выборки. Поскольку для получения мета-признака мы обучали классификатор A только на признаках, будем называть пару MF (X, A), MF (X 0, A) метапризнаком первого уровня. Преимуществом этого способа является также и то, что мы можем включить полученный метапризнак в обучающую выборку в качестве обычного признака. По- 10

11 Алгоритм 3 разбить обучающую выборку (X, Y ) на две части: (X 1, Y 1 ) и (X 2, Y 2 ). A 1 := A A 1.fit(X 1, Y 1 ) MF (X 2, A 1 ) := A 1.predict(X 2 ) MF (X 0, A 1 ) := A 1.predict(X 0 ) A 2 := A A 2.fit(X 2, Y 2 ) MF (X 1, A 2 ) := A 2.predict(X 1 ) MF (X 0, A 2 ) := A 2.predict(X 0 ) MF (X, A) := concath(mf (X 1, A 2 ), MF (X 2, A 1 )) MF (X 0, A) := (MF (X 0, A 1 ) + MF (X 0, A 2 )) / 2 M.fit(concatV(X, MF (X, A)), Y ) P := M.predict(concatV(X 0, MF (X 0, A))) вторив Алгоритм 3 над такой выборкой, мы получим мета-признак второго уровня, и так далее. Другой логичной модернизацией идеи стекинга может стать число разбиений обучающей выборки на первом шаге. Модифицируем последний алгоритм (Рисунок 2): Алгоритм 4 сделать разбиения {(X k, Y k ), k = 1... K} для k=1... K A k := A A k.fit(x X k, Y Y k ) MF (X k, A k ) := A k.predict(x k ) MF (X 0, A n ) := A k.predict(x 0 ) MF (X, A) := concath(mf (X k, A k ), k = 1... K) K MF (X 0, A) := 1 MF (X K 0, A k ) k=1 M.fit(concatV(X, MF (X, A)), Y ) P := M.predict(concatV(X 0, MF (X 0, A))) Назовём такой способ получения метапризнаков out-of-fold(k) или, для краткости, oof(k). При K = X получаем способ, изначально рассмотренный Д. Волпертом в его статье [2] (leave-one-out). 11

12 Рис. 2: Алгоритм 4, создание метапризнака по схеме K-fold При K X осуществлять разбиения представляется логичным таким образом, чтобы в каждой части оказалось равное количество объектов, а также, чтобы для каждого фиксированного класса доля объектов в каждой из K частей была одинакова. Такой способ принято называть разбиением на K блоков со стратификацией классов (Stratified K-fold). В дальнейшем будем предполагать именно его. Таким образом, oof(k) позволяет метаклассификатору M использовать для обучения всю выборку X. Однако, у него имеется следующий недостаток: полученные распределения значений метапризнаков для обучающей M F (X, A) и валидационной выборки MF (X 0, A) часто оказываются различны в силу того, что метапризнак для валидационной выборки был получен усреднением K предсказаний. Очевидно, что это приводит к ухудшению качества финального предсказания P. В качестве простой иллюстрации такой возможности рассмотрим следующий пример. Пример 1 Рассматривается задача двухклассовой классификации. A классификатор, предсказывающий класс объекта как класс его ближайшего соседа из обучающей выборки. В этом случае MF (X, A) может иметь только значения {0, 1}, в отличии от MF (X 0, A), которая, в результате усреднения K предсказаний, может иметь значения { k K, k = 0... K}. Чтобы избежать этого, мы могли бы предсказывать MF (X, A) с помощью одного классификатора, обученного на всей обучающей выборке. Модернизированный алгоритм: Предложенный последним алгоритм будем обозначать oof(k, test_averaging=false), а предыдущий, соответственно, oof(k, test_averaging=true). Однако, и oof(k, test_averaging=false) обладает своим недостатком: MF (X 0, A) 12

13 Алгоритм 5 сделать разбиения {(X k, Y k ), k = 1... K} для k=1... K A k := A A k.fit(x X k, Y Y k ) MF (X k, A k ) := A k.predict(x k ) MF (X, A) = concath(mf (X k, A k ), k = 1... K) A 0 := A A 0.fit(X, Y ) MF (X 0, A) := A 0.predict(X 0 ) M.fit(concatV(X, MF (X, A)), Y ) P := M.predict(concatV(X 0, MF (X 0, A))) может существенно отличаться от MF (X, A), поскольку для объектов из разных блоков обучение базовых классификаторов происходило на различных подмножествах обучающей выборки. В работе предлагается уменьшить отрицательный эффект этого с помощью внесения следующей модернизации в идею стекинга out-of-fold(k): классификатором A получить один и тот же метапризнак для различных разбиений обучающей выборки, затем усреднить. Выдвигается гипотеза, что достаточное количество усреднений позволяет уменьшить отрицательный эффект описанной выше вариативности значений метапризнаков. Модифицированный алгоритм: Если результаты классификатора A при фиксированной обучающей выборке фиксированны, то есть не зависят от некоторых стохастических параметров, разумным упрощением то N modified = 1, иначе N modified = N. Будем обозначать такой способ получения метапризнаков out-of-fold(k)*n или, для краткости, oof(k)*n. Очевидно, что oof(k) является частным случаем oof(k)*n. Также отметим, что при получении MF (X, A) фиксированное для всех классификаторов разбиение обучающей выборки на {(X k, Y k ), k = 1... K} является более предпочтительным, чем различные разбиения для разных классификаторов, поскольку в таком случае для фиксированного объекта из обучающей выборки значения метапризнаков от различных классификаторов будут более похожи друг на друга в силу того, что классификаторы A A будут обучены на одной и той же части обучающей выборки. Таким же образом, при получении метапризнаков oof(k)*n с помощью различных классификаторов логичным представляется фиксированный набор разбиений {{(X nk, Y nk ), k = 1... K}, n = 1... N}, что и будет использовано в данной работе. 13

14 Алгоритм 6 зафиксировать разбиения {{(X nk, Y nk ), k = 1... K}, n = 1... N} для n=1... N для k=1... K A nk := A A nk.fit(x X nk, Y Y nk ) MF (X nk, A nk ) := A nk.predict(x nk ) MF (X 0, A nk ) := A nk.predict(x 0 ) MF (X n, A n ) = concath({mf (X nk, A nk ), k = 1... K}) K MF (X, A n ) := 1 MF (X K 0, A nk ) k=1 если test_averaging==true то N MF (X 0, A) := 1 MF (X N 0, A n ) n=1 иначе для n=1... N modified A 0n := A A 0n.fit(X, Y ) MF (X 0, A 0n ) = A 0n.predict(X 0 ) N modified 1 MF (X 0, A) := N modified MF (X 0, A 0n ) n=1 M.fit(concatV(X, MF (X, A)), Y ) P := M.predict(concatV(X 0, MF (X 0, A))) 14

15 4 Экспериментальная часть 4.1 Необходимые пояснения Для удобства описания результатов экспериментов введём следующие обозначения: Будем называть качеством (quality) метапризнака качество метаклассификатора, обученного на признаках и этом метапризнаке, на валидационной выборке. Будем называть непосредственным качеством (direct quality) метапризнака M F (X, A) качество, которое мы получаем, предсказывая целевую переменную непосредственно этим метапризнаком. Вид рассматриваемого функционала качества совпадает с функционалом, который оптимизирует классификатор A. Поскольку качество метапризнака может быть не связано с его непосредственным качеством, предлагается сравнивать метапризнаки по результатам метаклассификаторов, построенных на них. Ясно, что для oof(k)*n качество метапризнака зависит от числа усреднений и, если классификатор A может давать различные результаты для одной и той же обучающей выборки в силу зависимости от некоторых случайных параметров, для oof(k) тоже. В таком случае, чтобы сравнить различные способы получения метапризнака, необходимо зафиксировать одинаковую вычислительную сложность для различных K в oof(k)*n и oof(k). Разумным представляется следующее предположение. Для того, чтобы построить метапризнак oof(k)*1, необходимо обучить K классификаторов на доле выборки, равной (K-1)/K. Пусть время обучения классификатора прямо пропорционально объему выборки, тогда время обучения oof(k)*1 будет пропорционально K*(K-1)/K = K-1, а время обучения oof(k)*n будет пропорционально (K-1)*N. В таком случае для сравнения качества метапризнаков с различным K предлагается зафиксировать (K-1)*N. Во всех проведенных в данной работе экспериментах (K-1)*N = 100. Обозначим цели вычислительного эксперимента: сравнить качество метапризнаков, полученных с помощью oof(k) и oof(k)*n; показать, что улучшение непосредственного качества метапризнака при измении способа его построения не обязательно ведёт к улучшению качества метапризнака; показать, что уменьшение разности непосредственного качества метапризнака на обучающей и валидационной выборке при измении способа его построения не обязательно ведёт к улучшению качества метапризнака. Для удобства в указании способа получения метапризнака иногда будем опускать test_averaging. Например, вместо oof(k), test_averaging=true будем записывать oof(k), True. Также для удобства будем обозначать схему стекинга следующим образом: M(X, A), например, если метаклассификатор M - градиентный бустинг (XGBoost) [21], а базовый классификатор A - ExtraTreesClassifier (ET) [20], то обозначение схемы стекинга будет выглядеть так: XGBoost(X,ET). 15

16 ExtraTreesClassifier является классификатором, построенным по аналогии с случайным лесом. Разница между случайным лесом и ET состоит в стратегии выбора разделения подвыборки в вершине дерева для фиксированного подмножества признаков. Случайный лес проверяет всевозможные варианты разбиений для каждого признака, тогда как ET выбирает лишь среди случайно выбранных по одному на признак разбиений. Используемый XGBoost оптимизирует многоклассовый logloss (multiclass logloss), ExtraTreesClassifier оптимизирует аккуратность (accuracy), логистическая регрессия (Logistic Regression [20]) решает задачу многоклассовой классификации методом один-против-всех (One-vs-rest, OVR), поэтому оптимизируется средний logloss (mean logloss). 4.2 Поставленные эксперименты Для эксперимента выбраны два датасета с задачами мультиклассовой классификации: UCI, Forest Cover Type Prediction; Kaggle, Otto Group Product Classification Challenge. Все результаты приводятся для усреднения по 10 случайным разбиениям на обучающую и тестовую выборки размером по 15 тысяч объектов. Если не указано иначе, границами ошибки на графиках изображено среднеквадратичное отклонение. Эксперименты 1-3: UCI Forest Cover Type Prediction. Используется один и тот же набор метапризнаков, отличаются только метаклассификаторы: ET, LogisticRegression, XGBoost соответственно. Метапризнаки получены с помощью базового классификатора XGBoost с параметрами max_depth=15, eta=0.1, early_stopping=true. При получении метапризнака для валидационной выборки с помощью XGBoost и test_averaging=false здесь и далее будем использовать среднее число итераций XGBoost для K моделей, полученных во время генерации метапризнака для обучающей выборки. Результат обучения базового классификатора зависел только от обучающей выборки, поэтому вычислительная сложность oof(k) была пропорциональна K-1. Эксперимент 1: Схема ET(X, XGBoost(X)). Параметры метаклассификатора: n_estimators= K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 1: Эксперимент 1. ET(X,XGBoost). В таблице приведены значения качества для метапризнаков, построенных различными способами. ET без метапризнаков даёт accuracy

17 Рис. 3: Эксперимент 1. Качество метапризнаков, полученных различными способами Рис. 4: Эксперимент 1. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. Эксперимент 2: Схема LogisticRegression(X, XGBoost(X)). Параметры метаклассификатора: C=1. Эксперимент 3: Схема XGBoost(X, XGBoost). Параметры метаклассификатора: max_depth=15, eta=0.1, early_stopping=true, colsample_bytree=0.75, subsample=0.75. Происходит усреднение предсказаний метаклассификаторов с параметром seed=

18 Рис. 5: Эксперимент 1. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. Рис. 6: Эксперимент 2. Качество метапризнаков, полученных различными способами 18

19 K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 2: Эксперимент 2. LogisticRegression(X,XGBoost). В таблице приведены значения качества для метапризнаков, построенных различными способами. LogisticRegression без метапризнаков даёт средний logloss Рис. 7: Эксперимент 2. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 3: Эксперимент 3. XGBoost(X,XGBoost). В таблице приведены значения качества для метапризнаков, построенных различными способами. XGBoost без метапризнаков даёт мультиклассовый logloss

20 Рис. 8: Эксперимент 2. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. Рис. 9: Эксперимент 3. Качество метапризнаков, полученных различными способами 20

21 Рис. 10: Эксперимент 3. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. Рис. 11: Эксперимент 3. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 21

22 Эксперименты 4-5: UCI Forest Cover Type Prediction. Используется один и тот же набор метапризнаков, отличаются только метаклассификаторы: ET, XGBoost соответственно. Метапризнаки получены с помощью базового классификатора LogisticRegression с параметрами C=1. Результат обучения базового классификатора зависел только от обучающей выборки, поэтому вычислительная сложность oof(k) была пропорциональна K-1. Эксперимент 4: Схема ET(X, LogisticRegression(X)). Параметры метаклассификатора: n_estimators= K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 4: Эксперимент 4. ET(X,LogisticRegression). В таблице приведены значения качества для метапризнаков, построенных различными способами. ET без метапризнаков даёт accuracy Эксперимент 5: Схема XGBoost(X, LogisticRegression). Параметры метаклассификатора: max_depth=15, eta=0.1, early_stopping=true. K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 5: Эксперимент 5. XGBoost(X,LogisticRegression). В таблице приведены значения качества для метапризнаков, построенных различными способами. XGBoost без метапризнаков даёт мультиклассовый logloss

23 Рис. 12: Эксперимент 4. Качество метапризнаков, полученных различными способами Рис. 13: Эксперимент 4. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 23

24 Рис. 14: Эксперимент 4. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 24

25 Рис. 15: Эксперимент 5. Качество метапризнаков, полученных различными способами Рис. 16: Эксперимент 5. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 25

26 Рис. 17: Эксперимент 5. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 26

27 Эксперименты 6-7: Kaggle, Otto Group Product Classification Challenge. Используется один и тот же набор метапризнаков, отличаются только метаклассификаторы: ET, XGBoost соответственно. Метапризнаки получены с помощью базового классификатора LogisticRegression с параметрами C=1. Результат обучения базового классификатора зависел только от обучающей выборки, поэтому вычислительная сложность oof(k) была пропорциональна K-1. В качестве границ ошибки изображено среднеквадратичное отклонение, делённое на 5. Эксперимент 6: Схема ET(X, LogisticRegression(X)). Параметры метаклассификатора: n_estimators= K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 6: Эксперимент 6. ET(X,LogisticRegression). В таблице приведены значения качества для метапризнаков, построенных различными способами. ET без метапризнаков даёт accuracy Эксперимент 7: Схема XGBoost(X, LogisticRegression). Параметры метаклассификатора: max_depth=15, eta=0.1, early_stopping=true, colsample_bytree=0.25, subsample=0.65. Происходит усреднение предсказаний метаклассификатора с параметром seed= K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 7: Эксперимент 7. XGBoost(X,LogisticRegression). В таблице приведены значения качества для метапризнаков, построенных различными способами. XGBoost без метапризнаков даёт мультиклассовый logloss

28 Рис. 18: Эксперимент 6. Качество метапризнаков, полученных различными способами Рис. 19: Эксперимент 6. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 28

29 Рис. 20: Эксперимент 6. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 29

30 Рис. 21: Эксперимент 7. Качество метапризнаков, полученных различными способами Рис. 22: Эксперимент 7. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 30

31 Рис. 23: Эксперимент 7. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 31

32 Эксперименты 8-10: Kaggle, Otto Group Product Classification Challenge. Используется один и тот же набор метапризнаков, отличаются только метаклассификаторы: ET, XGBoost, LogisticRegression соответственно. Метапризнаки получены с помощью базового классификатора XGBoost с параметрами max_depth=15, eta=0.1, early_stopping=true, colsample_bytree=0.75, subsample=0.75. При получении метапризнака с помощью XGBoost и test_averaging=false мы используем среднее число итераций K моделей, полученных во время генерации метапризнака для обучающей выборки, для установки количества итераций в модели, которой мы предсказываем метапризнак для тестовой выборки. Результат обучения базового классификатора зависел не только от обучающей выборки, но и от случайного параметра, поэтому вычислительная сложность oof(k) была пропорциональна (K-1)*N. В качестве границ ошибки изображено среднеквадратичное отклонение, делённое на 2. Эксперимент 8: Схема ET(X, XGBoost(X)). Параметры метаклассификатора: n_estimators= K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 8: Эксперимент 8. ET(X,XGBoost). В таблице приведены значения качества для метапризнаков, построенных различными способами. ET без метапризнаков даёт аккуратность Эксперимент 9: Схема XGBoost(X, XGBoost). Параметры метаклассификатора: max_depth=15, eta=0.1, early_stopping=true, colsample_bytree=0.25, subsample=0.65. Происходит усреднение предсказаний метаклассификатора с параметром seed= K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 9: Эксперимент 9. XGBoost(X,XGBoost). В таблице приведены значения качества для метапризнаков, построенных различными способами. XGBoost без метапризнаков даёт мультиклассовый logloss Эксперимент 10: Схема LogisticRegression(X, XGBoost(X)). Параметры метаклассификатора: C=1. 32

33 Рис. 24: Эксперимент 8. Качество метапризнаков, полученных различными способами Рис. 25: Эксперимент 8. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 33

34 Рис. 26: Эксперимент 8. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. K N oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False Таблица 10: Эксперимент 10. LogisticRegression(X,XGBoost). В таблице приведены значения качества для метапризнаков, построенных различными способами. LogisticRegression без метапризнаков даёт средний logloss

35 Рис. 27: Эксперимент 9. Качество метапризнаков, полученных различными способами Рис. 28: Эксперимент 9. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 35

36 Рис. 29: Эксперимент 9. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 36

37 Рис. 30: Эксперимент 10. Качество метапризнаков, полученных различными способами Рис. 31: Эксперимент 10. Зависимость качества метаклассификатора от непосредственного качества метапризнака для обучающей и тестовой выборки. 37

38 Рис. 32: Эксперимент 10. Зависимость качества метаклассификатора от разности между непосредственным качеством метапризнака для обучающей и тестовой выборки. 38

39 4.3 Обобщение результатов экспериментов Сделаем обобщение результатов проведенных экспериментов. Для каждого способа получения метапризнака посчитаем лучшее качество (или минимальную ошибку) по всем K. Сравним их для разных способов и составим таблицу, в строках и столбцах которой указаны способы получения метапризнаков, а в ячейках стоит число экспериментов, в которых способ по горизонтали дал метапризнак лучшего качества, чем способ по вертикали. Так как всего было поставлено десять экспериментов, идеальный способ получения метапризнака мог бы получить в сумме 30 вдоль соответствующей строки. oof(k), True oof(k), False oof(k)*n, True oof(k)*n, False всего oof(k), True /30 oof(k), False /30 oof(k)*n, True /30 oof(k)*n, False /30 Таблица 11: Результаты экспериментов Рис. 33: Таблица 11. Результаты экспериментов. 5 Заключение В работе предложен метод ансамблирования обучающихся алгоритмов, являющийся модификацией алгоритма стекинга. Поставлены эксперименты на реальных данных, показавшие, что предложенный алгоритм в большинстве случаев превосходит предложенные ранее аналогичные алгоритмы. Предложенный алгоритм обладает следующими преимуществами: происходит эффективное использование обучающей выборки осуществляется борьба с "неоднородностью"метапризнаков 39

40 Список литературы [1] Воронцов К.В. Лекции по алгоритмическим композициям // machinelearning.ru/wiki/images/0/0d/voron-ml-compositions.pdf [2] Wolpert, David H. Stacked generalization // Neural networks 5.2 (1992): [3] Breiman, Leo. Stacked regressions // Machine learning 24.1 (1996): [4] Breiman, Leo. Bagging predictors // Machine learning 24.2 (1996): [5] Breiman, Leo. Random Forests // Machine Learning, 45(1), 5-32, 2001 [6] Freund, Yoav, Robert Schapire, and N. Abe. A Short Introduction to Boosting // Journal-Japanese Society For Artificial Intelligence (1999): 1612 [7] Friedman, Jerome H. Stochastic gradient boosting // Computational Statistics and Data Analysis, 2002 [8] Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики [9] Рыжков А. М. Композиции алгоритмов, основанные на случайном лесе // Дипломная работа, ВМК МГУ, [10] Skurichina M., Duin R. P. W. Limited bagging, boosting and the random subspace method for linear classifiers // Pattern Analysis & Applications Pp [11] Kim, Mike. // 2015, otto-group-product-classification-challenge/forums/t/14295/ via-tsne-meta-bagging [12] Netflix Prize // [13] Jahrer, Michael. Netflix Prize report 2009 // net/combiningpredictionsforaccuraterecommendersystems.pdf [14] Sill, Joseph, et al. Feature-weighted linear stacking // arxiv preprint arxiv: (2009). [15] Toscher, Andreas and Jahrer, Michael. The BigChaos Solution to the Netflix Grand Prize // 2009, BPC_BigChaos.pdf [16] Menahem, Eitan, Lior Rokach, and Yuval Elovici. Troika An improved stacking schema for classification tasks // Information Sciences (2009): [17] Seewald, A. How to Make Stacking Better and Faster While Also Taking Care of an Unknown Weakness // Nineteenth International Conference on Machine Learning (pp ) (2002) 40

41 [18] Deng, Li, Dong Yu, and John Platt. Scalable stacking and learning for building deep architectures // Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. IEEE, [19] Jordan, Michael I., and Robert A. Jacobs. Hierarchical mixtures of experts and the EM algorithm // Neural computation 6.2 (1994): [20] Scikit-learn, [21] XGBoost, 41

Источник: docplayer.ru

Комментарии: