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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

Answer 6

Просто используйте метод Брента для минимизации . Это стабильно, быстро и правильно, если у вас есть только один параметр. Это то, что использует R функция optimize. Ссылка также содержит простую реализацию C ++. И да, вы можете задать для него значения параметров MIN и MAX.

Answer 7

Вы получаете хорошие ответы здесь.Повторная настройка - это то, что я бы порекомендовал.Кроме того, рассматривали ли вы другой метод поиска, например Metropolis-Hastings ?Это на самом деле довольно просто, когда вы пролистываете страшно выглядящую математику, и это дает вам стандартные ошибки и оптимум.