Стохастическая аппроксимация одновременных возмущений - Simultaneous perturbation stochastic approximation

Стохастическая аппроксимация одновременных возмущений (SPSA) - это алгоритмический метод оптимизации систем с множеством неизвестных параметры. Это тип стохастическая аппроксимация алгоритм. В качестве метода оптимизации он подходит для крупномасштабных моделей популяций, адаптивного моделирования, моделирования. оптимизация, и атмосферное моделирование. Многие примеры представлены на сайте SPSA. http://www.jhuapl.edu/SPSA. Обширная недавняя книга по этому вопросу - Bhatnagar et al. (2013). Ранняя статья по этому вопросу - Сполл (1987), а основополагающая статья, содержащая ключевую теорию и обоснование, - Сполл (1992).

SPSA - это метод спуска, способный находить глобальные минимумы, разделяя это свойство с другими методами как имитация отжига. Его главная особенность - аппроксимация градиента, которая требует всего двух измерений целевой функции, независимо от размерности задачи оптимизации. Напомним, что мы хотим найти оптимальное управление ${ displaystyle u ^ {*}}$ с функцией потерь ${ displaystyle J (u)}$:

${ displaystyle u ^ {*} = arg min _ {u in U} J (u).}$

И стохастическая аппроксимация конечных разностей (FDSA), и SPSA используют один и тот же итерационный процесс:

${ displaystyle u_ {n + 1} = u_ {n} -a_ {n} { hat {g}} _ {n} (u_ {n}),}$

куда ${ displaystyle u_ {n} = ((u_ {n}) _ {1}, (u_ {n}) _ {2}, ldots, (u_ {n}) _ {p}) ^ {T}}$представляет ${ displaystyle n ^ {th}}$ повторять ${ displaystyle { hat {g}} _ {n} (u_ {n})}$ оценка градиента целевой функции ${ displaystyle g (u) = { frac { partial} { partial u}} J (u)}$ оценивается в ${ displaystyle {u_ {n}}}$, и ${ Displaystyle {а_ {п} }}$ - последовательность положительных чисел, сходящаяся к 0. Если ${ displaystyle u_ {n}}$ это п-мерный вектор, ${ displaystyle i ^ {th}}$ компонент симметричный Оценка градиента методом конечных разностей:

FD: ${ displaystyle ({ hat {g_ {n}}} (u_ {n})) _ {i} = { frac {J (u_ {n} + c_ {n} e_ {i}) - J (u_ {n} -c_ {n} e_ {i})} {2c_ {n}}},}$

1 ≤i ≤p, куда ${ displaystyle e_ {i}}$ - единичный вектор с единицей в ${ displaystyle i ^ {th}}$место, и ${ displaystyle c_ {n}}$небольшое положительное число, которое убывает с п. С помощью этого метода 2p оценки J для каждого ${ displaystyle g_ {n}}$ необходимы. Ясно, когда п большой, эта оценка теряет эффективность.

Пусть сейчас ${ displaystyle Delta _ {n}}$ - случайный вектор возмущения. В ${ displaystyle i ^ {th}}$ Компонент оценки градиента стохастического возмущения:

СП: ${ displaystyle ({ hat {g_ {n}}} (u_ {n})) _ {i} = { frac {J (u_ {n} + c_ {n} Delta _ {n}) - J (u_ {n} -c_ {n} Delta _ {n})} {2c_ {n} ( Delta _ {n}) _ {i}}}.}$

Обратите внимание, что FD возмущает только одно направление за раз, в то время как оценка SP возмущает все направления одновременно (числитель одинаков во всех п составные части). Количество измерений функции потерь, необходимых в методе SPSA для каждого ${ displaystyle g_ {n}}$ всегда равно 2, независимо от измерение п. Таким образом, SPSA использует п раз меньше функциональных оценок, чем FDSA, что делает его намного более эффективным.

Простые эксперименты с р = 2 показали, что SPSA сходится за то же количество итераций, что и FDSA. Последний следует примерно то крутой направление спуска, как в градиентном методе. С другой стороны, SPSA со случайным направлением поиска не следует точно по траектории градиента. Однако в среднем он отслеживает его почти, потому что приближение градиента почти беспристрастный оценка градиента, как показано в следующей лемме.

Лемма о сходимости

Обозначим через

${ displaystyle b_ {n} = E [{ hat {g}} _ {n} | u_ {n}] - nabla J (u_ {n})}$

смещение в оценке ${ displaystyle { hat {g}} _ {n}}$. Предположить, что ${ Displaystyle {( Delta _ {п}) _ {я} }}$ все взаимно независимы с нулевым средним, ограниченными секундными моментами и ${ displaystyle E (| ( Delta _ {n}) _ {i} | ^ {- 1})}$ равномерно ограниченный. потом ${ displaystyle b_ {n}}$→ 0 п.п. 1.

Набросок доказательства

Главный идея использовать кондиционирование на ${ displaystyle Delta _ {n}}$ выражать ${ Displaystyle Е [({ шляпа {g}} _ {п}) _ {я}]}$ а затем использовать разложение Тейлора второго порядка ${ displaystyle J (u_ {n} + c_ {n} Delta _ {n}) _ {i}}$ и ${ displaystyle J (u_ {n} -c_ {n} Delta _ {n}) _ {i}}$. После алгебраических манипуляций с использованием нулевого среднего и независимости ${ Displaystyle {( Delta _ {п}) _ {я} }}$, мы получили

