ABOUT BOOSTED LEARNING OF NONPARAMETRIC ESTIMATORS

Full Text

Введение. Широкое распространение методов моделирования, идентификации объясняется возможностью их применения для построения моделей явлений, объектов и процессов разной физической природы. Универсальность и эффективность методов идентификации позволяют применять их как для различных технических систем (в том числе и в ракетно-космической отрасли), так и в медицине, экономике и других областях науки и практики. На сегодняшний день существует широкий спектр методов идентификации: от традиционных методов статистического анализа до современных алгоритмов машинного обучения [1]. В последние годы большую популярность получило построение коллективов моделей (ансамблей) [2-4]. Одной из основных задач объединения нескольких моделей одного типа является устранение тех или иных недостатков определенных моделей. Например, если деревья классификации и регрессии (CaRT) [5] склонны к переобучению, то их коллективы (Random Forest [6], GBM [7; 8]) менее подвержены этому негативному эффекту. В данной работе предложен подход к формированию ансамбля непараметрических оценок Надарая-Ватсона [9], позволяющий получать более гладкие и точные оценки в разреженных подобластях пространства входных переменных, чем при построении единственной непараметрической оценки. Постановка задачи. Формально задачу идентификации можно записать следующим образом [10]. Имеется множество наблюдений: Каждое наблюдение характеризуется набором переменных: где x1, x2, …, xm - независимые переменные, значения которых известны и на основании которых определяется значение зависимой переменной y. Требуется восстановить зависимость между независимыми входными переменными x1, x2, …, xm и выходной переменной y. Какая-либо другая априорная информация об исследуемом объекте отсутствует. При подобных постановках задачи одним из распространенных методов [11-13] восстановления зависимости между входом и выходом является непараметрическая оценка регрессии Надарая-Ватсона: (1) где K - ядерная функция; ͞с - вектор параметров размытости. Однако в ряде случаев данный подход имеет некоторые недостатки. При наличии разреженных областей в пространстве входных переменных (рис. 1) минимальный параметр размытости (рис. 1, а), необходимый для того, чтобы оценка (1) существовала во всех точках исследуемой области пространства входной переменной, настолько велик, что в некоторых точках ядро захватывает большую часть наблюдений (рис. 1, б), что может привести к определенным искажениям оценки. Другой важный момент связан с уменьшением точности оценки (1) на границах пространства входных переменных [14]. Данные недостатки могут быть устранены с помощью объединения непараметрических оценок Надарая-Ватсона в ансамбль последовательного обучения [15]. Ансамбль непараметрических оценок. Идея построения ансамбля непараметрических оценок состоит в итеративном улучшении некоторой начальной (базовой) оценки регрессии Надарая-Ватсона за счет последовательного добавления непараметрических оценок невязок текущего ансамбля. Процедура формирования ансамбля показана на рис. 2. Процедура начинается с построения некоторой базовой оценки (1) с большими параметрами размытости. Затем вычисляются невязки между выходом объекта и выходом базовой оценки, по которым строится следующая непараметрическая оценка (1) с меньшими параметрами размытости. Данная оценка добавляется к базовой оценке, так формируется ансамбль первого уровня. Затем вычисляются невязки между выходом объекта и выходом ансамбля первого уровня, и так далее, пока добавление каждой новой оценки в ансамбль приводит к его улучшению. а б Рис. 1. Ядро минимальной ширины: а - позволяющее получать некоторое значение оценки (1) в любой точке исследуемой области пространства входной переменной; б - захватывающее более половины наблюдений а б в г д е Рис. 2. Процедура формирования ансамбля непараметрических оценок последовательного обучения: а - построение базовой оценки с большим параметром размытости; б - вычисление невязок между выходами объекта и модели; в - формирование выборки, состоящей из невязок; г - построение модели невязки с меньшим параметром размытости, вычисление невязки ансамбля первого уровня; д - формирование выборки, состоящей из невязок ансамбля первого уровня; е - построение модели невязок ансамбля первого уровня с меньшим параметром размытости На первых итерациях (при больших параметрах размытости) алгоритм восстанавливает зависимость в разреженных областях, при этом оценки в областях с достаточным количеством наблюдений, очевидно, уступают в точности непараметрической оценке, построенной с меньшими параметрами размытости. Начиная с некоторого шага, ядро непараметрической оценки в точках разреженных областей перестает захватывать какие-либо из имеющихся наблюдений, процесс формирования ансамбля для таких областей автоматически прекращается. Одновременно с этим начинается уточнение оценки в областях с достаточным количеством наблюдений. Таким образом, предлагаемый алгоритм позволяет строить максимально точные (из возможных в классе непараметрических оценок Надарая-Ватсона) оценки как в разреженных областях пространства входных переменных, так и в областях, в которых количество наблюдений велико. Формирование ансамбля непараметрических оценок регрессии. Формирование ансамбля непараметрических оценок Надарая-Ватсона происходит последовательно. Каждая последующая оценка добавляется в ансамбль с целью улучшить его качество. Данный процесс продолжается до того момента, пока уменьшается значение меры рассогласования L выхода модели (ансамбля) и объекта, вычисленное по валидационной выборке (͠͠x, ͠y): В качестве меры рассогласования L в работе использовалась квадратичная ошибка: Ансамблем нулевого уровня H0(͞x) является непараметрическая оценка где ͞с0 - вектор параметров размытости. Каждая последующая непараметрическая оценка дополняет текущий ансамбль Hq-1(͞x), минимизируя невязку между выходом объекта y и выходом текущего ансамбля Hq-1(͞x): В результате задача построения ансамбля непараметрических оценок сводится к следующей задаче оптимизации: где Q - количество непараметрических оценок, включенных в ансамбль; C - последовательность векторов параметров размытости: Однако оптимизация параметров размытости при добавлении каждой модели при большом объеме обучающей выборки требует большого количества вычислительных ресурсов. Вычислительная сложность зависит от выбранного метода оптимизации и от решаемой задачи и может быть оценена как O(kñn) на каждом шаге, где k - количество вычислений критерия, ñ - объем валидационной выборки. Значение k при этом может быть достаточно большим (особенно в случае высокой размерности пространства входных переменных). Для того чтобы избежать данной проблемы, в данной работе предлагается алгоритм последовательного пересчета параметров размытости, гарантирующий вычислительную сложность O(mñn) на каждом шаге, где m - размерность пространства входных переменных. Параметры размытости пересчитываются по следующим формулам: где значения вектора ͞aq указывают на то, какой именно параметр размытости должен быть уменьшен на шаге q. Для того чтобы определить значения ͞aq, последовательно уменьшаем по одному из параметров размытости, строим оценку невязки текущего ансамбля, добавляем эту оценку к текущему ансамблю и вычисляем значение критерия качества. На основании значений критериев качества присваиваем следующие значения компонентам вектора ͞aq: ajq = 1, если уменьшение j-го параметра размытости привело к наибольшему увеличению точности ансамбля, иначе ajq = 0. В случае получения одинаковых значений критерия качества при уменьшении нескольких параметров, произвольным образом выбирается один из этих параметров размытости, соответствующая ему компонента вектора ͞aq равна 1, остальные компоненты равны 0. Вектор начальных параметров размытости ͞с0 должен быть таким, чтобы оценка (1) существовала для любого вектора входных переменных ͞x, каждая компонента которого лежит в интервале от минимального до максимального значений соответствующей компоненты, определенных по имеющейся обучающей выборке. Для того чтобы избежать дополнительных расчетов оценки (1) вектор начальных параметров размытости ͞с0 может быть выбран следующим образом: Параметр b непосредственно влияет на количество непараметрических оценок, которые будут включены в ансамбль: чем меньше b, тем быстрее ширина ядер в оценке (1) уменьшится до таких значений, что ядра перестанут захватывать наблюдения и процесс построения ансамбля прекратится. Выбор наилучшего параметра b можно сравнить с попыткой предсказать параметры размытости последней модели в ансамбле, а затем подобрать b, исходя из требований к количеству моделей в ансамбле. Параметры размытости последней модели связаны с особенностями решаемой задачи: распределения входных переменных, наличие сгустков наблюдений в обучающей выборке, плотность этих сгустков и т. д. Причем эта оценка всегда будет оценкой снизу, так как выполняется до построения ансамбля. Если b будет вычислен исходя из требования к количеству моделей в ансамбле, значение b может оказаться завышенным. Завышенное значение b приведет к остановке роста ансамбля при меньшем количестве моделей. Так как b непосредственно характеризует скорость изменения параметров, то завышенное b приводит к более быстрому уменьшению параметров размытости, что сказывается на точности. По этой причине построение нескольких ансамблей с различными значениями b и последующим выбором наилучшего представляется более выигрышной стратегией. Параметр b должен выбираться из диапазона от 0,5 до 1. На основании множества разнообразных численных экспериментов и решения прикладных задач идентификации рекомендуемое значение параметра b = 0,8. Данное значение параметра в большинстве задач позволяет получать достаточно высокую точность при небольшом количестве моделей в ансамбле. Оценка в разреженных областях пространства входных переменных. Покажем работоспособность данного подхода в условиях наличия разреженных областей в пространствах входных переменных. Рассмотрим следующий численный эксперимент. Пусть имеется единственная входная переменная x, принимающая значения от 0 до 3, структуру объекта зададим уравнением y = x2 + 10. После формирования обучающей выборки извлечем из нее все наблюдения со значением входной переменной от 1 до 2. К получившемуся набору данных применим предлагаемый подход к построению ансамблей непараметрических оценок регрессии. На рис. 3 показаны ансамбли, состоящие из одной, двух и пяти моделей. Сравнение единственной непараметрической оценки регрессии и предложенного в работе ансамбля приведено на рис. 4. Рис. 3. Построение ансамбля непараметрических оценок (1) для разряженных областей: 1 - обучающая выборка; 2 - базовая оценка; 3 - ансамбль, состоящий из суммы двух непараметрических оценок; 4 - ансамбль, состоящий из суммы пяти непараметрических оценок Рис. 4. Сравнение единственной непараметрической оценки регрессии и ансамбля для разряженных областей: 1 - обучающая выборка; 2 - непараметрическая оценка регрессии с настроенным параметром размытости; 3 - ансамбль, состоящий из суммы пяти непараметрических оценок В ходе численных исследований было показано, что точность ансамбля непараметрических оценок Надарая-Ватсона превосходит единственную оценку как в разреженных областях пространства входных переменных, так и в областях с большим количеством наблюдений. Следует также отметить, что для многомерных задач разница в точности между ансамблем и единственной оценкой становится более значительной. Оценка на границах пространства входных переменных и экстраполяция. Добавление каждой последующей непараметрической оценки в ансамбль направлено на то, чтобы уменьшить ошибку текущего ансамбля. Поэтому большое влияние на итоговую оценку оказывают наблюдения, близкие к границе области входных переменных, так как в силу особенности своего построения точность непараметрической оценки у границы меньше [14], а следовательно, больше значения невязок между выходом объекта и выходом текущего ансамбля и больше вклад в итоговую оценку. Рассмотрим следующий численный эксперимент. Пусть имеется единственная входная переменная x, принимающая значения от 0 до 3, структуру объекта зададим уравнением y = x2 + 10. Оценку будем строить на интервале от 0 до 4. К получившемуся набору данных применим предлагаемый подход к построению ансамблей непараметрических оценок регрессии. Последовательность ансамблей H0(x), H1(x), …, H4(x) показана на рис. 5. Нетрудно видеть, что вблизи граничных значений (0 и 3) различия между этими ансамблями больше. Сравнение единственной непараметрической оценки регрессии и предложенного в работе ансамбля приведено на рис. 6. Следует отметить, что ансамбль непараметрических оценок может быть использован и для экстраполяции. Рис. 5. Построение ансамбля непараметрических оценок (1) для границы области входных переменных: 1 - обучающая выборка; 2 - базовая оценка; 3 - ансамбль, состоящий из суммы двух непараметрических оценок; 4 - ансамбль, состоящий из суммы трех непараметрических оценок; 5 - ансамбль, состоящий из суммы четырех непараметрических оценок; 6 - ансамбль, состоящий из суммы пяти непараметрических оценок Рис. 6. Сравнение единственной непараметрической оценки регрессии и ансамбля для границы области входных переменных: 1 - обучающая выборка; 2 - непараметрическая оценка регрессии с настроенным параметром размытости; 3 - ансамбль, состоящий из суммы пяти непараметрических оценок В ходе численных исследований была показана высокая эффективность предложенного ансамбля при оценке вблизи границ области входных переменных, а также за ними. Для многомерных задач разница в точности между ансамблем и единственной оценкой становится более значительной. Заключение. Предложен подход к обучению ансамбля непараметрических оценок Надарая-Ватсона, позволяющий повысить точность восстановления зависимости между входными переменными и выходной переменной по наблюдениям. Разнообразные численные эксперименты свидетельствуют о высокой эффективности предложенного подхода к формированию ансамблей непараметрических оценок при наличии разреженных областей в пространстве входных переменных, а также на границах этого пространства.

About the authors

E. S. Mangalova

Reshetnev Siberian State Aerospace University

Email: e.s.mangalova@hotmail.com
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

O. V. Shesterneva

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files