Стохастическое приближение

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

Короче говоря, алгоритмы стохастической аппроксимации имеют дело с функцией вида ${\textstyle f(\theta )=\operatorname {E} _{\xi }[F(\theta ,\xi )]}$что является ожидаемым значением функции, зависящей от случайной величины ${\textstyle \xi }$. Цель состоит в том, чтобы восстановить свойства такой функции. ${\textstyle f}$ не оценивая его напрямую. Вместо этого алгоритмы стохастической аппроксимации используют случайные выборки ${\textstyle F(\theta ,\xi )}$ эффективно аппроксимировать свойства ${\textstyle f}$ такие как нули или экстремумы.

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

Самыми ранними и прототипами алгоритмов такого типа являются алгоритмы Роббинса-Монро и Кифера-Вольфовица, представленные соответственно в 1951 и 1952 годах.

Алгоритм Роббинса-Монро

Алгоритм Роббинса-Монро, представленный в 1951 году Гербертом Роббинсом и Саттоном Монро , представил методологию решения задачи поиска корня, где функция представлена ​​как ожидаемое значение. Предположим, что у нас есть функция ${\textstyle M(\theta )}$и константа ${\textstyle \alpha }$, такой, что уравнение ${\textstyle M(\theta )=\alpha }$ имеет уникальный корень в ${\textstyle \theta ^{*}}$. Предполагается, что пока мы не можем непосредственно наблюдать функцию ${\textstyle M(\theta )}$вместо этого мы можем получить измерения случайной величины ${\textstyle N(\theta )}$ где ${\textstyle \operatorname {E} [N(\theta )]=M(\theta )}$. Структура алгоритма заключается в генерации итераций вида:

$\theta _{n+1}=\theta _{n}-a_{n}(N(\theta _{n})-\alpha )$

Здесь, $a_{1},a_{2},\dots$ представляет собой последовательность положительных размеров шагов. Роббинс и Монро доказали ^{, Теорема 2} что $\theta _{n}$ сходится в $L^{2}$ (а значит, и по вероятности) $\theta ^{*}$и Блюм позже доказал, что сходимость на самом деле имеет вероятность единицу при условии, что:

