автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Беспереборные методы кросс-валидации для оценивания обобщающей способности регрессионных моделей

На правах рукописи

Черноусова Елена Олеговна

БЕСПЕРЕБОРНЫЕ МЕТОДЫ КРОСС-ВАЛИДАЦИИ ДЛЯ ОЦЕНИВАНИЯ ОБОБЩАЮЩЕЙ СПОСОБНОСТИ РЕГРЕССИОННЫХ МОДЕЛЕЙ

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

28 НОЯ 2013

005541227

Москва, 2013

005541227

Работа выполнена на кафедре «Интеллектуальные системы» Федерального государственного автономного образовательного учреждения высшего профессионального образования «Московский физико-технический институт (государственный университет)».

Научный руководитель: доктор технических наук, профессор

Моттль Вадим Вячеславович

Официальные оппоненты: доктор физико-математических наук, профессор

Вьюгин Владимир Вячеславович, заведующий лабораторией №1 им. М.С. Пинскера «Теория передачи информации и управления», Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. A.A. Харкевича Российской академии наук.

кандидат физико-математических наук, доцент Сулимова Валентина Вячеславовна, кафедра информационной безопасности, Государственное образовательное учреждение высшего профессионального образования "Тульский государственный университет".

Ведущая организация: Федеральное государственное бюджетное учреждение

науки Институт проблем управления им. В.А. Трапезникова Российской академии наук.

Защита состоится « 26 » декабря 2013 г. в 14:00 часов на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. A.A. Дородницына Российской академии наук», расположенном по адресу 119991, г. Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан « 22 » ноября 2013 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук

Рязанов В.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Задача восстановления объективно существующей зависимости между наблюдаемыми свойствами объектов реального мира и их некоторой скрытой характеристикой, доступной для наблюдения лишь в пределах конечной обучающей совокупности, является центральной задачи интеллектуального анализа данных. В частности, если скрытая характеристика принимает значения из конечного неупорядоченного множества, то такую задачу принято называть задачей обучения распознаванию образов, а в случае числовой скрытой характеристики говорят о задаче восстановления регрессионной зависимости. В диссертационной работе рассматривается последний случай.

Вероятностная интерпретация задачи обучения основана на предположении, что с каждым объектом из некоторого множества объектов реального мира, привлекающего внимание наблюдателя, объективно связаны значения двух его характеристик, одна из которых доступна для непосредственного наблюдения, а другая скрыта. В теории обучения обычно предполагается, что природа, случайным образом выбирая один объект, генерирует, тем самым, случайную пару значений его наблюдаемой и скрытой характеристик, причем соответствующее совместное распределение вероятностей объективно существует, но наблюдателю неизвестно. Наблюдатель всякий раз видит значение лишь наблюдаемой характеристики, в то время как природа требует, чтобы он «угадывал» значение скрытой характеристики объекта, штрафуя неправильное оценивание в соответствии с известной функцией потерь. Наблюдатель вынужден выработать решающее правило, связывающее с каждым наблюденным значением доступной характеристики объекта предполагаемое значение его скрытой характеристики. Как правило, наблюдатель формирует свое решающее правило на основе предположения о некотором параметрическом классе зависимостей, так что выбор наблюдателем конкретного решающего правила полностью задается выбором параметра. Естественной объективной оценкой «качества» решающего правила является математическое ожидание потерь, которое в теории обучения принято называть средним риском ошибки. Очевидно, что наблюдатель, выбирая вариант решающего правила, а именно значение параметра, не может вычислить средний риск ошибки, поскольку совместное распределение наблюдаемой и скрытой характеристик случайно появляющегося объекта ему неизвестно.

Единственную объективную информацию о свойствах природы, доступную наблюдателю, несет обучающая совокупность, под которой понимается конечное множество пар значений как наблюдаемой, так и скрытой характеристики объектов, случайно выбранных природой в соответствии с объективно существующим распределением вероятностей. Выбирая решающее правило, наблюдатель может лишь вычислить для всякого его варианта среднее арифметическое значение функции потерь, называемое эмпирическим риском ошибки. При выборе решающего правила общепринятым соображением, основанным на данных, является минимизация эмпирического риска в некотором классе решающих правил (variance minimization в англоязычной литературе).

Однако параметрический класс решающих правил, изначально принятый наблюдателем, может оказаться слишком широким для ограниченного объема обучающей совокупности, и средний риск ошибки результата обучения по критерию минимума эмпирического риска может оказаться неприемлемо большим. Такое явление принято называть переобучением. Другим общепринятым соображением, направленным

на уменьшение опасности переобучения, является использование априорной (регу-ляризующей) информации об «ожидаемом» решающем правиле восстановления зависимости. Другими словами, наблюдатель пытается сузить параметрический класс зависимостей, накладывая на параметр априорные регуляризирующие требования, в свою очередь контролируемые структурным параметром. Как правило, априорная информация выражена в виде некоторого функционала на классе решающих правил, подлежащего минимизации, причем обычно такой функционал содержит параметр, контролирующий отклонение решающего правила от некоторого подмножества наиболее «простых» правил, и называемый структурным параметром «сложности» класса решающих правил. Это дополнительное соображение при построении метода обучения касательно выбора решающего правила называется в англоязычной литературе bias, поскольку управляет «смещением» выбираемого решающего правила от выбранного на основе минимизации эмпирического риска.

В современной теории обучения эти два соображения объединяются в единый критерий обучения, получая тем самым регуляризованный критерий минимизации эмпирического риска. Естественно, что результат обучения, т.е. решающее правило, получаемое в качестве решения задачи минимизации, зависит от структурного параметра, отвечающего за сложность зависимости между ненаблюдаемой и наблюдаемой компонентами объекта.

Очевидным показателем «качества» выбора структурных параметров и, следовательно, получаемого решающего правила, является средний риск ошибки оценивания скрытой характеристики нового случайного объекта, не входящего в обучающую совокупность. Однако, вычисление среднего риска принципиально невозможно, поскольку наблюдателю неизвестно совместное распределение вероятностей на множестве пар значений наблюдаемой и скрытой характеристик объектов в генеральной совокупности. В качестве общепринятого компромисса на практике обычно заменяют критерий минимума среднего риска ошибки при выборе структурного параметра на его суррогат, вычисленный путем кросс-валидации единственной обучающей совокупности, доступной наблюдателю. Метод кросс-валидации (Cross-Validation)' заключается в том, что обучающая совокупность многократно разбивается на две части, по одной из которых определяется решающее правило для каждого пробного значения структурного параметра, а по другой оценивается среднее значение ошибки.

Проблемная ситуация заключается в том, что методы кросс-валидации требуют многократного повторения обучения при разных разбиениях обучающей совокупности, что определяет их чрезвычайно высокую вычислительную сложность. В частности, наиболее популярными видами кросс-валидации являются блочная кросс-валидация, заключающаяся в разбиении обучающей совокупности на достаточно большое число частей и поочередном использовании каждой части в качестве контрольной при обучении по остальным частям (K-fold Cross-Validation), и скользящий контроль2, в котором поочередно выделяется один объект в качестве контрольного, а обучение проводится по оставшимся объектам (Leave-one-out Cross-Validation). При этом число повторений обучения равно кратности разбиения обучающей сово-

1 P.A. Devijver, J. Kittler. Pattern Recognition: A Statistical Approach, Prentice-Hall, London, GB, 1982.

2 Бонгард M.M., Вайнцвайг M.H. Об оценках ожидаемого качества признаков. Проблемы кибернетики, 1968, вып. 20, с. 151-157.

купности на блоки, а в методе скользящего контроля совпадает с числом объектов в обучающей совокупности.

Для разрешения этой проблемной ситуации в диссертации предлагается общий метод, основанный на некотором предположении наблюдателя о возможном параметрическом классе совместных распределений наблюдаемой и скрытой характеристик случайно появляющегося объекта, и назван в диссертации методом неявной кросс-валидации. Метод основан на мысленном эксперименте, заключающемся в получении двух независимых выборок, по первой из которых находится решающее правило как по обучающей совокупности, а на второй измеряется эмпирический риск ошибки восстановления скрытой характеристики объекта. В качестве критерия выбора значений структурных параметров предлагается использовать математическое ожидание эмпирического риска ошибки.

