Задача XOR

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

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

Задача XOR

• • Задача XOR** (от англ. exclusive OR — исключающее «ИЛИ») — это классическая задача в области машинного обучения и искусственных нейронных сетей, которая заключается в построении модели, способной выучить функцию исключающего ИЛИ (XOR). Эта функция принимает два бинарных входа и возвращает 1, если входы различаются, и 0, если они совпадают .

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

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

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

Таблица истинности для функции XOR

Вход	Вход <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> .

См. также

• Искусственный нейрон
• Функция активации
• Логистическая регрессия
• Метод опорных векторов
• Аппроксимация функций

Примечания