Однослойный персептрон (пример)

Материал из MachineLearning.

Содержание

1 Постановка задачи линейного разделения классов
2 Описание алгоритма
3 Вычислительный эксперимент
4 Исходный код
5 Смотри также
6 Литература

Однослойный персептрон — это линейный алгоритм классификации, принцип работы которого основан на модели нервной клетки - нейрона. Представляет собой пример нейронной сети с одним скрытым слоем.

Постановка задачи линейного разделения классов

Пусть $X \in \mathbb{R}^n$ - множество объектов; $Y$ - множество допустимых ответов. Будем считать, что $\mathbf{x} = (x^0,x^1,\dots,x^n) \in \{-1\}\times X$ , где $x^j = f_j(x), j \geq 1$ - признаковое описание объекта, а $x_0 = -1$ - дополнительный константный признак; $Y = \{0,1\}$ . Задана обучающая выборка $\{(\mathbf{x}_i,y_i)\}_{i=1}^\ell$ . Значения признаков $x^j = f_j(x)$ рассматриваются как импульсы, поступающие на вход нейрона, которые складываются с весами $w_1,\dots,w_n$ . Если суммарный импульс превышает порог активации $w_0$ , то нейрон возбуждается и выдаёт на выходе 1, иначе выдаётся 0. Таким образом, нейрон вычисляет $n$ -арную булеву функцию вида

$a(x) = \varphi(\sum_{j=1}^{\ell}w_jx^j-w_0) = \varphi(f(\mathbf{x}_i,\mathbf{w}))$ , где $\varphi(z)=[z \geq 0], f(\mathbf{x}_i,\mathbf{w}) = \langle \mathbf{w},\mathbf{x}_i \rangle$

