WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР СООБЩЕНИЯ ПО ПРИКЛАДНОЙ МАТЕМАТИКЕ В. В. СТРИЖОВ, Е. А. КРЫМОВА МЕТОДЫ ВЫБОРА РЕГРЕССИОННЫХ МОДЕЛЕЙ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР РАН МОСКВА, 2010 УДК 519.584 ...»

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

СООБЩЕНИЯ ПО ПРИКЛАДНОЙ МАТЕМАТИКЕ

В. В. СТРИЖОВ, Е. А. КРЫМОВА

МЕТОДЫ ВЫБОРА РЕГРЕССИОННЫХ МОДЕЛЕЙ

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР РАН

МОСКВА, 2010

УДК 519.584

Ответственный редактор

доктор физ.-матем. наук К. В. Воронцов

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

Основу работы составляет курс лекций, читаемый автором в Московском физико-техническом институте .

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

Рецензенты: A. Г. Дьяконов, Ю. В. Чехович Научное издание c Учреждение Российской академии наук Вычислительный центр им. А. А. Дородницына РАН, 2010

1. Введение Решение практических задач восстановления регрессионной зависимости требует рассмотрения большого числа порождаемых признаков. Процедура построения регрессионных моделей состоит из двух шагов. На первом шаге, на основе свободных переменных результатов измерений порождается набор признаков .



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

Развитие методов отбора признаков в регрессионном анализе имеет насыщенную историю. Среди методов отбора признаков широкое распространение получил шаговый метод, впервые предложенный в 1960 г. М. А. Эфроимсоном [1] На каждом шаге признаки проверяются на возможность добавления признака в модель или возможность удаления из модели. При этом используется F -статистика или критерий Акаике, Байесовский критерий, критерий Маллоуза [2–4] .

В 1963 г. А. И. Тихонов ввел понятие регуляризации дополнительного ограничения на задачу [5]. В работах [6, 7] введено понятие класса регуляризуемых некорректно поставленных задач и обоснован общий метод решения таких задач, названный методом регуляризации .

Работы А. И. Тихонова были опубликованы на западе только в 1977 г. В 1970 г. А. Хоэрл и Р. Кеннард предложили метод гребневой регрессии, в котором использовалась регуляризация [8]. Было введено дополнительное регуляризующее слагаемое в минимизируемый функционал, стало возможным улучшить устойчивость решения [9] .

В первом издании книги Н. Дрейпера 1966 г. [10] приведен ступенчатый алгоритм выбора признаков. На каждой итерации выбирается признак, имеющий наибольшую проекцию на вектор ответов, после этого делается небольшой шаг в направлении решения [11]. Среди полученных на каждом шаге моделей находится оптимальная, тем самым производится отбор признаков .

В 1971 г. А. Г. Ивахненко начал разрабатывать семейство методов группового учета аргументов МГУА [12]. Согласно его подходу на каждом шаге происходит отбор моделей и построение на их основе более сложных моделей [13–15]. Метод позволяет сократить перебор и осуществить отбор признаков .



В книге Д. Холланда 1975 г. [16] рассматривался общий подход к построению адаптивных систем. Любая адаптивная задача может быть представлена в терминах теории эволюции. Задача, сформулированная таким образом, может быть решена с помощью генетического алгоритма, воспроизводящего процессы эволюции. В основе использования генетического алгоритма лежит теорема шим (scheme), из доказательства которой следует, что при определенных условиях алгоритм дает экспоненциально быструю сходимость решения к локальному оптимуму .

В работах С. Шена 1980 г. и 1991 г. [17, 18] рассмотрен алгоритм последовательного добавления признаков с ортогонализацией (Forward Orthogonal search). Отбор признаков происходит автоматически при выборе оптимальной модели [19, 20] .

Для упрощения структуры модели также используется метод оптимального прореживания, согласно которому элементы модели, оказывающие малое влияние на ошибку аппроксимации, можно исключить из модели без значительного ухудшения качества аппроксимации [21–23]. Алгоритм предложен в 1990 г .

А. Н. Горбанем и основан на анализе первых производных в ходе обучения градиентными методами .

Еще один метод регуляризации, Лассо, был предложен Р. Тибширани в 1996 г. [24]. В нем вводится ограничение на L1 норму вектора параметров модели, что приводит к обнулению части параметров модели и улучшению устойчивости решения .

В 2002 г. Б. Эфрон, Т. Хасти, И. Джонстон и Р. Тибширани предложили метод наименьших углов (Least Angle Regression) [25]. Алгоритм заключается в последовательном добавлении признаков. На каждом шаге признак выбирается таким образом, что вектор регрессионных остатков равноуголен уже добавленным в модель признакам [26] .

Перечислим рассмотренные ниже методы отбора признаков:

