C#
Классификация и предсказание с применением адаптивного обучения
Продукты и технологии:
Visual Studio 2010, C#
В статье рассматриваются:
- классификация на основе адаптивного обучения (adaptive boosting);
- демонстрационная программа, использующая алгоритм адаптивного обучения;
- алгоритм адаптивного обучения;
- общая структура программы.
Исходный код можно скачать по ссылке.
Классификация — методология машинного обучения, в которой обучающие данные используются для генерации модели (обычно одного комплексного правила или математического уравнения), где элементы данных распределяются по одной из нескольких категорий. Затем модель можно использовать для предсказаний по новым элементам данных, категория которых не известна. Примеры включают предсказание того, есть ли у пациента рак (да, нет), на основе данных различных медицинских анализов, и предсказание категории риска заявки на кредит (loan application) (низкая, средняя, высокая) на основе финансовой истории заявителя.
Существует много разных алгоритмов и методов классификации, включая наивный байесовский алгоритм, нейронные сети и логистическая регрессия (logistic regression). В этой статье я объясню восхитительный метод, называемый классификацией на основе адаптивного обучения (adaptive boosting classification), при котором вместо определения одного сложного правила предсказания используются обучающие данные, чтобы сгенерировать большой набор очень простых общих правил (rules of thumb). Затем вычисляется весовое значение каждого общего правила. Предсказание о новом вводе осуществляется комбинированием общих правил с учетом их весовых значений и достижением единого мнения о конечном результате. Термин «обучение» (boosting) связан с тем, что качество предсказания на основе простых правил повышается (улучшается) при их комбинировании.
Адаптивное обучение является мета-эвристическим. Под этим я подразумеваю, что адаптивное обучение — это набор принципов, которые можно использовать для создания конкретного алгоритма спецификации. У алгоритмов адаптивного обучения много вариаций, и есть немало автономных инструментов, в той или иной форме реализующих адаптивное обучение, — так зачем же писать с нуля код для классификации на основе адаптивного обучения? Существующие инструменты такой классификации могут оказаться сложными в настройке или вообще не настраиваемыми, их может быть трудно интегрировать в программную систему, и с ними могут быть связаны всяческие проблемы авторским прав или прав на интеллектуальную собственность.
Конкретный пример — лучший способ понять, что такое адаптивное обучение. Взгляните на рис. 1. В конечном счете задача демонстрационной программы сводится к предсказанию того, победит или проиграет на предстоящих соревнованиях некая спортивная команда из Сиэтла соперникам из Детройта, когда эта команда из Сиэтла будет играть на своем поле и ставка на разницу в счете будет небольшой. В верхней части рис. 1 показаны 10 вымышленных элементов обучающих данных с известными результатами. Первая обучающая последовательность (Detroit, Home, Large, Win) означает, что в прошлой игре против Детройта, когда Сиэтл играл на своем поле (Home) и ставка на разницу в счете была большой (Large), Сиэтл выиграл (Win).
.png "Классификация и предсказание на основе адаптивного обучения")
Рис. 1. Классификация и предсказание на основе адаптивного обучения
Следующая часть демонстрационной программы показывает, что эти 10 элементов обучающих данных были преобразованы из строковых данных в целочисленную форму с отсчетом от 0 для более эффективной обработки, а затем сохранены в памяти в виде матрицы. Например, (Detroit, Home, Large, Win) хранится как (3, 0, 2, 1). Заметьте, что в этом примере результат, который надо предсказать, имеет всего два значения: win (выигрыш) или lose (проигрыш). Такой вариант называют задачей бинарной классификации (binary classification problem). Адаптивное обучение также можно применять в ситуациях, где зависимая переменная имеет три или более значений (полиномиальная классификация). В большинстве методов бинарной классификации зависимая переменная, значение которой надо предсказать, кодируется по схеме (0, 1), но при адаптивном обучении почти всегда используется схема (–1, +1), так как эта кодировка слегка упрощает некоторые части реализации алгоритма. Заметьте, что все значения предиктора (independent variable predictor values) являются категориальными («Home», «Medium» и т. д.), а не числовыми. Как я поясню позже, адаптивное обучение можно применять и в том случае, когда обучающие данные имеют числовые значения.
Третья часть на рис. 1 показывает, что на основе обучающих данных было сгенерировано восемь общих правил. Общие правила в терминологии адаптивного обучения часто называют слабыми учениками (weak learners), или слабыми классификаторами (weak classifiers). Первый слабый ученик, выраженный в форме, понятной человеку, — «IF Opponent IS Buffalo THEN Result IS Win» с исходной частотой ошибок 0.00. Второй, более иллюстративный, слабый ученик — «IF Opponent IS Chicago THEN Result IS Lose» с частотой ошибок 0.33. Откуда взялся этот слабый ученик? Если вы проанализируете обучающие данные, то увидите, что есть три случая, где соперником является Чикаго. В двух из этих случаев результатом было Lose, поэтому слабый ученик прав в двух случаях из трех (0.67) и ошибается в одном случае из трех (0.33).
Заметьте, что не все значения предиктора обучающих элементов сгенерировали слабого ученика; отсутствует правило, когда соперником является Атланта. Поскольку имеются две обучающие последовательности, где соперником является Атланта, и один результат — Win, а другой — Lose, частота ошибок для ученика была бы равной 0.50, что не несет никакой полезной информации. Версия классификации на основе адаптивного обучения, представленная в этой статье, предполагает, что исходная частота ошибок у всех слабых учеников меньше 0.50.
Следующий раздел на рис. 1 указывает, что «за кулисами» алгоритм адаптивного обучения обрабатывает слабых учеников, чтобы определить весовое значение для каждого ученика. Эти весовые значения являются мерой значимости каждого слабого классификатора и называются альфа-значениями в терминологии адаптивного обучения. Определение альфа-значений — это ключевая часть адаптивного обучения. Набор слабых учеников и их альфа-весов образует модель классификации.
Последняя часть демонстрационной программы показывает модель классификации, используемую для предсказания по команде из Сиэтла, когда противники из Детройта, игра идет на своем поле, а ставка на разницу в счете (point spread) — Small. Взглянув на набор сгенерированных слабых учеников, вы увидите, что применимы три ученика: [2] IF Opponent IS Detroit THEN Result IS Win (+1), [3] IF Field IS Home THEN Result IS Win (+1) и [5] IF Spread IS Small THEN Result IS Lose (–1). Вычисленные альфа-значения для слабых учеников 2, 3 и 5 равны 0.63, 3.15 и 4.49 соответственно. Поэтому согласованное предсказание = (0.63)(+1) + (3.15)(+1) + (4.49)(–1) = –0.72 (округленно), что означает проигрыш (Lose), так как значение отрицательное. Заметьте: хотя двое из трех слабых учеников (2 и 3) предсказывают Win, большое альфа-значение у третьего слабого ученика под номером 5 перевешивает их предсказания Win и дает общее предсказание Lose.
В последующих разделах я подробно объясню, как работает демонстрационная программа, чтобы вы могли добавить средства предсказания в какую-либо .NET-систему или программу. В этой статье предполагается, что вы по крайней мере на среднем уровне владеете навыками программирования на языках семейства C, но ничего не знаете о классификации с адаптивным обучением. Я кодировал демонстрационную программу на C#, но мои пояснения должны дать вам достаточно информации для рефакторинга этой программы под другой язык, например Visual Basic .NET или Python. Исходный код демонстрационной программы слишком велик для этой статьи, поэтому скачайте полный исходный код демонстрационной программы по ссылке archive.msdn.microsoft.com/mag201304AdaptiveBoost.
Алгоритм адаптивного обучения
В сердцевине классификации на основе адаптивного обучения лежит процедура, которая анализирует слабых учеников и назначает каждому из них весовые альфа-значения. Этот алгоритм весьма хитроумный, и лучше его пояснять на конкретном примере. Допустим, у нас есть 10 обучающих последовательностей и восемь слабых учеников, как показано на рис. 1. Каждой обучающей последовательности назначается свой вес, который в литературе по адаптивному обучению называют D. Сумма весов D равна 1.0, что превращает значения D в распределение. Изначально всем элементам обучающих данных назначаются одинаковые веса D — в нашем случае 0.10, так как у нас 10 элементов:
[0] (D = 0.10) Detroit Home Large Win
[1] (D = 0.10) Detroit Away Medium Win
[2] (D = 0.10) Buffalo Home Small Win
[3] (D = 0.10) Buffalo Home Medium Win
[4] (D = 0.10) Atlanta Away Large Win
[5] (D = 0.10) Chicago Home Medium Win
[6] (D = 0.10) Chicago Away Small Lose
[7] (D = 0.10) Chicago Home Small Lose
[8] (D = 0.10) Atlanta Away Medium Lose
[9] (D = 0.10) Detroit Away Large Lose
Каждый ученик имеет эпсилон- и альфа-значения. Эпсилон-значения — это взвешенные значения частоты ошибок, используемые для вычисления альфа-значений. Изначально все ученики имеют неизвестные альфа-значения (скажем, a = 0.00) и неизвестные эпсилон-значения (скажем, e = –1.0):
[0] (a = 0.00) (e = -1.0) IF Opponent IS Buffalo THEN Result IS Win
[1] (a = 0.00) (e = -1.0) IF Opponent IS Chicago THEN Result IS Lose
[2] (a = 0.00) (e = -1.0) IF Opponent IS Detroit THEN Result IS Win
[3] (a = 0.00) (e = -1.0) IF Field IS Home THEN Result IS Win
[4] (a = 0.00) (e = -1.0) IF Field IS Away THEN Result IS Lose
[5] (a = 0.00) (e = -1.0) IF Spread IS Small THEN Result IS Lose
[6] (a = 0.00) (e = -1.0) IF Spread IS Medium THEN Result IS Win
[7] (a = 0.00) (e = -1.0) IF Spread IS Large THEN Result IS Win
В псевдокоде алгоритм нахождения альфа-весовых значений для каждого ученика выглядит так:
set t=0
while not done loop
Обновляем эпсилон-значения всех учеников (взвешенные ошибки)
Находим лучшего неиспользуемого ученика (с минимальным эпсилон-значением)
Вычисляем и сохраняем альфа-значение лучшего ученика, используя его эпсилон-значение
Обновляем веса D для каждого обучающего элемента, используя лучшего ученика
Нормализуем веса D, чтобы их сумма была равна 1.0
++t
end loop
Основной цикл обработки завершается, когда обработаны все слабые ученики и назначены альфа-весовые значения или когда счетчик цикла (переменная t) превысит некое максимальное значение, или когда взвешенная частота ошибок, эпсилон, для лучшего неиспользуемого слабого ученика принимает значение вроде 0.45 или 0.49, указывающее, что больше нет сравнительно хороших неиспользуемых учеников.
Первый шаг внутри цикла — обновление все эпсилон-значений. Эпсилон-значение является суммой весов D, неправильно классифицированных обучающих последовательностей. Для ученика [0] (IF Opponent IS Buffalo THEN Result IS Win) есть две применимые обучающие последовательности ([2] и [3]), и это правило выполняется в обоих случаях, поэтому эпсилон равен 0.00. Для ученика [1] (IF Opponent IS Chicago THEN Result IS Lose) есть три применимые обучающие последовательности ([5], [6] и [7]). Из них последовательность [5] неправильна, поэтому эпсилон является просто весом D для этой последовательности (0.10).
Хотя это становится очевидным не сразу, если вы внимательно проанализируете, как вычисляются эпсилон-значения, вы заметите, что они всегда будут находиться в диапазоне от 0.0 до 0.5. После всех обновлений эпсилон-значения учеников таковы:
[0] (a = 0.00) (e = 0.00) IF Opponent IS Buffalo THEN Result IS Win
[1] (a = 0.00) (e = 0.10) IF Opponent IS Chicago THEN Result IS Lose
[2] (a = 0.00) (e = 0.10) IF Opponent IS Detroit THEN Result IS Win
[3] (a = 0.00) (e = 0.10) IF Field IS Home THEN Result IS Win
[4] (a = 0.00) (e = 0.20) IF Field IS Away THEN Result IS Lose
[5] (a = 0.00) (e = 0.10) IF Spread IS Small THEN Result IS Lose
[6] (a = 0.00) (e = 0.10) IF Spread IS Medium THEN Result IS Win
[7] (a = 0.00) (e = 0.10) IF Spread IS Large THEN Result IS Win
К этому моменту выбирается лучший ученик. Это ученик [0], так как у него минимальное эпсилон-значение 0.00. Связанное альфа-значение вычисляется следующим образом:
alpha = 0.5 * log((1.0 - epsilon) / epsilon)
По сути, это магическое уравнение из теории адаптивного обучения. Здесь log — натуральный (по базе e) логарифм. Вспомните, что альфа-значение — это вес, определяющий значимость ученика. Предыдущее уравнение составлено так, чтобы меньшие эпсилон-значения (ошибки ученика) давали более высокие альфа-значения (важность ученика).
Конкретно в этой ситуации возникает проблема, так как эпсилон равен 0, а деление на ноль — это ошибка. Чтобы избежать этого, демонстрационная программа произвольно присваивает 0.000001 любым нулевым эпсилон-значениям. Поэтому альфа для ученика [0] вычисляется как 0.5 * log(0.999999 / 0.000001) = 6.91, и это значение присваивается ученику [0], после чего этот ученик помечается как обработанный.
Следующий шаг внутри цикла алгоритма — обновление весов D обучающих последовательностей на основе только что вычисленного лучшего ученика. Идея в том, чтобы увеличивать веса D для тех обучающих последовательностей, которые неправильно классифицируются лучшим учеником, и уменьшать их для правильно классифицируемых лучшим учеником. Уравнение обновления D на первый взгляд кажется слегка запутанным:
D(new) = D(old) * exp(-alpha * actualY * predictedY)
Лучшим является ученик [0] (IF Opponent IS Buffalo THEN Result IS Win) с альфой 6.91. Из 10 обучающих последовательностей ученик [0] применяется к последовательностям [2] и [3], чтобы обновить эти значения D. Для обучающей последовательности [2]:
D(new) = 0.10 * exp(-6.91 * (+1) * (+1))
= 0.10 * exp(-6.91)
= 0.0000997758
Новое значение D для обучающей последовательности [3] вычисляется так же и имеет то же значение, что и у последовательности [2].
В этом случае мы получаем новый вес D, который очень мал, так как обучающая последовательность была правильно классифицирована лучшим учеником. Заметьте: когда реальное и предсказанное значения Y одинаковы (оба –1 или оба +1), результат их перемножения равен +1, а аргумент в exp будет отрицательным числом (потому что –alpha всегда будет отрицательной), и это будет давать результат, меньший 1.0. Однако, если реальное и предсказанное значения Y различаются, результат их перемножения равен –1, а аргумент в exp будет положительным, что даст (возможно, большое) число, превышающее 1.0. Этим методом обновления D и объясняется, почему в классификации с адаптивным обучением, как правило, используют –1 и +1 для значений зависимых переменных, а не 0 и +1.
В этот момент предварительные приближенные значения D (округленные) таковы:
[0] (D = 0.1000) Detroit Home Large Win
[1] (D = 0.1000) Detroit Away Medium Win
[2] (D = 0.0001) Buffalo Home Small Win
[3] (D = 0.0001) Buffalo Home Medium Win
[4] (D = 0.1000) Atlanta Away Large Win
[5] (D = 0.1000) Chicago Home Medium Win
[6] (D = 0.1000) Chicago Away Small Lose
[7] (D = 0.1000) Chicago Home Small Lose
[8] (D = 0.1000) Atlanta Away Medium Lose
[9] (D = 0.1000) Detroit Away Large Lose
Следующий шаг в основном цикле алгоритма — нормализация значений D, чтобы в сумме они давали 1.0; для этого каждое предварительное значение D делится на сумму значений D. Сумма десяти значений D примерно равна 0.8002, поэтому нормализованное D для обучающей последовательности [0] приблизительно составляет 0.1000 / 0.8002 = 0.1249. Окончательные обновленные веса D выглядят так:
[0] (D = 0.1249) Detroit Home Large Win
[1] (D = 0.1249) Detroit Away Medium Win
[2] (D = 0.0001) Buffalo Home Small Win
[3] (D = 0.0001) Buffalo Home Medium Win
[4] (D = 0.1249) Atlanta Away Large Win
[5] (D = 0.1249) Chicago Home Medium Win
[6] (D = 0.1249) Chicago Away Small Lose
[7] (D = 0.1249) Chicago Home Small Lose
[8] (D = 0.1249) Atlanta Away Medium Lose
[9] (D = 0.1249) Detroit Away Large Lose
Здесь идея в том, чтобы алгоритм теперь сконцентрировался на обучающих последовательностях, отличных от [2] и [3], поскольку эти последовательности уже отражены учеником [0]. В этот момент алгоритм переходит обратно в начало цикла и обновляет эпсилон-значения всех учеников на основе только что вычисленных весов D, определяет лучшего неиспользованного ученика ([5]), вычисляет альфу для него (4.49), обновляет значения D для применимых обучающих последовательностей ([2], [6] и [7]) и рассчитывает нормализованные значения D для всех обучающих последовательностей.
В этом примере процесс продолжается, пока не будут вычислены альфа-значения для всех восьми слабых учеников, но, в целом, не все слабые ученики обязательно пройдут тест на хороших учеников и получат альфа-значение.
Общая структура программы
Демонстрационная программа, показанная на рис. 1, является единым консольным приложением на C#. Я использовал Visual Studio 2010, но подойдет любая версия, которая поддерживает Microsoft .NET Framework 2.0 или выше. Я создал новый проект с именем AdaptiveBoosting, а затем в окне Solution Explorer переименовал Program.cs в более описательное AdaptiveBoostingProgram.cs, что влечет за собой автоматическое переименование и класса Program. Я удалил все выражения using в самом начале исходного кода, сгенерированные шаблоном, кроме ссылок на пространства имен System и Collections.Generic. Метод Main приведен на рис. 2, но здесь удалены некоторые выражения WriteLine, внесен ряд других мелких правок и показан ключевой программно-определенный класс объектов слабых учеников.
Рис. 2. Общая структура программы
using System;
using System.Collections.Generic;
namespace AdaptiveBoosting
{
class Program
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin adaptive boosting classification demo\n");
string[] features = new string[] { "Opponent", "Field", "Spread",
"Result" };
string[][] values = new string[4][];
values[0] = new string[] { "Atlanta", "Buffalo", "Chicago",
"Detroit" }; // соперник
values[1] = new string[] { "Home", "Away" }; // поле
values[2] = new string[] { "Small ", "Medium", "Large " };
// Примечание: добавлены пробелы
values[3] = new string[] { "Lose", "Win" };
// Зависимая/предсказываемая переменная
string[][] rawTrain = new string[10][];
rawTrain[0] = new string[] { "Detroit", "Home", "Large ", "Win" };
rawTrain[1] = new string[] { "Detroit", "Away", "Medium", "Win" };
rawTrain[2] = new string[] { "Buffalo", "Home", "Small ", "Win" };
rawTrain[3] = new string[] { "Buffalo", "Home", "Medium", "Win" };
rawTrain[4] = new string[] { "Atlanta", "Away", "Large ", "Win" };
rawTrain[5] = new string[] { "Chicago", "Home", "Medium", "Win" };
rawTrain[6] = new string[] { "Chicago", "Away", "Small ", "Lose" };
rawTrain[7] = new string[] { "Chicago", "Home", "Small ", "Lose" };
rawTrain[8] = new string[] { "Atlanta", "Away", "Medium", "Lose" };
rawTrain[9] = new string[] { "Detroit", "Away", "Large ", "Lose" };
Console.WriteLine("Raw (string) training data for team seattle:\n");
Console.WriteLine("Opponent Field Spread Result");
Console.WriteLine("===============================");
ShowMatrix(rawTrain);
Console.WriteLine("\nConverting and storing training data");
int[][] train = RawTrainToInt(rawTrain, values);
Console.WriteLine("Training data in int form:\n");
ShowMatrix(train, true);
Console.WriteLine(
"\nCreating weak categorical stump learners from training data");
List<Learner> learners = MakeLearners(values, train);
Console.WriteLine("Completed. Weak learners are:\n");
for (int i = 0; i < learners.Count; ++i)
Console.WriteLine("[" + i + "] " + Description(learners[i],
features, values));
Console.WriteLine("\nInitializing list of best learner indexes");
List<int> bestLearners = new List<int>(); // индексы хороших слабых учеников
Console.WriteLine(
"\nUsing adaptive boosting to find best learners and alphas");
MakeModel(train, values, learners, bestLearners);
Console.WriteLine("\nModel completed");
int numGood = bestLearners.Count;
Console.Write("Algorithm found " + numGood + " good learners ");
Console.WriteLine("and associated alpha values");
Console.WriteLine("\nThe good learners and their alpha value are:");
for (int i = 0; i < bestLearners.Count; ++i)
{
int lrn = bestLearners[i];
Console.Write("[" + lrn + "] " +
learners[lrn].alpha.ToString("F2") + " ");
}
Console.Write("\nPredicting outcome when Opponent = Detroit, ");
Console.WriteLine("Field = Home, Spread = Small\n");
int[] unknownTuple = new int[] { 3, 0, 0 }; // Detroit, Home, Small
int Y = Classify(unknownTuple, learners, bestLearners);
Console.Write("Predicted Y = " + Y + " => ");
Console.WriteLine("seattle will " + YValueToString(Y, values));
Console.WriteLine("\nEnd\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// Здесь опущено много статических методов
} // класс Program
public class Learner // слабый ученик
{
// Здесь размещается определение
}
} // ns
Метод Main начинается с присваивания «зашитых» в код строк для названий характеристик «Opponent», «Field», «Spread» и «Result». Затем код в Main присваивает «зашитые» в код значения для каждой характеристики: «Atlanta», «Buffalo», «Chicago», «Detroit», «Home», «Away», «Small», «Medium», «Large», «Lose» и «Win». Чтобы вывод программы выглядел аккуратно, я воспользовался простым приемом и вставлял пробел в конце «Small» и «Large».
Для упрощения обучающие последовательности тоже «зашиты» в код демонстрационной программы. Во многих ситуациях ваши обучающие данные будут храниться в текстовом файле или в SQL-таблице. В этих ситуациях вам может понадобиться программное сканирование обучающих данных, чтобы определить названия характеристик (предположительно из строки заголовка текстового файла или из названий полей SQL-таблицы) и их значения.
Метод RawTrainToInt преобразует обучающие данные в строковой форме в целочисленные значения с отсчетом от нуля и сохраняет их в матрице train типа int[][]. RawTrainToInt вызывает вспомогательный метод ValueToInt. Матрица train имеет значения зависимой переменной (Result), хранящиеся в последнем столбце. Возможно, вы предпочтете хранить зависимые значения в отдельном массиве column. В ситуациях с очень большими наборами обучающих данных не исключено, что вы не сможете поместить весь набор обучающих данных в память компьютера. Тогда вам придется организовать его потоковую передачу через внешнее хранилище данных вместо использования внутренней матрицы.
Демонстрационная программа определяет слабых учеников, используя метод MakeLearners и определенный в программе класс Learner. Я подробно опишу эти метод и класс в следующем разделе. После создания слабых учеников демонстрационная программа вызывает метод MakeModel, который, как пояснялось в предыдущем разделе, является сердцевиной алгоритма адаптивного обучения. Конечный результат — отсортированный List с именем bestLearners, содержащий индексы учеников, которым были присвоены альфа-значения.
Метод Main завершает свою работу предсказанием результата для Сиэтла при наборе входных данных с Opponent = «Detroit», Field = «Home» и Spread = «Small», используя метод Classify. В этом случае значение, возвращаемое Classify, равно –0.72, что интерпретируется как «Lose».
Определение слабых учеников
Реализация конкретного алгоритма адаптивного обучения до некоторой степени зависит от специфического определения слабого учения. Класс Learner, определенный в программе, имеет шесть полей:
public int feature;
public int value;
public int predicted;
public double error;
public double epsilon;
public double alpha;
Простоты ради я объявил все поля открытыми. Поле feature хранит целочисленное значение, указывающее, какая независимая переменная является ключевой для ученика. Например, если feature равна 0, слабый ученик базируется на значении opponent. Поле value содержит целочисленное значение, указывающее значение feature. Так, если value равно 3, слабый ученик базируется на условии, что соперником является Детройт. Поле predicted содержит –1 или +1 в зависимости от того, какова реальная категория для значения feature — Lose или Win.
Поле error имеет тип double и определяет исходную частоту ошибок (raw error rate), связанную со слабым учеником на обучающих данных. Например, если у слабого ученика feature = 0, value = 3 и predicted = +1 (т. е. «if Opponent is Detroit then result is Win»), то исходная частота ошибок на обучающих данных с рис. 1 равна 0.33, так как один из трех элементов обучающих данных был бы предсказан неправильно. Заметьте, что при расчете исходных ошибок каждый обучающий элемент обрабатывается одинаково. Алгоритм адаптивного обучения, представленный в этой статье, на самом деле не нуждается в поле error, поэтому его можно было бы опустить, но для общей картины я считаю эту информацию полезной.
Поле epsilon — это взвешенный компонент ошибки (error term). Эпсилон для слабого ученика является компонентом ошибки, который учитывает внутренние веса D, назначенные каждому обучающему элементу. Эпсилон-значения используются алгоритмом адаптивного обучения для вычисления альфа-весовых значений. Подытожим. В классификации на основе адаптивного обучения применяются два набора весовых значений. Альфа-веса определяют значимость каждого слабого ученика и используются для определения общего предсказания. Эпсилон-ошибка — это внутренняя ошибка, связанная со слабым учеником, которая используется для вычисления альфа-весов. Каждая обучающая последовательность имеет внутренний вес (называемый D в литературе по адаптивному обучению), который применяется при вычислении эпсилон-ошибок.
В псевдокоде метод MakeLearners работает так:
Инициализируем пустой список результатов учеников
for each feature loop
for each value текущей feature loop
Сканируем обучающие данные, чтобы определить наиболее
вероятный результат -1, +1
if наиболее вероятного результата нет,
пропускаем текущее значение
Создаем новый объект ученика с feature, value, predicted
Добавляем объект ученика в список результатов
end each value
end each feature
for each learner в списке результатов
for each training data item
if ученик неприменим к данным,
пропускаем текущий элемент данных
Вычисляем исходную частоту ошибок
Сохраняем исходную ошибку в ученике
end each training data item
end each learner
Идея в том, что каждое значение характеристики (feature), такое как «Atlanta» (соперник) или «Medium» (ставка на разницу результатов), будет генерировать правило слабого ученика на основе обучающих данных, пока это значение не появится в обучающих данных (например, соперник «New York») или не даст наиболее вероятный результат, поскольку с этим значением связано одинаковое количество побед и проигрышей (например, когда в демонстрационных данных соперником является «Atlanta» с одной победой и одним проигрышем).
Заключение
Важная вариация алгоритма, представленная в этой статье, имеет дело с данными, в которых есть числовые значения. Пусть, например, значения для характеристики «ставка на разницу результатов» (point spread feature) являются не категориальными («Small», «Medium» и «Large»), а числовыми, такими как 1.5, 3.0 и 9.5. Одно из главных преимуществ классификации на основе адаптивного обучения по сравнению с другими методами классификации заключается в том, что адаптивное обучение позволяет легко обрабатывать непосредственно как категориальные, так и числовые данные. Вы могли бы создать класс выделенного ученика с понятным описанием вроде «if Spread is less than or equal to 5.5 then Result is Lose», или более сложного ученика наподобие «if Spread is between 4.0 and 6.0 then Result is Win».
На мой взгляд, классификация на основе адаптивного обучения лучше всего подходит, когда зависимая переменная, подлежащая предсказанию, имеет всего два возможных значения. Однако более сложные формы адаптивного обучения способны справляться и с полиномиальной классификацией. Если вы хотите исследовать этот вопрос или теорию адаптивного обучения в целом, советую поискать статьи за авторством R. Schapire и Y. Freund.
Исследование машинного обучения предполагает, что какого-то одного лучшего метода классификации или предсказания данных не существует. Но адаптивное обучение — очень эффективный подход, образующий основу для добавления средств предсказания в какую-либо программную .NET-систему.
Джеймс Маккафри (Dr. James McCaffrey) — руководит в компании Volt Information Sciences Inc. повышением квалификации инженеров ПО из Microsoft, работающих в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и MSN Search. Автор книги «.NET Test Automation Recipes» (Apress, 2006). С ним можно связаться по адресу jammc@microsoft.com.
Выражаю благодарность за рецензирование статьи эксперту Microsoft Даррену Герингу (Darren Gehring).