Тесты

  • Статья

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

Джеймс Маккафри

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

James McCaffreyОдна из наиболее фундаментальных форм машинного обучения — классификация по логистической регрессии (logistic regression, LR). Цель LR-классификации — создать модель, предсказывающей значение переменной, у которой может быть одно из двух значений. Например, вам нужно спрогнозировать, какого из двух кандидатов выберет избиратель («Smith» = 0, «Jones» = 1) на основе возраста избирателя (x1), пола (x2) и ежегодного дохода (x3).

Если Y является предсказываемым значением, модель LR для этой задачи приняла бы форму:

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

Здесь b0, b1, b2 и b3 — весовые значения, который являются просто числовыми значениями, которые нужно определить. Если в двух словах, то вы вычисляете значение z, которой представляет собой сумму входных значений, умноженных на b-веса, плюс константа b0; затем значение z подставляется в уравнение, использующее математическую константу e. Оказывается, что Y всегда находится в диапазоне от 0 до 1. Если Y меньше 0.5, вывод считается равным 0, а если Y больше 0.5, вывод равен 1.

Например, возраст избирателя — 32 года, пол мужской (–1), а годовой доход в десятках тысяч долларов составляет 48.0. Также допустим, что b0 = –9.0, b1 = 8.0, b2 = 5.0 и b3 = –5.0. Тогда z = –9.0 + (8.0)(32) + (5.0)(–1) + (–5.0)(48.0) = 2.0 и Y = 1.0 / (1.0 + e^–2.0) = 0.88.

Поскольку Y больше 0.5, вы заключаете, что избиратель проголосует за кандидата 1 («Jones»). Но откуда берутся значения b-весов? Обучение LR-классификатора — это процесс нахождения значений для b-весов. Идея в том, чтобы использовать обучающие данные, содержащие известных выходные значения, а затем найти набор b-значений с целью минимизировать разницу между вычисленными и известными выходными значениями. Эту математическую задачу часто называют численной оптимизацией.

Существует примерно дюжина основных алгоритмов оптимизации, применяемых в машинном обучении. В случае обучения по логистической регрессии два из наиболее распространенных алгоритма называются итерационный метод Ньютона-Рафсона (iterative Newton-Raphson) и L-BFGS. В этой статье я представлю метод, называемый оптимизацией на основе нескольких роев частиц (multi-swarm optimization, MSO). MSO — это вариация оптимизации роя частиц (particle swarm optimization, PSO). В MSO виртуальная частица имеет позицию, которая соответствует набору значений b-весов. Рой — это набор частиц, которые движутся так, как диктует групповое поведение, например, стаи птиц. MSO поддерживает несколько роев, взаимодействующих друг с другом в противоположность PSO, где используется один рой.

Лучший способ понять, куда я клоню в этой статье, и получить представление о том, что такое LR с MSO, — взглянуть на демонстрационную программу на рис. 1. Цель этой программы — использовать MSO для создания модели LR, которая предсказывает Y для набора синтетических (программно генерируемых) данных.

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

Демонстрационная программа начинает с создания 10 000 случайных элементов данных, где есть пять переменных-предикторов (часто называемых функциями [features] в терминологии ML). Значение каждой такой функции лежит в диапазоне от –10.0 до +10.0, а Y-значение (0 или 1) находится в последнем столбце набора данных. Значения функций не соответствуют реальной задаче.

Набор данных с 10 000 элементов случайным образом разбивается на обучающий набор с 8000 элементов, используемый для создания LR-модели, и на проверочный набор с 2000 элементов, применяемый для оценки точности модели после обучения. Демонстрационная программа создает LR-классификатор, а затем использует четыре роя, каждый с тремя частицами, чтобы обучить классификатор. MSO является итерационным процессом, и максимальное количество итераций, maxEpochs, задается равным 100.

