29

Если гессианы так хороши для оптимизации (см., Например , метод Ньютона ), зачем останавливаться на достигнутом? Давайте использовать третий, четвертый, пятый и шестой производные? Почему бы нет?

optimization gradient-descent hessian эхо
источник

11

Если вы нашли оптимальный вариант, зачем смотреть дальше? В самом деле, что вы действительно пытаетесь спросить? Какой у вас статистический вопрос?

whuber

2

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

AdamO

3

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

Владислав Довгальец

6

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

Аксакал

11

Вы не сделали научный прорыв. Галлея победил тебя примерно на 3 1/4 века. Halley, E., 1694, «Новый, точный и простой метод нахождения корней любых уравнений вообще и без предварительного сокращения» Филос. Сделка Рой. Soc. Лондон, 18, 136–145. Методы 3-й производной для оптимизации существуют и изучаются в течение многих лет, но не достигли большой популярности. При правильной реализации их наибольшим преимуществом может быть повышение надежности по сравнению с хорошо реализованным методом Ньютона. Это может быть полезно для самых неприятных проблем.

Марк Л. Стоун

31

Я интерпретирую вопрос так: «Почему в методе Ньютона используются только первые и вторые производные, а не третьи или более высокие производные?»

На самом деле, во многих случаях переход к третьей производной действительно помогает; Я сделал это с пользовательскими вещами раньше. Однако, в целом, переход к более высоким производным добавляет вычислительную сложность - вы должны найти и рассчитать все эти производные, а для многомерных задач третьих производных гораздо больше, чем первых! - это намного перевешивает экономию на количестве шагов, которое вы получаете, если таковые имеются. Например, если у меня есть трехмерная задача, у меня есть 3 первых производных, 6 вторых производных и 10 третьих производных, поэтому переход к версии третьего порядка более чем удваивает количество вычислений, которые я должен сделать (с 9 до 19), не говоря уже об увеличении сложности вычисления направления / размера шага после того, как я сделал эти оценки, но почти наверняка не сократит количество шагов, которые я должен сделать, вдвое.

Теперь, в общем случае с переменными, коллекция частных производных будет иметь номер , поэтому для задачи с пятью переменными общее число третьих четвертая и пятая частные производные будут равны 231, увеличившись более чем в 10 раз по сравнению с числом первых и вторых частных производных (20). Вам может понадобиться задача, которая очень, очень близка к полиному пятого порядка по переменным, чтобы увидеть достаточно большое сокращение числа итераций, чтобы компенсировать эту дополнительную вычислительную нагрузку. $k$ $n^{th}$ ${k+n-1} \choose {k-1}$

jbowman
источник

3

Не могли бы вы объяснить, как вы используете высшие производные?

whuber

5

@whuber То, на что ссылается ОП, крайне непонятно, должен признать, это метод Ньютона по оптимизации. Вопрос действительно в том, почему в методе Ньютона используются только первые и вторые производные, а не третьи или более высокие производные? Это не по теме, а также непонятно, о чем он / она спрашивает, но я подумал, что просто дам ответ, а не проголосую за закрытие по той или иной причине.

jbowman

4

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

Мэтью Друри

8

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

jbowman

9

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

Jbowman

22

Я на самом деле не вижу статистического аспекта этого вопроса, поэтому я отвечу на часть оптимизации.

Конвергенция состоит из 2 частей: стоимость итерации и количество итераций

Практически каждый ответ здесь фокусируется только на стоимости итерации и игнорирует количество итераций . Но оба они имеют значение. Метод, который повторяется за 1 наносекунду, но требует итераций, чтобы сходиться, вам не поможет. И взрывающийся метод тоже не поможет, независимо от того, насколько дешева его итерация. $10^{20}$

Давайте выясним, что происходит.

Итак: почему бы не использовать> производные 2-го порядка?

Частично потому (и это верно для 2-го порядка, но об этом чуть позже):

Методы более высокого порядка обычно сходятся быстрее только при приближении к оптимальному .

С другой стороны, они легче взрываются, когда находятся дальше от оптимального!

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

Это означает, что когда вы находитесь далеко от оптимума, вы обычно хотите использовать метод низкого порядка (читай: первого порядка). Только когда вы находитесь рядом, вы хотите увеличить порядок метода.

Так зачем останавливаться на 2-м порядке, когда вы находитесь рядом с корнем?

Потому что "квадратичное" поведение конвергенции действительно "достаточно хорошо"!

Чтобы понять почему, сначала вы должны понять, что означает «квадратичная конвергенция» .

Математически, квадратичная сходимость означает, что, если - ваша ошибка на итерации , то в конечном итоге справедливо следующее для некоторой константы : $\epsilon_k$ $k$ $c$

| ϵ_{k + 1} | \leq c | ϵ_{k} |^{2}

$\lvert\epsilon_{k+1}\rvert \leq c\ \lvert\epsilon_{k}\rvert^2$

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

Зачем? Это легко увидеть на примере: для и , то есть , , и т.д. , которые до смешного быстро , (Это супер экспоненциально !) $c = 1$ $\lvert\epsilon_1\rvert = 0.1$ $\lvert\epsilon_2\rvert \leq 0.01$ $\lvert\epsilon_3\rvert \leq 0.0001$

