Как запустить алгоритм спуска градиента, когда пространство параметров ограничено?

Question

Я хотел бы увеличить функцию с одним параметром.

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

Но есть одна проблема: параметр должен оставаться положительным, поэтому он не должен быть < = 0, потому что моя функция будет неопределенной. Мой поиск градиента иногда попадает в такие регионы, хотя (когда он был положительным, градиент сказал ему идти немного ниже, и он переполняется).

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

Каковы некоторые (простые) алгоритмы, которые касаются этой проблемы с ограниченной проблемой оптимизации? Я надеюсь на простое исправление моего алгоритма. Или, может быть, игнорировать градиент и выполнить поиск линии для оптимального параметра?

Answer 1

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

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

Проблема заключается в том, что ваш локальный максимум не является глобальным (если вы не знаете больше о своей функции, чем обмениваете). Это основное ограничение наивного градиентного восхождения - оно всегда фиксируется на первом локальном максимуме и сходится к нему. Если вы не хотите переключаться на более надежный алгоритм, один простой подход, который может помочь, - запустить n итерации вашего кода, начиная каждый раз из случайных позиций в функциональном пространстве и сохраняя максимальный максимум, который вы найдете в целом , Этот подход Монте-Карло увеличивает вероятность того, что вы наткнетесь на глобальный максимум за счет увеличения времени выполнения в n. Насколько эффективно это будет зависеть от «ухабистости» вашей целевой функции.

Answer 2

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

Answer 3

1. Каждый раз, когда вы обновляете свой параметр, проверьте, не отрицательный ли он, и если это так, закрепите его до нуля.
2. Если зажим на ноль неприемлем, попробуйте добавить «барьер журнала» (Google it). По сути, он добавляет гладкую «мягкую» стену к вашей целевой функции (и модификации вашего градиента), чтобы убрать ее от регионов, в которые вы не хотите. Затем вы повторно выполняете оптимизацию, закаляя стену, чтобы сделать ее более бесконечно вертикальной, но начиная с ранее найденного решения.В пределе (на практике требуется лишь несколько итераций), проблема, которую вы решаете, идентична исходной проблеме с жестким ограничением.

Answer 4

На каждом шаге ограничивайте параметр положительным. Это (короче) метод прогнозируемого градиента , о котором вы можете захотеть.

Answer 5

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

Во-первых, при градиентном спуске/восхождении вы каждый раз перемещаетесь по градиентным временам некоторого коэффициента, который вы называете «коэффициентом скорости обучения». Если, как вы описали, этот шаг заставляет x стать отрицательным, есть две естественные интерпретации: либо градиент был слишком велик, либо коэффициент скорости обучения был слишком большим. Поскольку вы не можете управлять градиентом, возьмите вторую интерпретацию. Убедитесь, что ваш ход приведет к тому, что x станет отрицательным, и если да, уменьшите коэффициент обучения в два раза и повторите попытку.

Во-вторых, чтобы уточнить ответ Анико, пусть x - ваш параметр, а f (x) - ваша функция. Затем определим новую функцию g (x) = f (e^x) и заметим, что хотя область f является (0, бесконечность), область g является (-инфекцией, бесконечностью). Поэтому g не может страдать от проблем, с которыми страдает f. Используйте градиентный спуск, чтобы найти значение x_0, которое максимизирует g. Тогда e^(x_0), положительное, максимизирует f. Чтобы применить градиентный спуск по g, вам понадобится его производная, которая является f '(e^x) * e^x, по цепному правилу.

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

Answer 6

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

Answer 7

Просто используйте Brent's method for minimization. Он стабилен и быстр и правилен, если у вас есть только один параметр. Это то, что использует функция Roptimize. Ссылка также содержит простую реализацию на C++. И да, вы можете указать минимальные значения параметра MIN и MAX.