Обратные задачи: теория и практика Лекция 4. Задача минимизации при нелинейной регрессии. Новосибирский Государственный Университет Физический факультет Кафедра биомедицинской физики к.ф.-м.н. Юркин М.А. This work is licensed under the Creative Commons Attribution 3.0 Unported License.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.2 План лекции Наличие многих локальных минимумов в общем случае. Алгоритмы поиска глобального минимума: Левенберга-Марквардта, мультистарта, DiRect… Классификация алгоритмов по использованию ими производной от целевой функции. Необходимость исследования целевой функции для конкретной задачи. Проверка применимости используемого алгоритма. Разделяемые параметры

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.3 Общая постановка задачи Если выполнено предположение о нормальности и независимости погрешностей, то всё определяется «суммой квадратов» Зависимость от σ очень простая, и все особенности (и вся нужная информация) содержатся в зависимости S от β, которую обычно тяжело описать. Задача состоит в нахождении (глобального) минимума S(β), т.е. оценки максимального правдоподобия, оценки σ, а также доверительных интервалов на эти величины и значения модельной функции.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.4 Общая постановка задачи При некоторых разновидностях регрессии, минимизируется функции другой структуры, например: Поэтому мы рассмотрим как общие методы минимизации, так и использующие структуру S(β) в виде суммы квадратов.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.5 Квадратичная функция Простейшая функция, имеющая минимум, это квадратичная: y y 0 b T x x T Gx/2, G – положительно определённая матрица. В любой точке градиент и гессиан равны: Определив их в любой точке можно точно найти положение минимума x 0 G 1 x x H 1 g Линейная регрессия сводится к такой функции Многие методы используют квадратичное приближение функции (линейное приближение модели)

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.6 Компоненты итерации Направление движения d Наискорейшего спуска (против градиента): g Спуска: Rg, R – положительно определена Направление Ньютона (из квадратичного приближения): H 1 g Величина шага Поиск в заданном направлении (линейный поиск), (приблизительно) минимизируя y( ) y(x d) Из квадратичного приближения

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.7 Метод наискорейшего спуска Движение против градиента (зелёная линия) сильно неоптимально, когда линии (эллипсы) постоянного уровня сильно вытянуты. Поэтому используются модификации, например, метод сопряжённых градиентов (красная линия) или метод Ньютона (сходится за одну итерацию).

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.8 Алгоритмы локальной минимизации Общие методы Не использующие производные Метод Нельдера-Мида (симплекса, амёбы) Первого порядка Метод сопряжённых градиентов Квазиньютоновские методы Второго порядка Метод Ньютона Модификации метода Ньютона Численное вычисление производных

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.9 Метод Ньютона и модификации Оригинальный Модификации : пробуем 1 и дальше уменьшаем (квадратичная или кубическая интерполяция) Преобразование H, чтобы положительна определена спектральный анализ (обращение знака отрицательных собственных значений) добавление положительно определённой матрицы Метод доверенной области Современные реализации – надёжные и быстросходящиеся методы

Метод доверенной области Минимизируем квадратичную функцию внутри области, размер которой ( Γ n ) увеличивается итерационно Фиксируем размер шага, оптимизируем направление Предполагаем, что минимум достигается при ||p λ || = Γ n, и используем множитель Лагранжа ( λ ) λ – параметр регуляризации. Упрощённые версии контролируют его вместо Γ n (аналогично методу Левенберга-Марквардта) Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.10

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.11 Квазиньютоновские методы Не вычисляет вторые производные. Строит приближение гессиана H по ходу итераций и тут же использует (например, Broyden–Fletcher–Goldfarb–Shanno). В «квазиньютоновском» направлении используется линейный поиск. Для квадратичной функции точный гессиан получается через p 1 итерацию. Рекомендуется, когда вторые производные недоступны или «дороги» для вычисления.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.12 Метод сопряжённых градиентов Направления поиска (примерно) ортогональны друг другу. Для квадратичной функции гарантирована сходимость за p (число параметров) итераций, но примерная сходимость может достигаться намного раньше. Рекомендуется при p 100. Используется также при решении больших систем линейных уравнений.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.13 Метод Нельдера-Мида Начинает с симплекса из p 1 точек. Точка с максимальным f заменяется на симметричную относительно среднего остальных точек. Если точка удачная (минимальная f), то пробуем больший шаг. Если совсем неудачная, то пробуем меньший шаг. В крайнем случае, сжимаем весь симплекс относительно лучшей точки. При вырождении симплекса, алгоритм перезапускается. Работает для негладких функций.

