Задача XOR

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

Версия 16:10, 11 июля 2026 (править) Alfina Iamaeva (Обсуждение | вклад) (→Определение и математическая постановка) ← К предыдущему изменению		Версия 16:18, 11 июля 2026 (править) (отменить) Alfina Iamaeva (Обсуждение | вклад) К следующему изменению →
Строка 1:		Строка 1:
-	== Задача XOR ==	+	= '''Задача XOR''' (исключающее ИЛИ) — классическая задача в области [[искусственные нейронные сети|нейронных сетей]] и [[машинное обучение|машинного обучения]], которая иллюстрирует фундаментальное ограничение [[персептрон|однослойного персептрона]] и демонстрирует необходимость использования [[многослойный персептрон|многослойных архитектур]] для решения нелинейно разделимых проблем. Суть задачи заключается в построении классификатора для логической функции XOR, которая возвращает истинное значение (1), если её два бинарных входа различны, и ложное (0), если они совпадают. Задача XOR является простейшим случаем функции [[четность|чётности]] (PARITY) для двух бит и широко используется как педагогический пример для объяснения принципов работы и ограничений нейросетей.
-	**Задача XOR** (от англ. ''exclusive OR'' — исключающее «ИЛИ») — это классическая задача в области [[машинное обучение|машинного обучения]] и [[искусственные нейронные сети|искусственных нейронных сетей]], которая заключается в построении модели, способной выучить функцию [[Исключающее «ИЛИ»|исключающего ИЛИ]] (XOR). Эта функция принимает два бинарных входа и возвращает 1, если входы различаются, и 0, если они совпадают .	+	== Постановка задачи ==
		+	[[Файл:XOR problem 4 points.svg|thumb|right|Графическое представление задачи XOR. Четыре точки в углах квадрата не могут быть разделены одной прямой линией.]]
-	Несмотря на кажущуюся простоту, задача XOR стала важнейшим рубежом в истории искусственного интеллекта, поскольку она наглядно демонстрирует фундаментальные ограничения линейных моделей классификации. Она является простейшей булевой функцией, которая не является [[линейная разделимость|линейно разделимой]], и поэтому не может быть решена с помощью однослойного [[персептрон|персептрона]] . Эта проблема, подробно описанная в книге Марвина Минского и Сеймура Пейперта «Персептроны» (1969), сыграла ключевую роль в наступлении «[[зима искусственного интеллекта|зимы искусственного интеллекта]]» — периода значительного спада интереса и финансирования исследований нейронных сетей, длившегося с конца 1960-х до середины 1980-х годов .	+	Даны четыре точки в двумерном пространстве признаков, соответствующие всем возможным комбинациям бинарных входов <math>x_1, x_2 \in \{0, 1\}</math>:
		+	* <math>(0, 0) \rightarrow 0</math>
		+	* <math>(0, 1) \rightarrow 1</math>
		+	* <math>(1, 0) \rightarrow 1</math>
		+	* <math>(1, 1) \rightarrow 0</math>
-	=== Определение и математическая постановка ===	+	Эти точки располагаются в углах единичного квадрата. Точки, принадлежащие разным классам (0 и 1), расположены по диагонали. Задача состоит в том, чтобы найти классификатор, который правильно разделит эти два класса.
-	Функция XOR определяется следующей таблицей истинности :	+	== Нелинейная разделимость ==
		+	Ключевое свойство задачи XOR заключается в том, что она не является [[линейная разделимость|линейно разделимой]]. Это означает, что невозможно провести одну прямую линию на плоскости, которая бы разделила точки двух классов. Доказательство этого факта может быть выполнено геометрически или алгебраически. Например, любая попытка провести линию, разделяющую точки (0,0) и (1,1) от точек (0,1) и (1,0), обречена на неудачу, поскольку эти множества не являются выпуклыми и разделимыми гиперплоскостью.
