Представляемость персептрона. Проблема XOR — исключающего ИЛИ

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

Для иллюстрации проблемы представляемости допустим, что есть множество карт, помеченных цифрами от 0 до 9. Допустим также, что существует гипотетическая машина, способная отличать карты с нечетным номером от карт с четным номером и зажигающей индикатор на своей панели при предъявлении карты с нечетным номером. Представима ли такая машина персептроном? То есть, может ли быть сконструирован персептрон и настроены его веса (неважно каким образом) так, чтобы он обладал такой же разделяющей способностью? Если это так, то говорят, что персептрон способен представлять желаемую машину. Возможности представления однослойными персептронами весьма ограниченны. Имеется много простых машин, которые не могут быть представлены персептроном независимо от того, как настраиваются его веса. Для примера рассмотрим проблему XORисключающего ИЛИ.

Проблема функции XOR – исключающего ИЛИ

Один из самых пессимистических результатов Минского показывает, что однослойный персептрон не может воспроизвести такую простую функцию, как XOR. Это функция от двух аргументов, каждый из которых может быть нулем или единицей. Она принимает значение 1, когда один из аргументов равен единице, но не оба, иначе 0. Проблему можно проиллюстрировать с помощью однослойной однонейронной системы с двумя входами, показанной на рисунке ниже.

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

Обозначим один вход через x_{1}, а другой через x_{2}, тогда все их возможные комбинации будут состоять из четырех точек на плоскости, как показано на рисунке.

Все четыре выхода функции XOR на плоскости

Таблица ниже показывает требуемую связь между входами и выходом, где входные комбинации, которые должны давать нулевой выход, помечены A_{0} и A_{1}, единичный выход – B_{0} и B_{1}.

Точки Значение x_{1} Значение x_{2} Требуемый выход
A_{0} 0 0 0
B_{0} 1 0 1
B_{1} 0 1 1
A_{1} 1 1 0

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

x_{1}w_{1}~+~x_{2}w_{2}~=~Y

Никакая комбинация значений двух весов не может дать соотношения между входом и выходом, заданного в таблице выше. Чтобы понять это ограничение, зафиксируем Y на величине порога 0.5. Сеть в этом случае описывается следующим уравнением:

x_{1}w_{1}~+~x_{2}w_{2}~=~0.5

Это уравнение линейно по x_{1} и x_{2}, т. е. все значения по x_{1} и x_{2}, удовлетворяющие этому уравнению, будут лежать на некоторой прямой в плоскости. Любые входные значения для x_{1} и x_{2} на этой линии будут давать пороговое значение 0.5. Прямая разделяет плоскость на две полуплоскости. Входные значения в одной полуплоскости обеспечат значения y больше порога, следовательно, OUT~=~1. Входные значения во второй полуплоскости обеспечат значения Y меньше порогового значения, делая OUT~=~0. Изменения значения w_{1}, w_{2} и порога будут менять наклон и положение прямой. Для того, чтобы сеть реализовала функцию XOR – исключающего ИЛИ, заданную таблицой выше, нужно расположить прямую так, чтобы точки A были с одной стороны прямой, а точки B – с другой. Попытавшись нарисовать такую прямую на рисунке ниже, убеждаемся, что это невозможно. Это означает, что какие бы значения ни приписывались весам и порогу, сеть неспособна воспроизвести соотношение между входом и выходом, требуемое для представления функции XOR – исключающего ИЛИ.

Проблема XOR -исключающего ИЛИ

Это интересно

Смотрите также