Тесты

Статья
06/01/2015

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

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

Джеймс Маккафри Я считаю классификацию по логистической регрессии (logistic regression, LR) чем-то вроде «Hello, world!» в машинном обучении (machine learning, ML). В стандартной LR-классификации цель заключается в прогнозе значения какой-либо переменной, которая может принимать только одно из двух категориальных значений. Например, возможно, вам надо предсказать пол некоего лица (мужской или женский), исходя из его роста и ежегодного дохода.

Классификация по логистической регрессии с несколькими классами (multi-class LR) расширяет стандартную LR, допуская наличие у прогнозируемой переменной трех или более значений. Скажем, вам может понадобиться спрогнозировать политические предпочтения некоего лица (консервативные, умеренные или либеральные) на основе таких переменных-предикторов, как возраст, ежегодный доход и т. д. В этой статье я объясню, как работает LR с несколькими классами, и покажу, как реализовать ее на C#.

Чтобы лучше понять, куда я клоню в этой статье, взгляните на демонстрационную программу на рис. 1. Она начинает с генерации 1000 строк синтетических данных с четырьмя переменными-предикторами (также называемыми свойствами [features]), где прогнозируемая переменная может принимать одно из трех значений. Строка сгенерированных данных может быть примерно такой:

5.33  -4.89  0.15  -6.67  0.00  1.00  0.00

Рис. 1. Логистическая регрессия с несколькими классами в действии

Первые четыре значения — это значения предикторов, которые представляют реальные данные, нормализованные так, чтобы значение 0.0 было точным средним для свойства (feature), значения выше 0.0 — больше среднего и значения менее 0.0 — меньше среднего. Последние три значения — это закодированная по схеме «1 из N» версия прогнозируемой переменной. Например, если вы пытаетесь предсказать политические предпочтения, тогда (1 0 0) представляет консерватора, (0 1 0) — умеренного и (0 0 1) — либерала.

После генерации синтетические данные были случайным образом разбиты на обучающий набор (80% данных, или 800 строк) и проверочный (тестовый) набор (оставшиеся 200 строк). Обучающие данные используются для создания модели прогнозирования, а проверочные — для оценки точности модели в прогнозировании на новых данных, где предсказываемое значение не известно.

Для верстки: здесь придется выделять курсивом однобуквенные обозначения, так как некоторые из них сливаются с обычными предлогами

Модель LR с f свойствами и c классами будет иметь (f * c) весовых значений и c смещений. Это числовые константы, которые должны быть определены. В данной демонстрации 4 * 3 = 12 весовых значений и три смещения. Обучение — это процесс оценки весовых значений и смещений. Этот процесс является итеративным, в демонстрационной программе задано максимальное количество итераций обучения (часто называемых в литературе по ML эпохами), равное 100. Метод, применяемый для обучения классификатора LR с несколькими классами, называется пакетным (или стандартным) градиентным спуском (batch gradient descent). Этот метод требует значений двух параметров: скорости обучения и скорости снижения весовых значений (weight decay rate). Эти два значения обычно находятся методом проб и ошибок; в демонстрационной программе используются значения 0.01 и 0.10 соответственно.

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

По окончании обучения демонстрационная программа показывает лучшие значения, найденные для 12 весовых значений и трех смещений. Эти 15 значений определяют LR-модель с несколькими классами. Используя эти значения, программа вычислила прогностическую точность модели на обучающих данных (92.63% правильных результатов, или 741 из 800) и на проверочных (90.00% правильных результатов, или 180 из 200).

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

Знакомство с логистической регрессией с несколькими классами

Допустим, вы хотите спрогнозировать политические предпочтения какого-либо человека (консерватор, умеренный, либерал) на основе возраста (x0), ежегодного дохода (x1), роста (x3) и уровня образования (x4). Вы кодируете политические предпочтения тремя переменными как (y0, y1, y2), где консерватор — (1, 0, 0), умеренный — (0, 1, 0) и либерал — (0, 0, 1). LR-модель с несколькими классами для этой задачи приняла бы такую форму:

z0 = (w00)(x0) + (w01)(x1) + (w02)(x2) + b0
y0 = 1.0 / (1.0 + e^-z0)
z1 = (w10)(x0) + (w11)(x1) + (w12)(x2) + b1
y1 = 1.0 / (1.0 + e^-z1)
z2 = (w20)(x0) + (w21)(x1) + (w22)(x2) + b2
y2 = 1.0 / (1.0 + e^-z2)

Здесь wij — весовое значение, сопоставленное с переменной-свойством i и переменной класса j, а bj — смещение, сопоставленное с j.

