解法アルゴリズムの選び方

コンピュータは、計算や処理が高速なだけで、何かを考えているわけではありません。そのため、現実の問題をコンピュータを使って解決するには、問題を計算や処理で解ける形に翻訳しなければなりません。しかし、計算や処理で解ける問題の形は、それほど多くありません。

コンピュータで解きたい問題は、大別すると将来予測問題と最適化問題の２つに分かれます。将来予測問題は、ある初期値を入力したら一定期間後にどうなるのかを予測する問題で、この問題に解決と呼べるものはありません。反対に、最適化問題は、一番良さそうな答え（最適解）を見つける問題で、最適解を計算することが問題解決に相当します。

そこで、本稿では最適化問題だけを扱うことにし、問題解決のための考え方を残しておこうと思います。

1 まずは、線形代数方程式にならないか考える
2 次に、最適化問題にならないか考える
3 最後は、モンテカルロ法を考える

まずは、線形代数方程式にならないか考える

もし答えが１つしかないのであれば、何も「一番良さそうな答え（最適解）」でなくても「答え（厳密解）」を計算してしまえば問題ありません。そして、コンピュータで厳密解が計算できるのは、次の３つ方程式の場合しかありません。

連立線形方程式 $b=Ax$
固有方程式 $Ax = \lambda x$
特異値方程式 $A y = \sigma x,\ A^* x = \sigma y$

ここで、 $x, y, \lambda, \sigma$ が未知の解です。Aは与えられた行列で、固有方程式の場合だけは正方行列でなければなりません。bは、与えられたベクトルを表します。

余談ですが、機械学習は大雑把に捉えると、連立線形方程式の $b, x$ に既知のデータを入力して、行列Aを見つけ出す方法と考えることができます。

さて、コンピュータで計算できる厳密解が上記の３種類しかないということは、解決したい問題を３つのどれかに翻訳しなければならないということです。

３種類の方程式は、全て線形代数の方程式なので、問題の解を無理やり線型結合で表現するという方法がよく使われます。例えば、解 $\phi_i$ を、基底 $e_j$ 、係数 $x_{ij}$ を用いて、次のような形に（無理やり）表す時、線型結合で表現したことになります。

$\phi_i = x_{i,0}e_0+x_{i,1}e_1+x_{i,2}e_2+\cdots$

このような書き換えを行って、３種類のどれかに当てはまれば厳密に解くことができます。もし、当てはまらなければ、次の最適解を検討することになります。

なお、線形計画法とか一次計画法と呼ばれる問題群は、最終的に連立線形方程式によって厳密解を計算できる問題群だったりします。

次に、最適化問題にならないか考える

最適化問題は、コンピュータの利用価値が最も高いテーマの一つであり、非常に多くの場面で利用されています。

例えば、パターン判別の機械学習は、最尤法という名前で最適化問題を解いて判別器を作っています。他にも、商品を推奨するリコメンド機能も最急降下法のような最適化アルゴリズムを使用しています。誤解を恐れなければ、現在の人工知能（AI）は最適化問題を解くことによって作られていると言えるかもしれません。

このように、最適化問題は利用場面が多岐に渡るため、その解法も多岐に渡ります。しかし、その中でも検討する軸は３つ程度に絞ることができます。

大域最適化／局所最適化
微分計算可能／微分計算不可能
制約なし／制約付き

ただし、このような検討軸に含まれない問題特有の解法もあります。代表例としては、量子力学のハートリー・フォック方程式や統計力学の平均場近似で用いられる自己無撞着（セルフ・コンシステント）法があります。

大域最適化と局所最適化

まず、最適化問題は、大域最適化問題（グローバル最適化問題）と局所最適化問題（ローカル最適化問題）に分かれます。代表的なアルゴリズムとして、大域最適化問題ではシミュレーテッド・アニーリング法が、局所最適化問題ではBFGS法が挙げられます。

