同時摂動確率近似

同時摂動確率近似法（SPSA）は、複数の未知パラメータを持つシステムを最適化するためのアルゴリズム手法です。これは確率近似アルゴリズムの一種です。最適化手法として、大規模個体群モデル、適応モデリング、シミュレーション最適化、大気モデリングなどに適しています。多くの例がSPSAのウェブサイト（http://www.jhuapl.edu/SPSA ）に掲載されています。このテーマに関する包括的な書籍としては、Bhatnagar et al. (2013) があります。このテーマに関する初期の論文としては Spall (1987) があり、その基礎となる理論と正当性を示す論文としては Spall (1992) があります。

SPSAは、シミュレーテッドアニーリングなどの他の手法と同様に、大域的最小値を見つけることができる降下法です。その主な特徴は、最適化問題の次元に関係なく、目的関数の2つの測定値のみを必要とする勾配近似です。最適な制御を見つけたいことを思い出してください。$\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に収束する正の数列です。$u_n$はp次元ベクトルであり、${\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}}},}$

${\displaystyle 1\leq i\leq p}$、 どこ${\displaystyle e_{i}}$は、1 を含む単位ベクトルです。${\displaystyle i^{th}}$ 場所、そして${\displaystyle c_{n}}$は、 nとともに減少する小さな正の数です。この方法では、各Jの評価は2p 回です。${\displaystyle g_{n}}$が必要です。pが大きい場合、この推定量は効率が低下します。

さあ $\displaystyle \Delta _{n}}$ランダムな摂動ベクトルとする。${\displaystyle i^{th}}$確率的摂動勾配推定量の構成要素は次のとおりです。

SP:${\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は一度に1つの方向のみを摂動させるのに対し、SP推定器はすべての方向を同時に摂動させる（分子はすべてのp成分で同一である）ことに注意してください。SPSA法で各方向に必要な損失関数測定の数は${\displaystyle g_{n}}$は常に2であり、次元pに依存​​しません。したがって、SPSAはFDSAよりもp倍少ない関数評価で済むため、はるかに効率的です。

p=2を用いた簡単な実験では、SPSA は FDSA と同じ反復回数で収束することが示されました。FDSA は勾配法のように、ほぼ最急降下方向をたどります。一方、ランダムな探索方向を持つ SPSA は、厳密には勾配経路をたどりません。しかし、平均的には勾配近似が勾配のほぼ不偏 推定量であるため、ほぼ勾配経路をたどります。これは次の補題で示されています。

で表す

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

推定量のバイアス${\displaystyle {\hat {g}}_{n}}$と仮定する${\displaystyle \{(\Delta _{n})_{i}\}}$これらはすべて互いに独立しており、平均はゼロで、2次モーメントは有界であり、${\displaystyle E(|(\Delta _{n})_{i}|^{-1})}$一様に有界である。${\displaystyle b_{n}}$→0 wp  1。

主なアイデアは、条件付けを使用することです$\displaystyle \Delta _{n}}$表現する${\displaystyle E[({\hat {g}}_{n})_{i}]}$そして、2次テイラー展開を使用する${\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。

次に、いくつかの仮説を再開します。$u_t$確率的にグローバル最小値の集合に収束する${\displaystyle J(u)}$この方法の効率は形状に依存します。${\displaystyle J(u)}$パラメータの値${\displaystyle a_{n}}$そして${\displaystyle c_{n}}$摂動項の分布$\displaystyle \Delta _{ni}}$まず、アルゴリズムのパラメータは以下の条件を満たす必要があります。

• ${\displaystyle a_{n}}$>0、${\displaystyle a_{n}}$n→∝ のとき →0 となり、${\displaystyle \sum _{n=1}^{\infty }a_{n}=\infty }$良い選択肢は${\displaystyle a_{n}={\frac {a}{n}};}$a>0;
• ${\displaystyle c_{n}={\frac {c}{n^{\gamma }}}}$、ただし c>0、$\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}}$これはラデマッハー分布、すなわち確率0.5のベルヌーイ分布±1です。他の選択肢も可能ですが、一様分布と正規分布は有限逆モーメント条件を満たさないため使用できないことに注意してください。

損失関数J(u) は3 回連続微分可能でなければならず、 3 階微分の各要素は有界でなければならない。${\displaystyle |J^{(3)}(u)|<a_{3}<\infty }$。 また、${\displaystyle |J(u)|\rightarrow \infty }$として${\displaystyle u\rightarrow \infty }$。

加えて、${\displaystyle \nabla J}$リプシッツ連続で有界であり、ODE${\displaystyle {\dot {u}}=g(u)}$各初期条件に対して一意の解が存在する必要がある。これらの条件およびその他いくつかの条件の下で、$u_k$確率的に J(u) のグローバル最小値の集合に収束する（Maryak と Chin、2008 を参照）。

微分可能性は必要なく、連続性と凸性があれば収束に十分であることが示されている。^{[ 1 ]}

標準的な（決定論的な）ニュートン・ラフソン法の確率的バージョン（「2次」法）は、漸近的に最適またはほぼ最適な確率的近似形式を提供することが知られています。SPSAは、ノイズのある損失測定値またはノイズのある勾配測定値（確率的勾配）に基づいて、損失関数のヘッセ行列を効率的に推定するためにも使用できます。基本的なSPSA法と同様に、問題の次元pに関係なく、各反復で必要な損失測定値または勾配測定値は少数の固定数のみです。詳細については、 「確率的勾配降下法」の簡単な説明を参照してください。

• Bhatnagar, S.、Prasad, HL、およびPrashanth, LA (2013)、『最適化のための確率的再帰アルゴリズム：同時摂動法』、Springer。
• 広上 哲也、前田 裕子、塚田 浩（2006）「同時摂動確率近似を用いたパラメータ推定」、電気工学会誌、154（2）、30-3
• Maryak, JL、Chin, DC (2008)、「同時摂動確率近似によるグローバルランダム最適化」、IEEE Transactions on Automatic Control、vol. 53、pp. 780-783。
• Spall, JC (1987)、「最大尤度パラメータ推定値を生成するための確率近似手法」、アメリカ制御会議議事録、ミネアポリス、ミネソタ州、1987年6月、pp. 1161–1167。
• Spall, JC (1992)、「同時摂動勾配近似を用いた多変量確率近似」、IEEE Transactions on Automatic Control、vol. 37(3)、pp. 332–341。
• Spall, JC (1998). 「効率的な最適化のための同時摂動法の概要」2 . Johns Hopkins APL Technical Digest , 19(4), 482–492.
• Spall, JC (2003) 『確率的探索と最適化入門：推定、シミュレーション、および制御』、 Wiley。ISBN 0-471-33052-3（第7章）