воскресенье, 28 апреля 2013 г.

Применение нейросетей для решения классических задач линейного и нелинейного разделения элементов множества на классы

Структура статьи:

1. Общие сведения о нейросистемах.

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

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

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

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

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

Основной областью исследований по искусственному интеллекту в 60-80-хх годах были экспертные системы. Такие системы основывались на высокоуровневом моделировании процесса мышления (в частности, на представлении, что процесс нашего мышления построен на манипуляциях с символами). Скоро стало ясно, что подобные системы, хотя и могут принести пользу в некоторых областях, не ухватывают некоторые ключевые аспекты человеческого интеллекта. Согласно одной из точек зрения, причина этого состоит в том, что они не в состоянии воспроизвести структуру мозга. Чтобы создать искусственных интеллект, необходимо построить систему с похожей архитектурой.

Мозг состоит из очень большого числа нейронов, соединенных многочисленными связями: в среднем несколько тысяч связей на один нейрон, однако это число может сильно колебаться.

Нейроны – это специальные клетки (см. рис. 1), способные распространять электрохимические сигналы. Нейрон имеет разветвленную структуру ввода информации (дендриты), ядро и разветвляющийся выход (аксон). Аксоны клетки соединяются с дендритами других клеток с помощью синапсов. При активации нейрон посылает электрохимический сигнал по своему аксону. Через синапсы этот сигнал достигает других нейронов, которые могут в свою очередь активироваться. Нейрон активируется тогда, когда суммарный уровень сигналов, пришедших в его ядро из дендритов, превысит определенный уровень (порог активации).


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

Один из авторитетных исследователей нейросистем, Дональд Хебб, высказал постулат, что обучение заключается в первую очередь в изменениях «силы» синаптических связей. Например, в классическом опыте Павлова, каждый раз непосредственно перед кормлением собаки звонил колокольчик, и собака быстро научилась связывать звонок колокольчика с пищей. Синаптические связи между участками коры головного мозга, ответственными за слух, и слюнными железами усилились, и при возбуждении коры звуком колокольчика у собаки начиналось слюноотделение.

Таким образом, будучи построен из очень большого числа простых элементов (каждый из которых берет взвешенную сумму входных сигналов и в случае, если суммарный вход превышает определенный уровень, передает сигнал дальше), мозг способен решать чрезвычайно сложные задачи.

2. Математический нейрон – персептрон.


Простой персептрон – это искусственный нейрон Маккалоха-Питтса (см. рис. 2.). В его структуре присутствуют следующие элементы.

вектор входных коэффициентов нейрона. 
Эти коэффициенты обозначают также
На практике обычно полагают

вектор весовых коэффициентов входов нейрона. 
Эти коэффициенты обозначают также
называют пороговым значением нейрона.

– сумматор нейрона.

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

Если считать коэффициенты векторов одномерными матрицами, то (1) можно переписать в матричной форме:
используя транспонированную матрицу

нелинейная функция активации персептрона. Она является ступенчатой, т.е. функция активации f(u) преобразует выходной сигнал сумматора в выходной сигнал нейрона y.

Также на практике часто используют функцию активации, записанную в виде:


2.1. Обучение персептрона на отдельных примерах с учителем.


Обучение персептрона состоит в таком подборе весов

чтобы для любого входного вектора


выходное значение персептрона

совпадало с требуемым значением


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

Алгоритм обучения персептрона на отдельных примерах состоит в прохождении следующих шагов.

  1. Задается начальный вектор весов

    случайно, либо используя некоторую специальную методику.
  2. На вход нейрона подается вектор

    из обучающей выборки для которого известно правильное выходное значение d нейрона и по формуле (2) рассчитывается значение выходного сигнала y. По результатам сравнения y и d уточняются значения весов.
  3. Если

    то

    не изменяются.
  4. Если

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

    где α коэффициент обучения, t – индекс текущего цикла (эпоха обучения).
  5. Если

    то значения весов уточняются по формуле:

Условия шагов 3, 4 и 5 алгоритма обучения с учителем можно объединить и выразить формулой:

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