1) полный перебор моделей [14];

2) генетический алгоритм [27];

3) метод группового учета аргументов [13, 14, 28];

4) шаговая регрессия [10, 1, 29];

5) гребневая регрессия [10];

6) алгоритм Лассо [24];

7) ступенчатая регрессия [10];

8) последовательное добавление признаков с ортогонализацией [17, 18];

9) метод наименьших углов LARS [25];

10) оптимальное прореживание в линейной регрессии [21, 22];

11) метод моделей наибольшей обоснованности .

Основная проблема, возникающая при порождении признаков проблема мультиколлинеарности. Термин мультиколлинеарность введен Р. Фришем при рассмотрении линейных зависимостей между признаками [30]. Мультиколлинеарность проявляется в сильной корреляции между двумя или более признаками, что затрудняет оценивание параметров модели. Мультиколлинеарность называют полной, если существует функциональная зависимость между всеми признаками. При этом становится невозможно однозначно оценить параметры модели. На практике встречаются случаи частичной мультиколлинеарности, когда имеется высокая степень корреляции между некоторыми признаками. Тогда решение получить можно, однако оценки параметров модели и их дисперсии могут быть неустойчивы. Увеличиваются дисперсии оценок и абсолютные значения регрессионных параметров, что усложняет их интерпретацию .





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

Рассмотрим основные способы обнаружения мультиколлинеарности: проверка корреляции между признаками [10], исследование факторов инфляции дисперсии (Variance Ination Factor) [31], метод Белсли [32] .

Пусть X матрица признаков, столбец в которой cоответствует значениям признака при различных измерениях.

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

(xi 1i )T (xj 1j ) x x ij =, xi 1i xj 1j x x где xi, xj cтолбцы X, xi, xj среднее значения соответствующих признаков, 1 столбец из единиц, число которых равно числу признаков, см. [33]. В случае центрированных и нормированных признаков ij = xT xj .

i Допустимым уровнем значимости называется минимальный уровень, вычисленный для данного значения статистики (значения коллинеарности преобразуются к t-статистике с m 2 степенями свободы), в случае выполнения гипотезы неколлинеарности признаков .

Если задан некоторый уровень значимости и вычисленные допустимые уровни значимости pij меньше заданного, то cчитается, что мультиколлинеарность велика. При этом следует помнить, что такие значения не обязательно являются следствием мультиколлинеарности .

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

Обозначим вектор параметров линейной регрессии и 2 дисперсию регрессионных остатков при условии их гомоскедастичности. Значение фактора VIF определим как VIFi = 2, 1 Ri где Ri коэффициент детерминации, вычисленный для i-го признака .

xi f (x1,..., xi1, xi+1,..., xn ) Ri = 1, xi 1i 2 x где f (x1,..., xi1, xi+1,..., xn ) приближение i-го признака, полученное регрессией всех признаков, кроме i-го на i-й признак, средние значения i-го признака. Дисперсия параметров xi

–  –  –

Наличие мультиколлинеарности определяется по значениям VIF. Если VIFi 10, то считается [34], что мультиколлинеарность велика .

В данной работе при исследовании мультиколлинеарости авторы используют метод Белсли. Пусть матрица признаков X имеет размерность m n, центрирована и нормирована. Проводится сингулярное разложение [35–39] матрицы X,

–  –  –

где U,V ортогональные матрицы размерностью соответственно m m и n n и диагональная матрица с элементами (сингулярными числами) на диагонали, такими что

–  –  –

где qij отношение соответствующего слагаемого в разложеV( ) ко всей сумме. Наличие мультиколлинеарности нии i определяется по таблице: большие величины i означают, что возможно есть зависимость между признаками. Большие значения qij в соответствующих строках относятся к признакам, между которыми эта зависимость существует. Маленькие величины i также исследуются: между признаками, соответствующими большим значениям qij, зависимости не существует .

Основными методами устранения мультиколлинеарности являются либо выбор признаков, либо введение ограничений на параметры модели [40, 41] .

В данной работе предлагается компромиссный вариант алгоритма выбора регрессионных моделей. Его целью является получение наиболее адекватной и одновременно с этим наименее мультиколлинеарной модели. Он заключается в последовательном порождении моделей наибольшей обоснованности и основан на работах по связаному Байесовскому выводу и порождающему походу к оценке параметров моделей [42–46]. При этом значения обоснованности различных моделей сравниваются. Выставляется порог интересующего нас значения правдопободия. В процессе порождения модели модифицируются таким образом, что при добавлении признаков уменьшается сумма квадратов регрессионных остатков, а при удалении признаков уменьшается мультиколлинеарность модели .

