Задача XOR

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
== Задача XOR ==
== Задача XOR ==
-
'''Задача XOR''' (исключающее ИЛИ) — одна из классических задач в области [[Машинное обучение|машинного обучения]] и [[Искусственные нейронные сети|нейронных сетей]], которая заключается в обучении модели воспроизводить логическую функцию [[Исключающее «или»|исключающего ИЛИ]] (XOR). Эта функция принимает два [[Бит|бинарных]] входа и возвращает истину (1), если входы различаются, и ложь (0), если они совпадают . Несмотря на свою кажущуюся простоту, задача XOR сыграла ключевую роль в истории развития искусственного интеллекта, поскольку на её примере была наглядно продемонстрирована фундаментальная вычислительная ограниченность [[Перцептрон|однослойного перцептрона]] .
+
**Задача XOR** (от англ. ''exclusive OR'' — исключающее «ИЛИ») — это классическая задача в области [[машинное обучение|машинного обучения]] и [[искусственные нейронные сети|искусственных нейронных сетей]], которая заключается в построении модели, способной выучить функцию [[Исключающее «ИЛИ»|исключающего ИЛИ]] (XOR). Эта функция принимает два бинарных входа и возвращает 1, если входы различаются, и 0, если они совпадают .
-
=== Определение и истинностная таблица ===
+
Несмотря на кажущуюся простоту, задача XOR стала важнейшим рубежом в истории искусственного интеллекта, поскольку она наглядно демонстрирует фундаментальные ограничения линейных моделей классификации. Она является простейшей булевой функцией, которая не является [[линейная разделимость|линейно разделимой]], и поэтому не может быть решена с помощью однослойного [[персептрон|персептрона]] . Эта проблема, подробно описанная в книге Марвина Минского и Сеймура Пейперта «Персептроны» (1969), сыграла ключевую роль в наступлении «[[зима искусственного интеллекта|зимы искусственного интеллекта]]» — периода значительного спада интереса и финансирования исследований нейронных сетей, длившегося с конца 1960-х до середины 1980-х годов .
-
Функция XOR является одной из шестнадцати возможных [[Булева функция|булевых функций]] от двух переменных . Её истинностная таблица выглядит следующим образом :
+
=== Определение и математическая постановка ===
-
{| class="wikitable"
+
Функция XOR определяется следующей таблицей истинности :
 +
 
 +
{| class="wikitable" style="margin:auto"
 +
|+ Таблица истинности для функции XOR
|-
|-
-
! x1 !! x2 !! x1 ⊕ x2
+
! Вход <math>x_1</math> !! Вход <math>x_2</math> !! Выход <math>x_1 \oplus x_2</math>
|-
|-
| 0 || 0 || 0
| 0 || 0 || 0
Строка 20: Строка 23:
|}
|}
-
В [[Алгебраическая нормальная форма|алгебраической нормальной форме]] XOR может быть выражена через базовые операции И, ИЛИ и НЕ. Например, <code>XOR(x1, x2) = (x1 AND NOT x2) OR (NOT x1 AND x2)</code> . Также существуют эквивалентные представления с использованием арифметических операций, такие как <math>x_1 \oplus x_2 = x_1 + x_2 - 2x_1x_2</math> .
+
В геометрической интерпретации четыре точки данных (<math>(0,0)</math>, <math>(0,1)</math>, <math>(1,0)</math>, <math>(1,1)</math>) необходимо разделить на два класса. Класс «0» представлен точками <math>(0,0)</math> и <math>(1,1)</math>, а класс «1» — точками <math>(0,1)</math> и <math>(1,0)</math>. Эти два класса не могут быть разделены одной прямой линией (гиперплоскостью), что и является определением линейной неразделимости .
-
=== Нелинейная разделимость ===
+
Алгебраически XOR может быть выражен несколькими способами :
 +
* <math>x_1 \oplus x_2 = x_1 + x_2 - 2x_1x_2</math>
 +