• ${\textstyle N(\theta )}$ равномерно ограничен,
• ${\textstyle M(\theta )}$ не убывает,
• ${\textstyle M'(\theta ^{*})}$ существует и является положительным, и
• Последовательность ${\textstyle a_{n}}$ удовлетворяет следующим требованиям:

$\qquad \sum _{n=0}^{\infty }a_{n}=\infty \quad {\mbox{ and }}\quad \sum _{n=0}^{\infty }a_{n}^{2}<\infty \quad$

Конкретная последовательность шагов, удовлетворяющая этим условиям, предложенная Роббинсом-Монро, имеет вид: ${\textstyle a_{n}=a/n}$, для ${\textstyle a>0}$. Возможны и другие серии, но для усреднения шума в ${\textstyle N(\theta )}$, вышеуказанное условие должно быть выполнено.

Результаты по сложности

1. Если ${\textstyle f(\theta )}$ дважды непрерывно дифференцируема и сильно выпукла, а минимизатор ${\textstyle f(\theta )}$ принадлежит внутренней части ${\textstyle \Theta }$, то алгоритм Роббинса-Монро достигнет асимптотически оптимальной скорости сходимости относительно целевой функции, равной ${\textstyle \operatorname {E} [f(\theta _{n})-f^{*}]=O(1/n)}$, где ${\textstyle f^{*}}$ это минимальное значение ${\textstyle f(\theta )}$ над ${\textstyle \theta \in \Theta }$.
2. Наоборот, в общем выпуклом случае, когда не хватает как предположения гладкости, так и сильной выпуклости, Немировский и Юдин показали, что асимптотически оптимальная скорость сходимости по значениям целевой функции равна ${\textstyle O(1/{\sqrt {n}})}$. Они также доказали, что этот показатель невозможно улучшить.

Последующие разработки и усреднение

Хотя алгоритм Роббинса-Монро теоретически способен достичь ${\textstyle O(1/n)}$ в предположении дважды непрерывной дифференцируемости и сильной выпуклости он может работать довольно плохо при реализации. В первую очередь это связано с тем, что алгоритм очень чувствителен к выбору последовательности размеров шагов, и предполагаемая асимптотически оптимальная политика размера шага может быть весьма вредной в начале.

Чанг (1954) и Фабиан (1968) показало, что мы достигнем оптимальной скорости сходимости ${\textstyle O(1/{\sqrt {n}})}$ с ${\textstyle a_{n}=\bigtriangledown ^{2}f(\theta ^{*})^{-1}/n}$ (или ${\textstyle a_{n}={\frac {1}{(nM'(\theta ^{*}))}}}$). Лай и Роббинс разработал адаптивные процедуры для оценки ${\textstyle M'(\theta ^{*})}$ такой, что ${\textstyle \theta _{n}}$ имеет минимальную асимптотическую дисперсию. Однако применение таких оптимальных методов требует большого количества априорной информации, которую в большинстве ситуаций трудно получить. Чтобы преодолеть этот недостаток, Поляк (1991) и Руперт (1988) самостоятельно разработал новый оптимальный алгоритм, основанный на идее усреднения траекторий. Поляк и Юдицкий также представил метод ускорения Роббинса-Монро для линейных и нелинейных задач поиска корня за счет использования более длинных шагов и усреднения итераций. Алгоритм будет иметь следующую структуру:

$$\theta _{n+1}-\theta _{n}=a_{n}(\alpha -N(\theta _{n})),\qquad {\bar {\theta }}_{n}={\frac {1}{n}}\sum _{i=0}^{n-1}\theta _{i}$$

Конвергенция ${\bar {\theta }}_{n}$ к уникальному корню $\theta ^{*}$ опирается на условие, что последовательность шагов $\{a_{n}\}$ убывает достаточно медленно. То есть

А1)

$$a_{n}\rightarrow 0,\qquad {\frac {a_{n}-a_{n+1}}{a_{n}}}=o(a_{n})$$

Следовательно, последовательность ${\textstyle a_{n}=n^{-\alpha }}$ с ${\textstyle 0<\alpha <1}$ удовлетворяет этому ограничению, но ${\textstyle \alpha =1}$ нет, отсюда и более длинные шаги. При предположениях, изложенных в алгоритме Роббинса – Монро, полученная модификация приведет к той же асимптотически оптимальной скорости сходимости. ${\textstyle O(1/{\sqrt {n}})}$ но с более жесткой политикой размера шага. До этого идею использования более длинных шагов и усреднения итераций уже предлагали Немировский и Юдин. для случаев решения задачи стохастической оптимизации с непрерывными выпуклыми целями и для выпукло-вогнутых седловых задач. Было замечено, что эти алгоритмы достигают неасимптотической скорости ${\textstyle O(1/{\sqrt {n}})}$.

Более общий результат дан в главе 11 книги Кушнера и Инь. путем определения интерполированного времени ${\textstyle t_{n}=\sum _{i=0}^{n-1}a_{i}}$, интерполированный процесс ${\textstyle \theta ^{n}(\cdot )}$ и интерполированный нормированный процесс ${\textstyle U^{n}(\cdot )}$ как

$$\theta ^{n}(t)=\theta _{n+i},\quad U^{n}(t)=(\theta _{n+i}-\theta ^{*})/{\sqrt {a_{n+i}}}\quad {\mbox{for}}\quad t\in [t_{n+i}-t_{n},t_{n+i+1}-t_{n}),i\geq 0$$

Пусть итерационная средняя будет $\Theta _{n}={\frac {a_{n}}{t}}\sum _{i=n}^{n+t/a_{n}-1}\theta _{i}$ и соответствующая нормализованная ошибка будет ${\hat {U}}^{n}(t)={\frac {\sqrt {a_{n}}}{t}}\sum _{i=n}^{n+t/a_{n}-1}(\theta _{i}-\theta ^{*})$.

С предположением A1) и следующим A2)

А2) Имеется матрица Гурвица ${\textstyle A}$ и симметричную и положительно определенную матрицу ${\textstyle \Sigma }$ такой, что ${\textstyle \{U^{n}(\cdot )\}}$ слабо сходится к ${\textstyle U(\cdot )}$, где ${\textstyle U(\cdot )}$ это статистическое решение

$$dU=AU\,dt+\Sigma ^{1/2}\,dw$$

где ${\textstyle w(\cdot )}$ стандартный винеровский процесс.

удовлетворены и определите ${\textstyle {\bar {V}}=(A^{-1})'\Sigma (A')^{-1}}$. Тогда для каждого ${\textstyle t}$,

