Тесты

Обучение по методу градиентного спуска на C#

James McCaffrey

Исходный код можно скачать по ссылке

Мое неформальное определение машинного обучения (machine learning, ML) — это система, которая использует данные для прогнозирования. Любой, кто начинает исследовать ML, быстро сталкивается с несколько загадочным словосочетанием «градиентный спуск» (gradient descent). В этой статье я поясню, что такое градиентный спуск, и продемонстрирую, как использовать его для обучения системы классификации по логистической регрессии.

Чтобы получить представление о том, куда я клоню в этой статье, взгляните на демонстрационную программу на рис. 1. Она начинает с генерации 10 000 элементов синтетических данных. При исследовании ML зачастую полезно использовать искусственные данные вместо реальных, так как вы можете управлять характеристиками данных. Каждый элемент данных имеет восемь значений переменных-предикторов (называемых функциями [features] в терминологии ML), за которыми следует единственная зависимая переменная — ее значение может быть либо 0, либо 1. Данные были сгенерированы, используя восемь случайных весовых значений (–7.78, –0.65, ... –7.97) плюс дополнительную константу (–5.02).

Рис. 1. Обучение классификатора по логистической регрессии с помощью градиентного спуска

Можете представить, что синтетические данные соответствуют задаче, в которой вы пытаетесь спрогнозировать пол человека (male = 0, female = 1) на основе восьми характеристик, таких как возраст, ежегодный доход, кредитная оценка и т. д., где все значения характеристик были отмасштабированы так, чтобы они укладывались в диапазон между –10.0 и +10.0.

После генерации 10 000 элементов данных демонстрационная программа случайным образом разбивает все данные на набор с 8000 элементами для обучения классификатора и набор с 2000 элементами для оценки точности прогнозирования полученной модели. Затем программа создает двоичный классификатор логистической регрессии и подготавливается к обучению по градиентному спуску, задавая значения для переменных maxEpochs (1000) и скорости обучения (0.01). Градиентный спуск — процесс итеративный, и переменная maxEpochs устанавливает лимит на количество итераций. Параметр скорости обучения я объясню позже, а пока можете считать его значением, которое управляет тем, сколько изменений происходит в модели классификатора по логистической регрессии на каждой итерации обучения.

Демонстрационная программа обучает классификатор и отображает ошибки модели на обучающих данных через каждые 100 итераций. Градиентный спуск можно использовать для обучения классификатора логистической регрессии двумя способами. Первый, более распространенный подход называют стохастическим, онлайновым или инкрементальным. (Терминология ML весьма хаотична.) Второй подход называют пакетным или офлайновым. Позже я опишу оба подхода, но демонстрационная программа применяет подход к обучению на основе стохастического градиентного спуска.

По окончании обучения программа выводит лучшие найденные весовые значения (–9.84, –14.88, ... –15.09). Заметьте, что все весовые значения модели примерно в два раза больше весовых значений, используемых при генерации случайных данных. Демонстрационная программа вычисляет точность полученной модели на обучающих данных (99.88%, или 7990 правильных значений из 8000) и на проверочных (99.80%, или 1996 правильных значений из 2000).

Классификация по логистической регрессии

Классификацию по логистической регрессии (logistic regression classification) лучше всего объяснить на конкретном примере. Допустим, вы хотите прогнозировать пол человека (male = 0, female = 1) на основе возраста (x1), ежегодного дохода (x2) и уровня образования (x3). Если Y — предсказанное значение, модель логистической регрессии для этой задачи приняла бы такую форму:

Z = b0 + b1(x1) + b2(x2) + b3(x3)
Y = 1.0 / (1.0 + e^-Z)

Здесь b0, b1, b2 и b3 — весовые значения, которые являются просто числами, подлежащими вычислению. Если на словах, то вы вычисляете промежуточное значение Z, которое представляет собой сумму входных значений, помноженных на b-веса с добавлением константы b0, а затем значение Z вы передаете в уравнение, использующее математическую константу e. Это уравнение называют логистической сигмоидной функцией (logistic sigmoid function). Заметьте, что каждая входная переменная (xi) имеет связанное весовое значение (bi), а также присутствует дополнительное весовое значение (b0), не связанное ни с каким входным значением.

