Math＆Julia #10｜勾配降下法 » 一変数関数の最小点を探索

はじめに

勾配降下法を使って目的関数（今回は一変数関数）の最小点$x$を探索することを考えます。もし、目的関数の導関数を手計算で求められるなら、自動微分などの特別な機能を使わずに、標準的な関数のみでシンプルな実装が可能です。そして、このような実装を行うことによって勾配降下法の基本的なこと（導関数や学習率の役割など）に対する理解が深まります。

勾配降下法（一変数関数）

勾配降下法の基本的なアイデアは、関数 $f(x)$ の接線の傾きを手がかりに、最小点$x$を求めて少しずつ降下していくというものです。

図 1　勾配降下法（一変数関数）

停留点の分類

停留点は $f'(x)=0$ の場所において、二階導関数の符号から次の 3種類に分類されます。

• $f''(x)>0$：極小点（その点の周辺で関数値が最小となる点）
• $f''(x)<0$：極大点（その点の周辺で関数値が最大となる点）
• $f''(x)=0$：変曲点（極大でも極小でもない点）※1

探索で見つけたいのは最小点$x$ですが、これは停留点の 1つである極小点に含まれます。最小点にはこのような性質があるため、単純な探索では目標とは異なる停留点に囚われやすくなり、真の最小点を見つけるのが困難です。

※1：多変数関数の場合は「鞍点」がこれに相当します。

目的関数と更新式

目的関数

次の関数について最小点を探索します。関数には図 1と形状が似たものを選定しました。

$$\tag{1}f(x) = x^4 - 20x^2 + 20x$$

目的関数の導関数

考え方の分かる実装にしたいので、自動微分を使わずに手計算で目的関数の導関数を求めます。

$$\tag{2}f'(x) = 4x^3 - 40x + 20$$

停留点を評価するには二階導関数が必要です。これについては「停留点の分類」ですでに触れています。

$$\tag{3}f''(x)=12x^{2}−40$$

最小点の解析解

今回の目的関数の最小点$x$は解析的に求めることができます。途中式は本筋と関係ないので省略して結果だけ示します。最小点の解析解はハンズオンで参照します。参考として、最小値 $f(x)$ も併記しておきます。

$$\tag{4}\begin{aligned}x​&≈−3.3876190585\\f(x​)&≈−165.5739147\end{aligned}$$

勾配降下法の更新式

式$(2)$に学習率$η$を掛けると $x$ の更新量が決まります。

$$\tag{5}x_{n+1}=x_{n}-η\,f'(x_{n})$$

・$η$ は学習率で $0.01$ のような小さな値

実装

すでに、単純な探索では真の最小点$x$を見つけるのが困難であることが分かっています。これを踏まえると、区間全体を走査して得られたすべての停留点の中から最小点を選び出すという実装も考えられます。しかし、本稿では分かりやすさを重視して単純な実装を行い、これに探索の開始点や学習率といったパラメータを恣意的に設定することで最小点を求めます。このような方法は、グラフの形状を知っている（つまり最小点のおおよその位置を知っている）からこそできる技ですが、勾配降下法の考え方を理解するのに適しています。

Julia

using CairoMakie, Printf

# 勾配降下法で目的関数の停留点を探索
function gradient_descent(df::Function, x::Float64, η::Float64; ε=1e-10, max_iter=100)
    log = Float64[x]                    # 探索ログ（xの軌跡を記録）
    for i in 1:max_iter
        x_new = x - η * df(x)           # 現在地点の傾きをもとに次の探索地点を決める（勾配降下法）
        push!(log, x_new)               # 探索ログを更新
        abs(x_new - x) < ε && break     # 許容誤差内であれば早期打ち切りへ
        x = x_new                       # 次の探索地点へ移動
    end
    log
end

