5  モーメンタム法

チャプター 4 の最急降下法は，各反復で現在の勾配だけを使って進む方向を決める．そのため，谷が細長い形をしている場合には，谷を横切る方向に振動し，収束が遅くなることがある．

モーメンタム法は，過去の更新量を速度 \mathbf{v} として保持し，そこに現在の勾配を加えることでこの振動を抑える．更新式は以下のとおりである．

\mathbf{v}^{(k+1)} = \beta \mathbf{v}^{(k)} - \alpha \nabla f(\mathbf{x}^{(k)})

\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \mathbf{v}^{(k+1)}

ここで，\alpha はステップサイズ，\beta \in [0, 1) はモーメンタム係数である．\beta = 0 とすると \mathbf{v}^{(k+1)} = -\alpha \nabla f(\mathbf{x}^{(k)}) となり，最急降下法に一致する．\beta を大きくするほど過去の更新量の影響が長く残る．

5.1 アルゴリズム

\begin{algorithm} \caption{Momentum} \begin{algorithmic} \Require function $f$, gradient $\nabla f$, initial guess $\mathbf{x}^{(0)}$, step size $\alpha$, momentum parameter $\beta$, tolerance $\text{tol}$ \State $\mathbf{x} \gets \mathbf{x}^{(0)}$ \State $\mathbf{v} \gets \mathbf{0}$ \While{$\|\nabla f(\mathbf{x})\| > \text{tol}$} \State $\mathbf{v} \gets \beta \mathbf{v} - \alpha \nabla f(\mathbf{x})$ \State $\mathbf{x} \gets \mathbf{x} + \mathbf{v}$ \EndWhile \State \textbf{return} $\mathbf{x}$ \end{algorithmic} \end{algorithm}

5.2 Pythonによる実装

import numpy as np

def momentum(f, grad, x0, alpha=1e-3, beta=0.9, tol=1e-6):
    """
    Momentum (optimization algorithm)

    Parameters
    ----------
    f : function
        The function to minimize
    grad : function
        The gradient of the function
    x0 : np.ndarray
        Initial guess
    alpha : float
        Step size
    beta : float
        Momentum parameter
    tol : float
        Tolerance

    Returns
    -------
    x : np.ndarray
        The estimate of the minimum
    """
    x = x0
    v = np.zeros_like(x)
    while np.linalg.norm(grad(x)) > tol:
        v = beta * v - alpha * grad(x)
        x = x + v
    return x


def f(x):
    return x[0]**2 + x[1]**2

def grad(x):
    return np.array([2*x[0], 2*x[1]])

x0 = np.array([1.0, 1.0])
x = momentum(f, grad, x0)
print(x)