Алгоритм градиентного спуска и его варианты

Опубликовано: 25 Июля, 2021

Градиентный спуск - это алгоритм оптимизации, используемый для минимизации функции стоимости в различных алгоритмах машинного обучения. Он в основном используется для обновления параметров модели обучения.

Виды градиентного спуска:

  1. Пакетный градиентный спуск: это тип градиентного спуска, который обрабатывает все обучающие примеры для каждой итерации градиентного спуска. Но если количество обучающих примеров велико, то пакетный градиентный спуск требует больших вычислительных затрат. Следовательно, если количество обучающих примеров велико, то пакетный градиентный спуск не является предпочтительным. Вместо этого мы предпочитаем использовать стохастический градиентный спуск или мини-пакетный градиентный спуск.
  2. Стохастический градиентный спуск: это тип градиентного спуска, который обрабатывает 1 обучающий пример за итерацию. Следовательно, параметры обновляются даже после одной итерации, в которой был обработан только один пример. Следовательно, это намного быстрее, чем пакетный градиентный спуск. Но опять же, когда количество обучающих примеров велико, даже тогда он обрабатывает только один пример, что может быть дополнительными накладными расходами для системы, поскольку количество итераций будет довольно большим.
  3. Мини-пакетный градиентный спуск: это тип градиентного спуска, который работает быстрее, чем пакетный градиентный спуск и стохастический градиентный спуск. Здесь b примеров, когда b <m обрабатываются за итерацию. Таким образом, даже если количество обучающих примеров велико, они обрабатываются пакетами b обучающих примеров за один раз. Таким образом, он работает для более крупных обучающих примеров, а также для меньшего количества итераций.


    Используемые переменные:
    Пусть m - количество обучающих примеров.
    Пусть n будет количеством функций.

    Примечание: если b == m, то мини-пакетный градиентный спуск будет вести себя так же, как пакетный градиентный спуск.

    Алгоритм пакетного градиентного спуска:
    Пусть h θ (x) - гипотеза линейной регрессии. Тогда функция стоимости определяется как:
    Пусть Σ представляет собой сумму всех обучающих примеров от i = 1 до m.



     J поезд (θ) = (1 / 2m) Σ (h θ (x (i) ) - y (i) ) 2
    
    Повторить {
     θj = θj - (скорость обучения / м) * Σ (h θ (x (i) ) - y (i) ) x j (i)
        Для каждого j = 0… n 
    }

    Где x j (i) Представляет j- ю функцию i- го обучающего примера. Таким образом, если m очень велико (например, 5 миллионов обучающих выборок), то для схождения к глобальному минимуму требуются часы или даже дни. Вот почему для больших наборов данных не рекомендуется использовать пакетный градиентный спуск, поскольку это замедляет обучение.


    Алгоритм стохастического градиентного спуска:
    1) Произвольно перемешайте набор данных, чтобы параметры можно было обучать равномерно для каждого типа данных.
    2) Как упоминалось выше, учитывается один пример на итерацию.

     Следовательно,
    Пусть (x (i) , y (i) ) - обучающий пример.
    Стоимость (θ, (x (i) , y (i) )) = (1/2) Σ (hθ (x (i) ) - y (i) ) 2
    
    Поезд J (θ) = (1 / м) Σ Стоимость (θ, (x (i) , y (i) ))
    
    Повторить {
    
    Для i = от 1 до m {
    
             θ j = θ j - (скорость обучения) * Σ (h θ (x (i) ) - y (i) ) x j (i)
            Для каждого j = 0… n
    
                    } 
    }


    Алгоритм мини-пакетного градиентного спуска:
    Скажем, b - количество примеров в одной партии, где b <m.
    Предположим, что b = 10, m = 100;

    Примечание. Однако мы можем отрегулировать размер партии. Обычно его используют как степень 2. Причина этого в том, что некоторое оборудование, такое как графические процессоры, обеспечивает лучшее время работы с обычными размерами пакетов, такими как мощность 2.

    Повторить {
     Для i = 1,11, 21,… .., 91
    
        Пусть Σ - это сумма от i до i + 9, представленная k. 
    
        θ j = θ j - (скорость обучения / размер (b)) * Σ (h θ (x (k) ) - y (k) ) x j (k)
            Для каждого j = 0… n
    
    }
    

    Тенденции конвергенции в разных вариантах градиентных спусков:

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

    В случае стохастического градиентного спуска и мини-пакетного градиентного спуска алгоритм не сходится, а продолжает колебаться около глобального минимума. Следовательно, чтобы добиться сходимости, мы должны постепенно изменять скорость обучения. Однако сходимость стохастического градиентного спуска намного более шумная, поскольку за одну итерацию он обрабатывает только один обучающий пример.