$${\hat {U}}^{n}(t){\stackrel {\mathcal {D}}{\longrightarrow }}{\mathcal {N}}(0,V_{t}),\quad {\text{where}}\quad V_{t}={\bar {V}}/t+O(1/t^{2}).$$

Успех идеи усреднения обусловлен разделением исходной последовательности по временной шкале. ${\textstyle \{\theta _{n}\}}$ и усредненная последовательность ${\textstyle \{\Theta _{n}\}}$, причем временной масштаб первого быстрее.

Применение в стохастической оптимизации

Предположим, мы хотим решить следующую задачу стохастической оптимизации.

$$g(\theta ^{*})=\min _{\theta \in \Theta }\operatorname {E} [Q(\theta ,X)],$$

где ${\textstyle g(\theta )=\operatorname {E} [Q(\theta ,X)]}$ дифференцируема и выпукла, то эта задача эквивалентна нахождению корня $\theta ^{*}$ из $\nabla g(\theta )=0$. Здесь $Q(\theta ,X)$ можно интерпретировать как некоторую «наблюдаемую» стоимость как функцию выбранной $\theta$ и случайные эффекты $X$. На практике может быть сложно получить аналитическую форму $\nabla g(\theta )$, метод Роббинса-Монро позволяет сгенерировать последовательность $(\theta _{n})_{n\geq 0}$ приблизить $\theta ^{*}$ если можно сгенерировать $(X_{n})_{n\geq 0}$ , в котором условное ожидание $X_{n}$ данный $\theta _{n}$ это точно $\nabla g(\theta _{n})$, то есть $X_{n}$ моделируется из условного распределения, определяемого

$$\operatorname {E} [H(\theta ,X)|\theta =\theta _{n}]=\nabla g(\theta _{n}).$$

Здесь $H(\theta ,X)$ является несмещенной оценкой $\nabla g(\theta )$. Если $X$ зависит от $\theta$, вообще не существует естественного способа генерирования случайного результата $H(\theta ,X)$ это несмещенная оценка градиента. В некоторых особых случаях, когда применимы методы IPA или отношения правдоподобия, можно получить несмещенную оценку градиента. $H(\theta ,X)$. Если $X$ рассматривается как некий «фундаментальный» случайный процесс, который генерируется независимо от $\theta$, и при некоторых условиях регуляризации для операций перестановки производной и интеграла так, что $\operatorname {E} {\Big [}{\frac {\partial }{\partial \theta }}Q(\theta ,X){\Big ]}=\nabla g(\theta )$, затем $H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)$ дает несмещенную оценку фундаментального градиента. Однако для некоторых приложений нам приходится использовать методы конечных разностей, в которых $H(\theta ,X)$ имеет условное математическое ожидание, близкое к $\nabla g(\theta )$ но не совсем равен ему.

Затем мы определяем рекурсию аналогично методу Ньютона в детерминированном алгоритме:

$$\theta _{n+1}=\theta _{n}-\varepsilon _{n}H(\theta _{n},X_{n+1}).$$

Сходимость алгоритма

Следующий результат дает достаточные условия на $\theta _{n}$ чтобы алгоритм сходился:

С1) $\varepsilon _{n}\geq 0,\forall \;n\geq 0.$

С2) $\sum _{n=0}^{\infty }\varepsilon _{n}=\infty$