最適化とは、複雑な地形にボールを置いて、一番低くなる場所を見つけ出すような作業をしています。床が傾いていると、床に置いたパチンコ玉が転がっていき、低いところで止まることをイメージすると分かりやすいかもしれません。

このイメージでいくと、局所最適化問題はパチンコ玉を置いた場所から一番近くの凹みを最適解とする問題で、大域最適化問題は部屋全体にパチンコ玉を転がして一番深い凹みを最適解とする問題です。

最適解は、凹みの底（極小解や極大解）に到達したことを判定条件にします。

局所最適化問題の場合は、１つ目の極小解（または極大解）で最適化アルゴリズムを強制終了します。

大域最適化問題の場合は、極小解（または極大解）を記録しておき、全範囲を探索し終えたのち、最小解（または最大解）を選択します。

汎用的アルゴリズム

汎用の局所最適化アルゴリズムは、次のようになります。

Local Optimization Algorithm

Set initial value x
for i = 1 to max-iteration: 
    Compute the objective function f(x). 
    if convergence-condition is true: then 
        break a loop 
    end if
    Set next value x
end for

同様に、汎用の大域最適化アルゴリズムは、次のようになります。

Global Optimization Algorithm

Set initial value x
Allocate memory for solution array : z[100], g[100]
Set initial solution index k=0
for i = 1 to max-iteration:
    Compute the objective function f(x)
    if convergence-condition is true : then
         z[k] = x
         g[k] = f(x)
         k=k+1
         Force to set value x 
    else
         Set next value x
    end if
end for

x = z[j] | j = index of minimum g[0:k-1]

凸問題

局所最適化にするか大域最適化にするかは悩むかもしれませんが、実際には下図のような二次関数の問題（凸問題と言います）として定義もしくは近似することが多いです。これは、凸問題の場合、解が１つに限定され、局所最適化アルゴリズムで最小解（大域的最適解）を計算できるためです。

例えば、複雑なポテンシャルを持つ分子系は局所的に二次関数に近似して計算しますし、機械学習の回帰問題では二乗ノルム（二次関数）を最小化する問題として定義します。

微分可能か微分不可能か

与えらえた地形の関数 $f(x)$ が微分可能かどうかは、最適化アルゴリズムの選択にとって非常に重要です。

なぜなら、微分値を使うことで、アルゴリズムに必要な収束条件（極小解にたどり着いかを判定する条件）と変数xの更新（次のxの値を計算すること）を決めることができるからです。ただし、微分不可能でも最適化アルゴリズムは構成可能なので、微分可能性は必要条件ではなく十分条件です。

このことから、下記が成立します。ただし、逆は真ではありません。

微分が計算できるなら、最適化できる

例えば、ニューラルネットワークは解析的（数式的）には微分を計算できませんが、バックプロパゲーション法を使うことで微分を計算することができます。したがって、ニューラルネットワークは最適化できるということです。

収束判定

収束判定は、問題の解が満たすべき条件を全て満たした時、収束したと判定したとみなします。収束判定条件は、問題によって異なるため、汎用的には定義できません。

しかし、局所最適化問題や大域最適化問題に表現することができ、最適化する関数 $f(x)$ の一次微分 $\frac{df}{dx}$ を計算できる場合は、収束判定条件を次のように表すことができます。

$\displaystyle\frac{df}{dx}=0$

これは、数学的には一次微分が地形の傾きを表すことに由来します。最適解とは地形の凹み（極小値）のことですが、極小値とは傾き＝０になった地点のことを言います。そのため、上記の条件が判定条件になります。（正確には、極大値も傾きが０になります）

変数更新

凹みを探している地形をポテンシャルエネルギーの地形 $V(x)$ とみなすと、物理学的には一次微分 $-\frac{dV}{dx}$ は「力」を表します。