Результаты сравнения алгоритмов приведены в таблице. Сравнение выполнялось на задаче поиска модели волатильности опционов. Использовались исторические данные торгов опционом Brent Crude Oil [47]. В таблицу входят значения функционала качества на обучающей и контрольной выборке, информационный критерий Акаике, число переменных модели. Исходя из значений критериев делается вывод об эффективности работы алгоритмов .

2. Постановка задачи Задана выборка D = (xi, y i ) m множество m пар, соi=1 стоящих из вектора значений n свободных переменных xi = (xi )n Rn, и значения одной зависимой переменной y i R1 .

j j=1 Индекс i объектов и индекс j свободных переменных далее будем рассматривать как элементы множеств i I = {1,..., m} и j J = {1,..., n} .

Дополнительно задано разбиение выборки I = L C на обучающую и контрольную. Для каждого набора данных, рассматриваемого в вычислительном эксперименте, наборы индексов L, C определены до начала эксперимента .

Задан класс регрессионных моделей F = {fs } параметрических функций, линейных относительно параметров,

–  –  –

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

Предлагается следующий способ порождения признаков выборки D. Задано множество свободных переменных (измеряемых признаков) = {u }U u=1 и конечное множество функций

–  –  –

Переменные xj поставлены в однозначное соответствие мономам полинома. Выражение (1) являются частным случаем выражения (4) для фиксированной модели с индексом s .

Для удобства описания алгоритмов выбора признаков обозначим вектор-столбец xj = x1,..., xm и y = y 1,..., y m Тогда j j

–  –  –

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

1. Орграф i является ациклическим .

–  –  –

Параметры каждой модели настраиваются методом наименьших квадратов по обучающей выборке. Наилучшая модель выбирается исходя из минимума ошибки на контрольной выборке. Для упрощения описания множества признаков введем переменную выбора монома вектор c = (c1,..., cn ). Его элемент cj {0, 1} принимает значение 1, если j Js, в противном случае 0. Тогда любая модель из (6) будет иметь вид y = cj j xj. При больших jJs R время работы алгоритма недопустимо велико .

–  –  –

4. Каждая модель из полученного множества с вероятностью P2 подвергается мутации: случайным образом из множества {1,..., n} выбирается индекс переменной выбора j .

В результате операции значение компоненты cj меняется на противоположное (если был выбран элемент cj = 0, то после операции он меняет свое значение на 1 и наоборот) .

После операций 3 и 4 новые модели настраиваются исходя из услоdef вия минимизации критерия (3) при X = L. Операция производятся заданное число раз .

3.3. Метод группового учета аргументов Алгоритмы МГУА воспроизводят схему массовой селекции, согласно которой последовательно порождаются и выбираются модели возрастающей сложности. При этом используются критерии, предложенные в рамках МГУА. Внутренним называется критерий (3), использующий только обучающую выборку XL. Внешним называется критерий, использующий тестовую выборку XC, при этом предполагается, что параметры модели настроены на обучающей выборке [13] .

Предложены следующие внешние критерии .

1. Критерий регулярности сумма квадратов ошибок на контрольной выборке:

2 (C) = yC XC L 2 .

–  –  –

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

–  –  –

Рис. 1. Вид графиков функций внешнего и внутреннего критериев SC и SL в зависимости от числа параметров модели n На каждом шаге алгоритма происходит порождение моделей .

Модели настраиваются из условий минимизации внутреннего критерия. Затем выбираются P лучших моделей согласно внешнему критерию. Обозначим линейную комбинацию признаков как f (x1, x2 ) = 1 x1 +2 x2, где 1, 2 коэффициенты модели. Верхним индексом зависимой переменной обозначается номер шага .

Порождение моделей происходит следующим образом .

Первый шаг селекции состоит из моделей, являющихся линейАлгоритм шаговой регрессии заключается в последовательном добавлении и удалении признаков при проверке значимости уже добавленных ранее признаков. Начальным набором является пустой набор индексов признаков A =. Добавляется несколько признаков, пока значение критерия на шаге не станет меньше заданного F1, затем из набора A удаляются признаки, значение частного F -критерия (8) для которых не превосходит заданного значения F2 .

Останов алгоритма производится при достижении минимума, заданного критерием Маллоуза Cp :

S + 2k m, Cp = M SE где M SE = S среднеквадратичная ошибка, вычисленная для n модели, настроенной с помощью метода наименьших квадратов на всем множестве признаков, k сложность модели. Критерий штрафует модели с большим числом признаков. Минимизация критерия позволяет найти множество, состоящее из значимых признаков .

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

–  –  –

0.2 0.2 0.4 Рис. 3. Оценки коэффициентов регрессии, полученные с помощью алгоритма гребневой регрессии в зависимости от коэффициента регуляризации В [49] приводится другой способ регуляризации = (1 )+ (D ), где D диагональная матрица, значения в которой диагональные элементы матрицы .