В диссертации доказано, что в случае квадратичной функции потерь, адекватной широкому классу задач восстановления регрессионных зависимостей, и квадратичного регуляризующего штрафа, налагаемого на вектор искомых коэффициентов регрессии, несмещенная оценка математического ожидания эмпирического риска ошибки выражается через элементы обучающей совокупности в виде простой формулы. Показано, что частным случаем такого критерия выбора структурных параметров при некоторых специальных предположениях о модели данных является известный информационный критерий Акаике3.

Чрезвычайная актуальность автоматического сокращения размерности представления объектов непосредственно в ходе обучения приводит к необходимости применения более сложной регуляризующей функции от вектора искомых коэффициентов регрессии, нежели квадратичная, а именно, квадратично-модульной функции (в англоязычной литературе соответствующий критерий обучения получил название Elastic Net4). Решающее правило наблюдателя, получаемое в результате обучения, характеризуется двумя структурыми параметрами, отвечающими за квадратичную и модульную регуляризацию, но для их выбора исходный метод неявной (беспереборной) кросс-валидации в чистом виде оказывается неприменимым в силу неквад-ратичности критерия обучения. Для того, чтобы избежать применения обычных переборных методов кросс-валидации, в диссертации используется тот факт, что с каждой парой значений числовых структурных параметров однозначно связано разбиение множества числовых признаков объектов на три непересекающихся подмножества, полученных с учетом знака и обнуления коэффициентов регрессии в точке минимума критерия. Именно такое разбиение, полученное согласно решению задачи обучения, предлагается использовать в качестве вторичного нечислового структурного параметра модели, подлежащего кросс-валидации. При фиксации такого структурного параметра критерий обучения, в исходном варианте не являющийся квадратичным, становится квадратичным по активным (ненулевым) коэффициентам регрессии, и к нему полностью применим разработанный ранее метод неявной (беспереборной) кросс-валидации.

3 Hirotugu Akaike. A new look at the statistical model identification. IEEE Transactions on Automatic Control, 1974, Vol. 19, pp. 716-723.

4 H. Zou, T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society, 67:301-320,2005.

Объект исследования: задачи восстановления числовых зависимостей между скрытой и наблюдаемой характеристиками объектов реального мира по эмпирическим данным.

Предмет исследования: выбор структурных параметров решающих правил, восстанавливающих числовую зависимость между скрытой и наблюдаемой характеристиками объектов, с помощью беспереборных методов кросс-валидации для оценивания адекватности решения на генеральной совокупности по единственно доступной исследователю выборке. Цели и задачи диссертации:

1. Показать, что идея информационного критерия Акаике для выбора структурного параметра основана на принципе неявной кросс-валидации.

2. Разработать беспереборный критерий кросс-валидации для квадратичной задачи оценивания линейной регрессии, в котором классический критерий Акаике являлся бы частным случаем.

3. Разработать беспереборный критерий кросс-валидации для неквадратичной задачи оценивания линейной регрессии с квадратично-модульной регуляризацией.

Общая методтка исследования: Исследование базируется на использовании классических понятий теории восстановления регрессионных зависимостей, теории вероятности, математической статистики, теории оптимизации.

Научная новизна. В работе предложены два варианта нового беспереборного метода кросс-валидации для оценивания обобщающей способности регрессионных моделей, отличающиеся областью применимости. Оба варианта являются альтернативами классическим способам оценивания обобщающей способности, основанным на принципе кросс-валидации.

Положения, выносимые на защиту.

1. Принцип неявной кросс-валидации для оценивания обобщающей способности линейно-квадратичных моделей числовых зависимостей.

2. Исследование природы классического информационного критерия Акаике как простейшего частного случая критерия неявной кросс-валидации.

3. Критерий неявной кросс-валидации для выбора степени волатильности модели нестационарной регрессии.

4. Критерий неявной кросс-валидации для выбора степени подавления нерелевантных регрессоров влинейно-квадратичной модели числовой регрессии.

5. Критерий неявной кросс-валидации для выбора уровня селективности формирования подмножества релевантных регрессоров в квадратично-модульной модели Elastic Net.

Достоверность полученных результатов подтверждается доказательствами сформулированных теорем и проверкой полученных результатов на модельных экспериментах и на реальных данных.

Практическая значимость результатов диссертации заключается в том, что предложенные беспереборные методы кросс-валидации для оценивания обобщающей способности регрессионных моделей являются (в силу беспереборности) вычислительно эффективными в сравнении с классическими (переборными) методами кросс-валидации, основанными на многократном повторении процедуры обучения и контроля качества решающего правила, полученного на этапе обучения, на различных разбиениях исходной выборки.

Связь с плановыми научными исследованиями. Работа выполнена при поддержке грантов Российского фонда фундаментальных исследований №№ 11-07-00409-а, 11-07-00634-а, 12-07-13142-офи-м и при поддержке Лаборатории структурных методов анализа данных в предсказательном моделировании.

Апробация работы. Основные положения и результаты диссертации докладывались на конференциях «Интеллектуализация обработки информации ИОИ -2010» (Республика Кипр, г. Пафос, 2010 г.), «Интеллектуализация обработки информации ИОИ - 2012» (Черногория, г. Будва, 2012 г.), «Математические методы распознавания образов ММРО - 2009» (г. Суздаль, 2009 г.), «Математические методы распознавания образов ММРО - 2013» (г. Казань, 2013 г.).

Публикации. По тематике работы опубликовано 8 статей, в том числе 2 статьи в журналах, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, 4 глав основного содержания, заключения и библиографии. Работа содержит 87 страниц основного текста.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность исследований по разработке методов эффективного оценивания обобщающей способности регрессионных моделей данных, указывается степень разработанности исследуемой проблемы, приведены цели и задачи проводимых исследований, указывается на научную новизну полученных результатов и их теоретическую и практическую значимость, приведены положения, выносимые на защиту, а также сведения о структуре диссертации, степени достоверности результатов исследований и их апробации.

В первой главе рассматривается общая постановка типичной задачи оценивания числовой зависимости между двумя характеристиками объектов реальной природы. А именно, пусть имеется некоторое множество объектов реального мира Q, привлекающее внимание наблюдателя. Пусть с каждым объектом сое £2 связаны значения двух его характеристик x(co):fi —>Х и .у (со): Q —> Y, первая из которых доступна для непосредственного наблюдения, а наблюдение второй невозможно либо, по крайней мере, затруднено. Цель исследователя - анализируя конечную обучающую совокупность объектов, в пределах которой обе характеристики известны