この地形の上に置かれたボールは「力」のかかる方向へ移動するので、新しい位置変数 $x'$ は、ステップ幅を $/alpha$ として、次のように書くことができます。

$x' = x - \alpha \displaystyle\frac{dV}{dx}$

局所最適化問題では、このようにしてボールを徐々に極小値へ近づけていき、収束判定条件を満たしたらアルゴリズムを停止します。

上記の変数更新方法は、最も傾きが大きい方向にボールを動かしていく方法で、このような更新をする最適化アルゴリズムを最急降下法と言います。この他にも、ジグザクにボールを動かす共役勾配法、二次微分（曲率）も考慮したニュートン法、二次微分を近似した準ニュートン法（BFGS法など）があります。

どの最適化アルゴリズムが良いのかは問題によって異なるため、問題に合わせて選択するしかありません。アルゴリズム選択は「一次微分・二次微分（が利用可能か）」「収束までの反復回数（は多くても良いか）」「メモリの未使用量（はたくさんあるか）」を考慮する必要があります。下表に、判定材料を一覧にしておきます。

最適化アルゴリズム	一次微分	二次微分	反復回数	メモリ使用量
最急降下法	必要	不要	多	少：O(n)
共役勾配法	必要	不要	中	少：O(n)
準ニュートン法	必要	不要	少	多：O(n^2)
ニュートン法	必要	必要	極少	多：O(n^2)

これによれば、共役勾配法か準ニュートン法が使いやすいかもしれません。

制約なしか制約付きか

ここまでは、制約条件を特に考えていませんでした。しかし、次のような制約条件付きの問題を考えなければならない場面も多いです。

$\min.\ f(x),\ \mathrm{subject\ to}\ g(x)=c$

これは、「制約条件 $g(x)=c$ の下で、目的関数 $f(x)$ を最小にする解xを求めよ」と読みます。この問題では、等号（=）による制約条件にしましたが、不等号（>, <, ≦, ≧）による制約条件の場合があります。

制約付き最適化問題の基本解法はラグランジュ未定乗数法です。制約条件が不等号の場合は、ラグランジュ未定乗数法を一般化したカルーシュ・クーン・タッカー条件（KKT条件）を使用します。KKT条件は、実際の制約条件に応じてアルゴリズムを考えることが多いため、ここでは基本であるラグランジュ未定乗数法の説明にとどめます。

ラグランジュ未定乗数法

ラグランジュ未定乗数法は、目的関数 $f(x)$ を、パラメータ $\lambda$ を加えた目的関数 $f(x,\lambda)$ に拡張して最適化する方法です。パラメータ $\lambda$ を未定乗数と言います。

拡張目的関数を使った最適化問題は、次のような制約なし最適化問題に変更されます。

$\min\ f(x,\lambda)=f(x)+\lambda\{g(x)-c\}$

第２項は、制約条件 $g(x)=c$ が満たされるときゼロで最小値になるように設定します。すると、本来の目的関数 $f(x)$ が複数の最小値（凹み）を持っていたとしても、第２項がゼロにならない範囲では最小値とならないため、制約条件を満たす最小値だけが選ばれることになります。

最後は、モンテカルロ法を考える

モンテカルロ法（MC法）は乱数サンプリングによって主に積分を計算する方法で、積分方程式を解くことができる解法です。モンテカルロ法を使った最適化アルゴリズムに、メトロポリスアルゴリズムがあります。メトロポリス法を一般化したものが、マルコフ連鎖モンテカルロ法（MCMC法）で、ベイズ統計学でよく使われる解法になります。

やまもとはあまりモンテカルロ法に詳しくはないので、詳細はWikipediaに譲ろうと思います。ただ、モンテカルロ法は非常に多くの分野で使用されているので、勉強しておくと良いと思います。例えば、アルゴリズムが生まれた計算物理学・統計物理学はもちろん、金融工学、コンピュータ・グラフィックス、機械学習、強化学習などがあります。

Post Views: 940