На рис. 2 показано пространство параметров модели. Критерий S квадратичная функция относительно параметров, поэтому кривая S = const является эллипсоидом. Регуляризирующий параметр, отличный от нуля, задает сферу в этом пространстве. Точка касания эллипсода сферой является решением нормального уравнения при фиксированном. При этом касание эллипсоида в нулевой точке исключено и обнуления параметров модели не происходит. Метод улучшает устойчивость параметров регрессионной модели, но не приводит к обращению в ноль ни одного из них .

–  –  –

Таким образом, начальная задача с n переменными и 2n ограничениями может быть преобразована в новую задачу с 2n переменными, но меньшим числом ограничений (2n + 1) .

На рис. 2 показано пространство параметров модели. Кривая S = const является эллипсоидом. Параметр t, отличный от нуля, задает многомерный октаэдр в этом пространстве. Точка касания эллипсода и октаэдра является решением нормального уравнения при фиксированном t. При касании сферы и ребра октаэдра происходит обнуление коэффициента .

3.7. Ступенчатая регрессия Алгоритм ступенчатой регрессии состоит в последовательном добавлении признаков, наиболее коррелирущих с вектором регрессионных остатков .

Начальный набор признаков пуст, вектор остатков r0 = y .

Рассмотрим k-й шаг алгоритма. Сначала находится признак, корреляция которого с вектором остатков максимальна

–  –  –

где достаточно маленькое число. Выбор большого, то есть |rT xi | = xi 2, приводит к обычному алгоритму последовательного k добавления признаков Add .

Процесс продолжается, пока значение критерия (3) не будет незначительно изменяться за шаг .

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

Это приводит к большим вычислительным затратам, но и к более тщательному отбору признаков .

3.8. Добавление признаков с ортогонализацией Метод последовательного добавления признаков с ортогонализацией (Forward Orthogonal Search) основан на ортогонализации признаков-столбцов матрицы X. Ортогонализация делает возможным вычисление индивидуального вклада каждого признака в вектор значений зависимой переменной. Ортогонализация матрицы X может быть произведена с помощью процедур ортогонализации Грамма-Шмидта или Хаусхолдера. Метод состоит в последовательном добавлении признаков с процедурой ортогонализации .

Запишем ортогональное разложение матрицы

–  –  –

Алгоритм последовательно добавляет признаки за n шагов .

Алгоритм FOS за счет нахождения ортонормированного базиса в пространстве признаков позволяет отбирать наименее коррелированные признаки. FOS, как и Add, делает максимальные шаги в выбираемом направлении .

3.9. Метод наименьших углов На каждом шаге алгоритма LARS (Least Angle Regression) происходит изменение вектора параметров модели так, чтобы доставить добавляемому признаку наибольшую корреляцию с вектором регрессионных остатков .

LARS последовательными шагами строит оценку коэффициентов. На k-м шаге только k элементов вектора отличны от нуля. Алгоритм последовательно вычисляет приближение зависимой переменной µ = X .

Для приближений используется вектор корреляций столбцов матрицы X с вектором остатков y µ:

–  –  –

Здесь uk вектор единичной длины, вычисляемый следующим образом. Пусть A подмножество индексов {1,..., n} столбцов xj матрицы X. Это подмножество задает матрицу

–  –  –

Найдем текущий набор индексов A, соответствующих признакам с наибольшими абсолютными значениями корреляций C = maxj=1,...,n |cj | и A = {j : |cj | = C} .

Пусть sj = sign(cj ) для j A. Построим матрицу XA, вычислим AA. Вычислим вектор uA и вектор скалярных произведений

–  –  –

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

–  –  –

Процедура повторяется до тех пор, пока значение ошибки (3) не превзойдет заранее заданное .

Рис. 9. Пример, иллюстрирующий последовательность выбора признаков

3.11. Модели наибольшего правдоподобия Для иллюстрации основного недостатка алгоритма LARS рассмотрим следующий пример. Пусть матрица X состоит из cтолбцов значений трех признаков. Первый признак x1 хорошо коррелирует с вектором ответов y, который является линейной комбинацией остальных двух признаков x2 и x3. Например, как показано на рис. 9, X = [x1, x2, x3 ] = 1 0 1, y = 1 .

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

Предлагаемый алгоритм использует счетное число порождаемых признаков при отыскании линейной регрессионной модели .

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

Используем два набора признаков: порожденный набор Z и текущий набор C. В начале работы алгоритма C = .

Рассмотрим k-й шаг алгоритма .

1. Последовательно, методом Add, добавляются признаки из объединенного набора C Z в активный набор признаков Ak. Итерации повторяются до тех пор, пока при увеличении сложности модели правдоподобие модели не будет меньше заданного порогового Emin .