Программа показывает лучшую (наименьшую) ошибку, найденную любой частицей, через каждые 10 итераций (эпох). По окончании обучения лучшие найденные весовые значения — (4.09, 10.00, 8.43, 1.86, –9.27, 1.84). Используя эти весовые значения, вычисляется точность LR-модели для обучающий данных (99.98%, что является результатом 7998 правильных из 8000) и для проверочных данных (99.85%, что является результатом 1997 правильных из 2000). Точность модели на проверочных данных дает вам примерную оценку того, насколько хорошо будет работать модель с новыми данными, выходные значения для которых не известны.

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

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

Общая структура программы

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

Рис. 2. Общая структура программы

using System;
namespace LogisticWithMulti
{
  class LogisticMultiProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin demo");
      int numFeatures = 5;
      int numRows = 10000;
      int seed = 0;
      Console.WriteLine("Generating " + numRows +
        " artificial data items with " + numFeatures + " features");
      double[][] allData = MakeAllData(numFeatures, numRows, seed);
      Console.WriteLine("Done");
      Console.WriteLine("Creating train and test matrices");
      double[][] trainData;
      double[][] testData;
      MakeTrainTest(allData, 0.80, seed, out trainData, out testData);
      Console.WriteLine("Done");
      Console.WriteLine("Training data: ");
      ShowData(trainData, 4, 2, true);
      Console.WriteLine("Test data: ");
      ShowData(testData, 3, 2, true);
      Console.WriteLine("Creating Logistic Regression classifier");
      LogisticClassifier lc = new LogisticClassifier(numFeatures);
      int numSwarms = 4;
      int numParticles = 3;
      int maxEpochs = 100;
      Console.WriteLine("Setting numSwarms = " + numSwarms);
      Console.WriteLine("Setting numParticles = " + numParticles);
      Console.WriteLine("Setting maxEpochs = " + maxEpochs);
      Console.WriteLine("\nStarting training");
      double[] bestWeights = lc.Train(trainData, maxEpochs,
        numSwarms, numParticles);
      Console.WriteLine("Training complete");
      Console.WriteLine("Best weights found:");
      ShowVector(bestWeights, 4, true);
      double trainAcc = lc.Accuracy(trainData, bestWeights);
      Console.WriteLine("Accuracy on training data = " +
        trainAcc.ToString("F4"));
      double testAcc = lc.Accuracy(testData, bestWeights);
      Console.WriteLine("Accuracy on test data = " +
        testAcc.ToString("F4"));
      Console.WriteLine("End demo");
      Console.ReadLine();
    } // Main
    static double[][] MakeAllData(int numFeatures,
      int numRows, int seed) { . . }
    static void MakeTrainTest(double[][] allData, 
      double trainPct, 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) { . . }
  } // Program
  public class LogisticClassifier { . . }
} // ns

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

В классе программы есть вспомогательные методы MakeAllData, MakeTrainTest, ShowData и ShowVector. Вся логика логистической регрессии содержится в одном классе LogisticClassifier. В этом классе имеются вложенные вспомогательные классы Particle, Swarm и MultiSwarm, которые инкапсулируют данные и логику MSO, используемые при обучении. Эти вспомогательные классы можно было бы определить вне класса LogisticClassifier.

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

int numFeatures = 5;
int numRows = 10000;
int seed = 0; // дает репрезентативную демонстрацию
double[][] allData = MakeAllData(numFeatures, numRows, seed);

Метод MakeAllData создает случайные значения b-весов в диапазоне от –10.0 до +10.0, затем генерирует для каждого элемента данных случайные x-значения в диапазоне от –10.0 до +10.0 и комбинирует их со значениями b-весов, что потом используется для генерации Y-значений. Синтетические данные соответствуют набору данных, где x-значения были нормализованы и где имеются примерно равные количества значений Y = 0 и Y = 1.

Данные разбиваются на обучающие и проверочные следующими выражениями:

double[][] trainData;
double[][] testData;
MakeTrainTest(allData, 0.80, seed, out trainData, out testData);

LR-модель создается и обучается этими выражениями:

LogisticClassifier lc = new LogisticClassifier(numFeatures);
int numSwarms = 4;
int numParticles = 3;
int maxEpochs = 100;
double[] bestWeights = lc.Train(trainData, 
  maxEpochs, numSwarms, numParticles);

А точность модели оценивается следующими двумя выражениями:

double trainAcc = lc.Accuracy(trainData, bestWeights);
double testAcc = lc.Accuracy(testData, bestWeights);

Вникаем в алгоритм MSO

Вот как выглядит MSO-оптимизация в высокоуровневом псевдокоде:

Для каждого роя
  Инициализируем каждую частицу случайной позицией
Конец цикла

Для каждого роя
  Для каждой частицы в рое
    Вычисляем новую скорость
    Используем новую скорость для вычисления новой позиции
    Проверяем, является ли эта позиция новой лучшей
    Погибла ли частица?
    Переместилась ли частица в другой рой?
  Конец цикла
Конец цикла

Возвращаем лучшую найденную позицию

Ключевая часть алгоритма MSO — вычисление скорости частицы, которая является просто набором значений, которые управляют тем, куда переместится частица. Например, в задаче всего с двумя x-размерностями, если частица находится в позиции (6.0, 8.0) и скорость равна (–2.0, 1.0), то ее новая позиция будет в (4.0, 9.0).

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

В математическом выражении, если x(t) — это позиция частицы в момент t, новая скорость, v(t+1), вычисляется как:

v(t+1) = w * v(t) +
         (c1 * r1) * (p(t) - x(t)) +
         (c2 * r2) * (s(t) - x(t)) +
         (c3 * r3) * (g(t) - x(t))

Здесь p(t) — лучшая известная позиция частицы, s(t) — лучшая позиция любой частицы в ее рое, g(t) — глобальная лучшая позиция любой частицы в любом рое, w — константа, называемая коэффициентом инерции, c1, c2 и c3 — константы, задающие максимальное изменение для каждого компонента новой скорости, а r1, r2 и r3 — случайные значения в интервале от 0 до 1, которые обеспечивают эффект рандомизации при каждом обновлении скорости.

Допустим, частица сейчас находится в (20.0, 30.0) и ее текущая скорость равна (–1.0, –3.0). Кроме того, лучшая известная позиция частицы — (10.0, 12.0), лучшая известная позиция любой частицы в рое — (8.0, 9.0), а лучшая известная позиция любой частицы в любом рое — (5.0, 6.0). И предположим, что константа w имеет значение 0.7, константы c1 и c2 равны 1.4, а константа c3 содержит 0.4. Наконец, все случайные значения r1, r2 и r3 равны 0.2.

Тогда новая скорость частицы (с округлением до первого знака после точки):

v(t+1) = 0.7 * (-1.0, -3.0) +
         (1.4 * 0.2) * ((10.0, 12.0) - (20.0, 30.0)) +
         (1.4 * 0.2) * ((8.0, 9.0) - (20.0, 30.0)) +
         (0.4 * 0.2) * ((5.0, 6.0) - (20.0, 30.0))
       = 0.7 * (-1.0, -3.0) +
         0.3 * (-10.0, -18.0) +
         0.3 * (-12.0, -21.0) +
         0.1 * (-15.0, -24.0)
       = (-8.8, -16.2)

А новая позиция частицы:

x(t+1) = (20.0, 30.0) + (-8.8, -16.2)
       = (11.2, 13.8)

Рис. 3 иллюстрирует процесс MSO для задачи с двумя x-значениями, тремя роями с пятью частицами в каждом, где оптимальная позиция находится в точке (0, 0). Видно, как первая частица в каждом рое приближается к оптимальной позиции. Движение по спирали — это особенность MSO.

Иллюстрация алгоритма оптимизации на основе нескольких роев частиц
Рис. 3. Иллюстрация алгоритма оптимизации на основе нескольких роев частиц

Multi-Swarm optimization (3 swarms, first 3 epochs, particle[0] in each swarm) Оптимизации на основе нескольких роев частиц (3 роя, первые 3 итерации, частица[0] в каждом рое)

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

Реализация логистической регрессии с применением MSO

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