# 探索の軌跡を可視化
function vis_gradient_descent(gp::GridPosition, fn::String, f::Function, log::Vector{Float64}, η::Float64)
    xs, xe   = log[1], log[end]                   # 探索ログから開始地点と終了地点を取得
    eta      = @sprintf "η = %.3f"        η       # 学習率
    iter     = @sprintf "iter = %d"       length(log)-1  # 反復回数（初期値の分を-1）
    label_xs = @sprintf "start: x = %.2f" xs      # 開始地点の凡例
    label_xe = @sprintf "end : x = %.2f"  xe      # 終了地点の凡例
    title    = fn * "  " * eta                    # タイトル（図番＋学習率η）
    xlo, xhi = -6,   6                            # x軸の区間
    ylo, yhi = -200, 250                          # y軸の区間
    xticks   = xlo:2:xhi                          # x軸のグリッド線
    yticks   = ylo:50:yhi                         # y軸のグリッド線
    xvals    = xlo:0.1:xhi                        # x軸上の点の集合（目的関数の描画用）
    ax = Axis(gp, title=title, xticks=xticks, yticks=yticks, backgroundcolor=:gray98, xlabel="x", ylabel="f(x)")
    lines!(ax, xvals, f.(xvals), color=:steelblue)                             # 目的関数を描画
    scatterlines!(ax, log, f.(log), color=:dimgray, marker=:star4, markersize=8, linestyle=(:dash,2), linewidth=1)  # 軌跡を描画
    scatter!(ax, xs, f(xs), color=:darkorange, markersize=11, label=label_xs)  # 開始地点を描画
    scatter!(ax, xe, f(xe), color=:red3,       markersize=11, label=label_xe)  # 終了地点を描画
    text!(ax, 3, -100, text=iter, fontsize=14)                                 # 反復回数を描画
    xlims!(ax, xlo, xhi)                          # x軸の表示範囲を設定
    ylims!(ax, ylo, yhi)                          # y軸の表示範囲を設定
    axislegend(ax, position=:rb)
end

# 探索開始地点と学習率の組み合わせ変えながら停留点を探索
function sweep_gradient_descent(f::Function, df::Function, x::Float64, ηs::Vector{Float64})
    fig = Figure(size=(800, 750))
    gp  = GridPosition[fig[1,1], fig[1,2], fig[2,1], fig[2,2]]       # 4枚の図の配置場所
    fn  = String["(A)", "(B)", "(C)", "(D)"]                         # 4枚の図に付与する図番
    for (i, η) in enumerate(ηs)
        log = gradient_descent(df, x, η)                             # 停留点を探索
        vis_gradient_descent(gp[i], fn[i], f, log, η)                # 探索の軌跡を描画
    end
    display(fig)
    fig
end

ハンズオン

右側から探索を開始

探索の開始地点を $x=4.9$ に固定して、4通りの学習率$η$で探索を行います。

Julia

f(x)  = x^4 - 20x^2 + 20x               # 目的関数（一変数関数）
df(x) = 4x^3 - 40x + 20                 # 導関数

fig = sweep_gradient_descent(f, df,  4.9, [0.032, 0.031, 0.013, 0.004])  # 右側から4通りの学習率を試す
save("10-start=r.png", fig)

図 2　右側から探索を開始

右側からの探索は、すべて失敗に終わりました。(A)，(C)，(D) は極小点に囚われています。(B)は惜しいように見えますが、反復回数（iter）の上限である100に到達して強制打ち切りになっているので収束の質が悪いです。

左側から探索を開始

探索の開始地点を $x=-5.5$ に固定して、4通りの学習率$η$で探索を行います。

Julia

fig = sweep_gradient_descent(f, df, -5.5, [0.025, 0.023, 0.013, 0.003])  # 左側から4通りの学習率を試す
save("10-start=l.png", fig)

図 3　左側から探索を開始

左側からの探索では (C) と (D) の終了地点が $x=-3.39$ になっています。これを解析解（ $x​≈−3.3876$）と比べると探索が成功していると判断できます。反復回数（iter）は(C)が23で(D)が64になっているので、(C)の方がスムーズに収束したと言えます。

ニューラルネットワークとの関連性について

• ニューラルネットワークでは勾配降下法によって損失関数を最小化しますが、それには改良されたアルゴリズムが使われています。
• ニューラルネットワークでの学習率$η$はハイパーパラメータとしてチューニングの対象であり、その値は実験的に決められます。
• 本稿では探索の開始地点$x$をグラフの形状を見て恣意的に決めています。この $x$ はニューラルネットワークの重み$w$に相当しますが、重み$w$は乱数によって初期化されます。