* <math>x_1 \oplus x_2 = |x_1 - x_2|</math>
-
Главная сложность задачи XOR заключается в том, что множество точек <math>\{(0,0), (1,1)\}</math> (класс 0) и <math>\{(0,1), (1,0)\}</math> (класс 1) являются [[Линейная разделимость|линейно неразделимыми]] на двумерной плоскости . Это означает, что не существует прямой линии, которая могла бы разделить эти две группы точек. В то же время, функции И (AND) и ИЛИ (OR) являются линейно разделимыми, и их может выучить однослойный перцептрон .
+
=== Историческое значение ===
-
==== Доказательство невозможности для однослойного перцептрона ====
+
Задача XOR стала центральной в критике однослойного персептрона, предложенного [[Фрэнк Розенблатт|Фрэнком Розенблаттом]] в конце 1950-х годов. В своей книге «Персептроны» Марвин Минский и Сеймур Пейперт строго математически доказали, что однослойный персептрон неспособен выучить функцию XOR, поскольку ее классы нелинейно разделимы . Хотя Минский и Пейперт знали, что добавление скрытого слоя решает проблему , на тот момент не существовало эффективного алгоритма обучения для многослойных сетей, что привело к пессимистическим выводам о потенциале нейросетевого подхода в целом. Это событие, наряду с другими факторами, вызвало «зиму искусственного интеллекта», когда финансирование и интерес к нейронным сетям резко упали .
-
Однослойный перцептрон вычисляет выход как <math>y = f(w_1 x_1 + w_2 x_2 + b)</math>, где <math>w_1, w_2</math> — веса, <math>b</math> — [[Смещение нейрона|смещение]], а <math>f</math> — [[Функция активации|пороговая функция активации]] . Чтобы решить задачу XOR, необходимо найти такие <math>w_1, w_2</math> и <math>b</math>, которые удовлетворяют следующей системе неравенств, вытекающих из истинностной таблицы :
+
=== Решение задачи с помощью нейронных сетей ===
-
# Для <math>(0,0) \rightarrow 0</math>: <math>b < 0</math>
+
Задача XOR решается использованием [[многослойный персептрон|многослойного персептрона]] (MLP), который вводит один или несколько скрытых слоев с нелинейными [[функция активации|функциями активации]] . Эти скрытые слои позволяют сети трансформировать исходное пространство признаков таким образом, что данные становятся линейно разделимыми на выходном слое.
-
# Для <math>(0,1) \rightarrow 1</math>: <math>w_2 + b \ge 0</math>
+
-
# Для <math>(1,0) \rightarrow 1</math>: <math>w_1 + b \ge 0</math>
+
-
# Для <math>(1,1) \rightarrow 0</math>: <math>w_1 + w_2 + b < 0</math>
+
-
Из неравенств (2) и (3) следует, что <math>w_1 + w_2 + 2b \ge 0</math>. Если сложить это выражение с неравенством (1) (<math>b < 0</math>), то нельзя прийти к противоречию напрямую. Однако, более строгий анализ показывает, что из (2) и (3) следует <math>w_1 + w_2 \ge -2b</math>. Подставляя это в (4), получаем <math>(-2b) + b < 0</math>, то есть <math>-b < 0</math>, или <math>b > 0</math>. Это противоречит неравенству (1), которое требует <math>b < 0</math> . Таким образом, доказано, что не существует набора весов для однослойного перцептрона, который бы решал задачу XOR.
+
==== Архитектура сети ====
 +
Простейшая нейронная сеть, решающая задачу XOR, имеет следующую архитектуру :
 +
* '''Входной слой:''' 2 нейрона (для входов <math>x_1</math> и <math>x_2</math>).
 +
* '''Скрытый слой:''' как минимум 2 нейрона с нелинейной функцией активации, такой как [[ReLU]] или [[сигмоида]].
 +
* '''Выходной слой:''' 1 нейрон с сигмоидальной функцией активации для бинарной классификации.
-
=== Историческое значение и «Зима ИИ» ===
+
Многослойный персептрон решает XOR, аппроксимируя его с помощью комбинации более простых линейно разделимых функций, таких как [[Конъюнкция|AND]], [[Дизъюнкция|OR]] и [[Штрих Шеффера|NAND]] . Например, один из подходов заключается в вычислении скрытым нейроном функции <math>OR</math>, а затем использовании выходного нейрона для комбинации <math>OR</math> и <math>NAND</math> .
-
Невозможность решения задачи XOR однослойным перцептроном была строго доказана [[Минский, Марвин|Марвином Минским]] и [[Пейперт, Сеймур|Сеймуром Пейпертом]] в их знаковой книге «Перцептроны» (1969 год) . Этот результат стал мощным аргументом против исследований в области нейронных сетей. Критика Минского и Пейперта, вкупе с завышенными ожиданиями от возможностей перцептронов, привела к так называемой «[[Зима искусственного интеллекта|Зиме ИИ]]» — периоду с конца 1960-х по середину 1980-х годов, когда финансирование и интерес к данной области исследований резко упали .
+
==== Алгоритм обучения ====
 +
