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

Введение

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

Интуиция градиентного спуска

Начнем с объяснения градиентного спуска. Это будет краткое описание, так как эта тема была подробно освещена, поэтому, пожалуйста, обратитесь к другим блогам или руководствам, если вам нужно более подробное объяснение.

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

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

Градиентный спуск для простой линейной регрессии

Возможно, самым простым примером для демонстрации градиентного спуска является Простая модель линейной регрессии. В этом случае наша гипотетическая функция, h(x), зависит от одной функциональной переменной, х:

Где θ_0 и θ_1являются параметрами модели. Функция потерь для этой задачи — это Ошибка суммы квадратов (SSE):

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

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

Затем эти параметры обновляются как:

Где η — это скорость обучения, определяющая размер шага, на который обновляется каждый параметр. Скорость обучения находится между нулем и единицей и определяет, насколько быстро мы приближаемся к минимуму. Если оно слишком велико, мы можем превзойти минимум, однако слишком маленькое приводит к большему времени вычислений. Поэтому необходимо найти золотую середину. Именно здесь используется настройка гиперпараметров с помощью таких методов, как сетка и случайный поиск или даже байесовский подход.

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

Аналитическое решение

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

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

Где x̅ и ȳ — это среднее значение данных и среднее значение целевой переменной соответственно. Следовательно, вычисляя эти средние значения, мы можем найти параметры, которые минимизируют функцию потерь, не используя итеративный подход!

Приведенное выше уравнение является аналитическим решением для Простой модели линейной регрессии. Это просто сокращенная версия общего решения для моделей линейной регрессии, где у нас может быть более двух неизвестных параметров:

Где Xэто матрица данных,Y,это матрица целевой переменной и ϴ — матрица параметров.

Почему тогда градиентный спуск?

Так почему же мы используем градиентный спуск, когда существует аналитическое решение? Этот ответ основан исключительно на затратах времени и места на вычисления.

Временная сложность градиентного спуска составляет O(kn²)где kколичество признаков и n — общее количество точек данных. Эта сложность может быть дополнительно улучшена с помощью векторизованных реализаций. Так сегодня реализовано большинство алгоритмов машинного обучения.

Однако общее аналитическое решение для линейной регрессии имеет временную сложность O(𝑛³). Поэтому для небольших наборов данных разница незначительна, но разница во времени вычислений растет экспоненциально по мере размер данных увеличивается. На практике большинство наборов данных содержат около 100 объектов с 1 миллионом строк. Таким образом, аналитическое решение для этих сценариев неприемлемо.

Кроме того, для некоторых моделей, таких как регрессия Пуассона и логистическая регрессия, установка нулевых производных приводит к набору нелинейных уравнений с > нет аналитического решения в закрытой форме,поэтому мы вынуждены использовать численные методы, такие как градиентный спуск.

Заключение

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

Надеюсь, вам понравилась эта статья, и вы узнали что-то новое! Есть много других статей, в которых более подробно рассматриваются некоторые из выводов, которые я сжал в этом посте, поэтому я бы порекомендовал их прочитать!

Свяжись со мной!

(Все эмодзи разработаны OpenMoji — проект эмодзи и иконок с открытым исходным кодом. Лицензия: CC BY-SA 4.0)

Что-то экстра!

Ниже показан пример кода, который я написал на C, чтобы продемонстрировать, как можно запрограммировать градиентный спуск!

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double dydx(double x);
int main(){
  int epochs, i; 
  double learning_rate, x, x_new;
  printf("Enter your intial guess integer: ");
  scanf("%lf", &x);      
 
  printf("Enter how many epochs: ");
  scanf("%d", &epochs);
  printf("Enter your learning rate: ");
  scanf("%lf", &learning_rate);
  for (i=1;i<epochs+1;++i){
   
    x_new = x;
    x_new = x_new - learning_rate*dydx(x_new);
    if ((x - x_new) < 0.000001){
      printf("number of epochs to coverge %d\n", i);
      break;  
   
    }
    x = x_new;
  }
  printf("The value of x that minimises is %lf", x);
}
double dydx(double x){
  return 2*x - 5;
}

Полный код можно найти на моем GitHub:



Medium-Articles/gradient_descent.c at main · egorhowell/Medium-Articles
Вы не можете выполнить это действие в данный момент. Вы вошли в другую вкладку или окно. Вы вышли на другой вкладке или…github.com