(х, у) = {(*,. , у,) = (х(со,), y((Oj)), j = 1,..., TV], (1)

сформировать для нового объекта сое Q, не представленного в обучении, оценку его скрытой характеристики по наблюдаемой у(х): X —> Y. Такая задача называется задачей обучения по прецедентам.

Предположим, что природа случайным образом многократно и независимо выбирает один объект из множества Q, генерируя, тем самым, пару значений

сое Q: (х,у) = (х(со), j(co)), хе X, ye Y, (2)

согласно неизвестной наблюдателю «истинной» совместной плотности распределения /*(х,у) > 0: X х Y —» R, jj/'(x,y)dydx = 1.

X Y

Штаф за неверное оценивание скрытой характеристики объекта измеряется действительным числом Loss е К, являющимся известной функцией от фактического и оцененного значений ненаблюдаемой характеристики объекта Loss(y,y): Y х Y —> М. Такую функцию принято называть функцией потерь. Предполагается,

что наблюдатель формирует свое решающее правило в пределах выбранного им некоторого параметрического класса зависимостей

j>(*,a):X-»Y, ае W, (3)

так что выбор оценки ненаблюдаемой компоненты полностью определяется выбором параметра а, а функция потерь Loss (у, у(х,а)) есть функция от трех переменных q(y,x,a) = Loss(y,y(x,a)).

Вообще говоря, естественно желание наблюдателя выбирать вектор параметров решающего правила из условия минимума средних потерь при оценивании скрытой характеристики (среднего риска ошибки решающего правила):

г„00 = г„ [Я',а)] = \\q{x,y,a)f{x,y)dydx, (4)

X Y

rov (а) —> min(a et"). (5)

Понятно, однако, что такой выбор принципиально невозможен, поскольку неизвестно «истинное» распределение f*(x,y).

Взамен минимизации среднего риска (5) наблюдатель, в качестве естественного компромисса, может организовать обучение, то есть выбор параметра решающего правила оценивания скрытой характеристики объекта а е М", на основе минимизации эмпирического риска ошибки, построенного по обучающей совокупности:

1 N 1 r«™,, (а) = —Е Ч(х,' Уj >:а> = ^ ß(x' У'а)' (6)

remp{ a)^min(ae М"), т.е. у,,а) min(ae Е"). (7)

j=]

Если предполагаемый параметрический класс решающих правил у(х,а): X —> Y,

a G К", достаточно широк, то наблюдатель сможет достаточно хорошо аппроксимировать числовую зависимость между характеристиками объектов и обучающей совокупности. Однако, в силу конечности множества прецедентов выбранная модель зависимостей может быть неадекватной на генеральной совокупности. Во избежание этой проблемы, наблюдатель пытается сузить параметрический класс зависимостей, накладывая на параметр а априорные регуляризирующие требования, формулируемые в терминах минимизации некоторого функционала

V(a,X) —> min(a), (8)

где X - некоторый структурный скалярный или векторный параметр, контролирующий нежелательность отклонения параметра aeR", т.е. решающего правила у(х,а), от некоторого подмножества наиболее «простых» правил Ае К".

Итоговое компромиссное решение для выбора вектора параметров а решающего правила осуществляется с помощью критерия минимизации регуляризованного эмпирического риска

а, (х, у) = arg min {0(х, у, а) + V(a, Я.)}. (9)

а

Ясно, что результат обучения (9) зависит от параметра X. Выбор адекватного значения структурного параметра X, отвечающего за степень регуляризации параметрического класса зависимостей _у(х,а):Х—>Y с помощью минимизации функционала V(a,X) —> min(a), является одной из ключевых задач машинного обучения.

Действительно, если рассмотреть «наименее регуляризующее» априорное требование V(aХ)~ const, aeR", то процедуры машинного обучения, как правило, стремятся подобрать параметрическую зависимость >>(х,а), которая «слишком хорошо» связывает наблюдаемую и скрытую характеристики для объектов из обучающей совокупности, но оказывается неадекватной для произвольных объектов генеральной совокупности. В литературе такое явление получило термин «переобучения» (overfitting). Напротив, выбор «сильного регуляризующего» априорного требования К(а,А.') = 0, ag Ае К", приводит к проблеме «недообучения» (underfitting), когда регрессионная модель слишком проста и не способна хорошо описать эмпирические данные.

В теории машинного обучения есть ряд классических методов выбора структурного параметра модели на основе единственной обучающей совокупности.

В теории В.Н. Вапника и А.Я. Червоненкиса5 сформулирован принцип минимизации структурного риска в задачах обучения распознаванию образов ye {-1,1} по обучающей совокупности размера N

Г = argmin[(l/7V)ö(x,y,ä,(x,y)) + понимаемого как сумма минимального эмпирического риска, достижимого в выбранном классе решающих правил g(x,y,äx(x,y)), определяемом в наших терминах выбором структурного параметра X, и верхней границы превышения среднего риска для этого класса на генеральной совокупности над эмпирическим риском Д(А., N)6. Зависимость этой верхней границы от класса решающих правил получена лишь для простейшей функции потерь, адекватной только задачам распознавания образов, под структурным параметром понимается эффективная размерности множества решающих правил, получившая в литературе название VC-размерности (Vapnik-Chervonenkis Dimension). К тому же, верхняя граница Д(Х, N) определена из общих неравенств теории вероятностей на основе созданной авторами теории равномерной близости эмпирических средних к математическим ожиданиям5, и является чрезвычайно завышенной. В исходном виде этот принцип неприменим к задачам восстановления числовых зависимостей.

Однако сама идея минимизации суммы эмпирического риска и некоторого штрафа за сложность класса моделей была сформулирована японским математиком Хиротугу Акаике3 (с. 10). Применительно к задаче восстановления зависимости >'(-v) предположим, что наблюдатель рассматривает вероятностную связь между скрытой и наблюдаемой переменными в виде параметрического семейства плотностей распределений ф(_у | х,а). Пусть размерность вектора а е R" слишком велика для объема N доступной обучающей совокупности (1), так что оценка максимального правдоподобия а(х, у) = arg шах In Ф(у | х, а) = arg max In ф( vy | xj, а) недостаточно надежна.

Простота ситуации, рассматриваемой Акаике, заключается в том, что компоненты вектора параметров а = (я,,...,ап) предполагаются априори упорядоченными по

5 Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. М.: Наука, 1974. Вапник В. Н. Принцип структурной минимизации в задачах восстановления зависимостей по

эмпирическим данным. Диссертация д.ф.-м.н. Институт проблем управления АН СССР, 1984.

«важности», и структурный параметр X понимается как целое число 0 < X < п, ограничивающее количество компонент, отличных от нуля

а = (ах, а„_,) = (<з,,ах, ак+]=0,..., а= 0). (10)

При дополнительном предположении, что логарифмическая функция правдоподобия 1пФ(у|х,а) допускает квадратичную аппроксимацию, Хиротугу Акаике доказал, что решение

X' =argmin{- 1пФ(у|х,ах(х,у)) + А.},

максимум правдоподобия (П)

эмпирический риск

основанное на штрафе, равном просто числу активных параметров X, в некотором усредненном смысле максимизирует количество информации Кульбака о неизвестном распределении природы, доступном лишь в виде конечной выборки (х,у), содержащееся в оценке параметра по самой этой выборке.

Формулу (11) Акаике получил в предположении, что гессиан V.2ia 1пФ(у | х,а) является матрицей полного ранга в точке максимума правдоподобия, и, как следствие, оценка ах(х,у) единственна. Чтобы учесть более общий случай, штраф X должен быть заменен рангом этой матрицы:

Г=агётш{-1пФ(у|х,а,(х,у)) +Rank[V23a 1пФ(у | х,ах(х,у))]} . (12)

Очевидно, что предположение об априорной упорядоченности компонент вектора коэффициентов регрессии неадекватно большинству практических задач.

В качестве универсального метода борьбы с «проклятием единственной выборки» в ходе оценки обобщающей способности класса моделей широкую популярность получили метод кросс-валидации1 и его наиболее часто используемый вариант, известный как скользящий контроль2 (с. 4), свободные от каких бы то ни было предположений о неизвестном распределении, породившем анализируемую выборку. Эти методы, в свою очередь, можно рассматривать как частные случаи методов, известных под общим названием Resampling1. В основе этих методов лежит идея многократного дробления исходной выборки на две части, одна их которых используется для обучения, т.е. для оценивания параметров модели искомой зависимости, а другая - для оценивания качества обучения. Неизбежной платой за универсальность метода кросс-валидации является его высокая вычислительная сложность.

Первая глава завершается постановкой задачи диссертационного исследования, сформулированной как разработка принципа выбора структурного параметра модели числовой зависимости по единственной обучающей совокупности, доступной наблюдателю, который сочетал бы, с одной стороны, универсальность общей идеи кросс-валидации и, с другой стороны, сохранял бы беспереборный характер, являющийся вычислительным достоинством информационного криетрия Акаике.

Во второй главе изложена основная математическая идея диссертации, названная принципом неявной кросс-валидации.

Представим неизвестную наблюдателю совместную плотность распределения случайной выборки (х,у) (обучающей совокупности) (1)

7 B. Efron. The jackknife, the bootstrap, and other resampling plans. Society of Industrial and Applied Mathematics CBMS-NSF Monographs, 38, 1982.

7=1

как произведение маргинальной плотности распределения наблюдаемой характеристики и условной плотности распределения ненаблюдаемой характеристики:

Г(х,у) = Ц>'{у\х)Е'{х), Г(х,у) = Пф*0>,- |х,)П£*(*,-) = Ф*(у|х)е*(х). (13)

,7=1 ,7=1

Ф'(у|х) С»

Дальнейшие построения основаны на предположении о структуре неизвестного условного распределения Ф*(у|х), названном в диссертации первой эвристикой наблюдателя.

Первая эвристика наблюдателя о незлонамеренности природы. Наблюдатель предполагает, что это распределение является неизвестной смесью ^'(а) известных распределений Ф(у | х,а)

Ф*(у|х)=|ф(у|х,а)Ч'*(аУа, (14)

К"

причем природа чаще генерирует пары с низким значением штрафа

Ф(У I х,а) ехр{—£)(у, х,а)} . (15)

Иными словами, первая эвристика наблюдателя заключается в предположении, что он правильно «угадал» функцию потерь (6) и, следовательно, класс решающих правил (9).

Дополнительный коэффициент с! в (15) выражает предполагаемую степень обоснованности такого предположения — чем больше с/, тем сильнее уверенность наблюдателя. Заметим, что при этом наблюдатель по-прежнему не делает никаких предположений о характере распределения скрытого параметра решающего правила 4>*(а) в (14).

Предлагаемый в диссертации принцип неявной кросс-валидации основан на следующем мысленном эксперименте наблюдателя. Пусть природа разыграла конкретное значение параметра согласно Ч'*(а), а также выборку наблюдаемых характеристик объектов согласно С(х) (13). Затем, дважды применив условное распределение Ф(у|х,а) (15), получила две реализации у = К" , у = (уп ...,у„)е М", об-

разующие две воображаемые совокупности которые наблюдатель мысленно рассматривает как контрольную (х,у) и обучающую (х,у). Если бы наблюдатель знал реализации у и у, то мог бы для всякого значения X вычислить оценку по обучающей совокупности ах(у,х) и подставить в функцию потерь для контрольной совокупности, вычислив потери на мысленном контроле 2(у,х,ах(у,х)). Идея скрытой кросс-валидации заключается в минимизации математического ожидания потерь:

}{|б(у.х,ах (у,х))||ф(у|х,а)ф(у|х,а)4/*(а)й'а|0*(х)а'у с?у с/х—>тт(?1,). (16) Согласно первой эвристике наблюдателя (1/с2 )£?(х, у, а) = -1пФ(у | х, а) + со/«7 (15), поэтому идея скрытой кросс-валидации | [1пФ(у[ х, ах(у, х))]ф(у| х, п)с1у —> тах (16) есть максимизация информации Кульбака о распределении Ф(у|х,а), содержащейся в его оценке по другой выборке Ф(у|х,ах(у,х)). В силу этого обстоятельства крите-

рии неявной кросс-валидацин уместно называть информационными и рассматривать их как обобщение классической идеи Хиротугу Акаике.

В реальности у наблюдателя имеется единственная обучающая выборка (х,у), и он может подставить в функцию потерь лишь оценку, вычисленную по той же выборке 2(у,х,ах(у,х)). Насколько испортится критерий, подлежащий максимизации, по сравнению с идеей (16)? Каким должен быть штраф за использование оценки параметра, вычисленного по той же выборке?

Теорема 1. Критерий максимизации по значению структурного параметра X (16) допускает эквивалентную запись:

X' = а^ттЩ |0(у,х,ах(у,х))Ф(у |х,а)</ун

[ ^6(у,хЛ(у,х))-е(у,х,ах(у,х)^Ф(у | х,а)Ф(у | х,а)</у</у - ехр{-(1/о2)[е(у,х,а) + е(у,х,а)]}

] (П)

функционал от функции потерь ()(»,х,а) и критерия обучения

Основная идея принципа неявной кросс-валидации базируется на том факте, что, как показано далее во второй главе, для многих типичных функций потерь (9(у,х,а) и критериев обучения ах(у,х), адекватных широкому классу практических задач, функционал во втором слагаемом в (17), играющий роль штрафа за использование оценки параметра, вычисленного по той же выборке, не зависит от а:

||^2(у,х,а,(у,х))-2(у,х,ах(у,х))^Ф(у | х,а)Ф(у | = о2Д(^,х). (18)

Для этого класса задач обучения критерий неявной кросс-валидации (17), установленный Теоремой 1 принимает следующий простой вид:

Г =аг8тш{и [с/2(у,х,ах(у,х)) + Д(Х,х)]Г(х,у)^}. (19)

Однако и в таком виде критерий по-прежнему неприменим, так как распределение генеральной совокупности F*(x,y) в (19) неизвестно.

Вторая эвристика наблюдателя заключается в замене математического ожидания его несмещенной оценкой по единственной доступной наблюдателю выборке уеК":

Я(у,х) = агешш{^ £(у,х,ах(у,х)) +Д(Х,х)} (20)

X '-■-Г-1

эмпирическии риск

структурный риск

Далее во второй главе рассмотрен важнейший частный случай линейно-квадратичной модели данных, адекватной многим практическим задачам восстановления числовых зависимостей, и доказано, что этот частный случай удовлетворяет основному предположению о независимости штрафа за использование оценки параметра решающего правила, вычисленного по той же выборке, от самого значения параметра (18). Класс линейно-квадратичных моделей определяется следующими предположениями.

Во-первых, предполагается, что наблюдатель выбрал линейный класс решающих правил оценивания скрытой характеристики объектов (3)

Ях)=агд::М"-»К, а = (а, ■■■а11)Т,х = (х, ■■■х„)т е К", уеМ. (21)

Это предположение позволяет предварительно центрировать и нормировать обучающую совокупность размера N (1)

(Х,у)={(л^,д^), Х=(лг, —матрица (пхЫ), уе К",

= = 1 для всех ' = 1'-'и- (22)

Во-вторых, предполагается, что наблюдатель выбрал квадратичную функцию потерь (6) £(у,Х,а) = ¿(Уу -а^.)2 = (у - Хга)г(У -Хга) . (23)

Наконец, в-третьих, предполагается квадратичная регуляризация (8)

К(аД) = а^В^а, (24)

полностью определяемая неотрицательно определенной квадратной матрицей Вх (,пхп), произвольным образом зависящей от выбора структурного параметра X, скалярного или векторного.

При таких предположениях задача обучения по предъявленной обучающей совокупности (9) становится квадратичной

а1(у,Х) = агётпт{агВ1а+ (у - Хга)г(у - Хга)] (25)

аеМ" 1 }

и численно сводится, вообще говоря, к решению системы п линейных уравнений.

Теорема 2. В методе неявной кросс-валидации для линейно-квадратичной модели (21)-(24) штраф за подстановку в функцию потерь оценки параметра, вычисленной по той же выборке (18), не зависит от исходного значения параметра ае К" и определяется выражением

, XX г(пхп). (26)

А(к,Х) = Тг ХКт(ХХт+ВхУ

В модели с квадратичной функцией потерь первая эвристика наблюдателя включает в себя предположение об условно-нормальном распределении наблюдаемых характеристик объектов (15), поэтому уместно использовать обозначение с1 = 1/2о2, прямо указывающее на дисперсию этого распределения

ф(у I х>а'°) - 0*(2я)*/2 ехр|-^(У,х,а)|. (27)

Таким образом, критерий . неявной кросс-валидации (20) для общей линейно-квадратичной модели принимает вид:

^(у,Х)=агётт|^г(у-Х^х(у,Х))Г(у-Хгйх(у>Х))+ Д(^Х)

эмпирический риск штраф за сложность J ^>8)