С3) $\sum _{n=0}^{\infty }\varepsilon _{n}^{2}<\infty$

С4) $|X_{n}|\leq B,{\text{ for a fixed bound }}B.$

С5) $g(\theta ){\text{ is strictly convex, i.e.}}$

$$\inf _{\delta \leq |\theta -\theta ^{*}|\leq 1/\delta }\langle \theta -\theta ^{*},\nabla g(\theta )\rangle >0,{\text{ for every }}0<\delta <1.$$

Затем $\theta _{n}$ сходится к $\theta ^{*}$ почти наверняка.

Вот несколько интуитивных объяснений этих состояний. Предполагать $H(\theta _{n},X_{n+1})$ является равномерно ограниченной случайной величиной. Если C2) не выполняется, т.е. $\sum _{n=0}^{\infty }\varepsilon _{n}<\infty$ , затем

$$\theta _{n}-\theta _{0}=-\sum _{i=0}^{n-1}\varepsilon _{i}H(\theta _{i},X_{i+1})$$

является ограниченной последовательностью, поэтому итерация не может сходиться к $\theta ^{*}$ если первоначальное предположение $\theta _{0}$ слишком далеко от $\theta ^{*}$. Что касается C3), обратите внимание, что если $\theta _{n}$ сходится к $\theta ^{*}$ затем

$$\theta _{n+1}-\theta _{n}=-\varepsilon _{n}H(\theta _{n},X_{n+1})\rightarrow 0,{\text{ as }}n\rightarrow \infty .$$

поэтому мы должны иметь $\varepsilon _{n}\downarrow 0$ ，и условие C3) это обеспечивает. Естественным выбором будет $\varepsilon _{n}=1/n$. Условие С5) является достаточно жестким условием на форму $g(\theta )$; он дает направление поиска алгоритма.

Пример (где подходит метод стохастического градиента)

Предполагать $Q(\theta ,X)=f(\theta )+\theta ^{T}X$, где $f$ является дифференцируемым и $X\in \mathbb {R} ^{p}$ является случайной величиной, не зависящей от $\theta$. Затем $g(\theta )=\operatorname {E} [Q(\theta ,X)]=f(\theta )+\theta ^{T}\operatorname {E} X$ зависит от среднего значения $X$, и в этой задаче будет уместен метод стохастического градиента. Мы можем выбрать $H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)={\frac {\partial }{\partial \theta }}f(\theta )+X.$

Алгоритм Кифера-Вольфовица

Алгоритм Кифера-Вольфовица был представлен в 1952 году Джейкобом Вулфовицем и Джеком Кифером . и был мотивирован публикацией алгоритма Роббинса-Монро. Однако алгоритм был представлен как метод, который стохастически оценивает максимум функции.

Позволять $M(x)$ — функция, имеющая максимум в точке $\theta$. Предполагается, что $M(x)$ неизвестно; однако некоторые наблюдения $N(x)$, где $\operatorname {E} [N(x)]=M(x)$, можно сделать в любой момент $x$. Структура алгоритма соответствует градиентному методу, при этом итерации генерируются как

$x_{n+1}=x_{n}+a_{n}\cdot \left({\frac {N(x_{n}+c_{n})-N(x_{n}-c_{n})}{2c_{n}}}\right)$

где $N(x_{n}+c_{n})$ и $N(x_{n}-c_{n})$ независимы. На каждом этапе градиент $M(x)$ аппроксимируется аналогично методу центральной разности с $h=2c_{n}$. Итак, последовательность $\{c_{n}\}$ задает последовательность ширины конечных разностей, используемую для аппроксимации градиента, а последовательность $\{a_{n}\}$ определяет последовательность положительных размеров шагов, сделанных в этом направлении.

Кифер и Вулфовиц доказали, что если $M(x)$ удовлетворяет определенным условиям регулярности, то $x_{n}$ сойдётся к $\theta$ по вероятности как $n\to \infty$, а позже Блюм в 1954 году показал $x_{n}$ сходится к $\theta$ почти наверняка, при условии, что:

