\(\)

Градиентный спуск — это алгоритм, позволяющий найти локальный минимум функции.
На каждой итерации алгоритма делается шаг в направлении скорейшего спуска.
Градиентный спуск позволяет найти только локальный минимум, а не глобальный. Таким образом, результат зависит от того, с какой точки мы начнем.

Графически это можно представить так:

Формула каждой итерации градиентного спуска
$$\begin{align*}& \theta_j := \theta_j — \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) — y^{(i)}) \cdot x_j^{(i)} \; & \text{for j := 0…n}\end{align*}$$

Критерий сходимости

Алгоритм градиентного спуска — это численный алгоритм, и результатом его работы является приближенное значение. Каждый шаг алгоритма приближает результат и нужен критерий остановки алгоритма. Останавливать работу алгоритма нужно тогда, когда результат практически не улучшается. В виде формулы это можно представить так
$$\begin{align*}& f{(i)} — f{(i+1)} < \epsilon \text{ , где } \epsilon \text{- достаточно малое число} \end{align*}$$

Шаг алгоритма

Шаг алгоритма — это параметр альфа в формуле. Если он слишком большой — градиентный спуск начинает расходиться. В такой ситуации нужно уменьшить шаг алгоритма.

Вычисление производной на C#

Посчитать производную можно по следующей формуле:
$$\frac{f(x + \Delta x) — f(x — \Delta x)}{2 \Delta x} \text{ , где } \Delta x \text{- достаточно малое число}$$

На C# это будет выглядеть вот так:

public double GetDerivative(Func<double, double> function, 
    double point, double delta) {
    return (function(point + delta) - function(point - delta)) / 
       (2 * delta);
}

Реализация алгоритма

public List<double> Calculate (List<double> startPoint, 
    Func<List<double>, double> function) {
    double alpha = 1;
    var alphaDecreaseRate = 0.9;
    var currentPoint = startPoint;
    while (true) {
        var currentValue = function (currentPoint);
        var newPoint = new List<double> ();
        for (var i = 0; i < currentPoint.Count; i++) {
            Func<double, double> func = x => 
                function (CopyPointWithReplace (currentPoint, x, i));
            newPoint.Add (currentPoint[i] - 
                alpha * (1.0 / Convert.ToDouble(startPoint.Count)) * 
                new Derivative ().GetDerivative (func, currentPoint[i]));
        }
        var newValue = function (newPoint);

        if (newValue > currentValue)
            alpha *= alphaDecreaseRate;
        else {
            if (currentValue - newValue <= EPSILON)
                return newPoint;
            else
                currentPoint = newPoint;
        }
    }
}

Вспомогательный метод для копировании точки с заменой значения одной из координат:

private List<double> CopyPointWithReplace (List<double> point, 
    double replace, int replaceIndex) {
    var result = new List<double> ();
    for (var i = 0; i < point.Count; i++)
        if (i == replaceIndex)
            result.Add (replace);
        else
            result.Add (point[i]);

    return result;
}

он исползуется в выражении

Func<double, double> func = 
    x => function (CopyPointWithReplace (currentPoint, x, i));

Это выражение преобразует функцию нескольких переменных к функции одной переменной, фиксируя значения всех остальных переменных.

Пример использования

private double TestFunction(List<double> point)
{
    if (point.Count != 5)
    throw new ArgumentException("Size of vector should be 5");
    double result = 0;
    foreach(var value in point)
        result += (value - 2) * (value - 2);
    return result;
}

...

var minimumPoint = new GradientDescent().Calculate(
    new List<double>(){0,0,0,0,0}, TestFunction);

Исходный код

Исходный код доступен на гитхабе