e4exp
commented
3 years ago はじめに
本稿では，多変数システムの確率的最適化のための simultaneous perturbation stochastic approximation (SPSA) アルゴリズムについて紹介します． 最適化アルゴリズムは，ほとんどの工学システムの設計，解析，制御において重要な役割を果たしており，APLやその他の組織の業務においても広く利用されています． 実際、将来は（最適化）アルゴリズムだらけになるでしょう。 最適化アルゴリズムは、ほとんどすべてのものに組み込まれるようになります。 最適化アルゴリズムは、企業全体の効率を上げるために、複雑さの連鎖を上っていきます。 また、コンピュータの普及に伴い、複雑性の連鎖を下降させています。(USA Today, 31 Dec 1997)
SPSAアルゴリズムを紹介する前に、ここでは確率的最適化に関する一般的な背景を説明します。 ほとんどの最適化問題の数学的表現は、調整可能なパラメータのベクトルに関して、あるスカラー値の目的関数を最小化（または最大化）することです。 最適化アルゴリズムは，調整可能なパラメータを，ある初期推測（または推測のセット）から目的関数を改善する値に変更するための，段階的な手順です．
図1は，u1とu2という2つの変数だけの非常に単純なケースで，目的関数が最小化される損失関数である場合のプロセスを示しています （一般性を損なわない範囲で，最大化問題は目的関数の符号を変えることで最小化問題に自明に変換できるため，ここでは最適化を最小化の文脈で説明します）． しかし、現実の問題では、もっと多くの変数が必要です。 また，図1の例では，繰り返し処理を行っても損失関数の値が一様に減少しないことから，入力情報にノイズがある確率的最適化の典型的な例となっています（アルゴリズムの3段階目で損失値が一時的に増加していることに注意してください）． 多くの最適化アルゴリズムは、決定論的な設定を前提とし、損失関数に関連する勾配ベクトル（すなわち、最適化されるパラメータに対する損失関数の勾配）に関する情報が利用可能であることを前提として開発されています。 しかし、直接的な勾配情報や測定値に依存しない再帰的最適化アルゴリズムへの関心が高まっています。 むしろ、これらのアルゴリズムは、損失関数の（一般的にノイズの多い）測定値から形成される勾配の近似値に基づいています。 このような関心は、例えば、複雑なシステムの適応制御や統計的同定、大規模なモンテカルロ・シミュレーションによるプロセスの最適化、リカレント・ニューラル・ネットワークの学習、ノイズの多いセンサーデータからの画像の復元、複雑な待ち行列や離散イベントシステムの設計などの問題に端を発している。
本稿では、直接的な勾配情報が得られないために、このような近似を使用する場合に焦点を当てています。 勾配なしの確率的アルゴリズムは、損失関数の測定のみを必要としながらも、勾配ベースの確率的アルゴリズム[例えば、Robbins-Monro1確率的近似（R-M SA）]と同様の収束特性を示します。 このようなアルゴリズムの主な利点は、勾配ベースのアルゴリズムで必要とされる、調整（最適化）されるパラメータと最小化される損失関数の間の関数関係に関する詳細な知識を必要としないことです。 一方、モンテカルロ最適化や再帰的統計的パラメータ推定などの分野では、損失関数を計算する方が、勾配を計算するよりも大幅に計算量を削減できる場合があります。
直接的な勾配測定に基づくアルゴリズムと、損失関数の測定値からの勾配近似に基づくアルゴリズムの違いについて詳しく説明します。 勾配ベースのアルゴリズムの原型はR-M SAであり、これは決定論的最急降下法やニュートン・ラフトン法、ニューラルネットワークのバックプロパゲーション法、離散事象システムのための無限小摂動解析ベースの最適化法などの技術の一般化と考えられる。 勾配ベースのアルゴリズムでは、最適化されるパラメータに対する損失関数の勾配を直接測定します。 一般的に、基礎となるデータにはノイズが含まれているため、これらの測定は通常、勾配の推定値をもたらします。 通常、システムの運用やシミュレーションの過程で、（ノイズが加わっていてもいなくても）勾配の直接的な測定値を自然に得ることはできないため、基本的なシステム出力の測定値からR-M勾配の推定値を計算するには、基本的なシステムの入出力関係に関する詳細な知識が必要となります。 一方、勾配近似に基づくアプローチでは、基本的な出力測定値を損失関数のサンプル値に変換するだけなので、システムの入出力関係を完全に知る必要はありません。 勾配のない確率的最適化の古典的な手法は，Kiefer-Wolfowitz有限差分SA（FDSA）アルゴリズムである2．
勾配ベース（R-M）と勾配なしのアルゴリズムの実装に必要な情報が根本的に異なるため、意味のある比較方法を構築することは困難です。 しかし、一般的には、反復回数で評価した場合、勾配ベースのアルゴリズムの方が、損失関数ベースの勾配近似を用いたアルゴリズムよりも収束が速いと言えます。 直感的には、勾配ベースのアルゴリズムに必要な追加情報を考えれば、この結果は驚くべきことではない。 特に、漸近理論に基づいて、真の最適パラメータベクトルからのパラメータ推定値の偏差で測定した最適収束率は、勾配ベースのアルゴリズムではk^{-1/2}オーダー、勾配近似に基づくアルゴリズムではk^{-1/3}オーダーとなる（kは反復回数を表す）。 (非勾配アルゴリズムの収束率の最大値がk^{-1/2}に任意に近いか等しいという特殊なケースも存在する)。 もちろん、実際には、以下の3つの理由から、どのアルゴリズムが最適かを決定するためには、他の多くの要素を考慮する必要があります。
(1）システムの入出力関係に関する信頼性の高い知識を得ることができない場合があります。つまり、勾配ベースのアルゴリズムは、（システムモデルが利用できない場合には）実現不可能であるか、（劣悪なシステムモデルを使用した場合には）信頼性に欠けるということになります。 (2) 効果的な収束を実現するための総コストは、必要な反復回数だけでなく、反復ごとに必要なコストにも依存し、勾配ベースのアルゴリズムでは一般的にこのコストが大きくなります。(このコストには、計算負荷の増加、勾配の決定とコーディングに必要な追加の人間の労力、モデル構築のための実験的なコスト(労働力、材料、燃料など)が含まれます)。 (3) 収束率は漸近理論に基づいており、有限のサンプルにおける実用的な収束率を代表していない可能性がある。
これらの理由から、勾配ベースのアルゴリズムが勾配近似ベースのアルゴリズムよりも優れているとは、勾配ベースのアルゴリズムの方が漸近的な収束速度が速いとしても、一概には言えません（また、無限小摂動解析などのシミュレーションベースの最適化では、1回の反復につき1回のシステム実行で済むのに対し、近似ベースのアルゴリズムでは、1回の反復につき複数回のシステム実行が必要となる場合があります）。
しかし、一般的には、直接的な勾配情報が便利で確実に得られる場合は、最適化プロセスにおいてこの情報を使用することが有利になります。 この記事では、そのような情報が容易に得られない場合に焦点を当てています。 次のセクションでは、SPSAと関連するFDSAアルゴリズムについて説明します。 次に、SPSAの収束と効率性に関連する理論の一部を要約します。 次のセクションでは、ニューラルネットワークに関連する例で、理論の意味を説明します。 次に、実装のための実用的なガイドラインが示され、その後、いくつかの補助的な結果とアルゴリズムのいくつかの拡張がまとめられています。 ここでは、遺伝的アルゴリズムやシミュレーテッドアニーリングなどの大域的な最適化手法については触れていませんが、Spall3では、確率的近似の文脈におけるこれらの手法についていくつかの議論を行っています。
多変量解析による確率的最適化は，多くの工学システムの解析と制御において重要な役割を果たしています． 実際の最適化問題では、解析的（閉形式）解が得られることはほとんどないため、解を反復的に求める数学的アルゴリズムを使用する必要があります。 このような観点から、多変量最適化問題に対する「同時摂動確率近似法（SPSA）」が開発されました。 SPSAは近年、統計的パラメータ推定、フィードバック制御、シミュレーションベースの最適化、信号・画像処理、実験計画などの分野で国際的に注目を集めています。 SPSAの特徴は、最適化問題の次元に関係なく、目的関数の2つの測定値のみを必要とする基本的な勾配近似にあります。 この特徴により、特に最適化されるべき変数の数が多い問題において、最適化のコストを大幅に削減することができます。
(キーワード 勾配近似, 多変量最適化, シミュレーションに基づく最適化, 同時摂動確率的近似, SPSA, 確率的最適化.)