Стохастическая аппроксимация одновременных возмущений - 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 \{a_{n}\}}$ - последовательность положительных чисел, сходящаяся к 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 _{n})_{i}\}}$ все взаимно независимы с нулевым средним, ограниченными секундными моментами и ${\displaystyle E(|(\Delta _{n})_{i}|^{-1})}$ равномерно ограниченный. потом ${\displaystyle b_{n}}$→ 0 п.п. 1.

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

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

${\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 }({\frac {a_{n}}{c_{n}}})^{2}<\infty }$
• ${\displaystyle \Delta _{ni}}$ должны быть взаимно независимыми случайными величинами с нулевым средним, симметрично распределенными относительно нуля, с ${\displaystyle \Delta _{ni}<a_{1}<\infty }$. Обратные первый и второй моменты ${\displaystyle \Delta _{ni}}$ должно быть конечным.

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

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

Кроме того, ${\displaystyle \nabla J}$ должно быть липшицевым, ограниченным и ОДУ ${\displaystyle {\dot {u}}=g(u)}$ должен иметь уникальное решение для каждого начального условия. В этих и некоторых других условиях ${\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)