Почему бы не остановиться на первом порядке, а не на втором?

На самом деле, люди часто делают это, когда производные второго порядка становятся слишком дорогими. Но линейная сходимость может быть очень медленной. например, если вы получили то вам понадобится, возможно, 10 000 000 итераций с линейной сходимостью, чтобы получить , но только 23 итерации с квадратичной сходимостью. Таким образом , вы можете видеть , почему существует резкое различие между линейной и квадратичной сходимости. Например, это не так для конвергенции 2-го и 3-го порядка (см. Следующий параграф). $\epsilon_k = 0.9999999$ $\lvert\epsilon\rvert < 0.5$

На этом этапе, если вы знакомы с какой-либо информатикой, вы понимаете, что с конвергенцией 2-го порядка проблема уже решена . Если вы не понимаете почему, вот почему: нет ничего практичного, чтобы выиграть, увеличивая число цифр на каждой итерации вместо того, чтобы удваивать его - что вы будете покупать? В конце концов, в компьютере даже число double-точности имеет точность 52 бита, что составляет около 16 десятичных цифр. Может быть, это уменьшит количество необходимых вам шагов с 16 до 3 ... что звучит замечательно, пока вы не поймете, что это достигается ценой необходимости вычислять третьи производные на каждой итерации, что является проклятием размерностибьет тебя сильно. Для мерной задачи вы просто заплатили коэффициент чтобы получить коэффициент , что немо. И в реальном мире проблемы имеют как минимум сотни измерений (или даже тысяч или даже миллионов), а не просто ! Таким образом, вы получаете коэффициент в 20, заплатив, скажем, 20 000 ... вряд ли разумный компромисс. $6$ $6$ $\approx 5$ $6$

Но опять же: помните, проклятие размерности - это половина истории .

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

Вывод

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

Mehrdad
источник

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

Федерико Полони,

@FedericoPoloni: Да, те же мысли приходили мне в голову, когда я решил вставить его. У меня его не было изначально ... Я подумал, что, может быть, мне следует добавить его как еще один пример того, почему более высокие степени могут иметь неожиданные проблемы. Но я полагаю, что я возьму это снова, если это не поможет, спасибо за комментарий.

Мердад

@FedericoPoloni: PS Пока мы обсуждаем численные вычисления, вам могут быть интересны функции Штурма (если вы о них еще не слышали).

Мердад

7

Даже вычисление гессиана - это довольно трудоемкая работа:

H = [\begin{matrix} \frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}} & \dots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}} \\ \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \dots & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{\partial^{2} f}{\partial x_{n} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}} & \dots & \frac{\partial^{2} f}{\partial x_{n}^{2}} \end{matrix}] .

$H = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$

Теперь посмотрим, как выглядит третья производная: Это трехмерная матрица. Вот как выглядят его элементы:

\partial H / \partial x = [\begin{matrix} \frac{\partial H}{\partial x_{1}} \\ \frac{\partial H}{\partial x_{2}} \\ ⋮ \\ \frac{\partial H}{\partial x_{n}} \end{matrix}]

$\partial H/\partial x=\begin{bmatrix} \dfrac{\partial H}{\partial x_1}\\ \dfrac{\partial H}{\partial x_2}\\ \vdots\\ \dfrac{\partial H}{\partial x_n} \end{bmatrix}$

(\partial H / \partial x)_{i j k} = \frac{\partial^{3} f}{\partial x_{i} \partial x_{j} \partial x_{k}}

$(\partial H/\partial x)_{ijk}=\dfrac{\partial^3 f}{\partial x_i\partial x_j\partial x_k}$

Производная шестого будет шестимерной матрицей:

\frac{\partial^{6} f}{\partial x_{i} \partial x_{j} \partial x_{k} \partial x_{l} \partial x_{m} \partial x_{n}}

$\dfrac{\partial^6 f}{\partial x_i\partial x_j\partial x_k\partial x_l\partial x_m\partial x_n}$

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

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

Аксакал
источник

4

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

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

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

источник

2

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

Лукас Робертс
источник

3

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

x^{2} - y^{2}

$x^2-y^2$

Дирк

@Dirk равно чему?

x^{2} - y^{2}

$x^2-y^2$

Ovi

1

Это квадратичная функция, но не выпуклая и не вогнутая.

Дирк

@ Дирк, да, ты прав, я должен был добавить положительное полуопределенное предупреждение. Я добавлю это к моему ответу.

Лукас Робертс

1

Позвольте мне быть здесь единственным, кто защищает методы 3-го порядка для сходимости SGD, но определенно не во всем пространстве, для чего потребуются коэффициенты 3/6, а, например, только в одном направлении, которому нужен только один дополнительный коэффициент, если уже имея модель 2-го порядка в этом направлении. $\approx dim^3/6$

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

Я полагаю, что мы пойдем к гибридным методам мультипорядка: метод 2-го порядка в низкоразмерном подпространстве, например, из PCA недавних градиентов, который по-прежнему допускает свободный одновременный спуск градиента 1-го порядка к части градиента, ортогонального этому подпространству ... и дополнительно Я бы добавил, например, модель 3-го порядка для одного наиболее актуального направления.

Ярек Дуда
источник

Почему бы не использовать третью производную для численной оптимизации?

Ответы: