TOC

3. 大量データの時代の極小値の求め方

3.1 大量のデータ, 多数の変数

従来と違う点

大量のデータ, 多変数（数個でなく, 数百, 数千？）
機械学習
例, 材料の開発にも機械学習が使われる時代 Deep Learningでは
- Classification 分類
- Regression 回帰

機械学習はすでに日常

エンジニアにとってひとつのツールである.
これを使って遊べばよろしい.

3.2 最適化アルゴリズム・極小値を求める

どんな手法がある？

いろいろな方法がある.
- 最適化に関する教科書, web サイトを参照.
次の 2 つについては原理とアルゴリズムを理解する
- Newton 法（極値を求める場合）
  - 演習でやってみる予定.
  - （非線形）方程式の根を求める方法.
  - \(f^{\prime}\) と \(f^{\prime\prime}\) が必要.
- Gradient descent 法（Deep Learning でよく使われる）
  - \(f^\prime\) だけでよい.
ほかにもいろいろな方法がある.
- Nelder-Mead 法

3.3 Newton 法

（非線形）方程式の解を求める方法.
最適化で極小値を求める場合, \(\frac{df}{dx} = 0\) の点を求める.

1 変数の場合

\(f(x) = 0\) の根を求める場合.

\[x^{[k+1]} = x^{[k]} - \frac{f(x^{[k]})}{f^\prime(x^{[k]})} \tag{3.1}\]

\[x^{[k+1]} = x^{[k]} - \left\{f^\prime(x^{[k]})\right\}^{-1}f(x^{[k]}) \tag{3.2}\]
\(f^\prime(x) = 0\) の根を求める場合

\[x^{[k+1]} = x^{[k]} - \left\{f^{\prime\prime}(x^{[k]})\right\}^{-1}f^\prime(x^{[k]}) \tag{3.3}\]

多変数の関数 \(f: \mathbb R^n \to \mathbb R^n\) の場合

\begin{align*} f(\boldsymbol x) = \begin{bmatrix} f_1(\boldsymbol x) \\ f_2 (\boldsymbol x) \\ \vdots \\ f_n (\boldsymbol x) \end{bmatrix} = \begin{bmatrix} f_1(x_1, \dotsc, x_n) \\ f_2(x_1, \dotsc, x_n) \\ \vdots \\ f_n(x_1, \dotsc, x_n) \end{bmatrix} \tag{3.4} \end{align*}

定義: ヤコビ行列

\begin{equation} J f(\boldsymbol x)= \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} & \cdots & \dfrac{\partial f_1}{\partial x_n} \\　\vdots & \ddots & \vdots \\ \dfrac{\partial f_n}{\partial x_1} & \cdots & \dfrac{\partial f_n}{\partial x_n}\end{bmatrix} \tag{3.5} \end{equation}

\(f(\boldsymbol x) = 0\) の根を求めるアルゴリズム

\[\boldsymbol x^{[k+1]} = \boldsymbol x^{[k]} - \underbrace{\left[J f(\boldsymbol x^{[k]}) \right]^{-1}}_{\mathbb R^n \times \mathbb R^n} \underbrace{f(\boldsymbol x^{[k]})}_{\mathbb R^n} \tag{3.6}\]

多変数関数 \(f:\mathbb R^n \to \mathbb R\) の \(\operatorname{grad} f (\boldsymbol x) = 0\) の解（停留点）を求める場合

グラディエント（勾配）とヘッセ行列の定義

\begin{equation} \nabla f (\boldsymbol x) = \operatorname{grad} f(\boldsymbol x) = \begin{bmatrix}\frac{\partial f}{\partial x_1} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{bmatrix} \tag{3.7} \end{equation}

\begin{equation} H f(\boldsymbol x) = \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \dots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \dots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix} \tag{3.8} \end{equation}

\(\operatorname{grad} f (\boldsymbol x) = 0\) の解を求めるアルゴリズム

\[\boldsymbol x^{[k+1]} = \boldsymbol x^{[k]} - \underbrace{\left[ H f(\boldsymbol x^{[k]}) \right]^{-1}}_{\mathbb R^n \times \mathbb R^n} \underbrace{ \operatorname{grad} f(\boldsymbol x^{[k]})}_{\mathbb R^n} \tag{3.9}\]

3.4 勾配降下法（最急降下法, gradient descent）

極小点を求める.
山の斜面を勾配が最大になる方向にくだっていくイメージ.
勾配が 0 の点で変化がなくなる.

\[\boldsymbol x^{[k+1]} = \boldsymbol x^{[k]} - \gamma_n \nabla f(\boldsymbol x^{[k]}) \tag{3.10}\]

\(\gamma\) は様々な名前で呼ばれている, 重み, 加速パラメーター, 学習率（機械学習での用語）
- \(\gamma\) の適切な値は問題によって異なる.
- \(\gamma\) が大きすぎると発散のおそれがある.
- \(\gamma\) が小さすぎると収束が遅くなる.
ニュートン法により単純
- 勾配（グラディエント）のみを計算すれば良い.
- 変数が多い時に有利.

例題 3.1

\(y= x^2\) の停留点を勾配降下法で求める.
初期値を \(x=1\) とする.
\(\gamma = 0.1, 0.4, 1\) としたときの値をステップ 3 まで求めよ.

[22]:

import numpy as np


def dfdx(x):
    return 2 * x


n = 3
x_0 = 1
gammas = [.1, .4, 1.0]
for gamma in gammas:
    x = x_0
    print('#### for gamma = {:.1f}'.format(gamma))
    for k in range(n):
        x = x - gamma * dfdx(x)
        print('k = {}, x = {:.4f}'.format(k, x))

#### for gamma = 0.1
k = 0, x = 0.8000
k = 1, x = 0.6400
k = 2, x = 0.5120
#### for gamma = 0.4
k = 0, x = 0.2000
k = 1, x = 0.0400
k = 2, x = 0.0080
#### for gamma = 1.0
k = 0, x = -1.0000
k = 1, x = 1.0000
k = 2, x = -1.0000

3.5 局所最適解と大域最適解（local and global optima）

停留点は必ずしも極小・極大ではないし,
極小・極大は必ずしも大域最小・大域最大ではない.
Newton 法も勾配降下法も, 初期値によって, 異なる極小・極大に収束.
大域最適解を求めるには?
最適化問題の永年の課題
ビッグデータ, 機械学習の応用面で様々な方法が試され今日に至る.

演習問題

3.1

関数電卓を使って以下の Newton 法を \(k=3\) まで実行する.
次の方程式の根をひとつ求めるためのステップを 5 つまで行う.

\[x^3 - x=0\]

\(f(x) = x^3 - x\) とおく.
初期値を \(x^{[0]} = 2\) に設定する.
\(x^{[k]}\) に対し
- \(f(x^{[k]})\), \(f^\prime (x^{[k]})\) を算出する.
- \(x^{[k + 1]}\) を式 (3.2) で計算する.

3.2

\(f(x) = x^3 - x\) の停留点をひとつ求めるためのステップを 5 つまで行う.
初期値を \(x^{[0]} = 2\) に設定する.
\(x^{[k]}\) に対し
- \(f^\prime (x^{[k]})\), \(f^{\prime\prime} (x^{[k]})\)を算出する.
- \(x^{[k + 1]}\) を式 (3.3) で計算する.

3.3

\(f(x) = x^3 - x\) の停留点をひとつ求めるためのステップを 5 つまで行う.
初期値を \(x^{[0]} = 1\) に設定する.
\(\gamma\) は各自設定せよ.
\(x^{[k]}\) に対し
- \(f^\prime (x^{[k]})\) を計算する.
- \(x^{[k + 1]}\) を式 (3.10) で計算する.

3.4

\(f(x) = x^3 - x\) のもうひとつの停留点を求めるために, \(y=-f(x)\) に対して勾配降下法をて適用する. ステップ \(k=5\) まで求めよ.
初期値を \(x^{[0]} = 0\) に設定する.
\(\gamma\) は各自設定せよ.
\(x^{[k]}\) に対し
- \(f^\prime (x^{[k]})\) を計算する.
- \(x^{[k + 1]}\) を式 (3.10) で計算する.

自習問題

3.1, 3.2 初期値を変えて, 収束する値がどのように変化するか調べよ.

◀ Previous

TOC

プロセス工学数学B