3. Задача линейного разделения элементов множества на два класса.

С персептроном связана классическая задача линейного (однозначного) разделения элементов множества на два класса.

Задача линейного разделения элементов множества на два класса состоит в построении линейного решающего правила, то есть нахождении такого вектора весов

где

– пороговое значение, что при значении нелинейной функции активации персептрона

вектор x относится к первому классу, а при

– ко второму.

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

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

3.1. Геометрическая интерпретация.


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

Уравнение разделяющей гиперплоскости задаётся в виде:
или расписав скалярное произведение векторов через их координаты:

В n-мерном векторном пространстве (пространстве входных сигналов персептрона) вектор нормали
перпендикулярен разделяющей гиперплоскости (4).

Длину проекции вектора x на вектор нормали вычислим как:
или, через координаты:

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

Схематично задача разделения элементов множества на два класса в случае двумерного пространства (n = 2) представлена на рис. 3.


Рассмотрим пример. В двухмерном пространстве входных сигналов уравнение гиперплоскости задаётся уравнением прямой:

Пусть
Тогда получаем уравнение прямой:
которая представлена на рис. 4 линией, пересекающей оси координат в точках:

– нормаль к прямой.


Пусть заданы два радиус-вектора:
Требуется отнести их к одному из классов, в зависимости от положения точек относительно разделяющей прямой.

Длины проекций векторов a и b на нормаль вычислим по формуле (5):



– вектор, относящийся к первому классу, так как на выходе персептрона по формуле (6) получаем значение

поскольку


– вектор, относящийся ко второму классу, так как на выходе персептрона получаем значение

поскольку

3.2. Реализация булевых функций AND и OR при помощи персептрона.


Легко убедиться, что однослойный персептрон способен реализовать булевы функции AND и OR. Для упрощения примеров, приведём далее только данные для реализации персептронов, схематичные изображения гиперплоскостей (в данном случае – прямых) и персептронов.

Данные для реализации функции AND (изображение гиперплоскости см. на рис. 5, схему персептрона см. на рис. 6):




Данные для реализации функции OR (изображение гиперплоскости см. на рис. 7, схему персептрона см. на рис. 8):




4. Задача нелинейного разделения элементов множества на два класса.

Как было показано выше, однослойный персептрон способен решать задачи линейного разделения двух классов, реализовать булевы функции AND и OR. Однако он уже не способен справиться с задачей воспроизведения функции XOR (исключающее ИЛИ) и выполнять более общие классификации, например, отделять точки выпуклых и невыпуклых областей плоскости. Эти ограничения можно снять, добавив дополнительные слои персептронов. 

Рассмотрим далее примеры реализации функции XOR и решение задачи классификации точек выпуклой (треугольной) области на плоскости.

4.1. Реализация булевой функции XOR при помощи сети персептронов.


Функцию XOR возможно реализовать при помощи двухслойной нейронной сети. Первый слой сети состоит из двух персептронов, реализующих функции OR и NOT(AND) – ИЛИ и отрицание функции И. Во втором слое находится персептрон, реализующий функцию AND от двух выходных сигналов первого слоя. 

Данные для реализации функции XOR (изображения гиперплоскостей см. на рис. 9, схему нейронной сети персептронов см. на рис. 10):





4.2. Выделение выпуклых областей при помощи сети персептронов.


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

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

Рассмотрим пример. Пусть в двухмерном пространстве входных сигналов необходимо выделить область треугольной формы (см. рис. 11). Данные по гиперплоскостям (фактически являющиеся обычными прямыми на плоскости) можно представить следующим образом:



Выделение области треугольной формы, может быть реализовано двухслойной нейросетью (см. рис. 12), в первом слое которой три персептрона реализуют разбиение плоскости на две полуплоскости заданными разделяющими прямыми, а во втором слое один персептрон реализует булеву функцию AND от трех входов (выходов предыдущего слоя).






По материалам лабораторных работ
для дисциплины  «Нейрокомпьютерные системы», 2008г.
кафедра СИБ, КГТУ им. А.Н. Туполева (КАИ),
(с) Гильмуллин Т.М., 2013.