2. Выполняется прореживание модели: последовательно удаляются те элементы линейной комбинации, заданной набором Ak, для которых критерий мультиколлинеарности Белсли принимает максимальное значение. Прореживание модели продолжается до тех пор пока, при уменьшении сложности модели, правдоподобие не будет меньше порогового Emin .

Коэффициенты полученной модели пересчитываются .

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

Пороговое правдоподобие вычисляется следующим образом .

def Обозначим p() = p(|f ) априорное распределение параметdef ров модели. Рассмотрим функцию правдоподобия p(D|, f ) = p(y|{xj }n,, f ) условную плотность распределения случайj=1 ной величины при заданном векторе параметров .

При отыскании вектора параметров вместо максимизации функции правдоподобия p(D|, f ) будем максимизировать апостериорное распределение параметров

–  –  –



в котором правдоподобие моделей p(D|fi ) определяется выражением (15). Будем считать априорную вероятность равной для всех моделей, p(fi ) = p(fj ). Так как знаменатель выражения (18) не зависит от выбора модели, то сравнение моделей происходит через вычисление правдоподобие моделей с помощью формул (16) и (17). Порог Emin вычисляется как mini=1,...,M p(D|fi ) для набора из M моделей, имеющих максимальное правдоподобие. Параметр M задан .

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

4. Байесовский вывод при выборе моделей

4.1. Сравнение моделей Воспользуемся двухуровневым Байесовским выводом для оценки степени предпочтения порождаемых регрессионной моделей. Рассмотрим конечное множество моделей f1,..., fM, приближающих данные D, обозначим априорную вероятность i-й модели P (fi ). При появлении данных апостериорная вероятность модели P (fi |D) равна

–  –  –

где p(D|fi ) функция правдоподобия моделей, определяющая, насколько хорошо модель fi описывает данные D. Знаменатель дроби обеспечивает выполнение условия M P (fi |D) = 1 .

i=1 Сравним две модели с помощью апостериорных вероятностей

–  –  –

Левая часть выражения называется отношением правдоподобия моделей. Отношение P (fi )/P (fj ) называется отношением апостериорных предпочтений моделей. Полагая априорные вероятности моделей одинаковыми, используем функции правдоподобия для выбора моделей .

Так как рассматриваемые модели f зависят от настраиваемых параметров, представим правдоподобие моделей в виде интеграла по пространству параметров

–  –  –

Рассмотрим вектор параметров модели как многомерную случайную величину w. Пусть плотность распределения параметров имеет вид многомерного нормального распределения N (0, A) c матрицей ковариации A,

–  –  –

4.2. Сравнение элементов моделей Предлагается итеративно найти параметры и гиперпараметры модели по отдельности. На каждой итерации сначала при фиксированных гиперпараметрах отыскиваются параметры путем оптимизации функционала (30). Используется алгоритм ЛевенбергаМарквардта. Затем по формулам, предложенным ниже, вычисляются гиперпараметры .

Предположим, что после очередного шага итерации нам известен локальный максимум (30) и он находится в точке w0. Для нахождения гиперпараметров приблизим (29) методом Лапласа .

Для этого построим ряд Тейлора второго порядка логарифма числителя (29) в окрестности w0 :

ln exp(S(w)) = ln exp(S(w0 ) + wT Hw + o(||w||3 )), (31) где w = w w0. При упрощении и отбрасывании пренебрежимо малой величины получается S(w) S(w0 ) wT Hw. (32) В выражении (32) нет слагаемого первого порядка, так как предполагается, что w0 доставляет локальный минимум функции ошибки S(w) = 0 .

w w=w0 Матрица H матрица Гессе функции ошибок

–  –  –

циона полгода. Тип опциона право на продажу базового инструмента, символ CLG01. Базовый инструмент нефть, символ NYM. Использовались ежедневные цены закрытия опциона и базового инструмента. Сетка цен исполнения опциона K = {1400, 1425,..., 1575, 1600} .

Регрессионная выборка

–  –  –

была построена по исходным данным историческим ценам опциона CK,t и базового инструмента Pt, где K K, t T, следующим образом. Для каждого значения Ki и ti, i = 1,..., m вычислялось значение предполагаемой волатильности i :

–  –  –

где справедливая цена опциона C вычислена по формуле БлэкаШоулза [51]. Длина истории составляет 314 отсчетов времени .

Задано множество порождающих функций G = 1/x, x, ln(x), tanh(x). Максимальная степень полинома Колмогорова-Габора равна трем. Регрессионная выборка была Рис. 10. Полученная модель зависимости исторической предполагаемой волатильности от цены и времени до исполнения случайным образом разбита на контрольную и обучающую, равные по мощности. Значения ошибок на обучении и контроле были усреднены по 10 запускам алгоритмов на различных разбиениях .

