0. Descent Direction Iteration

本章では,局所近似モデルにより目標関数を最小化する方向に繰り返し移動するアルゴリズムを紹介する.これはDescent Direction Methodです.私が知っている代表的なモデルはGradient Descentです.具体的な事項は型番によって異なりますが、総じて以下の段階を経験します.

xkx kxk(この時点の位置)が終了条件を満たしているかどうかを確認します.

グラデーションや希西安などの局所情報を用いて,移動方向と大きさを含むベクトルdkd kdkを決定した.この場合、∣dk∣=1lvertd krvert=1∣dk∣=1でなくてもよい.

移動するステップの大きさまたは学習率と呼ばれるαk\alpha_kαkを決める.一部のアルゴリズムはこの値が定数のスカラーであり、一部のアルゴリズムは反復ごとに新しい値を計算します.xk+1←xk+αkdk\displaystyle x_{k+1}\leftarrow x_k +\alpha_k d_kxk+1​←xk​+αk​dk​

1. Line Search

所定の下降方向dddの場合、行順はstep factorα\alphaα最適化のための方法です.この場合の目的関数は次のとおりです.
minimizeαf(x+αd)\displaystyle minimize_{\alpha} f(x +\alpha d)minimizeα​f(x+αd)
ここで注意すべき点は、xxxとdddにはすでに与えられたベクトルが存在するため、スカラー値を使用することができます.α\alphaαすなわち,日変数の最適化を行う.すなわち,全体目標関数はベクトルであるため多変数最適化であるが,局所的にラインアレイを用いると,日変数最適化が行われる.
アルゴリズム全体は次のとおりです.首都コードとしては、運転が保証されていないことに注意してください.

import sympy as sp
def line_search(f, x, d):
	alpha = sp.symbol('a')
	obj = f(x + ad)
    a, b = bracket_minimum(obj)
    alpha = minimize(obj, a, b)
    return x + alpha*d

ここでtable minimize関数は、a、bの範囲内で括弧で囲まれた近似局所最小値の関数であるα\alphaα微分を行う関数.
しかし,このようにすれば,関数の微分には大きな演算量が要求される.これは精度が高いが、時間がかかる可能性があるため、step factorを学習率として固定することもできる.
Learning Rate Decay
ただし、学習率を定数に固定すると、次のような問題が発生する可能性があります.

lrの大きさが大きいと、初期には損失関数曲線に沿って急速に進入し、最も利点に近いが、付近ではオーバーシュートが続き、最終的には最も利点に達しない.

lrのサイズが小さい場合、凸関数の学習は非常に遅く、最適点に達する時間が長すぎる.あるいは局所極小値から抜け出せない.

では、この2つを組み合わせて、初期からlrに力を入れて、これから勉強が進むにつれて、勉強を減らすほうがいいのではないでしょうか.この概念を導入したのはLearning Rate Decayである.学習率減衰に関する学習点tの更新式は以下の通りである.
wˉ  ⟸  wˉ−αt∇J\displaystyle\bar{w}\impliedby\bar{w} -\alpha_t\nabla Jwˉ⟸wˉ−αt​∇J
このときαt\alpha_tαtは定数ではなく,学習点tttに対する関数である.一般的に使用される方法は、次のように指数関数的減衰と逆減衰です.
αt=α0(−k⋅t)(Exponential Decay)\tag{Exponential Decay}\displaystyle\alpha_t =\alpha_0(-k\cdot t)αt​=α0​(−k⋅t)(Exponential Decay)
αt=α01+k⋅t(Inverse Decay)\tag{Inverse Decay}\alpha_t = {\alpha_0\over 1 + k\cdot t}αt​=1+k⋅tα0​​(Inverse Decay)

上図に示すように、Exponential DecayとInverse DecayはTTTに対して幾何級数的に減少している.これにより,初期のlrは比較的大きく,損失関数曲線に沿って急速に低下し,最適点に近づくとlrは小さくなった.

2. Approximate Line Search(Armijo Backtracking Line Search)