При LR с несколькими классами приведен на рис. 2. В одном элементе обучающих данных имеются четыре значения предикторов (5.10, –5.20, 5.30, –5.40), за которыми следуют три выходных значения (1, 0, 0). Значения предикторов произвольные, но вы можете считать, что они представляют человека, чей возраст больше среднего, доход ниже среднего, рос выше среднего, а уровень образования ниже среднего; его политические предпочтения — консерватор.

Рис. 2. Структуры данных логистической регрессии с несколькими классами

Каждый из трех столбцов матрицы весов соответствует одному из трех значений класса. Четыре значения в каждом столбце соответствуют четырем x-значениям предиктора. Массив смещений хранит дополнительное, особое весовое значение (по одному для каждого класса), которое не связано с предиктором.

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

В LR с несколькими классами выходные значения вычисляются для каждого класса. На рис. 2 вычисленные выходные значения — (0.32, 0.33, 0.35). Сумма выходных значений составляет 1.0, и их можно трактовать как вероятности. Поскольку последнее выходное значение чуть больше, чем остальные, вы заключаете, что вывод соответствует (0, 0, 1). В этом примере вычисленные выходные значения соответствуют трем выходным значениям в элементе обучающих данных, так что модель сделала корректный прогноз.

Выходные значения вычисляются сначала суммированием произведений каждого входного значения на весовое значение с последующим добавлением соответствующего смещения. Эти суммы произведений часто называют z-значениями. Они передаются в функцию логистического сигмоида 1.0 / (1.0 + e^–z), где e — математическая константа, а ^ означает возведение в степень. Хотя из рис. 2 это не очевидно, результат функции логистического сигмоида всегда будет находиться в диапазоне от 0.0 до 1.0.

Каждое из значений логистического сигмоида используется для вычисления конечных выходных значений. Значения логистического сигмоида суммируются и применяются как делитель. Этот процесс называется функцией softmax. Если вы новичок во всех этих концепциях LR, то поначалу они могут показаться очень запутанными. Но если вы внимательно и не один раз изучите пример на рис. 2, то в конечном счете поймете, что LR не столь сложна, как кажется на первый взгляд.

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

Точные значения весов и смещений вычислить невозможно, поэтому их приходится оценивать. Существует несколько численных методов оптимизации, которые можно использовать с этой целью. К распространенным методам относятся алгоритм L-BFGS, итеративно взвешенный метод наименьших квадратов (iteratively reweighted least squares method) и оптимизация роя частиц (particle swarm optimization). Демонстрационная программа использует метод, который по какой-то непонятной причине называют как градиентным спуском (gradient descent) (минимизация ошибки между вычисленными и известными выходными значениями), так и градиентным подъемом (gradient ascent) (максимизация вероятности того, что веса и смещения становятся оптимальными).

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

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

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

using System;
namespace LogisticMultiClassGradient
{
  class LogisticMultiProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin classification demo");
      ...
      Console.WriteLine("End demo");
      Console.ReadLine();
    }
    public static void ShowData(double[][] data,
      int numRows, int decimals, bool indices) { . . }
    public static void ShowVector(double[] vector,
      int decimals, bool newLine) { . . }
    static double[][] MakeDummyData(int numFeatures,
      int numClasses, int numRows, int seed) { . . }
    static void SplitTrainTest(double[][] allData,
      double trainPct, int seed, out double[][] trainData,
      out double[][] testData) { . . }
  }
  public class LogisticMulti
  {
    private int numFeatures;
    private int numClasses;
    private double[][] weights; // [свойство][класс]
    private double[] biases;    // [класс]
    public LogisticMulti(int numFeatures,
      int numClasses) { . . }
    private double[][] MakeMatrix(int rows,
      int cols) { . . }
    public void SetWeights(double[][] wts,
      double[] b) { . . }
    public double[][] GetWeights() { . . }
    public double[] GetBiases() { . . }
    private double[] ComputeOutputs(double[] dataItem) { . . }
    public void Train(double[][] trainData, int maxEpochs,
      double learnRate, double decay) { . . }
    public double Error(double[][] trainData) { . . }
    public double Accuracy(double[][] trainData) { . . }
    private static int MaxIndex(double[] vector) { . . }
    private static int MaxIndex(int[] vector) { . . }
    private int[] ComputeDependents(double[] dataItem) { . . }
  }
}

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

Класс LogisticMultiProgram включает вспомогательные методы MakeDummyData, SplitTrainTest, ShowData и ShowVector. Эти методы создают и отображают синтетические данные. Вся логика классификации содержится в классе LogisticMulti.

Метод Main создает синтетические данные с помощью следующих выражений:

int numFeatures = 4;
int numClasses = 3;
int numRows = 1000;
double[][] data = MakeDummyData(numFeatures, 
  numClasses, numRows, 0);

Метод MakeDummyData генерирует набор случайных весовых значений и смещений, а затем для каждой строки данных генерирует случайные входные значения, комбинирует веса, смещения и входные значения и вычисляет соответствующие выходные значения, кодированные по схеме «1 из N». Синтетические данные разбиваются на обучающий (80%) и проверочный наборы (20%):

double[][] trainData;
double[][] testData;
SplitTrainTest(data, 0.80, 7, out trainData, out testData);
ShowData(trainData, 3, 2, true);
ShowData(testData, 3, 2, true);

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

LogisticMulti lc = new LogisticMulti(numFeatures, numClasses);
int maxEpochs = 100;
double learnRate = 0.01;
double decay = 0.10;
lc.Train(trainData, maxEpochs, learnRate, decay);

Значения параметров maxEpochs (100), скорости обучения (0.01) и скорости снижения весов (0.10) определялись методом проб и ошибок. Оптимизация большинства методов ML обычно требует некоторого экспериментирования, чтобы добиться хорошей точности прогнозов.

После обучения лучшие весовые значения и смещения сохраняются в объекте LogisticMulti. Они извлекаются и отображаются так:

double[][] bestWts = lc.GetWeights();
double[] bestBiases = lc.GetBiases();
ShowData(bestWts, bestWts.Length, 3, true);
ShowVector(bestBiases, 3, true);

Альтернатива использованию void-метода Train в сочетании с Get-методами — такой рефакторинг метода Train, чтобы он возвращал матрицу лучших весовых значений и массив лучших смещений как выходные параметры или в комбинированном массиве. Качество обучения модели оценивается так:

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

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

Реализация обучения по LR с несколькими классами

Конструктор класса LogisticMulti определен как:

public LogisticMulti(int numFeatures, int numClasses)
{
  this.numFeatures = numFeatures;
  this.numClasses = numClasses;
  this.weights = MakeMatrix(numFeatures, numClasses);
  this.biases = new double[numClasses];
}

MakeMatrix — вспомогательный метод, который выделяет память под матрицу в стиле массив массивов. Матрица весов и массив смещений неявно инициализируются значениями 0.0. Некоторые исследователи предпочитают явно инициализировать весовые значения и смещения небольшими случайными значениями (как правило, между 0.001 и 0.01).

Определение метода ComputeOutputs приведено на рис. 4. Он возвращает массив значений (по одному для каждого класса), где каждое значение укладывается в диапазон между 0.0 и 1.0, а сумма значений равна 1.0.

Рис. 4. Метод ComputeOutputs

private double[] ComputeOutputs(double[] dataItem)
{
  double[] result = new double[numClasses];
  for (int j = 0; j < numClasses; ++j) // вычисляем z
  {
    for (int i = 0; i < numFeatures; ++i)
      result[j] += dataItem[i] * weights[i][j];
    result[j] += biases[j];
  }
  for (int j = 0; j < numClasses; ++j) // 1 / 1 + e^-z
    result[j] = 1.0 / (1.0 + Math.Exp(-result[j]));
  double sum = 0.0; // масштабирование softmax
  for (int j = 0; j < numClasses; ++j)
    sum += result[j];
  for (int j = 0; j < numClasses; ++j)
    result[j] = result[j] / sum;
  return result;
}

Определение класса содержит похожий метод, ComputeDependents:

private int[] ComputeDependents(double[] dataItem)
{
  double[] outputs = ComputeOutputs(dataItem); // 0.0 to 1.0
  int maxIndex = MaxIndex(outputs);
  int[] result = new int[numClasses];
  result[maxIndex] = 1;
  return result;
}

Метод ComputeDependents возвращает целочисленный массив, где одно значение равно 1, а остальные значения равны 0. Эти вычисленные выходные значения можно сравнить с известными целевыми выходными значениями в обучающих данных, чтобы определить, правильный ли прогноз выдала модель, что в свою очередь можно использовать в вычислении точности прогнозирования.

Выраженный на самом высокоуровневом псевдокоде, метод Train представляет собой следующее:

Цикл maxEpochs раз
  Вычисляем все весовые градиенты
  Вычисляем все градиенты смещений
  Используем весовые градиенты для обновления всех весов
  Используем градиенты смещений для обновления всех смещений
Конец цикла