Оказывается, Y всегда будет находиться в диапазоне от 0 до 1. Если Y меньше 0.5 (ближе к 0), вы заключаете, что прогнозируемый вывод равен 0, а если Y больше 0.5 — равен 1. Если вы располагаете n функциями (features), b-весов будет n+1. Не все данные можно смоделировать, используя логистическую регрессию, но, поскольку это один из простейших методов классификации, логистическая регрессия является хорошей отправной точкой.

Предположим, что некий человек имеет возрастную группу x1 = +0.80 (старше среднего), ежегодный доход x2 = –0.50 (чуть меньше среднего) и уровень образования x3 = –1.00 (меньше среднего). И допустим, что b0 = 3.0, b1 = –2.0, b2 = 2.0 и b3 = 1.5. Тогда Z = 3.0 + (–2.0)(0.80) + (2.0)(–0.50) + (1.5)(–1.00) = –1.10, а значит, Y = 1.0 / (1.0 + e^–(–1.10)) = 0.25. Поскольку Y ближе к 0 (меньше 0.5), вы прогнозируете, что этот человек мужчина (male).

Вот код из демонстрационной программы, реализующий вычисление вывода логистической регрессии:

public double ComputeOutput(double[] dataItem, double[] weights)
{
  double z = 0.0;
  z += weights[0]; // добавляем константу b0
  for (int i = 0; i < weights.Length - 1; ++i)
    z += (weights[i + 1] * dataItem[i]); // опускаем b0
  return 1.0 / (1.0 + Math.Exp(-z)); // логистическая сигмоида
}

Вопрос: откуда берутся b-веса? Процесс определения значений b-весов называют обучением модели. Идея в том, чтобы использовать набор обучающих данных, содержащий известные входные и выходные значения, а затем пробовать другие значения для b-весов, пока вы не найдете набор значений, которые минимизируют ошибку между вычисленными и известными правильными выходными значениями (этот набор часто называют целевыми, или желательными, значениями).

Найти весовые значения, которые минимизируют ошибку, трудно, и с этой целью можно применять множество алгоритмов численной оптимизации. У каждого алгоритма есть свои сильные и слабые стороны. К наиболее распространенным алгоритмам оптимизации относятся симплексная оптимизация, оптимизация L-BFGS, оптимизация роя частиц, итеративный метод Ньютона-Рафсона плюс еще примерно десяток других. Самый фундаментальный алгоритм оптимизации называется градиентным спуском.

Что такое градиентный спуск

Попробую разъяснить градиентный спуск с точки зрения разработчика ПО. Я позволю себе некоторые вольности в своем объяснении и терминологии, чтобы идеи были предельно ясными. Взгляните на график на рис. 2. На графике ошибка представлена как функция значения некоего веса. По мере изменения этого значения изменяется и ошибка получаемого классификатора логистической регрессии. Цель — найти весовое значение, при котором ошибка находится в минимуме. В случае рис. 2 это будет при w = 5.0. Здесь я использую w для обозначения любого из b-весов. Заметьте, что для каждого весового значения должно быть по одному графику, аналогичному представленному на рис. 2.

Рис. 2. Частные производные и градиентный спуск

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

Дифференцируемая производная (calculus derivative) функции в некоей точке является тангенсом угла наклона касательной прямой (slope of the tangent line) в этой точке. Угол наклона (slope) имеет знак (+ or –), который указывает направление касательной (tangent line), и величину, которая определяет крутизну наклона касательной. Например, на рис. 2, когда w = 7.0, наклон касательной прямой (иначе говоря, производной) равен +2.15 (сверху справа и вниз слева и имеет крутой наклон). Когда w = –5.0, производная равна –0.90 (сверху слева и вниз справа и не слишком крутой наклон).

Каждая индивидуальная производная называется частной, потому что производные имеются для каждого весового значения. Градиент — это набор всех частных производных. При повседневном применении термины «градиент» и «частная производная» часто употребляются как взаимозаменяемые в основном потому, что фраза наподобие «частная производная функции ошибки с учетом весового значения b2» куда труднее в произношении или написании, чем «градиент». Частные производные нередко обозначаются специальным математическим символом, который напоминает зеркальное отражение цифры 6.