既存のline searchメソッドは次のとおりです.α\alphaα過大な場合は減少する方法をとる.でもこれ.α\alphaα十分に小さくはできません.Armijo conditionと曲率conditionの追加α\alphaα 値段が付く.
2つの条件をウォルフ条件と呼ぶ.まず2つの条件を見てください.

2-1. Armijo Condition

このアレミヨ条件と呼ばれる条件は以下の式からなる.
f(xk+1)≤f(xk)+βα∇dkf(xk)f(x_{k + 1})\leq f(x_k) +\beta\alpha\nabla_{d_k}f(x_k)f(xk+1​)≤f(xk​)+βα∇dk​​f(xk​)
このとき、xk+1=xkβαdkx_{k+1} = x_k -\beta\alpha d_kxk+1​=xk​−βαdkなので、上の式はテイラーが展開した初めての微分港湾から導いたものです.
f(xk+1)≈f(xk)+(xk−βαdk−xk)∇dkf(xk)≈f(xk)−βαdk∇dkf(xk)\begin{aligned} f(x_{k+1}) &\approx f(x_k) +(x_k -\beta\alpha d_k - x_k)\nabla_{d_k}f(x_k)\\&\approx f(x_k) -\beta\alpha d_k\nabla_{d_k}f(x_k)\\\end{aligned}f(xk+1​)​≈f(xk​)+(xk​−βαdk​−xk​)∇dk​​f(xk​)≈f(xk​)−βαdk​∇dk​​f(xk​)​
この場合、グラデーションパレット上のdkd kdkは傾斜の反対方向であるため、dk87 dkf(xk)<0 dknabla dk}f(x k)<0 dk87 dkf(xk)<0であることを覚えておいてください.β∈[0,1]\beta\in [0, 1]β∈[0,1],普通β=1×10−4\beta = 1\times 10^{-4}β=1×10～4に設定されています.このとき、α\alphaα深さ学習で使われているのは小さな数ではなく、10程度の大きな数を表す.
上記の式は、次の移動点の値をある程度以上に減らしてこそ、実際の移動を導くことができることを意味します.

もし、もしβ=0\beta = 0β=0であれば、どの程度の減少を受け入れて移動するかを意味します.上図のようにf(xk)+βα∇dkf(xk)f(x_k) +\beta\alpha\nabla_{d_k}f(x_k)f(xk​)+βα△dkf(xk)は、現在の点に近づくと下降する直線を形成し、次の移動点は、関数f(x)f(x)f(x)f(x)との交点である.

2～2個のCurvation Condition（セカンダリーウォルフ条件）

曲率条件は、方向図関数の値が一定レベル未満の点に移動するように構成されます.
∇dkf(xk+1)≥σ∇dkf(xk)\displaystyle\nabla_{d_k}f(x_{k+1})\geq\sigma\nabla_{d_k}f(x_k)∇dk​​f(xk+1​)≥σ∇dk​​f(xk​)
このときβ<σ<1\beta <\sigma < 1β<σ<1に設定すると、関数の方向もどれだけ大きくする必要があるかを意味します.前述したように、グラデーションパレットでは、dkf(xk)nabla{dk}f(xk)8711 dkf(xk)が負であることを考慮して、最終的にこの式は次の点が現在の点よりもある程度0に近い値を持つようにします.すなわち、曲率を増加方向(2次導関数の値が増加した点)に移動させる.すなわち、global minimumに近づくほど、現在の点に対する方向が0に近づくほど、関数値がglobal minimumに近づくしかないことを意味する.

上記条件を満たす場合、α\alphaα検索アルゴリズムの単純なタグは次のとおりです.以下のとおりです.最終的に最初のウォルフの条件はα\alphaα確定した上限は、2回目のウォルフ条件が下限です.

def backtracking_line_search(f, df, x, d, a, p = 0.5, b = 0.0001, sig = 0.1):
	y, g = f(x), df(x)
    while f(x + a*d) > y + b*a*(g*d): # 1차 울프조건을 만족할때까지 a를 줄임
    	a *= p
    
    x_new = x + a*d
    
    if df(x_new) >= sig*df(x): # 2차 울프조건을 만족하는지 확인 
    	return x_new