Обучение многослойного персептрона для решения задачи XOR стало возможным благодаря алгоритму [[обратное распространение ошибки|обратного распространения ошибки]] (backpropagation), который был популяризирован в 1986 году . Этот алгоритм позволяет эффективно вычислять градиент функции потерь относительно всех весов сети, включая веса скрытых слоев. С появлением обратного распространения ошибки и открытием [[теорема о полноте|теоремы о полноте]] интерес к нейронным сетям возродился, что привело к современной эпохе [[глубокое обучение|глубокого обучения]] .
-
Важно отметить, что Минский и Пейперт критиковали именно ''однослойные'' перцептроны. Они осознавали, что добавление скрытых слоёв потенциально может решить проблему, однако в то время не существовало эффективного алгоритма обучения для [[Многослойный перцептрон|многослойных сетей]] . Этот нюанс был упущен широкой научной общественностью, что привело к неоправданно пессимистичным выводам о нейросетевом подходе в целом .
+
=== Современные взгляды и альтернативные решения ===
-
=== Решение задачи с помощью многослойных сетей ===
+
Хотя традиционно для решения задачи XOR требуется скрытый слой, современные исследования показывают, что использование некоторых продвинутых функций активации, таких как [[PReLU|Parametric ReLU (PReLU)]] или [[GCU|Growing Cosine Unit (GCU)]], позволяет решить ее даже в однослойной сети без скрытых слоев . Это становится возможным благодаря способности этих функций создавать нелинейные и немонотонные разделяющие поверхности. Данное открытие имеет значение для проектирования более эффективных архитектур нейронных сетей.
-
Проблема XOR решается добавлением как минимум одного скрытого слоя нейронов с нелинейными функциями активации . В такой архитектуре скрытые нейроны могут выучить промежуточные представления, например, функции И (AND) и И-НЕ (NAND), которые затем комбинируются выходным нейроном для получения функции XOR . Математически это описывается как композиция функций <math>XOR(x_1, x_2) = AND(OR(x_1, x_2), NAND(x_1, x_2))</math> .
+
Кроме того, существуют подходы к решению задачи XOR, не связанные с классическими нейронными сетями, например, с использованием комитетных конструкций или методов математического программирования . Задача XOR также служит простейшим бенчмарком для проверки новых архитектур и алгоритмов обучения, включая [[квантовое машинное обучение|вариационные квантовые классификаторы]] , и обобщается на многоклассовые варианты, такие как задача <math>XOR_p</math> на основе вычитания по модулю <math>p</math> .
-
Стандартная архитектура для решения XOR — [[Многослойный перцептрон]] с двумя входами, скрытым слоем из двух нейронов и одним выходом (2-2-1) . Эффективный алгоритм обучения таких сетей, [[Метод обратного распространения ошибки|обратное распространение ошибки]], был популяризирован в 1986 году, что ознаменовало возрождение интереса к нейронным сетям .
+
== См. также ==
 +
* [[Искусственный нейрон]]
 +
* [[Функция активации]]
 +
* [[Логистическая регрессия]]
 +
* [[Метод опорных векторов]]
 +
* [[Аппроксимация функций]]
-
==== Альтернативные решения ====
+
== Примечания ==
-
 
+
<references />
-
Исследования показывают, что задачу XOR можно решить и в однослойной архитектуре, если использовать специальные нелинейные функции активации или расширить пространство признаков :
+
-
 
+
-
* '''Функции активации:''' Использование нестандартных активаций, таких как [[PReLU|Parametric ReLU (PReLU)]] с отрицательным параметром или [[Оскуллирующая функция активации|оскуллирующая]] Growing Cosine Unit (GCU), позволяет одному нейрону вычислять XOR .
+
-
* '''Расширение признакового пространства:''' Добавление новых признаков, например, произведения входов <math>x_1 \cdot x_2</math>, делает задачу линейно разделимой в новом, более высокомерном пространстве .
+
-
 
+
-
Обобщением задачи XOR является задача <math>XOR_p</math> для <math>p</math> классов, которая заключается в классификации пар целых чисел <math>(a,b) \in \mathbb{Z}_p \times \mathbb{Z}_p</math> по значению их разности <math>a-b \bmod p</math> .
+
-
 
+
-
=== См. также ===
+
-
 
+
-
* [[Перцептрон]]
+
-
* [[Многослойный перцептрон]]
+
-
* [[Метод обратного распространения ошибки]]
+
-
* [[Функция активации]]
+
-
* [[Линейная разделимость]]
+
-
* [[Зима искусственного интеллекта]]
+
-
* [[Проблема чётности]]
+

Версия 16:09, 11 июля 2026

Содержание

Задача XOR