-	{| class="wikitable" style="margin:auto"	+	== Ограничения однослойного персептрона ==
-	|+ Таблица истинности для функции XOR	+	[[Персептрон]], предложенный [[Фрэнк Розенблатт|Фрэнком Розенблаттом]] в 1957 году, представляет собой простейшую нейронную сеть, состоящую из одного слоя [[искусственный нейрон|искусственных нейронов]]. Его выход для вектора признаков <math>\mathbf{x}</math> вычисляется как <math>y = \sigma(w_1 x_1 + w_2 x_2 + b)</math>, где <math>\sigma</math> — ступенчатая функция активации, <math>w_i</math> — веса, <math>b</math> — смещение.
-	|-	+
-	! Вход <tex>x_1</tex> !! Вход <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>w_1, w_2, b</math> ни был выбран, всегда найдётся по крайней мере одна точка, которая будет классифицирована неверно.
-	Алгебраически XOR может быть выражен несколькими способами :	+	=== Историческое значение: «Зима ИИ» ===
-	* <math>x_1 \oplus x_2 = x_1 + x_2 - 2x_1x_2</math>	+	Доказательство неспособности персептрона решить задачу XOR стало центральным аргументом в книге [[Марвин Минский|Марвина Минского]] и [[Сеймур Пейперт|Сеймура Пейперта]] «'''Персептроны'''» (1969 год). Авторы провели строгий математический анализ возможностей и ограничений однослойных персептронов. Хотя Минский и Пейперт знали, что добавление скрытого слоя может решить проблему, они указали на отсутствие в то время эффективного алгоритма обучения для таких сетей.
-	* <math>x_1 \oplus x_2 = |x_1 - x_2|</math>	+
-	=== Историческое значение ===	+	Критика, прозвучавшая в книге, оказала разрушительное влияние на область исследований нейронных сетей. Финансирование этой области было резко сокращено, а интерес к нейронным сетям практически угас на долгие годы. Этот период в истории искусственного интеллекта получил название «'''[[Зима ИИ|первая зима ИИ]]'''», которая длилась примерно с 1969 по середину 1980-х годов.
-	Задача XOR стала центральной в критике однослойного персептрона, предложенного [[Фрэнк Розенблатт|Фрэнком Розенблаттом]] в конце 1950-х годов. В своей книге «Персептроны» Марвин Минский и Сеймур Пейперт строго математически доказали, что однослойный персептрон неспособен выучить функцию XOR, поскольку ее классы нелинейно разделимы . Хотя Минский и Пейперт знали, что добавление скрытого слоя решает проблему , на тот момент не существовало эффективного алгоритма обучения для многослойных сетей, что привело к пессимистическим выводам о потенциале нейросетевого подхода в целом. Это событие, наряду с другими факторами, вызвало «зиму искусственного интеллекта», когда финансирование и интерес к нейронным сетям резко упали .	+	== Решение задачи с помощью многослойного персептрона ==
		+	Проблема XOR решается с помощью добавления одного или нескольких '''[[скрытый слой|скрытых слоёв]]''' нейронов, что приводит к созданию '''[[многослойный персептрон|многослойного персептрона]]''' (MLP). Ключевая идея заключается в том, чтобы разложить нелинейную функцию XOR на комбинацию более простых, линейно разделимых функций. Например, функцию XOR можно представить как: <math>\text{XOR}(x_1, x_2) = \text{OR}(\text{AND}(x_1, \neg x_2), \text{AND}(\neg x_1, x_2))</math>.
-	=== Решение задачи с помощью нейронных сетей ===	+	Архитектура MLP для решения задачи XOR включает в себя:
		+	# Входной слой с двумя нейронами (для <math>x_1</math> и <math>x_2</math>).
		+	# Скрытый слой с как минимум двумя нейронами. Каждый нейрон в этом слое обучается распознавать одну из линейно разделимых подзадач (например, один нейрон активируется для точки (0,1), а другой — для (1,0)).
		+	# Выходной слой с одним нейроном, который комбинирует выходы скрытого слоя, чтобы получить окончательный результат XOR.
-	Задача XOR решается использованием [[многослойный персептрон|многослойного персептрона]] (MLP), который вводит один или несколько скрытых слоев с нелинейными [[функция активации|функциями активации]] . Эти скрытые слои позволяют сети трансформировать исходное пространство признаков таким образом, что данные становятся линейно разделимыми на выходном слое.	+	Математически, скрытый слой преобразует исходное пространство признаков в новое пространство, где данные становятся линейно разделимыми. Например, нейроны скрытого слоя могут реализовать функции '''AND''' и '''NAND''', а выходной нейрон — функцию '''OR''', что в совокупности даёт XOR. Обучение такой сети стало возможным благодаря разработке и популяризации '''[[алгоритм обратного распространения ошибки|алгоритма обратного распространения ошибки]]''' (backpropagation) в 1986 году, что положило конец «зиме ИИ» и привело к возрождению интереса к нейронным сетям.
-	==== Архитектура сети ====	+	=== Теорема о универсальной аппроксимации ===
-	Простейшая нейронная сеть, решающая задачу XOR, имеет следующую архитектуру :	+	Способность многослойных нейронных сетей решать задачу XOR является частным случаем более общего результата — '''[[теорема о универсальной аппроксимации|теоремы о универсальной аппроксимации]]'''. Согласно этой теореме, многослойный персептрон с по крайней мере одним скрытым слоем и нелинейной функцией активации может аппроксимировать любую непрерывную функцию на компактном множестве с любой желаемой точностью. Это теоретическое обоснование делает MLP мощным инструментом для решения широкого круга задач, выходящих за рамки простой линейной классификации.
-	* '''Входной слой:''' 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 сохраняет своё значение и в современных исследованиях. Она используется как простой тестовый полигон для изучения:
		+	* Динамики обучения нейронных сетей с помощью [[стохастический градиентный спуск|стохастического градиентного спуска]] (SGD).
		+	* Явления [[переобучение|переобучения]] и обобщения в различных архитектурах.
		+	* Анализа поведения сетей в условиях «нулевого зазора» (zero-margin), когда данные лежат непосредственно на разделяющей поверхности.
-	==== Алгоритм обучения ====	+	Таким образом, задача XOR, начав свой путь как демонстрация фатального недостатка ранних нейросетей, превратилась в фундаментальный учебный пример и важный инструмент для понимания принципов глубокого обучения.
-	Обучение многослойного персептрона для решения задачи XOR стало возможным благодаря алгоритму [[обратное распространение ошибки|обратного распространения ошибки]] (backpropagation), который был популяризирован в 1986 году . Этот алгоритм позволяет эффективно вычислять градиент функции потерь относительно всех весов сети, включая веса скрытых слоев. С появлением обратного распространения ошибки и открытием [[теорема о полноте|теоремы о полноте]] интерес к нейронным сетям возродился, что привело к современной эпохе [[глубокое обучение|глубокого обучения]] .	+
-		+
-	=== Современные взгляды и альтернативные решения ===	+
-		+
-	Хотя традиционно для решения задачи XOR требуется скрытый слой, современные исследования показывают, что использование некоторых продвинутых функций активации, таких как [[PReLU|Parametric ReLU (PReLU)]] или [[GCU|Growing Cosine Unit (GCU)]], позволяет решить ее даже в однослойной сети без скрытых слоев . Это становится возможным благодаря способности этих функций создавать нелинейные и немонотонные разделяющие поверхности. Данное открытие имеет значение для проектирования более эффективных архитектур нейронных сетей.	+
-		+
-	Кроме того, существуют подходы к решению задачи XOR, не связанные с классическими нейронными сетями, например, с использованием комитетных конструкций или методов математического программирования . Задача XOR также служит простейшим бенчмарком для проверки новых архитектур и алгоритмов обучения, включая [[квантовое машинное обучение|вариационные квантовые классификаторы]] , и обобщается на многоклассовые варианты, такие как задача <math>XOR_p</math> на основе вычитания по модулю <math>p</math> .	+
-		+
-	== См. также ==	+
-	* [[Искусственный нейрон]]	+
-	* [[Функция активации]]	+
-	* [[Логистическая регрессия]]	+
-	* [[Метод опорных векторов]]	+
-	* [[Аппроксимация функций]]	+
	== Примечания ==		== Примечания ==
	<references />		<references />
		+
		+	== Литература ==
		+	* Minsky, M., & Papert, S. (1969). ''Perceptrons''. MIT Press.
		+	* Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. ''Nature'', 323(6088), 533-536.

---

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

= Задача XOR (исключающее ИЛИ) — классическая задача в области нейронных сетей и машинного обучения, которая иллюстрирует фундаментальное ограничение однослойного персептрона и демонстрирует необходимость использования многослойных архитектур для решения нелинейно разделимых проблем. Суть задачи заключается в построении классификатора для логической функции XOR, которая возвращает истинное значение (1), если её два бинарных входа различны, и ложное (0), если они совпадают. Задача XOR является простейшим случаем функции чётности (PARITY) для двух бит и широко используется как педагогический пример для объяснения принципов работы и ограничений нейросетей.

Содержание 1 Постановка задачи 2 Нелинейная разделимость 3 Ограничения однослойного персептрона 3.1 Историческое значение: «Зима ИИ» 4 Решение задачи с помощью многослойного персептрона 4.1 Теорема о универсальной аппроксимации 5 Современное значение 6 Примечания 7 Литература

Постановка задачи

thumb|right|Графическое представление задачи XOR. Четыре точки в углах квадрата не могут быть разделены одной прямой линией.

Даны четыре точки в двумерном пространстве признаков, соответствующие всем возможным комбинациям бинарных входов <math>x_1, x_2 \in \{0, 1\}</math>:

• <math>(0, 0) \rightarrow 0</math>
• <math>(0, 1) \rightarrow 1</math>
• <math>(1, 0) \rightarrow 1</math>
• <math>(1, 1) \rightarrow 0</math>

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

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

Ключевое свойство задачи XOR заключается в том, что она не является линейно разделимой. Это означает, что невозможно провести одну прямую линию на плоскости, которая бы разделила точки двух классов. Доказательство этого факта может быть выполнено геометрически или алгебраически. Например, любая попытка провести линию, разделяющую точки (0,0) и (1,1) от точек (0,1) и (1,0), обречена на неудачу, поскольку эти множества не являются выпуклыми и разделимыми гиперплоскостью.

Ограничения однослойного персептрона

Персептрон, предложенный Фрэнком Розенблаттом в 1957 году, представляет собой простейшую нейронную сеть, состоящую из одного слоя искусственных нейронов. Его выход для вектора признаков <math>\mathbf{x}</math> вычисляется как <math>y = \sigma(w_1 x_1 + w_2 x_2 + b)</math>, где <math>\sigma</math> — ступенчатая функция активации, <math>w_i</math> — веса, <math>b</math> — смещение.

Решение, которое может найти персептрон, эквивалентно построению линейной разделяющей поверхности (прямой на плоскости или гиперплоскости в многомерном пространстве). Было математически доказано, что персептрон не может выучить функцию XOR, поскольку она не является линейно разделимой. Это означает, что какой бы набор весов <math>w_1, w_2, b</math> ни был выбран, всегда найдётся по крайней мере одна точка, которая будет классифицирована неверно.

Историческое значение: «Зима ИИ»

Доказательство неспособности персептрона решить задачу XOR стало центральным аргументом в книге Марвина Минского и Сеймура Пейперта «Персептроны» (1969 год). Авторы провели строгий математический анализ возможностей и ограничений однослойных персептронов. Хотя Минский и Пейперт знали, что добавление скрытого слоя может решить проблему, они указали на отсутствие в то время эффективного алгоритма обучения для таких сетей.

Критика, прозвучавшая в книге, оказала разрушительное влияние на область исследований нейронных сетей. Финансирование этой области было резко сокращено, а интерес к нейронным сетям практически угас на долгие годы. Этот период в истории искусственного интеллекта получил название «первая зима ИИ», которая длилась примерно с 1969 по середину 1980-х годов.

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

Проблема XOR решается с помощью добавления одного или нескольких скрытых слоёв нейронов, что приводит к созданию многослойного персептрона (MLP). Ключевая идея заключается в том, чтобы разложить нелинейную функцию XOR на комбинацию более простых, линейно разделимых функций. Например, функцию XOR можно представить как: <math>\text{XOR}(x_1, x_2) = \text{OR}(\text{AND}(x_1, \neg x_2), \text{AND}(\neg x_1, x_2))</math>.

Архитектура MLP для решения задачи XOR включает в себя:

1. Входной слой с двумя нейронами (для <math>x_1</math> и <math>x_2</math>).
2. Скрытый слой с как минимум двумя нейронами. Каждый нейрон в этом слое обучается распознавать одну из линейно разделимых подзадач (например, один нейрон активируется для точки (0,1), а другой — для (1,0)).
3. Выходной слой с одним нейроном, который комбинирует выходы скрытого слоя, чтобы получить окончательный результат XOR.

Математически, скрытый слой преобразует исходное пространство признаков в новое пространство, где данные становятся линейно разделимыми. Например, нейроны скрытого слоя могут реализовать функции AND и NAND, а выходной нейрон — функцию OR, что в совокупности даёт XOR. Обучение такой сети стало возможным благодаря разработке и популяризации алгоритма обратного распространения ошибки (backpropagation) в 1986 году, что положило конец «зиме ИИ» и привело к возрождению интереса к нейронным сетям.

Теорема о универсальной аппроксимации

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

Современное значение

Задача XOR сохраняет своё значение и в современных исследованиях. Она используется как простой тестовый полигон для изучения:

• Динамики обучения нейронных сетей с помощью стохастического градиентного спуска (SGD).
• Явления переобучения и обобщения в различных архитектурах.
• Анализа поведения сетей в условиях «нулевого зазора» (zero-margin), когда данные лежат непосредственно на разделяющей поверхности.

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

Примечания

Литература

• Minsky, M., & Papert, S. (1969). Perceptrons. MIT Press.
• Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533-536.