public double[] Train(double[][] trainData, int maxEpochs,
  int numSwarms, int numParticles)
{
  int dim = numFeatures + 1;
  double minX = -10.0;
  double maxX = 10.0;
  MultiSwarm ms = new MultiSwarm(numSwarms, numParticles, dim);
...

Размерность задачи определяется количеством функций-предикторов (predictor features) плюс один для учета константы b0. Переменные minX и maxX хранят наименьшее и наибольшее значения для любого отдельного значения в массиве position объекта Particle. Класс LogisticClassifier содержит вложенный класс MultiSwarm. Конструктор класса MultiSwarm создает массив массивов объектов Particle, каждый из которых изначально имеет случайную позицию и случайную скорость. Поскольку метод Error логистической регрессии не виден напрямую вложенному определению Particle, конструктор MultiSwarm не предоставляет значение ошибки для каждой частицы, и метод Train добавляет информацию об ошибках. Прежде всего каждая частица получает значение ошибки:

for (int i = 0; i < numSwarms; ++i)
{
  for (int j = 0; j < numParticles; ++j)
  {
    Particle p = ms.swarms[i].particles[j];
    p.error = Error(trainData, p.position);
    p.bestError = p.error;
    Array.Copy(p.position, p.bestPosition, dim);
...

Затем вычисляются лучшая ошибка текущего роя и общая глобальная лучшая ошибка:

...
    if (p.error < ms.swarms[i].bestError) // лучший рой?
    {
      ms.swarms[i].bestError = p.error;
      Array.Copy(p.position, ms.swarms[i].bestPosition, dim);
    }
    if (p.error < ms.bestError) // глобально лучшая?
    {
      ms.bestError = p.error;
      Array.Copy(p.position, ms.bestPosition, dim);
    }
  } // j
} // i

Основной цикл обучения подготавливается так:

int epoch = 0;
double w = 0.729; // инерция
double c1 = 1.49445; // частица
double c2 = 1.49445;// рой
double c3 = 0.3645; // несколько роев
double pDeath = 1.0 / maxEpochs;
double pImmigrate = 1.0 / maxEpochs;
int[] sequence = new int[numParticles];
for (int i = 0; i < sequence.Length; ++i)
  sequence[i] = i;

Значения для констант w, c1 и c2 являются результатом некоторых исследований в области PSO. Любопытно, что по сравнению со многими алгоритмами численной оптимизации PSO и MSO относительно нечувствительны к значениям, используемым для внутренних магических констант (называемым свободными параметрами или гиперпараметрами). Константа c3, которая влияет на тенденцию частицы к продвижению к лучшей известной позиции, найденной на данный момент любой частицей в любом рое, исследована довольно слабо. Используемое мной значение (0.3645) является половиной значения константы инерции, и на практике прекрасно сработало для моей задачи.

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

Основной цикл обучения начинается так:

while (epoch < maxEpochs)
{
  ++epoch;
  // Optionally print best error here
  for (int i = 0; i < numSwarms; ++i) // Each swarm
  {
    Shuffle(sequence);
    for (int pj = 0; pj < numParticles; ++pj) // Each particle
    {
      int j = sequence[pj];
      Particle p = ms.swarms[i].particles[j];
...

Знание того, когда следует остановить обучение, — одна из наиболее трудных задач в машинном обучении. Здесь используется фиксированное количество итераций (maxEpochs). Это простой подход, но есть риск того, что обучение окажется недостаточным. Или наоборот чрезмерным, что приведет к тому. что ваша модель будет чрезвычайно точной, но с новыми данными будет показывать плохие результаты. Это называют переобучением (over-fitting). Для борьбы с переобучением можно применять десятки методов.

Далее вычисляется новая скорость текущей частицы, как пояснялось ранее (рис. 4).

Рис. 4. Вычисление новой скорости для текущей частицы

for (int k = 0; k < dim; ++k)
{
  double r1 = rnd.NextDouble();
  double r2 = rnd.NextDouble();
  double r3 = rnd.NextDouble();
  p.velocity[k] = (w * p.velocity[k]) +
    (c1 * r1 * (p.bestPosition[k] - p.position[k])) +
    (c2 * r2 * (ms.swarms[i].bestPosition[k] - p.position[k])) +
    (c3 * r3 * (ms.bestPosition[k] - p.position[k]));
  if (p.velocity[k] < minX)
    p.velocity[k] = minX;
  else if (p.velocity[k] > maxX)
    p.velocity[k] = maxX;
} // k

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

Потом новая скорость используется для вычисления новой позиции текущей частицы и связанной с ней ошибки:

for (int k = 0; k < dim; ++k)
{
  p.position[k] += p.velocity[k];
  if (p.position[k] < minX)
    p.position[k] = minX;
  else if (p.position[k] > maxX)
    p.position[k] = maxX;
}

После перемещения частицы вычисляется ее новая ошибка:

p.error = Error(trainData, p.position); // накладно
if (p.error < p.bestError) // новая лучшая позиция для частицы?
{
  p.bestError = p.error;
  Array.Copy(p.position, p.bestPosition, dim);
}

Новая ошибка текущей частицы может оказаться новой лучшей для роя или глобально лучшей:

// Новая лучшая ошибка для роя?
if (p.error < ms.swarms[i].bestError)
{
  ms.swarms[i].bestError = p.error;
  Array.Copy(p.position, ms.swarms[i].bestPosition, dim);
}
if (p.error < ms.bestError) // новая глобально лучшая ошибка?
{
  ms.bestError = p.error;
  Array.Copy(p.position, ms.bestPosition, dim);
}

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

double p1 = rnd.NextDouble();
if (p1 < pDeath)
{
  Particle q = new Particle(dim); // замена
  q.error = Error(trainData, q.position);
  Array.Copy(q.position, q.bestPosition, dim);
  q.bestError = q.error;

Альтернативой использованию фиксированной вероятности гибели является постепенное увеличение этой вероятности, например:

double pDeath = (maxProbDeath / maxEpochs) * epoch;

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

// Лучшая ошибка роя по чистой случайности?
if (q.error < ms.swarms[i].bestError)
{
  ms.swarms[i].bestError = q.error;
  Array.Copy(q.position, ms.swarms[i].bestPosition, dim);
  if (q.error < ms.bestError) // глобально лучшая ошибка?
  {
    ms.bestError = q.error;
    Array.Copy(q.position, ms.bestPosition, dim);
  }
}

Механизм гибели завершает свою работу заменой текущей частицы новой и уничтожением текущей:

...
  ms.swarms[i].particles[j] = q;
} // Die

Далее (необязательно) начинает работать механизм миграции:

double p2 = rnd.NextDouble();
if (p2 < pImmigrate)
{
  int ii = rnd.Next(0, numSwarms); // рандомизация роя
  int jj = rnd.Next(0, numParticles); // рандомизация частицы
  Particle q = ms.swarms[ii].particles[jj]; // q точек к другим
  ms.swarms[i].particles[j] = q;
  ms.swarms[ii].particles[jj] = p; // обмен
...

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

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

...
  // Текущая имеет новую позицию?
  if (q.error < ms.swarms[i].bestError)
  {
    ms.swarms[i].bestError = q.error;
    Array.Copy(q.position, ms.swarms[i].bestPosition, dim);
  }
  // Другая имеет новую позицию?
  if (p.error < ms.swarms[ii].bestError)
  {
    ms.swarms[ii].bestError = p.error;
    Array.Copy(p.position, ms.swarms[ii].bestPosition, dim);
  }
} // Миграция

Метод Train завершается возвратом лучшей позиции, найденной любой частицей:

...
      } // j - each particle
    } // i - each swarm
  } // while
  return ms.bestPosition;
} // Train

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

Заключение

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

Логистическая регрессия — одна из простейших форм классификации с применением машинного обучения. Для многих задач классификации LR работает не слишком хорошо. Однако многие из тех, кто имеет дело с ML, в том числе я, обычно начинают исследовать задачу классификации с помощью LR и только потом, если будет такая необходимость, применяют более сложные методы.

Как показывает мой опыт, по сравнению с более старыми методами численной оптимизации на основе расчетов (calculus-based), таких как градиентный спуск (gradient descent) и L-BFGS, обучение с использованием MSO, в целом, дает более качественные ML-модели, но MSO почти всегда на порядок медленнее.

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

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