Какой же в этом смысл? Если вы приглядитесь к рис. 2, то увидите, что частную производную можно использовать для перемещения от данного весового значения к тому весовому значению, где ошибка минимизируется. Знак частной производной указывает направление перемещения, а ее величина дает подсказку, насколько далеко следует сместиться; более высокая величина означает, что вы можете переместиться дальше, чем при меньшей величине. Этот прием называют градиентным спуском, поскольку вы движетесь вниз по графику функции ошибки к минимальному значению.

Что ж, пока неплохо, но как воплотить эту идею в пригодный для использования код? Или, другими словами, как выглядит псевдокод для обновления весового значения логистической регрессии? В Интернете много ресурсов, где демонстрируются некоторые весьма изощренные численные методы для вывода правила «вес-обновление». Конечный результат таков:

wj = wj + a * (target - computed) * xj

Если на словах, то «для j-того веса, новым весовым значением является старое весовое значение плюс произведение константы 'a' на разницу между целевым значением в обучающих данных и вычисленным выходным значением и на входное значение, связанное с j-тым весом». Правило обновления часто записывается греческими буквами, где тета (θ) обозначает весовое значение, а альфа (α) — константу. Константа «a» обычно называется скоростью обучения.

Допустим, вы работаете с весовым значением b2, где j = 2. И пусть текущее значение b2 равно 0.50. Если для какого-то элемента обучающих данных известное целевое значение равно 1, вычисленное выходное значение (с использованием всех x-значений) — 0.80, x2 (единственное входное значение, соответствующее весу b2) имеет значение 3.0, а скорость обучения — 0.10, тогда новое весовое значение b2 таково:

b2 = 0.50 + 0.10 * (1 - 0.80) * 3.0
b2 = 0.50 + 0.06
b2 = 0.56

Правило обновления применяется итеративно, пока не будет удовлетворено условие завершения. Заметьте, что вычисленный вывод (0.80) был слишком мал по сравнению с целевым выводом (1.0), поэтому правило обновления веса увеличило его значение. Это приведет к увеличению вычисленного выходного значения на следующей итерации обучения. Если бы вычисленный вывод был слишком велик по сравнению с целевым выводом, правило обновления уменьшило бы вес. Очень изящно!

Есть два основных способа вывести правило обновления весовых значений. Наиболее распространенный, который вы увидите по ссылкам на ресурсы в Интернете, начинается с определения вероятности получения набора обучающих данных для данного набора весовых значений, а затем используется весьма сложный численный метод, называемый ожиданием максимального правдоподобия (maximum likelihood expectation), чтобы найти значения параметров, которые максимизируют вероятность наблюдаемых данных.

Альтернативный подход начинается с определения того, что подразумевается под ошибкой, используя один из двух общих методов определения ошибки (суммы квадратичных отклонений или перекрестной энтропии). Далее используется численный метод, чтобы найти набор весовых значений, которые минимизируют ошибку. Если применяется ошибка перекрестной энтропии, полученное правило обновления веса идентично таковому, сгенерированному максимизацией вероятности. А если применяется сумма квадратичных отклонений, полученное правило обновления имеет два дополнительных члена:

wj = wj + a * (target - computed) * xj * computed * (1 - computed)

В альтернативном правиле обновления (из-за того, что член computed всегда находится в диапазоне 0–1) произведение computed и (1 – computed) будет всегда попадать в диапазон 0–0.25, т. е. обновление весовых значений при использовании альтернативного правила просто происходит меньшим шагом, чем в случае более простой формы. На практике оба правила обновления дают схожие результаты, поэтому в основном применяют более простую форму. К счастью, вам не нужно знать, как вывести правило обновления веса, чтобы обучить классификатор логистической регрессии.

Данный подход максимизирует вероятность за счет восхождения по градиенту, поэтому его называют градиентным подъемом (gradient ascent). Подход с выводом ошибки (error derivation approach) минимизирует ошибку за счет снижения по градиенту и называется градиентным спуском (gradient descent). Смысл в том, что обучение классификатора логистической регрессии с применением градиента называют как методом градиентного спуска, так и методом градиентного подъема. Оба термина относятся к одному и тому же правилу обновления веса.

Структура демонстрационной программы

