avlasov (avlasov) wrote,
avlasov
avlasov

Category:

Туториал по секонд-ордер методам - случай одной переменной

В математической оптимизации, если функция дифферинцируема, то обычно проблему решают взятием производной - градиента в многомерном случае, приравниванием его нулю - и решением полученной системы уравнений, обычно итеративно.
Т.е. типа у нас min f(x), тогда мы считаем градиент g(x), ну и решаем уравнение g(x) = 0. Т.е. оптимизация и нахождение корней уравнений - тесно связанные занятия.
При поиске корней мы также можем использовать информацию о производных g(x) - т.е. вторые производные относительно минимизируемой функции f(x), т.е. Гессиан - матрицу вторых производных в многомерном случае.

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

Итак мы решаем g(x) = 0, где g(x) - производная/градиент минимизируемой функции. Для метода итераций нам нужно преобразовать к виду x=phi(x) (где phi(x) - сжимающее отображение, но опустим подробности).
В случае градиентных методов, юзают x=x-lr(x)*g(x) где lr(x) - learning rate, которая, вообще говоря, может зависеть от x, но в простом случае Gradient Descent является скаляром и от него не зависит (хотя может зависеть от номера итерации). В более сложных случаях lr(x) может быть вообще матрицей, т.е. "поворачивать" градиент в направлении минимума. Но мы пока рассматриваем одномерный случай - прежде всего, чтобы посмотреть картинке :).

В некотором роде, "оптимально" выбрать lr(x) = 1/g'(x) т.е. обратную величину к первой производной от g(x) - и второй производной от мнимизируемой f(x). Уря у нас уже первый секонд-ордер метод, т.е. метод оптимизации, использующй информацию о второй производной, он же Метод Ньютона. Или метод касательных.
Посмотрим почему это так (и заодно когда это не так). Распишем приближение в виде двух членов ряда Тейлора g(x) = g(x0) + g'(x0)*(x-x0), поскольку мы ищем g(x) = 0, то решением будет x = x0 - g(x0)/g'(x0).
Геометрически это можно интерпретировать как апроксимацию производной линией, т.е. касательной, ну а для линейной функции несложно найти пересечение с нулем.

Отмечу что это график производной минимизируемой функции, а не самой минимизируемой функции. И мы ищем точку где производная пересекает ось Х. Если об этом не помнить, то можно немного запутаться :).
С точки зрения оптимизации, можно считать, что мы апроксимируем мнимизируемую функцию параболой f(x) = f(x0) + g(x0)*(x-x0) + g'(x0)*(x-x0)^2/2 ну и формула для минимума параболы находится аналогично.

Но тут есть тонкость - g'(x) должна быть больше нуля, т.е. функция должна быть выпуклой! Иначе мы вместо поиска минимума пойдем вверх. Т.е. lr(x) для минимизации должен быть всегда положителен (а для максимизации - наоборот, отрицательный). Таким образом метод Ньютона хоть и крут (быстро сходится, если все хорошо), но напрямую применим только к выпуклым функциям.
Но, на самом деле, если функция вогнута, то градиентный спуск все равно может работать, просто надо все равно идти в обратную сторону от градиента, т.е. использовать положительную lr. Правда, я лично не в курсе, какой лёрнинг рейт тут будет оптимальный. На практике, например, если функция оказалась невыпуклой и обнаружился восходящий путь (ведущий к максимуму), то делают line seach в обратном направлении. Или можно отрицательные собственные числа сделать положительными. Но об этом несколько позже.

Вобщем и целом отметим, что любой положительный лёрнинг рейт будет вести в сторону минимума, но в случае выпуклой функции, оптимальным будет lr = 1/g'(x) = 1/f''(x) (понятно что можно и третью произвдную юзать и она может дать еще более крутую сходимость, но это уже скорее теория :)). Собственно, обобщение этого на многомерный случай плюс всякие вариации и дает нам секонд ордер методы.

Рассмотрим еще такую вариацию, которая не требует вычисления второй производной минимизируемой функции (или просто производной, если мы ищем корень уравнения) - Метод хорд/секущих.
Собственно, все примерно так же, только вместо производной мы используем ее численную апроксимацию g'(x) ~ (g(x1)-g(x0))/(x1-x0), ну и получаем такую формулу итерации x2 = x0 - (x1-x0)/(g(x1)-g(x0))*g(x0). Это удобно тем, что не нужно считать вторую производную, а лишь оценивать ее на основании последовательности g(xi), которые мы и так считаем. Это актуально для многомерных случаев (в которых считать вторую производную может быть крайне накладно) и составляет основу Quasi-Newton методов.
Картинка из википедии для иллюстрации.
Subscribe

  • StatMod и ML

    Рассмотрим, чем полезен StatMod в плане инженерии ML и почему "преподаваемый" ML тут проигрывает. Под "преподаваемым" ML я имею в…

  • Инженерность в DataScience

    Когда я пишу что инженерность в ML слабо развита, это не значит что ее нет вообще. Точнее будет сказать, что в DataScience (некая объемлющая…

  • Основные вопросы в инженерии МЛ

    По своему опыту я выделяю следующие основные вопросы/проблемы, которые возникают при решении практических МЛ задач. Какую задачу мы решаем? Ту ли…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments