微分は関数のある点での傾きがわかる という優れものでしたね。ニューラルネットワークでは、その優れた性質を持つ微分を何度も繰り返しトライアル&エラーで最適なパラメータを獲得します。, でも、「微分なんか言うまどろっこしい方法を使わなくても上のグラフを見ればパッと最小値がわかるから、上のようなグラフを書いて最小値を取る値を最適な $w_1, w_2$ とすればいいじゃないか」、と思ってしまいそうです。, ただ、よく考えてみてください。このグラフを獲得するには、損失関数にいろんな組み合わせの $w_1, w_2$ を大量に代入してみて、それぞれで値を求めて大量にプロットしていくことで上のようなグラフが書けます。その色々な値を大量に計算するというのは要はブルートフォースで全く賢くありません。上のグラフのような2次元($w_1, w_2$)しかパラメータがないなら、なんかできそうと思う方もいるかもしれませんが、実際の最近のニューラルネットワークのパラメータ数は2次元どころではなく、1000万以上ものパラメータがあることが珍しくありません。もはや1000万の数字の組み合わせから損失を1つ計算するのだけでも時間がかかりそうですが、ブルートフォースではこれを大量に計算するので計算量はもはや無限になってしまいます。 ここで出てくるのが微分 です。 まずは $w_1$ で偏微分して現在の $w_1$ と $w_2$ を代入すれば $w_1$ 方向の傾きがわかり、 $$ Pathological Curvatureでは振動方向は最小値方向に比べて勾配が大きくなっていますね。これを解決するには、振動方向の学習率を下げてあげれば振動を抑えられそうです。 \mathbb{F}(\vec{x}) = {f_1(\vec{x}), f_2(\vec{x})...f_n(\vec{x})}\ where\ n \geq 4 Gradient Descent With Momentum (C2W2L06) 最適化アルゴリズムとは? SGDやらモーメンタムやらAdamやら色々な最適化アルゴリズムを聞きますが、 これらの最適化アルゴリズムは全て最急降下法の派生で、最急降下法さえ理解すれば他の最適化アルゴリズムは理解できてしまう のです。 10 の例と同じように適応度が20、50,30の3つの個体があったとき、それぞれが選択される確率を出力します。, 今回は移動距離をもとに適応度を計算しますが、移動距離は短ければ短いほどいいのに対して、適応度が高ければ高いほど選択されるため、少し細工が必要です。その細工として逆数を利用した例とその結果を以下に示します。(個体数: 3、都市数: 5 として), 道のり(path length)の小さい要素は、選択される確率(roulette table)が高くなっていることを確認できます。, ルーレット、つまり選ばれる確率のテーブルができたので、これを元に交叉を行う個体を選択する関数を実装します。, 2行目でgenerate_rouletteを使ってルーレットを生成し、またnumpy.random.choiceを使ってルーレットを実行しています。第1引数が選ぶ数字のレンジで、rouletteの長さ、つまり個体数があてはまり、第2引数は選ぶ数字の数、replace=は重複を許すか否かのオプションで、p=でそれぞれが選ばれる確率を指定しています。, エリート選択は成績の良い個体をそのまま保存することを目的としているため以下に示す交叉や突然変異の対象にはしません。, 交叉にも遺伝子の形によって適した方法があったり、あるいは同じ遺伝子の形に対しても様々な方法があったりします。色々変えて適切なのはどれか、選べる環境がベストだと思います。, さて今回の遺伝子の形は、都市のインデックスを巡る順番に格納しているというものです。順番の意味を失うことなく、遺伝子が重複しない手法をとる必要があります。, そのような交叉方法として、循環交叉や順序交叉などが挙げられますが、部分的交叉という手法を実装します。, 部分的交叉の具体的な例を用いた手順をFig. from keras import optimizers # All parameter gradients will be clipped to # a maximum norm of 1. sgd = optimizers.SGD(lr=0.01, clipnorm=1.) いままでは目的の関数の値がひとつの実数だったので自然と「よさ」を定量化できました。多目的最適化問題では別の「よさ」を定義します。, まず、 読みやすさのために引数である窓の大きさを $\vec{x}$, 目的関数の日照時間を $f_1(\vec{x})$, 電気代を $f_2(\vec{x})$ と表します。さらに、多目的最適化問題そのものは $\mathbb{F}(x) = {f_1(\vec{x}), f_2(\vec{x})}$ と表します。, x軸を $f_1$ の値、 y軸を $f_2$ の値にしたグラフを書いたとき、すべての目的関数が最小値をとる、 $(min\ f_1(\vec{x}),min\ f_2(\vec{x}))$ となる点があります。この点のことを 理想点(Utopia Point) と呼び、 $\mathbb{Z}^*$ と表現します。窓の例をとると日照時間が1日24時間かつ電気代が0のときです。多くの場合、先ほど挙げたトレードオフ関係のせいで理想点は実現することが不可能です。, 勾配降下法と同じように,適当に $\vec{a}_0$ を選んで $\vec{x}$ を初期化します。別の値 $\vec{a}_1$ を $x$ に代入したとき $f_1(\vec{a}_0)=f_1(\vec{a}_1)$ で $f_2(\vec{a}_0)>f_2(\vec{a}_1)$ の場合があるとします。 このときはトレードオフが発生しないので $a_1$ のほうが「よい」と言い切れます。 このような状況について $\mathbb{F}(\vec{a}_1)$ は $\mathbb{F}(\vec{a}_0)$ を 支配(Dominates) するといいます。, 厳密にはすべての目的関数について $f_i(\vec{a}_0) \geq f_i(\vec{a}_1)$ が成立し、最低でもひとつの目的関数について $f_i(\vec{a}_0) > f_i(\vec{a}_1)$ が成立する場合に $\mathbb{F}(\vec{a}_1)$ は $\mathbb{F}(\vec{a}_0)$ を支配します。, 引数 $x$ が取りうる値の範囲をすべて考慮したうえで支配されない、つまり「可能な限りよい」、点について パレート最適(Pareto Optimal) であるといいます。 そして、パレート最適な点が構成する境界を パレート最適曲面/曲線(Pareto Front) と呼びます。 そこで賢く損失関数の最小値を求めてみよう、というのが微分を使った方法です。 $w_2$ で偏微分して現在の $w_1$ と $w_2$ を代入すれば $w_2$ 方向の傾きがわかります。, それによって、 $w_1$ と $w_2$ 近辺の傾きは上図のようにわかり、損失を下げるためには$w_1$ と $w_2$ を大きくするのかまたは小さくするのかがわかりますね。, といっても、あらかじめ決めておいた学習率(0~1の値)を使うだけ です。よく $10^{-5}$ や $10^{-2}$ などが見受けられます。この学習率を先ほど微分して出てきた値に掛けるだけ。 次項のミニバッチ学習がこれを解決してくれるのです。, 全データを使ったバッチ学習ではまず全データの勾配を計算するのでその計算を並列化しました。一方でSGDは勾配計算のデータ数が1つでパラメータの更新が終わったら次のデータ1つに対してパラメータを更新しました。更新で使うデータ数が1つだからこそ並列化ができないのだから、このデータ数を増やせばバッチ学習のように並列化ができます。ただ、バッチ学習と同じように全データまで増やしてしまってはランダム性がなくなります。ということで、ミニバッチ学習SGDでは1回の更新で一定数のデータを使い学習 します。1回の更新で用いるデータ数は16個や32個などがよく使われ、このデータの塊を小さいバッチということでミニバッチ と言います。ミニバッチのサイズもハイパーパラメータです。マシンのスペックが高い場合は大きいサイズを指定できます。, ここまでで最急降下法の欠点をある程度克服することができたのですが、 11に示します。(画像自体は4分割されています。), numpy.whereは指定した値が対象とする行列の中のどの位置にあるかインデックスで返してくれるものです。 (Fig. 伝われ!(笑), 肝心の $\vec{v}_i(t)$ の計算についてですが、まずParticleに対して慣性 $W\vec{v}_i(t-1)$ が働きます。 By following users and tags, you can catch up information on technical fields that you are interested in as a whole, By "stocking" the articles you like, you can search right away. ここでは、最適化におけるPythonについて紹介します。, わかりやすい。数式によるモデルとPythonによるモデルが近いため、より本質的な記述に専念でき、保守しやすいモデルを作成できる。, Pythonで完結できる。汎用言語であるため、種々の目的の処理もほぼPythonで記述できる。 w_{t+1} = w_{t} - \alpha\nabla_w\mathcal{L}(w) RMSPropはgradの大きさに応じて学習率を調整する、というものです。 $$ (英語) 物凄く参考にしています。上の続編。モーメンタムからAdamまで。, Stochastic Gradient Descent with momentum 移動平均は急な変化に動じない、と言いましたがこれはつまり、振動のような急激に変化に動じない、ということですね。しかもPathological Curvatureで起きている振動は正負の符号が逆になるほどの振動ですね。前時刻で正の方向を向いていた勾配が現時刻では負の方向を向く勾配になってしまうほどの振動 です。この移動平均では前時刻と現時刻を足し合わせるので、正負で振動していると打ち消しあって振動が小さくなる のです。 $$, データ(入力値と正解ラベル(値)のペア)が1000個あるとします。ニューラルネットワークは初めはランダムに $w_1$ と $w_2$ を持っています。 pythonで遺伝的アルゴリズム(GA)を実装して巡回セールスマン問題(TSP)をとく. 例えば、webからデータを取得して、集計して、分析して、最適化して、可視化するなど、すべてPythonでできる。, ライブラリが多い。パッケージコミュニティサイト https://pypi.python.org/pypi だけでも約9万ものパッケージが公開されている。 $$ min\ f(x) $$ By following users and tags, you can catch up information on technical fields that you are interested in as a whole, By "stocking" the articles you like, you can search right away. 「素早く」というのは、目的関数の評価回数を少なくするという意味でもあります。$\vec{x}$ がとりうる値すべてに対して目的関数を評価して結果が良かったものを選択してしまえば最適解は得られるので、いかにして評価回数を抑えつつ最適化するかが味噌だったりします。, ちなみに、最適化アルゴリズムの評価に使われる評価関数はかなり複雑な構造をしていたりするので興味深いです。, そろそろ多目的最適化にたどり着くまであと1歩のところに来ました。 もし最初に $x=-100$ と代入して、転がり降りた先の小さな谷に収束したとしても、より深い谷が他にも存在しますね。, このような小さな谷のことを 局所解(Local Optima) と呼びます。このように最適化アルゴリズムが 大域的最適解(Global Optimum) に収束しなかったときのことを「局所解に陥る」といいます。, 最適化アルゴリズムは局所解に陥らないで素早く収束することを目的にしていますが、その両立は難しいです。 $$\vec{x} = (x_1, x_2)$$ Microsoft Ignite 2020の振り返りも「Azure Rock Star Community Day」, Intro to Optimization in Deep Learning: Vanishing Gradients and Choosing the Right Activation Function, Intro to optimization in deep learning: Momentum, RMSProp and Adam, Stochastic Gradient Descent with momentum, Exponentially Weighted Averages (C2W2L03), Understanding Exponentially Weighted Averages (C2W2L04), you can read useful information later efficiently. What is going on with this article? 私は、業務で、組合せ最適化技術を用いたソフトウェア開発(例えば、物流における輸送コストの最小化など)を行っています。以前は、C++やC#を用いて、最適化のモデルを作成していましたが、最近ではPythonを用いることが多いです。 要するに言いたいこととしては「傾き(勾配)」を計算してそれを「降下」していきたいんです。, 結果的に $step$ の大きさに応じて最小値の0に収束するか0の周りを振動しますね。 学習率は別名ステップサイズ(step size)とも呼ばれ、パラメータの1回の更新(ステップ)の大きさを表す値 になっています。, 学習率が大きすぎるとステップが大きくなりすぎて最小値を通り越してしまい(=オーバーシュート)、逆に学習率が小さすぎると1回の更新で少ししか動かなくなり収束まで果てしない時間がかかってしまいます。, データ全部を使ってその時の損失をプロットします。損失関数を今のパラメータ値で微分し、方向を求めます。出てきた方向に学習率をかけたら、その分だけパラメータ $w_1$ と $w_2$ を更新します。 この方法の名前が最急降下法 です。, まず、単語の意味ですが、最急降下というのは、損失関数においてある点から損失を最も急に降下させる(方向)ということです。 業務概要 ・自社サービスである『Loogia(ルージア)』のルート最適化エンジンの開発 ・組合せ最適化やアルゴリズム・データ構造の知識が活かし、効率的なエンジンの開発を進めます ・処理スピードと開発コストのバランスを見ながら、モジュールごとにJavaとPythonを使い分けています。 6), 遺伝的アルゴリズムは以上にあげたような、環境への適応度を求める評価、生き残る個体を決める選択、生き残った個体で遺伝情報を交換する交叉、そして多様性を担保するための突然変異、これら4つのプロセスを繰り返すことで構成されています。, 遺伝的アルゴリズムのフローチャートはFig. これらの最適化アルゴリズムは全て最急降下法の派生で、最急降下法さえ理解すれば他の最適化アルゴリズムは理解できてしまう のです。 1. More than 1 year has passed since last update. さらにはやく損失関数の最小値にたどり着きたいというモチベーションがあります。 $$, 目的関数がふたつになったからどうした、と思われるかもでしれませんがそれなりに影響が出るようになります。, 先ほどの「窓の大きさ」を引数とした「日照時間」と「電気代」の最適化問題をみてみましょう。 これでSGDの説明は終わりなのですが、なぜこれで極小値に陥ることを解決してくれるのか、ということに少し触れます。 例として「窓の大きさ」とを引数にしたときの「日照時間」と「電気代」を目的関数にしたときの最適化問題などがあげられます。 clipnormとclipvalueはすべての最適化法についてgradient clippingを制御するために使われます:. オミータです。ツイッターで人工知能のことや他媒体で書いている記事など を紹介していますので、人工知能のことをもっと知りたい方などは気軽に@omiita_atiimoをフォローしてください!, 深層学習を知るにあたって、最適化アルゴリズム(Optimizer)の理解は避けて通れません。 多目的最適化問題はこのパレート最適曲面をみつける問題です。, 多目的最適化問題の評価関数もかなり複雑な構造をしたものがいくつかあります。 (手順1)その時のデータ1000個を使ってまずは予測値を1000個出します。(手順2)正解値との損失をMSEで定義します。ここで、手順3の微分に移る前に実際に1000個の損失を計算したとして、その1000個の損失の総和を全体の損失として図にプロットしてみましょう。, 手順3からは現在の $w_1, w_2$ による損失よりも小さい損失となるように、 $w_1$ と $w_2$ を微調整します。その微調整には次の2点を決める必要があります。, のです。 Copyright © 2020 Yamakura's Blog All Rights Reserved. 8に示したような遺伝子の構成を用います。一個体の遺伝子は、巡る都市が順々に並んでいるベクトルです。したがってその長さは都市の数と等しくなります。例えば、都市が5つ存在している場合は、[0, 1, 2, 3, 4][2, 4, 1, 0, 3]などのような個体が考えられます。, また一世代の内に複数個体を作るのでその個体数をm、都市の数をnとすると一世代の遺伝子はm×nの行列で表せます。, 都市の数と個体数を入力して初期個体をランダムで生成して行列の形で出力する関数を実装します。, 各要素に格納されている数字は巡る都市を指しています。したがってint型であることを明示的にしています。またここで登場している数字はgenerate_rand_citiesの行数と対応させて使用します。, 今回はTSPに即した遺伝子の構成であり、他の構成の仕方としては複数同じものが選ばれるもの、ナップザック問題で使われる対立遺伝子が0と1で表現されるものなどさまざまあります。, 次はその遺伝子がどれほど環境に適合しているか?今回のTSPに即して言えばどれほど経路が短いか?を評価します。といっても距離を測るだけなのであまり難しくはないです。, 賢い方法としては2点間の距離のテーブルを作って、順序に合わせて参照する方法があります。が、今回は頭良くない方法でいきます。具体的にはその都度、都市を参照して距離を計算します。, まずは一個体の距離の総和を求める関数から実装します。入力は都市の位置と遺伝子、出力は距離の値です。, 使用例では個体数の分だけfor文で計算して個々の遺伝子に対して経路の長さを求めています。for文書くのも野暮ったいしベクトルとしてまとめて出力したいのでさらに一世代分まるごと経路の長さを求めて出力する関数を実装します。, 選択の内でも交叉する両親を選ぶものと、ダイレクトに子孫として残す個体を選ぶものの2種類存在します。前者にはルーレット選択やランキング選択などがあり、後者にはエリート選択があります(Fig. ここで、1階微分ではなく2階微分まで使ったらどうでしょうか 。つまり、更新式が以下のような場合はどうなのでしょうか。, $$ また、pandasは内部でnumpyを利用している。, numpyは、CやFortranで書かれた高度に最適化された線形代数ライブラリを使用しており行列計算を効率よく計算することができる。, CBC: COINプロジェクトの無料ソルバー(COIN-OR Branch and Cut の略), you can read useful information later efficiently. 実はここから説明する派生系ではこの式の第二項における モーメンタムは勾配(微分)を、RMSPropは学習率をいじっているだけ なのです。, このようにどちらもSGDに一工夫を加えているだけですのでここまで理解できていれば、ここからは難しいところは特にありません。ここからは微分をより正確に 勾配 と呼ぶことにします。ただ、これまでのように勾配は関数のある点での傾きの方向を表していると考えていて大丈夫です。, モーメンタム(Momentum)は、損失関数上での今までの動きを考慮することでSGDの振動を抑える と言う考えで導入されました。, 移動平均とは経済でよく使われ、急な変化があるグラフに対して移動平均を用いるとその変化がゆるやかになったグラフが得られる優れものです。(正確には指数平滑移動平均という仰々しい名前がついていますが、ここではわかりやすく移動平均に統一します。), オリジナルの青線に対して移動平均を用いているのが赤線のグラフ。 ただ よくよく見るとAdamの正体がモーメンタムとRMSPropを組み合わせただけ、というのがわかると思います。 (英語) Andrew Ng氏による移動平均とモーメンタムの解説動画。, Understanding Nesterov Momentum (NAG) わかりやすさのため、上の2個のポイントをそれぞれ, それでは最急降下法における、パラメータ値を増やすか減らすかを決めるプロセスを見ていきます。, 赤丸が現在のパラメータに対する損失を表しています。図のような位置に赤丸が損失関数に位置するときは $w_1$ と $w_2$ ともに小さくした方が良さそうです。, 現在の損失(赤丸)が上のように位置するのであれば $w_1$ は大きくし、 $w_2$ は小さくした方が良さそうです。 1. 赤い面が真のパレート最適曲面です。青い点がそれぞれひとつのParticleです。, 以上で最適化、多目的最適化問題、多目的最適化アルゴリズムへの入門が完了したつもりなのですが、いかがでしたか?, 実際に実装するときはもう少し複雑な内容になるのですが、そこが気になる人は多目的PSOのソースコードをここに貼ったので読んでみてください。 時間の都合で実行できるフォーマットじゃないのですが近いうちにコードをきれいにしてリポジトリをまとめておきます。, 遺伝的アルゴリズムを用いた多目的最適化アルゴリズムに興味がある方はこの論文 A fast and elitist multiobjective genetic algorithm: NSGA-II がオススメです。そして宣伝ですが、NSGA-IIを実装したのでよかったら見てください。こっちは実際に実行できます。, また、例として挙げていた窓の大きさを使った多目的最適化問題は BPOpt: A Framework for BIM-Based Performance Optimization.で実際に扱われています。, 多目的最適化はこの記事で紹介しきれるほど小さい分野ではないので Survey of Multi-objective Optimization Methods for Engineering. ここではそもそもの最適化アルゴリズムと損失関数の意味から入り、最急降下法から最適化アルゴリズムの大定番のAdamそして二階微分のニュートン法まで順を追って 図をふんだんに使いながら丁寧に解説 していきます。 PuLPは、数理モデリングのパッケージであり、pandasはデータ分析のパッケージである。, pandasは、モデルに含まれるデータの中で、表で表現できるデータを扱うのに適しており、複雑な処理をわかりやすく記述できる。 デフォルトでは、CBCが使われます。PuLPをインストールすると、CBCも同時にインストールされます。, PuLPで扱うことができる問題は、混合整数最適化問題です。 まず第1式ですが、何か見たことありますね。 child1 = np.copy(parent1) 私たちがなんとなく勝手に決めちゃうようなパラメータのことを ハイパーパラメータ と言い、他にハイパーパラメータの仲間として、「ニューラルネットワークの層の数」や「1層におけるニューロン(ユニット)の数」などがあります。, 今回のどれだけ変化させるかを決定するハイパーパラメータのことを 学習率 と言います。 What is going on with this article?