Проблема функции исключающее или

Один из самых пессимистических результатов Минского показывает, что однослойный персептрон не может воспроизвести такую простую функцию, как ИСКЛЮЧАЮЩЕЕ ИЛИ. Это - функция от двух аргументов, каждый из которых может быть нулем или единицей. Она принимает значение единицы, когда один из аргументов равен единице (но не оба). Проблему можно проиллюстрировать с помощью однослойной однонейронной системы с двумя входами, показанной на рис. 9. Обозначим один вход через х, а другой через у, тогда все их возможные комбинации будут состоять из четырех точек на плоскости х - у, как показано на рис. 10. Например, точка х=0 и у=0 обозначена на рисунке как точка Ао. Табл. 3 показывает требуемую связь между входами и выходом, где входные комбинации, которые должны давать нулевой выход, помечены Ао и А₁, единичный выход - Во и В₁.

В сети на рис. 9 функция F является обычным порогом, так что OUT принимает значение ноль, когда NET меньше 0,5, и единица в случае, когда NET больше или равно 0,5. Нейрон выполняет следующее вычисление:

Рис.9. Однонейронная система.

NET = xw₁+yw₂. (7)

Никакая комбинация значений двух весов не может дать соотношения между входом и выходом, задаваемого табл. 3. Чтобы понять это ограничение, зафиксируем NET на величине порога 0,5. Сеть в этом случае описывается уравнением (7). Это уравнение линейно по х и у, т.е. все значения по х и у, удовлетворяющие этому уравнению, будут лежать на некоторой прямой в плоскости х-у.

хw1 + yw2 = 0,5. (8)

Таблица 3. Таблица истинности для функции ИСКЛЮЧАЮЩЕЕ ИЛИ

Точки	Значения х	Значения у	Требуемый выход
Ao	0	0
Bo		0
B1
A1

Любые входные значения для х и у на этой линии будут давать пороговое значение 0,5 для NET. Входные значения с одной стороны прямой обеспечат значения NET больше порога, следовательно, OUT=1. Входные значения по другую сторону прямой обеспечат значения NET меньше порогового значения, делая OUT равным 0. Изменения значений w₁, w₂ и порога будут менять наклон и положе­ние прямой. Для того чтобы сеть реализовала функцию ИСКЛЮЧАЮЩЕЕ ИЛИ, заданную табл. 3, нужно расположить прямую так, чтобы точки А были с одной стороны прямой, а точки В - с другой. Попытавшись нарисовать такую прямую на рис. 10, убеждаемся, что это невозможно. Это означает, что какие бы значения ни приписывались весам и порогу, сеть неспособна воспроизвести соотношение между входом и выходом, требуемое для представления функции ИСКЛЮЧАЮЩЕЕ ИЛИ.

Рис. 10. Проблема ИСКЛЮЧАЮЩЕЕ ИЛИ.

Линейная разделимость

Как мы видели, невозможно нарисовать прямую линию, разделяющую плоскость х-у так, чтобы реализовывалась функция ИСКЛЮЧАЮЩЕЕ ИЛИ. К сожалению, этот пример не единственный. Имеется обширный класс функций, не реализуемых однослойной сетью. Об этих функциях говорят, что они являются линейно неразделимыми, и они накладывают определенные ограничения на возможности однослойных сетей.

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

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

Нейрон с п двоичными входами может иметь 2ⁿ различных входных образов, состоящих из нулей и единиц. Так как каждый входной образ может соответствовать двум различным бинарным выходам (единица и ноль), то всего имеется 2²ⁿ функций от п переменных.

Таблица 4. Линейно разделимые функции

n	2^2n	Число линейно разделимых функций
	4,3х10^9
	1,8х10^19	15 028 134

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

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

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

Первое систематическое изучение искусственных нейронных сетей было предпринято Маккалокком и Питтсом в 1943 г. Простая нейронная модель, показанная на рис. 7, использовалась в большей части их работы. Элемент ∑ умножает каждый вход х на вес w и суммирует взвешенные входы. Если эта сумма больше заданного порогового значения, выход равен единице, в противном случае - нулю. Эти системы (и множество им подобных) получили название персептронов. Они состоят из одного слоя искусственных нейронов, соединенных с помощью весовых коэффициентов с множеством входов (см. рис. 8), хотя в принципе описываются и более сложные системы.

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

Рис. 11. Выпуклые, ограниченные и неограниченные области.

Чтобы уточнить требование выпуклости, рассмотрим простую двухслойную сеть с двумя входами, подведенными к двум нейронам первого слоя, соединенными с единственным нейроном в слое 2 (рис. 12). Пусть порог выходного нейрона равен 0,75, а оба его веса равны 0,5. В этом случае для того, чтобы порог был превышен, и на выходе появилась единица, требуется, чтобы оба нейрона первого уровня на выходе имели единицу. Таким образом, выходной нейрон реализует логическую функцию И. На рис. 12 каждый нейрон слоя 1 разбивает плоскость х-у на две полуплоскости, один обеспечивает единичный выход для входов ниже верхней линии, другой - для входов выше нижней линии. На рис. 12 показан результат такого двойного разбиения, где выходной сигнал нейрона второго слоя равен единице только внутри V-образной области Аналогично во втором слое может быть использовано три нейрона с дальнейшим разбиением плоскости и создание» области треугольной формы. Включением достаточной числа нейронов во входной слой может быть образован выпуклый многоугольник любой желаемой формы. Так как они образованы с помощью операции И над областями, задаваемыми линиями, то все такие многогранники выпуклы, следовательно, только выпуклые области и возникают. Точки, не составляющие выпуклой области, не могут быть отделены от других точек плоскости двухслойной сетью.

Нейрон второго слоя не ограничен функцией И. Он может реализовывать многие другие функции при подходящем выборе весов и порога. Например, можно сделать так, чтобы единичный выход любого из нейронов первого слоя приводил к появлению единицы на выходе нейрона второго слоя, реализовав тем самым логическое ИЛИ. Имеется 16 двоичных функций от двух переменных. Если выбирать подходящим образом веса и порог, то можно воспроизвести 14 из них (все, кроме ИСКЛЮЧАЮЩЕЕ ИЛИ и ИСКЛЮЧАЮЩЕЕ НЕТ).

Рис.12. Выпуклая область решений, задаваемая двухслойной сетью.

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

Дата добавления: 2014-01-11