${ displaystyle E [({ hat {g}} _ {n}) _ {i}] = (g_ {n}) _ {i} + O (c_ {n} ^ {2})}$

Результат следует из гипотеза который ${ displaystyle c_ {n}}$→0.

Далее мы возвращаемся к некоторым гипотезам, согласно которым ${ displaystyle u_ {t}}$ сходится в вероятность к множеству глобальных минимумов ${ displaystyle J (u)}$. Эффективность метода зависит от формы ${ displaystyle J (u)}$, значения параметров ${ displaystyle a_ {n}}$ и ${ displaystyle c_ {n}}$ и распределение возмущающих членов ${ displaystyle Delta _ {ni}}$. Во-первых, параметры алгоритма должны удовлетворять следующим условиям:

• ${ displaystyle a_ {n}}$ >0, ${ displaystyle a_ {n}}$→ 0 при n → ∝ и ${ displaystyle sum _ {n = 1} ^ { infty} a_ {n} = infty}$. Хорошим выбором будет ${ displaystyle a_ {n} = { frac {a} {n}};}$ а> 0;
• ${ displaystyle c_ {n} = { frac {c} {n ^ { gamma}}}}$, где c> 0, ${ displaystyle gamma in left [{ frac {1} {6}}, { frac {1} {2}} right]}$;
• ${ displaystyle sum _ {n = 1} ^ { infty} ({ гидроразрыва {a_ {n}} {c_ {n}}}) ^ {2} < infty}$
• ${ displaystyle Delta _ {ni}}$ должны быть взаимно независимыми случайными величинами с нулевым средним, симметрично распределенными относительно нуля, с ${ displaystyle Delta _ {ni}$. Обратные первый и второй моменты ${ displaystyle Delta _ {ni}}$ должно быть конечным.

Хороший выбор для ${ displaystyle Delta _ {ni}}$ это Распределение Радемахера, то есть Бернулли + -1 с вероятностью 0,5. Возможны и другие варианты, но учтите, что нельзя использовать равномерные и нормальные распределения, поскольку они не удовлетворяют условиям конечного обратного момента.

Функция потерь J (u) должен быть трижды непрерывно дифференцируемый а отдельные элементы третьей производной должны быть ограничены: ${ Displaystyle | J ^ {(3)} (и) | <а_ {3} < infty}$. Также, ${ Displaystyle | J (и) | rightarrow infty}$ в качестве ${ Displaystyle и rightarrow infty}$.

Кроме того, ${ displaystyle nabla J}$ должно быть липшицевым, ограниченным и ОДУ ${ Displaystyle { точка {и}} = г (и)}$ должен иметь уникальное решение для каждого начального условия. В этих и некоторых других условиях ${ displaystyle u_ {k}}$ сходится по вероятности множеству глобальных минимумов J (u) (см. Маряк, Чин, 2008).

Расширение методов второго порядка (Ньютона)

Известно, что стохастическая версия стандартного (детерминированного) алгоритма Ньютона-Рафсона (метод «второго порядка») обеспечивает асимптотически оптимальную или почти оптимальную форму стохастической аппроксимации. SPSA также может использоваться для эффективной оценки матрицы Гессе функции потерь на основе измерений потерь с шумом или измерений градиента с шумом (стохастические градиенты). Как и в случае с базовым методом SPSA, на каждой итерации требуется лишь небольшое фиксированное количество измерений потерь или измерений градиента, независимо от размера проблемы. п. См. Краткое обсуждение в Стохастический градиентный спуск.

Рекомендации

• Бхатнагар, С., Прасад, Х. Л., и Прашант, Л. А. (2013), Стохастические рекурсивные алгоритмы оптимизации: методы одновременных возмущений, Springer [1].
• Hirokami, T., Maeda, Y., Tsukada, H. (2006) "Оценка параметров с использованием стохастической аппроксимации одновременных возмущений", Электротехника в Японии, 154 (2), 30–3 [2]
• Марьяк, Д.Л., Чин, Д.К. (2008), "Глобальная случайная оптимизация с помощью стохастической аппроксимации одновременных возмущений", IEEE Transactions по автоматическому контролю, т. 53, с. 780-783.
• Сполл, Дж. К. (1987), "Метод стохастической аппроксимации для получения оценок параметров максимального правдоподобия", Труды Американской конференции по контролю, Миннеаполис, Миннесота, июнь 1987 г., стр. 1161–1167.
• Сполл, Дж. К. (1992), "Многомерная стохастическая аппроксимация с использованием градиентной аппроксимации одновременных возмущений", IEEE Transactions по автоматическому контролю, т. 37 (3), стр. 332–341.
• Сполл, Дж. К. (1998). «Обзор метода одновременных возмущений для эффективной оптимизации» 2. Технический дайджест Johns Hopkins APL, 19(4), 482–492.
• Сполл, Дж. К. (2003) Введение в стохастический поиск и оптимизацию: оценка, моделирование и управление, Wiley. ISBN  0-471-33052-3 (Глава 7)