Примечание
Для доступа к этой странице требуется авторизация. Вы можете попробовать войти или изменить каталоги.
Для доступа к этой странице требуется авторизация. Вы можете попробовать изменить каталоги.
Обучение сетей на основе радиально-базисных функций
Исходный код можно скачать по ссылке.
Сеть на основе радиально-базисной функции (radial basis function, RBF) — это программная система, способная классифицировать данные и делать предсказания. RBF-сети имеют определенное поверхностное сходство с нейронными сетями, но на самом деле они довольно сильно отличаются. RBF-сеть принимает одно или более числовых входных значений и генерирует одно или более числовых выходных значений. Выходные значения определяются входными, а также набором параметров, называемых RBF-центроидами (centroids) (или центрами масс), набором RBF-интервалов по ширине (widths), набором весовых значений (weights) и набором смещений (biases).
Для упрощения терминологии комбинация RBF-значений весов и смещений иногда собирательно называют весовыми значениями. Контекст, в котором используется этот термин, обычно проясняет смысл. Подробнее на эту тему см. мою статью «Radial Basis Function Networks for Programmers» в октябрьском номере «MSDN Magazine» за 2013 г. (msdn.microsoft.com/magazine/dn451445).
При использовании RBF-сети для классификации и предсказания основная трудность — подобрать такой набор значений для центроидов, интервалов ширины, весовых значений и смещений, чтобы вычисленные выходные значения максимально соответствовали набору известных выходных значений. Этот процесс называется обучением RBF-сети. Хотя исследователи изучают RBF-сети с момента их появления в 1988 году, практического руководства, которое поясняло бы, как реализовать обучение RBF-сети, по сути, до сих пор нет. В этой статье будет представлена и описана полная демонстрационная RBF-сеть.
Взгляните на демонстрационную программу на рис. 1. Она создает RBF-модель, которая предсказывает виды цветков ириса — setosa (ирис щетинистый), versicolor (разноцветный) или virginica (виргинский) — по четырем числовым значениям, относящимся к длине и ширине чашелистика цветка, а также к длине и ширине лепестков. Источник данных демонстрационной программы состоит из 30 элементов, которые являются подмножеством общеизвестного эталонного набора из 150 элементов, называемого ирисами Фишера (Fisher’s Iris data). Эти 30 элементов данных были обработаны заранее. Четыре числовых x-значения были нормализованы, чтобы значения, меньшие нуля, указывали длину или ширину, более короткую, чем среднюю, а значения, большие нуля, — длину или ширину, превышающую среднюю. Кроме того, y-значение для видов кодировалось как (0,0,1), (0,1,0) или (1,0,0) для setosa, versicolor или virginica соответственно.
Рис. 1. Программа, демонстрирующая RBF-сеть
Демонстрационная программа выделяет из набора с 30 элементами данных набор с 24 элементами, используемый для обучения. Кроме того, остается контрольный набор с шестью элементами для тестирования/оценки конечной RBF-модели. Программа создает экземпляр RBF-сети с четырьмя входными узлами (по одному на каждое входное значение данных), пятью скрытыми узлами обработки и тремя выходными (по одному на каждое выходное значение данных). Наилучшее количество скрытых узлов в основном определяется методом проб и ошибок. Выбор пяти скрытых узлов в демонстрационной программе был произвольным.
На рис. 1 видно, что обучение RBF-сети проходит в три этапа. На первом определяются центроиды. Их можно считать репрезентативными x-значениями, выбранными из обучающих данных. RBF-сеть требует по одному центроиду на каждый скрытый узел, поэтому демонстрационной программе нужны пять центроидов. Алгоритм обучения выбирает x-значения из элементов обучающих данных [9], [19], [21], [20] и [4]. Иначе говоря, первый центроид — это (–0.362, –2.019, 0.074, 0.112).
На втором этапе определяются интервалы ширины. Их можно рассматривать как значения, описывающие расстояние между центроидами. RBF-сеть требует по одному такому значению на каждый скрытый узел. Демонстрационная программа вычисляет единственный общий интервал ширины со значением 3.3318 для всех пяти скрытых узлов вместо вычисления пяти раздельных значений.
На третьем этапе определяются весовые значения и смещения. Эти значения можно считать числовыми константами. Если в RBF-сети имеется NI входных узлов, NH скрытых узлов и NO выходных, то необходимы (NH * NO) весовых значений и NO смещений. Поскольку RBF-сеть в демонстрации имеет архитектуру «4-5-3», ей нужно 5 * 3 = 15 весовых значений плюс три смещения, что дает в итоге 18 весовых значений и смещений. Демонстрационная программа использует оптимизацию роя частиц (particle swarm optimization, PSO) для определения 18 весовых значений и смещений.
После обучения демонстрационной RBF-сети с помощью набора обучающих данных с 24 элементами вы подаете в сеть набор тестовых данных из шести элементов. В этом примере RBF-сеть корректно предсказывает виды из шести тестовых элементов, что дает точность классификации, равную 0.8333.
В этой статье предполагается, что вы владеете навыками программирования на языке C# по крайней мере на среднем уровне и имеете базовое представление о механизме ввода-обработки-вывода в сетях на основе радиально-базисных функций. Я обсуждал этот механизм в прошлой статье. Исходный код демонстрационной программы слишком велик, чтобы его можно было полностью представить в этой статье, но вы можете скачать его по ссылке archive.msdn.microsoft.com/mag201312TestRun.
Общая структура программы
Чтобы создать демонстрационную программу, я запустил Visual Studio 2012 и создал консольное приложение на C# под названием RadialNetworkTrain. В этой программе нет значимых зависимостей от .NET, поэтому можно работать в любой версии Visual Studio. После загрузки шаблона кода я переименовал в окне Solution Explorer файл Program.cs в RadialTrainProgram.cs, и Visual Studio автоматически переименовал связанный с ним класс Program. В начале исходного кода я удалил все ненужные ссылки на пространства имен .NET, оставив лишь ссылку на пространство имен System.
Структура программы в целом с некоторыми удаленными выражениями WriteLine и небольшой правкой представлена на рис. 2. В дополнение к классу программы, в котором находится метод Main, в демонстрации имеются класс RadialNetwork, который инкапсулирует создание и обучение RBF-сети, класс Particle, который определяет объект частицы для использования с алгоритмом обучения RBF, вычисляющий весовые значения и смещения, и класс Helpers, который содержит вспомогательные методы отображения.
Рис. 2. Общая структура программы, демонстрирующей RBF-сеть
using System;
namespace RadialNetworkTrain
{
class RadialTrainProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin radial basis function (RBF) network training demo");
double[][] allData = new double[30][];
allData[0] = new double[] { -0.784, 1.255, -1.332, -1.306, 0, 0, 1 };
allData[1] = new double[] { -0.995, -0.109, -1.332, -1.306, 0, 0, 1 };
// И т. д.
allData[28] = new double[] { 0.904, -1.473, 1.047, 0.756, 1, 0, 0 };
allData[29] = new double[] { 1.431, 1.528, 1.209, 1.659, 1, 0, 0 };
Console.WriteLine("First four and last line of normalized, encoded input data:");
Helpers.ShowMatrix(allData, 4, 3, true, true);
double[][] trainData = null;
double[][] testData = null;
int seed = 8; // обеспечивает хорошую демонстрацию
GetTrainTest(allData, seed, out trainData, out testData);
Helpers.ShowMatrix(trainData, trainData.Length, 3, true, false);
Helpers.ShowMatrix(testData, testData.Length, 3, true, false);
int numInput = 4;
int numHidden = 5;
int numOutput = 3;
RadialNetwork rn = new RadialNetwork(numInput, numHidden, numOutput);
Console.WriteLine("Beginning RBF training");
int maxIterations = 100; // максимум для PSO
double[] bestWeights = rn.Train(trainData, maxIterations);
Console.WriteLine("Evaluating RBF accuracy on the test data");
rn.SetWeights(bestWeights);
double acc = rn.Accuracy(testData);
Console.WriteLine("Classification accuracy = " + acc.ToString("F4"));
Console.WriteLine("End RBF network training demo");
}
static void GetTrainTest(double[][] allData, int seed,
out double[][] trainData, out double[][] testData) { . . }
}
public class RadialNetwork
{
private static Random rnd = null;
private int numInput;
private int numHidden;
private int numOutput;
private double[] inputs;
private double[][] centroids;
private double[] widths;
private double[][] hoWeights;
private double[] oBiases;
private double[] outputs;
public RadialNetwork(int numInput, int numHidden, int numOutput) { . . }
private static double[][] MakeMatrix(int rows, int cols) { . . }
public void SetWeights(double[] weights) { . . }
public double[] GetWeights() { . . }
private double MeanSquaredError(double[][] trainData,
double[] weights) { . . }
public double Accuracy(double[][] testData) { . . }
private static int MaxIndex(double[] vector) { . . }
public double[] ComputeOutputs(double[] xValues) { . . }
private static double[] Softmax(double[] rawOutputs) { . . }
public double[] Train(double[][] trainData, int maxIterations) { . . }
private void DoCentroids(double[][] trainData) { . . }
private static double AvgAbsDist(double[] v1, double[] v2,
int numTerms) { . . }
private int[] DistinctIndices(int n, int range) { . . }
private void DoWidths(double[][] centroids) { . . }
private double[] DoWeights(double[][] trainData, int maxIterations) { . . }
private static double EuclideanDist(double[] v1, double[] v2,
int numTerms) { . . }
private static void Shuffle(int[] sequence) { . . }
}
public class Particle
{
// Здесь должна быть реализация
}
public class Helpers
{
// Здесь должна быть реализация
}
}
Класс RadialNetwork не столь сложен, как предполагается структурой программы, поскольку большая часть методов этого класса является вспомогательной. Метод Train выполняет трехэтапный процесс обучения, вызывая вспомогательные методы DoCentroids, DoWidths и DoWeights. Закрытые методы AvgAbsDist и DistinctIndices являются вспомогательными для DoCentroids. Метод DoWeights использует закрытый метод Shuffle для обработки элементов обучающих данных каждый раз в другом порядке через итеративный алгоритм оптимизации роя частиц.
Основная часть демонстрационной программы довольно проста. Сначала подготавливаются нормализованные и кодированные данные:
double[][] allData = new double[30][];
allData[0] = new double[] { -0.784, 1.255, -1.332, -1.306, 0, 0, 1 };
allData[1] = new double[] { -0.995, -0.109, -1.332, -1.306, 0, 0, 1 };
// И т. д.
allData[28] = new double[] { 0.904, -1.473, 1.047, 0.756, 1, 0, 0 };
allData[29] = new double[] { 1.431, 1.528, 1.209, 1.659, 1, 0, 0 };
Здесь данные «зашиты» в код простоты ради. В большинстве случаев ваши данные будут храниться в текстовом файле или в SQL-таблице. Затем эти данные разделяются на обучающие и контрольные:
double[][] trainData = null;
double[][] testData = null;
int seed = 8;
GetTrainTest(allData, seed, out trainData, out testData);
Создается экземпляр RBF-сети:
int numInput = 4;
int numHidden = 5;
int numOutput = 3;
RadialNetwork rn = new RadialNetwork(numInput,
numHidden, numOutput);
Как упоминалось в предыдущем разделе, оптимальное количество скрытых узлов приходится определять по большей части методом проб и ошибок. Сеть обучается:
int maxIterations = 100;
double[] bestWeights = rn.Train(trainData, maxIterations);
Наконец, оценивается конечная модель:
rn.SetWeights(bestWeights);
double acc = rn.Accuracy(testData);
Console.WriteLine("Classification accuracy = " +
acc.ToString("F4"));
Массив bestWeights хранит весовые значения и смещения для RBF, определенные методом Train. Метод SetWeights загружает все эти значения. От вас не требуется явной загрузки центроидов и интервалов ширины, поскольку эти значения были заданы методом Train.
Ввод-обработка-вывод в RBF-сети
Чтобы понять процесс обучения RBF-сети, нужно представлять механизм ввода-обработки-вывода в такой сети. Схема на рис. 3 показывает, как демонстрационная RBF-сеть вычисляет выходные данные для элемента тестовых данных [1] = (0.482, 0.709, 0.452, 0.498) после ее обучения. Входные x-значения передаются каждому скрытому узлу. Каждый скрытый узел вычисляет свое выходное значение, используя собственные значения центроида и интервала ширины.
Рис. 3. Архитектура RBF-сети
Input | Ввод |
Output | Вывод |
(Most hidden-to-output weight values omitted for clarity) | (Большинство весовых значений между скрытыми и выходными узлами опущено для лучшего восприятия схемы) |
Например, центроид самого верхнего скрытого узла имеет значение (–0.362, –2.019, 0.074, 0.112) и интервал ширины 3.3318. Затем локальные выходные значения каждого скрытого узла используются для определения предварительных выходных значений; для этого вычисляются взвешенная сумма входных значений плюс смещение. Так, если hOutput[0] представляет локальный вывод скрытого узла 0, то предварительный вывод самого верхнего выходного узла равен (hOutput[0] * w[0][0]) + (hOutput[1] * w[1][0]) + (hOutput[2] * w[2][0]) + (hOutput[3] * w[3][0]) + (hOutput[4] * w[4][0]) + bias[0] = –12.7999.
После вычисления три предварительных выходных значения преобразуются в конечные с помощью функции softmax. Идея заключается в такой модификации предварительных выходных значений, чтобы все конечные выходные значения укладывались в диапазон между 0.0 и 1.0, а сумма была равна 1.0. Это позволяет, в принципе, интерпретировать выходные значения как вероятности.
На рис. 3 конечные выходные значения равны (0.2897, 0.6865, 0.0237). Поскольку средний узел имеет наибольшее значение, он интерпретируется как 1, а остальные два значения — как 0, что дает логический вывод (0, 1, 0). Вспомните, что тестовые данные имеют значения (0.482, 0.709, 0.452, 0.498, 0.000, 1.000, 0.000), где первые четыре значения являются входными, а последние три — целевыми, поэтому RBF-сеть делает правильное предсказание видов (в данном случае — ирис разноцветный). Теперь вопрос: откуда берутся значения для центроидов, интервалов ширины, весовых значений и смещений RBF-сети?
Определение центроидов RBF-сети
Метод Train класса RadialNetwork в основном является оболочкой трех вспомогательных методов, которые и выполняют всю работу:
public double[] Train(double[][] trainData, int maxIterations)
{
DoCentroids(trainData);
DoWidths(this.centroids);
double[] bestWeights = DoWeights(trainData, maxIterations);
return bestWeights;
}
Метод DoCentroids определяет репрезентативные входные x-значения. Здесь много возможностей. Один из распространенных подходов — применение алгоритма кластеризации на основе k-средних или k-медоидов (k-medoids), который итеративно назначает и переназначает элементы данных так, чтобы группировать схожие элементы. По окончании у каждого кластера будет репрезентативный член данных. Вы можете использовать эти значения как центроиды RBF.
Другой подход — извлечение x-значений из элементов обучающих данных, выбираемых случайным образом. Это просто, но есть риск случайного выбора неподходящих центроидов.
Демонстрационная программа использует подход, который можно было бы назвать облегченным алгоритмом кластеризации; его суть изложена в следующем псевдокоде:
Инициализируем maxDistance
Инициализируем bestIndices
loop
Выбираем случайные индексы numHidden в обучающие данные
Оцениваем расстояние между выбранными элементами данных
if это расстояние > maxDistance then
set maxDistance = текущее расстояние
set bestIndices = текущие индексы
end if
end loop
Получаем x-значения в обучающих данных при bestIndices
Сохраняем x-значения в центроиды RBF
Эту идею лучше всего проиллюстрировать на примере. Допустим, обучающие данные состоят из 24 элементов, показанных на рис. 1. Также предположим, что после первого прохода цикла обработки случайно выбираются четыре индекса: [0], [1], [2] и [3]. Они соответствуют:
0: ( 1.537, -0.382, 1.317, 0.756)
1: (-0.468, 2.346, -1.170, -1.048)
2: ( 1.115, 0.164, 0.560, 0.370)
3: ( 1.220, 0.436, 0.452, 0.241)
Это центроиды-кандидаты. Идея в том, чтобы получить репрезентативные x-значения, т. е. вам не нужны значения, близкие друг к другу. Поэтому вы вычисляете некую меру расстояния между этими центроидами-кандидатами. Здесь возможно много подходов. Демонстрационная программа оценивает среднее расстояние между всеми возможными парами центроидов-кандидатов, вычисляя среднее расстояние между смежными парами кандидатов вместо вычисления среднего расстояния между всеми возможными парами. В этом примере она вычисляет расстояния между кандидатами [0] и [1], между [1] и [2], а также между [2] и [3].
Распространенный подход к вычислению расстояния — применение евклидовой метрики, которая представляет собой квадратный корень из суммы квадратов разности между значениями. (Заметьте, что демонстрационная RBF-сеть использует гауссово ядро, которое вычисляет локальные выходные значения скрытых узлов с помощью евклидовой метрики.) Однако демонстрационная программа использует вариацию метрики Манхэттена (Manhattan distance), где расстояние является средним из разности абсолютных значений. Таким образом, расстояние между кандидатами [0] и [1] равно:
d = abs(1.537 - (-0.468)) + . . . + abs(0.756 - (-1.048)) / 4
= 2.256
Процесс генерации набора центроидов-кандидатов и вычисление предполагаемого среднего расстояния для этого набора повторяется заданного число раз, после чего в качестве набора RBF-центроидов выбирается набор кандидатов с наибольшим предполагаемым средним расстоянием.
Заметьте, что определение центроидов RBF-сети можно рассматривать как неконтролируемый метод обучения (unsupervised training technique), поскольку целевые значения (например, 0, 1, 0) в обучающих данных не нужны или не используются. Это означает, что центроиды можно определять очень быстро. Кроме того, интервалы ширины, весовые значения и смещения для RBF-сети можно (по крайней мере, теоретически) вычислять гораздо быстрее, чем примерный эквивалент весовых значений и смещений в нейронной сети. Это дает RBF-сетям потенциальное преимущество над нейронными сетями (но, как вы увидите, не все так просто).
В процессе нахождения центроидов RBF-сети возникает интересная подзадача определения индексов-кандидатов. Демонстрационная программа использует для этого весьма интеллектуальный алгоритм выборки с резервированием (reservoir sampling). Идея в том, чтобы выбрать первые возможные n индексов, а затем вероятностным методом заменить начальные индексы остающимися возможными индексами:
private int[] DistinctIndices(int n, int range)
{
// Выборка с резервированием;
// предполагается, что rnd существует
int[] result = new int[n];
for (int i = 0; i < n; ++i)
result[i] = i;
for (int t = n; t < range; ++t) {
int m = rnd.Next(0, t + 1);
if (m < n) result[m] = t;
}
return result;
}
Хотя этот метод лаконичен, он очень тонкий. К альтернативам относятся подход с использованием грубой силы, где генерируются случайные индексы, а затем проверяется, есть ли среди них дубликаты.
Определение интервалов ширины в RBF-сети
Механизм ввода-обработки-вывода в RBF-сети требует значения ширины для каждого скрытого узла. Эти значения можно определить множеством способов. Самый простой подход (он и используется в демонстрации) — вычисление одной общей ширины, которую могут использовать все скрытые узлы. Исследования в этой области дают довольно туманные результаты, и выводы иногда делаются прямо противоположные. Демонстрационная программа вычисляет общую ширину как среднюю евклидову метрику между всеми возможными парами центроидов. В псевдокоде это выглядит так:
sumOfDists = 0.0
for each пары центроидов
Накапливаем евклидову метрику между текущей парой
end loop
return накопленное sumOfDists / число пар
Исходя из моего опыта, эффективность RBF-сетей сильно зависит от значений, используемых для интервалов ширины в скрытых узлах. Исследования показывают, что слишком малая ширина приводит к «переобучению», а слишком большая — к «недообучению»; в любом случае это ведет к низкой точности классификации. Если вы поэкспериментируете с демонстрационным кодом, вручную изменяя значения интервалов ширины для RBF-сети, то сами увидите этот эффект в действии.
Помимо использования среднего расстояния между центроидами, davg, для общей ширины в скрытых узлах, в исследованиях также предлагается применять (2 * davg), или (davg / sqrt(2 * numHidden)), и много других значений. А вместо использования общей ширины есть масса возможностей вычислять разные интервалы ширины для каждого скрытого узла. По моему мнению, высокая чувствительность RBF-сетей к значениям ширины наряду с отсутствием убедительных результатов исследований, относящихся к тому, как лучше вычислять эти значения, — основные недостатки RBF-сетей в сравнении с такими альтернативами, как нейронные сети и векторных машин (vector machines).
Определение весовых значений и смещений для RBF-сети
После определения центроидов и интервалов ширины заключительный этап в обучении RBF-сети — определение весовых значений и смещений. Теоретически вы можете легко и быстро вычислять весовые значения для RBF-сети, поскольку, вольно выражаясь, у вас есть n уравнений с n неизвестными. Поэтому в теории можно использовать стандартные численные методы для нахождения весовых значений.
К сожалению, на практике применение стандартных методов создает множество проблем. Например, многие стандартные численные методы для решения систем уравнений включают использование обращения матрицы. Но обращение матрицы может закончиться неудачей по многим причинам.
Поэтому вместо детерминированных, но, возможно, хрупких численных методов для точного определения весовых значений RBF-сети демонстрационная программа применяет оптимизацию роя частиц (particle swarm optimization, PSO), чтобы приблизительно оценить наилучшие значения. PSO является мета-эвристическим алгоритмом, основанным на координированном поведении группы, например стаи птиц или рыб. В PSO у частицы есть позиция, которая представляет потенциальное решение (в данном случае — лучший набор весовых значений). У каждой частицы также имеется скорость, определяющая ее следующую позицию.
В PSO создается набор частиц. При каждом моделируемом такте времени каждая частица перемещается в новую позицию на основе ее текущей позиции и скорости, лучшей известной исторической позиции данной частицы и лучшей известной исторической позиции любой из частиц. Вот как выглядит алгоритм PSO, выраженным высокоуровневым псевдокодом:
Задаем количество частиц
Задаем maxIterations
Инициализируем все частицы по случайным позициям
loop maxIterations раз
for each частицы
Обновляем скорость текущей частицы
Используем новую скорость для расчета новой позиции
Вычисляем ошибку для новой позиции
Проверяем, является ли новая позиция лучшей для частицы
Проверяем, является ли новая позиция лучшей для всех частиц
end for
end loop
return лучшую позицию, найденную какой-либо частицей
PSO — сама по себе увлекательная тема. Вы можете узнать больше об этом алгоритме в моей статье «Particle Swarm Optimization» в номере за август 2011 г. (msdn.microsoft.com/magazine/hh335067). PSO требует определения нескольких свободных параметров, в том числе весовых констант (управляющих относительным влиянием текущей позиции частицы), лучшей исторической позиции и лучшей глобальной исторической позиции. PSO также требует указывать количество частиц, максимальное число итераций и (не обязательно) порог ошибок для раннего выхода из алгоритма. Вы можете поэкспериментировать с этими факторами, используя демонстрационный код.
В дополнение к PSO и традиционным численным методам существует много альтернатив в нахождении весовых значений для RBF-сети, включая простой градиентный спуск (simple gradient descent) и генетические алгоритмы с применением векторов вещественных значений (real-valued genetic algorithms). Хотя теория RBF-сетей изучалась довольно активно, убедительных результатов исследований по сравнительной эффективности различных методов обучения относительно мало.
Заключение
Код демонстрационной программы наряду с пояснениями, изложенными в этой статье, должны дать вам твердый фундамент для дальнейшего изучения RBF-сетей. Хотя RBF-сети хорошо известны в научно-исследовательском сообществе, не похоже, чтобы они часто использовались сообществом разработчиков программного обеспечения в сравнении с такими альтернативами, как нейросетевые классификаторы (neural network classifiers), наивные байесовские классификаторы (naive Bayes classifiers) и логистическая регрессия (logistic regression). Одна из возможных причин этого, по-видимому, связана с нехваткой примеров практических реализаций. Другая вероятная причина — неопределенность вокруг фундаментальных факторов RBF-сети, особенно тех, которые относятся к вычислению интервалов ширины. По моему мнению, четких научных доказательств того, что RBF-сети являются более эффективными, менее эффективными или примерно эквивалентными альтернативным методам машинного обучения, нет.
Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.
Выражаю благодарность за рецензирование статьи эксперту Microsoft Research Кирку Олинику (Kirk Olynyk).