Задача XOR
Материал из MachineLearning.
Содержание |
Задача XOR
Задача XOR (исключающее ИЛИ) — одна из классических задач в области машинного обучения и нейронных сетей, которая заключается в обучении модели воспроизводить логическую функцию исключающего ИЛИ (XOR). Эта функция принимает два бинарных входа и возвращает истину (1), если входы различаются, и ложь (0), если они совпадают . Несмотря на свою кажущуюся простоту, задача XOR сыграла ключевую роль в истории развития искусственного интеллекта, поскольку на её примере была наглядно продемонстрирована фундаментальная вычислительная ограниченность однослойного перцептрона .
Определение и истинностная таблица
Функция XOR является одной из шестнадцати возможных булевых функций от двух переменных . Её истинностная таблица выглядит следующим образом :
| x1 | x2 | x1 ⊕ x2 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
В алгебраической нормальной форме XOR может быть выражена через базовые операции И, ИЛИ и НЕ. Например, XOR(x1, x2) = (x1 AND NOT x2) OR (NOT x1 AND x2) . Также существуют эквивалентные представления с использованием арифметических операций, такие как <math>x_1 \oplus x_2 = x_1 + x_2 - 2x_1x_2</math> .
Нелинейная разделимость
Главная сложность задачи XOR заключается в том, что множество точек <math>\{(0,0), (1,1)\}</math> (класс 0) и <math>\{(0,1), (1,0)\}</math> (класс 1) являются линейно неразделимыми на двумерной плоскости . Это означает, что не существует прямой линии, которая могла бы разделить эти две группы точек. В то же время, функции И (AND) и ИЛИ (OR) являются линейно разделимыми, и их может выучить однослойный перцептрон .
Доказательство невозможности для однослойного перцептрона
Однослойный перцептрон вычисляет выход как <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>
- Для <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 однослойным перцептроном была строго доказана Марвином Минским и Сеймуром Пейпертом в их знаковой книге «Перцептроны» (1969 год) . Этот результат стал мощным аргументом против исследований в области нейронных сетей. Критика Минского и Пейперта, вкупе с завышенными ожиданиями от возможностей перцептронов, привела к так называемой «Зиме ИИ» — периоду с конца 1960-х по середину 1980-х годов, когда финансирование и интерес к данной области исследований резко упали .
Важно отметить, что Минский и Пейперт критиковали именно однослойные перцептроны. Они осознавали, что добавление скрытых слоёв потенциально может решить проблему, однако в то время не существовало эффективного алгоритма обучения для многослойных сетей . Этот нюанс был упущен широкой научной общественностью, что привело к неоправданно пессимистичным выводам о нейросетевом подходе в целом .
Решение задачи с помощью многослойных сетей
Проблема XOR решается добавлением как минимум одного скрытого слоя нейронов с нелинейными функциями активации . В такой архитектуре скрытые нейроны могут выучить промежуточные представления, например, функции И (AND) и И-НЕ (NAND), которые затем комбинируются выходным нейроном для получения функции XOR . Математически это описывается как композиция функций <math>XOR(x_1, x_2) = AND(OR(x_1, x_2), NAND(x_1, x_2))</math> .
Стандартная архитектура для решения XOR — Многослойный перцептрон с двумя входами, скрытым слоем из двух нейронов и одним выходом (2-2-1) . Эффективный алгоритм обучения таких сетей, обратное распространение ошибки, был популяризирован в 1986 году, что ознаменовало возрождение интереса к нейронным сетям .
Альтернативные решения
Исследования показывают, что задачу XOR можно решить и в однослойной архитектуре, если использовать специальные нелинейные функции активации или расширить пространство признаков :
- Функции активации: Использование нестандартных активаций, таких как 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> .