Для настройки вектора весов воспользуемся методом стохастического градиента. Возьмем квадратичную функцию потерь: $Q(\mathbf{w}) = \sum_{i=1}^{\ell}(a(\mathbf{x}_i)-y_i)^2$ , а в качестве функции активации возьмем сигмоидную функцию: $\varphi(z) = \frac{1}{1+e^{-z}}$ . Согласно принципу минимизации эмпирического риска задача сводится к поиску вектора, доставляющего минимум функционалу $Q(\mathbf{w}) \rightarrow \min_{\mathbf{w}$ .

Описание алгоритма

В соотвествие с методом градиентного спуска:

$\mathbf{w}:= \mathbf{w} - \eta \nabla Q(\mathbf{w}),$

где $\eta > 0$ величина шага в направлении антиградиента, называемая также темпом обучения (learning rate). Темп обучения выбираем, решая задачу одномерной минимизации: $\eta = argmin(Q( \mathbf{w} - \eta \nabla Q(\mathbf{w}))$ . Будем выбирать прецеденты $(\mathbf{x}_i, y_i)$ по одному в случайном порядке, для каждого делать градиентный шаг и сразу обновлять вектор весов:

$\mathbf{w}:= \mathbf{w} - \eta(a(x_i,\mathbf{w})-y_i)(1-\varphi\bigl(f(\mathbf{x}_i,\mathbf{w})\bigr))\varphi\bigl(f(\mathbf{x}_i,\mathbf{w})\bigr)\mathbf{x}_i.$ Значение функционала оцениваем: $Q = (1-\lambda)Q+\lambda \eps_i,$ где $\eps_i = (a(\mathbf{x_i},\mathbf{w})-y_i)^2$ , параметр $\lambda$ берем равным $1/\ell$ . Процедура останавливается после того, как изменение значения функционала функционала $Q$ становится меньше заданной константы: $|Q_n - Q_{n-1}|< \delta$

Вычислительный эксперимент

Показана работа алгоритма в серии задач, основанных как на реальных, так и на модельных данных.

Пример на реальных данных: ирисы

Из задачи о классификации ирисов выбраны 2 вида ирисов: Versicolour и Virginica, которые предлагается классифицировать по двум признакам — длине и ширине лепестка. Данные содержат информацию о 50 цветках каждого видаiris.txt.

На графике показаны результаты классификации. По оси абсцисс отложено значение одного признака (длина лепестка в см.), а по оси ординат — значение второго признака (ширина лепестка в см.). Различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующего цвета. Зеленой линией показана граница между классами, построенная алгоритмом.

%load data
load 'iris.txt';
x = iris;
x(:,1:2) = []; %eliminating first two attributes
y = [repmat(0,50,1);repmat(1,50,1)]; %creating class labels
 
%plotting data
plot(x(y == 0,1),x(y == 0,2),'*r');
hold on
plot(x(y == 1,1),x(y == 1,2),'*b');
 
%invoke One layer perceptron algorithm
w = OneLayerPerc(x,y);
 
%getting classification
y = PercTest(x,w);
 
%plotting resulting classification
plot(x(y == 0,1),x(y == 0,2),'or');
plot(x(y == 1,1),x(y == 1,2),'ob');
 
plot([w(3)/w(1),0],[0,w(3)/w(2)],'g');
 
hold off;

Заметим, что данные линейно не разделимы, но алгоритм показывает хороший результат, допустив 5 ошибок классификации.

Модельные данные (простой вариант): 2 нормально распределенных класса линейно разделимы

%generating 2 sample normal classes
x = GetNormClass(100,[0,0],[1,1]);
s = GetNormClass(100,[4,4],[1,1]);
 
x = [x;s];
 
y = [repmat(1,100,1);repmat(0,100,1)];
 
%invoke One layer perceptron algorithm
w = OneLayerPerc(x,y);
 
%generating control data with the same distribution
x = GetNormClass(100,[0,0],[1,1]);
s = GetNormClass(100,[4,4],[1,1]);
x = [x;s];
 
%plotting control data
plot(x(:,1),x(:,2),'*r');
hold on
plot(s(:,1),s(:,2),'*b');
 
%getting classification
y = PercTest(x,w);
 
%plotting classified data
plot(x(y == 0,1),x(y == 0,2),'ob');
plot(x(y == 1,1),x(y == 1,2),'or');
 
plot([w(3)/w(1),0],[0,w(3)/w(2)],'g');
 
hold off

Алгоритм не допустил при классификации ни одной ошибки.

Модельные данные (сложный вариант): задача исключающего ИЛИ

%generate 2 sample classes
x = GetNormClass(100,[0,0],[1,1]);
s = GetNormClass(100,[6,6],[1,1]);
x = [x;s];
s = GetNormClass(100,[0,6],[1,1]);
x = [x;s];
s = GetNormClass(100,[6,0],[1,1]);
x = [x;s];
 
 
y = [repmat(1,200,1);repmat(0,200,1)];
 
%invoke One layer perceptron algorithm
w = OneLayerPerc(x,y);
 
%generate control data with the same distribution
x = GetNormClass(100,[0,0],[1,1]);
s = GetNormClass(100,[6,6],[1,1]);
x = [x;s];
s = GetNormClass(100,[0,6],[1,1]);
x = [x;s];
s = GetNormClass(100,[6,0],[1,1]);
x = [x;s];
 
 
%plot control data
plot(x(y == 1,1),x(y == 1,2),'*r');
hold on
plot(x(y == 0,1),x(y == 0,2),'*b');
 
%get classification
y = PercTest(x,w);
 
%plot classified data
plot(x(y == 0,1),x(y == 0,2),'ob');
plot(x(y == 1,1),x(y == 1,2),'or');
 
plot([w(3)/w(1),0],[0,w(3)/w(2)],'g');
 
hold off

Алгоритм допустил около 50% ошибок классификация, что неудивительно, т.к. входные данные были принципиально линейно неразделимы.

Исходный код

Скачать листинги алгоритмов можно здесь [1].

Смотри также

Литература

Nabney Ian, NetLab Algotithms for Pattern Recognition. Springer. 2001.
К. В. Воронцов, Лекции по линейным алгоритмам классификации
Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006.

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

Студент: Максим Панов

Преподаватель: В.В.Стрижов

Срок: 28 мая 2009

В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B4%D0%BD%D0%BE%D1%81%D0%BB%D0%BE%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D1%81%D0%B5%D0%BF%D1%82%D1%80%D0%BE%D0%BD_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категории: Линейные классификаторы | Нейронные сети | Практика и вычислительные эксперименты