Результаты экспериментов показаны в табл. 3. Для каждого алгоритма вычислялись ошибки SL и SC на обучении и контроле (3), значение информационных критериев Акаике

–  –  –

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

5.2. Моделирование давления в двигателе Работа алгоритма проиллюстрирована на примере данных измерения давления в двигателе внутреннего сгорания. Выборка состоит из набора временных рядов измерений давления в камере внутреннего сгорания дизельного двигателя. Каждый временной ряд соответствует одному полному циклу работы двигателя, который состоит из рабочего и холостого тактов. Отчеты временного ряда равномерны и соответствуют углу вращения коленчатого вала. Нулевому углу соответствует верхняя мертвая точка вращения. Начало временного ряда соответствует углу в 360 градусов, конец углу в +359.9 градусов. Всего один полный цикл насчитывает 7200 отсчетов. Лабораторный эксперимент включал измерения давления 122 полных циклов .

Регрессионная выборка ( i, y i ) m m = ( n i, i, P i ) i=1 i=1 состоит из значений независимых переменных ni номера измерения и i угла вращения коленчатого вала. Каждой паре значений ni и i, i = 1,..., m, соответствует значение давления Pi в камере внутреннего сгорания .

Задано множество порождающих функций G = (xmi )2 1/x, (|x|), exp( 2s2 ), sin(ci x). Регрессионная выборка i была случайным образом разбита на контрольную и обучающую, равные по мощности. Вычислялось значение оценки скользящего контроля CV для фиксированных 10 разбиений выборки .

Результаты экспериментов показаны в табл. 3. Кроме оценки скользящего контроля вычислялись значение информационного

–  –  –

5.3. Контроль состояния трубопроводов Еще одна постановка задачи из области контроля качества состояния трубопроводов. Заданы координаты окружности (сечения трубы) множество точек {(x, y)}, измеренных с некоторой погрешностью. Требуется найти центр (c1, c2 ) и радиус r окружности .

Запишем регерссионную модель координаты окружности относительно центра и радиуса и выделим линейно входящие комРис. 11. Полученная модель зависимости исторической предполагаемой волатильности от цены и времени до исполнения

–  –  –

Аналогичным путем получаются решения задач нахождения параметров эллипсоида, параллелограмма и других геометрических фигур .

5.4. Прогнозирование и авторегрессия Рассмотрим постановку задачи прогнозирования временного ряда с выраженной периодической составляющей. Для прогноза используются скрытые регрессионные переменные .

Дан временной ряд x = [x1,..., xT ]T, x R1 .

• Предполагается, что отсчеты времени сделаны через равные промежутки. Следовательно, отсчеты времени t можно без потери общности заменить на индексы элементы натурального ряда .

• Предполагается, что ряд имеет периодическую составляющую и длина периода k известна .

• Предполагается, что ряд, возможно, имеет пропущенные значения .

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

–  –  –

6. Заключение Рассмотренные алгоритмы можно разделить на группы: алгоритмы последовательного добавления или удаления признаков (FOS, LARS, Add, ступенчатая регрессия), алгоритмы с введением ограничения на функционал качества (гребневая регрессия и Лассо), алгоритмы перебора моделей (МГУА, генетический алгоритм, полный перебор), алгоритмы добавления и удаления признаков (шаговая регрессия, предложенные методы) .

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

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

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

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

Описанные выше алгоритмы выполнены и протестированы в системе Матлаб и могут быть использованы для решения задач регрессионного анализа. Библиотека алгоритмов находится по адресу http://strijov.com/examples/mdlselection.zip и свободно распространяется на условиях лицензии GNU GPL .

Литература

1. Efroymson M. A. Multiple regression analysis. New York: Ralston, Wiley, 1960 .

2. Hocking R. R. A biometrics invited paper. the analysis and selection of variables in linear regression // Biometric. 1976. Vol. 32, no. 1. Pp. 1–49 .

3. Akaike H. A bayesian analysis of the minimum aic procedure // Ann. Inst. Statist. Math. 1978. Vol. 2, no. 30. Pp. 9–15 .

4. Mallows C. L. Some comments on Cp // Technometrics. 1973 .

Vol. 15. Pp. 661–675 .

5. Ильин В. А. О работах А. Н. Тихонова по методам решения некорректно поставленных задач // Математическая жизнь в СССР и за рубежом. 1966. Т. 1. С. 168–175 .

6. Тихонов A. Н. О решении некорректно поставленных задач и методе регуляризации // Доклады академии наук СССР .

1963. Т. 151. С. 501–504 .

7. Тихонов А. Н., Арсенин В.. Методы решения некорректных задач. М.: Наука, 1986. 284 с .

8. Hoerl A. E., Kennard R. W. Ridge regression: Biased estimation for nonorthogonal problems // Technometrics. 1970. Vol. 3, no. 12. Pp. 55–67 .