Пример метода Нельдера-Мида Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.14

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.15 Глобальная оптимизация Метод мультистарта. Обход локальных минимумов: Произвольные прыжки + динамика по времени Методы имитации отжига и квантового отжига Метод стохастического туннелирования Спуск с небольшими подъёмами Метод Левенберга-Марквардта Многоточечные методы Генетические, эволюционные и т.п. Исследование всего пространства (DiRect). В общем случае нет гарантии, но уверенность увеличивается со временем вычисления.

Метод имитации отжига На каждом шаге переходим из x в одно из возможных соседних «состояний» x с вероятностью P(y(x),y(x),T) ( T – текущая «температура» системы) Например: T уменьшается от до 0 в соответствии с расписанием отжига. Чем медленнее, тем ближе к 1 вероятность нахождения глобального минимума. Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.16

Генетический алгоритм На каждом шаге работаем с «популяцией» {x 1,…,x n } На основе значений y выбираем (стохастически) часть популяции ( k < n ) Из этой части выбираем случайно «родителей» ( 2 ), которые производят «ребёнка» x = f (x i,x j,…), повторяем n раз Каждый новый элемент подвергается мутации x = x + δ Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.17

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.18 Метод DiRect Новое разделение выбирается с учётом значения функции и размера текущего разбиения. Очень много вычислений, но примерно прописывает всю поверхность целевой функции. Рекурсивно делит пространство параметров, начиная с некоторого гиперкуба.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.19 Алгоритмы локальной минимизации Использующие структуру S(β) в виде суммы квадратов Не использующие производные В основном, численно приближающие производные Первого порядка Метод Гаусса-Ньютона и модификации Метод Левенберга-Марквардта

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.20 Метод Гаусса-Ньютона Гессиан может быть примерно вычислен, используя только Якобиан модельной функции. z – текущая невязка В оригинале матрицей A полностью пренебрегают (проблемы вдали от минимума) d (J T J) 1 J T z = J + z Модификации составляют приближение для A в процессе итераций аналогично квазиньютоновскому методу и выбирают оптимальный шаг в ньютоновском направлении.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.21 Метод Левенберга-Марквардта Наиболее часто используемый метод для нелинейной регрессии. Вместо d (J T J) 1 J T z, d (J T J D) 1 J T z, D – диагональная положительная матрица. Помимо прочего решается проблема плохой обусловленности. динамически изменяется: уменьшается в 10 раз при медленной сходимости, и увеличивается в 10 раз при попадании в (локальный минимум) Гибрид методов Гаусса-Ньютона и наискорейшего спуска.

Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.22 Разделяемые параметры Частично-линейная модель β (β,γ): y(β,γ) X(γ)β + v(γ) Например: y = a + b sin(cx) При фиксированном γ, линейная регрессия: β b(γ). Задача сводится к минимизации M(γ) S(b(γ),γ). Два подхода: Построение метода Гаусса-Ньютона для минимизации M(γ), используя выражение якобиана через X(γ) Упрощение алгоритма общей регрессии используя частичную линейность модели (двухшаговый алгоритм) Если матрица X(γ) имеет неполный ранг, то используется псевдообратная матрица при линейной регрессии

Псевдообратная матрица Определение A + : AA + A = A +, A + AA + = A, (AA + ) T = AA +, (A + A) T = A + A Свойства: Если A обратима, то A + = A 1 Если A T A обратима, то A + = (A T A) 1 A T Всегда В общем случае вычисляется через SVD Проекторы P A = AA + на imA, Q A = I P A перпендикулярно imA P̃ A = A + A на imA T, Q̃ A = I P̃ A перпендикулярно imA T Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.23

Производная от P A и A + Производная P по параметру ( P ) Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.24

Разделяемые параметры Формулы для разделяемых параметров Полное вычисление H дают поправки из первых производных, но ускорение сходимости несущественное Обратные задачи. Лекция 4: Минимизация в нелинейной регрессии.25