Общая структура программы с небольшими правками для экономии места представлена на рис. 3. Чтобы создать демонстрационную программу, я запустил Visual Studio и выбрал шаблон C# Console Application. Я назвал проект LogisticGradient. В этой программе нет значимых зависимостей от .NET, поэтому подойдет любая версия Visual Studio. Демонстрационная программа слишком длинная, чтобы ее можно было представить в статье во всей ее полноте, но вы можете найти полный исходный код в сопутствующем этой статье пакете кода. Я убрал стандартную обработку ошибок, чтобы по возможности не затуманивать основные идеи.

Рис. 3. Структура демонстрационной программы

using System;
namespace LogisticGradient
{
  class LogisticGradientProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin classification demo");
      Console.WriteLine("Demonstrating gradient descent");
      ...
      Console.WriteLine("End demo");
      Console.ReadLine();
    }
    static double[][] MakeAllData(int numFeatures,
      int numRows, int seed) { . . }
    static void MakeTrainTest(double[][] allData, int seed,
      out double[][] trainData, out double[][] testData) { . . }
    static void ShowData(double[][] data, int numRows,
      int decimals, bool indices) { . . }
    static void ShowVector(double[] vector,
      int decimals, bool newLine) { . . }
  }
  public class LogisticClassifier
  {
    private int numFeatures;
    private double[] weights;
    private Random rnd;
    public LogisticClassifier(int numFeatures) { . . }
    public double[] Train(double[][] trainData,
      int maxEpochs, double alpha) { . . }
    private void Shuffle(int[] sequence) { . . }
    private double Error(double[][] trainData,
      double[] weights) { . . }
    private double ComputeOutput(double[] dataItem,
      double[] weights) { . . }
    private int ComputeDependent(double[] dataItem,
      double[] weights) { . . }
    public double Accuracy(double[][] trainData,
      double[] weights) { . . }
  }
}

После загрузки кода шаблона я переименовал в окне Solution Explorer файл Program.cs в более описательный LogisticGradientProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылку на пространство имен верхнего уровня System.

Класс LogisticGradientProgram включает вспомогательные методы MakeAllData, MakeTrainTest, ShowData и ShowVector, которые создают и отображают синтетические данные. Вся логика классификации содержится в классе LogisticClassifier. Метод Main создает синтетические данные с помощью следующих выражений:

int numFeatures = 8;
int numRows = 10000;
int seed = 1; // произвольно
double[][] allData = MakeAllData(numFeatures, numRows, seed);

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

double[][] trainData;
double[][] testData;
MakeTrainTest(allData, 0, out trainData, out testData);
ShowData(trainData, 3, 2, true);
ShowData(testData, 3, 2, true);

Разбиение данных на обучающий и проверочный наборы в соотношении 80% к 20% «зашито» в код метода MakeTrainTest. Вы могли бы передавать долю обучающего набора как параметр. Классификатор логистической регрессии создается и обучается так:

LogisticClassifier lc = new LogisticClassifier(numFeatures);
int maxEpochs = 1000;
double alpha = 0.01; // скорость обучения
double[] weights = lc.Train(trainData, maxEpochs, alpha);
ShowVector(weights, 4, true);

Значения для параметров maxEpochs и alpha (скорость обучения) определялись методом проб и ошибок. Тонкая настройка большинства обучающих методов ML, как правило, требует экспериментов для получения хорошей точности прогнозирования. Качество модели обучения оценивается следующим образом:

double trainAcc = lc.Accuracy(trainData, weights);
Console.WriteLine(trainAcc.ToString("F4"));
double testAcc = lc.Accuracy(testData, weights);
Console.WriteLine(testAcc.ToString("F4"));

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

Реализация обучения по методу градиентного спуска

Определение метода Train начинается с:

public double[] Train(double[][] trainData, int 
  maxEpochs, double alpha)
{
  int epoch = 0;
  int[] sequence = new int[trainData.Length];
  for (int i = 0; i < sequence.Length; ++i)
    sequence[i] = i;
...

Переменная epoch — это счетчик обучающего цикла. Массив sequence инициализируется индексами элементов обучающих данных. Здесь идея в том, чтобы обучающие данные обрабатывались в другом, случайном порядке на каждой итерации. Затем начинается основной цикл обновления весов:

while (epoch < maxEpochs)
{
  ++epoch;
  if (epoch % 100 == 0 && epoch != maxEpochs)
  {
    double mse = Error(trainData, weights);
    Console.Write("epoch = " + epoch);
    Console.WriteLine(" error = " + mse.ToString("F4"));
  }
  Shuffle(sequence); // обрабатываем данные в случайном порядке
...

Мера ошибки вычисляется и отображается через каждые 100 итераций. Метод Error возвращает среднеквадратичную ошибку, которая является усредненной суммой квадратов разницы между вычисленными и целевыми выходными значениями. Заметьте, что это слегка отличается от определения ошибки, которое лежит в основе правила обновления весов, используемого методом градиентного спуска. При обучении этим методом ошибка используется не напрямую, а неявным образом. В других методах обучения, включая оптимизацию роя частиц, ошибка применяется явным образом. Метод Shuffle случайным образом переставляет индексы обучающих данных, содержащиеся в массиве sequence по алгоритму тасования Фишера-Йетса (Fisher-Yates algorithm).

Главная часть обучения методом градиентного спуска короткая:

for (int ti = 0; ti < trainData.Length; ++ti)
{
  int i = sequence[ti];
  double computed = ComputeOutput(trainData[i], weights);
  int targetIndex = trainData[i].Length - 1;
  double target = trainData[i][targetIndex];
  weights[0] += alpha * (target - computed) * 1;
  for (int j = 1; j < weights.Length; ++j)
    weights[j] += alpha * (target - computed) * trainData[i][j - 1];
}

Сначала определяется следующий элемент обучающих данных в случайном порядке, используя перетасованный массив sequence. Метод ComputeOutput использует текущие весовые значения, чтобы вычислить вывод при текущем наборе весовых значений, который будет представлять собой значение между 0.0 и 1.0. Целевое значение (0 или 1) извлекается из текущего элемента обучающих данных. Первым обновляется весовое значение b0. Вспомните, что правило обновления веса использует входное значение, связанное с модифицируемым весовым значением. Однако весовое значение b0 не связано ни с каким входным значением. Ввиду этого b0-веса логистической регрессии считаются всегда имеющими фиктивное входное значение, равное 1.0. В демонстрационном коде происходит умножение на 1.0, что совершенно очевидно ни на что не влияет; так сделано для иллюстрации сходства между обновлением b0 и обновлением любого другого b-веса. Обновление обычных b-весов выполняется довольно прямолинейно и требует лишь некоторого внимания к деталям индексации. Метод Train завершается так:

...
} // цикл while
  return this.weights;
} // Train

Этот метод возвращает ссылку на реальные веса в массиве weights в LogisticClassifier. Для безопасности стоит подумать о создании массива results, а затем копировать веса в этот массив и возвращать ссылку на него.

Как уже отмечалось, демонстрационная программа использует стохастический градиентный спуск. По мере перебора каждого элемента обучающих данных вычисляется градиент для текущего элемента и используется для обновления всех весов. В пакетном градиентном спуске, напротив, сначала на каждой итерации накапливаются градиенты по всем элементам обучающих данных и только потом обновляются весовые значения. Чтобы использовать пакетное обучение, сердцевина метода Train должна быть заменена кодом, показанным на рис. 4.

Рис. 4. Метод Train при использовании пакетного обучения

double[] accumulatedGradients = new double[weights.Length];
for (int i = 0; i < trainData.Length; ++i)  // аккумуляция
{
  double computed = ComputeOutput(trainData[i], weights);
  int targetIndex = trainData[i].Length - 1;
  double target = trainData[i][targetIndex];
  accumulatedGradients[0] += (target - computed) * 1; // для b0
  for (int j = 1; j < weights.Length; ++j)
    accumulatedGradients[j] += (target - computed) *
      trainData[i][j - 1];
}
for (int j = 0; j < weights.Length; ++j) // обновляем все веса
  weights[j] += alpha * accumulatedGradients[j];

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

Когда впервые было предложено обучение методом градиентного спуска, пакетный подход считался теоретически предпочтительным, потому что в этом случае для нахождения градиента весов используется вся доступная информация. Однако специалисты, применяющие ML на практике, быстро осознали, что скорость обучения можно было бы увеличить, используя градиент только для одного элемента обучающих данных как оценку общего градиента. Иначе говоря, стохастический (т. е. случайно определяемый) градиентный спуск использует один градиент для оценки общего градиента.

Заключение

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

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

James McCaffrey - работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи эксперту Microsoft Ричарду Хьюзу (Richard Hughes).