9. Bjorkstrom A. Ridge regression and inverse problems: Tech. rep.:

Stockholm University, Sweden, 2001 .

10. Draper N. R., Smith H. Appied Regression Analysis. John Wihley and Sons, 1998 .

11. Hastie T., Taylor J., Tibshirani R., Walther G. Forward stagewise regression and the monotone lasso // Electronic Journal of Statistics. 2007. Vol. 1, no. 1. Pp. 1–29 .

12. Стрижов В. В. Методы индуктивного порождения регрессионных моделей. М.: Вычислительный центр им. А. А. Дородницна РАН, 2008. С. 54 .

13. Malada H. R., Ivakhnenko A. G. Inductive Learning Algorithms for Complex Systems Modeling. CRC Press, 1994. 368 pp .

14. Ивахненко А. Г., Степашко В. С. Помехоустойчивость моделирования. Киев: Наукова думка, 1985. 216 с .

15. Ивахненко А. Г. Индуктивный метод самоорганизации моделей сложных систем. Киев: Наукова думка, 1981. 296 с .

16. Holland J. H. Adaptation in natural and articial systems. University of Michigan Press, 1975 .

17. Chen Y. W., Billings C. A., Luo W. Orthogonal least squares methods and their application to non-linear system identication // International Journal of Control. 1989. Vol. 2, no. 50 .

Pp. 873–896 .

18. Chen S., Cowan C. F. N., Grant P. M. Orthogonal least squares learning algorithm for radial basis function network // Transaction on neural netwark. 1991. Vol. 2, no. 2. Pp. 302–309 .

19. Berghen F. LARS Library: Least Angle Regression Stagewise Library. No. 1. Addision-Wesley, 2005. Pp. 93–102 .

20. Guyon I., Gunn S. Feature extraction: foundation and applications. Springer, 2006 .

21. Стрижов В. В. Поиск параметрической регрессионной модели в индуктивно заданном множестве // Журнал вычислительных технологий. 2007. Т. 1. С. 93–102 .

22. Хайкин С. Нейронные сети, полный курс. М: Вильямс, 2008 .

1103 с .

23. LeCun Y., Denker J., Solla S., Howard R. E., Jackel L. D. Optimal brain damage // Advances in Neural Information Processing Systems II / Ed. by D. S. Touretzky. San Mateo, CA: Morgan Kauman, 1990 .

24. Tibshirani R. Regression shrinkage and selection via the lasso // Journal of the Royal Statistical Society. 1996. Vol. 32, no. 1 .

Pp. 267–288 .

25. Efron B., Hastie T., Johnstone I., Tibshirani R. Least angle regression // The Annals of Statistics. 2004. Vol. 32, no. 3. Pp. 407– 499 .

26. Lawson L., Hanson R. J. Solving Least Squares Problems. Englewood Clis: Prentice Hall, 1974 .

27. Goldberg D. E. Genetic algirothms in search, optimization, and machine learning. Addison-Wesley, 1989 .

28. Шитиков В. К., Розенберг Г. С., Зинченко Т. Д. Количественная гидроэкология: методы системной идентификации .

Тольятти: ИЭВБ РАН, 2003. 463 с .

29. Rawlings J. O., Pantula S. G., Dickey D. A. Applied Regression Analysis: A Research Tool. New York: Springer-Verlag, 1998 .

30. Frisch R. Statistical Conuence Analysis by means of complete regression systems. Universitetets Okonomiske Institutt, 1934 .

192 pp .

31. Marquardt D. W. Generalized inverses, ridge regression, biased linear estimation, and nonlinear estimation // Technometrics .

1996. Vol. 12, no. 3. Pp. 605–607 .

32. Belsley D. A. Conditioning Diagnostics: Collinearity and Weak Data in Reggression. New York: John Wiley and Sons, 1991 .

33. Орлов А. И. Эконометрика. М.: Экзамен, 2002 .

34. Kutner J., Nachtsheim C., Neter. J. Applied Linear Regression Models. McGrow-Holl Irwin, 2004 .

35. Голуб Д., Ван-Лоан Ч. Матричные вычисления. М.: Мир, 1999 .

36. Hogben L. Handbook of linear algebra. CRC Press, 2007 .

37. Jollie I. T. Principal component analysis. Springer, 2002 .

457 pp .

38. Isenmann A. J. Modern multivariate statistical techniques .

Springer, 2008. 734 pp .

39. Рао С. Р. Линейные статистические методы и их применения .

М.: Наука, 1968. 547 с .

40. A A. A., Clark V., May S. Computer-aided multivariate analysis. CRC Press, 2004 .

41. Burnham K., Anderson D. R. Model Selection and Multimodel Inference. Springer, 2002 .

42. Ulusoy I., Bishop C. M. Generative versus discriminative methods for object recognition // CVPR. 2005. Pp. II: 258–265 .

