Бессмысленно использовать алгоритмы оптимизации на основе градиента, если вы можете предоставить только числовой градиент? Если нет, зачем в первую очередь указывать числовой градиент, если для самой библиотеки оптимизации достаточно просто выполнить конечное дифференцирование?
[РЕДАКТИРОВАТЬ]
Просто чтобы уточнить, мой вопрос действительно в более общем смысле, чем конкретное применение. Хотя моя область применения - оптимизация вероятности в различных статистических рамках.
Моя проблема с автоматическим дифференцированием заключается в том, что всегда есть подвох. Либо библиотека AD не может распространяться на вызовы из внешних библиотек (например, BLAS), либо вам приходится переделывать свой рабочий процесс настолько радикально, что ему становится трудно иметь дело ... особенно если вы работаете с языками, чувствительными к типу. Мои проблемы с AD - это отдельная проблема. Но я хочу верить!
Думаю, мне нужно лучше сформулировать свой вопрос, но я плохо справляюсь с этим. Если у вас есть возможность либо использовать алгоритм оптимизации без производных, либо алгоритм оптимизации на основе производных с оговоркой, что я могу дать ему только числовой градиент, какой из них в среднем будет лучше?
источник
Ответы:
В дополнение к отличному ответу Брайана, позвольте мне дать немного (редакционного) фона. Методы оптимизации без производных определяются как методы, использующие только оценки функций, и в основном представляют собой все варианты «более или менее систематической выборки допустимого набора и сохранения наилучшего значения функции» - это все, что вы можете сделать, учитывая информацию. Эти методы можно условно разделить на
Стохастические методы , где выборка выборок является в основном случайной (это означает, что случайность является критическим компонентом; могут существовать другие детерминированные компоненты). Эти методы часто мотивируются физическими или биологическими процессами и имеют соответствующие названия, такие как «имитация отжига», «генетические алгоритмы» или «метод роя частиц / светлячка / муравейника». Существует редко какая-либо теория конвергенции за пределами ", если вы попытаетесь достаточно долго, вы с вероятностью достигнете всех точек (включая минимизатор)1 "(Независимо от того , что произойдет , - с какой - либо вероятностью - до тепловой смерти вселенной другого дела ...) Как математик, я хотел бы рассмотреть эти методы в качестве последнего средства: Если вы не знаете ничего о вашем Функция, это все, что вы можете сделать, и вам может повезти.
Детерминированные методы , где выборка выборок не случайна, т. Е. Основана исключительно на предыдущих оценках функции. Наиболее известным примером является, вероятно, симплекс-метод Нелдера-Мида; другие генерируют множество методов поиска . Важно понимать, что это может работать только в том случае, если существует какое-либо (пригодное для использования) отношение между значением функции в разных точках, т. Е. Некоторая гладкость функции. Фактически, теория сходимости, например, для метода Нелдера-Мида, основана на построении неоднородногоконечно-разностная аппроксимация градиента, основанная на значениях функции в вершинах симплекса и показывающая, что он сходится как к точному градиенту, так и к нулю, когда симплекс сжимается в точку. (Вариант, основанный на стандартном приближении конечных разностей, называется поиском по компасу .)
Методы на основе модели , где значения функции используются для построения локальной модели функции (например, путем интерполяции), которая затем минимизируется с помощью стандартных (на основе градиента / гессиана) методов. Поскольку конечно-разностное приближение эквивалентно точной производной полиномиального интерполятора, классический подход «числовой градиент» также попадает в этот класс.
Как видите, границы между этими классами изменчивы, и зачастую это просто вопрос интерпретации. Но мораль должна быть ясной: убедитесь, что вы используете всю доступную информацию о функции, которую вы минимизируете. Процитирую Корнелиуса Ланцоша:
В конце концов, если вы не знаете ничего о вашей функции, она также может быть совершенно случайной, и свести к минимуму случайного значения является поручением дурака ...
источник
Если ваша цель гладкая, то использование конечно-разностных аппроксимаций для производной часто более эффективно, чем использование алгоритма бесплатной оптимизации с производной. Если у вас есть код, который точно вычисляет производные, то обычно лучше использовать этот код, чем использовать конечно-разностные аппроксимации.
Хотя некоторые библиотеки оптимизации будут вычислять аппроксимации конечных разностей для вас автоматически, используя эвристику для определения параметров размера шага, может быть лучше использовать ваши собственные процедуры для вычисления аппроксимаций конечных разностей либо потому, что вы лучше знаете соответствующие размеры шагов, либо из-за специальная структура в функции, которую может использовать ваш код.
Другой вариант, который часто стоит того, - это использовать методы автоматического дифференцирования для создания подпрограммы, которая вычисляет аналитические производные из исходного кода для вычисления самой целевой функции.
источник
Ваш вопрос спрашивает об оптимизаторах на основе градиента, так что я думаю, что Брайан был прав. Я бы только поделился, поскольку я сам сейчас с этим борюсь, некоторыми вопросами.
Проблемы с конечной разницей заключаются в 1) производительности, потому что вам необходимо заново оценить функцию для каждого измерения, и 2) может быть сложно выбрать хороший размер шага. Если шаг слишком велик, предположение о линейности функции может не выполняться. Если шаг слишком мал, он может столкнуться с шумом в самой функции, потому что производные усиливают шум. Последнее может стать реальной проблемой, если функция включает решение дифференциальных уравнений. Если возможно рассчитать градиенты аналитически или с использованием уравнений чувствительности, это, безусловно, будет более точным и, возможно, более быстрым.
Есть еще один подход, который вы можете попробовать, если вы еще не потратили слишком много времени на программное обеспечение, а именно запустить его со сложной арифметикой. Это называется сложной ступенчатой дифференциацией . Основная идея заключается в том, что, когда вы оцениваете функцию, если вы хотите, чтобы ее градиент относился к параметру X, вы устанавливаете мнимую часть X в очень малое число eps . После того, как вы выполните вычисления, мнимая часть значения функции, разделенная на eps , будет градиентом по отношению к X. Если вам нужен градиент по отношению к Y, вам, конечно, придется делать все это снова. Что интересного в том, что EPSможно сделать очень маленьким. Причина, по которой он работает, состоит в том, что нормальные правила дифференциального исчисления точно отражены в правилах комплексной арифметики.
Тем не менее, я считаю, что это не панацея, потому что не всегда легко выполнить сложную функцию в сложной арифметике, это не стоит того, чтобы градиент можно было рассчитать аналитически, а в случае дифференциальных уравнений это точно эквивалентно уравнениям чувствительности , который я делаю по мере необходимости.
источник