Как выполнить алгоритм спуска градиента, когда пространство параметров ограничивается?
Я хотел бы максимизировать функцию с одним параметром.
Таким образом, я выполняю спуск градиента (или, подъем на самом деле): Я запускаю с начального параметра и продолжаю добавлять градиент (времена некоторый фактор темпа обучения, который становится меньшим и меньшим), переоцените градиент, учитывая новый параметр, и так далее до сходимости.
Но существует одна проблема: Мой параметр должен остаться положительным, таким образом, он, как предполагается, не становится <= 0, потому что моя функция будет не определена. Мой поиск градиента будет иногда входить в такие регионы, хотя (когда это было положительно, градиент сказал ему идти немного ниже, и это промахивается).
И ко всем неприятностям, градиент в такой точке мог бы быть отрицательным, управляя поиском к еще более отрицательным значениям параметров. (Причина состоит в том, что целевая функция содержит журналы, но градиент не делает.)
Каковы некоторые хорошие (простые) алгоритмы, которые имеют дело с этой ограниченной проблемой оптимизации? Я надеюсь на просто простую фиксацию к своему алгоритму. Или, возможно, проигнорируйте градиент, и некоторая строка ищут оптимальный параметр?
7 ответов
Простой способ ограничить параметр положительным значением - это заново параметризовать задачу с помощью логарифма (не забудьте изменить градиент соответствующим образом). Конечно, возможно, что при этом преобразовании оптимум переместится в -infty, и поиск не сойдется.
- Каждый раз, когда вы обновляете параметр, проверяйте его отрицательное значение, а если отрицательный, фиксируйте его до нуля.
- Если ограничение до нуля недопустимо, попробуйте добавить «лог-барьер» (погуглите). По сути, он добавляет гладкую «мягкую» стену к вашей целевой функции (и изменяет ваш градиент), чтобы держать ее подальше от областей, в которые вы не хотите попадать. Затем вы повторно запускаете оптимизацию, укрепляя стену, чтобы сделать ее более бесконечно вертикальной, но начиная с ранее найденного решения. В пределе (на практике требуется всего несколько итераций) решаемая проблема идентична исходной задаче с жестким ограничением.
На каждом шаге ограничивайте значение параметра положительным значением. Это (вкратце) метод прогнозируемого градиента , о котором вы, возможно, захотите погуглить.
Здесь вы получите хорошие ответы. Я бы порекомендовал изменить параметры. Кроме того, рассматривали ли вы другой метод поиска, например Метрополис-Гастингс ? На самом деле это довольно просто, если вы пробудете устрашающую на вид математику, и она дает вам стандартные ошибки, а также оптимальные значения.
У меня есть три предложения, в порядке возрастания количества размышлений и работы, которую вы хотите проделать.
Во-первых, при градиентном спуске/подъеме вы каждый раз перемещаетесь по градиенту, умноженному на некоторый коэффициент, который вы называете "коэффициентом скорости обучения". Если, как вы описываете, это перемещение приводит к тому, что 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, чтобы помочь вам в этом.
Не зная больше о вашей проблеме, трудно дать конкретный совет. Ваш алгоритм градиентного восхождения может быть не особенно подходящим для вашего пространства функций. Однако, учитывая, что это то, что у вас есть, вот один твик, который мог бы помочь.
Вы следуете тому, что, как вы полагаете, является восходящим градиентом. Но когда вы двигаетесь вперед по направлению градиента, вы обнаруживаете, что упали в яму с отрицательным значением. Это означает, что поблизости был локальный максимум, а также очень резкий обрыв отрицательного градиента. Очевидное решение - вернуться к предыдущей позиции и сделать меньший шаг (например, в два раза меньше). Если вы все еще падаете, повторите с еще меньшим шагом. И так до тех пор, пока не будет найден локальный максимум на краю обрыва.
Проблема в том, что нет никакой гарантии, что ваш локальный максимум действительно является глобальным (если только вы не знаете о своей функции больше, чем делитесь). Это главное ограничение наивного градиентного восхождения - оно всегда фиксируется на первом локальном максимуме и сходится к нему. Если вы не хотите переходить на более надежный алгоритм, один простой подход, который может помочь, - это запустить n итераций вашего кода, начиная каждый раз со случайных позиций в пространстве функций и сохраняя лучший максимум, который вы находите в целом. Такой подход Монте-Карло повышает вероятность того, что вы наткнетесь на глобальный максимум, ценой увеличения времени выполнения в n раз. Насколько это эффективно, зависит от "неровности" вашей целевой функции.
Просто используйте метод Брента для минимизации . Это стабильно и быстро, и это правильно, если у вас есть только один параметр. Это то, что использует функция R optimize . Ссылка также содержит простую реализацию на C ++. И да, вы можете указать ему минимальные и максимальные значения параметров.