68974


これらの最適化にかかる時間, 最適化の拡張性の違いはなんですか？  
またそれぞれの強みはなんですか？  
※拡張性は例えば値のみしか最適化できないなど


CC BY-SA 4.0
2020-06-16T14:22:11.837
67730
2020-07-26T05:13:56.410
2020-06-16T14:39:43.367
40681
40681
question
機械学習
ベイズ最適化と遺伝的アルゴリズムと強化学習の違い


## 強化学習は累積報酬を最適化する

まず、強化学習は他のふたつとは最適化しようとしているものが異なります。ラフに書くと、状態の評価関数 f に対し、強化学習は行動を何回もした後の
**累積報酬** f(x₁) + f(x₂) + ... + f(xₙ) を最大化するための手法であるのに対し、他のふたつは 1
回の報酬を最大にするような値 argmaxₓ f(x) を求めるための手法です。

このため、強化学習では「状態 → 行動」の関数（policy）を求めますが、ベイズ最適化や遺伝的アルゴリズムでは最適な設定値など最大点を求めます。

## 遺伝的アルゴリズムはヒューリスティクス

ベイズ最適化と遺伝的アルゴリズムは、どちらも **ブラックボックス最適化** であるという意味で、同じフレームワークに属する似た手法です。

このふたつを定量的に比較するのは私には難しいですが、現状における定性的な違いとして、理論保証のつけやすさを挙げるのは許されると思います。

つまり、遺伝的アルゴリズムは **ヒューリスティクス**
であり、本当に最大値へ収束するのかどうかなかなか理論的な保証を与えるのが難しいのに対し、ベイズ最適化は最適化したい関数に適当な仮定（例：関数が "滑らか"
であること）をつけ確率論を用いた解析を行うことで、収束の **理論保証** がしやすい傾向にあり、実際よく理論保証がつけられています。

しかしベイズ最適化も最強ではなく、最適化したい関数が所望の仮定を満たしていない場合は収束の理論保証を得ることができません（遺伝的アルゴリズムではそもそも保証が無い場合が多いので、この点においてはイーブンですね）。

また現状のベイズ最適化では、それなりに大きい時間計算量を必要とする傾向があります。このため、サンプル点をたくさんは取りにくく、最適化できるのであれば計算に時間がかかっても構わないという問題設定において採用されることが多いです。

* * *

謝辞：この回答を書くにあたり友人 L の助けを借りました。ありがとう！


CC BY-SA 4.0
2020-07-25T07:49:05.243
68943
2020-07-26T05:13:56.410
2020-07-26T05:13:56.410
19110
19110
67730
answer


強化学習は、問題設定の話です。世界を、`(状態, 行動) -> (報酬, 状態)` な関数であるとみたてて、過去と現在の状態たちとこれまでの報酬から、
next action を決定する関数をどう定めると良いか、で定式化される問題です。

ベイズ最適化は、端的に言えば、「ベイズの確率論で最適化しましょう」という最適化技法の話です。

遺伝的アルゴリズムは、「最適化対象物をデータ構造化し、評価の良い個体は、そのデータ構造を少し変異させるか(mutation)、他の良い個体のデータ構造の適当なパーツを自分のパーツと交換することで(交差)、さらに評価が高くなる可能性が高い。」という仮定の下、適者(評価値の高い個体)生存と変異・交差を交互に繰り返すことで、最適化を行う手法です。

個人的には、遺伝的アルゴリズムは進化計算の一種であると思っています。適者生存と、なにかしらの変異を交互に繰替えすことによって特徴付けられると思っています。その変異に相当するところに、遺伝子の変異と交差相当のデータ操作を加えるものを遺伝的アルゴリズムという、という理解です。

ここまでの説明をした上で、これらは単純には比較不能なものだと思っており、これより詳細な何かしらを説明しようとする場合には、より問題設定を明確化する必要があると思っています。


CC BY-SA 4.0
2020-07-26T04:06:18.343
68974
2020-07-26T04:06:18.343
754
67730
answer