Г Т, г Ч-П структурный риск

А(Х,Х) = Тг ХХг(ХХг+Вх) .

В частности, предположение об априорной упорядоченности коэффициентов регрессии (10) при отсутствии априорных предположений об их значениях, лежащее в основе классического информационного критерия Акаике, выражается специальным видом матрицы квадратичной регуляризации (24):

в,

1 •■ • X

1/р. ■ 0 0- •0

0 • - 1/р 0 - •0

0 • ■0 р; •0

0 • • 0 0- •р

(29)

Введем также обозначение хХ] = (х^ ■■■хХ1)/ е К'' для первых X компонент векторов наблюдаемых характеристик объектов обучающей совокупности в дополнение к (22) и Хх =(дсХ1 Для матрицы (ХхЛ'), составленной из них как из столбцов, соот-

ветственно, - матрица (ХхХ).

Теорема 3. Величина штрафа (26) неявной кросс-валидации с квадратичной регуляризацией (29) определяется выражением А(Х.,X) = Яапк(\хХ[). Если ХхХ[ есть матрица полного ранга, то Д(А., X) = X.

Эти утверждения эквивалентно классическому критерию Акаике (11)-(12).

Во второй главе рассмотрен также способ оценивания дисперсии наблюдений о2, входящей как свободный параметр в (27) и (28). Для его оценивания вместе с параметром решающего правила а предлагается дополнить мысленный эксперимент наблюдателя предположением, что природа применила условное распределение Ф(у|х,а,о) (27) не дважды, а трижды, и получила три независимые реализации: уК^.-.У^еМ", У=(>'1>-..У*)еКЛ'> Iкй,-,^)«^", образовав, таким образом три независимые обучающие совокупности (Х,у), (Х,у) и (X,у), рассматриваемые соответственно как контрольная (Х,у), обучающая для ах(у,х) и обучающая для

62(Х,у) =(1/Л0(у-Хгах(Х,у)) (у-Хгах(Х,у)). Однако в реальности у наблюдателя имеется едиственная выборка (Х,у).

Теорема 4. Критерий неявной кросс-валидации для неизвестной дисперсии наблюдений:

Х(у, Х)=а^ тЫ — 1п (X, у) + -

I2

ОДу)

А (Х,Х

ХХТ(ХХТ+ Вх)~'

(30)

д2(Х,у)=^(у-Хгах(у,Х))'(у-Хгах(у,Х)), А (Х,Х)=Тг

В третьей главе рассмотрены особенности применения метода неявной кросс-валидации для трех частных видов квадратичной модели линейной регрессии.

Нестационарная регрессия с неизвестной степенью нестационарности отличается тем, что вместо обучающей совокупности независимых данных анализу подлежит пара процессов на оси дискретного времени

Требуется найти линейную зависимость скалярной компоненты процесса у, от векторной компоненты, предполагая, что искомый вектор коэффициентов регрессии сам изменяется во времени:

Заметим, что совокупность искомых коэффициентов регрессии многократно превышает число наблюдений, поэтому бессмысленно пытаться минимизировать квадратичную функцию потерь

Xq(y,,х„ а,) = ]£>-а?х, )2 -> min ((а,,..., а„ )е R"*).

i=i i=i

В качестве квадратичного условия регуляризации выступает предположение о медленном изменении модели регрессии во времени

!£(a,-V,a,_,)r(a,-V,a,_,) Л.

—» min

где последовательность заданных квадратных матриц У2,...,УЫ выражает понимание «медленного изменения» в смысле конкретного процесса реального мира, подлежащего изучению, но это условие также не имеет смысла как отдельная задача оптимизации.

Регуляризованный критерий оценивания модели нестационарной регрессии естественно построить как баланс между этими взаимно противоречивыми условиями

¿(у-а:х,)2+|Х(а,-У,а,_|)г(а-Ча,.1)^тт((а1,...,а;,)еК"л'), (31)

,=1 Л ,=2

где структурный параметр X определяет степень изменчивости во времени последовательности оценок векторных коэффициентов регрессии - чем больше X, тем более волатильна получаемая последовательность.

Несмотря на большое число переменных, задача (31) легко численно решается за время, пропорциональное длине временного ряда Ы, с помощью фильтра-интерполятора Калмана-Бьюси, реализующего принцип квадратичного динамического программирования8.

Задача (31) является частным случаем общей линейно-квадратичной задачи (25) с матрицей регуляризации специального вида

В, =-

v2'v2

-VT

-v,

о

V3'V3+I -v3

-vi ■-.

vrv

N N

о

+ 1 -V,

о

о

-V I

* N 1

(nNxnN).

(32)

Теорема 5. С учетом обозначения (32) критерии неявной кросс-валидации, соответственно, для задачи оценивания нестационарной регрессии с заданной и оцениваемой дисперсией наблюдений имеют вид, аналогичный (28) и (30).

Однако зависимость штрафного члена от структурного параметра волатильности оценок требует специального исследования.

Теорема 6. Эффективная размерность lim А(Х, X) = ^

Штрафной член Д(А.,Х) играет здесь роль эффективной размерности задачи. При малых значениях X модель становится стационарной, и вся последовательность оценок определяется первым вектором коэффициентов регрессии а, е R", поэтому

8 M. Markov, O. Krasotkina, V. Mottl, I. Muchnik. Time-varying regression model with unknown time-volatility for nonstationary signal analysis. Proceedings of the 8th 1ASTED International Conference on Signal and Image Processing. Honolulu, Hawaii, USA, August 14-16, 2006, paper 534-196.

эффективная размерность совпадает с числом регрессоров п. При очень больших значениях X нет никакой априорной информации об nN значениях (a, ■•■aw), но по N наблюдениям все равно можно оценить не более N параметров, поэтому эффективная размерность не превышает длины временного ряда.

С вычислительной точки зрения преимущества неявной кросс-валидации перед прямым скользящим контролем очевидны - для каждого пробного значения параметра X временной ряд обрабатывается один раз вместо N раз. Однако сравнить получаемые результаты можно лишь экспериментально.

Модельные эксперименты дают возможность придать абсолютный смысл понятию «подходящего» значения параметра нестационарности в модели нестационарной регрессии. Качество конкретной процедуры анализа временного ряда естественно оценивать по относительному отклонению восстановленной последовательности коэффициентов регрессии от истинной последовательности, в точности известной в модельных данных. Серия модельных экспериментов показала практически одинаковый разброс оценок последовательностей коэффициентов регрессии, полученных при подборе волатильности модели по методу неявной кросс-валидации и по скользящему контролю.

Обработка реальных данных дала тот же результат. Мы применили динамическую регрессионную модель скрытого долевого состава инвестиционного портфеля9 к опубликованным временным рядам периодических доходностей инвестиционной компании Laudus Rosenberg Value Long/Short Fund yx,...,yN в течении TV = 60 месяцев в интервале с января 2001 года по декабрь 2005 года вместе с известными по биржевым сводкам временными рядами индексов доходностей 10 основных секторов экономики х,,...,хд,, х, 6 К10. Долевой состав портфеля относительно этих индексов a,,...,a^, а, ей18, оценивался как последовательность коэффициентов нестационарной регрессии. В такой модели параметр нестационарности X имеет смысл неизвестной волатильности состава портфеля во времени.

Временные ряды восстановленного долевого состава портфеля с коэффициентом волатильности, выбранным двумя методами, показывают, что критерии дают весьма близкие результаты.

Вернемся к рассмотрению обычных задач оценивания регрессионных моделей, связанных с анализом обучающих совокупностей, рассматриваемых как результат многократных независимых экспериментов (21)-(22). Для практики типична ситуация, когда число пробных регрессоров п, доступных наблюдателю, превосходит число наблюдений N, и актуальна задача сокращения числа активных регрессоров и, соответственно, коэффициентов регрессии. Мы рассмотрим применение метода неявной кросс-валидации для выбора наиболее подходящего уровня сложности модели для двух спо-

9 M. Markov, I. Muchnik, V. Mottl, O. Krasotkina. Dynamic analysis of hedge funds. Proceedings of the

8th IASTED International Conference on Financial Engineering and Applications. MIT, Cambridge,

Massachusetts, USA, October 9-11, 2006, paper 546-028.

неявная кросс-вадидация скользящий контроль

собов отбора регрессоров, один из которых подавляет «лишние» регрессоры «мягким » путем, снижая степень их участия в модели, в то время как второй способ полностью удаляет неинформативные регрессоры из модели.

«Мягкое» подавление нерелевантных регрессоров. Соответствующий способ предложил аспирант Тульского государственного университета Нгуен Чонг Тинь10. В качестве основы он использовал диагональную квадратичную регуляризацию

ах(у,Х) = агВтт {агВх* + (У ~ Хга)г(у - Хга)} (33)

ае К" 1 '

с векторным структурным параметром X = (А,,,...,Л,Л), отличающуюся от обычной ридж-регрессии только тем, что коэффициенты, штрафующие отклонение коэффициентов регрессии от нуля, приняты разными для разных регрессоров

агВха=^"' {УX,)а] . Если Л.,—>0, то ¿¡¡(у,Х)—>0, и /-й регрессор существенно подавляется. Для автоматического индивидуального выбора коэффициента \/Х1 для каждого регрессора, в диссертации10 предложено использовать модифицированный критерий обучения

(ä- (y,XU(y,X))=aigmin af+fj

+(у-Хга)г(у-Хга) ,(34)

i_L+ 1+1

содержащий дополнительное второе слагаемое в регуляризующем члене, и предложен алгоритм численного решения расширенной задачи оптимизации. Коэффициент Ц > 0 в дополнительном слагаемом играет роль вспомогательного структурного параметра селективности отбора регрессоров — чем больше ц, тем большее число штрафных коэффициентов 1/Х, становятся очень большими, заставляя соответствующие коэффициенты регрессии приближаться к нулю в точке минимума критерия а, —> 0, подавляя соответствующие регрессоры и уменьшая тем самым эффективную размерность модели.

Для последовательности пробных значений селективности ц.(|)<...<ц.(т) алгоритм обучения Нгуена дает последовательность моделей уменьшающейся сложности А,(1),...,А,<1Я). В своей диссертации10 он использовал обычный алгоритм скользящего контроля для выбора оптимального значегам селективности, требующий для каждого пробного значения ц.'*' решать задачу обучения N раз. В настоящей диссертации мы используем для этого беспереборный метод неявной кросс-валидации.

Для каждого из полученных пробных значений векторного параметра регуляризации Л.(|), ...,Х(т) модель (33) является линейно-квадратичной (25) с диагональной матрицей ). Дисперсию наблюдения о в (27) вряд ли можно считать известной, поэтому следует использовать критерий неявной кросс-валидации (30).

Теорема 7. Эффективная размерность lim ^

Мы исследовали такой способ выбора селективности отбора регрессоров, используя тот же модельный эксперимент, который описан в диссертации10.

10 Нгуен Чонг Тинь. Методы селективного комбинирования признаковой информации в задаче оценивания регрессионной зависимости. Дисс. к.ф.-м.н. Тульский гос. унив., 2013.

Полное подавление нерелевантных регрессоров. Способ полного подавления нерелевантных регрессоров предложен в работе" под названием критерия обучения Elastic Net. Он опирается на обычную квадратичную модель ридж-регрессии

ap(y,X)=argmin{pX^ + (y-X^(y-X^a)}, где /={!,.-,«}-{—(35)

но отличается от нее наличием дополнительного регуляризующего слагаемого, штрафующего отклонение от нуля абсолютных значений коэффициентов регрессии:

a^(y,X) = argmin | + (у-Хга)г(у-Хга)|. (36)

asR" I J

Обычно ридж-коэффициент Р > О принимают достаточно малым, только чтобы преодолеть возможную вырожденность матрицы (26), если исходное число регрессоров превышает объем обучающей совокупности п> N (22). В качестве рабочего структурного параметра выступает коэффициент селективности jj. > 0. Чем больше р., тем большее число коэффициентов регрессии оказываются в точности равными нулю а, м=0 в точке минимума выпуклого критерия обучения (36).

В диссертации аспиранта МФТИ Николая Разина доказано, что для всякого значения селективности |Х полностью определено разбиение (Partitioning) PM=/~U/*U/° исходного полного множества регрессоров / = {1,...,л} на три подмножества /~={/б/:а| Ц<0}, /*={/e/:altl>0} и /°= {г'е/:а,ц-0}, так что только объединение первых двух подмножеств IJ/^c/ есть множество активных регрессоров в точке минимума критерия обучения (36), в то время как остальные регрес-соры /°с/ полностью удалены из модели.

Алгоритм Разина дает последовательность пробных значений селективности ц"|<...<д<"') и соответствующую последовательность моделей в основном уменьшающейся сложности, хотя полную вложенность подмножеств активных регрессоров /з/(|)з... =э/(т)=0 гарантировать, вообще говоря, нельзя. Остается вопрос о выборе «оптимального» значения селективности. Для ответа на него принято использовать алгоритм скользящего контроля, требующий повторения обучения по критерию Elastic Net (36) N раз для каждого пробного значения р."1.

Идея данной диссертации заключается в интерпретации подмножества активных (релевантных) регрессоров I{k)czl как самостоятельного структурного параметра модели вместо исходного значения селективности (i(i>. Для каждого такого разбиения исходный критерий ридж-регрессии (35) принимает простой вид:

a(l)= arg min \ р ^ X а1Хц-У f >где пк~I ■'<*> I ~ число активных регрессоров.

H. Zou and Т. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society, 2005, Vol. 67, pp. 301-320.

Разин H.A. Выпуклые критерии и параллелизуемые алгоритмы селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим данным. Дисс. к.ф.-м.н. ВЦ РАН, 2013.

Теорема 8. Критерий неявной кросс-валидации:

¿ = argminj|ln(a<*>)V^|^j, где Д«> = 7>{xtx[ (Х,Х[ )"'},

X, = (i\-rj, х{ = (х0, ie Ik)e R"', (¿">)! - 2>,(%)2

^ J'1 '€/,

Такой способ выбора селективности отбора регрессоров исследован в том же

модельном эксперименте, который описан в диссертации.

В заключении перечислены следующие основные результаты:

1. Разработан метод неявной кросс-валидации для оценивания обобщающей способности линейно-квадратичных моделей числовых зависимостей.

2. Исследована природа классического информационного критерия Акаике как простейшего частного случая критерия неявной кросс-валидации.

3. Разработан критерий неявной кросс-валидации для выбора степени волатильности модели нестационарной регрессии.

4. Разработан критерий неявной кросс-валидации для выбора степени подавления нерелевантных регрессоров влинейно-квадратичной модели числовой регрессии.

5. Разработан критерий неявной кросс-валидации для выбора уровня селективности формирования подмножества релевантных регрессоров в квадратично-модульной модели Elastic Net.

6. Экспериментально проверены полученные методы беспереборной кросс-валидации.

Список публикаций

[1] Обобщение AIC для выбора значений непрерывных параметров / Е. О. Ежова (Черноусова), В. В. Моттль, О. В. Красоткина // Таврический вестник информатики и математики. —2009. - No 1. - С. 61-71.

[2] Обобщение информационного критерия Акаике для выбора значений непрерывного параметра в моделях данных / В. В. Моттль, О. В. Красоткина, Е. О. Ежова (Черноусова) // Труды 51 научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». — 2008. — Т. 3, —С. 58-60.

[3] Estimation of time-varying linear regression with unknown time-volatility via continuous generalization of the Akaike Information Criterion. / E. Ezhova (Chernousova), V. Mottl, O. Krasotkina // Proceedings of World Academy of Science. Engineering and Technology. - 2009. - March. - No.51. - P. 144-150.

[4] Непрерывная коррекция информационного критерия Акаике для регуляризо-ванного оценивания сверхбольшого числа параметров регрессионных моделей данных с неизвестной дисперсией наблюдения / Е. О. Ежова (Черноусова), О. В. Красоткина, В. В. Моттль // Интеллектуализация обработки информации:

8-я международная конференция. Сборник докладов. - 2010. - М.:МАКС Пресс.-С. 51-54.

[5] Непрерывное обобщение информационного критерия Акаике для оценивания нестационарной регрессионной модели временного ряда с неизвестной степенью изменчивости коэффициентов / В. В. Моттль, О. В. Красоткина, Е. О. Ежова (Черноусова) // Математические методы распознавания образов: 14-я Всероссийская конференция. Сборник докладов. - 2009. - М.:МАКС Пресс. - С. 52-55.

[6] Линейные модели числовых зависимостей на множествах объектов, представленных парными сравнениями / Е. О. Черноусова, О. В. Красоткина, М. Е. Панов, Е. В. Гребенников, В. В. Моттль // Интеллектуализация обработки информации: 9-я международная конференция. Сборник докладов. - 2012. - М.:Торус Пресс. - С. 58-62.

[7] Linear regression via Elastic Net: Non-enumerative leave-one-out verifcation of feature selection / E.Chernousova, N. Razin, O. Krasotkina, V. Mottl, D Windridge //Clusters, orders, trees: methods and applications. P. Pardalos, B. Goldengorin, F. Aleskerov (Eds). Springer. - 2013. - V. 5 . - P. 35-46.

[8] Беспереборная кросс-валидация отбора признаков в линейной регрессионной модели / О. В. Красоткина, В. В. Моттль, Н. А. Разин, Е. О. Черноусова // Известия ТулГУ. Технические науки. - 2013. - Вып. 7. - No. 2. - С. 88-98.

Жирным шрифтом выделены статьи в журналах, рекомендованы ВАК. Личный вклад соискателя в работах с соавторами заключается в следующем:

[1, 2] Предложен и доказан способ выбора структурных параметров моделей, принимающих непрерывные значения, как обобщение классического способа выбора структурного параметра, принимающего целочисленные значения, на основе информационного критерия Акаике (AIC).

[3, 5] Проведение экспериментов на реальных данных для нестационарной регрессионной модели временного ряда с неизвестной степенью изменчивости коэффициентов для проверки обобщенного информационного критерия Акаике. Эксперимент проведен на примере анализа деятельности американского паевого инвестиционного фонда Лаудис Розенберг.

[4] Предложена и доказана непрерывная коррекция информационного критерия Акаике для регуляризованного оценивания сверхбольшого числа параметров регрессионных моделей данных с неизвестной дисперсией наблюдения.

[6] Исследованы особенности неявной кросс-валидации в линейных моделях числовых зависимостей на множествах объектов, представленных парными сравнениями.

[7, 8] Предложена и доказана реализация беспереборного вычисления метода скользящего контроля в задаче оценивания линейной регрессионной зависимости с квадратично-модульной регуляризацией.

Черноусова Елена Олеговна

Беспереборные методы кросе-валидации для оценивания обобщающей способности регрессионных моделей

АВТОРЕФЕРАТ

Подписано в печать 21.11.2013. Формат 60 х 84 1/1в._ Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 375 .

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

министерство образования и науки российской федерации московский физико-технический институт (государственный университет) факультет управления и прикладной математики вычислительный центр им. a.a. дородницына ран кафедра «интеллектуальные системы»

Черноусова Елена Олеговна

Беспереборные методы кросс-валидации для оценивания обобщающей способности регрессионных моделей

05.13.17 — Теоретические основы информатики На правах рукописи

Диссертация на соискание ученой степени кандидата физико-математичесих наук

Научный руководитель:

ведущий научный сотрудник ВЦ РАН д.т.н., профессор В. В. Моттль

Москва 2013 г.

Оглавление

Введение...........................................................................................................................5

1 Проблема численной реализации кросс-валидации при оценивании обобщающей способности регрессионных моделей............................................13

1.1 Проблема оценивания обобщающей способности регрессионных моделей.............................................................................................................13

1.2 Классический информационный критерий Акаике.....................................20

1.3 Методы кросс-валидации...............................................................................22

1.4 Основные задачи исследования.....................................................................23

2 Принцип неявной кросс-валидации.......................................................................25

2.1 Основные предположения о неизвестной регрессионной модели данных..............................................................................................................25

2.2 Мысленный эксперимент наблюдателя Критерий, основанный на идее неявной кросс-валидации...............................................................................27

2.3 Критерий неявной кросс-валидации для общей линейной нормальной модели..............................................................................................................30

2.3.1 Общая линейная нормальная модель....................................................30

2.3.2 Свойства линейной нормальной модели..............................................32

2.3.3 Критерий неявной кросс-валидации.....................................................34

2.3.4 Гауссовская модель данных с известным параметром дисперсии шума, как частный случай линейной нормальной модели.................36

2.3.5 Связь принципа неявной кросс валидации с методом несмещенного оценивания риска (среднего значения квадрата отклонения истинного значения скрытой характеристики от оцененного)..............................................................................................38

2.3.6 Частный случай: Классический информационный критерий Акаике40

2.3.7 Гауссовская модель данных с неизвестным параметром дисперсии шума, как частный случай линейной нормальной модели.................44

3 Частные виды квадратичной модели линейной регрессии и особенности применения метода неявной кросс-валидации для них.......................................52

3.1 Критерий для линейной нормальной модели с требованием гладкости вектора коэффициентов..................................................................................52

3.1.1 Регуляризация оценки регрессионной модели по гладкости вектора коэффициентов........................................................................................52

3.1.2 Критерий неявной кросс-валидации.....................................................53

3.2 Критерий для модели линейной нестационарной регрессии......................53

3.2.1 Модель линейной нестационарной регрессии.....................................53

3.2.2 Критерий неявной кросс-валидации.....................................................55

3.2.3 Эксперименты..........................................................................................56

3.3 Линейная нестационарная регрессия с регуляризацией по критерию релевантности признаков...............................................................................64

3.3.1 Гипер-априорная модель нестационарной регрессии.........................64

3.3.2 Критерий неявной кросс-валидации для коэффициентов нестационарной регрессии.....................................................................68

3.4 Линейная нормальная модель с регуляризацией по методу релевантности признаков...............................................................................69

3.4.1 Гипер-априорная модель данных..........................................................69

3.4.2 Критерий неявной кросс валидации для сложной гребневой регрессии..................................................................................................71

3.5 Неквадратичный выпуклый критерий оценивания коэффициентов в линеной регрессионной модели данных с квадратично-модульной регуляризацией................................................................................................72

3.5.1 Две версии критерия оценивания коэффициентов регрессионной модели с квадратично-модульной регуляризацией: Elasic Net и Naïve Elasic Net........................................................................................73

3.5.2 Нечисловой структурный параметр модели - оптимальное разбиение множества признаков...........................................................74

3.5.3 Принцип неявной кросс-валидации для линейной регрессионной зависимости с квадратично-модульной регуляризацией (полное подавление признаков)...........................................................................76

3.5.4 Беспереборное вычисление скользящего контроля для линейной регрессионной зависимости с квадратично-модульной

регуляризацией (полное подавление признаков).................................77

Заключение....................................................................................................................85

Литература.....................................................................................................................86

Введение

Актуальность темы исследования и степень ее разработанности

Задача восстановления объективно существующей зависимости между наблюдаемыми свойствами объектов реального мира и их некоторой скрытой характеристикой, доступной для наблюдения лишь в пределах конечной обучающей совокупности, является центральной задачи интеллектуального анализа данных [1]. В частности, если скрытая характеристика принимает значения из конечного неупорядоченного множества, то такую задачу принято называть задачей обучения распознаванию образов, а в случае числовой скрытой характеристики говорят о задаче восстановления регрессионной зависимости. В диссертационной работе рассматривается именно последний случай.

Вероятностная интерпретация задачи обучения основана на предположении, что с каждым объектом из некоторого множества объектов реального мира, привлекающего внимание наблюдателя, объективно связаны значения двух его характеристик, одна из которых доступна для непосредственного наблюдения, а другая скрыта. В теории обучения обычно предполагается, что природа, случайным образом выбирая один объект, генерирует, тем самым, случайную пару значений его наблюдаемой и скрытой характеристик, причем соответствующее совместное распределение вероятностей объективно существует, но наблюдателю неизвестно. Наблюдатель всякий раз видит значение лишь наблюдаемой характеристики, в то время как природа требует, чтобы он «угадывал» значение скрытой характеристики объекта, штрафуя неправильное оценивание в соответствии с известной функцией потерь. Наблюдатель вынужден выработать решающее правило, связывающее с каждым наблюденным значением доступной характеристики объекта предполагаемое значение его скрытой характеристики. Как правило, на-

блюдатель формирует свое решающее правило на основе предположения о некотором параметрическом классе зависимостей, так что выбор наблюдателем конкретного решающего правила полностью задается выбором параметра. Естественной объективной оценкой «качества» решающего правила является математическое ожидание потерь, которое в теории обучения принято называть средним риском ошибки. Очевидно, что наблюдатель, выбирая вариант решающего правила, а именно значение параметра, не может вычислить средний риск ошибки, поскольку совместное распределение наблюдаемой и скрытой характеристик случайно появляющегося объекта ему неизвестно.

Единственную объективную информацию о свойствах природы, доступную наблюдателю, несет обучающая совокупность, под которой понимается конечное множество пар значений как наблюдаемой, так и скрытой характеристики объектов, случайно выбранных природой в соответствии с объективно существующим распределением вероятностей. Выбирая решающее правило, наблюдатель может лишь вычислить для всякого его варианта среднее арифметическое значение функции потерь, называемое эмпирическим риском ошибки. При выборе решающего правила общепринятым соображением, основанным на данных, является минимизация эмпирического риска в некотором классе решающих правил {variance minimization в англоязычной литературе).

Однако параметрический класс решающих правил, изначально принятый наблюдателем, может оказаться слишком широким для ограниченного объема обучающей совокупности, и средний риск ошибки результата обучения по критерию минимума эмпирического риска, может оказаться неприемлемо большим. Такое явление принято называть переобучением. Другим общепринятым соображением, направленным на уменьшение опасности переобучения, является использование априорной (регуляризующей) информации об «ожидаемом» решающем правиле восстановления зависимости. Другими словами, наблюдатель пытается сузить параметрический класс зависимостей, накладывая на параметр априорные регуляризирующие требования, в свою очередь контролируемые структурным параметром. Как правило, такие требование наблюдатель может формулировать в

виде системы расширяющихся (с увеличением значения структурного параметра) подмножеств. Тем самым, структурный параметр регуляризации можно рассматривать как степень сложности предполагаемой зависимости. Это дополнительное соображение при построении метода обучения касательно выбора решающего правила называется в англоязычной литературе bias, поскольку управляет «смещением» выбираемого решающего правила от выбранного на основе минимизации эмпирического риска.

В современной теории обучения эти два соображения объединяются в единый критерий обучения, получая тем самым регуляризованный критерий минимизации эмпирического риска. Естественно, что результат обучения - решающее правило, получаемое в качестве решения задачи условной минимизации, зависит от структурного параметра, отвечающего за сложность, предполагаемой априори наблюдателем, зависимости между ненаблюдаемой и наблюдаемой компонентами объекта.

Очевидным показателем «качества» выбора структурных параметров и, следовательно, получаемого решающего правила, является средний риск ошибки оценивания скрытой характеристики нового случайного объекта, не входящего в обучающую совокупность. Однако, вычисление среднего риска принципиально невозможно, поскольку наблюдателю неизвестно совместное распределение вероятностей на множестве пар значений наблюдаемой и скрытой характеристик объектов в генеральной совокупности. В качестве общепринятого компромисса на практике обычно заменяют критерий минимума среднего риска ошибки при выборе структурного параметра на его суррогат, вычисленный путем кросс-валидации единственной обучающей совокупности, доступной наблюдателю. Метод кросс-валидации заключается в том, что обучающая совокупность многократно разбивается на две части, по одной из которых определяется решающее правило для каждого пробного значения структурного параметра, а по другой оценивается среднее значение ошибки.

Проблемная ситуация заключается в том, что методы кросс-валидации требуют многократного повторения обучения при разных разбиениях обучающей со-

вокупности, что определяет их чрезвычайно высокую вычислительную сложность. Наиболее популярным видом кросс-валидации является метод скользящего контроля, заключающийся в выделении поочередно одного объекта в качестве контрольного и обучения по оставшимся объектам (leave-one-out cross-validation в англоязычной терминологии). При этом число повторений обучения равно числу объектов в обучающей совокупности.

Для разрешения этой проблемной ситуации в диссертации предлагаются два метода, имеющие разные области применимости.

Первый метод (по порядку изложения, а не по предпочтительности) основан на некотором предположении наблюдателя о возможном параметрическом классе совместных распределений наблюдаемой и скрытой характеристик случайно появляющегося объекта, и назван в диссертации методом неявной кросс-валидации. Метод основан на мысленном эксперименте, заключающемся в получении трех независимых выборок, по первой из которых находится решающее правило как по обучающей совокупности, по второй оцениваются некоторые параметры предполагаемого совместного распределения двух характеристик случайного объекта, а на третьей измеряется эмпирический риск ошибки восстановления скрытой характеристики объекта. В качестве критерия выбора значений структурных параметров предлагается использовать математическое ожидание эмпирического риска ошибки. Выделен класс совместных распределений наблюдаемой и скрытой характеристик случайного объекта, для которых несмещенная оценка этого математического ожидания выражается через элементарные функции. Показано, что частным случаем такого критерия выбора структурных параметров при некоторых специальных предположениях о модели данных является известный информационный критерий Акаике.

Второй метод использует вычислительную простоту использования критерия скользящего контроля в случае, когда штраф за неправильное оценивание ненаблюдаемой характеристики объекта (потери наблюдателя) является квадратичным, а решающее правило является линейной функцией от вектора из ненаблюдаемых характеристик объектов, представленных в обучающей совокупности.

При выполнении перечисленных выше ограничений ошибка предсказания (значение функции потерь) на выделенном в качестве контроля объекте с использованием оценки решающего правила, построенной по сокращенной обучающей совокупности (без контрольного объекта), выражается через значение функции потерь для этого объекта, но с использованием оценки решающего правила, полученной по полной обучающей совокупности. Таким образом, в таком случае результат применения метода скользящего контроля для оценивания обобщающей способности выбранной модели зависимости явно выражается через результат обучения по исходной обучающей выборки, а значит и не требует выполнения полного перебора возможных контрольных объектов и обучения на всех соответствующих сокращенных выборках. Однако иногда эти требования являются ограничительными, а значит, применение процедуры скользящего контроля для оценивания качества выбранной регрессионной зависимости не является больше беспереборной и требует честного выполнения всех шагов, равных числу объектов в обучении. В частности, в работе рассматривается задача оценивания линейной регрессионной модели с квадратично-модульной регуляризацией и квадратичной функцией потерь. Решающее правило наблюдателя теперь характеризуется двумя параметрами, отвечающими за квадратичную и модульную регуляризацию. Для оценивания адекватности выбранной пары структурных параметров (обобщающей способности выбранной регрессионной модели) использование метода скользящего контроля приводит к его честному переборному варианту, что естественно сопряжено с большими вычислительными сложностями.

Предложенный метод основан на характеристическом свойстве решающих правил (то есть вектора коэффициентов регрессии), полученных согласно критерию с квадратично-модульной регуляризацией - разбиению множества признаков на три непересекающихся подмножества, полученных с учетом знака и обнуления коэффициента при соответствующем признаке в модели регрессии. В качестве вторичного нечислового структурного параметра модели предлагается использовать именно такое разбиение, полученное согласно решению задачи обучения. Важно, что при фиксации введенного структурного параметра критерий обучения

(в исходном варианте не являющийся квадратичным, а только выпуклым) является квадратичным по активным (ненулевым) коэффициентам регрессии, а значит процедура скользящего контроля для оценивания обобщающей способности регрессионной модели, характеризуемой нечисловым структурным параметром (разбиением множества признаков) становится беспереборной.

Цели и задачи диссертации

1. Разработка критерия выбора структурного параметра, характеризующего сложность регрессионной модели, на основе принципа неявной кросс-валидации. Показано, что частным случаем такого критерия выбора структурных параметров при некоторых специальных предположениях о модели данных является известный информационный критерий Акаике.

2. Разработка беспереборного метода скользящего контроля для задачи оценивания линейной регрессионной модели с квадратично-модульной регуляризацией.

3. Экспериментальная проверка полученных методов беспереборной кросс-валидации.

Научная новизна

В работе предложены два метода оценивания обобщающей способности регрессионных моделей, отличающихся областью применимости. Оба метода являются альтернативами классическим способам оцениван