[ «ПОРОЖДЕНИЕ И ВЫБОР МОДЕЛЕЙ В ЗАДАЧАХ РЕГРЕССИИ И КЛАССИФИКАЦИИ ...»
Федеральное государственное бюджетное учреждение наук
и
Вычислительный центр им. А. А. Дородницына Российской академии наук
На правах рукописи
СТРИЖОВ ВАДИМ ВИКТОРОВИЧ
ПОРОЖДЕНИЕ И ВЫБОР МОДЕЛЕЙ
В ЗАДАЧАХ РЕГРЕССИИ И КЛАССИФИКАЦИИ
05.13.17 теоретические основы информатики Диссертация на соискание учёной степени доктора физико-математических наук Москва 2014 Оглавление Введение........................................... 7 1. Постановка задачи выбора моделей......................... 1.1. Функция регрессии и регрессионная модель................ 1.2. Гипотеза порождения данных........................ 1.2.1. Дополнительные требования к данным.............. 1.2.2. Экспоненциальное семейство.................... 1.2.3. Нормальное распределение зависимой переменной....... 1.2.4. Биномиальное распределение зависимой переменной...... 1.2.5. Функция ошибки и гипотеза порождения данных........ 1.3. Задачи регрессионного анализа....................... 1.3.1. Оценка параметров модели..................... 1.3.2. Выбор оптимальной модели.................... 1.3.3. Оценка ковариационных матриц................. 1.3.4. Совместный выбор объектов и признаков............ 1.3.5. Выбор наиболее правдоподобной модели............. 1.3.6. Выбор смеси моделей........................ 1.3.7. Нахождение инвариантов моделей................ 1.3.8. Проверка гипотезы порождения данных............. 1.4. Оценка параметров моделей......................... 1.4.1. Линейные модели.......................... 1.4.2. Существенно нелинейные модели................. 1.4.3. Оптимизация целевой функции общего вида.......... 1.4.4. Оценка параметров функции ошибки общего вида методом сопряженных градиентов....................... 1.4.5. Обобщенно-линейные модели................... 1.4.6. Оптимизация многокритериальной функции ошибок...... 1.5. Ограничения, накладываемые на множество моделей........... 1.5.1. Анализ регрессионных остатков.................. 1.5.2. Адекватность регрессионной модели............... 1.5.3. Устойчивость моделей и мультиколлинеарность......... 2. Порождение моделей................................. 2.1. Допустимые суперпозиции.......................... 2.1.1. Порождающие функции и их суперпозиции........... 2.1.2. Условия допустимости суперпозиций............... 2.1.3. Порождение произвольных суперпозиций............ 2.1.4. Суперпозиции с дополнительными параметрами........ 2.1.5. Порождение обобщенно-линейных моделей........... 2.1.6. Структурная сложность суперпозиций.............. 2.1.7. Число суперпозиций ограниченной сложности.......... 2.2. Порождение суперпозиций.......................... 2.2.1. Стохастическое порождение суперпозиций............ 2.2.2. Стохастическая процедура порождения модели......... 2.2.3. Порождающие функции и классы моделей............ 2.2.4. Порождаемые модели........................ 2.3. Упрощение суперпозиций........................... 2.3.1. Порождение допустимых суперпозиций............. 2.3.2. Изоморфные суперпозиции..................... 2.3.3. Преобразование суперпозиций по правилам........... 2.4. Структурное обучение при порождении суперпозиций.......... 2.4.1. Постановка задачи структурного обучения........... 2.4.2. Способ задания структуры регрессионной модели....... 2.4.3. Оценка вероятности переходов в дереве суперпозиции..... 2.4.4. Решение задачи структурного обучения............. 2.4.5. Процедура прогнозирования структуры модели......... 3. Сравнение элементов моделей............................ 3.1. Методы эмпирического выбора признаков................. 3.1.1. Регуляризующие методы...................... 3.1.2. Корреляционные методы...................... 3.1.3. Прореживающие методы...................... 3.1.4. Шаговые методы.......................... 3.2. Сходимость при последовательном добавлении признаков........ 3.2.1. Расстояние между последовательно порождаемыми моделями 3.2.2. Расстояние между функциями регрессии............ 3.2.3. Критерии сходимости при выборе моделей............ 4.1.6. Использование байесовского вывода при выборе моделей... 4.2. Методы аналитической оценки гиперпараметров............. 4.2.1. Процедура оценивания параметров и гиперпараметров.... 4.2.2. Аналитическая оценка ковариационных матриц общего вида. 4.2.3. Одинаковая дисперсия элементов вектора параметров..... 4.2.4. Независимо-распределенные элементы вектора параметров.. 4.2.7. Аппроксимация Лапласа для оценки нормирующего коэффициента................................. 4.2.8. Метод Монте-Карло сэмплирования функции ошибки..... 4.2.9. Оценка структурных параметров методом скользящего контроля 4.2.10. Анализ метода оценки ковариационных матриц......... 4.3. Оценка гиперпараметров для случая линейных моделей......... 4.3.1. Вычисление производной функции правдоподобия модели.. 4.3.2. Отбор шумовых и коррелирующих признаков.......... 4.4.2. Алгоритм выбора многоуровневых моделей........... 4.5.3. Иллюстрация: прогнозирование периодических временных рядов 5. Выбор моделей для данных в разнородных шкалах и экспертных оценок... 5.1. Регрессионная модель согласования экспертных оценок......... 5.1.1. Базовая модель построения интегральных индикаторов.... 5.1.2. Критерий наибольшей информативности............. 5.1.3. Метрический метод построения модели............. 5.2. Криволинейные линейные методы согласования экспертных оценок.. 5.2.2. Линейное согласование экспертных оценок........... 5.2.3. Квадратичное согласование экспертных оценок......... 5.2.4. Монотонное согласование экспертных оценок.......... 5.2.5. Криволинейная регрессия для согласования экспертных оценок 5.3. Согласование экспертных оценок в ранговых шкалах........... 5.3.2. Отображение и пересечение многогранных конусов....... 5.3.3. Уточнение оценок в случае непересекающихся конусов.... 5.4. Устойчивость и регуляризация при выборе моделей экспертных оценок 5.4.1. Получение непротиворечивых экспертных оценок....... 5.4.2. Интегральные индикаторы, устойчивые к возмущению матрицы описаний............................. 5.4.3. Регуляризация при согласовании экспертных оценок...... 5.4.4. Устойчивые интегральные индикаторы с выбором опорного множества описаний объектов..................... 5.4.5. Построение коллаборативного интегрального индикатора... 5.5. Порядковая классификация объектов по частично упорядоченным множествам..................................... 5.5.2. Парето-классификация для случая двух классов........ 5.5.3. Построение набора Парето-оптимальных фронтов....... 6.1. Анализ постановок прикладных задач с использованием порождающих 6.1.1. Прогнозирование квазипериодических временных рядов.... 6.1.4. Порождение нелинейных моделей для оценки волатильности 6.1.5. Использование параметров модели в качестве независимых переменных............................... 6.2. Разметка временных рядов в задачах прогнозирования......... 6.2.1. Локальное прогнозирование и аппроксимация временных рядов 6.2.5. Прогнозирование размеченных апериодических временных рядов 6.3. Кластеризация с использованием наборов парных расстояний в ранговых шкалах................................... 6.3.2. Описание алгоритма кластеризации сетью.......... 6.4. Прямая и обратная задача авторегрессионного прогнозирования.... 6.4.4. Нахождение оптимального управляющего воздействия.... Диссертационная работа посвящена проблемам выбора моделей в задачах регрессионного анализа и классификации. Предлагается подход, согласно которому выбор производится из индуктивно-порождаемого множества моделей. Анализируется распределение параметров моделей. На основании этого анализа выбирается модель оптимальной сложности.
Ключевые слова: машинное обучение, интеллектуальный анализ данных, регрессионный анализ, классификация, выбор моделей, порождение моделей, байесовский подход.
Актуальность темы. Модель, описывающая исследуемое явление, может быть получена двумя путями: во-первых, методами математического моделирования, во-вторых, методами анализа данных и информационного моделирования. Первый тип моделей интерпретируем экспертами в контексте моделируемого явления [19]. Второй тип моделей не всегда интерпретируем, но более точно приближает данные [148]. Совмещение достоинств обоих подходов, результатом которого является получение интерпретируемых и достаточно точных моделей, является актуальной задачей теоретической информатики.
Центральным объектом исследования является проблема построения адекватных моделей регрессии и классификации при решении задач прогнозирования. Проблема заключается в отыскании моделей оптимальной сложности, которые описывают измеряемые данные с заданной точностью. Дополнительным ограничением является интерпретируемость моделей экспертами той предметной области, для решения задач которой создается модель.
Цель исследования заключается в создании и обосновании методов выбора моделей из индуктивно порождаемого множества, а также в исследовании свойств алгоритмов выбора моделей. Задача выбора моделей из счетного порождаемого множества поставлена впервые.
При постановке задачи использовался обширный материал о способах выбора моделей и выбора признаков из конечного множества, наработанный ранее в области машинного обучения.
Эта задача является одной из центральных проблем машинного обучения и интеллектуального анализа данных.
Основной задачей исследования является разработка методов последовательного порождения моделей и оценки ковариационных матриц параметров моделей с целью управления процедурой выбора моделей. Основной сложностью такой задачи является необходимость выбора из значительного числа регрессионных моделей, либо необходимость оценки параметров структурно сложной, так называемой универсальной модели.
Взаимосвязь задачи порождения и задачи выбора регрессионных моделей была освещена в начале 1980-х годов А. Г. Ивахненко. Согласно предложенному им методу группового учета аргументов [59, 17, 14], модель оптимальной структуры может быть найдена путем последовательного порождения линейных моделей, в которых компоненты являются мономами полинома Колмогорова-Габора от набора независимых переменных. Критерий оптимальности структуры модели задается с помощью скользящего контроля.
В отличие от этого метода, метод символьной регрессии [402, 258, 269, 296] рассматривает порождение произвольных нелинейных суперпозиций базовых функций. В последние годы тема анализа сложности моделей, получаемых с помощью этого метода, стала распространенным предметом исследований [208, 390].
Первоначально принципы индуктивного порождения моделей были предложены в методе группового учета аргументов. Структура суперпозиций задавалась при этом внешними критериями качества модели. Впоследствии эти критерии были обоснованы в рамках гипотезы порождения данных с помощью связанного байесовского вывода. При последовательном порождении моделей необходимо оценивать информативность элементов суперпозиции. В рамках метода байесовской регрессии [147, 131, 151] для этого предложено использовать функцию плотности распределения параметров модели. Эта функция является параметрической и ее параметры были названы гиперпараметрами [386, 148, 150, 149]. Было предложено использовать гиперпараметры моделей для оценки информативности элементов суперпозиции, что сделало анализ гиперпараметров одним из способов выбора моделей.
Для модификации суперпозиций нелинейных моделей был предложен метод оптимального прореживания [279, 231] Согласно этому методу, элемент суперпозиции можно отсечь как неинформативный, если значение выпуклости функции ошибки от параметров модели не превосходит относительный заданный порог.
Задача выбора модели является одной из самых актуальных в регрессионном анализе.
В современной зарубежной литературе для ее решения используется принцип минимальной длины описания. Он предлагает использовать для описания данных наиболее простую и одновременно наиболее точную модель [217, 222, 218, 219, 267].
Задача сравнения моделей детально разработана [293, 292, 294, 162, 291]. Как альтернатива информационным критериям [158, 159, 116, 117, 186, 391] был предложен метод двухуровневого байесовского вывода. На первом уровне вывода настраиваются параметры моделей.
На втором уровне настраиваются их гиперпараметры. Согласно этому методу, вероятность выбора более сложной модели ниже вероятности выбора простой модели при сравнимом значении функции ошибки на регрессионных остатках. Принципы байесовского подхода для выбора линейных моделей регрессии и классификации предложены авторами [164, 128, 132, 133].
В то же время, в упомянутых публикациях и подходах остается открытым ряд важных проблем, решение которых определяет актуальность представляемой диссертации. Поэтому представляется целесообразным создать и развить теорию порождения и выбора регрессионных моделей. Она заключается в следующем. Множество моделей заданного класса индуктивно порождается набором параметрических базовых функций, заданных экспертами.
Каждая модель является допустимой суперпозицией таких функций.
Интерпретируемость моделей обеспечена тем, что каждая из порождаемых моделей является суперпозицией базовых функций, заданных экспертами. Класс моделей задается правилами порождения суперпозиций. Точность моделей обеспечивается тем, что рассматривается достаточно большой набор моделей-претендентов, из которого выбирается оптимальная модель. Критерий оптимальности включает в себя понятия сложности и точности модели. При построении критерия учитывается гипотеза порождения данных предположение о распределении регрессионных остатков.
Одновременно с оценкой параметров вычисляются и гиперпараметры (параметры распределения параметров) модели. На основе гиперпараметров оценивается информативность элементов суперпозиции и оптимизируется её структура. Оптимальные модели выбираются согласно критерию, заданному гипотезой порождения данных.
Таким образом, требуется предложить новые подходы к решению поставленной задачи.
Множество моделей индуктивно порождается из набора базовых функций, заданных экспертами. Каждая модель является допустимой суперпозицией базовых функций. Одновременно с оценкой параметров моделей выполняется также и оценка гиперпараметров функции распределения параметров моделей. На основе этих параметров оценивается информативность элементов суперпозиции и принимается решение об оптимизации ее структуры. Оптимальные модели выбирается согласно критерию, заданному гипотезой порождения данных.
В связи с вышеизложенным, решение крупной задачи теории распознавания, в рамках которой будут предложены новые способы порождения и выбора моделей регрессии и классификации, является актуальной темой.
шения задачи последовательного выбора регрессионных моделей. Цель работы находится в рамках направления создание и исследование информационных моделей, моделей данных и знаний, методов машинного обучения и обнаружения новых знаний.
В частности, цель работы включает в себя:
1) создание и обоснование методов выбора индуктивно порождаемых моделей для решения задач регрессии и классификации, 2) исследование ограничений, накладываемых на структуру суперпозиции различными алгоритмами выбора моделей, 3) исследование структуры последовательно порождаемых суперпозиций и свойств параметров моделей.
Эти цели соответствуют направлению области исследования специальности 05.13.17 разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных а также создание техники, которая предоставляет, во-первых, совокупность методов разработки математических моделей и, во-вторых, возможность интерпретации моделей в той прикладной области знаний, в рамках которой эти модели создаются (пп. 5, 12).
На защиту выносятся следующие результаты.
1. Формализованы и исследованы в рамках предложенного языка методы выбора моделей для основных классов моделей: линейных, обобщенно-линейных и существенно нелинейных. Предложены способы конструктивного порождения указанных классов моделей. При выборе моделей решается многокритериальная оптимизационная задача, которая определена классом порожденных моделей. В работе исследуются только те методы выбора моделей, которые при решении задачи позволяют анализировать также и информативность отдельных элементов суперпозиций.
2. Исследованы условия, накладываемые на множество суперпозиций, при которых заданные алгоритмы оценки информативности элементов суперпозиций являются корректными. Каждому алгоритму, оценивающему гиперпараметры, ставится в соответствие процесс выбора элементов суперпозиции путем полного перебора всевозможных структур суперпозиции. Корректным называется такой алгоритм, который доставляет ту же ранговую оценку информативности элементов суперпозиции, что и алгоритм полного перебора.
3. Предложен способ оценки информативности элементов суперпозиций путем анализа пространства параметров моделей. Каждому элементу суперпозиции ставится в соответствие вектор параметров, который рассматривается как многомерная случайная величина. При заданной гипотезе порождения данных выполняется приближение эмпирического распределения параметров модельной параметрической функцией распределения. Оцениваются гиперпараметры параметры распределения параметров моделей. Данная оценка является информативностью элемента суперпозиции.
4. Получены критерии сходимости последовательно порождаемых суперпозиций. Так как задача выбора моделей является многокритериальной, то при их индуктивном порождении выбирается такая подпоследовательность, значения критериев качества которой сходится к заданному Парето-оптимальному фронту.
5. Разработана универсальная методика порождения и выбора моделей. Так как множество порождаемых моделей счётно, то предлагается методика последовательного их порождения. Она заключается в том, что на каждом шаге анализируется информативность элементов порождаемых моделей, после чего модель модифицируется таким образом, чтобы доставить наибольшее увеличение значению критерия выбора модели на данном шаге.
6. Развит метод Белсли для ковариационной матрицы параметров нелинейных моделей.
Предложен критерий отыскания мультиколлинеарности. Поставлена и решена оптимизационная задача последовательного исключения элементов модели. Полученное решение позволяет получать устойчивые модели.
Научная новизна. Выносимые на защиту результаты (1–6) являются новыми; также новыми являются следующие результаты, ранее опубликованные автором в рецензируемых журналах: 1) метод индуктивного порождения регрессионных моделей как суперпозиций гладких функций из заданного множества; 2) алгоритм выбора наиболее информативных элементов суперпозиции с помощью вектора гиперпараметров; 3) метод выбора опорного множества объектов как альтернатива процедурам регуляризации при построении интегральных индикаторов; 4) алгоритм поиска опорного множества объектов при построении устойчивых интегральных индикаторов; 5) алгоритм согласования экспертных оценок в ранговых шкалах: используется линейная комбинация конусов экспертных оценок в пространстве интегральных индикаторов и в пространстве весов показателей.
Методика исследования: методы алгебраического подхода к решению задач распознавания; методы вычислительной линейной алгебры, многомерной статистики и теории машинного обучения; методы теории категорий. В рамках машинного обучения используются такие методы как связанный байесовский вывод, метод минимальной длины описания, устойчивое оценивание параметров, аппроксимация Лапласа в пространстве параметров. Все эти методы являются новыми и активно обсуждаются в научных публикациях в течение последних лет.
Достоверность и обоснованность результатов подтверждена строгостью и корректностью математических высказывание и доказательств. Была выполнена экспериментальная проверка полученных результатов на задачах с модельными и реальными данными. Результаты исследований неоднократно обсуждались на российских и международных научных конференциях. Результаты исследования опубликованы в рецензируемых научных изданиях из числа рекомендованных ВАК РФ.
Теоретическая значимость. Впервые связаны методы порождения и методы выбора моделей. При этом снята проблема оценки параметров и их ковариационных матриц моделей большой структурной сложности, так как для этой оценки параметров последующих моделей используются результаты анализа ранее порожденных моделей. Такой подход позволяет получать устойчивые оценки параметров в условиях большого числа мультикоррелирующих и шумовых признаков. Для выбора конкурирующих моделей используется байесовский подход, что позволяет получить модель оптимальной статистической сложности.
Практическая значимость.
Работа носит преимущественно теоретический характер.
Для иллюстрации возможных практических применений в последней главе работы приведены математические постановки прикладных задач, при решении которых были использованы результаты работы. Ниже дан перечень моделей, созданных в рамках предложенной теории (в скобках указана организация, предложившая задачу): Элементы работы были использованы при подготовке патентов, зарегистрированных в European Patent Oce, Patent No. 06808733.7 1240 PCT/GB2006060369, Title: Particle Detector и в United States, Patent Application No. 12/092,623 SP/RJG/JH/642US00, Title: Dactyl Detector. Получено свидетельство о государственной регистрации программ для ЭВМ Программная система для построения интегральных индикаторов качества VVS_CCRAS_IIC_1, свидетельство № 2010613192.
Апробация работы. Основные результаты работы и отдельные её части докладывались на конференциях:
– международная конференция Conference of the International Federation of Operational Research Societies, Барселона 2014 г. [373];
– международная конференция European Conference on Operational Research, Бонн 2009 г. [367]; Лиссабон 2010 г. [375]; Вильнюс 2012 г. [377]; Рим 2013 г. [372];
– международная конференция Operational Research: Mastering Complexity, Бонн 2010 г.[374], Цюрих 2011 г. [376];
– всероссийская конференция Математические методы распознавания образов, Москва 2003, 2005, 2007, 2009 гг. [20, 77, 25, 27];
– международная конференция Интеллектуализация обработки информации, Симферополь 2006, 2008 гг. [80, 365];
– международная конференция Математика. Компьютер. Образование, Дубна 2005, 2006, 2008, 2009 гг. [371, 87, 82, 21];
– международная конференция SIAM Conference on Computational Science and Engineering, Майами 2009 г. [366];
– международный форум Quo Vadis Energy in Times Of Climate Change, Загреб 2009 г. [368];
– международная конференция Citizens and Governance for Sustainable Development, Вильнюс 2003, 2006 гг. [369, 364].
Результаты работ обсуждались на семинарах в институтах:
– Centre de Recherche de Cordeli`res, Univercit Pierre et Marie Curie, Париж (рук. семинара Dr. Doroty Bray, president of ImmunoClin Laboratory);
– Dpartement Signaux et Syst`mes Electroniques, SUPELEC, Жиф-Сюр-Иветт (рук. семинара Prof. Gilles Fleury, Chef de Departement);
– Centre de recherche en imagerie mdicale, Лион Magnin, Research Director of the Сenter);
– SwissQuant AG, Цюрих 2009 г. (рук. семинара Dr. Florian Herzog, Director of the Laboratory).
Полученные результаты обсуждались в течение 2005–2011 годов с рядом европейских исследователей. Теория порождения и выбора моделей обсуждалась с Prof. Gilles Fleury (Chef de Departement Signaux et Systemes Electroniques, SUPELEC), в рамках ежегодного заседания форума научного фонда Digiteo в Жиф-Сюр-Иветт, Франция. Приложения теории в области порождения моделей в медицине обсуждались во время лекции, прочитанной автором данного проекта в Centre de recherche en imagerie medicale, в Лионе, Франция, по приглашению Prof. Isabelle Magnin (Research Director of the Сenter). Приложения теории в области финансового анализа обсуждались во время лекции, прочитанной автором в лаборатории swissQuant в Цюрихе, Швейцария, по приглашению Dr. Florian Herzog (Director of the Laboratory).
По тематике работы были прочитаны циклы лекций в Middle East Technical University, Турция 2009 г. (по приглашению Prof. Wilhelm-Gerhard Weber, Research Director of the Institute of Applied Mathematics) и в University Siegen, Германия 2011 г. (по приглашению Prof. Peter Letmathe, Chair of Business Administration).
Материалы работы легли в основу обязательного курса Прикладной регрессионный анализ для студентов шестого курса Кафедры интеллектуальных систем ФУПМ МФТИ (курс читается с 2006 г.) и практикума Математические методы прогнозирования (выполняется на кафедре с 2009 г.).
Работа поддержана грантами Российского фонда фундаментальных исследований и Министерства образования и науки РФ:
1) 04-01-00401-а Распознавание и прогнозирование экстремальных ситуаций в сложных системах по многомерным временным рядам наблюдений, 2) 05-01-08030-офи Создание комплекса программных средств для имитационного моделирования сложных социально-технических систем на основе алгебраической технологии синтеза корректных алгоритмов, 3) 07-01-00064-а Точечные поля, инвариантные относительно сдвига, и их использование для решения прикладных задач, 4) 07-01-12076-офи Технология рубрикации документов в сети Интернет на основе совместного анализа содержимого и данных о посещаемости, 5) 07-07-00181-а Развитие теории поиска регрессионных моделей в неявно заданном множестве, 6) 08-01-12022-офи Создание программной системы построения интегральных индикаторов качества для поддержки принятия управленческих решений, 7) 10-07-00422-а Развитие теории индуктивного порождения и выбора моделей, 8) 12-07-13118-офи Методы порождения прогностических моделей оперативной (онлайновой) диагностики подвижного состава, 9) 07.524.11.4002, Министерство образования и науки РФ в рамках Государственного контракта Система агрегирования и публикации научных документов ВебСервис: построение тематических моделей коллекции документов, 10) 07.514.11.4001, контракт 2011-04-1.4-20-01-005 Высокоуровневые модели параллельных вычислений и их библиотеки поддержки времени выполнения: прогнозирвание вторичной струкуры белка.
Личный вклад. Все результаты, выносимые на защиту, получены автором лично и не имеют пересечений с результатами его кандидатской диссертации.
Полный текст диссертации находится на персональной странице автора по адресу http://www.ccas.ru/strijov/papers/Strijov2014MdlSel.pdf Публикации. Результаты диссертации описаны в 31-й статье в журналах, рекомендованных ВАК, в частности работах [273, 316, 40, 39, 11, 44, 379, 35, 37, 9, 10, 36, 38, 93, 109, 12, 8, 6, 31, 30, 7, 33, 378, 106, 92, 45, 381, 28, 84, 23, 81].
Описания отдельных результатов работы включались в научные отчёты по проектам РФФИ 04-01-00103-а, 04-01-00401-а, 04-01-00401-а, 05-01-08030-офи, 07-01-00064-а, 07-01-12076- офи, 07-07-00181-а, 07-07-00372-а, 08-01-12022-офи, 10-07-00422-а, 10-07-00673-а, 12-07-13118- офи, 13-07-00709.
Структура и объём работы. Диссертация состоит из оглавления, введения, перечня основных обозначений, шести глав, разбитых на параграфы, и списка литературы из 394-х наименований. Основной текст занимает 343 страницы.
Благодарности. Автор признателен чл.-корр. РАН Константину Владимировичу Рудакову за поддержку и внимание к работе, д.ф.-м.н. Константину Вячеславовичу Воронцову за обсуждение содержания работы и критические замечания, а также аспирантам Вычислительного центра РАН и студентам кафедры Интеллектуальные системы Факультета управления и прикладной математики Московского физико-технического института Михаилу Кузнецову, Анастасии Мотренко, Роману Сологубу, Алексею Зайцеву, Александру Адуенко, Анне Варфоломеевой, Арсентию Кузьмину, Марии Стениной, Георгию Рудому, Александре Токмаковой и Александру Катруце за сотрудничество и участие в многочисленных вычислительных экспериментах, проводимых при исследовании свойств предлагаемых методов.
Важным свойством регрессионных моделей является возможность интерпретации её структуры и её параметров в контексте решаемой прикладной задачи. Различают термины математическая модель и регрессионная модель. Математическая модель [19, 62] предполагает участие специалиста-аналитика в конструировании функции, которая описывает некоторую известную закономерность [142, 195, 74]. Математическая модель является интерпретируемой объясняемой в рамках исследуемой закономерности. При построении математической модели сначала создается параметрическое семейство функций, затем с помощью измеряемых данных выполняется идентификацией модели, состоящая в нахождении её параметров [287]. Основное отличие математического моделирования от регрессионного анализа состоит в том, что в первом случае функциональная известна связь зависимой переменной и свободных переменных. Специфика математического моделирования состоит в том, что измеряемые данные используются для верификации, но не для построения модели: модель строится исходя из экспертных предположений о характере и законах моделируемого явления. При этом затруднительно получить модель сложного явления, в котором взаимосвязано большое число различных факторов.
Регрессионные модели образуют широкий класс функций, которые описывают некоторую закономерность [182]. При этом для построения модели в основном используются измеряемые данные, а не знание свойств исследуемой закономерности. Такая модель часто неинтерпретируема с точки зрения специалистов данной прикладной задачи, но более точна. Это объясняется либо большим числом моделей-претендентов, которые используются для построения оптимальной модели, либо большей сложностью модели [206, 221, 339, 318].
И на регрессионную, и на математическую модель, накладывается требование непрерывности отображения. Требование непрерывности обусловлено классом решаемых задач: чаще всего это описание физических, химических и других явлений, где требование непрерывности выставляется естественным образом [94, 393, 58, 324, 322, 261]. Примеры регрессионных моделей: линейные функции, алгебраические полиномы, ряды Чебышёва, нейронные сети без обратной связи, функции радиального базиса. Модель также может быть представлена в виде суперпозиции функций свободных переменных из некоторого набора. На функцию регрессии также могут накладываться ограничения монотонности, гладкости, измеримости и некоторые другие [97, 63, 58, 94].
Термин регрессия введен Фрэнсисом Гальтоном в конце XIX века [157]. Гальтон обнаружил, что дети родителей с высоким или низким ростом как правило не наследуют выдающийся рост и назвал эту закономерность регрессия к посредственности [204]. Сначала этот термин использовался исключительно в биологическом смысле. После работ Карла Пирсона его стали использовать и в статистике [334]. [125].
Регрессионное моделирование и математическое связаны подходом, который называется суррогатным моделированием [215, 257]. Согласно этому подходу, сложная в создании или идентификации математическая модель приближается функцией регрессии. Дана функция u дискретного или непрерывного аргумента. Требуется найти функцию f из некоторого параметрического семейства, например, среди алгебраических полиномов заданной степени.
Параметры функции f должны доставлять минимум некоторому функционалу, например, (f, u) =ba a При прогнозе с использованием регрессионных моделей используется подход, называемый интер- или экстраполяцией. Интерполяция функций частный случай задачи приближения, когда требуется, чтобы в определенных точках, называемых узлами интерполяции, значения функции u и приближающей её функции f совпадали. В более общем случае накладываются ограничения на значения некоторых производных f. То есть, дана функция u дискретного аргумента. Требуется отыскать такую функцию f, график которой проходит через все точки u. При этом понятие расстояния обычно не используется, однако часто вводится понятие гладкости искомой функции.
В работе описаны аналитические и стохастические алгоритмы оптимизации структурных параметров прогностических регрессионных моделей. Исследуется оптимизация параметров линейных, обобщенно-линейных и нелинейных моделей. Приняты статистические гипотезы о распределении зависимой переменной и параметров модели. На основании этих предположений принята оптимизируемая функция ошибки. Аналитические алгоритмы основаны на получении оценок производных функции ошибок относительно параметров модели. Статистические алгоритмы основаны на сэмплироваинии параметров модели и на процедуре скользящего контроля элементов регрессионной выборки. Алгоритмы протестированы на наборе синтетических и реальных задач. Представлены результаты сравнения алгоритмов.
Выполнен анализ ошибок.
При моделировании измеряемых данных одной из важных проблем является оценка точности модели, аппроксимирующей эти данные. Для оценки точности аппроксимации вводится функция ошибки, оптимизируемая в данной работе. Предполагая, что данные измеряются с некоторой погрешностью, будем рассматривать моделирование данных как задачу восстановления регрессии [182, 271, 347, 151, 355, 385].
Эта задача состоит в нахождении функции регрессии и оценке параметров регрессионной модели [306, 159, 290]. Параметры модели назначаются таким образом, что модель наилучшим образом приближает данные, минимизируя функцию ошибки. Измеряемые данные представляют собой пары значений зависимой и независимой переменной.
Для оценки качества решения этой задачи вводится функция ошибки, исходя из значения которой делается вывод о том, насколько хорошо модель приближает данные, а также насколько адекватна гипотеза порождения данных [148, 233, 281]. Функция ошибки играет определяющую роль в выборе параметров регрессионной модели и зависит также от структурных параметров, которые определяются гипотезой порождения данных или априорными знаниями о виде модели. В данной работе функция ошибки назначается путем байесовского вывода [148, 189, 323, 331].
Структурными параметрами являются регуляризирующие параметры, включаемые в функционал качества для штрафа на вектор параметров модели [129, 163, 211]. Оценка структурных параметров [165, 288] является центральной задачей в данной работе. Для оценки используется метод максимизации правдоподобия модели [328, 123, 118].
Одним из методов максимизации правдоподобия модели является метод аппроксимации Лапласа [311, 255, 294], в основе которого лежат гипотезы нормального распределения зависимой переменной и вектора параметров модели. В зависимости от вида ковариационных матриц нормальных распределений зависимой переменной и вектора параметров, вводится ряд упрощений для максимизации правдоподобия модели. Рассматриваются ковариационные матрицы диагонального типа, скалярного типа и общего вида.
Альтернативным методом оценки правдоподобия модели является метод Монте-Карло [119, 143]. Согласно этому методу, производится процедура сэмплирования параметров модели при фиксированных структурных параметрах, и строится аппроксимирующая интеграл сумма значений правдоподобия по сэмплированным параметрам. Оптимальными структурными параметрами считаются те, которые доставляют максимум аппроксимирующей функции.
Для проверки качества предлагаемых алгоритмов используется метод скользящего контроля оценки структурных параметров [233, 122]. Этот метод не использует вероятностных предположений о структуре модели. Метод основан на многократном разбиении выборки на обучающую и контрольную части и подсчете функции ошибки на контрольной части выборки. Наилучшим структурным параметрам соответствуют те, при которых модель дает минимальную среднюю ошибку на различных разбиениях [130, 197, 217, 218].
Помимо моделей общего вида в работе в качестве частного случая рассматриваются линейные модели [306, 346]. Их отдельное рассмотрение позволяет выписать некоторые формулы, как, например, вычисление гессиана функции ошибки [403], в явном виде, и избежать избыточной оптимизации.
В работе рассматриваются также алгоритмы оптимизации структурных параметров регрессионной модели. Для оценки правдоподобия модели алгоритмы используют метод аппроксимации Лапласа функции ошибки, метод Монте-Карло, метод скользящего контроля.
Исследованы свойства предлагаемых методов: сходимость, вычислительная сложность.
При постановке и решении задач регрессионного анализа [322, 312, 226, 309, 172, 114, 359, 236, 238, 349, 205, 166, 398, 198, 209, 341, 242, 261, 88] встают следующие фундаментальные вопросы.
Как выбрать структуру модели?
Какова гипотеза порождения данных, каково распределение случайной переменной, какому семейству оно должно принадлежать?
Какова связь гипотезы порождения данных и распределения параметров модели?
Какой функцией ошибки требуется оценивать качество аппроксимации?
Как оценить параметры модели, каков должен быть алгоритм оптимизации параметров?
Эти вопросы рассматриваются ниже в постановочной главе, и далее в данной работе.
1.1. Функция регрессии и регрессионная модель Регрессионный анализ метод анализа измеряемых данных и исследования связи между независимыми и зависимыми переменными [182, 63, 69, 4]. Измеряемые данные представляют собой пары значений зависимой переменной y и независимой переменной x. Считается [67], что эта зависимость является статистической и имеет вид Регрессия математическое ожидание случайной величины y, зависящей от другой величины или от нескольких величин x. Зависимость f называется функцией регрессии от независимой переменной x при некоторых фиксированных параметрах w. Переменная x также называется регрессором. Точность, с которой функция f передает изменение в среднем при изменении x, измеряется дисперсией y, вычисляемой для каждого x: D(y|x) = y (x). Если D(y|x) = 0 при всех значениях x, то с вероятностью равной единице эти величины связаны функциональной зависимостью. Если D(y|x) = 0 ни при каком значении x и f (w, x) не зависит от x, то регрессия y по x отсутствует.
Основной задачей регрессионного анализа является нахождение функции регрессии f и оценка параметров w. При решении этой задачи используются измеряемые данные выборка реализаций свободных переменных и зависимой переменной.
Определение 1. Регрессионная выборка D = (xi, yi ) m множество m пар, состояi= щих из вектора xi = [xij ]n значений n свободных переменных и соотвествующего этому вектору значения зависимой переменной yi.
Далее предполагается, что переменные принадлежат множеству действительных чисел, либо его подмножеству: x X Rn и y Y R1. Индекс i элемента выборки и индекс j свободной переменной рассматриваются как элементы конечных множеств В дальнейшем будет использоваться также обозначение D = (X, y), где y = [y1,..., ym ]T вектор значений зависимой переменной и X матрица плана Матрицу X можно представить в виде где j j-й столбец матрицы, j = [1,..., n ]T. Регрессионную выборку также удобно представить как пару Предполагается, что элементы выборки связаны соотношением которое аддитивно включает случайную величину = (x). Предположение о том, что то зависимая переменная есть сумма значений модели и некоторой случайной величины, сохраняется и ниже. Мультипликативное включение случайной величины в соотношении (2) может быть представлено в аддитивном виде путем логарифмирования обеих частей выражения при условии, что независимые переменные принимают положительные значения.
Определение 2. Ошибкой или регрессионным остатком i называется разность между значением функции регрессии f (w, xi ) и значением зависимой переменной, соответствующей некоторой свободной переменной xi :
или где вектор-функция f = f(w, X) = [f (w, x1),..., f (w, xm)]T Y.
Выборка может быть как функцией дискретного аргумента, так и отношением. Например, данные для построения регрессии могут быть такими: D = {(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (1, 3)}. В такой выборке одному значению переменной x соответствует несколько значений переменной y, как показано на рис. 1.
Рис. 1. Пример выборки: зависимость объема продажи товара от цены.
Для нахождения функции регрессии f используются регрессионные модели.
Определение 3. Регрессионная модель параметрические семейство функций, отображение декартова произведения области допустимых значений W параметров модели и области допустимых значений X свободных переменных в область значения Y зависимой переменной. Иначе, регрессионная модель есть поэлементное отображение в котором вектор параметров w W, свободная переменная x X и зависимая переменная y Y.
Синонимами термина регрессионная модель являются термины теория, гипотеза.
Эти термины используются в статистике, в частности в разделе проверка статистических Рис. 2. Пример функции регрессии: зависимость цены товара от времени.
гипотез [281, 324, 313]. Регрессионная модель есть гипотеза, которая должна быть подвергнута статистической проверке, после чего она принимается или отвергается при выполнении процедуры выбора.
В дальнейшем предполагается, что выполнены следующие базовые условия:
1) функция f является непрерывной и гладкой по аргументу w, 2) множества W, X и Y являются подмножествами степеней декартовых произведений множества действительных чисел R · · · R.
Определение 4. Функция регрессии f функция полученная путем сужения области определения регрессионной модели f на заданное значение вектора параметров w.
Далее для краткости регрессионная модель будет называться моделью, а функция регрессии будет называться регрессией. В машинном обучении модель называют настроенной или обученной, если зафиксированы её параметры.
Различают следующие виды регрессионных моделей:
1) линейные модели [271, 346] модели, которые могут быть представлены в виде скалярного произведения вектора свободных переменных и вектора параметров модели в частности, линейными являются полиномиальные и криволинейные модели;
2) обобщенно-линейные модели [306, 180, 229, 284, 280, 227] модели вида где функция µ, называющаяся функцией связи, принадлежит множеству функций, заданному гипотезой о том, что распределение зависимой переменной принадлежит экспоненциальному семейству, см. раздел 1.2.;
которые не могут быть представлены как линейные (3) или обобщенно-линейные (4).
Различают одномерную и многомерную регрессию с одной и с несколькими свободнывектор x Rn. В частми переменными. Будем считать, что свободная переменная ных случаях, когда свободная переменная является скаляром, она будет обозначаться.
На рис. 2 показана функция регрессии f (w, ) = w1 + w2 2 + (). Ее оптимальные параметры w = [0.2839, 0.2412]. Соответствующая регрессионная модель имеет вид f = xT w, где Так как переменная y рассматривается в регрессионном анализе как случайная величина, то при восстановлении функции регрессии f и параметров w регрессионной модели f (w, x) используются вероятностные гипотезы.
Определение 5. Гипотезой порождения данных называется предположение о виде распределения случайной величины y и значених параметров этого распределения (если распределение параметрическое).
Эта гипотеза играет центральную роль в выборе критерия оценки качества модели и, как следствие, в методе оценки параметров модели. Для подтверждения или опровержения этой гипотезы выполняются статистические тесты, называемые анализом регрессионных остатков [124, 281, 324, 313]. При этом считается, что независимая переменная x не является случайной величиной, не содержит ошибок и не нуждается в дополнительных статистических гипотезах.
exp S(w) Рис. 3. Вид функции exp S(w) в окрестности оптимального вектора параметров.
Так как дисперсия и математическое ожидание зависимой переменной y зависит от реализаций x1,..., xm свободной переменной x, будем считать реализации зависимой переменной y многомерной случайной величиной y = [y1,..., ym ]T. В регрессионных задачах рассматриваются две основные многомерные случайные величины: зависимая переменная y и вектор параметров w.
Многомерная случайная величина упорядоченный набор (вектор) y = [y1,..., ym]T фиксированного числа m одномерных случайных величин. Многомерное наблюдение y реали- зация многомерной случайной величины y. Многомерная выборка Y = [ 1,..., yn ] неупоряy доченный набор фиксированного числа n многомерных наблюдений. Основными числовыми характеристиками многомерной случайной величины являются вектор средних и ковариационная матрица.
Вектор средних вектор математических ожиданий многомерной случайной величины, E(y) = [E(y1 ),..., E(ym )]T. Оценкой вектора средних по многомерной выборке Y, если верна гипотеза нормального распределения y, является среднее значение её реализаций, иначе среднее значение по строкам матрицы Y. При этом каждый элемент вектора параметров w равен n, где n число реализаций.
В качестве примера получения многомерной выборки по наблюдениям зависимой переменной можно привести восстановление регрессии непараметрическими методами в задачах прогнозирования временных рядов. При этом каждая строка матрицы Y содержит значения временного ряда в окрестности, заданной независимой переменной временем.
Пусть элементы многомерной случайной величины y имеют конечные дисперсии. Ковариационной матрицей величины y называется квадратная матрица элементы которой ij = cov(yi, yj ) = E (yi Eyi )(yj Eyj ) ковариации случайных величин yi и yj. На главной диагонали матрицы находятся дисперсии ii случайных величин yi.
Оценкой ковариационной матрицы по многомерной выборке Y является где Y обозначает центрированность столбцов матрицы Y. Ковариационная матрица симметрична и неотрицательно определена, В дальнейшем рассматриваются три варианта описания многомерных случайных величин y и w посредством ковариационных матриц. При этом используется матрица B, обратная к ковариационной матрице величины y, Ниже во всех примерах предполагается нормальное распределение N (·, ·) соответствующих многомерных случайных величин.
Для зависимой переменной y выполняется один из трех вариантов гипотезы порождения данных:
1) элементы зависимой переменной, случайной величины y, имеют одинаковую дисперсию 2 (y) и независимы, cov(yi, yj ) = 0, i, j I, i = j, 2) элементы переменной y имеют различную дисперсию и независимы, то есть, 3) элементы переменной y описываются ковариационной матрицей общего вида, В выражениях (3), (4) и (5) переменные y и w связаны функциональной зависимостью.
Поэтому параметры модели f также являются случайными величинами. Распределение этих параметров зависит от гипотезы порождения данных. При заданной линейной модели либо при заданном линеаризованном виде в котором матрица J есть матрица Якоби функции f, линейное отображение задаваемое матрицей X, переводит распределение многомерной случайной величины y в распределение многомерной случайной величины w. В случае нормального распределения случайной величины y распределение величины w также является нормальным. Обозначим A1 ковариационную матрицу параметров w.
Как и для зависимой переменной y, для параметров w выполняется один из трех вариантов:
1) параметры имеют одинаковую дисперсию 2 (w) и независимы, cov(wj, wk ) = 0, j, k 2) параметры модели имеют различную дисперсию и независимы, 3) параметры модели описываются ковариационной матрицей общего вида Таблица 1. Варианты гипотезы порождения зависимой переменной и параметров модели.
Определение 6. Параметры j, j J распределения параметров w модели f (w, x) называются гиперпараметрами. Ковариационная матрица A = [kj ] называется матрицей гиперпараметров.
Для гипотез (9), (10) и (11) матрица гиперпараметров имеет, соответственно, вид 1) A = I, 2) A = diag(1,..., n )I, 3) A.
Аналогично, назовем гиперпараметрами и обозначим i, i I параметры распределения зависимой переменной y.
Варианты гипотезы порождения данных. Считаем вектор зависимых переменных y и вектор параметров w многомерными нормально распределенными случайными величинами с ковариационными матрицами A1 и B1 соответственно. Чтобы получить оценки гиперпараметров A, B, w, введем ограничения на вид распределений p(D|w, B) и p(w|A). Для зависимой переменной y и для параметров w выполняется один из трех вариантов гипотезы порождения данных, продемонстрированных в таблице 1. Рассматриваются матрицы A и B скалярного, диагонального и полного вида, независимо друг от друга. Предложенные ниже методы позволяют решить задачу для случая матрицы B скалярного вида, т.е. B = I. При этом рассматриваются различные виды матрицы A.
При решении задач, к исходной выборке могут быть выдвинуты требования, связанные с природой измерения величин. При этом рекомендуется привести значения переменных к единой шкале с целью исключением шкалы и единицы измерения из дальнейшего рассмотрения [378].
Стандартизация данных. Выборка D стандартизируется таким образом, чтобы выполнялись условия нормированности и центрированности признаков столбцов матрицы плана X, а также условие центрированности вектора y:
Экспоненциальное, гам- Мультипликативная Обратное нормальное Обратная квадратичная или, в векторных обозначениях, Предполагается, что векторы j, k линейно независимы для всех значений j, k J, j = k.
Линейно зависимые векторы исключаются из дальнейшего рассмотрения.
Разбиение скользящего контроля. Дополнительно может быть задано разбиение множества индексов I = LC элементов выборки D на обучающее и контрольное подмножества.
Для каждой выборки, рассматриваемой при решении задач регрессионного анализа, наборы индексов L, C определены до начала эксперимента.
Далее предполагается, что распределение зависимой переменной принадлежит экспоненциальному семейству. Экспоненциальное семейство распределений [141] многомерной случайной величины y с вектором параметров задается набором распределений вида Вектор называется вектором естественных параметров распределения. Сомножитель u(y) некоторая вектор-функция многомерной случайной величины y.
Гипотеза принадлежности распределения зависимой переменной экспоненциальному семейству используется при построении обобщенных линейных моделей (4), то есть, моделей вида для которых µ функция связи, а Xw линейная комбинация признаков выборки. Канонические функции связи, соответствующие частным случаям экспоненциального семейства, представлены в таблице 2.
В [88, 280] показано, что из гипотезы о принадлежности распределения p(y) зависимой переменной y каноническому экспоненциальному семейству, при использовании соответствующей этому распределению функции связи µ, следует, что параметры w N (w, A1) обобщенно-линейной модели распределены нормально.
При решении прикладных задач наибольший интерес представляют два распределения этого семейства: нормальное и биномиальное [171, 284]. Первое используется в задачах восстановления регрессии, когда зависимая переменная принимает значения из множества R, второе используется в задачах классификации, когда зависимая переменная принимает значения из множества {0, 1}.
1.2.3. Нормальное распределение зависимой переменной Рассмотрим нормальное распределение зависимой переменной в качестве гипотезы порождения данных при восстановлении линейной или существенно-нелинейной регрессии:
Для нахождения наиболее правдоподобных параметров модели используем метод наибольшего правдоподобия [278, 277, 225]. Пусть многомерная случайная величина y N (f, B) имеет нормальное распределение В выражении (15) часть под экспонентой (y f)T B(y f) является квадратом расстояния Махаланобиса[298]. Матрицу можно представить в виде разложения Холецкого [214], B = LLT, где L диагональная нижнетреугольная матрица, либо в виде произведения B = UT U, см. [68]. Оба разложения единственны. В общем случае не предполагается, что её элементы независимы и не коррелируют. Ковариационная матрица B является симметричной неотрицательно определенной матрицей. Диагональные элементы i этой матрицы являются обратны значениям дисперсии элементов случайной величины y:
Так как правая часть выражения (15) зависит от вида регрессионной модели f, вектора параметров w, независимой переменной x и от ковариационной матрицы B, перепишем его в виде где ZD нормирующий коэффициент для плотности нормального распределения Функция ошибки, соответствующая матожиданию регрессионной модели при данной гипотезе, определена как Рассмотрим частный случай гипотезы порождения данных: элементы вектора y не коррелируют и имеют одинаковую дисперсию, то есть обратная ковариационная матрица B = Im.
В этом случае вид функции правдоподобия (16) упрощается: коэффициент ZD имеет вид a функция ошибки равна так как при справедливо выражение Рассмотрим вектор параметров w модели f многомерную случайную величину. Согласно принятой гипотезе распределения (15) зависимой переменной и теореме о функциях связи распределений [88, 280], распределение параметров w N (wML, A1) является нормальным с матожиданием wML, ковариационной матрицей A1 и имеет вид Выражение (19) справедливо для линейных моделей, поскольку многомерные случайные величины y и w связаны линейным отображением X. Для существенно нелинейных моделей предполагается, что это выражение будет справедливо в окрестности w некоторой точки w при линеаризации Матрица Якоби J это матрица частных производных модели f по элементам wj вектора параметров w:
Это предположение используется, например, в аппроксимации Лапласа [294, 394], согласно которой функция распределения параметров существенно нелинейной модели может быть приближена функций нормального распределения.
Нормирующий коэффициент Zw (A) равен где n число параметров модели f. Функция-штраф за большое значение параметров модели для принятого распределения определена как Рассмотрим частный случай: дисперсии элементов wj вектора параметров w равны, обратная ковариационная матрица имеет вид A = In. В этом случае выражения (20) и (21) Для нахождения наиболее вероятных параметров модели f (w, x) используем Байесовский вывод [146, 254, 244]. При заданной модели f и заданных значениях A и B выражение (16) принимает вид Элементы этого выражения и соответствующие им параметры:
Записывая функцию ошибки S = Ew + ED в виде получаем вместо (22) выражение где ZS нормирующий коэффициент.
Заметим, что матожидание вектора параметров в некоторых случаях может быть гипотетически принято равным нулю, w = 0. Такое предположение явно или неявно принимается при решении задач выбора признаков линейных регрессионных моделей, см. Лассо [384], Stagewise [232], LARS [184], а также при прореживании некоторых нелинейных моделей [231, 279].
При рассмотрении частных случаев ковариационных матриц A = In и B = Im, параметров модели w и гомоскедастичной зависимой переменной y выражение (22) принимает вид a функция ошибки Параметры и в последнем выражении играют роль регуляризирующих множителей [152, 382].
1.2.4. Биномиальное распределение зависимой переменной В данной работе задача классификации рассматривается как задача логистической регрессии [266, 243, 280], тo есть, как частный случай задачи восстановления регрессии (1).
В данном случае регрессия и классификация различаются не более чем предположением о распределении зависимой переменной y. При этом принимается гипотеза о биномиальном распределении зависимой переменной y {0, 1}:
случайная величина y принимает значение 0 c вероятностью P и значение 1 с вероятностью 1 P. Таким образом, функция регрессии f (w, x) в случае биномиального распределения зависимой переменной восстанавливает регрессию, равную вероятности принадлежности вектора x к одному из двух классов. Функция правдоподобия реализаций многомерной случайной величины y имеет вид Модель логистической регрессии имеет вид Выражение (25) при гипотезе (24) имеет вид а производная этой функции по параметрам равна где (X, w) сигмоидная функция. Перепишем функцию ошибки общего вида (23) для гипотезы (25) в виде На рисунке 4 синими и красными точками показана выборка, состоящая из двух классов.
Восстановленная регрессия показана поверхностью f (w, x), значение которой равно вероятности принадлежности элемента выборки x к одному из двух классов. Прогнозируемая принадлежность показана окружностями. При несовпадении цветов точки и окружности следует говорить об ошибке классификации.
1.2.5. Функция ошибки и гипотеза порождения данных Задача восстановления регрессии есть задача нахождения условного матожидания. Для оценки качества решения этой задачи вводится функция ошибки, исходя из значения которой делается вывод о том, насколько хорошо модель приближает данные, а также насколько адекватна гипотеза порождения данных [182, 2, 55, 233].
Определение 7. Функция ошибки S(w) функция, значение которой требуется минимизировать для получения оценок параметров w модели f, удовлетворяющих заданным требованиям.
Например, это одно из следующих требований:
требование максимизации правдоподобия данных, требование максимизации вероятности параметров модели, требование максимизации правдоподобия самой регрессионной модели, требования состоятельности, несмещенности оценки параметров, либо другие требования, определяемые решаемой задачей восстановления регрессии.
Функция ошибки назначается одним из двух способов:
1) путем байесовского вывода, тогда она определяется гипотезой порождения данных и, опционально, принятой регрессионной моделью (выше приведены примеры (23) и (27) для гипотез нормального и биномиального распределения зависимой переменной);
2) другим путем, который учитывает особенности постановки решаемой прикладной задачи.
Во втором случае несмещенность и другие статистические свойства полученных оценок параметров не исследуются. В качестве примера приведем функции ошибки, обеспечивающие выполнение требований промышленных стандартов [99] и требований к минимизации потерь при совершении торговых операций [5]. В первом примере симметричная функция ошибки имеет вид Во втором примере несимметричная функция ошибки, являющаяся кусочно-линейной функцией, имеет вид Параметры as, bs и концы отрезков zs выбираются согласно расчетам убытков при совершении торговых операций при условии непрерывности функции ошибки и её первой производной. В обоих случаях происходит отказ от принятия гипотезы порождения данных, и функция ошибки S(w) оптимизируется, исходя из условий поставленной задачи. Например, при восстановлении регрессии измерений некоторых физических величин используется метод наименьших модулей [24, 85, 78], согласно которому функция ошибки задана как сумма модулей регрессионных остатков. Задача нахождения минимального значения функций вида (28) или (29) решается методами линейного программирования. В таблице 3 приведен набор функций ошибок, часто используемых при решении задач прогнозирования.
Таблица 3. Функции ошибок регрессионных моделей.
остатков Функция ошибки и разбиение выборки. В данной работе не предполагается, что для оценки наиболее вероятных параметров модели, либо для выбора наиболее правдоподобной модели из некоторого множества требуется разбиение множества индексов I элементов выборки D = {(xi, yi )}, i I на обучающую и контрольную: I = L C. Тем не менее, следует отметить, что при выборе моделей такое разбиение является одним из наиболее эффективных способов избежать переобучения, см. [91, 73, 295]. Поэтому ниже приведен ряд примеров эвристических функций ошибок, предложенных авторами метода группового учета аргументов. Данные функции называются критериями. Значительная их часть опубликована на сайте [100].
Используемые в этом подразделе обозначения XC, yC, wL означают, что значения переменных X, y, w фиксированы, в выборку (XC, yC ) вошли только объекты с индексами из множества C I =, а оцека вектора параметров wL получена с использованием выборки, состоящей из элементов с индексами из множества L I = :
При этом считается, что множество индексов I элементов выборки разбито на подмножества в котором L обучающая выборка, C котрольная выборка, V валидационная выборка.
Последняя в ряде задач может быть пустой.
Метод группового учета аргументов [59, 14, 17] использует внутренний и внешний критерий, так как при оценке параметров моделей и при выборе моделей используются разные элементы выборки. Внутренний критерий используется для оценки параметров: их значения оцениваются на подвыборке элементов с индексами из L. Выбор моделей производится с помощью внешнего критерия, значение которого вычисляется на множестве C. При выборе минимум внешнего критерия означает, что модель, доставляющая такой минимум, является искомой.
Рис. 5. Внешний и внутренний критерии при различных значениях структурной сложности.
Критерий регулярности S2 равен норме разности вектора значений зависимой переменной и вектора значений функции регрессии на тестовой подвыборке C при параметрах, оцененных на обучающей подвыборке L.
где Этот критерий может быть нормирован выражениями yL 2 или yL mean(yL ) 2.
Критерий предсказательной способности модификация критерия регулярности для задач прогнозирования. Этот критерий включает среднеквадратичную ошибку для валидационной выборки V, которая не используется ни при оценке параметров, ни при выборе модели. В этом случае выборка делится на три части. Критерий предсказательной способности имеет вид Критерий минимального смещения или критерий непротиворечивости: модель, которая имеет на обучающей и на контрольной выборках различные векторы невязок, называется противоречивой. Критерий задан разностью между значениями функции регрессии, вычисленными на двух различных выборках, заданных множествами L и C и требует, чтобы оценки параметров, вычисленные на этих выборках, различались минимально. Он имеет вид:
модификация:
где wC и wL векторы параметров, полученные с использованием подвыборок C и L.
Критерий иммунитета к шуму имеет вид где wI вектор параметров, полученный с использованием полной выборке I. Утверждается [59], что с помощью этого критерия в сильно зашумленных данных можно найти скрытые закономерности.
Комбинированный критерий позволяет использовать при выборе моделей линейную комбинацию нескольких критериев. Комбинированный критерий Здесь Sk принятые на рассмотрение критерии, а vk веса этих критериев, назначенные в начале вычислительного эксперимента.
Используются также нормализованные значения критериев. При этом предыдущая формула имеет вид Максимальное значение критерия max(Sk ) берется по вычисленным значениям критериев Sk (f ) для всех порожденных моделей f F.
Задача восстановления регрессии (1) имеет несколько разных постановок, каждую их которых можно условно отнести к одному из следующих типов:
1) задачи оценки параметров модели, 2) задачи выбора признаков или объектов регрессионной выборки, 3) задачи выбора регрессионных моделей, 4) задачи проверки гипотезы порождения данных.
Предполагается, что функция ошибки S(w) задана гипотезой порождения данных. При задании функции ошибки используется байесовский вывод. Предполагается, что зависимая переменная имеет распределение из экспоненциального семейства (13), например, нормальное (15) или биномиальное (24). В гипотезу также включены условия взаимозависимости элементов целевого вектора y как многомерной случайной величины, например, условие гомоскедастичности (6), независимости (7) или гетероскедастичность (8) как отсутствие этих условий.
Функция ошибки может быть также определена исходя из постановки задачи, например, в случаях (28) или (29), когда её вид определен задачей минимизации потерь.
Задача 1. Задана выборка D = {(xi, yi )}, i I, функция ошибки модели S и модель параметрическое семейство функций f (w, x). Требуется найти такие параметры w модели, которые бы доставляли минимум функции ошибки В выражении (30) справа от вертикальной черты указаны фиксированные значения переменных, что читается: при заданной выборке D и модели f, аналогично обозначению, принятому для записи условной вероятности. Далее предполагается, что запись S(w) экивалентна записи S(w|D, f ), если специально не оговорено иное.
Например, задан критерий качества линейной регрессионной модели при предположениях (15) и (6). Также предполагается, что выполнены условия (37). Требуется найти параметры весовые коэффициенты, доставляющие минимальное значение функции ошибки квадрату евклидовой нормы вектора невязок S(w) = iI yi f (w, xi ) min. Ряд примеров, где f фиксированная нелинейная регрессионная модель рассмотрен в [347].
Функция ошибки, определенная посредством логарифмической функции правдоподобия, как в (16) и (17), обеспечивает максимизацию правдоподобия параметров. Параметры, найденные минимизацией этой функции ошибок, называются наиболее правдоподобными, а задача (30) имеет вид Параметры, найденные минимизацией функции ошибок, заданной апостериорным распределением (22), называются наиболее вероятными, а задача (30) имеет вид При этом предполагается, что обратные ковариационные матрицы A, B заданы, или оценивание уже выполнено.
Для выбора модели из некоторого множества допустимых моделей требуется ввести понятие сложности модели [220]. Различают следующие типы сложности:
1) обобщающая способность модели, оцениваемую с использованием скользящего контроля [295];
2) статистическая сложность модели, например, Mallow’s Cp [300], AIC [117], BIC [145] 3) минимальная длина описания модели, оцениваемая с использованием оценок правдоподобия модели [379, 381], 4) структурная сложность модели [390, 389, 208], зависящая от вида суперпозиции элементарных функций, которые задают модель.
Связано это с тем, что при выборе модели без учета сложности [383], будет выбрана наиболее сложная модель. Поставим задачу выбора моделей для случая обобщенно-линейных моделей. При этом число параметров и число признаков модели будут равны (равенство числа признаков и параметров может не быть в случае нелинейных моделей). Задача выбора модели тогда сводится к выбору признаков, то есть к поиску такого множества индексов признаков A J, которое доставит оптимальное значение критерию сложности модели.
При использовании скользящего контроля, критерии которого описаны в предыдущем разделе, задача выбора модели ставится следующим образом.
Задача 2. Задана выборка D = {(xi, yi )}, i I, где множество векторов свободных переменных {x = [x1,..., xj,..., xn ]}, проиндексировано j J = {1,..., n}. Задано разбиение скользящего контроля множества индексов элементов выборки I = L C. Задана функция ошибки S и модель параметрическое семейство функций f (w, x) = µ(wT x), где µ функция связи (14). Требуется найти такое подмножество индексов A J, которое бы доставляло минимум функции:
на подмножестве DC разбиении выборки D, определенном множеством индексов C. При этом параметры w модели должны доставлять минимум функции:
на подмножестве DL разбиении выборки, определенном множеством индексов L. Здесь fA обозначает обобщенно-линейную модель f = µ(wA xA ), включающую только столбцы матT рицы X с индексами из множества A.
Нелинейная модель не может быть однозначно задана множеством A активных признаков. Поэтому для задания модели используются правила индуктивного порождения моделей детально определенные в следующем разделе. Они позволяют однозначно индексировать модели f из множества моделей F.
Задача 3. Задана выборка D = {(xi, yi )} и разбиение скользящего контроля i I = L C.
Задано множество порождающих функций G = {g1,..., gn }. Заданы правила индуктивного порождения множества моделей F = {fr }, индексированных счетным множеством R r.
Требуется найти такую модель fr, которая бы доставляла минимум функции при условии оценки оптимальных параметров w решением задачи (32).
1.3.3. Оценка ковариационных матриц зависимой переменной и параметров Задача 4. Задана выборка D, гипотеза порождения данных H, соответствующая ей функция ошибки S(w) и модель f (w, x). Задан вектор w оптимальных параметров модели.
Требуется оценить обратные ковариационные матрицы A, B для случаев (6)–(11), максимизируя правдоподобие модели:
1.3.4. Совместный выбор объектов и признаков в обобщенно-линейных Обобщенно-линейная модель f однозначно задается активным множеством индексов признаков A J. Функция связи задана гипотезой порождения данных. Предполагая частичную гомоскедастичность выборки (например, среди объектов встречаются выбросы, которые должны быть исключены из рассмотрения), зададим фильтрованную выборку (другими словами активное множество объектов) индексами из множества B I. Обозначим множество векторов {xi |i B} как xB. Задача выбора модели имеет вид где функция правдоподобия модели равна интегралу по пространству её параметров Подынтегральное произведение включает функцию правдоподобия данных и априорное распределение параметров модели.
Обобщим предыдущую задачу на случай существенно нелинейных моделей. При этом для простоты будем считать, что элементы-выбросы уже исключены из регрессионной выборки, то есть, I = B. Тогда задача выбора правдоподобной модели fr c индексом r из множества моделей-претендентов F имеет следующий вид.
Задача 5. Задана выборка D = {(xi, yi )}, i I. Задано множество моделей F = {fr }, индексированных счетным множеством R r. Требуется выбрать наиболее правдоподобную модель Заметим, что оценивать параметры модели для того, чтобы выбрать наиболее правдоподобную модель, необязательно.
При предположении о равенстве априорных вероятностей моделей:
задача выбора наиболее правдоподобной модели становится эквивалентной задаче выбора наиболее вероятной модели. Задача оценивания апостериорного распределения или априорной функции вероятности моделей в данной работе не рассматривается.
В случае, когда невозможно получить адекватную функцию регрессии в связи со сложностью регрессионной выборки, решается задача восстановления регрессии с помощью нескольких регрессионных моделей. При этом некоторому элементу выборки может быть поставлена в соответствие либо одна, либо несколько моделей.
Определение 8. Многоуровневой моделью f называется набор моделей f = {fk (wk, xBk )|f F}, k = 1,..., K, такой, что при разбиении Задача 6. Задана выборка D, гипотеза порождения данных H, набор моделей F fk и распределения p(D|w, B, fk ), p(w|A, fk ). Требуется найти разбиение I = Bk, которое доставляло бы максимум произведению функций правдоподобия соответствующих моделей:
Правдоподобие модели определено в (35).
Частным случаем задачи разбиения выборки на несколько подмножеств является задача выбора опорных объектов [355]. При постановке этой задачи множество индексов разбивается на два подмножества, B1 B0 = I, причем модель определяется только на выборке c индексами объектов B1. Эти объекты считаются опорными. Объекты с индексами B0 при решении задачи не рассматриваются.
Данная задача возникает при прогнозировании квазипериодических временных рядов.
При нахождении многоуровневой модели может возникнуть ситуация, когда две или несколько моделей оказываются похожими. Предлагается сократить число моделей за счет обънайти функцию h : i, j единения элементов выборки, которые к ним относятся, иначе k, для некоторых i, j {1,..., K}, таких, что Bk = Bi Bj B. В качестве функции расстояния между моделями предлагается использовать расстояние Дженсена-Шеннона, вычислямое как расстояние между апостериорными распределениями моделей.
Задача 7. Задано разбиение выборки I = B1 · · · BK. Требуется найти функцию, отображающую {1,..., K} {1,..., P }.
Выше предполагалось, что гипотеза порождения данных определяет функцию ошибки и, в конечном итоге, выбранную модель. Однако, после получения оптимальной модели необходимо выполнить анализ регрессионных остатков, целью которого является возможное отвержение принятой ранее гипотезы.
Задача 8. Заданы выборка D и функция регрессии f (w, x), то есть, задан вектор регрессионных остатков = f y. Задан набор гипотез порождения данных H = {H()} функций распределения многомерной случайной величины y. Требуется оценить параметры каждой функции распределения и выбрать наиболее адекватную гипотезу порождения данных.
Оценки параметров при выборе гипотезы порождения данных должны быть несмещенные и состоятельные [155]. Оценка (x1,..., xn ) параметра называется несмещенной, если E(X1,..., Xn ) = для всех. Смещением называется разность Оценка (x1,..., xn ) параметра называется состоятельной, если для всех последовательность Символ означает сходимость по вероятности: для любого > 0 вероятность P (|n | > ) 0 при n. Предлагаемый состав методов анализа регрессионных остатков приведен ниже.
Математические объекты, упомянутые в вышеперечисленных задачах сведены в таблицу 4. Знак прочерка – означает, что соответствующий объект в задаче не используется, либо вычисляется в ходе решения и используется как промежуточный результат.
Оценка параметров моделей является одной из наиболее часто решаемых задач регрессионного анализа. Способ получения оптимального решения w0 может определяться видом Таблица 4. Сводная таблица задач, решаемых при восстановлении регрессии.
дения данных оптимизируемой функции [156, 153, 342] ошибок S(w), но также решение может быть получено с помощью стохастических оптимизационных алгоритмов [400]. Последние называют также алгоритмами глобальной оптимизации, и, как показано в [397, 395, 396], эти алгоритмы могут быть более эффективны, чем алгоритмы, использующие градиентный спуск, особенно в случаях большого числа локальных экстремумов функции ошибки. На практике применяется комбинация этих алгоритмов. Далее будут рассмотрены модификации таких алгоритмов, как алгоритм Левенберга-Марквардта [282] и алгоритм регионов доверия [173].
Нахождение параметров w линейной модели (3) при предположении о нормальном распределении (15) зависимой переменной y заключается в минимизации евклидовой нормы вектора регрессионных остатков 1) независимые переменные x не являются случайными величинами, 2) математическое ожидание E() = 0, 3) дисперсия D() = I (условие гомоскедастичности), 4) при i = k математическое ожидание E(i, k ) = 0, Эти условия называются условиями Гаусса-Маркова [58]. При этом оценки параметров модели (3) являются состоятельными и несмещенными. Оценки являются также эффективными, если N (0, I).
Требуется минимизировать евклидово расстояние от вектора y до вектора Xw. Этот вектор лежит в пространстве столбцов матрицы X, так как Xw это линейная комбинация столбцов этой матрицы с коэффициентами w1,..., wn. Задача оценки w эквивалентна задаче нахождения точки p = Xw, ближайшей к y и находящейся в пространстве столбцов матрицы X. Следовательно, вектор p должен быть проекцией y на пространство столбцов, вектор регрессионных остатков Xw y должен быть ортогонален этому пространству. Рассмотрим произвольный вектор Xv, ортогональный вектору регрессионных остатков Xw y:
Так как это равенство должно быть справедливо для произвольного вектора v, то XT Xw XT y = 0, см. рис. 6. Если столбцы матрицы X линейно независимы, то матрица XT X обратима и уравнение имеет единственное решение относительно параметров Рис. 6. Проекция вектора зависимой переменной на пространство столбцов матрицы плана.
Проекция вектора y на пространство столбцов матрицы X имеет вид Матрица P = X(XT X)1XT называется матрицей проектирования. Она она идемпотентна, P2 = P, и симметрична, PT = P.
Используемые здесь методы нахождения оптимальных параметров моделей предполагают непрерывную дифферренцируемость функции S(w) в области W w. Согласно (36), Для того, чтобы найти минимум этой функции, требуется приравнять её градиент к нулю:
Решение этого уравнения совпадает с решением (38).
Для произвольной существенно нелинейной модели f (w, x) принята гипотеза (15) о нормальности распределения зависимой случайной величины y. Требуется найти такое значение вектора параметров w, которое бы доставляло локальный минимум функции S(w), заданной выражением (36). Принятие этой функции ошибки обусловлено предположением о возможности такой линеаризации существенно нелинейной модели f, в окрестности вектора параметров w0, котоая удовлетворяла бы условиям (37).
Так как функция S(w) имеет локальный минимум, но в общем случае этот минимум не является единственным [58, 63], то предлагается назначить начальное значение вектора параметров w0, а затем найти последовательность приближений wk вектора параметров к оптимальному вектору w по шагам:
Здесь индекс k вектора параметров обозначает номер итерации, wk вектор приращения, разность векторов параметров на двух последовательных шагах.
Для оценки приращения wk используется линейное приближение функции где J матрица Якоби (39) вектор-функции f(w, X) в точке wk.
Приращение wk в точке w, доставляющее минимум S(w), равно нулю. Поэтому для нахождения следующего значения приращения w приравняем к нулю вектор частных производных S(w) по w. Для этого представим выражение (36) в виде продифференцируем и приравняем к нулю:
Таким образом, чтобы найти значение wk, нужно решить систему линейных уравнений В том случае, когда функция ошибки S(w) задана как взвешенная сумма квадратов остатков, где W диагональная матрица с неотрицательными элементами на диагонали, уравнение (41) будет иметь вид Так как число обусловленности матрицы JT J есть квадрат числа обусловленности матрицы J, то матрица JT J может оказаться существенно вырожденной. Проблема большого числа обусловленности матрицы JT J, возникающая при итеративном нахождении параметров существенно-нелинейных моделей, решается методами регуляризации [382, 16, 49, 107].
При этом вводится параметр регуляризации 0:
Параметр назначается на каждой итерации алгоритма. Если значение ошибки S убывает быстро, то можно выбрать близкое к нулю значение и свести этот алгоритм к алгоритму Гаусса-Ньютона [282].
Итерации прекращаются в том случае, если приращение w в последующей итерации меньше заданного значения, либо если параметры w доставляют ошибку S(w), меньшую заданной величины. Значение вектора w на последней итерации считается искомым.
Недостаток алгоритма значительное увеличение параметра при плохой скорости сходимости. При этом обращение матрицы (JT J + I) сводится к обращению её второго слагаемого. Этот недостаток можно устранить, используя диагональ матрицы JT J в качестве регуляризующего слагаемого:
1.4.3. Оптимизация целевой функции общего вида Приведем вариант алгоритма, описанного в предыдущем разделе, который минимизирует не функцию ошибки (36), функцию ошибки (23) общего вида, которая включает матрицы гиперпараметров A, B. Как и ранее, используем пошаговое линейное приближение (40), в котором строка матрицы Якоби Ji = f (w,xi ). Разложение целевой функции в ряд Тейлора имеет вид S(w + w) (w + w)T A(w + w) + (y f(w, X) Jw)T B (y f(w, X) Jw).
Отбросив члены второго порядка, получим:
Для нахождения минимума функции S(w + w) приравняем к нулю её градиент по w:
откуда получим решение нормального уравнения для функции ошибки общего вида Так как число обусловленности матрицы (JT J)1 растет при приближении функции S(w) к минимальному значению, как в случае (42) используем регуляризирующий параметр.
Сформулируем вышеприведенные результаты в виде теоремы.
Теорема 1. Для гипотезы нормального распределения зависимой переменной при фиксированных ковариационных матрицах A1, B1 итерационный алгоритм оценки параметров доставляет локальный минимум функции ошибки общего вида S(w|D, A, B, f) при сходимости последовательности векторов wk.
Замечание 1. Итерационный алгоритм wk+1 = wk+1 + wk предполагает известное начальное приближение w0. Последовательность wk+1 wk 2 монотонно убывает с увеличением номера шага k.
1.4.4. Оценка параметров функции ошибки общего вида методом Если известны значения гиперпараметров A, B для нелинейной регрессионной модели, то можно использовать алгоритм Левенберга-Марквардта для оценки вектора параметров модели w. Пусть задано некоторое приближение для значений параметров модели w. Функция ошибки имеет вид:
Для минимизации функции ошибки воспользуемся алгоритмом Левенберга-Марквардта, который предназначен для оптимизации параметров нелинейных регрессионных моделей.
Алгоритм заключается в последовательном приближении заданных начальных значений параметров к искомому локальному оптимуму и является обобщением метода сопряжённых градиентов и алгоритма Ньютона-Гаусса.
На первой итерации алгоритма задаётся начальное приближение для w. Приращение w в точке оптимума для функции ошибки (43) равно нулю. Поэтому для нахождения экстремума приравняем вектор частных производных S по w к нулю. Для этого представим S в виде двух слагаемых:
После дифференцирования получим следующие выражения:
Таким образом, чтобы найти приращение w необходимо решить систему линейных уравнений:
Так как матрицы A, B симметричные, положительно определенные матрицы ковариации, то эта система эквивалентна:
То есть, Вышеописанная процедура останавливается, в том случае, если приращение w в последующей итерации меньше заданного значения, либо если параметры w доставляют ошибку S меньшую заданной величины. Значение вектора w на последней итерации считается искомым.
Пусть целевая функция S(w) задана в виде (27), согласно гипотезе (24). Используя метод Ньютона-Рафсона [196], рассмотрим (k + 1)-й шаг минимизации целевой функции S(w) где H матрица Гессе, элементы которой являются вторыми производными целевой функции по параметрам модели Применим этот метод к модели линейной регрессии (3) считая, зависимая переменная y является нормально распределенной многомерной случайной величиной (15). Тогда первые и вторые производные функции ошибки S(w) будут иметь вид Перепишем (k + 1)-й шаг итерации (46) в виде Полученное решение эквивалентно решению методом наименьших квадратов (38).
Применим этот метод, принимая гипотезу распределения данных (24) для модели логистической регрессии (26). Дифференцируя однократно и двукратно функцию ошибки S(w) по элементам вектора параметров w, получим её градиент Рис. 7. Сходимость параметров логистической регрессионной модели.
В последнем выражении присутствует диагональная матрица весовых коэффициентов B = diag[1,..., m ] размера (m m) с элементами Так как гессиан зависит в этом случае от матрицы B, элементы которой, в свою очередь, содержат параметры модели, то целевая функция S(w) не является теперь квадратичной. Так как модель f (w, x) вида (26) принимает значения на интервале (0, 1), то для произвольного вектора u справедливо неравенство Следовательно, целевая функция S является выпуклой функцией аргумента w и имеет единственный минимум.
Процедура Ньютона-Рафсона имеет вид Элементы диагональной матрицы B интерпретируются как дисперсии элементов вектора y многомерной случайной величины. При этом условное математическое ожидание зависимой переменной и дисперсия Заметим, что для данной гипотезы порождения данных значение зависимой переменной y = y 2, так как y {0, 1}. Так как матрица B является диагональной, предполагается, что элементы многомерной случайной величины y некореллированы. При биномиальном распределении зависимой переменной и нормальном распределении параметров выражение (22), числитель которого соответствует функции ошибки S(w), процедура оценки параметров моделей имеет вид Рис. 7 иллюстрирует сходимость вышеописанного алгоритма. На оси абсцисс показана единственная свободная переменная, на оси ординат значение функции регрессии f и зависимой переменной y.
Перепишем полученные результаты в виде теоремы.
Теорема 2. Для гипотезы нормального распределения зависимой переменной вариант: биномиального при фиксированных ковариационных матриц A1, B1 итерационный алгоритм оценки параметров обобщенно-линейной модели доставляет локальный минимум функции ошибки общего вида S(w|D, A, B, f) при сходимости последовательности векторов wk.
1.4.6. Оптимизация многокритериальной функции ошибок При выборе регрессионных моделей в ряде задач требуется использовать несколько функций ошибок или критериев качества моделей. В качестве примера приведем задачу кредитного скоринга, которая ставится как задача логистической регрессии и предполагает, что оценка параметров получена в предположении о биномиальном распределении зависимой переменной. Одновременно, стандарт Basel-II [101] выдвигает ряд дополнительных критериев и требований к моделям-претендентам. В таких случаях для выбора строится Паретооптимальный фронт, называемый также оболочкой Эджворда-Парето [305, 201], включающий в качестве элементов недоминируемое геометрическое место точек.
Для решения задачи восстановления регрессии задается множество критериев, условиям оптимальности которых должна удовлетворять модель. Отыскиваются векторы, принадлежащие Парето-оптимальному фронту множества всех векторов, соответствующих порожденным моделям [26, 71, 193]. Поставим оптимизационную задачу оценки Парето-оптимального фронта в многокритериальной оптимизации. Рассмотрим невыпуклую немонотонную векторфункцию : W S, переводящую односвязную область W Rn в область S Rp. Множество W будем называть множеством возможных решений, а множество S множеством достижимых значений критериальных векторов Направления желательного изменения критериев заданы следующим образом. Задано отношение доминирования на множестве S такое, что вектор s1 S доминирует вектор s при условии, что векторы s1 = [s11,..., s1p ]T и s2 = [s21,..., s2p ]T не совпадают.
Множество S () недоминированных значений целевой функции называется Паретооптимальным фронтом Множество векторов W = {w } из прообраза отображения : W S будем называть Парето-оптимальным множеством, если образ каждого из этих векторов принадлежит Парето-оптимальному фронту:
Одним из способов сведения задачи многокритериальной оптимизации к однокритериальной является свертка критериев. Сверткой вектор-функции будем называть взвешенную сумму Оптимизационная задача имеет вид Рис. 8. Пример полученного Парето-оптимального фронта.
Парето-оптимальный фронт S также можно получить, максимизируя один из интегральных критериев его качества[388, 179, 263], описанных ниже.
Критерии качества найденного Парето-оптимального фронта включают критерии двух типов: близость к истинному фронту и разнородность или разброс решений в пространстве. Критерии близости:
1) число найденных решений Kconv (в частных случаях предполагается, что множество найденных решений счетно), расстояние от которых до предполагаемого или известного фронта не превышает заданное;
2) отношение числа недоминируемых точек фронта Knondom к количеству точек;
3) средняя сходимость к фронту µAC.
Используется следующая модификация последнего критерия:
известной границы фронта.
Критерии разнородности:
1) критерий разнообразия Шотта µSS, 2) критерий отношений объемов µVR, 3) критерий разности объемов µVD, 4) критерий разнородности µDD.
Критерий разнообразия Шотта равен где является манхеттенским расстоянием между точками si, sk найденного фронта, а d среднее расстояние d1,..., dK.
Критерий отношений объемов равен где и H объемы минимальных кубов размерности p, соответственно включающих полученный и истинный фронты.
Критерий разности объемов относительный объем области, доминируемой точками полученного фронта. Обозначим буквами C(s1 ),..., C(sK ) положительные конусы с вершинами в точках s1,..., sK фронта, включающие геометрическое место точек, доминирующее данные точки. Пусть r заданная опорная точка, R отрицательный конус, геометрическое место точек, доминируемое опорной точкой.
Критерий разности объемов задан как Рис. 9. Максимизация объема, заданного опорной точкой при поиске Парето-оптимального Здесь vol(·) объем объединения конусов, а Z множество всех точек в истинном фронте.
Рисунок 9 иллюстрирует процедуру вычисления этого критерия. Точки s1, s2 на рисунке задают конусы C(s1 ), C(s2 ). Опорная точка r задает отрицательный конус R. Заштрихованная область соответствует объединению конусов:
Искомое значение критерия определяется объемом этой области в p-мерном пространстве.
1.5. Ограничения, накладываемые на множество моделей После оценки параметров выбранной регрессионной модели встает вопрос о её статистических свойствах. При этом кроме требований и ограничений заданных прикладной задачей исследуется, во-первых, качество полученной функции регрессии и, во-вторых, её устойчивость относительно возмущения параметров. В первом случае выполняется анализ регрессионных остатков, во втором случае исследуется мультиколлинеарность признаков и вырожденность пространства параметров.
Требование соответствия вектора регрессионных остатков = y f принятой гипотезе порождения данных не только задает функцию ошибки, но и влечет ряд дополнительных условий, проверка которых называется анализом регрессионных остатков.
Анализ регрессионных остатков заключается в проверке следующих гипотез:
1) что матожидание регрессионных остатков равно нулю, 2) дисперсия регрессионных остатков постоянна и не зависит от переменной x, 3) что регрессионные остатки распределены нормально, Рис. 10. Гетероскедактичные регрессионные остатки с ненулевым средним.
где вектор регрессионных остатков некоторой модели. На рисунке 10 представлен пример регрессионных остатков, не удовлетворяющих ни одному из условий (48), (49) и (50).
Гипотеза (48) проверяется критерием знаков. Гипотеза гомоскедастичности [120, 352, 192] или постоянства дисперсий (49) проверяется тестом Ансари-Брэдли и критерием ГолдфелдаКванта. Так как тест Ансари-Брэдли проверяет равенство дисперсий двух выборок, предлагается разбить выборку регрессионных остатков на две подвыборки несколько раз. Независимость (49) проверяется статистикой Дарбина-Ватсона. Нормальность распределения (50) проверяется критерием согласия 2, который сравнивает распределение остатков с эталонным нормальным распределением, параметры которого вычислены по регрессионным остаткам. Вышеперечисленные тесты и статистики подробно рассмотрены в [43, 4, 243, 79, 183].
При отвержении теста гомоскедастичности рекомендуется использовать один из нижеперечисленных тестов гетероскедаксичности.
Тест Уайта. Предположим, что гетероскедастичность модели вызвана неявной зависимостью дисперсий ошибок от признаков. Примем гипотезу H0 без каких-либо предположений о структуре гетероскедастичности. Сначала применим к исходной модели метод наименьших квадратов и найдем вектор регрессионных остатков. Затем восстановим регрессию квадратов этих остатков 2 на все признаки, их квадраты, попарные произведения и константу. Тогда при неотвержении гипотезы H0 величина mR2 асимптотически имеет распределение 2 (N 1), где m число элементов выборки, N число признаков второй регрессии а R2 коэффициент детерминации Недостаток этого теста в том, что если гипотеза H0 отвергается, получить зависимость дисперсии регрессионных остатков от независимых переменных невозможно.
Тест Голдфелда-Кванта. Применяется, когда есть предположение о прямой зависимости дисперсии ошибок от одного признака j. Упорядочим множество индексов I i по убыванию признака j, исключим d средних наблюдений (пусть d 31 m), восстановим две независимые регрессии для первых d наблюдений и последних d наблюдений получим регрессионные остатки 1 и 2. Далее вычислим статистику Фишера Если верна гипотеза H0, то F имеет распределение Фишера. Большая величина этой статистики означает, что гипотеза H0 отвергается.
«