ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 3, с. 530-544
УДК 519.7
РЕГРЕССИОННАЯ МОДЕЛЬ, ОСНОВАННАЯ НА ВЫПУКЛЫХ КОМБИНАЦИЯХ, МАКСИМАЛЬНО КОРРЕЛИРУЮЩИХ
С ОТКЛИКОМ^
© 2015 г. А. А. Докукин, О. В. Сенько
(119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: dalex@ccas.ru; senkoov@mail.ru Поступила в редакцию 10.09.2013 г.
Переработанный вариант 29.09.2014 г.
Представлен новый регрессионный метод, основанный на построении оптимальных выпуклых комбинаций простых линейных регрессий метода наименьших квадратов (МНК-регрес-сий), построенных по исходным регрессорам. Было показано, что на самом деле описанный регрессионный метод эквивалентен модификации МНК, включающей дополнительное требование о совпадении знака регрессионного параметра с коэффициентом корреляции между соответствующим регрессором и откликом. Описывается метод построения оптимальных выпуклых комбинаций, основанный на концепции несократимых и нерасширяемых наборов. Представлены результаты экспериментов по сравнению разработанного метода с известным алгоритмом glmnet, подтверждающие эффективность разработанного метода. Библ. 14. Табл. 2.
Ключевые слова: регрессия, выпуклая коррекция, регуляризация.
Б01: 10.7868/80044466915030047
1. ВВЕДЕНИЕ
Рассматривается стандартная задача многомерного регрессионного анализа. Переменная У предсказывается по переменным Хъ Хп с помощью линейной регрессионной функции
р0 + У" 1 р(-Х(-. Предполагается, что вектор р = ф0,..., рп) ищется по выборке (уу,х1у-,хп]), У = 1, т.
Гребневая регрессия, Лассо (см. [1]) и эластичная сеть (см. [2]) являются популярными методами поиска регрессионных коэффициентов в задачах высокой размерности. Эти методы основаны на решении оптимизационной задачи вида
л2
i=1
+ ХДР)
где X > 0 и Р(Р) = Р(Р0,..., р") — функция штрафа. Для Лассо штраф имеет вид У" |р;|, для гребневой регрессии имеет вид У" 1 р;2, для эластичной сети —
п п
(1 -а) Ув2 + аУ |р,|,
1=1 1=1
где параметр а е [0,1] характеризует компромисс между видом штрафа по гребневой регрессии и по Лассо. Чрезвычайно высокая эффективность способа регуляризации, используемого в методе эластичной сети, была доказана на большом количестве задач. Однако неизвестно, достигает ли данный метод верхнего предела эффективности.
1) Работа выполнена при финансовой поддержке РФФИ (коды проектов 14-07-00819, 14-01-90413, 14-07-00965).
Отметим существование еще одного способа регуляризации, основанного на решении оптимизационной задачи с ограничениями:
j=1
min У yj -ро - УрР
i=1
Ci(Pо, .-,Pn) > 0,
(1)
Ck(во,...> 0,
где C — некоторая функция, i = 1, ..., k. Данный способ регуляризации используется, например, вариантом Лассо, описанным в [3]. Далее мы будем рассматривать ограничения, основанные на требовании равенства знака регрессионного коэффициента перед переменной X{ в линейной регрессионной модели знаку коэффициента корреляции Y с Xi: p(Y, Xi).
Мы покажем эквивалентность метода, основанного на последних ограничениях, регрессионному методу, основанному на оптимальной выпуклой комбинации простых одномерных регрессий, которые строятся по каждой из переменных X1,..., Xn. Выпуклые комбинации широко используются в методах распознавания (см. [4], [5]). В качестве примеров также могут быть приведены методы bagging и boosting (см. [6], [7]). Следует упомянуть и методы, основанные на коллективных решениях по системам закономерностей (см. [8]).
Выпуклая коррекция используется и в регрессионных задачах. Так, в [9] рассматривались ансамбли нейросетевых алгоритмов, основанные на поиске оптимального баланса между индивидуальной прогностической способностью алгоритмов и их дивергенцией. В [10]—[12] рассматривался метод, основанный на поиске оптимальных выпуклых комбинаций простых одномерных линейных регрессий Rb ., Rn, вычисляющих значения Y по переменным X1, ., Xn, с минимальной ошибкой на обучающей выборке. Эксперименты на модельных задачах выявили достаточно высокую эффективность данного подхода. Однако одновременно было обнаружено, что дисперсия значений оптимальных выпуклых комбинаций для каждой задачи оказывается низкой. Данный эффект, по-видимому, связан со структурой разложений дисперсии для выпуклых комбинаций случайных величин.
Пусть Z = {Z1,..., Zl} — некоторое множество случайных функций, заданных на вероятностен;
ном пространстве Q, и P(Z, c) = у, icZi является произвольной выпуклой комбинацией функций из Z. Тогда для дисперсии справедливо разложение
i i i
V[P(Z,c)] = ycV(Zi) - 2yyciCje(Zi,Zj), (2)
i=i i=1 j=1
где
g(Zi, Zj) = En(Zi - EnZi - Zj + EnZj)2 и V(Zj) является дисперсией функции Zj. Данное разложение рассматривалось в [11].
Из разложения (2) следует, что V[P(Z, c)] < У' i c ¡V(Zt). Но низкая дисперсия прогнозов ведет также к снижению прогностической способности. Поэтому дополнительное линейное преобразование необходимо, чтобы улучшить последнюю. Естественно искать такое преобразование в
~ V 1 n
виде простой линейной регрессии Y по P(R,c) = у, i ciRi. Однако ошибка прогнозирования для
простой одномерной регрессии р0 + p1X монотонно зависит от коэффициента корреляции p(Y, X). Поэтому целесообразным оказывается переход от поиска выпуклых комбинаций, минимизирующих ошибку прогнозирования, к поиску выпуклых комбинаций, максимально коррелирующих с откликом.
Регрессионный метод, вычисляющий выпуклую комбинацию простых регрессий с максимальным коэффициентом корреляции, рассматривался в [13]. Было показано, что эффективность данного метода близка к эффективности эластичной сети на множестве модельных задач, в которых целевая функция и предикторы генерировались в виде линейных комбинаций не-
скольких латентных переменных. Причем для ряда сценариев эффективность метода, основанного на поиске оптимальных выпуклых комбинаций, оказалась несколько выше.
Целями настоящей работы являются: доказательство эквивалентности метода, вычисляющего выпуклые комбинации простых регрессий с максимальным коэффициентом корреляции, и метода, вычисляющего коэффициенты линейной регрессии через решение оптимизационной задачи типа (1); построение математически обоснованной процедуры поиска оптимальных выпуклых комбинаций простых регрессий и проведение сравнения разработанного метода с методами Лассо и эластичной сети.
2. ОПТИМАЛЬНЫЕ ВЫПУКЛЫЕ КОМБИНАЦИИ КАК СПОСОБ РЕГУЛЯРИЗАЦИИ
Рассмотрим метод построения оптимальных выпуклых комбинаций, включающий три шага. На первом шаге с помощью стандартного метода наименьших квадратов (МНК) строится п простых линейных регрессионных моделей, предсказывающих отклик У по каждой из переменных
ХЪ •••> Хп:
к = к = р* + ви1х1
(3)
К = Р0п + РГХ}.
На втором шаге ищется выпуклая комбинация регрессионных моделей К1, „., кп, для которой оказывается максимальным коэффициент корреляции с откликом У. Другими словами, внутри стандартного симплекса ищется такой вектор коэффициентов сь = (е?, •.., еьп), что для
Р(Д сь) = уп 1 е\к и любой выпуклой комбинации Р(Д с) = уп 1 ек, где е принадлежит стандартному симплексу, выполняется неравенство
р у, р(к, с *)] >р[у, р(к, с)]. На третьем шаге по обучающей выборке с помощью стандартного МНК строится простая линейная регрессионная функция р0 + реР(Д с), вычисляющая прогноз У по выпуклой комбинации Р (Д с).
Описанный метод далее будет называться выпуклой регрессией (ВР), а регрессионная функция
во+ве
1=1
+ ее
1=1
ВР-решением.
Пусть /р = {/|/ = 1, •.., п, р(У,Х1) Ф 0} и 10 = {1, • .., п}\/ . Очевидно, что коэффициент р;и1 равен 0, если р(У, Х;-) = 0. Предположим, что некоторое ВР-решение построено по такой выпуклой комбинации уп 1 ек, что существует / е 10, для которого е. > 0. Тогда существует идентичная выпуклая комбинация, для которой е1 > 0 только в случае, если / е /р.
Покажем эквивалентность ВР варианту метода МНК с ограничениями типа (1), для которого искомый вектор регрессионных параметров является решением оптимизационной задачи
min
|ЗеЖ п+1
(4)
- У Уз -р0 -
3=11 1=1
р;р(У, X) > 0, /6 1р, в = 0, /е /0. Справедливы следующие утверждения.
Утверждение 1. Пусть Р (Д с) является выпуклой комбинацией регрессионных функций {Д |/ е /р},
имеющих положительную дисперсию, а р0, ре являются коэффициентами стандартной МНК-ре-
грессии, связывающими У с выпуклой комбинацией Р(к, с). Тогда ограничения задачи (4) выполняются для коэффициентов ВР-решения.
Доказательство. Действительно, мы должны показать, что sign(Pг■) = sign[p(У,Х1)]. Для произвольной линейной регрессии Д = рЦ + в'Х, справедливо равенство sign(pUí) = sign[p(У,Х;-)]. Следовательно, р(У, Д) > 0, I = 1,..., п. Поскольку Р(Д,с) является суммой случайных функций с положительными коэффициентами корреляции с У, то справедливо неравенство р[У, Р(Д с)] > 0.
Следовательно, рС > 0. Из равенства р;- = свСв"' вытекает существование двух возможностей: sign(P;■) = sign(pU) или р;- = 0. Утверждение доказано.
Утверждение 2. Для произвольных регрессионных коэффициентов р 0 и р;-, ■ е I удовлетворяющих ограничениям задачи (4), существует такая точка (с1,..., сп) в стандартном симплексе и вещественные коэффициенты р 0 и р[, что оказывается справедливым равенство
р0 + ура = р0+рс уд (5)
1е1р 1е1р
Доказательство. Действительно, пусть ^ = [И, при ■ е 1р. Равенство (5) справедливо при
ГЧ
с = УЪ ее = Р0 =Р0 - Хер*
уС] Мр Мр
Теорема, описывающая отношение между двумя типами решений, следует из утверждений 1 и 2.
Теорема 1. Любое решение задачи (4) является также ВР-решением. Любое ВР-решение является также решением задачи (4).
Доказательство. Пусть вектор ф*, Р*) является решением оптимизационной задачи (4). Отметим, что согласно утверждению 2 коэффициенты (р*,..., р*) могут быть получены из коэффициентов регрессий Д,..., Д с помощью некоторой выпуклой комбинации Р(Дс*) = уп 1 с*Д и линейного преобразования р0* + рС*Р(Д с*). Последнее преобразование может быть только стандартной МНК-регрессией У по Р(Д, с*). Предположим, что р0*, рС* не являются коэффициентами стандартной МНК-регрессии. Тогда квадратичная ошибка для коэффициентов (Р*,..., р*) должна быть меньше, чем квадратичная о
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.