• $\operatorname {Var} (N(x))\leq S<\infty$ для всех $x$.
• Функция $M(x)$ имеет единственную точку максимума (минимума) и является сильно вогнутым (выпуклым)
  • Алгоритм был впервые представлен с требованием, чтобы функция $M(\cdot )$ сохраняет сильную глобальную выпуклость (вогнутость) во всем допустимом пространстве. Учитывая, что это условие слишком ограничительно, чтобы его можно было наложить на всю область, Кифер и Вулфовиц предположили, что достаточно наложить это условие на компактное множество. $C_{0}\subset \mathbb {R} ^{d}$ которое, как известно, содержит оптимальное решение.
• Функция $M(x)$ удовлетворяет следующим условиям регулярности:
  • Существует $\beta >0$ и $B>0$ такой, что
    $$|x'-\theta |+|x''-\theta |<\beta \quad \Longrightarrow \quad |M(x')-M(x'')|<B|x'-x''|$$
  • Существует $\rho >0$ и $R>0$ такой, что
    $$|x'-x''|<\rho \quad \Longrightarrow \quad |M(x')-M(x'')|<R$$
  • Для каждого $\delta >0$, существует некоторый $\pi (\delta )>0$ такой, что
    $$|z-\theta |>\delta \quad \Longrightarrow \quad \inf _{\delta /2>\varepsilon >0}{\frac {|M(z+\varepsilon )-M(z-\varepsilon )|}{\varepsilon }}>\pi (\delta )$$
• Выбранные последовательности $\{a_{n}\}$ и $\{c_{n}\}$ должны быть бесконечными последовательностями положительных чисел такими, что
  • $\quad c_{n}\rightarrow 0\quad {\text{as}}\quad n\to \infty$
  • $\sum _{n=0}^{\infty }a_{n}=\infty$
  • $\sum _{n=0}^{\infty }a_{n}c_{n}<\infty$
  • $\sum _{n=0}^{\infty }a_{n}^{2}c_{n}^{-2}<\infty$

Подходящим выбором последовательностей, как рекомендовали Кифер и Вулфовиц, было бы следующее: $a_{n}=1/n$ и $c_{n}=n^{-1/3}$.

и важные

1. Алгоритм Кифера Вулфовица требует, чтобы для каждого вычисления градиента было как минимум $d+1$ разные значения параметров должны моделироваться для каждой итерации алгоритма, где $d$ - размерность пространства поиска. Это означает, что когда $d$ велик, алгоритм Кифера-Вольфовица потребует значительных вычислительных усилий на итерацию, что приведет к медленной сходимости.
   1. Чтобы решить эту проблему, Сполл предложил использовать одновременные возмущения для оценки градиента. Этот метод потребует только двух симуляций на итерацию, независимо от размерности. $d$.
2. В условиях, необходимых для сходимости, может быть трудно найти возможность указать заранее определенный компакт, который удовлетворяет сильной выпуклости (или вогнутости) и содержит единственное решение. Что касается реальных приложений, если область применения достаточно велика, эти предположения могут быть довольно ограничительными и крайне нереалистичными.

Дальнейшие разработки

Вокруг этих алгоритмов выросла обширная теоретическая литература, касающаяся условий сходимости, скорости сходимости, многомерности и других обобщений, правильного выбора размера шага, возможных моделей шума и т. д. Эти методы также применяются в теории управления , и в этом случае неизвестная функция, которую мы хотим оптимизировать или найти ноль, может меняться во времени. В этом случае размер шага $a_{n}$ не должен сходиться к нулю, а должен выбираться так, чтобы отслеживать функцию. ^{, 2-е изд., глава 3}

К. Йохан Масрелиес и Р. Дуглас Мартин первыми подали заявку. стохастическая аппроксимация для робастной оценки .

Основным инструментом анализа алгоритмов стохастических аппроксимаций (включая алгоритмы Роббинса-Монро и Кифера-Вольфовица) является теорема Арье Дворецкого, опубликованная в 1956 году.

См. также

• Стохастический градиентный спуск
• Стохастическое уменьшение дисперсии