最急降下法

多くの場合、学習の問題は、与えられた評価関数を最適とするようなパラメー タを求める問題として定式化されます。従って、学習のためには、その最適化 問題を解くための手法が必要になります。最適化手法には、簡単なものから高 速性や安定性のために工夫した複雑手法まで、多くの手法がありますが、ここ では、最も簡単な最適化手法のひとつである最急降下法と呼ばれる最適化手法 の基本的な考え方について理解し、そのプログラムを作ってみることにします。

例題として以下のような問題を考えてみることにします。

問題1.

あるパラメータ$a$の良さの評価尺度が以下のような２次 の関数

$$f(a) = (a - 1.0)^2$$ (1)

で与えられたとします。このとき、この評価関数が最小となるパラメータ $a$ の(最適解)を求めなさい。

図 1: 評価関数$f(a)$およびその微分

このような問題は、一般に最適化問題と呼ばれています。図 1(a) に評価関数のグラフを示します。この問題のように評価 関数$f(a)$がパラメータ$a$に関して２次の関数の場合には、最適なパラメー タはただひとつに決まり、その解も以下のような方法で簡単に求まります。

解析的な解法

式(1)のパラメータ$a$に関する微分を求めると

$$\frac{\partial f(a)}{\partial a} = 2 (a - 1.0)$$ (2)

となります。ここで考えている2次の評価関数の場合、微分が$0$となる点が最小値 となりますので、この評価関数を最小とする最適な$a$は、

$$\frac{\partial f(a)}{\partial a} = 2 (a - 1.0) = 0$$ (3)

から、$a = 1.0$であることがわかります。実際、式(1)の $a$に$1.0$を代入してみると、 $f(1.0)=(1.0-1.0)^2=0.0$となります。評価関 数$f(a)$は$0$以上の関数（非負の関数）であることから、$a = 1.0$で最小値 $0.0$を取ることが確かめられます。

最急降下法

最急降下法は、ある適当な初期値(初期パラメータ)からは じめて、その値を繰り返し更新する(修正する)ことにより、最適なパラメータ の値を求める方法(繰り返し最適化手法)の最も基本的で簡単な方法です。

問題1のような評価関数が最小となるパラメータを求める問題では、最急降下 法でのパラメータの更新は、

$$a^{(k+1)} = a^{(k)} - \alpha \frac{\partial f(a)}{\partial a}\vert _{a=a^{(k)}}$$ (4)

のようになります。ここで、$a^{(k)}$ は、$k$ 回目の繰り返して得られたパ ラメータ$a$の推定値で、 $\frac{\partial f(a)}{\partial a}\vert _{a=a＾ {(k)}}$は、$a=a^{(k)}$での評価関数のパラメータ$a$に関する微分値です。 また、$\alpha$は、1回の繰り返しでどれくらいパラメータを更新するかを制 御する小さな正の定数で、学習係数と呼ばれたりします。つまり、最急降下法 では、パラメータの値を微分値と逆の方向にちょっとだけ変化させて徐々に最 適なパラメータに近づけて行きます。そのため、学習係数$\alpha$の値を大き くすると1回の繰り返しでパラメータの値を大きく更新できますが、大きすぎ ると最適なパラメータの近くで値が振動してしまったり、発散してしまったり します。逆に、小さくしすぎると1回の更新ではパラメータの値がほとんど修 正されず、最適なパラメータが求まるまでの繰り返し回数が多く必要になりま す。そのため、最急降下法では、この値を適切に設定することが重要です。

それでは、問題1の最適なパラメータ$a$の値を最急降下法で求めるための具体 的な更新式を求めてみましょう。

評価関数$f(a)$のパラメータ$a$に関する微分は、先に求めたように

$$\frac{\partial f(a)}{\partial a} = 2 (a - 1.0)$$ (5)

のようになります。 これを最急降下の更新式に代入すると、パラメータの更新 式は、

$$a^{(k+1)} = a^{(k)} - 2 \alpha (a^{(k)} - 1.0)$$ (6)

となります。図1(b) に評価関数$f(a)$のパラメータ$a$に関 する微分 $\frac{\partial f(a)}{\partial a}$のグラフを示します。このグ ラフからパラメータの現在の推定値が$1.0$以上の場合には、微分は正となり、 現在の$a$の推定値より小さな値に更新され、逆に$1.0$以下の場合には、微分 は負となり、現在の推定値より大きな値に更新されます。その結果、いずれの 場合でも$1.0$に近付く方向に更新されるようになります。

この更新式を使って評価関数が最小となる $a$ の値（最適解）を求めるプ ログラムを作ると、以下のようになります。

