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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Исходный код)
 
(39 промежуточных версий не показаны.)
Строка 1: Строка 1:
{{TOCright}}
{{TOCright}}
-
'''Однослойный персептрон''' — это модель нейрона, простейший пример [[нейронная сеть|нейронной сети]]. Фактически представляет собой линейный пороговый классификатор.
+
'''Однослойный персептрон''' — это [[Линейный классификатор | линейный алгоритм классификации]], принцип работы которого основан на модели нервной клетки - [[нейрон]]а. Представляет собой пример [[нейронная сеть|нейронной сети]] с одним скрытым слоем.
-
 
+
== Постановка задачи линейного разделения классов ==
-
== Постановка задачи линейного разделения классов==
+
Пусть <tex>X \in \mathbb{R}^n</tex> - множество объектов;
-
Пусть <tex>X</tex> - пространство объектов; <tex>Y</tex> - множество допустимых ответов. Будем считать, что <tex>x = (x^0,x^1,\dots,x^n) \in \{-1\}\times\mathbb{R}^n</tex>, где <tex>x^j = f_j(x), j \geq 1</tex> - признаковое описание объекта, а <tex>x_0 = -1</tex> - дополнительный константный признак; <tex>Y = \{0,1\}</tex>. Задана обучающая выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^\ell</tex>. Значения признаков <tex>x^j = f_j(x)</tex> рассматриваются как импульсы, поступающие на вход нейрона, которые складываются с весами <tex>w_1,\dots,w_n</tex>. Если суммарный импульс превышает порог активации <tex>w_0</tex>, то нейрон возбуждается
+
<tex>Y</tex> - множество допустимых ответов. Будем считать, что <tex>\mathbf{x} = (x^0,x^1,\dots,x^n) \in \{-1\}\times X</tex>, где <tex>x^j = f_j(x), j \geq 1</tex> - признаковое описание объекта, а <tex>x_0 = -1</tex> - дополнительный константный признак; <tex>Y = \{0,1\}</tex>. Задана обучающая выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^\ell</tex>. Значения признаков <tex>x^j = f_j(x)</tex> рассматриваются как импульсы, поступающие на вход нейрона, которые складываются с весами <tex>w_1,\dots,w_n</tex>. Если суммарный импульс превышает порог активации <tex>w_0</tex>, то нейрон возбуждается
и выдаёт на выходе 1, иначе выдаётся 0. Таким образом, нейрон вычисляет <tex>n</tex>-арную булеву функцию вида
и выдаёт на выходе 1, иначе выдаётся 0. Таким образом, нейрон вычисляет <tex>n</tex>-арную булеву функцию вида
-
<center><tex>a(x) = \varphi(\sum_{i=1}^{\ell}w_jx^j-w_0) = \varphi(\langle w,x \rangle)</tex>, где <tex>\varphi(z)=[z \geq 0]</tex></center>
+
<center><tex>a(x) = \varphi(\sum_{j=1}^{\ell}w_jx^j-w_0) = \varphi(f(\mathbf{x}_i,\mathbf{w}))</tex>, где <tex>\varphi(z)=[z \geq 0], f(\mathbf{x}_i,\mathbf{w}) = \langle \mathbf{w},\mathbf{x}_i \rangle </tex></center>
-
Требуется найти значения параметров, при которых алгоритм наилучшим образом аппроксимирует целевую зависимость, заданную на объектах обучающей выборки.
+
Для настройки вектора весов воспользуемся методом стохастического градиента. Возьмем квадратичную функцию потерь: <tex>Q(\mathbf{w}) = \sum_{i=1}^{\ell}(a(\mathbf{x}_i)-y_i)^2</tex>, а в качестве функции активации возьмем сигмоидную функцию: <tex>\varphi(z) = \frac{1}{1+e^{-z}}</tex>. Согласно принципу [[Минимизация эмпирического риска | минимизации эмпирического риска]] задача сводится к поиску вектора, доставляющего минимум функционалу <tex> Q(\mathbf{w}) \rightarrow \min_{\mathbf{w}</tex>.
== Описание алгоритма ==
== Описание алгоритма ==
-
Для настройки вектора весов воспользуемся методом стохастического градиента. Возьмем квадратичную функцию потерь: <tex>Q(w) = \sum_{i=1}^{\ell}(a(x_i)-y_i)^2</tex>, а в качестве функции активации возьмем сигмоидную функцию: <tex>\varphi(z) = \frac{1}{1+e^{-z}}</tex>. Согласно принципу минимизации эмпирического риска задача сводится к поиску вектора, доставляющего минимум функционалу <tex> Q(w) \rightarrow \min_w</tex>. Применим для минимизации метод градиентного спуска:
+
В соотвествие с методом градиентного спуска:
-
<center><tex>w:=w - \eta \nabla Q(w)</tex>,</center>
+
<center><tex>\mathbf{w}:= \mathbf{w} - \eta \nabla Q(\mathbf{w}),</tex></center>
-
где <tex>\eta > 0</tex> величина шага в направлении антиградиента, называемая также темпом обучения (learning rate). Будем выбирать прецеденты <tex>(x_i, y_i)</tex> по одному в случайном порядке, для каждого делать градиентный шаг и сразу обновлять вектор весов:
+
где <tex>\eta > 0</tex> величина шага в направлении антиградиента, называемая также темпом обучения (learning rate). Темп обучения выбираем, решая задачу одномерной минимизации:<tex>\eta = argmin(Q( \mathbf{w} - \eta \nabla Q(\mathbf{w}))</tex>. Будем выбирать прецеденты <tex>(\mathbf{x}_i, y_i)</tex> по одному в случайном порядке, для каждого делать градиентный шаг и сразу обновлять вектор весов:
-
<center><tex>w:= w - \eta(a(x_i,w)-y_i)(1-\varphi(\langle w,x_i \rangle))\varphi(\langle w,x_i \rangle)x_i</tex>.</center> Значение функционала оцениваем: <center><tex>Q = (1-\lambda)Q+\lambda \eps_i</tex></center>, где <tex>\eps_i = (a(x_i,w)-y_i)^2</tex>.
+
<center><tex>\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.</tex></center>
 +
Значение функционала оцениваем: <center><tex>Q = (1-\lambda)Q+\lambda \eps_i,</tex></center> где <tex>\eps_i = (a(\mathbf{x_i},\mathbf{w})-y_i)^2</tex>, параметр <tex>\lambda</tex> берем равным <tex>1/\ell</tex>.
Процедура останавливается после того, как изменение значения функционала функционала <tex>Q</tex> становится меньше заданной константы: <center><tex>|Q_n - Q_{n-1}|< \delta</tex></center>
Процедура останавливается после того, как изменение значения функционала функционала <tex>Q</tex> становится меньше заданной константы: <center><tex>|Q_n - Q_{n-1}|< \delta</tex></center>
Строка 19: Строка 20:
Показана работа алгоритма в серии задач, основанных как на реальных, так и на модельных данных.
Показана работа алгоритма в серии задач, основанных как на реальных, так и на модельных данных.
-
1)Пример на реальных данных: ирисы.
+
=== Пример на реальных данных: ирисы ===
-
Из классической задачи о классификации ирисов выбраны 2 вида ирисов: Versicolour и Virginica, которые предлагается классифицировать по двум признакам – длине и ширине лепестка. Данные содержат информацию о 50 цветках каждого вида ([http://mlalgorithms.svn.sourceforge.net/viewvc/mlalgorithms/OneLayerPerceptron/iris.txt iris.txt])
+
Из задачи о классификации ирисов выбраны 2 вида ирисов: Versicolour и Virginica, которые предлагается классифицировать по двум признакам — длине и ширине лепестка. Данные содержат информацию о 50 цветках каждого вида[http://mlalgorithms.svn.sourceforge.net/viewvc/mlalgorithms/OneLayerPerceptron/iris.txt iris.txt].
[[Изображение:Iris.jpg|Iris.jpg]]
[[Изображение:Iris.jpg|Iris.jpg]]
[[Изображение:iris.png|300px]]
[[Изображение:iris.png|300px]]
-
На графике показаны результаты классификации. По оси х отложено значение одного признака(длина лепестка в см)б а по оси у значение второго признака(ширина лепестка в см). Различные классы показаны крестика различных цветов, а результат классификации кружочками соотвествующего цвета. Зеленой линией показана граница между классами, построенная алгоритмом.
+
На графике показаны результаты классификации. По оси абсцисс отложено значение одного признака (длина лепестка в см.), а по оси ординат — значение второго признака (ширина лепестка в см.). Различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующего цвета. Зеленой линией показана граница между классами, построенная алгоритмом.
<source lang="matlab">
<source lang="matlab">
%load data
%load data
load 'iris.txt';
load 'iris.txt';
x = iris;
x = iris;
-
x(:,1) = []; %eliminating first two attributes
+
x(:,1:2) = []; %eliminating first two attributes
-
x(:,1) = [];
+
y = [repmat(0,50,1);repmat(1,50,1)]; %creating class labels
y = [repmat(0,50,1);repmat(1,50,1)]; %creating class labels
Строка 54: Строка 54:
</source>
</source>
-
Заметим, что данные линейно не разделимы, но алгоритм показывает хороший результат, допустив всего 5 ошибок классификации.
+
Заметим, что данные линейно не разделимы, но алгоритм показывает хороший результат, допустив 5 ошибок классификации.
-
2) Модельные данные(простой вариант): 2 нормально распределенных класса линейно разделимы.
+
=== Модельные данные (простой вариант): 2 нормально распределенных класса линейно разделимы ===
<source lang="matlab">
<source lang="matlab">
Строка 94: Строка 94:
[[Изображение:simple.png|300px]]
[[Изображение:simple.png|300px]]
-
Алгоритм справился с задачей, не допустив при классификации ни одной ошибки.
+
Алгоритм не допустил при классификации ни одной ошибки.
 +
 
 +
=== Модельные данные (сложный вариант): задача исключающего ИЛИ ===
 +
<source lang="matlab">
 +
%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
 +
</source>
 +
 
 +
[[Изображение:Hard.png|300px]]
 +
 
 +
Алгоритм допустил около 50% ошибок классификация, что неудивительно, т.к. входные данные были принципиально линейно неразделимы.
== Исходный код ==
== Исходный код ==
-
Скачать листинги алгоритмов можно здесь [http://mlalgorithms.svn.sourceforge.net/viewvc/mlalgorithms/OneLayerPerceptron/| Func.m OneLayerPerc.m PercTest.m GetNormClass.m]
+
Скачать листинги алгоритмов можно здесь [http://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Panov2009OneLayerPerceptron/].
== Смотри также ==
== Смотри также ==
-
TODO
+
* [[Линейный классификатор]]
 +
* [[Персептрон]]
 +
* [[Логистическая регрессия]]
-
== Литература ==
+
== Литература ==
 +
* Nabney Ian, NetLab Algotithms for Pattern Recognition. Springer. 2001.
* К. В. Воронцов, Лекции по линейным алгоритмам классификации
* К. В. Воронцов, Лекции по линейным алгоритмам классификации
* Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006.
* Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006.
-
{{Задание|Максим Панов|В.В. Стрижов|28 мая 2009}}
+
 
-
[[Категория:Учебные материалы]]
+
{{ЗаданиеВыполнено|Максим Панов|В.В.Стрижов|28 мая 2009|Maxx|Strijov}}
 +
[[Категория:Линейные классификаторы]]
 +
[[Категория:Нейронные сети]]
 +
[[Категория:Практика и вычислительные эксперименты]]

Текущая версия

Содержание

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

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

Пусть 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.

Iris.jpg

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

%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 в учебном процессе.

Личные инструменты