С каждым весовым значением и смещением связано значение градиента. Вольно выражаясь, градиент — это значение, которое указывает, насколько далеко и в каком направлении (по положительной или отрицательной оси) вычисленное выходное значение сравнивается с целевым выходным значением. Например, пусть для одного веса, если значения всех остальных весов и смещений поддерживаются постоянными, вычисленное выходное значение равно 0.7, а целевое выходное значение — 1.0. Вычисленное значение слишком мало, поэтому градиент — это значение, приблизительно равное 0.3, которое будет добавлено к весу. Если значение веса увеличивается, увеличится и вычисленное выходное значение. Я опустил некоторые детали, но основная идея довольно проста.

Математика, связанная с обучением по градиентам, использует численные методы и очень сложна, но, к счастью, вам не обязательно полностью понимать математику, чтобы реализовать нужный код. Определение метода Train начинается с:

public void Train(double[][] trainData, int maxEpochs,
  double learnRate, double decay)
{
  double[] targets = new double[numClasses];
  int msgInterval = maxEpochs / 10;
  int epoch = 0;
  while (epoch < maxEpochs)
  {
    ++epoch;
...

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

if (epoch % msgInterval == 0 && epoch != maxEpochs)
{
  double mse = Error(trainData);
  Console.Write("epoch = " + epoch);
  Console.Write(" error = " + mse.ToString("F4"));
  double acc = Accuracy(trainData);
  Console.WriteLine(" accuracy = " + acc.ToString("F4"));
}

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

double[][] weightGrads = MakeMatrix(numFeatures, numClasses);
double[] biasGrads = new double[numClasses];

Обратите внимание на то, что все эти операции выделения памяти происходят в основном цикле while. Так как C# инициализирует массивы значениями 0.0, все градиенты автоматически инициализируются. В качестве альтернативы можно выделить пространство вне цикла while, а затем вызвать вспомогательные методы с именами наподобие ZeroMatrix и ZeroArray. Далее вычисляются весовые градиенты:

for (int j = 0; j < numClasses; ++j) {
  for (int i = 0; i < numFeatures; ++i) {
    for (int r = 0; r < trainData.Length; ++r) {
      double[] outputs = ComputeOutputs(trainData[r]);
        for (int k = 0; k < numClasses; ++k)
          targets[k] = trainData[r][numFeatures + k];
        double input = trainData[r][i];
        weightGrads[i][j] += (targets[j] - outputs[j]) * input;
    }
  }
}

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

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

double input = trainData[r][i];
int sign = (input > 0.0) ? 1 : -1;
weightGrads[i][j] += (targets[j] - outputs[j]) * sign;

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

for (int j = 0; j < numClasses; ++j) {
  for (int i = 0; i < numFeatures; ++i) {
    for (int r = 0; r < trainData.Length; ++r) {
      double[] outputs = ComputeOutputs(trainData[r]);
      for (int k = 0; k < numClasses; ++k)
        targets[k] = trainData[r][numFeatures + k];
      double input = 1; // 1 – имитация входного значения
      biasGrads[j] += (targets[j] - outputs[j]) * input;
    }
  }
}

Если вы проанализируете этот код, то заметите, что вычисление градиентов смещений можно было бы выполнять внутри циклов for, где вычисляются весовые градиенты. Я разделил вычисления этих двух градиентов для четкости, но ценой производительности. Кроме того, умножение на имитирующее входное значение, равное 1, можно пропустить. Оно тоже было добавлено для ясности. Теперь обновляем веса:

for (int i = 0; i < numFeatures; ++i) {
  for (int j = 0; j < numClasses; ++j) {
    weights[i][j] += learnRate * weightGrads[i][j];
    weights[i][j] *= (1 - decay);  // снижение веса
  }
}

После увеличения или уменьшения весового значения на основе доли скорости обучения в его градиенте это весовое значение уменьшается с использованием скорости снижения веса. Например, в демонстрационной программе используется типичное значение снижения веса 0.10, поэтому умножение на (1 – 0.10) эквивалентно умножению на 0.90, а это означает уменьшение на 10%. Снижение веса также называют регуляризацией. Этот метод предотвращает выход весовых значений из-под контроля. Метод Train завершается обновлением смещений:

...
    for (int j = 0; j < numClasses; ++j) {
      biases[j] += learnRate * biasGrads[j];
      biases[j] *= (1 - decay);
    }
  } // While
} // Train

Метод обучения обновляет матрицу весов и массив смещений «по месту». Эти значения определяют модель LR с несколькими классами и могут быть получены с помощью Get-методов.

Заключение

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

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

Выражаю благодарность за рецензирование статьи эксперту Microsoft Тодду Беллоу (Todd Bello) и Элиссон Сол (Alisson Sol).