43. Vladislavleva E. J., Smits G. F., den Hertog D. Order of nonlinearity as a complexity measure for models generated by symbolic regression via pareto genetic programming // IEEE Transactions on Evolutionary Computation. 2009. Vol. 13, no. 2. Pp. 333–349 .

44. Bishop C. M. A new framework for machine learning // Computational Intelligence: Research Frontiers, IEEE World Congress on Computational Intelligence, WCCI 2008, Hong Kong. Springer, 2008. Pp. 1–24 .

45. Bishop C. M., Lasserre J. Generative or discriminative? Getting the best of both worlds // In Bayesian Statistics 8 / Ed. by J. M .

e. a. Bernardo. Oxford University Press, 2007. Pp. 3–23 .

46. Zelinka I., Oplatkova Z., Nolle L. Analytic programming – symbolic regression by means of arbitrary evolutionary algorithm // I. J. of Simulation. 2008. Vol. 6, no. 9. Pp. 44–56 .

47. Ширяев А. Н. Основы cтохастической финансовой математики. М: ФАЗИС, 2004. Т. 1 .

48. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2001 .

49. Шурыгин A. M. Прикладная стохастика: робастность, оценивание, прогноз. М: Финансы и статистика, 2000 .

50. Weisberg S. Applied linear regression. New York: Wiley, 1980 .

51. Hull J. C. Options, Futures and Other Derivatives. Prentice Hall, 2000 .

–  –  –






Похожие работы:

«ReBus-2 ReBus-3 Программное обеспечение SonPRG2M.100 арт. 604 00 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ Москва Содержание 1. Общие сведения 1.1. Назначение 1.2 . Состав пакета программного обеспечения 1.3. Установка и запуск программы 1...»

«ПОДХОД К ПОЛУАВТОМАТИЧЕСКОЙ ГЕНЕРАЦИИ АДАПТЕРОВ В ПОСРЕДНИКЕ НЕОДНОРОДНЫХ КОЛЛЕКЦИЙ ЭЛЕКТРОННЫХ БИБЛИОТЕК Осипов М.А Брюхов Д.О. Калиниченко Л.А. Леонтьев И.В. osipov@newtech.ru brd@synth.ipi.ac.ru leonidk@synth.ipi.ac.ru ileon@synth.ipi.ac.ru Институт Проблем Информатики Российской Академии Нау...»

«Санкт-Петербургский государственный университет Математическое обеспечение и администрирование информационных систем Кафедра информатики Лысенко Юлия Олеговна Снятие образа Android с помощью агента Бакалаврская работа Научный руководитель: ст. преп. Губанов Ю.А.Рецензент: ст. преп. Луцив Д.В. Санкт-Петербург SAINT-PE...»

«ДОГОВОР № г. Санкт-Петербург " 2014 года " Закрытое акционерное общество "Петроэлектросбыт", именуемое в дальнейшем "Заказчик", в лице Генерального директора Горшковой Е.С., действующей на основании Устава, с од...»

«ПРОГРАММНЫЕ СИСТЕМЫ: ТЕОРИЯ И ПРИЛОЖЕНИЯ № 3(3), 2010, c. 93–106 ISSN 2079-3316 УДК 519.687.4 А. А. Кузнецов, В. А. Роганов Поддержка топологии вычислительного пространства в системе OpenTS Аннотация. Эффективное комплексирование массы разрозненных компьютеров и суперкомпьютеров...»

«Социология коммуникаций © 2001 г. Н.В. РОМАНОВСКИЙ СОЦИОЛОГИЯ ЗНАНИЯ-НОВЫЕ ВЫЗОВЫ РОМАНОВСКИЙ Николай Валентинович заместитель главного редактора журнала Социологические исследования. Среди обсуждаемых (в том числе в журнале Социологические исследования) грядущих крупных изменений во многи...»

«1 УДК 004(075.3=161.3=161.1) ББК 32.81я721 П88 Пупцев, А. Е. Мультимедиа в современной жизни: 11-й кл. : пособие П88 для учащихся учреждений общ . сред. образования с белорус. и рус. яз. обучения / А. Е. Пупцев, А. А. Козинский. — 2-е изд. — Минск : Адукацыя і выхаванне, 2014. — 68 с. : ил. — (Информатика. Факульта...»

«ПРОЕКТИРОВАНИЕ, СОЗДАНИЕ И НАПОЛНЕНИЕ ЭЛЕКТРОННОГО АРХИВА С.В.Антюфеев, А.Г.Марчук, А.Н.Немов, К.В.Федоров, В.Э.Филиппов, М.Я.Филиппова, Н.А.Черемных Институт систем информатики им. А.П.Ершова СО РАН, Новосибирск 630090...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.