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

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

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

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

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

Алгоритм Роббинса – Монро [ править ]

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

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

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

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

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

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

Результаты сложности [ править ]

1. Если является дважды непрерывно дифференцируемым и сильно выпуклым, а минимизатор принадлежит внутренней части , то алгоритм Роббинса – Монро достигнет асимптотически оптимальной скорости сходимости по отношению к целевой функции, равной , где - минимальное значение сверх . ^{[5] [6]}${\ 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. Напротив, в общем выпуклом случае, где отсутствуют как предположение гладкости, так и сильная выпуклость, Немировский и Юдин ^[7] показали, что асимптотически оптимальная скорость сходимости относительно значений целевой функции равна . Они также доказали, что этот показатель нельзя улучшить.${\textstyle O(1/{\sqrt {n}})}$

Последующие события и усреднение Поляка – Рупперта [ править ]

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

Чанг ^[9] (1954) и Фабиан ^[10] (1968) показали, что мы можем достичь оптимальной скорости сходимости с помощью (или ). Лай и Роббинс ^{[11] [12]} разработали адаптивные процедуры оценки , которые имеют минимальную асимптотическую дисперсию. Однако применение таких оптимальных методов требует большого количества априорной информации, которую трудно получить в большинстве ситуаций. Чтобы преодолеть этот недостаток, Поляк ^[13] (1991) и Рупперт ^[14] (1988) независимо друг от друга разработали новый оптимальный алгоритм, основанный на идее усреднения траекторий. Поляк и Юдицкий ^[15]${\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}}$также представил метод ускорения Роббинса – Монро для линейных и нелинейных задач поиска корня за счет использования более длинных шагов и усреднения итераций. Алгоритм будет иметь следующую структуру:

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

A1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сходимость алгоритма [ править ]

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

C1) ${\displaystyle \varepsilon _{n}\geq 0,\forall \;n\geq 0.}$

C2) ${\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}=\infty }$

C3) ${\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}^{2}<\infty }$

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

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

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

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

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

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

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

Пример (где подходит метод стохастического градиента) ^[8] [ править ]

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

Алгоритм Кифера – Вулфовица [ править ]

Алгоритм Кифер-Вольфовиц была введена в 1952 году Jacob Волфовица и Джек Kiefer , ^[19] , и было мотивировано публикации алгоритма Роббинса-Monro. Однако алгоритм был представлен как метод, который стохастически оценивает максимум функции. Позвольте быть функцией, которая имеет максимум в точке . Предполагается, что неизвестно; однако определенные наблюдения , где , могут быть сделаны в любой момент . Структура алгоритма соответствует градиентному методу, при этом итерации генерируются следующим образом:${\displaystyle M(x)}$${\displaystyle \theta }$${\displaystyle M(x)}$${\displaystyle N(x)}$${\displaystyle \operatorname {E} [N(x)]=M(x)}$${\displaystyle x}$

${\displaystyle x_{n+1}=x_{n}+a_{n}{\bigg (}{\frac {N(x_{n}+c_{n})-N(x_{n}-c_{n})}{2c_{n}}}{\bigg )}}$

где и независимы, а градиент аппроксимируется конечными разностями. Последовательность определяет последовательность ширины конечной разности, используемую для приближения градиента, в то время как последовательность определяет последовательность положительных размеров шага, взятых вдоль этого направления. Кифер и Вулфовиц доказали, что если удовлетворяются определенные условия регулярности, то будет сходиться по вероятности, как , а позже Блюм ^[4] в 1954 году показал сходится к почти наверняка, при условии, что:${\displaystyle N(x_{n}+c_{n})}$${\displaystyle N(x_{n}-c_{n})}$${\displaystyle M(x)}$${\displaystyle \{c_{n}\}}$${\displaystyle \{a_{n}\}}$${\displaystyle M(x)}$${\displaystyle x_{n}}$${\displaystyle \theta }$${\displaystyle n\to \infty }$${\displaystyle x_{n}}$${\displaystyle \theta }$

• ${\displaystyle \operatorname {Var} (N(x))\leq S<\infty }$для всех .${\displaystyle x}$
• Функция имеет единственную точку максимума (минимума) и является сильно вогнутой (выпуклой).${\displaystyle M(x)}$
  • Алгоритм впервые был представлен с требованием, чтобы функция поддерживала сильную глобальную выпуклость (вогнутость) во всем допустимом пространстве. Учитывая, что это условие слишком ограничительно, чтобы накладывать его на всю область, Кифер и Вулфовиц предложили, что достаточно наложить условие на компакт, который, как известно, включает оптимальное решение.${\displaystyle M(\cdot )}$${\displaystyle C_{0}\subset \mathbb {R} ^{d}}$
• Функция удовлетворяет следующим условиям регулярности:${\displaystyle M(x)}$
  • Существует и такое, что${\displaystyle \beta >0}$${\displaystyle B>0}$
    $${\displaystyle |x'-\theta |+|x''-\theta |<\beta \quad \Longrightarrow \quad |M(x')-M(x'')|<B|x'-x''|}$$

    
  • Существует и такое, что${\displaystyle \rho >0}$${\displaystyle R>0}$
    $${\displaystyle |x'-x''|<\rho \quad \Longrightarrow \quad |M(x')-M(x'')|<R}$$

    
  • Для каждого существует такое, что${\displaystyle \delta >0}$${\displaystyle \pi (\delta )>0}$
    $${\displaystyle |z-\theta |>\delta \quad \Longrightarrow \quad \inf _{\delta /2>\varepsilon >0}{\frac {|M(z+\varepsilon )-M(z-\varepsilon )|}{\varepsilon }}>\pi (\delta )}$$

    
• Выбранные последовательности и должны быть бесконечными последовательностями положительных чисел, таких что${\displaystyle \{a_{n}\}}$${\displaystyle \{c_{n}\}}$
  • ${\displaystyle \quad c_{n}\rightarrow 0\quad {\text{as}}\quad n\to \infty }$
  • ${\displaystyle \sum _{n=0}^{\infty }a_{n}=\infty }$
  • ${\displaystyle \sum _{n=0}^{\infty }a_{n}c_{n}<\infty }$
  • ${\displaystyle \sum _{n=0}^{\infty }a_{n}^{2}c_{n}^{-2}<\infty }$

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

Последующие события и важные вопросы [ править ]

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

Дальнейшее развитие [ править ]

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

К. Йохан Масрелиес и Р. Дуглас Мартин были первыми, кто применил стохастическую аппроксимацию к робастному оцениванию . ^[23]

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

См. Также [ править ]

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

Ссылки [ править ]