Несмотря на кажущуюся простоту, задача XOR стала важнейшим рубежом в истории искусственного интеллекта, поскольку она наглядно демонстрирует фундаментальные ограничения линейных моделей классификации. Она является простейшей булевой функцией, которая не является линейно разделимой, и поэтому не может быть решена с помощью однослойного персептрона . Эта проблема, подробно описанная в книге Марвина Минского и Сеймура Пейперта «Персептроны» (1969), сыграла ключевую роль в наступлении «зимы искусственного интеллекта» — периода значительного спада интереса и финансирования исследований нейронных сетей, длившегося с конца 1960-х до середины 1980-х годов .

Определение и математическая постановка

Функция XOR определяется следующей таблицей истинности :

Таблица истинности для функции XOR
Вход <math>x_1</math> Вход <math>x_2</math> Выход <math>x_1 \oplus x_2</math>
0 0 0
0 1 1
1 0 1
1 1 0

В геометрической интерпретации четыре точки данных (<math>(0,0)</math>, <math>(0,1)</math>, <math>(1,0)</math>, <math>(1,1)</math>) необходимо разделить на два класса. Класс «0» представлен точками <math>(0,0)</math> и <math>(1,1)</math>, а класс «1» — точками <math>(0,1)</math> и <math>(1,0)</math>. Эти два класса не могут быть разделены одной прямой линией (гиперплоскостью), что и является определением линейной неразделимости .

Алгебраически XOR может быть выражен несколькими способами :

  • <math>x_1 \oplus x_2 = x_1 + x_2 - 2x_1x_2</math>
  • <math>x_1 \oplus x_2 = |x_1 - x_2|</math>

Историческое значение

Задача XOR стала центральной в критике однослойного персептрона, предложенного Фрэнком Розенблаттом в конце 1950-х годов. В своей книге «Персептроны» Марвин Минский и Сеймур Пейперт строго математически доказали, что однослойный персептрон неспособен выучить функцию XOR, поскольку ее классы нелинейно разделимы . Хотя Минский и Пейперт знали, что добавление скрытого слоя решает проблему , на тот момент не существовало эффективного алгоритма обучения для многослойных сетей, что привело к пессимистическим выводам о потенциале нейросетевого подхода в целом. Это событие, наряду с другими факторами, вызвало «зиму искусственного интеллекта», когда финансирование и интерес к нейронным сетям резко упали .

Решение задачи с помощью нейронных сетей

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

Архитектура сети

Простейшая нейронная сеть, решающая задачу XOR, имеет следующую архитектуру :

  • Входной слой: 2 нейрона (для входов <math>x_1</math> и <math>x_2</math>).
  • Скрытый слой: как минимум 2 нейрона с нелинейной функцией активации, такой как ReLU или сигмоида.
  • Выходной слой: 1 нейрон с сигмоидальной функцией активации для бинарной классификации.

Многослойный персептрон решает XOR, аппроксимируя его с помощью комбинации более простых линейно разделимых функций, таких как AND, OR и NAND . Например, один из подходов заключается в вычислении скрытым нейроном функции <math>OR</math>, а затем использовании выходного нейрона для комбинации <math>OR</math> и <math>NAND</math> .

Алгоритм обучения

Обучение многослойного персептрона для решения задачи XOR стало возможным благодаря алгоритму обратного распространения ошибки (backpropagation), который был популяризирован в 1986 году . Этот алгоритм позволяет эффективно вычислять градиент функции потерь относительно всех весов сети, включая веса скрытых слоев. С появлением обратного распространения ошибки и открытием теоремы о полноте интерес к нейронным сетям возродился, что привело к современной эпохе глубокого обучения .

Современные взгляды и альтернативные решения

Хотя традиционно для решения задачи XOR требуется скрытый слой, современные исследования показывают, что использование некоторых продвинутых функций активации, таких как Parametric ReLU (PReLU) или Growing Cosine Unit (GCU), позволяет решить ее даже в однослойной сети без скрытых слоев . Это становится возможным благодаря способности этих функций создавать нелинейные и немонотонные разделяющие поверхности. Данное открытие имеет значение для проектирования более эффективных архитектур нейронных сетей.

Кроме того, существуют подходы к решению задачи XOR, не связанные с классическими нейронными сетями, например, с использованием комитетных конструкций или методов математического программирования . Задача XOR также служит простейшим бенчмарком для проверки новых архитектур и алгоритмов обучения, включая вариационные квантовые классификаторы , и обобщается на многоклассовые варианты, такие как задача <math>XOR_p</math> на основе вычитания по модулю <math>p</math> .

См. также

Примечания

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_XOR»
Личные инструменты