/*
 * Program to find the optimum value 
 * which minimizes the function f(a) = (a - 1.0)^2
 * using Steepest Decent Method
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


double f(double a) {
  return((a-1.0)*(a-1.0));
}

double df(double a) {
  return(2.0*(a-1.0));
}

main() {
  double a;
  int    i;
  double alpha = 0.1; /* Learning Rate */

  /* set the initial value of a by random number within [-50.0:50.0] */
  a = 100.0 * (drand48() - 0.5);
  printf("Value of a at Step 0 is %f, ", a);
  printf("Value of f(a) is %f\n", f(a));

  for (i = 1; i < 100; i++) {
    /* update theta by steepest decent method */
    a = a - alpha * df(a);
    printf("Value of a at Step %d is %f, ", i, a);
    printf("Value of f(a) is %f\n", f(a));  }
   
}

ここで、関数 $f$ は、最適化したい評価関数（２次関数）で、その微分が $df$ です。求めたい$a$の最初値をランダムな値で初期化し、先の更新式に従っ て、100回更新しています。更新の際の学習係数が $\alpha$ で、このプログラ ムでは、0.1 に設定しています。

このプログラムを適当なコンピュータでコンパイルして、走らせると 以下のような結果が得られます。

Value of a at Step 0 is -50.000000, Value of f(a) is 2601.000000
Value of a at Step 1 is -39.800000, Value of f(a) is 1664.640000
Value of a at Step 2 is -31.640000, Value of f(a) is 1065.369600
Value of a at Step 3 is -25.112000, Value of f(a) is 681.836544
Value of a at Step 4 is -19.889600, Value of f(a) is 436.375388
Value of a at Step 5 is -15.711680, Value of f(a) is 279.280248
Value of a at Step 6 is -12.369344, Value of f(a) is 178.739359
Value of a at Step 7 is -9.695475, Value of f(a) is 114.393190
Value of a at Step 8 is -7.556380, Value of f(a) is 73.211641
Value of a at Step 9 is -5.845104, Value of f(a) is 46.855451
Value of a at Step 10 is -4.476083, Value of f(a) is 29.987488
Value of a at Step 11 is -3.380867, Value of f(a) is 19.191993
Value of a at Step 12 is -2.504693, Value of f(a) is 12.282875
Value of a at Step 13 is -1.803755, Value of f(a) is 7.861040
Value of a at Step 14 is -1.243004, Value of f(a) is 5.031066
Value of a at Step 15 is -0.794403, Value of f(a) is 3.219882
Value of a at Step 16 is -0.435522, Value of f(a) is 2.060725
Value of a at Step 17 is -0.148418, Value of f(a) is 1.318864
Value of a at Step 18 is 0.081266, Value of f(a) is 0.844073
Value of a at Step 19 is 0.265013, Value of f(a) is 0.540207
Value of a at Step 20 is 0.412010, Value of f(a) is 0.345732
Value of a at Step 21 is 0.529608, Value of f(a) is 0.221269
Value of a at Step 22 is 0.623686, Value of f(a) is 0.141612
Value of a at Step 23 is 0.698949, Value of f(a) is 0.090632
Value of a at Step 24 is 0.759159, Value of f(a) is 0.058004
Value of a at Step 25 is 0.807327, Value of f(a) is 0.037123
Value of a at Step 26 is 0.845862, Value of f(a) is 0.023759
Value of a at Step 27 is 0.876690, Value of f(a) is 0.015205
Value of a at Step 28 is 0.901352, Value of f(a) is 0.009731
Value of a at Step 29 is 0.921081, Value of f(a) is 0.006228
Value of a at Step 30 is 0.936865, Value of f(a) is 0.003986
Value of a at Step 31 is 0.949492, Value of f(a) is 0.002551
Value of a at Step 32 is 0.959594, Value of f(a) is 0.001633
Value of a at Step 33 is 0.967675, Value of f(a) is 0.001045
Value of a at Step 34 is 0.974140, Value of f(a) is 0.000669
Value of a at Step 35 is 0.979312, Value of f(a) is 0.000428
Value of a at Step 36 is 0.983450, Value of f(a) is 0.000274
Value of a at Step 37 is 0.986760, Value of f(a) is 0.000175
Value of a at Step 38 is 0.989408, Value of f(a) is 0.000112
Value of a at Step 39 is 0.991526, Value of f(a) is 0.000072
Value of a at Step 40 is 0.993221, Value of f(a) is 0.000046
Value of a at Step 41 is 0.994577, Value of f(a) is 0.000029
Value of a at Step 42 is 0.995661, Value of f(a) is 0.000019
Value of a at Step 43 is 0.996529, Value of f(a) is 0.000012
Value of a at Step 44 is 0.997223, Value of f(a) is 0.000008
Value of a at Step 45 is 0.997779, Value of f(a) is 0.000005
Value of a at Step 46 is 0.998223, Value of f(a) is 0.000003
Value of a at Step 47 is 0.998578, Value of f(a) is 0.000002
Value of a at Step 48 is 0.998863, Value of f(a) is 0.000001
Value of a at Step 49 is 0.999090, Value of f(a) is 0.000001
Value of a at Step 50 is 0.999272, Value of f(a) is 0.000001
Value of a at Step 51 is 0.999418, Value of f(a) is 0.000000
Value of a at Step 52 is 0.999534, Value of f(a) is 0.000000
Value of a at Step 53 is 0.999627, Value of f(a) is 0.000000
Value of a at Step 54 is 0.999702, Value of f(a) is 0.000000
Value of a at Step 55 is 0.999761, Value of f(a) is 0.000000
Value of a at Step 56 is 0.999809, Value of f(a) is 0.000000
Value of a at Step 57 is 0.999847, Value of f(a) is 0.000000
Value of a at Step 58 is 0.999878, Value of f(a) is 0.000000
Value of a at Step 59 is 0.999902, Value of f(a) is 0.000000
Value of a at Step 60 is 0.999922, Value of f(a) is 0.000000
Value of a at Step 61 is 0.999937, Value of f(a) is 0.000000
Value of a at Step 62 is 0.999950, Value of f(a) is 0.000000
Value of a at Step 63 is 0.999960, Value of f(a) is 0.000000
Value of a at Step 64 is 0.999968, Value of f(a) is 0.000000
Value of a at Step 65 is 0.999974, Value of f(a) is 0.000000
Value of a at Step 66 is 0.999980, Value of f(a) is 0.000000
Value of a at Step 67 is 0.999984, Value of f(a) is 0.000000
Value of a at Step 68 is 0.999987, Value of f(a) is 0.000000
Value of a at Step 69 is 0.999990, Value of f(a) is 0.000000
Value of a at Step 70 is 0.999992, Value of f(a) is 0.000000
Value of a at Step 71 is 0.999993, Value of f(a) is 0.000000
Value of a at Step 72 is 0.999995, Value of f(a) is 0.000000
Value of a at Step 73 is 0.999996, Value of f(a) is 0.000000
Value of a at Step 74 is 0.999997, Value of f(a) is 0.000000
Value of a at Step 75 is 0.999997, Value of f(a) is 0.000000
Value of a at Step 76 is 0.999998, Value of f(a) is 0.000000
Value of a at Step 77 is 0.999998, Value of f(a) is 0.000000
Value of a at Step 78 is 0.999999, Value of f(a) is 0.000000
Value of a at Step 79 is 0.999999, Value of f(a) is 0.000000
Value of a at Step 80 is 0.999999, Value of f(a) is 0.000000
Value of a at Step 81 is 0.999999, Value of f(a) is 0.000000
Value of a at Step 82 is 0.999999, Value of f(a) is 0.000000
Value of a at Step 83 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 84 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 85 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 86 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 87 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 88 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 89 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 90 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 91 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 92 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 93 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 94 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 95 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 96 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 97 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 98 is 1.000000, Value of f(a) is 0.000000
Value of a at Step 99 is 1.000000, Value of f(a) is 0.000000

パラメータ$a$の更新が繰り返されると、次第に 1.0 に近付き、それと同時に 評価関数 $f(a)$ の値が 0.0 に近付いて行く様子がわかると思います。

次に、応用問題として、以下のような問題の最適解を最急降下法で求めるため のプログラムも作成してみてみましょう。

応用問題1.

あるパラメータ$a$の良さの評価尺度が以下のような４次 の関数

$$f(a) = (a - 1.0)^2 (a + 1.0)^2$$ (7)

で与えられたとします。このとき、この評価関数の意味で最も良いパラメータを 求めなさい。

この場合には、解は一意に決まらず、初期値に依存します。いろいろと初期値 を変えて解への収束の様子を調べてみてください。

ヒント

この評価関数 $f(a)$ のパラメータ$a$に関する微分は、

$$\frac{\partial f(a)}{\partial a} = 4.0 a (a - 1.0) (a + 1.0)$$ (8)

のようになります。

評価関数およびその微分を図2(a)および(b)に示します。

図 2: 評価関数$f(a)$およびその微分